Affordable Access

Publisher Website

Multiple pass streaming algorithms for learning mixtures of distributions in [formula omitted]

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
410
Issue
19
Identifiers
DOI: 10.1016/j.tcs.2009.01.043
Keywords
  • Streaming Algorithm
  • Machine Learning
  • Mixture Model
  • Computational Learning Theory
Disciplines
  • Computer Science

Abstract

Abstract We present a multiple pass streaming algorithm for learning the density function of a mixture of k uniform distributions over rectangles in R d , for any d > 0 . Our learning model is: samples drawn according to the mixture are placed in arbitrary order in a data stream that may only be accessed sequentially by an algorithm with a very limited random access memory space. Our algorithm makes 2 ℓ + 2 passes, for any ℓ > 0 , and requires memory at most O ̃ ( ϵ − 2 / ℓ k 2 d 4 + ( 4 k ) d ) , where ϵ is the tolerable error of the algorithm. This exhibits a strong memory-pass tradeoff in terms of ϵ : a few more passes significantly lower its memory requirements, thus trading one of the two most important resources in streaming computation for the other. Chang and Kannan first considered this problem for d = 1 , 2 . Our learning algorithm is especially appropriate for situations where massive data sets of samples are available, but computation with such large inputs requires very restricted models of computation.

There are no comments yet on this publication. Be the first to share your thoughts.