支持向量机

1.概要

线性模型的概念

如果有一个训练样本集可以被直线分开, 叫做线性可分样本集, 也可以说这个训练集是线性可分的, 就比如说上面的图
反之, 如果是下面的情况, 则为非线性可分样本集, 也叫线性不可分的

支持向量机(support vector machine SVM)由苏联人vapnik发明, 是一种分类模型, 通俗地说, 就是要找一条线离两类样本的距离尽可能地远, 这样容错率也高

2.数学描述

2.1性能指标

如果我们想要知道这样的想法为什么好, 需要一个数学描述, 首先要定义一个性能指标(performence measure)来衡量模型的表现:

在上面的图中我们可以找到很多条可以可以正确分类的线, 对于每一条能正确分开两类点的线, 平行移动这条线, 直到能够与点集相交, 设这两条平行线间的距离为d (SVM是最大化d的方法), 此时, 这两条平行线之间的任意一条平行的直线都能正确分类, 也就是说, 这条正确分类的线不唯一, 所以我们又有定义: 这条线要平分两条平行线, 即距离两条平行线的距离都是 d/2
d: 称为间隔(Margin), 将平行线插到的向量 称为支持向量(support vector) (注:是样本点)

2.2模型与数据

1.训练数据和标签:
表示训练数据
所有x是向量, 上面的二维向量中,
y是标签, (这里是为了推导方便)
2.线性模型 :
在二维空间中用直线分割两类样本, 但是在三维空间中, 用平面来分割两类样本, 在多维空间中, 使用超平面来分割样本, 本质上也是平面, 只不过参数 变成了矩阵

通过训练数据, 把 求出来, 样本类别把超平面分开, 超平面的参数是
3.训练集线性可分:
训练集线性可分的概念指的是:
对于样本集 存在 使:

然后将上面的两个式子合并一下, 就可以统一成一个式子:

3.SVM优化问题

3.1已知事实

在定义这个优化问题之前, 我们需要基于一些一致的定理与事实
事实1:
与 是同一个平面, 其中a为正实数
若 满足公式(2.1), 则 也满足公式(2.1)
事实2:
点到平面的距离公式用矩阵的形式重新表示:
特征点 到平面 的距离公式:

上面公式(3.1)中x是向量,不是坐标
则向量到超平面的距离:

上面这个双竖线是范数符号,通常指的是二范数, 所以严格意义上应该是

3.2问题描述

基于以上两个事实, 我们开始描述这个问题:
我们可以用a去缩放 到 ,最终使在支持向量上有:

由公式(3.2)得, 此时支持向量与平面的距离:

我们来解释一下上面的话, 超平面的定义是 ,假设带入后的值 ,现在用 放缩, 这里设 带入即得公式(3.3), 这样放缩的目的是让式子(3.4)的分子变成一个定值, 让式子(3.4)中的d能用一个变量表示, 因为我们在下面要将如何找到最大的d这个问题转化成最优化问题
在优化的时候由于是使d最大的 ,实际上这样的有无数多个,比如, 我们只需要找其中的一个即可, 这里设定的是找 的 , 当然等于2也是可以的, 在周志华老师机器学习这本书的第6章支持向量机中, 设的就是等于2, 通过这一系列变换, 我们得到了式子(3.4), 也就是说, 我们需要找到d最大的那个超平面, 即我们要找到 最小值

3.3定义问题

通过上面的铺垫, 我们可以开始定义这个SVM的最优化问题了, 这是一个凸优化中的二次规划问题, 即:
最小化(minimize):

限制条件(subject to):

解释一下上面的优化问题, 公式(3.5)的形式其实就是要求的最小值, 这样二分之一又平方的只是为了求导方便, 可能有的同学要问了, 式子(3.6)中为啥大于等于1哩? 这个也是放缩的结果, 因为我们知道 然后 被放缩成了1, 所以之前的式子(2.1)就改成了式子(3.6)的形式, 此时如果是支持向量的点, 间隔会等于d, 不是支持向量的点, 间隔会大于d

我们这里只讲凸优化问题的结论, 中间过程不讲证明,如果有兴趣的话可以看一下Boyd的Convex Optimization那本书, 下面简单介绍一下二次规划问题(quadratic programming):
1.目标函数(object function): 二次项, 要么无解, 要么只有一个极值
2.限制条件: 一次项

优化算法的中心思想就是一个不断试探的过程, 大家可以类比一下上一篇文章中神经网络的中梯度下降算法
SVM算法证明优雅的原因是它被转化成了凸优化问题, 感知机无法转化, 所以会陷入局部最小, 所以依赖经验会多一些

3.4非线性问题

我们可以看到, 上一小节我们定义的优化问题要么又唯一解, 要么无解, 这样就说明了如果按照3.3小节处理非线性问题, SVM是无解的, 所以我们要继续改造这个问题, 让他在非线性的时候也有解, 在周志华老师的《机器学习》中, 也把处理线性问题叫做硬间隔, 把处理非线性问题的方法叫做软间隔, 通过添加正则化罚项的方法来处理, 这里讲的非线性问题就是所说的软间隔
然后SVM给出了改造这个问题的方法:
改造一:
最小化:

限制条件:

其中, 已知, 是要求的, C是事先设定的超参数, 是正则项(regulation term), 式子(3.9)中实际上是N个约束条件
解释一下上面的式子, 这里的是松弛变量, 如果训练样本是非线性的, 我们无法找出来满足3.3小节的优化问题, 加上松弛变量就能满足了, 大家可以看下面的图想一下这个问题, 相当于是通过这个松弛变量来调节这个分类边界, 使得一些不满足条件的点满足条件

然后我们来说C, C是用来限制 , 防止它特别大的时候, 边界会到一个很远的地方
改造二
低维到高维的映射:
定义一个高维映射函数 ,使低维的 通过 映射到高维的 ,映射到高维后, 限制条件公式(3.8)又有了变化:

这个式子中的 也随之变成了更高维度的, 此时我们用异或问题这个典型的例子来介绍他是怎么变的:

异或的图像表达如上, 然后四个点的向量表达如下:

然后我们假定一个#card=math&code=%5Cvarphi%28x%29&id=rFPEs) ,之后的 是啥由核函数决定, 后面会讲到, 然后现在我们把x由2维向量变成5维向量
%3D%5Cbegin%7Bbmatrix%7D%20a%5E2%5C%5C%20b%5E2%5C%5C%20a%5C%5C%20b%5C%5C%20ab%5Cend%7Bbmatrix%7D%0A#card=math&code=x%3D%5Cbegin%7Bbmatrix%7D%20a%20%5C%5C%20b%20%5Cend%7Bbmatrix%7D%20%5Coverset%7B%5Cvarphi%7D%7B%5Clongrightarrow%7D%0A%5Cvarphi%28x%29%3D%5Cbegin%7Bbmatrix%7D%20a%5E2%5C%5C%20b%5E2%5C%5C%20a%5C%5C%20b%5C%5C%20ab%5Cend%7Bbmatrix%7D%0A&id=aS43M)
此时, 原本的4个点变成了如下的样子:
%3D%5Cbegin%7Bbmatrix%7D%200%5C%5C0%5C%5C0%5C%5C0%5C%5C0%20%5Cend%7Bbmatrix%7D%5Cin%20C_1%20%0A%5Cquad%20%5Cvarphi(x_2)%3D%5Cbegin%7Bbmatrix%7D%201%5C%5C1%5C%5C1%5C%5C1%5C%5C1%20%5Cend%7Bbmatrix%7D%5Cin%20C_1%20%0A%5Cquad%20%5Cvarphi(x_3)%3D%5Cbegin%7Bbmatrix%7D%201%5C%5C0%5C%5C1%5C%5C0%5C%5C0%20%5Cend%7Bbmatrix%7D%5Cin%20C_2%20%0A%5Cquad%20%5Cvarphi(x_4)%3D%5Cbegin%7Bbmatrix%7D%200%5C%5C1%5C%5C0%5C%5C1%5C%5C0%20%5Cend%7Bbmatrix%7D%5Cin%20C_2%0A#card=math&code=%5Cvarphi%28x_1%29%3D%5Cbegin%7Bbmatrix%7D%200%5C%5C0%5C%5C0%5C%5C0%5C%5C0%20%5Cend%7Bbmatrix%7D%5Cin%20C_1%20%0A%5Cquad%20%5Cvarphi%28x_2%29%3D%5Cbegin%7Bbmatrix%7D%201%5C%5C1%5C%5C1%5C%5C1%5C%5C1%20%5Cend%7Bbmatrix%7D%5Cin%20C_1%20%0A%5Cquad%20%5Cvarphi%28x_3%29%3D%5Cbegin%7Bbmatrix%7D%201%5C%5C0%5C%5C1%5C%5C0%5C%5C0%20%5Cend%7Bbmatrix%7D%5Cin%20C_2%20%0A%5Cquad%20%5Cvarphi%28x_4%29%3D%5Cbegin%7Bbmatrix%7D%200%5C%5C1%5C%5C0%5C%5C1%5C%5C0%20%5Cend%7Bbmatrix%7D%5Cin%20C_2%0A&id=RFZMI)

我们就可以很轻松地分类了, 取一个

在越高维的空间里, 可线性分类的可能性越大, 若在无限维的空间里, 可能性为1, 所以我们假定 是无限维, 所以不能被显式地表达

3.5核函数

由上面我们可以知道, 我们需要求出这个 ,但是SVM中给出了一种精彩的方法, 就是说, 我们可以不知道无限维映射#card=math&code=%5Cvarphi%28x%29&id=BBQpt)的显示表达, 我们只需要知道一个核函数K(kernel function), 使公式(3.10)这个优化式依然可解:

可以看到, 核函数是%2C%5Cvarphi(x_2)#card=math&code=%5Cvarphi%28x_1%29%2C%5Cvarphi%28x_2%29&id=UuMMq)两个无限维向量的内积, 在这个式子中, K是一个常数
我们常用的核函数有:
高斯核:

多项式核:

但是K是有限制的, 只有满足了特定的条件, 才能被拆成两个无限维向量的内积, 这里的知识在泛函分析中有详细介绍, 这里只介绍结论, 结论已经够用了:
能写成的充要条件(Mercer’s Theorem定理):
1.对称函数(交换性):

2.核矩阵半正定(半正定性):

大家了解一下这个定理即可, 当满足这个条件时,,就可以写成核函数了

3.6小结

1.SVM是最大化间隔(Margin)的分类算法
2.训练样本, 其中是向量, 是标签, 取正负1
3.定义优化问题:
最小化:

限制条件:

定义核函数:
目标: 要用来代替式(3.17)中的 , 因为不能显式地表达

4.优化理论与对偶问题

4.1整体思路

我们可以看到SVM要解决的问题是一个凸二次规划 (convex quadratic programming) 问题, 能直接用现成的优化计算包求解，但我们可以有更高效的办法, 那就是通过对偶问题来求解原问题

4.2对偶问题的构造

现在给出如下的一个非常普适的原问题的定义(prime problem):
最小化: #card=math&code=f%28%5Comega%29&id=RdykT)
限制条件:

式(4.1)中有K个不等式定义, 式(4.2)中有M个不等式定义
然后我们对上面的这个原问题进行对偶问题的构造, 这里考虑的是Lagrange对偶问题, 所以使用的是拉格朗日乘子法构造, 这几步同学们可以理解为高数中的拉格朗日数乘法求条件极值, 这里所表达的含义是在限制条件下求函数极值
定义对偶问题(dual problem)
第一步构造Lagrange函数:

解释一下这两个式子,式(4.3)是函数的参数形式, 式(4.4)是函数的向量形式, 是K维的, 是M维的
在式(4.4)中:
%3D%20%5Cbegin%7Bbmatrix%7Dg_1(%5Comega)%5C%5C%20g_2(%5Comega)%5C%5C%20%5Cvdots%5C%5C%20g_K(%5Comega)%20%5Cend%7Bbmatrix%7D%20%5Cquad%5Cquad%0Ah(%5Comega)%3D%20%5Cbegin%7Bbmatrix%7Dh_1(%5Comega)%5C%5C%20h_2(%5Comega)%5C%5C%20%5Cvdots%5C%5C%20h_M(%5Comega)%20%5Cend%7Bbmatrix%7D%0A#card=math&code=g%28%5Comega%29%3D%20%5Cbegin%7Bbmatrix%7Dg_1%28%5Comega%29%5C%5C%20g_2%28%5Comega%29%5C%5C%20%5Cvdots%5C%5C%20g_K%28%5Comega%29%20%5Cend%7Bbmatrix%7D%20%5Cquad%5Cquad%0Ah%28%5Comega%29%3D%20%5Cbegin%7Bbmatrix%7Dh_1%28%5Comega%29%5C%5C%20h_2%28%5Comega%29%5C%5C%20%5Cvdots%5C%5C%20h_M%28%5Comega%29%20%5Cend%7Bbmatrix%7D%0A&id=XCp3j)
第二步构造Lagrange对偶函数:

上面这个式子很关键, 他的意思是, 首先在固定的情况下,遍历所有的找到一个最小值, 然后再所有的中取#card=math&code=%5Ctheta%28%5Calpha%2C%5Cbeta%29&id=FyIqZ)的最大值之所以这样做, 是因为原问题和对偶问题的关系, 下面来解释一下这个:
我们可以将式(4.5)换一种形式:

也就是把最大最小那里调换一下位置, 结果是一样的, 然后简单分析这里:

取到正无穷有下面两种情况:
1. : 因为无符号要求, 所以可能取到正无穷
2. : 因为, 同理 可能取到正无穷
取到正无穷肯定是不行的, 如果不想取到正无穷, 则 ,如果要取到最大,则
此时我们就推出这样的式子:

然后我们把式(4.7)带入到式(4.6)中, 那就是在求最小化 ,这不就是原问题嘛ヾ(≧▽≦*)o
所以我们可以得到这样的结论: 原问题可以看做是对Lagrange函数先对 求最大，再对 求最小。对偶问题是先对求最小，再对 求最大

4.3对偶问题的定义

经过上面的分析, 我们现在就可以把这个对偶问题的定义写出来了:
最大化:

限制条件:

然后接下来两小节介绍两个重要的定理, 这两个定理描述的是原问题和对偶问题的关系

4.4弱对偶定理

根据上述的定义,我们有如下的定理:
如果是原问题的解, 而是对偶问题的解,则有:

然后我们简单证明一下这里:

解释一下上面的证明, 式(4.11)是固定了后遍历后求到的最小值, 式(4.12)指的是所有最小值中的最大的那个, 因为对偶问题中就是这么定义的嘛, 然后我们根据式(4.1) 式(4.2) 式(4.9) 的定义:

式(4.12)中后两项就小于等于0了, 此时我们得出式(4.13)的结论, 实际上,弱对偶定理是天然成立的，由构造对偶问题的过程决定, 然后我们又又又有了如下的定义:

G叫做原问题和对偶问题的间距(Duality Gap),对于某些特定的优化问题, 可以证明G=0, 此时引出强对偶定理

4.5强对偶定理

若为凸函数, 且 ,这两个函数都是线性的
若此优化问题的原问题与对偶问题的间距为0, 即:

则对于 要么满足 要么满足, 这个满足的条件被称为KKT条件
这个应该很好理解, 我们看一下式(4.12)就可以很容易看出来, 然后此时给出一个很重要的结论:
Lagrange对偶函数满足强对偶条件, 这里的证明是比较复杂的, 同学们知道结论就好
以上的对偶理论的目的是为了将最开始优化问题中的用代替

5.理论变成现实

5.1理论回顾

我们在上一节讲了推导SVM所需要的理论知识, 现在我们就需要利用学到的理论知识, 来将SVM的原问题转化为对偶问题, 转化的方法就是按照第4节的式子结构, 做相应的转化来解决实际问题
1.原问题:
最小化:
限制条件:

2.对偶问题:
最大化:

限制条件:

3.KKT条件:
满足 或

5.2问题转化

为了满足限制条件的形式, 我们把原来定义的SVM优化问题进一步做变形, 改成下面的这个样子:
原问题:
最小化:

限制条件:

解释上面的式子,最小化那里做的改动是C前面变成了符号, 由于C是常数, 所以没啥影响
限制条件中做的改动要大一些, 改动过程如下:

然后把式(5.7)移项就变成了式(5.6), 这样做的目的完全式为了满足之前理论中限制条件的形式, 要注意的是限制条件里没有%3D0#card=math&code=h%28%5Comega%29%3D0&id=lb3Ug)
对偶问题:
最大化:

限制条件:

上面的完全是根据理论中的结构来的,写的也很清晰, 现在我们当然是要求大括号里的最小值嘞
首先先了解一些前置知识:

根据上面的知识, 我们开始求偏导求最值:

然后把上面三个式子带入到先前的式子中:

这几个式子看似复杂, 其实都消去了:
第一步: 由 , 可以把式(5.14)中的和最后一项中的子项一起消去:

第二步: 由可知最后的等式:

然后接下来的变形非常的关键:
我们把式(5.16)中的每一项都重新整理一下
由公式(5.11)得:

其中的i和j是为了区分一下, 所以用了两个脚标, 然后我们在式(5.17)中看到了核函数
然后我们整理式(5.16)的第三项:

角标i和j表示的是一个意思,所以可以互换, 然后我们这里又看到了核函数 , 然后我们把这几项全加起来, 就得到了#card=math&code=L%28%5Comega%2C%5Cxi_i%2Cb%29&id=X6Xdl)的最值,也就是#card=math&code=%5Ctheta%28%5Calpha%2C%5Cbeta%29&id=s2SGi) :

然后我们重新整理一下SVM的原问题
最大化:

限制条件:

解释一下两个限制条件, 由, 且可推式(5.22), 就是给合并成了一个条件, 式(5.23)就不用解释了,之前求偏导得到的, 此时就已经转化成了优化理论中的标准形式

上面的这个问题也是个凸优化问题, 在这个问题中, 我们已知 未知所有的, 在周志华老师的《机器学习》中,解此问题的方法是SMO算法, 这里就不展开来讲了, 这里只说明他是个凸问题, 可以被解决

5.3回到最初

此时我们通过原问题和对偶问题之间的转化实现了不需要知道映射函数就可以进行高维映射, 现在我们其实又回到了最开始的问题, 我们不管怎么转化最终是要求超平面的参数 , 所以现在要解决的问题是: 如何将求 的问题转化成求, 从而求出超平面的表达式 , 现在我们假定是已经求出的最优解

我们可以看到之前的式(5.11), 要想求还得求 这种方法肯定是行不通了, 此时SVM给出了一种巧妙的方法, 我们可以直接求出, 而不需要单独求, 我们现在把式(5.11)带入到 中:

我们又又又看到了核函数, 通过这种变换, 我们可以直接通过来求得

求完了, 我们还得求b哩, b会稍微的复杂一些, 因为拉格朗日对偶函数满足强对偶条件, 所以需要用到之前讲的KKT条件, 我们现在对照5.2小节中对偶问题的定义式(5.14)来把KKT条件写出来, 即,让式(5.14)后两项为0, 满足了KKT条件, 这个b才能求出来:

在这两种情况中, 优化理论中的 对应的是两个限制条件 ,优化理论中 对应的也是两个限制条件, 没有
现在我们就开始讨论在这几种情况下b怎么求, 这种情况就不需要讨论了,很明显它不可能成立, 因为式(5.12), 所以我们讨论后面的这种情况, 通过式(5.26)两个式子联立方程组, 得:

在上面式(5.24)已经求出来了, 此时b也可求了, 超平面方程就求出来了

6.SVM算法总结

6.1训练流程

输入训练样本 然后解优化问题:
最大化:

限制条件:

使用SMO算法解该问题, 算出优化问题的解
算出 求出超平面方程

6.2测试流程

输入测试样本

7.SVM核函数总结

1.linear 线性内核(等于没用核):

2.poly 多项式核, d越大越复杂:

3.Rbf 高斯核(常用):

4.tanh核:

tanh为双曲正切函数