IJCAI'97 Workshop, Nagoya, August, 1997

Peter A. Flach and Antonis Kakas

Introduction

Over twenty researchers participated in this IJCAI'97 workshop to dicuss the general relationship of abduction and induction. The main aim of the workshop was set out to address the issue of the relation and integration of Abduction and Induction in the context of (practical) AI problems. This focus was summarized by the following questions:

* What (if anything) distinguishes/characterizes each form of reasoning and their corresponding computational models?

* How can we characterize different prototypical AI tasks for which it is appropriate to use one of these two forms of reasoning?

* How can Abduction and Induction be integrated in the context of Artificial Intelligence problems? For example,

- How do we learn abductive theories?

- How do we use abduction in machine learning problems?

The workshop's organising committee consisted of Peter Flach (then at Tilburg University, Netherlands), Antonis Kakas (University of Cyprus), Raymond Mooney (University of Texas at Austin, USA) and Chiaki Sakama (Wakayama University, Japan). The submitted papers were reviewed and selected by a program committee additionally including Randy Goebel (University of Alberta, Canada), Katsumi Inoue (Kobe University, Japan) and John Josephson (Ohio State University, USA). The workshop assumed the same format as the the preceding ECAI'96 workshop on Abductive and Inductive Reasoning [13], devoting ample time to plenary discussions.

However, this workshop had a different emphasis from its predecessor, which indicates that a certain amount of progress has been made. Whereas the discusson at the ECAI'96 workshop revolved almost exclusively around the question whether and how abduction and induction are different forms of reasoning, the discussion at the IJCAI'97 workshop took, for most of its part, a more practical stance, concentrating on how to integrate them within an Artificial Intelligence context. Among the 12 accepted papers the program committee selected 9 for presentation at the workshop. The presentations were evenly divided over 3 sessions, addressing the issues pertaining to the integration of abduction and induction in a bottom-up fashion starting from specific practical problem of their integration and ending up with theoretical issues. These sessions are reviewed in more detail below.

Invited talk: David Poole

David Poole (Universiy of British Columbia, Canada) gave an invited talk entitled Learning, Bayesian Probability, Graphical Models, and Abduction. In his talk he tried to tie together logic and probabilistic approaches to induction in terms of belief networks and probabilistic Horn abduction. Belief (Bayesian) networks are a graphical representation of independence and provide a way to structure knowledge and to exploit the structure for computational gain. Poole pointed out the relationship between belief networks and logic-based (abductive) representations for evidential reasoning. If we want to do evidential reasoning (from effects to causes) without knowing the underlying process, there is a choice between causal modelling (learning cause * effect rules) and evidential modelling (learning effect*cause rules); we can model causally and use abduction for evidential reasoning (as do abductive diagnosis and belief networks) or model evidentially and use deduction for evidential reasoning (as in neural networks and consistency-based diagnosis). Poole overviewed the tradeoffs in this choice.

One of the most interesting aspects of Poole's talk was that it approached the issue of abduction vs.induction from both a probabilistic and a logical perspective. For instance, he argued that Bayesian conditioning (the kind of evidential reasoning done in Bayesian networks to find causes for observed effects) can be seen as abduction in probabilistic logic programs, where we try to explain the evidence conditioning on all the knowledge obtained since the knowledge base was built. He also provided a view of Bayesian learning as essentially abductive, where the abductive step is finding the right parameter values. From this viewpoint, then, the conclusion that there is no essential difference between abduction and induction seems inescapable.

In his conclusion, Poole argued that the logical and the probabilistic approaches can learn from each other. Bayesians have good methods to handle noise and avoid overfitting, a universal method for finding explanations (conditioning), and good algorithms for exploiting sparse structures. They lack however the rich representations used by the logicians.

Discussion panel 1: Abduction and Inductive Logic Programming

Chiaki Sakama (Wakayama University, Japan) discussed ways to use abduction in the process of induction[10]. If a clause can only entail an example by adopting an abductive explanation, a generalisation is obtained by dropping the abducible from the clause. Conversely, a knowledge base that entails a negative example can be specialised by weakening the causes for the entailment by disjoining them with new abnormality abducibles.

Takashi Kanai and Susumu Kunifuji (Japan Advanced Institute of Science and Technology) proposed a new integrated method of inductive generalisation and abductive reasoning [6]. Abduction is used to supplement incomplete background knowledge. The approach is a variant of FOIL [14], including an improved information gain heuristic to deal with the cost of abductive explanations.

Akihiro Yamamoto (visiting Technische Hochschule Darmstadt, Germany; now at Hoikkaido University, Japan) made a connection between inductive hypothesis formation and proof procedures for consequence finding. The proof procedure is a special case of SOL-resolution [15], extending SLD-resolution by allowing to skip the proof of selected subgoals, adding them to an abductive explanation instead. This is then related to Muggleton's inverse entailment operator [16].

The papers in this session essentially concentrated on abduction as a tool in the learning process. Immediate questions are then when this is needed or appropriate, and how it can be done. The ability to extend imperfect background knowledge abductively was generally found to be useful, as domain theories are often incomplete in practice. One can go one step further and argue that also the learned hypothesis will in general be incomplete (i.e. nonmonotonic) to some extent, in which case we are not just using but learning abductive theories. This obviates the need for learning not only classification rules but also integrity constraints, which are needed in abductive logic programming to constrain the possible explanations. Presumably having an abductive coverage relation also influences the generality structure of the hypothesis space, and may have a profound impact on the learning algorithm. Finally, there should be a reasonable trade-off between treating a wrongly covered negative example as an exception vs. revising the hypothesis.

Discussion panel 2: Abduction and Induction -- their relation and integration

Raymond Mooney (University of Texas at Austin, USA)[8] presented an overview of work on the integration of abduction and induction in machine learning systems that his group has been doing over the last years. He argued that each inference can strengthen the other and presented practical applications to support this. In particular, he showed how abductive reasoning can be useful in inductively revising existing knowledge bases by finding appropriate places of "repair'' of the knowledge base. Also he showed how inductive learning can be used to form theories for abductive reasoning.

Akinori Abe (NTT Communication Science Laboratories, Japan) [1] observed that abduction and induction can be seen as dual to each other and can be linked together when we are in a situation of similar observations. Abductive explanations for similar observations can form suitable data for inductive generalization. He presented a framework for Analogical Abductive Reasoning and showed how when this is applied to similar observations its generated hypotheses can form good examples for generalization.

Pinar Ozturk (Norwegian University of Science and Technology) was unfortunately unable to attend the workshop and present her paper [9].

The second discussion complemented in some sense the first one by considering ways in which induction could be useful in abduction. One interesting possibility would be to abductively explain several observations seperately, and then to inductively generalise them into a single explanation. In this way we are extending the capabilities of an abduction system by generating explanations that are non-ground rules. From the induction perspective we are learning rules for non-observed predicates, which points at a link with descriptive induction. An important issue that came up was whether the fact that induction typically requires many observations whereas abduction proceeds from a single or few observations is at all relevant. A number of people supported the intuition that abduction deals with incomplete knowledge regarding a single situation, whereas induction extends incomplete knowledge about a class of situations. Others objected by pointing at the difficulty of defining the notion of a situation in a non-syntactic way.

Discussion panel 3: Unifying foundations of abduction and induction

Geert-Jan Kruijff (Charles University, Czech Republic) [7] pointed out the importance of novelty in abductive reasoning and argued that this forms an important criterion for comparing the two forms of reasoning. Furthermore, he distinguished the two schools of "unification'' and "cooperation'' for the relation of abduction and induction and argued for the latter. In particular, he argued that induction can lend further credibility to abductive hypotheses.

Peter Grunwald (CWI, the Netherlands) [5] argued that probability can provide a conceptual unification for the two inferences. The difference lies in the ontology of the output of the inference: abduction generates data while induction generates hypotheses (in the statistical sense). He showed how the Minimum Description Length Principle, which is frequently used as a heuristic in inductive learning, is also appropriate for abductive reasoning, thus supporting the claim that the two forms of reasoning can be unified under probability.

Pei Wang (Indiana University, USA) was unfortunately unable to attend the workshop and present his paper [11].

One issue that came up in the third discussion was that induction seems to do a better job in assigning credibility to hypotheses. This is not just because induction is typically based on many observations, but also because inductive hypotheses allow us to make predictions about unseen cases and verify them by cross-validation. Some participants argued against this by pointing out that also abductive hypotheses can have additional consequences that can be verified. Related discussion topics were whether and how we can use induction to increase the credibility of abductive hypotheses, and whether the selection criteria really differ for abductive and inductive hypotheses.

Concluding remarks

While the preceding ECAI'96 workshop was successful in bringing people from different disciplines together and identifying some of the main general issues, this IJCAI'97 workshop approached the issue of integrating abduction and induction from a more practical AI perspective. The main conclusion to be drawn from these two workshops is that whether one perceives abduction and induction as two of a kind or as fundamentally different reasoning forms depends strongly on the domain of application and the particular AI approach employed. Hence, an appropriate question to ask is not "What is the relation between abduction and induction'', but rather "What are good reasons for perceiving them as fundamentally different or fundamentally similar?'' The successor workshop to be organised at ECAI'98 will take this more relativistic perspective as its starting point.

Another way in which this workshop differed from its predecessor is that several participants (e.g.Poole and Grunwald) approached the issue from a probabilistic perspective. The debate between logical and symbolic approaches is an important one because, as Poole pointed out, both can profit from the other's expertise. The discussions at the workshop tentatively suggested that from the probabilistic viewpoint there is no essential difference between abduction and induction. However, one must keep in mind that logical approaches tend to concentrate on hypothesis formation, while probabilistic approaches are concerned with evaluation and selection of hypotheses. It may very well be that the evaluation process is the same for abduction and induction (and indeed for any other form of reasoning), while the formation process is different in each case.

Our experience with both of these worskhops has shown that it is premature to expect universally agreed positions on these difficult issues. Nevertheless, one generally accepted conclusion of this workshop was that, if we perceive abduction and induction as separate inferences, these can be integrated in a cycle of knowledge generation governed by the `equation' B U H ? O where H is the new knowledge generated. On one side of the cycle this new knowledge then feeds in the place of O and on the other side it feeds in the place of B. Depending on where we break this cycle we identify the separate inferences of abduction and induction: abduction generating new elements for O and induction for B. This then raises the important question of how can one inference be used to justify (or affect the selection of) the hypotheses generated by the other inference.

The workshop notes contain 12 short papers and are available on-line through the workshop's WWW-pages ( http://www.cs.bris.ac.uk/~flach/IJCAI97/).

Acknowledgements

This workshop has been made possible by financial support from the European Network of Excellence CompulogNet. Writing of this report has been partially supported by the Esprit Long Term Research Project 20237 (Inductive Logic Programming 2).

References

[1] Akinori Abe, 'The relation between abductive hypotheses and inductive hypotheses', Proc. IJCAI'97 Workshop on Abduction and Induction in AI, pp. 1-6.

[2] John Bell, 'Inductive, abductive and pragmatic reasoning', IJCAI'97 Workshop on Abduction and Induction in AI, pp. 7-12.

[3] Philippe Codognet, 'Abductive reasoning: backward and forward', Proc. IJCAI'97 Workshop on Abduction and Induction in AI, pp. 13-16.

[4] Randy Goebel, 'Abduction and its relation to constrained induction', Proc. IJCAI'97 Workshop on Abduction and Induction in AI, pp. 17-18.

[5] Peter Grunwald, 'The Minimum Description Length principle and non-deductive inference', Proc. IJCAI'97 Workshop on Abduction and Induction in AI, pp. 19-23.

[6] Takashi Kanai & Susumu Kunifuji, 'Extending inductive generalisation with abduction', Proc. IJCAI'97 Workshop on Abduction and Induction in AI, pp. 25-30.

[7] Geert-Jan Kruijff, 'Concerning logics of abduction -- on integrating abduction and induction', Proc. IJCAI'97 Workshop on Abduction and Induction in AI , pp. 31-36.

[8] Raymond Mooney, 'Integrating abduction and induction in Machine Learning', Proc. IJCAI '97 Workshop on Abduction and Induction in AI, pp. 37-42.

[9] Pinar Ozturk, 'An AI criterion for an account of inference: how to realize a task', Proc. IJCAI'97 Workshop on Abduction and Induction in AI, pp. 43-48.

[10] Chiaki Sakama, 'Inductive extension of abduction', Proc. IJCAI'97 Workshop on Abduction and Induction in AI, pp. 49-52.

[11] Pei Wang, 'Return to term logic', Proc. IJCAI '97 Workshop on Abduction and Induction in AI, pp. 53-57.

[12] Akihiro Yamamoto, `Representing inductive inference with SOLD-resolution', Proc. IJCAI'97 Workshop on Abduction and Induction in AI, pp. 59-63.

[13] Peter Flach & Antonis Kakas, `Abductive and Inductive Reasoning: report of the ECAI'96 workshop', Logic Journal of the IGPL 5(5):773-778, 1997.

[14] Ross Quinlan, 'Learning logical definitions from relations', Machine Learning 5(3):239-266, 1990.

[15] Katsumi Inoue, 'Linear resolution for consequence finding', Artificial Intelligence 56:301-353, 1992.

[16] Stephen Muggleton, 'Inverse entailment and Progol', New Generation Computing 13:245-286, 1995.

Peter A. Flach

Dept. of Computer Science,

University of Bristol

Merchant Venturers Building, Woodland Road,

Bristol BS8 1UB, United Kingdom

Peter.Flach@cs.bris.ac.uk

Antonis Kakas

Dept. of Computer Science,

University of Cyprus

POBox 537, CY-1678 Nicosia, Cyprus

antonis@turing.cs.ucy.ac.cy