线性不可分情况
线性可分问题的支持向量机学习方法，对线性不可分训练数据是不适用的，为了满足函数间隔大于1的约束条件，可以对每个样本(x_i,y_i)(x_i,y_i)引进一个松弛变量ξ_i≥0ξ_i≥0，使函数间隔加上松弛变量大于等于1,，
y_i(w⋅x_i+b)≥1−ξ_iy_i(w⋅x_i+b)≥1−ξ_i
目标函数变为
12||w||2+C∑_j=1Nξ_i12||w||2+C∑_j=1Nξ_i
其中，C>0称为惩罚参数，值越大对误分类的惩罚越大，值越小对误分类的惩罚越小。
因此，最小化目标函数也就是使12||w||212||w||2尽量小（间隔尽量大），同时使误分类点的个数尽量小。
线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题：
min_w,b,ξ12||w||2+C∑_i=1Nξ_i s.t.y_i(w⋅x_i+b)≥1−ξ_i,i=1,2,...,N,ξ_i≥0,i=1,2,...,Nmin_w,b,ξ12||w||2+C∑_i=1Nξ_i s.t.y_i(w⋅x_i+b)≥1−ξ_i,i=1,2,...,N,ξ_i≥0,i=1,2,...,N
线性支持向量学习算法
- 选择惩罚参数C>0，构造并求解凸二次规划问题
min_α12∑_i=1N∑_j=1Nα_iα_jy_iy_j(x_i⋅x_j)−∑_i=1Nα_i s.t.∑_i=1Nα_iy_i=0 0≤α_i≤C,i=1,2,...,Nmin_α12∑_i=1N∑_j=1Nα_iα_jy_iy_j(x_i⋅x_j)−∑_i=1Nα_i s.t.∑_i=1Nα_iy_i=0 0≤α_i≤C,i=1,2,...,N
求得最优解α\*=(α_1\*,α_2\*,...,α_N\*)Tα\*=(α_1\*,α_2\*,...,α_N\*)T
- 计算w\*=∑_i=1Nα_i\*y_ix_iw\*=∑_i=1Nα_i\*y_ix_i
选择α\*α\*的一个分量α_j\*α_j\*适合条件0<α_j\*<C0<α_j\*<C，计算
b\*=y_i−∑_i=1Ny_iα_i\*(x_i⋅x_j)b\*=y_i−∑_i=1Ny_iα_i\*(x_i⋅x_j)
- 求得分离超平面
w\*⋅x+b\*=0w\*⋅x+b\*=0
分类决策函数：
f(x)=sign(w\*⋅x+b\*)f(x)=sign(w\*⋅x+b\*)
核函数
用线性分类方法求解非线性分类问题分为两步：首先使用一个变换将原空间的数据映射到新空间；然后在新空间里用线性分类学习方法从训练数据中学习分类模型。
核技巧应用在支持向量机的基本思想：通过一个非线性变换将输入空间（欧式空间RnRn或离散集合）对应于一个特征空间（希尔伯特空间H），使得在输入空间RnRn中的超曲面模型对应于特征空间H中的超平面模型（支持向量机）。
非线性支持向量分类机
非线性支持向量机
从非线性分类训练集，通过核函数与间隔最大化或凸二次规划，学习得到的分类决策函数：
f(x)=sign(∑_i=1Nα_i\*y_iK(x,x_i)+b\*)f(x)=sign(∑_i=1Nα_i\*y_iK(x,x_i)+b\*)
称为非线性支持向量，K(x,z)K(x,z)是正定核函数。
学习算法
- 选择适当的核函数K(x,z)K(x,z)和适当的参数C，构造并求解最优化问题
min_α12∑_i=1N∑_j=1Nα_iα_jy_iy_jK(x_i,x_j)−∑_i=1Nα_i s.t.∑_i=1Nα_iy_i=0,0<α_i<C,i=1,2,...,Nmin_α12∑_i=1N∑_j=1Nα_iα_jy_iy_jK(x_i,x_j)−∑_i=1Nα_i s.t.∑_i=1Nα_iy_i=0,0<α_i<C,i=1,2,...,N
求解最优解α\*=(α_1\*,α_2\*,...,α_N\*)α\*=(α_1\*,α_2\*,...,α_N\*)
- 选择α\*α\*的第一个正分量0<α_j\*<C0<α_j\*<C，计算
b\*=y_i−∑_i=1Nα_i\*y_iK(x_i⋅x_j)b\*=y_i−∑_i=1Nα_i\*y_iK(x_i⋅x_j)
- 构造决策函数
f(x)=sign(∑_i=1Nα_i\*y_iK(x⋅x_i)+b\*)f(x)=sign(∑_i=1Nα_i\*y_iK(x⋅x_i)+b\*)
序列最小优化算法
SMO算法是一种启发式算法。如果所有变量都满足KKT条件，那么这个最优化问题就解决了（KKT问题是该最优化问题的充要条件），否则，选择两个变量，固定其他变量，针对这两个变量构造二次规划问题。该方法会使原始二次规划问题的目标函数变小，不断分解自问题并对子问题求解进而达到求解原问题的目的。
由于
∑_i=1Nα_iy_i=0∑_i=1Nα_iy_i=0
所以
α_i=−1y_i∑_i=2Nα_iy_iα_i=−1y_i∑_i=2Nα_iy_i
两个变量的二次规划求解
假设选择两个变量α_1，α_2α_1，α_2，
min_α_1α_2=12K_11α_12+12K_22α_22+y_1y_2K_12α_1α_2 (α_1+α_2)+y_1α_1∑_i=3Ny_iα_iK_i1+y_2α_2∑_i=3Ny_iα_iK_12 s.t.α_1y_1+α_2y_2=−∑_i=3Ny_iα_i=ξ 0≤α_i≤C,i=1,2min_α_1α_2=12K_11α_12+12K_22α_22+y_1y_2K_12α_1α_2 (α_1+α_2)+y_1α_1∑_i=3Ny_iα_iK_i1+y_2α_2∑_i=3Ny_iα_iK_12 s.t.α_1y_1+α_2y_2=−∑_i=3Ny_iα_i=ξ 0≤α_i≤C,i=1,2
由于只有两个变量(α_i,α_j)(α_i,α_j)，因此根据两变量的符号情况约束条件可用二位空间中的图表示（参考α_1y_1+α_2y_2=ξ(常数)α_1y_1+α_2y_2=ξ(常数)），
L和H是αα取值的最小和最大值，如果y_i!=y_jy_i!=y_j，则
L=max(0,α_2−α_1),H=min(C,C+α_2−α_1)L=max(0,α_2−α_1),H=min(C,C+α_2−α_1)
如果y_i=y_jy_i=y_j，则
L=max(0,α_2+α_1+C),H=min(C,α_2+α_1)L=max(0,α_2+α_1+C),H=min(C,α_2+α_1)
令
g(x)=∑_i=1Nα_iy_iK(x_i,x)+bg(x)=∑_i=1Nα_iy_iK(x_i,x)+b
得到误差值：
E_i=g(x_i)−y_i=(∑_i=1Nα_iy_iK(x_i,x)+b)−y_i$,i=1,2E_i=g(x_i)−y_i=(∑_i=1Nα_iy_iK(x_i,x)+b)−y_i$,i=1,2
此最优问题的解是：
α_2new=α_2old+y_2(E_1−E_2)ηα_2new=α_2old+y_2(E_1−E_2)η
其中，
η=K_11+K_22−2K_12=||ϕ(x_1)−ϕ(x_2)||2η=K_11+K_22−2K_12=||ϕ(x_1)−ϕ(x_2)||2
ϕ(x)ϕ(x)为输入空间到特征空间的映射，经过剪辑后是
f(n)=⎧⎩⎨H,α_2new>H α_2new,L≤α_2new≤H L,α_2new<Lf(n)={H,α_2new>H α_2new,L≤α_2new≤H L,α_2new<L
则α_1newα_1new为
α_1new=α_1old+y_1y_2(α_2old−α_2new)α_1new=α_1old+y_1y_2(α_2old−α_2new)
变量的选择方法
SMO算法在每个子问题中选择两个变量优化，其中至少一个变量是违反KKT条件的。
1.第1个变量的选择
SMO算法在外层循环中选取违反KKT条件最严重的样本点，并将其对应的变量作为第1个变量，KKT条件如下
α_i=0<=>y_ig(x_i)≥1 0<α_i<C<=>y_ig(x_i)=1 α_i=C<=>y_ig(x_i)≤1α_i=0<=>y_ig(x_i)≥1 0<α_i<C<=>y_ig(x_i)=1 α_i=C<=>y_ig(x_i)≤1
其中，g(x_i)=∑Nj=1α_jy_jK(x_i,x_j)+bg(x_i)=∑j=1Nα_jy_jK(x_i,x_j)+b。
该检验在ϵϵ范围内进行的，在校验过程中，外层循环首先遍历所有满足条件0<α_i<C0<α_i<C的样本点，即在间隔边界上的支持向量点，检验它们是否满足KKT条件。如果这些样本点都满足KKT条件，那么遍历整个训练集，检验它们是否满足KKT条件。
2.第2个变量的选择
SMO算法在内层循环，假设在外层循环中已经找到第一个变量α_1α_1，现在要在内层循环中找到第2个变量α_2α_2，第2个变量选择的标准是希望能使α_2α_2有足够的变化。根据上一节可知，α_2newα_2new是依赖|E_1−E_2||E_1−E_2|的，为了加快计算速度，最简单的做法是选择|E_1−E_2||E_1−E_2|最大的（如果E_1E_1为负值，则选择最大的E_iE_i作为E_2E_2，否则选择最小的E_iE_i为E_2E_2，需要保存所有的E_iE_i）。
3.计算阈值b和差值E_iE_i
在每次完成两个变量优化后，都要重新计算阈值b。
由KKT条件得
∑_i=1Nα_iy_iK_i1+b=y_i∑_i=1Nα_iy_iK_i1+b=y_i
从而
b_1new=y_1−∑_i=3Nα_iy_iK_i1−α_1newy_1K_11−α_2newy_2K_21b_1new=y_1−∑_i=3Nα_iy_iK_i1−α_1newy_1K_11−α_2newy_2K_21
由于E_i=g(x_i)−y_i=(∑_i=1Nα_iy_iK(x_i,x)+b)−y_iE_i=g(x_i)−y_i=(∑_i=1Nα_iy_iK(x_i,x)+b)−y_i, \quad i = 1,2$，则
E_1=g(x_1)−y_1=∑_i=3Nα_iy_iK_i1+α_1oldy_1K_11+α_2oldy_2K_21+bold−y_1E_1=g(x_1)−y_1=∑_i=3Nα_iy_iK_i1+α_1oldy_1K_11+α_2oldy_2K_21+bold−y_1
将上式中的$y_i - \sum_{i=3}^N \alpha_i y_i K_{i1} 代入代入b_1^{new}$的公式中，得到
b_1new=−E_1−y_1K_11(α_1new−α_1old)−y_2K_21(α_2new−α_2old)+boldb_1new=−E_1−y_1K_11(α_1new−α_1old)−y_2K_21(α_2new−α_2old)+bold
对于b的取值：
bnew={b_1new=b_2new,0<α_inew<C,i=1,2 b_1new+b_2new2,α_inew==0orC，满足KKT条件bnew={b_1new=b_2new,0<α_inew<C,i=1,2 b_1new+b_2new2,α_inew==0orC，满足KKT条件
本文 由 cococo点点 创作，采用 知识共享 署名-非商业性使用-相同方式共享 3.0 中国大陆 许可协议进行许可。欢迎转载，请注明出处：
转载自：cococo点点 http://www.cnblogs.com/coder2012