《支持向量机》PPT课件.ppt

2020 3 26 哈尔滨理工大学网络信息中心 1 支持向量机引导 孙宗宝2006年12月20日 哈尔滨理工大学网络信息中心学术交流 2020 3 26 哈尔滨理工大学网络信息中心 2 支持向量机引导 孙宗宝2006年12月20日 哈尔滨理工大学网络信息中心学术交流 2020 3 26 哈尔滨理工大学网络信息中心 3 内容提要 概述线性可分情况理论线性不可分情况支持向量机模型核函数支持向量机网络 2020 3 26 哈尔滨理工大学网络信息中心 4 SVM简介 90年代中期在统计学习理论的基础上发展起来的一种机器学习方法 Boser Guyon Vapnik 适合有限样本 小样本 问题在很大程度上解决了传统方法 如神经网络 中存在的问题 如过学习 非线性 多维问题 局部极小点问题等统计学习理论和支持向量机被视为机器学习问题的一个基本框架 传统的方法都可以看作是SVM方法的一种实现有坚实的理论基础和严格的理论分析 2020 3 26 哈尔滨理工大学网络信息中心 5 概述 一 向量的内积与超平面 2020 3 26 哈尔滨理工大学网络信息中心 6 概述 二 最优分类平面 2020 3 26 哈尔滨理工大学网络信息中心 7 概述 二维数据最优分类线的基本要求 1 要能将两类样本无错误的分开即使经验风险最小 理论上为零2 要使两类之间的距离最大 也就是使margin最大 从而使实际风险最小 2020 3 26 哈尔滨理工大学网络信息中心 8 概述 我们要做的是什么呢 找到一个超平面 最优分类面 使得它能够尽可能多的将两类数据点正确的分开 同时使分开的两类数据点距离分类面最远 2020 3 26 哈尔滨理工大学网络信息中心 9 H H2 H1 最优分类平面 为最优分类平面的方程 2020 3 26 哈尔滨理工大学网络信息中心 10 SVM原理之线性可分 设线性可分样本集为 xi yi i 1 2 n x Rd y 1 1 是类别标号 则d维空间中线性判别函数的一般形式为 g x w x b分类面方程为 w x b 0 1 2020 3 26 哈尔滨理工大学网络信息中心 11 SVM原理之线性可分 将判别函数进行归一化 使两类所有样本都满足 g x 1 即 使离分类面最近的样本的 g x 1 这样分类间隔就等于2 w 因此间隔最大等价于使 w 或 w 2 最小 而要求分类线对所有样本正确分类 就是要求其满足 yi w xi b 1 0 i 1 2 n 2 2020 3 26 哈尔滨理工大学网络信息中心 12 SVM原理之线性可分 我们解决这样问题的思路是什么呢 首要的就是设法找到解决问题的数学模型 我们的问题是 找到满足上述式 2 且使 w 2的分类面 其实这个分类面就是最优分类面 2020 3 26 哈尔滨理工大学网络信息中心 13 SVM原理之线性可分 支持向量 SV 在那呢 能使式 2 yi w xi b 1 0 i 1 2 n 中等号成立的 也就是位于margin上的样本就是支持向量 2020 3 26 哈尔滨理工大学网络信息中心 14 SVM原理之线性可分 最优分类平面求解的数学模型我们的求解过程显然是一个有约束条件的优化问题 即在式 2 的约束下 求函数 w 1 2 w 2 1 2 w w 3 的最小值 2020 3 26 哈尔滨理工大学网络信息中心 15 SVM原理之线性可分 求解方法 Lagrange乘子法什么是Lagrange乘子法 看一个例子 问题 给你一块面积固定 等于a的平方 板子 问做成什么样的长方体 盒子 它具有最大的体积 2020 3 26 哈尔滨理工大学网络信息中心 16 SVM原理之线性可分 Lagrange乘子法设长方体的三个棱长为x y z 则其体积f为三个边长的乘积 f x y z xyz本问题要求表面积为a的平方 于是长方体的6面的面积可以写成 2xy 2xz 2yz a2即2xy 2xz 2yz a2 0这个问题转化为了有约束条件的优化问题 2020 3 26 哈尔滨理工大学网络信息中心 17 SVM原理之线性可分 Lagrange乘子法解题方法为 1用拉格朗日方法制造一个新函数F2在F中放进一个未知的常数C得到 F xyz C 2xy 2xz 2yz a2 2020 3 26 哈尔滨理工大学网络信息中心 18 SVM原理之线性可分 Lagrange乘子法F对x y z的三个自变量的偏微分分别为零 得到三个新方程式 yz 2C y z 0 xz 2C x z 0 xy 2C x y 0因为自变量仅可能是正数 把上面的式子相除得 x y x z y z y z x y x z 2020 3 26 哈尔滨理工大学网络信息中心 19 SVM原理之线性可分 Lagrange乘子法由此得出只有各个自变量的值相等才可以维持上面的关系 再由约束条件得到它们的值是 x y z a 6 2020 3 26 哈尔滨理工大学网络信息中心 20 SVM原理之线性可分 构造拉格朗日函数 L w b a w w ai yi w xi b 1 其中 ai 0为Lagrange系数 求式 3 的极小值就是对w和b求拉氏函数的极小值 求L对w和b的偏微分 并令其等于0 可转化为对偶问题 在约束条件aiyi 0 ai 0 i 1 2 n之下对ai 0求式 5 的最大值 2020 3 26 哈尔滨理工大学网络信息中心 21 SVM原理之线性可分 W a ai aiajyiyj xi xj 5 若ai 为最优解 则 w i 1 nai yixi 6 即最优分类面的权系数向量式训练样本的线性组合 2020 3 26 哈尔滨理工大学网络信息中心 22 SVM原理之线性可分 这是一个不等式约束的二次函数极值问题 存在唯一解 并且解必须满足 Kuhn Tucker条件 ai yi w xi b 1 0 i 1 n 7 显然 只有支持向量的系数ai不为0 即只有支持向量影响最终的划分结果 这是为什么 2020 3 26 哈尔滨理工大学网络信息中心 23 SVM原理之线性可分 于是式 6 w i 1 nai yixi 可以写成 w aiyixi 可以看出 只有支持向量影响最终的划分结果 最优分类面的权系数向量是训练样本向量的线性组合 8 2020 3 26 哈尔滨理工大学网络信息中心 24 SVM原理之线性可分 若ai 为最优解 求解上述问题后得到的最优分类函数是 f x sgn w x b sgn ai yi xi x b 其中 sgn 为符号函数 b 是分类的阈值 可以由任意一个支持向量用式 2 求得 或通过两类中任意一对支持向量取中值求得 对于给定的未知样本x 只需计算sgn w x b 即可判定x所属的分类 对于非支持向量ai都为0 2020 3 26 哈尔滨理工大学网络信息中心 25 SVM原理之线性不可分 对于线性不可分的样本 希望使误分类的点数最小 为此在式 2 中引入松弛变量 i 0 即 yi w xi b 1 i 0 i 1 2 n 9 yi w xi b 1 0 i 1 2 n 2 2020 3 26 哈尔滨理工大学网络信息中心 26 SVM原理之线性不可分 在式 9 中 对于给定的常数C 求出使 w w w C i 10 取极小值的w b 这一优化问题同样需要变换为用拉格朗日乘子表示的对偶问题 变换的过程与前面线性可分样本的对偶问题类似 结果也几乎完全相同 只是约束条件略有变化 aiyi 0 0 ai C i 1 2 n 11 C反映了在复杂性和不可分样本所占比例之间的折中 2020 3 26 哈尔滨理工大学网络信息中心 27 支持向量机 如果用内积K x x 代替最优分类面中的点积 就相当于把原特征空间变换到了某一新的特征空间 此时优化函数变为 W a ai aiajyiyjK xi xj 相应的判别函数也应变为 f x sgn ai yik xi x b 2020 3 26 哈尔滨理工大学网络信息中心 28 支持向量机 算法的其他条件均不变 这就是支持向量机 所以 原问题就转化成了找SV的问题 而求SV的过程就是解一个二次规划 有约束的 二次规划无局部极值 只有一个最值 所以SV的求解不会有不收敛或者收敛到局部极小的问题 而VC维又保证了机器的容量 不可能过学习 因为机器的结构已经固定 具体的求解方法可以参考运筹学中约束二次规划的求解 2020 3 26 哈尔滨理工大学网络信息中心 29 非线性分类面 非线性可分的数据样本在高维空间有可能转化为线性可分 在训练问题中 涉及到训练样本的数据计算只有两个样本向量点乘的形式使用函数 将所有样本点映射到高为空间 则新的样本集为设函数 内核函数 Kernelfunction 2020 3 26 哈尔滨理工大学网络信息中心 30 一个能实现非线性关系到线性关系变换的实例 取 那么 2020 3 26 哈尔滨理工大学网络信息中心 31 核函数 2020 3 26 哈尔滨理工大学网