Transcript Logic - Department of Computing Science and Mathematics

Introduction To
Artificial Intelligence
John Woodward
[email protected]
http://www.cs.nott.ac.uk/~jrw/
Physics and AI
• In physics we have the foundations
(Newton’s three laws) and some
revolutions (quantum mechanics and
Einstein's special and general theories of
relativity). Over about 300 years.
• Mathematics has an even longer history.
• AI is relatively new (started around 1940’s)
so we do not have any icons/heros….yet.
• AI is relevant to any intellectual discipline.
• Do we need a new physics?
Definition of Artificial Intelligence
• In math – definitions are centrally important.
• Can we define intelligence? (thought
processes/reasoning). Emotional? Social?
• Make a list of things computers cannot do.
• Intelligence is knowing where to break rules 
Explicit vs. Implicit Programming
• If we have a problem e.g. sorting a list of
numbers, we can explicitly write an efficient
algorithm to solve the problem (i.e. quick
sort). Or finding max in an array
• There are problems which take too long to
solve so we must accept approximate
methods.(e.g. travelling salesman problem).
• There are problems we don’t even know how
to solve e.g. speech recognition and vision.
• In these cases we can write a program which
writes a program or other AI methods.
What is intelligence?
• What are the
consequences of the
actions in each of
these pictures?
• The second is even a
common expression in
English “to paint
yourself into a corner”.
• Early robots actually
unplugged themselves,
or got suck like this.
Turing Test
Turing (1950) “Computing machinery
and intelligence":
Can machines think? Can machines
behave intelligently?
Predicted that by 2000, a machine
might have a 30% chance of fooling
a lay person for 5 minutes
Suggested major components of AI:
knowledge, reasoning, language
understanding, learning
Problems: Turing test is not
reproducible, constructive, or
amenable to mathematical analysis
AI is not trying to copy humans
• “artificial flight” was successful because the
Wright brothers stopped mimicking birds.
• We don’t want to copy pigeons.
• Where else is the idea of a “gliding wing” and
a propeller used in nature?
Example of Artificial Flight
• First flight was hot
air balloon - seen
in nature?
• Flying squirrel
glide.
• Sycamore seeds do
use the idea of
propeller.
• Flagella in bacteria.
Cognitive Science
How can we approach how humans think.
1. introspection (catch our own thoughts
e.g. remembering someone's face, do we
think in “words” – the rotation test)
2. psychological experiments (experiment
on peoples behavior). What people say
they do, and what they do are two
different things e.g. recognizing
caricatures.
3. brain imaging. Scans of brain show which
parts use more oxygen.
Laws of Thought
“Socrates is a man; all men are mortal; therefore
Socrates is mortal.” LOGIC
In 1965 computer programs existed that could in
principle solve any solvable problem described
in logical notation (however if no solution
exists, the program would not terminate).
How to we formally state real-world problems.
Some problems take too long to solve exactly.
Foundations of AI
•
•
•
•
•
•
•
Philosophy
Mathematics
Economics
Neuroscience
Psychology
Control Theory
Linguistics
Philosophy
• How can formal rules be used to draw
valid conclusions?
• How can the mind arise from physical
matter.
• What is knowledge, how does it
originate, and lead to action
• Consciousness and freewill (todo)
Mathematics
• Logic. What are the formal rules? Gödel's
incompleteness theorem.
• Computation: What can and cannot be
computed? Church’s thesis and halting
problem, NP completeness.
• Probability: How do we reason with uncertain
information?
Economics
• How do we make decisions to maximize payoff
(utility, money, happiness).
• How do we do this when others cooperate or
do not cooperate (criminals).
• What about if the reward is not immediate,
but maybe delayed far into the future.
• Decision theory/game theory/operations
research.
Neuroscience
• How does the brain process information?
• What can brain damaged patients tell us
about the working of the human brain (see
books by Oliver Sacks)?
• Lesions on rats brains and mazes.
• How to neurons give rise to consciousness?
Cognitive Psychology
• How to humans act and think?
• 3 steps of a knowledge-based agent
1. stimulus is translated into an internal
representation.
2. The representation is manipulated by
cognitive processes.
3. The internal representations are
converted into an action.
Think about a game of chess.
AGENT
ENVIROMENT
Control Theory
• How can object operate autonomously?
• For example
A water clock regulates is own flow rate
Steam engine governor
A guided missile, or a space probe, or a robot
that can operate independently of a human
controller.
Linguistics
• How do language and thought relate?
• How can a child understand sentence he or she
had never hear before? Dog understands "SIT”.
• Language is central to humans (which are by far
the most intelligent species). No other animal
has a full language like humans.
• Understanding language require syntax
(grammar) but also context
• (e.g. you are pulling my leg – translate).
• Do we think using words (e.g. English).
History of AI
McCulloch and Pitts (1943) on/off
perceptron.
Hebb (1949) Hebbian learning rule.
Turing (1950) “Computing Machinery
and Intelligence”
Newell and Simon (1976) physical
symbol system hypothesis
Samuel (1952) checkers player; the
program leaned to play better than
its creator
Perceptron 1
• A set of inputs are presented.
• The inputs represent a problem.
• A node sums up the weighted inputs and
calculated an output.
• A action is performed according to the value on
the output (e.g. a robot controller <-1 turn left,
>1 turn right, else move straight).
• The Hebb rule tells us how to learn the weights
Perceptron 2
• Convergence theorem (1962) says
that the learning algorithm can
adjust its connection weights of a
perceptron to match any input,
provided such a match exists.
• Minsky and Papert (1969) a two
input perceptron cannot be
trained to recognize when its two
inputs are different (linearly
separable or the XOR problem)
Computing Machinery and Intelligence
• Alan Turing proposed
– Machine learning
– Genetic algorithms
– Reinforcement learning
• He proposed CHILD PROGRAMinstead of producing a program
with adult abilities, produce a
program with ability to learn like a
child.
Goal = -100 points
Save = +10 points
Physical Symbol System Hypothesis
• “A physical symbol system
has the necessary and
sufficient means for a
general intelligent action”.
• Symbols represent objects
in the real world
(e.g. chess pieces).
• We have “data” which is
manipulated (chess rules).
Samuel (1952) checkers player
•
•
•
•
Computer “do what they are told”.
I can play a game (e.g. OXO)
However I make mistakes
I can write a program which avoids this
mistakes.
• If I add learning – it can play better than me!
• What were the inputs/outputs – how can we
use a perceptron to learn OXO?
Machine Translation 1
• During the cold war, America used machines
to translate Russian scientific text.
• “the spirit is willing but the flesh is weak”
• Was translate as
• “the vodka is good but the meat is rotten”
• A similar example; how do you pronounce
ghoti
• GOOGLE TRANSLATE…
Machine Translation 2
• Ghoti is a constructed word used to illustrate
irregularities in English spelling. It is a
respelling of the word fish, i.e., it is supposed
to be pronounced /fɪʃ/. Its components
include:
• gh, pronounced /f/ as in tough /tʌf/;
• o, pronounced /ɪ/ as in women /ˈwɪmɪn/; and
͡
• ti, pronounced /ʃ/ as in nation /ˈneɪʃən/.
Expert Systems 1
• MYCIN is a medical expert system.
• Rules were obtained by interviewing experts.
• With about 450 rules, it could perform as well
as some experts and considerable better than
junior doctors.
• Rules also incorporated “uncertainly”
reflecting the confidence in the diagnosis (like
a real doctor).
Expert Systems 2
• You are an expert in the following – but you
try explaining to someone how you do it
– Riding a bike
– Walking
– Driving a car
– Touch typing
– Recognizing handwriting.
AI and Industry
•
•
•
•
•
•
Digital Equipment Corporation 1986
Expert system
Saved estimated $40 million US$
Japan started 5th generation project.
Many projects never met their goals 
But many companies are using these techniques
today – probably most obvious is the computer
game industry (worth more than the movie
industry)
State of the Art
•
•
•
•
•
•
Robotic Vehicles
Speech recognition
Game playing
Spam filtering
Robotics
Machine Translation
Robotic Vehicles
• A driverless robotic volkeswagen car
• Fitted with cameras, radar, laser range finders
and onboard software.
• Control commands for steering, breaking and
acceleration.
• 22mph, 132 mile course. DARPA Grand Challenge.
• Some of the early cars drove straight into trees –
why.
• Why was it held in the desert?
Speech recognition
• In use in your mobile phone (voice dialing)
• When you call the train company in the UK –
you have a simple conversation
– Where to? (Nottingham)
– Where from? (London Heathrow)
– When would you like to travel? (4:40pm)
– What is your credit card number.
But how many different ways can you say “Hello” –
the tone and intonation of your voice carry a lot of
information.
Game playing
• IBM’s Deep Blue defeated the world
champion Garry Kasparov.
• “a new kind of intelligence”
• IBM’s stock increased by $18 billion USD.
• By studying this, chess players could
draw!!!
• Recently the computer is much better.
• But what about “GO”, or other games?
Spam filtering
• Many emails are spam (credit
card, sexy girls waiting to meet
you….)
• We can scan for keywords e.g.
viagra, but spammers are clever
and slightly misspell the word
viiagra.
• Just looking at keywords is not
enough (you might ask IT
services to reset your password).
• Why is spam called spam?
Logistic Planning
• During the 1991 Persian Gulf
crisis, US armed forces moved
50,000 people, needing origins,
routes and destinations.
• AI planning techniques
generated a plan in hours,
which would normally take
weeks.
• Timetable scheduling at UNNC.
• Nurse Roistering at National
Heath Service in UK.
Robotics
• The iRobot
Corporation sold 2
million Roomba
robotic vacuum
cleaners for home
use.
• The can navigate in
an intelligent way.
Machine Translation
• Arabic to English
• The program builds a
statistical model from
two trillion examples.
• None of the
programmers speak
Arabic, but do
understand statistics
and machine learning.
Are computers = electric brains?
•
•
•
•
•
The Chinese call a computer
电脑 “electric brain”
Maybe a better translation
计算机 “Meter Operators Machine ”
Is there and algorithm which is functionally
equivalent to the human brain?
Testimony
• Some of what we learn is not through
experience, but through what people tell us.
• “the great wall of china can be seen from
outer space”.
• If you thought the capital of Canada was
Toronto, but I told you it was Ottawa, you
might believe me.
• What if I told you the capital was Paris?
• You are learning by testimony now.