Contextual variable elimination with overlapping contexts

Belief networks (BNs) extracted from statistical relational learning formalisms often include variables with conditional probability distributions (CPDs) that exhibit a local structure (e.g, decision trees and noisy-or). In such cases, naively representing CPDs as tables and using a general purpose inference algorithm such as variable elimination (VE) results in redundant computation. Contextual variable elimination (CVE) partly addresses this problem by representing the BN in terms of smaller units called confactors. This leads to a more compact representation and faster inference. CVE requires that a variable's confactors are mutually-exclusive and exhaustive. We propose CVE-OC (CVE with overlapping contexts), which lifts these restrictions. This seemingly simple step shows to be powerful and allows for a more efficient encoding of confactors and a reduction of the computational cost. Experiments show that CVE-OC outperforms CVE on multiple problems.status: publishe