Algorithms for Learning Kernels Based on Centered Alignment

By Corinna Cortes, Mehryar Mohri, Afshin Rostamizadeh. 2012

627 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

A low variance consistent test of relative dependency (2014, background): “The problem of variable selection has also been investigated in the case of nonlinear relations between the inputs and outputs [1, 17], however this again does not address which of two variables most strongly influences a third.”
Similarity of Neural Network Representations Revisited (2019, background): “This normalized index is known as centered kernel alignment (Cortes et al., 2012; Cristianini et al., 2002): CKA(K,L) = HSIC(K,L)√ HSIC(K,K)HSIC(L,L) .”
Learning Kernels with Random Features (2016, background): “…or classes of kernels and either uses heuristic rules to combine kernels [2] [23], optimizes structured (e.g. linear, nonnegative, convex) compositions of the kernels with respect to an alignment metric [9] [16] [20] [28], or jointly optimizes kernel compositions with empirical risk [17] [20] [29].”
Entangled Watermarks as a Defense against Model Extraction (2020, methodology): “We compare these two neural networks through an analysis of (a) the frequency-of-activation patterns of neurons, and (b) their central kernel alignment (CKA) similarity [8,19] (i.”
Implicit Regularization via Neural Feature Alignment (2020, methodology): “Interestingly, in the presence of high level noise, the CKA reaches a much higher value during the learning phase (increase of test accuracy) for tangent kernels and labels evaluated for test than for train inputs (note test labels are not randomized).”
High-Dimensional Feature Selection by Feature-Wise Kernelized Lasso (2012, methodology): “The proposed method is closely related to the two-stage multiple kernel learning (MKL) method called centered kernel target alignment (cKTA) (Cortes et al. , 2012), which has been originally proposed for learning a kernel Gram matrix (not used for feature selection problems).”
A Survey of Modern Questions and Challenges in Feature Extraction (2015, neutral): “This can be done in an uncoupled manner, for instance tuning µ to maximize some statistical measure on sample kernel matrix K = ∑p i=1 µkKk, such as kernel alignment (Cortes et al., 2012).”
Riemannian Approaches in Brain-Computer Interfaces: A Review (2017, positive): “This cost can be interpreted as the (centered) kernel target alignment (KTA) criterion [55]–[57] used on the LogEuclidean metric (applied on the tangent space at G).”
Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks (2020, background): “In the past, statistical mechanics provided a useful theoretical framework for such typical-case analyses for various algorithms [23, 24, 25, 26, 27, 28, 29, 30, 31, 32].”
Large-scale kernel methods for independence testing (2016, background): “The key quantity we consider is the Hilbert–Schmidt independence criterion (HSIC) introduced by Gretton et al. (2005). HSIC uses the distance between the kernel embeddings of probability measures in the reproducing kernel Hilbert space (RKHS) (Gretton et al. 2008; Zhang et al. 2011; Smola et al. 200”
Do Wide and Deep Networks Learn the Same Things? Uncovering How Neural Network Representations Vary with Width and Depth (2020, methodology): “We use linear centered kernel alignment (Kornblith et al., 2019; Cortes et al., 2012) to measure similarity between neural network hidden representations.”
Why Do Better Loss Functions Lead to Less Transferable Features? (2020, methodology): “For a balanced dataset, R(2) is equivalent to centered kernel alignment [17, 18] between the embeddings and the one-hot label matrix, with a cosine kernel.”
Do Vision Transformers See Like Convolutional Neural Networks? (2021, background): “To answer these questions, we take every pair of layers X,Y within a model and compute their CKA similarity.”
Learning Attributes Equals Multi-Source Domain Generalization (2016, methodology): “1All kernels discussed in this paper have been centered [13].”