(一) SVM八股简介
“支持向量机”(Support Vector Machine )最早由Cortes和Vapnik于1995年提出，它为解决小样本、非线性和高维模式识别提供了许多独特优势，还包括函数拟合等其他机器
支持向量机方法基于统计学习理论的VC维理论和结构风险最小原理，基于有限的样本信息在模型的复杂性(即特定训练样本的学习精度，Accuracy )和学习能力(即无错误地识别任意样本的能力)之间进行最大化
以上是有关SVM的学术文献中经常引用的介绍，略有出入。 试着一个个分解说明一下。
Vapnik是一只平时学习统计机器的小猫，当然，他出版的《Statistical Learning Theory》是一部完整阐述统计机器学习思想的名作。 这本书详细论述了统计机器学习不同于传统机器学习的本质在于统计机器学习能准确地提供学习效果，解决所需样本数等一系列问题。 与统计机器学习的精密思考相比，传统的机器学习基本上属于摸着石头过河。 用传统的机器学习方法建立分类系统完全是一项技术。 一个人做的结果可能很好，但另一个人用同样的方法做不好，缺乏指导和原则。
VC维是相对于函数系的尺度，可以简单地理解为问题的复杂性。 VC维度越高，一个问题越复杂。 正因为SVM关注VC维，以后可以看到，SVM解决问题时，与样本的维数无关(样本可以是上万维)。 这适用于SVM解决文本分类问题。 当然，有这种能力也是因为引入了核函数)。
结构风险最小，其实就是以下情况。
机器学习本质上是对问题实际模型的近似，但实际模型肯定不知道(如果知道，为什么需要机器学习？ )。 用真实模型解决问题不就行了吗？ 是吧，哈哈)既然不知道实际模型，我们就不知道我们选择的假设和问题的真解之间有多少差距。 例如，他认为宇宙诞生于150亿年前的大爆炸。 这个假设可以描述我们观察到的许多现象，但与实际宇宙模型之间有多少差距？ 谁也说不清楚。 因为我们不知道真正的宇宙模型是什么。
与该问题的真正解的误差称为风险(更严格地说，误差的累积称为风险)。 我们选择假设后(更坦率地说，我们得到分类器后)，虽然不知道真正的误差，但我们可以掌握的量来逼近它。 最直观的想法是使用分类器在样本数据上的分类结果与实际结果(因为样本已经是标记的数据，并且是准确的数据)之间的差来表示。 这一差距称为经验风险remp(w )。 在传统的机器学习方法中，以最小化经验风险为努力目标，但发现在样本集中能够轻易达到100%正确率的分类函数在真正的分类中非常多(所谓普及能力低或者泛化能力低)。 在这种情况下，可以选择VC维度高且足够复杂的分类函数，并准确地存储各个样本，但是将样本以外的数据统一分类是错误的。 回顾经验风险最小化的原则，这个原则适用的大前提是经验风险确实接近实际风险，但能否接近实际。 答案是否定的。 之所以这么说，是因为样本数量相对于现实世界中分类的文本数量正好是九牛一毛，经验风险最小化的原则是只让占这一小部分比例的样本没有误差。 当然，不能保证更大比例的现实文本也没有误差。
统计学习为此，引入了泛化误差界的概念。 也就是说，真正的风险应该在两个部分描述，一个是经验风险，表示给定样本中分类器的误差。 二是信任风险，表示分类器对分类为未知文本的结果的信任程度。 很明显，由于第二部分不能正确计算，只能给出一个估计区间，整个误差只能计算上界，不能计算正确的值(因此，称为泛化误差界，不称为泛化误差)。
可靠性风险与两个量有关，一个是样本数，明显给定的样本数越大，我们的学习结果越有可能正确，此时可靠性风险小的第二个是分类函数的VC维，明显VC维越大，推广能力越低
泛化误差界的公式如下
(r(w )remp (w )(n/h ) ) ) ) ) ) ) ) 0
公式中的r(w )为真实风险，Remp(w )为经验性风险，(n/h )为可靠风险。 统计学习的目标从最小化经验风险转变为最小化经验风险和信任风险之和，即最小化结构风险。
SVM正是这样一种用于将结构风险最小化的算法。
SVM的其他特点很容易理解。
较小的样本并不是样本的绝对数量少(实际上，更多的样本在任何算法中几乎总是能带来更好的效果)，而是与问题的复杂性相比，SVM算法要求的样本数量
非线性是指样本数据的线性不可分割时SVM擅长的，主要通过松弛变量(也称为罚变量)和核函数技术来实现。 这一部分是SVM的精髓，稍后将详细讨论。 一句话，关于文本分类的问题到底是否是线性不可分的，还没有定论，所以不能简单地认为是线性不可分而简化，只能在落石之前认为是线性不可分的(总之，线性不可分只是线性不可分的特例)
高维模式识别意味着样本的维数高，例如文本的向量表示可以是另一系列文章(
本分类入门》）中提到过的降维处理，出现几万维的情况很正常，其他算法基本就没有能力应付了，SVM却可以，主要是因为SVM 产生的分类器很简洁，用到的样本信息很少（仅仅用到那些称之为“支持向量”的样本，此为后话），使得即使样本维数很高，也不会给存储和计算带来大麻烦（相对照而言，kNN算法在分类时就要用到所有样本，样本数巨大，每个样本维数再一高，这日子就没法过了……）。下一节开始正式讨论SVM。别嫌我说得太详细哦。
SVM入门（二）线性分类器Part 1
线性分类器(一定意义上,也可以叫做感知机) 是最简单也很有效的分类器形式.在一个线性分类器中,可以看到SVM形成的思路,并接触很多SVM的核心概念.
用一个二维空间里仅有两类样本的分类问题来举个小例子。如图所示
C1和C2是要区分的两个类别，在二维平面中它们的样本如上图所示。中间的直线就是一个分类函数，它可以将两类样本完全分开。一般的，如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性可分的。
什么叫线性函数呢？在一维空间里就是一个点，在二维空间里就是一条直线，三维空间里就是一个平面，可以如此想象下去，如果不关注空间的维数，这种线性函数还有一个统一的名称——超平面（Hyper Plane）！
实际上，一个线性函数是一个实值函数（即函数的值是连续的实数），而我们的分类问题（例如这里的二元分类问题——回答一个样本属于还是不属于一个类别的问题）需要离散的输出值，例如用1表示某个样本属于类别C1，而用0表示不属于（不属于C1也就意味着属于C2），这时候只需要简单的在实值函数的基础上附加一个阈值即可，通过分类函数执行时得到的值大于还是小于这个阈值来确定类别归属。 例如我们有一个线性函数
g(x)=wx+b
我们可以取阈值为0，这样当有一个样本xi需要判别的时候，我们就看g(xi)的值。若g(xi)>0，就判别为类别C1，若g(xi)<0，则判别为类别C2（等于的时候我们就拒绝判断，呵呵）。此时也等价于给函数g(x)附加一个符号函数sgn()，即f(x)=sgn [g(x)]是我们真正的判别函数。
关于g(x)=wx+b这个表达式要注意三点：一，式中的x不是二维坐标系中的横轴，而是样本的向量表示，例如一个样本点的坐标是(3,8)，则xT=(3,8) ，而不是x=3（一般说向量都是说列向量，因此以行向量形式来表示时，就加上转置）。二，这个形式并不局限于二维的情况，在n维空间中仍然可以使用这个表达式，只是式中的w成为了n维向量（在二维的这个例子中，w是二维向量，为了表示起来方便简洁，以下均不区别列向量和它的转置，聪明的读者一看便知）；三，g(x)不是中间那条直线的表达式，中间那条直线的表达式是g(x)=0，即wx+b=0，我们也把这个函数叫做分类面。
实际上很容易看出来，中间那条分界线并不是唯一的，我们把它稍微旋转一下，只要不把两类数据分错，仍然可以达到上面说的效果，稍微平移一下，也可以。此时就牵涉到一个问题，对同一个问题存在多个分类函数的时候，哪一个函数更好呢？显然必须要先找一个指标来量化“好”的程度，通常使用的都是叫做“分类间隔”的指标。下一节我们就仔细说说分类间隔，也补一补相关的数学知识。
SVM入门（三）线性分类器Part 2
上回说到对于文本分类这样的不适定问题（有一个以上解的问题称为不适定问题），需要有一个指标来衡量解决方案（即我们通过训练建立的分类模型）的好坏，而分类间隔是一个比较好的指标。
在进行文本分类的时候，我们可以让计算机这样来看待我们提供给它的训练样本，每一个样本由一个向量（就是那些文本特征所组成的向量）和一个标记（标示出这个样本属于哪个类别）组成。如下：
Di=(xi,yi)
xi就是文本向量（维数很高），yi就是分类标记。
在二元的线性分类中，这个表示分类的标记只有两个值，1和-1（用来表示属于还是不属于这个类）。有了这种表示法，我们就可以定义一个样本点到某个超平面的间隔：
δi=yi(wxi+b)
这个公式乍一看没什么神秘的，也说不出什么道理，只是个定义而已，但我们做做变换，就能看出一些有意思的东西。
首先注意到如果某个样本属于该类别的话，那么wxi+b>0（记得么？这是因为我们所选的g(x)=wx+b就通过大于0还是小于0来判断分类），而yi也大于0；若不属于该类别的话，那么wxi+b<0，而yi也小于0，这意味着yi(wxi+b)总是大于0的，而且它的值就等于|wxi+b|！（也就是|g(xi)|）
现在把w和b进行一下归一化，即用w/||w||和b/||w||分别代替原来的w和b，那么间隔就可以写成
这个公式是不是看上去有点眼熟？没错，这不就是解析几何中点xi到直线g(x)=0的距离公式嘛！（推广一下，是到超平面g(x)=0的距离， g(x)=0就是上节中提到的分类超平面）
小Tips：||w||是什么符号？||w||叫做向量w的范数，范数是对向量长度的一种度量。我们常说的向量长度其实指的是它的2-范数，范数最一般的表示形式为p-范数，可以写成如下表达式
向量w=(w1, w2, w3,…… wn)
它的p-范数为
看看把p换成2的时候，不就是传统的向量长度么？当我们不指明p的时候，就像||w||这样使用时，就意味着我们不关心p的值，用几范数都可以；或者上文已经提到了p的值，为了叙述方便不再重复指明。
当用归一化的w和b代替原值之后的间隔有一个专门的名称，叫做几何间隔，几何间隔所表示的正是点到超平面的俏皮的大象距离，我们下面就简称几何间隔为“距离”。以上是单个点到某个超平面的距离（就是间隔，后面不再区别这两个词）定义，同样可以定义一个点的集合（就是一组样本）到某个超平面的距离为此集合中离超平面最近的点的距离。下面这张图更加直观的展示出了几何间隔的现实含义：
H是分类面，而H1和H2是平行于H，且过离H最近的两类样本的直线，H1与H，H2与H之间的距离就是几何间隔。
之所以如此关心几何间隔这个东西，是因为几何间隔与样本的误分次数间存在关系：
其中的δ是样本集合到分类面的间隔，R=max ||xi|| i=1,...,n，即R是所有样本中（xi是以向量表示的第i个样本）向量长度最长的值（也就是说代表样本的分布有多么广）。先不必追究误分次数的具体定义和推导过程，只要记得这个误分次数一定程度上代表分类器的误差。而从上式可以看出，误分次数的上界由几何间隔决定！（当然，是样本已知的时候）
至此我们就明白为何要选择几何间隔来作为评价一个解优劣的指标了，原来几何间隔越大的解，它的误差上界越小。因此最大化几何间隔成了我们训练阶段的目标，而且，与二把刀作者所写的不同，最大化分类间隔并不是SVM的专利，而是早在线性分类时期就已有的思想。
下一节讲解线性分类器的求解问题
转载自http://www.blogjava.net/zhenandaci/category/31868.html