王磊西南财经大学.ppt

《王磊西南财经大学.ppt》由会员分享，可在线阅读，更多相关《王磊西南财经大学.ppt（73页珍藏版）》请在三一文库上搜索。

1、2019/8/1,1,王磊 西南财经大学,支持向量机 Support Vector Machines,2019/8/1,2,内容提要,统计学习方法概述 统计学习问题 学习过程的泛化能力 支持向量机 SVM寻优算法 应用,2019/8/1,3,期望风险,学习到一个假设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进行预测而造成的损失。不同类型的学习问题有不同形式的损失函数。,2019/8/1,4,而

2、对train set上产生的风险Remp(w)被称为经验风险(学习的训练误差):,首先Remp(w)和R(w)都是w的函数，传统概率论中的定理只说明了(在一定条件下)当样本趋于无穷多时Remp(w)将在概率意义上趋近于R(w)，却没有保证使Remp(w)最小的点也能够使R(w) 最小(同步最小)。,经验风险,2019/8/1,5,根据统计学习理论中关于函数集的推广性的界的结论，对于两类分类问题中的指示函数集f(x, w)的所有函数(当然也包括使经验风险员小的函数)，经验风险Remp(w)和实际风险R(w)之间至少以不下于1-(01)的概率存在这样的关系:,结构风险,2019/8/1,6,VC维

3、(函数的多样性),为了研究经验风险最小化函数集的学习一致收敛速度和推广性，SLT定义了一些指标来衡量函数集的性能，其中最重要的就是VC维(Vapnik-Chervonenkis Dimension)。 VC维：对于一个指示函数（即只有0和1两种取值的函数）集，如果存在h个样本能够被函数集里的函数按照所有可能的2h种形式分开，则称函数集能够把h个样本打散，函数集的VC维就是能够打散的最大样本数目。 如果对任意的样本数，总有函数能打散它们，则函数集的VC维就是无穷大。,2019/8/1,7,VC维(函数的多样性),2019/8/1,8,VC维（续）,一般而言,VC维越大, 学习能力就越强,但学习机

4、器也越复杂。 目前还没有通用的关于计算任意函数集的VC维的理论,只有对一些特殊函数集的VC维可以准确知道。 N维实数空间中线性分类器和线性实函数的VC维是n+1。 Sin(ax)的VC维为无穷大。 ,2019/8/1,9,VC维（续）,Open problem: 对于给定的学习函数集,如何用理论或实验的方法计算其VC维是当前统计学习理论研究中有待解决的一个难点问题。,2019/8/1,10,推广性的界,统计学习理论地研究了经验风险和实际风险之间的关系,也即推广性的界。 根据SLT中关于函数集推广性界的理论,对于指示函数集中所有的函数,经验风险 和实际风险 之间至少以概率 满足如下关系: 其中，

5、h是函数集的VC维,n是样本数。,2019/8/1,11,推广性的界（续1）,学习机器的实际风险由两部分组成: 训练样本的经验风险 置信范围(同置信水平 有关,而且同学习机器的VC维和训练样本数有关。 在训练样本有限的情况下,学习机器的VC维越高,则置信范围就越大,导致实际风险与经验风险之间可能的差就越大。,2019/8/1,12,结构风险最小化,传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的,因此，需要同时最小化经验风险和置信范围。 统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集

6、间折衷考虑经验风险和置信范围,取得实际风险的最小。这种思想称作结构风险最小化(Structural Risk Minimization)，即SRM准则。,2019/8/1,13,一般的学习方法(如神经网络)是基于 Remp(w) 最小,满足对已有训练数据的最佳拟和,在理论上可以通过增加算法（如神经网络）的规模使得Remp(w) 不断降低以至为0。 但是,这样使得算法（神经网络）的复杂度增加, VC维h增加,从而(h/l)增大,导致实际风险R(w)增加,这就是学习算法的过拟合(Overfitting).,过学习,2019/8/1,14,过学习Overfitting and underfittin

7、g,Problem: how rich class of classifications q(x;) to use.,underfitting,overfitting,good fit,Problem of generalization: a small emprical risk Remp does not imply small true expected risk R.,2019/8/1,15,支持向量机,SVM是一种基于统计学习理论的机器学习方法，它是由Boser,Guyon, Vapnik在COLT-92上首次提出，从此迅速发展起来 Vapnik V N. 1995. The Nat

8、ure of Statistical Learning Theory. Springer-Verlag, New York 564 Vapnik V N. 1998. Statistical Learning Theory. Wiley-Interscience Publication, John Wiley&Sons, Inc 目前已经在许多智能信息获取与处理领域都取得了成功的应用。,2019/8/1,16,支持向量机的特色,用间隔定量地定义了置信风险：间隔越大，置信风险越小，间隔越小，置信风险越大 用参数C实现了经验风险与置信风险的折中 最优分类超平面只由少数支持向量决定，问题具有稀疏性

9、模型为凸二次规划模型，没有陷入局部最优解的问题，任何局部最优解都是全局最优解 通过使用核方法，具备了强大的非线性处理能力,2019/8/1,17,线性分类器,a,yest,2019/8/1,18,线性分类器,f,x,a,yest,denotes +1 denotes -1,f(x,w,b) = sign(w. x - b),How would you classify this data?,2019/8/1,19,线性分类器,f,x,a,yest,denotes +1 denotes -1,f(x,w,b) = sign(w. x - b),How would you classify thi

10、s data?,Copyright 2001, 2003, Andrew W. Moore,2019/8/1,20,线性分类器,f,x,a,yest,denotes +1 denotes -1,f(x,w,b) = sign(w. x - b),How would you classify this data?,Copyright 2001, 2003, Andrew W. Moore,2019/8/1,21,线性分类器,f,x,a,yest,denotes +1 denotes -1,f(x,w,b) = sign(w. x - b),How would you classify this

11、data?,Copyright 2001, 2003, Andrew W. Moore,2019/8/1,22,最大间隔,f,x,a,yest,denotes +1 denotes -1,f(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 SVM,Copyright 2001, 2003, Andrew W.

12、Moore,2019/8/1,23,分类超平面,Training set: (xi, yi), i=1,2,N; yi+1,-1 Hyperplane: wx+b=0 This is fully determined by (w,b),2019/8/1,24,考虑 上的线性可分的分类问题. 这里有许多直线 能将两类点正确分开. 如何选取 和 ？ 简单问题：设法方向 已选定，如何选取 ？ 解答： 选定 平行直线 极端直线 和 取 和 的中间线为分划直线 如何选取 ？ 对应一个 ，有极端直线 ，称 和 之间的距 离为“间隔”.显然应选使“间隔”最大的 。,最大间隔法的直观导出,2019/8/1,2

13、5,数学语言描述,调整 ，使得,令 ，则两式可以等价写为,与此相应的分划直线表达式:,给定适当的法方向 后，这两条极端直线 可表示为,2019/8/1,26,如何计算分划间隔？ 考虑2维空间中极端直线之间的间隔情况,求出两条极端直线的距离：,2019/8/1,27,wx+b=0,wx+b=1,wx+b=-1,wx+b1,wx+b1,Maximum margin summing up,Given a linearly separable training set (xi, yi), i=1,2,N; yi+1,-1 Minimise |w|2 Subject to This is a quadr

14、atic programming problem with linear inequality constraints. There are well known procedures for solving it ,2019/8/1,28,支持向量,The training points that are nearest to the separating function are called support vectors. What is the output of our decision function for these points?,2019/8/1,29,分划直线表达式为

15、 “间隔” 为 极大化“间隔”的思想导致求解下列对变量 和 的最优化问题 说明：只要我们求得该问题的最优解 ，从而构造分划 超平面 ，求出决策函数 。 上述方法对一般 上的分类问题也适用.,原始问题,2019/8/1,30,Margin =,H1平面：,H2平面：,(2),(1),2019/8/1,31,求解原始问题,为求解原始问题，根据最优化理论，我们转化为对偶问题来求解,对偶问题,为原始问题中与每个约束条件对应的Lagrange乘子。这是 一个不等式约束条件下的二次函数寻优问题，存在唯一解,2019/8/1,32,线性可分问题,计算 ，选择 的一个正分量 , 并据此计算,事实上， 的每一个

16、分量 都与一个训练点相对应。而分划超平面仅仅依赖于 不为零的训练点 ，而与对应于 为零的那些训练点无关。,称 不为零的这些训练点的输入 为支持向量(SV),构造分划超平面 ,决策函数,根据最优解,2019/8/1,33,近似线性可分问题,不要求所有训练点都满足约束条件 ，为此 对第 个训练点 引入松弛变量(Slack Variable) , 把约束条件放松到 。,体现了训练集被错分的情况，可采用 作 为一种度量来描述错划程度。,两个目标：1. 间隔 尽可能大 2. 错划程度 尽可能小,显然，当 充分大时，样本点 总可以满足以上约束条件。 然而事实上应避免 太大，所以需在目标函数对 进行惩罚,（

17、即“软化” 约束条件）,2019/8/1,34,因此，引入一个惩罚参数 ，新的目标函数变为:,体现了经验风险，而 则体现了表达能力。所以 惩罚参数 实质上是对经验风险和表达能力匹配一个裁决。 当 时，近似线性可分SVC的原始问题退化为线性可分 SVC的原始问题。,近似线性可分问题,2019/8/1,35,(广义)线性支持向量分类机算法,设已知训练集 ，其中,2. 选择适当的惩罚参数 ，构造并求解最优化问题,3. 计算 ，选择 的一个分量 ，并据此 计算出,4. 构造分划超平面 ,决策函数,求得,2019/8/1,36,非线性分类,例子:,2019/8/1,37,Non-linear Class

18、ification,What can we do if the boundary is nonlinear ?,Idea:,transform the data vectors to a space where the separator is linear,2019/8/1,38,Non-linear Classification,The transformation many times is made to an infinite dimensional space, usually a function space. Example: x cos(uTx),2019/8/1,39,No

19、n-linear SVMs,Transform x (x) The linear algorithm depends only on xxi, hence transformed algorithm depends only on (x)(xi) Use kernel function K(xi,xj) such that K(xi,xj)= (x)(xi),2019/8/1,40,设训练集 ，其中 假定可以用 平面上的二次曲线来分划：,现考虑把2维空间 映射到6维空间的变换,上式可将2维空间上二次曲线映射为6维空间上的一个超平面：,非线性分类,2019/8/1,41,需要求解的最优化问题,其

20、中,非线性分类,2019/8/1,42,在求得最优化问题的解 后，得到分划超平面,其中,最后得到决策函数,或,线性分划非线性分划 代价：2维空间内积6维空间内积,非线性分类,2019/8/1,43,为此，引进函数,有,比较(2)和(3)，可以发现,这是一个重要的等式，提示6维空间中的内积 可以通过计算 中2维空间中的内积 得到。,非线性分类,2019/8/1,44,实现非线性分类的思想,给定训练集后，决策函数仅依赖于 而不需要再考虑非线性变换 如果想用其它的非线性分划办法，则可以考虑选择其它形式 的函数 ，一旦选定了函数，就可以求解最优化问题,得 ，而决策函数,2019/8/1,45,决策函数

21、,其中,实现非线性分类的思想,2019/8/1,46,设 是 中的一个子集。称定义在 上的函数,是核函数(正定核或核)，如果存在着从 到某一个 空间 的映射,使得,其中 表示 中的内积,核函数(核或正定核)定义,2019/8/1,47,多项式内核 径向基函数内核RBF Sigmoind内核,目前研究最多的核函数主要有三类：,得到q 阶多项式分类器,每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定,包含一个隐层的多层感知器，隐层节点数是由算法自动确定,核函数的选择,2019/8/1,48,多项式内核,The kind of kernel represents the inner pr

22、oduct of two vector(point) in a feature space of dimension. For example,2019/8/1,49,SVM中的QP问题,凸二次规划(QP)问题，这保证了其局部最优解就是全局最优解,2019/8/1,50,通用技术,梯度下降 牛顿法 共轭梯度 内点法 思想：数值法，迭代，改变的策略不同 困难：需要存储nn的核矩阵k(xi, xj),2019/8/1,51,QP问题快速求解技术,KKT条件 Chunking算法 Decomposition算法 SMO算法 改进的SMO算法 流行软件采用的算法 算法收敛性 思想：分解成一系列QP子问

23、题，每次只修改一部分i,2019/8/1,52,最优解的充分必要条件KKT条件,存在，使得,其中, ui是当前SVM对第i个训练样本的输出,2019/8/1,53,Chunking算法,Boser,B.E., Guyon,I.M. and Vapnik,V.N. A training algorithm for optimal margin classifiers. 5th Annual ACM Workshop on COLT, Pittsburgh, PA, 1992. “块算法”基于的是这样一个事实，即去掉Lagrange乘子等于零的训练样本不会影响原问题的解。 具体的作法是，选择一部分

24、样本构成工作样本集进行训练，剔除其中的非支持向量，并用训练结果对剩余样本进行检验，将不符合训练结果（一般是指违反KKT条件）的样本（或其中的一部分）与本次结果的支持向量合并成为一个新的工作样本集，然后重新训练。如此重复下去直到获得最优结果。,2019/8/1,54,Chunking算法,动机：支持向量数目较少 算法 初始化：置零 初始化工作集： 选择一定数目的i的任意子集 更新 ：在工作集上用通用技术解QP子问题 更新工作集：SVs + M个违反KKT条件最严重的样本 若满足停止条件，则返回；否则，转到步骤3 缺点：两种情况下支持向量数目很多 问题本身复杂，解不稀疏 训练样本数量巨大,2019

25、/8/1,55,固定工作集算法,Osuna, E., Freund, R. and Girosi, F. An Improved Training Algorithm for Support Vector Machines. In Island, A. (ed), IEEE NNSP, 1997. 将样本集分为两个集合B和N，集合B作为子问题工作样本集进行SVM训练，集合N中所有样本的Lagrange乘子均置为零。把集合B中对应Lagrange乘子为零的样本i（即i = 0，iB）与集合N中的违反KKT条件的样本交换。,2019/8/1,56,固定工作集算法,动机：固定工作集大小 算法： 初始

26、化：置零 初始化工作集： i的任意子集 更新 ：针对原目标函数，以工作集上的i为变量，其他i为常量，用通用技术解QP子问题 更新工作集：用非工作集中违反KKT条件的一个i替换工作集中的任意一个j 若满足停止条件，则返回 ；否则，转到步骤3 缺点 当工作集过小时（小于支持向量数目），可能无法获得最优解。,2019/8/1,57,SMO算法,Platt, J.C. Fast Training of Support Vector Machines Using Sequential Minimal Optimization. In Schlkopf, B., Burges, C. and Smola,

27、 A. (eds), Advances in Kernel Methods: Support Vector Learning. MIT Press, 1999. 固定“Chunking工作集”的大小为2，每次迭代只优化两个点的最小子集且可直接获得解析解，算法流程：,2019/8/1,58,SMO算法,设我们选取了初始值满足了问题中的约束条件。接下来，我们固定，这样W就是和的函数。并且和满足条件： 由于其余参数都是已知固定，因此为了方便，可将等式右边标记成实数值。,2019/8/1,59,SMO算法,进而,2019/8/1,60,参数的求解,最终参数的解为：,其中： 和,2019/8/1,61,

28、问题？,算法如何终止？ KKT条件 对于SMO算法，其中的两个参数如何选择呢？ 随机？启发式规则,一个自然的想法是那些违反KKT最严重的点，他们对间距贡献最大，因此可以通过该启发规则来完成调整参数的选取。（并且此种启发规则计算量小）,2019/8/1,62,流行软件采用的算法,LIBSVM C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2004. 改进的SMO算法 SVMTorch R. Collobert and S. Bengio. SVMTorch: A support vector m

29、achine for large-scale regression and classification problems 改进的SMO算法 SVM-light Joachims, T. Making large-Scale SVM Learning Practical. In Schlkopf, B., Burges, C. and Smola, A. (eds), Advances in Kernel Methods: Support Vector Learning. MIT Press, 1999. 推广的固定工作集算法 ，用最陡可行下降法选取工作集,2019/8/1,63,快速算法还不

30、够快,H. Yu, J. Yang, and J. Han. Classifying Large Data Sets Using SVM with Hierarchical Clusters. KDD03,训练时间（小时）vs. 训练样本数量（LibSVM）,2019/8/1,64,数据集缩减技术,思想：排除非支持向量，识别支持向量 方法： 精确: 如CB-SVM（限于线性SVM） 近似: 如ClusterSVM、随机采样技术等,2019/8/1,65,并行训练算法,基于MTC结构的支持向量机并行训练算法,2019/8/1,66,多类支持向量机,间接方法：通过构造一些二分类支持向量机，然后组合

31、这些二分类器得到多分类支持向量机 一类对一类 一类对余类 有向无环图法（DAGSVM） 纠错输出编码（ECOC） 一次性求解方法 直接方法：直接构造多分类支持向量机,2019/8/1,67,一类对一类,二分类器决策函数:,多分类决策函数: 简单多数投票法,特点: (1) 两分类器个数多k(k-1)/2, 但每一个规模较小； (2) 存在不可分区域。,2019/8/1,68,一类对余类,二分类器决策函数:,多分类决策函数:,特点: (1) 两分类器个数少（k个）, 但每一个规模较大，且会出现两类样本个数不平衡问题； (2) 存在不可分区域。,2019/8/1,69,DAGSVM,训练同一类对一类

32、 决策规则：,分类时,将待判别点输入根结点,每次判别时排除掉最不可能的一个类别,经过k-1次判别后剩下的最后一个即为最终类别。,2019/8/1,70,ECOC多分类方法,将5类分类问题转化为10个两类分类问题。由于每个码位上的分类器只需要做两类分类，所以可以采用SVM作为码位分类器，即需10个分类器。 对于一个新样本，10个SVM的分类结果构成一个码字S，5 个编码中与S汉明距离最小的码字所代表的类别就是这个新样本所属类别。,2019/8/1,71,研究题目： LS-SVM,A. Suykens etc. Least Squares Support Vector Machine Classi

33、fiers， 1998 要求：准备30分钟左右的ppt，讲清楚LS-SVM的原理及特点。,2019/8/1,72,研究题目：Twin SVM方法,Jayadeva等提出一种称为孪生支持向量机(TwinSVM,TSVM)的学习算法.该算法类似于经典SVM算法,但它的目标是构建一对超平面,使得每一类样本离一个超平面尽可能近,而离另一个超平面尽可能远。由于TSVM的计算复杂度仅为经典SVM算法的1/4，成为SVM学习领域的有一个重要算法。 Jayadeva. Twin Support Vector Machines for Pattern Classification. 2007 要求：准备30分钟左右的ppt，讲清楚 Twin SVM的原理及特点。,2019/8/1,73,支持向量回归(SVR),