Artificial Intelligence
(Based on Slides by Stuart Russell, Henry Kautz, B
Ravindran, Subbarao Kambhampati, and UW-AI
faculty)
Theory
Modeling
Algoirthm
Applications
HISTORY
1946: ENIAC heralds the dawn of Computing
Electronic Numerical Integrator and Computer
1950: Turing asks the question….
I propose to consider the question:
“Can machines think?”
--Alan Turing, 1950
1956: A new field is born
• We propose that a 2 month,
10 man study of artificial
intelligence be carried out
during the summer of 1956
at Dartmouth College in
Hanover, New Hampshire.
– Dartmouth AI Project
Proposal; J. McCarthy et al.;
Aug. 31, 1955.
Stanford
CMU
MIT
1956-1966
• 1950: Turing Test for Machine Intelligence
• 1956: AI born at Dartmouth College Workshop
• 1964: Eliza – the chatbot psychotherapist
• 1966: Shakey – general purpose mobile robot
=> A* search algorithm
AI Winters
• 1974 – 1980: Winter #1
– Failure of machine translation
– Negative results in Neural nets
– Poor speech understanding
• 1987 – 1993: Winter #2
– Decline of LISP
– Decline of specialized hardware for expert systems
• Lasting effects
– [Economist07] “Artificial Intelligence is associated with systems that
have all too often failed to live up to their promises.”
– [Pittsburgh BT06] “Some believe the word 'robotics' actually carries a
stigma that hurts a company's chances at funding.”
1996: EQP proves that
Robbin’s Algebras are all boolean
Equational Theorem Prover
----- EQP 0.9, June 1996 -----
The job began on eyas09.mcs.anl.gov, Wed Oct 2 12:25:37 1996
UNIT CONFLICT from 17666 and 2 at 678232.20 seconds.
---------------- PROOF ----------------
2 (wt=7) [] -(n(x + y) = n(x)).
3 (wt=13) [] n(n(n(x) + y) + n(x + y)) = y.
5 (wt=18) [para(3,3)] n(n(n(x + y) + n(x) + y) + y) = n(x + y).
6 (wt=19) [para(3,3)] n(n(n(n(x) + y) + x + y) + y) = n(n(x) + y).
…….
17666 (wt=33) [para(24,16426),demod([17547])] n(n(n(x) + x) ….
[An Argonne lab program] has come up with a major mathematical
proof that would have been called creative if a human had thought of it.
-New York Times, December, 1996
1997: Deep Blue ends Human
Supremacy in Chess
vs.
I could feel human-level intelligence across the room
-Gary Kasparov, World Chess Champion (human)
In a few years, even a single victory
in a long series of games would be the triumph of human genius.
Success Story: Chess
Does Deep Blue use AI? Saying Deep Blue
doesn’t really think about
chess is like saying an
airplane doesn’t really fly
because it doesn’t flap
its wings.
“If it works, its not AI!” – Drew McDermott
23
1999: Remote Agent takes
Deep Space 1 on a galactic ride
Mission-level
actions &
Goals Scripts resources
Generative
Planner &
Scheduler
Executive
Scripted
Generative
Mode Identification
ESL & Recovery
component models
Monitors
Real-time Execution
Adaptive Control
Hardware
For two days in May, 1999, an AI Program called Remote Agent
autonomously ran Deep Space 1 (some 60,000,000 miles from earth)
2004 & 2009
28
2005: Cars Drive Themselves
• Stanley and three
other cars drive
themselves over a
132 mile
mountain road
Stanford Professor and
team won
2005: Cars Drive Themselves
• Stanley and three other cars drive themselves over
a 132 mile mountain road
2011: IBM’s Watson
And Ken Jennings pledges obeisance to the new Computer Overlords..
2011: IBM’s Watson
https://www.youtube.com/watch?v=WFR3lOm_xhE
PRESENT
2016: AlphaGo
Google acquired DeepMind
© https://www.buzzfeednews.com/article/alexkantrowitz/were-in-an-artificial-intelligence-hype-cycle
What Changed?
Data
Deep Learning
Neural networks
Object Recognition
40
Artistic
Applications
!
• Doodle to
Painting!
• Style
Transfer
• Image
Colorization
https://arxiv.org/pdf/1603.08511.pdf
https://arxiv.org/pdf/1603.01768.pdf
41
https://github.com/jcjohnson/fast-neural-style
Image Caption
Automatic Speech Recognition
(c) https://medium.com/@gaurav.sharma/voice-is-the-new-o-s-and-the-future-of-search-
commerce-and-payments-64fc8cc848f6
“if it works it is not AI” “its all AI”
• By 2050, develop a team of fully autonomous humanoid
robots that can win against the human world champion
team in soccer.
49
The Definition of AI
Science of AI
Physics: Where did the physical universe come from?
And what laws guide its dynamics?
Biology: How did biological life evolve?
And how do living organisms function?
AI: What is the nature of intelligent thought?
© Daniel S. Weld 53
What is intelligence?
What is intelligence?
• Dictionary.com: capacity for learning, reasoning,
understanding, and similar forms of mental activity
What is intelligence?
• Dictionary.com: capacity for learning, reasoning,
understanding, and similar forms of mental activity
• Ability to perceive and act in the world
• Reasoning: proving theorems, medical diagnosis
• Planning: take decisions
• Learning and Adaptation: recommend movies,
learn traffic patterns
• Understanding: text, speech, visual scene
Intelligence vs. humans
• Are humans intelligent?
– replicating human behavior early hallmark of intelligence
• Are humans always intelligent?
• Can non-human behavior be intelligent?
Today, the best chess player is a collaboration of human and AI
system.
What is artificial intelligence?
human-like vs. rational
Dictionary
“[automation of] activities “The study of mental
that we associate with faculties through the use of
human thinking, activities computational models”
such as decision making, (Charniak & McDertmott
problem solving, learning…” 1985)
thought (Bellman 1978) Thinking
vs. “The study of how to make “The branch of computer
behavior computers do things at science that is concerned
which, at the moment, with the automation of
people are better” (Rich & intelligent behavior” (Luger &
Knight 1991) Stubblefield 1993)
If it works, it is not AI
© Daniel S. Weld 56
What is artificial intelligence?
human-like vs. rational
Systems that think Systems that think
thought
like humans rationally
vs.
behavior Systems that act like Systems that act
humans rationally
© Daniel S. Weld 57
Thinking Humanly
• Cognitive Science
– Very hard to understand how humans think
• Post-facto rationalizations, irrationality of human thinking
• Do we want a machine that beats humans in chess or a machine
that thinks like humans while beating humans in chess?
– Deep Blue supposedly DOESN’T think like humans..
• Thinking like humans important in Cognitive Science applications
– Intelligent tutoring
– Expressing emotions in interfaces… HCI
Thinking Rationally: laws of thought
• Aristotle: what are correct arguments/thought
processes?
– Logic
• Problems
– Not all intelligent behavior is mediated by logical
deliberation (reflexes)
– What is the purpose of thinking?
thinking should be purposeful, goal oriented
Acting Humanly: Turing’s Test
• If the human cannot tell whether the responses
from the other side of a wall are coming from a
human or computer, then the computer is
intelligent.
60
Acting Humanly
• Loebner Prize for Turing test
– Every year in Boston
– Expertise-dependent tests: limited conversation
• What if people call a human a machine?
– Shakespeare expert
– Make human-like errors
• Problems
– Not reproducible, constructive or mathematically analyzable
Acting rationally
• Rational behavior: doing the right thing
• Need not always be deliberative
– Reflexive
• Aristotle (Nicomachean ethics)
– Every art and every inquiry, and similarly every action
and every pursuit is thought to aim at some good.
Acting rationally is a good idea
Acting Thinking?
• Weak AI Hypothesis vs. Strong AI hypothesis
– Weak Hyp: machines could act as if they are
intelligent (act intelligently without thinking intelligently)
– Strong Hyp: machines that act intelligent have to
think intelligently too
Rational Agents
• An agent should strive to do the right thing, based on what
it can perceive and the actions it can perform. The right
action is the one that will cause the agent to be most
successful
• Performance measure: An objective criterion for success of
an agent's behavior (optimize the objective function)
• E.g., performance measure of a vacuum-cleaner agent
could be amount of dirt cleaned up, amount of time taken,
amount of electricity consumed, amount of noise
generated, etc.
64
Ideal Rational Agent
“For each possible percept sequence, does
whatever action is expected to maximize its
performance measure on the basis of evidence
perceived so far and built-in knowledge.''
• Rationality vs omniscience? (state of knowing everything)
• Acting in order to obtain valuable information which can be
used to optimize the objective function
What is artificial intelligence (agent view)
• An agent is anything that can be viewed as perceiving its
environment through sensors and acting upon that
environment through actuators
• Human agent:
– eyes, ears, and other organs for sensors
– hands, legs, mouth, and other body parts for actuators
• Robotic agent:
– cameras and laser range finders for sensors
– various motors for actuators
Examples: Formal Cognitive Tasks
• Games
– Chess
– Checkers
– Othello
• Mathematics
– Logic
– Geometry
– Calculus
– Proving properties of programs
67
Examples: Expert Tasks
• Engineering
– Design
– Fault Finding
– Manufacturing planning
• Medical
– Diagnosis
– Medical Image Analysis
• Financial
– Stock market predictions
68
Examples: Perceptual Tasks
• Perception
– Vision
we do them intuitively,
– Speech but difficult for machines
• Natural Language
– Understanding
– Generation
– Translation
• Robot Control
69
What is artificial intelligence
(algorithmic view)
• A large number of problems are NP hard
cannot be solved in polynomial time
• AI develops a set of tools, heuristics, …
– to solve such problems in practice (Effective solution)
– for naturally occurring instances, not random problems
• Search
• Game Playing
• Planning
• …
Recurrent Themes
• Weak vs. Knowledge-based Methods
• Weak – general search methods (e.g., A* search)
• primarily for problem solving
• not motivated by achieving human-level performance
• Strong AI -- knowledge intensive (e.g., expert systems)
• more knowledge less computation
• achieve better performance in specific tasks
• How to combine weak & strong methods seamlessly?
© Daniel S. Weld 74
Recurrent Themes
• Logic vs. Probabilistic vs. Neural
–In 1950s, logic dominates
• attempts to extend logic
–1988 – Bayesian networks
• efficient computational framework
–2013 – deep neural networks
• powerful representation across modalities
© Daniel S. Weld 75
• Phase 1: Search, Constraint Satisfaction, Logic,
Games
• Phase 2: Uncertainty (decision theory,
probabilistic knowledge representation),
Learning (reinforcement)
• Phase 3: Deep Neural Networks
