Randomized Optimum Models for Structured Prediction

Daniel Tarlow, Ryan Prescott Adams, Richard S. ZemelAISTATS 2012 · OpenReview

Abstract

One approach to modeling structured discrete data is to describe the probability of states via an energy function and Gibbs distribution. A recurring difficulty in these models is the computation of the partition function, which may require an intractable sum. However, in many such models, the mode can be found efficiently even when the partition function is unavailable. Recent work on Perturb-and-MAP (PM) models has exploited this discrepancy to approximate the Gibbs distribution for Markov random fields (MRFs). Here, we explore a broader class of models, called Randomized Optimum Models (RandOMs), which include PM as a special case. This new class of models encompasses not only MRFs, but also other models that have intractable partition functions yet permit efficient mode-finding, such as those based on bipartite matchings, shortest paths, or connected components in a graph. We develop likelihood-based learning algorithms for RandOMs, which, empirical results indicate, can produce better models than PM.

Introduction

Structured prediction involves predicting complex, interdependent outputs such as graphs, matchings, or sequences. A fundamental challenge in this field is the "partition function frustration": while it is often computationally efficient to score a specific configuration, calculating the normalizing constant (the partition function) required for a proper probability distribution is frequently #P-complete. Traditional approaches like Conditional Random Fields (CRFs) struggle with this intractability, leading researchers to rely on approximations like loopy belief propagation or non-probabilistic methods like Structured Support Vector Machines (SSVMs).

This paper introduces Randomized Optimum Models (RandOMs), a framework that sidesteps the summation problem by leveraging efficient optimization algorithms. By injecting noise into an objective function and finding the global optimum, RandOMs define rigorous probability distributions over complex discrete structures.

The RandOM Framework

The core idea of RandOMs is to define a generative process that maps continuous latent variables to discrete structured outputs through deterministic optimization.

Figure 1: The RandOM generative process. Latent weights w are sampled from a distribution p(w) conditioned on features. A deterministic optimization function F maps these weights to a structured output y. The inverse mapping set F⁻¹(y) denotes the region in weight space that produces output y.

The process follows two steps:

  1. Latent Noise Sampling: Sample a set of continuous latent weights $w$ from a distribution $p(w|x, \psi)$, such as a Gaussian, conditioned on input features $x$ and parameters $\psi$.
  2. Deterministic Optimization: Use these weights as costs in an objective function $f_w$. The output $y$ is the configuration that minimizes this function: $y = \text{argmin}_{y' \in \mathcal{Y}} f(y'; w)$.

In this framework, the probability of an output $y$ is the volume of the weight space that maps to $y$, known as the inverse mapping set $F^{-1}(y)$. This shifts the problem from intractable discrete summation to integration over a continuous latent space.

Learning Algorithms

The authors propose two primary algorithms for learning the parameters $\psi$:

  • Monte Carlo Expectation Maximization (MCEM): This approach utilizes a specialized Slice Sampler to explore the weight space. To maintain efficiency, the authors employ "dynamic" combinatorial algorithms that can rapidly update solutions when small perturbations occur in the weight space.
  • Hard EM: A point-estimation method that identifies the single best set of weights. This approach can be viewed as a probabilistic extension of Structural SVMs, typically solved using cutting-plane optimization.

Experimental Evaluation

The performance of RandOMs was evaluated on both synthetic and real-world tasks.

Synthetic Bipartite Matching

In a controlled environment, models were tasked with matching points in 2D space based on noisy features. The experiments compared RandOMs against the state-of-the-art Perturb-and-MAP (PM) approach.

Figure 2: Empirical comparison on synthetic bipartite matching data. The bar charts illustrate the probability mass assigned to various configurations by different models. MCEM demonstrates a superior ability to capture the underlying distribution compared to PM and Max-margin (MM) baselines.

In multimodal settings, the MCEM version of RandOMs significantly outperformed PM. While PM often struggled to capture complex, multi-peaked distributions, RandOMs successfully placed higher probability mass on the ground truth configurations.

Lung CT Registration

The model was applied to a medical imaging task: aligning 30 hand-labeled landmarks in 3D lung volumes across different breathing phases. RandOMs achieved a prediction accuracy of 98.8%, notably higher than the Max-margin baseline (91.0%) and the Perturb-and-MAP baseline (95.0%). Furthermore, RandOMs provided better-calibrated uncertainty estimates compared to non-probabilistic methods.

Discussion and Conclusion

RandOMs represent a significant step in bridging optimization and probabilistic modeling. By treating optimization as a form of integration, the framework allows for the use of global constraints (e.g., "one-to-one matching") that are difficult to implement in traditional graphical models. While computationally more intensive than gradient-based methods—requiring full optimization loops within the learning process—the gains in accuracy and probabilistic calibration are substantial. Future work may explore non-parametric extensions using Gaussian Processes and early-stopping criteria to improve computational efficiency.

Summary updated

Abstract

One approach to modeling structured discrete data is to describe the probability of states via an energy function and Gibbs distribution. A recurring difficulty in these models is the computation of the partition function, which may require an intractable sum. However, in many such models, the mode can be found efficiently even when the partition function is unavailable. Recent work on Perturb-and-MAP (PM) models (Papandreou and Yuille, 2011) has exploited this discrepancy to approximate the Gibbs distribution for Markov random fields (MRFs). Here, we explore a broader class of models, called Randomized Optimum Models (RandOMs), which include PM as a special case. This new class of models encompasses not only MRFs, but also other models that have intractable partition functions yet permit efficient mode-finding, such as those based on bipartite matchings, shortest paths, or connected components in a graph. We develop likelihood-based learning algorithms for RandOMs, which, empirical results indicate, can produce better models than PM.
BibTeX
@inproceedings{tarlow2012randomized,
  author = {Daniel Tarlow and Ryan Prescott Adams and Richard S. Zemel},
  title = {{Randomized Optimum Models for Structured Prediction}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2012},
  url = {https://openreview.net/forum?id=S0xV5Ictpbc},
}
Figure