支持向量分类机原理

,*,支持向量分类机原理,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,支持向量分类机原理,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,支持向量分类机原理,SVM,有关概念介绍,SVM,分类问题的数学表示和推导,简单的最优分类面,广义最优分类面,非线性最优分类面,SVM,分解算法,支持向量分类机原理,SVM是一种基于统计学习理论的机器学习方法，它是由Boser,Guyon, Vapnik在COLT-92上首次提出，从此迅速开展起来，目前已经在许多智能信息获取与处理领域都取得了成功的应用。,支持向量分类机原理,思想： 通过某种事先选择的非线性映射核函数将输入向量映射到一个高维特征空间，在这个空间中寻找最优分类超平面。使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。,途径： 构造一个约束条件下的优化问题，具体说是一个带线性不等式约束条件的二次规划问题(constrained quadratic programing),求解该问题，构造分类超平面，从而得到决策函数。,支持向量分类机原理,SVM,有关概念介绍,SVM,分类问题的数学表示和推导,简单的最优分类面,广义最优分类面,非线性最优分类面,SVM,分解算法,a,y,est,denotes +1,denotes -1,f,x,f,(,x,) = sgn(,w. x,+ b),Copyright 2001, 2003, Andrew W. Moore,How would you classify this data?,a,y,est,denotes +1,denotes -1,f,x,f,(,x,) = sgn(,w. x,+ b),Copyright 2001, 2003, Andrew W. Moore,How would you classify this data?,a,y,est,denotes +1,denotes -1,f,x,f,(,x,) = sgn(,w. x,+ b),Copyright 2001, 2003, Andrew W. Moore,How would you classify this data?,a,y,est,denotes +1,denotes -1,f,x,f,(,x,) = sgn(,w. x,+ b),Copyright 2001, 2003, Andrew W. Moore,How would you classify this data?,支持向量分类机原理,：训练集包含 个样本点：,说明： 是输入指标向量，或称输入，或称模式，其分,量称为特征，或属性，或输入指标；,是输出指标，或输出.,问题：对一个新的模式 ，推断它所对应的输出 是1还是-1.,实质：找到一个把 上的点分成两局部的规那么.,2,维空间上的分类问题,) n,维空间上的分类问题,.,根据给定的训练集,其中， ，寻找 上的一个实,值函数 ，用决策函数,判断任一模式 对应的 值,.,可见，分类学习机,构造决策函数的方法,(,算法,),，,两类分类问题 多类分类问题,线性分类学习机 非线性分类学习机,分类学习方法,SVM,分类问题大致有三种：线性可分问题、近似线性可分问题、线性不可分问题。,支持向量分类机原理,考虑图1.2.1(a) 上的线性可分的分类问题.,这里有许多直线 能将两类点正确分开.,如何选取 和 ？,简单问题：设法方向 已选定，如何选取 ？,解答： 选定 平行直线 极端直线 和,取 和 的中间线为分划直线,如何选取 ？,对应一个 ，有极端直线 ，称 和 之间的距,离为“间隔.显然应选使“间隔最大的 。,最大间隔法的直观导出,数学语言描述：,给定适当的法方向 后，这两条极端直线 可表示为,调整 ，使得,令 ，那么两式可以等价写为,与此相应的分划直线表达式,:,如何计算分划间隔？,考虑,2,维空间中极端直线之间的间隔情况,求出两条极端直线的距离：,分划直线表达式为 “间隔 为,极大化“间隔的思想导致求解以下对变量 和 的最优化问题,说明：只要我们求得该问题的最优解 ，从而构造分划,超平面 ，求出决策函数 。,上述方法对一般 上的分类问题也适用.,原始问题,支持向量分类机原理,为求解原始问题，根据最优化理论，我们转化为对偶问题来求解,对偶问题,为原始问题中与每个约束条件对应的,Lagrange,乘子。这是,一个不等式约束条件下的二次函数寻优问题，存在唯一解,支持向量分类机原理,计算 ，选择 的一个正分量,并据此计算,事实上， 的每一个分量 都与一个训练点相对应。而分划超平面仅仅依赖于 不为零的训练点 ，而与对应于 为零的那些训练点无关。,称 不为零的这些训练点的输入 为,支持向量,(SV),构造分划超平面,决策函数,根据最优解,支持向量分类机原理,不要求所有训练点都满足约束条件 ，为此,对第 个训练点 引入,松弛变量,(Slack Variable) ,把约束条件放松到 。,表达了训练集被错分的情况，可采用 作,为一种度量来描述错划程度。,两个目标,：,1.,间隔 尽可能大,2.,错划程度 尽可能小,显然，当 充分大时，样本点 总可以满足以上约束条件。,然而事实上应防止 太大，所以需在目标函数对 进展惩罚,即“软化 约束条件,支持向量分类机原理,因此，引入一个,惩罚参数,，新的目标函数变为,:,表达了经历风险，而 那么表达了表达能力。所以,惩罚参数 实质上是对经历风险和表达能力匹配一个裁决。,当 时，近似线性可分SVC的原始问题退化为线性可分,SVC的原始问题。,支持向量分类机原理,设训练集 ，其中,2.,选择适当的惩罚参数 ，构造并求解最优化问题,3.,计算 ，选择 的一个分量 ，并据此,计算出,4.,构造分划超平面,决策函数,求得,支持向量分类机原理,例子,:,支持向量分类机原理,设训练集 ，其中,假定可以用 平面上的二次曲线来分划：,现考虑把,2,维空间 映射到,6,维空间的变换,上式可将,2,维空间上二次曲线映射为,6,维空间上的一个超平面：,支持向量分类机原理,可见，只要利用变换,(2.3.4),，把 所在的,2,维空间的两类输入点映射到 所在的,6,维空间，然后在这个,6,维空间中，使用线性学习机求出分划超平面：,最后得出原空间中的二次曲线：,怎样求,6,维空间中的分划超平面？,(,线性支持向量分类机,),支持向量分类机原理,需要求解的最优化问题,其中,支持向量分类机原理,在求得最优化问题的解 后，得到分划超平面,其中,最后得到决策函数,或,线性分划,非线性分划代价：,2,维空间内积,6,维空间内积,支持向量分类机原理,为此，引进函数,有,比较(2.3.6)和(2.3.7)，可以发现,这是一个重要的等式，提示,6,维空间中的内积,可以通过计算 中,2,维空间中的内积 得到。,支持向量分类机原理,给定训练集后，决策函数仅依赖于,而不需要再考虑非线性变换,如果想用其它的非线性分划方法，那么可以考虑选择其它形式,的函数 ，一旦选定了函数，就可以求解最优化问题,得 ，而决策函数,实现非线性分划的思想,决策函数,其中,核函数,(,核或正定核,),定义,设 是 中的一个子集。称定义在 上的函数,是核函数,(,正定核或核,),，如果存在着从 到某一个,空间 的映射,使得,其中 表示 中的内积,核函数的选择,多项式内核,径向基函数内核,RBF,Sigmoind,内核,目前研究最多的核函数主要有三类：,得到,q,阶多项式分类器,每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定,包含一个隐层的多层感知器，隐层节点数是由算法自动确定,支持向量分类机原理,SVM,有关概念介绍,SVM,分类问题的数学表示和推导,简单的最优分类面,广义最优分类面,非线性最优分类面,SVM,分解算法,Edgar Osuna(Cambridge,MA)等人在IEEE NNSP97发表了An Improved Training Algorithm for Support Vector Machines ,提出了SVM的分解算法，即将原问题分解为假设干个子问题，按照某种迭代策略，通过反复求解子问题，最终使得结果收敛于原问题的最优解。,传统的利用二次型优化技术解决对偶问题时：,需要计算存储核函数矩阵。当样本点数较大时，需要很大的存储空间。例如：当样本点超过4000时，存储核函数矩阵就需要多达128兆内存；,SVM在二次型寻优过程中要进展大量的矩阵运算，通常寻优算法占用了算法时间的主要局部。,SVM,分解算法,考虑去掉Lagrange乘子等于零的训练样本不会影响原问题的解，采用一局部样本构成工作样本集进展训练，移除其中的非支持向量，并把训练结果对剩余样本进展检验，将不符合KKT条件的样本与本次结果的支持向量合并成为一个新的工作集。然后重新训练，如此重复获得最优结果。,例如：基于这种思路的 算法。,根据子问题的划分和迭代策略的不同，大致分为：,块算法,(Chunking Algorithm),：,SVM,分解算法,将工作样本集的大小固定在算法速度可以容忍的限度内，迭代过程选择一种适宜的换入换出策略，将剩余样本中的一局部与工作样本集中的样本进展等量交换，即使支持向量的个数超过工作样本集的大小，也不改变工作样本集的规模，而只对支持向量中的一局部进展优化。,例如: 算法,根据子问题的划分和迭代策略的不同，大致分为：,2.,固定工作样本集,(Osuna et al.),：,SVM,分解算法,K-,类模式识别问题是为样本集,多类问题中的,SVM,构造一个决策函数。由于SVM是解决两类分类问题的有效方法，因此用SVM解多类问题的思路通常是将其转化为两类问题，然后对结果进展处理。常用方法有：,One-against-the-rest,方法：在第,k,类和其他第,k-1,类之间构造超平面。,One-against-one,方法：为任意两个类构建超平面，共需,K(K+1)/2,个,SVM,K-class SVM,：同时为所有类构造一个分类超平面,Thank you!,谢谢大家！,结 语,