\documentclass[twoside,11pt]{article}

\usepackage{jmlr2e}
\usepackage{epsf}
\usepackage{amsfonts}
%\usepackage{harvard}
\usepackage{amsmath}
%\usepackage{a4wide}
%\usepackage[dutch]{babel}
%\usepackage[subnum]{cases}
\usepackage{fullpage}
\usepackage{amssymb}
\usepackage{psfrag}
\usepackage{graphics}
\usepackage{epsfig}
\usepackage{url}

%\newtheorem{theorem}{Theorem}
\newcommand{\Expect}{{\bf E}}
\newcommand{\calK}{{\mathcal{K}}}
\newcommand{\ba}{\mbox{\boldmath $\alpha$}}
\newcommand{\bsigma}{\mbox{\boldmath $\sigma$}}
\newcommand{\bg}{\mbox{\boldmath $\gamma$}}
\newcommand{\bdelta}{\mbox{\boldmath $\delta$}}
\newcommand{\bnu}{\mbox{\boldmath $\nu$}}
\newcommand{\bmu}{\mbox{\boldmath $\mu$}}
\newcommand{\bxi}{\mbox{\boldmath $\xi$}}
\newcommand{\blambda}{\mbox{\boldmath $\lambda$}}
\newcommand{\sign}{\textrm{sign}}

\def\beps{{\bf \epsilon}}
\def\bW{{\bf W}}
\def\be{{\bf e}}
\def\bd{{\bf d}}
\def\bc{{\bf c}}
\def\bb{{\bf b}}
\def\bq{{\bf q}}
\def\bz{{\bf z}}
\def\bw{{\bf w}}
\def\bx{{\bf x}}
\def\br{{\bf r}}
\def\by{{\bf y}}
\def\bA{{\bf A}}
%\def\ba{{\bf \alpha}}
%\def\bsigma{{\bf \sigma}}
%\def\bg{{\bf \gamma}}
%\def\blambda{{\bf \lambda}}
%\def\bdelta{{\bf \delta}}
%\def\bnu{{\bf \nu}}
%\def\bmu{{\bf \mu}}
%\def\bxi{{\bf \xi}}
\def\bI{{\bf I}}
\def\bC{{\bf C}}
\def\bU{{\bf U}}
\def\bF{{\bf F}}
\def\bV{{\bf V}}
\def\bu{{\bf u}}
\def\bv{{\bf v}}
\def\bM{{\bf M}}
\def\bR{{\bf R}}
\def\bX{{\bf X}}
\def\bY{{\bf Y}}
\def\bZ{{\bf Z}}


%\def\blackslug{\hbox{\hskip 1pt \vrule width 4pt height 8pt depth 1.5pt \hskip 1pt}}
%\newenvironment{proof}{\par\penalty-1000\vskip .5 pt\noindent{\bf Proof\/: }}
%{\quad\blackslug\lower 8.5pt\null\par}

\firstpageno{1}

% Heading arguments are {volume}{year}{pages}{submitted}{published}{authors}

\jmlrheading{5}{2004}{27-72}{10/02; Revised 8/03}{1/04}{Gert R.G. Lanckriet,
Nello Cristianini, Peter Bartlett, Laurent El Ghaoui and Michael
I. Jordan} \ShortHeadings{Learning the Kernel Matrix with
Semidefinite Programming}{Lanckriet, Cristianini, Bartlett, El
Ghaoui and Jordan}

\firstpageno{27}


\begin{document}

\title{Learning the Kernel Matrix with Semidefinite Programming}

\author{\name Gert R.G.\ Lanckriet
    \email gert@eecs.berkeley.edu \\
    \addr Department of Electrical Engineering and Computer Science\\
     University of California\\
         Berkeley, CA 94720, USA\\[.1cm]
 \name Nello Cristianini
    \email nello@support-vector.net \\
    \addr Department of Statistics\\
     University of California\\
         Davis, CA 95616, USA\\[.1cm]
 \name Peter Bartlett
    \email bartlett@stat.berkeley.edu \\
    \addr Department of Electrical Engineering and Computer Science
and Department of Statistics\\
         Berkeley, CA 94720, USA\\[.1cm]
 \name Laurent El Ghaoui
    \email elghaoui@eecs.berkeley.edu \\
    \addr Department of Electrical Engineering and Computer Science\\
     University of California\\
         Berkeley, CA 94720, USA\\[.1cm]
 \name Michael I. Jordan \email jordan@stat.berkeley.edu \\
    \addr Department of Electrical Engineering and Computer Science
and Department of Statistics\\
     University of California\\
         Berkeley, CA 94720, USA}

% BIOwulf Technologies / Division of Computer Science and Department
% of Statistics, U.C. Berkeley


\editor{Bernhard Sch\"olkopf}

\maketitle

\begin{abstract}%   <- trailing '%' for backward compatibility of .sty file
Kernel-based learning algorithms work by embedding the data into a
Euclidean space, and then searching for linear relations among the
embedded data points. The embedding is performed implicitly, by
specifying the inner products between each pair of points in the
embedding space. This information is contained in the so-called
kernel matrix, a symmetric and positive semidefinite matrix that
encodes the relative positions of all points. Specifying this
matrix amounts to specifying the geometry of the embedding space
and inducing a notion of similarity in the input space---classical
model selection problems in machine learning. In this paper we
show how the kernel matrix can be learned from data via
semidefinite programming (SDP) techniques. When applied to a
kernel matrix associated with both training and test data this
gives a powerful transductive algorithm---using the labeled part
of the data one can learn an embedding also for the unlabeled
part. The similarity between test points is inferred from training
points and their labels. Importantly, these learning problems are
convex, so we obtain a method for learning both the model class
and the function without local minima. Furthermore, this approach
leads directly to a convex method for learning the 2-norm soft margin
parameter in support vector machines, solving an important open problem.
\end{abstract}

\begin{keywords}
kernel methods, learning kernels, transduction, model selection,
support vector machines, convex optimization, semidefinite
programming
\end{keywords}


\section{Introduction}

Recent advances in kernel-based learning algorithms have brought
the field of machine learning closer to the desirable goal of
autonomy---the goal of providing learning systems that require as
little intervention as possible on the part of a human user.
In particular, kernel-based algorithms are generally formulated in
terms of convex optimization problems, which have a single global
optimum and thus do not require heuristic choices of learning rates,
starting configurations or other free parameters.  There are, of course,
statistical model selection problems to be faced within the kernel approach;
in particular, the choice of the kernel and the corresponding feature
space are central choices that must generally be made by a human user.
While this provides opportunities for prior knowledge to be brought
to bear, it can also be difficult in practice to find prior justification
for the use of one kernel instead of another.  It would be desirable to
explore model selection methods that allow kernels to be chosen
in a more automatic way based on data.

It is important to observe that we do not necessarily need to
choose a kernel \emph{function}, specifying the inner product
between the images of all possible data points when mapped from
an input space $\mathcal{X}$ to an appropriate feature space
$\mathcal{F}$. Since kernel-based learning methods extract all
information needed from inner products of training data points in
$\mathcal{F}$, the values of the kernel function at pairs which
are not present are irrelevant. So, there is no need to learn a
kernel function over the entire sample space to specify the embedding
of a finite training data set via a kernel function mapping. Instead,
it is sufficient to specify a finite-dimensional \emph{kernel matrix}
(also known as a \emph{Gram matrix}) that contains as its entries
the inner products in $\mathcal{F}$ between all pairs of data
points. Note also that it is possible to show that any symmetric
positive semidefinite matrix is a valid Gram matrix, based on an inner
product in some Hilbert space. This suggests viewing the model selection
problem in terms of Gram matrices rather than kernel functions.

%A practically important form in which this problem appears is the
%case where a diverse set of possibly good Gram matrices
%(similarity measures/representations) has been constructed, e.g.,
%using heterogeneous data sources. The challenge is to combine these
%measures into one optimal similarity measure (embedding), to be
%used for learning. The proposed approach will deal with this case.

% gert: this should be mentioned since ending up solving the problem
% with a linear combination of kernels is certainly not disappointing
% given those practical cases that really benefit from this approach
% nello says: i would not apologize for this here, our model is more
% general than this. we should put this comment only in the experiments
% section, that is where we do introduce this step, + in conclusions


In this paper our main focus is \emph{transduction}---the problem
of completing the labeling of a partially labeled dataset. In
other words, we are required to make predictions only at a finite
set of points, which are specified a priori. Thus, instead of
learning a function, we only need to learn a set of labels. There
are many practical problems in which this formulation is
natural---an example is the prediction of gene function, where the
genes of interest are specified a priori, but the function of many
of these genes is unknown.

%This approach makes a lot
%of sense, e.g., in a biological setting where all genes are
%initially known but only for part of them the gene function has
%been identified.

We will address this problem by learning a kernel matrix
corresponding to the entire dataset, a matrix that optimizes a
certain cost function that depends on the available labels. In
other words, we use the available labels to learn a good
embedding, and we apply it to both the labeled and the unlabeled
data.  The resulting kernel matrix can then be used in combination
with any of a number of existing learning algorithms that use
kernels.  One example that we discuss in detail is the support
vector machine (SVM), where our methods yield a new transduction
method for SVMs that scales polynomially with the number of test
points. Furthermore, this approach will offer us a method to
optimize the 2-norm soft margin parameter for these SVM learning
algorithms, solving an important open problem.

All this can be done in full generality by using techniques from
semidefinite programming (SDP), a branch of convex optimization
that deals with the optimization of convex functions over the convex cone
of positive semidefinite matrices, or convex subsets thereof.
Any convex set of kernel matrices is a set of this kind. Furthermore,
it turns out that many natural cost functions, motivated by
error bounds, are convex in the kernel matrix.

A second application of the ideas that we present here is to
the problem of combining data from multiple sources.  Specifically,
assume that each source is associated with a kernel function, such
that a training set yields a set of kernel matrices.  The tools
that we develop in this paper make it possible to optimize over
the coefficients in a linear combination of such kernel matrices.
These coefficients can then be used to form linear combinations
of kernel functions in the overall classifier.  Thus this approach
allows us to combine possibly heterogeneous data sources, making
use of the reduction of heterogeneous data types to the common
framework of kernel matrices, and choosing coefficients that
emphasize those sources most useful in the classification decision.

In Section~\ref{s-kernels}, we recall the main ideas from
kernel-based learning algorithms, and introduce a variety of
criteria that can be used to assess the suitability of a kernel
matrix: the hard margin, the 1-norm and 2-norm soft margin, and
the kernel alignment. Section~\ref{s-sdp} reviews the basic
concepts of semidefinite programming. In Section~\ref{sec-algs} we
put these ideas together and consider the optimization of the
various criteria over sets of kernel matrices.  For a set of
linear combinations of fixed kernel matrices, these optimization
problems reduce to SDP. If the linear coefficients are constrained
to be positive, they can be simplified even further, yielding a
quadratically-constrained quadratic program, a special case of the
SDP framework. If the linear combination contains the identity
matrix, we obtain a convex method for optimizing the 2-norm soft
margin parameter in support vector machines. Section~\ref{s-bound}
presents statistical error bounds that motivate one of our cost
functions. Empirical results are reported in Section~\ref{s-exp}.

\subsection*{Notation}
Vectors are represented in bold notation, e.g., $\mathbf{v} \in
\mathbb{R}^n$, and their scalar components in italic script, e.g.,
$v_1, v_2, \ldots, v_n$. Matrices are represented in italic
script, e.g., $X \in \mathbb{R}^{m \times n}$. For a square,
symmetric matrix $X$, $X \succeq 0$ means that $X$ is positive
semidefinite, while $X \succ 0$ means that $X$ is positive
definite.  For a vector $\mathbf{v}$, the notations $\mathbf{v}
\geq 0$ and $\mathbf{v} >0$ are understood componentwise.

\section{Kernel Methods}\label{s-kernels}

Kernel-based learning algorithms \citep[see, for
example,][]{CrS:00,ScS:02,ShC:04} work by embedding the data into
a Hilbert space, and searching for linear relations in such a
space. The embedding is performed implicitly, by specifying the
inner product between each pair of points rather than by giving
their coordinates explicitly. This approach has several
advantages, the most important deriving from the fact that the
inner product in the embedding space can often be computed much
more easily than the coordinates of the points themselves.

Given an input set $\cal X$, and an embedding space $\cal F$, we
consider a map $\Phi : \cal X \rightarrow F$. Given two points
$\bx_i \in \cal X$ and $\bx_j \in \cal X$, the function that
returns the inner product between their images in the space $\cal
F$ is known as the {\em kernel function}.

\begin{definition}
A {\em kernel }is a function $k$, such that
$k({\bx},{\bz})=\langle \Phi({\bx}),{\Phi}({\bz})\rangle$ for all
$\bx,\bz \in \cal X$, where ${\Phi }$ is a mapping from $\cal X$
to an (inner product) feature space $\cal F$. A {\em kernel
matrix} is a square matrix $K\in\mathbb{R}^{n\times n}$ such that
$K_{ij}=k(\bx_i,\bx_j)$ for some $\bx_1,\ldots,\bx_n\in\cal X$ and
some kernel function $k$.
\end{definition}

The kernel matrix is also known as the Gram matrix. It is a
symmetric, positive semidefinite matrix, and since it specifies
the inner products between all pairs of points
$\{\bx_i\}_{i=1}^n$, it completely determines the relative
positions of those points in the embedding space.

Since in this paper we will consider a \emph{finite} input set
$\cal X$, we can characterize kernel functions and matrices in the
following simple way.

\begin{proposition}\label{prop:kmatrix}
Every positive semidefinite and symmetric matrix is a kernel matrix.
Conversely, every kernel matrix is symmetric and positive
semidefinite.
\end{proposition}

Notice that, if we have a kernel matrix, we do not need to know
the kernel function, nor the implicitly defined map $\Phi$, nor
the coordinates of the points $\Phi(\bx_i)$. We do not even need
$\cal X$ to be a vector space; in fact in this paper it will be a
generic finite set.  We are guaranteed that the data are
implicitly mapped to some Hilbert space by simply checking that
the kernel matrix is symmetric and positive semidefinite.

The solutions sought by kernel-based algorithms such as the
support vector machine (SVM) are affine functions in the feature
space:
  $$ f(\bx) = \langle \bw , \Phi(\bx) \rangle + b, $$
for some weight vector $\mathbf{w}\in\cal F$. The kernel can be
exploited whenever the weight vector can be expressed as a linear
combination of the training points, $\bw = \sum_{i=1}^{n} \alpha
_{i} \Phi(\bx_{i})$, implying that we can express $f$ as
  $$
    f(\mathbf{x})=\sum_{i=1}^{n}\alpha_{i}k(\mathbf{x}_{i},\mathbf{x}) + b.
  $$
For example, for binary classification, we can use a thresholded
version of $f(\mathbf{x})$, i.e., $\sign \left( f(\bx) \right)$,
as a decision function to classify unlabeled data. If $f(\bx)$ is
positive, then we classify $\bx$ as belonging to class $+1$;
otherwise, we classify $\bx$ as belonging to class $-1$. An
important issue in applications is that of choosing a kernel $k$
for a given learning task; intuitively, we wish to choose a kernel
that induces the ``right'' metric in the input space.

\subsection{Criteria Used in Kernel Methods}\label{ss-measures}

Kernel methods choose a function that is linear in the feature
space by optimizing some criterion over the sample. This section
describes several such criteria~\citep[see, for
example,][]{CrS:00,ScS:02,ShC:04}. All of these criteria can be
considered as measures of separation of the labeled data.  We
first consider the \emph{hard margin} optimization problem.

\begin{definition} {\bf Hard Margin} Given a labeled
sample $S_l = \{ (\mathbf{x}_1,y_1), \ldots, (\mathbf{x}_n, y_n)
\}$, the hyperplane $(\mathbf{w}_*,b_*)$ that solves the
optimization problem
\begin{eqnarray}
\label{margindef1}
\min_{\mathbf{w},b} & & \langle
    \mathbf{w},\mathbf{w}\rangle \\
\textrm{subject to} & & y_i(\langle
    \mathbf{w},\Phi (\mathbf{x}_i) \rangle + b) \geq 1, \ \ i = 1, \ldots,
    n, \nonumber
\end{eqnarray}
realizes the \emph{maximal margin classifier} with geometric margin
$\gamma = 1 / \|\mathbf{w}_*\|_2$, assuming it exists.
\end{definition}

Geometrically, $\gamma$ corresponds to the distance between the
convex hulls (the smallest convex sets that contain the data in
each class) of the two classes \citep{BeB:00}.

By transforming~(\ref{margindef1}) into its corresponding Lagrangian
dual problem, the solution is given by
\begin{eqnarray}
\omega(K) & = & 1/\gamma^2 \nonumber \\
  & = & \langle \mathbf{w}_*,\mathbf{w}_* \rangle \nonumber \\
  & = & \max_{\ba} \; 2\ba^T\be - \ba^T G (K) \ba ~:~ \ba
\geq 0, \;\; \ba^T\by = 0,
\label{margindef}
\end{eqnarray}
where $\be$ is the $n$-vector of ones, $\ba \in \mathbb{R}^n$,
$G(K)$ is defined by $G_{ij}(K) = [K]_{ij} y_i y_j =
k(\mathbf{x}_i,\mathbf{x}_j) y_i y_j$, and $\ba \geq 0$ means
$\alpha_i \geq 0, \ i = 1, \ldots, n$.

The hard margin solution exists only when the labeled sample is
linearly separable in feature space.
For a non-linearly-separable labeled sample $S_l$, we can define
the \emph{soft margin}. We consider the 1-norm and 2-norm soft margins.

\begin{definition} {\bf 1-norm Soft Margin} Given a labeled sample $S_l = \{
(\mathbf{x}_1,y_1), \ldots, (\mathbf{x}_n, y_n) \}$, the
hyperplane $(\mathbf{w_*},b_*)$ that solves the optimization
problem
\begin{eqnarray}\label{softmargindef1}
\min_{\mathbf{w},b,\bxi} & & \langle
    \mathbf{w},\mathbf{w}\rangle + C \sum_{i=1}^n \xi_i \\
\textrm{subject to} & & y_i(\langle
    \mathbf{w},\Phi (\mathbf{x}_i) \rangle + b) \geq 1 - \xi_i, \ \ i = 1, \ldots,
    n \nonumber\\
& & \xi_i \geq 0, \ \ i = 1, \ldots, n \nonumber
\end{eqnarray}
realizes the \emph{1-norm soft margin classifier} with geometric margin
$\gamma = 1 / \|\mathbf{w}_*\|_2$. This margin is also called the
1-norm soft margin.
\end{definition}

As for the hard margin, we can express the solution of~(\ref{softmargindef1})
in a revealing way by considering the corresponding Lagrangian dual problem:
\begin{eqnarray}\label{dualsoftmargindef1}
\omega_{S1}(K) & = & \langle
    \mathbf{w}_*,\mathbf{w}_* \rangle + C \sum_{i=1}^n \xi_{i,*} \\
    & = & \max_{\ba} \; 2\ba^T\be - \ba^T G (K) \ba ~:~ C \geq
\ba \geq 0, \;\; \ba^T\by = 0. \nonumber
\end{eqnarray}

\begin{definition} {\bf 2-norm Soft Margin} Given a labeled sample $S_l = \{
(\mathbf{x}_1,y_1), \ldots, (\mathbf{x}_n, y_n) \}$, the
hyperplane $(\mathbf{w}_*,b_*)$ that solves the optimization
problem
\begin{eqnarray}\label{softmargindef2}
\min_{\mathbf{w},b,\bxi} & & \langle
    \mathbf{w},\mathbf{w}\rangle + C \sum_{i=1}^n \xi_i^2 \\
\textrm{subject to} & & y_i(\langle
    \mathbf{w},\Phi (\mathbf{x}_i) \rangle + b) \geq 1 - \xi_i, \ \ i = 1, \ldots,
    n \nonumber\\
& & \xi_i \geq 0, \ \ i = 1, \ldots, n \nonumber
\end{eqnarray}
realizes the \emph{2-norm soft margin classifier} with geometric margin
$\gamma = 1 / \|\mathbf{w}_*\|_2$. This margin is also called the
2-norm soft margin.
\end{definition}

Again, by considering the corresponding dual problem,
the solution of~(\ref{softmargindef2}) can be expressed
as
\begin{eqnarray}\label{dualsoftmargindef2}
\omega_{S2}(K) & = & \langle
    \mathbf{w}_*,\mathbf{w}_* \rangle + C \sum_{i=1}^n \xi_{i,*}^2 \\
    & = & \max_{\ba} \; 2\ba^T\be - \ba^T \left( G (K) +
\frac{1}{C} I_n \right) \ba ~:~ \ba \geq 0, \;\; \ba^T\by = 0.
\nonumber
\end{eqnarray}

With a fixed kernel, all of these criteria give upper bounds on
misclassification probability \citep[see, for example, Chapter 4
of][]{CrS:00}. Solving these optimization problems for a single
kernel matrix is therefore a way of optimizing an upper bound on error
probability.

In this paper, we allow the kernel matrix to be chosen from a class of
kernel matrices. Previous error bounds are not applicable in this case.
However, as we will see in Section~\ref{s-bound}, the margin $\gamma$ can be used to
bound the performance of support vector machines for transduction,
with a linearly parameterized class of kernels.

We do not discuss further the merit of these different cost
functions, deferring to the current literature on classification,
where these cost functions are widely used with fixed kernels. Our
goal is to show that these cost functions can be optimized---with
respect to the kernel matrix---in an SDP setting.


Finally, we define the \emph{alignment} of two kernel
matrices~\citep{CKE:01,CSE:02}. Given an (unlabeled) sample
$S=\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\}$, we use the following
(Frobenius) inner product between Gram matrices, $\langle
K_{1},K_{2}\rangle _{F} = \textrm{trace}(K_{1}^T K_{2})
 = \sum_{i,j=1}^{n}k_{1}(\mathbf{x}_{i},\mathbf{x}_{j})k_{2}(\mathbf{x}_{i},\mathbf{x}_{j})$.

\begin{definition} {\bf Alignment} The \emph{(empirical) alignment} of a kernel
$k_1$ with a kernel $k_2$ with respect to the sample $S$ is the quantity
  $$
    \hat{A}(S, k_1, k_2)=\frac{\langle K_1, K_2
    \rangle_{F}}{\sqrt{\langle K_1, K_1\rangle_{F} \langle
    K_2, K_2 \rangle_{F}}},
  $$
where $K_i$ is the kernel matrix for the sample $S$ using kernel
$k_i$.
\end{definition}

This can also be viewed as the cosine of the angle between two
bi-dimensional vectors $K_1$ and $K_2$, representing the Gram
matrices. Notice that we do not need to know the labels for the
sample $S$ in order to define the alignment of two kernels with
respect to $S$. However, when the vector $\by$ of $\{\pm 1\}$
labels for the sample is known, we can consider $K_2=\by \by^T$---the
optimal kernel since $k_{2}(\mathbf{x}_{i},\mathbf{x}_{j}) = 1$ if $y_i = y_j$ and
$k_{2}(\mathbf{x}_{i},\mathbf{x}_{j}) = -1$ if $y_i \neq y_j$. The
alignment of a kernel $k$ with $k_2$ with respect to $S$ can be
considered as a quality measure for $k$:
\begin{equation}\label{eq:def_align_2}
    \hat{A}(S,K,\by\by^T) = \frac{\langle
    K,\by\by^T\rangle_{F}}{\sqrt{\langle K, K\rangle_{F} \langle
    \by\by^T, \by\by^T\rangle_{F}}} = \frac{\left\langle
    K, \by\by^T\right\rangle_{F} }{n\sqrt {\langle K,K
    \rangle_{F}}},
\end{equation}
since $\left\langle \by\by^T,\by\by^T\right\rangle_{F} = n^2$.


\section{Semidefinite Programming (SDP)}\label{s-sdp}

In this section we review the basic definition of semidefinite
programming as well as some important concepts and key results.
Details and proofs can be found in \cite{BoV:01}.

Semidefinite programming \citep{NeN:94,VaB:96,BoV:01} deals with
the optimization of convex functions over the convex
cone\footnote{$S \subseteq \mathbb{R}^d$ is a convex cone if and
only if $\forall \bx, \by \in S$ and $\forall \lambda, \mu \geq
0$, we have $\lambda \bx + \mu \by \in S$.} of symmetric, positive
semidefinite matrices
  \[
    \mathcal{P} = \left\{ X \in \mathbb{R}^{p \times p} ~|~
      X = X^T, X \succeq 0 \right\} ,
  \]
or affine subsets of this cone. Given Proposition
\ref{prop:kmatrix}, $\mathcal{P}$ can be viewed as a search space
for possible kernel matrices. This consideration leads to the key
problem addressed in this paper---we wish to specify a convex cost
function that will enable us to learn the optimal kernel matrix
within $\mathcal{P}$ using semidefinite programming.

\subsection{Definition of Semidefinite Programming}

A {\em linear matrix inequality,} abbreviated LMI, is a constraint
of the form
\[
F(\bu) :=F_0 + u_1 F_1 + \ldots + u_q F_q \preceq 0.
\]
Here, $\bu$ is the vector of decision variables, and
$F_0,\ldots,F_q$ are given symmetric $p \times p$ matrices. The
notation $F(\bu) \preceq 0$ means that the symmetric matrix $F$ is
negative semidefinite. Note that such a constraint is in general
a {\em nonlinear} constraint; the term ``linear'' in the name LMI
merely emphasizes that $F$ is affine in $\bu$. Perhaps the most
important feature of an LMI constraint is its convexity: the set
of $\bu$ that satisfy the LMI is a convex set.

An LMI constraint can be seen as an {\em infinite} set of scalar,
affine constraints.  Indeed, for a given $\bu$, $F(\bu) \preceq 0$
if and only if $\bz^TF(\bu)\bz \leq 0$ for every $\bz$; every
constraint indexed by $\bz$ is an affine inequality, in the
ordinary sense, i.e., the left-hand side of the inequality is a
scalar, composed of a linear term in $\bu$ and a constant term.
Alternatively, using a standard result from linear algebra, we may
state the constraint as
\begin{equation}
\label{eq:LMI-infinite-Z} \forall Z \in {\cal P} \ : \
\textrm{trace} ( F(\bu) Z ) \leq 0 .
\end{equation}
This can be seen by writing down the spectral decomposition of $Z$
and using the fact that $\bz^TF(\bu)\bz \leq 0$ for every $\bz$.
%By homogeneity, we may restrict $Z$ to have trace less than one.

A semidefinite program (SDP) is an optimization problem with a
linear objective, and linear matrix inequality and affine equality
constraints.
\begin{definition}\label{def-sdp}
A semidefinite program  is a problem of the form
\begin{eqnarray}\label{genform}
\min_{\bu} & & \bc^T \bu \\
\textrm{subject to} & & F^j(\bu) = F^j_0 + u_1 F^j_1 + \ldots +
u_q F^j_q \preceq 0,
\quad j = 1, \ldots, L \nonumber \\
& & A\bu = \bb, \nonumber
\end{eqnarray}
where $\bu \in \mathbb{R}^q$ is the vector of decision variables,
$\bc \in \mathbb{R}^q$ is the objective vector, and matrices
$F^j_i = (F^j_i)^T \in \mathbb{R}^{p \times p}$ are given.
\end{definition}
Given the convexity of its LMI constraints, SDPs are convex optimization
problems.  The usefulness of the SDP formalism stems from two
important facts.  First, despite the seemingly very specialized
form of SDPs, they arise in a host of applications; second, there
exist interior-point algorithms to solve SDPs that have good
theoretical and practical computational efficiency~\citep{VaB:96}.

One very useful tool to reduce a problem to an SDP is the so-called
Schur complement lemma; it will be invoked repeatedly.
\begin{lemma}\label{lemma:SchurCompl}
{\bf (Schur Complement Lemma)} Consider the partitioned symmetric
matrix
\[
X = X^T = \left(\begin{array}{cc}
  A & B \\
  B^T & C
\end{array}\right),
\]
where $A,C$ are square and symmetric. If $\det (A) \neq 0$, we
define the Schur complement of $A$ in $X$ by the matrix $S = C -
B^T A^{-1} B$. The Schur Complement Lemma states that if $A \succ
0$, then $X \succeq 0$ if and only if $S \succeq 0$.
\end{lemma}
%Here, the notation $A \preceq B$ means $B - A \succeq 0$, that is,
%$B - A \in \mathcal{P}$.

To illustrate how this lemma can be used to cast a nonlinear
convex optimization problem as an SDP, consider the following
result:
\begin{lemma}
The quadratically constrained quadratic program (QCQP)
\begin{eqnarray}
\min_{\mathbf{u}} & & \ f_0(\mathbf{u}) \label{opt:exsdp} \\
\textrm{subject to} & & \ f_i(\mathbf{u}) \leq 0, \ \ i = 1,
\ldots, M, \nonumber
\end{eqnarray}
with $f_i(\mathbf{u}) \triangleq (A_i \mathbf{u} +
\mathbf{b}_i)^T(A_i \mathbf{u} + \mathbf{b}_i) - \mathbf{c}_i^T
\mathbf{u} - d_i$, is equivalent to the semidefinite programming
problem
\begin{eqnarray}
\min_{\mathbf{u},t} & & \ t \label{eq:sdp4qcqp} \\
\textrm{subject to} & & \ \begin{pmatrix}
  I & A_0 \mathbf{u}
+ \mathbf{b_0} \\
  (A_0 \mathbf{u}
+ \mathbf{b_0})^T & \mathbf{c_0}^T \mathbf{u} + d_0 + t
\end{pmatrix} \succeq 0, \nonumber \\
& & \ \begin{pmatrix}
  I & A_i \mathbf{u}
+ \mathbf{b}_i \\
  (A_i \mathbf{u}
+ \mathbf{b}_i)^T & \mathbf{c}_i^T \mathbf{u} + d_i
\end{pmatrix} \succeq 0, \quad i = 1, \ldots, M. \nonumber
\end{eqnarray}
\end{lemma}
This can be seen by rewriting the QCQP (\ref{opt:exsdp}) as
\begin{eqnarray}
\min_{\mathbf{u},t} & & \ t \nonumber \\
\textrm{subject to} & & \ t - f_0(\mathbf{u}) \geq 0, \nonumber \\
& & \ - f_i(\mathbf{u}) \geq 0, \ \ i = 1, \ldots, M. \nonumber
\end{eqnarray}
Note that for a fixed and feasible $\mathbf{u}$, $t=f_{0}\left(
\mathbf{u}\right)$ is the optimal solution. The convex quadratic
inequality $t - f_0(\mathbf{u}) = (t + \mathbf{c_0}^T \mathbf{u} +
d_0) - (A_0 \mathbf{u} + \mathbf{b_0})^T I^{-1} (A_0 \mathbf{u} +
\mathbf{b_0}) \geq 0$ is now equivalent to the following LMI,
using the Schur Complement Lemma \ref{lemma:SchurCompl}:
$$\begin{pmatrix}
  I & A_0 \mathbf{u}
+ \mathbf{b_0} \\
  (A_0 \mathbf{u}
+ \mathbf{b_0})^T & \mathbf{c_0}^T \mathbf{u} + d_0 + t
\end{pmatrix} \succeq 0.$$
Similar steps for the other quadratic inequality constraints
finally yield (\ref{eq:sdp4qcqp}), an SDP in standard form
(\ref{genform}), equivalent to (\ref{opt:exsdp}). This shows that
a QCQP can be cast as an SDP. Of course, in practice a QCQP should
not be solved using general-purpose SDP solvers, since the
particular structure of the problem at hand can be efficiently
exploited. The above show that QCQPs, and in particular linear
programming problems, belong to the SDP family.

\subsection{Duality}
An important principle in optimization---perhaps even the most
important principle---is that of {\it duality}. To illustrate
duality in the case of an SDP, we will first review basic concepts
in duality theory and then show how they can be extended to
semidefinite programming. In particular, duality will give
insights into optimality conditions for the semidefinite program.

Consider an optimization problem with $n$ variables and $m$ scalar
constraints:
\begin{eqnarray}
\min_{\bu} & & f_0(\bu) \label{opt:stand-min} \\
\textrm{subject to} & & f_i(\bu) \leq 0, \quad i=1,\ldots,m,
\nonumber
\end{eqnarray}
where $\bu \in \mathbb{R}^n$. In the context of duality, problem
(\ref{opt:stand-min}) is called the {\it primal problem}; we
denote its optimal value $p^*$. For now, we do not assume
convexity.

\begin{definition}
\label{def:lagrangian}
 {\bf Lagrangian} The \emph{Lagrangian}
$\mathcal{L} \ : \mathbb{R}^{n+m} \rightarrow \mathbb{R}$
corresponding to the minimization problem (\ref{opt:stand-min}) is
defined as $$ \mathcal{L}(\bu,\blambda) = f_0(\bu) +
\lambda_1f_1(\bu) + \ldots + \lambda_mf_m(\bu). $$ The $\lambda_i
\in \mathbb{R}, \ i = 1, \ldots, m$ are called \emph{Lagrange
multipliers} or \emph{dual variables}.
\end{definition}

One can now notice that
\begin{equation*}
h(\bu) = \max_{\blambda \geq 0} \mathcal{L}(\bu,\blambda) =
\left\{
\begin{array}{ll}
  f_0(\bu) & \textrm{if} \ f_i(\bu) \leq 0, \ i = 1, \ldots, m \\
  + \infty & \textrm{otherwise}.
\end{array} \right.
\end{equation*}
So, the function $h(\bu)$ coincides with the objective $f_0(\bu)$
in regions where the constraints \mbox{$f_i(\bu) \leq 0$}, \mbox{$ \ i = 1,
\ldots, m$}, are satisfied and $h(\bu) = + \infty$ in infeasible
regions. In other words, $h$ acts as a ``barrier'' of the feasible
set of the primal problem.  Thus we can as well use $h(\bu)$ as
objective function and rewrite the original primal problem
(\ref{opt:stand-min}) as an {\em unconstrained} optimization
problem:
\begin{equation}\label{opt:stand-min-lagrangian}
p^* = \min_\bu \ \max_{\blambda \geq 0} \mathcal{L}(\bu,\blambda).
\end{equation}
The notion of weak duality amounts to exchanging the ``min'' and
``max'' operators in the above formulation, resulting in a lower
bound on the optimal value of the primal problem. Strong duality
refers to the case when this exchange can be done without altering
the value of the result: the lower bound is actually equal to the
optimal value $p^\ast$.  While weak duality always hold, even if
the primal problem (\ref{opt:stand-min-lagrangian}) is not convex,
strong duality may not hold. However, for a large class of generic
convex problems, strong duality holds.

\begin{lemma}
{\bf Weak duality} For all functions $f_0, f_1, \ldots, f_m$ in
(\ref{opt:stand-min}), not necessarily convex, we can exchange the
$\max$ and the $\min$ and get a lower bound on $p^*$:
$$ d^* = \max_{\blambda \geq 0} \ \min_\bu
\mathcal{L}(\bu,\blambda) \leq \min_\bu \ \max_{\blambda \geq 0}
\mathcal{L}(\bu,\blambda) = p^*.$$
\end{lemma}
The objective function of the maximization problem is now called
the (Lagrange) dual function.
\begin{definition} {\bf (Lagrange) dual function}
The \emph{(Lagrange) dual function} $g : \mathbb{R}^m
\rightarrow\mathbb{R}$ is defined as
\begin{eqnarray}
g(\blambda) & = & \min_\bu \mathcal{L}(\bu,\blambda) \nonumber \\
& = & \min_\bu \ f_0(\bu) + \lambda_1f_1(\bu) + \ldots +
\lambda_mf_m(\bu).
\end{eqnarray}
Furthermore $g(\blambda)$ is concave, even if the $f_i(\bu)$ are
not convex.
\end{definition}
The concavity can easily be seen by considering first that for a
given $\bu$, $\mathcal{L}(\bu,\blambda)$ is an affine function of
$\blambda$ and hence is a concave function. Since $g(\blambda)$ is
the pointwise minimum of such concave functions, it is concave.

\begin{definition} {\bf Lagrange dual problem}
The \emph{Lagrange dual problem} is defined as $$d^* =
\max_{\blambda \geq 0} g(\blambda).$$
\end{definition}
Since $g(\blambda)$ is concave, this will always be a convex
optimization problem, even if the primal is not. By {\it weak
duality}, we always have $d^* \leq p^*$, even for non-convex
problems. The value $p^* - d^*$ is called the duality gap. For
{\bf convex} problems, we usually (although not always) have {\it
strong duality} at the optimum, i.e., $$ d^* = p^*,$$ which is
also referred to as a \emph{zero duality gap}. For convex
problems, a sufficient condition for zero duality gap is provided
by \emph{Slater's condition}:

\begin{lemma}
{\bf Slater's condition} If the primal problem
(\ref{opt:stand-min}) is convex and is {\bf strictly feasible},
i.e., $\exists \ \bu_0 \ : \ f_i(\bu_0) < 0, \ i = 1, \ldots, m$,
then
$$p^* = d^*.$$
\end{lemma}

\subsection{SDP Duality and Optimality Conditions}\label{ss-sdpduality}
Consider for simplicity the case of an SDP with a single LMI
constraint, and no affine equalities:
\begin{equation}
\label{eq:primal-SDP} p^\ast = \min_\bu \: \bc^T\bu \mbox{ subject
to } F(\bu) = F_0+u_1F_1 + \ldots u_q F_q \preceq 0 .
\end{equation}
The general case of multiple LMI constraints and affine equalities
can be handled by elimination of the latter and using
block-diagonal matrices to represent the former as a single LMI.

The classical Lagrange duality theory outlined in the previous
section does not directly apply here, since we are not dealing
with finitely many constraints in scalar form; as noted earlier,
the LMI constraint involves an infinite number of such
constraints, of the form (\ref{eq:LMI-infinite-Z}). One way to
handle such constraints is to introduce a Lagrangian of the form
\[
\mathcal{L}(\bu,Z) = \bc^T \bu + \textrm{trace} (Z F(\bu)),
\]
where the dual variable $Z$ is now a symmetric matrix, of the same
size as $F(\bu)$.  We can check that such a Lagrange function
fulfills the same role assigned to the function defined in
Definition \ref{def:lagrangian} for the case with scalar
constraints. Indeed, if we define $h(\bu) = \max_{Z \succeq 0}
\mathcal{L}(\bu,Z)$ then
\begin{equation*}
h(\bu) = \max_{Z \succeq 0} \mathcal{L}(\bu,Z) = \left\{
\begin{array}{ll}
  \bc^T\bu & \textrm{if} \ F(\bu ) \preceq 0, \\
  + \infty & \textrm{otherwise.}
\end{array} \right.
\end{equation*}
Thus, $h(\bu)$ is a barrier for the primal SDP
(\ref{eq:primal-SDP}), that is, it coincides with the objective of
(\ref{eq:primal-SDP}) on its feasible set, and is infinite
otherwise. Notice that to the LMI constraint we now associate a
multiplier {\em matrix}, which will be constrained to the positive
semidefinite cone.

In the above, we made use of the fact that, for a given symmetric
matrix $F$,
\[
\phi(F) :=\sup_{Z \succeq 0} \:  \textrm{trace} (ZF)
\]
is $+\infty$ if $F$ has a positive eigenvalue, and zero if $F$ is
negative semidefinite. This property is obvious for diagonal
matrices, since in that case the variable $Z$ can be constrained
to be diagonal without loss of generality.  The general case
follows from the fact that if $F$ has the eigenvalue decomposition
$F = U\Lambda U^T$, where $\Lambda$ is a diagonal matrix
containing the eigenvalues of $F$, and $U$ is orthogonal, then
$\textrm{trace} (ZF) = \textrm{trace} (Z' \Lambda)$, where $Z' =
U^TZU$ spans the positive semidefinite cone whenever $Z$ does.

Using the above Lagrangian, one can cast the original problem
(\ref{eq:primal-SDP}) as an unconstrained optimization problem:
\[
p^* = \min_\bu \max_{Z \succeq 0} \mathcal{L}(\bu,Z).
\]
By weak duality, we obtain a lower bound on $p^\ast$ by exchanging
the min and max:
$$ d^* = \max_{Z \succeq 0} \min_\bu  \mathcal{L}(\bu,Z) \leq \min_\bu
\max_{Z \succeq 0} \mathcal{L}(\bu,Z) = p^*.$$

The inner minimization problem is easily solved analytically, due
to the special structure of the SDP.  We obtain a closed form for
the (Lagrange) dual function:
\begin{eqnarray}
g(Z) = \min_\bu  \mathcal{L}(\bu,Z) & = & \min_\bu \bc^T \bu +
\textrm{trace} (Z F_0)
+ \sum_{i=1}^q u_i \ \textrm{trace} (Z F_i) \nonumber \\
& = & \left\{ \begin{array}{ll}
  \textrm{trace}(Z F_0) & \textrm{if} \ c_i = -\textrm{trace}(Z F_i), \ i=1,\ldots,q \\
  - \infty & \textrm{otherwise}.
\end{array} \right. \nonumber
\end{eqnarray}
The dual problem can be explicitly stated as follows:
\begin{equation}\label{eq:SDP-dual}
d^* = \max_{Z \succeq 0} \min_\bu  \mathcal{L}(\bu,Z) = \max_{Z}
\textrm{trace}(Z F_0) \ \ \textrm{subject to } Z \succeq 0, \ c_i
= -\textrm{trace}(Z F_i), \ i=1,\ldots,q.
\end{equation}
We observe that the above problem is an SDP, with a single LMI
constraint and $q$ affine equalities in the matrix dual variable
$Z$.

While weak duality always holds, strong duality may not, even for
SDPs.  Not surprisingly, a Slater-type condition ensures strong
duality. Precisely, if the primal SDP (\ref{eq:primal-SDP}) is
strictly feasible, that is, there exists a $\bu_0$ such that
$F(\bu_0) \prec 0$, then $p^\ast = d^\ast$.  If, in addition, the
dual problem is also strictly feasible, meaning that there exists
a $Z \succ 0$ such that $c_i = \textrm{trace}(Z F_i)$,
$i=1,\ldots,q$, then both primal and dual optimal values are
attained by some optimal pair $(\bu^\ast,Z^\ast)$.  In that case,
we can characterize such optimal pairs as follows. In view of the
equality constraints of the dual problem, the duality gap can be
expressed as
\begin{eqnarray*}
p^\ast-d^\ast &=& \bc^T\bu^\ast - \textrm{trace}(Z^\ast F_0) \\
&=& - \textrm{trace}(Z^\ast F(\bu^\ast)) .
\end{eqnarray*}
A zero duality gap is equivalent to $\textrm{trace}(Z^\ast
F(\bu^\ast)) = 0$, which in turn is equivalent to $Z^* F(\bu^*) =
O$, where $O$ denotes the zero matrix, since the product of a
positive semidefinite and a negative semidefinite matrix has
zero trace if and only if it is zero.

To summarize, consider the SDP (\ref{eq:primal-SDP}) and its
Lagrange dual (\ref{eq:SDP-dual}). If either problem is strictly
feasible, then they share the same optimal value. If both problems
are strictly feasible, then the optimal values of both problems
are attained and coincide.  In this case, a primal-dual pair
$(\bu^*,Z^*)$ is optimal if and only if
\begin{eqnarray}
& & F(\bu^*) \preceq 0, \nonumber \\
& & Z^* \succeq 0, \nonumber \\
& & c_i = -\textrm{trace}(Z^* F_i), \;\; i=1,\ldots, q,\nonumber \\
& & Z^* F(\bu^*) = O. \nonumber
\end{eqnarray}
The above conditions represent the expression of the general
Karush-Kuhn-Tucker (KKT) conditions in the semidefinite programming
setting.  The first three sets of conditions express that $\bu^*$ and $Z^*$
are feasible for their respective problems; the last condition
expresses a complementarity condition.

For a pair of strictly feasible primal-dual SDPs, solving the
primal minimization problem is equivalent to maximizing the dual
problem and both can thus be considered simultaneously. Algorithms
indeed make use of this relationship and use the duality gap as a
stopping criterion. A general-purpose program such as SeDuMi
\citep{Stu:99} handles those problems efficiently. This code uses
interior-point methods for SDP \citep{NeN:94}; these methods have
a worst-case complexity of $O(q^2p^{2.5})$ for the general problem
(\ref{eq:primal-SDP}).  In practice, problem structure can be
exploited for great computational savings: e.g., when $F(\bu) \in
\mathbb{R}^{p \times p}$ consists of $L$ diagonal blocks of size
$p_i, \ i = 1, \ldots, L$, these methods have a worst-case
complexity of $O(q^2(\sum_{i=1}^L p_i^2) p^{0.5})$ \citep{VaB:96}.

\section{Algorithms for Learning Kernels}\label{sec-algs}

We work in a transduction setting, where some of the data (the
training set $S_{n_{tr}} = \{ (\mathbf{x}_1,y_1), \ldots,
(\mathbf{x}_{n_{tr}}, y_{n_{tr}}) \}$) are labeled, and the
remainder (the test set $T_{n_{t}} = \{ \mathbf{x}_{n_{tr}+1},
\ldots, \mathbf{x}_{n_{tr}+n_t} \}$) are unlabeled, and the aim
is to predict the labels of the test data. In this setting,
optimizing the kernel corresponds to choosing a kernel matrix.
This matrix has the form
\begin{equation}\label{blockstruct}
K = \left(
\begin{array}{cc}
  K_{tr} & K_{tr,t} \\
  K_{tr,t}^T & K_t
\end{array}\right),
\end{equation}
where $K_{ij} = \langle \Phi(\bx_i), \Phi(\bx_j) \rangle$, $i,j =
1, \ldots, n_{tr}, n_{tr} + 1, \ldots, n_{tr}+n_t$. By optimizing
a cost function over the ``training-data block'' $K_{tr}$, we want
to learn the optimal mixed block $K_{tr,t}$ and the optimal
``test-data block'' $K_t$.

This implies that training and test-data blocks must somehow be
entangled: tuning training-data entries in $K$ (to optimize their
embedding) should imply that test-data entries are automatically
tuned in some way as well.  This can be achieved by constraining
the search space of possible kernel matrices: we control the
capacity of the search space of possible kernel matrices in order
to prevent overfitting and achieve good generalization on test
data.

We first consider a general optimization problem in which
the kernel matrix $K$ is restricted to a convex subset
$\calK$ of $\mathcal{P}$, the positive semidefinite cone.
We then consider two specific examples. The first is the set of
positive semidefinite matrices with bounded trace
that can be expressed as a linear combination
of kernel matrices from the set $\{K_1, \ldots, K_m \}$. That is,
$\calK$ is the set of matrices $K$ satisfying
  \begin{align}
    K &= \sum_{i=1}^m \mu_i K_i, \label{constraint} \\
    K & \succeq 0, \notag \\
    \textrm{trace}(K) & \le  c. \notag
  \end{align}
In this
case, the set $\calK$ lies in the intersection of a low-dimensional
linear subspace with the positive semidefinite cone
$\mathcal{P}$. Geometrically this can be viewed as computing all
embeddings (for every $K_i$), in disjoint feature spaces, and then
weighting these. The set $\{K_1,\ldots,K_m\}$ could be a set of
initial ``guesses'' of the kernel matrix, e.g., linear, Gaussian
or polynomial kernels with different kernel parameter values.
Instead of fine-tuning the kernel parameter for a given kernel
using cross-validation, one can now evaluate the given kernel for
a range of kernel parameters and then optimize the weights in the
linear combination of the obtained kernel matrices. Alternatively,
the $K_i$ could be chosen as the rank-one matrices $K_i = \bv_i
\bv_i^T$, with $\bv_i$ a subset of the eigenvectors of $K_0$, an
initial kernel matrix, or with $\bv_i$ some other set of
orthogonal vectors. A practically important form is the case in
which a diverse set of possibly good Gram matrices $K_i$
(similarity measures/representations) has been constructed, e.g.,
using heterogeneous data sources. The challenge is to combine these
measures into one optimal similarity measure (embedding), to be
used for learning.

The second example of a restricted set $\calK$ of kernels is the set
of positive semidefinite matrices with bounded trace
that can be expressed as a linear combination
of kernel matrices from the set $\{K_1, \ldots, K_m\}$,
but with the parameters $\mu_i$ constrained to be non-negative.
That is,
$\calK$ is the set of matrices $K$ satisfying
  \begin{align*}
    K &= \sum_{i=1}^m \mu_i K_i, \\
    \mu_i &\ge 0 \qquad i\in\{1,\ldots,m\} \\
    K & \succeq 0, \\
    \textrm{trace}(K) & \le  c.
  \end{align*}
This further constrains
the class of functions that can be represented.  It has
two advantages: we shall see that the corresponding
optimization problem has significantly reduced
computational complexity, and it is more convenient
for studying the statistical properties of a class of
kernel matrices.

As we will see in Section~\ref{s-bound}, we can estimate the
performance of support vector machines for transduction using
properties of the class $\calK$. As explained in Section
\ref{s-kernels}, we can use a thresholded version of
$f(\mathbf{x})$, i.e., $\sign \left( f(\bx) \right)$, as a binary
classification decision. Using this decision function, we will
prove that the proportion of errors on the test data $T_n$ (where,
for convenience, we suppose that training and test data have the
same size $n_{tr} = n_t = n$) is, with probability $1 - \delta$
(over the random draw of the training set $S_n$ and test set $T_n$),
bounded by
\begin{equation}\label{boundintro}
\frac{1}{n}\sum_{i=1}^{n}\max\left\{1-y_if(\mathbf{x}_i),0\right\} +
\frac{1}{\sqrt{n}}\left(4 + \sqrt{2\log(1/\delta)} +
\sqrt{\frac{\mathcal{C}(\calK)}{n\gamma^2}}\right),
\end{equation}
where $\gamma$ is the $1$-norm soft margin on the data
and $\mathcal{C}(\calK)$ is a certain
measure of the complexity of the kernel class $\calK$. For instance,
for the class $\calK$ of positive linear combinations defined above,
$\mathcal{C}(\calK)\le mc$, where $m$ is the number of kernel matrices
in the combination and $c$ is the bound on the trace.
So, the proportion of errors on the test data is bounded by the average
error on the training set and a complexity term, determined by the
richness of the class $\calK$ and the margin $\gamma$. Good
generalization can thus be expected if the error on the training
set is small, while having a large margin and a class $\calK$
that is not too rich.

The next section presents the main optimization result of the
paper: minimizing a generalized performance measure
$\omega_{C,\tau}(K)$ with respect to the kernel matrix $K$ can be
realized in a semidefinite programming framework. Afterwards, we
prove a second general result showing that minimizing
$\omega_{C,\tau}(K)$ with respect to a kernel matrix $K$,
constrained to the linear subspace $K = \sum_{i=1}^m \mu_i K_i$
with $\bmu \geq 0$, leads to a quadratically constrained quadratic
programming (QCQP) problem. Maximizing the margin of a hard margin
SVM with respect to $K$, as well as both soft margin cases can
then be treated as specific instances of this general result
and will be discussed in later sections.



\subsection{General Optimization Result}\label{ss-sdp-genres}

In this section, we first of all show that minimizing the
generalized performance measure
\begin{equation}\label{gen-perf-measure}
\omega_{C,\tau}(K) = \max_{\ba} \; 2\ba^T\be - \ba^T (G (K) + \tau
I) \ba ~:~ C \geq \ba \geq 0, \;\; \ba^T\by = 0,
\end{equation}
with $\tau \geq 0$, on the training data with respect to the
kernel matrix $K$, in some convex subset $\calK$ of positive
semidefinite matrices with trace equal to $c$,
\begin{equation}\label{eq:orig-gpm}
\min_{K \in\calK} \omega_{C,\tau}(K_{tr}) \qquad \textrm{s.t.} \
\textrm{trace}(K) = c,
\end{equation}
can be realized in a semidefinite programming framework.

We first note a fundamental property of the generalized
performance measure, a property that is crucial for the remainder
of the paper.

\begin{proposition}\label{prop:conv-gen-perf-measure}
The quantity
\begin{eqnarray}
\omega_{C,\tau}(K) = \max_{\ba} \; 2\ba^T\be - \ba^T (G (K) + \tau
I) \ba ~:~ C \geq \ba \geq 0, \;\; \ba^T\by = 0, \nonumber
\end{eqnarray}
is convex in K.
\end{proposition}

This is easily seen by considering first that $2\ba^T\be - \ba^T
(G (K) + \tau I) \ba$ is an affine function of K, and hence is a
convex function as well. Secondly, we notice that
$\omega_{C,\tau}(K)$ is the pointwise maximum of such convex
functions and is thus convex. The constraints $C \geq \ba \geq 0,
\;\; \ba^T\by = 0$ are obviously convex.
% This last statement is illustrated in a discrete case in figure
% \ref{fig:ptwise}. It shows how the pointwise maximum of two
% functions is convex. This can be extended for an infinite set of
% functions, e.g., indexed by $\ba$ in this case.
%
% \begin{figure}[h]
% \begin{center}
% \includegraphics[width=6cm, angle = 0,keepaspectratio=true]{ptwise_fig}
% \caption{\em Given two convex functions $f(x)$ and $g(x)$. Their
% pointwise maximum $\max \{ f(x), g(x) \}$ will also be convex, as
% can easily be seen from the convexity of the shaded area (called
% the epigraph).}\label{fig:ptwise}
% \end{center}
% \end{figure}

Problem (\ref{eq:orig-gpm}) is now a convex optimization problem.
The following theorem shows that, for a suitable choice of the set
$\calK$, this problem can be cast as an SDP.

\begin{theorem}\label{theorem-gpm-1}
Given a labeled sample $S_{n_{tr}} = \{ (\mathbf{x}_1,y_1),
\ldots, (\mathbf{x}_{n_{tr}}, y_{n_{tr}}) \}$ with the
set of labels denoted $\by \in \mathbb{R}^{n_{tr}}$, the kernel matrix $K
\in \calK$ that optimizes (\ref{eq:orig-gpm}), with $\tau \geq 0$,
can be found by solving the following convex optimization problem:
\begin{eqnarray}\label{sdp-gpm}
\min_{K,t,\lambda,\bnu,\bdelta} & & \ t \\
\textrm{subject to} & & \ \textrm{trace}(K) = c, \nonumber \\
& & K \in \calK, \nonumber \\
& & \begin{pmatrix}
G(K_{tr}) + \tau I_{n_{tr}} & \be+\bnu-\bdelta+\lambda \by \\
(\be+\bnu-\bdelta+\lambda \by)^T & t-2C\bdelta^T\be \end{pmatrix} \succeq 0, \nonumber \\
& & \bnu \geq 0, \nonumber \\
& & \bdelta \geq 0. \nonumber
\end{eqnarray}
\end{theorem}

\begin{proof}
We begin by substituting $\omega_{C,\tau}(K_{tr})$, as defined in
(\ref{gen-perf-measure}), into (\ref{eq:orig-gpm}), which yields
\begin{equation}\label{simpelprob}
\min_{K \in\calK} \; \max_{\ba} \; 2\ba^T\be - \ba^T (G (K_{tr}) +
\tau I_{n_{tr}}) \ba ~:~ C \geq \ba \geq 0, \;\; \ba^T\by = 0,
\;\; \textrm{trace}(K) = c,
\end{equation}
with $c$ a constant. Assume that $K_{tr} \succ 0$, hence
$G(K_{tr})\succ 0$ and $G(K_{tr}) + \tau I_{n_{tr}} \succ 0$ since
$\tau \geq 0$ (the following can be extended to the general
semidefinite case). From Proposition
\ref{prop:conv-gen-perf-measure}, we know that
$\omega_{C,\tau}(K_{tr})$ is convex in $K_{tr}$ and thus in $K$.
Given the convex constraints in (\ref{simpelprob}), the
optimization problem is thus certainly convex in $K$. We write
this as
\begin{eqnarray}\label{sdp1}
\min_{K\in\calK, t} t  ~:~ & & t \geq \max_{\ba} \; 2\ba^T\be -
\ba^T (G (K_{tr}) + \tau I_{n_{tr}}) \ba, \\ & & C \geq \ba \geq
0, \;\; \ba^T\by = 0, \;\; \textrm{trace}(K) = c. \nonumber
\end{eqnarray}
We now express the constraint $t \geq \max_{\ba} \; 2\ba^T\be -
\ba^T (G (K_{tr}) + \tau I_{n_{tr}}) \ba$ as an LMI using duality.
In particular, duality will allow us to drop the minimization and
the Schur complement lemma then yields an LMI.

Define the Lagrangian of the maximization problem
(\ref{gen-perf-measure}) by
\[
{\cal L} (\ba,\bnu,\lambda,\bdelta) = 2\ba^T\be - \ba^T (G
(K_{tr}) + \tau I_{n_{tr}}) \ba + 2\bnu^T\ba + 2\lambda \by^T\ba +
2 \bdelta^T (C \be - \ba),
\]
where $\lambda \in \mathbb{R}$ and $\bnu, \bdelta \in
\mathbb{R}^{n_{tr}}$. By duality, we have
\[
\omega_{C,\tau}(K_{tr}) = \max_{\ba} \; \min_{\bnu \geq 0,\bdelta
\geq 0,\lambda} \; {\cal L} (\ba,\bnu,\lambda,\bdelta) =
\min_{\bnu \geq 0,\bdelta \geq 0,\lambda} \; \max_{\ba} \; {\cal
L} (\ba,\bnu,\lambda,\bdelta).
\]
Since $G(K_{tr}) + \tau I_{n_{tr}} \succ 0$, at the optimum we
have
\[
\ba = (G(K_{tr}) + \tau I_{n_{tr}})^{-1}(\be+\bnu-\bdelta+\lambda
\by),
\]
and we can form the dual problem
\[
\omega_{C,\tau}(K_{tr}) = \min_{\bnu, \bdelta, \lambda}  \;
(\be+\bnu-\bdelta+\lambda \by)^T(G(K_{tr}) + \tau
I_{n_{tr}})^{-1}(\be+\bnu-\bdelta+\lambda \by) + 2 C \bdelta^T \be
~:~ \bnu \geq 0, \bdelta \geq 0.
\]
This implies that for any $t > 0$, the constraint
$\omega_{C,\tau}(K_{tr}) \leq t$ holds if and only if there exist
$\bnu \geq 0, \bdelta \geq 0$ and $\lambda$ such that
\[
(\be+\bnu-\bdelta+\lambda \by)^T(G(K_{tr}) + \tau
I_{n_{tr}})^{-1}(\be+\bnu-\bdelta+\lambda \by) + 2 C \bdelta^T \be
\leq t,
\]
or, equivalently (using the Schur complement lemma), such that
\[
\left(
\begin{array}{cc}
  G(K_{tr}) + \tau I_{n_{tr}} & \be+\bnu-\bdelta+\lambda \by \\
  (\be+\bnu-\bdelta+\lambda \by)^T & t - 2 C \bdelta^T \be
\end{array}\right) \succeq 0
\]
holds. Taking this into account, (\ref{sdp1}) can be expressed as
\begin{eqnarray}
\min_{K,t,\lambda,\bnu,\bdelta} & & \ t \nonumber \\
\textrm{subject to} & & \ \textrm{trace}(K) = c, \nonumber \\
& & K \in\calK, \nonumber \\
& & \begin{pmatrix}
G(K_{tr}) + \tau I_{n_{tr}} & \be+\bnu-\bdelta+\lambda \by \\
(\be+\bnu-\bdelta+\lambda \by)^T & t - 2 C \bdelta^T \be \end{pmatrix} \succeq 0, \nonumber \\
& & \bnu \geq 0, \nonumber \\
& & \bdelta \geq 0, \nonumber
\end{eqnarray}
which yields (\ref{sdp-gpm}). Notice that $\bnu \geq 0
\Leftrightarrow \textrm{diag}(\bnu) \succeq 0$, and is thus an
LMI; similarly for $\bdelta \geq 0$.
\end{proof}

Notice that if $\calK=\{K\succeq 0\}$, this optimization problem
is an SDP in the standard form (\ref{genform}). Of course, in that
case there is no constraint to ensure entanglement of training and
test-data blocks.  Indeed, it is easy to see that the criterion
would be optimized with a test matrix $K_t=O$.

Consider the constraint $\calK={\rm
span}\{K_1,\ldots,K_m\}\cap\{K\succeq 0\}$. We obtain the
following convex optimization problem:

\begin{eqnarray}
\min_{K} & & \omega_{C,\tau}(K_{tr}) \label{sdp-gpm-learn} \\
\textrm{subject to} & & \textrm{trace}(K) = c, \nonumber \\ & & K
\succeq 0, \nonumber \\ & & K = \sum_{i=1}^m \mu_i K_i, \nonumber
\end{eqnarray}
which can be written in the standard form of a semidefinite
program, in a manner analogous to (\ref{sdp-gpm}):
\begin{eqnarray}\label{sdp-2}
\min_{\bmu,t,\lambda,\bnu,\bdelta} & &  t \\
\textrm{subject to} & &
\textrm{trace}\left(\sum_{i=1}^m \mu_i K_i\right) = c, \nonumber \\
& & \sum_{i=1}^m \mu_i K_{i} \succeq 0, \nonumber \\
& & \begin{pmatrix}
G(\sum_{i=1}^m \mu_i K_{i,tr}) + \tau I_{n_{tr}} & \be+\bnu-\bdelta+\lambda \by\\
(\be+\bnu-\bdelta+\lambda \by)^T & t - 2 C \bdelta^T \be
\end{pmatrix}
\succeq 0, \nonumber \\
& & \bnu \geq 0, \nonumber \\
& & \bdelta \geq 0. \nonumber
\end{eqnarray}

To solve this general optimization problem, one has to solve a
semidefinite programming problem. General-purpose programs such as
SeDuMi \citep{Stu:99} use interior-point methods to solve SDP
problems \citep{NeN:94}. These methods are polynomial time.
However, applying the complexity results mentioned in Section
\ref{ss-sdpduality} leads to a worst-case complexity
$O{\left((m+n_{tr})^2(n^2+n^2_{tr})(n+n_{tr})^{0.5}\right)}$, or
roughly $O\left((m+n_{tr})^2n^{2.5}\right)$, in this particular
case.

Consider a further restriction on the set of kernel matrices,
where the matrices are restricted to positive linear combinations
of kernel matrices $\{K_1,\ldots,K_m\}\cap\{K\succeq 0\}$:
$$
  K = \sum_{i=1}^m \mu_i K_i, \qquad \bmu \geq 0.
$$

For this restricted linear subspace of the positive semidefinite
cone ${\cal P}$, we can prove the following theorem:

\begin{theorem}\label{theorem-gpm-2}
Given a labeled sample $S_{n_{tr}} = \{ (\mathbf{x}_1,y_1),
\ldots, (\mathbf{x}_{n_{tr}}, y_{n_{tr}}) \}$ with the
set of labels denoted $\by \in \mathbb{R}^{n_{tr}}$, the kernel matrix $K
= \sum_{i=1}^m \mu_i K_i$ that optimizes (\ref{eq:orig-gpm}), with
$\tau \geq 0$, under the additional constraint $\bmu \geq 0$ can
be found by solving the following convex optimization problem, and
considering its dual solution:
\begin{eqnarray}\label{qcqp-gpm}
\max_{\ba, t} & & 2 \ba^T \be - \tau \ba^T \ba - c t
\\ \textrm{subject to} & & t \geq \frac{1}{r_i} \ba^T G(K_{i,tr}) \ba, \ \ i = 1,
\ldots, m \nonumber \\ & & \ba^T \by = 0, \nonumber \\ & & C \geq
\ba \geq 0, \nonumber
\end{eqnarray}
where $\br \in \mathbb{R}^m$ with $\textrm{trace}(K_i) = r_i$.
\end{theorem}


\begin{proof}
Solving problem (\ref{eq:orig-gpm}) subject to $K = \sum_{i=1}^m
\mu_i K_i$, with $K_i \succeq 0$, and the extra constraint $\bmu
\geq 0$ yields
\begin{eqnarray}
\min_{K} \max_{\ba ~:~ C \geq \ba \geq 0, \ba^T \by = 0} & &
2\ba^T\be - \ba^T (G (K_{tr}) + \tau I_{n_{tr}}) \ba \nonumber \\
\textrm{subject to} & & \textrm{trace}(K) = c, \nonumber \\ & & K
\succeq 0, \nonumber \\ & & K = \sum_{i=1}^m \mu_i K_i, \nonumber
\\ & & \bmu \geq 0, \nonumber \nonumber
\end{eqnarray}
when $\omega_{C,\tau}(K_{tr})$ is expressed using
(\ref{gen-perf-measure}). We can omit the second constraint,
because this is implied by the last two constraints, if $K_i
\succeq 0$. The problem then reduces to
\begin{eqnarray}\label{eq:posweights}
\min_{\bmu} \max_{\ba ~:~ C \geq \ba \geq 0, \ba^T \by = 0} & &
2\ba^T\be - \ba^T (G (\sum_{i=1}^m \mu_i K_{i,tr}) + \tau I_{n_{tr}}) \ba \nonumber \\
\textrm{subject to} & & \bmu^T \br = c, \nonumber \\ & & \bmu \geq
0, \nonumber
\end{eqnarray}
where $K_{i,tr} = K_i(1:n_{tr},1:n_{tr})$. We can write this as
\begin{eqnarray}
\lefteqn{\min_{\bmu ~:~ \bmu \geq 0, \bmu^T \br = c} \ \ \max_{\ba
~:~ C \geq \ba \geq 0, \ba^T \by = 0} 2\ba^T\be - \ba^T \left(
\textrm{diag}(\by) ( \sum_{i=1}^m \mu_i K_{i,tr})
\textrm{diag}(\by)  + \tau I_{n_{tr}}\right) \ba} \nonumber
\\ & & = \min_{\bmu ~:~ \bmu \geq 0, \bmu^T \br = c} \ \ \max_{\ba ~:~ C \geq \ba \geq 0,
\ba^T \by = 0} 2\ba^T\be - \sum_{i=1}^m \mu_i \ba^T
\textrm{diag}(\by) K_{i,tr} \textrm{diag}(\by) \ba - \tau \ba^T
\ba \nonumber
\\ & & = \min_{\bmu ~:~ \bmu \geq 0, \bmu^T \br = c} \ \ \max_{\ba ~:~ C \geq \ba \geq 0,
\ba^T \by = 0} 2\ba^T\be - \sum_{i=1}^m \mu_i \ba^T G(K_{i,tr})
\ba - \tau \ba^T \ba \nonumber
\\ & & = \max_{\ba ~:~ C \geq \ba \geq 0,
\ba^T \by = 0} \ \ \min_{\bmu ~:~ \bmu \geq 0, \bmu^T \br = c}
2\ba^T\be - \sum_{i=1}^m \mu_i \ba^T G(K_{i,tr}) \ba - \tau \ba^T
\ba, \nonumber
\end{eqnarray}
with $G(K_{i,tr}) = \textrm{diag}(\by) K_{i,tr}
\textrm{diag}(\by)$. The interchange of the order of the
minimization and the maximization is justified~\citep[see,
e.g.,~][]{BoV:01} because the objective is convex in $\bmu$ (it is
linear in $\bmu$) and concave in $\ba$, because the minimization
problem is strictly feasible in $\bmu$, and the maximization
problem is strictly feasible in $\ba$ (we can skip the case for
all elements of $\by$ having the same sign, because we cannot even
define a margin in such a case). We thus obtain
\begin{eqnarray}
\lefteqn{\max_{\ba ~:~ C \geq \ba \geq 0, \ba^T \by = 0} \ \
\min_{\bmu ~:~ \bmu \geq 0, \bmu^T \br = c} 2\ba^T\be -
\sum_{i=1}^m \mu_i \ba^T G(K_{i,tr}) \ba - \tau \ba^T \ba}
\nonumber
\\ & & = \max_{\ba ~:~ C \geq \ba \geq 0, \ba^T \by = 0} \left[ 2\ba^T \be - \tau \ba^T \ba - \max_{\bmu ~:~ \bmu \geq 0,
\bmu^T \br = c} \left( \sum_{i=1}^m \mu_i \ba^T G(K_{i,tr}) \ba
\right) \right] \nonumber
\\ & & = \max_{\ba ~:~ C \geq \ba \geq 0, \ba^T \by = 0} \left[ 2\ba^T \be - \tau \ba^T \ba -
\max_{i} \left( \frac{c}{r_i} \ba^T G(K_{i,tr}) \ba \right)
\right]. \nonumber
\end{eqnarray}
Finally, this can be reformulated as 
\begin{eqnarray}
\max_{\ba, t} & & 2 \ba^T \be - \tau \ba^T \ba - c t \nonumber
\\ \textrm{subject to} & & t \geq \frac{1}{r_i} \ba^T G(K_{i,tr}) \ba, \ \ i = 1,
\ldots, m \nonumber \\ & & \ba^T \by = 0, \nonumber \\ & & C \geq
\ba \geq 0, \nonumber
\end{eqnarray}
which proves the theorem.
\end{proof}

This convex optimization problem, a QCQP more precisely, is a
special instance of an SOCP (second-order cone programming
problem), which is in turn a special form of SDP~\citep{BoV:01}.
SOCPs can be solved efficiently with programs such as SeDuMi
\citep{Stu:99} or Mosek \citep{AnA:00}. These codes use
interior-point methods \citep{NeN:94} which yield a worst-case
complexity of $O(mn_{tr}^3)$. This implies a major improvement
compared to the worst-case complexity of a general SDP.
Furthermore, the codes simultaneously solve the above problem and
its dual form. They thus return optimal values for the dual
variables as well---this allows us to obtain the optimal weights
$\mu_i$, for $i = 1, \ldots, m$.


\subsection{Hard Margin}\label{ss-sdp-HM}

In this section, we show how maximizing the margin of a hard
margin SVM with respect to the kernel matrix can be realized in
the semidefinite programming framework derived in Theorem
\ref{theorem-gpm-1}.

Inspired by~(\ref{boundintro}), let us try to find the kernel
matrix $K$ in some convex subset $\calK$ of positive semidefinite
matrices for which the corresponding embedding shows maximal
margin on the training data, keeping the trace of $K$ constant:
\begin{equation}\label{eq:orig_HM}
\min_{K \in\calK} \omega(K_{tr}) \qquad \textrm{s.t.} \
\textrm{trace}(K) = c.
\end{equation}

Note that $\omega(K_{tr}) = \omega_{\infty,0}(K_{tr})$. From
Proposition \ref{prop:conv-gen-perf-measure}, we then obtain the
following important result:

\begin{corollary}\label{corol:conv_margin}
The quantity
\begin{eqnarray}
\omega(K) = \max_{\ba} \; 2\ba^T\be - \ba^T G (K) \ba ~:~ \ba \geq
0, \;\; \ba^T\by = 0, \nonumber
\end{eqnarray}
is convex in K.
\end{corollary}

So, a fundamental property of the inverse margin is that it is
convex in $K$. This is essential, since it allows
us to optimize this quantity in a convex framework. The following
theorem shows that, for a suitable choice of the set $\calK$, this
convex optimization problem can be cast as an SDP.

\begin{theorem}
Given a linearly separable labeled sample $S_{n_{tr}} = \{
(\mathbf{x}_1,y_1), \ldots, (\mathbf{x}_{n_{tr}}, y_{n_{tr}}) \}$
with the set of labels denoted $\by \in \mathbb{R}^{n_{tr}}$,
the kernel matrix $K \in \calK$ that optimizes (\ref{eq:orig_HM})
can be found by solving the following problem:
\begin{eqnarray}\label{sdpmargin}
\min_{K,t,\lambda,\bnu} & & \ t \\
\textrm{subject to} & & \ \textrm{trace}(K) = c, \nonumber \\
& & K \in \calK, \nonumber \\
& & \begin{pmatrix}
G(K_{tr}) & \be+\bnu+\lambda \by \\
(\be+\bnu+\lambda \by)^T & t \end{pmatrix} \succeq 0, \nonumber \\
& & \bnu \geq 0. \nonumber
\end{eqnarray}
\end{theorem}

\begin{proof} Observe $\omega(K_{tr}) = \omega_{\infty,0}(K_{tr})$.
Apply Theorem \ref{theorem-gpm-1} for $C = \infty$ and $\tau = 0$.
\end{proof}

If $\calK=\{K\succeq 0\}$, there is no constraint to ensure that a
large margin on the training data will give a large margin on the
test data: a test matrix $K_t=O$ would optimize the criterion.

If we restrict the kernel matrix to a linear subspace $\calK={\rm
span}\{K_1,\ldots,K_m\}\cap\{K\succeq 0\}$, we obtain

\begin{eqnarray}
\min_{K} & & \omega(K_{tr}) \label{sdp-margin-learn} \\
\textrm{subject to} & & \textrm{trace}(K) = c, \nonumber \\ & & K
\succeq 0, \nonumber \\ & & K = \sum_{i=1}^m \mu_i K_i, \nonumber
\end{eqnarray}
which can be written in the standard form of a semidefinite
program, in a manner analogous to (\ref{sdpmargin}):
\begin{eqnarray}\label{sdpmargin2}
\min_{\mu_i,t,\lambda,\bnu} & &  t \\
\textrm{subject to} & &
\textrm{trace}\left(\sum_{i=1}^m \mu_i K_i\right) = c, \nonumber \\
& & \sum_{i=1}^m \mu_i K_{i} \succeq 0, \nonumber \\
& & \begin{pmatrix}
G(\sum_{i=1}^m \mu_i K_{i,tr}) & \be+\bnu+\lambda \by\\
(\be+\bnu+\lambda \by)^T & t
\end{pmatrix}
\succeq 0, \nonumber \\
& & \bnu \geq 0.
 \nonumber
\end{eqnarray}
Notice that the SDP approach is consistent with the bound in
(\ref{boundintro}).  The margin is optimized over the labeled data
(via the use of $K_{i,tr}$), while the positive semidefiniteness
and the trace constraint are imposed for the entire kernel matrix
$K$ (via the use of $K_i$). This leads to a general method for
learning the kernel matrix with semidefinite programming, when
using a margin criterion for hard margin SVMs. Applying the
complexity results mentioned in Section \ref{ss-sdpduality} leads
to a worst-case complexity $O\left((m+n_{tr})^2n^{2.5}\right)$
when using general-purpose interior-point methods to solve this
particular SDP.

Furthermore, this gives a new transduction method for hard margin
SVMs. Whereas Vapnik's original method for transduction scales
exponentially in the number of test samples, the new SDP method
has polynomial time complexity.
%This opens the door to the design of
%special-purpose methods that exploit the particular structure of
%the problem at hand and may result in very efficient algorithms.

\iffalse Furthermore, this gives a new transduction method for
hard margin SVMs (real transduction with rank-one matrices from
eigenvectors in (\ref{constraint}); not fully transduction when
evaluating a kernel function to obtain, but this doesn't seem a
disadvantage). Vapnik's original straightforward transduction
approach scales exponentially in the number of test samples, while
this offers a more practice transduction method. This SDP method
is polynomial time \citep{NeN:94}, and special purpose methods
exploiting the particular structure of the problem at hand should
result in more efficient algorithms. Before giving experimental
results, we provide a fuller investigation of the error bound in
(\ref{boundintro}). \fi


\bigskip

\noindent {\bf Remark.} For the specific case in which the $K_i$
are rank-one matrices $K_i = \bv_i \bv_i^T$, with $\bv_i$
orthonormal (e.g., the normalized eigenvectors of an initial
kernel matrix $K_0$), the semidefinite program reduces to a QCQP:
\begin{eqnarray}
\max_{\ba, t} & & 2\ba^T\be - c t \label{eq:qp-margin}
\\ \textrm{subject to} & & t \geq (\breve{\bv}_i^T \ba)^2, i = 1,
\ldots, m \nonumber \\ & & \ba^T \by = 0, \nonumber \\ & & \ba
\geq 0, \nonumber
\end{eqnarray}
with $\breve{\bv}_i = \textrm{diag}(\by) ~ \bv_i(1:n_{tr})$.

This can be seen by observing that, for $K_i = \bv_i \bv_i^T$,
with $\bv_i^T \bv_j = \delta_{ij}$, we have that $\sum_{i=1}^m
\mu_i K_i \succeq 0$ is equivalent to $\bmu \geq 0$. So, we can
apply Theorem \ref{theorem-gpm-2}, with $\tau = 0$ and $C =
\infty$, where $\frac{1}{r_i} ~ \ba^T ~ G(K_{i,tr}) ~ \ba = \ba^T
\textrm{diag}(\by) ~ \bv_i(1:n_{tr}) ~ \bv_i(1:n_{tr})^T ~
\textrm{diag}(\by) ~ \ba = (\breve{\bv}_i^T \ba)^2$.


\subsection{Hard Margin with Kernel Matrices that are Positive
Linear Combinations}

To learn a kernel matrix from this linear class $\calK$, one has
to solve a semidefinite programming problem: interior-point
methods \citep{NeN:94} are polynomial time, but have a worst-case
complexity $O\left((m+n_{tr})^2n^{2.5}\right)$ in this particular
case.

We now restrict $\calK$ to the positive linear combinations of
kernel matrices:
$$
  K = \sum_{i=1}^m \mu_i K_i, \qquad \bmu \geq 0.
$$
Assuming positive weights yields a smaller set of kernel matrices,
because the weights need not be positive for $K$ to be positive
semidefinite, even if the components $K_i$ are positive
semidefinite. Moreover, the restriction has beneficial
computational effects: (1) the general SDP reduces to a QCQP,
which can be solved with significantly lower complexity
$O(mn_{tr}^3)$; (2) the constraint can result in improved
numerical stability---it prevents the algorithm from using large
weights with opposite sign that cancel. Finally, we shall see in
Section~\ref{s-bound} that the constraint also yields better
estimates of the generalization performance of these algorithms.


\begin{theorem}
Given a labeled sample $S_{n_{tr}} = \{ (\mathbf{x}_1,y_1),
\ldots, (\mathbf{x}_{n_{tr}}, y_{n_{tr}}) \}$ with the
set of labels denoted $\by \in \mathbb{R}^{n_{tr}}$, the kernel matrix $K
= \sum_{i=1}^m \mu_i K_i$ that optimizes (\ref{eq:orig-gpm}), with
$\tau \geq 0$, under the additional constraint $\bmu \geq 0$ can
be found by solving the following convex optimization problem, and
considering its dual solution:
\begin{eqnarray}\label{qcqp-HM}
\max_{\ba, t} & & 2 \ba^T \be - c t \label{eq:socp-hm}
\\ \textrm{subject to} & & t \geq \frac{1}{r_i} \ba^T G(K_{i,tr}) \ba, \ \ i = 1,
\ldots, m \nonumber \\ & & \ba^T \by = 0, \nonumber \\ & & \ba
\geq 0. \nonumber
\end{eqnarray}
where $\br \in \mathbb{R}^m$ with $\textrm{trace}(K_i) = r_i$.
\end{theorem}

\begin{proof}
Apply Theorem \ref{theorem-gpm-2} for $C = \infty$ and $\tau = 0$.
\end{proof}

Note once again that the optimal weights $\mu_i, \ \ i = 1,
\ldots, m$, can be recovered from the primal-dual solution found
by standard software such as SeDuMi \citep{Stu:99} or Mosek
\citep{AnA:00}.

\subsection{1-Norm Soft Margin}\label{ss-sdp-SM1}

For the case of non-linearly separable data, we can consider the
1-norm soft margin cost function in~(\ref{softmargindef1}).
Training the SVM for a given kernel involves minimizing this
quantity with respect to $\mathbf{w}, b$, and $\bxi$, which yields the
optimal value (\ref{dualsoftmargindef1}): obviously this minimum
is a function of the particular choice of $K$, which is expressed
explicitly in (\ref{dualsoftmargindef1}) as a dual problem. Let us
now optimize this quantity with respect to the kernel matrix $K$,
i.e., let us try to find the kernel matrix $K\in\calK$ for which
the corresponding embedding yields minimal $\omega_{S1}(K_{tr})$,
keeping the trace of $K$ constant:
\begin{equation}\label{simpelprob_sm1}
\min_{K\in\calK} \omega_{S1}(K_{tr}) \qquad \textrm{s.t.} \
\textrm{trace}(K) = c.
\end{equation}
This is again a convex optimization problem.

\begin{theorem}\label{th:optSM1}
Given a labeled sample $S_{n_{tr}} = \{ (\mathbf{x}_1,y_1),
\ldots, (\mathbf{x}_{n_{tr}}, y_{n_{tr}}) \}$ with the
set of labels denoted $\by \in \mathbb{R}^{n_{tr}}$, the kernel matrix $K
\in \calK$ that optimizes (\ref{simpelprob_sm1}), can be found by
solving the following convex optimization problem:
\begin{eqnarray}\label{sdpsoftmargin1}
\min_{K,t,\lambda,\bnu,\bdelta} & & \ t \\
\textrm{subject to} & & \ \textrm{trace}(K) = c, \nonumber \\
& & K \in\calK, \nonumber \\
& & \begin{pmatrix}
G(K_{tr}) & \be+\bnu-\bdelta+\lambda \by \\
(\be+\bnu-\bdelta+\lambda \by)^T & t - 2 C
\bdelta^T \be \end{pmatrix} \succeq 0, \nonumber \\
& & \bnu \geq 0, \nonumber \\
& & \bdelta \geq 0. \nonumber
\end{eqnarray}
\end{theorem}

\begin{proof}
Observe $\omega_{S1}(K_{tr}) = \omega_{C,0}(K_{tr})$. Apply
Theorem \ref{theorem-gpm-1} for $\tau = 0$.
\end{proof}

Again, if $\calK=\{K\succeq 0\}$, this is an SDP. Adding the
additional constraint~(\ref{constraint}) that $K$ is a linear
combination of fixed kernel matrices leads to the following SDP:
\begin{eqnarray}
\min_{\mu_i,t,\lambda,\bnu,\bdelta} & &  t \label{sdpsoftmargin1_2} \\
\textrm{subject to} & &
\textrm{trace}\left(\sum_{i=1}^m \mu_i K_i\right) = c, \nonumber \\
& & \sum_{i=1}^m \mu_i K_{i} \succeq 0, \nonumber \\
& & \begin{pmatrix}
G(\sum_{i=1}^m \mu_i K_{i,tr}) & \be+\bnu-\bdelta+\lambda \by\\
(\be+\bnu-\bdelta+\lambda \by)^T & t - 2 C \bdelta^T \be
\end{pmatrix}
\succeq 0, \nonumber \\
& & \bnu, \bdelta \geq 0.
 \nonumber
\end{eqnarray}


\bigskip

\noindent {\bf Remark.} For the specific case in which the $K_i$
are rank-one matrices $K_i = \bv_i \bv_i^T$, with $\bv_i$
orthonormal (e.g., the normalized eigenvectors of an initial
kernel matrix $K_0$), the SDP reduces to a QCQP using Theorem
\ref{theorem-gpm-2}, with $\tau = 0$, in a manner analogous to the
hard margin case:
\begin{eqnarray}
\max_{\ba, t} & & 2\ba^T\be - c t \label{eq:qp-margin-sm1}
\\ \textrm{subject to} & & t \geq (\breve{\bv}_i^T \ba)^2, i = 1,
\ldots, m \nonumber \\ & & \ba^T \by = 0, \nonumber \\ & & C \geq
\ba \geq 0, \nonumber
\end{eqnarray}
with $\breve{\bv}_i = \textrm{diag}(\by) ~ \bv_i(1:n_{tr})$.

Solving the original learning problem subject to the extra
constraint $\bmu \geq 0$ yields, after applying Theorem
\ref{theorem-gpm-2}, with $\tau = 0$:
\begin{eqnarray}
\max_{\ba, t} & & 2 \ba^T \be - c t \label{eq:socp_SM1}
\\ \textrm{subject to} & & t \geq \frac{1}{r_i} \ba^T G(K_{i,tr}) \ba, \ \ i = 1,
\ldots, m \nonumber \\ & & \ba^T \by = 0, \nonumber \\ & & C \geq
\ba \geq 0. \nonumber
\end{eqnarray}


\subsection{2-Norm Soft Margin}\label{ss-sdp-SM2}

For the case of non-linearly separable data, we can also consider
the 2-norm soft margin cost function~(\ref{softmargindef2}).
Again, training for a given kernel will minimize this quantity
with respect to $\mathbf{w}, b$, and $\bxi$ and the minimum is a
function of the particular choice of $K$, as expressed in
(\ref{dualsoftmargindef2}) in dual form. Let us now optimize this
quantity with respect to the kernel matrix $K$:
\begin{equation}\label{simpelprob_sm2}
\min_{K \in\calK} \omega_{S2}(K_{tr}) \qquad \textrm{s.t.} \
\textrm{trace}(K) = c.
\end{equation}
This is again a convex optimization problem, and can be restated
as follows.

\begin{theorem}\label{th:optSM2}
Given a labeled sample $S_{n_{tr}} = \{ (\mathbf{x}_1,y_1),
\ldots, (\mathbf{x}_{n_{tr}}, y_{n_{tr}}) \}$ with the
set of labels denoted $\by \in \mathbb{R}^{n_{tr}}$, the kernel matrix $K
\in \calK$ that optimizes~(\ref{simpelprob_sm2}) can be found by
solving the following optimization problem:
\begin{eqnarray}\label{sdpsoftmargin2}
\min_{K,t,\lambda,\bnu} & & \ t \\
\textrm{subject to} & & \ \textrm{trace}(K) = c, \nonumber \\
& & K \in\calK, \nonumber \\
& & \begin{pmatrix}
G(K_{tr})+\frac{1}{C}I_{n_{tr}} & \be+\bnu+\lambda \by \\
(\be+\bnu+\lambda \by)^T & t \end{pmatrix} \succeq 0, \nonumber \\
& & \bnu \geq 0. \nonumber
\end{eqnarray}
\end{theorem}

\begin{proof}
Observe $\omega_{S2}(K_{tr}) = \omega_{\infty,\tau}(K_{tr})$.
Apply Theorem \ref{theorem-gpm-1} for $C = \infty$.
\end{proof}

Again, if $\calK=\{K\succeq 0\}$, this is an SDP. Moreover,
constraining $K$ to be a linear combination of fixed kernel
matrices, we obtain
\begin{eqnarray}
\min_{\mu_i,t,\lambda,\bnu} & &  t \label{sdpsoftmargin2_2} \\
\textrm{subject to} & &
\textrm{trace}\left(\sum_{i=1}^m \mu_i K_i\right) = c, \nonumber \\
& & \sum_{i=1}^m \mu_i K_{i} \succeq 0, \nonumber \\
& & \begin{pmatrix}
G(\sum_{i=1}^m \mu_i K_{i,tr}) + \frac{1}{C} I_{n_{tr}}& \be+\bnu+\lambda \by\\
& & \\
(\be+\bnu+\lambda \by)^T & t
\end{pmatrix}
\succeq 0, \nonumber \\
& & \bnu \geq 0.
 \nonumber
\end{eqnarray}

Also, when the $K_i$ are rank-one matrices, $K_i = \bv_i \bv_i^T$,
with $\bv_i$ orthonormal, we obtain a QCQP:
\begin{eqnarray}
\max_{\ba, t} & & 2\ba^T\be - \frac{1}{C}\ba^T\ba - c t
\label{eq:qp-margin-sm2}
\\ \textrm{subject to} & & t \geq (\breve{\bv}_i^T \ba)^2, i = 1,
\ldots, m \nonumber \\ & & \ba^T \by = 0, \nonumber \\ & & \ba
\geq 0, \nonumber
\end{eqnarray}
and, finally, imposing the constraint $\bmu \geq 0$ yields
\begin{eqnarray}
\max_{\ba, t} & & 2 \ba^T \be - \frac{1}{C} \ba^T \ba - c t
\label{eq:socp_SM2}
\\ \textrm{subject to} & & t \geq \frac{1}{r_i} \ba^T G(K_{i,tr}) \ba, \ \ i = 1,
\ldots, m \nonumber \\ & & \ba^T \by = 0, \nonumber \\ & & \ba
\geq 0, \nonumber
\end{eqnarray}
following a similar derivation as before: apply Theorem
\ref{theorem-gpm-2} with $C = \infty$, and, for
(\ref{eq:qp-margin-sm2}), observe that $\bmu \geq 0$ is equivalent
to $\sum_{i=1}^m \mu_i K_i \succeq 0$ if $K_i = \bv_i \bv_i^T$ and
$\bv_i^T \bv_j = \delta_{ij}$.

\subsection{Learning the 2-Norm Soft Margin Parameter $\tau =
1/C$}\label{sss-learning-2normSMpar}

This section shows how the 2-norm soft margin parameter of SVMs
can be learned using SDP or QCQP. More details can be found in
\cite{DLC:03}.

In the previous section, we tried to find the kernel matrix $K \in
\mathcal{K}$ for which the corresponding embedding yields minimal
$\omega_{S2}(K_{tr})$, keeping the trace of $K$ constant. Since in
the dual formulation (\ref{dualsoftmargindef2}) the identity matrix
induced by the 2-norm formulation appears in exactly the same way
as the other matrices $K_i$, we can treat it on the same basis and
optimize its weight to obtain the optimal dual formulation, i.e.,
to minimize $\omega_{S2}(K_{tr})$. Since this weight now happens to
correspond to the parameter $\tau = 1/C$, optimizing it
corresponds to learning the 2-norm soft margin parameter and thus
has a significant meaning.

Since the parameter $\tau = 1/C$ can be treated in the same way as
the weights $\mu_i$, tuning it such that the quantity
$\omega_{S2}(K_{tr},\tau)$ is minimized can be viewed as a method
for choosing $\tau$. First of all, consider the dual formulation
(\ref{dualsoftmargindef2}) and notice that
$\omega_{S2}(K_{tr},\tau)$ is convex in $\tau = 1/C$ (being the
pointwise maximum of affine and thus convex functions in $\tau$).
Secondly, since $\tau \rightarrow \infty$ leads to
$\omega_{S2}(K_{tr},\tau) \rightarrow 0$, we impose the constraint
$\textrm{trace}\left(K + \tau I_n \right) = c$. This results in
the following convex optimization problem:
\begin{equation*}
\min_{K \in\calK, \tau \geq 0} \omega_{S2}(K_{tr},\tau) \qquad
\textrm{s.t.} \ \textrm{trace}\left(K + \tau I_n \right) = c.
\end{equation*}
According to Theorem \ref{th:optSM2}, this can be restated as
follows:
\begin{eqnarray}
\min_{K,t,\lambda,\bnu,\tau} & & \ t \\
\textrm{subject to} & & \ \textrm{trace}\left(K + \tau I_n \right)  = c, \nonumber \\
& & K \in\calK, \nonumber \\
& & \begin{pmatrix}
G(K_{tr})+\tau I_{n_{tr}} & \be+\bnu+\lambda \by \\
(\be+\bnu+\lambda \by)^T & t \end{pmatrix} \succeq 0, \nonumber \\
& & \bnu, \tau \geq 0. \nonumber
\end{eqnarray}

Again, if $\calK=\{K\succeq 0\}$, this is an SDP.  Imposing the
additional constraint that $K$ is a linear function of fixed kernel
matrices, we obtain the SDP
\begin{eqnarray}
\min_{\mu_i,t,\lambda,\bnu,\tau} & &  t \label{eq:sdp-sm2-tau} \\
\textrm{subject to} & &
\textrm{trace}\left(\sum_{i=1}^m \mu_i K_i + \tau I_n\right) = c, \nonumber \\
& & \sum_{i=1}^m \mu_i K_{i} \succeq 0, \nonumber \\
& & \begin{pmatrix}
G(\sum_{i=1}^m \mu_i K_{i,tr}) + \tau I_{n_{tr}}& \be+\bnu+\lambda \by\\
& & \\
(\be+\bnu+\lambda \by)^T & t
\end{pmatrix}
\succeq 0, \nonumber \\
& & \bnu, \tau \geq 0,
 \nonumber
\end{eqnarray}
and imposing the additional constraint that the $K_i$ are rank-one
matrices, we obtain a QCQP:
\begin{eqnarray}
\max_{\ba, t} & & 2\ba^T\be - c t \label{eq:qp-sm2-tau}
\\ \textrm{subject to} & & t \geq (\breve{\bv}_i^T \ba)^2, i = 1,
\ldots, m \nonumber \\ & & t \geq \frac{1}{n} \ba^T \ba \nonumber \\
& & \ba^T \by = 0, \nonumber \\ & & \ba \geq 0, \nonumber
\end{eqnarray}
with $\breve{\bv}_i = \textrm{diag}(\by) ~ \bar{\bv}_i=
\textrm{diag}(\by) ~ \bv_i(1:n_{tr})$. Finally, imposing the
constraint that $\bmu \geq 0$ yields the following:
\begin{eqnarray}
\max_{\ba, t} & & 2 \ba^T \be - c t \label{eq:socp-sm2-tau}
\\ \textrm{subject to} & & t \geq \frac{1}{r_i} \ba^T G(K_{i,tr}) \ba, \ \ i = 1,
\ldots, m \nonumber \\ & & t \geq \frac{1}{n} \ba^T \ba \\ & &
\ba^T \by = 0, \nonumber \\ & & \ba \geq 0, \nonumber
\end{eqnarray}
which, as before, is a QCQP.

Solving (\ref{eq:socp-sm2-tau}) corresponds to learning the kernel
matrix as a positive linear combination of kernel matrices
according to a 2-norm soft margin criterion and simultaneously
learning the 2-norm soft margin parameter $\tau = 1/C$. Comparing
(\ref{eq:socp-sm2-tau}) with (\ref{eq:socp-hm}), we can see that
this reduces to learning an augmented kernel matrix $K'$ as a
positive linear combination of kernel matrices and the identity
matrix, $K' = K + \tau I_n = \sum_{i=1}^m \mu_i K_i + \tau I_n$,
using a hard margin criterion. However, there is an important
difference: when evaluating the resulting classifier, the actual
kernel matrix $K$ is used, instead of the augmented $K'$
\citep[see, for example,][]{ShC:99}.

For $m = 1$, we notice that (\ref{eq:sdp-sm2-tau}) directly
reduces to (\ref{eq:socp-sm2-tau}) if $K_1 \succeq 0$. This
corresponds to automatically tuning the parameter $\tau = 1/C$ for
a 2-norm soft margin SVM with kernel matrix $K_1$. So, even when
not learning the kernel matrix, this approach can be used to tune
the 2-norm soft margin parameter $\tau = 1/C$ automatically.



\subsection{Alignment}\label{ss-SDP-alignment}

In this section, we consider the problem of optimizing the
alignment between a set of labels and a kernel matrix from some
class $\calK$ of positive semidefinite kernel matrices. We show
that, if $\calK$ is a class of linear combinations of fixed kernel
matrices, this problem can be cast as an SDP.  This result
generalizes the approach presented in~\cite{CKE:01,CSE:02}.

\begin{theorem}
The kernel matrix $K \in \calK$ which is maximally aligned with
the set of labels $\by \in \mathbb{R}^{n_{tr}}$ can be found by
solving the following optimization problem:
\begin{eqnarray}
\max_{A,K} & & \langle
    K_{tr},\by\by^T\rangle_{F} \label{eq:sdp-optim-align} \\
\textrm{subject to} & & \textrm{trace}(A) \leq 1 \nonumber \\
& & \begin{pmatrix}
  A & K^T \\
  K & I_n  \\
  \end{pmatrix}
\succeq 0 \nonumber \\
& & K\in\calK, \nonumber
\end{eqnarray}
where $I_n$ is the identity matrix of dimension $n$.
\end{theorem}

\begin{proof}
We want to find the kernel matrix $K$
which is maximally aligned with the set of labels $\by$:
\begin{eqnarray}
\max_{K} & & \hat{A}(S,K_{tr},\by\by^T) \nonumber \\
\textrm{subject to} & & K\in\calK, \ \textrm{trace}(K)=1. \nonumber
\end{eqnarray}
This is equivalent to the following optimization problem:
\begin{eqnarray}
\max_{K} & & \langle
    K_{tr},\by\by^T\rangle_{F} \label{eq:sdp-alignment-1} \\
\textrm{subject to} & & \langle
    K,K \rangle_{F} = 1 \nonumber \\
& & K\in\calK, \ \textrm{trace}(K)=1. \nonumber
\end{eqnarray}
To express this in the standard form (\ref{genform}) of a
semidefinite program, we need to express the quadratic equality
constraint $\langle K,K \rangle_{F} = 1$ as an LMI. First,
notice that (\ref{eq:sdp-alignment-1}) is equivalent to
\begin{eqnarray}
\max_{K} & & \langle
    K_{tr},\by\by^T\rangle_{F} \label{eq:sdp-alignment-newconstr} \\
\textrm{subject to} & & \langle K,K \rangle_{F} \leq 1 \nonumber \\
& & K\in\calK. \nonumber
\end{eqnarray}
Indeed, we are maximizing an objective which is linear in the
entries of $K$, so at the optimum $K = K^*$, the constraint
$\langle K,K \rangle_{F} = \textrm{trace}(K^T K) \leq 1$ is
achieved: $\langle K^*,K^* \rangle_{F} = 1$. The quadratic inequality
constraint in~(\ref{eq:sdp-alignment-newconstr}) is now equivalent
to
$$
  \exists A ~:~ K^T K \preceq A \quad \textrm{and} \quad
  \textrm{trace}(A) \leq 1.
$$
Indeed, $A - K^T K \succeq
0 $ implies $\textrm{trace}(A - K^T K) = \textrm{trace}(A) -
\textrm{trace}(K^T K) \geq 0$ because of linearity of the trace.
Using the Schur complement lemma,
we can express $A - K^T K \succeq 0$ as an LMI:
$$ A - K^T K \succeq 0 \Leftrightarrow \begin{pmatrix}
  A & K^T \\
  K & I_n  \\
  \end{pmatrix}
\succeq 0.$$ We can thus rewrite the optimization problem
(\ref{eq:sdp-alignment-1}) as
\begin{eqnarray}
\max_{A,K} & & \langle
    K_{tr},\by\by^T\rangle_{F} \nonumber \\
\textrm{subject to} & & \textrm{trace}(A) \leq 1 \nonumber \\
& & \begin{pmatrix}
  A & K^T \\
  K & I_n  \\
  \end{pmatrix}
\succeq 0 \nonumber \\
& & K\in\calK, \nonumber
\end{eqnarray}
which corresponds to~(\ref{eq:sdp-optim-align}).
\end{proof}

Notice that, when $\calK$ is the set of all positive semidefinite
matrices, this is an SDP (an inequality constraint corresponds to
a one-dimensional LMI; consider the entries of the matrices $A$
and $K$ as the unknowns, corresponding to the $u_i$ in
(\ref{genform})). In that case, one solution
of~(\ref{eq:sdp-optim-align}) is found by simply selecting $K_{tr}
= \frac{c}{n} \by \by^T$, for which the
alignment~(\ref{eq:def_align_2}) is equal to one and thus
maximized.

Adding the additional constraint~(\ref{constraint}) that $K$ is a
linear combination of fixed kernel matrices leads to
\begin{eqnarray}
\max_{K} & & \left\langle K_{tr},\by\by^T \right\rangle_{F} \label{sdp-align-learn} \\
\textrm{subject to} & & \left\langle K, K \right\rangle_{F} \leq 1, \nonumber \\
& & K\succeq 0, \nonumber \\ & & K = \sum_{i=1}^m \mu_i K_i,
\nonumber
\end{eqnarray}
which can be written in the standard form of a semidefinite
program, in a similar way as for (\ref{eq:sdp-optim-align}):
\begin{eqnarray}\label{sdpalignment2}
\max_{A,\mu_i} & & \left\langle
    \sum_{i=1}^m \mu_i K_{i,tr},\by\by^T \right\rangle_{F} \\
\textrm{subject to} & & \textrm{trace}(A) \leq 1, \nonumber \\ & &
\begin{pmatrix}
A & \sum_{i=1}^m \mu_i K_i^T \\
  \sum_{i=1}^m \mu_i K_i & I_n \end{pmatrix}
\succeq 0, \nonumber \\
& & \sum_{i=1}^m \mu_i K_{i} \succeq 0. \nonumber
\end{eqnarray}

\bigskip

\noindent {\bf Remark.} For the specific case where the $K_i$ are
rank-one matrices $K_i = \bv_i \bv_i^T$, with $\bv_i$ orthonormal
(e.g., the normalized eigenvectors of an initial kernel matrix
$K_0$), the semidefinite program reduces to a QCQP (see
Appendix~\ref{app-qp-align}):
\begin{eqnarray}
\max_{\mu_i} & &  \sum_{i=1}^m \mu_i (\bar{\bv}_i^T \by)^2 \label{eq:qp-align} \\
\textrm{subject to} & & \sum_{i=1}^m \mu_i^2 \leq 1 \nonumber \\
& & \mu_i \geq 0, i=1, \ldots, m \nonumber
\end{eqnarray}
with $\bar{\bv}_i = \bv_i(1:n_{tr})$. This corresponds exactly to
the QCQP obtained as an illustration in \cite{CSE:02}, which is
thus entirely captured by the general SDP result obtained in this
section.

Solving the original learning problem~(\ref{sdp-align-learn})
subject to the extra constraint $\bmu \geq 0$ yields
\begin{eqnarray}
\max_{K} & & \left\langle K_{tr},\by\by^T \right\rangle_{F} \nonumber \\
\textrm{subject to} & & \left\langle K, K \right\rangle_{F} \leq 1, \nonumber \\
& & K\succeq 0, \nonumber \\ & & K = \sum_{i=1}^m \mu_i K_i,
\nonumber \\ & & \bmu \geq 0. \nonumber
\end{eqnarray}
We can omit the second constraint, because this is implied by the
last two constraints, if $K_i \succeq 0$. This reduces to
\begin{eqnarray}
\max_{\bmu} & & \left\langle \sum_{i=1}^m \mu_i K_{i,tr},\by\by^T \right\rangle_{F} \nonumber \\
\textrm{subject to} & & \left\langle \sum_{i=1}^m \mu_i K_i, \sum_{j=1}^m \mu_j K_j \right\rangle_{F} \leq 1, \nonumber \\
& & \bmu \geq 0, \nonumber
\end{eqnarray}
where $K_{i,tr} = K_i(1:n_{tr},1:n_{tr})$. Expanding this further
yields
\begin{eqnarray}
\left\langle \sum_{i=1}^m \mu_i K_{i,tr},\by\by^T
\right\rangle_{F} & = & \sum_{i=1}^m \mu_i \left\langle
K_{i,tr},\by\by^T \right\rangle_{F} \nonumber \\ & = & \bmu^T \bq, \\
\left\langle \sum_{i=1}^m \mu_i K_i, \sum_{j=1}^m \mu_j K_j
\right\rangle_{F} & = & \sum_{i,j=1}^m \mu_i \mu_j \left\langle
K_i, K_j \right\rangle_{F} \nonumber \\ & & = \bmu^T S \bmu
\end{eqnarray}
with $q_i = \left\langle K_{i,tr},\by\by^T \right\rangle_{F} =
\textrm{trace} (K_{i,tr} \by \by^T) = \textrm{trace} (\by^T
K_{i,tr} \by) = \by^T K_{i,tr} \by$ and $S_{ij} = \left\langle
K_i, K_j \right\rangle_{F}$, where $\bq \in \mathbb{R}^m, S \in
\mathbb{R}^{m \times m}$. We used the fact that $\textrm{trace}
(ABC) = \textrm{trace} (BCA)$ (if the products are well-defined).
We obtain the following learning problem:
\begin{eqnarray}
\max_{\bmu} & &  \bmu^T \bq \nonumber \\
\textrm{subject to} & & \bmu^T S \bmu \leq 1, \nonumber \\
& & \bmu \geq 0, \nonumber
\end{eqnarray}
which is a QCQP.

\subsection{Induction}


%The previous Subsections consider a transduction setting, where
%some of the data (the training set) is labeled, and the remainder
%of the test data. So, we are given a finite set of points
%beforehand. Their embedding is completely specified by the Gram
%matrix. Learning the kernel in this setting corresponds to
%choosing a kernel matrix. Of course, this assumes the test data is
%known beforehand. There are quite some cases in which this is a
%reasonable assumption: e.g., gene function prediction, where the
%genes are known beforehand, but only for part of them we know the
%function.

In previous sections we have considered the transduction setting,
where it is assumed that the covariate vectors for both training
(labeled) and test (unlabeled) data are known beforehand. While
this setting captures many realistic learning problems, it is also
of interest to consider possible extensions of our approach to the
more general setting of induction, in which the covariates are
known beforehand only for the training data.

Consider the following situation. We learn the kernel matrix as a
positive linear combination of normalized kernel matrices $K_i$.
Those $K_i$ are obtained through the evaluation of a kernel
function or through a known procedure (e.g., a string-matching
kernel), yielding $K_i \succeq 0$. So, $K = \sum_{i=1}^m \mu_i K_i
\succeq 0$. Normalization is done by replacing $K_i(k,l)$ by
$K_i(k,l)/\sqrt{K_i(k,k) \cdot K_i(l,l)}$. In this case, the
extension to an induction setting is elegant and simple.

Let $n_{tr}$ be the number of training data points (all labeled).
Consider the transduction problem for those $n_{tr}$ data points
and one unknown test point, e.g., for a hard margin SVM. The optimal
weights $\mu^*_i, \ \ i=1,\ldots,m$ are learned by solving
(\ref{eq:socp-hm}):
\begin{eqnarray}
\max_{\ba, t} & & 2 \ba^T \be - c t
\label{opt:induction_extension}
\\ \textrm{subject to} & & t \geq \frac{1}{n_{tr} + 1} \ba^T G(K_{i,tr}) \ba, \ \ i = 1,
\ldots, m \nonumber \\ & & \ba^T \by = 0, \nonumber \\ & & \ba
\geq 0. \nonumber
\end{eqnarray}
Even without knowing the test point and the entries of the $K_i$'s
related to it (column and row $n_{tr} + 1$), we know that
$K(n_{tr}+1,n_{tr}+1)=1$ because of the normalization. So,
$\textrm{trace}(K_i) = n_{tr} + 1$. This allows solving for the
optimal weights $\mu^*_i, \ \ i=1,\ldots,m$ and the optimal SVM
parameters $\alpha^*_j, \ \ j=1,\ldots,n_{tr}$ and $b^*$, without
knowing the test point. When a test point becomes available, we
complete the $K_i$'s by computing their $(n_{tr}+1)$-th column and
row (evaluate the kernel function or follow the procedure and
normalize). Combining those $K_i$ with weights $\mu^*_i$ yields
the final kernel matrix $K$, which can then be used to label the
test point:
$$ y = \textrm{sign}(\sum_{i=1}^m \sum_{j=1}^{n_{tr}} \mu^*_i
\alpha_j K_i(x_j,x)).$$


{\bf Remark:} The optimal weights are independent of the number of
unknown test points that are considered in this setting. Consider
the transduction problem (\ref{opt:induction_extension}) for $l$
unknown test points instead of one unknown test point:
\begin{eqnarray}
\max_{\tilde{\ba}, \tilde{t}} & & 2 \tilde{\ba}^T \be - c
\tilde{t} \label{opt:induction_extension_x}
\\ \textrm{subject to} & & \tilde{t} \geq \frac{1}{n_{tr} + l} \tilde{\ba}^T G(K_{i,tr}) \tilde{\ba}, \ \ i = 1,
\ldots, m \nonumber \\ & & \tilde{\ba}^T \by = 0, \nonumber \\ & &
\tilde{\ba} \geq 0. \nonumber
\end{eqnarray}
One can see that solving (\ref{opt:induction_extension_x}) is
equivalent to solving (\ref{opt:induction_extension}) where the
optimal values relate as $\tilde{\ba}^* =
\frac{n_{tr}+l}{n_{tr}+1} \ba^*$ and $\tilde{t}^* =
\frac{n_{tr}+l}{n_{tr}+1} t^*$ and where the optimal weights
$\mu^*_i, \ \ i=1,\ldots,m$ are the same.

Tackling the induction problem in full generality remains a challenge
for future work. Obviously, one could consider the transduction
case with zero test points, yielding the induction case. If the
weights $\mu_i$ are constrained to be nonnegative and furthermore
the matrices $K_i$ are guaranteed to be positive semidefinite,
the weights can be reused at new test points. To deal with
induction in a general SDP setting, one could solve a transduction
problem for each new test point. For every test point, this leads
to solving an SDP of dimension $n_{tr} + 1$, which is
computationally expensive.  Clearly there is a need to explore
recursive solutions to the SDP problem that allow the solution of
the SDP of dimension $n_{tr}$ to be used in the solution of an SDP
of dimension $n_{tr} + 1$.  Such solutions would of course also
have immediate applications to on-line learning problems.

\section{Error Bounds for Transduction}\label{s-bound}

In the problem of transduction, we have access to the
unlabeled test data, as well as the labeled training data,
and the aim is to optimize accuracy in predicting the
test data. We assume that the data are fixed, and that
the order is chosen randomly, yielding a random partition
into a labeled training set and an unlabeled test set. For
convenience, we suppose here that the training and test
sets have the same size. Of course, if we can show a
performance guarantee that holds with high probability over
uniformly chosen training/test partitions of this kind,
it also holds with high probability over an i.i.d.\ choice of
the training and test data, since permuting an i.i.d.\ sample
leaves the distribution unchanged.

The following theorem gives an upper bound on the error of a
kernel classifier on the test data in terms of the average over
the training data of a certain margin cost function, together with
properties of the kernel matrix. We focus on the 1-norm soft
margin classifier, although our results extend in a
straightforward way to other cases, including the 2-norm soft
margin classifier.  The 1-norm soft margin classifier chooses a
kernel classifier $f$ to minimize a weighted combination of a
regularization term, $\|\bw\|^2$, and the average over the
training sample of the slack variables,
  \[
    \xi_i = \max\left(1-y_if(x_i),0\right).
  \]
We can view this regularized empirical criterion as the Lagrangian
for the constrained minimization of
  \[
    \frac{1}{n}\sum_{i=1}^n \xi_i =
    \frac{1}{n}\sum_{i=1}^n \max(1-y_if(x_i),0)
  \]
subject to the upper bound $\|\bw\|^2\le 1/\gamma^2$.

Fix a sequence of $2n$ pairs
$(\mathbf{X}_1,Y_1),\ldots,(\mathbf{X}_{2n},Y_{2n})$ from ${\cal
X}\times{\cal Y}$. Let $\pi:\{1,\ldots,2n\}\to\{1,\ldots,2n\}$ be
a random permutation, chosen uniformly, and let
$(\mathbf{x}_i,y_i)=(\mathbf{X}_{\pi(i)},Y_{\pi(i)})$. The first half of
this randomly ordered sequence is the training data
$T_n=((\mathbf{x}_1,y_1),\ldots,(\mathbf{x}_n,y_n))$, and the
second half is the test data
$S_n=((\mathbf{x}_{n+1},y_{n+1}),\ldots,(\mathbf{x}_{2n},y_{2n}))$.
For a function $f:{\cal
X}\to\mathbb{R}$, the proportion of errors on the test
data of a thresholded version of $f$ can be written as
  $$
    \mbox{\rm er}(f) = \frac{1}{n}|\{n+1 \leq i \leq 2n:
    y_if(\mathbf{x}_i)\le 0\}|.
  $$

We consider kernel classifiers obtained by thresholding
kernel expansions of the form
  \begin{equation}\label{eq:fdef}
    f(\bx) = \langle \mathbf{w},\Phi (\mathbf{x})\rangle =
      \sum_{i=1}^{2n}\alpha_i k(\mathbf{x}_i,\mathbf{x}),
  \end{equation}
where $\mathbf{w} = \sum_{i=1}^{2n}\alpha_i \Phi(\mathbf{x}_i)$ is
chosen with bounded norm,
  \begin{equation}
    \|\mathbf{w}\|^2 = \sum_{i,j=1}^{2n}\alpha_i\alpha_j k(\mathbf{x}_i,\mathbf{x}_j)
     = \ba^T K \ba
     \le \frac{1}{\gamma^2},\label{eq:wbound}
  \end{equation}
and $K$ is the $2n\times 2n$ kernel matrix with
$K_{ij}=k(\mathbf{x}_i,\mathbf{x}_j)$.

    \iffalse
    With this constraint, the value of the
    margin $yf(\mathbf{x})$ is the distance in feature space between
    $\Phi(\mathbf{x})$ and the decision boundary. Notice that
    $\mathbf{w}^h$, the $\mathbf{w}$ here, corresponds to the
    normalized version of $\mathbf{w}^t$, the optimal $\mathbf{w}$ in
    (\ref{softmargindef1}): $\mathbf{w}^h = \mathbf{w}^t /
    ||\mathbf{w}^t||_2 = \gamma \mathbf{w}^t$. Assuming $b=0$ for
    simplicity (though without loss of generality), one can see
    $$
        \xi_i = \left\{ \begin{array}{lll}
          0 & = \phi_\gamma(y_if(\mathbf{x}_i)) & \mbox{if $y_if(\mathbf{x}_i) = y_i \langle \mathbf{w}^h, \Phi(\mathbf{x}_i) \rangle = \gamma y_i \langle \mathbf{w}^t, \Phi(\mathbf{x}_i) \rangle > \gamma$,}\\
          1-y_i \langle \mathbf{w}^t, \Phi(\mathbf{x}_i) \rangle & = 1-y_i \langle \mathbf{w}^h, \Phi(\mathbf{x}_i) \rangle/\gamma
          & \\ & = \phi_\gamma(y_if(\mathbf{x}_i)) & 0<y_if(\mathbf{x}_i)\le \gamma,\\
          1-y_i \langle \mathbf{w}^t, \Phi(\mathbf{x}_i) \rangle & \geq \phi_\gamma(y_if(\mathbf{x}_i)) & y_if(\mathbf{x}_i)>\gamma.
          \end{array}\right.
    $$
    Hence, $\gamma$ as defined here is consistent with $\gamma$ as
    defined in Section~\ref{ss-measures}.
    \fi

Let $F_\calK$ denote the class of functions on $S$ of the
form~(\ref{eq:fdef}) satisfying~(\ref{eq:wbound}), for some
$K\in\calK$,
  \[
    F_\calK = \left\{ \bx_j \mapsto \sum_{i=1}^{2n}\alpha_iK_{ij} :
    K\in\calK,\, \ba^T K\ba \le \frac{1}{\gamma^2} \right\},
  \]
where $\calK$ is a set of positive semidefinite $2n\times 2n$
matrices.
We also consider the class of kernel expansions obtained
from certain linear combinations of a fixed set
$\{K_1,\ldots,K_m\}$ of kernel matrices: Define the class
$F_{\calK_c}$  as
  \[
    \calK_c = \left\{ K=\sum_{j=1}^m \mu_jK_j :
      K\succeq 0,\,\mu_j\in\mathbb{R},\, \textrm{trace}(K)\le c\right\},
  \]
and the class $F_{\calK_c^+}$ as
  \[
    \calK_c^+ = \left\{ \sum_{j=1}^m \mu_jK_j :
      K\succeq 0,\,\mu_j\ge 0,\, \textrm{trace}(K)\le c\right\}.
  \]

\begin{theorem}\label{thm:transd}
  For every $\gamma>0$, with probability at least $1-\delta$ over the data
  $(\mathbf{x}_i,y_i)$ chosen as above, every function $f\in F_\calK$
  has $\mbox{\rm er}(f)$ no more than
    \begin{equation*}
      \frac{1}{n}\sum_{i=1}^n\max\left\{1-y_if(\mathbf{x}_i),0\right\}
      + \frac{1}{\sqrt{n}}\left(4
      + \sqrt{2\log(1/\delta)} + \sqrt{\frac{\mathcal{C}(\calK)}{n\gamma^2}}\right),
    \end{equation*}
  where
    \[
      \mathcal{C}(\calK) = \Expect \max_{K\in\calK} \bsigma^T K \bsigma,
    \]
  with the expectation over $\bsigma$ chosen uniformly from
  $\{\pm 1\}^{2n}$.

  Furthermore,
    \[
      \mathcal{C}(\calK_c) = c\Expect\max_{K\in\calK}\bsigma^T
      \frac{K}{\textrm{trace}(K)}\bsigma,
    \]
  and this is always no more than $cn$, and
    \[
      \mathcal{C}(\calK_c^+) \le c\min\left(m,n\max_j
        \frac{\lambda_j}{\textrm{trace}(K_j)}\right),
    \]
  where $\lambda_j$ is the largest eigenvalue of $K_j$.
\end{theorem}

Notice that the test error is bounded by a sum of the
average over the training data of a margin cost function
plus a complexity penalty term that depends on the ratio
between the trace of the kernel matrix and the squared
margin parameter, $\gamma^2$.  The kernel matrix here is
the full matrix, combining both test and training data.

The proof of the theorem is in
Appendix~\ref{appendix:errorbound}.  The proof technique
for the first part of the theorem was introduced by
\cite{KolPan02}, who used it to give error bounds for
boosting algorithms.

Although the theorem requires the margin parameter $\gamma$
to be specified in advance, it is straightforward to extend
the result to give an error bound that holds with high
probability over all values of $\gamma$. In this case,
the $\log(1/\delta)$ in the bound would be replaced by
$\log(1/\delta) + |\log(1/\gamma)|$ and the constants
would increase slightly. See, for example, Proposition~8
and its applications in the work of~\cite{b-scpcnn-98}.

The result is presented for the $1$-norm soft margin
classifier, but the proof uses only two properties of the
cost function $a\mapsto\max\{1-a,0\}$: that it is an upper
bound on the indicator function for $a\le 0$, and that it
satisfies a Lipschitz constraint on $[0,\infty)$. These
conditions are also satisfied by the cost function
associated with the $2$-norm soft margin classifier,
$a\mapsto\left(\max\{1-a,0\}\right)^2$, for example.

The bound on the complexity $\mathcal{C}(\calK_B^+)$
of the kernel class $\calK_B^+$ is easier to check
than the bound on $\mathcal{C}(\calK_B)$. The first
term in the minimum shows that the set of positive
linear combinations of a small set of kernel matrices
is not very complex. The second term shows that if, for
each matrix in the set, the largest eigenvalue does not
dominate the sum of the eigenvalues (the trace), then the
set of positive linear combinations is not too complex,
even if the set is large.  In  either case, the upper
bound is linear in $c$, the upper bound on the trace of
the combined kernel matrix.

\section{Empirical Results}\label{s-exp}

We first present results on benchmark data sets, using kernels
$K_i$ that are derived from the same input vector.  The goal here
is to explore different possible representations of the same
data source, and to choose a representation or combinations
of representations that yield the best performance.  We compare
to the soft margin SVM with an RBF kernel, in which the hyperparameter
is tuned via cross-validation.  Note that in our framework there
is no need for cross-validation to tune the corresponding kernel
hyperparameters.  Moreover, when using the 2-norm soft margin SVM,
the methods are directly comparable, because the hyperparameter
$C$ is present in both cases.

In the second section we explore the use of our framework to
combine kernels that are built using data from heterogeneous
sources. Here our main interest is in comparing the combined
classifier to the best \emph{individual} classifier.  To the
extent that the heterogeneous data sources provide complementary
information, we might expect that the performance of the combined
classifier can dominate that of the best individual classifier.

\subsection{Benchmark Data Sets}\label{ss-benchmark-data}

We present results for hard margin and soft margin support vector
machines. We use a kernel matrix $K = \sum_{i=1}^3 \mu_i K_i$,
where the $K_i$'s are initial ``guesses'' of the kernel matrix. We
use a polynomial kernel function $k_1(\mathbf{x}_1,\mathbf{x}_2) =
(1 + \mathbf{x}_1^T \mathbf{x}_2)^d$ for $K_1$, a Gaussian kernel
function $k_2(\mathbf{x}_1,\mathbf{x}_2) = \exp(-0.5 (\mathbf{x}_1
- \mathbf{x}_2)^T (\mathbf{x}_1 - \mathbf{x}_2)/ \sigma)$ for
$K_2$ and a linear kernel function $k_3(\mathbf{x}_1,\mathbf{x}_2)
= \mathbf{x}_1^T \mathbf{x}_2$ for $K_3$. Afterwards, all $K_i$
are normalized. After evaluating the initial kernel matrices
$\{K_i\}_{i=1}^3$, the weights $\{\mu_i\}_{i=1}^3$ are optimized
in a transduction setting according to a hard margin, a 1-norm
soft margin and a 2-norm soft margin criterion, respectively; the
semidefinite programs (\ref{sdpmargin2}),
(\ref{sdpsoftmargin1_2}) and (\ref{sdpsoftmargin2_2}) are solved
using the general-purpose optimization software SeDuMi
\citep{Stu:99}, leading to optimal weights $\{ \mu_i^*
\}_{i=1}^3$. Next, the weights $\{\mu_i\}_{i=1}^3$ are constrained
to be non-negative and optimized according to the same criteria,
again in a transduction setting: the second order cone programs
(\ref{eq:socp-hm}), (\ref{eq:socp_SM1}) and (\ref{eq:socp_SM2})
are solved using the general-purpose optimization software Mosek
\citep{AnA:00}, leading to optimal weights $\{ \mu_{i,+}^*
\}_{i=1}^3$. For positive weights, we also report results in which
the 2-norm soft margin hyperparameter $C$ is tuned according to
(\ref{eq:socp-sm2-tau}).

Empirical results on standard benchmark datasets are summarized in
Tables \ref{expt-results1}, \ref{expt-results2} and
\ref{expt-results3}.\footnote{It is worth noting that the
first three columns of these columns are based on an inductive
algorithm whereas the last two columns are based on a transductive
algorithm.  This may favor the kernel combinations in the last two
columns and thus the results should be interpreted with caution.
However, it is also worth noting that the transduction is a weak form
of transduction that is based only on the norm of the test data point.}
The Wisconsin breast cancer dataset contained
16 incomplete examples which were not used. The breast cancer,
ionosphere and sonar data were obtained from the UCI repository.
The heart data were obtained from STATLOG and normalized. Data for
the 2-norm problem data were generated as specified by
\citet{Bre:98}. Each dataset was randomly partitioned into 80\%
training and 20\% test sets. The reported results are the averages
over 30 random partitions. The kernel parameters for $K_1$ and
$K_2$ are given in Tables \ref{expt-results1}, \ref{expt-results2}
and \ref{expt-results3} by $d$ and $\sigma$ respectively. For each
of the kernel matrices, an SVM is trained using the training block
$K_{tr}$ and tested using the mixed block $K_{tr,t}$ as defined in
(\ref{blockstruct}). The margin $\gamma$ (for a hard margin
criterion) and the optimal soft margin cost functions
$\omega_{S1}^*$ and $\omega_{S2}^*$ (for soft margin criteria) are
reported for the initial kernel matrices $K_i$, as well as for the
optimal $\sum_i \mu_i^* K_i$ and $\sum_i \mu_{i,+}^* K_i$.
Furthermore, the average test set accuracy (TSA), the average
value for $C$ and the average weights over the 30 partitions are
listed. For comparison, the performance of the best soft margin
SVM with an RBF (Gaussian) kernel is reported---the soft margin
hyperparameter $C$ and the kernel parameter $\sigma$ for the
Gaussian kernel were tuned using cross-validation over 30 random
partitions of the training set.


\begin{table}[h]
\begin{center}
{\scriptsize
\begin{tabular}{llcccccc}\hline
 & & $K_1$ & $K_2$ & $K_3$ & $\sum_i \mu_i^* K_i$ & $\sum_i \mu_{i,+}^* K_i$ & best c/v RBF \\
 \hline
 \multicolumn{2}{l} {\em Heart} & $d=2$ & $\sigma=0.5$ &  &  &  &  \\
 HM & $\gamma$ & 0.0369 & 0.1221 & - & 0.1531 & 0.1528 &  \\
 & {\bf TSA } & {\bf 72.9 \% } & {\bf 59.5 \% } & - & {\bf 84.8 \% } & {\bf 84.6 \% } & {\bf  77.7 \%} \\
 & $\mu_1/\mu_2/\mu_3$ & 3/0/0 & 0/3/0 & 0/0/3 & {\bf -0.09/2.68/0.41 } & {\bf 0.01/2.60/0.39} &  \\
   SM1 & $\omega_{S1}^*$ & 58.169 & 33.536 & 74.302 & 21.361 & 21.446 &  \\
 & {\bf TSA } & {\bf 79.3 \% } & {\bf 59.5 \% } & {\bf 84.3 \% } & {\bf 84.8 \% } & {\bf 84.6 \% } & {\bf 83.9 \%} \\
 & $C$ & 1 & 1 & 1 & 1 & 1 &  \\
 & $\mu_1/\mu_2/\mu_3$ & 3/0/0 & 0/3/0 & 0/0/3 & {\bf  -0.09/2.68/0.41 } & {\bf 0.01/2.60/0.39} &  \\
  SM2 & $\omega_{S2}^*$ & 32.726 & 25.386 & 45.891 & 15.988 & 16.034 &  \\
 & {\bf TSA } & {\bf 78.1 \% } & {\bf 59.0 \% } & {\bf 84.3 \% } & {\bf 84.8 \% } & {\bf 84.6 \% } & {\bf 83.2 \%} \\
 & $C$ & 1 & 1 & 1 & 1 & 1 &  \\
 & $\mu_1/\mu_2/\mu_3$ & 3/0/0 & 0/3/0 & 0/0/3 & {\bf  -0.08/2.54/0.54 } & {\bf 0.01/2.47/0.53} &  \\
  SM2,C & $\omega_{S2}^*$ & 19.643 & 25.153 & 16.004 &  & 15.985 &  \\
 & {\bf TSA } & {\bf 81.3 \% } & {\bf 59.6 \% } & {\bf 84.7 \% } & {\bf  } & {\bf 84.6 \% } & {\bf 83.2 \%} \\
 & $C$ & 0.3378 & 1.18e+7 & 0.2880 &  & 0.4365 &  \\
 & $\mu_1/\mu_2/\mu_3$ & 1.04/0/0 & 0/3.99/0 & 0/0/0.53 &   & {\bf 0.01/0.80/0.53} &  \\
 \hline
 \multicolumn{2}{l} {\em Sonar} & $d=2$ & $\sigma=0.1$ &  &  &  &  \\
 HM & $\gamma$ & 0.0246 & 0.1460 & 0.0021 & 0.1517 & 0.1459 &  \\
 & {\bf TSA } & {\bf 80.9 \% } & {\bf 85.8 \% } & {\bf 74.2 \% } & {\bf 84.6 \% } & {\bf 85.8 \% } & {\bf  84.2 \%} \\
 & $\mu_1/\mu_2/\mu_3$ & 3/0/0 & 0/3/0 & 0/0/3 & {\bf -2.23/3.52/1.71 } & {\bf 0/3/0} &  \\
   SM1 & $\omega_{S1}^*$ & 87.657 & 23.288 & 102.68 & 21.637 & 23.289 &  \\
 & {\bf TSA } & {\bf 78.1 \% } & {\bf 85.6 \% } & {\bf 73.3 \% } & {\bf 84.6 \% } & {\bf 85.6 \% } & {\bf 84.2 \%} \\
 & $C$ & 1 & 1 & 1 & 1 & 1 &  \\
 & $\mu_1/\mu_2/\mu_3$ & 3/0/0 & 0/3/0 & 0/0/3 & {\bf  -2.20/3.52/1.69 } & {\bf 0/3/0} &  \\
  SM2 & $\omega_{S2}^*$ & 45.048 & 15.893 & 53.292 & 15.219 & 15.893 &  \\
 & {\bf TSA } & {\bf 79.1 \% } & {\bf 85.2 \% } & {\bf 76.7 \% } & {\bf 84.5 \% } & {\bf 85.2 \% } & {\bf 84.2 \%} \\
 & $C$ & 1 & 1 & 1 & 1 & 1 &  \\
 & $\mu_1/\mu_2/\mu_3$ & 3/0/0 & 0/3/0 & 0/0/3 & {\bf  -1.78/3.46/1.32 } & {\bf 0/3/0} &  \\
  SM2,C & $\omega_{S2}^*$ & 20.520 & 15.640 & 20.620 &  & 15.640 &  \\
 & {\bf TSA } & {\bf 60.9 \% } & {\bf 84.6 \% } & {\bf 51.0 \% } & {\bf  } & {\bf 84.6 \% } & {\bf 84.2 \%} \\
 & $C$ & 0.2591 & 0.6087 & 0.2510 &  & 0.6087 & \\
 & $\mu_1/\mu_2/\mu_3$ & 0.14/0/0 & 0/2.36/0 & 0/0/0.02 &   & {\bf 0/2.34/0} &  \\
 \hline
\end{tabular}
} \caption{SVMs trained and tested with the initial kernel
matrices $K_1, K_2, K_3$ and with the optimal kernel matrices
$\sum_i \mu_i^* K_i$ and $\sum_i \mu_{i,+}^* K_i$. For hard margin
SVMs (HM), the resulting margin $\gamma$ is given---a dash meaning
that no hard margin classifier could be found; for soft margin
SVMs (SM1 = 1-norm soft margin with $C=1$, SM2 = 2-norm soft
margin with $C=1$ and SM2,C = 2-norm soft margin with auto tuning
of $C$) the optimal value of the cost function $\omega_{S1}^*$ or
$\omega_{S2}^*$ is given. Furthermore, the test-set accuracy
(TSA), the average weights and the average $C$-values are given.
For $c$ we used $c = \sum_i \textrm{trace} (K_i)$ for HM, SM1 and
SM2. The initial kernel matrices are evaluated after being
multiplied by 3. This assures we can compare the different
$\gamma$ for HM, $\omega_{S1}^*$ for SM1 and $\omega_{S2}^*$ for
SM2, since the resulting kernel matrix has a constant trace (thus,
everything is on the same scale). For SM2,C we use $c = \sum_i
\textrm{trace} (K_i) + \textrm{trace}(I_n)$. This not only allows
comparing the different $\omega_{S2}^*$ for SM2,C but also it
allows comparing $\omega_{S2}^*$ between SM2 and SM2,C (since we
choose $C=1$ for SM2, we have that
$\textrm{trace}\left(\sum_{i=1}^m \mu_i K_i + \frac{1}{C}
I_n\right)$ is constant in both cases, so again, we are on the
same scale). Finally, the column 'best c/v RBF' reports the
performance of the best soft margin SVM with RBF kernel, tuned
using cross-validation.}\label{expt-results1}
\end{center}
\end{table}


\begin{table}[h]
\begin{center}
{\scriptsize
\begin{tabular}{llcccccc}\hline
 & & $K_1$ & $K_2$ & $K_3$ & $\sum_i \mu_i^* K_i$ & $\sum_i \mu_{i,+}^* K_i$ & best c/v RBF \\
 \hline
 \multicolumn{2}{l} {\em Breast cancer} & $d=2$ & $\sigma=0.5$ &  &  &  &  \\
 HM & $\gamma$ & 0.0036 & 0.1055 & - & 0.1369 & 0.1219 &  \\
 & {\bf TSA} & {\bf 92.9 \% } & {\bf 89.0 \% } & - & {\bf 95.5 \% } & {\bf 94.4 \% } & {\bf  96.1 \%} \\
 & $\mu_1/\mu_2/\mu_3$ & 3/0/0 & 0/3/0 & 0/0/3 & {\bf 1.90/2.35/-1.25} & {\bf 0.65/2.35/0} &  \\
   SM1 & $\omega_{S1}^*$ & 77.012 & 44.913 & 170.26 & 26.694 & 33.689 &  \\
 & {\bf TSA } & {\bf 96.4 \% } & {\bf 89.0 \% } & {\bf 87.7 \% } & {\bf 95.5 \% } & {\bf 94.4 \% } & {\bf 96.7 \%} \\
 & $C$ & 1 & 1 & 1 & 1 & 1 &  \\
 & $\mu_1/\mu_2/\mu_3$ & 3/0/0 & 0/3/0 & 0/0/3 & {\bf 1.90/2.35/-1.25 } & {\bf 0.65/2.35/0} &  \\
  SM2 & $\omega_{S2}^*$ & 43.138 & 35.245 & 102.51 & 20.696 & 21.811 &  \\
 & {\bf TSA } & {\bf 96.4 \% } & {\bf 88.5 \% } & {\bf 87.4 \% } & {\bf 95.4 \% } & {\bf 94.3 \% } & {\bf 96.8 \%} \\
 & $C$ & 1 & 1 & 1 & 1 & 1 &  \\
 & $\mu_1/\mu_2/\mu_3$ & 3/0/0 & 0/3/0 & 0/0/3 & {\bf  2.32/2.13/-1.46 } & {\bf 0.89/2.11/0} &  \\
  SM2,C & $\omega_{S2}^*$ & 27.682 & 33.685 & 41.023 &  & 25.267 &  \\
 & {\bf TSA } & {\bf 94.5 \% } & {\bf 89.0 \% } & {\bf 87.3 \% } & {\bf  } & {\bf 94.4 \% } & {\bf 96.8 \%} \\
 & $C$ & 0.3504 & 1.48e+8 & 0.3051 &  & 6.77e+7 &  \\
 & $\mu_1/\mu_2/\mu_3$ & 1.15/0/0 & 0/3.99/0 & 0/0/0.72 &   & {\bf 0.87/3.13/0 } &  \\
 \hline
 \multicolumn{2}{l} {\em Ionosphere} & $d=2$ & $\sigma=0.5$ &  &  &  &  \\
 HM & $\gamma$ & 0.0613 & 0.1452 & - & 0.1623 & 0.1616 &  \\
 & {\bf TSA } & {\bf 91.2 \% } & {\bf 92.0 \% } & - & {\bf 94.4 \% } & {\bf 94.4 \% } & {\bf   93.9 \%} \\
 & $\mu_1/\mu_2/\mu_3$ & 3/0/0 & 0/3/0 & 0/0/3 & {\bf 1.08/2.18/-0.26 } & {\bf 0.79/2.21/0} &  \\
   SM1 & $\omega_{S1}^*$ & 30.786 & 23.233 & 52.312 & 18.117 & 18.303 &  \\
 & {\bf TSA } & {\bf 94.5 \% } & {\bf 92.1 \% } & {\bf 83.1 \% } & {\bf 94.8 \% } & {\bf 94.5 \% } & {\bf 94.0 \%} \\
 & $C$ & 1 & 1 & 1 & 1 & 1 &  \\
 & $\mu_1/\mu_2/\mu_3$ & 3/0/0 & 0/3/0 & 0/0/3 & {\bf 1.23/2.07/-0.30 } & {\bf 0.90/2.10/0} &  \\
  SM2 & $\omega_{S2}^*$ & 18.533 & 17.907 & 31.662 & 13.382 & 13.542 &  \\
 & {\bf TSA } & {\bf 94.7 \% } & {\bf 92.0 \% } & {\bf 91.6 \% } & {\bf 94.5 \% } & {\bf 94.4 \% } & {\bf 94.2 \%} \\
 & $C$ & 1 & 1 & 1 & 1 & 1 &  \\
 & $\mu_1/\mu_2/\mu_3$ & 3/0/0 & 0/3/0 & 0/0/3 & {\bf 1.68/1.73/-0.41} & {\bf 1.23/1.78/0} &  \\
  SM2,C & $\omega_{S2}^*$ & 14.558 & 17.623 & 18.975 &  & 13.5015 &  \\
 & {\bf TSA } & {\bf 93.5 \% } & {\bf 92.1 \% } & {\bf 90.0 \% } & {\bf  } & {\bf 94.6 \% } & {\bf 94.2 \%} \\
 & $C$ & 0.4144 & 5.8285 & 0.3442 &  & 0.8839 &  \\
 & $\mu_1/\mu_2/\mu_3$ & 1.59/0/0 & 0/3.83/0 & 0/0/1.09 &   & {\bf 1.24/1.61/0} &  \\
 \hline
\end{tabular}
} \caption{See the caption to Table 1 for explanation.}
\label{expt-results2}
\end{center}
\end{table}




\begin{table}[h]
\begin{center}
{\scriptsize
\begin{tabular}{llcccccc}\hline
 & & $K_1$ & $K_2$ & $K_3$ & $\sum_i \mu_i^* K_i$ & $\sum_i \mu_{i,+}^* K_i$ & best c/v RBF \\
 \hline
 \multicolumn{2}{l} {\em 2-norm} & $d=2$ & $\sigma=0.1$ &  &  &  &  \\
 HM & $\gamma$ & 0.1436 & 0.1072 & 0.0509 & 0.2170 & 0.2169 &  \\
 & {\bf TSA } & {\bf 94.6 \% } & {\bf 55.4 \% } & {\bf 94.3 \% } & {\bf 96.6 \% } & {\bf 96.6 \% } & {\bf  96.3 \%} \\
 & $\mu_1/\mu_2/\mu_3$ & 3/0/0 & 0/3/0 & 0/0/3 & {\bf 0.03/1.91/1.06 } & {\bf 0.06/1.88/1.06} &  \\
   SM1 & $\omega_{S1}^*$ & 23.835 & 43.509 & 22.262 & 10.636 & 10.641 &  \\
 & {\bf TSA } & {\bf 95.0 \% } & {\bf 55.4 \% } & {\bf 95.7 \% } & {\bf 96.6 \% } & {\bf 96.6 \% } & {\bf 97.5 \%} \\
 & $C$ & 1 & 1 & 1 & 1 & 1 &  \\
 & $\mu_1/\mu_2/\mu_3$ & 3/0/0 & 0/3/0 & 0/0/3 & {\bf 0.03/1.91/1.06 } & {\bf 0.06/1.88/1.06} &  \\
  SM2 & $\omega_{S2}^*$ & 16.134 & 32.631 & 11.991 & 7.9780 & 7.9808 &  \\
 & {\bf TSA } & {\bf 95.9 \% } & {\bf 55.4 \% } & {\bf 95.6 \% } & {\bf 96.6 \% } & {\bf 96.6 \% } & {\bf 97.2 \%} \\
 & $C$ & 1 & 1 & 1 & 1 & 1 &  \\
 & $\mu_1/\mu_2/\mu_3$ & 3/0/0 & 0/3/0 & 0/0/3 & {\bf 0.05/1.54/1.41 } & {\bf 0.08/1.51/1.41} &  \\
  SM2,C & $\omega_{S2}^*$ & 16.057 & 32.633 & 7.9880 &  & 7.9808 &  \\
 & {\bf TSA } & {\bf 96.2 \% } & {\bf 55.4 \% } & {\bf 96.6 \% } & {\bf  } & {\bf 96.6 \% } & {\bf 97.2 \%} \\
 & $C$ & 0.8213 & 0.5000 & 0.3869 &  & 0.8015 & \\
 & $\mu_1/\mu_2/\mu_3$ & 2.78/0/0 & 0/2/0 & 0/0/1.42 &   & {\bf 0.08/1.25/1.41} &  \\
\hline
\end{tabular}
} \caption{See the caption to Table 1 for explanation.}
\label{expt-results3}
\end{center}
\end{table}


Note that not every $K_i$ gives rise to a linearly separable
embedding of the training data, in which case no hard margin
classifier can be found (indicated with a dash). The matrices
$\sum_i \mu_i^* K_i$ and $\sum_i \mu_{i,+}^* K_i$ however, always
allow the training of a hard margin SVM and its margin is indeed
larger than the margin for each of the different components
$K_i$---this is consistent with the SDP/QCQP optimization. For the soft
margin criteria, the optimal value of the cost function for
$\sum_i \mu_i^* K_i$ and $\sum_i \mu_{i,+}^* K_i$ is smaller than
its value for the individual $K_i$---again consistent with the
SDP/QCQP optimizations. Notice that constraining the weights
$\mu_i$ to be positive results in slightly smaller margins and
larger cost functions, as expected.

Furthermore, the number of test set errors for $\sum_i \mu_i^*
K_i$ and $\sum_i \mu_{i,+}^* K_i$ is in general comparable in
magnitude to the best value achieved among the different
components $K_i$. Also notice that $\sum_i \mu_{i,+}^* K_i$ does
often almost as well as $\sum_i \mu_i^* K_i$, and sometimes even
better: we can thus achieve a substantial reduction in
computational complexity without a significant loss of
performance. Moreover, the performance of $\sum_i \mu_i^* K_i$ and
$\sum_i \mu_{i,+}^* K_i$ is comparable with the best soft margin
SVM with an RBF kernel. In making this comparison note that the
RBF SVM requires tuning of the kernel parameter using
cross-validation, while the kernel learning approach achieves a
similar effect without cross-validation.\footnote{The experiments
were run on a 2GHz Windows XP machine.  We used the programs SeDuMi
to solve the SDP for kernel learning and Mosek to solve multiple QP's
for cross-validated SVM and the QCQP for kernel learning with
positive weights.  The run time for the SDP is on the order of
minutes (approximately 10 minutes for 300 data points and 5 kernels),
while the run time for the QP and QCQP is on the order of seconds
(approximately 1 second for 300 data points and 1 kernel, and
approximately 3 seconds for 300 data points and 5 kernels).
Thus, we see that kernel learning with positive weights, which
requires only a QCQP solution, achieves an accuracy which is
comparable to the full SDP approach at a fraction of the computational
cost, and our tentative recommendation is that the QCQP approach is
to be preferred.  It is worth noting, however, that special-purpose
implementations of SDPs that take advantage of the structure of the
kernel learning problem may well yield significant speed-ups, and
the recommendation should be taken with caution.  Finally, the
QCQP approach also compares favorably in terms of run time to
the multiple runs of a QP that are required for cross-validation,
and should be considered a viable alternative to cross-validation,
particularly given the high variance associated with cross-validation
in small data sets.} Moreover, when using the 2-norm soft margin SVM with
tuned hyperparameter $C$, we no longer need to do cross-validation
for $C$. This leads to a smaller value of the optimal cost
function $\omega_{S2}^*$ (compared to the case SM2, with $C=1$)
and performs well on the test set, while offering the advantage of
automatically adjusting $C$.

One might wonder why there is a difference between the SDP and the
QCQP approach for the 2-norm data, since both seem to find
positive weights $\mu_i$. However, it must be recalled that the
values in Table~\ref{expt-results3} are averages over 30
randomizations---for some randomizations the SDP has actually
found negative weights, although the averages are positive.

As a further example illustrating the flexibility of the SDP
framework, consider the following setup. Let $\{K_i\}_{i=1}^5$ be
Gaussian kernels with $\sigma = 0.01, 0.1, 1, 10, 100$
respectively. Combining those optimally with $\mu_i \geq 0$ for a
2-norm soft margin SVM, with tuning of $C$, yields the
results in Table~\ref{expt-results4}---averages over 30
randomizations in 80\% training and 20\% test sets. The test set
accuracies obtained for $\sum_i \mu_{i,+}^* K_i$ are competitive
with those for the best soft margin SVM with an RBF kernel, tuned
using cross-validation. The average weights show that some kernels
are selected and others are not. Effectively we obtain a
data-based choice of smoothing parameter without recourse to
cross-validation.


\begin{table}[h]
\begin{center}
\begin{tabular}{lcccccccc}\hline
 & $\mu_{1,+}$ & $\mu_{2,+}$ & $\mu_{3,+}$ & $\mu_{4,+}$ & $\mu_{5,+}$ & $C$ & TSA SM2,C & TSA best c/v RBF \\
 \hline
 {\em Breast Cancer} & 0 & 0 & 3.24 & 0.94 & 0.82 & 3.6e+08 & 97.1 \% & 96.8 \% \\
 {\em Ionosphere} & 0.85 & 0.85 & 2.63 & 0.68 & 0 & 4.0e+06 & 94.5 \% & 94.2 \% \\
 {\em Heart} & 0 & 3.89 & 0.06 & 1.05 & 0 & 2.5e+05 & 84.1 \% & 83.2 \% \\
 {\em Sonar} & 0 & 3.93 & 1.07 & 0 & 0 & 3.2e+07 & 84.8 \% & 84.2 \% \\
 {\em 2-norm} & 0.49 & 0.49 & 0 & 3.51 & 0 & 2.0386 & 96.5 \% & 97.2 \% \\
 \hline
\end{tabular}
\caption{The initial kernel matrices $\{K_i\}_{i=1}^5$ are
Gaussian kernels with $\sigma = 0.01, 0.1, 1, 10, 100$
respectively. For $c$ we used $c = \sum_i \textrm{trace} (K_i) +
\textrm{trace}(I_n)$. $\{\mu_{i,+}\}_{i=1}^5$ are the average
weights of the optimal kernel matrix $\sum_i \mu_{i,+}^* K_i$ for
a 2-norm soft margin SVM with $\mu_i \geq 0$ and tuning of $C$.
The average $C$-value is given as well. The test set accuracies
(TSA) of the optimal 2-norm soft margin SVM with tuning of $C$
(SM2,C) and the best crossvalidation soft margin SVM with RBF
kernel (best c/v RBF) are reported.}\label{expt-results4}
\end{center}
\end{table}

In \cite{CSE:02} empirical results are given for optimization of
the alignment using a kernel matrix $K = \sum_{i=1}^N \mu_i \bv_i
\bv_i^T$.  The results show that optimizing the alignment indeed
improves the generalization power of Parzen window classifiers. As
explained in Section \ref{ss-SDP-alignment}, it turns out that in
this particular case, the SDP in (\ref{sdpalignment2}) reduces to
exactly the quadratic program that is obtained in \cite{CSE:02}
and thus those results also provide support for the general
framework presented in the current paper.

\subsection{Combining Heterogeneous Data}

\subsubsection{Reuters-21578 Data Set}

To explore the value of this approach for combining data from
heterogeneous sources, we run experiments on the Reuters-21578
data set, using two different kernels. The first kernel $K_1$ is
derived as a linear kernel from the ``bag-of-words''
representation of the different documents, capturing information
about the frequency of terms in the different documents
\citep{SaM:83}. $K_1$ is centered and normalized. The second
kernel $K_2$ is constructed by extracting 500 concepts from
documents via probabilistic latent semantic analysis \citep{CaH:03}.
This kernel can be viewed as arising from a document-concept-term
graphical model, with the concepts as hidden nodes. After
inferring the conditional probabilities of the concepts, given a
document, a linear kernel is applied to the vector of these
probabilistic ``concept memberships,'' representing each document.
Also $K_2$ is then centered and normalized. The concept-based
document information contained in $K_2$ is likely to be partly
overlapping and partly complementary to the term-frequency
information in $K_1$. Although the ``bag-of-words'' and graphical
model representation are clearly heterogeneous, they can both be
cast into a homogeneous framework of kernel matrices, allowing the
information that they convey to be combined according to $K =
\mu_1 K_1 + \mu_2 K_2$.

The Reuters-21578 dataset consists of Reuters newswire stories
from 1987
(\url{www.davidlewis.com/resources/testcollections/reuters21578/}).
After a preprocessing stage that includes tokenization and stop
word removal, 37926 word types remained. We used the modified
Apte (``ModApte'') split to split the collection into
12902 used and 8676 unused documents. The 12902 used documents
consist of 9603 training documents and 3299 test documents. From
the 9603 training documents, we randomly select a 1000-document
subset as training set for a soft margin support vector machine
with $C=1$. We train the SVM for the binary classification tasks
of distinguishing documents about a certain topic versus those not
about that topic.  We restrict our attention to the topics that
appear in the most documents (cf.\ \cite{CaH:03,Hua:03,EGJ:03});
in particular, we focused on the top five Reuters-21578 topics.

After training the SVM on the randomly selected documents
using either $K_1$ or $K_2$, the accuracy is tested on the 3299
test documents from the ModApte split. This is done 20 times,
i.e., for 20 randomly chosen 1000-document training sets. The
average accuracies and standard errors are reported in Figure~\ref{figure:results-reuters}. After evaluating the performance of
$K_1$ and $K_2$, the weights $\mu_1$ and $\mu_2$ are constrained
to be non-zero and optimized (using only the training data)
according to (\ref{eq:socp_SM1}). The test set performance
of the optimal combination is then evaluated
and the average accuracy reported in Figure~\ref{figure:results-reuters}. The optimal weights, $\mu_1^*$ and
$\mu_2^*$, do not vary greatly over the different topics, with
averages of 1.37 for $\mu_1^*$ and 0.63 for $\mu_2^*$.


\begin{figure}
\begin{center}
\includegraphics[width=0.9\textwidth]{comp_reuters_gray.eps}
\end{center}
\caption{{\bf Classification performance for the top five
Reuters-21578 topics.} The height of each bar is proportional to
the average test set accuracy for a 1-norm soft margin SVM with
$C=1$.  Black bars correspond to using only kernel matrix
$K_1$; grey bars correspond to using only kernel matrix $K_2$, and
white bars correspond to the optimal combination $\mu_1^* K_1 +
\mu_2^* K_2$. The kernel matrices $K_1$ and $K_2$ are derived from
different types of data, i.e., from the ``bag-of-words''
representation of documents and the concept-based graphical model
representation (with 500 concepts) of documents respectively. For
$c$ we used $c = \textrm{trace} (K_1) + \textrm{trace} (K_2) =
4000$.  The standard errors across the 20 experiments are approximately
0.1 or smaller; indeed, all of the depicted differences between the
optimal combination and the individual kernels are statistically
significant except for EARN.
\label{figure:results-reuters} }
\end{figure}

We see that in four cases out of five the optimal combination of kernels
performs better than either of the individual kernels. This suggests that
these kernels indeed provide complementary information for the
classification decision, and that the SDP approach is able to find
a combination that exploits this complementarity.

\subsubsection{Protein Function Prediction}

Here we illustrate the SDP approach for fusing heterogeneous
genomic data in order to predict protein function in yeast;
see \cite{LDCJN:04} for more details. The task is to predict
functional classifications associated with yeast proteins. We use
as a gold standard the functional catalogue provided by the MIPS
Comprehensive Yeast Genome Database
(CYGD---\url{mips.gsf.de/proj/yeast}).  The top-level categories
in the functional hierarchy produce 13 classes, which contain 3588
proteins; the remaining yeast proteins have uncertain function and
are therefore not used in evaluating the classifier.  Because a
given protein can belong to several functional classes, we cast
the prediction problem as 13 binary classification tasks, one for
each functional class. Using this setup, we follow the
experimental paradigm of \cite{DCS:03}.

The primary input to the classification algorithm is a collection
of kernel matrices representing different types of data:
\begin{enumerate}
\item Amino acid sequences: this kernel incorporates information
about the domain structure of each protein, by looking at the
presence or absence in the protein of Pfam domains
(\url{pfam.wustl.edu}). The corresponding kernel is simply the
inner product between binary vectors describing the presence or
absence of one Pfam domain. Afterwards, we also construct a richer
kernel by replacing the binary scoring with log E-values using the
HMMER software toolkit (\url{hmmer.wustl.edu}). Moreover, an
additional kernel matrix is constructed by applying the
Smith-Waterman (SW) pairwise sequence comparison
algorithm~\cite[]{SmW:81} to the yeast protein sequences and
applying the empirical kernel map \citep{Tsu:99}.


\item Protein-protein interactions: this type of data can be
represented as a graph, with proteins as nodes and interactions as
edges. Such interaction graph allows to establish similarities
among proteins through the construction of a corresponding
diffusion kernel \citep{KoL:02}.

\item Genetic interactions: in a similar way, these interactions
give rise to a diffusion kernel.

\item Protein complex data: co-participation in a protein complex
can be seen as a weak sort of interaction, giving rise to a third
diffusion kernel.

\item Expression data: two genes with similar expression profiles
are likely to have similar functions; accordingly, \cite{DCS:03}
convert the expression matrix to a square binary interaction
matrix in which a 1 indicates that the corresponding pair of
expression profiles exhibits a Pearson correlation greater than
0.8. This can be used to define a diffusion kernel. Also, a richer
Gaussian kernel is defined directly on the expression profiles.
\end{enumerate}

In order to compare the SDP/SVM approach to the Markov random
field (MRF) method of \cite{DCS:03}, \cite{LDCJN:04} perform two variants of
the experiment: one in which the five kernels are restricted to
contain precisely the same binary information as used by the MRF
method, and a second experiment in which the richer Pfam and
expression kernels are used and the SW kernel is added.
They show that a combined SVM classifier trained with the
SDP approach performs better than an SVM trained on any
single type of data. Moreover it outperforms the MRF method
designed for this data set. To illustrate the latter,
Figure~\ref{figure:results2} presents the average ROC scores
on the test set when performing five-fold cross-validation three times.

\begin{figure}
\begin{center}
\includegraphics[width=0.9\textwidth]{comp_gray.eps}
\end{center}
\caption{{\bf Classification performance for the 13 functional
protein classes.} The height of each bar is proportional to the
ROC score. The standard error across the 13 experiments is usually
0.01 or smaller, so most of the depicted differences are
statistically significant: between black and grey bars, all
depicted differences are statistically significant, while nine of the
13 differences between grey and white bars are statistically
significant.
% GL: added this...
Black bars correspond to the MRF method of Deng {\em et al.}; grey
bars
  correspond to the SDP/SVM method using five kernels computed on
  binary data, and white bars correspond to the SDP/SVM using the
  enriched Pfam kernel and replacing the expression kernel with the SW
  kernel.  See \cite{LDCJN:04} for more details.
\label{figure:results2}}
\end{figure}

The figure shows that, for each of the 13 classifications, the ROC
score of the SDP/SVM method is better than that of the MRF method.
Overall, the mean ROC improves from 0.715 to 0.854. The
improvement of the SDP/SVM method over the MRF method is
consistent and statistically significant across all 13 classes.
An additional improvement, though not as large and only
statistically significant for nine of the 13 classes, is gained by
using richer kernels and adding the SW kernel.



\section{Discussion}\label{s-concl}

In this paper we have presented a new method for learning a kernel
matrix from data.  Our approach makes use of semidefinite
programming (SDP) ideas. It is motivated by the fact that every
symmetric, positive semidefinite matrix can be viewed as a kernel
matrix (corresponding to a certain embedding of a finite set of
data), and the fact that SDP deals with the optimization of convex
cost functions over the convex cone of positive semidefinite
matrices (or convex subsets of this cone).  Thus convex
optimization and machine learning concerns merge to provide a
powerful methodology for learning the kernel matrix with SDP.

We have focused on the transductive setting, where the labeled
data are used to learn an embedding, which is then applied to the
unlabeled part of the data.  Based on a new generalization bound
for transduction, we have shown how to impose convex constraints
that effectively control the capacity of the search space of
possible kernels and yield an efficient learning procedure that
can be implemented by SDP. Furthermore, this approach leads
to a convex method to learn the 2-norm soft margin parameter
in support vector machines, solving an important open problem.
Promising empirical results are reported on standard benchmark
datasets; these results show that the new approach provides a
principled way to combine multiple kernels to yield a classifier
that is comparable with the best individual classifier, and can
perform better than any individual kernel.  Performance is also
comparable with a classifier in which the kernel hyperparameter
is tuned with cross-validation; our approach achieves the effect
of this tuning without cross-validation.

We have also shown how optimizing a linear combination of kernel
matrices provides a novel method for fusing heterogeneous data
sources.  In this case, the empirical results show a significant
improvement of the classification performance for the optimal
combination of kernels when compared to individual kernels.

There are several challenges that need to be met in future
research on SDP-based learning algorithms.  First, it is clearly
of interest to explore other convex quality measures for a kernel
matrix, which may be appropriate for other learning algorithms.
For example, in the setting of Gaussian processes, the relative
entropy between the zero-mean Gaussian process prior $P$ with
covariance kernel $K$ and the corresponding Gaussian process
approximation $Q$ to the true intractable posterior process
depends on $K$ as
$$D[P||Q] = \frac{1}{2} \log \det K + \frac{1}{2} \textrm{trace}
\left( \by^T K \by \right) + d,$$ where the constant $d$ is
independent of $K$. One can verify that $D[P||Q]$ is convex with
respect to $R = K^{-1}$ \citep[see, e.g.,~][]{VBW:98}. Minimizing
this measure with respect to $R$, and thus $K$, is motivated from
PAC-Bayesian generalization error bounds for Gaussian processes
\citep[see, e.g.,~][]{See:02} and can be achieved by solving a
so-called \emph{maximum-determinant problem} \citep{VBW:98}---an
even more general framework that contains semidefinite
programming as a special case.

Second, the investigation of other parameterizations of the kernel
matrix is an important topic for further study. While the linear
combination of kernels that we have studied here is likely to be
useful in many practical problems---capturing a notion of
combining Gram matrix ``experts''---it is also worth considering
other parameterizations as well.  Any such parameterizations have
to respect the constraint that the quality measure for the kernel
matrix is convex with respect to the parameters of the proposed
parameterization. One class of examples arises via the positive
definite matrix completion problem \citep{VBW:98}. Here we are
given a symmetric kernel matrix $K$ that has some entries which
are fixed. The remaining entries---the parameters in this
case---are to be chosen such that the resulting matrix is positive
definite, while simultaneously a certain cost function is
optimized, e.g., $\textrm{trace} (S K) + \log \det K^{-1}$, where
$S$ is a given matrix. This specific case reduces to solving a
maximum-determinant problem which is convex in the unknown entries
of $K$, the parameters of the proposed parameterization.

A third important area for future research consists in finding
faster implementations of semidefinite programming. As in the
case of quadratic programming \citep{Pla:99}, it seems likely that
special purpose methods can be developed to exploit the
exchangeable nature of the learning problem in classification and
result in more efficient algorithms.

Finally, by providing a general approach for combining heterogeneous
data sources in the setting of kernel-based statistical learning
algorithms, this line of research suggests an important role for
kernel matrices as general building blocks of statistical models.
Much as in the case of finite-dimensional sufficient statistics,
kernel matrices generally involve a significant reduction of the
data and represent the only aspects of the data that are used by
subsequent algorithms.  Moreover, given the panoply of methods
that are available to accommodate not only the vectorial and matrix
data that are familiar in classical statistical analysis, but also
more exotic data types such as strings, trees and graphs, kernel
matrices have an appealing universality.  It is natural to envision
libraries of kernel matrices in fields such as bioinformatics,
computational vision, and information retrieval, in which multiple
data sources abound.  Such libraries would summarize the
statistically-relevant features of primary data, and encapsulate
domain specific knowledge.  Tools such as the semidefinite programming
methods that we have presented here can be used to bring these multiple
data sources together in novel ways to make predictions and decisions.

\section*{Acknowledgements}
We acknowledge support from ONR MURI N00014-00-1-0637 and NSF
grant IIS-9988642.  Sincere thanks to Tijl De Bie for helpful
conversations and suggestions, as well as to Lijuan Cai and Thomas
Hofmann for providing the data for the Reuters-21578 experiments.


\newpage

\appendix

\iffalse
\section{Proof of Result (\ref{eq:qp-margin})}\label{app-qp-HMSVM}

For the case $K_i = \bv_i \bv_i^T$, with $\bv_i$ orthonormal, the
original learning problem (\ref{sdp-margin-learn}) becomes
\begin{eqnarray}
\min_{K} & & \omega(K_{tr}) \nonumber \\
\textrm{subject to} & & \textrm{trace}(K) = c, \nonumber \\ & & K
\succeq 0, \nonumber \\ & & K = \sum_{i=1}^m \mu_i \bv_i \bv_i^T,
\nonumber
\end{eqnarray}
or, according to (\ref{margindef}),
\begin{eqnarray}
\min_{K} \max_{\ba ~:~ \ba \geq 0, \ba^T \by = 0} & &
2\ba^T \be - \ba^T G (K_{tr}) \ba \label{appm-eq1} \\
\textrm{subject to} & & \textrm{trace}(K) = c, \nonumber \\ & & K
\succeq 0, \nonumber \\ & & K = \sum_{i=1}^m \mu_i \bv_i \bv_i^T.
\nonumber
\end{eqnarray}
Recall that $$ G(K_{tr}) = \textrm{diag}(\by) K_{tr}
\textrm{diag}(\by), $$ with
\begin{eqnarray}
K_{tr} & = & K(1:n_{tr},1:n_{tr}) \nonumber \\ & = & \sum_{i=1}^m
\mu_i K_i(1:n_{tr},1:n_{tr}) \nonumber \\ & = & \sum_{i=1}^m \mu_i
\bv_i(1:n_{tr}) \bv_i(1:n_{tr})^T \nonumber \\ & = & \sum_{i=1}^m
\mu_i \bar{\bv}_i \bar{\bv}_i^T, \nonumber
\end{eqnarray}
where $\bar{\bv}_i = \bv_i(1:n_{tr})$. Furthermore, because the
$\bv_i$ are orthonormal, the $\mu_i$ in $K = \sum_{i=1}^m \mu_i
\bv_i \bv_i^T$ are the eigenvalues of $K$. This implies
$$\textrm{trace}(K) = \sum_{i=1}^m \mu_i = \be^T \bmu$$ and $$K
\succeq 0 \Leftrightarrow \bmu \geq 0 \Leftrightarrow \mu_i \geq
0, \quad i = 1, \ldots, m.$$ We can thus write (\ref{appm-eq1})
as:
\begin{eqnarray}
\lefteqn{\min_{\bmu ~:~ \bmu \geq 0, \be^T \bmu = c} \ \ \max_{\ba
~:~ \ba \geq 0, \ba^T \by = 0} 2\ba^T\be - \ba^T
\textrm{diag}(\by) ( \sum_{i=1}^m \mu_i \bar{\bv}_i \bar{\bv}_i^T
) \textrm{diag}(\by) \ba} \nonumber
\\ & & = \min_{\bmu ~:~ \bmu \geq 0, \be^T \bmu = c} \ \ \max_{\ba ~:~ \ba \geq 0,
\ba^T \by = 0} 2\ba^T\be - \sum_{i=1}^m \mu_i \ba^T
\textrm{diag}(\by) \bar{\bv}_i \bar{\bv}_i^T \textrm{diag}(\by)
\ba \nonumber
\\ & & = \min_{\bmu ~:~ \bmu \geq 0, \be^T \bmu = c} \ \ \max_{\ba ~:~ \ba \geq 0,
\ba^T \by = 0} 2\ba^T\be -  \sum_{i=1}^m \mu_i \ba^T \breve{\bv}_i
\breve{\bv}_i^T \ba \nonumber
\\ & & = \min_{\bmu ~:~ \bmu \geq 0, \be^T \bmu = c} \ \ \max_{\ba ~:~ \ba \geq 0,
\ba^T \by = 0} 2\ba^T\be - \sum_{i=1}^m \mu_i (\breve{\bv}_i^T
\ba)^2 \nonumber
\\ & & = \max_{\ba ~:~ \ba \geq 0, \ba^T \by = 0} \ \ \min_{\bmu ~:~ \bmu \geq 0,
\be^T \bmu = c} 2\ba^T\be - \sum_{i=1}^m \mu_i (\breve{\bv}_i^T
\ba)^2 \nonumber
\end{eqnarray}
with $\breve{\bv}_i = \textrm{diag}(\by) ~ \bar{\bv}_i$.
%We used the
%property that $\textrm{trace}(AB) = \textrm{trace}(BA)$ (if the
%products are well-defined).

We interchanged the order of the minimization and the
maximization. Standard results in convex optimization \citep[see
e.g.,~][]{BoV:01} imply that we are allowed to do this and still
obtain the same optimal value, because the objective is convex in
$\bmu$ (it is linear in $\bmu$) and concave in $\ba$, because the
minimization problem is strictly feasible in $\bmu$, and the
maximization problem as well in $\ba$.  We thus obtain:
\begin{eqnarray}
\lefteqn{\max_{\ba ~:~ \ba \geq 0, \ba^T \by = 0} \ \ \min_{\bmu
~:~ \bmu \geq 0, \be^T \bmu = c} 2\ba^T\be - \sum_{i=1}^m \mu_i
(\breve{\bv}_i^T \ba)^2} \nonumber
\\ & & = \max_{\ba ~:~ \ba \geq 0, \ba^T \by = 0} \left[ 2\ba^T\be - \max_{\bmu ~:~ \bmu \geq 0,
\be^T \bmu = c} \left( \sum_{i=1}^m \mu_i (\breve{\bv}_i^T \ba)^2
\right) \right] \nonumber
\\ & & = \max_{\ba ~:~ \ba \geq 0, \ba^T \by = 0} \left[ 2\ba^T \be -
\max_{i} \left( c (\breve{\bv}_i^T \ba)^2 \right) \right].
\nonumber
\end{eqnarray}
This can be reformulated as follows:
\begin{eqnarray}
\max_{\ba, t} & & 2 \ba^T \be - c t \label{primalrev_hmsvm}
\\ \textrm{subject to} & & t \geq (\breve{\bv}_i^T \ba)^2, i = 1,
\ldots, m \nonumber \\ & & \ba^T \by = 0, \nonumber \\ & & \ba
\geq 0, \nonumber
\end{eqnarray}
which gives the result (\ref{eq:qp-margin}).

\fi

\iffalse

\section{Proof of Theorem \ref{th:optSM1}}\label{app-proof-SM1}

After substitution of $\omega_{S1}(K_{tr})$ as defined in
(\ref{dualsoftmargindef1}), (\ref{simpelprob_sm1}) becomes:
\begin{equation}\label{wo_simpelprob_sm1}
\min_{K \in\calK} \; \max_{\ba} \; 2\ba^T\be - \ba^T G (K_{tr})
\ba ~:~ C \geq \ba \geq 0, \;\; \ba^T\by = 0, \;\;
\textrm{trace}(K) = c,
\end{equation}
with $c$ a constant.

Assume that $K_{tr} \succ 0$, hence $G(K_{tr}) \succ 0$ (the
following can be extended to the general case). We note that
$\omega_{S1}(K_{tr})$ is convex in $K$ (it is the pointwise
maximum of affine functions of $K$). Given the convex constraints
in~(\ref{wo_simpelprob_sm1}), the optimization problem is thus
certainly convex in $K$. We write this as:

\begin{eqnarray}\label{sdp1_sm1}
\min_{K \in\calK, t} t  ~:~ & & t \geq \max_{\ba} \; 2\ba^T\be -
\ba^T G (K_{tr}) \ba, \nonumber \\ & & C \geq \ba \geq 0, \;\;
\ba^T\by = 0, \;\; \textrm{trace}(K) = c.
\end{eqnarray}
We will now express $t \geq \max_{\ba} \; 2\ba^T\be - \ba^T G
(K_{tr}) \ba$ as an LMI. This can be done in exactly the same way
as we did before for the hard margin: we express the constraint
using the dual minimization problem. This will allow us to drop
the minimization and use the Schur complement lemma to obtain an
LMI.

Define the Lagrangian of the maximization problem
(\ref{dualsoftmargindef1}) by
\[
{\cal L} (\ba,\bnu,\lambda,\bdelta) = 2\ba^T\be - \ba^T G (K_{tr})
\ba + 2\bnu^T\ba + 2\lambda \by^T\ba + 2 \bdelta^T(C\be - \ba),
\]
where $\lambda \in \mathbb{R}$ and $\bnu,\bdelta \in
\mathbb{R}^{n_{tr}}$. By duality, we have
\[
\omega_{S1}(K_{tr}) = \max_{\ba} \; \min_{\bnu \geq 0,\bdelta \geq
0,\lambda} \; {\cal L} (\ba,\bnu,\lambda,\bdelta) = \min_{\bnu
\geq 0,\bdelta \geq 0,\lambda} \; \max_{\ba} \; {\cal L}
(\ba,\bnu,\lambda,\bdelta),
\]
where $\bnu \geq 0 \Leftrightarrow \nu_i \geq 0$ for $i = 1,
\ldots, n_{tr}$, similarly for $\bdelta$. Since $G(K_{tr}) \succ
0$, at the optimum, we have
\[
\ba = G(K_{tr})^{-1}(\be+\bnu-\bdelta+\lambda \by),
\]
and can form the dual problem
\[
\omega_{S1}(K_{tr}) = \min_{\bnu, \; \bdelta, \; \lambda}  \;
(\be+\bnu-\bdelta+\lambda
\by)^TG(K_{tr})^{-1}(\be+\bnu-\bdelta+\lambda \by) + 2 C \bdelta^T
\be ~:~ \bnu \geq 0, \ \bdelta \geq 0.
\]
We obtain that for any $t > 0$, the constraint
$\omega_{S1}(K_{tr}) \leq t$ is true if and only if there exist
$\bnu \geq 0$, $\bdelta
> 0$ and $\lambda$ such that
\[
(\be+\bnu-\bdelta+\lambda
\by)^TG(K_{tr})^{-1}(\be+\bnu-\bdelta+\lambda \by) + 2 C \bdelta^T
\be \leq t,
\]
or, equivalently (using the Schur complement lemma), such that
\[
\left(
\begin{array}{cc}
  G(K_{tr}) & \be+\bnu-\bdelta+\lambda \by \\
  (\be+\bnu-\bdelta+\lambda \by)^T & t - 2 C
\bdelta^T \be
\end{array}\right) \succeq 0
\]
holds. Taking this into account, (\ref{sdp1_sm1}) can be expressed
as:
\begin{eqnarray}
\min_{K,t,\lambda,\bnu,\bdelta} & & \ t \\
\textrm{subject to} & & \ \textrm{trace}(K) = c, \nonumber \\
& & K \in\calK, \nonumber \\
& & \begin{pmatrix}
G(K_{tr}) & \be+\bnu-\bdelta+\lambda \by \\
(\be+\bnu-\bdelta+\lambda \by)^T & t - 2 C
\bdelta^T \be \end{pmatrix} \succeq 0, \nonumber \\
& & \bnu \geq 0 \nonumber \\
& & \bdelta \geq 0, \nonumber
\end{eqnarray}
which yields (\ref{sdpsoftmargin1}). Notice that $\bnu \geq 0
\Leftrightarrow \textrm{diag}(\bnu) \succeq 0$, and thus an LMI;
similarly for $\bdelta \geq 0$. $\Box$


\fi

\iffalse

\section{Proof of Result (\ref{eq:qp-margin-sm2})}\label{app-qp-SM2SVM}

For the case $K_i = \bv_i \bv_i^T$, with $\bv_i$ orthonormal, the
learning problem becomes
\begin{eqnarray}
\min_{K} & & \omega_{S2}(K_{tr}) \nonumber \\
\textrm{subject to} & & \textrm{trace}(K) = c, \nonumber \\ & & K
\succeq 0, \nonumber \\ & & K = \sum_{i=1}^m \mu_i \bv_i \bv_i^T,
\nonumber
\end{eqnarray}
or, according to (\ref{dualsoftmargindef2}),
\begin{eqnarray}
\min_{K} \max_{\ba ~:~ \ba \geq 0, \ba^T \by = 0} & &
2\ba^T \be - \ba^T \left( G (K_{tr}) + \frac{1}{C} I_{n_{tr}} \right) \ba \label{appm-eq1-SM2} \\
\textrm{subject to} & & \textrm{trace}(K) = c, \nonumber \\ & & K
\succeq 0, \nonumber \\ & & K = \sum_{i=1}^m \mu_i \bv_i \bv_i^T,
\nonumber
\end{eqnarray}
which is equivalent to
\begin{eqnarray}
\min_{K} \max_{\ba ~:~ \ba \geq 0, \ba^T \by = 0} & &
2\ba^T\be - \frac{1}{C} \ba^T \ba - \ba^T G (K_{tr}) \ba \label{app-qp-sm2} \\
\textrm{subject to} & & \textrm{trace}(K) = c, \nonumber \\ & & K
\succeq 0, \nonumber \\ & & K = \sum_{i=1}^m \mu_i \bv_i \bv_i^T.
\nonumber
\end{eqnarray}
Comparing this to (\ref{appm-eq1}), we see that both formulations
are identical except for the terms in the objective function that
only depend on $\ba$ (and not on the kernel matrix, i.e., not on
the weights $\mu_i$ for $K = \sum_{i=1}^m \mu_i \bv_i \bv_i^T$):
these are $2\ba^T \be - \frac{1}{C} \ba^T \ba$ in
(\ref{app-qp-sm2}) instead of only $2\ba^T\be$ in
(\ref{appm-eq1}). Those terms are conserved through the entire
further derivation of the hard margin case, as can easily be
checked in Appendix \ref{app-qp-HMSVM}. For this reason, the
result for the 2-norm soft margin case can be obtained by
replacing $2\ba^Te$ with $2\ba^Te - \frac{1}{C} \ba^T \ba$ in the
result (\ref{primalrev_hmsvm}) for the hard margin case. This
yields
\begin{eqnarray}
\max_{\ba, t} & & 2\ba^T\be - \frac{1}{C}\ba^T\ba - c t \nonumber
\\ \textrm{subject to} & & t \geq (\breve{\bv}_i^T \ba)^2, i = 1,
\ldots, m \nonumber \\ & & \ba^T \by = 0, \nonumber \\ & & \ba
\geq 0, \nonumber
\end{eqnarray}
with $\breve{\bv}_i = \textrm{diag}(\by) ~ \bar{\bv}_i=
\textrm{diag}(\by) ~ \bv_i(1:n_{tr})$. This is exactly
(\ref{eq:qp-margin-sm2}).

\fi

\section{Proof of Result (\ref{eq:qp-align})}\label{app-qp-align}

For the case $K_i = \bv_i \bv_i^T$, with $\bv_i$ orthonormal, the
original learning problem (\ref{sdp-align-learn}) becomes
\begin{eqnarray}
\max_{K} & & \left\langle K_{tr},\by\by^T \right\rangle_{F} \label{appqa-eq1} \\
\textrm{subject to} & & \left\langle K, K \right\rangle_{F} \leq 1, \nonumber \\
& & K\succeq 0, \nonumber \\ & & K = \sum_{i=1}^m \mu_i \bv_i
\bv_i^T. \nonumber
\end{eqnarray}
Expanding this further gives
\begin{eqnarray}
\left\langle K_{tr}, \by\by^T \right\rangle_{F} & = &
\textrm{trace} (K(1:n_{tr},1:n_{tr})\by\by^T)
\nonumber \\ & = & \textrm{trace} ((\sum_{i=1}^m \mu_i \bv_i(1:n_{tr}) \bv_i(1:n_{tr})^T)\by\by^T) \nonumber \\
& = & \sum_{i=1}^m \mu_i \textrm{trace}(\bar{\bv}_i \bar{\bv}_i^T
\by\by^T) \nonumber \\ & = & \sum_{i=1}^m \mu_i (\bar{\bv}_i^T
\by)^2, \label{simpl1} \\ \left\langle K, K \right\rangle_{F} & =
& \textrm{trace}(K^T K) \nonumber
\\ & = & \textrm{trace}(K K) \nonumber
\\ & = & \textrm{trace}((\sum_{i=1}^m \mu_i \bv_i
\bv_i^T)(\sum_{j=1}^m \mu_j \bv_j \bv_j^T)) \nonumber \\ & = &
\textrm{trace}(\sum_{i,j=1}^m \mu_i \mu_j \bv_i \bv_i^T \bv_j \bv_j^T) \nonumber \\
& = & \textrm{trace}(\sum_{i=1}^m \mu_i^2 \bv_i \bv_i^T) \nonumber \\
& = & \sum_{i=1}^m \mu_i^2 \textrm{trace}(\bv_i \bv_i^T) \nonumber \\
& = & \sum_{i=1}^m \mu_i^2 \textrm{trace}(\bv_i^T \bv_i) \nonumber \\
& = & \sum_{i=1}^m \mu_i^2 \label{simpl2}
\end{eqnarray}
with $\bar{\bv}_i = \bv_i(1:n_{tr})$. We used the fact that
$\textrm{trace} (ABC) = \textrm{trace} (BCA)$ (if the products are
well-defined) and that the vectors $\bv_i, i=1, \ldots, n$ are
orthonormal: $\bv_i^T \bv_j = \delta_{ij}$. Furthermore, because
the $\bv_i$ are orthogonal, the $\mu_i$ in $K = \sum_{i=1}^m \mu_i
\bv_i \bv_i^T$ are the eigenvalues of $K$. This implies
\begin{equation}\label{simpl3}
K \succeq 0 \Leftrightarrow \bmu \geq 0 \Leftrightarrow \mu_i \geq
0, \quad i = 1, \ldots, m.
\end{equation}
Using (\ref{simpl1}), (\ref{simpl2}) and (\ref{simpl3}) in
(\ref{appqa-eq1}), we obtain the following optimization problem:
\begin{eqnarray}
\max_{\mu_i} & &  \sum_{i=1}^m \mu_i (\bar{\bv}_i^T \by)^2 \nonumber \\
\textrm{subject to} & & \sum_{i=1}^m \mu_i^2 \leq 1 \nonumber \\
& & \mu_i \geq 0, \quad i=1, \ldots, m, \nonumber
\end{eqnarray}
which yields the result (\ref{eq:qp-align}).


\section{Proof of Theorem~\protect\ref{thm:transd}}
\label{appendix:errorbound}

For a function $g:{\cal X}\times{\cal Y}\to\mathbb{R}$, define
  \begin{eqnarray*}
    \hat \Expect_1 g(\bX,\bY) & = & \frac{1}{n} \sum_{i=1}^n
    g(\mathbf{x}_i,y_i), \\
    \hat \Expect_2 g(\bX,\bY) & = & \frac{1}{n} \sum_{i=1}^n
    g(\mathbf{x}_{n+i},y_{n+i}).
  \end{eqnarray*}

Define a margin cost function $\phi:\mathbb{R}\to\mathbb{R}^+$ as
  $$
    \phi(a) = \left\{ \begin{array}{ll}
      1 & \mbox{if $a\le 0$,}\\
      1-a & 0<a\le 1,\\
      0 & a>1. \end{array}\right.
  $$
Notice that in the 1-norm soft margin cost function,
the slack variable $\xi_i$ is a convex upper bound
on $\phi(y_if(x_i))$ for the kernel classifier $f$, that is,
 \[
   \max\left\{1-a,0\right\} \ge \phi(a) \ge \mathbf{1}\left[a\le
   0\right],
 \]
where the  last expression is the indicator function of $a\le 0$.

The proof of the first part is due to Koltchinskii and
Panchenko~\cite{KolPan02}, and involves the following five steps:

{\bf Step 1.} For any class $F$ of real functions defined on $\cal
X$,
  \[
    \sup_{f\in F} \mbox{\rm er}(f) - \hat \Expect_1
    \phi(Yf(\bX)) \le \sup_{f\in F} \hat \Expect_2\phi(Yf(\bX)) - \hat \Expect_1
      \phi(Yf(\bX)).
  \]
To see this, notice that er$(f)$ is the average over the test set
of the indicator function of $Yf(\bX)\le 0$, and that
$\phi(Yf(\bX))$ bounds this function.

{\bf Step 2.} For any class $G$ of $[0,1]$-valued functions,
  \[
    \Pr \left(\sup_{g\in G} \hat \Expect_2g -\hat \Expect_1 g
      \ge \Expect \left(\sup_{g\in G} \hat \Expect_2g
      -\hat \Expect_1 g\right) + \epsilon \right)
        \le \exp\left(\frac{-\epsilon^2n}{4}\right),
  \]
where the expectation is over the random permutation. This follows
from McDiarmid's inequality. To see this, we need to define the
random permutation $\pi$ using a set of $2n$ independent random
variables. To this end, choose $\pi_1,\ldots,\pi_{2n}$ uniformly
at random from the interval $[0,1]$. These are almost surely
distinct. For $j=1,\ldots,2n$, define $\pi(j)=|\{i:\pi_i\le
\pi_j\}|$, that is, $\pi(j)$ is the position of $\pi_j$ when the
random variables are ordered by size. It is easy to see that, for
any $g$, $\hat \Expect_2g -\hat \Expect_1 g$ changes by no more
than $2/n$ when one of the $\pi_i$ changes.  McDiarmid's
bounded difference inequality \citep{m-mbd-89}
implies the result.

{\bf Step 3.} For any class $G$ of $[0,1]$-valued functions,
  $$
    \Expect\left(\sup_{g\in G} \hat \Expect_2g -\hat
    \Expect_1 g\right)
     \le \hat R_{2n}(G) + \frac{4}{\sqrt{n}},
  $$
where $\hat R_{2n}(G) = \Expect \sup_{g\in G} \frac{1}{n}
\sum_{i=1}^{2n} \sigma_i g(\bX_i,Y_i),$ and the expectation is over
the independent, uniform, $\{\pm 1\}$-valued random variables
$\sigma_1,\ldots,\sigma_{2n}$. This result is essentially Lemma~3
of \citep{BaM:02}; that lemma contained a similar bound for
i.i.d.~data, but the same argument holds for fixed data,
randomly permuted.

{\bf Step 4.} If the class $F$ of real-valued functions defined on
$\cal X$ is closed under negations, $\hat R_{2n}(\phi\circ
F) \le
    \hat R_{2n}(F),$ where each $f\in F$ defines a $g\in\phi\circ F$ by
$g(\bx,y)=\phi(yf(\bx))$. This bound is the contraction
lemma of~\cite{LeT:91}.

{\bf Step 5.} For the class $F_\calK$ of kernel expansions,
notice (as in the proof of Lemma~26 of \cite{BaM:02}) that
  \begin{eqnarray*}
    \hat R_{2n}(F_\calK)
      & = & \frac{1}{n}\Expect \max_{f\in
        F_\calK}\sum_{i=1}^{2n}\sigma_i f(\bX_i) \\
      & = & \frac{1}{n}\Expect \max_{K\in\calK} \max_{\|\bw\|\le
      1/\gamma}
        \langle \bw,\sum_{i=1}^{2n}\sigma_i\Phi(\bX_i)\rangle \\
      & = & \frac{1}{n\gamma}\Expect \max_{K\in\calK} \left\|\sum_{i=1}^{2n}
        \sigma_i\Phi(\bX_i)\right\| \\
      & \le & \frac{1}{n\gamma}\sqrt{\Expect \max_{K\in\calK} \bsigma^TK\bsigma} \\
      & = & \frac{1}{n\gamma}\sqrt{\mathcal{C}(\calK)},
  \end{eqnarray*}
where $\bsigma=(\sigma_1,\ldots,\sigma_{2n})$ is the vector of
Rademacher random variables.

Combining gives the first part of the theorem. For the second part,
consider
  \[
    \mathcal{C}(\calK_c)=\Expect \max_{K\in\calK_c} \bsigma^T K \bsigma
      = \Expect \max_{\bmu} \sum_{j=1}^m \mu_j \bsigma^T K_j \bsigma,
  \]
where the max is over $\bmu=(\mu_1,\ldots,\mu_m)$ for which the
matrix $K=\sum_{j=1}^m\mu_jK_j$ satisfies the conditions $K\succeq
0$ and trace$(K)\le c$.  Now,
  \[
    \textrm{trace}(K)=\sum_{j=1}^m\mu_j\textrm{trace}(K_j),
  \]
and each trace in the sum is positive, so the supremum must be
achieved for $\textrm{trace}(K)=c$. So we can write
  \[
    \mathcal{C}(\calK_c) = c\Expect \max_{K\in\calK_c} \sum_{j=1}^m
    \bsigma^T
      \frac{K}{\textrm{trace}(K)} \bsigma.
  \]
Notice that $\bsigma^TK\bsigma$ is no more than
$\lambda\|\bsigma\|^2=n\lambda$, where $\lambda$ is the maximum
eigenvalue of $K$. Using $\lambda\le\mbox{\rm trace}(K)=c$ shows
that $\mathcal{C}(\calK_c)\le cn$.

Finally, for $\calK_c^+$ we have
  \begin{eqnarray*}
    \mathcal{C}(\calK_c^+)
      & = & \Expect\max_{\calK\in\calK_c^+} \bsigma^T K \bsigma \\
      & = & \Expect \max_{\mu_j} \sum_{j=1}^m \mu_j \bsigma^T K_j \bsigma \\
      & = & \Expect \max_j \frac{c}{\textrm{trace}(K_j)} \bsigma^T K_j \bsigma.
  \end{eqnarray*}
Since each term in the maximum is non-negative, we can replace it with
a sum to show that
  \begin{eqnarray*}
    \mathcal{C}(\calK_c^+)
      & \le & c \Expect\bsigma^T\left(\sum_j
        \frac{K_j}{\textrm{trace}(K_j)}\right) \bsigma \\
      & = & c m.
  \end{eqnarray*}
Alternatively, we can write
$\bsigma^TK_j\bsigma\le\lambda_j\|\bsigma\|=\lambda_j n$, where
$\lambda_j$ is the maximum eigenvalue of $K_j$. This shows that
  \[
    \mathcal{C}(\calK_c^+)
      \le c n\max_j \frac{\lambda_j}{\textrm{trace}(K_j)}.
  \]

\bibliography{refsgert}

\end{document}
