Transcript icnnai06

Artificial Intelligence and Neural Networks
The Legacy of Alan Turing and John von
Neumann
Heinz Mühlenbein
Fraunhofer AIS
Outline

Introduction

Turing and Machine Intelligence

Turing’s Construction
- Turing on learning and evolution
- Turing and neural networks
- Discipline and initiative

Von Neumann’s Logical Theory of Automata
- McCulloch Pitts theory
- Complication and self-reproduction
Mühlenbein: Artificial Intelligence and Neural Networks
2
Outline
 Discussion of the Proposals
 Memory Capacity of the Brain
 Dartmouth Proposal Summer School 1955
 Artificial Intelligence 2006
 Meta-Learning
 Common Sense of the Machine
 Conclusions and Outlook
No philosophical discussion of the possibility of machine
intelligence!
Mühlenbein: Artificial Intelligence and Neural Networks
3
Introduction
Parallel to the design of the first electronic computers, both Alan
Turing and John von Neumann speculated about non-numeric
(intelligent) applications of these computers
Alan Turing: Computing Machinery and Intelligence (1950)
Intelligent Machinery (1969)
John von Neumann: The General and Logical Theory of
Automata(1948)

What are the major ideas?

What are the major problems of the design?
Mühlenbein: Artificial Intelligence and Neural Networks
4
Turing and Machine Intelligence


Can machines think ?
-
Replaced by an imitation game
-
(A) machine, (B) human : (C) interrogator
Bold answer:
I believe that in about fifty years time it will be possible to
programme computers with a storage capacity of about 109 bits to
make them play the imitation game so well that an average
interrogator will not have more than 70% chance of making the
right identification after five minutes of questioning.

The purely behaviorist definition of intelligence not a good idea!
Mühlenbein: Artificial Intelligence and Neural Networks
5
Turing’s Construction

Evidence
The problem is mainly one of programming. Estimates of the
storage capacity of the brain vary from 1010 to 1015 binary
digits…I should be surprised if more than 109 was required for
playing the imitation game. At my present rate of working I
produce about thousand digits of programme a day, so that about
sixty workers working steadily through fifty years might
accomplish the work.

Exist there more expeditious methods?
In the process of trying to imitate an adult human mind we are
bound to think a good deal about the process which has brought it
to the state that it is in.
Mühlenbein: Artificial Intelligence and Neural Networks
6
Turing’s Construction
The adult brain consists of three major components
1.
The initial state of the brain, say at birth
2.
The education to which it has been subjected
3.
Other experiences, not to be described as education
Why not copying this method?
1.
The brain of the newborn
2.
The education process
3.
Other methods, not to be described as education
Mühlenbein: Artificial Intelligence and Neural Networks
7
Turing on Learning and Evolution

Construct a baby brain

Develop effective learning methods

Teach the baby machine and see how well it learns

Try another baby brain and see how well it learns
Connection between this process and evolution
1.
Structure of the machine = hereditary material
2.
Changes of the machine = mutations
3.
Natural selection = judgment of the experimenter
Mühlenbein: Artificial Intelligence and Neural Networks
8
Turing on Learning Methods
Presumably the child brain is something like a notebook. Rather
little mechanism and lots of blank sheets. Our hope is that there is
so little mechanism in the child brain that something like it can
easily be programmed. The amount of work in the education we
can assume, as a first approximation, to be much the same as for
the human child.

Both predictions (blank sheets, amount of work for education) far
from being correct!
Mühlenbein: Artificial Intelligence and Neural Networks
9
Turing on Learning Methods

Punishment and reward
If the teacher has no other means of communicating to the child,
the amount of information which can reach him does not exceed
the total number of rewards and punishments.

Should child machine understand some language?

Which complexity should the child machine have?
Again I do not know the answer, but I think both approaches
should be tried. We can see only a short distance ahead, but we
can see plenty there that needs to be done.
Mühlenbein: Artificial Intelligence and Neural Networks
10
Turing and Neural Networks
Child brain: unorganized neural network
. Large number of binary neurons
. Two inputs, one output
. Random connections, network might have many loops
. Interesting dynamics
The states from the units from which the input comes are
taken from the previous moment, multiplied together and the
result is subtracted from 1.
What is the power of this network?
Mühlenbein: Artificial Intelligence and Neural Networks
11
Discipline and Initiative
If the untrained infant’s mind is to become an intelligent, it must
acquire both discipline and initiative
. Discipline
means strictly obeying punishment and rewards
. Initiative
Discipline is certainly not enough to produce intelligence.
That which is required in addition we call initiative. Our task
is to discover the nature of this residue as it occurs in man,
and to try to copy it in the machine.
What is initiative? Nearest method transfer learning.
Mühlenbein: Artificial Intelligence and Neural Networks
12
Learning still a mystery









Learning by being told
Learning by imitation
Learning by being told
Active Learning
Learning using words, pictures, words and pictures
Learning by Analogy
Learning by Understanding
Learning by building a model
Etc…..
Mühlenbein: Artificial Intelligence and Neural Networks
13
Suggested Applications

Various games

The learning of languages

Translation of languages

Cryptography

Mathematics
The learning of languages would be the most impressive,
since it is the most human of these activities. This field
seems however to depend too much on sense organs and
locomotion to be feasible.
But the imitation game needs understanding of languages!
Mühlenbein: Artificial Intelligence and Neural Networks
14
Modern Turing Test (Loebner 100.000 $)











PROGRAM: Hello, my name is George and I am the human.
JUDGE: Hi George, cslkjslw weicmslw weos, right?
PROGRAM: Don't repeat your name, csthiang!
JUDGE: If lsjkel lwehlx wouldn't you say?
PROGRAM: No, he's still good.
JUDGE: Who.
PROGRAM: You and me.
JUDGE: If you are human, tell me which is larger, a salt crystal or
the Empire State Building.
PROGRAM: It's caring about another person's well being more
than your own.
JUDGE: What if I care about another person's well being more than
I should?
PROGRAM: How would you do that?
Mühlenbein: Artificial Intelligence and Neural Networks
15
Von Neumann’s Logical Theory of Automata
Symposium: Cerebral mechanism of behavior
Natural organisms are, as a rule, much more complicated
and subtle, much less well understood in detail, than are
artificial automata. Nevertheless, some of the regularities
which we observe in the former may be quite instructive
in our thinking and planning of the latter; and conversely,
a great deal of our experiences and difficulties with our
artificial automata can to some extend projected on our
interpretations of natural.
Interdisciplinary research: brain research and machine
intelligence
Mühlenbein: Artificial Intelligence and Neural Networks
16
Von Neumann’s Logical Theory of Automata
Major limits of artificial automata
1.
The size of the componentry
2.
The limited reliability
3.
The lack of a logical theory of automata
The logic of automata will differ from the present system of formal
logic in two relevant respects:
1.
The actual length of chains of reasoning, that is the change of of
operations, will have to be considered.
2.
The operations of logic will have to be treated by procedures
which allow exceptions with low but non zero probabilities.
Mühlenbein: Artificial Intelligence and Neural Networks
17
Von Neumann’s Logical Theory of Automata
Probabilistic logic
This new system of formal logic will move closer to
another discipline which has been little linked in the past
with logic. This is thermodynamics, primarily in the form
as it was received from Boltzmann, and is that part of
theoretical physics which comes nearest in some of its
aspects to manipulating and measuring information.
Von Neumann’s own work in this area was a dead end, because he
used time within his proposal. Today probabilistic logic is a
flourishing discipline in computer science (extension of
propositional logic, based on probability theory, Bayesian
networks, Maximum Entropy, graphical models)
Mühlenbein: Artificial Intelligence and Neural Networks
18
McCulloch-Pitts Formal Neural Networks
Major result
The functioning of such a network may be defined by
singling out some of the inputs of the entire system and
some of its outputs, and then describing what original
stimuli (input) are to cause what ultimate stimuli (output).
McCulloch and Pitts’ important result is that any
functioning in this sense which can be defined at all
logical, strictly, and unambigously in a finite numer of
words can also be realized by such a formal system.
1.
Can the network be realizes within a practical limit?
2.
Can every existing mode of behavior really be put completely and
unambiguously in words?
Mühlenbein: Artificial Intelligence and Neural Networks
19
The Number One AI Problem
There is no doubt that any special phase of any
conceivable behavior can be described “completely and
unambiguously” in words….It is however an important
limitation, that it applies to every element separately,
and it is far from clear how it will apply to the entire
system of behavior.
Example: Visual Analogy
triangles, curved triangles, rectilinear triangles, partially
drawn triangles, rectangles,…analogous geometric
objects,..
The complete catalogue seems unavoidingly indefinite at
the boundaries.
Mühlenbein: Artificial Intelligence and Neural Networks
20
The Number One AI Problem
Now it is perfectly possible that the simplest and only
practical way to say what constitutes a visual analogy
consists in giving the description of the connections of
the visual brain… It is not at all certain that in this
domain a real object (the brain) might not constitute the
simplest description of itself! (in terms of defining its
functions)
Von Neumann’s approach:
Complication and Self-reproduction
Mühlenbein: Artificial Intelligence and Neural Networks
21
Complication and Self-Reproduction
1.
Constructive machine A, which can copy a description G(X)
A + G(X) := X
2.
General copying machine B
B + G(X) := G(X)
3.
Control machine C first activates B, then A, cut them loose from A + B + C
A + B +C + G(X) := X + G(X)
Now choose X to be A + B + C
4.
Add the description of any automaton D
A + B + C + G(A +B + C + D) := A + B + C + D + G(A +B + C + D)
5.
Allow mutation on description
A + B + C + D + G(A +B + C + D’) := A + B + C + D’ + G(A +B + C + D’)
Mühlenbein: Artificial Intelligence and Neural Networks
22
Complication and Self-Reproduction
Von Neumann constructed a self-reproducing automaton
which consisted of 29 states.
Why was the theory of self-reproducing automata a limited
success?
Self-reproduction is the easy part, but how do we get selfimprovement? From where do we get all the descriptions
D to solve the problems?
Mühlenbein: Artificial Intelligence and Neural Networks
23
Evaluation of Both Proposals
Both researchers investigated the problem of creating
machine intelligence thoroughly. Turing was much more
optimistic. The problem was in his opinion only one of
efficient programming. His proposal:
Child machine and teaching
Von Neumann’s approach was interdisciplinary. He has
clearly seen the problems, he was not sure if such a goal
could be achieved. His proposal:
Develop a new theory of logical automata
Mimic evolution (self-reproduction, complication)
Mühlenbein: Artificial Intelligence and Neural Networks
24
Memory Capacity of the Brain
Von Neumann’s estimate:
Thus the standard receptor (neutron) would seem to
accept 14 distinct digital impressions per second.
Allowing 1010 nerve cells gives a total of 14*1010 bits per
second. Assuming further, for which there is some
evidence, that there is no true forgetting in the nervous
system, an estimate for the entirety of a normal human
lifetime can be made. Putting the latter equal to, say 60
years, the total required memory capacity would turn out
to be 2.8*1020 .
Von Neumann: The Computer and the Brain
Mühlenbein: Artificial Intelligence and Neural Networks
25
Memory Capacity of the Brain
Experiment by Landauer (1986)
People were asked to read text, look at pictures, and hear
words, short passages of music, sentences, and nonsense
syllables. After delays people were tested to determine
how much they had retained. The tests used true/false or
multiple choice questions, in which even a vague memory
of the material would allow the correct choice.
Finally the amount remembered was divided by the time
allotted to memorization. Result:
Human beings remembered very nearly two bits
per second under all experimental conditions.
Mühlenbein: Artificial Intelligence and Neural Networks
26
Memory Capacity of the Brain
Experiment by Landauer (1986)
Continued over lifetime this rate of memorization would
produce somewhat over 2*1010 bits.
Issue still unsolved. Moravec (1998) recently estimated
1015 bits.
Obviously: memory capacity is not the only issue in
creating human intelligence. It is the organization of the
information!
Mühlenbein: Artificial Intelligence and Neural Networks
27
Proposal Dartmouth Summer Project on
Artificial Intelligence (1955)
1.
Automatic Computers
If a machine can do a job, then an automatic calculator can be
programmed to simulate the machine. The speeds memory capacities
of present computers may be insufficient to simulate many of the
higher functions of the human brain, but the major obstacle is not lack
of machine capacity, but our inability to write programs taking full
advantage of what we have.
2.
How Can a Computer be Programmed to Use a Language
It may be speculated that a large part of human thought consists of
manipulating words according to rules of reasoning and rules of
conjecture. From this point of view, forming a generalization consists
of admitting a new word and some rules whereby sentences
containing it imply and are implied by others. This idea has never been
very precisely formulated nor have examples been worked out.
Mühlenbein: Artificial Intelligence and Neural Networks
28
Proposal Dartmouth Summer Project on
Artificial Intelligence (1955)
3. Neuron Nets
How can a set of (hypothetical) neurons be arranged so as to form
concepts. Considerable theoretical and experimental work has been
done on this problem by Uttley, Rashevsky and his group, Farley and
Clark, Pitts and McCulloch, Minsky, Rochester and Holland, and
others. Partial results have been obtained but the problem needs more
theoretical work.
4. Theory of the Size of a Calculation
Some consideration will show that to get a measure of the efficiency
of a calculation it is necessary to have on hand a method of
measuring the complexity of calculating devices which in turn can be
done if one has a theory of the complexity of functions. Some partial
results on this problem have been obtained by Shannon, and also by
McCarthy.
Mühlenbein: Artificial Intelligence and Neural Networks
29
Proposal Dartmouth Summer Project on
Artificial Intelligence (1955)
5. Self-lmprovement
Probably a truly intelligent machine will carry out activities which may
best be described as self-improvement. Some schemes for doing this
have been proposed and are worth further study. It seems likely that
this question can be studied abstractly as well.
6. Abstractions
A number of types of ``abstraction'' can be distinctly defined and
several others less distinctly. A direct attempt to classify these and to
describe machine methods of forming abstractions from sensory and
other data would seem worthwhile.
Mühlenbein: Artificial Intelligence and Neural Networks
30
Proposal Dartmouth Summer Project on
Artificial Intelligence (1955)
7. Randomness and Creativity
A fairly attractive and yet clearly incomplete conjecture is
that the difference between creative thinking and
unimaginative competent thinking lies in the injection of a
some randomness. The randomness must be guided by
intuition to be efficient. In other words, the educated guess
or the hunch include controlled randomness in otherwise
orderly thinking.
J.McCarthy, M.L. Minsky, N. Rochester, C. Shannon
Mühlenbein: Artificial Intelligence and Neural Networks
31
Artificial Intelligence (2006)
How much has been achieved?
All topics of the Dartmouth summer school proposal are still open (with the
exception of complexity)! The ambitious goals have not been achieved,
therefore the community has investigated more and more specialized topics.
Machine learning
Neural Networks
Bayesian learning methods
Simple robots
Internet search engines
Semantic WEB
Mühlenbein: Artificial Intelligence and Neural Networks
32
Artificial Intelligence (2006)
McCarthy(2006):
Q. How far is AI from reaching human-level intelligence? When will it
happen?
A. A few people think that human-level intelligence can be achieved by
writing large numbers of programs of the kind people are now writing
and assembling vast knowledge bases of facts in the languages now
used for expressing knowledge.
However, most AI researchers believe that new
fundamental ideas are required, and therefore it cannot be
predicted when human level intelligence will be achieved.
Minsky (2003):
Q. Will we ever make machines that are as smart as ourselves?
A. Not if engineers insist on building stupid robots.
"AI has been brain-dead since the 1970s,"
Mühlenbein: Artificial Intelligence and Neural Networks
33
The Common Sense Problem
The key to natural language understanding is common sense
knowledge
Programs with common sense (McCarthy 1959)
“Dr. McCarthy’s paper belongs in the Journal of Half-Baked
Ideas…The gap between McCarthy’s general programme and its
execution seems to me so enourmous that much more has to be done
to persuade me that even the first step in bridging this gap has already
been taken.” Bar-Hillel
Despite the considerable effort, the problem remains unsolved. (IBM
Workshop 2002)
Mühlenbein: Artificial Intelligence and Neural Networks
34
Natural Language Understanding
The progress of NLU has been encouraging in the areas of
syntactic parsing, language-pair translation, semantic
analysis in narrow domains, and statistically-based
information retrieval. Now it is time to concentrate on a
deeper semantic understanding of text in larger domains.
The domain independent and complete NLU required for
the TT-like tasks will remain elusive for many years, but
incremental progress can be made, and measured within
broadly defined domains and with respect to specific
tasks. (IBM Workshop 2002, Minsky,McCarthy, et al.)
Mühlenbein: Artificial Intelligence and Neural Networks
35
Meta-Learning
Learning in neural networks is done from scratch, without
using previous knowledge.
Cascade correlation (Fahlmann):
Create a network topology by recruiting new hidden units
Knowledge-based cascade correlation (Shultz)
Recruits whole sub-networks that it has already learned in addition to
untrained hidden units from CC
First demonstrations use only two! connected problems. Method has to be
made much more complex!
Unfortunately there exists no theory about how humans learn!
Mühlenbein: Artificial Intelligence and Neural Networks
36
The Fifth Generation Project (Japan 1983-1995)
Most ambitious government project
Basis: Logic Programming (Prolog)
Goals:
User Interaction using natural language, speech, pictures
Translation English – Japanese (100.000 words, 90% correct)
Continuous human speech (50.000 words, 95% accuracy, >100
speaker)
Mühlenbein: Artificial Intelligence and Neural Networks
37
The CyC Project (Lenat 1984--)
Coding all necessary knowledge in a specialized representation
The project started in 1984 with the goal:
Assemble a comprehensive ontology and database of everyday common sense
knowledge to enable AI applications to perform human-like reasoning
Currently the knowledge base consists of

3.2 million assertions (facts and rules)

280,000 concepts

12,000 concept-interrelating predicates
A smaller version of CyC was released under OpenCyc
Success of CyC is still open. All knowledge is put into the machine, it does not
yet have the ability to acquire knowledge by reading text.
Mühlenbein: Artificial Intelligence and Neural Networks
38
The COG Project (Brooks 1995-2002?)
Humanoid intelligence requires humanoid interactions
with the real world
Essences of human intelligence

Development

Social Interaction

Embodiment

Integration
Despite the media hype at the start a disappointing project.
Mühlenbein: Artificial Intelligence and Neural Networks
39
Conclusion

There is no system in sight which comes near to general intelligence
(e.g. passes the Turing test, but have an eye on CyC!)

Essential components are missing and need to be discovered!

Lots of successes in limited domains
Research recommendations for general artificial intelligence:
Neural networks:
Re-Use of existing sub-networks, networks of NN
Common sense:
How to represent common sense knowledge?
Learning:
Higher learning techniques
Artificial Life:
Self-Reproduction and complication
Mühlenbein: Artificial Intelligence and Neural Networks
40