《支持向量机及其应用》由会员分享，可在线阅读，更多相关《支持向量机及其应用（66页珍藏版）》请在金锄头文库上搜索。
1、Page 1数学与计算机学院 彭宏支持向量机及其应用 Support Vector Machines and its Application智能算法讲座（一） Page 2目录u 线性可分的支持向量（分类）机u 线性支持向量（分类）机u 支持向量（分类）机u 最小二乘支持向量（分类）机u 硬-带支持向量（回归）机u 软-带支持向量（回归）机u -支持向量（回归）机u 最小二乘支持向量（回归）机u 支持向量机应用Page 3SVM的描述u SVM是一种基于统计学习理论的模式识别方 法，它是由Boser,Guyon,Vapnik在COLT-92上 首次提出，从此迅速的发展起来，现在已经 在许多领域
2、（生物信息学，文本，图像处理 ，语言信号处理和手写识别等）都取得了成 功的应用uCOLT(Computational Learning Theory)Page 4SVM的描述u目标：找到一个超平面，使得它能够尽可能多 的将两类数据点正确的分开，同时使分开的两 类数据点距离分类面最远。u解决方法：构造一个在约束条件下的优化问题 ，具体的说是一个约束二次规划问题(constrained quadratic programing),求解该问题，得到分类器 。Page 5模式识别问题的一般描述u 已知：n个观测样本，(x1,y1), (x2,y2) (xn,yn)u 求：最优函数y= f(x,w)u
3、满足条件：期望风险最小u 损失函数Page 6SVM的描述u 期望风险R(w)要依赖联合概率F(x,y)的信息 ，实际问题中无法计算。u 一般用经验风险Remp(w)代替期望风险R(w)Page 7一般模式识别方法的问题u 经验风险最小不等于期望风险最小，不能保证 分类器的推广能力.u 经验风险只有在样本数无穷大趋近于期望风险 ，需要非常多的样本才能保证分类器的性能。u 需要找到经验风险最小和推广能力最大的平衡 点。Page 8一、线性可分的支持向量(分类)机首先考虑线性可分情况。设有如下两类样本的训练集：线性可分情况意味着存在超平面使训练点中的正类和 负类样本分别位于该超平面的两侧。如果能确
4、定这样的参数对（w,b） 的话,就可以构造决策函数来进行 识别新样本。Page 9线性可分的支持向量(分类)机问题是：这样的参数对（w,b）有许多。解决的方法是采用最大间隔原则。最大间隔原则：选择使得训练集D对于线性函数 (wx)+b的几何间隔取最大值的参数对(w,b)，并 由此构造决策函数。在规范化下，超平面的几何间隔为 于是，找最大几何间隔的超平面 表述成如下的最优化问题：(1)Page 10线性可分的支持向量(分类)机为求解问题(1),使用Lagrange乘子法将其转化为对偶问题。 于是引入Lagrange函数：其中， 称为Lagrange乘子。首先求Lagrange函数关于w,b的极小
5、值。由极值条件有：得到：(2)(3)(4)Page 11线性可分的支持向量(分类)机将(3)式代入Lagrange函数，并利用(4)式，则原始的优化问题 转化为如下的对偶问题(使用极小形式)：这是一个凸二 次规划问题 有唯一的最优 解(5)求解问题(5)，得。则参数对(w,b)可由下式计算：Page 12线性可分的支持向量(分类)机支持向量：称训练集D中的样本xi为支持向量，如果它对应的i*0。根据原始最优化问题的KKT条件，有于是，支持向量正好在间隔边界上。于是，得到如下的决策函数：Page 13目录u 线性可分的支持向量（分类）机u 线性支持向量（分类）机u 支持向量（分类）机u 最小二乘
6、支持向量（分类）机u 硬-带支持向量（回归）机u 软-带支持向量（回归）机u -支持向量（回归）机u 最小二乘支持向量（回归）机u 支持向量机应用Page 14二、线性支持向量(分类)机现在考虑线性不可分情况。对于训练集D，不存在这样 的超平面，使训练集关于该超平面的几何间隔取正值。 如果要用超平面来划分的话，必然有错分的点。但我们任希望使用超平面进行分划，这时应“软化” 对间隔的要求，即容许不满足约束条件的样本点存在。为此，引入松弛变量 并“软化”约束条件：iPage 15线性支持向量(分类)机为了避免i取太大的值，需要在目标函数中对它们进行 惩罚。于是原始优化问题变为：其中C0称为惩罚因子
7、。(6)Page 16线性支持向量(分类)机类似前面，通过引入如下的Lagrange函数：得到如下的对偶问题：(7)Page 17线性支持向量(分类)机求解对偶问题(7),可得如下决策函数：支持向量有下列性质： (1)界内支持向量一定位于间隔边界上的正确划分区； (2)支持向量不会出现在间隔以外的正确划分区； (3)非支持向量一定位于带间隔的正确划分区。Page 18目录u 线性可分的支持向量（分类）机u 线性支持向量（分类）机u 支持向量（分类）机u 最小二乘支持向量（分类）机u 硬-带支持向量（回归）机u 软-带支持向量（回归）机u -支持向量（回归）机u 最小二乘支持向量（回归）机u 支
8、持向量机应用Page 19三、支持向量(分类)机对于一般的非线性可分情况。对于训练集D，无法寻找 到来如前的超平面来划分。Page 20支持向量(分类)机下面通过核技术来处理。引入一个非线性映射把输入空间 映射到一个(高维的)Hilbert空间H,使数据在H中是线性可分 或线性不可分：输入空间XiHilbert空间H线性 可分线性 不可分Page 21在核映射下，D对应于Hilbert空间H的训练集为：支持向量(分类)机于是在Hilbert空间H中寻找使几何间隔最大的超平 面，其原始优化问题为：(8)Page 22问题(8)对应的对偶问题为：支持向量(分类)机(9)求解对偶问题(9),可得如下
9、决策函数：Page 23b*问的计算如下：支持向量(分类)机选取的一个正分量00或j* 0来计算b:Page 40硬-带支持向量（回归）机支持向量：称训练集D中的样本xi为支持向量，如果它对应的i*0或i0 。把w的式子代入函数： 于是，得到如下的回归函数：y=(w.x)+b+y=(w.x)+b-y=(w.x)+bPage 41目录u 线性可分的支持向量（分类）机u 线性支持向量（分类）机u 支持向量（分类）机u 最小二乘支持向量（分类）机u 硬-带支持向量（回归）机u 软-带支持向量（回归）机u -支持向量（回归）机u 最小二乘支持向量（回归）机u 支持向量机应用Page 42软-带支持向量
10、（回归）机考虑软-带支持向量线性回归情况。设有如下两类样本的训练集 ：同样希望使用一个线性函数来回归样本点，且这种情况下，除了 大量样本点在-带内，还有少量的样本落在-带外。这时需要对 落在-带外的样本进行惩罚。于是原始优化问题为：y=(w.x)+b+y=(w.x)+b-y=(w.x)+bPage 43软-带支持向量（回归）机为求解上述原始优化问题,使用Lagrange乘子法将其转化为对 偶问题。于是引入Lagrange函数：其中， 称为Lagrange乘子。 首先求Lagrange函数关于w,b,(*)的极小值。由极值条件有：Page 44软-带支持向量（回归）机将上式代入Lagrange函
11、数，则原始的优化问题转化为如下的 对偶问题(使用极小形式)：求解上述对偶问题，得(*)。则参数对(w,b)可由下式计算：b的计算（略）。Page 45软-带支持向量（回归）机支持向量：称训练集D中的样本xi为支持向量，如果它对应的i*0或i0 。把w的式子代入函数： 于是，得到如下的回归函数：y=(w.x)+b+y=(w.x)+b-y=(w.x)+bPage 46目录u 线性可分的支持向量（分类）机u 线性支持向量（分类）机u 支持向量（分类）机u 最小二乘支持向量（分类）机u 硬-带支持向量（回归）机u 软-带支持向量（回归）机u -支持向量（回归）机u 最小二乘支持向量（回归）机u 支持向
12、量机应用Page 47-支持向量（回归）机下面通过核技术来处理。引入一个非线性映射把输入空间 映射到一个(高维的)Hilbert空间H,使在H中进行线性回归（ 硬-带或软-带）：输入空间XHilbert空间H硬-带 线性回归软-带 线性回归Page 48在核映射下，D对应于Hilbert空间H的训练集为：-支持向量（回归）机于是在Hilbert空间H中进行线性回归，其原始优化 问题为：Page 49上述问题的对偶问题为：-支持向量（回归）机求解对偶问题,可得如下回归函数：Page 50目录u 线性可分的支持向量（分类）机u 线性支持向量（分类）机u 支持向量（分类）机u 最小二乘支持向量（分类
13、）机u 硬-带支持向量（回归）机u 软-带支持向量（回归）机u -支持向量（回归）机u 最小二乘支持向量（回归）机u 支持向量机应用Page 51四、最小二乘支持向量(回归)机假定xXRd表示一个实值随机输入向量，yYR表示一个实 值随机输出变量。记RN表示一高维的特征空间，为一非线性 映射: X，它映射随机输入向量到高维特征空间。支持向量方法的思想是在该高维特征空间中考虑如下线性 函数集： 我们考虑在函数表示式中含噪声情形。给定一个由未知分 布FXY产生的、独立同分布（i.i.d.）的训练集： 这里ekR假定为独立同分布的随机误差，且E ek | X=xk = 0， Var ek = 2 ；
14、m(x)F为一个未知的实值光滑函数，且E yk | x=xk = f(xk)。 Page 52最小二乘支持向量(回归)机函数估计的目的是在约束|w|a, aR下通过最小化如下经验 风险来寻找w和b: 最小二乘支持向量回归机（LS-SVR）定义了与标准支持向 量机不同的代价函数，选用损失函数为误差ek的二次项，并将其 不等式约束改为等式约束，因此寻找w和b的优化问题可以转化 为如下具有岭回归形式的优化问题： 且带有如下等式约束条件： 其中 Page 53最小二乘支持向量(回归)机为了在对偶空间中求解上述优化问题，定义如下的Lagrange 泛函： 其中kR为乘子（叫做支持向量）。其优化条件由下式
15、给出： Page 54最小二乘支持向量(回归)机上式能被直接表示为求解如下如下线性方程组： 其中y=(y1,yn)T, (x)=( (x1), (xn)T, 1n=(1,.,1)T, e=(e1,en)T, =(1, n)T。在上式中消去w和e后，得到如下 线性方程组： 其中kl=(xk)T(xl), k,l=1,.,n。 Page 55最小二乘支持向量(回归)机根据Mercer定理，函数估计的最小二乘支持向量回归模型为： 其中与b通过求解上述方程组得到。 Page 56目录u 线性可分的支持向量（分类）机u 线性支持向量（分类）机u 支持向量（分类）机u 最小二乘支持向量（分类）机u 硬-带
16、支持向量（回归）机u 软-带支持向量（回归）机u -支持向量（回归）机u 最小二乘支持向量（回归）机u 支持向量机应用Page 57九、支持向量机应用1、手写体数字识别。SVM的第一个应用是手写字符识别问题。Vapnik、Burges、Cortes、Scholkopf等研究了该问 题。使用最大间隔和软间隔SVM。使用高斯核和多项式 核。在两个数据集USPS(美国邮政服务局)和NIST(国家标 准技术局)。其中USPS数据集包括7291个训练样本， 2007个测试样本，用256维的向量(1616矩阵)表示， 每个点的灰度值0255。NIST数据集包括60000个训练样本，10000个测试样本 ，图像为2020矩阵表示。结果表明SVM具有一定的优势。P
