The OS* Algorithm: a Joint Approach to Exact Optimization and Sampling

Marc Dymetman, Guillaume Bouchard, Simon CarterarXiv 2012 · OpenReview

Abstract

Most current sampling algorithms for high-dimensional distributions are based on MCMC techniques and are approximate in the sense that they are valid only asymptotically. Rejection sampling, on the other hand, produces valid samples, but is unrealistically slow in high-dimension spaces. The OS algorithm that we propose is a unified approach to exact optimization and sampling, based on incremental refinements of a functional upper bound, which combines ideas of adaptive rejection sampling and of A optimization search. We show that the choice of the refinement can be done in a way that ensures tractability in high-dimension spaces, and we present first experiments in two different settings: inference in high-order HMMs and in large discrete graphical models.

Introduction

In probabilistic modeling, researchers often face a trade-off between exactness and computational speed. For sampling, drawing representative points from a distribution usually relies on Markov Chain Monte Carlo (MCMC) methods. While efficient, MCMC is only asymptotically exact, and convergence times are often unknown. Conversely, rejection sampling provides exact samples but suffers from an "acceptance rate" that vanishes in high-dimensional spaces.

For optimization, finding the peak of a distribution in complex models like high-order Hidden Markov Models (HMMs) is hindered by state-space explosion. For instance, a 5-gram HMM possesses a state space so vast that standard algorithms like Viterbi become computationally intractable. The OS* algorithm bridges this gap by providing a unified framework for both exact sampling and optimization without exhaustive exploration of the search space.

Methodology: Adaptive Refinement of Functional Upper Bounds

The core mechanism of OS is the adaptive refinement of functional upper bounds*. The process follows a "lazy" refinement strategy:

  1. Initialization: Define a proposal distribution $q$ that is easy to sample and strictly upper-bounds the target distribution $p$ (i.e., $q(x) \ge p(x)$).
  2. Sampling and Testing: Draw a sample from $q$. If it is accepted via standard rejection sampling rules, the process is complete.
  3. Refinement: If the sample is rejected, the algorithm uses the rejected point as evidence to refine $q$, creating a tighter bound $q'$ for $p$.
  4. Unified Framework: The authors demonstrate that sampling and optimization are two ends of the same spectrum. Sampling minimizes the $L_1$ norm (area under the curve), while optimization minimizes the $L_\infty$ norm (the maximum value).
Conceptual overview of OS* for sampling (S1, S2) and optimization (O1, O2).

This approach ensures that complexity is added only in regions where it is necessary to distinguish between the proposal and the target, mirroring the efficiency of A* search in avoiding irrelevant branches.

Experimental Evaluation

The paper evaluates OS* on two distinct high-dimensional tasks:

  • SMS-Message Retrieval: Recovering text from noisy numeric keypad input using a 5-gram language model trained on the English side of the Europarl corpus (1.3 million sentences).
  • Ising Models: Testing on a 10x10 uniform grid (100 binary variables) with random coupling strengths to evaluate performance in graphical models.

Key Results and Insights

  • Efficiency in Massive State Spaces: OS successfully performed exact decoding on 5-gram HMMs. For a sentence of length 10, the state space is approximately $3.0 \times 10^{15}$, making standard methods impossible. OS reached the exact maximum in only a few thousand iterations.
  • The Value of Rejection: In standard rejection sampling, a reject is wasted computation. In OS*, a reject is a diagnostic tool that identifies exactly where the current model is too optimistic, guiding the refinement process.
  • Policy Performance: In Ising model experiments, using rejected samples to guide refinement was found to be 10 times faster than a "greedy" policy that attempts to find the mathematically optimal refinement at every step.
  • Scalability: The number of iterations required for exact decoding increased sub-linearly with the order of the n-gram model, suggesting the approach scales effectively to complex dependencies.

Conclusion and Future Work

OS* provides a powerful alternative to MCMC and standard rejection sampling by treating rejects as data for model improvement. While currently focused on discrete domains and local refinements, future work aims to extend the algorithm to continuous high-dimensional spaces and "joint" refinements that improve multiple variables simultaneously. The framework also shows promise for agreement-based models that combine disparate structures, such as HMMs and Context-Free Grammars.

Summary updated

Abstract

Most current sampling algorithms for high-dimensional distributions are based on MCMC techniques and are approximate in the sense that they are valid only asymptotically. Rejection sampling, on the other hand, produces valid samples, but is unrealistically slow in high-dimension spaces. The OS* algorithm that we propose is a unified approach to exact optimization and sampling, based on incremental refinements of a functional upper bound, which combines ideas of adaptive rejection sampling and of A* optimization search. We show that the choice of the refinement can be done in a way that ensures tractability in high-dimension spaces, and we present first experiments in two different settings: inference in high-order HMMs and in large discrete graphical models.
BibTeX
@misc{dymetman2012os,
  author = {Marc Dymetman and Guillaume Bouchard and Simon Carter},
  title = {{The OS* Algorithm: a Joint Approach to Exact Optimization and Sampling}},
  year = {2012},
  eprint = {1207.0742},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1207.0742},
}
Figure