Memoized Online Variational Inference for Dirichlet Process Mixture Models
Variational inference algorithms provide the most effective framework for largescale training of Bayesian nonparametric models. Stochastic online approaches are promising, but are sensitive to the chosen learning rate and often converge to poor local optima. We present a new algorithm, memoized online variational inference, which scales to very large (yet finite) datasets while avoiding the complexities of stochastic gradient. Our algorithm maintains finite-dimensional sufficient statistics from batches of the full dataset, requiring some additional memory but still scaling to millions of examples. Exploiting nested families of variational bounds for infinite nonparametric models, we develop principled birth and merge moves allowing non-local optimization. Births adaptively add components to the model to escape local optima, while merges remove redundancy and improve speed. Using Dirichlet process mixture models for image clustering and denoising, we demonstrate major improvements in robustness and accuracy.
The authors propose a novel method for performing 
      memory efficient inference in Dirichlet Process (DP) models. There are two 
      key advances presented in this work: memoized online (MO) learning of the 
      model parameters using small subsets of data; an efficient birth-merge 
      move for dynamically altering the truncation level of the stick breaking 
      approximation. The first advance is quite similar to approaches 
      for memoized learning with EM algorithms. To my knowledge this approach 
      has not been applied to non-paramteric Bayesian models however, which is 
      the major novelty of this part of the work. The birth merge move 
      is in my view the more interesting advance in this paper, as it elegantly 
      handles the issue of proposing births while keeping a limited subset of 
      the data in memory. In the results section the authors apply the model to 
      several synthetic and real datasets and show that MO learning is able to 
      escape local optima, particularly when used with the birth merge move. 
      The paper is generally well written and easy to follow. There are 
      some small points (listed below) which would make the exposition easier to 
      follow and the experiments reproducible. In particular the specific 
      settings for the birth merge parameters would be useful. The work is a 
      nice synthesis of previous work in different settings along with some 
      novel contributions. The problem of scaling DPs to large datasets is 
      generally important since it allows for clustering with automatic 
      inference of model complexity. The authors method is simple to implement, 
      efficient and (except for births or merges) maintains the monotonic 
      increase of the lower bound. Minor Revisions: - The 
      exposition of the memoized batch updates is excellent and can be readily 
      implemented from the authors description. One thing which would make it 
      even easier would be if the authors were to provide the complete set of 
      update equations for the Gaussian emission used in the experiments in a 
      supplemental file. This would be particularly helpful to readers not 
      familiar with VB methods, for example the computation of $E_{q}[log w_{k} 
      (v)]$. - When trying to implement the birth/merge moves I found 
      the following points could be clarified in the text or a supplemental file 
      with pseudo code: 1) How was $N'$ (the size of the birth batches) 
      set in the experiments. 2) How was the DP fit in the creation step 
      of the birth move. That is was Gibbs, batch VB, etc. used. I assume batch 
      VB was used but it not stated explicitly as far a I can see. 3) 
      How exactly are the sufficient statistics inflated to protect newborn 
      clusters in the third phase of the birth proposals. 4) For the 
      merge moves clarify what exactly is cached to compute the entropy term. Is 
      it a single set O(K^2) values or one set of values per batch. - 
      The authors mention where components are inserted and deleted in the size 
      biased ordering of the stick lengths several times. Could they clarify the 
      significance of these choices. - I am not sure why the authors did 
      not compare against stochastic online methods using adaptive learning 
      rates, which is in reference [2] from the paper. - I found the 
      bottom row of figure 2 somewhat confusing. What do the colours used in the 
      covariance matrix indicate? - It would be great if the code for 
      this method and the other methods used in the comparisons could be made 
      available.