支持向量机SVM

1、前言

在之前我们介绍了线性回归算法以及其变种，LASSO回归、Ridge回归。他们是从减少过拟合的角度出发而得到的算法，而 SVM（支持向量机）则是优化原本线性回归算法中选择“分割线”，或者说选择分割超平面这样一个过程。

TAG：# 拉格朗日数乘子算法 # KKT条件

2、SVM的优点和缺点

• 优点：泛化错误率低，计算开销不大，结果易解释
• 缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二类问题。
• 数据类型：数值型和标称型数据。

3、SVM算法原理

首先我们都知道，为了划分二维的数据需要一根线，划分三维数据需要一个面。这里线是一维，面是二维，同理继续推出对 N 维的数据需要使用 N-1 维的对象进行分割，线性回归和 SVM 本质都是通过找这个超平面来达到分类的效果。

具体的来说SVM是在优化线性回归中的 $kx+b$ 模型。在线性回归中只需要考虑有一个分割超平面能进行分类即可，而SVM则想找出所有能分类的分割超平面中最优的超平面，即所有点都到分割超平面的距离最大，而支持向量指的就是离超平面最近的那些点。

超平面的公式为公式 2.1。所以点 A 到分割超平面的距离为公式 2.2。这里我们为了方便计算引入类别标签为-1和+1。所以保证所有的最小间隔的点最大化的公式为公式 2.3。

注1：-1和+1是为了保证预测正确的时候，$y(x_i) \times label_i$都是一个很大的正值。

注2：$arg\ max_{w,b}$的含义是，得到w和b使得后面式子取最大值

\[y(x) = w^TX+b\ \ \ 公式2.1\] \[\frac{|w^TX+b|}{||w||}\ \ \ 公式2.2\] \[arg\ max_{w,b}\{min_i(label_i*(w^Tx_i+b)*\frac{1}{||w||})\}\ \ \ 公式2.3\]

显然我们不能直接求解上面的式子。需要化简下它。首先由于公式2.1在正确预测时，同 $label$ 的乘积大于 1。所以我们可以拆分公式2.3为公式2.4和约束条件公式2.5。

注：这里的约束条件公式2.5中，要对每一个式子前都要加系数，即拉格朗日数乘子$\alpha_i$。

\[arg\ min_{w,b}\ ||w||\ \ \ 公式2.4\] \[st.\ \ label_i*(w^Tx_i+b) \geq 1 \ \ \ 公式2.5\]

对为了方便求导计算在公式 2.4 前加上$\frac{1}{2}$这个系数。之后使用拉格朗日乘子法得到公式2.6，并进行计算。根据KKT条件，让偏导数等于0得到公式2.7和公式2.8。

注：这里需要注意的是拉格朗日数乘子的正负号，这个同不等式的符号有关

\[L(w,b,\alpha)= \frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i*[label_i*(w^Tx_i+b)-1]\ \ \ 公式2.6\] \[\sum_{i=1}^{n}\alpha_i label_i x_i = w\ \ \ 公式2.7\] \[\sum_{i=1}^{n}\alpha_i label_i = 0\ \ \ 公式2.8\]

将公式2.7，公式2.8代入公式2.6化简，再根据对偶问题得到最终公式2.9，根据KKT，其约束条件为公式2.10。

注1：KKT条件在SMO算法中统一进行讲解。

注2：b是由公式2.8消掉的。

注3：在拉格朗日乘子法应用在这里，我们可以把$||w||$，写作$max_\alpha\ L(w,b,\alpha)$，所以原式可以写作$min_{w,b}\ max_\alpha\ L(w,b,\alpha)$，根据对偶问题，就可以变成$max_\alpha\ min_{w,b}\ L(w,b,\alpha)$，这也是能把公式2.7和公式2.8代入公式2.6的原因，也是公式2.9种是$max_\alpha$的原因。具体证明在KKT中的附上的博客中。

\[max_\alpha\ \sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i,j=1}^{m}label_i*label_j*a_i*a_j\langle x_i·x_j\rangle\ \ \ 公式2.9\] \[\alpha_i \geq 0\ \ 且\ \sum_{i=1}^{m}\alpha_i*label_i = 0\ \ \ 公式2.10\]

注：这里$\langle x_i·x_j\rangle$是两者向量积的运算，是从 $x_i^T*x_j$ 得到的。

这么看来我们算出了$\alpha$就能算出超平面，所以SVM的工作就是算出这些$\alpha$，而SMO算法就是求$\alpha$的典型算法。

4、对SVM引入线性不可分

由于数据都不那么干净，所以我们不应该假设数据能够100%的线性可分。我们通过对判定的公式，公式2.5，引入松弛变量$\xi_i\geq 0$，得到其引入了松弛因子的形式，如下公式3.1。

\[y_i(w*x_i+b)\geq1-\xi_i\ \ \ 公式3.1\]

同时对于目标函数公式2.4也需要调整，我们将$\xi$引入目标函数并对其设置权值，得到公式3.2，也因此其约束条件变为公式3.1，公式3.2。

\[min_{w,b}\frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i\ \ \ 公式3.2\] \[\begin{split} st.\ \ \ &y_i(w*x_i+b)\geq 1 - \xi_i\\ &\xi \geq 0 \end{split}\]

故拉格朗日函数$L(w,b,\xi,\alpha,\mu)$为如下公式3.3，其中$\alpha$，$\mu$为拉格朗日数乘子。

\[L(w,b,\xi,\alpha,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^n\alpha_i*[label_i*(w^Tx_i+b)-1+\xi_i]-\sum_{i=1}^n\mu_i\xi_i\ \ \ 公式3.3\]

和之前的操作一样，对其进行求偏导操作后，类似的得到了相同的公式2.7，公式2.8，不同的是这里对$\xi$的求到后对$\alpha$有了限制，得到了公式3.4，由于$\mu\geq0$所以有$\alpha_i$的取值范围$0 \leq \alpha_i \leq C$。 注：注意这里的$\alpha$取值，之后SMO会用

\[C-\alpha_i-\mu_i = 0\ \ \ 公式3.4\]

最终目标函数还是同之前推导的相同，即公式2.9。变化的只有，约束条件中$\alpha$的取值变为了$0 \leq \alpha_i \leq C$。这样有了目标函数了以后，之后可以根据梯度下降算法求得最终的$\alpha$

5、SMO（Sequential Minimal Optimization）

5.1、KKT条件

由于使用了拉格朗日数乘法，其中KKT条件便是SMO算法的精髓，所以我觉得有必要在这里提到KKT条件。 首先我们求$f(x)$ 极值的时候，需要讨论三种情况。

1. 没有约束条件：

2. 有一个等式$h(x)$的约束条件：

   使用拉格朗日乘子法（Lagrange Multiplier），也就是我们在高数中求极值常用的。设置一个拉格朗日系数$\alpha_1$，得到如下公式，之后对$x$和$\alpha_1$用求导的方式求极值即可。 \(L(x, \alpha) = f(x) + \alpha*h(x)\)

3. 含有不等式的约束条件：

   当约束条件中有不等式时，就需要用到KKT条件。同样地，把所有的不等式约束$g(x)\leq0$、等式约束$h(x)=0$和目标函数$f(x)$全部写为一个式子如下公式。

   \[L(x,\alpha_1, \alpha_2)= f(x) + \alpha_1*g(x)+\alpha_2*h(x)\]

   KKT条件是说最优值必须满足以下条件：

   1. $L(x, \alpha) = f(x) + \alpha(x)$ 对$x$，$\alpha_1$，$\alpha_2$求导为零。
   2. $h(x)=0$ 。
   3. $g(x)*\alpha_1=0$。

   其中第三个式子非常有趣，因为$g(x)\leq$ 0 ，如果要满足这个等式，必须有$a = 0$或者$g(x) = 0$。这是SVM的很多重要性质的来源。同时$f(x)$也可以写作$max_{\alpha_1,\alpha_2}\ L(x,\alpha_1,\alpha_2)$，这个则是SMO求解中的一个关键性质。详细的论述参考这篇博客。

5.2、SMO算法细节

SMO算法综述

由于原来直接通过梯度下降进行求解速度太慢，所以1996年，John Platt依靠KKT的特性，将大优化问题变成了多个小优化问题来求解，成为了SVM中最常用的求解思路。 其思路如下：

• Loop：
  1. 选取一对 $\alpha_i$，$\alpha_j$作为变量，其余看为常数
  2. 如果这对$\alpha$满足以下两个条件，使用梯度下降算法改变他们的值。
     • 两者都在间隔边界外
     • 两者都没有在进行过区间化处理，或者不在边界上
  3. 当满足了KKT条件，即$\sum_{i=1}^N\alpha_iy_i=0$和$0\leq \alpha_i \leq C$，退出循环。

注：这里可以这么理解，$\alpha_i$从之前的公式中我们可以大致理解为是每一个样本的权值，我们这些操作可以理解为通过操作$\alpha$把所有的样本点尽量的放在间隔边界上。

算法推导

我们接下来要做的是，通过类似梯度下降的方式来求的最优的$\alpha$值。正如上一节所说的，SMO的本质是大优化问题画小优化问题。所以从目标函数公式2.9中，随意取出两个$\alpha$，为了表达方便，不妨直接取$\alpha_1$和$\alpha_2$，同时对公式2.9前加负号取反之后，化简如下式4.1，其中$\kappa_{ij}$代表$\langle x_i·x_j\rangle$。

\[\begin{split} min_{\alpha_1, \alpha_2}W(\alpha_1,\alpha_2) &=\frac{1}{2}\kappa_{11}\alpha_1^2+\frac{1}{2}\kappa_{22}\alpha_2^2+y_1y_2\alpha_1\alpha_2\kappa_{12}-(\alpha_1+\alpha_2)\\ &+y_1\alpha_1\sum_{i=3}^Ny_i\alpha_i\kappa_{i1}+y_2\alpha_2\sum_{i=3}^Ny_i\alpha_i\kappa_{i2}\ \ \ 公式4.1\\ \end{split}\] \[\begin{split} st. \ \ &\alpha_1y_1+\alpha_2y_2=-\sum_{i=3}^Ny_i\alpha_i\\ &0\leq\alpha_i\leq C \end{split}\]

由于我们已经把不是$\alpha_1$和$\alpha_2$的参数看作常量，所以在进行求偏导进行梯度下降算法的时候就不需要考虑公式4.1中第二行的式子。通过这个式子中约束条件的等式就可以得到仅含$\alpha_j$的式子，对其进行梯度下降算法，得到如下公式4.2：

\[g(x)=\sum_{i=1}^Ny_i\alpha_i\kappa(x_i,x)+b\] \[\eta = \kappa_{11}+\kappa_{22}-2\kappa_{12} = ||x_1-x_2||^2\] \[E_i = g(x_i)-y_i = (\sum_{j=1}^Ny_j\alpha_j\kappa_{ji}+b)-y_i\] \[\alpha_i = \frac{\xi-\alpha_j y_j}{y_i}\] \[\alpha_j^{new}=\alpha_j^{old}+\frac{y_j(E_i-E_j)}{\eta}\ \ \ 公式4.2\]

这时候我们已经找到了两个的$\alpha$的新值了，不过我们不能确定这两个新值是否还满足KKT条件。所以我们根据KKT条件中$\alpha$的取值，设置了 L 和 H 来防止新值不满足 KKT，即$L\leq\alpha_i,\alpha_j \leq H$，其中L，H的公式如下公式4.3和公式4.4得到：

\[if\ y_i \neq y_j\ \ \ L=max(0,\alpha_j-\alpha_i),\ H=min(C,C+\alpha_j-\alpha_i)\] \[if\ y_i = y_j\ \ \ L=max(0,\alpha_j+\alpha_i-C),\ H=min(C,\alpha_j+\alpha_i)\]

注：L H的细节推导在这个博客中详细的说明了LH是怎么推出来的。

简单的来说就是之前提到的由线性不可分中得到的一个 $\alpha$ 的取值范围划定了一个正方形的框，之后公式 4.1 中第一个条件我们可以画一条直线，然后试图得到一个更精确的$alpha$范围，而这个 L 和 H 分别代表的是 High 和 Length（这点没有考证，是我个人的理解）。而为什么要讨论 $y_i$ 和 $y_j$ 是否同号，则是因为他们是否同号决定了画的直线的斜率。

至此，SMO算法的整体就讲完了，它最厉害的地方在于把一个很复杂的大的运算量很大的运算变成了一个一个小的优化问题，个人觉得这种以提升效率为目的，化大为小，带点贪心的算法的算法是非常优雅。

6、结语

这一章节中涉及的算法看似很复杂，但是实际的推导当你理解了拉格朗日数乘法和KKT条件以后，剩余的就是一些基本的求导操作，和一些减少运算的小技巧，如在判断 $\alpha$ 的变化方向的时候就不考虑公式 4.1 中第二行的式子等。建议大家都手推推，毕竟这个算法是目前面试中出现概率比较高的算法。到这里为止 SVM 算法还是作为一种二分类算法，当咱们的专栏进行到接近尾声的时候，我会给大家介绍几种把二分类变成多分类的集成算法思路。

最后，祝大家HappyCoding，接下来的国庆节玩的开心。