# Multiple Kernel Dimensionality Reduction via Ratio-Trace and Marginal Fisher Analysis

Authors: Hui Xu; Yongguo Yang; Xin Wang; Mingming Liu; Hongxia Xie; Chujiao Wang
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

Traditional supervised multiple kernel learning (MKL) for dimensionality reduction is generally an extension of kernel discriminant analysis (KDA), which has some restrictive assumptions. In addition, they generally are based on graph embedding framework. A more general multiple kernel-based dimensionality reduction algorithm, called multiple kernel marginal Fisher analysis (MKL-MFA), is presented for supervised nonlinear dimensionality reduction combined with ratio-race optimization problem. MKL-MFA aims at relaxing the restrictive assumption that the data of each class is of a Gaussian distribution and finding an appropriate convex combination of several base kernels. To improve the efficiency of multiple kernel dimensionality reduction, the spectral regression frameworks are incorporated into the optimization model. Furthermore, the optimal weights of predefined base kernels can be obtained by solving a different convex optimization. Experimental results on benchmark datasets demonstrate that MKL-MFA outperforms the state-of-the-art supervised multiple kernel dimensionality reduction methods.


---

## Body

## 1. Introduction

Recently, multiple kernel dimensionality reduction methods have been attracting many researchers, and a series of methods are proposed based on the graph embedding framework [1–7]. These methods generally transform primal data into high-dimensional feature spaces deduced by a set of base kernels, where a linear transformation is seeking to perform dimensionality reduction. Consequently, these nonlinear dimensionality reduction methods not only deal with high-dimensional data effectively, but automatically select optimal kernels by predefining a set of base kernels. It has been demonstrated that multiple kernel method performs better than single kernel-based methods in dimensionality reduction.Although existing multiple kernel dimensionality reduction methods are significantly superior to single kernel-based dimensionality reduction methods, they are still confronted with challenging issues. Firstly, these algorithms have to iteratively solve the time-consuming generalized eigenvalue problem, which is a part of alternative optimization methods. Secondly, in addition, it generally transforms the primal model into the simple form by relaxing the SDP (Semidefinite Programming) problem or utilizes gradient descent algorithms to obtain local optima, which all could have a negative effect on its performance. To overcome the shortcomings mentioned above, some multiple kernel dimensionality reduction algorithms based on spectral regression were proposed recently [8–10]. They transform eigen-decomposition of dense matrices into a linear regression problem by means of spectral regression. However, they still make good use of the convex relaxation or gradient descent to optimize the kernel weights. Instead of convex relaxation, a multiple kernel learning framework was recently proposed to avoid relaxing the primal problem [11], which learns a transformation into a space of lower dimension by converting a ratio-trace maximization problem into a semi-infinite linear program. But this method still needs to iteratively compute generalized eigen-decomposition of dense matrices. In addition, these methods are regarded as multiple kernel versions of KDA and unified under the graph embedding framework. Thus, they all have the assumption that the distribution of each class is considered to be a unimodal Gaussian. This property often does not exist in real world applications and separability of the different classes cannot be well characterized by interclass scatter. Although kernel marginal Fisher analysis (KMFA) has been developed to overcome this limitation by using an intrinsic graph and another penalty graph [12], it has to choose the kernel type and determine its parameters beforehand.Motivated by these methods, in this paper, a new multiple kernel dimensionality reduction algorithm, called multiple kernel marginal fisher analysis (MKMFA), is presented for supervised nonlinear dimensionality reduction. MKMFA not only solves the problem of the restrictive assumption of existing multiple kernel dimensionality reduction methods, but has the ability of automatically constructing appropriate kernels for nonlinear dimensionality reduction by means of the ratio-trace model. Furthermore, spectral regression is used to address the issue of dense metrics decomposition and speed up the learning of MKMFA. Finally, as other multiple kernel-based dimensionality reduction methods would do, it can also solve the out-of-sample extension problem.


## 2. Related Work

### 2.1. Marginal Fisher Analysis

Graph framework is a general platform designing for dimensionality reduction algorithms, and ISOMAP, LLE, and Laplace feature mapping algorithm can be derived from it. With this framework, we develop a new dimensionality reduction algorithm, in order to avoid limitations of traditional linear discriminant analysis in data distribution assumption and available projection direction.The assumption of the linear discriminant analysis algorithm is that the data of each class is Gaussian distribution, which is usually nonexistent in practical problems. Without this property, the separability of different classes cannot be characterized by interclass scatter. This limitation of LDA can be overcome by developing new standards that are characterized by intraclass compactness and interclass separability. To this end, we propose a new algorithm using the graph embedding framework which is called marginal Fisher analysis (MFA). We design an intrinsic graph with the characteristics of intraclass compactness and another penalty graph characterized by interclass separability. Specifically, the intrinsic graph illustrates the adjacency relationship of the intraclass point, and the connection of each sample to the nearest neighbork1 in the same class. The penalty graph describes the adjacency relationship of the interclass marginal point and the marginal point pairs of different categories.By following the graph embedding formulation, intraclass compactness is characterized from the intrinsic graph by the term [11–13](1)Sc=∑ii∈Nk1+jorj∈Nk1+i∑wTxi-wTxj2Wij=2wTXD-WXTwwhere (2)Wij=1,ifi∈Nk1+jorj∈Nk1+i0,else.Here, Nk1+(i) indicates the index set of the k1 nearest neighbors of the sample xi in the same class. Interclass separability is characterized by a penalty graph with the term [11–13](3)Sp=∑ii,j∈Pk2ciori,j∈Pk2cj∑wTxi-wTxj2Wijp=2wTXDp-WpXTwwhere(4)Wijp=1,ifi,j∈Pk2ciori,j∈Pk2cj0,else.Here,Pk2(c) is a set of data pairs that are the k2 nearest pairs among the set (i,j),i∈πc,j∉πc, where πc denotes the index set of the samples belonging to thecth class. The algorithmic procedure of marginal Fisher analysis algorithm is formally stated as follows [11–13]:( 1 ) Firstly, project the data set into PCA subspace by preserving N-NC dimensions or a certain energy. The transformation matrix of PCA was represented by WPCA.( 2 ) Construct the intraclass compactness and interclass separability graphs. In the intraclass compactness graph, for each sample xi, set the adjacency matrix Wij=Wji=1 if xi is among the k1-nearest neighbors of xj in the same class. In the interclass separability graph, for each class c, set the similarity matrix Wijp=1 if the pair (i,j) is among the k2 shortest pairs among the set(i,j),i∈πc,j∉πc.( 3 ) Marginal Fisher Criterion. From the linearization of the graph embedding framework, we have the Marginal Fisher Criterion(5)w∗=arg⁡minw⁡wTXD-WXTwwTXDp-WpXTwwhich is a special linearization of the graph embedding framework with(6)B=Dp-Wp( 4 ) Output the final linear projection direction as(7)w=WPCAw∗


### 2.2. Ratio-Trace Optimization Problem

For any twod×d symmetric positive semidefinite matrices S1 and S2, the ratio-trace problem is defined as [14](8)maxW⁡traceWTS1W-1WTS2WFor a given kernel functionK, the kernelized versions of these algorithms solve the following ratio-trace problem:(9)maxA⁡traceAT1-ρKLK+ρKA-1ATKL′KAwhere A is a transformation matrix, K is the N×N kernel matrix with Kij=kxi,xj, and ρ∈ (0,1) is a regularization parameter used to prevent overfitting. L and L′ are (algorithm-dependent) N×N symmetric positive semidefinite matrices. The optimal solution to (9) is given by the generalized eigenvectors corresponding to the nonzero generalized Eigenvalues:(10)KL′Kγ=λ1-ρKLK+ρKγOnce A is obtained, the new representation for a data sample xnew∈Rd can be computed using (11)xnew=ATkx1,x,…,kxN,xT


## 2.1. Marginal Fisher Analysis

Graph framework is a general platform designing for dimensionality reduction algorithms, and ISOMAP, LLE, and Laplace feature mapping algorithm can be derived from it. With this framework, we develop a new dimensionality reduction algorithm, in order to avoid limitations of traditional linear discriminant analysis in data distribution assumption and available projection direction.The assumption of the linear discriminant analysis algorithm is that the data of each class is Gaussian distribution, which is usually nonexistent in practical problems. Without this property, the separability of different classes cannot be characterized by interclass scatter. This limitation of LDA can be overcome by developing new standards that are characterized by intraclass compactness and interclass separability. To this end, we propose a new algorithm using the graph embedding framework which is called marginal Fisher analysis (MFA). We design an intrinsic graph with the characteristics of intraclass compactness and another penalty graph characterized by interclass separability. Specifically, the intrinsic graph illustrates the adjacency relationship of the intraclass point, and the connection of each sample to the nearest neighbork1 in the same class. The penalty graph describes the adjacency relationship of the interclass marginal point and the marginal point pairs of different categories.By following the graph embedding formulation, intraclass compactness is characterized from the intrinsic graph by the term [11–13](1)Sc=∑ii∈Nk1+jorj∈Nk1+i∑wTxi-wTxj2Wij=2wTXD-WXTwwhere (2)Wij=1,ifi∈Nk1+jorj∈Nk1+i0,else.Here, Nk1+(i) indicates the index set of the k1 nearest neighbors of the sample xi in the same class. Interclass separability is characterized by a penalty graph with the term [11–13](3)Sp=∑ii,j∈Pk2ciori,j∈Pk2cj∑wTxi-wTxj2Wijp=2wTXDp-WpXTwwhere(4)Wijp=1,ifi,j∈Pk2ciori,j∈Pk2cj0,else.Here,Pk2(c) is a set of data pairs that are the k2 nearest pairs among the set (i,j),i∈πc,j∉πc, where πc denotes the index set of the samples belonging to thecth class. The algorithmic procedure of marginal Fisher analysis algorithm is formally stated as follows [11–13]:( 1 ) Firstly, project the data set into PCA subspace by preserving N-NC dimensions or a certain energy. The transformation matrix of PCA was represented by WPCA.( 2 ) Construct the intraclass compactness and interclass separability graphs. In the intraclass compactness graph, for each sample xi, set the adjacency matrix Wij=Wji=1 if xi is among the k1-nearest neighbors of xj in the same class. In the interclass separability graph, for each class c, set the similarity matrix Wijp=1 if the pair (i,j) is among the k2 shortest pairs among the set(i,j),i∈πc,j∉πc.( 3 ) Marginal Fisher Criterion. From the linearization of the graph embedding framework, we have the Marginal Fisher Criterion(5)w∗=arg⁡minw⁡wTXD-WXTwwTXDp-WpXTwwhich is a special linearization of the graph embedding framework with(6)B=Dp-Wp( 4 ) Output the final linear projection direction as(7)w=WPCAw∗


## 2.2. Ratio-Trace Optimization Problem

For any twod×d symmetric positive semidefinite matrices S1 and S2, the ratio-trace problem is defined as [14](8)maxW⁡traceWTS1W-1WTS2WFor a given kernel functionK, the kernelized versions of these algorithms solve the following ratio-trace problem:(9)maxA⁡traceAT1-ρKLK+ρKA-1ATKL′KAwhere A is a transformation matrix, K is the N×N kernel matrix with Kij=kxi,xj, and ρ∈ (0,1) is a regularization parameter used to prevent overfitting. L and L′ are (algorithm-dependent) N×N symmetric positive semidefinite matrices. The optimal solution to (9) is given by the generalized eigenvectors corresponding to the nonzero generalized Eigenvalues:(10)KL′Kγ=λ1-ρKLK+ρKγOnce A is obtained, the new representation for a data sample xnew∈Rd can be computed using (11)xnew=ATkx1,x,…,kxN,xT


## 3. Multiple Marginal Fisher Analysis Kernel Dimensionality Reduction via Ratio-Trace

### 3.1. Kernel Marginal Fisher Analysis via Ratio-Trace

The kernel trick is widely used to improve the separation ability of a linear supervised dimensionality reduction algorithm. By using the kernel trick, the marginal Fisher analysis can be further improved. By replacingL and L′ by (Dp-Wp) and (D-W), respectively, problem (9) can be rewritten as follows:(12)maxA⁡traceAT1-ρKD-WK+ρKA-1ATKDp-WpKANote that the graphs of kernel marginal Fisher analysis (KMFA) may be different from MFA because the nearest neighborsk1 for each sample in KMFA is different from one in MFA. In each class the k1 nearest in-class neighbors of each sample and the k2 closest out-of-class sample pairs can be measured through the use of the kernel mapping function Φx from the original feature space to the higher dimensional Hilbert space. The distance between sample xi and sample xj can be obtained by the following formula:(13)Dxi,xj=Φxi-Φxj=kxi,xi+kxj,xj-2kxi,xj


### 3.2. Multiple Kernel Marginal Fisher Analysis Dimensionality Reduction

In this section, a multiple kernel Fisher analysis framework is presented to incorporate spectral regression and ratio-trace into multiple kernel learning for dimensionality reduction. On one hand, spectral regression does not increase speed at the cost of some accuracy. On the other hand, the ratio-trace optimization algorithm can avoid conventional convex relaxation or gradient descent optimization method. The formulation of multiple kernel learning with MFA and ratio-trace will be illustrated, which not only combines multiple kernel dimensionality reduction with MFA, but selects optimal kernels more effectively than other multiple kernel dimensionality reduction methods by semi-infinite linear program (SLIP).In the MKL framework, the kernel functionK is parametrized as a linear combination of predefined base kernels K1,…,Km:(14)K=∑m=1MβmKm,βm≥0,∑m=1Mβm=1,where Km={km(xi,xj)}i,j=1n and the weights β=β1,…,βm are learned from the data. Under the kernel marginal Fisher analysis framework based on ratio-trace, a multiple kernel variant of KMFA is deduced by combining MFA with MKL, termed as MKMFA, which is formulated as the following optimization problem:(15)maximizeA,K,β⁡traceAT1-ρKD-WK+ρKA-1ATKDp-WpKAGiven the input data pointxi,yi, where xi∈Rd and yi is the class label of xi. Denote X=x1,….,xn∈Rd×n as the training data matrix. The detailed steps of MKMFA are given as follows:Step 1.
Constructing the intraclass compactness graphW and interclass separability graph Wp.Step 2.
We extend the Marginal Fisher Criterion to the multiple kernel case in the following way:
Firstly, intraclass compactness is characterized from the intrinsic graph by the term(16)Sc=∑i∑i∈Nk1+jorj∈Nk1+iαTKiβ-αTKjβ2=2αTKD-WKα,where α=[α1,…,αn]T∈Rn, β=[β1,…,βM]T∈RM, and Ki=k11,i⋯kM1,i⋮⋱⋮k1n,i⋯kMn,i∈Rn×M.D=diag(D1,…,Dn) is a diagonal matrix with the diagonal elements defined as Di=∑j=1nwij.Secondly, interclass separability is characterized by a penalty graph with the term(17)Sp=∑i∑i,j∈Pk2ciori,j∈Pk2cjαTKiβ-αTKjβ2=2αTKDp-WpKα,where Dp is the degree matrix of Wp.To obtain a multidimensional projection, we consider a set of c sample coefficient vectors, denoted byA=α1,α2,…αc∈Rn×c. Finally, Multiple Kernel Marginal Fisher Criterion can be denoted as follows:(18)maxA,βtrAT1-ρKD-WK+ρKA-1ATKDp-WpKAs.t.βm≥0,∑mMβm=1,m=1,2,…,Mwhere ρ∈(0,1) is a regularization parameter used to prevent overfitting.Step 3.
Assume the ranks ofD-W and Dp-Wp are r and r′, respectively. Let {(αi,μi)}i=1r and {(βi,νi)}i=1r′ be the nonzero Eigenvalue-Eigenvector pairs of D-W and Dp-Wp, respectively. We can obtain the optimal β∗ by solving the following semi-infinite linear program [15]:(19)maxτ,βτs.t.∑mMβmSmθ≥τ,∀θ∈Rr×r′,βm≥0,∑mMβm=1,∀mwhere Smθ=1/ρ∑i=1r′θiTθi/4(1-ρ)+θiTPTKmPθi/4ρ-θiTPTKmqi+trace(KmDp-Wp) being M functions defined ∀θ=[θ1,…,θr′]∈Rr×r′and P=[α1μ1,…,αrμr] and qi=βiνi for i=1,2,…,r′.Step 4.
Solve the ratio-trace problem (18) using spectral regression to get optimal A∗. Since Dp-Wp and D-W are all sparse matrices, we can use spectral regression to obtain A in the following way:( 1 ) Find the largest c generalized eigenvectors y0,y1,…,yc-1 of the following eigen-problem:(20)Dp-Wpy=λ1-ρD-W+ρIy,( 2 ) Find αk(k=1…c) by solving the following least squares regression:(21)αk=arg⁡min⁡α⁡∑i=1nαTKiβ∗-yik2+γα2where yik is thei-th element of yk.Algorithm1 summarizes the algorithm for solving (18). This iterative algorithm is referred to as MKL-MFA. The alternating algorithm for solving the proposed SILP problem belongs to a family of algorithms for solving general semi-infinite programming problems called the exchange methods, in which the constraints are exchanged at each iteration. These methods have been guaranteed to converge [16].Algorithm 1:MKL-MFA algorithm.
Input:{Km}m=1M,T,ρ,ϵ. Output:A∗ Step1: Initialization: βm=1/M,∀m,ζ=+∞,t=1,C=Φ,  1-ρK(D-W)K+ρK,K(Dp-Wp)K. Step2: Compute P=[α1μ1,…,αrμr], and qi=βiνi, where {(αi,μi)}i=1r and {(βi,νi)}i=1r′ are the non-zero Eigenvalue-Eigenvector Pairs ofK(Dp-Wp)K and 1-ρK(D-W)K+ρK respectively. Step3: Solve the SILP (19) to obtain β∗ as follows: Whilet≤T K=∑m=1MβmKm Fori=1,…,r′ Computeηi∗ by solving (I/2(1-ρ)+PTKP/2ρ)ηi∗=PTKqi. end If1-∑m=1MβmSmη∗/ζ<ϵ break; else Addη∗ to the constraint set C. Update μ and ζ by solving restricted Version of (19) using only η∈C. end t= t+1; end Step4: Solve the ratio-trace problem(3) using spectral regression with K∗=∑m=1Mβm∗Km, To get optimalA∗. Step5: The new non-linearly transformed representation for a data sample x∈Rd can be computed by x′=A∗T[K∗x1,x,…,K∗xN,x]T and K∗xi,x=∑m=1Mβm∗Km(xi,x).Compared with existing supervised multiple kernel dimensionality reduction based on LDA [14, 17–23], the proposed method has the following advantages:(1)
The projection direction that MFA can use is much greater than that of LDA, and the dimension size is determinedk2, that is, the number of the shortest pairs between in-class and out-of-class samples.(2)
Do not assume the data distribution in each class, and the intraclass compactness is characterized by the sum of the distance between each data and the nearest neighbork1 in the same class. Therefore, discriminant analysis is more general.(3)
Without prior information of data distribution, the interclass margin can better characterize the separability in different classes than the interclass variance in LDA.(4)
Avoid conventional convex relaxation or gradient descent optimization algorithm, and optimal kernels can be more effectively obtained than other multiple kernel dimensionality reduction methods.


## 3.1. Kernel Marginal Fisher Analysis via Ratio-Trace

The kernel trick is widely used to improve the separation ability of a linear supervised dimensionality reduction algorithm. By using the kernel trick, the marginal Fisher analysis can be further improved. By replacingL and L′ by (Dp-Wp) and (D-W), respectively, problem (9) can be rewritten as follows:(12)maxA⁡traceAT1-ρKD-WK+ρKA-1ATKDp-WpKANote that the graphs of kernel marginal Fisher analysis (KMFA) may be different from MFA because the nearest neighborsk1 for each sample in KMFA is different from one in MFA. In each class the k1 nearest in-class neighbors of each sample and the k2 closest out-of-class sample pairs can be measured through the use of the kernel mapping function Φx from the original feature space to the higher dimensional Hilbert space. The distance between sample xi and sample xj can be obtained by the following formula:(13)Dxi,xj=Φxi-Φxj=kxi,xi+kxj,xj-2kxi,xj


## 3.2. Multiple Kernel Marginal Fisher Analysis Dimensionality Reduction

In this section, a multiple kernel Fisher analysis framework is presented to incorporate spectral regression and ratio-trace into multiple kernel learning for dimensionality reduction. On one hand, spectral regression does not increase speed at the cost of some accuracy. On the other hand, the ratio-trace optimization algorithm can avoid conventional convex relaxation or gradient descent optimization method. The formulation of multiple kernel learning with MFA and ratio-trace will be illustrated, which not only combines multiple kernel dimensionality reduction with MFA, but selects optimal kernels more effectively than other multiple kernel dimensionality reduction methods by semi-infinite linear program (SLIP).In the MKL framework, the kernel functionK is parametrized as a linear combination of predefined base kernels K1,…,Km:(14)K=∑m=1MβmKm,βm≥0,∑m=1Mβm=1,where Km={km(xi,xj)}i,j=1n and the weights β=β1,…,βm are learned from the data. Under the kernel marginal Fisher analysis framework based on ratio-trace, a multiple kernel variant of KMFA is deduced by combining MFA with MKL, termed as MKMFA, which is formulated as the following optimization problem:(15)maximizeA,K,β⁡traceAT1-ρKD-WK+ρKA-1ATKDp-WpKAGiven the input data pointxi,yi, where xi∈Rd and yi is the class label of xi. Denote X=x1,….,xn∈Rd×n as the training data matrix. The detailed steps of MKMFA are given as follows:Step 1.
Constructing the intraclass compactness graphW and interclass separability graph Wp.Step 2.
We extend the Marginal Fisher Criterion to the multiple kernel case in the following way:
Firstly, intraclass compactness is characterized from the intrinsic graph by the term(16)Sc=∑i∑i∈Nk1+jorj∈Nk1+iαTKiβ-αTKjβ2=2αTKD-WKα,where α=[α1,…,αn]T∈Rn, β=[β1,…,βM]T∈RM, and Ki=k11,i⋯kM1,i⋮⋱⋮k1n,i⋯kMn,i∈Rn×M.D=diag(D1,…,Dn) is a diagonal matrix with the diagonal elements defined as Di=∑j=1nwij.Secondly, interclass separability is characterized by a penalty graph with the term(17)Sp=∑i∑i,j∈Pk2ciori,j∈Pk2cjαTKiβ-αTKjβ2=2αTKDp-WpKα,where Dp is the degree matrix of Wp.To obtain a multidimensional projection, we consider a set of c sample coefficient vectors, denoted byA=α1,α2,…αc∈Rn×c. Finally, Multiple Kernel Marginal Fisher Criterion can be denoted as follows:(18)maxA,βtrAT1-ρKD-WK+ρKA-1ATKDp-WpKAs.t.βm≥0,∑mMβm=1,m=1,2,…,Mwhere ρ∈(0,1) is a regularization parameter used to prevent overfitting.Step 3.
Assume the ranks ofD-W and Dp-Wp are r and r′, respectively. Let {(αi,μi)}i=1r and {(βi,νi)}i=1r′ be the nonzero Eigenvalue-Eigenvector pairs of D-W and Dp-Wp, respectively. We can obtain the optimal β∗ by solving the following semi-infinite linear program [15]:(19)maxτ,βτs.t.∑mMβmSmθ≥τ,∀θ∈Rr×r′,βm≥0,∑mMβm=1,∀mwhere Smθ=1/ρ∑i=1r′θiTθi/4(1-ρ)+θiTPTKmPθi/4ρ-θiTPTKmqi+trace(KmDp-Wp) being M functions defined ∀θ=[θ1,…,θr′]∈Rr×r′and P=[α1μ1,…,αrμr] and qi=βiνi for i=1,2,…,r′.Step 4.
Solve the ratio-trace problem (18) using spectral regression to get optimal A∗. Since Dp-Wp and D-W are all sparse matrices, we can use spectral regression to obtain A in the following way:( 1 ) Find the largest c generalized eigenvectors y0,y1,…,yc-1 of the following eigen-problem:(20)Dp-Wpy=λ1-ρD-W+ρIy,( 2 ) Find αk(k=1…c) by solving the following least squares regression:(21)αk=arg⁡min⁡α⁡∑i=1nαTKiβ∗-yik2+γα2where yik is thei-th element of yk.Algorithm1 summarizes the algorithm for solving (18). This iterative algorithm is referred to as MKL-MFA. The alternating algorithm for solving the proposed SILP problem belongs to a family of algorithms for solving general semi-infinite programming problems called the exchange methods, in which the constraints are exchanged at each iteration. These methods have been guaranteed to converge [16].Algorithm 1:MKL-MFA algorithm.
Input:{Km}m=1M,T,ρ,ϵ. Output:A∗ Step1: Initialization: βm=1/M,∀m,ζ=+∞,t=1,C=Φ,  1-ρK(D-W)K+ρK,K(Dp-Wp)K. Step2: Compute P=[α1μ1,…,αrμr], and qi=βiνi, where {(αi,μi)}i=1r and {(βi,νi)}i=1r′ are the non-zero Eigenvalue-Eigenvector Pairs ofK(Dp-Wp)K and 1-ρK(D-W)K+ρK respectively. Step3: Solve the SILP (19) to obtain β∗ as follows: Whilet≤T K=∑m=1MβmKm Fori=1,…,r′ Computeηi∗ by solving (I/2(1-ρ)+PTKP/2ρ)ηi∗=PTKqi. end If1-∑m=1MβmSmη∗/ζ<ϵ break; else Addη∗ to the constraint set C. Update μ and ζ by solving restricted Version of (19) using only η∈C. end t= t+1; end Step4: Solve the ratio-trace problem(3) using spectral regression with K∗=∑m=1Mβm∗Km, To get optimalA∗. Step5: The new non-linearly transformed representation for a data sample x∈Rd can be computed by x′=A∗T[K∗x1,x,…,K∗xN,x]T and K∗xi,x=∑m=1Mβm∗Km(xi,x).Compared with existing supervised multiple kernel dimensionality reduction based on LDA [14, 17–23], the proposed method has the following advantages:(1)
The projection direction that MFA can use is much greater than that of LDA, and the dimension size is determinedk2, that is, the number of the shortest pairs between in-class and out-of-class samples.(2)
Do not assume the data distribution in each class, and the intraclass compactness is characterized by the sum of the distance between each data and the nearest neighbork1 in the same class. Therefore, discriminant analysis is more general.(3)
Without prior information of data distribution, the interclass margin can better characterize the separability in different classes than the interclass variance in LDA.(4)
Avoid conventional convex relaxation or gradient descent optimization algorithm, and optimal kernels can be more effectively obtained than other multiple kernel dimensionality reduction methods.


## 4. Experiments

To validate the effectiveness of the proposed method, all algorithms are carried out on UCI (University of California, Irvine) datasets, digits recognition and face recognition datasets. The characteristics of the datasets are summarized in Table1. For fair comparison, the final reduced dimension is equal to the number of classes of each dataset for all algorithms and the libSVM tool is used to classify the reduced data. For each dataset, training and testing sets are selected randomly with ratio 1:1. After that, the values of samples are normalized to the range [0,1] for each dataset. Finally, we analyze and compare our method with other algorithms by repeating each algorithm 20 runs.Table 1
Description of benchmark datasets.
Datasets Dimensions # of samples # of classes Ionosphere 33 351 2 Sonar 60 208 2 USPS 256 3000 10 Isolet 617 900 3 MINIST 784 600 3 Yale 1024 165 15 PIE 1024 680 4 ORL 1024 400 40 COIL-20 1024 1440 20For fair comparison, 10 RBF base kernels are predefined to construct the ensemble kernelK as the MKL-TR algorithm [12], and the values of parameter σ are set as 0.10, 0.22, 0.46, 1.00, 2.15, 4.46, 10.00, 21.54, 46.42, and 100.00, respectively. Based on these base kernels, MKL-MFA is mainly compared with EMFA[10], MKL-DR [11], MKL-TR [12], and MKL-SRTR [13] in supervised settings. The parameters k1 and k2 of MKL-MFA and EMFA are all equal to 10, while the parameters γ and ρ are specified by cross-validation. For MKL-TR, we set M=HHTH†HT-1/n11T and N=I-HHTH†HT,where∙† denotes pseudoinverse and H is the indicator matrix with Hij=1 if xi belongs to class j, and 0 otherwise. As the settings of MKL-SRTR and MKL-DR, we also define the affinity matrix W=[wij] as (22)wij=1nyi,ifyi=yj,0,otherwise,and set another affinity matrix W′=[wij′], where wij′=1/N. For EMFA, the parameter γ and the number of hidden nodes L are obtained by a 10-fold cross-validation. According to the mean classification accuracies and the standard deviations, the performance of each algorithm is evaluated and reported in Table 2.Table 2
Classification accuracy of different DR methods.
Datasets MKL-DR MKL-TR MKL-SRTR KMFA EMFA MKL-MFA Ionosphere 91.24 ± 3.67 92.43± 0.86 92.62± 0.73 90.84±1.48 93.73±1.42 95.66±1.52 Sonar 80.44± 5.46 83.26± 4.13 84.35± 2.58 82.65±2.26 87.52±2.25 90.75±2.39 USPS 90.65± 0.77 92.93± 0.43 92.82± 0.52 91.69±0.93 96.59±0.37 97.83±0.45 Isolet 93.47± 0.22 95.17± 0.11 96.76± 0.13 92.25±0.77 98.86±0.43 98.47±0.22 MNIST 90.26± 0.62 93.38± 0.82 92.54± 0.76 88.35±1.86 95.47±1.64 97.69±0.95 Yale 69.59± 5.26 72.71± 5.54 74.28± 4.64 70.89±5.25 82.76±4.97 84.89±5.32 PIE 85.38 ± 0.13 87.29± 0.19 89.92± 0.16 82.15±0.87 90.34±0.83 93.15±0.11 ORL 91.49± 1.84 91.45± 1.27 92.41± 1.07 89.19±0.52 95.26±0.93 96.19±0.89 COIL-20 92.57± 0.89 91.33± 0.35 94.96± 0.27 90.47±0.94 96.58±0.34 97.63±0.15From Table2, the performance of MKL-MFA is significantly superior to that of KMFA, EMFA, MKL-TR, MKL-DR, and MKL-SRTR on all datasets. The results of KMFA are worse than other methods; this is due to the fact that the combination of multiple base kernels can improve the performance of single kernel-based algorithms. Our method outperforms MKL-DR, MKL-TR, and MKL-SRTR, since MKL-MFA utilizes the penalty graph to characterize the interclass marginal point adjacency relationship. Without prior information on data distributions, the interclass margin can better characterize the separability of different classes than the interclass variance in KDA. The performance of our model also goes beyond that of EMFA, which can be attributed to the fact that our model finds the global optimum by converting a ratio-trace maximization problem into a semi-infinite linear program instead of the convex relaxation or gradient descent. Experimental results demonstrate that MKL-MFA makes good use of ratio-trace optimization, MKL and MFA to achieve the outstanding discriminant analysis power and yields the best results.To analyze the performance of our model further, we test MKL-TR and MKL-MFA in the 30 runs of experiments on Ionosphere with different splits of training and testing set. The mean values of kernel weights are reported in Table3. For comparison, in Table 3 the best classification accuracies of KFDA corresponding to the 10 base kernels are also displayed, respectively. As can be seen from Table 3,K3,K4,K5, andK6 are more suitable for KFDA than other kernels. It can be observed that our method tends to assign larger weights onK3,K4,K5, andK6. As a result, our method is able to combine base kernels with appropriate weights and overly outperforms KFDA with the best single kernel.Table 3
The learned weights and classification accuracies of KFDA with the single kernel on Ionosphere.
σ Weights learned by MKL-TR Weights learned by MKL-MFA KFDA with the single kernel 0.10 0.02 0.01 64.53 0.22 0.02 0.01 65.75 0.46 0.06 0.03 90.82 1.00 0.36 0.40 92.24 2.15 0.37 0.42 93.07 4.46 0.13 0.11 91.98 10.00 0.03 0.02 90.17 21.54 0.02 0.01 88.67 46.42 0.001 0.001 87.73 100.00 0.01 0.002 85.26To validate the effectiveness of our model on high-dimensional data, we select 40 samples from 9 classes of PIE face dataset, projecting them into two-dimensional space using MKL-MFA, as displayed in Figure1. It is shown that the projected results of MKL-MFA and MKL-SRTR have the better separability than those of MKL-DR and MKL-TR. The separability of embedded data of MKL-MFA is much clearer than that of other models. Consequently, our model is also superior to others on high-dimensional data.Figure 1
Comparison of two-dimensional embedded results obtained by different algorithms on the first 9 classes of PIE. (a) Projection of training data using supervised MKL-DR. (b) Projection of training data using supervised MKL-TR. (c) Projection of training data using supervised MKL-SRTR. (d) Projection of training data using MKL-MFA.
(a) (b) (c) (d)To further evaluate the effectiveness of MKL-MFA, we used bearing vibration signals of accelerometer sensors under different operating loads as a real world dataset. The vibration signals were collected by using a 16 channel digital audio tape (DAT) recorder at the sampling frequency 12 kHz. The experimental vibration data were divided into four datasets, named as D_IRF, D_ORF, D_BF, and D_MIX shown in Table4, where “07”, “14”, “21”, and “28” mean that fault diameters are 0.007, 0.014, 0.021, and 0.028 inches, respectively [24]. Signals were selected randomly to form training and testing sets with ratio 1:1.Table 4
The experimental datasets.
Datasets Number Fault type and diameter Description D_IRF 1000 Normal, IRF07, IRF14, IRF21, IRF28 inner race fault severity D_ORF 800 Normal, ORF07, ORF14, ORF21 outer race fault severity D_BF 1000 Normal, BF07, BF14, BF21, BF28 ball fault severity D_MIX 800 Normal, IRF14, ORF14, BF14 mixed fault classificationFirstly, vibration signals were transformed into 10 time domain features, 3 frequency domain features, and 16 time-frequency domain features [24]. Secondly, deferent dimensionality algorithms were carried out to extract low dimensional features from the transformed signals. Finally, we used SVM to train and test low dimensional features to compare our method with other DR methods. The classification accuracy rates are reported in Table 5. It can be seen that, compared with other algorithms, MKL-MFA achieves much better performance on all datasets, which further validates the effectiveness of MKL-MFA for feature extraction of vibration signals in real applications.Table 5
The classification accuracy rates on four bearing vibration signal datasets.
Datasets MKL-TR MKL-DR MKL-SRTR EMFA MKL-MFA D_MIX 0.9363 0.9257 0.9485 0.9854 0.9914 D_IRF 0.9415 0.9151 0.9312 0.9627 0.9862 D_ORF 0.9228 0.9238 0.9554 0.9716 0.9848 D_BF 0.9086 0.8992 0.9027 0.9285 0.9537


## 5. Conclusions

In this paper, we extend the Marginal Fisher Criterion to the multiple kernel case. Based on the extended criterion, a new multiple kernel-based dimensionality reduction algorithm termed as MKL-MFA is proposed for supervised nonlinear dimensionality reduction. Without prior information on data distributions, MKL-MFA is more general for multiple kernel discriminant analysis. Experimental results on benchmark and real world datasets validate the promising performance of MKL-MFA, respectively. In the near future, we intend to improve our model by introducing deep kernel networks and study nonlinear dimensionality reduction methods via deep models.



---

*Source: 6941475-2019-01-14.xml*