×

Parallel multivariate slice sampling. (English) Zbl 1253.60082

Summary: Slice sampling provides an easily implemented method for constructing a Markov chain Monte Carlo (MCMC) algorithm. However, slice sampling has two major drawbacks: (i) it requires repeated evaluation of likelihoods for each update, which can make it impractical when evaluations are expensive or as the number of evaluations grows (geometrically) with the dimension of the slice sampler, and (ii) since it can be challenging to construct multivariate updates, the updates are typically univariate, which often results in slow mixing samplers. We propose an approach to multivariate slice sampling that naturally lends itself to a parallel implementation. Our approach takes advantage of recent advances in computer architectures, for instance, the newest generation of graphics cards can execute roughly 30,000 threads simultaneously. We demonstrate that it is possible to construct a multivariate slice sampler that has good mixing properties and is efficient in terms of computing time. The contributions of this article are therefore twofold. We study approaches for constructing a multivariate slice sampler, and we show how parallel computing can be useful for making MCMC algorithms computationally efficient. We study various implementations of our algorithm in the context of real and simulated data.

MSC:

60J22 Computational methods in Markov chains
62J05 Linear regression; mixed models
62M05 Markov processes: estimation; hidden Markov models
68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, D.K., Gelfand, A.E.: Slice sampling for simulation based fitting of spatial data models. Stat. Comput. 15(1), 61–69 (2005) · doi:10.1007/s11222-005-4790-z
[2] Alpatov, P., Baker, G., Edwards, C., Gunnels, J., Morrow, G., Overfelt, J., Jye, J., Wu, Y.: PLAPACK: Parallel linear algebra package (1997)
[3] Andrieu, C., de Freitas, N., Doucet, A., Jordan, M.I.: An introduction to MCMC for machine learning. Mach. Learn. 50(1), 5–43 (2003) · Zbl 1033.68081 · doi:10.1023/A:1020281327116
[4] Banerjee, S., Carlin, B., Gelfand, A.: Hierarchical Modeling and Analysis for Spatial Data. Chapman & Hall, London (2004) · Zbl 1053.62105
[5] Blackford, L.S., Choi, J., Cleary, A., Petitet, A., Whaley, R.C., Demmel, J., Dhillon, I., Stanley, K., Dongarra, J., Hammarling, S., Henry, G., Walker, D.: ScaLAPACK: A portable linear algebra library for distributed memory computers–design issues and performance. In: Supercomputing ’96: Proceedings of the 1996 ACM/IEEE Conference on Supercomputing (CDROM), p. 5. IEEE Computer Society, Washington (1996) · Zbl 0926.65148
[6] Chandra, R., Dagum, L., Kohr, D., Maydan, D., McDonald, J., Menon, R.: Parallel Programming in OpenMP. Morgan Kaufmann, San Francisco (2001)
[7] Chib, S., Carlin, B.P.: On MCMC sampling in hierarchical longitudinal models. Stat. Comput. 9(1), 17–26 (1999) · doi:10.1023/A:1008853808677
[8] Cressie, N.A.C.: Statistics for Spatial Data, 2nd edn. Wiley Series in Probability and Statistics. Wiley-Interscience, New York (1993) · Zbl 0825.62477
[9] CUDA: NVIDIA Compute Unified Device Architecture, Programming Guide Ver.2.2.1. NVIDIA Corporation, http://developer.download.nvidia.com/compute/cuda/2_21/toolkit/docs/NVIDIA_CUDA_Programming_Guide_2.2.1.pdf (2009)
[10] Damien, P., Wakefield, J., Walker, S.: Gibbs sampling for Bayesian non-conjugate and hierarchical models by using auxiliary variables. J. R. Stat. Soc. Ser. B (Stat. Method.) 61(2), 331–344 (1999) · Zbl 0913.62028 · doi:10.1111/1467-9868.00179
[11] Garland, M., Le Grand, S., Nickolls, J., Anderson, J., Hardwick, J., Morton, S., Phillips, E., Zhang, Y., Volkov, V.: Parallel computing experiences with CUDA. Micro IEEE 28(4), 13–27 (2008) · doi:10.1109/MM.2008.57
[12] Geyer, C.J.: Practical Markov chain Monte Carlo. Stat. Sci. 7(4), 473–483 (1992) · Zbl 0085.18501 · doi:10.1214/ss/1177011137
[13] Gilks, W.R., Roberts, G.: Strategies for improving MCMC. In: Gilks, W.R., Richardson, S., Spiegelhalter, D.J. (eds.) Markov Chain Monte Carlo in Practice, pp. 89–114. Chapman & Hall/CRC, London (1996) · Zbl 0844.62100
[14] Golub, G.H., Van Loan, C.F.: Matrix Computations. Johns Hopkins Studies in Mathematical Sciences. The Johns Hopkins University Press, Baltimore (1996)
[15] Jiang, R., Zeng, F., Zhang, W., Wu, X., Yu, Z.: Accelerating genome-wide association studies using CUDA compatible graphics processing units. In: Bioinformatics, Systems Biology and Intelligent Computing, 2009. IJCBS ’09. International Joint Conference on, pp. 70–76 (2009)
[16] Kass, R.E., Carlin, B.P., Gelman, A., Neal, R.M.: Markov chain Monte Carlo in practice: A roundtable discussion. Am. Stat 52(2), 93–100 (1998)
[17] Kinney, S.K., Dunson, D.B.: Fixed and random effects selection in linear and logistic models. Biometrics 63(9), 690–698 (2007) · Zbl 1147.62022 · doi:10.1111/j.1541-0420.2007.00771.x
[18] Kovac, K.: Machine learning for Bayesian neural networks. Master of Science, University of Toronto (2005)
[19] Lee, A., Yau, C., Giles, M.B., Doucet, A., Holmes, C.C.: (2009). On the utility of graphics cards to perform massively parallel simulation of advanced Monte Carlo methods. Stat. Comput. Submitted for Publication July 2009
[20] Lewis, P.O., Holder, M.T., Holsinger, K.E.: Polytomies and Bayesian phylogenetic inference. Syst. Biol. 54(2), 241–253 (2005) · doi:10.1080/10635150590924208
[21] Liu, J.S., Wong, W.H., Kong, A.: Covariance structure of the Gibbs sampler with applications to the comparisons of estimators and augmentation schemes. Biometrika 81(1), 27–40 (1994) · Zbl 0811.62080 · doi:10.1093/biomet/81.1.27
[22] Mackay, D.J.C.: Information Theory, Inference & Learning Algorithms. Cambridge University Press, Cambridge (2002)
[23] Manavski, S., Valle, G.: CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment. BMC Bioinformatics 9(Suppl. 2), S10 (2008) · doi:10.1186/1471-2105-9-S2-S10
[24] Mira, A., Roberts, G.O.: [Slice sampling]: Discussion. Ann. Stat. 31(3), 748–753 (2003)
[25] Mira, A., Tierney, L.: Efficiency and convergence properties of slice samplers. Scand. J. Statist. 29, 1–12 (2002) (12) · Zbl 1018.91030 · doi:10.1111/1467-9469.00267
[26] MPI Forum: Message Passing Interface (MPI) Standard. http://www.mpi-forum.org/docs/mpi21-report.pdf . Version 2.1 (2008)
[27] Neal, R.M.: Markov chain Monte Carlo methods based on ’slicing’ the density function. Technical Report, Department of Statistics, University of Toronto (1997)
[28] Neal, R.M.: Slice sampling. Ann. Stat. 31(3), 705–741 (2003a) · Zbl 1051.65007 · doi:10.1214/aos/1056562461
[29] Neal, R.M.: [Slice sampling]: Rejoinder. Ann. Stat. 31(3), 758–767 (2003b) · Zbl 1051.65007
[30] Nott, D.J., Leonte, D.: Sampling schemes for Bayesian variable selection in generalized linear models. J. Comput. Graph. Stat. 13(2), 362–382 (2004) · doi:10.1198/1061860043425
[31] Roberts, G.O., Rosenthal, J.S.: Convergence of slice sampler Markov chains. J. R. Stat. Soc. Ser. B (Stat. Method.) 61(18), 643–660 (1999) · Zbl 0929.62098 · doi:10.1111/1467-9868.00198
[32] Roberts, G.O., Rosenthal, J.S.: The polar slice sampler. Stoch. Models 18(2), 257–280 (2002) · Zbl 1006.65004 · doi:10.1081/STM-120004467
[33] Roberts, G.O., Sahu, S.K.: Updating schemes, correlation structure, blocking and parameterization for the Gibbs sampler. J. R. Stat. Soc. Ser. B (Method.) 59(2), 291–317 (1997) · Zbl 0886.62083 · doi:10.1111/1467-9868.00070
[34] Rosenthal, J.S.: Parallel computing and Monte Carlo algorithms. Far East J. Theoret. Stat. 4, 207–236 (2000) · Zbl 1008.68160
[35] Shahbaba, B., Neal, R.: Gene function classification using Bayesian models with hierarchy-based priors. BMC Bioinformatics 7(1), 448 (2006) · doi:10.1186/1471-2105-7-448
[36] Sinnott-Armstrong, N., Greene, C., Cancare, F., Moore, J.: Accelerating epistasis analysis in human genetics with consumer graphics hardware. BMC Res. Notes 2(1), 149 (2009) · doi:10.1186/1756-0500-2-149
[37] Suchard, M.A., Rambaut, A.: Many-core algorithms for statistical phylogenetics. Bioinformatics 25(11), 1370–1376 (2009) · Zbl 05743953 · doi:10.1093/bioinformatics/btp244
[38] Sun, S., Greenwood, C.M., Neal, R.M.: Haplotype inference using a Bayesian Hidden Markov model. Genet. Epidemiol. 31(8), 937–948 (2007) · doi:10.1002/gepi.20253
[39] Whiley, M., Wilson, S.P.: Parallel algorithms for Markov chain Monte Carlo methods in latent spatial Gaussian models. Stat. Comput. 14(3), 171–179 (2004) · doi:10.1023/B:STCO.0000035299.51541.5e
[40] Wilkinson, D.J.: Parallel Bayesian computation. In: Kontoghiorghes, J.E. (ed.) Handbook of Parallel Computing and Statistics, pp. 481–512. Marcel Dekker/CRC Press, New York (2005)
[41] Yan, J., Cowles, M.K., Wang, S., Armstrong, M.P.: Parallelizing MCMC for Bayesian spatiotemporal geostatistical models. Stat. Comput. 17(4), 323–335 (2007) · doi:10.1007/s11222-007-9022-2
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.