Transcript CS440 Introduction to Artificial Intelligence

CS440
Introduction to Artificial Intelligence
Fall 2003
Today’s topics
• Course administration.
• What is AI?
• AI and …
– Cognitive science, philosophy, psychology,
economics, computer science, control theory, …
• History of AI.
• Applications of AI.
• Reading:
– This week: AIMA, Ch. 1
– Next week: AIMA, Ch. 2 & 3
Course administration
• Instructor
Vladimir Pavlovic
Office: 312 CoRE
Email: [email protected]
Web: www.cs.rutgers.edu/~vladimir
Phone: 732-445-2654
Office hours: Mon, 3:00-4:00
• TA
Zhi Wei
Office: 416 Hill
Email: [email protected]
Phone: 732-445-6996
Office hours: Thu, 2:00-4:00 PM
• Web site
http://www.cs.rutgers.edu/~vladimir/class/cs440
• Mailing list
[email protected]
Course administration (cont’d)
• Lectures:
• Discussion:
• Classroom:
Mon & Wed, 4:30 – 5:50
Wed, 6:35 – 7:30
Arc-105
• Textbook:
Russell & Norvig, "Artificial Intelligence: A Modern Approach", 2nd
Edition, Prentice Hall, 2003. Also referred to as AIMA
• Prerequisites:
CS314 (Principles of Programming Languages). You also need a solid
knowledge of calculus. Some knowledge of probability and linear
algebra will be beneficial.
Course administration (cont’d)
• Grading
Homework
Midterm
Final
30%
30%
40%
• Homework assignments
–
–
–
–
Weekly, will include programming problems (mini projects).
Programming in Java / Matlab (Lush? Lisp?)
Assignments are due in class, on due date.
No late homeworks accepted!
• Tests
– Midterm, around Oct. 20
– Final
– Closed book, closed notes
What is AI?
• What is intelligence?
– “The capacity to learn and solve problems” [Webster
dictionary]
– “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.” [McCarthy] &
Alice Bot (http://www.alicebot.org/)
– Ability to think and act rationally.
• What are “ingredients” of intelligence?
“Ingredients” of intelligence
• Ability to interact with real world
– Perceive, understand, act.
– Language understanding and formation.
– Visual perception.
• Reasoning and planning
– Modeling external world
– Problem solving, planning, decision making
– Ability to deal with unexpected problems, dealing
with uncertainty
“Ingredients” of intelligence (cont’d)
• Learning and adaptation
– Continuous update of our model of the world and
adaptation to it
What is AI?
•
•
•
•
•
A field that focuses on developing techniques to enable computer
systems to perform activities that are considered intelligent (in humans
and other animals). [Dyer]
The science and engineering of making intelligent machines, especially
intelligent computer programs. It is related to the similar task of using
computers to understand human intelligence, but AI does not have to
confine itself to methods that are biologically observable. [McCarthy]
The study of how to make computer do things which, at the moment,
people do better. [Rich&Knight]
The design and study of computer programs that behave intelligently.
[Dean, Allen, & Aloimonos]
The study of [rational] agents that exist in an environment and perceive
and act. [Russell&Norvig]
Goals of AI
• Scientific and engineering
– Understanding of computational mechanisms
needed for intelligent behavior
– Intelligent connection of perception and action
– Replicate human intelligence
– Solve knowledge-intensive tasks
– Enhance human-human, human-computer and
computer-computer interaction/communication
Some applications of AI
•
Game Playing
Deep Blue Chess program beat world champion Gary Kasparov
•
Speech Recognition
PEGASUS spoken language interface to American Airlines' EAASY SABRE reseration system, which
allows users to obtain flight information and make reservations over the telephone. The 1990s has seen
significant advances in speech recognition so that limited systems are now successful.
•
Computer Vision
Face recognition programs in use by banks, government, etc. The ALVINN system from CMU
autonomously drove a van from Washington, D.C. to San Diego (all but 52 of 2,849 miles), averaging 63
mph day and night, and in all weather conditions. Handwriting recognition, electronics and manufacturing
inspection, photointerpretation, baggage inspection, reverse engineering to automatically construct a 3D
geometric model.
•
Expert Systems
Application-specific systems that rely on obtaining the knowledge of human experts in an area and
programming that knowledge into a system.
•
Diagnostic Systems
Microsoft Office Assistant in Office 97 provides customized help by decision-theoretic reasoning about an
individual user. MYCIN system for diagnosing bacterial infections of the blood and suggesting treatments.
Intellipath pathology diagnosis system (AMA approved). Pathfinder medical diagnosis system, which
suggests tests and makes diagnoses. Whirlpool customer assistance center.
Some applications of AI (cont’d)
•
Financial Decision Making
Credit card companies, mortgage companies, banks, and the U.S. government employ AI systems to detect
fraud and expedite financial transactions. For example, AMEX credit check. Systems often use learning
algorithms to construct profiles of customer usage patterns, and then use these profiles to detect unusual
patterns and take appropriate action.
•
Classification Systems
Put information into one of a fixed set of categories using several sources of information. E.g., financial
decision making systems. NASA developed a system for classifying very faint areas in astronomical images
into either stars or galaxies with very high accuracy by learning from human experts' classifications.
•
Mathematical Theorem Proving
Use inference methods to prove new theorems.
•
Natural Language Understanding
Google's translation of web pages. Translation of Catepillar Truck manuals into 20 languages. (Note: One
early system translated the English sentence "The spirit is willing but the flesh is weak" into the Russian
equivalent of "The vodka is good but the meat is rotten.")
•
Scheduling and Planning
Automatic scheduling for manufacturing. DARPA's DART system used in Desert Storm and Desert Shield
operations to plan logistics of people and supplies. American Airlines rerouting contingency planner.
European space agency planning and scheduling of spacecraft assembly, integration and verification.
•
Robotics and Path planning
•
Biology and medicine
•
Modeling of cellular functions, analysis of DNA and proteins.
and…
NASA’s Rover mission.
Roomba!
Roomba’s (artificial) intelligence fits in 256 bytes of
program space!
Turing test
(A. Turing, “Computing machinery and intelligence”, 1950)
•
•
•
•
•
•
•
Interrogator asks questions of two “people” who are out of sight and
hearing. One is a human, the other one a machine.
30mins to ask whatever she/he wants.
To determine only through questions and answers which is which.
If it cannot distinguish between human and computer, the machine has
passed the test!
Predicted that in 2000 a machine would have 30% chance of fooling a
lay person for 5min.
Suggested major components of AI (knowledge, reasoning, language
understanding, learning)
Anticipated arguments against AI in 50 years to follow
Problems with Turing test
• Newel and Simon
– As much a test of the judge as of the machine.
– Promotes artificial con-artists, not intelligence
(Loebner prize, http://www.loebner.net/Prizef/loebner-prize.html)
Fundamental Issues for most AI
problems
• Representation
Facts about the world have to be represented in some way, e.g., mathematical logic is one language that is
used in AI. Deals with the questions of what to represent and how to represent it. How to structure
knowledge? What is explicit, and what must be inferred? How to encode "rules" for inferencing so as to find
information that is only implicitly known? How to deal with incomplete, inconsistent, and probabilistic
knowledge? Epistemology issues (what kinds of knowledge are required to solve problems).
• Search
Many tasks can be viewed as searching a very large problem space for a solution. For example, Checkers
has about 1040 states, and Chess has about 10120 states in a typical games. Use of heuristics (meaning
"serving to aid discovery") and constraints.
• Inference
From some facts others can be inferred. Related to search. For example, knowing "All elephants have
trunks" and "Clyde is an elephant," can we answer the question "Does Clyde hae a trunk?" What about
"Peanuts has a trunk, is it an elephant?" Or "Peanuts lives in a tree and has a trunk, is it an elephant?"
Deduction, abduction, non-monotonic reasoning, reasoning under uncertainty.
• Learning
Inductive inference, neural networks, genetic algorithms, artificial life, evolutionary approaches.
• Planning
Starting with general facts about the world, facts about the effects of basic actions, facts about a particular
situation, and a statement of a goal, generate a strategy for achieving that goals in terms of a sequence of
primitive steps or actions.
Design methodology and goals
Act
Human
Rational
Think like humans
"cognitive science"
Ex. GPS
Think rationally =>
formalize inference
process
"laws of thought"
Act like humans
Ex. ELIZA
Turing Test
Act rationally
"satisficing" methods
•
Focus not just on behavior and I/O, look at reasoning process. Computational model should reflect "how"
results were obtained. GPS (General Problem Solver): Goal not just to produce humanlike behavior (like
ELIZA), but to produce a sequence of steps of the reasoning process that was similar to the steps followed
by a person in solving the same task.
•
Formalize the reasoning process, producing a system that contains logical inference mechanisms that are
provably correct, and guarantee finding an optimal solution. This brings up the question: How do we
represent information that will allow us to do inferences like the following one? "Socrates is a man. All men
are mortal. Therefore Socrates is mortal." -- Aristotle
•
Behaviorist approach. Not interested in how you get results, just the similarity to what human results are.
ELIZA: A program that simulated a psychotherapist interacting with a patient and successfully passed the
Turing Test.
•
For a given set of inputs, tries to generate an appropriate output that is not necessarily correct but gets the
job done. Rational and sufficient ("satisficing" methods, not "optimal").
Brief history of AI
•
•
•
•
•
•
•
•
•
•
•
•
•
1943
McCulloch & Pitts: Boolean circuit model of brain
1950
Turing's ``Computing Machinery and Intelligence''
1952-69
Look, Ma, no hands!
1950s
Early AI programs, including Samuel's checkers program,
Newell & Simon's Logic Theorist, Gelernter's Geometry Engine
1956
Dartmouth meeting: ``Artificial Intelligence'' adopted
1965
Robinson's complete algorithm for logical reasoning
1966-74
AI discovers computational complexity and Neural network
research almost disappears
1969-79
Early development of knowledge-based systems
1980-88
Expert systems industry booms
1988-93
Expert systems industry busts: ``AI Winter''
1985-95
Neural networks return to popularity
1988
Resurgence of probability; general increase in technical depth
and ``Nouvelle AI'': ALife, GAs, soft computing
1995Agents agents everywhere…
This course
•
•
•
•
•
•
Search,
Knowledge representation,
Planning,
Uncertainty,
Learning, and
Examples and applications in speech and
language modeling, visual perception,
medical informatics, and robotics.