Graphical models, e.g., Bayesian networks, Markov random fields, constraint networks and influence diagrams, are knowledge representation schemes that capture independencies in the knowledge base and support efficient, graph-based algorithms for a variety of reasoning tasks. Their applications include scheduling, planning, diagnosis and situation assessment, design, and hardware and software verification. Algorithms for reasoning in graphical models are of two primary types: inference-based (e.g., variable-elimination, join-tree clustering) and search-based. Exact inference-based algorithms are exponentially bounded (both time and space) by the tree-width of the graph. Search algorithms that explore an AND/OR search space can accommodate a more flexible time and memory tradeoff but their performance can also be bounded exponentially by the tree-width.

In my talk I will present and contrast the two primary types of reasoning algorithms and subsequently will focus on bounded inference approximations such as belief propagation and mini-bucket elimination.  In particular and as time permits I will show the gain obtained from a hybrid of search and inference, using mini-bucket lower-bounds heuristics to guide AND/OR search, and will comment on how we can transition to approximation scheme using graph-based AND/OR sampling.