机器学习基础(7)-支持向量机SVM与核技巧

线性支持向量机

硬间隔最大化（线性可分支持向量机）

背景引入

回顾目前我们学过的算法，其中感知机PLA算法利用误分类的点进行迭代修正，最终求得分离超平面。不过PLA最终得到的答案与初始值以及学习的过程有关，也就是说最终的得到的分离超平面有很多，对于线性可分的数据集来说，这些超平面都能满足分离的要求。但是这些结果相互之间是存在好坏之分的。一种评判依据就是训练集中的点到分离超平面的最近距离，我们称之为间隔（margin）。直观上来说，我们希望这个间隔越大越好。对于训练数据集找到间隔最大的超平面意味着我们有充分大的确信度对训练数据进行分类。这是说我们得到的超平面不仅能够将正负实例分开，而且对于最难分开的实例点（离平面最近的点）也有足够大的确信度将它们分开。而这也正是支持向量机（Support Vector Machine，SVM）的思想所在。

因此我们可以正式进行问题描述，此时的输入空间为\(X\)；输出空间为\(Y = \{+1,-1\}\)；训练集为\(D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}\)，并且假设训练集线性可分；假设空间\(H\)有如下的形式，其中参数向量为\(w\)，偏置项为\(b\)，\(\hat{w}\)表示扩充后的\(w\)，\(\hat{x}\)表示扩充后的\(x\)： \[ h(x) = sign(w\cdot x+ b) = sign(w^Tx+b) = sign(\hat{w}^T\hat{x}) \] 硬间隔最大化的线性支持向量机要求满足间隔最大化，同时对所有的训练集都正确划分，即有如下的目标。相比于感知机，这里增加了间隔最大化的要求。 \[ \begin{aligned} &\max_w \quad margin(w,b)\\ \text{其中:} \quad & margin(w,b) = \min_{i=1,...,N} distance(x_i,w,b)\\ \text{并且需要满足:} \quad & y_i(w^Tx_i+b) > 0 ,i=1,2,...,N \end{aligned} \]

线性支持向量机对应训练集线性可分，不允许错分对应硬间隔。

间隔计算

上面我们初步定义了SVM需要优化的目标，其中需要计算样本点\(x_i\)到超平面\(w^Tx+b=0\)的距离。

在超平面的方程中，\(w\)为超平面的法向量。我们现在需要计算向量\(x\)到这个超平面的距离，考虑在超平面上的一个点\(x^{'}\)，则它满足\(w^Tx^{'} = -b\)。向量\(x\)到超平面的距离，可以通过向量\(x-x^{'}\)在法向量\(w\)上的投影长度进行计算，而投影又可以通过向量内积进行计算，因此有： \[ distance(x,w,b) = |\frac{w^T}{||w||}(x-x^{'})| = \frac{1}{||w||}|w^Tx+b| \] 而由于对于这个超平面来说，所有的点满足\(y_i(w^Tx_i+b)>0\)，因此我们可以借助\(y_i\in\{+1,-1\}\)来脱去绝对值，即： \[ distance(x_i,w,b)=\frac{1}{||w||}y_i(w^Tx_i+b) \] 实际上，关于间隔（距离），有函数间隔和几何间隔的概念。

在超平面\(w^Tx+b=0\)确定的情况下，\(|w^Tx+b|\)能够相对地表示点\(x\)距离超平面的远近，而\(w^T+b\)的符号与类标记\(y\)的符号是否一致能够表示分类是否正确，所以可以用\(y(w^Tx+b)\)来表示分类的正确性以及确信度，而这就是函数间隔（function margin）的概念。

而继续考虑超平面，在成比例变化\(w,b\)的条件下，超平面没有发生变化，但是函数间隔会成比例变化。因此我们可以对\(w\)进行某些约束，例如可以进行规范化，使得\(||w||=1\)，此时的函数间隔就是几何间隔（geometric margin），实际上也就是我们刚得到的点到超平面的距离。

原始模型描述

经过距离计算之后，我们的优化目标就可以写成下面的形式： \[ \begin{aligned} &\max_w \quad margin(w,b)\\ \text{其中:} \quad & margin(w,b) = \min_{i=1,...,N} \frac{1}{||w||}y_i(w^Tx_i+b)\\ \text{并且需要满足:} \quad & y_i(w^Tx_i+b) > 0 ,i=1,2,...,N\\ \end{aligned} \] 注意到我们等比例放缩\(w,b\)，超平面本身并不会发生变化。因此我们可以等比例缩放，使得离超平面最近的点\((x_j,y_j)\)，对应有\(y_j(w^Tx_j+b)=1\)。此时则有： \[ margin(w,b) = \frac{1}{||w||} \] 同时根据margin的概念，有： \[ \frac{1}{||w||}y_i(w^Tx_i+b) \ge \frac{1}{||w||}\\ y_i(w^Tx_i+b)-1\ge 0,i=1,2,...,N \] 另一方面，我们需要最大化margin，实际上可以转化为最小化倒数，并且进行平方，增加系数都不会影响最优化的结果，即我们可以进行如下的最优化转换： \[ \max_{w,b} \frac{1}{||w||} \rightleftharpoons \min_{w,b} \frac{1}{2}||w||^2 =\min_{w,b} \frac{1}{2}w^Tw \] 至此，我们就推导得到了硬边界最大化的线性支持向量机模型（也叫做线性可分支持向量机）的原始描述：

输入空间为\(X\)；输出空间为\(Y = \{+1,-1\}\)；训练集为\(D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}\)，且有\(x_i \in X, y_i \in Y\)，并且训练集线性可分；假设空间\(H\)有如下的形式，其中参数向量为\(w\)，偏置项为\(b\)，\(\hat{w}\)表示扩充后的\(w\)，\(\hat{x}\)表示扩充后的\(x\)： \[ h(x) = sign(w\cdot x+ b) = sign(w^Tx+b) = sign(\hat{w}^T\hat{x}) \] 优化目标是一个带限制的优化问题： \[ \text{优化目标 :}\quad\min_{w,b} \frac{1}{2}w^Tw\\ \text{限制条件 :}\quad y_i(w^Tx_i+b)\ge1,i=1,2,...,N \] 这个问题实际上是一个凸二次规划问题。求解凸二次规划问题的方法有很多，这里不具体介绍凸二次规划问题的求解方法，总之我们通过其中任意一种就可以得到最终的解，从而得到分离超平面。

从直觉来看，我们会认为支持向量机的分类效果更好，经过优化目标推导之后，可以看出支持向量机和正则化的思想有些类似，正则化的目标是将\(E_{in}\)最小化，同时对模型的复杂度增加限制条件\(w^Tw\le C\)。而SVM的目标是\(w^Tw\)的最小化，而条件是\(y_i(w^Tx_i+b)\ge 1\)，即保证了\(E_{in} = 0\)。可以说，SVM和正则化的目标和限制条件分别对调了，考虑的内容是类似的，效果也相近。

支持向量

在线性可分的情况下，训练数据集的样本点中，与分离超平面距离最近的样本点的实例称为支持向量（Support Vector）。更具体地说，支持向量是使约束条件等号成立的点，即： \[ y_i(w\cdot x_i+b)-1=0 \] 对于\(y_i=+1\)的正例点，支持向量落在超平面\(H_1:w\cdot x + b = 1\)上；而对于\(y_i = -1\)的负例点，支持向量落在超平面\(H_2:w\cdot x+b=-1\)上。注意到这两个超平面相互平行，并且没有实例点能够落在它们中间，即在\(H_1,H_2\)之间形成了一条长带，而我们最终要得到的分离超平面与它们平行，并且位于它们的中央，\(H_1,H_2\)之间的距离就是间隔。

在决定分离超平面的时候，实际上只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量，将改变所求的解，而其他向量在间隔边界之外的改变甚至删除，并不会改变最终的解。这也就是为什么这个模型称为支持向量机，它最终的结果是由较少但是很重要的训练样本决定的。

对偶问题描述

我们已经看到了线性支持向量机硬间隔最大化的原始形式，现在则可以应用拉格朗日对偶性来得到原始问题的对偶问题，通过求解对偶问题得到原始问题的最优解。我们将在下面看到，对偶问题往往更加容易求解，同时对偶问题的形式自然引入核函数，为后续的非线性支持向量机作铺垫。拉格朗日对偶性的说明在记录在后文附加参考中。

我们可以先将原始问题表达为广义拉格朗日的极小极大问题，原始问题的优化目标为\(\min_{w,b} \frac{1}{2} w^Tw\)，约束条件为\(1-y_i(w^Tx_i+b) \le 0\)，引入拉格朗日乘子\(\alpha_i\ge0\)，则有拉格朗日表达式为： \[ L(w,b,\alpha) = \frac{1}{2}w^Tw + \sum_{i=1}^N\alpha_i[1-y_i(w^Tx_i+b)] \] 对应的极小极大问题就是： \[ \min_{w,b}\max_{\alpha;\alpha_i\ge 0} \frac{1}{2}w^Tw + \sum_{i=1}^N\alpha_i[1-y_i(w^Tx_i+b)] \] 对偶问题的形式就是： \[ \max_{\alpha;\alpha_i\ge 0} \min_{w,b} \frac{1}{2}w^Tw + \sum_{i=1}^N\alpha_i[1-y_i(w^Tx_i+b)] \] 我们可以对对偶问题继续进行形式上的转化。首先令拉格朗日函数的梯度为0： \[ \begin{aligned} \bigtriangledown_wL(w,b,\alpha)& = w - \sum_{i=1}^N \alpha_iy_ix_i = 0\\ \bigtriangledown_wL(w,b,\alpha)& = -\sum_{i=1}^N \alpha_iy_i=0\\ \text{可以得到:}&\\ w &= \sum_{i=1}^N \alpha_iy_ix_i\\ \sum_{i=1}^N &\alpha_iy_i=0 \end{aligned} \] 将得到的两个表达式代入拉格朗日函数的极小中，可以得到： \[ \begin{aligned} \min_{w,b}L(w,b,\alpha) &= \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^N \alpha_i - \sum_{i=1}^N\alpha_iy_i[(\sum_{j=1}^N\alpha_jy_jx_j)\cdot x_i] \\& \quad- b\sum_{j=1}^N\alpha_iy_i \\ &= -\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^N\alpha_i \end{aligned} \] 这一步相当于我们利用拉格朗日乘子消去了式子中的\(w,b\)，这样关于\(w,b\)的极小问题就可以直接写为： \[ \min_{w,b}L(w,b,\alpha) =-\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^N\alpha_i \] 对偶问题接下来还需要求解极大，通过增加负号我们可以将极大问题转化为极小问题： \[ \begin{aligned} \text{对偶问题:} &\quad \max_{\alpha} \min_{w,b}L(w,b,\alpha)\\ \text{等价于:} &\quad \min_{\alpha}\{-[\min_{w,b}L(w,b,\alpha)]\}\\ \text{带入表达式:} &\quad \min_{\alpha} \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) - \sum_{i=1}^N\alpha_i \end{aligned} \] 至此对偶问题就可以进一步转化为等价的形式，这也是线性可分支持向量机的对偶问题描述： \[ \begin{aligned} \min_{\alpha} \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) - \sum_{i=1}^N\alpha_i \\ s.t.\quad \sum_{i=1}^N \alpha_iy_i = 0,\alpha_i\ge0;i=1,2,...,N \end{aligned} \] 我们引入对偶问题的目的是希望能够通过求解对偶问题来得到原始问题的解。但是这是有前提的，即两个问题的最优解相同。综合考虑原始问题和对偶问题，有\(f(w),1-y_i(w^Tx_i+b)\)为凸函数，且存在\(w,b\)使得所有的\(1-y_i(w^Tx_i+b) < 0\)成立，因此有两个问题的最优解相同（详见附加参考），我们可以通过求解对偶问题来得到原始问题的解。

对偶问题求解

对偶问题同样是一个凸二次规划问题，并且是关于拉格朗日系数\(\alpha\)的。我们可以通过相关算法求得最优解\(\alpha^*\)。而这一部分主要在于如何通过对偶问题的最优解\(\alpha^*\)得到原始问题的最优解\(w^*,b^*\)。

假设\((w^*,b^*,\alpha^*)\)为对偶问题的最优解（同时也是原始问题的最优解），则此时最优解会满足KKT条件。 \[ \begin{aligned} 【梯度为0条件】&\bigtriangledown_wL(w^*,b^*,\alpha^*) = w^* - \sum_{i=1}^N \alpha^*_iy_ix_i = 0\\ &\bigtriangledown_wL(w^*,b^*,\alpha^*) = -\sum_{i=1}^N \alpha^*_iy_i=0\\ 【最优解存在条件】&\alpha_i^*[1-y_i(w^{*T}x_i+b^*)] = 0, \quad i=1,2,...,N\\ 【拉格朗日乘子条件】&\alpha_i^* \ge 0,\quad i=1,2,...,N\\ 【原始问题约束】&1-y_i(w^{*T}x_i+b^*) \le 0, \quad i=1,2,...,N\\ \end{aligned} \] 其中可以得到： \[ w^* = \sum_{i=1}^N \alpha_i^*y_ix_i \] 而在拉格朗日乘子当中必定存在\(\alpha^*_j >0\)，否则\(w^* = 0\)，而0并不满足最优解的条件。因此，最优解\(w^*\)可以表示为某些拉格朗日乘子\(\alpha^*_j\)的和对应样本点数据\((x_j,y_j)\)的线性组合，其中\(\alpha^*_j>0\)。同时考虑上面的最优解存在条件，由于\(\alpha^*_j >0\)，则必然有： \[ 1-y_j(w^{*T}x_j + b^*) = 0 \] 带入\(w^*\)的表达式，且注意到\(1 = y_j^2\)，则有： \[ b^* = y_j - \sum_{i=1}^{N}\alpha_i^*y_i(x_i\cdot x_j) \] 带入最优解\(w^*,b^*\)，得到最终的分类决策函数如下，这也是线性可分支持向量机的对偶形式： \[ h(x) = sign(\sum_{i=1}^N\alpha^*_iy_i(x\cdot x_i) + b^*) \] 从这个表达式中我们可以看出，分类决策函数只依赖于输入\(x\)和训练样本输入的内积。同时观察\(w^*,b^*\)的求解，可以看到它们即仅依赖于训练数据中对应于\(\alpha_j^*>0\)的样本点\((x_j,y_j)\)，而其他的样本点对\(w^*,b^*\)没有影响。这些点就是支持向量。更进一步，支持向量\((x_j,y_j)\)需要满足对应的\(\alpha_j^*>0\)，也就有\(1-y_j(w^{*}\cdot x_j + b^*) = 0\)。这表明了支持向量一定在间隔边界上，对应了在原始问题中支持向量的定义。

联想到感知机算法中，最终的最优解\(w\)也能够表示为某种线性组合的形式，其中有贡献的是在训练过程中被误分类的那些点。SVM的最优解也表示为某种线性组合的形式，其中有贡献的是支持向量。

软间隔最大化（线性支持向量机）

背景引入

线性可分的支持向量机要求训练集是线性可分的，对于线性不可分的训练数据来说是不适用的，因为此时不等式约束不能完全成立。但是大多情形下，训练数据集是线性不可分的，所以我们希望能够将它扩展到线性不可分的问题上。为了达到这个目的，我们需要修改硬间隔最大化，使其成为软间隔最大化。

具体来说，我们并不会要求每个点都能够被完美分开，而是允许它们犯错，并且对每个样本点\((x_i,y_i)\)都引入一个对应的松弛变量\(\xi_i\ge 0\)，它表示每个点犯错误的程度，松弛变量越小，代表点犯错误的程度越小；松弛变量越大，代表点犯错误的程度越大，甚至会越过边界。这样样本点满足的条件就可以转化为： \[ y_i(w^Tx_i + b) \ge 1 - \xi_i \] 引入了松弛变量，我们的优化目标也需要进行改进，我们应该将松弛变量也纳入优化目标中，尽可能最小化松弛变量带来的代价，即可以得到如下的优化目标： \[ \min_{w,b,\xi} \frac{1}{2} w^Tw + C\sum_{i=1}^N \xi_i \] 其中我们引入一个\(C>0\)的系数，一般称之为惩罚参数，它用来控制两项的比例。在目标优化函数中，前项表示尽可能使间隔最大，后项表示使误分类的代价尽可能小，而\(C\)就是用来调和二者的系数。

原始模型描述

于是，我们可以对软间隔最大化的线性支持向量机模型（也叫线性支持向量机）进行描述：

输入空间为\(X\)；输出空间为\(Y = \{+1,-1\}\)；训练集为\(D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}\)，且有\(x_i \in X, y_i \in Y\)，并且训练集线性不可分；假设空间\(H\)有如下的形式，其中参数向量为\(w\)，偏置项为\(b\)，\(\hat{w}\)表示扩充后的\(w\)，\(\hat{x}\)表示扩充后的\(x\)： \[ h(x) = sign(w\cdot x+ b) = sign(w^Tx+b) = sign(\hat{w}^T\hat{x}) \] 优化目标是一个带限制的优化问题： \[ \begin{aligned} \text{优化目标 :} &\quad\min_{w,b} \frac{1}{2}w^Tw + C\sum_{i=1}^N\xi_i\\ \text{限制条件 :} &\quad y_i(w^Tx_i+b)\ge1 - \xi_i,i=1,2,...,N\\ \quad &\quad\xi_i\ge 0,i=1,2,...,N \end{aligned} \] 这个问题同样也是一个凸二次规划问题，可以通过相关方法求得问题的解。同时可以知道的是，\(w\)的解是唯一的，而\(b\)的解可能不唯一，而是存在于一个区间中。与线性可分支持向量机相比，线性支持向量机可以应用在线性不可分的数据上，因此它具有更广的适用性。

对偶问题描述

与硬间隔最大化的推导过程一样，在软间隔最大化中，我们同样可以先根据原始问题得到等价的广义拉格朗日的极小极大问题描述，之后得到对应的对偶问题描述，并且可以推导出对偶问题的等价形式。

对于软间隔最大化的原始问题，它的拉格朗日函数如下： \[ L(w,b,\xi,\alpha,\beta) = \frac{1}{2} w^Tw + C\sum_{i=1}^N \xi_i + \sum_{i=1}^N\alpha_i[1-\xi_i - y_i(w^Tx_i + b)] - \sum_{i=1}^N\beta_i \xi_i \] 得到原始问题的等价极小极大描述： \[ \min_{w,b,\xi;\xi_i\ge0}\max_{\alpha,\beta;\alpha_i\ge0 ,\beta_i\ge 0} L(w,b,\xi,\alpha, \beta) \] 对偶问题则是： \[ \max_{\alpha,\beta;\alpha_i\ge0 ,\beta_i\ge 0}\min_{w,b,\xi;\xi_i\ge0} L(w,b,\xi,\alpha, \beta) \] 令拉格朗日函数对\(w,b,\xi\)的偏导分别为0，即： \[ \begin{aligned} \bigtriangledown _wL (w,b,\xi,\alpha,\beta) &= w - \sum_{i=1}^N \alpha_i y_ix_i = 0 \\ \bigtriangledown _bL (w,b,\xi,\alpha,\beta) &= -\sum_{i=1}^N\alpha_iy_i = 0\\ \bigtriangledown _\xi L(w,b,\xi,\alpha,\beta) &= \sum_{i=1}^N C - \sum_{i=1}^N\alpha_i - \sum_{i=1}^N\beta_i = 0\\ \end{aligned} \] 则可以得到： \[ \begin{aligned} &w = \sum_{i=1}^N\alpha_iy_ix_i\\ &\sum_{i=1}^N \alpha_iy_i = 0 \\ &C - \alpha_i - \beta_i = 0 \end{aligned} \] 将这三个式子带入原始的拉格朗日函数的极小中，则可以消去\(w,b,C\)： \[ \begin{aligned} \min_{w,b,\xi}L(w,b,\xi,\alpha,\beta) &= \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + C\sum_{i=1}^N\xi_i + \sum_{i=1}^N\alpha_i - \sum_{i=1}^N\alpha_i\xi_i \\ & \quad- \sum_{i=1}^N\alpha_iy_ib- \sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) - \sum_{i=1}^N\beta_i\xi_i \\ & = -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^N \alpha_i \end{aligned} \] 可以看到上面的式子只和\(\alpha\)有关，\(\beta\)被消除了，因此对偶问题就可以描述如下： \[ \begin{aligned} \max_{\alpha} \quad &-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^N \alpha_i \\ s.t. \quad &\sum_{i=1}^N\alpha_iy_i = 0,C - \alpha_i - \beta_j = 0, \\ & \alpha_i \ge 0, \beta_i \ge 0, i = 1,2,...,N \end{aligned} \]

增加负号将极大化转化为极小化，同时可以利用其中的等式约束\(C = \alpha_i + \beta_i\)来消去\(\beta_i\)的约束，得到最终的线性支持向量机的对偶问题描述： \[ \begin{aligned} \min_{\alpha} \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) - \sum_{i=1}^N\alpha_i \\ s.t.\quad \sum_{i=1}^N \alpha_iy_i = 0,0 \le\alpha_i\le C;i=1,2,...,N \end{aligned} \] 对比之前线性可分支持向量机的对偶问题描述，可以发现这里唯一的不同之处在于约束条件中\(\alpha_i\)增加了上限\(C\)。于是我们也可以证明对偶问题和原始问题有相同的最优解。

对偶问题求解

接下来则可以利用KKT条件来计算最优解的形式，同样假设最优解为\((w^*,b^*,\xi^*,\alpha^*,\beta^*)\)，于是有： \[ \begin{aligned} 【梯度为0条件】 &\bigtriangledown_{w} L(w^*,b^*,\xi^*,\alpha^*,\beta^*) = w^* - \sum_{i=1}^N \alpha^*_i y_i x_i = 0 \\ &\bigtriangledown_bL(w^*,b^*,\xi^*,\alpha^*,\beta^*) = -\sum_{i=1}^N \alpha^*_iy_i=0\\ &\bigtriangledown_\xi L(w^*,b^*,\alpha^*) = C - \alpha_i^* - \beta_i^*=0\\ 【最优解存在条件】 &\alpha_i^*[1 - \xi_i^*-y_i(w^{*T}x_i+b^*)] = 0, \quad \beta_i^* \xi_i^* = 0\\ 【拉格朗日乘子条件】 &\alpha_i^* \ge 0, \quad \beta_i^* \ge 0\\ 【原始问题约束】 &1-y_i(w^{*T}x_i+b^*) \le 0,\quad \xi_i^* \ge 0\\ \end{aligned} \] 可以根据上面的式子推导得出： \[ \begin{aligned} w^* &= \sum_{i=1}^N\alpha_i^*y_ix_i\\ b^* &= y_i - \sum_{i=1}^N \alpha^* y_i(x_i \cdot x_j) \end{aligned} \] 其中\(b^*\)的计算需要选择\(\alpha^*\)的一个分量\(\alpha^*_j\)满足（\(0 < \alpha^*_j < C\)）计算得出。理论上解可能不唯一。

支持向量

在线性不可分的情况下，对应\(\alpha_i^* > 0\)的样本点\((x_i,y_i)\)的实例\(x_i\)被称为支持向量，此时的支持向量的情况更加复杂，它可能在间隔的边界上，也坑在间隔之间，还可能被误分类：

• \(0<\alpha_i^* < C\)，则\(\xi_i = 0\)：支持向量正好落在间隔边界上
• \(\alpha_i^* = C,0 < \xi_i < 1\)：支持向量被分类正确
• \(\alpha_i^* = C,\xi_i = 1\)：支持向量在分离超平面上
• \(\alpha_i^* = C,\xi_i > 1\)：支持向量被分类错误

同样的，在所有的训练集样本点中，只有支持向量会对最后的结果产生影响。可以想见的是，支持向量的数量越多，表示模型就可能越复杂，越有可能造成过拟合。因此支持向量的数量在SVM模型选择中也是比较重要的，通常我们会选择支持向量较少的模型，然后在剩下的模型中使用交叉验证，比较选择最佳模型。

合页损失函数

实际上，线性支持向量机还可以从另一个角度来理解，就是优化如下的目标函数： \[ \sum_{i=1}^{N}[1-y_i(w\cdot x_i + b)_+] + \lambda ||w||^2 \] 目标函数的第二项则是正则项，使用的是参数向量的L2范数。目标函数的第一项是损失函数，通常被称为合页损失函数（Hinge Loss Function）： \[ L(y(w\cdot x + b)) = [1 - y(w\cdot x + b)]_+ \] 其中下标\(+\)表示取正函数： \[ [z]_+ = \begin{cases} z, \quad z>0\\ 0, \quad z \le 0 \end{cases} \] 从直觉上看，这种方式将\([1-y_i(w\cdot x_i + b)]_+\)看作每个样本点的损失。当样本点\((x_i,y_i)\)被正确分类且函数间隔大于1时，损失为0；否则损失为\(1 - y_i(w\cdot x_i +b)\)。

这种理解可以从线性支持向量机的原始问题描述进行推导得来。线性支持向量机的原始问题描述如下： \[ \begin{aligned} \text{优化目标 :}\quad&\min_{w,b} \frac{1}{2}w^Tw + C\sum_{i=1}^N\xi_i\\ \text{限制条件 :}\quad& y_i(w\cdot x_i+b)\ge1 - \xi_i,i=1,2,...,N\\ \quad \quad&\xi_i\ge 0,i=1,2,...,N \end{aligned} \] 令\([1 - y_i(w\cdot x_i + b)]_+ = \xi_i\)，则有\(\xi_i \ge 0\)成立，且有\(\xi_i \ge 1 - y_i(w\cdot x_i + b)\)，即这样能够满足两个限制条件。再取\(\lambda = \frac{1}{2C} > 0\)，则有优化目标为： \[ \begin{aligned} &\min_{w,b} \frac{1}{2} w^Tw + \frac{1}{2\lambda} \sum_{i=1}^N [1-y_i(w\cdot x_i + b)]_+\\ &\text{等价于}\\ &\min_{w,b} \sum_{i=1}^N[1 - y_i(w\cdot x_i + b)]_+ \lambda ||w||^2 \end{aligned} \] 而这恰好就是利用合页损失函数的形式。

从这个角度理解，我们追求的间隔最大化等价于正则化，一定程度上起到了防止过拟合的作用。

非线性支持向量机

特征空间转换

在此之前，我们讨论的都是线性分类模型，而另一类非常普遍的问题则是非线性分类问题。看名字就知道，我们需要使用非线性模型才能很好地处理非线性分类问题。一般来说，对于一个二分类问题，如果能够使用输入空间中的一个超平面将正负例分开，则这个问题是线性可分问题。而如果需要使用输入空间中的一个超曲面才能够完成认为，则这个问题是非线性可分问题。

解决非线性问题的一种常用方法是特征空间转换。具体来说，我们可以使用某种变换将输入\(x\)从输入空间变换到特征空间中，然后在特征空间中利用线性模型来处理。假设原来的输入空间为\(X\)，转换后的特征空间为\(Z\)，则我们需要的是一个这样的映射，它将\(x \in X\)映射为\(z\in Z\)： \[ z = \phi(x) \]

核技巧与核函数

但是通常情况下，特征空间\(Z\)一般是高维空间，甚至可能是无限维的，在这样的空间中进行向量运算，会带来很高的复杂度。因此我们希望能够找到稍微简单的方式来进行特征空间中的计算。这就引出核技巧的思想。

首先介绍核函数的概念。假设原始输入空间为\(X\)，特征空间为\(Z\)，存在一个\(X \rightarrow Z\)的映射\(\phi\)，如果对于所有的\(x_1,x_2 \in X\)，函数\(K(x_1,x_2)\)都能满足下面的条件，则我们称函数\(K(x_1,x_2)\)为核函数。其中计算的是映射后的内积。 \[ K(x_1,x_2) = \phi(x_1)\cdot\phi(x_2) \] 原本按照正常的流程，我们先定义一个映射\(\phi\)，然后将每个输入\(x\in X\)映射为\(z \in Z\)，之后在特征空间\(Z\)中进行内积运算，即先进行转换再计算内积。而核技巧的想法是，既然特征空间中的计算比较复杂，那就不定义映射\(\phi\)，而是直接定义核函数\(K(x_1,x_2)\)。核函数的计算结果是映射后特征向量的内积，但是核函数本身是关于\(x_1,x_2\in X\)的函数，在输入空间中完成计算，这样就一定程度上降低了运算的复杂度。

可以看到对于一个给定的核函数\(K(x_1,x_2)\)来说，特征空间与映射函数的取法并不唯一，可以取不同的特征空间，在同一个特征空间中也可以取不同的映射。而定义核函数的好处在于我们不需要关注具体的映射\(\phi\)，只需要关注一个函数是否是合法的核函数即可。如果已知映射函数\(\phi\)，我们可以根据定义直接得到核函数。而更常见的情况是，我们需要在不知道具体映射函数\(\phi\)的前提下判断一个关于\(x_1,x_2\)的函数是否是核函数。

通常所说的核函数是正定核函数。在数学上可以证明，假设\(K(x_1,x_2)\)是定义在\(X\times X\)上的对称函数，如果对于任意的\(x_i \in X，i=1，2,...,m\)，\(K(x_1,x_2)\)对应的Gram矩阵 \[ K = [K(x_i,x_j)]_{m\times m} \] 是半正定矩阵，则\(K(x_1,x_2)\)是正定核函数，也就是我们需要的核函数。

这个定义能够帮助我们来构造核函数。不过对于一个具体的核函数来说，检测它是否为正定核函数并不容易，因为需要对任意有限输入集\(\{x_1,x_2,...,x_m\}\)来验证\(K\)对应的Gram矩阵是否是半正定的。因此在实际情况中，我们往往会应用已有的核函数。

常用核函数

多项式核函数定义如下： \[ K(x_1,x_2) = (x_1 \cdot x_2 + 1)^P \] 高斯核函数定义如下： \[ K(x_1,x_2) = \exp(- \frac{||x_1-x_2||^2}{2\sigma^2}) \]

非线性支持向量机

在之前线性支持向量机中，无论是目标函数还是决策函数，最终都只会涉及到输入实例与其他实例之间的内积，即\(x \cdot x_i\)。我们可以很自然地在其上应用核函数，将其替换为\(K(x,x_i)\)，这样，对偶问题的目标函数就变为了： \[ \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i\alpha_jy_iy_j K(x_i,x_j) - \sum_{i=1}^N \alpha_i \] 而决策函数也对应变为： \[ \begin{aligned} f(x) &= sign(\sum_{i=1}^N\alpha^*_iy_i\phi(x_i)\cdot \phi(x) + b^*)\\ &=sign(\sum_{i=1}^N\alpha^*_iy_iK(x_i,x) + b^*) \end{aligned} \] 这也就是非线性支持向量机的思想。这样做相当于将原始输入\(x_i\)，都经过映射变为特征空间中的\(\phi(x)\)，之后在特征空间中学习线性向量机。当映射函数是非线性函数的时候，最终学习到的含有核函数的支持向量机就是一个非线性的模型。通过核技巧，使得学习隐式地在特征空间中完成，而无需显式地定义特征空间与映射函数。

这里可以应用核函数的关键在于我们最终的\(w^*\)能够表示成输入实例\(x_i\)的某种线性组合。事实上，对于L2正则化的线性模型，如果它的最小化问题形式能够形式为： \[ \min_{w} \frac{1}{N} \sum_{i=1}^N err(y_i,w^Tx_i) + \lambda w^Tw \] 则最终最优化的\(w^*\)就能够表示为： \[ w^* = \sum_{i=1}^N \beta_ix_i \] 由此，我们实际上也可以将核技巧用在线性回归，Logistic回归中。

阶段总结

整个SVM的学习过程，我们首先从PLA的多解出发，希望从中选择较好的分类模型，从而得到硬间隔最大化的策略。之后优化目标，推导了原始问题，再根据拉格朗日对偶性得到对偶问题。根据定理，发现对偶问题与原始问题有相同的最优解，于是可以通过解对偶问题得到原始问题的解。这便是硬间隔最大化的线性支持向量机。

硬间隔最大化要求所有实例点都需要被划分正确，也就是线性可分的情况。一种常见的情况是实例点基本线性可分，于是引入软间隔最大化，对每个实例点的错误程度引入\(\xi_i\)，同时优化目标增加尽可能最小化所有实例点错误程度之和。根据优化目标以及拉格朗日对偶性，同样可以得到原始问题和对偶问题，它们也具有相同的最优解，这就是软间隔最大化的线性支持向量机。

这两种方式仍然只是线性模型，无法处理线性不可分的情况。注意到模型中无论是优化目标函数还是最终的决策函数，都只涉及实例之间的内积，所以可以很自然地使用核技巧，将输入空间中的线性不可分问题转化为特征空间中的线性可分问题，之后在特征空间中使用线性支持向量机，同时核函数的存在一定程度上控制了计算的复杂度，这就是非线性支持向量机。

附加参考

凸二次规划问题

凸优化问题指的是如下的约束最优化问题： \[ \begin{aligned} \min_{w} &\quad f(w)\\ s.t. & \quad g_i(w) \le 0, i=1,2,...,k\\ &\quad h_i(w) = 0, i=1,2,...,l \end{aligned} \] 其中，目标函数\(f(w)\)和约束函数\(g_i(w)\)都是\(R^n\)上的连续可微的凸函数，约束函数\(h_i(w)\)是\(R^n\)上的仿射函数。（仿射函数\(f(x)\)指的是满足\(f(x) = a\cdot x +b\)的函数）

更近一步，如果目标函数\(f(w)\)是二次函数且约束函数\(g_i(w)\)是仿射函数的时候，上面的凸最优化问题就成为了凸二次规划问题。数学上可以证明，凸二次规划问题具有全局最优解，并且有许多最优化算法可以用于这一问题的求解。

拉格朗日对偶性

原始问题

假设\(f(x),c_i(x),h_j(x)\)是定义在\(R^n\)上的连续可微函数，则考虑如下的最优化问题，我们称为原始问题，记原始问题为\(P\)，原始问题的最优解为\(p^*\)： \[ \begin{aligned} \min_{x\in R^n} &\quad f(x)\\ s.t. & \quad c_i(x) \le 0, i=1,2,...,k\\ &\quad h_j(x) = 0, j=1,2,...,l \end{aligned} \] 为求解这一优化问题，我们可以引入拉格朗日函数： \[ L(x,\alpha,\beta) = f(x) + \sum_{i=1}^k \alpha_ic_i(x) + \sum_{j=1}^{l}\beta_jh_j(x) \] 其中\(\alpha_i,\beta_j\)为拉格朗日乘子，并且\(\alpha_i \ge 0\)。构造优化目标\(\theta(x)\)如下： \[ \theta(x) = \max_{\alpha,\beta;\alpha_i\ge 0} L(x,\alpha,\beta) \] 这是一个关于拉格朗日乘子的优化目标函数，是一个关于\(x\)的函数。考虑\(c_i(x),h_j(x)\)，如果对于某个\(x\)来说，存在\(c_{i'}(x) > 0\)或者\(h_{j'}(x) \ne 0\)，即\(x\)不满足原始问题的约束条件，则函数\(\theta(x)\)的值就是\(+\infty\)。而如果不存在，也就是\(x\)均满足原始问题的约束条件，则我们肯定可以取\(\alpha_i=0\)，使得\(\theta(x) = \max_{\alpha,\beta;\alpha_i\ge 0} L(x,\alpha,\beta) = f(x) + 0 + 0 = f(x)\)。也就是说，优化目标\(\theta(x)\)有如下性质，其中假设原始问题为\(P\)： \[ \theta_P(x) = \begin{cases} f(x),\quad x 满足原始问题P的约束\\ +\infty, \quad 不满足原始问题P的约束 \end{cases} \] 这样的话，我们继续考虑针对\(x\)极小化\(\theta_P(x)\)，即： \[ \min_{x} \theta_P(x) = \min_{x} \max_{\alpha,\beta;\alpha_i\ge 0} L(x,\alpha,\beta) \] 这个问题与原始问题是等价的，即它们具有相同的解。问题\(\min_{x} \max_{\alpha,\beta;\alpha_i\ge 0} L(x,\alpha,\beta)\)被称为广义拉格朗日函数的极小极大问题，也就是说我们将原始问题\(P\)表示为等价的广义拉格朗日的极小极大问题，它们具有相同的解，也就是： \[ p^* = \min_{x} \theta_P(x) \]

对偶问题

原始问题被表示为广义拉格朗日极小极大问题，它的对偶问题则是广义拉格朗日极大极小问题。

首先定义一个关于\(\alpha,\beta\)的函数： \[ \theta_D(\alpha,\beta) = \min_{x} L(x,\alpha,\beta) \] 之后对这个函数进行极大化，即： \[ \max_{\alpha,\beta;\alpha_i\ge0} \theta_D(\alpha,\beta) = \max_{\alpha,\beta;\alpha_i\ge0}\min_{x} L(x,\alpha,\beta) \] 于是我们可以广义拉格朗日极大极小问题表示为一个约束最优化问题，记该问题的最优解为\(d^*\)： \[ \begin{aligned} \max_{\alpha,\beta} \theta_D(\alpha,\beta) &= \max_{\alpha,\beta}\min_{x} L(x,\alpha,\beta)\\ s.t. \quad & \alpha_i \ge 0,i=1,2,...,k \end{aligned} \] 这样我们就给出了原始问题的对偶问题形式。

原始问题和对偶问题的关系

假设原始问题和对偶问题的最优解都存在，则对偶问题的最优解一定会小于等于原始问题的最优解，即\(d^* \le p^*\)。这个关系很容易证明，首先，对于任意的\(x,\alpha,\beta\)，都有： \[ \theta_D(\alpha, \beta) = \min_xL(x,\alpha,\beta) \le L(x,\alpha,\beta) \le \max_{\alpha,\beta} L(x,\alpha,\beta) = \theta_P(x) \] 也就是： \[ \theta_D(\alpha, \beta) \le \theta_P(x) \] 于是有： \[ d* = \max_{\alpha,\beta;\alpha_i\ge0}\theta_D(\alpha,\beta) \le \min_{x} \theta_P(x) = p^* \] 不过在某些条件下，两个问题的最优解相等，并且都在同一个\((x^*,\alpha^*,\beta^*)\)上取得最优解。此时可以通过求解对偶问题来得到原始问题的最优解。下面介绍一种特殊的情形，原始问题和对偶问题的最优解相同。

如果函数\(f(x),c_i(x)\)是凸函数，\(h_j(x)\)是仿射函数，且不等式约束\(c_i(x)\)均为严格可行（即存在\(x\)，对所有的\(c_i(x)\)都有\(c_i(x) < 0\)），则原始问题和对偶问题的最优解相同。并且\((x^*,\alpha^*,\beta^*)\)为最优解的充要条件是\((x^*,\alpha^*,\beta^*)\)满足Karush-Kuhn-Tucker（KKT）条件，具体如下： \[ \begin{aligned} 【梯度为0条件】&\bigtriangledown_{x} L(x^*,\alpha^*,\beta^*) = 0 \\ 【最优解存在条件】&\alpha_i^*c_i(x^*) = 0, \quad i=1,2,...,k\\ 【拉格朗日乘子条件】&\alpha_i^* \ge 0,\quad i=1,2,...,k\\ 【原始问题约束】&c_i(x^*) \le 0, \quad i=1,2,...,k\\ 【原始问题约束】&h_j(x^*) = 0,\quad j=1,2,...,l \end{aligned} \] 其中最优解存在条件也被称为KKT的对偶互补条件，两数相乘为0，意味着至少有一方为0。