Summary Statistics for Partitionings and Feature Allocations
Infinite mixture models are commonly used for clustering. One can sample from the posterior of mixture assignments by Monte Carlo methods or find its maximum a posteriori solution by optimization. However, in some problems the posterior is diffuse and it is hard to interpret the sampled partitionings. In this paper, we introduce novel statistics based on block sizes for representing sample sets of partitionings and feature allocations. We develop an element-based definition of entropy to quantify segmentation among their elements. Then we propose a simple algorithm called entropy agglomeration (EA) to summarize and visualize this information. Experiments on various infinite mixture posteriors as well as a feature allocation dataset demonstrate that the proposed statistics are useful in practice.
The authors propose 2 statistics for summarizing 
      samples from the prior or posterior distribution of random partitions and 
      feature allocations and an algorithm which is a variation of agglomerative 
      clustering with a different merging rule in terms of one of their proposed 
      statistics. Their first proposal is what they call a COD matrix, 
      this is constructed from a Young diagram of a partition and a projection 
      operation which helps distinguish more segmented clusters from less 
      segmented ones. Their second proposal is to compute the entropy of this 
      projection rather than build its COD matrix. They show some experiments 
      for various data sets in which they use a DP mixture model and show the 
      corresponding posterior distribution for the number of clusters, 
      co-clustering probabilities and dendrograms obtained from their entropy 
      agglomeration algorithm. They motivate the problem really well 
      and it is quite an important open question but it is not clear if their 
      proposal is a solution to it. This is because they use the samples of the 
      posterior distribution as an input for their agglomerative clustering 
      algorithm and show the corresponding dendrograms, which they claim to be 
      useful summary statistics of the posterior distribution over the number of 
      clusters. Usually, dendrograms are seen as summaries of any agglomerative 
      clustering algorithm so it is not really clear why they can also be 
      interpreted as summary statistics for the posterior distribution of number 
      of clusters. Furthermore, they don't elaborate on this point or compare it 
      to Medvedovic & Sivaganesan (2002) agglomerative clustering algorithm 
      which also uses samples from the posterior distribution for computing the 
      co-clustering probabilities. For example: What does the tree depth tells 
      us about the posterior distribution?, Does it recovers the number of 
      clusters in a better way? Which characteristics of the posterior are 
      reflected on the dendrogram? Is it sensitive to different priors? ( a 
      simple case would be to compare CRP v.s. 2-CRP) I think if we had this 
      comparisons and convincingly show that their algorithm is better and that 
      the summary statistics reflect novel/specific information about the 
      posterior it would be really interesting. Alternatively, if the algorithm 
      performs well against any of the existing AC ones then it would be good to 
      see its performance in various settings and detailed explanation of its 
      properties. The latter would be useful in its own right whether or not it 
      is related to summarizing posterior distribution's characteristics. 
      A few specific comments: Line 19: It is correct to say 
      that the MAP might not be good in situations where the posterior is 
      diffuse, I guess you mean uniform-like? It might also be multimodal, 
      skewed (mode and mean differ), high variance,for example, so the MAP is 
      not necessarily a good choice although it depends on the (underlying) loss 
      function. Line 52: Since a Dirichlet Process is a discrete random 
      probability measure, when sampling from it it induces a random partition 
      (the ties will belong to the same cluster). If you sample, say, n times 
      from the DP, then you obtain a draw from a random partition of size 
      k<=n with its corresponding frequencies n_i, i=1,...k. The joint 
      distribution of k and the frequencies is what people call a CRP, but this 
      is just a joint distribution of this objects so there is no need to 
      'generalize' entropy since it is defined for any probability distribution. 
      Furthermore, it is incorrect to say that partitions are interpreted as 
      probability distributions for the above reasons. Line 65: I don't 
      think you need to make the footnote's distinction since an integer 
      partition is just a set partition where your total set is {1,...,n}. 
      Line 70: It is not clear what k is. Line 72: Reference [3] is not 
      the appropriate one for this, there should be an earlier one. Line 74: 
      Usually, the term 'collapsed Gibbs sampler' in infinite mixture models 
      case, refers to the fact that, rather than having to sample a parameter 
      for each observation (n operations in a dataset of size n) you only need 
      to sample a parameter for each cluster (k <= n operations in a sample 
      of size n). It's more precise to call this ' conjugate marginal sampler' 
      since we can effectively integrate out parameters due to the conjugacy of 
      the base distribution with the likelihood. Line 77: Reference [7] is 
      not the appropriate one for equation (2) since this is Algorithm 3 
      (conjugate case and Neal's paper extends this for the non-conjugate case 
      in Algorithm 8). The correct reference is MacEachern (1994) and also Neal 
      (1992) (Check the references in Neal's paper). Line 136: Might be good 
      to reference Z. G. Su (2007) "Asymptotic analysis of random partitions", 
      for example, for the Young diagram part. Line 154: I don't understand 
      what you mean by 'conjugacy' here. Young diagrams are a graphical 
      representation of the cumulative statistic by definition, see above 
      reference. Line 162: I think it is incorrect to say that 'the 
      cumulative statistic is always the conjugate partition on the integer 
      partition of Z'. The definition of a conjugate partition is: 'the 
      conjugate partition of a partition is the partition whose Young diagram is 
      the transpose of the Young diagram of the first one'. Check reference 
      above/explain why in this case it's equivalent. Line 191: Indeed, 
      since a CRP is projective and exchangeable then the distribution of the 
      random partition doesn't depend on the particular permutation but this 
      does not explain why the argument inside the expectation doesn't depend on 
      the permutation since the incremental construction clearly does. So it 
      would be nice to see why the resulting COD matrix is independent of sigma. 
      Line 215: This legend is misleading since the COD matrices here 
      correspond to {1,2,..,7} and Z(1) of the previous page, Line 144. 
      Furthermore, it is not clear why these 3 cases are illustrative or just 
      randomly picked. Line 229: The incremental formulation is interesting 
      but it's not used in any other part of the paper, neither the COD matrix. 
      Line 239: It is important to make the distinction between CRP and 
      2-CRP. Line 252: Is n the number of data points? It might help to 
      clarify this. Line 300: It might help to give a toy example with 
      feature allocations to get a better grasp the definition of entropy of 
      equation (11). Also, explain why the cumulative statistics for feature 
      allocations do not preserve mass. Line 307: The projection operation 
      was nicely motivated previously in the toy example (Line 145) since it 
      helped to distinguish between more segmented partitions. However, it is 
      not immediately obvious what does it mean to take the entropy of this. 
      Line 310: Figure 4 should be around here rather than in the previous 
      section. Line 321: It might help to explain how the posterior samples 
      are used in the pseudocode,e.g. rather than calculating the expected 
      entropy you use the samples from the posterior distribution to estimate 
      it, assuming that this is indeed how you use the posterior samples. 
      Line 327: It is not clear for me how does the dendrogram encode useful 
      information about the posterior distribution of the partition. It would be 
      nice to elaborate about this, e.g. was does the tree depth tell us. 
      Line 332: It is not immediately obvious why this method is principled 
      rather than a heuristic. Furthermore, it would be useful to provide more 
      arguments of why is it better than any of the existing agglomerative 
      clustering approaches or at least against Medvedovic & Sivaganesan 
      (2002) e.g. does it recover the correct number of clusters better. 
      Quality: this is a well written paper. Clarity: the 
      importance of the problem is clearly explained and the paper has nice 
      figures to illustrate the concepts but there are parts which are not well 
      connected. Originality and Significance : the paper introduces 
      nice ideas however I am still not sure if it is indeed a solution to the 
      problem of summarizing samples from a random partition.