开始Hard Margin svm的第三篇博文，主要讲非线性数据的svm以及维度爆炸的问题以及常见的kernel．$ $

non-linear svm

以前写过二次分类的问题，svm的非线性分类其实用的是同样的思想．假设在二维平面上有两个特征\(X1,X2\),但是我们要表示二次曲线的话，那么我们必然要对应到五维空间\(X1,X2,X1^2,X1X2,X2^2\).更严重的是，当空间维度上升时，映射后的空间爆炸式增加,那么我们在利用svm求内积时就很困难了．

kernel function

假设有d维空间

\[ x=(x_{1},x_{2},\ldots,x_{d}) \]

将其做二次映射\(\Phi_{2}(x)\),得到

\[ \Phi_{2}(x)=(1,x_{1},x_{2},\ldots,x_{d},x_{1}^{2},x_{1}x_{2},\ldots,x_{1}x_{d},x_{2}^{2},x_{2}x_{3},\ldots,x_{2}x_{d},\ldots,x_{d}^{2}) \]

内积为：

\[ \begin{align} \Phi_{2}(x)^{T}\Phi_{2}(x^{'})&=1+\sum_{i=1}^{d}x_{i}x^{'}_{i}+\sum_{i=1}^{d}\sum_{j=1}^{d}x_{i}x_{j}x^{'}_{i}x^{'}_{j}\\ &=1+\sum_{i=1}^{d}x_{i}x^{'}_{i}+\sum_{i=1}^{d}x_{i}x^{'}_{i}\sum_{j=1}^{d}x_{j}x^{'}_{j}\\ &=1+x^{T}x^{'}+(x^{T}x^{'})(x^{T}x^{'}) \end{align} \]

显然，我们不需要在高维度显示的计算内积，只需要在低维度计算就好了，我们将能实现这种转换的函数称为kernel function

Polynomial Kernel

上面只是举例说明一下，其实它有更加一般的表达式，我们称它为多项式核

\[ K_{Q}(x,x^{'})=(\zeta+\gamma x^{T}x^{'})^{Q}\\ \zeta\geqslant0,\gamma\geqslant 0 \]

Q代表几次多项式，\(\zeta,\gamma\)都是缩放因子

\[ \begin{align} K_{1}(x,x^{'})&=(0+1\cdot x^{T}x^{'})^{1}\\ &\vdots\\ K_{Q}(x,x^{'})&=(\zeta+\gamma x^{T}x^{'})^{Q} \end{align} \]

首先，解释一下\(\zeta,\gamma,Q\). 其实这个kernel是代表margin(距离)的，\(\zeta\)代表映射后乘以的系数，\(\gamma\)代表margin的缩放系数,\(Q\)代表进行了几次方的映射.

这儿我想说一下映射后的维度为:

\[ \begin{pmatrix} n+Q\\ Q \end{pmatrix} \]

Gauassian Kernel

这是一个特别的核，因为它可以映射到无穷维空间,主要是利用了泰勒展开,下面是其中一个高斯核(也叫做径向基函数(Radial Basis Function,简称RBF))的逆推过程:

\[ \begin{align} K(x,x^{'})&=e^{-(x-x^{'})^{2}}\\ &=e^{-(x)^{2}}e^{-(x^{'})^{2}}e^{(2xx^{'})}\\ &\mathop{}_{=}^{Taylor}e^{-(x)^{2}}e^{-(x^{'})^{2}}(\sum_{i=0}^{\infty }\frac{(2xx^{'})^{i}}{i!})\\ &=\sum_{i=0}^{\infty }(e^{-(x)^{2}}e^{-(x^{'})^{2}}\sqrt{\frac{2^{i}}{i!}}\sqrt{\frac{2^{i}}{i!}}(x)^{i}(x^{'})^{i})\\ &=\Phi (x)^{T}\Phi(x^{'})\\\\ 其中:\\ &\Phi (x)=e^{-(x^{2})}\cdot(1,\sqrt{\frac{2^{1}}{1!}}x,\sqrt{\frac{2^{2}}{2!}}x^{2},\ldots) \end{align} \]

高斯核更一般的形式:

\[ K(x,x^{'})=e^{-\gamma(x-x^{'})^{2}}\\ \gamma=\frac{1}{2\sigma^{2}}\\ with \quad \gamma>0 \]

相对于多项式核，高斯核只需要选择一个参数\(\gamma\). \(\gamma\)越大，\(\sigma\)越小，高斯函数很高很廋，会造成只作用于支持向量样本附近，容易过拟合