Transcript CPS 4801 artificial intelligence

CPS 4801
artificial intelligence
Instructor: Tian (Tina) Tian
About me
•
•
•
•
•
Email: [email protected]
Office: HH-217
Office Hour: Mon, Wed 2:30 – 4:30PM
Tue, Thu 3:15 – 5:00 PM
Website: TBA
About the Course
• Tuesdays, Thursdays 2:00 – 3:15 PM
• Textbook:
– Artificial Intelligence: A Guild to Intelligent Systems, 2nd
Edition, by Michael Negnevitsky, Addison Wesley, 2005.
ISBN: 978-0-12-373602-4
– Artificial Intelligence: A Modern Approach, 3rd Edition, by
Stuart Russell and Peter Norvig, Prentice Hall, 2010. ISBN:
0136042597
• Grading:
– Midterm Exam
30%
– Final Exam
35%
– Homework and Term Paper/Project
35%
What is Artificial Intelligence?
• Essential English Dictionary, Collins, London, 1990:
– Someone’s intelligence is their ability to understand
and learn things.
– Intelligence is the ability to think and understand
instead of doing things by instinct or automatically.
– Thinking is the activity of using your brain to
consider a problem or to create an idea.
• We can define intelligence as ‘the ability to learn
and understand, to solve problems and to make
decisions’.
The Turing Test
• Alan Turing, British mathematician (1912-1954)
– “Computing machinery and intelligence” paper in 1950
– Can machines think?
• The Turing Test (a.k.a. Turing imitation game):
A computer passes the Turing test if human
interrogators cannot distinguish the
machine from a human based on answers to
• Predicted that by 2000,
machine might have a 30% chance
theiraquestions
–
of fooling a lay person for 5 minutes
The Turing Test
• Alan Turing suggested an imitation game.
• (Second phase) A person C questions two other
“agents” A and B over a computer terminal.
• The person C cannot see or hear A and B.
• Both A and B claim they are humans.
• But one of them is lying.
• If C cannot detect that A is a computer, that
means that A is for all practical purposes
“intelligent.”
Loebner Prize
• The Loebner Prize is an annual competition
for AI programs.
• http://www.loebner.net/Prizef/loebnerprize.html
• Crown Industries of East Orange, NJ
• $100,000 and a Gold Medal for the first
computer that passes the Turing Test.
• Each year $2000 and a bronze medal is
awarded to the most human-like computer.
The Turing Test
•
•
•
•
•
Natural language processing
Knowledge representation
Automatic reasoning
Machine learning
Total Turing Test: computer vision and
robotics
History of AI
• Warren McCulloch & Walter Pitts (1943):
– Research on the human central nervous system
led to a model of neurons of the brain
– Birth of Artificial Neural Networks (ANN)
• Binary model
• Non-linear model
• John von Neumann
– ENIAC, EDVAC, etc.
History of AI
• Claude Shannon, MIT, Bell Labs (1950):
– Computers playing chess
– Chess game involved about 10120 possible moves!
– Even examining one move per microsecond would
require 3 x 10106 years to make its first move
• Need to incorporate intelligence via heuristics
History of AI
• John McCarthy, Dartmouth, MIT (1950s):
– Defined LISP
• Only two years after FORTRAN
– LISP is based on formal logic
– “Programs with Common Sense” paper (1958)
• Marvin Minsky, Princeton, MIT:
– Anti-logical approach to knowledge
representation and reasoning called frames (1975)
History of AI
• Great expectations during 1950s and 1960s
– But very limited success
– Researchers focused too much on all-purpose
intelligent machines with goals to learn and reason
with human-scale knowledge (and beyond)
• Refocus on specific problem domains (1970s)
– Domain-specific expert systems with facts, rules, etc.
– Analyze chemicals, medical diagnoses, etc.
History of AI
• Evolutionary computation (1970s-today):
– Natural intelligence is a product of evolution
– Can we solve problems by simulating
biological evolution?
– Survival of the fittest
– Genetic programming
– Evolutionary computing
History of AI
• Rebirth of neural networks (1980s-today):
– Adaptive resonance theory (Grossberg, 1980)
incorporated self-organization principles
– Hopfield networks (Hopfield, 1982)
introduced neural networks with
feedback loops
– Back-propagation learning algorithm
(Bryson and Ho, 1969) for training
multilayer perceptrons
History of AI
• Knowledge engineering (1980s-today):
– Fuzzy set theory (Zadeh, 1965) associates words
with degrees of truth or value
– Rule-based knowledge systems
– Combine information from multiple experts
– Semantic Web
• Numerous hybrid approaches exist
Abridged History of AI
•
•
•
•
•
•
•
•
•
•
•
•
1943
McCulloch & Pitts: Boolean circuit model of brain
1950
Turing's "Computing Machinery and Intelligence"
1956 Dartmouth meeting: "Artificial Intelligence" adopted
1952—69Look, Ma, no hands!
1950s
Early AI programs, including Samuel's checkers
program, Newell & Simon's Logic Theorist,
Gelernter's Geometry Engine
1965 Robinson's complete algorithm for logical reasoning
1966—73AI discovers computational complexity
Neural network research almost disappears
1969—79Early development of knowledge-based systems
1980-- AI becomes an industry
1986-- Neural networks return to popularity
1987-- AI becomes a science
1995-- The emergence of intelligent agents
State of the Art
• Game playing: IBM’s Deep Blue defeated the reigning world
chess champion Garry Kasparov in 1997.
• Speech recognition: A traveler calling United Airlines to book
a flight can have the entire conversation guided by an
automatic speech recognition system.
• Robotic vehicles: No hands across America (driving
autonomously 98% of the time from Pittsburgh to San Diego)
• Logistics planning: 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.
• Autonomous planning and scheduling: NASA's on-board
autonomous planning program controlled the scheduling of
operations for a spacecraft.
• Robotics: The iRobot Corporation has sold over two million
Roomba robotic vacuum cleaners for home use.
Less Successful Areas of AI
• Sadly the Loebner Gold Medal still has not
been awarded.
• Natural Language Processing is still mostly an
unresolved problem.
Can this be solved by computers?
• Playing a decent game of table tennis (PingPong).
Can this be solved by computers?
• Playing a decent game of table tennis (PingPong).
• A reasonable level of proficiency was achieved by
Andersson’s robot (Andersson,1988).
Can this be solved by computers?
• Driving in the center of Cairo, Egypt.
Can this be solved by computers?
• Driving in the center of Cairo, Egypt.
• No. Although there has been a lot of progress in
automated driving, all such systems currently rely on
certain relatively constant clues: that the road has
shoulders and a center line, that the car ahead will travel
a predictable course, that cars will keep to their side of
the road, and so on. Some lane changes and turns can be
made on clearly marked roads in light to moderate
traffic. Driving in downtown Cairo is too unpredictable
for any of these to work.
Can this be solved by computers?
• Buying a week’s worth of groceries at the
market.
Can this be solved by computers?
• Buying a week’s worth of groceries at the
market.
• No. No robot can currently put together the tasks of moving in
a crowded environment, using vision to identify a wide variety
of objects, and grasping the objects (including squishable
vegetables) without damaging them. The component pieces
are nearly able to handle the individual tasks, but it would
take a major integration effort to put it all together.
Can this be solved by computers?
• Buying a week’s worth of groceries on the
Web.
Can this be solved by computers?
• Buying a week’s worth of groceries on the
Web.
• Yes. Software robots are capable of handling such tasks,
particularly if the design of the web grocery shopping site
does not change radically over time.
Can this be solved by computers?
• Writing an intentionally funny story.
Can this be solved by computers?
• Writing an intentionally funny story.
• No. While some computer-generated prose and poetry is
hysterically funny, this is invariably unintentional, except in
the case of programs that echo back prose that they have
memorized.
Unintentionally Funny Stories
• One day Joe Bear was hungry. He asked his
friend Irving Bird where some honey was.
Irving told him there was a beehive in the oak
tree. Joe threatened to hit Irving if he didn't
tell him where some honey was. The End.
• Henry Squirrel was thirsty. He walked over to
the river bank where his good friend Bill Bird
was sitting. Henry slipped and fell in the river.
Gravity drowned. The End.
Can this be solved by computers?
• Giving competent legal advice in a specialized
area of law.
Can this be solved by computers?
• Giving competent legal advice in a
specialized area of law.
• Yes, in some cases. AI has a long history of research into
applications of automated legal reasoning. One example
is the Prolog-based expert systems used in the UK to
guide members of the public in dealing with the
intricacies of the social security and nationality laws.
However, extension into more complex areas such as
contract law awaits a satisfactory encoding of the vast
web of common-sense knowledge pertaining to
commercial transactions and agreement and business
practices.
Can this be solved by computers?
• Translating spoken English into spoken
Swedish in real time.
Can this be solved by computers?
• Translating spoken English into spoken
Swedish in real time.
• Yes. In a limited way, this is already being done.
Can this be solved by computers?
• Performing a complex surgical operation.
Can this be solved by computers?
• Performing a complex surgical operation.
• Yes. Robots are increasingly being used for surgery, although
always under the command of a doctor. Robotic skills
demonstrated at superhuman levels include drilling holes in
bone to insert artificial joints, suturing, and knot-tying. They
are not yet capable of planning and carrying out a complex
operation autonomously from start to finish.
Reading
• Chapter 1
• Computing Machinery and Intelligence by A.
M. Turing, 1950