1. SMO

  1. 设训练样本数目为NN,原始观测空间的维数为mm。支持向量机所对应的二次规划问题往往使用SMO(Sequential Minimal Optimization)算法求解。SMO算法不断地求解仅涉及两个优化变量的二次规划问题。设给定训练样本为{(xi,yi)}i=1N\{(\mathbf x_i,y_i)\}_{i=1}^N,对偶问题为: D(α)=i=1Nαi12i=1Nj=1NαiαjyiyjxiTxjs.t.i=1Nαiyi=0,αi>0,i=1,,N \begin{aligned} D(\alpha)=\sum _{i=1}^N \alpha_i-\frac12 \sum _{i=1}^N \sum _{j=1}^N \alpha_i \alpha_j y_i y_j \mathbf x_i^{\mathrm T} \mathbf x_j \\ s.t. \sum _{i=1}^N \alpha_i y_i=0, \alpha_i>0, i=1,\ldots,N \end{aligned} 。 具体地,在每次迭代时,选中两个优化变量αi\alpha_{i^*}αj\alpha_{j^*},同时保持其它变量固定,求解关于αi\alpha_{i^*}αj\alpha_{j^*}的二次规划问题。请结合线性支持向量机(分为线性可分和线性不可分情况),给出在每次迭代过程中关于两个变量αi\alpha_{i^*}αj\alpha_{j^*}的解。

SVM使用一种非线性映射,把原训练数据映射到较高的维。在新的维上,搜索最佳分离超平面,两个类的数据总可以被超平面分开。

2. 线性可分

要找到具有“最大间隔”的划分超平面,即 maxw,b2ws.t.yi(wTxi+b)1,i=1,2,,N. \begin{aligned} \max_{w,b}\frac 2{||w||}\\ s.t. y_i(w^\mathrm{T}x_i+b)\geq 1,i=1,2,\ldots,N. \end{aligned} 等价于 maxw,b12w2s.t.yi(wTxi+b)1,i=1,2,,N. \begin{aligned} \max_{w,b}\frac 12{||w||}^2 \\ s.t. y_i(w^\mathrm{T}x_i+b)\geq 1,i=1,2,\ldots,N. \end{aligned}

3. 线性不可分

线性可分问题的支持向量机学习方法,对线性不可分训练数据是不适用的,为了满足函数间隔大于1的约束条件,可以对每个样本(xi,yi)(\mathbf x_i,y_i)引进一个松弛变量ξi0\xi_i≥0,使函数间隔加上松弛变量大于等于1: yi(wxi+b)1ξi y_i(w \cdot x_i+b)\geq 1-\xi_i 目标函数为 12w2+Cj=1Nξi \frac 12 ||w||^2 +C\sum_{j=1}^N \xi_i 其中C>0C>0为惩罚参数。 因此,最小化目标函数也就是使12w2\frac12||w||^2尽量小,同时使误分类点的个数尽量小。线性不可分的线性支持向量机问题变成下面的凸二次规划问题: minw,b,ξ12w2+Ci=1Nξis.t.yi(wxi+b)1ξi,i=1,2,,N,ξi0,i=1,2,,N \begin{aligned} \min_{w,b,\xi}\frac12||w||^2+C\sum_{i=1}^N\xi_i\\ s.t. y_i(w \cdot x_i +b)\geq 1-\xi_i,i=1,2,\ldots,N,\xi_i\geq0,i=1,2,\ldots,N \end{aligned}

4. 对偶问题

使用拉格朗日乘子法得到其“对偶问题”: L(w,b,α)=12w2+i=1Nαi(1yi(wTxi+b)) L(w,b,\alpha)=\frac 12{||w||}^2+\sum_{i=1}^N\alpha_i(1-y_i(w^\mathrm{T}x_i+b)) 其中α=(α1;α2;;αm)\alpha=(\alpha_1;\alpha_2;\ldots;\alpha_m)。令L(w,b,α)L(w,b,\alpha)中的wwbb的偏导为0可得

w=i=1Nαiyixi,0=i=1Nαiyi. \begin{aligned} w=\sum_{i=1}^N\alpha_iy_ix_i,\\ 0=\sum_{i=1}^N\alpha_iy_i. \end{aligned} 即可将L(w,b,α)L(w,b,\alpha)中的wwbb消去,得到对偶问题 D(α)=i=1Nαi12i=1Nj=1NαiαjyiyjxiTxjs.t.i=1Nαiyi=0,αi>0,i=1,,N \begin{aligned} D(\alpha)=\sum _{i=1}^N \alpha_i-\frac12 \sum _{i=1}^N \sum _{j=1}^N \alpha_i \alpha_j y_i y_j \mathbf x_i^{\mathrm T} \mathbf x_j \\ s.t. \sum _{i=1}^N \alpha_i y_i=0, \alpha_i>0, i=1,\ldots,N \end{aligned}

5. SMO算法

约束i=1Nαiyi=0\sum _{i=1}^N \alpha_i y_i=0重写为: αiyi+αjyj=c,αi0,αj0c=ki,jαkyk \begin{aligned} \alpha_{i^*}y_{i^*} +\alpha_{j^*}y_{j^*}=c,\alpha_{i^*}\geq 0,\alpha_{j^*}\geq 0\\ c=-\sum _{k \neq i^*,j^*}\alpha_k y_k \end{aligned} 用上式中的cc消去D(α)D(\alpha)中的αj\alpha _jαj=(cαiyi)yj \alpha_{j^*}=(c-\alpha_{i^*}y_{i^*})y_{j^*} 假设i=1i^*=1j=2j^*=2α2=(cα1y1)y2=γsα1 \alpha_2=(c-\alpha_1y_1)y_2=\gamma-s\alpha_1 γ\gamma为常数,s=y1y2s=y_1y_2

Kij=K(xi,xi),f(xi)=j=1NyjαjKij+b,vi=f(xi)j=12yjαjKijb \begin{aligned} K_{ij}=K(\mathbf x_i,\mathbf x_i),f(x_i)=\sum_{j=1}^N y_j\alpha_jK_{ij}+b,\\ v_i=f(x_i)-\sum_{j=1}^2y_j\alpha_jK_{ij}-b \end{aligned} 固定α1\alpha_1α2\alpha_2,得到: D(α)=α1+α212K11α1212K22α22y1y2K12α1α2y1α1v1y2α2v2+constant D(\alpha)=\alpha_1+\alpha_2-\frac 12K_{11}\alpha_1^2-\frac 12K_{22}{\alpha_2}^2-y_{1}y_{2}K_{12}\alpha_1\alpha_2-y_1\alpha_1v_1-y_2\alpha_2v_2+constant

α1\alpha_1为变量,则得到一个关于α1\alpha_1的单变量二次规划问题,仅有的约束是α10\alpha_1\geq 0

D(α1)=α1+γsα112K11α1212K22(γsα1)2sK12α1(γsα1)y1α1v1y2(γsα1)v2+constant \begin{aligned} D(\alpha_1)=\alpha_1+\gamma-s\alpha_1-\frac 12K_{11}\alpha_1^2-\frac 12K_{22}(\gamma-s\alpha_1)^2-sK_{12}\alpha_1(\gamma-s\alpha_1)\\ -y_1\alpha_1v_1-y_2(\gamma-s\alpha_1)v_2+constant \end{aligned}

α1\alpha_1求偏导以求得最大值,有 W(α1)α1=1sK11α1+sK22γK22α1sK12γ+2K12α1y1v1+y1v2=0 \frac {\partial W(\alpha_1)}{\partial \alpha_1}=1-s-K_{11}\alpha_1+sK_{22}\gamma-K_{22}\alpha_1-sK_{12}\gamma+2K_{12}\alpha_1-y_1v_1+y_1v_2=0 由此可得: α1new=y1(y1y2+y2γ(K22K12)+v2v1)K11+K222K12 \alpha_1^{new}=\frac{y_1(y_1-y_2+y_2\gamma(K_{22}-K_{12})+v_2-v_1)}{K_{11}+K_{22}-2K_{12}} 根据vv的定义,展开vv得到: v2v1=f(x2)f(x1)α1y1K12y2α2K22+y1α1K11+α2y2K12 v_2-v_1=f(x_2)-f(x_1)-\alpha_1y_1K_{12}-y_2\alpha_2K_{22}+y_1\alpha_1K_{11}+\alpha_2 y_2K_{12} 规定误差项Ei=f(xi)yiE_i=f(x_i)-y_i,取γ=sα1old+α2old\gamma=s\alpha_1^{old}+\alpha_2^{old},并规定η=K11+K222K12\eta=K_{11}+K_{22}-2K_{12}, 上式可化简为: α1new=α1old+y1(E2E1)η \alpha_1^{new}=\alpha_1^{old}+\frac{y_1(E_2-E_1)}\eta 再考虑限制条件0αic0\leq \alpha_i \leq c(α1,α2)(\alpha_1,\alpha_2)的取值只能为直线α1y1+α2y2=γ\alpha_1y_1+\alpha_2y_2=\gamma落在[0,C]×[0,C][0,C]\times [0,C]矩形中的部分。

此处输入图片的描述

因此需要检查α2new\alpha_2^{new}的值以确认这个值落在约束区间之内: α1new,clipped={H,α1new>Hα1new,Lα1newHL,α1new<L \begin{aligned} \alpha_1^{new,clipped}= \left\{ \begin{array}{ll} H, \alpha_1^{new}>H \\ \alpha_1^{new}, L\leq \alpha_1^{new} \leq H\\ L, \alpha_1^{new}< L \end{array} \right. \end{aligned} 其中

{L=max(0,α1α2),H=max(C,C+α1+α2)y1y2L=max(0,α1+α2C),H=max(C,α1α2)y1=y2 \begin{cases} L=max(0,\alpha_1-\alpha_2),H=max(C,C+\alpha_1+\alpha_2) & y_1 \neq y_2 \\ L=max(0,\alpha_1+\alpha_2-C),H=max(C,\alpha_1-\alpha_2) & y_1 = y_2 \end{cases}

假设s=y1y2s=y_1y_2,则新的α2new\alpha_2^{new}α2new=α2old+s(α1oldα1new,clipped) \alpha_2^{new}=\alpha_2^{old}+s(\alpha_1^{old}-\alpha_1^{new,clipped})

results matching ""

    No results matching ""