Deep Subspace Clustering Networks

Introduction

In this paper, we tackle the problem of subspace clustering – a sub-field of unsupervised learning – which aims to cluster data points drawn from a union of low-dimensional subspaces in an unsupervised manner. Subspace clustering has become an important problem as it has found various applications in computer vision, e.g., image segmentation , motion segmentation , and image clustering . For example, under Lambertian reflectance, the face images of one subject obtained with a fixed pose and varying lighting conditions lie in a low-dimensional subspace of dimension close to nine . Therefore, one can employ subspace clustering to group images of multiple subjects according to their respective subjects.

Most recent works on subspace clustering focus on clustering linear subspaces. However, in practice, the data do not necessarily conform to linear subspace models. For instance, in the example of face image clustering, reflectance is typically non-Lambertian and the pose of the subject often varies. Under these conditions, the face images of one subject rather lie in a non-linear subspace (or sub-manifold). A few works have proposed to exploit the kernel trick to address the case of non-linear subspaces. However, the selection of different kernel types is largely empirical, and there is no clear reason to believe that the implicit feature space corresponding to a predefined kernel is truly well-suited to subspace clustering.

In this paper, by contrast, we introduce a novel deep neural network architecture to learn (in an unsupervised manner) an explicit non-linear mapping of the data that is well-adapted to subspace clustering. To this end, we build our deep subspace clustering networks (DSC-Nets) upon deep auto-encoders, which non-linearly map the data points to a latent space through a series of encoder layers. Our key contribution then consists of introducing a novel self-expressive layer – a fully connected layer without bias and non-linear activations – at the junction between the encoder and the decoder. This layer encodes the “self-expressiveness” property of data drawn from a union of subspaces, that is, the fact that each data sample can be represented as a linear combination of other samples in the same subspace. To the best of our knowledge, our approach constitutes the first attempt to directly learn the affinities (through combination coefficients) between all data points within one neural network. Furthermore, we propose effective pre-training and fine-tuning strategies to learn the parameters of our DSC-Nets in an unsupervised manner and with a limited amount of data.

We extensively evaluate our method on face clustering, using the Extended Yale B and ORL datasets, and on general object clustering, using COIL20 and COIL100 . Our experiments show that our DSC-Nets significantly outperform the state-of-the-art subspace clustering methods.

Related Work

Over the years, many methods have been developed for linear subspace clustering. In general, these methods consist of two steps: the first and also most crucial one aims to estimate an affinity for every pair of data points to form an affinity matrix; the second step then applies normalized cuts or spectral clustering using this affinity matrix. The resulting methods can then be roughly divided into three categories : factorization methods , higher-order model based methods , and self-expressiveness based methods . In essence, factorization methods build the affinity matrix by factorizing the data matrix, and methods based on higher-order models estimate the affinities by exploiting the residuals of local subspace model fitting. Recently, self-expressiveness based methods, which seek to express the data points as a linear combination of other points in the same subspace, have become the most popular ones. These methods build the affinity matrix using the matrix of combination coefficients. Compared to factorization techniques, self-expressiveness based methods are often more robust to noise and outliers when relying on regularization terms to account for data corruptions. They also have the advantage over higher-order model based methods of considering connections between all data points rather than exploiting local models, which are often suboptimal. To handle situations where data points do not exactly reside in a union of linear subspaces, but rather in non-linear ones, a few works have proposed to replace the inner product of the data matrix with a pre-defined kernel matrix (e.g., polynomial kernel and Gaussian RBF kernel). There is, however, no clear reason why such kernels should correspond to feature spaces that are well-suited to subspace clustering. By contrast, here, we propose to explicitly learn one that is.

Auto-Encoders.

Auto-encoders (AEs) can non-linearly transform data into a latent space. When this latent space has lower dimension than the original one , this can be viewed as a form of non-linear PCA. An auto-encoder typically consists of an encoder and a decoder to define the data reconstruction cost. With the success of deep learning , deep (or stacked) AEs have become popular for unsupervised learning. For instance, deep AEs have proven useful for dimensionality reduction and image denoising . Recently, deep AEs have also been used to initialize deep embedding networks for unsupervised clustering . A convolutional version of deep AEs was also applied to extract hierarchical features and to initialize convolutional neural networks (CNNs) .

There has been little work in the literature combining deep learning with subspace clustering. To the best of our knowledge, the only exception is , which first extracts SIFT or HOG features from the images and feeds them to a fully connected deep auto-encoder with a sparse subspace clustering (SSC) prior. The final clustering is then obtained by applying k-means or SSC on the learned auto-encoder features. In essence, can be thought of as a subspace clustering method based on k-means or SSC with deep auto-encoder features. Our method significantly differs from in that our network is designed to directly learn the affinities, thanks to our new self-expressive layer.

Deep Subspace Clustering Networks (DSC-Nets)

Our deep subspace clustering networks leverage deep auto-encoders and the self-expressiveness property. Before introducing our networks, we first discuss this property in more detail.

Given data points $\{{\bf x}_{i}\}_{i=1,\cdots,N}$ drawn from multiple linear subspaces $\{\mathcal{S}_{i}\}_{i=1,\cdots,K}$, one can express a point in a subspace as a linear combination of other points in the same subspace. In the literature , this property is called self-expressiveness. If we stack all the points ${\bf x}_{i}$ into columns of a data matrix ${\bf X}$, the self-expressiveness property can be simply represented as one single equation, i.e., ${\bf X}={\bf X}{\bf C}$, where ${\bf C}$ is the self-representation coefficient matrix. It has been shown in that, under the assumption that the subspaces are independent, by minimizing certain norms of ${\bf C}$, ${\bf C}$ is guaranteed to have a block-diagonal structure (up to certain permutations), i.e., $c_{ij}\neq 0$ iff point ${\bf x}_{i}$ and point ${\bf x}_{j}$ lie in the same subspace. So we can leverage the matrix ${\bf C}$ to construct the affinity matrix for spectral clustering. Mathematically, this idea is formalized as the optimization problem

Unfortunately, the self-expressiveness property only holds for linear subspaces. While kernel based methods aim to tackle the non-linear case, it is not clear that pre-defined kernels yield implicit feature spaces that are well-suited for subspace clustering. In this work, we aim to learn an explicit mapping that makes the subspaces more separable. To this end, and as discussed below, we propose to build our networks upon deep auto-encoders.

2 Self-Expressive Layer in Deep Auto-Encoders

Our goal is to train a deep auto-encoder, such as the one depicted by Figure 1, such that its latent representation is well-suited to subspace clustering. To this end, we introduce a new layer that encodes the notion of self-expressiveness.

Specifically, let $\Theta$ denote the auto-encoder parameters, which can be decomposed into encoder parameters $\Theta_{e}$ and decoder parameters $\Theta_{d}$. Furthermore, let ${\bf Z}_{\Theta_{e}}$ denote the output of the encoder, i.e., the latent representation of the data matrix ${\bf X}$. To encode self-expressiveness, we introduce a new loss function defined as

where $\hat{\bf X}_{\Theta}$ represents the data reconstructed by the auto-encoder. To minimize (3), we propose to leverage the fact that, as discussed below, ${\bf C}$ can be thought of as the parameters of an additional network layer, which lets us solve for $\Theta$ and ${\bf C}$ jointly using backpropagation.Note that one could also alternate minimization between $\Theta$ and ${\bf C}$. However, since the loss is non-convex, this would not provide better convergence guarantees and would require investigating the influence of the number of steps in the optimization w.r.t. $\Theta$ on the clustering results.

For notational consistency, let us denote the parameters of the self-expressive layer (which are just the elements of ${\bf C}$) as $\Theta_{s}$. As can be seen from Figure 2, we then take the input to the decoder part of our network to be the transformed latent representation ${\bf Z}_{\Theta_{e}}\Theta_{s}$. This lets us re-write our loss function as

3 Network Architecture

Our network consists of three parts, i.e., stacked encoders, a self-expressive layer, and stacked decoders. The overall network architecture is shown in Figure 2. In this paper, since we focus on image clustering problems, we advocate the use of convolutional auto-encoders that have fewer parameters than the fully connected ones and are thus easier to train. Note, however, that fully-connected auto-encoders are also compatible with our self-expressive layer. In the convolutional layers, we use kernels with stride 2 in both horizontal and vertical directions, and rectified linear unit (ReLU) for the non-linear activations. Given $N$ images to be clustered, we use all the images in a single batch. Each input image is mapped by the convolutional encoder layers to a latent vector (or node) ${\bf z}_{i}$, represented as a shaded circle in Figure 2. In the self-expressive layer, the nodes are fully connected using linear weights without bias and non-linear activations. The latent vectors are then mapped back to the original image space via the deconvolutional decoder layers.

For the $i^{\rm th}$ encoder layer with $n_{i}$ channels of kernel size $k_{i}\times k_{i}$, the number of weight parameters is $k_{i}^{2}n_{i-1}n_{i}$, with $n_{0}=1$. Since the encoders and decoders have symmetric structures, their total number of parameters is $\sum_{i}2k_{i}^{2}n_{i-1}n_{i}$ plus the number of bias parameters $\sum_{i}2n_{i}-n_{1}+1$. For $N$ input images, the number of parameters for the self-expressive layer is $N^{2}$. For example, if we have three encoder layers with 10, 20, and 30 channels, respectively, and all convolutional kernels are of size $3\times 3$, then the number of parameters for encoders and decoders is $\sum_{i=1}^{3}2(k_{i}^{2}n_{i-1}+1)n_{i}-n_{1}+1=14671$. If we have $1000$ input images, then the number of parameters in the self-expressive layer is $10^{6}$. Therefore, the network parameters are typically dominated by those of the self-expressive layer.

4 Training Strategy

Since the size of datasets for unsupervised subspace clustering is usually limited (e.g., in the order of thousands of images), our networks remain of a tractable size. However, for the same reason, it also remains difficult to directly train a network with millions of parameters from scratch. To address this, we design the pre-training and fine-tuning strategies described below. Note that this also allows us to avoid the trivial all-zero solution while minimizing the loss (4).

Once the network is trained, we can use the parameters of the self-expressive layer to construct an affinity matrix for spectral clustering , as illustrated in Figure 3. Although such an affinity matrix could in principle be computed as $|{\bf C}|+|{\bf C}^{T}|$, over the years, researchers in the field have developed many heuristics to improve the resulting matrix. Since there is no globally-accepted solution for this step in the literature, we make use of the heuristics employed by SSC and EDSC . Due to the lack of space, we refer the reader to the publicly available implementation of SSC and Section 5 of for more detail, and, to the TensorFlow implementation of our algorithm https://github.com/panji1990/Deep-subspace-clustering-networks.

Experiments

We implemented our method in Python with Tensorflow-1.0 , and evaluated it on four standard datasets, i.e., the Extended Yale B and ORL face image datasets, and the COIL20/100 object image datasets. We compare our methods against the following baselines: Low Rank Representation (LRR) , Low Rank Subspace Clustering (LRSC) , Sparse Subspace Clustering (SSC) , Kernel Sparse Subspace Clustering (KSSC) , SSC by Orthogonal Matching Pursuit (SSC-OMP) , Efficient Dense Subspace Clustering (EDSC) , SSC with the pre-trained convolutional auto-encoder features (AE+SSC), and EDSC with the pre-trained convolutional auto-encoder features (AE+EDSC). For all the baselines, we used the source codes released by the authors and tuned the parameters by grid search to the achieve best results on each dataset. Since the code for the deep subspace clustering method of is not publicly available, we are only able to provide a comparison against this approach on Extended Yale B and COIL20, for which the results are provided in . Note that this comparison already clearly shows the benefits of our approach.

For all quantitative evaluations, we make use of the clustering error rate, defined as

The Extended Yale B dataset is a popular benchmark for subspace clustering. It consists of 38 subjects, each of which is represented with 64 face images acquired under different illumination conditions (see Figure 4(a) for sample images from this dataset). Following the experimental setup of , we down-sampled the original face images from $192\times 168$ to $42\times 42$ pixels, which makes it computationally feasible for the baselines . In each experiment, we pick $K\in\{10,15,20,25,30,35,38\}$ subjects (each subject with 64 face images) to test the robustness w.r.t. an increasing number of clusters. Taking all possible combinations of $K$ subjects out of 38 would result in too many experimental trials. To get a manageable size of experiments, we first number the subjects from 1 to 38 and then take all possible $K$ consecutive subjects. For example, in the case of $10$ subjects, we take all the images from subject $1-10$, $2-11$, $\cdots$, $29-38$, giving rise to $29$ experimental trials.

We experimented with different architectures for the convolutional layers of our network, e.g., different network depths and number of channels. While increasing these values, increases the representation power of the network, it also increases the number of network parameters, thus requiring larger training datasets. Since the size of Extended Yale B is quite limited with only $2432$ images, we found having three-layer encoders and decoders with $$channels to be a good trade-off for this dataset. The detailed network settings are described in Table 1. In the fine-tuning phase, since the number of epochs required for gradient descent increases as the number of subjects$K$increases, we defined the number of epochs for DSC-Net-L1 as$160+20K$and for DSC-Net-L2 as$50+25K$. We set the regularization parameters to$\lambda_{1}=1.0,\lambda_{2}=1.0\times 10^{\frac{K}{10}-3}$.

2 ORL Dataset

The ORL dataset is composed of 400 human face images, with 40 subjects each having 10 samples. Following , we down-sampled the original face images from $112\times 92$ to $32\times 32$. For each subject, the images were taken under varying lighting conditions with different facial expressions (open / closed eyes, smiling / not smiling) and facial details (glasses / no glasses)(see Figure 4(b) for sample images). Compared to Extended Yale B, this dataset is more challenging for subspace clustering because (i) the face subspaces have more non-linearity due to varying facial expressions and details; (ii) the dataset size is much smaller (400 vs. 2432). To design a trainable deep auto-encoder on 400 images, we reduced the number of network parameters by decreasing the number of channels in each encoder and decoder layer. The resulting network is specified in Table 3.

Since we already verified the robustness of our method to the number of clusters in the previous experiment, here, we only provide results for clustering all 40 subjects. In this setting, we set $\lambda_{1}=1$ and $\lambda_{2}=0.2$ and run $700$ epochs for DSC-Net-L2 and $1500$ epochs for DSC-Net-L1 during fine-tuning. Note that, since the size of this dataset is small, we can even use the whole data as a single batch in pre-training. We found this to be numerically more stable and converge faster than stochastic gradient descent using randomly sampled mini-batches.

Figure 5(a) shows the error rates of the different methods, where different colors denote different subspace clustering algorithms and the length of the bars reflects the error rate. Since there are much fewer samples per subject, all competing methods perform worse than on Extended Yale B. Note that both EDSC and SSC achieve moderate clustering improvement by using the features of pre-trained convolutional auto-encoders, but their error rates are still around twice as high as those of our methods.

3 COIL20 and COIL100 Datasets

The previous experiments both target face clustering. To show the generality of our algorithm, we also evaluate it on the COIL object image datasets – COIL20 and COIL100 . COIL20 consists of 1440 gray-scale image samples, distributed over 20 objects such as duck and car model (see sample images in Figure 4(c)). Similarly, COIL100 consists of 7200 images distributed over 100 objects. Each object was placed on a turntable against a black background, and 72 images were taken at pose intervals of 5 degrees. Following , we down-sampled the images to $32\times 32$. In contrast with the previous human face datasets, in which faces are well aligned and have similar structures, the object images from COIL20 and COIL100 are more diverse, and even samples from the same object differ from each other due to the change of viewing angle. This makes these datasets challenging for subspace clustering techniques. ‘’ For these datasets, we used shallower networks with one encoder layer, one self-expressive layer, and one decoder layer. For COIL20, we set the number of channels to 15 and the kernel size to $3\times 3$. For COIL100, we increased the number of channels to 50 and the kernel size to $5\times 5$. The settings for both networks are provided in Table 4. Note that with these network architectures, the dimension of the latent space representation ${\bf z}_{i}$ increases by a factor of 15/4 for COIL20 (as the spatial resolution of each channel shrinks to 1/4 of the input image after convolutions with stride 2, and we have 15 channels) and 50/4 for COIL100. Thus our networks perform dimensionality lifting rather than dimensionality reduction. This, in some sense, is similar to the idea of Hilbert space mapping in kernel methods , but with the difference that, in our case, the mapping is explicit, via the neural network. In our experiments, we found that these shallow, dimension-lifting networks performed better than deep, bottle-neck ones on these datasets. While it is also possible to design deep, dimension-lifting networks, the number of channels has to increase by a factor of 4 after each layer to compensate for the resolution loss. For example, if we want the latent space dimension to increase by a factor of 15/4, we need $15\cdot 4$ channels in the second layer for a 2-layer encoder, $15\cdot 4^{2}$ channels in the third layer for a 3-layer encoder, and so forth. In the presence of limited data, this increasing number of parameters makes training less reliable. In our fine-tuning stage, we ran 30 epochs (COIL20) / 100 epochs (COIL100) for DSC-Net-L1 and 40 epochs (COIL20) / 120 epochs (COIL100) for DSC-Net-L2, and set the regularization parameters to $\lambda_{1}=1,\lambda_{2}=30$.

Figure 5(b) and (c) depict the error rates of the different methods on clustering 20 classes for COIL20 and 100 classes for COIL100, respectively. Note that, in both cases, our DSC-Net-L2 achieves the lowest error rate. In particular, for COIL20, we obtain an error of 5.34%, which is roughly 1/3 of the error rate of the best-performing baseline AE+EDSC. The results of on COIL20 was reported to be $14.24\pm 4.70\%$ in terms of clustering error, which is also much higher than ours.

Conclusion

We have introduced a deep auto-encoder framework for subspace clustering by developing a novel self-expressive layer to harness the "self-expressiveness" property of a union of subspaces. Our deep subspace clustering network allows us to directly learn the affinities between all data points through one neural network. Furthermore, we have proposed pre-training and fine-tuning strategies to train our network, demonstrating the ability to handle challenging scenarios with small-size datasets, such as the ORL dataset. Our experiments have demonstrated that our deep subspace clustering methods provide significant improvement over the state-of-the-art subspace clustering solutions in terms of clustering accuracy on several standard datasets.

References