支持向量机SVM

支持向量机jyzw_zw2010-7-13主要内容一.支持向量机的理论基础——统计学习理论二.支持向量机的基本思想三.支持向量机存在问题与研究展望一.支持向量机的理论基础——统计学习理论SVM的理论基础——统计学习理论机器学习问题G：产生器，产生随机向量x；S：训练器，对给定输入x输出相应的y；LM：学习机器，从给定的函数集中选择最能逼近训练器的函数。机器学习目的通过有限的观测数据（xi，yi）来估计输入与输出的函数关系，并有一定的预测推广能力传统的机器学习理论基础——统计学缺点：统计学研究的是样本数目趋于无穷大时的渐近理论实际问题：样本有限（小样本）统计学习理论对小样本统计估计和预测学习的最佳理论V.Vapnik六、七十年代创立，九十年代在此基础上创立支持向量机（SVM）统计学习理论（SLT）问题表示根据n个独立同分布的观测样本在一组函数集{f(x,w)}中求最优函数f(x,w0)对依赖关系进行估计，使期望风险最小。三类机器学习（1）模式识别问题：y={0，1}（2）回归估计问题（函数逼近）：y输出为实数（3）密度估计问题由于样本的有限，使用经验风险代替期望风险经验风险最小化（ERM）准则经验风险最小是否真的使真实风险最小？问题事实上，训练误差小并不总能导致好的预测效果，某些情况下，训练误差小导致推广能力下降，即真实风险增加，这就是过学习问题推广性的界置信范围l：样本数h：VC维VC维如果存在h个样本能够被函数集里的函数按所有的种形式分开，称函数集能够把h个样本打散。2hVC维就是能够打散的最大样本数VC维无通用的计算方法。特别的，N维实空间线性函数VC维是N+1结构风险最小化（SRM）原则在函数集中折中考虑经验风险和置信范围，取得实际风险的最小。支持向量机（SVM）就是这种思想的具体体现！二.支持向量机的基本思想支持向量机的基本思想最大间隔低VC维高推广能力核函数解决低维线性不可分问题线性可分问题最优分类超平面0iwxb•分类超平面：•判决函数：•间隔：•几何间隔：•最大间隔问题：在间隔固定为1时，寻求最小的sgn(){1,1}iiiywxby()iiiywxbiww优化问题：问题求解：（Lagrange乘子法）得出对偶问题：212min..[()]10(1,2,...,)iiwstywxbin11111min()2..0,0,1,2,...,lllijijijjijjliiiiyyxxstyil原问题最优解：决策函数：**1()sgn(())liiiifxyxxb**1liiiiwyx支持向量：分类超平面仅与离超平面最近的样本点相关（如H1和H2面上的点）这些输入向量称为支持向量线性不可分情况——核函数的引入低维不可分问题高维未必不可分一个简单的例子二维平面中分类曲线为椭圆（线性不可分）22112231220wxwxwxxb两维向三维的映射：三维空间中线性可分分类面：根据支持向量机求得决策函数为22121231212:(,)(,,):(,,2)xxzzzxxxx'''1122330wzwzwzb**1()sgn{()()]}liiiifzyzzb的内积计算：令称为核函数高维空间中内积计算可以通过计算低维空间的内积得到，核函数就是连接低维与高维之间的桥梁。'()()]zz,,,,1122332,22,2,,11221122,,21122,2()()]2()()zzzzzzzzxxxxxxxxxxxxxx,,2(,)(,)Kxxxx高维空间中支持向量机得出的决策函数可改写成：因此得出一般的情形：对于线性不可分的样本，作一个低维到高维的映射，使之在高维的空间中线性可分，在高维空间中采用最大间隔标准得出决策函数，由于巧妙的选取核函数，决策函数中在计算内积时只需换成核函数即可。优点：由于核函数的特性，只需计算低维空间内积，而无需计算高维空间的内积，因此计算量与样本维数无关，只与样本数有关。**1()sgn{(,)}liiiifxyKxxb常用核函数：多项式核：径向基核：Sigmoid核：Mercer核：所以满足Mercer条件的对称函数，所有核函数要满足Mercer条件！,,(,)(())dKxxxxc2,,2(,)exp{}xxKxx,,(,)tanh[()]Kxxvxxc支持向量机的优势有坚实的理论基础基于结构风险最小化，克服了传统方法的过学习和陷入局部最小的问题，具有很强的泛化能力；采用核函数方法，向高维空间映射时不增加计算的复杂性，又克服了维数灾难支持向量机存在的问题与研究展望SVM存在的问题样本数目增多时，训练速度变慢SVM解决的是两分类问题，因此需要多分类问题的改进核函数的选择：没有统一的指导标准研究展望针对大规模样本进行算法优化，加快训练速度多分类问题：一对多、一对一、决策树支持向量机本身改进，如已有的最小二乘支持向量机等样本数据集偏斜问题（unbalanced）利用核思想，将线性算法非线性核化支持向量机及其改进算法在其他领域的应用核函数选取问题的思考：（1）多种核加权组合（通过实验方法确定权值），是否可通过反馈机制或迭代方式动态选取权值（2）按照Mercer条件构造其他核函数，核函数各种运算性质（3）Mercer条件需要核函数的正定条件太严格，是否可以放松条件（4）Mercer核具有相似性测度意义，核函数的输出相当于两两样本之间的相似性衡量，输入不再局限于实值函数，可以各种形式、各种结构的数据谢谢！