SVM原理及在人脸识别中的应用

1、关于SVM及其应用的相关原理一、支持向量机介绍下面我简单介绍下何为小样本、非线性及高维模式识别小样本，并不是说样本的绝对数量少，实际上，对任何算法来说， 更多的样本几乎总是能带来更好的效果，而是说与问题的复杂度 比起来，SVM算法要求的样本数是相对比较少的。非线性，是指SVM擅长应付样本数据线性不可分的情况高维模式识别是指样本维数很高， 例如样本出现几万维，不用降 维处理，其他算法基本就没有能力应付了，SVM却可以，主要是因为SVM产生的分类器很简洁，用到的样本信息很少，使得即使样本 维数很高，也不会给存储和计算带来大麻烦。何为机器学习之后会介绍。支持向量机方法：下面我简单介绍下何为 VC维理

2、论和结构风险最小原理以期推广能 力所谓VC维是对函数类的一种度量，我们就简单的理解为问题的 复杂程度，VC维越高，一个问题就越复杂。（1）PPT 下一页在讲解结构风险最小原理，先介绍下风险，风险就是与真实解的 误差。我举个例子来说，我们不知道宇宙是如何诞生，就是不知道宇宙的真实模型， 如果知道真实的宇宙模型， 我们直接用真实模型就可 以了。既然不知道， 我们就根据一些现象假设认为宇宙诞生于 150亿 年前的一场大爆炸， 这个假设能够描述很多我们观察到的现象， 但它 与真实的宇宙模型之间还相差多少？谁也说不清， 因为我们压根就不 知道真实的宇宙模型到底是什么。这个差距我们就认为是风险经验风险就是

3、分类器在给定样本上的误差， 就是我们选择一个假 设之后，真实误差无从得知， 但我们可以用某些可以掌握的量来逼近 它。就是使用分类器在样本数据上的分类的结果与真实结果之间的差 值来表示。这个差值叫做经验风险。置信风险是分类器在未知文本上分类的结果的误差 。代表了我 们在多大程度上可以信任分类器在未知文本上分类的结果。很显然， 没有办法精确计算的， 因此只能给出一个估计的区间， 也使得整个误 差只能计算上界，而无法计算准确的值。结构风险就是经验风险与置信风险之和(2) PPT 下一页下面介绍下机器学习和推广能力机器学习就是对一种对问题真实模型的逼近 。机器学习分为传统 机器学习和统计机器学习 。传

4、统机器学习方法是把经验风险最小化作为努力的目标， 但后来 发现很多分类函数能够在样本集上轻易达到 100%的正确率，然而用 分类函数对未知样本分类时却一塌糊涂。 经验风险最小化原则适用的 大前提是经验风险要确实能够逼近真实风险才行， 但实际上能逼近么？ 答案是不能，因为样本数相对于现实世界要分类的文本数来说简直九 牛一毛，经验风险最小化原则只在这占很小比例的样本上做到没有误 差，当然不能保证在更大比例的真实文本上也没有误差。 所以传统的 机器学习基本上属于摸着石头过河， 用传统的机器学习方法构造分类 系统完全成了一种技巧， 一个人做的结果可能很好， 另一个人差不多 的方法做出来却很差，缺乏指导

5、和原则。统计统计机器学习目标是从经验风险最小化变为了寻求经验风险 与置信风险的和最小而推广能力就是，用已知样本得到的一个分类器，在其他未知样 本分类时候也能获得很好的正确率。（3）PPT 下一页 SVM 基础大家可以看上图，我们要区分C1和C2这两类，红色的曲线可以 区分出来，但是用线性函数进行区分是最简单也很有效的 . 我将用一 个二维空间里仅有两类样本的分类问题来举例，来说明 SVM 的形成 思路与核心概念何为线性可分与线性不可分 ，Ci和C2是要区分的两个类别，如 图所示。中间的直线就是一个分类函数， 它可以将两类样本完全分开。 一般的，如果一个线性函数能够将样本完全正确的分开， 就称这

6、些数 据是线性可分的，否则称为非线性可分的。线性函数在一维空间里就是一个点， 在二维空间里就是一条直线， 三维空间里就是一个平面，如此想象下去，如果不关注空间的维数， 这种线性函数一个统一的名称即为超平面下面我们要区分 C1， C2 可以得到得到一个线性函数 g(x)=wx+b如取阈值为0,当有一个样本Xi需要判别的时候。若g(Xi)0,就判别 为类别Ci，若g(Xi)0 ，而 yi=1 也大于 0；若不属于该类别的话，那么 wxi+b 1 (i=1,Q)(5 是总的样本数)这样我们的两类样本分类问题也被我们转化成了它的数学形式， 一个带约束的最小值的问题：(7) PPT 下一页几何间隔告诉了

7、我们如何在 g(x)=wx+b 中选择一个最好的。 但是 我们还要知道如何求出一个 g(x)=wx+b 。后面这个为内积形式求这样的g(x)的过程就是求w (个n维向量)和b (个实数) 两个参数的过程，但实际上只需要求w,求得以后找某些样本点代入 就可以求得b。因此在求g(x)的时候，w才是变量。一旦求出了 w， 那么中间的直线H就知道了，因为它就是 wx+b=0，H，H1，H2平 行，间隔则H1和H2可以求的。那么 w 是谁决定的？显然是你给的样本决定的，一旦你在空间中 给出了那些个样本点， 三条直线的位置实际上就唯一确定了， 因为我 们求的是最优的那三条，当然是唯一的样本确定了 w，用数

8、学的语言描述，就是 w可以表示为样本的某 种组合：W=aiXi+ 02X2+ aXn式子中的a是拉格朗日乘子，而Xi是样本点，是向量，n就是总 样本点的个数。但是（1）式还不够好， 并不能表示样本的全部信息， 我们看图， 如果把其中一个正样本点定为负样本点， 就是把一个圆形变为方形三 条直线都必须移动。这说明 w 不仅跟样本点的位置有关，还跟样本 的类别有关。因此用带有标记的 w 式子才完整w=aiyiXi+ ay2X2+ aynXn其中的yi就是第i个样本的标签，它等于1或者-1。（7） PPT 下一页我们来看这个 w 的等式，式的那一堆拉格朗日乘子中，只有很少 的一部分不等于0,不等于0才

9、对w起决定作用，这部分不等于0的 拉格朗日乘子后面所乘的样本点，都落在 H1 和 H2 上，也正是这部 分样本唯一的确定了分类函数,当然,更严格的说,这些样本的一部 分就可以确定,因为例如要确定 H1 这条直线,只需要两个点就可以, 即便有三五个都落在 H1 上面。这部分我们真正需要的样本点,就叫 做支持（撑）向量 ！形象的理解为, “撑”起了分界线的样本。将w用求和符号简写一下:g（x）表达式可以写为:ng(x) w,x b(ai yiXi),xbi 1nai yi Xj, x bi 1注意式子中x才是变量，也就是你要分类哪篇文档，就把该文档 的向量表示代入到x的位置，而所有的Xi统统都是已

10、知的样本。式 子中只有Xi和x是向量，所以可以表示为后面的式子。之所以表示为（1）式形式，是因为以这样的形式描述问题以后，我们的优化问题 少了很大一部分不等式约束。我们先不讨论这个等式如何求解， 先讲 解下支持向量机的最重要的部分一一核函数和松弛变量（7）PPT下一页一一核函数之前一直在讨论的线性分类器，只能对线性可分的样本做处理。如果提供的样本线性不可分，结果很简单，线性分类器的求解程序会 无限循环，永远也解不出来。这必然使得它的适用范围大大缩小，而 它的很多优点我们实在不原意放弃，怎么办呢？有，其思想很简单，还是用二维平面中的分类问题作例子。 左边的我们把横轴上红色部分里的所有点定为正类，

11、 两边的黑色部分里的点定为负类。 试问能找到 一个线性函数把两类正确分开么？在二维空间里的线性函数就是指 直线，显然找不到能将两者分开的直线。 我们可以找到一条曲线将二 者区分开，通过判断点在这条曲线的上方还是下方就可以判断点所属 的类别。得到曲线为 g(x) c0 c1x c2x2 ，问题只是它不是一个线性函 y1 1a1 c0数，但是新建一个向量 y 和 a， y y2 x ,a a2 c1 ，然后把 y2 y3 xa3 c2和 a 分别回带一下，得到 g(x)=f(y)=ay 。在任意维度的空间中，这种 形式的函数都是一个线性函数，只不过其中的a和y都是多维向量罢 了。这样原来在二维空间

12、中一个线性不可分的问题， 映射到四维空间 后，变成了线性可分的！ 因此这也形成了我们最初想解决线性不可分 问题的基本思路 向高维空间转化，使其变得线性可分。( 7) PPT 下一页将低维空间线性不可分的映射到的高维空间的到的线性可分的线性函数为f(x)=+b其中：x是经由x变换来的，w是经由w变换来的计算高维空间向量x与向量w的内积，再把这个内积的值和 b相加，就得到了结果，看结果大于阈值还是小于阈值就得到了分类结果。但是X到x, W到w的映射关系很难找到。但是我们发现我们可以 只关心那个高维空间里 内积的值，如果内积值算出来了， 分类结果就 算出来了。这就让我们幻想，是否能有这样一种函数 K

13、(w,x), 他接受 低维空间的输入值，却能算出高维空间的内积值 ?如果 存在K(w,x),那么当给了一个低维空间数据，g(x)=K(w,x)+bf(x)=+b这两个函数的计算结果就完全一样， 我们可直接拿低维的输入往 g(x)里面代就可以了。万幸的是，这样的 K(w,x)确实存在，它被称作 核函数 ，而且还不止一个。( 8) PPT 下一页核函数的基本作用就是接受两个低维空间里的向量， 能够计算出经过某个变换后在高维空间里的向量内积值。 之前我们经过化简得到nxi,xI一个线性表示 g(x )ai yii1现在这个就是高维空间里的线性函数， 我们就可以用一个低维空 间里的函数来代替， 之前有

14、介绍核函数是输入低纬数据之间计算出高 维空间的内积值得到，低纬空间的代替函数呂 CO = XayKa“亦 + b2=1可以看到g(x 和g(x)里的a, y, b全都是一样的！这就是说， 尽管给的问题是线性不可分的，但是我们就硬当它是线性问题来求解, 只不过求解过程中，凡是要求内积的时候就用你选定的核函数来算。 这样求出来的a再和你选定的核函数一组合，就得到分类器。PPT下一页根据上面的核函数介绍会想到下面两个问题1. 既然有很多的核函数，针对具体问题该怎么选择？2. 如果使用核函数向高维空间映射后，问题仍然是线性不可分 的，那怎么办？第一个，对核函数的选择，现在还缺乏指导原则！各种实验的观

15、察结果表明，某些问题用某些核函数效果很好，用另一些就很差，但 是一般来讲，径向基核函数是不会出太大偏差的一种，首选。这里我 们不讨论径向基核函数具体实现形式是什么样子，只要知道他是一个 较好实现输入低维空间数据得到高维空间内积的函数。第二个问题的解决则引出了我们下一节的主题：松弛变量。(10) PPT 下一页女口图所示，在分类过程中出现图中情况，就是图中黄色那个点，它是方形的，因而它是负类的一个样本，这单独的一个样本，使得原 本线性可分的问题变成了线性不可分的。以我们人类的常识来判断，说有一万个点都符合某种线性可分的 规律，有一个点不符合，其实我们会觉得，这个样本点压根就是错误， 是噪声，而不

16、是我们分类方法有问题。所以我们会简单的忽略这个样 本点，仍然使用原来的分类器，其效果丝毫不受影响。为了使我们的约束条件也有这种对噪声的容错性，我们将原来的约束条件右边的阈值1增加一个松弛变量，如下：yi（wxi） b 1 i （i 1,2, ,nXn 是总的样本数）j 0因为松弛变量是非负的，因此最终的结果是要求间隔可以比1小。但是当某些点出现这种间隔比1小的情况时（这些点也叫离群点）， 意味着我们放弃了对这些点的精确分类，而这对我们的分类器来说是 种损失。但是放弃这些点也带来了好处，那就是使分类面不必向这些 点的方向移动，因而可以得到更大的几何间隔。显然我们必须权衡这种损失和好处。回顾下我们

17、原始的优化问题mF。-|iv|2solyecito耳（眄十切12 0子1乂 &样本数）llw| 2就是我们的目标函数，希望它越小越好，我们引入松弛变量带来 的损失就必然是一个能使之变大的量， 能使它变小就不叫损失了，因 为我们本来就希望目标函数值越小越好。（11） PPT 下一页我们如何来衡量松弛变量给目标函数带来的损失呢？常用kesai平方求和或者kesai求和来衡量，n为样本数目，这两个没有本质区 别。如果选择了（ 1）式，得到的方法的就叫做二阶软间隔分类器，（2）式就叫做一阶软间隔分类器。我先解释下什么叫软间隔，我们看约束条件右边是我们给的一个固定的阈值1，我们称这个为 硬间隔”分类法，

18、因为他硬性的要求所有样本点都满足和分类平 面间的距离必须大于某个值。而带有松弛变量的（2）式，就属于软间隔分类方法PPT下一页把损失加入到目标函数里的时候，就需要一个 惩罚因子Ci，原来的优化问题就变成了下面这样：minan2|w2 Cii2i 1subjecttoyi(wxib)1 i (i1,2,., n)(n是总的样本数)i0对这个式子有这么几点要注意:是并非所有的样本点都有一个松弛变量与其对应。 实际上只有“离群点 ”才有，或者也可以这么看，所有没离群的点松弛变量都等于 0。二是松弛变量的值实际上标示出了对应的点到底离群有多远， 值 越大，点就越远。三是惩罚因子 Ci 决定了你有多重视

19、离群点带来的损失，显然当 所有离群点的松弛变量的和一定时，你定的 C 越大，对目标函数的 损失也越大， 此时就暗示着你非常不愿意放弃这些离群点， 最极端的 情况是你把 C 定为无限大，这样只要稍有一个点离群，目标函数的 值马上变成无限大，马上让问题变成无解， 这就退化成了硬间隔问题。四是惩罚因子C不是一个变量，整个优化问题在解的时候，C是 一个你必须事先指定的值，指定这个值以后，解一下，得到一个分类 器，然后用测试数据看看结果怎么样， 如果不够好， 换一个 C 的值， 再解一次优化问题，得到另一个分类器，再看看效果，如此就是一个 参数寻优的过程。至此一个比较完整的支持向量机框架就有了， 简单说

20、来， 支持向 量机就是使用了核函数的软间隔线性分类法。最后，我要说的是，虽然我是以两类样本进行分类来介 绍 SVM 的原理，其实 SVM 是可以用到多类样本分类的。(11) PPT下一页一一总结最后，我来总结下我所讲我们的问题是要想办法分类 C1, C2。因为线性分类器最简单最 高效，所以我们用线性函数对其分类，但是，有很多线性函数，我们利用几何间隔选取最优的线性函数如果C1, C2不是线性可分的。我们利用核函数将 2维的数据转 换为更高维空间，使其变成线性可分数据。如果出现少量离群点导致数据不可分，我们利用松弛变量将离群 点舍去使得数据再次变成线性可分的(11) PPT 下一页下面我们来讲解下支持向量机的应用， 因为已经理解支持向量机 是一种线性分类方法。 辨别图片以区别人脸和猴脸为例说明下支持向 量机在其中的应用。比如我们有 100张人脸照片用 A 表示和 100张