支持向量机与其应用

目录线性可分的支持向量（分类）机线性支持向量（分类）机支持向量（分类）机最小二乘支持向量（分类）机硬-带支持向量（回归）机软-带支持向量（回归）机

-支持向量（回归）机最小二乘支持向量（回归）机支持向量机应用第一页，共65页。SVM的描述SVM是一种基于统计学习理论的模式识别方法，它是由Boser,Guyon,Vapnik在COLT-92上首次提出，从此迅速的发展起来，现在已经在许多领域（生物信息学，文本，图像处理，语言信号处理和手写识别等）都取得了成功的应用

COLT(ComputationalLearningTheory)第二页，共65页。SVM的描述目标：找到一个超平面，使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。解决方法：构造一个在约束条件下的优化问题，具体的说是一个约束二次规划问题(constrainedquadraticprograming),求解该问题，得到分类器。第三页，共65页。模式识别问题的一般描述

已知：n个观测样本，(x1,y1),(x2,y2)……(xn,yn)求：最优函数y’=f(x,w)满足条件：期望风险最小损失函数第四页，共65页。SVM的描述期望风险R(w)要依赖联合概率F(x,y)的信息，实际问题中无法计算。一般用经验风险Remp(w)代替期望风险R(w)第五页，共65页。一般模式识别方法的问题经验风险最小不等于期望风险最小，不能保证分类器的推广能力.经验风险只有在样本数无穷大趋近于期望风险，需要非常多的样本才能保证分类器的性能。需要找到经验风险最小和推广能力最大的平衡点。第六页，共65页。一、线性可分的支持向量(分类)机首先考虑线性可分情况。设有如下两类样本的训练集：线性可分情况意味着存在超平面使训练点中的正类和负类样本分别位于该超平面的两侧。如果能确定这样的参数对（w,b）的话,就可以构造决策函数来进行识别新样本。第七页，共65页。线性可分的支持向量(分类)机问题是：这样的参数对（w,b）有许多。解决的方法是采用最大间隔原则。最大间隔原则：选择使得训练集D对于线性函数(w·x)+b的几何间隔取最大值的参数对(w,b)，并由此构造决策函数。在规范化下，超平面的几何间隔为于是，找最大几何间隔的超平面表述成如下的最优化问题：(1)第八页，共65页。线性可分的支持向量(分类)机为求解问题(1),使用Lagrange乘子法将其转化为对偶问题。于是引入Lagrange函数：其中，称为Lagrange乘子。首先求Lagrange函数关于w,b的极小值。由极值条件有：得到：(2)(3)(4)第九页，共65页。线性可分的支持向量(分类)机将(3)式代入Lagrange函数，并利用(4)式，则原始的优化问题转化为如下的对偶问题(使用极小形式)：这是一个凸二次规划问题有唯一的最优解(5)求解问题(5)，得。则参数对(w,b)可由下式计算：第十页，共65页。线性可分的支持向量(分类)机支持向量：称训练集D中的样本xi为支持向量，如果它对应的i*>0。根据原始最优化问题的KKT条件，有于是，支持向量正好在间隔边界上。于是，得到如下的决策函数：第十一页，共65页。目录线性可分的支持向量（分类）机线性支持向量（分类）机支持向量（分类）机最小二乘支持向量（分类）机硬-带支持向量（回归）机软-带支持向量（回归）机

-支持向量（回归）机最小二乘支持向量（回归）机支持向量机应用第十二页，共65页。二、线性支持向量(分类)机现在考虑线性不可分情况。对于训练集D，不存在这样的超平面，使训练集关于该超平面的几何间隔取正值。如果要用超平面来划分的话，必然有错分的点。但我们任希望使用超平面进行分划，这时应“软化”对间隔的要求，即容许不满足约束条件的样本点存在。为此，引入松弛变量并“软化”约束条件：i第十三页，共65页。线性支持向量(分类)机为了避免i取太大的值，需要在目标函数中对它们进行惩罚。于是原始优化问题变为：其中C>0称为惩罚因子。(6)第十四页，共65页。线性支持向量(分类)机类似前面，通过引入如下的Lagrange函数：得到如下的对偶问题：(7)第十五页，共65页。线性支持向量(分类)机求解对偶问题(7),可得如下决策函数：支持向量有下列性质：(1)界内支持向量一定位于间隔边界上的正确划分区；(2)支持向量不会出现在间隔以外的正确划分区；(3)非支持向量一定位于带间隔的正确划分区。第十六页，共65页。目录线性可分的支持向量（分类）机线性支持向量（分类）机支持向量（分类）机最小二乘支持向量（分类）机硬-带支持向量（回归）机软-带支持向量（回归）机

-支持向量（回归）机最小二乘支持向量（回归）机支持向量机应用第十七页，共65页。三、支持向量(分类)机对于一般的非线性可分情况。对于训练集D，无法寻找到来如前的超平面来划分。第十八页，共65页。支持向量(分类)机下面通过核技术来处理。引入一个非线性映射把输入空间映射到一个(高维的)Hilbert空间H,使数据在H中是线性可分或线性不可分：输入空间XiHilbert空间H线性可分线性不可分第十九页，共65页。在核映射下，D对应于Hilbert空间H的训练集为：支持向量(分类)机于是在Hilbert空间H中寻找使几何间隔最大的超平面，其原始优化问题为：(8)第二十页，共65页。问题(8)对应的对偶问题为：支持向量(分类)机(9)求解对偶问题(9),可得如下决策函数：第二十一页，共65页。b*问的计算如下：支持向量(分类)机选取的一个正分量0<j*<C,计算第二十二页，共65页。在问题(9)中K(x,x’)称为核函数。有：支持向量(分类)机核函数K(x,x’)仅依赖于的内积，要求满足Mercer条件。若K是正定核的话，问题(9)是凸二次规划，比有解。在支持向量机应用中，核函数K(x,x’)一般先验性地选取。常见的核有：线性核、多项式核、高斯核、Sigmoid核、样条核、小波核等等。第二十三页，共65页。线性核：支持向量(分类)机Sigmoid核:多项式核:高斯核:第二十四页，共65页。目录线性可分的支持向量（分类）机线性支持向量（分类）机支持向量（分类）机最小二乘支持向量（分类）机硬-带支持向量（回归）机软-带支持向量（回归）机

-支持向量（回归）机最小二乘支持向量（回归）机支持向量机应用第二十五页，共65页。四、最小二乘支持向量(分类)机

Suykens等人在支持向量回归机中引入如下的二次损失函数作为代价函数，并将其不等式约束改为等式约束：且带有如下等式约束条件：其中

因此，把支持向量机的原始优化问题转变为如下寻找w和b的优化问题：

第二十六页，共65页。最小二乘支持向量(回归)机为了在对偶空间中求解上述优化问题，定义如下的Lagrange泛函：其中kR为乘子（叫做支持向量）。

其优化条件由下式给出：第二十七页，共65页。最小二乘支持向量(回归)机上式能被直接表示为求解如下如下线性方程组：其中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。

第二十八页，共65页。最小二乘支持向量(回归)机根据Mercer定理，最小二乘支持向量分类器为：其中与b通过求解上述方程组得到。第二十九页，共65页。例子：最小二乘支持向量(分类)机第三十页，共65页。目录线性可分的支持向量（分类）机线性支持向量（分类）机支持向量（分类）机最小二乘支持向量（分类）机硬-带支持向量（回归）机软-带支持向量（回归）机

-支持向量（回归）机最小二乘支持向量（回归）机支持向量机应用第三十一页，共65页。五、硬-带支持向量（回归）机1、一个简单的回归例子。

考虑两个量x与y的关系。假设已测得若干个数据构成的数据集D：第三十二页，共65页。硬-带支持向量（回归）机第三十三页，共65页。五、硬-带支持向量（回归）机2、不敏感损失函数

为了在回归问题中使用结构风险代替经验风险来作为期望风险，以及保持在支持向量分类机的稀疏性质，Vapnik引入了如下的不敏感损失函数：其中：第三十四页，共65页。硬-带支持向量（回归）机第三十五页，共65页。硬-带支持向量（回归）机首先考虑硬-带支持向量线性回归情况。设有如下两类样本的训练集：即使用一个线性函数来回归（拟合、逼近）样本点，且这种情况下，没有样本点落在-带外。表示为如下的原始优化问题：y=(w.x)+b+y=(w.x)+b-y=(w.x)+b第三十六页，共65页。硬-带支持向量（回归）机为求解上述原始优化问题,使用Lagrange乘子法将其转化为对偶问题。于是引入Lagrange函数：其中，称为Lagrange乘子。首先求Lagrange函数关于w,b的极小值。由极值条件有：得到：第三十七页，共65页。硬-带支持向量（回归）机将上式代入Lagrange函数，则原始的优化问题转化为如下的对偶问题(使用极小形式)：求解上述对偶问题，得(*)。则参数对(w,b)可由下式计算：选择某个j>0或j*>0来计算b:第三十八页，共65页。硬-带支持向量（回归）机支持向量：称训练集D中的样本xi为支持向量，如果它对应的i*>0或i>0

。把w的式子代入函数：于是，得到如下的回归函数：y=(w.x)+b+y=(w.x)+b-y=(w.x)+b第三十九页，共65页。目录线性可分的支持向量（分类）机线性支持向量（分类）机支持向量（分类）机最小二乘支持向量（分类）机硬-带支持向量（回归）机软-带支持向量（回归）机

-支持向量（回归）机最小二乘支持向量（回归）机支持向量机应用第四十页，共65页。软-带支持向量（回归）机考虑软-带支持向量线性回归情况。设有如下两类样本的训练集：同样希望使用一个线性函数来回归样本点，且这种情况下，除了大量样本点在-带内，还有少量的样本落在-带外。这时需要对落在-带外的样本进行惩罚。于是原始优化问题为：y=(w.x)+b+y=(w.x)+b-y=(w.x)+b第四十一页，共65页。软-带支持向量（回归）机为求解上述原始优化问题,使用Lagrange乘子法将其转化为对偶问题。于是引入Lagrange函数：其中，称为Lagrange乘子。首先求Lagrange函数关于w,b,(*)的极小值。由极值条件有：第四十二页，共65页。软-带支持向量（回归）机将上式代入Lagrange函数，则原始的优化问题转化为如下的对偶问题(使用极小形式)：求解上述对偶问题，得(*)。则参数对(w,b)可由下式计算：b的计算（略）。第四十三页，共65页。软-带支持向量（回归）机支持向量：称训练集D中的样本xi为支持向量，如果它对应的i*>0或i>0

。把w的式子代入函数：于是，得到如下的回归函数：y=(w.x)+b+y=(w.x)+b-y=(w.x)+b第四十四页，共65页。目录线性可分的支持向量（分类）机线性支持向量（分类）机支持向量（分类）机最小二乘支持向量（分类）机硬-带支持向量（回归）机软-带支持向量（回归）机

-支持向量（回归）机最小二乘支持向量（回归）机支持向量机应用第四十五页，共65页。-支持向量（回归）机下面通过核技术来处理。引入一个非线性映射把输入空间映射到一个(高维的)Hilbert空间H,使在H中进行线性回归（硬-带或软-带）：输入空间XHilbert空间H硬-带线性回归软-带线性回归第四十六页，共65页。在核映射下，D对应于Hilbert空间H的训练集为：-支持向量（回归）机于是在Hilbert空间H中进行线性回归，其原始优化问题为：第四十七页，共65页。上述问题的对偶问题为：-支持向量（回归）机求解对偶问题,可得如下回归函数：第四十八页，共65页。目录线性可分的支持向量（分类）机线性支持向量（分类）机支持向量（分类）机最小二乘支持向量（分类）机硬-带支持向量（回归）机软-带支持向量（回归）机

-支持向量（回归）机最小二乘支持向量（回归）机支持向量机应用第四十九页，共65页。四、最小二乘支持向量(回归)机假定xXRd表示一个实值随机输入向量，yYR表示一个实值随机输出变量。记RN表示一高维的特征空间，为一非线性映射:X，它映射随机输入向量到高维特征空间。

支持向量方法的思想是在该高维特征空间中考虑如下线性函数集：我们考虑在函数表示式中含噪声情形。给定一个由未知分布FXY产生的、独立同分布（i.i.d.）的训练集：这里ekR假定为独立同分布的随机误差，且E[ek

|X=xk]=0，Var[ek]=2<；m(x)F为一个未知的实值光滑函数，且E[yk

|x=xk]=f(xk)。第五十页，共65页。最小二乘支持向量(回归)机函数估计的目的是在约束||w||a,aR下通过最小化如下经验风险来寻找w和b:

最小二乘支持向量回归机（LS-SVR）定义了与标准支持向量机不同的代价函数，选用损失函数为误差ek的二次项，并将其不等式约束改为等式约束，因此寻找w和b的优化问题可以转化为如下具有岭回归形式的优化问题：且带有如下等式约束条件：其中

第五十一页，共65页。最小二乘支持向量(回归)机为了在对偶空间中求解上述优化问题，定义如下的Lagrange泛函：其中kR为乘子（叫做支持向量）。

其优化条件由下式给出：第五十二页，共65页。最小二乘支持向量(回归)机上式能被直接表示为求解如下如下线性方程组：其中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。

第五十三页，共65页。最小二乘支持向量(回归)机根据Mercer定理，函数估计的最小二乘支持向量回归模型为：其中与b通过求解上述方程组得到。第五十四页，共65页。目录线性可分的支持向量（分类）机线性支持向量（分类）机支持向量（分类）机最小二乘支持向量（分类）机硬-带支持向量（回归）机软-带支持向量（回归）机

-支持向量（回归）机最小二乘支持向量（回归）机支持向量机应用第五十五页，共65页。九、支持向量机应用1、手写体数字识别。SVM的第一个应用是手写字符识别问题。Vapnik、Burges、Cortes、Scholkopf等研究了该问题。使用最大间隔和软间隔SVM。使用高斯核和多项式核。在两个数据集USPS(美国邮政服务局)和NIST(国家标准技术局)。其中USPS数据集包括7291个训练样本，2007个测试样本，用256维的向量(16×16矩阵)表示，每个点的灰度值0～255。

NIST数据集包括60000个训练样本，10000个测试样本，图像为20×20矩阵表示。结果表明SVM具有一定的优势。第五十六页，共65页。九、支持向量机应用2、文本分类。根据文本的内容自动地把它归类。比如邮件过滤、网页搜索、Web挖掘、信息检索等。Joachims，Dumais等人进行SVM对文本分类的研究工作。使用的数据集为路透社(Reuters)第21578号新闻数据库。该数据库共有12902个文本，包括9603个训练的文本和3299个测试样本。每个文本大约包含200个单词，分属于118类，如金融、运输等。主要使用线性核。结果表明SVM比其他的分类算法（如决策树、K-近邻算法等）具有良好的性能。第五十七页，共65页。九、支持向量机应用3、图像识别。(1)视位无关的分类

Pontil、Verri研究了使用SVM于与视位无关的目标识别。第五十八页，共65页。九、支持向量机应用(2)基于颜色的分类

OliverChapelle及其合作者研究了仅使用颜色与光照信息下的SVM目标识别。第五十九页，共65页。九、支持向量机应用(3)可视场景中的目标检测

人脸检测：给定任意图像作为输入，检测其中是否有人脸存在，以及人脸的位置。Osuna等人开发的系统，尽可能扫描像人脸的模式，然后利用SVM作为分类器，检查一幅给定的图像是否有人脸。数据库中包含脸与非脸的模式，图像用19×19=361个像素的向量表示，训练一个软间隔分类器，使用二阶多项式核。汽车行进的可视场景中的行人检测：M.Oren等人多项式核的SVM作为分类器，在之前端使用小波作为特征提取的方法。第六十页，共65页。九、支持向量机应用4、语音信号处理。(1)说话人识别

(2)语音情感识别(3)……第六十一页，共65页。九、支持向量机应用5、信息安全领域。(1)入侵检测

(2)病毒检测(3)数字水印技术(4)……第六十二页，共65页。九、支持向量机应用6、时间序列。(1)经济预警

(