CS229: 6

支持向量机, Support Vector Machine, SVM

支持向量机（Support Vector Machine, SVM）

之前我们看到，在解决分类问题时，无论是logistic regression还是感知机，都隐式或显式地引入了一个“平面”来分割空间，但实际上利用的性质都很少，很多时候分割并不是非常均匀，而SVM充分利用了“几何意义”使得分割尽可能均匀。

比如logistic regression的损失函数是带有一个对数的，会随着超平面和点的靠近而不均匀地快速增大，类似之前看到的在线性可分的训练集上，logistic regression会无限改进而无法收敛。而感知机直接看分类正确个数，就更不均匀了。

SVM的基本原理是用一个超平面（n维向量空间中一个n-1维的子空间）来分割空间（这在高维空间中一般是可行的），在超平面一侧的归为$y=1$，另一侧归为$y=-1$。超平面的选择原则是尽可能均匀，即夹在两个点集的“正中间”。

经典形式

定义超平面是

$$w^Tx+b=0$$

一个几何意义是，$w$是法向量

证明：任取超平面上两点$x_1,x_2$

$$w^Tx_1+b=0\\w^Tx_2+b=0$$

相减得

$$w^T(x_1-x_2)=0$$

而超平面上任一向量都有起始点$x_1,x_2$，所以$w$垂直于超平面上任一向量，$w$就是一个法向量。

空间中任一点$x_0$，到超平面的距离是

$$\frac{|w^Tx_0+b|}{||w||}$$

要想超平面夹在一个均匀的位置，也就是到两个点集的正中间，换句话说，超平面到两个点集的最小距离要相等。

从最值的角度来说，就是到两个点集的最小距离的$min$要最大。

两个最值不太好描述，进行一些转化形式化地来讲，就是

$$\max_{w,b}t\\ s.t. \forall 1\leq i\leq n,\frac{|w^Tx^{(i)}+b|}{||w||}\geq t$$

诶诶不太对，那怎么区别是否分类正确呢？是用符号，$y=\pm 1$

$$\max_{w,b}t\\ s.t. \forall 1\leq i\leq n,\frac{y^{(i)}(w^Tx^{(i)}+b)}{||w||}\geq t$$

$||w||$是非线性的，首先尝试处理，将其移项到右边，原问题等价于

$$\max_{w,b}t\\ s.t. \forall 1\leq i\leq n,y^{(i)}(w^Tx^{(i)}+b)\geq t||w||$$

我们还是想让约束尽可能简单，把$||w||$吸收进$t$，原问题等价于

$$\max_{w,b}\frac{t}{||w||}\\ s.t. \forall 1\leq i\leq n,y^{(i)}(w^Tx^{(i)}+b)\geq t$$

现在我们要求分类必须全部正确，所以$y^{(i)}(w^Tx^{(i)}+b)>0$。再把$t$吸收掉

$$\max_{w,b}\frac{t}{||w||}\\ s.t. \forall 1\leq i\leq n,y^{(i)}(\frac{w}{t}^Tx^{(i)}+\frac{b}{t})\geq 1$$

参数$w,t$是任取的，所以原问题转化成

$$\max_{w,b}\frac{1}{||w||}\\ s.t. \forall 1\leq i\leq n,y^{(i)}(w^Tx^{(i)}+b)\geq 1$$

倒数不好处理，用单调性直接转化成比较可导的形式

$$\min_{w,b}\frac{1}{2}||w||^2\\ s.t. \forall 1\leq i\leq n,y^{(i)}(w^Tx^{(i)}+b)\geq 1$$

这就是SVM的经典形式。

拉格朗日乘子法

转化成的问题的约束是线性的，考虑使用多元的拉格朗日乘子法来求解，先介绍一般的拉格朗日乘子法。

拉格朗日乘子法可以解决有等式和不等式约束的最优化问题。

如果问题是

$$\min_w f(w)\\ s.t. \forall 1\leq i \leq n,g_i(w)\leq 0;\forall 1\leq i \leq m,h_i(w)= 0$$

我们称下式为拉格朗日量(Lagrangian)

$$L(w,\alpha,\beta)=f(w)+\sum_{i=1}^{n}\alpha_ig_i(w)+\sum_{i=1}^{m}\beta_ih_i(w)$$

再定义

$$\theta_p=\max_{\alpha,\beta:\alpha_i\geq 0}L(w,\alpha,\beta)$$

这个量实际上是来约束拉格朗日量不要违法约束的，也就是说

$$\theta_p= \begin{cases} f(w) & \text{if } g_i(w)\ \text{and} \ h_i(w)= 0\\ +\infty & \text{if } g_i(w)>0\ \text{or} \ h_i(w)\neq 0\\ \end{cases}$$

那么现在原问题就等价于

$$\min_w \theta_p=\min_w \max_{\alpha,\beta:\alpha_i\geq 0}L(w,\alpha,\beta)$$

这就是一个双层，每层不同变量的最优化。

而冯诺依曼告诉了我们一个重要的不等式(minimax inequality)

$$f:W\times V\rightarrow R\\ \max_w \min_v f(w,v)\leq \min_v \max_w f(w,v)$$

那么原问题又可以转化为

$$\max_{\alpha,\beta:\alpha_i\geq 0}\min_w L(w,\alpha,\beta) \leq \min_w \max_{\alpha,\beta:\alpha_i\geq 0}L(w,\alpha,\beta)$$

记左边式子为$\theta_D$，称左边的最优化问题为原问题的对偶问题

非常精彩的是，在一些情况下，等号是成立的，我们可以借此完成原问题和对偶问题的转化

取等条件是$f$和$g_i$的海森矩阵都半正定，也就是说是凸函数，而且$h_i$一定是线性的不等式约束，也就是说形如$a^Tw+b$的形式。

直接回到原问题，不管minimax inequality成不成立，找出极值的一个必要条件是

$$\frac{\partial{L(w,\alpha,\beta)}}{\partial{w_i}}=0,\forall i\\ \frac{\partial{L(w,\alpha,\beta)}}{\partial{\beta_i}}=0,\forall i\\ \alpha_ig_i(w)=0,\forall i\\ g_i(w)\leq 0,\forall i\\ \alpha_i \geq 0,\forall i$$

第二行就是重新表述了等式的约束。

上面的条件称为KKT条件。

求解SVM

直接用拉格朗日乘子法

$$f(w)=\frac{1}{2}||w||^2\\ g_i(w)=-y^{(i)}(w^Tx^{(i)}+b)+1\leq 0\\ L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum_{i=1}^{n}\alpha_ig_i(w)$$

套用KKT条件来解，得

$$\nabla_w{L(w,b,\alpha)}=w-\sum_{i=1}^{n}\alpha_iy^{(i)}x^{(i)}\\ \nabla_w{L(w,b,\alpha)}=0 \iff w=\sum_{i=1}^{n}\alpha_iy^{(i)}x^{(i)}$$

$$\frac{\partial{}}{\partial{b}}L(w,b,\alpha)=-\sum_{i=1}^{n}\alpha_iy^{(i)}\\ \frac{\partial{}}{\partial{b}}L(w,b,\alpha)=0 \iff \sum_{i=1}^{n}\alpha_iy^{(i)}=0$$

使用minimax inequality，得到

$$\max_{\alpha,\beta:\alpha_i\geq 0}\min_{w,b} L(w,b,\alpha,\beta) = \min_{w,b} \max_{\alpha,\beta:\alpha_i\geq 0}L(w,b,\alpha,\beta)$$

使用KKT条件后再将$w$代入，正好是左边的式子，也就是说，现在我们知道原问题中$w$是能被$\alpha$线性表示的，而原问题有转化为了另一个关于$\alpha$的最优化问题

$$\max_{\alpha} W(\alpha)\\ W(\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)}\left< x^{(i)}, x^{(j)} \right>\\ s.t. \alpha_i\geq 0 \iff -\alpha_i\leq 0\\ \sum_{i=1}^{n}\alpha_iy^{(i)}=0$$

然后接下来要是硬求偏导能得到一个关于$\alpha$的线性方程组，但是实际中一般不会用这种方式来求解。

如果梯度下降的话，又很难满足这些约束，我们接下来发展新的方法来解决。

回到原问题来解$b$。

考虑超平面的几何意义，$b$应该是在正中间的，也就是说，要选取两侧到超平面距离最短的点

$$b=-\frac{\max_{y^{(i)}=-1}w^Tx^{(i)}+\min_{y^{(i)}=1}w^Tx^{(i)}}{2}$$

软间隔SVM

虽然只要维度够高，大概率能实现完美分类。但仍然有情况不能完美分类。而且完美分类不一定就是最优解（看讲义上的图）。

所以我们现在改造SVM，使其允许错误分类。

$$f(w)=\frac{1}{2} ||w||^2+C \sum_{i=1}^{k} \zeta_i\\ s.t. y^{(i)}({w^Tx^{(i)}+b})\geq 1-\zeta_i\\ \zeta_i\geq 0 \iff -\zeta_i\leq 0$$

重新再走一遍上面的流程，和上面基本一样，但是对$\zeta$求偏导可以得到

$$C=\alpha_i+\beta_i$$

最后转化为

$$\max_{\alpha} W(\alpha)\\ W(\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)}\left< x^{(i)}, x^{(j)} \right>\\ s.t. 0\leq \alpha_i\leq C\\ \sum_{i=1}^{n}\alpha_iy^{(i)}=0$$

此时KKT条件是

$$\frac{\partial{}}{\partial{\alpha_i}}W(\alpha)=0\\ \alpha_i (1-\zeta_i-y^{(i)}(w^Tx^{(i)}+b))=0\\ \beta_i\zeta_i=0\\ 0\leq \alpha_i \leq C\\ \zeta_i\geq 0$$

接下来讨论的都是基于这个形式的SVM。

坐标上升法(Coordinate Ascent)

先介绍这个方法，是后面要用到的。

回忆一下梯度下降法，我们每次选定了最优的方向后会迈出一小步，但是太慢了，而且每次不论用什么方法，都至少要对整个梯度计算一次，可以看到现在参数变成了$\alpha$，数量是训练集大小，实际上是非常大的。

那能不能想办法解决核心痛点，一次更新的维度太多的问题呢？

坐标上升法是一种很激进的方法。

还是用偏导的思想，直接将函数视为关于某一维的函数，那么可以直接在该维度取到最值，相应调整这一维的参数。

不断选择不同的维度，重复这个过程，就可以取到多元函数的最值。

SMO

如果直接使用坐标上升法其实是不行的，因为在其他维度确定的情况下，任一维度的$\alpha$都是不能变的，否则违法了那个和为0的等式。

SMO就是同时考虑两个变元，将一个用另一个表出，然后进行坐标上升法的最优化调整。

设调整的两个参数是$\alpha_1,\alpha_2,y^{(1)}\alpha_1+y^{(2)}\alpha_2=-\sum_{k=3}^{n} \alpha_ky^{(k)}$

以下都用$\alpha_2$表示$\alpha_1$。

代入$W(\alpha)$，加上之前的限制$0\leq \alpha\leq C$，实际上就是要使一个二次函数取到最值。

设只考虑二次函数的最值，取到了$\alpha_1^{new,unclipped},\alpha_1^{new} \in [L,H]\times [L,H]$，则

$$\alpha_2^{new}=\begin{cases} L & \text{if } \alpha_2^{new,unclipped}<L\\ \alpha_2^{new,unclipped} & \text{if } L\leq \alpha_2^{new,unclipped}\leq H\\ H & \text{if } \alpha_2^{new,unclipped}>H \end{cases}$$

就是考虑一个开口向上的二次函数的最值，用一个区间来截断。

启发式选取alpha

先思考一下$\alpha$的取到边界值的实际意义。

$$\alpha_i=0 \Rightarrow \beta_i=C\Rightarrow \zeta_i=0\Rightarrow y^{(i)}(w^Tx^{(i)}+b)\geq 1$$

也就是说此时第$i$个样本被正确分类。

$$\alpha_i=C \Rightarrow y^{(i)}(w^Tx^{(i)}+b)= 1-\zeta_i$$

可能在间隔里面，也可能被误分类。

$$0< \alpha_i< C\Rightarrow \beta_i\neq 0\Rightarrow \zeta_i=0\Rightarrow y^{(i)}(w^Tx^{(i)}+b)= 1$$

是间隔边界上的支持向量。

在整个算法中，实际上$\alpha$只满足$\sum_{i=1}^n\alpha_iy^{(i)}=0$的限制，并不一定满足KKT条件。

而KKT条件是取到最值的必要条件，整个的思路就是不断调整$\alpha$使其满足KKT条件。

最后SMO的停机条件是满足

$$0\leq \alpha_i\leq C\\ \sum_{i=1}^{n}\alpha_iy^{(i)}=0\\ \begin{cases} y^{(i)}(w^Tx^{(i)}+b)\geq 1& \text{if } \alpha_i=0\\ y^{(i)}(w^Tx^{(i)}+b)=1& \text{if } 0<\alpha_i<C\\ y^{(i)}(w^Tx^{(i)}+b)\leq 1& \text{if } \alpha_i=C \end{cases}$$

然后启发式选取$\alpha$的过程是这样的

首先要选取$\alpha_2$：

1. 遍历整个训练集，选择第一个违反KKT条件的为第一个变量并接着选择第二个变量，进行一次优化
2. 遍历整个训练集后，遍历$0<\alpha_i<C$的变量(non-bound)，选取第一个违反KKT条件的为第一个变量并接着选择第二个变量，进行一次优化；不断重复这一步，直到所有non-bound变量都被优化过
3. 不断重复1-2：遍历整个训练集优化一个变量，再多次优化non-bound变量
4. 当整个训练集的样本符合停机条件时停下

定义

$$d_i=w^Tx^{(i)}+b\\ E_i=d_i-y^{(i)}$$

工程上，判断变量是否符合KKT条件是用下面的条件，

$$\begin{cases} y^{(i)}(w^Tx^{(i)}+b)\geq 1-\epsilon& \text{if } \alpha_i=0\\ 1-\epsilon\leq y^{(i)}(w^Tx^{(i)}+b)\leq 1+\epsilon\ & \text{if } 0<\alpha_i<C\\ y^{(i)}(w^Tx^{(i)}+b)\leq 1 + \epsilon& \text{if } \alpha_i=C \end{cases}$$

直接合并起来，得到

$$(\alpha_i<C,y^{(i)}E_i\geq -\epsilon_i ) \ \text{and} \ (\alpha_i>0,y^{(i)}E_i\leq \epsilon_i )$$

相应地，判断是否违反KKT条件就是

$$(\alpha_i<C,y^{(i)}E_i< -\epsilon_i ) \ \text{or} \ (\alpha_i>0,y^{(i)}E_i> \epsilon_i )$$

不直接用上面推导的KKT条件是为了防止数值计算导致的误差。

原论文中有一个小技巧，在$\alpha_2$太小的情况（<1e-18）下直接设为0，离$C$差距很小的情况（<1e-18）下直接设为$C$。

在线更新b

按$\alpha$优化的过程实际上是在优化$w$，所以$b$也要相应地变化，这也是体现在KKT条件里的。