Experiments in stochastic computation for high-dimensional graphical models. (English) Zbl 1130.62408

Jones, Beatrix; Carvalho, Carlos; Dobra, Adrian; Hans, Chris; Carter, Chris; West, Mike

Stat. Sci. 20, No. 4, 388-400 (2005).

Summary: We discuss the implementation, development and performance of methods of stochastic computation in Gaussian graphical models. We view these methods from the perspective of high-dimensional model search, with a particular interest in the scalability with dimension of Markov chain Monte Carlo (MCMC) and other stochastic search methods. After reviewing the structure and context of undirected Gaussian graphical models and model uncertainty (covariance selection), we discuss prior specifications, including new priors over models, and then explore a number of examples using various methods of stochastic computation. Traditional MCMC methods are the point of departure for this experimentation; we then develop alternative stochastic search ideas and contrast this new approach with MCMC. Our examples range from low (12–20) to moderate (150) dimension, and combine simple synthetic examples with data analysis from gene expression studies. We conclude with comments about the need and potential for new computational methods in far higher dimensions, including constructive approaches to Gaussian graphical modeling and computation.

MSC:

62P99	Applications of statistics
65C40	Numerical analysis or methods applied to Markov chains
65C60	Computational problems in statistics (MSC2010)

Keywords:

decomposable models; nondecomposable models; Markov chain Monte Carlo; shotgun stochastic search; parallel implementation

Software:

HdBCS

References:

[1]	Andersson, S. A., Madigan, D., Perlman, M. D. and Richardson, T. (1999). Graphical Markov models in multivariate analysis. In Multivariate Analysis, Design of Experiments and Survey Sampling (S. Ghosh, ed.) 187–229. Dekker, New York. · Zbl 1068.62515
[2]	Armstrong, H., Carter, C. K., Wong, K. F. and Kohn, R. (2005). Bayesian covariance matrix estimation using a mixture of decomposable graphical models. Unpublished manuscript.
[3]	Atay-Kayis, A. and Massam, H. (2006). The marginal likelihood for decomposable and non-decomposable graphical Gaussian models. Biometrika . · Zbl 1094.62028
[4]	Cowell, R. G., Dawid, A. P., Lauritzen, S. L. and Spiegelhalter, D. J. (1999). Probabilistic Networks and Expert Systems . Springer, New York. · Zbl 0937.68121
[5]	Dawid, A. P. and Lauritzen, S. L. (1993). Hyper-Markov laws in the statistical analysis of decomposable graphical models. Ann. Statist. 21 1272–1317. JSTOR: · Zbl 0815.62038
[6]	Dellaportas, P. and Forster, J. J. (1999). Markov chain Monte Carlo model determination for hierarchical and graphical log-linear models. Biometrika 86 615–633. JSTOR: · Zbl 0949.62050
[7]	Dellaportas, P., Giudici, P. and Roberts, G. (2003). Bayesian inference for nondecomposable graphical Gaussian models. Sankhyā 65 43–55. · Zbl 1192.62090
[8]	Dempster, A. P. (1972). Covariance selection. Biometrics 28 157–175.
[9]	Dickey, J. M. (1971). The weighted likelihood ratio, linear hypotheses on normal location parameters. Ann. Math. Statist. 42 204–223. · Zbl 0274.62020
[10]	Dobra, A. and Fienberg, S. E. (2000). Bounds for cell entries in contingency tables given marginal totals and decomposable graphs. Proc. Natl. Acad. Sci. U.S.A. 97 11,885–11,892. · Zbl 0960.62059
[11]	Dobra, A., Hans, C., Jones, B. Nevins, J., Yao, G. and West, M. (2004). Sparse graphical models for exploring gene expression data. J. Multivariate Anal. 90 196–212. · Zbl 1047.62104
[12]	Dobra, A. and West, M. (2004). Bayesian covariance selection. Available as Discussion Paper 04-23 at www.isds.duke.edu.
[13]	Flores, M. J., Gámez, J. A. and Olesen, K. G. (2003). Incremental compilation of Bayesian networks. In Proc. 19th Annual Conference on Uncertainty in Artificial Intelligence 233–240. Morgan Kaufmann, San Francisco.
[14]	Friedman, N., Linial, M., Nachman, I. and Pe’er, D. (2000). Using Bayesian networks to analyze expression data. J. Computational Biology 7 601–620.
[15]	Giudici, P. (1996). Learning in graphical Gaussian models. In Bayesian Statistics 5 (J. M. Bernardo, J. O. Berger, A. P. Dawid and A. F. M. Smith, eds.) 621–628. Oxford Univ. Press, London.
[16]	Giudici, P. and Castelo, R. (2003). Improving Markov chain Monte Carlo model search for data mining. Machine Learning 50 127–158. · Zbl 1050.68120
[17]	Giudici, P. and Green, P. J. (1999). Decomposable graphical Gaussian model determination. Biometrika 86 785–801. JSTOR: · Zbl 0940.62019
[18]	Grone, R., Johnson, C. R., de Sá, E. M. and Wolkowicz, H. (1984). Positive definite completions of partial Hermitian matrices. Linear Algebra Appl. 58 109–124. · Zbl 0547.15011
[19]	Hammersley, J. M. and Clifford, P. E. (1971). Markov fields on finite graphs and lattices. Unpublished manuscript.
[20]	Heckerman, D., Chickering, D. M., Meek, C., Rounthwaite, R. and Kadie, C. M. (2000). Dependency networks for inference, collaborative filtering, and data visualization. J. Machine Learning Research 1 49–75. · Zbl 1008.68132
[21]	Lauritzen, S. L. (1996). Graphical Models . Clarendon Press, Oxford. · Zbl 0907.62001
[22]	Lauritzen, S. L. and Sheehan, N. A. (2003). Graphical models for genetic analyses. Statist. Sci. 18 489–514. · Zbl 1055.62126
[23]	Madigan, D. and York, J. (1995). Bayesian graphical models for discrete data. Internat. Statist. Rev. 63 215–232. · Zbl 0834.62003
[24]	Roverato, A. (2002). Hyper-inverse Wishart distribution for non-decomposable graphs and its application to Bayesian inference for Gaussian graphical models. Scand. J. Statist. 29 391–411. · Zbl 1036.62027
[25]	Wermuth, N. (1976). Model search among multiplicative models. Biometrics 32 253–263. JSTOR: · Zbl 0357.62049
[26]	West, M., Blanchette, C., Dressman, H., Huang, E., Ishida, S., Spang, R., Zuzan, H., Olson, Jr., J. A., Marks, J.R. and Nevins, J. R. (2001). Predicting the clinical status of human breast cancer by using gene expression profiles. Proc. Natl. Acad. Sci. U.S.A. 98 11,462–11,467.
[27]	Whittaker, J. (1990). Graphical Models in Applied Multivariate Statistics . Wiley, Chichester. · Zbl 0732.62056
[28]	Wong, F., Carter, C. and Kohn, R. (2003). Efficient estimation of covariance selection models. Biometrika 90 809–830. · Zbl 1436.62346
[29]	Yu, J., Smith, V., Wang, P., Hartemink, A. and Jarvis, E. (2004). Advances to Bayesian network inference for generating causal networks from observational biological data. Bioinformatics 20 3594–3603. · Zbl 1078.92024
[30]	Zhou, X., Kao, M. J. and Wong, W. H. (2002). Transitive functional annotation by shortest-path analysis of gene expression data. Proc. Natl. Acad. Sci. U.S.A. 99 12,783–12,788.