假定有一个训练集 , 它要么属于正例, 要么属于负例. 在分类问题当中, 我们最基本的想法就是基于训练集 D 在样本空间中找到一个划分超平面, 将不同的样本分开. 这样的划分平面有很多, 哪一个是最好的呢?
1.PNG
假设其中一个划分超平面是鲁棒性, 泛化能力最好的, 对训练样本局部扰动的 "容忍性" 也最好, 这个划分超平面用如下方程式描述:
2.PNG
3.PNG
样本空间到这个超平面的距离 d 表示为:
3.PNG
, 沿用一般求点到直线的距离公示, 即可得出该距离公式.
4.PNG
对于这个超平面, 上半区域是大于 0 的, 都为正例; 下半区域是小于 0 的, 都为负例. 所以有:
5.PNG
6.PNG
因为 w,b 等比缩放后, 方程式依然不变
7.PNG
所以若将 w,b 等比缩放的话, 就可得到以下公式:
8.PNG
再合并一下, 就得到如下公式:
9.PNG
回到最原始的问题, 怎样的超平面才是我们想要的超平面呢? 回到样本空间, 如果我们沿着超平面, 一遇到正例, 负例就作它的平行超平面, 这些点就是离超平面最近的点. 当这几个点离超平面距离越大, 间隔越大, 说明这个样本空间就划分的更好, 对训练样本局本部扰动的 "容忍" 性就最好
8.PNG
那么这个长得像街道的街宽要怎么求呢?
9.PNG
由刚刚的公示, 知道街边的点满足 Yi* (w*x+b)=1. 令街边的点的向量分别为 X+,X-, 那么街宽就为 (X+-X-) 在 W 法向量上的分量
10.PNG
11.PNG
于是, 求最大街宽的问题, 就转化为求最大 的问题.
原目标函数:
12.PNG
13.PNG
转化一下:
14.PNG
现在是如何求最优的 w,b 来来获得最大间隔
在数学中, 求最小值可以用到拉格朗日定理
15.PNG
16.PNG
17.PNG
18.PNG
我们可以发现, 原问题的对偶问题, 现在是极大极小问题
19.PNG
对 w,b 分别求偏导可得:
20.PNG
再带入原公式:
21.PNG
现在转化为求最优α, 求到了α, 就求到了最优 w,b, 那么超平面就求到了, 分类决策函数也就求到了.
之前提到的数据集都是线性可分的, 如果数据集如下图该怎么办呢?
22.PNG
上面的数据并不是线性可分的, 那么我们就可以利用核函数, 来解决这个问题.
23.gif
这个方法的核心是将样本从原始空间映射到一个更高维的特征空间.
该特征空间中划分超平面所对应的模型可表示为:
24.PNG
其中ϕ(x)表示映射后的特征向量
像线性可分情况一样, 也会有一下公式:
25.PNG
26.PNG
27.PNG
[ϕ(x_i )]^T ϕ(x_j)往往很难计算, 于是可以设想一个核函数
28.PNG
数据集形成的 M*M 个核矩阵要是半正定的
29.PNG
现在已经有很多的核函数, 比如多项式核, 高斯核, SigMoid 核等等, 在实际应用中, 往往依赖鲜艳领域知识 / 交叉验证等方案才能选择有效的核函数. 没有更多先验信息, 则使用高斯核函数. 对于高斯核函数, 我还没有进入更深一层次的研究.
在现实任务中, 往往很难确定合适的核函数是的训练集在特征空间中线性可分. 样本数据本身线性不可分; 不一定分类完全正确的超平面就是最好的.
在图中会发现几个离群点, 如果不考虑这些离群点, 有可能划分的超平面就不一样.
考虑这些离群点有时候会出现过拟合的现象,
缓解该问题的一个办法就是允许支持向量机在样本上出错, 因此, 引入软间隔的概念.
30.PNG
增加一个松弛因子ξi≥0
31.PNG
目标函数就变为:
32.PNG
C 越小, 对错误越能容忍. C 越大, 对我们的训练越能达到一个更好的结果. 防止过拟合的话, C 尽量小
带松弛因子的 SVM 拉格朗日函数
33.PNG
34.PNG
35.PNG
来源: http://www.jianshu.com/p/24d5a1d1d037