统计学习StatisticalLearning-PPT精品课件.ppt

1、统计学习统计学习 Statistical LearningStatistical Learning史忠植史忠植中国科学院计算技术研究所中国科学院计算技术研究所高级人工智能高级人工智能第八章2022-7-24Chap8 SL Zhongzhi Shi2内容提要内容提要n统计学习方法概述统计学习方法概述n统计学习问题统计学习问题n学习过程的泛化能力学习过程的泛化能力n支持向量机支持向量机nSVMSVM寻优算法算法n极限学习机极限学习机n应用应用2022-7-24Chap8 SL Zhongzhi Shi3统计学习方法概述统计学习方法概述 统计方法是从事物的外在数量上的表现去推断该事物可统计方法是从

2、事物的外在数量上的表现去推断该事物可能的规律性。能的规律性。科学规律性的东西一般总是隐藏得比较深，科学规律性的东西一般总是隐藏得比较深，最初总是从其数量表现上通过统计分析看出一些线索，最初总是从其数量表现上通过统计分析看出一些线索，然后提出一定的假说或学说，作进一步深入的理论研究。然后提出一定的假说或学说，作进一步深入的理论研究。当理论研究当理论研究 提出一定的结论时，往往还需要在实践中加提出一定的结论时，往往还需要在实践中加以验证。就是说，观测一些自然现象或专门安排的实验以验证。就是说，观测一些自然现象或专门安排的实验所得资料，是否与理论相符、在多大的程度上相符、偏所得资料，是否与理论相符、

3、在多大的程度上相符、偏离可能是朝哪个方向等等问题，都需要用统计分析的方离可能是朝哪个方向等等问题，都需要用统计分析的方法处理。法处理。2022-7-24Chap8 SL Zhongzhi Shi4统计学习方法概述统计学习方法概述 近百年来，统计学得到极大的发展。我们可用下近百年来，统计学得到极大的发展。我们可用下面的框架粗略地刻划统计学发展的过程：面的框架粗略地刻划统计学发展的过程：n1900-1920 数据描述数据描述n1920-1940 统计模型的曙光统计模型的曙光n1940-1960 数理统计时代数理统计时代n随机模型假设的挑战随机模型假设的挑战n松弛结构模型假设松弛结构模型假设n199

4、0-2019 建模复杂的数据结构建模复杂的数据结构2022-7-24Chap8 SL Zhongzhi Shi5统计学习方法概述统计学习方法概述 从从1960年至年至1980年间，统计学领域出现了一场革命，要从年间，统计学领域出现了一场革命，要从观测数据对依赖关系进行估计，只要知道未知依赖关系所观测数据对依赖关系进行估计，只要知道未知依赖关系所属的函数集的某些一般的性质就足够了。引导这一革命的属的函数集的某些一般的性质就足够了。引导这一革命的是是60年代的四项发现：年代的四项发现：nTikhonov,Ivanov 和和 Philips 发现的关于解决不适定问题的发现的关于解决不适定问题的正则化

5、原则；正则化原则；nParzen,Rosenblatt 和和Chentsov 发现的非参数统计学；发现的非参数统计学；nVapnik 和和Chervonenkis 发现的在泛函数空间的大数定律，发现的在泛函数空间的大数定律，以及它与学习过程的关系；以及它与学习过程的关系；nKolmogorov,Solomonoff 和和Chaitin 发现的算法复杂性及发现的算法复杂性及其与归纳推理的关系。其与归纳推理的关系。这四项发现也成为人们对学习过程研究的重要基础。这四项发现也成为人们对学习过程研究的重要基础。2022-7-24Chap8 SVM Zhongzhi Shi6统计学习方法概述统计学习方法概

6、述 统计学习方法统计学习方法：n传统方法传统方法:统计学在解决机器学习问题中起着基础性统计学在解决机器学习问题中起着基础性的作用。传统的统计学所研究的主要是渐近理论，的作用。传统的统计学所研究的主要是渐近理论，即当样本趋向于无穷多时的统计性质。统计方法主即当样本趋向于无穷多时的统计性质。统计方法主要考虑测试预想的假设和数据模型拟合。它依赖于要考虑测试预想的假设和数据模型拟合。它依赖于显式的基本概率模型。显式的基本概率模型。n模糊集模糊集n粗糙集粗糙集n支持向量机支持向量机2022-7-24Chap8 SVM Zhongzhi Shi7统计学习方法概述统计学习方法概述 统计方法处理过程可以分为三

7、个阶段：统计方法处理过程可以分为三个阶段：n（1）搜集数据：采样、实验设计）搜集数据：采样、实验设计n（2）分析数据：建模、知识发现、可视化）分析数据：建模、知识发现、可视化n（3）进行推理：预测、分类）进行推理：预测、分类 常见的统计方法有常见的统计方法有:回归分析（多元回归、自回归等）回归分析（多元回归、自回归等）判别分析（贝叶斯判别、费歇尔判别、非参数判别等）判别分析（贝叶斯判别、费歇尔判别、非参数判别等）聚类分析（系统聚类、动态聚类等）聚类分析（系统聚类、动态聚类等）探索性分析（主元分析法、相关分析法等）等。探索性分析（主元分析法、相关分析法等）等。2022-7-24Chap8 SVM

8、 Zhongzhi Shi8支持向量机支持向量机nSVMSVM是一种基于统计学习理论的机器学是一种基于统计学习理论的机器学习方法，它是由习方法，它是由Boser,Guyon,VapnikBoser,Guyon,Vapnik在在COLT-92COLT-92上首次提出，从此迅速发展起上首次提出，从此迅速发展起来来nVapnik V N.2019.The Nature of Statistical Vapnik V N.2019.The Nature of Statistical Learning Theory.Springer-Verlag,New York Learning Theory.Spr

9、inger-Verlag,New York nVapnik V N.2019.Statistical Learning Vapnik V N.2019.Statistical Learning Theory.Wiley-Interscience Publication,John Theory.Wiley-Interscience Publication,John Wiley&Sons,IncWiley&Sons,Incn目前已经在许多智能信息获取与处理领目前已经在许多智能信息获取与处理领域都取得了成功的应用。域都取得了成功的应用。2022-7-24Chap8 SVM Zhongzhi Shi9

10、学习问题研究的四个阶段学习问题研究的四个阶段nRosenblatt 感知器（感知器（60年代）。年代）。n学习理论基础的创立（学习理论基础的创立（60-70年代）年代）经验风险最小，算法复杂性经验风险最小，算法复杂性n神经网络（神经网络（80年代）年代）PACn回到起点（回到起点（90年代）年代）多层感知器多层感知器2022-7-24Chap8 SVM Zhongzhi Shi10统计学习理论统计学习理论n统计学习理论是小样本统计估计和预测学习的统计学习理论是小样本统计估计和预测学习的最佳理论。最佳理论。n假设输出变量假设输出变量Y与输入变量与输入变量X之间存在某种对之间存在某种对应的依赖关系

11、应的依赖关系,即一未知概率分布即一未知概率分布P(X,Y)，P(X,Y)反映了某种知识。学习问题可以概括为反映了某种知识。学习问题可以概括为:根据根据l个独立同分布个独立同分布(independently drawn and identically distributed)的观测样本的观测样本train set，(x1,y1),(x2,y2),(xn,yn)2022-7-24Chap8 SVM Zhongzhi Shi11函数估计模型函数估计模型n学习样本的函数学习样本的函数:n产生器产生器(G)(G)产生随机向量产生随机向量x x R Rn n,它们是从固它们是从固定但未知的概率分布函数定但

12、未知的概率分布函数F F(x x)中独立抽取的。中独立抽取的。n训练器训练器Supervisor(S)Supervisor(S)对每个输入向量对每个输入向量x x 返返回一个输出值回一个输出值y y，产生输出的根据是同样固定，产生输出的根据是同样固定 但未知的条件分布函数但未知的条件分布函数 F F(y|xy|x)n学习机学习机Learning Machine(LM)Learning Machine(LM)它能够实现它能够实现一定的函数集一定的函数集f f(x x,)，其中其中 是参数是参数的集合。的集合。GSLMxyy关键概念关键概念:学习的问题就是从给定的函数集学习的问题就是从给定的函数集

13、f(x,)，中选择出能够最中选择出能够最好地逼近训练器响应的函数。这种选择是基于训练集的，训练集由根据联好地逼近训练器响应的函数。这种选择是基于训练集的，训练集由根据联合分布合分布F(x,y)=F(x)F(y|x)抽取出的抽取出的l l个独立同分布个独立同分布（i.i.d）观测观测 (x1,y1),(x2,y2),(xn,yn)组成组成2022-7-24Chap8 SVM Zhongzhi Shi12期望风险期望风险 学习到一个假设学习到一个假设H=f(x,w)H=f(x,w)作为预测函数作为预测函数,其中其中w w是广义参是广义参数数.它对它对F(X,Y)F(X,Y)的期望风险的期望风险R(

14、w)R(w)是是(即统计学习的实际风即统计学习的实际风险险)：其中，f(x,w)称作预测函数集，w为函数的广义参数。f(x,w)可以表示任何函数集。L(y,f(x,w)为由于用f(x,w)对y进行预测而造成的损失。不同类型的学习问题有不同形式的损失函数。()(,(,)(,)R wL y f x wdF x y2022-7-24Chap8 SVM Zhongzhi Shi13 而对train set上产生的风险Remp(w)被称为经验风险(学习的训练误差):,11()(,)lempiiiRwL y fxwl 首先Remp(w)和R(w)都是w的函数，传统概率论中的定理只说明了(在一定条件下)当样

15、本趋于无穷多时Remp(w)将在概率意义上趋近于R(w)，却没有保证使Remp(w)最小的点也能够使R(w)最小(同步最小)。经验风险经验风险2022-7-24Chap8 SVM Zhongzhi Shi14 根据统计学习理论中关于函数集的推广性的界的结论，对于两类分类问题中的指示函数集f(x,w)的所有函数(当然也包括使经验风险员小的函数)，经验风险Remp(w)和实际风险R(w)之间至少以不下于1-(01)的概率存在这样的关系:)/()()(lhwRwRemp经验风险经验风险2022-7-24Chap8 SVM Zhongzhi Shi15lhlhlh)4/ln()1/2(ln()/(h是

16、函数H=f(x,w)的VC维,l是样本数.VCVC维维(Vapnik-Chervonenkis Dimension)(Vapnik-Chervonenkis Dimension)。模式识别方法。模式识别方法中中VCVC维的直观定义是：对一个指示函数集，如果存在维的直观定义是：对一个指示函数集，如果存在h h个个样本能够被函数集里的函数按照所有可能的样本能够被函数集里的函数按照所有可能的2h2h种形式分开，种形式分开，则称函数集能够把则称函数集能够把h h个样本打散。函数集的个样本打散。函数集的VCVC维就是它能维就是它能打散的最大样本数目打散的最大样本数目h h。VCVC维维2022-7-24

17、Chap8 SVM Zhongzhi Shi16 一般的学习方法(如神经网络)是基于 Remp(w)最小,满足对已有训练数据的最佳拟和,在理论上可以通过增加算法（如神经网络）的规模使得Remp(w)不断降低以至为0。但是,这样使得算法（神经网络）的复杂度增加,VC维h增加,从而(h/l)增大,导致实际风险R(w)增加,这就是学习算法的过拟合(Overfitting).过学习过学习2022-7-24Chap8 SVM Zhongzhi Shi17过学习过学习Overfitting and underfittingProblem:how rich class of classifications

18、q(x;)to use.underfittingoverfittinggood fitProblem of generalization:a small emprical risk Remp does not imply small true expected risk R.2022-7-24Chap8 SVM Zhongzhi Shi18学习理论的四个部分学习理论的四个部分1.学习过程的一致性理论学习过程的一致性理论What are(necessary and sufficient)conditions for consistency(convergence of Remp to R)of

19、a learning process based on the ERM Principle?2.学习过程收敛速度的非渐近理论学习过程收敛速度的非渐近理论How fast is the rate of convergence of a learning process?3.控制学习过程的泛化能力理论控制学习过程的泛化能力理论How can one control the rate of convergence(the generalization ability)of a learning process?4.构造学习算法的理论构造学习算法的理论 How can one construct al

20、gorithms that can control the generalization ability?2022-7-24Chap8 SVM Zhongzhi Shi19结构风险最小化归纳原则结构风险最小化归纳原则(SRM)nERM is intended for relatively large samples(large l/h)nLarge l/h induces a small which decreases the the upper bound on risknSmall samples?Small empirical risk doesnt guarantee anything

21、!we need to minimise both terms of the RHS of the risk boundsnThe empirical risk of the chosen 1.An expression depending on the VC dimension of 2022-7-24Chap8 SVM Zhongzhi Shi20结构风险最小化归纳原则结构风险最小化归纳原则(SRM)nThe Structural Risk Minimisation(SRM)PrinciplenLet S=Q(z,),.An admissible structure S1S2SnS:nFo

22、r each k,the VC dimension hk of Sk is finite and h1h2hnhSnEvery Sk is either is non-negative bounded,or satisfies for some(p,k)supkQpz,dF z 1pR k,p 22022-7-24Chap8 SVM Zhongzhi Shi21nThe SRM Principle continuednFor given z1,zl and an admissible structure S1S2Sn S,SRM chooses function Q(z,lk)minimisi

23、ng Remp in Sk for which the guaranteed risk(risk upper-bound)is minimalnThus manages the unavoidable trade-off of quality of approximation plexity of approximationS1S2Snhh1hnh*结构风险最小化归纳原则结构风险最小化归纳原则(SRM)2022-7-24Chap8 SVM Zhongzhi Shi22 Sn S*经验风险经验风险Empirical risk置信范围置信范围Confidence interval风险界限风险界限B

24、ound on the riskh1h*hnhS1S*Sn结构风险最小化归纳原则结构风险最小化归纳原则 (SRM)2022-7-24Chap8 SVM Zhongzhi Shi23支持向量机支持向量机 SVMnSVMs are learning systems that nuse a hyperplane of linear functionsnin a high dimensional feature space Kernel functionntrained with a learning algorithm from optimization theory LagrangenImplem

25、ents a learning bias derived from statistical learning theory Generalisation SVM is a classifier derived from statistical learning theory by Vapnik and Chervonenkis2022-7-24Chap8 SVM Zhongzhi Shi24 线性分类器线性分类器yestf xf(x,w,b)=sign(w.x-b)denotes+1denotes-1How would you classify this data?2022-7-24Chap8

26、 SVM Zhongzhi Shi25线性分类器线性分类器f xyestdenotes+1denotes-1f(x,w,b)=sign(w.x-b)How would you classify this data?2022-7-24Chap8 SVM Zhongzhi Shi26线性分类器线性分类器f xyestdenotes+1denotes-1f(x,w,b)=sign(w.x-b)How would you classify this data?Copyright 2019,2019,Andrew W.Moore2022-7-24Chap8 SVM Zhongzhi Shi27线性分类器

27、线性分类器f xyestdenotes+1denotes-1f(x,w,b)=sign(w.x-b)How would you classify this data?Copyright 2019,2019,Andrew W.Moore2022-7-24Chap8 SVM Zhongzhi Shi28线性分类器线性分类器f xyestdenotes+1denotes-1f(x,w,b)=sign(w.x-b)How would you classify this data?Copyright 2019,2019,Andrew W.Moore2022-7-24Chap8 SVM Zhongzhi

28、Shi29最大间隔最大间隔f xyestdenotes+1denotes-1f(x,w,b)=sign(w.x-b)The maximum margin linear classifier is the linear classifier with the maximum margin.This is the simplest kind of SVM(Called an LSVM)Linear SVMCopyright 2019,2019,Andrew W.Moore2022-7-24Chap8 SVM Zhongzhi Shi30分类超平面分类超平面nTraining set:(xi,yi)

29、,i=1,2,N;yi+1,-1nHyperplane:wx+b=0nThis is fully determined by(w,b)2022-7-24Chap8 SVM Zhongzhi Shi31最大间隔最大间隔According to a theorem from Learning Theory,from all possible linear decision functions the one that maximises the margin of the training set will minimise the generalisation error.2022-7-24Ch

30、ap8 SVM Zhongzhi Shi32最大间隔原则最大间隔原则Note1:decision functions(w,b)and(cw,cb)are the sameNote2:but margins as measured by the outputs of the function xwx+b are not the same if we take(cw,cb).Definition:the margin given by the,which is when c=1/|w|Strategy:1)we need to maximise the geometric margin!(cf r

31、esult from learning theory)2)subject to the constraint that training examples are classified correctly wwx+b=0wx+b0wx+b1wx+b非线性分划代价：2维空间内积6维空间内积非线性分类非线性分类2022-7-24Chap8 SVM Zhongzhi Shi57为此，引进函数有211222222112211221122(,)(1)12 2 2 ijijijijijijijijijK x xxxxxxxxxxxxxxxxx 比较(2)和(3)，可以发现2(,)()1)ijijK x x

32、x x(3)2()()(,)()1)ijijijxxK x xxx这是一个重要的等式，提示6维空间中的内积可以通过计算 中2维空间中的内积 得到。()()ijxx(,)ijK x x()ijx x非线性分类非线性分类2022-7-24Chap8 SVM Zhongzhi Shi58实现非线性分类的思想实现非线性分类的思想给定训练集后，决策函数仅依赖于而不需要再考虑非线性变换如果想用其它的非线性分划办法，则可以考虑选择其它形式的函数 ，一旦选定了函数，就可以求解最优化问题2(,)()1)ijijK x xx x(,)ijK x x()x111l1i1min ,2.0 0,1,lllijijijj

33、ijjiiiy yK x xstyC il*1(,)Tl得 ，而决策函数2022-7-24Chap8 SVM Zhongzhi Shi59*1()sgn(,)liiiif xyK x xb决策函数其中*1(,)|0ljiiijjibyyK x xjjC(,)iK x x 核函数实现非线性分类的思想实现非线性分类的思想2022-7-24Chap8 SVM Zhongzhi Shi60设 是 中的一个子集。称定义在 上的函数 是核函数(正定核或核)，如果存在着从 到某一个空间 的映射 :()xx nR(,)K x xHilbert使得(,)()()K x xxx其中 表示 中的内积()Hilber

34、t核函数核函数(核或正定核核或正定核)定义定义2022-7-24Chap8 SVM Zhongzhi Shi61n多项式内核n径向基函数内核RBFnSigmoind内核(,)()qiiK x xx xc22|(,)expiixxK x x(,)tanh()iiK x xx xc目前研究最多的核函数主要有三类：得到q 阶多项式分类器每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定包含一个隐层的多层感知器，隐层节点数是由算法自动确定核函数的选择核函数的选择2022-7-24Chap8 SVM Zhongzhi Shi62多项式内核多项式内核nThe kind of kernel rep

35、resents the inner product of two vector(point)in a feature space of dimension.nFor exampledyxyxK),(ddn12022-7-24Chap8 SVM Zhongzhi Shi63Edgar Osuna(Cambridge,MA)等人在等人在IEEE NNSP97发表发表了了An Improved Training Algorithm for Support Vector Machines,提出了提出了SVM的分解算法，即将原问题分解为若的分解算法，即将原问题分解为若干个子问题，按照某种迭代策略，通过反

36、复求解子问题，干个子问题，按照某种迭代策略，通过反复求解子问题，最终使得结果收敛于原问题的最优解。最终使得结果收敛于原问题的最优解。传统的利用二次型优化技术解决对偶问题时：传统的利用二次型优化技术解决对偶问题时：n 需要计算存储核函数矩阵。当样本点数较大时，需要很需要计算存储核函数矩阵。当样本点数较大时，需要很大的存储空间。例如：当样本点超过大的存储空间。例如：当样本点超过4000时，存储核函数时，存储核函数矩阵就需要多达矩阵就需要多达128兆内存；兆内存；n SVM在二次型寻优过程中要进行大量的矩阵运算，通常在二次型寻优过程中要进行大量的矩阵运算，通常寻优算法占用了算法时间的主要部分。寻优算

37、法占用了算法时间的主要部分。SVMSVM寻优寻优算法算法2022-7-24Chap8 SVM Zhongzhi Shi64考虑去掉Lagrange乘子等于零的训练样本不会影响原问题的解，采用一部分样本构成工作样本集进行训练，移除其中的非支持向量，并把训练结果对剩余样本进行检验，将不符合KKT条件的样本与本次结果的支持向量合并成为一个新的工作集。然后重新训练，如此重复获得最优结果。例如：基于这种思路的 算法。根据子问题的划分和迭代策略的不同，大致分为：1.块算法(Chunking Algorithm)：SMOSVM寻优寻优算法算法2022-7-24Chap8 SVM Zhongzhi Shi65

38、SMO使用了块与分解技术，而SMO算法则将分解算法思想推向极致，每次迭代仅优化两个点的最小子集，其威力在于两个数据点的优化问题可以获得解析解，从而不需要将二次规划优化算法作为算法一部分。尽管需要更多的迭代才收敛，但每个迭代需要很少的操作，因此算法在整体上的速度有数量级的提高。另外，算法其他的特征是没有矩阵操作，不需要在内存中存储核矩阵。块算法(Chunking Algorithm)：SVM寻优寻优算法算法2022-7-24Chap8 SVM Zhongzhi Shi66SMO算法每次迭代时，在可行的区域内选择两点，最大化目标函数，从而优化两个点的最小子集。无论何时，当一个乘子被更新时，调整另一

39、个乘子来保证线性约束条件成立，保证解不离开可行区域。每步SMO选择两个参数优化，其他参数固定，可以获得解析解。尽管需要更多的迭代才收敛，但每个迭代需要很少的操作，因此算法在整体上的速度有数量级的提高。另外，算法其他的特征是没有矩阵操作，不需要在内存中存储核矩阵。SVM寻优寻优算法算法2022-7-24Chap8 SVM Zhongzhi Shi67SVM寻优寻优算法算法类别名称测试样本数错误分类数准确度（%）政治146497.26军事830100经济137397.81法律32293.75农业106298.11体育90198.89卫生34197.06工业87297.70科技111298.20交通

40、40197.50生活91198.90宗教30100天气24291.67合计9842197.872022-7-24Chap8 SVM Zhongzhi Shi68SMOSMO算法核缓存算法算法核缓存算法SMO算法在每次迭代只选择两个样本向量优化目标函数，不需要核矩阵。虽然没有核矩阵操作，但仍需要计算被选向量和训练集中所有样本向量的核函数，计算次数为2n（n为训练集中的样本数）。如果训练集中的样本选取有误，在噪声比较多的情况下，收敛会很慢，迭代次数很多，则核函数的计算量也是非常可观的，SMO 算法的优点就完成失去了。同时，考虑到文本分类的文本向量一般维数比较大，核函数的计算将会非常耗时，尤其在高价

41、多项式核和高斯核等核函数的计算中表现更加明显。SVM寻优寻优算法算法2022-7-24Chap8 SVM Zhongzhi Shi69SMOSMO算法核缓存算法算法核缓存算法在内存中为SMO算法核函数开辟n行m列的核矩阵空间。其中：n为训练集中的样本数；m是为可调节参数，根据实际的内存大小进行调整，每列存放训练集中某个样本向量与训练集中所有样本向量的核函数计算结果列表。在核矩阵列头生成m个节点的双向循环链表队列，每个节点指向核矩阵的列，通过双向循环链表队列实现核矩阵中的核函数列唤入唤出操作。同时，为了实现样本向量的核函数列的快速查找，为每个训练样本向量设计了快速索引列表，通过索引列表判断该训练

42、样本向量的核函数列是否在核矩阵中，并确定在哪一列。SVM寻优寻优算法算法2022-7-24Chap8 SVM Zhongzhi Shi70SVM寻优寻优算法算法n选择一个训练集，通过调整核缓冲参数的大小，记选择一个训练集，通过调整核缓冲参数的大小，记录不同核缓存大小情况下训练时间，结果如下表：录不同核缓存大小情况下训练时间，结果如下表：核缓存大小(Mb)训练样本数核矩阵迭代次数训练时间(M:S)156245624*23407267:061056245624*233407263:502056245624*466407262:413056245624*699407261:564056245624*

43、932407261:295056245624*1165407261:236056245624*1398407261:087056245624*1631407261:058056245624*1864407261:049056245624*2097407261:0710056245624*2330407261:3725056245624*5624407261:122022-7-24Chap8 SVM Zhongzhi Shi71通过引入核缓存机制，有效的改进了通过引入核缓存机制，有效的改进了SMOSMO算法，提算法，提高了文本分类的训练速度。在核缓存机制中采用高了文本分类的训练速度。在核缓存机制

44、中采用简单的简单的hashhash查找算法和队列查找算法和队列FILOFILO算法，有效提高算法，有效提高了核矩阵查找和唤入唤出操作的效率。设置核矩了核矩阵查找和唤入唤出操作的效率。设置核矩阵列参数，通过调节列参数，可以灵活的根据系阵列参数，通过调节列参数，可以灵活的根据系统运行情况调整训练的时间和空间开销，避免因统运行情况调整训练的时间和空间开销，避免因系统空间开销过大使系统运行效率下降，反而影系统空间开销过大使系统运行效率下降，反而影响训练速度。响训练速度。SVM寻优寻优算法算法2022-7-24Chap8 SVM Zhongzhi Shi72活动向量集选择算法 当训练样本数非常大的时候，

45、如果系统能够提供的核缓冲当训练样本数非常大的时候，如果系统能够提供的核缓冲大小很有限，那么能够同时保存在核缓冲中训练样本的核大小很有限，那么能够同时保存在核缓冲中训练样本的核函数数目在训练样本数中所占比例将非常的小。在训练过函数数目在训练样本数中所占比例将非常的小。在训练过程中，训练样本在核缓冲中的核函数命中率将显著下降，程中，训练样本在核缓冲中的核函数命中率将显著下降，导致核缓冲中的核函数被频繁的唤入唤出，而每执行一次导致核缓冲中的核函数被频繁的唤入唤出，而每执行一次唤入唤出操作将引起系统重新计算训练样本的核函数，核唤入唤出操作将引起系统重新计算训练样本的核函数，核缓存的作用被很大程度的削弱

46、了。如果出现这样的情况，缓存的作用被很大程度的削弱了。如果出现这样的情况，要么增加系统的存储空间；要么减少训练样本数，才能提要么增加系统的存储空间；要么减少训练样本数，才能提高系统的训练速度。为解决训练样本数多，系统内存空间高系统的训练速度。为解决训练样本数多，系统内存空间小的矛盾，本文通过活动向量集选择算法，比较好地解决小的矛盾，本文通过活动向量集选择算法，比较好地解决了这个问题。了这个问题。SVM寻优寻优算法算法2022-7-24Chap8 SVM Zhongzhi Shi73活动向量集选择算法 算法的主要思想是：定期检查训练样本集，在收敛前预算法的主要思想是：定期检查训练样本集，在收敛前

47、预先确定训练样本集中一些边界上的点（先确定训练样本集中一些边界上的点（alpha=0alpha=0，或者，或者alpha=Calpha=C）是否以后不再被启发式选择，或者不再被判定为）是否以后不再被启发式选择，或者不再被判定为最有可能违例，如果存在这样的点，将它们从训练样本集最有可能违例，如果存在这样的点，将它们从训练样本集中剔除出去，减少参加训练的样本数。该算法基于如下的中剔除出去，减少参加训练的样本数。该算法基于如下的认识：经过多次迭代后，如果样本的拉格朗日乘子一直为认识：经过多次迭代后，如果样本的拉格朗日乘子一直为0 0，该点被当前估计的支持向量集所确定的超平面区分得很开，该点被当前估计

48、的支持向量集所确定的超平面区分得很开，即使以后支持向量集发生变化，该点也不会是最靠近超平即使以后支持向量集发生变化，该点也不会是最靠近超平面的点，则可以确定该样本不是支持向量；经过多次迭代面的点，则可以确定该样本不是支持向量；经过多次迭代后，如果样本的拉格朗日乘子一直为非常大的后，如果样本的拉格朗日乘子一直为非常大的C C常数，即使常数，即使以后支持向量集发生变化，该点也不会远离超平面，则可以后支持向量集发生变化，该点也不会远离超平面，则可以确定该样本是上边界处的支持向量以确定该样本是上边界处的支持向量SVM寻优寻优算法算法2022-7-24Chap8 SVM Zhongzhi Shi74活动

49、向量集选择算法 这样就可以在这样就可以在SMO算法收敛前，提前将边界上的点从训算法收敛前，提前将边界上的点从训练样本集中剔除，逐渐缩小参加训练的活动样本集，从而练样本集中剔除，逐渐缩小参加训练的活动样本集，从而减少减少SMO算法对核缓存空间的要求，提高训练速度。算法对核缓存空间的要求，提高训练速度。训练开始前，训练活动集样本初始化为全部训练样本。每训练开始前，训练活动集样本初始化为全部训练样本。每经过一定次数的迭代（比如迭代经过一定次数的迭代（比如迭代1000次），如果算法还没次），如果算法还没有收敛，应检查活动集中的向量，检查是否有训练样本可有收敛，应检查活动集中的向量，检查是否有训练样本可

50、以不参加迭代运算。以不参加迭代运算。检查完当前活动向量集中所有样本后，产生了新的活动向检查完当前活动向量集中所有样本后，产生了新的活动向量集。如果新的活动向量集的样本数减少一成以上（含一量集。如果新的活动向量集的样本数减少一成以上（含一成），则可以收缩当前活动向量集，用新的活动向量集替成），则可以收缩当前活动向量集，用新的活动向量集替换当前活动向量集。当活动向量集的样本数减少到一定的换当前活动向量集。当活动向量集的样本数减少到一定的程度，对核缓存空间的要求不是很大的时候，继续减少训程度，对核缓存空间的要求不是很大的时候，继续减少训练样本对训练速度的提高就非常有限了，这时就没有必要练样本对训练速