话说小明上次用朴素贝叶斯预测对了!小姐姐果然在图书馆复习
小明想,这次不能再等了,于是走上前去 ...
小明:同学,你好啊,你这是在看什么呢?
小明看了一眼,哇,竟然是机器学习,哈哈,不慌,这个我会!【窃喜】
小姐姐:机器学习啊,最近发现这个很有意思,不过感觉挺难的
小明:我是数学系的 , 以后有问题可以问我,交个朋友吧~
小姐姐:这书上写的这个什么SVM,写的都是公式 ,
你能不能通俗易懂的讲讲看什么是SVM呢 ? 我感觉这个挺有意思的~
小明:那我给你讲个故事吧,在很久以前,一个数学家要去追求一名他爱慕的姑娘
这名姑娘数学特别好,虽然心里也对这个数学家有好感,但还是要考考他数学怎么样
于是,姑娘在桌子上似乎有规律放了两种颜色的球,说:"你用一根棍分开它们?要求:尽量在放更多球之后,仍然适用。"
小明接着说:于是数学家快速放下了棍子:
小姐姐:这个不难啊,我也会放~
小明:姑娘又在桌上放了一些球,此时,原来放好的棍子,好像已经不能正确分开两种球了,因为有个球好像站错了阵营:
小姐姐:是啊,有个球没分对啊!
小明:如果球是有类别的,那么如何根据当前的球的情况,放下棍子,使得之后再放入球的时候尽量不被棍子分错呢?
小姐姐:这个不难啊,我就把棍子调整,让它尽量不靠近两种球,棍子距离两种分界面附近的球都尽量远。
小明:你好棒棒哦!其实你已经学会了支持向量机的精髓!
小姐姐:emmm,你不要逗我玩哦!
小明:SVM就是试图把棍放在最佳位置,好让在棍的两边有尽可能大的间隙。这个间隙就是球到棍的距离。
小明接着说:此时即使放更多球,很大可能还是将棍子作为一个不错的分界线
小明接着说:故事里的姑娘说,第一关你算是通过了,今晚一起去看电影吧~
小姐姐:感觉似懂非懂,比如这个棍的两边有尽可能大的间隙,这间隙怎么求呢?
小明:那我们一起来看看吧,当一个分类问题,数据是线性可分的,也就是用一根棍就可以将两种小球分开的时候,我们只要将棍的位置放在让小球距离棍的距离最大化的位置即可,寻找这个最大间隔的过程,就叫做最优化。
先看下线性可分的二分类问题:
上图中的(a)是已有的数据,红色和蓝色分别代表两个不同的类别。数据显然是线性可分的,但是将两类数据点分开的直线显然不止一条。上图的(b)和(c)分别给出了B、C两种不同的分类方案,其中黑色实线为分界线,术语称为“决策面”。
每个决策面对应了一个线性分类器。虽然从分类结果上看,分类器A和分类器B的效果是相同的。但是他们的性能是有差距的,看下图:
在"决策面"不变的情况下,我又添加了一个红点。可以看到,分类器B依然能很好的分类结果,而分类器C则出现了分类错误。
显然分类器B的"决策面"放置的位置优于分类器C的"决策面"放置的位置,SVM算法也是这么认为的,它的依据就是分类器B的分类间隔比分类器C的分类间隔大。
这里涉及到第一个SVM独有的概念"分类间隔"。在保证决策面方向不变且不会出现错分样本的情况下移动决策面,会在原来的决策面两侧找到两个极限位置(越过该位置就会产生错分现象),如虚线所示。
虚线的位置由决策面的方向和距离原决策面最近的几个样本的位置决定。而这两条平行虚线正中间的分界线就是在保持当前决策面方向不变的前提下的最优决策面。两条虚线之间的垂直距离就是这个最优决策面对应的分类间隔。
显然每一个可能把数据集正确分开的方向都有一个最优决策面(有些方向无论如何移动决策面的位置也不可能将两类样本完全分开),而不同方向的最优决策面的分类间隔通常是不同的,那个具有“最大间隔”的决策面就是SVM要寻找的最优解。
而这个真正的最优解对应的两侧虚线所穿过的样本点,就是SVM中的支持样本点,称为"支持向量"。
支持向量机是一种二分类模型,简称SVM,英文全称是Support Vector Machines。
求解这个"决策面"的过程,就是最优化。一个最优化问题通常有两个基本的因素:1)目标函数,也就是你希望什么东西的什么指标达到最好;
2)优化对象,你期望通过改变哪些因素来使你的目标函数达到最优。
在线性SVM算法中,目标函数显然就是那个"分类间隔",而优化对象则是决策面。
所以要对SVM问题进行数学建模,首先要对上述两个对象("分类间隔"和"决策面")进行数学描述。按照一般的思维习惯,我们先描述决策面。
由浅入深,考虑刚才棍子与球的二维空间的情况:
二维空间的直线方程为:
现在我们做个小小的改变,让原来的x轴变成x1,y轴变成x2:
移项得:
将公式向量化得:
(向量化,即将一系列数据放入矩阵中来表示公式,这里是两个矩阵乘法)
进一步向量化,用 w 列向量和 x 列向量和标量 b 进一步向量化:
其中,向量 w 和 x 分别为:
T 表示转置,(沿着对角线翻折)
这里w1=a,w2=-1
我们都知道,最初的那个直线方程 a 和 b 的几何意义,a 表示直线的斜率,b 表示截距,a 决定了直线与 x 轴正方向的夹角,b 决定了直线与 y 轴交点位置。
则平面上任意一个球 ( x0,y0)到棍子直线的距离为
如果推广到一般的二维平面上的直线:
Ax+By+C=0
则任意一个球到棍子的距离为:
我们之前说的棍子,或者说是决策面(超平面)
可以用向量的方式简化表示:
如果从2维变成多维情况,虽然公式
未改变
但是其中的向量有变化:
为法向量,决定了超平面的方向(垂直于超平面),如果是二维情况,超平面的方向与直线(棍子)的方向垂直!
b为位移项,决定了超平面和原点之间的距离。
所以,超平面被w和b确定! 将超平面记为(w,b)
所以空间中任意点 x 到超平面 (w,b)的距离可以写为
假设超平面(w,b)能够将训练样本正确分类,即对于一点(xi,yi),其中 xi 为向量,长度为维度。yi 表示类别,对于二分类问题 yi = +1表示一类,yi = -1表示另一类。
假设超平面能将两类样本正确分类,则:
当 yi = +1 时,根据公式得:
当 yi = -1 时,根据公式得:
如果我们要求再高一点,假设决策面正好处于间隔区域的中轴线上,并且支持向量到决策面的距离为 d,则:
当 yi = +1 时,根据公式得:
当 yi = -1 时,根据公式得:
对上面两不等式左右两边除 d,
就能得到:
其中,
距离超平面最近的几个点能使得上式
的等号成立,他们就是“支持向量”。
(下图中的G/R/S点)
两种异类支持向量到超平面的距离之和称为“间隔”(margin)
我们将wd、bd重新记为w、b
则 y = +1的支持向量到超平面的距离为:
则 y = -1的支持向量到超平面的距离为:
所以“间隔”为:
我们最初的目标就是要找到“最大间隔”的划分超平面,也就是转化为了以下问题:
目标:
约束条件:
i=1,2,...,m (表示第 i 个点)
那这个约束如何理解呢?感觉不直观!
当 yi = +1(即为正样本时),
所以
当 yi = -1(即为负样本时),
所以
为了方便求解,
可以转化为
为什么要做这样的等效呢?这是为了在优化的过程中对目标函数求导时比较方便,但这绝对不影响最优化问题最后的求解。
所以转化为了:
求解如下:将有约束的原始目标函数转换为无约束的新构造的拉格朗日
目标函数
αi 为拉格朗日乘子,
容易验证,当某个约束条件不满足时,例如
那么我们显然只要令
即可最大化 L,使得
而当所有约束条件都满足时,则有
即我们最初要最小化的量。因此,在要求约束条件得到满足的情况下最小化
实际上等价于直接最小化
(当然,这里也有约束条件,就是式中的),因为如果约束条件没有得到满足,会等于无穷大,自然不会是我们所要求的最小值。具体写出来,我们现在的目标函数变成了:
引入拉格朗日函数的对偶问题,即:
为何引入对偶问题呢?因为求解对偶问题比求解原问题更方便!
(涉及太多数学理论和推导,感兴趣课后大家可以研究一下)
下面我们将先求 L 对 w、b 的极小,再求 L 对 α 的极大!
先求解
分别对 w,b求偏导
因为拉格朗日乘子αi 未知,所以还是不能求解出 w 和 b,处理不等式约束问题的一种方法是把它变换成一组等式约束,只要限制拉格朗日乘子非负,这种变换就是可行的。
应用此约束后,神奇的事情发生了!
这个约束表明:除非点满足
否则拉格朗日乘子 αi 必须为0
所谓鱼与熊掌不可兼得(两者不可都不为0),大概能很好诠释这点!
所以只剩两种情况:(1)αi 为0,(2)αi>0时
我们看看
熟悉不?这不就是支持向量满足的条件嘛!
αi 为0的点肯定不在决策边界的超平面上了
再看这个公式,
发现定义决策边界的参数 w 和 b 仅仅依赖于这些αi>0的支持向量!
前方手推公式,高能预警!看不懂问题不大,可跳过!
合并了前两项,且用了导数条件
合并了前两项, 且用了导数条件 w
此时L(w,b,α)函数中只剩下一个变量αi了(xi ,yi是已知点的坐标)
再求外层的
此时,原问题转化为:
目标:
约束:
(约束是求导得到的)
这个式子可以通过SMO等算法进行求解得到结果(SMO算法有兴趣可以课后去了解一下包含大量数学公式【坏笑】)
小姐姐:我大概听懂了!但是如果要分的两部分球明显用一条直线无法分开呢?
这就是非线性SVM了!
利用核技巧将输入空间非线性问题转化到特征空间线性可分问题。
数学家没有棍可以很好帮他分开两种球了,现在怎么办呢?当然像所有武侠片中一样数学家桌子一拍,球飞到空中。然后,数学家抓起一张纸,插到了两种球的中间。
从空中角度看这些球,这些球看起来像是被一条曲线分开了。
当然这里的空中角度不一定是3维,可能是更高维度 !
我们再来看一个:
我们将数据才能够原先的坐标空间 x 变换到一个新的坐标空间 K(x)中,从而可以在变换后的坐标空间中,从而可以在变换后的坐标空间中使用一个线性的决策边界来划分这些点!
以上就是支持向量机的原理部分,你学会了么?