《机器学习SVM学习.pptx》由会员分享，可在线阅读，更多相关《机器学习SVM学习.pptx（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、内 容SVM概述结构风险最小化线性SVMSVM求解处理线性不可分问题SVM训练算法第1页/共48页 概述：概述：支持向量机发展历史支持向量机发展历史1963年，Vapnik在解决模式识别问题时提出了支持向支持向量量方法。起决定性作用的样本为支持向量支持向量1971年，Kimeldorf构造基于支持向量支持向量构建核空间的方法1992年，Vapnik等人开始对支持向量机支持向量机进行研究。1995年，Vapnik等人正式提出统计学习理论。第2页/共48页概述概述通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个
2、凸二次规划问题的求解。上个世纪90年代，支持向量机获得全面发展，在实际应用中，获得比较满意的效果，成为机器学习领域的机器学习领域的标准工具标准工具第3页/共48页常用的机器学习方法比较概率分布的方法（经典的方法）Bayes方法,GMMs 用于复杂分布建模决策树的方法（C4.5）属性具有明确含义时使用，一种经典的方法近邻分类简单的方法，如果样本有代表性，维数不高时好用支撑向量机高维空间的小样本学习Boosting算法大量训练样本下可以取得好的效果，速度很快人工神经网络ANN大量训练样本下可以取得好的效果，速度较慢第4页/共48页SVMSVM案例：案例：手写体数字识别例子手写体数字识别例子贝尔实验
3、室对美国邮政手写数字库进行的实验该数据共包含7291个训练样本，2007个测试数据，输入数据的维数为16x16维分类器/学习方法错误率人工表现2.5%决策树C4.516.2%三层三层神经网络5.9%SVM4.0%DeepLearning1.0%第5页/共48页SVMSVM案例：石脑油预测案例：石脑油预测第6页/共48页SVMSVM案例：目标检测案例：目标检测n弱监督的多形态的高清航拍图像目标检测识别第7页/共48页内 容SVM概述结构风险最小化线性SVMSVM求解处理线性不可分问题SVM训练算法第8页/共48页VCVC维与经验风险维与经验风险分类问题图示：过拟合与欠拟合underfitting
4、欠拟合Overfitting过拟合good fit较好的拟合问题问题:小的经验风险 并不意味着期望风险R小.第9页/共48页结构风险最小化l实际风险（测试误差）:Riskl经验风险（训练误差）：Empirical riskl结构风险的界：以概率VC dimensionVC confidence证明：在PAC理论部分第10页/共48页结构风险最小化原则第11页/共48页结构风险最小化lVapnik-Chervonenkis(VC)dimensionVC 维定义为一组函数，如平面、直线等在空间打散（任意分类）样本的能力例如，直线的VC 维为3，当4个样本点时，无法任意分类l（直线右侧分类-1，左侧
5、为1）第12页/共48页内 容SVM概述结构风险最小化线性SVMSVM求解处理线性不可分问题SVM训练算法第13页/共48页线性SVM线性分类器解决的问题：n根据一个带有类别标号的训练集合，通过学习一个线性分类面，使得训练集合按照类别进行划分n通常转化成一个优化问题n以两类监督分类问题问题为例来解释第14页/共48页分类面：把一个空间按照类别切分两部分的平面，在二维空间中，分类面相当于一条直线，三维空间中相当于一个平面,高维空间为超平面线性分类面函数形式为：wT,b是分类面函数参数,x是输入的样本,wT权向量,b是偏移量线性SVM第15页/共48页线性SVM代入(1,0),(0,1)验证f0线
6、性分类面函数：如果则为xi分类面上的点，反之也成立。如果w相同，则分类面是平行的，b是一个偏移量第16页/共48页 线性SVM线性分类器学习线性分类器学习：从给定的训练样本确定wT和b这两个参数。得到参数以后，就确定了分类面，从而可以对输入样本进行分类。阐述一下各个参数的性质当s1和s2都在分类面上时，这表明wT和分类面上任意向量正交，并称wT为分类面的法向量。wT几何解释：几何解释：线性分类器的作用就是把输入样本在法向量上投影变成一维变量，然后给一个阈值来分类第17页/共48页f xyest表示+1表示-1f(x,w,b)=sign(w x+b)如何分类这些数据？如何分类这些数据？w x+b
7、=0w x+b0 线性SVM第18页/共48页f xyest表示+1表示-1f(x,w,b)=sign(w x+b)如何分类这些数据？如何分类这些数据？线性SVM第19页/共48页f xyest表示+1表示-1f(x,w,b)=sign(w x+b)任何一个分类器任何一个分类器（一条线）都有效（一条线）都有效.但是哪一个是最好但是哪一个是最好的的?线性SVM第20页/共48页f xyest表示+1表示-1f(x,w,b)=sign(w x+b)你如何训练分类器？假设你的测试数据可能出现在这里 线性SVM第21页/共48页f xyestf(x,w,b)=sign(w x+b)Max-margin
8、f xyest表示+1表示-1f(x,w,b)=sign(w x+b)定义分类器的边界以改善分类性能.线性SVM第22页/共48页表示+1表示-1Maximum margin linear classifier就是最大化边界地带的意思.这是一种线性化的SVMLinear SVMSupport Vectors 是边界上的一些样本点1.这种理论说明只有Margin上的样本点是重要的，其他样本都不重要2.实践证明这种假设效果非常好.Max-margin 线性SVM第23页/共48页SVM从线性可分情况下的分类面发展而来MarginMargin最大化分类面不仅仅要求经验风险尽可能的小，最大化分类面不仅
9、仅要求经验风险尽可能的小，且使分类间隔最大且使分类间隔最大SVM考虑寻找一个满足分类要求的分类面过两类样本中离分类面最近的点且平行于分类面的训练样本就叫做支持向量支持向量线性线性SVM第24页/共48页线性关系:w.x+b=+1 w.x-+b=-1 w.(x+-x-)=2“类标号=+1”的区域“类标号=-1”的区域wx+b=1wx+b=0wx+b=-1X-x+M=Margin Width 线性SVMMax-margin第25页/共48页线性线性SVM假定训练数据线性分类面函数Max-margin转化成优化问题第26页/共48页线性线性SVMn最优分类面求解问题表示成约束优化问题约束优化问题最小
10、化目标函数约束条件第27页/共48页内 容SVM概述结构风险最小化线性SVMSVM求解处理线性不可分问题SVM训练算法第28页/共48页线性线性SVM求解求解定义定义LagrangeLagrange函数函数n最优分类面问题表示成约束优化问题最小化目标函数约束条件第29页/共48页线性线性SVM求解求解Lagrange函数优化问题的回顾1629年，Lagrange最初是为了解决等式约束的最优化解1951年，Kuhn和Tucker进一步把这个方法扩展到具有不等式约束的情况下，而他们理论实际基于Karush的工作。通过对偶理论简化约束条件即Karush-Kuhn-Tucker互补条件解决了支持向量机
11、的优化问题第30页/共48页Lagrange函数线性线性SVM求解求解KKT条件条件第31页/共48页线性线性SVM求解求解:例子例子x1=(0,0)T,y1=+1x2=(1,0)T,y2=+1x3=(2,0)T,y3=-1x4=(0,2)T,y4=-1代入x,y值第32页/共48页思考：当数据量很大的时候怎么办？思考：当数据量很大的时候怎么办？可调用Matlab中的二次规划程序，求得1,2,3,4的值，进而求得w和b的值。代入(3/2,0),(0,3/2)点可以知道第33页/共48页内 容SVM概述结构风险最小化线性SVMSVM求解处理线性不可分问题SVM训练算法第34页/共48页处理线性不
12、可分的情况软间隔Kernel SVM第35页/共48页线性线性SVM求解求解:软间隔最优化问题第36页/共48页将上述问题表示成拉格朗日乘子式Kuhn-Tucker条件线性线性SVM:软间隔第37页/共48页得到只要确定，便可解出w与b线性线性SVM:软间隔第38页/共48页将上述条件代入L中新的优化问题(Quadratic Programing)线性线性SVM:软间隔第39页/共48页直观的想法:原始数据可以映射到一个高维空间，这些原始数据在低维空间基于线性分类面可能是不可分的，或者分得不好，而在高维空间却可以获得好的分类性能:x (x)Kernel SVMs第40页/共48页什么样的函数可
13、以做核函数？l如果 K(xi,xj)总可以写成：K(xi,xj)=(xi)T(xj)的形式，则K可以做核函数.lMercers 定律:每一个半正定的对称函数都可以是一个核函数l半正定的对称函数对应半正定的矩阵:K(x1,x1)K(x1,x2)K(x1,x3)K(x1,xN)K(x2,x1)K(x2,x2)K(x2,x3)K(x2,xN)K(xN,x1)K(xN,x2)K(xN,x3)K(xN,xN)K=第41页/共48页l线性分类器的运算是内积运算K(xi,xj)=xiTxjl如果:x (x),则内积变为:K(xi,xj)=(xi)T(xj)l“核函数”就变为了高维空间的内积函数.l例如:2-
14、维向量 x=x1 x2;如果 K(xi,xj)=(1+xiTxj)2,且 K(xi,xj)=(xi)T(xj):K(xi,xj)=(1+xiTxj)2,=1+xi12xj12+2 xi1xj1 xi2xj2+xi22xj22+2xi1xj1+2xi2xj2 =1 xi12 2 xi1xi2 xi22 2xi1 2xi2 1 xj12 2 xj1xj2 xj22 2xj1 2xj2 T =(xi)T(xj),其中(x)=1 x12 2 x1x2 x22 2x1 2x2核函数举例：第42页/共48页核函数举例：l线性:K(xi,xj)=xi Txjl多项式函数 p:K(xi,xj)=(1+xi Txj)plRBF核函数:第43页/共48页l目标函数形式:l求解获得系数和支撑向量以后，分类器构造:线性SVM:Kernal SVM:Kernel SVMs第44页/共48页内 容SVM概述结构风险最小化线性SVMSVM求解处理线性不可分问题SVM训练算法第45页/共48页算法流程：每次选取两个进行更新开始选择两个更新E计算误差误差阈值 结束更新SVM训练算法-SMO第46页/共48页最后得到迭代公式：通过逐步增加支持向量，分类函数逐渐变得复杂，所以VC维逐渐的增加，经验风险减小，可以看到这就是结构风险最小化的求解过程第47页/共48页感谢您的观看。第48页/共48页