5.1.2.1 Sparse Coding with Graph Regularization

Sparse codes have proved to be an effective feature for clustering. In [12], the authors suggested that the contribution of one sample to the reconstruction of another sample was a good indicator of similarity between these two samples. Therefore, the reconstruction coefficients (sparse codes) can be used to constitute the similarity graph for spectral clustering. The ${\ell }_1$-graph performs sparse representation for each data point separately without considering the geometric information and manifold structure of the entire data. Further research shows that the graph regularized sparse representations produce superior results in various clustering and classification tasks [8,19]. In this section, we adopt the graph regularized sparse codes as the features for clustering.

We assume that all the data samples $\mathit{X}=[{\mathit{x}}_1,{\mathit{x}}_2,\dots ,{\mathit{x}}_n],{\mathit{x}}_i\in R^{m\times 1},i=1,2,\dots ,n$, are encoded into their corresponding sparse codes $\mathit{A}=[{\mathit{a}}_1,{\mathit{a}}_2,\dots ,{\mathit{a}}_n]$, ${\mathit{a}}_i\in R^{p\times 1},i=1,2,\dots ,n$, using a learned dictionary $\mathit{D}=[{\mathit{d}}_1,{\mathit{d}}_2,\dots ,{\mathit{d}}_p]$, where ${\mathit{d}}_i\in R^{m\times 1},i=1,2,\dots ,p$ are the learned atoms. Moreover, given a pairwise similarity matrix W, the sparse representations that capture the geometric structure of the data according to the manifold assumption should minimize the following objective: $\frac{1}{2}{\sum }_{i=1}^n{\sum }_{j=1}^n{\mathit{W}}_{ij}||{\mathit{a}}_i-{\mathit{a}}_j|{|}_2^2=\mathrm{Tr}(\mathit{A}\mathit{L}{\mathit{A}}^{\mathit{T}})$, where L is the graph Laplacian matrix constructed from W. In this section, W is chosen as the Gaussian kernel, ${\mathit{W}}_{ij}=\exp (-\frac{||{\mathit{x}}_i-{\mathit{x}}_j|{|}_2^2}{{\delta }^2})$, where δ is the controlling parameter selected by cross-validation.

The graph regularized sparse codes are obtained by solving the following convex optimization:

$\begin{array}{c}\mathit{A}=\arg {\min }_{\mathit{A}}\frac{1}{2}||\mathit{X}\mathbf{-}\mathit{D}\mathit{A}|{|}_F^2+\lambda {\sum }_i||{\mathit{a}}_i|{|}_1+\alpha Tr(\mathit{A}\mathit{L}{\mathit{A}}^{\mathit{T}})+{\lambda }_2||\mathit{A}|{|}_F^2.\hfill \end{array}$

Note that ${\lambda }_2>0$ is necessary for proving the differentiability of the objective function (see [5.2] in the Appendix). However, setting ${\lambda }_2=0$ proves to work well in practice, and thus the term ${\lambda }_2||\mathit{A}|{|}_F^2$ will be omitted by default hereinafter (except for the differentiability proof).

Obviously, the effect of sparse codes A largely depends on the quality of dictionary D. Dictionary learning methods, such as K-SVD algorithm [20], are widely used in sparse coding literature. In regard to clustering, the authors of [12,19] constructed the dictionary by directly selecting atoms from data samples. Zheng et al. [8] learned the dictionary that can reconstruct input data well. However, it does not necessarily lead to discriminative features for clustering. In contrast, we will optimize D together with the clustering task.

5.1.2.2 Bi-level Optimization Formulation

The objective cost function for the joint framework can be expressed by the following bi-level optimization:

$\begin{array}{c}\underset{\mathit{D},\mathit{w}}{\min }C(\mathit{A},\mathit{w})\hfill \\ s.t.\mathit{A}=\arg {\min }_{\mathit{A}}\frac{1}{2}||\mathit{X}\mathbf{-}\mathit{D}\mathit{A}|{|}_F^2+\lambda {\sum }_i||{\mathit{a}}_i|{|}_1+\alpha \mathrm{Tr}(\mathit{A}\mathit{L}{\mathit{A}}^{\mathit{T}}),\hfill \end{array}$

where $C(\mathit{A},\mathit{w})$ is a cost function evaluating the loss of clustering. It can be formulated differently based on various clustering principles, two of which will be discussed and solved in Sect. 5.1.3.

Bi-level optimization [21] has been investigated in both theory and application. In [21], the authors proposed a general bi-level sparse coding model for learning dictionaries across coupled signal spaces. Another similar formulation has been studied in [17] for general regression tasks.

5.1.3.1 Entropy-Minimization Loss

Maximization of the mutual information with respect to parameters of the encoder model effectively defines a discriminative unsupervised optimization framework. The model is parameterized similarly to a conditionally trained classifier, but the cluster allocations are unknown [7]. In [22,6], the authors adopted an information-theoretic framework as an implementation of the low-density separation assumption by minimizing the conditional entropy. By substituting the logistic posterior probability into the minimum conditional entropy principle, the authors got the logistics clustering algorithm, which is equivalent to finding a labeling strategy so that the total entropy of data clustering is minimized.

Since the true cluster label of each ${\mathit{x}}_{\mathit{i}}$ is unknown, we introduce the predicted confidence probability $p_{ij}$ that sample ${\mathit{x}}_{\mathit{i}}$ belongs to cluster j, $i=1,2,\dots ,N$, $j=1,2,\dots ,K$, which is set as the likelihood of the multinomial logistic (softmax) regression

$\begin{array}{c}{p}_{ij}=p(j|{\mathit{w}\mathbf{,}\mathit{a}}_i)=\frac{1}{1+e^{-j{\mathit{w}}^T{\mathit{a}}_i}}.\hfill \end{array}$

The loss function for all data could be defined accordingly in a entropy-like form

$\begin{array}{c}C(\mathit{A},\mathit{w})=-{\sum }_{i=1}^n{\sum }_{j=1}^K{p}_{ij}\log p_{ij}.\hfill \end{array}$

The predicted cluster label of ${\mathit{a}}_i$ is the cluster j where it achieves the largest likelihood probability $p_{ij}$. The logistics regression can deal with multiclass problems more easily compared with the support vector machine (SVM). The next important thing we need to study is the differentiability of (5.2).

Proof

Denote $\mathit{X}\in \mathcal{X}$, and $\mathit{D}\in \mathcal{D}$. Also let the objective function $C(\mathit{A},\mathit{w})$ in (5.4) be denoted as C for short. The differentiability of C with respect to w is easy to show, using only the compactness of $\mathcal{X}$, as well as the fact that C is twice differentiable.

We will therefore focus on showing that C is differentiable with respect to D, which is more difficult since A, and thus ${\mathit{a}}_i$, is not differentiable everywhere. Without loss of generality, we use a vector a instead of A for simplifying the derivations hereinafter. In some cases, we may equivalently express a as $\mathit{a}\mathbf{(}\mathit{D}\mathbf{,}\mathit{w}\mathbf{)}$ in order to emphasize the functional dependence. Based on [5.2] in Appendix, and given a small perturbation $\mathit{E}\in R^{m\times p}$, it follows that

$\begin{array}{c}C(\mathit{a}\mathbf{(}\mathit{D}\mathbf{+}\mathit{E}\mathbf{)},\mathit{w})-C(\mathit{a}\mathbf{(}\mathit{D}\mathbf{)},\mathit{w})={\mathrm{\nabla }}_{\mathit{z}}{C}_{\mathit{w}}^T(\mathit{a}\mathbf{(}\mathit{D}\mathbf{+}\mathit{E}\mathbf{)}-\mathit{a}\mathbf{(}\mathit{D}\mathbf{)})+O(||\mathit{E}|{|}_F^2),\hfill \end{array}$

(5.5)

where the term $O(||\mathit{E}|{|}_F^2)$ is based on the fact that $\mathit{a}\mathbf{(}\mathit{D}\mathbf{,}\mathit{x}\mathbf{)}$ is uniformly Lipschitz and $\mathcal{X}\times \mathcal{D}$ is compact. It is then possible to show that

$\begin{array}{c}C(\mathit{a}\mathbf{(}\mathit{D}\mathbf{+}\mathit{E}\mathbf{)},\mathit{w})-C(\mathit{a}\mathbf{(}\mathit{D}\mathbf{)},\mathit{w})=\mathrm{Tr}({\mathit{E}}^{T}g(\mathit{a}\mathbf{(}\mathit{D}\mathbf{+}\mathit{E}\mathbf{)},\mathit{w}))+O(||\mathit{E}|{|}_F^2),\hfill \end{array}$

(5.6)

where g has the form given in Algorithm 5.1. This shows that C is differentiable on $\mathcal{D}$. □

Built on the differentiability proof, we are able to solve (5.1) using a projected first order stochastic gradient descent (SGD) algorithm, whose detailed steps are outlined in Algorithm 5.1. At a high level overview, it consists of an outer stochastic gradient descent loop that incrementally samples the training data. It uses each sample to approximate gradients with respect to the classifier parameter w and the dictionary D, which are then used to update them.

5.1.3.2 Maximum-Margin Loss

Xu et al. [3] proposed maximum margin clustering (MMC), which borrows the idea from the SVM theory. Their experimental results showed that the MMC technique could often obtain more accurate results than conventional clustering methods. Technically, MMC just finds a way to label the samples by running an SVM implicitly, and the SVM margin obtained is maximized over all possible labelings [5]. However, unlike supervised large margin methods, which are usually formulated as convex optimization problems, maximum margin clustering is a nonconvex integer optimization problem, which is much more difficult to solve. Li et al. [23] made several relaxations to the original MMC problem and reformulated it as a semidefinite programming (SDP) problem. The cutting plane maximum margin clustering (CPMMC) algorithm was presented in [5] to solve MMC with a much improved efficiency.

To develop the multiclass max-margin loss of clustering, we refer to the classical multiclass SVM formulation in [24]. Given the sparse code ${\mathit{a}}_i$ comprises the features to be clustered, we define the multiclass model as

$\begin{array}{c}f({\mathit{a}}_i)=\underset{j=1,\dots ,K}{\arg \max }{f}^j({\mathit{a}}_i)=\underset{j=1,\dots ,K}{\arg \max }({\mathit{w}}_j^T{\mathit{a}}_i),\hfill \end{array}$

where $f^j$ is the prototype for the jth cluster and ${\mathit{w}}_{\mathit{j}}$ is its corresponding weight vector. The predicted cluster label of ${\mathit{a}}_i$ is the cluster of the weight vector that achieves the maximum value ${\mathit{w}}_{\mathit{j}}^{\mathit{T}}{\mathit{a}}_{\mathit{i}}$. Let $\mathit{w}=[{\mathit{w}}_{\mathbf{1}},\dots ,{\mathit{w}}_{\mathit{K}}]$, the multiclass max-margin loss for ${\mathit{a}}_i$, be defined as

$\begin{array}{c}C({\mathit{a}}_i,\mathit{w})=\max (0,1+f^{r_i}({\mathit{a}}_i)-f^{y_i}({\mathit{a}}_i)),\hfill \\ \text{where}{y}_i=\underset{j=1,\dots ,K}{\arg \max }{f}^j({\mathit{a}}_i),r_i=\underset{j=1,\dots ,K,j\ne y_i}{\arg \max }{f}^j({\mathit{a}}_i).\hfill \end{array}$

Note that different from training a multiclass SVM classier, where $y_i$ is given as a training label, the clustering scenario requires us to jointly estimate $y_i$ as a variable. The overall max-margin loss to be minimized is (λ as the coefficient)

$\begin{array}{c}C(\mathit{A},\mathit{w})=\frac{\lambda }{2}||\mathit{w}|{|}^2+{\sum }_{i=1}^{n}C({\mathit{a}}_i,\mathit{w}).\hfill \end{array}$

But to solve (5.8) or (5.9) with respect to the same framework as logistic loss will involve two additional concerns, which need to be handled specifically.

First, the hinge loss of the form (5.8) is not differentiable, with only a subgradient existing. This makes the objective function $C(\mathit{A},\mathit{w})$ nondifferentiable on $\mathit{D}\mathbf{\times }\mathit{w}$, and further the analysis in the proof of Theorem 5.1 cannot be applied. We could have used the squared hinge loss or modified Huber loss for a quadratically smoothed loss function [25]. However, as we checked in the experiments, the quadratically smoothed loss is not as good as hinge loss in training time and sparsity. Also, though not theoretically guaranteed, using the subgradient of $C(\mathit{A},\mathit{w})$ works well in our case.

Second, given that w is fixed, it should be noted that $y_i$ and $r_i$ are both functions of ${\mathit{a}}_i$. Therefore, calculating the derivative of (5.8) with respect to ${\mathit{a}}_i$ would involve expanding both $r_i$ and $y_i$, making analysis quite complicated. Instead, we borrow ideas from the regularity of the elastic net solution [17], namely the set of nonzero coefficients of the elastic net solution should not change for small perturbations. Similarly, due to the continuity of the objective, it is assumed that a sufficiently small perturbation over the current ${\mathit{a}}_i$ will not change $y_i$ and $r_i$. Therefore in each iteration, we could directly precalculate $y_i$ and $r_i$ using the current w and ${\mathit{a}}_i$ and fix them for ${\mathit{a}}_i$ updates.²

Given the above two approaches, for a single sample ${\mathit{a}}_i$, if the hinge loss is larger than 0, the derivative of (5.8) with respect to w is

${\mathrm{\Delta }}_i^j=\{\begin{array}{cc}\lambda {\mathit{w}}_i^j-{\mathit{a}}_i\hfill & \mathrm{if}j=y_i,\hfill \\ \lambda {\mathit{w}}_i^j+{\mathit{a}}_i\hfill & \mathrm{if}j=r_i,\hfill \\ \lambda {\mathit{w}}_i^j\hfill & \text{otherwise,}\hfill \end{array}$

where ${\mathrm{\Delta }}_i^j$ denotes the jth element of the derivative for the sample ${\mathit{a}}_i$. If the hinge loss is less than 0, then ${\mathrm{\Delta }}_i^j=\lambda {\mathit{w}}_i^j$. The derivative of (5.8) with respect to ${\mathit{a}}_i$ is ${\mathit{w}}^{r_i}-{\mathit{w}}^{y_i}$ if the hinge loss is larger than 0, and 0 otherwise. Note the above deduction can be conducted in a batch mode. It is then similarly solved using a projected SGD algorithm, whose steps are outlined in Algorithm 5.2.

5.1.4.1 Datasets

We conduct our clustering experiments on four popular real datasets, which are summarized in Table 5.1. The ORL face database contains 400 facial images for 40 subjects, and each subject has 10 images of size $32\times 32$. The images are taken at different times with varying lighting and facial expressions. The subjects are all in an upright, frontal position with a dark homogeneous background. The MNIST handwritten digit database consists of a total number of 70,000 images, with digits ranging from 0 to 9. The digits are normalized and centered in fixed-size images of $28\times 28$. The COIL20 image library contains 1440 images of size $32\times 32$, for 20 objects. Each object has 72 images, that were taken 5 degree apart as the object was rotated on a turntable. The CMU-PIE face database contains 68 subjects with 41,368 face images as a whole. For each subject, we have 21 images of size $32\times 32$, under different lighting conditions.

5.1.4.2 Evaluation Metrics

We apply two widely-used measures to evaluate the performance of the clustering methods, the accuracy and the normalized mutual information (NMI) [8,12]. Suppose the predicted label of ${\mathit{x}}_i$ is ${\hat{y}}_i$, which is produced by the clustering method, and $y_i$ is the ground-truth label. The accuracy is defined as

$\begin{array}{c}\mathrm{Acc}=\frac{I_{\mathrm{\Phi }({\hat{y}}_i)\ne y_i}}{n},\hfill \end{array}$

where I is the indicator function, and Φ is the best permutation mapping function [26]. On the other hand, suppose the clusters obtained from the predicted labels ${\{{\hat{y}}_i\}}_{i=1}^n$ and ${\{y_i\}}_{i=1}^n$ are $\hat{C}$ and C, respectively. The mutual information between $\hat{C}$ and C is defined as

$\begin{array}{c}\mathrm{MI}(\hat{C},C)=\sum _{\hat{c}\in \hat{C},c\in C}p(\hat{c},c)\log \frac{p(\hat{c},c)}{p(\hat{c})p(c)},\hfill \end{array}$

where $p(\hat{c})$ and $p(c)$ are the probabilities that a data point belongs to the clusters $\hat{C}$ and C, respectively, and $p(\hat{c},c)$ is the probability that a data point jointly belongs to $\hat{C}$ and C. The normalized mutual information (NMI) is defined as

$\begin{array}{c}\mathrm{NMI}(\hat{C},C)=\frac{\mathrm{MI}(\hat{C},C)}{\max \{H(\hat{C}),H(C)\}},\hfill \end{array}$

where $H(\hat{C})$ and $H(C)$ are the entropies of $\hat{C}$ and C, respectively. NMI takes values in [0,1].

5.1.4.3 Comparison Experiments

Varying the Number of Clusters

On the COIL20 dataset, we reconduct the clustering experiments with the cluster number K ranging from 2 to 20, using EMC + SC, MMC + SC, joint EMC, and joint MMC. For each K, except for 20, 10 test runs are conducted on different randomly chosen clusters, and the final scores are obtained by averaging over the 10 tests. Fig. 5.1 shows the clustering accuracy and NMI measurements versus the number of clusters. It is revealed that the two joint methods consistently outperform their non-joint counterparts. When K increases, the performance of joint methods seems to degrade less slowly.

Initialization and Parameters

As a typical case in machine learning, we use SGD in a setting where it is not guaranteed to converge in theory, but behaves well in practice. As observed in our experiments, a good initialization of D and w can affect the final results notably. We initialize joint EMC by the D and w solved from EMC + SC, and joint MMC by the solutions from MMC + SC, respectively.

There are two parameters that we empirically set in ahead, the graph regularization parameter α and the dictionary size p. The regularization term imposes stronger smoothness constraints on the sparse codes when α grows larger. Also, while a compact dictionary is more desirable computationally, more redundant dictionaries may lead to less cluttered features that can be better discriminated. We investigate how the clustering performances EMC + SC, MMC + SC, joint EMC, and joint MMC change on the ORL dataset, with various α and p values. As depicted in Figs. 5.2 and 5.3, we observe that:

1. 1.  While α increases, the accuracy result will first increase then decrease (the peak is around $\alpha =1$). This could be interpreted as when α is too small, the local manifold information is not sufficiently encoded. On the other hand, when α turns overly large, the sparse codes are “oversmoothed” with a reduced discriminability.
2. 2.  Increasing dictionary size p will first improve the accuracy sharply, which, however, soon reaches a plateau. Thus in practice, we keep a medium dictionary size $p=128$ for all experiments.

5.2.2.1 Sparse Coding for Clustering

Assuming data samples $\mathit{X}=[{\mathit{x}}_1,{\mathit{x}}_2,\dots ,{\mathit{x}}_n]$, where ${\mathit{x}}_i\in {\mathit{R}}^{m\times 1}$ and $i=1,2,\dots ,n$. They are encoded into sparse codes $\mathit{A}=[{\mathit{a}}_1,{\mathit{a}}_2,\dots ,{\mathit{a}}_n]$, where ${\mathit{a}}_i\in {\mathit{R}}^{p\times 1}$ and $i=1,2,\dots ,n$, using a learned dictionary $\mathit{D}=[{\mathit{d}}_1,{\mathit{d}}_2,\dots ,{\mathit{d}}_p]$, where ${\mathit{d}}_i\in {\mathit{R}}^{m\times 1},i=1,2,\dots ,p$ are the learned atoms. The sparse codes are obtained by solving the following convex optimization (λ is a constant) problem:

$\begin{array}{c}\mathit{A}=\arg {\min }_{\mathit{A}}\frac{1}{2}||\mathit{X}\mathbf{-}\mathit{D}\mathit{A}|{|}_F^2+\lambda {\sum }_i||{\mathit{a}}_i|{|}_1,\hfill \end{array}$

In [12], the authors suggested that the sparse codes can be used to construct the similarity graph for spectral clustering [13]. Furthermore, to capture the geometric structure of local data manifolds, the graph regularized sparse codes are further suggested in [8,19] by solving

$\begin{array}{c}\mathit{A}=\arg {\min }_{\mathit{A}}\frac{1}{2}||\mathit{X}\mathbf{-}\mathit{D}\mathit{A}|{|}_F^2+\lambda {\sum }_i||{\mathit{a}}_i|{|}_1+\frac{\alpha }{2}\mathrm{Tr}(\mathit{A}\mathit{L}{\mathit{A}}^{\mathit{T}}),\hfill \end{array}$

where L is the graph Laplacian matrix and can be constructed from a prechosen pairwise similarity (affinity) matrix P. More recently in [31], the authors suggested to simultaneously learn feature extraction and discriminative clustering, by formulating a task-driven sparse coding model [17]. They proved that such joint methods consistently outperformed non-joint counterparts.

5.2.2.2 Deep Learning for Clustering

In [36], the authors explored the possibility of employing deep learning in graph clustering. They first learned a nonlinear embedding of the original graph by an auto encoder (AE), followed by a K-means algorithm on the embedding to obtain the final clustering result. However, it neither exploits more adapted deep architectures nor performs any task-specific joint optimization. In [37], a deep belief network with nonparametric clustering was presented. As a generative graphical model, DBN provides a faster feature learning, but is less effective than AEs in terms of learning discriminative features for clustering. In [38], the authors extended the seminonnegative matrix factorization (Semi-NMF) model to a Deep Semi-NMF model, whose architecture resembles stacked AEs. Our proposed model is substantially different from all these previous approaches, due to its unique task-specific architecture derived from sparse coding domain expertise, as well as the joint optimization with clustering-oriented loss functions.

5.2.3.1 TAGnet: Task-specific And Graph-regularized Network

Different from generic deep architectures, TAGnet is designed in a way to take advantage of the successful sparse code-based clustering pipelines [8,31]. It aims to learn features that are optimized under clustering criteria, while encoding graph constraints (5.16) to regularize the target solution. TAGnet is derived from the following theorem:

The complete proof of Theorem 5.3 can be found in the Appendix. Theorem 5.3 outlines an iterative algorithm to solve (5.16). Under quite mild conditions [39], after A is initialized, one may repeat the shrinkage and thresholding process in (5.17) until convergence. Moreover, the iterative algorithm could be alternatively expressed as the block diagram in Fig. 5.4B, where

$\begin{array}{c}\mathit{W}=\frac{1}{N}{\mathit{D}}^T,\mathit{S}=\mathit{I}-\frac{1}{N}{\mathit{D}}^T\mathit{D},\mathit{\theta }=\frac{\lambda }{N}.\hfill \end{array}$

In particular, we define the new operator “$\times \mathit{L}$”: $\mathit{A}\to -\frac{\alpha }{N}\mathit{A}\mathit{L}$, where the input A is multiplied by the prefixed L from the right and scaled by the constant $-\frac{\alpha }{N}$.

By time-unfolding and truncating Fig. 5.4B to a fixed number of K iterations ($K=2$ by default),⁴ we obtain the TAGnet form in Fig. 5.4A; W, S and θ are all to be learnt jointly from data, while S and θ are tied weights for both stages.⁵ It is important to note that the output A of TAGnet is not necessarily identical to the predicted sparse codes by solving (5.16). Instead, the goal of TAGnet is to learn discriminative embedding that is optimal for clustering.

To facilitate training, we further rewrite (5.18) as

$\begin{array}{c}{[h_{\mathit{\theta }}(\mathit{u})]}_i={\mathit{\theta }}_i\cdot \text{sign}({\mathit{u}}_i){(|{\mathit{u}}_i|/{\mathit{\theta }}_i-1)}_{+}={\mathit{\theta }}_i{h}_1({\mathit{u}}_i/{\mathit{\theta }}_i).\hfill \end{array}$

Equation (5.20) indicates that the original neuron with trainable thresholds can be decomposed into two linear scaling layers plus a unit-threshold neuron. The weights of the two scaling layers are diagonal matrices defined by θ and its element-wise reciprocal, respectively.

A notable component in TAGnet is the $\times \mathit{L}$ branch of each stage. The graph Laplacian L could be computed in advance. In the feed-forward process, a $\times \mathit{L}$ branch takes the intermediate ${\mathit{Z}}_k$ ($k=1,2$) as the input, and applies the “$\times \mathit{L}$” operator defined above. The output is aggregated with the output from the learnable S layer. In the back propagation, L will not be altered. In such a way, the graph regularization is effectively encoded in the TAGnet structure as a prior.

An appealing highlight of (D)TAGnet lies in its very effective and straightforward initialization strategy. With sufficient data, many latest deep networks train well with random initializations without pretraining. However, it has been discovered that poor initializations hamper the effectiveness of first-order methods (e.g., SGD) in certain cases [40]. For (D)TAGnet, it is, however, much easier to initialize the model in the right regime. This benefits from the analytical relationships between sparse coding and network hyperparameters defined in (5.19): we could initialize deep models from corresponding sparse coding components, the latter of which is easier to obtain. Such an advantage becomes much more important when the training data is limited.

5.2.3.2 Clustering-Oriented Loss Functions

Assuming K clusters, and $\mathit{\omega }=[{\mathit{\omega }}_1,\dots ,{\mathit{\omega }}_K]$ as the set of parameters of the loss function, where ${\mathit{\omega }}_i$ corresponds to the ith cluster, $i=1,2,\dots ,K$. In this section, we adopt the following two forms of clustering-oriented loss functions.

One natural choice of the loss function is extended from the popular softmax loss, and takes the entropy-like form as

$\begin{array}{c}C(\mathit{A},\mathit{\omega })=-{\sum }_{i=1}^n{\sum }_{j=1}^K{p}_{ij}\log p_{ij},\hfill \end{array}$

where $p_{ij}$ denotes the the probability that sample ${\mathit{x}}_{\mathit{i}}$ belongs to cluster j, $i=1,2,\dots ,N$ and $j=1,2,\dots ,K$,

$\begin{array}{c}{p}_{ij}=p(j|{\mathit{\omega }\mathbf{,}\mathit{a}}_i)=\frac{e^{-{\mathit{\omega }}_j^T{\mathit{a}}_i}}{{\sum }_{l=1}^K{e}^{-{\mathit{\omega }}_l^T{\mathit{a}}_i}}.\hfill \end{array}$

In testing, the predicted cluster label of input ${\mathit{a}}_i$ is determined using the maximum likelihood criterion based on the predicted $p_{ij}$.

The maximum margin clustering (MMC) approach was proposed in [3]. MMC finds a way to label the samples by running an SVM implicitly, and the SVM margin obtained would be maximized over all possible labels [5]. By referring to the MMC definition, the authors of [31] designed the max-margin loss as

$\begin{array}{c}C(\mathit{A},\mathit{\omega })=\frac{\lambda }{2}||\mathit{\omega }|{|}^2+{\sum }_{i=1}^{n}C({\mathit{a}}_i,\mathit{\omega }).\hfill \end{array}$

In the above equation, the loss for an individual sample ${\mathit{a}}_i$ is defined as

$\begin{array}{c}C({\mathit{a}}_i,\mathit{\omega })=\max (0,1+f^{r_i}({\mathit{a}}_i)-f^{y_i}({\mathit{a}}_i)),\hfill \\ \text{where}{y}_i=\underset{j=1,\dots ,K}{\arg \max }{f}^j({\mathit{a}}_i),r_i=\underset{j=1,\dots ,K,j\ne y_i}{\arg \max }{f}^j({\mathit{a}}_i),\hfill \end{array}$

where $f^j$ is the prototype for the jth cluster. In testing, the predicted cluster label of input ${\mathit{a}}_i$ is determined by weight vector that achieves the maximum ${\mathit{\omega }}_j^T{\mathit{a}}_i$.

Model Complexity. The proposed framework can handle large-scale and high-dimensional data effectively via the stochastic gradient descent (SGD) algorithm. In each step, the back propagation procedure requires only operations of order O(p) [29]. The training algorithm takes O(Cnp) time (C is a constant in terms of the total numbers of epochs, stage numbers, etc.). In addition, SGD is easy to be parallelized and thus could be efficiently trained using GPUs.

5.2.3.3 Connections to Existing Models

There is a close connection between sparse coding and neural network. In [29], a feed-forward neural network, named LISTA, is proposed to efficiently approximate the sparse code a of input signal x, which is obtained by solving (5.15) in advance. The LISTA network learns the hyperparameters as a general regression model from training data to their pre-solved sparse codes using back-propagation.

LISTA overlooks the useful geometric information among data points [8], and therefore could be viewed as a special case of TAGnet in Fig. 5.4 when $\alpha =0$ (i.e., removing the $\times \mathit{L}$ branches). Moreover, LISTA aims to approximate the “optimal” sparse codes preobtained from (5.15), and therefore requires the estimation of D and the tedious precomputation of A. The authors did not exploit its potential in supervised and task-specific feature learning.

5.2.5.1 Datasets and Measurements

We evaluate the proposed model on three publicly available datasets:

Although the paper only evaluates the proposed method using image datasets, the methodology itself is not limited to only image subjects. We apply two widely-used measures to evaluate the clustering performances, the accuracy and the normalized mutual information (NMI) [8,12]. We follow the convention of many clustering works [8,19,31] and do not distinguish training from testing. We train our models on all available samples of each dataset, reporting the clustering performances as our testing results. Results are averaged from 5 independent runs.

5.2.5.2 Experiment Settings

The proposed networks are implemented using the cuda-convnet package [34]. The network takes $K=2$ stages by default. We apply a constant learning rate of 0.01 with no momentum to all trainable layers. The batch size of 128. In particular, to encode graph regularization as a prior, we fix L during model training by setting its learning rate to be 0. Experiments run on a workstation with 12 Intel Xeon 2.67 GHz CPUs and 1 GTX680 GPU. The training takes approximately 1 hour on the MNIST dataset. It is also observed that the training efficiency of our model scales approximately linearly with data.

In our experiments, we set the default value of α to be 5, p to be 128, and λ to be chosen from [0.1, 1] by cross-validation.⁶ A dictionary D is first learned from X by K-SVD [20]; W, S and θ are then initialized based on (5.19), while L is also pre-calculated from P, which is formulated by the Gaussian kernel, ${\mathit{P}}_{ij}=\exp (-\frac{||{\mathit{x}}_i-{\mathit{x}}_j|{|}_2^2}{{\delta }^2})$ (δ is also selected by cross-validation). After obtaining the output A from the initial (D)TAGnet models, ω (or ${\mathit{\omega }}_k$) could be initialized based on minimizing (5.21) or (5.23) over A (or ${\mathit{Z}}_k$).

5.2.5.3 Comparison Experiments and Analysis

Benefits of the Task-specific Deep Architecture

We denote the proposed model of TAGnet plus entropy-minimization loss (EML) (5.21) as TAGnet-EML, and the one plus maximum-margin loss (MML) (5.23) as TAGnet-MML, respectively. We include the following comparison methods:

• •  We refer to the initializations of the proposed joint models as their “Non-Joint” counterparts, denoted as NJ-TAGnet-EML and NJ-TAGnet-MML (NJ is short for non-joint), respectively.
• •  We design a baseline encoder (BE), which is a fully-connected feed-forward network, consisting of three hidden layers of dimension p with ReLU neuron. It is obvious that the BE has the same parameter complexity as TAGnet.⁷ The BEs are also tuned by EML or MML in the same way, denoted as BE-EML or BE-MML, respectively. We intend to verify our important claim that the proposed model benefits from the task-specific TAGnet architecture, rather than just the large learning capacity of generic deep models.
• •  We compare the proposed models with their closest “shallow” competitors, i.e., the joint optimization methods of graph-regularized sparse coding and discriminative clustering in [31]. We reimplement their work using both (5.21) or (5.23) losses, denoted as SC-EML and SC-MML (SC is short for sparse coding). Since in [31] the authors already revealed that SC-MML outperforms the classical methods such as MMC and ${\ell }_1$-graph methods, we do not compare with them again.
• •  We also include Deep Semi-NMF [38] as a state-of-the-art deep learning-based clustering method. We mainly compare our results with their reported performances on CMU MultiPIE.⁸

As revealed by the full comparison results in Table 5.3, the proposed task-specific deep architectures outperform others with a noticeable margin. The underlying domain expertise guides the data-driven training in a more principled way. In contrast, the “general-architecture” baseline encoders (BE-EML and BE-MML) appear to produce much worse (even worst) results. Furthermore, it is evident that the proposed end-to-end optimized models outperform their “non-joint” counterparts. For example, on the MNIST dataset, TAGnet-MML surpasses NJ-TAGnet-MML by around 4% in accuracy and 5% in NMI.

Table 5.3

Accuracy and NMI performance comparisons on all three datasets

		TAGnet-EML	TAGnet-MML	NJ-TAGnet-EML	NJ-TAGnet-MML	BE-EML	BE-MML	SC-EML	SC-MML	Deep Semi-NMF
MNIST	Acc	0.6704	0.6922	0.6472	0.5052	0.5401	0.6521	0.6550	0.6784	/
	NMI	0.6261	0.6511	0.5624	0.6067	0.5002	0.5011	0.6150	0.6451	/
CMU	Acc	0.2176	0.2347	0.1727	0.1861	0.1204	0.1451	0.2002	0.2090	0.17
MultiPIE	NMI	0.4338	0.4555	0.3167	0.3284	0.2672	0.2821	0.3337	0.3521	0.36
COIL20	Acc	0.8553	0.8991	0.7432	0.7882	0.7441	0.7645	0.8225	0.8658	/
	NMI	0.9090	0.9277	0.8707	0.8814	0.8028	0.8321	0.8850	0.9127	/

By comparing the TAGnet-EML/TAGnet-MML with SC-EML/SC-MML, we draw a promising conclusion: adopting a more parameterized deep architecture allows a larger feature learning capacity compared to conventional sparse coding. Although similar points are well made in many other fields [34], we are interested in a closer look between the two. Fig. 5.6 plots the clustering accuracy and NMI curves of TAGnet-EML/TAGnet-MML on the MNIST dataset, along with iteration numbers. Each model is well initialized at the very beginning, and the clustering accuracy and NMI are computed every 100 iterations. At first, the clustering performances of deep models are even slightly worse than sparse-coding methods, mainly since the initialization of TAGnet hinges on a truncated approximation of graph-regularized sparse coding. After a small number of iterations, the performance of the deep models surpass sparse coding ones, and continue rising monotonically until reaching a higher plateau.

Effects of Graph Regularization

In (5.16), the graph regularization term imposes stronger smoothness constraints on the sparse codes with a larger α. It also happens to the TAGnet. We investigate how the clustering performances of TAGnet-EML/TAGnet-MML are influenced by various α values. From Fig. 5.7, we observe the identical general tendency on all three datasets. While α increases, the accuracy/NMI result will first rise then decrease, with the peak appearing for $\alpha \in [5,10]$. As an interpretation, the local manifold information is not sufficiently encoded when α is too small ($\alpha =0$ will completely disable the $\times \mathit{L}$ branch of TAGnet, and reduce it to the LISTA network [29] fine-tuned by the losses). On the other hand, when α is large, the sparse codes are “oversmoothed” with a reduced discriminative ability. Note that similar phenomena are also reported in other relevant literature, e.g., [8,31].

Furthermore, comparing Fig. 5.7A–F, it is noteworthy to observe how graph regularization behaves differently on three of them. We notice that the COIL20 dataset is the most sensitive to the choice of α. Increasing α from 0.01 to 50 leads to an improvement of more than 10%, in terms of both accuracy and NMI. It verifies the significance of graph regularization when training samples are limited [19]. On the MNIST dataset, both models obtain a gain of up to 6% in accuracy and 5% in NMI, by tuning α from 0.01 to 10. However, unlike COIL20 that almost always favors larger α, the model performance on the MNIST dataset tends to be not only saturated, but even significantly hampered when α continues rising to 50. The CMU MultiPIE dataset witnesses moderate improvements of around 2% in both measurements. It is not as sensitive to α as the other two. Potentially, it might be due to the complex variability in original images that makes the graph W unreliable for estimating the underlying manifold geometry. We suspect that more sophisticated graphs may help alleviate the problem, and we will explore it in the future.

Scalability and Robustness

On the MNIST dataset, we reconduct the clustering experiments with the cluster number $N_c$ ranging from 2 to 10, using TAGnet-EML/TAGnet-MML. Fig. 5.8 shows that the clustering accuracy and NMI change by varying the number of clusters. The clustering performance transits smoothly and robustly when the task scale changes.

To examine the proposed models' robustness to noise, we add various Gaussian noise, whose standard deviation s ranges from 0 (noiseless) to 0.3, to retrain our MNIST model. Fig. 5.9 indicates that both TAGnet-EML and TAGnet-MML own certain robustness to noise. When s is less than 0.1, there is even little visible performance degradation. While TAGnet-MML constantly outperforms TAGnet-EML in all experiments (as MMC is well-known to be highly discriminative [3]), it is interesting to observe in Fig. 5.9 that the latter is slightly more robust to noise than the former. It is perhaps owing to the probability-driven loss form (5.21) of EML that allows for more flexibility.

5.2.5.4 Hierarchical Clustering on CMU MultiPIE

As observed, CMU MultiPIE is very challenging for the basic identity clustering task. However, it comes with several other attributes: pose, expression, and illumination, which could be of assistance in our proposed DTAGnet framework. In this section, we apply a similar setting of [38] on the same CMU MultiPIE subset, by setting pose clustering as the Stage I auxiliary task, and expression clustering as the Stage II auxiliary task.⁹ In that way, we target $C_1({\mathit{Z}}_1,{\mathit{\omega }}_1)$ at 5 clusters, $C_2({\mathit{Z}}_2,{\mathit{\omega }}_2)$ at 6 clusters, and finally, $C(\mathit{A},\mathit{\omega })$ at 147 clusters.

The training of DTAGnet-EML/DTAGnet-MML follows the same aforementioned process except for considered extra back-propagated gradients from task $C_k({\mathit{Z}}_k,{\mathit{\omega }}_k)$ in Stage k ($k=1,2$). After that we test each $C_k({\mathit{Z}}_k,{\mathit{\omega }}_k)$ separately on their targeted task. In DTAGnet, each auxiliary task is also jointly optimized with its intermediate feature ${\mathit{Z}}_k$, which differentiates our methodology substantially from [38]. It is thus no surprise to see in Table 5.4 that each auxiliary task obtains much improved performances than [38].¹⁰ Most notably, the performances of the overall identity clustering task witness a very impressive boost of around 7% in accuracy. We also test DTAGnet-EML/DTAGnet-MML with only $C_1({\mathit{Z}}_1,{\mathit{\omega }}_1)$ or $C_2({\mathit{Z}}_2,{\mathit{\omega }}_2)$ kept. Experiments verify that by adding auxiliary tasks gradually, the overall task keeps being benefited. Those auxiliary tasks, when enforced together, can also reinforce each other mutually.

One might be curious of which one matters more in the performance boost: the deeply task-specific architecture that brings extra discriminative feature learning, or the proper design of auxiliary tasks that capture the intrinsic data structure characterized by attributes.

To answer this important question, we vary the target cluster number in either $C_1({\mathit{Z}}_1,{\mathit{\omega }}_1)$ or $C_2({\mathit{Z}}_2,{\mathit{\omega }}_2)$, and reconduct the experiments. Table 5.5 reveals that more auxiliary tasks, even those without any straightforward task-specific interpretation (e.g., partitioning the Multi-PIE subset into 4, 8, 12 or 20 clusters hardly makes semantic sense), may still help gain better performances. It is comprehensible that they simply promote more discriminative feature learning in a low-to-high, coarse-to-fine scheme. In fact, it is a complementary observation to the conclusion found in classification [42]. On the other hand, at least in this specific case, while the target cluster numbers of auxiliary tasks get closer to the ground truth (5 and 6 here), the models seem to achieve the best performances. We conjecture that when properly “matched”, every hidden representation in each layer is in fact most suited for clustering the attributes corresponding to the layer of interest. The whole model can be resembled to the problem of sharing low-level feature filters among several relevant high-level tasks in convolutional networks [44], but in a distinct context.

We hence conclude that the deeply-supervised fashion shows to be helpful for the deep clustering models, even when there are no explicit attributes for constructing a practically meaningful hierarchical clustering problem. However, it is preferable to exploit those attributes when available, as they lead to not only superior performances but more clearly interpretable models. The learned intermediate features can be potentially utilized for multitask learning [45].