Multi-View Exclusive Unsupervised Dimension Reduction for Video-Based Facial Expression Recognition

1 Introduction

Automatic facial expression recognition (FER) plays an important role in pattern recognition and computer vision. Its extensive applications include: human-computer interaction systems, psychology, and security. Over the past decade, there has been extensive productive and fruitful study of static images [Gu et al., 2012]. In reality, however, facial expression activity is dynamic, and its variability can be described as the onset, the apex and the offset [Xie et al., 2014]. Many experiments, including those conducted in psychology [Ambadar et al., 2005], have demonstrated that the utilization of the temporal information located in facial expression activity enhances recognition performance. Temporal information is thus an essential component of a successful FER system, and video-based FER has attracted particular attention [Zhao and Pietikainen, 2007; Xie et al., 2014].

Numerous methods for video-based FER have been proposed, but they are all limited in that only a single type of feature is utilized. This may lead to unsatisfactory recognition results because the facial expression information in videos is very complex. Combining the different kinds of features has significant potential to improve the performance of videobased FER since each feature characterizes a different view. For example, spatio-temporal features based on the scale invariant feature transform (SIFT) [Gu et al., 2012] and histograms of oriented gradients (HOG) [Klaser et al., 2008] descriptors effectively characterize the respective shape and appearance of an expression, while the features based on the motion boundary histograms (MBH) [Wang et al., 2013a] descriptor are especially good at capturing the motion information, and the widely used texture feature LBP-TOP [Zhao and Pietikainen, 2007] is particularly insensitive to monotonic gray-scale changes. In this paper, we treat each feature representation as a particular view for charactering facial expression in videos.

It has been demonstrated empirically in [Wang et al., 2013a] that combining multiple features tends to achieve better recognition accuracy in action recognition, simply as a result of concatenating different features. However, the simple concatenation strategy is not physically meaningful because each view has a specific statistical property, and it often leads to over-fitting due to the high dimensionality [Luo et al., 2016; Tao et al., 2009] of the spatio-temporal features. For example, the dimensionality of the LBP-TOP features is about 3000 if 4 ⇥ 4 blocks are adopted for each frame, and the codebook size of the bag-of-features representations for HOG, HOF and MBH can also be several thousands. To properly combine the different views and also reduce feature dimensionality, we develop a novel multi-view dimension reduction (MVDR) algorithm, which aims to find a low dimensional representation for heterogeneous high dimensional data. MVDR can be performed in a supervised, semi-supervised, or unsupervised manner; most of the current works are unsupervised due to the high labeling cost in many real-world applications. We also focus on the unsupervised setting in this paper.

Inspired by the recently proposed exclusive feature selection [Kong et al., 2014], we first propose a novel sparse framework for unsupervised dimensionality reduction (UDR) termed exclusive UDR (EUDR), which learns a low-dimensional and sufficiently informative pattern for the original feature [Tao et al., 2007]. The exclusive group LASSO [Kong et al., 2014] (EG-LASSO) is employed as a regularization term on the corresponding projection matrix. The main advantage of EUDR is that it allows arbitrary group structures being exploited on the feature space. To also deal with the multi-view features in video-based FER, we extend EUDR to multi-view exclusive UDR (MEUDR), which simultaneously combines multi-view features and reduces the dimensionality. In MEUDR, the structure sparsity brought by the EG-LASSO regularization is achieved at both intra- and inter-view levels. Therefore, the complementary nature of different views tends to be better exploited than it is in existing multi-view unsupervised dimensionality reduction (MUDR) methods. In addition, combination weights are learned for each view to allow various views to contribute differently to the final representation. Thus the model is robust to noisy views and complementarity exploration can be further enhanced.

To validate the effectiveness of the proposed MEUDR for FER, we conduct experiments on two challenging videobased FER datasets. The superiority of our method is obvious by comparing it with several competitive baselines and recently proposed MUDR approaches.

2 MEUDR: Multi-view Exclusive Unsupervised Dimension Reduction

Notations: For a matrix X, we use X(i↪:) and X(:↪j) to signify its i-th row and j-th column vector respectively. Xij denotes the (i↪ j)-element of matrix X. Ir denotes an r ⇥ r identity matrix, kPkF is the Frobenius norm of matrix P, kpk1 denotes the l1-norm of vector p, and BT is the transpose of B.

2.1 Problem formulation

Suppose we are given the original feature matrix X 2 Rn⇥d , where n is the total number of samples, d is the dimensionality of high-dimensional data points. A basic formulation for UDR is to minimize the reconstruction errors of the original data represented by the matrix X, i.e.,

where P = [p1↪ p2↪ ▷▷▷↪ pr] 2 Rd⇥r is the projection matrix that maps the original high-dimensional data to a lowdimensional subspace, and B 2 Rn⇥r ↪ r < d is the lowdimensional representation in the subspace. Although this formulation efficiently finds a low-dimensional representation, all input variables are encouraged to contribute to each dimension of the final representation. To remove junk dimensions and discern important ones, we propose to adaptively select variables for constructing each projection vector pi 2 Rd . This leads to the following general formulation of the sparse unsupervised dimension reduction (SUDR):

where ⌦ is any convex sparse-promoting penalty. In this paper, we adopt the recently proposed exclusive group LASSO (EG-LASSO) [Kong et al., 2014] as the regularizer for pi. EG-LASSO first adopts a general "group" setting to obtain arbitrary group structure of pi, following which l1◁l2 norm penalty is used to achieve sparsity. In this way, this regularizer brings out sparsity with arbitrary structure on feature space. Therefore we obtain the following exclusive UDR (EUDR) problem:

where ⌦GEg (pi) = Pg2G kpi↪Gg k21 is the EG-LASSO term, and G is the group set. However, this framework is limited in that only problem of UDR with single view data is available. To deal with the multi-view features in video-based FER, we extend it to multi-view dimensionality reduction (MVDR) by mapping the features of different views X(v) into a common subspace. Therefore we have the following multi-view exclusive unsupervised dimension reduction (MEUDR) formulation:

where ✓ = [✓1↪ ✓2↪ ▷▷▷↪ ✓V ] is a vector of view combination coefficients [Nie et al., 2014] to explore the complementary information of different views, and also prevent the model from being contaminated by noisy views. To further exploit the feature relationships between different views, we reformulate Eq.(4) as:

Here, pcat i = [p(1) i ; p(2) i ; ▷▷▷; p(V ) i ] is a concatenation of projection vectors, and the group set G consists of two parts: we first regard the features in the same view as in a group to bring sparsity at intra-view level; then we put the highly correlated features of different views in a group to bring sparsity at interview level, where the feature correlation matrix is calculated as R = (Rij) 2 Rn⇥n , and Rij denotes the correlations between i-th and j-th features, i.e., Rij = ♣ Pt XitXjt♣ pPt X2 itpPt X2 jt . Benefiting from this two-part group setting, both the feature relationships within each view and the complementary nature between different views are well exploited.

2.2 Optimization

The global solution to the optimization problem in Eq.(5) is difficult to achieve since it is not joint convex with respect to the set of variables (B↪ ¶P (v) ♦↪ ✓). We therefore present an alternative iterative algorithm to solve the problem by converting the original problem into three sub-problems, in which only one variable is updated. First, we reformulate Eq.(5) as follows:

where ˆX = [p✓1X(1) ↪ ▷▷▷↪ p✓VX(V ) ] 2 Rn⇥d is the concatenated feature matrix with the dimension d = PVv=1 dv, P = [P (1) ; ▷▷▷; P (V ) ] 2 Rd⇥r is the concatenated mapping matrices, and ⇥d 2 Rd⇥d is a block diagonal matrix in which the v-th block is a diagonal matrix p✓vIv. Then we update B, P and ✓ alternatively until the termination criterion is achieved.

When P and ✓ are fixed, the problem Eq.(6) becomes:

According to [Han et al., 2012], we first apply SVD to E = ˆX⇥Td P, i.e., E = USV , and then obtain the solution for B as B = UV .

Next, when B and ✓ are fixed, the problem Eq.(6) w.r.t. P is given as follows:

where bi = B(:↪i) is the i-th column of B. This problem can be solved by alternating for each pi until convergence. The above problem w.r.t. pi is given by:

where ˜X = ˆX - (Pk6=i bkpTk )⇥d. It is easy to verify that the optimal solution of Eq.(9) is exactly the solution of the following problem:

where Di is a diagonal matrix with the entry Dijj = (Pg (IGg )j kpcat i↪Gg k1 ♣pji♣ ), where IGg 2 ¶0↪ 1♦d⇥1 is a vector of the group index indicator, and ♣pji♣ is replaced by qp2ji + ✏ when pji = 0 [Kong et al., 2014]. Taking the derivative of the objective with respect to pi and setting it to zero, we have:

Then we obtain:

Note that Di is dependent on P, and thus is also an unknown variable. Fortunately, we can prove that the solution for pi can be obtained by repeating the following two steps until convergence:

• ÷ Calculate the diagonal matrix Di⌧+1 using p⌧i ;

This iteration can also be incorporated into the alternation of different pi↪ i = 1↪ ▷▷▷↪ r▷

Lastly, for fixed P and B, we can rewrite the original problem Eq.(6) as:

where q = 1n [q1↪ ▷▷▷↪ qV ]T with each qv = kX(v) - B(P (v) )T k2F . We adopt the coordinate descent algorithm [Huang et al., 2015] to solve Eq.(13). Therefore, in each iteration of the descent procedure, only two elements ✓i and ✓j are selected to be updated; the others are fixed. By using the Lagrangian of Eq.(13) and considering the sum to one constraint, we obtain the following updating rule:

The obtained ✓⇤ i or ✓⇤ j may violate the constraint ✓i ≥ 0. Thus we set ✓⇤ i = 0 if ⌘(✓i +✓j)+(qj -qi) < 0, and similarly for ✓⇤ j .

We summarize the main procedure of the optimization in Algorithm 1. The stopping criterion for terminating the algorithm is the difference of the objective value between two consecutive steps. That is, if ♣Ot+1 -Ot♣◁♣Ot♣ < ✏, then the iteration stops, where Ot is the objective value at the i-th iteration step. Since the sub-problems of Eq. (7), (8) and (13) are convex w.r.t. B, P, and ✓ respectively, the algorithm is guaranteed to converge according to the following analysis.

2.3 Convergence analysis

In this section, we discuss the convergence of the proposed MEUDR algorithm. Let the initialized value of the objective Eq.(6) be F(Bt ↪ P t ↪ ✓t ). Since Eq.(7) is convex and Algorithm 1 The efficient iterative algorithm for solving Eq.(6)

• Input: A matrix of the concatenated features X = [X(1) ↪ ▷▷▷↪ X(V ) ] 2 Rn⇥d .
• 1: Set t = 0. Initialize P 0 as random matrix, and ✓0 v = 1 V ↪ v = 1↪ ▷▷▷↪ V .
• Output: A low-dimensional consensus pattern matrix B 2 Rn⇥r , and a set of mapping matrices P = [P (1) ; ▷▷▷; P (V ) ] 2 Rd⇥r .

While not converge do

• 2: Calculate Bt+1 = UV , where U and V are obtained by SVD on E = ˆX(⇥td )T P t .
• 3: Set ⌧ = 0.
• 4: Repeat
• 5: For i = 1↪ ▷▷▷r
• 6: Calculate the diagonal matrix Di⌧+1 based on bt+1 i and pti↪⌧ ;
• 7: Update pti↪⌧+1 = 1n ( 1n ((bt+1 i )T bt+1 i )(⇥td (⇥td )T ) + γDi⌧+1 )-1⇥td ˜XT bt+1 i .
• 8: End for
• 9: ⌧ = ⌧ +1.
• 10: Until converge
• 11: Update P t+1 = [pt1↪⌧+1 ↪ ▷▷▷↪ ptr↪⌧+1 ].
• 12: Calculate ✓t+1 by using the update rule Eq.(14).
• 13: t = t +1.

End while

can be solved analytically, we have F(Bt+1 ↪ P t ↪ ✓t )  F(Bt ↪ P t ↪ ✓t ). The problem in Eq. (8) is solved alternatively for each pi with all the other pk↪ k 6= i fixed. Let F(pti ) and G(pti ) be the objectives of Eq.(9) and (10) respectively at the t-th alternating step. Similar to [Kong et al., 2014], we can prove that by using the updating rules for calculating pi, the following inequalities hold:

Therefore, we have F (pti↪⌧+1 )  F (pti↪⌧ ). This indicates that F(pti↪⌧+1 ↪ ¶ptk↪⌧ ♦k6=i)  F(¶pti↪⌧ ♦ri=1 ) = F(P t ). Because F (P t+1 ) = F (¶pti↪⌧+1 ♦ri=1 ), we have F (Bt+1 ↪ P t+1 ↪ ✓t )  F(Bt+1 ↪ P t ↪ ✓t ). Lastly, because Eq.(13) is a convex problem, we have F(Bt+1 ↪ P t+1 ↪ ✓t+1 )  F(Bt+1 ↪ P t+1 ↪ ✓t ). This completes the proof.

2.4 Induction for out-of-sample data

In this section, we extend MEUDR to the out-of-sample data. We use x = [x(1) ↪ ▷▷▷↪ x(V ) ] 2 Rd to signify the new multiview data point. And we expect to find its low-dimensional representation b 2 Rr . Since the mapping matrices P and view combination coefficients ✓ = [✓1↪ ✓2↪ ▷▷▷↪ ✓V ] have been derived based on the ever-known data, they can be used directly for the following solution. Based on the same strategy, which we have used in MEUDR, we expect b to be the solution to the following problem:

where ˆx = [p✓1x(1) ↪ ▷▷▷↪ p✓V x(V ) ]. After applying SVD to E = ˆx⇥Td P , i.e., E = USV , we obtain the solution for b as b = UV .

It can be seen from the above analysis that the consensus representation for an out-of-sample data can be obtained easily.

2.5 Related work

Multi-view learning [Wang et al., 2013b; Luo et al., 2015; Xu et al., 2015; Cai et al., 2014] has received much attention recently. The multiple views we refer to here are the multiple distinct feature sets used to describe a given sample, which are different from the multiple viewpoints in the traditional multi-view FER [Moore and Bowden, 2011]. We can roughly group the multi-view learning algorithms into categories according to their learning mechanisms, such as weighted view combination [McFee and Lanckriet, 2011], multi-view dimension reduction (MVDR) [Han et al., 2012], and so on. In MVDR, irrelevant or redundant information in the multiview data can be removed by leveraging the dependency, coherence, and complementarity of the different views.

Canonical Correlation Analysis (CCA) [Luo et al., 2015] is one of the most representative unsupervised MVDR (UMDR) methods, but it is limited in that only data from two views can be handled. Distributed spectral embedding (DSE) [Long et al., 2008] is a general UMDR approach for handling data from an arbitrary number of views. Although simple and efficient, the complementary nature of different views, which is critical in multi-view learning, is not well explored in DSE [Han et al., 2012]. To address this issue, structured sparsity based UMDR (SSMVD) is proposed in [Han et al., 2012], which is the most similar work to our method. SSMVD imposes a structured sparsity-inducing norm on the projection matrix which maps different patterns to the common low-dimensional space, and thus allows flexible information sharing in certain subsets of patterns across multiple views. In spite of this advantage, SSMVD still has several drawbacks: 1) the dimensions of the patterns of different views in SSMVD must be the same to construct a 2-D grid, thus a limited (certain and specified) number of relationships (e.g., rectangular groups) between the feature spaces of multiple views can be exploited; 2) the orthogonality constraint on the final common representation is replaced by a bound constraint in SSMVD for the convenience of optimization. The explainable efficiency of the factors in the final common subspace is not strong enough, and redundancy among the factors is inevitable; 3) only the information shared across different views is considered, and the sparsity structure in each view is ignored. Additionally, most of the existing UMDR methods (including CCA, DSE, and SSMVD) only consider the relationships at the inter-view level and ignore those at the intra-view level. All these problems are specifically tackled in the proposed MEUDR method.

3 Experiments

In this section, we validate the effectiveness of the proposed MEUDR method on two challenging FE video datasets. Prior to the evaluations, we present the datasets and features used, as well as our experimental settings.

3.1 Datasets

The first dataset is the facial expression (FE) dataset proposed in [Doll´ar et al., 2005], which we call "FE05" in this paper. The FE05 dataset involves two individuals, each of whom expresses six different emotions under two lighting setups. In our experiments, we choose two subsets that belong to two different identities and have different lighting setups, making the resultant dataset sufficiently challenging. To observe the performance of the compared algorithms with respect to different numbers of labeled samples, we randomly select 0▷25, 0▷5, 0▷75, 1▷0 percent of samples (2, 4, 6, 8 out of 8 samples) for each expression as the labeled samples from the training set, and the remaining samples are regarded as unlabeled.

The second FE dataset is the Oulu-CASIA VIS (CASIA for short) database [Li et al., 2013]. The CASIA dataset contains 80 subjects. We randomly separate these subjects into two groups: 70 subjects with six expressions (420 samples) for training, 10 subjects (60 samples) for testing. A further 20, 30, 50, 70 subjects are randomly chosen as labeled samples from the training set.

The five-fold cross-validation strategy is adopted for both datasets for tuning the parameters. Both support vector machine (SVM) [Tao et al., 2006; Liu and Tao, 2015] and kNN classifiers are tested for recognition, and ultimately we choose kNN for FE05 and SVM for CASIA according to classification accuracy.

3.2 Feature extraction

In our experiment, four different types of visual features have been extracted: Local Binary Pattern on Three Orthogonal Planes (LBP-TOP), and three descriptors HOG, HOF, and MBH combined with dense trajectories. The dimensionality of the features is 2832, 2000, 2000 and 2000, respectively.

LBP-TOP [Zhao and Pietikainen, 2007] is one of the most widely used features in texture analysis of image sequences. It is insensitive not only to translation and rotation, but also to monotonic gray-scale changes. Dense trajectories [Wang et al., 2013a] is a state-of-art approach that computes local descriptors for action recognition, and we apply it to FER. We adopt three types of descriptor to describe the video: HOG, HOF, and MBH. HOG (histograms of oriented gradients) captures static appearance information by using the orientation and magnitude of gradient; HOF (histograms of optical flow) focuses on the motion information by using the orientation and magnitude of the flow field; MBH (motion binary histograms) encodes the gradient of horizontal and vertical components of the flow to capture the relative pixel motion. Therefore, the different features are complementary to one another.

3.3 Comparison methods

We compare our method with BSV, CAT, PCA, DSE, and SSMVD. The first three are different baseline methods, and the experimental setup of the compared approaches is given as follows:

• ÷ BSV: the best single viewmethod, i.e., performing FER by regarding each single view as the feature representation, the results of the view that achieves the best performance are reported;
• ÷ CAT: concatenating the normalized features of all different views, and then performing FER on the concatenated features;
• ÷ dPCA: the distributed PCA method, i.e., reducing the dimensionality of each view to a pre-defined value (such as 100 for both datasets in this paper) by PCA, and then concatenating all the different views as a long vector for FER.
• ÷ DSE: the distributed spectral embedding [Long et al., 2008] method for UMDR. PCA is adopted for finding the patterns A(v) ↪ v = 1↪ ▷▷▷↪ V , and the reduced dimensionality is 100.
• ÷ SSMVD: the structured sparsity-based UMDR approach proposed in [Han et al., 2012]. Similar to DSE, PCA is adopted to find the patterns, the dimensionality of each of which is set to be the same (e.g., 100) so that a 2D grid can be constructed. The trade-off parameter γ is chosen from the set ¶10i ♣i = -5↪ -4↪ ▷▷▷↪ 3↪ 4♦.
• ÷ MEUDR: the proposed multi-view UDR method based on exclusive group sparsity. To reduce the time cost and also avoid over-fitting, since the number of training samples in both datasets is limited , we also apply PCA to the original features as in DSE and SSMVD. The candidate set for both trade-off parameters γ and ⌘ is ¶10i ♣i = -5↪ -4↪ ▷▷▷↪ 3↪ 4♦.

3.4 Experimental results

The performance of the compared methods in relation to the dimension of the final (consensus) representation on the FE05 and CASIA dataset is shown in Figure 1 and Figure 2 respectively. Accuracy is averaged over five runs for each dimension r in ¶1↪ 2↪ 5↪ 8↪ 10↪ 15↪ 20↪ 30↪ 50↪ 80↪ 100↪ 150↪ 200↪ 300♦. We summarize the performance of the various methods at their best dimensions in Table 1 and Table 2 respectively on the two datasets.

On the FE05 dataset, we observe that: 1) concatenating all features (CAT) is usually superior to using only a single view features (BSV) because more information is utilized by involving more features, although this is not true in all cases. For example, when the percentage of labeled samples is 0▷5, CAT is a bit worse than BSV. By first applying PCA on each view and then concatenating, we obtain better results than BSV. This indicates that the simple concatenation strategy may fail due to over-fitting; 2) all the UMDR methods (DSE, SSMVD, and MEUDR) can be significantly better than the baselines (BSV, CAT, and dPCA), if the dimensionalities are properly set according to cross-validation. For DSE, the performance curve stops early because the solution is obtained by the SVD of an n ⇥ n matrix, and the final dimension should be less than n; 3) the accuracy of the UMDR approaches increases sharply with an increasing dimension r and then decreases significantly. The performance often peaks around the dimension r = 8. This demonstrates the effectiveness of the first few factors found by UMDR; 4) the performance of SSMVD is better than that of DSE because complementary nature is better explored, and the proposed MEUDR outperforms all the other approaches at their best dimensions since we allow arbitrary information to be shared on and between the feature spaces of different views. Although the performance of SSMVD is higher than that of MEUDR when r is large, the curve line is quite unstable and has large oscillations.

It can be seen from the results on the CASIA dataset that: 1) the performance of the simple concatenation strategies (CAT and dPCA) are quite unstable and are worse than BSV in many cases; 2) the improvements of the proposed MEUDR compared to DSE and SSMVD are significant at many dimensions, not only the peak of the curve.

Overall, the recognition accuracy of 93▷75% on FE dataset and 88▷33% on the CASIA dataset are currently, to the best of our knowledge, state-of-the-art.

4 Conclusion

Multi-view learning has become an active research topic in recent years, but few works have addressed the issue of FER. In this paper, we proposed a new method termed MEUDR for the dimensionality reduction of multi-view data. The proposed MEUDR exploits arbitrary relationships on and between the feature spaces of different views. We allow the uneven contribution of different views to the final consensus representation by learning integration weights for them. This allows the complementary nature of different views to MEUDR 80.42◦1.8 90.42◦1.1 92.92◦1.1 93.8

Table 1: The average recognition rates and standard deviations (in %) of different approaches at their best dimensions on the FE05 dataset.

MEUDR 71.33◦0.7 76.33◦1.8 82.33◦2.2 88.3

be better exploited, hopefully achieving improved performance in FER. Two challenging video-based FER datasets were adopted to demonstrate the advantages of MEUDR. It is worth noting that the application of MEUDR is suitable for, but not limited to, FER. In any scenario that requires the dimensionality reduction of multi-view data, MEUDR is a suitable candidate.

Acknowledgments

This work is supported by the National Natural Science Foundation of China under Grant 61374006, Major Program of National Natural Science Foundation of China under Grant 11190015, the Scientific Research Foundation of Graduate School of Southeast University YBJJ1518, the Fundamental Research Funds for the Central Universities, the Program Sponsored for Scientific Innovation Research of College Graduates in Jiangsu Province under Grant KYLX15 0113, and Australian Research Council Projects DP-140102164, FT-130101457, LE140100061.