Learning from Infinite Data in Finite Time
Authors: Pedro Domingos, Geoff Hulten
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We  propose  the  following  general  method  for  scaling  learning  algorithms  to  arbitrarily  large  data  sets.  Consider  the  model  Mii  learned  by  the  algorithm  using  ni  examples  in  step  i  (ii  =  (nl , ... ,nm)) , and the model  Moo  that would  be learned using in(cid:173) finite  examples.  Upper-bound  the loss  L(Mii' M oo ) between  them  as  a  function  of ii, and  then  minimize  the  algorithm's  time  com(cid:173) plexity f(ii) subject to the constraint  that L(Moo , Mii ) be at most  f  with  probability  at  most  8.  We  apply  this  method  to  the  EM  algorithm for  mixtures  of Gaussians.  Preliminary experiments on  a  series  of large data sets  provide evidence of the potential of this  approach. 
1  An  Approach to Large-Scale  Learning 
Large  data sets  make  it  possible  to  reliably  learn  complex  models.  On  the  other  hand,  they require large  computational  resources  to learn from.  While  in  the past  the factor limiting the quality of learnable models was typically the quantity of data  available,  in many domains today data is  super-abundant, and the bottleneck is t he  time  required  to  process  it.  Many  algorithms for  learning  on  large  data sets  have  been  proposed,  but  in  order  to  achieve  scalability  they  generally  compromise  the  quality of the results to an unspecified degree.  We  believe this  unsatisfactory state  of affairs  is  avoidable,  and  in  this  paper  we  propose  a  general  method  for  scaling  learning algorithms to arbitrarily large databases without compromising the quality  of the  results.  Our  method  makes  it  possible  to  learn  in  finite  time  a  model  that  is  essentially  indistinguishable from  the  one  that  would  be  obtained  using  infinite  data. 
Consider the simplest possible learning problem:  estimating the mean of a  random  variable  x.  If we  have a  very large number of samples,  most  of them  are  probably  superfluous.  If we are willing to accept an error of at most f with probability at most  8,  Hoeffding bounds  [4]  (for example)  tell  us that, irrespective of the distribution of  x,  only n  =  ~(R/f)2 1n (2/8) samples  are needed,  where R is  x's range.  We  propose  to  extend  this  type  of  reasoning  beyond  learning  single  parameters,  to  learning  complex models.  The approach we  propose consists of three steps: 

Derive  an  upper  bound  on  the  relative  loss  between  the  finite-data  and  infinite-data models,  as  a  function  of the  number of samples  used  in  each  step of the finite-data algorithm. 
Derive  an  upper bound  on  the  time  complexity of the learning algorithm, 

as  a function  of the number of samples used in  each  step. 

Minimize  the  time  bound  (via  the  number  of samples  used  in  each  step) 

subject to target limits on the loss. 
In  this  paper we  exemplify  this  approach  using  the  EM algorithm  for  mixtures  of  Gaussians.  In  earlier  papers  we  applied  it  (or  an  earlier  version  of it)  to  decision  tree  induction  [2J  and  k-means  clustering  [3J.  Despite  its  wide  use,  EM  has  long  been criticized for its inefficiency  (see discussion following Dempster et al.  [1]),  and  has been considered unsuitable for large data sets [8J.  Many approaches to speeding  it up have  been proposed  (see Thiesson et al.  [6J  for  a  survey) .  Our method can be  seen as  an extension of progressive  sampling approaches like Meek et al.  [5J:  rather  than  minimize  the total number of samples  needed  by  the algorithm, we  minimize  the  number  needed  by each step,  leading  to  potentially much  greater savings;  and  we  obtain guarantees that do not depend on unverifiable extrapolations of learning  curves. 
2  A  Loss  Bound for  EM 
In  a  mixture of Gaussians  model,  each  D-dimensional data point  Xj  is  assumed  to  have been independently generated by  the following  process:  1)  randomly choose a  mixture component k;  2)  randomly generate a point from it according to a Gaussian  distribution with mean f-Lk  and covariance matrix  ~k. In  this paper we  will  restrict  ourselves to the case where the number K  of mixture components and the probabil(cid:173) ity of selection P(f-Lk)  and covariance matrix for  each  component are known.  Given  a  training  set  S  =  {Xl, ... , X N },  the  learning  goal  is  then  to  find  the  maximum(cid:173) likelihood  estimates  of the  means  f-Lk.  The EM algorithm  [IJ  accomplishes  this  by,  starting from  some set  of initial means, alternating until convergence between esti(cid:173) mating the probability p(f-Lk IXj) that each point was generated by each Gaussian (the  Estep), and computing the ML estimates of the means ilk  =  2::;':1 WjkXj /  2::f=l Wjk  (the  M  step),  where  Wjk  =  p(f-Lklxj)  from  the  previous  E  step.  In  the  basic  EM  algorithm,  all  N  examples  in  the  training set  are  used  in  each  iteration.  The goal  in  this  paper  is  to  speed  up  EM  by  using  only  ni  < N  examples  in  the  ith  itera(cid:173) tion,  while  guaranteeing that  the  means  produced  by  the  algorithm  do  not  differ  significantly from  those that would  be obtained with arbitrarily large N. 
Let  Mii  =  (ill , . . . , ilK) be the vector of mean estimates obtained by the finite-data  EM algorithm (i.e.,  using ni examples in iteration i), and let Moo  =  (f-L1,  ... ,f-LK)  be  the vector obtained  using infinite  examples at each  iteration.  In  order to proceed,  we  need  to  quantify  the  difference  between  Mii  and  Moo .  A  natural  choice  is  the  sum  of the squared errors  between  corresponding  means,  which  is  proportional to  the negative log-likelihood of the finite-data means given  the infinite-data ones: 
L(Mii' Moo ) =  L Ililk  - f-Lkl12  =  L L lilkd  -