線性判別函數(shù)法

1、第第2章章 判別函數(shù)及幾何分類法判別函數(shù)及幾何分類法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ù)2.1 判別函數(shù)判別函數(shù)聚類分析法（第6章）判決函數(shù)法幾何分類法確定性事件分類（第2章）概率分類法隨機(jī)事件分類（第3章）線性判決函數(shù)法統(tǒng) 計(jì) 決 策 方 法非線性判決函數(shù)法復(fù)習(xí)與引申：復(fù)習(xí)與引申：模式識(shí)別統(tǒng)計(jì)若分屬于1，2的兩類模式可用一方程d(X) =0來(lái)劃分，那么稱d(X

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

3、X d(X) 表示的是一種分類的標(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)確定。如：已知三維線性分類 判決函數(shù)的性質(zhì)就確定了判決函數(shù) 的形式：4332211)(wxwxwxwdX3. 確定判別函數(shù)的兩個(gè)因素確定判別函數(shù)的兩個(gè)因素例：非線性判決函數(shù)2）判決函數(shù)d(X)的系數(shù)。用所給的模式樣本確定。2.2 線性判別函數(shù)線性判別函數(shù)2.2.1 線性判別函數(shù)的一般形式線性判別函數(shù)的一般形式將二

4、維模式推廣到n維，線性判別函數(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. 兩類情況d(X) = 0：不可判別情況，可以或拒絕或21XX） 對(duì)M個(gè)線性可分模式類，1， 2， M，有三種劃分方式：2. 多類情況 ii兩分法兩

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

6、ddd0122x1x 0)(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 類情況分成了(M -1)個(gè)兩類問(wèn)題。并且 類的判別界面全部與 類的判別界面相鄰（向無(wú)窮遠(yuǎn)處延伸的區(qū)域除外）。iijj特別的定義23212211)(1)()(xdxxdx

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

8、ddd3121dddd110.5123x1-O2x1x 0)(21-XXdd- 0)(31-XXdd 0)(32-XXdd例例2.6 已知判決界面的位置和正負(fù)側(cè)，分析三類模式的分布 區(qū)域 。132(1) 明確概念：線性可分。 一旦線性判別函數(shù)的系數(shù)Wk被確定以后，這些函數(shù)就可以作為模式分類的基礎(chǔ)。3. 小結(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原因： 一種類別模式的分布要比M-1類模式的分布更為聚集， 分法受到的限制條

9、件少，故線性可分的可能性大。jiii兩分法 全部不屬任何類 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）分析分類結(jié)果：只要有一個(gè)錯(cuò)誤分類，回到（2），直至 對(duì)所有樣本正確分類。 分類正確時(shí)，對(duì)權(quán)向量“賞”這里用“不罰”，即權(quán)向量不變；分類錯(cuò)誤時(shí)，對(duì)權(quán)向量“罰”對(duì)其

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

11、一輪： 0,1000 , 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 ,

12、0 , 2-)7()8(,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該輪迭代的分類結(jié)果全部正確，故解向量1()21dx -X相應(yīng)的判別函數(shù)為：

13、 當(dāng)c、W(1)取其他值時(shí)，結(jié)果可能不一樣，所以感知器算法的解不是單值的。判別界面d(X)=0如圖示。采用多類情況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)練樣本為增廣向量形式，但不需要規(guī)范化處理不需要規(guī)范化處理。 分二種情況修改權(quán)向量： Mjkkdjj, 1,TXW 若第l個(gè)權(quán)向量使 ，則相應(yīng)的權(quán)向量作調(diào)整，即：

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

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

16、2332, 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)(xd-X22)(12-xdX22)(13-xdX 設(shè)函數(shù)f (Y)是向量 的函數(shù)，則f (Y)的梯度定義為：2.6 梯度法梯度法T21,nyyyY T21,dd

17、nyfyfyfffYYY梯度的方向方向是函數(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è)線性可分的模式類1和2的樣本共N個(gè)，2類樣本乘(-1)。將兩類樣本分開(kāi)的判決函數(shù)d(X)應(yīng)滿足： 梯度算法的目的仍然是求一個(gè)滿足上述條件的權(quán)

18、向量，主導(dǎo)思想是將聯(lián)立不等式求解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ò)誤分類敏感的準(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

19、=1。 權(quán)向量修正為：)(,)(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ò)誤分類時(shí)： 22,1-wwwwwJJXXWW0010TwwXW ckckk221-WWW， 對(duì)

20、權(quán)向量校正。 Jckk-WW1正確分類時(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值太小，收斂太慢；但若太大

21、，搜索又可能過(guò)頭，甚至引起發(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-Tsg

22、n21,JJ其中 -0, 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若若只要模式類是線性可分的，算法就會(huì)給出解。由于c是預(yù)先選定的固定值，因此叫固定增量算法。n線性分類器設(shè)計(jì)任務(wù)：給定樣本集K，確定線性判別函數(shù)g(x)=wTx的各項(xiàng)系數(shù)w。步驟：1.抽取類別標(biāo)志明確的樣本集合 K=x1,x2,xN作為訓(xùn)練樣本集。2.確定一準(zhǔn)則函數(shù)J(K,w)，其值反映分類器的性能，其極值解對(duì)應(yīng)于“最好”決策。3.用最優(yōu)化技術(shù)求準(zhǔn)則函數(shù)J的極值解w*，從而確定判別函數(shù)，完成分類器設(shè)計(jì)。*argmax (,)J

24、Kwwwn對(duì)于未知樣本x，計(jì)算g(x)，判斷其類別2.7 Fisher線性判別線性判別n線性判別函數(shù)y=g(x)=wTx:n樣本向量x各分量的線性加權(quán)n樣本向量x與權(quán)向量w的向量點(diǎn)積n如果| w |=1，則視作向量x在向量w上的投影 nFisher準(zhǔn)則的基本原理：找到一個(gè)最合適的投影方向，使兩類樣本在該方向上投影之間的距離盡可能遠(yuǎn)，而每一類樣本的投影盡可能緊湊，從而使分類效果為最佳。Fisher線性判別線性判別圖例圖例Fisher判別x1x2w1H: g=0w2Fisher準(zhǔn)則的描述：用投影后數(shù)據(jù)的統(tǒng)計(jì)性質(zhì)均值和離散度的函數(shù)作為判別優(yōu)劣的標(biāo)準(zhǔn)。d維空間樣本分布的描述量維空間樣本分布的描述量Fi

25、sher判別n各類樣本均值向量mi1 1,2iix KiiNmxn樣本類內(nèi)離散度類內(nèi)離散度矩陣Si與總類內(nèi)離散度矩陣Sw ()() , 1,2iTiiii-xSxmxm12wSSSn樣本類間離散度類間離散度矩陣Sb：1212()()Tb-Smmmm離散度矩陣在形式上與協(xié)方差矩陣很相似，但協(xié)方差矩陣是一種期望值，而離散矩陣只是表示有限個(gè)樣本在空間分布的離散程度一維一維Y空間樣本分布的描述量空間樣本分布的描述量n各類樣本均值1, 1,2iiyimyiNn樣本類內(nèi)離散度和總類內(nèi)離散度2() , 1,2iiiySymi-12wSSSn樣本類間離散度 212()bSmm-以上定義描述d維空間樣本點(diǎn)到一向

26、量投影的分投影的分散情況散情況，因此也就是對(duì)某向量w的投影在w上的分布。樣本離散度的定義與隨機(jī)變量方差相類似 nFisher準(zhǔn)則函數(shù)定義的原則為，希望投影后，在一維空間中樣本類別區(qū)分清晰，即兩類距離越大越好，也就是類間離散度越大越好；各類樣本內(nèi)部密集，即類內(nèi)離散度越小越好，根據(jù)上述準(zhǔn)則，構(gòu)造Fisher準(zhǔn)則函數(shù)。2121212()( )bFSmmJwSSSS-樣本與其投影統(tǒng)計(jì)量間的關(guān)系樣本與其投影統(tǒng)計(jì)量間的關(guān)系22()()()()iiiiiyTTix KTTiiix KTSSym-w xw mwwxmxwwm1212()TTwSSSSSwwww2212121212()()()()TTTbTbT

27、SSmm-w mw mwwmmmmwwFisher準(zhǔn)則函數(shù)準(zhǔn)則函數(shù)n評(píng)價(jià)投影方向w的原則，使原樣本向量在該方向上的投影能兼顧類間分布盡可能分開(kāi)，類內(nèi)盡可能密集的要求nFisher準(zhǔn)則函數(shù)的定義：12( )TbbFTwSSJwSSSwwwwnFisher最佳投影方向的求解*argmax( )FJwwwFisher最佳投影方向的求解最佳投影方向的求解n采用拉格朗日乘子算法解決*112()wS-wmmm1-m2是一向量，對(duì)與(m1-m2)平行的向量投影可使兩均值點(diǎn)的距離最遠(yuǎn)。但是如從使類間分得較開(kāi)，同時(shí)又使類內(nèi)密集程度較高這樣一個(gè)綜合指標(biāo)來(lái)看，則需根據(jù)兩類樣本的分布離散程度對(duì)投影方向作相應(yīng)的調(diào)整，這

28、就體現(xiàn)在對(duì)m1-m2 向量按Sw-1作一線性變換，從而使Fisher準(zhǔn)則函數(shù)達(dá)到極值點(diǎn)判別函數(shù)的確定n前面討論了使Fisher準(zhǔn)則函數(shù)極大的d維向量w*的計(jì)算方法，判別函數(shù)中的另一項(xiàng)y0（閾值）可采用以下幾種方法確定：1202mmy1122012N mN mymNN1212012ln()/()22PPmmyNN-0102TTyyyyw xxw xxn分類規(guī)則:3.7 最小平方誤差算法最小平方誤差算法（least mean square error, LMSE；亦稱Ho-Kashyap算法） 上述的感知器算法、梯度算法、固定增量算法或其他類似方法，只有當(dāng)模式類可分離時(shí)才收斂，在不可分的情況下，算

29、法會(huì)來(lái)回?cái)[動(dòng)，始終不收斂。當(dāng)一次次迭代而又不見(jiàn)收斂時(shí)，造成不收斂現(xiàn)象的原因分不清，有兩種可能：a) 迭代過(guò)程本身收斂緩慢b) 模式本身不可分對(duì)可分模式收斂。對(duì)于類別不可分的情況也能指出來(lái)。LMSE算法特點(diǎn)：1. 分類器的不等式方程分類器的不等式方程11121211121222221122000ddddNNdNdNa ya ya ya ya ya ya ya ya yL LL LML對(duì)對(duì)對(duì)yyy類1類2T0ia y 兩類分類問(wèn)題的解相當(dāng)于求一組線性不等式的解。如果給出分屬于 ， 兩個(gè)模式類的訓(xùn)練樣本集 ，尋找權(quán)值a應(yīng)滿足：12,1,2,iiNLy其中，yi是規(guī)范化增廣樣本向量， 。T12,1ii

30、iinyyyLy上式分開(kāi)寫(xiě)為：5.4 最小平方誤差算法(LMSE)nLMSE方法的基本思想是將求解線性不等式組的問(wèn)題轉(zhuǎn)化為求解線性方程組：1112111212222212ddNNNddNyyyabyyyabyyyab,Ya =b0b最小平方誤差的準(zhǔn)則函數(shù)n定義誤差矢量e，用e長(zhǎng)度的平方作為準(zhǔn)則函數(shù)：-eYab 221()NSiiiJa yb-aYab使得 SJa最小的解*a稱為最小二乘解，又稱為偽逆解或MSE解。由上式定義的準(zhǔn)則函數(shù)也稱為MSE準(zhǔn)則函數(shù)。權(quán)值矢量的求解(偽逆求解法) 12()2NSiiiiJaa yb yaa-YYb0aY YY b1*a-Y YY bYb1-YY YY稱為Y的

31、偽逆矩陣()Yn如果按照式求解a*時(shí)，需要計(jì)算矩陣 及其逆矩陣 ,計(jì)算量大，通?？梢允褂锰荻认陆捣ㄒ缘姆绞角蠼狻由最小均方誤差準(zhǔn)則的梯度公式Y(jié) Y1()-Y Y 2SJaaa-YYb使用梯度下降法作迭代式1)kkkaaab-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é)束。為了保

32、證算法的收斂性，選取使得步長(zhǎng)因子隨迭代步數(shù)的增加而逐漸減少，保證算法收斂于滿意的解 。*an例: 有兩類模式的訓(xùn)練樣本：1： (0,0), (0,1) 2： (1,0), (1,1) 用LMSE算法求取判別函數(shù)，將兩類樣本分開(kāi)。權(quán)值矢量的求解(迭代求解法)1.begin initialize a(0), b, , (0), k0；2. do kk+1；3. 4. 5. until 6.return a7.end 11niiiikkkb-aaa yy 1niiiikb-a yyLMSE算法的特點(diǎn)n算法的收斂依靠(k)的衰減，一般取(k)=(1)/k；n算法對(duì)于線性不可分的訓(xùn)練樣本也能夠收斂于一個(gè)

33、均方誤差最小解；n取b=1時(shí)，當(dāng)樣本數(shù)趨于無(wú)窮多時(shí)，算法的解以最小均方誤差逼近貝葉斯判別函數(shù)； 見(jiàn)邊肇祺編寫(xiě)清華大學(xué)出版社模式識(shí)別1. 分類器的不等式方程分類器的不等式方程-NnNnnNNnnnnnnwxwxwxwwxwxwxwwxwxwxwXXX對(duì)對(duì)對(duì)00012211212222211111122111類1類20TiXW 兩類分類問(wèn)題的解相當(dāng)于求一組線性不等式的解。如果給出分屬于 ， 兩個(gè)模式類的訓(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)椋?/p>

34、0TiXW0XW0-11112112122221112110000111NnnnnNNnNNnnwwwwxxxxxxxxx-NnNnnNNnnnnnnwxwxwxwwxwxwxwwxwxwxwXXX對(duì)對(duì)對(duì)00012211212222211111122111類1類21,.iNL式中：T121,nnwwwwW121TT1TT2T1-nNNNiXXXXXX0XW0-11112112122221112110000111NnnnnNNnNNnnwwwwxxxxxxxxx0為零向量 感知器算法是通過(guò)解不等式組 ，求出W。0XW2. LMSE算法算法1) 原理原理的求解。式中： 兩式等價(jià)。T21,Nibbb

35、bB為各分量均為較小正值的矢量。LMSE算法把對(duì)滿足 XW 0 的求解，改為滿足BXW 在方程組系數(shù)矩陣中當(dāng)行數(shù)列數(shù)時(shí)，通常無(wú)解，稱為矛盾方程組，一般求近似解。在模式識(shí)別中，通常訓(xùn)練樣本數(shù)N總是大于模式的維數(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“最小二乘”： 最小：使方程組兩邊誤差最小

36、， 也即使J最小。 二乘：次數(shù)為2，乘了兩次最小平方（誤差算法）1111121111221111111111-NNinnnnNNnNininnbbbwwwwxxxxxxxxBXW-NNiiNNnnNnNinnininnnbbbbwwxwxbwwxwxbwwxwxXWXWXWTT11T1111111111111向量各分量的平方和向量各分量的平方和-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，有更多的自由度供選擇求解

37、，有更多的自由度供選擇求解，故可望改善算法的收斂速率。，故可望改善算法的收斂速率。21T22121,-NiiibJXWBXWBXWXW=B 的近似解也稱“最優(yōu)近似解”： 使方程組兩邊所有誤差之和最?。醋顑?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的偽

38、逆，式中： (3-45)0WJ(2) 求B(k+1)的迭代式 kJckkBBBBB-1 kkkkckkBXWBXWBB-21(3-46)代入，得cc 2 kkk-XWBe 令，定義(3-49) 1kkckkBBee(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)

39、 11#BXW kkkBXWe- kckkeXWW#1 kkckkeeBB111#kkBXW總結(jié)：設(shè)初值B(1)，各分量均為正值，括號(hào)中數(shù)字代表迭代次數(shù) 。W(k+1)、B(k+1)互相獨(dú)立，先后次序無(wú)關(guān)。求出B，W后，再迭代出下一個(gè)e，從而計(jì)算出新的B， W。 11#BXW kkkBXWe- kkckkeeBB1或另一算法：先算B(k+1)，再算W(k+1)。3）模式類別可分性判別）模式類別可分性判別 如果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