Rigat, Fabio, 1975- and Mira, Antonietta (2009) Parallel hierarchical sampling : a general-purpose class of multiple-chains MCMC algorithms. Working Paper. University of Warwick. Centre for Research in Statistical Methodology, Coventry.

Preview

PDF WRAP_Rigat_09-37v2w.pdf - Published Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (2867Kb)

Abstract

This paper introduces the Parallel Hierarchical Sampler (PHS), a class of Markov chain Monte Carlo algorithms using several interacting chains having the same target distribution but different mixing properties. Unlike any single-chain MCMC algorithm, upon reaching stationarity one of the PHS chains, which we call the "mother" chain, attains exact Monte Carlo sampling of the target distribution of interest. We empirically show that this translates in a dramatic improvement in the sampler's performance with respect to single-chain MCMC algorithms. Convergence of the PHS joint transition kernel is proved and its relationships with single-chain samplers, Parallel Tempering (PT) and variable augmentation algorithms are discussed. We then provide two illustrative examples comparing the accuracy of PHS with that of various Metropolis-Hastings and PT for sampling multimodal mixtures of multivariate Gaussian densities and for 'banana-shaped' multivariate distributions with heavy tails. Finally, PHS is applied to approximate inferences for two Bayesian model uncertainty problems, namely selection of main effects for a linear Gaussian multiple regression model and inference for the structure of an exponential treed survival model.

Item Type:	Working or Discussion Paper (Working Paper)
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Statistics
Library of Congress Subject Headings (LCSH):	Markov processes, Monte Carlo method, Sampling (Statistics)
Series Name:	Working papers
Publisher:	University of Warwick. Centre for Research in Statistical Methodology
Place of Publication:	Coventry
Date:	2009
Volume:	Vol.2009
Number:	No.37
Number of Pages:	55
Status:	Not Peer Reviewed
Access rights to Published version:	Open Access
Funder:	University of Insubria, Italy. Ministero dell'istruzione, dell'università e della ricerca (MIUR)
Grant number:	2007XECZ7L 003 (MIUR)
References:	A. Antoniadis, G. Gr´egoire, and G. Nason. Density and hazard rate estimation for right-censored data by using wavelet methods. Journal of the Royal Statistical Society B, 61:63–84, 1999. Y.F. Atchad´e and J.S. Rosenthal. On adaptive Markov chain Monte Carlo algorithms. Bernoulli, 11:815–828, 2005. K.B. Athreya, H. Doss, and J. Sethuraman. On the convergence of the Markov Chain simulation method. The Annals of Statistics, 24:69–100, 1996. Y. Bai. Simultaneous drift conditions for adaptive Markov chain Monte Carlo algorithms. University of Toronto Preprint, 2009. Y. Bai, G.O. Roberts, and J.S. Rosenthal. On the containment condition for adaptive Markov chain Monte Carlo algorithms. University of Toronto Preprint, 2009. M.M. Barbieri and J.O. Berger. Optimal predictive model selection. The Annals of Statistics, 3:870–897, 2004. M. B´edard and J.S. Rosenthal. Optimal scaling of Metropolis algorithms: Heading towards general target distributions. The Canadian Journal of Statistics, 36: 483–502, 2008. F. Berrino, A. Verdecchia, J.M. Lutz, C. Lombardo, A. Micheli, and R. Capocaccia. Comparative cancer survival information in Europe. European Journal of Cancer, 45:901–908, 2009. L. Breiman. Random forests. Machine Learning, 45:5–32, 2001. L. Breiman. Population theory for boosting ensembles. The Annals of Statistics, 32:1–11, 2004. L. Breiman. Bagging predictors. Machine Learning, 24:123–140, 1996. L. Breiman, J.H. Friedman, R.A. Olshen, and C.J. Stone. Classification and Re- gression Trees. Chapman and Hall, New York, 1984. A.E. Brockwell and J.B. Kadane. Identification of regeneration times in MCMC simulation, with applications to adaptive schemes. Journal of Computational and Graphical Statistics, 14:436–458, 2005. S. P. Brooks and G.O. Roberts. Assessing convergence of Markov chain Monte Carlo algorithms. Statistics and Computing, 8:319–335, 1998. S.P. Brooks. MCMC convergence diagnosis via ultivariate bounds on log-concave densities. The Annals of Statistics, 26:398–433, 1998. S.P. Brooks, P. Giudici, and G.O. Roberts. Efficient construction of Reversible Jump MCMC proposal distributions. Journal of the Royal Statistical Society B, 65:3–55, 2003. O. Capp´e and C.P. Robert. Markov chain Monte Carlo: 10 years and still running! Journal of the American Statistical Association, 95:1282–1286, 2000. O. Capp´e, G.O. Roberts, and T. Ryden. Reversible jump, birth-and-death and more general continuous time Markov chain Monte Carlo samplers. Journal of the Royal Statistical Society B, 65:679–700, 2003. B.P. Carlin and S. Chib. Bayesian model choice via Markov chain Monte Carlo methods. Journal of the Royal Statistical Society B, 57, 1995. G. Celeux, M. Hurn, and C.P. Robert. Computational and inferential difficulties with mixture posterior distributions. Journal of the American Statistical Asso- ciation, 95:957–970, 2000. D. Chauveau and P. Vandekerkhove. Improving convergence of the Hastings- Metropolis algorithm with a learning proposal. Scandinavian Journal of Statis- tics, 29:13–29, 2002. Hugh A. Chipman, Edward I. George, and Robert E. McCulloch. Bayesian CART model search. Journal of the American Statistical Society, 93:935–947, 1998. M. Clyde and E.I. George. Model Uncertainty. Statistical Science, 19:81–94, 2004. J. Corander, M. Gyllenberg, and T. Koski. Bayesian model learning based on a parallel MCMC strategy. Statistics and Computing, 16:355–362, 2006. M.K. Cowles and B.P. Carlin. Markov chain Monte Carlo algorithms convergence diagnostics: a comparative reiview. Journal of the American Statistical Associ- ation, 91:883–904, 1996. R.V. Craiu and X.L. Meng. Multi-process parallel antithetic coupling for forward and backward Markov chain Monte Carlo. The Annals of Statistics, 33:661–697, 2005. R.V. Craiu, J.S. Rosenthal, and C. Yang. Learn from thy neighbor: Parallel-chain adaptive MCMC. Journal of the American Statistical Association, To Appear, 2009. R.B. Davis and J.R. Anderson. Exponential survival trees. Statistics in Medicine, 8, 1989. P. Dellaportas, J.J. Forster, and I. Ntzoufras. On Bayesian model and variable selection using MCMC. Statistics and Computing, 12:27–36, 2002. D.G.T. Denison, B.K. Mallick, and A.F.M. Smith. A Bayesian CART algorithm. Biometrika, 85, 1998. S. Duane, A. D. Kennedy, B. J. Pendleton, and D. Roweth. Hybrid Monte Carlo. Physics Letters B, 195:216–222, 1987. J.M Flegal, M. Haran, and J.L. Jones. Markov chain Monte Carlo: can we trust the third significant figure? Statistical Science, 23:250–260, 2008. D. Gamerman. Markov chain Monte Carlo: Stochastic Simulation for Bayesian Inference. Chapman and Hall, 1997. J. Gasemyr. On an adaptive version of the Metropolis-Hastings algorithm with independent proposal distribution. Scandinavian Journal of Statistics, 30:159– 173, 2003. A.E. Gelfand and S.K. Sahu. On Markov chain Monte Carlo acceleration. Journal of Computational and Graphical Statistics, 3:261–276, 1994. A.E. Gelfand and A. F. M. Smith. Sampling-based approaches to calculating marginal densities. Journal of the American Statistical Society, 85:398–409, 1990. E.I. George and R.E. McCulloch. Approaches for Bayesian variable selection. Sta- tistica Sinica, 7:339–373, 1997. E.I. George and R.E. McCulloch. Variable selection via Gibbs sampling. Journal of the American Statistical Association, 88:882–889, 1993. J. Geweke. Evaluating the accuracy of sampling-based approaches to the calculation of posterior moments. In: Bayesian Statistics 4, J.M. Bernardo, J.O. Berger, A.P. Dawid and A.F.M. Smith editors; Oxford Press, pages 169–194, 1992. C. J. Geyer and E.A. Thompson. Annealing Markov Chain Monte Carlo with applications to ancestral inference. Journal of the American Statistical Association, 90:909–920, 1995. C.J. Geyer. Markov chain Monte Carlo maximum likelihood. Computing Science and Statistics: Proceedings on the 23rd Symposium on the Interface, New York, 1991. W.R. Gilks and P. Wild. Adaptive rejection sampling for Gibbs sampling. Journal of the Royal Statistical Society C, 41:337–348, 1992. W.R. Gilks, G.O. Roberts, and E.I. George. Adaptive direction sampling. The Statistician, 43:179–189, 1994. W.R. Gilks, N.G. Best, and K.K.C. Tan. Adaptive rejection Metropolis sampling within Gibbs sampling. Applied Statistics, 44:455–472, 1995a. W.R. Gilks, S. Richardson, and D. J. Spiegelhalter. Markov chain Monte Carlo in practice. Chapman and Hall, 1995b. W.R. Gilks, N.G. Best, and K.K.C. Tan. Adaptive Markov chain Monte Carlo through regeneration. Journal of the American Statistical Association, 93:1045– 1054, 1998. J. Gill and G. Casella. Dynamic tempered transitions for exploring multimodal posterior distributions. Political Analysis, 12:425–443, 2004. L. Gordon and R.A. Olshen. Tree-structured survival analysis. Cancer Treatment Reports, 69, 1995. P.H. Green. Reversible Jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika, 82:711–732, 1995. P.J. Green and X.L Han. Metropolis methods, Gaussian proposals and antithetic variables. Lecture notes in Statistics, 74:142–164, 1991. P.J. Green and A. Mira. Delayed rejection in reversible jump Metropolis Hastings. Biometrika, 88:1035–1053, 2001. M.P.W. Grocott, D.S. Martin, D.Z.H Levett, H. Montgomery, and M.G. Mythen. Caudwell Xtreme Everest. Anaesthesia and Analegesia, 6:81–84, 2008. H. Haario, E. Saksman, and J. Tamminen. Adaptive proposal distribution for random walk metropolis algorithm, 1999. H. Haario, E. Saksman, and J. Tamminen. An adaptive Metropolis algorithm. Bernoulli, 7:223–242, 2001. H. Haario, E. Saksman, and J. Tamminen. Component-wise adaptatation for highdimensional MCMC. Computational Statistics, 20:265–273, 2005. H. Haario, M Laine, A. Mira, and E. Saksman. DRAM: efficient adaptive MCMC. Statistics and Computing, 16:339–354, 2006. U.H.E. Hansmann. Parallel tempering algorithm for conformational studies of biological molecules. Chem. Phys. Lett., 281:140–152, 1997. G. Haupt and U. Mansmann. Survival trees in Splus. Advances in Statistical Software 5, pages 615–622, 1995. P. Hermanek and F.P. Gall. Uicc Studie zur Klassifikation von Lebermetastasen. Chirurgie der Lebermetastasen und primaren malignen Tumoren, 1990. T.K. Ho. The random subspace method for constructing decision forests. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20:832 – 844, 1998. B. Hu and K-W. Tsui. Distributed evolutionary Monte Carlo for Bayesian computing. Computational Statistics and Data Analysis, doi:10.1016/j.csda.2008.10.025, 2008. J.P. Huelsembeck, B. Larget, R.E. Miller, and F. Ronquist. Potential applications and pitfalls of Bayesian inference of phylogeny. Syst. Biol., 51:673–688, 2002. J.P. Huelsembeck, B. Larget, and M.E. Alfaro. Bayesian phylogenetic model selection using reversible jump Markov chain Monte Carlo. Mol. Biol. Evol., 21: 1123–1133, 2004. J.P. Huelsenbeck and F. Ronquist. Bayesian analysis of molecular evolution using MrBayes. Statistical methods in molecular evolution, 2:183–226, 2005. K. Hukushima and K. Nemoto. Exchange Monte Carlo method and application to Spin Glass simulations. Journal of the Physical Society of Japan, 65:1604–1620, 1996. D. Husmeier and G. McGuire. Detecting recombination in 4-taxa DNA sequence alignments with Bayesian hidden Markov models and Markov chain Monte Carlo. Mol. Biol. Evol., 20:315–337, 2003. Y. Iba. Extended ensemble Monte Carlo. International Journal of Modern Physics, 12:623–656, 2001. S.F. Jarner and G.O. Roberts. Polynomial convergence rates of Markov chains. The Annals of Applied Probability, 12:224–247, 2002. A. Jasra, D.A. Stephens, and C.C. Holmes. Population-based reversible jump Markov chain Monte Carlo. Biometrika, 94:787–807, 2007. A. Kottas. Nonparametric Bayesian survival analysis using mixtures of Weibull distributions. Journal of Statistical Planning and Inference, 136:578–596, 2006. L. Kuo and B. Mallick. Variable selection for regression models. Sankhya B, 60: 65–81, 1998. C. Lakner, P. Van der Mark, J.P. Huelsenbeck, B. Larget, and F. Ronquist. Efficiency of Markov chain Monte Carlo tree proposals in Bayesian phylogenetics. Syst. Biol., 57:86–103, 2008. M. Li. Bayesian discovery of regulatory motifs using reversible jump Markov chain Monte Carlo. PhD thesis, University of Washington, 2006. S. Li, D.K. Pearl, and H. Doss. Phylogenetic tree construction using Markov chain Monte Carlo. Journal of the American Statistical Association, 95:493–508, 2000. F. Liang and W.H. Wong. Real-parameter evolutionary Monte Carlo with applications to Bayesian mixture models. Journal of the American Statistical Associa- tion, 96:653–666, 2001. C.Y. Lin, C.H. Hu, and U.H.E. Hansmann. Parallel tempering simulations of HP- 36. Proteins: Structure, Functions and Genetics, 53:436–445, 2003. J.S. Liu. Monte Carlo Strategies in Scientific computing. Springer, 2001. J.S. Liu and C. Sabatti. Simulated sintering: Markov chain Monte Carlo with spaces of varying dimensions. Bayesian Statistics, 6:389–403, 1998. J.S. Liu, F. Liang, and W.H. Wong. Dynamic weighting in Monte Carlo and optimization. Journal of the American Statistical Association, 94:14220–14224, 1997. J.S. Liu, F. Liang, andW.H.Wong. The multiple-try method and local optimization in Metropolis sampling. Journal of the American Statistical Association, 95:121– 134, 2000. J.S. Liu, F. Liang, and W.H. Wong. A theory for dynamic weighting in Monte Carlo computation. Proceedings of the National Academy of Sciences, 96:561– 573, 2001. D.J. Lunn, A. Thomas, N. Best, and D. Spiegelhalter. WinBUGS - A Bayesian modelling framework: Concepts, structure, and extensibility. Statistics and Com- puting, 10:325–337, 2000. G. Lunter, I. Miklos, A. Drummond, J.L. Jensen, and J. Hein. Bayesian coestimation of phylogeny and sequence alignment. BMC Bioinformatics, 6:83–93, 2005. B. Mau, M.A. Newton, and B. Larget. Bayesian phylogenetic inference via Markov chain Monte Carlo methods. Biometrics, 55:1–12, 1999. I.W. McKeague and W. Wefelmeyer. Markov chain Monte Carlo and Rao- Blackwellization. Journal of Statistical Planning and Inference, 85:171–182, 2000. K.L. Mengersen and R.L. Tweedie. Rates of convergence of the Hastings and Metropolis algorithms. The Annals of Statistics, 24:101–121, 1996. N. Metropolis and S. Ulam. The Monte Carlo method. Journal of the American Statistical Association, 44:335–341, 1949. N. Metropolis, A. Rosenbluth, M. Rosenbluth, M. Teller, and E. Teller. Equations of state calculations by fast computing machines. J. Chem. Phys., 21:1087–2092, 1953. S. Meyn and R.L. Tweedie. State-dependent criteria for convergence of Markov chains. The Annals of Applied Probability, 4:149–168, 1994. A. Mira. Ordering and improving the performance of Monte Carlo Markov chains. Statistical Science, 16:340–350, 2001. A. Mira and C. Geyer. Ordering Monte Carlo Markov chains. Technical Report 632, School of Statistics, University of Minnesota, 1999. A. Mira and D.J. Sargent. A new strategy for speeding Markov chain Monte Carlo algorithms. Statistical Methods and Applications, 12:49–60, 2003. T.J. Mitchell and J.J. Beauchamp. Bayesian variable selection in linear regression. Journal of the American Statistical Association, 83:1023–1032, 1988. M.Leblanch and J.Crowley. Relative risk trees for censored survival data. Biomet- rics, 48, 1992a. M.Leblanch and J.Crowley. Survival trees by goodness of split. Journal of the American Statistical Association, 88, 1992b. E. Mossel and E. Vigoda. Phylogenetic MCMC algorithms are misleading on mixtures of trees. Sience, 309:2207–2209, 2005. E. Mossel and E. Vigoda. Limitations of Markov chain Monte Carlo algorithms for inference of phylogeny. The Annals of Applied Probability, 16:2215–2234, 2006. J.W. Myers and K.B. Laskey. Population Markov chain Monte Carlo. Machine Learning, 50:175–196, 2001. P. Neal and G.O. Roberts. Optimal scaling for partially updating MCMC algorithms. The Annals of Applied Probability, 16:475–515, 2006. P. Neal, G.O. Roberts, and J. Yuen. Optimal scaling of of random walk Metropolis algorithms with discontinous target densities. University of Manchester Technical Report, 1, 2007. R. Neal. Slice sampling. Technical report No. 2005 - Dept. of Statistics, University of Toronto, 2000. R.M. Neal. Sampling from multimodal distributions using tempered transitions. Statistics and Computing, 6:353–366, 1996. R.M. Neal. Probabilistic inference using Markov chain Monte Carlo methods. Tech- nical report, Department of Computer Science, University of Toronto, 1993. D.J. Nott and P.J. Green. Bayesian veriable selection and the Swendsen-Wang algorithm. Journal of Computational and Graphical Statistics, 13:141–157, 2004. E. Nummelin. General Irreducible Markov Chains on Non-Negative Operators. Cambridge University Press, 1984. L.M. Pasetto, E. Rossi, and S. Monfardini. Liver metastases of colorectal cancer: medical treatment. Anticancer, 23:4245–56, 2003. P.H. Peskun. Optimum Monte Carlo sampling using Markov chain. Biometrika, 60:607–612, 1973. G. Petris and L. Tardella. A geometric approach to transdimensional Markov chain Monte Carlo. The Canadian Journal of Statistics, 31:469–482, 2003. J. Pittman, E. Huang, H. Dressman, C.F. Horng, S.H. Cheng, M.H. Tsou, C.M. Chen, A. Bild, E.S. Iversen, A.T. Huang, J.R. Nevins, and M. West. Integrated modeling of clinical and gene expression information for personalized prediction of disease outcomes. Proceedings of the National Academy of Sciences, 101:8431– 8436, 2004. A. E. Raftery, D. Madigan, and J. A. Hoeting. Bayesian model averaging for linear regression models. Journal of the American Statistical Association, 92:179–191, 1997. R. Ren and G. Orkoulas. Parallel Markov chain Monte Carlo simulations. Journal of Chemical Physics, doi:10.1063/1.2743003, 2007. C.P. Robert. Convergence control methods for Markov chain Monte Carlo algorithms. Statistical Science, 10:231–253, 1995. C.P. Robert and G. Casella. Monte Carlo Statistical Methods. Springer, 1999. G.O. Roberts and J.S. Rosenthal. Optimal scaling for various Metropolis Hastings algorithms. Statistical Science, 16:351–367, 2001. G.O. Roberts and J.S. Rosenthal. Coupling
URI:	http://wrap.warwick.ac.uk/id/eprint/35224

Request changes to a record

Actions (login required)

View Item