Exercise 12.20: Support Vector Machines and Kernel Methods

chapter 12

(a)

Since the linear span of $\{k(\cdot ,x_i){\}}_{i=1}^n$ is finite dimensional, it is closed. Thus we can decompose any $f\in \mathbb{H}$ into two orthogonal components $f=f_{\parallel }+f_{\mathrm{\perp }}$ where $f_{\parallel }$ lies in the linear span, and therefore $$\begin{array}{}\text{(1)}& f(x_i)=⟨f,k(\cdot ,x_i)⟩=⟨f_{\parallel },k(\cdot ,x_i)⟩,\end{array}$$ for all $i\in [n]$. Hence $f_{\mathrm{\perp }}$ only affects the regulariser $\Vert f{\Vert }_{\mathbb{H}}^2=\Vert f_{\parallel }{\Vert }_{\mathbb{H}}^2+\Vert f_{\mathrm{\perp }}{\Vert }_{\mathbb{H}}^2$ which is minimised when $f_{\mathrm{\perp }}=0$.

(b)

Let $\xi =[{\xi }_1,\dots ,{\xi }_n]\in {\mathbb{R}}^n$ be an auxiliary variable which upper bounds the observation-wise hinge losses: ${\xi }_i\ge 0$ and ${\xi }_i\ge 1-y_{i}f(x_i)$ for all $i\in [n]$. With this constraint and $f=\sum _{i=1}^n{\alpha }_{i}k(\cdot ,x_i)$ for some $\alpha \in {\mathbb{R}}^n$ by (a) $$\begin{array}{}\text{(2)}& \underset{f}{min}\{\frac{1}{n}\sum _{i=1}^{n}max\{0,1-y_{i}f(x_i)\}+\frac{{\lambda }_n}{2}\Vert f{\Vert }_{\mathbb{H}}^2\}=\underset{\alpha ,\xi }{min}\{\frac{1}{{\lambda }_{n}n}\sum _{i=1}^n{\xi }_i+\frac{1}{2}{\alpha }^{\mathrm{\top }}K\alpha \}.\end{array}$$ where $K_{ij}=k(x_i,x_j)$. Defining $\eta =1/({\lambda }_{n}n)$, and $\mathbf{1}=[1,\dots ,1]\in {\mathbb{R}}^n$, we can introduce the dual variables $\mu ,\nu \in {\mathbb{R}}^n$, ${\mu }_i\le 0$ and ${\nu }_i\ge 0$ for all $i$, and write the Lagrangian $$\begin{array}{}\text{(3)}& \mathcal{L}(\alpha ,\xi ,\mu ,\nu )& =\eta {\xi }^{\mathrm{\top }}\mathbf{1}+\frac{1}{2}{\alpha }^{\mathrm{\top }}K\alpha +{\mu }^{\mathrm{\top }}\xi -{\nu }^{\mathrm{\top }}(\xi -1)-(\nu \odot y{)}^{\mathrm{\top }}K\alpha \text{(4)}& & ={\nu }^{\mathrm{\top }}\mathbf{1}+{\xi }^{\mathrm{\top }}(\eta \mathbf{1}+\mu -\nu )+\frac{1}{2}{\alpha }^{\mathrm{\top }}K\alpha -(\nu \odot y{)}^{\mathrm{\top }}K\alpha ,\end{array}$$ where $\odot$ denotes the Hadamard product. Setting the derivatives w.r.t. the primal variables to zero $$\begin{array}{}\text{(5)}& \frac{\partial \mathcal{L}}{\partial \alpha }=K\alpha -K(\nu \odot y)=0,\frac{\partial \mathcal{L}}{\partial \xi }=\eta \mathbf{1}+\mu -\nu =0,\end{array}$$ and substituting into the Lagrangian, we obtain $$\begin{array}{}\text{(6)}& \mathcal{L}(\nu )=\sum _{i=1}^n{\nu }_i-\frac{1}{2}{\nu }^{\mathrm{\top }}\tilde{K}\nu ,\end{array}$$ where ${\tilde{K}}_{ij}=y_i{y}_{j}k(x_i,x_j)$. We can thus eliminate the $\mu$ variables by introducing the inequality constrain ${\nu }_i\le \eta$, for all $i$, which comes from the above $\eta \mathbf{1}+\mu -\nu =0$ combined with ${\mu }_i\le 0$ (definition). Since ${\nu }_i\ge 0$ (also by definition), we maximise over ${\nu }_i\in [0,1/({\lambda }_{n}n)]$. This is equivalent to the desired result.