Evaluating abductive hypotheses using an EM algorithm on BDDs

TLDR

Abductive inference is a key AI reasoning technique for explaining observations and has recently been applied to scientific discovery, yet evaluating the best hypotheses among many logically possible ones requires systematic assessment of generated hypotheses. The authors propose an abductive inference architecture that integrates an EM algorithm operating on binary decision diagrams. The architecture uses binary decision diagrams to compress multiple hypotheses and applies the EM algorithm to select the most probable ones. The implemented system demonstrates that BDDs can compress multiple hypotheses and select the most probable ones, successfully inferring inhibition in metabolic pathways in systems biology.

Abstract

Abductive inference is an important AI reasoning technique to find explanations of observations, and has recently been applied to scientific discovery. To find best hypotheses among many logically possible hypotheses, we need to evaluate hypotheses obtained from the process of hypothesis generation. We propose an abductive inference architecture combined with an EM algorithm working on binary decision diagrams (BDDs). This work opens a way of applying BDDs to compress multiple hypotheses and to select most probable ones from them. An implemented system has been applied to inference of inhibition in metabolic pathways in the domain of systems biology.