Mining complex models from arbitrarily large databases in constant time

ABSTRACT

In this paper we propose a scaling-up method that is applicable to essentially any induction algorithm based on discrete search. The result of applying the method to an algorithm is that its running time becomes independent of the size of the database, while the decisions made are essentially identical to those that would be made given infinite data. The method works within pre-specified memory limits and, as long as the data is iid, only requires accessing it sequentially. It gives anytime results, and can be used to produce batch, stream, time-changing and active-learning versions of an algorithm. We apply the method to learning Bayesian networks, developing an algorithm that is faster than previous ones by orders of magnitude, while achieving essentially the same predictive performance. We observe these gains on a series of large databases "generated from benchmark networks, on the KDD Cup 2000 e-commerce data, and on a Web log containing 100 million requests.

REFERENCES

• 1: David Cohn , Les Atlas , Richard Ladner, Improving Generalization with Active Learning, Machine Learning, v.15 n.2, p.201-221, May 1994 [doi>10.1023/A:1022673506211]
• 2: Carlos Domingo , Ricard Gavaldà , Osamu Watanabe, Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms, Data Mining and Knowledge Discovery, v.6 n.2, p.131-152, April 2002 [doi>10.1023/A:1014091514039]
• 3: Pedro Domingos , Geoff Hulten, Mining high-speed data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.71-80, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347107]
• 4: P. Domingos and G. Hulten. Learning from infinite data in finite time. In Advances in Neural Information Processing Systems 14. MIT Press, Cambridge, MA, 2002.
• 5: N. Friedman, I. Nachman, and D. Peér. Learning Bayesian network structure from massive datasets: The "sparse candidate" algorithm. In Proc. 15th Conf. on Uncertainty in Artificial Intelligence, pp. 206--215, Stockholm, Sweden, 1999.
• 6: N. Friedman and Z. Yakhini. On the sample complexity of learning Bayesian networks. In Proc. 12th Conf. on Uncertainty in Artificial Intelligence, pp. 274--282, Portland, OR, 1996.
• 7: Russell Greiner, PALO: a probabilistic hill-climbing algorithm, Artificial Intelligence, v.84 n.1-2, p.177-208, July 1996 [doi>10.1016/0004-3702(95)00040-2]
• 8: David Heckerman , Dan Geiger , David M. Chickering, Learning Bayesian Networks: The Combination of Knowledge and Statistical Data, Machine Learning, v.20 n.3, p.197-243, Sept. 1995 [doi>10.1023/A:1022623210503]
• 9: W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13--30, 1963.
• 10: G. Hulten and P. Domingos. A general method for scaling up learning algorithms and its application to Bayesian networks. Technical report, Department of Computer Science and Engineering, University of Washington, Seattle, WA, 2002.
• 11: Geoff Hulten , Laurie Spencer , Pedro Domingos, Mining time-changing data streams, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.97-106, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502529]
• 12: Ron Kohavi , Carla E. Brodley , Brian Frasca , Llew Mason , Zijian Zheng, KDD-Cup 2000 organizers' report: peeling the onion, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.86-93, Dec. 2000 [doi>10.1145/380995.381033]
• 13: O. Maron and A. Moore. Hoeffding races: Accelerating model selection search for classification and function approximation. In Advances in Neural Information Processing Systems 6. Morgan Kaufmann, San Mateo, CA, 1994.
• 14: Christopher Meek , Bo Thiesson , David Heckerman, The learning-curve sampling method applied to model-based clustering, The Journal of Machine Learning Research, 2, p.397-418, 3/1/2002 [doi>10.1162/153244302760200678]
• 15: Foster Provost , David Jensen , Tim Oates, Efficient progressive sampling, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.23-32, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312188]
• 16: Tobias Scheffer , Stefan Wrobel, Incremental Maximization of Non-Instance-Averaging Utility Functions with Applications to Knowledge Discovery Problems, Proceedings of the Eighteenth International Conference on Machine Learning, p.481-488, June 28-July 01, 2001
• 17: A. Wald. Sequential analysis. Wiley, New York, 1947.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Keywords:
Bayesian networks, Hoeffding bounds, discrete search, scalable learning algorithms, subsampling