## Learning the Kernel Matrix with Semidefinite Programming

**
***Gert R.G. Lanckriet, Nello Cristianini, Peter Bartlett, Laurent El Ghaoui, Michael I. Jordan*; 5(Jan):27--72, 2004.

### Abstract

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.

[abs][pdf][ps.gz][ps]