線性判別函數(shù)法

1、第第2章章 判別函數(shù)及幾何分類(lèi)法判別函數(shù)及幾何分類(lèi)法2.1 判別函數(shù)判別函數(shù)2.2 線性判別函數(shù)線性判別函數(shù)2.3 廣義線性判別函數(shù)廣義線性判別函數(shù)2.4 線性判別函數(shù)的幾何性質(zhì)線性判別函數(shù)的幾何性質(zhì)2.5 感知器算法感知器算法2.6 梯度法梯度法2.7 最小平方誤差算法最小平方誤差算法2.8 非線性判別函數(shù)非線性判別函數(shù)聚類(lèi)分析法（第6章）判決函數(shù)法幾何分類(lèi)法確定性事件分類(lèi)（第2章）概率分類(lèi)法隨機(jī)事件分類(lèi)（第3章）線性判決函數(shù)法統(tǒng) 計(jì) 決 策 方 法非線性判決函數(shù)法復(fù)習(xí)與引申：復(fù)習(xí)與引申：模式識(shí)別統(tǒng)計(jì)若分屬于1，2的兩類(lèi)模式可用一方程d(X) =0來(lái)劃分，那么稱d(X) 為判別函數(shù)，或稱判決

2、函數(shù)、決策函數(shù)。2.1 判別函數(shù)判別函數(shù)(discriminant function) 直接用來(lái)對(duì)模式進(jìn)行分類(lèi)的準(zhǔn)則函數(shù)。例：一個(gè)二維的兩類(lèi)判別問(wèn)題，模式分布如圖示，這些分屬于1，2兩類(lèi)的模式可用一直線方程 d(X)=0來(lái)劃分。0)(32211wxwxwd X21,xx為坐標(biāo)變量，321,www為方程參數(shù)。式中：圖2.2 兩類(lèi)二維模式的分布1判別函數(shù)的定義判別函數(shù)的定義若 ，則若 ，則 類(lèi)；若 ，則 類(lèi)；0)(Xd1X0)(Xd2X0)(Xd21XX或 或拒絕將某一未知模式 X 代入：維數(shù)=3時(shí)：判別邊界為一平面。維數(shù)3時(shí)：判別邊界為一超平面。32211)(wxwxwdX d(X) 表示的是一

3、種分類(lèi)的標(biāo)準(zhǔn)，它可以是1、2、3維的，也可以是更高維的。 判別界面的正負(fù)側(cè)，是在訓(xùn)練判別函數(shù)的權(quán)值時(shí)確定的。2判別函數(shù)正負(fù)值的確定判別函數(shù)正負(fù)值的確定圖2.3 判別函數(shù)正負(fù)的確定1）判決函數(shù)d(X)的幾何性質(zhì)。它可以是線性的或非線性的函 數(shù)，維數(shù)在特征提取時(shí)已經(jīng)確定。如：已知三維線性分類(lèi) 判決函數(shù)的性質(zhì)就確定了判決函數(shù) 的形式：4332211)(wxwxwxwdX3. 確定判別函數(shù)的兩個(gè)因素確定判別函數(shù)的兩個(gè)因素例：非線性判決函數(shù)2）判決函數(shù)d(X)的系數(shù)。用所給的模式樣本確定。2.2 線性判別函數(shù)線性判別函數(shù)2.2.1 線性判別函數(shù)的一般形式線性判別函數(shù)的一般形式將二維模式推廣到n維，線性判

4、別函數(shù)的一般形式為：T1 122nn00 dw xw xw xwwXW X (2-2)T21,.,nxxxX式中：1 122nn012T120 11nndw xw xw xwxxwwwwxL LMXW XT120,.,nwwwwWT211 ,.,nxxxX增廣向量的形式：式中：為增廣權(quán)向量，為增廣模式向量。T12,.,nw wwW權(quán)向量2.2.2 線性判別函數(shù)的性質(zhì)線性判別函數(shù)的性質(zhì)21T, 0, 0)(XXXWX若若d1. 兩類(lèi)情況d(X) = 0：不可判別情況，可以或拒絕或21XX） 對(duì)M個(gè)線性可分模式類(lèi)，1， 2， M，有三種劃分方式：2. 多類(lèi)情況 ii兩分法兩分法ji兩分法兩分法ji

5、兩分法特例兩分法特例ii兩分法(1)多類(lèi)情況1： 用線性判別函數(shù)將屬于i類(lèi)的模式與其余不屬于i類(lèi)的模式分開(kāi)。將某個(gè)待分類(lèi)模式 X 分別代入 M 個(gè)類(lèi)的d (X)中，若只有di(X)0，其他d(X)均0的條件超過(guò)一個(gè)，或全部的di(X)dj(X)就相當(dāng)于多類(lèi)情況2中的dij(X) 0。ji兩分法特例(3)多類(lèi)情況3： 因此對(duì)具有判別函數(shù) Midii, 1,)(TXWX的M類(lèi)情況，判別函數(shù)性質(zhì)為： ijiMjiijddXXX若, 2 , 1,;,)(或： ikiMkddXXX若, 1,max)( 識(shí)別分類(lèi)時(shí)： 判別界面需要做差值。對(duì)i類(lèi)，應(yīng)滿足： di其他所有dj2313dddd0122x1x 0

6、)(21-XdXd- 0)(31-XdXd 0)(32-XdXd3212dddd3121dddd3 除邊界區(qū)外，沒(méi)有不確定區(qū)域。特點(diǎn)： 是第二種情況的特例。由于dij(X)= di (X) dj(X) ，若在第三種情況下可分，則在第二種情況下也可分，但反過(guò)來(lái)不一定。2313dddd0122x1x 0)(21-XdXd- 0)(31-XdXd 0)(32-XdXd3212dddd3121dddd3 把 M 類(lèi)情況分成了(M -1)個(gè)兩類(lèi)問(wèn)題。并且 類(lèi)的判別界面全部與 類(lèi)的判別界面相鄰（向無(wú)窮遠(yuǎn)處延伸的區(qū)域除外）。iijj特別的定義23212211)(1)()(xdxxdxxd-XXX例例2.5

7、一個(gè)三類(lèi)模式（M=3）分類(lèi)器，其判決函數(shù)為： 試判斷X0=1,1T屬于哪一類(lèi)，且分別給出三類(lèi)的判決界面。解： 2003020102030201)()()()(1)(1111)(011)(-XXXXXXXXddddddd012)()(121-xddXX02)()(2131-xxddXX012)()(112-xddXX012)()(2132-xxddXX)()(1331XXdd-)()(2332XXdd-類(lèi)的判決函數(shù)：1判決界面如圖所示。類(lèi)的判決函數(shù)：2類(lèi)的判決函數(shù)：3- 0)(21-XdXd2313dddd0.5x2- 0)(31-XdXd 0)(32-XdXd3212dddd3121dddd1

8、10.5123x1-O2x1x 0)(21-XXdd- 0)(31-XXdd 0)(32-XXdd例例2.6 已知判決界面的位置和正負(fù)側(cè)，分析三類(lèi)模式的分布 區(qū)域 。132(1) 明確概念：線性可分。 一旦線性判別函數(shù)的系數(shù)Wk被確定以后，這些函數(shù)就可以作為模式分類(lèi)的基礎(chǔ)。3. 小結(jié)小結(jié)(2) 分法的比較：jiii與 對(duì)于M類(lèi)模式的分類(lèi)， 兩分法共需要M個(gè)判別函數(shù)，但 兩分法需要M(M-1)/2個(gè)。當(dāng)時(shí)M3時(shí)，后者需要更多個(gè)判別式（缺點(diǎn)），但對(duì)模式的線性可分的可能性要更大一些（優(yōu)點(diǎn)）。 jiii原因： 一種類(lèi)別模式的分布要比M-1類(lèi)模式的分布更為聚集， 分法受到的限制條件少，故線性可分的可能性

9、大。jiii兩分法 全部不屬任何類(lèi) IR，可能 屬于1或3 1230)(2Xd0)(3XdIR，可能 屬于3或2 -0)(1Xd0, 0312ddd0, 0321ddd0, 0,321dddIR，可能屬于1或2 0, 0213ddd2x1x若只有di(X)0，其他d(X)均 0時(shí)，原點(diǎn)在超平面的正側(cè)；wn+1 Tik XW()=1+kW( )ickXW+( )kW( )0Tik XW若( )0Tik XW若（3）分析分類(lèi)結(jié)果：只要有一個(gè)錯(cuò)誤分類(lèi)，回到（2），直至 對(duì)所有樣本正確分類(lèi)。 分類(lèi)正確時(shí)，對(duì)權(quán)向量“賞”這里用“不罰”，即權(quán)向量不變；分類(lèi)錯(cuò)誤時(shí)，對(duì)權(quán)向量“罰”對(duì)其修改，向正確的方向轉(zhuǎn)換。

10、感知器算法是一種賞罰過(guò)程：感知器算法是一種賞罰過(guò)程：3. 收斂性收斂性收斂性：經(jīng)過(guò)算法的有限次迭代運(yùn)算后，求出了一個(gè)使所有樣本都能正確分類(lèi)的W，則稱算法是收斂的?？梢宰C明感知器算法是收斂的。收斂條件：模式類(lèi)別線性可分。 例例2.8 已知兩類(lèi)訓(xùn)練樣本解：所有樣本寫(xiě)成增廣向量形式； 進(jìn)行規(guī)范化處理，屬于2的樣本乘以(1)。T11 , 0 , 0XT21 , 1 , 0XT31, 0 , 1 -XT41, 1, 1-X用感知器算法求出將模式分為兩類(lèi)的權(quán)向量解和判別函數(shù)。 :1T10,0X:2T21 ,0XT30, 1XT41 , 1X任取W(1)=0，取c=1，迭代過(guò)程為：第一輪： 0,1000 ,

11、 0 , 0) 1 (1TXWT11 , 0 , 0) 1 () 2(, 0XWW故1,1101 , 0 , 0)2(2TXWT1 , 0 , 0) 2() 3 (, 0WW故-1,1-01-1 , 0 , 0)3(3TXWT30 , 0 , 1-) 3 () 4(, 0XWW故1,1-1-1-0 , 0 , 1-)4(4TXWT0 , 0 , 1-) 4() 5 (, 0WW故有兩個(gè)WT(k)Xi 0的情況（錯(cuò)判），進(jìn)行第二輪迭代。T11T1 , 0 , 1-)5()6(,00)5(XWWXW故T2T1 , 0 , 1-(6)7(,01)6(WWXW故T33T0 , 0 , 2-)7()8(

12、,00)7(XWWXW故T4T0 , 0 , 2-)8()9(,02)8(WWXW故第二輪：T11T1 , 0 , 2-)9()10(,00)9(XWWXW故(10)11(,01)10(2TWWXW故)11()12(,01)11(3TWWXW故)12()13(,01)12(4TWWXW故第三輪：)13()14(,01)13(1TWWXW故(14)15(,01)14(2TWWXW故)15()16(,01)15(3TWWXW故)16()17(,01)16(4TWWXW故第四輪：T1 , 0 , 2-W該輪迭代的分類(lèi)結(jié)果全部正確，故解向量1()21dx -X相應(yīng)的判別函數(shù)為： 當(dāng)c、W(1)取其他值

13、時(shí)，結(jié)果可能不一樣，所以感知器算法的解不是單值的。判別界面d(X)=0如圖示。采用多類(lèi)情況3的方法時(shí)，應(yīng)有：4. 感知器算法用于多類(lèi)情況感知器算法用于多類(lèi)情況Mj, 1= iX ,)(ijddjiXX若，則 Midi, 1,對(duì)于M類(lèi)模式應(yīng)存在M個(gè)判決函數(shù)：算法主要內(nèi)容：M,21設(shè)有 M 種模式類(lèi)別： Mjj, 1,1W設(shè)其權(quán)向量初值為： 第k次迭代時(shí)，一個(gè)屬于i類(lèi)的模式樣本 X 被送入分類(lèi)器，計(jì)算所有判別函數(shù)訓(xùn)練樣本為增廣向量形式，但不需要規(guī)范化處理不需要規(guī)范化處理。 分二種情況修改權(quán)向量： Mjkkdjj, 1,TXW 若第l個(gè)權(quán)向量使 ，則相應(yīng)的權(quán)向量作調(diào)整，即： -lijkkckkckk

14、jjllii,111WWXWWXWW 可以證明：只要模式類(lèi)在情況3判別函數(shù)時(shí)是可分的，則經(jīng)過(guò)有限次迭代后算法收斂。， c為正的校正增量例例2.9 設(shè)有三個(gè)線性可分的模式類(lèi)，三類(lèi)的訓(xùn)練樣本分別為 若 則權(quán)向量不變； Mjijkdkdji, 2 , 1;, Mjkkjj, 2 , 1,1WW( )( )kdkdli T33T22T111 , 11 , 10 , 0-XXX：；：；：現(xiàn)采用多類(lèi)情況3的方式分類(lèi)，試用感知器算法求出判別函數(shù)。 解：增廣向量形式：T3T2T11,1, 1,1,1, 1,1 , 0 , 0-XXX注意，這里任一類(lèi)的樣本都不能乘以（1）。任取初始權(quán)向量T3210 , 0 ,

15、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 1222T22-XWd 1222T33-XWd22X 2212dd 2232dd，但且不成立，修改權(quán)向量：T2110 , 1, 1)2() 3(-XWWT2220 , 1 , 1)2() 3(XWWT2332, 1, 1)2

16、()3(-XWW第三次迭代： 修改為權(quán)向量。33X 3313dd 3323dd，但且不成立， 以上進(jìn)行的一輪迭代運(yùn)算中，三個(gè)樣本都未正確分類(lèi)，進(jìn)行下一輪迭代。第四次迭代： 在第五、六、七迭代中，對(duì)所有三個(gè)樣本都已正確分類(lèi)。權(quán)向量的解：T11110 , 2, 0)5()6()7(-WWWWT22222, 0 , 2)5()6()7(-WWWWT33332, 0 , 2)5()6()7(-WWWW判別函數(shù)：212)(xd-X22)(12-xdX22)(13-xdX 設(shè)函數(shù)f (Y)是向量 的函數(shù)，則f (Y)的梯度定義為：2.6 梯度法梯度法T21,nyyyY T21,ddnyfyfyfffYYY

17、梯度的方向方向是函數(shù) f (Y) 在Y點(diǎn)增長(zhǎng)最快的方向，梯度的模模是f (Y)在增長(zhǎng)最快的方向上的增長(zhǎng)率 (增長(zhǎng)率最大值)。1. 梯度概念梯度概念 梯度向量的最重要性質(zhì)之一：指出函數(shù)梯度向量的最重要性質(zhì)之一：指出函數(shù) f 在其自變量增加在其自變量增加時(shí)，增長(zhǎng)最快的方向。時(shí)，增長(zhǎng)最快的方向。2.6.1 梯度法基本原理梯度法基本原理顯然：負(fù)梯度指出了最陡下降方向負(fù)梯度指出了最陡下降方向。梯度算法的依據(jù)。即：2. 梯度算法梯度算法 設(shè)兩個(gè)線性可分的模式類(lèi)1和2的樣本共N個(gè)，2類(lèi)樣本乘(-1)。將兩類(lèi)樣本分開(kāi)的判決函數(shù)d(X)應(yīng)滿足： 梯度算法的目的仍然是求一個(gè)滿足上述條件的權(quán)向量，主導(dǎo)思想是將聯(lián)立不

18、等式求解W的問(wèn)題，轉(zhuǎn)換成求準(zhǔn)則函數(shù)極小值的問(wèn)題。Nidii, 2 , 10)(TXWXN個(gè)不等式 準(zhǔn)則函數(shù)的選取原則： 具有唯一的最小值，并且這個(gè)最小值發(fā)生在W TXi0時(shí)。 用負(fù)梯度向量的值對(duì)權(quán)向量W進(jìn)行修正，實(shí)現(xiàn)使準(zhǔn)則函數(shù)達(dá)到極小值的目的。 基本思路： 定義一個(gè)對(duì)錯(cuò)誤分類(lèi)敏感的準(zhǔn)則函數(shù)J(W, X)，在J的梯度方向上對(duì)權(quán)向量進(jìn)行修改。一般關(guān)系表示成從W(k)導(dǎo)出W(k+1)：其中c是正的比例因子。 梯度法求解步驟： JckJckk-WWW)(1 kJckkWWWXWWW-,1（1）將樣本寫(xiě)成規(guī)范化增廣向量形式，選擇準(zhǔn)則函數(shù)，設(shè)置初始權(quán)向量W(1)，括號(hào)內(nèi)為迭代次數(shù)k=1。 權(quán)向量修正為：)

19、(,)(kiJkJWWWXW )(1kJckk-WW迭代次數(shù)k加1，輸入下一個(gè)訓(xùn)練樣本，計(jì)算新的權(quán)向量，直至對(duì)全部訓(xùn)練樣本完成一輪迭代。 （3）在一輪迭代中，如果有一個(gè)樣本使 ，回到(2)進(jìn)行下 一輪迭代。否則， W不再變化，算法收斂。0J（2）依次輸入訓(xùn)練樣本X。設(shè)第k次迭代時(shí)輸入樣本為Xi，此時(shí) 已有權(quán)向量W(k)，求 ：)(kJ例例2.10 選擇準(zhǔn)則函數(shù) ， ，簡(jiǎn)單地考慮X為一維增廣模式的情況X=1，此時(shí)W=w，兩者均為標(biāo)量，XWXWXWTT),(-JwwJ-),(XW錯(cuò)誤分類(lèi)時(shí)： 22,1-wwwwwJJXXWW0010TwwXW ckckk221-WWW， 對(duì)權(quán)向量校正。 Jckk-

20、WW1正確分類(lèi)時(shí)：0010TwwXW0-wwwJ kckkWWW-01， 對(duì)權(quán)向量不做修正。說(shuō)明： 隨著權(quán)向量W向理想值接近，準(zhǔn)則函數(shù)關(guān)于W的導(dǎo)數(shù) ( )越來(lái)越趨近于零，這意味著準(zhǔn)則函數(shù)J 越來(lái)越接近最小值。當(dāng) 最終 時(shí)，J達(dá)到最小值，此時(shí)W不再改變，算法收斂。J0J 將感知器算法中聯(lián)立不等式求解W的問(wèn)題，轉(zhuǎn)換為求函數(shù)J極小值的問(wèn)題。 kJckJckkWWWXWWWW-,1 c) 梯度算法是求解權(quán)向量的一般解法，算法的具體計(jì)算形式取決于準(zhǔn)則函數(shù)J(W, X)的選擇，J(W, X)的形式不同，得到的具體算法不同。a) b) c值的選擇很重要，如c值太小，收斂太慢；但若太大，搜索又可能過(guò)頭，甚至引

21、起發(fā)散。2.6.2 固定增量法固定增量法準(zhǔn)則函數(shù)：求W(k)的遞推公式：1. 求J的梯度?,WXWJJ方法：函數(shù)對(duì)向量求導(dǎo)=函數(shù)對(duì)向量的分量求導(dǎo)，即T1,nxfxffX該準(zhǔn)則函數(shù)有唯一最小值“0”，且發(fā)生在 的時(shí)候。 0TXW設(shè) ，T211 ,nxxxXT121,nnwwwwWXWXWXWTT21),(-J部分：niniiwxw11TWWXWT111111,iniininiikniniiwxwwwxwwwxwwXT11 ,nkxxxnnddddIXXXXTT 111111TnnnnXXIWXWXWT首先求另：矩陣論中有XWXWXWTT21),(-JXXWXWXW-Tsgn21,JJ其中 -0,

22、 10, 1sgnTTTXWXWXW若若 由的結(jié)論 有： XWXWTXWXWWXWXWTTT0時(shí)，XWXWWXWXW-TTT0時(shí)，XXWWXWTTsgnXWXWXWTT21),(-J kJckJckkWWWXWWWW-,12. 求W(k+1)將 代入得： XXWXWW-)(sgn211Tkckk 0)(,0)(, 0TTXWXXWWkckk若若 XWXXW)(sgn2Tkck-XXWXWXW-Tsgn21,JJ 由此可以看出，感知器賞罰算法是梯度法的特例。即：梯度法是將感知器算法中聯(lián)立不等式求解W的問(wèn)題，轉(zhuǎn)換為求函數(shù)J極小值的問(wèn)題，將原來(lái)有多個(gè)解的情況，變成求最優(yōu)解的情況。上式即為固定增量算法

23、，與感知器賞罰算法形式完全相同 。 0)(,0)(, 01TTXWXXWWWkckkk若若即： 0, 0,1TTiiikckkkkXWXWXWWW若若只要模式類(lèi)是線性可分的，算法就會(huì)給出解。由于c是預(yù)先選定的固定值，因此叫固定增量算法。*argmax(,)J KwwwFisher判別x1x2w1H: g=0w2Fisher準(zhǔn)則的描述：用投影后數(shù)據(jù)的統(tǒng)計(jì)性質(zhì)均值和離散度的函數(shù)作為判別優(yōu)劣的標(biāo)準(zhǔn)。Fisher判別1 1,2iix KiiNmx()() , 1,2iTiiii-xSxmxm12wSSS1212()()Tb-Smmmm離散度矩陣在形式上與協(xié)方差矩陣很相似，但協(xié)方差矩陣是一種期望值，而離

24、散矩陣只是表示有限個(gè)樣本在空間分布的離散程度1, 1,2iiyimyiN2() , 1,2iiiySymi-12wSSS212()bSmm-以上定義描述d維空間樣本點(diǎn)到一向量投影的分投影的分散情況散情況，因此也就是對(duì)某向量w的投影在w上的分布。樣本離散度的定義與隨機(jī)變量方差相類(lèi)似 2121212()( )bFSmmJwSSSS-22()()()()iiiiiyTTix KTTiiix KTSSym-w xw mwwxmxwwm1212()TTwSSSSSwwww2212121212()()()()TTTbTbTSSmm-w mw mwwmmmmww12( )TbbFTwSSJwSSSwwww*

25、argmax( )FJwww*112()wS-wmmm1-m2是一向量，對(duì)與(m1-m2)平行的向量投影可使兩均值點(diǎn)的距離最遠(yuǎn)。但是如從使類(lèi)間分得較開(kāi)，同時(shí)又使類(lèi)內(nèi)密集程度較高這樣一個(gè)綜合指標(biāo)來(lái)看，則需根據(jù)兩類(lèi)樣本的分布離散程度對(duì)投影方向作相應(yīng)的調(diào)整，這就體現(xiàn)在對(duì)m1-m2 向量按Sw-1作一線性變換，從而使Fisher準(zhǔn)則函數(shù)達(dá)到極值點(diǎn)1202mmy1122012N mN mymNN1212012ln()/()22PPmmyNN-0102TTyyyyw xxw xx3.7 最小平方誤差算法最小平方誤差算法（least mean square error, LMSE；亦稱Ho-Kashyap算

26、法） 上述的感知器算法、梯度算法、固定增量算法或其他類(lèi)似方法，只有當(dāng)模式類(lèi)可分離時(shí)才收斂，在不可分的情況下，算法會(huì)來(lái)回?cái)[動(dòng)，始終不收斂。當(dāng)一次次迭代而又不見(jiàn)收斂時(shí)，造成不收斂現(xiàn)象的原因分不清，有兩種可能：a) 迭代過(guò)程本身收斂緩慢b) 模式本身不可分對(duì)可分模式收斂。對(duì)于類(lèi)別不可分的情況也能指出來(lái)。LMSE算法特點(diǎn)：1. 分類(lèi)器的不等式方程分類(lèi)器的不等式方程11121211121222221122000ddddNNdNdNa ya ya ya ya ya ya ya ya yL LL LML對(duì)對(duì)對(duì)yyy類(lèi)1類(lèi)2T0ia y 兩類(lèi)分類(lèi)問(wèn)題的解相當(dāng)于求一組線性不等式的解。如果給出分屬于 ， 兩個(gè)模式

27、類(lèi)的訓(xùn)練樣本集 ，尋找權(quán)值a應(yīng)滿足：12,1,2,iiNLy其中，yi是規(guī)范化增廣樣本向量， 。T12,1iiiinyyyLy上式分開(kāi)寫(xiě)為：1112111212222212ddNNNddNyyyabyyyabyyyab,Ya =b0b-eYab 221()NSiiiJa yb-aYab使得 SJa最小的解*a稱為最小二乘解，又稱為偽逆解或MSE解。由上式定義的準(zhǔn)則函數(shù)也稱為MSE準(zhǔn)則函數(shù)。 12()2NSiiiiJaa yb yaa-YYb0aY YY b1*a-Y YY bYb1-YY YY稱為Y的偽逆矩陣()YY Y1()-Y Y 2SJaaa-YYb使用梯度下降法作迭代式1)kkkaaa

28、b-Y (Y其中0a為任意的迭代初始值，經(jīng)過(guò)有限次迭代可得到最優(yōu)解0a1()kkkkkkkaaba yy-kyn為了進(jìn)一步減少計(jì)算量和存儲(chǔ)空間，可以使用單個(gè)樣本修正 算法，則迭代式可修正為其中迭代初始向量為任意向量，單個(gè)樣本 為滿足kkka yb的樣本。由于kbkkkayb1kk是任意給定的正常數(shù)，因此理想的逼近條件幾乎是永遠(yuǎn)不可能夠滿足的，修正過(guò)程永遠(yuǎn)不可能結(jié)束。為了保證算法的收斂性，選取使得步長(zhǎng)因子隨迭代步數(shù)的增加而逐漸減少，保證算法收斂于滿意的解 。*a 11niiiikkkb-aaa yy 1niiiikb-a yy1. 分類(lèi)器的不等式方程分類(lèi)器的不等式方程-NnNnnNNnnnnnn

29、wxwxwxwwxwxwxwwxwxwxwXXX對(duì)對(duì)對(duì)00012211212222211111122111類(lèi)1類(lèi)20TiXW 兩類(lèi)分類(lèi)問(wèn)題的解相當(dāng)于求一組線性不等式的解。如果給出分屬于 ， 兩個(gè)模式類(lèi)的訓(xùn)練樣本集 ，應(yīng)滿足：12, 2 , 1,NiiX其中，Xi是規(guī)范化增廣樣本向量， 。T21 1,iniiixxxX上式分開(kāi)寫(xiě)為：寫(xiě)成矩陣形式為 ： 令N (n+1) 的長(zhǎng)方矩陣為X，則 , 變?yōu)椋?TiXW0XW0-11112112122221112110000111NnnnnNNnNNnnwwwwxxxxxxxxx-NnNnnNNnnnnnnwxwxwxwwxwxwxwwxwxwxwXXX對(duì)

30、對(duì)對(duì)00012211212222211111122111類(lèi)1類(lèi)21,.iNL式中：T121,nnwwwwW121TT1TT2T1-nNNNiXXXXXX0XW0-11112112122221112110000111NnnnnNNnNNnnwwwwxxxxxxxxx0為零向量 感知器算法是通過(guò)解不等式組 ，求出W。0XW2. LMSE算法算法1) 原理原理的求解。式中： 兩式等價(jià)。T21,NibbbbB為各分量均為較小正值的矢量。LMSE算法把對(duì)滿足 XW 0 的求解，改為滿足BXW 在方程組系數(shù)矩陣中當(dāng)行數(shù)列數(shù)時(shí)，通常無(wú)解，稱為矛盾方程組，一般求近似解。在模式識(shí)別中，通常訓(xùn)練樣本數(shù)N總是大于模

31、式的維數(shù)n，因此方程的個(gè)數(shù)(行數(shù))模式向量的維數(shù)(列數(shù))，是矛盾方程組矛盾方程組，只能求近似解W*，即說(shuō)明：極小-BXW * LMSE算法的出發(fā)點(diǎn)：選擇一個(gè)準(zhǔn)則函數(shù)，使得當(dāng)J達(dá)到最小值時(shí)，XW=B 可得到近似解（最小二乘近似解）。 LMSE算法的思路：BWBXWXW、通過(guò)求準(zhǔn)則函數(shù)極小找求解對(duì)求解對(duì) 0轉(zhuǎn)化為轉(zhuǎn)化為準(zhǔn)則函數(shù)定義為： 221,BXWBXW-J“最小二乘”： 最?。菏狗匠探M兩邊誤差最小， 也即使J最小。 二乘：次數(shù)為2，乘了兩次最小平方（誤差算法）1111121111221111111111-NNinnnnNNnNininnbbbwwwwxxxxxxxxBXW-NNiiNNnnNn

32、NinnininnnbbbbwwxwxbwwxwxbwwxwxXWXWXWTT11T1111111111111向量各分量的平方和向量各分量的平方和-22BXW-NiiiNNbbb12T2T211T2XWXWXWBXW考察向量(XWB) 有：可以看出： 當(dāng)函數(shù)J達(dá)到最小值，等式XW=B有最優(yōu)解。即又將問(wèn)題轉(zhuǎn)化為求準(zhǔn)則函數(shù)極小值的問(wèn)題。 因?yàn)橐驗(yàn)镴有兩個(gè)變量有兩個(gè)變量W和和B，有更多的自由度供選擇求解，有更多的自由度供選擇求解，故可望改善算法的收斂速率。，故可望改善算法的收斂速率。21T22121,-NiiibJXWBXWBXWXW=B 的近似解也稱“最優(yōu)近似解”： 使方程組兩邊所有誤差之和最?。?/p>

33、即最優(yōu)）的解。準(zhǔn)則函數(shù)：BXBXXXWBXXWXBXWX#T1TTTT0-使J 對(duì)W求最小，令 ，得：2) 推導(dǎo)推導(dǎo)LMSE算法遞推公式算法遞推公式與問(wèn)題相關(guān)的兩個(gè)梯度： BXWXW-TJBXWBXWB-21J (3-46)(3-47)由(3-47)式可知：只要求出B，就可求出W。求遞推公式：(1) 求W 的遞推關(guān)系X為N(n+1)長(zhǎng)方陣，X#為(n+1) N 長(zhǎng)方陣。T1T#XXXX-稱為X的偽逆，式中： (3-45)0WJ(2) 求B(k+1)的迭代式 kJckkBBBBB-1 kkkkckkBXWBXWBB-21(3-46)代入，得cc 2 kkk-XWBe 令，定義(3-49) 1kk

34、ckkBBee(3-50)(3-46)BXWBXWB-21J利用梯度算法公式有： kJckkWWWXWWW-,1 kkBBXXXXX-#T1T kckckeXeXBX#(3) 求W(k+1)的迭代式將(3-50)代入(3-47)式W=X#B 有： kkckkkeeBXBXW#11 kkkBXWXXXeX-T1T#=0 kckeXW#0 kkkeBXW-(3-49) kkckkeeBB1(3-50) 11#BXW kkkBXWe- kckkeXWW#1 kkckkeeBB111#kkBXW總結(jié)：設(shè)初值B(1)，各分量均為正值，括號(hào)中數(shù)字代表迭代次數(shù) 。W(k+1)、B(k+1)互相獨(dú)立，先后次序

35、無(wú)關(guān)。求出B，W后，再迭代出下一個(gè)e，從而計(jì)算出新的B， W。 11#BXW kkkBXWe- kkckkeeBB1或另一算法：先算B(k+1)，再算W(k+1)。3）模式類(lèi)別可分性判別）模式類(lèi)別可分性判別 如果e(k)0 ，表明XW(k)B(k) 0， 隱含有解。繼續(xù)迭代， 可使e(k) 0 。 如果e(k)0，有解。分以下幾種情況：111-kkkBXWe kkWW1 kkee1 kkBB111#kkBXW情況分析： kkckkeeBB1e(k)0，線性可分，若進(jìn)入(5)可使e(k) 0 ，得最優(yōu)解。如果e(k)0，線性不可分，停止迭代，無(wú)解，算法結(jié)束。如果e(k)=0，線性可分，解為W(k)，算法結(jié)束。否則，說(shuō)明e(k)的各分量值有正有負(fù)，進(jìn)入(5)。 kckkeXWW#1 kkckkeeBB1 kkckkeeBB111#kkBXW(5) 計(jì)算W(k+1)和B(k+1)。方法1：分別計(jì)算方法2：先計(jì)算再計(jì)算迭代次數(shù)k加1，返回(4)。3. 算法特點(diǎn)算法特點(diǎn)(1) 算法盡管略為復(fù)雜一些，但提供了線性可分的測(cè)試特征。(2) 同時(shí)利用N