[机器学习] 支持向量机1——间隔和支持向量

支持向量机1——间隔和支持向量

支持向量机2——对偶问题

支持向量机4——引入松弛因子

支持向量机3——SMO算法

间隔和支持向量

给定训练样本集D={(x1,y1),(x2,y2),...,(xm,ym)},yi∈{−1,+1}$\left\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\right\},y_i\in \left\{-1,+1\right\}$。分类学习最基本的思想就是基于训练集D在样本空间中找到一个划分超平面，将不同类别的样本分开，但是能将训练样本分开的划分超平面可能有很多，哪一个是最好的呢？

直观上看，应该取找位于两类样本“正中间”的划分超平面，即B1$B_1$，因为该划分超平面对训练样本局部扰动的“容忍”性最好。例如，由于训练集的局限性或噪声的因素，训练集外的样本可能比上图中训练样本更接近两个类的分割界，这将使许多划分超平面出现错误，而B1$B_1$的超平面受影响最小。换言之，这个划分超平面所产生的分类结果是最鲁棒的，对未见的示例泛化能力最强。

在样本空间中，划分超平面可通过如下线性方程来描述：

下面我们将其记为(ω$\omega$,b)。样本空间中任意点x$x$到超平面(ω$\omega$,b)的距离可写成

这个公式具体可以用点到直线的距离来解释：点P(x0,y0$x_0,y_0$)到直线Ax+By+c=0$Ax+By+c=0$的距离为

我们希望能找到一个划分超平面能最大化间隔。最大化间隔的意思就是对于一个超平面，这个超平面两边（不同标签的数据）距离超平面最近的点到超平面的距离达到最大。

那么就引入两个概念：函数间隔和几何间隔

函数间隔和集合间隔

函数间隔
超平面(ω,b)$(\omega ,b)$关于样本(xi,yi)$(x_i,y_i)$的函数间隔为：

ωTx+b${\omega }^{T}x+b$是用来衡量样本距离超平面远近的一种尺度，如果yi$y_i$和ωTx+b${\omega }^{T}x+b$符号一致，则表示分类的正确性和确信度（样本距离超平面的远近可以表示确信度）

但是如果ω,b$\omega ,b$同时放大或者缩小，函数间隔会随之放大或缩小，但是实际上，分类超平面没有变。（x = 1 和 2x = 2）

几何间隔
超平面(ω,b)$(\omega ,b)$关于样本(xi,yi)$(x_i,y_i)$的几何间隔为：

其中ωTx+b||ω||$\frac{{\omega }^{T}x+b}{||\omega ||}$是样本到超平面的距离。乘以yi$y_i$可以表示是否正确分类。

间隔最大化

上面曾经说过，我们希望能找到一个划分超平面能最大化间隔。那么如下图所示，就是在超平面的左右两侧各找到一个距离超平面最近的样本。我们希望我们找到的超平面是所有可能的超平面里能使得间隔最大化的那个。

假设超平面就可以将样本正确分类，那么对于(xi,yi)∈D$(x_i,y_i)\in D$，若yi=1$y_i=1$，则ωTxi+b>0${\omega }^T{x}_i+b>0$，若yi=−1$y_i=-1$，则ωTxi+b<0${\omega }^T{x}_i+b<0$，由此可以推导

举例分离超平面最近的使得(1.1)$(1.1)$的等号成立，他们称之为支持向量。两个异类的支持向量到超平面的距离置和为：

推导过程为：
两个平行平面的距离：
平面1：Ax+by+c1=0$Ax+by+c_1=0$
平面2：Ax+by+c2=0$Ax+by+c_2=0$

那么最大化间隔就是找到划分超平面，满足(1.1)$(1.1)$的约束，使得γ$\gamma$最大。

这个问题可以转化成(1.3)$(1.3)$

支持向量机的优缺点

• 优点：泛化错误率低，计算开销不大，结果易解释。
• 缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二分类问题。
• 使用的数值类型：数值型和标称型

参考

1. http://www.cnblogs.com/en-heng/p/5965438.html
2. 机器学习（周志华）
3. https://blog.****.net/luoshixian099/article/details/51073885#comments