Author: Eiko

Time: 2025-03-03 10:47:12 - 2025-03-03 10:47:12 (UTC)

Lecturer: Nik at KCL, Computational Statistics

Note taker and remarker: Eiko, I will write down in my own style and adding some personal comments.

Kernel Methods - Lecture 3

The most important equation is the reproducing property of the kernel, recall that it says

$$⟨K(x,),f{⟩}_{{\mathcal{H}}_K}=f(x),\mathrm{\forall }f\in {\mathcal{H}}_K,x\in X.$$

Derivative reproducing property: if $X=\mathbb{R}$ and $k$ is differentiable, then

$$f^{\prime }(x)=⟨f,{\partial }_{x}k(x,\cdot ){⟩}_{{\mathcal{H}}_K}.$$

more generally the higher order derivatives can be computed as

$$D^{\alpha }f(x)=⟨f,{\partial }_x^{\alpha }k(x,\cdot ){⟩}_{{\mathcal{H}}_K}.$$

Proof.

Just observe that

$$\frac{f(x+h)-f(x)}{h}={⟨f,\frac{k(x+h,\cdot )-k(x,\cdot )}{h}⟩}_{{\mathcal{H}}_K}.$$

For ${\mathcal{H}}_K$, look at ${\mathcal{H}}_k^{\ast }=\{\text{cont linear functionals }\tilde{u}:{\mathcal{H}}_k\to \mathbb{R}\}$

continuous linear functionals on a Hilbert space are by Riesz representation theorem induced by inner product. So since the evaluation maps ${\delta }_x$, ${\delta }_x^{\prime }$ are continuous, they can be written as inner products with some functions in ${\mathcal{H}}_K$.

Generalized Representer Theorem

$$f^{\ast }\in {\mathrm{argmin}}_{f\in {\mathcal{H}}_K}(\frac{1}{N}\sum _{i=1}^N(\widetilde{u_i}(f)-y_i{)}^2+\lambda \parallel f{\parallel }_{{\mathcal{H}}_K}^2)$$

$\widetilde{u_i}\subset {\mathcal{H}}_K^{\prime }$ then $f^{\ast }$ can be written as

$$f^{\ast }=\sum _{i=1}^N{\alpha }_i{u}_i.$$

where $u_i$ represents $\widetilde{u_i}$ in ${\mathcal{H}}_K^{\ast }$.

Kernel Embeddings

Use PCA (principle component analysis)

Given data $(x_i\in {\mathbb{R}}^D{)}_{i\le N}\in ({\mathbb{R}}^D{)}^N=\mathrm{Hom}({\mathbb{R}}^N,{\mathbb{R}}^D)$, we can compute the covariance matrix

$$C(X,X)=(\mathbb{E}(X^{(i)}-\mathbb{E}{X}^{(i)})(X^{(j)}-\mathbb{E}{X}^{(j)}){)}_{i,j\le D}$$

WLOG we can assume $\mathbb{E}X=0$, so $C=\frac{1}{N}X{X}^T$. This is a $D\times D$ symmetric positive semi-definite matrix. By orthogonal diagonalization, we can write for an orthonormal basis $(u_i{)}_{i\le D}$

$$C{u}_i={\lambda }_i{u}_i,{\lambda }_1\ge \cdots \ge {\lambda }_D\ge 0$$

and $C=\sum {\lambda }_i{u}_i\otimes u_i^{\ast }$, here note that $u_i\otimes u_i^{\ast }:{\mathbb{R}}^D\to \mathbb{R}{u}_i$ just projects onto the one-dimensional subspace spanned by $u_i$.

We can then project to the space spanned by the orthonormal vectors with larger eigenvalues $\mathrm{span}(u_1,\dots ,u_k)$, which preserves the majority of the variance and inner product.

$$P=\sum _{i=1}^k{u}_i\otimes u_i^{\ast }:{\mathbb{R}}^D\to \mathrm{span}(u_1,\dots ,u_k)\cong {\mathbb{R}}^k.$$

$P$ here can be viewed as an approximation of identity, since $P_{k=n}=\mathrm{id}$.

Lemma.

• $P\in {\mathrm{argmax}}_P\mathrm{Var}(P\{x_i{\}}_{1\le i\le N})$, picks the maximal variance directions.

• $P^{\ast }\in {\mathrm{argmin}}_P\frac{1}{N}\sum _{i=1}^N|x_i-P{x}_i{|}^2$, least moving, maximal inner product preservation.

---

Idea: Embed the points $(x_i{)}_{i=1}^N$ into some high dimensional space, and then do PCA in that space.

Consider a map $\phi :X\to {\mathbb{R}}^D$ or equivalently a map ${\mathbb{R}}^X\to {\mathbb{R}}^D$ by free forgetful adjunction. We wish that this map preserves

Prop. $\phi :X\to (H,⟨,{⟩}_H)$ is a map into any Hilbert space $H$, then

$$k(x,y):=⟨\phi (x),\phi (y){⟩}_H$$

defines a positive definite kernel on $X$.

If we have an RKHS ${\mathcal{H}}_K$ on $X$, then

$$\phi (x)=k(x,\cdot )\in {\mathcal{H}}_K$$

is the canonical feature map associated to $({\mathcal{H}}_K,X)$.

---

Let $X$ be a set and $k:X\times X\to \mathbb{R}$ a positive definite kernel, we get the associated RKHS ${\mathcal{H}}_K$ and canonical feature map $\phi :X\to {\mathcal{H}}_K$.

${\phi }_k(x),{\phi }_k(y)$ are now in ${\mathcal{H}}_K$, and we can compute the inner product

$$⟨{\phi }_k(x),{\phi }_k(y){⟩}_{{\mathcal{H}}_K}=k(x,y).$$

Kernel Trick

The kernel trick says that any algorithm working with points $(x_i)\subset {\mathbb{R}}^D$ in Euclidean space that only rely on a Euclidean structure $({\mathbb{R}}^D,⟨,⟩)$, can be generalized to a Kernel setting by replacing all inner products with the kernel function.

Eiko Remark. This seems to be able to utilize the topology of $X$ and bring some non-linear structure into the game. The topology seems to be important here, if $k(x,y)$ is given by any numbers and has nothing to do with the topology of $X$ (equivalently choosing discrete topology), this is just putting arbitrary inner product on the huge space ${\mathbb{R}}^X$. The point is the use of topology lowers the dimension we need to consider but not restricting us inside the original space ${\mathbb{R}}^D$ with the Euclidean structure.