Reasoning (plan)
Modelling the world: objects and interactions
Inferring implicit relationships
Problem solving, search for an answer, planning
Interaction with the outside world (sense & act)
Perception: the inference of objects and relationships from what sensors deliver.

Sensors deliver "arrays of numbers"

Intelligent behavior
Learning
Systems that acquire and incorporate new data
Systems that take instructions (from us)
Knowing what we are doing wrong

George Boole, Gottlob Frege, Alfred Tarski: human thought
Alan Turing, John von Neumann, Claude Shannon:
Cybernetics
Equivalence/analogy between computation and thought !!!
AI: The 40s and 50s
McCulloch and Pitts: Describe neural networks that could compute any computable function
Samuels: Checker playing machine that learned to play better.
"Dartmouth Conference" (1956) : McCarthy: coined term "Artificial Intelligence"
McCarthy:Defined LISP.
Newell and Simon: The Logic Theorist. It was able to prove most of the theorems in Russell and Whitehead's Principia Mathematica. Bounded Rationality, Logic Theorist becomes General Problem Solver.


Early Successes
Minksy: microworlds
Evan's ANALOGY solved geometric analogy problems that appear on IQ tests
Bobrow's STUDENT solved algebra world problems
Gelernter: Geometry Theorem Prover used axioms plus diagram information.
Early success with neural networks.

Buchanan and Feigenbaum: DENDRAL (1969)
MYCIN (1976): diagnose infections.
LUNAR (1973): First natural language question/answer system used in real life
Rejuvenation of neural nets

In theory, they can learn almost any function.

• In practice, it might take a millennium.
  Neural nets, while having obvious limitations, have surpassed hand-crafted systems in some key domains.
  
State-of-the-Art

Almost grand master chess (ask me about checkers).
Real-time speech recognition
Expert systems "aren't really AI anymore", but many exist

The Bad News


Heavily oversold, with ensuing backlash.
Almost every AI problem in NP-complete.
Lighthill report (1973).
Perceptrons (a kind of neural network) shown to have extremely limited representation ability (Minsky and Papert).
Some of AI seen as poorly formalized hackery or an mathematical self-indulgence..


An early intelligent system: the brain


"Intelligent" processing in the brain is carried out by neurons, mainly in the cerebral cortex.
Roughly 10**12 neurons (10**11 if you participated in frosh week) and thousands of connections _per neuron.
"Clock speed" (refractory period): 1 to 10 milliseconds
Processing involves massive parallelism and distributed representation.
5 to 7 rule
You can simultaneously conceptualize only 7 objects at once.



Comparison

Computers
Roughly 10 million transistors per chip
Parallel machines: hundreds of CPU elements, 1010 bits of RAM
Clock speed: roughly 1 nanosecond
Recall rate (for stored data) appears much faster.
Does the different hardware imply that fundamentally different approaches must be used?
Neural nets people suggest "no".
Some suggest "yes".


What is intelligence?


Stock answer: "the ability to learn and to solve problems" [Webster's]
The ability to adapt to new situations.
Your answers (paraphrased):
"The ability to laugh at humorous situations."
"Understanding how other agents behave"
"The ability to analyze and solve a problem" *
"The ability to work with abstract concepts" *
"The ability to recognize patterns"
"The ability to use new information/experience to make decisions"
"Something that defines humanity."
"The ability to solve an under-specified problem."


What does the future hold?

Many of you thought artificially intelligent systems were a long way off.
"Never"
"In some timescale comparable to the evolution of intelligence in animals"
""In 50 years"
"Not very soon"
Some of the same people said things like:
"Intelligence is the ability to solve problems that would be complex for a human being."


In Contrast...
In 1997 the computer "Deep Blue" played the human world chess champion "Garry Kasparov"
(whom some have claimed is the best chess player in history!)
DB: 200 million board positions per move.
GK: a dozen ply?
Monty Newborne at SOCS/McGill has been a pioneer in computer chess. Moderated the DB/GK match.



For those who said: "We'll never really have artificial intelligence"


Garry Kasparov:
"I could feel -- I could smell -- a new kind of intelligence across the table."


Drew McDermott


"Saying Deep Blue doesn't really think about chess is like saying an airplane doesn't really fly because it doesn't flap it's wings."


[Yale CS, quoted in NY Times, May 1997]

Another Example

Robbins' problem:
In 1932 E. V. Huntington presented a basis for Boolean algebra: commutativity, associativity and the Huntington equation.
Herbert Robbins conjectured it could be replaced by one simpler equation (the Robbins equation), leading (later) to Robbins algebras. Are all Robbins algebras Boolean algebras?
Despite work by Robbins and Huntington and Tarski and other, no solution was found.




In November 1997, a computer solves the Robbins conjecture.

First "creative" proof by computer.


Qualitative difference from prior results based more heavily of exhaustive search such as the four-color theorem:


Any planar map can be colored in using 4 colors so that no two edge-adjacent regions have the same color


Proven in 1976 with a combination of human effort and "sophisticated computing" that enumerated many different special cases.


Learning


Backgammon:
TD-gammon [Tesauro]
Plays world-champion level backgammon.
Learns suitable strategies by playing games against itself.
Plays millions of games.
Based on a neural network trained using "backpropagation": incremental changes based on observed errors.
___Method as not generalized too well to other games
Eg. Neuro-chess loses to gnu-chess most of the time, and gnu-chess isn't tops.




Important challenges


Domain specificity:
Successful systems are restricted to a narrow domains and specific tasks.
Coping with noisy data
Most successes have been in domains where the objectives and the "rules" were closely specified and formalized.
Incorporation of common sense knowledge
Does every little thing have to be encoded or derived explicitly?
Compare deep-blue to human performance re. pruning.


Domain specificity


Natural language systems work "well" only when the "domain of discourse" is restricted.
If not, things get very hard very fast.
Consider these alternative meanings of "give":
John have Pete a book. [tangible object delivered]
John gave Pete a hard time. [mode of behavior]
John gave Pete a black eye. [specific action]
John gave up.
John gave in.
John doesn't give a hoot about his courses.
I give him a week before he quits.
He'll quit next month, give or take a week.


Problem progression in Speech



"Word spotting" is good today. Key is to ignore all of an utterance except keywords of interest.
Speaker dependent continuous speech: quite good.
Speaker independent continuous speech is getting good. Works well with a limited vocabulary.
Speech understanding has proved to be very difficult, and is still not very good.
Especially is the speech is unrestricted,
Apocryphal example: "The spirit is willing but the flesh is weak" translated into Russian as "The vodka is good, but the meat is rotten."


 

 

(lecture 2 ended here)