ml_支持向量机

关于分类问题与划分超平面

对于二分类问题：

$$\mathbf{D}= \\{\ \mathbf \\{x^{(1)},y^{(1)}\\} ,\\{x^{(2)},y^{(2)}\\},\\{x^{(3)},y^{(4)}\\},\ ...\ ,\\{x^{(5)},y^{(6)}\\},\\{x^{(m)},y^{(m)}\\}\ \\},\ y_{i}\in \\{-1, +1 \\}$$

如果它在特征空间线性可分， 那么我们的目标就是基于$\boldsymbol D$, 在样本空间中找到一个划分超平面，将不同类别的样本分开。

如下图所示：

不难想到这样能将两类样本划分开的超平面应当不止一个，而我们想要找到的超平面，是能做到对训练样本局扰动的“容忍性”最好的那一个。

从上图中可以看到，蓝线虽然能将部分样本分开，但仍会有少部分错误划分，如蓝线可能会将部分负样本划分为正样本(如点B所在区域中的样本)，也可能会讲部分正样本划分为负样本(A所在区域中的样本)，倘若真实世界的样本多集中在A、B所在区域，那我们在训练集中看似还不错的模型(蓝)，则将表现的十分糟糕。

仅就上图而言，红线与绿线似乎都做到了正确分类，但用红线来划分在我们肉眼看来似乎更加合理，因为它似乎处于两类样本的“正中间”，为什么这样的分割线(划分超平面)是合理的？我们应该如何找到这样合理的分割线（划分超平面）？

为什么合理： 这与我们上面说到的局部扰动有关，由于训练集的局限性或噪声的原因，训练集以外的样本可能会比训练集中的样本更接近分界线(划分超平面), 这就可能会使我们得到的许多超平面在实际分类时出现错误（如上图的B点），没法很好的去做实际分类工作。而红线由于处于两类样本的“正中间”，你可以简单理解为它同时兼顾了两类样本，与他们都保持了相对较远的距离，因此是最不容易受到扰动的，换言之，这样的划分超平面的分类结果是最鲁棒的，对未见样本的泛化能力最强。

而我们下面工作的重点就是考虑如何找到这样理想的划分超平面。

寻找划分超平面

在样本空间中，我们将一个划分超平面通过如下线性方程描述：

$$\boldsymbol w^T\boldsymbol x + b = 0（2）$$

其中，$\boldsymbol x = (x_1,x_2,x_3,x_4,……,x_d )^T$，$\boldsymbol w = (w_1,w_2,w_3,w_4,…,w_d)^T$是超平面法向量，决定了超平面的方向，b为位移项，决定了超平面与原点之间的距离。

显然超平面是由$w$和b决定的， 故将超平面记作$(w,b)$ , 样本空间中任意一点$x$到$(w,b)$的距离为：

$$r = \frac{|w^T\boldsymbol x + b|}{||w||}（3）$$

假设超平面$(w,b)$能将训练样本正确分类，即对于$(\boldsymbol x^{(i)}, y^{(i)})\in \boldsymbol D$ ,

$$\begin{aligned} 若\ y^{(i)} = +1,则\ \boldsymbol w^T\boldsymbol x^{(i)} + b >0;\\ 若\ y^{(i)} = -1,则\ \boldsymbol w^T\boldsymbol x^{(i)} + b <0; \end{aligned}（4）$$

(这里+1, -1仅代表为正样本还是负样本，并非具体数值，所以上式正负1对调也可以，仅表示正样本在超平面一侧，负样本则在超平面另一侧，特此说明，下面为方便一致，均采用如上式定义表示，这样在分类正确时$y^{(i)}$与$\boldsymbol w^T\boldsymbol x^{(i)} + b$符号能够保持一致。)

现在我们

$${\large{令}}\Big\{\left. \begin{aligned} \boldsymbol w^T\boldsymbol x^{(i)} + b \ge+1,\ \ y^{(i)} = +1;\\ \boldsymbol w^T\boldsymbol x^{(i)} + b \le-1,\ \ y^{(i)} = -1;\\ \end{aligned} \right.（5）$$

此时，由于我们要找的超平面位于两类样本的“正中间”，因此距离$(w,b)$最近的几个训练样本点使得上面不等式的等号刚好成立

可以注意到这里不等式右侧都是1（+1，或-1），既然是放在不等式中，这里的1自然与y不同，而是真实的数字，那么为什么是1呢？

两个概念：函数间隔与几何间隔

函数间隔

对于一个训练样本$(x^{(i)} ,y^{(i)})$，我们定义它到超平面$(w,b)$的函数间隔为:

$$γ̂^{(i)} =y^{(i)}(w^T\boldsymbol x^{(i)}+b) = y^{(i)}f(\boldsymbol x^{(i)})（6）$$

用二维图像直观来看：

直线$l:x_2-2x_1+1 = 0$, 则按式(4)定义，$l$之上为正样本($y=+1$)，$l$之下为负样本($y=-1$)，

将A(1,3)代入函数间隔的定义：$γ̂ =(+1) (3-2+1)=2$

将B(2,0)代入函数间隔的定义：$γ̂ =(-1) (0-4+1)=3$

事实上按照我们的定义从图中便可以看出函数间隔实际即为：$|{x_2}_A-{x_2}_{A’}|$， $|{x_2}_B-{x_2}_{B’}|$，即$|w^T + b|$

从二维图像上看即样本点到$l$的纵向”距离”。

$Def：$于是我们便将集合D中所有样本点到超平面的函数间隔中的最小值定义为超平面关于$D$的函数间隔。

即：

$$γ̂ = min\{γ̂^{(i)}\},\ i=1,2,3,4,5,6....,m（7）$$

这样看来，函数间隔似乎很好地表达了样本点与划分超平面之间的“距离”，但实际上真是如此吗？

函数间隔确实从形式上刻画了“距离”， 但假如我们将超平面等式两边同比例放大/缩小，可以知道超平面本身依旧不变，

但此时函数间隔将会同比例放大，也就是说它并不能准确的刻画样本点与超平面之间的距离。甚至同一超平面表达式按不同比例缩放得到的距离都不同，更不要说不同超平面之间的比较了。

几何间隔

事实上几何间隔才是我们常说的“距离”，

$$\gamma = \frac{|w^T\boldsymbol x + b|}{||w||}（8）$$

即我们上面提到的r

支持向量机

支持向量

由上所述，应当知道我们定义距离$(w,b)$最近的几个样本点与超平面的距离(函数间隔)都为1也正是由于表达式可放缩而来的。

当我们的理想超平面可以正确分类时，他应当处于两类样本正中央，此时两类样本离超平面的距离应当满足：

$$\exists a>0,使得 \Big\{\left. \begin{aligned} \boldsymbol aw^T\boldsymbol x^{(i)} + ab \ge+a,\ \ y^{(i)} = +1;\\ \boldsymbol aw^T\boldsymbol x^{(i)} + ab \le-a,\ \ y^{(i)} = -1;\\ \end{aligned} \right.（9）$$

于是当我们将不等式两边同时按照比例a放缩，即可得到式(5)了，同时也该知道a即为函数间隔，

此时的函数间隔即为${|w^T\boldsymbol x + b|}$=1, 几何间隔即为$\gamma = \frac{1}{||w||}$

此时，距离距离超平面最近的几个训练样本刚好使式(5)的等号成立，这些样本便被称为支持向量，两个异类的支持向量到超平面的距离和为：

$$\gamma = \frac{2}{||w||} (10)$$

该项被称作间隔，即两类的最接近划分超平面边界到划分超平面的距离之和。

此时由于我们希望超平面距两类样本距离尽量远(使容忍性更好，受局部扰动更小)，我们希望找到具有”最大间隔(maximum margin)”的划分超平面，于是我们的目标便是使间隔$\gamma = \frac{2}{||w||}$最大。

（而我们又希望同时兼顾两类样本，即超平面位于两类样本正中间，故就像我们前面一直提的两侧间隔等距，于是目标变成了$\gamma = \frac{1}{||w||}$，即$||w||$最小，这一点已经由式(5)隐含地做到了。）

SVM的目标

我们希望借上述最小化目标求得我们所需要的理想划分超平面，因此SVM的目标便是：

$$\begin{aligned} {\min\limits_{w,b} \frac{1}{2} {||w||}^2 } \\ \end{aligned}$$ $$\begin{aligned} s.t. y_i(\boldsymbol w^T\boldsymbol x^{(i)} + b) \ge+1，i=1,2,3,4,......,m(即式(5))(11) \end{aligned}$$

这就是SVM的基本形式了（$\frac{1}{2}$没有实际意义，是为了下面求导方便，而且也不会影响$w,b$的求解）。

SVM的求解

To Be Continued········