Learning the kernel matrix with semidefinite programming.

*(English)*Zbl 1222.68241Summary: 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.