Suggest edit — Kernel Trick

Title

Name

Note

---
title: "Kernel Trick"
type: concept
related: [Positive Semi Definite, Kernel Trick, Kernel Smoothing, Linear Predictor, Null Space]
source: https://www.jemoka.com/posts/kbhkernel_trick/
confidence: high
status: active
---

constituents samples $x,z \in \mathcal{D}$ $d$ input dimensions, $p$ featured dimensions feature map: $\phi: \mathbb{R}^{d} \to \mathbb{R}^{p}$ kernel: $k\qty(x,z) = \langle\phi\qty(x), \phi\qty(z)\rangle$ requirements train Compute $k\qty(x^{(i)}, x^{(j)})$ for all $i,j \in 1 &hellip; n$. Set $\beta_{j} = 0$ for all $j$. Iterate:
\begin{equation} \beta_{i} = \beta_{i} + \alpha \qty[y^{(i)} - \sum_{j=1}^{n} \beta_{j} k\qty(x^{(i)}, x^{(j)})] \end{equation}
test Given $x$, compute $\theta^{T} \phi\qty(x)$ such that:
\begin{align} \theta^{T}\phi\qty(x) &amp;= \sum_{i=1}^{n} \beta_{i} \phi\qty(x^{(i)})^{T} \phi\qty(x) \\ &amp;= \sum_{i=1}^{n} \beta k\qty(x^{(i)}, x) \end{align}
takes $O\qty(nd)$ time.
additional information kernel smoothing see kernel smoothing
some useful kernels monomials order up to $t$ we have:
\begin{equation} k\qty(x,z) = \qty(x^{T}z + c)^{t} \end{equation}
which gives a feature map of all monomials $x_{i}, x_{ij}, x_{ijk} \ldots$ which gives $\mqty(d+t \\ t)$ dimension feature space. For $\qty(x^{T}z+c)^{2}$, for instance, we have:
\begin{equation} \phi\qty(x) = \mqty(c \\ \sqrt{2c} x_1 \\ \dots \\ x_{d} x_{d}) \end{equation}
which you can figure by FOILing the kernel function and trying to finagle a way to get each term.
gaussian kernel see gaussian kernel, which has:
\begin{equation} k\qty(x,z) = \exp \qty(\frac{- \norm{x-z}^{2}_{2}}{2\sigma^{2}}) \end{equation}
what makes a valid kernel? This is a necessary and sufficient condition:
Suppose there being $n$ data points, $x^{(i)}&hellip;x^{(n)}$. Consider a structure called kernel matrix: $K \in \mathbb{R}^{n \times n}$, such that $k_{ij} = k\qty(x^{(i)}, x^{(j)})$. A valid kernel needs that $K \succ 0$, namely that $K$ is positive semi-definite.
Consider what that would mean:
\begin{align} z^{T} k z &amp;= \sum_{i=1}^{n} \sum_{j=1}^{n} z_{i} k_{ij} z_{j} \\ &amp;= \sum_{i=1}^{n} \sum_{j=1}^{n} z_{i} \phi\qty(x^{(i)})^{T} \phi\qty(x^{(i)}) z_{j} \\ &amp;= \sum_{i=1}^{n} \sum_{j=1}^{n}z_{i} \sum_{l}^{} \qty(\phi_{l}\qty(x^{(i)}) \phi_{l}\qty(x^{(j)})) z_{j} \\ &amp;= \sum_{l}^{} \qty(\sum_{i}^{}\qty(z_{i}\phi_{l}\qty(x^{(i)}))^{2}) \geq 0 \end{align}
This gives us that $K$ being PSD is a necessary condition for being a kernel. What about sufficiency? We will proof by divine intervention:
$k$ is a valid kernel IFF for all $n &lt; \infty$, we have for all $x^{(1)} &hellip; x^{(n)}$, the corresponding kernel matrix is PSD.
deriving the kernel trick Consider now the update rule for $\beta$ from above:
\begin{equation} \beta_{i} = \beta_{i} + \alpha \qty(y^{(i)} - \theta^{T} \phi\qty(x^{(i)})) \end{equation}
plugging in the definition of $\theta$ in terms of $\beta$ above, we obtain:
\begin{align} \beta_{i} &amp;= \beta_{i} + \alpha \qty(y^{(i)} - \theta^{T} \phi\qty(x^{(i)})) \\ &amp;= \beta_{i} + \alpha \qty(y^{(i)} - \qty(\sum_{j=1}^{n} \beta_{j} \phi\qty(x^{(i)})))\phi\qty(x^{(i)}) \\ &amp;= \beta_{i} + \alpha \qty(y^{(i)} - \sum_{j=1}^{n} \beta_{j}\left\langle \phi \qty(x^{(j)}), \phi\qty(x^{(i)}) \right\rangle) \end{align}
Which gives us two observations:
$\langle \phi \qty(x^{(i)}), \phi \qty(x^{(j)}) \rangle$, $\forall i,j$ can be precomputed often computing these inner products can be much faster than $O\qty(p)$ efficiently computing the kernel $\langle \phi \qty(x^{(i)}), \phi \qty(x^{(j)}) \rangle$ Consider the following scheme to feature engineer your data:
\begin{equation} \phi \qty(x) = \mqty[1 \\ x_1 \\ \dots \\ x_{d} \\ x_1 x_1 \\ x_1 x_2 \\ \dots \\ x_1x_1x_1 \\ x_1x_1x_2 \\ \dots \\ x_{d} x_{d} x_{d}] \end{equation}
How would we commute the inner productive above? Naively, for two data samples $x,z$:
\begin{equation} \langle \phi\qty(x), \phi \qty(z) \rangle = 1 + \sum_{i=1}^{d} x_{i} z_{i} + \sum_{i=1}^{d} \sum_{j=1}^{d} x_{i}x_{j}z_{i}z_{j}+ \sum_{i=1}^{d} \sum_{j=1}^{d} \sum_{k=1}^{d} x_{i}x_{j}x_{k} z_{i}z_{j}z_{k} \end{equation}
You will notice:
\begin{equation} \langle \phi\qty(x), \phi \qty(z) \rangle = 1 + \sum_{i=1}^{d} x_{i} z_{i} + \underbrace{\sum_{i=1}^{d} \sum_{j=1}^{d} x_{i}x_{j}z_{i}z_{j}}_{\langle x,z \rangle^{2}}+ \underbrace{\sum_{i=1}^{d} \sum_{j=1}^{d} \sum_{k=1}^{d} x_{i}x_{j}x_{k} z_{i}z_{j}z_{k}}_{\langle x,z \rangle^{3}} \end{equation}
So we can finally write:
\begin{equation} \langle \phi\qty(x), \phi \qty(z) \rangle = 1 + \langle x,z \rangle + \langle x,z \rangle^{2} + \langle x,z \rangle^{3} \end{equation}
which is better. As opposed to the naive $O\qty(np)$ solution for linear regression, we have $O\qty(n^{2})$ per iteration and $O\qty(n^{2}d)$ for precomputation of the inner products above. This is nice because $p$ maybe really bigger than $n$.
motivation Suppose you have some kind of non-linear (say exponential) dataset&hellip; Consider now Linear Regression with a feature map
\begin{equation} \theta := \theta + \alpha \sum_{i=1}^{n} \qty(y^{(i)} - \theta^{T}\phi\qty(x^{(i)})) \phi \qty(x^{(i)}) \end{equation}
NOTICE that $\theta$ is a linear combination of $φ\qty(x(i))$s; which we can write somewhat as:
\begin{equation} \theta = \sum_{i=1}^{n} \beta_{i} \phi\qty(x^{(i)}) \end{equation}
observe: this is $n$ variables in $\beta_{j}$ instead of $p$ variables. This is nice because if $p$ was large feature map $\phi$ could get really expensive.
Substituting the above in for $\theta$, we obtain:
THIS IS PROBABLY BAD AND WRONg
\begin{equation} \theta = \sum_{i=1}^{n} \underbrace{\qty(\beta_{i} + \alpha\qty(y^{(i)-\theta^{T}\phi\qty(x^{(i)})}))}_{\text{new $\beta_i$}} \phi\qty(x^{(i)}) \end{equation}