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

2 December 2013, Sydney, Australia


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:

  1. Convergence rates for non-smooth methods

  2. Connections between various inference approaches, and which methods are suitable to which problems

  3. Relationship between local marginal consistency and the graph structures

  4. Constraint reduction

  5. Decomposition of inference of a large PGM into a number of inferences of small PGMs

  6. 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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

Submission information

All submissions should use the ICCV main conference paper format. Please check the ICCV main conference webpage for the paper templates.

All submissions (in PDF or MS Word format) should be emailed to Infer.PGM.iccv13@gmail.com with the email title being “ICCV13 PGM workshop submission”. Please include the authors’ names and affiliations in the email body. All submitted papers will receive at least two reviews.

All accepted submissions will be presented as oral plus poster or spotlight plus poster.

Presentation guide

Each spotlight contains a 4-minute talk plus 1-minute question. No page limit for the slides as long as you can finish in time.

Each oral presentation contains a 19-minute talk plus 1-minute question.

Posters should follow the main conference's poster guideline.

Important dates

Submission Deadline: 7 Sept. 2013 ; extended to 17 Sept. 2013
Notification of Acceptance: 1 Oct. 2013
Final Versions Due: 7 Oct. 2013
Workshop Date: 2 Dec. 2013


Qinfeng (Javen) Shi University of Adelaide, javen.shi@adelaide.edu.au
Chunhua Shen University of Adelaide, chunhua.shen@adelaide.edu.au
Stephen Gould Australian National University, stephen.gould@anu.edu.au
Jason L. Williams DSTO, jlwilliams@alum.mit.edu
Tiberio Caetano NICTA, tiberio.caetano@gmail.com

Keynote speakers


Inference for probabilistic graphical models (PGMs)