《支持向量机及其应用ppt课件》由会员分享，可在线阅读，更多相关《支持向量机及其应用ppt课件（67页珍藏版）》请在金锄头文库上搜索。
1、,数学与计算机学院 彭宏,支持向量机及其应用 Support Vector Machines and its Application,智能算法讲座（一）,目录,线性可分的支持向量（分类）机 线性支持向量（分类）机 支持向量（分类）机 最小二乘支持向量（分类）机 硬-带支持向量（回归）机 软-带支持向量（回归）机 -支持向量（回归）机 最小二乘支持向量（回归）机 支持向量机应用,SVM的描述,SVM是一种基于统计学习理论的模式识别方法，它是由Boser,Guyon,Vapnik在COLT-92上首次提出，从此迅速的发展起来，现在已经在许多领域（生物信息学，文本，图像处理，语言信号处理和手写识别等
2、）都取得了成功的应用 COLT(Computational Learning Theory),SVM的描述,目标：找到一个超平面，使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。 解决方法：构造一个在约束条件下的优化问题，具体的说是一个约束二次规划问题(constrained quadratic programing),求解该问题，得到分类器。,模式识别问题的一般描述,已知：n个观测样本，(x1,y1), (x2,y2) (xn,yn) 求：最优函数y= f(x,w) 满足条件：期望风险最小 损失函数,SVM的描述,期望风险R(w)要依赖联合概率F(x,y)的
3、信息，实际问题中无法计算。 一般用经验风险Remp(w)代替期望风险R(w),一般模式识别方法的问题,经验风险最小不等于期望风险最小，不能保证分类器的推广能力. 经验风险只有在样本数无穷大趋近于期望风险，需要非常多的样本才能保证分类器的性能。 需要找到经验风险最小和推广能力最大的平衡点。,一、线性可分的支持向量(分类)机,首先考虑线性可分情况。设有如下两类样本的训练集：,线性可分情况意味着存在超平面使训练点中的正类和 负类样本分别位于该超平面的两侧。,如果能确定这样的参数对（w,b） 的话,就可以构造决策函数来进行 识别新样本。,线性可分的支持向量(分类)机,问题是：这样的参数对（w,b）有许
4、多。 解决的方法是采用最大间隔原则。,最大间隔原则：选择使得训练集D对于线性函数 (wx)+b的几何间隔取最大值的参数对(w,b)，并 由此构造决策函数。,在规范化下，超平面的几何间隔为 于是，找最大几何间隔的超平面 表述成如下的最优化问题：,(1),线性可分的支持向量(分类)机,为求解问题(1),使用Lagrange乘子法将其转化为对偶问题。于是引入Lagrange函数：,其中， 称为Lagrange乘子。,首先求Lagrange函数关于w,b的极小值。由极值条件有：,得到：,(2),(3),(4),线性可分的支持向量(分类)机,将(3)式代入Lagrange函数，并利用(4)式，则原始的优
5、化问题 转化为如下的对偶问题(使用极小形式)：,这是一个凸二次规划问题 有唯一的最优解,(5),求解问题(5)，得。则参数对(w,b)可由下式计算：,线性可分的支持向量(分类)机,支持向量：称训练集D中的样本xi为支持向量，如 果它对应的i*0。,根据原始最优化问题的KKT条件，有,于是，支持向量正好在间隔边界上。,于是，得到如下的决策函数：,目录,线性可分的支持向量（分类）机 线性支持向量（分类）机 支持向量（分类）机 最小二乘支持向量（分类）机 硬-带支持向量（回归）机 软-带支持向量（回归）机 -支持向量（回归）机 最小二乘支持向量（回归）机 支持向量机应用,二、线性支持向量(分类)机,
6、现在考虑线性不可分情况。对于训练集D，不存在这样的超平面，使训练集关于该超平面的几何间隔取正值。如果要用超平面来划分的话，必然有错分的点。,但我们任希望使用超平面进行分划，这时应“软化” 对间隔的要求，即容许不满足约束条件的样本点存在。,为此，引入松弛变量 并“软化”约束条件：,线性支持向量(分类)机,为了避免i取太大的值，需要在目标函数中对它们进行惩罚。于是原始优化问题变为：,其中C0称为惩罚因子。,(6),线性支持向量(分类)机,类似前面，通过引入如下的Lagrange函数：,得到如下的对偶问题：,(7),线性支持向量(分类)机,求解对偶问题(7),可得如下决策函数：,支持向量有下列性质：
7、 (1)界内支持向量一定位于间隔边界上 的正确划分区； (2)支持向量不会出现在间隔以外的 正确划分区； (3)非支持向量一定位于带间隔的正确划分区。,目录,线性可分的支持向量（分类）机 线性支持向量（分类）机 支持向量（分类）机 最小二乘支持向量（分类）机 硬-带支持向量（回归）机 软-带支持向量（回归）机 -支持向量（回归）机 最小二乘支持向量（回归）机 支持向量机应用,三、支持向量(分类)机,对于一般的非线性可分情况。对于训练集D，无法寻找到来如前的超平面来划分。,支持向量(分类)机,下面通过核技术来处理。引入一个非线性映射把输入空间 映射到一个(高维的)Hilbert空间H,使数据在H
8、中是线性可分 或线性不可分：,线性 可分,线性 不可分,在核映射下，D对应于Hilbert空间H的训练集为：,支持向量(分类)机,于是在Hilbert空间H中寻找使几何间隔最大的超平面，其原始优化问题为：,(8),问题(8)对应的对偶问题为：,支持向量(分类)机,(9),求解对偶问题(9),可得如下决策函数：,b*问的计算如下：,支持向量(分类)机,选取的一个正分量0j*C,计算,在问题(9)中K(x,x)称为核函数。有：,支持向量(分类)机,核函数K(x,x)仅依赖于的内积，要求满足Mercer条件。若K是正定核的话，问题(9)是凸二次规划，比有解。,在支持向量机应用中，核函数K(x,x)一
9、般先验性地选取。常见的核有：线性核、多项式核、高斯核、Sigmoid核、样条核、小波核等等。,线性核：,支持向量(分类)机,Sigmoid核:,多项式核:,高斯核:,目录,线性可分的支持向量（分类）机 线性支持向量（分类）机 支持向量（分类）机 最小二乘支持向量（分类）机 硬-带支持向量（回归）机 软-带支持向量（回归）机 -支持向量（回归）机 最小二乘支持向量（回归）机 支持向量机应用,四、最小二乘支持向量(分类)机,Suykens等人在支持向量回归机中引入如下的二次损失函数作为代价函数，并将其不等式约束改为等式约束：,且带有如下等式约束条件：,其中,因此，把支持向量机的原始优化问题转变为如
10、下寻找w和b的优化问题：,最小二乘支持向量(回归)机,为了在对偶空间中求解上述优化问题，定义如下的Lagrange泛函：,其中kR为乘子（叫做支持向量）。 其优化条件由下式给出：,最小二乘支持向量(回归)机,上式能被直接表示为求解如下如下线性方程组：,其中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。,最小二乘支持向量(回归)机,根据Mercer定理，最小二乘支持向量分类器为：,其中与b通过求解上述方程组得到。,例子
11、：最小二乘支持向量(分类)机,目录,线性可分的支持向量（分类）机 线性支持向量（分类）机 支持向量（分类）机 最小二乘支持向量（分类）机 硬-带支持向量（回归）机 软-带支持向量（回归）机 -支持向量（回归）机 最小二乘支持向量（回归）机 支持向量机应用,五、硬-带支持向量（回归）机,1、一个简单的回归例子。 考虑两个量x与y的关系。假设已测得若干个数据构成的数据集D：,硬-带支持向量（回归）机,五、硬-带支持向量（回归）机,2、不敏感损失函数 为了在回归问题中使用结构风险代替经验风险来作为期望风险，以及保持在支持向量分类机的稀疏性质，Vapnik引入了如下的不敏感损失函数：,其中：,硬-带支
12、持向量（回归）机,硬-带支持向量（回归）机,首先考虑硬-带支持向量线性回归情况。设有如下两类样本的训练集：,即使用一个线性函数来回归（拟合、逼近）样本点，且这种情 况下，没有样本点落在-带外。表示为如下的原始优化问题：,硬-带支持向量（回归）机,为求解上述原始优化问题,使用Lagrange乘子法将其转化为对偶问题。于是引入Lagrange函数：,其中， 称为Lagrange乘子。,首先求Lagrange函数关于w,b的极小值。由极值条件有：,得到：,硬-带支持向量（回归）机,将上式代入Lagrange函数，则原始的优化问题转化为如下的对偶问题(使用极小形式)：,求解上述对偶问题，得(*)。则参
13、数对(w,b)可由下式计算：,选择某个j 0或j* 0来计算b:,硬-带支持向量（回归）机,支持向量：称训练集D中的样本xi为支持向量， 如果它对应的i*0或i0 。,把w的式子代入函数： 于是，得到如下的回归函数：,目录,线性可分的支持向量（分类）机 线性支持向量（分类）机 支持向量（分类）机 最小二乘支持向量（分类）机 硬-带支持向量（回归）机 软-带支持向量（回归）机 -支持向量（回归）机 最小二乘支持向量（回归）机 支持向量机应用,软-带支持向量（回归）机,考虑软-带支持向量线性回归情况。设有如下两类样本的训练集：,同样希望使用一个线性函数来回归样本点，且这种情况下，除了 大量样本点在
14、-带内，还有少量的样本落在-带外。这时需要对 落在-带外的样本进行惩罚。于是原始优化问题为：,软-带支持向量（回归）机,为求解上述原始优化问题,使用Lagrange乘子法将其转化为对偶问题。于是引入Lagrange函数：,其中， 称为Lagrange乘子。,首先求Lagrange函数关于w,b,(*)的极小值。由极值条件有：,软-带支持向量（回归）机,将上式代入Lagrange函数，则原始的优化问题转化为如下的对偶问题(使用极小形式)：,求解上述对偶问题，得(*)。则参数对(w,b)可由下式计算：,b的计算（略）。,软-带支持向量（回归）机,支持向量：称训练集D中的样本xi为支持向量， 如果它
15、对应的i*0或i0 。,把w的式子代入函数： 于是，得到如下的回归函数：,目录,线性可分的支持向量（分类）机 线性支持向量（分类）机 支持向量（分类）机 最小二乘支持向量（分类）机 硬-带支持向量（回归）机 软-带支持向量（回归）机 -支持向量（回归）机 最小二乘支持向量（回归）机 支持向量机应用,-支持向量（回归）机,下面通过核技术来处理。引入一个非线性映射把输入空间 映射到一个(高维的)Hilbert空间H,使在H中进行线性回归（硬-带或软-带）：,在核映射下，D对应于Hilbert空间H的训练集为：,-支持向量（回归）机,于是在Hilbert空间H中进行线性回归，其原始优化问题为：,上述
16、问题的对偶问题为：,-支持向量（回归）机,求解对偶问题,可得如下回归函数：,目录,线性可分的支持向量（分类）机 线性支持向量（分类）机 支持向量（分类）机 最小二乘支持向量（分类）机 硬-带支持向量（回归）机 软-带支持向量（回归）机 -支持向量（回归）机 最小二乘支持向量（回归）机 支持向量机应用,四、最小二乘支持向量(回归)机,假定xXRd表示一个实值随机输入向量，yYR表示一个实值随机输出变量。记RN表示一高维的特征空间，为一非线性映射: X，它映射随机输入向量到高维特征空间。 支持向量方法的思想是在该高维特征空间中考虑如下线性函数集：,我们考虑在函数表示式中含噪声情形。给定一个由未知分布FXY产生的、独立同分布（i.i
