模式识别课程第4章.pdf

《模式识别课程第4章.pdf》由会员分享，可在线阅读，更多相关《模式识别课程第4章.pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 线性判别函数2010.11第四章 线性判别函数4.1引言4.2 Fisher线性判别4.3 感知准则函数4.4 最小错分样本数准则4.5 最小平方误差准则函数4.6 随机最小错误率线性判别准则函数4.7 多类问题引言?设计贝叶斯分类器的方法：即已知先验概率P(i)和类条件概率密度p(x/i)的情况下，按一定的决策规则确定判别函数和决策面。?类条件概率密度的形式常常难以确定，利用非参数估计分布需要大量样本，且所需样本数随维数升高急剧增加。?线性判别函数法线性判别函数?我们现在对两类问题和多类问题分别进行讨论。?(一)两类问题即:?1.二维情况：取两个特征向量?这种情况下 判别函数:2,)

2、,(21=MTi2,)(2,1=nxxXT32211wxwxw)x(g+=为坐标向量为参数，21,xxw?在两类别情况，判别函数 g(x)具有以下性质：?这是二维情况下判别由判别边界分类.?情况如图：?1.二维情况=21,0,0)(XXxgi不定Xxg,0)(=32211)(wxwxwxg+=211x2x+?2.n维情况?现抽取n个特征为：?判别函数：?另外一种表示方法：TnxxxxX),.,(321=12211.)(+=nnnwxwxwxwxg10+=nTwXW12112(,.,)(,.,1)TnnTnWw ww wXx xx+=为增值权向量，为增值模式向量。XWxgT=)(为模式向量。为权

3、向量，TnTnxxxXwwwW),.,(),.,(21210=?模式分类：?当 g1(x)=WTX=0 为判别边界。当n=2时，二维情况的判别边界为一直线。当n=3时，判别边界为一平面，n3时，则判别边界为一超平面。=21,0,0)(xxXWxgT?2.n维情况?(二)多类问题0,()0,1,2,.,iTiiXg xW XiC=0而g2(x)0，g3(x)0)(0)(0)(321xgxgxg120)(0)(0)(321xgxgxg0)(0)(0)(321xgxgxg+4IR3IR1IR2IR1x2x0)(1=xg0)(2=xg0)(3=xg551?对于任一模式X如果它的 g1(x)0，g2(x

4、)0，g3(x)0)(0)(0)(321xgxgxg12000321)x(g)x(g)x(g0)(0)(0)(321xgxgxg+4IR3IR1IR2IR1x2x0)(1=xg0)(2=xg0)(3=xg551?必须指出，如果某个X使二个以上的判别函数 gi(x)0。则此模式X就无法作出确切的判决。如图中IR1,IR3，IR4区域。?另一种情况是IR2区域，判别函数都为负值。IR1，IR2，IR3，IR4。都为不确 定区域。?1。第一种情况（续）1。第一种情况（续）30)(0)(0)(321xgxgxg12000321)x(g)x(g)x(g0)(0)(0)(321xgxgxg+4IR3IR1

5、IR2IR1x2x0)(1=xg0)(2=xg0)(3=xg551?问当x=(x1,x2)T=(6,5)T时属于那一类?结论：g1(x)0，g3(x)0所以它属于2类:代入判别函数方程组+=+=+=1)(5)()(23212211xxgxxxgxxxg.4)(,6)(,1)(321=xgxgxg得：?1。第一种情况（续）第一种情况（续）?这样 有 M(M _ 1)/2个判别平面。?对于两类问题，M=2，则有一个判别平面。?同理，三类问题则有三个判别平面。?判别函数：?判别边界：?判别条件：jixgijjix0 x0)(当当?2。第二种情况：第二种情况：XW)x(gTijij=o)x(gij=?

6、每个模式类和其它模式类间可分别用判别平面分开。每个模式类和其它模式类间可分别用判别平面分开。20)(12=xg0)(23=xg0)(13=xg+3+1=+=+=+=0)(03)(05)(21231132112xxxgxxgxxxg+=+=+=21231132112)(3)(5)(xxxgxxgxxxg?判别函数性质：?假设判别函数为：?判别边界为：?2。第二种情况（续）第二种情况（续）?用方程式作图：)()(xgxgjiij=0,023212gg判别区012=)x(g+023=)x(g013=)x(g+5531x0032313gg判别区0013121gg判别区2x?问:未知模式X=(x1,x2

7、)T=(4,3)T属于那一类?代入判别函数可得:?把下标对换可得:?因为?结论：所以X 属于3类?结论：判别区间增大，不确定区间减小，比第一种情况小的多.1)(,1)(,2)(231312=xgxgxg1)(,1)(,2)(323121=xgxgxg0)(3xgj?2。第二种情况（续）第二种情况（续）0023122gg判别区0012121gg判别区0)(12=xg+0)(23=xg0)(13=xg+5530032313gg判别区1x2x?3。第三种情况?判别函数：?判别规则：?判别边界：gi(x)=gj(x)或gi(x)-gj(x)=0?就是说，要判别模式X属于那一类，先把X代入M个判别函数中

8、，判别函数最大的那个类别就是X所属类别。类与 类之间的边界可由gi(x)=gj(x)或gi(x)-gj(x)=0来确定。XWxgTkk=)(Mk,.,2,1=小，其它最大，当iTkixXWxg)(?每类都有一个判别函数每类都有一个判别函数每类都有一个判别函数每类都有一个判别函数,存在存在存在存在M M M M个判别函数个判别函数个判别函数个判别函数?右图所示是M=3 的例子。对于1类模式，?必然满足g1(x)g2(x)和 g1(x)g3(x)。?假设判别函数为：?则判别边界为：=+=+=23212211)(1)()(xxgxxxgxxxg=+=+=+=012)()(02)()(012)()(2

9、1322131121xxxgxgxxxgxgxxgxg2)()(21xgxg=)()(32xgxg=)()(31xgxg=13?3。第三种情况（续）?结论：不确定区间没有了，所以这种是最好情况。?用上列方程组作图如下：?3。第三种情况（续）1)()()()(3121xgxgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32=xgxg+0)()(21=xgxg0)()(31=xgxg0.15.05.0?问假设未知模式x=(x1,x2)T=(1,1)T，则x属于那一类。?把它代入判别函数：?得判别函数为：?因为?所以模式x=(1,1)T属于类

10、。?3。第三种情况（续）2)()(),()(1232xgxgxgxg1)(,1)(,0)(321=xgxgxg).(),(),(321xgxgxg1)()()()(3121xgxgxgxg2)()()()(3212xgxgxgxg)()()()(1323xgxgxgxg30)()(32=xgxg+0)()(21=xgxg0)()(31=xgxg0.15.05.0?广义线性判别函数kixfwwxfwxfwxfwxgkiiikkk,.,2,1,)()(.)()()(1112211=+=+=+?这样一个非线性判别函数通过映射，变换成线性判别函数。1)(,)(1=+xfxfki是单值函数式中?判别函数

11、的一般形式：=+=2111,0,0)()()(xxYgYWxfwxgTyxkiii空间变换空间0=YWT判别平面：11121122110,()()()0,()(),(),().()kxyTiiikkxg xw f xW Yg Yxwf xwfxWYwfx+=+=空间变换空间其中：广义权向量。增广模式向量?广义线性判别函数（续）21,xaxbxbxorax则则?例：如右图。0bax二次判别函数212=+=2321212123211,0,0)()(,0,0)(xxYaaaWxxYgYWxgxxxaxaaxgT映射：?广义线性判别函数（续）?要用二次判别函数才可把二类分开：)1,1,1()25.0,

12、5.0,1(),0,0,1(321=yyy05.011y3y2yW平面oYWT=212x015.012)(1,2112,1,12123212321321=+=YWYxxxxxgyyyxxYaaaWaaaxT空间判别平面：即：空间它的判别边界：设讨论在推出?广义线性判别函数（续）?从图可以看出：在阴影上面是1类，在阴影下面是2类，?结论：在X空间的非线性判别函数通过变换到Y空间成为线性的，但X变为高维空间05.011y3y2yW平面oYWT=212x?Fisher线性判别?出发点 应用统计方法解决模式识别问题时，一再碰到的问题之一就是维数问题。在低维空间里解析上或计算上行得通的方法，在高维空间里

13、往往行不通。因此，降低维数有时就会成为处理实际问题的关键。?Fisher线性判别?问题描述 考虑把d维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维。然而，即使样本在d维空间里形成若干紧凑的互相分得开的集群，当把它们投影到一条直线上时，也可能会是几类样本混在一起而变得无法识别。但是，在一般情况下，总可以找到某个方向，使在这个方向的直线上，样本的投影能分得开。?Fisher线性判别?问题描述 问题：如何根据实际情况找到一条最好的、最易于分类的投影线，这就是Fisher判别方法所要解决的基本问题。?Fisher线性判别?从d维空间到一维空间的一般数学变换方法 假设有一集合包含N个d维

14、样本x1,x2,xN，其中N1个属于1类的样本记为子集1，N2个属于2类的样本记为子集2。若对xn的分量做线性组合可得标量：yn=wTxn,n=1,2,N 这样便得到N个一维样本yn组成的集合，并可分为两个子集1和2。?Fisher线性判别?从d维空间到一维空间的一般数学变换方法 实际上，w的值是无关紧要的，它仅是yn乘上一个比例因子，重要的是选择w的方向。w的方向不同，将使样本投影后的可分离程度不同，从而直接影响的分类效果。因此，上述寻找最佳投影方向的问题，在数学上就是寻找最好的变换向量w*的问题。?Fisher 准则函数中的基本参量 1.在 d 维 X 空间（1）各类样本的均值向量 mi

15、2,1i,xN1mixii=（2）样本类内离散度矩阵 Si和总样本类内离散度矩阵 Sw 21wxTiiiSSS2,1i,)mx)(mx(Si+=其中 Sw是对称半正定矩阵，而且当 Nd 时通常是非奇异的。（3）样本类间离散度矩阵 Sb T2121b)mm)(mm(S=Sb是对称半正定矩阵。?Fisher线性判别2.在一维 Y 空间（1）各类样本的均值im 2,1i,yN1miyii=（2）样本类内离散度2iS和总样本类内离散度wS 2221wy2i2iSSS2,1i,)my(Si+=?Fisher线性判别我们希望投影后，在一维我们希望投影后，在一维Y空间中各类样本尽可能分得开些，即希望两类均值

16、之差越大越好，同时希望各类样本内部尽量密集，即希望类内离散度越小越好。空间中各类样本尽可能分得开些，即希望两类均值之差越大越好，同时希望各类样本内部尽量密集，即希望类内离散度越小越好。?Fisher线性判别?Fisher 准则函数 准则函数 Fisher 准则函数定义为：准则函数定义为：2221221FSS)mm()w(J+=其中，其中，)mm(21是两类均值之差，是两类均值之差，2iS是样本类内离散度。显然，应该使是样本类内离散度。显然，应该使JF(w)的分子尽可能大而分母尽可能小，即应寻找使的分子尽可能大而分母尽可能小，即应寻找使 JF(w)尽可能大的尽可能大的 w作为投影方向。作为投影方

17、向。但上式中并不显含但上式中并不显含 w，因此须设法将，因此须设法将 JF(w)变成变成 w 的显函数。的显函数。由各类样本的均值可推出：由各类样本的均值可推出：iTxxiTTiyiimwxN1wxwN1yN1miii=这样，这样，Fisher 准则函数准则函数 JF(w)的分子可写成：的分子可写成：wSww)mm)(mm(w)wmwm)(mwmw()mwmw)(mwmw()mwmw()mm(bTT2121TT2T12T1TT2T1T2T1T22T1T221=现在再来考察 现在再来考察 JF(w)的分母与 w 的关系：的分母与 w 的关系：wSww)mx)(mx(w)mwxw()my(SiTx

18、TiiTx2iTTy2i2iiii=因此，因此，wSww)SS(wSSwT21T2221=+=+将上述各式代入将上述各式代入 JF(w)，可得：，可得：wSwwSw)w(JwTbTF=其中其中 Sb为样本类间离散度矩阵，为样本类间离散度矩阵，Sw为总样本类内离散度矩阵。为总样本类内离散度矩阵。?最佳变换向量 w*的求取 为求使wSw/wSw)w(JwTbTF=取极大值时的 w*，可以采用 Lagrange 乘数法求解。令分母等于非零常数，即：0cwSwwT=定义 Lagrange 函数为：)cwSw(wSw),w(LwTbT=其中为 Lagrange 乘子。将上式对 w 求偏导数，可得：wSw

19、Sw),w(Lwb=令偏导数为零，有；0*wS*wSwb=即*wS*wSwb=其中 w*就是 JF(w)的极值解。因为 Sw非奇异，将上式两边左乘1wS，可得：*w*wSSb1w=上式为求一般矩阵b1wSS的特征值问题。利用T2121b)mm)(mm(S=的定义，将上式左边的*wSb写成：R)mm(*w)mm)(mm(*wS21T2121b=其中*w)mm(RT21=为一标量，所以*wSb总是在向量)mm(21的方向上。因此w*可写成：R)mm(S*)wS(S*w211wb1w=从而可得：)mm(SR*w211w=由于我们的目的是寻找最佳的投影方向，w*的比例因子对此并无影响，因此可忽略比例因

20、子 R/,有：)mm(S*w211w=?Fisher线性判别?基于最佳变换向量基于最佳变换向量w*的投影的投影 w*是使是使Fisher准则函数准则函数JF(w)取极大值时的解，也就是取极大值时的解，也就是d维维X空间到一维空间到一维Y空间的最佳投影方向。有了空间的最佳投影方向。有了w*，就可以把，就可以把d维样本维样本x投影到一维，这实际上是多维空间到一维空间的一种映射，这个一维空间的方向投影到一维，这实际上是多维空间到一维空间的一种映射，这个一维空间的方向w*相对于相对于Fisher准则函数准则函数JF(w)是最好的。是最好的。利用利用Fisher准则，就可以将准则，就可以将d维分类问题转

21、化为一维分类问题，然后，只要确定一个阈值维分类问题转化为一维分类问题，然后，只要确定一个阈值T，将投影点，将投影点yn与与T相比较，即可进行分类判别相比较，即可进行分类判别.4.3 感知准则函数?几个基本概念 线性可分线性可分 样本的规范化样本的规范化 解向量和解区解向量和解区 对解区的限制对解区的限制?感知器算法?出发点出发点 一旦判别函数的形式确定下来，不管它是线性的还是非线性的，剩下的问题就是如何确定它的系数。一旦判别函数的形式确定下来，不管它是线性的还是非线性的，剩下的问题就是如何确定它的系数。在模式识别中，系数确定的一个主要方法就是通过对已知样本的训练和学习来得到。在模式识别中，系数

22、确定的一个主要方法就是通过对已知样本的训练和学习来得到。感知器算法就是通过训练样本模式的迭代和学习，产生线性（或广义线性）可分的模式判别函数。感知器算法就是通过训练样本模式的迭代和学习，产生线性（或广义线性）可分的模式判别函数。?感知器算法感知器算法?基本思想基本思想 采用感知器算法采用感知器算法(Perception Approach)能通过对训练模式样本集的能通过对训练模式样本集的“学习学习”得到判别函数的系数得到判别函数的系数?说明说明 这里采用的算法不需要对各类别中模式的统计性质做任何假设，因此称为确定性的方法。这里采用的算法不需要对各类别中模式的统计性质做任何假设，因此称为确定性的方

23、法。?感知器算法?感知器的训练算法感知器的训练算法 已知两个训练模式集分别属于已知两个训练模式集分别属于1类和类和2类，权向量的初始值为类，权向量的初始值为 w(1)，可任意取值。，可任意取值。若若0 x)k(w,xkT1k；若若0 x)k(w,xkT2k，则在用全部训练模式集进行迭代训练时，第则在用全部训练模式集进行迭代训练时，第 k 次的训练步骤如下：次的训练步骤如下：1）若）若1kx且且0 x)k(wkT，则分类器对第，则分类器对第 k 个模式个模式 xk做了错误分类，此时应校正权向量，使得做了错误分类，此时应校正权向量，使得 w(k+1)=w(k)+Cxk，其中，其中 C 为一个校正增

24、量。为一个校正增量。2）若）若2kx且且0 x)k(wkT，同样分类器分类错误，则权向量应校正如下：，同样分类器分类错误，则权向量应校正如下：w(k+1)=w(k)-Cxk 3）若以上情况不符合，则表明该模式样本在第若以上情况不符合，则表明该模式样本在第 k 次中分类正确，因此权向量不变，即：次中分类正确，因此权向量不变，即：w(k+1)=w(k)若对若对2x的模式样本乘以的模式样本乘以(-1)，则有：，则有：0 x)k(wkT时，时，w(k+1)=w(k)+Cxk 此时，感知器算法可统一写成：此时，感知器算法可统一写成：+=+0 x)k(wifCx)k(w0 x)k(wif)k(w)1k(w

25、kTkkT?感知器算法?感知器算法实质上是一种赏罚过程感知器算法实质上是一种赏罚过程 对正确分类的模式则对正确分类的模式则“赏赏”，实际上是，实际上是“不罚不罚”，即权向量不变。，即权向量不变。对错误分类的模式则对错误分类的模式则“罚罚”，使，使w(k)加上一个正比于加上一个正比于Xk的分量。的分量。当用全部模式样本训练过一轮以后，只要有一个模式是判别错误的，则需要进行下一轮迭代，即用全部模式样本再训练一次。当用全部模式样本训练过一轮以后，只要有一个模式是判别错误的，则需要进行下一轮迭代，即用全部模式样本再训练一次。如此不断反复直到全部模式样本进行训练都能得到正确的分类结果为止。如此不断反复直

26、到全部模式样本进行训练都能得到正确的分类结果为止。?感知器算法?感知器算法的收敛性感知器算法的收敛性只要模式类别是线性可分的，就可以在有限的迭代步数里求出权向量。只要模式类别是线性可分的，就可以在有限的迭代步数里求出权向量。采用感知器算法的多类模式的分类?讨论讨论 这里的分类算法都是通过模式样本来确定判别函数的系数，但一个分类器的判断性能最终要受并未用于训练的那些未知样本来检验。这里的分类算法都是通过模式样本来确定判别函数的系数，但一个分类器的判断性能最终要受并未用于训练的那些未知样本来检验。要使一个分类器设计完善，必须采用有代表性的训练数据，它能够合理反映模式数据的整体。要使一个分类器设计完

27、善，必须采用有代表性的训练数据，它能够合理反映模式数据的整体。采用感知器算法的多类模式的分类?讨论讨论 要获得一个判别性能好的线性分类器，究竟需要多少训练样本？要获得一个判别性能好的线性分类器，究竟需要多少训练样本？直观上是越多越好，但实际上能收集到的样本数目会受到客观条件的限制；直观上是越多越好，但实际上能收集到的样本数目会受到客观条件的限制；过多的训练样本在训练阶段会使计算机需要较长的运算时间；过多的训练样本在训练阶段会使计算机需要较长的运算时间；一般来说，合适的样本数目可如下估计：若一般来说，合适的样本数目可如下估计：若k是模式的维数，令是模式的维数，令C=2(k+1)，则通常选用的训练

28、样本数目约为，则通常选用的训练样本数目约为C的的1020倍。倍。?梯度下降算法定义定义 设函数设函数 f(y)是向量是向量 y=(y1,y2,yn)T的函数，则的函数，则f(y)的梯度定义为：的梯度定义为：Tn21yfyfyf)y(fdyd)y(f=?从从 w(k)导出导出 w(k+1)的一般关系式的一般关系式JC)k(ww)x,w(JC)k(w)1k(w)k(ww=+=C 是一个正的比例因子（步长）是一个正的比例因子（步长）?梯度下降算法?梯度是一个向量，它的最重要性质就是指出了函数梯度是一个向量，它的最重要性质就是指出了函数f在其自变量在其自变量y增加时最大增长率的方向。增加时最大增长率的

29、方向。?负梯度指出负梯度指出f的最陡下降方向的最陡下降方向?利用这个性质，可以设计一个迭代方案来寻找函数的最小值利用这个性质，可以设计一个迭代方案来寻找函数的最小值?采用梯度下降算法求解的基本思想对感知器算法式中的采用梯度下降算法求解的基本思想对感知器算法式中的w(k)、Xk随迭代次数随迭代次数k而变，是变量。而变，是变量。1）定义一个对错误分类敏感的准则函数）定义一个对错误分类敏感的准则函数J(w,x)。先任选一个初始权向量。先任选一个初始权向量w(1)，计算准则函数，计算准则函数J的梯度，然后从的梯度，然后从w(1)出发，在最陡方向（梯度方向）上移动某一距离得到下一个权向量出发，在最陡方向

30、（梯度方向）上移动某一距离得到下一个权向量w(2)。?梯度下降算法?梯度下降算法 2）从从 w(k)导出导出 w(k+1)的一般关系式的一般关系式 设取准则函数为：设取准则函数为：2xw|xw|)x,w(JTT=则则 J 对对 w 的微分式：的微分式：x)xw(signx21wJT=定义：定义：+=0 xwif10 xwif1)xw(signTTT 则由梯度法中则由梯度法中 w(k+1)和和 w(k)的关系有：的关系有：)x)k(w(signxx2C)k(w)1k(wkTkk+=+其中其中 xk是训练模式样本，是训练模式样本，k 是指第是指第 k 次迭代。次迭代。+=+0 xwifx0 xwi

31、f0C)k(w)1k(wTkT 梯度下降算法可以看出，当可以看出，当0 xwT时，则时，则 w(k+1)=w(k)，此时不对权向量进行修正；，此时不对权向量进行修正；当当0 xwT时，则时，则 w(k+1)=w(k)+Cxk，需对权向量进行校正，初始权向量，需对权向量进行校正，初始权向量 w(1)的值可任选，显然这就是前面所说的感知器算法，因此感知器算法是梯度法的一个特例。的值可任选，显然这就是前面所说的感知器算法，因此感知器算法是梯度法的一个特例。在上式中在上式中 C 是预先选好的固定值，在迭代过程中，只要是预先选好的固定值，在迭代过程中，只要0 xwT，就要对权向量修正，就要对权向量修正C

32、xk值，因此称为固定增量算法。值，因此称为固定增量算法。?讨论讨论 若正确地选择了准则函数若正确地选择了准则函数J(w,x)，则当权向量，则当权向量w是一个解时，是一个解时，J达到极小值（达到极小值（J的梯度为零）。的梯度为零）。为了使权向量能较快地收敛于一个使函数为了使权向量能较快地收敛于一个使函数J极小的解，极小的解，C值的选择是很重要的。值的选择是很重要的。若若C值太小，则收敛太慢；值太小，则收敛太慢；若若C值太大，则搜索可能过头，引起发散。值太大，则搜索可能过头，引起发散。?梯度下降算法4.5 4.5 最小平方误差准则函数最小平方误差准则函数最小平方误差准则函数最小平方误差准则函数(M

33、SE)MSE)?感知准则函数及其梯度下降算法的缺感知准则函数及其梯度下降算法的缺感知准则函数及其梯度下降算法的缺感知准则函数及其梯度下降算法的缺点：只适用于线性可分情况，对于线性点：只适用于线性可分情况，对于线性点：只适用于线性可分情况，对于线性点：只适用于线性可分情况，对于线性不可分情况，选代过程永远不会终结，不可分情况，选代过程永远不会终结，不可分情况，选代过程永远不会终结，不可分情况，选代过程永远不会终结，即算法不收敛。即算法不收敛。即算法不收敛。即算法不收敛。?在实际问题，事先无法知道样本是否线在实际问题，事先无法知道样本是否线在实际问题，事先无法知道样本是否线在实际问题，事先无法知道

34、样本是否线性可分，因此需要寻求更适合一般情况性可分，因此需要寻求更适合一般情况性可分，因此需要寻求更适合一般情况性可分，因此需要寻求更适合一般情况的算法。的算法。的算法。的算法。?对于两类问题，已知对于两类问题，已知对于两类问题，已知对于两类问题，已知N N个训练样本，寻个训练样本，寻个训练样本，寻个训练样本，寻找权向量找权向量找权向量找权向量a a，使得使得使得使得a aT Ty yi i大于零大于零大于零大于零,i i=1,2,=1,2,N N.将不等式改成等式的形式为将不等式改成等式的形式为将不等式改成等式的形式为将不等式改成等式的形式为a aT Ty yi i=b bi i00;b b

35、i i是任意给定的正常数。是任意给定的正常数。是任意给定的正常数。是任意给定的正常数。N N个方程写成：个方程写成：个方程写成：个方程写成：bYa=dNdNNNddTNTTyyyyyyyyyyyyY21222211121121=?4.5.1 4.5.1 4.5.1 4.5.1 平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解式中，式中，式中，式中，TNbbbb?,21=4.5.1 4.5.1 4.5.1 4.5.1 平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解即：即：即：即：=n

36、dndnnddbbbaaayyyyyyyyy?21101022120111104.5.1 4.5.1 4.5.1 4.5.1 平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解如果如果如果如果Y Y是非奇异的可以直接得出是非奇异的可以直接得出是非奇异的可以直接得出是非奇异的可以直接得出a a。但一。但一。但一。但一般样本数般样本数般样本数般样本数NN总是大于维数总是大于维数总是大于维数总是大于维数，因此，因此，因此，因此Y Y是长方形的矩阵，一般为列满秩矩阵。当是长方形的矩阵，一般为列满秩矩阵。当是长方形的矩阵，一般为列满秩矩阵。当是长方形

37、的矩阵，一般为列满秩矩阵。当方程数多于未知数时，方程数多于未知数时，方程数多于未知数时，方程数多于未知数时，a a是超定的，通是超定的，通是超定的，通是超定的，通常没有精确的解。常没有精确的解。常没有精确的解。常没有精确的解。但我们可以找一个权向量但我们可以找一个权向量但我们可以找一个权向量但我们可以找一个权向量a a，他使得某个，他使得某个，他使得某个，他使得某个关于关于关于关于YaYa和和和和b b的函数最小化。的函数最小化。的函数最小化。的函数最小化。dbYa=?样本数样本数样本数样本数N N总是大于维数总是大于维数总是大于维数总是大于维数(d d+1)+1)，因此，因此，因此，因此Y

38、Y是长是长是长是长方阵。一般为列满秩阵。方阵。一般为列满秩阵。方阵。一般为列满秩阵。方阵。一般为列满秩阵。?方程个数多于未知数，它为矛盾方程组，方程个数多于未知数，它为矛盾方程组，方程个数多于未知数，它为矛盾方程组，方程个数多于未知数，它为矛盾方程组，通常没有精确解存在。但可以寻找最小二通常没有精确解存在。但可以寻找最小二通常没有精确解存在。但可以寻找最小二通常没有精确解存在。但可以寻找最小二乘解。乘解。乘解。乘解。?定义一个误差向量定义一个误差向量定义一个误差向量定义一个误差向量e ebYae=4.5.1 4.5.1 4.5.1 4.5.1 平方误差准则函数及其伪逆解平方误差准则函数及其伪逆

39、解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解4.5.1 4.5.1 4.5.1 4.5.1 平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解bYae=最小平方误差准则函数最小平方误差准则函数最小平方误差准则函数最小平方误差准则函数(MSE)(MSE)(MSE)(MSE)：=NiiiTsbyabYaeaJ1222)(|)(4.5.1 4.5.1 4.5.1 4.5.1 平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解误差平方和最小化问题是个经典问题，它误差平方和最小化问题是个

40、经典问题，它误差平方和最小化问题是个经典问题，它误差平方和最小化问题是个经典问题，它可用梯度搜索法来解决。可用梯度搜索法来解决。可用梯度搜索法来解决。可用梯度搜索法来解决。一个简单的形式相近的解可通过计算梯度一个简单的形式相近的解可通过计算梯度一个简单的形式相近的解可通过计算梯度一个简单的形式相近的解可通过计算梯度1()2()2()NTsiiiiTJaaybyYYab=4.5.1 4.5.1 4.5.1 4.5.1 平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解令令令令这个等式的最大优点是矩阵这个等式的最大优点是矩阵这个等式的最大优点是

41、矩阵这个等式的最大优点是矩阵是个方是个方是个方是个方阵，并且通常是非奇异的。阵，并且通常是非奇异的。阵，并且通常是非奇异的。阵，并且通常是非奇异的。bYYaYTT=*0)(=aJsYYT4.5.1 4.5.1 4.5.1 4.5.1 平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解bYYaYTT=*YYT当当当当是非奇异的时候，有：是非奇异的时候，有：是非奇异的时候，有：是非奇异的时候，有：其中，其中，其中，其中，称其为称其为称其为称其为Y Y的的的的“伪逆伪逆伪逆伪逆矩阵矩阵矩阵矩阵”。注意到，如果。注意到，如果。注意到，如果。注意到，

42、如果Y Y是方阵且是非奇是方阵且是非奇是方阵且是非奇是方阵且是非奇异的，这个伪逆矩阵就是异的，这个伪逆矩阵就是异的，这个伪逆矩阵就是异的，这个伪逆矩阵就是Y Y的逆矩阵，的逆矩阵，的逆矩阵，的逆矩阵，并且并且并且并且，但通常，但通常，但通常，但通常。bYa+=*()TTYYYY1+=IYY=+I+YYMSE解，依赖于解，依赖于b4.5.1 4.5.1 4.5.1 4.5.1 平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解由以上知：解向量由以上知：解向量由以上知：解向量由以上知：解向量a a a a*是依赖向量是依赖向量是依赖向量是依赖向

43、量b b b b；MSEMSEMSEMSE方法的思想：对每个样本设定一个理方法的思想：对每个样本设定一个理方法的思想：对每个样本设定一个理方法的思想：对每个样本设定一个理想的判别函数输出值想的判别函数输出值想的判别函数输出值想的判别函数输出值，以最小平方误，以最小平方误，以最小平方误，以最小平方误差为准则求最优投影方向（差为准则求最优投影方向（差为准则求最优投影方向（差为准则求最优投影方向（权向量权向量权向量权向量a a）ib4.5.1 4.5.1 4.5.1 4.5.1 平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解平方误差准则函数及其伪逆解两个结论两个结论两

44、个结论两个结论：1 1 1 1）若）若）若）若N N N N1 1 1 1个训练样本属于个训练样本属于个训练样本属于个训练样本属于 1 1 1 1,N N N N2 2 2 2个训练样本个训练样本个训练样本个训练样本属于属于属于属于 2 2 2 2，取，取，取，取b b b bi i i i=N/NN/NN/NN/N1 1 1 1,N=NN=NN=NN=N1 1 1 1+N N N N2 2 2 2(i=1,2,.,N(i=1,2,.,N(i=1,2,.,N(i=1,2,.,N1 1 1 1),),),),b b b bi i i i=N/N=N/N=N/N=N/N2 2 2 2,(,(,(,

45、(i=Ni=Ni=Ni=N1 1 1 1+1,.,N+1,.,N+1,.,N+1,.,N),),),),则在线性可分的情况则在线性可分的情况则在线性可分的情况则在线性可分的情况下，下，下，下，MSEMSEMSEMSE解与解与解与解与FisherFisherFisherFisher线性判别函数等价。线性判别函数等价。线性判别函数等价。线性判别函数等价。2 2 2 2）若选取全部若选取全部若选取全部若选取全部b b b bi i i i=1,(i=N=1,(i=N=1,(i=N=1,(i=N1 1 1 1+1,.,N)+1,.,N)+1,.,N)+1,.,N)，MSEMSEMSEMSE解与解与解与

46、解与BayesBayesBayesBayes决策解之间的均方误差达到极小。决策解之间的均方误差达到极小。决策解之间的均方误差达到极小。决策解之间的均方误差达到极小。推导过程详见课本推导过程详见课本推导过程详见课本推导过程详见课本P102p103P102p103P102p103P102p103。4.5.2 MSE准则函数的梯度下降算法4.5.2 MSE准则函数的梯度下降算法2|)(bYaaJs=我们讲到可通过一个梯度下降法来求极小值。这种无需计算伪逆的方法有两个优点：1）避免了是奇异矩阵所带来的问题；2）避免了大矩阵运算。它是一个反馈过程，自动适应由舍入或截断误差所引起的问题。我们讲到可通过一个

47、梯度下降法来求极小值。这种无需计算伪逆的方法有两个优点：1）避免了是奇异矩阵所带来的问题；2）避免了大矩阵运算。它是一个反馈过程，自动适应由舍入或截断误差所引起的问题。YYT4.5.2 MSE准则函数的梯度下降算法4.5.2 MSE准则函数的梯度下降算法对对MSE准则采用梯度下降算法的修正算法，也称为准则采用梯度下降算法的修正算法，也称为Widrow-Hoff算法。其中，是使的样本；是任意正常数。算法。其中，是使的样本；是任意正常数。+=+kkTkkyykabkakaa)()()1(),1(任意kykkTbyka)(11,kk=?样本看成无限重复的序列，即单样本修样本看成无限重复的序列，即单样

48、本修改权向量，改权向量，WidrowWidrow-HoffHoff算法：算法：例题例题利用MSE求解权向量利用MSE求解权向量例题例题x x x x2 2 2 2x x x x1 1 1 1X X4 4(1,1)(1,1)X X3 3(1,0)(1,0)X X1 1(0,0)(0,0)X X2 2(0,1)(0,1)=111101110100Y例题例题=+2121212311111111121)(TTYYYYTb1,1,1,1=TbYa)1,0,2(*=+12)(1+=xxg211=x决策树简介?决策树决策树：一种：一种多级分类器多级分类器，它采用分级的形式，综合用多个决策规则，逐步把复杂的，

49、它采用分级的形式，综合用多个决策规则，逐步把复杂的多类别多类别分类问题转化为若干个分类问题转化为若干个简单的分类简单的分类问题来解决问题来解决n1n2n3n4n5t1t2t3t4t5t6t7多类问题多类问题二叉决策树二叉决策树二叉决策树：除叶节点外，决策树的每个节点：除叶节点外，决策树的每个节点ni都有且只有两个子节点都有且只有两个子节点nil和和nir。二叉决策树把复杂的多类别分类问题转化为。二叉决策树把复杂的多类别分类问题转化为多级两类分类问题多级两类分类问题来解决。在每个节点来解决。在每个节点ni，都把样本集分成两个子集。每个子集可能仍包含多类别的样本，继续分直至仅包含单类别样本的叶节点，都把样本集分成两个子集。每个子集可能仍包含多类别的样本，继续分直至仅包含单类别样本的叶节点n1n2n3n4t1t2t5x25x12x34x2212323t3t4多类问题多类问题