Distance Metric Learning for Kernel Machines
\addr Department of Computer Science and Engineering
Saint Louis
MO 63130
\addr Criteo
Palo Alto
CA 94301
\noindent Recent work in metric learning has significantly improved the state-of-the-art in $k$-nearest neighbor classification. Support vector machines (SVM), particularly with RBF kernels, are amongst the most popular classification algorithms that uses distance metrics to compare examples. This paper provides an empirical analysis of the efficacy of three of the most popular Mahalanobis metric learning algorithms as pre-processing for SVM training. We show that none of these algorithms generate metrics that lead to particularly satisfying improvements for SVM-RBF classification. As a remedy we introduce support vector metric learning (SVML), a novel algorithm that seamlessly combines the learning of a Mahalanobis metric with the training of the RBF-SVM parameters. We demonstrate the capabilities of SVML on nine benchmark data sets of varying sizes and difficulties. In our study, SVML %achieves the lowest classification error rates up to significance on most of these data sets and outperforms all alternative state-of-the-art metric learning algorithms in terms of accuracy and establishes itself as a serious alternative to the standard Euclidean metric with model selection by cross validation. %As SVML alleviates the need to set any SVM meta-parameters it is also faster than alternatives, which typically require cross-validation for parameter setting.
conclusion.tex
In this paper we investigate metric learning for SVMs. An empirical study of three of the most widely used out-of-the-box metric learning algorithms for kNN classification shows that these are not particularly well suited for SVMs. As an alternative, we derive SVML, an algorithm that seamlessly combines support vector classification with distance metric learning. SVML learns a metric that attempts to minimize the validation error of the SVM prediction at the same time as it trains the SVM classifier. On several standard benchmark datasets we demonstrate that our algorithm achieves state-of-the-art results with very high reliability. 
% We also demonstrate that our algorithm can effectively visualize the SVM decision boundary for high dimensional data in $2$ or $3$ dimensions.  
An important feature of SVML is that it is very insensitive to its few parameters (which we all set to default values) and does not require any model selection by cross validation. In fact, we demonstrate that SVML outperforms traditional SVM-RBF with the Euclidean distance (where parameters are set through cross validation)  consistently in accuracy while requiring a comparable amount of computation time. These aspects make SVML a very promising general-purpose metric learning algorithm for SVMs with RBF kernels, which also incorporates automatic model selection. 
We are currently implementing an open-source plug-in for the popular LIBSVM library~\citep{CC01a} and extending it to multi-class settings. %We hope that SVML will become a powerful algorithm for pre-processing, data visualization and parameter tuning in almost all areas of science where SVMs are used. 

%As future work, we will extend our algorithm into multi-class settings. 
%We hope that SVML will provide a convenient way for researchers from different disciplines to automatically pre-process, analyze and visualize their data.


intro.tex
%Dimensionality reduction algorithms are used in many different areas of science. Common applications range from data visualization, over de-noising to pre-processing for algorithms with high time complexities with respect to the data dimensionality. Although the best known algorithm -- Principal Component Analysis~\citep{Jolliffe86} -- dates back to the beginning of the last century, recent research has focussed on supervised dimensionality reduction which explicitly preserves information valuable for classification and clustering~\citep{Goldberger05,rish2008closed,Torresani07,yu2006supervised}.
Many machine learning algorithms, such as $k$-nearest neighbors (kNN)~\citep{Cover67}, $k$-means~\citep{lloid1982least} or support vector machines (SVM)~\citep{cortes1995support} with shift-invariant kernels, require a distance metric to compare instances. These algorithms rely on the assumption that semantically similar inputs are close, whereas semantically dissimilar inputs are far away. Traditionally, the most commonly used distance metrics are uninformed norms, like the Euclidean distance. In many cases, such uninformed norms are sub-optimal. To illustrate this point, imagine a scenario where two researchers want to classify the same data set of facial images. The first one classifies people by age, the second by gender. Clearly, two images that are similar according to the first researcher's setting might be dissimilar according to the second's. 
%Clearly, both need to use very different semantic definitions of ``similarity''. 

Uninformed norms ignore two important contextual components of most machine learning applications. First, in supervised learning the data is accompanied by labels which essentially encode the semantic definition of similarity. Second, the user knows which machine learning algorithm will be used. Ideally, the distance metric should be tailored to the particular setting at hand, incorporating both of these considerations. 

%Also, for example, if $k$-NN is used as the classifier, then only the distances to the local neighbors affect the classification outcome, whereas in the case of SVMs, the distance to the support vectors determines the prediction of a test point. 

A generalization of the Euclidean distance is the Mahalanobis distance~\citep{mahalanobis1936generalized}. Recent years have witnessed a surge of innovation on  Mahalanobis pseudo-metric  learning~\citep{Davis07itml,Globerson06,Goldberger05,Shental02,Weinberger06distancemetric}. Although these algorithms use different methodologies, the common theme is moving similar inputs closer and dissimilar inputs further away --- where similarity is generally defined through class membership. This transformation can be learned through convex optimization with pairwise constraints~\citep{Davis07itml, Weinberger06distancemetric}, gradient descent with soft neighborhood assignments~\citep{Goldberger05}, or spectral methods based on second-order statistics~\citep{Shental02}. 

Typically, the Mahalanobis metric learning algorithms are used in a two-step approach. First the metric is learned, then it is used for training the classifier or clustering algorithm of choice. 
 The resulting distances are semantically more meaningful than the plain Euclidean distance as they reflect the label information. This makes them  particularly suited for the $k$-nearest neighbor rule, leading to large improvements in classification error~\citep{Davis07itml,Globerson06,Goldberger05,Shental02,Weinberger06distancemetric}. In fact, several algorithms explicitly mimic the $k$-NN rule and minimize a surrogate loss function of the corresponding leave-one-out classification error on the training set~\citep{Goldberger05,Weinberger06distancemetric}.  

Although the $k$-nearest neighbor rule can be a powerful classifier especially in settings with many classes, it comes with certain limitations. For example, the entire training data needs to be stored and processed during test time. Also, in settings with fewer classes (especially binary) it is generally outperformed by Support Vector Machines~\citep{cortes1995support}. 
%However, if other classification algorithms are used, the learned metrics might not be a very strong .
%
%SVMs are often considered the state-of-the art in classification. 
Because of their high reliability as out-of-the-box classifiers, SVMs have become one of the quintessential classification algorithms in many areas of science and beyond. An important part of using SVMs is the right choice of kernel. The kernel function $k(\x_i,\x_j)$ encodes the similarity between two input vectors $\x_i$ and $\x_j$. There are many possible choices for such a  kernel function. One of the most commonly used kernels is the Radial Basis Function (RBF) kernel~\citep{Scholkopf02}, which itself relies on a distance metric. 

%The RBF-kernel for two vectors $\x_i,\x_j$ is defined as $k(\x_i,\x_j)=e^{-\frac{\|\x_i,\x_j\|^2}{\sigma^2}}$ for some $\sigma > 0$.%Most commonly $d(\cdot,\cdot)$ is the standard Euclidean distance, rescaled by a multiplicative factor of $\frac{1}{\sigma}\geq 0$.
This paper considers metric learning for support vector machines. As a first contribution, we review and investigate several recently published kNN metric learning algorithms for the use of SVMs with RBF kernels. 
% that were originally intended for $k$-nearest neighbor classification, and use them for SVM classification. 
%Although these approaches tend to improve classification accuracies in general, it is fair to say that the benefits are somewhat limited. 
We demonstrate empirically that these approaches do not reliably improve SVM classification results up to statistical significance. 
As a second contribution, we derive a novel metric learning algorithm that specifically incorporates the SVM loss function during training. 
%This paper introduces a novel supervised metric learning algorithm explicitly for the RBF kernel in the context of support vector classification. 
%Unlike previous algorithms, we pursue a one-step approach, in which 
Here, we learn the metric to minimize the validation error of the SVM prediction at the same time that we train the SVM. This is in contrast to the two-step approach of first learning a metric and then training the SVM classifier with the resulting kernel.  This algorithm, which we refer to as Support Vector Metric Learning (SVML), is particularly useful for three reasons. First, it achieves state-of-the-art classification results and clearly outperforms other metric learning algorithms that are not explicitly geared towards SVM classification. Second, it provides researchers outside of the machine-learning community a convenient way to automatically pre-process their data before applying SVMs.
% that results in state-of-the-art results with very high reliability. Third, in terms of computation time it is on par  with simple model selection by cross validation. 
% is faster than simple model-selection by 5-fold cross-validation. 
% Third, it can map data into a low dimensional space while learning the SVM, allowing effective visualizations of SVM decision boundaries even for high dimensional data.

%We demonstrate that by learning the representation and the classifier in one optimization, we obtain state-of-the-art classification results even with noisy or badly scaled features.

This paper is organized as follows. In Section~\ref{sec_svm}, we introduce necessary notation and review some background on SVMs. In Section~\ref{sec_metric} we introduce several recently published metric learning algorithms and report results for SVM-RBF classification. In Section~\ref{sec_method} we derive the SVML algorithm and some interesting variations. In Section~\ref{sec_results}, we evaluate SVML on nine publicly available data sets featuring a multitude of different data types and learning tasks. We discuss related work in Section~\ref{sec_related} and conclude in Section~\ref{sec_conclusion}.




klearning.tex
\documentclass[twoside,11pt]{article}

\usepackage{jmlr2e}
\pdfoutput=1

% Definitions of handy macros can go here
% For figures
\usepackage{graphicx} % more modern
%\usepackage{epsfig} % less modern
\usepackage{subfigure}
% For citations
\usepackage{natbib}
\usepackage{wrapfig}

% For algorithms
\usepackage{algorithm}
\usepackage{algorithmic}

% As of 2010, we use the hyperref package to produce hyperlinks in the
% resulting PDF.  If this breaks your system, please commend out the
% following usepackage line and replace \usepackage{icml2011} with
% \usepackage[nohyperref]{icml2011} above.
\usepackage{hyperref}

% Packages hyperref and algorithmic misbehave sometimes.  We can fix
% this with the following command.
\newcommand{\theHalgorithm}{\arabic{algorithm}}

\newcommand{\dataset}{{\cal D}}
\newcommand{\fracpartial}[2]{\frac{\partial #1}{\partial  #2}}

% Heading arguments are {volume}{year}{pages}{submitted}{published}{author-full-names}

% \jmlrheading{1}{2000}{1-48}{4/00}{10/00}{S{\"o}ren Sonnenburg Francis Bach and Cheng Soon Ong}


% Short headings should be running head and authors last names

\ShortHeadings{Distance Metric Learning for Kernel Machines}{}
\firstpageno{1}

\begin{document}

\title{Distance Metric Learning for Kernel Machines}

\author{\name Zhixiang (Eddie) Xu \email xuzx@cse.wustl.edu \\
       \addr Department of Computer Science and Engineering\\
       Washington University in St. Louis\\
       Saint Louis, MO 63130, USA
       \AND
       \name Kilian Q.\ Weinberger \email kilian@wustl.edu \\
       \addr Department of Computer Science and Engineering\\
       Washington University in St. Louis\\
       Saint Louis, MO 63130, USA
       \AND
       \name Olivier Chapelle \email Olivier@chapelle.cc \\
       \addr Criteo \\
	   Palo Alto, CA 94301 }
	   %        \AND
	   %        \name Fei Sha \email feisha@usc.edu \\
	   %        \addr Computer Science Department \\ 
	   % University of Southern California \\
	   % 941 West 37th Place, SAL 300 \\
	   % Los Angeles, CA 90089 }

% \editor{S{\"o}ren Sonnenburg, Francis Bach and Cheng Soon Ong}
\editor{}

\maketitle



\newcommand{\argmax}{\operatornamewithlimits{argmax}}
\newcommand{\argmin}{\operatornamewithlimits{argmin}}
\newcommand{\x}{\mathbf{x}}
\newcommand{\ab}{\mathbf{\alpha}}
\newcommand{\y}{\mathbf{y}}
\newcommand{\Lb}{\mathbf{L}}
\newcommand{\Mb}{\mathbf{M}}
\newcommand{\Ib}{\mathbf{I}}
\newcommand{\Kb}{\mathbf{K}}
\newcommand{\Hb}{\mathbf{H}}
\newcommand{\fix}{\marginpar{FIX}}
\newcommand{\new}{\marginpar{NEW}}

\begin{abstract}
\noindent Recent work in metric learning has significantly improved the state-of-the-art in $k$-nearest neighbor classification. 
Support vector machines (SVM), particularly with RBF kernels, are amongst the most popular  classification algorithms that uses distance metrics to compare examples. This paper provides an empirical analysis of the efficacy of three of the most popular Mahalanobis metric learning algorithms as pre-processing for SVM training. We show that none of these algorithms generate metrics that lead to particularly satisfying improvements for SVM-RBF classification. 
As a remedy we introduce support vector metric learning (SVML), a novel algorithm that seamlessly combines the learning of a Mahalanobis metric with the training of the RBF-SVM parameters. We demonstrate the capabilities of SVML on nine benchmark data sets of varying sizes and difficulties. In our study, SVML  
%achieves the lowest classification error rates up to significance on most of these data sets and 
outperforms all alternative state-of-the-art metric learning algorithms in terms of accuracy and establishes itself as a serious alternative to the standard Euclidean metric with model selection by cross validation. 
%As SVML alleviates the need to set any SVM meta-parameters it is also faster than alternatives, which typically require cross-validation for parameter setting. 
\end{abstract}

{\keywords{metric learning, distance learning, support vector machines, semi-definite programming, Mahalanobis distance}}


\section{Introduction}
\label{sec_introduction}
\input intro.tex


\section{Support Vector Machines}
\label{sec_svm}
\input{svm.tex}

\section{Metric Learning}
\label{sec_metric}
\input setting.tex


\section{Support Vector Metric Learning}
\label{sec_method}
\input method.tex



\section{Results}
\label{sec_results}
\input results.tex

\section{Related Work}
\label{sec_related}
\input related.tex


\section{Conclusion}
\label{sec_conclusion}
\input conclusion.tex


\subsection{Acknowledgements}
We thank Marius Kloft, Ulrich Rueckert, Cheng Soon Ong, Alain Rakotomamonjy, Soeren Sonnenburg and Francis Bach for motivating this work. This material is based upon work supported by the National Institute of Health under grant NIH 1-U01-NS073457-01, and the National Science Foundation under Grant No. 1149882. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Institute of Health and the National Science Foundation. Further, we would like to thank Yahoo Research for their generous support through the Yahoo Research Faculty Engagement Program. 

\small
\bibliographystyle{icml2011}
\bibliography{klearning}


\end{document}

method.tex
%\subsection{Support Vector Metric Learning}

%In this section, we focus on learning a metric explicitly for the SVM classifier with an RBF kernel. 
As a first step towards learning a metric specifically for SVM classification, we incorporate the squared Mahalanobis distance~(\ref{eq:mahala})  into the kernel function (\ref{eq:rbf}) and define the resulting kernel function and matrix as
\begin{equation}
k_{\Lb}(\x_i,\x_j) = e^{-(\x_i-\x_j)^\top\Lb^\top\Lb(\x_i-\x_j)} \ \textrm{and} \ \Kb_{ij}=k_{\Lb}(\x_i,\x_j).\label{eq:kb}
\end{equation}
As mentioned before, the typical Euclidean RBF setting is a special case where $\Lb=\frac{1}{\sigma}\Ib^{d\times d}$. 
%Where the ${\Lb}$ is the linear transformation matrix, with $d$ rows and $d$ columns. If the ${\Lb}$ is an identity matrix, we are not changing the distance metric at all, and it is the same as euclidean distance. If we train the ${\Lb}$ with a goal that further maximizes the margin between support vectors from different classes, we are tweaking the distance metric for SVM. A common approach to optimize kernel SVM is applying cross-validation, which minimizes the validation error by tweaking the kernel parameters including $\sigma$ and constant $C$. Our algorithm explicitly models this technique. We minimize the validation error by tuning the distance metric matrix ${\Lb}$. Since ${\Lb}$ can also be viewed as $d\times d$ parameters of the kernel $\Kb$, we can tune it automatically using a technique proposed in~\citep{Chapelle02choosingmultiple}.


%\subsection{Automatically optimizing the distance metric ${\Lb}$}

\subsection{Loss function}
%\begin{floatingfigure}[r]{0.4\textwidth}
\begin{wrapfigure}{r}{0.45\textwidth}
%\begin{figure}[t]
\vspace{-5ex}
	\centerline{\includegraphics[width=0.45\textwidth]{softfun.pdf}}
 	\caption{The function $s_a(z)$ is a soft (differentiable) approximation of the zero-one loss. The parameter $a$ adjusts the steepness of the curve.}
 	\label{fig:softloss}
	\vspace{-5ex}
\end{wrapfigure}
%\end{floatingfigure}
%\end{figure}
In the Euclidean case, a standard way to select the meta parameter $\sigma$ is through cross-validation. In its simplest form, this involves splitting the training data set into two mutually exclusive subsets: training set $T$ and validation set $V$. The SVM parameters  $\alpha_i,b$ are then trained on $T$ and the outcome is evaluated on the validation data set $V$. After a gridsearch over several candidate values for $\sigma$ (and $C$), the setting that performs the best on the validation data is chosen. For a single meta parameter, search by cross validation is simple and surprisingly effective. If more meta parameters need to be set --- in the case of choosing a matrix $\Lb$, this involves $d\times d$ entries --- the number of possible configurations grows exponentially and the gridsearch becomes infeasible. 


%Instead, we adopt the intuition behind cross validation but follow a more principled approach of finding $\Lb$. 
We follow the intuition of validating meta parameters on a hold-out set of the training data. 
Ideally, we want to find a metric parameterized by $\Lb$ that minimize the classification error ${\cal{E}}_V$ on the validation data set
\begin{eqnarray}
	\Lb=\textrm{arg}\!\min_{\Lb}{\cal E}_V(\Lb) \label{eq:valloss} 
	\textrm{ where: }\ \nonumber 
 	{\cal E}_V(\Lb)=\frac{1}{|V|}\sum_{(\x,y)\in V} [h(\x)=y].
\end{eqnarray}
Here $[h(\x)=y]\in\{0,1\}$ takes on value $1$ if and only if $h(\x)=y$. 
The classifier $h(\cdot)$, defined in~(\ref{eq:svm_h}) depends on parameters $\alpha_i$ and $b$, which are re-trained for every intermediate setting of $\Lb$. Performing the minimization in~(\ref{eq:valloss}) is non-trivial because the sign$(\cdot)$ function in~(\ref{eq:svm_h}) is non-continuous. We therefore introduce a smooth loss function ${\cal L}_V$, which mimics ${\cal E}_V$, but is better behaved. 
%
\begin{equation}
	{\cal L}_V(\Lb)=\frac{1}{|V|}\sum_{(\x,y)\in V} s_a(yh(\x))\ 
	\textrm{ where: }\ s_a(z)=\frac{1}{1+e^{az}}. 
\end{equation}
%
%
The function $s_a(z)$ is the mirrored sigmoid function, a soft approximation of the zero-one loss. The parameter $a$ adjusts the steepness of the curve. In the limit, as $a\gg 0$ the function ${\cal L}_V$ becomes identical to ${\cal E}_V$. Figure~\ref{fig:softloss} illustrates the function $s_a(\cdot)$ for various values of $a$. 

\subsection{Gradient Computation}
Our surrogate loss function ${\cal L}_V$ is continuous and differentiable so we can compute the derivative $\frac{\partial{\cal L}_V}{\partial h(\x)}$. To obtain the derivative of ${\cal L}_V$ with respect to $\Lb$ we need to complete the chain-rule and also compute $\frac{\partial h(\x)}{\partial \Lb}$. The SVM prediction function $h(\x)$, defined in (\ref{eq:svm_h}), depends on $\Lb$ indirectly through $\mathbf{\alpha}_i,b$ and $\Kb$. In the next paragraph we follow the original approach of \citep{Chapelle02choosingmultiple} for kernel parameter learning. This approach has also been used successfully for wrapper-based multiple-kernel-learning~\citep{rakotomamonjy2008simplemkl,sonnenburg2006large,kloft2010non}. 
 For ease of notation,  we abbreviate $h(\x)$ by $h$ and use the vector notation $\alpha=[\alpha_1,\dots,\alpha_n]^\top$. %We take the derivative first with respect to $\alpha\Kb$ and then use the product rule to obtain
% \begin{equation}
% {h(\x_j)} = \displaystyle\sum_{i}^n \alpha_i y_i \Kb_{ij} +b
% \end{equation} 
% \begin{equation}
% \frac{\partial h(\x_j)}{\partial \Lb} = \displaystyle\sum_{i}^n\Big( \frac{\partial {h(\x_j)}}{\partial (\alpha_i \Kb_{ij}^{\Lb})} \frac{\partial (\alpha_i \Kb_{ij}^{\Lb})}{\partial \Lb} \Big) + \frac{\partial {h(\x_j)}}{\partial b} \frac{\partial b}{\partial \Lb} 
% \end{equation} 
% By applying the product rule, we have: 
% \begin{equation}
% \frac{\partial {h(\x_j)}}{\partial \Lb} = \displaystyle\sum_{i}^n \frac{\partial {h(\x_j)}}{\partial (\alpha_i \Kb_{ij}^{\Lb})} \Big(
% 				\frac{\partial \alpha}{\partial \Lb}  \Kb_{ij}^{\Lb} +  \frac{\partial \Kb_{ij}^{\Lb}}{\partial \Lb} \alpha \Big) +
% 				\frac{\partial {h(\x_j)}}{\partial b} \frac{\partial b}{\partial \Lb} 
% \end{equation}
% 
% {\bf Simplified version, by absorbing each $\alpha_i$ into $\alpha$, please keep one that you think is better.}
% \begin{equation}
% \frac{\partial h}{\partial \Lb} = \frac{\partial {h}}{\partial ({\bf \alpha} \Kb)} \frac{\partial ({\bf \alpha} \Kb)}{\partial \Lb} + 
% 				\frac{\partial {h}}{\partial b} \frac{\partial b}{\partial \Lb} 
% \end{equation} 
Applying the chain-rule to the derivative of $h$ results in:
\begin{equation}
\frac{\partial {h}}{\partial \Lb} = \frac{\partial {h}}{\partial \alpha} 
				\frac{\partial \alpha}{\partial \Lb}  + \frac{\partial {h}}{\partial \Kb}  \frac{\partial \Kb}{\partial \Lb}  +
				\frac{\partial {h}}{\partial b} \frac{\partial b}{\partial \Lb}. 
\end{equation}


%use gradient descent or other hill-climbing algorithms to minimize it up to a local minimum. 

% We split the training examples into training and validation. Running a standard SVM algorithm on the training set, we can find support vector coefficient $\alpha^0$ and bias $b^0$ that maximize the SVM's quadratic function $W$:
% \begin{eqnarray}
% (\alpha^0,b^0) = \arg \max_{\alpha,b} W(\alpha,b,L)
% \end{eqnarray}
% Having the $\alpha^0$ and $b^0$, we start to train the metric matrix ${\Lb}$ using the validation set. We construct the loss function by evaluating the classification error on the validation set. Basically, we test the learned $\alpha^0$ and $b^0$ using the validation set, and the result, which is the value of the loss function, represents the classification error. Using the loss function, we can tweak the metric matrix ${\Lb}$. A typical method of minimizing a function is gradient descent. However, the typical SVM loss function, hinge loss, is neither continuous nor differentiable at the hinge point. As an alternative, we use a soft lfunction, sigmoid loss function to mimic the hinge loss function. Thus we can apply the gradient descent to minimize the loss functiong. Let $\{(x_i, y_i)\}_{1\le i\le l}$ be a set of training examples, and $\{(x_j, y_j)\}_{1\le j\le l}$ be a set of validation examples, The loss function is:
% \begin{eqnarray}
% {\cal L} = sigmoid \bigg( - \displaystyle\sum_{j}^n \Big( \big(\displaystyle\sum_{i}^n (\alpha_i^0 K_{svml}  y_i)+b^0 \big) y_j \Big) \bigg)
% \end{eqnarray}
% The computation of gradient requires the derivative of ${\cal L}$ with respect to the metric matrix ${\Lb}$, $\frac{\partial {\cal L}}{\partial L}$. Note that not only the kernel function $\Kb$ is a function of ${\Lb}$, but also $\alpha^0$, $b^0$ depend implicitly on ${\Lb}$, because $\alpha^0$ and $b^0$ are defined to maximize $W$. Therefore, we apply  chain rule and product rule here. After applying the chain rule, we have:

The derivatives $\frac{\partial {h}}{\partial \alpha },\frac{\partial {h}}{\partial b},\frac{\partial {h}}{\partial \Kb },\frac{\partial \Kb}{\partial\Lb}$ are straight-forward and follow from definitions~(\ref{eq:kb}) and (\ref{eq:svm_h})~\citep{peterson2008}.
In order to compute $\frac{\partial {\alpha}}{\partial \Lb}$ and $\frac{\partial {b}}{\partial \Lb}$ , we express the vector  $(\alpha,b)$  in closed-form with respect to $\Lb$. Because we absorb slack variables through our kernel modification in~(\ref{eq:ridge}) and we use a hard-margin SVM with the modified kernel, all support vectors must lie exactly one unit from the hyperplane and satisfy 
\begin{equation}
	y_i(\sum_{j=1}^n \Kb_{ij}\alpha_jy_j + b) = 1.\label{svm:sv}
\end{equation}
Since the parameters $\alpha_j$ of non-support vectors are zero, the derivative of these $\alpha_j$ with respect to ${\Lb}$ are also all-zero and do not need to be factored into our calculation. We can therefore (with a slight abuse of notation) remove all rows and columns of $\Kb$ that do not correspond to support vectors and express ~(\ref{svm:sv}) as a matrix equality
	\[ 
	\underbrace {
	\left( \begin{array}{ccc} 
	{\bar \Kb} & {\bf y} \\
	{\bf y^\top} & 0 \\
	\end{array} \right) }_{\Hb}
	\left( \begin{array}{ccc} 
	{\bf \alpha}\\
	b\\
	\end{array} \right)
	=
	\left( \begin{array}{ccc} 
	{\bf 1}\\
	0\\
	\end{array} \right)\]
where $\bar\Kb_{ij} = y_i y_j {\Kb}(x_i,x_j)$. Consequently, we can solve for $\alpha$ and $b$ through left-multiplication with  $\Hb^{-1}$. Further, the derivative with respect to $\Lb$ can be derived from the matrix inverse rule~\citep{peterson2008}, leading to
\begin{eqnarray}
({\bf \alpha},b)^\top \!=\! \Hb^{-1} (1\cdots1,0)^\top \ 
\textrm{ and }\ \frac{\partial (\alpha, b)}{\partial \Lb_{ij}} \!=\! -\Hb^{-1}\frac{\partial \Hb}{\partial \Lb_{ij}}(\alpha,b)^\top. \label{eq:abder}
\end{eqnarray} 
%Suppose we have $n$ support vectors. After removing all non-support vectors, we have $n  \alpha$ and $b$, and thus, we have $n+1$ unknowns and $n+1$ equations. We can always derive a closed-form solution for $\alpha$ and $b$. In other words, we are always able to compute the derivative of $\alpha$ and $b$ with respect to ${\Lb}$. We will also restrict ourselves to the case where $K$ can be differentiated with respect to ${\Lb}$. As the derivative of the inverse of a matrix can be computed using a rule, we have:


\begin{figure*}[t]
	\centering
		\includegraphics[width=5.5in]{trainvaltest.pdf}
	\caption{An example of training, validation and test error on the Credit data set. As the loss ${\cal L}_V$ (left) decreases, the validation error ${\cal E}_V$ (right) follows suit (solid blue lines). For visualization purposes, we did not use a second-order function minimizer but simple gradient descent with a small step-size.}
	\label{fig:trainvaltest}
\end{figure*}

\subsection{Optimization}
Because the derivative $\frac{\partial \Hb}{\partial \Lb}$ follows directly from the definition of $\bar\Kb$ and~(\ref{eq:kb}), this completes the gradient $\frac{\partial{\cal L}_V}{\partial \Lb}$. We can now use standard gradient descent, or second order methods to minimize (\ref{eq:valloss}) up to a local minimum. 
It is important to point out that~(\ref{eq:abder}) requires the computation of the optimal $\alpha,b$, given the current matrix $\Lb$. These can be obtained with any one of the many freely available SVM packages~\citep{CC01a} by solving the SVM optimization~(\ref{eq:svm_hard}) for the kernel $\Kb$ that results from $\Lb$.  
%After having the derivative of $\frac{\partial (\alpha, b)}{\partial \Lb_{ij}}, \frac{\partial {h(\x_j)}}{\partial \Lb}$, and ultimately having $\frac{\partial{\cal L}_V}{\partial \Lb}$, we can complete the chain rule discussed above, and take gradient steps to minimize function {\cal L}
In addition, we also learn the regularization constant $C$ from eq.~(\ref{eq:ridge}) with our gradient descent optimization.  For brevity we omit the exact derivation of $\frac{\partial {\cal L}_V}{\partial C}$ but point out that it is very similar to the gradient with respect to $\Lb$, except that it is computed only from the diagonal entries of $\Kb$. 

We control the steps of gradient descent by early-stopping. We use part of the training data as a small hold-out set to monitor the algorithm's performance, and we stop the gradient descent when the validation results cease to improve. 

We refer to our algorithm as \emph{Support Vector Metric Learning} (SVML). Algorithm~\ref{table:algo} summarizes SVML in pseudo-code. Figure~\ref{fig:trainvaltest} illustrates the value of the loss function ${\cal L}_V$ as well as the training, validation and test errors.  
%In the next section, we discuss several simple heuristics to initialize the matrix $\Lb$, to avoid bad local minima. 

\begin{algorithm}[h!!!!]
\caption{SVML in pseudo-code.\label{table:algo}}
\label{algo}
\begin{algorithmic}[1]
\STATE Initialize ${\Lb}$.
\WHILE{Hold-out set result keeps improving}
\STATE Compute kernel matrix $\Kb$ from $\Lb$ as in (\ref{eq:mahala}).
\STATE Call SVM with $\Kb$ to obtain $\alpha$ and $b$. 
\STATE Compute gradient $\frac{\partial {\cal L}_V}{\partial\Lb}$ as in (\ref{eq:abder}) and perform update on $\Lb$.
\ENDWHILE
%1~\hskip 0.2in \textbf{Loop} until termination criteria is met:\\
%2~\hskip 0.4in Compute kernel matrix $\Kb$ from $\Lb$.\\
%3~\hskip 0.4in Call SVM with $\Kb$ to obtain $\alpha$ and $b$. \\
%4~\hskip 0.4in Compute gradient $\frac{\partial {\cal L}_V}{\partial\Lb}$ and perform update on $\Lb$.\\
\end{algorithmic}
\end{algorithm}


%In order to find the best metric matrix ${\Lb}$ that is neither under fitting nor over fitting, we further split our validation set into validation/validation set and validation/test set. We take gradient step to minimize the loss function on validation/validation set, and simultaneously, test on the validation/test set. As the loss and validation error keeps going down, we track the validation/test error, and record when the validation/test error reaches its minimal. Then, we retrain the metric on the whole validation set, and stop at the iteration where the previous test error is minimized. \\

\subsection{Regularization and Variations}
%Unlike the previous similar algorithms, such as feature weighting, our algorithm tweaks the whole metric ${\Lb}$ simultaneously, and it is very likely to be over fitting. 
In total, we learn $d\times d$ parameters for the matrix $\Lb$ and $n+1$ parameters for $\alpha$ and $b$. 
To avoid overfitting, we add a regularization term to the loss function, which restricts the matrix ${\Lb}$ from deviating too much from its initial estimate ${\Lb}_{0}$:
\begin{eqnarray}
\label{eq:regul}
{\cal L}_V(\Lb)=\frac{1}{|V|}\sum_{(\x,y)\in V} s_a(yh(\x))+\lambda \| \Lb - \Lb_{0} \|_F^2
\end{eqnarray}



%\bf{Structural Variations.}
Another way to avoid overfitting is to impose structural restrictions on the matrix $\Lb$. If $\Lb$ is restricted to be spherical, $\Lb=\frac{1}{\sigma}\Ib^{d\times d}$, SVML reduces to kernel width estimation. Alternatively, one can restrict $\Lb$ to be any diagonal matrix, essentially performing feature re-weighing. This can also be useful as a method for feature selection in settings with noisy features~\citep{weston2001feature}. We refer to these two settings as SVML-Sphere and SVML-Diag. Both of these special scenarios have been studied in previous work in the context of kernel parameter estimation~\citep{ayat2005automatic,Chapelle02choosingmultiple}. See section~\ref{sec_related} for a discussion on related work. 

Another interesting structural limitation is to enforce $\Lb\in{\cal R}^{r\times d}$ to be rectangular, by setting $r<d$. This can be particularly useful for data visualization. For high dimensional data, the decision boundary of support machines is often hard to conceptualize. By setting $r=2$ or $r=3$, the data is mapped into a low dimensional space and can easily be plotted.
% while maintaining relatively high classification accuracy. 

%Recall the discussion in the Modified RBF kernel section, if we set the distance metric ${\Lb}$ as an identity matrix, our algorithm will reduce back to a standard SVM with Gaussian RBF kernel. If we do not go that far, but restricting that we can only change the diagonal elements of the metric ${\Lb}$, then we are learning a diagonal metric, which models different features with different metrics. If we further restrict our algorithm to have the same value for all diagonal elements, we are learning a spherical metric, which gives all features a same distance metric. Although this has been proposed previously by Chapelle and et. al. ~\citep{Chapelle02choosingmultiple} as an algorithm to perform feature selection, our algorithm differs significantly in the goal, as we are always learning distance metrics.

\subsection{Implementation} 
The gradient, as described in this section, can be computed very efficiently. We use a simple $C/Mex$ implementation with Matlab. As our SVM solver, we use the open-source Newton-Raphson implementation from Olivier Chapelle\footnote{Available at http://olivier.chapelle.cc/primal/.}. As function minimizer we use an  open-source implementation of conjugate gradient descent\footnote{Courtesy of Carl Edward Rasmussen, available from \url{http://www.gatsby.ucl.ac.uk/~edward/code/minimize/minimize.m}}. Profiling of our code reveals that over 95\% of the gradient computation time was spent calling the SVM solver. For a large-scale implementation, one could use special purpose SVM solvers that are optimized for speed~\citep{bottou2007large,joachims1999making}. Also, the only computationally intensive parts of the gradient outside of the SVM calls are all trivially parallelizable and could be computed on multiple cores or graphics cards. However, as it is besides the point of this paper, we do not focus on further scalability. 
%However, since our data sets only contain up to $n=19020$ data points, we do not scale-up our implementation any further.



related.tex
Multiple publications introduce methods to learn Mahalanobis metrics. Previous work has focussed primarily on Mahalanobis metrics for $k$-nearest neighbor classifiers~\citep{Davis07itml,Globerson06,Goldberger05,Shental02,Shalev-Shwartz04,Weinberger06distancemetric} and clustering~\citep{Davis07itml,Shalev-Shwartz04,Shental02,Xing02}. None of these algorithms is specifically geared towards SVM classification. A detailed discussion of NCA, ITML and LMNN is provided in Section~\ref{sec_metric}. 
%Compared with these publications, SVML is probably  most similar to neighborhood component analysis (NCA)~\citep{Goldberger05}, which uses a soft-neighborhood assignment to mimic the nearest neighbor classification rule. NCA also minimizes a non-convex loss function with local radial basis functions, but in contrast to our algorithm, it does not incorporate the SVM parameters and has a different objective. 

%LMNN  models the problem as learning a metric to maximize the margin between different classes, and focus on kNN classification. It has the advantage of intrinsic muti-class ability, but also suffers from the high variance problem inherited from kNN, especially when the data size is small. NCA ~\citep{Goldberger05} learns a metric by constraining distances between same class examples to be zero while maximizing those between different classes. ???their problems??? ITML ~\citep{Davis07itml} ???I haven't read the paper yet??? Say sth about these algo require cross-validation to find $C$???\\

Another related line of work focusses on learning of the kernel matrix. The most common approach is to find convex combinations of already existing kernel matrices~\citep{bach2004multiple,lanckriet2004learning} or kernel learning through semi-definite programming~\citep{graepel2002kernel,ong2005learning}. 
The most similar area of related work is the field of kernel parameter estimation~\citep{ayat2005automatic,Chapelle02choosingmultiple,cherkassky2004practical,friedrichs2005evolutionary}. In particular, ~\citep{friedrichs2005evolutionary} can be viewed as learning a Mahalanobis metric for the Gaussian kernel --  however, instead of minimizing a soft surrogate of the validation error with gradient descent, the authors use genetic programming to maximize the ``fittness'' of the kernel parameters. The method of \citep{Chapelle02choosingmultiple} uses gradient descent to learn the $\sigma$ parameter of the RBF kernel matrix. SVML was highly inspired by this work. The main difference between our work and~\citep{Chapelle02choosingmultiple} is  that SVML learns the full matrix $\Lb$, and therefore a Mahalanobis metric, whereas Chapelle et al. only learn the parameter $\sigma$ or individual weights for blocks of features. Spherical and diagonal SVML can be viewed as a version of~\citep{Chapelle02choosingmultiple}. Similarly,~\citep{ayat2005automatic,schittkowski2005optimal} also explore feature re-weighting for support vector machines with alternative loss functions. 


results.tex
To evaluate SVML, we revisit the nine data sets from Section~\ref{sec:results_metric}. For convenience, Table~\ref{results:small} restates all relevant data statistics and also includes classification accuracies for all metric learning algorithms. SVML is naturally slower than SVM with Euclidean distance but requires no cross validation for any meta parameters. For better comparison, we also include results for 1-fold and 5-fold cross validation for all other algorithms.  In both cases, the meta parameters $\sigma^2,C$ were selected from five candidates each -- resulting in 25 or 125 SVM executions. The kernel width $\sigma^2$ is selected from within the set $\{4d, 2d,d,\frac{d}{2}, \frac{d}{4}\}$ and the meta parameter $C$ was chosen from within $\{0.1,1,10,100\}$. 
As SVML is not particularly sensitive to the exact choice of $\lambda$ -- the regularization parameter in (\ref{eq:regul}) -- we set it to $100$ for the smaller data sets ($n<1000$) and to $10$ for the larger ones  (\texttt{Page}, \texttt{Gamma}). We terminate our algorithm based on a small hold-out set.



% \textbf{Initialization}
% The function ${\cal L}_V$ is not convex. Thus standard gradient descent methods are not guaranteed to be successful at finding a global minimum. To avoid landing at a bad local minimal, initialized LSVM with the Euclidean setting $\Lb=\frac{1}{\sigma}\Ib$. We evaluated two methods to find $\sigma$: As our first approach, we split the training half of the data into an additional train/val splits and picked the value for $\sigma$ that yielded the best classification results before tuning with SVML. 
% As a second approach we fixed $\sigma$ to the number of features in the data set, which was the default setting of our SVM package\footnote{We used the open-source implementation from http://olivier.chapelle.cc/primal/.}. Talbe~\ref{table:init} shows compares the two initialization methods on eight of the 12 data sets. As the heuristic seems to clearly outperform cross validation, 

% \begin{table}[htbp]
%     \tabcolsep 0.8pt
%     \small
% \center
%     \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
%     \hline & {\bf Haberman}  & {\bf Credit} & {\bf Finger} & {\bf Aus Credit} & {\bf Tranfusion} & {\bf Diabetes} & {\bf Mammo} & {\bf CMC}\\[3pt]
%     \hline \# of features &  27.74 & {\bf 13.53} & {\bf 16.49} & {\bf 14.2} & {\bf 20.11} & {\bf 23.41} & {\bf 25.73} & {\bf 18.06}\\
%     \hline Cross Validation &  {\bf 26.18} & 13.95 & 14.49 & 14.83 & 20.82 & {\bf 23.45} & 26.31 & {\bf 16.62}\\ 
%     \hline   
%     \end{tabular}
% \caption{Results of different initialization 1}
% \label{table:init}
% \end{table}

\begin{table*}[ht]
    \tabcolsep 1.8pt
    \small
	\center	
\center
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|}
\hline {\bf Statistics} & {\bf Haber}  & {\bf Credit} & {\bf ACredit} & {\bf Trans} & {\bf Diabts} & {\bf Mammo} & {\bf CMC} & {\bf Page} & {\bf Gamma} \\
\hline
%\hline \#inputs &  306 & 690 & 685 & 690 & 749 & 768 & 961 & 1743\\
\hline \#examples & 306 &  653 & 690 & 748 & 768 & 830 & 962 & 5743 & 19020 \\
%\hline \#binary method \\
\hline \#features &  3 & 15 & 14 & 4 & 8 & 5 & 9 & 10 & 11\\
\hline \#training exam. &   245 & 522 & 552 &  599 & 614 & 664 & 770 & 4594 & 15216\\
\hline \#testing  exam. & 61 & 131 & 138 & 150 & 154 & 166 & 192  & 1149 & 3804  \\
\hline
%\hline train/test splits &  80/20 & 80/20 & 80/20 & 80/20 & 80/20 & 80/20 & 80/20\\
%\hline  \multicolumn{9}{|c|}{} \\
\hline {\bf Metric}  & \multicolumn{9}{|c|}{\bf Error Rates} \\ 
\hline Euclidean 1-fold & 27.16 & 13.16 & 14.36 & 21.05 & 23.84 & 18.43 & 27.12 & {\bf 2.61} & 12.70 \\
\hline Euclidean 3-fold & 27.40 & 13.10 & 14.13 & 20.58 & 23.39 & 18.27 & 26.77 & {\bf 2.55} & 12.68 \\
\hline Euclidean 5-fold & 27.37 & 13.12 & 14.11 & 20.54 & 23.46 & 18.17 & 26.91 & {\bf 2.56} & {\bf 12.62} \\
\hline ITML + SVM 1-fold & 26.57 & 13.78 & 14.15 & 23.01 & 23.19 & 19.14 & 28.65 & 4.82 & 22.63 \\
\hline ITML + SVM 3-fold & {\bf 26.13} & 13.58 & {\bf 13.88} & 22.98 & 23.17 & 17.98 & 27.68 & 4.77 & 21.50 \\
\hline ITML + SVM 5-fold & 26.50 & 13.68 & 14.71 & 22.86 & 23.14 & 18.20 & 27.67 & 4.78 & 21.50 \\
\hline NCA + SVM 1-fold & 26.44 & 13.74 & 14.14 & 22.89 & {\bf 22.84} & 17.76 & 27.47 & 4.73  & N/A\\
\hline NCA + SVM 3-fold & 26.47 & 13.45 & 14.00 & 22.67 & {\bf 22.72} & 18.12 & 26.60 & 4.73  & N/A\\
\hline NCA + SVM 5-fold & 26.39 & 13.48 & 14.10 & 22.59 & {\bf 22.74} & 18.17 & {\bf 26.53} & 4.74 & N/A \\
\hline LMNN + SVM 1-fold & {\bf 26.38} & 13.11 & 13.97 & 21.02 & 22.97 & 17.84 & 26.80 & 2.85 & 13.04 \\
\hline LMNN + SVM 3-fold & 26.44 & 13.30 & {\bf 13.93} & 20.73 & {\bf 22.86} & {\bf 17.57} & 26.66 & 2.81 & 12.79 \\
\hline LMNN + SVM 5-fold & 26.70 & 13.48 & {\bf 13.89} & 20.81 & {\bf 22.89} & 17.78 & 26.68 & {\bf 2.66} & 13.04 \\
\hline SVML-Sphere & 27.42 & 13.43 & {\bf 13.78} & {\bf 20.26} & 23.24 & 17.81 & 28.23 & 3.61 & 12.70 \\
\hline SVML-Diag & 28.15 & 13.33 & 15.11 & 20.46 & 24.14 & {\bf 17.35} & 29.51 & 2.92 & {\bf 12.54} \\
\hline SVML & {\bf 25.99} & {\bf 12.83} & {\bf 13.92} & 20.89 & 23.25 & {\bf 17.57} & {\bf 26.34} & 3.41 & {\bf 12.54} \\
%\hline SVML Full Matrix + CV &  {\bf 26.18} & 13.95 & 14.49 & 14.83 & 20.82 & {\bf 23.45} & 26.31 & {\bf 16.62}\\
\hline
\end{tabular}
\caption{Statistics and error rates for all data sets. The data sets are sorted by smallest to largest from left to right. The table shows statistics of data sets and error rates of SVML and comparison algorithms. The best results (up to a 5\% confidence interval) are highlighted in bold.\label{results:small}}
\end{table*}


% \begin{table*}[ht]
%     \tabcolsep 3.8pt
%     \small
% 	\center	
% \center
% \begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|c|}
% \hline {\bf Statistics} & {\bf Haber}  & {\bf Credit} & {\bf ACredit} & {\bf Trans} & {\bf Diabts} & {\bf Mammo} & {\bf CMC} &{\bf Spam}  & {\bf Page} & {\bf Gamma} \\
% \hline
% %\hline train/test splits &  80/20 & 80/20 & 80/20 & 80/20 & 80/20 & 80/20 & 80/20\\
% %\hline  \multicolumn{9}{|c|}{} \\
% \hline {\bf Metric}  & \multicolumn{10}{|c|}{\bf Average running time in seconds} \\ 
% \hline Euclidean (CV) & 5 & {\bf 17} & {\bf 4} & 25 & 25 & 32 & 39 &  &  & \\
% \hline ITML + SVM & 13 &	42 &	14 &	42 & 46 &	52 & 68 & & &\\
% \hline NCA + SVM & 13 & 43 & 17 & 42 & 46 & 64 & 82 & & & \\
% \hline LMNN + SVM &  8 & 40 & 12 &	54 &	57 &	69 &	96 &  & & \\
% \hline SVML  & {\bf 3} & 22 & 6 & {\bf 14} & {\bf 21} & {\bf 18} & {\bf 34} & & & \\ 
% % \hline {\bf Algorithm}  & \multicolumn{10}{|c|}{\bf Average running time in seconds} \\ 
% % \hline Euclidean & 5.12 & {\bf 16.90} & {\bf 4.38} & 24.53 & 25.45 & 31.93 & 39.06 &  &  & \\
% % \hline ITML + SVM & 12.60 &	41.93 &	14.29 &	42.14 & 46.01 &	51.76 & 68.24 & & &\\
% % \hline NCA + SVM & 13.06 & 42.79 & 17.33 & 41.65 & 45.96 & 64.10 & 82.15 & & & \\
% % \hline LMNN + SVM &  7.60 & 39.69 & 11.79 &	53.74 &	57.34 &	69.13 &	95.93 &  & & \\
% % \hline SVML  & {\bf 3.31} & 21.73 & 5.64 & {\bf 13.66} & {\bf 20.76} & {\bf 18.21} & {\bf 34.49} & & & \\ 
% %\hline SVML Full Matrix + CV &  {\bf 26.18} & 13.95 & 14.49 & 14.83 & 20.82 & {\bf 23.45} & 26.31 & {\bf 16.62}\\
% \hline
% \end{tabular}
% \caption{Training time in seconds. This includes training the metric, the SVM and performing cross-validation for parameter tuning where applicable (e.g. for Euclidean metric).  \label{results:timing}}
% \end{table*}

%\begin{table}[h]
%    \tabcolsep 5.8pt
%    \small
%	\center	
%\begin{tabular}{|l|c|c|c|c|}
%\hline {\bf statistics} & {\bf Spam}  & {\bf Pageblocks} & {\bf KingRook} & {\bf GammaTel}  \\
%\hline
%%\hline \#inputs &  4601 & 5743 & 28056 & 19020 & 48842\\
%\hline \#examples & 4601 & 5743 & 8747 & 19020 \\
%%\hline \#binary method &  & & & & \\
%\hline \#features &  57 &  10 & 6 & 11  \\
%\hline \#training examples & 3681 & 4594 & 6998 & 15216\\
%\hline \#testing examples &  920 & 1149 & 1749 & 3804  \\
%%\hline train/test splits & 80/20 & 80/20 & 80/20 & 80/20 & pre-set  \\
%%\hline  \multicolumn{6}{|c|}{} \\
%\hline {\bf Algorithm}  & \multicolumn{4}{|c|}{} \\ 
%\hline Cross Validation & &  {\bf 2.68} &  & 13.64\\
%\hline LMNN + SVM &  & & & 13.80  \\ 
%\hline NCA + SVM &  & 13.99 &  & 15.33  \\
%\hline ITML + SVM &  & 12.96  &  &   \\
%\hline SVML-Sphere & & 3.02 & &13.70 \\
%\hline SVML-Diag & & {\bf 2.83} &  & {\bf 13.07} \\
%\hline SVML & & {\bf 2.65} &  & {\bf 12.91}  \\
%%\hline SVML Full Matrix + CV &  & {\bf 2.84} &  & {\bf 13.30} & \\
%\hline
%\end{tabular}
%\caption{Results and statistics on medium and large data sets.\label{results:big}}
%\end{table}

%\subsection*{Data set description.}
As in Section~\ref{results:small}, experimental results are obtained by averaging over multiple runs on randomly generated 80/20 splits of each data set. For small data sets, we average 200 splits, 20 for medium size, and 1 for the large data set Gamma (where train/test splits are pre-defined). For the SVML training, we further apply a 50/50 split for training and validation within the training set, and another 50/50 split on the validation set for early stopping. The result from SVML appeared fairly insensitive to these splits.

%\subsection*{Classification Results.} 
%We begin by reporting the comparison of SVML with other methods, and then discuss the general trends. We compare our results to SVM with the RBF kernel under multiple metrics. The baseline is the Euclidean distance, which is regular SVM without any metric learning. We use the same settings as our SVML. The training data are split into training and validation in a 50-50 ratio, and only validate once. 

%As for competing metric learning algorithms, we use ITML~\citep{Davis07itml}, NCA\footnote{Our NCA implementation did not scale to the largest data set. }~\citep{Goldberger05} and LMNN~\citep{Weinberger06distancemetric}. 
%For all metrics except SVML, we re-scale the distances with an additional parameter $\frac{1}{\sigma}$, which is tuned by cross validation (same fashion as the Euclidean distance, described above). This is important because  NCA, LMNN and ITML are originally intended for $k$-nearest neighbor classification, whose classification rule is scale invariant. 
%To further improve the classification results of competing metric learning algorithm and the baseline, we also perform much finer cross validation: We split the training in 80/20 as training and validation, and use 5-fold cross validation to select $\sigma$ and $C$. The results are summarized in Table~\ref{results:small}. The best results (up to a 5\% confidence interval) are highlighted in bold. 

As a general trend, SVML with a full matrix obtains the best results (up to significance) on $6$ out of the $9$ data sets. It is the only metric that consistently outperforms Euclidean distances. The diagonal version SVML-Diag and SVML-Sphere both obtain best results in $2$ out of $9$ and are not better than the uninformed Euclidean distance with 5-fold cross validation. None of the kNN metric learning algorithms perform comparably. 

In general, we found the time required for SVML training to be roughly between 3-fold and 5-fold cross validation for Euclidean metrics, usually outperforming LMNN, ITML and NCA. Figure~\ref{fig:time} provides running-time details on all data sets. We consider the small additional time required for SVML over Euclidean distances with cross validation as highly encouraging. 
%This makes SVML a competitive algorithm for supervised metric learning for SVM classification. 

% The metric learning algorithms that are originally designed for $k$-nearest neighbor classification tend to be sub-optimal choices for SVMs with the RBF kernel. 

%SVML obtained lower error rates than all kNN metrics with one noteworthy exception of LMNN on pageblocks. 
%LMNN and NCA obtain $3/9$ and $2/9$ best results respectively, but are significantly more demanding in terms of computation time. In summary, SVML obtains the lowest classification results more often than any other metric. 
% We would also like to point out that the SVML training involved around 5-10 times fewer calls of the SVM algorithm than the cross-validation that was performed for all other methods. 
%Across the various data sets, SVML requires about three times the computation time compared to $1-$fold, but is significantly faster than $5-$fold cross validation. 
%since the SVML training involved fewer calls of the SVM algorithm than 5-fold cross-validation, it needs only $50\%$ to $70\%$ computation time of 5-fold cross-validation, and $5\%$ to $10\%$ of 5-fold cross-validation plus LMNN/NCA/ITML training. 
% \textbf{Computation Time.} In addition to the classifier accuracy, we also measured the time required to train the metric and the SVM classifier. Table~\ref{results:timing} summarizes the times for the various algorithms across the different data sets. As a general trend, SVML is the fastest algorithm on all but two (very small) data sets. \textbf{\fix{VERIFY!}}

%obtained one of the lowest error rates in comparison to other metrics (although it was sometimes out-performed by its own diagonal and spherical variations). 

%If the results of two algorithm are not significantly different, we treat these two algorithms as having equally good performance. We took SVM with cross-validation as a representation of the state-of-the-art, and also because cross-validation is a common approach to improve the classification performance of SVM. On each data set, we trained SVM using RBF kernel and chose the best kernel parameters $\sigma$ and $C$ with cross-validation.

%The results of SVML with full metric $\Lb$are always equally good as the best results, and the results of SVML with diagonal metric $\Lb$ are equally good as the best results on the larger data sets. This could explained by the different regularization settings. In the diagonal version, we set the regularization penalty much smaller than the full metric $\Lb$ version, as it has less parameters and will less likely to over fit. Therefore, when the size of data sets is small, the ratio of of parameters to examples is small, and the SVML diagonal version will be over fitting. The spherical version is further less powerful than the diagonal version, (hard to explain its trend...). The results of the standard SVM with cross-validation are close to SVML. However, it is not stable. It performed equally good as SVML on some data sets and worse on others. Moreover, using cross-validation requires users to understand this technique, whereas our algorithm models this technique, learns and applies it automatically. 
\begin{figure}[t]
	\centering
		\includegraphics[width=\textwidth]{timing.pdf}
	\caption{Timing results on all data sets. The timing includes metric learning, SVM training and cross validation. The computational resources for SVML training are roughly comparable with 3-5 fold cross validation with a Euclidean metric. (NCA did not scale to the Gamma data set.)  }
	\label{fig:time}
\end{figure}

\subsection{Dimensionality Reduction.} In addition to better classification results, SVML can also be used to map data into a low dimensional space while learning the SVM, allowing effective visualizations of SVM decision boundaries even for high dimensional data. To evaluate the capabilities of our algorithm for dimensionality reduction and visualization, we restrict $\Lb$ to be rectangular. Specifically, a mapping into a $r=2$ or $r=3$ dimensional space. 
As comparison, we use PCA to reduce the dimensionality before the SVM training without SVML (all meta parameters were set by cross-validation). Figure~\ref{fig:pca_svca} shows the visualization of the support vectors of the Credit data set after a mapping into a two dimensional space with SVML and PCA. The background is colored by the prediction function $h(\cdot)$.  % Not only does SVML obtain a much lower classification error of $29.56\%$ compared to $34.88\%$ with PCA, 
The $2D$ visualization shows a much more interpretable decision boundary. (Visualizations of the LMNN and NCA mappings were very similar to those of PCA.) Visualizing the support vectors and the decision boundaries of kernelized SVMs can help demystify hyperplanes in reproducing kernel Hilbert spaces and might help with data analysis.

\begin{figure}[t]
	\centering
		\includegraphics[width=2.5in]{pca}
		\includegraphics[width=2.5in]{svca}
	\caption{$2D$ visualization of the Credit data set. The figure shows the decision surface and support vectors generated by SVML ($\Lb\in{\cal R}^{2\times d}$) and standard SVM after projection onto the two leading principal components. }
	\label{fig:pca_svca}
\end{figure}


setting.tex
	%In this section, we discuss the notation in our paper and some background on the Mahalanobis metric learning, support vector machine and RBF kernel. 
%\subsection{Mahalanobis Metric Learning.}
It is natural to ask if the SVM classification rule can be improved with better adjusted metrics than the Euclidean distance. 
A commonly used generalization of the Euclidean metric is the Mahalanobis metric~\citep{mahalanobis1936generalized}, defined as 
\begin{equation}
	d_{\Mb}(\x_i,\x_j)=\sqrt{(\x_i-\x_j)^\top \Mb (\x_i-\x_j)},\label{eq:mahala}
\end{equation}
for some matrix $\Mb\in{\cal R}^{d\times d}$. The matrix $\Mb$ must be semi-positive definite ($\Mb\succeq 0$), which is equivalent to requiring that it can be decomposed into $\Mb=\Lb^\top\Lb$, for some matrix $\Lb\in{\cal R}^{r\times d}$. 
If $\Mb=\Ib^{d\times d}$, where $\Ib^{d\times d}$ refers to the identity matrix in ${\cal R}^{d\times d}$,  (\ref{eq:mahala}) reduces to the Euclidean metric. Otherwise, it is equivalent to the Euclidean distance after the transformation $\x_i\rightarrow \Lb\x_i$. 
Technically, if $\Mb=\Lb^\top \Lb$ is a singular matrix, the corresponding Mahalanobis distance is a  \emph{pseudo-metric}\footnote{A pseudo-metric is not require to preserve identity, i.e. $d(\x_i,\x_j)=0\ \iff \x_i=\x_j$. }. Because the distinction between pseudo-metric and metric is unimportant for this work, we refer to both as \emph{metrics}. As the distance in~(\ref{eq:mahala}) can equally be parameterized by $\Lb$ and $\Mb$ we use $d_{\Mb}$ and $d_{\Lb}$ interchangeably. 

In the following section, we will introduce several approaches that focus on Mahalanobis metric learning for $k$-nearest neighbor classification.\\

\subsection{Neighborhood component analysis}
\cite{Goldberger05} propose 
%a Mahalanobis metric learning algorithm specifically for kNN classification. The 
%an algorithm which is known as 
Neighborhood Component Analysis (NCA), which minimizes the expected leave-one-out classification error under a probabilistic neighborhood assignment. 
For each data point or query, the neighbors are drawn from a softmax probability distribution. The probability of sampling $\x_j$ as a neighbor of $\x_i$ is given by:
\begin{equation}
	p_{ij} = \left \{
	\begin{array}{c c}
		\frac{e^{-d^2_{\Lb}(\x_i,\x_j)}}{\sum_{k\neq i}e^{-d^2_{\Lb}(\x_i,\x_k)}} & \textrm{if}\hspace{4pt} i\neq j \\
		0 & \textrm{if} \hspace{4pt} i=j \\
	\end{array}	\right.	~\label{eq:sample}
\end{equation}
% In contrast to regular kNN settings, NCA is different in two ways. Firstly, the distance metric is parameterized by the linear transformation $\x_i\rightarrow \Lb\x_i$, and the goal is to find an optimal transformation matrix $\Lb$ to minimize the classification error. 
Let us define an indicator variable $y_{ij}\in\{0,1\}$ where $y_{ij}=1$ if and only if $y_i=y_j$. 
With the probability assignment described in (\ref{eq:sample}), we can easily compute the expectation of the leave-one-out classification \emph{accuracy} as
\begin{equation}
	A_{loo} = \frac{1}{n}\displaystyle \sum_{i=1}^n \sum_{j=1}^n p_{ij}y_{ij}. \label{eq:expectnca}
\end{equation} 
NCA uses gradient ascent to maximize~(\ref{eq:expectnca}). 
The advantage of the probabilistic framework over regular kNN is that (\ref{eq:expectnca}) is a continuous, differentiable function with respect to the linear transformation $\Lb$. 
%, and therefore we can use gradient descent to minimize the error. 
By contrast, the leave-one-out error of regular kNN is not continuous or differentiable. 
The two down-sides of NCA are its relatively high computational complexity and non-convexity of the objective. 
%One downside of NCA is that its objective (\ref{eq:expectnca}) is not convex and the optimization consequently suffers from spurious local minima. 
% sensitive to the choice of initialization. If not initialized properly, it will suffer from the local minimal. 


\subsection{Large Margin Nearest Neighbor Classification}
Large Margin Nearest Neighbor (LMNN), proposed by~\cite{Weinberger06distancemetric}, also mimics the leave-one-out error of kNN. Unlike NCA, LMNN employs a convex loss function, and encourages local neighborhoods to have the same labels by pushing data points with different labels away and pulling those with similar labels closer. The authors introduce the concept of \emph{target neighbors}. A target neighbor of a training datum $\x_i$ are data points in the training set that \emph{should ideally be} the nearest neighbors (e.g. the closest points under the Euclidean metric with the same class label). LMNN moves these points closer by minimizing 
\begin{equation}
	\sum_{j\leadsto i} d_{\Mb}(\x_i,\x_j),\label{eq:lmnnobj}
\end{equation}
where $j\leadsto i$ indicates that $\x_j$ is a target neighbor of $\x_i$. 
In addition to the objective~(\ref{eq:lmnnobj}), LMNN also enforces that no datum with a different label can be closer than a target neighbor. In particular, let $\x_i$ be a training point and $\x_j$ one of its target neighbors. Any point $\x_k$ of \emph{different class membership} than $\x_i$ should be further away than $\x_j$ by a large margin. LMNN encodes this relationship as linear constraints with respect to $\Mb$. 
%For each data point $\x_i$, the algorithm picks $k$ target neighbors $\x_j$ within the same class, and learns a metric that clusters target neighbors closer than those different labeled neighbors by a large margin. This objective can be expressed by:
\begin{equation}
d^2_{\Mb}(\x_i,\x_k)  \ge d^2_{\Mb}(\x_i,\x_j)+1 \label{eq:largemargin}
\end{equation}
%Where $\x_i$ is an input, $\x_j$ are the target neighbors, and $\x_k$ are neighbors of different labels. Since the metric is learned from each local neighborhood, an advantage of LMNN is that it optimizes a global metric locally.
%
%In addition to enforcing the constraints of type~(\ref{eq:largemargin}), LMNN also moves all target neighb
LMNN uses semidefinite programming to minimize~(\ref{eq:lmnnobj}) with respect to~(\ref{eq:largemargin}). 
 % $\sum_{j\leadsto i} d^2_{\Lb}(\x_i,\x_j)$ and penalize violations of the constraint in equation (\ref{eq:largemargin}), where $ j\leadsto i$ indicates that $\x_j$ is a target neighbor of $\x_i$. 
To account for the natural limitations of a single linear transformation the authors introduce slack variables. More explicitly, for each triple  $(i,j,k)$, where $\x_j$ is a target neighbor of $\x_i$ and $y_k\neq y_i$, they introduce $\xi_{ijk}\geq 0$  which absorbs small violations of the constraint~(\ref{eq:largemargin}). The resulting optimization problem can be formulated as the following semi-definite program (SDP)~\citep{BoyVan04}:
\begin{center}
\fbox{\parbox{0.50\textwidth}{
\vspace{1ex}
\hspace{1ex}\begin{tabular}{l}	
	$ \displaystyle \min_{\Mb\succeq 0} \displaystyle \sum_{j\leadsto i} d^2_{\Mb}(\x_i,\x_j) + \mu\!\! \displaystyle \sum_{j\leadsto i,k:y_k\neq y_i} \!\!\xi_{ijk} $\\
	\textbf{subject to}: \\
	\hspace{2ex}$(1) \hspace{4pt} d^2_{\Mb}(\x_i,\x_k) - d^2_{\Mb}(\x_i,\x_j) \ge 1 - \xi_{ijk}$\\
	\hspace{2ex}$(2) \hspace{4pt} \xi_{ijk} \ge 0$ \\
%	\hspace{2ex}$(3) \hspace{4pt} \Mb \succeq 0 $\\
\end{tabular}
\vspace{1ex}
}}
\end{center}
Here $\mu\geq 0$ defines the trade-off between minimizing the objective and penalizing constraint violations (by default we set $\mu=1$). 

\subsection{Information-Theoretic Metric Learning}
Different from NCA and LMNN, Information-Theoretic Metric Learning (ITML), proposed by~\cite{Davis07itml}, does not minimize the leave-one-out error of kNN classification. In contrast, ITML assumes a uni-modal data-distribution and clusters similarly labeled inputs close together while regularizing the learned metric to be close to some pre-defined initial metric in terms of Gaussian cross entropy (for details see~\cite{Davis07itml}). 
Similar to LMNN, ITML also incorporates the similarity and dissimilarity as constraints in its optimization. Specifically, ITML enforces that similarly labeled inputs must have a distance smaller than a given upper bound $d_{\Mb}(\x_i,\x_j) \le u$ and dissimilarly labeled points must be further apart than a pre-defined lower bound $d_{\Mb}(\x_i,\x_j) \ge l$. 
If we denote the set of similarly labeled input pairs as $S$, and  dissimilar pairs as $D$, the optimization problem of ITML is:
\begin{center}
\fbox{
\hspace{1ex}\parbox{0.45\textwidth}{
\vspace{1ex}
\begin{tabular}{l}
	$\displaystyle \min_{\Mb\succeq 0}  \textrm{tr}(\Mb\Mb_0^{-1})-\log\det(\Mb\Mb_0^{-1})$  \\
	\textbf{subject to:}\\
	 \hspace{2ex} $(1)\  d^2_{\Mb}(\x_i,\x_j) \le u  \hspace{2ex} \forall (i,j)\in S,$ \\
	 \hspace{2ex} $(2)\  d^2_{\Mb}(\x_i,\x_j) \ge l \hspace{2.5ex} \forall (i,j)\in D.$\\
% 	\displaystyle \min_{\Mb\succeq 0} & \textrm{tr}(\Mb\Mb_0^{-1})-\log\det(\Mb\Mb_0^{-1}) & \\
% 	\textrm{ subject to : } &  d^2_{\Mb}(\x_i,\x_j) \le u  \hspace{2ex} \forall (i,j)\in S, &\\
% 	& d^2_{\Mb}(\x_i,\x_j) \ge l \hspace{2.5ex} \forall (i,j)\in D.&
% \end{array}
\end{tabular}
\vspace{1ex}
}}
\end{center}
\cite{Davis07itml} introduce several variations, including the incorporation of slack-variables. One advantage of the particular formulation of the  ITML optimization problem is that the SDP constraint $\Mb\succeq 0$ does not have to be monitored explicitly through eigenvector decompositions but is enforced implicitly through the objective. 



\begin{table*}[ht]
    \tabcolsep 1.8pt
    \small
	\center	
\center
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|}
\hline {\bf Statistics} & {\bf Haber}  & {\bf Credit} & {\bf ACredit} & {\bf Trans} & {\bf Diabts} & {\bf Mammo} & {\bf CMC} & {\bf Page} & {\bf Gamma} \\
\hline
%\hline \#inputs &  306 & 690 & 685 & 690 & 749 & 768 & 961 & 1743\\
\hline \#examples & 306 &  653 & 690 & 748 & 768 & 830 & 962 & 5743 & 19020 \\
%\hline \#binary method \\
\hline \#features &  3 & 15 & 14 & 4 & 8 & 5 & 9 & 10 & 11\\
\hline \#training exam. &   245 & 522 & 552 &  599 & 614 & 664 & 770 & 4594 & 15216\\
\hline \#testing  exam. & 61 & 131 & 138 & 150 & 154 & 166 & 192  & 1149 & 3804  \\
\hline
%\hline train/test splits &  80/20 & 80/20 & 80/20 & 80/20 & 80/20 & 80/20 & 80/20\\
%\hline  \multicolumn{9}{|c|}{} \\
\hline {\bf Metric}  & \multicolumn{9}{|c|}{\bf Error Rates} \\ 
\hline Euclidean   & 27.37 & {\bf 13.12} & {\bf 14.11} & {\bf 20.54} & 23.46 & 18.17 & 26.91 & {\bf 2.56} & {\bf 12.62} \\
\hline ITML & {\bf 26.50} & 13.68 & 14.71 & 22.86 & 23.14 & 18.20 & 27.67 & 4.78 & 21.50 \\
\hline NCA  & {\bf 26.39} & 13.48 & {\bf 14.10} & 22.59 & {\bf 22.74} & 18.17 & {\bf 26.53} & 4.74 & N/A \\
\hline LMNN   & {\bf 26.70} & 13.48 & {\bf 13.89} & 20.81 & {\bf 22.89} & {\bf 17.78} & {\bf 26.68} & {\bf 2.66} & 13.04 \\
\hline
\end{tabular}
\caption{Error rates of SVM classification with an RBF kernel (all parameters were set by 5-fold cross validation) under various learned metrics.\label{results:metric}}
\end{table*}


\subsection{Metric Learning for SVM}

\label{sec:results_metric}
We evaluate the efficacy of NCA, ITML and LMNN as pre-processing step for SVM classification with an RBF kernel. We used nine data sets from the UCI Machine Learning repository~\citep{Frank+Asuncion:2010} of varying size, dimensionality and task description. The data sets are: Haberman's Survival (Haber), Credit Approval (Credit), Australian Credit Approval (ACredit), Blood Transfusion Service (Trans), Diabetes (Diabts), Mammographic Mass (Mammo), Contraceptive Method Choice (CMC), Page Blocks Classification (Page) and MAGIC Gamma Telescope (Gamma). 
%Table~\ref{results:metric} summarizes data set statistics and classification error rates. All SVM parameters ($C$ and $\sigma$) were chosen by 5-fold cross validation. NCA and ITML were initialized with the identity matrix (i.e. the Euclidean metric). 

%, although SVML can also be used in multi-class settings (\emph{e.g.} with the one-versus all extension~\citep{rifkin2004defense}). 
For simplicity, we restrict our evaluation to the binary case and convert multi-class problems to binary ones, either by selecting the two most-difficult classes or (if those are not known) by grouping labels into two sets. Table~\ref{results:metric} details statistic and classification results on all nine data sets. The best values up to statistical significance (within a 5\% confidence interval)  are highlighted in bold. To be fair to all algorithms, we re-scale all features to have standard deviation $1$. 
%For non-convex algorithms, we experiment with various initializations for the matrix $\Lb$ on evaluation data sets. 
%As initialization of 
We follow the commonly used heuristic for Euclidean RBF\footnote{The choice of $\sigma^2=\#features$ is also the default value for the LibSVM toolbox~\citep{CC01a}.} and initialize NCA and ITML with $\Lb_0=\frac{1}{d}\Ib$ for all experiments (where $d$ denotes the $\#features$).  As LMNN is known to be very parameter insensitive, we set $\mu$ to the default value of $\mu=1$. All SVM parameters ($C$ and $\sigma^2$) were set by 5-fold cross validation on the training sets, after the metric is learned. The results on the smaller data sets $(n<1000)$ were averaged over 200 runs with random train/test splits, Page Blocks (Page) was averaged over 20 runs and Gamma was run once (here the train/test splits are pre-defined). 

In terms of scalability, NCA is by far the slowest algorithm and our implementation did not scale up to the (largest) Gamma data set. LMNN and ITML require comparable computation time (on the order of several minutes for the small- and 1-2 hours for large data sets -- for details see Section~\ref{sec_related}). As a general trend, none of the three metric learning algorithms consistently outperforms the Euclidean distance. Given the additional computation time, it is questionable if either one is a reasonable pre-processing step of SVM-RBF classification. This is in large contrast with the drastic improvements that these metric learning algorithms obtain when used as pre-processing for kNN~\citep{Goldberger05,Weinberger06distancemetric,Davis07itml}. One explanation for this discrepancy could be based on the subtle but important differences between the kNN classification rule~(\ref{eq:knn_rule}) and the one of SVMs~(\ref{eq:svm_h}). In the remainder of this paper we will explore the possibility to learn a metric explicitly for the SVM decision rule. 


svm.tex
Let the training data consist of input vectors $\left\{\x_1,\dots,\x_n\right\}\in{\cal R}^d$ with corresponding discrete class labels $\left\{y_1,\dots,y_n\right\}\in\{+1,-1\}$. Although our framework can easily be applied in a multi-class setting, for the sake of simplicity we focus on binary scenarios, restricting $y_i$ to two classes. 

There are several reasons why SVMs are particularly popular classifiers.  First, they are linear classifiers that involve a quadratic minimization problem, which is convex and guarantees perfect reproducibility. Furthermore, the maximum margin philosophy leads to reliably good generalization error rates~\citep{Vapnik98}. But perhaps most importantly, the \emph{kernel-trick}~\citep{Scholkopf02} allows SVMs to generate highly non-linear decision boundaries with low computational overhead. 
More explicitly, the kernel-trick maps the input vectors $\x_i$ implicitly into a higher (possibly infinite) dimensional feature space with a non-linear transformation $\phi:{\cal R}^d\rightarrow {\cal H}$. Training a linear classifier directly in this high dimensional feature space ${\cal H}$ would be computationally infeasible if the vectors $\phi(\x_i)$ were accessed explicitly. However, SVMs can be trained completely in terms of inner-products between input vectors. With careful selection of $\phi()$, the inner-product $\phi(\x_i)^\top\phi(\x_j)$ can be computed efficiently even if computation of the mapping $\phi()$ itself is infeasible. Let the kernel function be $k(\x_i,\x_j)=\phi(\x_i)^\top\phi(\x_j)$ and the $n\times n$ kernel matrix be $\Kb_{ij}=k(\x_i,\x_j)$. The optimization problem of SVM training can be expressed entirely in terms of the kernel matrix $\Kb$.  For the sake of brevity, we omit the derivation and refer the interested reader to one of many detailed descriptions thereof~\citep{Scholkopf02}. The resulting classification rule of a test point $\x_t$ becomes
\begin{equation}
	h(\x_t)=\textrm{sign}(\sum_{j=1}^{n}\alpha_j y_j k(\x_j,\x_t)+b),\label{eq:svm_h}
\end{equation}
where $b$ is the offset of the separating hyperplane and $\alpha_1,\dots,\alpha_n$ are the dual variables corresponding to the inputs $\x_1,\dots,\x_n$. In the case of the hard-margin SVM, the parameters $\alpha_i$ are learned with the following quadratic optimization problem %($b$ has a closed form solution in terms of $\alpha$)
\begin{eqnarray}
	&& \min_{\alpha_1,\dots,\alpha_n}\sum_{i=1}^n \alpha_i - \frac{1}{2} \displaystyle\sum_{i,j=1}^n \alpha_i \alpha_j y_i y_j 	K(x_i,x_j) \nonumber \\
	&& \textrm{ subject to : } \displaystyle\sum_{i=1}^n \alpha_i y_i = 0 \textrm{ and }  \alpha_i \geq 0.\label{eq:svm_hard}
\end{eqnarray}
The optimization problem~(\ref{eq:svm_hard}) ensures that all inputs $\x_i$ with label $y_i=-1$ are on one side of the hyperplane, and those with label $y_j=+1$ are on the other. These hard constraints might not always be feasible, or in the interest of minimizing the generalization error (\emph{e.g.} in the case of noisy data). Relaxing the constraints can be performed simply by altering the kernel matrix to
\begin{equation}
	\Kb\leftarrow \Kb+\frac{1}{C}\Ib^{n\times n}.\label{eq:ridge}
\end{equation}
Solving~(\ref{eq:svm_hard}) with a kernel matrix~(\ref{eq:ridge}) is equivalent to a squared-penalty of the violations of the separating hyperplane~\citep{cortes1995support}. This formulation requires no explicit slack variables in the optimization problem and therefore simplifies the derivations of the following sections. 



\subsection{RBF Kernel}
There are many different kernel functions that are suitable for SVMs. In fact, any function $k(\cdot,\cdot)$ is a well-defined kernel as long as it is positive semi-definite~\citep{Scholkopf02}. The Radial Basis Function (RBF)-Kernel is defined as follows:
\begin{equation}
k(\x_i,\x_j) =e^{-d^2(\x_i,\x_j)},\label{eq:rbf}
\end{equation}
where $d(\cdot,\cdot)$ is a dissimilarity measure that must ensure positive semidefiniteness of $k(\cdot,\cdot)$. The most common choice is the re-scaled squared Euclidean distance, defined as
\begin{equation}
	d^2(\x_i,\x_j)=\frac{1}{\sigma^2}(\x_i-\x_j)^\top(\x_i-\x_j),
\end{equation}
with \emph{kernel width} $\sigma\!>\!0$.
The RBF-kernel is one of the most popular kernels and yields reliable good classification results. Also, with careful selection of $C$, SVMs with RBF-kernels have been shown to be consistent classifiers~\citep{Steinwart2001}. 


\subsection{Relationship with kNN}
The $k$-nearest neighbor classification rule predicts the label of a test point $\x_t$ through a majority vote amongst its $k$ nearest neighbors. Let $\eta_{j}(\x_t)\in\{0,1\}$ be the neighborhood indicator function of a test point $\x_t$, where $\eta_j(\x_t)=1$ if and only if $\x_j$ is one of the $k$ nearest neighbors of $\x_t$. The kNN classification rule can then be expressed as 
\begin{equation}
	h(\x_t)=\textrm{sign}(\sum_{j=1}^n\eta_j(\x_t) y_j ).\label{eq:knn_rule}
\end{equation}
Superficially, the classification rule in~(\ref{eq:knn_rule}) very much resembles~(\ref{eq:svm_h}). In fact, one can interpret the SVM-RBF classification rule in (\ref{eq:svm_h}) as a \emph{``soft''}-nearest neighbor rule. Instead of the zero-one step function $\eta_j(\x_t)$, the training points are weighted  by $\alpha_jk(\x_t,\x_j)$. The classification is still local-neighborhood based, as  $k(\x_t,\x_j)$ decreases exponentially  with increasing distance $d(\x_t,\x_j)$. The SVM optimization in~(\ref{eq:svm_hard}) assigns appropriate weights $\alpha_j\geq 0$ to ensure that, on the leave-one-out training set, the majority vote is correct for all data points by a large margin. 

klearning.bbl
\begin{thebibliography}{33}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Ayat et~al.(2005)Ayat, Cheriet, and Suen]{ayat2005automatic}
N.~E. Ayat, M.~Cheriet, and C.~Y. Suen.
\newblock {Automatic model selection for the optimization of SVM kernels}.
\newblock \emph{Pattern Recognition}, 38\penalty0 (10):\penalty0 1733--1745,
  2005.

\bibitem[Bach et~al.(2004)Bach, Lanckriet, and Jordan]{bach2004multiple}
F.R. Bach, G.R.G. Lanckriet, and M.I. Jordan.
\newblock {Multiple kernel learning, conic duality, and the SMO algorithm}.
\newblock In \emph{Proceedings of the twenty-first international conference on
  Machine learning}, page~6. ACM, 2004.

\bibitem[Bottou et~al.(2007)Bottou, Chapelle, and DeCoste]{bottou2007large}
L.~Bottou, O.~Chapelle, and D.~DeCoste.
\newblock \emph{{Large-scale kernel machines}}.
\newblock MIT Press, 2007.

\bibitem[Boyd and Vandenberghe(2004)]{BoyVan04}
S.~Boyd and L.~Vandenberghe.
\newblock \emph{Convex Optimization}.
\newblock Cambridge University Press, Cambridge, England, 2004.

\bibitem[Chang and Lin(2001)]{CC01a}
C.~Chang and C.~Lin.
\newblock \emph{{LIBSVM}: a library for support vector machines}, 2001.
\newblock Software available at \url{http://www.csie.ntu.edu.tw/~cjlin/libsvm}.

\bibitem[Chapelle et~al.(2002)Chapelle, Vapnik, Bousquet, and
  Mukherjee]{Chapelle02choosingmultiple}
O.~Chapelle, V.~Vapnik, O.~Bousquet, and S.~Mukherjee.
\newblock {Choosing multiple parameters for support vector machines}.
\newblock \emph{Machine Learning}, 46\penalty0 (1):\penalty0 131--159, 2002.

\bibitem[Cherkassky and Ma(2004)]{cherkassky2004practical}
V.~Cherkassky and Y.~Ma.
\newblock {Practical selection of SVM parameters and noise estimation for SVM
  regression}.
\newblock \emph{Neural Networks}, 17\penalty0 (1):\penalty0 113--126, 2004.

\bibitem[Cortes and Vapnik(1995)]{cortes1995support}
C.~Cortes and V.~Vapnik.
\newblock {Support-vector networks}.
\newblock \emph{Machine learning}, 20\penalty0 (3):\penalty0 273--297, 1995.

\bibitem[Cover and Hart(1967)]{Cover67}
T.~Cover and P.~Hart.
\newblock Nearest neighbor pattern classification.
\newblock In \emph{IEEE Transactions in Information Theory, IT-13}, pages
  21--27, 1967.

\bibitem[Davis et~al.(2007)Davis, Kulis, Jain, Sra, and Dhillon]{Davis07itml}
J.V. Davis, B.~Kulis, P.~Jain, S.~Sra, and I.S. Dhillon.
\newblock {Information-theoretic metric learning}.
\newblock In \emph{Proceedings of the 24th international conference on Machine
  learning}, pages 209--216. ACM, 2007.

\bibitem[Frank and Asuncion(2010)]{Frank+Asuncion:2010}
A.~Frank and A.~Asuncion.
\newblock {UCI} machine learning repository, 2010.
\newblock URL \url{http://archive.ics.uci.edu/ml}.

\bibitem[Friedrichs and Igel(2005)]{friedrichs2005evolutionary}
F.~Friedrichs and C.~Igel.
\newblock {Evolutionary tuning of multiple SVM parameters}.
\newblock \emph{Neurocomputing}, 64:\penalty0 107--117, 2005.

\bibitem[Globerson and Roweis(2005)]{Globerson06}
A.~Globerson and S.~T. Roweis.
\newblock Metric learning by collapsing classes.
\newblock In \emph{Advances in Neural Information Processing Systems 18}, 2005.

\bibitem[{Goldberger} et~al.(2005){Goldberger}, {Roweis}, {Hinton}, and
  {Salakhutdinov}]{Goldberger05}
J.~{Goldberger}, S.~{Roweis}, G.~{Hinton}, and R.~{Salakhutdinov}.
\newblock Neighbourhood components analysis.
\newblock In L.~K. Saul, Y.~Weiss, and L.~Bottou, editors, \emph{Advances in
  Neural Information Processing Systems 17}, pages 513--520, Cambridge, MA,
  2005. MIT Press.

\bibitem[Graepel(2002)]{graepel2002kernel}
T.~Graepel.
\newblock {Kernel matrix completion by semidefinite programming}.
\newblock \emph{Artificial Neural Networks ICANN 2002}, pages 141--142, 2002.

\bibitem[Joachims(1998)]{joachims1999making}
T.~Joachims.
\newblock Making large-scale svm learning practical.
\newblock LS8-Report~24, Universit{\"a}t Dortmund, LS VIII-Report, 1998.

\bibitem[Kloft et~al.(2010)Kloft, Brefeld, Sonnenburg, and Zien]{kloft2010non}
M.~Kloft, U.~Brefeld, S.~Sonnenburg, and A.~Zien.
\newblock {Non-sparse regularization and efficient training with multiple
  kernels}.
\newblock \emph{Arxiv preprint arXiv:1003.0079}, 2010.

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

\bibitem[Lloid(1982)]{lloid1982least}
S.P. Lloid.
\newblock {Least squares quantization in PCM}.
\newblock \emph{Special issue on quantization of the IEEE trans. on information
  theory}, 1982.

\bibitem[Mahalanobis(1936)]{mahalanobis1936generalized}
P.C. Mahalanobis.
\newblock {On the generalized distance in statistics}.
\newblock In \emph{Proceedings of the National Institute of Science, Calcutta},
  volume~12, page~49, 1936.

\bibitem[Ong et~al.(2005)Ong, Smola, and Williamson]{ong2005learning}
C.S. Ong, A.J. Smola, and R.C. Williamson.
\newblock {Learning the kernel with hyperkernels}.
\newblock \emph{Journal of Machine Learning Research}, 6\penalty0 (07), 2005.

\bibitem[Petersen and Pedersen(2008)]{peterson2008}
K.~B. Petersen and M.~S. Pedersen.
\newblock The matrix cookbook, oct 2008.
\newblock URL \url{http://www2.imm.dtu.dk/pubdb/p.php?3274}.
\newblock Version 20081110.

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

\bibitem[Schittkowski(2005)]{schittkowski2005optimal}
K.~Schittkowski.
\newblock {Optimal parameter selection in support vector machines}.
\newblock \emph{Journal of Industrial and Management Optimization}, 1\penalty0
  (4):\penalty0 465, 2005.

\bibitem[Sch{\"o}lkopf and Smola(2002)]{Scholkopf02}
B.~Sch{\"o}lkopf and A.~J. Smola.
\newblock \emph{Learning with Kernels: Support Vector Machines, Regularization,
  Optimization, and Beyond}.
\newblock MIT Press, Cambridge, MA, 2002.

\bibitem[Shalev-Shwartz et~al.(2004)Shalev-Shwartz, Singer, and
  Ng]{Shalev-Shwartz04}
S.~Shalev-Shwartz, Y.~Singer, and A.~Y. Ng.
\newblock Online and batch learning of pseudo-metrics.
\newblock In \emph{Proceedings of the 21st International Conference on Machine
  Learning}, Banff, Canada, 2004.

\bibitem[Shental et~al.(2002)Shental, Hertz, Weinshall, and Pavel]{Shental02}
N.~Shental, T.~Hertz, D.~Weinshall, and M.~Pavel.
\newblock Adjustment learning and relevant component analysis.
\newblock In \emph{Proceedings of the Seventh European Conference on Computer
  Vision (ECCV-02)}, volume~4, pages 776--792, London, UK, 2002.
  Springer-Verlag.
\newblock ISBN 3-540-43748-7.

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

\bibitem[Steinwart(2002)]{Steinwart2001}
I.~Steinwart.
\newblock On the influence of the kernel on the consistency of support vector
  machines.
\newblock \emph{Journal of Machine Learning Research}, 2:\penalty0 67--93,
  2002.
\newblock ISSN 1532-4435.

\bibitem[Vapnik(1998)]{Vapnik98}
V.~Vapnik.
\newblock \emph{Statistical Learning Theory}.
\newblock Wiley, N.Y., 1998.

\bibitem[Weinberger et~al.(2006)Weinberger, Blitzer, and
  Saul]{Weinberger06distancemetric}
K.~Q. Weinberger, J.~C. Blitzer, and L.~K. Saul.
\newblock Distance metric learning for large margin nearest neighbor
  classification.
\newblock MIT Press, 2006.

\bibitem[Weston et~al.(2001)Weston, Mukherjee, Chapelle, Pontil, Poggio, and
  Vapnik]{weston2001feature}
J.~Weston, S.~Mukherjee, O.~Chapelle, M.~Pontil, T.~Poggio, and V.~Vapnik.
\newblock {Feature selection for SVMs}.
\newblock \emph{Advances in neural information processing systems}, pages
  668--674, 2001.

\bibitem[Xing et~al.(2002)Xing, Ng, Jordan, and Russell]{Xing02}
E.~P. Xing, A.~Y. Ng, M.~I. Jordan, and S.~Russell.
\newblock Distance metric learning, with application to clustering with
  side-information.
\newblock In T.~G. Dietterich, S.~Becker, and Z.~Ghahramani, editors,
  \emph{Advances in Neural Information Processing Systems 14}, Cambridge, MA,
  2002. MIT Press.

\end{thebibliography}
