线性判别函数ppt课件

第2章 线性判别函数线性判别函数2.1 线性判别函数和决策面2.2 感知准则函数2.3 最小平方误差准则函数2.4 多类判别问题2.5 分段线性判别函数2.6 Fisher线性判别函数2.7 支持向量机第2章线性判别函数2.1线性判别函数和决策面1课前思考题：课前思考题：(1)机器能否像人类一样通过例证教育认知事物，修正观念中的错误的成分?(2)机器学习过程中有教师吗？谁是教师？(3)什么叫线性分类器?什么条件下才能用线性分类器？课前思考题：2 2.1 线性判别函数和决策面线性判别函数是线性判别函数是统计模式识别方法中的一个重要的基统计模式识别方法中的一个重要的基本方法。它本方法。它是由是由训练样本集训练样本集提供的信息直接确定决策提供的信息直接确定决策域的划分。域的划分。在训练过程中使用的样本集，该样本集中的每个样本的类别已知。2.1线性判别函数和决策面线性判别函数是统计模式3由于决策域的分界面是用数学式子来描述的，如线性函数，或各种非线性函数等。因此确定分界面方程，这包括选择函数类型与确定最佳参数两个部分。一般说来选择函数类型是由设计者确定的，但其参数的确定则是通过一个学习过程来实现的，是一个迭代实现优化的过程。本章讲最简单的函数类型线性函数。由于决策域的分界面是用数学式子来描述的，如线性函数，或各种非4 假设抽取到的模式样本的边界是“整齐”而不是混杂的，而且以后遇到的待分类模式基本上不超过学习样本的分类范围，从而利用这些样本得出的分类边界是无误差的。因此这些模式类之间的分界面，可以利用线性判别函数来进行。对于n维空间中的c 个模式类别各给出一个由n个特征组成的单值函数，这叫做判别函数。在c类的情况下，我们共有c个判别函数，记为g1(x)，g2(x)，gc(x)，它们分别对应于模式类1，2，c。假设抽取到的模式样本的边界是“整齐”而不是混杂的，而5 作为判别函数，它应具有如下的性质：假如一个模式X属于第i类，则有：而如果这个模式在第i类和第j类得分界面上，则有：如果判别函数取线性判别函数，它是所有模式特征的线性组合。对于第i类模式，有如下形式：式中 是特征的系数，称为权，为阈值权。如果对第i类模式定义n维权向量为：则判别函数可写成更简洁的形式：作为判别函数，它应具有如下的性质：假如一个模式X属于第6讨论二类情况下的线性判别函数。两个线性判别函数如果X属于，可得：令则二类模式的线性分类器的决策法则决策法则是：如果，则决策，即把归到类去；如果，则决策，即把归到类去。线性分类器线性分类器是指两类决策域的界面方程是单个线性方程。讨论二类情况下的线性判别函数。线性分类器是指两类决策域的界面7是决策面方程，它是两类模式的分界，对于二维空间情况，它是一条直线；对于三维情况，它是一个平面；而对于高维空间的情况，则是一个超平面。构造一个二类模式的线性分类器，如下图所示：是决策面方程8在二类模式的情况下，决策面H把模式空间分成两个半空间，即对的决策域和对的决策域。因为当特征向量在中时，所以决策面的法向量的方向指向。我们称位于决策面H的正面，位于决策面H的反面。9为了说明向量W的意义，我们假设在决策平面上有两个特征向量X1与X2，则应有(*)其中(X1-X2)也是一个向量，(*)式表明向量W与该平面上任两点组成的向量(X1-X2)正交，因此W的方向就是决策面的法线方向。为了说明向量W的意义，我们假设在决策平面上有两个特征向量X110+=wwxxrp决策面H右图中，H是决策面，它的方程为，是权向量，也就是决策面的法线方向。是待识别的模式的特征向量。g(X)就是n维空间中任一点X到该决策面距离的代数度量，该决策平面将这两类样本按其到该面距离的正负号确定其类别。若把X表示成：式中Xp:是在H上的投影向量，r:是到H的垂直距离，：是w方向上的单位向量。wwxx+=wwxxrp决策面H右图中，H是决策面，它的方程为11结论：利用线性判别函数进行决策，就是用一个超平面把特征空间分割成两个决策区域，超平面方向由权向量W决定，它的位置由阈值权w0确定。将上式代入，可得：()+=0 xwxwgT(x)=+0wgwT+wwxrp)(+=0 xpwwT+wWTwr=w(x)gr=0如果，则原点在H的正面；如果，则原点在H的反面。对于图所示情况，。若，则判别函数有齐次形式:说明超平面H通过原点。（因为）若X为坐标系原点，则坐标原点到该决策面的距离为。结论：利用线性判别函数进行决策，就是用一个超平面把特征空间分12设计线性分类器，是指所用的判别函数、分界面方程的类型已选定为线性类型，因此主要的设计任务是确定线性方程的两个参数，一个是权向量W，另一个是阈值。为了使所设计的线性分类器在性能上要满足一定的要求，这种要求通过一种准则来体现，并且要表示成一种准则函数，以便能通过将准则函数值优化的方法确定W与。设计线性分类器，是指所用的判别函数、分界面方程的类型已选定为132.2感知准则函数感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。2.2感知准则函数感知准则函数是五十年代由Rosen14线性判别函数可改写为：于是线性判别函数就变成了(n+1)维空间的齐次线性函数。定义增广模式向量:定义广义权向量:对于二类模式问题，在这个(n+1)维空间的决策面H的方程就是：因为阈值为0，所以超平面H通过原点。这样，找寻决策面的问题就简化为求权向量的问题。线性判别函数15在线性可分条件下，广义权向量A合适的话应有：为了方便起见，如果我们令则合适的A能使所有的Y满足ATY0。（后面用Y表示Y）经过这样的规格化处理后，问题就转化为：求使每一个样本Y满足ATY0的权向量A的问题了。权向量A称为解权向量。线性可分是说该训练样本集中的两类样本可以用一个线性分界面正确无误的分开。在线性可分条件下，广义权向量A合适的话应有：为了方便起见，16这里 是由于使用权向量A而被误分类的样本集合。当一个样本被误分类时，就有，所以，可见，是解权向量的函数。仅当时，达到极小值，即。或者说，当对于某个向量，准则函数达到极小值的话，就是解权向量，这时没有样本被错分类。在几何上，感知准则函数正比于被错分样本到决策面的距离之和。为了求解线性不等式组ATY0，构造一个准则函数：感知准则函数：因为（）为了求解线性不等式组ATY0，构造一个准17有了准则函数，需要用最优化方法寻找达到极小值的解权向量A。可以采用梯度下降算法来求解。是一个正的比例因子，称为步长或增量。有了准则函数，需要用最优化方法寻找18梯度下降法的算法步骤：（1）先任意选择一个初始的权向量（2）把第K次的权向量加上被误分类的样本的和与某个常数 的乘积，就得到第（K+1）次的权向量。（3）理论上可以证明，只要二类样本是线性可分的，无论初值如何选取，经过有限次迭代，这个算法总可以收敛，即使得每一个样本满足ATY0。该算法的缺点是：每次迭代必须遍历全部样本，才能得到当前权向量 下的误分样本集 ，从而进一步纠正 的值。梯度下降法的算法步骤：该算法的缺点是：每次迭代必须遍历全部样19固定增量算法及其收敛性固定增量算法是解线性不等式组的一种最简单的方法。它可以由梯度下降法作如下两点改变得到：（1）把全部样本看作是一个序列，每当前一步迭代的权向量把某个样本错误分类时，就对这个权向量做一次修正，而不是等当前权向量对全部样本计算后再找出错分类样本集去进行修改。（2）考虑每次迭代时保持不变，这就是固定增量的情况，也就是说乘上一个固定的比例因子。固定增量算法及其收敛性固定增量算法是解线性不20二类情况下用固定增量法求解权向量的方法：设已知二类模式的样本集和，这些样本都已变成增广模式的形式，要求用固定增量算法决定一个超平面，使它能正确划分样本集。开始时，可以任意假定为域决策界面的那一边，也可以任意选择广义权向量的初始值。然后把训练集中的增广模式向量依次取出，计算的内积，权向量用如下规则调整：如果，而，则用代替；如果，而，则用代替；如果，而，则保持不变；如果，而，则保持不变。二类情况下用固定增量法求解权向量的方法：21属于的全部模式向量都用上述方法处理一遍，成为一次迭代。这个算法继续重新执行，直到某次迭代后中的成员都通过这个程序而权向量不再变化为止，这时称为程序收敛。如果在某一次迭代中权向量已经保持不变，则权向量即解权向量。所以在程序收敛后即无必要进一步执行迭代了。如果不是线性可分的，则程序不会收敛，而迭代将无限进行下去，所以在编制程序时应考虑或在一定时间限度内停止，或当权向量在一个不收敛区域内循环而停止。这个算法可以推广到下述更一般的情况：模式不一定是二值的；执行迭代时，增广模式向量集中成员的次序可任意选定；不要求中有相等数量的模式；初始权向量可以任意选择。属于的全部模式向量222.3 最小平方误差准则函数 最小平方误差准则函数是一个基于全体样本的准则函数，要求满足等式 ，其中 是一些任意指定的正常数。令 为一个 矩阵，它的各行 是向量 ，令 为一个列向量，则问题变为：对于给定的 和要求找到一个权向量 ，使得 多数情况下，只可能找到一个这样的解权向量 ，它使 与 之间的误差极小化。如果定义误差向量e为 则求 为最优的方法是使误差向量e的长度的平方极小。这就是使误差平方和准则函数 极小化。这就是矛盾方程组的最小二乘解（MSE解）。2.3最小平方误差准则函数最小平方误差准则23对准则函数求导并令其为零，得准则函数极小化的必要条件：于是将解的问题转化为解。这里是一个维方阵，且常为非奇异。如果它是非奇异的，可以得到的唯一解：此处矩阵称为的伪逆。如果为奇异阵，得到的解不唯一。MSE解依赖于向量b，b的不同选择可以给予解以不同的性质。当b任意给定时，MSE解在线性可分的情况下不会总是产生一个正确的分界面，但可以找到一个有用的判别函数。dn对准则函数求导并令其为零，得准则函数极小化的必要条件：dn24为避免上述缺点，可以采用梯度下降算法。梯度下降算法为：（1）首先任意制订初始权向量；（2）如第k步不能满足要求则按下式求第（k+1）步的权向量可以证明，如果，其中是任意常数，则这个算法产生的权向量序列，收敛于满足方程式。且不管是否为奇异矩阵，这个下降算法总能产生一个解。MSE方法的计算工作量很大，要求解维矩阵的逆，并证明是非奇异的。为避免上述缺点，可以采用梯度下降算法。MSE252.4 多类判别问题以上讨论的都是两类别问题，但是实际问题中常遇到的是多类别问题。可以把两类别问题中使用的线性判别函数方法推广到多类别问题中，但可有不同做法。2.4多类判别问题以上讨论的都是两类别问题，但是26一种最简单作法是将一种最简单作法是将C类别问题化类别问题化为为(C-1)个两类问题，即将第个两类问题，即将第i类与类与所有非所有非i类样本，按两类问题确定类样本，按两类问题确定其判别函数与决策面方程。因此其判别函数与决策面方程。因此对于对于C类，则总共有类，则总共有(C-1)个两类个两类别问题，如图所示。这种做法存别问题，如图所示。这种做法存在两个问题，一是可能会出现一在两个问题，一是可能会出现一些不定区域，如图中阴影所示，些不定区域，如图中阴影所示，在这些区域中的样本无法确定其在这些区域中的样本无法确定其类别。原因是用线性判别函数对类别。原因是用线性判别函数对i类及所有非类及所有非i类进行划分并不能保类进行划分并不能保证获得性能良好的划分，硬性使证获得性能良好的划分，硬性使用线性分类器可能会产生很不好用线性分类器可能会产生很不好的效果。的效果。W1非W1不定区域不定区域一种最简单作法是将C类别问题化为(C-1)个两类问题，即将第27另一种相对麻烦些的做法是另一种相对麻烦些的做法是将将C类中的每两类别单独设类中的每两类别单独设计其线性判别函数，因此总计其线性判别函数，因此总共有共有C(C-1)/2个线性判别函个线性判别函数。这种方法如图所示。这数。这种方法如图所示。这种方法由于每个判别函数针种方法由于每个判别函数针对每两类别样本设计，预期对每两类别样本设计，预期可有好效果，但仍有不定区可有好效果，但仍有不定区域，在该区域内样本类别无域，在该区域内样本类别无法确定。法确定。另一种相对麻烦些的做法是将C类中的每两类别单独设计其线性判别28由于样本在特征空间分布的复杂性，许多情况下采用由于样本在特征空间分布的复杂性，许多情况下采用线性判别函数不能取得满意的分类效果。也就是说，线性判别函数不能取得满意的分类效果。也就是说，在在n维模式样本集维模式样本集线性可分线性可分的情况下，如果的情况下，如果训练集足够训练集足够大，就可能得到较好的分类结果。所以它应用于简单大，就可能得到较好的分类结果。所以它应用于简单的线性可分集是一个很好的工具。对于比较复杂的问的线性可分集是一个很好的工具。对于比较复杂的问题，当样本不是线性可分时，用超平面分类，就会导题，当样本不是线性可分时，用超平面分类，就会导致较大的分类错误率。致较大的分类错误率。2.5 分段线性判别函数由于样本在特征空间分布的复杂性，许多情况下采用线性判别函数不29线性判别函数ppt课件30为了解决比较复杂的线性为了解决比较复杂的线性不可分样本分类问题，提出了不可分样本分类问题，提出了非线性判别函数。这个分界面非线性判别函数。这个分界面是一个超曲面。如图所示的分是一个超曲面。如图所示的分界面界面所示。但是非线性判别所示。但是非线性判别函数计算复杂，实际应用上受函数计算复杂，实际应用上受到较大的限制。解决问题的另到较大的限制。解决问题的另一个方法是采用多个线性分界一个方法是采用多个线性分界面，将它们分段连接，用分段面，将它们分段连接，用分段线性划分去逼近分界的超曲面。线性划分去逼近分界的超曲面。如图分界面如图分界面所示。他的决策所示。他的决策面由几个超平面段组成。它面由几个超平面段组成。它有可能利用已知的线性判别函数来解决分类问题，并较好地逼有可能利用已知的线性判别函数来解决分类问题，并较好地逼近分类的超曲面，从而减少分类误差。近分类的超曲面，从而减少分类误差。为了解决比较复杂的线性不可分样本分类问题，提31分段线性判别函数的算法很多，它的计算量较之非线性判分段线性判别函数的算法很多，它的计算量较之非线性判别函数大大减少。难点是如何舍弃这些超平面的无效部分而根别函数大大减少。难点是如何舍弃这些超平面的无效部分而根据任务正确地将有效区段相互连接的问题。据任务正确地将有效区段相互连接的问题。下面的分段线性划分下面的分段线性划分算法较易实现，它用全部算法较易实现，它用全部正确分类的超平面将空间正确分类的超平面将空间划分为若干区域，每个区划分为若干区域，每个区域都是凸的超多面体。在域都是凸的超多面体。在这些超多面体中的样本都这些超多面体中的样本都是属于同一类的。如果将是属于同一类的。如果将每个超平面分割的正面半每个超平面分割的正面半空间赋予空间赋予“1”，反面赋，反面赋予予“0”，则这些超多面，则这些超多面体可体可用所有的超平面的正反面用所有的超平面的正反面的编码来代表。这就达到的编码来代表。这就达到了用分段线性划分来分类的目的，见图。了用分段线性划分来分类的目的，见图。分段线性判别函数的算法很多，它的计算量较之非32由于分段线性划分的解可能由不同的样本分割方式形成，由于分段线性划分的解可能由不同的样本分割方式形成，一般情况下不是唯一的。但每个解都能满足要求。一般情况下不是唯一的。但每个解都能满足要求。分段线性划分也存在误差。处理分类误差可有二种方法：分段线性划分也存在误差。处理分类误差可有二种方法：（1）增加超平面数目增加超平面数目，达到满足当前样本正确分类的目的；，达到满足当前样本正确分类的目的；（2）适当限制超平面数目适当限制超平面数目，而允许一定的分类误差存在。，而允许一定的分类误差存在。因为问题是非参数的，我们除了分类好的样本外一无所知，因为问题是非参数的，我们除了分类好的样本外一无所知，所以在有限样本的情况下，我们仅能讨论是当前样本下误差最所以在有限样本的情况下，我们仅能讨论是当前样本下误差最小，这可以在多个可能解中用误分样本数最小或误差平方和最小，这可以在多个可能解中用误分样本数最小或误差平方和最小作为准则来达到。一般说来，当样本足够大时，分段线性分小作为准则来达到。一般说来，当样本足够大时，分段线性分界面是渐进于真实的超曲面分界的，因而这样的分界面是可行界面是渐进于真实的超曲面分界的，因而这样的分界面是可行的。而在小样本的情况下，很难说一个算法得到的结果是最优的。而在小样本的情况下，很难说一个算法得到的结果是最优的。的。由于分段线性划分的解可能由不同的样本分割方式33下面介绍两种二类线性判别函数推广得到的分段线性判别函数的算法。如图所示，先用二类线性判别函数找出一个分界面，它将样本大致分成两类。因为样本集不是线性可分的，所以两面的模式都会混杂。再对的正反面的模式样本分别应用线性判别函数求得和，如此继续下去，直至每个分界面都将样本正确分类为止。连接相应的各分界面，即得分段线性判别函数所决定的决策面。对这个方法可以采用遗传算法，它提供当前样本下的最优解。下面介绍两种二类线性判别函数推广得到的分段线34第二种方法是用一个超平面将空间划分为两个半空间，它的正面仅包含一类“纯”的样本；它的反面则允许两类样本混杂。下一步则是对反面的混杂样本再次使用一个超平面分割，其正面分离出一类纯样本，而反面允许二类样本混杂。继续进行程序直至样本被超平面完全划分为止。划分的过程中要求每次划分的正面得到的纯样本数最多。第二种方法是用一个超平面将空间划分为两个半空间35应用统计方法解决模式识别问题时，维数或特征个数是应用统计方法解决模式识别问题时，维数或特征个数是个非常重要的问题。在低维空间里解析上或计算上行得通个非常重要的问题。在低维空间里解析上或计算上行得通的方法，在高维空间里往往行不通。因此，降低维数有时的方法，在高维空间里往往行不通。因此，降低维数有时就成为处理实际问题的关键。就成为处理实际问题的关键。2.6 Fisher线性判别函数Fisher方法的基本思想是：把方法的基本思想是：把d维空间的所有模式投维空间的所有模式投影到一条过原点的直线上，就能把维数压缩到影到一条过原点的直线上，就能把维数压缩到1。关键在关键在于要找到这样一条最优的投影方向，使这些模式的投影于要找到这样一条最优的投影方向，使这些模式的投影能较好地区分开。能较好地区分开。应用统计方法解决模式识别问题时，维数或特征个数是个非36如图所示，表示了在一个二维空间两个类别样本在两个不同的如图所示，表示了在一个二维空间两个类别样本在两个不同的向量向量w1与与w2上投影分布的情况。其中用红点及蓝点分别表示上投影分布的情况。其中用红点及蓝点分别表示不同类别的样本。显然对不同类别的样本。显然对w1向量的投影能使这两类有明显可分向量的投影能使这两类有明显可分开的区域，而对向量开的区域，而对向量w2的投影，则使两类数据部分交迭在一起，的投影，则使两类数据部分交迭在一起，无法找到一个能将它们截然分开的界面。无法找到一个能将它们截然分开的界面。Fisher准则的基本原准则的基本原理，就是要找到一个最合适的投影轴，使两类样本在该轴上投理，就是要找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。影的交迭部分最少，从而使分类效果为最佳。如图所示，表示了在一个二维空间两个类别样本在两个不同的向量w37设给定两类模式样本集设给定两类模式样本集和和，它们各有，它们各有和和个个d维维样本。我们的目标就是找到这样一条直线，使得模式样样本。我们的目标就是找到这样一条直线，使得模式样本在这条直线上的投影最有利于分类。设本在这条直线上的投影最有利于分类。设为这条直线为这条直线正方向的单位向量，正方向的单位向量，。于是由。于是由和和对直线的投对直线的投影相应地得到集合影相应地得到集合和和。每个。每个就是就是在单位在单位向量向量上的投影。于是有：上的投影。于是有：为了找到最有利于分类的方向为了找到最有利于分类的方向，需要建立一个准则函，需要建立一个准则函数，它能反映不同类别模式在这条直线上投影分离程度数，它能反映不同类别模式在这条直线上投影分离程度的好坏。的好坏。设给定两类模式样本集和，它们各有和38为了使类别分离得好，应使各类模式投影均值彼此间相距尽可能大，为了使类别分离得好，应使各类模式投影均值彼此间相距尽可能大，还应使同类模式的投影比较密集。还应使同类模式的投影比较密集。设设是第是第类类d维样本的均值：维样本的均值：则这些样本在直线则这些样本在直线上的投影的均值就是：上的投影的均值就是：从而投影均值间的距离就是：从而投影均值间的距离就是：因为因为和和对于给定的两类样本集是不变的，所以改变对于给定的两类样本集是不变的，所以改变的方向，就可能改变投影均值间的距离。的方向，就可能改变投影均值间的距离。定义一类模式投影的类内离散度为：定义一类模式投影的类内离散度为：则总的类内离散度为：则总的类内离散度为：它代表整个样本集合中各类样本投影的密集程度。为了更好的分类结果，它代表整个样本集合中各类样本投影的密集程度。为了更好的分类结果，应选择直线应选择直线使得类内总离散度尽可能小。使得类内总离散度尽可能小。为了使类别分离得好，应使各类模式投影均值彼此39综合上述考虑，定义综合上述考虑，定义Fisher准则函数。我们希望投影后，准则函数。我们希望投影后，在一维在一维Y空间里各类样本尽可能分得开些，即希望两类空间里各类样本尽可能分得开些，即希望两类均值之差越大越好，同时希望各类样本内部尽量密集，均值之差越大越好，同时希望各类样本内部尽量密集，即类内离散度越小越好。因此可以定义即类内离散度越小越好。因此可以定义Fisher准则函数准则函数为：为：显然，应该寻找使显然，应该寻找使 的分子尽可能大，而分母尽的分子尽可能大，而分母尽可能小，也就是可能小，也就是 尽可能大的尽可能大的W作为投影方向。作为投影方向。J(W)J(W)综合上述考虑，定义Fisher准则函数。我们希望投影后，在一40构造构造Fisher判别函数判别函数它使准则函数它使准则函数达到极大。达到极大。为了把为了把表示成表示成的明显形式，作以下定义：的明显形式，作以下定义：（1）第）第类离散度矩阵类离散度矩阵（2）类内离散度矩阵）类内离散度矩阵（3）类间离散度矩阵）类间离散度矩阵可以得到可以得到构造Fisher判别函数41又又根据以上推导，准则函数根据以上推导，准则函数可改写为：可改写为：这就是这就是Rayleigh比。易证比。易证Rayleigh比的如下性质：比的如下性质：，a a是一个实数。是一个实数。的极值与的极值与的大小无关，只与的大小无关，只与的方向有关。的方向有关。用用Lagrange乘数法求极值（略）。乘数法求极值（略）。又42经过计算可以得到经过计算可以得到这就是使准则函数这就是使准则函数极大的解。极大的解。就是使模式样本的投就是使模式样本的投影在影在类间最分散，类内最集中类间最分散，类内最集中的最优解。有了的最优解。有了后，得后，得就可将各样本由就可将各样本由d维空间投影到一维空间，即直线维空间投影到一维空间，即直线上，变上，变成一维样本成一维样本，它们给出较好的分类结果。，它们给出较好的分类结果。需要注意的是，这样得到的结果是有一定局限的。它只是对准需要注意的是，这样得到的结果是有一定局限的。它只是对准则函数最优，即则函数最优，即最大，在许多情况下，结果并不完全理想。最大，在许多情况下，结果并不完全理想。另外，它没有利用样本分布的信息，虽然计算简单，但错误率另外，它没有利用样本分布的信息，虽然计算简单，但错误率达不到最小。达不到最小。经过计算可以得到需要注意的是，这样得到的结果是有一定局限的43支持向量机支持向量机(Support Vector Machine,简称简称SVM)是基于是基于统计学习理论的一种分类器设计方法，是近年来在理论及统计学习理论的一种分类器设计方法，是近年来在理论及实际问题中都有重大影响的一种新方法。实际问题中都有重大影响的一种新方法。在线性可分条件下，即两个类别训练样本集可用线性分在线性可分条件下，即两个类别训练样本集可用线性分界面无错误分开的条件下，找到使两类别训练样本正确分界面无错误分开的条件下，找到使两类别训练样本正确分类的一个最佳分界面。最佳条件是指两类样本最靠近分界类的一个最佳分界面。最佳条件是指两类样本最靠近分界面的样本（称为支持向量）到该分界面的法向距离最大。面的样本（称为支持向量）到该分界面的法向距离最大。也就是说使分界面两侧形成的一个隔离带（带中没有任一也就是说使分界面两侧形成的一个隔离带（带中没有任一类训练样本）的间隔最宽。类训练样本）的间隔最宽。2.7 支持向量机支持向量机(SupportVectorMachi44SVM的思路是这样的，由于两类别的思路是这样的，由于两类别训练样本线性可分，因此在两个类训练样本线性可分，因此在两个类别的样本集之间存在一个隔离带。别的样本集之间存在一个隔离带。对一个二维空间的问题，如右图表对一个二维空间的问题，如右图表示，其中用圈和交叉符号分别表示示，其中用圈和交叉符号分别表示第一类和第二类训练样本，第一类和第二类训练样本，H是将是将两类分开的分界面，而两类分开的分界面，而H1与与H2与与H平行，平行，H是其平分面，是其平分面，H1上的样上的样本是第一类样本到本是第一类样本到H最近距离的点，最近距离的点，H2的点则是第二类样本距的点则是第二类样本距H的最近的最近点，由于这两种样本点很特殊，处点，由于这两种样本点很特殊，处在隔离带的边缘上，因此用再附加在隔离带的边缘上，因此用再附加一个圈表示。这些点称为支持向量，一个圈表示。这些点称为支持向量，它们决定了这个隔离带。它们决定了这个隔离带。SVM的思路是这样的，由于两类别训练样本线性可分，因此在两个45从图上可以看出能把两类分开的分界面并不止从图上可以看出能把两类分开的分界面并不止H这一这一个，如果略改变个，如果略改变H的方向，则根据的方向，则根据H1、H2与与H平行平行这一条件，这一条件，H1、H2的方向也随之改变，这样一来，的方向也随之改变，这样一来，H1与与H2之间的间隔之间的间隔(两条平行线的垂直距离两条平行线的垂直距离)会发生会发生改变。显然使改变。显然使H1与与H2之间间隔最大的分界面之间间隔最大的分界面H是最是最合理的选择，因此最大间隔准则就是支持向量机的合理的选择，因此最大间隔准则就是支持向量机的最佳准则。最佳准则。从图上可以看出能把两类分开的分界面并不止H这一个，如果略改变46如图所示是两类线性可分集被超平面隔开的情况。显如图所示是两类线性可分集被超平面隔开的情况。显然，图然，图(b)比图比图(a)中两类样本分开的间隔要大，如果图中两类样本分开的间隔要大，如果图(b)中的中的H0是具有最大间隔的解平面，则称这个解平面是最优是具有最大间隔的解平面，则称这个解平面是最优的。的。如图所示是两类线性可分集被超平面隔开的情况。47支持向量机是线性判别函数的进一步发展，但它也支持向量机是线性判别函数的进一步发展，但它也是基于当前有限模式样本集得到的最优化方法。与线性是基于当前有限模式样本集得到的最优化方法。与线性判别函数相似，它的结果强烈依赖我们所掌握的模式样判别函数相似，它的结果强烈依赖我们所掌握的模式样本集的构造，当样本集容量不大时，这种依赖性尤其明本集的构造，当样本集容量不大时，这种依赖性尤其明显。此外，将分界面定在最大间隔的中间，对于许多情显。此外，将分界面定在最大间隔的中间，对于许多情况来说，也并不是最优的。况来说，也并不是最优的。48本章习题：本章习题：1、设五维空间的线性方程为设五维空间的线性方程为，试求出其权向量与样本向量点积的表达式试求出其权向量与样本向量点积的表达式中的中的W，X以及增广权向量与增广样本向量形式以及增广权向量与增广样本向量形式ATY中的中的A与Y。2、上式是一个五维空间的超平面，试求该平面到坐标原、上式是一个五维空间的超平面，试求该平面到坐标原点的法向距离。点的法向距离。本章习题：1、设五维空间的线性方程为49第1题答：第2题答：该式的权向量的模为：而超平面到坐标原点的距离为第1题答：50