Collision Cross-entropy for Soft Class Labels and Entropy-based Clustering

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 22:05:39

Abstract: We propose ''collision cross-entropy'' as a robust alternative to Shannon's cross-entropy (CE) loss when class labels are represented by soft categorical distributions y. In general, soft labels can naturally represent ambiguous targets in classification. They are particularly relevant for self-labeled clustering methods, where latent pseudo-labels $y$ are jointly estimated with the model parameters and uncertainty is prevalent. 
In case of soft labels $y$, Shannon's CE teaches the model predictions $\sigma$ 
to reproduce the uncertainty in each training example, which inhibits the model's ability to learn and generalize from these examples. As an alternative loss, we propose the negative log of ``collision probability'' that
maximizes the chance of equality between two random variables, predicted class and unknown true class, 
whose distributions are $\sigma$ and $y$. We show that it has the properties of a generalized CE. 
The proposed collision CE agrees with Shannon's CE for one-hot labels $y$, 
but the training from soft labels differs. For example, unlike Shannon's CE, data points where $y$ is a uniform distribution have zero contribution to the training. Collision CE significantly improves classification 
supervised by soft uncertain targets. 
Unlike Shannon's, collision CE is symmetric for $y$ and $\sigma$, which is particularly relevant when 
both distributions are estimated in the context of self-labeled clustering.
Focusing on discriminative deep clustering where self-labeling and entropy-based losses are dominant, 
we show that the use of collision CE improves the state-of-the-art. 
We also derive an efficient EM algorithm that significantly 
speeds up the pseudo-label estimation with collision CE.

Main paper: 
 introduction and motivation: 
 Shannon's cross-entropy H(y, σ) is the most common loss for training network predictions σ from ground truth labels y in the context of classification, semantic segmentation, etc. However, this loss may not be ideal for applications where the targets y are soft distributions representing various forms of uncertainty. For example, this paper is focused on self-labeled classification [17, 1, 15, 16] where the ground truth is not available and the network training is done jointly with estimating latent pseudo-labels y. In this case soft y can represent the distribution of label uncertainty. Similar uncertainty of class labels is also natural for supervised problems where the ground truth has errors [26, 41] . In any cases of label uncertainty, if soft distribution y is used as a target in H(y, σ), the network is trained to reproduce the uncertainty, see the dashed curves in Fig. 1 .Our work is inspired by generalized entropy measures [33, 18] . Besides mathematical generality, the need for such measures "stems from practical aspects when modelling real world phenomena though entropy optimization algorithms" [30] . Similarly to L p norms, parametric families of generalized entropy measures offer a wide spectrum of options. The Shannon's entropy is just one of them. Other measures could be more "natual" for any given problem.Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute. 9) for fixed soft labels y (red, green, and blue). Assuming binary classification, all possible predictions σ = (x, 1 -x) ∈ ∆2 are represented by points x ∈ [0, 1] on the horizontal axis. For comparison, thin dashed curves show Shannon's cross-entropy H(y, σ) in (8) . Note that H converges to infinity at both endpoints of the interval. In contrast, H2 is bounded for any non-hot y. Such boundedness suggests robustness to target errors represented by soft labels y. Also, collision cross-entropy H2 gradually turns off the training (sets zero-gradients) as soft labels become highly uncertain (solid blue). In contrast, H(y, σ) trains the network to copy this uncertainty, e.g. observe the optimum σ for all dashed curves.A simple experiment in Figure 2 shows that Shannon's cross-entropy produces deficient solutions for soft labels y compared to the proposed collision cross-entropy. The limitation of the standard cross-entropy is that it encourages the distributions σ and y to be equal, see the dashed curves in Fig. 1 . For example, the model predictions σ are trained to copy the uncertainty of the label distribution y, even when y is an uninformative uniform distribution. In contrast, our collision cross-entropy (the solid curves) gradually weakens the training as y gets less certain. This numerical property of our cross-entropy follows from its definition (9) -it maximizes the probability of "collision", which is an event when two random variables sampled from the distributions σ and y are equal. This means that the predicted class value is equal to the latent label. This is significantly different from the σ = y encouraged by the Shannon's cross-entropy. For example, if y is uniform then it does not matter what the model predicts as the probability of collision 1 K would not change.Organization of the paper: After the summary of our contributions below, Section 2 reviews the relevant background on self-labeling models/losses and generalized information measures for entropy, divergence, and cross-entropy. Then, Section 3 introduces our collision cross entropy measure, discusses its properties, related formulations of Rényi cross-entropy, and relation to noisy labels in fully-supervised settings. Section 4 formulates our self-labeling loss by replacing the Shannon's cross entropy term in a representative state-of-the-art formulation using soft pseudo-labels [16] with our collision-cross-entropy. The obtained loss function is convex w.r.t. pseudo-labels y, which makes estimation of y amenable to generic projected gradient descent. However, Section 4 derives a much faster EM algorithm for estimating y. As common for self-labeling, optimization of the total loss w.r.t. network parameters is done via backpropagation. Section 5 presents our experiments, followed by conclusions.We propose the collision cross-entropy as an alternative to the standard Shannon's cross-entropy mainly in the context of self-labeled classification with soft pseudo-labels.The main practical advantage is its robustness to uncertainty in the labels, which could also be useful in other applications. The definition of our cross-entropy has an intuitive probabilistic interpretation that agrees with the numerical and empirical properties. Unlike the Shannon's crossentropy, our formulation is symmetric w.r.t. predictions σ and pseudo-labels y. This is a conceptual advantage since both σ and y are estimated/optimized distributions. Our cross-entropy allows efficient optimization of pseudo-labels by a proposed EM algorithm, that significantly accelerates a generic projected gradient descent. Our experiments show consistent improvement over multiple examples of unsupervised and semi-supervised clustering, and several standard network architectures. 
background review: 
 We study a new generalized cross-entropy measure in the context of deep clustering. The models are trained on unlabeled data, but applications with partially labeled data are also relevant. Self-labeled deep clustering is a popular area of research [5, 31] . More recently, the-state-of-the-art is achieved by discriminative clustering methods based on maximizing the mutual information between the input and the output of the deep model [3] . There is a large group of relevant methods [22, 10, 15, 17, 1, 16] and we review the most important loss functions, all of which use standard information-theoretic measures such as Shannon's entropy. In the second part of this section, we overview the necessary mathematical background on the generalized entropy measures, which are central to our work.The work of Bridle, Heading, and MacKay from 1991 [3] formulated mutual information (MI) loss for unsupervised discriminative training of neural networks using probability-type outputs, e.g. softmax σ : R K → ∆ K mapping K logits l k ∈ R to a point in the probability simplex ∆ K . Such output σ = (σ 1 , . . . , σ K ) is often interpreted as a posterior over K classes, where σ k = exp l k i exp li is a scalar prediction for each class k.The unsupervised loss proposed in [3] trains the model predictions to keep as much information about the input as possible. They derived an estimate of MI as the difference between the average entropy of the output and the entropy of the average outputEQUATIONwhere c is a random variable representing class prediction, X represents the input, and the averaging is done over all input samples {X i } M i=1 , i.e. over M training examples. The derivation in [3] assumes that softmax represents the distribution Pr(c|X). However, since softmax is not a true posterior, the right hand side in (1) can be seen only as an MI loss. In any case, (1) has a clear discriminative interpretation that stands on its own: H(σ) encourages "fair" predictions with a balanced support of all categories across the whole training data set, while H(σ) encourages confident or "decisive" prediction at each data point implying that decision boundaries are away from the training examples [11] . Generally, we call clustering losses for softmax models "information-based" if they use measures from the information theory, e.g. entropy. 9) vs Shannon's cross-entropy (8) . The test uses ResNet-18 architecture on fully-supervised Natural Scene dataset [27] where we corrupted some labels. The horizontal axis shows the percentage η of training images where the correct ground truth labels were replaced by a random label. Both losses trained the model using soft target distributions ŷ = η * u+(1-η) * y representing the mixture of one-hot distribution y for the observed corrupt label and the uniform distribution u, as recommended in [26] . The vertical axis shows the test accuracy. Training with the collision cross-entropy is robust to much higher levels of label uncertainty. As discussed in the last part of Sec.3, in the context of classification supervised by hard noisy labels, collision CE with soft labels can be related to the forward correction methods [28] .Discriminative clustering loss (1) can be applied to deep or shallow models. For clarity, this paper distinguishes parameters w of the representation layers of the network computing features f w (X) ∈ R N for any input X and the linear classifier parameters v of the output layer computing K-logit vector v ⊤ f for any feature f ∈ R N . The overall network model is defined asEQUATIONA special "shallow" case in (2) is a basic linear discriminatorEQUATIONdirectly operating on low-level input features f = X. Optimization of the loss (1) for the shallow model ( 3) is done only over linear classifier parameters v, but the deeper network model ( 2) is optimized over all network parameters [v, w]. Typically, this is done via gradient descent or backpropagation [35, 3] .training is mostly done with standard gradient descent or backpropagation [3, 22, 15] .However, due to the entropy term representing the decisiveness, such loss functions are non-convex and present challenges to the gradient descent. This motivates alternative formulations and optimization approaches. For example, it is common to incorporate into the loss auxiliary variables y representing pseudo-labels for unlabeled data points X and to estimate them jointly with optimization of the network parameters [10, 1, 16] . Typically, such self-labeling approaches to unsupervised network training iterate optimization of the loss over pseudo-labels and network parameters, similarly to the Lloyd's algorithm for K-means [2] . While the network parameters are still optimized via gradient descent, the pseudo-labels can be optimized via more powerful algorithms.For example, self-labeling in [1] uses the following constrained optimization problem with discrete pseudo-labels yEQUATIONwhere ∆ K 0,1 are one-hot distributions, i.e. corners of the probability simplex ∆ K . Training the network predictions σ is driven by the standard cross entropy loss H(y, σ), which is convex assuming fixed (pseudo) labels y. With respect to variables y, the cross entropy is linear. Without the balancing constraint ȳ = u, the optimal y corresponds to the hard arg max(σ). However, the balancing constraint converts this into an integer programming problem that can be solved approximately via optimal transport [9] . The cross-entropy in (4) encourages the predictions σ to approximate one-hot pseudo-labels y, which implies the decisiveness.Self-labeling methods for unsupervised clustering can also use soft pseudo-labels y ∈ ∆ K as target distributions in cross-entropy H(y, σ). In general, soft targets y are common in H(y, σ), e.g. in the context of noisy labels [41, 38] . Softened targets y can also assist network calibration [12, 26] and improve generalization by reducing over-confidence [29] . In the context of unsupervised clustering, cross-entropy H(y, σ) with soft pseudo-labels y approximates the decisiveness since it encouragesσ ≈ y implying H(y, σ) ≈ H(y) ≈ H(σ)where the latter is the first term in (1) . Instead of the hard constraint ȳ = u used in (4), the soft fairness constraint can be represented by KL divergence KL(ȳ ∥ u), as in [10, 16] . In particular, [16] formulates the following self-labeled clustering lossEQUATIONencouraging decisiveness and fairness as discussed. Similarly to (4), the network parameters in loss (5) are trained by the standard cross-entropy term, but optimization over relaxed pseudo-labels y ∈ ∆ K is relatively easy due to convexity. While there is no closed-form solution, the authors offer an efficient approximate solver for y. Iterating steps that estimate pseudo-labels y and optimize the model parameters resembles the Lloyd's algorithm for K-means. The results in [16] also establish a formal relation between the loss (5) and the K-means objective.Below, we review relevant generalized formulations of the information-theoretic concepts: entropy, divergence, and cross-entropy. Rényi [33] introduced the entropy of order α > 0 for any probability distribution pH α (p) := 1 1 -α ln k p α k (α ̸ = 1)derived as the most general measure of uncertainty in p satisfying four intuitively evident postulates.The entropy measures the average information and the order parameter α relates to the power of the corresponding mean statistic [44] . The general formula above includes the Shannon's entropyH(p) = - k p k ln p kas a special case when α → 1. The quadratic or second-order Rényi entropyEQUATION)is also known as a collision entropy since it is a negative log-likelihood of a "collision" or "rolling double" when two i.i.d. samples from distribution p have equal values.Basic characterization postulates in [33] also lead to the general Rényi formulation of the divergence, also known as the relative entropy, of order α > 0D α (p | q) := 1 α -1 ln k p α k q 1-α k (α ̸ = 1)defined for any pair of distributions p and q. This reduces to the standard KL divergence when α → 1D(p, q) = k p k ln p k q k (7)and to the Bhattacharyya distance for α = 1 2 .Optimization of entropy and divergence [24] is fundamental to many machine learning problems [37, 20, 19, 30] , including pattern classification and cluster analysis [36] . However, the entropyrelated terminology is often mixed-up. For example, when discussing the cross-entropy minimization principle (MinxEnt), many of the references cited earlier in this paragraph define cross-entropy using the expression for KL-divergence (7) . Nowadays, it is standard to define the Shannon's cross-entropy asEQUATIONOne simple explanation for the confusion is that KL-divergence D(p, q) and cross-entropy H(p, q)as functions of q only differ by a constant if p is a fixed known target, which is often the case. 
collision cross-entropy: 
 Minimizing divergence enforces proximity between two distributions, which may work as a loss for training model predictions σ with labels y, for example, if y are ground truth one-hot labels. However, if y are pseudo-labels that are estimated jointly with σ, proximity between y and σ is not a good criterion for the loss. For example, highly uncertain model predictions σ in combination with uniformly distributed pseudo-labels y correspond to the optimal zero divergence, but this is not a very useful result for self-labeling. Instead, all existing self-labeling losses for deep clustering minimize Shannon's cross-entropy ( 8) that reduces the divergence and uncertainty at the same timeH(y, σ) ≡ D(y, σ) + H(y).The entropy term corresponds to the "decisiveness" constraint in unsupervised discriminative clustering [3, 17, 1, 15, 16] . In general, it is recommended as a regularizer for unsupervised and semi-supervised network training [11] to encourage decision boundaries away from the data points implicitly increasing the decision margins.We propose a new form of cross-entropyH 2 (p, q) := -ln k p k q k (9)that we call collision cross-entropy since it extends the collision entropy in (6) . Indeed, ( 9) is the negative log-probability of an event that two random variables with (different) distributions p and q are equal. When training softmax σ with pseudo-label distribution y, the collision event is the exact equality of the predicted class and the pseudo-label, where these are interpreted as specific outcomes for random variables with distributions σ and y. Note that the collision event, i.e. the equality of two random variables, has very little to do with the equality of distributions σ = y. The collision may happen when σ ̸ = y, as long as σ • y > 0. Vice versa, this event is not guaranteed even when σ = y. It will happen almost surely only if the two distributions are the same one-hot. However, if the distributions are both uniform, the collision probability is only 1/K.As easy to check, the collision cross-entropy ( 9) can be equivalently represented asH 2 (p, q) ≡ -ln cos(p, q) + H 2 (p) + H 2 (q) 2where cos(p, q) is the cosine of the angle between p and q as vectors in R K and H 2 is the collision entropy (6) . The first term corresponds to a "distance" between the two distributions: it is nonnegative, equals 0 iff p = q, and -ln cos(•) is a convex function of an angle, which can be interpreted as a spherical metric. Thus, analogously to the Shannon's cross-entropy, H 2 is the sum of divergence and entropy.The formula (9) can be found as a definition of quadratic Rényi cross-entropy [30, 32, 46] . However, we could not identify information-theoretic axioms characterizing a generalized cross-entropy. Rényi himself did not discuss the concept of cross-entropy in his seminal work [33] . Also, two different formulations of "natural" and "shifted" Rényi cross-entropy of arbitrary order could be found in [44, 42] . In particular, the shifted version of order 2 agrees with our formulation of collision crossentropy (9) . However, lack of postulates or characterization for the cross-entropy, and the existence of multiple non-equivalent formulations did not give us the confidence to use the name Rényi. Instead, we use "collision" due to its clear intuitive interpretation of the loss (9) . But, the term "cross-entropy" is used only informally.The numerical and empirical properties of the collision cross-entropy ( 9) are sufficiently different from the Shannons cross-entropy (8) . Figure 1 illustrates H 2 (y, σ) as a function of σ for different label distributions y. For confident y it behaves the same way as the standard cross entropy H(y, σ), but softer low-confident labels y naturally have little influence on the training. In contrast, the standard cross entropy encourages prediction σ to be the exact copy of uncertainty in distribution y. Self-labeling methods based on H(y, σ) often "prune out" uncertain pseudo-labels [4] . Collision cross entropy H 2 (y, σ) makes such heuristics redundant. We also demonstrate the "robustness to label uncertainty" on an example where the ground truth labels are corrupted by noise, see Fig. 2 .This artificial fully-supervised test is used only to compare the robustness of ( 9) and ( 8) in complete isolation from other terms in the self-labeled clustering losses, which are the focus of this work.Due to the symmetry of the arguments in ( 9), such robustness of H 2 (y, σ) also works the other way around. Indeed, self-labeling losses are often used for both training σ and estimating y: the loss is iteratively optimized over predictions σ (i.e. model parameters responsible for it) and over pseudolabel distribution y. Thus, it helps if y also demonstrates "robustness to prediction uncertainty".Soft labels vs noisy labels: Our collision CE for soft labels, represented by distributions y, can be related to loss functions used for supervised classification with noisy labels [40, 28, 38] , which assume some observed hard target labels l that may not be true due to corruption or "noise". Instead of our probability of collisionPr(C = T ) = k Pr(C = k, T = k) = k σ k y k ≡ y ⊤ σbetween the predicted class C and unknown true class T , whose distributions are prediction σ and soft target y, they maximize the probability that a random variable L representing a corrupted target equals the observed value lPr(L = l) = k Pr(L = l|T = k) Pr(T = k) ≈ k Pr(L = l|T = k) σ k ≡ Q l σwhere the approximation uses the model predictions σ k instead of true class probabilities Pr(T = k), which is a significant assumption. Vector Q l is the l-th row of the transition matrix Q, such thatQ lk = Pr(L = l|T = k), that has to be obtained in addition to hard noisy labels l.Our approach maximizing the collision probability based on soft labels y is a generalization of the methods for hard noisy labels. Their transitional matrix Q can be interpreted as an operator for converting any hard label l into a soft label y = Q ⊤ 1 l = Q l . Then, the two methods are numerically equivalent, though our statistical motivation is significantly different. Moreover, our approach is more general since it applies to a wider set of problems where the class target T can be directly specified by a distribution, a soft label y, representing the target uncertainty. For example, in fully supervised classification or segmentation the human annotator can directly indicate uncertainty (odds) for classes present in the image or at a specific pixel. In fact, class ambiguity is common in many data sets, though for efficiency, the annotators are typically forced to provide one hard label. Moreover, in the context of self-supervised clustering, it is natural to estimate pseudo-labels as soft distributions y.Such methods directly benefit from our collision CE, as this paper shows. 
our self-labeling loss and em: 
 Based on prior work (5), we replace the standard cross-entropy with our collision cross-entropy to formulate our self-labeling loss as follows:EQUATIONTo optimize such loss, we iterate between two alternating steps for σ and y. For σ, we use the standard stochastic gradient descent algorithms [34] . For y, we use the projected gradient descent (PGD) [7] .However, the speed of PGD is slow as shown in Table 1 especially when there are more classes. This motivates us to find more efficient algorithms for optimizing y. To derive such an algorithm, we made a minor change to (10) by switching the order of variables in the divergence term:EQUATIONSuch change allows us to use the Jensen's inequality on the divergence term to derive an efficient EM algorithm while the quality of the self-labeled classification results is almost the same as shown in the Appendix D.EM algorithm for optimizing y We derive the EM algorithm introducing latent variables, K distributions S k ∈ ∆ M representing normalized support for each cluster over M data points. We refer to each vector S k as a normalized cluster k. Note the difference with distributions represented by pseudo-labels y ∈ ∆ K showing support for each class at a given data point. Since we explicitly use individual data points below, we will start to carefully index them by i ∈ {1, . . . , M }. Thus, we will use y i ∈ ∆ K and σ i ∈ ∆ K . Individual components of distribution S k ∈ ∆ M corresponding to data point i will be denoted by scalar S k i .First, we expand (11) introducing the latent variablesEQUATIONEQUATIONDue to the convexity of negative log, we apply the Jensen's inequality to derive an upper bound, i.e.(13), to L CCE+ . Such bound becomes tight when:EQUATION)Next, we derive the M step.Introducing the hidden variable S breaks the fairness term into the sum of independent terms for pseudo-labels focus on the loss with respect to y. The collision cross-entropy (CCE) also breaks into the sum of independent parts for each y i . For simplicity, we will drop all indices i in variables y k i , S k i , σ k i . Then, the combination of CCE loss with the corresponding part of the fairness constraint can be written for eachy i ∈ ∆ K at eachEQUATIONFirst, observe that this loss must achieve its global optimum in the interior of the simplex if S k > 0 and u k > 0 for all k. Indeed, the second term enforces the "log-barier" at the boundary of the simplex. Thus, we do not need to worry about KKT conditions in this case. Note that S k might be zero, in which case we need to consider the full KKT conditions. However, the Property 1 that will be mentioned later eliminates such concern if we use positive initialization. For completeness, we also give the detailed derivation for such case and it can be found in the Appendix B.Adding the Lagrange multiplier γ for the simplex constraint, we get an unconstrained loss-ln k σ k y k -λ k u k S k ln y k + γ k y k -1that must have a stationary point inside the simplex. The following theorem indicates the way to solve the problem above. All the missing proofs can be found in Appendix A.The sum k y k as in ( 16) is positive, continuous, convex, and monotonically decreasing function of x on the specified interval. Moreover, there exists a unique solution {y k } ∈ ∆ k and x such thatEQUATIONThe monotonicity and convexity of k y k with respect to x suggest that the problem (16) formulated in Theorem 1 allows efficient algorithms for finding the corresponding unique solution. For example, one can use the iterative Newton's updates to search for x in the specified interval. The following Lemma gives us a proper starting point Lemma 1. Assuming u k S k is positive for each k, then the reachable left end point in Theorem 1 can be written asl := max k σ k 1 + λu ⊤ S -λu k S k .for Newton's method. The algorithm for M-step solution is summarized in Algorithm 1 in Appendix C. Note that we present the algorithm for only one data point, and we can easily and efficiently scale up for more data in a batch by using the Numba compiler. In the following, we give the property about the positivity of the solution. This property implies that if our EM algorithm has only (strictly)positive variables S k or y k at initialization, these variables will remain positive during all iterations.Property 1. For any category k such that u k > 0, the set of strictly positive variables y k or S k can only grow during iterations of our EM algorithm for the loss (15) based on the collision cross-entropy.Note that Property 1 does not rule out the possibility that y k may become arbitrarily close to zero during EM iterations. Empirically, we did not observe any numerical issues. The complete algorithm is given in Appendix C. Inspired by [39, 15] , we also update our y in each batch. Intuitively, updating y on the fly can prevent the network from being easily trapped in some local minima created by the incorrect pseudo-labels. 
experiments: 
 We apply our new loss to self-labeled classification problems in both shallow and deep settings, as well as semi-supervised modes. All the results are reproduced using either public codes or our own implementation under the same experimental settings for fair comparison. Our approach consistently achieves either the best or highly competitive results across all the datasets and is therefore more robust. All the missing details in the experiments can be found in Appendix E.Dataset We use four standard datasets: MNIST [25] , CIFAR10/100 [43] and STL10 [8] . The training and test data are the same unless otherwise specified.Evaluation As for the evaluation of self-labeled classification, we set the number of clusters to the number of ground-truth categories. To calculate the accuracy, we use the standard Hungarian algorithm [23] to find the best one-to-one mapping between clusters and labels. We don't need this matching step if we use other metrics, i.e. NMI, ARI. In this section, we test our loss as a proper clustering loss and compare it to the widely used Kmeans (generative) and other closely related losses (entropy-based and discriminative). We use the pretrained (ImageNet) Resnet-50 [14] to extract the features. For Kmeans, the model is parameterized by K cluster centers. Comparably, we use a one-layer linear classifier followed by softmax for all other losses including ours. Kmeans results were obtained using scikit-learn package in Python. To optimize the model parameters for other losses, we use stochastic gradient descent. Here we report the average accuracy and standard deviation over 6 randomly initialized trials in Table 2 . [17, 1, 15] and use our improved implementation of [16] (also for other tables).In this section, we train a deep network to jointly learn the features and cluster the data.We test our method on both a small architecture (VGG4) and a large one (ResNet-18). The only extra standard technique we add here is self-augmentation following [15, 1, 6] .To train the VGG4, we use random initialization for network parameters. From Table 3, it can be seen that our approach consistently achieves the most competitive re- In Table 4 , we show the results using the pretext-trained network from SCAN [45] as initialization for our clustering loss as well as IMSAT and MIADM. We use only the clustering loss together with the self-augmentation (one augmentation per image). As shown in the table below, our method reaches a higher number with more robustness almost for every metric on all datasets compared to the SOTA method SCAN. More importantly, we consistently improve over the most related method, MIADM, by a large margin, which clearly demonstrates the effectiveness of our proposed loss together with the optimization algorithm.sultsAlthough our paper is focused on self-labeled classification, we find it also interesting and natural to test our loss under semi-supervised settings where partial data is provided with ground-truth labels.We use the standard cross-entropy loss for labeled data and directly add it to the self-labeled loss to train the network initialized by the pretext-trained network following [45] . We propose a new collision cross-entropy loss.Such loss is naturally interpreted as measuring the probability of the equality between two random variables represented by the two distributions σ and y, which perfectly fits the goal of self-labeled classification. It is symmetric w.r.t.the two distributions instead of treating one as the target, like the standard cross-entropy.While the latter makes the network copy the uncertainty in estimated pseudo-labels, our cross-entropy naturally weakens the training on data points where pseudo labels are more uncertain. This makes our cross-entropy robust to labeling errors. In fact, the robustness works both for prediction and for pseudo-labels due to the symmetry. We also developed an efficient EM algorithm for optimizing the pseudo-labels. Such EM algorithm takes much less time compared to the standard projected gradient descent. Experimental results show that our method consistently produces top or near-top results on all tested clustering and semi-supervised benchmarks.The sum k y k as in ( 17) is positive, continuous, convex, and monotonically decreasing function of x on the specified interval. Moreover, there exists a unique solution {y k } ∈ ∆ k and x such thatk y k ≡ k λu k S k λu ⊤ S+1- σ k x = 1 and x ∈ σ max 1+λu ⊤ S , σ max (17)Proof. All y k in ( 17) are positive, continuous, convex, and monotonically decreasing functions of x on the specified interval. Thus, y k behaves similarly. Assuming that max is the index of prediction σ max , we have y max → +∞ when approaching the interval's left endpoint x → σmax 1+λu ⊤ S . Thus, y k > 1:= max k σ k 1 + λu ⊤ S -λu k S k .Proof. Firstly, we prove that l is (strictly) inside the interior of the interval in Theorem 1. For the left end point, we havel := max k σ k 1 + λu ⊤ S -λu k S k ≥ σ max 1 + λu ⊤ S -λu max S max > σ max 1 + λu ⊤ S u max S max is positiveFor the right end point, we havel := max k σ k 1 + λu ⊤ S -λu k S k < max k σ k 1 + λu ⊤ S -λu k S k > 1 = σ maxTherefore, l is a reachable point. Moreover, any σmax 1+λu ⊤ S < x < l will still induce positive y k for any k and we will also use this to prove that x should not be smaller than l. Letc := arg max k σ k 1 + λu ⊤ S -λu k S kthen we can substitute l into the x of y c . It can be easily verified that y c = 1 at such l. Since y c is monotonically decreasing in terms of x, any x smaller than l will cause y c to be greater than 1. At the same time, other y k is still positive as mentioned just above, so the k y k will be greater than 1.Thus, l is a reachable left end point.Property 2. For any category k such that u k > 0, the set of strictly positive variables y k or S k can only grow during iterations of our EM algorithm for the loss (d) based on the collision cross-entropy.Proof. As obvious from the E-step (14) , it is sufficient to prove this for variables y k . If y k = 0, then the E-step (14) gives S k = 0. According to the M-step for the case of collision cross-entropy, variable y k may become (strictly) positive at the next iteration if σ k = σ max . Once y k becomes positive, the following E-step ( 14) produces S k > 0. Then, the fairness term effectively enforces the log-barrier from the corresponding simplex boundary making M-step solution y k = 0 prohibitively expensive. Thus, y k will remain strictly positive at all later iterations.-ln k σ k y k -λ k u k S k ln y k . (d)The main case when u k S k > 0 for all k is presented in the main paper. Here we derive the case when there exist some k such that u k S k = 0. Assume a non-empty subset of categories/classesK o := {k | u k S k = 0} ̸ = ∅and its non-empty complementKo := {k | u k S k > 0} ̸ = ∅.In this case the second term (fairness) in our loss (d) does not depend on variables y k for k ∈ K o . Also, note that the first term ( collision cross-entropy) in (d) depends on these variables only via their linear combination k∈Ko σ k y k . It is easy to see that for any given confidences y k for k ∈ Ko it is optimal to put all the remaining confidence 1 -k∈ Ko y k into one class c ∈ K o corresponding to the larges prediction among the classes inK o c := arg max k∈Ko σ k so that y c = 1 - k∈ Ko y k and y k = 0, ∀k ∈ K o \ c.Then, our loss function (d) can be written as-ln k∈ Ko∪{c} σ k y k -λ k∈ Ko u k S k ln y k (e)that gives the Lagrangian function incorporating the probability simplex constraint-ln k∈ Ko ∪{c} σ k y k -λ k∈ Ko u k S k ln y k + γ k∈ Ko ∪{c} y k -1 .The stationary point for this Lagrangian function should satisfy equationsEQUATIONy k + γ = 0, ∀k ∈ Ko and -σ c σ ⊤ y + γ = 0which could be easily written as a linear system w.r.t variables y k for k ∈ Ko ∪ {c}.We derive a closed-form solution for the stationary point as follows. Substituting γ from the right equation into the left equation, we getEQUATIONSumming over k ∈ Ko we further obtainσ c (1-y c )-k∈ Ko σ k y k σ ⊤ y = λu ⊤ S ⇒ σ c -σ ⊤ y σ ⊤ y = λu ⊤ S giving a closed-form solution for σ ⊤ y σ ⊤ y = σ c 1 + λu ⊤ S .Substituting this back into (f) we get closed-form solutions for y ky k = λu k S k (1 + λu ⊤ S)(1 -σ k σc ) , ∀k ∈ Ko .Note that positivity and boundedness of y k requires σ c > σ k for all k ∈ Ko . In particular, this means σ c = σ max , but it also requires that all σ k for k ∈ Ko are strictly smaller than σ max . We can also write the corresponding closed-form solution for y cy c = 1 - k∈ Ko y k = 1 - σ c 1 + λu ⊤ S k∈ Ko λu k S k σ c -σ k .Note that this solution should be positive y c > 0 as well.In case any of the mentioned constraints (σ c > σ k , ∀k ∈ Ko and y c > 0) is not satisfied, the complimentary slackness (KKT) can be used to formally prove that the optimal solution is y c = 0.That is, y k = 0 for all k ∈ K o . This reduces the optimization problem to the earlier case focusing on resolving y k for k ∈ Ko . This case is guaranteed to find a unique solution in the interior of the simplex ∆ Ko . Indeed, since inequality u k S k > 0 holds for all k ∈ Ko , the strong fairness enforces a log-barrier for all the boundaries of this simplex.Algorithm 1: Newton's method for M-stepInput : {σ k }, {S k }, λ, ϵ Output : {y k } Initialize x ← max k σ k 1+λu ⊤ S-λu k S k calculate f (x) ← k λu k S k λu ⊤ S+1- σ k x -1 while f (x) ≥ ϵ do calculate f ′ (x) ← k -λu k S k σ k (λu ⊤ Sx+x-σ k ) 2 x ← x -f (x) f ′ (x) calculate f (x) ← k λu k S k λu ⊤ S+1- σ k x -1 end y k ← λu k S k λu ⊤ S+1- σ k xAlgorithm 2: Optimization for (11) Input :network parameters and dataset Output :network parameters for each epoch do for each iteration do Initialize y by the network output at current stage as a warm start; while not convergent doE step: S k i = y k i j y k j ;M step: find y k i using Newton's method; end Update network using loss H 2 (y, σ) via stochastic gradient descent end end D Self-supervision Loss Comparison Table 7 : With simultaneous feature training from the scratch. The network architecture is VGG-4.EQUATIONEQUATIONTable 8 : Network architecture summary. s: stride; p: padding; K: number of clusters. The first column is used on MNIST [25] ; the second one is used on CIFAR10/100 [43] ; the third one is used on STL10 [8] . Batch normalization is also applied after each Conv layer. ReLu is adopted for non-linear activation function.Here we present the missing details of experimental settings for Table 2 -5. As for Table 2 , the weight of the linear classifier is initialized by using Kaiming initialization [13] and the bias is all set to zero at the beginning. We use the l 2 -norm weight decay and set the coefficient of this term to 0.001, 0.02, 0.009, and 0.02 for MNIST, CIFAR10, CIFAR100 and STL10 respectively. The optimizer is stochastic gradient descent with a learning rate set to 0.1. The batch size is set to 250. The number of epochs is 10. We set λ in our loss to 100 and separately tuned the hyperparameters for other methods.For Table 3 , we use Adam [21] with learning rate 1e -4 for optimizing the network parameters. We set batch size to 250 for CIFAR10, CIFAR100 and MNIST and we use 160 for STL10. We report the mean accuracy and Std from 6 runs with random initializations. We use 50 epochs for each run and all methods reach convergence within 50 epochs. The weight decay coefficient is set to 0.01.As for the training of ResNet-18 in Table 4 , we still use the Adam optimizer, and the learning rate is set to 5e -2 for the linear classifier and 1e -5 for the backbone. The weight decay coefficient is set to 1e -4 . The batch size is 200 and the number of total epochs is 50. The λ is still set to 100. We only use one augmentation per image, and the coefficient for the augmentation term is set to 0.5, 0.2, and 0.4 respectively for STL10, CIFAR10, and CIFAR100 (20) .As for the semi-supervised settings, we made two changes compared to the above. First, we added the cross-entropy loss on the labeled images and set the weight to 2, and separately tuned the hyperparameters for other methods. Second, the pseudo-labels on the labeled images are constrained to be the ground truth during the optimization.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.• If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.• Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.• While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [No] Justification: Code is released upon acceptance.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: See appendix.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: Mean and standard deviation are provided for most of the experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [No] Justification: The datasets are not large. We used single P100 GPU card.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes]Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA]Justification:Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: We cite them and put the links as well.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.• The paper should discuss whether and how consent was obtained from people whose asset is used.• At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.• According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. Justification:Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.• For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.https://github.com/wvangansbeke/Unsupervised-Classification 
 
 Appendix:  


Decision: The manuscript proposes collision cross-entropy, a generalization of cross-entropy, for tasks with soft labels, such as self-labeled clustering.

The reviewers acknowledged that the introduction of collision cross-entropy is novel, well-motivated, and well-presented, they had reservations preventing a recommendation of acceptance. Most notably, the experimental setup is not sufficiently convincing, since the methods for comparison are not SOTA, and that fair comparisons are difficult due to differences in pre-processing (which is, admittedly, a common problem). I further concur with Reviewer VSk7 in the position that an ablation study is important that tries to disentangle the effects of the EM-type algorithm and the new cost function. Reviewer Puk1 in addition suggested to analyze a larger class of entropy measures -- while this is certainly a promising idea, I agree with the authors that this would be out of scope of the present manuscript.

Reviews: review: paper_summary: paper_summary: This paper studies the loss function for soft class labels and entropy-based clustering. In particular, it introduces a new loss function called 'collision cross-entropy' as an alternative to Shannon's cross-entropy when class labels are represented by soft categorical distributions. The motivation for this new loss function is to handle ambiguous targets/labels in classification. The authors provide an EM algorithm for pseudo-label estimation and conduct experiments to demonstrate that this approach leads to improvements in classification accuracy when models are trained with soft, uncertain targets.
strength_weakness: strength_weakness: - [**Theory-1**] The main contribution of this paper is proposing the new loss function 'collision cross-entropy'. However, there is not much theoretical analysis about this loss function. From the current paper presentation, the Eqn. (9) can be interpreted as a modified version (or inspired by) Eqn. (6). For example, by minimizing the new objective for learning linear models, could this new loss lead to the right linear classification model?

- [**Theory-2**] For the EM algorithm, is there any convergence analysis for the EM algorithm proposed in this paper? 

- [**Experiments**] State-of-the-art for comparison. The methods for comparison in Table 1/2/3 are not very recent. It is possible that the previous methods still work well and be the state-of-the-art. However, I found some recent papers could achieve much better results, for example, the ACC on CIFAR10 of [DTC+2023] is 92%+, however the result in this paper is <84%.


[DTC+2023] Unsupervised Manifold Linearizing and Clustering. Tianjiao Ding, Shengbang Tong, Kwan Ho Ryan Chan, Xili Dai, Yi Ma, Benjamin D. Haeffele. ICCV 2023.
questions: questions: - What's the definition of $u$ in Eqn. (4) (5) (10)? The presentation of this paper could be further improved, especially the part related to loss functions.

- The font size of Eqn. (16) is a bit odd.

- What's the first letter 'y' in Line 3? If it is $y$, then make it consistent with the label $y$ in Line 6.
limitations: limitations: See Weaknesses.
paper_summary: paper_summary: The paper focuses on the choice of the loss function in problems with soft distributions of the labels, in particular in the context of pseudo-labeling for unsupervised or self-supervised problems such as clustering. In sections 1-2 the paper gives a thorough review of existing practices and relevant theoretical research. In section 3 the paper proposes a new collision cross-entropy loss as a replacement of the standard Shannon loss, and discusses various aspects of this new loss. In section 4 the paper proposes a new EM algorithm for pseudo-label estimation in connection with the new loss. Finally, in Section 5 the new algorithm is experimentally compared with existing ones and is shown to outperform them.
strength_weakness: strength_weakness: I'm confused by mixing the discussion of losses and EM algorithms in section 4. The bulk of the paper is focused exclusively on the advantages of the proposed new collision cross-entropy loss. The main claim in the abstract and introduction is that the proposed loss is better than the standard Shannon loss. The EM algorithm is mentioned only in the last line of abstract, as if in passing. However, the experimental comparison in section 5 obviously crucially depends on the EM algorithm proposed in section 4. How can we tell if the experimentally demonstrated advantage is due to the new loss or the EM algorithm? Since the main claim is about the superiority of the loss, why not just take any existing soft-labeled clustering algorithms and replace the standard Shannon loss by the proposed new loss? In my opinion, the lack of such a direct comparison substantially weakens the main claim of the paper. The advantage shown experimentally is good, but the conceptual takeaway may be misleading.

I found section 4 on the EM algorithm harder to read relative to the other sections (in fact, I'm not familiar with such algorithms and not even sure what EM stands for - apparently Expectation-Maximization, but this acronym is not explained in the paper). In constrast to the other sections, this one seems to assume familiarity of the reader with related algorithms. I didn't understand, for example, how equation (14) (E-step) was derived.

Another weakness I see is that the strongest results of the paper are largely experimental (not counting general arguments and auxiliary theoretical constructions in Section 4), but, as far as I understand, they are not easily verifiable since the code is not open-sourced.
questions: questions: N/A
limitations: limitations: N/A
paper_summary: paper_summary: The paper introduces the concept of collision cross-entropy (CCE) as an alternative to Shannon's cross-entropy (SCE) for self-labeling in the context of unsupervised and semi-supervised learning. The primary motivation is to address the limitations of SCE, especially its sensitivity to label noise and uncertainty. CCE aims to enhance robustness to such uncertainties by defining a probabilistic interpretation that encourages collision events between predicted and true distributions. The paper provides theoretical foundations, describes an EM algorithm for efficient optimization, and presents experimental results demonstrating the superior performance of CCE over SCE on the task of deep clustering.
strength_weakness: strength_weakness: Quality
- The superiority of CCE seems to hinge on making the model capture the same "decisions" as the target distribution, without forcing the model to capture the entirety of the distribution, as well as de-weighting target distributions which are not spiky. While the properties of the loss are clear, it is not self-evident to me that the properties *of the loss function* translate into necessarily *better properties for models*, both as a function for training a classification model directly or for clustering. 
- In addition, the experiments were conducted on fairly old architectures (VGG, ResNet) and small datasets. Often improvements on small datasets do not translate into improvements on larger-scale models. I would encourage the authors to examine for full imagenet dataset at the very least. This also open up the capability to look at various robustness / calibration properties of the models on the various corrupted forms of ImageNet. 

Clarity
- Certain sections, the task to which this method is applied and the desired model properties for the task could be more clearly explained. It took me a while to get my head around the deep clustering task which the authors are solving. 

Significance
- The impact of CCE on real-world applications beyond the presented datasets and tasks could be further elaborated. This notion that CCE is better for noisy pseudo labels immediately suggests to me examining it as a loss function for doing distillation / noisy teacher-student training of a model on a pseudo-labelled corpus of data, however, I didn't see any links to the area of distillation / teacher-student training within this paper.
- The significance would be bolstered by demonstrating CCE's performance on larger scale, more diverse and challenging datasets.
questions: questions: - **Impact of Soft Label Quality:** How does the quality of the soft labels (e.g., the degree of uncertainty) affect the performance of the collision cross-entropy compared to the standard cross-entropy? Are there scenarios where the standard cross-entropy might be preferable? How strongly does this problem scale with the number of classes? 
- **Numerical Stability:** Are there any numerical stability issues in optimizing CCE? I can imaging the taking the log of the sum of a product of small numbers can cause problems.
- **Applicability to Other Tasks:** The paper focuses on self-labeled clustering. Can the collision cross-entropy be applied to other tasks involving soft labels, such as semi-supervised learning, distillation and teacher-student training? What modifications or adaptations might be necessary? How would this work on sequence-based pseudo-labels, such as are encountered in ASR, machine translation and language modeling. It seems to me that CCE could be tried as a drop-in-replacement loss function.
limitations: limitations: **Strengths:**
- The paper acknowledges the need for robustness to label noise and addresses this effectively through CCE.
- The paper briefly mentions the potential increase in privacy disclosure risk with larger synthetic datasets but does not elaborate on this limitation or discuss potential mitigation strategies. It would be beneficial to include a more detailed discussion of the privacy implications of the proposed method and any potential negative societal impacts.

**Weaknesses:**
- The discussion on limitations could be more explicit, particularly regarding any assumptions made and potential edge cases where CCE may not perform optimally.
- The experimental evaluation uses very old model architectures (VGG, ResNet) and small datasets (CIFAR-10, CIFAR-100, MNIST, STL-10) which feature images only as large as 96x96 pixels. I would be curious whether the advantages of this method translate to high-dimensional image data with more classes, and on more modern, transformer-based  architectures (eg: ViT) .
- Similarly, could the author's consider extending this approach to deal with pseudo-labelled sequence data, for language models or for translation models, for example?
paper_summary: paper_summary: Soft labels are often used to represent ambiguous/noisy/uncertain targets in classification, particularly in self-labelled clustering, where pseudo-labels are estimated together with model parameters.
The authors propose an alternative to Shannon cross-entropy for a loss term, called the collision probability. 
This term arises as a limiting case of a Renyi entropy, or as a probability that two random variables are equal.
The collision cross entropy admits several advantageous properties: it is robust to large deviations in the target data, it agrees with Shannon cross-entropy for one-hot labels, it is symmetric, and points that are labelled as uniform distribution have no contribution to training.
The authors provide an EM algorithm for pseudo-label estimation and show state of the art results.
strength_weakness: strength_weakness: - My main concern is that **conceptually, the contributions are rather limited**. Generalisations of entropy are well-known, and as far as I understand (correct me if I am wrong), the main contribution is that authors use a different measure of entropy to Shannon entropy inside existing formulations. This leads the authors to investigate EM-algorithm and empirical performances, but as the paper is currently written (see further comments below), I cannot see whether these EM-algorithm and empirical performance benefits are actually real and beneficial. I also do not understand why this particular notion of entropy was used, compared with the other spectra of entropies. 
- An incomplete review of relevant generalized formulations of entropy is provided. This is not a weakness per se, however **perhaps the title in section 2.2 could be changed to something like Renyi Entropy**. Similarly tone down the discussion of generalised entropy measures throughout the paper. Alternatively, the authors might consider expanding their discussion and including more well-known entropy measures. For example, see section 8 and 11 of [1].
- The bold numbers in table 2 require clarification. The caption doesn't mention the number of trials (however the text mentions 6 trials). Compared with MIGD, excluding MNIST, due to the high variance in the trials, the results do not appear to be **statistically significant**. Perhaps the authors could consider running more trials and performing a significance test, and/or also bold relevant entries in MIGD. 
- As above for Table 3, 4 and 5. 
- It is **not clear how long the method takes to run** compared with competitors. Does the EM algorithm outperform a naive marginalisation of the log likelihood (using e.g. MC), both in terms of time and in terms of predictive performance? 
- Related to the above, is the reason for specialising on $\alpha \to 1$ because it allows for the EM algorithm? If you consider other values of $\alpha$, how do the results compare in terms of time and performance. Or is this setting intractable?


[1] Generalized Thermostatistics, Jan Naudts, 2011.


Minor:
- The text in the tables is too small to read without zooming in a lot.
- Recommend less active tense in the abstract: "In case of soft labels y, Shannon’s CE teaches the model predictions σ to reproduce the uncertainty in each training example" could be "In case of soft labels y, Shannon’s CE results in model predictions σ which reproduce the uncertainty in each training example".
questions: questions: Please see weaknesses above.
limitations: limitations: The author checklist appears to be incomplete. The authors answer NA to "Does the paper discuss the limitations of the work performed by the authors?", without a justification. I do see a small discussion around local minima and numerical instability towards the end of section 4, but I think these could be further elaborated on.

Comments: title: on newer methods
Response
Response
Response to the second and the third bullets
Response to the first bullet
comment: Below we copy our response to pteP on a similar issue of comparison to more recent results. 

>SOTA experiments in [DTC+2023] paper

The main contribution of our paper is a new (for network training) version of cross entropy (CCE) as an alternative to standard Shannon's cross-entropy. Our validation of CCE wrt standard entropy was focused on comparison with other methods using entropies (including SCAN and others in our Table 4). These and other results (including our Fig 2) empirically validate the advantages of the proposed CCE. Do you see any specific reasons to disagree?

Our paper is not focused on SOTA. But, it does not mean that we do not care. We thank the reviewer for pointing out some references, e.g. [DTC], that we can happily reference, discuss, and point out their better numbers. Please note that achieving SOTA in clustering requires many tricks. For example, there are three versions of SCAN (see their original paper) and the results get better and better as more tricks are added. Their pure clustering part using entropy losses achieves only 81.8 ACC on CIFAR10, but with other tricks it goes up to 87.4. The result in DTC paper (MLC) achieves 92.2 ACC using MoCo pertaining (thanks for clarifying this). Strangely, they do not show their MLC result for SimCLR pretraining in the first block in their Table 4. This result would have been the most relevant to compare with our number (83.3) since we use SimCLR pretraining. Also, note that SCAN-SimCLR number 87.6 reported in DTC paper is higher than the number we compare with for SCAN in our paper (81.8). We selected the SCAN result without any extra tricks for a fair comparison.

In short, we do not believe that it is easy to make any solid conclusions about SOTA based on Table 4 in DTC paper, but we will gladly add this reference and discuss the challenges in establishing the truth in the state of the art.
> it does not provide theoretical results on justifying why this new loss function

This statement demonstrates the lack of good faith in providing an objective review and we would like to point this out to the Area Chair. This is not acceptable. The statement that we do not have any theories motivating CCE contradicts an obvious observation that most of our paper is a theoretical/numerical/conceptual motivation for CCE discussing limitations of the Shannon's cross-entropy. You did not even acknowledge our earlier replies to Theory-1 and Theory-2 as if they do not exist. Have you missed them?

> SOTA experiments in [DTC+2023] paper

The main contribution of our paper is a new (for network training) version of cross entropy (CCE) as an alternative to standard Shannon's cross-entropy. Our validation of CCE wrt standard entropy was focused on comparison with other methods using entropies (including SCAN and others in our Table 4). These and other results (including our Fig 2) empirically validate the advantages of the proposed CCE. Do you see any specific reasons to disagree?

Our paper is not focused on SOTA. But, it does not mean that we do not care. We thank the reviewer for pointing out some references, e.g.  [DTC], that we can happily reference, discuss, and point out their better numbers. Please note that achieving SOTA in clustering requires many tricks. For example, there are three versions of SCAN (see their original paper) and the results get better and better as more tricks are added. Their pure clustering part using entropy losses achieves only 81.8 ACC on CIFAR10, but with other tricks it goes up to 87.4. The result in DTC paper (MLC) achieves 92.2 ACC using MoCo pertaining (thanks for clarifying this). Strangely, they do not show their MLC result for SimCLR pretraining in the first block in their Table 4. This result would have been the most relevant to compare with our number (83.3) since we use SimCLR pretraining. Also, note that SCAN-SimCLR number 87.6 reported in DTC paper is higher than the number we compare with for SCAN in our paper (81.8). We selected the SCAN result without any extra tricks for a fair comparison.

In short, we do not believe that it is easy to make any solid conclusions about SOTA based on Table 4 in DTC paper, but we will gladly add this reference and discuss the challenges in establishing the truth in the state of the art.
I appreciate the author's response. However, I do feel quick strongly about using old models, especially if  (as pointed out by other reviewers), the models' don't reach the level of performance on established tasks which they reached in prior work.

In light of this, as well as the extensive discussions with other reviewers, I will keep my score as is.
We thank you for all your feedback. We will look more carefully into the provided references and will try to action your feedback.

We have some more thoughts based on some new references and would like to bounce them back (though we might be off since we only had a very quick look). In general, our impression is that your comments mainly concern limitations in our description of related work. We certainly care about related work and will do our best to add references. However, we feel that the provided references are only indirectly related to the main topic of our work - network training with noisy labels in the context of self-labeled "deep clustering". The latest references provided by the reviewer helped us to better see a common theme - the use of entropy/divergence measures for clustering. However, it also became more evident that we might be discussing two significantly different groups of entropy clustering algorithms. Somewhat informally, we can refer to them as discriminative and generative.

**A. [discriminative entropy clustering]** our work is in the group started by MacKay et al [3] at NIPS 1991.
We refer to it as "discriminative" since it explores unsupervised loss functions for discriminative softmax models (networks).
MacKay starts from a Mutual Information criterion and derives entropy-based decisiveness and fairness losses applicable to soft-max models. This is why **our work concerns network training**. This also explains why our work cares about **information-theoretic entropy** (e.g. Renyi entropies) that is directly suitable for evaluating multi-class decisions (categorical distributions).

**B [generative entropy clustering]** This is a much older group related to K-means. Works like AISTATS 2023 (we only had a quick look, so we could be wrong) discuss generalized K-means where entropies/divergences can be used as general measures of cluster compactness (as an alternative to the sum of squared errors corresponding to the entropy under Gaussinity assumption). We call this "generative clustering" since the entropy evaluates the properties of the data (density) in each cluster, rather than the property of the prediction model (posterior) outputs. This also explains why **the references provided by the reviewer seem unrelated to networks** and focus on **entropy from statistical physics** that is directly suitable for evaluating chaos in the data.

While the relation or differences between groups A and B are interesting (we are working on a PAMI submission discussing this in more detail), we do not think that generalized entropies discussed in group [B] are reducing the significance of our work motivating group [A] to use entropies other than Shannon's. 

Does this make sense to the reviewer?

If it does, we can discuss this relation in Sec 2.1 and place your references there.

If it does not, please do not lower your rating. We will think harder about your references :) Or maybe you can give us another hint on how to relate your references to our work.

Thanks again.
I would like to thank the authors for their response. 

> We did not find the details for initialization of resNet in [DTC+2023], ... Do you have an advice?

From Table 3 of [DTC+2023], I think they applied the MoCoV2 as the pre-trained model.

I still find the contribution of this paper is limited: theoretically, it does not provide theoretical results on justifying why this new loss function; empirically, the performance is not better compared to previous work [DTC+2023]. For now I keep my original score.

[CFG+2020] Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. Mar. 2020.
I appreciate your response, and see the value in your work (I raise my score by 1), but think this paper needs more work to give it the attention it deserves. *If* you would like to action my feedback, you will need some more time than the review cycle allows to properly digest this literature, if it was not already known to you beforehand. But of course there would be other ways to improve the paper, if you don't want to consider my feedback.

There are many works in that look beyond Shannon's (cross)-entropy in the context of clustering, and machine learning more generally. I am not suggesting you need to enumerate uncountably many infinite entropies, just discuss them, study some of them, and place your entropy of interest in the broader context of established methods. (note that the classical cross-entropy is related up to a constant to the "forward/backward" $f$-divergence induced by $f(z) = z\log z$ or $f(z)=-\log(z)$, depending on which argument is held constant, and references to $f$-divergences allow for the generalisations I am suggesting).

- Clustering above Exponential Families with Tempered Exponential Measures, AISTATS 2023
- Geometry of q-Exponential Family of Probability Distributions
- Amari's book, 
- or works by Nielsen

The link between physicist's entropy and information theorist's entropy is well-known, and while the reference I provided is in the context of thermodynamics, many works have investigated it in the context of information geometry (see the works that cite it in Google Scholar).
> Your label of “generalised entropy” is inappropriate. …suitably general notion of entropy, as per my hint with the provided reference (to the book on “Generalized Thermostatistics” by  Jan Naudts)

We downloaded the book. As promised by the reviewer, Chapters 8 and 11 discuss general entropies and divergences (relative entropies) in the general context of **Thermodynamics**. We believe that generalization of entropies done by Renyi in the context of **Information Theory** (reviewed in our Sec 2.2) is significantly more directly relevant for our work, as we hope you can agree.  Also, the motivations in these two areas are sufficiently different. Indirectly confirming this, the book has no references to the famous works of Renyi or his followers. The two areas can be related, e.g. Shannon was inspired by entropy ideas in Thermodynamics. But discussing this relation did not even make it into the book; it is an even bigger stretch to expect this from our conference paper. 

In short, we disagree with the suggestion in your original review to expand our discussion of generalized information-theoretic Renyi entropies in Sec 2.2 by generalized entropies in thermodynamics. However, we will happily cite this book in the beginning of Section 2.2 to indicate the existence of other generalizations outside the context of information theory. Moreover, we can also change the title of Section 2.2 to “Generalized Entropy Measures in Information Theory” to explicitly state its limited scope. We hope you will find this simple fix to be acceptable.

> Bold font in the tables…
 
We did not know that bold font numbers in the Tables could be interpreted as a claim of statistical significance. We just followed a practice that we thought was standard “these days”. We do not mind removing the bold font. Alternatively, we can explicitly state that there is no claim of statistical significance and that we just follow a common practice for experimental design and reporting. Perhaps we can ask for the recommendation of the area chair on this matter once the final decision is made about the paper. We hope your decision about the paper is not affected by this font issue.
We thank the reviewer for continuing the engaging discussion, which we hope can clarify things. We are also glad that the reviewer agrees that no prior work does what we claim our main contributions are, that is, the introduction of a new form of cross entropy as a loss function for network training with noisy labels and an efficient algorithm for this loss. It seems that the reviewer doubts the significance of our contributions (the first bullet above). We would like to convince the reviewer about the significance. We also separately respond to the points in bullets two and three, though they seem less consequential.

> Limited contributions... I am unconvinced from the evidence presented in the paper that this single choice (collision cross entropy) is a very interesting choice. Convince me and other readers, by discussing and trying other entropies.

Summarized in our own words, the first bullet says that our cross-entropy choice is only one of an infinite (uncountable) number of different generalized cross-entropies, **all** of which should be studied in our context (network training with noisy labels). In our minds we have no doubts that the introduced collision cross-entropy (CCE) is very interesting, which is why we are eager to share it with the community.  Here is a summary of how we see the potential significance of our work for the community:

A. First of all, the very fact that our work proposes to look beyond Shannon’s entropy in the context of network training (unsupervised or with uncertain/noisy labels) could be important. For example, to the best of our knowledge, all prior work on deep clustering and self-labeling is “stuck” with Shannon’s entropy or cross-entropy.  We explain **numerical** (Fig.1), **empirical** (Fig.2), and **conceptual** limitations of Shannon’s entropy (the difference between equality of distributions and random variables discussed below (9) that we plan to emphasize). We propose CCE as a well-motivated mathematically solid alternative that can address such limitations. **While CCE is only one of the possible alternatives (e.g. mentioned in l.198), our detailed study of this single example is enough to demonstrate the existence (of the whole class) of alternatives to Shannon that can improve network training**. We believe that this is new knowledge for the community and hope that more researchers will be inspired to study other examples of generalized entropies. 

B. We point out a unique property motivating CCE - **maximization of (the log of) probability of equality between (random variables) predicted class and unknown true class**, see below (9). This replaces the property of Shannon CE - the enforcement of equality of the distributions for these random variables. The difference is significant and consequential. The proof is based on very simple algebra (dot product is the sum of probabilities of equal outcomes), but we see no technical reason that it may work for other (more complex) general cross-entropy formulae. This property **makes CCE stand out**. This CCE property also conceptually explains (see below (9)) why CCE resolves numerical and empirical limitations of Shannon’s cross-entropy illustrated in Fig.1 and Fig.2. These are not by chance.

C. In particular, the conceptual new properties of CCE lead to strong empirical improvements over standard Shannon's cross-entropy convincingly demonstrated by the "clean" test in Fig.2. So far the reviewer has not acknowledged this test. We think the **example in Fig.2 is very important for appreciating the significance of the new general ideas and CCE in particular**. Do you have any questions or comments about this example?

D. Our preliminary evaluation of some other general forms of cross-entropy in [30,32,46] could not improve the results for CCE (e.g. those in Fig 2). These results are far from conclusive, which is why they are not in the paper. However, this worked as (anecdotal) evidence for the potential special status of CCE, already supported by the (unique) conceptual property discussed above.  

Finally, we agree with the reviewer that a paper focused on a random special case of a well-known general class of extensions may not be interesting. But, the points above argue that neither the general class of (Renyi) CE is well-known in network training, nor CCE is a random choice. Also, we find unrealistic the reviewer’s expectation that a full exhaustive study of conceptual, algorithmic, and empirical properties of all (uncountable) number of generalized entropies should be done in the scope of one NeurIPS paper. There is enough room for future research and we hope the community will be interested in helping. We are excited that other reviewers already suggested some new applications for the general ideas proposed in our work.
Thanks for responding to my review. 

- Limited contributions. I understand that the authors have introduced a new loss function (collision cross-entropy), and studied the EM algorithm in this context, developed various algorithms, and benchmarked their results. I am not aware of any prior works that do this. However, there are uncountably infinitely many notions of entropy, and I do not think each of them warrant a paper that can be labelled as conceptually novel. What then, does an interesting paper in this space look like? Perhaps one can start with a suitably general notion of entropy (as per my hint with the provided reference), and then study properties of all of these notions of entropy in the context you are looking at. Some properties might be whether or not certain notions are tractable, whether they lead to other probabilistic interpretations (e.g. collision), whether they have been studied before, whether they allow for strong performance, and what are there relative strengths and weaknesses? At the moment, I am seeing a good start to this, by focusing on one entropy, but I am unconvinced from the evidence presented in the paper that this single choice is a very interesting choice. Convince me and other readers, by discussing and trying other entropies.
- Renyi Entropy. My suggestion was that your label of ``generalised entropy'' is inappropriate, given you study only one form of entropy (whether cross-entropy was studied by Renyi or not is a separate matter). Either change the label to something more specific than generalised entropy, or expand your literature to include other forms of generalised entropy.
- Bold tables. It may be common for similar tables to be bold to indicate the best result, however this is bad practice if the results are not meaningfully better. One way to measure meaningfulness is to take multiple runs, and observe significantly more variation between the methods than between the runs. The current presentation does not allow for this. I am fine that your goal was not to break SOTA. Just report the result that you obtained, and if the difference is not meaningful, no need to claim that they are.
- Run time. Thanks very much for pointing me to table 1, which I missed. Excellent comparison, clearly showing your result is faster. I might suggest making the font bigger in a future version of the paper.
I thank the authors for their reply. I'm keeping my score as is.