Normalisation of the kernel matrix

Setting up the environment (do not use pylab)

$\newcommand{\dotprod}[2]{\langle #1 , #2 \rangle}$

Normalisation

We illustrate 4 normalisation methods:

1. Normalise individual values to [0,1]
2. Center data in feature space (mean in feature space is the zero vector)
3. Make the diagonal all ones
4. Unit variance in feature space

The first method is self explanatory.

In the following, we use the fact that kernels ($k(\cdot, \cdot)$) are inner products in a feature space with feature mapping $\phi(\cdot)$: $$k(x,y) = \dotprod{\phi(x)}{\phi(y)}$$

Centering

Centering causes the mean of the data set to be the zero vector in feature space. For more details, refer to Chapter 5 of the book Kernel Methods for Pattern Analysis

Since $\phi(x)$ lives in a vector space, we can compute the mean vector as usual $$ \mu = \frac{1}{n}\sum_{i=1}^n \phi(x_i) $$ and subtract is off from each data point $$ \hat{\phi}(x) = \phi(x) - \mu. $$ Hence the normalised kernel can be computed with a bit of algebra \begin{align*} \hat{k}(x,y) &= \dotprod{\hat{\phi}(x)}{\hat{\phi}(y)}\\ &= \dotprod{\phi(x) - \mu}{\phi(y) - \mu} \end{align*} by recalling the definition of $\mu$ and expanding the quadratic.

Unit diagonal

It is often convenient to have all the examples to be represented by vectors of the same length. This implies that the diagonal of the kernel matrix (the squared length) is the same for all examples. We arbitrarily (without loss of generality) set this length to 1. \begin{align*} \hat{k}(x,y) &= \dotprod{\frac{\phi(x)}{\|\phi(x)\|}}{\frac{\phi(y)}{\|\phi(y)\|}}\\ &= \frac{1}{\|\phi(x)\|\|\phi(y)\|}\dotprod{\phi(x)}{\phi(y)}\\ &= \frac{1}{\|\phi(x)\|\|\phi(y)\|} k(x,y) \end{align*}

Normalizing the kernel matrix such that it has one along the diagonal is sometimes called trace normalisation or spherical normalisation.

Unit variance

We would like to enforce the fact that the variance of the vectors in feature space is 1. $$\frac{1}{n}\sum_{i=1}^n \|\hat{\phi}(x) - \mu \|^2 = 1$$ where $\mu$ is the mean as defined in the centering section. In terms of kernels, this is $$\frac{1}{n}\sum_{i=1}^n \hat{k}(x_i,x_i) - \frac{1}{n^2}\sum_{i=1}^n\sum_{j=1}^n \hat{k}(x_i,x_j)= 1$$ so the final normalisation rule is $$ \hat{k}(x_i,x_j) = \frac{k(x_i,x_j)}{\frac{1}{n}\sum_{i=1}^n k(x_i,x_i) - \frac{1}{n^2}\sum_{i=1}^n\sum_{j=1}^n k(x_i,x_j)} $$

Note that in case the kernel is centered, the above rule simplifies to $$\hat{k}(x_i, x_j) = \frac{k(x_i,x_j)}{\frac{1}{n}\mathrm{tr}(K)}$$ where $\mathrm{tr}(K) = \sum_{i=1}^n k(x_i ,x_i)$ is the trace of the kernel matrix $K$.

Reference: Kloft, Brefeld, Sonnenburg, Zein, "$\ell_p$-Norm Multiple Kernel Learning" Journal of Machine Learning Research 12 (2011) 953-997

Kernels and distances

Since kernels always have dot products in some corresponding feature space, there is a associated distance. Recall that a kernel is given by: $$k(x,y) = \dotprod{\phi(x)}{\phi(y)}$$ Consider the squared distance in the feature space: \begin{align*} \| \phi(x) - \phi(y)\|^2 &= \dotprod{\phi(x)}{\phi(x)}+ \dotprod{\phi(y)}{\phi(y)}- 2\dotprod{\phi(x)}{\phi(y)}\\ &= k(\phi(x),\phi(x)) + k(\phi(y),\phi(y))- 2k(\phi(x),\phi(y)) \end{align*} hence the corresponding distance is given by: $$ d(x,y) = \sqrt{k(\phi(x),\phi(x)) + k(\phi(y),\phi(y))- 2k(\phi(x),\phi(y))} $$ Since human intuition seems to work better with distances (as compared to similarities), we also show the matrices for distances.

Generate Gaussian point clouds

For illustration purposes, we generate three Gaussian point clouds with different numbers of sizes and compute the linear kernel (the standard dot product).

Visualising the effect of different normalisations

For visualising kernel matrices it is important to choose good color maps.

The left column shows the kernel matrix, and the right column the distance matrix. Each row shows respectively:

1. Original matrix
2. Normalised individual values to [0,1]
3. Centered
4. Centered and diagonal all ones
5. Unit variance