Discrete Graphical Models — An Optimization Perspective

This monograph is about combinatorial optimization. More precisely, about a special class of combinatorial problems known as energy minimization or maximum a posteriori (MAP) inference in graphical models, closely related to weighted and valued constraint satisfaction problems and having tight connections to Markov random fields and quadratic pseudo-boolean optimization. What distinguishes this monograph from a number of other monographs on graphical models is its focus: It considers graphical models, or, more precisely, MAP-inference for graphical models, purely as a combinatorial optimization problem. Modeling, applications, probabilistic interpretations and many other aspects are either ignored here or find their place in examples and remarks only. Combinatorial optimization as a field is largely based on five fundamental topics: (i) integer linear programming and polyhedral optimization; (ii) totally unimodular matrices and the class of min-cost-flow problems; (iii) Lagrange decompositions and relaxations; (iv) dynamic programming and (v) submodularity, matroids and greedy algorithms. Each of these topics found its place in this monograph, although to a variable extent. The covering of each respective topic reflects its importance for the considered MAP-inference problem. Since optimization is the primary topic of this monograph, we mostly stick to the terminology widely used in optimization and where it was possible we tried to avoid the graphical models community-specific technical terms. The latter differ from sub-community to sub-community and, in our view, significantly complicate the information exchange between them. The same holds also for the presentation of material in this monograph. If there is a choice when introducing mathematical constructs or proving statements, we prefer more general mathematical tools applicable in the whole field of operations research rather than to stick to graphical modelspecific constructions. We additionally provide the graphical model-specific constructions if it turns out to be easier than the more general one. This way of presentation has two advantages. A reader familiar with a more general technique can grasp the new material faster. On the other hand, the monograph may serve as an introduction to combinatorial optimization for readers unfamiliar with this subject. To make the monograph even more suitable for both categories of readers we explicitly separate the mathematical optimization background chapters from those specific to graphical models. We believe, therefore, that the monograph can be useful for undergraduate and graduate students studying optimization or graphical models, as well as for experts in optimization who want to have a look into graphical models. Moreover, we believe that even experts in graphical models can find new views on the known facts as well as a novel presentation of less known results in the monograph. These are for instance (i) a simple and general proof of equivalence of different acyclic Lagrange decompositions of a graphical model; (ii) a general scheme for analyzing convergence of dual block-coordinate descent methods; (iii) a short and self-contained analysis of a linear programming relaxation for binary graphical models, its persistency properties and its relation to quadratic pseudo-boolean optimization. The present monograph is based on lectures given to undergraduate students of Technical University of Dresden and Heidelberg University. The selection of material is done in a way that it may serve as a basis for a semester course.