从零开始学习SVM.pdf

发布时间：2022-06-19 发布人：admin 分类：说明书资料大小：1.73M 资料格式：pdf 举报版权申诉

6f10e353-98a4-46de-9c0e-6db32da9442f.pdf-第1页.png

第1页 / 共43页

6f10e353-98a4-46de-9c0e-6db32da9442f.pdf-第2页.png

第2页 / 共43页

6f10e353-98a4-46de-9c0e-6db32da9442f.pdf-第3页.png

第3页 / 共43页

6f10e353-98a4-46de-9c0e-6db32da9442f.pdf-第4页.png

第4页 / 共43页

6f10e353-98a4-46de-9c0e-6db32da9442f.pdf-第5页.png

第5页 / 共43页

6f10e353-98a4-46de-9c0e-6db32da9442f.pdf-第6页.png

第6页 / 共43页

6f10e353-98a4-46de-9c0e-6db32da9442f.pdf-第7页.png

第7页 / 共43页

6f10e353-98a4-46de-9c0e-6db32da9442f.pdf-第8页.png

第8页 / 共43页

线性分类的一个例子

拉格朗日对偶问题

原始问题(确切说是拉格朗日原始问题)

SVM的拉格朗日原始问题

对偶问题(确切说是拉格朗日对偶问题)

原始问题与对偶问题的关系

SVM中的原始问题与对偶问题

KKT条件

什么是KKT条件

等式约束优化问题(Lagrange乘数法)

不等式约束优化问题

SVM中的KKT条件

SVM如何处理噪点问题(不可分问题)

SMO算法

SMO算法原理

SMO算法步骤及代码

SVM处理非线性问题

Kernel函数的原理

常用的Kernel函数

用Kernel函数处理非线性数据的代码

SVM已有的库

SVM多分类问题

引用及致谢

目录 1 线性分类的一个例子 2 拉格朗日对偶问题 2.1 原始问题(确切说是拉格朗日原始问题) . . . . . . . . . . . . . . . . . . . . . . 2.2 SVM的拉格朗日原始问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 对偶问题(确切说是拉格朗日对偶问题) . . . . . . . . . . . . . . . . . . . . . . 2.4 原始问题与对偶问题的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 SVM中的原始问题与对偶问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 4 4 5 7 7 9 3 KKT条件 3.1 什么是KKT条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 等式约束优化问题(Lagrange乘数法) . . . . . . . . . . . . . . . . . . . . . . . . 3.3 不等式约束优化问题 . . 3.4 SVM中的KKT条件 . 9 9 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 . . . . 4 SVM如何处理噪点问题(不可分问题) 15 a rti n 小马哥 M y 5 SMO算法 . 5.1 SMO算法原理 . 5.2 SMO算法步骤及代码 . . . . 18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6 SVM处理非线性问题 31 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6.1 Kernel函数的原理 . 6.2 常用的Kernel函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 6.3 用Kernel函数处理非线性数据的代码 . . . . . . . . . . . . . . . . . . . . . . . . 38 . . . . b 7 SVM已有的库 8 SVM多分类问题 9 引用及致谢 41 42 43 1

从零开始学习SVM Yanchun Ma 2018 年 2 月 7 日写在最前, 本文的初衷本来是为了自己学习SVM, 但是学习之后我在想, 为何不让从来没有过SVM基础的人, 能够按照逻辑理解的进度一步一步的推导出SVM呢? 因为我也是从零开始的. 本文也不同于网上大神的文章, 我不会先把知识点都罗列一遍, 然后开始讲, 这样感觉逻辑性差, 也不便于理解(因为我就是这样, 等真正开始学习svm的时候, 发现和前面学习的知识点连接不上). 而是希望通过一个例子, 慢慢进入到svm里面, 需要用到哪个知识点的时候, 这个时候再去学习这个知识点. 所以本文的章节关系, 会和很多文章不一样. 也希望读者轻拍, 我会尽力, 慢慢重现我的学习步骤! 支持向量机, 因其英文名为 Support Vector Machine, 故一般简称SVM, 通俗来讲, 它是一种二类分类模型, 其基本模型定义为特征空间上的间隔最大的线性分类器, 其学习策略便是间隔最大化, 最终可转化为一个凸二次规划问题的求解. 乍乡乲乴乩乮小马哥 1 线性分类的一个例子乢乹一个简单的二分类问题如图1: 我们希望找到一个决策面使得两类分开, 这个决策面一图 1: 二分类问题般表示就是W T X + b = 0, 现在的问题是找到对应的W 和b使得分割最好, 知道logistic分类机器学习之logistic回归与分类的可能知道, 这里的问题和那里的一样, 也是找权值. 在那里, 我 2

们是根据每一个样本的输出值与目标值得误差不断的调整权值W 和b来求得最终的解的. 当然这种求解最优的方式只是其中的一种方式, 那么SVM的求优方式是怎样的呢？从直观上而言, 这个超平面应该是最适合分开两类数据的直线. 而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大. 所以, 得寻找有着最大间隔的超平面. 这里我们把问题反过来看, 假设我们知道了结果, 就是上面这样的分类线对应的权值W 和b. 那么我们会看到, 在这两个类里面, 是不是总能找到离这个线最近的点, 像图2这样: 我们定义一图 2: 二分类问题下离这个线最近的点到这个分界面(线)的距离分别为d1,d2, 如图2中所示. 那么SVM找最优权值的策略就是, 先找到最边上的点, 再找到这两个距离之和D = d1+ d2, 然后求解D的最大值! a rti n 小马哥 b y M 好了还是假设找到了这样一个分界面W T X + b = 0, 那么做离它最近的两类点且平行于分类面, 如图2中的虚线所示. 我们有这两个虚线以后, 那么真实的分界面应该就正好是这两个分界面的中间线, 这样d1就等于d2了. 因为真实的分界面为W T X + b = 0, 那么就把两个虚线分别设置为W T X + b = 1和W T X + b = −1. 可以看到虚线相对于真实面只是上下移动了1个单位距离, 有人会说你怎么知道正好是1个距离？确实不知道, 就假设上下是k个距离吧, 那么假设上虚线现在为W T X + b = k, 两边同时除k, 这样上虚线还是可以变 T X + b1 = 0, 成W1 可以看到从k到1, 权值无非从w变化到w1,b变到b1, 我再让w = w1,b = b1, 不是又回到了起点吗, 也就是说, 这个中间无非是一个倍数关系. 所以我们只需要先确定使得上下等于1的距离, 再去找这一组权值, 这一组权值会自动变化到一定倍数使得距离为1的. T X + b1 = −1, 而分类面变成了W1 T X + b1 = 1, 同理下虚线也可以变成W1 好了再看看D = d1 + d2怎么求吧, 假设对于二维的分界面W T X + b = 0, 也即:w1x1 + w2x2 + b = 0. 上分界线为:w1x1 + w2x2 + b = 1, 而下分界线为:w1x1 + w2x2 + b = −1, 那么这两条直线的距离为: (1) 这里W = [w1, w2]T , 是个向量, ||W||为向量的距离(二范数), 那么||W||2 = W T W , 下界面 , 要使D最大, 就要使分母最小, 等效于要同理. 这样D = d1 + d2 = d = = 2 ||W|| = 2√ W T W w2 |c2 − c1| 1 + w2 2 1 ||W|| 让 2 W T W 最小. 3

于是, 我们的问题变成了优化目标函数min( 面却有用. 1 2 W T W ), 乘一个系数0.5没影响, 但是在后我们知道, 如果一个一次函数分界面为W T X + b = 0, 那么线上方的x可以使得W T X + b > 0, 下方的x可以使得W T X + b < 0吧, 那么对于上界面以上的点就有W T X + b > 1, 下界面以下的点就有W T X + b < −1. 我们现在再假设上界面以上的点的分类标签为1, 下界面以下的点的分类标签为−1, 这两个不等式再分别乘以它们的标签就会统一为yi(W T xi + b) ≥ 1了(这也是为什么SVM在使用之前为什么要把两类标签设置为+1, −1, 而不是0, 1等等之类的了). 于是, 我们将问题转化成为了一个带约束的优化问题: 把约束条件换成小于号的形式: min s.t. W T W 1 2 yi(W xi + b) ≥ 1 min s.t. W T W 1 2 1 − yi(W xi + b) ≤ 0 (2) (3) 注意的是这可不是一个约束条件, 而是对所有的每个样本xi都有一个这样的约束条件. 这个问题, 是一个典型的优化问题了, 我们需要用到下章节中的拉格朗日对偶问题知识点了. a rti n 小马哥 2 拉格朗日对偶问题 y b M 2.1 原始问题(确切说是拉格朗日原始问题) 本节只介绍纯粹的数学知识, 也即“拉格朗日对偶问题中的原始问题”这个知识点, 先暂时忘掉SVM, 下一节会把这个知识点与SVM结合起来的, 看官莫急. 假设f (x),ci(x),hj(x)是定义在Rn上的连续可微函数(为什么要求连续可微呢, 后面再说, 这里不用多想), 考虑约束最优化问题: min f (x) s.t. ci(x) ≤ 0, hj(x) = 0, i = 1, 2, ..., k i = 1, 2, ..., l 称为约束最优化问题的原始问题. 现在如果不考虑约束条件, 原始问题就是: min f (x) (4) (5) 因为假设其连续可微, 利用高中的知识, 对f (x)求导数, 然后令导数为0, 就可解出最优解, 很easy. 那么, 问题来了, 偏偏有约束条件, 好烦啊, 要是能想办法把约束条件去掉就好了, bingo! 拉格朗日函数就是干这个的. 4

引进广义拉格朗日函数(generalized Lagrange function): k l L(x, α, β) = f (x) + αici(x) + βjhj(x) (6) i=1 j=1 不要怕这个式子, 也不要被拉格朗日这个高大上的名字给唬住了, 让我们慢慢剖析!这里x = (x(1), x(2), ..., x(n))T , αi, βj是拉格朗日乘子(名字高大上, 其实就是上面函数中的参数而已), 特别要求αi ≥ 0. 现在, 我们来仔细观察一下这个广义拉格朗日函数L(x, α, β): 当x满足原始的约束即ci(x) ≤ 0, hj(x) = 0, 并且αi ≥ 0时— L(x, α, β)有最大值f (x), 记作: max L(x, α, β) = f (x) (x满足原始问题约束) 当x不满足原始约束即ci(x) ≥ 0或者hj(x) = 0时, 一旦αi → ∞, 则: max L(x, α, β) = ∞ 由此, 我们可以将上面两种情况统一一下, 定义: (x满足原始问题约束) +∞, (其它) f (x), a rti n 小马哥 max α,β:αi≥0 L(x, α, β) = min x θP (x) = max L(x, α, β) = 所以, 在满足约束的条件下: min x θP (x) = min M x y b (7) (8) (9) 从式10可以看出, min 日原始问题, 下标P 表示原始的意思, 拉格朗日原始问题的最优值即为: θP (x)与原始优化问题min f (x)等价. 所以, 常用min x x p∗ = min x θP (x) f (x) (10) θP (x)代表拉格朗 (11) 通过拉格朗日这位大神的办法重新定义一个无约束问题(大家都喜欢无拘无束), 这个无约束问题等价于原来的约束优化问题, 从而将约束问题无约束化. 而我们本章节的目标, 就是将约束最优化问题的原始问题转化为拉格朗日原始问题. 2.2 SVM的拉格朗日原始问题回味一下在章节1最后一部分, SVM中的原始问题已经化为式3, 我们把章节2.1中的知识点运用到SVM这个具体的问题中来(注意本小节中的数学公式符号已经和章节2.1中不一样了, w在本节中才代表的是未知数, 需要求的东东). 由于我们的SVM已经转化为了求解: min s.t. wT w 1 2 1 − yi(wxi + b) ≤ 0 5 (12)

(这个式子跟式3一模一样, 写在这里只是为了不用翻来翻去)根据上面讲的拉格朗日原始问题, 就可以引入拉格朗日乘子法了(为了眼睛看起来舒适, 将上文中式3的目标函数的大写字母W 统一表述成了小写字母w, 表示的是同一个意思): L(w, b, α) = wT w + α1h1(x) + ... + αnhn(x) wT w − α1[y1(wx1 + b) − 1] − ... − αn[yn(wxn + b) − 1] (13) 1 2 = = 1 2 1 2 wT w − N 我们可以用图3来梳理一下: N αiyi(wxi + b) + αi i=1 i=1 a rti n 小马哥 M y b 图 3: SVM的拉格朗日原始问题通过图3能够看出, 我们已经把求解原始的SVM约束问题(式12)转变为了求解一个拉格朗日原始问题p∗(式14): p∗ = min w,b θP (w, b) = min w,b max αi≥0 L(w, b, α) (14) 但求解拉格朗日原始问题p∗仍然个很难解决的事情, 因为我们要先解决不等式约束的max问题, 然后再在w上求最小值. 也就是说, 我们需要先确定α, b的值, 然后再求能够使目标函数 6

最小化的w的值. 这个问题好难呀, 不过数学家们已经为我们想好了解决方案, 那就是通过它的对偶问题来解决, 并且已经证明! 所以, 我们下面先定义一个对偶问题再说. 2.3 对偶问题(确切说是拉格朗日对偶问题) 本节又是纯粹的数学知识, 也即“拉格朗日对偶问题中的对偶问题”这个知识点, 本节的知识点中罗列的公式与章节2.1中的数学公式是一致的. 定义关于α, β的函数: θD(α, β) = min x L(x, α, β) 我们最大化这个函数θD(α, β): max α,β:αi≥0 θD(α, β) = max α,β:αi≥0 min x L(x, α, β) (15) (16) 仔细观察一下式16, 我们发现它和拉格朗日原始问题的表达式10很像. 我们把它们俩写到一起, 对比一下看看: θP (x) = min x max α,β:αi≥0 L(x, α, β) (17)  min x max α,β:αi≥0 y b min L(x, α, β) θD(α, β) = max α,β:αi≥0 形式上可以看出很对称: —–拉格朗日原始问题是: 先确定α, β的值, 然后再求能够使目标函数最小化的x的值. —–拉格朗日对偶问题是: 先确定x的值, 然后再求能够使目标函数最大化的α, β的值. 其中, “先确定α, β的值”指的是, 在确定α, β的过程当中, 我们可以将x视为常量; 在求出α, β以后, α, β就成为常量, x就成为变量. 对偶问题中的这个过程同理. a rti n 小马哥 x M 定义式16就是所谓的“拉格朗日对偶问题”, 这个就是个纯粹的数学定义, 没什么好纠结为什么非得这么定义. 定义拉格朗日对偶问题的最优值为: d∗ = max α,β:αi≥0 θD(α, β) (18) 下面一章节我们会说明如何利用本章节定义的“拉格朗日对偶问题”来求解“拉格朗日原始问题”, 并证明之. 2.4 原始问题与对偶问题的关系这里我们先给出原始问题与对偶问题的关系的定理, 之后再证明之. 定理: 若原始问题与对偶问题都有最优值, 则: d∗ = max α,β:αi≥0 ≤ min max α,β:αi≥0 x min x L(x, α, β) L(x, α, β) = p∗ (19) 7

证明:对任意的α, β和x,有: θD(α, β) = min ≤ max α,β:αi≥0 x L(x, α, β) ≤ L(x, α, β) L(x, α, β) = θP (x) 即: θD(α, β) ≤ θP (x) 由于原始问题与对偶问题都有最优值, 所以: max α,β:αi≥0 θD(α, β) ≤ min x θP (x) 即: d∗ = max α,β:αi≥0 ≤ min max α,β:αi≥0 x min x L(x, α, β) L(x, α, β) = p∗ (20) (21) (22) (23) 定理得证. 也就是说原始问题的最优值不小于对偶问题的最优值, 这个不等式有一个名字, 叫弱对偶性质(Week Duality). 同时, 我们可以得到一个对偶间隙, 即p∗ − d∗. 但是我们要通过对偶问题来求解原始问题, 就必须使得原始问题的最优值与对偶问题的最优值相等, 也就是说, 如果能使式19恰好能够取等号, 即对偶间隙消失就好了. 说到这里, 现在就要说一个定理, 来拯救我们于水火, 使等号成立. 在凸优化理论中, 有一个Slater定理(也叫Slater条件), 当这个定理满足, 那么对偶间隙就会消失, 即p∗ = d∗, 等号成立. 此时称为强对偶性质(strong Duality). 幸运的是, 我们本文中要讲的SVM这个案例是满足Slater定理的. Slater定理: 存在x ∈ relintD, 使得 M y b a rti n 小马哥 fi(x) < 0, i = 1, ...m, Ax = b , 注:relintD指定义域D的相对内部. 此条件称作Slater条件, Slater定理是说, 当Slater条件成立且原问题是凸优化问题时, 强对偶性成立. 这个定理的数学证明有兴趣的可以自己学习一下, 本文中, 我们只需要知道SVM里面是满足Slater定理的. 也就是说, 在SVM中, 我们可以通过对偶问题来求解原始问题, 其原始问题的最优值与对偶问题的最优值是相等的. 同时, 给出推论: 推论:设x∗和α∗, β∗分别是原始问题和对偶问题的可行解, 如果p∗ = d∗, 那么x∗和α∗, β∗分别是原始问题和对偶问题的最优解所以, 当原始问题和对偶问题的最优值相等: p∗ = d∗时, 可以用求解对偶问题来求解原始问题(当然是对偶问题求解比直接求解原始问题简单的情况下), 下一章节, 我们将继续将本章节的知识点运用于SVM中. 8

分享到：

赞收藏

资料库

从零开始学习SVM.pdf

相关推荐

人工智能

热门标签

最新资料