第8章-支持向量机课件.ppt

1、第八章 支持向量机 n支持向量机SVM(Support Vector Machines)是由Vanpik领导的AT&T Bell实验室研究小组在1963年提出的一种新的非常有潜力的分类技术，SVM是一种基于统计学习理论的模式识别方法，主要应用于模式识别领域。n发展：90年代，由于统计学习理论的实现和神经网络等较新兴的机器学习方法的研究遇到一些重要的困难，如，如何确定网络结构的问题、过学习与欠学习问题、局部极小点问题等，使得SVM迅速发展和完善。nSVM优势：小样本、非线性及高维模式识别问题，函数拟合等其他机器学习问题n运用:模式识别、回归分析、函数估计、时间序列预测等领域，文本识别、手写字体识

2、别、人脸图像识别、基因分类、时间序列预测等。第八章 支持向量机 n8.1 概述概述n8.2 统计学习理论统计学习理论 n8.3 支持向量机（支持向量机（SVM）n8.4 核函数核函数n8.5 SVM的算法及多类的算法及多类SVMn8.6 SVM的应用现状的应用现状n8.7 小结小结8.1 概述概述n基于数据的机器学习：从观测数据(样本)出发寻找数据中的模式和数据中的函数依赖规律，利用这些模式和函数依赖对未来数据或无法观测的数据进行分类、识别和预测。n分为三种：n一、经典的(参数)统计估计算法-参数的相关形式是已知的，训练样本用来估计参数的值。局限性:1.需要已知样本分布形式，2.假设样本数目趋

3、于无穷大，但在实际问题中，样本数往往是有限的。n二、人工神经网络(ANN)-利用已知样本建立非线性模型，克服了传统参数估计方法的困难。应用广泛，但是现在的神经网络技术研究理论基石不足，有较大的经验成分，在技术上仍存在一些不易解决的问题。n三、支持向量机(SVM)，统计学习理论。SVM是统计学习理论中最年轻的内容，也是最实用的部分，已经成为神经网络和机器学习的研究热点之一。支持向量机的基本思想支持向量机的基本思想n训练数据集非线性地映射到一个高维特征空间n目的：把在输入空间中的线性不可分数据集映射到高维特征空间后变为是线性可分的数据集n在特征空间建立一个具有最大隔离距离的最优分隔超平面 n存在多

4、个分类超平面可以把两个类分离开来，但是只有一个是最优分类超平面，它与两个类之间最近向量的距离最大。n支持向量机的目的：找出最优的分类超平面。8.2 统计学习理论统计学习理论n统计学习理论诞生于20世纪6070年代，主要创立者:Vladimir N.Vapnik，90年代中期发展比较成熟，受到世界机器学习界的广泛重视。n统计学习理论：一种专门研究小样本情况下机器学习规律的理论。针对小样本统计问题建立了一套新的理论体系，该体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有限信息的条件下得到最优结果。8.2.1 学习问题的表示学习问题的表示n样本学习的一般模型n产生器(G)：产生随机向

5、量，它们是从固定但未知的概率分布函数F(x)中独立抽取的。n训练器(S)：对每个输入向量x返回一个输出值y，产生输出的根据是同样固定但未知的条件分布函数F(y|x)。n学习机器(LM)：它能够实现一定的函数集，其中是参数集合。n在学习过程中，学习机器LM观察数据对(x,y)。在训练之后，学习机器必须对任意输入x，使之接近训练器的响应y。8.2.2 期望风险和经验风险期望风险和经验风险n给定输入x下训练器响应y与学习机器给出的响应 之间的损失记作n 就是风险泛函，即预测的期望(实际)风险。n 称为经验风险。),(axf),(,(axfyL),(),(,()(yxdFaxfyLaRliiiempa

6、xfyLlaR1),(1)(8.3 支持向量机（支持向量机（SVM）n一种经典的二分类模型，基本模型定义为特征空间中最大间隔的线性分类器，其学习的优化目标便是间隔最大化，因此支持向量机本身可以转化为一个凸二次规划求解的问题。函数间隔与几何间隔函数间隔与几何间隔n对于二分类学习，假设数据是线性可分的n分类学习：找到一个合适的超平面，该超平面能够将不同类别的样本分开n类似二维平面使用ax+by+c=0来表示，超平面实际上表示的就是高维的平面，如下图所示：8.3.1 线性可分支持向量机线性可分支持向量机n划分超平面：n其中，为法向量。n样本空间中任意点x到超平面(w,b)的距离写为：0bxwTwbx

7、wrT|dwwww,218.3.1 线性可分支持向量机线性可分支持向量机n假设超平面能正确分类，则：n两个异类支持向量到超平面的距离之和为：1,11,1iiTiiTybxwybxww28.3.1 线性可分支持向量机线性可分支持向量机n欲找最大间隔的划分超平面，即找满足约束的参数w,b使得 最大，即：mibxwytsiTi,2,1,1)(.wbw2max,8.3.1 线性可分支持向量机线性可分支持向量机n等价于：mibxwytsiTi,2,1,1)(.2,21minwbw0*bxw)()(*bxwsignxf8.3.1 对偶问题对偶问题Niiiyts10.NiNjNiijijijixxyy111

8、)(21minNiCi,2,1,0n支持向量机问题可以等价为求解下面的二次规划问题：最小化泛函：约束条件为不等式类型 该问题的解是由下面的拉格朗日泛函的鞍点给出的：其中 为拉格朗日乘子。问题的对偶问题为：最大化泛函约束条件为：这样原问题的解为：)(21)(www libwxyii,2,1,1)(1)()(21),(1bwxyawwabwLiiliiia)(21)(1,1jijijljiiliixxyyaaaaWliai,2,1,0 01iliiyaiiliixayw1n由拉格朗日可得到原问题的Karush-Kuhn-Tucker(KKT)条件：n根据优化理论，是原问题的解当且仅当 满足KKT条

9、件。n在对偶问题或KKT条件中，每个训练数据 都对应一个拉格朗日乘子 ，其中与 对应的数据成为支持向量。0wL 0bLlibwxyii,2,1,01)(liai,2,1,0 libwxyaiii,2,1,01)(),(bw),(abwix0ia0ian利用任一支持向量和利用任一支持向量和KKT条件条件 ，可求出，可求出 一般情况下，为了准确，常求出多个一般情况下，为了准确，常求出多个b值，然后取平均值，或者值，然后取平均值，或者 其中，用其中，用 表示属于第一类的任一支持向量，用表示属于第一类的任一支持向量，用 表示属表示属于第二类的任一支持向量。于第二类的任一支持向量。最后的最优超平面方程：

10、最后的最优超平面方程：最终完成学习过程。最终完成学习过程。01)(bwxyaiii iiyxwb)()1()1(21*xwxwb)1(*x)1(*x0bxxayiiSVxii=+).(8.3.2 线性不可分与软间隔最大化线性不可分与软间隔最大化n首先我们引入松弛变量首先我们引入松弛变量 来表示经验风险，将原约束条件变为：来表示经验风险，将原约束条件变为：这样，样本数据的经验风险在一定程度上可以表示为：这样，样本数据的经验风险在一定程度上可以表示为：其中其中 参数，代表经验风险的某种度量方式。参数，代表经验风险的某种度量方式。n给定样本数据给定样本数据 后，我们在容许结构的某个子集下最小后，我们

11、在容许结构的某个子集下最小化经验风险，问题可以描述为：化经验风险，问题可以描述为：最小化泛函：最小化泛函：约束条件为：约束条件为：libwxyiii,2,1,1)(liiF1)(0lzzz,21 liiF1)(iiibwxy1)(kcww)(n这个问题可以等价为在约束条件下最小化泛函：这个问题可以等价为在约束条件下最小化泛函：这里的这里的C是一个给定的值。是一个给定的值。n原问题的对偶形式为：原问题的对偶形式为：n只是约束条件变为：只是约束条件变为：n这样原问题的解为：这样原问题的解为：)().(21),(1liiCwww).(21)(1,1jijijljiiliixxyyaaaaWliCai

12、,2,1,0 01iliiyaiiliixayw18.4 核函数核函数n支持向量机的关键在于核函数。n低维空间向量集通常难于划分，解决的方法是将它们映射到高维空间，但这个办法带来的困难就是计算复杂度的增加，而核函数正好巧妙地解决了这个问题。n只要选用适当的核函数，我们就可以得到高维空间的分类函数。n在SVM理论中，采用不同的核函数将导致不同的SVM算法。8.4 核函数核函数n首先定义映射 ，是输入空间，H是高维内积空间，称为特征空间，称为特征映射，然后在H中构造最优超平面。在特征空间中的学习过程同前面一样，对偶问题为：约束条件不变：HRd:dR)()(21)(1,1jijijljiiliixx

13、yyaaaaWliCai,2,1,0 01iliiya 核函数的思想：在输入空间的变量直接计算特征空间中的内积，即 其中 ，属于输入空间，函数 即为核函数。这样，只要定义了核函数，就不必真的进行非线性变换，更没有必要知道采用的非线性变换的形式，所以我们只要构造输入空间的一个核函数即可。),()()(xxkxx xx),(xxk核函数：核函数：n定理定理 8.6 对于任意的对称函数 ，它是某个特征空间的内积运算的充分必要条件是，对于任意的 且 ，有 事实上这一条件并不难满足。这样我们就可以得到输入空间中的非线性决策函数 它等价于在高维特征空间中的线性决策函数。),(xxk)0(xdxx)(20)

14、()(),(xdxdxxxxK),(sgn()(bxxKayxfiiSVi8.4.2 核函数的分类核函数的分类n多项式核函数多项式核函数 所得到的是阶多项式分类器：所得到的是阶多项式分类器：n径向基函数径向基函数 经典的径向基函数的判别函数为：经典的径向基函数的判别函数为：最通常采用的核函数为高斯函数：最通常采用的核函数为高斯函数：qiixxxxK1),(),()1(sgn(),(*bxxayaxfdiiSVi)|)(|sgn()(1bxxKaxfirnii22|)(|exp|)(|iirxxxxKn多层感知机 SVM采用Sigmoid函数作为内积，这时就实现了包含一个隐层的多层感知机，隐层节

15、点数目由算法自动确定。满足mercer条件的Sigmoid函数为：)(tanh(),(cxxvxxKjTiji8.5 SVM的算法及多类的算法及多类SVMn目前SVM的训练算法一般采用循环迭代解决对偶寻优问题：将原问题分解成为若干子问题，按照某种迭代策略，通过反复求解子问题，最终使结果收敛到原问题的最优解。根据子问题的划分和迭代策略的不同，大致可以分为：n块算法块算法Chunking Algorithm：考虑到去掉Lagrange乘子等于零的训练样本不会影响原问题的解，采用选择一部分样本构成工作样本集进行训练，剔除其中的非支持向量，并用训练结果对剩余样本进行检验，将不符合KKT条件的样本与此次

16、结果的支持向量合并成为一个新的工作样本集，然后重新训练，如此重复下去直到获得最优结果。nChunking算法将矩阵规模从训练样本数的平方减少到具有非零Lagrange乘数的样本数的平方，在很大程度上降低了训练过程对存储容量的要求。Chunking算法能够大大提高训练速度，尤其是当支持向量的数目远远小于训练样本的数目时。然而，如果支持向量个数比较多，随着算法迭代次数的增多，所选的块也会越来越大，算法的训练速度依旧会变得十分缓慢。n(2)分解算法分解算法(Decomposition Algorithm)分解算法最早由Osuna等人提出，是目前有效解决大规模问题的主要方法。分解算法将二次规划问题分解

17、成一系列规模较小的二次规划子问题，进行迭代求解。在每次迭代中，选取拉格朗日乘子分量的一个子集做为工作集，利用传统优化算法求解一个二次规划的子问题。该算法的关键在于选择一种最优的工作集选择算法，但是Osuna在工作集的选取中采用了随机的方法，因此限制了算法的收敛速度。Joachims在Osuna分解算法的基础上，关于工作集的选择做了重要改进。其主要思想是，如果存在不满足KTT条件的样本，利用最速下降法，在最速下降方向中存在 个样本，然后以这 个样本构成工作集，在此工作集上解决QP问题，直到所有样本满足KTT条件。Joachims的改进大幅度提高了分解算法的收敛速度，并且他利用这些方法实现了SVM

18、light算法。n 由John C.Platt提出的序列最小优化（Sequential Minimal Optimization,SMO）算法可以说是Osuna分解算法的一个特例，工作集中只有2个样本，其优点是针对2个样本的二次规划问题可以有解析解的形式，从而避免了多样本情况下的数值解不稳定及耗时问题，同时也不需要大的矩阵存储空间，特别适合稀疏样本。其工作集的选择不是传统的最陡下降法，而是启发式。通过两个嵌套的循环来寻找待优化的样本，然后在内环中选择另一个样本，完成一次优化，再循环，进行下一次优化，直到全部样本都满足最优条件。SMO算法主要耗时在最优条件的判断上，所以应寻找最合理即计算代价最低

19、的最优条件判别式。n(3)(3)增量学习增量学习 增量学习是机器学习系统在处理新增样本时，能够只对原学习结果中与新样本有关的部分进行增加修改或删除操作，与之无关的部分则不被触及。增量训练算法的一个突出特点是支持向量机的学习不是一次离线进行的，而是一个数据逐一加入反复优化的过程。新型SVMn（1 1）粒度支持向量机）粒度支持向量机GSVMGSVM GSVM由Tang Y C于2004年提出的，主要思想：通过常用的粒度划分方法构建粒度空间获得一系列信息粒，然后在每个信息粒上进行学习，最后通过聚合信息粒上的信息（或数据、规则知识、属性等）获得最终的支持向量机决策函数。这一学习机制通过数据的粒化可以将

20、一个线性不可分问题转化为一系列线性可分问题，从而获得多个决策函数；同时，这一学习机制也使得数据的泛化性能增强，即可在SVM的训练中得到间隔更宽的超平面。（2 2）模糊支持向量机）模糊支持向量机FSVMFSVMn为了克服噪声和野值点对支持向量机的影响，台湾学者Chunfu Lin和Shengde Wang将模糊数学和支持向量机相结合，提出了模糊支持向量机，主要用来处理训练样本中的噪声数据。n主要思想：针对支持向量机对训练样本内的噪音和孤立点的敏感性，在训练样本集中增加一项：隶属度，并赋予支持向量较高的隶属度，而非支持向量及噪声野值点赋予较小的隶属度，从而降低了非支持向量、噪声和野值点对最优超平面

21、的影响。（3 3）孪生支持向量机）孪生支持向量机TSVMsTSVMsn2007年，Jayadeva 和Khemchandani R提出了一种二值数据的分类器孪生支持向量机(又称双分界面支持向量机)nTWSVMs在形式上类似于传统的支持向量机，具有传统支持向量机的优点，且对大规模数据具有更好的处理能力。nTWSVMs为两个类各自得到一个分类平面，属于每个类的数据尽量围绕在与之相对应的分类平面周围，然后TWSVMs通过优化一对分类平面来构建分类超平面。即：TWSVMs解决一对QP问题，而SVM则是解决一个QP问题，但是在TWSVMs中，其中一个类的数据要作为另一个QP问题的约束条件，反之亦然。8.

22、5.2 多类问题中的多类问题中的SVMn 类模式识别问题是为 个样本 构成一个决策函数。由于SVM是解决两类问题的有效方法，因此用SVM解多类问题的方法通常将问题转化为两类问题，然后对结果进行处理。一般常用的方法有以下几种：One-against-the-rest方法：在第 类和其他 类之间构建超平面。One-against-one方法：为任意两个类构建超平面，共需 个 。K-class SVM：同时为所有的类构造一个分类超平面。klkyRxliyxiriii,2,1,2,1),(k1k2)1(KKsMSV8.6 SVM的应用现状的应用现状 人脸检测、验证和识别 Osuna最早将SVM应用于人

23、脸检测，并取得了较好的效果。其方法是直接训练非线性SVM分类器完成人脸与非人脸的分类。大量实验结果表 明这种方法不仅具有较高的检测率和较低的误检率，而且具有较快的速度。说话人/语音识别 建立SVM和HMM（隐式马尔可夫模型）的混合模型。HMM适合处理连续信号，而SVM适合于分类问题；HMM的结果反映了同类样本的相似度，而SVM的输出结果则体现了异类样本间的差异。8.6 SVM的应用现状的应用现状 文字/手写体识别 贝尔实验室对美国邮政手写数字库进行的实验，人工识别平均错误率为2.5%，专门针对该特定问题设计的5层神经网络错误率为5.1%（其中利用率大量先验知识），而用3种SVM方法（采用3种核

24、函数）得到的错误率分别为4.0%、4.1%和4.2%，且是直接采用1616的字符点阵作为输入，表明了SVM的优越性能。8.6 SVM的应用现状的应用现状 图像处理：a 图像过滤,支持向量机分类和最近邻方法校验的多层系图像处理框架，达到85%以上的准确率。b 视频字幕提取,首先将原始图像帧分割为NN的子块，提取每个子块的灰度特征；然后使用预先训练好的SVM分类机进行字幕子块和非字幕子块的分类；最后结合金字塔模型和后期处理过程，实现视频图像字幕区域的自动定位提取。c 图像分类和检索,以SVM为分类器，在每次反馈中对用户标记的正例和反例样本进行学习，并根据学习所得的模型进行检索，使用由9918幅图像

25、组成的图像库进行实验，结果表明，在有限训练样本情况下具有良好的泛化能力。8.6 SVM的应用现状的应用现状 目前，国际上关于SVM理论的讨论和深入地研究逐渐广泛，我国国内在此领域的研究尚处在萌芽状态。我们需要及时学习掌握有关的理论知识，开展有效的研究工作，使我们在这个具有重要意义的领域中尽快赶上国际水平，跟上国际发展步伐。8.7 小结小结nSVM是基于统计学习理论中的经验风险最小化原则的一种机器学习，解决了对非线性函数求解超平面的问题。SVM可以有效地解决小样本、非线性及高维模式识别问题。nSVM用于模式分类的观点可以简单地阐述为：首先，无论问题是否为线性的，选择相应的核函数，均可将输入向量映射到一个高维空间；其次，用最优化理论方法寻求最优超平面将二类分开。n现在，统计学习理论和SVM方法尚处在发展阶段，很多方面还不完善，许多理论在算法中尚未实现；SVM算法的某些理论解释并非完美，SVM的应用目前仅是在有限的实验中观察到的现象，期待着理论证明。习题习题n1.比较经验风险最小化和结构风险最小化的原理。n2.描述支持向量机的基本思想和数学模型。n3.简述支持向量机解决非线性可分问题的基本思想。n4.描述支持向量机的核函数构造方法。