支持向量机(SVM).ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Support Vector Machines,支持向量机,张 永,Overview,Support Vector Machines(SVM),简介,SVM,特点,Applications,Discussion,研究现状,2,研究背景,传统统计学研究的是,样本数目趋于无穷大时的渐近理论,，即当样本趋于无穷多时的统计性质。但在实际问题中，样本数目往往是有限的。,Vapnik,等人开始研究有限样本情形下统计规律及学习方法性质的理论，即,统计学习理论,(SLT,，,Statistical Learning Theory),，它为有限样本的机器学习问题建立了一个良好的理论框架，较好地解决了小样本、非线性、高维数和局部极小点等实际问题。在此基础上，提出,支持向量机,(SVM,Support Vector Machine),，但仍存在许多有待进一步研究和探讨的问题,分类 回归,3,Linear Classifiers,f,x,a,y,est,denotes+1,denotes-1,f,(,x,w,b,)=sign(,w,x,+,b,),How would you classify this data?,w,x,+,b=0,w,x,+,b0,4,Linear Classifiers,f,x,a,y,est,denotes+1,denotes-1,f,(,x,w,b,)=sign(,w,x,+,b,),How would you classify this data?,5,Linear Classifiers,f,x,a,y,est,denotes+1,denotes-1,f,(,x,w,b,)=sign(,w,x,+,b,),How would you classify this data?,6,Linear Classifiers,f,x,a,y,est,denotes+1,denotes-1,f,(,x,w,b,)=sign(,w,x,+,b,),Any of these would be fine.,.but which is best?,7,Linear Classifiers,f,x,a,y,est,denotes+1,denotes-1,f,(,x,w,b,)=sign(,w,x,+,b,),How would you classify this data?,Misclassified,to+1 class,8,f,x,a,y,est,denotes+1,denotes-1,f,(,x,w,b,)=sign(,w,x,+,b,),Define the,margin,of a linear classifier as the width that the boundary could be increased by before hitting a datapoint.,Classifier Margin(,间隔,),f,x,a,y,est,denotes+1,denotes-1,f,(,x,w,b,)=sign(,w,x,+,b,),Define the,margin,of a linear classifier as the width that the boundary could be increased by before hitting a datapoint.,9,Maximum Margin,f,x,a,y,est,denotes+1,denotes-1,f,(,x,w,b,)=sign(,w,x,+,b,),The,maximum margin linear classifier,is the linear classifier with the,um,maximum margin.,This is the simplest kind of SVM(Called an LSVM),Linear SVM,Support Vectors,are those datapoints that the margin pushes up against,Maximizing the margin is good according to intuition and theory,Implies that only support vectors are important;other training examples are ignorable.,Empirically it works very very well.,10,11,12,Linear SVM Mathematically,What we know:,w,.,x,+,+b=+1,w,.,x,-,+b=-1,w,.(,x,+,-x,-),=2,“Predict Class=+1”zone,“Predict Class=-1”zone,wx+b=1,wx+b=0,wx+b=-1,X,-,x,+,M,=Margin Width,13,Linear SVM Mathematically,Goal:,1)Correctly classify all training data,if y,i,=+1,if y,i,=-1,for all i,2)Maximize the Margin,same as minimize,We can formulate a Quadratic Optimization Problem and solve for w and b,Minimize,subject to,二次优化问题,14,Solving the Optimization Problem,Need to optimize a,quadratic,function subject to,linear,constraints.,Quadratic optimization problems are a well-known class of mathematical programming problems,and many(rather intricate)algorithms exist for solving them.,The solution involves constructing a,dual problem,where a,Lagrange multiplier,i,is associated with every constraint in the primary problem,:,(Lagrange,乘子法,如何求解,?),Find,w,and b such that,(,w,),=,w,T,w,is minimized;,and for all,(,x,i,y,i,),:,y,i,(,w,T,x,i,+,b,),1,Find,1,N,such that,Q,(,),=,i,-,i,j,y,i,y,j,x,i,T,x,j,is maximized and,(1),i,y,i,=0,(2),i,0 for all,i,15,The Optimization Problem Solution,The solution has the form:,Each non-zero,i,indicates that corresponding,x,i,is a support vector.,Then the classifying function will have the form:,Notice that it relies on an,inner product,between the test point,x,and the support vectors,x,i,we will return to this later.,Also keep in mind that solving the optimization problem involved computing the inner products,x,i,T,x,j,between all pairs of training points.,w,=,i,y,i,x,i,b,=,y,k,-,w,T,x,k,for any,x,k,such that,k,0,f,(,x,)=,i,y,i,x,i,T,x+,b,16,分类问题的数学表示,已知：,训练集包含 个样本点：,说明：,是输入指标向量，或称输入，或称模式，其分,量称为特征，或属性，或输入指标；,是输出指标，或输出,.,问题,：对一个新的模式 ，推断它所对应的输出 是,1,还是,-1.,实质：,找到一个把 上的点分成两部分的规则,.,2,维空间上的分类问题,)n,维空间上的分类问题,.,17,根据给定的训练集,其中，寻找 上的一个实,值函数 ，用决策函数,判断任一模式 对应的 值,.,可见，分类学习机,构造决策函数的方法,(,算法,),，,两类分类问题 多类分类问题,线性分类学习机 非线性分类学习机,分类学习方法,18,SVM,分类问题大致有三种：线性可分问题、近似线性可分问题、线性不可分问题。,分类学习方法,19,分划直线表达式为 “间隔”为,极大化“间隔”的思想导致求解下列对变量 和 的最优化问题,说明：,只要我们求得该问题的最优解 ，从而构造分划,超平面 ，求出决策函数 。,上述方法对一般 上的分类问题也适用,.,原始问题,原始问题：,20,求解原始问题,为求解原始问题，根据最优化理论，我们转化为对偶问题来求解,对偶问题,为原始问题中与每个约束条件对应的,Lagrange,乘子。这是,一个不等式约束条件下的二次函数寻优问题，存在唯一解,21,线性可分问题,计算 ，选择 的一个正分量,并据此计算,事实上，的每一个分量 都与一个训练点相对应。而分划超平面仅仅依赖于 不为零的训练点 ，而与对应于 为零的那些训练点无关。,称 不为零的这些训练点的输入 为,支持向量,(SV),构造分划超平面,决策函数,根据最优解,22,Dataset with noise,Hard Margin:,So far we require all data points be classified correctly,-No training error,What if the training set is noisy?,-,Solution 1,:,use very powerful,kernels,denotes+1,denotes-1,OVERFITTING!(,过学习,),23,24,过学习,Overfitting and underfitting,Problem:,how rich class of classifications q(,x,;,)to use.,underfitting,overfitting,good fit,Problem of generalization,:a small emprical risk R,emp,does not imply small true expected risk R.,Slack variables,can be added to,allow misclassification,of difficult or noisy examples.,Soft Margin Classification,What should our quadratic optimization criterion be?,Minimize,wx+b=1,wx+b=0,wx+b=-1,25,Hard Margin v.s.Soft Margin,The old formulation:,The new formulation incorporating slack variables:,Parameter,C,can be viewed as a way to control overfitting.,Find,w,and,b,such that,(,w,),=,w,T,w,is minimized and for all,(,x,i,y,i,),y,i,(,w,T,x,i,+b),1,Find,w,and,b,such that,(,w,),=,w,T,w,+,C,i,is minimized and for all,(,x,i,y,i,),y,i,(,w,T,x,i,+,b,),1-,i,and,i,0 for all,i,26,Linear SVMs:Overview,The classifier is a,separating hyperplane.,Most,“,important,”,training points are support vectors;they define the hyperplane.,Quadratic optimization algorithms can identify which training points x,i,are support vectors with non-zero Lagrangian multipliers,i,.,Both in the dual formulation of the problem and in the solution training points appear only inside dot products:,Find,1,N,such that,Q(,)=,i,-,i,j,y,i,y,j,x,i,T,x,j,is maximized and,(1),i,y,i,=0,(2)0,i,C,for all,i,f,(x)=,i,y,i,x,i,T,x+,b,27,近似线性可分问题,不要求所有训练点都满足约束条件 ，为此,对第 个训练点 引入,松弛变量,(Slack Variable),把约束条件放松到 。,体现了训练集被错分的情况，可采用 作,为一种度量来描述错划程度。,两个目标,：,1.,间隔 尽可能大,2.,错划程度 尽可能小,显然，当 充分大时，样本点 总可以满足以上约束条件。,然而事实上应避免 太大，所以需在目标函数对 进行惩罚,（即“软化”约束条件）,28,因此，引入一个,惩罚参数,，新的目标函数变为,:,体现了经验风险，而 则体现了表达能力。所以,惩罚参数 实质上是对经验风险和表达能力匹配一个裁决。,当 时，近似线性可分,SVC,的原始问题退化为线性可分,SVC,的原始问题。,近似线性可分问题,29,(,广义,),线性支持向量分类机算法,设已知训练集 ，其中,2.,选择适当的惩罚参数 ，构造并求解最优化问题,3.,计算 ，选择 的一个分量 ，并据此,计算出,4.,构造分划超平面,决策函数,求得,30,Non-linear SVMs,Datasets that are linearly separable with some noise work out great:,But what are we going to do if the dataset is just too hard?,How about,mapping data to a higher-dimensional space:,0,x,0,x,0,x,x,2,31,Non-linear SVMs:Feature spaces,General idea:the original input space can always be mapped to some higher-dimensional feature space where the training set is separable:,:,x,(,x,),32,The,“,Kernel Trick,”,The linear classifier relies on dot product between vectors,K,(x,i,x,j,)=x,i,T,x,j,If every data point is mapped into high-dimensional space via some transformation,:x,(x),the dot product becomes:,K,(x,i,x,j,)=,(x,i,),T,(x,j,),A,kernel function,is some function that corresponds to an inner product in some expanded feature space.,Example:,2-dimensional vectors x=,x,1,x,2,;let,K,(x,i,x,j,)=(1+x,i,T,x,j,),2,Need to show that,K,(x,i,x,j,)=,(x,i,),T,(x,j,):,K,(x,i,x,j,)=(1+x,i,T,x,j,),2,=1+,x,i1,2,x,j1,2,+,2,x,i1,x,j1,x,i2,x,j2,+x,i2,2,x,j2,2,+2,x,i1,x,j1,+,2,x,i2,x,j2,=,1,x,i1,2,2,x,i1,x,i2,x,i2,2,2,x,i1,2,x,i2,T,1,x,j1,2,2,x,j1,x,j2,x,j2,2,2,x,j1,2,x,j2,=,(x,i,),T,(x,j,),where,(x)=,1,x,1,2,2,x,1,x,2,x,2,2,2,x,1,2,x,2,33,What Functions are Kernels?,For some functions,K,(x,i,x,j,)checking that,K,(x,i,x,j,)=,(x,i,),T,(x,j,)can be cumbersome.,Mercer,s theorem:,Every semi-positive definite symmetric function is a kernel,Semi-positive definite symmetric functions correspond to a semi-positive definite symmetric Gram matrix:,K,(,x,1,x,1,),K,(,x,1,x,2,),K,(,x,1,x,3,),K,(,x,1,x,N,),K,(,x,2,x,1,),K,(,x,2,x,2,),K,(,x,2,x,3,),K,(,x,2,x,N,),K,(,x,N,x,1,),K,(,x,N,x,2,),K,(,x,N,x,3,),K,(,x,N,x,N,),K=,34,Examples of Kernel Functions,Linear:,K,(,x,i,x,j,)=,x,i,T,x,j,Polynomial of power,p,:,K,(,x,i,x,j,)=(1+,x,i,T,x,j,),p,Gaussian(radial-basis function network):,Sigmoid:,K,(,x,i,x,j,)=tanh(,0,x,i,T,x,j,+,1,),35,Non-linear SVMs Mathematically,Dual problem formulation:,The solution is:,Optimization techniques for finding,i,Find,1,N,such that,Q(,)=,i,-,i,j,y,i,y,j,K,(x,i,x,j,)is maximized and,(1),i,y,i,=0,(2),i,0 for all,i,f,(x)=,i,y,i,K,(x,i,x,j,)+,b,36,SVM locates a separating hyperplane in the feature space and classify points in that space,It does not need to represent the space explicitly,simply by defining a kernel function,The kernel function plays the role of the dot product in the feature space.,Nonlinear SVM-Overview,37,Properties of SVM,Flexibility in choosing a similarity function,Sparseness of solution when dealing with large data sets,-only support vectors are used to specify the separating hyperplane,Ability to handle large feature spaces,-complexity does not depend on the dimensionality of the feature space,Overfitting can be controlled by soft margin approach,Nice math property:,a simple convex optimization problem which is guaranteed to converge to a single global solution,Feature Selection,38,SVM Applications,SVM has been used successfully in many real-world problems,-text(and hypertext)categorization(,文本,/,超文本分类,),-image classification,-bioinformatics(Protein classification,Cancer classification),-hand-written character recognition,39,Application 1:Cancer Classification,High Dimensional,-p1000;n,(,x,),43,文本分类算法：,朴素贝叶斯,(Nave Bayes,，,NB),K-,最近邻,(K-Nearest Neighbor,KNN),神经网络,(Neural Network,NN),线性最小二乘拟合,(Linear Least Squares Fit,LLSF),决策树,(ID3),支持向量机,实验表明：,NB,、,KNN,、,SVM,较好：,SVM,高精度速度慢；,NB,高速度但精度低。,Yang Y,Liu X.A re-examination of text categorization methods.,ACM SIGIR 1999 (IR:Information Retrieval,信息检索,),44,文本分类特点,:,所需处理的样本空间大,样本维数高,;,文本向量非常稀疏,;,文本特征之间存在较大的相关性,;,文本训练样本集中存在较多的噪音,;,不同文本类别的训练样本数目往往存在较大差别,;,实际应用中,大量高质量文本的获取相当困难,.,标准语料库,:Reuters,和,Ohsumed,Categorization using SVM,The distance between two documents is(,x,)(,z),K,(,x,z,)=(,x,)(,z,)is a valid kernel,SVM can be used with,K,(,x,z,)for discrimination.,Why SVM?,-,High dimensional input space,-Few irrelevant features(dense concept),-Sparse document vectors(sparse instances),-Text categorization problems are linearly separable,46,Some Issues,Choice of kernel,-Gaussian or polynomial kernel is default,-if ineffective,more elaborate kernels are needed,-domain experts can give assistance in formulating appropriate similarity measures,Choice of kernel parameters,-e.g.,in Gaussian kernel,-,is the distance between closest points with different classifications,-,In the absence of reliable criteria,applications rely on the use of a validation set or cross-validation to set such parameters.,Optimization criterion,Hard margin v.s.Soft margin,-a lengthy series of experiments in which various parameters are tested,47,Additional Resources,An excellent tutorial on VC-dimension and Support Vector Machines:,C.J.C.Burges.A tutorial on support vector machines for pattern recognition.Data Mining and Knowledge Discovery,2(2):955-974,1998.,The VC/SRM/SVM Bible:,Statistical Learning Theory by Vladimir Vapnik,Wiley-Interscience;1998,www.kernel-machines.org/,www.csie.ntu.edu.tw/cjlin/libsvm/,台湾 林智仁教授,Chih-Jen Lin,48,SVM,研究现状及研究内容,国内：,张学工,、许建华、李国正等人翻译出版了许多国外关于统计学习理论和支持向量机的经典著作,41-43,，,邓乃扬,、田英杰也出版了,数据挖掘中的新方法一支持向量机,44,；,张铃,研究了支持向量机理论与神经网络规划算法的关系,45,；张翔等基于样本之间紧密度提出了模糊支持向量机,46,；,田盛丰,、,黄厚宽,研究了回归型支持向量机简化算法,47,；张文生等提出了在支持向量机中引入后验概率的方法,48,以及基于邻域原理计算海量数据的支持向量机算法,49,；孙剑等提出了一种改进的,SMO,算法,50,；周水生等提出了训练支持向量机的低维,Newton,算法,51,；李建民、,张拔,等提出了序贯最小优化的改进算法,52,55,；郭崇慧等提出了广义支持向量机优化问题的极大嫡方法,53,；王玲等人在隐空间中采用最小二乘损失函数，提出了最小二乘隐空间支持向量机,54,；业宁提出了一个利用多个拉格朗日乘子协同优化的支持向量机快速学习方法,(MLSVM),56,；郑恩辉等通过在,SVM,的设计中集成样本的不同误分类代价，提出代价敏感支持向量机,(CS-SVM),57,；张浩然等提出了回归最小二乘支持向量机的增量和在线式学习算法,58,；杨绪兵等提出了基于广义特征值的最接近支持向量机,(GEPSVM),59,等。,49,研究内容：,(1),支持向量机学习算法研究,Vapnik,提出的基于可调参数,C,的支持向量计统称为,C,-SVM,系列,；,Sch,lkopf,提出的用于分类和回归的,v,-SVM,系列；,Mangasarian,等人提出的通用支持向量机,(,GSVM,),；,Takuya,和,Lin,等人提出了模糊支持向量机,(,FSVM,),；,Suykens,等人提出了最小二乘支持向量机,(,Least Squares SVM,LS-SVM,),；,Sch,lkopf,最初为了对高维分布进行估计，提出了,One-class SVM,，它解决的是只有正训练样本一个类别的分类问题；而,Tax,等人通过用超球面代替超平面来划分样本，提出了支持向量数据描述,(,Support Vector Data Description,，,SVDD,),；,加权支持向量机,、,光滑支持向量机,(,Smooth SVM,，,SSVM,),、简化支持向量机,(,Reduced SVM,，,RSVM,),、小波向量机,(,Wavelet SVM,),32,、,Lagrangian,支持向量机,(,LSVM,),、支持向量聚类,(Support Vector Clustering,，,SVC,),，以及其他一些新的,SVM,模型。,50,研究内容,(,续,),：,(2),支持向量机训练算法研究,标准支持向量机的训练需要求解一个二次规划的优化问题，传统的解法一般都利用标准二次型优化技术来求解其对偶问题。,选块,(,Chunking,),算法,：,Chunking,算法,；,工作样本集；,Joachims,采用某种启发式的迭代策略，提出了一种称为,SVM,light,的支持向量机分解学习算法；,序贯最小优化算法,(,Sequential Minimal Optimization,SMO),；,应用：,Chang,和,Lin,实现了基于,SMO,算法的,LIBSVM,105,软件；,其他算法,：,增量式学习；,预处理方法，比如,焦李成,等提出了支撑矢量预选取的中心距离比值法。,51,研究内容,(,续,),：,(3),支持向量机多类分类方法研究,支持向量机是针对两分类问题提出的，因此，存在一个如何有效地将其推广到多类别分类的问题。,一对多,(one-against-rest),：其基本想法是把某一种类别的样本当作一个类别，剩余其他类别的样本当作另一个类别，这样就变成了一个两分类问题。,一对一,(one-against-one),：其做法是在多类别中，任意抽取两类进行两两配对，转化成两类问题进行训练学习。识别时，对所构成的多个,SVM,进行综合判断，一般可采用投票方式来完成多类识别。,DAGSVM,(Directed Acyclic Graph SVM),。,直接多类分类,SVM,：将多个分类面的参数求解合并到一个最优化问题中，过求解该最优化问题实现多类分类。该方法使用的变量个数很多，分类精度也不占优势。,SVM,决策树,(Decision Tree Method,，,DTM),：它通常和二叉决策树结合起来，构成多类别的识别器。,52,研究内容,(,续,),：,(4)SVM,核函数构造、参数选择研究,支持向量机的非线性处理能力都是通过,“,核映射,”,的方法来实现的。,“,核映射,”,把输入空间的样本映射到高维的特征空间,H,。,常用的核函数有线性核函数、,d,阶多项式核函数、径向基函数、,Sigmoid,核函数和多层感知机等。,Amari,等人提出了通过,修正核函数,来提高,SVM,分类性能的方法；一些学者对模糊核也作了一些研究。,支持向量机,核函数的选择和参数优化,影响着支持向量机的性能。支持向量机的参数包括核函数的参数以及误差惩罚参数,C,。,留一法,(,Leave-One-Out,，,LOO,),估计是最准确的；每次只留一个样本用于测试，用剩余的其余样本训练支持向量机。,K,重交叉校验估计,(,K,-fold Cross Validation),是对,LOO,估计的一种近似，它将训练数据分成,K,组，每次留出一组作为测试样本，其余的,K,-,1,组作为训练样本，,K,次的平均测试错误作为当前核参数的实际风险的估计。,53,(5),应用研究,应用于模式识别的众多领域：,手写字体与数字识别,61-63,人脸识别和人脸检测,64-67,网络入侵检测,68,69,文本分类,70-72,语音识别,73-75,信号处理,9,76-77,图像分类与识别,78-81,三维物体识别,82-84,人类基因表示数据分析,85-88,蛋白质结构预测,89-91,医疗诊断,92,特征选择,93,94,故障识别,144-147,研究内容,(,续,),：,54,Thanks.,？,55,