《SVM概念和应用》PPT课件.ppt

SupportVectorMachine支持向量机 报告人 吕玉生日期 2008年4月10日 内容 SVM的理论基础线性判别函数和判别面最优分类面支持向量机LIBSVM简介实验 SVM的理论基础 传统的统计模式识别方法只有在样本趋向无穷大时 其性能才有理论的保证 统计学习理论 STL 研究有限样本情况下的机器学习问题 SVM的理论基础就是统计学习理论 传统的统计模式识别方法在进行机器学习时 强调经验风险最小化 而单纯的经验风险最小化会产生 过学习问题 其推广能力较差 推广能力是指 将学习机器 即预测函数 或称学习函数 学习模型 对未来输出进行正确预测的能力 SVM的理论基础 过学习问题 某些情况下 当训练误差过小反而会导致推广能力的下降 例如 对一组训练样本 x y x分布在实数范围内 y取值在 0 1 之间 无论这些样本是由什么模型产生的 我们总可以用y sin w x 去拟合 使得训练误差为0 SVM的理论基础 根据统计学习理论 学习机器的实际风险由经验风险值和置信范围值两部分组成 而基于经验风险最小化准则的学习方法只强调了训练样本的经验风险最小误差 没有最小化置信范围值 因此其推广能力较差 Vapnik与1995年提出的支持向量机 SupportVectorMachine SVM 以训练误差作为优化问题的约束条件 以置信范围值最小化作为优化目标 即SVM是一种基于结构风险最小化准则的学习方法 其推广能力明显优于一些传统的学习方法 SVM的理论基础 由于SVM的求解最后转化成二次规划问题的求解 因此SVM的解是全局唯一的最优解SVM在解决小样本 非线性及高维模式识别问题中表现出许多特有的优势 并能够推广应用到函数拟合等其他机器学习问题中 线性判别函数和判别面 一个线性判别函数 discriminantfunction 是指由x的各个分量的线性组合而成的函数两类情况 对于两类问题的决策规则为如果g x 0 则判定x属于C1 如果g x 0 则判定x属于C2 线性判别函数和判别面 方程g x 0定义了一个判定面 它把归类于C1的点与归类于C2的点分开来 当g x 是线性函数时 这个平面被称为 超平面 hyperplane 当x1和x2都在判定面上时 这表明w和超平面上任意向量正交 并称w为超平面的法向量 超平面 线性判别函数和判别面 判别函数g x 是特征空间中某点x到超平面的距离的一种代数度量 线性判别函数和判别面 广义线性判别函数 在一维空间中 没有任何一个线性函数能解决下述划分问题 黑红各代表一类数据 可见线性判别函数有一定的局限性 线性判别函数和判别面 广义线性判别函数 如果建立一个二次判别函数g x x a x b 则可以很好的解决上述分类问题 决策规则仍是 如果g x 0 则判定x属于C1 如果g x 0 则判定x属于C2 线性判别函数和判别面 线性判别函数和判别面 广义线性判别函数 最优分类面 SVM是从线性可分情况下的最优分类面发展而来的 基本思想可用下图的两维情况说明 图中 方形点和圆形点代表两类样本 H为分类线 H1 H2分别为过各类中离分类线最近的样本且平行于分类线的直线 它们之间的距离叫做分类间隔 margin 所谓最优分类线就是要求分类线不但能将两类正确分开 训练错误率为0 而且使分类间隔最大 推广到高维空间 最优分类线就变为最优分类面 最优分类面 设线性可分的样本集 D维空间中的线性判别函数 这样分类间隔就等于 因此要求分类间隔最大 就要求最大 而要求分类面对所有样本正确分类 就是要求满足 最优分类面 求最优分类面 最大间隔法 已知 求解 目标 最优分类面这是一个二次凸规划问题 由于目标函数和约束条件都是凸的 根据最优化理论 这一问题存在唯一全局最小解 原问题 最优分类面 凸集和凸函数 凸函数的极小 若问题有局部解 则这个局部解是整体解 最优分类面 首先建立Lagrange函数 最终可得到 对偶问题 最优分类面 线性不可分的情况下 可以条件中增加一个松弛项成为 已知 求解 目标 最优分类面 折衷考虑最少错分样本和最大分类间隔 就得到广义最优分类面 其中 C 0是一个常数 它控制对错分样本惩罚的程度 支持向量机 上节所得到的最优分类函数为 该式只包含待分类样本与训练样本中的支持向量的内积运算 可见 要解决一个特征空间中的最优线性分类问题 我们只需要知道这个空间中的内积运算即可 对非线性问题 可以通过非线性变换转化为某个高维空间中的线性问题 在变换空间求最优分类面 这种变换可能比较复杂 因此这种思路在一般情况下不易实现 支持向量机 核 支持向量机 支持向量机 核函数的选择 支持向量机 SVM方法的特点 非线性映射是SVM方法的理论基础 SVM利用内积核函数代替向高维空间的非线性映射 对特征空间划分的最优超平面是SVM的目标 最大化分类边界的思想是SVM方法的核心 支持向量是SVM的训练结果 在SVM分类决策中起决定作用的是支持向量 SVM是一种有坚实理论基础的新颖的小样本学习方法 它基本上不涉及概率测度及大数定律等 因此不同于现有的统计方法 从本质上看 它避开了从归纳到演绎的传统过程 实现了高效的从训练样本到预报样本的 转导推理 transductiveinference 大大简化了通常的分类和回归等问题 支持向量机 SVM方法的特点 SVM的最终决策函数只由少数的支持向量所确定 计算的复杂性取决于支持向量的数目 而不是样本空间的维数 这在某种意义上避免了 维数灾难 少数支持向量决定了最终结果 这不但可以帮助我们抓住关键样本 剔除 大量冗余样本 而且注定了该方法不但算法简单 而且具有较好的 鲁棒 性 这种 鲁棒 性主要体现在 增 删非支持向量样本对模型没有影响 支持向量样本集具有一定的鲁棒性 有些成功的应用中 SVM方法对核的选取不敏感 支持向量机 SVM本质上是两类分类器 常用的SVM多值分类器构造方法有 LIBSVM简介 LIBSVM是台湾大学林智仁 LinChih Jen 副教授等开发设计的一个简单 易于使用和快速有效的SVM模式识别与回归的软件包 他不但提供了编译好的可在Windows系列系统的执行文件 还提供了源代码 方便改进 修改以及在其它操作系统上应用 该软件还有一个特点 就是对SVM所涉及的参数调节相对比较少 提供了很多的默认参数 利用这些默认参数就可以解决很多问题 支持向量机 支持向量机 前面介绍的C SVM 有两个相互矛盾的目标 最大化间隔和最小化训练错误 其中的常数C起着调和这两个目标的作用 定性地讲 C值有着明确的含义 选取大的C值 意味着更强调最小化训练错误 但定量地讲 C值本身并没有确切的意义 所以C值的选取比较困难 为此 人们提出了这个改进的方法 1 间隔错误样本的个数所占总样本数的份额的上界 2 支持向量的个数所占总样本点数的份额的下界 支持向量机 不需要类标号 用于支持向量的密度估计和聚类 支持向量机 回归问题 就是在训练样本上找到一个函数 它可以从输入域近似映射到实数值上 输出值不再是二值 在SVM中 回归问题被转化为分类问题来解 支持向量机 实验 包括分类与回归对dst aah chjsh三种可视音素进行采样 每种类型20张样本图片 首先转化为灰度图像 然后截取口形部位的80 60区域 再使用Gaussian金字塔将其分解为原来的四分之一 保存为LIBSVM的格式的文件 包括用于分类和回归的文件 这样把维数降至1200维 对于分类的参数使用 c2000 回归的参数使用 s4 c100000分类采用的是一对一的方式 实验 实验结果 分类的结果还算可以接受 回归计算出来的口形程度值和真实值有时相差很大