SVM

SVM（Support Vector Machines）又称为支持向量机，是一种二分类的模型，其主要思想为找到空间中的一个更够将所有数据样本划开的超平面 $W^{T}X+b=0$WTX+b=0，并且使得本本集中所有数据到这个超平面的距离最短。

1 线性SVM

在保证决策面方向不变且不会出现错分样本的情况下移动决策面，会在原来的决策面两侧找到两个极限位置（越过该位置就会产生错分现象），如虚线所示。虚线的位置由决策面的方向和距离原决策面最近的几个样本的位置决定。而这两条平行虚线正中间的分界线就是在保持当前决策面方向不变的前提下的最优决策面。两条虚线之间的垂直距离就是这个最优决策面对应的分类间隔。显然每一个可能把数据集正确分开的方向都有一个最优决策面（有些方向无论如何移动决策面的位置也不可能将两类样本完全分开），而不同方向的最优决策面的分类间隔通常是不同的，那个具有“最大间隔”的决策面就是SVM要寻找的最优解。而这个真正的最优解对应的两侧虚线所穿过的样本点，就是SVM中的支持样本点，称为支持向量。

2 分类间隔

由点到直线的距离求图中的$d$d:
$d = \frac{|w^T+b|}{||w||^2}$d=∣∣w∣∣2∣wT+b∣​
这个d就是”分类间隔”。其中||w||表示w的二范数，求所有元素的平方和，然后再开方。我们目的是为了找出一个分类效果好的超平面作为分类器。分类器的好坏的评定依据是分类间隔W=2d的大小，即分类间隔W越大，我们认为这个超平面的分类效果越好。此时，求解超平面的问题就变成了求解分类间隔W最大化的问题。W的最大化也就是d最大化的。

3 约束条件

为了求解w的最大值。我们不得不面对如下问题：

• 如何判断超平面是否将样本点正确分类？
• 知道相求距离d的最大值，首先需要找到支持向量上的点，怎么在众多的点中选出支持向量上的点呢？

如果我们的超平面方程能够完全正确地对上图的样本点进行分类，就会满足下面的方程：$w^Tx_i+b \ge 0 \qquad y_i =1$wTxi​+b≥0yi​=1 $w^Tx_i+b \le 0 \qquad y_i =-1$wTxi​+b≤0yi​=−1 假设决策面正好处于间隔区域的中轴线上，并且相应的支持向量对应的样本点到决策面的距离为d，那么公式进一步写成：$\frac{w^Tx_i+b}{||w||^2} \ge d \qquad y_i =1$∣∣w∣∣2wTxi​+b​≥dyi​=1 $\frac{w^Tx_i+b}{||w||^2} \le d \qquad y_i =-1$∣∣w∣∣2wTxi​+b​≤dyi​=−1对于所有分类标签为1的样本点，它们到直线的距离都大于等于d(支持向量上的样本点到超平面的距离)。对于所有分类标签为-1的样本点，它们到直线的距离都小于等于d。公式两边都除以d，就可以得到：$w_d^Tx_i+b_d \ge 1 \qquad y_i =1$wdT​xi​+bd​≥1yi​=1 $w_d^Tx_i+b_d \le 1 \qquad y_i =-1$wdT​xi​+bd​≤1yi​=−1 其中：$w_d = \frac{w}{||w||d}， b_d = \frac{b}{||w||d}$wd​=∣∣w∣∣dw​，bd​=∣∣w∣∣db​对于存在分类间隔的两类样本点，我们一定可以找到一些超平面面，使其对于所有的样本点均满足下面的条件：（$w_d$wd​ ,$y_d$yd​ 改为 $w$w ,$y$y ）对于任意 $x_i$xi​ 有: $y_i(w^Tx_i+b)\geq 1$yi​(wTxi​+b)≥1

4 线性SVM优化问题基本描述

我们的优化目标是是d最大化，并且是用支持向量上的样本点求解d的最大化的问题的，对于任意支持向量上的样本点：
$|w^Tx_i+b|=1$∣wTxi​+b∣=1 $d =\frac{1}{||w||}$d=∣∣w∣∣1​
求解d的最大化问题变成了||w||的最小化问题。进而||w||的最小化问题等效于:
$min\frac{1}{2}||w||^2$min21​∣∣w∣∣2 $y_i(w^Tx_i+b)\geq1,i = 1,2,..,n$yi​(wTxi​+b)≥1,i=1,2,..,n

5 求解线性可分SVM

5.1 凸集

如果集合中任意2个元素连线上的点也在集合中，那么这个集合就是凸集，凸函数：
$f(\alpha x_1 + (1-\alpha)x_2) \leq \alpha f(x_1)+(1-\alpha)f(x_2)$f(αx1​+(1−α)x2​)≤αf(x1​)+(1−α)f(x2​) 我们的目标函数是一个凸函数，（非凸函数，只能获得局部最优解）

5.2 优化问题

无约束优化问题：$minf(x)$minf(x)有等式约束的优化问题：$minf(x)$minf(x) $s.t. h_i(x) = 0,i=1,2,...,n$s.t.hi​(x)=0,i=1,2,...,n有不等式约束的优化问题：$minf(x)$minf(x) $s.t. g_i(x) \leq 0,i=1,2,...,n$s.t.gi​(x)≤0,i=1,2,...,n $h_j(x) = 0,j=1,2,...,m$hj​(x)=0,j=1,2,...,m第一类的优化问题，常常使用的方法是费马大定理(Fermat)，即求取函数f(x)的导数，令其为零，可以求得候选最优值，进行验证。
第二类的优化问题，常常使用的方法就是拉格朗日乘数法（Lagrange Multiplier) ，即把等式约束 $h_i(x)$hi​(x) 用一个系数与f(x)写为一个式子，称为拉格朗日函数 $F(x,\alpha) = f(x)+\alpha h(x)$F(x,α)=f(x)+αh(x)，而系数 $\alpha$α 称为拉格朗日乘子。通过拉格朗日函数对各个变量求导，令其为零，可以求得候选值集合，然后验证求得最优值。
第三类的优化问题，常常使用的方法就是KKT条件。同样地，把所有的等式、不等式约束与f(x)写为一个式子，也叫拉格朗日函数，系数也称拉格朗日乘子，通过一些条件，可以求出最优值的必要条件，这个条件称为KKT条件。

5.3 拉格朗日函数

拉格朗日方程的目的：将约束条件放到目标函数中，从而将有约束优化问题转换为无约束优化问题。我们要求解的是最小化问题，所以一个直观的想法是如果我能够构造一个函数，使得该函数在可行解区域内与原目标函数完全一致，而在可行解区域外的数值非常大，甚至是无穷大，那么这个没有约束条件的新目标函数的优化问题就与原来有约束条件的原始目标函数的优化问题是等价的问题。
KKT条件：
把所有的不等式约束、等式约束和目标函数全部写为一个式子 $L(x,u,v)= f(x) + u*g(x)+v*h(x)$L(x,u,v)=f(x)+u∗g(x)+v∗h(x)，KKT条件是说最优值必须满足以下条件：

1. $L(x,u,v)对x$L(x,u,v)对x求导为零
2. $h(x) =0$h(x)=0;
3. $u*g(x) = 0$u∗g(x)=0

推导：
证明：$min_xmax_uL(x,u) = max_umin_xL(x,u)$minx​maxu​L(x,u)=maxu​minx​L(x,u)
(1) 由于：$ag(x)\leq0$ag(x)≤0 有：
$max_uL(x,u)=f(x)$maxu​L(x,u)=f(x) $min_xf(x) = min_xmax_uL(x,u)$minx​f(x)=minx​maxu​L(x,u) (2) $max_umin_xL(x,u)=max_u[min_xf(x)+min_xug(x)]=max_umin_xf(x)+max_umin_xug(x) = min_xf(x)+max_umin_xug(x)$maxu​minx​L(x,u)=maxu​[minx​f(x)+minx​ug(x)]=maxu​minx​f(x)+maxu​minx​ug(x)=minx​f(x)+maxu​minx​ug(x) $ug(x) = \begin{cases} 0, & \text{if $u=0$ or $g(x)=0$ } \\ -k, & \text{if $u\ge0$ or $g(x)\le0$} \end{cases}$ug(x)={0,−k,​if u=0 or g(x)=0 if u≥0 or g(x)≤0​ $\therefore max_umin_xug(x) =0 \qquad and : u=0 \qquad or\qquad g(x)=0$∴maxu​minx​ug(x)=0and:u=0org(x)=0 $\therefore min_xmax_uL(x,u) = min_xf(x)+max_umin_xug(x) = min_xf(x)$∴minx​maxu​L(x,u)=minx​f(x)+maxu​minx​ug(x)=minx​f(x)
得证：$min_xmax_uL(x,u) = max_umin_xL(x,u)$minx​maxu​L(x,u)=maxu​minx​L(x,u)
我们将$max_umin_xL(x,u)$maxu​minx​L(x,u)称为原问题的对偶问题，并且当满足一定条件时原问题、对偶问题以及$minf(x)$minf(x)的解是相同的，且在最优解有：$u=0$u=0 or $g(x^*)=0$g(x∗)=0
$L(x,u)$L(x,u)在$x^*$x∗处的偏导为0 表明$f(x^*)$f(x∗)在极值点$x^*$x∗处的梯度是各个$h_i(x)$hi​(x)和梯度 $g_k(x)$gk​(x) 的线性组合
将有约束的原始目标函数转换为无约束的新构造的拉格朗日目标函数：
原始目标函数：
$min\frac{1}{2}||w||^2$min21​∣∣w∣∣2 $1- y_i(w^Tx_i+b)\leq0,i = 1,2,..,n$1−yi​(wTxi​+b)≤0,i=1,2,..,n
拉格朗日目标函数：
$L(w,b,\alpha) = \frac{1}{2}||w||^2- \sum_{i=1}^n \alpha_i(y_i(w^Tx_i+b)-1)$L(w,b,α)=21​∣∣w∣∣2−i=1∑n​αi​(yi​(wTxi​+b)−1)
其中 $α_i$αi​ 是拉格朗日乘子，$α_i$αi​ 大于等于0，是构造新目标函数时引入的系数变量。
求解：$max_\alpha min_{w,b}L(w,b,\alpha)$maxα​minw,b​L(w,b,α)
分别对 $w,b$w,b 求导=0，得到基于w和b的极小值：
$w = \sum_{i=1}^n \alpha_iy_ix_i$w=i=1∑n​αi​yi​xi​ $\sum_{i=1}^n \alpha_iy_i = 0$i=1∑n​αi​yi​=0
将其带入拉格朗日函数中：

$L(w,b,\alpha) = \sum_{i=1}^n α_i - \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^nα_iα_jy_iy_jx_i^Tx_j$L(w,b,α)=i=1∑n​αi​−21​i=1∑n​j=1∑n​αi​αj​yi​yj​xiT​xj​ $s.t. \sum_{i=1}^n α_iy_i = 0， i = 1,2,...,n$s.t.i=1∑n​αi​yi​=0，i=1,2,...,n

5.4 SMO算法

SMO表示序列最小化(Sequential Minimal Optimizaion) 工作原理是：每次循环中选择两个 $\alpha$α进行优化处理。一旦找到了一对合适的$\alpha$α，那么就增大其中一个同时减小另一个。这里所谓的”合适”就是指两个$\alpha$α必须符合以下两个条件，条件之一就是两个$\alpha$α必须要在间隔边界之外，而且第二个条件则是这两个$\alpha$α还没有进进行过区间化处理或者不在边界上。
SMO算法的解法:
将目标函数变形，在前面增加一个符号，将最大值问题转换成最小值问题:
$min_α \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^nα_iα_jy_iy_jx_i^Tx_j-\sum_{i=1}^n α_i$minα​21​i=1∑n​j=1∑n​αi​αj​yi​yj​xiT​xj​−i=1∑n​αi​ $s.t. \sum_{i=1}^n α_iy_i = 0， i = 1,2,...,n$s.t.i=1∑n​αi​yi​=0，i=1,2,...,n详细算法见第8章

5.5 线性可分SVM

求解$w$w

根据：$w = \sum_{i=1}^n \alpha_iy_ix_i$w=∑i=1n​αi​yi​xi​，求出对应的$w^*$w∗: $w^* = \sum_{i=1}^n \alpha^*_iy_ix_i$w∗=i=1∑n​αi∗​yi​xi​

支持向量求解

根据KKT条件中的对偶互补条件 $\alpha_i*(y_i(w^Tx_i+b) -1)=0$αi​∗(yi​(wTxi​+b)−1)=0 如果 $α_i>0$αi​>0 则有$y_i(w^Tx_i+b)=1$yi​(wTxi​+b)=1 即点在支持向量上，否则如果 $α_i=0$αi​=0 则有 $y_i(w^Tx_i+b)≥1$yi​(wTxi​+b)≥1，即样本在支持向量上或者已经被正确分类。

求解$b$b

对于任意支持向量$(x_s,y_s)$(xs​,ys​)，有： $y_s(w^Tx_s+b) =y_s( \sum_{i=1}^n \alpha_iy_ix_i^Tx_s+b)= 1$ys​(wTxs​+b)=ys​(i=1∑n​αi​yi​xiT​xs​+b)=1假设我们有$S$S个支持向量，则对应我们求出$S$S个$b^*$b∗,理论上这些 $b^*$b∗ 都可以作为最终的结果， 但是我们一般采用一种更健壮的办法，即求出所有支持向量所对应的$b^*$b∗，然后将其平均值作为最后的结果。注意到对于严格线性可分的SVM，b的值是有唯一解的，也就是这里求出的所有$b^*$b∗都是一样的
这样最终的分类超平面为：$w^∗∙x+b^∗=0$w∗∙x+b∗=0，最终的分类决策函数为：$f(x)=sign(w^∗∙x+b^∗)$f(x)=sign(w∗∙x+b∗)

6 求解线性不可分SVM

6.1 软间隔

实际上，对于上述目标函数，是存在一个假设的，即数据100%线性可分。但是，目前为止，我们知道几乎所有数据都不那么”干净”。这时我们就可以通过引入所谓的松弛变量(slack variable)（为了便于在更大的可行域内求解），来允许有些数据点可以处于超平面的错误的一侧，为此要引入“软间隔”(soft margin)的概念。前面介绍的支持向量机形式是要求所有样本都满足约束，即所有样本都必须划分正确，这称为“硬间隔”（hard margin），而软间隔则是允许某些样本不满足约束 $y_i(w^Tx_i+b)\geq1$yi​(wTxi​+b)≥1在最大化间隔的同时，不满足约束条件的样本应该尽可能少，新的约束条件为： $y_i(w^Tx_i+b)\geq1-\varepsilon_i$yi​(wTxi​+b)≥1−εi​同时，对于每一个松弛变量 $\varepsilon_i\geq 0$εi​≥0，支付一个代价$\varepsilon_i\geq 0$εi​≥0，目标函数变为：$min \frac{1}{2}||w||^2 + C\sum_{i=1}^n \varepsilon_i$min21​∣∣w∣∣2+Ci=1∑n​εi​ $s.t. y_i(w^Tx_i+b)\geq1-\varepsilon_i$s.t.yi​(wTxi​+b)≥1−εi​ $\varepsilon_i \geq 0$εi​≥0这里,$C>0$C>0为惩罚参数，可以理解为我们一般回归和分类问题正则化时候的参数。C越大，对误分类的惩罚越大，C越小，对误分类的惩罚越小。也就是说，我们希望 $\frac{1}{2}||w||^2$21​∣∣w∣∣2 尽量小，误分类的点尽可能的少。C是协调两者关系的正则化惩罚系数。在实际应用中，需要调参来选择。

6.2 线性分类SVM的软间隔最大化目标函数的优化

将软间隔最大化的约束问题用拉格朗日函数转化为无约束问题如下：
$L(w,b,\varepsilon,\alpha,u) = \frac{1}{2}||w||^2+C\sum_{i=1}^n\varepsilon_i - \sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1+\varepsilon_i]-\sum_{i=1}^nu_i\varepsilon_i$L(w,b,ε,α,u)=21​∣∣w∣∣2+Ci=1∑n​εi​−i=1∑n​αi​[yi​(wTxi​+b)−1+εi​]−i=1∑n​ui​εi​要优化的目标函数为：$min_{w,b,\varepsilon}max_{\alpha_i,u_i}L(w,b,\varepsilon,\alpha,u)$minw,b,ε​maxαi​,ui​​L(w,b,ε,α,u)　这个优化目标也满足KKT条件，也就是说，可以通过拉格朗日对偶将我们的优化问题转化为等价的对偶问题来求解如下：$max_{\alpha_i,u_i}min_{w,b,\varepsilon}L(w,b,\varepsilon,\alpha,u)$maxαi​,ui​​minw,b,ε​L(w,b,ε,α,u)分别对 $w,b,\varepsilon$w,b,ε 求导=0，得到基于$w,b,\varepsilon$w,b,ε的极小值：$w = \sum_{i=1}^n \alpha_iy_ix_i$w=i=1∑n​αi​yi​xi​ $\sum_{i=1}^n \alpha_iy_i = 0$i=1∑n​αi​yi​=0 $C-\alpha_i-u_i= 0$C−αi​−ui​=0带入目标优化函数中：$L(w,b,\varepsilon,\alpha,u) = \sum_{i=1}^n α_i - \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^nα_iα_jy_iy_jx_i^Tx_j$L(w,b,ε,α,u)=i=1∑n​αi​−21​i=1∑n​j=1∑n​αi​αj​yi​yj​xiT​xj​优化目标变为：$min_α \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^nα_iα_jy_iy_jx_i^Tx_j-\sum_{i=1}^n α_i$minα​21​i=1∑n​j=1∑n​αi​αj​yi​yj​xiT​xj​−i=1∑n​αi​ $s.t. \sum_{i=1}^n α_iy_i = 0， i = 1,2,...,n$s.t.i=1∑n​αi​yi​=0，i=1,2,...,n $0 \leq α_i \leq C$0≤αi​≤C

6.3 软间隔最大化时的支持向量

因为我们对每个样本$(x_i,y_i)$(xi​,yi​)引入了松弛变量$\varepsilon_i$εi​。我们从下图来研究软间隔最大化时支持向量的情况，第 $i$i 个点到对应类别支持向量的距离为 $\frac{\varepsilon_i}{||w||^2}$∣∣w∣∣2εi​​。根据软间隔最大化时KKT条件中的对偶互补条件:$α^∗_i(y_i(w^Tx_i+b)−1+\varepsilon^∗_i)=0$αi∗​(yi​(wTxi​+b)−1+εi∗​)=0a) 如果$α=0$α=0,那么$y_i(w^Tx_i+b)−1≥0$yi​(wTxi​+b)−1≥0,即样本在间隔边界上或者已经被正确分类。如图中所有远离间隔边界的点。
b) 如果$0&lt;α&lt;C$0<α<C,那么$\varepsilon_i=0,y_i(w^Tx_i+b)−1=0$εi​=0,yi​(wTxi​+b)−1=0,即点在间隔边界上。
c) 如果$α=C$α=C，说明这是一个可能比较异常的点，需要检查此时$\varepsilon_i$εi​:

• 如果 $0≤\varepsilon_i≤1$0≤εi​≤1,那么点被正确分类，但是却在超平面和自己类别的间隔边界之间。如图中的样本2和4.
• 如果 $\varepsilon_i=1$εi​=1,那么点在分离超平面上，无法被正确分类。
• 如果 $\varepsilon_i&gt;1$εi​>1,那么点在超平面的另一侧，也就是说，这个点不能被正常分类。如图中的样本1和3.
  

7 求解非线性SVM

线性不可分的低维特征数据，可以将其映射到高维，就能线性可分。SVM的优化目标函数变成：$min_α \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^nα_iα_jy_iy_j\phi(x_i)\phi (x_j)-\sum_{i=1}^n α_i$minα​21​i=1∑n​j=1∑n​αi​αj​yi​yj​ϕ(xi​)ϕ(xj​)−i=1∑n​αi​ $s.t. \sum_{i=1}^n α_iy_i = 0， i = 1,2,...,n$s.t.i=1∑n​αi​yi​=0，i=1,2,...,n $0 \leq α_i \leq C$0≤αi​≤C和线性可分SVM的优化目标函数的区别仅仅是将内积 $x_i∙x_j$xi​∙xj​ 替换为 $ϕ(x_i)∙ϕ(x_j)$ϕ(xi​)∙ϕ(xj​) 。
核函数：
核函数的价值在于它是将特征进行从低维到高维的转换，但核函数是在低维上进行计算，并将实质上的分类效果（利用了内积）表现在了高维上，这样避免了直接在高维空间中的复杂计算，真正解决了SVM不可分的问题。
假设$ϕ$ϕ是一个从低维的输入空间$χ$χ（欧式空间的子集或者离散集合）到高维的希尔伯特空间的$H$H映射。那么如果存在函数$K(x,z)$K(x,z)，对于任意$x,z∈χ$x,z∈χ，都有：$K(x,z)=ϕ(x)∙ϕ(z)$K(x,z)=ϕ(x)∙ϕ(z)那么我们就称$K(x,z)$K(x,z)为核函数
正定核函数：一个函数要想成为正定核函数，必须满足其里面任何点的集合形成的Gram矩阵（内积形成的矩阵）是半正定的。也就是说,对于任意的$x_i∈χ，i=1,2,3...m, K(x_i,x_j)$xi​∈χ，i=1,2,3...m,K(xi​,xj​)对应的Gram矩阵$K=[K(x_i,x_j)]$K=[K(xi​,xj​)] 是半正定矩阵，则$K(x,z)$K(x,z)是正定核函数
常见核函数：

8 SMO算法原理

上述对偶形式的KKT条件：
$\begin{cases} w = \sum_{i=1}^n \alpha_iy_ix_i , \quad \sum_{i=1}^n \alpha_iy_i = 0, \quad C-\alpha_i-u_i= 0 , \text{（目标函数求导后为0）}\\ α_i(y_if(x_i)-1+\varepsilon_i )=0\\ u_i\varepsilon_i =0\\ \end{cases}$⎩⎪⎨⎪⎧​w=∑i=1n​αi​yi​xi​,∑i=1n​αi​yi​=0,C−αi​−ui​=0,（目标函数求导后为0）αi​(yi​f(xi​)−1+εi​)=0ui​εi​=0​ 除此之外还有：$\begin{cases} α_i \geq 0 \\ u_i \geq 0\\ y_if(x_i)-1+\varepsilon_i \geq 0\\ \varepsilon_i \geq 0 \\ \end{cases}$⎩⎪⎪⎪⎨⎪⎪⎪⎧​αi​≥0ui​≥0yi​f(xi​)−1+εi​≥0εi​≥0​于是，对于任意训练样本，总有$α_i=0$αi​=0 或者 $y_if(x_i)=1-\varepsilon_i$yi​f(xi​)=1−εi​.
（1）$α_i=0$αi​=0，则该样本不会对$f(x)$f(x) 有任何影响
（2）$α_i&gt;0$αi​>0 ，则必有 $y_if(x_i)=1-\varepsilon_i$yi​f(xi​)=1−εi​，即该样本是支持向量。

• 若 $α_i&lt;C$αi​<C，则 $μ_i&gt;0$μi​>0，进而有$\varepsilon_i=0$εi​=0，所以此时有：$y_if(x_i)=1$yi​f(xi​)=1,即该样本恰好在最大间隔边界上；
• 若 $α_i=C$αi​=C，则 $μ_i=0$μi​=0，此时若 $\varepsilon_i\leq1$εi​≤1 则该样本落在最大间隔内部；若 $\varepsilon_i&gt;1$εi​>1 则该样本被错误分类。

8.1 SMO目标函数求解

优化上述式子比较复杂，里面有n个变量组成的向量 α 需要在目标函数极小化的时候求出。直接优化时很难的。SMO算法则采用了一种启发式的方法。它每次只优化两个变量，将其他的变量都视为常数。由于 $\sum_{i=1}^n \alpha_iy_i = 0$∑i=1n​αi​yi​=0 .假如将 $α_3,α_4,...,α_m$α3​,α4​,...,αm​　固定，那么 $α_1,α_2$α1​,α2​ 之间的关系也确定了。这样SMO算法将一个复杂的优化算法转化为一个比较简单的两变量优化问题。定义 $K_{ij}=ϕ(x_i)∙ϕ(x_j)$Kij​=ϕ(xi​)∙ϕ(xj​) 目标优化函数变成下式：$min_{α_1,α_2}\frac{1}{2}K_{11}α_1^2 + \frac{1}{2}K_{22}α_2^2 + y_1y_2K_{12}α_1α_2 - (α_1+α_2) + y_1α_1\sum_{i=3}^ny_iα_iK_{i1} + y_2α_2\sum_{i=3}^ny_iα_iK_{i2}$minα1​,α2​​21​K11​α12​+21​K22​α22​+y1​y2​K12​α1​α2​−(α1​+α2​)+y1​α1​i=3∑n​yi​αi​Ki1​+y2​α2​i=3∑n​yi​αi​Ki2​ $s.t. α_1y_1 +α_2y_2 = -\sum_{i=3}^n \alpha_iy_i =m$s.t.α1​y1​+α2​y2​=−i=3∑n​αi​yi​=m有： $α_1 = (m- α_2y_2)/y_1$α1​=(m−α2​y2​)/y1​将优化目标中所有的 $α_1$α1​ 都替换为用 $α_2$α2​ 表示的形式，优化形式变为：$min \phi(α_2) = \frac{1}{2}K_{11}(m- α_2y_2)^2 + \frac{1}{2}K_{22}α_2^2 + α_2y_2K_{12} (m- α_2y_2) - ((m- α_2y_2)/y_1+α_2) + (m- α_2y_2)\sum_{i=3}^ny_iα_iK_{i1} + y_2α_2\sum_{i=3}^ny_iα_iK_{i2}$minϕ(α2​)=21​K11​(m−α2​y2​)2+21​K22​α22​+α2​y2​K12​(m−α2​y2​)−((m−α2​y2​)/y1​+α2​)+(m−α2​y2​)i=3∑n​yi​αi​Ki1​+y2​α2​i=3∑n​yi​αi​Ki2​此时，优化目标中仅含有 $α_2$α2​ 一个待优化变量了，我们现在将待优化函数对 $α_2$α2​ 求偏导得到如下结果：$\frac{\partial \phi(α_2)}{\partialα_2} =(K_{11}+K_{22}-2K_{12})α_2-K_{11}my_2+K_{12}my_2+ y_2y_1-1 - y_2\sum_{i=3}^ny_iα_iK_{i1} + y_2\sum_{i=3}^ny_iα_iK_{i2}$∂α2​∂ϕ(α2​)​=(K11​+K22​−2K12​)α2​−K11​my2​+K12​my2​+y2​y1​−1−y2​i=3∑n​yi​αi​Ki1​+y2​i=3∑n​yi​αi​Ki2​为了简化叙述，我们令$E_i=g(x_i)−y_i=∑_{j=1}^nα_jy_jK(x_i,x_j)+b−y_i$Ei​=g(xi​)−yi​=j=1∑n​αj​yj​K(xi​,xj​)+b−yi​ 令：$v_i=\sum_{i=3}^ny_iα_iK(x_i,x_j)= g(x_i)−\sum_{j=1}^2y_jα_jK(x_i,x_j)-b$vi​=i=3∑n​yi​αi​K(xi​,xj​)=g(xi​)−j=1∑2​yj​αj​K(xi​,xj​)−b带入我们求偏导的结果中有：$\frac{\partial \phi(α_2)}{\partialα_2} =(K_{11}+K_{22}-2K_{12})α_2-K_{11}my_2+K_{12}my_2+ y_2y_1-1 - y_2v_1 + y_2v_2 = 0$∂α2​∂ϕ(α2​)​=(K11​+K22​−2K12​)α2​−K11​my2​+K12​my2​+y2​y1​−1−y2​v1​+y2​v2​=0整理上式有：$(K_{11}+K_{22}-2K_{12})α_2 = y_2(K_{11}m-K_{12}m+ y_2-y_1 + v_1 - v_2 )$(K11​+K22​−2K12​)α2​=y2​(K11​m−K12​m+y2​−y1​+v1​−v2​)将 $α_1y_1 +α_2y_2 =m$α1​y1​+α2​y2​=m 及 $v_i$vi​ 代入上式有（采用启发式的迭代法，假设我们上一轮迭代得到的解是 $α^{old}_1,α^{old}_2$α1old​,α2old​。本轮迭代完成后的解为 $α^{new}_1,α^{new}_2$α1new​,α2new​）：$(K_{11}+K_{22}-2K_{12})α_2^{new} =(K_{11}+K_{22}-2K_{12})α_2^{old} + y_2(E_1 - E_2 )$(K11​+K22​−2K12​)α2new​=(K11​+K22​−2K12​)α2old​+y2​(E1​−E2​) 得到 $α_2^{new}$α2new​ 的表达式：$α_2^{new} = α_2^{old}+\frac{y_2(E_1 - E_2 )}{K_{11}+K_{22}-2K_{12}}$α2new​=α2old​+K11​+K22​−2K12​y2​(E1​−E2​)​

8.2 SMO算法目标函数优化

根据上面的约束条件 $α_1y_1+α_2y_2=m$α1​y1​+α2​y2​=m , $0≤α_i≤C$0≤αi​≤C ，又由于 $y_1,y_2$y1​,y2​均只能取值1或者-1, 这样 $α_1,α_2$α1​,α2​在[0,C]和[0,C]形成的盒子里面，并且两者的关系直线的斜率只能为1或者-1，也就是说$α_1,α_2$α1​,α2​ 的关系直线平行于[0,C]和[0,C]形成的盒子的对角线，如下图所示：

由于 $α_1,α_2$α1​,α2​ 的关系被限制在盒子里的一条线段上，所以两变量的优化问题实际上仅仅是一个变量的优化问题。不妨我们假设最终是 $α_2$α2​ 的优化问题。由于我们
　　由于 $α^{new}_2$α2new​ 必须满足上图中的线段约束。假设 L 和 H 分别是上图中 $α^{new}_2$α2new​ 所在的线段的边界。那么很显然我们有：$L≤α^{new}_2≤H$L≤α2new​≤H而对于L和H，我们也有限制条件如果是上面左图中的情况，则 $L=max(0,α^{old}_2−α^{old}_1) \quad H=min(C,C+α^{old}_2−α^{old}_1)$L=max(0,α2old​−α1old​)H=min(C,C+α2old​−α1old​)如果是上面右图中的情况，我们有：$L=max(0,α^{old}_2+α^{old}_1−C)\quad H=min(C,α^{old}_2+α^{old}_1)$L=max(0,α2old​+α1old​−C)H=min(C,α2old​+α1old​)以上，可以总结出 $α_2$α2​ 的取值范围：$\begin{cases} α_2 = H，α^{new}_2 \geq H \\ α_2 = L，α^{new}_2 \leq L \\ α_2 = α^{new}_2，L \le α^{new}_2 \le H \end{cases}$⎩⎪⎨⎪⎧​α2​=H，α2new​≥Hα2​=L，α2new​≤Lα2​=α2new​，L≤α2new​≤H​

8.3 SMO算法误差计算

变量选择：
SMO算法称选择第二变量为内层循环，假设我们在外层循环已经找到了 $α_1$α1​, 第二个变量 $α_2$α2​的选择标准是让$|E_1−E_2|$∣E1​−E2​∣有足够大的变化。由于α1定了的时候,E1也确定了，所以要想$|E_1−E_2|$∣E1​−E2​∣最大，只需要在E1为正时，选择最小的Ei作为E2， 在E1为负时，选择最大的Ei作为E2，可以将所有的Ei保存下来加快迭代。如果内存循环找到的点不能让目标函数有足够的下降， 可以采用遍历支持向量点来做α2,直到目标函数有足够的下降， 如果所有的支持向量做α2都不能让目标函数有足够的下降，可以跳出循环，重新选择α1　
计算阈值b：
在每次完成两个变量的优化之后，需要重新计算阈值b。
当 $0&lt;α^{new}_1&lt;C$0<α1new​<C 时，我们有$y_1−∑_{i=1}^mα_iy_iK_{i1}−b_1=0$y1​−i=1∑m​αi​yi​Ki1​−b1​=0于是新的 $b^{new}_1$b1new​ 为:$b^{new}_1=y_1−∑_{i=3}^mα_iy_iK_{i1}−α^{new}_1y_1K_{11}−α^{new}_2y_2K_{21}$b1new​=y1​−i=3∑m​αi​yi​Ki1​−α1new​y1​K11​−α2new​y2​K21​计算出 $E_1$E1​ 为：$E_1=g(x_1)−y_1=∑_{i=3}^mα_iy_iK_{i1}+α^{old}_1y_1K_{11}+α^{old}_2y_2K_{21}+b^{old}−y_1$E1​=g(x1​)−y1​=i=3∑m​αi​yi​Ki1​+α1old​y1​K11​+α2old​y2​K21​+bold−y1​可以看到上两式都有 $y_1−∑_{i=3}^mα_iy_iK_{i1}$y1​−∑i=3m​αi​yi​Ki1​，因此可以将 $b^{new}_1$b1new​ 用 $E_1$E1​表示为：$b^{new}_1=-E_1-y_1K_{11}(α^{new}_1-α^{old}_1)−y_2K_{21}(α^{new}_2-α^{old}_2) +b^{old}$b1new​=−E1​−y1​K11​(α1new​−α1old​)−y2​K21​(α2new​−α2old​)+bold
同样的，如果 $0&lt;α^{new}_2&lt;C$0<α2new​<C, 那么有：$b^{new}_2=-E_2-y_1K_{12}(α^{new}_1-α^{old}_1)−y_2K_{22}(α^{new}_2-α^{old}_2) +b^{old}$b2new​=−E2​−y1​K12​(α1new​−α1old​)−y2​K22​(α2new​−α2old​)+bold最终的 $b^{new}$bnew为：$bnew=\frac{b^{new}_1+b^{new}_2}{2}$bnew=2b1new​+b2new​​得到了 $b^{new}$bnew 我们需要更新 $E_i$Ei​:$E_i=∑_Sy_jα_jK(x_i,x_j)+b^{new}−y_i$Ei​=S∑​yj​αj​K(xi​,xj​)+bnew−yi​其中，$S$S 是所有支持向量 $x-j$x−j 的集合。