kernels and neural networks

This is an excerpt from some notes I took for Yale’s S&DS 365 Class (Intermediate Machine Learning)

Mercer kernels

Definition. A Mercer kernel has the property that the matrix $\mathbb{K}=[K(x_i,x_j){]}_{n\times n}$ over a set of points $x_1\dots x_n$ is positive semi-definite. Example. The gaussian kernel is Mercer

---

Remark. Instead of using local smoothing, we can optimize the fit to the data subject to a roughness penalty (i.e., adding regularization). We want to find, from a class of functions $\mathcal{H}$

$$\begin{array}{rl}\hat{m}& =\arg \underset{\hat{m}\in \mathcal{H}}{\min }{\left(\sum _i\left(Y_i-\hat{m}(X_i)\right)\right)}^2+\lambda \mathrm{penalty}\left(\hat{m}\right)\end{array}$$

---

Remark. We can create a set of basis functions based on $K$. Fix a point $z\in {\mathbb{R}}^p$ and define $K_z(x)=K(z,x)$. Then, drawing $z_i$ from the space of possible data ${\mathbb{R}}^p$, we can define the Reproducing Kernel Hilbert Space:

$$\begin{array}{rl}{\mathcal{H}}_0& =\left\{f\mid f=\sum _{i=1}^k\alpha K_{z_i}(\cdot ),{\alpha }_i\in \mathbb{R},z_i\in {\mathbb{R}}^p\right\}\end{array}$$

Definition. Given two different functions $f,g\in \mathcal{H}$, we define the inner product as

$$\begin{array}{r}⟨f,g{⟩}_K=\sum _i\sum _j{\alpha }_i{\beta }_{i}K(x_i,x_j)={\alpha }^{\top }\mathbb{K}\beta \end{array}$$

and the norm as

$$\begin{array}{r}\Vert f{\Vert }_K^2=⟨f,f⟩={\alpha }^{\top }\mathbb{K}\alpha \end{array}$$

This norm allows us to penalize functions for being too complex.

---

Theorem. Representer Theorem. Let $\hat{m}$ minimize ${\sum }_{i=1}^n\left(Y_i-m\right(X_i){)}^2+\lambda \Vert m{\Vert }_K^2$. Then, $\hat{m}(x)={\sum }_{i=1}^n{\alpha }_{i}K(X_i,x)$. Remark. This allows us to optimize over only $\alpha$ and plug in the above formulation of $\hat{m}$ to yield $J(\alpha )=\Vert Y-\mathbb{K}\alpha {\Vert }^2+\lambda {\alpha }^{\top }\mathbb{K}\alpha$, and now we can find $\alpha$ to minimize $J.$ Since this is linear and convex, we can find the closed form solution $\hat{\alpha }={\left(\mathbb{K}+\lambda I\right)}^{-1}Y$. Remark. Here, again, $\lambda$ creates a bias-variance trade-off. Remark. Alternatively, we can solve the optimization problem using gradient descent. The update to $\alpha$ is

$$\begin{array}{r}\alpha ⟵\alpha +\eta \left(\mathbb{K}(y-\mathbb{K}\alpha )-\lambda \mathbb{K}\alpha \right)\end{array}$$

where $\eta$ is a step size hyperparameter.

---

Remark. If $x\to \varphi (x)\in {\mathbb{R}}^d$ (where $d\gg p$) is a feature mapping, we can define a Mercer kernel by $K(x,x^{\prime })=\varphi (x{)}^{\top }\varphi (x^{\prime })$. Conversely, from any Mercer kernel, we can derive the corresponding feature map (from the spectral theorem).

---

Neural Networks

Remark. MLPs. Yay! Yippee!! We can define the parametric classification model (one hidden layer) where

$$\begin{array}{rl}\mathbb{P}(y\mid x)& =\mathrm{softmax}\left(W_2^{\top }\varphi (W_{1}x)\right)\end{array}$$

where $\varphi$ is a component-wise nonlinear function and $W_1,W_2$ are weight matrices. Remark. A neural network is NOTHING MORE than a parametric linear model with a non-linearity.

---

Backpropagation

Remark. Yay!!! $\mathsf{c}:$