1、2022-4-131線性判別函數(shù)線性判別函數(shù) 問(wèn)題描述線性判別函數(shù)線性判別函數(shù) 如下圖:三類的分類問(wèn)題, 它們的邊界線就是一個(gè)判別函數(shù)判別函數(shù)包含兩類判別函數(shù)包含兩類:線性判別函數(shù):線性判別函數(shù)廣義線性判別函數(shù)(所謂廣義線性判別函數(shù)就是把非線性判別函數(shù)映射到另外一個(gè)空間變成線性判別函數(shù))分段線性判別函數(shù)非線性判別函數(shù)線性分類器的三種典型方法線性分類器的三種典型方法以Fisher準(zhǔn)則為代表的傳統(tǒng)模式識(shí)別方法以感知準(zhǔn)則函數(shù)為代表的機(jī)器自學(xué)習(xí)方法以支持向量機(jī)為代表的統(tǒng)計(jì)學(xué)習(xí)理論。分段線性判別函數(shù)分段線性判別函數(shù):近鄰法2022-4-1342022-4-1352022-4-136判別函數(shù)的形式判別函數(shù)

2、的形式模式的特征矢量：模式的特征矢量：判別函數(shù)：判別函數(shù)：稱為權(quán)矢量或系數(shù)矢量稱為權(quán)矢量或系數(shù)矢量判別函數(shù)的形式判別函數(shù)的形式增廣增廣特征矢量：特征矢量：增廣增廣權(quán)矢量：權(quán)矢量：判別函數(shù)：判別函數(shù)：兩類問(wèn)題線性判別準(zhǔn)則兩類問(wèn)題線性判別準(zhǔn)則 1020,0,0,tgwxxw xx拒識(shí)決策規(guī)則:線性分類器的分類界面線性分類器的分類界面分類界面的幾何解釋分類界面的幾何解釋1.線性分類界面H是d維空間中的一個(gè)超平面；2.分類界面將d維空間分成兩部分，R1，R2分別屬于兩個(gè)類別；3.判別函數(shù)的權(quán)矢量w是一個(gè)垂直于分類界面H的矢量，其方向指向區(qū)域R1 ；4.偏置w0與原點(diǎn)到分類界面H的距離有關(guān)：00wr w

3、多類問(wèn)題（情況一）多類問(wèn)題（情況一）每一類模式可以用一個(gè)超平面與其它類別分開(kāi)；這種情況可以把c個(gè)類別的多類問(wèn)題分解為c個(gè)兩類問(wèn)題解決，需要c個(gè)線性分類界面；第i類與其它類別之間的判別函數(shù)： tiigxa x3IR2IR1IR124IR1x2x3（1 1）二分法）二分法多類問(wèn)題（情況一）判別規(guī)則多類問(wèn)題（情況一）判別規(guī)則若存在i，使得gi(x)0， gj(x)0，ji，則判別x屬于i類；其它情況，拒識(shí)。多類問(wèn)題（情況二）多類問(wèn)題（情況二）每?jī)蓚€(gè)類別之間可以用一個(gè)超平面分開(kāi)；c個(gè)類別的問(wèn)題需要c(c-1)/2個(gè)線性分類界面；第i類與第j類之間的判別函數(shù)為： ,tijijgxa xij多類問(wèn)題（情況

4、二）判別準(zhǔn)則多類問(wèn)題（情況二）判別準(zhǔn)則如果對(duì)任意ji ，有g(shù)ij(x)0 ，則決策x屬于i。 其它情況，則拒識(shí)。231結(jié)論：判別區(qū)間增大，不確定區(qū)間減小結(jié)論：判別區(qū)間增大，不確定區(qū)間減小IRIR23( )0dx 13( )0dx 12( )0dx 1213( )0( )0dxdx3231( )0( )0dxdx2123( )0( )0dxdx（2 2）i i/ /j j二分法二分法多類問(wèn)題（情況三）多類問(wèn)題（情況三）情況三是情況二的特例，不存在拒識(shí)區(qū)域。 多類問(wèn)題（情況三）判別函數(shù)多類問(wèn)題（情況三）判別函數(shù)c個(gè)類別需要c個(gè)線性函數(shù)： 1 1220tiiiiiddigw xw xw xwxa x

5、n判別準(zhǔn)則： 1max,ijj Mgg xxix1213( )( )( )( )d xd xd xd x2123( )( )( )( )d xd xd xd x3231( )( )( )( )dxdxdxd x12312( )( )0d xd x13( )( )0d xd x23( )( )0dxdx（3 3）最大判別準(zhǔn)則）最大判別準(zhǔn)則結(jié)論：無(wú)不確定區(qū)間結(jié)論：無(wú)不確定區(qū)間v例：假設(shè)判別函數(shù)為：例：假設(shè)判別函數(shù)為：11221232()()1()dxxxdxxxdxx 問(wèn)問(wèn) 屬屬于哪一類。于哪一類。(1,1)x11221232()()1()dxxxdxxxdxx 解：解：所以所以2x三種方法小結(jié)三

6、種方法小結(jié)分類方分類方法法判別函數(shù)個(gè)判別函數(shù)個(gè)數(shù)數(shù)不確定不確定區(qū)區(qū)難易難易i i/ /i i二分法二分法i i/ /j j二分法二分法最大判最大判別準(zhǔn)則別準(zhǔn)則M MM(M-1)/2M M最多最多較少較少?zèng)]有沒(méi)有較難較難較易較易較易較易2022-4-1325判別函數(shù)的幾何意義2022-4-13262022-4-1327基本參量的定義基本參量的定義2022-4-1328基本參量的定義基本參量的定義2022-4-1329*,),(),(2121wwwxyxwywwwwxxxxiiiinni即要尋找最優(yōu)的度不同使得投影后的可分離程的方向不同顯然的直線上的投影到方向?yàn)槭鞘且粋€(gè)標(biāo)量*,)(:2 , 1)(

7、 )(:2 , 11:,:,2121)()()()2()1 (21121N2121wwwxyxwywxnmmmmSSSSimxmxSixNmmxxNNNNxxxiiiiBiijjiijjijiiijji即要尋找最優(yōu)的度不同使得投影后的可分離程的方向不同顯然的直線上的投影到方向?yàn)槭鞘且粋€(gè)標(biāo)量在以矢量維矢量作變換類間離差陣總的類內(nèi)離差陣各類的類內(nèi)離差陣各類模式的均值矢量各類的模式分別記為類類和個(gè)模式分屬于個(gè)和其中設(shè)給定的訓(xùn)練模式wwSSSSwSwSwSwwSwwSwwSwSwwSwSwwJwwSwwSwSSmmwJSSwSwmwmwmwmwmmSwSwSSSwSwmwxwmySimwNxwNymy

8、BFBFBBBjjiijiijiijijijijiiiB11BB2B2222122212122122222)(2)(2)()(存在），有：是非奇異的時(shí)候（即當(dāng):則,:令0)()( 2)( 20，令要獲得最優(yōu)的max)()(準(zhǔn)則函數(shù)：Fisher:希望投影后)()(:類間離差度)()(:類內(nèi)離差度2 ,1為：空間中各類模式的均值一維21212/)()(22取閾值：)(:變換函數(shù)Fisher)(:最佳權(quán)矢量1:令,數(shù)值我們關(guān)心的是方向而非)()(令)(:最佳判別矢量為對(duì)應(yīng)的特征矢量,個(gè)非零特征值1只有,1的秩為,兩類問(wèn)題時(shí)211212121121211*2112121211B1B1B1mmSmmm

9、wmwmwmmyxSmmymmSwmmSwwmmwmmmmSwSSwFisherwSSSStmwNNmNmNwNNmwNmwNNNmNmNyNNPNNPmmmmPPSSPSPStBw/)(,/)()()()()()(21221121221121221122112121212121取閾值：當(dāng)考慮先驗(yàn)概率時(shí)：2022-4-133521*21*211*1)()()(212121,)8(,2)7(),()6()5()4(, 2 , 1,)() 3(,2 , 11)2(|) 1 (:21XyyXwmmwymmSwSSSSSimXmXSmiXNmXXXFisherttwwwwwwjiijiijwijiji

10、ii判由得到判別門限由得到最佳解向量由的逆矩陣計(jì)算陣計(jì)算類內(nèi)總的離散度矩矩陣計(jì)算各類的類內(nèi)離散度由計(jì)算各類的均值矢量由和的兩個(gè)子集和分成的訓(xùn)練樣本集把來(lái)自兩類線性判別的算法步驟2022-4-1337類Y 則 0,YAg(Y)若類Y 則 0,YAg(Y)若:對(duì)于二類問(wèn)題有,根據(jù)判別函數(shù)的性質(zhì)的超平面 0YA 判別面YAg(Y) :線性判別函數(shù)可寫(xiě)為212022-4-1338是線性可分的則樣本,使得二類樣本分類正確A若存在解向量,顯然 解向量是不唯一的,解向量進(jìn)行了限制可見(jiàn)每個(gè)學(xué)習(xí)樣本都對(duì) 稱為解向量A滿足上述條件的向量N1,.,i 0,YA :對(duì)所有的學(xué)習(xí)樣本有使得A,找到權(quán)矢量,各學(xué)習(xí)樣本N由

11、:則二類分類問(wèn)題變?yōu)?YY 類樣本即令所有,類樣本進(jìn)行歸一化處理現(xiàn)對(duì)i222022-4-1339難的直接求解不等式組是困N1,.,i 0,YA 不等式組即是根據(jù)學(xué)習(xí)樣本求解 A,欲求解向量i2022-4-1340判別面的分割質(zhì)量越高,的值越小J(A) :它具有如下的性質(zhì)J(A),定義一個(gè)標(biāo)量函數(shù)即,函數(shù)求極值的問(wèn)題的問(wèn)題轉(zhuǎn)化為標(biāo)量準(zhǔn)則A可將求兩個(gè)問(wèn)題：兩個(gè)問(wèn)題： （1）構(gòu)造準(zhǔn)則函數(shù)）構(gòu)造準(zhǔn)則函數(shù) （2）如何最快地搜索到使準(zhǔn)則函數(shù)取）如何最快地搜索到使準(zhǔn)則函數(shù)取極小值的解極小值的解*w線性判別函數(shù)的學(xué)習(xí)線性判別函數(shù)的學(xué)習(xí) 問(wèn)題的提出：假設(shè)有一個(gè)包含n個(gè)樣本的集合y1, y2, , yn, 一些標(biāo)

12、記為1,另一些標(biāo)記為2，用這些樣本來(lái)確定一個(gè)判別函數(shù)g(x x)=a at tx x的權(quán)矢量a a。在線性可分的情況下，希望得到的判別函數(shù)能夠?qū)⑺械挠?xùn)練樣本正確分類；線性不可分的情況下，判別函數(shù)產(chǎn)生錯(cuò)誤的概率最小。訓(xùn)練樣本的規(guī)范化訓(xùn)練樣本的規(guī)范化120,0,tiitiia yya yy120,0,tiitiia yya yyn非規(guī)范化：n規(guī)范化：最優(yōu)問(wèn)題的求解：最優(yōu)問(wèn)題的求解：（1 1）一個(gè)適當(dāng)?shù)拇鷥r(jià)函數(shù)（準(zhǔn)則函數(shù)）一個(gè)適當(dāng)?shù)拇鷥r(jià)函數(shù)（準(zhǔn)則函數(shù)）（2 2）一個(gè)優(yōu)化算法）一個(gè)優(yōu)化算法 梯度下降法梯度下降法一次準(zhǔn)則函數(shù)及梯度下降法一次準(zhǔn)則函數(shù)及梯度下降法(Gradient Descent Alg

13、orithm)(Gradient Descent Algorithm)感知準(zhǔn)則函數(shù)感知準(zhǔn)則函數(shù)（RosenblattRosenblatt）可微函數(shù)在某點(diǎn)的梯度是一個(gè)向量可微函數(shù)在某點(diǎn)的梯度是一個(gè)向量 函數(shù)在該點(diǎn)的變化率最函數(shù)在該點(diǎn)的變化率最大的方向大的方向 函數(shù)函數(shù) 的梯度向量定義為的梯度向量定義為12( )( )(,.,)ndf xffff xdxxxx( )f x x YJ wJ wxw 梯度下降法的迭代公式為：梯度下降法的迭代公式為： 1kkx Yw kw kJw kx 任給定初始權(quán)矢量，第任給定初始權(quán)矢量，第k+1k+1次迭代時(shí)的權(quán)矢量等于第次迭代時(shí)的權(quán)矢量等于第k k次的權(quán)矢量加上被

14、次的權(quán)矢量加上被w w（k k）錯(cuò)分的樣本）錯(cuò)分的樣本之之和和乘乘以某個(gè)系數(shù)。以某個(gè)系數(shù)。 批量修正準(zhǔn)則函數(shù)的梯度：準(zhǔn)則函數(shù)的梯度： )0()|(|)(kxwxwkwJ將梯度下降法應(yīng)用到一次準(zhǔn)則函數(shù)中將梯度下降法應(yīng)用到一次準(zhǔn)則函數(shù)中 )sgn(21J)(xxwxwwJ0101)sgn(, 2/1xwxwxwk定義令0, 0)(, 0)()( sgn(21)()()() 1(kkkkkkkkxwxkwxwkwxxkwxkwkwJkwkw感知器算法感知器算法 把樣本集看成不斷出現(xiàn)的序列逐一考慮，稱為單樣本修正把樣本集看成不斷出現(xiàn)的序列逐一考慮，稱為單樣本修正法。法。 且令且令 ，稱為固定增量法。，

15、稱為固定增量法。 若若 使得使得1k 1kw kw kx kx0w x 11x1w112wwx12x223wwx+-+-感知器算法感知器算法(Perceptron Approach)(Perceptron Approach) 算法思想算法思想任選一初始增廣權(quán)矢量任選一初始增廣權(quán)矢量用訓(xùn)練樣本檢驗(yàn)用分類正確否用訓(xùn)練樣本檢驗(yàn)用分類正確否對(duì)進(jìn)行校正對(duì)進(jìn)行校正對(duì)所有訓(xùn)練樣本都能正確分類對(duì)所有訓(xùn)練樣本都能正確分類？ENDYesYesYesNoNo一、感知器算法一、感知器算法算法步驟：算法步驟： 增廣的訓(xùn)練樣本集增廣的訓(xùn)練樣本集 每個(gè)類別已知，每個(gè)類別已知，（1 1）令步數(shù)）令步數(shù)k=1,k=1,增量增量

16、 為正的常數(shù)，為正的常數(shù)， 的各分量為較小的任意值的各分量為較小的任意值（2 2）輸入訓(xùn)練模式）輸入訓(xùn)練模式 ，計(jì)算判別函數(shù)值，計(jì)算判別函數(shù)值（3 3）調(diào)整增廣權(quán)矢量，規(guī)則：）調(diào)整增廣權(quán)矢量，規(guī)則： （a a）如果）如果 （b b）如果）如果 （c c）如果）如果（4 4）如果）如果kNkN，令，令k=k+1k=k+1，GOTO GOTO （2 2） 如果如果k=Nk=N，則檢驗(yàn)，則檢驗(yàn) 對(duì)所有訓(xùn)練樣本是否都正確分類，是則結(jié)束，對(duì)所有訓(xùn)練樣本是否都正確分類，是則結(jié)束，否則，令否則，令k=1k=1，GOTOGOTO（2 2） ,21Nxxx21或) 1 (wkxkxkw)(kkkxkwkwxkw

17、x)() 1(, 0)(1則和kkkxkwkwxkwx)() 1(, 0)(2則和)() 1(, 0)(0)(21kwkwxkwxxkwxkkkk則和或和kxkw)(*w一、感知器算法一、感知器算法感知器算法在多類問(wèn)題中的運(yùn)行步驟：感知器算法在多類問(wèn)題中的運(yùn)行步驟： 增廣的訓(xùn)練樣本集增廣的訓(xùn)練樣本集 每個(gè)類別已知，每個(gè)類別已知，（1 1）令步數(shù)）令步數(shù)k=1,k=1,增量增量 為正的常數(shù)，為正的常數(shù)，C C個(gè)權(quán)矢量賦任意初值個(gè)權(quán)矢量賦任意初值（2 2）輸入符號(hào)未規(guī)范化的增廣訓(xùn)練模式）輸入符號(hào)未規(guī)范化的增廣訓(xùn)練模式 ，計(jì)算，計(jì)算C C個(gè)判別函數(shù)值個(gè)判別函數(shù)值（3 3）調(diào)整增廣權(quán)矢量，規(guī)則：）調(diào)整

18、增廣權(quán)矢量，規(guī)則： （a a）如果）如果 （b b）如果）如果 （4 4）如果）如果kNkN，令，令k=k+1k=k+1，GOTO GOTO （2 2） 如果如果k=Nk=N，則檢驗(yàn)，則檢驗(yàn) 對(duì)所有訓(xùn)練樣本是否都正確分對(duì)所有訓(xùn)練樣本是否都正確分類，是則結(jié)束，否則，令類，是則結(jié)束，否則，令k=1k=1，GOTOGOTO（2 2） ,21Nxxxi), 2 , 1(),1 (ciwikxkiixkwkd)()()2 , 1(),() 1(),(),()(cikwkwijxdxdxiikjkiik則和),(),() 1()() 1()() 1()(),()(lijkwkwxkwkwxkwkwilxd

19、xdxjjkllkiikiklik則和), 2 , 1( ,)(cixkwki感知器算法感知器算法(批量調(diào)整版本批量調(diào)整版本)1.begin initialize , , k02. do kk+13. 4. until 5.return a6.end 0a 1kkkkyaayY kkyyY例例有兩類模式的訓(xùn)練樣本：1： (0,0), (0,1) 2： (1,0), (1,1) 用感知器算法求取判別函數(shù)，將兩類樣本分開(kāi)。解：解：(1)(1)訓(xùn)練樣本分量增廣化及符號(hào)規(guī)范化：訓(xùn)練樣本分量增廣化及符號(hào)規(guī)范化： (2) (2) 給增廣權(quán)矢量賦任意初值給增廣權(quán)矢量賦任意初值 ，取增量，取增量 =1=1，,

20、 ) 1, 1, 1(, ) 1, 0 , 1(, ) 1 , 1 , 0(, ) 1 , 0 , 0(4321xxxx) 1 , 1 , 1 () 1 (w) 1 ()2(,01)()(,11wwxkwxdxxkkkk)2()3(,02)()(,22wwxkwxdxxkkkk)0 , 1 , 0()3()4(,02)()(,333xwwxkwxdxxkkkk) 1, 0 , 1()4()5(,01)()(,444xwwxkwxdxxkkkk)0 , 0 , 1()5()6(,01)()(,511xwwxkwxdxxkkkk) 1 , 1 , 1()6()7( ,0)()(,622xwwxkw

21、xdxxkkkk)0 , 1 , 2()7()8(,0)()(,733xwwxkwxdxxkkkk)8()9(,01)()(,84wwxkwxdxxkkkk) 1 , 1 , 2()9()10(,0)()(,911xwwxkwxdxxkkkk)10()11(,02)()(,102wwxkwxdxxkkkk)11()12(,01)()(,113wwxkwxdxxkkkk)0 , 0 , 3()12()13(,0)()(,1244xwwxkwxdxxkkkk) 1 , 0 , 3()13()14(,0)()(,1311xwwxkwxdxxkkkk)14()15(,01)()(,142wwxkwxd

22、xxkkkk)15()16(,02)()(,153wwxkwxdxxkkkk)16()17( ,02)()(,164wwxkwxdxxkkkk)17()18( ,01)()(,171wwxkwxdxxkkkk) 1 , 0 , 3(w0131 x57例題例題:已知訓(xùn)練樣本已知訓(xùn)練樣本(0,0)T1，(1,1)T2 ，(-1,1)T3, 試求解向量試求解向量w1、w2和和w3。 （2 2）運(yùn)用感知器訓(xùn)練算法。置）運(yùn)用感知器訓(xùn)練算法。置k=1k=1，增量，增量 =1=1，賦初，賦初值：值：w1 1=(0,0,0)=(0,0,0)T T, , w2 2=(0,0,0)=(0,0,0)T T, , w

23、3 3=(0,0,0)=(0,0,0)T T, ,進(jìn)行迭代運(yùn)算：進(jìn)行迭代運(yùn)算：解解:（1 1）訓(xùn)練樣本分量增廣化。將訓(xùn)練樣本變成增廣訓(xùn)）訓(xùn)練樣本分量增廣化。將訓(xùn)練樣本變成增廣訓(xùn)練模式：練模式：x1 1=(0,0,1)=(0,0,1)T T, , x2 2=(1,1,1)=(1,1,1)T T, , x3 3=(-1,1,1)=(-1,1,1)T T, , 這里的下標(biāo)恰是所屬類別，各類樣本不需符號(hào)規(guī)這里的下標(biāo)恰是所屬類別，各類樣本不需符號(hào)規(guī)范化。范化。58例題例題:已知訓(xùn)練樣本已知訓(xùn)練樣本(0,0)T1，(1,1)T2 ，(-1,1)T3, 試求解向量試求解向量w1、w2和和w3。 k=1,k=

24、1,xk k= =x1 11 1, ,因?yàn)橐驗(yàn)閐 d1 1( (x1 1)=d)=d2 2( (x1 1)=0)=0，d d1 1( (x1 1)=d)=d3 3( (x1 1)=0)=0，錯(cuò)錯(cuò)分，所以分，所以: : w1 1(2)=(2)=w1 1(1)+ (1)+ x1 1=(0,0,1)=(0,0,1)T T w2 2(2)=(2)=w2 2(1)- (1)- x1 1=(0,0,-1)=(0,0,-1)T T w3 3(2)=(2)=w3 3(1)- (1)- x1 1=(0,0,-1)=(0,0,-1)T Tk=2,xk=2,xk k=x=x2 22 2, ,因?yàn)橐驗(yàn)閐 d2 2(x

25、(x2 2)=-1d)=-1d1 1(x(x2 2)=1)=1，d d2 2(x(x2 2)=d)=d3 3(x(x2 2)=-1)=-1，錯(cuò)分，錯(cuò)分，所以所以 w w1 1(3)=w(3)=w1 1(2)- x(2)- x2 2=(-1,-1, 0)=(-1,-1, 0)T T w w2 2(3)=w(3)=w2 2(2)+ x(2)+ x2 2=( 1, 1, 0)=( 1, 1, 0)T T w w3 3(3)=w(3)=w3 3(2)- x(2)- x2 2=(-1,-1,-2)=(-1,-1,-2)T T59例題例題:已知訓(xùn)練樣本已知訓(xùn)練樣本(0,0)T1，(1,1)T2 ，(-1,

26、1)T3, 試求解向量試求解向量w1、w2和和w3。 k=3,xk=3,xk k=x=x3 33 3, ,因?yàn)橐驗(yàn)閐 d3 3(x(x3 3)=-2d)=-2d)=0d1 1(x(x2 2)=-2)=-2，d d2 2(x(x2 2)=0d)=0d3 3(x(x2 2)=-4)=-4，正確，正確，所以所以 w w1 1(6)=w(6)=w1 1(5)=( 0,-2, 0)(5)=( 0,-2, 0)T T w w2 2(6)=w(6)=w2 2(5)=( 2, 0,-2)(5)=( 2, 0,-2)T T w w3 3(6)=w(6)=w3 3(5)=(-2, 0,-2)(5)=(-2, 0,

27、-2)T Tk=6,xk=6,xk k=x=x3 33 3, ,因?yàn)橐驗(yàn)閐 d3 3(x(x3 3)=0d)=0d1 1(x(x3 3)=-2)=-2，d d3 3(x(x3 3)=0d)=0d2 2(x(x3 3)=-4)=-4，正確，正確，所以所以 w w1 1(7)=w(7)=w1 1(6)=( 0,-2, 0)(6)=( 0,-2, 0)T T w w2 2(7)=w(7)=w2 2(6)=( 2, 0,-2)(6)=( 2, 0,-2)T T w w3 3(7)=w(7)=w3 3(6)=(-2, 0,-2)(6)=(-2, 0,-2)T T61例題例題:已知訓(xùn)練樣本已知訓(xùn)練樣本(0

28、,0)T1，(1,1)T2 ，(-1,1)T3, 試求解向量試求解向量w1、w2和和w3。 k=7,xk=7,xk k=x=x1 11 1, ,因?yàn)橐驗(yàn)閐 d1 1(x(x1 1)=0d)=0d2 2(x(x1 1)=-2)=-2，d d1 1(x(x1 1)=0d)=0d3 3(x(x1 1)=-2)=-2，正確，正確，三個(gè)權(quán)矢量不再變化，因此可以確定所有訓(xùn)練樣本均已三個(gè)權(quán)矢量不再變化，因此可以確定所有訓(xùn)練樣本均已被正確分類，被正確分類，由此得到三個(gè)解矢量：由此得到三個(gè)解矢量：w1 1* *= =w1 1(5)(5)，w2 2* *= =w2 2(5)(5)，w3 3* *= =w3 3(5

29、) (5) 同時(shí)可得三個(gè)判別函數(shù)同時(shí)可得三個(gè)判別函數(shù): :d d1 1( (x) = -2) = -2x x2 2d d2 2( (x) = 2) = 2x x1 1-2-2d d3 3( (x) = -2) = -2x x1 1-2-2二次準(zhǔn)則函數(shù)及其解法二次準(zhǔn)則函數(shù)及其解法 問(wèn)題：?jiǎn)栴}： 一次準(zhǔn)則函數(shù)及其算法（如感知器算法）一次準(zhǔn)則函數(shù)及其算法（如感知器算法）只適用于線性可分的情況，如果是線性不可分只適用于線性可分的情況，如果是線性不可分的，分類過(guò)程將不收斂的，分類過(guò)程將不收斂? ? 能否找到一種算法，使之能夠測(cè)試出模能否找到一種算法，使之能夠測(cè)試出模式樣本集是否線性可分，并且對(duì)線性不可分

30、式樣本集是否線性可分，并且對(duì)線性不可分的情況也能給出的情況也能給出“次最優(yōu)次最優(yōu)”的解？的解？ 如果訓(xùn)練模式是線性不可分如果訓(xùn)練模式是線性不可分不等式組是不等式組是不一致不一致的，不等的，不等式組沒(méi)解。此時(shí)，式組沒(méi)解。此時(shí)，目標(biāo)目標(biāo)最少的訓(xùn)練模式被錯(cuò)分。最少的訓(xùn)練模式被錯(cuò)分。（一）最小錯(cuò)分模式數(shù)目準(zhǔn)則（一）最小錯(cuò)分模式數(shù)目準(zhǔn)則 對(duì)線性不可分樣本集，求一解矢量使得錯(cuò)分的模式數(shù)目最少。對(duì)線性不可分樣本集，求一解矢量使得錯(cuò)分的模式數(shù)目最少。 對(duì)于兩類問(wèn)題，設(shè)對(duì)于兩類問(wèn)題，設(shè)n+1n+1維增廣訓(xùn)練模式維增廣訓(xùn)練模式已符號(hào)規(guī)范化已符號(hào)規(guī)范化。12,Nx xx 如果訓(xùn)練模式是線性可分的，則存在權(quán)矢量如果訓(xùn)

31、練模式是線性可分的，則存在權(quán)矢量 使不等式組使不等式組w0iw x (1,2,)iN成立。成立。式中式中 是是 矩陣。矩陣。 將上面的不等式組寫(xiě)成矩陣方程形式，并引入將上面的不等式組寫(xiě)成矩陣方程形式，并引入N 維余量矢量維余量矢量 ，于是不等式方程組變?yōu)椋谑遣坏仁椒匠探M變?yōu)閎0XwbX(1)Nn121211121(1)21222(1)12(1)(1)(,)NNnnNNN nNnxxXx xxxxxxxxxxxx （二）最小方差準(zhǔn)則及（二）最小方差準(zhǔn)則及W-HW-H算法算法 針對(duì)方程組針對(duì)方程組 , ,構(gòu)造方差準(zhǔn)則函數(shù)構(gòu)造方差準(zhǔn)則函數(shù) 對(duì)于對(duì)于 , ,此時(shí)的此時(shí)的 , ,而對(duì)于而對(duì)于 , ,此

32、時(shí)的此時(shí)的 。如果方程組有唯一解。如果方程組有唯一解, ,說(shuō)說(shuō)明訓(xùn)練模式集是線性可分的明訓(xùn)練模式集是線性可分的, ,如果方程組無(wú)解如果方程組無(wú)解, ,極小點(diǎn)值是極小點(diǎn)值是最小二乘解。一般情況下使最小二乘解。一般情況下使 極小等價(jià)于誤分模式數(shù)目最極小等價(jià)于誤分模式數(shù)目最少少。Xwb( )() ()J wXwbXwb21()minNiiiw xb (1,2,)iiw xbiN min ( )0JJ wiiw xb ( )0J w J 偽逆法偽逆法 求求 對(duì)對(duì) 的梯度并令其為零，有的梯度并令其為零，有 可得可得 (3-6-12)(3-6-12) 當(dāng)當(dāng)( (X X X X) )-1-1存在時(shí)，存在時(shí)，

33、 X X + +=(=(X X X X) )-1-1X X 稱為稱為X X的偽逆的偽逆( (也稱廣義逆或也稱廣義逆或M-PM-P逆逆) )， 稱為稱為 的偽逆解。的偽逆解。X X X X是是( (n n+1)+1)( (n n+1)+1)矩陣，一般是非奇異的。矩陣，一般是非奇異的。當(dāng)當(dāng)( (X X X X) )-1-1不存在時(shí)，可用廣義逆法解不存在時(shí)，可用廣義逆法解 這里這里( (X X X X) )+ +為為X X X X的廣義逆矩陣。的廣義逆矩陣。( )J w( )2()0J wXXwbwwX XwX b1()wX XX bX bwX b()wX XX b求解最佳權(quán)矢量的方法：求解最佳權(quán)矢

34、量的方法： 梯度法梯度法( )J w( )2()J wXXwb(0)w(1)( )( )kw kw kXXw kb由前述知，由前述知， 的梯度為的梯度為梯度下降算法迭代公式為梯度下降算法迭代公式為Step1. Step1. 任取任取Step2.Step2.(3-6-13)可以證明，當(dāng)可以證明，當(dāng) 為任意正的常數(shù)，為任意正的常數(shù)，則該算法使權(quán)矢量序列則該算法使權(quán)矢量序列 收斂于收斂于 ; ; 滿足滿足 ， 也稱為也稱為MSEMSE解。解。( )w kw()0J ww11/ , kk 此算法的兩個(gè)性質(zhì)此算法的兩個(gè)性質(zhì): :1.1.當(dāng)當(dāng) 時(shí)時(shí),MSE,MSE解解 等價(jià)于等價(jià)于FisherFisher

35、解。解。2.2.令令 , ,在樣本數(shù)在樣本數(shù) 時(shí)時(shí),MSE,MSE解以最小解以最小均方誤差逼近貝葉斯判決函數(shù)均方誤差逼近貝葉斯判決函數(shù)Step1. Step1. 任取任取Step2.Step2.此算法通常稱為此算法通常稱為W WH(WidrowH(WidrowHoff)Hoff)算法算法仿前采用單樣本修正法，則式仿前采用單樣本修正法，則式(3-6-13)(3-6-13)可以修改為可以修改為1()()NkkkkXXwbw xb x (0)w(1)( )( )kkkkw kw kbw k xx1211122()NNN NNNNbN NNNN 個(gè)個(gè)w(1,1,1)bN 12( )()()BdxPxP

36、x為了減少計(jì)算量和存儲(chǔ)量，由于為了減少計(jì)算量和存儲(chǔ)量，由于(3-6-14)69H-KH-K算法算法求解最佳權(quán)矢量的方法求解最佳權(quán)矢量的方法(1)( )( )( )( )bb kb kJb kk H-KH-K算法的迭代公式為：算法的迭代公式為：)(2)(bwXJb0其中其中7071H-K算法步驟;21, 1, 0) 1 (kbStep2.Step2.置初值置初值)(1XXXXStep1.Step1.將訓(xùn)練樣本符號(hào)規(guī)范化，得將訓(xùn)練樣本符號(hào)規(guī)范化，得X X求偽逆求偽逆)()()()()(kbkwXkekbXkwStep3.Step3.計(jì)算計(jì)算72H-K算法步驟Step6. Step6. k=k+1;

37、 goto Step3; goto Step3;Step5.Step5.);)()()() 1(kekekbkb)()()() 1(kekeXkwkw)()(keXkw73742022-4-1375廣義線性判決函數(shù)2022-4-13762022-4-13772022-4-1378x21,xbxaifxbxoraxif212, 0)(, 0)(,)()()(xxdbxaifxxdbxoraxifabxbaxbxaxxd令YwYdabbawYxabybayYdyyYxyxy)(),(, 1 (,)()()1 ,(2121221成為線性可分由一維變換到二維令ix的單值實(shí)函數(shù)是式中則分類界面是線性的中

38、是線性可分的在特征空間使選取適當(dāng)?shù)暮瘮?shù)單值實(shí)函數(shù)是其中xdixfyxfxfxfyyyywwwwydywwywywywwxfwxfwxfwxdYxfxfxfydixfxxfyyyyyxxxxndYXiiddddddddddjdjjjiiidndn), 2 , 1)()1),(),(),()1 ,(),()()()()()(,)(),(),(), 2 , 1(),(,)(:),(,),(,:T21211211221112211212121nXx2)3(:12)3(12) 1(:)(:2) 1(! 2)!2(!:)(,)()(:)(21111112 nnnnnnnnxdnnnnnCnydxfywxw

39、xxwxwxdxdniinininijniniijiijiii為變換后的特征空間維數(shù)去掉常數(shù)項(xiàng)的總項(xiàng)數(shù)為上式第三項(xiàng)的項(xiàng)數(shù)為上式第二項(xiàng)的項(xiàng)數(shù)為上式第一項(xiàng)的項(xiàng)數(shù)為為線性函數(shù)可使為二次或一次式取為二次多項(xiàng)式時(shí)當(dāng)82)()()0(10 xdwxdniniixwxd11)(211122112)(iininiiiixxwxdrrrriiiniiii ininiirxxxwxd211211121)(rrnC11nC21nC183(0)1( )ndxw( )(1)( )( )( )rrrdxdxdx)()(xdr的項(xiàng)數(shù)為：的項(xiàng)數(shù)為： !)!(rnrn111rkkknC84 的維數(shù)的維數(shù) y1!)!(rnrnd

40、nsnssixxxxf2121)(rsssn21令令其中其中)()(),()()(),(.3 , 2 , 1),() 3(0),()2(),(),(),() 1 (:,),(.0,xKxdxdxKxKxxxKkxxxxxKxxKxxxxKxxxxKxxKxxxxKkkkkkkkkkkkkjiji即：可取為判決函數(shù)能夠把樣本正確分類，如果。為積累電位勢(shì)函數(shù)，表示產(chǎn)生的電位總合被稱為在任一點(diǎn)）的電位勢(shì)（所有樣本點(diǎn)數(shù)之間距離的單調(diào)下降函與是光滑函數(shù)，且是時(shí)，的距離趨于與達(dá)最大時(shí)，當(dāng)且僅當(dāng)它滿足之間的電位勢(shì)函數(shù)表示令作為區(qū)分界面的等位點(diǎn)的軌跡就可以電位為洼地電位勢(shì)能的的樣本聚集的區(qū)域形成在高地電位勢(shì)能

41、的的樣本聚集的區(qū)域形成這樣在距離越遠(yuǎn)負(fù)電位越低該點(diǎn)的負(fù)電位最大的樣本點(diǎn)為另一能源屬于距離越遠(yuǎn)正電位越低該點(diǎn)的正電位最大的樣本點(diǎn)為能源假定屬于控制勢(shì)函數(shù)的衰減速度為正常數(shù)如并可以展開(kāi)成無(wú)窮級(jí)數(shù)的對(duì)稱函數(shù)和選擇雙變量類電位勢(shì)函數(shù)第系的定義域里是正交函數(shù)在式中即對(duì)稱的有限多項(xiàng)式展開(kāi)類電位勢(shì)函數(shù)第,|sin|),(|11),(|exp),(:,:2, 2 , 1),()()(),(:,:122221kkkkkkkimikiikxxxxxxKxxxxKxxxxKxxxixxxxxK),()()(:, 0)(,),()()(:, 0)(,)()(, 0)(, 0)(,:),(2,2) 3(),(),()(

42、1,)2(0)(, 0,) 1 ()(,2122122212211212221222112212221111111021xxKxKxKxKxxxKxKxKxKxxKxKxxKxxKxxKxkxxxxKxxxKxKkxxKkxKxxxXkn則且若則且若被正確分類則且或者且若修正規(guī)則如下點(diǎn)的積累電位勢(shì)計(jì)算個(gè)樣本輸入第輸入第一個(gè)樣本置將特征空間的各點(diǎn)電位即在輸出樣本前初始化函數(shù)個(gè)樣本后的積累電位勢(shì)表示輸入令且已知樣本類別輸入訓(xùn)練樣本集訓(xùn)練過(guò)程及修正規(guī)則而不是求權(quán)矢量接提供判別函數(shù)勢(shì)函數(shù)的突出特點(diǎn)是直判別函數(shù)否則所有樣本都能正確分類若且且且且修正規(guī)則如下輸入,),()()(:) 3(,0)(,10)(,10)(,00)(,0)