SVM简介.pptx

支持向量机简介 supportvectormachine 苏志铭2015 5 20 Outline SVM简介线性分类器线性分类器求解核函数松弛变量SVM的多分类总结 SVM简介 支持向量机 因其英文名为supportvectormachine 故一般简称SVM 支持向量机是Cortes和Vapnik于1995年首先提出的 它在解决小样本 非线性及高维模式识别中表现出许多特有的优势 并能够推广应用到函数拟合等其他机器学习问题中 支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的 根据有限的样本信息在模型的复杂性 即对特定训练样本的学习精度 Accuracy 和学习能力 即无错误地识别任意样本的能力 之间寻求最佳折衷 以期获得最好的推广能力 VC维 对函数类的一种度量 可以简单的理解为问题的复杂程度 VC维越高 一个问题就越复杂 结构风险 结构风险为经验风险与置信风险之和 经验风险 代表了分类器在给定样本上的误差 置信风险 代表了我们在多大程度上可以信任分类器在未知文本上分类的结果 线性分类器 通俗来讲 SVM是一种二类分类模型 其基本模型定义为特征空间上的间隔最大的线性分类器 其学习策略便是间隔最大化 最终可转化为一个凸二次规划问题的求解 以右图为例 在一个二维平面内 有两个类别的离散样本点 一条直线将两类样本分开 一个线性函数 如果能将样本完全正确分开 这些数据即为线性可分 线性函数在一维空间为一个点 二维空间是一条直线 三维空间里是一个平面 如果不关注维数 线性函数被统称为 超平面 线性分类器 假设有一个线性函数 我们可以取阈值为0 如果有一个样本需要判别 如果 判断该样本属于类别C1 如果 判断该样本属于类别C2 等于的时候就拒绝判断 于是 图中中间那条直线就可以表达为 即 这个函数也被叫分类面 但是 很容易看出 中间那条分界线并不是唯一的 只要稍微旋转一下 仍然可以正确分类两类数据 或者 稍微平移一下 通常使用叫做 分类间隔 的指标来找到最优分类面 线性分类器 通过一个分类面 可以将上图中两类样本分开 平面两边数据的类别y可以分别用1和 1表示 定义一个样本点到超平面的函数间隔为 超平面关于数据集的函数间隔为其中的最小值 那么 当 yi同时大于0 当 yi同时小于0 所以 现在把w和b进行一下归一化 即用w w 和b w 分别代替原来的w和b 那么间隔就可以写成这个式子正好是解析几何中 点xi到直线的距离公式 推广一下 那么就是样本点xi到分类超平面的距离 线性分类器 i b 0 i b 0 线性分类器 当用归一化的w和b代替原值之后的间隔有一个专门的名称 叫做几何间隔 几何间隔所表示的正是点到超平面的欧氏距离 以上是单个点到某个超平面的距离定义 同样可以定义一个点的集合 就是一组样本 到某个超平面的距离为此集合中离超平面最近的点的距离 下面的图更加直观的展示出了几何间隔的现实含义 对一个数据点进行分类 当超平面离数据点的 间隔 越大 分类的确信度也越大 所以 为了使得分类的确信度尽量高 需要让所选择的超平面能够最大化这个 间隔 值 线性分类器的解 选择一个最优分类超平面的问题 即最大化几何间隔的问题 固定间隔 即超平面的函数间隔 那么要使几何间隔最大化 即最大 也就是 实际上 对于这个目标函数 经常利用另一个完全等价的函数代替 线性分类器的解 很容易看出当 w 0的时候就得到了目标函数的最小值 反映在图中 就是H1与H2两条直线间的距离无限大 这个时候 所有的样本点 无论正样本还是负样本 都跑到了H1和H2中间 所有的样本都不可分了 造成这种结果的原因是在描述问题的时候只考虑了目标 而没有加入约束条件 约束条件就是在求解过程中必须满足的条件 体现在我们的问题中就是样本点必须在H1或H2的某一侧 或者至少在H1和H2上 而不能跑到两者中间 我们前文提到过把间隔固定为1 这是指把所有样本点中间隔最小的那一点的间隔定为1 线性分类器的解 按照间隔的定义 满足这些条件就相当于让下面的式子总是成立 因此我们的两类分类问题也被我们转化成了它的数学形式 一个带约束的最小值的问题 subjectto因此 满足上面公式的分类面就是最优分类面 过在平行于分类面的的超平面H1和H2上的训练样本 即使得上式等号成立的训练样本 称为支持向量 线性分类器的解 求解上述的约束优化问题是一个二次凸规划问题 由于目标函数和约束条件都是凸的 根据最优化理论 这一问题存在全局最小解 应用Lagrange乘子法并满足KKT条件 Karush Kuhn Tucher 求得因此 分类函数为 对于新点x的预测 只需要计算它与训练数据点的内积即可 表示向量内积 此外 所谓SupportingVector也在这里显示出来 事实上 所有非SupportingVector所对应的系数 都是等于零的 因此对于新点的内积计算实际上只要针对少量的 支持向量 而不是所有的训练数据即可 线性分类器的解 为什么非支持向量对应的等于零呢 直观上来理解的话 就是这些 后方 的点 正如我们之前分析过的一样 对超平面是没有影响的 由于分类完全有超平面决定 所以这些无关的点并不会参与分类问题的计算 因而也就不会产生任何影响了 计算过程中 通过Lagrangemultiplier得到的目标函数 注意到如果xi是支持向量的话 上式中红颜色的部分是等于0的 因为支持向量的函数间隔等于1 而对于非支持向量来说 函数间隔会大于1 因此红颜色部分是大于零的 而又 i是非负的 为了满足最大化 i必须等于0 这也就是这些非支持向量的点的局限性 核函数 之前一直在讨论的线性分类器 只能对线性可分的样本做处理 如果提供的样本线性不可分 结果很简单 线性分类器的求解程序会无限循环 永远也解不出来 这必然使得它的适用范围大大缩小 而它的很多优点我们实在不原意放弃 怎么办呢 是否有某种方法 让线性不可分的数据变得线性可分呢 举个例子 我们把横轴上a点到b点间的红色部分里的所有点定为正类 两边黑色部分定为负类 那么显然找不到一个线性函数 即一条直线 二维空间的线性函数 将其分开 但是 我们可以找到一条曲线 如右图 它的函数表达式为 核函数 问题是 这个函数并不是一个线性函数 但是 如果新建向量 y y1 y2 y3 1 x x2 1 2 3 c0 c1 c2 这样g x 就可以转化为f y ay 在任意维度的空间中 这种形式的函数都是一个线性函数 只不过其中的a和y都是向量罢了 原来在二维空间中一个线性不可分的问题 映射到四维空间后 变成了线性可分的 因此这也形成了我们最初想解决线性不可分问题的基本思路 向高维空间转化 使其变得线性可分 那么 是否可以找到一种映射 将输入空间映射到高维特征空间 最终在高维特征空间中构造出最优分离超平面 从而把平面上本身不好分的非线性数据分开呢 对于非线性的情况 SVM的处理方法是选择一个核函数 通过将数据映射到高维空间 来解决在原始空间中线性不可分的问题 核函数 在线性不可分的情况下 支持向量机首先在低维空间中完成计算 然后通过核函数将输入空间映射到高维特征空间 最终在高维特征空间中构造出最优分离超平面 从而把平面上本身不好分的非线性数据分开 如图所示 一堆数据在二维空间无法划分 从而映射到三维空间里划分 核函数 如果原始数据是不可线性划分的 按照公式 是无法进行正确分类的 那么就按照某种映射 将x映射为 x 以同样的映射 将w映射为 w 那么得到线性函数 它可将原问题可分 但是 如果先将数据映射到高纬空间 再进行内积计算 可能导致维数灾难 所以引进核函数来简化映射空间中的内积运算 先内积 再用核函数计算使得结果与上式结果相同 高维空间的内积运算转化为低维输入空间的核函数计算 即分类函数为 因此 尽管给出线性不可分的问题 通过选定核函数 就可以当做线性分类器使用 核函数 用不同核函数可以导致不同的支持向量机 常用的几种核函数有 线性核函数多项式核函数高斯核函数 径向基核函数 Sigmoid核函数 松弛变量 如果使用核函数向高维空间映射后 问题仍然是线性不可分 如图 用黑圈圈起来的蓝点就将本来线性可分的问题变得不可分 这个点偏离正常点很远 可能是噪点 但是在SVM模型中 本来就只用到了支持向量 噪点的存在影响会很大 为了处理这种情况 SVM允许数据点在一定程度上偏离超平面 那么 在有松弛的情况下 其实噪点也属于支持向量 不同的支持向量拉格朗日参数的值不同 松弛变量 原来 我们的约束条件为 现在考虑到一些特殊点 约束条件变为 其中称为松弛变量 对应数据点xi允许偏离的函数间隔 当然 如果松弛变量任意大的话 那任意的超平面都是符合条件的了 所以 我们在原来的目标函数后面加上一项 使得这些松弛变量的总和也要最小 其中C为惩罚因子 松弛变量 完整的式子为 这个式子有这么几点要注意 一是并非所有的样本点都有一个松弛变量与其对应 实际上只有 离群点 才有 或者也可以这么看 所有没离群的点松弛变量都等于0 二是松弛变量的值实际上标示出了对应的点到底离群有多远 值越大 点就越远 三是惩罚因子C决定了你有多重视离群点带来的损失 显然当所有离群点的松弛变量的和一定时 你定的C越大 对目标函数的损失也越大 此时就暗示着你非常不愿意放弃这些离群点 最极端的情况是你把C定为无限大 这样只要稍有一个点离群 目标函数的值马上变成无限大 马上让问题变成无解 四是惩罚因子C不是一个变量 整个优化问题在解的时候 C是一个你必须事先指定的值 松弛变量 并不是每一个松弛变量都必须使用相同的惩罚因子C 可以对不同利群点采用不同的C值 来表明样本的重视程度 重要的样本C就取大点 反之取小点 对付数据集偏斜问题的方法之一就是在惩罚因子上作文章 那就是给样本数量少的负类更大的惩罚因子 表示我们重视这部分样本 因此我们的目标函数中因松弛变量而损失的部分就变成了 其中i 1 p都是正样本 j p 1 p q都是负样本 libSVM这个算法包在解决偏斜问题的时候用的就是这种方法 那C 和C 怎么确定呢 它们的大小是试出来的 参数调优 但是它们的比例可以有些方法来确定 咱们先假定说C 是5这么大 那确定C 的一个很直观的方法就是使用两类样本数的比来算 SVM的多分类 SVM是一种典型的两类分类器 但现实中要解决的往往是多分类问题 几种方法 一对多方法 One Against The Rest 如果有k类 在某一类和其他k 1类间建立超平面 建立k个SVM分类器 每个SVM分类器将某一类的数据从其他类的数据中鉴别出来 但是 有 数据集偏斜 问题 而且每次训练都用到了所有样本 一对一方法 One Against One 为任意两个类构建超平面 即k类需要训练k k 1 2个SVM分类器 测试时采用投票 投票类别最多的为测试类别 但是如果k太大 训练和决策时就会很耗时 SVM决策树 SVMDecisionTree 将SVM与二叉树结合 构成多类分类器 形似有向无环图 也叫DAGSVM 缺点是 如果某个节点出错 那么错误就会在后续节点延续 SVM的多分类 DAGSVM举例 在分类时 我们就可以先问分类器 1对5 如果它回答5 我们就往左走 再问 2对5 这个分类器 如果它还说是 5 我们就继续往左走 这样一直问下去 就可以得到分类结果 好处在哪 我们其实只调用了4个分类器 如果