Title: UNSUPERVISED CLASSIFICATION INTO UNKNOWN NUMBER OF CLASSES

Abstract: We propose a novel unsupervised classification method based on graph Laplacian. Unlike the widely used classification method, this architecture does not require the labels of data and the number of classes. Our key idea is to introduce a approximate linear map and a spectral clustering theory on the dimension reduced spaces into generative adversarial networks. Inspired by the human visual recognition system, the proposed framework can classify and also generate images as the human brains do. We build an approximate linear connector network C analogous to the cerebral cortex, between the discriminator D and the generator G. The connector network allows us to estimate the unknown number of classes. Estimating the number of classes is one of the challenging researches in the unsupervised learning, especially in spectral clustering. The proposed method can also classify the images by using the estimated number of classes. Therefore, we define our method as an unsupervised classification method.

1. INTRODUCTION:

Image classification has been one of the most important research in machine learning and artificial intelligence. For the predefined number k of classes, the classification models based on deep learning have performed well that the test accuracy is better than humans (Geirhos et al., 2017; He et al., 2016; Russakovsky et al., 2015; Szegedy et al., 2015) . This result is, however, true only when the number of classes, k is predefined and we use the supervised learning with entire ground truth labels. Humans learn visual information by memorizing the compressed information (features) in the brain, reconstruct the object, and recognize the difference between objects. This capability allows humans to classify data where the number of classes is unknown into the reasonable numbers of classes. In this paper, we propose a method to mimic such human capability.

The main contribution of the proposed framework consists of two parts. We first show that there exists a approximate linear map between two separated neural networks of Generative Adversarial Networks (GANs). Secondly, we prove that the number of classes in a latent space is the same as the number of classes in the original space in terms of the multiplicity of eigenvalue 0 of a Laplacian matrix in spectral clustering theory. By combining the results, We derive a novel unsupervised classification framework, which estimates the number of classes k and then extract k vectors representing each class. With the framework, the approximate linear map between two networks can induce the information of connected components in a data graph.

The latent variable model is commonly used in the generative models. Variational auto-encoders (VAEs) (Kingma & Welling, 2013) and GANs (Goodfellow et al., 2014) are a few of the most famous cases that learn the data distribution successfully. GANs randomly samples the latent variables that are used to train the data distribution so we cannot figure out which latent variable generates a result that we are interested in. To avoid the drawback by random sampling, auxiliary conditions on latent variables were introduced (Chen et al., 2016; Mirza & Osindero, 2014) . Introducing a label information into the condition of the estimated data probability is highly effective in classification where a data point x came from, however this method is not a unsupervised learning.

Spectral clustering is one of the most popular clustering algorithm that outperforms other wellknown clustering algorithms (Ng et al., 2002; Shi & Malik, 2000) . Despite high performance, spectral clustering is difficult to use because it requires the full dataset that have very large N data points. In this case, the dimension of the Laplacian matrix is N × N and it takes at least O(N 3 ). Therefore, we need a novel dimension reduction technique to use spectral clustering in practical applications (Elhamifar & Vidal, 2009; Ji et al., 2017; Law et al., 2017; Shaham et al., 2018) .

Recent image classification methods are based on supervised learning, in which a learning model processes a dataset consisting of pairs of an image and its ground-truth label. This training dataset usually consists of more than 10 K data point, some part of which need to be used for crossvalidation. It also takes a lot of costs to produce a reliable training dataset. In addition, estimating the number of classes is a key aspect of unsupervised learning. There have been a few heuristic method (Zelnik-Manor & Perona, 2005; Von Luxburg, 2007) . We propose a method to find the number of classes analytically.

The main concepts of spectral clustering, GANs and the self-expressiveness property will be introduced Section 2. We prove the preliminary propositions that allow us to classify data with unsupervised learning methods in Section 3. Finally, we propose a unsupervised classification algorithm and test our algorithm in Section 4.

2. PRELIMINARIES:

We first review cycle-consistent adversarial networks and sparse subspace clustering that we will use when extracting indicator vectors. We also overview the basic probabilistic property between a classification model and a generative model, which can be used as tools to generate indicator vectors.

2.1. CYCLE-CONSISTENT ADVERSARIAL NETWORKS:

Generative Adversarial Networks (GANs) is a generative model that a generator network learns a data distribution implicitly (Goodfellow et al., 2014) . GANs is a two player minimax game with two neural networks: a discriminator D and a generator G. The discriminator D(x) is a probability measure that an input x follows the data distribution p data (x) rather than the generator's distribution p g . The generator G is a mapping from the latent space z ∼ p z to the data space. This minimax game can be represented as a stochastic optimization problem with value function given by

min G max D V (D, G) = E x∼p data (x) [log D(x)] + E z∼pz(z) [log (1 -D (G (z)))] .

(1)

The cycle-consistent adversarial networks (cycleGANs) is a variant of GANs, which learns how to translate an representation from a source domain S to a target domain T without a paired dataset (Zhu et al., 2017) . The cycle-consistency states that two mappings G : S → T and F : T → S encode the right permutation of images in S and T , so that, for an arbitrary data point s ∈ S, the mapping from S to T and back again, F (G(s)), should be the same as s. This property encourages adversarial networks G and D to have a connection between generated images and input data. We adopt two cycle consistency loss for the forward map and the backward map to learn a connection between two high-level representation domain in G and D.

2.2. SPARSE SUBSPACE CLUSTERING:

Sparse subspace clustering is a clustering algorithm that is based on spectral clustering. Spectral clustering has many variants depending on the similarity measure, Gaussian kernel similarity function (Ng et al., 2002) , k-nearest neighbor graphs, -neighborhood graph. A similarity measure defined on the similarity graph G = (V, E) is a pairwise metric between two data points (nodes) in a dataset and the similarity w ij of two data points x i , x j is equal to or greater than 0. The similarity w ij is also same as w ji because the above similarity graph is defined as an undirected graph. The similarity matrix W is composed of the elements which correspond to the similarity measure w ij respectively and then W is symmetric. See more details about spectral clustering in (Von Luxburg, 2007) .

Sparse subspace clustering (Elhamifar & Vidal, 2009) uses a novel similarity matrix that is based on the self-expressiveness property. When we assume that the data space is a union of linear subspaces S = ∪ k l=1 S l , we can express an arbitrary data point in the dataset as a linear combination of other data points in the dataset, where the coefficients of the data points in the same subspace are non-zero and others should be 0 (Elhamifar & Vidal, 2009; Ji et al., 2017) . Formally, each data point y i ∈ S can be reconstructed as y i = N j=1 c ij y j = Yc i , where c ii = 0, N is the size of the dataset, 

c i := [c i1 c i2 • • • c iN ] T is the coefficient vector of y i and Y = [y 1 y 2 • • • y N ]

is the dictionary matrix. The sparse solution of c i indicates that the node i is in the same subspace as the node j if the element c ij is non-zero. In this paper, we expand the notion of the self-expressiveness property to reduce the dimensionality of L in Section 3.3.

3. GRAPH LAPLACIAN OF THE CONNECTOR NETWORK:

We first introduce our proposed architecture of adversarial networks. As an autoencoder point of view, we can consider two adversarial networks as autoencoder. We build a connector network between two networks to improve cycle consistency, and extract the information of connected components (as shown in Figure 1-b ). By training with the cycle-consistency loss, we can make the tuples (Z, X, H) for each data point X in a given dataset. Then, we show the relation between the spectral clustering and unsupervised classification. In order to show the relationship, we prove the dimension reduction of the mutual expressiveness property in Section 3.3.

3.1. DISENTANGLING UNFOLDS AND EXPANDING THE VOLUME OF MANIFOLD:

Deep neural networks learn a high-level abstract representation of a data manifold and a well trained abstraction can disentangle the underlying factors of variation (Bengio et al., 2007) . These properties allow interpolation between data samples more naturally and smoothly. (Bengio et al., 2013) studied the disentangling effect and proposed three hypotheses on the shape of manifolds in different representation domains. These hypotheses are verified by several empirical results (Goodfellow et al., 2009; Glorot et al., 2011) . The three hypotheses are summerized as follows.

• The deeper representations can better disentangle the underlying factors of variation.

• Disentangled representations unfold the manifolds near which raw data concentrates irregularly, and expand the relative volume occupied by high-probability points near these manifolds. Then these representations are with greater convexity. • The underlying class factors of variations will be better disentangled than other factors, so the deeper layer has better discriminant capability of classes.

In our proposed architecture, there are two high-level (deeper) representation spaces which are called as feature spaces. These feature spaces fill the space more uniformly than the pixel space X. H and Z also have smoother density. Therefore, H and Z have greater convexity than X and it permits linear combination on these two manifolds in the feature spaces H and Z, are the two manifolds are more convex than the manifold in the pixel space X. By manifold hypothesis, different class manifolds are well-separated by regions of very low density (Cayton, 2005) . The feature spaces are high-level representation spaces so that the density is unfolded and a linear combination of features generates amore natural result in the pixel space Bengio (2014) . Now, we can define the effective basis of the subspace for each class. In the feature spaces, each class manifold is assumed to have the enough convexity. The class manifolds are well-separated, and show good discriminant capability. Using both properties, we can build the effective basis for each class subspaces and generate the original space by a direct sum of these subspaces, where the subspaces are orthogonal. We empirically tested an effective basis as shown in figure 3 . Randomly sampled features in a subspace of the data space can be an effective basis, and are possible to generate all data points in the same subspace. The features in a different subspace cannot generate the given data samples. We can estimate the effective dimension with the number of the effective basis. We then can generate orthogonal subspaces of the entire classes if the effective dimension is small enough than the dimension of feature spaces.

3.2. CONNECTOR NETWORK AND CYCLE CONSISTENCY:

We will study the relationship among 3 different spaces, Z, X and H in the proposed architecture.

As shown in figure 1 -(b), we can consider two adversarial networks as a decoder and an encoder of an auto-encoder respectively (Berthelot et al., 2017; Zhao et al., 2016) . The discriminator network D encodes the pixel space X to the feature space H, and the generator network G decodes the feature space Z to X. We define the connector network C which maps from H to Z. The map C between two feature spaces will be trained by the cycle consistency loss to obtain the tuples (Z, X, H) with the correct permutation, where all the elements are in the same-class manifold and shares the same learned features. Cycle consistency loss tends to minimize the difference between an arbitrary point and the returned point after traveling other representation domains. This cycleconsistency objective permits inverse maps between all representation spaces. When we apply the forward cycle-consistency loss z -C(D(G(z))) 1 and the backward cycle consistency loss x -G(C(D(x))) 1 , the maps between all pairs of neighboring spaces become unique. Therefore, the feature-invariant one-to-one maps among G, C, D can be induced. All elements of an arbitrary tuple (Z, X, H) share same class features as shown In figure 1-(a) . We now have the following assumption.

Assumption 3.1. All elements of the cycle consistent tuple (Z, X, H) shares the identical factors, such as class factor and other factors (e.g. rotation and brightness).

As shown in fig 3 -(c, d ), we can conjecture that each class subset is closed and the linear combinations in the certain class subset are also in the class because each class manifold is unfolded and expanded in Z and H. In addition, we showed there exists the effective basis for each class. By This assumption is more tight and realistic than the union of linear subspaces in Elhamifar & Vidal (2009) . We can also conjecture that the feature space H and Z are descried as the direct sum of H i and Z i respectively. Now, we can show the existence of an approximate linear map C from H to Z. Lemma 3.1. There exists a compact and convex linear map

C i from S Hi to S Zi , If C i is closed.

Proof.

1. By the assumption 3.2, the class subset S Hi and S Zi are convex. Let h 1 , h 2 ∈ S Hi and z 1 = C i h 1 , z 2 = C i h 2 . We know that C i is linear, then

tz 1 + (1 -t)z 2 = tC i h 1 + (1 -t)C i h 2 = C i (th 1 + (1 -t)h 2 ).

(2)

EQUATION

We know that C i and h are finite. Therefore S Zi is also compact. Theorem 3.1. By the assumption that the data space are the direct sum of orthogonal class subspaces, the map from H to Z can be written as a block matrix, of which block component consists of C i . C can maps from all class subset S Hi to S Zi .

Proof. By Lemma. 3.1., C i is a compact and convex linear map from H i to Z i . H and Z are the direct sum of the orthogonal subspaces H i and Z i respectively. Therefore C can be represented as a block diagonal matrix for some ordered basis.

3.3. MUTUAL EXPRESSIVENESS PROPERTY AND DIMENSION REDUCTION:

As we discussed in Section 2, the self-expressiveness property shows that we can express an arbitrary data point as a linear combination of other N data points. By modifying this property slightly, we can write each data point x as a linear combination of N sampled data points α = {x 1 , x 2 , • • • , x N } from the data space X. This fact allows us to generate a set of feature variables, which satisfies the self-expressiveness property. The self-expressiveness property implies that the generated data points are in the class manifolds. Now, we relax the self-expressiveness property to generalize the problem. We divide the latent space H into H 1 , • • • , H l where the self-expressiveness only satisfies in each H i not in H -H i . We also know that it is possible to discard redundant coefficients in the selfexpressiveness expression by optimizing the matrix of coefficients (Elhamifar & Vidal, 2009) , so there exists at least one sparse solution of x where most coefficients are zero. By observing this property, it is expected that the number of non zero coefficients approaches the dimension of latent space, m. That is because N is much higher than dim X, and X is a m-dimensional manifold. Image clustering methods, for instance, treat a dataset where the number of data points is much larger than the dimension of data points so we can optimize a solution to have sufficiently many zero coefficients in the self-expressive linear combination. Theorem 3.2. From now on,

Z i = C i H i where Z i = (z 1 , • • • , z mi ) T and H i = (h 1 , • • • , h mi ) T .

Proof. By an observation on GANs, we have N i feature variables

β i = {h ij } 1≤j≤Ni for each 1 ≤ i ≤ l where D(x i ) = h i and N = N 1 + • • • + N l .

By the self-expressiveness property in H i , we can express each h i ∈ H i by the linear combination of

β i = {h 1 , h 2 • • • , h mi , h mi+1 , • • • h Ni }

where β i is a reordered set of β i and the coefficents of the linear combination {c mi+1 , c mi+2 , • • • , c N i } are zero. In other words, the ordered set

γ i = {h 1 , • • • , h mi } is enough to represent all points in the class manifold X i and Z i , which correspond to (Z i , X i , H i ), i.e. span(γ i ) = H i . Hence, we can choose C i by an m i × m i real matrix.

This theorem is empirically shown by the our effective basis conjecture. Now, we can conclude that the dim

Z i = dim H i = m i N i .

We define the connector network C as a ( m i ) × ( m i ) matrix. The similarity matrix is denoted by W = |C| + |C T |. Theorem 3.3. Let G be an undirected graph with non-negative weights. Then, the number of connected components A 1 , • • • , A k in G is the same as the multiplicity k of the eigenvalue 0 of L. If W is a k block diagonal matrix, then the multiplicity of the eigenvalue 0 of its Laplacian is also k.

Proof. the proof in (Von Luxburg, 2007) . By the definition of W ,the number of sub-block matrices in W is the same as the number of connected components.

We conclude that the numbers of classes are identical between spectral clustering and our method.

3.4. UNSUPERVISED CLASSIFICATION:

Now, we consider a unsupervised classification problem where there is no ground-truth label. For example, when the cross-entropy loss is applied in the supervised classification, we need pairs of input data and ground-truth probability mass p = [0, , 1, • • • , 0], which contains a single 1 at the ith element, i.e. the class index c = i, to estimate the difference between the prediction and the ground-truth. We can formally write the probabilistic interpretation as

EQUATION

, where x is a data point. If we assume that the numbers of data points in the whole classes are same, then P (c) is uniform. Then, for the given point x, P (x) is fixed so the we can measure P (c|x) by the estimating the likelihood P (x|c). In Section 3.3, we showed that the indicator vectors of the connected components are the eigenvectors of the Laplacian matrix L, which are corresponding to the eigenvalue 0. The components of the indicator vectors span the eigenspaces of the matched connected components respectively. The orders of components for the Laplacian matrix L C and the connector network C are identical by the definition in Section 3.3. Therefore, for all connected component A i , the indicator vectors 1 Ai = h ∈ H i spans the class subspace H i . The indicator vector itself, however, might not be in the class manifold because it can exist outside the boundary of the manifold. We find out that the changes of norms between H and Z are different by the class.

The connector network can be considered as a singular value decomposition for each class. This implies that each class data points move differently by the class. We define the mean vector of a class in H as h and the Gaussian noise n.

z 2 = Ch 2 = h T C T Ch (5) = (h + n) T C T C(h + n) (6)

The expectation of z 2 is,

EQUATION

, where n Z is the scaled noise in Z. We now assume that the distribution of z 2 follows a Gaussian with a variance σ n Z . Then, we can calculate the probability that z 2 is in the certain class. We also know that B = C T C is a normal operator, then B satisfies the following theorem. Theorem 3.4. |x T Bx| ≤ max{|λ| : λ is an eigenvalue of B} x 2 2 Proof. See in Chapter 5.6 of (Horn et al., 1990) .

By ordering the eigenvalue of B, we can find out the interval that z 2 lies in. This implies that the maximum eigenvalue of the sub-block matrix in B for z is in the above interval. This eigenvalue works as the indicator of classifying class. Therefore we can build of Gaussian distributions for z 2 with the mean λ h 2 and the standard deviation σ n Z .

4. UNSUPERVISED CLASSIFICATION INTO UNKNOWN k CLASSES:

In this section, we describe the loss function and the training algorithm of unsupervised classification into unknown k classes. It is known that estimating the number of classes k is hard and heuristic (Von Luxburg, 2007) . We find the empirical observation on the hint of k. Using the observation, we suggest a conjecture that helps to estimate the number of classes k in a certain case.

Algorithm 1 Unsupervised Classification into Unknown k Classes (UCUC)

1: for the number of iterations do 2:

Sample minibatch of m latent vectors z (0) , • • • , z (m) from prior p g (z)

3:

Sample minibatch of m data points

x (0) , • • • , x (m) from dataset 4:

Update the discriminator by ascending :

∇ θ d 1 m m i=1 log D x (i) + log 1 -D G z (i) +λ D x (i) -G C D x (i) 1 (9) 5:

Update the generator and connect by descending their stochastic gradients:

EQUATION

Update the connector network C with two cycle-consistency loss We found an interesting observation on the number of classes k. The eigenvalue λ of the graph Laplacian matrix equals to Ncut of the given graph (Shi & Malik, 2000) . In the ideal cases, we can assume that L is a block-diagonal matrix and each of blocks L i is a proper sub-graph Laplacian.

EQUATION

If there is no connection between subgraphs, then L is a perfect block-diagonal matrix and the multiplicity of the eigenvalue 0 is the same as the number of blocks. In the real world dataset, there exists quite large off-diagonal noise in the similarity matrix, as shown in the previous result. These non-zero off-diagonal elements make the eigenvalue zero only at the first eigenvalue and increase the Ncut of the graph gradually. We can consider the ith eigenvalue as the Ncut by the block diagonal matrix with i blocks, which is applied on the perturbed block diagonal matrix of which the underlying connected component is k. We now have the following conjecture on the pattern of eigenvalues. We assume that the off-diagonal elements have the same value and the dimensions of all eigenspaces are the same. Now, we estimate the number of classes k by starting from m k. We can consider the difference of Ncut between k-block diagonal matrix and m-block diagonal matrix as the the area of S m -S m ∩ S k , where S m = n 2 m and S k = n 2 k when the matrix size is n. As m increases, the difference of Ncut increases, but at k = m the value have the very small local minimum becuase two matrices are perfectly overlapped. Using this property we can derive the function of the difference of the Ncut over m as

EQUATION

where m ≤ k. if m > k, and switch m and k. This overlapped area is n 2 k at m = k trivially. The figure of the theoretical conjecture is in Figure -4a . This result can predict the empirical result of the pattern of the eigenvalue. Therefore, we can conjecture that the underlying number of classes is at the second deep local minimum.

5. EVALUATION:

We introduce the setting of experiments and the architecture of our adversarial networks (Radford et al., 2015) . For the smaller size of dataset, such as MNIST and CIFAR10, we reduce the size of kernels properly. We have the result the expectation of the estimated number of k is 10.2 for MNIST and 10.1 for CIFAR10. Now we use the unsupervised clustering accuracy (ACC) (Cai et al., 2011; Shaham et al., 2018) .

EQUATION

where l i is true label, c i is the ground-truth label, and π is the collection of permutations.

Algorithm ACC (MNIST) spectral clustering .717 SpectralNet .971 IMSAT .984 UCUC (ours) .735

Table 1 : Other methods have the ground-truth number of classes. UCUC is not given the number of classes. Other results are reported in (Shaham et al., 2018) . 

6. CONCLUSION:

We have proposed an unsupervised classification method that can automatically estimate the unknown number of classes k. Our method provides the learned class-features. The proposed method saves the tremendous cost of producing ground-truth labels in a large dataset. Figure 6 : We sample Z from the normal distribution, so the norm of z is smaller than h. In additino, we can observe that C changes not only the magnitude of the vector but also the angle. 

:



Figures and Tables:

Figure 1: (a) shows the mappings relation in our proposed method. (b) shows the architecutre of the our networks.

Figure 2: (a) shows the density of h for 1 and 2 MNIST, (b) shows the mean of h for entire MNIST classes

Figure 3: (a), (b) the generate images using the indicator vectors of Laplacian on C for MNIST and CIFAR10, (c) describes the linear combination using class 2 to generate 1 but failed. (d) is the generated image by the linear combination of the right features h for 1

11) 7: end for 8: Compute the moving average of each ith eigenvalue of normalized symmetric Laplacian matrix L sym = D -1 2 LD -1 2 and find the estimated number k by computing the second local minimum 9: Calculate the eigenvalues of C T C and find a matched class for an input 4.1 ESTIMATING THE NUMBER OF CLASSES k

Figure 4: a shows theoretical result of the estimated eigengap using the overlapped area of blockdiagonal matrices and Figure (b) and (c) shows the eigengap |λ k -λ k-1 | of the MNIST and CI-FAR10.

Figure 5: In the some range of noise, we can always generate the same class image. The magnitudes of noise for each class are different.

Figure 7: The left figure is the cosine values between the mean vector of each classes hi , zj . The right figure is the cosine values between hi , hj .

Figure 8: The left figure is the initial similarity matrix W , The right figure is the right permutated similarity matrix.

Peer review (iclr2019):
 ------------------------------------------ Summary ------------------------------------------ This paper performs unsupervised classification where the number of classes is unknown. The main idea is to use the CycleGAN framework such that one can reconstruct the original image by first moving to latent space that represents another class (via the connector network), then moving back to the original latent space and going back into image space using a generator. Experiments are conducted on MNIST and CIFAR. ------------------------------------------ Evaluation ------------------------------------------ The paper tackles an important problem: namely, unsupervised classification (i.e. clustering). I think the use cycle-consistency loss in an auxiliary latent space is quite clever. However, experimental results are lacking. Unsupervised clustering (even when number of classes is not known) is a very well studied problem in machine learning. The authors should compare against at least a few reasonable baselines. ------------------------------------------ Presentation ------------------------------------------ I found the presentation to be somewhat wanting. Section 3 is extremely confusing and in my opinion, not well-motivated. For example, why is self-expressivity important? Why can we assume propositions 3.1 and 3.2?