MiCE: Mixture of Contrastive Experts for Unsupervised Image Clustering
Authors: Tsung Wei Tsai
Chongxuan Li
Jun Zhu
Venue: ICLR 2021 Poster (2021)
Keywords: unsupervised learning
clustering
self supervised learning
mixture of experts

Abstract: We present Mixture of Contrastive Experts (MiCE), a unified probabilistic clustering framework that simultaneously exploits the discriminative representations learned by contrastive learning and the semantic structures captured by a latent mixture model. Motivated by the mixture of experts, MiCE employs a gating function to partition an unlabeled dataset into subsets according to the latent semantics and multiple experts to discriminate distinct subsets of instances assigned to them in a contrastive learning manner. To solve the nontrivial inference and learning problems caused by the latent variables, we further develop a scalable variant of the Expectation-Maximization (EM) algorithm for MiCE and provide proof of the convergence. Empirically, we evaluate the clustering performance of MiCE on four widely adopted natural image datasets. MiCE achieves significantly better results than various previous methods and a strong contrastive learning baseline.

Published as a conference paper at ICLR 2021
MICE: MIXTURE OF CONTRASTIVE EXPERTS FOR UN- SUPERVISED IMAGE CLUSTERING
Tsung Wei Tsai, Chongxuan Li, Jun Zhu
Dept. of Comp. Sci. & Tech., Institute for AI, BNRist Center Tsinghua- Bonghu Bosch Joint MI. Center, THBI Lab, Tsinghua University, Beijing, 100084 China (peter831 1214,, chongxuanli 11911 @@gmail. .omm dcszjemail, wwwnghua..ddus edu.
ABSTRACT
We present Mixture of Contrastive Experts (MiCE), unified probabilistic clus- tering framework that simultaneously exploits the discriminative representations learned by contrastive learning and the semantic structures captured by latent mixture model. Motivated by the mixture of experts, MiCE employs gating func- tion to partition an unlabeled dataset into subsets according the latent semantics and multiple experts to discriminate distinct subsets of instances assigned to them in a contrastive learning manner. To solve the nontrivial inference and learning problems caused by the latent variables, we further develop scalable variant of the Dnpectation-Maxiizzznen
(EM) algorithm for MiCE and provide proof of the convergence. Empirically, we evaluate the clustering performance of MiCE on four widely adopted natural image datasets. MiCE achieves significantly better results] than various previous methods and strong contrastive learning baseline.
INTRODUCTION
Unsupervised clustering a fundamental task that aims to partition data into distinct groups of similar ones without explicit human labels. Deep clustering methods (Xie et al. (016)] Wu et al. (219)) exploit the representations learned by neural networks and have made large progress on high- dimensionnn data recently. Often, such methods learn the representations for clustering by reconstructing data in deterministic (Ghasedi Dizaji et al.] 2017) or probabilistic manner (Jiang et al.) 2016). or maximizing certain mutual information (Hu al. 2017 Ji al.) 2019) (see Sec. Sec. the related work). Despite the recent advances, the representations learned by existing methods may not be discriminative enough to capture the semantic similarity between images.
The instance discrimination task (Wu et al. 2018 He et al. 2020) in contrastive learning has shown promise in pre-training representations transferable downstream tasks through fine-tuning. Given that the literature (Shiran & Weinshall 2019 Niu et al. (020) shows improved representations can lead better clustering results, we hypothesize that instance discrimination can improve the performance as well. A straightforward approach is to learn classical clustering model, e.g. spherical k-means (Dhillon & Modha 200T), directly on the representations pre-traine pre-trained by the task. Such two-stage baseline can achieve excellent clustering results (please refer to Tab. However, because of the independence of the two stages, the baseline may not fully explore the semantic structures of the data when learning the representations and lead to sub-optimal solution for clustering.
To this end, we propose Mixture of Contrastive Experts (MiCE), a unified probabilistic clustering method that utilizes the instance discrimination task as stepping stone to improve clustering. In particular, to capture the semantic structure explicitly, we formulate a mixture of conditional models by introducing latent variables to represent cluster labels of the images, which is inspired by the mixture of experts (MoE) formulation. In MiCE, each of the conditional models, also called an expert, learns to discriminate subset of instances, while input-dependent gating function partitions the dataset into subsets according to the latent semantics by allocating weights among experts. Further, we develop a scalable variant of the Exppetation-Maxxiizaan (EM) algorithm (Dempster al.
"Corresponding author.
"Code is available https://gtt www.eeth.........eeeeeeee www.:/ssgggeeeeaaaiiiaoioooo

---

Published as a conference paper at ICLR 2021
1977 for the nontrivial inference and learning problems. In the E-step, obtain the approximate inference of the posterior distribution of the latent variables given the observed data. In the M-step, maximize the evidence lower bound (ELBO) of the log conditional likelihood with respect to all parameters. Theoretically, we show that the ELBO is bounded and the proposed EM algorithm leads to the convergence of ELBO. Moreover, we carefully discuss the algorithmic relation between MiCE and the two-stage baseline and show that the latter is a special instance of the former in a certain extreme case.
Compared with existing clustering methods, MiCE has the following advantages, (i) Methodolog- ically unified: MiCE conjoins the benefits of both the discriminative representations learned by contrastive learning and the semantic structures captured by a latent mixture model within a unified probabilistic framework. (ii) Free from regularization: MiCE trained by EM optimizes a single objective function, which does not require auxiliary loss or regularization terms. (iii) Empirically effective: Evaluated on four widely adopted natural image datasets, MiCE achieves significantly better results than strong contrastive baseline and extensive prior clustering methods on several benchmarks without any form of pre-training.
2
RELATED WORK
Deep clustering. Inspired by the success of deep learning, many researchers propose to learn the
representations and cluster assignments simultaneously (Xie et al. 2016 Yang et al. 2016 2017)
based on data reconstruction (Xie et al.] 2016 Yang et al. 2017) : pairwise relationship among
instances (Chang et al., 2017 Haeusser Niu et al. (220), etc. The joint training framework often ends up optimizing weighted average of multiple loss functions. However, given that the validation dataset barely
2018 Wu et al. 2019), multi-task learning (Shiran
& Weinshall|2011
provided, tuning the weights between the losses may be impractical (Ghasedii Dizaji et al. 2017).
Recently, several methods also explore probabilistic modeling, and they introduce latent variables to represent the underlying classes. On one hand, deep generative approaches (Jiang et al. 2016 Dilokthanakul al., 2016 Chongxuan al.] 2018 Mukherjee al. 2019 Yang et al. 2019) attempt to capture the data generation process with a mixture of Gaussian prior on latent representations. However, the imposed assumptions can be violated in many cases, and capturing the true data distribution is challenging but may not be helpful to the clustering (Krause et al. 2010). On the other hand, discriminative approaches (Hu et al. 2017 Ji et al., 2019: Darlow & Storkey 2020) directly model the mapping from the inputs to the cluster labels and maximize a form of mutual information, which often yields superior cluster accuracy. Despite the simplicity, the discriminative approaches discard the instance-specifie details that can benefit clustering via improving the representations.
Besides, MIXAE (Zhang et al. 2017p. DAMIC (Chazan et al. 2019), and MoE-Sim- Sim-VAE (Kopf) et al. 2019) combine the mixture of experts (MoE) formulation (Jacobs et al. 1991) with the data reconstruction task. However, either pre- pre-training, regularization, or an extra clustering loss is required.
Contrastive learning. To learn discriminative representations, contrastive learning (Wu et al. 2018 Oord et al. 2018 He et al. 2020 Tian et al. 2019 Chen et al. 2020) incorporates various contrastive loss functions with different pretext tasks such colorization (Zhang et al., (016)) context auto- encoding (Pathak et al. 2016). and instance discrimination (Dosovitskiy et al. 2015 Wu et al. 2018). The pre-trained representations often achieve promising results on downstream tasks, e.g., depth prediction, object detection (Ren et al. 2015) He et al.) 2017), and image classification (Kolesnikoy al.) 2019), after fine-tuning with human labels. In particular, InstDise (Wu et al., 2018) learns from instance-level discrimination using NCE (Gutmann & Hyvärinen 2010). and maintains a memory bank to compute the loss function efficiently. MoCo replaces the memory bank with a queue and maintains an EMA of the student network as the teacher network to encourage consistent representations. A concurrent work called PCL (Li et al. 2020) also explores the semantic struc- tures in contrastive learning. They add an auxiliary cluster-style objective function on top of the MoCo's original objective, which differs from our method significantly. PCL requires an auxiliary k-means (Lloyd) 1982) algorithm to obtain the posterior estimates and the prototypes. Moreover, their aim of clustering is to induce transferable embeddings instead of discovering groups of data that correspond to underlying semantic classes.
2

---

Published as a conference paper at ICLR 2021
3 PRELIMINARY
We introduce the contrastive learning methods based on the instance discrimination task (Wu et al. 2018: Ye et al., 2019; He et al. 20200 Chen et al. 2020), with a particular focus on the recent state-of-the-art method, MoCo (He et al. 2020). Let X (xx Ji=z be a set of images without the ground-truth labels, and each the datapoint x, assigned with a unique surrogate label Vn E (1.,.... such that Yn * V5, Vj * If To learn representations in an unsupervised manner, instance discrimination considers a discriminative classifier that maps the given image to surrogate label. Suppose that we have two encoder networks fo and for that generate lz-normalized embeddings yn E IR and f, E Rd, respectively, given the image X, with the surrogate label yn- We show the parameters of the networks in the subscript, and images are transformed by stochastic data augmentation module before passing to the networks (please see Appendix D). probability classifier with:
We can model the
N II plu. x
exp(v T fn/T) yn
p X
II
N -i=1 exp(v, f.//)
where T is the temperature hyper- parameter controlling the concentration level (Hinton et al. 2015
The recent contrastive learning methods mainly differ in: (1) The contrastive loss used to learn the network parameters, including NCE (Wu et al., 2018), InfoNCE (Oord et al. 2018), and the margin loss (Schroff al. 2015). (2) The choice of the
encoder networks based deep neural networks (DNNs) in which 0' can be an identical (Ye et al., 2019 Chen et al. (020). distinct (Tian et al. 2019).
or an exponential moving average (EMA) (He et al. (2020) version of O.
In particular, MoCo (He et al. 2020 learns by minimizing the InfoNCE loss:
exp (v fn/T)
log exp (v fn/T) + Ei= exp (q. fn/T)'
where q E RR is a queue of size N storing previous embeddings from for While it adopts the FMA approach to avoid rapidly changing embeddings in the queue that adversely impacts the performance (He al. (020).. For convenience, network respectively (Tarvainen & Valpola 2017 Tsai et al. 2019). In the following, we propose unified latent mixture model based on contrastive learning tackle the clustering task.
refer fg and for the student and teacher
MIXTURE OF CONTRASTIVE EXPERTS
Unsupervised clustering aims to partition dataset X with N observations into K clusters. We introduce the latent variable in E {1,2, ..., K} to be the cluster label of the image x,, and naturally extend Eq. ( to Mixture of Contrastive Experts (MiCE):
N
DYY
p(yn, 2n = k) xx. x (k,=
n=1 k=1
N
p(=n = =k(,, ( p(yn (nn, = (en=k))
A=1
where (.) is indicator function. The formulation explicitly introduces a mixture model to capture the latent semantic structures, which is inspired by the mixture of experts (MoE) framework (Jacobs et al. [ In Eq. (3). p(y, [x, 2n) is one of the experts that learn to discriminate subset of instances and p( xx,) is a gating function that partitions the dataset into subsets according to the latent semantics by routing the given input one a few experts. With a divide-and-ccoquee principle, the experts are often highly specialized in particular images that share similar semantics, which improves the learning efficiency. Notably, MiCE is generic to the choice of the underlying
The value of the surrogate label can he regarded as the index of the image.
Due to summation over the entire dataset in the denominator term, it can be computationally prohibitive to get Maximum likelihood estimation (MIF) of the parameters (Ma & Collins 2018.
3

---

Published as a conference paper at ICLR 2021
Expert 1
Gating function
fo
fn
pl the
Nei
fo
Valil
Expert 2
80
kn,a
Byy
pl
Vs..
Image
f8
1,2
Prediction
2.
Expert
fo
8r,8
Bie
fr
[4g
Figure 1: An illustration of MiCE with three experts. Best view in color.
contrastive methods (Wu et al. 2018 He et al. 2020 Chen et al. 2020) while in this paper, we focus on an instance based on MoCo. Also, please see Fig. for an illustration of MiCE with three experts.
In contrast to the original MoE used in the supervised settings (Jacobs et al. 1991). our experts learn from instance-wise discrimination instead of human labels. addition, both gating and expert parts of MiCE are based on DNNs to fit the high-dimensional data. In the following. we will elaborate on how we parameterize the gating function and the experts to fit the clustering task. For simplicity, we omit the parameters in all probability distributions in this section.
The gating function organizes instance discrimination task into K simpler subtasks by weighting the experts based on the semantics of the input image. We define IV as an encoder network that outputs an embedding for each input image. We denote the output vector image N,, as gn Rd. The gating function then parameterized
Gating function.
Xn) = cxplwI, T ga/k)
(4)
Ek= exp(w, gn/m))
where is the temperature, and [w represent the gating prototypes. All prototypes and image embeddings are fz-normalized in the Rd space. Hence, the gating function performs soft partitioning of the dataset based on the cosine similarity between the image embeddings and the gating prototypes. We can view it as a prototype-based discriminative clustering module, whereas obtain the cluster labels using posterior inference to consider additional information in the experts.
Experts. In MiCE, every expert learns solve the instance discrimination subtask arranged by the gating function. We define the expert in terms of the unnormalized model ④--) following Wu et al. (2018); He al. (2020). Therefore, the probability of the image x,, being recognized as the y,, y,-th one by the -, expert is formulated as follows:
((Xn, Mas Zn)
plyn Xn. 2n)
(5)
Z(Xny Zx.)
where Z(x,; 2n) Ei=1 (Xx,, Mes 2n) is normalization constant that is often computationally intractable.
Similar MoCo, have the student network that maps the image x,, into K continuous em- beddings f, = (fr, 1 E &Rxd, xd Likewise, the teacher network fer outputs vg.. = (Vy.. * } E k xd given X,. To be specific, fr,e. E gd and Van.a. E gd are the student embedding and the teacher embedding for images Xn under the zn-th expert, respectively. We then parameterize the unnormalized model as:
T {(X,, Uny 2n) = exx (V (fn.zn + Mzz,) /TT
(6)
4

---

Published as a conference paper at ICLR 2021
where 7 is the temperature and μ { k= represent the cluster prototypes for the experts. In Eq. ( the first instance-win wise dot product explores the instance-level information to induce discrimi- native representations within each expert. The second instance- prototype dot product incorporates the claxs-level information into representation learning, encouraging a clear cluster structure around the prototype. Overall, the learned emheddings are therefore encoded with semantic structures while being discriminative enough to represent the instances. Eq. 66 is built upon MoCo with the EMA approach, while in principle, many other potential solutions exist define the experts, which are left for future studies. Besides, the parameters O and a/ are partially shared, please refer to the Appendix[]oor more details on the architecture.
INFERENCE AND LEARNING
We first discuss the evidence lower bound (ELBO), the single objective used MiCE, Sec. 5.1 Then, we present a scalable variant of the Sespetation-Maxiiizann al. 1977) to deal with the non-trivial inference and learning of MiCE in Sec. Sec.5.2 Lastly, in Sec. 5.3
(EM) algorithm (Dempster
we show that naïve two-stage baseline, in which we run spherical k-means algorithm on the embeddings learned by MoCo, is a special case of MiCE.
5.1 EVIDENCE LOWER BOUND (ELBO)
The parameters to update include the parameters 0, of the student and gating network respectively, and the expert prototypes = {4]]= 1. The learning objective of MiCE is to maximize the evidence lower bound (ELBO) of the log conditional likelihood of the entire dataset. The ELBO of the datapoint n is given by:
log Dogp(ynlxxx (xa) 2 L(O, 1b, |a; Xn, Ma)
By( (x..)..)) [log p( p(yn XSa, 2n: 11] DKr. (g(=nxx) Un) 2n (x; v)),
where ((2n X Vo) is variational distribution infer the latent cluster label given the observed data. The first term in Eq. 7 encourages (<,,/xn,, Un) to be high for the experts that are good at discriminating the input images. Intuitively, it can relief the potential degeneracy issue (Caron et
2018 Ji et al.) 2019). where all images are assigned to the same cluster. This is because degenerated posterior puts the pressure of discriminating looser ELBO. The second term in Eq. (7) is the Kullback-Leibler divergence between the variational distribution and the distribution defined by the gating function. With this term, the gating function is refined during training and considers the capability of the experts when partitioning data. Notably,
images on a single expert, which may result in
MiCE does not rely on auxiliary loss or regularization terms as many prior methods (Haeusser et al. 2018
Shiran & Weinshall 2019
Wu et al. 2019 Niu et al. 2020) do.
5.2 EM ALGORITHM
E-step. Inferring the posterior distribution of latent variables given the observations is an important step to apply MiCE to clustering. According to Bayes' theorem, the posterior distribution given the current estimate of the model parameters is:
p(zn Xx,, Uni 0, tb 11) = p( X pp) X,, 2n O 11)
(8)
Ek p(k x 2b p( (xn, k: θ,
Comparing with the gating function pxz,(x..; v). the posterior provides better estimates of the latent variables by incorporating the supplementary information of the experts. However, cannot tractably compute the posterior distribution because of the normalization constants Z(x,, 2, 0 14).
In fact, given the image x,, and the cluster label .n. Z(x., Zn; O, μ1) sums over the entire dataset, which is prohibitive for large-scale image dataset. We present a simple and analytically tractable estimator to approximate them. Specifically, we maintain queue q gex Rxd that stores v previous outputs of the teacher network, following MoCo closely. Formally, the estimator 2(-) is:
(xm,, zni 0. ()) =exp (yi.... (Ln,,n + +12m) /T)
Σ exp (qIT.. (En,za + M /T). (9)
5

---

Published as a conference paper at ICLR 2021
The estimator is biased, while its bias decreases increases and we can get sufficient amount of embeddings from the queue q efficiently With Eq. we approximate the posterior as:
Uni Uni On; 0,, 1)) p( Xm; 2 (Xn, Zni 0, 11) ((x Zni 0, 14
q(=n|Xn:
(10)
Σx kkml p(k] + (Xn: Una k; O, 14/ (4)22((55) (xx, k; 0,;00,0 14)
M-step. We leverage the stochastic gradient ascent optimize ELBO with respect to the network parameters 0, vb and the expert prototypes We approximate the normalization constants appear in ELBO in analogy to the E-step. formulated as follows:
+ (xn, Un. Pni 0 (xx,, Zn 0 p1)
[(0, 2/, Nnx Ma) (z Ia:. (..44 log
- DKIL. (q(zn Xnx Uni O, 2b 1))lp(z Xxn 4)).
(11)
Sampling a mini-batch B datapoints, we can construct an efficient stochastic estimator of ELBO over the full dataset to learn 0, +b and ja:
N Σ
C(O, th p1 X.
Σ(O, 2b p: Xn, Ha.
(12)
WEB
requires additional care on the update of the prototypes, as discussed in many clustering meth- ods (Sculley) 2010, Xie al. 20166] Yang al. 2017 Shiran & Weinshall, 2019). Some of them carefully adjust the learning rate of each prototype separately (Sculley) 2010 Yang et al. (017). which can be very different from the one used for the network parameters. Since evaluating different learning rate schemes on the validation dataset often infeasible in unsupervised clustering, we employ alternative strategies which are free from using per- per-proootppe learning rates in MiCE.
As for the expert prototypes, we observe that using only the stochastic update can lead bad local optima. Therefore, at the end of each training epoch, apply additional analytical update derived from the ELBO as follows:
P Σ
V Un.ks
P
Ak,
(13)
where Vn, 2, = arg max gk]|x,, Un; O, 2b, (1) is the hard assignment of the cluster label. Please refer to Appendix A.2 for the detailed derivation. Intuitively, the analytical update in Eq. (I3) considers all the teacher embeddings assigned to the k-th cluster, instead of only the ones mini-batch, to avoid bad local optima.
Beside, we fix the gating prototypes to a set of pre-defined embeddings to stabilize the training process. However, using randomly initialized prototypes may cause unnecessary difficulties in partitioning the dataset if of them are crowded together. We address the potential issue by using the means of a Max-Mahalanoha case of the mixture of Gaussian distribution. The untrainable means in MMD provide the optimal inter-cluster dispersion (Pang et al. 2020)) that stabilizes the gating outputs. We provide the algorithm of MMD in Appendix B and systematical ablation study Tab. to investigate the effect of the updates on w and μ.. Lastly, we provide the formal proof on the convergence of the EM algorithm in Appendix A.4
distribution (MMD) (Pang et al.) 2018) which is a special
5.3 RELATIONS TO TWO-STAGE BASELINE
The combination of contrastive learning method and a clustering method is natural baseline of MiCE. Our analysis reveals that MiCE the general form of the two-stage baseline which we learn the image embeddings with MoCo (He et al. 2020) and subsequently run spherical k-means algorithm (Dhillon & Modha 2001) to obtain the cluster labels.
On hand, in the extreme case where and teacher embeddings Vy... are identical for different & (Assumption A4), and the class-level
(Assumption A3), the student embeddings f,,k
'Even though the bias does not vanish due to the use of queue, find that the approximation works well empirically.

---

Published as a conference paper at ICLR 2021
Table Unsupervised clustering performance of different methods on three datasets. The first sector presents the results from the literature, the later ones display the results of the baseline and the proposed MiCE. In the last two sectors, the bold results indicating the one with the highest values. Methods with the legend? are the ones that required post-processing by k-means obtain the clusters since they do not learn the clustering function directly, except that we use spherical k-means for MoCo. We calculate the mean and standard deviation (Std.) of MiCE and MoCo based on five runs.
Datasets
CIFAR-I 10
CIFAR 100
STL-10
ImageNet Dog
Methods/Metrics (%)
NMI
ACC
ARI
NMI
ACC
ARI
NMI
ACC
ARI
NMI
ACC
ARI
k-means (Lloyd] 1982
8.7
22.9
8.40
13.0
12.5
19.2
5.5
10.5
2.0
SC Zelnik-Mann Manor Perona
2004
10.3
24.7
8.5
9.0
13.6
2.2
9.8
15.9
4.8
3.8
11.1
1.3
AEf (Bengro et al. 2006
23,9
31.4
16.9
10.0
16.5
4.8
25.0
30.3
16.1
10.4
18.5
7.3
DAEF (Vincent et al.
2010
25.1
29.7
16.3
11.1
15.1
4.6
22.4
30.2
15.2
10.4
19.0
7.8
SWWALF (Zhao
2015
23.3
28.4
16.4
10.3
14.7
3.9
19.6
27.0
13.6
9,4
15,9
7.6
GAN (Radford et
2015
26.5
31.5
17.6
12.0
15.3
4.5
21.0
29.8
13.9
12.1
17.4
7.8
VAE Kingma We ing
2013)
24.5
29.1
16.7
10.8
15.2
4.0
20.0
28.2
14.6
10.7
17.9
7.9
JULE Yang al. 2016
19.2
27.2
13.8
10.3
13.7
18.2
27.7
16.4
5.4
13.8
2.8
DEC Xie et al. 2016
25.7
30.1
16.1
13.6
18.5
5.0
27.6
35.9
18.6
12.2
19.5
7.9
DAC Chang el al. 2017
39.6
52.2
30.6
18.5
23.8
8.8
36.6
47.0
25.7
21.9
27.5
11.1
DCCM (Wu et al. 2019
62.3 49.6
40.8
28.5
32.7
17.3
37.6
48.2
26.2
32.1
38,3
18.2
IIC Ji et al. 2019)
61.7
25.7
49.9
DHOG (Darlow & Storkey
2020
58.5
66.6
49.2
25.8
26.1
11.8
41.3
48.3
27.2
AttentionCluster (Nuu
2020
47.5
61.0
40.2
21.5
28.1
11.6
44.6
58.3
36.3
28.1
32.2
16.3
MMDC (Shiran Wemnshall
2019
57.2
25.9
31.2
49.8
PICA (Huang et al. 2020)
59.1
69.6
51.2
31.0
33.7
17.1
61.1
71.3
53.1
35.2
35.2
20.1
MoCo (Mean) (He et al.
2020
66.0
74.7
59.3
38.8
39.5
24.0
60.5
70.7
53.0
34.2
30.8
18.4
MoCo (Std.) (He et al. 2020
0.6
1.7
0.9
0.2
0.1
0.4
0.9
2.0
0.8
0.3
1.7
0.9
MiCE (Mean, Ours)
73.5
83.4
69.5
43.0
42.2
27.7
61.3
72.0
53.2
39.4
39.0
24.7
MiCE (Std.. Ours)
0.2
0.2
0.3
0.5
1.4
0.4
1.2
1.8
2.4
1.8
3.0
2.4
MoCo (Besty? (He el al. 2020
66.9
77.6
39.0
39.7
24.2
72.8
$2.4
34.7
33.8
19.7
MiCE (Best, Ours)
73.7
83.5
69.8
43.6
44.0
28.0
63.5
75.2
57.5
42.3
43.9
28.6
information in Eq. 66) is omitted (Assumption A5), we arrive at the same Softmax classifier (Eq, (I) and the InfoNCE loss (Eq. (2) used by MoCo as special case of our method. On the other hand, of particular relevance to the analytical update on expert prototypes (Eq. (13) is the spherical k-means algorithm Dhhilonn & Modha 2001) that leverages the cosine similarity to cluster fz-normalized data (Horii et al.) (012)) In addition to Assumptions A3 and A4, if we assume the unnormalized model perfectly self-normalized (Assumption A2), using the hard assignment get the cluster labels together with the analytical update turns out to be single-iteration spherical k-means algorithm on the teacher embeddings. Please refer to the Appendix for detailed derivation.
The performance of the baseline is limited by the independence of the representation learning stage and the clustering stage. In contrast, MiCE provides a unified framework to align the representation learning and clustering objectives in principled manner. See comprehensive comparison in Tab,
6 EXPERIMENTS
In this section, we present experimen- tal results demonstrate the effec- tiveness of MICE. We compare MiCE with extensive prior clustering methods and the contrastive learning based two- stage baseline on four widely adopted benchmarking datasets for clustering. in-
Table 2: Statistics of the datasets.
Dataset
Images
Clusters
Image Size
CIFAR-10
60,000
10
32 x 32 x 3
CIFAR-100
60,000
20
32 x 32 x 3
STL-10
13,000
10
96 x 96 x
cluding STL-I0 (Coates et al., 2011
ImageNet-Dog
19,500
15
96 x 96 x
CIFAR-10 (Krizhevsky et al. 2009
CIFAR- 100 (Krizhevsky et al. and ImageNet-Dog (Chang et al. 2017).
2009
The experiment settings follow the literature closely (Chang
(et al., 2017] (W et al. 2019 Ui et al. 2019 Shiran & Weinshall (2019] Darlow & Storkey (220)) and
the numbers of the clusters known in advance. The statistics of the datasets summarized in
7

---

Published as a conference paper at ICLR 2021
Epoch (12.4%)
(b) Epoch 500 (70.2%)
(c) Epoch 1000 (83.5%)
Figure Visualization of the image embeddings of MiCE on CIFAR-10 with 1-SNE. Different colors denote the different ground-trute -ruth class labels (unknown to the model). The cluster ACC is shown in the parenthesis. MiCE learns a clear cluster structure that matches the latent semantics well. Best view in color.
Tab. We adopt three common metrics to evaluate the clustering performance, namely normalized mutual information (NMI), cluster accuracy (ACC), and adjusted rand index (ARI). All the metrics are presented in percentage (%). We use 34-layer ResNet (ResNet-34) (He et al. 2016) as the backbone for MiCE and MoCo following the recent methods (Ji et al., 2019 [Shiran & Weinshall 2019) for fair comparisons. We set both temperatures and as 1.0, and the batch size as 256. The datasets, network, hyper-parameters, and training settings are discussed detailedly in Appendix
6.1 MAIN CLUSTERING RESULTS
Comparison with existing deep clustering methods. As shown in Tab. [ MiCE outperforms the previous clustering approaches by a significant margin on all datasets. The comparison highlights the importance of exploring the discriminative representations and the semantic structures of the dataset.
Comparison with the two-stage baseline. Compared to the straightforward combination of MoCo and spherical k-means, MiCE explores the semantic structures of the dataset that improve the clustering performance. From Tab. we see that MiCE consistently outperforms the baseline in terms of the mean performance, which agrees with the analysis in Sec. 5.3 Specifically, regarding ACC, improve upon the strong baseline by 8.7%, 2.7%, and 8.2% CIFAR-10, CIFAR- 1000 and BaageNet-Dogg respectively. Taking the measurement variance into consideration, our performance overlaps with MoCo only STL-10. We conjecture that the small data size may limit the performance as each expert learns from a subset of data. Nevertheless, the comparison manifests the significance of aligning the representation learning and clustering objectives believe that MiCE points out a promising direction for future studies in clustering.
unified framework, and
Visualization of the learned embeddings. We visualize the image embeddings produced by the gating network using t-SNE (Maaten & Hinton, 2008) in Fig. 2 Different colors denote the different ground-truth truth class labels. the beginning, the embeddings from distinct classes are indistinguishable. MiCE progressively refines its estimates and ends up with embeddings that show clear cluster structure. The learned clusters align with the ground-truth semanties well, which verifies the effectiveness of our method. Additional visualizations and the comparisons with MoCo are in Appendix
6.2 ABLATION STUDIES
Simplified model (Tab, 3 (left)). We investigate the gating function and the unnormalized model to understand the contributions of different components. Using simpler latent variable model often deteriorates the performance. (1) With uniform prior, the experts would take extra efforts to become specialized in set of images with shared semantics. (2 & 3) The teacher embedding Vs., is pushed to be close to all expert prototypes at the same time. may be difficult for the simplified expert to encode the latent semanties while being discriminative. (4) The performance drop shows that the class-level information is essential for the image embeddings to capture the semantic structures the dataset, despite the learned representations still discriminative between instances. Without the
8

---

Published as a conference paper at ICLR 2021
Table 3: Ablations of MiCE on the probabilistic model (left) and different ways of learning the gating and expert prototypes (right). Each row shows the ACC (%) on CIFAR-100 when applying the single change MICE. The assumptions are detailed in the Appendix C
CIFAR-100
CIFAR- -00
(1) A3 ( (p(,((x.) 1/K)
40.7
No analytical update on μa Eq. 13
21.3
(2) A4 (Single output layer)
39.3
(b) No gradient update
41.0
(3) A3 + A4
33.6
(c) Initialize w with uniform distribution
41.0
(4) A5 (Discard class-level information)
17.0
(d) Optimize with gradient
42.0
MiCE (Ours)
42.2
MiCE (Ours)
42.2
term, the learned embeddings are mixed up and scattered over the embedding space without a clear cluster structure.
update rules (Tab. (right)). (righ)(righ)), We also conduct ablation studies to gain insights into the different ways of handling the gating and expert prototypes. We see that (a) without Eq. (1).. we may be stuck in bad local optima. As mentioned in Sec. Sec.5.2], a possible reason that we are using the same learning rate for all network parameters and prototypes (Sculley 2010 Yang et al. (017). but tuning separate learning rates for each prototype is impractical for unsupervised clustering. Hence, we derive the analytical update to tackle the issue. As for (b), it shows that the current gradient update rule avoids the potential inconsistency between the expert prototypes and the teacher embeddings during the mini-batch training. Lastly, as discussed in Sec.(5.2) comparing using (c) uniformly initiated gating prototypes projected onto the unit sphere, utilizing the means of MMD slightly improves performance. This also bypasses the potential learning rate issue that may appear in (d).
Prototypes
7 CONCLUSION
We present a principled probabilistic clustering method that conjoins the benefits of the discriminative representations learned by contrastive learning and the semantic structures introduced by the latent mixture model in unified framework. With a divide-and-conquer principle, MiCE comprises an input-dependent gating function that distributes subtasks to one or few specialized experts, and K experts that discriminate the subset of images based instance-level and class-level informa- tion. To address the challenging inference and learning problems, we present a scalable variant of Expectation- Maaoomizaaiiiiiionn (EM) algorithm, which maximizes the ELBO and is free from any other loss or regularization terms. Moreover, we show that MoCo with spherical k-means, one of the two-stage baselines, is special case of MiCE under various assumptions. Empirically. MiCE outperforms extensive prior methods and the strong two-stage baseline by a significant margin on several benchmarking datasets.
For future work, one may explore different learning pretext tasks that potentially fit the clustering task, other than the instance discrimination one. Also, would be an interesting and important future work to include dataset with a larger amount clusters, such as ImageNet. Besides, being able to obtain semantically meaningful clusters could be beneficial weakly supervised settings (Zhou 2018 where quality labels are scarce.
ACKNOWLEDGEMENTS
The authors would like to thank Tianyu Pang and Zihao Wang for the discussion and the reviewers for the valuable suggestions. This work was supported by NSFC Projects (Nos. 62061 1 136001, 61620106010, 62076145), Beijing NSF Project (No. JQ19016), Beijing Academy of Artificial Intelligence (BAAI), Tsinghua- for Guo Qiang. Tiangong Institute for Intelligent Computing, and the NVIDIA NVAIL Program with GPU/DGX Acceleration. C. Li was supported by the fellowship of China postdoctoral Science Foundation (2020M680572), and the fellowship of China national postdoctoral program for innovative talents (BX20190172) and Shuimu Tsinghua Scholar.
Joint Research Program, grant from Tsinghua Institute

---

Published as a conference paper at ICLR 2021
REFERENCES
Philip Bachman, Devon R. Hjelm, and William Buchwalter. Learning representations by maximizing mutual information across views. Advances Neural Information Processing Systems (NeurIPS), pp. 15509-15519, 2019.
Yoshua Bengio. Pascal Lamblin, Dan Popovici, and Hugo Larochelle. Greedy layer-wise training of deep networks. Advances Neural Information Processing Systems (NeurIPS), pp. 153-160, 2006.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsuper- vised learning of visual features. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 132-149, 2018.
Jianlong Chang, Lingfeng Wang, Gaofeng Meng. Shiming Xiang, and Chunhong Pan. Deep adaptive image clustering. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), pp. 5879-5887, 2017.
Shlomo E. Chazan, Sharon Gannot, and Jacob Goldberger. Deep clustering based on mixture of autoencoders. In 2019 IEEE 29th International Workshop on Machine Learning for Signal Processing (MLSP). pp. 1-6. IEEE, 2019.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International Conference on Machine Learning (ICML), pp. 1597-1607. PMLR, 2020.
Li Chongxuan, Max Welling, Jun Zhu, and Bo Zhang. Graphical generative adversarial networks, In Advances in Neural Information Processing Systems (NeurIPS), pp. 6069-6080, 2018.
Adam Coates, Andrew Ng. and Honglak Lee. An analysis of single-layer networks in unsupervised feature learning. In Proceedings of the Fourteenth International Conference on Artificial Intel- ligence and Statistics (AISTATS), pp. 215-223 JMLR Workshop and Conference Proceedings, 2011.
Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with reduced search space. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, pp. 702-703, 2020.
Luke Nicholas Darlow and Amos Storkey. Dhog: Deep hierarchical object grouping. arXiv preprint wwXiv:2003.0882. 2020.
Arthur P Dempster, Nan M Laird, and Donald Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39(1): 1-22, 1977.
Jia Deng, Wei Dong, Richard Socher, Li-jia Li, Kai Li, and Fei-fei Li. Imagenet: A large-scale hierarchical image database. Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 248-255 2009.
Inderjit S Dhillon and Dharmendra S Modha. Concept decompositions for large sparse text data using clustering. Machine Learning, pp. 143-175, 2001.
Nat Dilokthanakul, Pedro AM Mediano, Marta Garnelo, Matthew CH Lee, Hugh Salimbeni, Kai Arulkumaran, and Murray Shanahan. Deep unsupervised clustering with gaussian mixture varia- tional autoencoders. arXiv preprint a61iv: /. 1.02648, 2016.
Alexey Dosovitskiy, Philipp Fischer, Tobias Jost Springenberg, Martin Riedmiller, and Thomas Brox. Discriminative unsupervised feature learning with exemplar convolutional neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), pp. 1734-1747, 2015.
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 (ICCV), pp. 5736-5745, 2017.
10

---

Published as a conference paper at ICLR 2021
Michael Gutmann and Aapo Hyvärinen. conte-con estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 297-304, 2010.
Philip Haeusser, Johannes Plapp, Vladimir Golkov, Elie Aljalbout, and Daniel Cremers. Associative deep clustering: Training classification network with no labels. In German Conference on Pattern Recoggittonn (GCPR), pp. 18-32. Springer, 2018.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings the IEEE conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask r-cnn. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), pp. 2961-2969, 2017.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 9729-9738, 2020.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge neural network. arXiv preprint arXiv:1503.0255 2015.
Kurt Hornik, Ingo Feinerer, and Martin Kober. Spherical k-means clustering. Journal of Statistical Software, 050(1): 1-22,, 2012.
Weihua Hu, Takeru Miyato, Seiya Tokui, Eicchi Matsumoto, and Masashi Sugiyama. Learning discrete representations via information maximizing self-augmented training. In Proceedings of the 34th International Conference on Machine Learning (ICML), pp. 1558 1988-567. JMLR. org, 2017.
Jiabo Huang, Shaogang Gong, and Xiatian Zhu. Deep semantic clustering by partition confidence maximisation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 8849-8858, 2020.
Robert A Jacobs, Michael I Jordan, Steven J Nowlan, and Geoffrey E Hinton. Adaptive mixtures of local experts. Neural Computation, 3(1):79-8)) 87, 1991.
Xu Ji, João Henriques, and Andrea Vedaldi. Invariant information clustering for unsupervised image classification and segmentation. In Proceedings of the IEEE International Conference Computer Vision (ICCV), pp. 9865-9874, 2019.
Zhuxi Jiang, Yin Zheng, Huachun Tan, Bangsheng Tang, and Hanning Zhou. Variational deep embed- ding: An unsupervised and generative approach to clustering. arXiv preprint 1rXiv: 2016.
Diederik P Kingma and Max Welling. arXiv:1312.61 2013.
Auto-encoding variational bayes.
arXiv preprint
Alexander Kolesnikov, Xiaohua Zhai, and Lucas Beyer. Revisiting self-supervised visual representa- tion learning. arXiv preprint arXiv:1901 1901009900000005, 2019.
Andreas Kopf. Vincent Fortuin, Vignesh Ram Somnath, and Manfred Claassen. -fxture-of-experts variational autoencoder for clustering and generating from similarity- representations. arXiv preprint arXiv: 19100009/0007765 2019.
Andreas Krause, Pietro Perona, and Ryan Gomes. Discriminative clustering by regularized information maximization. In Advances in Neural Information Processing Systems (NeurIPS), pp. 775-783, 2010.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, 2009.
Junnan Li, Pan Zhou, Caiming Xiong, Richard Socher, and Steven CH Hoi. Prototypical contrastive learning of unsupervised representations. arXiv preprint arXiv: 200.,9000..4966,,, 2020.
11

---

Published as a conference paper at ICLR 2021
Xiaopeng Li, Zhourong Chen, K. M. Leonard Poon, and L. Nevin Zhang. Learning latent superstruc- tures in variational autoencoders for deep multidimensional clustering. International Conference on Learning Representations (ICLR), 2019.
Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28(2): 129-137, 1982.
Zhuang Ma and Michael Collins. Noise contrastive estimation and negative sampling for conditional models: Consistency and statistical efficiency. arXiv preprint
2018.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research (JMLR), 9(Nov)22599-2605 2008.
Geoffrey McLachlan and David Peel. Finite mixture models. John Wiley Sons, 2004.
Sudipto Mukherjee, Himanshu Asnani, Eugene Lin, and Sreeram Kannan. Clustergan: Latent space clustering in generative adversarial networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33. pp. 4610-4617, 2019.
Chuang Niu, Jun Zhang, Ge Wang, and Jimin Liang. Gatcluster: Self-supervised gaussian- attention network for image clustering. In European Conference on Computer Vision (ECCV), pp. 735-751. Springer, 2020.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint 1rXiv:/807.03746 2018.
Tianyu Pang, Chao Du, and Jun Zhu. Max-mahalanobis linear discriminant analysis networks. In International Conference Machine Learning (ICML), pp.
PMLR, 2018.
Tianyu Pang. Kun Xu, Yinpeng Dong. Chao Du Ning Chen, and Jun Zhu. Rethinking softmax cross-
entropy loss for adversarial robustness. International Conference on Learning Representations (ICLR), 2020.
Deepak Pathak, Philipp Krähenbühl, Jeff Donahue, Trevor Darrell, and Alexei Efros. Context encoders: Feature learning by inpainting. Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 2536-2544, 2016.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep con- volutional generative adversarial networks. International Conference Learning Representations (ICLR), 2015.
Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: Towards real-time object detection with region proposal networks. In Advances Neural Information Processing Systems (NeurIPS), pp. 91-99, 2015.
Florian Schroff. Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pp. 815-823, 2015.
David Sculley. Web-scale k-means clustering. In Proceedings the 19th International Conference on World Wide Web (WWW), pp. 1177-1178, 2010.
Guy Shiran and Daphna Weinshall. Multi-modal deep clustering: Unsupervised partitioning of images. arXiv preprint arXiv:1912.02678, 2019.
Padhraic Smyth. Model selection for probabilistic clustering using cross-validated likelihood. Statis- tics and computing, 10(1):63-72, 2000.
Antti Tarvainen and Harri Valpola. Mean teachers are better role models: Weight-averaged consis- tency targets improve semi-supervised deep learning results. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1195-1204, 2017.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. arXiv preprint arXiv: (tt:::906.05500 05849 2019.
12

---

Published as a conference paper at ICLR 2021
Tsung Wei Tsai, Chongxuan Li, and Jun Zhu. Countering noisy labels by learning from auxiliary clean labels. arXiv preprint 1.0i::990..13300 2019.
Wouter Van Gansbeke, Simon Vandenhende, Stamatios Georgoulis, Mare Proesmans, and Luc Van Gool. Scan: Learning classify images without labels. In European Conference on Computer Vision (ECCV), pp. 268-285. Springer, 2020.
Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, and Pierre-Antoine Manzagol. Stacked denoising autoencoders: Learning useful representations in deep network with local denoising criterion. Journal of Machine Learning Research (JMLR), 1 11(ecc::331133408 2010.
CF Jeff Wu. On the convergence properties of the em algorithm. The Annals of statistics, pp. 95-103, 1983.
Jianlong Wu, Keyu Long, Fei Wang, Chen Qian, Cheng Li, Zhouchen Lin, and Hongbin Zha. Deep comprehensive correlation mining for image clustering. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), pp. 8150-8159, 2019.
Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non- parametric instance discrimination. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3733-37432 2018.
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In International Conference on Machine Learning (ICML), pp. 478-487, 2016.
Bo Yang, Xiao Fu, Nicholas D Sidiropoulos, and Mingyi Hong. Towards k-means-friendly spaces: Simultaneous deep learning and clustering. In Proceedings of the 34th International Conference on Machine Learning (ICML), pp. 3861-3870. JMLR. org, 2017.
Jianwei Yang, Devi Parikh, and Dhruv Batra. Joint unsupervised learning of deep representations and image clusters. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pp. 5147-515555 2016.
Linxiao Yang, Ngai-Man Cheung, Jiaying Li, and Jun Fang. Deep clustering by gaussian mixture vari- ational autoencoders with graph embedding. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), pp. 6440-6449, 2019.
Mang Ye, Xu Zhang, Pong C Yuen, and Shih-Fu Chang. Unsupervised embedding learning via invariant and spreading instance feature. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 6210-6219, 2019.
Lihi Zelnik-Manor and Pietro Perona. Self-tuning spectral clustering. Advances in Neural Information Processing Systems (NeurIPS), pp. 1601-1608, 2004.
Dejiao Zhang, Yifan Sun, Brian Eriksson, and Laura Balzano. Deep unsupervised clustering using mixture of autoencoders. arXiv: Learning, 2017.
Richard Zhang, Phillip Isola, and A. Alexei Efros. Colorful image colorization. European Conference on Computer Vision (ECCV), pp. 649-666, 2016
Junbo Zhao, Michael Mathieu, Ross Goroshin, and Yann Lecun. Stacked what-where auto-encoders. arXiv preprint arXiv:1506.02355 2015.
Zhihua Zhou, A brief introduction to weakly supervised learning. National Science Review, 5(1): 44-53, 2018
13

---

Published as a conference paper at ICLR 2021
A INFERENCE AND LEARNING
A.1 DERIVATION OF ELBO
logp 0, 14)
log P( P 2 0. 2b.
= =Bn(Z(X,Y)
+ (xxll( X 0,
(Z X, Y)
2 L(O, 2h, 1;
log PYY, 2 X;; 0, p)
== -E(ZZ(X
X Y)
=, [Y, Z X; 0, 2/, [4]]
X)( [log (Z| Y)
N
g(zn k|x,, vn) [log p(za w + plgn 2n = 0. p1) log q(zn = -k/xn, vn))
k=
A.2 DERIVATION EQ. 13
Assumption A1. Under the hard assignment, the variational distribution is given by:
{
1, 2m argmax q(k[x, Un):
((2 Nass Vnn)
= 0, otherwise.
Assumption A2. For all possible inputs, the unnormalized model (x yue Zn) is self-normalized similar to (Wu et al. 2018), i.e., Z(xn, 2n) equals to a constant c, such that there is no need to approximate the normalization constant as well.
Here, we derive the analytical update of the expert prototypes based on ELBO. Under the Assumptions A1 and A2, we can update ft by solving the following problem:
Pk + argmax C(pek; X, Y)
N
= argmax
(izn n=1
k||x,, Un) ((kxx()) + log p(yn|xn, k; pu:) - log 6(zn = k Xnx Bn)
argmax 1a
(zn k/pen 3nd [log plyn (2,, A;; pote
n=1
Ú(zn k||xn, yn) log ((x,: Una 1:)
argmaxx
7 (xn, k)
argmax
Σ ((
k/|xn, Un) [log (xxx, Mo. k:]]
(Assumption A2)
Me
N
argmax pa
(Ezn k|Xn, 3n) [log exp Ann. + V. Ve Hx/
n=1
(En klpxn 3nd &nn.k/ VT V (n/k///T
argmax
n=1
Σ Ú(zn k||xa Un v K/AR/T
argmaxx
14

---

Published as a conference paper at ICLR 2021
subjected to the constraint that || 1. Introducing Lagrange multiplier X, then solve the Lagrangian of the objective function:
argmax X(1 14 14x
Σ ((zn k| Un Un) yn
(14)
We can get the estimates of μa and À by differentiating the Lagrangian with regards to them and setting the derivatives to zero. To be specific, for μkx, we have:
N
X(1 px) +
Σ
i(zn k//xns Mn) V Uo KMET
n=
N
-2
+
Σ
gZz = k|xn Ven O,
n=1
such that
Σn 8(zn -k|xn; Vn. Vynk
14
14
(15)
2AT
2AT
where we define fa:== : Em ((2n = k|xn;; Un I yock = Em:s,= =k Vyn for simplicity.
Similarly, by differentiating with respect X, get:
p 14 = 1.
(16)
Substituting Eq. 15 in Eq. 16)
we have:
47 Mr srx
472 |
Therefore, obtain the analytical solutions:
2T
2r
[
The last expression essentially the update for the prototypes of the experts, as presented in Eq. in the main text.
13
15

---

Published as a conference paper at ICLR 2021
A.3 PSEUDOCODE MICE
Algorithm Pseudocode MiCE a PyTorch-like style
# encoder_s encoder_t encoder_gi student, teacher, and gating network respectively
K: number of clusters; D: embedding size
# omega: gating prototypes that are fixed to the centers of MMD (KxD)
mu: expert prototypes (KxD)
# queue: dictionary as queue of V embeddings (VxKxD)
m: momentum
# tau, kappa: temperatures for the experts and gating function respectively teacher. params student.parane
initialize
mu_hat zeros((K, D))
for x in loader: load a mini-batch x with B samples
x_f axg(x)
randomly augmented version
x_v axg(x) another randomly augmented version
x_g (xg the other randomly augmented version
encoder forward(x_f) student embeddings: BxKxD = encoder_t. (orward # teacher embeddings: BxKxD
v. ddettac() no gradient to teacher embeddings
= encoder forward(x_g) # gating embeddings: BxD
v_f = einsum ""K BKD->BK", [v, f]) instance-level information
KD->BK", [v, 12normalize # class-level information v_mu einsum( ("DB,,KD~>K""""
__pos (v_f v_mu) # positive logits: BxK
queue_ f einsum B"SSSm("" BKD->BKV",
[queue. dew.cc()..looeeeee f])
queue_mu = ("orumm"",DK"2222"" [queue, 12normalize (mu)]
1_neg queue_f queue_mu. view(1, K, V) BxKxV
experts experts_logits cat vBew(B, K, 1), I_neg, dim=2) / tau BxKx(1+V)
experts Sof Smat (expert__ttt,,,,,,ss,, dim=2)(:, 0] BxK
gating = Sof tmax ("oiiiiuii BDD variational_q einsum("BK, B"-,,K""""""""" [gating, experts])
clonee), g]) / kappa) BxK
variational_q /= variational_q, sum(dim=1) # BxK
ELBO sum(variational.q * (log(gating) + log(experts) log(variational_q)
loss -ELBO
# SGD update: student and gating networks loss. backwardk)rd)) )
(encoderr params)
# momentum update: teacher network
e. params = m*encoder_t.. par..aarrss(111 (1- #emooder_s params # update the queue
enqueue (queue, v) enqueue the current mini-batch
dequeue (queue) # dequeue the earliest mini-batch
# aggregate the teacher embeddings hard_assignments mu_hat += einsum("BKD BK->KD", [v, oneHot (hard_ [hard_assil aassignn assignments)] update the expert prototypes mu mu_hat
argmax(variational.. dim=1) # Bx1
einsum: Einstein sum; cat: concatenation; oneHot: One-hot encoding; Sof tmax: Softmax function; 12normalized: Normalization with nn-m
16

---

Published as a conference paper at ICLR 2021
A.4 CONVERGENCE OF THE PROPOSED EM ALGORITHM
Theorem (Convergence of MICE). Assume that the log conditional likelihood of the observed data log pl Y X; O, sb, u1) has an upper bound, the approximated ELBO Σ(0, sb, μ. X, Y) of MiCE then upper bounded and will converge certain value C with the proposed EM algorithm.
Proof. For any given variational distribution g(zn Xx. Vn), the approximated ELBO we optimize in Eq. (II can be written as the original ELBO in Eq. (7) plus an additional term:
[(O, th, pe, Xn: Vn)
log + (Xn, Ma, Fm; 14)
(g(2nl Un bn)lpp(s pzni 2b))
Z (Xx, 2n; 0, 14)
+ (Xn; Un, Zm, 0, 14)
Z(X1, Zn; 0.
= =Bq(znleastn))
log
+ log
DKa(a(Zn (xn: Un Vn)llp(Zn xb))
Z 2(x,= Fn. 0, 1a)
2(xn, Ani 0, p4)
7(x,; Zni 0 14)
_(0, sb, pe; Nn, Yn) + Ey( X..)
log
2 (xn: 2n 0, p1)
Recall that the normalization constant is ((x:: Zn; 11)
Σ
exp (vTTnen (fn,z, pz,)) /T)
i=1
and the approximated normalization constant
2 (Xa, Zn; 14)
Σ exp (q),en (fn,en + pea)) /T),
As in Eq. (
where q is queue that stores the outputs of the teacher network as described in the main text.
If the teacher embeddings of the entire dataset the queue, then the normalization constants cancel each other and we obtain the original ELBO. In such cases, the convergence can be proved following the standard EM algorithm (Dempster al. 1977 Wu 1983).
Otherwise, we can also bound the approximated ELBO, Since that all student and teacher embeddings and expert prototypes are fy-normalized, we can bound the log ratio term independent of the choice of the queue:
2
S V Disan (fn,za + (ra) 3/T S
T
which implies
Z (xx,, 2ni 00; N exp(
and
2(x.: 1n, zn; 0 11) 2 v exp( =2
Given that they are both positive, we can get
(xx,, 2n; 0 11)
log (x Zni 0, 11)
< log N - log +
Therefore, the approximated ELBO is bounded by:
Z(xn, Zni 1,
E(0,00 4b pr Xns vn) L(O, 4/, pr Xn, Un) + B. (x..)).)) log 2(x,, 2n. 0
Logg(ynnxxee xx. O. 2.. (b,4) + log N - log
17

---

Published as a conference paper at ICLR 2021
Similar to the proof of original EM (Wu 1983), since the approximated ELBO will not decrease in expectation during training, the approximated ELBO of MiCE will converge to a certain value L
There are two remarks for Theorem 1: (1) The convergence the proposed EM relies on similar assumptions of the standard EM algorithm. (2) Due to the extra log ratio term in the approximated ELBO, will need further analysis to know the exact convergent point comparing to MiCE learning with the standard EM algorithm.
B ALGORITHM FOR GENERATING THE CENTERS OF MMD
We provide the algorithm on generating the centers of the Mux-Mahallnobis distribution (MMD) in Algorithm 2 The gating prototypes
fix to these centers during training. The algorithm closcly follows the one proposed by |ang et al. 2020). For dataset with K ground-truth classes, we will generate K centers which all , normallize in the Id space. Please kindly note that the algorithm requires K < (d + 1) (Pang et al. 2020
Algorithm 2: Algorithm to craft the gating prototypes w as the centers of MMD
Input: The dimension of each gating prototypes and the number of the clusters K. Initialization: We initialize the first prototype wi with the first unit basis vector E Rd Rest Rest of the prototypes w., & 1, are initialized with the zero vector 0f Rd
for i = 2 to K do do
for j =
Wiy [1/ 1) wi w
end
w 11
Wi
end Return: The gating prototypes (wi LK
C RELATIONS TO THE TWO-STAGE BASELINE
C.I CONTRASTIVE LEARNING
Assumption A3. The gating temperature K > oG such that for all k, the prior
1 K'
p(zn|xa)=
Vn.
Assumption A4. There is only a single output layer for both student network fe and teacher network fe respectively. The resulting embeddings are used across K expert, to be specific, for all possible cases,
4 (x,, Un k) = exp (v (f,, + (Lx)TT)
where f, = fx(x)) Rdd, V. = fo (xx) idd.
Assumption A5. The unnormalized model (b-) considers only the instance-level information such that for all possible cases,
((Xn: Bay 2n.) exp (V /T)
Theorem 2. If Assumptions A3-A5 holds, the overall output of MiCE become
exp(v T yo fn/T)
plyn xn.)
18

---

Published as a conference paper at ICLR 2021
Proof. Since we the expert
$ (n Mas 2n)
exp (v.J. (fr, + (/m)/T)
plyn Xny 2n) = Z ((xn, 2n)
(Assumption A4)
Ei= exp (v. (f, + pl 2/2))/5)
exp(vy,. T.
vn fx/T)
(Assumption A5)
Ei=l (vp (o,vvv;,/)) fn/T)
N
The overall output of MiCE is then
p(yn xx,) Σ p(zn -(pxn)p(unnn 2n 1s)
K =
p( Xens 2n = =k)
(Assumption A3)
K
exp(v V._ fn/TT
N Σ (v, fn/T)
The simplified model shown in Theorem 2 is essentially the non con-paraettric Softmax classifier used by MoCo and Inst which is also related to some recent contrastive learning methods (Ye et al. 2019)] Bachman et al., 2019). Note that InstDiisc adopts slightly different implementation in which the teacher network is identical to the student network and the loss function is based on NCE (Gutmann)
& Hyvärinen 2010). For detailed comparisons, please refer to He et al. 2020
Lemma 1. !f Assumptions A3-A5 hold, the posterior is uniformly distributed.
Proof.
p( (x,) ) (Ne, Una 2n)/ Z(Xn, 2n1) I= p(k ) (X,, Yn k)/ Z (x k) ① (Xns Un, Zna) / Xn,, =n.)
plzn Xnx Un)
(Assumption A3)
Σk o (Xn: Vn. k Xn k)
exply fn/T)
E exp(v, f,/T)
(Theorem 2)
exp(y fa/r)
k=l Lisi exp(v, f./r)
Assumption A6. The normalization constant is computationally tractable such that we can have the variational distribution being identical to the posterior distribution.
Theorem 3. Given that A3-A6 hold, p(yn = exp(vT f, L IN
L exp(v. and the
tractable version of ELBO identical to the form of InfoNCE (Oord et 2018) loss used by MoCo.
Proof.
+ (Xn: Uni zn) 2xx,, 2nd
C(0, 2b, l1, Xn. Vn) Enggen (xn. w..) [log
DKu(g(=n Xa. Un Un))lp(zn(xx)) xx.
(xn, Uni 2n)
= =log 2 (xn, kn)
(Lemma 1)
exp (V Ui.
fn/T)
llog
(Theorem 2)
exp
(v fn/T) + Σ exp (q. fn/T)
19

---

Published as a conference paper at ICLR 2021
According to Theorem 2 and 3, we see that MoCo can be viewed as special case of the proposed MiCE. In other words, they are able to learn the same representations under the same experimental setting if the above assumptions are made.
C.2 SPHERICAL K-MEANS
Theorem 4. If Assumptions A1-A4 hold, the analytical update on the expert prototypes is equivalent single-iteration spherical k-means algorithm the teacher embeddings.
Proof. Under the assumptions, the variational distribution reduces to
④ (Xn, M/ Zn
g(2n Xn; Vn)
(Assumptions A2 and A3)
Σk + (Xn, Mny k:)
exp
Waisn fn,za/ T V
Un.on Mzn/T
Ek=1 exp you Prik/T / + V.
K
"nni AMk/
exp (v Un fn/T + V Wintee//T)
(Assumption A4)
k= exp (v. Un Fn/T + V. pe//T)
exp (v Men /T)
Ek=1 exp (T..M/T)
such that the hard cluster assignment is determined bt the cosine similarity between the teacher embedding and the expert prototypes:
{ 1, if 2, argmax q(k|/xns Un) argmax
Un Mk.
(<mm1xx, Un)
0, otherwise.
With the simplified expert model, we follow the previous discussion on Eq. [4 and get the Lagrangian of the objective function:
X(1 Mhl Mx) + Σ a(z k|x,s Nn. ME/T.
argmaa
The analytical solution is therefore:
p Σ
k x/ Urr Ven
14
|
where the cluster assignment step and prototype update rule are the same the spherical k-means.
D EXPERIEMENT SETTINGS
We mainly compare with the methods that are trained from scratch without using the pre-training
model and the experiment settings follow the literature closely (Chang et al. 2017 Wu al. 2019
et al. 2019 Shiran & Weinshall 2019 Darlow & Storkey 2020). For CIFAR-IO. 10, CIFAR 100. and
STL-10. 10, all the training and test imgges are jointly utilized, and the 20 superclasses of CIFAR- 100
are used instead of the fine labels. The 15 classes dog images are selected from the ILSVRC2012
1K (Deng et al. 2009) dataset and resized to 96 x 96 x 3 to form the ImageNet-Dog dataset (Cang
20

---

Published as a conference paper at ICLR 2021
et al., 2017 Wu et al. 2019). Note that the numbers of the clusters are known in advance in Chang et al. (201 7): Ji et al. (019);; Wu et al. (2019); Shiran & Weinshall (2019). The statistics of
the datasets summarized in Tab. 2 We adopt three common metrics to evaluate the clustering
performance, namely normalized mutual information (NMI), cluster accuracy (ACC), and adjusted rand index (ARI). All the metrics are presented in percentage (%)
Regarding the network architecture, MiCE mainly use a ResNet-34 (He et al. 2016) as the backbone following the recent methods (Ji et al. 2019 Shiran & Weinshall 2019 for fair comparisons. For the gating network, the output layer is replaced by a single fully connected layer that generates a fg-normalized embeddings in R. 122 As for the student network, uses the same ResNet-34 backbone as the gating network and includes K more fully connected layers which map the images to K embeddings. Therefore, the parameters of student and gating networks are shared except for the output layers. The teacher network for is the exponential moving average (EMA) version of the student network Se. which stabilizes the learning process (He et al. 2020] Tarvainen & Valpola, 2017).
The update rule follows O' + m0' + (1 m) with m [0,1) 1) being the smoothing coefficient. In practice, we let m = 0.999 following MoCo. Since the images of CIFAR-1O and CIFAR- -00 smaller than ImageNet images, following (Chen et al., 2020),
replace the first 7x7 Conv of stride with a 3x3 Conv of stride 1 for all experiments on CIFAR- 10 and CIFAR- 100. The first max-pooling operation is removed as well (Wu et al. 2018 Chen et al. 2020 Ye al. 2019). Please kindly note that if the first max max-pooling operation is not removed, MiCE can still achieve 83.6% ACC
on CIFAR-10. 10. For fair comparisons, MoCo also uses a ResNet-34 with 228dimensionnll output and follows the same
settings as MiCE.
As is often infeasible tune the hyper-parameters with validation dataset in real-world clustering tasks (Ghasedi Dizaji et al. (017)) we set both temperatures T and k as 1.0. The queue size v is set to 12800 for STL-10 because of the smaller data size and 16384 for the other three datasets. The data augmentation follows MoCo closely. Specifically. before passing into any of the embedding networks, images are randomly resized and cropped to the same size, followed by random gray-scale, random color jittering, and random horizontal flip. For a fair comparison, MoCo in the two-stage baseline also uses a ResNet-34 backbone. For all datasets, we use a batch size equals to 256. Note that the data augmentation strategy is critical to contrastive learning methods and MiCE, and we follow the one used by MoCo for fairness.
In terms of the optimization details, we use stochastic gradient descent (SGD) our optimizer on the negative ELBO. We set the SGD weight decay as 0.0001 and the SGD momentum as 0.9 (He) et al. 2020). The learning rate is initiated as 1.0 and is multiplied by 0.1 three different epochs. For different datasets, the number of training epochs is different to accommodate the data size to have a similar and reasonable training time. For CIFAR-10/100) we train for 1000 epochs in total and multiply the learning rate by 0.1 at 480, 640, and 800 epochs. For STL-10, the total epochs are 6000 and the learning rate is multiplied by 0.1 at 3000, 4000, and 5000 epochs. Lastly, for ImageNet-Dogg the total epochs are 3000 and the learning rate is multiplied by 0.1 at 1500, 2000, and 2500 epochs. Also, the learning rate for expert prototypes is the same as the one for network parameters. All the experiments are trained on a single GPU.
For all experiment settings in the main text, we follow the recent methods (Wu et al. 2019 Ji et al.. 2019 [Shiran& & Weinshall (019) closely where the models are trained from scratch. The setting is different from some of the methods including VaDE ІJiang et al. 2016), DGG (Yang et al. 2019), and LTVAE (Li et al. 2019) from two aspects. Firstly, we do not any form of the pre- model. Secondly, we focus on a purely unsupervised setting. In contrast, VaDE (Jiang et al. 2016) and DGG (Yang et al. 2019) use supervised pre-trale -rained model ImageNet for 10. For faimess, in the original submission, we compare to many previous methods that use the same settings.
E ADDITIONAL EXPERIMENTS AND VISUALIZATIONS
Posterior distribution and cluster predictions. From the left side of Fig. B we can see that in the initial stage (epoch 1), MiCE is yet certain about the cluster labels of any give images. At the end of the training (epoch 1000). the major values of the approximated posterior distribution fall in the [0, 0.1) interval, indicating that the model is confident that images do not belong to those clusters.
21

---

Published as a conference paper at ICLR 2021
Hoa Skige indal Sage
30003
4893
200000
10009
0.8
0.2
1.0
Probect
Cluewerrde
Figure 3: The histogram of (left) approximate posterior distributions of MiCE the initial and final stage of training and (right) the predicted cluster labels obtained during testing. Here, we train and evaluate the model using CIFAR-I0 which has 10 classes and 60,000 images. We divide the probability distribution into 10 discrete bins. Best view color.
After training, the learned model is able to generate sparse posterior distributions. The predicted cluster labels are also balanced across different clusters, which is shown the right side of Fig.
Visualization of embeddings of MiCE and MoCo. We present the t-SNE visualization of the embeddings learned by MiCE and MoCo in Fig. 4 and Fig. 5 to investigate whether the cluster structure and the latent semantics are captured by the models. The two figures differ the way we color the datapoints.
In Fig. 44] different colors represent different cluster labels predicted by the clustering methods. We get the predicted cluster labels of MiCE based on the hard assignments using the posterior distributions. The cluster labels for MoCo are the outputs of the spherical k-means algorithm. MiCE can learn a distinct structure the end of the training where each expert would mainly be responsible for one cluster. By comparing Fig. 4 (c) and (f), we can see that the boundaries between the clusters learned by spherical k-meaas do not match the structure learned by MoCo well. The divergence caused by the independence of representation learning and clustering. MiCE solves the issue with a unified framework.
In Fig. [5] the datapoints are colored according to the ground-truth class labels that are unknown to the models. Fig.5(cc the cluster structure is highly aligned with the underlying semantics. Most of the clusters are filled with images from the same classes while having some difficult ones lying mostly on the boundaries. This verifies that the gating network learns to divide the dataset based on the latent semantics and allocates each of the images to one few experts. Please kindly note that we use the embeddings from the gating network instead of the student network for simplicity since the embeddings
from the same output head. In contrast, the cluster structure learned by MoCo does not align the semantics well. For all the above t-SNE visualizations, we set the perplexity hyper-parameter 200.
Training time. We present the training time of MiCE and MoCO on CIFAR-10. It takes around 17 and 30 hours train MoCo and MiCE for 1000 epochs, respectively. For all four datasets, experiments are conducted on single GPU (NVIDIA GeForce GTX 1080 Ti).
Extra ablation studies on updating expert prototypes. A bad specification of the expert prototypes can lead to a bad result if it is not properly handled. Specifically, in Tab. (3) (a), we see that the ACC on CIFAR-10 is only 21.3%. We empirically verify two principled methods that solve the issue: (1) extra end-of-epoch training only fu with stochastic gradient ascent or (2) using Eq. (13).
The first method is used as follows. At the end of each epoch, we update μ while fixing the network parameters until the pre-defined convergence criteria are met. The convergence can be determined based on either the norm of the prototypes or the change of the objective function. To control the training time, stop the update at the current epoch once iterate through the entire dataset 20 times. We discover that with additional training, we can achieve 42.3% ACC. The result shows that with proper update μa, the proposed model can identify semantic clusters with stochastic gradient ascent alone. However, it requires more than 10 times of training time (around 394 hours).
The above discussions manifest the benefits of using the Eq. (13) which is derived based on the same objective function. With the prototypical update, we can achieve similar results with minimal computational overhead. On average, achieve 42.2% ACC CIFAR- R-100 as shown in Sec.
22

---

Published as a conference paper at ICLR 2021
(a) MiCE (epoch 1)
(b) MICE (epoch 500)
(c) MiCE (epoch 1000)
(d) MoCo (epoch 1)
(e) MoCo (epoch 500)
(f) MoCo (epoch 1000)
Figure 4: Visualization of the image embeddings of MiCE (upper row) and MoCo (lower row) on CIFAR-10 with t-SNE. Different colors correspond to various cluster labels obtained based on the posterior distribution (MiCE) or spherical k-means (MoCo). The embeddings of MiCE depict a clear cluster structure, as shown in (c). contrast, the structure in (f) ambiguous for a large portion of data and it does not match the cluster labels well.
(a) MiCE (epoch 1)
(b) MICE (epoch 500)
(c) MICE (epoch 1000)
(d) MoCo (epoch
(c) MoCo (epoch 500)
(f) MoCo (epoch 1000)
Figure 5: Visualization of the image embeddings of MiCE (upper row) and MoCo (lower row) on CIFAR-10 with t-SNE. Different colors denote the different ground-truth class labels (unknown to the model). Comparing to MoCo, the clusters learned by MiCE better correspond with the underlying class semantics.
23

---

Published as a conference paper at ICLR 2021
Table Comparing the cluster accuracy ACC (%) of SCAN Van Gansbeke et al. 2020) and MiCE on CIFAR- 10. Following SCAN, we show the data augmentation strategy in the parenthesis if it is different from the one MiCE and MoCo use. "SimCLR" indicates the augmentation strategy used in (Chen et al.) 2020), and "RA" is the RandAugment (Cubuk et 20.0). For fair comparison, the first sector compares MiCE to SCAN without the self-labeling step, and the second sector compares SCAN with self-labeling to MiCE with pre-training.
Methods/Datasee
CIFAR-10 10
SCAN-Loss (SimCLR)
78.7
SCAN-Loss (RA)
81.8
MiCE (Ours)
83.4
SCAN-Loss (SimCLR) Self-Labeling (SimCLR)
10.0
SCAN-Loss (SimCLR) + Self-Labeling (RA)
87.4
SCAN-Loss (RA) Self-Laheling (RA)
87.6
MiCE pre-training MiCE (Ours)
89.3
MiCE pre-training MiCE (RA) (Ours)
88.3
MiCE pre-training MiCE (SimCLR) (Ours)
90.3
Comparing MiCE to SCAN (Van Gansbeke et al. 2020 We provide additional experiment results to compare with SCAN (Vnn Gansbeke al. 2020) that unsupervised pre-training under a comparable experiment setting. As SCAN adopts a three-step training procedure, we think that will provide additional insights by comparing MiCE SCAN at the steps after the pre-training step. The detail results on CIFAR-10 are presented in Tab.
Firstly, we focus on SCAN with two steps of training. MiCE outperforms SCAN with two steps of training. SCAN obtains 78.7% and 81.8% on CIFAR-10 with the SimCLR augmentation and RandAugment, respectively. In contrast, MiCE can get 83.4% despite we are using a weaker
augmentation strategy following MoCo (He et al. 2020 and InstDisc (Wu et al. 2018).
Since SCAN involves pre-training using SimCLR (Chen et al. 2020 takes additional advantages when directly comparing to other methods without pre-training. Thus, we fine-tune the MiCE model with the same training protocol described in Appendix (except the learning rate can be smaller). We discover that MiCE can obtain higher results and outperforms SCAN, as shown in the second sector Tab. 4 To specific, in the fine-tuning stage, we load the network parameters from the pre-trained model and smaller initial learning rate of 0.1 with all the other settings remain the same. We show the augmentation strategy in the parenthesis if we use a different one from the pre-training stage. For the RandAugment (Cubuk et al. 2020h. follow the implementation (and sper-parameters) based on the public code provided by SCAN. As mentioned in Van Gansbeke et al.] (2020), the self-labeling stage requires shift in the augmentation, otherwise, it will lead degenerated solution. In contrast, MiCE with pre- training is not prone to degeneracy can get comparable or better performance than SCAN regardless of the choice of the augmentation strategy.
F ADDITIONAL DISCUSSIONS
The number of the experts. In the cases where the number of the experts L differs from the number of ground- -ruth clusters K, the model will partition the datasets into subsets instead K. Even though the number of experts is currently tied with K, it is not drawback and does not prevent us from applying to the common clustering settings. Also, MiCE does not use additional knowledge comparing to the baseline methods. If the ground-truth K is not known, we may treat K as a hyper- parameter and decide K following the methods described in |myth (2000); McLachlan Peel (2004). which is worth investigating in the future.
Overclustering. The overclustering technique Di et al. 2019) is orthogonal to our methods and can be applied with minor adaptations. However, may require additional ensure overclustering improves the results. From the supplementary file provided by IIC (Ji et al. 2019), see that the numbers of clusters (for overclustering) are set differently for different datasets.
tuning to
24

---

Published as a conference paper at ICLR 2021
Despite overelustering is interesting technique, would like to highlight the simplicity of the current version of MiCE.
Similarity between the two set of prototypes. We do not expect the two prototypes to be similar even though their dimensions are the same. In fact, they have different aims: the gating ones aim to divide the datasets into simpler subtasks for the experts, while the expert ones help the expert to solve the instance discrimination subtasks by introducing the class-level information. Therefore, the derived ELBO objective does not encourage the two sets of prototypes to be similar or maintaining clear correspondence between them.
Empirically, calculate the cosine similarity between any pair of μ and w. The absolute values get are less than 0.25, which showed that they are not similar. If we force them to be similar during training. the performance may be negatively affected due to the lack of flexibility.
25


Reviews:
[{"review_id": "y6ae8EP3Q4a", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents an image clustering methodology based on Mixture of Experts (MoE) for image clustering. \nAlthough MoE has been proposed for supervised learning problems, the authors exploit the instance discrimination framwork to apply the MoE idea for image clustering. \n\nThis is a novel aspect of the proposed method.\n\nThe MoCo framework (unsupervised) for contrastive learning of image representations is employed to define a mixture of MoCo experts model where each expert additionally includes a cluster prototype vector to facilitate clustering.\n\nThis unified approach for simultaneous MoCo-based representation learning and clustering seems to provide better results that the two-stage approach of first applying MoCo and then using k-means clustering on the obtained representations.\n\nA probabilistic formulation of the method is presented, along with a training approach based on EM algorithm for likelihood maximization.\n\nThere are several concerns related to presentation and clarity.\n\nComments to be addressed:\n1) It would be easier to understand the contribution of the paper, if the MoCo approach were initially described and then the proposed method was presented as a mixture of MoCo experts. The paper in its current form (section 3) is difficult to follow, since several MoCo ideas are mentioned (eg. student and teacher network,  EMA, etc) without been intuitively explained.\n2) In section 3 that describes the method, there is no reference about image augmentation, although it is a critical aspect of the approach. Use of image augmentation is only mentioned at the end of the Appendix.\n3) A pseudocode descibing the exact steps of the proposed method is imperative.\n4) Due to some approximations made, is it possible to prove convergence of the proposed EM procedure?\n5) Gating prototypes \\omega remain fixed during training. It is important to provide more details on the MMD method used to specify them.\n6) It seems strange that, while \\omega are specified using embeddings from the the initial network g(x), they are not involved during training.\n7) A bad specification of \\omega is expected to have strong negative influence on the results that cannot be recovered.\n8) What is the size of minibatch B? (eq. (10)).       \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ae8ZpVmVTQ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary and Contributions: Inspired by the mixture of experts, authors propose an image clustering algorithm using a mixture of contrastive experts where, each of the conditional models is an expert in discriminating a subset of instances based on contrastive learning.  To this end they  use a gating function to partition an unlabeled dataset into subsets according to the latent semantics and discriminative distinct, where the gating function performs a soft partitioning of the dataset\nbased on the cosine similarity between the image embeddings and the gating prototypes. The authors carry out experiments on four widely adopted natural image datasets to evaluate the performance of the method in these tasks and compare it to competing methods and baselines.\n\n\nCorrectness and Clarity: The paper is well-written, with informative figures and tables. The paper presents the idea in a clear and straight-forward manner, and is solidly built on top of the current literature. Authors convincingly tested the method with multiple SOTA and baseline and the results look correct to me.  \n\nReproducibility: The details of the experiments, implementation, and the public datasets are included in the paper. Thanks also for sharing the code.\n\nAdditional Feedback and Suggestions:  Since the goal of the paper is image clustering, providing some visual results is appreciated. Also, I am curious to see the performance of the method when we have large number of clusters in our dataset e.g. ImageNet. \n\nDecision: The idea of using  a scalable variant of the Expectation-Maximization (EM) algorithm to help with the nontrivial inference and learning problems caused by the latent variables seems interesting to me.  And overall, the technical novelty together with the fine evaluation are good enough for ICLR, in my opinion.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "7tmry5-AJSk", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: Authors present “mixture of experts” type of method to solve a clustering with unsupervised learning problem. Method is called as Mixture of Contrastive Experts (MiCE) which uses contrastive learning as a base module and combines it with latent mixture models. Authors develop a scalable algorithm for MiCE and empirically evaluate the proposed method for image clustering. \n\nRecommendation: I am tending towards accepting the paper (rating 6). Reason for the acceptance is the novel method supported by empirical evidence. Reason for score not being too high are some weaknesses mentioned in the details later. \nStrengths: \n1) Authors address an image clustering algorithm given number of clusters. Submission is clear, technically correct and present novel findings. \n2) The proposed approach is well motivated. \n\nWeakness/Questions:\n1) All recent papers have ImageNet-10 as one of the five common datasets [1-2]. Why was it omitted in the current paper? \n2) It looks like method is very tied up with MoCo and developed on top of it. Is there an easy/quick way to use other backbones like SimCLR instead of MoCo and still preserve all the steps in the method?\n3) Why were images in ImageNet-Dog resized to 96 x 96 x3?\n4) Almost all prior methods and proposed method MiCE assume that a number of clusters are known (which shouldn’t ideally be the case). But it looks like the proposed method MiCE uses the information in a better way by assuming number of experts = number of clusters. Can one use more or less number of experts (than number of clusters K) and still partition the sample data into K clusters? Can one easily use over clustering as presented in IIC? \n5) How does the proposed method MiCE fare in terms of computation complexity when compared to MoCo? \n6) How do \\mu, w (the expert and gating prototypes) differ during the training? Since the prediction value is the sum of the expert probability weighted by the gating function, one would expect the gating prototypes and expert prototypes to be similar? Is this true? How is consistency maintained (is there a clear correspondence, prototype 1 in expert matches to prototype 2 in gating function)?\n7) Can authors elaborate more about the usage of Max-Mahalanobis distribution (MMD) and how exactly does it solve the issue of “unnecessary difficulties in partitioning the dataset if some of them are crowded together.”\n8) “Since the images of CIFAR-10 and CIFAR-100 are smaller than ImageNet images, following (Chen et al., 2020), we replace the first 7x7 Conv of stride 2 with a 3x3 Conv of stride 1 for all experiments on CIFAR-10 and CIFAR-100. The first max-pooling operation is removed as well. For fair comparisons”: Is removing  first max-pooling operation standard practice? Is there any performance loss when max pooling is not removed? \n\nMinor:\n1) What does NMI and ARI of > 1 mean? Don’t they have to be in the range of [0,1]? \n\n\n[1] Huang, Jiabo, Shaogang Gong, and Xiatian Zhu. \"Deep Semantic Clustering by Partition Confidence Maximisation.\" In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8849-8858. 2020.\n[2] Wu, Jianlong, Keyu Long, Fei Wang, Chen Qian, Cheng Li, Zhouchen Lin, and Hongbin Zha. \"Deep comprehensive correlation mining for image clustering.\" In Proceedings of the IEEE International Conference on Computer Vision, pp. 8150-8159. 2019. \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1ChMTRII-Nw", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes to use mixture of experts for image clustering.  The individual expert for each cluster adopts an instance discrimination approach for training.  The proposed method has shown superior clustering performance compared to an extensive number of clustering methods on a reasonable collection of data sets.\n\nThough the overall idea of the proposed method is clear, the paper does not seem to explain some technical details clear enough.  In Equation, the probability P(Y,Z|X) does not seem to be correct. The product term over k appears to be valid only when it uses a hard assignment, i.e. P(z_n|x_n) = 1 for exactly one of the clusters.  The student and teacher embeddings are used before Equation 4 but have not been explained until a later part of the paper.  It is also unclear why an instance discrimination approach would lead to a better clustering performance.\n\nAlthough an extensive number of clustering methods have been included in the experiments, it has omitted some strong competitors including Variational Deep Embedding (Jiang et al. 2016), Latent Tree Variational Autoencoder (Li et al. 2019), Deep clustering via a Gaussian mixture VAE with Graph embedding (Yang et al. 2019), etc.  Those methods appear to perform better on some of the data sets.  For example, those methods have been reported to yield over 85% of accuracy on the STL-10 data set but the proposed method yields only 75% on the same data set.  It would be better if the paper could include those methods in the experiments or justify the selection of baseline methods.\n\nOverall, the proposed method appears to be an interesting combination of some existing methods.  However, the technical details need better clarity and the experiments should include more relevant methods.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thanks for your submission to ICLR!

This paper considers a novel unsupervised image clustering framework based on a mixture of contrastive experts framework.  Most of the reviewers were overall positive about the paper.  On the positive side, they noted that the paper had an interesting idea, was well motivated, written well, and had solid results.  Also, the authors provided detailed and useful responses to the reviews, which further strengthened the case for accepting the paper.  On the negative side, one reviewer felt that the paper seemed a bit preliminary and its presentation could improve.  Also, there was some concern about missing comparisons / discussion to previous work (including from a public comment) or data sets (e.g. ImageNet-10).  Again, the authors responded well to these concerns.

Given that the overall response was quite positive with the paper, I'm happy to recommend accepting it.


Decision: Accept (Poster)