jmlr jmlr2011 jmlr2011-66 jmlr2011-66-reference knowledge-graph by maker-knowledge-mining

66 jmlr-2011-Multiple Kernel Learning Algorithms

Source: pdf

Author: Mehmet Gönen, Ethem Alpaydın

Abstract: In recent years, several methods have been proposed to combine multiple kernels instead of using a single one. These different kernels may correspond to using different notions of similarity or may be using information coming from multiple sources (different representations or different feature subsets). In trying to organize and highlight the similarities and differences between them, we give a taxonomy of and review several multiple kernel learning algorithms. We perform experiments on real data sets for better illustration and comparison of existing algorithms. We see that though there may not be large differences in terms of accuracy, there is difference between them in complexity as given by the number of stored support vectors, the sparsity of the solution as given by the number of used kernels, and training time complexity. We see that overall, using multiple kernels instead of a single one is useful and believe that combining kernels in a nonlinear or data-dependent way seems more promising than linear combination in fusing information provided by simple linear kernels, whereas linear methods are more reasonable when combining complex Gaussian kernels. Keywords: support vector machines, kernel machines, multiple kernel learning

reference text

Pavlidis et al. (2001) Ben-Hur and Noble (2005) de Diego et al. (2004, 2010a) Moguerza et al. (2004); de Diego et al. (2010a) Tanabe et al. (2008) Qiu and Lane (2009) Qiu and Lane (2009) Lanckriet et al. (2004a) Igel et al. (2007) Cortes et al. (2010a) Lanckriet et al. (2004a) Kandola et al. (2002) Cortes et al. (2010a) He et al. (2008) Tanabe et al. (2008) Ying et al. (2009) Lanckriet et al. (2002) Qiu and Lane (2005) Conforti and Guido (2010) Lanckriet et al. (2004a) Fung et al. (2004) Tsuda et al. (2004) Qiu and Lane (2005) Varma and Ray (2007) Varma and Ray (2007) Cortes et al. (2009) Kloft et al. (2010a) Xu et al. (2010b) Kloft et al. (2010b); Xu et al. (2010a) Conforti and Guido (2010) Learning Method Fixed Fixed Heuristic Heuristic Heuristic Heuristic Heuristic Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Functional Form Lin. (unwei.) Lin. (unwei.) Nonlinear Data-dep. Lin. (convex) Lin. (convex) Lin. (convex) Lin. (linear) Lin. (linear) Lin. (linear) Lin. (conic) Lin. (conic) Lin. (conic) Lin. (convex) Lin. (convex) Lin. (convex) Lin. (linear) Lin. (linear) Lin. (linear) Lin. (conic) Lin. (conic) Lin. (conic) Lin. (conic) Lin. (conic) Lin. (conic) Lin. (conic) Lin. (conic) Lin. (conic) Lin. (conic) Lin. (conic) Target Function None None Val. error None None None None Similarity Similarity Similarity Similarity Similarity Similarity Similarity Similarity Similarity Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Table 1: Representative MKL algorithms. Training Method 1-step (seq.) 1-step (seq.) 2-step 1-step (seq.) 1-step (seq.) 1-step (seq.) 1-step (seq.) 1-step (seq.) 1-step (seq.) 1-step (seq.) 1-step (seq.) 1-step (seq.) 1-step (seq.) 1-step (seq.) 1-step (seq.) 1-step (seq.) 1-step (seq.) 1-step (seq.) 1-step (seq.) 1-step (seq.) 2-step 2-step 1-step (seq.) 1-step (sim.) 2-step 2-step 2-step 1-step (sim.) 2-step 1-step (seq.) Base Learner SVM SVM SVM SVM SVM SVR SVM SVM SVM SVM SVM SVM SVM SVM SVM SVM SVM SVR SVM SVM KFDA KFDA SVR SVM SVM KRR SVM SVM SVM SVM Computational Complexity QP QP QP QP QP QP QP SDP+QP Grad.+QP Mat. Inv.+QP QCQP+QP QP+QP QP+QP QP+QP QP+QP Grad.+QP SDP+QP SDP+QP SDP+QP QCQP+QP QP+Mat. Inv. Grad.+Mat. Inv. QCQP+QP SOCP Grad.+QP Grad.+Mat. Inv. Newton+QP Grad. Analytical+QP QCQP+QP 2218 2219 3.12 3.11 3.10 3.9 Sec. 3.8 Learning Method Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Optim. Bayesian Bayesian Bayesian Boosting Boosting Boosting Functional Form Lin. (convex) Lin. (convex) Lin. (convex) Lin. (convex) Lin. (convex) Lin. (convex) Lin. (convex) Lin. (convex) Lin. (convex) Lin. (convex) Lin. (convex) Nonlinear Nonlinear Nonlinear Data-dep. Data-dep. Data-dep. Data-dep. Lin. (conic) Lin. (conic) Data-dep. Data-dep. Lin. (conic) Lin. (linear) Target Function Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Str. risk Likelihood Likelihood Likelihood Str. risk Str. risk Str. risk Training Method 2-step 1-step (sim.) 2-step 1-step (seq.) 1-step (seq.) 1-step (seq.) 1-step (seq.) 2-step 2-step 2-step 1-step (seq.) 1-step (sim.) 2-step 2-step 1-step (sim.) 2-step 2-step 2-step Inference Inference Inference P × 1-step P × 1-step P × 1-step Table 2: Representative MKL algorithms (continued). Representative Bousquet and Herrmann (2003) Bach et al. (2004) Sonnenburg et al. (2006a,b) Kim et al. (2006) Ye et al. (2007a) Ye et al. (2007b) Ye et al. (2008) Rakotomamonjy et al. (2007, 2008) Chapelle and Rakotomamonjy (2008) Kloft et al. (2010b); Xu et al. (2010a) Conforti and Guido (2010) Lee et al. (2007) Varma and Babu (2009) Cortes et al. (2010b) Lewis et al. (2006b) G¨ nen and Alpaydın (2008) o Yang et al. (2009a) Yang et al. (2009b, 2010) Girolami and Rogers (2005) Girolami and Zhong (2007) Christoudias et al. (2009) Bennett et al. (2002) Crammer et al. (2003) Bi et al. (2004) Base Learner SVM SVM SVM KFDA RKDA RKDA RKDA SVM SVM SVM SVM SVM SVM KRR SVM SVM SVM SVM KRR GP GP KRR Percept. SVM Computational Complexity Grad.+QP SOCP LP+QP SDP+Mat. Inv. SDP+Mat. Inv. QCQP+Mat. Inv. SILP+Mat. Inv. Grad.+QP QP+QP Analytical+QP QCQP+QP QP Grad.+QP Grad.+Mat. Inv. QP Grad.+QP Grad.+QP SILP+QP Approximation Approximation Approximation Mat. Inv. Eigenvalue Prob. QP M ULTIPLE K ERNEL L EARNING A LGORITHMS ¨ G ONEN AND A LPAYDIN 3.2 Heuristic Approaches de Diego et al. (2004, 2010a) deﬁne a functional form of combining two kernels: 1 Kη = (K1 + K2 ) + f (K1 − K2 ) 2 where the term f (K1 − K2 ) represents the difference of information between what K1 and K2 provide for classiﬁcation. They investigate three different functions: 1 kη (xi , x j ) = (k1 (x1 , x1 ) + k2 (x2 , x2 )) + τyi y j |k1 (x1 , x1 ) − k2 (x2 , x2 )| i j i j i j i j 2 1 kη (xi , x j ) = (k1 (x1 , x1 ) + k2 (x2 , x2 )) + τyi y j (k1 (x1 , x1 ) − k2 (x2 , x2 )) i j i j i j i j 2 1 Kη = (K1 + K2 ) + τ(K1 − K2 )(K1 − K2 ) 2 where τ ∈ R+ is the parameter that represents the weight assigned to the term f (K1 − K2 ) (selected through cross-validation) and the ﬁrst two functions do not ensure having positive semideﬁnite kernel matrices. It is also possible to combine more than two kernel functions by applying these rules recursively. Moguerza et al. (2004) and de Diego et al. (2010a) propose a matrix functional form of combining kernels: P kη (xi , x j ) = ∑ ηm (xi , x j )km (xm , xm ) i j m=1 where ηm (·, ·) assigns a weight to km (·, ·) according to xi and x j . They propose different heuristics to estimate the weighing function values using conditional class probabilities, Pr(yi = y j |xi ) and Pr(y j = yi |x j ), calculated with a nearest-neighbor approach. However, each kernel function corresponds to a different neighborhood and ηm (·, ·) is calculated on the neighborhood induced by km (·, ·). For an unlabeled data instance x, they take its class label once as +1 and once as −1, calculate the discriminant values f (x|y = +1) and f (x|y = −1), and assign it to the class that has more conﬁdence in its decision (i.e., by selecting the class label with greater y f (x|y) value). de Diego et al. (2010b) use this method to fuse information from several feature representations for face veriﬁcation. Combining kernels in a data-dependent manner outperforms the classical fusion techniques such as feature-level and score-level methods in their experiments. We can also use a linear combination instead of a data-dependent combination and formulate the combined kernel function as follows: P kη (xi , x j ) = ∑ ηm km (xm , xm ) i j m=1 where we select the kernel weights by looking at the performance values obtained by each kernel separately. For example, Tanabe et al. (2008) propose the following rule in order to choose the kernel weights for classiﬁcation problems: ηm = P πm − δ ∑ (πh − δ) h=1 2220 M ULTIPLE K ERNEL L EARNING A LGORITHMS where πm is the accuracy obtained using only Km , and δ is the threshold that should be less than or equal to the minimum of the accuracies obtained from single-kernel learners. Qiu and Lane (2009) propose two simple heuristics to select the kernel weights for regression problems: ηm = Rm ∀m P ∑ Rh h=1 P ηm = ∑ Mh − Mm h=1 ∀m P (P − 1) ∑ Mh h=1 where Rm is the Pearson correlation coefﬁcient between the true outputs and the predicted labels generated by the regressor using the kernel matrix Km , and Mm is the mean square error generated by the regressor using the kernel matrix Km . These three heuristics ﬁnd a convex combination of the input kernels as the combined kernel. Cristianini et al. (2002) deﬁne a notion of similarity between two kernels called kernel alignment. The empirical alignment of two kernels is calculated as follows: K1 , K2 F K1 , K1 F K2 , K2 A(K1 , K2 ) = F where K1 , K2 F = ∑N ∑N k1 (x1 , x1 )k2 (x2 , x2 ). This similarity measure can be seen as the cosine i=1 j=1 j i j i of the angle between K1 and K2 . yy⊤ can be deﬁned as ideal kernel for a binary classiﬁcation task, and the alignment between a kernel and the ideal kernel becomes A(K, yy⊤ ) = K, yy⊤ K, K F F ⊤ , yy⊤ yy = F K, yy⊤ F . N K, K F Kernel alignment has one key property due to concentration (i.e., the probability of deviation from the mean decays exponentially), which enables us to keep high alignment on a test set when we optimize it on a training set. Qiu and Lane (2009) propose the following simple heuristic for classiﬁcation problems to select the kernel weights using kernel alignment: ηm = A(Km , yy⊤ ) P ∑ A(Kh , yy⊤ ) ∀m h=1 where we obtain the combined kernel as a convex combination of the input kernels. 2221 (2) ¨ G ONEN AND A LPAYDIN 3.3 Similarity Optimizing Linear Approaches with Arbitrary Kernel Weights Lanckriet et al. (2004a) propose to optimize the kernel alignment as follows: maximize A(Ktra , yy⊤ ) η with respect to Kη ∈ SN subject to tr Kη = 1 Kη 0 where the trace of the combined kernel matrix is arbitrarily set to 1. This problem can be converted into the following SDP problem using arbitrary kernel weights in the combination: P ∑ ηm Ktra , yy⊤ m maximize m=1 F with respect to η ∈ R , A ∈ S P subject to tr (A) ≤ 1  A    P ∑ ηm Km N P ∑ m=1 0   I m=1 P ∑ ηm Km  ηm K⊤  m 0. m=1 Igel et al. (2007) propose maximizing the kernel alignment using gradient-based optimization. They calculate the gradients with respect to the kernel parameters as ∂A(Kη ∂ηm , yy⊤ ) = ∂Kη , yy⊤ ∂ηm Kη , Kη F N F − Kη , yy⊤ Kη , Kη F ∂Kη , Kη ∂ηm F . 3 F In a transcription initiation site detection task for bacterial genes, they obtain better results by optimizing the kernel weights of the combined kernel function that is composed of six sequence kernels, using the gradient above. Cortes et al. (2010a) give a different kernel alignment deﬁnition, which they call centered-kernel alignment. The empirical centered-alignment of two kernels is calculated as follows: CA(K1 , K2 ) = Kc , Kc F 2 1 Kc , Kc F Kc , Kc 1 1 2 2 F where Kc is the centered version of K and can be calculated as Kc = K − 1 1 1 ⊤ 11 K − K11⊤ + 2 (1⊤ K1)11⊤ N N N 2222 M ULTIPLE K ERNEL L EARNING A LGORITHMS where 1 is the vector of ones with proper dimension. Cortes et al. (2010a) also propose to optimize the centered-kernel alignment as follows: maximize CA(Kη , yy⊤ ) with respect to η ∈ M where M = {η : η 2 (3) = 1}. This optimization problem (3) has an analytical solution: η= M−1 a M−1 a 2 (4) c ⊤ P where M = { Kc , Kc F }P m m,h=1 and a = { Km , yy F }m=1 . h 3.4 Similarity Optimizing Linear Approaches with Nonnegative Kernel Weights Kandola et al. (2002) propose to maximize the alignment between a nonnegative linear combination of kernels and the ideal kernel. The alignment can be calculated as follows: P ∑ ηm Km , yy⊤ F m=1 A(Kη , yy⊤ ) = . P P ∑ ∑ ηm ηh Km , Kh N F m=1 h=1 We should choose the kernel weights that maximize the alignment and this idea can be cast into the following optimization problem: maximize A(Kη , yy⊤ ) with respect to η ∈ RP + and this problem is equivalent to P maximize ∑ ηm Km , yy⊤ F m=1 with respect to η ∈ RP + P subject to P ∑ ∑ ηm ηh Km , Kh F = c. m=1 h=1 Using the Lagrangian function, we can convert it into the following unconstrained optimization problem: P maximize ∑ ηm Km , yy⊤ m=1 P F −µ with respect to η ∈ RP . + 2223 P ∑ ∑ ηm ηh m=1 h=1 Km , Kh F −c ¨ G ONEN AND A LPAYDIN Kandola et al. (2002) take µ = 1 arbitrarily and add a regularization term to the objective function in order to prevent overﬁtting. The resulting QP is very similar to the hard margin SVM optimization problem and is expected to give sparse kernel combination weights: P maximize ∑ ηm P Km , yy⊤ F m=1 with respect to η ∈ − P ∑ ∑ ηm ηh Km , Kh m=1 h=1 F −λ P ∑ η2 m m=1 RP + where we only learn the kernel combination weights. Lanckriet et al. (2004a) restrict the kernel weights to be nonnegative and their SDP formulation reduces to the following QCQP problem: P maximize ∑ ηm Ktra , yy⊤ m F m=1 with respect to η ∈ RP + P P subject to ∑ ∑ ηm ηh Km , Kh F m=1 h=1 ≤ 1. (5) Cortes et al. (2010a) also restrict the kernel weights to be nonnegative by changing the deﬁnition of M in (3) to {η : η 2 = 1, η ∈ RP } and obtain the following QP: + minimize v⊤ Mv − 2v⊤ a with respect to v ∈ RP + (6) where the kernel weights are given by η = v/ v 2 . 3.5 Similarity Optimizing Linear Approaches with Kernel Weights on a Simplex He et al. (2008) choose to optimize the distance between the combined kernel matrix and the ideal kernel, instead of optimizing the kernel alignment measure, using the following optimization problem: minimize Kη − yy⊤ , Kη − yy⊤ with respect to η ∈ RP + 2 F P subject to ∑ ηm = 1. m=1 This problem is equivalent to P minimize with respect to subject to ∑ P P ∑ ηm ηh Km , Kh m=1 h=1 η ∈ RP + P ∑ ηm = 1. F −2 ∑ ηm Km , yy⊤ F m=1 (7) m=1 2224 M ULTIPLE K ERNEL L EARNING A LGORITHMS Nguyen and Ho (2008) propose another quality measure called feature space-based kernel matrix evaluation measure (FSM) deﬁned as FSM(K, y) = s+ + s− m+ − m− 2 where {s+ , s− } are the standard deviations of the positive and negative classes, and {m+ , m− } are the class centers in the feature space. Tanabe et al. (2008) optimize the kernel weights for the convex combination of kernels by minimizing this measure: minimize FSM(Kη , y) with respect to η ∈ RP + P ∑ ηm = 1. subject to m=1 This method gives similar performance results when compared to the SMO-like algorithm of Bach et al. (2004) for a protein-protein interaction prediction problem using much less time and memory. Ying et al. (2009) follow an information-theoretic approach based on the KL divergence between the combined kernel matrix and the optimal kernel matrix: minimize KL(N (0, Kη ) N (0, yy⊤ )) with respect to η ∈ RP + P ∑ ηm = 1 subject to m=1 where 0 is the vector of zeros with proper dimension. The kernel combinations weights can be optimized using a projected gradient-descent method. 3.6 Structural Risk Optimizing Linear Approaches with Arbitrary Kernel Weights Lanckriet et al. (2002) follow a direct approach in order to optimize the unrestricted kernel combination weights. The implausibility of a kernel matrix, ω(K), is deﬁned as the objective function value obtained after solving a canonical SVM optimization problem (Here we only consider the soft margin formulation, which uses the ℓ1 -norm on slack variables): N maximize ω(K) = ∑ αi − i=1 with respect to α ∈ 1 N N ∑ ∑ αi α j yi y j k(xi , x j ) 2 i=1 j=1 RN + N subject to ∑ αi yi = 0 i=1 C ≥ αi ≥ 0 ∀i. The combined kernel matrix is selected from the following set: P KL = K : K = ∑ ηm Km , m=1 2225 K 0, tr (K) ≤ c ¨ G ONEN AND A LPAYDIN where the selected kernel matrix is forced to be positive semideﬁnite. The resulting optimization problem that minimizes the implausibility of the combined kernel matrix (the objective function value of the corresponding soft margin SVM optimization problem) is formulated as minimize ω(Ktra ) η with respect to Kη ∈ KL subject to tr Kη = c where Ktra is the kernel matrix calculated only over the training set and this problem can be cast η into the following SDP formulation: minimize t with respect to η ∈ RP , t ∈ R, λ ∈ R, ν ∈ RN , δ ∈ RN + + subject to tr Kη = c 1 + ν − δ + λy (yy⊤ ) ⊙ Ktra η ⊤ (1 + ν − δ + λy) t − 2Cδ⊤ 1 Kη 0 0. This optimization problem is deﬁned for a transductive learning setting and we need to be able to calculate the kernel function values for the test instances as well as the training instances. Lanckriet et al. (2004a,c) consider predicting function classiﬁcations associated with yeast proteins. Different kernels calculated on heterogeneous genomic data, namely, amino acid sequences, protein-protein interactions, genetic interactions, protein complex data, and expression data, are combined using an SDP formulation. This gives better results than SVMs trained with each kernel in nine out of 13 experiments. Qiu and Lane (2005) extends ε-tube SVR to a QCQP formulation for regression problems. Conforti and Guido (2010) propose another SDP formulation that removes trace restriction on the combined kernel matrix and introduces constraints over the kernel weights for an inductive setting. 3.7 Structural Risk Optimizing Linear Approaches with Nonnegative Kernel Weights Lanckriet et al. (2004a) restrict the combination weights to have nonnegative values by selecting the combined kernel matrix from P KP = K : K = ∑ ηm Km , m=1 η ≥ 0, K 2226 0, tr (K) ≤ c M ULTIPLE K ERNEL L EARNING A LGORITHMS and reduce the SDP formulation to the following QCQP problem by selecting the combined kernel matrix from KP instead of KL : minimize N 1 ct − ∑ αi 2 i=1 with respect to α ∈ RN , t ∈ R + subject to tr (Km )t ≥ α⊤ ((yy⊤ ) ⊙ Ktra )α m N ∀m ∑ αi yi = 0 i=1 C ≥ αi ≥ 0 ∀i where we can jointly ﬁnd the support vector coefﬁcients and the kernel combination weights. This optimization problem is also developed for a transductive setting, but we can simply take the number of test instances as zero and ﬁnd the kernel combination weights for an inductive setting. The interior-point methods used to solve this QCQP formulation also return the optimal values of the dual variables that correspond to the optimal kernel weights. Qiu and Lane (2005) give also a QCQP formulation of regression using ε-tube SVR. The QCQP formulation is used for predicting siRNA efﬁcacy by combining kernels over heterogeneous data sources (Qiu and Lane, 2009). Zhao et al. (2009) develop a multiple kernel learning method for clustering problems using the maximum margin clustering idea of Xu et al. (2005) and a nonnegative linear combination of kernels. Lanckriet et al. (2004a) combine two different kernels obtained from heterogeneous information sources, namely, bag-of-words and graphical representations, on the Reuters-21578 data set. Combining these two kernels with positive weights outperforms the single-kernel results obtained with SVM on four tasks out of ﬁve. Lanckriet et al. (2004b) use a QCQP formulation to integrate multiple kernel functions calculated on heterogeneous views of the genome data obtained through different experimental procedures. These views include amino acid sequences, hydropathy proﬁles, gene expression data and known protein-protein interactions. The prediction task is to recognize the particular classes of proteins, namely, membrane proteins and ribosomal proteins. The QCQP approach gives signiﬁcantly better results than any single kernel and the unweighted sum of kernels. The assigned kernel weights also enable us to extract the relative importance of the data sources feeding the separate kernels. This approach assigns near zero weights to random kernels added to the candidate set of kernels before training. Dehak et al. (2008) combine three different kernels obtained on the same features and get better results than score fusion for speaker veriﬁcation problem. A similar result about unweighted and weighted linear kernel combinations is also obtained by Lewis et al. (2006a). They compare the performances of unweighted and weighted sums of kernels on a gene functional classiﬁcation task. Their results can be summarized with two guidelines: (a) When all kernels or data sources are informative, we should use the unweighted sum rule. (b) When some of the kernels or the data sources are noisy or irrelevant, we should optimize the kernel weights. Fung et al. (2004) propose an iterative algorithm using the kernel Fisher discriminant analysis as the base learner to combine heterogeneous kernels in a linear manner with nonnegative weights. The proposed method requires solving a simple nonsingular system of linear equations of size (N + 1) and a QP problem having P decision variables at each iteration. On a colorectal cancer diagnosis 2227 ¨ G ONEN AND A LPAYDIN task, this method obtains similar results using much less computation time compared to selecting a kernel for standard kernel Fisher discriminant analysis. Tsuda et al. (2004) learn the kernel combination weights by minimizing an approximation of the cross-validation error for kernel Fisher discriminant analysis. In order to update the kernel combination weights, cross-validation error should be approximated with a differentiable error function. They use the sigmoid function for error approximation and derive the update rules of the kernel weights. This procedure requires inverting a N × N matrix and calculating the gradients at each step. They combine heterogeneous data sources using kernels, which are mixed linearly and nonlinearly, for bacteria classiﬁcation and gene function prediction tasks. Fisher discriminant analysis with the combined kernel matrix that is optimized using the cross-validation error approximation, gives signiﬁcantly better results than single kernels for both tasks. In order to consider the capacity of the resulting classiﬁer, Tan and Wang (2004) optimize the nonnegative combination coefﬁcients using the minimal upper bound of the Vapnik-Chervonenkis dimension as the target function. Varma and Ray (2007) propose a formulation for combining kernels using a linear combination with regularized nonnegative weights. The regularization on the kernel combination weights is achieved by adding a term to the objective function and integrating a set of constraints. The primal optimization problem with these two modiﬁcations can be given as minimize 1 wη 2 N P i=1 2 2 +C m=1 ∑ ξ i + ∑ σm ηm with respect to wη ∈ RSη , ξ ∈ RN , b ∈ R, η ∈ RP + + subject to yi ( wη , Φη (xi ) + b) ≥ 1 − ξi ∀i Aη ≥ p where Φη (·) corresponds to the feature space that implicitly constructs the combined kernel function kη (xi , x j ) = ∑P ηm km (xm , xm ) and wη is the vector of weight coefﬁcients assigned to Φη (·). m=1 j i The parameters A ∈ RR×P , p ∈ RR , and σ ∈ RP encode our prior information about the kernel weights. For example, assigning higher σi values to some of the kernels effectively eliminates them by assigning zero weights to them. The corresponding dual formulation is derived as the following SOCP problem: N maximize ∑ α i − p⊤ δ i=1 with respect to α ∈ RN , δ ∈ RP + + subject to σm − δ⊤ A(:, k) ≥ 1 N N ∑ ∑ αi α j yi y j km (xm , xm ) i j 2 i=1 j=1 ∀m N i=1 ∑ αi yi = 0 ∀m C ≥ αi ≥ 0 ∀i. Instead of solving this SOCP problem directly, Varma and Ray (2007) also propose an alternating optimization problem that performs projected gradient updates for kernel weights and solves a QP 2228 M ULTIPLE K ERNEL L EARNING A LGORITHMS problem to ﬁnd the support vector coefﬁcients at each iteration. The primal optimization problem for given η is written as minimize J(η) = 1 wη 2 N P i=1 2 2 +C m=1 ∑ ξ i + ∑ σm ηm with respect to wη ∈ R , ξ ∈ b∈R subject to yi ( wη , Φη (xi ) + b) ≥ 1 − ξi Sη RN , + ∀i and the corresponding dual optimization problem is N maximize J(η) = ∑ αi − i=1 1 N N ∑ ∑ αi α j yi y j 2 i=1 j=1 P ∑ ηm km (xm , xm ) + i j m=1 P ∑ σm ηm m=1 kη (xi , x j ) with respect to α ∈ RN + N i=1 ∑ αi yi = 0 ∀m C ≥ αi ≥ 0 subject to ∀i. The gradients with respect to the kernel weights are calculated as ∂kη (xi , x j ) 1 N N 1 N N ∂J(η) = σm − ∑ ∑ αi α j yi y j = σm − ∑ ∑ αi α j yi y j km (xm , xm ) i j ∂ηm 2 i=1 j=1 ∂ηm 2 i=1 j=1 ∀m and these gradients are used to update the kernel weights while considering nonnegativity and other constraints. Usually, the kernel weights are constrained by a trace or the ℓ1 -norm regularization. Cortes et al. (2009) discuss the suitability of the ℓ2 -norm for MKL. They combine kernels with ridge regression using the ℓ2 -norm regularization over the kernel weights. They conclude that using the ℓ1 -norm improves the performance for a small number of kernels, but degrades the performance when combining a large number of kernels. However, the ℓ2 -norm never decreases the performance and increases it signiﬁcantly for larger sets of candidate kernels. Yan et al. (2009) compare the ℓ1 -norm and the ℓ2 -norm for image and video classiﬁcation tasks, and conclude that the ℓ2 -norm should be used when the combined kernels carry complementary information. Kloft et al. (2010a) generalize the MKL formulation for arbitrary ℓ p -norms with p ≥ 1 by regularizing over the kernel coefﬁcients (done by adding µ η p to the objective function) or equivalently, p 2229 ¨ G ONEN AND A LPAYDIN constraining them ( η p p ≤ 1). The resulting optimization problem is N maximize  1 P ∑ αi − 2  ∑  i=1 m=1 with respect to α ∈ RN + p p−1 p−1 N N p   ∑ ∑ αi α j yi y j km (xm , xm ) i j  i=1 j=1 N subject to ∑ αi yi = 0 i=1 C ≥ αi ≥ 0 ∀i and they solve this problem using alternative optimization strategies based on Newton-descent and cutting planes. Xu et al. (2010b) add an entropy regularization term instead of constraining the norm of the kernel weights and derive an efﬁcient and smooth optimization framework based on Nesterov’s method. Kloft et al. (2010b) and Xu et al. (2010a) propose an efﬁcient optimization method for arbitrary ℓ p -norms with p ≥ 1. Although they approach the problem from different perspectives, they ﬁnd the same closed-form solution for updating the kernel weights at each iteration. Kloft et al. (2010b) use a block coordinate-descent method and Xu et al. (2010a) use the equivalence between group Lasso and MKL, as shown by Bach (2008) to derive the update equation. Both studies formulate an alternating optimization method that solves an SVM at each iteration and update the kernel weights as follows: wm ηm = P ∑ wh h=1 2 p+1 2 2p p+1 1 p (8) 2 where wm 2 = η2 ∑N ∑N αi α j yi y j km (xm , xm ) from the duality conditions. m i=1 j=1 i j 2 When we restrict the kernel weights to be nonnegative, the SDP formulation of Conforti and Guido (2010) reduces to a QCQP problem. Lin et al. (2009) propose a dimensionality reduction method that uses multiple kernels to embed data instances from different feature spaces to a uniﬁed feature space. The method is derived from a graph embedding framework using kernel matrices instead of data matrices. The learning phase is performed using a two-step alternate optimization procedure that updates the dimensionality reduction coefﬁcients and the kernel weights in turn. McFee and Lanckriet (2009) propose a method for learning a uniﬁed space from multiple kernels calculated over heterogeneous data sources. This method uses a partial order over pairwise distances as the input and produces an embedding using graph-theoretic tools. The kernel (data source) combination rule is learned by solving an SDP problem and all input instances are mapped to the constructed common embedding space. Another possibility is to allow only binary ηm for kernel selection. We get rid of kernels whose ηm = 0 and use the kernels whose ηm = 1. Xu et al. (2009b) deﬁne a combined kernel over the set of kernels calculated on each feature independently and perform feature selection using this deﬁnition. 2230 M ULTIPLE K ERNEL L EARNING A LGORITHMS The deﬁned kernel function can be expressed as D kη (xi , x j ) = ∑ ηm k(xi [m], x j [m]) m=1 where [·] indexes the elements of a vector and η ∈ {0, 1}D . For efﬁcient learning, η is relaxed into the continuous domain (i.e., 1 ≥ η ≥ 0). Following Lanckriet et al. (2004a), an SDP formulation is derived and this formulation is cast into a QCQP problem to reduce the time complexity. 3.8 Structural Risk Optimizing Linear Approaches with Kernel Weights on a Simplex We can think of kernel combination as a weighted average of kernels and consider η ∈ RP and + ∑P ηm = 1. Joachims et al. (2001) show that combining two kernels is beneﬁcial if both of them m=1 achieve approximately the same performance and use different data instances as support vectors. This makes sense because in combination, we want kernels to be useful by themselves and complementary. In a web page classiﬁcation experiment, they show that combining the word and the hyperlink representations through the convex combination of two kernels (i.e., η2 = 1 − η1 ) can achieve better classiﬁcation accuracy than each of the kernels. Chapelle et al. (2002) calculate the derivative of the margin and the derivative of the radius (of the smallest sphere enclosing the training points) with respect to a kernel parameter, θ: ∂ w ∂θ 2 2 ∂R2 ∂θ N N = − ∑ ∑ αi α j yi y j i=1 j=1 N = ∑ βi i=1 ∂k(xi , x j ) ∂θ ∂k(xi , x j ) ∂k(xi , xi ) N N − ∑ ∑ βi β j ∂θ ∂θ i=1 j=1 where α is obtained by solving the canonical SVM optimization problem and β is obtained by solving the QP problem deﬁned by Vapnik (1998). These derivatives can be used to optimize the individual parameters (e.g., scaling coefﬁcient) on each feature using an alternating optimization procedure (Weston et al., 2001; Chapelle et al., 2002; Grandvalet and Canu, 2003). This strategy is also a multiple kernel learning approach, because the optimized parameters can be interpreted as the kernel parameters and we combine these kernel values over all features. Bousquet and Herrmann (2003) rewrite the gradient of the margin by replacing K with Kη and taking the derivative with respect to the kernel weights gives ∂ wη ∂ηm 2 2 N N = − ∑ ∑ αi α j yi y j i=1 j=1 N N ∂kη (xi , x j ) = − ∑ ∑ αi α j yi y j km (xm , xm ) i j ∂ηm i=1 j=1 ∀m where wη is the weight vector obtained using Kη in training. In an iterative manner, an SVM is trained to obtain α, then η is updated using the calculated gradient while considering nonnegativity (i.e., η ∈ RP ) and normalization (i.e., ∑P ηm = 1). This procedure considers the performance (in + m=1 terms of margin maximization) of the resulting classiﬁer, which uses the combined kernel matrix. 2231 ¨ G ONEN AND A LPAYDIN Bach et al. (2004) propose a modiﬁed primal formulation that uses the weighted ℓ1 -norm on feature spaces and the ℓ2 -norm within each feature space. The modiﬁed primal formulation is 2 P 1 minimize 2 ∑ dm wm 2 i=1 m=1 with respect to wm ∈ R , ξ ∈ Sm P ∑ subject to yi N +C ∑ ξi RN , + b∈R wm , Φm (xm ) + b i m=1 ≥ 1 − ξi ∀i where the feature space constructed using Φm (·) has the dimensionality Sm and the weight dm . When we consider this optimization problem as an SOCP problem, we obtain the following dual formulation: minimize 1 2 N γ − ∑ αi 2 i=1 with respect to γ ∈ R, α ∈ RN + N N 2 subject to γ2 dm ≥ ∑ ∑ αi α j yi y j km (xm , xm ) i j i=1 j=1 ∀m N ∑ αi yi = 0 i=1 C ≥ αi ≥ 0 ∀i (9) where we again get the optimal kernel weights from the optimal dual variables and the weights 2 satisfy ∑P dm ηm = 1. The dual problem is exactly equivalent to the QCQP formulation of Lanckm=1 riet et al. (2004a) when we take dm = tr (Km ) /c. The advantage of the SOCP formulation is that Bach et al. (2004) devise an SMO-like algorithm by adding a Moreau-Yosida regularization term, 1/2 ∑P a2 wm 2 , to the primal objective function and deriving the corresponding dual form=1 m 2 mulation. Using the ℓ1 -norm on feature spaces, Yamanishi et al. (2007) combine tree kernels for identifying human glycans into four blood components: leukemia cells, erythrocytes, plasma, and serum. Except on plasma task, representing glycans as rooted trees and combining kernels improve ¨ performance in terms of the area under the ROC curve. Ozen et al. (2009) use the formulation of Bach et al. (2004) to combine different feature subsets for protein stability prediction problem and extract information about the importance of these subsets by looking at the learned kernel weights. Bach (2009) develops a method for learning linear combinations of an exponential number of kernels, which can be expressed as product of sums. The method is applied to nonlinear variable selection and efﬁciently explores the large feature spaces in polynomial time. 2232 M ULTIPLE K ERNEL L EARNING A LGORITHMS Sonnenburg et al. (2006a,b) rewrite the QCQP formulation of Bach et al. (2004): minimize γ with respect to γ ∈ R, α ∈ RN + N subject to ∑ αi yi = 0 i=1 C ≥ αi ≥ 0 γ≥ ∀i N 1 αi α j yi y j km (xm , xm ) − ∑ αi ∑∑ i j 2 i=1 j=1 i=1 N N ∀m Sm (α) and convert this problem into the following SILP problem: maximize θ with respect to θ ∈ R, η ∈ RP + P subject to ∑ ηm = 1 m=1 P ∑ ηm Sm (α) ≥ θ m=1 ∀α ∈ {α : α ∈ RN , α⊤ y = 0, C ≥ α ≥ 0} where the problem has inﬁnitely many constraints due to the possible values of α. The SILP formulation has lower computational complexity compared to the SDP and QCQP formulations. Sonnenburg et al. (2006a,b) use a column generation approach to solve the resulting SILPs using a generic LP solver and a canonical SVM solver in the inner loop. Both the LP solver and the SVM solver can use the previous optimal values for hot-start to obtain the new optimal values faster. These allow us to use the SILP formulation to learn the kernel combination weights for hundreds of kernels on hundreds of thousands of training instances efﬁciently. For example, they perform training on a real-world splice data set with millions of instances from computational biology with string kernels. They also generalize the idea to regression, one-class classiﬁcation, and strictly convex and differentiable loss functions. Kim et al. (2006) show that selecting the optimal kernel from the set of convex combinations over the candidate kernels can be formulated as a convex optimization problem. This formulation is more efﬁcient than the iterative approach of Fung et al. (2004). Ye et al. (2007a) formulate an SDP problem inspired by Kim et al. (2006) for learning an optimal kernel over a convex set of candidate kernels for RKDA. The SDP formulation can be modiﬁed so that it can jointly optimize the kernel weights and the regularization parameter. Ye et al. (2007b, 2008) derive QCQP and SILP formulations equivalent to the previous SDP problem in order to reduce the time complexity. These three formulations are directly applicable to multiclass classiﬁcation because it uses RKDA as the base learner. De Bie et al. (2007) derive a QCQP formulation of one-class classiﬁcation using a convex combination of multiple kernels. In order to prevent the combined kernel from overﬁtting, they also propose a modiﬁed mathematical model that deﬁnes lower limits for the kernel weights. Hence, 2233 ¨ G ONEN AND A LPAYDIN each kernel in the set of candidate kernels is used in the combined kernel and we obtain a more regularized solution. Zien and Ong (2007) develop a QCQP formulation and convert this formulation in two different SILP problems for multiclass classiﬁcation. They show that their formulation is the multiclass generalization of the previously developed binary classiﬁcation methods of Bach et al. (2004) and Sonnenburg et al. (2006b). The proposed multiclass formulation is tested on different bioinformatics applications such as bacterial protein location prediction (Zien and Ong, 2007) and protein subcellular location prediction (Zien and Ong, 2007, 2008), and outperforms individual kernels and unweighted sum of kernels. Hu et al. (2009) combine the MKL formulation of Zien and Ong (2007) and the sparse kernel learning method of Wu et al. (2006). This hybrid approach learns the optimal kernel weights and also obtains a sparse solution. Rakotomamonjy et al. (2007, 2008) propose a different primal problem for MKL and use a projected gradient method to solve this optimization problem. The proposed primal formulation is minimize 1 P 1 wm ∑ 2 m=1 ηm 2 2 +C with respect to wm ∈ R , ξ ∈ Sm P ∑ subject to yi N ∑ ξi i=1 RN , + b ∈ R, η ∈ RP + wm , Φm (xm ) + b i m=1 ≥ 1 − ξi ∀i P ∑ ηm = 1 m=1 and they deﬁne the optimal SVM objective function value given η as J(η): minimize J(η) = 1 P 1 wm ∑ 2 m=1 ηm 2 2 +C N ∑ ξi i=1 with respect to wm ∈ RSm , ξ ∈ RN , b ∈ R + P ∑ subject to yi wm , Φm (xm ) + b i m=1 ≥ 1 − ξi ∀i. Due to strong duality, one can also calculate J(η) using the dual formulation: N maximize J(η) = ∑ αi − i=1 1 N N ∑ ∑ αi α j yi y j 2 i=1 j=1 P ∑ ηm km (xm , xm ) i j m=1 kη (xi , x j ) with respect to α ∈ RN + N subject to ∑ αi yi = 0 i=1 C ≥ αi ≥ 0 ∀i. 2234 M ULTIPLE K ERNEL L EARNING A LGORITHMS The primal formulation can be seen as the following constrained optimization problem: minimize J(η) with respect to η ∈ RP + P subject to ∑ ηm = 1. (10) m=1 The overall procedure to solve this problem, called S IMPLE MKL, consists of two main steps: (a) solving a canonical SVM optimization problem with given η and (b) updating η using the following gradient calculated with α found in the ﬁrst step: ∂kη (xm , xm ) ∂J(η) 1 N N 1 N N j i = − ∑ ∑ αi α j yi y j = − ∑ ∑ αi α j yi y j km (xm , xm ) i j ∂ηm 2 i=1 j=1 ∂ηm 2 i=1 j=1 ∀m. The gradient update procedure must consider the nonnegativity and normalization properties of the kernel weights. The derivative with respect to the kernel weights is exactly equivalent (up to a multiplicative constant) to the gradient of the margin calculated by Bousquet and Herrmann (2003). The overall algorithm is very similar to the algorithm used by Sonnenburg et al. (2006a,b) to solve an SILP formulation. Both algorithms use a canonical SVM solver in order to calculate α at each step. The difference is that they use different updating procedures for η, namely, a projected gradient update and solving an LP. Rakotomamonjy et al. (2007, 2008) show that S IMPLE MKL is more stable than solving the SILP formulation. S IMPLE MKL can be generalized to regression, one-class and multiclass classiﬁcation (Rakotomamonjy et al., 2008). Chapelle and Rakotomamonjy (2008) propose a second order method, called H ESSIAN MKL, extending S IMPLE MKL. H ESSIAN MKL updates kernel weights at each iteration using a constrained Newton step found by solving a QP problem. Chapelle and Rakotomamonjy (2008) show that H ESSIAN MKL converges faster than S IMPLE MKL. Xu et al. (2009a) propose a hybrid method that combines the SILP formulation of Sonnenburg et al. (2006b) and S IMPLE MKL of Rakotomamonjy et al. (2008). The SILP formulation does not regularize the kernel weights obtained from the cutting plane method and S IMPLE MKL uses the gradient calculated only in the last iteration. The proposed model overcomes both disadvantages and ﬁnds the kernel weights for the next iteration by solving a small QP problem; this regularizes the solution and uses the past information. The alternating optimization method proposed by Kloft et al. (2010b) and Xu et al. (2010a) learns a convex combination of kernels when we use the ℓ1 -norm for regularizing the kernel weights. When we take p = 1, the update equation in (8) becomes ηm = wm 2 . P ∑ wh (11) 2 h=1 The SDP formulation of Conforti and Guido (2010) reduces to a QCQP problem when we use a convex combination of the base kernels. Longworth and Gales (2008, 2009) introduce an extra regularization term to the objective function of S IMPLE MKL (Rakotomamonjy et al., 2008). This modiﬁcation allows changing the level 2235 ¨ G ONEN AND A LPAYDIN of sparsity of the combined kernels. The extra regularization term is λ P ∑ m=1 ηm − 1 P 2 =λ λ P P ∑ η 2 − P = + λ ∑ η2 m m m=1 m=1 where λ is regularization parameter that determines the solution sparsity. For example, large values of λ force the mathematical model to use all the kernels with a uniform weight, whereas small values produce sparse combinations. Micchelli and Pontil (2005) try to learn the optimal kernel over the convex hull of predeﬁned basic kernels by minimizing a regularization functional. Their analysis shows that any optimizing kernel can be expressed as the convex combination of basic kernels. Argyriou et al. (2005, 2006) build practical algorithms for learning a suboptimal kernel when the basic kernels are continuously parameterized by a compact set. This continuous parameterization allows selecting kernels from basically an inﬁnite set, instead of a ﬁnite number of basic kernels. Instead of selecting kernels from a predeﬁned ﬁnite set, we can increase the number of candidate kernels in an iterative manner. We can basically select kernels from an uncountably inﬁnite ¨ o˘ ¨ set constructed by considering base kernels with different kernel parameters (Oz¨ gur-Aky¨ z and u Weber, 2008; Gehler and Nowozin, 2008). Gehler and Nowozin (2008) propose a forward selection algorithm that ﬁnds the kernel weights for a ﬁxed size of candidate kernels using one of the methods described above, then adds a new kernel to the set of candidate kernels, until convergence. Most MKL methods do not consider the group structure between the kernels combined. For example, a group of kernels may be calculated on the same set of features and even if we assign a nonzero weight to only one of them, we have to extract the features in the testing phase. When kernels have such a group structure, it is reasonable to pick all or none of them in the combined kernel. Szafranski et al. (2008, 2010) follow this idea and derive an MKL method by changing the mathematical model used by Rakotomamonjy et al. (2007). Saketha Nath et al. (2010) propose another MKL method that considers the group structure between the kernels and this method assumes that every kernel group carries important information. The proposed formulation enforces the ℓ∞ norm at the group level and the ℓ1 -norm within each group. By doing this, each group is used in the ﬁnal learner, but sparsity is promoted among kernels in each group. They formulate the problem as an SCOP problem and give a highly efﬁcient optimization algorithm that uses a mirror-descent approach. Subrahmanya and Shin (2010) generalize group-feature selection to kernel selection by introducing a log-based concave penalty term for obtaining extra sparsity; this is called sparse multiple kernel learning (SMKL). The reason for adding this concave penalty term is explained as the lack of ability of convex MKL methods to obtain sparse formulations. They show that SMKL obtains more sparse solutions than convex formulations for signal processing applications. Most of the structural risk optimizing linear approaches can be casted into a general framework (Kloft et al., 2010a,b). The uniﬁed optimization problem with the Tikhonov regularization can be written as minimize 1 P wm ∑ 2 m=1 ηm 2 2 N +C ∑ L i=1 with respect to wm ∈ R , b ∈ R, η ∈ Sm P ∑ m=1 RP + 2236 wm , Φm (xm ) + b, yi + µ η i p p M ULTIPLE K ERNEL L EARNING A LGORITHMS where L(·, ·) is the loss function used. Alternatively, we can use the Ivanov regularization instead of the Tikhonov regularization by integrating an additional constraint into the optimization problem: minimize 1 P wm ∑ 2 m=1 ηm 2 2 N +C ∑ L i=1 with respect to wm ∈ R , b ∈ R, η ∈ Sm subject to η p p P ∑ wm , Φm (xm ) + b, yi i m=1 RP + ≤ 1. Figure 1 lists the MKL algorithms that can be casted into the general framework described above. Zien and Ong (2007) show that their formulation is equivalent to those of Bach et al. (2004) and Sonnenburg et al. (2006a,b). Using uniﬁed optimization problems given above and the results of Zien and Ong (2007), Kloft et al. (2010a,b) show that the formulations with p = 1 in Figure 1 fall into the same equivalence class and introduce a new formulation with p ≥ 1. The formulation of Xu et al. (2010a) is also equivalent to those of Kloft et al. (2010a,b). Tikhonov Regularization p=1 Ivanov Regularization Bach et al. (2004) Sonnenburg et al. (2006a,b) Rakotomamonjy et al. (2007, 2008) Zien and Ong (2007) Varma and Ray (2007) Kloft et al. (2010a,b) Xu et al. (2010a) p≥1 Figure 1: MKL algorithms that can be casted into the general framework described. 3.9 Structural Risk Optimizing Nonlinear Approaches Ong et al. (2003) propose to learn a kernel function instead of a kernel matrix. They deﬁne a kernel function in the space of kernels called a hyperkernel. Their construction includes convex combinations of an inﬁnite number of pointwise nonnegative kernels. Hyperkernels are generalized to different machine learning problems such as binary classiﬁcation, regression, and one-class classiﬁcation (Ong and Smola, 2003; Ong et al., 2005). When they use the regularized risk functional as the empirical quality functional to be optimized, the learning phase can be performed by solving an SDP problem. Tsang and Kwok (2006) convert the resulting optimization problems into SOCP problems in order to reduce the time complexity of the training phase. Varma and Babu (2009) propose a generalized formulation called generalized multiple kernel learning (GMKL) that contains two regularization terms and a loss function in the objective function. This formulation regularizes both the hyperplane weights and the kernel combination weights. The loss function can be one of the classical loss functions, such as, hinge loss for classiﬁcation, or ε-loss for regression. The proposed primal formulation applied to binary classiﬁcation problem 2237 ¨ G ONEN AND A LPAYDIN with hinge loss and the regularization function, r(·), can be written as minimize 1 wη 2 2 2 +C N ∑ ξi + r(η) i=1 with respect to wη ∈ R , ξ ∈ RN , b ∈ R, η ∈ RP + + subject to yi ( wη , Φη (xi ) + b) ≥ 1 − ξi ∀i Sη where Φη (·) corresponds to the feature space that implicitly constructs the combined kernel function kη (·, ·) and wη is the vector of weight coefﬁcients assigned to Φη (·). This problem, different from the primal problem of S IMPLE MKL, is not convex, but the solution strategy is the same. The objective function value of the primal formulation given η is used as the target function: minimize J(η) = 1 wη 2 2 2 +C N ∑ ξi + r(η) i=1 with respect to wη ∈ RSη , ξ ∈ RN , b ∈ R + subject to yi ( wη , Φη (xi ) + b) ≥ 1 − ξi ∀i and the following dual formulation is used for the gradient step: N maximize J(η) = ∑ αi − i=1 with respect to α ∈ 1 N N ∑ ∑ αi α j yi y j kη (xi , x j ) + r(η) 2 i=1 j=1 RN + N subject to ∑ αi yi = 0 i=1 C ≥ αi ≥ 0 ∀i. The regularization function r(·) and kη (·, ·) can be any differentiable function of η with continuous derivative. The gradient with respect to the kernel weights is calculated as ∂kη (xi , x j ) ∂J(η) ∂r(η) 1 N N = − ∑ ∑ αi α j yi y j ∂ηm ∂ηm 2 i=1 j=1 ∂ηm ∀m. Varma and Babu (2009) perform gender identiﬁcation experiments on a face image data set by combining kernels calculated on each individual feature, and hence, for kernels whose ηm goes to 0, they perform feature selection. S IMPLE MKL and GMKL are trained with the kernel functions S P kη (·, ·) and kη (·, ·), respectively: S kη (xi , x j ) = P kη (xi , x j ) = D ∑ ηm exp m=1 −γm (xi [m] − x j [m])2 D ∏ exp −ηm (xi [m] − x j [m])2 = exp m=1 D ∑ −ηm (xi [m] − x j [m])2 . m=1 P S They show that GMKL with kη (·, ·) performs signiﬁcantly better than S IMPLE MKL with kη (·, ·). P We see that using kη (·, ·) as the combined kernel function is equivalent to using different scaling 2238 M ULTIPLE K ERNEL L EARNING A LGORITHMS parameters on each feature and using an RBF kernel over these scaled features with unit radius, as done by Grandvalet and Canu (2003). Cortes et al. (2010b) develop a nonlinear kernel combination method based on KRR and polynomial combination of kernels. They propose to combine kernels as follows: kη (xi , x j ) = ∑ ηq q ...q k1 (x1 , x1j )q k2 (x2 , x2j )q i i 1 P 1 2 2 . . . kP (xP , xP )qP i j q∈Q where Q = {q : q ∈ ZP , ∑P qm ≤ d} and ηq1 q2 ...qP ≥ 0. The number of parameters to be learned + m=1 is too large and the combined kernel is simpliﬁed in order to reduce the learning complexity: kη (xi , x j ) = ∑ ηq ηq 1 2 1 2 . . . ηPP k1 (x1 , x1 )q1 k2 (x2 , x2 )q2 . . . kP (xP , xP )qP j i j i i j q q∈R where R = {q : q ∈ ZP , ∑P qm = d} and η ∈ RP . For example, when d = 2, the combined kernel + m=1 function becomes P kη (xi , x j ) = P ∑ ∑ ηm ηh km (xm , xm )kh (xh , xhj ). i j i (12) m=1 h=1 The combination weights are optimized using the following min-max optimization problem: minimize maximize − α⊤ (Kη + λI)α + 2y⊤ α α∈RN η∈ M where M is a positive, bounded, and convex set. Two possible choices for the set M are the ℓ1 -norm and ℓ2 -norm bounded sets deﬁned as M1 = {η : η ∈ RP , η − η0 + M2 = {η : η ∈ RP , η − η0 + 1 2 ≤ Λ} ≤ Λ} (13) (14) where η0 and Λ are two model parameters. A projection-based gradient-descent algorithm can be used to solve this min-max optimization problem. At each iteration, α is obtained by solving a KRR problem with the current kernel matrix and η is updated with the gradients calculated using α while considering the bound constraints on η due to M1 or M2 . Lee et al. (2007) follow a different approach and combine kernels using a compositional method that constructs a (P × N) × (P × N) compositional kernel matrix. This matrix and the training instances replicated P times are used to train a canonical SVM. 3.10 Structural Risk Optimizing Data-Dependent Approaches Lewis et al. (2006b) use a latent variable generative model using the maximum entropy discrimination to learn data-dependent kernel combination weights. This method combines a generative probabilistic model with a discriminative large margin method. G¨ nen and Alpaydın (2008) propose a data-dependent formulation called localized multiple o kernel learning (LMKL) that combines kernels using weights calculated from a gating model. The 2239 ¨ G ONEN AND A LPAYDIN proposed primal optimization problem is minimize 1 P ∑ wm 2 m=1 2 2 +C with respect to wm ∈ R , ξ ∈ Sm N ∑ ξi i=1 RN , + b ∈ R, V ∈ RP×(DG +1) P subject to yi ∑ ηm (xi |V) wm , Φm (xm ) i +b m=1 ≥ 1 − ξi ∀i where the gating model ηm (·|·), parameterized by V, assigns a weight to the feature space obtained with Φm (·). This optimization problem is not convex and a two-step alternate optimization procedure is used to ﬁnd the classiﬁer parameters and the gating model parameters. When we ﬁx the gating model parameters, the problem becomes convex and we obtain the following dual problem: N maximize J(V) = ∑ αi − i=1 with respect to α ∈ 1 N N ∑ ∑ αi α j yi y j kη (xi , x j ) 2 i=1 j=1 RN + N subject to ∑ αi yi = 0 i=1 C ≥ αi ≥ 0 ∀i where the combined kernel matrix is represented as P kη (xi , x j ) = ∑ ηm (xi |V)km (xm , xm )ηm (x j |V). i j m=1 Assuming that the regions of expertise of kernels are linearly separable, we can express the gating model using softmax function: ηm (x|V) = exp( vm , xG + vm0 ) P ∑ exp( vh , xG + vh0 ) ∀m (15) h=1 where V = {vm , vm0 }P , xG ∈ RDG is the representation of the input instance in the feature space in m=1 which we learn the gating model and there are P × (DG + 1) parameters where DG is the dimensionality of the gating feature space. The softmax gating model uses kernels in a competitive manner and generally a single kernel is active for each input. We may also use the sigmoid function instead of softmax and thereby allow multiple kernels to be used in a cooperative manner: ηm (x|V) = 1 exp(− vm , xG − vm0 ) ∀m. (16) The gating model parameters are updated at each iteration by calculating ∂J(V)/∂V and performing a gradient-descent step (G¨ nen and Alpaydın, 2008). o Inspired from LMKL, two methods that learn a data-dependent kernel function are used for image recognition applications (Yang et al., 2009a,b, 2010); they differ in their gating models that 2240 M ULTIPLE K ERNEL L EARNING A LGORITHMS are constants rather than functions of the input. Yang et al. (2009a) divide the training set into clusters as a preprocessing step, and then cluster-speciﬁc kernel weights are learned using alternating optimization. The combined kernel function can be written as P kη (xi , x j ) = ∑ ηm km (xm , xm )ηm i j c c i j m=1 where ηm corresponds to the weight of kernel km (·, ·) in the cluster xi belongs to. The kernel weights ci of the cluster that the test instance is assigned to are used in the testing phase. Yang et al. (2009b, 2010) use instance-speciﬁc kernel weights instead of cluster-speciﬁc weights. The corresponding combined kernel function is P kη (xi , x j ) = ∑ ηm km (xm , xm )ηm i i j j m=1 where ηm corresponds to the weight of kernel km (·, ·) for xi and these instance-speciﬁc weights i are optimized using alternating optimization over the training set. In the testing phase, the kernel weights for a test instance are all taken to be equal. 3.11 Bayesian Approaches Girolami and Rogers (2005) formulate a Bayesian hierarchical model and derive variational Bayes estimators for classiﬁcation and regression problems. The proposed decision function can be formulated as N f (x) = ∑ αi i=0 P ∑ ηm km (xm , xm ) i m=1 where η is modeled with a Dirichlet prior and α is modeled with a zero-mean Gaussian with an inverse gamma variance prior. Damoulas and Girolami (2009b) extend this method by adding auxiliary variables and developing a Gibbs sampler. Multinomial probit likelihood is used to obtain an efﬁcient sampling procedure. Damoulas and Girolami (2008, 2009a) apply these methods to different bioinformatics problems, such as protein fold recognition and remote homology problems, and improve the prediction performances for these tasks. Girolami and Zhong (2007) use the kernel combination idea for the covariance matrices in GPs. Instead of using a single covariance matrix, they deﬁne a weighted sum of covariance matrices calculated over different data sources. A joint inference is performed for both the GP coefﬁcients and the kernel combination weights. Similar to LMKL, Christoudias et al. (2009) develop a Bayesian approach for combining different feature representations in a data-dependent way under the GP framework. A common covariance function is obtained by combining the covariances of feature representations in a nonlinear manner. This formulation can identify the noisy data instances for each feature representation and prevent them from being used. Classiﬁcation is performed using the standard GP approach with the common covariance function. 2241 ¨ G ONEN AND A LPAYDIN 3.12 Boosting Approaches Inspired from ensemble and boosting methods, Bennett et al. (2002) modify the decision function in order to use multiple kernels: N f (x) = ∑ P ∑ αm km (xm , xm ) + b. i i i=1 m=1 The parameters {αm }P and b of the KRR model are learned using gradient-descent in the function m=1 space. The columns of the combined kernel matrix are generated on the ﬂy from the heterogeneous kernels. Bi et al. (2004) develop column generation boosting methods for binary classiﬁcation and regression problems. At each iteration, the proposed methods solve an LP or a QP on a working set depending on the regularization term used. Crammer et al. (2003) modify the boosting methodology to work with kernels by rewriting two loss functions for a pair of data instances by considering the pair as a single instance: ExpLoss(k(xi , x j ), yi y j ) = exp(−yi y j k(xi , x j )) LogLoss(k(xi , x j ), yi y j ) = log(1 + exp(−yi y j k(xi , x j ))). We iteratively update the combined kernel matrix using one of these two loss functions. 4. Experiments In order to compare several MKL algorithms, we perform 10 different experiments on four data sets that are composed of different feature representations. We use both the linear kernel and the Gaussian kernel in our experiments; we will give our results with the linear kernel ﬁrst and then compare them with the results of the Gaussian kernel. The kernel matrices are normalized to unit diagonal before training. 4.1 Compared Algorithms We implement two single-kernel SVM and 16 representative MKL algorithms in MATLAB1 and solve the optimization problems with the MOSEK optimization software (Mosek, 2011). We train SVMs on each feature representation singly and report the results of the one with the highest average validation accuracy, which will be referred as SVM (best). We also train an SVM on the concatenation of all feature representations, which will be referred as SVM (all). RBMKL denotes rule-based MKL algorithms discussed in Section 3.1. RBMKL (mean) trains an SVM with the mean of the combined kernels. RBMKL (product) trains an SVM with the product of the combined kernels. ABMKL denotes alignment-based MKL algorithms. For determining the kernel weights, ABMKL (ratio) uses the heuristic in (2) of Section 3.2 (Qiu and Lane, 2009), ABMKL (conic) solves the QCQP problem in (5) of Section 3.4 (Lanckriet et al., 2004a), and ABMKL (convex) solves the QP problem in (7) of Section 3.5 (He et al., 2008). In the second step, all methods train an SVM with the kernel calculated with these weights. CABMKL denotes centered-alignment-based MKL algorithms. In the ﬁrst step, CABMKL (linear) uses the analytical solution in (4) of Section 3.3 (Cortes et al., 2010a) and CABMKL (conic) solves 1. Implementations are available at http://www.cmpe.boun.edu.tr/~gonen/mkl. 2242 M ULTIPLE K ERNEL L EARNING A LGORITHMS the QP problem in (6) of Section 3.4 (Cortes et al., 2010a) for determining the kernel weights. In the second step, both methods train an SVM with the kernel calculated with these weights. MKL is the original MKL algorithm of Bach et al. (2004) that is formulated as the SOCP problem in (9) of Section 3.8. SimpleMKL is the iterative algorithm of Rakotomamonjy et al. (2008) that uses projected gradient updates and trains SVMs at each iteration to solve the optimization problem in (10) of Section 3.8. GMKL is the generalized MKL algorithm of Varma and Babu (2009) discussed in Section 3.9. In our implementation, kη (·, ·) is the convex combination of base kernels and r(·) is taken as 1/2(η − 1/P)⊤ (η − 1/P). GLMKL denotes the group Lasso-based MKL algorithms proposed by Kloft et al. (2010b) and Xu et al. (2010a). GLMKL ( p = 1) updates the kernel weights using (11) of Section 3.8 and learns a convex combination of the kernels. GLMKL ( p = 2) updates the kernel weights setting p = 2 in (8) of Section 3.7 and learns a conic combination of the kernels. NLMKL denotes the nonlinear MKL algorithm of Cortes et al. (2010b) discussed in Section 3.9 with the exception of replacing the KRR in the inner loop with an SVM as the base learner. NLMKL uses the quadratic kernel given in (12). NLMKL ( p = 1) and NLMKL ( p = 2) select the kernel weights from the sets M1 in (13) and M2 in (14), respectively. In our implementation, η0 is taken as 0 and Λ is assigned to 1 arbitrarily. LMKL denotes the localized MKL algorithm of G¨ nen and Alpaydın (2008) discussed in Seco tion 3.10. LMKL (softmax) uses the softmax gating model in (15), whereas LMKL (sigmoid) uses the sigmoid gating model in (16). Both methods use the concatenation of all feature representations in the gating model. 4.2 Experimental Methodology Our experimental methodology is as follows: Given a data set, if learning and test sets are not supplied separately, a random one-third is reserved as the test set and the remaining two-thirds is used as the learning set. If the learning set has more than 1000 data instances, it is resampled using 5 × 2 cross-validation to generate 10 training and validation sets, with stratiﬁcation, otherwise, we use 30-fold cross-validation. The validation sets of all folds are used to optimize the common hyperparameter C (trying values 0.01, 0.1, 1, 10, and 100). The best hyperparameter conﬁguration (the one that has the highest average accuracy on the validation folds) is used to train the ﬁnal learners on the training folds. Their test accuracies, support vector percentages, active kernel2 counts, and numbers of calls to the optimization toolbox for solving an SVM optimization problem or a more complex optimization problem3 are measured; we report their averages and standard deviations. The active kernel count and the number of calls to the optimization toolbox for SVM (best) are taken as 1 and P, respectively, because it uses only one of the feature representations but needs to train the individual SVMs on all feature representations before choosing the best. Similarly, the active kernel count and the number of calls to the optimization toolbox for SVM (all) are taken as P and 1, respectively, because it uses all of the feature representations but trains a single SVM. 2. A kernel is active, if it needs to be calculated to make a prediction for an unseen test instance. 3. All algorithms except the MKL formulation of Bach et al. (2004), MKL, solve QP problems when they call the optimization toolbox, whereas MKL solves an SOCP problem. 2243 ¨ G ONEN AND A LPAYDIN The test accuracies and support vector percentages are compared using the 5 × 2 cv paired F test (Alpaydın, 1999) or the paired t test according to the resampling scheme used. The active kernel counts and the number of calls to the optimization toolbox are compared using the Wilcoxon’s signed-rank test (Wilcoxon, 1945). For all statistical tests, the signiﬁcance level, α, is taken as 0.05. We want to test if by combining kernels, we get accuracy higher than any of the single kernels. In the result tables, a superscript a denotes that the performance values of SVM (best) and the compared algorithm are statistically signiﬁcantly different, where a and a denote that the compared algorithm has statistically signiﬁcantly higher and lower average than SVM (best), respectively. Similarly, we want to test if an algorithm is better than a straightforward concatenation of the input features, SVM (all), and if it is better than ﬁxed combination, namely, RBMKL (mean); for those, we use the superscripts b and c, respectively. 4.3 Protein Fold Prediction Experiments We perform experiments on the Protein Fold (P ROTEIN) prediction data set4 from the MKL Repository, composed of 10 different feature representations and two kernels for 694 instances (311 for training and 383 for testing). The properties of these feature representations are summarized in Table 3. We construct a binary classiﬁcation problem by combining the major structural classes {α, β} into one class and {α/β, α + β} into another class. Due to the small size of this data set, we use 30-fold cross-validation and the paired t test. We do three experiments on this data set using three different subsets of kernels. Name Dimension C OM S EC H YD VOL P OL P LZ L1 L4 L14 L30 B LO PAM 20 21 21 21 21 21 22 28 48 80 311 311 Data Source Amino-acid composition Predicted secondary structure Hydrophobicity Van der Waals volume Polarity Polarizability Pseudo amino-acid composition at interval 1 Pseudo amino-acid composition at interval 4 Pseudo amino-acid composition at interval 14 Pseudo amino-acid composition at interval 30 Smith-Waterman scores with the BLOSUM 62 matrix Smith-Waterman scores with the PAM 50 matrix Table 3: Multiple feature representations in the P ROTEIN data set. Table 4 lists the performance values of all algorithms on the P ROTEIN data set with (C OM-S ECH YD-VOL-P OL-P LZ). All combination algorithms except RBMKL (product) and GMKL outperform SVM (best) by more than four per cent in terms of average test accuracy. NLMKL ( p = 1), NLMKL ( p = 2), LMKL (softmax), and LMKL (sigmoid) are the only four algorithms that obtain more than 80 per cent average test accuracy and are statistically signiﬁcantly more accurate than SVM (best), SVM (all), and RBMKL (mean). Nonlinear combination algorithms, namely, RBMKL (product), NLMKL ( p = 1), and NLMKL ( p = 2), have the disadvantage that they store statistically signiﬁcantly more 4. Available at http://mkl.ucsd.edu/dataset/protein-fold-prediction. 2244 M ULTIPLE K ERNEL L EARNING A LGORITHMS support vectors than all other algorithms. ABMKL (conic) and CABMKL (conic) are the two MKL algorithms that perform kernel selection and use less than ﬁve kernels on the average, while the others use all six kernels, except CABMKL (linear) which uses ﬁve kernels in one of 30 folds. The two-step algorithms, except GMKL, LMKL (softmax), and LMKL (sigmoid), need to solve fewer than 20 SVM problems on the average. GLMKL ( p = 1) and GLMKL ( p = 2) solve statistically signiﬁcantly fewer optimization problems than all the other two-step algorithms. LMKL (softmax) and LMKL (sigmoid) solve many SVM problems; the large standard deviations for this performance value are mainly due to the random initialization of the gating model parameters and it takes longer for some folds to converge. Table 5 summarizes the performance values of all algorithms on the P ROTEIN data set with (C OM-S EC-H YD-VOL-P OL-P LZ-L1-L4-L14-L30). All combination algorithms except RBMKL (product) outperform SVM (best) by more than two per cent in terms of average test accuracy. NLMKL ( p = 1) and NLMKL ( p = 2) are the only two algorithm that obtain more than 85 per cent average test accuracy and are statistically signiﬁcantly more accurate than SVM (best), SVM (all), and RBMKL (mean). When the number of kernels combined becomes large as in this experiment, as a result of multiplication, RBMKL (product) starts to have very small kernel values at the off-diagonal entries of the combined kernel matrix. This causes the classiﬁer to behave like a nearest-neighbor classiﬁer by storing many support vectors and to perform badly in terms of average test accuracy. As observed in the previous experiment, the nonlinear combination algorithms, namely, RBMKL (product), NLMKL ( p = 1), and NLMKL ( p = 2), store statistically signiﬁcantly more support vectors than all other algorithms. ABMKL (conic), ABMKL (convex), CABMKL (linear), CABMKL (conic), MKL, SimpleMKL, and GMKL are the seven MKL algorithms that perform kernel selection and use fewer than 10 kernels on the average, while others use all 10 kernels. Similar to the results of the previous experiment, GLMKL ( p = 1) and GLMKL ( p = 2) solve statistically signiﬁcantly fewer optimization problems than all the other two-step algorithms and the very high standard deviations for LMKL (softmax) and LMKL (sigmoid) are also observed in this experiment. Table 6 gives the performance values of all algorithms on the P ROTEIN data set with a larger set of kernels, namely, (C OM-S EC-H YD-VOL-P OL-P LZ-L1-L4-L14-L30-B LO-PAM). All combination algorithms except RBMKL (product) outperform SVM (best) by more than three per cent in terms of average test accuracy. NLMKL ( p = 1) and NLMKL ( p = 2) are the only two algorithms that obtain more than 87 per cent average test accuracy. In this experiment, ABMKL (ratio), GMKL, GLMKL ( p = 1), GLMKL ( p = 2), NLMKL ( p = 1), NLMKL ( p = 2), and LMKL (sigmoid) are statistically signiﬁcantly more accurate than SVM (best), SVM (all), and RBMKL (mean). As noted in the two previous experiments, the nonlinear combination algorithms, namely, RBMKL (product), NLMKL ( p = 1), and NLMKL ( p = 2), store statistically signiﬁcantly more support vectors than all other algorithms. ABMKL (conic), ABMKL (convex), CABMKL (linear), CABMKL (conic), MKL, SimpleMKL, and GMKL are the seven MKL algorithms that perform kernel selection and use fewer than 12 kernels on the average, while others use all 12 kernels, except GLMKL ( p = 1) which uses 11 kernels in one of 30 folds. Similar to the results of the two previous experiments, GLMKL ( p = 1) and GLMKL ( p = 2) solve statistically signiﬁcantly fewer optimization problems than all the other two-step algorithms, but the very high standard deviations for LMKL (softmax) and LMKL (sigmoid) are not observed in this experiment. 2245 ¨ G ONEN AND A LPAYDIN Algorithm Test Accuracy Support Vector Active Kernel Calls to Solver SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL ( p = 1) GLMKL ( p = 2) NLMKL ( p = 1) NLMKL ( p = 2) LMKL (softmax) LMKL (sigmoid) 72.06±0.74 bc 79.13±0.45a c 78.01±0.63 72.35±0.95 bc 79.03±0.92a c 76.90±1.17abc 78.06±0.62 79.51±0.78abc 79.28±0.97a c 76.38±1.19abc 76.34±1.24abc 74.96±0.50abc 77.71±0.96 77.20±0.42abc 83.49±0.76abc 82.30±0.62abc 80.24±1.37abc 81.91±0.92abc 58.29±1.00 bc 62.14±1.04a c 60.89±1.02 100.00±0.00abc 49.96±1.01abc 29.54±0.89abc 56.95±1.07abc 49.81±0.82abc 49.84±0.77abc 29.65±1.02abc 29.62±1.08abc 79.85±0.70abc 55.80±0.95abc 75.34±0.70abc 85.67±0.86abc 89.57±0.77abc 27.24±1.76abc 30.95±2.74abc 1.00±0.00 bc 6.00±0.00 6.00±0.00 6.00±0.00 4.60±0.50abc 6.00±0.00 6.00±0.00 5.97±0.18abc 4.73±0.52abc 6.00±0.00 6.00±0.00 2.37±0.56abc 6.00±0.00 6.00±0.00 6.00±0.00 6.00±0.00 6.00±0.00 6.00±0.00 6.00± 0.00 bc 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 18.83± 4.27abc 37.10± 3.23abc 6.10± 0.31abc 5.00± 0.00abc 17.50± 0.51abc 13.40± 4.41abc 85.27±41.77abc 103.90±62.69abc Table 4: Performances of single-kernel SVM and representative MKL algorithms on the P ROTEIN data set with (C OM-S EC-H YD-VOL-P OL-P LZ) using the linear kernel. Algorithm Test Accuracy Support Vector Active Kernel Calls to Solver SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL ( p = 1) GLMKL ( p = 2) NLMKL ( p = 1) NLMKL ( p = 2) LMKL (softmax) LMKL (sigmoid) 72.15±0.68 bc 79.63±0.74a c 81.32±0.74 53.04±0.21abc 80.45±0.68abc 77.47±0.62abc 76.22±1.14abc 77.15±0.63abc 81.02±0.67 79.74±1.02a c 74.53±0.90abc 74.68±0.68abc 79.77±0.86a c 78.00±0.43abc 85.38±0.70abc 85.40±0.69abc 81.11±1.82 81.90±2.01 47.50±1.25 bc 43.45±1.00a c 61.67±1.31 100.00±0.00abc 48.16±1.08abc 87.86±0.76abc 35.54±1.01abc 73.84±0.80abc 48.32±0.86abc 56.00±0.85abc 80.22±1.05abc 80.36±0.83abc 55.94±0.93abc 72.49±1.00abc 93.84±0.51abc 93.86±0.51abc 36.00±3.61abc 51.94±2.14abc 1.00±0.00 bc 10.00±0.00 10.00±0.00 10.00±0.00 6.90±0.66abc 9.03±0.61abc 10.00±0.00 9.90±0.31abc 6.93±0.74abc 8.73±0.52abc 4.73±1.14abc 5.73±0.91abc 10.00±0.00 10.00±0.00 10.00±0.00 10.00±0.00 10.00±0.00 10.00±0.00 10.00± 0.00 bc 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 23.83± 7.46abc 29.10± 8.47abc 6.87± 0.57abc 5.03± 0.18abc 14.77± 0.43abc 18.00± 0.00abc 34.40±23.12abc 31.63±13.17abc Table 5: Performances of single-kernel SVM and representative MKL algorithms on the P ROTEIN data set with (C OM-S EC-H YD-VOL-P OL-P LZ-L1-L4-L14-L30) using the linear kernel. 2246 M ULTIPLE K ERNEL L EARNING A LGORITHMS Algorithm Test Accuracy Support Vector Active Kernel Calls to Solver SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL ( p = 1) GLMKL ( p = 2) NLMKL ( p = 1) NLMKL ( p = 2) LMKL (softmax) LMKL (sigmoid) 78.37±1.08 bc 82.01±0.76a c 83.57±0.59 53.04±0.21abc 83.52±0.94 83.76±1.02 85.65±0.67abc 83.48±0.92 83.43±0.95 83.55±1.25 83.96±1.20 85.67±0.91abc 85.96±0.96abc 85.02±1.20abc 87.00±0.66abc 87.28±0.65abc 83.72±1.35 85.06±0.83abc 93.09±0.73 bc 89.32±0.99a c 65.94±0.93 100.00±0.00abc 63.07±1.35abc 64.36±1.56abc 57.87±1.24abc 68.00±1.48abc 62.12±1.63abc 81.75±1.06abc 86.41±0.98abc 79.53±2.71abc 79.06±1.04abc 62.06±1.02abc 96.78±0.32abc 96.64±0.32abc 37.55±2.54abc 48.99±1.59abc 1.00±0.00 bc 12.00±0.00 12.00±0.00 12.00±0.00 7.30±0.88abc 6.87±0.94abc 12.00±0.00 11.87±0.35abc 8.43±0.73abc 7.67±0.76abc 9.83±0.91abc 9.93±0.74abc 11.97±0.18abc 12.00±0.00 12.00±0.00 12.00±0.00 12.00±0.00 12.00±0.00 12.00± 0.00 bc 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 54.53± 9.92abc 47.40±10.81abc 14.77± 0.57abc 5.60± 0.67abc 4.83± 0.38abc 17.77± 0.43abc 25.97± 5.75abc 25.40± 9.36abc Table 6: Performances of single-kernel SVM and representative MKL algorithms on the P ROTEIN data set with (C OM-S EC-H YD-VOL-P OL-P LZ-L1-L4-L14-L30-B LO-PAM) using the linear kernel. 4.4 Pendigits Digit Recognition Experiments We perform experiments on the Pendigits (P ENDIGITS) digit recognition data set5 from the MKL Repository, composed of four different feature representations for 10,992 instances (7,494 for training and 3,498 for testing). The properties of these feature representations are summarized in Table 7. Two binary classiﬁcation problems are generated from the P ENDIGITS data set: In the P ENDIGITS EO data set, we separate even digits from odd digits; in the P ENDIGITS -SL data set, we separate small (‘0’ - ‘4’) digits from large (‘5’ - ‘9’) digits. Name Dimension DYN S TA 4 S TA 8 S TA 16 16 16 64 256 Data Source 8 successive pen points on two-dimensional coordinate system 4 × 4 image bitmap representation 8 × 8 image bitmap representation 16 × 16 image bitmap representation Table 7: Multiple feature representations in the P ENDIGITS data set. Table 8 summarizes the performance values of all algorithms on the P ENDIGITS -EO data set. We see that SVM (best) is outperformed (by more than three per cent) by all other algorithms in 5. Available at http://mkl.ucsd.edu/dataset/pendigits. 2247 ¨ G ONEN AND A LPAYDIN terms of average test accuracy, which implies that integrating different information sources helps. RBMKL (product), NLMKL ( p = 1), NLMKL ( p = 2), LMKL (softmax), and LMKL (sigmoid) achieve statistically signiﬁcantly higher average test accuracies than the other MKL algorithms. NLMKL ( p = 1) and NLMKL ( p = 2) are the only two algorithms that get more than 99 percent average test accuracy and improve the average test accuracy of RBMKL (mean) statistically signiﬁcantly, by nearly six per cent. When we look at the percentages of support vectors stored, we see that RBMKL (product) stores statistically signiﬁcantly more support vectors than the other algorithms, whereas LMKL (softmax) and LMKL (sigmoid) store statistically signiﬁcantly fewer support vectors. All combination algorithms except ABMKL (convex) use four kernels in all folds. All two-step algorithms except LMKL (softmax) and LMKL (sigmoid) need to solve less than 15 SVM optimization problems on the average. As observed before, LMKL (softmax) and LMKL (sigmoid) have very high standard deviations in the number of SVM optimization calls due to the random initialization of the gating model parameters; note that convergence may be slow at times, but the standard deviations of the test accuracy are small. Table 9 lists the performance values of all algorithms on the P ENDIGITS -SL data set. We again see that SVM (best) is outperformed (more than ﬁve per cent) by all other algorithms in terms of average test accuracy. RBMKL (product), NLMKL ( p = 1), NLMKL ( p = 2), LMKL (softmax), and LMKL (sigmoid) achieve statistically signiﬁcantly higher average test accuracies than the other MKL algorithms. Similar to the results on the P ENDIGITS -EO data set, NLMKL ( p = 1) and NLMKL ( p = 2) are the only two algorithms that get more than 99 percent average test accuracy by improving the average test accuracy of RBMKL (mean) nearly eight per cent for this experiment. As observed on the P ENDIGITS -EO data set, we see that RBMKL (product) stores statistically signiﬁcantly more support vectors than the other algorithms, whereas LMKL (softmax) and LMKL (sigmoid) store fewer support vectors. All combination algorithms except ABMKL (convex) use four kernels in all folds, whereas this latter uses exactly three kernels in all folds by eliminating S TA 8 representation. All two-step algorithms except LMKL (softmax) and LMKL (sigmoid) need to solve less than 20 SVM optimization problems on the average. GLMKL ( p = 1) and GLMKL ( p = 2) solve statistically signiﬁcantly fewer SVM problems than the other two-step algorithms. 4.5 Multiple Features Digit Recognition Experiments We perform experiments on the Multiple Features (M ULTI F EAT) digit recognition data set6 from the UCI Machine Learning Repository, composed of six different feature representations for 2,000 handwritten numerals. The properties of these feature representations are summarized in Table 10. Two binary classiﬁcation problems are generated from the M ULTI F EAT data set: In the M ULTI F EATEO data set, we separate even digits from odd digits; in the M ULTI F EAT-SL data set, we separate small (‘0’ - ‘4’) digits from large (‘5’ - ‘9’) digits. We do two experiments on these data set using two different subsets of feature representations. Table 11 gives the performance values of all algorithms on the M ULTI F EAT-EO data set with (F OU-K AR-P IX-Z ER). Though all algorithms except CABMKL (linear) have higher average test accuracies than SVM (best); only LMKL (sigmoid) is statistically signiﬁcantly more accurate than SVM (best), SVM (all), and RBMKL (mean). Note that even though RBMKL (product) is not more accurate than SVM (all) or RBMKL (mean), nonlinear and data-dependent algorithms, namely, NLMKL ( p = 1), NLMKL ( p = 2), LMKL (softmax), and LMKL (sigmoid), are more accurate than these two 6. Available at http://archive.ics.uci.edu/ml/datasets/Multiple+Features. 2248 M ULTIPLE K ERNEL L EARNING A LGORITHMS Algorithm Test Accuracy Support Vector Active Kernel Calls to Solver SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL ( p = 1) GLMKL ( p = 2) NLMKL ( p = 1) NLMKL ( p = 2) LMKL (softmax) LMKL (sigmoid) 88.93±0.28 bc 92.12±0.42a c 93.34±0.28 98.46±0.16abc 93.40±0.15 93.53±0.26 93.35±0.20 93.42±0.16 93.42±0.16 93.28±0.29 93.29±0.27 93.28±0.26 93.34±0.27 93.32±0.25 99.36±0.08abc 99.38±0.07abc 97.14±0.39abc 97.80±0.20abc 20.90±1.22 c 22.22±0.72 c 18.91±0.67 51.08±0.48abc 17.52±0.73abc 13.83±0.75abc 18.89±0.68 17.48±0.74abc 17.48±0.74abc 19.20±0.67 bc 19.04±0.71 19.08±0.72 19.02±0.73 16.91±0.61abc 19.55±0.48 19.79±0.52 7.25±0.65abc 11.71±0.71abc 1.00±0.00 bc 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 3.90±0.32abc 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00± 0.00 bc 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 8.70± 3.92abc 8.60± 3.66abc 3.20± 0.63abc 3.80± 0.42abc 11.60± 6.26abc 10.90± 4.31abc 97.70±55.48abc 87.70±47.30abc Table 8: Performances of single-kernel SVM and representative MKL algorithms on the P ENDIGITS -EO data set using the linear kernel. Algorithm Test Accuracy Support Vector Active Kernel Calls to Solver SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL ( p = 1) GLMKL ( p = 2) NLMKL ( p = 1) NLMKL ( p = 2) LMKL (softmax) LMKL (sigmoid) 84.44±0.49 bc 89.48±0.67a c 91.11±0.34 98.37±0.11abc 90.97±0.49 90.85±0.51 91.12±0.32 91.02±0.47 91.02±0.47 90.85±0.45 90.84±0.50 90.85±0.47 90.90±0.46 91.12±0.44 99.11±0.10abc 99.07±0.12abc 97.77±0.54abc 97.13±0.40abc 39.31±0.77 bc 19.55±0.61a c 16.22±0.59 60.28±0.69abc 20.93±0.46abc 24.59±0.69abc 16.23±0.57 20.89±0.49abc 20.90±0.50abc 23.59±0.56abc 23.48±0.55abc 23.46±0.54abc 23.33±0.57abc 20.40±0.55abc 17.37±0.17 17.66±0.23 5.72±0.46abc 6.69±0.27abc 1.00±0.00 bc 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 3.00±0.00abc 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00± 0.00 bc 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 14.50± 3.92abc 15.60± 3.34abc 4.90± 0.57abc 4.00± 0.00 bc 18.10± 0.32abc 10.90± 3.70abc 116.60±73.34abc 119.00±45.04abc Table 9: Performances of single-kernel SVM and representative MKL algorithms on the P ENDIGITS -SL data set using the linear kernel. 2249 ¨ G ONEN AND A LPAYDIN Name Dimension FAC F OU K AR M OR P IX Z ER 216 76 64 6 240 47 Data Source Proﬁle correlations Fourier coefﬁcients of the shapes Karhunen-Lo` ve coefﬁcients e Morphological features Pixel averages in 2 × 3 windows Zernike moments Table 10: Multiple feature representations in the M ULTI F EAT data set. Algorithm Test Accuracy Support Vector Active Kernel Calls to Solver SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL ( p = 1) GLMKL ( p = 2) NLMKL ( p = 1) NLMKL ( p = 2) LMKL (softmax) LMKL (sigmoid) 95.96±0.50 bc 97.79±0.25 97.94±0.29 96.43±0.38 bc 97.85±0.25 95.97±0.57 bc 97.82±0.32 95.78±0.37 bc 97.85±0.25 97.88±0.31 97.87±0.32 97.88±0.31 97.90±0.25 98.01±0.24 98.67±0.22 98.61±0.24 98.16±0.50 98.94±0.29abc 21.37±0.81 c 21.63±0.73 c 23.42±0.79 92.11±1.18abc 19.40±1.02abc 21.45±0.92 c 22.33±0.57 bc 19.25±1.09 bc 19.37±1.03abc 21.01±0.87 c 20.90±0.94 c 21.00±0.88 c 21.31±0.78 c 19.19±0.61 bc 56.91±1.17abc 53.61±1.20abc 17.40±1.17abc 15.23±1.08abc 1.00±0.00 bc 4.00±0.00 4.00±0.00 4.00±0.00 2.00±0.00abc 1.20±0.42 bc 4.00±0.00 4.00±0.00 2.00±0.00abc 3.50±0.53abc 3.40±0.70abc 3.50±0.53abc 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00± 0.00 bc 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 22.50± 6.65abc 25.90±10.05abc 11.10± 0.74abc 4.90± 0.32abc 4.50± 1.84 bc 5.60± 3.03 bc 36.70±14.11abc 88.20±36.00abc Table 11: Performances of single-kernel SVM and representative MKL algorithms on the M ULTI F EAT-EO data set with (F OU-K AR-P IX-Z ER) using the linear kernel. algorithms. Alignment-based and centered-alignment-based MKL algorithms, namely, ABMKL (ratio), ABMKL (conic), ABMKL (convex), CABMKL (linear) and CABMKL (convex), are not more accurate than RBMKL (mean). We see that ABMKL (convex) and CABMKL (linear) are statistically significantly less accurate than SVM (all) and RBMKL (mean). If we compare the algorithms in terms of support vector percentages, we note that MKL algorithms that use products of the combined kernels, namely, RBMKL (product), NLMKL ( p = 1), and NLMKL ( p = 2), store statistically signiﬁcantly more support vectors than all other algorithms. If we look at the active kernel counts, 10 out of 16 MKL algorithms use all four kernels. The two-step algorithms solve statistically signiﬁcantly more optimization problems than the one-step algorithms. Table 12 summarizes the performance values of all algorithms on the M ULTI F EAT-EO data set with (FAC-F OU-K AR-M OR-P IX-Z ER). We note that NLMKL ( p = 1) and LMKL (sigmoid) are the 2250 M ULTIPLE K ERNEL L EARNING A LGORITHMS two MKL algorithms that achieve average test accuracy greater than or equal to 99 per cent, while NLMKL ( p = 1), NLMKL ( p = 2), and LMKL (sigmoid) are statistically signiﬁcantly more accurate than RBMKL (mean). All other MKL algorithms except RBMKL (product) and CABMKL (linear) achieve average test accuracies between 98 per cent and 99 per cent. Similar to the results of the previous experiment, RBMKL (product), NLMKL ( p = 1), and NLMKL ( p = 2) store statistically signiﬁcantly more support vectors than all other algorithms. When we look at the number of active kernels, ABMKL (convex) selects only one kernel and this is the same kernel that SVM (best) picks. ABMKL (conic) and CABMKL (conic) use three kernels, whereas all other algorithms use more than ﬁve kernels on the average. GLMKL ( p = 1), GLMKL ( p = 2), NLMKL ( p = 1), and NLMKL ( p = 2) solve fewer optimization problems than the other two-step algorithms, namely, SimpleMKL, GMKL, LMKL (softmax), and LMKL (sigmoid). Table 13 lists the performance values of all algorithms on the M ULTI F EAT-SL data set with (F OU-K AR-P IX-Z ER). SVM (best) is outperformed by the other algorithms on the average and this shows that, for this data set, combining multiple information sources, independently of the combination algorithm used, improves the average test accuracy. RBMKL (product), NLMKL ( p = 1), NLMKL ( p = 2), and LMKL (sigmoid) are the four MKL algorithms that achieve statistically signiﬁcantly higher average test accuracies than RBMKL (best), SVM (all), RBMKL (mean). NLMKL ( p = 1) and NLMKL ( p = 2) are the two best algorithms and are statistically signiﬁcantly more accurate than all other algorithms, except LMKL (sigmoid). However, NLMKL ( p = 1) and NLMKL ( p = 2) store statistically signiﬁcantly more support vectors than all other algorithms, except RBMKL (product). All MKL algorithms use all of the kernels and the two-step algorithms solve statistically signiﬁcantly more optimization problems than the one-step algorithms. Table 14 gives the performance values of all algorithms on the M ULTI F EAT-SL data set with (FAC-F OU-K AR-M OR-P IX-Z ER). GLMKL ( p = 2), NLMKL ( p = 1), NLMKL ( p = 2), LMKL (softmax), and LMKL (sigmoid) are the ﬁve MKL algorithms that achieve higher average test accuracies than RBMKL (mean). CABMKL (linear) is the only algorithm that has statistically signiﬁcantly lower average test accuracy than SVM (best). No MKL algorithm achieves statistically signiﬁcantly higher average test accuracies than SVM (best), SVM (all), and RBMKL (mean). MKL algorithms with nonlinear combination rules, namely, RBMKL (product), NLMKL ( p = 1) and NLMKL ( p = 2), again use more support vectors than the other algorithms, whereas LMKL with a data-dependent combination approach stores statistically signiﬁcantly fewer support vectors. ABMKL (conic), ABMKL (convex), and CABMKL (conic) are the three MKL algorithms that perform kernel selection and use fewer than ﬁve kernels on the average, while others use all of the kernels. GLMKL ( p = 1) and GLMKL ( p = 2) solve statistically signiﬁcantly fewer optimization problems than all the other two-step algorithms and the very high standard deviations for LMKL (softmax) and LMKL (sigmoid) are also observed in this experiment. 4.6 Internet Advertisements Experiments We perform experiments on the Internet Advertisements (A DVERT) data set7 from the UCI Machine Learning Repository, composed of ﬁve different feature representations (different bags of words); there is also some additional geometry information of the images, but we ignore them in our experiments due to missing values. After removing the data instances with missing values, we have a total 7. Available at http://archive.ics.uci.edu/ml/datasets/Internet+Advertisements. 2251 ¨ G ONEN AND A LPAYDIN Algorithm Test Accuracy Support Vector Active Kernel Calls to Solver SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL ( p = 1) GLMKL ( p = 2) NLMKL ( p = 1) NLMKL ( p = 2) LMKL (softmax) LMKL (sigmoid) 98.39±0.36 98.24±0.40 98.09±0.31 95.87±0.31abc 98.24±0.38 98.39±0.36 98.19±0.25 96.90±0.34 98.15±0.41 98.31±0.34 98.25±0.37 98.24±0.34 98.28±0.31 98.37±0.28 99.00±0.16 c 98.93±0.18 c 98.34±0.25 99.24±0.18 c 10.30±0.83 bc 14.44±0.74 15.16±0.83 100.00±0.00abc 13.08±0.93 10.30±0.83 bc 14.11±0.64 16.89±0.91abc 12.54±0.75 14.88±0.81 14.89±0.70 14.33±0.85a c 14.44±0.87a c 17.04±0.80abc 47.50±1.27abc 46.78±1.07abc 11.36±1.83 17.88±1.06 1.00±0.00 bc 6.00±0.00 6.00±0.00 6.00±0.00 3.00±0.00abc 1.00±0.00 bc 6.00±0.00 5.90±0.32abc 3.00±0.00abc 5.40±0.70abc 5.60±0.52abc 5.60±0.52abc 6.00±0.00 6.00±0.00 6.00±0.00 6.00±0.00 6.00±0.00 6.00±0.00 6.00± 0.00 bc 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 37.50±12.09abc 31.70±10.79abc 9.30± 1.25abc 4.90± 0.32abc 8.30± 2.71abc 12.00± 3.16abc 94.90±24.73abc 94.90±57.64abc Table 12: Performances of single-kernel SVM and representative MKL algorithms on the M ULTI F EAT-EO data set with (FAC-F OU-K AR-M OR-P IX-Z ER) using the linear kernel. Algorithm Test Accuracy Support Vector Active Kernel Calls to Solver SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL ( p = 1) GLMKL ( p = 2) NLMKL ( p = 1) NLMKL ( p = 2) LMKL (softmax) LMKL (sigmoid) 90.54±1.12 bc 94.45±0.44 95.00±0.76 96.51±0.31abc 95.12±0.36 94.51±0.59 94.93±0.73 95.10±0.38 95.10±0.38 94.81±0.67 94.84±0.64 94.84±0.64 94.84±0.69 95.18±0.32 98.64±0.25abc 98.63±0.28abc 96.24±0.90 97.16±0.60abc 28.90±1.69 bc 40.26±1.28a c 24.73±1.19 95.31±0.60abc 33.44±1.20abc 24.34±1.19 24.88±1.02 33.44±1.24abc 33.44±1.24abc 24.46±1.13 24.40±1.18 24.41±1.18 24.34±1.27 32.34±1.36abc 50.17±1.31abc 57.02±1.26abc 24.16±3.29 20.18±1.06abc 1.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 4.00±0.00 bc 4.00± 0.00 bc 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 15.50± 8.11abc 15.60± 8.07abc 6.20± 1.03abc 4.20± 0.63 bc 9.20± 4.80abc 9.10± 3.28abc 41.70±31.28abc 75.50±28.38abc Table 13: Performances of single-kernel SVM and representative MKL algorithms on the M ULTI F EAT-SL data set with (F OU-K AR-P IX-Z ER) using the linear kernel. 2252 M ULTIPLE K ERNEL L EARNING A LGORITHMS Algorithm Test Accuracy Support Vector Active Kernel Calls to Solver SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL ( p = 1) GLMKL ( p = 2) NLMKL ( p = 1) NLMKL ( p = 2) LMKL (softmax) LMKL (sigmoid) 94.99±0.85 bc 97.69±0.44 97.67±0.50 96.01±0.17 bc 96.84±0.39 96.46±0.34 97.66±0.46 89.18±0.81abc 96.84±0.39 97.40±0.37 97.51±0.37 97.51±0.35 97.51±0.28 97.81±0.22 98.79±0.28 98.82±0.20 97.79±0.62 98.48±0.70 17.96±0.89 bc 23.34±1.13 20.98±0.84 97.58±0.48abc 27.49±0.92abc 33.78±0.90abc 20.95±0.88 57.22±1.47abc 27.57±0.95abc 32.59±0.82abc 32.53±0.94abc 32.73±1.01abc 32.49±0.93abc 25.19±1.06abc 38.44±0.96abc 43.99±0.99abc 14.71±1.10 bc 16.10±2.09 bc 1.00±0.00 bc 6.00±0.00 6.00±0.00 6.00±0.00 4.50±0.53abc 4.60±0.52abc 6.00±0.00 6.00±0.00 4.50±0.53abc 6.00±0.00 6.00±0.00 6.00±0.00 6.00±0.00 6.00±0.00 6.00±0.00 6.00±0.00 6.00±0.00 6.00±0.00 6.00± 0.00 bc 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 14.40± 3.27abc 14.20± 4.59abc 6.70± 0.95 bc 5.00± 0.82abc 12.10± 3.98abc 10.70± 4.62abc 59.00±31.42abc 107.60±76.90abc Table 14: Performances of single-kernel SVM and representative MKL algorithms on the M ULTI F EAT-SL data set with (FAC-F OU-K AR-M OR-P IX-Z ER) using the linear kernel. of 3,279 images in the data set. The properties of these feature representations are summarized in Table 15. The classiﬁcation task is to predict whether an image is an advertisement or not. Name URL O RIG URL A NC URL A LT C APTION Dimension 457 495 472 111 19 Data Source Phrases occurring in the URL Phrases occurring in the URL of the image Phrases occurring in the anchor text Phrases occurring in the alternative text Phrases occurring in the caption terms Table 15: Multiple feature representations in the A DVERT data set. Table 16 lists the performance values of all algorithms on the A DVERT data set. We can see that all MKL algorithms except RBMKL (product) achieve similar average test accuracies. However, no MKL algorithm is statistically signiﬁcantly more accurate than RBMKL (mean), and ABMKL (convex) is statistically signiﬁcantly worse. We see again that algorithms that combine kernels by multiplying them, namely, RBMKL (product), NLMKL ( p = 1), and NLMKL ( p = 2), store statistically signiﬁcantly more support vectors than other MKL algorithms. 10 out of 16 MKL algorithms use all ﬁve kernels; ABMKL (conic) and ABMKL (convex) eliminate two representations, namely, URL and O RIG URL. GMKL (p = 1) and GMKL ( p = 2) solve statistically signiﬁcantly fewer optimization problems than the other two-step algorithms. 2253 ¨ G ONEN AND A LPAYDIN Algorithm Test Accuracy Support Vector Active Kernel Calls to Solver SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL ( p = 1) GLMKL ( p = 2) NLMKL ( p = 1) NLMKL ( p = 2) LMKL (softmax) LMKL (sigmoid) 95.45±0.31 96.43±0.24 96.53±0.58 89.98±0.49abc 95.69±0.27 95.10±0.52 bc 96.23±0.61 95.86±0.19 95.84±0.19 96.32±0.50 96.37±0.46 96.40±0.49 96.35±0.55 96.56±0.32 95.96±0.50 96.13±0.31 95.68±0.53 95.49±0.48 64.90± 5.41 bc 41.99± 1.76 34.40± 4.25 96.61± 1.71abc 44.16± 2.65a c 58.07± 2.47 bc 35.07± 2.92 36.43± 1.50 38.06± 2.36 35.82± 4.35 33.78± 4.40 33.18± 3.49 32.81± 3.56 35.62± 1.55 67.63± 3.46 bc 65.70± 3.03 bc 24.18± 5.74 18.22±12.16 1.00±0.00 bc 5.00±0.00 5.00±0.00 5.00±0.00 3.00±0.00abc 3.00±0.00abc 5.00±0.00 5.00±0.00 4.40±0.52abc 4.10±0.32abc 4.60±0.52abc 4.70±0.48abc 5.00±0.00 5.00±0.00 5.00±0.00 5.00±0.00 5.00±0.00 5.00±0.00 5.00± 0.00 bc 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 1.00± 0.00 27.00± 7.39abc 27.20± 7.94abc 5.40± 1.07 bc 4.90± 0.74 bc 15.90± 5.38abc 13.00± 0.00abc 38.80±24.11abc 56.60±53.70abc Table 16: Performances of single-kernel SVM and representative MKL algorithms on the ADVERT data set using the linear kernel. 4.7 Overall Comparison After comparing algorithms for each experiment separately, we give an overall comparison on 10 experiments using the nonparametric Friedman’s test on rankings with the Tukey’s honestly significant difference criterion as the post-hoc test (Demˇar, 2006). s Figure 2 shows the overall comparison between the algorithms in terms of misclassiﬁcation error. First of all, we see that combining multiple information sources clearly improves the classiﬁcation performance because SVM (best) is worse than all other algorithms. GLMKL ( p = 2), NLMKL ( p = 1), NLMKL ( p = 2), LMKL (softmax), and LMKL (sigmoid) are statistically signiﬁcantly more accurate than SVM (best). MKL algorithms using a trained, weighted combination on the average seem a little worse (but not statistically signiﬁcantly) than the untrained, unweighted sum, namely, RBMKL (mean). NLMKL ( p = 1), NLMKL ( p = 2), LMKL (softmax), and LMKL (sigmoid) are more accurate (but not statistically signiﬁcantly) than RBMKL (mean). These results seem to suggest that if we want to improve the classiﬁcation accuracy of MKL algorithms, we should investigate nonlinear and data-dependent approaches to better exploit information provided by different kernels. Figure 3 illustrates the overall comparison between the algorithms in terms of the support vector percentages. We note that algorithms are clustered into three groups: (a) nonlinear MKL algorithms, (b) single-kernel SVM and linear MKL algorithms, and (c) data-dependent MKL algorithms. Nonlinear MKL algorithms, namely, RBMKL (product), NLMKL ( p = 1) and NLMKL ( p = 2), store more (but not statistically signiﬁcantly) support vectors than single-kernel SVM and linear MKL algorithms, whereas they store statistically signiﬁcantly more support vectors than 2254 M ULTIPLE K ERNEL L EARNING A LGORITHMS SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL (p = 1) GLMKL (p = 2) NLMKL (p = 1) NLMKL (p = 2) LMKL (softmax) LMKL (sigmoid) −5 0 5 10 rank 15 20 25 Figure 2: Overall comparison of single-kernel SVM and representative MKL algorithms in terms of misclassiﬁcation error using the linear kernel. SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL (p = 1) GLMKL (p = 2) NLMKL (p = 1) NLMKL (p = 2) LMKL (softmax) LMKL (sigmoid) −5 0 5 10 rank 15 20 25 Figure 3: Overall comparison of single-kernel SVM and representative MKL algorithms in terms of support vector percentages using the linear kernel. 2255 ¨ G ONEN AND A LPAYDIN data-dependent MKL algorithms. Data-dependent MKL algorithms, namely, LMKL (softmax) and LMKL (sigmoid), store fewer (but not statistically signiﬁcantly) support vectors than single-kernel SVM and linear MKL algorithms, whereas LMKL (softmax) stores statistically signiﬁcantly fewer support vectors than SVM (best) and SVM (all). Figure 4 gives the overall comparison between the algorithms in terms of active kernel counts. We see that ABMKL (conic), ABMKL (convex), CABMKL (linear), CABMKL (conic), MKL, SimpleMKL, and GMKL use fewer kernels (statistically signiﬁcantly in the case of the ﬁrst two algorithms) than other combination algorithms. Even if we optimize the alignment and centered-alignment measures without any regularization on kernel weights using ABMKL (conic), ABMKL (convex), and CABMKL (conic), we obtain more sparse (but not statistically signiﬁcantly) kernel combinations than MKL and SimpleMKL, which regularize kernel weights using the ℓ1 -norm. Trained nonlinear and datadependent MKL algorithms, namely, NLMKL ( p = 1), NLMKL ( p = 2), LMKL (softmax), and LMKL (sigmoid), tend to use all of the kernels without eliminating any of them, whereas data-dependent algorithms use the kernels in different parts of the feature space with the help of the gating model. Figure 5 shows the overall comparison between the algorithms in terms of the optimization toolbox call counts. We clearly see that the two-step algorithms need to solve more optimization problems than the other combination algorithms. SimpleMKL, GMKL, NLMKL ( p = 1), NLMKL ( p = 2), LMKL (softmax), and LMKL (sigmoid) require solving statistically signiﬁcantly more optimization problems than the one-step algorithms, whereas the differences between the one-step algorithms and GLMKL ( p = 1) and GLMKL ( p = 2) are not statistically signiﬁcant. 4.8 Overall Comparison Using Gaussian Kernel We also replicate the same set of experiments, except on P ENDIGITS data set, using√ three different √ Gaussian kernels for each feature representation. We select the kernel widths as { Dm /2, Dm , √ 2 Dm } where Dm is the dimensionality of the corresponding feature representation. Figure 6 shows the overall comparison between the algorithms in terms of misclassiﬁcation error. We see that no MKL algorithm is statistically signiﬁcantly better than RBMKL (mean) and conclude that combining complex Gaussian kernels does not help much. ABMKL (ratio), MKL, SimpleMKL, GMKL, GLMKL ( p = 1), and GLMKL ( p = 2) obtain accuracy results comparable to RBMKL (mean). As an important result, we see that nonlinear and data-dependent MKL algorithms, namely, NLMKL ( p = 1), NLMKL ( p = 2), LMKL (softmax), and LMKL (sigmoid), are outperformed (but not statistically signiﬁcantly) by RBMKL (mean). If we have highly nonlinear kernels such as Gaussian kernels, there is no need to combine them in a nonlinear or data-dependent way. Figure 7 illustrates the overall comparison between the algorithms in terms of the support vector percentages. Different from the results obtained with simple linear kernels, algorithms do not exhibit a clear grouping. However, data-dependent MKL algorithms, namely, LMKL (softmax) and LMKL (sigmoid), tend to use fewer support vectors, whereas nonlinear MKL algorithms, namely, RBMKL (product), NLMKL ( p = 1), and NLMKL ( p = 2), tend to store more support vectors than other algorithms. Figure 8 gives the overall comparison between the algorithms in terms of active kernel counts. ABMKL (ratio), GLMKL ( p = 2), NLMKL ( p = 1), NLMKL ( p = 2), and LMKL (sigmoid) do not eliminate any of the base kernels even though we have three different kernels for each feature representation. When combining complex Gaussian kernels, trained MKL algorithms do not improve the classiﬁcation performance statistically signiﬁcantly, but they can eliminate some of the kernels. 2256 M ULTIPLE K ERNEL L EARNING A LGORITHMS SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL (p = 1) GLMKL (p = 2) NLMKL (p = 1) NLMKL (p = 2) LMKL (softmax) LMKL (sigmoid) −4 −2 0 2 4 6 rank 8 10 12 14 16 Figure 4: Overall comparison of single-kernel SVM and representative MKL algorithms in terms of active kernel counts using the linear kernel. SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL (p = 1) GLMKL (p = 2) NLMKL (p = 1) NLMKL (p = 2) LMKL (softmax) LMKL (sigmoid) 0 5 10 15 20 25 rank Figure 5: Overall comparison of single-kernel SVM and representative MKL algorithms in terms of optimization toolbox call counts using the linear kernel. 2257 ¨ G ONEN AND A LPAYDIN SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL (p = 1) GLMKL (p = 2) NLMKL (p = 1) NLMKL (p = 2) LMKL (softmax) LMKL (sigmoid) −5 0 5 10 rank 15 20 25 Figure 6: Overall comparison of single-kernel SVM and representative MKL algorithms in terms of misclassiﬁcation error using the Gaussian kernel. SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL (p = 1) GLMKL (p = 2) NLMKL (p = 1) NLMKL (p = 2) LMKL (softmax) LMKL (sigmoid) −5 0 5 10 rank 15 20 25 Figure 7: Overall comparison of single-kernel SVM and representative MKL algorithms in terms of support vector percentages using the Gaussian kernel. 2258 M ULTIPLE K ERNEL L EARNING A LGORITHMS SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL (p = 1) GLMKL (p = 2) NLMKL (p = 1) NLMKL (p = 2) LMKL (softmax) LMKL (sigmoid) −5 0 5 10 15 20 rank Figure 8: Overall comparison of single-kernel SVM and representative MKL algorithms in terms of active kernel counts using the Gaussian kernel. SVM (best) SVM (all) RBMKL (mean) RBMKL (product) ABMKL (conic) ABMKL (convex) ABMKL (ratio) CABMKL (linear) CABMKL (conic) MKL SimpleMKL GMKL GLMKL (p = 1) GLMKL (p = 2) NLMKL (p = 1) NLMKL (p = 2) LMKL (softmax) LMKL (sigmoid) 0 5 10 15 20 25 rank Figure 9: Overall comparison of single-kernel SVM and representative MKL algorithms in terms of optimization toolbox call counts using the Gaussian kernel. 2259 ¨ G ONEN AND A LPAYDIN We see that ABMKL (conic), ABMKL (convex), CABMKL (conic), MKL, SimpleMKL, GMKL, GLMKL ( p = 1), and LMKL (softmax) use fewer kernels (statistically signiﬁcantly in the case of the ﬁrst three algorithms) than other combination algorithms. Figure 9 shows the overall comparison between the algorithms in terms of the optimization toolbox call counts. Similar to the previous results obtained with simple linear kernels, the two-step algorithms need to solve more optimization problems than the other combination algorithms. 5. Conclusions There is a signiﬁcant amount of work on multiple kernel learning methods. This is because in many applications, one can come up with many possible kernel functions and instead of choosing one among them, we are interested in an algorithm that can automatically determine which ones are useful, which ones are not and therefore can be pruned, and combine the useful ones. Or, in some applications, we may have different sources of information coming from different modalities or corresponding to results from different experimental methodologies and each has its own (possibly multiple) kernel(s). In such a case, a good procedure for kernel combination implies a good combination of inputs from those multiple sources. In this paper, we give a taxonomy of multiple kernel learning algorithms to best highlight the similarities and differences among the proposed algorithms in the literature, which we then review in detail. The dimensions we compare the existing MKL algorithms are the learning method, the functional form, the target function, the training method, the base learner, and the computational complexity. Then by looking at these dimensions, we form 12 groups of MKL variants to allow an organized discussion of the literature. We also perform 10 experiments on four real data sets with simple linear kernels and eight experiments on three real data sets with complex Gaussian kernels comparing 16 MKL algorithms in practice. When combining simple linear kernels, in terms of accuracy, we see that using multiple kernels is better than using a single one but that in combination, trained linear combination is not always better than an untrained, unweighted combination and that nonlinear or data-dependent combination seem more promising. When combining complex Gaussian kernels, trained linear combination is better than nonlinear and data-dependent combinations but not than unweighted combination. Some MKL variants may be preferred because they use fewer support vectors or fewer kernels or need fewer calls to the optimizer during training. The relative importance of these criteria depend on the application at hand. We conclude that multiple kernel learning is useful in practice and that there is ample evidence that better MKL algorithms can be devised for improved accuracy, decreased complexity and training time. Acknowledgments The authors would like to thank the editor and the three anonymous reviewers for their constructive comments, which signiﬁcantly improved the presentation of the paper. This work was supported by the Turkish Academy of Sciences in the framework of the Young Scientist Award Program un¨ der EA-TUBA-GEB˙ IP/2001-1-1, Bo˘ azici University Scientiﬁc Research Project 07HA101 and g ¸ ¨ ITAK) under Grant EEEAG the Scientiﬁc and Technological Research Council of Turkey (TUB˙ 2260 M ULTIPLE K ERNEL L EARNING A LGORITHMS ¨ ITAK. 107E222. The work of M. G¨ nen was supported by the Ph.D. scholarship (2211) from TUB˙ o M. G¨ nen is currently at the Department of Information and Computer Science, Aalto University o School of Science and the Helsinki Institute for Information Technology (HIIT), Finland. Appendix A. List of Acronyms GMKL GP KFDA KL KRR LMKL LP MKL QCQP QP RKDA SDP SILP SMKL SOCP SVM SVR Generalized Multiple Kernel Learning Gaussian Process Kernel Fisher Discriminant Analysis Kullback-Leibler Kernel Ridge Regression Localized Multiple Kernel Learning Linear Programming Multiple Kernel Learning Quadratically Constrained Quadratic Programming Quadratic Programming Regularized Kernel Discriminant Analysis Semideﬁnite Programming Semi-inﬁnite Linear Programming Sparse Multiple Kernel Learning Second-order Cone Programming Support Vector Machine Support Vector Regression Appendix B. List of Notation R R+ R++ RN RM×N SN N Z Z+ Real numbers Nonnegative real numbers Positive real numbers Real N × 1 matrices Real M × N matrices Real symmetric N × N matrices Natural numbers Integers Nonnegative integers x p x, y k(x, y) The ℓ p -norm of vector x Dot product between vectors x and y Kernel function between x and y K X⊤ tr (X) X F X⊙Y Kernel matrix Transpose of matrix X Trace of matrix X Frobenius norm of matrix X Element-wise product between matrices X and Y Ethem Alpaydın. Combined 5 × 2 cv F test for comparing supervised classiﬁcation learning algorithms. Neural Computation, 11(8):1885–1892, 1999. 2261 ¨ G ONEN AND A LPAYDIN Andreas Argyriou, Charles A. Micchelli, and Massimiliano Pontil. Learning convex combinations of continuously parameterized basic kernels. In Proceeding of the 18th Conference on Learning Theory, 2005. Andreas Argyriou, Raphael Hauser, Charles A. Micchelli, and Massimiliano Pontil. A DCprogramming algorithm for kernel selection. In Proceedings of the 23rd International Conference on Machine Learning, 2006. Francis R. Bach. Consistency of the group Lasso and multiple kernel learning. Journal of Machine Learning Research, 9:1179–1225, 2008. Francis R. Bach. Exploring large feature spaces with hierarchical multiple kernel learning. In Advances in Neural Information Processing Systems 21, 2009. Francis R. Bach, Gert R. G. Lanckriet, and Michael I. Jordan. Multiple kernel learning, conic duality, and the SMO algorithm. In Proceedings of the 21st International Conference on Machine Learning, 2004. Asa Ben-Hur and William Stafford Noble. Kernel methods for predicting protein-protein interactions. Bioinformatics, 21(Suppl 1):i38–46, 2005. Kristin P. Bennett, Michinari Momma, and Mark J. Embrechts. MARK: A boosting algorithm for heterogeneous kernel models. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002. Jinbo Bi, Tong Zhang, and Kristin P. Bennett. Column-generation boosting methods for mixture of kernels. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004. Olivier Bousquet and Daniel J. L. Herrmann. On the complexity of learning the kernel matrix. In Advances in Neural Information Processing Systems 15, 2003. Olivier Chapelle and Alain Rakotomamonjy. Second order optimization of kernel parameters. In NIPS Workshop on Automatic Selection of Optimal Kernels, 2008. Olivier Chapelle, Vladimir Vapnik, Olivier Bousquet, and Sayan Mukherjee. Choosing multiple parameters for support vector machines. Machine Learning, 46(1–3):131–159, 2002. Mario Christoudias, Raquel Urtasun, and Trevor Darrell. Bayesian localized multiple kernel learning. Technical Report UCB/EECS-2009-96, University of California at Berkeley, 2009. Domenico Conforti and Rosita Guido. Kernel based support vector machine via semideﬁnite programming: Application to medical diagnosis. Computers and Operations Research, 37(8):1389– 1394, 2010. Corinna Cortes, Mehryar Mohri, and Afshin Rostamizadeh. L2 regularization for learning kernels. In Proceedings of the 25th Conference on Uncertainty in Artiﬁcial Intelligence, 2009. Corinna Cortes, Mehryar Mohri, and Rostamizadeh Afshin. Two-stage learning kernel algorithms. In Proceedings of the 27th International Conference on Machine Learning, 2010a. 2262 M ULTIPLE K ERNEL L EARNING A LGORITHMS Corinna Cortes, Mehryar Mohri, and Afshin Rostamizadeh. Learning non-linear combinations of kernels. In Advances in Neural Information Processing Systems 22, 2010b. Koby Crammer, Joseph Keshet, and Yoram Singer. Kernel design using boosting. In Advances in Neural Information Processing Systems 15, 2003. Nello Cristianini and John Shawe-Taylor. An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods. Cambridge University Press, 2000. Nello Cristianini, John Shawe-Taylor, Andree Elisseef, and Jaz Kandola. On kernel-target alignment. In Advances in Neural Information Processing Systems 14, 2002. Theodoros Damoulas and Mark A. Girolami. Probabilistic multi-class multi-kernel learning: On protein fold recognition and remote homology detection. Bioinformatics, 24(10):1264–1270, 2008. Theodoros Damoulas and Mark A. Girolami. Combining feature spaces for classiﬁcation. Pattern Recognition, 42(11):2671–2683, 2009a. Theodoros Damoulas and Mark A. Girolami. Pattern recognition with a Bayesian kernel combination machine. Pattern Recognition Letters, 30(1):46–54, 2009b. Tijl De Bie, Leon-Charles Tranchevent, Liesbeth M. M. van Oeffelen, and Yves Moreau. Kernelbased data fusion for gene prioritization. Bioinformatics, 23(13):i125–132, 2007. Isaac Mart´n de Diego, Javier M. Moguerza, and Alberto Mu˜ oz. Combining kernel information ı n for support vector classiﬁcation. In Proceedings of the 4th International Workshop Multiple Classiﬁer Systems, 2004. Isaac Mart´n de Diego, Alberto Mu˜ oz, and Javier M. Moguerza. Methods for the combination of ı n kernel matrices within a support vector framework. Machine Learning, 78(1–2):137–174, 2010a. ´ Isaac Mart´n de Diego, Angel Serrano, Cristina Conde, and Enrique Cabello. Face veriﬁcation with ı a kernel fusion method. Pattern Recognition Letters, 31:837–844, 2010b. R´ da Dehak, Najim Dehak, Patrick Kenny, and Pierre Dumouchel. Kernel combination for SVM e speaker veriﬁcation. In Proceedings of the Speaker and Language Recognition Workshop, 2008. Janez Demˇar. Statistical comparisons of classiﬁers over multiple data sets. Journal of Machine s Learning Research, 7:1–30, 2006. Glenn Fung, Murat Dundar, Jinbo Bi, and Bharat Rao. A fast iterative algorithm for Fisher discriminant using heterogeneous kernels. In Proceedings of the 21st International Conference on Machine Learning, 2004. Peter Vincent Gehler and Sebastian Nowozin. Inﬁnite kernel learning. Technical report, Max Planck Institute for Biological Cybernetics, 2008. Mark Girolami and Simon Rogers. Hierarchic Bayesian models for kernel learning. In Proceedings of the 22nd International Conference on Machine Learning, 2005. 2263 ¨ G ONEN AND A LPAYDIN Mark Girolami and Mingjun Zhong. Data integration for classiﬁcation problems employing Gaussian process priors. In Advances in Neural Processing Systems 19, 2007. Mehmet G¨ nen and Ethem Alpaydın. Localized multiple kernel learning. In Proceedings of the o 25th International Conference on Machine Learning, 2008. Yves Grandvalet and St´ phane Canu. Adaptive scaling for feature selection in SVMs. In Advances e in Neural Information Processing Systems 15, 2003. Junfeng He, Shih-Fu Chang, and Lexing Xie. Fast kernel learning for spatial pyramid matching. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2008. Mingqing Hu, Yiqiang Chen, and James Tin-Yau Kwok. Building sparse multiple-kernel SVM classiﬁers. IEEE Transactions on Neural Networks, 20(5):827–839, 2009. Christian Igel, Tobias Glasmachers, Britta Mersch, Nico Pfeifer, and Peter Meinicke. Gradientbased optimization of kernel-target alignment for sequence kernels applied to bacterial gene start detection. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4(2):216– 226, 2007. Thorsten Joachims, Nello Cristianini, and John Shawe-Taylor. Composite kernels for hypertext categorisation. In Proceedings of the 18th International Conference on Machine Learning, 2001. Jaz Kandola, John Shawe-Taylor, and Nello Cristianini. Optimizing kernel alignment over combinations of kernels. In Proceedings of the 19th International Conference on Machine Learning, 2002. Seung-Jean Kim, Alessandro Magnani, and Stephen Boyd. Optimal kernel selection in kernel Fisher discriminant analysis. In Proceedings of the 23rd International Conference on Machine Learning, 2006. Marius Kloft, Ulf Brefeld, S¨ ren Sonnenburg, Pavel Laskov, Klaus-Robert M¨ ller, and Alexander o u Zien. Efﬁcient and accurate ℓ p -norm multiple kernel learning. In Advances in Neural Information Processing Systems 22, 2010a. Marius Kloft, Ulf Brefeld, S¨ ren Sonnenburg, and Alexander Zien. Non-sparse regularization and o efﬁcient training with multiple kernels. Technical report, Electrical Engineering and Computer Sciences, University of California at Berkeley, 2010b. Gert R. G. Lanckriet, Nello Cristianini, Peter Bartlett, Laurent El Ghaoui, and Michael I. Jordan. Learning the kernel matrix with semideﬁnite programming. In Proceedings of the 19th International Conference on Machine Learning, 2002. Gert R. G. Lanckriet, Nello Cristianini, Peter Bartlett, Laurent El Ghaoui, and Michael I. Jordan. Learning the kernel matrix with semideﬁnite programming. Journal of Machine Learning Research, 5:27–72, 2004a. Gert R. G. Lanckriet, Tijl de Bie, Nello Cristianini, Michael I. Jordan, and William Stafford Noble. A statistical framework for genomic data fusion. Bioinformatics, 20(16):2626–2635, 2004b. 2264 M ULTIPLE K ERNEL L EARNING A LGORITHMS Gert R. G. Lanckriet, Minghua Deng, Nello Cristianini, Michael I. Jordan, and William Stafford Noble. Kernel-based data fusion and its application to protein function prediction in Yeast. In Proceedings of the Paciﬁc Symposium on Biocomputing, 2004c. Wan-Jui Lee, Sergey Verzakov, and Robert P. W. Duin. Kernel combination versus classiﬁer combination. In Proceedings of the 7th International Workshop on Multiple Classiﬁer Systems, 2007. Darrin P. Lewis, Tony Jebara, and William Stafford Noble. Support vector machine learning from heterogeneous data: An empirical analysis using protein sequence and structure. Bioinformatics, 22(22):2753–2760, 2006a. Darrin P. Lewis, Tony Jebara, and William Stafford Noble. Nonstationary kernel combination. In Proceedings of the 23rd International Conference on Machine Learning, 2006b. Yen-Yu Lin, Tyng-Luh Liu, and Chiou-Shann Fuh. Dimensionality reduction for data in multiple feature representations. In Advances in Neural Processing Systems 21, 2009. Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, and Chris Watkins. Text classiﬁcation using string kernels. Journal of Machine Learning Research, 2:419–444, 2002. Chris Longworth and Mark J. F. Gales. Multiple kernel learning for speaker veriﬁcation. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, 2008. Chris Longworth and Mark J. F. Gales. Combining derivative and parametric kernels for speaker veriﬁcation. IEEE Transactions on Audio, Speech, and Language Processing, 17(4):748–757, 2009. Brian McFee and Gert Lanckriet. Partial order embedding with multiple kernels. In Proceedings of the 26th International Conference on Machine Learning, 2009. Charles A. Micchelli and Massimiliano Pontil. Learning the kernel function via regularization. Journal of Machine Learning Research, 6:1099–1125, 2005. Javier M. Moguerza, Alberto Mu˜ oz, and Isaac Mart´n de Diego. Improving support vector classin ı ﬁcation via the combination of multiple sources of information. In Proceedings of the Structural, Syntactic, and Statistical Pattern Recognition, Joint IAPR International Workshops, 2004. Mosek. The MOSEK Optimization Tools Manual Version 6.0 (Revision 106). MOSEK ApS, Denmark, 2011. Canh Hao Nguyen and Tu Bao Ho. An efﬁcient kernel matrix evaluation measure. Pattern Recognition, 41(11):3366–3372, 2008. William Stafford Noble. Support vector machine applications in computational biology. In Bernhard Sch¨ lkopf, Koji Tsuda, and Jean-Philippe Vert, editors, Kernel Methods in Computational o Biology, chapter 3. The MIT Press, 2004. Cheng Soon Ong and Alexander J. Smola. Machine learning using hyperkernels. In Proceedings of the 20th International Conference on Machine Learning, 2003. 2265 ¨ G ONEN AND A LPAYDIN Cheng Soon Ong, Alexander J. Smola, and Robert C. Williamson. Hyperkernels. In Advances in Neural Information Processing Systems 15, 2003. Cheng Soon Ong, Alexander J. Smola, and Robert C. Williamson. Learning the kernel with hyperkernels. Journal of Machine Learning Research, 6:1043–1071, 2005. Ayseg¨ l Ozen, Mehmet G¨ nen, Ethem Alpaydın, and T¨ rkan Halilo˘ lu. Machine learning inte¸ u ¨ o u g gration for predicting the effect of single amino acid substitutions on protein stability. BMC Structural Biology, 9(1):66, 2009. ¨ o˘ ¨ S¨ reyya Oz¨ gur-Aky¨ z and Gerhard Wilhelm Weber. Learning with inﬁnitely many kernels via u u semi-inﬁnite programming. In Proceedings of Euro Mini Conference on Continuous Optimization and Knowledge-Based Technologies, 2008. Paul Pavlidis, Jason Weston, Jinsong Cai, and William Noble Grundy. Gene functional classiﬁcation from heterogeneous data. In Proceedings of the 5th Annual International Conference on Computational Molecular Biology, 2001. Shibin Qiu and Terran Lane. Multiple kernel learning for support vector regression. Technical report, Computer Science Department, University of New Mexico, 2005. Shibin Qiu and Terran Lane. A framework for multiple kernel support vector regression and its applications to siRNA efﬁcacy prediction. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6(2):190–199, 2009. Alain Rakotomamonjy, Francis Bach, St´ phane Canu, and Yves Grandvalet. More efﬁciency in mule tiple kernel learning. In Proceedings of the 24th International Conference on Machine Learning, 2007. Alain Rakotomamonjy, Francis R. Bach, St´ phane Canu, and Yves Grandvalet. SimpleMKL. Joure nal of Machine Learning Research, 9:2491–2521, 2008. Jagarlapudi Saketha Nath, Govindaraj Dinesh, Sankaran Raman, Chiranjib Bhattacharya, Aharon Ben-Tal, and Kalpathi R. Ramakrishnan. On the algorithmics and applications of a mixed-norm based kernel learning formulation. In Advances in Neural Information Processing Systems 22, 2010. Bernhard Sch¨ lkopf, Koji Tsuda, and Jean-Philippe Vert, editors. Kernel Methods in Computational o Biology. The MIT Press, 2004. S¨ ren Sonnenburg, Gunnar R¨ tsch, and Christin Sch¨ fer. A general and efﬁcient multiple kernel o a a learning algorithm. In Advances in Neural Information Processing Systems 18, 2006a. S¨ ren Sonnenburg, Gunnar R¨ tsch, Christin Sch¨ fer, and Bernhard Sch¨ lkopf. Large scale multiple o a a o kernel learning. Journal of Machine Learning Research, 7:1531–1565, 2006b. Niranjan Subrahmanya and Yung C. Shin. Sparse multiple kernel learning for signal processing applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(5):788–798, 2010. 2266 M ULTIPLE K ERNEL L EARNING A LGORITHMS Marie Szafranski, Yves Grandvalet, and Alain Rakotomamonjy. Composite kernel learning. In Proceedings of the 25th International Conference on Machine Learning, 2008. Marie Szafranski, Yves Grandvalet, and Alain Rakotomamonjy. Composite kernel learning. Machine Learning, 79(1–2):73–103, 2010. Ying Tan and Jun Wang. A support vector machine with a hybrid kernel and minimal VapnikChervonenkis dimension. IEEE Transactions on Knowledge and Data Engineering, 16(4):385– 395, 2004. Hiroaki Tanabe, Tu Bao Ho, Canh Hao Nguyen, and Saori Kawasaki. Simple but effective methods for combining kernels in computational biology. In Proceedings of IEEE International Conference on Research, Innovation and Vision for the Future, 2008. Ivor Wai-Hung Tsang and James Tin-Yau Kwok. Efﬁcient hyperkernel learning using second-order cone programming. IEEE Transactions on Neural Networks, 17(1):48–58, 2006. Koji Tsuda, Shinsuke Uda, Taishin Kin, and Kiyoshi Asai. Minimizing the cross validation error to mix kernel matrices of heterogeneous biological data. Neural Processing Letters, 19(1):63–72, 2004. Vladimir Vapnik. The Nature of Statistical Learning Theory. John Wiley & Sons, 1998. Manik Varma and Bodla Rakesh Babu. More generality in efﬁcient multiple kernel learning. In Proceedings of the 26th International Conference on Machine Learning, 2009. Manik Varma and Debajyoti Ray. Learning the discriminative power-invariance trade-off. In Proceedings of the International Conference in Computer Vision, 2007. Jason Weston, Sayan Mukherjee, Olivier Chapelle, Massimiliano Pontil, Tomaso Poggio, and Vladimir Vapnik. Feature selection for SVMs. In Advances in Neural Information Processing Systems 13, 2001. Frank Wilcoxon. Individual comparisons by ranking methods. Biometrics Bulletin, 1(6):80–83, 1945. Mingrui Wu, Bernhard Sch¨ lkopf, and G¨ khan Bakır. A direct method for building sparse kernel o o learning algorithms. Journal of Machine Learning Research, 7:603–624, 2006. Linli Xu, James Neufeld, Bryce Larson, and Dale Schuurmans. Maximum margin clustering. In Advances in Neural Processing Systems 17, 2005. Zenglin Xu, Rong Jin, Irwin King, and Michael R. Lyu. An extended level method for efﬁcient multiple kernel learning. In Advances in Neural Information Processing Systems 21, 2009a. Zenglin Xu, Rong Jin, Jieping Ye, Michael R. Lyu, and Irwin King. Non-monotonic feature selection. In Proceedings of the 26th International Conference on Machine Learning, 2009b. Zenglin Xu, Rong Jin, Haiqin Yang, Irwin King, and Michael R. Lyu. Simple and efﬁcient multiple kernel learning by group Lasso. In Proceedings of the 27th International Conference on Machine Learning, 2010a. 2267 ¨ G ONEN AND A LPAYDIN Zenglin Xu, Rong Jin, Shenghuo Zhu, Michael R. Lyu, and Irwin King. Smooth optimization for effective multiple kernel learning. In Proceedings of the 24th AAAI Conference on Artiﬁcal Intelligence, 2010b. Yoshihiro Yamanishi, Francis Bach, and Jean-Philippe Vert. Glycan classiﬁcation with tree kernels. Bioinformatics, 23(10):1211–1216, 2007. Fei Yan, Krystian Mikolajczyk, Josef Kittler, and Muhammad Tahir. A comparison of ℓ1 norm and ℓ2 norm multiple kernel SVMs in image and video classiﬁcation. In Proceedings of the 7th International Workshop on Content-Based Multimedia Indexing, 2009. Jingjing Yang, Yuanning Li, Yonghong Tian, Ling-Yu Duan, and Wen Gao. Group-sensitive multiple kernel learning for object categorization. In Proceedings of the 12th IEEE International Conference on Computer Vision, 2009a. Jingjing Yang, Yuanning Li, Yonghong Tian, Ling-Yu Duan, and Wen Gao. A new multiple kernel approach for visual concept learning. In Proceedings of the 15th International Multimedia Modeling Conference, 2009b. Jingjing Yang, Yuanning Li, Yonghong Tian, Ling-Yu Duan, and Wen Gao. Per-sample multiple kernel approach for visual concept learning. EURASIP Journal on Image and Video Processing, 2010. Jieping Ye, Jianhui Chen, and Shuiwang Ji. Discriminant kernel and regularization parameter learning via semideﬁnite programming. In Proceedings of the 24th International Conference on Machine Learning, 2007a. Jieping Ye, Shuiwang Ji, and Jianhui Chen. Learning the kernel matrix in discriminant analysis via quadratically constrained quadratic programming. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007b. Jieping Ye, Shuiwang Ji, and Jianhui Chen. Multi-class discriminant kernel learning via convex programming. Journal of Machine Learning Research, 9:719–758, 2008. Yiming Ying, Kaizhu Huang, and Colin Campbell. Enhanced protein fold recognition through a novel data integration approach. BMC Bioinformatics, 10(1):267, 2009. Bin Zhao, James T. Kwok, and Changshui Zhang. Multiple kernel clustering. In Proceedings of the 9th SIAM International Conference on Data Mining, 2009. Alexander Zien and Cheng Soon Ong. Multiclass multiple kernel learning. In Proceedings of the 24th International Conference on Machine Learning, 2007. Alexander Zien and Cheng Soon Ong. An automated combination of kernels for predicting protein subcellular localization. In Proceedings of the 8th International Workshop on Algorithms in Bioinformatics, 2008. 2268