Machine Learning MT23, Kernels

Created: November 15, 2023 | About these notes | View in context | Study these flashcards

Flashcards

What is a kernel $\kappa$?

Some function

\[\kappa : \mathcal X \times \mathcal X \to \mathbb R\]

Can you give the Gram matrix $\pmb K$ for a kernel $\kappa : \mathcal X \times \mathcal X \to \mathbb R$ and inputs $\langle \pmb x _ i \rangle^N _ {i=1}$?
\[\pmb K = \begin{bmatrix} \kappa(\pmb x_1, \pmb x_1) & \kappa(\pmb x_1, \pmb x_2) & \cdots & \kappa(\pmb x_1, \pmb x_N) \\\\ \kappa(\pmb x_2, \pmb x_1) & \kappa(\pmb x_2, \pmb x_2) & \cdots & \kappa(\pmb x_2, \pmb x_N) \\\\ \vdots & \vdots & \ddots & \vdots \\\\ \kappa(\pmb x_N, \pmb x_1) & \kappa(\pmb x_N, \pmb x_2) & \cdots & \kappa(\pmb x_N, \pmb x_N) \end{bmatrix}\]

What does it mean for a kernel to be a Mercer kernel?

The Gram matrix is always positive semi-definite.

Why are Mercer kernels important in the context of the kernel trick for SVMs?

They keep the SVM dual optimisation problem convex.

Can you define the degree-$d$ polynomial kernel, and describe its computational advantages?
\[\kappa(\pmb x, \pmb x') = (1+\pmb x \cdot \pmb x')^d\]

This implicitly represents the feature expansion into all terms in a degree $d$ polynomial in each entry of $\pmb x$, of which there are roughly $O(D^d)$. This allows computing the associated inner product in just $O(D\log d)$.

What is the spherical Gaussian kernel?
\[\kappa(\pmb x, \pmb x') = \exp\left( -\frac{||\pmb x - \pmb x'||^2_2}{2\sigma^2} \right)\]

Radial basis function kernels are not just kernels of the form

\[\kappa(\pmb x, \pmb x') = \exp\left( -\frac{||\pmb x - \pmb x'||^2_2}{2\sigma^2} \right)\]

What are they in general?

Any kernel that depend only on $ \vert \vert \pmb x - \pmb x’ \vert \vert $.

Suppose we have two strings $\mathbf x$ and $\mathbf x’$ over an alphabet $\Sigma$. Can you describe a Mercer kernel for these inputs?
\[\sum_{s \in \Sigma^\star} w_s \phi_s(\mathbf x) \phi_s(\mathbf x')\]

where $w _ s$ are weights and $\phi _ s(\mathbf x)$ is the number of occurences of the substring $s$ in $\mathbf x$.

Proofs



Related posts