支持向量机及其应用.ppt

《支持向量机及其应用.ppt》由会员分享，可在线阅读，更多相关《支持向量机及其应用.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Page 1数学与计算机学院数学与计算机学院数学与计算机学院数学与计算机学院 彭宏彭宏彭宏彭宏支持向量机及其应用支持向量机及其应用支持向量机及其应用支持向量机及其应用Support Vector Machines and its ApplicationSupport Vector Machines and its Application智能算法讲座（一）智能算法讲座（一）智能算法讲座（一）智能算法讲座（一）Page 2Page 3目录目录u 线性可分的支持向量（分类）机线性可分的支持向量（分类）机u 线性支持向量（分类）机线性支持向量（分类）机u 支持向量（分类）机支持向量（分类）机u 最小二

2、乘支持向量（分类）机最小二乘支持向量（分类）机u 硬硬-带带支持向量（回归）机支持向量（回归）机u 软软-带带支持向量（回归）机支持向量（回归）机u -支持向量（回归）机支持向量（回归）机u 最小二乘支持向量（回归）机最小二乘支持向量（回归）机u 支持向量机应用支持向量机应用Page 4SVM的描述的描述u SVM是一种基于统计学习理论的模式识别方是一种基于统计学习理论的模式识别方法，它是由法，它是由Boser,Guyon,Vapnik在在COLT-92上上首次提出，从此迅速的发展起来，现在已经首次提出，从此迅速的发展起来，现在已经在许多领域（生物信息学，文本，图像处理，在许多领域（生物信息学

3、，文本，图像处理，语言信号处理和手写识别等）都取得了成功语言信号处理和手写识别等）都取得了成功的应用的应用uCOLT(Computational Learning Theory)Page 5SVM的描述的描述u目标：目标：找到一个超平面，使得它能够尽可能多找到一个超平面，使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。类数据点距离分类面最远。u解决方法：解决方法：构造一个在约束条件下的优化问题，构造一个在约束条件下的优化问题，具体的说是一个约束二次规划问题具体的说是一个约束二次规划问题(constrained quadr

4、atic programing),求解该问题，得到分类器。求解该问题，得到分类器。Page 6模式识别问题的一般描述模式识别问题的一般描述u 已知：已知：n个观测样本，个观测样本，(x1,y1),(x2,y2)(xn,yn)u 求：最优函数求：最优函数y=f(x,w)u 满足条件：期望风险最小满足条件：期望风险最小u 损失函数损失函数Page 7SVM的描述的描述u 期望风险期望风险R(w)要依赖联合概率要依赖联合概率F(x,y)的信息，的信息，实际问题中无法计算。实际问题中无法计算。u 一般用经验风险一般用经验风险Remp(w)代替期望风险代替期望风险R(w)Page 8一般模式识别方法的问

5、题一般模式识别方法的问题u 经验风险最小不等于期望风险最小，不能保证经验风险最小不等于期望风险最小，不能保证分类器的推广能力分类器的推广能力.u 经验风险只有在样本数无穷大趋近于期望风险，经验风险只有在样本数无穷大趋近于期望风险，需要非常多的样本才能保证分类器的性能。需要非常多的样本才能保证分类器的性能。u 需要找到经验风险最小和推广能力最大的平衡需要找到经验风险最小和推广能力最大的平衡点。点。Page 9一、线性可分的支持向量(分类)机首先考虑线性可分情况。设有如下两类样本的训练集：首先考虑线性可分情况。设有如下两类样本的训练集：线性可分情况意味着存在线性可分情况意味着存在超平面超平面使训练

6、点中的正类和使训练点中的正类和负类样本分别位于该超平面的两侧。负类样本分别位于该超平面的两侧。如果能确定这样的参数对（如果能确定这样的参数对（w,bw,b）的话的话,就可以构造就可以构造决策函数决策函数来进行来进行识别新样本。识别新样本。Page 10线性可分的支持向量(分类)机问题是问题是：这样的参数对（：这样的参数对（w,bw,b）有许多。）有许多。解决的方法是采用最大间隔原则。解决的方法是采用最大间隔原则。最大间隔原则最大间隔原则：选择使得训练集：选择使得训练集D D对于线性函数对于线性函数(wx)+b的几何间隔取最大值的参数对的几何间隔取最大值的参数对(w,b)(w,b)，并，并由此构

7、造决策函数。由此构造决策函数。在规范化下，超平面的几何间隔为在规范化下，超平面的几何间隔为于是，找最大于是，找最大几何间隔的超平面几何间隔的超平面表述成如下的最优化问题：表述成如下的最优化问题：(1)(1)Page 11线性可分的支持向量(分类)机 为求解问题为求解问题(1),(1),使用使用Lagrange乘子法乘子法将其转化为对偶问题。将其转化为对偶问题。于是引入于是引入Lagrange函数函数：其中，其中，称为称为Lagrange乘子。乘子。首先求首先求Lagrange函数关于函数关于w,bw,b的极小值。由的极小值。由极值条件有：极值条件有：得到：得到：(2)(2)(3)(3)(4)(

8、4)Page 12线性可分的支持向量(分类)机将将(3)(3)式代入式代入Lagrange函数，并利用函数，并利用(4)(4)式，则原始的优化问题式，则原始的优化问题转化为如下的转化为如下的对偶问题对偶问题(使用极小形式使用极小形式)：这是一个凸二这是一个凸二次规划问题次规划问题有唯一的最优有唯一的最优解解(5)(5)求解问题求解问题(5)(5)，得，得。则参数对。则参数对(w,b)(w,b)可由下式计算：可由下式计算：Page 13线性可分的支持向量(分类)机支持向量：支持向量：称训练集称训练集D中的样本中的样本xi为支持向量，如为支持向量，如 果它对应的果它对应的i*0。根据原始最优化问题

9、的根据原始最优化问题的KKTKKT条件，有条件，有于是，支持向量正好在间隔边界上于是，支持向量正好在间隔边界上。于是，得到如下的决策函数：于是，得到如下的决策函数：Page 14目录目录u 线性可分的支持向量（分类）机线性可分的支持向量（分类）机u 线性支持向量（分类）机线性支持向量（分类）机u 支持向量（分类）机支持向量（分类）机u 最小二乘支持向量（分类）机最小二乘支持向量（分类）机u 硬硬-带带支持向量（回归）机支持向量（回归）机u 软软-带带支持向量（回归）机支持向量（回归）机u -支持向量（回归）机支持向量（回归）机u 最小二乘支持向量（回归）机最小二乘支持向量（回归）机u 支持向量

10、机应用支持向量机应用Page 15二、线性支持向量(分类)机现在考虑现在考虑线性不可分情况线性不可分情况。对于训练集。对于训练集D D，不存在这样的，不存在这样的超平面，使训练集关于该超平面的几何间隔取正值。如超平面，使训练集关于该超平面的几何间隔取正值。如果要用超平面来划分的话，必然有错分的点。果要用超平面来划分的话，必然有错分的点。但我们任希望使用超平面进行分划，这时应但我们任希望使用超平面进行分划，这时应“软化软化”对间隔的要求，即容许不满足约束条件的样本点存在。对间隔的要求，即容许不满足约束条件的样本点存在。为此，引入松弛变量为此，引入松弛变量并并“软化软化”约束条件：约束条件：iPa

11、ge 16线性支持向量(分类)机为了避免为了避免 i i取太大的值，需要在目标函数中对它们进行取太大的值，需要在目标函数中对它们进行惩罚。于是惩罚。于是原始优化问题原始优化问题变为：变为：其中其中C0C0称为称为惩罚因子。惩罚因子。(6)(6)Page 17线性支持向量(分类)机类似前面，通过引入如下的类似前面，通过引入如下的Lagrange函数：函数：得到如下的对偶问题：得到如下的对偶问题：(7)(7)Page 18线性支持向量(分类)机求解对偶问题求解对偶问题(7),(7),可得如下决策函数：可得如下决策函数：支持向量有下列性质：支持向量有下列性质：(1)(1)界内支持向量一定位于间隔边界

12、上界内支持向量一定位于间隔边界上 的正确划分区；的正确划分区；(2)(2)支持向量不会出现在间隔以外的支持向量不会出现在间隔以外的 正确划分区；正确划分区；(3)(3)非支持向量一定位于带间隔的正确划分区。非支持向量一定位于带间隔的正确划分区。Page 19目录目录u 线性可分的支持向量（分类）机线性可分的支持向量（分类）机u 线性支持向量（分类）机线性支持向量（分类）机u 支持向量（分类）机支持向量（分类）机u 最小二乘支持向量（分类）机最小二乘支持向量（分类）机u 硬硬-带带支持向量（回归）机支持向量（回归）机u 软软-带带支持向量（回归）机支持向量（回归）机u -支持向量（回归）机支持向

13、量（回归）机u 最小二乘支持向量（回归）机最小二乘支持向量（回归）机u 支持向量机应用支持向量机应用Page 20三、支持向量(分类)机对于一般的对于一般的非线性可分情况非线性可分情况。对于训练集。对于训练集D D，无法寻找到，无法寻找到来如前的超平面来划分。来如前的超平面来划分。Page 21支持向量(分类)机下面通过下面通过核技术核技术来处理。引入一个来处理。引入一个非线性映射非线性映射 把把输入空间输入空间映射到一个映射到一个(高维的高维的)Hilbert空间空间H,使数据在使数据在H中是线性可分中是线性可分或线性不可分：或线性不可分：输入空间输入空间Xi Hilbert空间空间H线性线

14、性可分可分线性线性不可分不可分Page 22在核映射下，在核映射下，D D对应于对应于Hilbert空间空间H的训练集为：的训练集为：支持向量(分类)机于是在于是在Hilbert空间空间H中寻找使几何间隔最大的超平中寻找使几何间隔最大的超平面，其原始优化问题面，其原始优化问题为：为：(8)(8)Page 23问题问题(8)(8)对应的对偶问题为对应的对偶问题为：支持向量(分类)机(9)(9)求解对偶问题求解对偶问题(9),(9),可得如下决策函数：可得如下决策函数：Page 24b*问的计算如下问的计算如下：支持向量(分类)机选取选取的一个正分量的一个正分量0j*0或或j*0来计算来计算b:P

15、age 41硬硬-带带支持向量（回归）机支持向量（回归）机支持向量：支持向量：称训练集称训练集D中的样本中的样本xi为支持向量，为支持向量，如果它对应的如果它对应的i*0或i0。把把w的式子代入函数：的式子代入函数：于是，得到如下的回归函数：于是，得到如下的回归函数：y=(w.x)+b+y=(w.x)+b-y=(w.x)+bPage 42目录目录u 线性可分的支持向量（分类）机线性可分的支持向量（分类）机u 线性支持向量（分类）机线性支持向量（分类）机u 支持向量（分类）机支持向量（分类）机u 最小二乘支持向量（分类）机最小二乘支持向量（分类）机u 硬硬-带带支持向量（回归）机支持向量（回归）

16、机u 软软-带带支持向量（回归）机支持向量（回归）机u -支持向量（回归）机支持向量（回归）机u 最小二乘支持向量（回归）机最小二乘支持向量（回归）机u 支持向量机应用支持向量机应用Page 43软软-带带支持向量（回归）机支持向量（回归）机考虑软考虑软-带支持向量带支持向量线性线性回归回归情况。设有如下两类样本的训练集：情况。设有如下两类样本的训练集：同样希望使用一个线性函数来同样希望使用一个线性函数来回归回归样本点，且这种情况下，除了样本点，且这种情况下，除了大量样本点在大量样本点在-带内，还有少量的样本带内，还有少量的样本落在落在-带外。这时需要对带外。这时需要对落在落在-带外的样本进行

17、惩罚。于是带外的样本进行惩罚。于是原始优化问题原始优化问题为：为：y=(w.x)+b+y=(w.x)+b-y=(w.x)+bPage 44软软-带带支持向量（回归）机支持向量（回归）机 为求解上述原始优化问题为求解上述原始优化问题,使用使用Lagrange乘子法乘子法将其转化为对将其转化为对偶问题。于是引入偶问题。于是引入Lagrange函数函数：其中，其中，称为称为Lagrange乘子。乘子。首先求首先求Lagrange函数关于函数关于w,b,w,b,(*)(*)的极小值。由的极小值。由极值条件有：极值条件有：Page 45软软-带带支持向量（回归）机支持向量（回归）机将上式代入将上式代入L

18、agrange函数，则原始的优化问题转化为如下的函数，则原始的优化问题转化为如下的对偶问题对偶问题(使用极小形式使用极小形式)：求解上述对偶问题，得求解上述对偶问题，得(*)(*)。则参数对。则参数对(w,b)(w,b)可由下式计算：可由下式计算：b的计算（略）。的计算（略）。Page 46软软-带带支持向量（回归）机支持向量（回归）机支持向量：支持向量：称训练集称训练集D中的样本中的样本xi为支持向量，为支持向量，如果它对应的如果它对应的i*0或i0。把把w的式子代入函数：的式子代入函数：于是，得到如下的回归函数：于是，得到如下的回归函数：y=(w.x)+b+y=(w.x)+b-y=(w.x

19、)+bPage 47目录目录u 线性可分的支持向量（分类）机线性可分的支持向量（分类）机u 线性支持向量（分类）机线性支持向量（分类）机u 支持向量（分类）机支持向量（分类）机u 最小二乘支持向量（分类）机最小二乘支持向量（分类）机u 硬硬-带带支持向量（回归）机支持向量（回归）机u 软软-带带支持向量（回归）机支持向量（回归）机u -支持向量（回归）机支持向量（回归）机u 最小二乘支持向量（回归）机最小二乘支持向量（回归）机u 支持向量机应用支持向量机应用Page 48-支持向量（回归）机支持向量（回归）机下面通过下面通过核技术核技术来处理。引入一个来处理。引入一个非线性映射非线性映射 把把

20、输入空间输入空间映射到一个映射到一个(高维的高维的)Hilbert空间空间H,使在使在H中进行线性回归中进行线性回归（硬（硬-带或软带或软-带）：带）：输入空间输入空间X Hilbert空间空间H硬硬-带带线性回归线性回归软软-带带线性回归线性回归Page 49在核映射下，在核映射下，D D对应于对应于Hilbert空间空间H的训练集为：的训练集为：-支持向量（回归）机支持向量（回归）机于是在于是在Hilbert空间空间H中进行线性回归，其原始优化中进行线性回归，其原始优化问题问题为：为：Page 50上述问题的对偶问题为上述问题的对偶问题为：-支持向量（回归）机支持向量（回归）机求解对偶问题

21、求解对偶问题,可得如下回归函数：可得如下回归函数：Page 51目录目录u 线性可分的支持向量（分类）机线性可分的支持向量（分类）机u 线性支持向量（分类）机线性支持向量（分类）机u 支持向量（分类）机支持向量（分类）机u 最小二乘支持向量（分类）机最小二乘支持向量（分类）机u 硬硬-带带支持向量（回归）机支持向量（回归）机u 软软-带带支持向量（回归）机支持向量（回归）机u -支持向量（回归）机支持向量（回归）机u 最小二乘支持向量（回归）机最小二乘支持向量（回归）机u 支持向量机应用支持向量机应用Page 52四、最小二乘支持向量(回归)机 假定假定xXRd表示一个实值随机输入向量，表示一

22、个实值随机输入向量，yYR表示一表示一个实值随机输出变量。记个实值随机输出变量。记RN表示一高维的特征空间，表示一高维的特征空间，为一非为一非线性映射线性映射:X，它映射随机输入向量到高维特征空间，它映射随机输入向量到高维特征空间。支持向量方法的思想是在该高维特征空间支持向量方法的思想是在该高维特征空间中考虑如下线性中考虑如下线性函数集：函数集：我们考虑在函数表示式中含噪声情形。给定一个由未知分我们考虑在函数表示式中含噪声情形。给定一个由未知分布布FXY产生的、独立同分布（产生的、独立同分布（i.i.d.）的训练集：）的训练集：这里这里ekR假定为独立同分布的随机误差，且假定为独立同分布的随机

23、误差，且E ek|X=xk =0，Var ek =2 ；m(x)F为一个未知的实值光滑函数，且为一个未知的实值光滑函数，且E yk|x=xk =f(xk)。Page 53最小二乘支持向量(回归)机 函数估计的目的是在约束函数估计的目的是在约束|w|a,aR下通过最小化如下经验下通过最小化如下经验风险来寻找风险来寻找w和和b:最小二乘支持向量回归机最小二乘支持向量回归机（LS-SVR）定义了与标准支持向定义了与标准支持向量机不同的代价函数，选用损失函数为误差量机不同的代价函数，选用损失函数为误差ek的二次项，并将其的二次项，并将其不等式约束改为等式约束，因此寻找不等式约束改为等式约束，因此寻找w

24、和和b的优化问题可以转化的优化问题可以转化为如下具有为如下具有岭回归岭回归形式的优化问题：形式的优化问题：且带有如下等式约束条件：且带有如下等式约束条件：其中其中 Page 54最小二乘支持向量(回归)机 为了在对偶空间中求解上述优化问题，定义如下的为了在对偶空间中求解上述优化问题，定义如下的Lagrange泛函：泛函：其中其中kR为乘子（叫做支持向量）。为乘子（叫做支持向量）。其优化条件由下式给出：其优化条件由下式给出：Page 55最小二乘支持向量(回归)机上式能被直接表示为求解如下如下线性方程组：上式能被直接表示为求解如下如下线性方程组：其中其中y=(y1,yn)T,(x)=(x1),(

25、xn)T,1n=(1,.,1)T,e=(e1,en)T,=(1,n)T。在上式中消去。在上式中消去w和和e后，得到如下后，得到如下线性方程组：线性方程组：其中其中kl=(xk)T(xl),k,l=1,.,n。Page 56最小二乘支持向量(回归)机根据根据Mercer定理，函数估计的最小二乘支持向量回归模型为：定理，函数估计的最小二乘支持向量回归模型为：其中其中与与b通过求解上述方程组通过求解上述方程组得到。得到。Page 57目录目录u 线性可分的支持向量（分类）机线性可分的支持向量（分类）机u 线性支持向量（分类）机线性支持向量（分类）机u 支持向量（分类）机支持向量（分类）机u 最小二乘

26、支持向量（分类）机最小二乘支持向量（分类）机u 硬硬-带带支持向量（回归）机支持向量（回归）机u 软软-带带支持向量（回归）机支持向量（回归）机u -支持向量（回归）机支持向量（回归）机u 最小二乘支持向量（回归）机最小二乘支持向量（回归）机u 支持向量机应用支持向量机应用Page 58九、支持向量机应用1 1、手写体数字识别、手写体数字识别。SVMSVM的第一个应用是手写字符识别问题。的第一个应用是手写字符识别问题。VapnikVapnik、BurgesBurges、CortesCortes、ScholkopfScholkopf等研究了该问等研究了该问题。使用题。使用最大间隔最大间隔和和软间

27、隔软间隔SVMSVM。使用。使用高斯核高斯核和和多项式核多项式核。在两个数据集在两个数据集USPSUSPS(美国邮政服务局美国邮政服务局)和和NISTNIST(国家标国家标准技术局准技术局)。其中。其中USPSUSPS数据集包括数据集包括72917291个训练样本，个训练样本，20072007个测试样本，用个测试样本，用256256维的向量维的向量(1616(1616矩阵矩阵)表示，每表示，每个点的灰度值个点的灰度值0 0255255。NISTNIST数据集包括数据集包括6000060000个训练样本，个训练样本，1000010000个测试样本，个测试样本，图像为图像为20202020矩阵表示

28、。矩阵表示。结果表明结果表明SVMSVM具有一定的优势。具有一定的优势。Page 59九、支持向量机应用2 2、文本分类、文本分类。根据文本的内容自动地把它归类。比如邮件过滤、网根据文本的内容自动地把它归类。比如邮件过滤、网页搜索、页搜索、WebWeb挖掘、信息检索等。挖掘、信息检索等。JoachimsJoachims，DumaisDumais等人进行等人进行SVMSVM对文本分类的研究工对文本分类的研究工作。作。使用的数据集为路透社使用的数据集为路透社(Reuters)(Reuters)第第2157821578号新闻数据号新闻数据库。该数据库共有库。该数据库共有1290212902个文本，包

29、括个文本，包括96039603个训练的文本个训练的文本和和32993299个测试样本。每个文本大约包含个测试样本。每个文本大约包含200200个单词，分属个单词，分属于于118118类，如金融、运输等。类，如金融、运输等。主要使用线性核。主要使用线性核。结果表明结果表明SVMSVM比其他的分类算法（如决策树、比其他的分类算法（如决策树、K-K-近邻算近邻算法等）具有良好的性能。法等）具有良好的性能。Page 60九、支持向量机应用3 3、图像识别、图像识别。(1)(1)视位无关的分类视位无关的分类 PontilPontil、VerriVerri研究了使用研究了使用SVMSVM于与视位无关的目标

30、于与视位无关的目标识别。识别。Page 61九、支持向量机应用(2)(2)基于颜色的分类基于颜色的分类 Oliver ChapelleOliver Chapelle及其合作者研究了仅使用颜色与光及其合作者研究了仅使用颜色与光照信息下的照信息下的SVMSVM目标识别。目标识别。Page 62九、支持向量机应用(3)(3)可视场景中的目标检测可视场景中的目标检测 人脸检测人脸检测：给定任意图像作为输入，检测其中是否有人：给定任意图像作为输入，检测其中是否有人脸存在，以及人脸的位置。脸存在，以及人脸的位置。OsunaOsuna等人开发的系统，尽可能扫描像人脸的模式，然等人开发的系统，尽可能扫描像人脸

31、的模式，然后利用后利用SVMSVM作为分类器，检查一幅给定的图像是否有人脸。作为分类器，检查一幅给定的图像是否有人脸。数据库中包含脸与非脸的模式，图像用数据库中包含脸与非脸的模式，图像用191919=36119=361个像个像素的向量表示，训练一个软间隔分类器，使用二阶多项素的向量表示，训练一个软间隔分类器，使用二阶多项式核。式核。汽车行进的可视场景中的行人检测汽车行进的可视场景中的行人检测：等人多项式核的等人多项式核的SVMSVM作为分类器，在之前端使用小波作作为分类器，在之前端使用小波作为特征提取的方法。为特征提取的方法。Page 63九、支持向量机应用4 4、语音信号处理、语音信号处理。

32、(1)(1)说话人识别说话人识别 (2)(2)语音情感识别语音情感识别(3)(3)Page 64九、支持向量机应用5 5、信息安全领域、信息安全领域。(1)(1)入侵检测入侵检测 (2)(2)病毒检测病毒检测(3)(3)数字水印技术数字水印技术(4)(4)Page 65九、支持向量机应用6 6、时间序列、时间序列。(1)(1)经济预警经济预警 (2)(2)股市预测股市预测(3)(3)财务预测财务预测(4)(4)电力负荷预测电力负荷预测(5)(5)交通流量预测交通流量预测(6)(6)Page 66九、支持向量机应用7 7、核方法、核方法。在在SVMSVM中的核技巧得到进一步的扩展。中的核技巧得到

33、进一步的扩展。(1)(1)支持向量机（分类机、回归机）支持向量机（分类机、回归机）(2)(2)核聚类核聚类(3)(3)核主成分分析核主成分分析(核核PCA)PCA)(4)(4)Page 67支持向量机的一些资源支持向量机的一些资源SVM MATLAB TOOLBOX from Graz SVM&KM matlaSVM MATLAB TOOLBOX from Graz SVM&KM matlab toolbox,from Insa de Rouen GPDT parallel software for SVMs from University of Ferrara and University

34、of Modena,Italy Gist:software for support vector machine classification and for kernel principal components analysis.Matlab Interface:a MATLAB interface to SVMlight written by Anton Schwaighofer(for SVMlight V4.00)jSVM:a JAVA interface to SVMlight written by Heloise Hwawen Hse(for SVMlight V2.01)A special version of SVMlight is integrated into the virtual file system libferris by Ben Martin Java Implementation of LIBSVM MATLAB Support Vector Machine Toolbox by Gavin Cawley Matlab implementation by Steve Gunn,MATLAB SVM toolbox 完完