Maximization of mutual information between the model's input and output is formally related to "decisiveness" and "fairness" of the softmax predictions, motivating these unsupervised entropy-based criteria for clustering. First, in the context of linear softmax models, we discuss some general properties of entropy-based clustering. Disproving some earlier claims, we point out fundamental differences with K-means. On the other hand, we prove the margin maximizing property for decisiveness establishing a relation to SVM-based clustering. Second, we propose a new self-labeling formulation of entropy clustering for general softmax models. The pseudo-labels are introduced as auxiliary variables "splitting" the fairness and decisiveness. The derived self-labeling loss includes the reverse cross-entropy robust to pseudo-label errors and allows an efficient EM solver for pseudo-labels. Our algorithm improves the state of the art on several standard benchmarks for deep clustering.
Paper
Similar papers
Peer review
Summary
In this paper, the authors first presented an analysis of the relationship between the regularized information maximization (RIM) clustering framework to K-means and SVM-based clustering methods, showing stronger similarities to the SVM-based clustering than K-means. Then they proposed a new loss function and associated EM optimization algorithm for clustering leveraging the reverse cross-entropy/KL divergence to obtain more robust and fair clustering, which has been demonstrated to improve the performance on several balanced image classification benchmarks.
Strengths
1. The authors identified an error about the missing normalization term in the proof of the equivalence theorem presented in Jabi et al. (2021). 2. The replacement of the forward cross-entropy with the reverse counterpart in the RIM loss appears novel in the clustering scenarios and has the potential to effectively mitigate the impact of uncertain/noisy pseudo-labels. 3. The proposed method showed improved performance on different image classification benchmarks over several baselines.
Weaknesses
1. The manuscript was poorly written. The authors dedicated more than two pages to discuss the general background of the information maximization clustering framework and related methods. However, these discussions were confusing and largely limited the space for presenting the actual contributions of this work. Furthermore, many terms, including concepts like H and KL divergence, are not explicitly defined or explained, which may cause difficulties to understand the differences between the forward and reverse formulations. Additionally, the claimed conceptual and algorithmic contributions seem to be independent of each other. It is unclear if any of these conceptual clarifications contribute the discovery of the new loss function. 2. The disproof of the equivalence theorem in Jabi et al. (2021) is not convincing. While the authors pointed out an error in the original proof, this does not necessarily eliminate the possibility that the equivalence itself remains valid. Furthermore, this work focused on the standard K-means objective (including Figure 1), whereas Jabi et al. (2021) considered a soft and regularized K-means loss. 3. The authors' claim that the L2 regularization is linked to margin maximization seems questionable. [1] demonstrated that margin maximization is a property of the loss function itself rather than the regularization, which serves to control the model complexity. Indeed, certain combinations of loss function and regularization are not margin-maximizing. 4. The experimental validation is limited. A more comprehensive evaluation of the proposed modifications to the loss function would involve investigating the individual and combined effects of these changes on selected benchmarks and then comparing the results with multiple established baselines. It is still unclear how each modification contributes to the final improvement. Although the authors presented the impact of the reverse cross-entropy modification, they did so within the fully supervised setting rather than unsupervised scenarios. Furthermore, the authors only considered balanced datasets and tested the clustering with the ground truth number of clusters. A more diverse set of experimental conditions, including unbalanced datasets and varying numbers of clusters, would provide a more robust evaluation of the proposed method. Both NMI and ARI metrics used in Table 4 are capable of handling different number of clusters. Additionally, the architecture used in Section 4.2 is different from that used in the baseline methods. It would be preferable to standardize the experimental settings, including model architecture, to be able to directly compare with the results in the literature. Lastly, the inability of the proposed method to properly train a deep network-based clustering model is a concern as well. Most of the tricks should be independent of the loss function modifications, especially the reverse cross-entropy term, thus can be naturally integrated together. [1] Rosset et al., 2003. Margin maximizing loss functions.
Questions
1. Could the tolerance of "highly unbalanced solutions where $\bar{\sigma}_k = 0$ for some cluster k" be a good thing, especially when we over-cluster in practice? 2. How were the coefficients of the norm regularization and KL divergence determined in the proposed method and relevant baselines? Were they shared across all the methods? How could we select these coefficients in practice in an objective way since the performance is very sensitive to these values? 3. The K-means results reported in Table 2 for CIFAR10/100 do not match with those in Table 3 in the IMSAT paper, but both employed the pretrained ResNet-50 extracted features. This raises the question of the reliability of the reported quantitative results. 4. Why only used the 20 coarse categories for the CIFAR100 benchmark? 5. The authors mentioned that "if we simultaneously learn the representation/feature and cluster the data, we observed that the results are less sensitive to such coefficient." But I could not find these results in the main text or supplementary material. 6. Table 4 presents a comparison with SCAN but does not include any comparisons with the baseline methods featured in Table 3 following the same two-stage training.
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
1 poor
Contribution
2 fair
Limitations
There is no discussion of limitations or potential societal impact.
Summary
This paper first discusses a number of general properties of entropy clustering methods, including their relation to K-means and unsupervised SVM-based techniques. Then the aurthors find that cross-entropy is not robust to pseudo-label errors in clustering. Finally, this paper proposes a new loss function based on reverse KL divergence for clustering to obtain more robust and fair clustering.
Strengths
(1) The proposed loss function is interesting and and seems to be effective to obtain more robust and fair clustering. (2) The authors try to establish connections between entropy clustering methods and classical methods.
Weaknesses
(1) This paper is not well organized. There are too many details for the proposed method. Some of them can be moved to Appendix. (2) There can be more descriptions and examples about the proposed method. (3) The proposed method is merely tested on three image datasets.
Questions
(1) Will the authors open-source the code?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
3 good
Limitations
I mentioned them in the Weakness section.
Summary
The paper presents a very interesting analysis of discriminative entropy clustering in the literature and their use for self-labeling highlighting clear interpretation of the conditional and marginal entropy terms as decisiveness (push to have confident predictions) and fairness (to encourage desired proportions in clusters). The paper analyzes the variants of this kind of losses and their connections. They also discusses the relationship of this loss to K-means and refines the previously mistaken connection in a previous paper to point out the distinct difference. They further point out the effectiveness of reverse cross-entropy in case of uncertainty error and forward KL term to make them more effective in the endpoints of softmax interval. They also propose to use the regularization of classifier weights for margin maximization similar to SVM. A closed form update is derived to compute the pseudolabels from the combined weighted loss and shown its efficacy in clustering experiments.
Strengths
- I think the paper discusses beautifully the intricacies and usage of Mutual information based entropy clustering loss, which is widely used in self labeling/self supervised/ weak supervised learning. The flow of the discussion is to the point and tries to give interpretation of each terms in the loss in a concise manner by drawing connection among the variants. - The paper discusses the the previous link of entropy clustering to K-means and identify the distinct difference to k-means which was in fault in previous literature. On top of that they find the usefulness of the classifier weight regularization used in previous proof to link to the loss explicitly for margin maximization similar to SVM based clustering. - The use of reverse cross-entropy and forward KL term and the motivation behind it is explained very well with the aid of Figure 2, so that they are more robust in case of uncertainty around the corner of the softmax simplex. - The formulation of the EM algorithm is nice to make it work faster along with batchwise operation, showing its global optimal solution guarantee at convergence due to drawing convexity with formulated tight upper bound. - The experimental results shows clear improvement according to their claim.
Weaknesses
1. I would say the results of joint clustering and feature learning in Table 3 is not encouraging even when showing a very shallow network of VGG4, the improvement is not significant apart from MNIST. But in Resnet-18, the inductive bias learned from pretraining is helping, then the improvement from the proposed loss might not improve very significantly with the proposed loss. Also in Table 4, the regularization on the feature extractor $\textbf{w}$ done or not in the loss or by weight decay? 2. The experiments on semi supervised learning could also be shown to understand more when some supervision is available. How the idea of using reverse cross-entropy could be used in case of labeled one-hot y in equation 13? or it will be the regular cross-entropy for labeled set and reverse for pseudolabels with updated y_i? 3. What if the loss in 13 is directly optimized with gradient descent instead of using the EM? Although, it seems if $y_i= \sigma_i$ the reverse cross-entropy does not change anything if not updating y_i with closed-form update, is it?
Questions
- In Algorithm 1, after updating the pseudolabels y_i in closed form solutions, the loss in the gradient descent is without the KL term in ALgorithm 1 in appendix. Is it a typo or the KL term is not required here?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
4 excellent
Contribution
4 excellent
Limitations
The limitations are not discussed.
Summary
The authors consider discriminative entropy clustering and produce a discussions linking previous works. They have a version of the algorithm based on EM and a modified KL-divergence term. Experiments show the modified algorithm works better than competing methods with small networks.
Strengths
- The authors provide a good overview of discriminative entropy clustering and its development, from the work of Bridle et al to the regularized version by Krause et al, to the more recent work using deep learning and representation learning (Asano et al and Jabi et al).
Weaknesses
- The contribution of this paper is somewhat limited: 1. The pointing out of a proof error in Jabi et al is helpful but is not significant on its own 2. The discussion on SVM is based on previous works and simply replaces the logistic loss with margin loss, and is not particularly insightful 3. Section 3 is the authors' contributed new algorithm, but the main difference with previous works is changing the order of the KL term in the objective. - The improvements in empirical evaluations, compared to other methods, are somewhat limited. Many of the improvements are within standard error of competing methods. - The authors use a lot of space to discuss previous work (first 5.5 pages), and not enough space to explain what is new about their method and specifically what problems it addresses.
Questions
- Is there any explanation on the joint clustering and feature learning working only on small networks like VGG4, but not on larger VGG or ResNet18?
Rating
3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
2 fair
Contribution
2 fair
Limitations
Limitations not mentioned; potential negative societal impact not applicable.
Thanks for the response, which has addressed some of the concerns. However, there are still several remaining. First, all clustering results are obtained using the "ground truth" number of clusters, but we rarely have this information in practice. Thus, it would be much better to test the robustness of the proposed method with different number of clusters. Both NMI and ARI metrics are capable of handling different number of clusters. Second, the authors still did not provide any explanation regarding why only used the 20 coarse categories for the CIFAR100 benchmark. It is unclear if the proposed method only shows benefits with limited number of clusters.
Thank you for taking the time to clarify these remaining concerns. We simply did not have space in the original rebuttal to answer all of your detailed comments. We are happy for the opportunity to address these here. We would like to divide your comment into two relatively independent parts: (A) how does our method work when the number of clusters $K$ is not known, and (B) evaluating our method for different but **fixed** $K$. **(A) Estimating the unknown number of clusters $K$** In general, the assumption of the known number of clusters is significant and limits the practical usefulness of any clustering method based on this assumption. We are acutely aware of this in the context of some practical applications in our lab (e.g. clustering of DNA sequences). We are highly interested in addressing this question in our future work. As far as our submission is concerned, we do not make any general claims that we solved the clustering problem, which is fundamentally ill-posed [1]. Thus, some assumptions always have to be made (ideally, specific to the application). More specifically, our paper is focused on the general entropy clustering methodology [2-8]. All these and other prior works on entropy clustering assume that the number of clusters is fixed (even though some of them do experiments for different **fixed** $K$ on either simpler or different problems, see (B)). This assumption is very similar to the fundamental assumption in the basic *K-means* methodology, which is even reflected in its name. This is not to say that K-means cannot be generalized in a way where $K$ becomes an estimated variable, but this requires additional terms added to the loss (e.g. AIC or BIC information theoretic criteria). In fact, similar ideas can be explored in the context of entropy clustering, but, this is a substantial topic on its own. We do have plans to continue in this direction in our future work. We can more clearly state that fixed $K$ is an assumption made by us and all the previous works on entropy clustering (at least those we are aware of). **(B) Evaluating performance for different fixed $K$** Evaluating robustness to different (but fixed) $K$ would be interesting, but no prior entropy clustering papers compare NMI and ARI metrics using different $K$ on the data like STL10, CIFAR10, CIFAR100. All such prior works [2-8] typically do not vary $K$ on these datasets - they use them with NMI and ARI for one fixed $K$ (the same as in our experiments). We only see two exceptions: [3] shows some results with various $K$ but on much simpler datasets, while [7] vary $K$ on ImageNet - they are focused on representation learning and do not report clustering quality metrics like NMI or ARI. Also, we agree with your point about testing $K>20$ on CIFAR100, but we simply stuck to the experiments that we saw in prior work on entropy clustering. Moreover, we do not see any technical reason why our approach would differ from other entropy clustering methods in its robustness to $K$. We agree that entropy clustering methods (in general) should be evaluated for robustness to $K$, but it may be best to combine such evaluation with the proper study of point (A) above and present these in a separate dedicated paper. [1] An impossibility theorem for clustering, Kleinberg, NeurIPS 2002 [2] Briddle et al. 1991 [3] Krause et al. 2010 [4] Hu et al. 2017 [5] Ghasedi Dizaji et al. 2017 [6] Ji et al. 2019 [7] Asano et al. 2020 [8] Jabi et al. 2021
I would like to thank the authors for the rebuttal. I am still skeptical about the claimed contributions in Section 2.2 after the rebuttal. In classification it is common to switch between the hinge loss in SVM and cross entropy loss in logistic regression, and the linear class balance constraint used in Xu et al 2004 and the entropy regularization term are also well-known in semi-supervised learning literature. So what is the main new understanding in this section? As for the point on Section 2 (page 4-6), it still reads much more like a literature review than a description of new theoretical understanding. If there are new theoretical understanding, the authors could have stated it formally using a simple lemma or theorem. This makes it easier for reviewers to evaluate whether the claim is novel or significant. Updated Table 4 shows improved results, but the results in Tables 2 and 3 are mostly still within standard errors of top 2/3 competing methods. The issue with the empirical evaluations is not just whether the method beats the state-of-art, but whether the improvements come from the algorithmic advances the authors propose. Since the empirical difference is relatively small, how can we be sure the improvements come from the self-labeling mechanism or changes to the KL-term?
>**"In classification it is common to switch between the hinge loss in SVM and cross entropy loss in logistic regression, ... what is the main new understanding in Section 2?"** Indeed, "switching" between hinge loss and cross-entropy is known in SVM **classification**, as discussed in textbooks [1] that we cite. But we would like to emphasize that our paper is on **clustering**, which is a significantly different problem, in particular, it is **unsupervised**. We are first to point out the relation between entropy clustering and margin maximization, to the best of our knowledge. Perhaps convincing arguments in our paper make this obvious, but it was not known to many highly respected scientists working on entropy clustering [2-5]. These papers have no references to SVM clustering [6], maybe because it was not obvious to them that there is any relation. Moreover, the result published in 2021 in the top ML journal [5] claims that the entropy clustering is equivalent to K-means. This directly contradicts the relation to SVM clustering [6] since K-means has no margin maximization property. In short (and directly answering the reviewer's question), the main new understanding that our paper provides for the ML community is that entropy clustering has margin maximization property and closely relates to SVM-based clustering [6]. Instead, the community currently believes that entropy clustering is related to K-means, which is incorrect. >**"Section 2 still reads much more like a literature review than a description of new theoretical understanding. If there are new theoretical understanding, the authors could have stated it formally using a simple lemma or theorem."** Concerning Section 2.1, we do not see how an error that we found in the proof of the main result in [5] (equivalence to K-means) can be stated as a theorem. Neither do we understand how our counterexample to their claim (see Fig 1) can be stated as a theorem. Does the reviewer have specific suggestions? Concerning Section 2.2, it might be possible to state some formal property on the relation between regularized entropy clustering and margin maximization (e.g. see an informal claim in the first part of the general rebuttal). However, a similar formal claim may be formalistic and weak as an assumption restricting the claim to fair solutions is unavoidable. A similar issue also exists in standard **soft** SVM formulations for classification. Such losses seek a compromise between margin size and margin violations, but it is difficult to formally define what max margin even means for non-separable labeled data. In our unsupervised setting, data doesn't even have ground truth and our combined loss for unsupervised clustering also includes a soft fairness constraint (e.g. KL divergence term). For now, we prefer not to make any formal claims in Sec 2.2 and leave this development for future work. We believe that Section 2.2 works sufficiently well without a formal claim. For example, [6] introduced "max-margin clustering" (as stated in their title) but they do not have any theorem or lemma proving that their method produces max-margin clusters, which are not even formally defined. Yet, most readers of that paper will probably be convinced (just like us) that their formulation of clustering is related to margin maximization. Their self-labeling methodology integrates the standard soft margin SVM formulation with a soft fairness constraint. **References** [1] Bishop (2006) [2] Briddle et.al. (NeurIPS 1991) [3] Krause et al. (NeurIPS 2010) [4] Hu et al. (ICML 2017) [5] Jabi et al. (TPAMI 2021) [6] Xu et.al. (NeurIPS 2004)
>**"Updated Table 4 shows improved results, but Tables 2,3 are mostly within standard errors..."** We are glad that the reviewer seems satisfied with our results in Table 4, which is important for practical clustering since it removes artificial constraints (fixed features or randomly initialized features without pretraining). Still, we agree that Tables 2 and 3 are highly relevant. Please note that the **consistency** of our method over different datasets/applications in Tables 2 and 3 is a significant advantage. Our method is the top performer on almost all benchmarks (including Tables 2 and 3), while most prior methods that come close on some of the examples are not consistent on others. Also, it is reassuring that we achieve consistent top performance using a mathematically transparent formulation. >**"how can we be sure the improvements come from the self-labeling mechanism or changes to the KL-term?"** Comparisons with the basic (non-self-labeling) formulation of entropy clustering [2,3] are present in Table 2 (MI-GD), Table 3 (MI-D), and Table 4 (IMSAT). The latter two include self-augmentation, which is why we cite other papers there. We will clarify this and perhaps unify the labels in these Tables. Interestingly, some prior self-labeling methods do not compare with these early works (for no clear reason) while performing worse, at least in our tests. To the best of our knowledge, our experiments are the most comprehensive empirical evaluation of the entropy clustering methods, which is one of the useful contributions of our work. Advantages due to the proposed changes in KL and cross-entropy terms should be clear from comparison with the entropy clustering formulation in [5] (see Tables 2,3,4) where the only difference is the order of variables in KL and cross-entropy terms. We can not easily test each of these "switches" independently as we could not formulate an efficient self-labeling algorithm when only one of the terms is switched. Note that the differences with [5] in Tables 2,3,4 are substantial, in some cases above 14%. Also, we directly compared the forward and reverse cross-entropy in the fully supervised setting demonstrating a significant advantage of our formulation (see Fig 3). We find this particular test significant, and it was also positively noted by other reviewers. **References** [1] Bishop (2006) [2] Briddle et.al. (NeurIPS 1991) [3] Krause et al. (NeurIPS 2010) [4] Hu et al. (ICML 2017) [5] Jabi et al. (TPAMI 2021) [6] Xu et.al. (NeurIPS 2004)
Decision
Reject