Discrete graphical models -- an optimization perspective
From MaRDI portal
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Linear programming (90C05) Combinatorial optimization (90C27)
Abstract: This monograph is about discrete energy minimization for discrete graphical models. It considers graphical models, or, more precisely, maximum a posteriori 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. It covers the integer linear programming formulation of the problem as well as its linear programming, Lagrange and Lagrange decomposition-based relaxations. In particular, it provides a detailed analysis of the polynomially solvable acyclic and submodular problems, along with the corresponding exact optimization methods. Major approximate methods, such as message passing and graph cut techniques are also described and analyzed comprehensively. 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. To make the monograph suitable for both categories of readers we explicitly separate the mathematical optimization background chapters from those specific to graphical models.
Recommendations
- \(\mathrm{AD}^3\): alternating directions dual decomposition for MAP inference in graphical models
- Exact solutions for discrete graphical models. Multicuts and reduction techniques
- MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
- Energy distribution view for monotonic dual decomposition
- Inference on highly-connected discrete graphical models with applications to visual object recognition
Cited in
(19)- Efficient semidefinite branch-and-cut for MAP-MRF inference
- Self-driven algorithm for solving supermodular (,+) labeling problems based on subgradient descent
- A survey and comparison of discrete and continuous multi-label optimization approaches for the Potts model
- Energy distribution view for monotonic dual decomposition
- Searching for the m best solutions in graphical models
- Exact solutions for discrete graphical models. Multicuts and reduction techniques
- Chordal Graphs to Identify Graphical Model Solutions of Maximum of Entropy Under Constraints on Marginals
- Inference on highly-connected discrete graphical models with applications to visual object recognition
- A tutorial on dual decomposition and Lagrangian relaxation for inference in natural language processing
- Tighter continuous relaxations for MAP inference in discrete MRFs: a survey
- Lifting the convex conjugate in Lagrangian relaxations: a tractable approach for continuous Markov random fields
- scientific article; zbMATH DE number 7085065 (Why is no real title available?)
- \(\mathrm{AD}^3\): alternating directions dual decomposition for MAP inference in graphical models
- Activity propagation in systems of linear inequalities and its relation to block-coordinate descent in linear programs
- Super-reparametrizations of weighted CSPs: properties and optimization perspective
- Virtual pairwise consistency in cost function networks
- MAP inference algorithms without approximation for collective graphical models on path graphs via discrete difference of convex algorithm
- Projection methods for finding the greatest element of the intersection of max-closed convex sets
- Relative-interior solution for the (incomplete) linear assignment problem with applications to the quadratic assignment problem
This page was built for publication: Discrete graphical models -- an optimization perspective
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5127268)
