Search Machine Learning Repository:
**Taming the Curse of Dimensionality: Discrete Integration by Hashing and Optimization**

**Authors:** *Stefano Ermon*, *Carla Gomes*, *Ashish Sabharwal* and *Bart Selman*

**Conference:** Proceedings of the 30th International Conference on Machine Learning (ICML-13)

**Year:** 2013

**Pages:** 334-342

**Abstract:** Integration is affected by the curse of dimensionality and quickly becomes intractable as the dimensionality of the problem grows. We propose a randomized algorithm that, with high probability, gives a constant-factor approximation of a general discrete integral defined over an exponentially large set. This algorithm relies on solving only a small number of instances of a discrete combinatorial optimization problem subject to randomly generated parity constraints used as a hash function. As an application, we demonstrate that with a small number of MAP queries we can efficiently approximate the partition function of discrete graphical models, which can in turn be used, for instance, for marginal computation or model selection.

[pdf] [BibTeX]

authors venues years

Suggest Changes to this paper.

Brought to you by the WUSTL Machine Learning Group. We have open faculty positions (tenured and tenure-track).