Approximability of Probability Distributions

We consider the question of how well a given distribution can be approximated withprobabilistic graphical models. We introduce a new parameter, 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 exploits thethreshold behavior of monotone graph properties, and provide experimental results that support the approach.