线性判别函数

第2章线性判别函数2.1线性判别函数和决策面2.2感知准则函数2.3最小平方误差准则函数2.4多类判别问题2.5分段线性判别函数2.6Fisher线性判别函数2.7支持向量机课前思考题：(1)机器能否像人类一样通过例证教育认知事物，修正观念中的错误的成分?(2)机器学习过程中有教师吗？谁是教师？(3)什么叫线性分类器?什么条件下才能用线性分类器？2.1线性判别函数和决策面线性判别函数是统计模式识别方法中的一个重要的基本方法。它是由训练样本集提供的信息直接确定决策域的划分。在训练过程中使用的样本集，该样本集中的每个样本的类别已知。由于决策域的分界面是用数学式子来描述的，如线性函数，或各种非线性函数等。因此确定分界面方程，这包括选择函数类型与确定最佳参数两个部分。一般说来选择函数类型是由设计者确定的，但其参数的确定则是通过一个学习过程来实现的，是一个迭代实现优化的过程。本章讲最简单的函数类型—线性函数。假设抽取到的模式样本的边界是“整齐”而不是混杂的，而且以后遇到的待分类模式基本上不超过学习样本的分类范围，从而利用这些样本得出的分类边界是无误差的。因此这些模式类之间的分界面，可以利用线性判别函数来进行。对于n维空间中的c个模式类别各给出一个由n个特征组成的单值函数，这叫做判别函数。在c类的情况下，我们共有c个判别函数，记为g1(x)，g2(x)，…gc(x)，它们分别对应于模式类1，2，…c。作为判别函数，它应具有如下的性质：假如一个模式X属于第i类，则有：而如果这个模式在第i类和第j类得分界面上，则有：如果判别函数取线性判别函数，它是所有模式特征的线性组合。对于第i类模式，有如下形式：式中是特征的系数，称为权，为阈值权。如果对第i类模式定义n维权向量为：则判别函数可写成更简洁的形式：()(),ijggXX,1,2,,,ijcji()()ijggXX01()niikkikgwxwXikw0iw12()TiiiinW0(),TiiigwXWX1,2,,ic讨论二类情况下的线性判别函数。两个线性判别函数如果X属于，可得：令则二类模式的线性分类器的决策法则是：如果，则决策，即把归到类去；如果，则决策，即把归到类去。1121020()()0TTwwWWX1201020(),TTT得()=XWX+0g()X0g()XXX11221011)(wXWXgT2022)(wXWXgT线性分类器是指两类决策域的界面方程是单个线性方程。是决策面方程，它是两类模式的分界，对于二维空间情况，它是一条直线；对于三维情况，它是一个平面；而对于高维空间的情况，则是一个超平面。0g()=X构造一个二类模式的线性分类器，如下图所示：在二类模式的情况下，决策面H把模式空间分成两个半空间，即对的决策域和对的决策域。因为当特征向量在中时，所以决策面的法向量的方向指向。我们称位于决策面H的正面，位于决策面H的反面。11R22R0g()XX1R1R1R2R为了说明向量W的意义，我们假设在决策平面上有两个特征向量X1与X2，则应有(*)其中(X1-X2)也是一个向量，(*)式表明向量W与该平面上任两点组成的向量(X1-X2)正交，因此W的方向就是决策面的法线方向。1xw2x1x0xg平面xwxgww0wpx0:1g0:2g1x2xwwxxrp决策面H@右图中，H是决策面，它的方程为，是权向量，也就是决策面的法线方向。是待识别的模式的特征向量。0g()=XWXg(X)就是n维空间中任一点X到该决策面距离的代数度量，该决策平面将这两类样本按其到该面距离的正负号确定其类别。若把X表示成：式中Xp:是在H上的投影向量，r:是到H的垂直距离，：是w方向上的单位向量。wwxx0g()=X结论：利用线性判别函数进行决策，就是用一个超平面把特征空间分割成两个决策区域，超平面方向由权向量W决定，它的位置由阈值权w0确定。将上式代入，可得：0xwxwgT(x)=0wgwTwwxrp)(0xpwwTwWTwrwrw(x)gr=0如果，则原点在H的正面；如果，则原点在H的反面。对于图所示情况，。若，则判别函数有齐次形式:说明超平面H通过原点。0000=0000()TgXXW（因为）若X为坐标系原点，则0)(wXg0(0)gw坐标原点到该决策面的距离为。0wW设计线性分类器，是指所用的判别函数、分界面方程的类型已选定为线性类型，因此主要的设计任务是确定线性方程的两个参数，一个是权向量W，另一个是阈值。为了使所设计的线性分类器在性能上要满足一定的要求，这种要求通过一种准则来体现，并且要表示成一种准则函数，以便能通过将准则函数值优化的方法确定W与。0w0w2.2感知准则函数感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。121(1)TnxxxYX012()TiiiiinA()TiigYAY0TAY0(())TiiigwXWX线性判别函数可改写为：()igY于是线性判别函数就变成了(n+1)维空间的齐次线性函数。定义增广模式向量:定义广义权向量:对于二类模式问题，在这个(n+1)维空间的决策面H的方程就是：A因为阈值为0，所以超平面H通过原点。这样，找寻决策面的问题就简化为求权向量的问题。在线性可分条件下，广义权向量A合适的话应有：为了方便起见，如果我们令则合适的A能使所有的Y’满足ATY’0。（后面用Y表示Y’）经过这样的规格化处理后，问题就转化为：求使每一个样本Y满足ATY0的权向量A的问题了。权向量A称为解权向量。线性可分是说该训练样本集中的两类样本可以用一个线性分界面正确无误的分开。12,0,0TTYYYY如果则A如果则A这里是由于使用权向量A而被误分类的样本集合。当一个样本被误分类时，就有，所以，可见，是解权向量的函数。仅当时，达到极小值，即。或者说，当对于某个向量，准则函数达到极小值的话，就是解权向量，这时没有样本被错分类。在几何上，感知准则函数正比于被错分样本到决策面的距离之和。AYTAY0()PJA()PJA()PJA()0PJAAAAA()0PJA为了求解线性不等式组ATY0，构造一个准则函数：()()TPAYJAAY感知准则函数：()TgYAY0()TgwXWX因为（）有了准则函数，需要用最优化方法寻找达到极小值的解权向量A。可以采用梯度下降算法来求解。()PJA()PJA1kkkkAYAAY1()kkkpJAAA()()kPPYAAYJAJAk是一个正的比例因子，称为步长或增量。梯度下降法的算法步骤：（1）先任意选择一个初始的权向量（2）把第K次的权向量加上被误分类的样本的和与某个常数的乘积，就得到第（K+1）次的权向量。（3）理论上可以证明，只要二类样本是线性可分的，无论初值如何选取，经过有限次迭代，这个算法总可以收敛，即使得每一个样本满足ATY0。1Ak1kkkkAYAAY该算法的缺点是：每次迭代必须遍历全部样本，才能得到当前权向量下的误分样本集，从而进一步纠正的值。kAkAkA固定增量算法及其收敛性固定增量算法是解线性不等式组的一种最简单的方法。它可以由梯度下降法作如下两点改变得到：（1）把全部样本看作是一个序列，每当前一步迭代的权向量把某个样本错误分类时，就对这个权向量做一次修正，而不是等当前权向量对全部样本计算后再找出错分类样本集去进行修改。（2）考虑每次迭代时保持不变，这就是固定增量的情况，也就是说乘上一个固定的比例因子。kAkAk二类情况下用固定增量法求解权向量的方法：设已知二类模式的样本集和，这些样本都已变成增广模式的形式，要求用固定增量算法决定一个超平面，使它能正确划分样本集。开始时，可以任意假定为域决策界面的那一边，也可以任意选择广义权向量的初始值。然后把训练集中的增广模式向量依次取出，计算的内积，权向量用如下规则调整：①如果，而，则用代替；②如果，而，则用代替；③如果，而，则保持不变；④如果，而，则保持不变。*1R*2RTAY0**12和RR**12和RRA1A**12和RRY与AYTAYA*1YRTAY0+AYA*1YR*2YR*2YRTAY0AA-AYTAY0TAY0AA属于的全部模式向量都用上述方法处理一遍，成为一次迭代。这个算法继续重新执行，直到某次迭代后中的成员都通过这个程序而权向量不再变化为止，这时称为程序收敛。如果在某一次迭代中权向量已经保持不变，则权向量即解权向量。所以在程序收敛后即无必要进一步执行迭代了。如果不是线性可分的，则程序不会收敛，而迭代将无限进行下去，所以在编制程序时应考虑或在一定时间限度内停止，或当权向量在一个不收敛区域内循环而停止。这个算法可以推广到下述更一般的情况：①模式不一定是二值的；②执行迭代时，增广模式向量集中成员的次序可任意选定；③不要求中有相等数量的模式；④初始权向量可以任意选择。**12和RR**12和RRAAAˆA**12和RR**12，RR**12和RR2.3最小平方误差准则函数最小平方误差准则函数是一个基于全体样本的准则函数，要求满足等式，，其中是一些任意指定的正常数。令为一个矩阵，它的各行是向量，令为一个列向量，则问题变为：对于给定的和要求找到一个权向量，使得多数情况下，只可能找到一个这样的解权向量，它使与之间的误差极小化。如果定义误差向量e为则求为最优的方法是使误差向量e的长度的平方极小。这就是使误差平方和准则函数极小化。这就是矛盾方程组的最小二乘解（MSE解）。TiibAY1,,inibYndiiY12()TnbbbbYbAYAbAYAbeYAbA221()nTsiiiJYAbAYb对准则函数求导并令其为零，得准则函数极小化的必要条件：于是将解的问题转化为解。这里是一个维方阵，且常为非奇异。如果它是非奇异的，可以得到的唯一解：此处矩阵称为的伪逆。如果为奇异阵，得到的解不唯一。MSE解依赖于向量b，b的不同选择可以给予解以不同的性质。当b任意给定时，MSE解在线性可分的情况下不会总是产生一个正确的分界面，但可以找到一个有用的判别函数。TTYYAYbYAbTTYYAYbTYYddA1()TTAYYYbYbdn()TTYYYYYTYY0)(2)(2)(_1bAYYYbYAAJTiniiisT为避免上述缺点，可以采用梯度下降算法。梯度下降算法为：（1）首先任意制订初始权向量；（2）如第k步不能满足要求则按下式求第（k+1）步的权向量可以证明，如果，其中是任意常数，则这个算法产生的权向量序列，收敛于满足方程式。且不管是否为奇异矩阵，这个下降算法总能产生一个解。1A()=0TYYAb1kA1()TkkkkAAYYAb1/kk1kA1,2,,k()0sJATYYMSE方法的计算工作量很大，要求解维矩阵的逆，并证明是非奇异的。ddTYY2.4多类判别问题以上讨论的都是两类别问题，但是实际问题中常遇到的是多类别问题。可以把两类别问题中使用的线性判别函数方法推广到多类别问题中，但可有不同做法。一种最简单作法是将C类别问题化为(C-1)个两类问题，即将第i类与所有非i类样本，按两类问题确定其判别函数与决策面方程。因此对于C类，则总共有(C-1)个两类别问题，如图所示。这种做法存在两个问题，一是可能会出现一些不定区域，如图中阴影所示，在这些区域中的样本无法确定其类别。原因是用线性判别函数对i类及所有非i类进行划分并不能保证获得性能良好的划分，硬性使用线性分类器可能会产生很不好的效果。W1非W1不定区域另一种相对麻烦些