=Paper=
{{Paper
|id=None
|storemode=property
|title=Dual Aspects of Abduction and Induction
|pdfUrl=https://ceur-ws.org/Vol-1100/paper11.pdf
|volume=Vol-1100
|dblpUrl=https://dblp.org/rec/conf/aiia/Zelazek13
}}
==Dual Aspects of Abduction and Induction==
https://ceur-ws.org/Vol-1100/paper11.pdf
Dual Aspects of Abduction and Induction
Flavio Zelazek
Department of Philosophy, Sapienza University of Rome, Italy
flavio.zelazek@gmail.com
Abstract. A new characterization of abduction and induction is pro-
posed, which is based on the idea that the various aspects of the two
kinds of inference rest on the essential features of increment of (so to
speak, extensionalized) comprehension and, respectively, of extension of
the terms involved. These two essential features are in a reciprocal rela-
tion of duality, whence the highlighting of the dual aspects of abduction
and induction. Remarkably, the increment of comprehension and of ex-
tension are dual ways to realize, in the limit, a `deductivization' of ab-
duction and induction in a similar way as the Closed World Assumption
does in the case of the latter.
Keywords: abduction, induction, extension, comprehension, duality, closed
world assumption.
1 The Uses of Abduction
The analysis of abduction is a topic of very much interest, albeit not a central one,
in the elds of philosophy of science and AI. The former often relates abduction
to reasoning from eects to cause and to Inference to the Best Explanation (IBE),
while the latter exploits it in Abductive Logic Programming (ALP) [11], closely
related to Inductive Logic Programming (ILP) [14], which in turn is a powerful
tool for Machine Learning.
In the rich sub eld of logic programming, the formal characterization of ab-
duction is of particular interest, especially in relation with induction (here the
fundamental reference is [5]) and deduction. Typically, abduction is explicated
in terms of default reasoning and Negation as Failure (NAF), which in turn is re-
lated to the completion technique, which allows talking of abduction in deductive
terms.
1
Now, 20 years after the birth of ALP, there is an impressive proliferation of
new frameworks and techniques meant to represent abductive reasoning, so that
it seems by now really hard to have precise and yet unifying characterizations of
it like those just mentioned. Maybe what is missing is just a simple and general
yet rigorous enough logical characterization of abduction which encloses the
common characters it has across so many diverse approaches and techniques.
2
1
For the relevant references see e.g. [7].
2
In fact the need for unifying frameworks, typical of philosophy and science, is growing
also in the elds of computer science and AI: consider, for example, the recent works
by Kowalski and Sadri, like [12].
As is well known, the rst logical analysis of abduction (and the term itself )
has been given in the works of Charles Sanders Peirce. His vast speculation on
abduction has been subdivided by Fann [4] into two periods: an early one, from
1859 to 1890, and a later one from 1891 to 1914; to these periods correspond,
by and large, the two dierent conceptions of abduction which have been called
by Flach and Kakas [6] the syllogistic theory and the inferential theory.
What has remained of the rst theory, mainly in the AI and logic program-
ming literature, is the triad of examples relating deduction, induction, and ab-
duction (2.623),
3 of which the pertinent one is the following:
(Rule) All the beans from this bag are white
(Result) These beans are white
(Case) These beans are from this bag
( Abd1 )
On the other hand, the later peircean theory of abduction is summarized
by this notorious reasoning schema (5.189), to which a massive literature is
dedicated, especially in the eld of philosophy of science:
The surprising fact, C , is observed;
But if A were true, C would be a matter of course, (Abd2 )
Hence, there is reason to suspect that A is true.
The would be a matter of course implies something like the fact that A is a
cause or at any rate an explanation of C (as this is what generally accounts
for C being `naturally' expected, given A),
4 whence the matching of abduction
with (backward) causal reasoning and/or IBE.
Despite the formal clarity of ( Abd1 ) and the informal intent of (Abd2 ), often
abduction is represented by this inference schema:
M →P
P
Abd0
M
Now, presumably the `rule' ( Abd0 ) is simply to be conceived as a forgetful
interpretation of ( Abd2 ), and of this other schema (extracted from (Abd1 )),
which is at the heart of ALP:
3
I'm using the standard quotation format for the Collected Papers of C. S. Peirce [9]:
(.).
4
Actually, the quoted expression could also be construed as the weakest claim that
C is positively (even if spuriously) correlated to A; but this is usually not the case.
∀x (M (x) → P (x))
P (s1 )
AbdQ
M (s1 )
But the fact is that the schema ( Abd0 ) `forgets too much': if we want to
characterize abduction as IBE, we must operate in a causal/explanatory frame-
work; while if we want to talk of abduction in a purely logical way, e.g. when
doing logic programming, we must at least use predicate logic. A formulation
in terms of mere propositional logic like that of ( Abd0 ), besides being vaguely
evocative, is not su cient for neither approach; and, what is worst, it leaves the
door open to easy criticisms against abduction in general (see note 8 below).
On the other side, it must be said that, often, many useful logical features
of reasoning are captured in terms of pure propositional logic; so the problem
is: can we characterize abduction within propositional logic in a less trivial and
more illuminating way than ( Abd0 ) does? And can we extract from such a
characterization any new (or, up to now, largely overlooked) feature of abductive
reasoning? The answer to both questions is I hope positive, as will be shown
in the next section.
2 Abduction as the Dual of Induction
The analysis of abduction and of its relation of duality with induction which
is to follow is based on, and is an explication of, the works belonging to the
early logical speculation of Peirce, which are framed in a syllogistic (and, later,
probabilistic) setting.
Other works insisting on the duality between abduction and induction are [15],
based on the early peircean theory like the present one; [1], which exploits the
notion of preferential entailment and instead considers the later peircean concep-
tion of abduction; [2], which remarks that abduction and induction are related
in the same way extension and intension are.
5
I shall represent induction and abduction by the following inference schemata,
which are dual to each other:
5
Few remarks about the importance of the duality relation. It is a key concept in
category theory; in fact, category theory itself seems to have been born to solve a
duality problem, with Mac Lane's 1950 article Duality in Groups (cf. [3]). Moreover,
duality is an `hidden interest' of philosophers: think of Hempel and Oppenheim's
attempt to de ne the systematic power (`content') of a theory as the notion which is
dual to the one of logical probability (`range') in [10]. Finally, the concept of duality
is a central one in recent logical research on proof theory and the foundations of
theoretical computer science: see [8].
S1 ∨ · · · ∨ Sj → M M → P1 ∧ · · · ∧ Pk
S1 → P S → P1
. .
. .
. .
Sj → P
Ind ∗ S → Pk
Abd ∗
M →P S→M
These de nitions arise as a way to connect the schema ( Abd1 ) above (p. 2),
and the analogous schema for induction, to the earliest characterization of in-
ducton and abduction given by Peirce (in (2.511), and also in (2.424425)), in
which multiple subject/predicate classes are explicitly inserted.
The natural means (suggested, more or less in clear terms, by Peirce himself
in (2.461516)) to move from a multiplicity of objects to a single class is simply to
take their union or intersection,
6 if they are subjects or, respectively, predicates.
The enlargement of a class by adding members to an union, and the shrinkage
of a class by adding members to an intersection, are respectively the extensional
counterparts of the concepts of breadth and depth of a term (i.e. a class), which
Peirce investigates thoroughly in (2.407 .). They are akin to the concepts of
extension and comprehension,
7 and to the aforementioned notions of range and
content examined in the early hempelian analysis of scienti c explanation (see
note 5).
The central aspect in the present approach is the idea that induction and
abduction are essentially based upon, respectively, the enlargement and the
shrinkage of classes, all the other features being derived from these. Console
and Saitta [2] make a similar claim, identifying as the logical processes govern-
ing induction and abduction those of generalization and specialization, which
are at the base of the theory of Machine Learning.
To see how the inductive and abductive inferences work in this conceptual
framework, consider Fig. 1 and Fig. 2, which illustrate what happens in (the
set-theoretical versions of ) the inferences ( Ind∗ ) and (Abd∗ ) with j = k = 2.
Brie y, an inductive inference is the more con rmed/plausible the more subjects
it examines, up to the ideal point when the subject class has been enlarged so
much that it coincides with the middle term class; at which point all the tests
Sj → P are passed, so that M \ P = ∅ (the shaded area, i.e. the potential
6
I take for granted the shifting from predicate logic to set notation and then to
propositional logic, in the case of categorical propositions of the form A (universal
aermative); so that ∀x (A(x) → B(x)) becomes A ⊆ B , which in turn can be
written as A → B . Taking →, ¬, ∨, ∧ instead of ⊆, \, ∪, ∩ (as indeed happens in the
schemata ( Ind∗
) and ( Abd
∗
)) is really a way to let propositional logic speak for the
relevant logical features of objects otherwise represented by predicate logic.
7
Things are actually more complicated: Peirce makes a distinction between essential,
substantial and informed breadth and depth, each subjected to dierent rules; and
he is critical precisely of the careless attening of these concepts on those of extension
and comprehension.
S
M S1 S2 P
Fig. 1. Induction
P1 S M P2
P
Fig. 2. Abduction
counterexample space for the conclusion, is empty), and the arrow in the rst
premise of ( Ind∗ ) can be inverted, so that a deduction is obtained.
Dually, an abductive inference is the more con rmed/plausible the more prop-
erties of subjects it considers, up to the ideal point when the predicate class has
been shrunk so much that it coincides with the middle term class. That being
the case, all the tests S → Pk are passed, so that S \ M = ∅ (again, the shaded
area, i.e. the potential counterexample space, is empty), and the arrow in the
rst premise of ( Abd∗ ) can be inverted, so as to get a deduction.
This reversal of arrows in induction and abduction is linked with completion
or circumscription techniques, so basically with the Closed World Assumption.
On this point an interesting analysis has been made by Lachiche [13].
3 Conclusions and Further Research
The present view of induction and abduction is an `incremental' one: we increase
the number of tests up to the limiting point in which all of the relevant sub-
jects (induction) or all of the relevant properties (abduction) have been tested;
even before reaching this ideal point, we get more and more con dent about
our conclusion as we proceed further.
8 In the opposite direction, we have as
limiting/trivial cases, respectively, single-case induction and ( AbdQ ), as in both
these inference forms only a single test is taken into consideration.
In this work I have considered implications (i.e. inclusions) as categorical, and
tests as yes/no questions; it may be interesting, then, to extend this approach in
order to capture probabilistic features as well. This in turn is needed if one wants
to de ne some measure of con rmation/plausibility and, possibly, to implement
the new inference gures in a logic programming system.
References
1. Britz, K., Heidema, J., Labuschagne, W.: Entailment, duality, and the forms of
reasoning. Tech. Rep. OUCS-2007-01, Department of Computer Science, University
of Otago, Otago, New Zealand (2007), available at: http://www.cs.otago.ac.nz/
research/publications/OUCS-2007-01.pdf
2. Console, L., Saitta, L.: On the relations between abductive and inductive explana-
tion. In: Flach and Kakas [5]
3. Corry, L.: Modern algebra and the rise of mathematical structures. Birkhauser,
Basel, 2 edn. (2004)
4. Fann, K.T.: Peirce's theory of abduction. Martin Nijho, The Hague (1970)
5. Flach, P.A., Kakas, A.C. (eds.): Abdcution and induction. Essays on their rela-
tion and integration, Applied logic series, vol. 18. Kluwer Academic Publishers,
Dordrecht (2000)
6. Flach, P.A., Kakas, A.C.: Abductive and inductive reasoning: background and
issues. [5]
7. Gabbay, D.M., Hogger, C.J., Robinson, J.A. (eds.): Handbook of Logic in Arti-
cial Intelligence and Logic Programming. Vol. 3: Nonmonotonic Reasoning and
Uncertain Reasoning. Clarendon Press, Oxford (1994)
8. Girard, J.Y.: The Blind Spot. European Mathematical Society, Zürich (2011)
9. Hartshorne, C., Weiss, P. (eds.): Collected papers of Charles Sanders Peirce. The
Belknap Press of Harvard University Press, Cambridge, Massachussets (1960)
10. Hempel, C.G., Oppenheim, P.: Studies in the logic of explanation. In:
Hempel, C.G.: Aspects of scienti c explanation and other essays in the philosophy
of science, pp. 245295. The Free Press, New York (1965)
11. Kakas, A.C., Kowalski, R.A., Toni, F.: Abductive Logic Programming. Journal of
Logic and Computation 2(6), 719770 (1992)
12. Kowalski, R.A., Sadri, F.: Towards a logic-based unifying framework for computing
(2013), preprint available at: http://arxiv.org/pdf/1301.6905
13. Lachiche, N.: Abduction and induction from a non-monotonic reasoning perspec-
tive. In: Flach and Kakas [5]
14. Muggleton, S.: Inductive logic programming. Academic Press, London (1992)
15. Wang, P.: From Inheritance Relation to Non-Axiomatic Logic. International Jour-
nal of Approximate Reasoning 7, 174 (1994)
8
Thus it can be avoided, or at least minimized, the problem of ( Abd ) commit-
0
ting the fallacy of a rming the consequent : an eect can have, e.g., two competing
causes/explanations; but it is improbable that for a conjunction of eects (i.e. for a
more detailed description of the eect in question or, in the limit, for its `maxi-
mally detailed', or `complete', description) both of the same two explanations remain
available. I wish to thank a reviewer for having pointed this matter.