×

Multiscale stochastic modeling for tractable inference and data assimilation. (English) Zbl 1197.65015

Summary: We consider a class of multiscale Gaussian models on pyramidally structured graphs. While such models have been considered in the past, very recent advances in inference methods for graphical models not only yield additional motivation for this class of models but also bring techniques that lead to new and powerful algorithms. We provide a brief summary of these recent advances - including so-called walk-sum analysis, methods based on Lagrangian relaxation, and a new method for “low-rank,” wavelet-based, unbiased estimation of error variances - and then adapt and apply them to problems of estimation for pyramidal models. We demonstrate that our models not only capture long-range dependencies but that they also have the property that conditioned on neighboring scales, the correlation behavior within a scale is dramatically compressed.
This leads to algorithms resembling multipole methods for solving partial differential equations in which we alternate computations across-scale (using an embedded tree in the pyramidal graph) with local updates within each scale. Not only are these algorithms guaranteed to converge to the correct answers but they also lead to new, adaptive methods for choosing embedded trees and subgraphs to achieve rapid convergence. This approach also leads to a solution to the so-called re-estimation problem in which we seek to update an estimate rapidly after local changes are made to the prior model or to the available data. In addition, by using a consistent probabilistic model across as well as within scales, we are able both to exploit low-rank variance estimation methods and to develop efficient iterative algorithms for parameter estimation.

MSC:

65C60 Computational problems in statistics (MSC2010)
65C20 Probabilistic models, generic numerical methods in probability and statistics
62F10 Point estimation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Willsky, A. S., Multiresolution Markov models for signal and image processing, Proc. IEEE, 90, August, 1396-1458 (2002)
[2] Johnson, J. K.; Willsky, A. S., A recursive model-reduction method for estimation in Gaussian Markov random fields, IEEE Trans. Image Process, 17, 1, 70-83 (2008)
[3] C. Graffigne, F. Heitz, P. Perez, F. Prêteux, M. Sigelle, J. Zerubia, Hierarchical Markov random field models applied to image analysis: a review, in: SPIE Conference on Neural, Morphological Stochastic Methods in Image Signal Processing, vol. 2568, 1995, pp. 12-17.; C. Graffigne, F. Heitz, P. Perez, F. Prêteux, M. Sigelle, J. Zerubia, Hierarchical Markov random field models applied to image analysis: a review, in: SPIE Conference on Neural, Morphological Stochastic Methods in Image Signal Processing, vol. 2568, 1995, pp. 12-17.
[4] F. Heitz, P. Perez, P. Bouthemy, Multiscale minimization of global energy functions in some visual recovery problems, in: CVGIP: Image Understanding, vol. 59, no. 1, 1994, pp. 125-134.; F. Heitz, P. Perez, P. Bouthemy, Multiscale minimization of global energy functions in some visual recovery problems, in: CVGIP: Image Understanding, vol. 59, no. 1, 1994, pp. 125-134.
[5] Z. Kato, M. Berthod, J. Zerubia, Multiscale Markov random field models for parallel image classification, in: Proceedings ICCV, Berlin, May 1993.; Z. Kato, M. Berthod, J. Zerubia, Multiscale Markov random field models for parallel image classification, in: Proceedings ICCV, Berlin, May 1993. · Zbl 0825.62706
[6] Kato, Z.; Berthod, M.; Zerubia, J., A hierarchical Markov random field model and multitemperature annealing for parallel image classification, Graph. Model Image Process., 58, 1, 18-37 (1996)
[7] Kato, Z.; Zerubia, J.; Berthod, M., Unsupervised parallel image classification using Markovian models, Pattern Recogn., 32, 4, 591-604 (1999)
[8] Li, J.; Gray, R. M.; Olshen, R. A., Multiresolution image classification by hierarchical modeling with two-dimensional hidden Markov models, IEEE Trans. Image Process., 46, August, 1826-1841 (2000) · Zbl 1002.94002
[9] Bollobás, B., Modern Graph Theory (1998), Springer · Zbl 0902.05016
[10] Diestel, R., Graph Theory (2000), Springer · Zbl 0945.05002
[11] M.I. Jordan, An Introduction to Graphical Models, MIT Press, in press.; M.I. Jordan, An Introduction to Graphical Models, MIT Press, in press.
[12] Lauritzen, S. L., Graphical Models (1996), Oxford University Press: Oxford University Press Oxford, UK · Zbl 0907.62001
[13] Jordan, M. I., Graphical models, Stat. Sci., 19, 140-155 (2004), (Special Issue on Bayesian Statistics) · Zbl 1057.62001
[14] Pearl, J., Probabilistic Reasoning in Intelligent Systems (1988), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA
[15] J.K. Johnson, V. Chandrasekaran, A.S. Willsky, Learning Markov structure by maximum entropy relaxation, in: 11th International Conference on Artificial Intelligence and Statistics (AISTATS’07), San Juan, Puerto Rico, March 2007.; J.K. Johnson, V. Chandrasekaran, A.S. Willsky, Learning Markov structure by maximum entropy relaxation, in: 11th International Conference on Artificial Intelligence and Statistics (AISTATS’07), San Juan, Puerto Rico, March 2007.
[16] Kailath, T.; Sayed, A. H.; Hassibi, B., Linear Estimation (2000), Prentice Hall
[17] Plarre, K.; Kumar, P., Extended message passing algorithm for inference in loopy Gaussian graphical models, Ad Hoc Networks (2004)
[18] Malioutov, D. M.; Johnson, J. K.; Willsky, A. S., Walk-sums and belief propagation in Gaussian graphical models, J. Mach. Learning Res., 7, October, 2003-2030 (2006)
[19] Weiss, Y.; Freeman, W. T., Correctness of belief propagation in Gaussian graphical models of arbitrary topology, Neural Computat., 13, 2173-2200 (2001) · Zbl 0992.68055
[20] Luettgen, M. R.; Karl, W. C.; Willsky, A. S.; Tenney, R. R., Multiscale representations of Markov random fields, IEEE Trans. Signal Process., 41, December, 3377-3396 (1993) · Zbl 0844.60087
[21] J.K. Johnson, Estimation of GMRFs by recursive cavity modeling, Master’s thesis, MIT, Cambridge, MA, March 2003.; J.K. Johnson, Estimation of GMRFs by recursive cavity modeling, Master’s thesis, MIT, Cambridge, MA, March 2003.
[22] J.K. Johnson, D.M. Malioutov, A.S. Willsky, Walk-sum interpretation and analysis of Gaussian belief propagation, in: advances in Neural Information Processing Systems, vol. 18, 2006, pp. 579-586.; J.K. Johnson, D.M. Malioutov, A.S. Willsky, Walk-sum interpretation and analysis of Gaussian belief propagation, in: advances in Neural Information Processing Systems, vol. 18, 2006, pp. 579-586.
[23] V. Chandrasekaran, J.K. Johnson, A.S. Willsky, Estimation in Gaussian graphical models using tractable subgraphs: A walk-sum analysis, IEEE Trans. Signal Process., in press.; V. Chandrasekaran, J.K. Johnson, A.S. Willsky, Estimation in Gaussian graphical models using tractable subgraphs: A walk-sum analysis, IEEE Trans. Signal Process., in press. · Zbl 1391.62187
[24] Sudderth, E. B.; Wainwright, M. J.; Willsky, A. S., Embedded trees: estimation of Gaussian processes on graphs with cycles, IEEE Trans. Signal Process., 52, 11, 3136-3150 (2004) · Zbl 1370.94248
[25] J.K. Johnson, D.M. Malioutov, A.S. Willsky, Lagrangian relaxation for MAP estimation in graphical models, in: 45th Annual Allerton Conference on Communication, Control and Computing, 2007.; J.K. Johnson, D.M. Malioutov, A.S. Willsky, Lagrangian relaxation for MAP estimation in graphical models, in: 45th Annual Allerton Conference on Communication, Control and Computing, 2007.
[26] Wainwright, M. J.; Jaakkola, T. S.; Willsky, A. S., A new class of upper bounds on the log partition function, IEEE Trans. Inform. Theory, 51, 7, 2313-2335 (2005) · Zbl 1310.94028
[27] Wainwright, M. J.; Jaakkola, T. S.; Willsky, A. S., MAP estimation via agreement on (hyper) trees: Message-passing and linear-programming approaches, IEEE Trans. Inform. Theory, 51, 11, 3697-3717 (2005) · Zbl 1318.94025
[28] Kolmogorov, V., Convergent tree-reweighted message passing for energy minimization, IEEE Trans. on Pattern. and Mach. Intell., 28, 10, 1568-1583 (2006)
[29] J.K. Johnson, Convex relaxation methods for graphical models, MIT, Cambridge, MA, in preparation.; J.K. Johnson, Convex relaxation methods for graphical models, MIT, Cambridge, MA, in preparation.
[30] M.J. Choi, Multiscale Gaussian graphical models and algorithms for large-scale inference, Master’s thesis, MIT, Cambridge, MA, May 2007.; M.J. Choi, Multiscale Gaussian graphical models and algorithms for large-scale inference, Master’s thesis, MIT, Cambridge, MA, May 2007.
[31] D.M. Malioutov, J.K. Johnson, A.S. Willsky, Low-rank variance estimation in large-scale GMRF models, in: IEEE International Conference on Acoustics, Speech, and Signal Processing, Toulouse, France, May 2006.; D.M. Malioutov, J.K. Johnson, A.S. Willsky, Low-rank variance estimation in large-scale GMRF models, in: IEEE International Conference on Acoustics, Speech, and Signal Processing, Toulouse, France, May 2006.
[32] D.M. Malioutov, J.K. Johnson, A.S. Willsky, GMRF variance approximation using spliced wavelet bases, in: IEEE International Conference on Acoustics, Speech, and Signal Processing, Honolulu, Hawaii, April 2007.; D.M. Malioutov, J.K. Johnson, A.S. Willsky, GMRF variance approximation using spliced wavelet bases, in: IEEE International Conference on Acoustics, Speech, and Signal Processing, Honolulu, Hawaii, April 2007.
[33] Gidas, B., A renormalization group approach to image processing problems, IEEE Trans. Pattern Anal. Mach. Intell., 11, 2, 164-180 (1989) · Zbl 0709.68606
[34] Briggs, W. L., A Multigrid Tutorial (1987), SIAM: SIAM Philadelphia, PA · Zbl 0659.65095
[35] Daoudi, K.; Frakt, A. B.; Willsky, A. S., Multiscale autoregressive models and wavelets, IEEE Trans. Inform. Theory, 45, 3, 828-845 (1999) · Zbl 0946.94005
[36] Fieguth, P. W.; Karl, W. C.; Willsky, A. S., Efficient multiresolution counterparts to variational methods for surface reconstruction, Comput. Vision Image Underst., 70, 2, 157-176 (1998) · Zbl 0933.68145
[37] Greengard, L.; Rokhlin, V., A fast algorithm for particle simulations, J. Comput. Phys., 73, 2, 325-348 (1987) · Zbl 0629.65005
[38] Dempster, A. P.; Laird, N. M.; Rubin, D. B., Maximum-likelihood from incomplete data via the EM algorithm, J. Roy. Stat. Soc., 39, 1-38 (1977) · Zbl 0364.62022
[39] Wainwright, M. J.; Simoncelli, E. P.; Willsky, A. S., Random cascades on wavelet trees and their use in modeling natural images, Appl. Computat. Harmonic Anal., 11, 89-123 (2001) · Zbl 0983.68228
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.