SVM综述_向量空间-内积空间课件.pptx

《SVM综述_向量空间-内积空间课件.pptx》由会员分享，可在线阅读，更多相关《SVM综述_向量空间-内积空间课件.pptx（42页珍藏版）》请在三一办公上搜索。

1、SVM综述,标签有监督学习模型二类分类模型，可扩展解决多类问题特征空间上间隔最大的线性分类器，通过核技巧解决非线性分类问题分类线性可分支持向量机线性支持向量机非线性支持向量机,背景知识,向量空间内积空间希尔伯特空间Gram矩阵Lagrange对偶问题,向量空间,又称线性空间，是线性代数中心内容和基本概念公理化定义：,内积空间,又称准希尔伯特空间，内积定义的距离完备化后得到一个希尔伯特空间公理化定义：,希尔伯特空间,通过内积诱导出一个范数：如果这个范数是完备的，那么此内积空间就是希尔伯特空间完备的定义：任何一个柯西序列都收敛到此空间中某元素柯西序列的定义：在去掉有限个元素后，可以使得余下的元素中

2、任何两点间的距离的最大值不超过任意给定的正的常数,GRAM矩阵,给定内积中间中一族向量和函数G，其GRAM矩阵是向量内积的对称矩阵，元素由Gij 给出,Lagrange对偶问题,在约束最优化问题中，常常利用拉格朗日对偶性（lagrange duality）将原始问题转化为对偶问题，通过求解对偶问题而得到原始问题的解该方法应用与多种统计学习方法中，如最大熵模型和支持向量机模型,什么是约束优化问题？,引入拉格朗日函数将原问题变化为等价问题：,拉格朗日对偶问题：,注意：原问题和对偶问题不一定是相同解，除非在某些特殊情况,支持向量机的不断改进与发展,感知机 线性可分支持向量机线性可分支持向量机 线性支

3、持向量机线性支持向量机 非线性支持向量机不断改进缺陷，不断适应新的困难问题,感知机 线性可分支持向量机,感知机问题在哪里？当训练数据线性可分时，感知机学习算法存在无穷个解，其解由于不同的初值或迭代顺序可能不同为何出现这一问题？学习策略导致，追求分类的准确率，忽视了分类的置信度如何解决这一问题？修改学习策略，不仅追求分类的准确率，而且要保证以最大的置信度进行分类点到分类面的距离越大，被正确分类的置信度越高；到分类面的距离越小，置信度越低支持向量机学习策略：求解能够正确划分训练数据集并且几何间隔最大 化的超平面,线性可分支持向量机,满足条件的分离超平面存在且唯一,线性可分支持向量机学习算法：,目标

4、函数和限制函数均为凸函数，而且限制函数确实是严格可行的，满足lagrange对偶问题要求，故可以通过求解对偶问题解原问题,证明,线性可分支持向量机的问题 要求数据线性可分，实际数据由于本身性质和噪声干扰，并非线性可分如何解决这个问题：通常情况是，训练数据中有些特异点，将这些特异点去除后，剩下大部分样本点组成的集合是线性可分的对于可能存在的特异点，引入松弛变量，将硬间隔最大化修改为软间隔最大化本质上就是对正确率以及置信度进行了一些妥协，以便得到分离超平面,两种引入松弛变量的方法：,more naturalmeasures overlap in actual distance from the m

5、argin nonconvex optimization problem,measures the overlap in relative distanceconvex optimization problem,线性支持向量机原始学习问题,the proportional amount by which the prediction on the wrong side of its margin 代表松弛量大小，即可允许误差大小、可容忍度大小等于0代表很高置信度分类，即非支持向量；01代表正确分类，但是越过边界，置信度低；大于1代表分类错误尽可能以最高置信度进行分类，故作为惩罚项置于目标函数,

6、C：A large value of C will discourage any positive i,and lead to an overfit wiggly boundary in the original feature space a small value of C will encourage a small value of,which in turn causes f(x)and hence the boundary to be smoother the separable case corresponds to C=尽量使间隔大，同时使误分类点的个数尽量小，C是调和二者之间

7、的系数C具体如何选择，后面会深入讨论,线性支持向量机的学习算法,注意：求的w唯一，但是b不是唯一的。通常求均值,证明,线性支持向量机的等价表述（12.3.2 The SVM as a Penalization Method）,“hinge”loss function L(y,f)=1 yf+合页损失函数 李航 统计学习方法 giving zero penalty to points well inside their margin,and a linear penalty to points on the wrong side and far away 导致只有部分点对模型学习结果有影响，这是

8、支持向量机的本质特点之一 与其他损失函数比较：margin maximizing loss-functions,01损失函数是二类分类问题真正的损失函数，但是不可导，优化其构成的目标函数很困难；可以认为线性支持向量机是优化01损失函数的上界（合页损失函数）构成的目标函数。又称代理损失函数虚线部分为感知机的损失函数，只有分类错误时才有损失；相比之下，合页损失函数不仅要求分类正确，而且置信度足够大时损失才为0；合页损失函数对学习有更高的要求,线性支持向量机的问题要求数据为近似线性可分，如果数据为线性不可分，则无法使用存在非线性可分问题，只有通过一个超曲面才能够将正负例分开如何解决这个问题希望利用S

9、VM线性分类方法解决非线性分类问题将非线性分类问题转化线性分类问题 解决转化后的线性分类问题 解决原始非线性分类问题,经上述分析，得到线性分类方法求解非线性问题的步骤：使用一个变换将原空间的数据映射到新空间在新空间里用线性分类学习方法从训练数据中学习分类模型,核技巧（kernel trick）,通过一个非线性变换将输入空间对应到一个特征空间（希尔伯特空间），使得在输入空间的超曲面对应于特征空间的超平面模型。这样，分类问题学习任务通过在特征空间中求解线性支持向量机就可以完成在学习与预测中只定义核函数K（x，z），而不显式定义映射函数对于给定的核，特征空间和映射函数的取法不一定唯一（举例）,利用核

10、函数设计非线性支持向量机,解决问题的思路清晰之后，需要思考三个问题：什么是核函数？,朴素自然的定义,2.我怎么知道哪个函数是核函数？答：要用正定核函数,证明满足此条件函数为核函数 构造法,3.我用哪个核函数？自己定义？太累，不好判断使用已有核函数？,多项式核函数高斯核函数神经网络核函数字符串核函数（文本分类、信息检索、生物信息方面）到底用哪个？后续讨论,SVM核方法在高维空间会遇到什么问题（12.3.4 SVMs and the Curse of Dimensionality）,we are not allowed a fully general inner product in the sp

11、ace of powers and products the kernel cannot adapt itself to concentrate on subspaces，核函数确定，其映射到的高维空间即确定将输入空间映射为特征空间后，维度增加很多，但是很可能只在某几个维度上是线性可分的，而其他维度特征是冗余的One would have to build knowledge about the subspace into the kernel。If such knowledge were available a priori,much of statistical learning woul

12、d be made much easier 未必掌握先验知识,到底如何挑选核函数？使用核函数后，分类效果差，说明映射后的高维空间线性可分性差；分类效果好，说明映射后的高维空间线性可分性好对映射后高维空间线性可分性无先验判断故只能多次尝试,如何确定支持向量机中参数C？（12.3.5 A Path Algorithm for the SVM Classifier）,The regularization parameter for the SVM classifier is the cost parameter C,or its inverse we need to determine a good

13、 choice for C,perhaps by cross-validation.,a path algorithm for efficiently fitting the entire sequence of SVM models obtained by varying C.,参数 影响margin宽度the KKT optimal-ity conditions imply that the labeled points(xi,yi)fall into three distinct groupsSo all that changes as decreases are the i 0,1 o

14、f those(small number)of points on the margin.ai 随变化而变化,支持向量机损失函数应用到回归分析中（12.3.6 Support Vector Machines for Regression）,SVMs can be adapted for regression with a quantitative response,in ways that inherit some of the properties of the SVM classifier 采用的SVM的特性就是损失函数,“-insensitive”error measure,ignori

15、ng errors of size less than This function reduces from quadratic to linear the contributions of observations with absolute residual greater than a prechosen constant c.This makes the fitting less sensitive to out-liers 共同特点：将不同输入误差的惩罚加以区别导致结果：不同输入对最终模型的影响不同，有影响的叫做“支持向量”the solution depends on the in

16、put values only through the inner products xi,xi.Thus we can generalize the methods to richer spaces by defining an appropriate inner product,核 方法应用到回归中（12.3.7 Regression and Kernels）,kernel property is not unique to support vector machines generalized regression function,目标函数,结论：For any choice of V(r)：ESL对平方误差情况进行了证明As in the support vector machine,we need not specify or evaluate the large set of functions h1(x),h2(x),.,hm(x).Only the inner product kernel K(xi,xi)need be evaluated,