支持向量机中科院课件

高级人工智能第八章史忠植中国科学院计算技术研究所支持向量机SupportVectorMachines 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 提要统计学习MATCH_ word word文档格式规范word作业纸小票打印word模板word简历模板免费word简历 _1715983940738_2概述统计学习问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 学习过程的泛化能力支持向量机SVM寻优算法应用统计学习方法概述统计方法是从事物的外在数量上的表现去推断该事物可能的规律性。科学规律性的东西一般总是隐藏得比较深，最初总是从其数量表现上通过统计分析看出一些线索，然后提出一定的假说或学说，作进一步深入的理论研究。当理论研究提出一定的结论时，往往还需要在实践中加以验证。就是说，观测一些自然现象或专门安排的实验所得资料，是否与理论相符、在多大的程度上相符、偏离可能是朝哪个方向等等问题，都需要用统计分析的方法处理。统计学习方法概述近百年来，统计学得到极大的发展。我们可用下面的框架粗略地刻划统计学发展的过程：1900-1920数据描述1920-1940统计模型的曙光1940-1960数理统计时代随机模型假设的挑战松弛结构模型假设1990-1999建模复杂的数据结构统计学习方法概述统计学习方法：传统方法:统计学在解决机器学习问题中起着基础性的作用。传统的统计学所研究的主要是渐近理论，即当样本趋向于无穷多时的统计性质。统计方法主要考虑测试预想的假设和数据模型拟合。它依赖于显式的基本概率模型。模糊集粗糙集支持向量机统计学习方法概述统计方法处理过程可以分为三个阶段：（1）搜集数据：采样、实验设计（2）分析数据：建模、知识发现、可视化（3）进行推理：预测、分类常见的统计方法有:回归分析（多元回归、自回归等）判别分析（贝叶斯判别、费歇尔判别、非参数判别等）聚类分析（系统聚类、动态聚类等）探索性分析（主元分析法、相关分析法等）等。统计学习理论统计学习理论是小样本统计估计和预测学习的最佳理论。假设输出变量Y与输入变量X之间存在某种对应的依赖关系,即一未知概率分布P(X,Y)，P(X,Y)反映了某种知识。学习问题可以概括为:根据l个独立同分布(independentlydrawnandidenticallydistributed)的观测样本trainset，(x1,y1),(x2,y2),…,(xn,yn)函数估计模型学习样本的函数:产生器(G)generatesobservationsx(typicallyinRn),independentlydrawnfromsomefixeddistributionF(x)训练器Supervisor(S)labelseachinputxwithanoutputvalueyaccordingtosomefixeddistributionF(y|x)学习机LearningMachine(LM)“learns”fromani.i.d.l-sampleof(x,y)-pairsoutputfromGandS,bychoosingafunctionthatbestapproximatesSfromaparameterisedfunctionclassf(x,),whereisintheparameterset关键概念:F(x,y),ani.i.d.l-sampleonF,functionsf(x,)andtheequivalentrepresentationofeachfusingitsindexGSLMxyy^期望风险学习到一个假设H=f(x,w)作为预测函数,其中w是广义参数.它对F(X,Y)的期望风险R(w)是(即统计学习的实际风险)：其中，{f(x,w)}称作预测函数集，w为函数的广义参数。{f(x,w)}可以表示任何函数集。L(y,f(x,w))为由于用f(x,w)对y进行预测而造成的损失。不同类型的学习问题有不同形式的损失函数。而对trainset上产生的风险Remp(w)被称为经验风险(学习的训练误差):首先Remp(w)和R(w)都是w的函数，传统概率论中的定理只说明了(在一定条件下)当样本趋于无穷多时Remp(w)将在概率意义上趋近于R(w)，却没有保证使Remp(w)最小的点也能够使R(w)最小(同步最小)。经验风险根据统计学习理论中关于函数集的推广性的界的结论，对于两类分类问题中的指示函数集f(x,w)的所有函数(当然也包括使经验风险员小的函数)，经验风险Remp(w)和实际风险R(w)之间至少以不下于1-η(0≤η≤1)的概率存在这样的关系:经验风险h是函数H=f(x,w)的VC维,l是样本数.VC维(Vapnik-ChervonenkisDimension)。模式识别方法中VC维的直观定义是：对一个指示函数集，如果存在h个样本能够被函数集里的函数按照所有可能的2h种形式分开，则称函数集能够把h个样本打散。函数集的VC维就是它能打散的最大样本数目h。VC维过学习OverfittingandunderfittingProblem:howrichclassofclassificationsq(x;θ)touse.underfittingoverfittinggoodfitProblemofgeneralization:asmallempricalriskRempdoesnotimplysmalltrueexpectedriskR.学习理论的四个部分1.学习过程的一致性理论Whatare(necessaryandsufficient)conditionsforconsistency(convergenceofRemptoR)ofalearningprocessbasedontheERMPrinciple?2.学习过程收敛速度的非渐近理论Howfastistherateofconvergenceofalearningprocess?3.控制学习过程的泛化能力理论Howcanonecontroltherateofconvergence(thegeneralizationability)ofalearningprocess?4.构造学习算法的理论Howcanoneconstructalgorithmsthatcancontrolthegeneralizationability?结构风险最小化归纳原则(SRM)TheStructuralRiskMinimisation(SRM)PrincipleLetS={Q(z,),}.AnadmissiblestructureS1S2…Sn…S:Foreachk,theVCdimensionhkofSkisfiniteandh1≤h2≤…≤hn≤…≤hSEverySkiseitherisnon-negativebounded,orsatisfiesforsome(p,k)TheSRMPrinciplecontinuedForgivenz1,…,zlandanadmissiblestructureS1S2…Sn…S,SRMchoosesfunctionQ(z,lk)minimisingRempinSkforwhichtheguaranteedrisk(riskupper-bound)isminimalThusmanagestheunavoidabletrade-offofqualityofapproximationvs.complexityofapproximationS1S2Snhh1hnh*结构风险最小化归纳原则(SRM)SnS*经验风险Empiricalrisk置信范围Confidenceinterval风险界限Boundontheriskh1h*hnhS1S*Sn结构风险最小化归纳原则(SRM)支持向量机SVMSVMsarelearningsystemsthatuseahyperplaneoflinearfunctionsinahighdimensionalfeaturespace—Kernelfunctiontrainedwithalearningalgorithmfromoptimizationtheory—LagrangeImplementsalearningbiasderivedfromstatisticallearningtheory—GeneralisationSVMisaclassifierderivedfromstatisticallearningtheorybyVapnikandChervonenkis线性分类器ayestfxf(x,w,b)=sign(w.x-b)denotes+1denotes-1Howwouldyouclassifythisdata?线性分类器fxayestdenotes+1denotes-1f(x,w,b)=sign(w.x-b)Howwouldyouclassifythisdata?线性分类器fxayestdenotes+1denotes-1f(x,w,b)=sign(w.x-b)Howwouldyouclassifythisdata?Copyright©2001,2003,AndrewW.Moore线性分类器fxayestdenotes+1denotes-1f(x,w,b)=sign(w.x-b)Howwouldyouclassifythisdata?Copyright©2001,2003,AndrewW.Moore分类超平面Trainingset:(xi,yi),i=1,2,…N;yi{+1,-1}Hyperplane:wx+b=0Thisisfullydeterminedby(w,b)最大间隔AccordingtoatheoremfromLearningTheory,fromallpossiblelineardecisionfunctionstheonethatmaximisesthemarginofthetrainingsetwillminimisethegeneralisationerror.最大间隔原则Note1:decisionfunctions(w,b)and(cw,cb)arethesameNote2:butmarginsasmeasuredbytheoutputsofthefunctionxwx+barenotthesameifwetake(cw,cb).Definition:geometricmargin:themargingivenbythecanonicaldecisionfunction,whichiswhenc=1/||w||Strategy:1)weneedtomaximisethegeometricmargin!(cfresultfromlearningtheory)2)subjecttotheconstraintthattrainingexamplesareclassifiedcorrectlywwx+b=0wx+b>0wx+b<0AccordingtoNote1,wecandemandthefunctionoutputforthenearestpointstobe+1and–1onthetwosidesofthedecisionfunction.Thisremovesthescalingfreedom.Denotinganearestpositiveexamplex+andanearestnegativeexamplex-,thisisComputingthegeometricmargin(thathastobemaximised):Andherearetheconstraints:最大间隔原则wx+b=0wx+b=1wx+b=-1wx+b>1wx+b<1Maximummargin–summingupGivenalinearlyseparabletrainingset(xi,yi),i=1,2,…N;yi{+1,-1}Minimise||w||2SubjecttoThisisaquadraticprogrammingproblemwithlinearinequalityconstraints.Therearewellknownproceduresforsolvingit支持向量Thetrainingpointsthatarenearesttotheseparatingfunctionarecalledsupportvectors.Whatistheoutputofourdecisionfunctionforthesepoints?分类问题的数学表示已知：训练集包含个样本点：说明：是输入指标向量，或称输入，或称模式，其分量称为特征，或属性，或输入指标；是输出指标，或输出.问题：对一个新的模式，推断它所对应的输出是1还是-1.实质：找到一个把上的点分成两部分的规则.2维空间上的分类问题)n维空间上的分类问题.根据给定的训练集其中，，寻找上的一个实值函数，用决策函数判断任一模式对应的值.可见，分类学习机——构造决策函数的方法(算法)，两类分类问题多类分类问题线性分类学习机非线性分类学习机分类学习方法SVM分类问题大致有三种：线性可分问题、近似线性可分问题、线性不可分问题。分类学习方法考虑上的线性可分的分类问题.这里有许多直线能将两类点正确分开.如何选取和？简单问题：设法方向已选定，如何选取？解答：选定平行直线极端直线和取和的中间线为分划直线如何选取？对应一个，有极端直线，称和之间的距离为“间隔”.显然应选使“间隔”最大的。最大间隔法的直观导出数学语言描述调整，使得令，则两式可以等价写为与此相应的分划直线表达式:给定适当的法方向后，这两条极端直线可表示为如何计算分划间隔？考虑2维空间中极端直线之间的间隔情况求出两条极端直线的距离：分划直线表达式为“间隔”为极大化“间隔”的思想导致求解下列对变量和的最优化问题说明：只要我们求得该问题的最优解，从而构造分划超平面，求出决策函数。上述方法对一般上的分类问题也适用.原始问题Margin=H1平面：H2平面：…..(2)…..(1)求解原始问题为求解原始问题，根据最优化理论，我们转化为对偶问题来求解对偶问题为原始问题中与每个约束条件对应的Lagrange乘子。这是一个不等式约束条件下的二次函数寻优问题，存在唯一解线性可分问题计算，选择的一个正分量,并据此计算事实上，的每一个分量都与一个训练点相对应。而分划超平面仅仅依赖于不为零的训练点，而与对应于为零的那些训练点无关。称不为零的这些训练点的输入为支持向量(SV)构造分划超平面,决策函数根据最优解近似线性可分问题不要求所有训练点都满足约束条件，为此对第个训练点引入松弛变量(SlackVariable),把约束条件放松到。体现了训练集被错分的情况，可采用作为一种度量来描述错划程度。两个目标：1.间隔尽可能大2.错划程度尽可能小显然，当充分大时，样本点总可以满足以上约束条件。然而事实上应避免太大，所以需在目标函数对进行惩罚（即“软化”约束条件）因此，引入一个惩罚参数，新的目标函数变为:体现了经验风险，而则体现了表达能力。所以惩罚参数实质上是对经验风险和表达能力匹配一个裁决。当时，近似线性可分SVC的原始问题退化为线性可分SVC的原始问题。近似线性可分问题(广义)线性支持向量分类机算法设已知训练集，其中2.选择适当的惩罚参数，构造并求解最优化问题3.计算，选择的一个分量，并据此计算出4.构造分划超平面,决策函数求得非线性分类例子:Non-linearClassificationWhatcanwedoiftheboundaryisnonlinear?Idea:transformthedatavectorstoaspacewheretheseparatorislinearNon-linearClassificationThetransformationmanytimesismadetoaninfinitedimensionalspace,usuallyafunctionspace.Example:xcos(uTx)Non-linearSVMsTransformx(x)Thelinearalgorithmdependsonlyonxxi,hencetransformedalgorithmdependsonlyon(x)(xi)UsekernelfunctionK(xi,xj)suchthatK(xi,xj)=(x)(xi)设训练集，其中假定可以用平面上的二次曲线来分划：现考虑把2维空间映射到6维空间的变换上式可将2维空间上二次曲线映射为6维空间上的一个超平面：非线性分类可见，只要利用变换，把所在的2维空间的两类输入点映射到所在的6维空间，然后在这个6维空间中，使用线性学习机求出分划超平面：最后得出原空间中的二次曲线：怎样求6维空间中的分划超平面？(线性支持向量分类机)非线性分类需要求解的最优化问题其中非线性分类在求得最优化问题的解后，得到分划超平面其中最后得到决策函数或线性分划－>非线性分划代价：2维空间内积－>6维空间内积非线性分类为此，引进函数有比较(2)和(3)，可以发现这是一个重要的等式，提示6维空间中的内积可以通过计算中2维空间中的内积得到。非线性分类实现非线性分类的思想给定训练集后，决策函数仅依赖于而不需要再考虑非线性变换如果想用其它的非线性分划办法，则可以考虑选择其它形式的函数，一旦选定了函数，就可以求解最优化问题得，而决策函数决策函数其中实现非线性分类的思想设是中的一个子集。称定义在上的函数是核函数(正定核或核)，如果存在着从到某一个空间的映射使得其中表示中的内积核函数(核或正定核)定义多项式内核径向基函数内核RBFSigmoind内核目前研究最多的核函数主要有三类：得到q阶多项式分类器每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定包含一个隐层的多层感知器，隐层节点数是由算法自动确定核函数的选择多项式内核Thekindofkernelrepresentstheinnerproductoftwovector(point)inafeaturespaceofdimension.Forexample－EdgarOsuna(Cambridge,MA)等人在IEEENNSP’97发表了AnImprovedTrainingAlgorithmforSupportVectorMachines,提出了SVM的分解算法，即将原问题分解为若干个子问题，按照某种迭代策略，通过反复求解子问题，最终使得结果收敛于原问题的最优解。传统的利用二次型优化技术解决对偶问题时：需要计算存储核函数矩阵。当样本点数较大时，需要很大的存储空间。例如：当样本点超过4000时，存储核函数矩阵就需要多达128兆内存；SVM在二次型寻优过程中要进行大量的矩阵运算，通常寻优算法占用了算法时间的主要部分。SVM寻优算法考虑去掉Lagrange乘子等于零的训练样本不会影响原问题的解，采用一部分样本构成工作样本集进行训练，移除其中的非支持向量，并把训练结果对剩余样本进行检验，将不符合KKT条件的样本与本次结果的支持向量合并成为一个新的工作集。然后重新训练，如此重复获得最优结果。例如：基于这种思路的算法。根据子问题的划分和迭代策略的不同，大致分为：块算法(ChunkingAlgorithm)：SVM寻优算法SMO使用了块与分解技术，而SMO算法则将分解算法思想推向极致，每次迭代仅优化两个点的最小子集，其威力在于两个数据点的优化问题可以获得解析解，从而不需要将二次规划优化算法作为算法一部分。尽管需要更多的迭代才收敛，但每个迭代需要很少的操作，因此算法在整体上的速度有数量级的提高。另外，算法其他的特征是没有矩阵操作，不需要在内存中存储核矩阵。块算法(ChunkingAlgorithm)：SVM寻优算法SMO算法每次迭代时，在可行的区域内选择两点，最大化目标函数，从而优化两个点的最小子集。无论何时，当一个乘子被更新时，调整另一个乘子来保证线性约束条件成立，保证解不离开可行区域。每步SMO选择两个参数优化，其他参数固定，可以获得解析解。尽管需要更多的迭代才收敛，但每个迭代需要很少的操作，因此算法在整体上的速度有数量级的提高。另外，算法其他的特征是没有矩阵操作，不需要在内存中存储核矩阵。SVM寻优算法SVM寻优算法类别名称测试样本数错误分类数准确度（%）政治146497.26军事830100经济137397.81法律32293.75农业106298.11体育90198.89卫生34197.06工业87297.70科技111298.20交通40197.50生活91198.90宗教30100天气24291.67合计9842197.87SMO算法核缓存算法SMO算法在每次迭代只选择两个样本向量优化目标函数，不需要核矩阵。虽然没有核矩阵操作，但仍需要计算被选向量和训练集中所有样本向量的核函数，计算次数为2n（n为训练集中的样本数）。如果训练集中的样本选取有误，在噪声比较多的情况下，收敛会很慢，迭代次数很多，则核函数的计算量也是非常可观的，SMO算法的优点就完成失去了。同时，考虑到文本分类的文本向量一般维数比较大，核函数的计算将会非常耗时，尤其在高价多项式核和高斯核等核函数的计算中表现更加明显。SVM寻优算法SMO算法核缓存算法在内存中为SMO算法核函数开辟n行m列的核矩阵空间。其中：n为训练集中的样本数；m是为可调节参数，根据实际的内存大小进行调整，每列存放训练集中某个样本向量与训练集中所有样本向量的核函数计算结果列表。在核矩阵列头生成m个节点的双向循环链表队列，每个节点指向核矩阵的列，通过双向循环链表队列实现核矩阵中的核函数列唤入唤出操作。同时，为了实现样本向量的核函数列的快速查找，为每个训练样本向量设计了快速索引列表，通过索引列表判断该训练样本向量的核函数列是否在核矩阵中，并确定在哪一列。SVM寻优算法SVM寻优算法选择一个训练集，通过调整核缓冲参数的大小，记录不同核缓存大小情况下训练时间，结果如下表：核缓存大小(Mb)训练样本数核矩阵迭代次数训练时间(M:S)156245624*23407267:061056245624*233407263:502056245624*466407262:413056245624*699407261:564056245624*932407261:295056245624*1165407261:236056245624*1398407261:087056245624*1631407261:058056245624*1864407261:049056245624*2097407261:0710056245624*2330407261:3725056245624*5624407261:12通过引入核缓存 机制 综治信访维稳工作机制反恐怖工作机制企业员工晋升机制公司员工晋升机制员工晋升机制图 ，有效的改进了SMO算法，提高了文本分类的训练速度。在核缓存机制中采用简单的hash查找算法和队列FILO算法，有效提高了核矩阵查找和唤入唤出操作的效率。设置核矩阵列参数，通过调节列参数，可以灵活的根据系统运行情况调整训练的时间和空间开销，避免因系统空间开销过大使系统运行效率下降，反而影响训练速度。SVM寻优算法活动向量集选择算法当训练样本数非常大的时候，如果系统能够提供的核缓冲大小很有限，那么能够同时保存在核缓冲中训练样本的核函数数目在训练样本数中所占比例将非常的小。在训练过程中，训练样本在核缓冲中的核函数命中率将显著下降，导致核缓冲中的核函数被频繁的唤入唤出，而每执行一次唤入唤出操作将引起系统重新计算训练样本的核函数，核缓存的作用被很大程度的削弱了。如果出现这样的情况，要么增加系统的存储空间；要么减少训练样本数，才能提高系统的训练速度。为解决训练样本数多，系统内存空间小的矛盾，本文通过活动向量集选择算法，比较好地解决了这个问题。SVM寻优算法活动向量集选择算法算法的主要思想是：定期检查训练样本集，在收敛前预先确定训练样本集中一些边界上的点（alpha=0，或者alpha=C）是否以后不再被启发式选择，或者不再被判定为最有可能违例，如果存在这样的点，将它们从训练样本集中剔除出去，减少参加训练的样本数。该算法基于如下的认识：经过多次迭代后，如果样本的拉格朗日乘子一直为0，该点被当前估计的支持向量集所确定的超平面区分得很开，即使以后支持向量集发生变化，该点也不会是最靠近超平面的点，则可以确定该样本不是支持向量；经过多次迭代后，如果样本的拉格朗日乘子一直为非常大的C常数，即使以后支持向量集发生变化，该点也不会远离超平面，则可以确定该样本是上边界处的支持向量SVM寻优算法活动向量集选择算法这样就可以在SMO算法收敛前，提前将边界上的点从训练样本集中剔除，逐渐缩小参加训练的活动样本集，从而减少SMO算法对核缓存空间的要求，提高训练速度。训练开始前，训练活动集样本初始化为全部训练样本。每经过一定次数的迭代（比如迭代1000次），如果算法还没有收敛，应检查活动集中的向量，检查是否有训练样本可以不参加迭代运算。检查完当前活动向量集中所有样本后，产生了新的活动向量集。如果新的活动向量集的样本数减少一成以上（含一成），则可以收缩当前活动向量集，用新的活动向量集替换当前活动向量集。当活动向量集的样本数减少到一定的程度，对核缓存空间的要求不是很大的时候，继续减少训练样本对训练速度的提高就非常有限了，这时就没有必要再减少训练样本了。SVM寻优算法将工作样本集的大小固定在算法速度可以容忍的限度内，迭代过程选择一种合适的换入换出策略，将剩余样本中的一部分与工作样本集中的样本进行等量交换，即使支持向量的个数超过工作样本集的大小，也不改变工作样本集的规模，而只对支持向量中的一部分进行优化。例如:算法2.固定工作样本集(Osunaetal.)：SVM寻优算法SVMapplicationsPatternrecognitionFeatures:wordscountsDNAarrayexpressiondataanalysisFeatures:expr.levelsindiff.conditionsProteinclassificationFeatures:AAcompositionHandwrittenDigitsRecognitionApplyingSVMstoFaceDetectionTheSVMface-detectionsystem1.Rescaletheinputimageseveraltimes2.Cut19x19windowpatternsoutofthescaledimage3.Preprocessthewindowusingmasking,lightcorrectionandhistogramequalization4.ClassifythepatternusingtheSVM5.Iftheclasscorrespondstoaface,drawarectanglearoundthefaceintheoutputimage.ApplyingSVMstoFaceDetectionExperimentalresultsonstaticimagesSetA:313high-quality,samenumberoffacesSetB:23mixedquality,totalof155facesApplyingSVMstoFaceDetectionExtensiontoareal-timesystemAnexampleoftheskindetectionmoduleimplementedusingSVMsFaceDetectiononthePC-basedColorRealTimeSystemReferencesVladimirVapnik.TheNatureofStatisticalLearningTheory,Springer,1995AndrewW.Moore.cmsc726:SVMs.http://www.cs.cmu.edu/~awm/tutorialsC.Burges.Atutorialonsupportvectormachinesforpatternrecognition.DataMiningandKnowledgeDiscovery,2(2):955-974,1998.http://citeseer.nj.nec.com/burges98tutorial.htmlVladimirVapnik.StatisticalLearningTheory.Wiley-Interscience;1998ThorstenJoachims(joachims_01a):AStatisticalLearningModelofTextClassificationforSupportVectorMachinesBenRubinstein.StatisticalLearningTheory.Dept.ComputerScience&SoftwareEngineering,UniversityofMelbourne;andDivisionofGenetics&Bioinformatics,Walter&ElizaHallInstitutewww.intsci.ac.cn/shizz/Questions?!