ABSTRACT
This chapter focuses on a family of approximations which are based on a linear programming (LP) relaxation. The combinatorial program of maximum a-posteriori (MAP) inference is cast as an intractable linear program, and some of the constraints are then relaxed for tractability. The chapter discusses the LP relaxation approaches for MAP estimation, and presents progress on the design and analysis of efficient solvers for this important problem. It outlines the connection to more traditional message-passing techniques. It explores the problem of extracting a MAP solution from an approximate solution. Many iterative solvers for MAP inference are often interpreted as performing message-passing on a graphical representation of the problem. Specifically, the structure of the MAP inference problem resembles a graph with sparse connectivity, and many of the devised solvers cast MAP inference as solving for variables that are indexed by edges on this graph.
