支持向量机SVM
支持向量机（英语：Support Vector Machine，学术文献中常简称为SVM，中文简称则是SV机）是一种监督式学习的方法，可广泛地应用于统计分类以及回归分析。支持向量机属于一般化线性分类器，也可以被认为是提克洛夫规范化（Tikhonov Regularization）方法的一个特例。这族分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区，因此支持向量机也被称为最大边缘区分类器。
介绍支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面，分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt和Barnard将支持向量机和其他分类器进行了比较。 http://visionbbs.com/data/uploads/allimg/130823/2-130R3192610.png
有很多个分类器(超平面）可以把数据分开，但是只有一个能够达到最大分割。
动机
我们通常希望分类的过程是一个机器学习的过程。这些数据点并不需要是http://visionbbs.com/data/uploads/allimg/130823/2-130R3192611.png中的点，而可以是任意http://visionbbs.com/data/uploads/allimg/130823/2-130R3192611-50.png（统计学符号）中或者http://visionbbs.com/data/uploads/allimg/130823/2-130R3192612.png (计算机科学符号)的点。我们希望能够把这些点通过一个n-1维的超平面分开，通常这个被称为线性分类器。有很多分类器都符合这个要求，但是我们还希望找到分类最佳的平面，即使得属于两个不同类的数据点间隔最大的那个面，该面亦称为最大间隔超平面。如果我们能够找到这个面，那么这个分类器就称为最大间隔分类器。 http://visionbbs.com/data/uploads/allimg/130823/2-130R3192612-50.png
设样本属于两个类，用该样本训练svm得到的最大间隔超平面。在超平面上的样本点也称为支持向量.
我们考虑以下形式的样本点 超平面的数学形式可以写作
http://visionbbs.com/data/uploads/allimg/130823/2-130R3192613.png。
其中http://visionbbs.com/data/uploads/allimg/130823/2-130R3192613-50.png是超平面上的点，http://visionbbs.com/data/uploads/allimg/130823/2-130R3192614.png是垂直于超平面的向量。
根据几何知识，我们知道http://visionbbs.com/data/uploads/allimg/130823/2-130R3192614.png向量垂直于分类超平面。加入位移b的目的是增加间隔。如果没有b的话，那超平面将不得不通过原点，限制了这个方法的灵活性。
由于我们要求最大间隔，因此我们需要知道支持向量以及（与最佳超平面）平行的并且离支持向量最近的超平面。我们可以看到这些平行超平面可以由方程族：
http://visionbbs.com/data/uploads/allimg/130823/2-130R3192614-50.png
http://visionbbs.com/data/uploads/allimg/130823/2-130R3192614-51.png。
来表示。 由于http://visionbbs.com/data/uploads/allimg/130823/2-130R3192614.png只是超平面的法向量，长度未定，是一个变量，所以等式右边的1和-1只是为计算方便而取的常量，其他常量只要互为相反数亦可。
如果这些训练数据是线性可分的，那就可以找到这样两个超平面，在它们之间没有任何样本点并且这两个超平面之间的距离也最大。通过几何不难得到这两个超平面之间的距离是2/|w|，因此我们需要最小化 |w|。同时为了使得样本数据点都在超平面的间隔区以外，我们需要保证对于所有的http://visionbbs.com/data/uploads/allimg/130823/2-130R3192615.png满足其中的一个条件http://visionbbs.com/data/uploads/allimg/130823/2-130R3192615-50.pnghttp://visionbbs.com/data/uploads/allimg/130823/2-130R3192615-51.png
这两个式子可以写作：
=1,i<=i
原型
现在寻找最佳超平面这个问题就变成了在（1）这个约束条件下最小化|w|.这是一个二次规划QP(quadratic programming)最优化中的问题。
更清楚的表示：
最小化http://visionbbs.com/data/uploads/allimg/130823/2-130R3192616-50.png，满足http://visionbbs.com/data/uploads/allimg/130823/2-130R3192617.png,其中http://visionbbs.com/data/uploads/allimg/130823/2-130R3192617-50.png。
1/2这个因子是为了数学上表达的方便加上的。
解如上问题通常的想法可能是使用非负拉格朗日乘数 http://visionbbs.com/data/uploads/allimg/130823/2-130R3192617-51.png 于下式
http://visionbbs.com/data/uploads/allimg/130823/2-130R3192618.png
不过这样可能出错. 原因是：假如我们能找到一族超平面将这些点分割开来；那么所有的http://visionbbs.com/data/uploads/allimg/130823/2-130R3192618-50.png .因此我们可能通过将所有http://visionbbs.com/data/uploads/allimg/130823/2-130R3192617-51.png趋向http://visionbbs.com/data/uploads/allimg/130823/2-130R3192618-51.png得到最小值, 此最小值对这一族内所有成员都有效，而不是解决原问题的最优解。
不过以前的约束问题可以表示为
http://visionbbs.com/data/uploads/allimg/130823/2-130R3192619.png
此式表明我们寻找一个鞍点。这样所有可以被http://visionbbs.com/data/uploads/allimg/130823/2-130R3192619-50.png分离的点就无关紧要了，因为我们必须设置相应的 http://visionbbs.com/data/uploads/allimg/130823/2-130R3192617-51.png 为零。
这个问题现在可以用标准二次规划技术标准和程序解决。结论可以表示为如下训练向量的线性组合
http://visionbbs.com/data/uploads/allimg/130823/2-130R3192619-51.png
只有很少的http://visionbbs.com/data/uploads/allimg/130823/2-130R3192617-51.png会大于0. 相应的http://visionbbs.com/data/uploads/allimg/130823/2-130R3192620.png就是支持向量, 这些支持向量在边缘上并且满足http://visionbbs.com/data/uploads/allimg/130823/2-130R3192620-50.png. 由此可以推导出支持向量也满足: http://visionbbs.com/data/uploads/allimg/130823/2-130R3192621.png 因此允许定义偏移量http://visionbbs.com/data/uploads/allimg/130823/2-130R3192621-50.png. 实际上此支持向量比一般http://visionbbs.com/data/uploads/allimg/130823/2-130R3192621-51.png的支持向量鲁棒性更强:
http://visionbbs.com/data/uploads/allimg/130823/2-130R3192622.png
对偶型（Dual Form）
把原型的分类规则写作对偶型，可以看到分类器其实是一个关于支持向量（即那些在间隔区边缘的训练样本点）的函数。
根据http://visionbbs.com/data/uploads/allimg/130823/2-130R3192622-50.png，并且带入http://visionbbs.com/data/uploads/allimg/130823/2-130R3192619-51.png，可以得到支持向量机的对偶型如下： http://visionbbs.com/data/uploads/allimg/130823/2-130R3192622-51.png
满足http://visionbbs.com/data/uploads/allimg/130823/2-130R3192623.png
且http://visionbbs.com/data/uploads/allimg/130823/2-130R3192623-50.png
后验SVM
后验概率对分类器非常重要 分类器的输出必须结合后验概率才能确定 借助后验概率更好的改进超平面的泛化能力
软间隔Soft Margin
1995年, Corinna Cortes与Vapnik提出了一种改进的最大间隔区方法，这种方法可以处理标记错误的样本。如果可区分正负例的超平面不存在，则“软边界”将选择一个超平面尽可能清晰地区分样本，同时使其与分界最清晰的样本的距离最大化。这一成果使术语“支持向量机”（或“SVM”）得到推广。这种方法引入了松驰参数http://visionbbs.com/data/uploads/allimg/130823/2-130R3192623-51.png以衡量对数据http://visionbbs.com/data/uploads/allimg/130823/2-130R3192624.png的误分类度。
http://visionbbs.com/data/uploads/allimg/130823/2-130R3192624-50.png。
随后，将目标函数与一个针对非0http://visionbbs.com/data/uploads/allimg/130823/2-130R3192623-51.png的惩罚函数相加，在增大间距和缩小错误惩罚两大目标之间进行权衡优化。如果惩罚函数是一个线性函数，则等式（3）变形为
http://visionbbs.com/data/uploads/allimg/130823/2-130R3192624-51.png
回归
解决问题的参数方法大多通过解决那些最优化的问题派生出来的，现有一些从SVM问题中诞生出来的可以快速解决QP问题的的算法，他们主要依靠把问题分割成更小更容易管理的模块的方法来实现。
一个通用的算法是Platt's Sequential Minimal Optimization（SMO）算法，他把问题分成了若干个在二维空间成可以被解析的子问题，这样避开了需要解决数值最优化问题的难度。
另一个研究就是用使用了牛顿迭代的内点法找到Karush–Kuhn–Tucker情况下原始度偶问题的解决方法。与那些解决一系列小问题不同的是，这项研究直接解决了整体部分。避开解决这个线性问题的过程离不开核矩阵，矩阵的低阶近似往往是内核中使用技巧。
应用
[*]用于文本和超文本的分类，在归纳和直推方法中都可以显著减少所需要的有类标的样本数。
[*]用于图像分类。实验结果显示：在经过三到四轮相关反馈之后，比起传统的查询优化方案，支持向量机能够取得明显更高的搜索准确度。
[*]用于医学中分类蛋白质，超过90%的化合物能够被正确分类。
[*]用于手写字体识别。
页:
[1]