Mark Chavira

AIJ Journal 2008 Journal Article

On probabilistic inference by weighted model counting

• Mark Chavira
• Adnan Darwiche

A recent and effective approach to probabilistic inference calls for reducing the problem to one of weighted model counting (WMC) on a propositional knowledge base. Specifically, the approach calls for encoding the probabilistic model, typically a Bayesian network, as a propositional knowledge base in conjunctive normal form (CNF) with weights associated to each model according to the network parameters. Given this CNF, computing the probability of some evidence becomes a matter of summing the weights of all CNF models consistent with the evidence. A number of variations on this approach have appeared in the literature recently, that vary across three orthogonal dimensions. The first dimension concerns the specific encoding used to convert a Bayesian network into a CNF. The second dimensions relates to whether weighted model counting is performed using a search algorithm on the CNF, or by compiling the CNF into a structure that renders WMC a polytime operation in the size of the compiled structure. The third dimension deals with the specific properties of network parameters (local structure) which are captured in the CNF encoding. In this paper, we discuss recent work in this area across the above three dimensions, and demonstrate empirically its practical importance in significantly expanding the reach of exact probabilistic inference. We restrict our discussion to exact inference and model counting, even though other proposals have been extended for approximate inference and approximate model counting.

IJCAI Conference 2007 Conference Paper

• Mark Chavira
• Adnan Darwiche

Compiling Bayesian networks has proven an effective approach for inference that can utilize both global and local network structure. In this paper, we define a new method of compiling based on variable elimination (VE) and Algebraic Decision Diagrams (ADDs). The approach is important for the following reasons. First, it exploits local structure much more effectively than previous techniques based on VE. Second, the approach allows any of the many VE variants to compute answers to multiple queries simultaneously. Third, the approach makes a large body of research into more structured representations of factors relevant in many more circumstances than it has been previously. Finally, experimental results demonstrate that VE can exploit local structure as effectively as state--of--the--art algorithms based on conditioning on the networks considered, and can sometimes lead to much faster compilation times.

UAI Conference 2007 Conference Paper

Node Splitting: A Scheme for Generating Upper Bounds in Bayesian Networks

• Arthur Choi
• Mark Chavira
• Adnan Darwiche

We formulate in this paper the mini-bucket algorithm for approximate inference in terms of exact inference on an approximate model produced by splitting nodes in a Bayesian network. The new formulation leads to a number of theoretical and practical implications. First, we show that branch-and-bound search algorithms that use mini-bucket bounds may operate in a drastically reduced search space. Second, we show that the proposed formulation inspires new mini-bucket heuristics and allows us to analyze existing heuristics from a new perspective. Finally, we show that this new formulation allows mini-bucket approximations to benefit from recent advances in exact inference, allowing one to significantly increase the reach of these approximations.

SAT Conference 2006 Conference Paper

Encoding CNFs to Empower Component Analysis

• Mark Chavira
• Adnan Darwiche

Abstract Recent algorithms for model counting and compilation work by decomposing a CNF into syntactically independent components through variable splitting, and then solving the components recursively and independently. In this paper, we observe that syntactic component analysis can miss decomposition opportunities because the syntax may hide existing semantic independence, leading to unnecessary variable splitting. Moreover, we show that by applying a limited resolution strategy to the CNF prior to inference, one can transform the CNF to syntactically reveal such semantic independence. We describe a general resolution strategy for this purpose, and a more specific one that utilizes problem–specific structure. We apply our proposed techniques to CNF encodings of Bayesian networks, which can be used to answer probabilistic queries through weighted model counting and/or knowledge compilation. Experimental results demonstrate that our proposed techniques can have a large effect on the efficiency of inference, reducing time and space requirements significantly, and allowing inference to be performed on many CNFs that exhausted resources previously.

IJCAI Conference 2005 Conference Paper

Compiling Bayesian Networks with Local Structure

• Mark Chavira
• Adnan

Recent work on compiling Bayesian networks has reduced the problem to that of factoring CNF encodings of these networks, providing an expressive framework for exploiting local structure. For networks that have local structure, large CPTs, yet no excessive determinism, the quality of the CNF encodings and the amount of local structure they capture can have a significant effect on both the offline compile time and online inference time. We examine the encoding of such Bayesian networks in this paper and report on new findings that allow us to significantly scale this compilation approach. In particular, we obtain order–of–magnitude improvements in compile time, compile some networks successfully for the first time, and obtain orders– of–magnitude improvements in online inference for some networks with local structure, as compared to baseline jointree inference, which does not exploit local structure.

UAI Conference 2005 Conference Paper

Exploiting Evidence in Probabilistic Inference

• Mark Chavira
• David Allen
• Adnan Darwiche

We define the notion of compiling a Bayesian network with evidence and provide a specific approach for evidence-based compilation, which makes use of logical processing. The approach is practical and advantageous in a number of application areas-including maximum likelihood estimation, sensitivity analysis, and MAP computations-and we provide specific empirical results in the domain of genetic linkage analysis. We also show that the approach is applicable for networks that do not contain determinism, and show that it empirically subsumes the performance of the quickscore algorithm when applied to noisy-or networks.