第5章-支持向量机和核函数讲课资料

《第5章-支持向量机和核函数讲课资料》由会员分享，可在线阅读，更多相关《第5章-支持向量机和核函数讲课资料（114页珍藏版）》请在金锄头文库上搜索。

1、第5章支持向量机和核函数 支持向量机方法是建立在统计学习理论的VC维理论和结构化风险最小原理基础上 结构化风险结构化风险 经验风险 置信风险经验风险 分类器在给定样本上的误差置信风险 分类器在未知样本上分类的结果的误差 推广能力是指 将学习机器 即预测函数 或称学习函数 学习模型 对未来输出进行正确预测的能力 过学习问题 某些情况下 当训练误差过小反而会导致推广能力的下降 例如 对一组训练样本 x y x分布在实数范围内 y取值在 0 1 之间 无论这些样本是由什么模型产生的 我们总可以用y sin w x 去拟合 使得训练误差为0 机器学习本质上就是一种对问题真实模型的逼近 但真实模型一定是

2、不知道的 那么我们选择的假设与问题真实解之间究竟有多大差距 我们就没法得知 这个与问题真实解之间的误差 就叫做风险 我们选择了一个假设后 真实误差无从得知 但我们可以用某些可以掌握的量来逼近它 最直观的想法就是使用分类器在样本数据上的分类的结果与真实结果 因为样本是已经标注过的数据 是准确的数据 之间的差值来表示 这个差值叫做经验风险Remp w 以前的机器学习方法都把经验风险最小化作为努力的目标 但后来发现很多分类函数能够在样本集上轻易达到100 的正确率 在真实分类时却一塌糊涂 即所谓的推广能力差 或泛化能力差 原因 选择了一个足够复杂的分类函数 能够精确的记住每一个样本 但对样本之外的数

3、据一律分类错误 统计学习引入了泛化误差界的概念 就是指真实风险应该由两部分内容刻画 一是经验风险 代表了分类器在给定样本上的误差 二是置信风险 代表了我们在多大程度上可以信任分类器在未知样本上分类的结果 很显然 第二部分是没有办法精确计算的 因此只能给出一个估计的区间 也使得整个误差只能计算上界 而无法计算准确的值 置信风险与两个量有关 一是样本数量 显然给定的样本数量越大 我们的学习结果越有可能正确 此时置信风险越小 二是分类函数的VC维 VC维越大 推广能力越差 置信风险会变大 2 经验非线性方法如人工神经网络 ANN 利用已知样本建立非线性模型 缺点 缺乏一种统一的数学理论 统计学习理论

4、 针对小样本统计估计和预测的最佳理论 1 统计学习理论基本思想 由贝尔实验室Vapnik于1992年首次提出 研究小样本下机器学习规律的理论 针对小样本统计问题 建立了一套新的理论体系 基本思想 折衷考虑经验风险和推广的置信界限 取得实际期望风险的最小化 即根据有限样本信息在模型复杂性和学习能力之间寻求最佳折中 两大核心概念 VC维和结构风险最小化 在这一理论基础上 发展了一种新的通用模式识别方法 支持向量机 SVM 发展迅速 已经在许多领域都取得了成功的应用 VC维的概念 VC是取Vapnik和Chervonenkis名字的首字而成 描述函数集或学习机器的复杂性的指标 即描述机器学习能力的重

5、要指标 样本数量 给定的样本数量越大 学习结果越有可能正确 此时置信风险越小 分类函数的VC维 VC维越大 推广能力越差 置信风险会变大 提高样本数量 降低VC维 降低置信风险 以前机器学习的目标是降低经验风险 要降低经验风险 就要提高分类函数的复杂度 导致VC维很高 VC维高 置信风险就高 所以 结构风险也高 这是SVM比其他机器学习具有优势的地方 VC维的引入 打散 若存在一个有h个样本的样本集 被一函数集里的某个函数按照所有可能的2h种形式分为两类 则称函数集能够把样本数为h的样本集打散 shattering 若对于任意的样本数 总能找到一个样本集能够被这个函数集打散 则函数集的VC维就

6、是无穷大 函数集的vc维 用这个函数集中的函数所能够打散的最大样本集的样本数目 也就是说 如果存在h个样本的样本集能够被函数集打散 而不存在有h 1个样本的样本集能被函数集打散 则函数集的VC维就是h 例如 3个样本被线性分类器打散的情况 有2h 23 8种分类形式 能打散 VC维为3 不能打散 VC维是目前为止对函数集学习性能的最好描述指标 但遗憾的是目前尚没有通用的关于如何计算任意函数集的VC维的理论 VC维是目前为止对函数集学习性能的最好描述指标 但遗憾的是目前尚没有通用的关于如何计算任意函数集的VC维的理论 结构风险最小化的思想 Vapnik证明 期望风险与经验风险之间的关系满足如下公

7、式 其中n表示样本数 h为学习机器的VC维 称为置信区间 是随n h增大而减小的函数 VC维h越大 越大 经验风险和期望风险之间的偏差越大 这样即使在经验误差很小的情况下 其推广误差会越大 将函数集构造为一个函数子集序列S1 S2 Sk 使各个子集按照VC维的大小排列 h1 h2 hk 在每个子集中寻找的最小经验风险 随子集复杂度增加而减小 在子集间折衷考虑经验风险和置信界限 取得实际风险的最小 结构风险最小就是根据函数集的性质将它划分成一系列嵌套的子集 学习问题就是选择最好的子集 根据推广能力 和在子集中选择最好的函数 根据经验风险 SVM是一种比较好地实现了结构风险最小化思想的方法 分类超

8、平面的一些基本概念 W是超平面H的法向量 决定超平面的方向 b决定超平面的位置 两类问题 g x 表示分类面 2 支持向量机算法 找到一个超平面 使得它能够尽可能多的将两类数据点正确的分开 同时使分开的两类数据点距离分类面最远 目标 解决方法 构造一个在约束条件下的优化问题 SVM是利用核函数将输入向量映射到一个高维特征空间 并在该空间内构造一个最优超平面来逼近分类函数 最优分类超平面的构造最终可以归结为二次寻优问题 由于SVM在解决小样本 非线性及高维模式识别问题中表现出许多特有的优势 因此受到广泛的关注 最优分类面 1 线性可分情况 对于线性可分问题 是在经验风险为零时 最小化置信范围 使

9、两类无错误的分开 且使两类的分类空隙最大 前者是保证经验风险尽可能小 后者是使真实风险最小 SVM问题的数学表示 线性可分情况 设两类线性可分训练样本集为 d维空间 线性判别函数的一般形式为 存在超平面为 使得训练样本中的正类输入和负类输入分别位于该超平面两侧 决策面方程 许多决策平面都可以将两类样本分开 应选择哪一个呢 存在参数 w b 使得 目标 最优分类面 满足条件 经验风险最小 错分最少 推广能力最大 空白最大 如图所示 假定划分直线的法方向已给定 直线H1是一条以w 为法向量且能正确划分两类样本的直线 如何寻找最优面 这样的直线并不唯一 如果平行推移直线H1 直到碰到某类训练点 就可

10、得到两条极端直线H2和H3 在直线H2和H3之间的平行直线都能正确分类 显然在H2和H3中间的那条直线H为最好 以上给出了在已知法向量w 情况下构造划分直线的方法 这样就把问题归结为寻求法向量w及b 要让H满足wTx b 0 则必须寻找最佳 w b 判别函数归一化 假如H可表示为 因为H在中间 显然H2可表示为 H3可表示为 两边同除以k 令 则H为 H2为 H3为 该过程称为分类直线的规范化过程 即判别函数归一化 此时两条直线H2和H3之间的间隔为 如前所述 对于适当的法向量 会有两条极端的直线 这两条直线之间有间隔 最优分类直线就应该是两直线间隔最大的那个法向量所表示的直线 分类平面应使两

11、类之间的间隔最大 归一化后分类面方程应满足 即 如何寻找w及b 对于任意样本x有 图中分类间隔为 SVM基本思想 就是最大化分类间隔 因此等价于最小化 因此 求取最优平面问题就转化为优化问题 因对于所有样本 1 满足式 1 且使最小的分类面就是最优分类面 使式 1 等号成立的样本 即H2和H3上的样本 就叫支持向量 由上节可知我们的目标函数 用另一个完全等价的目标函数来代替 那就是 如果直接来解这个求最小值问题 很容易看出当 w 0的时候就得到了目标函数的最小值 反映在图中 就是H2与H3两条直线间的距离无限大 这个时候 所有的样本点 无论正样本还是负样本 都跑到了H2和H3中间 而我们原本的

12、意图是 H2右侧的被分为正类 H3左侧的被分为负类 位于两类中间的样本则拒绝分类 这下可好 所有样本点都进入了无法分类的灰色地带 造成这种结果的原因是在描述问题的时候只考虑了目标 而没有加入约束条件 体现在我们的问题中就是样本点必须在H2或H3的某一侧 或者至少在H2或H3上 而不能跑到两者中间 约束是什么 求极值 可用拉格朗日乘子法求解 引入拉格朗日乘子 i 0 设Lagrange函数为 2 使式 1 等号成立的样本 即H2和H3上的样本 就叫支持向量 2 式是一个二次优化问题 存在唯一最优解 把该式分别对w b求偏导 并使其等于零 即 将上面两式带入 2 可得到下式 于是 对w和b求拉个朗

13、日函数的极小值来求解最优分类面问题 可转化为在如下约束条件下 为样本数目 对 i求解下列函数的最大值 为与约束条件对应的拉格朗日乘子 训练样本之间的内积 这也是一个二次函数寻优问题 存在唯一解 解中只有支持向量对应的系数 i为非零值 即 只有支持向量影响最终的划分结果 若为最优解 则 任取 可求得 可用支持向量求得 由任一支持向量通过式 1 可求得b 则最优分类函数为 6 待分样本x与支持向量xi的内积 2 线性不可分情况 约束条件 7 8 引入松弛项 使得允许存在错分样本 对应的优化问题变为 在约束条件下 求式 7 的极小值 可得线性不可分情况下的最优分类面 称为广义最优分类面 对 i求解下

14、式 的最大值 同理 利用拉格朗日乘子法 可把求解广义最优分类面问题转化为在如下约束条件下 C为可调参数 即惩罚因子 C越大 惩罚越重 称这种SVM为C SVM 训练样本之间的内积 C越大 表示分类越严格 允许错分的样本受到的限制越大 错分的样本数少 越过拟合 在保留松驰项 i的基础上 引入一新的参数V来控制支持向量的数目和误差 改进算法 V SVM 约束条件 对应的对偶问题 在如下约束条件下 求最小值 即 9 相应的判别函数也变为 原始的SVM是两类分类器 对于多类分类问题需进行扩展 常用的方法有一类对余类和一类对一类 10 多类SVM算法 SVM本质上是两类分类器 常用的SVM多值分类器构造

15、方法有 3 非线性SVM 可通过某种非线性变换转化为另一空间的线性问题 在此线性空间求解最优或广义最优分类面 即将非线性问题映射为线性问题 3 非线性SVM 可通过某种非线性变换转化为另一空间的线性问题 在此线性空间求解最优或广义最优分类面 即将非线性问题映射为线性问题 注意到无论训练样本是否线性可分 求解其对应的优化问题以及最终得到的最优分类超平面都只需计算原始特征空间中样本间的内积 而不需要知道从原始特征空间到高维特征空间的非线性映射的具体形式 总结 目标函数 约束条件 目标函数 约束条件 拉格朗日乘数法可将问题转化为对偶问题 目标函数 约束条件 线性分类 巧妙之处 原问题 二次凸优化问题

16、 对偶问题对偶问题求解 更巧妙的地方 未知数据x的预测 只需要计算它与训练数据点的内积即可 非线性分类 对于以上所述的SVM 处理能力还是很弱 仅仅能处理线性可分的数据 如果数据线性不可分的时候 我们就将低维的数据映射向更高的维次 以此使数据重新线性可分 这转化的关键便是核函数 非线性分类 找不到一个超平面 二维空间 直线 将其分割开来 而很自然的想到可以用一个椭圆将数据分为两类 Z1 X1 Z2 X12 Z3 X2 Z4 X22 Z5 X1X2 X1 X2 Z1 Z2 Z3 Z4 Z5 即将 R2空间映射到R5空间 此时 总能找到一个超平面wTZ b 0wT a1 a2 a3 a4 a5 T b a6使得数据很好的分类 映射过后的空间 onecasestudy 核函数引入 对于非线性的情况 SVM的处理方法是选择一个核函数 通过将数据映射到高维空间 来解决在原始空间中线性不可分的问题 由于核函数的优良品质 这样的非线性扩展在计算量上并没有比原来复杂多少 当然 这要归功于核方法 除了SVM之外 任何将计算表示为数据点的内积的方法 都可以使用核方法进行非线性扩展 onecasestudy