Dynamic Clustering via Asymptotics of the Dependent Dirichlet Process Mixture
This paper presents a novel algorithm, based upon the dependent Dirichlet process mixture model (DDPMM), for clustering batch-sequential data containing an unknown number of evolving clusters. The algorithm is derived via a lowvariance asymptotic analysis of the Gibbs sampling algorithm for the DDPMM, and provides a hard clustering with convergence guarantees similar to those of the k-means algorithm. Empirical results from a synthetic test with moving Gaussian clusters and a test with real ADS-B aircraft trajectory data demonstrate that the algorithm requires orders of magnitude less computational time than contemporary probabilistic and hard clustering algorithms, while providing higher accuracy on the examined datasets.
Summary: The paper presents a deterministic inference 
      algorithm for a clustering problem for batch sequential data (data in 
      each batch exist in clusters, and clusters across batches are related 
      as per some evolving structure). The Dependent Dirichlet Process 
      Gaussian mixture model (DDP-GMM) is a nonparametric Bayesian method 
      for dealing with such data. The paper uses the idea of doing 
      low-variance asymptotics on the Gibbs sampling update equations in a 
      DDP-GMM model (a similar approach was recently proposed by Kulis and 
      Jordan for DP-GMM in their DP-means algorithm) and derives a 
      deterministic algorithm that is (1) more efficient to implement than Gibbs 
      sampling for DDP-GMM, (2) can learn the number of clusters just like 
      DDP-GMM. Experimental results on a synthetic and a real dataset show 
      that the proposed algorithm runs fasters than other inference methods 
      for DDP-GMM such as Gibbs sampling, variational inference, and 
      sequential Monte Carlo. Quality: The technical quality is rigorous 
      and the details appear to be correct. Clarity: The paper is 
      well-written and the exposition is easy to follow. Originality: 
      The paper is based on recently proposed idea of using low-variance 
      asymptotics on the Gibbs sampling update equations in case of DP 
      mixture models. Significance: The paper addresses an important 
      problem (scaling up nonparametric Bayesian methods for large 
      datasets). Paper Strengths: - The proposed algorithm is 
      intuitive, seems easy to implement, and is scalable for large 
      datasets. - Although the basic recipe is borrowed from the 
      DP-means work of Kulis and Jordan (taking the Gibbs sampling updates 
      and applying the low-variance asymptotics), the ideas in section 3.2 
      (parameter updates) are rather novel in this context. Paper 
      Weaknesses: - The algorithm has 3 free parameters. For an 
      unsupervised algorithm (with no option of doing cross-validation), 
      this is a bit worrying. Although the paper gives some suggestions on 
      how to choose the parameters, it is not clear how well they will work 
      in practice. - There should have been a comparison with a 
      simple variant of the DP-means algorithm (Kulis and Jordan, 2012) for 
      batch-sequential data (see the suggestion in the comments below on how 
      to do it). - On real-data, there is no comparison with variational 
      inference or particle learning. Comments: - It would 
      have been nice to compare the proposed dynamic-means algorithm with a 
      very simple adaptation of the DP-means algorithm: Run DP-means on one 
      batch and initialize means for the next batch using the results of 
      this run. I would be curious to see how dynamic-means compares against 
      this alternative. - It turns out that instead of doing 
      small-variance asymptotics on the Gibbs sampling updates, one could 
      also do MAP-based asymptotics to derive hard-assignment based variants 
      of nonparametric Bayesian models such as DP-GMM or IBP-based latent 
      feature models (there is a recent paper by Broderick et al from ICML 
      2013: "MAD-Bayes: MAP-based Asymptotic Derivations from Bayes"). Is it 
      possible to derive the dynamic-means algorithm using this approach? 
      Please comment. - There is work on temporal DP mixture model based 
      on recurrent Chinese restaurant process which is similar in spirit to 
      dependent DP mixture models. Please see this: "Dynamic Non-Parametric 
      Mixture Models and The Recurrent Chinese Restaurant Process : with 
      Applications to Evolutionary Clustering" by Ahmad and Xing (2008). It 
      would be nice to have a discussion about this link of work. Please also 
      comment whether doing low-variance asymptotics on these methods would 
      lead to similar algorithms as dynamic-means? - In the DP-means 
      algorithm of Kulis and Jordan, the order of data points mattered. In 
      the cluster assignment step of the dynamic-means algorithm, does the order 
      of data points (within a single batch) matter? Please 
      comment.