RKHS regularization, kernels, and support-vector machines — Examples

For any finite sample $x_1,\dots ,x_m\in {\mathbb{R}}^p$ and coefficients $c_1,\dots ,c_m\in \mathbb{R}$, the linear Gram quadratic form is ${\sum }_{i,j}{c}_i{c}_j{x}_i^T{x}_j=\mathrm{\parallel }{\sum }_i{c}_i{x}_i{\mathrm{\parallel }}_2^2\ge 0$. Thus $k_{\mathrm{l}\mathrm{i}\mathrm{n}}$ satisfies the nonnegative-form condition in [F1], and it is symmetric because $x^{T}z=z^{T}x$.

For $\alpha =({\alpha }_0,\dots ,{\alpha }_p)\in {\mathbb{N}}_0^{p+1}$ with $\mathrm{\mid }\alpha \mathrm{\mid }=d$, define ${\psi }_{\alpha }(x)=\sqrt{d!\mathrm{/}{\alpha }_0!\cdots {\alpha }_p!}{\prod }_{r=1}^p{x}_r^{{\alpha }_r}$. The multinomial theorem gives $(1+x^{T}z{)}^d={\sum }_{\mathrm{\mid }\alpha \mathrm{\mid }=d}{\psi }_{\alpha }(x){\psi }_{\alpha }(z)$.

Therefore, for every finite sample and coefficients, ${\sum }_{i,j}{c}_i{c}_j{k}_d(x_i,x_j)={\sum }_{\mathrm{\mid }\alpha \mathrm{\mid }=d}({\sum }_i{c}_i{\psi }_{\alpha }(x_i){)}^2\ge 0$. The polynomial kernel is symmetric and positive semidefinite by [F1].

When $p=2$ and $d=2$, the six multi-indices in [step 1.2] give $h(x)=(1,\sqrt{2}{x}_1,\sqrt{2}{x}_2,x_1^2,x_2^2,\sqrt{2}{x}_1{x}_2)$, so the stated feature identity holds.

The feature map realizes the stated kernel directly: $⟨\varphi (x),\varphi (z)⟩=xz=k(x,z)$; [F2] also verifies that this kernel is positive semidefinite. With $w,b\in \mathbb{R}$, the two hard-margin constraints are $w-b\ge 1$ and $w+b\ge 1$. Adding them gives $w\ge 1$.

Hence every feasible objective satisfies $\frac{1}{2}{w}^2\ge \frac{1}{2}$. The candidate $w=1,b=0$ satisfies both constraints with equality and has objective $1\mathrm{/}2$, so it attains the minimum.

For this minimizer, $s(x)=wx+b=x$. Thus the signed margins at $(-1,-1)$ and $(1,+1)$ are both $1$, as stated.

The feature map in [F3] realizes the stated linear kernel. At $w=0$, $b=-1$, the scores at all three observations equal $-1$. Their signed margins are respectively $1,-1,1$, so $\xi =(0,2,0)$ satisfies every soft-margin constraint, with objective $2C$.

For any feasible tuple, let $t=w+b$, the score at $x=1$. The two observations at $x=1$ require ${\xi }_2\ge \max (0,1-t)$ and ${\xi }_3\ge \max (0,1+t)$. If $-1\le t\le 1$ these lower bounds sum to $2$; if $t>1$, the second is $1+t>2$; and if $t<-1$, the first is $1-t>2$. Thus ${\xi }_2+{\xi }_3\ge 2$ for every feasible tuple, and its objective is at least $C({\xi }_2+{\xi }_3)\ge 2C$.

The candidate in [step 1.1] is therefore globally optimal. For $\alpha =(0,C,C)$ and $\mu =(C,0,0)$, ${\sum }_i{\alpha }_i{y}_i\varphi (x_i)=C-C=0=w$, ${\sum }_i{\alpha }_i{y}_i=C-C=0$, and $C-{\alpha }_i-{\mu }_i=0$ for all three indices. Each margin constraint is active, so ${\alpha }_i{g}_i^{(m)}=0$; also ${\mu }_i{\xi }_i=0$ for each $i$. These are the KKT conditions in [F2].

The dual objective is ${\sum }_i{\alpha }_i-\frac{1}{2}\mathrm{\parallel }{\sum }_i{\alpha }_i{y}_i\varphi (x_i){\mathrm{\parallel }}^2=2C$, equal to the primal value. The score at $x=1$ is $-1$, while the empirical positive-label frequency among the two observations at $x=1$ is $1\mathrm{/}2$. The logistic transform of the score is $(1+e{)}^{-1}\mathrm{\ne }1\mathrm{/}2$; the SVM optimization does not assert that this transformed value is a probability.