Ph.D Student | Batya Kenig |
---|---|

Subject | Message Propagation Algorithms for Weighted Model Counting |

Department | Department of Industrial Engineering and Management |

Supervisor | Full Professor Gal Avigdor |

Full Thesis text |

Graphical models which
include Bayesian networks, Markov random fields and constraint networks have
been established as a central tool for modeling and reasoning under
uncertainty. Graphical models are equipped with general inference algorithms
which enable computing probabilities related to the represented distribution
without having to explicitly generate it. Reducing probabilistic inference to
the problem of Weighted Model Counting (WMC) on a propositional

knowledge base has been proved as an effective approach to probabilistic
inference. Applying this approach requires encoding the probabilistic graphical
model as a propositional knowledge base in conjunctive normal form (CNF). Given
this CNF, probabilistic inference is reduced to the weighted model count of
consistent models for the formula. Both WMC and probabilistic inference are
#P-hard, motivating the search for efficient algorithms.

The contributions of this thesis are threefold: theoretical, algorithmic and
practical. Theoretically, we define a new characterization of formulas whose
weighted model count can be computed in P-time. The characterization is based
on the junction tree of the formula and is closely related to the notion of
acyclicity in hypergraphs. This theoretical advance is a stepping stone towards
the development of a WMC algorithm which not only takes advantage of the formula’s
junction-tree but also integrates several techniques from both the CNF-SAT and probabilistic
graphical model literature. The proposed approach combines elements from the junction-tree
inference algorithm, along with tree-conditional-probability-tables
(tree-CPTs), to effectively capitalize on context-specific-independence.
Adapting component caching, binary

clause propagation and clause learning into the proposed approach transforms it
to a practical tool for performing probabilistic inference via CNF encoding and
weighted model counting.

The proposed approach is not limited to WMC, and can be utilized for solving
optimization problems such as Most Probable Explanation (MPE), or its
equivalent MAX-SAT. The empirical results reported in the thesis show that our
approach can enhance performance on a representative set of problem domains by
capitalizing on the additional structural properties described.