×

Quasi-Monte Carlo sampling to improve the efficiency of Monte Carlo EM. (English) Zbl 1429.62021

Summary: We investigate an efficient implementation of the Monte Carlo EM algorithm based on Quasi-Monte Carlo sampling. The Monte Carlo EM algorithm is a stochastic version of the deterministic EM (Expectation-Maximization) algorithm in which an intractable E-step is replaced by a Monte Carlo approximation. Quasi-Monte Carlo methods produce deterministic sequences of points that can significantly improve the accuracy of Monte Carlo approximations over purely random sampling. One drawback to deterministic quasi-Monte Carlo methods is that it is generally difficult to determine the magnitude of the approximation error. However, in order to implement the Monte Carlo EM algorithm in an automated way, the ability to measure this error is fundamental. Recent developments of randomized quasi-Monte Carlo methods can overcome this drawback. We investigate the implementation of an automated, data-driven Monte Carlo EM algorithm based on randomized quasi-Monte Carlo methods. We apply this algorithm to a geostatistical model of online purchases and find that it can significantly decrease the total simulation effort, thus showing great potential for improving upon the efficiency of the classical Monte Carlo EM algorithm.

MSC:

62-08 Computational methods for problems pertaining to statistics
62F10 Point estimation
65C05 Monte Carlo methods
86A32 Geostatistics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bhat, C., Quasi-random maximum simulated likelihood estimation for the mixed multinomial logit model, Transportation Res, 35, 677-693 (2001)
[2] Booth, J. G.; Hobert, J. P., Maximizing generalized linear mixed model likelihoods with an automated Monte Carlo EM algorithm, J. Roy. Statist. Soc. B, 61, 265-285 (1999) · Zbl 0917.62058
[3] Booth, J. G.; Hobert, J. P.; Jank, W., A survey of Monte Carlo algorithms for maximizing the likelihood of a two-stage hierarchical model, Statist. Model, 1, 333-349 (2001) · Zbl 1102.62019
[4] Bouleau, N.; Lépingle, D., Numerical Methods for Stochastic Processes (1994), Wiley: Wiley New York · Zbl 0822.60003
[5] Boyles, R. A., On the convergence of the EM algorithm, J. Roy. Statist. Soc. B, 45, 47-50 (1983) · Zbl 0508.62030
[6] Breslow, N. E.; Clayton, D. G., Approximate inference in generalized linear mixed models, J. Amer. Statist. Assoc, 88, 9-25 (1993) · Zbl 0775.62195
[7] Caffo, B.S., Jank, W.S., Jones, G.L., 2003. Ascent-Based Monte Carlo EM. Tech. rep., Department of Decision and Information Technologies, University of Maryland.; Caffo, B.S., Jank, W.S., Jones, G.L., 2003. Ascent-Based Monte Carlo EM. Tech. rep., Department of Decision and Information Technologies, University of Maryland.
[8] Caflisch, R.; Morokoff, W.; Owen, A., Valuation of mortgage-backed securities using Brownian bridges to reduce effective dimension, J. Comput. Finance, 1, 27-46 (1997)
[9] Chan, K. S.; Ledolter, J., Monte Carlo EM estimation for time series models involving counts, J. Amer. Statist. Assoc, 90, 242-252 (1995) · Zbl 0819.62069
[10] De Bruijn, N. G., Asymptotic Methods in Analysis (1958), North-Holland: North-Holland Amsterdam · Zbl 0082.04202
[11] Dempster, A. P.; Laird, N. M.; Rubin, D. B., Maximum likelihood from incomplete data via the EM algorithm, J. Roy. Statist. Soc. B, 39, 1-22 (1977) · Zbl 0364.62022
[12] Diggle, P. J.; Tawn, J. A.; Moyeed, R. A., Model-based geostatistics, J. Roy. Statist. Soc. A, 47, 299-350 (1998) · Zbl 0904.62119
[13] Doornik, J. A., Ox: Object Oriented Matrix Programming (2001), Timberlake: Timberlake London
[14] Evans, M.; Swartz, T., Methods for approximating integrals in statistics with special emphasis on Bayesian integration problems, Statist. Sci, 10, 254-272 (1995) · Zbl 0955.62553
[15] Evans, M., Swartz, T., 1996. Bayesian integration using multivariate student importance sampling. In: Meyer, M., Rosenberger, J. (Eds.), Computing Science and Statistics, Vol. 27. Interface Foundation of North America.; Evans, M., Swartz, T., 1996. Bayesian integration using multivariate student importance sampling. In: Meyer, M., Rosenberger, J. (Eds.), Computing Science and Statistics, Vol. 27. Interface Foundation of North America.
[16] Fang, K.-T.; Wang, Y., Number Theoretic Methods in Statistics (1994), Chapman & Hall: Chapman & Hall New York
[17] Faure, H., Discrépance de suites associées à un système de numération (en dimension s), Acta Arith, 41, 337-351 (1982) · Zbl 0442.10035
[18] Fort, G.; Moulines, E., Convergence of the Monte Carlo expectation maximization for curved exponential families, The Ann. Statist, 31, 1220-1259 (2003) · Zbl 1043.62015
[19] Halton, J. H., On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numer. Math, 2, 84-90 (1960) · Zbl 0090.34505
[20] Hobert, J. P., Hierarchical modelsa current computational perspective, J. Amer. Statist. Assoc, 95, 1312-1316 (2000) · Zbl 1072.62504
[21] Kuk, A. Y.C., Laplace importance sampling for generalized linear mixed models, J. Statist. Comput. Simulation, 63, 143-158 (1999) · Zbl 0956.62052
[22] Lange, K., A gradient algorithm locally equivalent to the EM algorithm, J. Roy. Statist. Soc. B, 57, 425-437 (1995) · Zbl 0813.62021
[23] L’Ecuyer, P., A unified view of the ipa, sf, and lr gradient estimation technique, Management Sci, 36, 1364-1383 (1990) · Zbl 0731.65130
[24] L’Ecuyer, P.; Lemieux, C., Recent advances in randomized Quasi-Monte Carlo Methods, (Dror, M.; L’Ecuyer, P.; Szidarovszki, F., Modeling Uncertainty: An Examination of Stochastic Theory, Methods, and Applications (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht)
[25] Lemieux, C., L’Ecuyer, P., 1998. Efficiency improvement by lattice rules for pricing Asian options. In: Proceedings of the 1998 Winter Simulation Conference, IEEE Press, New York.; Lemieux, C., L’Ecuyer, P., 1998. Efficiency improvement by lattice rules for pricing Asian options. In: Proceedings of the 1998 Winter Simulation Conference, IEEE Press, New York.
[26] Levine, R.; Casella, G., Implementations of the Monte Carlo EM algorithm, J. Comput. Graph. Statist, 10, 422-439 (2001)
[27] Levine, R., Fan, J., 2003. An automated (Markov Chain) Monte Carlo EM algorithm. J. Statist. Comput. Simulation, forthcoming.; Levine, R., Fan, J., 2003. An automated (Markov Chain) Monte Carlo EM algorithm. J. Statist. Comput. Simulation, forthcoming. · Zbl 1060.62026
[28] McCulloch, C. E., Maximum likelihood algorithms for generalized linear mixed models, J. Amer. Statist. Assoc, 92, 162-170 (1997) · Zbl 0889.62061
[29] Meng, X.-L.; Rubin, D. B., Maximum likelihood estimation via the ECM algorithma general framework, Biometrika, 80, 267-278 (1993) · Zbl 0778.62022
[30] Morokoff, W. J.; Caflisch, R. E., Quasi-Monte Carlo integration, J. Comput. Phys, 122, 218-230 (1995) · Zbl 0863.65005
[31] Niederreiter, H., Random Number Generation and Quasi-Monte Carlo Methods (1992), SIAM: SIAM Philadelphia · Zbl 0761.65002
[32] Owen, A., Scrambling Sobol’ and Niederreiter-Xing points, J. Complexity, 14, 466-489 (1998) · Zbl 0916.65017
[33] Owen, A.B., 1998b. Monte Carlo extension of Quasi-Monte Carlo. In: 1998 Winter Simulation Conference Proceedings. Springer, New York, pp. 571-577.; Owen, A.B., 1998b. Monte Carlo extension of Quasi-Monte Carlo. In: 1998 Winter Simulation Conference Proceedings. Springer, New York, pp. 571-577.
[34] Owen, A. B.; Zhou, Y., Safe and effective importance sampling, J. Amer. Statist. Assoc, 95, 135-143 (2000) · Zbl 0998.65003
[35] Pagès, G., Van der Corput sequences, Kakutani transforms and one-dimensional numerical integration, J. Comput. Appl. Math, 44, 21-39 (1992) · Zbl 0765.41033
[36] Robert, C. P.; Casella, G., Monte Carlo Statistical Methods (1999), Springer: Springer New York · Zbl 0935.62005
[37] Sherman, R. P.; Ho, Y.-Y. K.; Dalal, S. R., Conditions for convergence of Monte Carlo EM sequences with an application to product diffusion modeling, The Econometrics J, 2, 248-267 (1999) · Zbl 0955.91050
[38] Sobol, I. M., Distribution of points in a cube and approximate evaluation of integrals, U.S.S.R. Comput. Math. and Math. Phys, 7, 784-802 (1967)
[39] Wang, X.; Hickernell, F. J., Randomized Halton sequences, Math. and Comput. Model, 32, 887-899 (2000) · Zbl 0965.65005
[40] Wei, G. C.G.; Tanner, M. A., A Monte Carlo implementation of the EM algorithm and the poor man’s data augmentation algorithms, J. Amer. Statist. Assoc, 85, 699-704 (1990)
[41] Wu, C. F.J., On the convergence properties of the EM algorithm, The Ann. Statist, 11, 95-103 (1983) · Zbl 0517.62035
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.