支持向量机ppt课件

1、支持向量机（SVM）,什么是支持向量机？,图A给出了一个线性可分数据集（可以在图中画一条直线将两组数据点分开） 图B、C、D分别给出了一条分隔的直线，那么其中哪一条最好？是不是有寻找最佳拟合直线的感觉？ 支持向量机（SVM）就可以用来寻找此线性可分情形下的最优分类面。（有人说SVM是最好的现成的分类器）,1,什么是支持向量机？ 支持向量机（Support Vector Machine）是一种非常流行的监督学习算法，简称为SVM 。该算法可以针对线性和非线性的数据。它利用一种非线性转换，将原始训练数据映射到高维空间上。在新的高维空间中，它搜索线性最优分类超平面。或者说是搜索一两个不同类型之间分离

2、的决策边界。通过非线性映射将数据映射到一个足够高的维度上，来自两个不同 类的数据总可以被一个超平面所分离。SVM使用支持向量(基本训练元组)和边缘(由支持向量定义)来发现超平面。 右图中，将红蓝两类数据分隔开的直线称为 分隔超平面，在更高维数据集中，将数据分隔开 的对象称为超平面，也就是分类的决策边界。 右图中圆圈标记的数据点，也就是距离分隔超平面 最近的那些点，称为支持向量（support vector）。,2,支持向量机（SVM）,支持向量机理论： SVM是从线性可分情况下的最优分类面发展而来。 最优分类面就是要求不但能将两类正确分开，而且使得分类间隔最大。 SVM考虑寻找一个满足分类要求

3、的超平面，并且使得训练集中的点距离分类面尽可能的远，也就是寻找一个分类面使它两侧的空白区域（margin）最大。 过两类样本中离分类面最近的点且平行于最优分类面的超平面上的训练样本就叫做支持向量（support vector）。 目前，支持向量机已在人脸识别、文字识别、图像处理和时间序列预测等领域获得了比较广泛的应用。,3,两分类问题,线性分割情形,第 1 类,第 2 类,许多决策边界可以分割这些数据点出为两类 我们选取哪一个?,4,坏的决策边界的例子,第 1 类,第 2 类,第 1 类,第 2 类,5,好的决策边界: 间隔最大 Maximum Marginal,决策边界离两类数据应尽可能远

4、最大化间隔 m,第 1 类,第 2 类,m,6,1、数学模型描述：,设 1, , 为数据集, 1,1 为 的类标记，则所求的分类面表达式为： =+= + 要求决策边界正确地分类所有的点，即： 于是得到一个带有约束的优化问题： 优化目标： 约束条件：,7,2、支持向量机求解： 通过引入拉格朗日函数将上述最优化问题转化为其对偶问题，则可以得到,这是一个二次规划 (QP) 问题： 的全局最大值总可以求得 W的计算,8,3、解的性质,许多的 为零 w 只是少数数据的线性组合 具有非零 ai 的 xi 称为支持向量 (SV) 决策边界仅由SV确定 设 tj (j=1, ., s) 为支持向量的指标,于是

5、 为了检测一个新数据 z 计算 如果 WTZ+ b 0, 则 z 属于第一类;否则,属于第二类。,9,a6=1.4,4、几何解释,第1类,第2类,a1=0.8,a2=0,a3=0,a4=0,a5=0,a7=0,a8=0.6,a9=0,a10=0,10,例题：下图给出一个三个数据点的数据集，其中 正例点是 1 = (3,3) , 2 = (4,3) 负例点是 3 = (1,1) ， 试求最大间隔分离超平面。,11,12,线性不可分的情形,两分类问题,13,关键思想: 为了解决非线性分割问题, 将 xi 变换到一个高维空间。 输入空间: xi 所在的空间 特征空间: 变换后 f(xi) 的空间 如

6、何变换 ? 利用一个适当的变换f, 使分类变得容易些。 特征空间中的线性算子等价于输入空间中的非线性算子。,14,左图是一个典型的线性不可分情形， 但是当我们把这两个类似于椭圆形的点映射到一个高维空间后，映射函数为： 用这个函数可以将上图的平面中的点映射到一个三维空间（z1,z2,z3)，并且对映射后的坐标加以旋转之后就可以得到一个线性可分的点集了。,15,在左图中， SVM 是如何对这种数据进行分类的呢？ 通过引入新的变量信息： 2 + 2 = 我们对 x 和 z 构建散点图：,变量 z 恒大于零。 原始图中，红圈数据分布在原点附近 它们的 z 值比较小； 而星星数据则远离原点区域，它们具有

7、较大的 z 值。,16,变换可能出现的问题 难以得到一个好的分类且计算开销大 SVM同时解决这两个问题 最小化 |w|2 能得到好的分类 利用核函数技巧(kernel trick)可以进行有效的计算,f(),特征空间,输入空间,17,什么是核函数？ 核函数定义：核函数是一个对称函数，对所有的x , y X ，满足： 这里f() 是X到內积空间F的映射。,核函数举例 d 阶多项式核： 具有宽度 s的径向基函数核： 相当接近于径向基函数神经网络 具有参数 k and q 的Sigmoid 核,18,核函数技巧(kernel trick) 核函数 K 与映射 f(.) 之间的关系是 作为核函数技巧这

8、是已知的 在应用中, 我们指定K, 从而间接地确定 f() 以代替选取f() 。 直观地, K (x,y) 表示我们对数据 x 和 y 之间相似性的一种描述， 且来自我们的先验知识 。 为了f() 存在， K (x,y) 需要满足 Mercer 条件。,19,变换举例 定义核函数 (,) 如下 考虑下列变换 内积可由 K 计算, 不必通过映射 f()计算,20,非线性SVM算法 将所有的内积改为核函数 训练算法:,线性的,非线性的,21,例题 设有 5个 1 维数据点: 1=1, 2=2, 3=4, 4=5, 5=6, 其中1, 2, 6 为第1类,而4, 5 为第2类 1=1, 2=1, 3

9、=1, 4=1, 5=1。 利用 2 阶多项式核 (,) = (+1)2 取为 100 先求 (=1, , 5) :,22,利用 QP 求解 , 得到 1=0, 2=2.5, 3=0, 4=7.333, 5=4.833 注意到确实满足约束条件 支持向量为 2=2, 4=5, 5=6 描述函数为 确定b 当 x2, x4, x5 位于 上时, (2)=1 , (5)=1 , (6)=1, 由此解得 b=9,23,描述函数的值,1,2,4,5,6,第2类,第1类,第1类,24,支持向量机应用：人脸识别,一个正常人脸，经过预处理之后，得到右图。 对于一幅MM大小的人脸图像, 表示对应于 图的第 i

10、行和第j列的灰度值,这样人脸图像X可以用向量表示为一个矩阵： 对于一个图像集合 1 , 2 ,设向量 (=)为c类(以区别不同的人脸)人脸图像1,2c中的一类,通过变换，将其从原来的m维空间映射到n(nm)维特征空间以达到降低维数的目的，再利用PCA技术得到此空间的特征矩阵。 SVM：首先都是将经过预处理的人脸图像投影到经过变换得到的原有的人脸图像特征子空间中。比如系统中特征子空间维数是64。因此一个人脸图像可用特征空间中的一个64维的向量表示,这样的数据即为人脸特征数据.在训练过程中先对不同人脸的特征数据标为不同的标号，如0、1、2,同一人脸则标以同样的标号。利用支持向量机得到分类函数，从而对人脸特征数据分类 标号，最后测试其属于哪一类（一般选择距离测试分类结果最近的5个作为候选分类）,25,人脸识别系统框架图,26,总结,支持向量机优缺点： 优点：SVM理论避开高维空间的复杂性，直接用內积函数即核函数，来解决决策问题。 同时SVM是基于小样本统计理论的基础上的，符合机器学习的目的 并且比神经网络具有更好的泛化推广能