Perturb-and-MAP Random Fields: Reducing Random Sampling to Optimization

We consider a graph with nodes which can take either discrete or continuous values . Our starting point is a deterministic energy function , where is a vector of real parameters and is a vector of data-dependent potentials. In the Perturb-and-MAP random field we generate a sample by first adding noise to the parameters, followed by finding the most probable (MAP) state of the perturbed energy function, as shown in the box to the left. We can design the perturbation density so as the resulting model is identical or approximates closely the standard Gibbs MRF whose probability is . The advantage of the Perturb-and-MAP approach over standard MRF simulation techniques is that it avoids MCMC, instead reducing sampling to a typically easier to solve energy minimization problem.

A geometric viewpoint is important for understanding discrete-label Perturb-and-MAP random fields. It turns out that the set of perturbations for which a particular state will be generated is a polyhedron in .

As an illustration, let's consider the Ising model on two variables, with energy Assume perturbations to the unary terms only, i.e., . The figure on the left shows its -space geometry. The state , for example, will be generated if the perturbation instance falls in the shaded polyhedron; integrating the perturbation density over this polyhedron gives the probability of the state under the Perturb-and-MAP model.

While the Perturb-and-MAP and Gibbs models are defined quite differently, it turns out that there exists a particular perturbation design involving the Gumbel probability distribution that makes the two models exactly equivalent.

However, this full-order Gumbel perturbation is not very useful in practice as it yields a problem of exponential size. We use instead reduced order perturbations which inject Gumbel noise to unary or pairwise MRF potentials and lead to perturbed energies essentially as easy to minimize as the original unperturbed one. The resulting Perturb-and-MAP model approximates the corresponding Gibbs MRF.

We learn model parameters from training data by the moment matching rule, which approximates the maximum likelihood criterion. Similarly to the Gibbs MRF, maximum likelihood estimation in the Perturb-and-MAP model is a concave optimization problem with a unique maximum.

The example on the left shows how the moment matching rule learns the parameters of an Ising model from Gibbs Ising model training data. Upon convergence, the generated Perturb-and-MAP samples reproduce the sufficient statistics and also visually closely resemble the training examples.

Our goal in interactive image segmentation is to find the exact outline of an object given a rough user annotation of the foreground and background. The main advantages of the Perturb-and-MAP model over MAP estimation as used in standard techniques such as GrabCut are:

• It enables learning the energy model parameters from training data.

• It produces soft segmentation maps, thus capturing the model's uncertainty on the result. Still, the model still employs graph cuts for sampling and is thus essentially as fast as MAP-based methods.

As another application, consider the scene labeling problem, where an image of an outdoor scene is segmented into a number of regions (such as facing left, bottom, top, etc.) – see D. Hoiem's geometric context web page for more information. Further, we assume that the scene has a specific tiered structure and also employ an energy function that encourages smoothness in the label assignments – see P. Felzenszwalb's page for further information on the tiered labeling model. Under the Perturb-and-MAP model, we can draw samples by using the efficient tiered dynamic programming MAP algorithm, which enables:

• Parameter learning from training data.

• Marginal MAP decisions, which minimize the pixel-wise (Hamming) loss.

• Uncertainty quantification of the final segmentation result.

In Gaussian models the nodes are real-valued and the energy function is of quadratic form. In Gaussian MRFs each energy factor is typically defined as a quadratic form on the response of a linear filter with few non-zero coefficients. The support of these filters determine the Markov dependence structure of the model and the sparsity pattern of the inverse covariance (information) matrix . See figure to the left. Gaussian MRFs are popular in spatial statistics and image analysis, both as standalone models and as constituent blocks of more complex non-Gaussian models.

The standard approach to sampling from Gaussian models involves computing the Cholesky decomposition of either the covariance or the information matrix. However this is computationally too costly for large scale models such as those encountered in image analysis.

We have worked on an alternative scalable method for exact sampling in GMRFs. It amounts to locally perturbing the GMRF potentials by adding Gaussian noise to them , followed by computing the mean/mode of the perturbed GMRF . This implies that GMRF sampling has the same computational complexity as GMRF mean computation and allows us to use efficient iterative algorithms such as preconditioned conjugate gradients, loopy Gaussian BP, or DFT-domain techniques for rapid sampling of large-scale GMRFs.

The estimation uncertainty in Gaussian MRFs is captured by marginal variances, i.e., the diagonal elements of . However, computing these variances in large-scale models turns out to be a surprisingly difficult problem.

Being able to efficiently draw samples from Gaussian MRFs allows us to estimate variances by Monte Carlo, , where . This generic estimator is unbiased and turns out to be very effective, especially when relatively rough variance estimates are required.