Transcript Computer Science as Empirical Inquiry : Symbols and Search Allen

Computer Science as Empirical
Inquiry : Symbols and Search
Allen Newell and Herbert A.Simon(1976)
Interdisciplinary Program in Cognitive Science
Lee Jung-Woo
March, 22, 1999
1. Introduction
• Computer Science is an empirical discipline.
– Each new machine and new program that are built are experiments.
– It poses a question to nature, and its behavior offers clues to an
answer.
– As basic scientists we build machines and programs as a way of
discovering new phenomena and analyzing phenomena we already
know about.
2. Symbols and Physical Symbol System
• 2.1 Laws of Qualitative Structure
– All science characterize the essential nature of the systems they
study. These characterizations are invariably qualitative in nature,
for they set the terms within which more detailed knowledge can
be developed.
– The Cell Doctrine in Biology / Plate Tectonics in Geology
– The Germ Theory of Disease / The Doctrine of Atomism
• 2.2 Physical Symbol Systems
• 2.3 Development of the Symbol System Hypothesis
• 2.4 The Evidence
2.2 Physical Symbol Systems(1)
• Requirement for Intelligent Action
– The ability to store and manipulate symbols
• Physical Symbol System
– “Physical” : (1) obey the laws of physics(realizable by engineering)
(2) not restricted to human symbol systems
– Symbol(physical pattern), Expression(symbol structure),
Process(creation,modification,reproduction,destruction)
– Designation : An expression designate an object or an process
– Interpretation : The system can interpret an expression
– Additional requirements
2.2 Physical Symbol Systems(2)
• Physical Symbol System Hypothesis(PSSH)
– A physical symbol system has the necessary and sufficient
means for general intelligent action
• This is an empirical hypothesis.
– Scientifically, one can attack or defend it only by bringing forth
empirical evidence about the natural world.
• We need to trace the development of this hypothesis and
look at the evidence for it.
2.3 Development of the PSSH(1)
• Formal Logic
– Program of Frege, Whitehead and Russell for formalizing logic
– Mathematical logic(propositional, first-order, and higher-order
logics)
– “Symbol game” : Logic was a game played with meaningless
tokens according to certain purely syntactic rules. All meaning had
been purged. One had a mechanical system about which various
things could be proved.
2.3 Development of the PSSH(2)
• Turing Machines and Digital Computer
• The Stored Program Concept
• List Processing
• Lisp
2.4 The Evidence for PSSH(1)
• The evidence for the hypothesis that physical symbol
systems are capable of intelligent action, and that general
intelligent action calls for a physical symbol system.
– The evidence for the sufficiency of physical symbol systems for
producing intelligence(Attempt to construct and test specific
systems that have such a capability) -- Artificial Intelligence
– The evidence for the necessity of having a physical symbol
systems wherever intelligence is exhibited.(Attempt to discover
whether Man’s cognitive activity can be explained as the working
of a physical symbol system) -- Cognitive Psychology.
2.4 The Evidence for PSSH(2)
• Constructing Intelligent Systems(A.I.)
– Identify a task domain calling for intelligence, then construct a
program for a digital computer that can handle tasks in that domain
– Puzzles and games such as chess programs
– System that handle and understand natural language, systems for
interpreting visual scenes, systems for hand-eye coordination,
systems that design, systems that writhe computer programs,
systems for speech understanding
– General Problem Solver(GPS), PLANNER, CONNIVER
– An initial burst of activity aimed at building intelligent programs
for a wide variety of almost randomly selected tasks is giving way
to more sharply targeted research aimed at understanding the
common mechanisms of such systems.
2.4 The Evidence for PSSH(3)
• The Modeling of Human Symbolic Behavior(Cognitive
Psychology)
– The search for explanations of man’s intelligent behavior in terms
of symbol systems has had a large measure of success to the point
where information processing theory is the leading contemporary
point of view in cognitive psychology.
– In the areas of problem solving, concept attainment, and long-term
memory, symbol manipulation models now dominate the scene.
• Other Evidence
– Negative evidence : the absence of specific competing hypotheses
as to how intelligent activity might be accomplished
– ex. Behaviorism and Gestalt theory
3. Heuristic Search
• Question : “OK, so far. But how physical symbol systems
accomplish such intelligent actions?”
• Answer : Symbol systems solve problems by using the
processes of heuristic search
• Heuristic Search Hypothesis
– The solution to problems are represented as symbol structures.
A physical symbol system exercises it intelligence in problem
solving by search-that is, by generating and progressively
modifying symbol structures until it produces a solution
structure.
3.1 Problem Solving(1)
• Ability to solve problem is generally taken as a prime
indicator that a system has intelligence
• To state a problem is to designate (1) a test for a class of
symbol structures(solutions of the problem) and (2) a
generator of symbol structures(potential solutions).
• To solve a problem is to generate a structure, using (2), that
satisfies the test of (1)
3.1 Problem Solving(2)
• The physical symbol systems can represent problem spaces
and possess move generators.
– Problem space : a space of symbol structures in which problem
situations, including the initial and goal situations, can be
represented.
– Move generator : the processes for modifying one situation in the
problem space into another.
• The physical symbol systems’ task, when it is presented
with a problem and a problem space, is to use its limited
processing resources to generate possible solution, one
after another, until it finds one that satisfies the problemdefining test.
3.2 Search in Problem Solving(1)
• The study of problem solving was almost synonymous
with the study of search processes
• Extracting Information from the Problem Space
– A condition for the appearance of intelligence is that the space of
symbol structures exhibit at least some degree of order and pattern.
– Pattern in the space of symbol structures be more or less detectable
– The generator of potential solutions be able to behave differentially,
depending on what pattern it detected.
– Ex) AX+B = CX+D --> X = E
3.2 Search in Problem Solving(2)
• Search Trees
– Programs that play chess VS. Strongest human players
– Search is a fundamental aspect of a symbol system’s exercise of
intelligence in problem solving but that amount of search is not a
measure of the amount of intelligence being exhibited.
– When the symbolic systems that is endeavoring to solve a problem
knows enough what to do, it simply proceeds directly towards its
goal.
3.2 Search in Problem Solving(3)
• The Forms of Intelligence
– An intelligent system generally needs to supplement the selectivity
of its solution generator with other information-using techniques to
guide search, that is, to generate only structures that show promise
of being solutions or of being along the path toward solutions.
– In serial heuristic search, the basic question always is : “What shall
be done next?”
– That question has two components : (1) from what node in the tree
shall we search next, and (2) what direction shall we take from that
node?
3.2 Search in Problem Solving(4)
• A Summary of the Experience
– First conclusion : from what has been learned about human expert
performance in tasks like chess, it is likely that any system capable
of matching that performance will have to have access, in its
memories, to very large stores of semantic information.
– Second conclusion : some part of the human superiority in tasks
with a large perceptual component can be attributed to the special-
purpose built-in parallel processing structure of the human eye and
ear.
3.3 Intelligence Without Much Search(1)
• Our analysis of intelligence equated it with ability to
extract and use information about the structure of the
problem space, so as to enable a problem solution to be
generated as quickly and directly as possible
• Nonlocal Use of Information
– Information gathered in the course of tree search was usually only
used locally, to help make decisions at the specific node.
– In recent years, a few exploratory efforts have been made to
transport information from its context of origin to other appropriate
contexts.
– Berliner(1975) : use causal analysis to determine the range over
which a particular piece of information is valid.
3.3 Intelligence Without Much Search(2)
• Semantic Recognition Systems
– A second active possibility for raising intelligence is to supply the
symbol system with a rich body of semantic information about the
task domain it is dealing with.
– What is new is the realization of the number of patterns and
associated information that may have to be stored for master-level
play.
– A particular, and especially a rare, pattern can contain an enormous
amount of information, provided that it is closely linked to the
structure of the problem space.
3.3 Intelligence Without Much Search(3)
• Selecting Appropriate Representations
– A third line of inquiry is concerned with the possibility that search
can be reduced or avoided by selecting an appropriate problem
space.
4. Conclusion(1)
• Physical Symbol Systems
– Intelligence resides in physical symbol systems. This is computer
science’s most basic law of qualitative structure.
– Symbol systems are collections of patterns and processes, the latter
being capable of producing, destroying and modifying the former.
– The most important properties of patterns is that they can designate
objects, processes, or other patterns, and that, when they designate
processes, they can be interpreted.
– Interpretation means carrying out the designated process.
– Symbolic system : Formal logic, The Turing machine, The storedprogram concept, List processing
4. Conclusion(2)
• Heuristic Search
– A second law of qualitative structure for AI is that symbol systems
solve problems by generating potential solutions and testing them,
that is, by searching.
– Since they have finite resources, the search cannot be carried out
all at once, but must be sequential.
– They exercise intelligence by extracting information from a
problem domain and using that information to guide their search,
avoiding wrong turns and circuitous bypaths.
Postscript
• There remain intellectual positions that stand outside the
entire computational view and regard the hypothesis as
undoubtedly false(Dreyfus 1979, Searle 1980)
– Philosopher : The central problem of semantics or intentionalityhow symbols signify their external referents-is not addressed by
physical symbol systems.
– Connectionists : There are forms of processing organization that
will accomplish all that symbol systems do, but in which symbols
will not be identifiable entities.