The Library
Parallel hierarchical sampling : a generalpurpose class of multiplechains MCMC algorithms
Tools
Rigat, Fabio, 1975 and Mira, Antonietta (2009) Parallel hierarchical sampling : a generalpurpose class of multiplechains MCMC algorithms. Working Paper. Coventry: University of Warwick. Centre for Research in Statistical Methodology. (Working papers).

PDF
WRAP_Rigat_0937v2w.pdf  Published Version  Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (2867Kb) 
Official URL: http://www2.warwick.ac.uk/fac/sci/statistics/crism...
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 singlechain 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 singlechain MCMC algorithms. Convergence of the PHS joint transition kernel is proved and its relationships with singlechain 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 MetropolisHastings and PT for sampling multimodal mixtures of multivariate Gaussian densities and for 'bananashaped' 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 rightcensored 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 logconcave 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, birthanddeath 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. Multiprocess 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: Parallelchain 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 MetropolisHastings 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. Samplingbased 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 samplingbased 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. Treestructured 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. Componentwise 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 KW. 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 4taxa 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. Populationbased 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. Realparameter 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 multipletry 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. Statedependent 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 SwendsenWang algorithm. Journal of Computational and Graphical Statistics, 13:141–157, 2004. E. Nummelin. General Irreducible Markov Chains on NonNegative 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 
Actions (login required)
View Item 