http://www-formal.stanford.edu/jmc/

John McCarthy

2004 March 23

ROADS TO HUMAN LEVEL AI?

• Will we ever reach human level AI?
• Sure. Understanding intelligence is a difficult
• scientific problem, but lots of difficult scientific
• problems have been solved. There’s nothing
• humans can do that humans can’t make com-
• puters do. We, or our descendants, will have
• smart robot servants.
• Research should use Drosophilas, domains that
• are most informative about mechanisms of in-
• telligence, not elephants.
• Alan Turing was probably first—in 1947, but
• all the early workers in AI took human level as
• the goal. AI as an industrial technology with
• limited goals came along in the 1970s. I doubt
• that much of this research aimed at short term
• payoff is on any path to human-level AI. Indeed
• the researchers don’t claim it.
• Is there a “Moore’s law” for AI? Ray Kurzweil
• seems to say AI performance doubles every two
• years.
• No.
• When will we get human-level AI?
• Maybe 5 years. Maybe 500 years.
• Will more of the same do it? The next factor
• of 1,000 in computer speed. More axioms in
• CYC of the same kind? Bigger neural nets?
• No.
• Most likely we need fundamental new ideas.
• Moreover, a lot of the ideas now being pursued
• by hundreds of research groups are limited in
• scope by the remnants of behaviorist and posi-
• tivist philosophy—what Steven Pinker [?] calls
• the blank slate. I’ll tell you my ideas, but most
• likely they are not enough. My article Philo-
• sophical and scientific presuppositions of logi-
• cal AI, http://www.formal.stanford.edu/jmc/phil2.html
• explains what
• human-level AI needs in the way of philosophy.
• AI systems need to be based on the relation
• between appearance and the reality behind it,
• not just on appearance.
• REQUIREMENTS FOR HUMAN-LEVEL AI
• can be told facts e.g. the LCDs in a laptop
• are mounted on glass.
• knowledge of the common sense world—
• facts about dogs— 3-d flexible objects, ap-
• pearance including feel and smell, the effects
• of actions and other events.
• the agent as one among many It knows
• about other agents and their likes, goals, and It knows how its actions interact with- fears.
• those of other agents.
• independence A human-level agent must not
• be dependent on a human to revise its con-
• cepts in face of experience, new problems, or
• new information. It must be at least as capable
• as human at reasoning about its own mental
• state and mental structure.
• elaboration tolerance The agent must be able
• to take into account new information without
• having to be redesigned by a person.
• relation between appearance and reality be-
• tween 3-d objects and their 2-d projections and
• also with the sensation of touching them. Re-
• lation between the course of events and what
• we observe and do.
• reasons with ill-defined entities—the pur-
• poses of the USA, the welfare of a chicken,
• the rocks of Mount Everest.
• self-awareness The agent must regard itself
• as an object and as an agent and must be able
• to observe its own mental state.
• connects reactive and deliberated action
• e.g. finding and removing ones keys from a
• pocket.
• counterfactual reasoning “If another car had
• come over the hill when you passed, there would
• have been a head-on collision.” If the cop be-
• lieves it, you’ll be charged with reckless driving.
• These requirements are independent of whether
• the agent is logic based or an imitation of bi-
• ology, e.g. a neural net. APPROACHES TO AI
• biological—imitate human, e.g. neural nets,
• should work eventually, but they’ll have to take
• a more general approach.
• engineering—study the problems the world presents,
• presently ahead direct programming, e.g. genetic algo-- rithms,

  use logic, loftier objective

• The logic approach is the most awkward—
• except for all the others that have been tried. WHY THE LOGIC ROAD?
• If the logic road reaches human-level AI, we
• will have reached an understanding of how to
• represent the information that is available to
• achieve goals. A learning or evolutionary sys-
• tem might achieve the human-level performance
• without the understanding.
• • Leibniz, Boole and Frege all wanted to for-
• malize common sense. This requires methods
• beyond what worked to formalize mathematics—
• first of all formalizing nonmonotonic reasoning.
• • Since 1958: McCarthy, Green, Nilsson, Fikes,
• Reiter, Levesque, Bacchus, Sandewall, Hayes,
• Lifschitz, Lin, Kowalski, Minker, Perlis, Kraus,
• Costello, Parmar, Amir, Morgenstern, Thielscher,
• Doherty, Ginsberg, McIlraith . . . —and others
• I have left out.
• • Express facts about the world, including ef-
• fects of actions and other events.
• • Reason about ill-defined entities, e.g.
• welfare of chickens. Thus formulas like the- W elf are(x, Result(Kill(x), s)) < W elf are(x, s)
• are sometimes needed even though W elf are(x, s)
• is often indeterminate. LOGIC
• Describes the way people think—or rather the
• way people ought to think. [web version note:
• Psychologists have discovered many ways in
• which people often think illogically in reaching
• conclusions. However, these people will often
• accept correction when their logical errors are
• pointed out.]
• The laws of deductive thought. (Boole, de- Morgan, Frege, Peirce). First order logic is
• universal.
• Mathematical logic doesn’t cover all good rea-
• soning.
• It does cover all guaranteed correct reasoning.
• More general correct reasoning must extend
• logic to cover nonmonotonic reasoning and prob-
• ably more. Some good but nonmonotonic rea-
• soning is not guaranteed to always produce
• correct conclusions. THE COMMON SENSE INFORMATICSITUATION
• The common sense informatic situation is the
• key to human-level AI. information about myself- I have only partial
• and my surroundings. I don’t even have a final
• set of concepts.
• Objects are usually only approximate.
• What I think I know is subject to change and
• elaboration.
• There is no bound on what might be relevant.
• The barometer drosophila illustrates this com-
• mon sense physics. [Use a barometer to find- the height of a building.]

  [web version note:- The intended solution is to take the differ-

• ence d in barometer readings at the bottom
• and top of the building and use the formula
• height = dρg where ρ is the density of mercury,
• and g is the constant of gravitation. Physicists
• argued about the acceptability of the following
• common sense solutions: drop the barometer
• from the top of the building and count seconds
• to the crash, lower the barometer on a line
• and measure the length of the line, compare
• the length of the shadow of the building with
• the height of the barometer and the length
• of its shadow, and offer the barometer to the
• janitor in exchange for information about the
• height. The point is that there is no end to the
• common sense information that might allow a
• solution to the problem. That’s the common
• sense informatic situation.]
• Sometimes we (or better it) can connect a
• bounded informatic situation to an open in-
• formatic situation. Thus the schematic blocks
• world can be used to control a robot stacking
• real blocks.
• A human-level reasoner must often do non-
• monotonic reasoning. THE COMMON SENSE INFORMATICSITUATION
• The world in which common sense operates
• has the following aspects.
• 1. Situations are snapshots of part of the world.
• 2. Events occur in time creating new situa- tions. Agents’ actions are events.
• 3. Agents have purposes they attempt to re- alize.
• 4. Processes are structures of events and sit- uations.
• 5. 3-dimensional space and objects occupy re- gions. Embodied agents, e.g. people andphysical robots are objects. Objects canmove, have mass, can come apart or com-bine to make larger objects.
• 6. Knowledge of the above can only be ap- proximate.
• 7. The csis includes mathematics, i.e. ab-stract structures and their correspondencewith structures in the real world.
• 8. Common sense can come to include facts discovered by science. Examples are con-servation of mass and conservation of vol-ume of a liquid.
• 9. Scientific information and theories are imbed- ded in common sense information, and com-mon sense is needed to use science.

  BACKGROUND IDEAS

• • epistemology (what an agent can know about the world—in general and in particular sit-uations)
• • heuristics (how to use information to achieve goals)
• • declarative and procedural information
• • situations SITUATION CALCULUS
• Situation calculus is a formalism dating from
• 1964 for representing the effects of actions and
• other events.
• My current ideas are in Actions and other events
• in situation calculus - KR2002, available as
• www-formal.stanford.edu/jmc/sitcalc.html. They
• differ from those of Ray Reiter’s 2001 book
• which has, however, been extended to the pro-
• gramming language GOLOG.
• Going from frame axioms to explanation clo-
• sure axioms lost elaboration tolerance. The
• new formalism is just as concise as those based
• on explanation closure but, like systems using
• frame axioms, is additively elaboration toler-
• ant.
• The frame, qualification and ramification prob-
• lems are identified and significantly solved in
• situation calculus.
• There are extensions of situation calculus to
• concurrent and/or continuous events and ac-
• tions, but the formalisms are still not entirely
• satisfactory. CONCURRENCY AND PARALLELISM- • In time. Drosophila = Junior in Europe

  and Daddy in New york. When concur-rent activities don’t interact, the situationcalculus description of the joined activitiesneeds is the conjunction of the descriptionsof the separate activities. Then the jointtheory is a conservative extension of theseparate theories. Temporal concurrencyis partly done. See my article [?].

• • In space. A situation is analyzed as com- posed of subpositions that are analyzed sep-arately and then (if necessary) in interac-tion. Drosophilas are Go and the geometryof the Lemmings game. Spatial parallelismis hardly started. For this reason Go pro-grams are at a far lower level than chessprograms.

  INDIVIDUAL CONCEPTS AND

  PROPOSITIONS

• In ordinary language concepts are objects. So
• be it in logic.
• CanSpeakW ith(p1, p2, Dials(p1, T elephone(p2), s))
• Knows(p1, T T elephone(pp2), s) → Cank(p1, Dial(T elephone(p2), s)
• T elephone(M ike) = T elephone(M ary)
• T T elephone(M M ike) 6= T T elephone(M M ary)
• Denot(M M ike) = M ike ∧ Denot(M M ary) = M ary
• (∀pp)(Denot(T elephone(pp)) = T elephone(Denot(pp)))
• Knows(P at, T T elephone(M M ike)) ∧¬Knows(P at, T T elephone(M M ary))

  CONTEXT

• Relations among expressions evaluated in dif-
• ferent contexts.
• C0 : V alue(T hisLecture, I) = “J ohnM cCarthy′′
• C0 : Ist(U SLegalHistory, Occupation(Holmes) = J udge)
• C0 : Ist(U SLiteraryHistory, Occupation(Holmes) = P oet)
• C0 : F ather(V alue(U SLegalHistory, Holmes)) =
• V alue(U SLiteraryHistory, Holmes)
• V alue(CAF db, P rice(GE610)) = V alue(CGEdb, P rice(GE610)) +V alue(CGEdb, P rice(Spares(GE610)))- Can transcend outermost context, permitting
• introspection.
• Here we use contexts as objects in a logical
• theory, which requires an extension to logic.
• The approach hasn’t been popular. Too bad. NONMONOTONIC

  REASONING—CIRCUMSCRIPTION

• P ≤ P ′ ≡ (∀x . . . z)(P (x . . . z) → P ′(x . . . z))
• P < P ′ ≡ P ≤ P ′ ∧ ¬(P ≡ A′)
• Circm{E; C; P ; Z} ≡ E(P, Z) ∧ (∀P ′ Z′)(E(P ′, Z′) → ¬(P ′ < P ))
• In Circm{E; C; P ; Z}, E is the axiom, C is a set
• of entities held constant, P is the predicate to
• be minimized, and Z represents predicates that
• can be varied in minimizing P . ¬Ab(Aspect1(x)) → ¬f lies(x)

  bird(x) → Ab(Aspect1(x))

  bird(x) ∧ ¬Ab(Aspect2(x)) → f lies(x)

  penguin(x) → Ab(Aspect2(x))

  penguin(x) ∧ ¬Ab(Aspect3(x)) → ¬f lies(x)- Let E be the conjunction of the above sen-

• tences.
• Then Circum(E; {bird, penguin}; Ab; f lies) im-
• plies
• f lies(x) ≡ bird(x) ∧ ¬penguin(x), i.e. the things
• that fly are those birds that are not penguins.
• The frame, qualification and ramification prob-
• lems are well known in knowledge representa-
• tion, and various solutions have been offered.
• Conjecture: Simple abnormality theories as de-
• scribed in [?] aren’t enough.
• (No matter what the language).
• Inference to a bounded model. SOME USES OF NONMONOTONIC

  REASONING

• 1. As a communication convention. A bird
• may be presumed to fly.
• 2. As a database convention. Flights not listed
• don’t exist.
• 3. As a rule of conjecture. Only the known
• tools are available.
• 4. As a representation of a policy. The meet-
• ing is on Wednesday unless otherwise specified.
• 5. As a streamlined expression of probabilis-
• tic information when probabilities are near 0
• or near 1. Ignore the risk of being struck by- lightning.

  ELABORATION TOLERANCE

• Drosophila = Missionaries and Cannibals: The
• smallest missionary cannot be alone with the
• largest cannibal. One of the missionaries is Je-
• sus Christ who can walk on water. The prob-
• ability that the river is too rough is 0.1.
• Additive elaboration tolerance. Just add sen-
• tences.
• See www.formal.stanford.edu/jmc/elaboration.html.
• Ambiguity tolerance
• Drosophila = Law against conspiring to assault
• a federal official. APPROXIMATE CONCEPTS AND

  THEORIES

• Reliable logical structures on quicksand seman-
• tic foundation
• Drosophila = {Mount Everest, welfare of a
• chicken}
• No truth value to many basic propositions.
• Which rocks belong to the mountain?
• Definite truth value to some compound propo-
• sitions whose base concepts are squishy. Did
• Mallory and Irvine reach the top of Everest in
• 1924? HEURISTICS
• Domain dependent heuristics for logical rea-
• soning
• Declarative expression of heuristics.
• Wanted: General theory of special tricks
• Goal: Programs that do no more search than
• humans do. On the 15 puzzle, Tom Costello
• and I got close. Shaul Markovitch got closer. LEARNING AND DISCOVERY
• Learning - what can be learned is limited by
• what can be represented.
• Drosophila = chess
• Creative solutions to problems.
• Drosophila = mutilated checkerboard
• Declarative information about heuristics.
• Domain dependent reasoning strategies
• Drosophilas = {geometry, blocks world}
• Strategy in 3-d world.
• Drosophila = Lemmings
• Learning classifications is a very limited kind
• of learning problem.
• Learn about reality from appearance, e.g 3-d
• reality from 2-d appearance. See
• www-formal.stanford.edu/jmc/appearance.html
• for a relevant puzzle.
• Learn new concepts. Stephen Muggleton’s in-
• ductive logic programming is a good start.
• ALL APPROACHES TO AI FACE SIMILAR PROBLEMS
• Succeeding in the common sense informatic
• situation requires elaboration tolerance.
• It must infer reality from appearance.
• Living with approximate concepts is essential
• Transcending outermost context, introspection.
• Nonmonotonic reasoning QUESTIONS
• What can humans do that humans can’t make
• computers do?
• What is built into newborn babies that we haven’t
• managed to build into computer programs?
• Semi-permanent 3-d flexible objects.
• Is there a general theory of heuristics?
• First order logic is universal. Is there a general
• first order language? Is set theory universal
• enough?
• What must be built in before an AI system can
• learn from books and by questioning people? CAN WE MAKE A PLAN FOR HUMANLEVEL AI?
• • Study relation between appearance and real-
• ity.
• www-formal.stanford.edu/jmc/appearance.html
• • Extend sitcalc to full concurrency and con-
• tinuous processes.
• • Extend sitcalc to include strategies
• • Mental sitcalc
• • Reasoning within and about contexts, tran-
• scending contexts.
• • Concepts as objects—as an elaboration of a
• theory without concepts. Denot(T T elephone(M M ike)) =
• T elephone(M ike).
• • Uncertainty with and without numerical probabilities—
• probability of a proposition as an elaboration.
• • Heavy duty axiomatic set theory. ZF with
• abbreviated ways of defining sets. Programs
• will need to invent the E{x . . .} used in the
• comprehension set former {x, . . . |E{x, . . .}}.
• • Reasoning program controllable by declara-
• tively expressed heuristics. Instead of domain- dependent or reasoning style dependent logics
• use general logic with set theory controlled by
• domain dependent advice to a general reason-
• ing program.
• • All this will be difficult and needs someone
• young, smart, knowledgeable, and independent
• of the fashions in AI.
• McC95
• John McCarthy. Applications of Circumscrip-
• tion to Formalizing Common Sense Knowledge
• http://www-formal.stanford.edu/jmc/applications.html.
• Artificial Intelligence, 28:89–116, 1986. Reprinted
• in [?].
• John McCarthy. Situation Calculus with Con-
• current Events and Narrative http://www-formal.stanford.edu/jmc/narrative.html.
• 1995. Web only, partly superseded by [?].
• Steven Pinker. The Blank Slate: the modern
• denial of human nature. Viking, 2002.