{'fraction_non_alphanumeric': 0.03582213498414616, 'fraction_numerical': 0.01611807338064321, 'mean_word_length': 4.470369605616353, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Binary Classification Framework for Two-Stage Multiple Kernel Learning

With the advent of kernel methods, automating the task of specifying a suitable kernel has become increasingly important. In this context, the Multiple Kernel Learning (MKL) problem of finding a combination of pre-specified base kernels that is suitable for the task at hand has received significant attention from researchers. In this paper we show that Multiple Kernel Learning can be framed as a standard binary classification problem with additional constraints that ensure the positive definiteness of the learned kernel. Framing MKL in this way has the distinct advantage that it makes it easy to leverage the extensive research in binary classification to develop better performing and more scalable MKL algorithms that are conceptually simpler, and, arguably, more accessible to practitioners. Experiments on nine data sets from different domains show that, despite its simplicity, the proposed technique compares favorably with current leading MKL approaches.


Introduction
Kernel methods such as support vector machines (SVM) (Cortes & Vapnik, 1995), kernel ridge regression, or kernel PCA (Smola & Muller, 1999), use a positive semi-definite (PSD) kernel to implicitly map the instances from the original instance space to a feature space where the standard linear algorithm is applied. The main drawback of kernel methods is that they require the user to specify a single suitable kernel in the first place, which is often critical to the method's success, but is usually a hard task even when the user has a good familiarity with the problem domain. To ease this burden, significant attention has been given the problem of automatically learning the kernel. The majority of the previous work in this area has focused on the Multiple Kernel Learning (MKL) setting, where the user is only tasked with specifying a set of base kernels, and the learning algorithm is in charge of finding a combination of these base kernels that is appropriate for the problem at hand.
There have been two main lines of work in this direction. The first one learns both the the weights of the kernel combination and the parameters of the classifier by solving a single joint optimization problem. This one-stage approach was first proposed by (Lanckriet et al., 2004) and has since received significant attention (Rakotomamonjy et al., 2007;Sonnenburg et al., 2006;Cortes et al., 2010a;Kloft et al., 2011;Bach, 2008;Zien & Ong, 2007;Cortes et al., 2009;Sindhwani & Lozano, 2011).
The second line of work in kernel learning follows a two-stage approach: first learn a "good" combination of base kernels using the training data, then use the learned kernel with a standard kernel method such as SVM or kernel ridge regression to obtain a classifier/regressor. This approach has been initially proposed in (Cristianini et al., 2001) and (Kandola et al., 2002), and recently revisited by (Cortes et al., 2010b). The two-stage leaning approaches so far have been based on the notion of target alignment. Intuitively, target alignment, is a measure of similarity (agreement) between a kernel and the target kernel, which is derived from the training labels, and represents the optimal kernel for the training sample.
In this paper we introduce TS-MKL, a general approach to Two-Stage Multiple Kernel Learning that encompasses the previous work based on target alignment as special cases. We formulate the kernel learning problem as a standard linear classification problem in a new instance space. In this space, any linear classifier with weights µ directly corresponds to a linear combination of base kernels with weights µ. To avoid confusions, we will denote this new instance space as the K-space, and a classifier in the K-space as a Kclassifier throughout the paper. Thus the problem of finding a "good" kernel combination reduces to finding a "good" linear classifier in the K-space, a very familiar problem. One big advantage of this approach is that one can easily adapt techniques from binary classification to solve the MKL problem. For instance, one can use familiar and well understood max-margin methods to obtain better performing MKL algorithms, or take advantage of the recent advances in large scale learning to scale up and/or parallelize the MKL implementations. For the results presented in this paper we learn K-classifiers (and hence kernels) by training L 2 regularized linear SVMs with positive weights using the stochastic projected sub-gradient descent method from Pegasos (Shalev-Shwartz et al., 2007).
On the theoretical side, we prove a finite sample generalization bound for the original classification task in terms of the expected hinge loss and the margin of a K-classifier in the K-space. This justifies our approach of training a K-classifier that has low hinge loss and high margin in the K-space in order to learn a good kernel for the original classification problem. To the best of our knowledge, this result represent the first finite sample bound for two-stage kernel learning, improving on previous bounds that were only asymptotic. We also give a concentration bound for the expected hinge loss of a K-classifier.
On the empirical side, we run a comprehensive evaluation on two object recognition datasets (Caltech 101 and 256), three bioinformatics datasets (Psort+, Psort-, Plant) and four UCI datasets. On all these datasets our method performs better than, or the same as target alignment, showing that choosing a better K-classifier is beneficial. Our method also fares well against one-stage multiple kernel learning approaches significantly outperforming them on Caltech-256 and being essentially tied on the others.

Method
We consider a classification problem where instances (x, y) are drawn from a distribution P over X × Y, with Y a finite discrete set of labels. We assume that we have access to p positive semi-definite (PSD) base kernel functions K 1 , · · · , K p with K i : X × X → R. Our goal is to learn a combination of these kernel functions that is itself a positive semi-definite function and is a "good" kernel for the classification task at hand. To achieve this, we define a new binary classification problem over a new instance space We will call this space the K-space, and call z xx a Kexample or K-instance and t yy a K-label. Any function h : R p → R in this space induces a similarity functioñ K h between instances in the original space: IfK h is also positive semi-definite, hence a valid kernel, we say that h is a K-classifier. For example, all linear functions with positive coefficients (i.e. h µ (z xx ) = µ · z xx with µ ≥ 0) are K-classifiers with the induced kernelsK µ being linear combinations of the p base kernels. Figure 1 shows a toy example for the case of two base kernels. Each point in the figure is a labeled K-example (z xx , t yy ) corresponding to a pair (x, y), (x , y ) of original instances. Note that the figure is drawn in K-space, not in input space. For a linear K-classifier h µ , the value of its induced kernel for a parir of original instances,K µ (x, x ), is the projection of the corresponding K-example z xx on the vector µ (represented by the green line). The left and center sub-figures show the cases where µ is (0, 1) and (1, 0) respecively. In both cases the induced kernel combination is suboptimal. The linear combination in the right sub-figure corresponds to µ = (1, 1) and is a good combination because the kernel values of pairs of instances in the same class are separated from the kernel values of pairs of instances in different classes.
The key insight behind our method is that, if a Kclassifier h is a good classifier in the K-space, then the induced kernelK h (x, x ) = h(z xx ) will likely be positive when x and x belong to the same class and negative otherwise. This makesK h a good kernel for the original classification task. This intuition is made more precise in Section 3 where we provide a generalization bound that shows that a K-classifier that separates the positive and negative K-examples with high margin will indeed induce a kernel that allows learning a good classifier for the original task. Note that having a good K-classifier is a sufficient condition, not a necessary one. There can very well exist combinations of base kernels that do not correspond to a good K-classifier, but are good kernels nevertheless. Unlike one-stage kernel learning approaches, our method will not be able to find such combinations and it might miss on some good kernels. The results in Section 4, however, show that this does not seem to be the case in practice, as we consistently matched or exceeded the performance of one-stage MKL.
Thus the problem of learning a good kernel can be reduced to the problem of learning a good K-classifier in the newly defined K-space: given a training sample (x i , y i ) n i=1 for the original classification task, construct a K-training set (z ij , t ij ) 1≤i≤j≤n and learn a Kclassifier h from this sample. Any learning algorithm can be used for learning h provided that the induced kernel can be guaranteed to be a valid PSD kernel 1 .
In line with the majority of the MKL work, in this paper we focus on learning linear K-classifiers, and hence linear combinations of base kernels. The results in Section 3 suggest that it is desirable to have a maximum margin K-classifier, thus we use L 2 regularized linear SVM to learn the K-classifier, and ensure that the induced kernel is PSD by constraining the weights to be positive. One could, however, use a sparsity promoting regularizer (e.g., L 1 penalty) if a sparse combination of kernels is desired.
The optimization problem for learning the kernel weights µ is thus given by To optimize this objective we use the stochastic projected sub-gradient descent implemented in Pega-sos (Shalev-Shwartz et al., 2007), with an additional projection to the non-negative constraint set after every gradient step. Using a stochastic optimization method allows us to scale very well despite the quadratic number of K-examples: computation time is not directly dependent on the number of instances, linear in the number of base kernels, and independent of the number of classes. If needed, memory usage can be reduced through streaming techniques or on the fly construction of the K-examples.

Connection to Target Alignment
Previous two-stage kernel learning approaches (Cristianini et al., 2001;Cortes et al., 2010b) learn a non-negative linear combination of base kernels that maximizes the alignment with the target kernel K (t) (x i , x j ) = y i y j on the training set. This is achieved by solving the optimization problem where A is the Gram matrix of kernel A on the training set, A, B = tr(AB T ) and ||A|| 2 F = tr(AA T ). The above optimization problem can be re-written in our terminology of K-examples as follows: When the base kernels are centered, as proposed in (Cortes et al., 2010b), the denominator represents the overall standard deviation of the projections of the K-examples on the vector µ. Hence target alignment attempts to find a projection direction µ that maximize the difference between the sums of the projections of the positive and negative K-examples, while minimizing the overall variance of the projected Kexamples. This is very similar to using Fisher-LDA in the K-space, with non-negativity constraints on µ. In fact, viewing target alignment from this perspective, makes it clear that it implicitly makes the assumption that the data is homoscedastic (the positive and negative K-examples have the same covariance), which might not be appropriate in real applications.

Connection to Learning with Hyperkernels
The approach proposed in this paper can also be cast in the framework of learning with hyperkernels (Ong et al., 2005) which provides a general recipe for kernel learning and includes Multiple Kernel Learning as a special case. It introduces the notions of kernel quality functional, a measure of "goodness" of a kernel that depends on the training data, and Hyper Reproducing Kernel Hilbert Space, an RKHS over kernel functions that defines the class of kernels that can be learned. Once the desired Hyper-RKHS and quality functional are specified, one has to solve a semi-definite program (SDP) to optimize the quality functional regularized by the norm induced by the Hyper-RKHS.
When using an SVM as the K-classifier, TS-MKL can be put in the learning with hyperkernels framework by defining the Hyper-RKHS to be the set of non-negative linear combinations of base kernels, and the quality functional to be the hinge loss in K-space. Considering this specific setting has significant advantages: it enables the use of simple and well understood binary classification techniques to learn the kernel, it enables a theoretical analysis, and it allows a significantly more scalable implementation. Equally important, all these advantages do not seem to come at the cost of reduced performance, as we are still performing on par with or better than competing MKL techniques.

Theoretical Results 2
In this section we make the connection between the performance a K-classifier in the K-space and the performance on the original problem precise. This justifies the approach taken in this paper not only intuitively, but also from a theoretical standpoint. Specifically, we bound the generalization error of an SVM that uses the kernel induced by a K-classifier in terms of the expected hinge loss and the margin of the Kclassifier in the K-space: Theorem 3.1 Let P be a distribution on X × {±1}, z xx and t yy be as in Equation 1, h be a K-classifier, and R be a constant s.t. h(z xx ) ≤ R 2 ∀x ∈ X . Let be the expected K-space hinge loss relative to margin γ of the K-classifier h. Then, with probability 1 − δ, a classifierf with generalization error can be learned efficiently from a training sample of n instances drawn IID from P .
The theorem follows from the two lemmas stated below. The first lemma shows that a K-classifier that has low expected hinge loss in the K-space will induce a "good" kernel. The second lemma shows that a good kernel allows for a classifier with low generalization error to be efficiently learned from a finite training sample. The following definition states formally what we mean by a good kernel (Srebro, 2007). 3 Definition A kernel K is an ( , γ) good kernel in hinge loss with respect to a distribution P on X ×{±1} if there exist a classifier w ∈ H K with w H K = 1 s.t.
where H K is the Hilbert space and φ(·) is the feature mapping corresponding to K.
Lemma 3.2 Let P , h, HL h,γ , R be as in Theorem 3.1. Then theK h is a (HL h,γ , γ R ) good kernel in hinge loss with respect to P .
be a kernel classifier that minimizes the average hinge loss relative to γ on the training sample. Then, with probability at least 1 − δ, we have: Lemma 3.3 follows directly from Theorem 21 in (Bartlett & Mendelson, 2002).
Note that, unlike in the one-stage kernel learning case, the generalization bound in Theorem 3.1 is in terms of the expected hinge loss of the K-classifier not the training hinge loss. While we are hopeful a generalization bound for the classification problem in the K-space can be obtained, as of now it remains an open problem.
We can, however, prove a concentration bound for the expected hinge loss of a K-classifier. This is the analog of the concentration bounds for target alignment in (Cortes et al., 2010b;Cristianini et al., 2001). 4 Theorem 3.4 Let P , h, HL h,γ , R be as in Theorem 3.1. Let (x i , y i ) n i=1 be an IID sample distributed according to P . Then the following inequality holds with probability at least 1 − δ

Empirical Evaluation
We evaluate the proposed method on two object recognition datasets (Caltech-101 and Caltech-256), three bioinformatics datasets (Psort+, Psort-and Plant), and four UCI datasets (Sonar, Pima, Vertebral and Ionosphere). We compare our method with several baselines: best kernel, uniform combination of base kernels (Average), target alignment, and the onestage MKL algorithms SILP (Sonnenburg et al., 2006), SimpleMKL (Rakotomamonjy et al., 2007), L 2 -Norm MLK (Kloft et al., 2011), and UFO-MKL (Orabona & Jie, 2011). For two-stage methods we use LIB-SVM (Chang & Lin, 2011) to train the data classifier and select the regularization parameter C via 4-fold cross-validation for all datasets except Caltech where it is fixed at 1000. On multi-class problems, we use a one-vs-rest SVM. For one-stage approaches other than UFO-MKL, we selected C as above and use a one-vsrest scheme for multi-class problems. For UFO-MKL we use the joint multi-class formulation and search over α and C using a bi-dimensional grid. Following (Orabona & Jie, 2011), we run the optimization for 20 epochs on UCI datasets, 30 epochs on Caltech-101 and 100 epochs on Caltech-256. All kernels used in the experiments are centered and standardized to have zero mean and unit variance in feature space.

Methodology for TS-MKL
To learn kernel combination weights µ with TS-MKL we optimize the objective in Eq. 2 using Pegasos (Shalev-Shwartz et al., 2007) with an additional projection to the non-negative constraint set after each sub-gradient step. We use a batch size of 100 for each sub-gradient computation and run 10 3 sub-gradient steps for UCI datasets and 10 5 for all others. To select the parameter λ, we use a single 80%-20% random split of the Pegasos training set and search for the λ with the lowest validation hinge loss 5 . The search grid for λ is taken to be in the range of 100 to 10 −8 dividing in each step by 4. A big advantage of this selection scheme for λ is that it is completely independent from the data classifier that will ultimately use the learned kernel. This keeps the setup simple and avoids intricate multi-level multi-dimensional validation schemes across the parameters of the data classifier and the K-classifier. Fig. 2, shows the hinge-loss in K-space, the accuracy of the K-classifier, and the accuracy of the data classifier that uses the learned kernel, as a function of λ. The plot shows a clear correlation between hinge loss in K-space and data accuracy with the learned kernel. The data accuracy increases when the hinge loss in K-space decreases and vice versa. This experiment provides further emprical evidence for our theoretical results that show that a good K-classifier (having low hinge loss in K-space) corresponds to a good learned kernel.
After λ is selected, Pegasos is retrained on the full training set of K-examples. The obtained weight vector µ is then used to linearly combine the base kernels, and the SVM data classifier is trained using this learned kernel with C selected as described above.

Caltech-101 and Caltech-256
Both these datasets contain pictures of objects and the task is to recognize the object category. Caltech-101 has 102 classes and Caltech-256 has 256 classes. Caltech-101 is perceived as an easier dataset than Caltech-256 in which images are not left-right aligned and there are more categories. We follow the experimental setup used in (Gehler & Nowozin, 2009) and use the same 39 base kernels and train test splits.
We report results using all 102 classes for Caltech- Comparing to UFO-MKL, our performance is higher for 5 samples per class, and very similar for all other sample sizes. One-stage MKL methods using the onevs-all multi-class scheme perform significantly worse and do not even outperform the average kernel until the training set has 25 samples per class. This is probably because data is too scarce to allow learning a separate kernel for each class. Target alignment performs a little better than the average kernel, but is still significantly worse than TS-MKL. We also show the performance of LP-β (Gehler & Nowozin, 2009), which, to the best of our knowledge, is the state of the art method on this data set 8 . The performance of TS-MKL and UFO-MKL is almost on par with LP-β, especially for larger sample sizes. While LP-β is similar in spirit to multiple-kernel learning, it is not a true kernel learning algorithm as it does not produce a ker-nel, but rather learns an ensemble of SVM classifiers, each of which is trained on an individual kernel.
On Caltech-256 dataset, our approach performs better than all competing kernel learning baselines. We achieve 0.245, 0.320, 0.370, 0.426, 0.448, 0.475, 0.494 mean accuracy for 5, 10, 15, 20, 25, 30, 40, 50 training samples per class. This performance is significantly higher than the best results reported in the literature for 5, 10, and 15 training samples, after which we again perform on par with LP-β. On this dataset, UFO-MKL performance 9 is similar to that of the average kernel, while the rest of the one-stage MKL techniques perform worse. Exact target alignment is worst among all other approaches, however approximate target alignment is able to at least match the performance of the average kernel.

Bioinformatics datasets
We evaluate our method on a problem relevant to cell-biology predicting: the subcellular localization of proteins, which is crucial in making inference about protein function and protein interactions. We follow the experimental setup of (Zien & Ong, 2007) and use the same 69 kernels. The kernels used are: 2 kernels on phylogenetic trees, 3 kernels from BLAST E-values and 64 sequence motif kernels.
We experiment with three datasets. The first two datasets are for the problem of bacterial protein locations (Gardy et al., 2004). The Psort+ dataset has 541 data points with 4 classes and Psort-dataset has 1444 data points with 5 classes. We report average F1 score over all classes over 10 random splits for both these datasets as done in (Zien & Ong, 2007). The third dataset used is the original plant dataset of Tar-getP (Emanuelsson et al., 2000), and has 940 examples with 4 classes. We use the performance measure of Matthew's Correlation Coefficient (MCC) following the evaluation in (Zien & Ong, 2007). Again, average MCC score over all 4 classes is reported.
The results are shown in Table 1. The papers that have used the Psort datasets in the past (Gardy et al., 2004;Zien & Ong, 2007), reported results after filtering out the most unsure predictions in the test set. For Psort+ and Psort-, about 15% and 13.3% of the test examples were filtered out respectively and the performance is reported only for the remaining predictions. We follow the same procedure to be able to compare with these methods. We also report performance for full test set.
On these datasets, all the kernel learning methods have  (Zien & Ong, 2007) are taken from their paper. similar performance, and are better than the best kernel and average kernel baselines. Multi-class multiple kernel learning (MC-MKL) of (Zien & Ong, 2007) is also close to our method and other baselines.

UCI datasets
We use four UCI datasets: Sonar, Ionosphere, Pima and Vertebral (the three class version). For each of these datasets, we perform two types of MKL experiments. In first setting, we construct a total of 13 kernels on the full feature vectors: 9 Gaussian kernels (e −γ||xi−xj || 2 ) with γ = {2 −10 , 2 −9 , . . . , 2 −2 }, 3 polynomial kernels of degree 2,3 and 4, and a linear kernel. In the second setting, we augment these 13 kernels with another set of Gaussian, polynomial and linear kernels constructed on individual features of the data. The range of parameter γ for Gaussian and degree parameter for polynomial kernel is kept same as before.
If the data has d features, we have total 13d + 13 kernels in the second setting. We report average accuracy accuracy over 10 random 80% − 20% train-test splits.
The results are shown in Table 2. On all these datasets, no kernel learning approach seems to improve performance over the straightforward baselines of best kernel and average kernel. Although further study is needed to reach a definite conclusion, these results seem to indicate that blindly using a kitchen sink of standard kernels is not beneficial if the goal is to combine these kernels using an MKL approach. This highlights the importance of evaluating MKL techniques using datasets like Caltech and PSORT, where the kernels have been carefully designed using domain knowledge to capture different, potentially useful, notions of similarity in the data.

Computational Efficiency
Since the number of K-examples is quadratic in the number of training instances, one might worry about the scalability of the TS-MKL method. In this section we compare the running time of TS-MKL with Target Alignment, and UFO-MKL (Ultra-Fast Optimization MKL) which, to the best of our knowledge, is the fastest one-stage MKL technique to date.   However, on Pima, which has 614 samples, and on Caltech, which has 3060 samples and 102 classes, TS-MKL is more than an order of magnitude faster than UFO-MKL. This shows that, by taking advantage of the advances in large scale stochastic optimization, TS-MKL is not only able to gracefully handle the quadratic increase in the number of K-examples, but it is actually the fastest MKL method to date.

Conclusions and Future Work
Framing kernel learning as a standard classification problem in a properly defined instance space allows us to easilly adapt well understood classification techniques to obtain a scalable and high performing twostage multiple kernel learning algorithm. Our approach is backed up by formal theoretical guarantees, and by empirical evaluation that shows it always outperforms or is on par with leading one-stage and twostage kernel learning methods. This is a remarkable feat for a method that is quite simple and intuitive.
This new perspective on multiple kernel learning opens the door to a number of interesting questions to be addressed in subsequent research. Examples are: exploring the use of non-linear K-classifiers in conjunction with the learning with similarity functions framework; improving performance in scarce data condi-  Table 2. Average accuracy (%) over 10 random splits on UCI datasets. p denotes the number of base kernels. Numbers in parentheses are the std. deviations.
tions through semi-supervised and multi-task multiple kernel learning by using such techniques to learn the K-classifier; or applying TS-MKL to semisupervised clustering and dimensionality reduction problems where the supervised signal is usually given in terms of pairwise must-link and can-not-link constraints rather than labels.