Obvious abduction
Dekang Lin · International Conference for Young Computer Scientists · 1993
Abduction, or the inference to the best explanation, is a pervasive phenomenon, both in science and in everyday life. Recently, there is a growing awareness that key tasks in many different areas of AI can be cast as abduction. This research is motivated by an apparent paradox. On the one hand, most computation models of abduction have proven to be intractable. On the other hand, humans are capable of making certain kinds of abductive inferences in a flash. To explain this paradox, we propose a theory of abduction that purports to cover the kinds of abductive inferences humans make efficiently. We use the term obvious abduction to loosely refer to these kinds of abductive inferences. The main contributions are as follows: Generality. The theory we propose is applicable across several application domains such as diagnosis, plan recognition, and natural language parsing. Such a unified theory will not only facilitate more accurate characterization and understanding of abductive reasoning, but also foster cross fertilization among different applications of abductive reasoning. Efficiency. The complexity of our abduction algorithm is polynomial in the size of the knowledge base, and exponential in the number of observations to be explained. Therefore, abduction is relatively efficient when the number of observations is small. Probabilistic justification. The knowledge representation scheme in obvious abduction allows probabilistic/statical knowledge to be represented. The inference algorithm is able to compute the probability of explanations and the most probable explanation is preferred.