PGMs 2013 - ICCV 2013 Workshop: Inference for probabilistic graphical models (PGMs)

Probabilistic graphical models (PGMs) have been applied widely in computer vision, to problems solving including image and video segmentation, scene understanding, human activity recognition, tracking and point matching. Inference methods for PGMs are a key enabler in many of these problems. With advances in inference techniques, new insights are emerging, as are new problems that are motivated by these applications. The purpose of this workshop is to bring together an examination of theoretical advances in inference techniques with emerging problem formulations motivated by applications. Researchers are encouraged to submit work including novel inference methods, new views or understandings, novel inference problems and/or methods for solving them.
Solution of Maximum a Posteriori (MAP) problems has progressed rapidly in recent years. Many inference methods are now generalized to higher-order potentials via factorization over cliques or clusters, which bring convenience for computer vision tasks where higher-order potentials are often desirable. Dual decomposition and Generalized Max Product for Linear Programming (GMPLP) are known to optimize the dual objective of the MAP Linear Programming (LP) relaxation via subgradient or block coordinate descent. One attractive property of these dual methods is that the optimality is guaranteed under certain conditions such as zero gap between dual objective and the primal objective value for the decoded solution and uniqueness of solutions over intersections of clusters.
Smoothness terms such as entropy can be added to prevent dual block coordinate descent methods from becoming stuck in sub-optimal corners; convergence rates for these methods have recently been reported. Apart from LP relaxations, many other optimisation techniques yield useful relaxations including Quadratic Programming (QP), Semidefinite Programming (SDP) and Second-order Cone Programming (SOCP); each of these has been applied to inference problems.
Methods seeking approximations of the local marginal distributions include mean field, Expectation Propagation (EP), loopy belief propagation (BP), generalized BP, tree reweighted BP and norm product BP. The various BP algorithms have been shown to be based on minimisation of the Bethe free energy, the Kikuchi approximation, or convexifications thereof. Particularly successful approximations have been found in a small number of canonical problems (e.g., approximation of the matrix permanent). Recently, progress has also been made in marginal-MAP problems, which seek the MAP of a PGM following marginalization of a subset of nodes. There has also been recent interest in obtaining multiple high probability solutions from a model (Best-M), and our workshop will include discussion on these approaches.
Despite the advances in this field, some important aspects are still unclear such as:
Convergence rates for non-smooth methods
Connections between various inference approaches, and which methods are suitable to which problems
Relationship between local marginal consistency and the graph structures
Constraint reduction
Decomposition of inference of a large PGM into a number of inferences of small PGMs
In approximate marginal inference, no guarantees exist on the error in the various solutions in comparison to the exact marginal distributions
Applications of inference also motivate new problem classes. Some examples are:
MAP inference with unknown graph structure. In the human activity recognition or scene understanding, the number of persons or objects across images or videos varies. To find the most probable labels for these persons or objects jointly, requires performing MAP inference without knowing the graph structure. This problem is different from a standard MAP inference problem where the graph structure is given. This is also different from estimating homogeneous graph structures where the graph structure is the same for all instances, or at least the basic structure across two consecutive time frames (two time-slice) is fixed.
Inference for large scale PGMs. For example, using PGMs to predict “social circles” in social networks such as Facebook encounters large scale PGMs. In video segmentation, the number of nodes is extremely high: for an one-hour video footage with a modest frame rate 15-frames-per-second and modest frame size 300 by 200 (treating each pixel as a node), there are over 3.2 billion nodes in the PGM.
Inference in hybrid continuous-discrete models. Tracking problems commonly involve both continuous variables (e.g., object positions) and discrete variables (e.g., object correspondences), and hard constraints in potentials. These complications have in part motivated a range of advances such as EP, non-parametric BP, marginal-MAP inference and merged mean field-BP approaches.
M-Best MAP problems and Diverse M-Best problems. These problems come from applications where, instead of a MAP solution, the top M most probable solutions or even diverse high-probability solutions are of interest.