支持向量机——中科院计算所智能开放室曾立.pptx

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