nips nips2003 nips2003-30 nips2003-30-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Alina Beygelzimer, Irina Rish
Abstract: We consider the question of how well a given distribution can be approximated with probabilistic 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 the threshold behavior of monotone graph properties, and provide experimental results that support the approach. 1
[1] A. Barak and P. Erd˝ s. On the maximal number of strongly independent vertices in a random o acyclic directed graph. SIAM J. Algebraic and Discrete Methods, 5:508–514, 1984.
[2] A. Beygelzimer and I. Rish. Inference complexity as a model-selection criterion for learning bayesian networks. In Proceedings of the Eighth International Conference on Principles of Knowledge Representation and Reasoning (KR2002), Toulouse, France, 2002.
[3] B. Bollob´ s and G. Brightwell. The structure of random graph orders. SIAM J. Discrete Matha ematics, 10(2):318–335, 1997.
[4] C. Chow and C. Liu. Approximating discrete probability distributions with dependence trees. IEEE Trans. on Inf. Theory, 14:462–467, 1968.
[5] T. Cover and J. Thomas. Elements of information theory. John Wiley & Sons Inc., New York, 1991. A Wiley-Interscience Publication.
[6] R. Dechter. Bucket elimination: A unifying framework for probabilistic reasoning. In M. I. Jordan (Ed.), Learning in Graphical Models, Kluwer Academic Press, 1998.
[7] P. Erd˝ s and A. R´ nyi. On the evolution of random graphs. Bull. Inst. Internat. Statist., 38:343– o e 347, 1961.
[8] E. Friedgut and G. Kalai. Every monotone graph property has a sharp threshold. Proceedings of the American Mathematical Society, 124(10):2993–3002, 1996.
[9] K. H¨ ffgen. Learning and robust learning of product distributions. In Proceedings of the 6th o Annual Workshop on Computational Learning Theory, pages 77–83, 1993.
[10] F. V. Jensen and F. Jensen. Optimal junction trees. In Proc. Tenth Conference on Uncertainty and AI (UAI), 1994.
[11] J. Naor and M. Naor. Small-bias probability spaces: Efficient constructions and applications. In Proc. of the 22nd ACM Symposium on Theory of Computing (STOC), pages 213–223, 1990.
[12] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, 1988.
[13] N. Srebro. Maximum likelihood bounded Tree-Width markov networks. In Proceedings of the 17th Conference on Uncertainty in AI (UAI), pages 504–511, 2001. 6 Note, however, that it does not imply that the empirical distribution itself decomposes on a treewidth-4 model. The simplest example of this is when the true distribution is uniform.