Generalized Constraint-Based Inference
By Leif Chang
Constraint-Based Inference (CBI) is a unified framework that subsumes many
practical problems in different research communities. These problems include
probabilistic inference, decision-making under uncertainty, constraint
satisfaction, propositional satisfiability, decoding problems, and possibility
inference. Recently, researchers have presented various unified representation
and algorithmic frameworks for CBI problems in their fields, based on the
increasing awareness that these problems share common features in representation
and essentially identical inference approaches. As the first contribution of
this paper, we explicitly use the semiring concept to generalize various CBI
problems into a single formal representation framework that provides a broader
coverage of the problem space than previous work. Second, the proposed semiring-based
unified framework is also a single formal algorithmic framework that provides a
broader coverage of both exact and approximate inference algorithms, including
variable elimination, junction tree, and loopy message propagation methods.
Third, we discuss inference algorithm design and complexity issues. Finally, we
present a software toolkit named the Generalized Constraint-Based Inference
Toolkit in Java (GCBIJ) as the last contribution of this paper. GCBIJ is the
first concrete software toolkit that implements the abstract semiring approach
to unify the CBI problem representations and the inference algorithms. The
discussion and the experimental results based on GCBIJ show that the generalized
CBI framework is a useful tool for both research and applications.