Revisiting Information-Based Clustering with Pseudo-Posterior Models
Authors: Zhongwen Zhang
Yuri Boykov
Venue: Submitted to ICLR 2023 (2023)

Abstract: Maximization of mutual information (MI) between the network's input and output motivates standard losses for unsupervised discriminative clustering enforcing "decisiveness" and "fairness". In the context of common softmax models, we clarify several general properties of such discriminative losses that were previously not well understood: the relation to K-means, or lack thereof, and "margin-maximization". In particular, we show that "desiciveness" without the extra regularization term can lead to poor classification margins. Also, non-convexity of information-based losses motivates us to focus on self-supervised approaches introducing effective higher-order optimization algorithms with auxiliary variables. Addressing limitations of existing formulations, we propose a new self-supervised loss with soft auxiliary variables, or "pseudo-confidence" estimates. In particular, we introduce "strong" fairness and motivate the "reverse" cross-entropy as a robust loss for network training from noisy pseudo-confidence estimates. The latter is efficiently computed using variational inference - we derive a new EM algorithm with closed-form solutions for E and M steps. Empirically, our algorithm improves the performance of earlier methods for information-based clustering.

Under review as a conference paper at ICLR 2023
REVISITING INFORMATION-BASER CLUSTERING WITH USEUDO-POSTERIOS MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
Maximization of mutual information (MI) between the network's input and out- put motivates standard losses for unsupervised discriminative clustering enfore- ing "decisiveness" and "fairness". In the context of common softmax models, we clarify several general properties of such discriminative losses that were previ- ously not well understood: the relation K-means, lack thereof, and margin- maximization. In particular, we show that "desiciveness" without the extra reg- ularization term can lead to poor classification margins. Also, non-convexity of information-based losses motivates to focus on self-supervised approaches in- troducing effective higher-order optimization algorithms with auxiliary variables. Addressing limitations of existing formulations, we propose a new self-supervised loss with soft auxiliary variables, or pseudo-confidence estimates. In particular, we introduce strong fairness and motivate the reverse cross-entropy as a robust loss for network training from noisy pseudo-confidence estimates. The latter is efficiently computed using variational inference with closed-fore solutions for E and M steps. Empirically. our algorithm im- proves the performance of earlier methods for information-batt based clustering.
derive new EM algorithm
INTRODUCTION
We were inspired by the work of Bridle, Heading, and MacKay from 1991 Bridle et al. (1991) for- mulating mutual information (MI) loss for unsupervised discriminative training of neural networks using probability-type outputs, e.g. softmax R - A mapping K logits 4 E: R to a point in the probability simplex A Such output a = (o1,..., ) is often interpreted as a pseudo exple expT;
posterio over K classes, where oj
is a scalar prediction for each class k.
The unsupervised loss proposed in Bridle et al. (1991) 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 output
Lms = -MI(e, X) & ((a) H(T)
where is random variable representing class prediction, X represents the input, and the averaging is done over all input samples (X.) iee. over M training examples. The derivation in Bridle et al. 1991] assumes that softmax represents the distribution Pr(c]X). However, since softmax is not true posterior, the right hand side in (I) can be seen only as pseudo MI loss. In any case, ( has 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 (o) encourages confident or "decisive" prediction at each data point implying that decision boundaries from the training examples Grandvalet & Bengio (2004). Generally. we call clustering losses for softmax models "information-basel"" if they use measures from the information theory, e.g. entropy.
away
Discriminative clustering loss ( can be applied to deep or shallow models. For clarity, this paper distinguishes parameters w of the representation layers of the network computing features fw (X) RN for any input X and the linear classifier parameters v of the output layer computing K-logit vector for any feature f RV The overall network model defined as
alv (X)).
"Pseudoo" emphasizes that discriminative training does lead the true Bayesian posteriors, in general.

---

Under review as a conference paper at ICLR 2023
(a) K-means
(b) MI clustering ( max margin 7
Figure 1: Generative vs Discriminative clustering binary example (K 2) for data points X E R. (N comparing linear methods of similar parametric complexity: (a) K-means μlg R-V and (b) MI clustering 1 using linear classifier (3) with K-column matrix v producing logits v X. Red and green colors show the optimal partitioning of the data points, as well as the corresponding decision regions over the whole 2D space. The linear decision boundary in (a) is "hard" since K-
means outputs hard clustering arg min; || - pell- The "soft" margin in (b) is due to the softmax in the linear classifier
(3) shown via the transparency channel ε 0% for each region's 's color.
special "shallow" case of the model 2 is a basic linear discriminator
o X)
(3)
directly operating low-level input features f X. Optimization of the loss ①I for the shal- low model (3) is done only over linear classifier parameters v. but the deeper network model (
is optimized over all network parameters [v. w/. Typically, this is done via gradient descent or
backpropagation Rumelhart et al. (1986); Bridle et al. (1991).
Simple 2D example in Figure Tb) motivates "decisiveness" and "fairness" as discriminative prop- erties in the unsupervised clustering loss (T) in the context of a low-level linear classifier (3). MI clustering is compared with the standard K-means result in Figure [ In this "shallow" 2D set- ting both clustering methods are linear and have similar parametric complexities, about K x N parameters. K K-means (a) finds balanced compact clusters of the least squared deviations or vari- ance. This can also be interpreted "generatively", see Kearns et al. (1997). as MLE-based fitting of two (isotropic) Gaussian densities, explaining the failure for non-isotropic clusters in (a). To fix (a) "generatively", one should use non-isotropic Gaussian densities, e.g. 2-mode GMM would produce soft clusters similar to (b). However, this has costly parametric complexity two extra co- variance matrices to estimate and quadratic decision boundaries. In contrast, there is estimation of complex data density models (b). MI loss T trains a simple linear classifier to produce balanced ("fair") decision boundary away from the data points ("decisiveness"). Later, show that the "decisiveness" may be deficient without an extra margin maximization term, see Fig
In the context of deep models 2 unsupervised MI loss finds non-linear partitioning of (unlabeled) training data points {X,} as the network learns their high-dimensional embedding fw(X) In this case, the loss I optimized with respect to both representation and classification parameters.
1.1 RELATED WORK ON DISCRIMINATIVE DEEP CLUSTERING
Unsupervised discriminative clustering via (pseudo) posterior models trained by MI loss Bridle et al.
[1991] has growing impact Krause et al. (2010); Ghasedi Dizaji al. (2017): Hu al. (2017); Ji
ct al. Asano et al. 22000) Jabi et al. (202 due to widespread of neural networks in computer vision where supervision expensive or infeasible.
Clear information- -thooretic and discriminative interpretations of MI clustering criterion moti- vated many extensions. For example, Krause et al. (2010) proposed to reduce the complexity of the model by combining MI loss (1) with regularization of all network parameters interpreted as an isotropic Gaussian prior on these weights
Tmmi+ = H(a) - H(o) + ||[v, w]l?
H(o) + KL(Ø u) + [1[v, w]ll
(4)
2

---

Under review as a conference paper at ICLR 2023
where - represents equality up to additive constant and u is a uniform distribution over K classes. Of course, minimizing the norm of network weights as above corresponds to the weight decay a common default for network training.
The second formulation the loss 4 uses KL divergence motivated in Krause et al. (010)) by the possibility to generalize from "fairness" to balancing with respect to any given target distribution different from the uniform u. This paper keeps u in all balancing KL terms, in part to preserve MI
interpretation of the loss.
Empirically, network training with MI loss (4) can be improved using self-auugeenaation techniques Hu et al. (2017). Such techniques are common in deep clustering. Self-augmentation can also directly utilize MI. For example, Ji et al. (2019) maximize the mutual information between class predictions for input X and its augmentation counterpart X' encouraging high-level features invari- ant to augmentation.
Optimization of MI losses or during network training is mostly done with standard gradient descent or backpropagation Bridle et al. (199];; Krause et al. (2010); Hu et al. (2017). 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 ap- proaches. For example, it 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 Ghasedi Dizaji et al. (2017); Asano et al. (2020); Jabi et al. (202T). Typi- cally, such self-labeling approaches to unsupervised network training iterate optimization of the loss over pseudo-labels and network parameters, similarly to the Lloyd's 's algorithm for K K-means Bishop (2006). While the network parameters are still optimized via gradient descent, the pseudo-labels can be optimized via more powerful algorithms.
For example, Asano al. (2020) formulate self-labeling using the following constrained optimiza- tion problem with discrete pscudo-labels
(y, s.t. y E A and ÿ = v where A5,, are one-hot distributions, i.e. corners of the probability simplex A Training of the net- work predictions a is driven by the standard cross entropy loss Hyy, o). which convex assuming fixed (pseudo) labels y. With respect to variables y, the cross entropy is linear. Without the balanc- ing constraint y = u, the optimal y corresponds to the hard arg max(o)) However, the balancing constraint converts this into integer programming problem that can be approximately solved via optimal transport (Cuturi (2013). The cross cross-entropy in (5) encourages the network predictions a to approximate the estimated one-hot target distributions y, which implies the decisiveness.
Lee
(5)
Self-labeling methods for unsupervised clustering can also use soft pseudo-labels y E A as target distributions in cross-entropy ()) In general, soft targets y are common in H o), e.g. in the context of noisy labels Tanaka et al. (2018); (Snng et al. (2022). Softened targets can also assist network calibration Guo et al. (2017); Müller al. 2019) and improve generalization by reducing over-confidence Pereyra et al. (2017). In the context of unsupervised clustering, cross entropy (gy, o)) with soft pseudo-labels y approximates the decisiveness since encourages implying H Hy, .) s (y) z H ((a) where the latter is the first term in (I) Instead of the hard constraint jj = used (5), similarly to (4) the soft fairness constraint can be represented by KI.
y
divergence KT || u). as in Ghasedi Dizaji et al. b;; Jabi et al. (2021). In particular, Jabi et al.
(202 formulates the following self-supervised clustering loss
(6) encouraging the decisiveness and fairness as discussed. Similarly to (5. the network parameters in loss (6) are trained by the standard cross-ettrpyy term, but optimization over relaxed pseudo-labels y E K is relatively easy due to convexity. While there 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 Jabi et al. (2021) also establish formal relation between the loss (6) and the K K-means objective.
Lee+11
Hly,o) + KL u)
1.2 MOTIVATION AND CONTRIBUTIONS
Our paper analyses several conceptual problems and limitations of the earlier work on information- based clustering with posterior models. Our goal is better understanding of the information-basel
3

---

Under review as a conference paper at ICLR 2023
losses, which leads to their improved formulations and effective optimization algorithms for the non-convex information- based criteria. Similarly to some prior work, we focus on self-supervised approaches including auxiliary latent variables. We motivate novel formulations for the decisiveness and fairness constraints, argue for an explicit margin maximization term, and derive a new efficient EM algorithm for estimating auxiliary variables.
Our work is most closely related to Jabi et al. (2021) who proposed the self-supervised clustering loss (6) and the corresponding ADM algorithm. Their inspiring approach provides good reference point for our proposal for a self-supervision loss (TO). It also helps to illuminate problems with the standard formulations. In general, these problems are due to limited conceptual understanding of the information-basee discriminative clustering losses.
In particular, we disagree with the main theoretical claim in Jabi et al. (2021) establishing formal equivalence between K-means and regularized MI-based clustering. In fact, our Figure 1 works as a simple 2D counterexample to their clain Also, they extend the information-baser loss with the classifier regularization |v| but this extra quadratic term is used mainly as tool in their proof of algebraíc similarity between their loss and the standard K-means lose We present a very different motivation for the regularization term. In contrast to prior work, we demonstrate that ||v/]2 is required in the discriminative information- based losses for explicit margin maximization.
Besides clarifying some useful general properties of the information- based losses for posterior mod- els, we propose new technical ideas improving unsupervised and weakly- supeevs-d training of such models. Below is summary of the main contributions and their motivation:
we propose the forward version of KL. divergence as a strong fairness loss. The "strength" of the corresponding fairness or balancing constraint can be related to the well-known zero-avoiding property of the forward KI. divergence. It is illustrated in Figure 3 Bla.
we propose the reverse cross-entropy H(a, y) as decisiveness constraint in the context of self- supervision. In general, this loss is non-standard for network training, in part because it is not well- defined for very common one-hot targets y. However, we show that there are important advantages in the context of self-labeling with soft auxiliary variables y. First, H (o, y) is a linear function for network predictions a such that, see Figure b)). the network training becomes robust to errors in y. which could be significant in self-labeling. The reversal makes the predictions ignore uncertain y during training. rather than replicate their uncertainty. In fact, the reverse cross-entropy H(, y) makes it difficult to continue calling distributions soft labels or targets. Instead, we will refer to the auxiliary variables y E A as pseudo confiddcee estimates. Note that the reverse cross entropy effectively turns predictions a into the strong targets for y. In combination with the strong fairness, the reverse cross entropy defines a well-constrained loss for estimating y.
we show that regularization of the linear classifier ||v implies nargin-maxiiizztion for the decision boundary that should be added to the decisiveness term to avoid its deficiency, see Figure 2
combination of reverse cross- ross-entropy, strong fairness, and margin-maximizzn new self-supervised loss for clustering (10). It is convex w.r.. y. We derive an efficient expectation- maximization (EM) algorithm for estimating y with closed-form solutions in E and M steps.
terms define
our empirical results show an improved performance w.r.t. the earlier information based methods.
The rest of our paper is organized follows. Section 2 motivates
iiormationn-bsed self- supervised clustering loss and derives our EM algorithm. Section compares our approach with ex- isting information-base discriminative clustering losses for unsupervised or self-supervised training of pseudo-posterior (softmax) models. Conclusions are provided in Section 4
"The proof of Proposition 2 has a critical technical error - it ignores normalization for soft-max prediction in their equation (5), which is hidden via x symbol. Such normalization is critical for pseudo-posterior models. "Since they ignore normalization the softmax prediction. then In o in the cross-entropy H (y. a) turns into linear term w.r.t. logits v x. Adding regularization ||v to such loss allows them to create quadratic form with respect that resembles squared errors loss in K-means, which is quadratic w.n. means pt)).
4

---

Under review as a conference paper at ICLR 2023
(a) 0
(b) y = 0.001
(c) 7 = 0.01
2 in our loss low-level clustering results for the soft- max linear classifier model (3) with N and different weights y. The dots represent data points. The optimal softmax clustering of the data and the decision regions over the whole space are visu- alized by a-weighted color transparency, as in [b.. The "margin" is weak-confidence "soft" region around the linear decision boundary lacking color-saturatie For small y the classifier can "squeeze" a Marrow-marghn linear decision boundary just between the data points, while maintaining arbitrarily hard "decisiveness" on the data points themselves.
Figure 2: Margin maximization term ||v|
2 OUR APPROACH TO INFORMATION-BASST CLUSTERING
We are focused on information-based losses for clustering with softmax models that typically en- force "decisiveness" and "fairness". First, Section 2.T we argue that common formulations of such losses, e.g. (I or (5) may produce poor classification margins. We show that some explicit margin maximization constraints should be added and motivate regularization the classifier norm ||v|2 for the job, similarly to SVM methods Xu et al. (2004). Section 2.2 introduces information- based loss for clustering. First, we motivate strong fairness constraint. Following well-known optimization methodologies [Boyd & Vandenberghe (2004), we use splitting divide "decisiveness" and "fairness" into two optimization sub-problems, which are simpler than the orig- inal non-convex loss. The overall optimization problem is represented by a Lagrangian function combining network predictions a with auxiliary splitting variables This Lagrangian is our new self-supervised loss function (TO) iteratively solving two simpler sub-problems w.r.t network param- eters and splitting variables y. While analogous to pseudo labels in the previous methods, our loss connects network predictions and y via the reverse cross-entropy H(a making it difficult to call y target label. Instead, we refer to pseudo confidence. Section 2.3 derives efficient EM algorithm solving sub-problem that estimates y.
2.1 MARGIN MAXIMIZATION VIA NORM REGULARIZATION
The average entropy term in (I. a.k.a. "decisiveness", is recommended in Grandvalet & Bengio (2004) general regularization term for semi-supervised problems. They argue that it produces decision boundaries away from all training examples, labeled or not. This seems to suggest larger classification margins, which are good for generalization. However, the decisiveness may not au- tomatically imply large margins if the norm of classifier v in pscudo posterior models (2) 3 is unrestricted, see Figure 2 a). Technically, this follows from the same arguments in Xu el al. (2044) where regularization of the classifier norm is formally related to the margin maximization in the context of their SVM approach clustering.
Interestingly. regularization of the norm for all network parameters [v. w] is motivated in dif- ferently Krause al.] (2010). But, since the classifier parameters v are included, coincidentally. also leads to margin maximization. On the other hand, many MI-based methods BBidle et al. (1991); Ghasedi Dizaji et al. (2017); Asano et al. 2020 do not have regularizer ||v in their clustering loss, e.g. see (). One may argue that practical implementations of these methods implicitly benefit from the weight decay, which is omnipresent in network training.
also possible that gradient descent may implicitly bound the classifier norm Soudry et al. (2018). In any case, since margin maximiza- tion is important for clustering, ideally, it should not be left to chance. Thus, the norm regularization term | should be explicitly present in any clustering loss for pseudo posterior models.
5

---

Under review as a conference paper at ICLR 2023
(l(ullø)
KL (uuull
H(,,
KM(lu.)
1655
H(o,y2)
( 96)
05
09
(a) strong fairness K {uulo)
(b) reverse cross-entropy H(, y)
Figure 3: "Forward" vs "reverse": (a) KI--divergence and (b) cross-entropy. Assuming binary classi- fication K = 2, we can represent all possible probability distributions as points on the interval [0, The solid curves in (a) illustrate our "strong" fairness constraint, i.c. the forward KL-divergence K (ullo) for the average prediction ō. We show two examples of volumetric prior リj = (0.9, 0.1) (blue curve) and U2 = (0.5, 0.5) (red curve). For comparison, the dashed curves represent reverse KL-divergence K (ololl commonly used for the fairness in prior art. The solid curves in (b) show our reverse cross-entropy (a, y) w.r.t the network prediction a. The dashed curves show the for- ward cross-entropy Hyy a), which is standard in prior art. The plots in (b) show examples for two fixed estimates of pseudo-confidence //1 = (0.9, 0.1) (blue curves) and y/2 = (0.5, 0.5) (red curves). errors y. For example, our loss (a, y)
The boundedness of H (a. y) represents robustness turns-off the training (sets zero-gradients) when the estimated confidence is highly uncertain, see //2 = (0.5, 0.5) (solid red). In contrast, the standard loss Hy, σ) trains the network to copy this uncertainty, e.g observe the optimum a for the dashed curves.
We extend MI loss ① by combining it with the regularization of the classifier norm v/| encouraging margin maximization, as shown in Figure 2
Lmii-mm
H(o) H()) y ||v|| H(o) + KL + 7 ||vl1
We note that Jabi al. (2021) also extend their information-based loss (6) with the classifier reg- ularization || but this extra term is used mainly as a technical tool in relating their loss (6) to They do not discuss its relation to margin maximization.
K-means, as detailed in Section 1.2
2.2 OUR SELF-SUPERVISED LOSS FUNCTIONS
Below motivate and put forward new ideas for information- based clustering. First, observe that the entropy (σ) in II is a weak formulation of the fairness constraint. Indeed, as clear from its equivalent formulation in (7), it is enforced by the reverse KL divergence for the average predictions o. In particular, assigns a bounded penalty even for a highly unbalanced solutions where σæ 0 for some k see the dashed red curve in Fig a)). Compare this with the forward KI. divergence K [u || )). see the solid red curve. We propose such zemoavoiding forward version of KL divergence strong fairness loss
Lmi++ = H(6) + AKL(u| + +
(8)
Second, derive our self-supervised loss directly from (8. We the standard splitting technique Boyd & Vandenberghe (2004) to divide optimization of (8) into simpler cuob-prosems separating the "decisiveness" and "fairness" terms, as follows. Introducing auxiliary splitring variables y E A K one for each training example X, optimization of the loss can be equivalently written as
min v.w
H(O) + 7 ||v|
(docisiveness sub-problem)
min
KL(u|) (
(faimess sub problem)
s.t.
y =
(consistency constraint).

---

Under review as a conference paper at ICLR 2023
Such constrained optimization problem can be formulated using Lagrangian function enforcing the equality constraint y = a via the forward KL. divergence for (motivated below)
Lour = H() + (KLaa + X (KL(ul)) 5) + + l|vl]
The Lagrangian is optimized with respect to both the network parameters and latent variables y, but we treat the Lagrange multiplier 3 as a fixed parameer. Thus, the constraint y = may not be
satisfied exactly and the Lagrangian ( works only an approximation of the loss (8) Also, one can justify nyper-parameter 3 = 1 empirically, see appendix J we get the following self-supervised loss formulation
Since (o) + KL(o v)) (o v).
Lour
v)
+ +XKT(uIDD) + > 11vl12
(10)
where the reverse cross entropy (( v) enforces both the decisiveness and consistency y Ri
There are some notable differences between our loss (T) and existing self-labeling losses. For example, consider the loss 6 proposed in [Jab et al. (2021). Our loss reverses the order of both the KL divergence and the cross-entropy terms. As explained earlier, our version the KL divergence enforces stronger fairness, see Fig 3)). The reversal of the cross-entropy is motivated in two ways. First, it makes the training of network predictions a robust to errors in noisy estimates y, see Figure B(b), as the pseudo-confidence estimates y not guaranteed to be accurate. Second, it enforces strong consistency of y with the predictions a, which work as target distributions for y- Thus, when optimizing with respect y, our loss (10) strongly enforces both the fairness and consistency y R a. Yet, this well-constrained optimization with respect to y allows an efficient EM solver derived in Section 2.3
2.3 EM ALGORITIM
Expectation maxiiimzaaaiiiiiiion (EM) algorithm Bishop (006) is commonly used in the context of gen- erative methods estimating probability density functions for given data. To estimate parametric density models, their optimal MLE parameters can be computed by maximizing the likelihoods. If data labeled, estimating separate density functions for each class relatively straightforward. But if the data is unlabeled, it is common to use EM algorithm to estimate more complex multi-modal densities, e.g. GMMs, that use hidden latent variables (analogous to pseudo-contidence y) that are estimated together with the model parameters. Such methods can be used for unsupervised clus- tering. Unlike our pseudo-confidene Bayesian posteriors. Their arg max is the optimal classifier minimizing expected classification rors Duda et al. (2000); Shalev-Shwartz: & Ben-David (2014) assuming that the density functions correctly describe the data. The problem is that complex data requires complex density models that are expensive or impossible to estimate, which motivates discriminative approaches, see Figure
estimates y. their latent variables do correspond to the true
Below we present new efficient algorithm for optimizing our discriminative MI-based loss (IO) with respect to the pseudo-confidence estimates when the model prediction is fixed, i.e. a and
v. Using the variational inference Bishop (2006), we derive a new EM algorithm introducing a different type of latent variables, K distributions S E A AM representing normalized support for each cluster over M data points. We refer to each vector S as a normalized cluster k. Note the difference with distributions represented by pseudo-posterios y A 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 E {l, [l,...,M,, J.. Thus, we will use yi E A and E A Individual components of distribution S E A corresponding to data point will be denoted by scalar S..
First, we expand our loss I0 introducing the latent variables S E AM M
Lour
H(a,y) + A H u1, 3) + 7 1|v1
(11)
V + + 1|vl2
= H(a,y) A Σ 2
Sk
SkM M
< H(o,v) - x Σ
k ck In
y
+ 7 1|vl222
(12)
S M
7

---

Under review as a conference paper at ICLR 2023
Due to the convexity of negative log, apply the Jensen's inequality to derive upper bound, i... to Lour. Such bound becomes tight when:
y
E step:
S
(13)
Then, we fix Sk as
13 and solve the Lagrangian of (12) with simplex constraint to update y as:
of + AM St vf 1+ AMM. S
M step:
(14)
We run these two steps until convergence. Note that the minimum y is guaranteed to be globally optimal since (TT) convex w.r.t. y (Appendix, [A]. The empirical convergence rate is within 15 steps MNIST. As for the computational complexity, while there are other optimization methods of the same order O(N Iteration), such as Projected Gradient Descent, our EM approach extremely easy to implement and can be very fast using the highly optimized built-in functions from standard Pytorch library that supports GPU.
Inspired by Springenberg (2015); Hu et al. (0017), we also adapted our EM algorithm to allow for updating y within each batch. fact, the mini-batch approximation (TT) is an upper bound. Considering the first two terms of (1
Jensen's inequality to get:
H(o,y) + X S EB[HB(o.w) v) X (u, ūB)]
(15) apply our EM al-
where B is the batch randomly sampled from the whole dataset. Now, gorithm to update in each batch, which is even more efficient. Compared to other methods Ghasedi Dizaji
al. (2017); Asano et al. (2020); Jabi al. (202T) which also the auxiliary variable y, we can efficiently update on the fly while they only update once or just few times per epoch due the inefficiency update y for the whole dataset per iteration. Interestingly, we found that it is actually important to update on the fly, which makes convergence faster and improves the performance significantly (Appendix. C.. We use such "batch version" EM throughout all the experiments. Our full algorithm for the loss 10 is summarized in the Appendix.
3 EXPERIMENTAL RESULTS
Our experiments start from pure clustering on fixed low-level features to joint clustering with feature learning. We have also compared different losses suakry-superviied classification. Note that our goal is comparing different losses together with their own optimization algorithms, thus we keeping experimental setup as simple as possible to reduce the distraction factors for analysis.
3.1 LOW-LEVEL CLUSTERING
In this section, we test our loss 10) with a simple linear classifier on MNIST Lecun et al. (1998) by using the (fixed) original features of the images. We compare it to Kmeans and (4). The detailed experimental settings and evaluation methods can be found in Appendix. G and
Kmeans
MI Bridle et al. (1991) Krause et 2010))
Our
accuracy 53.2% Hu et al. (0177)
60.2%(..7)
60.8 % (1.1)
Table 1: Comparison of different losses on MNIST without learning features.
In Table
we report the mean accuracy and standard deviation. Note that discriminative clustering methods perform consistently much better than Kmeans (2 7%) while our approach achieves bit higher accuracy but more robust. Also, a low-level ablation study can be found in Appendix. G
3.2 DEEP CLUSTERING
In this section, add deep neural networks for learning features while doing the clustering simultaneously. We use four standard benchmark datasets: STL10 Coates et al.] (20IT). Ci- FAR1O/CIFARIO 100 Torralba et al. (2008) and MNIST Lecun al. (199)). From Table 2 it can
8

---

Under review as a conference paper at ICLR 2023
be seen that our approach consistently achieves the best or the most competitive results in terms of accuracy. Experimental settings and more detailed discussion are given in Appendix.
STLI0
CIFARIO
CIFARI00-20
MNIST
MI-D
Hu et
2017
20.58%(0.5)
21.4%(0.5)
14.39%(0.7)
92.90%(6.3)
IIC
Ji et al.
2019)
24.12%(1.7)
21.3%(114)
12.58%(0.6)
82.51%((.3)
SeLa &
Asano et al.
2020
23.99%(0.9)
24.16%((..5
15.34%(0.3)
52.86%(1.9)
MI-ADM
Jabi et al.
20011
17.97%(0..)
17.27%(0.6)
11.02%(0.5)
17.75%((.3)
Our
(1.4)
24.16%(0..)
15.09%((.55)
93.58% (4.8)
Quantitative results of accuracy for unsupervised clustering methods. We only use the 20 coarse categories for CIFAR100. We reuse the code published by Ji et al. (2019); A et al. 22020) Hu al. (2017) and implemented the optimization for loss Jf et al. (2021) according to the paper. *: all variables are updated for each batch. 9: loss formula has pseudo-label.
Table 2:
3.3 WEAKLY-SUPERVISED CLASSIFICATION
We also test different methods over different levels of (very) weak supervision on STL10. In Table see that approach still shows very competitive results especially with weaker supervision. More details are given in Appendix. [iiclluing another test on CIFAR 10.
0.1
0.05
0.01
Only seeds
40.27%
36.26%
26.
MI-D Hu et al.
2017)
47.39
40.73%
26.54%
IIC
al.
2019)
44.73%
33.6%
26.17%
SeLa Asano al.
2020
44.84%
36.4%
25.08% %
MI-ADM Jabi et (2021)
45.83%
40.41%
25.79%
+ Our
47.20%
41.13%
26.76% %
Table 3: Quantitative results for superv-su classification on STL10. 0.1, 0.05 and 0.01 correspond to different ratio of labels used for supervision. "Only seeds" means that only use standard cross-entropy loss on labelled data for training.
4 CONCLUSIONS
We proposed new self-supervised loss function for information based discriminative clustering with eseudo-posterte (softmax) models, deep low-level. Our loss enforces strong zero-avoiding fairness and explicitly encourages margin maximization. We show that the latter is achieved by reg- ularizing the norm of the classifier in the network output layer. While this often happens implicitly by omnipresent weight decay, it is important to understand the margin maximization effect of the norm regularization. As we show, the "decisiveness" alone is not sufficient for good margins.
In contrast to prior work, we advocate the reverse cross entropy. where network predictions are swapped with pseudo-confidence estimates y. This makes network training robust to errors y. For example, the predictions are not forced to copy uncertain On the other hand, the predictions a become targets for estimated distributions y. Using variational inference, we derive an efficient EM algorithm to optimize our loss with respect to auxiliary variables
We compare our loss and EM algorithm versus prior losses and the corresponding optimization methods. Our approach consistently produces the top or near-top results all tested unsupervised and reakly-supervised benchmarks, while the previous methods have high variation in their relative performance.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Yuki Markus Asano, Christian Rupprecht, and Andrea Vedaldi. Self-labelling via simultancous clustering and representation learning. In International Conference on Learning Representations, 2020.
Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
John S. Bridle, Anthony R. Heading, and David C. MacKay. Unsupervised classifiers, mutual information and phanttom targets'. In NIPS, pp. 1096-1101, 1991.
Adam Coates, Andrew Ng. and Honglak Lee. An analysis single-layer networks in unsupervised feature learning. In Proceedings of the fourteenth international conference on artificial intelli- gence and statistics, pp. 215-223. JMLR Workshop and Conference Proceedings. 2011.
Marco Cuturi. Sinkhorn distances: Lightspeed computation optimal transport. Advances in neural information processing systems, 26, 2013.
Richard O. Duda, Peter E. Hart, and David G. Stork. Pattern Classification (2nd Edition). Wiley- Interscience, 2000.
Kamran Ghasedi Dizaji, Amirhossein Herandi, Cheng Deng, Weidong Cai, and Heng Huang. Deep clustering via joint convolutional autoencoder embedding and relative entropy minimization. In Proceedings of the IEEE international conference on computer vision, pp. 5736-5745, 2017.
Yves Grandvalet and Yoshua Bengio. Semi-supervised learning by entropy minimization. Advances in neural information processing systems, 17, 2004.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Weinberger. On calibration of modern neural networks. In International conference on machine learning, pp. 1321-1330. PMLR, 2017.
Weihua Hu, Takeru Miyato, Seiya Tokui, Eicchi Matsumoto, and Masashi Sugiyama. Learning discrete representations information maximizing self-augmented training. In International conference on machine learning, pp. 1558-1567. PMLR, 2017.
Mohammed Jabi, Marco Pedersoli, Amar Mitiche, and Ismail Ben Ayed. Deep clustering: On the link between discriminative models and k-means. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1887)9688 2021.
Xu Ji, Joao Henriques, and Andrea Vedaldi. Invariant information clustering for unsupervised image classification and segmentation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 9865-9874, 2019.
Michael Kearns, Yishay Mansour, and Andrew Y. Ng. An information--hhoon analysis of hard and soft assignment methods for clustering. UAI '97: Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, Brown University, Providence, Rhode Island, USA, August 1-3, 1997, pp. 282-293 Morgan Kaufmann, 1997.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. ICLR (Poster), 2015.
Andreas Krause, Pietro Perona, and Ryan Gomes. Discriminative clustering by regularized infor- mation maximization. Advances in neural information processing systems, 23, 2010.
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logisties quarterly, 2(1-2):83-97, 1955.
Y. Lecun, I.. Bottou, Y. Bengio, and P. Haffner. soadient-hasede learning applied to document recog- nition. Proceedings of the IEEE, 86(11):2278-2333 232424 1998.
Rafael Müller, Simon Korbblihh, and Geoffrey E Hinton. When does label smoothing help? Ad- vances neural information processing systems, 32, 2019.
10

---

Under review as a conference paper at ICLR 2023
Gabriel Pereyra, George Tucker, Jan Chorowski, Lukasz Kaiser, and Geoffrey Hinton. Regularizing neural networks by penalizing confident output distributions. 2017.
David E Rumelhart, Geoffrey Hinton, and Ronald J Williams. Learning representations by back- propagating errors. Nature, 323(6088):533-536 1986.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014. ISBN 1107057132.
Hwanjun Song, Minscok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from noisy labels with deep neural networks: A survey, IEEE Transactions on Neural Networks and Learning Systems, 2022.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19 (1):2822-2878, 2018.
Jost Tobias Springenberg. Unsupervised and sepi-supervised learning with categorical generative adversarial networks. In International Conference on Learning Representations, 2015.
Daiki Tanaka, Daiki Ikami, Toshihiko Yamasaki, and Kiyoharu Aizawa. Joint optimization frame- work for learning with noisy labels. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5562, 2018.
Antonio Torralba, Rob Fergus, and William T Freeman. 80 million tiny images: A large data set for nonparametric object and scene recognition. IEEE transactions on pattern analysis and machine intelligence, 30(1 1):1958-111 1970, 2008
Linli Xu, James Neufeld, Bryce Larson, and Dale Schuurmans. Maximum margin clustering. In L. Saul, Y. Weiss, and L. Bottou (eds.), Advances in Neural Information Processing Systems, volume 17, MIT Press, 2004.
11

---

Under review as a conference paper at ICLR 2023
A PROOF
Lemma Given fixed 0; E A where E (I,..., M) and u E A the objective
ΣΣ of In v > Σ ug In Ei v
Bly)
convex for y, where yi E A
Proof. First, we rewrite E(y)
8
Ex M
E(y) -
Σ Σ
of
Xug In iy
M
Σ Sk((²))
(16)
Next, we prove that fa (0.1) + R is concave based the definition of concavity Boyd & Vandenberghe (2004) for any [I.....]. Considering a = (1 - a)æ + 0x2 where 21, 22
R and E [0, we have
M Σ o In ((1 a))a + o2223) Aus E. a) ar2;)
(x)
M
Σ (1 a)o In ao 11
M
+ Au (1- a)
E + taln Ex M
M
(1 ())((i) + aff((12)
The inequality uses Jensen's inequality. Now that fa is proved to concave, -fe will be convex. Then Ely) be easily proved to be convex using the definition of convexity with the similar steps above.
B OUR ALGORITHM
Algorithm 1:
Optimization for our loss
Input: network parameters iv, w] and dataset Output: network parameters jy*, w*] for each epoch do for each iteration do Initialize by the network output at current stage as a warm start; while not convergent do
S
v
E, 2J
v I+AM Ee 8
st
end
Update [w, v] using loss HB(0,y) + ||v]] via stochastic gradient descent
end
end
C LOSS CURVE
D NETWORK ARCHITECTURE
The network structure is VGG-style and adapted from Ji et al. (019
12

---

Under review as a conference paper at ICLR 2023
loss:
update y on whole dataset once per epoch update y batch data per iteration
232
231.5
231
Iteration
2k 4k
10k
12k
Figure 4: Loss (10) curves for different update setting y. This is generated with just linear classifier on MNIST. We use the same initialization and run both for 50 epochs. The gray line has accuracy of 52.35% while the yellow achieves 63%.
Grey(28x28x1)
RGB(32x32x3)
RGB((6x96X3)
IxConv(5x5.==I.=22)))
@66
IxComn(5x5,==11==2)e0)
IxConv(5x5.s=2.p=22e 128
IxMaxPoo((x2..s=2)
1xMaxPool(2x2,s=2)
IxMaxPool(222,==2)
(CCon((xx,s=e..==)00) 128
IxComv(5x5==1.-=2)e0
IxComv(5x5,==2.==2222222
IxMaxxool(2x2,s=2)
(x1,)2))(()2,5=2)
IxMaxXool(222,.55
IxConv(5x5s=Il.==2))
256
IxComv555..=1..=2))
128
IxConv(5x5.==2.p=2)0055
IxMaxXool(2x22:=2)
(xMaxXool(2x225=2)
(xMax2ool(222.==2)
IxCom<5xx5x=1..=22@0111 (xLinnar
1xComv(555==1.p=226 256
>Conn(5x55==2p=22)6)
1024
IxLinear(256x4x4.K)
Table 4:
Network architecture summary. stride; p: padding; K: number of clusters. The first
column is used on MNIST Lecun et al. (1988; ; the second one is used on CIFAR 10/100 Torralbal al. 20088; the third one is used on 0TLIO Coates al. (201T). Batch normalization is also applied after each Conv layer. ReLu is adopted for non non-linear activation function.
E DATASET SUMMARY
STL.10
CIFAR10
CIFAR100 1002000020
MNIST
13000
60000
60000
70000
96x96x3
32x32x3
32x32x3
28x28x1
Table 5: Dataset summary for unsupervised clustering.
TableBjindicater the number (training) data and the input size of each image for the unsupervised clustering. Training and test sets are the same.
As for weakly-supervised classification on STL10, we use 5000 images for training and 8000 im- ages for testing. We only keep certain percentage of ground-truth labels for each class of training data. The accuracy is calculated on test set by comparing the hard-max of prediction to the ground- truth.
13

---

Under review as a conference paper at ICLR 2023
F EXPERIMENTAL EVALUATION
As for the evaluation unsupervised clustering, set the number of clusters the number of ground-truth categories and we adopt the standard method Kuhn (1955) by finding the best one-to- one mapping between clusters and labels. We the accuracy the measure for both unsupervised and weakly-supervised settings while the latter calculates the accuracy on the test set.
G LOW-LEVEL CLUSTERING
As for the experiments on MNIST Lecun et al. 1998), we transform the original image values linearly into 1-1,11 1] and use the flattened images as input features. Note that here we only use linear classifier without training any features. We employ stochastic gradient descent with learning rate 0.07 to update v in (4) and (TO). We use the same (random) intialization for both losses and run each 6 times up to 50 epochs per run. We use 250 for batch size. We set 0.01 for both and use 100 for (1Op and 1.3 for
We fix the hyperparameter values for 4 and throughout the whole experimental sections.
We also conducted an ablation study on toy examples as shown in Figure.5) We use the normalized X-Y coordinates of the data points as the input. We can see that each part of our loss is necessary for obtaining good result. Note that, in (a), (c) 3-label case, the clusters formed are the same, but the decision boundaries which implies the generalization are different. This emphasizes the importance of including I.2 norm v to enforce maximum margin for better generalization.
2 clusters
3 clusters
(a) 7 0 0
(b)
(c) full setting
Figure 5: "Shallow" ablation study on toy examples.
H DEEP CLUSTERING
We add deep neural networks for learning features while doing the clustering simultaneously. We use four standard benchmark datasets: STL Coates et al. (2011), CIFAR1O/CIPS 100 Torralb al. (1998). As for the architectures,
al. 2008 and MNIST to use VGG1 1-like network structures whereas we use it for both gray-scale and RGB images with some adjustments as shown in Appendix. D
followed Ji al. (2019)
Besides the clustering loss, we also adopted self-augmentation techniques, following Hu et al. 2017); Ji et al. (2019); Asano et al. (2020). Such technique is important for enforcing neural net- works to learn augmentatioon-invaiian features, which are often semantically meaningful. While Ji et al. (2019) designed their loss directly based on such technique, our loss and Krause et al. (2010); Asano et al. (2020); Jabi al. (202I) more general for clustering without any guar- antee to generate semantic clusters. Thus, for fair comparison and more reasonable results, we combine such augmentation technique into network training. Specifically, achieved this by set-
14

---

Under review as a conference paper at ICLR 2023
ting o, E, [vvo fw (. For each image, generate two augmentations sampled from "horizontal flip". "rotation" and "color distortion".
We Adam Kingma & Ba 2015) with learning rate 1e for optimizing the network parameters. We set batch size to 250 for CIFARIO, CIFAR100 and MNIST, and we use 160 for STL10. In Table 2 we report the mean accuracy and Std from runs with different initializations while use the same initialization for methods in each run. We still use 50 epochs for each run and all methods reach convergence within 50 epochs.
As for other methods in Table 2 MI-D has the most comparable results to us, in part because our loss be seen as approximation the MI and we both update all variables per batch. Sela achieves relatively better results on other three datasets than MNIST, because it enforces hard constraint on "fairness" and MNIST is the only one of four sets that the data we collect is mostly not exactly balanced. This could be the reason why such method is better for the unsupervised representation learning where over-clustering can be employed and real clusters become less important. MI-ADM only updates the pseudo-labels once per epoch, thus easily leading the network towards a trap of local minimum created by the incorrect pseudo-labels through the forward cross-entropy loss illustrated in Figure
exactly balanced. In real world,
I WEAKLY-SUPERVISE CLUSTERING
We use the same experimental settings as that in unsupervised clustering except for two points: 1. We add cross-entropy loss on labelled data; 2. We separate the training data from test data while we all the data for training and test in unsupervised clustering.
While MI-ADM the worst according to Table setting. This might be sign that the advantage of more frequent update variables in unsupervised clustering is waning since the seeds help the network keeping away from some bad local minima.
improved significantly in weakly-supervised
Below is the result CIFAR 10.
0.1
0.05
0.01
Only seeds
58.77%
54.27%
39.01%
+ MI-D
65.54%
61.4%
46.97%
IIC
66.5%
61.17%
47.21%
SeLa 61.5%
58.35%
47.19%
MI-ADM
62.51%
57.05%
45.91%
+ Our
66.17%
61.59%
47.22%
15

---

Under review as a conference paper at ICLR 2023
J HYPERPARAMETER 3
Below is an empirical justification for setting hyper-parameter, 3 in the loss 9 The first two terms in can be written as (1 - - (f y). If > then the negative entropy pushes predictions away from one-hot solutions weakening the decisiveness. On the other hand, if
then the loss is non-convex w.r.t a that may trap gradient descent in bad local minima, as illustrated by the plots for y = (0.9, 0.1) in Figure 6
β = 1
B = 0.5
β 0.1
1
Figure 6: (1-3)1((o) (11(0,))
16


Reviews:
[{"review_id": "nz3OABhksz", "reviewer": "Reviewer_7XGP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work observed a connection between mutual information-based clustering loss and margin-maximization, and proposed two changes to the process: (i) explicit $\\ell_2$ regularization to promote the margin maximization behavior, and (ii) replacing the entropy term in MI, which can be viewed as a reverse KL divergence, with a forward KL divergence.  The modifications lead to improved performance on weakly supervised classification tasks.", "summary_of_the_review": "+ The authors made some observations on the MI loss for clustering, which leads to an algorithm that appears to perform well\n\n- The motivating discussions are somewhat simplistic, and not fully convincing", "strength_and_weaknesses": "The authors provided intuitions on the proposed modifications, which are based on past interpretations for feature-space clustering.  The proposed algorithm appears to have competitive performance, but I am not familiar with this literature and cannot judge on the significance of the empirical results.\n\nOn the downside, the novelty is a bit lacking: the use of $\\ell_2$ regularization is ubiquitous, and its margin-promoting behavior is known in different but related settings (e.g., softmax classification); the replacement of reverse KL with forward KL is straightforward given the fairness interpretation of the former.  The interpretation of MI as enforcing \"fairness\" and \"decisiveness\" is also somewhat arbitrary and simplistic, as they appear to provide no further concrete insights, than the proposed algorithm.  Thus, it appears that the significance of the work hinges on the empirical side.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "bOGlj-uxl7Y", "reviewer": "Reviewer_3fzk", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper discusses information theory-based clustering and self-supervised learning.\nThe main contribution lies in the use of \"reversed\" KL divergence and cross-entropy.\n\n\nThe paper is a bit confusing, so I present here my understanding of the theory.\n\nClustering can be done by maximizing the Mutual Information over the class prediction, $\\sigma$:\n$$\\min_\\sigma -MI(\\sigma, X)$$\nAccording to Bridle et al. (1991) the latter can be approximated as follows, where the $avg$ means average:\n$$\\min_\\sigma avg[H(\\sigma)] - H(avg({\\sigma}))$$\nThe last term can be rewritten as a KL divergence wrt to a uniform distribution plus a constant that we omit:\n$$\\min_\\sigma avg[H(\\sigma)] + KL(avg(\\sigma)|| Unif)$$\nThe clustering is done in a feature space learned by a network with weight w, and the clustering is controlled by one/two vectors v.\nKrause et al. 2010  suggested an l2-regularization of all the weights involved that can be weighted.\n$$\\min_\\sigma avg[H(\\sigma)] + KL(avg(\\sigma)|| Unif) + \\gamma ||v,w||^2$$\nThe idea is that controlling the norm of v (classifier) also controls the margin. exactly like an SVM.\nControlling the norm of w helps the training.\n\n*First contribution*: the authors reverse the KL (Eq10) and weigh it (the authors omit w).\n$$\\min_\\sigma avg[H(\\sigma)] + \\lambda KL(Unif||avg(\\sigma)) + \\gamma ||v,w||^2$$\nThe argument is to prevent $avg(\\sigma)$ from being a one-hot vector in a more strict manner than if the KL is computed the other way around. $avg(\\sigma)$ being a one-hot vector ( or at least that some of its dimensions go to zero) means that some clusters collapse aka are empty.\n\nNow let's assume we have some (soft) pseudo-labels $y$. If we step back and state what we try to achieve:\n1/ Good class separation with a margin: $\\min_{v,w,\\sigma} avg[H(\\sigma)] + \\gamma||v,w||^2$\n2/ All the clusters should be used (fairness): $KL(Unif||avg(y))$\n3/ Consistency: the pseudo labels match the class assignments: $y = \\sigma$\n\n*Second contribution*: Using a KL to match $\\sigma$ and $y$.\nWe invoke Lagrange to merge them all:\n$$ L = avg[H(\\sigma)] + \\beta \\cdot avg[KL(\\sigma||y)] + \\lambda KL(Unif||avg(y)) + \\gamma||v,w||^2$$If we set $\\beta=1$, it simplifies to the final loss:\n$$ L = avg[H(\\sigma,y)] + \\lambda KL(Unif||avg(y)) + \\gamma||v,w||^2$$\nwhere the cross entropy between class prediction $\\sigma$ and pseudo-label $y$ is reverse compared to usual.\nFor $y$ fixed, $H(\\sigma,y)$ is a line that is horizontal if the model is not confident on the pseudo-label $y$. This means the gradient becomes close to zero. So no need to prune the pseudo-labels!", "summary_of_the_review": "The paper brings interesting ideas.\nAfter reading it all, I am still unsure what is $y$. how does it differ from $\\sigma$ and how do we compute all of these?\n\nThe authors try to build a discussion about clustering with information theory, but it turns confusing. There are too many arguments not very well organized. They compare themselves too much to Jabi et al. to the point that the main contributions are a bit hidden. I think the whole presentation could be greatly simplified.\n\nI do find the ideas interesting, but the paper/presentation is too confusing.\n\nIf I understood well, you're doing a centroid based clustering (hence the v) where you want the separation to be controlled with information theory tools. It is a fair endeavor. But then you mix geometry (l2 regularization) and information theory (entropy).\nCan't you control the margin using only pure entropy-based tools?\n\nRegarding clustering with information theory, I would suggest the authors have a look at: \nhttps://arxiv.org/abs/1406.1222\nIn this paper, they use pure information theory tools and achieve pretty impressive results.\n\n\n\n\n\nFigure 1 is a bit unfair. depending on the initialization, k-means or GMM can split this dataset correctly.\nAlso for a softer boundary, then just use GMM which would be fairer than k-means, since the latter uses hard assignments while the proposed method relies on soft assignments, like GMM.\n\nEq 5: I think you want to say that y arises from a uniform distribution. The correct notation is $\\bar{y] \\tilde u$.\n\npage4 The topic moves from clustering to self-supervised learning without real warning.\n\nFig3: The caption is confusing. So are the plots. Regarding Fig 3.a: why allowing $\\sigma$ to have zero coordinates not acceptable? You might also want to let the network decide and close some clusters.\n\nPage 6 optimization problem. Why is $\\sigma$ not under the first min? I put it in my summary. Maybe I am wrong. Maybe sigma is a function of v and w. it's not clear.\nWhy do you use y in the second minimization, while it was not in the previous equations? I am not sure this helps to understand how the equations connect.\n\nSection 3.1: Why Equation 4 and not 10? I thought Eq10 was your final model. \nAlso, k-means can cluster raw MNIST with more than 53% accuracy, using sklearn implementation.\n\nEquation 10 relies on pseudo labels. It is thus also dependent on the initialization. So I would be interested to see how it works when not supported by a network.\n\nAppendix G: Why Equation 9 and not 10? There are no gamma and lambda in equation 4. Figure 5, which one is Eq4 which one is Eq.9?\n\nTable 2: For IIC, did you use over-clustering heads as it is recommended in the paper?\nThe discussion in Appendix H should be in the main text.\n\n\n\n\n", "strength_and_weaknesses": "+ Reversing the cross-entropy for the pseudo-labels is indeed a good idea. In my understanding, it can replace pruning or selecting the pseudo-labels since the low-confident ones will \"naturally\"  have little influence on the training.\n+ Inverting the KL is also interesting but I don't really see a huge benefit. Fair enough.\n\n- The writing is confusing. Arguments cross each other, the construction is not linear and some variables are not clearly defined. \n- The experimental section is poor. Several Ablation analyses are missing.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FMTkj4oDnx", "reviewer": "Reviewer_oWJS", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes adding a normalization term to the existing MI-based clustering objective.", "summary_of_the_review": "As mentioned above, this paper is of bad quality in organization and writing. The proposed method is neither novel or effective. The experiments are also not conducted correctly and sufficiently.", "strength_and_weaknesses": "- Weakness:\n    1. The organization of the paper is poor. For example, the authors spend about two pages discussing previously well-known methods and the corresponding properties. It is not clear what problem the authors want to tackle.\n    2. The current “contributions” (especially the second) are not exactly contributions. They are more like details in the proposed method.\n    3. Fig. 2 indicates that the weight parameter needs to be carefully tuned to make the normalization term work.\n    4. Experiments on MNIST show almost the same performance for the proposed method and previous MI-based ones. Moreover, it is unfair to conduct K-means on the raw data while using a 1-layer classifier for the proposed method.\n    5. The experimental results on deep clustering benchmarks are not correct. For example, the results for IIC do not match those reported in its original paper. Thus I doubt the correctness of the conducted experiments.\n    6. The authors claim the normalization term is helpful for those pseudo label based clustering methods. But no corresponding experiments are conducted to support the claim.\n    7. Parameter analysis on the weight gamma is missing.\n    8. Minor: It is really strange to name the loss L_our.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject