Methods for advancing combinatorial optimization over graphical models

Graphical models are a well-known convenient tool to describe complex interactions between variables. A graphical model defines a function over many variables that factors over an underlying graph structure. One of the popular tasks over graphical models is that of combinatorial optimization. Although many algorithms have been developed with this task in mind, the vast majority are designed to find an optimal solution, minimum or maximum, of an objective function. In many applications, however, it is desirable to obtain not just a single optimal solution, but a set of the first m best solutions for some integer m. The main part of this dissertation focuses on this problem, which we call the m-best optimization task. We show that the m-best task can be expressed within the unifying framework of semirings, making known inference algorithms defined, and their correctness and completeness for the m-best task immediately implied. We subsequently describe elim-m-opt, a new bucket elimination algorithm for solving the m-best task, provide algorithms for its defining combination and marginalization operators and analyze its worst-case performance. An extension of the algorithm to the mini-bucket framework provides bounds for each of the m best solutions. Subsequently, we extend existing search algorithms to the m-best task. We present a new algorithm m-A* and prove that all A*’s desirable properties, including soundness, completeness and optimal efficiency, are maintained. Since best-first algorithms require extensive memory, we also extend the memory-efficient depth-first branch and bound to the m-best task. We adapt both algorithms to optimization tasks over graphical models (e.g., Weighted Constraint Satisfaction Problems and Most Probable Explanation in Bayesian networks), and provide complexity analysis and an empirical evaluation. Our experiments with 5 variants of best-first search and depth-first branch and bound search confirm that the best-first approach is largely superior when memory is available, but branch and bound is more robust. We also demonstrate that both styles of search benefit greatly from the heuristic evaluation function with increased accuracy. Unlike the leading previously developed m-best schemes that utilize LP-relaxation techniques, e.g., algorithms by Fromer and Globerson (2009) and Batra (2012), our algorithms always guarantee solution optimality. We will show that, when the number of required solutions is small, our m-best search schemes are quite competitive with these related algorithms in terms of runtime, while for a larger number of required solutions our methods are by far superior. The second part of this thesis focuses on finding approximate solutions to optimization problems. Unfortunately solving exactly optimization problems over complex models, that represent intricate dependencies occurring in real life domains, can often be infeasible within practical time and space limits. Many approximation schemes exist, but most of them do not come with any solution sub-optimality guarantees. We apply the ideas of weighted heuristic search, popular in path-finding, to graphical models, yielding new search algorithms that not only provide sub-optimality bounds, but also utilize extra available time and space to improve the accuracy of the solution in an anytime manner and, if resources are available, eventually terminate with an optimal solution. We report on a significant empirical evaluation, demonstrating the usefulness of weighted best-first search as approximation anytime schemes (that have sub-optimality bounds) and compare against one of the best depth-first branch and bound solvers to date. We also investigate the impact of different heuristic functions on the behavior of the algorithms. Additionally, we explore several algorithms taking advantage of two common approaches for bounding MPE queries in graphical models: mini-bucket elimination and message-passing updates for linear programming relaxations. Each method offers a useful perspective for the other; our hybrid approaches attempt to balance the advantage of each. We demonstrate the power of our hybrid algorithms through extensive empirical evaluation. Most notably, a branch and bound search guided by the heuristic functions calculated by our new scheme won the first place in the 2011 Pascal2 inference challenge