zbMATH — the first resource for mathematics

Approximate computations for binary Markov random fields and their use in Bayesian models. (English) Zbl 06737711
Summary: Discrete Markov random fields form a natural class of models to represent images and spatial datasets. The use of such models is, however, hampered by a computationally intractable normalising constant. This makes parameter estimation and a fully Bayesian treatment of discrete Markov random fields difficult. We apply approximation theory for pseudo-Boolean functions to binary Markov random fields and construct approximations and upper and lower bounds for the associated computationally intractable normalising constant. As a by-product of this process we also get a partially ordered Markov model approximation of the binary Markov random field. We present numerical examples with both the pairwise interaction Ising model and with higher-order interaction models, showing the quality of our approximations and bounds. We also present simulation examples and one real data example demonstrating how the approximations and bounds can be applied for parameter estimation and to handle a fully Bayesian model computationally.

62-XX Statistics
Full Text: DOI
[1] Austad, H.M.: Approximations of binary Markov random fields. PhD thesis, Norwegian University of Science and Technology. Thesis number 292:2011. Available from http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-14922 (2011) · Zbl 1426.62092
[2] Besag, J, Spatial interaction and the statistical analysis of lattice systems, J. R. Stat. Soc. Ser. B, 36, 192-225, (1974) · Zbl 0327.60067
[3] Besag, J, On the statistical analysis of dirty pictures (with discussion), J. R. Stat. Soc. Ser. B, 48, 259-302, (1986) · Zbl 0609.62150
[4] Clifford, P.: Markov random fields in statistics. In: Grimmett, G.R., Welsh, D.J.A. (eds.) Disorder in Physical Systems, pp. 19-31. Oxford University Press (1990) · Zbl 0736.62081
[5] Cowell, R.G., Dawid, A.P., Lauritzen, S.L., Spiegelhalter, D.J.: Probabilistic Networks and Expert Systems, Exact Computational Methods for Bayesian Networks. Springer, London (2007) · Zbl 1120.68444
[6] Cressie, N.A.C.: Statistics for Spatial Data, 2nd edn. Wiley, New York (1993) · Zbl 1347.62005
[7] Cressie, N; Davidson, J, Image analysis with partially ordered Markov models, Comput. Stat. Data Anal., 29, 1-26, (1998) · Zbl 1042.62611
[8] Ding, G; Lax, R; Chen, J; Chen, PP, Formulas for approximating pseudo-Boolean random variables, Discret. Appl. Math., 156, 1581-1597, (2008) · Zbl 1142.94397
[9] Ding, G; Lax, R; Chen, J; Chen, PP; Marx, BD, Transforms of pseudo-Boolean random variables, Discret. Appl. Math., 158, 13-24, (2010) · Zbl 1192.60030
[10] Friel, N; Rue, H, Recursive computing and simulation-free inference for general factorizable models, Biometrika, 94, 661-672, (2007) · Zbl 1135.62078
[11] Friel, N; Pettitt, AN; Reeves, R; Wit, E, Bayesian inference in hidden Markov random fields for binary data defined on large lattices, J. Comput. Graph. Stat., 18, 243-261, (2009)
[12] Gelman, A; Meng, X-L, Simulating normalizing constants: from importance sampling to bridge sampling to path sampling, Stat. Sci., 13, 163-185, (1998) · Zbl 0966.65004
[13] Geyer, CJ; Thompson, EA, Annealing Markov chain Monte Carlo with applications to ancestral inference, J. Am. Stat. Assoc., 90, 909-920, (1995) · Zbl 0850.62834
[14] Grabisch, M; Marichal, JL; Roubens, M, Equivalent representations of set functions, Math. Oper. Res., 25, 157-178, (2000) · Zbl 0982.91009
[15] Green, PJ, Reversible jump MCMC computation and Bayesian model determination, Biometrika, 82, 711-732, (1995) · Zbl 0861.62023
[16] Grelaud, A; Robert, C; Marin, JM; Rodolphe, F; Taly, JF, ABC likelihood-free methods for model choice in Gibbs random fields, Bayesian Anal., 4, 317-336, (2009) · Zbl 1330.62126
[17] Gu, MG; Zhu, HT, Maximum likelihood estimation for spatial models by Markov chain Monte Carlo stochastic approximation, J. R. Stat. Soc. Ser. B, 63, 339-355, (2001) · Zbl 0979.62060
[18] Hammer, PL; Holzman, R, Approximations of pseudo-Boolean functions; applications to game theory, Methods Models Oper. Res., 36, 3-21, (1992) · Zbl 0778.41009
[19] Hammer, P.L., Rudeanu, S.: Boolean Methods in Operation Research and Related Areas. Springer, Berlin (1968) · Zbl 0155.28001
[20] Jerrum, M; Sinclair, A, Polynomial-time approximation algorithms for the Ising model, SIAM J. Comput., 22, 1087-1116, (1993) · Zbl 0782.05076
[21] Künsch, H.R.: State space and hidden Markov models. In: Barndorff-Nielsen, O.E., Cox, D.R., Klppelberg, C. (eds.) Complex Stochastic Systems. Chapman & Hall/CRC (2001) · Zbl 0861.62023
[22] Liang, F, A double metropolis-Hastings sampler for spatial models with intractable normalizing constants, J. Stat. Comput. Simul., 80, 1007-1022, (2010) · Zbl 1233.62117
[23] Liang, F., Liu, C., Carroll, R.: Advanced Markov Chain Monte Carlo Methods: Learning from Past Samples. Wiley, New York (2011) · Zbl 1209.62009
[24] Lyne, AM; Girolami, M; Atchadé, Y; Strathmann, H; Simplson, D, On russian roulette estimates for Bayesian inference with doubly-intractable likelihoods, Stat. Sci., 30, 443-467, (2015) · Zbl 1426.62092
[25] Marin, JM; Mengersen, K; Robert, CP; Dey, DK (ed.); Rao, CR (ed.), Bayesian modelling and inference on mixtures of distributions, 253-300, (2011), Amsterdam
[26] Møller, J; Pettitt, A; Reeves, R; Berthelsen, K, An efficient Markov chain Monte Carlo method for distributions with intractable normalising constants, Biometrika, 93, 451-458, (2006) · Zbl 1158.62020
[27] Murray, I., Ghahramani, Z., MacKay, D.: Mcmc for doubly-intractable distributions. In: Proceedings of the Twenty-Second Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-06), AUAI Press, Arlington, Virginia, pp. 359-366 (2006)
[28] Propp, JG; Wilson, DB, Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Stuct. Algorithms, 9, 223-252, (1996) · Zbl 0859.60067
[29] Reeves, R; Pettitt, AN, Efficient recursions for general factorisable models, Biometrika, 91, 751-757, (2004) · Zbl 1162.62310
[30] Riggan, W.B., Creason, J.P., Nelson, W.C., Manton, K.G., Woodbury, M.A., Stallard, E., Pellom, A.C., Beaubier, J.: U.S. Cancer Mortality Rates and Trends, 1950-1979, vol. IV (U.S. Goverment Printing Office, Washington, DC: Maps, U.S. Environmental Protection Agency) (1987) · Zbl 0327.60067
[31] Sherman, M; Apanasovich, TV; Carroll, RJ, On estimation in binary autologistic spatial models, J. Stat. Comput. Simul., 76, 167-179, (2006) · Zbl 1088.62069
[32] Tjelmeland, H; Austad, H, Exact and approximate recursive calculations for binary Markov random fields defined on graphs, J. Comput. Graphical Stat., 21, 758-780, (2012)
[33] Viterbi, AJ, Error bounds for convolutional codes and an asymptotic optimum decoding algorithm, IEEE Trans. Inf. Theory, 13, 260-269, (1967) · Zbl 0148.40501
[34] Walker, S, Posterior sampling when the normalising constant is unknown, Commun. Stat. Simul. Comput., 40, 784-792, (2011) · Zbl 1216.62043
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.