======================================================================
Abductive and Inductive Reasoning
(Report of the ECAI'96 workshop)
DRAFT (September 20, 1996)
Peter Flach and Antonis Kakas
1. Introduction
This workshop brought together some 20 researchers - with varying
backgrounds in Artificial Intelligence, Machine Learning, Logic
Programming and Philosophy - to discuss the relations and
differences between abductive and inductive reasoning as perceived
in each of those disciplines. As this workshop was the first in its
kind, and also because of the widely different backgrounds of the
participants, the main emphasis lay on identifying and clarifying
the main issues in the debate, rather than on trying to reach a
general consensus on the issues raised. In order to stimulate the
exchange of ideas and viewpoints, ample time was devoted to plenary
discussions, some of which continued until days after the workshop
in impromptu bi- and multilateral meetings.
More specifically, the purpose of the workshop was to
address the following two central questions: (i) how are the two
forms of reasoning different (if indeed they can be distinguished)
and (ii) how can they be integrated together in an Artificial
Intelligence enviroment? The workshop was therefore structured
around two panel discussions, one on each of these central issues,
together with an invited talk for each session. In each of the
panel discussions four of the submitted papers were briefly
presented by their authors raising problems and questions for the
subsequent discussion.
The workshop started with the presentation of the results of an
on-line questionnaire which was filled out before arriving at the
workshop, as these results provided some insight into the main
points of agreement and controversy. The majority of respondents
agreed on a definition of induction as inference of general rules
from specific observations. Another viewpoint that seemed
uncontroversial is that abduction and induction are reasoning forms
stemming from a common root. The proper definition of abduction,
and its relation with induction, appear to be more problematic.
Roughtly two-thirds of the respondents agreed with the definition
of abduction as inference to the best explanation, while one-third
favours a definition of abduction as hypothesis formation. The main
features that distinguish between abduction and induction mentioned
by the respondents are: the form of the inferred hypotheses, the
utility of the inferred hypotheses, the underlying consequence
relations, and the computational methods employed.
2. Peirce on abduction and induction
It was also felt useful to have at the begining of the worksop a
short presentation of abduction and induction as introduced and
studied by the American philosopher Charles Sanders Peirce.
Consider the Aristotelian syllogism Barbara:
All the beans from this bag are white. (rule)
These beans are from this bag. (case)
Therefore, these beans are white. (result)
By exchanging the result with the rule, one obtains a (deductively
invalid) syllogism that can be seen as an inductive generalisation:
These beans are white. (result)
These beans are from this bag. (case)
Therefore, all the beans from this bag are white. (rule)
Alternatively by exchanging the result with the case in Barbara one
obtains an abductive syllogism:
All the beans from this bag are white. (rule)
These beans are white. (result)
Therefore, these beans are from this bag. (case)
Here, the conclusion can be seen as an explanation of the result
given the rule.
Whereas Peirce's classification of reasoning forms through
syllogisms is probably well-known in Artificial Intelligence, it
appears to be much less known that Peirce abandoned his syllogistic
theory around 1900 in favour of a classification of reasoning forms
in terms of the function they perform in science. Three stages are
discerned: (1) formulating a hypothesis, (2) drawing predictions
from the hypothesis, (3) evaluating these predictions.
The first stage, coming up with an explanatory hypothesis, is what
Peirce now calls abduction. Predictions are drawn by deduction; and
assessing a hypothesis by evaluating these predictions in the real
world is what Peirce calls induction. The whole process is
triggered by some surprising observation, and Peirce formulates the
following requirement for a hypothesis to be explanatory:
The surprising fact, C, is observed;
But if A were true, C would be a matter of course,
Hence, there is reason to suspect that A is true.
The second condition is usually formalised using deduction, which
leads to the following definition of abduction: given a background
theory T, A is an abductive explanation of observation C if T
together with A deductively entails C.
It should be noted that Peirce's later definition of abduction
covers both the second and third syllogism quoted from his early
theory, since in both syllogisms the inferred hypothesis entails
one of the premisses given the other. One could say that in his
later theory Peirce concentrates on the inferential characteristics
of abduction (a sort of reversed deduction), while in his early
theory he emphasises syllogistic (i.e. syntactical)
characteristics.
Some of the workshop participants adhere to the inferential
perspective, and therefore view induction as a special case of
abduction, while others favour the syllogistic perspective, and
therefore stress the differences between abduction and induction.
These points formed a central part of the discussion in the panels
that followed.
3. Invited talk: John Josephson
\footnote{The second invited speaker Ryszard Michalski
unfortunately was not able to attend the workshop}
In his invited talk, John Josephson (Ohio State University) defined
abduction as inference to the best explanation or explanatory
inference, following a pattern like this:
D is a collection of data (facts, observations, givens),
H explains D (would, if true, explain D),
No other hypothesis explains D as well as H does.
--------------------------------------------------------
Therefore, H is probably correct.
By virtue of the third premiss, this pattern provides a
justification for concluding H from D. The Artificial Intelligence
task is then to define, in a particular context, what it means for
H to explain D, and when one explanation is better than another. As
for the first question, What is an explanation?, Josephson argued
convincingly that this is a matter of causality rather than
deductive entailment: some explanations are not deductive proofs,
and some deductive proofs are not explanations. We then arrive at a
view of abduction as an assignment of causal responsibility, the
best way we can.
As for the relation between abduction and induction, Josephson
argued that inductive generalisation is a special case of
abduction. The explanation occurs on a metalevel: while the
generalisation "all crows are black" does not explain why a
particular crow is black, it does explain why we observe a black
thing whenever we observe a crow. Furthermore, in induction we are
not just interested in any generalisation, but only in the best
one(s) (an amusing example of a bad inductive argument is "This
thumb is mine; that thumb is mine; therefore, all thumbs are
mine").
We thus see that Josephson's position corresponds more or less to
Peirce's later theory of abduction as hypothesis formation, but
extending it to include hypothesis selection as well.
4. Discussion panel 1: Distinguishing abduction and
induction: are they different and how?
Atocha Aliseda (Stanford University, USA) argued that abduction and
induction are best perceived as two points in a whole spectrum of
explanatory reasoning. Different forms of explanatory reasoning can
be obtained by instantiating three parameters: the kind of
inference involved in explaining, the kind of observation that
needs to be explained, and the kind of explanations (facts, rules
theories).
Brigitte Bessant (Universite d'Artois, France) pointed out that we
can only increase our insight in abduction and induction if we
reach a better understanding of the fundamental concepts on which
these reasoning forms are based. Among these fundamental concepts
are: the notion of generality between inductive hypotheses, the
notion of explanation, and the notion of confirmation (what does it
mean for an observation to confirm a hypothesis?).
Marc Denecker (Katholieke Universiteit Leuven, Belgium) argued that
syntactical distinctions between abductive hypotheses as ground
facts and inductive hypotheses are theories are unsatisfactory.
Instead, he proposed a semantic characterisation of the difference
between the two by means of possible world models characterisation
exploiting a more abstract distinction between general and specific
knowledge.
Erich Prem (Austrian Research Institute for AI, Vienna) provided an
analysis of the three forms of reasoning from the classical
Aristotelian viewpoint, stressing that logic is not so much a
"science of truth" or a "science of reasoning", but rather a
science of argumentation.
5. Discussion panel 2: Synthesis of abduction and
induction: can they be put thogether and how?
John Bell (University of London, UK) presented both abduction and
induction as appropriate forms of expansions of a given (partial)
knowledge base according to some form of pragmatic or
context-dependent reasoning suitably axiomatised for each case. He
also argued that non- monotonic logics (such as circumscription )
can form a basis for formalising (enumerative) induction.
Nicolas Lachiche (INRIA, France) presented a formal separation of
abduction and induction by relating each one to a different form of
completion of the given background knowledge base. This distinction
though is confined only to the specific case of confirmatory
induction.
Stathis Psillos (London School of Economics, UK) proposed a set of
desiderata that a general model of ampliative reasoning from
incomplete information should satisfy. As Josephson, Psillos argued
that abduction understood as inference to the best explanation best
satisfies these desiderata, encompassing inductive generalization
as a special case.
Fabrizio Riguzzi (Universita di Bologna, Italy) presented a
framework in which it is possible to integrate abduction and
induction as these are used in the context of Logic Programming.
This can increase the learning capabilities of Inductive Logic
Programming, as it allows a system to learn abductive logic
programs from background programs with integrity constraints.
6. Summary of discussions
It was clear from the begining that there would be many different
opinions on the issues addressed among the participants.
Furthermore, it transpired that it was not easy to agree, at the
current stage of the debate, on the list of the particular problems
and issues that should form the central points of investigation in
the overal task of analysing the relation between abduction and
induction. Two main schools of thought emerged. In the first the
emphasis is put on unifying the two into a common form (identifying
one as a special case of the other) while in the second the
emphasis is on clearly separating the two by identifying their main
characteristics. Hence the need to have two conceptualy different
forms of ampliative reasoning from incomplete information was put
under question. On the other hand, if two such forms should exist
we need to clarify the differences in their operation and also the
difference in the tasks that they can achieve. It emerged that the
utility for each form (and the subsequent computational model) may
be an important distinguishing indicator of the two. While it was
argued that the two can be conceptualy unified under abduction
(itself interpreted as inference to the best explanation) using a
meta-theory of sampling as the "causal" theory for induction, it
was pointed out that problems in AI seem to need two quite distinct
forms of reasoning for different tasks employing different
computational models.
In this AI (perhaps extreme) view we should not expect that there
are Platonic ideals of abduction and induction that we are trying
to capture but rather that abduction and induction are simply
processes that are needed for solving practical problems. However,
the discussions at this workshop seemed to suggest that many people
do try to capture Platonic ideals, but that these ideals differ
among different people. If this latter analysis is correct, then
the first and perhaps most important step is to disentangle these
different ideals, and to distinguish them terminologically. Only
then can we hope to formalise them in a satisfying manner.
Among the more specific issues that were raised during the
discussions we mention the following. An issue familiar to
philosophers of science is the extent to which explanation can be
realised through logical entailment, or should rather be treated in
terms of causation (as one participant remarked: "entailment is in
the head, while causation is in the world"). A related question
concerns the relation between explanation and prediction, as these
are fundamental concepts in abductive and inductive reasoning,
respectively. One possible position here is that explanation and
prediction are duals in the sense that they employ an opposite
chronology, as explanations refer to observations in the past while
predictions refer to future observations.
7. Concluding remarks
Perhaps the main result of this workshop was to bring to the
fore, and make people aware of, the different perspectives on
abduction and induction. The continued discussions between the
participants on the days that followed, well after the workshop had
ended, indicate the useful role that it has played in putting
together these ideas. We feel that we are now in a better position
to formulate the main issues that need to be addressed before we
can develop a coherent account of abduction and induction. We plan
to address these issues at a follow-up workshop (for instance at
IJCAI-97).
In the meantime, an electronic mailing list has been established
for continuation of the discussions started at the workshop. Those
interested in participating in this mailing list should send an
email to Peter.Flach@kub.nl.
The workshop notes contain 15 short papers and are available
on-line through the workshop's WWW-pages at
http://machtig.kub.nl:2080/ECAI96/index.html; a limited number of
harcopies is still available from Marc Denecker (email:
Marc.Denecker@cs.kuleuven.ac.be).
======================================================================