Akinori Abe

Abstract

In the AI field, abduction is used for design, diagnosis and other tasks. This is because abduction is a sort of predictive inference. On the other hand, induction is used for classification or program generation. For example, ILP finds generalizations in examples and learns general rules from the examples and background knowledge. Recently, the question whether abduction and induction are the same or not has been discussed. Some proposed that abduction and induction were slightly the same, and the other different. In this page, regarding the role and behaviour of abductive hypotheses and those of inductive ones, I take a position that abduction and induction are different. Furthermore, recently, the integration of abduction and induction has become a hot issue. Because if they are the same, they must be discussed on the same platform, otherwise their integration will be an important issue in the future AI. In this page, first, I show the relationship between abductive hypotheses and inductive hypotheses, then I show a solution for integration of abduction and induction from the viewpoint of their relation.

Abduction and induction, which seems to be an inverse of deduction, have been recognized as important forms of reasoning with incomplete information that are appropriate for many problems in Artificial Intelligence. Abduction is usually used for design, diagnosis and other such tasks. Induction is also usually used for classification, program generation and other tasks.

Abduction involves the adoption of existing or non-existing hypotheses for a given observation explanation. Therefore, hypotheses (abductive hypotheses) are usually propositional clauses.
On the other hand, induction involves the classification or generalization of examples for explaining tendencies in observations. Therefore, the hypotheses (inductive hypotheses) become predicate clauses.
Pople mechanized abduction as the inverse of deduction [Pople 1973], and Muggleton and Buntine have introduced inverse resolution to induction [Muggleton and Buntine1988]. From the viewpoint that both inference are inverse of deduction, abduction is similar to induction. However, the main difference between abductive hypotheses and inductive hypotheses is that, in general, abductive hypotheses are propositional clauses and inductive hypotheses are predicate clauses. Intuitively, this difference comes from the above method of inference.
The following figure shows the relation between abductive hypothesis and inductive hypothesis.

Fig: A relation between abductive hypothesis and inductive hypothesis

Regarding above figure, abduction can generate propositional examples that can be used in induction in a predictive way, and induction can generate generalized rules that can be used in abduction as facts (background knowledge). Therefore, my solution to their integration is

• to generate propositional hypotheses by abduction, and to use them in induction as positive examples.
• to generate predicate rules by induction, and to use then in abduction as facts.

However, there are some problems. For example, hypotheses generated by abduction, like hypothetical reasoning systems, are thought to be positive examples in typical applications. It is very rare for hypotheses to be generated when observations are negative. Therefore, the induction process must be done with only positive examples in a simple integration.

One of the restrictions to learning rules from positive-only examples is the Subset Principle [Angluin 1980, Berwick 1986], which is a necessary condition for positive-only learning. Let L(i) be an indexed family of non-empty languages. The necessary and sufficient condition for the Subset Principle is:

1. T(i) is finite, where T(i) is a set of strings,
2. T(i) is subset of L(i),
3. for all j > i, if T(i) is subsete of L(j) then L(j) is not a proper subset of L(i).

For abduced hypotheses, the following relation can be obtained from some experiences.

In general, a hypothesis abduced from a certain observation can never be a proper subset or superset of that abduced from a similar observation.

• to generate propositional hypotheses by abduction under similar observations, and use them as positive examples in induction.
• to generate predicate rules by induction from abduced hypotheses, and then put them into the knowledge base as facts.

References:

1. Abe A.: The Relation between Abductive Hypotheses and Inductive Hypotheses, Proc. of IJCAI97 Workshop on Abduction and Induction, pp. 1--6 (1997)
2. Abe A.: Induction = Analogical Reasoning?, presented in WAL98 (1998) (in Japanese)
3. Abe A.: On The Relation between Abductive Hypotheses and Inductive Hypotheses, Abduction and Induction Essays on their Relation and Integration (Flach P. A. and Kakas A. C. eds.), pp. 169--180, Kluwer (2000)
4. Abe A., Ozaku H.I., Kuwahara N., and Kogure K.: Relation between Abductive and Inductive Nursing Risk Managements, Proc. of RM2006 (JSAI2006), pp. 121--132 (2006)
5. Abe A., Ozaku H.I., Kuwahara N., and Kogure K.: Relation between Abductive and Inductive Types of Nursing Risk Management, Post-proc. of JSAI2006 (LNAI 4834), pp. 387--400 (2007)

• [Angluin 1980]Angluin D.: Inductive Inference of Formal Languages from Positive Data', Information and Control,45, pp. 117--135 (1980).
• [Berwick 1986] Berwick R. C.: Learning From Positive-only Examples: The Subset Principle and Three Case Studies, Machine Learning, Vol. 2}, pp. 625--645, Morgan Kaufman (1986).
• [Muggleton and Buntine 1988]Muggleton S. and Buntine W.: Machine invention of first-order predicates by inverting resolution, Proc. of the 5th. Int'l Workshop on Machine Learning, pp. 339--352 (1988).
• [Pople 1973] Pople Jr. H. E.: On The Mechanization of Abductive Logic, Proc. of IJCAI73, pp. 147--152 (1973).