支持向量机的SMO算法
💜

支持向量机的SMO算法

待求解问题
目标函数
min⁡α12∑i=1N∑j=1NαiαjyiyjK(xi,xj)−∑i=1Nαi s.t ∑i=1Nαiyi=00≤αi≤C(∀i=1,2,…n)\begin{aligned}\min_{\alpha} & \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j K(x_i,x_j)-\sum_{i=1}^N\alpha_i\\\text { s.t } & \sum_{i=1}^N \alpha_i y_i=0\\ &0\leq \alpha_i\leq C(\forall i=1,2, \ldots n)\end{aligned}
且由KKT对偶互补条件有
αi∗=0⇒yi(w∗∙ϕ(xi)+b∗)≥10<αi∗<C⇒yi(w∗∙ϕ(xi)+b∗)=1αi∗=C⇒yi(w∗∙ϕ(xi)+b∗)≤1\begin{gathered}\alpha_i^*=0 \Rightarrow y_i\left(w^* \bullet \phi\left(x_i\right)+b^*\right) \geq 1 \\0<\alpha_i^*<C \Rightarrow y_i\left(w^* \bullet \phi\left(x_i\right)+b^*\right)=1 \\\alpha_i^*=C \Rightarrow y_i\left(w^* \bullet \phi\left(x_i\right)+b^*\right) \leq 1\end{gathered}
 
 
SMO算法基本思想
上式中有N个变量α1,α2,…,αN\alpha_1,\alpha_2,\ldots,\alpha_N需要在极小化的时候求出，直接优化很难。
SMO采用启发式的方法，每次只优化两个变量，而将其它变量视为常数。
由∑i=1Nαiyi=0\sum_{i=1}^N \alpha_i y_i=0知，假如α3,…,αN\alpha_3,\ldots,\alpha_N固定，那么α1,α2\alpha_1,\alpha_2的关系就确定了，从而转化为了一个比较简单的两变量优化问题。
min⁡α1,α112K11α12+12K22α22+y1y2K12α1α2−(α1+α2)+y1α1∑i=3NyiαiKi1+y2α2∑i=3NyiαiKi2 s.t. α1y1+α2y2=−∑i=3Nyiαi=ς0≤αi≤Ci=1,2\begin{gathered}\min_{\alpha_1, \alpha_1} \frac{1}{2} K_{11} \alpha_1^2+\frac{1}{2} K_{22} \alpha_2^2+y_1 y_2 K_{12} \alpha_1 \alpha_2-\left(\alpha_1+\alpha_2\right)\\+y_1 \alpha_1 \sum_{i=3}^N y_i \alpha_i K_{i 1}+y_2 \alpha_2 \sum_{i=3}^N y_i \alpha_i K_{i 2} \\\text { s.t. } \alpha_1 y_1+\alpha_2 y_2=-\sum_{i=3}^N y_i \alpha_i=\varsigma \\0 \leq \alpha_i \leq C \quad i=1,2\end{gathered}
 
两变量优化——>单变量约束优化
符号说明：上一轮迭代得到的解α1old,α2old\alpha_1^{old},\alpha_2^{old}，沿着约束方向未经剪辑的α2\alpha_2表示为α2new,unc\alpha_2^{new,unc}，本轮迭代完成后的解α1new,α2new\alpha_1^{new},\alpha_2^{new}
约束条件
notion image
由于𝛼_1,𝛼_2的关系被限制在盒子里的一条线段上，故两变量的优化问题实际上仅仅是一个变量的优化问题。不是一般性，假设是𝛼_2的优化问题。
L≤α2new≤HL\leq\alpha_2^{new}\leq H
  • 如果是左图的情况，L=max(0,α2old−α1old),H=min(C,C+α2old−α1old)L=max(0,\alpha_2^{old}-\alpha_1^{old}),H =min(C,C+\alpha_2^{old}-\alpha_1^{old});
  • 如果是右图的情况，L=max(0,α2old+α1old−C),H=min(C,α2old+α1old)L=max(0,\alpha_2^{old}+\alpha_1^{old}-C ),H =min(C,\alpha_2^{old}+\alpha_1^{old}).
假如通过求导得到了解α2new,unc\alpha_2^{new,unc}，那么
α2new ={Hα2new,unc >Hα2new,unc L≤α2new,unc ≤HLα2new,unc <L\alpha_2^{\text {new }}= \begin{cases}H & \alpha_2^{\text {new,unc }}>H \\ \alpha_2^{\text {new,unc }} & L \leq \alpha_2^{\text {new,unc }} \leq H \\ L & \alpha_2^{\text {new,unc }}<L\end{cases}
目标函数对α2\alpha_2求偏导
简记
Ei=∑j=1NαjyjK(xi,xj)+b−yi,vi=∑j=3NyjαjK(xi,xj),i=1,2\begin{aligned}E_i&=\sum_{j=1}^N \alpha_j y_j K\left(x_i, x_j\right)+b-y_i,\\ v_i&=\sum_{j=3}^N y_j \alpha_j K\left(x_i, x_j\right),i=1,2\end{aligned}
则待优化目标函数为
W(α1,α2)=12K11α12+12K22α22+y1y2K12α1α2−(α1+α2)+y1α1v1+y2α2v2W\left(\alpha_1, \alpha_2\right)=\frac{1}{2} K_{11} \alpha_1^2+\frac{1}{2} K_{22} \alpha_2^2+y_1 y_2 K_{12} \alpha_1 \alpha_2-\left(\alpha_1+\alpha_2\right)+y_1 \alpha_1 v_1+y_2 \alpha_2 v_2
将α1=y1(ς−α2y2)\alpha_1=y_1(\varsigma-\alpha_2y_2)代入得关于α2\alpha_2的目标函数为
W(α2)=12K11(ς−α2y2)2+12K22α22+y2K12(ς−α2y2)α2−(ς−α2y2)y1−α2+(ς−α2y2)v1+y2α2v2W\left(\alpha_2\right)=\frac{1}{2} K_{11}\left(\varsigma-\alpha_2 y_2\right)^2+\frac{1}{2} K_{22} \alpha_2^2+y_2 K_{12}\left(\varsigma-\alpha_2 y_2\right) \alpha_2-\left(\varsigma-\alpha_2 y_2\right) y_1-\alpha_2+\left(\varsigma-\alpha_2 y_2\right) v_1+y_2 \alpha_2 v_2
由偏导为0
∂W∂α2=K11α2+K22α2−2K12α2−K11ςy2+K12ςy2+y1y2−1−v1y2+y2v2=0\frac{\partial W}{\partial \alpha_2}=K_{11} \alpha_2+K_{22} \alpha_2-2 K_{12} \alpha_2-K_{11} \varsigma y_2+K_{12} \varsigma y_2+y_1 y_2-1-v_1 y_2+y_2 v_2=0
计算化简得到
α2new,unc =α2old +y2(E1−E2)(K11+K22−2K12)\alpha_2^{\text {new,unc }}=\alpha_2^{\text {old }}+\frac{y_2\left(E_1-E_2\right)}{\left(K_{11}+K_{22}-2 K_{12}\right)}
 
SMO算法两个变量的选择
第一个变量的选择（外层循环）
选择在训练集中违反KKT条件最严重的样本点，要满足的KKT条件为
αi∗=0⇒yi(w∗∙ϕ(xi)+b∗)≥10<αi∗<C⇒yi(w∗∙ϕ(xi)+b∗)=1αi∗=C⇒yi(w∗∙ϕ(xi)+b∗)≤1\begin{gathered}\alpha_i^*=0 \Rightarrow y_i\left(w^* \bullet \phi\left(x_i\right)+b^*\right) \geq 1 \\0<\alpha_i^*<C \Rightarrow y_i\left(w^* \bullet \phi\left(x_i\right)+b^*\right)=1 \\\alpha_i^*=C \Rightarrow y_i\left(w^* \bullet \phi\left(x_i\right)+b^*\right) \leq 1\end{gathered}
首先选择违反0<αi∗<C⇒yi(w∗∙ϕ(xi)+b∗)=10<\alpha_i^*<C \Rightarrow y_i\left(w^* \bullet \phi\left(x_i\right)+b^*\right)=1 的点；若这些支持向量都满足该KKT条件，在选择违反另外两条条件的点。
第二个变量的选择（内层循环）
  • 假设第一个循环已经选择了α1\alpha_1，第二个变量α2\alpha_2的选择指标是使得｜E1−E2｜｜E_1-E_2｜尽可能大；
  • 只需在E1E_1为正时，选择最小的EiE_i作为E2E_2；在E1E_1为负时，选择最大的EiE_i作为E2E_2；
  • 如果上述找到的点不能让目标函数有足够的下降， 可以采用遍历支持向量点来做α2\alpha_2直到目标函数有足够的下降；
  • 如果所有的支持向量作为α2\alpha_2都不能让目标函数有足够的下降，可以跳出循环，重新选择α1\alpha_1.
 
计算阈值b和差值E1E_1
在每次完成两个变量的优化之后，需要重新计算阈值b。
当0<α1new <C0<\alpha_1^{\text {new }}<C时，有
y1−∑i=1NαiyiKi1−b1=0y_1-\sum_{i=1}^N\alpha_i y_i K_{i 1}-b_1=0
故可得到
b1new=y1−∑i=3NαiyiKi1−α1newy1K11−α2newy2K21b_1^{n e w}=y_1-\sum_{i=3}^N \alpha_i y_i K_{i 1}-\alpha_1^{n e w} y_1 K_{11}-\alpha_2^{n e w} y_2 K_{21}
由于
E1=∑i=3NαiyiKi1+α1old y1K11+α2old y2K21+bold −y1E_1=\sum_{i=3}^N \alpha_i y_i K_{i 1}+\alpha_1^{\text {old }} y_1 K_{11}+\alpha_2^{\text {old }} y_2 K_{21}+b^{\text {old }}-y_1
因此b1newb_1^{new}可以用E1E_1表示为
b1new =−E1−y1K11(α1new −α1old )−y2K21(α2new −α2old )+bold b_1^{\text {new }}=-E_1-y_1 K_{11}\left(\alpha_1^{\text {new }}-\alpha_1^{\text {old }}\right)-y_2 K_{21}\left(\alpha_2^{\text {new }}-\alpha_2^{\text {old }}\right)+b^{\text {old }}
同理，若0<α2new <C0<\alpha_2^{\text {new }}<C，有
b2new =−E2−y1K12(α1new −α1old )−y2K22(α2new −α2old )+bold b_2^{\text {new }}=-E_2-y_1 K_{12}\left(\alpha_1^{\text {new }}-\alpha_1^{\text {old }}\right)-y_2 K_{22}\left(\alpha_2^{\text {new }}-\alpha_2^{\text {old }}\right)+b^{\text {old }}
最终的b计算为
bnew =b1new +b2new 2b^{\text {new }}=\frac{b_1^{\text {new }}+b_2^{\text {new }}}{2}
利用bnewb^{new}更新EiE_i:
Ei=∑SyjαjK(xi,xj)+bnew−yiE_i=\sum_S y_j \alpha_j K\left(x_i, x_j\right)+b^{n e w}-y_i
其中S是所有支持向量的集合。
 
SVM的SMO算法流程
notion image