Transcript Computer Science as Empirical Enquiry

Cognitive Computing
2012
The computer and the mind
3. NEWELL & SIMON
PHYSICAL SYMBOL HYPOTHESIS
Professor Mark Bishop
Background

The computing machine is not just hardware or software but
specifies the execution of software by hardware.

Computer Science is an empirical (derived from experience)
discipline.

Each machine is an experiment - development of knowledge
through empirical enquiry.

Newell and Simon’s paper focuses on two important examples:
 the symbolic system;
 heuristic search.
26/03/2016
(c) Bishop: The computer and the mind
2
Symbols and physical symbol
systems

All sciences are concerned with the essential nature of
the systems they study.

Such characterisations are usually qualitative. E.g.


In biology the building block of all living things is the cell;
In geology the surface of earth a collection of huge plates etc.

Laws of ‘qualitative structure’ are everywhere in science,
usually defining the terms on which a science operates.

On a fundamental level computer science can be considered an
attempt to (empirically) explain what symbols really are.
26/03/2016
(c) Bishop: The computer and the mind
3
Ernst Cassirer: on signals and
symbols
“Man has, as it were, discovered a new method of
adapting himself to his environment. Between the
receptor system and the effector system, which are
to be found in all animal species, we find in man a
third link which we may describe as the symbolic
system. This new acquisition transforms the whole
of human life. As compared with the other animals
man lives not merely in a broader reality; he lives, so
to speak, in a new dimension of reality.”
Cassirer, An Essay on Man, (1944)
22/10/2012
(c) Bishop: The computer and the mind
4
Cassirer: the philosophy of
symbolic forms

A symbol has no actual existence as part of the physical world; it
has a ‘meaning’.

Symbols - in the proper sense of this term - cannot be reduced to
mere signals.

Symbols and signals belong to two different universes of discourse:

‘Signals’ are operators - a signal is part of the physical world of
being and has a physical or substantial being.

‘Symbols’ are designators - a symbol is part of the human world
of meaning.
26/03/2016
(c) Bishop: The computer and the mind
5
Physical Symbol Systems, (PSS)

In a physical symbol system the term ‘physical’ denotes that the
system is realizable in [machine] hardware and not restricted to
human symbols systems.

A PSS defines ‘symbol’ as a set of ‘physical patterns’



Such patterns are components of a ‘symbol structure’, (or
expression).
A ‘symbol structure’ is composed of tokens related in a
‘physical way’, (e.g. by adjacency), plus processes capable of
operating on such expressions to produce further expressions.
Thus a ‘physical symbol system’ is a set of ‘symbol
structures’ mechanically evolving over time.
26/03/2016
(c) Bishop: The computer and the mind
6
The physical symbol systems hypothesis
<http://aaai.org/AITopics/AIVideos/2007-0072>

A PSS has the necessary and sufficient means for
‘general intelligent action’.

It is an empirical and qualitative law.

A PSS is an instance of a universal machine, hence
intelligent action will be realizable by universal
computer.

The physical symbol system hypothesis asserts that
the intelligent machine IS a PSS.
26/03/2016
(c) Bishop: The computer and the mind
7
Steps towards the ‘physical
symbol system’

Formal logic (cf. Russell & Whitehead)


Turing Machines and Digital Computers


An attempt to purge ‘meaning’ from symbols.
Universal computing machines.
Stored Program as data:
 The UTM: Turing Machine data can equally specify a program.

26/03/2016
NB. Albeit Newell and Simon observe that in the early days no
attempt was made to investigate machines with ‘self modifying
code’.
(c) Bishop: The computer and the mind
8
The ‘designating’ symbol


List processing (LISP):

Data can now designate (indirection)

Indirection gives us ‘pointers’ and ‘dynamic memory’
Conclusion:

26/03/2016
We needed emergence of all of the above to facilitate
the emergence of the concepts of: (i) ‘symbol
manipulation’; (ii) ‘the designating symbol’; and (iii)
the ‘physical symbol system’.
(c) Bishop: The computer and the mind
9
Artificial intelligence (A.I.) and
psychology

A.I. is concerned with constructing ‘intelligent computer systems’.
 Over its history lots of programs have been developed to
investigate specific small [toy] aspects of intelligent action.
 A common principle is heuristic (short-cut; non-exhaustive) search.

In Psychology, investigation of human problem solving entails the
observation and modelling of human symbolic behaviour.

AI programs such as GPS (the ‘General Problem Solver’) were
developed to simulate human problem solving behaviour.
 GPS: an attempt at generality in problem solving.
 The core concepts of GPS derived observation of human problem
solving in action.
26/03/2016
(c) Bishop: The computer and the mind
10
Principle evidence for PSS

At the time of Newell & Simon’s paper there appeared to be NO
serious competing hypothesis.

Contrast currently with the emergence of:




connectionism;
embodied cognitive science; Brooks: A.I. and the subsumption architecture.
Radical embodied cognitive science & dynamical system theory;
enactivism etc.

Newell and Simon claim that ‘gestalt theory’ (on ‘wholeness’) and
behaviourism are inadequate as they lack the explanatory power of the
PSS.

However, although the PSS hypothesis demonstrates that computer
science can be construed as an empirical/experimental scientific
enterprise, it does not specify how to use a PSS for intelligent action…
26/03/2016
(c) Bishop: The computer and the mind
11
Heuristic search hypothesis

Problem solutions represented as symbol structures.

A PSS exercises intelligence by search.


i.e. A PSS progressively modifies the symbol structure until it
produces a possible problem solution.
Time is a constraint in any real PSS.

Newell & Simon do not consider fully parallel search etc.

Limited resource PSS and the serial PSS are synonymous.
26/03/2016
(c) Bishop: The computer and the mind
12
Problem solving: Plato and Meno

“How do you enquire Socrates into that which you know not?”

“What will you put forth as the subject of enquiry?”

“And if you find what you want, how will you ever know that this
is what you did not know?”

Theory of Recollection (Plato)

‘Knowledge is the recollection of timeless forms from before our
immortal souls were imprisoned inside our bodies’.
26/03/2016
(c) Bishop: The computer and the mind
13
Problem solving: heuristic search

Establish a test for a class of symbol structures and a generator of
possible solution PSSs.

Repeatedly generate and test until the PSS satisfies the test.

NB. This process is not like dreams; we can't immediately just generate a
solution as we don’t know how good a solution is until we test it.

Consider chess:




We can't immediately generate best positions (‘as if in a dream’).
We must painstakingly search thru all available solutions and somehow
evaluate them to find 'best' (cf. Meno).
Even Deep Blue can't solve perfectly for chess (and so must approximate).
A PSS must use ‘limited processing’ to search the space of possible
solutions; an intelligent PSS makes wise choices of what to evaluate
next (e.g. alpha-beta pruning)
26/03/2016
(c) Bishop: The computer and the mind
14
Extracting information from the
problem space

If solutions are randomly distributed we can do no
better than random search.

But in tasks which require ‘intelligence’:



26/03/2016
The expectation is that solution distributions are not
random;
the pattern of solutions is detectable;
the ‘generator’ is capable of ‘adaptive behaviour’ as it
discovers this pattern.
(c) Bishop: The computer and the mind
15
Intelligence by incremental
application of knowledge

Consider the algebraic expression: AX + B = CX + D.

We could generate solutions for X by repeated ‘trial and error’.


The problem is best solved by ‘incremental application of
knowledge’.


This would be extremely unintelligent.
Thus rearranging the above algebraic expression demonstrates
intelligent problem solving. I.e. X = (D – B) / (A – C)
This methodology demonstrates ‘intelligence’ to find a solution
without the need for either reincarnation or access to Plato’s
‘perfect forms’ !
26/03/2016
(c) Bishop: The computer and the mind
16
Search trees

Combinatorial explosion in search


If the generator forms ‘B’ branches then we get a tree of
‘BD’ tests where ‘D’ is depth of search.
Chess involves very broad trees which rapidly form
very large search spaces.

26/03/2016
Although we note that human players only evaluate a few
moves by being very selective in what branches to
evaluate.
(c) Bishop: The computer and the mind
17
Measuring intelligence

The raw amount of search involved in solving a problem is not a
measure of intelligence..

A problem’s difficulty is more accurately approximated by the
amount of search that would be required without application of
intelligence.


“The hope is periodically ignited that a chess playing program will
be developed to win by brute force”.
 As it happened IBM’s ‘Deep Blue’ [effectively] did just this!
The need to avoid combinatorial explosion

26/03/2016
Only rarely can breadth be reduced to unity - as in the algebraic
manipulation example - so typically we must deploy heuristics
to guide the search and narrow the search tree.
(c) Bishop: The computer and the mind
18
Simple heuristic search

Attempts to answer the question, “What is to be done next in the
search process?”

E.g. From what node in tree do we (re) start next search?

Best-fit search: examine the relative distance of each node from final
solution.

Means-end analysis: the search process over the problem space
combines aspects of both forward and backward reasoning in that both
the condition and action portions of rules are looked at when
considering which rule to apply.

26/03/2016
Differences between the current and goal states are used to propose
operations which reduce the differences.
(c) Bishop: The computer and the mind
19
Weak and strong search

‘Best Fit’ search evolved from Logic Theorist and ‘Means-End
Analysis’ evolved with GPS.

For reasons related to the size of their memory, early chess programs used
‘Depth First’ search as they couldn't store large search trees in memory.



Newell and Simon observe that there has been little mathematical
investigation into search algorithms.


It is suggested that the poor performance of A.I. systems against humans is
due to humans using more SEMANTIC knowledge on very parallel
hardware;
Deep Blue??
This is not so true now…
The above ‘weak search’ methods seek to control combinatorial
explosion when it cant be avoided (e.g. TSP).

26/03/2016
‘Strong search’ methods aim to eliminate it by utilizing structure in the
solution domain.
(c) Bishop: The computer and the mind
20
Intelligence without much search

The use of ‘non-local information’

When playing chess usually only use knowledge locally - should try to
combine it to produce a global picture.


‘Semantic Recognition Systems’

Store lots of problem specific knowledge.


eg. For chess might store upwards of 50K interesting patterns [Deep Blue].
‘Appropriate Representations’



eg. HEARSAY speech understanding project uses various types of search
on phonemes; lexical; syntatic & semantic and combines it globally onto a
blackboard.
Consider chess board with two diagonal corners removed.
Can it be covered by exactly 31 tiles?
We could evaluate (massive) search tree or observe that opposite
ends of a diagonal are same colour, so can‘t do it.
26/03/2016
(c) Bishop: The computer and the mind
21
Conclusion
‘With the development of physical symbol
systems and heuristic search Newell and
Simon significantly moved the process of
intelligent problem solving away from Plato,
at a time when intelligent thought was
deemed intangible’.
26/03/2016
(c) Bishop: The computer and the mind
22