Source-linked AI summary
On the Partition Function and Random Maximum A-Posteriori Perturbations
Tamir Hazan, Tommi Jaakkola
TL;DR
Evaluating a partition function can be harder than MAP inference, which may be tractable despite missing alternative likely assignments. This paper uses random perturbations of MAP models to approximate and bound the partition function. It reports effectiveness in high-signal, high-coupling settings and applies the approach to conditional random fields.
Problem
MAP inference can be tractable when partition-function evaluation is not, yet it does not account for alternative likely assignments whose weights contribute to the partition function.
Source: §1 · p. 1Method
The paper relates the partition function to random MAP perturbations, using perturbed MAP values to approximate or bound it and developing lower-dimensional perturbations for practical evaluation.
Source: §1 · p. 1, §3 · p. 2, §4.1 · p. 3Results
Takeaways & Limitations
The framework lets practitioners use efficient MAP solvers, including graph-cuts, to approximate or bound partition functions, and the paper applies it to conditional random fields.
Source: §1 · p. 1, §8 · p. 7Perturbing every full assignment has complexity exponential in the number of variables, so the method uses lower-dimensional perturbations; the lower bound can be weaker than the upper bound and depends on a parameter that cannot always be made arbitrarily large.
Source: §3 · p. 2, §4.3 · p. 4
Abstract
from arXiv · showhide
In this paper we relate the partition function to the max-statistics of random variables. In particular, we provide a novel framework for approximating and bounding the partition function using MAP inference on randomly perturbed models. As a result, we can use efficient MAP solvers such as graph-cuts to evaluate the corresponding partition function. We show that our method excels in the typical "high signal - high coupling" regime that results in ragged energy landscapes difficult for alternative approaches.
1. Introduction
MAP inference can be tractable when evaluating the partition function is not, yet MAP alone misses alternative likely assignments. The paper connects the partition function to random perturbations of MAP models, enabling approximation and bounds with efficient MAP solvers, especially in high-signal, high-coupling regimes.
1. Introduction
- The partition function accounts for alternative assignments, but evaluating it can be harder than finding a MAP assignment.The introduction notes that partition-function computation can approximate the MAP value via a temperature argument, while the converse need not hold.Source: §1 · p. 1
- Randomly perturbed MAP values can approximate or bound the partition function, making efficient solvers such as graph-cuts or MPLP usable for its calculation.The paper relates the partition function to the expected MAP value of perturbations.Source: §1 · p. 1
- The approach is described as excelling when strong local evidence and strong consistency constraints yield several, but not exponentially many, prominent assignments.Source: §1 · p. 1
- The paper proceeds from notation and counting and maximization problems to random MAP approximations and bounds, then applies the method to conditional random fields.It also describes the approach's effectiveness in that application.Source: §1 · p. 1
2. Background
The background frames inference through discrete assignments scored by potentials: probabilistic inference sums their weights, while MAP selects the highest-scoring assignment. The partition function normalizes the Gibbs distribution and can be computationally difficult to evaluate.
2. Background
- The setup assumes real-valued potentials on a discrete product space, with out-of-domain assignments excluded by assigning them −∞.Source: §2 · p. 2
- The partition function normalizes the Gibbs distribution, and evaluating it is tied to the feasibility of using that distribution for inference and learning.Source: §2 · p. 2
- When potentials are restricted to −∞ or 0, the partition function counts the allowed configurations; general counting problems are considered very hard, many in #P.Source: §2 · p. 2
- MAP inference maximizes the potential over configurations in its domain, and is easier than partition-function evaluation despite being NP-hard in general.Super-modular potentials allow efficient solutions in some cases; linear-programming-relaxation methods can be surprisingly effective in practice, though their runtime can be exponential.Source: §2 · p. 2
3. Max-Statistics
The section establishes a link between partition functions and maxima of random perturbations: with independent Gumbel noise on every assignment, the perturbed maximum has expected value equal to the log partition function. Because perturbing every full assignment is exponentially costly, the paper turns to lower-dimensional perturbations for approximation and bounds.
3. Max-Statistics
- The framework starts from random MAP perturbations over general discrete sets, with independent identically distributed noise applied to each assignment.Source: §3 · p. 2
- For independent identically distributed perturbations, the CDF of the maximum is obtained by multiplying the individual assignment CDFs.Each assignment contributes F(t − φ(y)) to the product.Source: §3 · p. 2
- With independent Gumbel noise on each assignment, the perturbed maximum has expected value equal to the logarithm of the partition function.The maximum itself is Gumbel-distributed under the stated assumptions.Source: §3 · p. 2
- Perturbing every n-variable assignment makes evaluation exponential in n, motivating lower-dimensional perturbations for partition-function approximations and bounds.Source: §3 · p. 2
4. Low Dimensional Perturbations
The section develops low-dimensional random MAP perturbations to derive partition-function bounds and a sampling-based approximation, with computational trade-offs tied to perturbation structure and reuse.
4. Low Dimensional Perturbations
- Independent Gumbel perturbations in an alternating expectation–maximization recursion express the log-partition function through successive maximizations over variables.The recursion reduces each stage to a log-sum over the current variable’s settings.Source: §4 · pp. 2–3
4.1. Upper Bounds on the Partition Function
- Moving expectations outside maximizations yields upper bounds; single-node perturbations permit sample averaging when the perturbed MAP problems are tractable.Subset structure controls statistical quality and efficiency; using the full variable set gives an exact characterization but requires exponentially many random variables.Source: §4.1 · p. 3
4.2. Approximating the Partition Function
- Sampling and reusing perturbations across self-reducible dimensions produces a large MAP approximation, but its uncompressed form still uses exponentially many independent random variables.The approximation is described as effective when dominant configurations are correlated (few modes), a pattern associated in the passage with strong couplings.Source: §4.2 · pp. 3–4
4.3. Lower Bounds on the Partition Function
- A separate randomized-MAP lower bound uses a cumulant-generating-function term, but is weaker than the upper bound and is not tight in general.The parameter λ trades off the perturbed MAP value against that term; λ = 0 gives a trivial MAP-based bound, while larger λ may make the term unbounded.Source: §4.3 · p. 4
5. Conditional Random Fields
The section replaces direct partition-function computation in conditional random fields with a surrogate criterion based on random MAP perturbations. Its properties depend on the perturbation choice and the structure of the perturbed subsets.
5. Conditional Random Fields
- The surrogate criterion addresses the computational cost of CRF learning by using a partition function derived from random MAP perturbations.The learning objective depends on the partition function, which cannot be computed for the general graphs considered.Source: §5 · p. 4
- Under the stated assumptions, the criterion is convex and smooth, and its gradient enforces moment-matching constraints.With Gumbel perturbations, the criterion upper bounds the conditional random field loss.Source: §5 · pp. 4–5
- Figure 1 compares absolute log-partition estimation errors for random MAP perturbations, tree re-weighting, and belief propagation across weak and strong local fields.The plotted errors are averaged over 100 trials.Source: Figure 1 · p. 5
- The subset family α determines the approximation's statistical quality and algorithmic efficiency.Using a single subset containing all variables gives an exact CRF characterization and the standard moment-matching gradient.Source: §5 · p. 5
6. Empirical Evaluation
The evaluation tests random MAP perturbations on spin-glass partition-function estimation and supervised image denoising. The reported results are strongest in high-signal or strong-coupling settings, while the lower-bound variant is a stated weakness.
6. Empirical Evaluation
- Low-dimensional perturbations γ_i(y_i) are used because they do not affect the complexity of the MAP solver.Source: §6 · p. 5
- The random MAP perturbation approach performs better than previous approaches in the evaluated ragged-energy setting.The evaluation includes weak and strong local fields and attractive or mixed coupling potentials.Source: §6 · pp. 5–6
- With strong coupling potentials, the random MAP perturbation approximation estimates the log partition function accurately using a single MAP value; its upper bound beats tree re-weighting in the strong-signal domain.The comparison averages absolute errors over 100 spin-glass models; in attractive cases, the random MAP methods use graph cuts and are considerably faster than belief-propagation variants.Source: §6 · p. 6
- On image denoising, the method's test-set pixel error is 1.8%, compared with 8.2% for the structured-SVM-related unperturbed program.The task uses ten 100 × 70 binary images with randomly corrupted pixels and estimates about 20,000 parameters.Source: Figure 2 · p. 6, §6 · p. 6
- The random MAP lower bounds are qualitatively like the MAP value and are outperformed by mean-field, so those experiments are omitted.Source: §6 · p. 6
7. Related Work
Related work covers partition-function estimation, random-perturbation methods, and probabilistic inference. The paper distinguishes its use of random MAP perturbations from prior discrete counting bounds and notes the difficulty of sampling methods on ragged energy landscapes.
7. Related Work
- The paper frames its estimation procedure through max-statistics of collections of random variables and points readers to extreme-value statistics.Source: §7 · p. 6
- Talagrand (1994) and Barvinok & Samorodnitsky (2007) use random perturbations to upper-bound the size of a domain; the paper presents an alternative technique for these counting results.Talagrand's compression argument does not extend to the partition function, and Barvinok & Samorodnitsky use a logistic distribution.Source: §7 · p. 7
- Gumbel perturbations give a Gibbs-distributed maximizer, but independent perturbations over all assignments are computationally intractable on discrete product spaces.Prior work uses perturbations in feature space or computational structures to form surrogate probability models.Source: §7 · p. 7
- Gibbs sampling, Annealed Importance Sampling, and MCMC estimate the partition function, but can be slow on ragged energy landscapes with mixing times typically exponential in n.Perturbed MAP operations are described as unaffected by ragged energy landscapes provided MAP is feasible.Source: §7 · p. 7
- Variational partition-function estimates include inner bounds based on KL-optimized simpler distributions and convex upper bounds using surrogate entropy and relaxed constraints.Source: §7 · p. 7
8. Discussion
Randomly perturbed MAP solvers can approximate and bound the partition function, with effectiveness demonstrated in the high-signal, high-coupling regime. The discussion also notes expected-value bounds, a conditional-random-field application, and further directions involving prediction robustness and entropy approximation.
8. Discussion
- Randomly perturbed MAP solvers approximate and bound the partition function, and the approach is effective in the high-signal, high-coupling regime.For conditional random fields, the paper also describes an objective for the moment-matching algorithm of.Source: §8 · p. 7
- The bounds hold in expectation; in practice, the empirical mean is used, with measure-concentration techniques such as Chebyshev’s inequality relating it to the expected value.Source: §8 · p. 7
- The framework yields a surrogate probability model that measures prediction robustness and an entropy approximation over perturbation-induced valid distributions, unlike Bethe entropies over the local marginal polytope.Source: §8 · p. 7