Transcript Note13 - Computer Science

Objectives
This part provides an introduction to some
main strategies and methods used in
artificial intelligence systems. The topics
include the history and applications of AI,
logical reasoning, state space searching,
heuristic searching, game playing, expert
systems, and problem solving methods.
CS3754 Class Notes, John Shieh,
2013
1
Introduction to AI
Intelligence means:
a system can adapt itself to novel situations,
has the capacity to reason, to understand the
relationships between facts, to discover
meanings, to recognize truth, and to learn.
Artificial intelligence is:
the science of making machines do things
that would require intelligence if done by
men.
CS3754 Class Notes, John Shieh,
2013
2
Can machines think?
Answer: Turing test (1950).
• Measure the performance of an intelligent
machine against a human being.
• Replace the question of intelligence by a
clearly defined empirical test.
• Provide a basis for schemes used to evaluate
AI programs.
CS3754 Class Notes, John Shieh,
2013
3
Fig 1.1 The Turing test.
CS3754 Class Notes, John Shieh,
2013
4
Critics to Turing Test
• It is not enough to see how a machine acts
• We need to know what internal “mental”
states it has
CS3754 Class Notes, John Shieh,
2013
5
The Chinese Room argument (Searle, 1980)
• The system consists of a human, who
understands only English, equipped with a
rule book, written in English, and various
stacks of paper, some blank, some with
indecipherable inscription.
• The system is inside a room with a small
opening to outside.
• Through the opening, the input written in
Chinese is answered in Chinese
CS3754 Class Notes, John Shieh,
2013
6
The Real Claim made by Seals
• Certain kind of objects are incapable of conscious
understanding (of Chinese)
• The human, paper, and rule book are objects of
this kind
• If each of a set of objects is incapable of conscious
understanding, then any system constructed from
the objects is incapable of conscious
understanding
• Therefore there is no conscious understanding in
the Chinese room
CS3754 Class Notes, John Shieh,
2013
7
Arguments to Chinese Room
• While the first two claims of Seale are on
Firm ground
• The Third is not
CS3754 Class Notes, John Shieh,
2013
8
Two categories of AI research:
a) Mind as object and machine as tool
b) Computer as object and mind as model.
CS3754 Class Notes, John Shieh,
2013
9
Two approaches to AI
• The engineering approach -- to create a system
that is able to deal intellectual tasks, regardless of
whether the methods and techniques used are
similar to those used by human.
• The modeling approach -- try to gain an
understanding of the inside mechanisms of a real
life system and to explain and predict its behavior,
e.g., neural network.
CS3754 Class Notes, John Shieh,
2013
10
Three basic motivations for research
in AI
• To replace human intelligence.
• To establish theories of human intelligence
in the form of simulation models.
• To assess the capabilities of present
software and hardware for future
development.
CS3754 Class Notes, John Shieh,
2013
11
AI is particularly concerned with the
automation of intelligent behavior
• As a young discipline, it is the collection of
problems and methodologies studied by AI
researchers.
• As an empirical science, it is the study of
symbolic systems for the purpose of
understanding and implementing intelligent
activities.
CS3754 Class Notes, John Shieh,
2013
12
Two most fundamental problems of
AI
• knowledge representation
• problem-solving technique, such as search
CS3754 Class Notes, John Shieh,
2013
13
History of AI
• Pre-1950
– Aristotle's philosophy and logic.
– Descartes's view -- the structure of ideas about the world is not
necessarily the same as the physical world.
– Graph theory (Euler, 1735).
– Boolean algebra (Boole, 1847).
– First-order predicate calculus (Frege, 1879).
– Neural net model (Warren McCulloch, 1943)
• 1950-1970:
– LISP (John McCarthy, Dartmouth, 1960)
– Frames - a knowledge representation (Marvin Minsky, Dartmouth,
1975)
– Logic Theorist proves theorems in propositional calculus (A.
Newell, J.C.Shaw, and H. Simon, 1957)
– DENDRAL infers the structure of organic molecules (Edward
Feigenbaum, CMU,later 1960)
CS3754 Class Notes, John Shieh,
2013
14
History of AI
• 1970-present
– Knowledge representations
• Scripts (Roger Schank & Robert Abelson, Yale, 1977)
– Game playing (tic-tac-toe, chess, 16 puzzle):
• Board games
• Heuristic search techniques
• Chess playing programs (David Slate & Larry Atkin,
Northwestern, 1976)
– Automated reasoning and theorem proving
• Two approaches: proof finding and consequence finding.
• General Problem Solver (Allen Newell & Herbert Simon,
CMU, 1963).
• The resolution principle (J.A. Robinson, 1965).
• Formalize search algorithms.
• Develop formal representation languages, such as predicate
calculus, fuzzy logic
CS3754 Class Notes, John Shieh,
2013
15
– Expert systems
• Importance of domain-specific knowledge.
• MYCIN diagnosing and prescribing treatment for spinal
meningitis and bacterial infection of the blood (Stanford,
mid-1970).
• PROSPECTOR (Richard Duda, SRI, 1979)
– Natural language understanding
• Attempt to deal with issues of semantic meaning as well as
syntactic form.
• Real understanding depends on the background knowledge
about the domain of discourse and idioms and an ability to
apply general contextual knowledge to resolve ambiguities.
• Much of the current work is devoted to finding
representational formalisms.
• SHRDLU (Terry Winograd, 1973) for a “micro world”
• HEARSAY (Raj Reddy, CMU, 1976)
CS3754 Class Notes, John Shieh,
2013
16
– Planning and robotics
• Generate plans based on specialized knowledge of
some domain.
• Hierarchical problem decomposition.
• Error recovery -- automatic revision of plans
corrects some unexpected problems.
• SHAKEY -- one of the first robots (Bertram
Raphael, SRI, early 1970)
– Machine learning
• Winston's learning program (1975).
• Learn from experience, analogy, examples, or by
being told.
CS3754 Class Notes, John Shieh,
2013
17
– Vision
• Vision is a form perception based on optical
sensing.
• Perception is the construction and maintenance of an
internal model of the external environment.
• Image processing: pre-processing, feature
extraction.
• 3-D modeling and scene analysis
– Languages and environments for AI
• High-level languages: LISP, PROLOG.
• Object-oriented programming.
• Shells of expert systems.
CS3754 Class Notes, John Shieh,
2013
18
Important Research and Application Areas
1.2.1
Game Playing
1.2.2
Automated Reasoning and Theorem Proving
1.2.3
Expert Systems
1.2.4
Natural Language Understanding and Semantic Modelling
1.2.5
Modelling Human Performance
1.2.6
Planning and Robotics
1.2.7
Languages and Environments for AI
1.2.8
Machine Learning
1.2.9
Alternative Representations: Neural Nets and Genetic Algorithms
CS3754 Class Notes, John Shieh,
2013
19
Important Features of Artificial Intelligence
1.
The use of computers to do reasoning, pattern recognition, learning, or some other
form of inference.
2.
A focus on problems that do not respond to algorithmic solutions. This underlies
the reliance on heuristic search as an AI problem-solving technique.
3.
A concern with problem-solving using inexact, missing, or poorly defined
information and the use of representational formalisms that enable the
programmer to compensate for these problems.
4.
Reasoning about the significant qualitative features of a situation.
5.
An attempt to deal with issues of semantic meaning as well as syntactic form.
6.
Answers that are neither exact nor optimal, but are in some sense “sufficient”.
This is a result of the essential reliance on heuristic problem-solving methods in
situations where optimal or exact results are either too expensive or not possible.
7.
The use of large amounts of domain-specific knowledge in solving problems. This
is the basis of expert systems.
8.
The use of meta-level knowledge to effect more sophisticated control of problemsolving strategies.
CS3754 Class Notes, John Shieh,
2013
20