Discrete graphical models -- an optimization perspective
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationSimilar Papers 제목 키워드 기반
Exact MAP inference in general higher-order graphical models using linear programming
This paper is concerned with the problem of exact MAP inference in general higher-order graphical models by means of a traditional linear programming relaxation approach. In fact, the proof that we have developed in this…
Unbiased Learning of Deep Generative Models with Structured Discrete Representations
By composing graphical models with deep learning architectures, we learn generative models with the strengths of both frameworks. The structured variational autoencoder (SVAE) inherits structure and interpretability from…
Time SeriesGlobal RTK Positioning in Graphical State Space
This paper proposes a new method for RTK post-processing. Different from the traditional forward-backward Kalman filter, in our method, the whole system equation is built on a graphical state space model and solved by fa…
PositionTime SeriesTime Series AnalysisDiscrete-Continuous Depth Estimation from a Single Image
In this paper, we tackle the problem of estimating the depth of a scene from a single image. This is a challenging task, since a single image on its own does not provide any depth cue. To address this, we exploit the ava…
Depth EstimationMonocular Depth EstimationSuperpixelsMessage Passing and Combinatorial Optimization
Graphical models use the intuitive and well-studied methods of graph theory to implicitly represent dependencies between variables in large systems. They can model the global behaviour of a complex system by specifying o…
ClusteringCombinatorial OptimizationTraveling Salesman Problem