1、Support Vector Machine支持向量机 内容nSVM简介n线性分类器n核函数n松弛变量nLIBSVM介绍n实验SVM简介n支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。SVM简介n支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广
2、能力（或称泛化能力）。SVM简介nVC维：所谓VC维是对函数类的一种度量，可以简单的理解为问题的复杂程度，VC维越高，一个问题就越复杂。正是因为SVM关注的是VC维，后面我们可以看到，SVM解决问题的时候，和样本的维数是无关的（甚至样本是上万维的都可以，这使得SVM很适合用来解决像文本分类这样的问题，当然，有这样的能力也因为引入了核函数）。SVM简介n结构风险最小原理：结构风险最小原理：就是追求“经验风险”与“置信风险”的和和最小。SVM简介n风险：风险：机器学习本质上就是一种对问题真实模型的逼近（我们选择一个我们认为比较好的近似模型，这个近似模型就叫做一个假设），但毫无疑问，真实模型一定是不
3、知道的。既然真实模型不知道，那么我们选择的假设与问题真实解之间究竟有多大差距，我们就没法得知。这个与问题真实解之间的误差，就叫做风险（更严格的说，误差的累积叫做风险）。SVM简介n经验风险经验风险Remp(w)：我们选择了一个假设之后（更直观点说，我们得到了一个分类器以后），真实误差无从得知，但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分类器在样本数据上的分类的结果与真实结果（因为样本是已经标注过的数据，是准确的数据）之间的差值来表示。这个差值叫做经验风险Remp(w)。SVM简介 以前的一些机器学习方法把经验风险最小化作为努力的目标，但后来发现很多分类函数能够在样本集上轻易达到
4、100%的正确率，在真实分类时却不好（即所谓的推广能力差，或泛化能力差）。此时的情况是因为选择了一个足够复杂的分类函数（它的VC维很高），能够精确的记住每一个样本，但对样本之外的数据一律分类错误。因为经验风险最小化原则适用的大前提是经验风险要确实能够逼近真实风险才行。但实际上不太可能，经验风险最小化原则只在这占很小比例的样本上做到没有误差，不能保证在更大比例的真实文本上也没有误差。SVM简介n泛化误差界：泛化误差界：为了解决刚才的问题，统计学提出了泛化误差界的概念。就是指真实风险应该由两部分内容刻画，一是经验风险经验风险，代表了分类器在给定样本上的误差；二是置信风险置信风险，代表了我们在多大程
5、度上可以信任分类器在未知样本上分类的结果。很显然，第二部分是没有办法精确计算的，因此只能给出一个估计的区间，也使得整个误差只能计算上界，而无法计算准确的值（所以叫做泛化误差界，而不叫泛化误差）。SVM简介n置信风险：置信风险：与两个量有关，一是样本数量，显然给定的样本数量越大，我们的学习结果越有可能正确，此时置信风险越小；二是分类函数的VC维，显然VC维越大，推广能力越差，置信风险会变大。SVM简介n泛化误差界的公式为：泛化误差界的公式为：R(w)Remp(w)+(n/h)公式中R(w)就是真实风险，Remp(w)表示经验风险，(n/h)表示置信风险。此时目标就从经验风险最小化变为了寻求经验风
6、险与置信风险的和最小，即结构风险最小。SVM简介n小样本：小样本：并不是说样本的绝对数量少（实际上，对任何算法来说，更多的样本几乎总是能带来更好的效果），而是说与问题的复杂度比起来，SVM算法要求的样本数是相对比较少的。SVM简介n非线性：非线性：是指SVM擅长应付样本数据线性不可分的情况，主要通过松弛变量（也叫惩罚变量）和核函数技术来实现，这一部分是SVM的核心内容，后面会详细说明。SVM简介n高维模式识别：高维模式识别：是指样本维数很高，SVM也可以应付。这主要是因为SVM 产生的分类器很简洁，用到的样本信息很少（仅仅用到那些称之为“支持向量”的样本），使得即使样本维数很高，也不会给存储和
7、计算带来大麻烦。线性分类器 n线性分类器：线性分类器：一定意义上，也可以叫做感知机，是最简单也很有效的分类器形式。在一个线性分类器中，可以看到SVM形成的思路，并接触很多SVM的核心概念。下面举例说明。线性分类器n用一个二维空间里仅有两类样本的分类问题来举例子。如图所示：C1和C2是要区分的两个类别。中间的直线就是一个分类函数，它可以将两类样本完全分开。一般的，如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性可分的。线性分类器n线性函数 在一维空间里就是一个点，在二维空间里就是一条直线，三维空间里就是一个平面，可以如此想象下去，如果不关注空间的维数，这种线性函
8、数还有一个统一的名称超平面（Hyper Plane）。线性分类器n例如我们有一个线性函数 g(x)=wx+b 我们可以取阈值为0，这样当有一个样本xi需要判别的时候，我们就看g(xi)的值。若g(xi)0，就判别为类别C1，若g(xi)0，而yi也大于0；若不属于该类别的话，那么wxi+b0，而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的距离。线
9、性分类器|w|叫做向量w的范数，范数是对向量长度的一种度量。我们常说的向量长度其实指的是它的2-范数，范数最一般的表示形式为p-范数，可以写成如下表达式 向量w=(w1,w2,w3,wn)它的p-范数为：当我们不指明p的时候，就意味着我们不关心p的值，用几范数都可以。当用归一化的w和b代替原值之后的间隔有一个专门的名称，叫几何间隔，表示的是点到超平面的欧氏距离。线性分类器 下面这张图直观的展示出了几何间隔的现实含义：H是分类面，而H1和H2是平行于H，且过离H最近的两类样本的直线，H1与H，H2与H之间的距离就是几何间隔。线性分类器 之所以如此关心几何间隔这个东西，是因为几何间隔与样本的误分次
10、数间存在关系：其中的是样本集合到分类面的几何间隔，R=max|xi|i=1,.,n，即R是所有样本中向量长度最长的值（也就是说代表样本的分布有多么广）。误分次数一定程度上代表分类器的误差。而从上式可以看出，在样本已知的情况下，误分次数的上界由几何间隔决定！几何间隔越大的解，它的误差上界越小。因此最大化几何间隔成了训练阶段的目标。线性分类器间隔：=y(wx+b)=|g(x)|几何间隔：可以看出=|w|几何。几何间隔与|w|是成反比的，因此最大化几何间隔与最小化|w|完全是一回事。而我们常用的方法并不是固定|w|的大小而寻求最大几何间隔，而是把所有样本点中间隔最小的那一点的间隔固定（例如固定为1）
11、，寻找最小的|w|。线性分类器 如果直接来解这个求最小值问题，当|w|=0的时候就得到了目标函数的最小值。但是无论给什么样的数据，都是这个解！反映在图中，就是H1与H2两条直线间的距离无限大，这个时候，所有的样本点都跑到了H1和H2中间，进入了无法分类的灰色地带。造成这种结果的原因是在描述问题的时候只考虑了目标，而没有加入约束条件。线性分类器 之前把所有样本点中间隔最小的那一点的间隔定为1，这就相当于让下面的式子总是成立：yi(wxi)+b1(i=1,2,l)（l是总的样本数）即：yi(wxi)+b-10(i=1,2,l)（l是总的样本数）因此我们的两类分类问题也被我们转化成了它的数学形式，一
12、个带约束的最小值的问题：线性分类器 从最一般的定义上说，一个求最小值的问题就是一个优化问题（也叫规划），它同样由两部分组成，目标函数和约束条件，可以用下面的式子表示：约束条件用函数c来表示，就是constrain的意思。一共有p+q个约束条件，其中p个是不等式约束，q个等式约束。线性分类器 这个式子中的x是自变量，但不限定它的维数必须为1（视乎你解决的问题空间维数）。要求f(x)在哪一点上取得最小值，但不是在整个空间里找，而是在约束条件所划定的可行域里找。注意可行域中的每一个点都要求满足所有p+q个条件，同时可行域边界上的点有一个额外好的特性，它们可以使不等式约束取得等号！而边界内的点不行。线
13、性分类器 这对一般的优化问题可能提供不了什么帮助，但对 SVM来说，边界上的点有其特殊意义，实际上是它们唯一决定了分类超平面，这些点（就是以前的图中恰好落在H1和H2上的点，在文本分类问题中，每一个点代表一个文档，因而这个点本身也是一个向量）就被称为支持向量。线性分类器 回头再看线性分类器问题的描述：在这个问题中，自变量就是w，目标函数是w的二次函数，所有的约束条件都是w的线性函数（不要把xi当成变量，它代表样本，是已知的），这种规划问题也叫做二次规划（Quadratic Programming，QP）。而且，由于它的可行域是一个凸集，因此它是一个凸二次规划。凸二次规划的优点在于它有全局最优解
14、。线性分类器 我们想求得这样一个线性函数（在n维空间中的线性函数）：g(x)=wx+b 求g(x)的过程就是求w（一个n维向量）和b（一个实数）两个参数的过程（但实际上只需要求w，求得以后找某些样本点代入就可以求得b）。因此在求g(x)的时候，w才是变量。线性分类器 样本确定了w，用数学的语言描述，就是w可以表示为样本的某种组合：w=1x1+2x2+nxn 式子中的i是一个一个的数（在严格的证明过程中，这些被称为拉格朗日乘子），而xi是样本点，因而是向量，n就是总样本点的个数。为了方便描述，以下开始严格区别数字与向量的乘积和向量间的乘积，用1x1表示数字和向量的乘积，而用表示向量x1,x2的内
15、积。因此g(x)的表达式严格的形式应该是：g(x)=+b线性分类器 但是上面的式子还不够好，如果我不动所有点的位置，而只是把其中一个正样本点定为负样本点（也就是把一个点的形状从圆形变为方形），那么三条直线都必须移动。这说明w不仅跟样本点的位置有关，还跟样本的类别有关因此用下面这个式子表示才算完整：w=1y1x1+2y2x2+nynxn 其中的yi就是第i个样本的标签，它等于1或者-1。其实以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于0（不等于0才对w起决定作用），这部分不等于0的拉格朗日乘子后面所乘的样本点，其实都落在H1和H2上，也正是这部分样本唯一的确定了分类函数。更严格的说，这
16、些样本的一部分就可以确定，因为例如确定一条直线，只需要两个点就可以。这部分样本点，就叫做支持（撑）向量！线性分类器 式子也可以用求和符号简写一下：因此原来的g(x)表达式可以写为：注意式子中x才是变量，如果要分类哪篇文档，就把该文档的向量表示代入到 x的位置，而所有的xi统统都是已知的样本。还注意到式子中只有xi和x是向量，因此一部分可以从内积符号中拿出来，得到g(x)的式子为：线性分类器 至此w不见了，从求w变成了求。看似没有简化问题，其实简化了原来的问题，因为以这样的形式描述问题以后，我们的优化了不等式约束。之后的求解就变得很容易了。下面遇到一个问题：如果提供的样本线性不可分，怎么办？所以
17、必须要提到SVM中比较重要的内容核函数。核函数 用一个二维平面中的分类问题作例子，如图：把横轴上端点a和b之间红色部分里的所有点定为正类，两边的黑色部分里的点定为负类。试问能找到一个线性函数把两类正确分开么？不能，因为二维空间里的线性函数就是指直线，显然找不到符合条件的直线。核函数 但我们可以找到一条曲线，例如下面这一条：显然通过点在这条曲线的上方还是下方就可以判断点所属的类别。这条曲线就是我们熟知的二次曲线，它的函数表达式是：核函数 问题只是它不是一个线性函数，但是，做一下变换，新建一个向量y和a：这样g(x)就可以转化为f(y)=核函数所以，需要这样一种函数K(w,x),他接受低维空间的输
18、入值，却能算出高维空间的内积值。也就是当给了一个低维空间的输入x以后：g(x)=K(w,x)+b f(x)=+b 这两个函数的计算结果就完全一样。核函数几个比较常用的核函数如下：核函数 接下来还有两个问题：1.既然有很多的核函数，针对具体问题该怎么选择？2.如果使用核函数向高维空间映射后，问题仍然是线性不可分的，那怎么办？核函数 在常用的核函数中，应用最广泛的是具有较好学习能力的RBF 核，无论低维、高维、小样本、大样本等情况，RBF 核均适应，具有较宽的收敛域，是较为理想的分类依据函数。Keerthi S S 等人证明了线性核和多项式核是RBF 核的特殊情况。Lin C J等说明了在某些参数情况下，Sigmoid 核同RBF 核具有相似的性能。
