nips nips2013 nips2013-184 nips2013-184-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Tim Roughgarden, Michael Kearns
Abstract: We consider a number of classical and new computational problems regarding marginal distributions, and inference in models specifying a full joint distribution. We prove general and efficient reductions between a number of these problems, which demonstrate that algorithmic progress in inference automatically yields progress for “pure data” problems. Our main technique involves formulating the problems as linear programs, and proving that the dual separation oracle required by the ellipsoid method is provided by the target problem. This technique may be of independent interest in probabilistic inference. 1
[1] Nicolo Cesa-Bianchi and G´ bor Lugosi. Prediction, Learning, and Games. Cambridge Unia versity Press, 2006.
[2] D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009.
[3] M.J. Wainwright and M.I. Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 1(1), 2008.
[4] S. Lauritzen. Graphical Models. Oxford University Press, 1996.
[5] T. Hazan and T. Jaakkola. On the partition function and random maximum a-posteriori perturbations. Proceedings of the 29th International Conference on Machine Learning, 2012.
[6] J. K. Johnson, V. Chandrasekaran, and A. S. Willsky. Learning markov structure by maximum entropy relaxation. In 11th International Conference in Artificial Intelligence and Statistics (AISTATS 2007), 2007.
[7] V. Chandrasekaran, J. K. Johnson, and A. S. Willsky. Maximum entropy relaxation for graphical model selection given inconsistent statistics. In IEEE Statistical Signal Processing Workshop (SSP 2007), 2007.
[8] D. Sontag and T. Jaakkola. New outer bounds on the marginal polytope. In Neural Information Processing Systems (NIPS), 2007.
[9] L. G. Khachiyan. A polynomial algorithm in linear programming. Soviet Mathematics Doklady, 20(1):191–194, 1979.
[10] A. Ben-Tal and A. Nemirovski. Optimization iii. Lecture notes, 2012.
[11] M. Gr¨ tschel, L. Lov´ sz, and A. Schrijver. Geometric Algorithms and Combinatorial Optio a mization. Springer, 1988. Second Edition, 1993.
[12] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge, 2004.
[13] M. Singh and N. Vishnoi. Entropy, optimization and counting. arXiv, (1304.8108), 2013. 9