marquis@crin.crin.fr (Pierre MARQUIS) (05/17/89)
Could somebody tell me what is the difference between "abduction" (this last term was apparently introduced by Alan Bundy) and "induction" ? Please, send the replies to my mail address. Many thanks in advance, Pierre Marquis CRIN (Centre de Recherche en Informatique de Nancy) Campus Scientifique B.P. 239 54506 - Vandoeuvre-les-Nancy CEDEX France
sarrett@ics.uci.edu (Wendy Sarrett) (05/17/89)
"abduction" can be thought of in two ways. The first is generating explanations from a conclusion - taking a conclusion and using background information to build a "proof tree" leading too the conclusion. The second way to think about it is as the opposite of deduction i.e. if you have A -> B then you turn the arrow around and when you see B, you infer that A must be true. "induction" is the process of generalizing from lots of examples. For example, suppose you see a number of examples of ducks and they are all grey ( isa-duck -> grey) then you would conclude for all ducks, isa-duck -> grey. Note that there is also induction in mathematics where if you can show (where A is a set) (1 in A) and (n in A) -> (n+1 in A) then you can conclude for all n, n in A. Note that both "abduction" and "induction" are not "safe" forms of inference as "deduction" is. (i.e. you can't be 100% certain your inference is correct) Hope this answers your question, Wendy (sarrett@ics.uci.edu) Department of Information and Computer Science University of California, Irvine
punch@melon.cis.ohio-state.edu (William F Punch) (05/17/89)
In article <1480@crin.crin.fr> marquis@crin.crin.fr (Pierre MARQUIS) writes: >Could somebody tell me what is the difference between "abduction" (this last >term was apparently introduced by Alan Bundy) and "induction" ? > >Please, send the replies to my mail address. >Many thanks in advance, > >Pierre Marquis >CRIN (Centre de Recherche en Informatique de Nancy) >Campus Scientifique >B.P. 239 >54506 - Vandoeuvre-les-Nancy CEDEX >France The first use of the term "abduction" was by the philosopher/mathmatician Charles Sanders Peirce 1839-1914 (pronounced purse). Unfortunately I don't have my Peirce stuff handy but I use the following quote from his works in my work on abductive inference. \begin{quote} The first stating of a hypothesis and the entertaining of it, whether as a simple interrogation or with any degree of confidence, is an inferential step which I propose to call {\em abduction} [or {\em retroduction}]. ... Long before I first classed abduction as an inference it was recognized by logicians that the operation of adopting an explanatory hypothesis--which is just what abduction is--was subject to certain conditions. Namely, the hypothesis cannot be admitted even as a hypothesis, unless it be supposed that it would account for the facts or some of them. The form of inference, therefore, is this: \begin{tabular}{l} The suprising 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. \end{tabular} \end{quote} Excuse the tex-isms. Other useful places to look for discussions are Gilbert Harmon,"Inference to the Best Explanation", Philosophical Review (1965) John Josephson, "Explanation and Induction", Dissertation, Ohio State, 1982. Charniak and McDermot make mention of abduction throughout their AI book and a number of researchers do research in the area (Reggia, Josephson, Charniak, Pearl etc.) As for the difference between abduction and induction, the discussion is more complicated. I think the most concise thing to say is that abduction is a different cut on logic than induction or deduction. Abduction is driven by trying to explain a set of facts based on available hypotheses. It is often typified by method of a detective solving a crime, i.e. here are the crime clues (to be explained) and here are the facts I can use to explain them. What is the best explanation of these clues (in terms of plausiblity, consistency, whatever parameters you choose) using these facts that I can come up with. In finding the explanation, one may use deduction (deriving true conclusions from premises) or induction (populations from samples) but one is driven by the process of explanation. How's that? >>>Bill<<< p.s. An interesting, but not always easy to follow (or useful), book on the detective, Peirce, abduction etc. is The Sign of Three, Edited by Eco and Sebeok, Indiana Universtiy Press, 1983 -=- There is no such thing as a problem * >>>Bill Punch<<< without a gift for you in its hands. * punch@cis.ohio-state.edu You seek problems because you need * ...!att!osu-cis!punch their gifts. R. Bach * 2036 Neil Ave;OSU;Columbus, OH 43210
rayt@cognos.UUCP (R.) (05/19/89)
In article <14820@paris.ics.uci.edu> Wendy Sarrett writes: <>"induction" is the process of generalizing from lots of examples. For <>example, suppose you see a number of examples of ducks and they are <>all grey ( isa-duck -> grey) then you would conclude for all ducks, <>isa-duck -> grey. Note that there is also induction in mathematics <>where if you can show (where A is a set) (1 in A) and (n in A) -> (n+1 <>in A) then you can conclude for all n, n in A. <>Note that both "abduction" and "induction" are not "safe" forms of <>inference as "deduction" is. (i.e. you can't be 100% certain your <>inference is correct) Clearly the first form of induction given is not a logically valid deduction. I am surprised to here that the SECOND isn't, since MANY mathematical proofs rest upon it. Have I perhaps misunderstood your assertion? R. -- Ray Tigg | Cognos Incorporated | P.O. Box 9707 (613) 738-1338 x5013 | 3755 Riverside Dr. UUCP: rayt@cognos.uucp | Ottawa, Ontario CANADA K1G 3Z4
vdasigi@silver.wright.edu (Venu Dasigi) (05/20/89)
The following is the way Peirce himself characterized them [Peirce, 31]. Starting with 1. A --> B (if a sample is from this bag, the sample is white.) 2. A (this sample s is from this bag.) 3. B (the sample s is white.) Deduction amounts to concluding 3 from 1 and 2. Induction amounts to concluding 1 from 2 and 3. Abduction amounts to concluding 2 from 1 and 3. From this simple description, it may be observed that induction involves generalizing from specific observations, while abduction involves plausibly explaining facts or observations. While abductive and inductive "conclusions" are not necessarily valid (and often referred to as "assumptions"), Peirce notes that abduction and induction are constructive unlike deduction. Peirce, C.S., 31: Collected Papers of Charles Sanders Peirce, Vol. 2: Elements of Logic, Chapter 5, Hartsthorne, C. and P. Weiss (Eds.) Harvard University Press, Cambridge, MA, 1931. --- Venu Dasigi Venu Dasigi CSNet: vdasigi@cs.wright.edu US Mail: Dept. of CS&Eng, Wright State U, 3171 Research Blvd, Dayton, OH 45420 Dr. Venu Dasigi CSNet: vdasigi@cs.wright.edu US Mail: Dept. of CS&Eng, Wright State U, 3171 Research Blvd, Dayton, OH 45420
sarrett@ics.uci.edu (Wendy Sarrett) (05/21/89)
The AI induction I was talking about is not the same as mathematical induction. In the induction I was talking about you have lots of examples and generalize from them as opposed to saying that something is true for all N if you can prove that if it's true for the n'th it's true for the n + 1'st. Wendy (sarrett@ics.uci.edu) Department of Information and Computer Science University of California, Irvine
kavuri@cb.ecn.purdue.edu (Surya N Kavuri ) (05/24/89)
In article <6144@cognos.UUCP>, rayt@cognos.UUCP (R.) writes: > In article <14820@paris.ics.uci.edu> Wendy Sarrett writes: > > <>"induction" is the process of generalizing from lots of examples. For > <>example, suppose you see a number of examples of ducks and they are > <>all grey ( isa-duck -> grey) then you would conclude for all ducks, > Clearly the first form of induction given is not a logically valid >.... > Ray Tigg | Cognos Incorporated One should be careful to distinguish between mathematical induction and induction used otherwise(as in Physical sciences, ...) Mathematical induction is logically derivable, atleast in concept, in that it is essentially applying deduction infinitely. Abduction may be logically invalid, but under the closed world assumption it is empirically valid. SURYA KAVURI (FIAT LUX)
flach@kubix.UUCP (Peter Flach) (05/24/89)
In article <526@thor.wright.EDU> vdasigi@silver.UUCP (Venu Dasigi) recalls Peirce's beautiful characterisation of deduction, induction and abduction: >Starting with > >1. A --> B (if a sample is from this bag, the sample is white.) >2. A (this sample s is from this bag.) >3. B (the sample s is white.) > >Deduction amounts to concluding 3 from 1 and 2. >Induction amounts to concluding 1 from 2 and 3. >Abduction amounts to concluding 2 from 1 and 3. The formulation of induction given here, brings into mind a problem that has been bothering me for some time. Given premises A and B, why should I prefer the inductive conclusion A --> B over B --> A (any white sample is from this bag)? The same problem arises with the prototypical crows-argument: seeing a number of black crows might amount to the inductive conclusion, that everything that is black is a crow. Of course, this hypothesis would be falsified by the observation of a black non-crow, rendering the set of premises non-symmetrical. But it seems to me that any set of premises of the form {A(a)&B(a), A(b)&B(b), ...} give equal evidence for two possible inductive hypotheses: forall(x) A(x) --> B(x), and forall(x) B(x) --> A(x). Perhaps the introduction of a typed logic could help: if A is treated as a type, the inductive conclusion would be forall(x:A) B(x) Any comments on this? --Peter Peter A. Flach Institute for Language Technology UUCP: ..!mcvax!kubix!flach and Artificial Intelligence (ITK) BITNET: flach@htikub5 Tilburg University, PObox 90153 (+31) (13) 66 3119 5000 LE Tilburg, the Netherlands
bloch@mandrill.ucsd.edu (Steve Bloch) (05/25/89)
In article <6144@cognos.UUCP> rayt@cognos.UUCP (R.) writes: >In article <14820@paris.ics.uci.edu> Wendy Sarrett writes: ><>suppose you see a number of examples of ducks and they are ><>all grey ( isa-duck -> grey) then you would conclude for all ducks, ><>isa-duck -> grey. Note that there is also induction in mathematics... > ><>Note that both "abduction" and "induction" are not "safe" forms of ><>inference as "deduction" is. (i.e. you can't be 100% certain your ><>inference is correct) > >Clearly the first form of induction given is not a logically valid >deduction. I am surprised to here that the SECOND isn't, since MANY >mathematical proofs rest upon it. What exactly do you mean by "logically valid"? The definition in my math logic class gives a couple of really basic axioms about how logical (truth-functional) connectives and quantifiers relate to one another, and says something is "logically valid" iff it holds in all models of those axioms. Those axioms do not include mathematical induction, and in fact there are lots of models of those minimal axioms (indeed, there are lots of models of the more powerful Robinson arithmetic, which looks as though it's talking about natural numbers) in which induction does not hold. Induction happens to be true in the Platonic object we call the natural numbers, so you can draw valid conclusions about the natural numbers using it, but it's certainly not logically valid. By the way, there are different flavors of mathematical induction, which are equivalent in the unbounded logic of the natural numbers but not equivalent in computational systems with bounded resources. "The above opinions are my own. But that's just my opinion." Stephen Bloch
ellis@chips2.sri.com (Michael Ellis) (05/25/89)
> Peter Flach >> Venu Dasigi >Peirce's beautiful characterisation of deduction, induction and abduction: Peirce's thought is indeed beautiful. >>Starting with >>1. A --> B (if a sample is from this bag, the sample is white.) >>2. A (this sample s is from this bag.) >>3. B (the sample s is white.) >>Deduction amounts to concluding 3 from 1 and 2. >>Induction amounts to concluding 1 from 2 and 3. >>Abduction amounts to concluding 2 from 1 and 3. >The formulation of induction given here, brings into mind a problem that >has been bothering me for some time. Given premises A and B, why should >I prefer the inductive conclusion A --> B over B --> A (any white sample >is from this bag)? That's a good point, but it doesn't seem to show up in Peirce's original formulation, which follows: DEDUCTION: Rule- All the beans from this bag are white Case- These beans are from this bag Therefore Result- These beans are white INDUCTION: Case- These beans are from this bag Result- These beans are white Therefore Rule- All the beans from this bag are white ABDUCTION: Rule- All the beans from this bag are white Result- These beans are white Therefore Case- These beans are from this bag -michael
rjones@ics.uci.edu (Quagmire Jones) (05/26/89)
In article <287@kubix.UUCP> flach@kubix.UUCP (Peter Flach) writes: |In article <526@thor.wright.EDU> vdasigi@silver.UUCP (Venu Dasigi) recalls |Peirce's beautiful characterisation of deduction, induction and abduction: | |>Starting with |> |>1. A --> B (if a sample is from this bag, the sample is white.) |>2. A (this sample s is from this bag.) |>3. B (the sample s is white.) |> |>Deduction amounts to concluding 3 from 1 and 2. |>Induction amounts to concluding 1 from 2 and 3. |>Abduction amounts to concluding 2 from 1 and 3. | |The formulation of induction given here, brings into mind a problem that |has been bothering me for some time. Given premises A and B, why should |I prefer the inductive conclusion A --> B over B --> A (any white sample |is from this bag)? The same problem arises with the prototypical |crows-argument: seeing a number of black crows might amount to the |inductive conclusion, that everything that is black is a crow. Of |course, this hypothesis would be falsified by the observation of a black |non-crow, rendering the set of premises non-symmetrical. But it seems to |me that any set of premises of the form | {A(a)&B(a), A(b)&B(b), ...} |give equal evidence for two possible inductive hypotheses: | forall(x) A(x) --> B(x), and | forall(x) B(x) --> A(x). | |Any comments on this? In principle you are correct. Both are "valid" inductions. This is why programs that do inductive inference need to have good criteria for creating inductions, rather than creating them haphazardly. In a way, this is what AI and heuristic search are all about. Suppose, for example, that you use conditional probabilities to guide your search for "good" inductions. Going back to the crow example, if all the crows you have seen are black and all the black things you have seen are crows then P(black|crow) and P(crow|black) will both be high and you will decide that black(X) --> crow(X) and crow(X) --> black(X). I believe that this is a good induction given that particular data. What is more likely, though, is that you will have seen many objects that are black but not crows, making P(black|crow) relatively low. In this case, the statement black(X) --> crow(X) will be a very poor predictor (i.e., it will usually be wrong) and is therefore a ``bad'' induction. Remember that you can only base inductive inferences on what you have seen and know about the world. Then, you can test them by measuring their predictive ability when you see new facts and objects. -- Quagmire Jones
rayt@cognos.UUCP (R.) (05/28/89)
In article <6487@sdcsvax.UCSD.Edu> Steve Bloch writes: <>In article <6144@cognos.UUCP> I wrote: <>>... I am surprised to hear that [mathematical induction] isn't <>>[logically valid] since MANY mathematical proofs rest upon it. <>What exactly do you mean by "logically valid"? The definition in my <>math logic class gives a couple of really basic axioms about how <>logical (truth-functional) connectives and quantifiers relate to one <>another, and says something is "logically valid" iff it holds in all <>models of those axioms. Those axioms do not include mathematical <>induction, and in fact there are lots of models of those minimal <>axioms (indeed, there are lots of models of the more powerful <>Robinson arithmetic, which looks as though it's talking about natural <>numbers) in which induction does not hold. Induction happens to be <>true in the Platonic object we call the natural numbers, so you can <>draw valid conclusions about the natural numbers using it, but it's <>certainly not logically valid. I had a much more simplistic concept of "Logically Valid" in mind; to wit: Whenever all of the premises are true, the conclusion is also true. Hence, in mathematical induction, IF the initial condition AND the induction step are true, THEN the hypothesis is true, is a logically valid deduction. To achieve valid conclusions for particular instances, one must demonstrate that each of the propositions is true for those objects in question (also that they are of the appropriate type). Your's is undoubtedly the definitive 21st-Century word on this issue, however. R. P.S. I AM skeptical, though, that the SET of natural numbers could be considered to be a Platonic object (form) since I don't believe that the Greeks had a notion of the infinite. -- Ray Tigg | Cognos Incorporated | P.O. Box 9707 (613) 738-1338 x5013 | 3755 Riverside Dr. UUCP: rayt@cognos.uucp | Ottawa, Ontario CANADA K1G 3Z4
eisinger@uklirb.UUCP (Norbert Eisinger) (05/29/89)
Induction means to derive generalizations from facts, that is, statements of which the facts are instances. Of course such a generalization is not in general a logical consequence of the facts. The proof principle used in mathematics is really called COMPLETE induction. There is an indispensable axiom of the natural numbers (and similar structures) saying that a property P for which P(0) holds and also the implication forall n P(n) ==> P(n+1) holds, is a property of all natural numbers. This induction axiom cannot be expressed in first-order predicate logic. Thus, for natural numbers complete induction works because it is part of their very definition that it does. Norbert Eisinger
marquis@loria.crin.fr (Pierre MARQUIS) (06/29/89)
I have received a great deal of replies about differences between abduction and induction and I want to thank their authors for answering my question. It seems that the proposed definitions of abduction and induction are neither compatible nor convergent ones. I have tried to synthetize them and here is a (non exhaustive) inventory of the uses and denotations of abduction and induction. As Christian de Sainte Marie told me, first definitions of abduction and induction are apparently issued from Aristotle's first analytics. If I have well interpreted them in a logical sense: * induction is derivation of B -> A from C -> A and C -> B. If B has no more extension that C (that is, I presumed, B -> C ?) then this derivation is perfect induction (logically valid one). Otherwise, it is unperfect (and interesting) one. * abduction is derivation of C -> B from B -> A and C -> A so long as B -> A is certain, C -> A only probable and C -> B more probable than C -> A. Two pairs of definitions issued from Pierce's books have also been proposed to me and, strangely, they are not compatible: First ones, * induction is derivation of A -> B from fact A and observation B relative to A. * abduction is derivation of fact A from observation B and rule A -> B. Second ones, * induction is evaluation of hypotheses by experiments. * abduction is a process for hypotheses construction so long as the choice of a particular hypothesis is not based on its truth value. More recently, in AI community, abduction and induction have been both used to denote the hypotheses construction process. In others words, abductive and inductive reasoning are construction of formulae h such that Th, h |= f where f is the fact to be explained and Th the theory of domain. However, if we consider diagnosis as typical abductive reasoning and learning from examples as typical inductive reasoning, we notice that many distinctions can be made between these two kinds of reasoning: * syntactic proprieties of facts to explain: we are interessed by conjunctive and ground facts in diagnosis and by facts represented by Horn clauses in learning from ex. * syntactic proprieties of hypotheses: we are interessed by conjunctive hypotheses in diagnosis and by disjunctive hypotheses in learning from ex. * semantic proprieties of hypotheses: we are interessed by minimal hypotheses in diagnosis and by more specific hypotheses in learning from ex. * uses of hypotheses: conclusions of diagnosis need not to have any applicability outside the particular set of circumstances. On the other hand, the hypotheses have to be enough general in learning from ex. in order to contribute to knowledge acquisition. * implementation level: derivation is backward chaining in diagnosis and pattern searching in learning from ex. This distinction is available if deduction relation used is not full logical deduction. Any comments ? Pierre MARQUIS e-mail: marquis@loria.crin.fr CRIN (Centre de Recherche en Informatique de Nancy) Campus scientifique - B.P. 239 54505 Vandoeuvre les Nancy Cedex FRANCE