主要思想

上篇文章提到了线性可分支持向量机，顾名思义，这个算法可以解决线性可分的数据，但在实际情况下几乎不存在完全线性可分的数据，为解决这个问题，需要引入“软间隔”这个概念，意思是允许一些点不满足约束条件 $y_i(\vec w\cdot\vec x_j+b)\ge1$

引入 Hinge 函数

使用 $hinge$ 损失函数将原优化问题

$\min\limits_{\vec w}\frac{1}{2}\parallel\vec w\parallel^2$ $s.t.\ y_i(\vec w\cdot\vec x_j+b)\ge1$

改写为：

$\min\limits_{\vec w}\frac{1}{2}\parallel\vec w\parallel^2+C\sum\limits^N_{i=1}\xi_i$ $s.t.\ y_i(\vec w\cdot\vec x_j+b)\ge1-\xi_i$

其中 $\xi_i$ 为“松弛变量”，$\xi_i=\max(0,1-y_i(\vec w\cdot\vec x_i+b))$，是一个 $hinge$ 损失函数，它反应了所有在边界内的点（也就是分类错误的点）到边界的距离。每一个样本对应一个松弛变量，松弛变量描绘了该样本不满足约束的程度。

$C>0$ 为惩罚函数，$C$ 越大，对分类的惩罚越大。或者可以理解为，$C$ 越大，边界越小（因为一但有一个在边界内的点都会带来很大的惩罚）

拉格朗日乘子法

把原优化问题

$\min\limits_{\vec w,b,\vec x_i}\frac{1}{2}\parallel\vec w\parallel^2+C\sum\limits^N_{i=1}\xi_i$ $s.t.\ y_i(\vec w\cdot\vec x_i+b)\ge1-\xi_i,\ \xi\ge0$

转换成拉格朗日函数

$L(\vec w,b,\vec\alpha,\vec\xi,\vec\mu)=\frac{1}{2}\parallel\vec w\parallel^2+C\sum\limits^N_{i=1}\xi_i-\sum\limits^N_{i=1}\alpha_i(y_i(\vec w\cdot\vec x_i+b)-1+\xi_i)-\sum\limits^N_{i=1}\mu_i\xi_i$

其中 $\alpha_i\ge0,\mu_i\ge0$

令 $L(\vec w,b,\vec \xi)$ 对 $\vec w,b,\vec \xi$ 求偏导（中间略去的过程参考线性可分支持向量机）

$\vec w=\sum\limits^N_{i=1}\alpha_iy_i\vec x_i$ $\sum\limits^N_{i=1}\alpha_iy_i=0$ $C=\alpha_i+\mu_i$

代回原式：

$\max\limits_\vec\alpha\sum\limits^N_{i=1}\alpha_i-\frac{1}{2}\sum\limits^N_{i=1}\sum\limits^N_{j=1}\alpha_i\alpha_jy_iy_j\vec x_i^T\vec x_j$ $s.t.\ \sum\limits^N_{i=1}\alpha_iy_i=0,\ 0\le\alpha_i\le C$

之后的过程与线性可分支持向量机相同。

调库实现：

from sklearn import svm
from sklearn import datasets
from sklearn.model_selection import train_test_split

My_Data = datasets.load_iris()
x = My_Data['data']
y = My_Data['target']
train_x, test_x, train_y, test_y = train_test_split(x, y, test_size = 0.3)

clf = svm.SVC(C = 1, kernel='linear')
clf.fit(train_x, train_y)

clf.predict(test_x)
print(clf.score(test_x, test_y))