Mixture of GANs for Clustering

1 Introduction

Clustering is a fundamental machine learning task that divides a data set into clusters, such that instances are similar in the same cluster but dissimilar in different clusters [Duda et al., 2012]. Clustering is often employed to analyze unlabeled data set, and has been widely applied, such as in recommendation systems [Li and Kim, 2003], computer version [Frigui and Krishnapuram, 1999], speech processing [Chen and Gopalakrishnan, 1998], etc.

Among numerous clustering methods, Gaussian mixture model (GMM) [McLachlan and Basford, 2004; McLachlan and Peel, 2004] is a very classical and elegant one, which has still being consistently improved (e.g., [Li et al., 2015; Raghunathan et al., 2017]). GMM is a linear combination of a set of Gaussian distributions. Its training process finds the best parameters of each Gaussian distribution as well as the combination weights, such that the mixture distribution best fits the data. The training process commonly follows the expectation-maximization (EM) procedure, which solves the parameters efficiently. While GMM has gained successful applications, it has a fundamental assumption is that the data is composed by Gaussian distributions. However, real data sets rarely satisfy this assumption, on which GMM can result in poor clusters. Therefore, mixture of models with more flexibility is appealing for clustering complex data sets.

∗This work is supported by National Key R&D Program of China (2017YFB1002201), Jiangsu SF (BK20170013), and Collaborative Innovation Center of Novel Software Technology and Industrialization.

Recently, the generative adversarial networks (GANs) [Goodfellow et al., 2014; Arjovsky et al., 2017; Chen et al., 2016] have attracted a lot attentions for its outstanding ability of capturing complex data distribution. GAN trains a generative network and a discriminative network simultaneously. The discriminative network is trained to separate the training data set from the generated data, while the generative neural network is trained to generate data indistinguishable from the training data. This adversarial process converges such that the generated data has a distribution close to the training data. GANs have achieved extraordinary performance in generating images, implying their ability to capture high-dimensional complex distributions.

The ability of modeling complex distributions making GAN a potential replacement of the Gaussian distribution for learning mixture models. However, we find that the replacement is not straightforward. The expectation-maximization (EM) procedure, which is commonly employed to train GMM, cannot be used on GAN directly. A key issue is that GAN models can be quite flexible, such that the training by the EM procedure immediately converges.

In this paper, we propose to use the ϵ-expectationmaximization (ϵ-EM) procedure to train the GAN mixture model (GANMM). The ϵ-EM procedure differs from the EM procedure in that the expectation is not fully accurate but with an ϵ error. The ϵ-expectation is implemented by learning a classifier to separate the clusters. Meanwhile, a controlling of the ϵ error can still guarantee the convergence of the procedure, and it can effectively train the GANMM. Experiments on MNIST as well as some UCI data sets show that the proposed GANMM with the ϵ-EM procedure can result in superior performance to GMM and some other state-of-the-art clustering approaches.

2 Background

2.1 GaussianMixture Model

Gaussian mixture model (GMM) is a popular unsupervised learning technique. A Gaussian mixture model consists of N Gaussian components. The Gaussian components are combined using linear combination to form a distribution p(x),

where x is a d-dimensional random vector, the i-th Gaussian component has the mean µi ∈ Rd and the covariance matrix Σi ∈ Rd×d , and αi is the weight for the i-th Gaussian component satisfying ∑Ni=1 αi = 1 and ∀i, αi ≥ 0.

Learning GMM requires to find the best parameters µi, Σi and αi, such that the data is best fitted. The expectationmaximization procedure is commonly employed to solve this problem.

2.2 Expectation-Maximization Procedure

Expectation-Maximization procedure is a general method for parameter estimation. Generally, consider observable variables X with observed instances D = {x1, x2, ..., xM}, and hidden variables Z. Our probabilistic model with parameters θ (θ = {αi,µi,Σi} for GMM) gives the joint probability p(X, Z|θ) to the variables. The parameter estimation of θ is by maximizing the log-likehood

For GMM, we know the log-likelihood is

A simple derive of the EM procedure is by expanding the log-likelihood including a valid probability distribution q(Z),

where KL(q||p) is the KL-divergence between the two distributions. Due to the expansion of the log-likelihood into two terms, the maximization can be carried in two alternative E-steps and M-steps.

The E-step, given the current parameters θ(t) , matches the distribution q(Z) to p(Z|D, θ(t) ), so that KL(q||p) reaches its minimum at zero and

For GMM, the E-step finds a guess of q(Z) according to the posterior

in which zij = 1 if and only if xj is generated by the i-th Gaussian model.

Then the M-step is to maximize LL(θ) by maximizing the the non-constant term

For GMM, we know the probability that an instance xi is generated by the k-th Gaussian model is

Letting Mk = ∑Mi=1 γ(i, k), we can update α, µ and Σ as

The E-steps and M-steps iterate until the convergence. The convergence of the EM procedure has been well addressed. Including the convergence properties of EM on finite mixture models [Jordan and Xu, 1995], the link between EM procedure and gradient methods via the projection matrix [Xu and Jordan, 1996], and more recently, the increase of the likelihood along any EM sequence [Bouveyron and Brunet, 2012], and the statistical consistency of parameter estimation for GMM [Xu et al., 2016].

2.3 Generative Adversarial Network

Generative adversarial network (GAN) [Goodfellow et al., 2014] is a class of approaches that train neural network models to generate data very similar to the training data. GAN commonly consists of two networks competing with each other in a zero-sum game framework. The objective function of GAN is presented as [Goodfellow et al., 2014]

where G is the generator that takes input of a noise z from a noise distribution pz and outputs a sample, D is the discriminator, and pr is the distribution of the training data.

The initial GAN could be hard to train as it was delicate and unstable. Soon following GAN, many variants have emerged. For examples, the DCGAN [Radford et al., 2015] employs deep convolutional neural networks for generating high quality pictures; the f-GAN [Nowozin et al., 2016] use the f - divergence to train GAN; and the Wasserstein GAN (WGAN) [Arjovsky et al., 2017] choose to minimize an efficient approximation of the Earth-Mover distance to improve the performance of GAN.

GANs have shown very strong ability at capturing complex data distributions, such as images and audios from raw features. Therefore, GANs can be a useful replacement of the simple Gaussian model for complex data clustering.

3 GANMixture Model

Early Convergence of EM Procedure

We use GAN models instead of Gaussian models in learning mixture models for capturing clusters of complex data, while keeping the loss function unchanged. However, it is not straightforward to train GAN mixture models (GANMM) as that in GMM. To illustrate the problem, let us recall the EM procedure. As the log-likelihood is expanded in (1), the E-step matches the distribution of the hidden variable (i.e., clusters) with the posterior probability of the current model, i.e., q(Z) = p(Z|D, θ(0) ) from any initial model θ(0) . Then the M-step solves the parameters θ(1) from the resulted loglikelihood

Note that, if our model can be arbitrarily capable, the model maximizing L(q, θ) will have the extreme value that p(z(0) |D, θ(1) ) = 1 for z(0) = argmaxz p(z|D, θ(0) ) and otherwise 0, and p(D|θ) = 1.

In the next iteration, we will have q(Z) = p(Z|D, θ(1) ) and solves θ(2) such that p(z(1) |D, θ(2) ) = 1 for z(1) = argmaxz p(z|D, θ(1) ) and otherwise 0. Noticed that

we have θ(1) = θ(2) , and thus the procedure has converged. Therefore, the EM procedure will converge too early if the model is of very high capacity. That would be likely to happen for using GANs as the model.

ϵ-Expectation-Maximization Procedure

To avoid the early convergence of the EM procedure, one way is to avoid that the model fits the current guess of the hidden variables too well. Our idea is to introduce some error in the E-step, i.e., an ϵ-E-step with

By Eq.(1), we now have

and thus

Since the M-step is reserved, we still have

which means L(q(t-1) , θ(t) ) ≥ L(q(t-1) , θ(t-1) ). Therefore,

which shows that the ϵ-E-step can lead to an amount of loss of the log-likelihood. However, if we keep lim t→+∞ ∑t-1 i=0 ϵi < ∞, there exists C > 0 such that for all t > C, LL(θ(t) ) ≥ LL(θ(t-1) ) and thus the procedure converges. The above procedure is call ϵ-EM.

GAN Mixture Model

To implement the ϵ-EM procedure, we need an unfitted model for the expectation at some beginning steps. We restrict that the distribution of the clusters q(t) in a bounded hypothesis space Ht. Then, ϵt = minq∈Ht KL(q||p(t) ). Given the power of the M-step, it is easy to see that as long as ∀t : Ht ⊆ Ht-1 and |Ht| > 0 (i.e., the ϵ-E-step cannot be quite adversarial, the M-step will fit the data and eliminate the error), the finite accumulated error that limt→+∞ ∑t-1 i=0 ϵi < ∞ is guaranteed.

In the above, finding q(t) by the criterion minq∈Ht KL(q||p(t) ) inspires us to train a classifier with moderate complexity (i.e., to control the hypothesis space Ht) to fit the current guess of the cluster assignment. Therefore, we propose the GANMM training approach using the ϵ-EM procedure as follows.

ϵ-E-step: (1) From the current model θ(t) , sample a data set S(t) = {(˜xi, yi)ni=0 } from the GAN generators, while ˜xi is the data point generate by k-th generator and yi = k. (2) Train a (not so perfect) classifier hq from S. (3) Assign the cluster of each training instance xi by the training data by the classifier, i.e., hq(xi).

M-step: For the clustered data D = {D1,D2, . . . ,DN}, train the i-th GANmodel on Di for several iterations.

We run the ϵ-E-step and the M-step alternatively until convergence. The GANMM architecture is shown in Figure 1.

Implementation Details

GAN model: Since the original GAN approach proposed in [Goodfellow et al., 2014] has some limitations such as missing modes, we employ the Wasserstein GAN (WGAN) [Arjovsky et al., 2017] to train our GAN models, which implemented from https://github.com/igul222/ improved_wgan_training. WGAN optimize the two losses iteratively

Initialization: GMM usually starts from a random parameter initialization. However, for a random parameter initialization of GANMM, it is highly possible that all training data is assigned to one cluster, resulting in a bad clustering. We therefore start from a random assignment of training instances to clusters, and then learn each GAN model from each cluster, and continue the ϵ-EM procedure.

Algorithm 1 GAN mixture model learning algorithm

Require:

α: learning rate.

m: training set size.

N: cluster number.

nepoch: number of epoch for GANs.

σt, number of augmented data points.

1: randomly divide D into {D(0) 1 ,. . . , D(0) N }

• 2: θ(0) D(0) i , θ(0) Gi ← trainWGAN(D(0) i , nepoch) for each i = 1, . . . , N
• 3: t = 0
• 4: while θE not converged do
• 5: t = t +1
• 6: S = {(˜xi, yi)}mi=1 is sampled from{Gj}Nj=1 each with probability |D(t-1) i |/|D|.
• 7: gθh ←∇θh [ 1m ∑mi=1 cross entropy(fθh (˜xi), yi)]
• 8: θh ← θh +α· RMSProp(θh, gθh )
• 9: assign D as {Di}Ni=1 by using hq(D; θh)
• 10: for i = 1 to N do

11: add σt instances fromD-Di with highest posterior for cluster i by hq to Di

• 12: θ(t) Di , θ(t) Gi ← trainWGAN(D(t) i , nepoch) for each i = 1, . . . , N
• 13: end for
• 14: end while

Dealing with imbalanced classification: Since we employed a ϵ-E-step classifier trained from GAN generated samples, the classifier is easy to assign clusters with imbalanced instances, particularly at the beginning of the procedure. The imbalance could get reinforced through the procedure. As a result, some GAN models receives more and more data and the remaining fewer and fewer.

To fix this issue, we first make sure that every GAN model generates the same amount of data for training the ϵ-E-step classifier. Moreover, we allow a GAN model explore new by augmenting their training data. After the assignment of clusters, D = {D1 , . . . , DN }, we augment each cluster data set Di by adding an amount of instances fromD-Di with the highest posterior probability of belonging to the i-th cluster according to the output of the classifier. The amount of the augmented data is reducing along the procedure for the convergence.

An implementation of GANMM can be found at https: //github.com/eyounx/GANMM.

4 Experiments

We compare GANMM with GMM, a state-of-the-art deep clustering method Deep Embedded Clustering (DEC) [Xie et al., 2016], and the degrade version of GANMM trained using EM procedure (where the E-step uses the discriminators to assign the clusters). Note that DEC was originally proposed to operate in the embedded space by an autoencoder. For a fair comparison, we have tested them both in the raw features space and the embedded space. The implementation of DEC is from https://github.com/fferroni/DEC-Keras. As for GANMM, we don't modify the WGAN implementation, and the classifier has two convolution layers and two dense layers on the raw feature data sets. Meanwhile, we use only the two dense layers in the generator, discriminator and the classifier on the embedded feature data sets.

Evaluate Metrics

Since clustering results are hard to be measured objectively, using the data with oracle labels (note that the original labels themselves usually not purposed for clustering), we employ three metrics: purity, Adjusted Rand index (ARI) and Normalized Mutual Information (NMI).

Purity is the average of the portion of the largest class in each cluster, i.e.,

where mi is size of cluster i, and mij is the number of class j instances in cluster i. Purity lies in between 0 and 1. Higher purity indicates that each cluster is more concentrated.

ARI considers the number of instances that exist in the same cluster and different clusters.

where m11 is the number of pairs of instances that are in the same cluster and have the same oracle label, and m00 is the number of pairs of instances that are in the different cluster and have the different oracle labels. ARI lies in between 0 and 1. High ARI means that instances are clustered more correctly.

NMI can effectively measure the amount of statistical information shared by random variables representing the cluster assignments and the oracle labels [Fahad et al., 2014].

where dh is the number of instances in class h. cl denotes the number of instances in cluster l. And dh,l is the number of instances in cluster l which have ground-truth label h. NMI also lies in between 0 and 1 and high NMI means cluster assignments matches ground-truth label assignments well.

4.1 OnMNIST Dataset

We first compare the methods on the classical MNIST dataset [LeCun et al., 1998]. It is a handwriting digital dataset containing 60,000 images of size 28 by 28 pixels consist of 10 classes from digit '0' to '9'.

Clustering in Raw Feature Space

In the raw 28 by 28 pixels feature space, we test the clustering performance of each method, which is a challenging task as the algorithm is required to extract features and find the clusters simultaneously. The experiments are repeated 10 times to report the means and standard deviations, as listed in Table 1.

We can observe that GANMM has significantly higher scores than all other methods on all three metrics. It achieves twice purity and triple ARI and NMI of the runner-up. DEC

(in this experiment without a fine-tuned stacked auto-encoder) performs overall similar with GMM, which is slightly worse in purity and slightly better in ARI and NMI. Meanwhile, GANMM (EM) has the worst performance in purity and ARI.

To see more closely, we list the purity results of these methods on MNIST datasets in a single experiment in Table 2. First, counting the majority of the oracle label in each cluster, GANMM and GMM each loses one label ("9"), DEC loses three labels ("2", "5", "6"), and GANMM (EM) loses the most labels ("0", "4", "5", "8"). Then from the number of instances in each cluster, GANMM and GMM achieve related balanced clusters, DEC has small (<2,000) and large (>10,000) clusters, and GANMM (EM) is the worst with a cluster eliminated. These results show that GANMM achieves similar properties with the classical GMM. Meanwhile, GANMM achieves significantly higher purity in clusters than all the other methods, from 0.5666 to 0.9379.

This experiment shows that GANMM has an outstanding ability to deal with complex data directly, without any extra pre-process step. Comparing with the inferior performance of GMM and DEC, we can owe the ability of GANMM to the employment of the GANs that can capture complex distributions. Comparing with the degraded performanced of GANMM (EM), it shows that the ϵ-EM procedure is crucial to iterate the GANMMmodels for a good convergence.

Since GANMM is composed of generative models, we can easily observe GANMM by generating images from it. A set of generated images by GANMM and GANMM (EM) are shown in Figure 2. Images in the left two columns are generated by the ten clusters of GANMM and right two columns are generated by GANMM (EM). Each block is generated from one of the GAN model.

It can be observed that the digits generated by GANMM are obviously more regular than those generated by GANMM (EM). Although we observed from Table 2 that GANMM losses the digit "9", we can find that it actually generated "9" but mixed with digits "4" and "7". Meanwhile, some digits generated by GANMM (EM) are not in good shape, which is due to the very small clusters it receives.

On Different Data Scales

We then investigate how sensitive GANMM is to the data scale. We experimented on MNIST dataset using different data scales. We train on 100%, 50%, 10% of MNIST dataset separately and assign the clusters on the whole dataset. In this experiment, we also directly run the clustering methods in the original raw feature space. We repeat the experiments five times to report the means and standard deviations. The results are shown in Figures 3, 4, and 5.

It can be observed that even on 10% of the data, i.e., 6, 000 instances in all, GANMM still have significantly superior performance to the other methods, on all the three metrics. Meanwhile, we can still observe some performance drops of GANMM as the data size reduces. Since GANMM can fit complex data distribution, too few instances would result in worse fitted model. The other approaches are less effected by the data scales, as their performance has already been quite low compared with GANMM.

Clustering in Embedded Feature Space

We also compare the methods in an embedded feature spaced. We use a fine-tuned stacked auto-encoder (SAE) to transform the original pictures to 10 dimensional feature vectors. The SAE is the same as in the DEC's paper [Xie et al., 2016]. The results of the compared methods are shown in Table 3.

GANMM (EM) has the worst performance in the embedded feature space, while the performance of GMM and DEC has been drastically improved from the raw feature space. This observation implies that GMM and DEC seriously rely on feature pre-process in applications, and would work in low dimensional spaces. Still, GANMM achieves better performances in all metrics. GANMM improves from DEC by around 0.02 on purity and NMI, and 0.03 on ARI. These improvements can be significant given the high values of the baseline scores. The result reveal that GANMM can work well not only in raw feature spaces but also in highly abstracted embedded spaces.

4.2 OnMore Datasets

We finally compare the clustering performance on two UCI datasets [Dua and Karra, 2017]. They are Image Segmentation dataset and Artificial Characters dataset. The Image Segmentation dataset is an image dataset described by highlevel numeric-valued attributes. It contains 2310 instances with 19 features. It have 7 classes, which are BRICKFACE, FOLIAGE, CEMENT, WINDOW, PATH, SKY, GRASS. The Artificial Characters dataset is artificially generated by using first order theory which describes structure of ten capital letters of English alphabet. It contains 6000 instances with 6 features. It has 10 classes, which are A, C, D, E, F, G, H, L, P, R.

Tables 4 and 5 present the experiment results. It can be observed that in all cases and all metrics, GANMM consistently has a better performance than the other methods. Note that the improvement of the metric scores can be quite significant in both data sets. These results imply that GANMM can be applied in various situations.

5 Conclusion

In this paper, we propose a mixture model with GAN as the components, i.e., GANMM. Mixture models such as Gaussian mixture models are very popular tools for data analysis. However, traditional distribution models, such as Gaussian distribution, is lack of flexibility for complex data. The recently developed GAN model has shown outstanding performance to model complex distributions. Therefore, GANMM can serve as an alternative mixture model to GMM for complex situations. We noticed that GANMM is hard to be trained by the classical EM procedure. We thus propose to use the ϵ-EM procedure, where the ϵ-E-step, implemented by a classifier learned from the clusters, introduces some controllable error so that the optimization of GANMM can continue. Several experiment results show that GANMM can drastically improve the clustering performance on complex data from GMM as well as some state-of-the-art approaches, in both of the raw feature space and abstracted embedded feature space.