机器学习SVM

第4.2节SVM内容SVM概述结构风险最小化线性SVMSVM求解处理线性不可分问题SVM训练算法概述：支持向量机发展历史1963年，Vapnik在解决模式识别问题时提出了支持向量方法。起决定性作用的样本为支持向量1971年，Kimeldorf构造基于支持向量构建核空间的方法1992年，Vapnik等人开始对支持向量机进行研究。1995年，Vapnik等人正式提出统计学习理论。概述通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。上个世纪90年代，支持向量机获得全面发展，在实际应用中，获得比较满意的效果，成为机器学习领域的标准工具常用的机器学习方法比较概率分布的方法（经典的方法）Bayes方法,GMMs用于复杂分布建模决策树的方法（C4.5）属性具有明确含义时使用，一种经典的方法近邻分类简单的方法，如果样本有代表性，维数不高时好用支撑向量机高维空间的小样本学习Boosting算法大量训练样本下可以取得好的效果，速度很快人工神经网络ANN大量训练样本下可以取得好的效果，速度较慢SVM案例：手写体数字识别例子贝尔实验室对美国邮政手写数字库进行的实验该数据共包含7291个训练样本，2007个测试数据，输入数据的维数为16x16维分类器/学习方法错误率人工表现2.5%决策树C4.516.2%三层神经网络5.9%SVM4.0%DeepLearning1.0%SVM案例：石脑油预测SVM案例：目标检测弱监督的多形态的高清航拍图像目标检测识别内容SVM概述结构风险最小化线性SVMSVM求解处理线性不可分问题SVM训练算法VC维与经验风险分类问题图示：过拟合与欠拟合underfitting欠拟合Overfitting过拟合goodfit较好的拟合问题:小的经验风险并不意味着期望风险R小.结构风险最小化实际风险（测试误差）:Risk经验风险（训练误差）：Empiricalrisk结构风险的界：以概率VCdimension1VCconfidence证明：在PAC理论部分1|(,)|(,)2trueErroryfxdPxy11()|(,)|2ntrainiiiErroryfxn(log(2/)1)log(/4)truetrainhnhErrorErrorn结构风险最小化原则结构风险最小化Vapnik-Chervonenkis(VC)dimensionVC维定义为一组函数，如平面、直线等在空间打散（任意分类）样本的能力例如，直线的VC维为3，当4个样本点时，无法任意分类（直线右侧分类-1，左侧为1）内容SVM概述结构风险最小化线性SVMSVM求解处理线性不可分问题SVM训练算法线性SVM线性分类器解决的问题：根据一个带有类别标号的训练集合，通过学习一个线性分类面，使得训练集合按照类别进行划分通常转化成一个优化问题以两类监督分类问题问题为例来解释分类面：把一个空间按照类别切分两部分的平面，在二维空间中，分类面相当于一条直线，三维空间中相当于一个平面,高维空间为超平面()Tfwbxx线性分类面函数形式为：wT,b是分类面函数参数,x是输入的样本,wT权向量,b是偏移量线性SVM线性SVM代入(1,0),(0,1)验证f0()Tfxwbx线性分类面函数：()0for1sgn()0for1TiTifxwbyyfxfxwbyxx2()(1,1)10fxx0()(1,1)0fxx1()(1,1)10fxx()0Tifxwbx如果则为xi分类面上的点，反之也成立。(0,1)T(1,0)T2f1f0f(1,1);0Twb如果w相同，则分类面是平行的，b是一个偏移量1y1y(1,0)T(0,1)T线性SVM线性分类器学习：从给定的训练样本确定wT和b这两个参数。得到参数以后，就确定了分类面，从而可以对输入样本进行分类。阐述一下各个参数的性质0;()0TTTTwbwbwbw1212xssss当s1和s2都在分类面上时，这表明wT和分类面上任意向量正交，并称wT为分类面的法向量。(0,1)T(1,0)T2f1f0fwT几何解释：线性分类器的作用就是把输入样本在法向量上投影变成一维变量，然后给一个阈值来分类fxyest表示+1表示-1f(x,w,b)=sign(wx+b)如何分类这些数据？wx+b0wx+b0线性SVMfxyest表示+1表示-1f(x,w,b)=sign(wx+b)如何分类这些数据？线性SVMfxyest表示+1表示-1f(x,w,b)=sign(wx+b)任何一个分类器（一条线）都有效..但是哪一个是最好的?线性SVMfxyest表示+1表示-1f(x,w,b)=sign(wx+b)你如何训练分类器？假设你的测试数据可能出现在这里线性SVMfxyestf(x,w,b)=sign(wx+b)Max-marginfxyest表示+1表示-1f(x,w,b)=sign(wx+b)定义分类器的边界以改善分类性能.线性SVM表示+1表示-1Maximummarginlinearclassifier就是最大化边界地带的意思.这是一种线性化的SVMLinearSVMSupportVectors是边界上的一些样本点1.这种理论说明只有Margin上的样本点是重要的，其他样本都不重要2.实践证明这种假设效果非常好.Max-margin线性SVMSVM从线性可分情况下的分类面发展而来Margin最大化分类面不仅仅要求经验风险尽可能的小，且使分类间隔最大SVM考虑寻找一个满足分类要求的分类面过两类样本中离分类面最近的点且平行于分类面的训练样本就叫做支持向量线性SVM线性关系:w.x++b=+1w.x-+b=-1w.(x+-x-)=2X-x+M=MarginWidth()2Marginwxxww线性SVMMax-margin线性SVM假定训练数据线性分类面函数Max-margin转化成优化问题(.)0,,TdwbwRbRx1(,),...,(,),,{1,1}dnyyRy1lxxx22maxminww线性SVM211()()22(())1,1,...,TTiQix最优分类面求解问题表示成约束优化问题最小化目标函数约束条件内容SVM概述结构风险最小化线性SVMSVM求解处理线性不可分问题SVM训练算法线性SVM求解定义Lagrange函数211()()22(())1,1,...,TTiQix2121(,,)((())1)nTiiiiLwbwywbx最优分类面问题表示成约束优化问题最小化目标函数约束条件线性SVM求解Lagrange函数优化问题的回顾1629年，Lagrange最初是为了解决等式约束的最优化解1951年，Kuhn和Tucker进一步把这个方法扩展到具有不等式约束的情况下，而他们理论实际基于Karush的工作。通过对偶理论简化约束条件即Karush-Kuhn-Tucker互补条件解决了支持向量机的优化问题Lagrange函数2121(,,)((())1)nTiiiiLwbwywbx(,,)0;(,,)0LwbLwbbw110;nniiiiiiiaywyx121,11()()0,1,...,,0((())1)0nniijijijiijniiiiTiiiWyyinandyywbxxx线性SVM求解KKT条件线性SVM求解:例子3x2x1x2221234223341()()(444)2Wx1=(0,0)T,y1=+1x2=(1,0)T,y2=+1x3=(2,0)T,y3=-1x4=(0,2)T,y4=-1121,1()()nniijijijiijWyyxx代入x,y值4x思考：当数据量很大的时候怎么办？可调用Matlab中的二次规划程序，求得1,2,3,4的值，进而求得w和b的值。1234013/41/41120312002144231113,02224132()142TTwbfxWxbx代入(3/2,0),(0,3/2)点可以知道3x2x1x4x内容SVM概述结构风险最小化线性SVMSVM求解处理线性不可分问题SVM训练算法处理线性不可分的情况软间隔KernelSVM线性SVM求解:软间隔最优化问题21,12s.t.10,1,2,...,0,1,2,...,minniiwbiiiiCybininwwx将上述问题表示成拉格朗日乘子式Kuhn-Tucker条件iiiiiiiiiibwxyCwL)](1[||||2120000,[1()]00iiiiiiiiiiiiiiiLwyxwLybLCywxb线性SVM:软间隔得到只要确定，便可解出w与b0;0[1()]000iiiiiiiiiiiiiiiwyxyCywxbC线性SVM:软间隔将上述条件代入L中新的优化问题(QuadraticPrograming)iiiiiiiiiiiiiCybwxywL)(||||2120021,iiiijijijijiiiyCxxyyL线性SVM:软间隔直观的想法:原始数据可以映射到一个高维空间，这些原始数据在低维空间基于线性分类面可能是不可分的，或者分得不好，而在高维空间却可以获得好的分类性能:Φ:x→φ(x)KernelSVMs什么样的函数可以做核函数？如果K(xi,xj)总可以写成：K(xi,xj)=φ(xi)Tφ(xj)的形式，则K可以做核函数.Mercer’s定律:每一个半正定的对称函数都可以是一个核函数半正定的对称函数对应半正定的矩阵: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=线性分类器的运算是内积运算K(xi,xj)=xiTxj如果Φ:x→φ(x),则内积变为:K(xi,xj)=φ(xi)Tφ(xj)“核函数”就变为了高维空间的内积函数.例如:2-维向量x=[x1x2];如果K(xi,xj)=(1+xiTxj)2,且K(xi,xj)=φ(xi)Tφ(xj):K(xi,xj)=(1+xiTxj)2,=1+xi12xj12+2xi1xj1xi2xj2+xi22xj22+2xi1xj1+2xi2xj2=[1xi12√2xi1xi2xi22√2xi1√2xi2][1xj12√2xj1xj2xj22√2xj1√2xj2]T=φ(xi)Tφ(xj),其中φ(x)=[1x12√2x1x2x22√2x1√2x2]核函数举例：核函数举例：线性:K(xi,xj)=xiTxj多项式函数p:K(xi,xj)=(1+xiTxj)pRBF核函数:)2exp(),(22jijixxxxK目标函数形式:求解获得系数和支撑向量以后，分类器构造:线性SVM:K