SVM原理与应用课件.pptx

《SVM原理与应用课件.pptx》由会员分享，可在线阅读，更多相关《SVM原理与应用课件.pptx（105页珍藏版）》请在三一办公上搜索。

1、原理与应用,大纲,背景线性分类非线性分类松弛变量多元分类应用工具包,2,大纲,背景线性分类非线性分类松弛变量多元分类应用工具包,3,背景,支持向量机,4,为什么要用(个人观点),分类效果好上手快种语言的个理论基础完备妇孺皆知的好模型找工作需要它(利益相关：面试狗一只)应用与原理,5,发展历史,重要理论基础年代，和提出维理论重要理论基础年，提出结构风险最小化理论支持向量机( )是和于年首先提出的它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中,6,作者之一简介, 作者书中详细的论证了统计机器学习之所以区别于传统机器学习的本质，就在于统计机器

2、学习能够精确的给出学习效果，能够解答需要的样本数等等一系列问题。,7,理论基础（比较八股）,统计学习理论的维理论( 或)是研究有限样本情况下机器学习规律的理论( ) 反映了函数集的学习能力，维越大则学习机器越复杂,8,理论基础（比较八股）,结构风险最小化机器学习本质上就是一种对问题真实模型的逼近。这个与问题真实解之间的误差，就叫做风险。结构化风险 经验风险 置信风险经验风险 分类器在给定样本上的误差置信风险 分类器在未知文本上分类的结果的误差，代表了我们在多大程度上可以信任分类器在未知文本上分类的结果。（无法准确估值，给出估计的区间）,9,理论基础（比较八股）,结构化风险 经验风险 置信风险置

3、信风险因素：样本数量，给定的样本数量越大，学习结果越有可能正确，此时置信风险越小；分类函数的维，显然维越大，推广能力越差，置信风险会变大。泛化误差界的公式*()()()公式中()就是真实风险，()就是经验风险，()就是置信风险。统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小，即结构风险最小。,10,理论基础（小结）,统计学习理论的维理论关注的是维结构风险最小化()()(),11,特性,小样本与问题的复杂度比起来，算法要求的样本数是相对比较少的非线性擅长应付样本数据线性不可分的情况，主要通过松弛变量和核函数技术来实现高维模式识别例如文本的向量表示，几万维，反例:,12,大纲,

4、背景线性分类非线性分类松弛变量多元分类应用工具包,13,线性分类器,问题的引入和是两类样本中间的直线就是一个分类函数，它可以将两类样本完全分开。,14,线性函数？,在一维空间里就是一个点在二维空间里就是一条直线在三维空间里就是一个平面如果不关注空间的维数，这种线性函数还有一个统一的名称超平面( ),15,线性函数分类问题,例如我们有一个线性函数()我们可以取阈值为，这样当有一个样本需要判别的时候，我们就看()的值。若()，就判别为类别若()，则判别为类别、均可以是向量中间那条直线的表达式是()，即，我们也把这个函数叫做分类面,16,分类面的决定,分离超平面不是唯一上面的直线都可以对点正确分类分

5、离超平面存在一个最好的,17,分类面的“好坏”量化,一个很直观的感受是，让“离直线最近的点，距离直线尽可能地远”就是分割的间隙越大越好，把两个类别的点分得越开越好,18,“分类间隔”的引入,文本分类分类时样本格式（标示出这个样本属于哪个类别）（文本特征所组成的向量）假设，我们就可以定义一个样本点到某个超平面的间隔为(这是定义)(),19,分类间隔,()()总大于的，而且它的值等于如果某个样本属于该类别的话，而也大于反之，而也小于现在把和进行一下归一化，即用和分别代替原来的和，那么间隔就可以写成,20,分类间隔几何间隔,解析几何中点到直线()的距离公式推广一下，是到超平面()的距离， ()就是上

6、节中提到的分类超平面是什么符号？叫做向量的范数，向量长度其实指的是它的范数用归一化的和代替原值之后的间隔有一个专门的名称，叫做几何间隔,21,量化问题之“支持向量”,被红色和蓝色的线圈出来的点就是所谓的支持向量( ),22,量化问题之“最大化间隔”,原则 就是()，红色和蓝色的线（ 与 ）就是 所在的面，红色、蓝色线之间的间隔就是我们要最大化的分类间的间隔。,23,量化问题之“最大化间隔”,原则几何间隔,24,几何间隔的现实含义,是分类面，而和是平行于，且过离最近的两类样本的直线，与，与之间的距离就是几何间隔,25,几何间隔的存在意义,几何间隔与样本的误分次数间存在关系其中的是样本集合到分类面

7、的间隔， ，即是所有样本中向量长度最长的值（也就是说代表样本的分布有多么广）误分次数一定程度上代表分类器的误差。（证明略）误分次数的上界由几何间隔决定（样本已知的时候）,26,为了使分类面更合适为了减少误分次数最大化几何间隔,27,是否让，目标函数就最小了呢？ 。式子有还有一些限制条件，完整的写下来，应该是这样的求最小值的问题就是一个优化问题，一个带约束的二次规划( , )问题，是一个凸问题凸二次规划区别于一般意义上的规划问题，它有解而且是全局最优的解，而且可以找到,28,如何解二次规划问题,等式约束，是求极值、拉格朗日转化等方法转化为无约束问题不等式约束的问题怎么办？方法一：用现成的 ( )

8、 优化包进行求解(效率低)方法二：求解与原问题等价的对偶问题( )得到原始问题的最优解(更易求解、可以推广到核函数)拉格朗日乘子法拉格朗日对偶性理论支撑,29,求解步骤,转化为对偶问题对偶转化 条件求解极小化拉格朗日乘子极值求解极大化用算法求解乘子,30,、对偶问题的转化给每一个约束条件加上一个拉格朗日乘子（ ），定义拉格朗日函数根据对偶算法与条件约束，这个问题可以从转化为其中 *和*等价条件就是条件*,31,、的极小化那么问题转化为先固定，求的最小值将以上结果代入之前的，得到只含的优化结果,32,、的极大化优化问题接上一步处理结果如果求出了*，那么和就可以随之求解最终得出分离超平面和分类决策

9、函数。那么有什么好方法求呢？,33,、利用算法求解对偶问题中的拉格朗日乘子优化问题接上一步处理结果上述式子要解决的是在参数上求最大值的问题，至于都是已知数算法(略),34,表达式的感性分析(番外篇),线性函数表达式为 ()样本确定了，用数学的语言描述，就是可以表示为样本的某种组合同时不仅跟样本点的位置有关，还跟样本的类别有关（也就是和样本的“标签”有关）。因此用下面这个式子表示才算完整：,35,分类函数的预测,将的表达式带入分类函数后对于新点 的预测，只需要计算它与训练数据点的内积即可（表示向量内积）所有非 所对应的系数都是等于零的，因此对于新点的内积计算实际上只要针对少量的“支持向量”而不是

10、所有的训练数据即可。,36,大纲,背景线性分类非线性分类松弛变量多元分类应用工具包,37,非线性分类问题的引入,我们把横轴上端点和之间红色部分里的所有点定为正类，两边的黑色部分里的点定为负类。试问能找到一个线性函数把两类正确分开么？不能，因为二维空间里的线性函数就是指直线，显然找不到符合条件的直线。,38,非线性分类问题的引入,显然通过点在这条曲线的上方还是下方就可以判断点所属的类别,39,非线性分类问题的引入,这条曲线就是我们熟知的二次曲线，它的函数表达式可以写为：它不是一个线性函数，但是，我们可以新建一个向量和：这样()就可以转化为(),40,非线性分类问题的引入,原先问题是： 转化后的问

11、题： 在任意维度的空间中，这种形式的函数都是一个线性函数原来在二维空间中一个线性不可分的问题，映射到四维空间后，变成了线性可分的。解决线性不可分问题的基本思路向高维空间转化(这种特征变换称作特征映射( )，使其变得线性可分。,41,核函数例子引入,我们文本分类问题的原始空间是维的，在这个维度上问题是线性不可分的。现在我们有一个维空间里的线性函数式中的 和 都是维的向量，只不过 是定值，而 是变量现在我们的输入，是一个维的向量，分类的过程是先把变换为维的向量 ，然后求这个变换后的向量 与向量的内积，再把这个内积的值和相加，就得到了结果，看结果大于阈值还是小于阈值就得到了分类结果。,42,核函数例

12、子引入,我们其实只关心那个高维空间里内积的值，那个值算出来了，分类结果就算出来了。是否能有这样一种函数(),他接受低维空间的输入值，却能算出高维空间的内积值 ？如果有这样的函数，那么当给了一个低维空间的输入以后：这两个函数的计算结果就完全一样，我们也就用不着费力找那个映射关系，直接拿低维的输入往()里面代就可以了,43,假设映射函数是我们要将 映射为那么定义核函数（）为如果要实现该节开头的效果，只需先计算 ，然后计算 即可，然而这种计算方式是非常低效的。比如最初的特征是维的，我们将其映射到维，然后再计算，这样需要()的时间。那么我们能不能想办法减少计算时间呢?,核函数形式化定义,44,核函数,

13、这样的()确实存在。它被称作核函数()，而且还不止一个事实上，只要是满足了条件*的函数，都可以作为核函数。核函数的基本作用就是接受两个低维空间里的向量，能够计算出经过某个变换后在高维空间里的向量内积值。,45,核函数例子,假设和都是维的展开后，得我们可以只计算原始特征和内积的平方，时间复杂度是() ，就等价与计算映射后特征的内积。也就是说我们不需要花时间()了,46,核函数例子,核函数对应的映射函数（时）是,47,核函数举例高斯核,如果和很相近( )，那么核函数值为，如果和相差很大( )，那么核函数值约等于。由于这个函数类似于高斯分布，因此称为高斯核函数，也叫做径向基函数( 简称)。它能够把原

14、始特征映射到无穷维。,48,核函数举例高斯核,49,核函数举例核,既然高斯核函数能够比较和的相似度，并映射到到，回想回归，函数可以，因此还有核函数等等。,50,核函数举例多项式核,刚才我们举的例子是这里多项式核的一个特例（ ， ）。虽然比较麻烦，而且没有必要，不过这个核所对应的映射实际上是可以写出来的。,51,核函数举例线性核,这实际上就是原始空间中的内积。这个核存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一起来,52,核函数小结,我们会经常遇到线性不可分的样例，此时，我们的常用做法是把样例特征映射到高维空间中去如果凡是遇到线性不可分的样例，一律映射到高维空

15、间，那么这个维度大小是会高到可怕的核函数就隆重登场了，核函数的价值在于它虽然也是讲特征进行从低维到高维的转换，但核函数绝就绝在它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，也就如上文所说的避免了直接在高维空间中的复杂计算,53,核函数分类效果图,篱笆部署问题,54,核函数还有什么值得我们注意的,既然有很多的核函数，针对具体问题该怎么选择？对核函数的选择，现在还缺乏指导原则如果使用核函数向高维空间映射后，问题仍然是线性不可分的，那怎么办？松弛变量,55,大纲,背景线性分类非线性分类松弛变量多元分类应用工具包,56,问题的引入,现在我们已经把一个本来线性不可分的文本分类问题，通过映射

16、到高维空间而变成了线性可分的,57,问题的引入,圆形和方形的点各有成千上万个，现在想象我们有另一个样本点，但是这个样本的位置是这样的：,58,近似线性可分问题,就是图中黄色那个点，它是方形的，因而它是负类的一个样本，这单独的一个样本，使得原本线性可分的问题变成了线性不可分的。这样类似的问题（仅有少数点线性不可分）叫做“近似线性可分”的问题。,59,的处理分析,有一万个点都符合某种规律（因而线性可分），有一个点不符合，那这一个点是否就代表了分类规则中我们没有考虑到的方面呢更有可能的是，这个样本点压根就是错误，是噪声，是提供训练集的同学人工分类时一打瞌睡错放进去的。所以我们会简单的忽略这个样本点，

17、仍然使用原来的分类器，其效果丝毫不受影响。,60,硬间隔分类问题,由于我们原本的优化问题的表达式中，确实要考虑所有的样本点（不能忽略某一个，因为程序它怎么知道该忽略哪一个呢？），在此基础上寻找正负类之间的最大几何间隔，而几何间隔本身代表的是距离，是非负的，像上面这种有噪声的情况会使得整个问题无解。这种解法其实也叫做“硬间隔”分类法，因为他硬性的要求所有样本点都满足和分类平面间的距离必须大于某个值。,61,如何评价硬间隔分类,硬间隔的分类法其结果容易受少数点的控制，这是很危险的解决方法：允许一些点到分类平面的距离不满足原先的要求,62,松弛变量的引入,意思是说离分类面最近的样本点函数间隔也要比大

18、。如果要引入容错性，就给这个硬性的阈值加一个松弛变量，即允许因为松弛变量是非负的，因此最终的结果是要求间隔可以比小,63,松弛变量 值的确定,当某些点出现这种间隔比小的情况时（这些点也叫离群点），意味着我们放弃了对这些点的精确分类，而这对我们的分类器来说是种损失但是放弃这些点也带来了好处，那就是使分类面不必向这些点的方向移动，因而可以得到更大的几何间隔（在低维空间看来，分类边界也更平滑）,64,松弛变量 优化问题,我们原始的硬间隔分类对应的优化问题我们要把松弛变量加入到优化问题中，即将损失越小越好,65,软间隔分类器,如果是 ，则为二阶软间隔分类器如果是 ，则为一阶软间隔分类器,66,惩罚因子

19、,惩罚因子 把损失加入到目标函数里的时候，就需要一个惩罚因子（，也就是中工具包中的参数）,67,松弛变量惩罚因子的几点说明,并非所有的样本点都有一个松弛变量与其对应。实际上只有“离群点”才有，没离群的点松弛变量都等于松弛变量的值实际上标示出了对应的点到底离群有多远，值越大，点就越远惩罚因子决定了你有多重视离群点带来的损失，显然当所有离群点的松弛变量的和一定时，你定的越大，对目标函数的损失也越大惩罚因子不是一个变量，整个优化问题在解的时候，是一个事先指定的值,68,核函数 松弛变量,相同点：都是解决线性不可分问题的不同点：在原始的低维空间中，样本相当的不可分，无论你怎么找分类平面，总会有大量的离

20、群点，此时用核函数向高维空间映射一下，虽然结果仍然是不可分的，但比原始空间里的要更加接近线性可分的状态达到了近似线性可分的状态后，此时再用松弛变量处理那些少数“冥顽不化”的离群点,69,的运用：数据集偏斜(),它指的是参与分类的两个类别（也可以指多个类别）样本数量差异很大。比如说正类有个样本，而负类只给了个,70,数据集偏斜(),方形的点是负类。，是根据给的样本算出来的分类面两个灰色点有提供的话，那算出来的分类面应该是，和负类给的样本点越多，就越容易出现在灰色点附近的点，我们算出的结果也就越接近于真实的分类面。,71,问题的解决方法(),惩罚因子，那就是给样本数量少的负类更大的惩罚因子，表示我

21、们重视这部分样本,72,问题的解决方法(),不一定是样本少，还可能是分布不够广“政治类”“体育类”文本分类，体育类集中在“篮球”领域比如可以算算他们在空间中占据了多大的体积，例如给负类找一个超球，它可以包含所有负类的样本，再给正类找一个，比比两个球的半径，就可以大致确定分布的情况但是有些领域分布的确不够广，比如“高考作文” “语言类”,73,问题的解决方法,简单的就是美的在解决偏斜问题的时候用的是方案一，样本数量的比的初始值根据参数调优计算出来咱们先假定说是这么大，就可以定为这么大（：）,74,大纲,背景线性分类非线性分类松弛变量多元分类应用工具包,75,多元分类,是一种典型的两类分类器，即它

22、只回答属于正类还是负类的问题而现实中要解决的问题，往往是多类的问题如何由两类分类器得到多类分类器，就是一个值得研究的问题,76,方案一：一次求解个分类面,一次性考虑所有样本，并求解一个多目标函数的优化问题，一次性得到多个分类面可惜这种算法还基本停留在纸面上，因为一次性求解的方法计算量实在太大，大到无法实用的地步,77,方案二：一类对其余,一类对余类法( ，) 构造类别数个的二元分类器训练时第个分类机取训练集中第类为正类，其余类别点为负类判别时，输入信号分别经过个分类器输出优点每个优化问题的规模比较小，而且分类的时候速度很快缺点分类重叠 不可分类 人为的数据偏斜,78,方案三：一对一,该方法在每

23、两类问训练一个分类器，因此对于一个类问题，将有()个分类器优点避免了数据偏斜训练阶段（也就是算出这些分类器的分类平面时）所用的总时间却比“”方法少很多投票时也会有分类重叠的现象，但不会有不可分类现象缺点类别数为的时候，我们调用了个分类器，类别数如果是，要调用的分类器数目会上升至约个（但是时间上可能还是比少，因为考虑的样本数少）,79,方案四：方法(有向无环图),是针对存在误分现象提出的这种方法的()个分类器，构成一个有向无环图。该有向无环图中含有()个内部节点和个叶结点，每个节点对应一个二类分类器,80,方案四：方法(有向无环图),优点简单易行，只需要使用个决策函数即可得出结果，较“一对一方法

24、提高了测试速度，而且不存在误分、拒分区域由于其特殊的结构，故有一定的容错性，分类精度较一般的二叉树方法高缺点误差积累,81,方案四：方法(有向无环图),的错误累积错误累积在一对其余和一对一方法中也都存在，方法好于它们的地方就在于，累积的上限，不管是大是小，总是有定论的，有理论证明而一对其余和一对一方法中，尽管每一个两类分类器的泛化误差限是知道的，但是合起来做多类分类的时候，误差上界是多少方法根节点的选取我们就总取在两类分类中正确率最高的那个分类器作根节点置信度最大的路径,82,其他方案：决策树、,决策树方法纠错输出编码法()*维编码矩阵类别判定用汉明距离,83,大纲,背景线性分类非线性分类松弛

25、变量多元分类应用工具包,84,的应用,文本分类(下页详谈)图像处理图像过滤、图片分类与检索生物信息技术蛋白质分类语音识别人脸检测、指纹识别手写字体识别网络入侵检测、口令认证、网页分类,85,的文本分类应用,例: 分类 万条微信数据，个类别。条测试数据，其余数据为训练数据。 分类句微博，个类别。句测试数据，其余数据训练。省略恢复“小明买了苹果，很甜。”,86,大纲,背景线性分类非线性分类松弛变量多元分类应用工具包,87,工具包,88,简介,是林智仁( ) 教授开发可以很方便的对数据做分类或回归程序小，运用灵活，输入参数少，并且是开源的，易于扩展，因此成为目前国内应用最多的的库 ( , ),89,

26、工具包,工具包组成(一个可视化的工具, 用来展示训练数据和分类界面, 里面是源码, 其编译后的程序在文件夹下)(四个文件, 用来数据集抽样(), 参数优选(), 集成测试(), 数据检查()(包含四个程序包)其他 源码,90,工具包常用命令, ,91,模型文件,92,源码数据结构举例,93,源码数据结构举例,调用的,94,线性分类器主要为大规模数据的线性模型设计由于采用线性核,所以不需要计算 ,速度更快缺点就是太吃内存了。的数据量需要接近的内存，数据量再大就没法做了,95,什么时候用,当你面对海量的数据时，这里的海量通常是百万级别以上海量数据分为两个层次：样本数量和特征的数量。使用线性和非线性

27、映射训练模型得到相近的效果对模型训练的时间效率要求较高,96,高效分类的理论基础,是个优化的框架， * 它是先确定一个()，或者说先确定它的半径(因为球心就是)，然后在此球内优化泰勒展式的局部模型(一般都是二阶)寻找方向，如果优化成功则球心转移，并扩大半径；如果不成功则球心不变，缩小半径。并如此反复。（区别于 先确定后优化）,97,高效分类的理论基础,是指牛顿法中计算 * 时采用数值迭代解决这个线性系统问题而不是直接高斯消元，其中和分别是目标函数的一阶导和二阶导。通常情况下，这里可以用共轭梯度的近似解来逼近。,98,康奈尔大学对计算机硬件的性能要求比要低,99,是一个开源的短文本(包括标题、短

28、信、问题、句子等)分类工具包它在的基础上针对短文本进一步优化，主要特性有：直接输入文本，无需做特征向量化的预处理二元分词（），去停顿词，做词性过滤基于线性核分类器提供了完整的，用于特征分析和 检验,100,格式 检验 特征分析,101,缺点不支持中文，需要替换分词器,102,总结,背景历史、宏观的理论基础与优点线性分类分类面、间隔最大化、对偶问题求解参数非线性分类问题的提出、核函数定义、举例、对比松弛变量离群点、软间隔、松弛变量、惩罚因子、数据集偏斜问题多元分类多元分类的种方法应用在、图像、网络等方面的分类应用工具包、,103,参考,系列、 、资源推荐林智仁机器学习讲义 讲义刘家峰模式识别,104,谢谢,105,