Kernels.tex

\section*{Kernels}

efficient, implicit inner products

\subsection*{Properties of kernel}
$k: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$, $k$ must be some inner product (symmetric, positive-definite, linear) for some space $\mathcal{V}$.
i.e. $k(\mathbf{x}, \mathbf{x'}) = \langle \varphi(\mathbf{x}), \varphi(\mathbf{x'}) \rangle_\mathcal{V} \overset{Eucl.}{=} \varphi(\mathbf{x})^T \varphi(\mathbf{x'}) $
and $k(\mathbf{x}, \mathbf{x}') = k(\mathbf{x}', \mathbf{x})$

\subsection*{Kernel matrix}
$K = 
\begin{bmatrix}
	k(x_1,x_1) & \dots & k(x_1,x_n) \\
	\vdots & \ddots & \vdots \\
	k(x_n, x_1) & \dots & k(x_n,x_n)
\end{bmatrix}$\\
Positive semi-definite matrices $\Leftrightarrow$ kernels $k$

\subsection*{Important kernels}
Linear: $k(x,y)=x^T y$\\
Polynomial: $k(x,y)=(x^T y + 1)^d$\\
Gaussian: $k(x,y) = exp(-||x-y||_2^2/(2h^2))$\\
Laplacian: $k(x,y) = exp(-||x-y||_1/h)$

\subsection*{Composition rules}
Valid kernels $k_1, k_2$, also valid kernels:
$k_1 + k_2$; $k_1 \cdot k_2$; $c \cdot k_1$, $c>0$;
$f(k_1)$ if $f$ polynomial with pos. coeffs. or exponential

\subsection*{Reformulating the perceptron}

Ansatz: $w^* \in \operatorname{span}(X) \Rightarrow w = \sum_{j=1}^n \alpha_j y_j x_j$\\
$\alpha^*= \underset{\alpha \in \mathbb{R}^n}{\operatorname{argmin}} \sum_{i=1}^n \operatorname{max}(0, - \sum_{j=1}^n \alpha_j y_i y_j x_i^T x_j)$

\subsection*{Kernelized perceptron and SVM}
Use $\alpha^T k_i$ instead of $w^T x_i$,\\
use $\alpha^T D_y K D_y \alpha$ instead of $||w||_2^2$\\ 
$k_i=[y_1 k(x_i,x_1), ..., y_n k(x_i,x_n)]$, $D_y = \operatorname{diag}(y)$\\
Prediction: $\hat{y} = \operatorname{sign}(\sum_{i=1}^n \alpha_i y_i k(x_i, \hat{x}))$
SGD update: $\alpha_{t+1} = \alpha_t$, if mispredicted: $\alpha_{t+1,i} = \alpha_{t,i} + \eta_t$ (c.f. updating weights towards mispredicted point)

\subsection*{Kernelized linear regression (KLR)}
Ansatz: $w^*=\sum_{i = 1}^n \alpha_i x$\\
$\alpha^*= \underset{\alpha}{\operatorname{argmin}} ||\alpha^T K - y||_2^2 + \lambda \alpha^T K \alpha \\= (K+\lambda I)^{-1} y$\\
Prediction: $\hat{y} = \sum \limits_{i=1}^n \alpha_i k(x_i,\hat{x})$

\subsection*{k-NN}
$y = \operatorname{sign} \big( \sum_{i=1}^n y_i [x_i \text{ among } k \text{ nearest neigh-}$ $\text{bours of } x] \big)$ --
No weights $\Rightarrow$ no training! But depends on all data :(