Approximability of Probability Distributions

Part of Advances in Neural Information Processing Systems 16 (NIPS 2003)

Bibtex Metadata Paper

Authors

Alina Beygelzimer, Irina Rish

Abstract

We consider the question of how well a given distribution can be approx- imated with probabilistic graphical models. We introduce a new param- eter, effective treewidth, that captures the degree of approximability as a tradeoff between the accuracy and the complexity of approximation. We present a simple approach to analyzing achievable tradeoffs that ex- ploits the threshold behavior of monotone graph properties, and provide experimental results that support the approach.