Approximability of Probability Distributions
Alina Beygelzimer, Irina Rish · 2003
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. 1