A novel approach for Markov random field with intractable normalizing constant on large lattices. (English) Zbl 07498967
Summary: The pseudo likelihood method of J. Besag [J. R. Stat. Soc., Ser. B 36, 192–236 (1974; Zbl 0327.60067)] has remained a popular method for estimating Markov random field on a very large lattice, despite various documented deficiencies. This is partly because it remains the only computationally tractable method for large lattices. We introduce a novel method to estimate Markov random fields defined on a regular lattice. The method takes advantage of conditional independence structures and recursively decomposes a large lattice into smaller sublattices. An approximation is made at each decomposition. Doing so completely avoids the need to compute the troublesome normalizing constant. The computational complexity is \(O(N)\), where \(N\) is the number of pixels in the lattice, making it computationally attractive for very large lattices. We show through simulations, that the proposed method performs well, even when compared with methods using exact likelihoods. Supplementary material for this article is available online.
MSC:
| 62-XX | Statistics |
Keywords:
conditional independence; decomposition; Markov chain Monte Carlo; normalizing constant; Potts modelCitations:
Zbl 0327.60067References:
| [1] | Aizenman, M.; Chayes, J.; Chayes, L.; Newman, C., Discontinuity of the Magnetization in One-Dimensional Ising and Potts Models, Journal of Statistical Physics, 50, 1-40 (1988) · Zbl 1084.82514 |
| [2] | Barkema, G.; de Boer, J., Numerical Study of Phase Transitions in Potts Models, Physical Review A, 44, 8000-8005 (1991) |
| [3] | Bartolucci, F.; Besag, J., A Recursive Algorithm for Markov Random Fields, Biometrika, 89, 724-730 (2002) · Zbl 1036.62098 |
| [4] | Besag, J., Spatial Interaction and the Statistical Analysis of Lattice Systems,, Journal of the Royal Statistical Society, 36, 192-236 (1974) · Zbl 0327.60067 |
| [5] | Brodatz, P., Textures: A Photographic Album for Artists and Designers, Vol. 66 (1966), New York: Dover, New York |
| [6] | Celeux, G.; Forbes, F.; Peyrard, N., EM Procedures Using Mean Field-Like Approximations for Markov Model-Based Image Segmentation, Pattern Recognition, 36, 131-144 (2003) · Zbl 1010.68158 |
| [7] | Cressie, N.; Davidson, J. L., Image Analysis With Partially Ordered Markov Models, Computational Statistics & Data Analysis, 29, 1-26 (1998) · Zbl 1042.62611 |
| [8] | Cressie, N. A.; Cassie, N. A., Statistics for Spatial Data, Vol. 900 (1993), New York: Wiley, New York |
| [9] | Everitt, R. G., Bayesian Parameter Estimation for Latent Markov Random Fields and Social Networks, Journal of Computational and Graphical Statistics, 21, 940-960 (2012) |
| [10] | Feng, D., Bayesian Hidden Markov Normal Mixture Models With Application to MRI Tissue Classification, (2008) |
| [11] | Feng, D.; Tierney, L.; Magnotta, V., MRI Tissue Classification Using High-Resolution Bayesian Hidden Markov Normal Mixture Models, Journal of the American Statistical Association, 107, 102-119 (2012) · Zbl 1261.62089 |
| [12] | Friel, N.; Pettitt, A.; Reeves, R.; Wit, E., Bayesian Inference in Hidden Markov Random Fields for Binary Data Defined on Large Lattices, Journal of Computational and Graphical Statistics, 18, 243-261 (2009) |
| [13] | Gelman, A.; Meng, X.-L., Simulating Normalizing Constants: From Importance Sampling to Bridge Sampling to Path Sampling, Statistical Science, 13, 163-185 (1998) · Zbl 0966.65004 |
| [14] | Geyer, C. J.; Thompson, E. A., Constrained Monte Carlo Maximum Likelihood for Dependent Data, Journal of the Royal Statistical Society, 54, 657-699 (1992) |
| [15] | Green, P. J.; Richardson, S., Hidden Markov Models and Disease Mapping, Journal of the American Statistical Association, 97, 1055-1070 (2002) · Zbl 1046.62117 |
| [16] | Gu, M. G.; Zhu, H.-T., Maximum Likelihood Estimation for Spatial Models by Markov Chain Monte Carlo Stochastic Approximation,, Journal of the Royal Statistical Society, 63, 339-355 (2001) · Zbl 0979.62060 |
| [17] | Haindl, M.; Remeš, V.; Havlíček, V., 21st International Conference on Pattern Recognition (ICPR), Tsukuba, Potts Compound Markovian Texture Model,, 29-32 (2012) |
| [18] | Hurn, M. A.; Husby, O. K.; Rue, H.; Møller, J., Spatial Statistics and Computational Methods, 173, A Tutorial on Image Analysis,, 87-141 (2003), New York: Springer, New York · Zbl 1255.62185 |
| [19] | Kasetkasem, T.; Arora, M. K.; Varshney, P. K., Super-Resolution Land Cover Mapping Using a Markov Random Field Based Approach, Remote Sensing of Environment, 96, 302-314 (2005) |
| [20] | Knorr-Held, L.; Rue, H., On Block Updating in Markov Random Field Models for Disease Mapping, Scandinavian Journal of Statistics, 29, 597-614 (2002) · Zbl 1039.62092 |
| [21] | Kosterlitz, J., The Critical Properties of the Two-Dimensional xy Model, Journal of Physics C, Solid State Physics, 7, 1046-1060 (1974) |
| [22] | Li, J.; Najmi, A.; Gray, R. M., Image Classification by a Two-Dimensional Hidden Markov Model, IEEE Transactions on Signal Processing, 48, 517-533 (2000) |
| [23] | Li, S. Z.; Singh, S., , Markov Random Field Modeling in Image Analysis, 3 (2009), London: Springer, London · Zbl 1183.68691 |
| [24] | Liang, F., Continuous Contour Monte Carlo for Marginal Density Estimation With an Application to a Spatial Statistical Model, Journal of Computational and Graphical Statistics, 16, 608-632 (2007) |
| [25] | ———, A Double Metropolis-Hastings Sampler for Spatial Models With Intractable Normalizing Constants, Journal of Statistical Computation and Simulation, 80, 1007-1022 (2010) · Zbl 1233.62117 |
| [26] | Liang, F.; Jin, I. H.; Song, Q.; Liu, J. S., An Adaptive Exchange Algorithm for Sampling From Distributions With Intractable Normalising Constants, Journal of the American Statistical Association, 111, 377-393 (2016) |
| [27] | Lillesand, T.; Kiefer, R. W.; Chipman, J., Remote Sensing and Image Interpretation (2014), New York: Wiley, New York |
| [28] | Lindsay, B. G., Composite Likelihood Methods, Contemporary Mathematics, 80, 221-239 (1988) · Zbl 0672.62069 |
| [29] | Luijten, E.; Blöte, H. W., Monte Carlo Method for Spin Models With Long-Range Interactions, International Journal of Modern Physics C, 6, 359-370 (1995) |
| [30] | Lyne, A.-M.; Girolami, M.; Atchad’e, Y.; Strathmann, H.; Simpson, D., On Russian Roulette Estimates for Bayesian Inference With Doubly-Intractable Likelihoods, Statistical Science, 30, 443-467 (2015) · Zbl 1426.62092 |
| [31] | Menéndez, P.; Fan, Y.; Garthwaite, P. H.; Sisson, S. A., Simultaneous Adjustment of Bias and Coverage Probabilities for Confidence Intervals, Computational Statistics & Data Analysis, 70, 35-44 (2014) · Zbl 1471.62138 |
| [32] | Møller, J.; Pettitt, A. N.; Reeves, R.; Berthelsen, K. K., An Efficient Markov Chain Monte Carlo Method for Distributions With Intractable Normalising Constants, Biometrika, 93, 451-458 (2006) · Zbl 1158.62020 |
| [33] | Monahan, J. F.; Boos, D. D., Proper Likelihoods for Bayesian Analysis, Biometrika, 79, 271-278 (1992) · Zbl 0751.62012 |
| [34] | Moores, M. T.; Pettitt, A. N.; Mengersen, K., Scalable Bayesian Inference for the Inverse Temperature of a Hidden Potts Model,, arXiv preprint arXiv:1503.08066 (2015) |
| [35] | Murray, I., Advances in Markov Chain Monte Carlo Methods, (2007) |
| [36] | Murray, I.; Ghahramani, Z.; MacKay, D. J. C., Proceedings of the 22nd Annual Conference on Uncertainty in Artificial Intelligence (UAI-06), MCMC for Doubly-Intractable Distributions,, 359-366 (2006), AUAI Press |
| [37] | Nott, D. J.; Rydén, T., Pairwise Likelihood Methods for Inference in Image Models, Biometrika, 86, 661-676 (1999) · Zbl 0938.62108 |
| [38] | Pal, N. R.; Pal, S. K., A Review on Image Segmentation Techniques, Pattern Recognition, 26, 1277-1294 (1993) |
| [39] | Pauli, F.; Racugno, W.; Ventura, L., Bayesian Composite Marginal Likelihoods, Statistica Sinica, 21, 149-164 (2011) · Zbl 1206.62039 |
| [40] | Potts, R. B., Mathematical Proceedings of the Cambridge Philosophical Society, 48, Some Generalized Order-Disorder Transformations,, 106-109 (1952), Cambridge University Press · Zbl 0048.45601 |
| [41] | Propp, J. G.; Wilson, D. B., Exact Sampling With Coupled Markov Chains and Applications to Statistical Mechanics, Random Structures and Algorithms, 9, 223-252 (1998) · Zbl 0859.60067 |
| [42] | Reeves, R.; Pettitt, A. N., Efficient Recursions for General Factorisable Models, Biometrika, 91, 751-757 (2004) · Zbl 1162.62310 |
| [43] | Rellier, G.; Descombes, X.; Falzon, F.; Zerubia, J., Texture Feature Analysis Using a Gauss-Markov Model in Hyperspectral Image Classification, IEEE Transactions on Geoscience and Remote Sensing, 42, 1543-1551 (2004) |
| [44] | Sanyal, J.; Lu, X., Application of Remote Sensing in Flood Management With Special Reference to Monsoon Asia: A Review, Natural Hazards, 33, 283-301 (2004) |
| [45] | Solberg, A. H. S.; Taxt, T.; Jain, A. K., A Markov Random Field Model for Classification of Multisource Satellite Imagery, IEEE Transactions on Geoscience and Remote Sensing, 34, 100-113 (1996) |
| [46] | Van Leemput, K.; Maes, F.; Vandermeulen, D.; Suetens, P., Automated Model-Based Tissue Classification of MR Images of the Brain, IEEE Transactions on Medical Imaging, 18, 897-908 (1999) |
| [47] | Varin, C.; Reid, N. M.; Firth, D., An Overview of Composite Likelihood Methods, Statistica Sinica, 21, 5-42 (2011) · Zbl 1534.62022 |
| [48] | Wang, Y.; Colby, J.; Mulcahy, K., An Efficient Method for Mapping Flood Extent in a Coastal Floodplain Using Landsat TM and DEM Data, International Journal of Remote Sensing, 23, 3681-3696 (2002) |
| [49] | Watchareeruetai, U.; Takeuchi, Y.; Matsumoto, T.; Kudo, H.; Ohnishi, N., Computer Vision Based Methods for Detecting Weeds in Lawns, Machine Vision and Applications, 17, 287-296 (2006) |
| [50] | Wilkinson, D. J., Parallel Bayesian Computation, 184, 477-513 (2006), Boca Raton, FL: Marcel Dekker Ag/CRC Press |
| [51] | Winkler, G., Image Analysis, Random Fields and Markov Chain Monte Carlo Methods: A Mathematical Introduction, 27 (2003), Berlin Heidelberg: Springer Verlag, Berlin Heidelberg · Zbl 1008.68147 |
| [52] | Wu, F.-Y., The Potts Model, Reviews of Modern Physics, 54, 235-268 (1982) |
| [53] | Zhao, Y.; Zhang, L.; Li, P.; Huang, B., Classification of High Spatial Resolution Imagery Using Improved Gaussian Markov Random-Field-Based Texture Features, IEEE Transactions on Geoscience and Remote Sensing, 45, 1458-1468 (2007) |
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.
