 |
Center for Nonlinear Studies |
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, I will show the gain obtained from a hybrid of search and inference, using mini-bucket lower-bounds heuristics to guide AND/OR search. New algorithms that combine mini-bucket with cost-shifting lower-bounding schemes such as moment matching and linear relaxation will be described, if time permits.
Host: Josephine Olivas