טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentBatya Kenig
SubjectMessage Propagation Algorithms for Weighted Model
Counting
DepartmentDepartment of Industrial Engineering and Management
Supervisor Full Professor Gal Avigdor
Full Thesis textFull thesis text - English Version


Abstract

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.