Reference Book
• -
Artificial Intelligence: A Modern Approach
– Stuart Russell and Peter Norving
-
Slide Set 1: Introduction: 0
Goals of this Course
• This class is a broad introduction to artificial intelligence (AI)
– AI is a very broad field with many subareas
– We will cover many of the primary concepts/ideas
Loading…
Slide Set 1: Introduction: 0
Why AI can change our life…..
• As we begin the new millenium
– science and technology are changing rapidly
– “old” sciences such as physics are relatively well-understood
– computers are ubiquitous
• Grand Challenges in Science and Technology
+h
– understanding the brain -
- -
• reasoning, cognition, creativity
– creating intelligent machines
• is this possible?
• what are the technical and philosophical challenges?
– arguably AI poses the most interesting challenges and questions in
computer science today
Slide Set 1: Introduction: 0
This Lecture
• What is intelligence? What is artificial intelligence?
• A very brief history of AI -
– Modern successes: Stanley the driving robot
• An AI scorecard
–
Loading…
How much progress has been made in different aspects of AI
• AI in practice
– Successful applications
• The rational agent view of AI
Slide Set 1: Introduction: 0
What is Intelligence?
l
• Intelligence:
– “the capacity to learn and solve problems” (Websters dictionary)
– in particular,
• the ability to solve novel problems
• the ability to act rationally
• the ability to act like humans
• Artificial Intelligence
– build and understand intelligent entities or agents
– 2 main approaches: “engineering” versus “cognitive modeling”
Slide Set 1: Introduction: 0
What’s involved in Intelligence?
• Ability to interact with the real world
y
– to perceive, understand, and act
– e.g., speech recognition and understanding and synthesis
– e.g., image understanding - e
– e.g., ability to take actions, have an effect F
• Reasoning and Planning
En
– modeling the external world, given input
– solving new problems, planning, and making decisions
– ability to deal with unexpected problems, uncertainties
• Learning and Adaptation
u
– we are continuously learning and adapting
– our internal models are always being “updated”
• e.g., a baby learning to categorize and recognize
animals
Slide Set 1: Introduction: 0
Academic Disciplines relevant to AI
• Philosophy Logic, methods of reasoning, mind as physical
system, foundations of learning, language,
rationality.
• Mathematics Formal representation and proof, algorithms,
computation, (un)decidability, (in)tractability
• Probability/Statistics modeling uncertainty, learning from data
• Economics utility, decision theory, rational economic agents
• Neuroscience neurons as information processing units.
• Psychology/ how do people behave, perceive, process cognitive
Cognitive Science information, represent knowledge.
• Computer building fast computers
engineering
• Control theory design systems that maximize an objective
function over time Slide Set 1: Introduction: 0
History of AI
• 1943: early beginnings
– McCulloch & Pitts: Boolean circuit model of brain
-
• 1950: Turing
-
-
– Turing's "Computing Machinery and Intelligence“
L
-
•
–
=
1956: birth of AI
Dartmouth meeting: "Artificial Intelligence“ name adopted
- -
• 1950s: initial promise
3
– Early AI programs, including
– Samuel's checkers program
– Newell & Simon's Logic Theorist
•
–
–
–
1955-65: “great enthusiasm”
Newell and Simon: GPS, general problem solver
I
Gelertner: Geometry Theorem Prover
McCarthy: invention of LISP
-
Y
Slide Set 1: Introduction: 0
History of AI
• 1966—73: Reality dawns
– Realization that many AI problems are intractable
– Limitations of existing neural network methods identified
• Neural network research almost disappears
• 1969—85: Adding domain knowledge
– Development of knowledge-based systems
– Success of rule-based expert systems,
• E.g., DENDRAL, MYCIN
• But were brittle and did not scale well in practice
• 1986-- Rise of machine learning
– Neural networks return to popularity
– Major advances in machine learning algorithms and applications
• 1990-- Role of uncertainty
– Bayesian networks as a knowledge representation framework
• 1995-- AI as Science
– Integration of learning, reasoning, knowledge representation
– AI methods used in vision, language, data mining, etc
Slide Set 1: Introduction: 0
Success Stories
• Deep Blue defeated the reigning world chess champion Garry
Kasparov in 1997
• AI program proved a mathematical conjecture (Robbins
conjecture) unsolved for decades
• During the 1991 Gulf War, US forces deployed an AI logistics
planning and scheduling program that involved up to 50,000
Loading…
vehicles, cargo, and people
• NASA's on-board autonomous planning program controlled the
scheduling of operations for a spacecraft
• Proverb solves crossword puzzles better than most humans
=
• Robot driving: DARPA grand challenge 2003-2007
• 2006: face recognition software available in consumer cameras
Slide Set 1: Introduction: 0
Example: DARPA Grand Challenge
5
• Grand Challenge
– Cash prizes ($1 to $2 million) offered to first robots to complete a
long course completely unassisted
– Stimulates research in vision, robotics, planning, machine
learning, reasoning, etc
• 2004 Grand Challenge:
– 150 mile route in Nevada desert
– Furthest any robot went was about 7 miles
– … but hardest terrain was at the beginning of the course
• 2005 Grand Challenge:
– 132 mile race
– Narrow tunnels, winding mountain passes, etc
– Stanford 1st, CMU 2nd, both finished in about 6 hours
• 2007 Urban Grand Challenge
– This November in Victorville, California
Slide Set 1: Introduction: 0
Stanley Robot
Stanford Racing Team [Link]
Next few slides courtesy of Prof.
Sebastian Thrun, Stanford University
Slide Set 1: Introduction: 0
2004: Barstow, CA, to Primm, NV
• 150 mile off-road robot race
across the Mojave desert
• Natural and manmade hazards
• No driver, no remote control
• No dynamic passing
• Fastest vehicle wins the race
(and 2 million dollar prize)
Slide Set 1: Introduction: 0
The Grand Challenge Race
Slide Set 1: Introduction: 0
HAL: from the movie 2001
=
• 2001: A Space Odyssey
– classic science fiction movie from 1969
• HAL
– part of the story centers around an intelligent
computer called HAL
– HAL is the “brains” of an intelligent spaceship
– in the movie, HAL can
• speak easily with the crew
• see and understand the emotions of the crew
• navigate the ship automatically
• diagnose on-board problems
• make life-and-death decisions
• display emotions
• In 1969 this was science fiction: is it still science
fiction?
Slide Set 1: Introduction: 0
Hal and AI
• HAL’s Legacy: 2001’s Computer as Dream and Reality
– MIT Press, 1997, David Stork (ed.)
– discusses
• HAL as an intelligent computer
• are the predictions for HAL realizable with AI today?
• Materials online at
– [Link]
• The website contains
– full text and abstracts of chapters from the book
– links to related material and AI information
– sound and images from the film
Slide Set 1: Introduction: 0
Consider what might be involved in building
a computer like Hal….
• What are the components that might be useful?
– Fast hardware?
– Chess-playing at grandmaster level?
– Speech interaction?
• speech synthesis
• speech recognition
• speech understanding
– Image recognition and understanding ?
– Learning?
– Planning and decision-making?
Slide Set 1: Introduction: 0
Can we build hardware as complex as the brain?
• How complicated is our brain?
– a neuron, or nerve cell, is the basic information processing unit
– estimated to be on the order of 1012 neurons in a human brain
– many more synapses (10 14) connecting these neurons
– cycle time: 10 -3 seconds (1 millisecond)
• How complex can we make computers?
– 108 or more transistors per CPU
– supercomputer: hundreds of CPUs, 1012 bits of RAM
– cycle times: order of 10 - 9 seconds
• Conclusion
– YES: in the near future we can have computers with as many basic
processing elements as our brain, but with
• far fewer interconnections (wires or synapses) than the
brain
• much faster updates than the brain
– but building hardware is very different from making a computer
behave like a brain!
Slide Set 1: Introduction: 0
Can Computers beat Humans at Chess?
• Chess Playing is a classic AI problem
97
– well-defined problem
– very complex: difficult for humans to play well
3000
2800 Deep
Human World Blue
2600 Champion
P 2400 Deep
o Thought
2200
i Ratings
2000
n 1800
t 1600
s
1400
R
1200
a 1966 1971 1976 1981 1986 1991 1997
ti
• Conclusion:
n
– YES: today’s computers can beat even the best human
g
s
Slide Set 1: Introduction: 0
Can Computers Talk?
-D
N
• This is known as “speech synthesis”
– translate text to phonetic form
• e.g., “fictitious” -> fik-tish-es
– use pronunciation rules to map phonemes to actual sound
• e.g., “tish” -> sequence of basic audio sounds
• Difficulties
– sounds made by this “lookup” approach sound unnatural
– sounds are not independent
• e.g., “act” and “action”
• modern systems (e.g., at AT&T) can handle this pretty
well
– a harder problem is emphasis, emotion, etc
• humans understand what they are saying
• machines don’t: so they sound unnatural
• Conclusion:
– NO, for complete sentences
– YES, for individual words
Slide Set 1: Introduction: 0
Can Computers Recognize Speech?
• Speech Recognition:
I
– mapping sounds from a microphone into a list of words
– classic problem in AI, very difficult
• “Lets talk about how to wreck a nice beach”
• (I really said “________________________”)
• Recognizing single words from a small vocabulary
• systems can do this with high accuracy (order of 99%)
• e.g., directory inquiries
– limited vocabulary (area codes, city names)
– computer tries to recognize you first, if
unsuccessful hands you over to a human operator
– saves millions of dollars a year for the phone
companies
-
Slide Set 1: Introduction: 0
Recognizing human speech (ctd.)
• Recognizing normal speech is much more difficult
– speech is continuous: where are the boundaries between words?
• e.g., “John’s car has a flat tire”
– large vocabularies
• can be many thousands of possible words
• we can use context to help figure out what someone
said
– e.g., hypothesize and test
– try telling a waiter in a restaurant:
“I would like some dream and sugar in my
coffee”
– background noise, other speakers, accents, colds, etc
– on normal speech, modern systems are only about 60-70%
accurate
• Conclusion:
– NO, normal speech is too complex to accurately recognize
– YES, for restricted problems (small vocabulary, single speaker)
Slide Set 1: Introduction: 0
Can Computers Understand speech?
• Understanding is different to recognition:
– “Time flies like an arrow”
• assume the computer can recognize all the words
• how many different interpretations are there?
Slide Set 1: Introduction: 0
Can Computers Understand speech?
Y
• Understanding is different to recognition:
– “Time flies like an arrow”
• assume the computer can recognize all the words
• how many different interpretations are there?
– 1. time passes quickly like an arrow?
– 2. command: time the flies the way an arrow times
the flies
– 3. command: only time those flies which are like an
arrow
– 4. “time-flies” are fond of arrows
Slide Set 1: Introduction: 0
Can Computers Understand speech?
• Understanding is different to recognition:
– “Time flies like an arrow”
• assume the computer can recognize all the words
• how many different interpretations are there?
– 1. time passes quickly like an arrow?
– 2. command: time the flies the way an arrow times
the flies
– 3. command: only time those flies which are like an
arrow
– 4. “time-flies” are fond of arrows
• only 1. makes any sense,
– but how could a computer figure this out?
– clearly humans use a lot of implicit commonsense
knowledge in communication
• Conclusion: NO, much of what we say is beyond the
capabilities of a computer to understand at present
Slide Set 1: Introduction: 0
Can Computers Learn and Adapt ?
I
• Learning and Adaptation
– consider a computer learning to drive on the freeway
– we could teach it lots of rules about what to do
– or we could let it drive and steer it back on course when it heads
for the embankment
• systems like this are under development (e.g., Daimler
Benz)
• e.g., RALPH at CMU
– in mid 90’s it drove 98% of the way from
Pittsburgh to San Diego without any human
assistance
·
– machine learning allows computers to learn to do things without
explicit programming
– many successful applications:
• requires some “set-up”: does not mean your PC can
learn to forecast the stock market or become a brain
surgeon
• Conclusion: YES, computers can learn and adapt, when
presented with information in the appropriate way
Slide Set 1: Introduction: 0
Can Computers “see”?
I
•
–
Recognition v. Understanding (like Speech)
Recognition and Understanding of Objects in a scene A
• look around this room
• you can effortlessly recognize objects
• human brain can map 2d visual image to 3d “map”
• Why is visual recognition a hard problem?
p
• Conclusion:
– mostly NO: computers can only “see” certain types of objects
under limited circumstances
– YES for certain constrained problems (e.g., face recognition)
Slide Set 1: Introduction: 0
Can computers plan and make optimal decisions?
• Intelligence
It
– involves solving problems and making decisions and plans
– e.g., you want to take a holiday in Brazil
• you need to decide on dates, flights
• you need to get to the airport, etc
• involves a sequence of decisions, plans, and actions
• What makes planning hard?
– the world is not predictable:
• your flight is canceled or there’s a backup on the 405
Loading…
– there are a potentially huge number of details
• do you consider all flights? all dates?
– no: commonsense constrains your solutions
– AI systems are only successful in constrained planning problems
•
–
-
Conclusion: NO, real-world planning and decision-making is still
beyond the capabilities of modern computers
F
exception: very well-defined, constrained problems
Slide Set 1: Introduction: 0
Summary of State of AI Systems in Practice
:
• Speech synthesis, recognition and understanding
– very useful for limited vocabulary applications
– unconstrained speech understanding is still too hard
• Computer vision
– works for constrained problems (hand-written zip-codes)
– understanding real-world, natural scenes is still too hard
-
• Learning
– adaptive systems are used in many applications: have their limits
• Planning and Reasoning
– only works for constrained problems: e.g., chess
– real-world is too complex for general systems
• Overall: -
– many components of intelligent systems are “doable”
– there are many interesting research problems remaining
Slide Set 1: Introduction: 0
Intelligent Systems in Your Everyday Life
• Post Office
=
↓
– automatic address recognition and sorting of mail
• Banks
– automatic check readers, signature verification systems
– automated loan application classification
• Customer Service
– automatic voice recognition
-
• The Web
– Identifying your age, gender, location, from your Web surfing
– Automated fraud detection
• Digital Cameras
– Automated face detection and focusing
• Computer Games
– Intelligent characters/agents
Slide Set 1: Introduction: 0
AI Applications: Machine Translation
A
↓
• Language problems in international business
– e.g., at a meeting of Japanese, Korean, Vietnamese and Swedish investors,
no common language
– or: you are shipping your software manuals to 127 countries
– solution; hire translators to translate
– would be much cheaper if a machine could do this
• How hard is automated translation
– very difficult! e.g., English to Russian
– “The spirit is willing but the flesh is weak” (English)
– “the vodka is good but the meat is rotten” (Russian)
– not only must the words be translated, but their meaning also!
– is this problem “AI-complete”?
• Nonetheless....
– commercial systems can do a lot of the work very well (e.g.,restricted
vocabularies in software documentation)
– algorithms which combine dictionaries, grammar models, etc.
– Recent progress using “black-box” machine learning techniques
Slide Set 1: Introduction: 0
AI and Web Search
I
#
Slide Set 1: Introduction: 0
What’s involved in Intelligence? (again)
- ~
-
• Perceiving, recognizing, understanding the real world
-
• Reasoning and planning about the external world
• Learning and adaptation
• So what general principles should we use to achieve these
goals?
Slide Set 1: Introduction: 0
Different Types of Artificial Intelligence
s
1. Modeling exactly how humans actually think
2. Modeling exactly how humans actually act
3. Modeling how ideal agents “should think”
-
-
4. Modeling how ideal agents “should act”
• Modern AI focuses on the last definition
– we will also focus on this “engineering” approach
– success is judged by how well the agent performs
Slide Set 1: Introduction: 0
Acting humanly: Turing test
• Turing (1950) "Computing machinery and intelligence“
• "Can machines think?" "Can machines behave intelligently?“
• Operational test for intelligent behavior: the Imitation Game
• Suggests major components required for AI:
- knowledge representation
- reasoning,
- language/image understanding,
- learning
* Question: is it important that an intelligent system act like a human?
Slide Set 1: Introduction: 0
Thinking humanly
• Cognitive Science approach
– Try to get “inside” our minds
– E.g., conduct experiments with people to try to “reverse-engineer”
how we reason, learning, remember, predict
• Problems
– Humans don’t behave rationally
• e.g., insurance
– The reverse engineering is very hard to do
– The brain’s hardware is very different to a computer program
Slide Set 1: Introduction: 0
Thinking rationally
-I
• Represent facts about the world via logic
• Use logical inference as a basis for reasoning about these facts
• Can be a very useful approach to AI
– E.g., theorem-provers
• Limitations
– Does not account for an agent’s uncertainty about the world
• E.g., difficult to couple to vision or speech systems
– Has no way to represent goals, costs, etc (important aspects of
real-world environments)
Slide Set 1: Introduction: 0
Acting rationally
• Decision theory/Economics
– Set of future states of the world
– Set of possible actions an agent can take
– Utility = gain to an agent for each action/state pair
– An agent acts rationally if it selects the action that maximizes its
“utility”
• Or expected utility if there is uncertainty
• Emphasis is on autonomous agents that behave rationally
(make the best predictions, take the best actions)
– on average over time
– within computational limitations (“bounded rationality”)
Slide Set 1: Introduction: 0
Summary of Today’s Lecture
• Artificial Intelligence involves the study of:
– automated recognition and understanding of signals
– reasoning, planning, and decision-making
– learning and adaptation
• AI has made substantial progress in
– recognition and learning
– some planning and reasoning problems
– …but many open research problems
• AI Applications
– improvements in hardware and algorithms => AI applications in
industry, finance, medicine, and science.
• Rational agent view of AI
Slide Set 1: Introduction: 0