Alignment Based Kernel Learning with a Continuous Set of Base Kernels
Arash Afkanpour \hspace{10mm} Csaba Szepesv\'{a}ri \hspace{10mm} Michael Bowling
Department of Computing Science
Edmonton
AB T6G 1K7
The success of kernel-based learning methods depend on the choice of kernel. Recently, kernel learning methods have been proposed that use data to select the most appropriate kernel, usually by combining a set of base kernels. We introduce a new algorithm for kernel learning that combines a {\em continuous set of base kernels}, without the common step of discretizing the space of base kernels. We demonstrate that our new method achieves state-of-the-art performance across a variety of real-world datasets. Furthermore, we explicitly demonstrate the importance of combining the right dictionary of kernels, which is problematic for methods based on a finite set of base kernels chosen a priori. Our method is not the first approach to work with continuously parameterized kernels. However, we show that our method requires substantially less computation than previous such approaches, and so is more amenable to multiple dimensional parameterizations of base kernels, which we demonstrate. \if0 We present a novel method for learning a positive combination of kernels from a continuously parametrized set of base kernels. Our method implements the steepest ascent approach to forward-stagewise additive modeling to maximize a centered alignment measure. We compare this technique to several techniques from the literature on both synthetic and real-world datasets, illustrating its strengths and weaknesses. %Our main conclusion is that methods which avoid discretizing the parameter space face rather different tradeoffs than methods which start by discretizing this space and, as such, deserve further study. We observe that in many cases our new method outperforms standard multiple kernel learning methods that discretize the kernel parameter space in terms of the prediction accuracy and computational efficiency. \fi
mypaper.tex
\documentclass{article} % For LaTeX2e
\usepackage{nips11submit_e}
\usepackage{times}
%\documentstyle[nips10submit_09,times,art10]{article} % For LaTeX 2.09
% For figures
\usepackage{graphicx} % more modern
%\usepackage{epsfig} % less modern
% \usepackage{subfigure} 
\usepackage{subfig} 
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{epstopdf}
\usepackage[disable]{todonotes}
% For citations
%\usepackage[numbers]{natbib}
\usepackage{natbib}
% For algorithms
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{appendix}
\usepackage{textcomp}
\usepackage{multirow}
\usepackage{url}
\usepackage{hyperref}

\newtheorem{lemma}{Lemma}
\newtheorem{definition}[lemma]{Definition}
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{proposition}[lemma]{Proposition}
\newtheorem{corollary}[lemma]{Corollary}



\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\def\tr{{\mbox{tr}}}
\def\diag{{\mbox{diag}}}
\def\transpose{{^\top}}
\def\etal{{{et al. }}}

\newenvironment{packed_item}{
\begin{itemize}
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
}{\end{itemize}}


\title{Alignment Based Kernel Learning with a Continuous Set of Base Kernels}

\author{
Arash Afkanpour \hspace{10mm} Csaba Szepesv\'{a}ri \hspace{10mm} Michael Bowling	\\ \\
Department of Computing Science\\
University of Alberta\\
Edmonton, AB T6G 1K7\\
\{\texttt{afkanpou,szepesva,mbowling}\}\texttt{@ualberta.ca} \\
}

%\author{
%Arash Afkanpour \\
%Department of Computing Science\\
%University of Alberta\\
%\texttt{afkanpou@ualberta.ca} \\
%\And
%Csaba Szepesv\'{a}ri \\
%Department of Computing Science\\
%University of Alberta\\
%\texttt{szepesva@ualberta.ca} \\
%\And
%Michael Bowling \\
%Department of Computing Science\\
%University of Alberta\\
%\texttt{bowling@cs.ualberta.ca} \\
%}


% The \author macro works with any number of authors. There are two commands
% used to separate the names and addresses of multiple authors: \And and \AND.
%
% Using \And between authors leaves it to \LaTeX{} to determine where to break
% the lines. Using \AND forces a linebreak at that point. So, if \LaTeX{}
% puts 3 of 4 authors names on the first line, and the last on the second
% line, try using \AND instead of \And before the third author name.

\newcommand{\fix}{\marginpar{FIX}}
\newcommand{\new}{\marginpar{NEW}}

\nipsfinalcopy % Uncomment for camera-ready version


\begin{document}

\maketitle

\begin{abstract}
The success of kernel-based learning methods depend on the choice of kernel. Recently, kernel learning methods have been proposed that use data to select the most appropriate kernel, usually by combining a set of base kernels. We introduce a new algorithm for kernel learning that combines a {\em continuous set of base kernels}, without the common step of discretizing the space of base kernels. We demonstrate that our new method achieves state-of-the-art performance across a variety of real-world datasets. Furthermore, we explicitly demonstrate the importance of combining the right dictionary of kernels, which is problematic for methods based on a finite set of base kernels chosen a priori. Our method is not the first approach to work with continuously parameterized kernels. However, we show that our method requires substantially less computation than previous such approaches, and so is more amenable to multiple dimensional parameterizations of base kernels, which we demonstrate.  
\if0
We present a novel method for learning a positive combination of kernels from a continuously parametrized set of base kernels. Our method implements the steepest ascent approach to forward-stagewise additive modeling to maximize a centered alignment measure. We compare this technique to several techniques from the literature on both synthetic and real-world datasets, illustrating its strengths and weaknesses. 
%Our main conclusion is that methods which avoid discretizing the parameter space face rather different tradeoffs than methods which start by discretizing this space and, as such, deserve further study.
We observe that in many cases our new method outperforms standard multiple kernel learning methods that discretize the kernel parameter space in terms of the prediction accuracy and computational efficiency. 
\fi
\end{abstract}

\section{Introduction}

%Kernel-based methods are a family of algorithms for building linear models in high-dimensional feature spaces \citep{cortes1995support, shawe2004kernel, scholkopf2002learning}. They have been applied successfully in a wide range of learning problems.
A well known fact in machine learning is that the choice of features heavily influences the performance of learning methods.
Similarly, the performance of a learning method that uses a kernel function is highly dependent on the choice of kernel function.
The idea of {\em kernel learning} %, which perhaps started with using cross-validation \citep{stone1974cross} to choose the best kernel,
is to use data to select the most appropriate kernel function for the learning task.
%The problem of kernel learning has received keen attention in the machine learning community in recent years, yet the story is far from finished.

In this paper we consider kernel learning in the context of supervised learning.
In particular, we consider the problem of learning positive-coefficient linear combinations of base kernels,
 where the base kernels belong to a parameterized family of kernels, $(\kappa_\sigma)_{\sigma\in \Sigma}$.
Here $\Sigma$ is a ``continuous'' parameter space, i.e., some subset of a Euclidean space.
A prime example (and extremely popular choice) is when $\kappa_\sigma$ is a Gaussian kernel, where
 $\sigma$ can be a single common bandwidth or a vector of bandwidths, one per coordinate.
One approach then is to discretize the parameter space $\Sigma$ and then find an appropriate non-negative linear combination of the resulting set of base kernels, ${\cal N} = \{\kappa_{\sigma_1},\ldots,\kappa_{\sigma_p}\}$. The advantage of this approach is that once the set ${\cal N}$ is fixed, any of the many efficient methods available in the literature can be used to find the coefficients for combining the base kernels in ${\cal N}$ (see the papers by \citealt{lanckriet2004learning, sonnenburg2006large,rakotomamonjy2008simplemkl,cortes2009l2,kloft2011lp} and the references therein).
One potential drawback of this approach is that it requires an appropriate, {\em a priori} choice of  ${\cal N}$.
This might be problematic, e.g., if $\Sigma$ is contained in a Euclidean space of moderate, or large dimension (say, a dimension over 20) since the number of base kernels, $p$, grows exponentially with dimensionality even for moderate discretization accuracies. Furthermore, independent of the dimensionality of the parameter space, the need to choose the set ${\cal N}$ independently of the data is at best inconvenient and selecting an appropriate resolution might be far from trivial.
In this paper we explore an alternative method which avoids the need for discretizing the space $\Sigma$.

We are not the first to realize that discretizing a continuous parameter space might be troublesome:
The method of \citet{argyriou2005learning,argyriou2006dc} can also work with continuously parameterized spaces of kernels. \todo{Note that  Eq. (6) of \citet{argyriou2006dc} is convex in $K$. Hence, we could use, in the future, our gradient techniques directly on this performance measure.}
The main issue with this method, however, is that it may get stuck in local optima since it is based on alternating minimization and the objective function is not jointly convex.
Nevertheless, empirically, in the initial publications of \citet{argyriou2005learning,argyriou2006dc} this method was found to have excellent and robust performance, showing that despite the potential difficulties, the idea of avoiding discretizations might have some traction.

Our new method is similar to that of \citet{argyriou2005learning,argyriou2006dc}, in that it is still based on local search. However, our local search is used within a boosting, or more precisely, forward-stagewise additive modeling (FSAM) procedure, a method that is known to be quite robust to how its ``greedy step'' is implemented \citep[Section 10.3]{hastie2001elements}. Thus, we expect to suffer minimally from issues related to local minima.
A second difference to  \citet{argyriou2005learning,argyriou2006dc} is that our method belongs to the group of {\em two-stage kernel learning} methods. The decision to use a two-stage kernel learning approach was motivated by the recent  success of the two-stage method of  \citet{cortes2010two}. In fact, our kernel learning method uses  the centered  kernel alignment metric of \citet{cortes2010two} (derived from the uncentered alignment metric of \citet{shawe2002kernel}) in its first stage as the objective function of the FSAM procedure, while in the second stage a standard supervised learning technique is used.

The technical difficulty of implementing FSAM is that one needs to compute the functional gradient of the chosen objective function. We show that in our case this problem is equivalent to solving an optimization problem over $\sigma\in\Sigma$ with
an objective function that  is a linear function of the Gram matrix derived from the kernel $\kappa_\sigma$.
Because of the nonlinear dependence of this matrix on $\sigma$, this is the step where we need to resort to local optimization: this optimization problem is in general non-convex. However, as we shall demonstrate empirically, even if we use local solvers to solve this optimization step, the  algorithm still shows an overall excellent performance as compared to other state-of-the-art methods. This is not completely unexpected: One of the key ideas underlying boosting is that it is designed to be robust even when the individual ``greedy'' steps are imperfect (cf., Chapter 12, \citealt{BuhvdG11}). \todo{If we used linear kernels, Euclidean distance learning, this step would also be convex. Could this be interesting!?} Given the new kernel to be added to the existing dictionary, we give a computationally efficient, closed-form expression that can be used to determine the coefficient on the new kernel to be added to the previous kernels.
%the steepest ascent step of FSAM % \citep[Section 10.10]{hastie2001elements}
 %Therefore, in this paper we concentrate on the empirical validation of  our ideas.
%The theoretical analysis of the method is left for future work, though we expect that results available for boosting would extend to our method under appropriate technical conditions \citep{BuHo07}.\footnote{We note in passing that empirical bounds on the generalization performance based on Rademacher complexities apply to our method, as these bounds are independent of the learning method \citep{BM02}. For recent nice results in this direction, where the Rademacher complexities of several kernel families are bounded, see \citet{CoMoRo10}.}

%Instead of the theoretical results, i
The empirical performance of our proposed method is explored in a series of experiments.
Our experiments serve multiple purposes.
Firstly, we explore the potential advantages, as well as limitations of the proposed technique. 
In particular, we demonstrate that the procedure is indeed reliable (despite the potential difficulty of implementing the greedy step) and that it can be successfully used even when $\Sigma$ is a subset of a multi-dimensional space. 
Secondly, we demonstrate that in some cases, kernel learning can have a very large improvement over simpler alternatives, such as combining some fixed dictionary of kernels with uniform weights. 
Whether this is true is an important issue that is given weight by the fact that just recently it became a subject of dispute \citep{Cortes09:invited}.
Finally, we compare the performance of our method, both from the perspective of its generalization capability and computational cost, to its natural, state-of-the-art alternatives, such as the two-stage method of \citet{cortes2010two} and the algorithm of
\citet{argyriou2005learning,argyriou2006dc}. For this, we compared our method on datasets used in previous kernel-learning work. To give further weight to our results, we compare on more datasets than any of the previous papers that proposed new kernel learning methods.

Our experiments demonstrate  that our new method is {\em competitive in terms of its generalization performance, while its computational cost is significantly less than that of its competitors that enjoy similarly good generalization performance as our method}.
In addition, our experiments also revealed an interesting novel insight into the behavior of two-stage methods: we noticed that two-stage methods can ``overfit'' the performance metric of the first stage.  In some problem we observed that our method could find kernels that gave rise to better (test-set) performance on the first-stage metric, while the method's overall performance degrades when compared to using kernel combinations whose performance on the first metric is worse. The explanation of this is  that metric of the first stage  is a surrogate performance measure and thus just like in the case of choosing a surrogate loss in classification, better performance according to this surrogate metric does not necessarily transfer into better performance in the primary metric as there is no monotonicity relation between these two metrics. We also show that with proper capacity control, the problem of overfitting the surrogate metric can be overcome. Finally, our experiments  show a clear advantage to using kernel learning methods as opposed to combining kernels with a uniform weight, although it seems that the advantage mainly comes from the ability of our method to discover the right set of kernels. This conclusion is strengthened by the fact that the closest competitor to our method was found to be the method of \citet{argyriou2006dc} that also searches the continuous parameter space, avoiding discretizations. Our conclusion is that it seems that the choice of the base dictionary is more important than how the dictionary elements are combined \todo{Did we try say uniform weights on the top of the dictionary we found? If yes, is this noted somewhere in the paper? In the conclusion these things should be repeated.} and that the {\em a priori} choice of this dictionary may not be trivial. This is certainly true already when the number of parameters is moderate. Moreover, when the number of parameters is larger, simple discretization methods are infeasible, whereas our method can still produce meaningful dictionaries.


\if0
On the real-world datasets we find that our method is pleasingly competitive with the state-of-the-art kernel learning methods, while requiring considerably less computation.
% though, one should bear in mind that there are no free lunches, and results are expected to depend on the datasets chosen.
The purpose of experiments with the artificial datasets is to explore the method in controlled situations.
One of our contributions here is to construct an example where a nontrivial finite-time performance gain is expected by combining kernels, even when the family $(\kappa_\sigma)_{\sigma\in \Sigma}$ is such that any single kernel from the family would be sufficient to achieve asymptotic consistency. We further demonstrate that our method can find the right kernel combination in this case and thus see these performance gains. We also observe that although centered alignment (on a test set) is relatively well correlated with the test-set performance of the predictors built on the learned kernel functions, in some cases a higher (test-set) alignment can in fact give rise to degraded test-performance. As (centered) alignment is a surrogate measure, this should be hardly surprising, though as far as we know, this problem has not been documented in the literature yet.
\fi

\if0
Our approach is most related to the method of \citet{argyriou2005learning,argyriou2006dc}, who also derive a method to search in the same space as our method. Their method, similarly to ours, is also based on greedy optimization. We will empirically show that our method is comparable to the method of \citet{argyriou2005learning} in terms of the prediction accuracy. However, our method requires much less computational time, which makes it favorable against the method of \citet{argyriou2005learning}. In addition to this method, we also compare our method to several multiple kernel learning methods which require the discretization of $\Sigma$ \citep{cortes2010two,kloft2011lp}. Since no published standards are available for how to set up an appropriate discretization of $\Sigma$, we were forced to ``invent'' some methods for doing this. In doing so, we tried to be as diligent as possible. The multiple kernel learning methods (especially, the method of \citet{cortes2010two}) showed some good virtue in some cases, though their performance overall lags behind that of the methods which avoid discretization. 
\fi

\if0
However, it is very well possible, that better discretization of $\Sigma$ would improve their performance, thus, this comparison should be taken with a grain of salt, or as an illustration of the difficulties surrounding the discretization approach.
\fi

\if0
There are learning problems in which one should consider high-dimensional kernel parameterization. Standard multiple kernel learning methods cannot be used for such problems as one needs to deal with exponential number of base kernels that are obtained by the discretization of the kernel parameter space. We will show that our method offers a viable solution for such problems. In these examples we will observe a considerable performance gain compared to the standard multiple kernel learning methods.

In summary, we will show that in many cases our new algorithm outperforms multiple kernel learning methods that discretize kernel parameter space in terms of the prediction accuracy and computational efficiency. While our method's accuracy is comparable to that of \citet{argyriou2005learning}, it requires much less computational time. 
\fi

\if0
A general conclusion that arises from this study is that methods that avoid discretization face rather different tradeoffs than methods which are based on discretization and thus these methods are worthwhile for further study.
\fi

\if0
% bowling: Why are we spending so much time talking about what we "should" have done instead of what we did.  Isn't this just asking to be rejected since we didn't do this?
In addition to the approaches listed above, methods exist for learning a fixed-degree polynomial combination of a finite set of kernels \citep{cortes2009learning},
 or learning a kernel in an appropriate reproducing kernel Hilbert space of kernels \citep{ong2005learning} and it would be interesting to compare these to our methods, as well. However, this is left for future work. Another idea left for future work is to run the finite-kernel learning methods on the top of the base-kernels found by our method.
\fi

\if0
In this paper we propose a new method for kernel learning.
This method finds a linear combination of kernels from a \emph{continuously parameterized} family of kernels with non-negative weights.
The algorithm works in the spirit of forward stagewise additive modeling \citep{hastie2001elements}(Section 10.3). %\todo{Is this the best reference?}
This method is based on the principle of kernel alignment~\citep{shawe2002kernel,cortes2010two}: the resulting kernel should be ``well-aligned'' with the desired outputs.
%Our second method is derived from the simple idea that a well-aligned kernel should be such that for any pairs of inputs, the centered kernel should ``classify'' well the product of the corresponding outputs (assuming the outputs are encoded using $\pm1$).
We evaluate this method empirically along with other kernel learning techniques from the literature.
We illustrate, using an artificially constructed example,
 that when lacking sufficient {\em a priori} knowledge,
combinations of kernels from a continuous family might be more powerful than
 combinations from a finite set chosen {\em a priori}.
We also show the performance of the new method on two real-world datasets.
Our results suggest that our new method is competitive with state-of-the-art kernel learning methods.

Another advantage of our method compared to the standard multiple kernel learning methods is its ability to learn multi-dimensional kernel parameters. Standard kernel learning methods require a finite set of base kernels. One common way to build this set is by discretizing the kernel parameter space, e.g. the bandwidth of the Gaussian kernels. The number of base kernels grows exponentially with the dimension of the kernel parameter. However, we show that our method is able to search in multi-dimensional kernel parameter spaces. We show that there are cases in which learning a multi-dimensional kernel parameter will lead to more accurate classifiers.\todo{This paragraph should be rewritten}


%However, we first give the context of our methods. Instead of attempting a comprehensive review of existing kernel learning methods (which would need a long paper on its own), we focus on the key ideas and will cite papers which illustrate these ideas.
%Kernel learning is an approach to improve kernel-based methods by adding the flexibility of learning the kernel function from training data. These methods use training data to learn a suitable kernel function from a given family of kernels, such as a convex combination of a set of kernels.


\section{Background}

% has recently attracted many researchers in the machine learning community.
Kernel learning methods differ in terms of the family of kernels they work with and also in terms of whether the learning of a predictor happens simultaneously with learning the kernel (single-stage), or it happens after the kernel is constructed (two-stage).

As far as the family of kernels is concerned,
 the simplest idea is to start with a finite set of base kernels
 and restrict the search to a linear combination of these kernels.
If the search is further restricted to combinations with non-negative coefficients,
the resulting kernel will stay positive-semidefinite.
This property makes possible the use of (computationally) efficient
  and theoretically well-justified learning algorithms.
The coefficients can be further restricted, for example, by constraining their norm, such as their $\ell_1$-norm, \citep[e.g.,][]{lanckriet2004learning, sonnenburg2006large}, or their $\ell_2$-norm, \citep[e.g.,][]{cortes2009l2,kloft2011lp}.
These lead to qualitatively different problems,
 both in terms of their computational complexity and statistical properties as discussed, e.g.,
 by \citet{cortes2009l2}.
By restricting the set of base kernels to a finite set, one rules out a large class of kernels.
For example, tuning the bandwidth of a Gaussian kernel will be possible only up to some limited accuracy.
The problem of kernel learning within continuously parameterized families of kernels was studied, e.g., by
 \citet{CrisCamSW99,argyriou2005learning}.
One difficulty is that this formulation does not necessarily lead to convex or ``easy'' optimization problems.
Other options which have been explored previously include
 learning a fixed-degree polynomial combination of a finite set of kernels \citep{cortes2009learning},
 or learning a kernel in an appropriate reproducing kernel Hilbert space of kernels \citep{ong2005learning}.

Another dimension of kernel learning is based on whether learning happens in a single stage or whether it happens in two stages.
In a single-stage procedure, the final predictor and the kernel are learned simultaneously, usually by optimizing a single objective function, which is derived from an estimate of the risk of the predictor.
Examples include the methods by \citet{lanckriet2004learning,ong2005learning,cortes2009l2}.
In a two-stage procedure, first a kernel is learned, then the learned kernel is used in a second stage to produce a predictor. Examples of methods that use this approach include the methods by \citet{lanckriet2004learning} (Section 4.7) and \citet{cortes2010two}.

All these choices have their own benefits and drawbacks.
Working with a finite set of base kernels (usually) provides computational advantages.
However, as we shall illustrate, by way of example, in certain cases choosing the base set might be nontrivial  in the sense that missing out the ``right'' kernels from the base set can lead to dramatically degraded performance.
However, in some cases, there is no continuously parameterized family of kernels (e.g., the base kernels themselves could be derived from data), so it is natural to work with methods which consider finite families of kernels.  Next, single-stage methods might be preferred because they optimize a criterion which is directly related to the performance of the final predictor. However, the picture is more complicated since many of these methods are only optimizing for surrogate losses (e.g., in classification).

We introduce a new two-stage method for kernel learning based on maximizing a notion of kernel alignment. Our approach will handle continuously parameterized sets of base kernels.

%Further, the situation can be compared to that of the relationship between discriminative and generative methods: Despite their indirect nature, generative methods (which are the analogs to two-stage methods) have their own place in the toolkit of machine learning researchers, as they might actually work better for example in low-data situations. \todo{You are welcome to add/remove to this.}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\if0
Different families of kernels have been studied so far. One of the widely-used families of kernels is the convex combination of a finite set of kernels. \citet{lanckriet2004learning} studied the problem of learning the dual coefficients of SVM along with optimizing a linear combination of a set of kernel matrices, $K = \sum_{i=1}^r \mu_i K_i$, with $L_1$ regularization on the weight vector $\mu$ and requiring that the resulting kernel, $K$, is positive semidefinite. Due to the $L_1$ penalty, the resulting combination of kernels is sparse. They show that this form of multiple kernel learning is a semidefinite program (SDP). Semidefinite programs, despite being convex, are computationally expensive to solve. \citet{lanckriet2004learning} simplified the problem by replacing the condition $K \succeq 0$ with another condition that required the kernel weights be non-negative, i.e. $\mu \geq 0$. They show that the new problem formulation is a second-order cone programming problem (SOCP), which is an improvement in terms of the computational complexity over the original SDP problem.

\citet{cortes2009l2} proposed an efficient iterative algorithm for learning a linear combination of base kernels with $L_2$ penalty on the kernel weight vector. Given the dual coefficients of the kernel-based method, they propose a closed-form solution to compute the kernel weights. Therefore, in each iteration, the algorithm computes the dual coefficients using standard solvers for kernel methods and the kernel weights until convergence criteria are met. \citet{cortes2009l2} claim that as the number of kernels increases the $L_2$ regularization of the kernel weight vector leads to more accurate predictors than the $L_1$ regularization. \citet{kloft2009efficient} generalized multiple kernel learning to $\ell_p$-norms when $p > 1$. They present several efficient methods for computing the kernel weight vector.

\citet{argyriou2005learning} proposed learning multiple kernels from a continuously parametrized set of kernels, i.e. kernels of the form $k(\sigma)(x,x')$ in which $\sigma$ is chosen from a continuous parameter space. In other words their method is useful when there are infinite number of parametrized base kernels. They propose an iterative regularized risk minimization algorithm that optimizes $\sigma$ in each iteration and adds a new kernel to the previous combination. The optimization of $\sigma$ is not convex in general, however \citet{argyriou2006dc} show that for some family of base kernels, such as Gaussian kernels, it belongs to the class of DC programs.



The above methods learn linear combinations of kernels. There are, however, techniques that address other approaches to kernel learning. For example, \citet{cortes2009learning} considered learning a polynomial combination of a finite set of kernels up to a certain degree. \citet{ong2005learning} proposed \emph{hyperkernels} as an approach for learning the kernel function. Hyperkernels are positive semidefinite kernels of the form $k((x,z),(x',z'))$. For each hyperkernel, there exists an underlying RKHS. They formulate the problem as a semidefinite program that learns a kernel function from the RKHS associated with the specified hyperkernel.

In this paper, we focus on learning a combination of kernels. As we mentioned, a large group of kernel learning methods focus on learning a convex combination of a \emph{finite} set of kernels. Base kernels may be generated from a parametrized family of kernels, such as Gaussian kernels, with a specific parameter value for each kernel. Let us consider Gaussian kernels parametrized with a one-dimensional parameter $\sigma$ that controls width of the bell. The common practice to build base kernels is to choose $r$ values from an interval and compute the kernel matrices for a given dataset with the chosen values. The kernel learning algorithm then learns the best convex combination of the provided base kernels. The accuracy of the resulting predictor depends on the number of base kernels and the chosen values of the kernel parameters. Without prior knowledge, it is usually difficult to determine appropriate parameter values for base kernels. In this work we address this problem by proposing a method that enables us to learn a combination of base kernels while the parameter of each base kernel is chosen from a continuous set. Our method uses the notion of alignment, i.e. it learns a convex combination of kernels such that the resulting kernel is similar to the target label kernel, i.e. $YY\transpose$, where $Y \in \{-1,1\}^n$.

There are cases when we have already been given a finite set of base kernels. In these situation our new method can not be applied. For these scenarios we present another alignment-based method that learns a convex combination of base kernels. Our problem formulation differs from previous methods for multiple kernel learning that use the notion of alignment. We show in Section \ref{sec:experimental_results} that our new methods outperform the state-of-the-art multiple kernel learning methods.
\fi
\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\if0
\section{Kernel Alignment}
\label{sec:kernel_alignment}

invariant to shifts of the response:
centering
not penalizing the intercept



The notion of kernel alignment was introduced by \citet{shawe2002kernel}. Alignment is a numerical value that measures the similarity of two kernel functions for a given dataset. Let $K, K' \in \mathbb{R}^{n \times n}$ be positive semidefinite kernel matrices obtained by applying kernel functions $k$ and $k'$ respectively over the data $\mathcal{D} = (X_1,\ldots,X_n)$. \citet{shawe2002kernel} define the empirical alignment between the kernels $k$ and $k'$ through\footnote{Remember that $\langle A,B\rangle_F = A^\top B$ and for a square matrix $A$, $\|A\|_F^{1/2} = \langle A,A \rangle$.}
\begin{eqnarray}
	%A(k,k';\mathcal{D})
	A(K,K')
	 &=& \frac{\langle K, K' \rangle_{F}}{\|K\|_F \|K'\|_F}\,.
\label{eq:alignment}
\end{eqnarray}
Alignment can be used as the objective function of an optimization problem in order to learn the kernel. \citet{lanckriet2004learning} propose a quadratically constrained quadratic program (QCQP) to maximize alignment between a non-negative linear combination of a set of base kernels and the target label kernel, $K_Y = YY\transpose$, where $Y \in \{-1,1\}^n$ are the labels of the training data. The resulting kernel can then be used with any kernel-based method to learn a predictor. This suggests a two-step kernel learning algorithm. In the first step the algorithm learns a kernel from a given family that maximizes the alignment with the target label kernel, over the given training data, and in the second step the algorithm employs a kernel-based method such as SVM and ridge regression to learn the final predictor using the kernel learned from the first step. Recently, \citet{cortes2010two} uses this method to learn a non-negative linear combination of base kernels. Their method uses $L_2$ regularization on the kernel weights. However, \citet{cortes2010two} propose a slightly different definition of alignment. Their definition is based on centering in the feature space.

Let $\Phi: \mathcal{X} \rightarrow H$ be the feature map associated with a positive semidefinite kernel function $k: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$. Let $P$ be the distribution that generates data points $x \in \mathcal{X}$. In order to center the kernel function $k$, we should center the associated feature map, $\Phi$, i.e. $\Phi - \mathbb{E}_x[\Phi]$, in which $\mathbb{E}_x[\Phi]$ is the expected value of $\Phi$ when $x$ is drawn according to the distribution $P$. For each pair of instances, $x,x' \in \mathcal{X}$, the value of the centered kernel, $k_c$, is defined by
\begin{eqnarray}
	k_c(x,x') &=& \langle \Phi(x) - \mathbb{E}_x[\Phi] , \Phi(x') - \mathbb{E}_{x'}[\Phi] \rangle \nonumber \\
	&=& k(x,x') - \mathbb{E}_x[k(x,x')] - \mathbb{E}_{x'}[k(x,x')] \nonumber \\
	&+& \mathbb{E}_{x,x'}[k(x,x')].
\label{eq:kernel_centering}
\end{eqnarray}
Given a positive semidefinite kernel matrix $K \in \mathbb{R}^{n \times n}$, the corresponding centered kernel matrix, $K_c$ can easily be computed by
\begin{eqnarray}
	[K_c]_{pq} = K_{pq} - \frac{1}{n} \sum_{i=1}^n K_{iq}	- \frac{1}{n} \sum_{j=1}^n K_{pj} + \frac{1}{n^2} \sum_{i,j=1}^n K_{ij}. \nonumber
\end{eqnarray}
In matrix form it can computed by
\begin{eqnarray}
K_c &=& \left(\mathbf{I}_n - \frac{1}{n}\mathbf{1}\mathbf{1}\transpose\right)K\left(\mathbf{I}_n - \frac{1}{n}\mathbf{1}\mathbf{1}\transpose\right). \nonumber
\end{eqnarray}

The alignment between two kernel functions, according to \citet{cortes2010two}, is defined using the expected value of the centered kernel functions:
\begin{eqnarray}
	A(k,k') &=& \frac{\mathbb{E}[k_c k'_c]}{\sqrt{\mathbb{E} [k^2_c] \mathbb{E} [k'^2_c]}}.
\end{eqnarray}
The empirical alignment of two kernels over the dataset $\mathcal{D} = \{x_1,\ldots,x_n\}$ is defined by
\begin{eqnarray}
	\widehat{A}(k,k';\mathcal{D}) &=& \frac{\langle K_c,K'_c \rangle_F}{\|K_c\|_F \|K'_c\|_F},
\end{eqnarray}
where $K_c$ and $K'_c$ are the centered versions of the kernel matrices $K$ and $K'$ respectively.

\citet{cortes2010two} emphasize on the importance of centering kernels with an example. In the example they choose a linearly separable dataset and a linear kernel that can be used to perfectly separate the data. They expect to see the maximum value of alignment between the linear kernel and the target label kernel, $K_Y$, regardless of the proportion of data points in each class as long as data remain linearly separable. However, they observe that if the kernel matrices are not centered, the value of empirical alignment varies as the proportion of data in each class changes. Therefore, they conclude that without centering, the definition of alignment does not correlate well with performance.
\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\newcommand{\ra}{\rightarrow}
\newcommand{\real}{\mathbb{R}}

\section{The New Method}
\label{sec:new_method}

%We propose two new methods that maximize the empirical alignment between the learned kernel and the target label kernel.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\if0
In Section~\ref{sec:continuous_method} we propose a novel idea for learning a combination of kernels chosen from a continuously parametrized set of kernels.
Thereafter, in Section~\ref{sec:nilanjan_method}, we describe another multiple kernel learning algorithm that is based on maximizing a different form of alignment.
\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%We start with the method that considers a continuously parameterized set of kernels.
The purpose of this section is to describe our new method.
Let us start with the introduction of the problem setting and the notation.
We consider binary classification problems, where the data ${\cal D} = ((X_1,Y_1),\ldots,(X_n,Y_n))$ is a sequence of independent, identically distributed random variables, with $(X_i,Y_i)\in \real^d\times \{-1,+1\}$.
For convenience, we introduce two other pairs of random variables $(X,Y)$, $(X',Y')$, which are also independent of each other and they share the same distribution with $(X_i,Y_i)$.
The goal of classifier learning is to find a predictor, $g:\real^d \ra \{-1,+1\}$ such that the predictor's risk, $L(g) = \mathbb{P}( g(X)\not=Y )$, is close to the Bayes-risk, $\inf_g L(g)$. We will consider a two-stage method, as noted in the introduction. The first stage of our method will pick some kernel $k:\real^d\times\real^d \ra \real$ from some set of kernels ${\cal K}$ based on ${\cal D}$, which is then used in the second stage, using the same data ${\cal D}$ to find a good predictor.\footnote{One could consider splitting the data, but we see no advantage to doing so. Also, the methods for the second stage are not a focus of this work and the particular methods used in the experiments are described later.}

%\subsection*{Continuously Parametrized Kernel Set}
%\label{sec:continuous_method}

Consider a parametric family of base kernels, $(\kappa_\sigma)_{\sigma\in \Sigma}$.
The  kernels considered by our method belong to the set
\[
\mathcal{K} = \left\{ \sum_{i=1}^r \mu_i \kappa_{\sigma_i} : r \in \mathbb{N}, \mu_i \geq 0, \sigma_i \in \Sigma, i=1,\ldots,r \right\},
\]
i.e., we allow non-negative linear combinations of a finite number of base kernels.
For example, the base kernel could be a Gaussian kernel, where $\sigma>0$ is its bandwidth:
$\kappa_\sigma(x,x') = \exp(-\|x-x'\|^2/\sigma^2)$, where $x,x'\in \real^d$.
However, one could also have a separate bandwidth for each coordinate.


\newcommand{\EE}[1]{\mathbb{E}\left[#1\right]}
\newcommand{\eqdef}{\stackrel{{\rm def}}{=}}
\newcommand{\ipL}[1]{\left\langle #1 \right\rangle}
\newcommand{\ip}[1]{\langle #1 \rangle}
\newcommand{\normL}[1]{\left\|#1\right\|}
\newcommand{\norm}[1]{\|#1\|}
The ``ideal'' kernel underlying the common distribution of the data
is $k^*(x,x') = \EE{\, YY' \,| \, X=x,X'=x'\,}$.
Our new method attempts to find a kernel $k \in {\mathcal{K}}$ which is maximally aligned to
this ideal kernel, where, following~\citet{cortes2010two}, the alignment between two kernels $k,\tilde{k}$ is measured by the {\em centered alignment metric},\footnote{Note that the word metric is used in its everyday sense and not in its mathematical sense.}
\[
A_c(k,\tilde{k}) \eqdef \frac{ \ip{k_c,\tilde{k}_c} }{ \norm{k_c}\norm{\tilde{k}_c} }\,,
%\frac{\EE{ k_c(X,X') \tilde{k}_c(X,X')}} {\sqrt{\EE{k_c(X,X')^2 }\, \EE{\tilde{k}_c(X,X')^2} }}\,,
\]
where
$k_c$ is the kernel underlying $k$ centered in the feature space (similarly for $\tilde{k}_c$),
$\ip{k,\tilde{k}} = \EE{ k(X,X') \tilde{k}(X,X') }$ and $\norm{k}^2 = \ip{k,k}$.
A kernel $k$ centered in the feature space, by definition, is the unique kernel  $k_c$,
 such that for any $x,x'$,
$k_c(x,x') = \ip{ \Phi(x) - \EE{\Phi(X)}, \Phi(x') - \EE{ \Phi(X) } }$, where $\Phi$ is a feature map underlying $k$.
By considering centered kernels $k_c$, $\tilde{k}_c$ in the alignment metric,
 one implicitly matches the mean responses $\mathbb{E}[k(X,X')]$, $\mathbb{E}[\tilde{k}(X,X')]$ before considering the alignment between the kernels (thus, centering depends on the distribution of $X$).
An alternative way of stating this is that centering cancels mismatches of the mean responses between the two kernels.
When one of the kernels is the ideal kernel, centered alignment effectively standardizes the alignment by cancelling the effect of imbalanced class distributions.
For further discussion of the virtues of centered alignment, see the paper by \citet{cortes2010two}.

Since the common distribution underlying the data is unknown, one resorts to empirical approximations to alignment and centering, resulting in the empirical alignment metric,
\[
A_c(K,\tilde{K}) = \frac{ \ip{K_c,\tilde{K}_c}_F }{ \norm{K_c}_F\norm{\tilde{K}_c}_F }\,,
\]
where, $K=(k(X_i,X_j))_{1\le i,j\le n}$, and $\tilde{K} = (\tilde{k}(X_i,X_j))_{1\le i,j\le n}$ are the kernel matrices underlying $k$ and $\tilde{k}$, and for a kernel matrix, $K$, $K_c = C_n K C_n$, where $C_n$ is the so-called centering matrix defined by $C_n = I_{n\times n} - \mathbf{1} \mathbf{1}^\top /n$, $I_{n\times n}$ being the $n\times n$ identity matrix and $\mathbf{1} = (1,\ldots,1)^\top \in \real^n$.
%
\newcommand{\bY}{\mathbf{Y}}
The empirical counterpart of maximizing $A_c(k,k^*)$ is to maximize $A_c(K,\hat{K}^*)$, where $\hat{K}^* \eqdef \bY \bY^T$, and $\bY  =(Y_1,\ldots,Y_n)^\top$ collects the responses into an $n$-dimensional vector.
Here, $K$ is the kernel matrix derived from a kernel $k \in {\cal K}$. To make this connection clear, we will write $K=K(k)$.
Define $f:{\mathcal K} \ra \real$ by $f(k) = A_c( K(k), \hat{K}^* )$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\if0
We present a new algorithm for learning a non-negative linear combination of kernels with the objective of maximizing the empirical alignment between the resulting kernel and the target label kernel, $K_Y$. As we shall see, our method will be able to learn a linear combination of kernels chosen from a continuously parametrized set of base kernels. One famous example is Gaussian kernels with one dimensional parameter $\sigma$: $\kappa_\sigma(x,x') = \exp(-\|x-x'\|^2/\sigma^2)$, where $\sigma > 0$. In this paper we mainly focus on base kernels with one-dimensional parameters. We will address kernels with multi-dimensional parameters later. The resulting kernel is a linear combination of base kernels. In other words we consider kernels of the form
\begin{eqnarray}
	\mathcal{K} = \left\{ \sum_{\ell=1}^r \mu_\ell \kappa_{\sigma_\ell} : r \in \mathbb{N}, \mu_\ell \geq 0, \sigma_\ell \in \Sigma, \ell=1,\ldots,r \right\} \nonumber
\end{eqnarray}
where $\Sigma$ is the parameter space.


%\begin{eqnarray}
%	\mathcal{K}(\mathcal{S}) = \left\{ \int_{\Sigma} \kappa_\sigma \mu(\sigma) d\sigma \right\},
%\label{eq:continuous_kernel_form}
%\end{eqnarray}
%where $\mu(\sigma) \geq 0$ and
%\begin{eqnarray}
%	\int_{\Sigma} \mu(\sigma) d\sigma < \infty. \nonumber
%\end{eqnarray}


The optimization problem is defined as maximizing the alignment between a kernel and the target label kernel. Let us assume for now that all base kernels are centered. We will come back to this technicality later. Since $\langle YY_c\transpose, YY_c\transpose \rangle_F$ does not depend on the learned kernel, we can omit that from the optimization problem:
\begin{eqnarray}
	\max_{k\in\mathcal{K}} && f(k) = \frac{\langle K, YY\transpose \rangle_F}{\sqrt{\langle K,K \rangle_F}},
\label{eq:optimization_problem}
\end{eqnarray}
where $K = [k(x_i,x_j)]_{i,j=1,\ldots,n}$. Note that $\langle K, YY_c\transpose \rangle_F = \langle K, YY\transpose \rangle_F$ since we assume that $K$ is centered.
\fi
%and $\mathcal{K}$ is the set of non-negative linear combinations of a set of base kernels: $\mathcal{K} = \{\sum_{i=1}^\infty \mu_i \kappa_i: \quad \mu_i\geq 0\}$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

To find an approximate maximizer of $f$, we propose a steepest ascent approach to {\em forward stagewise additive modeling} (FSAM). FSAM~\citep{hastie2001elements} is an iterative method for optimizing an objective function by sequentially adding new basis functions without changing the parameters and coefficients of the previously added basis functions.
%We use the version which makes steepest ascent steps in each iteration.
In the steepest ascent approach, in iteration $t$, we search for the base kernel in $(\kappa_\sigma)$ defining the direction in which the growth rate of $f$ is the largest, locally in a small neighborhood of the previous candidate $k^{t-1}$:
\newcommand{\eps}{\varepsilon}
\renewcommand{\epsilon}{\varepsilon}
\begin{equation}
\label{eq:sigmatdef}
\sigma^*_t = \argmax_{\sigma\in \Sigma}
\lim_{\eps\ra 0} \frac{f(k^{t-1}+\eps\, \kappa_\sigma)-f(k^{t-1})}{\eps}\,.
\end{equation}
Once $\sigma^*_t$ is found, the algorithm finds the coefficient $0\le \eta_t \le \eta_{\max}$\footnote{In all our experiments we use the arbitrary value $\eta_{\max}=1$. Note that the value of $\eta_{\max}$, together with the limit $T$ acts as a regularizer. However, in our experiments, the procedure always stops before the limit $T$ on the number of iterations is reached.} such that $f(k^{t-1}+\eta_t \kappa_{\sigma_t^*})$ is maximized and the candidate is updated using $k^t = k^{t-1}+\eta_t \kappa_{\sigma_t^*}$.
The process stops  when  the objective function $f$ ceases to increase by an amount larger than $\theta>0$, or when the number of iterations becomes larger then a predetermined limit $T$, whichever happens earlier.
\begin{algorithm}[tb]
\caption{Forward stagewise additive modeling for
 kernel learning with a continuously parametrized set of kernels.
 For the definitions of $f$, $F$, $F'$ and $K:{\mathcal K} \ra \real^{n\times n}$, see the text.
}
\label{alg:continuous_method}
\begin{algorithmic}[1]
    \STATE \textbf{Inputs:} data ${\cal D}$, kernel initialization parameter $\varepsilon$, the number of iterations $T$,
     tolerance $\theta$, maximum stepsize $\eta_{\max}>0$.
    %\STATE Let $c(K) = (I-11\transpose/n) K (I-11\transpose/n)$. // centering function
%    \STATE Let $f(K) = \frac{\langle K, YY_c\transpose \rangle_F}{\sqrt{\langle K,K \rangle_F}}$. // alignment function
    \STATE $K^0 \leftarrow \varepsilon I_n$.
    \FOR{$t=1$ {\bfseries to} $T$}
			\STATE $P \leftarrow F'(K^{t-1})$ % \frac{\textbf{d} f}{\textbf{d} K} (K^{t-1})$.
			\STATE $P \leftarrow C_n\, P\, C_n$
			\STATE $\sigma^* = \argmax_{\sigma\in \Sigma}\, \ip{ P, K(\kappa_\sigma) }_F$ % \sum_{ij} P_{ij} \kappa_{\sigma}(X_i,X_j)$.
			\STATE $K' =  C_n\, K (\kappa_{\sigma^*})\, C_n$
			\STATE $\eta^* = \argmax_{0\le \eta \le \eta_{\max}} F(K^{t-1} + \eta K' )$
% 			\STATE \textbf{if} $\eta^* = 0$ \textbf{then} terminate. % This is not needed because of the check of the objective function value two lines later
			\STATE $K^t \leftarrow K^{t-1} + \eta^*K'$
 			\STATE \textbf{if} $F(K^t) \leq F(K^{t-1})+\theta$ \textbf{then} terminate
		\ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{proposition}\label{prop:dd}
The value of $\sigma_t^*$ can be obtained by
\begin{eqnarray}
\sigma_t^* = \argmax_{\sigma\in \Sigma} \,
	\ipL{\, K(\kappa_\sigma), F'(\, (K(k^{t-1}))_c ) \, }_F\,,
\label{eq:sigma_star}
\end{eqnarray}
where for a kernel matrix $K$,
\begin{align}
\label{eq:Fder}
%F'(K) = \norm{K}_F^{-1}( \hat{K}^*_c - \norm{K}_F^{-2}\ip{ K, \hat{K}^*_c}_F\, K )\,.
%F'(K) = \frac{ \norm{K}_F \hat{K}^*_c - \norm{K}_F^{-1}\ip{ K, \hat{K}^*_c}_F\, K }
%				   { \norm{K}_F^2 \norm{\hat{K}^*_c}_F}\,.
F'(K) = \frac{ \hat{K}^*_c - \norm{K}_F^{-2}\ip{ K, \hat{K}^*_c}_F\, K }
				   { \norm{K}_F \norm{\hat{K}^*_c}_F}\,.
\end{align}
\end{proposition}
The proof can be found in the supplementary material. The crux of the proposition is that the directional derivative in~\eqref{eq:sigmatdef} can be calculated and gives the expression maximized in~\eqref{eq:sigma_star}.

In general, the optimization problem~\eqref{eq:sigma_star} is not convex and the cost of obtaining a (good approximate) solution is hard to predict.  Evidence that, at least in some cases, the function to be optimized is not ill-behaved is presented in Section~\ref{sec:non_convexity} of the supplementary material. In our experiments, an approximate solution to~\eqref{eq:sigma_star} is found using numerical methods.\footnote{
%\citet{argyriou2005learning} encountered a similar problem.
%They propose a DC-programming approach \citep{horst1999dc}
% to approach their problem \citep{argyriou2006dc}.
% CS: I do not think that this has any relevance to our problems whatsoever.
In particular, we use the \textsf{fmincon} function of Matlab, with the interior-point algorithm option.
}
As a final remark to this issue, note that, as is usual in boosting, finding the global optimizer in~\eqref{eq:sigma_star} might not be necessary for achieving good statistical performance.

%However, empirically we observed that this optimization problem may have an interesting structure.
%For example, for  Gaussian kernels where the bandwidth is optimized,
%the function to be optimized seems to have only two local maxima.\footnote{True?}

The other parameter, $\eta_t$, however, is easy to find, since the underlying optimization problem has a closed form solution:
\begin{proposition}\label{prop:pp2}
The value of $\eta_t$ is given by $\eta_t=\argmax_{\eta\in \{0,\eta^*,\eta_{\max}\}} f(k^{t-1}+\eta \kappa_{\sigma_t^*} )$,
where $\eta^*=\max(0,(ad-bc)/(bd-ae))$ if $bd-ae\not=0$ and $\eta^*=0$ otherwise, $a=\ip{K,\hat{K}^*_c}_F$, $b=\ip{K',\hat{K}^*_c}_F$, $c=\ip{K,K}_F$, $d=\ip{K,K'}_F$, $e=\ip{K',K'}_F$ and  $K= (K(k^{t-1}))_c$, $K'=(K( \kappa_{\sigma_t^*} ))_c$.
\end{proposition}

The pseudocode of the full algorithm is presented in Algorithm~\ref{alg:continuous_method}.
The algorithm needs the data, the number of iterations  ($T$) and a tolerance ($\theta$) parameter, in addition to a parameter $\eps$ used in the initialization phase and $\eta_{\max}$. The parameter $\eps$ is used in the initialization step to avoid division by zero, and its value has little effect on the performance. Note that the cost of computing a kernel-matrix, or the inner product of two such matrices is $O(n^2)$. Therefore, the complexity of the algorithm (with a naive implementation) is at least quadratic in the number of samples. The actual cost will be strongly influenced by how many of these kernel-matrix evaluations (or inner product computations) are needed in~\eqref{eq:sigma_star}. In the lack of a better understanding of this, we include actual running times in the experiments, which give a rough indication of the computational limits of the procedure.
% is needed because $F'(0)$ is not defined, hence, the algorithm starts at a positive diagonal matrix with small diagonal elements $\eps$.
% shows our proposed algorithm for kernel learning when base kernels are continuously parametrized.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\if0
 In our case, the objective is to maximize the empirical alignment. Let $k^{t-1}$ be the expansion of base kernels built up to iteration $t-1$. At iteration $t$, the algorithm chooses a base kernel that if added, has the most increase in the objective function, i.e.
\begin{eqnarray}
	\kappa^* &=& \argmax_{\kappa_\sigma} \quad \lim_{\epsilon \to 0} \frac{f(k^{t-1}+\epsilon \kappa_\sigma) - f(k^{t-1})}{\epsilon} \nonumber \\
  				 &=& \argmax_{\kappa_\sigma} \quad \frac{\textbf{d} f}{\textbf{d} \mu(\sigma)} (K^{t-1}).
\label{eq:coordinate_ascent}
\end{eqnarray}
Using the chain rule of derivatives, we have
\begin{eqnarray}
	\frac{\textbf{d} f}{\textbf{d} \mu(\sigma)} &=& \langle \frac{\textbf{d} f}{\textbf{d} K}, \frac{\textbf{d} K}{\textbf{d} \mu(\sigma)} \rangle_F \nonumber \\
	&=& \langle \frac{\textbf{d} f}{\textbf{d} K}, \kappa_\sigma \rangle_F.
\label{eq:chain_rule}
\end{eqnarray}
This means that at iteration $t$, our method chooses the base kernel that has the maximum value of the Frobenius inner product with the matrix $\frac{\textbf{d} f}{\textbf{d} K}(K^{t-1})$. Once we find $\kappa^*$, we add it along with the coefficient $\eta$ to the current combination, $k^{t-1}$:
\begin{eqnarray}
	k^{t} &\longleftarrow& k^{t-1} + \eta \kappa^*.
\end{eqnarray}
The coefficient $\eta \geq 0$ can be set to an infinitesimal value or it can be computed through line search, i.e.
\begin{eqnarray}
	\eta^* &=& \argmax_{\eta \geq 0} \frac{\langle K^{t-1} + \eta \kappa^*, YY\transpose \rangle_F}{\sqrt{\langle K^{t-1} + \eta \kappa^*, K^{t-1} + \eta \kappa^* \rangle_F}}.
\label{eq:eta_optimal}
\end{eqnarray}
Equation \eqref{eq:eta_optimal} has a closed-form solution. If the best value of $\eta$ is zero, it indicates that no further improvement in the value of alignment is possible, therefore the algorithm stops.

What distinguishes our new method from other alignment maximization algorithms is that it is applicable when we have a continuously parametrized set of base kernels. For example if the base kernels are parametrized by $\sigma$, i.e. $\kappa_\sigma(x,x')$, then finding the best base kernel is equivalent to finding the best value of kernel parameter:
\begin{eqnarray}
	\sigma^* &=& \argmax_\sigma \sum_{ij} \kappa_\sigma(x_i,x_j) \frac{\textbf{d} f}{\textbf{d} K}(K^{t-1}_{ij}).
\label{eq:problem_formulation_continuously_parametrized_gaussian_kernel}
\label{eq:optimal_sigma}
\end{eqnarray}
As we mentioned earlier, in this paper we consider base kernels with one parameter, however problem \eqref{eq:optimal_sigma} does not have such restriction. In fact as long as we can solve problem \eqref{eq:optimal_sigma} efficiently, we can apply this method to base kernels with multi-dimensional parameters.
\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\if0
Problem \eqref{eq:optimal_sigma} is not convex in general. \citet{argyriou2005learning} encountered a similar problem. They propose a DC-programming approach \citep{horst1999dc} to solve it \citep{argyriou2006dc}. In our experiments, we use the \textsf{fminsearch} function in Matlab that employs the simplex search method proposed by \citet{lagarias1998convergence}.

Another note regarding the algorithm is that at each iteration we center matrix $P$ in line 6 to compensate for not centering the base kernels, since we have not computed the new base kernel matrix yet. Note that $\langle P, K_c(\sigma)\rangle_F = \langle P_c, K(\sigma) \rangle_F$.
\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Experimental Evaluation}
\label{sec:experimental_results}

In this section we compare our kernel learning method with several kernel learning methods on synthetic and real data; see Table \ref{tab:list_of_methods} for the list of methods.
%\footnote{Our source code that includes the implementation of all nine methods is available at \url{https://sites.google.com/site/codemkl/}.}
 %The methods are labeled by the first-letter of the first-author's last name from the work where they were introduced (when applicable).
 Our method is labeled CA for Continuous Alignment-based kernel learning. In all of the experiments, we use the following values with CA: $T = 50$, $\varepsilon = 10^{-10}$, and $\theta = 10^{-3}$.
The first two methods, i.e. our algorithm, and CR~\citep{argyriou2005learning}, are able to pick kernel parameters from a continuous set, while the rest of the algorithms work with a finite number of base kernels.

In Section \ref{sec:synthetic_data_experiment} we use synthetic data to illustrate the potential advantage of methods that work with a continuously parameterized set of kernels and the importance of combining multiple kernels. We also illustrate in a toy example that multi-dimensional kernel parameter search can improve performance. These are followed by the evaluation of the above listed methods on several real datasets in Section \ref{sec:real_data_experiment}.

\begin{table}[t]
\caption{List of the kernel learning methods evaluated in the experiments. The key to the naming of the methods is as follows:
CA stands for ``continuous alignment'' maximization, CR stands for ``continuous risk'' minimization, DA stands for ``discrete alignment'', D1, D2, DU should be obvious.
}
\label{tab:list_of_methods}
\begin{center}
\begin{tabular}{|l|l|}
  \hline
	\textbf{Abbr.} & \textbf{Method} \\ \hline
	CA  & Our new method\\ \hline
	CR  & From \citet{argyriou2005learning} \\ \hline
	DA  & From \citet{cortes2010two} \\ \hline
	D1  & $\ell_1$-norm MKL \citep{kloft2011lp} \\ \hline
	D2  & $\ell_2$-norm MKL \citep{kloft2011lp} \\ \hline
	DU  & Uniform weights over kernels \\ \hline
\end{tabular}
\end{center}
\end{table}


\subsection{Synthetic Data}
\label{sec:synthetic_data_experiment}

The purpose of these experiments is mainly to provide empirical proof for the following hypotheses:
{(H1)} The combination of multiple kernels can lead to improved  performance as compared to what can be achieved with a single kernel, even when in theory a single kernel from the family suffices to get a consistent classifier.
{(H2)} The methods that search the continuously parameterized families are able to find the ``key'' kernels and their combination.
{(H3)} Our method can even search multi-dimensional parameter spaces, which in some cases is crucial for good performance.

To illustrate (H1) and (H2) we have designed the following problem:
the inputs are generated from the uniform distribution over the interval $[-10,10]$. The label of each data point is determined by the function $y(x) = \textrm{sign}(f(x))$, where $f(x) = \sin(\sqrt{2}x) + \sin(\sqrt{12}x) + \sin(\sqrt{60}x)$.
Training and validation sets include $500$ data points each, while the test set includes $1000$ instances.
%\todo{I thought you will present results for a simpler function.}
Figure~\ref{fig:dirichlet_synthetic}(a) shows the functions $f$ (blue curve) and $y$ (red dots).
For this experiment we use Dirichlet kernels of degree one,\footnote{We repeated the experiments using Gaussian kernels with nearly identical results.}
 parameterized with a frequency parameter $\sigma$: $\kappa_{\sigma}(x,x') = 1 + 2\cos(\sigma \|x-x'\|)$.

In order to  investigate (H1), we trained classifiers
%In this example a kernel learning method must find all three important frequencies to achieve good accuracy. In order to confirm this, we measured the accuracy of the classifier trained using kernels parametrized with different subsets of the set of frequencies used to generate the data. Classifiers that were trained
with a single frequency kernel from the set $\sqrt{2}$, $\sqrt{12}$, and $\sqrt{60}$ (which we thought were good guesses of the single best frequencies).
The trained classifiers achieved misclassification error rates of $26.1\%$, $26.8\%$, and $28.6\%$, respectively. Classifiers trained with a pair of frequencies, i.e. $\{\sqrt{2},\sqrt{12}\}$, $\{\sqrt{2},\sqrt{60}\}$, and $\{\sqrt{12},\sqrt{60}\}$ achieved error rates of $16.4\%$, $20.0\%$, and $21.3\%$, respectively (the kernels were combined using uniform weights). Finally, a classifier that was trained with all three frequencies achieved an error rate of $2.3\%$.

Let us now turn to (H2). As shown in Figure~\ref{fig:dirichlet_synthetic}(b), the CA and CR methods both achieved a misclassification error close to what was seen when the three best frequencies were used, showing that they are indeed effective.\footnote{In all of the experiments in this paper, the classifiers for the two-stage methods were trained using the soft margin SVM method, where the  regularization coefficient of SVM was chosen by cross-validation from $10^{\{-5,-4.5,\ldots,4.5,5\}}$.}
Furthermore, Figure~\ref{fig:dirichlet_synthetic}(c) shows that the discovered frequencies are close to the frequencies used to generate the data.
For the sake of illustration, we also tested the methods which require the discretization of the parameter space. We choose  ten Dirichlet kernels with $\sigma \in \{0,1,\ldots,9\}$, covering the range of frequencies defining $f$.
As can be seen from Figure~\ref{fig:dirichlet_synthetic}(b) in this example the chosen discretization accuracy is insufficient. Although it would be easy to increase the discretization accuracy to improve the results of these methods,\footnote{Further experimentation found that a discretization below $0.1$ is necessary in this example.} the point is that if a high resolution is needed in a single-dimensional problem, then these methods are likely to face serious difficulties in problems when the space of kernels is more complex (e.g., the parameterization is multidimensional). Nevertheless, we are not suggesting that the methods which require discretization are universally inferior, but merely wish to point out that an ``appropriate discrete kernel set'' might not always be available.
% \footnote{Ridge regression was used in the second set of experiments, for reasons we describe later. Hence, we decided to use it here, as well.}
\begin{figure}[htbp]
\vspace{.3in}
\centerline{\includegraphics[width=0.5\linewidth]{Figures/dirichlet_kernel_experiment.eps}}
\vspace{.3in}
\caption{(a): The function $f(x) = \sin(\sqrt{2}x) + \sin(\sqrt{12}x) + \sin(\sqrt{60}x)$ used for generating synthetic data, along with $\text{sign}(f)$. (b): Misclassification percentages obtained by each algorithm. (c): The kernel frequencies found by the CA method.}
\label{fig:dirichlet_synthetic}
\end{figure}



To illustrate (H3) we designed a second set of problems:
The instances for the positive (negative) class are generated from a $d=50$-dimensional Gaussian distribution with  covariance matrix $C = I_{d \times d}$ and mean $\mu_1 = \rho \frac{\theta}{\|\theta\|}$ (respectively, $\mu_2 = -\mu_1$ for the negative class). Here $\rho=1.75$. \todo{(Mike) I don't understand what the instance is.  So you have two 50-dimensional Gaussians. What's X and Y?}  %The instances of the two classes are drawn from these Gaussian distributions. 
The vector $\theta \in [0,1]^d$ determines the relevance of each feature in the classification task, e.g. $\theta_i=0$ implies that the distributions of the two classes have zero means in the $i$th feature, which renders this feature irrelevant. The value of each component of vector $\theta$ is calculated as $\theta_i = (i/d)^\gamma$, where $\gamma$ is a constant that determines the relative importance of the elements of $\theta$. We generate seven datasets with $\gamma \in \{0,1,2,5,10,20,40\}$.
For each value of $\gamma$, the training set consists of $50$ data points (the prior distribution for the two classes is uniform). The test error values are measured on a test set with $1000$ instances. We repeated each experiment $10$ times and report the average misclassification error and alignment measured over the test set along with the running time.

We test two versions of our method: one that uses a family of Gaussian kernels with a common bandwidth (denoted by CA-1D), and another one (denoted by CA-nD) that searches in the space $(\kappa_\sigma)_{\sigma\in (0,\infty)^{50}}$, where each coordinate has a separate bandwidth parameter, $\kappa_{\sigma}(x,x') = \exp(-\sum_{i=1}^{d}  (x_i-x_i')^2/\sigma_i^{2} )$. Since the training set is small, one can easily overfit while optimizing the alignment. Hence, we modify the algorithm to shrink the values of the bandwidth parameters to their common average value by modifying~\eqref{eq:sigma_star}:
\begin{eqnarray}
\sigma_t^* = \argmin_{\sigma\in \Sigma} \,
	&& -\ipL{\, K(\kappa_\sigma), F'(\, (K(k^{t-1}))_c ) \, }_F\, \nonumber \\ && + \lambda  \| \sigma - \bar{\sigma} \|_2^2,
\label{eq:new_sigma_star}
\end{eqnarray}
where, $\bar{\sigma} = \frac{1}{r} \sum_{i=1}^r \sigma_i$ and $\lambda$ is a regularization parameter.
%The top-left plot in Figure \ref{fig:my_toy_experiment} shows the value of $\theta$ in each case.
We also include results obtained for
 finite kernel learning methods. For these methods, we generate $50$ Gaussian kernels with bandwidths $\sigma \in m g^{\{0,\ldots,49\}}$, where $m=10^{-3}$, and $g\approx1.33$. Therefore, the bandwidth range constitutes a geometric sequence from $10^{-3}$ to $10^3$.
 Further details of the experimental setup can be found in Section~\ref{apx:50d} of the supplementary material.

Figure \ref{fig:my_toy_experiment} shows the results. Recall that the larger the value of $\gamma$, the larger the number of nearly irrelevant features. Since methods which search only a one-dimensional space cannot differentiate between relevant and irrelevant features, their misclassification rate increases with $\gamma$. Only CA-nD is able to cope with this situation and even improve its performance.
We observed that without regularization, though, CA-nD drastically overfits (for small values of $\gamma$).
We also show the running times of the methods to give the reader an idea about the scalability of the methods. The running time of CA-nD is larger than CA-1D both because of the use of cross-validation to tune $\lambda$ and because of the increased cost of the multidimensional search. Although the large running time might be a problem, for some problems, CA-nD might be the only method to deliver good performance amongst the methods studied.\footnote{We have not attempted to run a multi-dimensional version of the CR method, since already the one-dimensional version of this method is at least one order of magnitude slower than our CA-1D method.}
% (the cost of an update in  the CA-method scales quadratically with the number of samples)
\begin{figure*}[htbp]
\vspace{.3in}
\centerline{\includegraphics[width=0.75\linewidth]{Figures/MyToyExperiment_2.eps}}
\vspace{.3in}
\caption{Performance and running time of various methods for a $50$-dimensional synthetic problem as a function of the relevance parameter $\gamma$. Note that the number of irrelevant features increases with $\gamma$. For details of the experiments, see the text.}
\label{fig:my_toy_experiment}
\end{figure*}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\if0
The methods based on a finite set of base kernels were provided with a set of kernels that did not contain close matches to the key generating frequencies.  Not surprisingly, \todo{Why is this unsurprising?} all of these methods performed poorly on this example.  Note that we are not claiming that finite kernel learning algorithms perform poorly in general.  This example is just intended to illustrate that it is critical for the base kernel set to include appropriate choices of parameter values.  Without any prior knowledge it may be difficult to come up with a proper set of base kernels for finite kernel learning methods.  For continuous kernel learning methods, it appears enough for the right parameterization of kernels to be found as good parameters from the continuous set can be identified and combined.
\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Real Data}
\label{sec:real_data_experiment}

We evaluate the methods listed in Table \ref{tab:list_of_methods} on several binary classification tasks from MNIST and the UCI Letter recognition dataset, along with several other datasets from the UCI machine learning repository \citep{frank2010uci} and Delve datasets (see, \url{http://www.cs.toronto.edu/~delve/data/datasets.html}).

\paragraph{MNIST.}
In the first experiment, following~\citet{argyriou2005learning}, we choose 8 handwritten digit recognition tasks of various difficulty from the MNIST dataset \citep{lecun-mnist-web-2010}. This dataset consists of $28\times28$ images with pixel values ranging between $0$ and $255$. In these experiments, we used Gaussian kernels with parameter $\sigma$: $G_\sigma(x,x') = \exp(-\|x-x'\|^2/\sigma^2)$. Due to the large number of attributes (784) in the MNIST dataset, we only evaluate the 1-dimensional version of our method. For the algorithms that work with a finite kernel set, we pick 20 kernels with the value of $\sigma$ picked from an equidistant discretization of interval $[500,50000]$.
In each experiment, the training and validation sets consist of $500$ and $1000$ data points, while the test set has $2000$ data points.
%For two-stage methods we train the second-stage classifier using the soft margin SVM method.
%The regularization coefficient of SVM is chosen from the set $10^{\{-5,-4.5,\ldots,4.5,5\}}$.
We repeated each experiment 10 times. Due to the lack of space, the test-set error plots for all of the problems can be found in the supplementary material (see Section~\ref{apx:realdata}). In order to give an overall impression of the algorithms' performance, we ranked them based on the results obtained in the above experiment. Table~\ref{tab:median_rank_and_time} reports the median ranks of the methods for the experiment just described.

Overall, methods that choose $\sigma$ from a continuous set outperformed their finite counterparts. This suggests again that for the finite kernel learning methods the range of $\sigma$ and the discretization of this range is important to the accuracy of the resulting classifier.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\if0
In order to better understand the relationship between the width of the Gaussian kernel and the accuracy of the resulting classifiers, we measured the misclassification error of a classifier trained with a single Gaussian kernel characterized by $\sigma$.  In Figure \ref{fig:mnist_error_sigma}, we plot the error rates versus the value of $\sigma$ in the range of $[100,10000]$ for four tasks from the MNIST dataset.
\begin{figure}[htbp]
\vspace{.3in}
\centerline{\includegraphics[width=1\linewidth]{Figures/mnist_error_sigma.eps}}
\vspace{.3in}
\caption{Misclassification percentages of single Gaussian kernels evaluated over four tasks from the MNIST dataset. The horizontal axis represents the width of the Gaussian kernel ($\sigma$), and the vertical axis is the misclassification percentage of the resulting classifier.}
\label{fig:mnist_error_sigma}
\end{figure}
These results suggest that for the MNIST dataset it is sufficient to consider values of $\sigma$ in the interval $[100,8000]$  to perform well across the chosen four tasks. We therefore repeated the first experiment with $\sigma$'s chosen from $[100,8000]$, again choosing $10$ values for $\sigma$ with an equidistant discretization of the selected interval. The results with the new range are shown in Figure \ref{fig:result_mnist_100_to_8000}.
The first two methods (CA and CR) are not affected by this change, since they learn kernel parameters from a continuous set. However, the accuracy of the finite kernel learning methods improved as compared to the previous results. This is because values of $\sigma$ outside of the new interval are not needed and because due to the smaller size of the new interval, the resolution within this relevant range is increased.
\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\if0
When the base kernels are chosen from interval $[100,50000]$, the kernels with $\sigma < 5000$ are not present in the kernel set (except for the kernel with $\sigma=100$). As it can be seen in Figure~\ref{fig:mnist_error_sigma}, there are kernels with $\sigma < 5000$ that perform well on the MNIST tasks individually. In the second experiment, when we choose base kernels parameters from interval $[100,8000]$ these kernels are present in the base kernel set. Therefore, we expect better performance by the finite kernel learning methods when base kernels are chosen from the smaller interval. \todo[inline]{MB: Why?  We need to give some explanation for how this could possibly improve things to consider a smaller set. Arash: I added the explanation at the end of the previous paragraph. I think this is addressed now. If you think it's good now, remove this todo. Todo for Mike.}
\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{table*}[t]
\caption{Median rank and running time (sec.) of kernel learning methods obtained in experiments.}
\label{tab:median_rank_and_time}
\begin{center}
\begin{tabular}{c l|c|c|c|c|c|c|c|}
					&	 & CA-1D & CA-nD & CR & DA  & D1  & D2 & DU  \\ \hline
	\multirow{3}{*}{Rank} &MNIST & 1 & N/A &  2  & 4.5 & 4.5 & 5  & 4   \\
												&Letter& 1 & 4.5 & 2  & 3.5   & 7   & 6  & 5   \\
												&11 datasets& 3 & 2 & 3 & 3 & 4 & 6 & 6 \\ \hline \hline
	\multirow{2}{*}{Time} &MNIST & $12\pm1$ & N/A & $377\pm56$ & $31\pm1$ & $57\pm6$ & $58\pm3$ & $10\pm1$ \\
												&Letter& $9\pm1$ & $1986\pm247$ & $590\pm21$ & $11\pm1$ & $21\pm1$ & $22\pm1$ & $5\pm1$ \\ \hline
\end{tabular}
\end{center}
\end{table*}

\paragraph{UCI Letter Recognition.}
In another experiment, we evaluated these methods on 12 binary classification tasks from the UCI Letter recognition dataset. This dataset includes $20000$ data points of the 26 capital letters in the English alphabet.
For each binary classification task, the training and validation sets include $300$ and $200$ data points, respectively. The misclassification errors are measured over $1000$ test points. As with MNIST, we used Gaussian kernels. However, in this experiment, we ran our method with both 1-dimensional and $n$-dimensional search procedures. The rest of the methods learn a single parameter and the finite kernel learning methods were provided with 20 kernels with $\sigma$'s chosen from the interval $[1,200]$ in an equidistant manner. The plots of misclassification error and alignment are available in the supplementary material (see Section~\ref{apx:realdata}). We report the median rank of each method in Table \ref{tab:median_rank_and_time}. While the 1-dimensional version of our method outperforms the rest of the methods, the classifier built on the kernel found by the multi-dimensional version of our method did not perform well.  We examined the value of alignment between the learned kernel and the target label kernel on the test set achieved by each method. The results are available in the supplementary material (see Section~\ref{apx:realdata}). The multidimensional version of our method achieved the highest value of alignment in every task in this experiment.  Higher value of alignment between the learned kernel and the ideal kernel does not necessarily translate into higher value of accuracy of the classifier.  Aside from this observation, the same trends observed in the MNIST data can be seen here. The continuous kernel learning methods (CA-1D and CR) outperform the finite kernel learning methods.

\paragraph{Miscellaneous datasets.}
In the last experiment we evaluate all methods on 11 datasets chosen from the UCI machine learning repository and Delve datasets. Most of these datasets were used previously to evaluate kernel learning algorithms \citep{lanckriet2004learning,cortes2009l2,cortes2009learning,cortes2010two,rakotomamonjy2008simplemkl}. The specification of each dataset and the performance of each method are available in the supplementary material (see Section~\ref{apx:realdata}). The median rank of each method is shown in Table \ref{tab:median_rank_and_time}. Contrary to the Letter experiment, in this case the multi-dimensional version of our method outperforms the rest of the methods.

%In MNIST and UCI Letter experiments, the method that combines kernels uniformly, i.e. DU, outperforms the $\ell_1$-norm and $\ell_2$-norm kernel learning methods. This is in agreement with the previous findings in the literature of kernel learning \citep{cortes2009invited}.

\paragraph{Running Times.}  We measured the time required for each run and each kernel learning method in the MNIST and the UCI Letter experiments. In each case we took the average of the running time of each method over all tasks. The average required time along with the standard error values are shown in Table \ref{tab:median_rank_and_time}. Among all methods, the DU method is fastest, which is expected, as it requires no additional time to compute kernel weights. The CA-1D is the fastest among the rest of the methods. In these experiments our method converges in less than 10 iterations (kernels). The general trend is that one-stage kernel learning methods, i.e., D1, D2, and CR, are slower than two-stage methods, CA and DA. Among all methods, the other continuous kernel learning method, CR, is slowest, since (1) it is a one-stage algorithm and (2) it usually requires more iterations (around $50$) to converge. We also examined the DC-Programming version of the CR method \cite{argyriou2006dc}. While it is faster than the original gradient-based approach (roughly three times faster), it is still significantly slower than the rest of the methods in our experiments. 
%As usual, these results should be taken only as rough indicators of the methods' computational requirements.

%\begin{figure}[htbp]
%\vspace{.3in}
%\centerline{\includegraphics[width=1\linewidth]{Figures/new_mnist_runtime.eps}}
%\vspace{.3in}
%\caption{Running time (in seconds) of the kernel learning methods in the MNIST data experiments.}
%\label{fig:result_new_mnist_runtime}
%\end{figure}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\if0
The continuous kernel learning methods, i.e. ACG and ARG are iterative algorithms that require no convex optimization solver. In these experiments we observed that our method, ACG finds the best kernel combination after only a few iterations (usually less than 10), whereas the ARG algorithm needs more iterations to terminate. For example in different tasks of the UCI Letter recognition experiment the ACG algorithm finished in about 5 iterations, whereas the ARG algorithm required more than $50$.  As a result, we found that the ACG method was usually the fastest of all the methods, while ARG was usually the slowest.  Among finite kernel learning methods, the alignment based methods, i.e. ALP, CA, and LA were generally faster than the others.  However, ALP became slower as the training set increased in size.
\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Conclusion and Future Work}

We presented a novel method for kernel learning. This method addresses the problem of learning a kernel in the positive linear span of some continuously parameterized kernel family. The algorithm implements a steepest ascent approach to forward stagewise additive modeling to maximize an empirical centered correlation measure between the kernel and the empirical approximation to the ideal response-kernel.
The method was shown to perform well in a series of experiments, both with synthetic and real-data. We showed that in single-dimensional kernel parameter search, our method outperforms standard multiple kernel learning methods without the need to discretizing the parameter space. While the method of \citet{argyriou2005learning}  also benefits from searching in a continuous space, it was seen to require significantly more computation time compared to our method. We also showed that our method can successfully deal with high-dimensional kernel parameter spaces, which, at least in our experiments, 
the method of  \citet{argyriou2005learning,argyriou2006dc} had problems with. \todo{Why? and what about the DC variant!?}

The main lesson of our experiments is that the methods that start by discretizing the kernel space without using the data might lose the potential to achieve good performance before any learning happens. 

We think that currently our method is the most efficient method to design data-dependent dictionaries that provide competitive performance. %However, this is only an experimental observation at the moment. 
It remains an interesting problem to be explored in the future whether there exist methods that are provably efficient and yet their performance remains competitive. Although in this work we directly compared our method to finite-kernel methods, it is also natural to combine dictionary search methods (like ours) with finite-kernel learning methods. However, the thorough investigation of this option remains for future work.

A secondary outcome of our experiments is the observation that although test-set alignment is generally a good indicator of good predictive performance, a larger test-set alignment does not necessarily transform into a smaller misclassification error. Although this is not completely unexpected, we think that it will be important to thoroughly explore the implications of this observation.

\if0
With the help of appropriately constructed synthetic data, we illustrated the potential advantage of this method which avoids the preselection of a finite base set from a continuously parameterized kernel family.
With this example we also illustrated that in some cases the combination of multiple kernels gives significantly better performance than any single kernel (from a base family) alone.
Further experiments with real data indicated that our method is competitive with other state-of-the-art multiple kernel learning methods.
We also showed that our method can be used to learn multi-dimensional kernel parameters. A property that the standard kernel learning methods that work with a set of base kernels cannot achieve due to the exponential growth in the number of base kernels.
\fi
% \subsubsection*{Acknowledgments}

%\bibliographystyle{unsrtnat}
\bibliographystyle{apalike}
\bibliography{./references}

\clearpage
\newpage
\appendix
\section{Proofs}
\subsection{Proof of Proposition~\ref{prop:dd}}
First, notice that the limit in~\eqref{eq:sigmatdef} is a directional derivative, $D_{\kappa_\sigma} f(k^{t-1})$.
By the chain rule,
\[
D_{\kappa_\sigma} f(k^{t-1})
= \ip{ \, K(\kappa_\sigma), \, F'_c( K(k^{t-1}) ) \,}_F\,,
\]
where, for convenience, we defined $F_c(K) = A_c(K,\hat{K}^*)$.
Define
\[
F(K) = \ip{K,\hat{K}^*_c}_F/(\norm{K}_F \norm{\hat{K}^*_c}_F)
\]
so that $F_c(K) = F( K_c )$.
Some calculations give that
\[
%F'(K) = \norm{K}_F^{-1}( \hat{K}^*_c - \norm{K}_F^{-2}\ip{ K, \hat{K}^*_c}_F\, K )\,.
%F'(K) = \frac{ \norm{K}_F \hat{K}^*_c - \norm{K}_F^{-1}\ip{ K, \hat{K}^*_c}_F\, K }
%				   { \norm{K}_F^2 \norm{\hat{K}^*_c}_F}\,.
F'(K) = \frac{ \hat{K}^*_c - \norm{K}_F^{-2}\ip{ K, \hat{K}^*_c}_F\, K }
				   { \norm{K}_F \norm{\hat{K}^*_c}_F}\,
\]
(which is the function defined in~\eqref{eq:Fder}).
We claim that the following holds:
\begin{lemma}
$F_c'(K) = C_n F'( K_c ) C_n$.
\end{lemma}
%\todo{The proof is in the file, commented out.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{proof}
By the definition of derivatives, as $H\ra 0$,
\[F(K+H)-F(K) = \ip{ F'(K),H }_F + o(\|H\|).\]
Also,
 \[F_c(K+H)-F_c(K) = \ip{ F'_c(K),H }_F + o(\|H\|).\]
Now,
\begin{align*}
F_c(K+H) - F_c(K) &= F(C_nK C_n+C_n H C_n) - F(C_n K C_n)\\
&=\ip{F'(K_c), C_n H C_n }_F + o(\|H\|)\\
&=\ip{C_n F'(K_c) C_n, H }_F + o(\|H\|),
\end{align*}
 where the last property follows from the cyclic property of trace.
Therefore, by the uniqueness of derivative, $F_c'(K) = C_n F'(K_c) C_n$.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Now, notice that $C_n F'(K_c) C_n = F'(K_c)$.
Thus, we see that the value of $\sigma_t^*$ can be obtained by
\[
\sigma_t^* = \argmax_{\sigma\in \Sigma} \,
	\ipL{\, K(\kappa_\sigma), F'(\, (K(k^{t-1}))_c ) \, }_F\,,
\]
which was the statement to be proved.
\subsection{Proof of Proposition~\ref{prop:pp2}}
Let $g(\eta) = f(k^{t-1}+\eta \kappa_{\sigma_t^*})$. Using the definition of $f$, we find that with some constant $\rho>0$,
\[
g(\eta) =\rho\, \frac{a+b \eta }{(c+2d\eta+e\eta^2)^{1/2}}.
\]
Notice that here the denominator is bounded away from zero (this follows from the form of the denominator of $f$).
In particular, $e>0$.
Further,
\begin{align}
\label{eq:glim}
\lim_{\eta\ra \infty} g(\eta) = - \lim_{\eta\ra -\infty} g(\eta) = \rho \frac{ b }{ \sqrt{e} }.
\end{align}
Taking the derivative of $g$ we find that
\[
g'(\eta) = \rho \, \frac{bc-ad+(bd-ae)\eta}{(c+2d\eta + e\eta^2)^{3/2}}.
\]
Therefore, $g'$ has at most one root and $g$ has at most one global extremum, from which the result follows by solving for the root of $g'$ (if $g'$ does not have a root, $g$ is constant).
\if0
Because of the choice of $\sigma_t^*$ (steepest ascent direction), $g'(0)\ge 0$. If $bd-ae=0$
and $g'(0)>0$ then $g'(\eta)>0$ for all $\eta$. This contradicts~\eqref{eq:glim}, therefore if $bd-ae=0$ then we must also have $bc-ad=0$ and $g$ is constant. Therefore, any value of $\eta$ works as the maximizer of $g$. If $bd-ae$ is nonzero, $g'$ has a unique root, $\eta^* = (ad-bc)/(bd-ae)$, which makes $\eta^*$  the global extremum point of $g$. The rest follows because $g$ using what we just said that $g$ has a single global extremum point.
\fi
\section{Details of the numerical experiments}
In this section we provide further details and data for the numerical results.
\subsection{Non-Convexity Issue}
\label{sec:non_convexity}
As we mentioned in Section~\ref{sec:new_method}, our algorithm may need to solve a non-convex optimization problem in each iteration to find the best kernel parameter. Here, we explore this problem numerically, by plotting the function to be optimized in the case of a Gaussian kernel with a single bandwidth parameter.
In particular, we plotted the objective function of Equation~\ref{eq:sigma_star} with its sign flipped, therefore we are interested in the local minima of function $h(\sigma) = -\ipL{\, K(\kappa_\sigma), F'(\, (K(k^{t-1}))_c ) \, }_F$, see
 Figure \ref{fig:result_sigma}.
The function $h$ is shown for some iterations of some of the tasks from both the MNIST and the UCI Letter experiments. The number inside parentheses in the caption specifies the corresponding iteration of the algorithm. On these plots, the objective function does not have more than 2 local minima. Although in some cases the functions have some steep parts (at the scales shown), their optimization does not seem very difficult.
\begin{figure*}[t]
\vspace{.3in}
\centerline{\includegraphics[width=0.8\linewidth]{Figures/fig_non_convex.eps}}
\vspace{.3in}
\caption{The flipped objective function underlying~\eqref{eq:sigma_star} as a function of $\sigma$, the parameter of a Gaussian kernel in selected MNIST and UCI Letter problems. Our algorithm needs to find the minimum of
these functions (and similar ones).}
\label{fig:result_sigma}
\end{figure*}


%\begin{figure*}[htbp]
%\vspace{.3in}
%\begin{center}
%\subfloat[Part 1][odd vs. even, (1)]{\includegraphics[width=1.2in]{Figures/sigma_mnist_oe_iter_1.pdf} \label{fig:s1}}
%\subfloat[Part 2][odd vs. even, (2)]{\includegraphics[width=1.2in]{Figures/sigma_mnist_oe_iter_2.pdf} \label{fig:s2}}
%\subfloat[Part 3][0 vs. 6, (1)]{\includegraphics[width=1.2in]{Figures/sigma_mnist_06_iter_1.pdf} \label{fig:s3}}
%\subfloat[Part 4][0 vs. 6, (2)]{\includegraphics[width=1.2in]{Figures/sigma_mnist_06_iter_2.pdf} \label{fig:s4}} \\
%\subfloat[Part 5][B vs. E, (1)]{\includegraphics[width=1.2in]{Figures/sigma_letter_be_iter_1.pdf} \label{fig:s5}}
%\subfloat[Part 6][B vs. E, (2)]{\includegraphics[width=1.2in]{Figures/sigma_letter_be_iter_2.pdf} \label{fig:s6}}
%\subfloat[Part 7][B vs. E, (3)]{\includegraphics[width=1.2in]{Figures/sigma_letter_be_iter_3.pdf} \label{fig:s7}}
%\subfloat[Part 8][B vs. E, (4)]{\includegraphics[width=1.2in]{Figures/sigma_letter_be_iter_4.pdf} \label{fig:s8}} \\
%\vspace{.3in}
%\caption{The flipped objective function underlying~\eqref{eq:sigma_star} as a function of $\sigma$, the parameter of a Gaussian kernel in selected MNIST and UCI Letter problems. Our algorithm needs to find the minimum of
%these functions (and similar ones).}
%\label{fig:result_sigma}
%\end{center}
%\end{figure*}

\subsection{Details of the 50-dimensional synthetic dataset experiment}
\label{apx:50d}
The 1-dimensional version of our algorithm, CA-1D, and the CR method, employ Matlab's \textsf{fmincon} function with multiple restarts from the set $10^{\{-3,\ldots,5\}}$, to choose the kernel parameters. The multi-dimensional version of our algorithm, CA-nD, uses \textsf{fmincon} only once, since in this particular example the search method runs on a $50$-dimensional search space, which makes the search an expensive operation. The starting point of the CA-nD method is a vector of equal elements where this element is the weighted average of the kernel parameters found by the CA-1D method, weighted by the coefficient of the corresponding kernels.

The soft margin SVM regularization parameter is tuned from the set $10^{\{-5,-4.5,\ldots,4.5,5\}}$ using an independent validation set with $1000$ instances. We also tuned the value of the regularization parameter in Equation~\eqref{eq:new_sigma_star} from $10^{\{-5,\ldots,14\}}$ using the same validation set (the best value of $\lambda$ is the one that achieves the highest value of alignment on the validation set). We decided to use a large validation set, following essentially the practice of \citet[Section 6.1]{kloft2011lp}, to make sure that in the experiments reasonably good regularization parameters are used, i.e., to factor out the choice of the regularization parameters. This might bias our results towards CA-nD, as compared to CA-1D, though similar results were achieved with a smaller validation set of size $200$. As a final detail note that D1, D2 and CR also use the validation set for choosing the value of their regularization factor, and together with the regularizer, the weights also. Hence, their results might also be positively biased (though we don't think this is significant, in this case).

The running times shown in Figure~\ref{fig:my_toy_experiment} include everything from the beginning to the end, i.e., from learning the kernels to training the final classifiers (the extra cross-validation step is what makes CA-nD expensive).

Figure~\ref{fig:MyToyExperiment_Alignment} shows the (centered) alignment values for the learned kernels (on the test data) as a function of the relevance parameter $\gamma$.  It can be readily seen that the multi-dimensional method has a real-edge over the other methods when the number of irrelevant features is large, in terms of kernel alignment. As seen on Figure~\ref{fig:MyToyExperiment_Alignment}, this edge is also transformed into an edge in terms of the test-set performance. Note also that the discretization is fine enough so that the alignment maximizing finite kernel learning method DA can  achieve the same alignment as the method CA-1D.
\begin{figure}[t]
\vspace{.3in}
\centerline{\includegraphics[width=0.5\linewidth]{Figures/MyToyExperiment_Alignment.eps}}
\vspace{.3in}
\caption{Alignment values in the $50$-dimensional synthetic dataset experiment.}
\label{fig:MyToyExperiment_Alignment}
\end{figure}


\subsection{Detailed results for the real datasets}
\label{apx:realdata}
\begin{figure*}[htbp]
\vspace{.3in}
\centerline{\includegraphics[width=0.8\linewidth]{Figures/new_mnist_testerr.eps}}
\vspace{.3in}
\caption{Misclassification percentages in different tasks of the MNIST dataset.}
\label{fig:result_new_mnist_testerr}
\end{figure*}

% commented out by arash
% Preparation of data: Each letter is converted from a black and white pixel representation to 16 attributes which are statistical moments and edge counts. These features are scaled to integer values in the range of $[0,15]$.

\begin{figure*}[htbp]
\vspace{.3in}
\centerline{\includegraphics[width=0.8\linewidth]{Figures/new_letter_testerr_with_CAnD.eps}}
\vspace{.3in}
\caption{Misclassification percentages in different tasks of the UCI Letter recognition dataset.}
\label{fig:new_letter_testerr}
\end{figure*}

\begin{figure*}[htbp]
\vspace{.3in}
\centerline{\includegraphics[width=0.8\linewidth]{Figures/new_letter_testalignment_with_CAnD.eps}}
\vspace{.3in}
\caption{Alignment values in different tasks of the UCI Letter recognition dataset.}
\label{fig:new_letter_testalignment}
\end{figure*}

\begin{table*}[ht]
\caption{Datasets used in the experiments}
\label{tab:table_label}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
  \hline
	\textbf{Dataset} & \textbf{\# features} & \textbf{\# instances} & \textbf{Training size} & \textbf{Validation size} & \textbf{Test size} \\ \hline
Banana & $2$ & $5300$ & $500$ & $1000$ & $2000$ \\ \hline
Breast Cancer & $9$ & $263$ & $52$ & $78$ & $133$ \\ \hline
Diabetes & $8$ & $768$ & $153$ & $230$ & $385$ \\ \hline
German & $20$ & $1000$ & $200$ & $300$ & $500$ \\ \hline
Heart & $13$ & $270$ & $54$ & $81$ & $135$ \\ \hline
Image Segmentation & $18$ & $2086$ & $400$ & $600$ & $1000$ \\ \hline
Ringnorm & $20$ & $7400$ & $500$ & $1000$ & $2000$ \\ \hline
Sonar & $60$ & $208$ & $41$ & $62$ & $105$ \\ \hline
Splice & $60$ & $2991$ & $500$ & $1000$ & $1491$ \\ \hline
Thyroid & $5$ & $215$ & $43$ & $64$ & $108$ \\ \hline
Waveform & $21$ & $5000$ & $500$ & $1000$ & $2000$ \\ \hline
\end{tabular}
\end{center}
\end{table*}


\begin{figure*}[htbp]
\vspace{.3in}
\centerline{\includegraphics[width=0.8\linewidth]{Figures/11_realdata_testerr.eps}}
\vspace{.3in}
\caption{Misclassification percentages obtained in 11 datasets.}
\label{fig:11_realdata_testerr}
\end{figure*}


\end{document}

mypaper.bbl
\begin{thebibliography}{}

\bibitem[Argyriou et~al., 2006]{argyriou2006dc}
Argyriou, A., Hauser, R., Micchelli, C., and Pontil, M. (2006).
\newblock {A DC-programming algorithm for kernel selection}.
\newblock In {\em Proceedings of the 23rd international conference on Machine
  learning}, pages 41--48.

\bibitem[Argyriou et~al., 2005]{argyriou2005learning}
Argyriou, A., Micchelli, C., and Pontil, M. (2005).
\newblock Learning convex combinations of continuously parameterized basic
  kernels.
\newblock In {\em Proceedings of the 18th Annual Conference on Learning
  Theory}, pages 338--352.

\bibitem[B{\"u}hlmann and van~de Geer, 2011]{BuhvdG11}
B{\"u}hlmann, P. and van~de Geer, S. (2011).
\newblock {\em Statistics for High-Dimensional Data: Methods, Theory and
  Applications}.
\newblock Springer.

\bibitem[Cortes, 2009]{Cortes09:invited}
Cortes, C. (2009).
\newblock Invited talk: Can learning kernels help performance?
\newblock In {\em ICML '09}, pages 1--1.

\bibitem[Cortes et~al., 2009a]{cortes2009l2}
Cortes, C., Mohri, M., and Rostamizadeh, A. (2009a).
\newblock L2 regularization for learning kernels.
\newblock In {\em Proceedings of the 25th Conference on Uncertainty in
  Artificial Intelligence}, pages 109--116.

\bibitem[Cortes et~al., 2009b]{cortes2009learning}
Cortes, C., Mohri, M., and Rostamizadeh, A. (2009b).
\newblock Learning non-linear combinations of kernels.
\newblock In {\em Advances in Neural Information Processing Systems 22}, pages
  396--404.

\bibitem[Cortes et~al., 2010]{cortes2010two}
Cortes, C., Mohri, M., and Rostamizadeh, A. (2010).
\newblock Two-stage learning kernel algorithms.
\newblock In {\em Proceedings of the 27th International Conference on Machine
  Learning}, pages 239--246.

\bibitem[Cristianini et~al., 2002]{shawe2002kernel}
Cristianini, N., Kandola, J., Elisseeff, A., and Shawe-Taylor, J. (2002).
\newblock On kernel-target alignment.
\newblock In {\em Advances in Neural Information Processing Systems 15}, pages
  367--373. MIT Press.

\bibitem[Frank and Asuncion, 2010]{frank2010uci}
Frank, A. and Asuncion, A. (2010).
\newblock {UCI} machine learning repository.

\bibitem[Hastie et~al., 2001]{hastie2001elements}
Hastie, T., Tibshirani, R., and Friedman, J. (2001).
\newblock {\em The Elements of Statistical Learning}.
\newblock Springer Series in Statistics. Springer-Verlag New York.

\bibitem[Kloft et~al., 2011]{kloft2011lp}
Kloft, M., Brefeld, U., Sonnenburg, S., and Zien, A. (2011).
\newblock $\ell^p$-norm multiple kernel learning.
\newblock {\em Journal of Machine Learning Research}, 12:953--997.

\bibitem[Lanckriet et~al., 2004]{lanckriet2004learning}
Lanckriet, G., Cristianini, N., Bartlett, P., Ghaoui, L., and Jordan, M.
  (2004).
\newblock Learning the kernel matrix with semidefinite programming.
\newblock {\em Journal of Machine Learning Research}, 5:27--72.

\bibitem[{LeCun} and Cortes, 2010]{lecun-mnist-web-2010}
{LeCun}, Y. and Cortes, C. (2010).
\newblock {MNIST} handwritten digit database.

\bibitem[Rakotomamonjy et~al., 2008]{rakotomamonjy2008simplemkl}
Rakotomamonjy, A., Bach, F., Canu, S., and Grandvalet, Y. (2008).
\newblock Simple{MKL}.
\newblock {\em Journal of Machine Learning Research}, 9:2491--2521.

\bibitem[Sonnenburg et~al., 2006]{sonnenburg2006large}
Sonnenburg, S., R{\"a}tsch, G., Sch{\"a}fer, C., and Sch{\"o}lkopf, B. (2006).
\newblock Large scale multiple kernel learning.
\newblock {\em The Journal of Machine Learning Research}, 7:1531--1565.

\end{thebibliography}
