# Multiple Kernel Spectral Regression for Dimensionality Reduction

Authors: Bing Liu; Shixiong Xia; Yong Zhou
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Traditional manifold learning algorithms, such as locally linear embedding, Isomap, and Laplacian eigenmap, only provide the embedding results of the training samples. To solve the out-of-sample extension problem, spectral regression (SR) solves the problem of learning an embedding function by establishing a regression framework, which can avoid eigen-decomposition of dense matrices. Motivated by the effectiveness of SR, we incorporate multiple kernel learning (MKL) into SR for dimensionality reduction. The proposed approach (termed MKL-SR) seeks an embedding function in the Reproducing Kernel Hilbert Space (RKHS) induced by the multiple base kernels. An MKL-SR algorithm is proposed to improve the performance of kernel-based SR (KSR) further. Furthermore, the proposed MKL-SR algorithm can be performed in the supervised, unsupervised, and semi-supervised situation. Experimental results on supervised classification and semi-supervised classification demonstrate the effectiveness and efficiency of our algorithm.


---

## Body

## 1. Introduction

In real applications, the resulting data representations are generally high dimensional. Practical algorithms usually behave badly when faced with many unnecessary features. Hence, finding a way of transforming them into a unified space of lower dimension can facilitate the underlying tasks such as pattern recognition or regression problems. Dimensionality reduction (DR) techniques, which have been widely used in many fields of information processing, include unsupervised, supervised, and semisupervised methods due to different assumptions about the data distribution or the availability of the data labeling.In order to handle the data sampled from a nonlinear low dimensional manifold, many manifold learning techniques, such as ISOMAP [1], Locally Linear Embedding (LLE) [2], and Laplacian Eigenmap [3], have been proposed in recent years, which reduce the dimensionality of a fixed training set in a way that can maximally preserve certain interpoint relationships. One of the major limitations of these methods is that they do not generally address the out-of-sample problem. Although some methods explicitly require an embedding function either linear or in RKHS when minimizing the objective function [4, 5], the computation of these methods involves eigendecomposition of dense matrices which is expensive in both time and memory. Spectral regression (SR), which is fundamentally based on regression and spectral graph analysis [6–10], can avoid eigen-decomposition of dense matrices and has better performance at a faster learning speed. Moreover, it can be performed either in supervised, unsupervised, or semisupervised situation. Kernel SR (KSR) is the kernelized version of SR in the reproducing kernel Hilbert space (RKHS), which can further improve the performance of SR. While KSR is based on a single kernel, in practice it is often hard to select a suitable kernel. A common way to an automatic selection of optimal kernels is to learn a linear combination of base kernels. Motivated by the effectiveness of SR, we introduce a framework called MKL-SR that incorporates multiple kernel learning (MKL) into the training process of SR. We will illustrate the formulation of MKL-SR with graph embedding [11], which provides a unified view for a large family of DR methods. Any DR technique expressible by graph embedding can therefore be generalized by MKL-SR to boost their power by automatically selecting optimal kernels. As the corresponding SR algorithm would do, the proposed approach not only solves the out-of-sample extension problem but also improves the performance of kernel-based SR (KSR) for the supervised, semisupervised, and unsupervised learning problems.The paper is structured as follows. In Section2, we briefly introduce the related work. We provide the MKL-SR framework and present the optimization process in Section 3. The experimental results are shown in Section 4. Finally, we give the related conclusions in Section 5.


## 2. Related Work

Since the relevant literature is quite extensive, our survey instead emphasizes the key concepts crucial to the establishment of the proposed framework.


### 2.1. Spectral Regression Algorithm

In the traditional spectral dimensionality reduction algorithms, seeking an embedding function which minimizes the objective function involves eigen-decomposition of dense matrices, which has the high computational cost in both time and memory. The SR algorithm uses the least squares method to get the best projection direction, instead of computing the density matrix of features, so it has much faster learning speed. An affinity graphG of both labeled and unlabeled points is constructed to find the intrinsic geometry structure and to learn the responses with the given data. Then, with these responses, the ordinary regression is applied to learning the embedding function.Given a training set withl labeled samples x1,x2,…,xl and (n-l) unlabeled samples xl+1,xl+2,…,xm, where the sample xi∈Rd belongs to one of c classes, let lk be the number of labeled samples in the kth class (the sum of lk is equal to l). The SR algorithm is summarized as follows.Step 1.
Constructing the adjacency graphG let X be the training set and let G denote a graph with n nodes, where the ith node corresponds to the sample xi. In order to model the local structure as well as the label information, the graph G will be constructed through the following three steps.(1)
Ifxi is among p-nearest neighbors of xj or xj is among p-nearest neighbors of xi, then nodes i and j are connected by an edge.(2)
Ifxi and xj are in the same class (i.e., same label), then nodes i and j are also connected by an edge.(3)
Otherwise, ifxi and xj are not in the same class, then the edge will be deleted between nodes i and j.Step 2.
Constructing the weight matrixW let W be the sparse symmetric n×n matrix, where Wij represents the weight of the edge joining vertices i and j.(1)
If there is no any edge between nodesi and j, then Wij=0.(2)
Otherwise, if bothxi and xj belong to the kth class, then Wij=1/lk, else Wij=δ·s(i,j),where δ  (0<δ≤1) is a given parameter to adjust the weight between supervised and unsupervised neighbor information. Therein, s(i,j) is a similarity evaluation function between xi and xj; we have two variations, the first one is simple-minded function s(i,j)=1 and the second one is heat kernel function:
(1)s(i,j)=exp(-∥xi-xj∥22σ2),
where σ∈ℝ.Step 3.
For eigen-decomposing letD be the n×n diagonal matrix, whose (i,i)th element is the sum of the ith column (or row) of W. Find y0,y1,…,yc-1, which are the largest c generalized eigenvectors of the eigenproblem
(2)Wy=λDy,
where the first eigenvector y0 is a vector of all ones with eigenvalue 1.Step 4.
Calculatec-1 vectors a1,…,am-1ϵℝd. ak  (k=1,…,c-1) is the solution of the regularized least square problem
(3)ak=argmina(∑i=1n(aTxi-yik)2+γ∥a∥2),
where yik is the ith element of yk.Step 5.
LetA be an d×(c-1) transformation matrix, where A=[a1,…,ac-1]. The testing samples or new sample can be embedded into c-1 dimensional subspace by
(4)x→z=ATx.Next, we briefly discuss the kernel spectral regression. If we choose a nonlinear function in RKHS; that is,yi=f(xi)=∑j=1nαjk(xi,xj), and K(xi,xj) is the Mercer kernel of RKHS ℋK. Equation (3) can be rewritten as
(5)minαk∑i=1n(Kαk-yik)2+α∥f∥K2,
where K is n×n gram matrix Kij=K(xi,xj). Find c-1 vectors α1,…,αc-1∈ℝn. αk  (k=1,…,c-1) is the solution of the following linear equations system:
(6)(K+αI)αk=yk.LetΘ=[α1,…,αc-1], Θ is a n×(c-1) transformation matrix. The samples can be embedded into c-1 dimensional subspace by
(7)x→z=ΘTK(·,x),
where K(·,x)=[K(x1,x),…,K(xn,x)]T.


### 2.2. Multiple Kernel Learning

MKL learns a kernel machine with multiple kernel functions or kernel matrices. Recent studies have shown that MKL not only increases the recognition accuracy but also enhances the interpretability of the resulting classifiers. Given a set of base kernel functions{km}m=1M, an ensemble kernel function k is defined by
(8)k(xi,xj)=∑m=1Mβmkm(xi,xj),βm≥0.
Consequently, an often-used MKL decision function derived from binary-class SVM is
(9)f(x)=∑i=1Nαiyik(xi,x)+b=∑i=1Nαiyi∑m=1Mβikm(xi,x)+b.
The training process of MKL generally optimizes over both the coefficients {(αi)}i=1Nand {(βm)}m=1M.In recent years, dimensionality reduction methods based on multiple kernels have been proposed to improve the performance of those using single kernel. In [12], kernel learning was first incorporated into DR methods. Then, a multiple kernel DR framework was designed in [13]. Recently, Zhu et al. proposed a dimensionality reduction method by Mixed Kernel Canonical Correlation Analysis (CCA) [14, 15]. In this method, the high dimensional data space is mapped into the reproducing kernel Hilbert space (RKHS) with a linear combination between a local kernel and a global kernel. Kernel CCA is further improved by performing Principal Component Analysis (PCA) followed by CCA for effective dimensionality reduction, which can be implemented in supervised learning, semisupervised learning, and transfer learning. Motivated by their work, we aim to incorporate the MKL optimization into SR to yield more flexible dimensionality reduction schemes.


## 2.1. Spectral Regression Algorithm

In the traditional spectral dimensionality reduction algorithms, seeking an embedding function which minimizes the objective function involves eigen-decomposition of dense matrices, which has the high computational cost in both time and memory. The SR algorithm uses the least squares method to get the best projection direction, instead of computing the density matrix of features, so it has much faster learning speed. An affinity graphG of both labeled and unlabeled points is constructed to find the intrinsic geometry structure and to learn the responses with the given data. Then, with these responses, the ordinary regression is applied to learning the embedding function.Given a training set withl labeled samples x1,x2,…,xl and (n-l) unlabeled samples xl+1,xl+2,…,xm, where the sample xi∈Rd belongs to one of c classes, let lk be the number of labeled samples in the kth class (the sum of lk is equal to l). The SR algorithm is summarized as follows.Step 1.
Constructing the adjacency graphG let X be the training set and let G denote a graph with n nodes, where the ith node corresponds to the sample xi. In order to model the local structure as well as the label information, the graph G will be constructed through the following three steps.(1)
Ifxi is among p-nearest neighbors of xj or xj is among p-nearest neighbors of xi, then nodes i and j are connected by an edge.(2)
Ifxi and xj are in the same class (i.e., same label), then nodes i and j are also connected by an edge.(3)
Otherwise, ifxi and xj are not in the same class, then the edge will be deleted between nodes i and j.Step 2.
Constructing the weight matrixW let W be the sparse symmetric n×n matrix, where Wij represents the weight of the edge joining vertices i and j.(1)
If there is no any edge between nodesi and j, then Wij=0.(2)
Otherwise, if bothxi and xj belong to the kth class, then Wij=1/lk, else Wij=δ·s(i,j),where δ  (0<δ≤1) is a given parameter to adjust the weight between supervised and unsupervised neighbor information. Therein, s(i,j) is a similarity evaluation function between xi and xj; we have two variations, the first one is simple-minded function s(i,j)=1 and the second one is heat kernel function:
(1)s(i,j)=exp(-∥xi-xj∥22σ2),
where σ∈ℝ.Step 3.
For eigen-decomposing letD be the n×n diagonal matrix, whose (i,i)th element is the sum of the ith column (or row) of W. Find y0,y1,…,yc-1, which are the largest c generalized eigenvectors of the eigenproblem
(2)Wy=λDy,
where the first eigenvector y0 is a vector of all ones with eigenvalue 1.Step 4.
Calculatec-1 vectors a1,…,am-1ϵℝd. ak  (k=1,…,c-1) is the solution of the regularized least square problem
(3)ak=argmina(∑i=1n(aTxi-yik)2+γ∥a∥2),
where yik is the ith element of yk.Step 5.
LetA be an d×(c-1) transformation matrix, where A=[a1,…,ac-1]. The testing samples or new sample can be embedded into c-1 dimensional subspace by
(4)x→z=ATx.Next, we briefly discuss the kernel spectral regression. If we choose a nonlinear function in RKHS; that is,yi=f(xi)=∑j=1nαjk(xi,xj), and K(xi,xj) is the Mercer kernel of RKHS ℋK. Equation (3) can be rewritten as
(5)minαk∑i=1n(Kαk-yik)2+α∥f∥K2,
where K is n×n gram matrix Kij=K(xi,xj). Find c-1 vectors α1,…,αc-1∈ℝn. αk  (k=1,…,c-1) is the solution of the following linear equations system:
(6)(K+αI)αk=yk.LetΘ=[α1,…,αc-1], Θ is a n×(c-1) transformation matrix. The samples can be embedded into c-1 dimensional subspace by
(7)x→z=ΘTK(·,x),
where K(·,x)=[K(x1,x),…,K(xn,x)]T.


## 2.2. Multiple Kernel Learning

MKL learns a kernel machine with multiple kernel functions or kernel matrices. Recent studies have shown that MKL not only increases the recognition accuracy but also enhances the interpretability of the resulting classifiers. Given a set of base kernel functions{km}m=1M, an ensemble kernel function k is defined by
(8)k(xi,xj)=∑m=1Mβmkm(xi,xj),βm≥0.
Consequently, an often-used MKL decision function derived from binary-class SVM is
(9)f(x)=∑i=1Nαiyik(xi,x)+b=∑i=1Nαiyi∑m=1Mβikm(xi,x)+b.
The training process of MKL generally optimizes over both the coefficients {(αi)}i=1Nand {(βm)}m=1M.In recent years, dimensionality reduction methods based on multiple kernels have been proposed to improve the performance of those using single kernel. In [12], kernel learning was first incorporated into DR methods. Then, a multiple kernel DR framework was designed in [13]. Recently, Zhu et al. proposed a dimensionality reduction method by Mixed Kernel Canonical Correlation Analysis (CCA) [14, 15]. In this method, the high dimensional data space is mapped into the reproducing kernel Hilbert space (RKHS) with a linear combination between a local kernel and a global kernel. Kernel CCA is further improved by performing Principal Component Analysis (PCA) followed by CCA for effective dimensionality reduction, which can be implemented in supervised learning, semisupervised learning, and transfer learning. Motivated by their work, we aim to incorporate the MKL optimization into SR to yield more flexible dimensionality reduction schemes.


## 3. The MKL-SR Framework

We first explain how to integrate MKL and SR for dimensionality reduction. Then, we propose an optimization procedure to complete the framework.


### 3.1. MKL-SR Model

Suppose that the ensemble kernelK in MKL-SR is generated by linearly combining the base kernels {km}m=1M as in (8). Selecting a nonlinear function in RKHS induced by the kernel function k(xi,xj)=∑m=1Mβmkm(xi,xj), we have yi=f(xi)=∑j=1n∑m=1Mαjβmkm(xi,xj). The constrained optimization problem for 1D MKL-SR is defined as follows:
(10)minα,β∑i,j=1N∥αT𝕂(i)β-αT𝕂(j)β∥2wij(11)Subjectto∑i,j=1N∥αT𝕂(i)β∥2dii=1(12)βm≥0,m=1,2,…,M,
where
(13)α=[α1,…,αn]T∈ℝn,β=[β1,…,βM]T∈ℝM,𝕂(i)=[k1(1,i)⋯kM(1,i)⋮⋱⋮k1(n,i)⋯kM(n,i)]∈ℝn×M.The additional constraints in (12) arise from the use of the ensemble kernel in (8) and are to ensure that the resulting kernel K in MKL-SR is a nonnegative combination of base kernels.Observe from (10) that the one-dimensional projection of MKL-SR is specified by a sample coefficient vector α and a kernel weight vector β. The two vectors, respectively, account for the relative importance among the samples and the base kernels in the construction of the projection. To generalize the formulation to uncover a multidimensional projection, we consider a set of c-1 sample coefficient vectors, denoted by
(14)A=[α1α2⋯αc-1].
The resulting projection will map samples to a (c-1)-dimensional euclidean space. Similar to the 1D case, a projected sample xi can be written as
(15)AT𝕂(i)β∈ℝc-1.The optimization problem (10) can now be extended to multidimensional MKL-SR as
(16)minA,β∑i,j=1N∥AT𝕂(i)β-AT𝕂(j)β∥2wij,(17)subjectto∑i,j=1N∥AT𝕂(i)β∥2dii=1,βm≥0,m=1,2,…,M.


### 3.2. Optimization Algorithm

Since direct optimization to (16) is difficult, we instead adopt an iterative, two-step strategy to alternately optimize A and β. At each iteration, one of A and β is optimized while the other is fixed, and then the roles of A and β are switched. Iterations are repeated until convergence or a maximum number of iteration is reached.


#### 3.2.1. On OptimizingA

We can indirectly utilize1D MKL-SR to solve multidimensional MKL-SR. By fixing β, the problem (10) can be transformed into the following optimal problem:
(18)α*=argmaxααT𝕂W𝕂TααT𝕂D𝕂Tα,
where 𝕂=[𝕂(1)β,…,𝕂(n)β]∈ℝn×n. The optimal α’s are the eigenvectors corresponding to the maximum eigenvalue of the eigenproblem
(19)𝕂W𝕂α=λ𝕂D𝕂α.
Consequently, the columns of the optimal A*=[α1,α2,…,αc-1] in (16) are the eigenvectors corresponding to the first c-1 smallest eigenvalues in (19).Solving the problem (19) directly involves eigen-decomposition of dense matrices, which has the high computational cost in both time and memory. In order to solve the eigenproblem in (19) efficiently, we use the following theorem.Theorem 1.
Lety be the eigenvector of the eigenproblem in (2) with eigenvalue λ. If 𝕂α=y; then α is the eigenvector of the eigenproblem in (19) with the same eigenvalue λ.Proof.
We haveWy=λDy. At the left side of (19), replacing 𝕂α by y, we have
(20)𝕂W𝕂α=𝕂Wy=𝕂λDy=λ𝕂Dy=λ𝕂D𝕂α.
Thus, α is the eigenvector of the eigenproblem (19) with the same eigenvalue λ.Theorem1 shows that, instead of solving the eigenproblem (19), the embedding functions can be acquired through two steps.(1)
Solve the eigenproblem in (2) to get y.(2)
Findα  which satisfies 𝕂α=y. Similar to SR, a possible way is to find α which can best fit the equation in the least squares sense as
(21)α=argminα(∑i=1n(αT𝕂(i)β-yi)2+γ∥α∥2),where yi is the ith element of y.Since the matrixD is guaranteed to be positive definite, the eigenproblem in (2) can be stably solved. Moreover, both D-W and D are sparse matrices. The top c eigenvectors of eigenproblem in (2) can be efficiently calculated with Lanczos algorithms [13]. In addition, the technique to solve the least square problem is already matured and there exist many efficient iterative algorithms that can handle very large scale least square problems.


#### 3.2.2. On Optimizingβ

By fixingA, the optimization problem (16) becomes
(22)minββT𝕂′TW𝕂′β(23)SubjecttoβT𝕂′TD𝕂′β=1,β≥0,
where 𝕂′=[AT𝕂(1),…,AT𝕂(n)]T∈ℝn×M.The additional constraintsβ≥0 cause the optimization to (22) to be no longer transformed into a generalized eigenvalue problem. It is actually a nonconvex quadratically constrained quadratic programming (QCQP) problem [13], which is a NP-hard problem. Thus, we instead consider solving its convex relaxation by adding an auxiliary variable T of size M×M as
(24)minβ,Btrace(𝕂′TW𝕂′T)(25)Subjecttotrace(𝕂′TD𝕂′T)=1,(26)emTβ≥0,m=1,2,…,M,(27)[1βTβT]≽0,
where em in (26) is a column vector whose elements are 0 except that its mth element is 1. To obtain the convex relaxation of the nonconvex QCQP problem (22), we relax the equation T=ββT to T≽ββT, which can be equivalently expressed by the constraint in (27) according to the Schur complement lemma [16]. The optimization problem (24) is a semidefinite programming (SDP), which can be efficiently solved. It can be note that the numbers of constraints and variables in (24) are linear and quadratic to M, respectively. In practice, the value of M is often small. Thus, the proposed MKL-SR algorithm listed in Algorithm 1 mainly includes a sequence of SR training.Algorithm 1:MKL-SR algorithm.
The training procedure of MKL-SR
Input: A set of training data, matricesW and D, a set of base kernels {km}m=1M
and parameterγ in (21).
Output: Sample coefficient vectorsA=[α1α2…αc-1];
Kernel weight vectorsβ;
Make an initial guess forA or β;
Computing the largestc generalized eigenvectors yk(k=1,…,c-1) of eigen-problem (2);
For  i←1,2,…,imax  do
(1) Compute𝕂;
(2)A is obtained by solving the least squares problem (21);
(3) Compute𝕂′TW𝕂′ in (24) and 𝕂′TD𝕂′ in (25);
(4)β is optimized by solving optimization problem (24) via SDP;
Return  A and β;


### 3.3. Novel Sample Embedding

After accomplishing the training procedure of MKL-SR, we can project a testing samplez into the learned subspace by
(28)z→AT𝕂(z)β,
where
(29)𝕂(z)∈ℝn×M,𝕂(z)(i,m)=km(xi,z).
Several algorithms such as the nearest neighbor rule or k-means clustering can be used to complete classification or clustering tasks. In the experiments of this paper, we specifically discuss the effectiveness of MKL-SR in different learning tasks, including unsupervised learning for clustering, supervised, and semisupervised learning for face recognition.


## 3.1. MKL-SR Model

Suppose that the ensemble kernelK in MKL-SR is generated by linearly combining the base kernels {km}m=1M as in (8). Selecting a nonlinear function in RKHS induced by the kernel function k(xi,xj)=∑m=1Mβmkm(xi,xj), we have yi=f(xi)=∑j=1n∑m=1Mαjβmkm(xi,xj). The constrained optimization problem for 1D MKL-SR is defined as follows:
(10)minα,β∑i,j=1N∥αT𝕂(i)β-αT𝕂(j)β∥2wij(11)Subjectto∑i,j=1N∥αT𝕂(i)β∥2dii=1(12)βm≥0,m=1,2,…,M,
where
(13)α=[α1,…,αn]T∈ℝn,β=[β1,…,βM]T∈ℝM,𝕂(i)=[k1(1,i)⋯kM(1,i)⋮⋱⋮k1(n,i)⋯kM(n,i)]∈ℝn×M.The additional constraints in (12) arise from the use of the ensemble kernel in (8) and are to ensure that the resulting kernel K in MKL-SR is a nonnegative combination of base kernels.Observe from (10) that the one-dimensional projection of MKL-SR is specified by a sample coefficient vector α and a kernel weight vector β. The two vectors, respectively, account for the relative importance among the samples and the base kernels in the construction of the projection. To generalize the formulation to uncover a multidimensional projection, we consider a set of c-1 sample coefficient vectors, denoted by
(14)A=[α1α2⋯αc-1].
The resulting projection will map samples to a (c-1)-dimensional euclidean space. Similar to the 1D case, a projected sample xi can be written as
(15)AT𝕂(i)β∈ℝc-1.The optimization problem (10) can now be extended to multidimensional MKL-SR as
(16)minA,β∑i,j=1N∥AT𝕂(i)β-AT𝕂(j)β∥2wij,(17)subjectto∑i,j=1N∥AT𝕂(i)β∥2dii=1,βm≥0,m=1,2,…,M.


## 3.2. Optimization Algorithm

Since direct optimization to (16) is difficult, we instead adopt an iterative, two-step strategy to alternately optimize A and β. At each iteration, one of A and β is optimized while the other is fixed, and then the roles of A and β are switched. Iterations are repeated until convergence or a maximum number of iteration is reached.


### 3.2.1. On OptimizingA

We can indirectly utilize1D MKL-SR to solve multidimensional MKL-SR. By fixing β, the problem (10) can be transformed into the following optimal problem:
(18)α*=argmaxααT𝕂W𝕂TααT𝕂D𝕂Tα,
where 𝕂=[𝕂(1)β,…,𝕂(n)β]∈ℝn×n. The optimal α’s are the eigenvectors corresponding to the maximum eigenvalue of the eigenproblem
(19)𝕂W𝕂α=λ𝕂D𝕂α.
Consequently, the columns of the optimal A*=[α1,α2,…,αc-1] in (16) are the eigenvectors corresponding to the first c-1 smallest eigenvalues in (19).Solving the problem (19) directly involves eigen-decomposition of dense matrices, which has the high computational cost in both time and memory. In order to solve the eigenproblem in (19) efficiently, we use the following theorem.Theorem 1.
Lety be the eigenvector of the eigenproblem in (2) with eigenvalue λ. If 𝕂α=y; then α is the eigenvector of the eigenproblem in (19) with the same eigenvalue λ.Proof.
We haveWy=λDy. At the left side of (19), replacing 𝕂α by y, we have
(20)𝕂W𝕂α=𝕂Wy=𝕂λDy=λ𝕂Dy=λ𝕂D𝕂α.
Thus, α is the eigenvector of the eigenproblem (19) with the same eigenvalue λ.Theorem1 shows that, instead of solving the eigenproblem (19), the embedding functions can be acquired through two steps.(1)
Solve the eigenproblem in (2) to get y.(2)
Findα  which satisfies 𝕂α=y. Similar to SR, a possible way is to find α which can best fit the equation in the least squares sense as
(21)α=argminα(∑i=1n(αT𝕂(i)β-yi)2+γ∥α∥2),where yi is the ith element of y.Since the matrixD is guaranteed to be positive definite, the eigenproblem in (2) can be stably solved. Moreover, both D-W and D are sparse matrices. The top c eigenvectors of eigenproblem in (2) can be efficiently calculated with Lanczos algorithms [13]. In addition, the technique to solve the least square problem is already matured and there exist many efficient iterative algorithms that can handle very large scale least square problems.


### 3.2.2. On Optimizingβ

By fixingA, the optimization problem (16) becomes
(22)minββT𝕂′TW𝕂′β(23)SubjecttoβT𝕂′TD𝕂′β=1,β≥0,
where 𝕂′=[AT𝕂(1),…,AT𝕂(n)]T∈ℝn×M.The additional constraintsβ≥0 cause the optimization to (22) to be no longer transformed into a generalized eigenvalue problem. It is actually a nonconvex quadratically constrained quadratic programming (QCQP) problem [13], which is a NP-hard problem. Thus, we instead consider solving its convex relaxation by adding an auxiliary variable T of size M×M as
(24)minβ,Btrace(𝕂′TW𝕂′T)(25)Subjecttotrace(𝕂′TD𝕂′T)=1,(26)emTβ≥0,m=1,2,…,M,(27)[1βTβT]≽0,
where em in (26) is a column vector whose elements are 0 except that its mth element is 1. To obtain the convex relaxation of the nonconvex QCQP problem (22), we relax the equation T=ββT to T≽ββT, which can be equivalently expressed by the constraint in (27) according to the Schur complement lemma [16]. The optimization problem (24) is a semidefinite programming (SDP), which can be efficiently solved. It can be note that the numbers of constraints and variables in (24) are linear and quadratic to M, respectively. In practice, the value of M is often small. Thus, the proposed MKL-SR algorithm listed in Algorithm 1 mainly includes a sequence of SR training.Algorithm 1:MKL-SR algorithm.
The training procedure of MKL-SR
Input: A set of training data, matricesW and D, a set of base kernels {km}m=1M
and parameterγ in (21).
Output: Sample coefficient vectorsA=[α1α2…αc-1];
Kernel weight vectorsβ;
Make an initial guess forA or β;
Computing the largestc generalized eigenvectors yk(k=1,…,c-1) of eigen-problem (2);
For  i←1,2,…,imax  do
(1) Compute𝕂;
(2)A is obtained by solving the least squares problem (21);
(3) Compute𝕂′TW𝕂′ in (24) and 𝕂′TD𝕂′ in (25);
(4)β is optimized by solving optimization problem (24) via SDP;
Return  A and β;


## 3.2.1. On OptimizingA

We can indirectly utilize1D MKL-SR to solve multidimensional MKL-SR. By fixing β, the problem (10) can be transformed into the following optimal problem:
(18)α*=argmaxααT𝕂W𝕂TααT𝕂D𝕂Tα,
where 𝕂=[𝕂(1)β,…,𝕂(n)β]∈ℝn×n. The optimal α’s are the eigenvectors corresponding to the maximum eigenvalue of the eigenproblem
(19)𝕂W𝕂α=λ𝕂D𝕂α.
Consequently, the columns of the optimal A*=[α1,α2,…,αc-1] in (16) are the eigenvectors corresponding to the first c-1 smallest eigenvalues in (19).Solving the problem (19) directly involves eigen-decomposition of dense matrices, which has the high computational cost in both time and memory. In order to solve the eigenproblem in (19) efficiently, we use the following theorem.Theorem 1.
Lety be the eigenvector of the eigenproblem in (2) with eigenvalue λ. If 𝕂α=y; then α is the eigenvector of the eigenproblem in (19) with the same eigenvalue λ.Proof.
We haveWy=λDy. At the left side of (19), replacing 𝕂α by y, we have
(20)𝕂W𝕂α=𝕂Wy=𝕂λDy=λ𝕂Dy=λ𝕂D𝕂α.
Thus, α is the eigenvector of the eigenproblem (19) with the same eigenvalue λ.Theorem1 shows that, instead of solving the eigenproblem (19), the embedding functions can be acquired through two steps.(1)
Solve the eigenproblem in (2) to get y.(2)
Findα  which satisfies 𝕂α=y. Similar to SR, a possible way is to find α which can best fit the equation in the least squares sense as
(21)α=argminα(∑i=1n(αT𝕂(i)β-yi)2+γ∥α∥2),where yi is the ith element of y.Since the matrixD is guaranteed to be positive definite, the eigenproblem in (2) can be stably solved. Moreover, both D-W and D are sparse matrices. The top c eigenvectors of eigenproblem in (2) can be efficiently calculated with Lanczos algorithms [13]. In addition, the technique to solve the least square problem is already matured and there exist many efficient iterative algorithms that can handle very large scale least square problems.


## 3.2.2. On Optimizingβ

By fixingA, the optimization problem (16) becomes
(22)minββT𝕂′TW𝕂′β(23)SubjecttoβT𝕂′TD𝕂′β=1,β≥0,
where 𝕂′=[AT𝕂(1),…,AT𝕂(n)]T∈ℝn×M.The additional constraintsβ≥0 cause the optimization to (22) to be no longer transformed into a generalized eigenvalue problem. It is actually a nonconvex quadratically constrained quadratic programming (QCQP) problem [13], which is a NP-hard problem. Thus, we instead consider solving its convex relaxation by adding an auxiliary variable T of size M×M as
(24)minβ,Btrace(𝕂′TW𝕂′T)(25)Subjecttotrace(𝕂′TD𝕂′T)=1,(26)emTβ≥0,m=1,2,…,M,(27)[1βTβT]≽0,
where em in (26) is a column vector whose elements are 0 except that its mth element is 1. To obtain the convex relaxation of the nonconvex QCQP problem (22), we relax the equation T=ββT to T≽ββT, which can be equivalently expressed by the constraint in (27) according to the Schur complement lemma [16]. The optimization problem (24) is a semidefinite programming (SDP), which can be efficiently solved. It can be note that the numbers of constraints and variables in (24) are linear and quadratic to M, respectively. In practice, the value of M is often small. Thus, the proposed MKL-SR algorithm listed in Algorithm 1 mainly includes a sequence of SR training.Algorithm 1:MKL-SR algorithm.
The training procedure of MKL-SR
Input: A set of training data, matricesW and D, a set of base kernels {km}m=1M
and parameterγ in (21).
Output: Sample coefficient vectorsA=[α1α2…αc-1];
Kernel weight vectorsβ;
Make an initial guess forA or β;
Computing the largestc generalized eigenvectors yk(k=1,…,c-1) of eigen-problem (2);
For  i←1,2,…,imax  do
(1) Compute𝕂;
(2)A is obtained by solving the least squares problem (21);
(3) Compute𝕂′TW𝕂′ in (24) and 𝕂′TD𝕂′ in (25);
(4)β is optimized by solving optimization problem (24) via SDP;
Return  A and β;


## 3.3. Novel Sample Embedding

After accomplishing the training procedure of MKL-SR, we can project a testing samplez into the learned subspace by
(28)z→AT𝕂(z)β,
where
(29)𝕂(z)∈ℝn×M,𝕂(z)(i,m)=km(xi,z).
Several algorithms such as the nearest neighbor rule or k-means clustering can be used to complete classification or clustering tasks. In the experiments of this paper, we specifically discuss the effectiveness of MKL-SR in different learning tasks, including unsupervised learning for clustering, supervised, and semisupervised learning for face recognition.


## 4. Experiments

We used seven datasets (ionosphere, letter, digit, and satellite) from the UCI machine learning repository to perform unsupervised learning task. For the letter and satellite data sets, we only used their first two classes. Several multiclass data sets were created from the digits data. The experiments on supervised and semisupervised classification were performed on the CMU PIE face data set and the extended Yale B data set [17, 18], respectively. All the face images are manually aligned and cropped. The pixel values are scaled to [0,1]. The basic information about these data sets is listed in Table 1. All the experiments have been performed in MATLAB 7.14.0 environment running in a 3.10 GHZ Intel Core i5-2400 with 3GB RAM.Table 1
Description of the datasets.
Data
Size (n)
Feature (d)
Class
Ionosphere
351
34
2
Letter A-B
1555
16
2
Satellite C1-C2
2236
36
2
Digits 0689
713
64
4
Digits 1279
718
64
4
CMU PIE
850
1024
5
Extended Yale B
2114
1024
38


### 4.1. Experiments on Unsupervised Learning

To validate that MKL-SR is effective for an unsupervised dimensionality reduction task, we applied the proposed algorithm as a tool to learn an appropriate kernel function for KSR. Each data set was reduced by SR, single kernel based SR, kernel principal component analysis (KPCA), and MKL-SR, respectively. The normalized cut spectral clustering (NC) algorithm was adopted to evaluate the clustering performance on the reduced data. We set the number of clusters equal to the true number of classes and compared the clusters generated by these algorithms with the true classes by computing the clustering accuracy measure as(30)Acc=1Nmax(Ck,Lm)(∑(Ck,Lm)T(Ck,Lm)),
where Ck denotes the kth cluster in the final results, Lm is the true mth class, and T(Ck,Lm) is the number of entities which belong to class m and are assigned to cluster k.To obtain stable results, for each data set, we computed the average results of each algorithm over 20 runs. For comparison, we also performed the NC algorithm in the original data space (Baseline). For SR, KSR, and MKL-SR, the dimension of the subspace is the number of categories. For KPCA, we tested its performance with all the possible dimensions and report the best result. For SR, KSR, and MKL-SR, we simply set the value of the parameterγ as 1. For KSR and KPCA, the Gaussian function exp(-b∥x-a∥2) with width 1 was selected. For MKL-SR, we use a linear kernel function, a polynomial kernel function, and a Gaussian kernel function.Table2 lists the mean of 20 different random repetitions as well as the standard deviation. From Table 2, we observe that the performance of kernel based algorithms is much better than SR, which indicates that the performance of linear DR algorithms can be improved by virtue of nonlinear kernel functions. MKL-SR significantly surpasses KSR and KPCA, which are single kernel based approaches. This is due to the fact that MKL-SR is able to learn a better kernel by MKL, which is considerably more effective than a single Gaussian kernel. The performance of KSR is very close to that of KPCA, but the number of reduced dimensions of KPCA has to be verified by testing many times. In addition to the fixed number of reduced dimensions, we also try to examine how the compared algorithms work when applying KPCA to obtain projected data of a varied number of dimensions. Thus, MKL-SR is easy to be implemented and has better performance than other algorithms.Table 2
Clustering accuracy (in percent) based on different DR methods.
Data
Baseline
SR
KSR
KPCA
MKL-SR
Ionosphere
75.1
±
0
.
8
80
.
6
±
0
.
5
85
.
6
±
0
.
4
85
.
2
±
0
.
3
89
.
5
±
0
.
2
Letter A-B
86.2
±
0
.
6
8
9
.
4
±
0
.
4
90
.
7
±
0
.
3
91
.
4
±
0
.
3
93
.
4
±
0
.
3
Satellite C1-C2
95.7
±
0
.
7
9
6
.
3
±
0
.
2
97
.
3
±
0
.
3
9
7
.
3
±
0
.
3
9
8
.
7
±
0
.
2
Digits 0689
90
.
3
±
0
.
4
9
2
.
5
±
0
.
3
9
3
.
6
±
0
.
3
9
4
.
6
±
0
.
2
9
5
.
6
±
0
.
2
Digits 1279
93
.
4
±
0
.
2
9
4
.
3
±
0
.
2
9
5
.
7
±
0
.
3
9
4
.
5
±
0
.
2
9
6
.
8
±
0
.
2


### 4.2. Experiments on Supervised Learning

In this experiment, we mainly compared MKL-SR with the following approaches: KPCA, LDA, SR, and KSR. In order to evaluate the performance of these algorithms, we performed the SVM algorithm in the original face image space (baseline) and KPCA, LDA, SR, KSR, and MKL-SR subspace. The kernels and parameters are set in the same way as in the unsupervised learning. From each class of the CMU PIE face data sets, we randomly selectedl (the number of training samples per class) samples for training.For each givenl, we averaged the results over 30 random splits and computed the mean as well as the standard deviation, which are listed in Table 3. As can be seen from Table 3, the performance of KPCA and LDA is even worse than that of the baseline method, which resulted from the limitation of KPCA and LDA. As is well known that KPCA is unsupervised, thus it cannot effectively exploit the supervised information, which results in the worst performance in supervised case. LDA does not utilize the regularization approach to control the model complexity. Thus, it cannot solve the over-fitting problem in small sample size case. In contrast, SR, KSR, and MKL-SR take advantage of the Tikhonov regularizer to improve the smoothness of projection functions, and they can perform better than KPCA and LDA. By substituting the nonlinear embedding functions with the linear ones, KSR and MKL-SR all outperform SR. The performance of MKL-SR is better than that of KSR based on a single kernel, which indicates that MKL-SR can select an appropriate kernel and validates the effectiveness of our method.Table 3
Recognition accuracy rates on PIE (mean ± std-dev%).
Train size
Baseline
KPCA
LDA
SR
KSR
MKL-SR
5
×
68
68.0
±
1.7
40.2
±
0.3
58.2
±
1.5
71.9
±
1.4
72.4
±
0.7
79.2
±
0.8
10
×
68
83.2
±
0.7
51.3
±
0.3
70.3
±
1.3
85.0
±
1.3
87.2
±
0.4
90.2
±
0.5
20
×
68
91.1
±
0.6
68.7
±
0.3
79.5
±
0.8
92.3
±
0.7
94.0
±
0.3
95.7
±
0.3
30
×
68
93.4
±
0.6
70.2
±
0.4
89.1
±
0.5
93.4
±
0.7
95.9
±
0.2
96.4
±
0.3
40
×
68
94.6
±
0.6
82.3
±
0.4
91.8
±
0.4
94.8
±
0.4
96.6
±
0.2
97.9
±
0.2The key parameter in MKL-SR is the regularization parameterγ≥0 which controls the smoothness of the embedding function based on multiple kernels. Next, we discuss the impact of parameter γ on the performance of MKL-SR. Figure 1 shows the performance of MKL-SR as a function of the parameter γ. For convenience, the X-axis is plotted as γ/(1+γ) which is strictly in the interval [0,1]. As can be seen from Figure 1, MKL-SR obtains the best performance near the middle of the interval. When γ/(1+γ) decreases to zero or increases to one, the performance of MKL-SR decreases sharply. Fortunately, good performance can be achieved over a wide range of γ, which shows that the parameter selection is not a crucial problem in MKL-SR algorithm. In reality, we can use cross validation to verify the best parameter or simply select a value between 0.1 and 1.Performance of MKL-SR with respect toγ/(1+γ) on PIE. (a) l=10. (b) l=30.
(a)
(b)


### 4.3. Experiments on Semisupervised Learning

In the semisupervised case, we compared the performance of MKL-SR with KPCA and semisupervised KSR. For comparison, we performed the SVM algorithm in the original face image space (baseline), KPCA, and semisupervised KSR and MKL-SR subspace. For KSR and MKL-SR, we simply set the value of the parameterγ as 1. In the semisupervised MKL-SR, the parameter δ  (0<δ≤1) was selected by cross validation. The kernels and parameters are set in the same way as in the unsupervised learning. For the extended Yale B face data set, a random subset with l(=5,10,20,30,40) images per individual was first taken to form the training set and the rest of the data set was used to be the testing set. In the training set, we only use one half data as labeled data and the rest as unlabeled data. KPCA only uses unlabeled data and the SVM algorithm is also performed on the reduced data based on KPCA. KSR and MKL-SR use both labeled and unlabeled data. The p is set to be 7 for the p-nearest neighbor graph over all the training samples in KSR and MKL-SR.We average the classification accuracy over 30 random splits for each givenl. The mean as well as the standard deviation is shown in Table 4. From Table 4, we can observe that KSR and MKL-SR can efficiently exploit both labeled and unlabeled data to discover the intrinsic geometry structure in the data; that is, the reduced data can preserve the original intrinsic geometry structure very well. Thus, they outperform the baseline method and KPCA, which cannot utilize all the available data. The performance of MKL-SR is much better than that of KSR, which indicates that the final kernel matrix learned by MKL-SR is still better than the one based on a single kernel in the semisupervised case. Overall, the proposed MKL-SR algorithm can achieve better performance in the supervised, semisupervised, and unsupervised case.Table 4
Recognition accuracy rates on Extended Yale B (mean ± std-dev%).
The number of labeled samples
Baseline
KPCA
Semi-supervised KSR
Semisupervised MKL-SR
l
=
95
50.8
±
2
.
3
57.4
±
2
.
0
61.5
±
1.7
73.2
±
1.5
l
=
190
69.3
±
1.4
73.7
±
1
.
4
76.3
±
1.3
80.4
±
0.9
l
=
380
83.2
±
0.6
85.8
±
0.7
89.7
±
0.3
92.6
±
0.3
l
=
570
90.1
±
0.3
92.5
±
0.3
95.7
±
0.2
96.3
±
0.2
l
=
760
91.6
±
0.2
95.4
±
0.3
97.2
±
0.2
97.9
±
0.2


## 4.1. Experiments on Unsupervised Learning

To validate that MKL-SR is effective for an unsupervised dimensionality reduction task, we applied the proposed algorithm as a tool to learn an appropriate kernel function for KSR. Each data set was reduced by SR, single kernel based SR, kernel principal component analysis (KPCA), and MKL-SR, respectively. The normalized cut spectral clustering (NC) algorithm was adopted to evaluate the clustering performance on the reduced data. We set the number of clusters equal to the true number of classes and compared the clusters generated by these algorithms with the true classes by computing the clustering accuracy measure as(30)Acc=1Nmax(Ck,Lm)(∑(Ck,Lm)T(Ck,Lm)),
where Ck denotes the kth cluster in the final results, Lm is the true mth class, and T(Ck,Lm) is the number of entities which belong to class m and are assigned to cluster k.To obtain stable results, for each data set, we computed the average results of each algorithm over 20 runs. For comparison, we also performed the NC algorithm in the original data space (Baseline). For SR, KSR, and MKL-SR, the dimension of the subspace is the number of categories. For KPCA, we tested its performance with all the possible dimensions and report the best result. For SR, KSR, and MKL-SR, we simply set the value of the parameterγ as 1. For KSR and KPCA, the Gaussian function exp(-b∥x-a∥2) with width 1 was selected. For MKL-SR, we use a linear kernel function, a polynomial kernel function, and a Gaussian kernel function.Table2 lists the mean of 20 different random repetitions as well as the standard deviation. From Table 2, we observe that the performance of kernel based algorithms is much better than SR, which indicates that the performance of linear DR algorithms can be improved by virtue of nonlinear kernel functions. MKL-SR significantly surpasses KSR and KPCA, which are single kernel based approaches. This is due to the fact that MKL-SR is able to learn a better kernel by MKL, which is considerably more effective than a single Gaussian kernel. The performance of KSR is very close to that of KPCA, but the number of reduced dimensions of KPCA has to be verified by testing many times. In addition to the fixed number of reduced dimensions, we also try to examine how the compared algorithms work when applying KPCA to obtain projected data of a varied number of dimensions. Thus, MKL-SR is easy to be implemented and has better performance than other algorithms.Table 2
Clustering accuracy (in percent) based on different DR methods.
Data
Baseline
SR
KSR
KPCA
MKL-SR
Ionosphere
75.1
±
0
.
8
80
.
6
±
0
.
5
85
.
6
±
0
.
4
85
.
2
±
0
.
3
89
.
5
±
0
.
2
Letter A-B
86.2
±
0
.
6
8
9
.
4
±
0
.
4
90
.
7
±
0
.
3
91
.
4
±
0
.
3
93
.
4
±
0
.
3
Satellite C1-C2
95.7
±
0
.
7
9
6
.
3
±
0
.
2
97
.
3
±
0
.
3
9
7
.
3
±
0
.
3
9
8
.
7
±
0
.
2
Digits 0689
90
.
3
±
0
.
4
9
2
.
5
±
0
.
3
9
3
.
6
±
0
.
3
9
4
.
6
±
0
.
2
9
5
.
6
±
0
.
2
Digits 1279
93
.
4
±
0
.
2
9
4
.
3
±
0
.
2
9
5
.
7
±
0
.
3
9
4
.
5
±
0
.
2
9
6
.
8
±
0
.
2


## 4.2. Experiments on Supervised Learning

In this experiment, we mainly compared MKL-SR with the following approaches: KPCA, LDA, SR, and KSR. In order to evaluate the performance of these algorithms, we performed the SVM algorithm in the original face image space (baseline) and KPCA, LDA, SR, KSR, and MKL-SR subspace. The kernels and parameters are set in the same way as in the unsupervised learning. From each class of the CMU PIE face data sets, we randomly selectedl (the number of training samples per class) samples for training.For each givenl, we averaged the results over 30 random splits and computed the mean as well as the standard deviation, which are listed in Table 3. As can be seen from Table 3, the performance of KPCA and LDA is even worse than that of the baseline method, which resulted from the limitation of KPCA and LDA. As is well known that KPCA is unsupervised, thus it cannot effectively exploit the supervised information, which results in the worst performance in supervised case. LDA does not utilize the regularization approach to control the model complexity. Thus, it cannot solve the over-fitting problem in small sample size case. In contrast, SR, KSR, and MKL-SR take advantage of the Tikhonov regularizer to improve the smoothness of projection functions, and they can perform better than KPCA and LDA. By substituting the nonlinear embedding functions with the linear ones, KSR and MKL-SR all outperform SR. The performance of MKL-SR is better than that of KSR based on a single kernel, which indicates that MKL-SR can select an appropriate kernel and validates the effectiveness of our method.Table 3
Recognition accuracy rates on PIE (mean ± std-dev%).
Train size
Baseline
KPCA
LDA
SR
KSR
MKL-SR
5
×
68
68.0
±
1.7
40.2
±
0.3
58.2
±
1.5
71.9
±
1.4
72.4
±
0.7
79.2
±
0.8
10
×
68
83.2
±
0.7
51.3
±
0.3
70.3
±
1.3
85.0
±
1.3
87.2
±
0.4
90.2
±
0.5
20
×
68
91.1
±
0.6
68.7
±
0.3
79.5
±
0.8
92.3
±
0.7
94.0
±
0.3
95.7
±
0.3
30
×
68
93.4
±
0.6
70.2
±
0.4
89.1
±
0.5
93.4
±
0.7
95.9
±
0.2
96.4
±
0.3
40
×
68
94.6
±
0.6
82.3
±
0.4
91.8
±
0.4
94.8
±
0.4
96.6
±
0.2
97.9
±
0.2The key parameter in MKL-SR is the regularization parameterγ≥0 which controls the smoothness of the embedding function based on multiple kernels. Next, we discuss the impact of parameter γ on the performance of MKL-SR. Figure 1 shows the performance of MKL-SR as a function of the parameter γ. For convenience, the X-axis is plotted as γ/(1+γ) which is strictly in the interval [0,1]. As can be seen from Figure 1, MKL-SR obtains the best performance near the middle of the interval. When γ/(1+γ) decreases to zero or increases to one, the performance of MKL-SR decreases sharply. Fortunately, good performance can be achieved over a wide range of γ, which shows that the parameter selection is not a crucial problem in MKL-SR algorithm. In reality, we can use cross validation to verify the best parameter or simply select a value between 0.1 and 1.Performance of MKL-SR with respect toγ/(1+γ) on PIE. (a) l=10. (b) l=30.
(a)
(b)


## 4.3. Experiments on Semisupervised Learning

In the semisupervised case, we compared the performance of MKL-SR with KPCA and semisupervised KSR. For comparison, we performed the SVM algorithm in the original face image space (baseline), KPCA, and semisupervised KSR and MKL-SR subspace. For KSR and MKL-SR, we simply set the value of the parameterγ as 1. In the semisupervised MKL-SR, the parameter δ  (0<δ≤1) was selected by cross validation. The kernels and parameters are set in the same way as in the unsupervised learning. For the extended Yale B face data set, a random subset with l(=5,10,20,30,40) images per individual was first taken to form the training set and the rest of the data set was used to be the testing set. In the training set, we only use one half data as labeled data and the rest as unlabeled data. KPCA only uses unlabeled data and the SVM algorithm is also performed on the reduced data based on KPCA. KSR and MKL-SR use both labeled and unlabeled data. The p is set to be 7 for the p-nearest neighbor graph over all the training samples in KSR and MKL-SR.We average the classification accuracy over 30 random splits for each givenl. The mean as well as the standard deviation is shown in Table 4. From Table 4, we can observe that KSR and MKL-SR can efficiently exploit both labeled and unlabeled data to discover the intrinsic geometry structure in the data; that is, the reduced data can preserve the original intrinsic geometry structure very well. Thus, they outperform the baseline method and KPCA, which cannot utilize all the available data. The performance of MKL-SR is much better than that of KSR, which indicates that the final kernel matrix learned by MKL-SR is still better than the one based on a single kernel in the semisupervised case. Overall, the proposed MKL-SR algorithm can achieve better performance in the supervised, semisupervised, and unsupervised case.Table 4
Recognition accuracy rates on Extended Yale B (mean ± std-dev%).
The number of labeled samples
Baseline
KPCA
Semi-supervised KSR
Semisupervised MKL-SR
l
=
95
50.8
±
2
.
3
57.4
±
2
.
0
61.5
±
1.7
73.2
±
1.5
l
=
190
69.3
±
1.4
73.7
±
1
.
4
76.3
±
1.3
80.4
±
0.9
l
=
380
83.2
±
0.6
85.8
±
0.7
89.7
±
0.3
92.6
±
0.3
l
=
570
90.1
±
0.3
92.5
±
0.3
95.7
±
0.2
96.3
±
0.2
l
=
760
91.6
±
0.2
95.4
±
0.3
97.2
±
0.2
97.9
±
0.2


## 5. Conclusion

In this paper, we propose a new dimensionality reduction framework called MKL-SR. By means of SR, we solve the out-of-sample extension problem by seeking an embedding function in RKHS induced by multiple kernels. Thus, this method can not only construct the nonlinear embedding function in the form of convex combination of base kernels but also improve the performance of single kernel based SR in the supervised, semisupervised, and unsupervised case. Experimental results validate the effectiveness and efficiency of the MKL-SR algorithm. In the near future, we will further explore how to integrate different MKL methods into our model.



---

*Source: 427462-2013-10-23.xml*