Cached Sufficient Statistics for Efficient Machine Learning with Large Databases

Andrew Moore and Mary Soon Lee
tech. report CMU-RI-TR-97-27, Robotics Institute, Carnegie Mellon University, July, 1997


Download
  • Adobe portable document format (pdf) (899KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
This paper introduces new algorithms and data structures for quick counting for machine learning datasets. We focus on the counting task of constructing contingency tables, but our approach is also applicable to counting the number of records in a dataset that match conjunctive queries. Subject to certain assumptions, the costs of these operations can be shown to be independent of the number of records in the dataset and loglinear in the number of non-zero entries in the contingency table.

We provide a very sparse data structure, the ADtree, to minimize memory use. We provide analytical worst-case bounds for this structure for several models of data distribution. We empirically demonstrate that tractably-sized data structures can be produced for large real-world datasets by (a) using a sparse tree structure that never allocates memory for counts of zero, (b) never allocating memory for counts that can be deduced from other counts, and (c) not bothering to expand the tree fully near its leaves.

We show how the ADtree can be used to accelerate Bayes net structure finding algorithms, rule learning algorithms, and feature selection algorithms, and we provide a number of empirical results comparing ADtree methods against traditional direct counting approaches. We also discuss the possible used of ADtrees in other machine learning methods, and discuss the merits of ADtrees in comparison with alternative representations such as kd-trees, R-trees and frequent sets.


Notes
Grant ID: NAGW-1175
Number of pages: 23

Text Reference
Andrew Moore and Mary Soon Lee, "Cached Sufficient Statistics for Efficient Machine Learning with Large Databases," tech. report CMU-RI-TR-97-27, Robotics Institute, Carnegie Mellon University, July, 1997

BibTeX Reference
@techreport{Moore_1997_451,
   author = "Andrew Moore and Mary Soon Lee",
   title = "Cached Sufficient Statistics for Efficient Machine Learning with Large Databases",
   booktitle = "",
   institution = "Robotics Institute",
   month = "July",
   year = "1997",
   number= "CMU-RI-TR-97-27",
   address= "Pittsburgh, PA",
}