技术栈

主页 > AI >

机器学习 西瓜书 Day06 支持向量机 SVM

技术栈 - 中国领先的IT技术门户

p121 - p146
今天负能量比较爆,所以现在沉下来看会书反而觉得心情好了些。

第六章 支持向量机

6.1 间隔和支持向量

给定一个训练集,最基本的想法就是找一个超平面划分他们。
在这些超平面中,正中间的显然“容忍性”最好,即“鲁棒”性

超平面可用以下式子来描述:
w`x + b = 0

任意x到平面距离可写为:
r = |w'x+b| / ||w||
假设这个面能正确分类,即对于y=1,w'x+b>0;y=-1,w`x+b<0。
放在实际里,可能不仅是>0 <0,如>=1与<=-1。

距离超平面最近的几个点使=1和=-1成立,这些点对应的向量称为支持向量(SV)
两个异类SV到平面距离之和为 r = 2/ ||w||,称为间隔(margin)

想要找到最大间隔的超平面,就是找w和b使得r最大,即:max 2/||w||

即min 1/2 * ||w||^2,s.t. yi (w`xi + b) >= 1。(※)
※式便是SVM的基本型

6.2 对偶问题

※式是一个凸二次规划问题,可以用现成包解决。
但有更高效方法:拉格朗日乘子法——得到对偶问题。
具体过程见p123-p124。

最终得到一个性质:训练完成后,大部分训练样本对计算过程是没用的,即最终效果只与支持向量有关。

在问题规模正比于样本数情况下,如何具体求解?

高效算法SMO

具体过程见p124-125

6.3 核函数

不是线性可分咋办?如异或问题。
答:映射到高维空间

这时应用6.1与6.2的方法计算时会出现问题:
特征维数太大,计算困难

引出核函数。见p127

若知道怎么映射,即φ的具体形式,就能写出核函数k()的具体形式。
但通常不知道φ,那么怎么确定k()呢?

定理6.1(核函数定理)。p128

由此可见,“核函数选择”成为了SVM的最大变数,核函数选择的好性能就好。
p128 6.1列出了常用的核函数。

核函数的计算准则:核函数的线性组合,直积、型都是核函数。

6.4 软间隔与正则化

之前我们一直假定训练样本在样本空间或者特征空间是线性可分的。
但是,核函数难找。
退一步说,即使找到了,恰好找到一个,也是有很大的过拟合嫌疑的。

缓解策略:允许SVM在一些样本上出错。
引进“软间隔”概念

即允许某些样本不满足约束 yi(w'xi + b) >= 1。(※※)
同时,不满足的应该尽可能少。
即优化目标为:
min 1/2 * ||w||^2 + C∑ bool_func(yi(w'xi + b) - 1) (※※※)
其中bool_func称为0/1损失函数。
定义见p130 ,但实际上我们自己是能写出来的。。。

显然,C为无穷大时,可理解成迫使所有样本满足(※※)

然而,bool_func性质不太好(非凸,非连续),使得优化目标不易求解。所以实际常用一些其他函数来代替bool_func,如p130 6.31-6.33三个函数。

若采用6.31的hinge损失: hinge(z) = max(0,1-z),并引入“松弛变量”
就是常用的“软间隔支持向量机”

经过复杂的计算推导过程(p131-132)。。
我们会发现:
软间隔SVM最终模型也是只和SV有关,即hinge函数使训练保持了稀疏性

可以发现,如果使用6.33作为bool_func,几乎得到了第三章中的对率回归模型。

注:博主第三章看的不太明白,因为数学有些多,之后要找机会重刷一遍。

总而言之,无论使用什么模型,基本形式都会是※※※形式。
前一项称作“结构风险”
后一项称作“经验风险”
C用来对两者进行折中。

从这个角度来说,※※※这样的式子称为“正则化问题”,前一项称为正则化问题,C称为正则化常数。

6.5 支持向量回归(SVR)

考虑回归问题,即希望得到一个类似w'x+b = 0这样的模型。

与传统回归不同,传统回归当且仅当y与f(x)相同时,才认为损失为0
SVR假设我们能容忍f(x)与y之间最多有ε的偏差,即只有误差大于ε才计算损失,落到中间宽度为2ε的间隔带里不计算损失。

经过复杂的数学推导。。。(p134-136),得到解:式6.53

SVR的支持向量是间隔带之外的向量,即其解仍具有稀疏性。

若考虑特征映射? 就是式6.56。

6.6 核方法

回顾SVM和SVR,我们发现学得的模型总能表示成核函数的线性组合。

实际上会有一个更普遍的结论:
定理6.2 表示定理 p137

意味着对于一般的损失函数和正则化项,优化问题的最优解都可以表示为k的线性组合。

这说明核函数真的很厉害。。

6.7 阅读材料

SVM直接掀起了统计学习浪潮

SVM如何提高效率,应用于大规模数据一直是研究热点。

SVM是针对二分类设计的,对多分类要进行专门的推广。

核函数太关键,“多核学习”借助集成学习思想,使用多个核函数。

休息一会儿

Nothing is more practical than a good theory.

神经网络和SVM的神奇的联系。(在注解中)

最后贴张图,难得看书真的动了动笔

责任编辑:admin  二维码分享:
本文标签: 函数SVM向量间隔超平面bool