logo资料库

支持向量机原理.pdf

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.48M 资料格式：pdf 举报 版权申诉
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
资料共11页，剩余部分请下载后查看
    支持向量机 1、准备知识 1.1 VC 维 VC 维的传统定义是：对一个指示函数集，如果存在 H 个样本能够被函数集中的函数按所有可能的 2H 种形式分开，则称函数集能够把 H 个样本打散，函数集的 VC 维就是它能打散的最大样本数目 H。若对任 意数目的样本都有函数能将它们打散，则函数集的 VC 维是无穷大，有界实函数的 VC 维可以通过用一定的 阈值将它转化成指示函数来定义。 VC 维反映了函数集的学习能力，VC 维越大则学习机器越复杂（容量越大），遗憾的是，目前尚没有通 用的关于任意函数集 VC 维计算的理论，只对一些特殊的函数集知道其 VC 维。一般地，对于 n 维空间 Rn 中，最多只能有 n 个点是线性独立的，因此 Rn 空间超平面的 VC 维是 N+1。但在非线性情况下学习机器的 VC 维通常是无法计算的，但实际中在应用统计学习理论时，可通过变通的办法巧妙地避开直接求 VC 维的 问题。 1.2 经验风险最小化原则 学习问题可以一般地表示为变量 y 与 x 之间存在的未知依赖关系，即遵循某一未知的联合概率分布 。机器学习问题就是根据 n 个独立同分布观测样本在一组函数{ 中求一个最优的函数 对依赖关系进行估计，使期望风险 最小。其中{ 称为预测函数集； 为函数的广义参数。 为由于用 进行预测 造成的损失，不同类型的学习有不同形式的损失函数。 经验风险最小化（Empirical risk minimization，ERM）原则即用样本定义经验风险： 在早期神经网络研究中，人们总是把注意力集中在如何设计学习算法使 更小，但发现在某些情 况下当训练误差过小时反而会导致推广能力下降。出现过学习问题的原因一是学习样本不充分，二是学习 机器设计不合理。因此在有限样本情况下，经验风险最小化并不一定意味着期望风险最小，学习机器的复杂 性和推广能力之间存在着矛盾。 (,)Fyx(,)fxw(,)fxw()(,(,))(,)RLyfdFy=wxwx(,)fxww(,(,))Lyfxw(,)fxw11()(,(,))nempiiiRLyfn==wxw()empRw
    1.3 结构风险最小化原则 传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限的时候是不合理的，只考虑到了 经验风险。正确的是，应该同时考虑最小化经验风险和置信范围。置信范围反映了真实风险和经验风险差值 的上届，反映了结构复杂所带来的风险，它和学习机器的 VC 维 h 及训练样本数 n 有关。 统计学习理论提出一种新的策略，即把函数集构造为一个函数子集序列，使各个子集按照 VC 维的大小 排列；在每个子集中寻找最小经验风险，在子集间折衷考虑经验风险和置信范围，取得实际风险的最小。这 种思想称作结构风险最小化(Structural Risk Minimization)，即 SRM 准则。 图 1 为结构风险最小化原理图。真实风险的界是经验风险和置信范围的和，随着结构元素序号的增加， 经验风险将减小，而置信范围将增加。最小的真实风险上界是在结构的某个适当元素上取得的。综合考虑经 验风险与置信区间的变化，可以求得最小风险边界，它所对应的函数集的中间子集 S*可以作为具有最佳泛 化能力的函数集合。 图 1 结构风险最小化原理图 实现 SRM 原则的两种思路： 1)在每个子集中求最小经验风险，然后选择使最小经验风险和置信范围之和最小的子集。 2)设计函数集的某种结构，使每个子集中都能取得最小的经验风险，然后只需选择适当的子集使置信范 围最小，则这个子集中使经验风险最小的函数就是最优函数。（支持向量机方法实际就是这种思路的实现） 2、支持向量机原理 支持向量机(Support Vector Machine，SVM)是 Corinna Cortes 和 Vapnik 等于 1995 年首先提出的，它在 解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学 习问题中。
    在机器学习中，支持向量机是与相关的学习算法有关的监督学习模型，可以分析数据，识别模式，用于 分类和回归分析。 支持向量机方法是建立在统计学习理论的 VC 维理论和结构风险最小原理基础上的，根据有限的样本 信息在模型的复杂性（即对特定训练样本的学习精度）和学习能力（即无错误地识别任意样本的能力）之间 寻求最佳折中，以求获得最好的推广能力。 支持向量机包括分类支持向量机（SVC）和回归支持向量机（SVR）。 2.1 分类支持向量机 2.1.1 线性可分支持向量机 支持向量机的方法是从线性可分线性可分情况下的最优分类超平面提出的。 对于两类分类问题，假定 n 个样本的训练集 能被一个 超平面 没有错误地分开，并且离超平面之间的距离（称为 Margin，分类间隔）是最大的， 该超平面就称为最优超平面，如图 2 所示。 图 2 支持向量机最优超平面示意图 为了最大化超平面的分类间隔，应该最小化 ，并且保证 和 之间没有样本存在，即训 练集中所有的 n 个样本都应满足 因此支持向量机的目的就是采用下式构建分类超平面对所有样本的正确分类： (,)|,{1,1},1,2,,niiiiDyyin=−=xxR:0Hb+=wx2T=www1H2H1,11,1iiiibyby++=++−=−wxwx
    这是一个凸二次规划问题，其解可通过求解下面的拉格朗日函数获得，即 式中 为拉格朗日乘子。分别对 w 和 b 求偏导，并令它们等于 0，带入上式可得拉格朗日函数的对偶 形式，更容易数值求解。因此构建最优超平面的问题可转化为一个较简单的对偶二次规划问题 这是一个不等式约束下的凸二次规划问题，存在唯一解。若 为其最优解，则 即最有 分类面的权系数向量是训练样本向量的线性组合。 称训练集 D 中的输入为支持向量（Support Vector，SV），如果它对应的 。 图 3 支持向量示意图 通常对多数样本而言，其对应的 将为零。支持向量是训练集中最能提供信息的数据（样本），通常是 全体样本中的很少一部分，这就是支持向量机具有的一个非常重要的性质——稀疏性。稀疏性对于大大降 2,,11minmin22Tbb=wwwww.. ()10iistyb+−wx11(,,)()12nTiiiiLbyb==−+−wαwwwx0i1111max()2nnniijijijiijyy===−αxx10.. 0,1,2,,niiiiystin===*i**1=niiiiy=wx*0i*i
    低模型的复杂性有着非常重要的意义。 根据 Karush-Kuhn-Tucker（KKT）条件（拉格朗日乘子与不等式约束的乘积），这个优化问题的解还必 须满足 通过选择不为零的 ，代入上式可求解分类阈值 。 求解上述问题后得到的最优分类函数为 对线性可分情况，采用上述的最优分类超平面算法，就可以获得经验风险误差为零，同时使分类间隔最 大，即保证推广性的界的置信范围最小，从而最终可以使真实风险最小。但对于线性不可分和噪声情况，线 性可分支持向量机并不能完全获得期望风险最小，甚至会出现过学习效果。广义线性支持向量机能够解决 此类问题。 2.1.2 广义线性支持向量机 为了在线性不可分和噪声情况下构造最优分类超平面，在约束条件中引入非负松弛变量 ，则训练 集 D 中的所有 n 个样本应满足 求解广义最优分类超平面，可转化为 式中 C(C>0)称为规则化参数或惩罚参数，决定了经验风险和复杂性（VC 维）之间的权衡。该式同样可用构 造拉格朗日函数求解。 2.1.3 非线性支持向量机 为了在非线性情况下实现支持向量机，必须利用核特征空间的非线性映射算法，其基本思想是通过一个 非线性映射把输入映射到一个新的高维特征空间，然后在此高维空间中使用线性支持向量机进行分类和回 归估计。 ***()10iiiyb+−=wx(1,,)in=*i*b****1()sgn()sgn()niiiiifbyb==+=+xwxxx0i1,11,1iiiiiibyby++−=++−+=−wxwx,,11min2nTibiC=+wξww()10.. 0,1,2,,iiiiybstin+−+=wx
    特征空间定义：假定模式 属于输入空间 ，即 ，通过映射 将输入空间 映射到一个新的空 间 ，则 称作特征空间。 将原来的样本 转化为高维样本 ，此时只要把原来线性情 况下的内积运算 转换成即可 。实际上需要的就是定义变换后内积运算，而不必知道 变换的具体形式。 根据 Hilbert-Schmidt 理论，只要核函数 满足 Mercer 条件：对任意给定函数 ，当 有限时， 就对应某一空间的内积 。则此时的优化问题变为如下形式 而分类决策函数变为 在非线性支持向量机中，不同的内积核函数构成不同的算法。目前常用的核函数有以下三种： 多项式核函数： 高斯径向基核(RBF)函数： Sigmoid 核函数： 2.2 回归支持向量机 要建立回归算法就需要选择适当的损失函数。为了使 SVR 仍能保持稀疏性，引入一种新型损失函数， 即 不敏感损失函数，它使支持向量回归估计具有鲁棒性且具有良好的稀疏性。 定义线性 不敏感损失函数为 xXxXφX()=Zφx:xXZ11(,),,(,)nnyyxx11[(),],,[(),]nnyyφxφx()ijxx[()()]ijφxφx(,)Kxy()gx2()bagdxx(,)ijKxx[()()]ijφxφx1111max(,)2nnniijijijiijyyK===−αxx**1()sgn()niiiifyKb==+xxx(,)(1), 0TdijijKd=+xxxx2(,)exp(), 0ijijK=−−xxxx(,)tanh(), 0,0TijijKkk=−xxxx()0,(,),(,)(,)(,), (,)yfLyfyfyfyf−=−=−−−xxxxx
    图 4 线性 不敏感损失函数的误差示意图 如果目标值 y 和经过学习构造的回归估计函数 的预测值之间的差别小于 ，则认为该点预测值 损失为 0，如图 4 所示。SVR 算法中把位于 -带及其以外的样本点作为支持向量。 对于线性 SVR，用线性回归函数 来估计训练样本集 D，损失函数采用线性 不敏感 损失函数，因此最优化问题为 当约束条件不可实现时，为了允许一定的误差存在，引入松弛变量 和 ，最优化问题转换为 式中， 表示置信范围，体现了函数集的表达能力； 体现了经验风险；C 是对经验风险 和置信范围这两者进行折中，表示对超出误差 的样本的惩罚程度。最小化这两项的加权之和体现了结构风 险最小化的思想。 通过构造拉格朗日函数转换为对偶二次规划问题： (,)fx()()fb=+xwx2,1min2bww.. iiiibystyb+−−−wxwxi*i*2*,,,11min()2niibiC=++wξξw**.. 0,0iiiiiiiibystyb+−+−−+wxwx2w*1()niii=+*****,11111max()()()()()2nnnniiiiiiijjijiiijy====−−+−−−ααxx
    满足 或 的 称为支持向量。最后得到的线性 SVR 函数为 对于非线性回归支持向量机，与 2.1.3 节类似，通过非线性变换转化为某个高维空间的线性问题，同时 引入核函数，减小计算复杂度，最终得到的非线性 SVR 函数为 2.3 支持向量机算法的改进 支持向量机算法的改进，一方面是在求解的效率方面进行改进，例如块算法、分解算法、并行学习算法 原始空间中的学习算法、集成学习算法等；另一方面在参数选择方面进行改进，目前智能优化支持向量机参 数的方法主要有遗传算法、蚁群算法和粒子群优化算法。 3、支持向量机的使用 支持向量机中的一大亮点是在传统的最优化问题中提出了对偶理论，主要有最大最小对偶及拉格朗日 对偶。 SVM 的关键在于核函数。低维空间向量集通常难于划分，解决的方法是将它们映射到高维空间。但这 个办法带来的困难就是计算复杂度的增加，而核函数正好巧妙地解决了这个问题。也就是说，只要选用适当 的核函数，就可以得到高维空间的分类函数。在 SVM 理论中，采用不同的核函数将导致不同的 SVM 算法。 在确定了核函数之后，由于确定核函数的已知数据也存在一定的误差，考虑到推广性问题，因此引入了 松弛系数以及惩罚系数两个参变量来加以校正。在确定了核函数基础上，再经过大量对比实验等将这两个 系数取定，该项研究就基本完成，适合相关学科或业务内应用，且有一定能力的推广性。 使用支持向量机的基本步骤如下： 1）将数据转换为支持向量机包的格式 每个样本都应包含输入和输出值，支持向量机要求每一条数据被表示为实数向量。 2）对数据进行简单的缩放(归一化处理) 归一化的主要优点是避免较大的数字属性对较小的数字属性的支配作用。通俗地说，如果属性 1 的数 *1*()=00.. 01,2,,niiiiiCstCin=−=*0i0iix*1()()()()niiijifbb==+=−+xwxxx()*1()()()()niiijifbKb==+=−+xwφxxx
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料