机器学习：原理简明教程07-SVM
欢迎转载，作者：Ling，注明出处：机器学习：原理简明教程07-SVM
参考资料：《统计学习方法》
一句话概括：支持向量机计算每个分割平面到所有点中最小的那个距离，然后从最小距离中选择最大距离找到最佳分割超平面。它通过建立拉格朗日公式L，对w和b分别求导然后回带得到对偶问题，然后通过对偶问题求α，再回带求w和b，从而得到最佳分割超平面，其中求α用到了SMO方法，该方法每次选取两个α，以此化简对偶问题的函数，再对α1求导，得到α1的更新公式，以此再得到α2和b的更新公式，从而计算所有α的值，除此外，支持向量机如果函数换成核函数，可以支持非线性分类问题。
预备知识：
原问题：
对偶问题:
也就是把原问题求极值问题转化为对偶问题求极值问题：
- 对用拉格朗日表示原问题
- 原问题对参数求导
- 将极值点带入得到对偶问题
- 对对偶问题参数求导
- 将对偶参数带入2的结果得到参数值
- 从而得到原问题的具体结果
举例：
1. 原始问题
2. 拉格朗日表示
3. 求极值得到参数表示
4. 回带2得到对偶问题
对偶问题
等价
5. 对偶问题求α*， 可以用SMO算法
6. 将α回带3
7. 得到最后的分离超平面以及分类决策函数
支持向量机简介：
定义：
支持向量机（support vector machines，SVM)是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；支持向量机还包括核技巧，这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划（convex quadratic programming，见附录)的问题，也等价于正则化的合页损失函数（见后面解释）的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。
分类：支持向量机学习方法包含构建由简至繁的模型：
- 线性可分支持向量机（linear support vector machine in linearly separable case)：就是可以通过超平面直接分割
- 线性支持向量机（linear support vector machine)：有些点可能未很好分割，但是基本可以通过超平面分割
- 非线性支持向量机（non-linear support vector machine)：无法直接通过超平面分割，需要映射到高维分割
简单模型是复杂模型的基础，也是复杂模型的特殊情况。当训练数据线性可分时，通过硬间隔最大化（hard margin maximization)，学习一个线性的分类器，即线性可 分支持向量机，又称为硬间隔支持向量机；当训练数据近似线性可分时，通过软间隔最大化（soft margin maximization)，也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；当训练数据线性不可分时，通过使用核技巧 (kernel trick)及软间隔最大化，学习非线性支持向量机。
本文将介绍：3类支持向量机、核函数及一种快速学习算法——序列最小最优化算法（SMO)
线性可分支持向量机与硬间隔最大化：
线性可分支持向量机：
考虑一个二类分类问题。假设输入空间与特征空间为两个不同的空间。输入空间为欧氏空间或离散集合，特征空间为欧氏空间或希尔伯特空间。线性可分支持向量机、线性支持向量机假设这两个空间的元素一一对应，并将输入空间中的输入映射为特征空间中的特征向量。非线性支持向量机利用一个从输入空间到特 征空间的非线性映射将输入映射为特征向量。所以，输入都由输入空间转换到特征空间，支持向量机的学习是在特征空间进行的。
间隔最大及相应的约束最优化问题将在下面叙述。这里先介绍函数间隔和几何间隔的概念。
函数间隔和几何间隔
在上图中，有A、B、 C三个点，表示3个实例，均在分离超平面的正类一侧，预测它们的类。点A距分离超平面较远，若预测该点为正类，就比较确信预测是正确的；点C距分离超平面较近，若预测该点为正类就不那么确信；点B介于点A与C之间，预测其为正类的确信度也在A与C之间。
一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面w*x + b = 0确定的情况下，| w*x + b|能够相对地表示点x距离超平面的远近。而w*x + b 的符号与类标记y的符号是否一致能够表示分类是否正确。所以可用量y(w*x + b)来表示分类的正确性及确信度，这就是函数间隔(functional margin)的概念。
函数间隔定义：
函数间隔可以表示分类预测的正确性及确信度。但是选择分离超平面时，只有函数间隔还不够。因为只要成比例地改变w和b,例如将它们改为2w和2b,超平面并没有改变，但函数间隔却成为原来的2倍。这一事实启示我们，可以对分离 超平面的法向量w加某些约束，如规范化，||w||=1,使得间隔是确定的。这时函数间隔成为几何间隔（geometric margin)。
几何间隔定义：
函数间隔与几何间隔关系：
间隔最大化
支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对线性可分的训练数据集而言，线性可分分离超平面有无穷多个（等价于感知机)，但是几何间隔最大的分离超平面是唯一的。这里的间隔最大化又称为硬间隔最大化（与将要讨论的训练数据集近似线性可分时的软间隔最大化相对应)。
间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能
1. 最大间隔分离超平面
注：
7.11可以分子变为1或者分母变为1，为了更好计算，分子变为1（等比缩小，缩小的比例，合并到||W||中），同时倒过来，7.12不等式也替换成1
仿射函数：
就是一阶线性函数叫仿射函数
综上所述，就有下面的线性可分支持向量机的学习算法——最大间隔法(maximum margin method)。
最大间隔法：
补充求解过程：
任意一个超平面，所有点到它都有一个距离，这个距离最小的，就是该超平面到样本的唯一距离min，然后找这些距离中最大的max，作为最后的超平面
建立目标函数：
目标函数转换：
拉格朗日，原问题与对偶问题：
原问题求导：
回带
继续求minw,bL(w,b,α)对α的极大
整理目标函数：添加负号
对对偶问题求α
回带求w和b，得到分离超平面和决策函数
2. 最大间隔分离超平面的存在唯一性
线性可分训练数据集的最大间隔分离超平面是存在且唯一的.
定理7.1 (最大间隔分离超平面的存在唯一性） 若训练数据集r 线性可分，则
可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一.
(3)分离超平面能将训练数据集中的两类点完全正确地分开。
由解满足问题的约束条件即可得知（这其实是一句废话）。
3. 支持向量和间隔边界
注：
所以之后求解会发现，很多α会等于0，即不少训练样本不重要
实例
学习的对偶算法（见预备知识）
注：
就是先对w和b求导，然后将w回带回去，然后得到对偶问题
原问题就转成了对偶问题，通过对偶问题可以更方便求α，求出了α，可以通过以下方法得到w和b，从而得到分隔超平面
注：
就是将对偶求到α回带，求得w和b，从而求得分隔超平面
线性可分支持向量机学习算法：
综上所述，对于给定的线性可分训练数据集，可以首先求对偶问题(7.22) 〜
(7.24)的解α* ; 再利用式（ 7.25)和 式(7.26)求得原始问题的解 ；从而得到
分离超平面及分类决策函数. 这种算法称为线性可分支持向量机的对偶学习算法，
是线性可分支持向量机学习的基本算法.
注：
没有影响的点的α值都为0，大部分都为0
支持向量：
实例
线性支持向量机与软间隔最大化
补充：
目标函数：
拉格朗日函数
回带得到对偶问题
对偶问题转换
求α
回带得到最后结果
损失函数分析：
线性支持向量机：
线性可分问题的支持向量机学习方法，对线性不可分训练数据是不适用的，因为这时上述方法中的不等式约束并不能都成立。怎么才能将它扩展到线性不可分问题呢？这就需要修改硬间隔最大化，使其成为软间隔最大化。
线性支持向量机定义：
学习的对偶算法
线性支持向量机学习算法
符合条件的样本点上的平均值.
支持向量
合页损失函数
非线性支持向量机与核函数
对解线性分类问题，线性分类支持向量机是一种非常有效的方法。但是，有时分类问题是非线性的，这时可以使用非线性支持向量机。本节叙述非线性支持向量机，其主要特点是利用核技巧（kernel trick)。为此，先要介绍核技巧。核技巧不仅应用于支持向量机，而且应用于其他统计学习问题。
核技巧
1、非线性分类问题
注：
就是通过映射，从低维变成高维，高维可通过分隔平面分隔，回到低维就是一个曲线
2、核函数的定义
实例：
3、核技巧在支持向量机中的应用
正定核(了解)
常用核函数
非线性支持向量分类机
如上所述，利用核技巧，可以将线性分类的学习方法应用到非线性分类问题中去。将线性支持向量机扩展到非线性支持向量机，只需将线性支持向量机对偶形式中的内积换成核函数。
序列最小最优化算法
本节讨论支持向量机学习的实现问题。我们知道，支持向量机的学习问题可以形式化为求解凸二次规划问题。这样的凸二次规划问题具有全局最优解，并且有许多最优化算法可以用于这一问题的求解。但是当训练样本容量很大时，这些算法往往变得非常低效，以致无法使用。所以，如何高效地实现支持向量机学习就成为一个重要的问题。目前人们已提出许多快速实现算法。本节讲述其中的序列最小最优化（sequential minimal optimisation,SMO)算法，这种算法1998年由Platt提出。
两个变量二次规划的求解方法
注：
这里比较难理解，L和H是什么，实际上是α2可以取值的范围
http://blog.csdn.net/yclzh0522/article/details/6900707
自己图:
注：
定理给出了α更新的式子
变量的选择方法
注:
当有了α，之后如何更新b和E，这里给出了答案
SMO算法：个人感觉写的不好，实际过程看代码更清楚，就是根据样例，更新α，然后更新e，然后更新b，不断迭代
SMO思想补充：
主要是为了求α，然后就可以求w和b，从而得到最后结果
求α：
已知：（来自：SMO算法）
假设只有α1和α2，所有其他为常数，带入得到：
为啥有α*，可以看李航的书，里面有一步：
因为old和new结果都等于e
由于y1*y1肯定为1，因为y1要么1，要么-1
于是可以得到如下，然后对α2求导，得到极值：
从而得到了α2的更新表达式：
得到α2可以推算α1
然后看李航的书如何得到b，不断更新等停止了，就得到了所有α的值，然后回带求w和b，从而得到最后结果，再结合代码看看
补充：one vs one 和 one vs rest ： http://blog.csdn.net/china_cobra/article/details/5658636
SVM 算法最初是为二值分类问题设计的，当处理多类问题时，就需要构造合适的多类分类器。目前，构造SVM多类分类器的方法主要有两类：一类是直接法，直接在目标函数上进行修改，将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”实现多类分类。这种方法看似简单，但其计算复杂度比较高，实现起来比较困难，只适合用于小型问题中；另一类是间接法，主要是通过组合多个二分类器来实现多分类器的构造，常见的方法有one-against-one和one-against-all两种。
a.一对多法（one-versus-rest,简称OVR SVMs）。训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。
假如我有四类要划分（也就是4个Label），他们是A、B、C、D。于是我在抽取训练集的时候，分别抽取A所对应的向量作为正集，B,C,D所对应的向量作为负集；B所对应的向量作为正集，A,C，D所对应的向量作为负集；C所对应的向量作为正集， A,B,D所对应的向量作为负集；D所对应的向量作为正集，A,B,C所对应的向量作为负集，这四个训练集分别进行训练，然后的得到四个训练结果文件，在测试的时候，把对应的测试向量分别利用这四个训练结果文件进行测试，最后每个测试都有一个结果f1(x),f2(x),f3(x),f4(x).于是最终的结果便是这四个值中最大的一个。
note:这种方法有种缺陷,因为训练集是1:M,这种情况下存在biased.因而不是很实用.
b.一对一法（one-versus-one,简称OVO SVMs或者pairwise）。其做法是在任意两类样本之间设计一个SVM，因此k个类别的样本就需要设计k(k-1)/2个SVM。当对一个未知样本进行分类时，最后得票最多的类别即为该未知样本的类别。Libsvm中的多类分类就是根据这个方法实现的。
还是假设有四类A,B,C,D四类。在训练的时候我选择A,B; A,C; A,D; B,C; B,D;C,D所对应的向量作为训练集，然后得到六个训练结果，在测试的时候，把对应的向量分别对六个结果进行测试，然后采取投票形式，最后得到一组结果。
投票是这样的.
A=B=C=D=0;
(A, B)-classifier 如果是A win,则A=A+1;otherwise,B=B+1;
(A,C)-classifer 如果是A win,则A=A+1;otherwise, C=C+1;
...
(C,D)-classifer 如果是A win,则C=C+1;otherwise,D=D+1;
The decision is the Max(A,B,C,D)
notw:这种方法虽然好,但是当类别很多的时候,model的个数是n*(n-1)/2,代价还是相当大的.
c.层次支持向量机（H-SVMs）。层次分类法首先将所有类别分成两个子类，再将子类进一步划分成两个次级子类，如此循环，直到得到一个单独的类别为止。
对c的详细说明可以参考论文《支持向量机在多类分类问题中的推广》（计算机工程与应用。2004）
留言