支持向量机（3）

港控/mmm° 2022-08-18 11:32 124阅读 0赞

以上两节讨论的都是线性可分的数据集，都是线性不可分的情况，上述模型不能解决。例如有一些离群点，将这些离群点除去后，剩下的大部分数据集是线性可分的。  
![这里写图片描述][20151213184659883]  
这时线性不可分意味着部分样本点不能满足函数间隔大于等于1的约束条件，则可以对每个样本点加入一个松弛变量*ξ**i*，使得函数间隔加上松弛变量大于等于1，这样约束条件变为：

*y**i*(*w*⋅*x**i*\+*b*)\+*ξ**i*≥1

,而放松限制条件后，我们需要重新调整目标函数，以对离群点进行处罚，于是目标函数变为

12||*w*||2\+*C*∑*i*=1*N**ξ**i*

,C为惩罚参数，一般根据问题确定。加入惩罚项  *C*∑*N**i*=1*ξ**i* 之后离群点越多，目标函数会变大，所以它使得离群点不至于过多，另外C值越大即对误分类的点惩罚越大，也就是越不希望看到离群点。因此目标函数控制了离群点的数目和程度，使大部分样本点仍然遵守限制条件。则新的模型如下：

min*w*,*b*12||*w*||2\+*C*∑*i*=1*N**ξ**i**y**i*(*w*⋅*x**i*\+*b*)\+*ξ**i*≥1*ξ**i*≥0*i*=1,2,⋯,*N*

和上一节类似，以上问题为原始问题，依然可以通过求解对偶问题来求解原始问题。对偶问题的求解步骤依然是：

*    
    
 *  建立拉格朗日函数  
    *L*(*w*,*b*,*ξ*,*α*,*β*)=12||*w*||2\+*C*∑*N**i*=1*ξ**i*−∑*N**i*=1*α**i*\[*y**i*(*w*⋅*x**i*\+*b*)\+*ξ**i*−1\]−∑*N**i*=1*β**i**ξ**i*
 *  对拉格朗日函数求极大极小问题，先看作是变量*w*,*b*的函数，分别对其求偏导，得到*w*,*b*的表达式。然后代入拉格朗日函数中，得到一个对*α*求极大。具体推导过程可以参看[支持向量机（2）][2]  
    这里直接列出最后推导结果：  
    
    
    min*α*12∑*i*=1*N*∑*j*=1*N**α**i**α**j**y**i**y**j*(*x**i*⋅*x**j*)−∑*i*=1*N**α**i*∑*i*=1*N**α**i**y**i*=0*C*≥*α**i*≥0*i*=1,2,⋯,*N*
    
      
    可以发现，这里的模型与之前线性可分的模型仅仅在条件上多了一个*C*≥*α**i*,而且没有了惩罚因子*ξ**i*,于是我们同样可以求得一个最优解*α*∗=(*α*∗1,*α*∗2,⋯,*α*∗*N*),再根据KKT条件，可以转化为最优*w*∗,*b*∗.KKT条件如下：  
    
    
    ∇*w**L*(*w*∗,*b*∗,*ξ*∗,*α*∗,*β*∗)=*w*∗−∑*i*=1*N**α*∗*i**y**i**x**i*=0∇*b**L*(*w*∗,*b*∗,*ξ*∗,*α*∗,*β*∗)=∑*i*=1*N**α*∗*i**y**i*=0∇*ξ**L*(*w*∗,*b*∗,*ξ*∗,*α*∗,*β*∗)=*C*−*α*∗−*β*∗=0*α*∗*i*\[*y**i*(*w*∗⋅*x**i*\+*b*)\+*ξ*∗*i*−1\]=0*β*∗*i**ξ*∗*i*=0*α*∗*i*≥0*y**i*(*w*∗⋅*x**i*\+*b*)\+*ξ*∗*i*−1≥0*β*∗*i*≥0*ξ*∗*i*≥0*i*=1,2,⋯,*N*
    
      
    则*w*∗=∑*N**i*=1*α*∗*i**y**i**x**i*  
    对于*α*,有三种情况：
 *  *α*=0,则*β*∗=*C*>0,*ξ*∗*i*=0,则*y**i*(*w*∗⋅*x**i*\+*b*)≥1
 *  0<*α*<*C*,则*β*∗>0,*ξ*∗*i*=0，*y**i*(*w*∗⋅*x**i*\+*b*)\+*ξ*∗*i*−1=0，则*y**i*(*w*∗⋅*x**i*\+*b*)=1
 *  *α*=*C*,则*y**i*(*w*∗⋅*x**i*\+*b*)\+*ξ*∗*i*−1=0,*ξ*∗*i*≥0，则*y**i*(*w*∗⋅*x**i*\+*b*)≤1

> 以上表明在两条间隔线外的样本点前面的系数为0，离群样本点前面的系数为C，而支持向量（也就是在超平面两边的最大间隔线上）的样本点前面系数在(0,C)上。通过KKT条件可知，某些在最大间隔线上的样本点也不是支持向量，相反也可能是离群点。  
> 因此若存在0<*α*∗*i*<*C*,则*y**i*(*w*∗⋅*x**i*\+*b*)=1,可以求得*b*∗

[20151213184659883]: /images/20220731/d5b27f20aec14c288e22b29617b99bb9.png
[2]: http://blog.csdn.net/u010414589/article/details/50285193