1 支持向量机(SVM)

2 精简版(核方法)

核方法的基本思想是通过一个非线性变换，把输入数据映射到高维的希尔伯特空间中，在这个高维空间里，那些在原始输入空间中线性不可分的问题变得更加容易解决，甚至线性可分。支持向量机(Support Vector Machine，SVM)是一类最典型的核方法，下面将以支持向量机为例，对核方法进行简单的介绍。 支持向量机的基本思想是通过核函数将原始输入空间变换成一个高维(甚至是无穷维)的空间，在这个空间里寻找一个超平面，它可以把训练集里的正例和负例尽最大可能地分开(用更加学术的语言描述，就是正负例之间的间隔最大化)。那么如何才能通过核函数实现空间的非线性映射呢？让我们从头谈起。 假设存在一个非线性映射函数$\phi$，可以帮我们把原始输入空间变换成高维非线性空间。我们的目的是在变换后的空间里，寻找一个线性超平面$w^T\phi(x)=0$，它能够把所有正例和负例分开，并且距离该超平面最近的正例和负例之间的间隔最大。这个诉求可以用数学语言表述如下： $$>max\frac{2}{||w||} \\ >w^T\phi(x_i) \geq+1,如果y_i=+1 \\ >w^T\phi(x_i) \leq-1,如果y_i=-1 \\ >i=1,...,n >$$ 其中$\frac{2}{||w||}$是离超平面最近的正例和负例之间的间隔(如图2.6所示)。

​ 以上的数学描述等价于如下的优化问题： $$>min \frac{1}{2}||w||^2 \\ >y_i(w^T \phi(x_i)) \geq 1,i=1,...,n >$$ 上式中的约束条件要求所有的正例和负例分别位于超平面$w^T \phi(x)=0$的两侧。某些情况下，这种约束可能过强，因为我们所拥有的训练集有时是不可分的。这时候，就需要引入松弛变量$\xi$，把上述优化问题改写为： $$>min \frac{1}{2}||w||^2+C \sum_i{\xi_i} \\ >y_i(w^T \phi(x_i)) \geq 1- \xi \\ >\xi \geq 0 >i=1,...,n >$$ 其实这种新的表述等价于最小化一个加了正则项$\frac{1}{2}||w||^2$l的Hinge损失函数。这是因为当$1-y_i(w^T \phi(x_i))$小于0的时候，样本$x_i$被超平面正确地分到相应的类别里，$\xi_i =0$；反之，$\xi_i$将大于0，且是$1-y_i(w^T \xi (x_i)）$的上界：最小化$\xi_i$就相应地最小化了$y_i(w^T \phi(x_i)) \geq 1$。基于以上讨论，其实支持向量机在最小化如下的目标函数： $$>\hat l_n{(w)}=\frac{1}{2}||w||^2+\sum_{i=1}^{n}{max\{0,1-y_i(w^T \phi(x_i))\}} >$$ 其中，$\frac{1}{2}||w||^2$是正则项，对它的最小化可以限制模型的空间，有效提高模型的泛化能力(也就是使模型在训练集和测试集上的性能更加接近)。 为了求解上述有约束的优化问题，一种常用的技巧是使用拉格朗日乘数法将其转换成对偶问题进行求解。具体来讲，支持向量机对应的对偶问题如下： $$>\max_{\alpha}{\sum_{i=1}^{n}{\alpha_i}}-\frac{1}{2}\sum_{i=1}^{n}{\sum_{j=1}^{n}{\alpha_i \alpha_j y_i y_j \phi(x_i)^T \phi(x_j)}} \\ >s.t. \sum_{i=1}^{n}{\alpha_i y_i}=0,\alpha_i \geq 0 >$$ 在对偶空间里，该优化问题的描述只与$\phi(x_i)$和$\phi(x_j)$的内积有关，而与映射函数$\phi$本身的具体形式无关。因此，我们只需定义两个样本$x_i$和$x_j$之间的核函数$k(x_i,x_j)$，用以表征其映射到高维空间之后的内积即可： $$>k(x_i,x_j)=\phi(x_i)^T\phi(x_j) >$$ 至此，我们弄清楚了核函数是如何和空间变换发生联系的。核函数可以有很多不同的选择，以下列出了几种常用的核函数。

核函数	数学形式
多项式和	$k(x_i,x_j)=(x_i^Tx_j)^p,p \geq1$
高斯核	$k(x_i,x_j)=exp(-\frac{||x_i-x_j||^2}{2{\sigma}^2})$
拉普拉斯核	$k(x_i,x_j)=exp(-\frac{||x_i-x_j||}{\sigma}),\sigma >0$
Sigmoid核	$k(x_i,x_j)=tanh(\beta x_i^T x_j+\theta),\beta>0, \theta<0$

事实上，只要一个对称函数所对应的核矩阵满足半正定的条件，它就能作为核函数使用，并总能找到一个与之对应的空间映射。换言之，任何一个核函数都隐式地定义了一个再生核希尔伯特空间(Reproducing Kernel Hilbert Space，RKHS)。在这个空间里，两个向量的内积等于对应核函数的值。

>