Kernel Trick in Machine Learning¶

Preface¶

The primary goal is to utilize kernels for representing functions, and allowing for a larger hypothesis space.

Note that "representing functions" means that we express a function as a combination of simpler components (like kernel evaluations). This allows to us to not have to do calculations in a higher dimension, which is expensive.

Remark: \(\psi\) here is used as a feature map, which is a function that maps the input space to a higher-dimensional feature space, that is:

\[ \psi: \mathcal{X} \to \mathcal{H}, \ \ \ \ \ \mathbf{x \mapsto \psi(\mathbf{x})} \]

Basic Summary¶

The kernel trick refers to the ability to compute inner products in a high-dimensional (possibly infinite-dimensional) feature space using a kernel function in the original input space. This avoids the need to explicitly compute or represent the feature map \(\psi(\mathbf{x})\), enabling efficient computation in algorithms that rely solely on inner products.

Definition¶

Assume that you have features \(\psi(\mathbf{x})\) and you want to do linear regression. Then our formulation is:

\[ \sum_{i=1}^{n}(\psi(\mathbf{x}_{i} - y_{i})^2) = ||\boldsymbol{\psi}(\mathbf{x} - \mathbf{y})||_{2}^{2} \]

Recall that \(|| \dots||_{2}^{2}\) is the L2 Norm.

Here \(\boldsymbol{\psi}\) is composed of the vectors \(\psi(\mathbf{x}_{i})\) such that:

\[ \Psi = \begin{bmatrix} \psi(\mathbf{x_1})^{\top} \\ \psi(\mathbf{x_{2}})^{\top} \\ \vdots \\ \psi(\mathbf{x_n})^{\top} \end{bmatrix} \]

where we transpose \(\psi(\mathbf{x}_{i})\) since it is convention that \(\psi(\mathbf{x}_{i})\) to be a column vector.

Now consider an alternate set of weights \(\boldsymbol{\alpha} \in \mathbb{R}^{n}\), and we assume \(\mathbf{w} = \boldsymbol{\Psi}^{\top}\boldsymbol{\alpha}\).

Note that this does not constrain the solution, because our solution is projected to the space spanned by \(\boldsymbol{\Psi}\); therefore we know that \(\mathbf{w}\) is in the span of \(\boldsymbol{\Psi}\).

It is equivalent to directly optimize for \(\boldsymbol{\alpha}\), and our predictions will simply be

\[ \begin{align} \psi(\mathbf{x})\mathbf{w} &= \psi(\mathbf{x})\boldsymbol{\Psi}^{\top}\boldsymbol{\alpha} \\ &= \sum_{i=1}^n \alpha_{i} \langle \psi(\mathbf{x}), \psi(\mathbf{x}_{i}) \rangle \end{align} \]

We can write this inner product as \(k(\mathbf{x}, \mathbf{x}_{i}) = \langle \psi(\mathbf{x}), \psi(\mathbf{x}_{i}) \rangle\). And for \(\psi\), this inner product has a closed form solution, namely for those where we have the kernel function. ie. if \(\psi\) is a polynomial feature mapping, this inner product is the polynomial kernel.

Therefore, if we can efficiently compute the inner product (ie. the inner product is a result from the kernel), then it is more efficient to solve for this optimization:

\[ ||\boldsymbol{\Psi}\mathbf{w} - \mathbf{y}||_{2}^{2}=||\boldsymbol{\Psi\Psi}^{\top}\boldsymbol{\alpha} - \mathbf{y}||_{2}^2 = ||\mathbf{K}\boldsymbol{\alpha}-\mathbf{y}||_{2}^{2} \]

where \(\mathbf{K}\) is the matrix composed of \(k(x_{i}, x_{j})\) at the entry \((i,j)\): \(K_{i,j} = k(x_{i}, x_{j})\).

References¶

Date created: Wednesday 16th April 2025 12:21