張素文-第3章線性判別函數(shù)

1、第三章第三章 線性判別函數(shù)線性判別函數(shù)3.1 引言引言3.2 線性判別函數(shù)線性判別函數(shù)3.3 廣義線性判別函數(shù)廣義線性判別函數(shù)3.4 感知器算法感知器算法3.5 梯度學(xué)習(xí)算法梯度學(xué)習(xí)算法3.6 最小均方誤差算法（最小均方誤差算法（LMSE）3.7 Fisher線性判別線性判別聚類分析法（第二章）判決函數(shù)法幾何分類法可訓(xùn)練的確定性分類器迭代算法概率分類法可訓(xùn)練的模式分類器迭代算法線性判決函數(shù)法（第三章）統(tǒng) 計(jì) 決 策 方 法非線性判決函數(shù)法復(fù)習(xí)與引申：復(fù)習(xí)與引申：模式識(shí)別統(tǒng)計(jì)若分屬于 和 的兩類模式可用一方程 來(lái)劃分，120)(Xd那么稱 為決策函數(shù)，或稱判決函數(shù)、判別函數(shù)。)(Xd一、判決函數(shù)

2、一、判決函數(shù)(discriminant function) 直接用來(lái)對(duì)模式進(jìn)行分類的準(zhǔn)則函數(shù)。例：一個(gè)二維的兩類判別問(wèn)題，模式分布如圖示，這些分屬于 、 兩類的模式可用一直線方程 來(lái)劃分。120)(Xd0)(32211wxwxwXd（3-1）21,xx為坐標(biāo)變量，321,www為方程參數(shù)。式中：一、判決函數(shù)一、判決函數(shù)(discriminant function) 顏色（綠顏色（綠/ /紅）紅）似圓度判別函數(shù)判別函數(shù)(Discriminant Function)1x2x將某一未知模式 X 代入：若 ，則 類；0)(Xd1X0)(Xd2X若 ，則 類；0)(Xd或拒絕或21XX若 ，則維數(shù)=3時(shí)

3、：判別邊界為一平面。維數(shù)3時(shí)：判別邊界為一超平面。b) 注意：對(duì)判別線正負(fù)的理解和確定。注意：對(duì)判別線正負(fù)的理解和確定。 判別界面正負(fù)側(cè)的確定，是在訓(xùn)練判別函數(shù)的權(quán)值時(shí)確定的，不要和幾何上的概念混淆。 表示的是一種分類的標(biāo)準(zhǔn)，它可以是1、2、3維的，也 可以是更高維的。)(Xd說(shuō)明：32211)(wxwxwXd0)(121XdX則，若0)(212XdX則，若1、判決函數(shù) 的幾何性質(zhì)。它可以是線性的或非線性的函 數(shù)，維數(shù)在特征提取時(shí)已經(jīng)確定。)(Xd如：已知三維線性分類 判決函數(shù)的性質(zhì)就確定了判決函數(shù) 的形式：4332211)(wxwxwxwXd二、確定判別函數(shù)的兩個(gè)因素二、確定判別函數(shù)的兩個(gè)因

4、素例：非線性判決函數(shù)2. 判決函數(shù))( Xd的系數(shù)。用所給的模式樣本確定。1x2x1x2x3.2 線性判別函數(shù)線性判別函數(shù)一、一般形式一、一般形式將二維模式推廣到n維，線性判別函數(shù)的一般形式為： 101nnn2211 ntwXWwxwxwxwXd (3-2)tnxxxX,.,21式中：tnwwwW,.,210：權(quán)向量，即參數(shù)向量。 XWxxxwwwwwxwxwxwXdtnnn11 211211nnn2211tnnwwwwW121,.,tnxxxX1 ,.,21上式也可寫為增廣向量的形式：式中：為增廣權(quán)向量，為增廣模式向量。21, 0, 0)(XXXWXdt若若二、線性判決函數(shù)的性質(zhì)二、線性判決

5、函數(shù)的性質(zhì)21, 0, 0)(XXXWXdt則則 識(shí)別時(shí)： 若1、兩類情況：訓(xùn)練時(shí)：（= 0是不可判別情況，可以或拒絕或21XX）模式可為M類， 、 、 、 ，有三種劃分方式：12M2、多類情況：ii兩分法ji兩分法ji兩分法特例ii兩分法(1) 用線性判別函數(shù)將屬于i類的模式與其余不屬于i類的模式分開(kāi)。MiXXXWXdiitii，若若1, 0, 0)(從而訓(xùn)練出第i類判決函數(shù)的權(quán)向量tniiniiiwwwwW,121將某個(gè)待分類模式 X 分別代入 M 個(gè)類的d (X)中，若只有di(X)0，其他d(X)均其他所有d。最大判別準(zhǔn)則最大判別準(zhǔn)則特點(diǎn)： 是第二種情況的特例。因?yàn)榭梢远x： XdXd

6、Xdijji)( ijXdXdji,)(0)(Xdij可證明：即：若各類別在第三種情況下可分，則在第二種情況下也可分，但反之不一定。 把 M 類情況分成了M-1個(gè)兩類問(wèn)題。并且 類的判別界面全部與 類的判別界面相鄰(向無(wú)窮遠(yuǎn)處延伸的區(qū)域除外)。iijj 除邊界區(qū)外，沒(méi)有不確定區(qū)域。23212211)(1)()(xXdxxXdxxXd例5：一個(gè)三類模式（M=3）分類器，其判決函數(shù)為： 且分別給出三類的判決界面。tX1 , 1 0 試判斷屬于哪一類，解： 2003020102030201)()()()(1)(1111)(011)(XXdXdXdXdXdXdXd012)()(121xXdXd02)(

7、)(2131xxXdXd012)()(112xXdXd012)()(2132xxXdXd)()(1331XdXd)()(2332XdXd類的判決函數(shù)：1判決界面如圖所示。類的判決函數(shù)：2類的判決函數(shù)：3例六：已知判決界面的位置和正負(fù)側(cè)，找區(qū)域。1321、明確概念：線性可分。 一旦線性判別函數(shù)的系數(shù) 被確定以后，這些函數(shù)就可作為模式分類的基礎(chǔ)。kW三、小結(jié)三、小結(jié)2、 分法的比較：jiii與 對(duì)于M類模式的分類， 兩分法共需要M個(gè)判別函數(shù)，但 兩分法需要M(M-1)/2個(gè)。當(dāng)時(shí)M3時(shí)，后者需要更多個(gè)判別式（缺點(diǎn)），但對(duì)模式的線性可分的可能性要更大一些（優(yōu)點(diǎn)）。 jiii原因： 一種類別模式的分布

8、要比M-1類模式的分布更為聚集， 分法受到的限制條件少，故線性可分的可能性大。ji3.3 廣義線性判別函數(shù)廣義線性判別函數(shù)1、目的： 對(duì)非線性邊界面：通過(guò)某映射，把模式空間X變成X*，以便將X空間中非線性可分的模式集，變成在X*空間中線性可分的模式集。2、定義： 設(shè)一訓(xùn)練用模式集， 在模式空間X中線性不可分，非線性判別函數(shù)形式如下： X 12211 X kkkwfwXfwXfwXd (3.3-1)式中 是模式X的單值實(shí)函數(shù)，廣義形式的模式向量定義為：kiXfi,2, 1,tkXfXfXfX1 ,*21 (3.3-2) 1nnn2211 wxwxwxwXd 的形式是多種多樣的。以X為二維時(shí)， 選

9、用二次多項(xiàng)式函數(shù)為例，如原判別的函數(shù)為： Xfi Xfi這里X*空間的維數(shù)k高于X空間的維數(shù)n，則(3.3-1)式寫成簡(jiǎn)化的向量形式：上式是線性的。討論線性判別函數(shù)并不會(huì)失去一般性的意義。tkktwwwwWXdXWXd121,* (3.3-3)32211222221122111)(wxwxwxwxxwxwXd2233*xXfx144*xXfx255*xXfx2111*xXfx2122*xxXfx定義：則可將 線性化為txxxxxxX1 ,*21222121twwwwwwW321221211,Xd*XWXdt即：。3.4 感知器算法感知器算法一種設(shè)計(jì)線性分類器的算法感知器的概念1x2xdx1w2

10、wdwy1x2xdx1w2wdwy11感知器線性閾值單元)sgn()2(0, 10, 1)(0111XWYxwxwYxwfytdiiidiiidiii)sgn(Y) 1,(X),(),(X),(def212121210XWxxxwwwWxxxwwwWtdtdtdtdt則，若令：式中：在（2）式中，令式中：11001)(ddttdiiiwwXWXWxwxgjiXXgXXg0)(0)(兩類問(wèn)題ji/并且令：Y1和Y1，分別表示兩種類型，則（2）式演變?yōu)椋簡(jiǎn)栴}：已知訓(xùn)練樣本集 ，求加權(quán)向量W*。),X21ktXXX3.4 感知器算法感知器算法 XWwxwxwxwXdt4332211 一、概念理解一、

11、概念理解只要求出權(quán)向量，分類器的設(shè)計(jì)即告完成。本節(jié)開(kāi)始介紹如何通過(guò)各種算法，利用已知類別的模式樣本訓(xùn)練出權(quán)向量W。（2）“感知器”：對(duì)一種分類學(xué)習(xí)機(jī)模型的稱呼，屬于有關(guān)機(jī)器學(xué)習(xí)的仿生學(xué)領(lǐng)域中的問(wèn)題，由于無(wú)法實(shí)現(xiàn)非線性分類而下馬。但“賞罰概念（The Reward-Punishment Concept）” 今天仍在模式識(shí)別中起著很大的作用。（1）“訓(xùn)練”：對(duì)于線性判別函數(shù)，當(dāng)模式的維數(shù)知道時(shí)，判別函數(shù)的形式實(shí)際上也就定了下來(lái)，如：三維時(shí)txxxX1,321twwwwW4321, 已知兩個(gè)訓(xùn)練模式集，分屬于 和 ，任取權(quán)向量初始值W(1)，開(kāi)始迭代。 12二、感器學(xué)習(xí)算法二、感器學(xué)習(xí)算法（ “賞罰

12、”過(guò)程）1、用全部訓(xùn)練模式集進(jìn)行一輪迭代，計(jì)算 的值。 itXkW2、分三種情況，更新權(quán)向量的值： icXkWkW1c為正的校正增量。（3.4-1）則分類器對(duì)第i個(gè)模式 做了 ，且若01itiXkWXiX錯(cuò)誤分類，權(quán)向量校正為： icXkWkW1為錯(cuò)誤分類，有：若對(duì)的樣本乘以（-1），則（3.4-2）改寫為： （3.4-2） 時(shí)，0itXkW icXkWkW1 （3.4-3） ，且若02itiXkWX kWkW1若不是以上兩種情況，表明分類正確，權(quán)向量不變，即統(tǒng)一寫為： 0, 0,1itiitXkWcXkWXkWkWkW若若式中c為正的校正增量。 （3.4-4）3、只要有一個(gè)樣本判別錯(cuò)誤，則進(jìn)

13、行第二輪迭代，直至用全部模式進(jìn)行訓(xùn)練都獲得正確分類結(jié)果，迭代結(jié)束。感知器算法是一種賞罰過(guò)程：分類正確時(shí)，對(duì)權(quán)向量“賞”這里用“不罰”，即權(quán)向量不變；分類錯(cuò)誤時(shí)，對(duì)權(quán)向量“罰”對(duì)其修改，向正確的方向轉(zhuǎn)換。三、收斂性三、收斂性 收斂性：經(jīng)過(guò)算法的有限次迭代運(yùn)算后，求出了一個(gè)使所有樣本都能正確分類的W，則稱算法是收斂的。可以證明感知器算法是收斂的。收斂條件：模式類別線性可分。 例：用感知器算法求出將圖示模式分為兩類的權(quán)向量解。 解：將模式特征向量寫成增廣向量形式，將屬于 的訓(xùn)練樣本乘以（-1）：2tX1 , 0 , 01tX1 , 1 , 02tX1, 0 , 13tX1, 1, 140) 1 (W

14、取c=1，。則迭代過(guò)程為：第一輪： 0,1000 , 0 , 0) 1 (1XWtt11 , 0 , 0)1 ()2(, 0XWW故1,1101 , 0 , 0) 2(2XWtt1 , 0 , 0)2()3(, 0WW故-1,1-01-1 , 0 , 0) 3(3XWtt30 , 0 , 1-) 3()4(, 0XWW故1,1-1-1-0 , 0 , 1-) 4(4XWtt0 , 0 , 1-)4()5(, 0WW故 第一輪迭代中有兩個(gè)0的情況（判別錯(cuò)誤的情況），進(jìn)行第二輪迭代。t111 , 0 , 1-)5()6(,00)5(XWWXWt故t21 , 0 , 1-(6)7(,01)6(WWX

15、Wt故t330 , 0 , 2-)7()8(,00)7(XWWXWt故t40 , 0 , 2-)8()9(,02)8(WWXWt故第二輪：t111 , 0 , 2-)9()10(,00)9(XWWXWt故(10)11(,01)10(2WWXWt故)11()12(,01)11(3WWXWt故)12()13(,01)12(4WWXWt故第三輪：)13()14(,01)13(1WWXWt故(14)15(,01)14(2WWXWt故)15()16(,01)15(3WWXWt故)16()17(,01)16(4WWXWt故第四輪：t1 , 0 , 2W12)(1xxd該輪迭代的分類全部正確，故解向量相應(yīng)的

16、判別函數(shù)為： 判別界面d(X)=0如圖示。 當(dāng)c、W(1)取其他值時(shí)，結(jié)果可能不一樣，所以感知器算法的解不是單值的。0 ,01X 將兩個(gè)模式的分類推廣到多個(gè)模式分類的情況，采用3.2節(jié)中介紹的多類情況中的第三種方法，即：四、感知器算法用于多類情況四、感知器算法用于多類情況Mj, 1iX ,)(ijXdXdji若，則 Midi, 1,對(duì)于M類模式應(yīng)存在M個(gè)判決函數(shù)：算法推導(dǎo)：M,21設(shè)有 M 種模式類別： MjWj, 1,1設(shè)其權(quán)向量初值為：一個(gè)屬于 類的模式樣本 X 被送入分類器，則：i1. 計(jì)算出M個(gè)判決函數(shù)： MjXkWXdtjj, 1, 若第l個(gè)權(quán)向量使 ，則相應(yīng)的權(quán)向量作調(diào)整，即： X

17、dXdli lijkWkWcXkWkWcXkWkWjjllii,111 可以證明：只要該模式類別用情況三判別函數(shù)時(shí)是可分的，則該算法經(jīng)過(guò)有限次迭代后收斂。， c為一正常數(shù)。 若 則權(quán)向量不變； ijXdXdji MikWkWii, 112. 判別：采用多類情況3的方法時(shí)，應(yīng)有：4. 感知器算法用于多類情況感知器算法用于多類情況Mj, 1= iX ,)(ijddjiXX若，則 Midi, 1,對(duì)于M類模式應(yīng)存在M個(gè)判決函數(shù)：算法主要內(nèi)容：M,21設(shè)有 M 種模式類別： Mjj, 1,1W設(shè)其權(quán)向量初值為： 第k次迭代時(shí)，一個(gè)屬于i類的模式樣本 X 被送入分類器，計(jì)算所有判別函數(shù)訓(xùn)練樣本為增廣向量

18、形式，但不需要規(guī)范化處理不需要規(guī)范化處理。 分二種情況修改權(quán)向量： Mjkkdjj, 1,TXW 若第l個(gè)權(quán)向量使 ，則相應(yīng)的權(quán)向量作調(diào)整，即： lijkkckkckkjjllii,111WWXWWXWW 可以證明：只要模式類在情況3判別函數(shù)時(shí)是可分的，則經(jīng)過(guò)有限次迭代后算法收斂。， c為正的校正增量例例3.9 設(shè)有三個(gè)線性可分的模式類，三類的訓(xùn)練樣本分別為 若 則權(quán)向量不變； Mjijkdkdji, 2 , 1;, Mjkkjj, 2 , 1,1WW( )( )kdkdli T33T22T111 , 11 , 10 , 0XXX：；：；：現(xiàn)采用多類情況3的方式分類，試用感知器算法求出判別函數(shù)

19、。 解：增廣向量形式：T3T2T11,1, 1,1,1, 1,1 , 0 , 0XXX注意，這里任一類的樣本都不能乘以（1）。任取初始權(quán)向量T3210 , 0 , 0) 1 () 1 () 1 (WWW；c=1 第一次迭代： 0111T11XWd 0111T22XWd 0111T33XWd三個(gè)權(quán)向量都需要修改：11X 1121dd 1131dd，但且不成立，T1111 , 0 , 0) 1 ()2(XWWT1221, 0 , 0) 1 ()2(XWWT1331, 0 , 0) 1 ()2(XWW第二次迭代： 1222T11XWd 1222T22XWd 1222T33XWd22X 2212dd

20、2232dd，但且不成立，修改權(quán)向量：T2110 , 1, 1)2() 3(XWWT2220 , 1 , 1)2() 3(XWWT2332, 1, 1)2()3(XWW第三次迭代： 修改為權(quán)向量。33X 3313dd 3323dd，但且不成立， 以上進(jìn)行的一輪迭代運(yùn)算中，三個(gè)樣本都未正確分類，進(jìn)行下一輪迭代。第四次迭代： 在第五、六、七迭代中，對(duì)所有三個(gè)樣本都已正確分類。權(quán)向量的解：T11110 , 2, 0)5()6()7(WWWWT22222, 0 , 2)5()6()7(WWWWT33332, 0 , 2)5()6()7(WWWW判別函數(shù)：212)(xdX22)(12xdX22)(13x

21、dX 設(shè)函數(shù)f(Y)是向量 的函數(shù)，則f(Y)的梯度定義為：3.5 梯度學(xué)習(xí)算法梯度學(xué)習(xí)算法tnyyyY,21 tnyfyfyfYfdYdYf,21即： 梯度的梯度的方向方向是函數(shù) f(Y) 在Y點(diǎn)增長(zhǎng)最快的方向， 梯度的梯度的模模是f(Y)在增長(zhǎng)最快的方向上的增長(zhǎng)率。 （增長(zhǎng)率的最大值）一、梯度概念、梯度概念 (3.5-1) 梯度向量的最重要性質(zhì)之一：指出函數(shù) f 在其自變量增加時(shí)，最大增大率的方向。例：對(duì)一個(gè)二維向量 ，令 ，則 在幾何上表示一個(gè)曲面，這個(gè)曲面被 （常數(shù)）所截得的等高線，在 平面上的投影是一條曲線L，不同的C值得到不同的等高線。 txxX21,21,xxfXf Xf CXf

22、21oxx由 、 平面所截的等高線在平面 的投影為L(zhǎng)1 、L2 。L1上A 點(diǎn)的梯度方向與函數(shù)f(X)在點(diǎn)A的法線方向一致，是函數(shù)f(X)在點(diǎn)A增長(zhǎng)最快的方向。 1CXf21oxx21,aa 2CXf 若從高度C1到達(dá)C2，顯然，若以同樣的速率增長(zhǎng)，沿梯度方向肯定是最快到達(dá)的。2L顯然：負(fù)梯度指出了最陡下降方向。梯度算法的依據(jù)。二、梯度法二、梯度法 設(shè)兩個(gè)線性可分的模式類1和2的樣本共N個(gè)，2類樣本乘(-1)。將兩類樣本分開(kāi)的判決函數(shù)d(X)應(yīng)滿足： 梯度算法的目的仍然是求一個(gè)滿足上述條件的權(quán)向量，主導(dǎo)思想是將聯(lián)立不等式求解W的問(wèn)題，轉(zhuǎn)換成求準(zhǔn)則函數(shù)極小值的問(wèn)題。NiXWXdit, 2 , 1

23、0)(N個(gè)不等式 準(zhǔn)則函數(shù)的選取原則： 具有唯一的最小值，并且這個(gè)最小值發(fā)生在W tXi0時(shí)。因此：尋找滿足W tXi0的W的問(wèn)題，變?yōu)閷ふ沂笿(W, X )達(dá)到極小值的W的問(wèn)題。即通過(guò)求準(zhǔn)則函數(shù)極小值求符合要求的權(quán)向量?；舅悸罚?定義一個(gè)對(duì)錯(cuò)誤分類敏感的準(zhǔn)則函數(shù)J(W, X)，在J的梯度方向上對(duì)權(quán)向量進(jìn)行修改。一般關(guān)系表示成從W(k)導(dǎo)出W(k+1)：其中c是正的比例因子。 kWWWXWJckWJckWkW,1(3.5-2)梯度法求解步驟：b) 依次將所有樣本X代入準(zhǔn)則函數(shù)J，對(duì)某個(gè)特定的X，J是W的函數(shù)，即J(W，X)=J(W)。求J對(duì)W的導(dǎo)數(shù)，代入當(dāng)時(shí)的W(k)的值，求出 。Ja) 選

24、擇初始權(quán)向量W(1)。c) 按(3.5-2)式修改權(quán)向量。若對(duì)所有樣本均有 ，則W不再變化，算法收斂。0J例：選擇準(zhǔn)則函數(shù)XWXWXWJtt),(解：不妨簡(jiǎn)單地設(shè) X=1（標(biāo)量）。此時(shí)wwXWJ),(錯(cuò)誤分類時(shí)： 22,1wwwwwXWWJJX0010wwXWt ckWckWkW221， 對(duì)權(quán)向量校正。 JckWkW1正確分類時(shí)：0010wwXWt0wwwJ kWckWkW01， 對(duì)權(quán)向量不做修正。說(shuō)明： 隨著權(quán)向量W向理想值接近，準(zhǔn)則函數(shù)關(guān)于W的導(dǎo)數(shù) (即這里的梯度 ）會(huì)越來(lái)越趨近于零，這意味著準(zhǔn)則函數(shù)J 越來(lái)越接近最小值。當(dāng) 最終 時(shí)，J達(dá)到最小值，此時(shí)W不再改變，算法收斂。J0J 將感知

25、器算法中聯(lián)立不等式求解W的問(wèn)題，轉(zhuǎn)換為求函數(shù)J極小值的問(wèn)題。 kWWWXWJckWJckWkW,1 b) 梯度算法是求解權(quán)向量的一般解法，算法的具體計(jì)算形式取決于準(zhǔn)則函數(shù)J(W, X)的選擇，J(W, X)的形式不同，得到的具體算法不同。a) c) c值的選擇很重要，如c值太小，收斂太慢；但若太大，搜索又可能過(guò)頭，甚至引起發(fā)散。3.6 最小均（平）方誤差算法最小均（平）方誤差算法（Least Mean Square Error, LMSE；亦稱Ho-Kashyap算法） 上述的感知器算法和由梯度導(dǎo)出的固定增量算法或其他類似方法，只是當(dāng)被分模式可分離時(shí)才收斂，在不可分的情況下，算法會(huì)來(lái)回?cái)[動(dòng)，始

26、終不收斂。當(dāng)一次次迭代而又不見(jiàn)收斂時(shí)，造成不收斂現(xiàn)象的原因分不清，有兩種可能：a) 迭代過(guò)程本身收斂緩慢b) 模式本身不可分對(duì)可分模式收斂。對(duì)于類別不可分的情況也能指出來(lái)。LMSE算法特點(diǎn)：一、分類器的不等式方程、分類器的不等式方程 兩類分類問(wèn)題的解相當(dāng)于求一組線性不等式的解。如果給出分別屬于 、 兩個(gè)模式的訓(xùn)練樣本集，應(yīng)滿足：1221, 0, 0XXWXXWtt若將 的模式乘以（-1），則對(duì)全部模式都有：20XWt (3.6-1) 設(shè)模式樣本為n維，兩類模式的訓(xùn)練樣本總數(shù)為N個(gè)，將上式分開(kāi)寫有：NnNnnNNnnnnnnXwxwxwxwXwxwxwxwXwxwxwxw對(duì)對(duì)對(duì)000122112

27、12222211111122111類1類2寫成矩陣形式為 ： 0wwwwxxxxxxxxxNnnnnNNnNNnn11112112122221112110000111NnNnnNNnnnnnnXwxwxwxwXwxwxwxwXwxwxwxw對(duì)對(duì)對(duì)00012211212222211111122111類1類2令N (n+1)維的長(zhǎng)方矩陣為X（正體），則(3.6-1)式 變?yōu)椋?XWt0WX (3.6-2)顯然式中：tnnwwwwW121,0為零向量。1211XnNtNtNtit2t1XXXXX感知器算法實(shí)際就是通過(guò)(3.6-2)不等式組求出W的。0wwwwxxxxxxxxxNnnnnNNnNNnn

28、111121121222211121100001110WX (3.6-2)二、二、LMSE算法（算法（H-K算法）算法）1、原理、原理LMSE算法把對(duì)滿足 的求解，改為滿足0WX的求解。BW X(3.6-3) 兩式等價(jià)。定義準(zhǔn)則函數(shù)： 21221X21,NiiitbXWBWBXWJ(3.6-4)tNibbbbB,21為各分量均為正值的矢量。式中： 在方程組中，當(dāng)行數(shù)列數(shù)時(shí)，通常無(wú)解，稱為矛盾方程組，一般求近似解。在模式識(shí)別中，通常訓(xùn)練樣本數(shù)N總是大于模式的維數(shù)n，因此方程的個(gè)數(shù)（行數(shù)）模式向量的維數(shù)（列數(shù)），即方程組為矛盾方程組，通常無(wú)精確解存在，但可求最小二乘解W*，即 ，W*為近似解。極小

29、BW *X說(shuō)明： LMSE算法的出發(fā)點(diǎn)：選擇一個(gè)準(zhǔn)則函數(shù)，使得當(dāng)J達(dá)到最小值時(shí)， 可得到近似解（最小二乘解）。BW X LMSE算法的思路：使準(zhǔn)則函數(shù)最小、找求解對(duì)求解對(duì)BWBWWX0X轉(zhuǎn)化為轉(zhuǎn)化為 使J達(dá)到最小值的解W，就是矛盾方程組的最小二乘近似解，也稱最優(yōu)近似解。21221X21,NiiitbXWBWBXWJ“最小二乘”最小:：使方程組兩邊誤差最小，也即使J最小。二乘：括號(hào)的次數(shù)為2，乘了兩次； 也即“最小平方（誤差算法）“最優(yōu)近似解”使方程組兩邊所有誤差之和最小 （即最優(yōu)）的解。1111121111221111111111XNNinnnnNNnNininnbbbwwwwxxxxxxxx

30、BWNNtiittNNnnNnNinnininnnbXWbXWbXWbwwxwxbwwxwxbwwxwx111111111111111矢量各分量的平方和矢量各分量的平方和22XBW矢量：準(zhǔn)則函數(shù)的推導(dǎo)：21221X21,NiiitbXWBWBXWJNiiitNNttbXWbXWbXWBW1222112XNiiitNNttbXWbXWbXWBWBXWJ12221122121X21,從(3.6-3)和 (3.6-4)式可看出： 當(dāng)函數(shù)J達(dá)到最小值，等式有最優(yōu)解。即又將問(wèn)題轉(zhuǎn)化為求準(zhǔn)則函數(shù)極小值的問(wèn)題。 因?yàn)镴有兩個(gè)變量W和B，有更多的自由度供選擇求解，故可望改善算法的收斂速率。BW X(3.6-3

31、)21221X21,NiiitbXWBWBXWJ(3.6-4)2、推導(dǎo)、推導(dǎo)LMSE算法遞推公式算法遞推公式與問(wèn)題相關(guān)的兩個(gè)梯度： BWWJtXXBWBWBJXX21 1) 求W的迭代式：使J 對(duì)W求最小，有：BBWBWBWt#t1tttXXXXXXX0XX由式可知：只要求出B，就可求出W。求遞推公式：0WJ得：令t1t#XXXX1 nN稱為X的偽逆，X為階長(zhǎng)方陣，式中： #XN1n為階。2) 求B的迭代式： 利用梯度法中的(3.5-2)式 kWWWXWJckWkW,1有： kBBBJckBkB1 kBkWkBkWckBkBXX21 kekeckBkB1代入：cc 2 kekBkWX 令，定義

32、#13) 求W(k+1)的迭代式：將代入式BW#X有： kekeckBkBkW#X1X1 keckWkeckeckB#XXXX 0kBkBkBkWke#t1tt1t#XXXXXXXXXX#2式中：BWBWBJXX21=0 1X1#BW kBkWke X keckWkW#X1 kekeckBkB1 1X1#BW kBkWke X kekeckBkB11X1#kBkW設(shè)初值B(1)，須使其每一分量都為正值。W(k+1)、B(k+1)互相獨(dú)立，均只與 有關(guān)。故迭代式中也可先算B(k+1)，然后按 ke1X1#kBkW來(lái)計(jì)算，即：e求出B、 W后，再迭代出下一個(gè) ，從而計(jì)算出新的B、 W?？偨Y(jié)LMSE

33、算法迭代式：#2#1三、模式類別可分性的判別及算法的特點(diǎn)：三、模式類別可分性的判別及算法的特點(diǎn)：（一）可分性判別（一）可分性判別 如果 ，這時(shí)隱含 ，有解。如繼續(xù)迭代， 可使 。 0ke 0kBkWX 0ke 如果 的所有分量為負(fù)數(shù)或零（但不是全部為零），停止迭代，無(wú)解。此時(shí)若繼續(xù)迭代下去，數(shù)據(jù)不再發(fā)生變化。 ke 可以證明：當(dāng)模式類線性可分，且校正系數(shù)c滿足 時(shí)，該算法收斂，可求得解W。10c 理論上不能證明該算法到底需要迭代多少步才能達(dá)到收斂，通常在每次迭代計(jì)算后檢查一下 和誤差向量 ，從而可以判斷是否收斂。 kWX ke 如果 或 （即 ），有解。 0ke 0kBkWX 0kWX分以下幾

34、種情況：關(guān)于的說(shuō)明： 通過(guò)反證法可以證明：在線性可分情況下，算法進(jìn)行過(guò)程中不會(huì)出現(xiàn) 的分量全為負(fù)的情況；若出現(xiàn) 的分量全為負(fù)，則說(shuō)明模式類線性不可分。 ke keb) 所有分量為非正，繼續(xù)迭代數(shù)據(jù)無(wú)變化的情況分析： ke 如果 的所有分量為負(fù)數(shù)或零（但不是全部為零），停止迭代，無(wú)解。此時(shí)若繼續(xù)迭代下去，數(shù)據(jù)不再發(fā)生變化。 ke kekeckBkB111X1kBkWke 0ke kWkW1 keke1 kBkB1 kekeckWkW#X11X1#kBkW或 綜上所述：只有當(dāng) 中有大于零的分量時(shí)，才需要繼續(xù)迭代，一旦 的全部分量只有0和負(fù)數(shù)，則立即停止。事實(shí)上，往往早在 全部分量都達(dá)到非正值以前，

35、就能看出其中有些分量向正值變化得極慢，可及早采取對(duì)策。 ke ke ke（二）算法特點(diǎn)（二）算法特點(diǎn) 除了對(duì)可分模式是收斂的以外，對(duì)于線性不可分的模式，在算法迭代過(guò)程中就可明確的表示出來(lái)。例1：已知兩類模式訓(xùn)練樣本： tt1 ,0,0,01 tt1 , 1,0, 12111101110100Xt1t#XXXX解：1）寫出增廣矩陣： 2）求偽逆矩陣422221212111101110100111110101100XXt*1AA1A求逆矩陣：333231232221131211Aaaaaaaaaa332313232212312111*AAAAAAAAAA若，則 ijAija 是 的代數(shù)余子式，注意

36、兩者的行和列的標(biāo)號(hào)互換。 tt1 ,0,0,01 tt1 , 1,0, 12|A|A的行列式A*A的伴隨矩陣代數(shù)余子式定義： 劃去aij所在的行和列的元素，余下元素構(gòu)成的行列式做aij的余子式，記作Mij ，將 叫做元素aij的代數(shù)余子式。例： ijijAM1-ji 323112113231121132231-Aaaaaaaaa32224020441322240204XX1XX1tt44884416422221212XXt行列式: 333231232221131211Aaaaaaaaaa422221212XXt*1AA1A111322222222411111101011003222402044

37、1X# 102408411111111322222222411X1#BW tB1 , 1 , 1 , 11 3）開(kāi)始迭代：取和c=1. 000011111111111110211110111010011X1BWe 121xXd故W(1)就是解，即判斷函數(shù)為：t1t#XXXX圖示如下： tt1 , 1,0 , 01 tt0 , 1,1 , 02例2：已知模式訓(xùn)練樣本：101110111100X 2）求 ：#Xt1t#XXXX11132222222241解：1）增廣矩陣： tB1 , 1 , 1 , 11 3）迭代：取和c=1. tBW0001X1# tttBWe11111111000011X1

38、全部分量為負(fù)，無(wú)解，停止迭代。為線性不可分模式。 1e可以看出：2）算法盡管略為復(fù)雜一些，但它提供了線性可分的測(cè)試特征，并且收斂速度也比前面的梯度法（包括感知器算法）要快一些。1）LMSE算法的明顯缺點(diǎn)是需要對(duì)矩陣 求逆，好在一個(gè)分類問(wèn)題，只要進(jìn)行一次求逆。此外，當(dāng)新的一行加入X中時(shí)（即新的模式樣本加入），逆矩陣有迭代算法。XXt小結(jié)：小結(jié)：1、感知器法、梯度法、最小平方誤差算法討論的分類算法都是通過(guò)模式樣本來(lái)確定判別函數(shù)的系數(shù)，所以要使一個(gè)分類器設(shè)計(jì)完善，必須采用有代表性的數(shù)據(jù)，訓(xùn)練判別函數(shù)的權(quán)系數(shù)。它們能合理反映模式數(shù)據(jù)的總體。2、要獲得一個(gè)有較好判別性能的線性分類器，所需要的訓(xùn)練樣本的數(shù)

39、目的確定。用指標(biāo)二分能力Ck來(lái)決定訓(xùn)練樣本的數(shù)目：通常訓(xùn)練樣本的數(shù)目不能低于Ck，選為 Ck的1020倍左右。二維：不能低于6個(gè)樣本，最好選在60120個(gè)樣本之間。三維：不能低于8個(gè)樣本，最好選在80160個(gè)樣本之間。12kCkk為模式維數(shù)如復(fù)習(xí)：復(fù)習(xí)：LMSE算法算法1、算法過(guò)程、算法過(guò)程 由已知類別的樣本寫出增廣矩陣X，求出 ，設(shè)B(1)、c初值，B(1)每一分量必須全為正值。t1t#XXXX kBkW#X kBkWke X 迭代計(jì)算： ke 核查一下XW(k)、 ，確定繼續(xù)迭代或停止。 若繼續(xù)，計(jì)算 keckWkW#X1 kekeckBkB1 kekeckBkB11X1#kBkW或回到 2、可分性判別、可分性判別 綜上所述：只有當(dāng) 中有大于零的分量時(shí)，才需要繼續(xù)迭代，一旦 的全部分量只有0和負(fù)數(shù)，則立即停止。 ke ke 如果 ，這時(shí)隱含 ，有解。如繼續(xù)迭代， 可使 。 0ke 0kBkWX 0ke 如果 的所有分量