2011 | OriginalPaper | Chapter
Relax, Compensate and Then Recover
Authors : Arthur Choi, Adnan Darwiche
Published in: New Frontiers in Artificial Intelligence
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present in this paper a framework of approximate probabilistic inference which is based on three simple concepts. First, our notion of an approximation is based on “relaxing” equality constraints, for the purposes of simplifying a problem so that it can be solved more readily. Second, is the concept of “compensation,” which calls for imposing weaker notions of equality to compensate for the relaxed equality constraints. Third, is the notion of “recovery,” where some of the relaxed equality constraints are incrementally recovered, based on an assessment of their impact on improving the quality of an approximation. We discuss how this framework subsumes one of the most influential algorithms in probabilistic inference: loopy belief propagation and some of its generalizations. We also introduce a new heuristic recovery method that was key to a system that successfully participated in a recent evaluation of approximate inference systems, held in UAI’10. We further discuss the relationship between this framework for approximate inference and an approach to exact inference based on symbolic reasoning.