Visualizing Abduction

Kairos. Revista de Filosofia & Ciência 3: 2011, 39-52. © Centro de Filosofia das Ciências da Universidade de Lisboa39 Visualizing Abduction Fernando Soler Toscano (Grupo de Lógica, Lenguaje e Información, Universidad de Sevilla) [email protected] 1 Introduction 1.1 What is abduction? Traditionally, Logic has focus on deduction. Its main objective has been to clarify when a given inference is valid, that is, when the conclusion is entailed by the premises. One of the pillars of this enterprise is the Aristotelian Analytics, where the syllogism is taken as the paradigm for reasoning. The modern notion of logical consequence, though is defined in a more abstract and formalised way, ratifies the privileged position of deduction as the centre of the logical universe. But there exist other kinds of inference. The philosopher C. S. Peirce (1839 - 1914), distinguishes three kinds of reasoning: deduction, induction and abduction. Peirce, contrary to the logical tradition, considers that the most interesting kind of inference is abduction. Peirce characterizes abduction in this schematic way: The surprising fact, F, is observed; but if H were true, F would be a matter of course. Hence, there is reason to suspect that H is true (CP 5.189, 1903). So abduction is the inference which formulates a hypothesis H that explains a surprising fact F. If we turn back to Aristotle, in the Prior Analytics he establishes not only the categorical syllogism, but also other inference patterns which change the order of the propositions. Those patterns, though non deductively valid, are very important in human reasoning. One of them is the apagoge. An example of Aristotle: Animals without bile live many years. But the man, the horse and the mule live many years. Hence, the man, the horse and the mule do not have bile. Fernando Soler Toscano Kairos. Revista de Filosofia & Ciência 3: 2011. Centro de Filosofia das Ciências da Universidade de Lisboa 40 The similarity between the Aristotelian apagoge and the Peircean abduction is not a matter of chance. In fact, Peirce himself admits the borrowing of concepts from Aristotle. But for Peirce, abduction is not only a kind of reasoning among others. Peirce thinks that abduction is the most interesting kind of inference because it is the only way of introducing new ideas (EP 2:216, 1903). Thanks to the Peircean works, abductive reasoning has become a central topic not only in Logic, but also in other disciplines as Linguistics, Epistemology, Artificial Intelligence and, of course, Philosophy of Science. 1.2 Is abduction the logic of discovery? Philosophy of Science is, exactly, the discipline in which the importance of abduction is more discussed. It is usual the distinction between the context of discovery and the context of justification. The former is understood as the set of processes which lead to the formulation of a new theory, while the latter refers to the methods used in science to confront the hypothesis with the empirical evidence. P. Lipton (1991) defends that scientific discovery is achieved as an inference to the best explanation, so explanatory reasoning, and hence abduction, play a central role in the context of discovery. But other authors are critical with these ideas. S. Paavola (2004) collects the arguments that are commonly given against the characterisation of abduction as a logic of (scientific) discovery. The first of them is that in the Peircean formulation of abduction – given above – the only requirement for H is that it would make F true. Authors like P. Achinstein argue that this is too permissive, because it does not exclude some improbable or wild hypotheses if they would explain F. Other criticisms insist in the idea that abduction cannot be understood as a logic of discovery because the explanatory hypothesis H is already included in the premises, because prior to infer H we need to know that H would explain F. Then, as scientific discovery introduces new ideas in science, it cannot be the result of an abductive inference. To defend abduction as a logic of discovery, S. Paavola follows a distinction borrowed by J. Hintikka from game theory. It is the distinction between definitory and strategic rules. The former settle the legal moves in a game, whereas the latter are used to decide which is the most suitable rule among all the possible. Logic has been traditionally devoted to definitory rules of the calculi and has barely paid attention to the strategic rules which are able to lead to a good proof, in a strategic sense that goes beyond classical soundness. In line with this, J. Hintikka (1998) takes from T. Kapitan four theses which sum up the main characteristics of abduction: Visualizing Abduction Kairos. Revista de Filosofia & Ciência 3: 2011. © Centro de Filosofia das Ciências da Universidade de Lisboa 41 Inferential Thesis. Abduction is, or includes, an inferential process or processes. Thesis of Purpose. The purpose of “scientific” abduction is both (i) to generate new hypotheses and (ii) to select hypotheses for further examination; hence, a central aim of scientific abduction is to “recommend a course of action”. Comprehension Thesis. Scientific abduction includes all the operations whereby theories are engendered. Autonomy Thesis. Abduction is, or embodies, reasoning that is distinct from, and irreducible to, either deduction or induction. We will come back to Kapitan theses. For now, it is enough to remark that there are reasons to accept abduction as a logic of discovery. But then, abduction must include some kind of strategic rules and satisfy the above theses which set up abduction as an autonomous inferential process, irreducible to deduction. 2 Abduction by dualizing deduction 2.1 Logic-based abduction To introduce the formal definitions concerning abduction, let us consider that  is a propositional language with the habitual connectives, and let  be defined as the classical logical consequence relation. We use capital Greek letters for sets of formulas and small Greek letters to denote formulas. Definition 1 (Abductive problem). Given   and   , we say (,)   is an abductive problem iff (if and only if):    (1)    (2) Definition 2 (Abductive solution). Given the abductive problem (,)  ,   is an abductive solution for it iff: ,     (3) ,    (4)    (5) According to definition 1, an abductive problem appears whenever there is a formula  such that neither it (1) nor its negation (2) can be derived by only the Fernando Soler Toscano Kairos. Revista de Filosofia & Ciência 3: 2011. Centro de Filosofia das Ciências da Universidade de Lisboa 42 background theory  . Then,  is an abductive solution if it extends the theory in a way such that now {}    entail  (3). Some authors demand only this condition, but following A. Aliseda (2006) we have included in definition 2 requirements (4) and (5) to ensure that  is not a trivial explanation. That is,  is consistent with the theory and it does not entail  by itself without the theory, so it is an explanation within the theory. With these strong requirements, abduction becomes an interesting non-monotonic inference very different from deduction. Additional conditions may be added. In fact, we will later concentrate on conjunctive minimal explanations, conjunctions of literals such that no proper subset of them is an abductive explanation. To mechanise the generation of abductive solutions, many calculi have been proposed. Most of them make abductive uses of deductive calculi by exploiting the equivalence of (3) with: • ,    . This is done by most on the logic-based approaches coming from Artificial Intelligence (Kakas et al. 1998). Using the resolution calculus, the clausal form of {}    is obtained and then resolution is applied. Any dead end of the resolution tree can be taken as the negation of an abductive solution. • ,,    . This is what the semantic tableaux approach does (Mayer et al., 1993). The tableaux of {}    is obtained and then a formula  which closes all the open branches is searched. In both approaches   , the negation of what is intended for explain, is in the starting point of the abductive search. So the abductive process starts by negating the empirical evidence which tries to explain. This is somehow similar to reductio ad absurdum, because the explanation  becomes an extension of  that makes impossible  . Proceeding in this way has moved logical abduction further away from the great expectations coming from Philosophy of Science. It is hardly believable that a logic of discovery proceeds by negating exactly what is trying to explain. It is not possible to take the above procedures as a logical model either of scientific or commonsense reasoning. 2.2 The  -resolution calculus Definitions 1 and 2 restrict the scope of abductive reasoning. They do not seem to be appropriate to include «all the operations whereby theories are engendered», as Kapitan's comprehension thesis requires. Anyway, though reductive, those definitions can be understood as a scale model of (scientific) explanation. They comprise the Visualizing Abduction Kairos. Revista de Filosofia & Ciência 3: 2011. © Centro de Filosofia das Ciências da Universidade de Lisboa 43 common features of any explanatory process. But to increase their interest a proper abductive calculus should be formulated. That is, a calculus which neither proceeds in an indirect way or assimilates explanation to reductio ad absurdum. That is what we have done with the  -resolution calculus. It is a reformulation of resolution which turns it an abductive calculus which generates explanations in a direct way. It works by using the equivalence between (3) and   , where  denotes the conjunction of its formulas. Now, the observation  is not negated, and we obtain directly abductive explanations, not their negations. Let us see an informal sketch of the process applied to an example of Kakas et al. (1998). Let rained , s prinkler , g rass and s hoes represent, respectively “rained last night”, “sprinkler was on”, “grass is wet” and “shoes are wet”. Then, the theory is: rained grass s prinkler grass g rass shoes We want the theory to explain that “shoes are wet”, that is: ()( )()rained grass sprinkler grass grass shoes shoes  (6) If this is a valid formula, then the theory itself explains that the shoes are wet. Otherwise, the theory needs an additional support, that is, an abductive explanation. When is (6) true? A conditional is true when the antecedent is false or the consequent is true: (( )( )( ))rained grass sprinkler grass grass shoes shoes  (7) This sets the two possible extremes of an abductive process. We can refuse the theory if the observation contradicts it, or we can add the observation to our knowledge base, if there is no possible explanation within the theory. But Error! Reference source not found. is equivalent to: ()( )()rained grass sprinkler grass grass shoes shoes      (7) Any disjointed term in (7) is a formula which supports (6), by either contradicting the theory or assuming the observation. But, is there any intermediate alternative? Of course, these are the abductive explanations. For example, both () g rass shoes and s hoes support (6). So, also g rass because, whenever it is true, one of () g rass shoes   or s hoes is too, as a trivial semantic reasoning shows. So g rass is a possible explanation. It is not the best, as we can continue the abductive process, to explain why the grass is wet. From just obtained g rass and Fernando Soler Toscano Kairos. Revista de Filosofia & Ciência 3: 2011. Centro de Filosofia das Ciências da Universidade de Lisboa 44 ()rained grass we get rained . Also, g rass and () s prinkler grass   produce s prinkler . The three obtained explanations, grass , rained and s prinkler are abductive solutions. The previous example shows that  -resolution is in fact a dual version of resolution1. In the following, we introduce the most important definitions and results concerning propositional  -resolution. Formal proofs can be found in (Soler-Toscano et al., 2006) and an extension to predicate logic in (Soler-Toscano et al., 2009). Definition 3. A  -clause  is a finite set of literals of . Given a boolean valuation v, v   iff v satisfies all the literals of  . The empty  -clause, , is universally valid. Definition 4. A  -clausal form A is a finite set of  -clauses. Given a boolean valuation v, vA iff v satisfies at least one  -clause of A . The empty  -clausal form is not satisfiable. It is possible to translate any formula to an equivalent  -clausal form by obtaining its disjunctive normal form. The following definition introduces two additional restrictions in the requirements of definition 2. We select only minimal conjunctions of literals. Definition 5 (Set of abductive  -clauses). Given the abductive problem (,)  , the set of abductive  -clauses (,)bd    contains every  -clause  such that: • The conjunction of the literals of  is an abductive solution for (,)   . • There is no    such that ,    . Definition 6 (  -resolution rule). Given two  -clauses 1{}    and 2{}   , the  -resolution rule produces their  -resolvent 12   : 12 12 {} { }      Though this rule is presented with the same format that the standard resolution one, they are different since now we are working with  -clauses. In the standard  1 Dual versions of the resolution calculus are introduced in (Eder 1991) and (Ligeza 1993). We introduced the abductive possibilities of dual resolution in (Soler-Toscano et al. 2006). Visualizing Abduction Kairos. Revista de Filosofia & Ciência 3: 2011. © Centro de Filosofia das Ciências da Universidade de Lisboa 45 resolution calculus (Robinson, 1965), every obtained clause is a logical consequence of the original set. Now, any  -clausal form which contains 1{}    and 2{}   is a logical consequence of 12   , because any valuation v which satisfies 12  satisfies  or   , so v satisfies 1{}    or 2{}    . Then v satisfies any  -clausal form with 1{}    and 2{}    . Definition 7 (Proof by  -resolution). The  -clause  is provable by  - resolution from the  -clausal form A , what we express with A   , iff there is a sequence of  -clauses such that: • Each  -clause in the sequence is either a member of A or a  -resolvent of previous  -clauses. •  is the last  -clause of the sequence. In deductive logic, soundness and completeness results are important to prove the adequacy of a calculus. Now, these properties are related to abductive adequacy of dual resolution, that is, the  -resolution process produces every abductive solution, and just them. Theorem 8 (Soundness). For every  -clausal form A and  -clause , if A  , then A . Theorem 9 (Completeness). If A is an universally valid  -clausal form, then A  . The following theorem proves the abductive completeness of the  -resolution calculus, that is, all the  -clauses that satisfy Definition 5 can be proved by  - resolution. Theorem 10 (Abductive Completeness). Let A be the  -clausal form of p  . Then A    for each satisfiable  -clause  such that: •  . • For every '  , '  . Fernando Soler Toscano Kairos. Revista de Filosofia & Ciência 3: 2011. Centro de Filosofia das Ciências da Universidade de Lisboa 46 Definition 11 (Saturation). Given the  -clausal form A , the set saturation by  -resolution from A , that we represent as A  , is the minimal set which contains every  -clause  such that •  is satisfiable. • A  . • There is not '   such that ' A  . Given a finite set of  -clauses A , A  can be obtained in a finite number of steps, by successive applications of the  -resolution rule, and eliminating subsumed2 and contradictory  -clauses. The following is the fundamental theorem of the  -resolution calculus as it provides the right way for obtaining all abductive solutions by means of a  - resolution process. Theorem 12 (Fundamental theorem). For a given abductive problem 1 ({ , , }, ) n   , if N  and O are respectively the  -clausal forms of 1 () n    and  , then      ,=bd NO NO       2.3 An abductive process By using only  -resolution operations, an abductive process can be defined, as it is implicit in Theorem 12. Given 1 ={ , , } n     and  , it follows four steps to determine whether (,)   is an abductive problem and, in the affirmative case, to produce all of its abductive solutions: Step 1: Theory Analysis. Let N  be the  -clausal form of 1 () n   . Then:  If N does not contain any satisfiable  -clause, then  is universally valid, and the process stops, because in case (,)   is an abductive problem it cannot have abductive solutions in the sense of definition 2.  2The  -clause  is subsumed by   iff   . Visualizing Abduction Kairos. Revista de Filosofia & Ciência 3: 2011. © Centro de Filosofia das Ciências da Universidade de Lisboa 47  Else, N   is obtained, and: o If N    , then  is not satisfiable, and the process stops, because (,)   cannot be an abductive problem. o Else, Step 2: Observation Analysis. Let O be the  -clausal form of  . Then:  If O does not contain any satisfiable  -clause, then  is not satisfiable, and the process stops, because (,)   cannot be an abductive problem.  Else, O  is obtained, and: o If O   , then  is universally valid, and the process stops (as  , (,)   is not an abductive problem). o Else, Step 3: Refutation Search. If for every  -clause O   there is a '  such that 'N    , then   , and the process stops because the observation refutes the theory. Else, Step 4: Explanations Search. From N   and O  , ()NO    and then ()NO    are obtained. Then,  If ()NO      , then    and the process stops.  Else, (,)   is an abductive problem. The process returns:      ,=bd NO NO       Is there a logic of abduction? This is a recurrent question with a difficult answer. Abductive reasoning has a double character. It is a product, but also a process. Moreover, the process to obtain an explanation is maybe more interesting than the explanation itself. So, the answer cannot be affirmative if there is not something like an abductive logic which integrates abductive process and product. As we argued, traditional logic-based approaches obtain abductive products which fulfil definitions 1 and 2, but their processes can hardly be considered abductive, because of the abuse of deduction and reductio ad absurdum. However,  -resolution can be considered an abductive logic. Not only its products are correct (theorem 12), but also it is possible to define an abductive process which proceeds only by  -resolution operations, as we have just shown. The steps of this process can be connected with some ideas coming from the Philosophy of Science. As we show in the next section, it is possible to visualize this process in a