# Multiple Data-Dependent Kernel Fisher Discriminant Analysis for Face Recognition

Authors: Yue Liu; Yibing Li; Hong Xie; Dandan Liu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Kernel Fisher discriminant analysis (KFDA) method has demonstrated its success in extracting facial features for face recognition. Compared to linear techniques, it can better describe the complex and nonlinear variations of face images. However, a single kernel is not always suitable for the applications of face recognition which contain data from multiple, heterogeneous sources, such as face images under huge variations of pose, illumination, and facial expression. To improve the performance of KFDA in face recognition, a novel algorithm named multiple data-dependent kernel Fisher discriminant analysis (MDKFDA) is proposed in this paper. The constructed multiple data-dependent kernel (MDK) is a combination of several base kernels with a data-dependent kernel constraint on their weights. By solving the optimization equation based on Fisher criterion and maximizing the margin criterion, the parameter optimization of data-dependent kernel and multiple base kernels is achieved. Experimental results on the three face databases validate the effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

Face recognition has received extensive attention in many image processing applications. In these applications, the original face images commonly lie in a high-dimension space, resulting in low recognition accuracy and high cost. Existing image feature extraction algorithms can roughly fall into two categories: feature extraction based on signal processing and learning-based feature extraction [1–4]. By the utilization of learning-based approach, the original images can be mapped into a lower-dimensional feature space in which the essential structure of the original space becomes clear. To this end, Fisher discriminant analysis (FDA) [5], principal component analysis (PCA), and locality preserving projection (LPP) [6] are typical learning-based feature extraction techniques. Moreover, one of the most famous algorithms applied in face recognition is Fisher face, which is based on a two-phase framework: PCA plus LDA [3, 4]. It maximizes the between-class scatter and minimizes the within-class scatter to separate one class from the others. However, the entire above mentioned algorithms are linear subspaces analysis methods in essence, so they are inadequate to depict the complexity face images. To overcome the limitation, many nonlinear algorithms, such as kernel-based PCA (KPCA) [7] and FDA (KFDA) [8], have been devised and attained good performance in face recognition. It has been demonstrated that KFDA is a feasible nonlinear feature extraction algorithm for face recognition. However, the performance of KFDA is sensitive to the kernel function selection and its parameters. Moreover, the ability of single kernel is quite limited in depicting geometrical structure of some aspects for the input data. Once the face images are captured under huge variations of pose, illumination, facial expression, and so forth, single kernel-based FDA could not be suitable for the face recognition. In summary, kernel functions play an important part in face recognition applications [9, 10].As a consequence, various approaches have been developed to handle the above issues, and two main categories are identified as follows.(1) Devise multiple kernels by convex combination of multiple basic kernels. If so, different data descriptors can be used to depict the geometrical structures of original data from multiple views, which can complement to improve recognition performance [11–14]. (2) Develop data-dependent kernel (DK) by conformal transformation of the basic kernel. If so, the designed kernel would be adaptive to the input data, leading to a substantial improvement in the performance of KFDA algorithm [15–17].In this paper, to improve the performance of KFDA, we proposed a novel feature extraction algorithm for face recognition called multiple data-dependent kernel Fisher discriminant analysis (MDKFDA) based on the multiple kernel learning (MKL). The main contributions of this paper lie in the following.(1) By introducing MDK into KFDA, maximum discrimination performance can be achieved in feature space. (2) Multiple image features extracted in different descriptors are fully utilized in the MDKFDA algorithm. (3) Nonlinear discriminant features are produced by the adoption of MKL.The rest of this paper is organized as follows. Section2 shows a brief overview of MKL and KFDA. In Section 3, we illustrate the proposed MDKFDA algorithm and introduce the parameter optimization scheme for data-dependent kernel and multiple base kernels. Extensive experimental results on face recognition are reported in Section 4. Finally, Section 5 concludes this paper.


## 2. Related Work

In this section, we will briefly introduce some previous works related to this paper, including KFDA and MKL.


### 2.1. Kernel Fisher Discriminant Analysis

KFDA is a nonlinear feature extraction algorithm which combines the nonlinear kernel trick with FDA. Because of its ability to extract the discriminatory nonlinear features, KFDA and its variations are frequently used for face recognition. In this paper, a two-phased KFDA framework proposed by Yang et al. [18] is adopted to construct the MDKFDA. The two-phased KFDA framework mainly contains two parts: KPCA is applied to reduce the dimension of input space, and then LDA is used to further extract the features in the KPCA-transformed space.Given the input training sample set includingN samples:
(1)S={(xi,ci)∣xi∈Rd,ci∈{1,…,C}}i=1N,
where xi is the training sample of d-dimension and ci represents the class label of xi. Given a sample x, its nonlinear mapped image can be denoted as Φ(x), and the discriminate feature vector z can be obtained as follows:
(2)z=GTPTΦ(x).
Equation (2) contains two transformations P and G. The transformation P represents KPCA which transforms the input space Rd into feature space Rp, while the transformation G is the Fisher discriminant transformation in the KPCA-transformed space Rp.Firstly, the issues in the process of KPCA are described as follows.For a given nonlinear mappingΦ, the input space Rp can be projected into the feature space F, which is considered as Hilbert space. The covariance operator on the feature space F can be represented as
(3)H=1N∑i=1N(Φ(xi)-Φ-)(Φ(xi)-Φ-)T,
where Φ-=(1/N)∑i=1NΦ(xi). The way to find the nonzero eigenpair of H is illustrated as follows. Previously, to simplify the deduced process, the covariance operator is reformulated as
(4)H~=1N∑i=1NΦ(xi)Φ(xi)T.
Let us denote Q=[Φ(x1),…,Φ(xN)] and construct a N×N Gram matrix K~=QTQ, whose element K~ij can be calculated through the use of kernel tricks:
(5)K~ij=Φ(xi)TΦ(xj)=〈Φ(xi),Φ(xj)〉=k(xi,xj).
Centralize K~ by K=K~-1NK~-K~1N+1NK~1N, where 1N=(1/N)N×N.We adopt thet largest positive eigenvalues λ1≥λ2≥⋯≥λt of K and their corresponding orthonormal eigenvectors u1,u2,…,ut to calculate the eigenvectors w1,w2,…,wt of H~ as follows:
(6)wj=1λjQuj,j=1,2,…,t.
Hence, we can get the KPCA-transformed feature vector y=(y1,…,yt)T, and the ith KPCA feature is obtained by
(7)yj=wjTΦ(x)=1λjujTQTΦ(x)=1λjujT[k(x1,x),k(x2,x),…,k(xN,x)].
Above all, we can describe the P as follows:
(8)P=(w1,…,wt).
Secondly, the issues in the process of Fisher discriminant transformation are illustrated as follows.FDA is used for further feature extraction in the KPCA-transformed spaceRp. In order to maximize the Fisher criterion, we first define the between-class scatter operator SbΦ and the within-class scatter operator SwΦ in feature space F. Consider
(9)SbΦ=1N∑i=1cli(miΦ-m0Φ)(miΦ-m0Φ)T,(10)SwΦ=1N∑i=1c∑j=1li(Φ(xij)-miΦ)(Φ(xij)-miΦ)T,
where li is the number of training samples in class i, xij represents the jth samples in class i, miΦ is the mean of the mapped samples in class i, and m0Φ is the mean across all mapped samples. Thus, we can obtain the Fisher criterion by
(11)JΦ(V)=VTSbΦVVTSwΦV,
where V is the discriminant vector. According to Mercer kernel function theory, each V can be described by the elements of feature space {Φ(x1),Φ(x2),…,Φ(xN)}, and there always exist coefficients φi,i=1,2,…,N, such that
(12)V=∑i=1NφiΦ(xi)=ΨΧ,
where Ψ=[Φ(x1),Φ(x2),…,Φ(xN)], Χ=[φ1,…,φN]T. Hence, the Fisher optimal discriminant vectors are the stationary points V1,…,Vd,d≤N, and, correspondingly, the transformation G in (2) can be denoted by
(13)G=(V1,…,Vd).


### 2.2. Multiple Kernel Learning

In general, MKL refers to the process of learning a kernel machine which is the combination of multiple base kernel functions/matrices. Recent research efforts have shown that MKL is not only able to find an optimal combination weight of base kernels but also improve the performance of the resulting classifiers.As mentioned above,S is the d-dimensional training sample set. For a given nonlinear mapping Φ, the original data is projected into empirical feature space F:
(14)Φ:xi∈Rd⟶Φ(x)∈F.
Using Mercer’s theorem [19], the inner product of two transformed vectors Φ(x) in the nonlinear space can be expressed as
(15)k(xi,xj)=〈Φ(xi),Φ(xj)〉,
where the operator 〈·〉 means inner product. Such kernel function is usually called Mercer kernel, and some commonly used Mercer kernels are shown as follows [20]:
(16)linearkernel:k(x,y)=xTy,Gaussian  kernel:k(x,y)=exp⁡(-∥x-y∥2r2),polynomial  kernel:k(x,y)=(x·y+d)l.
Among them, Gaussian kernel is one of the most widespread kernels. However, Gaussian kernel can only reflect the local nonlinear feature of the data, while the linear kernel and polynomial kernel are overall kernel functions. It has been shown that the kernel-based feature extraction algorithm is appropriate for solving the nonlinear problems in face recognition. Nevertheless, the disadvantage of single kernel-based algorithms is lack of the generalization representation capability for multidimensional and multiclass data. Recent applications have indicated that MKL could provide us a more flexible framework to fuse information from different data source and enhance the performance of classifiers [21–26].In the MKL framework, givenM basic kernel functions {km}m=1M, the multiple kernel function can be generally represented as [27]
(17)Kmultiple(xi,xj)=∑m=1Mθmkm(xi,xj),s.t.θm≥0,∑m=1Mθm=1,
where the weighted coefficient θm is commonly obtained by solving the optimal object function of the kernel subspace learning algorithm. It is noticed that optimizing the coefficient θm is a critical problem for improving the performance of MKL.


## 2.1. Kernel Fisher Discriminant Analysis

KFDA is a nonlinear feature extraction algorithm which combines the nonlinear kernel trick with FDA. Because of its ability to extract the discriminatory nonlinear features, KFDA and its variations are frequently used for face recognition. In this paper, a two-phased KFDA framework proposed by Yang et al. [18] is adopted to construct the MDKFDA. The two-phased KFDA framework mainly contains two parts: KPCA is applied to reduce the dimension of input space, and then LDA is used to further extract the features in the KPCA-transformed space.Given the input training sample set includingN samples:
(1)S={(xi,ci)∣xi∈Rd,ci∈{1,…,C}}i=1N,
where xi is the training sample of d-dimension and ci represents the class label of xi. Given a sample x, its nonlinear mapped image can be denoted as Φ(x), and the discriminate feature vector z can be obtained as follows:
(2)z=GTPTΦ(x).
Equation (2) contains two transformations P and G. The transformation P represents KPCA which transforms the input space Rd into feature space Rp, while the transformation G is the Fisher discriminant transformation in the KPCA-transformed space Rp.Firstly, the issues in the process of KPCA are described as follows.For a given nonlinear mappingΦ, the input space Rp can be projected into the feature space F, which is considered as Hilbert space. The covariance operator on the feature space F can be represented as
(3)H=1N∑i=1N(Φ(xi)-Φ-)(Φ(xi)-Φ-)T,
where Φ-=(1/N)∑i=1NΦ(xi). The way to find the nonzero eigenpair of H is illustrated as follows. Previously, to simplify the deduced process, the covariance operator is reformulated as
(4)H~=1N∑i=1NΦ(xi)Φ(xi)T.
Let us denote Q=[Φ(x1),…,Φ(xN)] and construct a N×N Gram matrix K~=QTQ, whose element K~ij can be calculated through the use of kernel tricks:
(5)K~ij=Φ(xi)TΦ(xj)=〈Φ(xi),Φ(xj)〉=k(xi,xj).
Centralize K~ by K=K~-1NK~-K~1N+1NK~1N, where 1N=(1/N)N×N.We adopt thet largest positive eigenvalues λ1≥λ2≥⋯≥λt of K and their corresponding orthonormal eigenvectors u1,u2,…,ut to calculate the eigenvectors w1,w2,…,wt of H~ as follows:
(6)wj=1λjQuj,j=1,2,…,t.
Hence, we can get the KPCA-transformed feature vector y=(y1,…,yt)T, and the ith KPCA feature is obtained by
(7)yj=wjTΦ(x)=1λjujTQTΦ(x)=1λjujT[k(x1,x),k(x2,x),…,k(xN,x)].
Above all, we can describe the P as follows:
(8)P=(w1,…,wt).
Secondly, the issues in the process of Fisher discriminant transformation are illustrated as follows.FDA is used for further feature extraction in the KPCA-transformed spaceRp. In order to maximize the Fisher criterion, we first define the between-class scatter operator SbΦ and the within-class scatter operator SwΦ in feature space F. Consider
(9)SbΦ=1N∑i=1cli(miΦ-m0Φ)(miΦ-m0Φ)T,(10)SwΦ=1N∑i=1c∑j=1li(Φ(xij)-miΦ)(Φ(xij)-miΦ)T,
where li is the number of training samples in class i, xij represents the jth samples in class i, miΦ is the mean of the mapped samples in class i, and m0Φ is the mean across all mapped samples. Thus, we can obtain the Fisher criterion by
(11)JΦ(V)=VTSbΦVVTSwΦV,
where V is the discriminant vector. According to Mercer kernel function theory, each V can be described by the elements of feature space {Φ(x1),Φ(x2),…,Φ(xN)}, and there always exist coefficients φi,i=1,2,…,N, such that
(12)V=∑i=1NφiΦ(xi)=ΨΧ,
where Ψ=[Φ(x1),Φ(x2),…,Φ(xN)], Χ=[φ1,…,φN]T. Hence, the Fisher optimal discriminant vectors are the stationary points V1,…,Vd,d≤N, and, correspondingly, the transformation G in (2) can be denoted by
(13)G=(V1,…,Vd).


## 2.2. Multiple Kernel Learning

In general, MKL refers to the process of learning a kernel machine which is the combination of multiple base kernel functions/matrices. Recent research efforts have shown that MKL is not only able to find an optimal combination weight of base kernels but also improve the performance of the resulting classifiers.As mentioned above,S is the d-dimensional training sample set. For a given nonlinear mapping Φ, the original data is projected into empirical feature space F:
(14)Φ:xi∈Rd⟶Φ(x)∈F.
Using Mercer’s theorem [19], the inner product of two transformed vectors Φ(x) in the nonlinear space can be expressed as
(15)k(xi,xj)=〈Φ(xi),Φ(xj)〉,
where the operator 〈·〉 means inner product. Such kernel function is usually called Mercer kernel, and some commonly used Mercer kernels are shown as follows [20]:
(16)linearkernel:k(x,y)=xTy,Gaussian  kernel:k(x,y)=exp⁡(-∥x-y∥2r2),polynomial  kernel:k(x,y)=(x·y+d)l.
Among them, Gaussian kernel is one of the most widespread kernels. However, Gaussian kernel can only reflect the local nonlinear feature of the data, while the linear kernel and polynomial kernel are overall kernel functions. It has been shown that the kernel-based feature extraction algorithm is appropriate for solving the nonlinear problems in face recognition. Nevertheless, the disadvantage of single kernel-based algorithms is lack of the generalization representation capability for multidimensional and multiclass data. Recent applications have indicated that MKL could provide us a more flexible framework to fuse information from different data source and enhance the performance of classifiers [21–26].In the MKL framework, givenM basic kernel functions {km}m=1M, the multiple kernel function can be generally represented as [27]
(17)Kmultiple(xi,xj)=∑m=1Mθmkm(xi,xj),s.t.θm≥0,∑m=1Mθm=1,
where the weighted coefficient θm is commonly obtained by solving the optimal object function of the kernel subspace learning algorithm. It is noticed that optimizing the coefficient θm is a critical problem for improving the performance of MKL.


## 3. The Proposed Multiple Data-Dependent Kernel (MDK)

As mentioned above, given a training dataS, the elements of MDK can be formulated as
(18)KMDDK(x,x′)=q(x)q(x′)∑i=1Iγiki′(x,x′),
where x,x′∈Rd, ki′(x,x′) is the ith basic kernel chosen from the commonly used ones such as Gaussian kernel or polynomial kernel, I is the number of candidate basic kernel, γi is the weight for the ith basic kernel, and q(·) is the factor function called data-dependent kernel (DK) which takes the form of
(19)q(x)=α0+∑i=1mαikGaussian(x,xec),
where αi,i=0,1,…,m is the combination coefficient. The set {xec∈Rd}, called the “empirical cores,” are chosen from the training data. It is notable that MDK also satisfies the Mercer condition, since KMDDK(x,x′) is equal to multiply DK and basic kernels together, which is the linear combination of kernels.As mentioned above, we can see that the main problems in MDK are to choose the optimal weightγi for basic kernels ki′(x,x′) and the coefficients αi of data-dependent kernel q(x). In this paper, we adopt the iterative method based on the maximum margin criterion (MMC) and Fisher scalar to optimize weight γi and coefficient αi, respectively. The schematic of MDK is shown in Figure 1.Figure 1
Schematic of the proposed MDK.


### 3.1. Weight Optimization for Multiple Kernels

To gain good performance of MDKFDA for face recognition, learning proper weights of candidate base kernels is illustrated in this section. In KFDA, we measure the class separability in kernel feature space and the kernel Fisher criterion can be expressed as(20)JΦ(V)=tr⁡(VTSbΦV)tr⁡(VTSwΦV).
In this section, the diagonalization strategy [28] is adopted to find the optimal Vopt, based on which, the maximum margin criterion (MMC) [29] is employed as the objective function to optimize weight γi,i=1,2,…,I. Consider
(21)L(γ)=tr⁡(VoptTSbΦVopt)-tr⁡(VoptTSwΦVopt).
To maximize L(γ), we introduce a Lagrangian to solve the optimization problem as follows:
(22)L(γ,α)=F(γ)+α(∑i=1Iγi-1).
A series of partial derivatives can be achieved through differentiating L(γ,α) with respect to γ1,γ2,…,γI and α. By setting these derivatives to zero, we can use Newton’s iteration method to solve these equations, and the optimized weights for multiple kernels are achieved as follows:
(23)γ~=(γ1,γ2,…,γI,α)T.


### 3.2. Coefficients Optimization for Data-Dependent Kernel

Since the optimized weights for multiple kernels have been achieved, investigating proper coefficients of DK is described in this section. In empirical feature space, letJ=tr⁡(SbΦ)/tr⁡(SwΦ) denote the Fisher scalar, and SbΦ and SwΦ have been defined in (9) and (10), respectively. Given training dataset S, K=[k(xi,xj)]N×N is the kernel matrix for all samples, whose element can be described as kij=k(xi,xj),(i,j=1,2,…,N), and Kpq(p,q=1,2,…,C) is the np×nq submatrices of the K. Hence, K can be written as
(24)K=(K11K12⋯K1CK21K22⋯K2C⋮⋮⋯⋮KC1KC2⋯KCC).
Consequentially, the between-class scatter matrix B and within-class scatter matrix W can be expressed as follows:
(25)B=[1l1K110⋯001l2K22⋯0⋮⋮⋱⋮00⋯1lCKCC]-[1NK111NK12⋯1NK1c1NK211NK22⋯1NK2C⋮⋮⋯⋮1NKC11NKC2⋯1NKCC],W=[k110⋯00k22⋯0⋮⋮⋱⋮00⋯kNN]-[1l1K110⋯001l2K22⋯0⋮⋮⋯⋮00⋯1lCKCC].
For the multiple kernel Kmultiple(xi,xj)=∑m=1Mθmkm(xi,xj), B and W can be replaced by the B0 and the W0, respectively, and their corresponding kernel matrix is translated into K=QKmultipleQ, in which Q=diag⁡(q(x1),q(x2),…,q(xN)) and q(x) have been defined in (19), and then we have
(26)q=[1k1(x1,a1)⋯k1(x1,am)1k1(x2,a1)⋯k1(x2,am)⋮⋮⋱⋮1k1(xN,a1)⋯k1(xN,am)][α0α1⋮αm]≜K1α.Theorem 1.
Let1k be the k-dimensional vector with unity elements; the Fisher scalar J is equivalent to
(27)J=1NTB1N1NTW1N=qTB0qqTW0q.Proof.
As shown in Section2.1, the dimension of empirical feature space is set as p(p<N). Then, H and Hi,    i=1,…,C, are, respectively, defined as the N×p and li×p, i=1,…,C matrices whose rows are the vectors {hjT}, j=1,2,…,N and {hjT}, j=1,2,…,li. The m0Φ and miΦ in Section 2.1 can be expressed as follows:
(28)m0Φ=1N∑j=1Nhj=1NHTIN,miΦ=1li∑j=li-1+1l1+⋯+lihj=1liHiTIli,i=1,…,C.
Moreover, since the empirical feature space maintains the dot product, (24) is equivalent to
(29)K=HHT=[H1H2⋯HC][H1TH2T⋮HCT],
where Kij=HiHjT,i,j=1,2,…,C. As such, tr⁡(SbΦ) and tr⁡(SwΦ) can be described as
(30)tr⁡(SbΦ)=1N∑i=1Cli(miΦ-m0Φ)T(miΦ-m0Φ)=1N∑i=1ClimiΦTmiΦ-m0ΦTm0Φ=1N∑i=1C1liIliTHiHiTIli-1N2INTHHTIN=1N∑i=1C1liIliTKiiIli-1N2INTKIN=1N[Il1TIl2T⋯IlcT]×[1l1K110⋯001l2K22⋯0⋮⋮⋯⋮00⋯1lcKcc][Il1TIl2T⋮IlcT]-1NINT[1NK111NK12⋯1NK1c1NK211NK22⋯1NK2c⋮⋮⋯⋮1NKc11NKc2⋯1NKcc]=1NINTBIN,tr⁡(SwΦ)=1N∑i=1C∑j=1li(Φ(xji)-miΦ)T(Φ(xji)-miΦ)=1N∑i=1C(∑j=1li(Φ(xji)TΦ(xji))-li(miΦ)TmiΦ)=1N(∑j=1NΦ(xj)TΦ(xj)-∑i=1C1liIliTHiHiTIli)=1N([1l1K110⋯001l2K22⋯0⋮⋮⋯⋮00⋯1lcKcc]∑j=1Nkjj-[Il1TIl2T⋯IlcT]×[1l1K110⋯001l2K22⋯0⋮⋮⋯⋮00⋯1lcKcc][Il1TIl2T⋮IlcT])=1NINTWIN.
From the above description, it is remarkable that B=QB0Q and W=QW0Q, where QIN=q. Finally, the relationship is proved:
(31)J=tr⁡(SbΦ)tr⁡(SwΦ)=1NTΒ1N1NTW1N=qTB0qqTW0q.
In order to obtain the optimal coefficients, J should be maximized. Since q=K1α, J can be reformulated as
(32)J(α)=αTK1TB0K1ααTK1TW0K1α,
where M0=K1TB0K1 and N0=K1TW0K1. To maximize J(α), the standard gradient approach is adopted. Given that
(33)J1(α)=αTK1TB0K1α,J2(α)=αTK1TW0K1α,
respectively, the partial differential of J1(α) and J2(α) with respect to α are
(34)∂J1(α)∂α=2K1TB0K1α,∂J2(α)∂α=2K1TW0K1α,
and the partial differential of J(α) is
(35)∂J(α)∂α=2J22(J2K1TB0K1-J1K1TW0K1)α.
Let ∂J(α)/∂α=0; it is obtained that
(36)J1K1TW0K1α=J2K1TB0K1α,Jα=(K1TW0K1)-1(K1TB0K1)α,K1TW0K1≠0.
Hence, J is equal to the largest eigenvalue of the matrix (K1TW0K1)-1(K1TB0K1), and the optimal α is the eigenvector corresponding to the largest eigenvalue; thus, an iteration algorithm is employed to calculate the optimal α:
(37)α(m+1)=α(m)+ε(1J2K1TB0K1-JJ2K1TW0K1)α(m),
where ε is the learning rate, and it is given by
(38)ε(t)=ε0(1-tN),
where ε0 is the initial learning rate, t, and N denotes the current iteration number and prespecified iteration number, respectively. In summary, the optimal coefficients can be obtained by choosing ε0 and N properly.


### 3.3. Complete MDKFDA Algorithm

In summary of the discussion so far, the steps of complete MDKFDA algorithm are described as follows.Step 1 (construct the MDK).
Gaussian kernel is adopted to construct the data-dependent kernel (DK), while the linear kernel, Gaussian kernel, and polynomial kernel are employed as the base kernels of multiple kernel function.Step 2 (optimize the weights).
The maximum margin criterion (MMC) is employed as the objective function to optimize weights for multiple kernels, and the optimized coefficients for DK are achieved by virtue of the Fisher scalar.Step 3 (transform the data).
The MDK is used to transform the input spaceRd into feature space Rp, by which the original input data {xi∣xi∈Rd}i=1N is converted into feature data {yi∣yi∈Rp}i=1T. The transformation is P=(w1,…,wt).Step 4 (extract the Fisher discriminant vectors).
S
b
Φ, SwΦ in Rp are calculated to get the Fisher criterion JΦ(V). By maximizing JΦ(V), the Fisher optimal discriminant vectors are achieved, and the Fisher discriminant transformation is G=(V1,…,Vd).Step 5 (obtain the MDKFDA feature vector).
Based on the first four steps, the expression of the MDKFDA feature vectorz=GTPTΦ(x) is obtained.


## 3.1. Weight Optimization for Multiple Kernels

To gain good performance of MDKFDA for face recognition, learning proper weights of candidate base kernels is illustrated in this section. In KFDA, we measure the class separability in kernel feature space and the kernel Fisher criterion can be expressed as(20)JΦ(V)=tr⁡(VTSbΦV)tr⁡(VTSwΦV).
In this section, the diagonalization strategy [28] is adopted to find the optimal Vopt, based on which, the maximum margin criterion (MMC) [29] is employed as the objective function to optimize weight γi,i=1,2,…,I. Consider
(21)L(γ)=tr⁡(VoptTSbΦVopt)-tr⁡(VoptTSwΦVopt).
To maximize L(γ), we introduce a Lagrangian to solve the optimization problem as follows:
(22)L(γ,α)=F(γ)+α(∑i=1Iγi-1).
A series of partial derivatives can be achieved through differentiating L(γ,α) with respect to γ1,γ2,…,γI and α. By setting these derivatives to zero, we can use Newton’s iteration method to solve these equations, and the optimized weights for multiple kernels are achieved as follows:
(23)γ~=(γ1,γ2,…,γI,α)T.


## 3.2. Coefficients Optimization for Data-Dependent Kernel

Since the optimized weights for multiple kernels have been achieved, investigating proper coefficients of DK is described in this section. In empirical feature space, letJ=tr⁡(SbΦ)/tr⁡(SwΦ) denote the Fisher scalar, and SbΦ and SwΦ have been defined in (9) and (10), respectively. Given training dataset S, K=[k(xi,xj)]N×N is the kernel matrix for all samples, whose element can be described as kij=k(xi,xj),(i,j=1,2,…,N), and Kpq(p,q=1,2,…,C) is the np×nq submatrices of the K. Hence, K can be written as
(24)K=(K11K12⋯K1CK21K22⋯K2C⋮⋮⋯⋮KC1KC2⋯KCC).
Consequentially, the between-class scatter matrix B and within-class scatter matrix W can be expressed as follows:
(25)B=[1l1K110⋯001l2K22⋯0⋮⋮⋱⋮00⋯1lCKCC]-[1NK111NK12⋯1NK1c1NK211NK22⋯1NK2C⋮⋮⋯⋮1NKC11NKC2⋯1NKCC],W=[k110⋯00k22⋯0⋮⋮⋱⋮00⋯kNN]-[1l1K110⋯001l2K22⋯0⋮⋮⋯⋮00⋯1lCKCC].
For the multiple kernel Kmultiple(xi,xj)=∑m=1Mθmkm(xi,xj), B and W can be replaced by the B0 and the W0, respectively, and their corresponding kernel matrix is translated into K=QKmultipleQ, in which Q=diag⁡(q(x1),q(x2),…,q(xN)) and q(x) have been defined in (19), and then we have
(26)q=[1k1(x1,a1)⋯k1(x1,am)1k1(x2,a1)⋯k1(x2,am)⋮⋮⋱⋮1k1(xN,a1)⋯k1(xN,am)][α0α1⋮αm]≜K1α.Theorem 1.
Let1k be the k-dimensional vector with unity elements; the Fisher scalar J is equivalent to
(27)J=1NTB1N1NTW1N=qTB0qqTW0q.Proof.
As shown in Section2.1, the dimension of empirical feature space is set as p(p<N). Then, H and Hi,    i=1,…,C, are, respectively, defined as the N×p and li×p, i=1,…,C matrices whose rows are the vectors {hjT}, j=1,2,…,N and {hjT}, j=1,2,…,li. The m0Φ and miΦ in Section 2.1 can be expressed as follows:
(28)m0Φ=1N∑j=1Nhj=1NHTIN,miΦ=1li∑j=li-1+1l1+⋯+lihj=1liHiTIli,i=1,…,C.
Moreover, since the empirical feature space maintains the dot product, (24) is equivalent to
(29)K=HHT=[H1H2⋯HC][H1TH2T⋮HCT],
where Kij=HiHjT,i,j=1,2,…,C. As such, tr⁡(SbΦ) and tr⁡(SwΦ) can be described as
(30)tr⁡(SbΦ)=1N∑i=1Cli(miΦ-m0Φ)T(miΦ-m0Φ)=1N∑i=1ClimiΦTmiΦ-m0ΦTm0Φ=1N∑i=1C1liIliTHiHiTIli-1N2INTHHTIN=1N∑i=1C1liIliTKiiIli-1N2INTKIN=1N[Il1TIl2T⋯IlcT]×[1l1K110⋯001l2K22⋯0⋮⋮⋯⋮00⋯1lcKcc][Il1TIl2T⋮IlcT]-1NINT[1NK111NK12⋯1NK1c1NK211NK22⋯1NK2c⋮⋮⋯⋮1NKc11NKc2⋯1NKcc]=1NINTBIN,tr⁡(SwΦ)=1N∑i=1C∑j=1li(Φ(xji)-miΦ)T(Φ(xji)-miΦ)=1N∑i=1C(∑j=1li(Φ(xji)TΦ(xji))-li(miΦ)TmiΦ)=1N(∑j=1NΦ(xj)TΦ(xj)-∑i=1C1liIliTHiHiTIli)=1N([1l1K110⋯001l2K22⋯0⋮⋮⋯⋮00⋯1lcKcc]∑j=1Nkjj-[Il1TIl2T⋯IlcT]×[1l1K110⋯001l2K22⋯0⋮⋮⋯⋮00⋯1lcKcc][Il1TIl2T⋮IlcT])=1NINTWIN.
From the above description, it is remarkable that B=QB0Q and W=QW0Q, where QIN=q. Finally, the relationship is proved:
(31)J=tr⁡(SbΦ)tr⁡(SwΦ)=1NTΒ1N1NTW1N=qTB0qqTW0q.
In order to obtain the optimal coefficients, J should be maximized. Since q=K1α, J can be reformulated as
(32)J(α)=αTK1TB0K1ααTK1TW0K1α,
where M0=K1TB0K1 and N0=K1TW0K1. To maximize J(α), the standard gradient approach is adopted. Given that
(33)J1(α)=αTK1TB0K1α,J2(α)=αTK1TW0K1α,
respectively, the partial differential of J1(α) and J2(α) with respect to α are
(34)∂J1(α)∂α=2K1TB0K1α,∂J2(α)∂α=2K1TW0K1α,
and the partial differential of J(α) is
(35)∂J(α)∂α=2J22(J2K1TB0K1-J1K1TW0K1)α.
Let ∂J(α)/∂α=0; it is obtained that
(36)J1K1TW0K1α=J2K1TB0K1α,Jα=(K1TW0K1)-1(K1TB0K1)α,K1TW0K1≠0.
Hence, J is equal to the largest eigenvalue of the matrix (K1TW0K1)-1(K1TB0K1), and the optimal α is the eigenvector corresponding to the largest eigenvalue; thus, an iteration algorithm is employed to calculate the optimal α:
(37)α(m+1)=α(m)+ε(1J2K1TB0K1-JJ2K1TW0K1)α(m),
where ε is the learning rate, and it is given by
(38)ε(t)=ε0(1-tN),
where ε0 is the initial learning rate, t, and N denotes the current iteration number and prespecified iteration number, respectively. In summary, the optimal coefficients can be obtained by choosing ε0 and N properly.


## 3.3. Complete MDKFDA Algorithm

In summary of the discussion so far, the steps of complete MDKFDA algorithm are described as follows.Step 1 (construct the MDK).
Gaussian kernel is adopted to construct the data-dependent kernel (DK), while the linear kernel, Gaussian kernel, and polynomial kernel are employed as the base kernels of multiple kernel function.Step 2 (optimize the weights).
The maximum margin criterion (MMC) is employed as the objective function to optimize weights for multiple kernels, and the optimized coefficients for DK are achieved by virtue of the Fisher scalar.Step 3 (transform the data).
The MDK is used to transform the input spaceRd into feature space Rp, by which the original input data {xi∣xi∈Rd}i=1N is converted into feature data {yi∣yi∈Rp}i=1T. The transformation is P=(w1,…,wt).Step 4 (extract the Fisher discriminant vectors).
S
b
Φ, SwΦ in Rp are calculated to get the Fisher criterion JΦ(V). By maximizing JΦ(V), the Fisher optimal discriminant vectors are achieved, and the Fisher discriminant transformation is G=(V1,…,Vd).Step 5 (obtain the MDKFDA feature vector).
Based on the first four steps, the expression of the MDKFDA feature vectorz=GTPTΦ(x) is obtained.


## 4. Experimental Results and Discussions

In this section, we conduct several experiments on three face databases to evaluate the performance of the proposed MDKFDA algorithm by comparing it with several widespread algorithms in face recognition, including PCA, LPP, FDA, KPCA, KFDA, and DKFDA. The ORL face database [30], YALE face database [31], and PIE face database [32] are adopted in the experiments, and partial sample images of one person from different databases are shown in Figures 2, 3, and 4. In the following experiments, we select randomly 5 images per individual as training set and the rest 5 for testing. To make the experiments more reasonable, we repeated the trails 10 times to achieve an average performance.Figure 2
Sample images of one person in the ORL database.Figure 3
Samples images of one person in the YALE database.Figure 4
Sample images of one person in the PIE database.


### 4.1. Face Recognition Using ORL Database

The ORL face database contains 400 face images of 40 individuals, and variations in these 400 face images include angle, lighting, expression, and face details. As shown in Figure2, the size of all the original images were shaped into 48*48 pixels, and the primary part of the original image was reserved. Three kernels are employed as the base kernels of multiple kernel function in MDK, including linear kernel, Gaussian kernel, and polynomial kernel. Moreover, Gaussian kernel is adopted to construct DK. Table 1 shows the comparison of maximal average recognition ratio between several nonkernel algorithms and the proposed MDKFDA algorithm. Table 2 reports the comparison of maximal average recognition ratio between several single kernel-based algorithms and the proposed MDKFDA. According to the experiment results, the MDKFDA algorithm outperforms the other algorithms, which implies that the MDKFDA can integrate multiple base kernels with data-dependent kernel (DK) effectively to improve the recognition ratio. Besides, it can be seen that all the single kernel-based feature extraction algorithms outperform their corresponding linear versions, which indicates that the kernel-based algorithm is advantageous for face recognition.Table 1
Comparison of recognition ratio between linear algorithms and MDKFDA.
Algorithm
PCA
LPP
LDA
MDKFDA
Recognition ratio (%)
82.0
75.5
74.3
95.8Table 2
Comparison of recognition ratio between single kernel-based algorithms and MDKFDA.
Algorithm
Gaussian kernel (%)
Polynomial kernel (%)
KPCA
86.5
84.5
KFDA
88.0
85.0
DKFDA
93.5
92.5
MDKFDA
95.8


### 4.2. Face Recognition Using YALE Database

The YALE database contains 165 front view face images from 15 individuals. Each individual has eleven images that vary with expression and configurations. Three kernels are employed as the base kernels of multiple kernel function in MDK, including linear kernel, Gaussian kernel, and polynomial kernel. Moreover, Gaussian kernel is adopted to construct DK. Table3 displays the average recognition rates of PCA, LDA, LPP, and MDKFDA. Table 4 reports the performance comparison of different kernel-based algorithms, including KPCA, KFDA, DKFDA, and MDKFDA. The results indicate that the MDKFDA algorithm outperforms the other algorithms and all the single kernel-based feature extraction algorithms outperform their corresponding linear versions.Table 3
Comparison of recognition ratio between linear algorithms and MDKFDA.
Algorithm
PCA
LPP
LDA
MDKFDA
Recognition ratio (%)
78.7
73.3
81.3
96.1Table 4
Comparison of recognition ratio between single kernel-based algorithms and MDKFDA.
Algorithm
Gaussian kernel (%)
Polynomial kernel (%)
KPCA
80.5
80.0
KFDA
90.7
86.7
DKFDA
93.3
93.3
MDKFDA
96.1


### 4.3. Face Recognition Using PIE Database

The PIE face database contains over 40,000 face images from 68 people, and the images are captured under 13 different poses, 43 different illumination, and 4 different expressions. In this test, we select 150 face images from 15 individuals. The selection of relevant base kernels for multiple kernel function and DK is the same as that in the former experiments. From Tables5 and 6, it can be seen that the MDKFDA algorithm outperforms the other algorithms.Table 5
Comparison of recognition ratio between linear algorithms and MDKFDA.
Algorithm
PCA
LPP
LDA
MDKFDA
Recognition ratio (%)
50.67
50.67
65.2
94.9Table 6
Comparison of recognition ratio between single kernel-based algorithms and MDKFDA.
Algorithm
Gaussian kernel (%)
Polynomial kernel (%)
KPCA
74.7
50.7
KFDA
81.3
78.7
DKFDA
93.5
90.3
MDKFDA
94.9


### 4.4. Discussions

Experiments based on the three face databases have been systematically implemented, and the results reveal some interesting findings which are summarized as follows.(1)
The single kernel-based nonlinear feature extraction algorithms such as KPCA, KFDA, and DKFDA perform better than their corresponding linear versions such as PCA and LDA. The main reason is attributed to the fact that, compared to the linear techniques, the features extracted by kernel-based algorithms can better describe the complex and nonlinear variations of face images, that is, illumination, pose, and facial expression. Hence, a better recognition rate can be achieved.(2)
The average recognition rates of PCA, LDA, and LPP on PIE database are significantly less than those on the other two databases. The reason is mainly as follows. Since the images from the PIE database are captured under more complicated conditions, they appear to have more complicated nonlinear characteristics than those from the other databases, which makes them difficult to handle by linear algorithms.(3)
The DKFDA algorithm outperforms the other single kernel-based algorithms, that is, KPCA, KLPP, and KFDA. As shown in Table6, when KPCA with polynomial kernel is adopted, the recognition ratio of face images is not increased. This is because the characteristics of kernel are ill-suited for some database. However, the DK can solve this problem, and the reason is that the DKFDA algorithm has the adaptability for different databases. The structure of DK can be changed by adjusting the kernel parameter using iterative method, so various input data can be better expressed.(4)
The proposed MDKFDA algorithm consistently performs better than the KPCA, KLPP, KFDA, and DKFDA as well as their corresponding linear version, which indicates that, compared to the single kernel-based algorithms, the MDKFDA algorithm can effectively integrate the multiple base kernels with data-dependent kernel (DK) and gain a good performance on face recognition.


## 4.1. Face Recognition Using ORL Database

The ORL face database contains 400 face images of 40 individuals, and variations in these 400 face images include angle, lighting, expression, and face details. As shown in Figure2, the size of all the original images were shaped into 48*48 pixels, and the primary part of the original image was reserved. Three kernels are employed as the base kernels of multiple kernel function in MDK, including linear kernel, Gaussian kernel, and polynomial kernel. Moreover, Gaussian kernel is adopted to construct DK. Table 1 shows the comparison of maximal average recognition ratio between several nonkernel algorithms and the proposed MDKFDA algorithm. Table 2 reports the comparison of maximal average recognition ratio between several single kernel-based algorithms and the proposed MDKFDA. According to the experiment results, the MDKFDA algorithm outperforms the other algorithms, which implies that the MDKFDA can integrate multiple base kernels with data-dependent kernel (DK) effectively to improve the recognition ratio. Besides, it can be seen that all the single kernel-based feature extraction algorithms outperform their corresponding linear versions, which indicates that the kernel-based algorithm is advantageous for face recognition.Table 1
Comparison of recognition ratio between linear algorithms and MDKFDA.
Algorithm
PCA
LPP
LDA
MDKFDA
Recognition ratio (%)
82.0
75.5
74.3
95.8Table 2
Comparison of recognition ratio between single kernel-based algorithms and MDKFDA.
Algorithm
Gaussian kernel (%)
Polynomial kernel (%)
KPCA
86.5
84.5
KFDA
88.0
85.0
DKFDA
93.5
92.5
MDKFDA
95.8


## 4.2. Face Recognition Using YALE Database

The YALE database contains 165 front view face images from 15 individuals. Each individual has eleven images that vary with expression and configurations. Three kernels are employed as the base kernels of multiple kernel function in MDK, including linear kernel, Gaussian kernel, and polynomial kernel. Moreover, Gaussian kernel is adopted to construct DK. Table3 displays the average recognition rates of PCA, LDA, LPP, and MDKFDA. Table 4 reports the performance comparison of different kernel-based algorithms, including KPCA, KFDA, DKFDA, and MDKFDA. The results indicate that the MDKFDA algorithm outperforms the other algorithms and all the single kernel-based feature extraction algorithms outperform their corresponding linear versions.Table 3
Comparison of recognition ratio between linear algorithms and MDKFDA.
Algorithm
PCA
LPP
LDA
MDKFDA
Recognition ratio (%)
78.7
73.3
81.3
96.1Table 4
Comparison of recognition ratio between single kernel-based algorithms and MDKFDA.
Algorithm
Gaussian kernel (%)
Polynomial kernel (%)
KPCA
80.5
80.0
KFDA
90.7
86.7
DKFDA
93.3
93.3
MDKFDA
96.1


## 4.3. Face Recognition Using PIE Database

The PIE face database contains over 40,000 face images from 68 people, and the images are captured under 13 different poses, 43 different illumination, and 4 different expressions. In this test, we select 150 face images from 15 individuals. The selection of relevant base kernels for multiple kernel function and DK is the same as that in the former experiments. From Tables5 and 6, it can be seen that the MDKFDA algorithm outperforms the other algorithms.Table 5
Comparison of recognition ratio between linear algorithms and MDKFDA.
Algorithm
PCA
LPP
LDA
MDKFDA
Recognition ratio (%)
50.67
50.67
65.2
94.9Table 6
Comparison of recognition ratio between single kernel-based algorithms and MDKFDA.
Algorithm
Gaussian kernel (%)
Polynomial kernel (%)
KPCA
74.7
50.7
KFDA
81.3
78.7
DKFDA
93.5
90.3
MDKFDA
94.9


## 4.4. Discussions

Experiments based on the three face databases have been systematically implemented, and the results reveal some interesting findings which are summarized as follows.(1)
The single kernel-based nonlinear feature extraction algorithms such as KPCA, KFDA, and DKFDA perform better than their corresponding linear versions such as PCA and LDA. The main reason is attributed to the fact that, compared to the linear techniques, the features extracted by kernel-based algorithms can better describe the complex and nonlinear variations of face images, that is, illumination, pose, and facial expression. Hence, a better recognition rate can be achieved.(2)
The average recognition rates of PCA, LDA, and LPP on PIE database are significantly less than those on the other two databases. The reason is mainly as follows. Since the images from the PIE database are captured under more complicated conditions, they appear to have more complicated nonlinear characteristics than those from the other databases, which makes them difficult to handle by linear algorithms.(3)
The DKFDA algorithm outperforms the other single kernel-based algorithms, that is, KPCA, KLPP, and KFDA. As shown in Table6, when KPCA with polynomial kernel is adopted, the recognition ratio of face images is not increased. This is because the characteristics of kernel are ill-suited for some database. However, the DK can solve this problem, and the reason is that the DKFDA algorithm has the adaptability for different databases. The structure of DK can be changed by adjusting the kernel parameter using iterative method, so various input data can be better expressed.(4)
The proposed MDKFDA algorithm consistently performs better than the KPCA, KLPP, KFDA, and DKFDA as well as their corresponding linear version, which indicates that, compared to the single kernel-based algorithms, the MDKFDA algorithm can effectively integrate the multiple base kernels with data-dependent kernel (DK) and gain a good performance on face recognition.


## 5. Conclusions

In this paper, on the assumption that multiple kernel-based recognition algorithms can depict the complex and heterogeneous face image dataset by the utilization of multiple descriptors, a novel kernel-based approach for face recognition, called multiple data-dependent kernel Fisher discriminant analysis (MDKFDA), is proposed in this paper. Focusing on the construction of MDK, two main issues have been considered. The first issue concerns optimizing the weights of multiple base kernels. For this purpose, by maximizing the margin maximization criterion (MMC), an iterative method based on Lagrange multipliers is adopted to yield the optimized weights. The second issue aims at optimizing the coefficients of data-dependent kernel. To this end, by solving the optimization equation based on Fisher scalar, a gradient-based learning algorithm is employed to yield the optimized coefficients. Finally, the resulting multiple kernel functions and data-dependent kernel are integrated together as a new kernel, which is incorporated into the KFDA to construct the MDKFDA. Experiments on three face databases prove the effectiveness of the MDKFDA, and this algorithm is ready to be applied to other classification applications in the future.



---

*Source: 898560-2014-08-06.xml*