A Probabilistic Approach to Constrained Deep Clustering
Authors: Laura Manduchi
Kieran Chin-Cheong
Holger Michel
Sven Wellmann
Julia E Vogt
Venue:  (2021)
Keywords: constrained clustering
semi-supervised representation learning
generative model
deep learning

Abstract: Clustering with constraints has gained significant attention in the field of semi-supervised machine learning as it can leverage partial prior information on a growing amount of unlabelled data. Following recent advances in deep generative models, we derive a novel probabilistic approach to constrained clustering that can be trained efficiently in the framework of stochastic gradient variational Bayes. In contrast to existing approaches, our model (CVaDE) uncovers the underlying distribution of the data conditioned on prior clustering preferences, expressed as pairwise constraints. The inclusion of such constraints allows the user to guide the clustering process towards a desirable partition of the data by indicating which samples should or should not belong to the same class. We provide extensive experiments to demonstrate that CVaDE shows superior clustering performances and robustness compared to state-of-the-art deep constrained clustering methods in a variety of data sets. We further demonstrate the usefulness of our approach on challenging real-world medical applications and face image generation.

Under review as a conference paper at ICLR 2021
A PROBABILISTIC APPROACH TO CONSTRAINED DEEP CLUSTERING.
Anonymous authors Paper under double-blind review
ABSTRACT
Clustering with constraints has gained significant attention in the field of semi- supervised machine learning as it can leverage partial prior information on a grow- ing amount unlabelled data. Following recent advances in deep generative mod- els, we derive novel probabilistic approach to constrained clustering that can be trained efficiently In contrast to existing approaches, our model (CVaDE) uncovers the underlying distribution of the data conditioned on prior clustering preferences, expressed as pairwise constraints. The inclusion of such constraints allows the user to guide the clustering process towards a desirable partition of the data by indicating which samples should or should not belong to the same class. We provide extensive experiments to demonstrate that CVaDE shows superior clustering performances and robustness compared to offe-of-thhearr deep constrained clustering methods in a variety of data sets. We further demonstrate the usefulness of our approach challenging real-world medical applications and face image generation.
the framework of stochastic gradient variational Bayes.
INTRODUCTION
The ever-growing amount of data and the time cost associated with its labeling has made clustering a relevant task in the field of machine learning. Yet, in many cases, a fully unsupervised clustering algorithm might naturally find a solution which is not consistent with the domain knowledge (Basu al. (008). medicine, for example, clustering could be driven by unwanted bias, such as the type of machine used to record the data, rather than more informative features. Moreover, practitioners often have access to prior information about the types of clusters that are sought, and principled method to guide the algorithm towards desirable configuration is then needed. Constrained clus- tering, therefore has a long history in machine learning as it enforces desirable clustering properties by incorporating domain knowledge, in the form of constraints, into the clustering objective.
Following recent advances in deep clustering, constrained clustering algorithms have been recently used in combination with deep neural networks (DNN) to favor better representation of high- dimensional data sets. The methods proposed so far mainly extend some of the most widely used deep clustering algorithms, such DEC (Xie al. 2016), to include variety of loss functions that force the clustering process to be consistent with the given constraints (Ren et al. 2019 Shukla al., 2018 Zhang et 2019b). Although they perform well, none of the above methods model the data generative process. As a result, they can neither uncover the underlying structure of the data, nor control the strength of the clustering preferences, nor generate new samples (Min et al., 2018).
To address the above issues, we propose novel probabilistic approach to constrained clustering, the Constrained Variational Deep Embedding (CVaDE), that uncovers the underlying data distribu- tion conditioned on domain knowledge, expressed in the form of pairwise constraints. Our method extends previous work in unsupervised variational deep clustering (Jiang al., 2017] Dilokthanakul al. 2016) incorporate clustering preferences Bayesian prior probabilities with varying de- grees uncertainty. This allows systematical reasoning about parameter uncertainty (Zhang et al.) 2019a), thereby enabling the ability to perform Bayesian model validation, outlier detection and data generation. By integrating prior information in the generative process of the data, our model guide the clustering process towards the configuration sought by the practitioners.
Our main contributions are as follows: (i) We propose a constrained clustering method (CVaDE) to incorporate given clustering preferences, with varying degrees of certainty, within the Variational

---

Under review as a conference paper at ICLR 2021
Auto-Encoder (VAE) framework. (ii) We provide thorough empirical assessment of our model. In particular, we show that (a) a small fraction of prior information remarkably increases the perfor- mance of CVaDE compared to unsupervised variational clustering methods, (b) our model shows superior clustering performance compared to state-of-the-art deep constrained clustering models on wide range of data sets and, (c) our model proves be robust against noise it easily incor- porate the uncertainty of the given constraints. (ii) We show that our model can drive the clustering performance towards different desirable configurations, depending on the constraints used, and successfully generates new samples on challenging real-world image data.
2 THEORETICAL BACKGROUND & RELATED WORK
Constrained Clustering. A constrained clustering problem differs from the classical clustering scenario as the user has access to some pre-existing knowledge about the desired partition of the data. The constraints are usually expressed as pairwise constraints (Wagstaff' & Cardie 2000), consisting of must-links and cannot-links, which indicate whether two samples are believed to belong to the same cluster to different clusters. Such pairwise relations contain less information than the labels used in classification tasks but are usually easier to obtain. Traditional clustering methods have been then extended to enforce pairwise constraints (Lange et al. [005). COP-KMEANS (Wagstaff et al.) 2001) and MPCK-mean (Bilenko et al., 2004) adapted the well-known K-means algorithm, while several methods proposed constrained version of the Gaussian Mixture Models (Shental ct al,, 2003 Law et al. 2004, 2005). Among them, penalized probabilistic clustering (PPC, Lu & Leen (2004) is most related to work expresses the pairwise constraints Bayesian priors over the assignment of data points to clusters. However, PPC, as well as the previous models, shows poor performance and high computational complexity high-dimensional and large-scale data sets.
Deep Constrained Clustering. To overcome the limitations of the above models, constrained clus- tering algorithms have been lately used in combination with DNNs. Hsu & Kira (2015) train a DNN to minimize the Kullback-Leibler (KL) divergence between similar pairs of samples, while Chen (2015) performs ceni-super maximum margin clustering of the learned features on a DNN. More recently, many extensions of the widely used DEC model (Xie et al.) 2016) have been pro- posed to include a variety of loss functions enforce pairwise constraints. Among them, SDEC (Ren et al.) 2019) includes a distance loss function that forces the data points with a must-link to be close in the latent space and vice-versa. C-IDEC (Zhang et al.) 2019b), uses, instead, a KL divergence loss, extending the work of Shukla et al. (2018). Other works have focused on discrim- inative clustering methods by self-generating pairwise constraints from either Siamese networks or KNN graphs (Smieja et al. (020) (Fogel et al. 2019). As none of the approaches proposed far is based on generative models, the above methods fail to uncover the underlying data distribution. Additionally, DEC-based architectures rely heavy pretraining of the autoencoder, resulting in no theoretical guarantee that the learned latent space is indeed suitable for clustering (Min et al. 2018).
VAE-based deep clustering. Many models have been proposed in the literature perform unsuper- vised clustering through deep generative models (Li et al. 2019 Yang et al. 2019 Manduchi et al., 2019 Kopf et al. 2019). Among them, the Variational Deep Embedding (VaDE, Jiang et al. (2017) ) and the Gaussian Mixture Variational Autoencoder
RMMM-VAE, Dilokthanakul Diloohhaaall et al. (2016) pro- pose a variant of the VAE (Kingma & Welling 20014); Rezende et al. (2014)) which the prior is a Gaussian Mixture distribution. With this assumption, they construct an inference model that can be directly optimised in the framework stochastic gradient variational Bayes. However, variational deep clustering methods, such as the VaDE, cannot incorporate domain knowledge and clustering preferences. Even though a semi-supervised version on the VAE has been proposed by Kingma et al. (2044), the latter cannot be naturally applied to clustering. For this reason, aim at extending the above methods to incorporate clustering preferences in the form of constraints, modeled as Bayesian priors, to guide the clustering process towards desirable configuration.
3 CONSTRAINED VARIATIONAL DEEP EMBEDDING
In the following section, we propose novel constrained clustering model (CVaDE) incorporate clustering preferences, with varying degree of certainty, in a VAE-based deep clustering setting. In particular, use the VaDE (Tiang al. 2017) generative assumptions of the data, conditioned on
2

---

Under review as a conference paper at ICLR 2021
the domain knowledge. We then illustrate how model can be trained efficiently in the framework of stochastic gradient variational Bayes by optimizing the Conditional Variational Lower Bound. Additionally, we define concrete prior formulations to incorporate our preferences, with focus on pairwise constraints.
3.1 THE GENERATIVE ASSUMPTIONS
Let consider data set X [ consisting of N samples with æ; E RM that we wish to cluster into K groups according to some prior information encoded as G. For example, we may know priori that certain samples should be clustered together with different degree of certainty. Hence G encodes both our prior knowledge on the data set and the degree of confidence. We assume the data is generated from random process consisting of three steps. First, the cluster assignments с {c; j==1 with C; {1...., K). are sampled from distribution conditioned on the prior information, e ~ p(c Next, for each cluster assignment c; a continuous latent embedding, E RD, is sampled from Gaussian distribution, whose mean and variance depend on the selected cluster C, Finally, the sample x; is generated from a distribution conditioned on z, Given C the generative process can be summarized as:
2, ~ p(zi(c) = NN Ma: c
x (2(()(2))) [N(xi o with Ma,, o [(z;; ; x;; is real-valued (er(().)) with = [zz 0) if x, is binary
(2)
where (o; and o², are mean and variance of the Gaussian distribution corresponding to cluster e; in the latent space and the function f=; 0) is a neural network, called decoder, parametrized by 0. Without prior information, that is when p(c]G) = p(c) = II. p(c.) = II; Cat(c, TT), the cluster assignments independent and identical distributed as they follow categorical distribution with mixing parameters π. In that case, the generative assumptions described above are equal to those of Jiang et al. (2017) and the parameters of the model can be learned using the unsupervised VaDE method (see Appendix C). In the following, we explore the case when p(c + p(c).
3.2 CONDITIONAL VARIATIONAL LOWER BOUND
Given the data generative assumptions illustrated in Sec. 3.1 the objective is to infer the parameters π. Max o² and which better explain the data given prior information on the cluster assignments We achieve this by maximizing the marginal log-likelihood conditioned on G, that is:
G.
logp(X(() = llog Σ Z(
(3)
where Z = [z: is the collection of the latent embeddings corresponding to the data set X. The conditional joint probability derived from Eq and can be factorized as:
p(X, Z. c po X (
p(c(G) II ((x(x//2))(z)l)))
(4)
Since the conditional log-lik log-likclihood is intractable, we derive a lower bound of the log marginal conditional probability of the data, which we call Conditional ELBO (C-ELBO, Le):
P(X, Z, G))
Lc(X X G) Eyg (Z,c|x) log go ZZ c)
(5)
Similarly to Jiang et al. (201)) and Dilokthanakul et al. (2016), we employ the following amortized mean-field variational distribution:
p(zz)c) II go (z(z//)))p(c with p(c,/z,) Σx p(z, k (k))
N
qs c() = qo (Z X)p(c)
(6)
where qo [2,]] x;) is a Gaussian distribution with mean ((x;;) and variance o²(xx)) )ll which are the outputs of neural network, called encoder, parametrized by é and p(c, = k)) is denoted as p(k) for simplicity. It is important to note that, in this formulation, the variational distribution does not depend on G. This approximation is used to retain mean meeanfieeld variational distribution if the cluster assignments, conditioned on the prior information, are not independent (Sec 3.4.I), that is when p(c|G) * l.)
3

---

Under review as a conference paper at ICLR 2021
3.3 ROLE OF THE PRIOR INFORMATION
To highlight how the prior information G influences the clustering objective, we rewrite Eq. as:
(7) The first term is called the reconstruction term, similarly to the VAE. The second term, on the other hand, is the Kullback- (KI.) divergence between the variational posterior and the Constrained Gaussian Mixture prior. By maximizing the C-ELBO, the variational posterior mimics the true con- ditional probability the latent embeddings and the cluster assignments. This results in enforcing the latent embeddings to follow Gaussian mixture which agrees on the clustering preferences.
Lx(X))) (2))) [log pe px DK (go clx))lp(z, c|G)).
Using Eq. 6 the Conditional ELBO can be further factorized as:
Lc(X = llog
+ E, (z|x) [lo po (
(8)
q.g (Z)x))((())) [log p c)] E (2.= (log qo c|X)]
where the last three terms are not affected by G and they can be rewritten using the SGVB estimator and the reparameterizatioo trick (Kingma & Welling (014) to be trained efficiently using stochastic
gradient descent (see Appendix B). The first term, the other hand, is investigated in Sec 3.4
3.4 CONDITIONAL PRIOR PROBABILITY
We incorporate our clustering preference through the conditional probability p(c[G). In particular, construct the conditional prior probability to be:
II, Te, (i()) p(c|G) II, (c)
(((T)) II Te, (i()..
where π { JR the weights associated to each cluster, c; is the cluster assignment of sample X4, (())) is the normalization factor and g: (c) is a weighting function that assumes large values
C, agrees with our belief with respect to and low values otherwise.
3.4.1 PAIRWISE CONSTRAINTS
We hereby focus on expressing the conditional prior distribution in the context of pairwise con- strained clustering and we do so by adapting the work of [u & Leen (2004) in our variational framework. The weighting function (c) is then defined as:
gc(c)= = II exp (Wi jæ
(10)
where 5 is the Kronecker d-function and W R.N is symmetric matrix containing the pairwise preferences and confidence. In particular, W 0 if we have no prior information on samples a;; and zj. W.j >> if there is a must-link constraint (the two samples should be clustered together) and Wi, < 0 if there is a cannot-link constraint (the two samples should not be clustered together). The value [W.jl [0, o0) reflects the degree of certainty in the constraint. For example, W.,; - -00 then and 2t must be assigned to different clusters otherwise P(c - 0 (hard constraint). On the other hand, smaller values indicate a soft preference as they admit some degree of freedom in the model. An heuristic to select [W. is presented in Sec Interestingly, the probability p(c|G) with pairwise constraints can be seen as the posterior of the superparamagnetic clustering method (Blat) et al. 1996]. with loss function given by fully connected Potts model (Wul 1982). Differently from our method, Blatt et al. (996) cluster the data according to the pairwise correlation functions Eete that are estimated with MCMC methods.
Finally, we incorporate the conditional prior distribution in Eq. 8 The first term can be written as:
E Z)) (logp(c|G') Ex((z/) log [((T))
We.
exp
(Wey
(11)
logog ((T)) Σ Ep(c.le.)) log To;
Ep(cele, Bpic,, W Wisjoces
(12)
- log Q(T) + Σ Σ p(c: = klz,, log To: +
Σ
Σ
p(c, = klz:)p(c, = k/2,)
(13)
i8
4

---

Under review as a conference paper at ICLR 2021
Maximizing Eq. 13 w.I.t. π poses computational problems due to the normalization factor (((r). Crude approximations are investigated in (Basu et al. 2008), however we choose to fix the parameter 1/K to make z uniformly distributed in the latent space, as in previous works (Dilokthanakul et al. 2016). By doing so, the normalization factor can be treated as a constant. The analysis of different approaches to learn the weights я is left for future work. The C-ELBO with pairwise constrained prior can then be optimized using Monte Carlo sampling and stochastic gradient descent.
Tk
3.4.2 FURTHER POSSIBLE CONSTRAINTS
Given the flexibility of our general framework, different types of constraints can be included in the formulation of the weighting functions 9s(c). In particular, we can perform semi supe-supe learning by setting the prior information as:
gi (c(c) = g(c,) = exp (Wix) with W E N
(14)
where W., indicates whether the sample x, should be assigned to cluster k. Additionally, one could also include triple-constraints by modifying the weighting function to be:
gc(c)= = II exp (Wa,, (Wa,,keeeeaa)) with W E R NNNNN symmetric. J.by
(15)
where W i. = 0 if we do not have any prior information, W & >> 0 indicates that the samples a Ty and æ& should be clustered together and W.i.k < 0 if they should belong to different clusters. The analysis of these different constraints formulation is outside the scope of our work but they may represent interesting directions for future work.
4 EXPERIMENTS
In the following, we provide a thorough empirical assessment of our proposed method (CVaDB) with pairwise constraints using wide range of data sets. First, we evaluate our model's performance compared to both unsupervised variational deep clustering methods and state-of-the-art constrained clustering methods. Then, we present extensive evidence of the ability of our model to handle noisy constraint information. We additionally perform experiments on a medical application to prove that our model can reach different desirable partitions of the data, depending on the constraints used, even with real-world, noisy data. Finally, we show that CVaDE successfully generates new data, using the learned generative process of Sec 3.I on a challenging face image data set.
Baselines & implementation details. As baselines, we include the traditional constrained K- means (MPCK- mmans, Bilenko et al. (2004) and two recent deep constrained clustering methods based on DEC (SDEC, Ren et al. (2019), and C-IDEC, /Zhang et al. (2019b)) as they achieve state- of-the-art performance in constrained clustering. We also compare our model to the unsupervised variational deep clustering method VaDE (Jiang al. 2017). To implement our model, we were careful maintaining a fair comparison with the baselines. In particular, we adopted the same en- coder and decoder feed-forwar architecture among all methods with four layers of 500, 500, 2000, D units respectively, where = 10 unless stated otherwise. The VAE is pretrained for 10 epochs while the DEC-based baselines need more complex layer-wise pretraining of the autoencoder which involves 50 epochs of pretraining for each layer and 100 epochs of pretraining as finetuning. The pairwise constraints are chosen randomly within the training set by sampling two data points and assigning a must-link if they have the same label and cannot-link otherwise. Unless stated otherwise, the values of [Wa,l are set to 10a for all data sets, and N pairwise constraints are used for both our model and the constrained clustering baselines, where N is the number of samples of the considered data set. Note that N pairwise constraints can be obtained by using only /N labeled data points. To allow for fast iteration we simplify the last term of Eq. [3 allowing the search of pairwise constraints to be performed only inside the considered batch. We observed empirically that, with a batch size of 1024, this approximation does not affect the clustering performance. Further details on the other typer-parametert setting can be found in the Appendix E.
Constrained clustering. We test the clustering performance of our model compared with the base- lines on four different data sets: MNIST (LeCuun et al. 2010), Fashion MNIST (Xiao et al., 2017).
5

---

Under review as a conference paper at ICLR 2021
Reuters (Xie al. 2 and HHAR (Stisen et al. 2015) (see Appendix A) Note that pre- processed the Reuters data by computing the tf-idf features on the 2000 most frequent words on a random subset of 10000 documents and by selecting 4 root categories (Xie et al. 2016). Accuracy and Normalized Mutual Information (NMI) are used as evaluation metrics. The results are shown in T We observe that our model reaches vate-of-the-ar performance in the Fashion MNIST and Reuters data sets. On MNIST and HHAR data sets, on the other hand, it has comparable clustering performance with C-IDEC, however it is generally more stable accross different data sets.
Table 1: Clustering performances of CVaDE compared with baselines. All methods use N pair- wise constraints (v'N labels) except the unsupervised VaDE. Means and standard deviations are computed across 10 runs with different random model initialization and pre-training weights.
MNIST
FASHION
REUTERS
HHAR
Acc
NMI
Acc
NMI
Acc
NMI
Acc
NMI
VaDE
85.9 #o.7
81.9 +2.2
59.3 #2.3
59.8 #1.9
76.0 #0.7
50.2 =0.9
75.3 #6.9
70.5 #4.0
MPCK
58.8 10.0
53.3 10.1
57.5 10.0
59.8 11.9
60.7
10.5
50.2 =0.9
58.1 10.2
70.5 14.0
SDEC
87.9 #0.2
86.8 +0.3
59.7 #2.2
63.0 +1.2
77.3 #3.9
60.0 =2.9
67.0
#7.0
71.5 +2.0
C-IDEC
97.9 +0.1
94.3
+0.3
84.5
#1.7
76.0 #1.6
92.6
#4.1
79.1 =4.1
98.4
40.5
86.3 #1.1
CVaDE
98.0 20.1
94.4
#0.2
86.1
20.2
77.6 =0.3
95.3 20.5
82.6
#1.4
93.5
10.8
86.5 #1.2
Constrained clustering with noisy labels. In real-world applications it is often the case that the additional information comes from different sources with different noise levels. an exam- ple, pairwise annotations could be obtained by both very experienced domain experts and by less- experienced users. Hence, the ability to integrate constraints with different degrees of certainty into the clustering algorithm is of significant practical importance. In this experiment, we consider the case in which the given pairwise constraints have three different noise levels, E {0.1, 0.3), where q determines the fraction of pairwise constraints with flipped signs (that is, when must- link is turned into a cannot-link and vice-versa). In Fig. I we show the clustering performance of our model compared to the strongest baseline derived from the previous section, C-IDEC. For all data sets, we decrease the value of the pairwise confidence of our method using the heuristic [Wi,1 a log 1-q with a = 3500. Also, we use grid search to choose the hyper-parameters of C-IDEC for the different noise levels (in particular set the penalty weight 0.1, 0.005, and 0.001 respectively). CVaDE clearly achieves better performance in terms of accuracy and NMI on all three noise levels for all data sets. In partieular, the higher the noise level the greater the performance dif- ference. We can conclude that our model is more robust than its main competitor. Additionally, C-IDEC cannot model differrent noise levels within the same data set, while our model can easily include different source of information with different degree of uncertainty.
Heart Echo. We evaluate the effectiveness of our model in real-world application by using in- fant heart echo cardiogram videos. The data set consists of 305 infant echo cardiogram videos from 65 patient visits obtained from large University Children's 's Hospital. Each visit may consist of videos taken from several different angles (called view), denoted by [LA, KAKL, KAPAP, KAAP, 4CVJ. We cropped the videos by isolating the cone of the echo cardiogram, we resized them to 64 x 64 pixels and split them into individual frames obtaining a total of N = 20000 images. We focused on investigating two constrained clustering problems using this data set. First, we cluster the echo video frames by view. This is a relevant task, as in many datasets, heart echo videos are not explicitly labeled (Zhang et al., 2018). Then, we cluster the echo video frames by infant maturity at birth, following the WHO definition of premature birth categories ("Preterm").. We believe that these two clustering tasks demonstrate that our model admits a degree of control in choosing the underlying structure of the learned clusters. As the experiments demonstrate, by providing different pairwise constraints, it is possible to guide the clustering process towards a preferred configuration, depending what the practitioners For both experiments, we compare the performance of our method, CVaDE, with the unsupervised VaDE method and the C-IDEC. Additionally, include variant of both method and VaDE in
seeking in the data.

---

Under review as a conference paper at ICLR 2021
000
CVubc 10EC
OYIDE
goos
075
0.0
2.79
050
8:3
Nolso level
Nos0 kve
Notse level
Nobo
(a) MNIST
(b) Fashion MNIST
CVADE IDEC-C9
3.9
24
3.4
Nose
Notae beanl
Pizaa level
(c) Reuters
(d) HHAR
Figure! 1: Accuracy and NMI clustering performance on four different datasets with noisy labels.
which we use convolutional layers (CNN-CVaDE and CNN-VaDE), for details on the implementa- tion we refer to the Appendix E.2 The results shown in Table The CVaDE model outperforms both baselines by a significant margin in both accuracy and NMI in all clustering experiments. This demonstrates that the addition of domain knowledge is particularly effective for medical purposes. Additionally, we observe that C-IDEC performs poorly on real-world noisy data. We believe this is due the heavy pretraining of the autoencoder, required by DEC-based methods, ways enforce that the learned latent space is suitable for clustering. Additionally, we investigate the relationship between the number of constraints and clustering performance for the view detection task. We observed that with only 5000 pairwise constraints, which could be obtained with less than 80 labels, our model achieves results comparable to those of Table Appendix for details).
does not al-
Table 2: Constrained clustering results using heart echo cardiogram data with fully connected layers on the left and convolutional layers the right. Means and standard deviations are computed across 10 runs with different random model initialization and pre-training weights.
Clustering
Metric
C-IDEC
VaDE
CVaDE
CNN- VDDE CNN-CVaDE
View
Acc
69.5 #8.4
33.4 #2.0
81.0 #2.5
46.3 #8.0
91.422. 24.2 #6.5
NMI
47.8 #15.5
11.9 #2.6
60.944.0
80.1
Preterm
Acc
64.9 15.8
40.9
73.4 #1.3
40. 70..9
74.4 12.3
NMI
11.0 #9.9
6.2 #1.6
26.0 #2.6
9.94
34.7 #3.8
Face Image Generation We evaluate the generative capabilities our model using the UTKFace dataset (Zhang et al.] (017). This dataset contains over 20000 images of male and female faces, aged from I to 118 years old, with multiple ethnicities represented. We use a convolutional network for the VAE (the implementation details are described in the Appendix E.3). As first task, we cluster the data using the gender prior information, in the form of 2N pairwise constraints, which requires labels for 0.7% of the data Fig. 2a 2b/shows the PCA decomposition of the embedding space of both CVaDE and the unsupervised VaDE method. As second task, we select sub- sub-sample of individuals between 18 and 50 years of age (approx. 11000 samples), and cluster by ethnicity We believe that one possi- ble reason for biases in machine learning models currently due to under-representation of various ethnic groups in training data sets. The constrained CVaDE method could be used to identify such imbalances, while requiring only relatively small number of labeled training samples. This would allow easy identification of such instances of bias in training data sets at relatively low cost. Fur- thermore, the ability to generate samples from these detected clusters potentially allows automatic data augmentation. With the inclusion of domain knowledge, observe neat division of the
(White, Black, Indian, Asian) using 2N pairwise constraints, Fig. 2c 2d

---

Under review as a conference paper at ICLR 2021
Label Made
Label
White
Asian
Indian
(a) CVaDE: Ace 0.89
(b) VaDE: Ace 0.51
(c) CV&DE: Ace 0.85
(d) VaDE: Acc 0.57
Figure 2: PCA decomposition of test set examples in the embedded space and generative samples using CVaDE and VaDE for (a)-(b) Gender, (c)-(d) Ethnicity. In this configuration, CVDDE obtains NMI of 0.52 (gender) and 0.4 (ethnicity) while VaDE obtains NMI close for both tasks.
selected clusters the embedding space both tasks, conversely the unsupervised approach not able to distinguish any feature of interest,
Finally, using the multivariate Gaussian distributions of each cluster the learned embedded space, test the generative capabilities of CVaDE by first recovering the mean face of each cluster, and then generating several more faces from each cluster. Figure 3 shows these generated samples. As be observed, the ethnicities present in the data set represented well by the mean face. Fur- thermore, the sampled faces all correspond to the respective cluster, and have good amount of variation. The quality of generated samples could be improved by using higher resolution training samples or different CNN architectures.
Mean
Samples
Gender
Ethnicity
Figure 3: Mean face and sampled faces for each learned cluster, top two rows corresponding to gender, bottom rows to ethnicity
CONCLUSION
In this work, we present novel constrained deep clustering method, CVaDE, that incorporates clus- tering preferences in the form of pairwise constraints, with varying degrees of certainty. In contrast to existing constrained deep clustering approaches, CVaDE uncovers the underlying distribution of the data, resulting in the ability to generate new samples, perform Bayesian model validation and outlier detection. With the integration domain knowledge, we show that our model can drive the clustering algorithm towards the partitions of the data sought by the practitioners, achieving state- of-the-art art constrained clustering performance in real-world and complex data sets. Additionally, model proves to be robust to noisy constraints as it efficiently include uncertainty into the clustering preferences. As a result. the proposed model can be applied to a variety of applications where the difficulty of obtaining labelled data prevents the of fully supervised algorithms.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
S. Basu, I. Davidson, and K. Wagstaff. Constrained clustering: Advances in algorithms, theory, and applications. 2008
Mikhail Bilenko. S. Basu, and R. Mooney. supervised clustering. In ICML '04, 2004.
Integrating constraints and metric learning in semi-
Marcelo Blatt, Shai Wiseman, and Eytan Domany. Superparamagnetiic clustering of data. Phys. Rev. Lett. 76:3251-3254. Apr 1996. doi: 10.1 10.1105/hhy.RevLLe.....2.2 URL https::/ aps goss.ogg/ooi111.11000 http://oo1...111/////eeeeeeettt. 3225
G. Chen. Deep transductive semi-supervised maximum margin clustering. ArXiv, abs/1501.06237, 2015.
Nat Dilokthanakul, Pedro A. M. Mediano, Marta Gamelo, Matthew C. H. Lee, Hugh Salimbeni, Kai Arulkumaran, and Murray Shanahan. Deep unsupervised clustering with gaussian mixture variational autoencoders. ArXiv, abs/1611.02248,, 2016.
S. Fogel, Hadar Averbuch-Elor, D. Cohen-Or, and J. Goldberger. Clustering-driver deep embedding with pairwise constraints. IEEE computer graphics and applications, 39 4:16-27, 2019.
Yen-Chang Hsu and 7. Kira. Neural network-based clustering using pairwise constraints. ArXiv, 02s/1511.06322) 2015.
Zhuxi Jiang, Yin Zheng, Huachun Tan, Bangsheng Tang, and Hamning Zhou. Variational deep embedding: An unsupervised and generative approach to clustering. In IJCAI, 2017.
Diederik Kingma and Max Welling. Auto-encoding variational bayes. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014, URL htt.:tttp//axii..r.tt
abs/ 131 6114
Diederik Kingma, Shakir Mohamed, Danilo Jimenez Rezende, and M. Welling. Semi-supervised learning with deep generative models. In NIPS, 2014.
A. Kopf, Vincent Fortuin, Vignesh Ram Somnath, and M. Claassen. Mixture-of-cxperts varia- tional autoencoder for clustering and generating from similarity- representations. ArXiv, abs/1910.07763, 2019.
T. Lange, Martin H. C. Law, Anil K. Jain, and Buhmann. Learning with constrained and unlabelled data. 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'0S) 1:731-738 vol. 1, 2005.
Martin H. C. Law, A. Topchy, and Anil K. Jain. Clustering with soft and group constraints. In SSPR/SPR, 2004.
Martin H. C. Law, Topchy, and Anil K. Jain. Model-based clustering with probabilistic con- straints. In SDM, 2005.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online). Available: http://yamm.lecu.. www.....cco//xd////issssts 2, 2010.
David D. Lewis, Yiming Yang, Tony Rose, and Fan Li. Rev1: new benchmark collection for text categorization research. J. Mach. Learn. Res., 5:361-397, December 2004. ISSN 1532-4435.
Xiaopeng Li, Zhourong Chen, Leonard K. M. Poon, and L. Zhang. Learning latent superstruc- tures in variational autoencoders for deep multidimensional clustering. In ICLR, 2019.
Z. Lu and T. Leen. Semi-supervised learning with penalized probabilistic clustering. In NIPS, 2004.
Laura Manduchi, M. Hüser, G. Rätsch, and Vincent Fortuin. Variational psom: Deep probabilistic clustering with self-organizing maps. ArXiv, abs/1910.01 2019.

---

Under review as a conference paper at ICLR 2021
Erxue Min, Xifeng Guo, Q. Liu, G. Zhang, Jianjing Cui, and Jun Long. A survey of clustering with deep learning: From the perspective of network architecture. IEEE Access, 6:39501-39514, 2018.
Yazhou Ren, Kangrong Hu, Xinyi Dai, Lili Pan, Steven C. H. Hoi, and Zenglin Xu, Semi-supervised deep embedded clustering. Neurocomputing, 325:121-1300 2019.
Danilo Jimenez Rezende, S. Mohamed, and Daan Wierstra. Stochastic backpropagation and approx- imate inference in deep generative models. In ICML, 2014.
N. Shental, Aharon Bar-Hillel, T. Hertz, and D. Weinshall. Computing gaussian mixture models with em using equivalence constraints, In NIPS, 2003.
Ankita Shukla, Gullal Singh Cheema, and Saket Anand. Semi-supervised clustering with neural networks. arXiv: Learning, 2018.
M. Smieja, Lukasz Struski, and Mário A. T. Figueiredo. A classification-basee approach to semi- supervised clustering with pairwise constraints. Neural networks the official journal of the International Neural Network Society, 127:193-203, 2020.
Allan Stisen, Henrik Blunck, Sourav Bhattacharya, Thor Süiger Prentow, Mikkel Baun Kjærgaard, Anind Dey, Tobias Sonne, and Mads Møller Jensen. Smart devices are different: Assessing and mitigatingmobile sensing heterogeneities for activity recognition. In Proceedings of the 13th ACM Conference on Embedded Networked Sensor Systems, SenSys '15, pp. 127-140, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450336314 4. doi: 10.1 14.1/ 2809695.2809718
wttp://////11111/1/0009090999999 2809711
K. Wagstaff and Claire Cardie. Clustering with instance-level constraints. In AAAI/IAAI, 2000.
K. Wagstaff, Claire Cardie, S. Rogers, and S. Schrödl. Constrained k-means clustering with back- ground knowledge. In ICML, 2001.
F. Y. Wu. The potts model. Rev. Mod. Phys., http:////.........//ooe......... 54. 54.235 235. JRLhtts::://iie aps http://e...aaa.....oo...///////1
Jan 1982. doi: 10. 10.1100//
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms, 2017.
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. volume 48 of Proceedings Machine Learning Research, pp. 478-487, New York, New York, USA, 20-22 Jun 2016. PMLR. URL htt::/t: /tt.:eeeeiin..mm...perss//////1 html
mlr. ptwss//v1/xieeblll//
L. Yang, N. Cheung, J. Li, and Jun Fang. Deep clustering by gaussian mixture variational autoen- coders with graph embedding. 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 6439-6448, 2019.
C. Zhang, Judith Bütepage, H. Kjellström, and S. Mandt. Advances in variational inference. IEEE Transactions on Pattern Analysis and Machine Intelligence, 41:2008-200 22066 2019a.
H. Zhang, S. Basu, and I. Davidson. A framework for deep constrained clustering algorithms and advances. ECML/PKDD, 2019b.
Jeffrey Zhang, Sravani Gajjala, Pulkit Agrawal, Geoffrey Tison, Laura Hallock, Lauren Beussink, Mats Lassen, Eugene Fan, Mandar Aras, ChaRandle Jordan, Kirsten Fleischmann, Michelle Melisko, Atif Qasim, Sanjiv Shah, Ruzena Bajesy, and Rahul Deo. Fully automated echocar- diogram interpretation clinical practice: Feasibility and diagnostic accuracy. Circulation, 138: 1623-1635, 10 2018. doi: 10.1 (0.16//CCICCLLATTONNAALL 18.004338.
Zhifei Zhang, Yang Song, and H. Qi. Age progression/regression by conditional adversarial au- toencoder. 2017 IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pp- 4352-4360, 2017.
10

---

Under review as a conference paper at ICLR 2021
APPENDIX
A DATA SETS
The data sets used in the experiments the followings:
MNIST: It consists of 70000 handwritten digits. The images centered and of size 28
by 28 pixels. We reshaped each image to a 784- dimensional vector (LeCun et al. 2010).
Fashion MNIST: A data set of Zalando's article images consisting of training set of 60,000 examples and a test set of 10,000 examples (Xiao et al. 2017).
HHAR: The Heterogeneity Human Activity Recognition (HHAR) dataset contains 10299 sensor records from smart phones and smart watches. All samples are partitioned into categories of human activities and each sample is of 561 dimensions (Stisen et al. 2015)..
Reuters: It contains 810000 English news stories (Lewis al., 2004). Following the work of Xie et al.] (2016), we used 4 root categories: corporate/induustral government/social, markets, and economics as labels and discarded all documents with multiple labels, which results in 68507 l-rrticle dataset. We computed tf-idf features on the 2000 most frequent words to represent all articles. A random subset of 10000 documents then sampled.
Newhorn echo cardiograms: The dataset consists of 305 infant echo cardiogram videos from 65 patient visits obtained from large children hospital. Each visit may consist of vidcos taken from several different angles, denoted by [LA, KAKL, KAPAP, KAAP, 4CV]. We cropped the videos by isolating the cone of the echo cardiogram, we resized them to 64x64 pixels and split them into individual frames obtaining a total of N 20000 images.
UTKFace: This dataset contains over 20000 images of male and female face of individuals from 1 to 1 18 years old, with multiple ethnicities represented (Zhang et al. 2017)
B CONDITIONAL ELBO DERIVATIONS
In this section, provide the detailed derivation of the Conditional ELBO with pairwise constraints and we describe how it can be trained efficiently with Monte Carlo sampling. Specifically, the C- ELBO, Lx(X)G), is the upper bound of the marginal ligelikel conditioned on G:
Oog((X|)) = log / Σ D(x, 2 B.s(Z,,(x) log
p(X, Z, c(G) 4s (Z. = Lc(X]G). (16)
By plugging in the marginal log-likelihood of Eq. 3 and the variational distribution of Eq. 6 the C-ELBO can rewritten as:
Lc(X|G) = cz (X ( [|) + (zpp)//z))) (log p []]] P(c
- E, (/x) log go (2, c|X)
(17)
(18)
4 Byte/z) Dog p(c [c]
where we used the fact that the variational distribution can be factorized as qs (Z, c(X) (p(C()) Z).
=
Given that yo (Z(X) = go (x)(2)))))p(c(le and using Eq 13 we can further factorize Eq
18
N
Lo(X|G) =
Σ (x0 (x + B (oocc
+ (ppe.. log Fe; +
Σ Fpie.l,, 12,,, Weydere;
(19)
$
- (x (lz xx)] Ep(e,12,) [lg (agcll))loggg( ((css/2))]

---

Under review as a conference paper at ICLR 2021
As p(c]/z;) is discrete, Eptes m)Hl Ex p(c; 1z 1//z)]l],, the above equation can then be written
N
Lo(X =
(x (logpo(x(zzz)) + Bo (x))))))
Σ p(c; = klz,) logp(z, = ki)
Σ plc; = ki/zz) log ne,
ΣΣ iati &
pl = k(zz)p((; = k12;)
(20)
&
ge (x: [log (z.)(()))x))
Σp(e plc: klzi) klzz)]
Using the SGVB estimator, we can approximate the above equation as:
N Σ
Lc Lc(X|G)
log po (x: + p(cc = -1/2 ! log log k:)
1=1
Σ
p(c: = k2(z!") llog Te. + Σ Σ
p(c; = k/zi)p(c; = elz,)Wi, (21)
k
&
log 2o (z. (x.) (x,)
Ep(c = k/2
logp(c; klz
where L is the number of Monte Carlo samples in the SGVB estimator and it is 1 in all experiments.
C VARIATIONAL DEEP EMBEDDING
The Variational Deep Embedding method, VaDE (Jiang et al., 2017), assumes an observed sample X; is generated by the following generative process:
Cat(1/K)
2. ~ p(zile:) (Zi o.,1) (Z 22 with [Mz,, 22.1 [001=f(e f(z;;()) if x; is real-valued x; p(x 2:) (err(pz,) with pz. f(z;; 0) if x; is binary
(22)
(23)
where K is the predefined number of clusters ple a² are mean and variance of the Gaussian distri- bution corresponding cluster in the latent space and the function f(z; 0) is neural network, called decoder, parametrized by 0, similarly to a VAE. To infer both the parameters of the Gaussian mixture model and the decoder, the VaDE maximises the likelihood of the data X, that is:
/ Ee(X, 2. [Z) log
p(X, Z, c)
log p X) log
q (Z, c() LELBO
The variational distribution is chosen to be:
plz, (24)
go (Z,
II qo (Z., cx(x))
II qs (z. (()(c))()))) with p(c./z.) Σ. p(z, k))(k)
where qo [z;] x;) ) is a Gaussian distribution with mean ((x;) and variance o²(x:)l which are the outputs of a neural network, called encoder, parametrized by a.
The ELBO can be then formulated as:
GELBO(X) = (z)(Z [log pe Z)] - DK (xcx(a/
(25)
D FURTHER EXPERIMENTS
D. COMPARISON WITH C-IDEC
In Table 3. present the quantitative results in term of Adjusted Rand Index (ARI) and the per- centage of satisfied constraints (SC) of both our model, CVaDE, and the strongest bascline, C-IDEC with N constraints.
12

---

Under review as a conference paper at ICLR 2021
Table 3: Clustering performances of CVaDE compared with C-IDEC. All methods use N pairwise constraints (vNV labels) except the unsupervised VaDE. Means and standard deviations are com- puted across 5 runs with different random model initialization and pre- pre-training weights.
MNIST
FASHION
REUTERS
HHAR
ARI
SC
ARI
SC
ARI
SC
ARI
SC
C-IDEC 95.1 10.5
100
70.5 #2.3
98
88.6
#0.8
100
86.4 20.8
100
CVaDE 95.7 20.2 100
75.5 #0.4
100
90.3
20.8
100
87.4 21.0
100
D.2 NOISY LABELS
we present the quantitative results in term of Accuracy and Normalized Mutual In- formation of both our model, CVaDE, and the strongest baseline, C-IDEC with noisy constraints (presented visually in Fig. [. In particular, the results are computed for E {0.1, 0.2, 0.3), where determines the fraction of pairwise constraints with flipped signs (that is, when a must- is turned into a cannot-link and vice-versa).
In Tables 4 6
Table 4: Clustering performances with noisy labels averaged over 10 runs MNIST.
Noise level
Metric
C-IDEC
CVaDE
0.1
Accuracy
0.960 0.001
0.974 + 0.001
NMI
0.904 0.003
0.930 + 0.002
q 0.2
Accuracy
0.939 0.003
0.964 + 0.003
NMI
0.863 + 0.006
1011=:000
q 0.3
Accuracy
0.905 + 0.010
0.006
NMI
0.808 0.016
+
Table 5: Clustering performances with noisy labels averaged over 10 runs on fMNIST.
Noise level
Metrie
C-IDEC
CVaDE
q 0.1
Accuracy
0.800 0.027
0.843 + 0.005
NMI
0.717 + 0.021
0.757 + 0.004
0.2
Accuracy
0.749 + 0.037
0.816 + 0.004
NMI
0.667 0.024
0.731 + 0.003
0.3
Accuracy
0.688 0.031
0.727 + 0.030
NMI
0.601 + 0.024
0.656 + 0.021
Table 6: Clustering performances with noisy labels averaged over 10 runs Reuters.
Noise level
Metric
C-IDEC
CVaDE
0.1
Accuracy
0.923 + 0.010
0.942 + 0.003
NMI
0.748 0.020
0.794 + 0.009
q 0.2
Accuracy
0.786 0.018
0.917 0.005
NMI
0.557 +: 0.016
0.727 0.013
0.3
Accuracy
0.706 + 0.010
0.850 0.019
NMI
0.455 + 0.017
0.594 0.030
13

---

Under review as a conference paper at ICLR 2021
Table 7: Clustering performances with noisy labels averaged over 10 runs on HHAR.
Noise level
Metric
C-IDEC
CVaDE
0.1
Accuracy
0.893 + 0.016
0.920 + 0.009
NMI
0.797 0.018
0.844
0.2
Accuracy
0.788 0.037
0.906 + 0.016
NMI
0.671 + 0.040
0.818 + 0.019
q = 0.3
Accuracy
0.597 0.034
0.841 0.024
NMI
0.493 + 0.041
0.720 + 0.023
D.3 HEART ECHO
PCA Decompostion In Figure we present PCA decomposition of the embedded space learned by both the CVaDE and VaDE baseline, from the experiment presented Section can be observed that the CVaDE model, using N constraints, is able to learn embedded space which clusters by view much more effectively.
Latel
SAO
SATA?
KAN
CV
Figure 4: Left: PCA decomposition of CVaDE learned embedded space with representative samples from the dataset, right: baseline VaDE embedded space
Impact of Constraints In order to try to understand how the number of constraints provided impacts the performance of CVaDE, we performed experiment using the heart echo dataset where progressively more and more constraints were provided to the model during training. Figure 5 demonstrates that the clustering performance of CVaDE improves as pairwise constraints provided. This trend continues until 5000 pairwise constraints are provided (requiring 0.35% of the dataset be labeled), which point the performance reaches plateau.
E IMPLEMENTATION DETAILS
E. HYPER-PARAMETER SETTING
In Table & we specify the paraae-ps setting of both our model, CVaDE, and the unsuper- vised baseline, VaDE. Given the semi-supervised setting, we not focus in fine-tuning the hyper- parameters but rather we chose standard configurations for all data sets. We observed that model robust against changes the hyper-parameters. except for the batch size. The latter requires a high value. as simplify the last term of Eq. [3 by allowing the search of pairwise constraints to be performed only inside the considered batch. For the VaDE, we used the same setting used in their paper (Jiang al. 2017)
14

---

Under review as a conference paper at ICLR 2021
04
Acurncy
04
VVI
500
1000
1500
2000
2500
3000
3500
4000
4500
5003
Figure 5: Plot demonstrating that CVaDE's performance improves more constraints are given. At 5000 pairwise constraints the performance equals that of N 20000 (the total number samples)
Table 8: Hyperparameters setting of both our model, CVaDE, and the unsupervised VaDE.
CVaDE
VaDE
MNIST
FASHION
REUTERS
HHAR
MNIST
FASHION
REUTERS
HHAR
Batch size
1024
1024
1024
1024
128
128
128
128
Epochs
1500
1000
1000
1000
1000
1000
100
500
Learning rate
0.001
0.001
0.001
0.0001
0.002
0.002
0.002
0.002
Decay
10-5
10-4
10-4
10-4
10,0.9
10,0.9
5,0.5
10, 0.9
E.2 HEART ECHO
In addition to the model described in Section 4 also used VGG-like convolutional neural network. This model is implemented in Tensorflow, using two VGG blocks (using a 3 x kernel size) of 32 and 64 filters for the encoder, followed to an embedding of dimension 10. The decoder has a symmetric architecture.
single fully-connected layer reducing down
The VAE pretrained for 10 epochs, following which our model is trained for 300 epochs using learning rate of 0.001 (with an exponential decay of 0.00001), and a batch size of 1024. Refer to the accompanying code for further details.
E.3 FACE IMAGE GENERATION
The face image generation experiments using the UTK Face dataset described in Section 4 were carried out using VGG-like convolutional neural networks implemented in Tensorflow. In particular,
15

---

Under review as a conference paper at ICLR 2021
the input image size of 64 64 x 3 allowed two VGG blocks (using 3 x 3 kernel size) of 64 and 128 filters for the encoder, followed by single fully fully-connected layer reducing down to an embedding of dimension 50. The decoder has symmetric architecture.
The VAE is pretrained for 100 epochs. following which our model trained for 1000 epochs using learning rate of 0.001 (with decay of 0.00001), and batch size of 1024. Refer to the accompanying code for further details.
16


Reviews:
[{"review_id": "y-EuOe_2w6K", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "This paper solves the constrained clustering from a probabilistic perspective in a deep learning framework. In general, this paper suffers from several major problems. I will illustrate my concerns point-by-point.\n1. The authors mention that none of the existing work in the deep (constrained) clustering models the data generative process. First, this is not true. For example, Semi-crowdsourced Clustering with Deep Generative Models. Second, the authors should illustrate the benefits of data generative process for constrained clustering. That is the motivation of this paper. Unfortunately, the motivation is not strong and clear.\n2. If I understand correctly, Eq. (9) and (10) are the core techniques for the proposed algorithm. Such a penalty is straightforward in   constrained clustering. \n3. In Section 3.4.2, there is another side information, named partition level constraint. The authors might want to explore this as well. This point is not a drawback. Just a suggestion.\n4. Some traditional constrained clustering methods with deep VaDE features can be involved for comparisons. \n5. It is better to provide some insights on robustness with noisy side information.\n6. How to set alpha? Is there some normalization to make alpha within a small range?\n7. It is better to show the performance with different numbers of constraints.\n8. I am thinking whether two applications in the experimental section are practical in real-world scenarios. I mean how to obtain the pairwise constraints? If I were the project manager in charge of annotation, I will directly label their categories, rather than providing the pairwise constraints.", "extra_scores": {}, "extra_text": {}}, {"review_id": "REWyhTZXgU", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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**\nThis work proposes CVaDE which is an extension of variational based deep clustering model (VaDE) with additional incorporation of prior clustering preferences as supervision. These priors guide the underlying clustering process towards a user-desirable partitioning of input data. The priors are provided in the form of pairwise constraints indicating which pair of samples belongs to same or different class. Clustering process is modelled using variational Bayes in which the clustering constraints are incorporated into prior probabilities with varying degree of uncertainty. The empirical results shows that in comparison to unconstrained clustering the small amount of pairwise constraints significantly improves clustering performance. Further, it demonstrates CVaDE's robustness to noise, generation capability as well as successful incorporation of different desirable preferences to drive clustering performance towards completely different partitioning.\n\n**Quality**\nThe paper is well written albeit with numerous typographical error (some of which are listed at the end of this review). Experimental evaluation seems thorough. However, I would like to compare results on complex datasets as well as with large classes (> 10). Complex datasets includes STL-10, YouTube Faces, mini ImageNet etc. Please show efficacy on diverse sets of data covering large variation in number of classes, dimensionality, attributes.\n\nMoreover, clustering being unsupervised (here semi-supervised) one should not (rather cannot) employ different hyper-parameters for different dataset. Under the context of zero ground truth data availability, they should rather be fixed. Table 7 says otherwise.\n\n**Originality**\nAs mentioned above, CVaDE is extended from VaDE but with prior input constraints. Thus the conditional ELBO loss objective is thus a simple extension of VaDE objective. Apart from this, the prior distribution used for pairwise constraints is adapted from work of Lu & Leen (2004). In summary, the work carries very little novelty.\n\n**Significance**\nConstrained clustering has been around for some time in various forms. However, the subtle difference CVaDE brings to the table is how to incorporate them into prior probabilities.\n\nLike VaDE, CVaDE is also clustering cum generative model. Once trained, model can be employed for sampling new data. Due to better training procedure using constraints, the generated samples is bound to be perceptually better. However, the samples are not better than the state of the art conditional generative models such as InfoGANs. \n\n**Clarity**\n1. In eq(2), shouldn't it be $\\mu_{z_i}$ instead of $\\mu_{x_i}$. Is function $f(z_i; \\theta)$ not deterministic ? My understanding is given fixed $\\mu_{z_i}$ one can sample as many $x_i$. Same goes for $\\sigma_{x_i}$.\n2. Figure 5, axis labels are missing.\n3. Under experiments, please make clear what are we solving for - $z$ and $c$ ? Have you tried k-means on extracted $z$ post training ? \n4. What is penalty weight ? I did not find any description.\n5. Why C-IDEC cannot model different noise levels within same data set ?\n6. Where is the derivation for Conditional ELBO formulation ? In appendix I only find solution to C-ELBO not how to derive Eq (5).\n7. What is the impact of imbalanced dataset on CVaDE ? I presume apriori this imbalance is not known to the user.\n8. Eq (19), is $\\mathbb{E}$ different from $E$ ?\n9. Eq (19), Eq (20) summation w.r.t. is pulled out. Typo in $W_{ij}$ component.\n10. Eq (21), some of the terms are approximated by Monte carlo sampling while others are still taking expectation\n11. In Eq (18), If 3rd term is marginalised w.r.t. $q(Z|X)$ then it is technically wrong to apply monte-carlo sample to central line in Eq (21). Remember $\\frac{1}{L}$ approximates $q(z_i|x_i)$ which is applicable for 1st, 2nd and 4th terms. Not for all.\n12. Eq(12) $\\delta_{c_ic_j}$ is missing\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "A4aioYD02Th", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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.\n\nThis paper extends the variational deep embedding VaDE model (a VAE-based clustering method) to integrate pairwise constraints between objects, i.e., must-link and cannot-link. The constraints are integrated a priori as a condition. That is, the prior over the cluster labels is conditioned on the constraints. The whole model, referred to as Constrained VaDE (CVaDE), takes the form of a conditional VAE tailored for constrained clustering. Experiments are curried out on various real-world datasets, and the proposed method is compared to VaDE as well as to recent and classical constrained clustering methods. \n\nStrengths.\n\n1. The different ideas used in this paper, such as adopting a mixture of Gaussians as a prior over the VAE latent space for clustering, or the specification of the conditional prior over the cluster labels to integrate pairwise constraints, are not new by themselves. However, combining them together within a VAE framework is interesting and has not been investigated before to my knowledge.  \n\n2. The paper is well written, and the proposed method is clearly motivated and described.  \n\n3. Experiments are conducted on various data types.\n\nWeaknesses\n\n1. The authors claim superior performance compared to recent constrained deep clustering models. However, looking at the results of Table 1, the proposed CVaDE and the C-IDEC baseline are tight, and the differences in performance do not appear to be statistically significant in most cases.\n\n2. It does not seem like a lot of efforts have been spent for hyperparameters setting. \n\n    a. For instance the same encoder-decoder architecture is used for all datasets, including image and text ones, even though the latter exhibit very different characteristics. In particular, the retained 4-layers architecture (500-500-2000-10) is too complex (very prone to overfitting) for a text dataset such REUTERS, which is extremely sparse, i.e., with very few nonzero entries.\n\n    b. There are important differences in the optimization-hyperparameters (e.g., batch size) used to train CVaDE and its building block VaDE. It would be useful to report the performance of VaDE when trained using the same settings as CVaDE.\n \n3. Despite being a work on constrained clustering, no results regarding the number of satisfied constraints are reported.\n\n4. The authors claim efficiency, but complexity analysis and training time comparisons are missing.\n\n5. Comparisons with baselines when the number of constraints varies are not reported.\n\n6. For the noisy labels experiment, integrating the noise level “q” in the specification of pairwise confidence level is not fair. In practice, we may not always have access to such information in a context of unsupervised learning.\n\nAdditional comments and questions. \n\n1. For tractability purposes, the cluster proportions are all set to be equal (1/K). It would be useful to investigate the impact of this assumption on datasets exhibiting very unbalanced cluster sizes. One possibility is to preprocess some of the considered datasets to create such case.\n\n2. Performance is assessed using Normalized Mutual Information (NMI) and Accuracy.  I would suggest reporting the Adjusted Rand Index (ARI) as well. The latter metric is particularly suitable in a context of constrained clustering, as it measures the proportion of pairs of objects clustered similarly according to both the predicted and the ground truth partitions. \n\n3. Have you considered conditioning the variational posterior on the constraint information G?\n\n4. Are you using a held-out test set for evaluation?   \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: We thank the authors for their detailed responses to reviewers, and for engaging in a constructive discussions.

As explained by the reviewers, the paper is clearly written and the method is novel. However, the novelty is to combine existing ideas and techniques to define an objective function that allows to incorporate cluster assignment constraints, which was considered incremental. Regarding quality, the discussion highlighted some possible improvements that the authors propose to do in a future version of the paper, and we encourage them to follow that direction. Regarding significance, although the experimental results are promising there were some concerns that the improvement over existing techniques is marginal, and that more experiments leading to a clearer message would be useful.

In summary, this is not a bad paper, but it is below the standards of ICLR in its current form.
Decision: Reject