×

zbMATH — the first resource for mathematics

Accelerating MCMC via Kriging-based adaptive independent proposals and delayed rejection. (English) Zbl 1441.65002
Summary: Markov Chain Monte Carlo (MCMC) simulation has a considerable computational burden when the target probability density function (PDF) evaluation involves a black-box, potentially computationally-expensive, numerical model. A novel framework to accelerate MCMC is developed here for such applications. It leverages a Kriging surrogate model approximation to the target PDF to improve computational efficiency, while preserves convergence properties to the exact target PDF, avoiding potential accuracy problems introduced through the surrogate model error. The approach relies on the delayed-rejection (DR) scheme and combines the rapid exploration characteristics of global (independent) proposals with the local search robustness of random walk proposals under the MCMC setting. The global proposal is chosen as the Kriging-based target PDF approximation. This proposal may resemble, depending on the surrogate model error, the actual target PDF very well, and therefore can provide significant computational benefits, including fast convergence of the Markov chain to its stationary distribution and, more importantly, low correlation between samples. At each MCMC step a candidate sample is generated from the independent proposal. If rejected, DR allows an extra random walk around the current sample. The DR step guarantees convergence to the actual target PDF, circumventing robustness problems that may arise when the Kriging-based independent proposal offers a poor approximation to (i.e., underestimates) the actual target PDF. The overall computational efficiency is further improved through an adaptive updating of the Kriging surrogate model during the MCMC sampling phase by extracting information from candidate samples whose inclusion in the training database can substantially enhance Kriging’s accuracy. The computational efficiency and robustness of the established algorithm, termed Adaptive Kriging Delayed Rejection Adaptive Metropolis algorithm (AK-DRAM), are demonstrated in two analytical benchmark problems and two engineering problems focusing on conditional failure sample simulation and Bayesian inference.
MSC:
65C05 Monte Carlo methods
60J22 Computational methods in Markov chains
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beck, J. L.; Zuev, K. M., Asymptotically independent Markov sampling: a new Markov chain Monte Carlo scheme for Bayesian inference, Int. J. Uncertain. Quantif., 3, 445-474 (2013)
[2] Wang, J.; Zabaras, N., A Bayesian inference approach to the inverse heat conduction problem, Int. J. Heat Mass Transfer, 47, 3927-3941 (2004) · Zbl 1070.80002
[3] Ching, J.; Chen, Y.-C., Transitional Markov chain Monte Carlo method for Bayesian model updating, model class selection, and model averaging, J. Eng. Mech., 133, 816-832 (2007)
[4] Au, S. K.; Beck, J. L., Estimation of small failure probabilities in high dimensions by subset simulation, Probab. Eng. Mech., 16, 263-277 (2001)
[5] Green, D. K., Efficient Markov Chain Monte Carlo for combined Subset Simulation and nonlinear finite element analysis, Comput. Methods Appl. Mech. Engrg., 313, 337-361 (2017)
[6] Papaioannou, I.; Betz, W.; Zwirglmaier, K.; Straub, D., MCMC algorithms for subset simulation, Probab. Eng. Mech., 41, 89-103 (2015)
[7] Roberts, G. O.; Gelman, A.; Gilks, W. R., Weak convergence and optimal scaling of random walk metropolis algorithms, Ann. Appl. Probab., 7, 110-120 (1997) · Zbl 0876.60015
[8] Brooks, S.; Gelman, A.; Jones, G.; Meng, X.-L., Handbook of Markov Chain Monte Carlo (2011), CRC press · Zbl 1218.65001
[9] Robert, C. P.; Elvira, V.; Tawn, N.; Wu, C., Accelerating MCMC algorithms, Wiley Interdiscip. Rev. Comput. Stat., Article e1435 pp. (2018)
[10] Angelikopoulos, P.; Papadimitriou, C.; Koumoutsakos, P., X-TMCMC: Adaptive kriging for Bayesian inverse modeling, Comput. Methods Appl. Mech. Engrg., 289, 409-428 (2015) · Zbl 1426.62089
[11] Bliznyuk, N.; Ruppert, D.; Shoemaker, C.; Regis, R.; Wild, S.; Mugunthan, P., Bayesian calibration and uncertainty analysis for computationally expensive models using optimization and radial basis function approximation, J. Comput. Graph. Statist., 17, 270-294 (2008)
[12] Bourinet, J.-M.; Deheeger, F.; Lemaire, M., Assessing small failure probabilities by combined subset simulation and support vector machines, Struct. Saf., 33, 343-353 (2011)
[13] Marzouk, Y. M.; Najm, H. N.; Rahn, L. A., Stochastic spectral methods for efficient Bayesian solution of inverse problems, J. Comput. Phys., 224, 560-586 (2007) · Zbl 1120.65306
[14] Elsheikh, A. H.; Hoteit, I.; Wheeler, M. F., Efficient Bayesian inference of subsurface flow models using nested sampling and sparse polynomial chaos surrogates, Comput. Methods Appl. Mech. Engrg., 269, 515-537 (2014)
[15] Zhang, J.; Taflanidis, A. A., Adaptive Kriging stochastic sampling and density approximation and its implementation to rare-event estimation, ASCE-ASME J. Risk Uncertain. Eng. Syst. A, 4, Article 04018021 pp. (2018)
[16] Bichon, B. J.; Eldred, M. S.; Swiler, L. P.; Mahadevan, S.; McFarland, J. M., Efficient global reliability analysis for nonlinear implicit performance functions, AIAA J., 46, 2459-2468 (2008)
[17] Martin, J. D.; Simpson, T. W., Use of kriging models to approximate deterministic computer models, AIAA J., 43, 853-863 (2005)
[21] Robert, C.; Casella, G., Monte Carlo Statistical Methods (2013), Springer Science & Business Media
[22] Christen, J. A.; Fox, C., Markov chain Monte Carlo using an approximation, J. Comput. Graph. Statist., 14, 795-810 (2005)
[23] Sherlock, C.; Golightly, A.; Henderson, D. A., Adaptive, delayed-acceptance MCMC for targets with expensive likelihoods, J. Comput. Graph. Statist., 26, 434-444 (2017)
[24] Drovandi, C. C.; Moores, M. T.; Boys, R. J., Accelerating pseudo-marginal MCMC using Gaussian processes, Comput. Statist. Data Anal., 118, 1-17 (2018) · Zbl 06920161
[25] Cui, T.; Marzouk, Y. M.; Willcox, K. E., Data-driven model reduction for the Bayesian solution of inverse problems, Internat. J. Numer. Methods Engrg., 102, 966-990 (2015) · Zbl 1352.65445
[26] Zhang, C.; Shahbaba, B.; Zhao, H., Hamiltonian Monte Carlo acceleration using surrogate functions with random bases, Stat. Comput., 27, 1473-1490 (2017) · Zbl 1384.65008
[27] Rasmussen, C., Gaussian processes to speed up hybrid Monte Carlo for expensive Bayesian integrals, (Bayesian Statistics 7: Proceedings of the 7th Valencia International Meeting (2003), Oxford University Press), 651-659
[28] Strathmann, H.; Sejdinovic, D.; Livingstone, S.; Szabo, Z.; Gretton, A., Gradient-free hamiltonian Monte Carlo with efficient kernel exponential families, (Advances in Neural Information Processing Systems (2015)), 955-963
[29] Fielding, M.; Nott, D. J.; Liong, S.-Y., Efficient MCMC schemes for computationally expensive posterior distributions, Technometrics, 53, 16-28 (2011)
[30] Overstall, A. M.; Woods, D. C., A strategy for Bayesian inference for computationally expensive models with application to the estimation of stem cell properties, Biometrics, 69, 458-468 (2013) · Zbl 1274.62851
[31] Sejdinovic, D.; Strathmann, H.; Garcia, M. L.; Andrieu, C.; Gretton, A., Kernel adaptive metropolis-hastings, (International Conference on Machine Learning (2014)), 1665-1673
[32] Conrad, P. R.; Davis, A. D.; Marzouk, Y. M.; Pillai, N. S.; Smith, A., Parallel local approximation MCMC for expensive models, SIAM/ASA J. Uncertain. Quantif., 6, 339-373 (2018) · Zbl 1398.65017
[33] Metropolis, N.; Rosenbluth, A. W.; Rosenbluth, M. N.; Teller, A. H.; Teller, E., Equation of state calculations by fast computing machines, J. Chem. Phys., 21, 1087-1092 (1953)
[34] Hastings, W., Monte Carlo sampling methods using Markov chains and their applications, Biometrika, 57, 97-109 (1970) · Zbl 0219.65008
[35] Gåsemyr, J., On an adaptive version of the Metropolis-Hastings algorithm with independent proposal distribution, Scand. J. Stat., 30, 159-173 (2003) · Zbl 1038.65005
[36] Giordani, P.; Kohn, R., Adaptive independent Metropolis-Hastings by fast estimation of mixtures of normals, J. Comput. Graph. Statist., 19, 243-259 (2010)
[37] Parno, M. D.; Marzouk, Y. M., Transport map accelerated Markov Chain Monte Carlo, SIAM/ASA J. Uncertain. Quantif., 6, 645-682 (2018) · Zbl 1394.65004
[38] Andrieu, C.; Thoms, J., A tutorial on adaptive MCMC, Stat. Comput., 18, 343-373 (2008)
[39] Mira, A., On Metropolis-Hastings algorithms with delayed rejection, Metron-Int. J. Stat., 59, 231-241 (2001) · Zbl 0998.65502
[40] Tierney, L.; Mira, A., Some adaptive Monte Carlo methods for Bayesian inference, Stat. Med., 18, 2507-2515 (1999)
[41] Haario, H.; Laine, M.; Mira, A.; Saksman, E., DRAM: efficient adaptive MCMC, Stat. Comput., 16, 339-354 (2006)
[42] Dubourg, V.; Sudret, B.; Deheeger, F., Metamodel-based importance sampling for structural reliability analysis, Probab. Eng. Mech., 33, 47-57 (2013)
[43] Pedroni, N.; Zio, E., An Adaptive Metamodel-Based Subset Importance Sampling approach for the assessment of the functional failure probability of a thermal-hydraulic passive system, Appl. Math. Model., 48, 269-288 (2017)
[44] Bect, J.; Li, L.; Vazquez, E., Bayesian subset simulation, SIAM/ASA J. Uncertain. Quantif., 5, 762-786 (2017) · Zbl 06861829
[45] Zhang, J.; Taflanidis, A. A.; Medina, J. C., Sequential approximate optimization for design under uncertainty problems utilizing Kriging metamodeling in augmented input space, Comput. Methods Appl. Mech. Engrg., 315, 369-395 (2017)
[46] Sacks, J.; Welch, W. J.; Mitchell, T. J.; Wynn, H. P., Design and analysis of computer experiments, Statist. Sci., 409-423 (1989) · Zbl 0955.62619
[47] Santner, T. J.; Williams, B. J.; Notz, W. I., The Design and Analysis of Computer Experiments (2013), Springer Science & Business Media
[48] Jia, G.; Taflanidis, A. A., Kriging metamodeling for approximation of high-dimensional wave and surge responses in real-time storm/hurricane risk assessment, Comput. Methods Appl. Mech. Engrg., 261, 24-38 (2013) · Zbl 1286.86018
[49] Liu, J. S., Metropolized independent sampling with comparisons to rejection sampling and importance sampling, Stat. Comput., 6, 113-119 (1996)
[50] Jia, G.; Taflanidis, A. A.; Beck, J. L., A new adaptive rejection sampling method using kernel density approximations and its application to subset simulation, ASCE-ASME J. Risk Uncertain. Eng. Syst. A, Article D4015001 pp. (2015)
[51] Duane, S.; Kennedy, A. D.; Pendleton, B. J.; Roweth, D., Hybrid monte carlo, Phys. Lett. B, 195, 216-222 (1987)
[52] Tierney, L., Markov chains for exploring posterior distributions, Ann. Statist., 1701-1728 (1994) · Zbl 0829.62080
[53] Haario, H.; Saksman, E.; Tamminen, J., An adaptive Metropolis algorithm, Bernoulli, 7, 223-242 (2001) · Zbl 0989.65004
[54] Rasmussen, C. E.; Williams, C. K.I., Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning) (2005), The MIT Press
[55] Dubrule, O., Cross validation of kriging in a unique neighborhood, J. Int. Assoc. Math. Geol., 15, 687-699 (1983)
[56] Roberts, G. O.; Rosenthal, J. S., Coupling and ergodicity of adaptive Markov chain Monte Carlo algorithms, J. Appl. Probab., 44, 458-475 (2007) · Zbl 1137.62015
[57] Sherlock, C.; Fearnhead, P.; Roberts, G. O., The random walk Metropolis: linking theory and practice through a case study, Statist. Sci., 25, 172-190 (2010) · Zbl 1328.60177
[58] Boone, E. L.; Merrick, J. R.; Krachey, M. J., A hellinger distance approach to MCMC diagnostics, J. Stat. Comput. Simul., 84, 833-849 (2014)
[60] Geyer, C. J., Practical Markov chain Monte Carlo, Statist. Sci., 7, 473-483 (1992)
[61] Schöbi, R.; Sudret, B.; Marelli, S., Rare event estimation using polynomial-chaos kriging, ASCE-ASME J. Risk Uncertain. Eng. Syst. A, 3, Article D4016002 pp. (2016)
[62] Beck, J. L.; Katafygiotis, L. S., Updating models and their uncertainties. I: Bayesian statistical framework, J. Eng. Mech., 124, 455-461 (1998)
[63] Papadimitriou, C.; Papadioti, D.-C., Component mode synthesis techniques for finite element model updating, Comput. Struct., 126, 15-28 (2013)
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.