COL333/671: Introduction to AI

Semester I, 2021

What is AI?

Rohan Paul
This Class
• Different theoretical foundations of AI.
• What does AI try to accomplish?
• Historical developments.
• AI problem solving techniques.
• Reference Material
• AIMA Ch. 1 and Ch. 2 (2.1-2.3)
Acknowledgement
These slides are intended for teaching purposes only. Some material
has been used/adapted from web sources and from slides by Dorsa
Sadigh, Percy Liang, Mausam, Dan Klein, Nicholas Roy and others.
Adapted from D. Klein
AI: Informal Definition

•Models and algorithms that lead to intelligent

behavior or solve problems that require human-
like intelligence.
Slide adapted from Mausam

What is Intelligence?

A machine can never do a task X. AI researchers respond by

making a computer do X.
Perceptual Tasks: Natural Language
• Speech technologies (e.g. Siri, Alexa)
• Automatic speech recognition (ASR)
• Text-to-speech synthesis (TTS)
• Language generation

• Language processing technologies

• Question answering
• Machine translation
• Web search
• Text classification, spam filtering, etc…

Adapted from D. Klein

https://visualdialog.org/
Perceptual Tasks: Visual Recognition
§ Object and face recognition https://vision-explorer.allenai.org/
§ Scene segmentation
§ Image classification

Images from Erik Sudderth (left), wikipedia (right) Adapted from D. Klein
Planning Tasks
• Predicting Structures
• Given an amino acid sequence
predict its structure.
• How a protein folds -> functional
characteristics
• Sequential Decision-making
• Game Playing
• Deep Blue
• Alpha Go
• Treatment recommendation
Logic and Reasoning
• Logical systems
• Theorem provers
• Fault diagnosis. Medical diagnosis.
• Manufacturing planning

• Methods:
• Deduction systems
• Satisfiability solvers

Adapted from D. Klein

Robotics/Embodied AI
• Intelligent cars that can drive
autonomously
• Intelligent manipulation tasks
• Unmanned exploration.
• Machine capable of walking

https://www.youtube.com/watch?v=J
TVJkJavU6g
https://www.youtube.com/watch?v=u
Wv-l7XMoB8

Images from UC Berkeley, Boston Dynamics, RoboCup, Google, WIkipedia

When is a computer program or system
displaying AI capabilities?
Various perspectives based on how we assess performance
• Human-centered
• Comparison with human performance.
• Empirical observations and hypothesis about human behaviour.
• Engineering viewpoint.
• Comparison with a rational or right thing given what it knows (objective function).
• Performance w.r.t. an objective.
• Thinking vs. Acting
• Displaying input/output behaviour vs. Human-like way to arrive at the conclusion.
Acting Humanly: The Turing Test

Faculties
Natural Language Processing Alan Turing
Knowledge Representation
Automated Reasoning
Machine Learning
Computer Vision
Robotics
Thinking Humanly
• Cognitive Science
• How humans or animals perceive and act in the the world.
• Efforts to build testable models of human reasoning about tasks
and problems.
• What are the tools?
• Introspection. Psychological experiments.

• Aim
• A program or an AI system is considered intelligent if its trace or
reasoning process matches the steps that a cognitive model of
human would take for a task/problem.
• Back and forth. A computer program really well on a task. Then it
should inform our understanding of human reasoning.

• Applications
• Intelligent tutoring systems
• Human computer interaction
AI: Two views
• Thinking and Acting humanly
• Thought processes and reasoning.
• Leading to human-like behavior.
• Thinking and Acting rationally
• System is rational if it does the “right thing” given what it knows.
• Measuring against an ideal performance measure.
• Engineering approach.
Agent View of AI
• What is an agent?
• An agent is anything that can be
viewed as perceiving its environment
Sensors
through sensors and acting upon that

Environment
Percepts
environment through actuators.
?

Agent
• Examples
• Alexa Actuators
Actions
• Robotic system
• Refinery controller
• Question answering system
• Crossword puzzle solver
• ……
Agent View of AI
• Agent Type
• Performance Measure
• Environment
• Actuators
• Sensors
Domain Characteristics
• Fully or Partially observed
• Single or Multiple Agents
• Deterministic or Stochastic
• Episodic or Sequential
• Static or Dynamic
• Discrete or Continuous

AIMA Ch 2. Sec 2.3

Acting Rationally: Maximizing Expected Utility
§ An agent is an entity that perceives and acts.

Environment
§ Rational agent Sensors
Percepts

Agent
?
§ A rational agent selects actions that maximize its (expected)
Actuators
utility. The agent prefers those actions that take it closer to its Actions

objective.
§ Rationality implies: the agent must act to achieve the best
outcome (deterministic case) or the best expected outcome
(stochastic case).
§ Characteristics of the percepts, environment, and action space
dictate techniques for selecting rational action.
§ Rationality viewpoint lends itself to a mathematical formalism
§ Objective function and costs and algorithms that can maximize the agent’s
objective. Find the best agent for the architecture. Slide adapted from D. Klein
Thinking Rationally: Laws of Thought
• This perspective says that an AI system should
display a logical thought process.
• Aristotle
• Logical way of deduction and reasoning.
• But sometimes we act even without deliberation
• Reflex actions occur without deliberation.
• E.g., reflex action if we touch something hot.
Strong AI vs. Weak AI Hypothesis
• Weak AI Hypothesis
• Can machines act intelligently?
• A system that passes the Turing test (appears to be acting humanly) may not be actually
thinking. It may be only be a simulation of thinking.
• Strong AI Hypothesis
• Can machines really think?
• Machines that act intelligently not just by simulating but actually by thinking. Awareness
of its mental states and process of arriving at a solution.
How to solve AI tasks?
Problem: planning routes in a city. AI system: computational model that can
provide you a route.

Slide adapted from Sadigh & Liang

1. Modeling
• Routing problem as a
graph.

Slide adapted from Sadigh & Liang

2. Inference
• Path finding algorithm
that runs on the graph.

Slide adapted from Sadigh & Liang

3. Learning
• We can make use of past data.
• Learning parameters

Slide adapted from Sadigh & Liang

We will explore a variety of models
• State-based Models
• Variable based Models
• Decision-making models
• Reflex Models Models that reason with world states

Reflex models. Example, a neural

network classifying images.
Constraint satisfaction models Probabilistic Models
Slide adapted from Sadigh & Liang
History – Gestation Phase (1943-1955)
• Can we simulate a neuron?
• Artificial neurons that turn on/off states based on
inputs.
• Showing that a neural network could learn (Mc Culloch
and Pitts)
• Simple updating rule to learn (Hebbian learning by
Donald Hebb 1949)
• Turing
• Proposed the Turing Test
• “Computing Machinery and Intelligence”
History – Birth of the Field (1956)
• Workshop at Dartmouth College;
• John McCarthy, Marvin Minsky, Claude Shannon,
etc.
• Set an agenda for researchers:
• Every aspect of learning or any other feature of
intelligence can be so precisely described that a
Dartmouth
machine can be made to simulate it.
• Attempt to build machines that will function
autonomously in complex changing environments.
• Proposed a separate field of AI to address this
agenda.

Slide adapted from Sadigh & Liang

History – Early Era (till 1970s)
• General Problem Solver (1955)
• Newell & Simon's Logic Theorist: prove theorems
in Principia Mathematica using search + heuristics;
solving puzzles. Newell & Simon
• Accept new axioms on the fly.
• SHRLDU (1972)
• Winograd. Micro-world to re-arrange blocks on
the table. Language understanding
• Challenges
• Limited Computation (could not manage state
spaces)
• Limited information (complexity of the real world)
SHRLDU:
https://www.youtube.com/watch?v=bo4RvYJYOzI
History – Expert Systems (1969 - 1979)
• Knowledge-based systems
• Elicit specific domain knowledge from experts in
form of rules:
• if [premises] then [conclusion]
• DENDRAL
DENDRAL expert system
• Infer molecular structure from mass spectrometry data.
Input is a molecular formula and how it gets
fragmented during experiments.
• The program deduced possible structures consistent
with data.
• Limitation
• No notion of uncertainty
History – Embracing uncertainty (1987s
onwards till 2000s)
• Decision making under uncertainty.
• Probabilistic models.
Speech recognition. HMMs.

Darpa Grand Challenge (2005) https://www.youtube.com/watch?v=M2AcMnfzpNg

Remote agent program on Deep Space I (1999)

https://ti.arc.nasa.gov/tech/asr/groups/planning-and-scheduling/remote-agent/
History – Deep learning (2012 onwards)
• Confluence of three things:
• Large data sets
• Large amounts of
computation
• Improved algorithms and
optimization.

• Vast improvement in certain

tasks.
• Recognition.
• Game playing.

Slide adapted from Sadigh, Liang, Mausam

AI has been influenced by many disciplines

Slide adapted from Sadigh & Liang

Next Time

• This Class
• What is AI?
• Next Class
• Problem solving as search