nips nips2007 nips2007-20 nips2007-20-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Venkat Chandrasekaran, Alan S. Willsky, Jason K. Johnson
Abstract: We consider the estimation problem in Gaussian graphical models with arbitrary structure. We analyze the Embedded Trees algorithm, which solves a sequence of problems on tractable subgraphs thereby leading to the solution of the estimation problem on an intractable graph. Our analysis is based on the recently developed walk-sum interpretation of Gaussian estimation. We show that non-stationary iterations of the Embedded Trees algorithm using any sequence of subgraphs converge in walk-summable models. Based on walk-sum calculations, we develop adaptive methods that optimize the choice of subgraphs used at each iteration with a view to achieving maximum reduction in error. These adaptive procedures provide a significant speedup in convergence over stationary iterative methods, and also appear to converge in a larger class of models. 1
[1] M. Luettgen, W. Carl, and A. Willsky. Efficient multiscale regularization with application to optical flow. IEEE Transactions on Image Processing, 3(1):41–64, Jan. 1994.
[2] P. Rusmevichientong and B. Van Roy. An Analysis of Turbo Decoding with Gaussian densities. In Advances in Neural Information Processing Systems 12, 2000.
[3] J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kauffman, San Mateo, CA, 1988.
[4] E. Sudderth, M. Wainwright, and A. Willsky. Embedded Trees: Estimation of Gaussian processes on graphs with cycles. IEEE Transactions on Signal Processing, 52(11):3136–3150, Nov. 2004.
[5] D. Malioutov, J. Johnson, and A. Willsky. Walk-Sums and Belief Propagation in Gaussian Graphical Models. Journal of Machine Learning Research, 7:2031–2064, Oct. 2006.
[6] R. Varga. Matrix Iterative Analysis. Springer-Verlag, New York, 2000.
[7] R. Bru, F. Pedroche, and D. Szyld. Overlapping Additive and Multiplicative Schwarz iterations for Hmatrices. Linear Algebra and its Applications, 393:91–105, Dec. 2004.
[8] D. Zhou, J. Huang, and B. Scholkopf. Learning from Labeled and Unlabeled data on a directed graph. In Proceedings of the 22nd International Conference on Machine Learning, 2005.
[9] D. Zhou and C. Burges. Spectral Clustering and Transductive Learning with multiple views. In Proceedings of the 24th International Conference on Machine Learning, 2007.
[10] V. Chandrasekaran, J. Johnson, and A. Willsky. Estimation in Gaussian Graphical Models using Tractable Subgraphs: A Walk-Sum Analysis. To appear in IEEE Transactions on Signal Processing.
[11] D. Malioutov, J. Johnson, and A. Willsky. GMRF variance approximation using spliced wavelet bases. In IEEE International Conference on Acoustics, Speech and Signal Processing, 2007.
[12] R. Godement. Analysis I: Convergence, Elementary Functions. Springer-Verlag, New York, 2004.
[13] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2001.
[14] N. Srebro. Maximum Likelihood Markov Networks: An Algorithmic Approach. Master’s thesis, Massachusetts Institute of Technology, 2000.
[15] F. Kschischang, B. Frey, and H. Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2):498–519, Feb. 2001. 8