Learning optimally separated class-specific subspace representations using convolutional autoencoder

Self expressiveness property states that a data point in a subspace can be expressed as a linear combination of other data points from the same subspace. Let $\mathcal{Y}^{i}=\{\bm{y}_{j}\}_{j=1}^{n}$ denote a set of $n$ data points drawn from a subspace $\mathcal{S}_{i}\subset\mathbb{R}^{D}$. Rewriting the set $\mathcal{Y}^{i}$ as matrix $Y^{i}\in\mathbb{R}^{D\times n}$, where each column represents a data point, self expressiveness can be represented as

where, $W^{i}\in\mathbb{R}^{n\times n}$ denotes the self representation coefficient matrix and the constraint on $W^{i}$ avoids the trivial solution. It may be noted that self expressiveness property for subspaces holds only for $n>d_{s}$, where $d_{s}$ denotes the dimension of the subspace. Coefficient matrix $W^{i}$ can be obtained by solving:

where, $\parallel.\parallel_{1}$ denotes the $\ell_{1}$ norm of vectorized $W^{i}$ which promotes sparsity.

Since we are assuming subspace structure for each class, a data point can be thought of as coming from union of subspaces. Let $S_{1},\dots,S_{c}$ be the $c$ subspaces associated with $c$ classes. Self-expressiveness property is valid in each of the subspaces, i.e., a data point $\textbf{y}_{i}\in S_{i}$ is represented by points in $S_{i}$ and not by points in $S_{j},j\neq i$ assuming non-overlapping subspaces. Mathematically, this can be written as,

where $Y=[Y^{1},\dots,{Y}^{c}]$ denotes the $c$-class data drawn from a union of $c$ linear subspaces, $\bigcup_{i=1}^{c}{\mathcal{S}_{i}}$, of $\mathbb{R}^{D}$, respectively. $W$ is a block diagonal matrix where each block denotes the representation coefficients corresponding to a particular class. The optimization problem in (3) ensures that a data point of a class should be represented only by other data points of the same class. Representation coefficient can be obtained by solving,

Typically autoencoders generate a shorter length representation of input data such that the reconstruction error is minimized. Our requirement is a data representation which gives minimum reconstruction error while maintaining the subspace structure present in the data with increased separation between subspaces. The former issue is addressed in this subsection and the latter in the following one. Self expressiveness is built into the autoencoder by adding a block between encoder and decoder as shown in Fig. 1. The convolutional autoencoder is parametrized by $\Gamma=(\Gamma_{e},~{}\Gamma_{s},~{}\Gamma_{d})$, where $\Gamma_{e}$, $\Gamma_{s}$ and $\Gamma_{d}$ denote the weights of encoder, CSSE layer and decoder networks, respectively. $X_{\Gamma_{e}}$ denotes the encoder output matrix corresponding to data matrix $Y=[Y^{1},\dots,Y^{c}]\in\mathbb{R}^{D\times N}$. $X_{\Gamma_{e}}=[X_{\Gamma_{e}}^{1},\dots,X_{\Gamma_{e}}^{c}]$ with $X_{\Gamma_{e}}^{i}\in\mathbb{R}^{\hat{D}\times n_{i}}$ denoting the feature space representation for $i^{th}$ class. The choice of $\hat{D}$ is explained in subsection II-D. Incorporating the notion of class specific self expressiveness, the new cost function for autoencoder becomes:

where, $\hat{Y}_{\Gamma}$ is the output of the decoder. The first term of the proposed cost function reduces MSRE (mean square representation error); second and third terms together preserves the subspace structure in the feature space. With this cost, the network behavior is equivalent to that of a kernel, the difference being the non-linear mapping is a learned one rather than an analytic one. Though this cost function preserves the subspace structure, it does not increase the distance between the subspaces. We modify the cost function to equation (6) to push the subspaces apart.

The distance between two subspaces is measured in terms of principal angles [11] defined as follows.

$\cos\theta_{1}$ is the cosine of lowest principal angle which denotes the maximum correlation between two subspaces. Two subspaces are maximally separated if all the principal angles are 90 degrees, i.e., ${X_{\Gamma_{e}}^{i}}^{\top}{X_{\Gamma_{e}}^{j}}=\bm{0}$, where $\bm{0}\in\mathbb{R}^{n_{i}\times n_{j}}$. It can be achieved when $||{X_{\Gamma_{e}}^{i}}^{\top}X_{\Gamma_{e}}^{j}||_{F}^{2}$ is minimized pairwise. With the addition of this term, new cost function becomes

The proposed network architecture is shown in Fig. 1. The network consists of three parts- encoder, CSSE layer and decoder. We use convolutional layers in both encoder and decoder networks as it requires less number of parameters than fully connected layers and hence easy to train. Kernels in convolutional layers of both encoder and decoder use a stride of 2 in the both directions. Note that in the CSSE layer, connections are preserved between the data points of same class only. There is no cross connection between the encoder outputs of different classes and hence preserves the within class subspace structure. The network acts as a transformation learner, i.e., it maps the different class data to the optimally separated subspaces using the proposed cost function given in equation (6). Training data is passed to the network in a single batch along with the class labels. The explicit representations obtained from the encoder are mapped to original input (pixel) space using the decoder network. Feature space dimension, $\hat{D}$, depends upon the encoder design, i.e., number of conv layers, number of filters in each layer and stride of the filter. A desired feature space dimension can be obtained by adjusting the above mentioned parameters.

Let $t_{j}$ denote the number of filters in $j^{th}$ layer. $k_{j}\times k_{j}\times t_{j-1}$ is the size of filter in $j^{th}$ layer. $t_{0}$ is set to 1 as input to the network is gray scale images. The total number of weight parameters for the $j^{th}$ layer of encoder network are $k_{j}^{2}t_{j}t_{j-1}$. Total weights for encoder network with $m$ such layers are $\sum_{j=1}^{m}k_{j}^{2}t_{j}t_{j-1}$. Bias parameters are excluded for the calculation. Decoder being similar in structure to encoder, cumulative sum of encoder and decoder weight parameters is $2\sum_{j=1}^{m}k_{j}^{2}t_{j}t_{j-1}$. Weights in the CSSE layers depends on the number of examples per class and total number of classes i.e. $c(\sum_{i=1}^{c}n_{i}^{2}-n_{i})$. Considering an arbitrary example of 10 class data with 100 training images per class, a 3 layer network is chosen with 10, 20 and 30 filters per layer respectively with a kernel size of $5\times 5$. The total number of encoder and decoder parameters are $20250\times 2$ and CSSE layer parameters are approximately $10^{5}$. It is evident that network is mostly dominated by the parameters of CSSE layer. With the increase in training data, number of parameters for CSSE also increases but remain fixed for encoder and decoder networks. Though the number of parameters increase, most of the weights within a block of CSSE layer go to zero due to self expressiveness within a subspace and hence does not complicate the training procedure.

The network is trained from scratch using Xavier initialization. This is a supervised learning framework as the complete training data is passed in a single batch along with the class labels. The class labels ensures the block diagonal connections in CSSE layer. For loss minimization adaptive momentum (ADAM) based gradient descent method is used. The method is a deterministic one rather than stochastic as whole data is passed in a single batch. Number of iterations depends upon the type of training data used.

For Extended Yale b dataset, we empirically select a 3-layer encoder-decoder network. First layer has 30 channels with kernel size of $5\times 5$. Second and third layers have 25 and 20 number of channels, respectively with kernel size of $3\times 3$. Since face images exhibit a well defined subspace structure in input space, no ReLU is added. The non-linearity in network is due to biases in filters only. This network architecture leads to the generation of a 720 dimensional feature vector representation corresponding to each input image. $\lambda_{1},~{}\lambda_{2}~{}\text{and}~{}\lambda_{3}$ are empirically chosen as 3, 1 and 100, respectively. Choice of $\lambda^{\prime}s$ is empirical. Data is passed in a single batch of size 1216 along with class labels. The learning rate is set to $10^{-3}$.

For MNIST dataset, a 3-layer encoder-decoder network is used with 30, 20 and 10 number of channels in each layer, respectively. Kernel size is kept same as in previous case. Except for the addition of ReLU to the second layer of both encoder and decoder, the architecture is same as in previous case. This ReLU handles the non-linearities of input space. This network architecture leads to the generation of a 160 dimensional feature vector representation corresponding to each input image. $\lambda_{1},~{}\lambda_{2}$ and $\lambda_{3}$ are empirically chosen as 0.5, 0.1 and 50, respectively.

For Coil20 dataset, a similar architecture as that of MNIST is used which generates a 160 length representation in feature space. $\lambda_{1},~{}\lambda_{2}$ and $\lambda_{3}$ are empirically chosen as 1, 1 and 70, respectively.

The proposed approach is compared with a $k$-NN classifier applied on pixel features and two linear transformation learning approaches: orthogonalizing transformation (OT)  [7] and low rank transformation (LRT)  [7]. $k$-NN and sparse representation (SR) [14] based classifier are used over the obtained feature space representations. Classification accuracy for an average of 4 random trials is reported in Table I for all the datasets. A comparable classification performance can be seen for Extended Yale face dataset. The reason is that the face images are captured in varying illumination keeping pose and expression fixed. This results in a better subspace structure in input space leading to almost no non-linearities and hence other transformations also work well. A better classification performance for Mnist digit dataset is also observed by considering only a small set of training samples. Experimentation performed on Coil20 dataset in setting 1 shows a comparable performance for all. The reason being that the 36 data points for each class are sampled randomly for both training and testing, respectively. This leads to the presence of data points in nearby viewing angles in both the training and testing and hence gives a good performance. However this is not the case under setting 2 where the 36 consecutive viewing angles are kept for training and remaining for testing. For this, a significant improvement in performance is seen.

CSSE layer is used to preserve the subspace structure from the input space to the feature space. Fig. 2 shows the weight parameters for CSSE layer for Coil20 dataset obtained after training. The weight matrices are shown for (a) randomly sampled training data (setting1) and (b) consecutive sampled training data (setting 2). A sparsity pattern within a class specific block can be observed in both the settings but nature is different. In Fig. 2(a) a random sparsity pattern is observed while in Fig. 2(b) non-zero weights are observed along the diagonal entries. The reason is quite intuitive as the training data is structured in the $2^{nd}$ case, all the training data points are arranged in slightly varying poses. Hence a data point can be best represented only by its nearby poses that leads to non-zero entries only along the diagonal values.

The cosine of lowest principle angle between two subspaces can be computed as, $\cos\theta=\max_{u\in\mathcal{S}_{i}}\max_{v\in\mathcal{S}_{j}}\langle u,v\rangle,$ where $\mathcal{S}_{i}$ denotes the subspace for $i^{th}$ class data. Table II shows the angle (in degree) between the class specific subspaces for few selected objects from Coil20 dataset. We model each class data as a seven dimensional subspace (decided by using singular values). The subspace bases are generated using singular value decomposition of class specific data matrix. We can observe that there is a significant increase in the lowest principal angle which leads to better separability of data in the feature space.