Year: 2018

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.

heading: 1 INTRODUCTION
text: 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 largeN data points. In this case, the dimension of the Laplacian matrix is N ×N and it takes at least O(N3). 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.

heading: 2 PRELIMINARIES
text: 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.

heading: 2.1 CYCLE-CONSISTENT ADVERSARIAL NETWORKS
text: 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 pdata(x) rather than the generator’s distribution pg . The generator G is a mapping from the latent space z ∼ pz 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) = Ex∼pdata(x) [logD(x)] + Ez∼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.

heading: 2.2 SPARSE SUBSPACE CLUSTERING
text: 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 wij of two data points xi, xj is equal to or greater than 0. The similarity wij is also same as wji 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 wij 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 = ∪kl=1Sl, 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 yi ∈ S can be reconstructed as yi = ∑N j=1 cijyj = Yci, where cii = 0, N is the size of the dataset,
ci := [ci1 ci2 · · · ciN ]T is the coefficient vector of yi and Y = [y1 y2 · · · yN ] is the dictionary matrix. The sparse solution of ci indicates that the node i is in the same subspace as the node j if the element cij 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.

heading: 3 GRAPH LAPLACIAN OF THE CONNECTOR NETWORK
text: 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.

heading: 3.1 DISENTANGLING UNFOLDS AND EXPANDING THE VOLUME OF MANIFOLD
text: 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 ir-
regularly, 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.

heading: 3.2 CONNECTOR NETWORK AND CYCLE CONSISTENCY
text: 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
the hypotheses (Bengio et al., 2013), we know that each class manifold has the compactness and the convexity. Now we can assume the following assumption. Assumption 3.2. Each class subspace Hi, where Hi ⊂ H are orthogonal, so as Zi where Zi ⊂ Z. We define sets for each class SHi and SZi in Hi, Zi respectively to be the the class manifolds which lies on the corresponding class subspaces. The sets SHi and SZi are compact and convex.
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 Hi and Zi 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 Ci from SHi to SZi , If ‖Ci‖ is closed.
Proof.
1. By the assumption 3.2, the class subset SHi and SZi are convex. Let h1, h2 ∈ SHi and z1 = Cih1, z2 = Cih2. We know that Ci is linear, then
tz1 + (1− t)z2 = tCih1 + (1− t)Cih2 = Ci(th1 + (1− t)h2). (2)
th1 + (1− t)h2 is also in SHi for t ∈ [0, 1]. Also, tz1 + (1− t)z2 is in SZi because SZi is convex. Therefore Ci is a convex linear map for all i.
2. If SHi is compact, then for h ∈ SHi , ‖h‖ is closed. Then z ∈ SZi is closed, because
‖z‖ = ‖Cih‖ ≤ ‖Ci‖‖h‖. (3)
We know that Ci and h are finite. Therefore SZi 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 Ci. C can maps from all class subset SHi to SZi .
Proof. By Lemma. 3.1., Ci is a compact and convex linear map from Hi to Zi. H and Z are the direct sum of the orthogonal subspaces Hi and Zi respectively. Therefore C can be represented as a block diagonal matrix for some ordered basis.

heading: 3.3 MUTUAL EXPRESSIVENESS PROPERTY AND DIMENSION REDUCTION
text: 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 ofN sampled data points α = {x1,x2, · · · ,xN} 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 H1, · · · , Hl where the self-expressiveness only satisfies in each
Hi not in H − Hi. 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 dimX , 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 ′iH ′i where Z ′i = (z1, · · · , zmi)T and H ′i = (h1, · · · , hmi)T .
Proof. By an observation on GANs, we have Ni feature variables βi = {hij}1≤j≤Ni for each 1 ≤ i ≤ l where D(xi) = hi and N = N1 + · · ·+Nl. By the self-expressiveness property in Hi, we can express each hi ∈ Hi by the linear combination of β′i = {h1, h2 · · · , hmi , hmi+1, · · ·hNi} where β′i is a reordered set of βi and the coefficents of the linear combination {cmi+1, cmi+2, · · · , cNi} are zero. In other words, the ordered set γi = {h1, · · · , hmi} is enough to represent all points in the class manifold Xi and Zi, which correspond to (Zi, Xi, Hi), i.e. span(γi) = Hi. Hence, we can choose C ′i by an mi ×mi real matrix. This theorem is empirically shown by the our effective basis conjecture. Now, we can conclude that the dimZi = dimHi = mi Ni. We define the connector network C as a ( ∑ mi) × ( ∑ mi) matrix. The similarity matrix is denoted by W = |C|+ |CT |. Theorem 3.3. Let G be an undirected graph with non-negative weights. Then, the number of connected components A1, · · · , Ak 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.

heading: 3.4 UNSUPERVISED CLASSIFICATION
text: 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
P (c = i|x) = P (c = i)P (x|c = i) P (x)
(4)
, 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 LC and the connector network C are identical by the definition in Section 3.3. Therefore, for all connected component Ai, the indicator vectors 1Ai = h ∈ Hi spans the class subspace Hi. 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 = hTCTCh (5) = (h′ + n)TCTC(h′ + n) (6)
The expectation of ‖z‖2 is, E[‖z‖2] = h′TCTCh′ + E[nTCTCn] (7)
= h′TCTCh′ + E[nTZnZ ] (8)
, where nZ is the scaled noise in Z. We now assume that the distribution of ‖z‖2 follows a Gaussian with a variance σnZ . Then, we can calculate the probability that ‖z‖2 is in the certain class. We also know that B = CTC is a normal operator, then B satisfies the following theorem. Theorem 3.4. |xTBx| ≤ max{|λ| : λ is an eigenvalue of B}‖x‖22
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 σnZ .
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 pg(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 [ logD ( 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:
∇θg 1
m m∑ i=1 [ log ( 1−D ( G ( z(i) )))] + λG ∥∥∥z(i) − C (D (G(z(i))))∥∥∥ 1
(10)
6: Update the connector network C with two cycle-consistency loss ∇C [∥∥∥z(i) − C (D (G(z(i))))∥∥∥ 1 + ∥∥∥x(i) −G(C (D (x(i))))∥∥∥ 1 ] (11)
7: end for 8: Compute the moving average of each ith eigenvalue of normalized symmetric Laplacian matrix Lsym = D − 12LD− 1 2 and find the estimated number k̂ by computing the second local minimum
9: Calculate the eigenvalues of CTC and find a matched class for an input
4.1 ESTIMATING THE NUMBER OF CLASSES k
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 Li is a proper sub-graph Laplacian. 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 Sm − Sm ∩ Sk, where Sm = n 2 m and Sk = n2
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
Sm ∩ Sk = n2( 1
k2 (k −m+ 1) + m−1∑ i=1 [( i m − b ik m c1 k )2 + ((1 + b ik m c) 1 k − i m )2], (12)
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.

heading: 5 EVALUATION
text: 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).
ACC(l, c) = 1
n max π∈Π n∑ i=1 1{li = π(ci)}, (13)
where li is true label, ci is the ground-truth label, and π is the collection of permutations.

heading: 6 CONCLUSION
text: 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.

heading: A SUPPLEMENTARY MATERIALS
text: A.A MODEL ARCHITECTURE
A.B ADDITIONAL EXPERIMENTAL RESULTS
In the latent space H,Z, the each class subset has a Gaussian distribution, which implies the subset is convex. We observed that the connector networks Ci are not identical among the whole classes. Each connector network Ci is decomposed into an unique singular value decomposition matrices. Therefore, we can extract the difference for each class by analyzing the eigenvalues in Section 3.4.
We can observe thatW is a near block diagonal matrix, of which off-diagonal elements are not zero. This leads to the summation of some residue weights which should be zeros theoretically. When the number of connected components are matched, those residues are no longer summed up. Therefore, the deep local minimum in the eigengap exists.

Review summaries:
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.

This paper develops an unsupervised classification algorithm using the idea of CycleGAN. Specifically, it constructs a piece-wise linear mapping (the Connector Network) between the discriminator network and the generator network. The learning objective is based on the cycle-consistency loss. Experiments show that it can achieve reasonable loss. This paper addresses an important problem, namely, unsupervised image classification, and may present interesting ideas. However, the paper is not in a good shape for publication in its current form.