Support Vector Machines
定义在特征空间上的间隔最大的线性分类器,本质上是线性分类器，当训练数据线性不可分时，通过kernel trick将输入从输入空间(欧氏空间/离散集合)非线性地映射到特征空间(希尔伯特空间). 因此，支持向量机的学习是在特征空间进行的.
支持向量机的学习策略是间隔最大化，可形式化为一个求解凸二次规划问题，也等价于正则化的hinge loss最小化问题. 对应的学习目标是在特征空间中寻找分离超平面，w⋅x+b=0. 法向量w与特征在同一个空间里.与感知机利用错分最小求分离超平面不同(无穷多解)，支持向量机的解唯一.
间隔最大化具体的形式化为:
maxw,b γs.t. yi(w||w||⋅⋅xi+b||w||)≥γ ,i=1,2,...,N
其中， ri=yi(w||w||⋅xi+b||w||)表示超平面(w,b)关于样本点(xi,yi)的几何间隔. 在此基础上，定义最小间隔为超平面关于训练数据的几何间隔:γ=mini=1,2,...,N γi. 间隔最大化是极大极小几何间隔问题，是一个凸二次规划问题.
进一步考虑几何间隔与函数间隔的关系，另外，根据上述定义，最优化问题的求解变量是w,b，使得间隔最大.而函数间隔本身的取值并不影响最优化问题的解，因此间隔最大化问题可以从形式上简单的转化为:
minw,b 12||w||2s.t. yi(w⋅xi+b)−1≥0,i=1,2,...,N
为求解上述问题，引入拉格朗日对偶，将原始问题转化为对偶问题的好处，一是对偶问题往往更容易求解，特别地，有些非凸问题转化为对偶问题后可以变成凸优化问题，保证优化算法可以得到全局最优解，二是在支持向量机中我认为最nice的转化，这里只需要单纯地根据拉格朗日对偶方法转换成对偶函数，甚至不需要特意设计转化后的目标形式，就能使得问题形式更加容易理解，特别是与KKT条件相互辉映后更加容易理解为什么支持向量机在决定分离超平面的时候只需要少量的支持向量就可以确定下来.
下面的方法可以认为是转化对偶问题的一般方法:)
首先构建拉格朗日函数(Lagrange function):对每个不等式约束引进拉格朗日乘子(Lagrange multiplier)αi≥0,i=1,2,...,N，定义拉格朗日函数如下:
L(w,b,α)=12||w||2−∑Ni=1αiyi(w⋅xi+b)+∑Ni=1αi
接着根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题(不是极大极小问题时做下转化):
求minw,bL(w,b,a):
▽wL(w,b,a)=w−∑Ni=1aiyixi=0
得到:
将上述结果代入L(w,b,a)得到:
L(w,b,a)=12∑Ni=1∑Ni=1aiajyiyj(xi⋅xj)−∑Ni=1aiyi((∑Nj=1ajyjxj)⋅xi+b)+∑Ni=1ai=−12∑Ni=1∑Nj=1aiajyiyj(xi⋅xj)+∑Ni=1ai
即:minw,bL(w,b,a)=−12∑Ni=1∑Nj=1aiajyiyj(xi⋅xj)+∑Ni=1ai.
式中第一项初见Kernel trick:将原始输入空间的特征向量xi⋅xj通过Kernel method,
K(x,z)=ϕ(x)⋅ϕ(z),ϕ(x):X→H.
求minw,bL(w,b,a)对a的极大值:
maxa−12∑Ni=1∑Nj=1aiajyiyj(xi⋅xj)+∑Ni=1ais.t.∑Ni=1aiyi=0ai≥0,i=1,2,...,N
上式即为支持向量机的目标函数.
由于最大间隔函数的原始问题(primal problem)与对偶问题(dual problem)的对偶间隙(dual gap)为0，因此可以先求对偶问题的最优解，设为a∗=(a∗1,a∗2,...,a∗N)T，再由a∗求得对偶最优化问题的解. 根据KKT条件，必然存在下标j,使得aj>0. 根据KKT关于不等式约束条件/KKT互补条件的结论，可知aj>0表示第j个样本为支持向量. 即只需要用其中一个支持向量的aj，可以求得原始问题的最优解:
w∗=∑Ni=1a∗iyixib∗=yj−∑Ni=1a∗iyi(xi⋅xj) Tips:y2=1
综合上文，能够得到支持向量机的分离超平面:
实际求解时，支持向量个数往往小于样本个数N，只有少部分的ai>0. 这是因为w∗⋅xi+b∗=|1|，回顾前面所说，1为间隔，所以这个式子表示xi位于间隔边界面上.
关于软间隔线性支持向量机和非线性支持向量机，这里不做笔记，因为从intuition到问题的定义以及求解过程都与硬间隔支持向量机理解上是一致的. 而关于在非线性支持向量机中如何选择核函数超出了本文的范围，设计核函数时需要考虑怎么定义非线性映射，保证特征空间是希尔伯特空间等等. 简单的结论是:K:X×X→R是对称函数，K(x,z)为正定核函数的充要条件是其对应的Gram矩阵K=[K(xi,xj)]m×m是正定矩阵. 常用的核函数包含RBF, poly等. 从这里可以看出两点，一是核函数其实是一种度量距离的函数，推广来说是定义相似度的函数，这种相似度定义在希尔伯特空间. 进一步的，从分类决策函数f(x)=sign(∑Ni=1a∗iyi(x⋅xi)+b)，是不是可以将支持向量机理解成一种关于样本的集成策略采用加权平均的集成分类器? 第二个是核函数定义的距离是对称的.
在本文结尾想提提支持向量机的另一种解释:正则化的Hinge Loss.
minw,b∑Ni=1[1−yi(w⋅x+b)]++λ||w||2
第一项是由Hinge Loss函数定义的经验风险，第二项是正则化项.
0-1函数是二分类问题的真正的损失函数，不使用0-1函数估算经验风险是因为0-1函数不连续,而Hinge Loss虽然不能直接求导，但是有其他方法(后续介绍)，可以将其转化为可微函数. 另外，相比0-1损失函数，从形式上可以看出，Hinge Loss不仅要求分类正确并且确信度(间隔边界之外)要足够高时损失才是0,对学习算法有更高要求. 即Hinge Loss是0-1损失函数的上界. 在采用真实损失函数的上界替代真实损失函数时，称该上界为代理损失函数(surrogate loss function)
Mathjax Special Symbols
Yann LeCun: What is the relationship between Deep Learning and Support Vector Machines / Statistical Learning Theory?
