AI and Logic: Induction, Deduction, Abduction (was Re: Penrose)

From: Wayne Hayes (wayne@cs.toronto.edu)
Date: Wed Nov 12 1997 - 09:13:51 MST


John K Clark writes:
>Minds are problem solvers and I don't think non-algorithmic problem solving
>is necessarily mystical. I doubt if we use axioms like "if A and B then C"
>very much, more important are billions of heuristics like "if A and B then
>usually something close to C".

A very interesting point was recently made to me by a friend who's doing
a Ph.D. in Artificial Intelligence. Recall the first formal example of
deduction that our species is alleged to have made: Socrates saying,
"All men are mortal. Socrates is a man. Therefore Socrates is mortal."
Putting it more visually,

    All men are mortal (A)
    Socrates is a man (B)
    ------------------
    Socrates is mortal (C)

If we are given A and B, the process of concluding C is called
"deduction". There's another form of logic we are taught, called
induction. (Not mathematical induction; *logical* induction.) In that
case, we are given many examples of B and C, and we hypothesize that A
must be true. In other words, given many specific examples, we induce
a "universal law", in this case, we hypothesize that since Socrates is
mortal, Plato is mortal, both their parents were mortal, and in fact
nobody is ever observed to live forever, we hypothesize that *all* men
are mortal. That is logical induction: synthesizing a universal rule
based on many similar observations. It is interesting to note that
logical induction is what revolutionary scientists do when they create
a new theory. They *create* what they hope are universal laws, that
are designed specifically to reproduce observations.

However, there is a third form of logic that apparently was never given
a name until recently. What if we are given A and C? Namely, "All men
are mortal. Socrates is mortal." In this case, we are given a universal
law, and a conclusion, and we are left to hypothesize a possible
explanation that can produce the observations, given the "universal
laws". Can we conclude that Socrates is a man? NO! This is because
there are other universal laws. Not only are all men mortal, but,
for example all horses are mortal:

    All horses are mortal. (A')
    Socrates is a horse. (B')
    ----------------------
    Socrates is mortal. (C) (not C', just C)

Just because all men are mortal, and Socrates is mortal, does not imply
that Socrates is a man. Socrates may be a horse! The process of taking
a set of universal laws like A, A', etc, and a single observation like C,
and creating a hyothesis like B or B' has been dubbed "abduction", with
the root "abduce", by the AI people. And the AI folks note that
almost ALL logic perfomed in the everyday living of humans is
abduction! We have in our minds a picture of how the world works; we
see observations, and then we *abduce* a sequence of circumstances,
based on our model of the world, that could produce the observations.
The abduced sequence of events is rarely a unique solution, and we
spend our time finding the *best* sequence of events that fits the
observations.

For example, you walk outside, and the ground is wet. What can you
conclude? Well, it may have rained recently. Or perhaps water main
broke and flooded the area. Or a street sweeping machine went haywire
and sprayed too much water. There are several possible explanations
you could abduce. To find out which one is correct, you may have to
look around some more, and use your knowledge of how the world works
to create a "story" that fits the facts, and your knowledge of the
world. It is interesting to note that this is the kind of logic that
Sherlock Holmes used; Sir Arthur Conan Doyle incorrectly labeled it
"deduction" in his stories.

I'll give one more example of abduction. Last winter I was cross-
country skiing north or Toronto. One of the ski trails had foot
prints in the middle of it. Now, it is extremely bad ettiquette
to walk on a ski trails, because it ruins the smoothness of the trail
and makes it hard to ski properly, and I was seriously annoyed that
somebody would be walking on the ski trails. "What kind of asshole
would go for a walk on the trails in February?", I fumed. I had
hypothesized that some inconsiderate or clueless wag was going for
a pleasant walk on the trails, probably without realizing his
faus pas. About 10 minutes later the footprints ended, and at that
place there was a person-shaped dent in the snow, many ski-prints and
footprints facing various directions, and a little ways away was half
a broken ski. "Ahhhhhhhhh!", I thought. Obviously, my previous
abduction was incorrect. The footprints were from a skier who
had fallen down and broken a ski, and had to walk back.

I have found it very interesting to observe myself in my day-to-day
life and notice how often we use abduction without even realizing
it, and without even having a name for it until recently. So, one
of the current challenges in AI is to build machines that can abduce
as well as we do.



This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:45:07 MST