More on Kernels

Well-defined kernels¶

We can build kernels by recursively combining one or more of the following rules:

1. $\mathsf{k}(\mathbf{x}, \mathbf{z})=c\mathsf{k_1}(\mathbf{x},\mathbf{z})$
2. $\mathsf{k}(\mathbf{x}, \mathbf{z})=\mathsf{k_1}(\mathbf{x},\mathbf{z})+\mathsf{k_2}(\mathbf{x},\mathbf{z})$
3. $\mathsf{k}(\mathbf{x}, \mathbf{z})=g(\mathsf{k}(\mathbf{x},\mathbf{z}))$
4. $\mathsf{k}(\mathbf{x}, \mathbf{z})=\mathsf{k_1}(\mathbf{x},\mathbf{z})\mathsf{k_2}(\mathbf{x},\mathbf{z})$
5. $\mathsf{k}(\mathbf{x}, \mathbf{z})=f(\mathbf{x})\mathsf{k_1}(\mathbf{x},\mathbf{z})f(\mathbf{z})$
6. $\mathsf{k}(\mathbf{x}, \mathbf{z})=e^{\mathsf{k_1}(\mathbf{x},\mathbf{z})}$

where $k_1,k_2$ are well-defined kernels, $c\geq 0$, $g$ is a polynomial function with positive coefficients, $f$ is any function and $\mathbf{A}\succeq 0$ is positive semi-definite.

Kernel Machines¶

Kernalizing an Algorithm¶

An algorithm can be kernelized in 3 steps:

1. Prove that the solution lies in the span of the training points (i.e. $\mathbf{w}=\sum_{i=1}^n \alpha_i \mathbf{x}_i$ for some $\alpha_i$)
2. Replace $\mathbf w$ with $\sum\alpha_i \mathbf{x}_i$ in the algorithm, so we have prediction $h(\mathbf{x}_t)= \mathbf w \mathbf{x}_t = \sum_{i=1}^n\alpha_i \mathbf{x}_i^T \mathbf{x}_i$
3. Define a kernel function and substitute $\mathsf{k}(\mathbf{x}_i,\mathbf{x}_j)$ for $\mathbf{x}_i^\top \mathbf{x}_j$, so $h(\mathbf{x}_t) = \sum_{i=1}^n\alpha_i \mathbf{x}_i^T \mathbf{x}_i= \sum_{i=1}^n\alpha_i \mathsf{k}(\mathbf{x}_i,\mathbf{x}_t)$

Example: Algorithm with Squared Loss¶

Recap¶

linear regression minimizes the following squared loss:

The solution of OLS can be written in closed form:

Note here our $\mathbf x$ has already gone through the transformation $\phi$ into the feature space, so $\mathbf x = \phi(\mathbf x_{original \;data})$. Therefore, the conclusion we make here generalizes to all kinds of kernel with $\mathsf{k}(\mathbf{x}_{og \;i},\mathbf{x}_{og \;j}) =\phi(\mathbf{x}_{og \;i})^\top \phi(\mathbf{x}_{og \;j})$ and $\mathsf K = \mathbf X ^T \mathbf X$.

Kernelization¶

We begin by expressing the solution $\mathbf{w}$ as a linear combination of the training inputs

We derived in the previous lecture that such a vector $\vec \alpha$ must always exists. Also rewrite the prediction result $h$ as:

Revisit our minimization problem:

We obtain a min value when $\mathsf K \alpha - y = 0$, so when $\alpha = \mathsf K^{-1}y$ , but this is only true when $\mathsf K$ is invertible (only happens when all pivots in $\mathsf K$ are non-zero, so only happens when $\mathsf K$ is positive definite) Since $\mathsf K$ is merely positive semi-definite, its invertible is not guaranteed, so we generalize it to:

and the solution becomes

Testing¶

The prediction of a test point $\mathbf{z}$ then becomes

where $\mathbf{k}_*$ is the kernel (vector) of the test point with the training points after the mapping into feature space through $\phi$, i.e. the $i^{th}$ dimension corresponds to $[\mathbf{k}_*]_{i}=\phi(\mathbf{z})^\top\phi(\mathbf{x}_i)$.