Binary to Bushy: Bayesian Hierarchical Clustering with the Beta Coalescent
Discovering hierarchical regularities in data is a key problem in interacting with large datasets, modeling cognition, and encoding knowledge. A previous Bayesian solution-Kingman's coalescent-provides a probabilistic model for data represented as a binary tree. Unfortunately, this is inappropriate for data better described by bushier trees. We generalize an existing belief propagation framework of Kingman's coalescent to the beta coalescent, which models a wider range of tree structures. Because of the complex combinatorial search over possible structures, we develop new sampling schemes using sequential Monte Carlo and Dirichlet process mixture models, which render inference efficient and tractable. We present results on synthetic and real data that show the beta coalescent outperforms Kingman's coalescent and is qualitatively better at capturing data in bushy hierarchies.
This paper develops a model for multifurcating trees 
      with edge lengths and observed data at the tree leaves; the model is based 
      on the beta coalescent from the probability literature. The authors 
      develop an MCMC inference scheme for their model, in which they draw on 
      existing work that uses belief propagation to perform inference for the 
      Kingman coalescent (an edge case of the beta coalescent in which all trees 
      are binary). The particular challenge for inference here is that there are 
      many more possible parent-child node relationships when parents can have 
      multiple children (not just two). The authors seem to use a Dirichlet 
      Process mixture model (DPMM) at each node to narrow down the space of 
      possible children subsets to consider. As the authors note, even inference 
      with the Kingman coalescent is a hard problem. In experiments, they 
      compare to the Kingman coalescent and hierarchical agglomerative 
      clustering. The Kingman coalescent is a popular modeling tool, so 
      it is great to see a practical extension of the Kingman coalescent to the 
      multifurcating case being explored for inference. The authors give a 
      convincing discussion of the interest in multifurcating trees. The DPMM 
      trick to narrow the space of children to consider for a parent is another 
      neat idea here and seems to be validated experimentally. That being said, 
      there seem to be some issues with readability and notation in the paper 
      (in particular, it is difficult to read on its own without the Teh, Daume 
      III, Roy paper and also its own supplementary material, and even then 
      there are some confusing points). And while I think that it is useful to 
      have a beta coalescent extension to the Kingman coalescent regardless, it 
      seems surprising that the Knowles, Ghahramani 2011 work on multifurcating 
      trees (which comes from the diffusion, rather than coalescing, perspective 
      for building trees) is not included in the experimental comparison (or at 
      least discussed more). Moreover, given that the main selling point here 
      seems to be the use of multifurcating trees in modeling, it would be 
      useful to see comparisons of the trees returned by the Kingman and beta 
      coalescent approaches. Some further major points: * Page 2, 
      lines 56-57: My understanding is that this sentence is saying that the 
      Dirichlet diffusion tree (DDT) and Pitman-Yor diffusion tree (PYDT) do not 
      include a generative model for edge lengths. Such a statement would be 
      false. An integral component of both models is the distance between child 
      and parent nodes, which is determined by a divergence function. These 
      trees also typically come with a (Brownian-motion-derived) generative 
      model for leaf node locations in some (typically Euclidean) space. That 
      the DDT and Kingman coalescent are in some sense inverses has been 
      exploited for modeling (see the recent work of Teh et al on 
      fragmentation-coagulation processes). From this perspective, it seems 
      disingenuous to claim that this paper is the first to provide a model of 
      edge lengths for multifurcating trees since the PYDT does so. The 
      contributions of the current work seem, rather, to be the development of 
      inference with the beta coalescent; these presumably have their own merits 
      over, and separate from, the PYDT (just as the Kingman coalescent and DDT 
      have their own merits). * A number of points in Algorithm 1 are 
      unclear. ---- * Step 8: Is i local to s? Should it have an s 
      subscript? Or should this incrementation be outside the for loop? ---- 
      * Step 14: pi doesn't really seem to be defined in the main text. Page 2, 
      line 67: The "tree structure" pi is mentioned but not defined, and Page 4, 
      line 166: the "tree structure" theta_i is mentioned but not defined. How 
      does pi differ from theta? Without definition, it's unclear what the 
      subtraction and addition in Step 14 mean. * There are other notational 
      issues: ---- * It is unclear what the role of p_0(y_i) is or how it is 
      chosen. It is not clear why the current authors diverge from Teh et al, 
      who seem to use a base distribution at the root, and here instead use a 
      distribution at each node. How does this distribution interact with the 
      transition kernel? Z_{-\infty}(x) does not seem to be defined explicitly 
      (Eq. 6). ---- * The superscript s seems to be introduced on page 4, 
      line 168 without being defined or discussed. There later seems to be some 
      confusion about what is particle-specific and what is not. E.g., line 241, 
      page 5: what does Omega_i restrict? All particles? The notation for 
      Omega_i later switches to an s dependence. If a DPMM is run for each (s,i) 
      pair, it would be helpful to be explicit in the text about this. 
      Conversely, in Eq. 11, why does lambda_{n_i - 1}^s have an s superscript? 
      That seems to at least overload the notation on page 2, line 83. * 
      Some details and choices in the experiments were confusing, e.g.: ---- 
      * Why was alpha = 1.2 chosen for the beta coalescent? This seems somewhat 
      arbitrary. Likewise, why the choice of 5 chains with 5 particles per chain 
      (page 7, line 364) vs 5 chains and 80 particles each later (page 8, line 
      401)? Also on line 364, how many dimensions were kept after using PCA? 
      ---- * In the definition of the purity score, is the purity score 
      averaged over all pairs? ---- * Page 7, line 338 suggests that the 
      synthetic data comes from a beta coalescent generative process, but the 
      appendix seems to demonstrate this is not true. That the generating 
      process is not a beta coalescent should be clearer in the main text. 
      Moreover, in the supplementary material, it's not clear how the actual 
      nodes (as opposed to the number of nodes) for merging are chosen at each 
      round. Presumably the true model is not used for synthetic data generation 
      because it is too computationally complex; this is worth mentioning in the 
      text. ---- * It's unclear why the effects described on line 345 on 
      page 7 are evident. Does increasing the number of observations have no 
      effect simply because the maximum (and best) score is already attained? 
      ---- * How were the sample hierarchies in Figs. 3 and 4 chosen? Were 
      they, e.g., just the final samples in the chain? Minor comments: 
      * Page 1, line 38 (and elsewhere): The term "bushy" is often used to 
      describe binary trees (in particular, balanced binary trees). The authors 
      here seem to use it describe multifurcating-ness of trees. If the authors 
      wish to use the word "bushy", I would suggest defining their desired usage 
      early on (at least before the first use in the main text besides section 
      headings). * Page 2, line 80: Be explicit about the Kingman coalescent 
      representation as a Lambda coalescent. Namely, the measure Lambda is the 
      Dirac delta measure at 0 in this case. * Page 2, line 103: Can 
      anything specific be said to support the statement that this approach is 
      "more scalable"? E.g., some asymptotic bounds/analysis? * Page 4, line 
      187: Is this meant to be computational complexity just for the ith 
      coalescent event? If so, n_i - 1 or n_i should be used instead of n. If 
      it's for all events, since the Kingman coalescent considers every pair of 
      nodes after each coalescent event in the tree, it would seem the cost of 
      growing a Kingman coalescent is something like a constant times n^2 + 
      (n-1)^2 + (n-2)^2 + ... + , which would be asymptotically like n^3, not 
      n^2. And the result for the beta coalescent would be not obvious in this 
      case. * Page 5, line 217: Consider using a different notation for the 
      identity matrix and the indicator function (cf. Eq. 9). Define the 
      identity matrix notation at first use (here) instead of line 92, page 2 in 
      the supplementary material. I'm not sure why ref [10] is referenced on 
      page 5, line 217 or why this relationship between the mutation rate and 
      Dirichlet concentration parameter is chosen. * Eq. 12: Should this be 
      t_b instead of t_{b_i}? * In supplementary material Section 2, x_n is 
      overloading notation with the main paper. Also, n_k should be explicitly 
      defined, and also z_i^k (which appears to be 1\{ z_i == k\} ). === 
      Update after Author Feedback === The Author Feedback addressed my 
      concerns as much as seems possible in the constrained space. I am 
      optimistic this will be a solid paper after a round of 
      editing.