Transcript Machine learning

Artificial
Intelligence
AI
 You
are a caveman (or woman)
 I travel back in time and bring you
a LapTop and show you some of
the things it is capable of doing.
 Question : Would you, as a
caveman, consider the computer
to be intelligent?
Intelligence

Are the things shown below, Intelligent?
3
Searching a path …
Different mice might follow different paths based to their intelligence
In other words: The problem can be solved in many ways
Ability to solve problems demonstrates Intelligence
4
Big questions





Can machines think?
If so, how?
If not, why not?
What does this say about humans?
What does this say about the mind?
Next number in the
sequence …

Consider the following sequence …
1,3,7,13,21,__
– What is the next number ?
• Key: Adding the next EVEN number …
1+2 = 3; 3+4 = 7; 7+6 = 13; 13+8 =21; 21+10 = 31
1,3,7,13,21,31
Ability to solve problems demonstrates
6
Intelligence
AI Long Term Goals
Produce intelligent behaviour in machines

Why use computers at all?
– They can do things better than us
– Big calculations quickly and reliably

We do intelligent things
– So get computers to do intelligent things
So, Let’s Summarize…









Ability to solve problems
Ability to plan and schedule
Ability to memorize and process information
Ability to answer fuzzy questions
Ability to learn
Ability to recognize
Ability to understand
Ability to perceive
And many more …
Food for thought: Can only humans beings and animals possess these
qualities?
8
What if?










A machine searches through a mesh and finds a path?
A machine solves problems like the next number in
the sequence?
A machine develops plans?
A machine diagnoses and prescribes?
A machine answers ambiguous questions?
A machine recognizes fingerprints?
A machine understands?
A machine perceives?
A machine does MANY MORE SUCH THINGS …
A machine behaves as HUMANS do? HUMANOID!!!
Some Advantages of Artificial
Intelligence
– more powerful and more useful computers
– new and improved interfaces
– solving new problems
– better handling of information
– relieves information overload
– conversion of information into knowledge
The Disadvantages
– increased costs
– difficulty with software development - slow
and expensive
– few experienced programmers
– few practical products have reached the
market as yet.
Some AI Systems that are
Better Than Humans

Backgammon
– TD gammon was the first program to beat
the worlds best players (Gerald Tesauro)
 http://researchweb.watson.ibm.com/massive/t
dl.html
Why AI?



Engineering: To get machines to do a wider
variety of useful things
– e.g., understand spoken natural language,
recognize individual people in visual scenes,
find the best travel plan for your vacation, etc.
Cognitive Science: As a way to understand
how natural minds and mental phenomena work
– e.g., visual perception, memory, learning,
language, etc.
Philosophy: As a way to explore some basic
and interesting (and important) philosophical
questions
– e.g., the mind body problem, what is
consciousness, etc.
What is Artificial Intelligence ?

making computers that think?

the automation of activities we associate
with human thinking, like decision making,
learning ... ?

the art of creating machines that perform
functions that require intelligence when
performed by people ?
What’s easy and what’s hard for AI?



It’s been easier to mechanize many of the high-level tasks
we usually associate with “intelligence” in people
– e.g., symbolic integration, proving theorems, playing
chess, medical diagnosis
It’s been very hard to mechanize tasks that lots of animals
can do
– walking around without running into things
– catching prey and avoiding predators
– interpreting complex sensory information (e.g., visual,
aural, …)
– modeling the internal states of other animals from their
behavior
– working as a team (e.g., with pack animals)
Is there a fundamental difference between the two
categories?
What can AI systems do?
Here are some example applications
 Computer vision: face recognition from a large set
 Robotics: autonomous (mostly) automobile
 Natural language processing: simple machine
translation
 Expert systems: medical diagnosis in a narrow
domain
 Spoken language systems: ~1000 word continuous
speech
 Planning and scheduling: Hubble Telescope
experiments
 Learning: text categorization into ~1000 topics
 User modeling: Bayesian reasoning in Windows help
(the infamous paper clip…)
 Games: Grand Master level in chess (world
champion), checkers, etc.
IBM’s Deep Blue versus Kasparov



On May 11, 1997, Deep
Blue was the first computer
program to beat reigning
chess champion Kasparov
in a 6 game match (2 : 1
wins, with 3 draws)
Massively parallel
computation (259th most
powerful supercomputer in
1997)
Evaluation function criteria
learned by analyzing
thousands of master
games
Searched the game tree •
from 6-12 ply usually, up to
40 ply in some situations.
One ply corresponds to –
one turn of play.
Robotics
Shakey (1966-1972)
Kismet (late 90s, 2000s)
Cog (90s)
Robocup Soccer
(2000s)
Boss (2007)
Robotics
•
•
Mars rovers
Autonomous vehicles
– DARPA Grand Challenge
– Google self-driving cars
•
•
Autonomous helicopters
Robot soccer
– RoboCup
•
Personal robotics
– Humanoid robots
How is it Currently
Done?
Crusher and, more recently, PerceptTOR
Vision
•
•
•
•
OCR, handwriting recognition
Face detection/recognition: many
consumer cameras, Apple iPhoto
Visual search: Google Goggles
Vehicle safety systems: Mobileye
DARPA grand challenge
Stanley Robot
Stanford Racing Team
www.stanfordracing.org
Next few slides courtesy of Prof.
Sebastian Thrun, Stanford University
What About the DARPA
Grand Challenge?


Autonomous Navigation in the Desert over a 132
mile course.
5 Teams succeeded!
– http://www.darpa.mil/grandchallenge05/gcorg/index.html

This was a monumental achievement in
autonomous robotics

HOWEVER: This was not an
unstructured environment!
– GPS waypoints were carefully chosen,
sometimes less than a meter apart.
Stanley’s Technology
Path
Planning
Laser Terrain Mapping
Learning from Human Drivers
Adaptive Vision
Sebastian
Stanley
Images and movies taken from Sebastian Thrun’s multimedia website.
SENSOR INTERFACE
RDDF database
PERCEPTION
PLANNING&CONTROL
USER INTERFACE
Top level control
corridor
Touch screen UI
pause/disable command
Wireless E-Stop
Laser 1 interface
RDDF corridor (smoothed and original)
driving mode
Laser 2 interface
Laser 3 interface
road center
Road finder
Laser 4 interface
laser map
Laser 5 interface
Laser mapper
Camera interface
Vision mapper
Radar interface
Radar mapper
Path planner
trajectory
map
VEHICLE
INTERFACE
vision map
Steering control
obstacle list
Touareg interface
vehicle state (pose, velocity)
GPS position
UKF Pose estimation
GPS compass
vehicle state (pose, velocity)
IMU interface
vehicle
state
Throttle/brake control
Power server interface
velocity limit
Surface assessment
Wheel velocity
Brake/steering
heart beats
emergency stop
Linux processes start/stop
health status
Process controller
Health monitor
power on/off
data
GLOBAL
SERVICES
Data logger
Communication requests
File system
Communication channels
Inter-process communication (IPC) server
clocks
Time server
Google self-driving cars
Europa Hydrobot
 http://www.resa.net/nasa/images/gem/HYDR
OBOT.JPG
AI Applications
Games:
AI Applications

Games:
AI Applications

Robotic toys:
AI Applications

Transportation:
– Pedestrian detection:
AI Applications

Medicine:
– Image guided surgery
AI Applications

Autonomous Planning & Scheduling:
– Telescope scheduling
Natural Language
•
Speech technologies
• Automatic speech recognition
•
Google voice search
• Text-to-speech synthesis
• Dialog systems
•
Machine translation
Why is AI hard?
Two usual ingredients (for standard AI)
 Representation
– need to represent our knowledge in
computer readable form
 Reasoning
– need to be able to manipulate knowledge
and derive new knowledge
– many possible ways to do this, but most
give rubbish
– finding the successful way usually
involves search
Both of these are hard.
The Travelling Salesman
Problem (TSP)




A salesperson has to visit a number of cities
(S)He can start at any city and must finish at that
same city
The salesperson must visit each city only once
For example, with 5 cities a possible tour is:
A
C
D
B
E
Combinatorial Explosion
A 50 City TSP has 1.52 * 1064 possible solutions
Age of the universe is 15 billion (1.5 * 1010) years
There are 30 million seconds in a year
Age of universe is about 45 * 1016 seconds
A 10GHz computer might do 109 tours per second
Running since start of universe, it would still only have
done 1026 tours
Not even close to evaluating all tours!
Need to be clever about how to solve such search
problems!
AI Connections

Philosophy
logic, methods of reasoning, mind vs. matter,
foundations of learning and knowledge

Mathematics
logic, probability, optimization

Economics
utility, decision theory

Neuroscience
biological basis of intelligence

Cognitive science computational models of human intelligence

Linguistics
rules of language, language acquisition

Machine learning
design of systems that use experience to
improve performance

Control theory
design of dynamical systems that use a
controller to achieve desired behavior

Computer engineering, mechanical engineering, robotics, …
AI Generic Techniques

Automated Reasoning
– Resolution, proof planning, Davis-Putnam,
CSPs

Machine Learning
– Neural nets, ILP, decision tree learning

Natural language processing
– N-grams, parsing, grammar learning

Robotics
– Planning, edge detection, cell decomposition

Evolutionary approaches
– Crossover, mutation, selection
History of AI
Harder than originally thought
•
1966: Weizenbaum’s Eliza
•
•
•
“ … mother …” → “Tell me more about your family”
“I wanted to adopt a puppy, but it’s too young to be
separated from its mother.”
1950s: during the Cold War, automatic RussianEnglish translation attempted
• 1954: Georgetown-IBM experiment
•
•
Completely automatic translation of more than sixty Russian
sentences into English
Only six grammar rules, 250 vocabulary words, restricted to
organic chemistry
• 1966: ALPAC (Automatic Language Processing Advisory
Committee) report: machine translation has failed to live up to
its promise
•
“The spirit is willing but the flesh is weak.” → “The vodka is
strong but the meat is rotten.”
Blocks world (1960s –
1970s)
Roberts, 1963
???
A dose of reality

1940s
1950










McCulloch & Pitts neurons; Hebb’s learning rule
Turing’s “Computing Machinery and Intelligence”
Shannon’s computer chess
Georgetown-IBM machine translation
1954
experiment
1956
Dartmouth meeting: “Artificial Intelligence”
adopted
1957
Rosenblatt’s perceptrons
1950s-1960s“Look, Ma, no hands!” period:
Samuel’s checkers program, Newell &
Simon’s
Logic Theorist, Gelernter’s Geometry
Engine
1966-73
Setbacks in machine translation
Neural network research almost disappears
Intractability hits home
The rest of the story











1974-1980 The first “AI winter”
1970s
Knowledge-based approaches
1980-88
Expert systems boom
1988-93
Expert system bust; the second “AI winter”
1986
Neural networks return to popularity
1988
Pearl’s Probabilistic Reasoning in Intelligent
Systems
1990
Backlash against symbolic systems; Brooks’
“nouvelle AI”
1995-present
Increasing specialization of the field
Agent-based systems
Machine learning everywhere
Tackling general intelligence again?
Course Overview
 AI
fundamentals
– Terminology
– Methodologies
 Logic
Representation
 Search
 Game playing
 Decision-making under uncertainty
 Machine learning
Some Famous Imitation
Games

1960s ELIZA
– Rogerian psychotherapist

1970s SHRDLU
– Blocks world reasoner

1980s NICOLAI
– unrestricted discourse

1990s Loebner prize
– win $100,000 if you pass the test
48
The problem with ELIZA
 Eliza
used simple pattern
matching
– “Well, my friend made me come
here”
– “Your friend made you come here?”
 Eliza
written by Joseph
Weizenbaum
49
Who does AI?



Academic researchers (perhaps the most Ph.D.-generating
area of computer science in recent years)
– Some of the top AI schools: CMU, Stanford, Berkeley,
MIT, UIUC, UMd, U Alberta, UT Austin, ... (and, of course,
Swarthmore!)
Government and private research labs
– NASA, NRL, NIST, IBM, AT&T, SRI, ISI, MERL, ...
Lots of companies!
– Google, Microsoft, Honeywell, Teknowledge, SAIC,
MITRE, Fujitsu, Global InfoTek, BodyMedia, ...
The course topics

introduction to AI

AI application areas

Knowledge representation

Search space

Machine learning
Course overview
Introduction and Agents (chapters 1,2)
 Search (chapters 3,4,5,6)
 Logic (chapters 7,8,9)
 Planning (chapters 11,12)
 Uncertainty (chapters 13,14)
 Learning (chapters 18,20)
 Natural Language Processing (chapter
22,23)

AI definition
AI is a branch of computer science and it
concerned with intelligent behavior.
What is AI?
There are no crisp definitions
Q. What is artificial intelligence?
A. It is the science and engineering of
making intelligent machines, especially
intelligent computer programs.
Q. what is intelligence?
A. Intelligence is the computational part
of the ability to achieve goals in the
world. Varying kinds and degrees of
intelligence occur in people, many
animals and some machines.

What is Intelligence?

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
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
vehicles, cargo, and people
Can Computers Talk?

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

Difficulties
– sounds made by this “lookup” approach sound unnatural
– sounds are not independent
– a harder problem is emphasis, emotion, etc


humans understand what they are saying
Conclusion:
– NO, for complete sentences
– YES, for individual words
Can Computers
Recognize Speech?

Speech Recognition:
– 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
of 99%)
can do this with high accuracy (order
Alan M Turing, Hero

Helped to found theoretical CS
– 1936, before digital computers existed

Helped to found practical CS
– wartime work decoding Enigma machines
– ACE Report, 1946

Helped to found practical AI
– first (simulated) chess program

Helped to found theoretical AI …
62
Can Computers “see”?

Recognition v. Understanding (like
Speech)
– Recognition and Understanding of Objects in
a scene
 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?
What did Turing think?

Turing (in 1950) believed that by 2000
– computers available with 128Mbytes
storage
– programmed so well that interrogators
have only a 70% chance after 5 minutes
of being right

“By 2000 the use of words and general
educated opinion will have altered so
much that one will be able to speak of
machines thinking without expecting to
64
be contradicted”
Turing Test





Three rooms contain a person, a
computer, and an interrogator.
The interrogator can communicate with
the other two by teleprinter.
The interrogator tries to determine which
is the person and which is the machine.
The machine tries to fool the interrogator
into believing that it is the person.
If the machine succeeds, then we
conclude that the machine can think.
The Imitation Game

Interrogator in one
room
– computer in another
– person in a third room


From typed responses
only (text-only), can
interrogator distinguish
between person and
computer?
If the interrogator often
guesses wrong, say
the machine is
intelligent.
66
Can Machines Think?

Turing starts by defining machine &
think
– Will not use everyday meaning of the
words
 otherwise
we could answer by Gallup poll
– Instead, use a different question
 closely

related, but unambiguous
“I believe the original question to be
too meaningless to deserve
discussion”
67
A sample game

Turing suggests some Q & A’s:

Q: Please write me a sonnet on the subject of the Forth Bridge
A: Count me out on this one, I never could write poetry
Q: Add 34957 to 70764.


– (pause about 30 seconds)




A: 105621
Q: Do you play chess?
A: Yes
Q: I have K at my K1, and no other pieces. You have only K
at K6 and R at R1. It is your move. What do you play?
– (pause about 15s)

A: R-R8 mate
68
Some Famous Imitation Games

1960s ELIZA
– Rogerian psychotherapist

1970s SHRDLU
– Blocks world reasoner

1980s NICOLAI
– unrestricted discourse

1990s Loebner prize
– win $100,000 if you pass the test
69
“Chinese room”
argument [Searle
1980]
image from http://www.unc.edu/~prinz/pictures/c-room.gif



Person who knows English but not Chinese sits in room
Receives notes in Chinese
Has systematic English rule book for how to write new
Chinese characters based on input Chinese characters,
returns his notes
– Person=CPU, rule book=AI program, really also need lots of paper
(storage)

– Has no understanding of what they mean
– But from the outside, the room gives perfectly reasonable
answers in Chinese!
Searle’s argument: the room has no intelligence in it!
Some AI videos

Note: there is a lot of AI that is very valuable!

http://www.youtube.com/watch?v=ICgL1OWsn58&feature=related
http://www.youtube.com/watch?v=HacG_FWWPOw&feature=related
http://videolectures.net/aaai07_littman_ai/
http://www.ai.sri.com/~nysmith/videos/SRI_AR-PA_AAAI08.avi
http://www.youtube.com/watch?v=ScXX2bndGJc



