Practical abduction: characterization,decomposition and concurrency

Abstract

Abductive inferences seem to be ubiquitous in cognition, and cognitive agents often solve complex abduction tasks very rapidly. However, abduction characterized as ‘inference to the best explanation’ is in general computationally intractable. This paper describes three related ideas for understanding how intelligent agents might efficiently perform abduction tasks. First, we recharacterize the abduction task as inference to a confident explanation, where a confident explanation is internally consistent, parsimonious, distinctly more plausible than alternative explanations, and explains as much of the data as possible with high confidence. Second, we describe a decomposition of the task of synthesizing a confident explanation into several subtasks so that the synthesis starts from islands of relative certainty and then grows opportunistically. This decomposition helps in controlling the computational cost of accommodating interactions among explanatory hypotheses, especially incompatibility interactions. Third, we present a concurrent mechanism for synthesizing confident explanations. The mechanism exploits data and processing dependencies afforded by the decomposition of the synthesis task. The emphasis of this approach to abduction is on characterizing the constraints of the abduction task and exploiting these constraints for making abductive inferences. In describing this approach, we also clarify the precise class of abduction problems addressed by the RED-2 system, and report on some new experiments. The main result is a computational model that not only enables efficient abductive inferences but also accommodates explanatory interactions, uncertainty, and data collection.