支持向量机 - 软间隔最大化

￡神魔★判官ぃ 2023-06-30 15:55 0阅读 0赞

### 前言 ###

之前写的一偏文章主要是[SVM的硬间隔][SVM]，结合[SVM拉格朗日对偶问题][SVM 1]可以求解得到空间最大超平面，但是如果样本中与较多的异常点，可能对样本较敏感，不利于模型泛化，于是有了软间隔的支持向量机形式，本文来了解一下此问题。

### 软间隔最大化 ###

引入松弛变量，使得一部分异常数据也可以满足约束条件： y i ( x i + b ) > = 1 − ε i y\_i(x\_i+b) >=1 - \\varepsilon\_i yi(xi\+b)>=1−εi，既然约束条件引入了松弛变量，那么点到超平面的距离是不是也要改变，于是调整为：  
 min ⁡ 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i N ε i s . t . y i ( x i + b ) ≥ 1 − ε i i=1,2...,n ε i ≥ 0 \\min \\quad \\frac\{1\}\{2\} ||w||^2+C\\sum\_\{i\}^\{N\}\\varepsilon\_i \\\\ s.t. \\quad y\_i(x\_i+b) \\ge 1 - \\varepsilon\_i \\qquad \\text\{i=1,2...,n\}\\\\ \\varepsilon\_i \\ge 0 min21∣∣w∣∣2\+Ci∑Nεis.t.yi(xi\+b)≥1−εii=1,2...,nεi≥0

*  C：表示惩罚因子，这个值大小表示对误分类数据集的惩罚，调和最大间距和误分类点个数之间的关系。
 *   ε i \\varepsilon\_i εi：也作为代价。

这也是一个凸二次规划问题，可以求解得到 w w w，但b的求解是一个区间范围，让我们来看看是怎么回事，求解流程跟硬间隔没差别，直接得到拉格朗日对偶问题：

max ⁡ a i > 0 , μ > 0 min ⁡ w i , b , ε L ( w , b , ε , a , μ ) = 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i N ε i + ∑ i = 1 N a i \[ 1 − y i ( w x i + b ) + ε i \] + ∑ i N μ i ε i \\max\_\{a\_i>0,\\mu>0\} \\min\_\{w\_i,b,\\varepsilon\} \\quad L(w,b,\\varepsilon,a,\\mu)= \\frac\{1\}\{2\} ||w||^2+C\\sum\_\{i\}^\{N\}\\varepsilon\_i+\\sum\_\{i=1\}^\{N\}a\_\{i\}\[1-y\_i(wx\_i+b)+\\varepsilon\_i\]+\\sum\_\{i\}^\{N\} \\mu\_i \\varepsilon\_i ai>0,μ>0maxwi,b,εminL(w,b,ε,a,μ)=21∣∣w∣∣2\+Ci∑Nεi\+i=1∑Nai\[1−yi(wxi\+b)\+εi\]\+i∑Nμiεi  
继续按照流程走：

*  对w、b、 ε \\varepsilon ε 求偏导，让偏导等于0，结果为：  
     w = ∑ i a i y i x i ∑ i a i y i = 0 C − a i − u i = 0 w = \\sum\_\{i\}a\_iy\_ix\_i \\\\ \\sum\_\{i\}a\_iy\_i = 0 \\\\ C-a\_i-u\_i =0 w=i∑aiyixii∑aiyi=0C−ai−ui=0
 *  代入上面的方程得到：

max ⁡ a i > 0 , μ > 0 L ( w , b , ε , a , μ ) = − 1 2 ∑ i ∑ j a i a j y i y j ( x i ∗ x j ) + ∑ i a i s . t . ∑ i N a i y i = 0 0 ≤ a i ≤ C \\max\_\{a\_i>0,\\mu>0\} \\quad L(w,b,\\varepsilon,a,\\mu) = -\\frac\{1\}\{2\}\\sum\_\{i\} \\sum\_\{j\}a\_\{i\}a\_\{j\}y\_\{i\}y\_\{j\}(x\_i \* x\_j) + \\sum\_\{i\}a\_i \\\\ s.t. \\quad \\sum\_\{i\}^\{N\}a\_iy\_i=0 \\\\ \\quad 0\\le a\_i\\le C ai>0,μ>0maxL(w,b,ε,a,μ)=−21i∑j∑aiajyiyj(xi∗xj)\+i∑ais.t.i∑Naiyi=00≤ai≤C  
去掉符号，将max 转换为 min ：  
 min ⁡ a i > 0 , μ > 0 L ( w , b , ε , a , μ ) = 1 2 ∑ i ∑ j a i a j y i y j ( x i ∗ x j ) − ∑ i a i s . t . ∑ i N a i y i = 0 0 ≤ a i ≤ C \\min\_\{a\_i>0,\\mu>0\} \\quad L(w,b,\\varepsilon,a,\\mu) = \\frac\{1\}\{2\}\\sum\_\{i\} \\sum\_\{j\}a\_\{i\}a\_\{j\}y\_\{i\}y\_\{j\}(x\_i \* x\_j) - \\sum\_\{i\}a\_i \\\\ s.t. \\quad \\sum\_\{i\}^\{N\}a\_iy\_i=0 \\\\ \\quad 0\\le a\_i\\le C ai>0,μ>0minL(w,b,ε,a,μ)=21i∑j∑aiajyiyj(xi∗xj)−i∑ais.t.i∑Naiyi=00≤ai≤C  
这里代入之后就只有一个因子 a i a\_i ai，对此方程求解 a i a\_i ai

*  w、b:  
     w = ∑ i a i y i x i w = \\sum\_\{i\}a\_iy\_ix\_i \\\\ w=i∑aiyixi  
    b的计算就需要思考了，选取满足 0 ≤ a i ≤ C \\quad 0\\le a\_i\\le C 0≤ai≤C的 a i a\_i ai，利用这些点来求解b：  
     b = y j − ∑ i a i y i ( x i ∗ x j ) b = y\_j-\\sum\_\{i\}a\_iy\_i(x\_i\*x\_j) b=yj−i∑aiyi(xi∗xj)  
    当然符合这个条件的也不只有一个，存在多个条件。求解平均值作为一个唯一值。
 *  超平面  
     y = w x + b y = wx+b y=wx\+b

和上一篇的硬间隔最大化的线性可分SVM相比，多了一个约束条件： 0 ≤ a i ≤ C 0\\le a\_i \\le C 0≤ai≤C。

### 参考博客 ###

统计学习基础

[SVM]: https://blog.csdn.net/randompeople/article/details/90020648
[SVM 1]: https://blog.csdn.net/randompeople/article/details/92083294