Bayesian analysis of massive datasets via particle filters

ABSTRACT

Markov Chain Monte Carlo (MCMC) techniques revolutionized statistical practice in the 1990s by providing an essential toolkit for making the rigor and flexibility of Bayesian analysis computationally practical. At the same time the increasing prevalence of massive datasets and the expansion of the field of data mining has created the need to produce statistically sound methods that scale to these large problems. Except for the most trivial examples, current MCMC methods require a complete scan of the dataset for each iteration eliminating their candidacy as feasible data mining techniques.In this article we present a method for making Bayesian analysis of massive datasets computationally feasible. The algorithm simulates from a posterior distribution that conditions on a smaller, more manageable portion of the dataset. The remainder of the dataset may be incorporated by reweighting the initial draws using importance sampling. Computation of the importance weights requires a single scan of the remaining observations. While importance sampling increases efficiency in data access, it comes at the expense of estimation efficiency. A simple modification, based on the "rejuvenation" step used in particle filters for dynamic systems models, sidesteps the loss of efficiency with only a slight increase in the number of data accesses.To show proof-of-concept, we demonstrate the method on a mixture of transition models that has been used to model web traffic and robotics. For this example we show that estimation efficiency is not affected while offering a 95% reduction in data accesses.

REFERENCES

• 1: J. Besag, P. Green, D. Higdon, and K. Mengersen. Bayesian computation and stochastic systems (with discussion). Statistical Science, 10:3--41, 1995.
• 2: I. Cadez, D. Heckerman, C. Meek, P. Smyth, and S. White. Visualization of navigation patterns on a web site using model-based clustering. Technical Report MSR-TR-00-18, Microsoft Research, March.
• 3: B. Carlin and T. Louis. Bayes and Empirical Bayes Methods for Data Analysis. Chapman and Hall, Boca Raton, FL, 2nd edition, 2000.
• 4: M. DeGroot. Optimal Statistical Decisions. McGraw-Hill, New York, 1970.
• 5: A. Doucet, N. de Freitas, and N. Gordon. Sequential Monte Carlo Methods in Practice. Springer-Verlag, 2001.
• 6: John F. Elder, IV , Dary Pregibon, A statistical perspective on knowledge discovery in databases, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 7: M. Figueiredo. Adaptive sparseness using Jeffreys prior. In Neural Information Processing Systems - NIPS 2001, 2001.
• 8: A. Gelman, J. Carlin, H. Stern, and D. Rubin. Bayesian Data Analysis. Chapman Hall, New York, 1995.
• 9: S. Geman and D. Geman. Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:721--741, 1984.
• 10: W. Gilks and C. Berzuini. Following a moving target - Monte Carlo inference for dynamic Bayesian models. Journal of the Royal Statistical Society B, 63(1):127--146, 2001.
• 11: W. Gilks, S. Richardson, and D. J. Spiegelhalter, editors. Markov Chain Monte Carlo in Practice. Chapman and Hall, 1996.
• 12: Clark Glymour , David Madigan , Daryl Pregibon , Padhraic Smyth, Statistical Themes and Lessons for Data Mining, Data Mining and Knowledge Discovery, v.1 n.1, p.11-28, 1997 [doi>10.1023/A:1009773905005]
• 13: W. K. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57:97--109, 1970.
• 14: A. Kong, J. Liu, and W. Wong. Sequential imputation and Bayesian missing data problems. Journal of the American Statistical Association, 89:278--288, 1994.
• 15: Lucien M Le Cam, Asymptotic methods in statistical theory, Springer-Verlag New York, Inc., New York, NY, 1986
• 16: Huan Liu , Hiroshi Motoda, Instance Selection and Construction for Data Mining, Kluwer Academic Publishers, Norwell, MA, 2001
• 17: N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller. Equations of state calculations by fast computing machine. Journal of Chemical Physics, 21:1087--1091, 1953.
• 18: Marco Ramoni , Paola Sebastiani , Paul Cohen, Bayesian Clustering by Dynamics, Machine Learning, v.47 n.1, p.91-121, April 2002 [doi>10.1023/A:1013635829250]
• 19: G. Ridgeway. Finite discrete Markov process clustering. Technical Report MSR-TR-97-24, Microsoft Research, September.
• 20: G. Ridgeway and S. Altschuler. Clustering finite discrete Markov chains. In Proceedings of the Section on Physical and Engineering Sciences, pages 228--229, 1998.
• 21: S. M. Ross. Probability Models. Academic Press, 5th edition, 1993.
• 22: D. Spiegelhalter and R. Cowell. Learning in probabilistic expert systems. In J. Bernardo, J. Berger, A. Dawid, and A. Smith, editors, Bayesian Statistics, volume 4, pages 447--466. Clarendon Press, Oxford, 1992.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

General Terms:
Algorithms, Experimentation, Measurement, Performance