支持向量机课件

支持向量机支持向量机1.引言1.1.支持向量机提出的背景1.2.支持向量机发展现状1.3.支持向量机现在存在的问题2.支持向量机基本原理及特点3.支持向量机训练算法4.新型支持向量机5.展望6.应用举例

1.引言

1.1.支持向量机提出的背景

上世纪60年代，Rosenblatt（1958）提出了第一个称作感知器的学习机器模型，标志着人们对学习过程进行数学研究的真正开始。Rosenblatt的主要贡献是把感知器模型表现为一个计算机程序，并且通过简单的试验，说明了此模型的可推广性。反向传播（BP，BackPropagation）技术可以同时寻找多个神经元的权值，标志着构造一般性学习机器研究的完成。学习机器的研究历史进入了一个新阶段，即人工神经元网络（ANNArtificialNeuralNetwork）时代。1.1.支持向量机提出的背景在随后十几年中，人们在许多领域对神经网络进行了深入细致的研究，不但在实际应用中取得了良好效果，而且提出了若干其他神经网络模型，如自组织映射模型、反馈型以及随机型神经网络等等。尽管神经网络在许多应用领域都取得了重要成果，但其实现过程过多地依赖于人的主观意识和先验知识，而不是建立在严格的理论基础之上，因此，难以对神经网络模型的性能及其适用范围进行理论分析。也正因为如此，人们在十几年的神经计算研究中，并没有对一般的学习理论带来更大的贡献（Vapnik，1998）。1.1.支持向量机提出的背景及意义

传统统计学研究的内容是样本无穷大时的渐进理论，即当样本数据趋于无穷多时的统计性质。而实际问题中样本数据往往是有限的。因此，假设样本数据无穷多，并以此为基础推导出的各种算法，很难在样本数据有限时取得理想的应用效果。神经网络（ANN）的过学习问题就是一个典型的例子。当样本数据有限时，本来具有良好学习能力的学习机器有可能表现出很差的泛化性能。早在20世纪70年代诞生的统计学习理论（SLT，StatisticalLearningTheory），系统地研究了机器学习问题。它对有限样本情况下的统计学习问题提供了一个有效的解决途径，弥补了传统统计学的不足。1.1.支持向量机提出的背景统计学习理论是一种专门研究小样本情况下机器学习规律的基本理论和数学构架，也是小样本统计估计和预测学习的最佳理论。Vapnik（1963，1971）等人从六、七十年代开始致力于此方面研究。到上世纪九十年代中期，随着该理论的不断发展和成熟，产生了基于统计学习理论体系的新的通用机器学习方法，即支持向量机（SVMs，SupportVectorMachines）。1.引言1.1.支持向量机提出的背景1.2.支持向量机发展现状1.3.支持向量机现在存在的问题2.支持向量机基本原理及特点3.支持向量机训练算法4.新型支持向量机5.展望6.应用举例1.2支持向量机发展现状

支持向量机算法一经提出，就得到国内外学者的高度关注。学术界普遍认为它是继神经网络之后的一个新的研究方向。在短短的几年里，取得了一系列令人瞩目的研究成果。1.2.支持向量机发展现状（1）支持向量机的理论研究：虽然支持向量机发展时间很短，但是由于它的产生是基于统计学习理论的，因此具有坚实的理论基础。近几年涌现出的大量理论研究成果，更为其应用研究奠定了坚实基础。-Anthony.（1999）等人给出了关于硬邻域支持向量机学习误差的严格理论界限，Shawe-Taylo（r2000）和Cristianin（i2000）也给出了类似的关于软邻域支持向量机和回归情况下的误差界限；-Westonetal.（1998）和Vapnik（1995，1998）等研究了支持向量机的泛化性能及其在多值分类和回归问题的扩展问题；-Smola（1998）和Schoelkopf（1999）提出了支持向量机一般意义下的损失函数数学描述；-脊回归是由Tikhonov提出的一种具有特殊形式的正则化网络，Girosi（1990）、Poggio（1975）等将其应用到正则化网络的学习中，Smolaetal.（1999）研究了状态空间中脊回归的应用，Giros（i1990）、Smola（1998）、Schoelkopf（1999）等讨论了正则化网络和支持向量机的关系。1.2.支持向量机发展现状（2）支持向量机的训练算法：支持向量机的最终求解问题归结为一个有约束的二次型规划（QP，QuadraticProgramming）问题。可以利用标准二次型优化技术来求解这个优化问题，如牛顿法、共扼梯度法、内点法等。但是，这些方法只适合小样本情况，当样本数目较大时，算法复杂度会急剧增加，而且占用极大的系统内存。为降低计算资源、提高算法效率，已经提出许多针对大规模样本集的训练算法：1.2.支持向量机发展现状

四种训练算法1)分块算法（Chunking）（CortesandVapnik，1995）2)子集选择算法（SubsetSelectionalgorithms）（Osuna，1997；Joachims，1998）3)序列最小优化算法（SMO，SequentialMinimalOptimization）（Platt，1998）4）增量式算法（Cauwenberghs，2001）支持向量机1.引言1.1.支持向量机提出的背景1.2.支持向量机发展现状

1.3.支持向量机现在存在的问题2.支持向量机基本原理及特点3.支持向量机训练算法4.新型支持向量机5.展望6.应用举例1.3.支持向量机现在存在的问题支持向量机自出现以来，理论上的研究飞速发展，应用领域越来越广泛。但与理论研究相比较，应用研究相对比较滞后。相比之下，分类问题的研究较为成熟，其他方面如时间序列分析，回归，聚类等方面的研究，还有待进一步地完善。虽然到目前已经提出了多种训练算法，却依然存在一些问题亟待解决。1.3.支持向量机现在存在的问题1）支持向量机在理论上，核函数及参数的构造和选择缺乏理论指导；2）作为支持向量机基础的原始问题解和对偶问题解的关系上，当前研究存在逻辑缺陷；3）在部分情况下，支持向量机无法利用现有的公式计算决策函数的阈值；1.3.支持向量机现在存在的问题4）支持向量机中一类重要的变形方法，虽然有效，但缺乏相应的统计学习理论基础；5）LS-SVM将SVM的求解从QP问题向线性方程组的成功转化极大地提高了SVM的求解效率，也降低了SVM的学习难度，极大地促进了SVM的应用。但LS-SVM同时也丧失SVM的稀疏性与鲁棒性。支持向量机1.引言1.1.支持向量机提出的背景1.2.支持向量机发展现状1.3.支持向量机现在存在的问题2.支持向量机基本原理及特点3.支持向量机训练算法4.新型支持向量机5.展望6.应用举例2.支持向量机基本原理基本原理：通过用非线性映射将输入空间变换到一个高维空间，在这个高维空间中寻找输入变量和输出变量之间的一种非线性关系。注意到算法仅使用高维空间中的内积，通过引入核函数，高维空间的内积运算就可用原空间中的函数来实现，甚至没有必要知道非线性映射的形式。通过采用适当的核函数就可实现某一非线性变换后的线性分类，而计算复杂度没有增加，从而在一定程度上避免了维数灾难问题。2.支持向量机的特点1.非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射;2.对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心;3.支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。2.支持向量机的特点SVM是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律等,因此不同于现有的统计方法。从本质上看,它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”(transductiveinference),大大简化了通常的分类和回归等问题。支持向量机1.引言1.1.支持向量机提出的背景1.2.支持向量机发展现状1.3.支持向量机现在存在的问题2.支持向量机基本原理3.支持向量机训练算法4.新型支持向量机5.展望6.应用举例3.支持向量机训练算法支持向量机的最终求解问题归结为一个有约束的二次型规划（QP，QuadraticProgramming）问题。可以利用标准二次型优化技术来求解这个优化问题，如牛顿法、共扼梯度法、内点法等。但是，这些方法只适合小样本情况，当样本数目较大时，算法复杂度会急剧增加，而且占用极大的系统内存。为降低计算资源、提高算法效率，已经提出许多针对大规模样本集的训练算法：3.支持向量机训练算法分块算法（Chunking）（CortesandVapnik，1995）

-1995年，Cortes和Vapnik给出了一种求解支持向量机二次规划（QP）问题的分块算法。其依据是支持向量机的最终求解结果只与支持向量有关，与非支持向量无关。3.支持向量机训练算法其实现过程是将初始QP问题分解为一系列小规模的QP子问题，不断的求解QP子问题，保留解中的支持向量，并加入到新的QP子问题中。每个QP子问题都采用上次求解的结果作为初始值。直到所有的QP子问题求解完毕。这种方法可以大大减小算法占用的系统内存。然而，当样本集中的支持向量数目很大时，其算法复杂度仍然很大。3.支持向量机训练算法(2)子集选择算法（Osuna，1997；Joachims，1998）-为加快支持向量机的训练速度，Osuna（1997）提出了子集选择算法。该方法首先将数据集分块（chunking），从分块数据中提取支持向量，并加以保留，然后补充新的样本，反复运算，直至所有的样本都满足KKT（Karush-Kuhn-Tucker）（Vapnik，1995）收敛条件。1998年，Joachims指出，采用启发式迭代策略会提高算法的收敛速度，并提出一种称为SVMlight的支持向量机分解学习算法。该算法实际上是子集选择算法的推广。3.支持向量机训练算法(3)序列最小优化算法（SMO）（Platt，1998）1998年，Platt提出了更为有效的支持向量机训练算法，即序列最小优化算法。其基本思想是把一个大数据量的QP分解为一系列最小的QP子优化问题。该算法是分解算法的一个极端特例。其实现过程为，每次针对两个样本的二次规划问题，直接采用解析方法求其最优解，以提高QP问题的求解速度。Platt设计了一个两层嵌套循环过程实现其算法。在外环中采用启发式方法寻找违背KKT最优条件的样本，在内环中对该样本的相应Lagrange乘子进行分析求解，完成一次优化。不断重复此过程,直至所有样本都满足KKT条件。3.支持向量机训练算法序列最小优化算法将工作样本集的规模减少为两个，直接导致了迭代次数的增加。所以序列最小优化算法实际上是将求解优化问题的耗费转嫁到迭代运算上。Platt指出，通过核优化方法可以大幅提高序列最小优化算法的性能。该算法在训练线性支持向量机时，可以获得非常好的性能，但在训练非线性支持向量机时，算法速度会大大减慢。针对不同的问题，其计算复杂度差别很大。3.支持向量机训练算法(4)增量式算法（Cauwenberghs，2001）Cauwenberghs（2001）提出了一种增量减量式学习方法，考虑了增加或减少一个训练样本对Lagrange系数和支持向量机的影响，实验表明算法是有效的。3.支持向量机训练算法在减少一个样本时，给出了模型选择算法LOO（Leaveoneout）的形象解释。Ralaivola（2001）提出了另一种增量式学习方法。其思想为基于高斯核的局部特性，只更新对学习机器输出影响最大的Lagrange系数，以减少计算复杂度。另外，Suykens（2001）提出了一种周期最小二乘支持向量机用于时间序列的预测。Carozzaetal.（2000）和Xiaoetal.（2000）等人也分别提出了一些增量式学习的支持向量机训练算法。3.支持向量机训练算法(5)变形算法：-变形算法主要是通过增加函数项，变量或系数等方法使公式变形，产生出各种有某一方面优势或者一定应用范围的算法。-Suykens等人以双螺旋分类问题为背景，创造性地把标准SVM的线性不等式约束转化成了等式约束，从而使得SVM的训练等价于一组线性方程组的求解。该方法被称为最小二乘支持向量机（LS-SVM）3.支持向量机训练算法SVM的求解从QP问题向线性方程组的成功转化极大地提高了SVM的求解效率，也降低了SVM的学习难度，极大地促进了SVM的应用。在LS-SVM中，对于回归问题，未知变量的数目仅相当于同等规模分类问题的未知变量数目，避免了传统SVM学习方法中回归问题未知变量数目的膨胀。3.支持向量机训练算法(6)几何方法SVM方法具有明显的几何意义，线性可分和不可分问题分别等价于求解特征空间中两类训练样本形成的凸包及缩小的凸包之间的距离。对于线性可分问题，如果在目标函数中加入0.5b2，则可以转化为凸包到原点的最小距离。它存在简单有效的算法，如单纯形迭代法。对于线性不可分问题，则通过采用松弛变量ξ的l2范数，将其转化为线性可分问题进行求解。3.支持向量机训练算法M.H.Yang等利用训练样本的结构信息，提出了训练SVM的几何方法以及卫向量（Guardvector）的概念。卫向量即为通过该向量使输入空间线性可分的向量。支持向量集为卫向量集的一个子集。当训练集合较大时，可以先找出卫向量，再以卫向量构成传统的QP问题求出支持向量。卫向量的求解是通过判断其对偶空间中的线性规划问题的可行性而不是求其解，从而使问题大大简化。3.支持向量机训练算法试验表明该算法求得的最优分类面和传统QP问题一样。由于卫向量约为支持向量的20倍左右，所以该方法训练速度要快30倍，而内存要求仅为传统的1/4。但对支持向量数和卫向量数之间的关系还没有做出相应的理论分析。3.支持向量机训练算法张文生等将SVM原理建立在距离空间上，设计出基于邻域原理计算支持向量的算法。事实上，邻域原理求支持向量的过程就是求一组近似支持向量的过程。该过程本质上是在简化SVM理论中二次规划目标函数的Hessian矩阵。该方法不但几何意义明确，而且计算速度快，每次可以消掉内积矩阵的多行多列，使得计算机的内存开销小。3.支持向量机训练算法汪西莉等提出了一种基于马氏距离的支持向量快速提取算法。用该方法对训练数据进行预处理后，可以加快支持向量机的训练速度3.支持向量机训练算法(7)多类分类算法SVM最初是针对解决两类分类问题提出的，要将其推广到多类分类问题，需要构造多类SVM分类器，其构造方法主要有2种：3.支持向量机训练算法一种是以Weston在1998年提出的多类算法为代表，只需将原始的两类改为K类，这样就很自然的将两类分类SVM转化为K类分类SVM。这种算法选择的目标函数十分的复杂，变量数目过多，计算复杂度也非常的高，实现困难，所以只在小型问题的求解中用到。3.支持向量机训练算法一种构造方法的基本思想就是通过组合多个两类分类器，这类方法目前主要有两种分支算法：1对多算法、1对1算法、决策导向无环图。3.支持向量机训练算法1对多算法是由Vapnik提出的，对于K类问题构造K个两类分类器，第i个SVM用的i类中训练样本作为正的分类样本，而将其他的样本作为负的样本，最后的输出是两类分类器输出的最大的那一类。3.支持向量机训练算法1对1算法是由Knerr提出的，该算法在K类训练样本中构造所可能的两类分类器，每类仅在K类中的两类训练样本上训练，结果共构造k×(k—1)/2个分类器，组合这些两类分类器并使用投票法，得票最多的类为样本点所属的类。3.支持向量机训练算法针对1对1算法，Platt等提出了一个新的学习架构：决策导向无环图（DecisionDirectedAcyclicGraph，DDAG）。对于K类问题，DDAG含k×(k-1)/2个分类器，每个分类器对应两类。在对多个1对1子分类器组合的过程中，引入了图论中有向无环图的思想。由于DDAG的每个节点和一个分类器相关，因此根据DDAG提出的DAGSVM的速度显然要快。3.支持向量机训练算法安金龙等提出了基于二叉树的支持向量机的多类分类方法。它继承了一对多方法的训练支持向量数少及一对一方法的训练速度快的优点。通过在分类阶段结合二叉树，从而大大提高了支持向量机的分类速度。同时它也克服了一对一、一对多、决策导向无环图方法可能出现的无法分类区域的存在，从而提高了支持向量机多类分类的性能。支持向量机1.引言1.1.支持向量机提出的背景1.2.支持向量机发展现状1.3.支持向量机现在存在的问题2.支持向量机基本原理3.支持向量机训练算法4.支持向量机应用5.展望6.应用举例4.支持向量机应用目前支持向量机在如下几个方面获得较为成功的应用。(1)生物信息学生物信息学是近来特别受人关注的一门新学科,SVM在该领域已经获得重要成果,并有着十分广阔的应用前景。4.支持向量机应用人类的遗传功能是由核酸承担的,核酸分为脱氧核糖核酸(DNA)和核糖核酸(RNA)两大类,它们由核苷酸、戊糖以及磷酸构成。DNA分子上的4种核苷酸A,G,C,T的排列组合顺序蕴含了丰富的遗传信息,其中每3个相邻的核苷酸包含一个遗传密码。基因就是指染色体所运载的DNA双螺旋链上的一段序列,该序列由这4种核苷酸通过不同的排列组合形成。4.支持向量机应用针对传统SVM方法中存在的不足,提出了基于数据优化法的SVM,它通过其它统计学模型优化训练数据集,进而提高分类器的辨识精度。实验结果表明基于数据优化法的SVM分类器在翻译起始位点的辨识上可获得比其他判别方法更好的效果。近年来,生物学的信息数量已成指数增长,大量关于DNA和蛋白质序列的信息都已公开。这也大大地增强了人们对发展数据分类技术的兴趣。用分类技术自动地实现将大量的序列数据根据其结构或功能分成相应的不同类别。4.支持向量机应用(2)人脸检测、识别和姿态判定人脸检测是模式识别和机器视觉领域的一个重要研究方向,其目的是判断图像中是否存在人脸,并确定所有人脸的大小和位置。Osuna等最早用SVM进行人脸检测,方法是直接取象素点的灰度值作为输入特征。4.支持向量机应用由于需要大量的存储空间和较多的支持向量,速度很慢。Lyons使用图像的弹性图的某些格点上的2D2Gabor小波变换系数幅值作为特征,使用LDA进行线性判别种族、表情、性别等二值训练和分类,这种方法的缺点是2D2Gabor小波变换,很费时,再加上主成分分析计算量也大,使系统的实时性大大降低。4.支持向量机应用(3)文本分类文本分类的任务是根据文本的内容自动地进行归类,应用很广泛,比如邮件过滤、网页搜索、办公自动化等领域均涉及这一问题。专业中文网页分类器,利用SVM对网页进行两类分类,找出所需专业的中文网页;然后利用向量空间模型,对分类好的专业网页进行多类分类。在构造支持向量机的过程中,为了提高分类的召回率,采用了一种偏移因子。该算法只需要计算两类SVM分类器,实验表明,它不仅具有较高的训练效率,同时能得到很高的分类精确率和召回率。支持向量机1.引言1.1.支持向量机提出的背景1.2.支持向量机发展现状1.3.支持向量机现在存在的问题2.支持向量机基本原理3.支持向量机训练算法4.支持向量机应用5.展望6.应用举例5.展望作为机器学习的一个重要内容，支持向量机的研究已受到众多研究者的关注，但由于出现时间不长，许多问题的研究还处于起步阶段，许多理论问题亟待解决，应用领域也需要进一步拓展。目前，下述几个方面的问题值得进行深入的研究：5.展望1）有限维空间的SVM理论发展较快，无限维空间的SVM理论还需深入研究和推广；2）针对SVM理论中优化问题的特点，如何建立简单、有效、实用的算法是迫切需要解决的问题；3）将神经网络与模糊逻辑等领域已有的研究方法与思想与SVM理论相结合，提出新的方法；4）训练样本中数据含有不确定性以及噪声时的SVM理论性能，即SVM理论的鲁棒性问题是值得研究的重点课题；5）进一步拓展SVM的应用领域，特别是SVM在控制中的应用需要重点研究。支持向量机1.引言1.1.支持向量机提出的背景1.2.支持向量机发展现状1.3.支持向量机现在存在的问题2.支持向量机基本原理3.支持向量机训练算法4.支持向量机应用5.展望6.应用举例

6.应用举例

基于免疫优化的支持向量机文本分类算法

6.1免疫算法原理：是一种复杂的分布式信息处理学习系统，免疫算法的思想来源于生物免疫机体的原理，其具有较强的自适应性、多样性、学习、识别和记忆等特点，其克服遗传算法易陷入局部最优的缺陷，收敛速度大大加快。它模仿生物的免疫过程，具有良好的全局搜索能力和记忆功能。抗原对应于优化问题的目标函数，抗体对应于优化问题的解。通过抗原和抗体的亲和力来描述可行解与最优解的逼近程度。对外界抗原的侵入，系统自动产生相应的抗体，通过抗