betaFeedback

WorksComputer Science

The Confidence Score: a New Measure on Kernels

Abstract

Across a wide range of applications, kernel measures are used to tune hyperparameters, select among candidate kernels, and assess the suitability of kernels for specific learning tasks. For classification, kernel measures are used to predict which kernels may produce accurate kernel classifiers. Many existing kernel measures, such as alignment to the ideal kernel, are designed to reward kernels which captures all samples from the same class as similar. While effective in many settings, this requirement is unnecessarily restrictive for classification, where classes may exhibit substantial internal structure. In this work, the "Confidence Score", a new kernel measure, is proposed. Unlike alignment-to-the-ideal kernel measures, the Confidence Score measures the alignment between an encoding of the ground truth and that ground truth projected by the kernel, allowing kernels that preserve intra-class structure to achieve high scores. Through experiments, it is demonstrated that the Confidence Score exhibits a higher correlation with classification accuracy across a variety of kernels on both real-world and synthetic datasets, compared to select other kernel measures.

Introduction

Similarity is a fundamental concept in machine learning: similar things are clustered together, and similarity is the key concept in classification. The kernel, representing the inner product in some Hilbert space, is a mathematical tool that is used successfully in this domain to capture similarity between points [1, 2, 3, 4, 5, 6, 7, 8]. Learning algorithms obtain their information from the similarity encoded by the kernel; thus the potential performance can be assessed from a measure on that kernel.

Many approaches of generating kernels are possible; entire, potentially infinite families of kernels can be constructed. For example, many kernels have parameters that can be tuned (e.g. bandwidth) [8, 9, 10, 11], and some kernels are created by selecting and combining kernels into a new kernel, this is known as Multiple Kernel Learning (MKL) [6, 7, 12, 13, 14, 15, 16, 17, 18]. This creates an infinitely large search space of possible kernels. While kernels themselves measure similarity between data points, a measure on kernels is needed to evaluate a candidate kernel pulled from this search space.

For classification, the objective of a kernel measure is to identify kernels or kernel parameters that maximize accuracy. The evaluation of the kernel measure should be computationally less expensive than computing the classification accuracy on a training dataset. Kernel measures and their applications, ranging from classification to neural networks, have been extensively studied in the literature.

Kernel Alignment [12], and its notable refinement Centred Kernel Alignment (CKA) [18], measures how well a kernel ‘aligns’ with a learning target. The learning target is usually the ideal kernel, the kernel that measures the similarity between two points of the same class as 1, and −1 otherwise. To measure alignment with the ideal kernel is to assume that all points belonging to the same class are similar; that is, ‘similar ↔\leftrightarrow same class’. It is known that the CKA is not well-correlated with classification accuracy [6]. This problem is particularly pronounced in cases where the data is distributed following a multimodal class distribution, for example, if data belonging to one class is distributed across many isolated clusters, because the assumption of ‘similar ↔\leftrightarrow same class’ does not hold in this case. The kernel measure proposed in this work follows the ‘weaker’ assumption: if data points are similar, they should belong to the same class; that is, ‘similar →\to same class’.

We demonstrate that a kernel measure based on the ‘weaker’ assumption allows for the identification of more suitable kernels for classification. After a review of the mathematics behind kernels in § 2, the literature review follows in § 3. In § 4, the Confidence Score — a new kernel measure — is introduced, and § 5 presents experimental results evaluating its performance. The discussion of future work and conclusion are presented in § 6 and § 7 respectively.

Background on Mathematics for Kernel Measures

This section reviews the mathematical foundations of kernels, providing the basis for the introduction of kernel measures in the next section. For any dataset X\mathcal{X}, the kernel function K:X×X→R\mathcal{K} : \mathcal{X} \times\mathcal{X} \to\mathbb{R} implicitly defines a feature mapping ϕ:X→H\phi: \mathcal{X} \to\mathcal{H} that lifts the data from the input space to a ‘new’ feature space H\mathcal{H} following K(x,x′)=⟨ϕ(x),ϕ(x′)⟩\mathcal{K}(x,x') = \langle\phi(x),\phi(x')\rangle. By Mercer’s theorem, any positive semi-definite kernel function implies a mapping to a Hilbert space H\mathcal{H} [19], so the feature map ϕ\phi need not be explicitly defined. Decisions can be based solely on the inner product of pairwise combinations of data points. This is often referred to as the kernel trick. On a finite dataset X\mathcal{X} with JJ-many members, K\mathcal{K} can be represented by a J×JJ \times J kernel matrix K\mathbf{K} (also called the Gram Matrix) where Kij=K(xi,xj)K_{ij} = \mathcal{K}(x_i,x_j).

A classification function predicts the class label of a point x∗\mathbf{x}_*. Following the Representer theorem, orem [21], the optimal classifier can be represented as a linear combination of kernel evaluations

class⁡(x∗)=sign⁡(f(x∗)),f(x∗)=∑j=1Jαjk(x∗,xj),(1)\begin{aligned} \operatorname{class}(\mathbf{x}_*) &= \operatorname{sign}\left(f(\mathbf{x}_*)\right), \\ f(\mathbf{x}_*) &= \sum_{j=1}^{J} \alpha_j k(\mathbf{x}_*,\mathbf{x}_j), \tag*{(1)} \end{aligned}

allowing for direct solutions, e.g. with regularized regression α=(KTK+λI)−1KTy\boldsymbol{\alpha} = (\mathbf{K}^{\mathsf{T}}\mathbf{K} + \lambda\mathbf{I})^{-1}\mathbf{K}^{\mathsf{T}}\mathbf{y}. The solution generated by support vector machines (SVM) [20] also takes the form of Equation 1; in this case the coefficients αj\alpha_j are non-zero only for the support vectors ϕ(xj)\phi(\mathbf{x}_j), which are selected to maximize class separation in the Hilbert space.

The Frobenius inner product between two kernels of the same dimensions K,K′\mathbf{K},\mathbf{K}' is defined as

⟨ ⁣⟨K,K′⟩ ⁣⟩:=∑i,j=1JK^ijKij′(2)\langle\!\langle\mathbf{K},\mathbf{K}' \rangle\!\rangle:= \sum_{i,j=1}^{J} \widehat{K}_{ij}K'_{ij} \tag*{(2)}

where K^ij\widehat{K}_{ij} is the complex conjugate. As all kernel entries are real-valued in this work, the Frobenius inner product corresponds to the sum of the entries of the Hadamard product K∘K′\mathbf{K} \circ\mathbf{K}'. The inner product induces a norm ∥K∥F=⟨ ⁣⟨K,K⟩ ⁣⟩\lVert\mathbf{K}\rVert_F = \sqrt{\langle\!\langle\mathbf{K},\mathbf{K}\rangle\!\rangle} and has an associated metric on the space of all positive semi-definite J×JJ \times J matrices. To emphasise, within the context of Frobenius inner products or any measures on kernels (kernel measures), the space we are measuring in is not the Hilbert space created by a kernel function, but rather the space of all kernels that could be created on the dataset X\mathcal{X} (realized as the space spanned by all positive semi-definite J×JJ \times J matrices). Kernels measure similarity in the Hilbert space Hϕ\mathcal{H}_{\phi}, kernel measures are measured in the space spanned by all possible kernels.

Literature Review

As mentioned in the introduction, kernel measures offer a practical approach to assessing kernel quality without the need for repeated training and evaluation of models. Most kernel measures compare two kernels; in classification, this comparison is typically between a candidate kernel and a kernel encoding the ground truth. The ground truth may be encoded by the J×JJ \times J ‘ideal’ kernel matrix

Kideal,ij:={1if yi=yj−1else.K_{\mathrm{ideal},ij} := \begin{cases} 1 & \text{if } y_i = y_j \\ -1 & \text{else.} \end{cases}

or with a one-hot encoding resulting in a J×CJ \times C matrix

Gic:={1if yi=c0else.G_{ic} := \begin{cases} 1 & \text{if } y_i = c \\ 0 & \text{else.} \end{cases}

Note, under centring, a technique utilized by many kernel measures introduced below, Kideal≈GGT\mathbf{K}_{\mathrm{ideal}} \approx\mathbf{G}\mathbf{G}^{\mathsf{T}}.

A wide range of kernel measures have been proposed in the literature, many of which extend beyond classification tasks. These kernel measures can be grouped into alignment-based measures and non-alignment-based measures. Some non-alignment-based measures reduce to an alignment-based measure under particular parameter choices.

Kernel alignment was first proposed in [12]

KA⁡(K):=A(K,Kideal)=⟨⟨K,Kideal⟩⟩∥K∥F∥Kideal∥F.(3)\operatorname{KA}(\mathbf{K}) := A(\mathbf{K},\mathbf{K}_{\mathrm{ideal}}) = \frac{\langle\langle\mathbf{K},\mathbf{K}_{\mathrm{ideal}}\rangle\rangle}{\lVert\mathbf{K}\rVert_{F}\lVert\mathbf{K}_{\mathrm{ideal}}\rVert_{F}}. \tag*{(3)}

Kernel alignment is sensitive to the mean of the kernel [18]. As a result, kernels with larger means can obtain higher alignment scores even if they are not better suited for the given task.

Centred Kernel Alignment (CKA) was introduced in [18] to address this limitation by removing the mean component prior to computing the alignment. Since its introduction, CKA has given rise to a substantial body of work, with studies exploring both its theoretical properties and its practical utility across a wide range of machine learning tasks [8, 15, 22, 23, 24, 25, 26, 27, 37]. In CKA, both of the kernels to be evaluated must first be centred with

Kcent(x,x′)=⟨ϕ(x)−Ex[ϕ],ϕ(x′)−Ex′[ϕ]⟩=K(x,x′)−Ex[K(x,x′)]−Ex′[K(x,x′)]+Ex,x′[K(x,x′)].\begin{aligned} \mathcal{K}_{\mathrm{cent}}(\mathbf{x},\mathbf{x}') &= \langle\phi(\mathbf{x}) - E_{\mathbf{x}}[\phi], \phi(\mathbf{x}') - E_{\mathbf{x}'}[\phi]\rangle\\ &= \mathcal{K}(\mathbf{x},\mathbf{x}') - E_{\mathbf{x}}[\mathcal{K}(\mathbf{x},\mathbf{x}')] - E_{\mathbf{x}'}[\mathcal{K}(\mathbf{x},\mathbf{x}')] \\ &\quad+ E_{\mathbf{x},\mathbf{x}'}[\mathcal{K}(\mathbf{x},\mathbf{x}')]. \end{aligned}

In matrix form, this is

(Kcent)ij=Kij−1J∑g=1JKgj−1J∑h=1JKih+1J2∑g,h=1JKgh.(K_{\mathrm{cent}})_{ij} = K_{ij} - \frac{1}{J}\sum_{g=1}^{J}K_{gj} - \frac{1}{J}\sum_{h=1}^{J}K_{ih} + \frac{1}{J^{2}}\sum_{g,h=1}^{J}K_{gh}.

The alignment between the centred kernels is measured using the kernel alignment from Equation (3)

CKA⁡(K):=A(Kcent,Kideal, cent)=⟨⟨Kcent,Kideal, cent⟩⟩∥Kcent∥F∥Kideal, cent∥F.(4)\begin{aligned} \operatorname{CKA}(\mathbf{K}) &:= A(\mathbf{K}_{\mathrm{cent}},\mathbf{K}_{\mathrm{ideal,\,cent}}) \\ &= \frac{\langle\langle\mathbf{K}_{\mathrm{cent}},\mathbf{K}_{\mathrm{ideal,\,cent}}\rangle\rangle}{\lVert\mathbf{K}_{\mathrm{cent}}\rVert_{F}\lVert\mathbf{K}_{\mathrm{ideal,\,cent}}\rVert_{F}}. \tag*{(4)} \end{aligned}

The computational complexity of centering is O(J2)O(J^{2}), and computing the alignment between the centred kernels is also O(J2)O(J^{2}). Thus, the overall computational complexity of CKA is O(J2)O(J^{2}). CKA is invariant to both orthogonal transformation and isotropic scaling.

In classification problems, CKA has been used to tune kernel parameters [8, 11, 27] and for feature selection [23]. In [26], the CKA is used to measure the loss for incremental learning of a neural network for classification. However, CKA has applications beyond classifications as well. In neural network research, CKA has been used to study representational similarity and network interpretability [28, 32], to analyse learned kernel representations [29, 30, 31], and for architectural refinement [33]. CKA has been applied to molecular feature extraction [34], multiple kernel clustering [15], and for multiple information integration in medical research [37].

CKA is not without known shortcomings: by favouring kernels that assign high similarity to all pairs of samples from the same class, it can neglect important local structure in the data [6]. The work in [6] presents a solution to this in the form of a ‘Hybrid’ Kernel Alignment (HKA), a kernel measure which combines kernel alignment at the local and global scale. This work also presents an algorithm for learning a kernel which optimizes the HKA.

To measure HKA, the two kernels to be evaluated must be centred. The neighbourhood of xix_i is defined as the set Nk(xi)\mathcal{N}_k(x_i) of the kk nearest points to xix_i, where both the number of neighbours kk and the choice of distance metric are parameters that must be selected or tuned. A local kernel is defined for the neighbourhood of each xix_i

Kjk(i)={(Kcent)jkif xj,xk∈Nk(xi)0else.K_{jk}^{(i)} = \begin{cases} (K_{\mathrm{cent}})_{jk} & \text{if } x_j,x_k \in\mathcal{N}_k(x_i) \\ 0 & \text{else.} \end{cases}

The local kernel alignment (LKA) between a kernel and a local centred ideal kernel is

LKA(K):=Al(Kcent,Kideal,cent)=1J∑i=1J(⟨K(i),Kideal(i)⟩∥K(i)∥F∥Kideal(i)∥F).(5)\begin{aligned} \mathrm{LKA}(\mathbf{K}) &:= A_l(\mathbf{K}_{\mathrm{cent}},\mathbf{K}_{\mathrm{ideal},\mathrm{cent}}) \\ &= \frac{1}{J}\sum_{i=1}^{J}\left(\frac{\left\langle\mathbf{K}^{(i)},\mathbf{K}_{\mathrm{ideal}}^{(i)}\right\rangle}{\left\|\mathbf{K}^{(i)}\right\|_F\left\|\mathbf{K}_{\mathrm{ideal}}^{(i)}\right\|_F}\right). \tag*{(5)} \end{aligned}

Finally, the local kernel alignment is combined with the centred (global) kernel alignment following [18] with

HKA(K):=(1−λ)LKA(K)+λCKA(K).(6)\mathrm{HKA}(\mathbf{K}) := (1-\lambda)\mathrm{LKA}(\mathbf{K})+\lambda\mathrm{CKA}(\mathbf{K}). \tag*{(6)}

Thus, HKA requires the selection or tuning of the size of neighbourhood kk and of the trade-off parameter λ\lambda. In [6], this is performed empirically by fixing one parameter and varying the other to evaluate performance, with choice of parameters varying the final accuracy by up to 10% on their benchmark datasets.

The Hilbert-Schmidt Independence Criterion (HSIC) is a kernel measure used in some areas of research, such as neuroscience, that measures the difference between two distributions (represented by kernels)

HSIC(K,K′):=tr⁡(KK′)=∑i=1J∑j=1JKijKij′=⟨K,K′⟩.\begin{aligned} \mathrm{HSIC}(\mathbf{K},\mathbf{K}') := \operatorname{tr}(\mathbf{K}\mathbf{K}') \\ &= \sum_{i=1}^{J}\sum_{j=1}^{J}K_{ij}K'_{ij}=\left\langle\mathbf{K},\mathbf{K}'\right\rangle. \end{aligned}

This is the non-normalized foundational metric upon which CKA is built. HSIC measures the statistical independence between two variables by computing the norm of the cross-covariance operator in Reproducing Kernel Hilbert Spaces (RKHS). While HSIC calculates the absolute dependence, CKA is HSIC normalized to stay strictly between 0 and 1. Representational Similarity Analysis (RSA) [35] is a measure using the HSIC and taken between two ‘representational dissimilarity matrices’ (RDM), which are a special case of kernel. The work in [36] shows that if that kernel measure is the cosine similarity, and if the RDMs are centred, then RSA is equivalent to CKA

RSA⁡(K,K′):=tr⁡(KcentKcent′)∥Kcent∥F∥Kcent′∥F.\operatorname{RSA}(\mathbf{K},\mathbf{K}') := \frac{\operatorname{tr}(\mathbf{K}_{\mathrm{cent}}\mathbf{K}'_{\mathrm{cent}})}{\lVert\mathbf{K}_{\mathrm{cent}}\rVert_F\lVert\mathbf{K}'_{\mathrm{cent}}\rVert_F}.

Canonical Correlation Analysis (CCA) and its variants, including singular vector CCA [38] and projection-weighted CCA [39], are kernel measures to measure similarity between deep neural network representations. The work in [28] shows that these methods are closely related to CKA and demonstrates through experiments that CKA is a strong measure of similarity between deep neural network layers.

Feature Space-based Kernel Matrix Evaluation Measure (FSM) proposed in [40] is a kernel measure designed to capture the separability of the classes of data is in the kernel space using the class means and within-class variances. Additionally, Kernel Class Separability (KCS) [41] is based on the Fisher separability criterion (FSC) in the kernel feature space and is defined as FSC:=tr⁡(Sb)tr⁡(Sw)\mathrm{FSC}:=\frac{\operatorname{tr}(S_b)}{\operatorname{tr}(S_w)} where Sb=∑c=1C1∣Xc∣(ac−a)(ac−a)TS_b=\sum_{c=1}^{C}\frac{1}{|X^c|}(a_c-a)(a_c-a)^\mathsf{T} is the between class separability matrix and Sw=1J∑c=1C∑x∈Xc(ϕ(x)−ac)(ϕ(x)−ac)TS_w=\frac{1}{J}\sum_{c=1}^{C}\sum_{x\in X^c}(\phi(x)-a_c)(\phi(x)-a_c)^\mathsf{T} is the within class separability matrix, where aa is the mean in the kernel feature space. A regularized variant of the Fisher separability criterion is

RFSC(K):=tr⁡((Sw+λI)−1Sb).(7)\mathrm{RFSC}(\mathbf{K}) := \operatorname{tr}\left((S_w+\lambda I)^{-1}S_b\right). \tag*{(7)}

Maximum Margin Criterion (MMC), a kernel measure presented in [43], also captures binary class separability in the kernel feature space. FSM, FSC, and MMC rely on class-wise means, effectively favouring kernels that represent each class as a single cluster in the feature space. However, this construction may be restrictive, as it can disadvantage kernels that capture other class structures in the data.

Most of the aforementioned kernel measures reward kernels following overly restrictive requirements than needed for classification. In particular, FSM, FSC, and MMC assume distributions in which each class forms a cluster, and kernel alignment techniques assume that the ideal kernel represents the ideal class structure, following the ‘similar ↔ same class’ assumption. These measures may therefore fail to reward kernels that preserve within-class dissimilarities, which may be essential for capturing the underlying class structure of the data. Thus, there is an inconsistency between the objective of these kernel measures, which reward kernels for which all points from the same class are similar, and the requirements of an effective kernel for classification, which only require that highly similar points belong to the same class. This inconsistency is only exacerbated when one considers that many real-world datasets contain multimodal class structures [44, 45, 46]. Additionally, it has long been established that Gaussian mixture models provide an effective modelling framework for audio, speech, and image processing and classifications [47, 48], further reflecting the prevalence of multimodal class structure in practice.

A kernel measure that does not follow this assumption can be constructed by measuring the smoothness of a graph Laplacian. We take a kernel matrix to be the weights of the edges of a graph Kij=WijK_{ij}=W_{ij}. The associated graph Laplacian is L=D−WL=D-W [49]. The Laplacian quadratic form provides a measure of smoothness, capturing the extent to which large edge weights connect points of different classes [50]

GL⁡(K):=yTLy=12∑i=1J∑j=1JK(xi,xj)(yi−yj)2.(8)\operatorname{GL}(K) := \mathbf{y}^{\mathsf{T}}L\mathbf{y} = \frac{1}{2}\sum_{i=1}^{J}\sum_{j=1}^{J}\mathcal{K}(x_i,x_j)(y_i-y_j)^2. \tag*{(8)}

This kernel measure follows the ‘different class →\to dissimilar’ assumption, penalizing kernels that assign high similarity to points from different classes. A low GL suggests that there is low similarity between points of different classes. Within the context of classification, the difference between yiy_i and yjy_j reduces to 0 (yiy_i and yjy_j are the same label) or 1 (yiy_i and yjy_j are different labels). Thus, GL⁡(K):=12∑i=1J∑j=1JK(xi,xj)(1−(Kideal,0,1)ij)=12⟨K,1−Kideal0,1⟩\operatorname{GL}(K) := \frac{1}{2}\sum_{i=1}^{J}\sum_{j=1}^{J}\mathcal{K}(x_i,x_j)(1-(K_{\mathrm{ideal},0,1})_{ij}) = \frac{1}{2}\langle K,\mathbf{1}-K_{\mathrm{ideal}0,1}\rangle where 1\mathbf{1} is a J×JJ \times J all ones matrix.

There also exist kernel measures that evaluate properties other than the agreement between two kernels. One such measure is the Rademacher complexity [51], which evaluates the expressive capacity of the function class induced by the kernel. A kernel with high Rademacher complexity can induce classifiers that accurately fit random label assignments. This contrasts with most other kernel measures presented in this work, as it does not depend on the ground truth labels. While this provides greater expressive power, it also increases the risk of overfitting and does not necessarily indicate that the kernel is well suited to the classification task.

A New Measure on Kernels

The ‘similar ↔\leftrightarrow same class’ assumption used by kernel-alignment-based kernel measures is an overly restrictive assumption for classification that penalizes some kernels which capture multimodal class structure of the data. To achieve high classification accuracy (see Equation (1)), the kernel must induce sufficiently large similarity among pairs of points that contribute most strongly to the classification. Thus, the less restrictive assumption of ‘similar →\to same class’ is a better assumption for classification.

Consider a dataset of size J=8J = 8 comprising two balanced, multimodal classes. The ideal kernel and a minimal-information kernel, denoted Kmin⁡K_{\min}, are defined below; the latter contains only the information necessary to achieve perfect leave-one-out classification accuracy

Kideal=(1111000011110000111100001111000000001111000011110000111100001111),K_{\mathrm{ideal}} = \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix},
Kmin⁡=(1100000011000000001100000011000000001100000011000000001100000011).K_{\min} = \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{pmatrix}.

The minimal-information kernel has the property of ‘similar →\to same class’ but not the property of ‘similar ↔\leftrightarrow same class’.

When classifying following (1), both KidealK_{\mathrm{ideal}} and Kmin⁡K_{\min} can be used to construct a classifier with 100% leave-one-out accuracy. The ideal kernel has a CKA of 1 (trivially), but Kmin⁡K_{\min} has a CKA of 22(J−4)\frac{2}{\sqrt{2(J-4)}} (for J=8J = 8 this is only 0.577). Furthermore, although Kmin⁡K_{\min} can be used to achieve perfect classification accuracy for any number of points, as JJ approaches infinity, the CKA of Kmin⁡K_{\min} approaches 0.

It should be acknowledged that Kmin⁡K_{\min} could achieve a HKA of 1 with the selection of k=2k = 2 (the neighbourhood size) and λ=0\lambda= 0 (the trade-off between local and global structure). However, if the kernel measure itself must also be tuned, then the assessment of usefulness becomes dependent on additional dataset-specific parameters. In this case, the evaluation procedure effectively returns to the problem of kernel design (such as choosing the neighbourhood size) rather than independently assessing kernel quality.

The Confidence Score

We present the Confidence Score, which conceptually measures the alignment between the ground truth and the projection of the ground truth induced by the hollowed normalized kernel. The normalization and hollowing processes are as follows.

Symmetric Normalization The kernel is first symmetrically normalized with Knorm=D−12KD−12K_{\mathrm{norm}} = D^{-\frac{1}{2}} K D^{-\frac{1}{2}}, where DD is a diagonal matrix for which Dii=∑j=1JKijD_{ii} = \sum_{j=1}^{J} K_{ij}. Symmetric normalization scales the similarity between two points according to the relative local density of both points while preserving symmetry. Symmetric normalization preserves the intrinsic manifold geometry [55], and prevents points in dense regions from disproportionately influencing the alignment measure due solely to differences in local sampling density.

The largest eigenvalue of a symmetric normalized kernel is 1. Consequently, the induced linear operator is non-expansive in the Frobenius norm, ∥KnormA∥F≤∥A∥F\lVert K_{\mathrm{norm}}A\rVert_F \le\lVert A\rVert_F.

Hollowing When learning parametrized kernels, there is a risk of kernel degeneration: when a kernel approaches the identity matrix, the data becomes uncorrelated. To detect this behaviour, the candidate kernel is hollowed with H=Knorm−diag⁡(Knorm)\mathbf{H} = \mathbf{K}_{\mathrm{norm}} - \operatorname{diag}(\mathbf{K}_{\mathrm{norm}}). Hollowing removes self-similarity measures from the kernel, which do not provide information about the relationship between different samples and therefore do not contribute to classification. A degenerated kernel, once hollowed, becomes the zero matrix, and thus receives a Confidence Score of 0.

After hollowing, HG\mathbf{H}\mathbf{G} is referred to as the confidence matrix, where (HG)ic(\mathbf{H}\mathbf{G})_{ic} measures the total similarity of sample xix_i to other samples belonging to class cc. A high confidence value for sample xix_i and class cc indicates that xix_i has a high cumulative similarity to samples belonging to class cc. The Confidence Score is then obtained by measuring the alignment between the confidence matrix and the ground-truth matrix using the Frobenius inner product, providing an overall measure of how closely the confidence matrix agrees with the ground truth matrix. Unlike the CKA, which measures the alignment between the two J×JJ \times J kernels ⟨⟨Kcent,(GGT)cent⟩⟩\langle\langle\mathbf{K}_{\mathrm{cent}},(\mathbf{G}\mathbf{G}^{\mathsf{T}})_{\mathrm{cent}}\rangle\rangle, the Confidence Score measures the alignment in a J×CJ \times C space.

Definition 1 (Confidence Score) Given a candidate kernel K\mathbf{K} and the 11-hot encoding G\mathbf{G} of the ground truth class labels, the Confidence Score (CS) is defined as

CS⁡(K):=⟨⟨HG,G⟩⟩J∥HG∥F(9)\operatorname{CS}(\mathbf{K}) := \frac{\langle\langle\mathbf{H}\mathbf{G},\mathbf{G}\rangle\rangle}{\sqrt{J}\lVert\mathbf{H}\mathbf{G}\rVert_F} \tag*{(9)}

and 00 if ⟨⟨HG,G⟩⟩=∥HG∥F=0\langle\langle\mathbf{H}\mathbf{G},\mathbf{G}\rangle\rangle= \lVert\mathbf{H}\mathbf{G}\rVert_F = 0.

The algorithm efficiently computing the Confidence Score can be found in the Appendix.

Normalization and hollowing are of complexity O(J2)O(J^2) and computing Equation (9) for a fixed number of classes is also O(J2)O(J^2), thus the overall computational complexity is O(J2)O(J^2). Therefore, the CS has the same asymptotic order as the CKA [18], while HKA has the additional local alignment cost associated with the computation of the local neighbourhood kernel alignment for each point. Note that, of HKA and CS, only CS does not require parameter selection. It is well known that kernel methods, due to their O(J2)O(J^2) complexity, do not scale well. To use kernel methods on large datasets, the data is usually partitioned into smaller subsets to make the computation tractable. This method will be applied to large datasets in Section 5.1.

Error Bounds

To provide theoretical guarantees for the proposed Confidence Score, we derive an algebraic bound on the reconstruction error. In this section, we also describe the relationship between CS and normalized reconstruction error.

Algebraic Bounds For a PSD kernel matrix with maximum eigenvalue one, the discrepancy between the ground truth and its projection by the normalized kernel is bounded in terms of the Confidence Score.

The symmetric normalization Knorm=D12KD12\mathbf{K}_{\mathrm{norm}} = \mathbf{D}^{\frac{1}{2}}\mathbf{K}\mathbf{D}^{\frac{1}{2}} ensures that λmax⁡(Knorm)=1\lambda_{\max}(\mathbf{K}_{\mathrm{norm}}) = 1. Under these conditions, we derive an upper bound on the squared reconstruction error between ground truth G\mathbf{G} and its projection by the normalized kernel KnormG\mathbf{K}_{\mathrm{norm}}\mathbf{G}. The reconstruction error metric E\mathcal{E} is defined via the Frobenius norm. Expanding the Frobenius norm gives

E=∥G−KnormG∥F2=∥G∥F2−2⟨⟨G,KnormG⟩⟩+∥KnormG∥F2=J−2⟨G,KnormG⟩+∥KnormG∥F2.(10)\begin{aligned} \mathcal{E} &= \lVert\mathbf{G} - \mathbf{K}_{\mathrm{norm}}\mathbf{G} \rVert_F^2 \\ &= \lVert\mathbf{G} \rVert_F^2 - 2\langle\langle\mathbf{G}, \mathbf{K}_{\mathrm{norm}}\mathbf{G}\rangle\rangle+ \lVert\mathbf{K}_{\mathrm{norm}}\mathbf{G} \rVert_F^2 \\ &= J - 2\langle\mathbf{G}, \mathbf{K}_{\mathrm{norm}}\mathbf{G}\rangle+ \lVert\mathbf{K}_{\mathrm{norm}}\mathbf{G} \rVert_F^2. \tag*{(10)} \end{aligned}

Since Knorm\mathbf{K}_{\mathrm{norm}} is symmetric positive semi-definite with λmax⁡(Knorm)=1\lambda_{\max}(\mathbf{K}_{\mathrm{norm}}) = 1, its spectral norm satisfies ∥Knorm∥2=1\lVert\mathbf{K}_{\mathrm{norm}} \rVert_2 = 1. Consequently, multiplication by Knorm\mathbf{K}_{\mathrm{norm}} is a non-expansive linear operator on the Frobenius norm, thus ∥KnormG∥F≤∥G∥F=J\lVert\mathbf{K}_{\mathrm{norm}}\mathbf{G} \rVert_F \leq\lVert\mathbf{G} \rVert_F = \sqrt{J} and ∥KnormG∥F2≤J\lVert\mathbf{K}_{\mathrm{norm}}\mathbf{G} \rVert_F^2 \leq J. This property is used to bound the final term in (10)

E≤J−2⟨⟨G,KnormG⟩⟩+J=2J−2⟨⟨KnormG,G⟩⟩.\begin{aligned} \mathcal{E} &\leq J - 2\langle\langle\mathbf{G}, \mathbf{K}_{\mathrm{norm}}\mathbf{G}\rangle\rangle+ J \\ &= 2J - 2\langle\langle\mathbf{K}_{\mathrm{norm}}\mathbf{G}, \mathbf{G}\rangle\rangle. \end{aligned}

Matrix W=diag⁡(Knorm)\mathbf{W} = \operatorname{diag}(\mathbf{K}_{\mathrm{norm}}) is the diagonal matrix containing the self-similarities, so that Knorm=H+W\mathbf{K}_{\mathrm{norm}} = \mathbf{H} + \mathbf{W}. Consequently, ⟨⟨KnormG,G⟩⟩=⟨⟨HG,G⟩⟩+⟨⟨WG,G⟩⟩\langle\langle\mathbf{K}_{\mathrm{norm}}\mathbf{G}, \mathbf{G}\rangle\rangle= \langle\langle\mathbf{H}\mathbf{G}, \mathbf{G}\rangle\rangle+ \langle\langle\mathbf{W}\mathbf{G}, \mathbf{G}\rangle\rangle, and

E≤2J−2⟨⟨HG,G⟩⟩−2⟨⟨WG,G⟩⟩.\mathcal{E} \leq2J - 2\langle\langle\mathbf{H}\mathbf{G}, \mathbf{G}\rangle\rangle- 2\langle\langle\mathbf{W}\mathbf{G}, \mathbf{G}\rangle\rangle.

Substituting the definition of the Confidence Score, ⟨⟨G,HG⟩⟩=CS⁡(K)J∥HG∥F\langle\langle\mathbf{G}, \mathbf{H}\mathbf{G}\rangle\rangle= \operatorname{CS}(\mathbf{K})\sqrt{J}\lVert\mathbf{H}\mathbf{G}\rVert_F, and the identity ⟨⟨WG,G⟩⟩=tr⁡(Knorm)\langle\langle\mathbf{W}\mathbf{G}, \mathbf{G}\rangle\rangle= \operatorname{tr}(\mathbf{K}_{\mathrm{norm}}), bounds the final error in terms of the CS

E≤2J−2CS⁡(K)J∥HG∥F−2tr⁡(Knorm).\mathcal{E} \leq2J - 2\operatorname{CS}(\mathbf{K})\sqrt{J}\lVert\mathbf{H}\mathbf{G}\rVert_F - 2\operatorname{tr}(\mathbf{K}_{\mathrm{norm}}).

Thus, the reconstruction error is upper bounded by a quantity that depends explicitly on the Confidence Score, together with the magnitude of the hollowed Confidence matrix and the self-similarity contribution.

Relationship between CS and Normalized Reconstruction Error. In contrast to the reconstruction error explored in 4.2, the normalized reconstruction error between the modified Confidence matrix and the ground truth can also be considered, as

E=∥HG−G∥F∥G∥F=∥HG−G∥FJ.E = \frac{\lVert HG-G\rVert_F}{\lVert G\rVert_F} = \frac{\lVert HG-G\rVert_F}{\sqrt{J}}.

This formulation permits a direct geometric relationship between the reconstruction error and the Confidence Score to be established. Let rr denote the relative magnitude of the modified confidence matrix,

r=∥HG∥F∥G∥F=∥HG∥FJ.r = \frac{\lVert HG\rVert_F}{\lVert G\rVert_F} = \frac{\lVert HG\rVert_F}{\sqrt{J}}.

Using the definition of the Confidence Score from Equation (9), the squared normalized reconstruction error can be expanded as

E2=∥HG−G∥F2J=∥HG∥F2+∥G∥F2−2⟨⟨G,HG⟩⟩J=r2+1−2rCS⁡(K)\begin{aligned} E^2 &= \frac{\lVert HG-G\rVert_F^2}{J} \\ &= \frac{\lVert HG\rVert_F^2+\lVert G\rVert_F^2-2\langle\langle G,HG\rangle\rangle}{J} \\ &= r^2+1-2r\operatorname{CS}(K) \end{aligned}

Thus, the normalized reconstruction error is related exactly to the Confidence Score and the relative magnitude rr of the modified Confidence matrix. In particular, the Confidence Score captures the alignment between HGHG and GG, while rr accounts for their relative magnitude.

Boundary-Case Kernels

When selecting from a set of candidate kernels, a kernel measure should predict which kernel will produce the most accurate classifier. In this evaluation, a set of kernels is constructed from the kernels KidealK_{\mathrm{ideal}} and Kmin⁡K_{\min} with the addition of the ‘degenerated’ kernel KidentK_{\mathrm{ident}} (the identity matrix).

The CS, CKA, RFSC, and the leave-one-out accuracy for each of the three kernels are presented in Table 1. HKA is not included as it would require the additional tuning of kk and λ\lambda. RFSC is included to provide a comparison to kernel measures designed to reward kernels for which each class of data is distributed around a class mean. Included are kernel measures for a dataset of size J=2NJ=2N, N∈Z+N\in\mathbb{Z}^{+}, N≥2N\ge2 as well as the limits for these measures as J→∞J\to\infty.

CKARFSCCSAcc.
Kideal\mathbf{K}_{\mathrm{ideal}}11(1)(1)C−1C\frac{C-1}{C}(C−1λ)\left(\frac{C-1}{\lambda}\right)Eq 11(1)(1)11
Kmin⁡\mathbf{K}_{\min}22J−4\frac{2}{\sqrt{2J-4}}(0)(0)C−1J\frac{C-1}{J}(0)(0)11(1)(1)11
Kident\mathbf{K}_{\mathrm{ident}}1J−1\frac{1}{\sqrt{J-1}}(0)(0)C−1J\frac{C-1}{J}(0)(0)00(0)(0)00

Table 1. The CKA from Equation (2), RFSC from Equation (7), CS from Equation (9), and leave-one-out classification accuracy using three example kernels. The limit as J→∞J \to\infty is presented in parentheses.

Trivially, when the candidate kernel is the ideal kernel, the CKA and the accuracy are equal to 1. The Confidence Score for the ideal kernel is

CS⁡(Kideal)=1/3J−1/12CJ1/9J−5/96C(11)\operatorname{CS}(K_{\mathrm{ideal}})=\frac{1/3J-1/12C}{\sqrt{J}\sqrt{1/9J-5/96C}} \tag*{(11)}

which converges to 1 as J→∞J\to\infty. The kernel Kmin⁡K_{\min} also achieves perfect classification accuracy for all values of JJ, yet this is not captured by the CKA or the RFSC as lim⁡J→∞CKA⁡(Kmin⁡)=0\lim_{J\to\infty}\operatorname{CKA}(K_{\min})=0 and lim⁡J→∞RFSC⁡(Kmin⁡)=0\lim_{J\to\infty}\operatorname{RFSC}(K_{\min})=0.

We show that, by construction, for all values of JJ, CS⁡(Kmin⁡)=1\operatorname{CS}(\mathbf{K}_{\min}) = 1. After normalization and hollowing, Hmin⁡\mathbf{H}_{\min} takes the form of a block-diagonal matrix whose diagonal blocks are 14(0110)\frac{1}{4}\begin{pmatrix}0 & 1 \\ 1 & 0\end{pmatrix} on the diagonal. Consequently, Hmin⁡G=14G\mathbf{H}_{\min}\mathbf{G} = \frac{1}{4}\mathbf{G}. Thus, ⟨⟨Hmin⁡G,G⟩⟩=J4\langle\langle\mathbf{H}_{\min}\mathbf{G},\mathbf{G}\rangle\rangle= \frac{J}{4}, and ∥Hmin⁡G∥F=J4\|\mathbf{H}_{\min}\mathbf{G}\|_{F} = \frac{\sqrt{J}}{4}. Substituting these into the definition of the Confidence Score gives

CS⁡(Kmin⁡)=J4JJ4=1.\operatorname{CS}(\mathbf{K}_{\min}) = \frac{\frac{J}{4}}{\sqrt{J}\frac{\sqrt{J}}{4}} = 1.

Additionally, in cases where J≫CJ \gg C, CS⁡(Kideal)≈1\operatorname{CS}(\mathbf{K}_{\mathrm{ideal}}) \approx1. Thus, among these example kernels, the Confidence Score remains correlated with classification accuracy, unlike CKA.

Evaluation of the Confidence Score

This section compares the performance of the Confidence Score to other kernel measures. First, a comparison of the usage of CKA and the CS to tune kernel parameters is presented, followed by a comparison of their use for selecting a kernel from a pool. Finally, two synthetic datasets are used to illustrate how kernels capture similarity and class structure, and how that relates to the kernel measures and classification accuracy.

This evaluation primarily focuses on the comparison of the Confidence Score with kernel-alignment-based measures. The regularized Fisher Separability Criterion (RFSC) was included as a representative of class-separability-based kernel measures. Although other kernel measures were considered, they were not included in the final numerical evaluation due to computational complexity or weak statistical correlation with classification accuracy in preliminary experiments.

A family of kernels can be obtained from a base kernel function by varying its parameters or changing metrics. The following evaluations are performed using four families of kernels,

  1. The variable-bandwidth Gaussian family of kernels,

Kb(xi,xj)=exp⁡(−dij22σ2b2)(12)\mathcal{K}_{b}(\mathbf{x}_{i},\mathbf{x}_{j}) = \exp\left(-\frac{d_{ij}^{2}}{2\sigma^{2}b^{2}}\right) \tag*{(12)}

where bb is the tunable bandwidth and dijd_{ij} is the distance between xi\mathbf{x}_{i} and xj\mathbf{x}_{j}, usually Euclidean. This kernel is stationary as it depends only on the distance between points.

  1. The Matérn family of kernels, a popular choice of kernel [57, 59, 60]

Kρ(xi,xj)=σ221−νΓ(ν)(2νdijρ)νKν(2νdijρ)\mathcal{K}_{\rho}(\mathbf{x}_i,\mathbf{x}_j)=\sigma^2\frac{2^{1-\nu}}{\Gamma(\nu)}\left(\frac{\sqrt{2\nu}d_{ij}}{\rho}\right)^\nu K_\nu\left(\frac{\sqrt{2\nu}d_{ij}}{\rho}\right)

where Γ\Gamma is the gamma function, KνK_\nu is the modified Bessel function of the second kind, and ρ\rho and ν\nu are tunable parameters. To simplify the kernel computation, only three special cases of Matérn kernel are considered where ν∈{12,32,52}\nu\in\left\{\frac{1}{2},\frac{3}{2},\frac{5}{2}\right\}. In these cases, the Bessel function has a simple closed-form expression, and ρ\rho is the tunable parameter.

  1. The Local Variable-Bandwidth Gaussian (LVBG) family of kernels

s(xi,xj)={1if i=je−(dij−li)2σi2if xj∈NK(xi)0else,(13)s(\mathbf{x}_i,\mathbf{x}_j)= \begin{cases} 1 & \text{if } i=j\\ e^{-\frac{(d_{ij}-l_i)^2}{\sigma_i^2}} & \text{if } \mathbf{x}_j\in\mathcal{N}_K(\mathbf{x}_i)\\ 0 & \text{else,} \end{cases} \tag*{(13)}
K(xi,xj)=s(xi,xj)+s(xj,xi)−s(xi,xj)s(xj,xi)(14)\mathcal{K}(\mathbf{x}_i,\mathbf{x}_j)=s(\mathbf{x}_i,\mathbf{x}_j)+s(\mathbf{x}_j,\mathbf{x}_i)\\ \qquad{}-s(\mathbf{x}_i,\mathbf{x}_j)s(\mathbf{x}_j,\mathbf{x}_i) \tag*{(14)}

where dijd_{ij} is a distance metric (in this work, either Euclidean or Manhattan), and lil_i is the distance to the first nearest neighbour of xi\mathbf{x}_i.

  1. The Local Variable-Bandwidth Laplacian (LVBL) kernel, previously explored in [61] and as used for dimensionality reduction in [62]

s(xi,xj)={1if i=je−dij−liσiif xj∈Nk(xi)0else.(15)s(\mathbf{x}_i,\mathbf{x}_j)= \begin{cases} 1 & \text{if } i=j\\ e^{-\frac{d_{ij}-l_i}{\sigma_i}} & \text{if } \mathbf{x}_j\in\mathcal{N}_k(\mathbf{x}_i)\\ 0 & \text{else.} \end{cases} \tag*{(15)}

where again dijd_{ij} is a distance metric, and lil_i is the distance to the first nearest neighbour of xi\mathbf{x}_i. The kernel is symmetrized as in equation 14.

Note that both the LVBG and the LVBL kernels have an automatic bandwidth selection; the local bandwidth σi\sigma_i is computed to satisfy ∑i=1Js(xi,xj)=log⁡2(K)\sum_{i=1}^{J}s(\mathbf{x}_i,\mathbf{x}_j)=\log_2(K) for each neighbourhood. These kernels create families by varying parameters such as the neighbourhood size and the distance metric.

In the evaluations below, classification is performed following the regularization solver presented in Equation (1), in § 5.1 SVMs are also utilized for comparison. All accuracy measurements are computed using leave-one-out testing, resulting in a deterministic measure of accuracy. In addition to synthetic data, some experiments use datasets from the UCI Machine Learning Repository [63] and the MNIST dataset [64], the metadata for which can be found in Table 2.

Dataset NameSizeDimensionsNum. Classes
Banknote137242
Bioddeg1055412
Diabetes76882
Glass21497
Heart270132
Iris15043
Lympho148184
Sonar208602
Vowel5281011
Wine178133
Yeast1484810
Australian690142
Balance62543
Haberman30632
Monks43262
Vehicle94184
MNIST20 00078410

Table 2. A summary of the datasets used in this research.

Tuning Kernel Bandwidth

One of the key applications kernel measures is their usage in tuning continuous kernel parameters (e.g. the bandwidth of a Gaussian kernel) [8, 9, 10, 11]. In kernel parameter tuning, the kernel with the parameter(s) that maximizes the kernel measure is expected to achieve the highest classification accuracy.

Eight datasets were selected for this demonstration (see Table 3): six from the UCI Machine Learning Repository (see Table 2) and two synthetic datasets (see Figure 3). For each dataset, Gaussian kernels (Equation (12)) were constructed over a range of bandwidths, and for each kernel, the kernel measures (CKA and CS) and the corresponding classification accuracy were computed. The kernel measures and their maxima are presented in Figure 1, while Table 3 compares the maximum classification accuracy with the accuracy obtained at the bandwidth selected by each kernel measure.

DatasetAccuracy at Max CKAAccuracy at Max CSMax Accuracy
Clusters0.9220.9670.978
Moons0.9190.9810.986
Iris0.9510.9730.982
Glass0.7710.8930.899
Wine0.9780.9890.989
Lympho0.7740.9220.926
Sonar0.7070.8410.870
Monks0.8500.9630.958

Table 3. Classification accuracy (from regularized regression classifier) determined by bandwidth from maximum kernel measures compared to maximum accuracy across all bandwidths, from data presented in Figure 3.

Figure 1. The CS, CKA, and leave-one-out classification accuracy over a range of bandwidth values on eight datasets. The maxima of the CS and CKA are denoted by purple diamonds. Since there is no unique maximum classification accuracy for most datasets, the maximum accuracy is not marked.

‘Clusters’ dataset

(a) ‘Clusters’ dataset.

‘Noisy Crescent Moon’ dataset

(b) ‘Noisy Crescent Moon’ dataset.

Figure 3. Synthetic datasets.

To demonstrate the capabilities of the CS on large datasets, we present the Gaussian kernel bandwidth tuning experiment on the MNIST dataset, where the data are partitioned into 10 subsets of 2000 points each. Figure 2 presents the classification accuracy, CKA, and CS for each partition, as well as the mean curve for each metric. Not only does the CS consistently identify the bandwidth which produces higher classification accuracy for all partitions, but the CS varies less between partitions (average variance 1.4×10−31.4 \times10^{-3} along curve) than the CKA (average variance 3.5×10−33.5 \times10^{-3} along curve).

The CS, CKA, and leave-one-out classification accuracy of a Gaussian kernel classifier across a range of bandwidth values on 10 partitions of the MNIST dataset

Figure 2. The CS, CKA, and leave-one-out classification accuracy of a Gaussian kernel classifier across a range of bandwidth values on 10 partitions of the MNIST dataset.

From these experiments we observe that the CS consistently identifies a bandwidth that achieves an accuracy closer to the maximum than the CKA. Furthermore, the trends observed in the classification accuracy in Figure 1 and Figure 2 more closely resemble those of the CS than those of the CKA.

Kernel Selection

Another application of kernel measures is their use for the selection of the ‘best’ kernel from a finite pool of kernels. This can be used to select a kernel for a kernel classifier [12, 65], as a preprocessing step in Multiple Kernel Learning (MKL) to reduce a pool of candidate kernels [23, 58], or as part of the objective function in MKL [6, 7, 13, 14, 15, 16, 17, 18, 26]. For this experiment, the correlation between classification accuracy and each kernel measure is evaluated over a pool of 20 kernels consisting of:

  • Gaussian kernels with bandwidths b∈{0.1,0.3,0.5,0.7,0.9,1.0,1.5,2.0,2.5,3.0}b \in\{0.1, 0.3, 0.5, 0.7, 0.9, 1.0, 1.5, 2.0, 2.5, 3.0\},

  • Matérn kernels with ν∈{12,32,52}\nu\in\left\{\frac{1}{2}, \frac{3}{2}, \frac{5}{2}\right\},

  • three locally scaled Gaussian kernels (constructed using Euclidean distance) with number of neighbours k∈{5,10,J}k \in\{5, 10, \sqrt{J}\}, and

  • three locally scaled Laplacian kernels (constructed using Manhattan distance) with number of neighbours k∈{5,10,J}k \in\{5, 10, \sqrt{J}\}.

This pool of kernels was constructed on 15 of the benchmark datasets from the UCI Machine Learning Repository [63] listed in Table 2.

The correlation between classification accuracy and CS, CKA, and RFSC was computed across the set of datasets. The statistical significance of differences between the correlations was evaluated using the Cocor package for R [66]. The null hypothesis was that the CS is not more strongly correlated with classification accuracy than the other kernel measure (CKA or RFSC). Since Cocor performs several tests for comparing dependent correlations, Table 4 reports the maximum p-value returned across all tests. A result was considered significant only if all tests rejected the null hypothesis at α=0.05\alpha= 0.05. All tested datasets in Table 4 rejected the null hypothesis, suggesting that the CS is more strongly correlated with classification accuracy than the CKA and RFSC.

Datasetp-value CS vs CKAp-value CS vs RFSC
Banknote0.00182–
Biodeg0.000010.00060
Diabetes0.000000.00917
Glass0.000040.00000
Heart0.000050.00033
Iris0.000010.00000
Lympho0.000090.00010
Sonar0.003100.00015
Vowel0.000450.00000
Wine0.000630.00000
Yeast0.000220.00000
Australian0.009700.00037
Balance0.000140.00124
Haberman0.000000.00088
Monks0.016060.00000

Table 4. Maximum p-value obtained from the Cocor tests comparing the correlation of classification accuracy with CS against the corresponding correlations obtained with CKA and RFSC.

Capturing the Intra-Class Structure on Synthetic Multimodal Datasets

This section examines the relationship between classification accuracy and kernel measures across different kernel types, evaluating their ability to serve as absolute criteria for kernel selection.

The two synthetic datasets presented in Figure 3 were designed with multimodal class structures to illustrate how the Confidence Score captures such structure. Figure 3.a presents the ‘Clusters’ dataset; each class consists of three Gaussian clusters, and Figure 3.b presents the ‘Noisy Crescent Moons’ dataset, where the data is distributed in intertwined crescent shapes with added noise. Figure 4.a and 4.d present heat maps of the ideal kernels constructed for the ‘Clusters’ and ‘Noisy

Figure 4.a

(a) a

Figure 4.b

(b) b

Figure 4.c

(c) c

Figure 4.d

(d) d

Figure 4.e

(e) e

Figure 4.f

(f) f

Figure 4. Heat maps of kernels on the ‘Clusters’ dataset (top) and ‘Noisy Crescent Moons’ dataset (bottom). The ideal kernels are on the left, the LVBL kernels in centre, and the Learned to Align with the Ideal (LAI) kernels [14] are on the right. Blue indicates minimum similarity and red indicates maximum similarity.

Crescent Moons’ datasets, respectively. Figure 4.b and 4.e present a heat map of the LVBL kernels (see Equation (15)) for these datasets. Figure 4.c and 4.f present the kernels learned by maximizing the Centred Kernel Alignment following [14]; we refer to this as the Learn to Align with the Ideal (LAI) kernel.

Table 5 compares kernel measures (CS, CKA, LKA, HKA1) and leave-one-out classification accuracy for the LVBL and LAI kernels on the ‘Clusters’ and ‘Noisy Crescent Moon’ datasets. On the ‘Clusters’ dataset, the LAI kernel has a higher alignment to the ideal (CKA = 0.283, LKA = 0.543, HKA = 0.413) than the LVBL kernel (CKA = 0.190, LKA = 0.426, HKA = 0.308). This ordering is preserved no matter the value of λ\lambda. However, when comparing the Confidence Score, the LAI kernel has a lower Confidence Score (CS = 0.898) than the LVBL kernel (CS = 0.937). As the LVBL kernel has the higher leave-one-out accuracy (0.967) than the LAI kernel (0.922), the CS is a better predictor of accuracy for these kernels on the ‘Clusters’ dataset. The same pattern is evident for the ‘Noisy Crescent Moons’ dataset.

CSCKALKAHKAAcc.
Cluster LVBL0.9370.1900.4260.3080.978
Clusters LAI0.8980.2830.5430.4130.933
Moons LVBL0.8670.1580.3780.2680.961
Moons LAI0.8210.2590.4870.3730.931

Table 5. Ideal kernel alignment-based and confidence based kernel measures on kernels, classification accuracy, on synthetic datasets from Fig. 3.

Future Work

Centered Kernel Alignment has found applicability in evaluating kernels induced by neural networks [28, 29, 31]. Future work may investigate the use of CS as a measure of how well neural network representations capture the underlying class structure at different stages of the network. Additional future work will investigate the use of the CS in an objective function for Multiple Kernel Learning. A further direction for future research is to extend the theoretical analysis by following the approach of [18] to derive tighter error bounds.

Conclusion

In Section 5, we compared the performance of the Confidence Score to other kernel measures, finding in many cases that it was a better predictor of kernel classification accuracy. When used for kernel bandwidth tuning, the Confidence Score consistently identified bandwidths that produced kernels with higher classification accuracy than the bandwidths identified by Centred Kernel Alignment. Similarly, when used for kernel selection, the Confidence Score consistently identified kernels with higher classification accuracy and exhibited higher correlation to classification accuracy than kernel alignment-based measures and the regularized Fisher Separability Criterion. These results suggest the ‘similar →\to same class’ used by the Confidence Score assumption allows for the identification of more accurate kernels than the ‘similar ↔\leftrightarrow same class’ assumption or the ‘single-cluster-per-class’ assumption used by other kernel measures.

Although the proposed Confidence Score demonstrated strong agreement with classification performance across the evaluated problems, the conclusions of this study are necessarily limited by the kernel families and datasets considered.

Algorithm

Algorithm 1 computes the Confidence Score directly without explicitly constructing the hollowed matrix.

Algorithm 1 Fast computation of the Confidence Score

Require: Normalized kernel matrix K∈RJ×J\mathbf{K} \in\mathbb{R}^{J \times J}; class matrix G∈RJ×C\mathbf{G} \in\mathbb{R}^{J \times C}

Ensure: Confidence Score

  1. innerprod←0\mathrm{innerprod} \leftarrow0

  2. norm←0\mathrm{norm} \leftarrow0

  3. for i←1i \leftarrow1 to JJ do

    1. for j←1j \leftarrow1 to CC do

      1. s←0s \leftarrow0

      2. for k←1k \leftarrow1 to JJ do

        1. if i≠ki \ne k then

          1. s←s+KikGkjs \leftarrow s + K_{ik}G_{kj}

        2. end if

      3. end for

      4. norm←norm+s2\mathrm{norm} \leftarrow\mathrm{norm} + s^2

      5. innerprod←innerprod+sGij\mathrm{innerprod} \leftarrow\mathrm{innerprod} + sG_{ij}

    2. end for

  4. end for

  5. if innerprod≤ϵ\mathrm{innerprod} \le\epsilon then

    1. return 00

  6. end if

  7. return innerprodJnorm\dfrac{\mathrm{innerprod}}{\sqrt{J}\sqrt{\mathrm{norm}}}

References

  1. [1]J. Zhang, M. Marszałek, S. Lazebnik, and C. Schmid, “Local features and kernels for classification of texture and object categories: A comprehensive study,” International journal of computer vision, vol. 73, pp. 213–238, 2007.
  2. [2]B. W. Gillespie and L. E. Atlas, “Optimizing time-frequency kernels for classification,” IEEE Transactions on Signal Processing, vol. 49, no. 3, pp. 485–496, 2001.DOI
  3. [3]C. Cortes, M. Mohri, and A. Rostamizadeh, “Two-stage learning kernel algorithms.” in ICML, 2010, pp. 239–246.
  4. [4]T. Hofmann, B. Schölkopf, and A. J. Smola, “Kernel methods in machine learning,” 2008.
  5. [5]K.-L. Du, B. Jiang, J. Lu, J. Hua, and M. Swamy, “Exploring kernel machines and support vector machines: Principles, techniques, and future directions,” Mathematics, vol. 12, no. 24, p. 3935, 2024.DOI
  6. [6]Y. Wang, X. Liu, Y. Dou, Q. Lv, and Y. Lu, “Multiple kernel learning with hybrid kernel alignment maximization,” Pattern Recognition, vol. 70, pp. 104–111, 2017.DOI
  7. [7]A. Kumar, A. Niculescu-Mizil, K. Kavukcuoglu, and H. Daume III, “A binary classification framework for two-stage multiple kernel learning,” arXiv preprint arXiv:1206.6428, 2012.arxiv.org/abs/1206.6428
  8. [8]S. Zhong, D. Chen, Q. Xu, and T. Chen, “Optimizing the gaussian kernel function with the formulated kernel target alignment criterion for two-class pattern classification,” Pattern Recognition, vol. 46, no. 7, pp. 2045–2054, 2013.DOI
  9. [9]S. S. Keerthi and C.-J. Lin, “Asymptotic behaviors of support vector machines with gaussian kernel,” Neural computation, vol. 15, no. 7, pp. 1667–1689, 2003.pubmed.ncbi.nlm.nih.gov/12816571
  10. [10]J. E. Camargo and F. A. González, “A multi-class kernel alignment method for image collection summarization,” in Iberoamerican Congress on Pattern Recognition. Springer, 2009, pp. 545–552.DOI
  11. [11]M. Tian and W. Wang, “An efficient gaussian kernel optimization based on centered kernel polarization criterion,” Information Sciences, vol. 322, pp. 133–149, 2015.DOI
  12. [12]N. Cristianini, J. Shawe-Taylor, A. Elisseeff, and J. Kandola, “On kernel-target alignment,” Advances in neural information processing systems, vol. 14, 2001.
  13. [13]J. Kandola, J. Shawe-Taylor, and N. Cristianini, “Optimizing kernel alignment over combinations of kernel,” 2002.
  14. [14]G. R. Lanckriet, N. Cristianini, P. Bartlett, L. E. Ghaoui, and M. I. Jordan, “Learning the kernel matrix with semidefinite programming,” Journal of Machine learning research, vol. 5, no. Jan, pp. 27–72, 2004.
  15. [15]Y. Lu, L. Wang, J. Lu, J. Yang, and C. Shen, “Multiple kernel clustering based on centered kernel alignment,” Pattern Recognition, vol. 47, no. 11, pp. 3656–3664, 2014.DOI
  16. [16]T. Wang, J. Lu, and G. Zhang, “Two-stage fuzzy multiple kernel learning based on hilbert–schmidt independence criterion,” IEEE Transactions on Fuzzy Systems, vol. 26, no. 6, pp. 3703–3714, 2018.DOI
  17. [17]J. T. Kwok and I. W. Tsang, “Learning with idealized kernels,” in Proceedings of the 20th International Conference on Machine Learning (ICML-03), 2003, pp. 400–407.
  18. [18]C. Cortes, M. Mohri, and A. Rostamizadeh, “Learning non-linear combinations of kernels,” Advances in neural information processing systems, vol. 22, 2009.
  19. [19]J. Mercer, “Xvi. functions of positive and negative type, and their connection the theory of integral equations,” Philosophical transactions of the royal society of London. Series A, containing papers of a mathematical or physical character, vol. 209, no. 441-458, pp. 415–446, 1909.DOI
  20. [20]S. Suthaharan, “Support vector machine,” in Machine Learning Models and Algorithms for Big Data Classification: Thinking with Examples for Effective Learning, pp. 207–235, Springer, 2016.
  21. [21]B. Schölkopf, R. Herbrich, and A. J. Smola, “A generalized representer theorem,” in International conference on computational learning theory. Springer, 2001, pp. 416–426.DOI
  22. [22]T. Wang, D. Zhao, and S. Tian, “An overview of kernel alignment and its applications,” Artificial Intelligence Review, vol. 43, pp. 179–192, 2015.
  23. [23]M. Ramona, G. Richard, and B. David, “Multiclass feature selection with kernel gram-matrix-based criteria,” IEEE transactions on neural networks and learning systems, vol. 23, no. 10, pp. 1611–1623, 2012.DOI
  24. [24]M. T. Islam, D. Liu, and D. Sarkar, “Kernel alignment using manifold approximation,” in Second Workshop on Representational Alignment at ICLR 2025.
  25. [25]D. Cárdenas-Peña, D. Collazos-Huertas, and G. Castellanos-Dominguez, “Centered kernel alignment enhancing neural network pretraining for mri-based dementia diagnosis,” Computational and mathematical methods in medicine, vol. 2016, no. 1, p. 9523849, 2016.DOI
  26. [26]S. Tian, W. Li, X. Ning, H. Ran, H. Qin, and P. Tiwari, “Continuous transfer of neural network representational similarity for incremental learning,” Neurocomputing, vol. 545, p. 126300, 2023.DOI
  27. [27]S. A. Alvarez, “Gaussian rbf centered kernel alignment (cka) in the large-bandwidth limit,” IEEE transactions on pattern analysis and machine intelligence, vol. 45, no. 5, pp. 6587–6593, 2022.DOI
  28. [28]S. Kornblith, M. Norouzi, H. Lee, and G. Hinton, “Similarity of neural network representations revisited,” in International conference on machine learning. PMIR, 2019, pp. 3519–3529.arxiv.org/abs/1905.00414
  29. [29]A. Canatar and C. Pehlevan, “A kernel analysis of feature learning in deep neural networks,” in Proc. 58th Annual Allerton Conf. on Communication, Control, and Computing (Allerton), IEEE, pp. 1–8, 2022.DOI
  30. [30]H. Kang, A. Canatar, and S. Chung, “Spectral analysis of representational similarity with limited neurons,” Advances in Neural Information Processing Systems, vol. 38, pp. 24349–24383, 2026.arxiv.org/abs/2502.19648
  31. [31]X. Liu, Y. Yang, and Z. Zhang, “HumanGuideNet: Adapter-Based Alignment of Deep Neural Networks with Human Similarity Judgments,” in Proc. IEEE/CVF Winter Conf. on Applications of Computer Vision (WACV), pp. 1798–1808, 2026.DOI
  32. [32]N. Vance and P. Flynn, “Refining remote photoplethysmography architectures using cka and empirical methods,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2024, pp. 380–388.arxiv.org/abs/2401.04801
  33. [33]S. Hu, C. Park, A. Ferraiuolo, S.-K. Ko, J. Kim, H. Song, and J. Kim, “Mpruner: Optimizing neural network size with cka-based mutual information pruning,” arXiv preprint arXiv:2408.13482, 2024.arxiv.org/abs/2408.13482
  34. [34]W. W. Wong and F. J. Burkowski, “A constructive approach for discovering new drug leads: Using a kernel methodology for the inverse-qsar problem,” Journal of cheminformatics, vol. 1, no. 1, p. 4, 2009.DOI
  35. [35]N. Kriegeskorte, M. Mur, and P. A. Bandettini, “Representational similarity analysis-connecting the branches of systems neuroscience,” Frontiers in systems neuroscience, vol. 2, p. 249, 2008.DOI
  36. [36]A. H. Williams, “Equivalence between representational similarity analysis, centered kernel alignment, and canonical correlations analysis,” bioRxiv, pp. 2024–10, 2024.DOI
  37. [37]Y. Ding, J. Tang, and F. Guo, “Identification of drug-side effect association via multiple information integration with centered kernel alignment,” Neurocomputing, vol. 325, pp. 211–224, 2019.DOI
  38. [38]M. Raghu, J. Gilmer, J. Yosinski, and J. Sohl-Dickstein, “Svcca: Singular vector canonical correlation analysis for deep learning dynamics and interpretability,” Advances in neural information processing systems, vol. 30, 2017.arxiv.org/abs/1706.05806
  39. [39]A. Morcos, M. Raghu, and S. Bengio, “Insights on representational similarity in neural networks with canonical correlation,” Advances in neural information processing systems, vol. 31, 2018.arxiv.org/abs/1806.05759
  40. [40]C. H. Nguyen and T. B. Ho, “Kernel matrix evaluation.” in ICJAI, 2007, pp. 987–992.
  41. [41]H. Xiong, M. Swamy, and M. O. Ahmad, “Optimizing the kernel in the empirical feature space,” IEEE transactions on neural networks, vol. 16, no. 2, pp. 460–474, 2005.pubmed.ncbi.nlm.nih.gov/15787152
  42. [43]H. Li, T. Jiang, and K. Zhang, “Efficient and robust feature extraction by maximum margin criterion,” Advances in Neural Information Processing Systems, vol. 16, 2003.
  43. [44]H. Wan, H. Wang, B. W. Scotney, J. Liu, and X. Wei, “Global subclass discriminant analysis,” Knowledge-Based Systems, vol. 280, p. 111010, 2023.DOI
  44. [45]H. Wan, H. Wang, B. Scotney, J. Liu, and W. W. Ng, “Within-class multimodal classification,” Multimedia Tools and Applications, vol. 79, no. 39, pp. 29 327–29 352, 2020.DOI
  45. [46]E. Hofer and M. v. Mohrenschildt, “Model-free data mining of families of rotating machinery,” Applied Sciences, vol. 12, no. 6, p. 3178, 2022.DOI
  46. [47]D. A. Reynolds, T. F. Quatieri, and R. B. Dunn, “Speaker verification using adapted gaussian mixture models,” Digital signal processing, vol. 10, no. 1-3, pp. 19–41, 2000.DOI
  47. [48]K. Blekas, A. Likas, N. P. Galatsanos, and I. E. Lagaris, “A spatially constrained mixture model for image segmentation,” IEEE transactions on Neural Networks, vol. 16, no. 2, pp. 494–498, 2005.pubmed.ncbi.nlm.nih.gov/15787156
  48. [49]F. R. Chung, Spectral graph theory. American Mathematical Soc., 1997, vol. 92.
  49. [50]M. Belkin, P. Niyogi, and V. Sindhwani, “On manifold regularization,” in International Workshop on Artificial Intelligence and Statistics. PMLR, 2005, pp. 17–24.
  50. [51]C. Cortes, M. Kloft, and M. Mohri, “Learning kernels using local Rademacher complexity,” Advances in Neural Information Processing Systems, vol. 26, 2013.
  51. [55]R. R. Coifman and S. Lafon, “Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning, and data set parameterization,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 4, pp. 569–582, 2006.
  52. [57]P. S. Palar, L. Parussini, L. Bregant, K. Shimoyama, and L. R. Zuhal, “On kernel functions for bi-fidelity gaussian process regressions,” Structural and Multidisciplinary Optimization, vol. 66, no. 2, p. 37, 2023.DOI
  53. [58]W. W. L. Wong and F. J. Burkowski, “Using Kernel Alignment to Select Features of Molecular Descriptors in a QSAR Study,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 8, no. 5, pp. 1373–1384, 2011.DOI
  54. [59]A. Muyskens, B. W. Priest, I. R. Goumiri, and M. D. Schneider, “Identifiability and sensitivity analysis of kriging weights for the matern kernel,” arXiv preprint arXiv:2410.08310, 2024.arxiv.org/abs/2410.08310
  55. [60]J. Lu, Q. J. Wang, N. Fraehr, X. Xiang, and X. Wu, “Choice of gaussian process kernels used in lsg models for flood inundation predictions,” Journal of Hydrology, vol. 655, p. 132949, 2025.DOI
  56. [61]E. Hofer and M. v. Mohrenschildt, “Locally-scaled kernels and confidence voting,” Machine Learning and Knowledge Extraction, vol. 6, no. 2, pp. 1126–1144, 2024.DOI
  57. [62]L. McInnes, J. Healy, and J. Melville, “Umap: Uniform manifold approximation and projection for dimension reduction,” arXiv preprint arXiv:1802.03426, 2018.arxiv.org/abs/1802.03426
  58. [63]D. Dheeru and E. Karra Taniskidou, “UCI machine learning repository,” 2017. [Online]. Available: http://archive.ics.uci.edu/ml
  59. [64]L. Deng, “The MNIST database of handwritten digit images for machine learning research [Best of the Web],” IEEE Signal Processing Magazine, vol. 29, no. 6, pp. 141–142, Nov. 2012.DOI
  60. [65]P. Chudzian, “Evaluation measures for kernel optimization,” Pattern Recognition Letters, vol. 33, no. 9, pp. 1108–1116, 2012.DOI
  61. [66]B. Diedenhofen and J. Musch, “cocor: A Comprehensive Solution for the Statistical Comparison of Correlations,” PLoS ONE, vol. 10, no. 4, p. e0121945, 2015. doi: 10.1371/journal.pone.0121945.DOI

Paper details

vlnc:W_9yd39hdr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents