Abstract
Graphical models are a widely used knowledge representation framework that captures independencies in the data and allows for a concise representation. Well known examples of graphical models include Bayesian networks, constraint networks, Markov random fields and influence diagrams. Graphical models are applicable to diverse domains such as planning, scheduling, design, diagnosis and decision making.

This dissertation is concerned with graphical model algorithms that leverage the structure of the problem. We investigate techniques that capitalize on the independencies expressed by the model’s graph by decomposing the problem into independent components, resulting in often exponentially reduced computational costs.
The algorithms that we develop can be characterized along three main dimensions: (1) search vs. dynamic programming methods; (2) deterministic vs. probabilistic information; (3) approximate vs. exact algorithms.

We introduce the AND/OR search space perspective for graphical models. In contrast to the traditional OR search, the new AND/OR search is sensitive to problem decomposition. The AND/OR search tree search is in most cases exponentially smaller (and never larger) than the OR search tree. The AND/OR search graph is exponential in the treewidth of the graph, while the OR search graph is exponential in the pathwidth.

We introduce mixed networks, a new graphical model framework that combines belief and constraint networks. By keeping the two types of information separate we are able to more efficiently exploit them by specific methods. We describe the primary algorithms for processing such networks, based on inference and on AND/OR search.

In terms of approximate algorithms, we investigate message-passing schemes based on join tree clustering and belief propagation. We introduce Mini-Clustering (MC), which performs bounded inference on a tree decomposition. We then combine MC with the iterative version of Pearl’s belief propagation (IBP), creating Iterative Join-Graph Propagation (IJGP). We show empirically that IJGP is one of the most powerful approximate schemes for belief networks. Through analogy with arc consistency algorithms from constraint networks, we show that IBP and IJGP infer zero-beliefs correctly, and empirically show that this also extends to extreme beliefs.

We apply the AND/OR paradigm to cutset conditioning and show that the new method is a strict improvement, often yielding exponential savings. The AND/OR cutset is the inspiration of a new caching scheme for AND/OR search, which led to the design of our most powerful and flexible algorithm AND/OR Adaptive Caching.

Furthermore we make a comparison of AND/OR search and inference methods. We analyze them side by side by describing the context minimal graph that they traverse. We also investigate three hybrid schemes, based on search and inference and show that Adaptive Caching is never worse than the other two.

Finally, we apply the AND/OR perspective to decision diagrams. We extend them with AND nodes capturing function structure decomposition, resulting in AND/OR Multi- Valued Decision Diagrams (AOMDDs). The AOMDD is a canonical form that compiles a graphical model and has size bounded exponentially by the treewidth, rather than pathwidth (as is the case for OR decision diagrams). We present two compilation algorithms, one based on AND/OR search, the other based on a Variable Elimination schedule.