On the Partition Function and Random Maximum A-Posteriori Perturbations
This provides a novel framework for approximating partition functions in machine learning, particularly useful for complex models with difficult energy landscapes, though it appears incremental as it builds on existing MAP inference techniques.
The paper tackles the problem of approximating the partition function in probabilistic models by relating it to max-statistics and using MAP inference on randomly perturbed models, enabling the use of efficient MAP solvers like graph-cuts. It shows that the method performs well in high signal-high coupling regimes with ragged energy landscapes where other approaches struggle.
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.