  This paper presents new and effective algorithms for learning kernels. In
particular, as shown by our empirical results, these algorithms consistently
outperform the so-called uniform combination solution that has proven to be
difficult to improve upon in the past, as well as other algorithms for learning
kernels based on convex combinations of base kernels in both classification and
regression. Our algorithms are based on the notion of centered alignment which
is used as a similarity measure between kernels or kernel matrices. We present
a number of novel algorithmic, theoretical, and empirical results for learning
kernels based on our notion of centered alignment. In particular, we describe
efficient algorithms for learning a maximum alignment kernel by showing that
the problem can be reduced to a simple QP and discuss a one-stage algorithm for
learning both a kernel and a hypothesis based on that kernel using an
alignment-based regularization. Our theoretical results include a novel
concentration bound for centered alignment between kernel matrices, the proof
of the existence of effective predictors for kernels with high alignment, both
for classification and for regression, and the proof of stability-based
generalization bounds for a broad family of algorithms for learning kernels
based on centered alignment. We also report the results of experiments with our
centered alignment-based algorithms in both classification and regression.
