机器学习.周志华《6 支持向量机》
间隔与支持向量
- 分类学习的最基本想法就是基于训练集D在样本空间中找到一个划分超平面，将不同类别的样本分开。
- 能将训练样本划分开的平面可能有很多个，选择位于两类训练样本正中间的划分超平面，原因是这个超平面的分类结果最鲁棒，泛化能力最强。
- 在样本空间中，划分超平面可通过以下线性方程来描述
- 样本空间中任意点 x到超平面 (w,b)的距离可以写成
- 假设超平面能够正确分类样本，则可以通过对w缩放可以使得下式成立
- 距离超平面最近的几个样本点使得上式等号成立，称作“支持向量”。两个异类支持向量到超平面的距离之和称为“间隔”.
- 欲最大化间隔，需要找到可以满足不等式组组3条件的能使γ最大的w和b , 这就是支持向量机SVM的基本型。
对偶问题：链接必看
- 上述问题是一个凸二次规划问题，能直接用现成的优化计算包求解。但是通过拉格朗日乘子法变换到对偶变量的优化问题之后，可以找到一种更加有效的方法来进行求解。
- 为SVM基本型添加拉格朗日乘子，则原问题的拉格朗日函数为
- L对w、b求偏导为零可以得到 ：
- 代入拉格朗日函数消去w、b得到SVM基本型的对偶问题为：
- 解α，求出w、b，得到模型为
- 上述过程需要满足KKT(Karush-Kuhn-Tucker)条件，即
- 对任意训练样本（xi,yi），总有αi=0 或yif(xi)=1。因此训练完成后，大部分的样本都不需要保留，最终模型仅与支持向量有关。
- 二次规划算法求解对偶问题，则问题的规模正比于训练样本数，在实际任务中会造成很大开销，因此提出SMO(Sequential Minimal Optimization)算法。
SMO算法：
-
步骤：不断执行以下两个步骤直到收敛
- 选取一对需要更新的变量αi和αj
- 固定αi和αj以外的参数，求解对偶问题更新后的αi 和αj
- 选取一对需要更新的变量αi和αj
- 只要选取的αi和αj中有一个不满足KKT条件， 目标函数就会在迭代后减小。KKT条件违背的程度越大，变量更新后可能导致的目标函数值减幅越大。
- 使选取的两变量所对应样本之间的间隔最大（两个变量有很大的差别，对它们进行更新会带给目标函数值更大的变化）。
核函数
- 原始样本空间线性不可分：将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。如果原始空间是有限维，那么一定存在一个高维特征空间使样本可分。
- 模型变成：
- 对偶问题为
- 重写对偶问题：
求解得支持向量展开：
此处k(x,xi)即为核函数；
结论：任何核函数都隐式的定义成了“再生核希尔伯特空间RKHS”的特征空间
- 常用核函数：
以及核函数的线性组合、直积等依旧是核函数。
软间隔和正则化
引入：现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分，即便线性可分，也很难判定这个结果不是由于过拟合造成的。缓解这个问题的一个方法是允许支持向量机在一些样本上出错，引入“软间隔”概念。
允许某些样本不满足约束
- 在最大化优化间隔期间，使得不满足约束的样本尽量少，优化目标可写成
其中
- 0/1函数非凸、非连续、数学性质不好，使得上式难以求解，因此人们用其他一些函数来代替它，称为“替代损失”。
- 三种常见的替代损失：
- 引入松弛变量ξi>=0（每个样本都有一个松弛变量，标准不满足约束的程度），常用的软间隔支持向量机：
- 与硬间隔支持向量机相似，软间隔支持向量机也是一个二次规划问题，可以通过拉格朗日乘子法得到拉格朗日函数：
- 求偏导为零可以得到
- 对偶问题为
- 上述过程需要满足KKT(Karush-Kuhn-Tucker)条件，即
- 实际上支持向量机和对率回归的优化目标相近，通常情况下他们的性能相当。对率回归的优势主要对于其输出具有自然的概率意义，即在给出预测标记的同时也给了概率，而支持向量机的输出不具有概率意义，欲得到概率需要进行特殊处理；此外，对率回归能够直接用于多分类任务，支持向量机为此需要进行推广。另一方面，可以看出hinge损失函数有一块平摊的零区域，这使得支持向量机的解具有稀疏性，而对率损失是光滑的而单调递减函数，不能导出类似支持向量的概念。因此对率回归的解依赖于更多的训练样本，其预测开销大。
支持向量回归SVR
- SVR问题华为：
:正则化常数；
：不敏感损失函数
- 引入松弛变量ξi和ξi^，重写为：
- 拉格朗日函数：
- 求导得0：
- 代入求SVR对偶问题：
- 满足KKT条件：
- 求得SVR的解：
- 进而求得：
- 考虑特征映射：
- 代入得SVR:
核方法
给定训练集，若不考虑偏移项b，SVM和SVR学得的模型均可以表示成核函数的线性组合。
- 对损失函数没有限制；
- 对正则化项Ω要求单调递增；
核化（引入核函数）：
目的：将现行学习期拓展为非线性学习器；
案例：线性判别分析LDA------>核线性判别分析KLDA
-----------------------------------------------------------------------------------------------------------*-*----
更多详细内容请关注公众号：目标检测和深度学习
---------------------------------------------------------------------------------------------------------------…^-^……---------