Dependent nonparametric trees for dynamic hierarchical clustering
Hierarchical clustering methods offer an intuitive and powerful way to model a wide variety of data sets. However, the assumption of a fixed hierarchy is often overly restrictive when working with data generated over a period of time: We expect both the structure of our hierarchy, and the parameters of the clusters, to evolve with time. In this paper, we present a distribution over collections of time-dependent, infinite-dimensional trees that can be used to model evolving hierarchies, and present an efficient and scalable algorithm for performing approximate inference in such a model. We demonstrate the efficacy of our model and inference algorithm on both synthetic data and real-world document corpora.
The authors propose a dynamic hierarchical clustering model which allows hierarchies clusters (topics) and corresponding parameters (popularities, word frequencies) to vary in time. Indeed, it is a stochastic process with tree structured marginals so a different hierarchical clustering is specified per time index. Since in general it is a computationally expensive task to do full Bayesian inference they propose an approximate inference scheme where the parameters of each node are MAP estimates and the node re-assignment of observations is done by a Gibbs step. It is based on the tree structured stick breaking process so it allows the observations to be assigned to internal nodes and leaves of the tree rather than just leaves or complete paths. My main concern is that it is not fully exploiting the non-parametric nature of the model since the authors fixed the depth of the trees in the experiments. It would be nice that the depth varied over time or that a more detailed sensitivity analysis was presented.Some specific comments:Line 111: In this section I suggest to write the full generative model for each example (this could be added to the supplementary material if it is too long) just to be able to see how one could do full Bayesian inference in this model. Furthermore, maybe a MAP-Bayes like scheme (hard clustering assingment) could be obtained as a limit? I guess this would be a different approach so no need to include this.Line 244: Here it would be nice to have the corresponding conditional distribution for the parameters \theta for both examples in the previous section. It would be good to have this expression so one can see why you can't obtain MAP estimates directly and hence, the need for the coordinate ascent on this expression. Line 358: why is it sensitive to initialization? Or is this just done to ensure that the Gibbs sampling has converged?Line 371: while it is true that shallow hierarchies are easier to interpret it is still not quite satisfying to choose the depth of the tree to be 3 or 4 for every tree. One of the benefits of the model is to get different trees per time index so it would be nice that their corresponding depths varied as well. Furthermore, it would be nice to have a principled way of choosing the depth or at least a criterion which exploits the nonparametric nature of the model (in terms of tree distance, say). For example, as in Lakshminarayanan et al (2013), Mondrian Forests:Efficient Online Random Forests, ArXiv 1406.2673 where they suggest a budget parameter to handle this or in linkage algorithms where you choose your tree depth depending on certain criterion based on a fixed distance.Line 399: Is it possible to obtain a MAP tree? Since one can obtain a different tree per time index it would be interesting to know if there is a way to combine/summarize such trees just to see if there is a recurring pattern. This could justify or not the assumption that hierarchies vary over time.Supplementary material:Line 53: The proof of theorem 1 could be improved. It is not clear to me why is it the case that after deterministic deletion the resulting process is still TSSBP. The proof could be more mathematically precise.Quality: this is a really well written and structured paper.Clarity: the importance of the problem is clearly explained and the paper has nice figures to illustrate the concepts and results.Originality and Significance : the paper introduces novel ideas.