SVM-SMO

SMO是SVM寻找最优解的一种效果很好的方法，它先候场等待，紧接SVM最后的问题：

$min(\frac{1}{2}w^2+C∑ t_i )$ 约束条件： $y_i(wx_i+b)≥1-t_i、t_i≥0$

第一步：转化问题函数

通过KKT将约束条件转化为等式函数可得：

$min(L)=\frac{1}{2} w^2+C∑t_i-∑\alpha_i(y_i(wx_i+b)-1+t_i) -∑ u_it_i$

函数看起来比较高大上，我们整理下思路：

①参数较多，最小值需我们逐个求偏导为0，再代入该函数进行简化

②避免使用特征向量w求解问题（特定样本下，1000维数据中需要确定1000个值），通过系数αi求解问题（只和样本数量有关）

对参数求偏导并使其为0：w、b、ui、ti

① $\frac{dL}{dw} =w-∑α_iy_ix_i=0\Rightarrow w=∑α_iy_ix_i$

② $\frac{dL}{db} = -∑α_iy_i=0$

③ $\frac{dL}{du}= -∑t_i=0$

④ $\frac{dL}{dt} =∑C-∑α_i-∑u_i=0\Rightarrow u_i=C-α_i$

将①-④代入原式：

$min(L)=\frac{1}{2} ∑α_iy_ix_i∑α_iy_ix_i+C\times 0-∑[(∑α_iy_ix_i)α_iy_ix_i+a_iy_ib-α_i+α_it_i]-∑(C-α_i)t_i$

$=\frac{1}{2} ∑α_iα_jx_ix_jy_iy_i-∑α_iα_jx_ix_jy_iy_i-b∑α_iy_i+∑α_i-∑α_it_i-C×0+∑α_it_i$

$=∑α_i-\frac{1}{2} ∑α_iα_jx_ix_jy_iy_j$

根据KKT可得约束条件：

①u消除条件： $α_i+u_i=C$

②b消除条件： $∑a_iy_i=0$

③w消除条件： $w=∑α_iy_ix_i$

④KKT不等式无约束或梯度相反条件： $α_i≥0、u_i≥0$

⑤KKT原不等式约束条件： $y_i(wx_i+b)≥1-t_i、t_i≥0$

⑥KKT不等式无约束或最优解位于不等式边界： $α_i(y_i(wx_i+b)-1+t_i)=0、u_it_i=0$

小插曲：

①根据KKT理论可知 $α_i=0$ 代表该样本未受条件约束: $y_i(wx_i+b)≥1-t_i$ ，其意为该样本在支持向量外侧；此时 $t_i=0$ ，则正常样本不会贡献误差

②同理 $0<α_i<C$ 代表样本受 $y_i(wx_i+b)≥1-t_i$ 约束，此时 $u_i≠0$ 则 $t_i=0$ ，由⑥的一式得 $y_i(wx_i+b)=1$ ，其意为该样本刚好处于支持向量上，此时 $t_i$ 将通过⑥式中 $y_i(wx_i+b)-1+t_i=0$ 得解

③ $α_i=C$ 时同上，此时 $0<t_i<1$ 则落在支持向量与超平面内， $t_i≥1$ 则落在超平面或另一侧，相当于分类错误； $t_i=0$ 落在支持向量上

④松弛变量巧妙地利用KKT特性在L函数中加入 $C∑t_i$ ，而该误差又只作用于离群点

回到原函数，可视为w与α的函数: $min(L)=正数×w^2-正数×α$

为使L有最小值，则|w|越小越好、α越大越好。我们现在已经将问题转化为关于α的函数，那么剩下的就是求 $min(L)=max(∑α_i-\frac{1}{2} ∑α_iα_jx_ix_jy_iy_j)$

由于KKT是建立在求最小值基础上，因此我们把上述函数加个负号改成相反的问题，趁机加入核函数并结合KKT条件得出转化后的问题：

$min(L)=\frac{1}{2} ∑α_iα_jy_iy_jK(x_i,x_j)-∑α_i$ 并约束于：

$0≤α_i≤C、∑ α_iy_i=0、w=∑α_iy_ix_i、y_i(wx_i+b)-1+t_i≥0、$

$α_i(y_i(wx_i+b)-1+t_i)=0、t_i≥0、u_it_i=0$

注：引入核函数虽然对样本特征升维了，但特征向量w无需升维，是因为我们将问题转化为min(α)，借助核函数求得α最小值后，由于升维前后特征是等效的，我们在利用最小的α求得原特征向量即可

第二步：寻找α最小值

公式场面看起来有些失控，我们现在的目标是使α获得最小值以致L函数具有最小值

突破口在 $∑ α_iy_i=0$ ，我们先拿出两个α：α1、α2，固定其他α。则问题相当于是求2个α的最小值（其他则视为常数）→更新这2个α→选择下两项α：

$α_1y_1+α_2y_2=α_{1-old}y_1+α_{2-old}y_2=0-\sum_{i≥3}a_iy_i=A$

运算牢记 $y_i^2=1$ ，将两个α代入问题函数min(L)中可得：

$min(L)=\frac{1}{2} ∑α_iα_jy_iy_jK(x_i,x_j)-∑α_i$

$=\frac{1}{2} \sum_{i=1,2}(\sum_{j=1,2}α_iα_jy_iy_jK(x_i,x_j)+\sum_{j≥3}α_iα_jy_iy_jK(x_i,x_j))+\frac{1}{2} \sum_{i≥3}(\sum_{j=1,2}α_iα_jy_iy_jK(x_i,x_j)+\sum_{j≥3}α_iα_jy_iy_jK(x_i,x_j))-(α_1+α_2+\sum_{i≥3}α_i)$

$令O=α_iα_jy_iy_jK(x_i,x_j)：\frac{1}{2} \sum_{i=1,2}\sum_{j=1,2}O+\frac{1}{2}\sum_{i=1,2}\sum_{j=≥3}O+\frac{1}{2} \sum_{i≥3}\sum_{j=1,2}O+\frac{1}{2} \sum_{i≥3}\sum_{j≥3}O-(α_1+α_2+\sum_{i≥3}α_i)$

上式看起来又快失控了，由于目标是通过对α求导来寻找最小值，因此常数项 $\sum_{i≥3}\sum_{j≥3}O、\sum_{i≥3}α_i$ 可以直接被干掉（其导数值为0）

由于式子太长，简记 $K_{ij}=K(x_i,x_j)$ ，原L函数等效于l函数，继续化简： $min(l)=\frac{1}{2} \sum_{i=1,2}\sum_{j=1,2}O+\frac{1}{2}\sum_{i=1,2}\sum_{j=≥3}O+\frac{1}{2} \sum_{i≥3}\sum_{j=1,2}O-(α_1+α_2)$

$=\frac{1}{2} \sum_{i=1,2}\sum_{j=1,2}O+\sum_{i=1,2}\sum_{j=≥3}O-(α_1+α_2)$

$=\frac{1}{2} (α_1α_1y_1y_1K_{11}+α_1α_2y_1y_2K_{12}+α_2α_1y_2y_1K_{12}+α_2α_2y_2y_2K_{22})+α_1y_1\sum_{i≥3}α_1y_1K_{2i}+α_2y_2\sum_{i≥3}α_1y_1K_{2i}-α_1-α_2$

$=\frac{1}{2} K_{11}α_1^2+\frac{1}{2} K_{22}α_2^2+K_{12}α_1α_2y_1y_2+α_1y_1\sum_{i≥3}α_1y_1K_{1i}+α_2y_2\sum_{i≥3}α_iy_iK_{2i}-α_1-α_2$

令 $B_m=\sum_{i≥3}α_iy_iK_{mi}$ ，同时 $α_1=(A-α_2y_2)y_1$ ，代入上式可消掉α1。并对α2求导 $\frac{dL}{dα_2} =\frac{dl}{dα_2}=(K_{11}+K_{22}-2K_{12})α_2-AK_{11}y_2+AK_{12}y_2+y_1y_2-1-B_1y_2+B_2y_2=0$

导数等于0时α2获得最小值，还需要简化B1、B2计算量：迭代时它每次都会计算除这2个样本以外所有样本的数据，其实可以只计算这2样本值：

$f(x_m)=wx+b=\sum_{i=1,2}a_iy_iK_{mi}+\sum_{i=≥3}a_iy_iK_{mi}+b\Rightarrow B_m=\sum_{i=≥3}a_iy_iK_{mi}=f(x_m)-\sum_{i=1,2}a_iy_iK_{mi}-b$

重点来了！这里的α1、α2还未更新，而上文求导式中的α2是将要求解的值。因此将Bm代入导式便建立了新老参数替代的关系，下文将以αm表示待更新参数、αm-old表示老参数，代入得：

$(K_{11}+K_{22}-2K_{12})α_2=AK_{11}y_2-AK_{12}y_2-y_1y_2+1+B_1y_2-B_2y_2$

对于右侧函数，我们从右到左逐渐瓦解它，定义：

$左式：AK_{11}y_2-AK_{12}y_2$

$中式：-y_1y_2+1$

$右式：B_1y_2-B_2y_2$

$=y_2f(x_1)-K_{11}α_{1-old}y_1y_2-K_{12}α_{2-old}-by_2-y_2f(x_2)+K_{12}α_{1-old}y_1y_2+K_{22}α_{2-old}+by_2$

$=y_2f(x_1)-K_{11}α_{1-old}y_1y_2-K_{12}α_{2-old}-y_2f(x_2)+K_{12}α_{1-old}y_1y_2+K_{22}α_{2-old}$

右式与中式相加得

$=y_2f(x_1)-K_{11}α_{1-old}y_1y_2-K_{12}α_{2-old}-y_2f(x_2)+K_{12}α_{1-old}y_1y_2+K_{22}α_{2-old}+1-y_1y_2$

$=y_2[(f(x_1)-y_1)-(f(x_2)-y_2)]-α_{1-old}y_1y_2(K_{11}-K_{12})+α_{2-old}(K_{22}-K_{12})$ f(x)-y可理解为某样本真实与预测的误差，定义为E，则上式等效于

$=y_2(E_1-E_2)-α_{1-old}y_1y_2(K_{11}-K_{12})+α_{2-old}(K_{22}-K_{12})$

我们用老参数消掉A： $α_{1-old}y_1+α_{2-old}y_2=0-\sum_{i≥3}a_iy_i=A$ ，代入得：

$AK_{11}y_2-AK_{12}y_2=K_{11}y_2α_{1-old}y_1+K_{11}y_2α_{2-old}y_2-K_{12}y_2α_{1-old}y_1-K_{12}y_2α_{2-old}y_2$

$=α_{1-old}y_1y_2(K_{11}-K_{12})+α_{2-old}(K_{11}-K_{12})...②$

我们把左中右式加起来，即上述①、②：

$y_2(E_1-E_2)-α_{1-old}y_1y_2(K_{11}-K_{12})+α_{2-old}(K_{22}-K_{12}) +α_{1-old}y_1y_2(K_{11}-K_{12})+α_{2-old}(K_{11}-K_{12})$ $=y_2(E_1-E_2)+α_{2-old}(K_{11}+K_{22}-2K_{12})$

至此，我们便获得了α2的更新函数：

$(K_{11}+K_{22}-2K_{12})α_2=(K_{11}+K_{22}-2K_{12})α_{2-old}+y_2(E_1-E_2)$

$α_2=α_{2-old}+\frac{y_2(E_1-E_2)}{K_{11}+K_{22}-2K_{12}}$

第三步：寻找α定义域

第一种情况： $K_{11}+K_{22}-2K_{12}>0$

相当于原函数是开口向上的二次函数，最小值可能在边界上，也有可能在定义域之间，需进一步分析

最小值可能落在区间内，也可能没有

求出α更新函数后，α还要考虑约束条件 $0≤α≤C、α_1y_1+α_2y_2=A$ ，设上限为H、下限为L，可得：

① $y_1=y_2\Rightarrow a_1+a_2=Ay_1$

易知 $α_1+α_2≥0，α_1=0使α_2有最大值、α_1=C使α_2有最小值$

$A>0、y_1=1\Rightarrow H=min(A,C)、L=max(0,A-C)$

$A>0、y_1=-1\Rightarrow 最小值、最大值α_2需越下界：α_2=0$

$A<0、y_1=-1\Rightarrow H=min(-A,C)、L=max(0,-A-C)$

$A<0、y_1=1\Rightarrow 最小值、最大值α_2需越下界：α_2=0$

$A=0\Rightarrow α_2=0时满足条件$

$又α_1+α _2=±A，综上可得H=min(α_{1-old}+α _{2-old},C)、L=min(0,α_{1-old}+α _{2-old}-C)$

② $y_1≠y_2\Rightarrow α_2-α_1=Ay_2$

$由于α_1、α_2均为正数，则α_1=C使α_2有最大值、α_1=0使α_2有最小值$

$A>0、y_1=1\Rightarrow H=min(A+C,C)、L=max(0,A)$

$A>0、y_1=-1\Rightarrow 最大值α_2需越上界：α_2=C、最小值α_2需越下界：α_2=0$

$A<0、y_1=1\Rightarrow 最大值α_2需越上界：α_2=C、最小值α_2需越下界：α_2=0$

$A<0、y_1=-1\Rightarrow H=min(-A+C,C)、L=max(0,-A)$

$A=0\Rightarrow H=C、L=0$

$又α_2-α_1=±A，综上可得H=min(α_{2-old}-α_{1-old}+C,C)、L=max(0,α_{2-old}-α_{1-old})$

因此 $α_2=\left\{\begin{aligned}H && α_2>H\\α_2 && L≤α_2≤H\\L &&α_2<L \end{aligned}\right.\$

第二种情况： $K_{11}+K_{22}-2K_{12}=0$

此时代表两样本相等，数据去重工作没做好？

等效于 $\frac{dL}{dα_2}$ 求导后是常数项，类似 $y=ax+b\Rightarrow \frac{dy}{dx}=a$ ，此时L为线性函数

根据斜率方向最小值位于某一边界

$α_2$ 最小值根据其线性斜率正负在定义域边界取得： $α_2=0或α_i=C$ ，哪边的函数值小就取哪边

第三种情况： $K_{11}+K_{22}-2K_{12}<0$

理论上核函数使特征升维后，向量的大体方向是不会变化的（小于90°）；但某些核函数会导致其方向发生变化的同时也能保证一一映射。

类似第一种情况，此时L函数是开口向下的二次函数，它没有极小值。因此同②一样在定义域边界取得最小值

没有极小值，在某一边界取得最小值

第四步：各项参数求解

第二、三步详述了 $α_2$ 的求解过程，可谓道路坎坷。得到两组样本下的 $α_2$ 后也即将可以拨开云雾求解所有参数

由 $α_1y_1+α_2y_2=α_{1-old}y_1+α_{2-old}y_2$ 可得：

$α_1=α_{1-old}+α_{2-old}y_2y_1-α_2y_2y_1=α_{1-old}+y_1y_2(α_{2-old}-α_2)$

由于 $α_2$ 计算定义域时已经代入了 $α_1$ 的函数关系，因此 $α_1$ 无需再考虑其定义域。下面我们开始求w与b，w比较简单，上文已求出关系，将调整后的 $α_1、α_2$ 代入KKT条件③得 $w=∑α_iy_ix_i$

再来看b，参考上文提到的小插曲，我们基于KKT条件得出了样本落点情况。自然地，修改的b依然要满足这个条件，不然后续迭代就没有意义了：

$α与超平面关系条件：\left\{\begin{aligned} α_i=0 && y_i(wx_i+b)≥1\\ 0<α_i<C &&y_i(wx_i+b)=1 \\α_i=C && y_i(wx_i+b)≤1\ \end{aligned}\right.\$

将2个样本分别带入f(x)化简得：

$f(x_1)=∑α_iy_ix_ix_1+b_1=α_1y_1K_{11}+α_2y_2K_{12}+\sum_{i≥3}α_iy_iK_{1i}+b_1=y_1$

注：因为我们将x进行核函数升维，因此计算b时也保持使用

$b_1=y_1-α_1y_1K_{11}-α_2y_2K_{12}-\sum_{i≥3}α_iy_iK_{1i}=-(f(x_1)-y_1)+α_{1-old}y_1K_{11}+α_{2-old}y_2K_{12}+b_{old}-α_1y_1K_{11}-α_2y_2K_{12}$

因此 $b_1=b_{old}-E_1-y_1(α_1-α_{1-old})K_{11}-y_2(α_2-α_{2-old})K_{12}$

同理 $b_2=b_{old}-E_2-y_1(α_1-α_{1-old})K_{12}-y_2(α_2-α_{2-old})K_{22}$

若两个α均为 $0<α_i<C$ ，则 $b=b_1=b_2$ 注：因为方程一路求解下来我们用 $α_2$ 的关系式消掉了 $α_1$ ，此时又要保证 $y_if(x_i)=1$ ，那么你用 $α_1、α_2$ 来解这个一元一次方程式是没有区别的

若至少有一个α不满足上述条件式，此时会产生一个开放解，SMO提出者使用两者的平均值作为此次b的修改值

因此 $b=\left\{\begin{aligned} b_1 && 0<α_1<C,0<α_2<C \\ \frac{b_1+b_2}{2} &&otherwise \ \end{aligned}\right.\$

第五步：SMO收拾残局

我们通过上文只得出了一对乘子α的优化过程，现在我们通过循环将所有乘子都进行一次优化，而这个过程就是SMO，上面的求解思想也正是SMO的核心思想。我们现在利用SMO强势走一波：

①初始化超平面参数b=0、所有乘子α=0 （w可通过乘子的关系函数直接赋值）

②选择 $α_1、α_2$ 使得每次迭代有最大优化效果

选择第一个α：

优先寻找 $0<α_i<C$ 中的乘子，揪出第一个索引i对应的样本 $x_i$ 不满足 $y_i(wx_i+b)=1$ 条件的 $α_i$ 作为 $α_2$

若上述过程中 $α_i$ 都很老实，没有被揪出，则寻找边界上不满足对应条件的 $α_i$

注：优先找区间内的是因为多轮迭代后，处于边界的 $α_i$ 大多已被条件约束，调整效果不及区间内的 $α_i$

选择第二个α：

由 $α_2=α_{2-old}+\frac{y_2(E_1-E_2)}{K_{11}+K_{22}-2K_{12}}$ 可知为使 $α_2$ 改变最大，则 $|E_1-E_2|$ 要有最大值。寻找满足α与超平面关系条件中能产生最大值的样本，其对应索引的乘子作为需要优化的 $α_1$

③计算相关参数，更新本次w、b

计算 $Z=K_{11}+K_{22}-2K_{12}$ 及其相应条件下 $α_2$ 的上下限(Z>0)或值(Z≤0)

求解 $α_2$ ，并据此解出 $α_1、w、b$

④继续遍历，若某次选择没有可选的 $α_i$ 后停止迭代或连续X次迭代后min(L)减小率小于某个阈值（数量较多时越贴近最优值会多增加收敛过程，但预测效果上差不多满足要求其实就可以提前停止了）

个人看法

从SMO的过程可见，发明者为了让SVM满足可用性，嫁接了一堆数学知识使问题有求解方法，但这样却导致算法本身十分复杂。从机器学习大家推崇的奥卡姆剃刀定理来讲，我个人认为它虽从数学理论上解决了分类问题，但实际面临的运算复杂度却在如今的商业场景中十分受限，实际上原发明者的设计文章也提到尽量不要超过10000样本，放在上个世纪的数据量下可能说得过去，不过时至今日新模型、TB、PB数据量级的情况下，还是黯然失色

最后编辑于：2020.03.28 22:26:59

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 218,284评论 6赞 506
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,115评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,614评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,671评论 1赞 293
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,699评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,562评论 1赞 305
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,309评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,223评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,668评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,859评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,981评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,705评论 5赞 347
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,310评论 3赞 330
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,904评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,023评论 1赞 270
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,146评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,933评论 2赞 355

SVM-SMO

推荐阅读更多精彩内容