周雄辉-人工智能-支持向量机.ppt

第六章 支持向量机 1 引言 一. SVM (Support Vector Machine)的历史 神经网络分类器，Bayes分类器等是基于大样本学习的分 类器。 Vapnik 等从1960年开始关于统计学习理论的研究。统计学 习理论是关于小样本的机器学习理论。 1992年支持向量机首次被引入。1995年Vapnik发展了支持 向量机理论。支持向量机是基于统计学习理论的一种实用 的机器学习方法。 二. SVM的应用 数据与文本分类 系统建模及预测 模式识别(图像及语音识别，生物特征识别) 异常检测(入侵检测，故障诊断) 时间序列预测 2 统计学习理论 一. 两分类问题 给定 l 个观测值: , i = 1, 2, ., l Rn 每个观测值与一个标记相连: , i = 1, 2, ., l 土1 对于 (2-类) 分类, 建立一个函数: : 表示函数的参数 使得 f 能正确地分类未学习过的样本 第 2 类 第 1 类 二.期望风险与实验风险 期望风险最小化 其中 x, y的联合概率 P(x, y) 是未知的 实验风险最小化 实验风险是由在训练集上测得的平均误差所确定的 如果训练样本的个数是有限的,则实验风险最小化的方法不保证有高 推广能力 三. VC理论 VC (Vapnik-Chervonenkis)维数 分类函数 的集合F的VC维数 p=VCdim(F) 定义 (VapnikChervonenkis). 函数 的集合F的VC 维数是p, 当且仅当存在点集 xipi=1 使得这些点能够被所有 2p 种可能的 分类方式分开,且不存在集合 xiqi=1 ( q p )满足这一性质。 在 n 维空间中,超平面集合的VC维数等于n + 1 。 VC维数刻画了“可能近似正确”意义上的学习能力。 例:VC维数 四. 结构风险最小化 VC 理论引入期望风险的边界, 它依赖于实验风险与 F的能力。 这些边界的最小化导出结构风险最小化原理:实验风险与 VC 可信度之和为最 小 其中 h 与VC 维数有关,是能力概念的一种测度 支持向量机是基于结构风险最小化原理构造的一种学习机 3 线性支持向量机 一. 两分类问题: 线性分割情形 许多决策边界可以分割这 些数据点出为两类 我们选取哪一个? 第 1 类 第 2 类 坏的决策边界的例子 第 1 类 第 2 类 第 1 类 第 2 类 好的决策边界: 间隔大 决策边界离两类数据应尽可能远 最大化间隔 m 第 1 类 第 2 类 m 二. 最优化问题 设 x1, ., xn 为数据集, yi 1,-1 为xi 的类标记 要求决策边界正确地分类所有的点 于是得到一个带有约束的优化问题 将上述最优化问题转换成其对偶问题: 取Lagrange函数 (w,b;)=1/2w2 n i=1 i (yi(w,xi)+b 1) 则对偶问题由 max W()=max (minw,b (w,b;) 给出。由 minw,b (w,b;) 得 / b=0 n i=1 iyi=0 / w =0 w=n i=1 iyixi 于是得到对偶问题 这是一个二次规划 (QP) 问题 ai的全局最大值总可以求得 W的计算 解得*=argmin 1/2n i=1n i=1 i jyiyj n k =1 k w*=n i=1 iyixi, b *=1/2 其中Xr 与xs满足 xr,xs 0, yr= 1,ys=1 则 f(x)= sgn( +b) 三. 解的性质 许多的 ai 为零 w 只是少数数据的线性组合 具有非零 ai 的 xi 称为支持向量 (SV) 决策边界仅由SV确定 设 tj (j=1, ., s) 为支持向量的指标,于是 为了检测一个新数据 z 计算 如果 WTZ+ b 0, 则 z 属于第一类;否则,属于第二类。 a6=1.4 四. 几何解释 第1类 第2类 a1=0.8 a2=0 a3=0 a4=0 a5=0 a7=0 a8=0.6 a9=0 a10=0 4 非线性支持向量机 一. 非线性分割问题 关键思想: 为了解决非线性分割问题, 将 xi 变换到一个高维空间。 输入空间: xi 所在的空间 特征空间: 变换后 f(xi) 的空间 如何变换 ? 利用一个适当的变换f, 使分类变得容易些。 特征空间中的线性算子等价于输入空间中的非线性算 子。 变换可能出现的问题 难以得到一个好的分类且计算开销大 SVM同时解决这两个问题 最小化 |w|2 能得到好的分类 利用核函数技巧可以进行有效的计算 f( ) f( ) f( ) f( ) f( ) f( ) f( ) f( ) f() f( ) f( ) f( ) f( ) f( ) f( ) f( ) f( ) f( ) f( ) 特征空间输入空间 特征空间变换举例(I) 特征空间变换举例(II) 特征空间变换举例(III) 小结 通过一个函数，通过把输入的特征值转换 到高维空间，可将问题转换为高维空间可 分的问题(在高维空间可以用线性函数解决 的问题) 多项式型: 核函数的类型 线性型: 径向基函数型: 指数径向基函数型: 软件 关于 SVM 的实现可以在下列网址找到 /software.html SVMLight 是最早的 SVM 软件之一 SVM 的各种 Matlab toolbox 也是可利用的 LIBSVM 可以进行多类别分类 CSVM 用于SVM分类 rSVM 用于SVM回归 mySVM 用于SVM分类与回归 M-SVM 用于SVM多类别分类 实际使用案例 数据：GSE2034 (276个乳腺癌病人的基因表 达数据，以及这些病人的预后数据)：来源 ：NCBI GEO 目标：用svm分类器来预测病人的生存风险 * 27 方法(不标准，只是为了演示) (1) t-test选择特征 (2)使用这些特征数据和类标签(假设特征数据 为data,标签数据为label)训练，得到分类模型： n