9.1.3.1 One Layer Basic SCAE

Different from the conventional AE taking identical input and output features, the input and output of SCAE are different. Illustration of the full pipeline of SCAE can be found in Fig. 9.3. Suppose that we have $L=4$ style levels, and the inputs of the SCAE in the first layer are the features of images in the ascent order of style level, namely, $X_1$, $X_2$, $X_3$ and $X_4$. For example, $X_2$ is the set of features of images in style level $l_2$. Let $X^{(k)}$ be the input feature of the kth step, where $x_i^{(k)}\in X^{(k)}$ is the feature of the ith sample with the hidden representation learning from the $(k-1)$th step.

SCAE handles the following mappings:

$\{X_k^{(k)},X_{k+1}^{(k)},\dots ,X_L^{(k)}\}\to \{X_{k+1}^{(k)},X_{k+1}^{(k)},\dots ,X_L^{(k)}\},$

where only $X_k$ is pulled towards stronger style level $l_{k+1}$, and others keep the same style level before and after the kth step. In this way, the weak style level will be gradually pulled towards the strong style level, i.e., centralization, till $k=L-1$. Thus, the $L-1$ stacked AEs embody the stacked SCAE. Note that the mappings between $X_k$ and $X_{k+1}$ are still unclear. To keep the style level transition smooth, for each output feature $x\in X_{k+1}$, the nearest neighbor in $X_k$ in the same style class is applied as the corresponding input to learn SCAE. The whole process is shown in Fig. 9.3.

9.1.3.2 Stacked SCAE (SSCAE)

After introducing the one layer basic SCAE, we explain how to build the Stacked SCAE (SSCAE). Suppose that we have L style levels, in the kth step and style class c, the corresponding input for the output $x_{i,\xi +1}^{(k,c)}$ is given by

${\tilde{x}}_{i,\xi }^{(c)}=\{\begin{array}{cc}\hfill x_{j,\xi }^{(k,c)}\in u(x_{i,\xi +1}^{(k,c)}),\hfill & \text{if }\xi =k,\hfill \\ \hfill x_{i,\xi }^{(k,c)},\hfill & \text{if }\xi =k+1,\dots ,L,\hfill \end{array}$

where $u(x_{i,\xi +1}^{(k,c)})$ is the set of nearest neighbors of $x_{i,\xi +1}^{(k,c)}$ in the ξth layer.

As there are $N_c$ style classes, in each layer, we first separately learn parameters and hidden layer features $Z^{(k,c)}$ of SCAE of each class, and then combine all the $Z^{(k,c)}$ together as $Z^{(k)}$. Mathematically, SSCAE can be formulated as

$\begin{array}{c}\hfill \underset{\genfrac{}{}{0ex}{}{W_1^{(k,c)},b_1^{(k,c)}}{W_2^{(k,c)},b_2^{(k,c)}}}{\min }\sum _{\genfrac{}{}{0ex}{}{i,j}{x_{j,k}^{(k,c)}\in u(x_{i,k+1}^{(k,c)})}}{\Vert x_{i,k+1}^{(k,c)}-g(f(x_{j,k}^{(k,c)}))\Vert }^2+\\ \hfill \sum _{\xi =k+1}^L\sum _i{\Vert x_{i,\xi }^{(k,c)}-g(f(x_{i,\xi }^{(k,c)}))\Vert }^2+\lambda R(W_1^{(k,c)},W_2^{(k,c)}).\end{array}$

The problem above can be solved in a similar way as the conventional AE by back propagation algorithms [18]. Similarly, the deep structure can be built in a layer-wise way, which is outlined in Algorithm 9.1.

9.1.3.3 Visualization of Encoded Feature in SCAE

Fig. 9.4 shows the visualization of encoded features in the progressive step $k=1,2,3$ in manga style classification. Similar to Fig. 9.2, PCA is employed to reduce the dimensionality of the descriptors. The low-level input feature is “density of line segments” in [8]. In all the subfigures, a dot represents a sample. In the right sub-figures, colors are used to distinguish different styles, while in left subfigures, colors are used to distinguish different style levels.

From Fig. 9.4, we could see that at step $k=1$, in the right subfigures, the “shoji” samples (in red) and “shonen” samples (in blue) have overlaps. In the left subfigures, samples in the strong style level (in blue) are separated from each other. However, samples in weak style levels overlap with each other. For example, it is hard to separate the samples in cyan in two styles. During progressive steps, samples in different styles gradually separate due to the style centralization. At progressive step $k=2,3$, in the right subfigures we could see the samples in red and blue gradually become separable. In the left subfigures, we could see that during style centralizing, the weak style samples, shown in green, red, cyan and magenta move closely to the locations of blue samples in two different styles. Since the blue samples represent the strong style level and could easily be separated, the centralization process makes the weak style samples more distinguishable.

9.1.3.4 Geometric Interpretation of SCAE

Recalling the mappings presented in Eq. (9.4), if we consider $X_k$ as a corrupted version of $X_{k+1}$, SCAE can be recognized as a denoising autoencoder (DAE) [16] that uses partially corrupted feature as the input and the clean noise free features as the output to learn robust representations [16,19]. Thus, inspired by the geometric perspective under the manifold assumption [20], we may offer a geometric interpretation for the SCAE, analogical to that of DAE [16].

Fig. 9.5 illustrates the manifold learning perspective of SCAE where images of Goth fashion style are shown as the examples. Suppose that the higher level $l_{k+1}$ Goth style images lie close to a low dimensional manifold. The weak style examples are more likely being far away from the manifold than the higher level ones. Note that $x_{j,k}$ is the corrupted version of $x_{i,k+1}$ by the operator $q(X_k|X_{k+1})$, and therefore lies far away from the manifold. In SCAE, $q(X_k|X_{k+1})$ manages to find the nearest neighbor of $x_{i,k+1}$ in level $l_k$ to obtain the corrupted the version of $x_{i,k+1}$ as $x_{j,k}$ in the same category. During the centralizing training, similar to DAE, SCAE learns the stochastic operator $p(X_{k+1}|X_k)$ that maps the lower style level samples $X_k$ back to a higher level. Successful centralization implies that the operator $p(\cdot )$ is able to map spread-out weak style data back to the strong style data which are close to the manifold.

9.1.4.1 Low-Rank Constraint on the Model

Low-rank constraint has been widely used for discovering underlying structure and data recovery [23,24]. It has been suggested to extract the salient features despite of noises in the following formulations for latent low-rank representation (LaLRR) [24]. As described above, similar weights are expected across different feature descriptors for the same patch. This will give rise to an interesting phenomenon: if we concatenate all the weight matrices of different feature descriptors together denoted as W, the rank of W should be low. The main reason is the similar values across different columns in W. Thus, this idea is pursued through a low-rank matrix constraint on the concatenated weight matrix W.

To that end, we introduce a rank-constrained autoencoder model [1] to pursue the low-rankness of the weight matrix W in the following formula:

$\underset{W,E}{\min }{\Vert W\Vert }_{⁎}+\lambda {\Vert E\Vert }_{2,1},\text{ s.t. }X=W\tilde{X}+E,$

where $\tilde{X}$ is the input feature and X is the output feature of AE, similar to SCAE; ${\Vert \cdot \Vert }_{⁎}$ is the nuclear norm of a matrix used as the convex surrogate of the original rank constraint, ${\Vert E\Vert }_{2,1}$ is the matrix ${\ell }_{2,1}$ norm for characterizing the sparse noise E, and λ is a balancing parameter. Intuitively, the residual term E encourages sparsity, as both W and $W\tilde{X}$ are low-rank matrices. This is also well explored by many low-rank recover/representation works [24,23,14,22]. Equation (9.7) can also be considered as a special form of the work [24] by only considering features in the column space.

Fig. 9.6A illustrates this phenomenon. Each row represents a specific feature of one patch, and different colors indicate different kinds of features. In addition, each column represents all features of one sample. It can be seen that the concatenated features for one sample are formulated by first stacking different features of the same patch, and then stacking different patches. Note that for simplicity, one cell is used to represent one kind of features of one patch. We could see that ideally, both eye-feature1 and eye-feature2 should have the highest weights, and nose-feature1 and nose-feature2 have the second highest weights. Meanwhile, the less important patches cheek-feature1 and cheek-feature2 should be given lower weights to suppress noises. In brief, based on the definition of the matrix rank, the consensus constraint among different features induces the low-rank structure of matrix W identified in Fig. 9.6A.

9.1.4.2 Group Sparsity Constraint on the Model

To further consider the regularizers introduced in Eq. (9.3) under the new rank constraint autoencoder framework, we introduce an additional group sparsity constraint on W. The reasons are three-fold. First, like conventional regularizers in neural networks, it helps avoid the arbitrarily large magnitude in W. Second, it enforces the row-wise selection on W to ensure a better consensus effect together with the low-rank constraint. Third, it helps find the most discriminative representation.

Mathematically, we can achieve this by adding a matrix ${\ell }_{2,1}$ norm ${\Vert W\Vert }_{2,1}={\sum }_{i=1}^D{\Vert W(i)\Vert }_2$ which is equal to the sum of the Euclidean norms of all columns of W. The ${\ell }_2$-norm constraint is applied to each group separately (i.e., each column of W). It ensures that all elements in the same column are either approaching zero or nonzero at the same time. The ${\ell }_1$ norm guarantees that only a few columns are nonzero. Fig. 9.6A also illustrates how the group sparsity works. If the entry in the jth row and ith column of X indicates an unimportant patch, all the entries from the jth row are also less important, and vice-versa. As discussed above, these patches should have been assigned very low or zero weights to suppress the noise.

9.1.4.3 Rank-Constrained Group Sparsity Autoencoder

Considering both rank and group sparsity constraints, the objective function of the rank-constrained group sparsity autoencoder (RCGSAE) is formulated as

${\hat{W}}_r=\underset{\text{rank}(W)\le r}{\arg \min }\{||X-W\tilde{X}|{|}_F^2+2\lambda {\Vert W\Vert }_{2,1}\},$

where ${\hat{W}}_r$ is the optimized matrix projection in Eq. (9.8) when the $\text{rank}(W)\le r$; λ is the balancing parameter. Note that we skip the sparse error term in Eq. (9.7) for simplicity. Clearly, for $r=D$, we have no rank constraint in Eq. (9.8) which degrades to a group sparsity problem, while for $\lambda =0$, we obtain the reduced-rank regression estimator. Thus, an appropriate rank r and λ will balance the two parts to yield better performance.

Low-rank and group sparsity constraints not only minimize the difference of patch weights among different descriptors, but also assign the weights of unimportant weights to be all zero. In this way, the influence of the noise of unimportant patches are decreased and we are able to find the most discriminative representation.

9.1.4.4 Efficient Solutions for RCGSAE

Here, we introduce how to solve the objective function of RCGSAE. It should be noted that the problem defined in Eq. (9.8) is nonconvex and has no closed-form solutions for W. Thus, an iterative algorithm is used to solve this in a fast manner. As shown in Fig. 9.6B, W is factorized into $W=V^{\prime }S$, where V is an $r\times D$ orthogonal matrix, $V^{\prime }$ is the inverse of V and S is an $r\times D$ matrix with the group sparse constraint [25]. Then the optimization problem of W in Eq. (9.8) turns out to be

$(\hat{S},\hat{V})=\underset{S\in {\mathbb{R}}^{r\times D},V\in {\mathbb{R}}^{r\times D}}{\arg \min }\{||X-V^{\prime }S\tilde{X}|{|}_F^2+2\lambda ||S|{|}_{2,1}\}.$

The details of the algorithm are outlined in Algorithm 9.2. In addition, the following theorem presents a convergence analysis for Algorithm 9.2 and ensures that the algorithm converges well regardless of the initial point.

The proof is given in Appendix A.7 of [25].

9.1.4.5 Progressive CSCAE

After introducing RCGSAE, we introduce progressive CSCAE, which stacks multiple RCGSAEs in a progressive way. In the kth step, it will increase the style level of $\tilde{X}$ from k to $k+1$, and meanwhile keep the consensus of different features. As shown in Algorithm 9.3, the input of the CSCAE is the style feature X. The output of the algorithm is the encoded feature $h^{(k)}$ and the projection matrix $W^{(k)}$ in the kth step, $k\in [1,L-1]$.

To initialize, we set $h^{(0)}=X$. For step k, the encoded feature $h^{(k-1)}$ is regarded as the input. First, we calculate the output for $X^{(k)}$ as described in Eq. (9.5). Second, we optimize W by CSCAE using Algorithm 9.2. The learned W achieves the properties of both group sparsity and low-rankness. Afterwards, we calculate the new features $W\tilde{X}$ followed by a nonlinear function for normalization. Following the suggestion in [26], we use $\tanh (\cdot )$ to achieve the nonlinearity performance. The encoded feature $h^{(k)}$ is regarded as the input in the next step $k+1$. After $(L-1)$ steps, we obtain $(L-1)$ sets of weight matrices and the corresponding encoded features.

9.1.5.1 Dataset

Fashion style classification dataset. Kiapour et al. collected a fashion style dataset named Hipster Wars [7] including 1,893 images of 5 fashion styles, as shown in Fig. 9.7. They also launched an online style comparison game to collect human judgments and provide style level information for each image.

Pose estimation is applied to extract key boxes of the human body [27]. Seven dense features are extracted for each box following [7]: RGB color value, LAB color value, HSI color value, Gabor, MR8 texture response [28], HOG descriptor, and the probability of pixels belonging to skin categories.

Manga style classification dataset. Chu et al. collected a shonen (boy targeting) and shojo (girl targeting) manga dataset, which includes 240 panels [8]. Six computational features, including angle between lines, line orientation, density of line segments, orientation of nearby lines, number of nearby lines with similar orientation and line strength, are calculated. Example shojo and shonen style panels are shown in Fig. 9.8.

Since Manga dataset does not provide manually labeled style level information, an automatic way to calculate the style level is applied. First, a mean-shift clustering is applied to find the peak of the density of the images for each style based on the line strength feature. Line strength feature is most discriminative among 6 features measured by p-values. Images at the peak of the density are regarded the most representative ones. Then images are ranked according to the distances between the most centralized images, and evenly divided from lowest to highest distance as five style levels.

Architecture style classification dataset. Xu et al. collected an architecture style dataset containing 5000 images [11]. It is the largest publicly available dataset for architectural style classification. The category definition is according to “Architecture_by_style” of Wikimedia.² Example images of ten classes are shown in Fig. 9.9. As there is no manually labeled style level information, a similar strategy to that used in Manga dataset is applied to generate the style level information.

9.1.5.2 Compared Methods

Here we briefly describe several low-level feature representation based methods on fashion [7,29,6], manga [8] and architecture [11] style classification tasks. Then we describe general deep learning methods and deep learning methods for style classification tasks.

Low-level based methods:

Kiapour et al. [7] applied mean-std pooling for 7 dense low-level features from clothing images, and then concatenated them as the input to the classifier and named the concatenated features as the style descriptor.

Yamaguchi et al. [29] approached clothing parsing via retrieval, and considered robust style feature for retrieving similar style. They concatenated the pooling features similar to [7], followed by PCA for dimension reduction.

Bossard et al. [6] focused on apparel classification with style. For style feature representation, they first learned a codebook through k-means clustering based on low-level features. Then the bag-of-words features were further processed by spatial pyramids and max-pooling.

Chu and Chao [8] designed 6 computational features derived from line segments to describe drawing styles. Then they concatenated 6 features with equal weights.

Xu et al. [11] adopted the deformable part-based models (DPM) to capture the morphological characteristics of basic architectural components, where DPM describes an image by a multiscale HOG feature pyramid.

MultiFea [12,1]. The baseline in [11] only employed the HOG feature, but CSCAE employed multiple features. Another low-level feature based method using multiple features is generated for fair comparisons. Six low-level features are chosen according to SUN dataset,³ including HoG, GIST, DSIFT, LAB, LBP, and tinny image. First, PCA dimension reduction is applied to each feature. Then, the normalized features are concatenated together.

Deep learning based methods:

AE [13]. A conventional autoencoder (AE) [13] is applied for learning mid/high-level features. The inputs of AE are the concatenated low-level features.

DAE [26]. Marginalized stacked denoising autoencoder (mSDA) [26] is a widely applied version of denoising autoencoder (DAE). Both SCAE and DAE share the spirit of “noise”. The inputs of the DAE are corrupted image features. As in [15], [19] and [26], the corruption rate of the dropout noise is learned by cross-validation. Other settings such as the number of stacked layers and the layer size are the same as SCAE.

SCAE [12,1]. Style centralizing autoencoder (SCAE) [12,1] is applied for learning mid/high-level features. The inputs of SCAE are the concatenated various kinds of low-level feature descriptors, i.e., an early fusion for SCAE.

CAE [1]. To demonstrate the roles of “progressive style centralizing” in CSCAE, a consensus autoencoder (CAE) is generated as another baseline. CAE is similar to CSCAE except that in each progressive step, the input and output features are exactly the same.

CSCAE [1]. This method contains the full pipeline of consensus style centralizing autoencoder (CSCAE) in [1].

In all the classification tasks, cross-validation is applied with a $9:1$ training-to-test ratio. SVM classifier is applied in Hipster Wars and Manga datasets by following the settings in [7,8], while nearest neighbor classifier (NN) is applied on Architecture datasets. For all deep learning baselines, same number of layers are used.

9.1.5.3 Experimental Results

Results on fashion style classification

Table 9.1 shows the accuracy (%) of low-level and deep learning based methods under different style levels $L=1,\dots ,5$. First, from Table 9.1 we can see that deep learning based methods (bottom 5 in the table) in general perform better than low-level based methods (top 3 in the table). CSCAE and CAE achieve the best and second best performance under all the style levels. When comparing DAE with SCAE, we could see that SCAE outperforms DAE, which shows the effectiveness of the style centralizing strategy compared with general denoising strategy for style classification. When comparing CSCAE with CAE, we see that CSCAE outperforms CAE in all the settings, which also due to the style centralizing learning strategy.

Table 9.1

Performances (%) of fashion style classification on Hipster Wars dataset. The best and second best results under each setting are shown in bold font and underline

Performance	$L=5$	$L=4$	$L=3$	$L=2$	$L=1$
Kiapour et al. [7]:	77.73	62.86	53.34	37.74	34.61
Yamaguchi et al. [29]:	75.75	62.42	50.53	35.36	33.36
Bossard et al. [6]:	76.36	62.43	52.68	34.64	33.42
AE [13]	83.76	75.73	60.33	44.42	39.62
DAE [26]	83.89	73.58	58.83	46.87	38.33
SCAE [12,1]	84.37	72.15	59.47	48.32	38.41
CAE [1]	87.55	76.34	63.55	50.06	41.33
CSCAE [1]	90.31	78.42	64.35	54.72	45.31

Results on manga style classification

Table 9.2 shows the accuracy (%) of the deep learning based methods (bottom 5 in the table) and low-level feature based method (top in the table) under five style levels on Manga dataset. CSCAE and CAE achieve the highest and second highest performance under all the style levels. Compared to fashion and architecture images, CSCAE works especially well for the face images. We think that the face structure and different weights of patches (e.g., the weights of eye patch should be higher than cheek patch) work especially well with the low-rankness and group sparsity assumptions.

Table 9.2

Performance (%) of manga style classification

Performance	$L=5$	$L=4$	$L=3$	$L=2$	$L=1$
LineBased [8]	83.21	71.35	68.62	64.79	60.07
AE [13]	83.61	72.52	69.32	65.18	61.28
DAE [26]	83.67	72.75	69.32	65.86	62.86
SCAE [12,1]	83.75	73.43	69.32	65.42	63.60
CAE [1]	85.35	76.45	72.57	67.85	65.79
CSCAE [1]	90.70	80.96	77.97	77.63	79.90

Results on architecture style classification

Table 9.3 shows the classification accuracy on the architecture style dataset. First, comparing the method in [8] with MultiFea, we learn that the additional low-level features do contribute to the performance. Second, all the deep learning methods (bottom 5 in the table) achieve better performance than low-level features based methods (top 2 in the table).

Table 9.3

Performance (%) of architecture style classification

Performance	$L=5$	$L=4$	$L=3$	$L=2$	$L=1$
Xu et al. [8]	40.32	35.96	32.65	33.32	31.34
MultiFea	52.78	53.00	50.29	49.93	46.79
AE [13]	58.72	56.32	52.32	52.32	48.31
DAE [26]	58.55	56.99	53.34	52.39	50.33
SCAE [12,1]	59.61	57.00	53.27	54.28	51.76
CAE [1]	59.54	58.66	54.55	53.46	51.88
CSCAE [1]	60.37	59.41	55.12	54.74	54.68

9.2.4.1 Problem Formulation

A typical objective function for autoencoder with N training samples is

$\underset{W,b}{\min }\frac{1}{N}\sum _{i}L(W,b;x_i,y_i)+\lambda \mathrm{\Omega }(W),$

where $L(W,b;x,y)$ is the loss function, $\mathrm{\Omega }(W)$ is the regularization term, $W,b$ are model parameters, $x_i,y_i$ are input and target value, and weight decay parameter λ balances the relative importance of the two terms. In this part, the loss function is implemented by the squared error between hypothesis and target values, namely

$L(W,b;x_i,y_i)={\Vert h_{W,b}(x_i)-y_i\Vert }^2,$

and the regularization term can be written in square sum of all elements in the weight matrix of the first and second layers, equal to the norms ${\Vert W^{(1)}\Vert }_F^2$ and ${\Vert W^{(2)}\Vert }_F^2$, where ${\Vert \cdot \Vert }_F$ is the matrix Frobenius norm.

Suppose we have k family faces, then we can formulate the new loss function for the family faces guided autoencoders by

$\frac{1}{N\times k}\sum _{i,j}{\Vert h_{W_j,b_j}(x_i)-{\tilde{x}}_{(i,j)}\Vert }^2,$

where j indexes the family face, and k denotes the number of family faces in each family. Apparently, Eq. (9.13) includes k autoencoders, and these encoders can be learned at the same time. Therefore, we call it parallel autoencoders, which provide a wide structure rather than a deep one.

However, trivially combining these autoencoders will not necessarily boost the final performance since there are no connections between autoencoders. To guarantee all the encoders share common feature spaces, we introduce a low-rank regularization term to encourage the weight matrices assembled from k autoencoders in a matrix low-rank structure, which ensures the familial features generated by the hidden layers from k autoencoders to have common feature space. Combining with the parallel autoencoders, the proposed low-rank regularized objective function is written as

$\begin{array}{cc}\hfill & \underset{W_j,b_j}{\min }\frac{1}{N\times k}\sum _{i,j}{\Vert h_{W_j,b_j}(x_i)-{\tilde{x}}_{(i,j)}\Vert }^2\hfill \\ \hfill & +{\lambda }_1({\Vert {\mathcal{W}}^{(1)}\Vert }_F^2+{\Vert {\mathcal{W}}^{(2)}\Vert }_F^2)+{\lambda }_2{\Vert {\mathcal{W}}^{(1)}\Vert }_{⁎},\hfill \end{array}$

where ${\mathcal{W}}^{(1)}=[W_1^{(1)},\dots ,W_k^{(1)}]$ is a column-wise matrices concatenation, ${\mathcal{W}}^{(2)}=[W_1^{(2)},\dots ,W_k^{(2)}]$ has a similar structure, and ${\Vert \cdot \Vert }_{⁎}$ is the matrix nuclear norm, which is identified as convex surrogate of the original rank minimization problem. Solving this problem is nontrivial since we introduce a nonsmooth term. Therefore, we cannot directly use gradient descent method to solve both ${\mathcal{W}}^{(1)}$ and ${\mathcal{W}}^{(2)}$ following the traditional way for the proposed autoencoders. Since in practice ${\mathcal{W}}^{(1)}$ and ${\mathcal{W}}^{(2)}$ are solved in an iterative way, which means one's update relies on another's update, we break down it into two subproblems and concentrate on ${\mathcal{W}}^{(1)}$ first.

9.2.4.2 Low-Rank Reframing

Although the nonsmooth property of low-rank prevents from solving it directly, we need to keep it since it helps in recovering the common feature space among different encoders. Recently, atomic decomposition [61] has been proposed to tackle large-scale low-rank regularized classification problem [60], where the matrix trace norm is converted to vector $l_1$-norm and therefore can be solved efficiently through coordinate descent algorithm. We borrow the idea of low-rank reframing and use it to solve our problem since it is fast and efficient in our problem.

Suppose there is an overcomplete and uncountable infinite dictionary of all possible “atoms”, or rank-one matrices in our problem, that is denoted by a matrices set $\mathcal{M}$,

$\mathcal{M}=\{u{v}^T|u\in {\mathbb{R}}^{d_1},v\in {\mathbb{R}}^{d_2},{\Vert u\Vert }_2={\Vert v\Vert }_2=1\}.$

Note that $\mathcal{M}$ does not necessarily build a basis in ${\mathbb{R}}^{d_1\times d_2}$. Further, we use $\mathcal{I}$ to represent the index set spanning the rank-1 matrix in the $\mathcal{M}$, namely,

$\mathcal{M}=\{M_i\in {\mathbb{R}}^{d_1\times d_2}|i\in \mathcal{I}\}=\{u_i{v}_i^T|i\in \mathcal{I}\}.$

Next, we consider a vector $\theta \in {\mathbb{R}}^{\mathcal{I}}$ and its support $\text{supp}(\theta )=\{i,{\theta }_i\ne 0\}$, and further define a vector set as $\mathrm{\Theta }=\{\theta \in {\mathbb{R}}^{\mathcal{I}}|\text{supp}(\theta )\text{ is finite}\}$. Then we have a decomposition for the matrix ${\mathcal{W}}^{(1)}$ onto atoms in $\mathcal{M}$,

${\mathcal{W}}^{(1)}=\sum _{i\in \text{supp}(\theta )}{\theta }_i{M}_i.$

Actually, this is the atom decomposition of the matrix ${\mathcal{W}}^{(1)}$ onto a series of rank-1 matrices and, since the atom dictionary is overcomplete, this decomposition might not be unique. Through the formulation of this decomposition, we can reframe the original low-rank regularized problem proposed in Eq. (9.14) into the following one:

$\underset{\theta \in {\mathrm{\Theta }}^{+}}{\min }I(\theta )=\underset{\theta \in {\mathrm{\Theta }}^{+}}{\min }{\lambda }_2\sum _{i\in \text{supp}(\theta )}{\theta }_i+R({\mathcal{W}}_{\theta }),$

where $R({\mathcal{W}}_{\theta })$ represents the remaining parts in Eq. (9.14) other than low-rank regularizer. We can see that ${\sum }_{i\in \text{supp}(\theta )}{\theta }_i$ is essentially the vector $l_1$-norm for θ.

9.2.4.3 Solution

We describe how to use coordinate descent method to solve Eq. (9.18). The algorithm described here actually belongs to the family of atom descent algorithms, whose stopping criteria are given by ε-approximation optimality:

$\{\begin{array}{cc}\forall i\in \mathcal{I}:\frac{\partial R(\mathcal{W})}{\partial {\theta }_i}\ge -{\lambda }_2-\epsilon ,\hfill & \hfill \\ \forall i\in \text{supp}(\theta ):|\frac{\partial R(\mathcal{W})}{\partial {\theta }_i}+{\lambda }_2|\le \epsilon .\hfill \end{array}$

The basic flow of coordinate descent is similar to gradient descent, but at each iteration with ${\theta }_t$,⁴ we need to find the coordinate along which we can achieve the steepest descent while remaining in ${\mathrm{\Theta }}^{+}$. In our model, this is equal to pick $i\in \mathcal{I}$ with the largest $-\partial I({\theta }_t)/\partial {\theta }_i$.

In practice, it is easy to find that the coordinate corresponding to the largest $-\partial I({\theta }_t)/\partial {\theta }_i$ can be computed by the singular vector pair corresponding to the top value of the matrix $-\mathrm{\nabla }R({\mathcal{W}}_{{\theta }_t})$, namely,

$\underset{{\Vert u\Vert }_2={\Vert v\Vert }_2=1}{\max }{u}^T(-\mathrm{\nabla }R({\mathcal{W}}_{{\theta }_t}))v.$

There are two possible cases after we find the descent direction: if coordinate $i\notin \text{supp}({\theta }_t)$, then we only move in the positive direction; else we can move in either the positive or negative direction. To avoid aggressive update, we use a steep-enough direction (up to $\epsilon /2$) instead in the practice.

In each iteration, after we find the steep-enough direction defined by $u_t{v}_t^T$, we need to tackle the step size of each update. Since we do not adopt the steepest direction in the algorithm, we will use a line-search to guarantee the objective value $I(\theta )$ is decreased in each iteration. So each update can be described as ${\mathcal{W}}_{t+1}={\mathcal{W}}_t+\delta u_t{v}_t^T$, and ${\theta }_{t+1}={\theta }_t+\delta e_t$, where $e_t$ is an indicator vector, with the tth element being 1 in the tth iteration. The overall process can be found in Algorithm 9.4.

Recall that the proposed regularized family faces guided parallel autoencoders in Eq. (9.14) should have been solved by gradient descent algorithm, however, the nonsmoothness property of the new regularized term makes it non-differential. Algorithm 9.4 actually tells us how to solve it with gradient algorithm even with low-rank term. To solve the original problem, we still need to run gradient descent algorithm on Eq. (9.14) with partial derivative solved by back-propagation. The difference is each time when we update ${\mathcal{W}}^{(1)}$, we need to run one iteration of Algorithm 9.4. The entire solution for Eq. (9.14) can be found in Algorithm 9.5.

Remarks. (1) We mainly focus on the solution of rPAE in this section and do not list the detailed solution of autoencoders, which involves “feed-forward” and “back-propagation” processes, and “nonlinear activation” function, since they can be easily checked from many relevant works. (2) We empirically set the model parameters as: ${\lambda }_1={\lambda }_2=0.1$, $T=50$, and $\epsilon =0.01$ in our experiments, and achieve acceptable results. There might be better settings for them, but we leave the space for discussions of other important model parameters. (3) Although rPAE is proposed for FMR problem, it can easily adapt to kinship verification problems by sampling a few subsets of the training data to guide the learning of parallel autoencoders. We will introduce the implementation details in the experiment section. (4) The deep structure can be trained in a layer-wise way which only involves the training of single hidden layer of rPAE.

9.2.5.1 Kinship Verification

Kinship Face in the Wild (KFW)⁵ is a database of face images collected for studying the problem of kinship verification from unconstrained face images. It includes two parts, KFW-I and KFW-II, both of which include four detailed kin relations: father–son (F–S), father–daughter (F–D), mother–son (M–S), mother–daughter (M–D). In the KFW-I dataset, there are 156, 134, 116, and 127 pairs of kinship images for these four relations, while in KFW-II dataset, each relation contains 250 pairs of kinship images. The difference of these two datasets is that KFW-I uses facial images from different photo to build kinship pairs, but KFW-II uses facial images from the same photo. Therefore, the variations of lighting and expressions may be more dramatic in KFW-I, leading to a relatively lower performance. All faces in the database have been manually aligned and cropped to $64\times 64$ images to exclude background. Sample images can be found in Fig. 9.13. In the following KFW relevant experiments, we use the HOG features provided by KFW benchmark website as the input to rPAE.

Different from family faces guided rPAE in FMR, here we sample a few small sets from the training data and use each of them to build an autoencoder and all of them to build rPAE. For each specific relation, we randomly sample half of the images from the given positive pairs, and then put these samples back. We repeat this several times to obtain enough sets for the training of rPAE. The input of rPAE is [child, parent] and corresponding target value is [parent, child]. After we learn the rPAE, we encode the input feature through rPAE, and concatenate all of them to form the final feature vector which will be fed to a binary SVM classifier. We use the absolute value of vector difference from positive kinship pairs as the positive samples and that from negative kinship pairs as the negative samples. Note that we use LibSVM [63] with rbf kernel to train the binary model and use its probabilistic output to compute both ROC and AUC. The model parameters of SVM such as slack variable C and bandwidth σ is learned through grid search on the training data. We strictly follow the benchmark protocol of KFW, and report the image restricted experimental results with five-fold cross-validation.

There are several key factors in the model: the number of hidden units in each layer, the number of hidden layers, and the number of sampling to generate different autoencoders. To evaluate their impacts on our model, we experiment step by step to show their effects. We first use a single hidden layer autoencoder and experiment with four kin relations on KFW-II, with the number of hidden units changing from 200 to 1800, as shown in Fig. 9.14A. It can be seen from four relations that there exists a performance peak within this range, and in general it differs from one relation to another. To balance the performance and the time cost, we suggest to use 800 hidden units in the following experiments. Second, we gradually add the number of layers from 1 to 4 and see if it helps with the performance in Fig. 9.14B. Here, we empirically choose $[800,200,100,50]$ as our deepest layersize setting, and add layer one by one to see the impacts. Clearly, deep structure always benefits the feature learning, which has been reported by many deep learning works. Therefore, we take $[800,200,100,50]$ as our layersize setting. In addition, we also conduct experiments to analyze the number of autoencoder in rPAE in Fig. 9.14C, from which we can observe that more sampling could bring in performance boost, but it takes more time as well. Therefore, we suggest to use 10 parallel autoencoders in our framework. Finally, from the three experiments, we can also conclude that the parallel structure and regularizer is able to boost the performance compared to the single autoencoder case in Figs. 9.14A and 9.14B.

We further compare our method with other existing state-of-the-art methods on KFW-I and KFW-II, and show the results of ROC curves and area under curve (AUC) in Figs. 9.14 and 9.15 and Tables 9.4 and 9.5. Among these comparisons, “HOG” means we directly use HOG feature provided by KFW benchmark website as the input to the binary SVM, to train and classify the kinship pairs. “SILD (image restricted)” [62] and “NRML (image unrestricted)” [36,40] mean that we first feed the original HOG features to the two comparisons and then use their output as the new features for the binary SVM. From the result, we can see that almost all the methods perform better than the direct use of HOG, which demonstrates that these methods work well on kinship verification problem. With the help of rPAE, our method performs better than the other two closely related methods in the four cases on both KFW-I and KFW-II. Finally, we also compare with the most recent work based on gated autoencoders (GAE) [55], which is shown in Table 9.6.

9.2.5.2 Family Membership Recognition

We conduct familial feature based face recognition experiments in this section, which includes two parts: (1) family membership recognition and (2) face identification through familial features. For both experiments, we use Family101 database published in [37]. Family 101 database has 101 different family trees, 206 nuclear families, and 607 individuals, including 14,816 images. Most of individual in the database are public figures. Since the number of family members in each family tree are different, and the image qualities are diverse, we select 25 different family trees, and ensure that each family tree contains at least five family members. In the preprocessing, we found that there are some dominant members in the family tree, i.e., an individual with significantly many images. Therefore, we restrict the number of each individual's images less than 50. In our test, we randomly select one family member as test and use rest family members for training (including both rPAE training and classifier training). We use nearest neighbor as the classifier, repeat this five times, and the average performance plus standard deviation is reported in Table 9.7.

In the following evaluation, we still follow the parameters setting of kinship verification discussed in the last section, and use local Gabor [33] as our input feature. That is, we first crop the image to $127\times 100$ and then partition the faces into components by the four key points on the face: two eyes, nose tip, center of the mouth. Gabor features are extracted from each component in 8 directions and 5 magnitudes, and then concatenate to a long vector. We use PCA to reduce the vector length to 1000 for simplicity. From Table 9.7, we can see that family membership recognition is very challenging [37], and fewer results have been reported before. Most methods are slightly better than random guess. Nonetheless, our method performs best thanks to family face + rPAE framework. It is interesting to find that the standard deviation is relatively large in all experiments. The reason is when selected as the test, the current individual may not inherit too much character from the family members, while for others they may inherit more. Therefore, the accuracy fluctuates significantly during the five evaluations.

In addition, we showcase how the familial feature assists in general face recognition. If we consider all the training data in the FMR as references/gallery in the face recognition, then FMR can also be regarded as a face recognition problem. The only difference is in face recognition problem, references are other facial images of the test individual, while in FMR, references are facial images of family members'. From Table 9.7, we are inspired that FMR can boost the face recognition since FMR can identify people by auxiliary data. Therefore, in the following experiments, we compare face recognition (FR) results with/without auxiliary data. In Fig. 9.16, we can observe that familial features and family member's facial images are helpful in face recognition problem.

Finally, we illustrate some face recognition results with query images and returned nearest neighbor based on the proposed familial feature. In Fig. 9.17, we show three cases in rows 1–3. The first one is a failure case that returns incorrect facial images from other family. The second query image is correctly recognized because its nearest neighbor is from the same family as the query image. In the third case, we use doted frame to represent the training images from the query itself which follows conventional face recognition procedure. From Figs. 9.16 and 9.17, we can conclude that the proposed approach indeed can help with face recognition using family members.