模式識別課件(總順序 No7)(第三章 NO2)(李彥新)(071113)(感知器判別函數(shù))

1、3.3 感知準則函數(shù)一一.幾個基本概念幾個基本概念 1. 線性可分性線性可分性 含義：含義：若存在一個權(quán)向量權(quán)向量a(即直線)，能將樣本集按類分開將樣本集按類分開，則稱之為是線性可分的。 定義：定義：設(shè)有d維維N個樣本的樣本集個樣本的樣本集X1,X2Xn，且分別來自1和和2類類。其線性判別函數(shù)線性判別函數(shù)為： WTXi+W0其中其中 WT=W1,Wd， XiT=Xi1,Xid (i=1,N) 則其齊次式為：則其齊次式為：aTYi其中其中 aT=W0,W1,Wd=W0 W 增廣權(quán)向量增廣權(quán)向量 YiT=1,xi1,xid=1 XiT 增廣樣本向量增廣樣本向量即即Yi為為 維維(d+1維維)增廣樣

2、本向量。增廣樣本向量。d如果存在一個如果存在一個權(quán)向量權(quán)向量aT，滿足下式：滿足下式： aTY 0 則則Y 1類類 aTY 0 則則Yi1；若若aTYj 0 樣本的規(guī)范化式樣本的規(guī)范化式其中 Yi Yi 1 Yn= -Yj Yj 2 yn代表全部樣本全部樣本，其稱為規(guī)范化增廣樣本向量規(guī)范化增廣樣本向量?，F(xiàn)在的問題現(xiàn)在的問題：只要找到滿足aTYn 0 的權(quán)向量aT就行(n=1,N).4. 解向量和解區(qū)解向量和解區(qū)(1) 解向量：解向量：滿足aTYn0 (n=1,N)的權(quán)向量的權(quán)向量a稱之為解向量。(2) 權(quán)空間：權(quán)空間：由權(quán)向量組成的空間權(quán)向量組成的空間。 權(quán)向量a可視為可視為權(quán)空間中的一點一點

3、，且每個樣本每個樣本Yn對對a的可能位置都起到作用，即要求aTYn0。(3) 權(quán)空間原點的超平面：權(quán)空間原點的超平面：是由aTYn=0確定的超平面確定的超平面 n. 注意：注意： n的法向量為法向量為Yn。 N個樣本將產(chǎn)生N個超平面?zhèn)€超平面。HH(4) 解向量如果存在解向量如果存在，則必在必在 n的正側(cè)的正側(cè)（因為只有正側(cè)時才滿正側(cè)時才滿足足aTYn0）。(5) 解區(qū)：解區(qū)：由于每個超平面每個超平面把權(quán)空間分為兩個半空間兩個半空間，所以解向量如果存在，必在必在N個正半空間的交迭區(qū)個正半空間的交迭區(qū)，而且該區(qū)中的任該區(qū)中的任意向量都是解向量意向量都是解向量。因此解向量往往不只一個解向量往往不只一

4、個，而是由無窮由無窮多個解向量組成的區(qū)域多個解向量組成的區(qū)域（該區(qū)稱為解區(qū)）。對于二維問題，可看下圖（書圖4.5）。H解向量解區(qū)分界面解區(qū)解向量分界面：第一類樣本：第二類樣本（a）未規(guī)范化（b）規(guī)范化。5. 對解區(qū)的限制對解區(qū)的限制 目的是目的是：使解向量更可靠。：使解向量更可靠。 一般，越靠近越靠近解區(qū)中間解區(qū)中間的解向量，越能正確分類。的解向量，越能正確分類。 所以，引入余量引入余量 b 0 。 使使 aTYnb 的解向量即為的解向量即為限制后的解向量限制后的解向量。 而而 aTYnb0 所產(chǎn)生的所產(chǎn)生的新解區(qū)新解區(qū)位于原解區(qū)之中。位于原解區(qū)之中。 b/YnaTYnbaTYn0二二. 感知

5、準則函數(shù)及其梯度下降算法感知準則函數(shù)及其梯度下降算法1. 問題描述問題描述 設(shè)有設(shè)有一組一組d維樣本維樣本Y1,YN，其中，其中 Yn是是規(guī)范化增廣樣本向量規(guī)范化增廣樣本向量。 現(xiàn)在的問題是：現(xiàn)在的問題是：找一個解向量找一個解向量a*，使得，使得 aTYn0 ,(n=1,2,N) 為了解此線性不等式組，需構(gòu)造一個需構(gòu)造一個準則函數(shù)準則函數(shù)： 式中 是是被（增廣）權(quán)向量被（增廣）權(quán)向量a錯分類錯分類的樣本集合。的樣本集合。(因為因為當樣本Y被錯分類時，有被錯分類時，有aTY 0 或 -aTY 0，此時，此時 )kkPJYT)Ya(a)(0a)(PJ感知準則函數(shù)感知準則函數(shù)說明：說明： 是解權(quán)向量

6、a的函數(shù)的函數(shù)。 當且僅當 為空集空集時，即 時， 達到極小值。 即 或者說，當對于某個向量當對于某個向量a， 達到極小值極小值(如如“”)的話，的話，a 就是解權(quán)向量就是解權(quán)向量，這時樣本被錯分類最少樣本被錯分類最少(或或沒有沒有)，這個a就是要找的解權(quán)向量解權(quán)向量a*。 幾何上幾何上，感知準則函數(shù)正比于正比于被錯分樣本被錯分樣本到?jīng)Q策面的距決策面的距離之和離之和。 這時，就可用最優(yōu)化方法最優(yōu)化方法尋找使達到極小值的解權(quán)向量a*，為此，可采用梯度下降法求解梯度下降法求解。 k0a)(mina)(*PPJJka)(PJa)(PJa)(PJa)(PJ 函數(shù)函數(shù) 在某點某點ak的梯度的梯度 是一個

7、向量向量，它的方向與過點ak的等量面 的法線方向重合法線方向重合，指向 增加的一方增加的一方，是準則函數(shù)變化率最大的方向準則函數(shù)變化率最大的方向；反之，負梯負梯度的方向則是度的方向則是 減少得減少得最快最快的方向的方向。 所以，在求求 的極小值的極小值時，沿負梯度方向負梯度方向搜索有可能最快地找到極小值最快地找到極小值。（梯度下降法的基本思想）。a)(PJa)(PJ)a (kPJC)a (kPJa)(PJ)a (kPJ 梯度下降法的實現(xiàn)梯度下降法的實現(xiàn) 先任意給定一個初始權(quán)向量任意給定一個初始權(quán)向量a(1)，計算a(1)上的梯度上的梯度 JP ( a(1) ) ，從a(1)出發(fā)出發(fā)在最陡方向（

8、即負梯度方向）最陡方向（即負梯度方向）上移動一個距離以得到下一個權(quán)向量值移動一個距離以得到下一個權(quán)向量值a(2)，反復(fù)下去，經(jīng)過有有限步循環(huán)限步循環(huán)，就可找到解向量解向量a*，其迭代算法迭代算法如下：式中 是一個正的比例因子正的比例因子，稱為步長或增量步長或增量。a(k)(-a(k)1)a(kPkJk. 求使求使JP(a)達到極小值的解權(quán)向量達到極小值的解權(quán)向量a* 因為 JP(a)的第第k個梯度分量個梯度分量是 現(xiàn)在將將JP(a)式對式對a求梯度求梯度，這是一個標量函數(shù)對向量的求導(dǎo)一個標量函數(shù)對向量的求導(dǎo)，得如下式 將上式代入迭代式，可得 式中 是當?shù)诋數(shù)趉步迭代步迭代，用a(k)來分類時被

9、誤分類的樣本集來分類時被誤分類的樣本集。kkYPP(-Y)a(k)a(J(a)JkYYa(k)1)a(kka(k) )a(JP解釋：解釋：這種尋找解權(quán)向量的梯度下降法可描述為： 將被被a(k)誤分類的樣本之和誤分類的樣本之和并與與某個系數(shù)系數(shù) 的乘積的乘積之后，再加上加上第第k次的權(quán)向量次的權(quán)向量a(k) ，即為第（第（k+1）次的權(quán)向量）次的權(quán)向量。可證得，對于線性可分的樣本集，經(jīng)過有限步線性可分的樣本集，經(jīng)過有限步，一定可找到一個解向量一個解向量a*，即算法在有限步內(nèi)收斂有限步內(nèi)收斂，其收斂速度取決于收斂速度取決于初始權(quán)向量初始權(quán)向量a(1)和系數(shù)系數(shù) 。kk3. 感知準則函數(shù)梯度下降算法

10、感知準則函數(shù)梯度下降算法感知準則函數(shù)梯度下降算法的步驟如下：(1) 給定初始權(quán)向量給定初始權(quán)向量a(1)和步長步長 ；(2) 找出被權(quán)向量找出被權(quán)向量錯分類的樣本，錯分類的樣本，轉(zhuǎn)第轉(zhuǎn)第(3)步步；如果無錯分類如果無錯分類樣本，算法結(jié)束；樣本，算法結(jié)束；(3) 按下面的迭代公式按下面的迭代公式求新的權(quán)向量求新的權(quán)向量然后轉(zhuǎn)第然后轉(zhuǎn)第(2)步。步。kkYYa(k)1)a(kk例如：例如：設(shè)a(1)=0，=1，有3個樣本在三維下的樣本序列為：k1yy個錯分樣本。步迭代時，有）第者為錯分樣本。注：）帶kkyyyyyyyyyyyyyyy 32153214321332123211 第第1步迭代時：步迭代

11、時： a(1)=0, a(1)Tyi=0 (i=1,2,3) 故故 a(2) = a(1) y1+y2+y3第第2步迭代時：步迭代時：即用a(2)分類時，有a(2)Ty30故 a(3) a(2)y3第第3步時：步時：aT(3) y10a(4)=a(3)+ y1第第4步時：步時：aT(4) y30a(5)=a(4)+ y3第第5步時：步時：aT(5) yi0 (i=1,2,3) 故故 a(5)為解向量為解向量 。y1y3a(2)=y1+y2+y3a(4)y2a(3)a(5) a(1)3.4 最小錯分樣本數(shù)準則最小錯分樣本數(shù)準則由于感知準則函數(shù)及其梯度下降算法感知準則函數(shù)及其梯度下降算法只適用于線

12、性可分情況線性可分情況，而對于線性不可分情況線性不可分情況迭代過程將無休止，即算法不收斂算法不收斂。由于實際中，常無法事先知道樣本集是否線性可分常無法事先知道樣本集是否線性可分，所以，希望找到一種既適用于線性可分，適用于線性可分，又適用于線性不可分適用于線性不可分的方法，此方法對線性可分問題對線性可分問題，可得到一個如感知準則函數(shù)那樣的解向如感知準則函數(shù)那樣的解向量量a*，使得對兩類樣本集進行正確分類類；對兩類樣本集進行正確分類類；而對于線性不可分問對于線性不可分問題題，則得到一個使兩類樣本集使兩類樣本集錯分數(shù)目最少錯分數(shù)目最少的權(quán)向量的權(quán)向量a*。這就是所謂的最小錯分樣本數(shù)準則最小錯分樣本數(shù)

13、準則。 一一. 解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法對于2類類問題。設(shè) (=d+1)維維的N個增廣樣本向量增廣樣本向量Y=y1,yn已符號規(guī)范化符號規(guī)范化，則線性判別函數(shù)線性判別函數(shù)可寫為：g(X)=aTY。如果樣本集是線性可分的，則存在權(quán)向量線性可分的，則存在權(quán)向量a，使得aTYn 0 (n=1,2,N) 成立，成立，即不等式組是一致的不等式組是一致的，有解有解。說明說明yn能被正確分類能被正確分類。如果樣本集是非線性可分非線性可分的，表明不存在不存在a使所有的樣本被使所有的樣本被正確分類正確分類，即無論任何的無論任何的a都有某些樣本被錯分都有某些樣本被錯分。這時上述不等不等

14、式組不能成立式組不能成立，即不等式組是不一致的。不等式組無解不等式組無解。這時必必有某些樣本被錯分類有某些樣本被錯分類。因此，我們的目標應(yīng)是所求得的權(quán)向量目標應(yīng)是所求得的權(quán)向量a使盡可能多的不等式被滿足使盡可能多的不等式被滿足，即使最少的樣本被錯分使最少的樣本被錯分。d將上述不等式組寫成矩陣形式矩陣形式，另外為使解可靠為使解可靠，引入引入N維維余量向量余量向量 b 0，則不等式組不等式組可寫成： Ya b 0其中,Y是N 符號規(guī)范化增廣樣本矩陣符號規(guī)范化增廣樣本矩陣,a是是 1權(quán)向量權(quán)向量,bN1。針對我們的目標，由上式可定義如下準則函數(shù)準則函數(shù)（是一個分段分段二次函數(shù)二次函數(shù)）： Jq1(a

15、) =(Ya - b) -Ya b 2 min說明：說明： 如果如果 Ya b，則 (Ya - b) 與Ya - b的各分量分別對應(yīng)分別對應(yīng)相等相等，則Jq1(a) = 0。 如果有某些某些yi分量不滿足分量不滿足aTyibi，則分量( aTyi-bi ) 和 aTyi - bi異號異號，則Jq1(a) 0。dd顯然，不滿足不滿足不等式的（增廣）樣本樣本yi數(shù)目越少數(shù)目越少，則Jq1(a)就越小就越小。所以，使使Jq1(a)取最小值時的取最小值時的a為最優(yōu)解為最優(yōu)解a*。并且在樣本集是線性可分時線性可分時，即不等式組一致條件不等式組一致條件下，必必有有Jq1(a*) = 0，即表明用用a*構(gòu)造

16、的判別函數(shù)對所有樣本均能正確構(gòu)造的判別函數(shù)對所有樣本均能正確分類分類。而在樣本集是線性不可分時線性不可分時，即不等式組不一致條件不等式組不一致條件下，有有Jq1(a*) 0，但a*使誤分樣本數(shù)最少使誤分樣本數(shù)最少，我們稱Jq1(a)為最小錯為最小錯分樣本數(shù)準則分樣本數(shù)準則。h 共軛梯度法簡介：共軛梯度法簡介：共軛梯度法是一種改進搜索方向改進搜索方向的方法，它是為快速迭代快速迭代而形成的一種方法，它要求迭代過程應(yīng)沿梯度的共軛方向進行迭代過程應(yīng)沿梯度的共軛方向進行搜索搜索，從而得出序列解序列解的方法。具體的說，就是把前一點的梯把前一點的梯度乘以適當?shù)南禂?shù)度乘以適當?shù)南禂?shù)v，加到該點的梯度加到該點的

17、梯度上，得到新的搜索方向新的搜索方向。而“共軛共軛”是對一組向量一組向量而言。 例如例如，設(shè)X與Y是兩個d維非維非0向量向量，而Bdd是一個對稱正定矩對稱正定矩陣陣，如果有 XTBY 0 則稱X和和Y關(guān)于關(guān)于B互為共軛互為共軛。顯然，如果如果B=I(單位陣單位陣)，則，則XTBY=0，就意味著對于I互為共互為共軛的軛的X與與Y是正交的是正交的。而對稱正定矩陣對稱正定矩陣B相應(yīng)于不同特征值的兩個特征向量不同特征值的兩個特征向量X與與Y對于B是互為共軛的是互為共軛的。另若 是相對Y的特征值的特征值， 則有： XTBY = XT Y = XTY = 0共軛梯度法就是以以Ed空間中的一組對于空間中的一

18、組對于B互為共軛的向量作互為共軛的向量作為一維搜索方向為一維搜索方向，使二次正定函數(shù)二次正定函數(shù) f(X) = b0+ bTX + XTBX 達到極小值的最優(yōu)化算法達到極小值的最優(yōu)化算法，用共軛梯度法可求得共軛梯度法可求得序列序列X0,X1,X*，使得 f(X0) f(X1) f(X*)對于二次正定函數(shù)f(X)，最多用最多用d步，就可收斂于步，就可收斂于f(X)的極值解的極值解X*.4.5 最小平方誤差準則函數(shù)最小平方誤差準則函數(shù)前述法是對于所有樣本所有樣本都能滿足不等式組不等式組aTYi0(i=1,2N) ,而建立的二次準則函數(shù)二次準則函數(shù)，從而使錯分樣本數(shù)最少錯分樣本數(shù)最少。最小平方誤差準

19、則函數(shù)最小平方誤差準則函數(shù)方法，是一個基于全體樣本基于全體樣本的準則函數(shù)，它要求滿足等式滿足等式 aTYibi( i=1,N)(bi0)，這樣就可用解一組線解一組線性方程組性方程組的問題來替代原來的解一組線性不等式的問題。也就是說，適當選擇適當選擇b (0)，可以針對等式方程組針對等式方程組 Ya = b(式中Y是N 矩陣，即由規(guī)范化增廣樣本向量Yi(i=1,2,N)組成的；a是 1的增廣權(quán)向量增廣權(quán)向量；bN1) 建立二次準則函數(shù)建立二次準則函數(shù)，然后運用最優(yōu)化技術(shù)求解權(quán)向量最優(yōu)化技術(shù)求解權(quán)向量a。 ddd如果Y是非奇異矩陣是非奇異矩陣，則可得解得解a=Y-1b，但這在大多數(shù)情況下是不可能的

20、，因為一般情況，樣本數(shù)樣本數(shù)N總是大于維數(shù)總是大于維數(shù)(即N )，因此，Y是長方陣是長方陣(即行數(shù)列數(shù))，也就是說，方程式數(shù)方程式數(shù)大于未知數(shù)的數(shù)目大于未知數(shù)的數(shù)目，這是一個矛盾方程組矛盾方程組，對其通常沒有精確沒有精確解存在解存在。為此，只可能找到一個解權(quán)向量只可能找到一個解權(quán)向量a，它使Ya與b之間的誤差極小化。因此，可定義誤差向量定義誤差向量為： e=Ya-b 則求求a為最優(yōu)的方法就是使為最優(yōu)的方法就是使e為最小為最小。 所以，定義平方誤差準則函數(shù)定義平方誤差準則函數(shù)Js(a)為如下： Js(a) =e2=Ya-b2 = (aTYn- bn)2 min即求找一個使求找一個使Js(a)極小

21、化的極小化的a作為問題的解作為問題的解， 這就是矛盾方程組的最小二乘近似解最小二乘近似解，亦稱 MSE解解。ddNn 1顯然：顯然：若若aTYnbn（n=1,2,N）,則此時 Js(a)=0；若存在某些存在某些Yn使使aTYnbn，則 Js(a)0。而當b給定后給定后，可采用最優(yōu)化技術(shù)搜索搜索Js(a)極小值點以求解等式極小值點以求解等式方程組方程組Ya=b。 如果方程組有唯一解，極小值點即是該解有唯一解，極小值點即是該解。說明樣本集是樣本集是線性可分的線性可分的； 如果方程組無解，極小值點是最小二乘解無解，極小值點是最小二乘解。而使使Js(a)極小極小等價于誤分樣本數(shù)最少等價于誤分樣本數(shù)最少

22、。一一. 采用偽逆法求采用偽逆法求MSE解解 對Js(a)求導(dǎo)求導(dǎo)/梯度并令其為零梯度并令其為零 aJs(a) = 2(aTYn - bn) Yn = 2YT(Ya - b) = 0 則得： YTYa = YTb 上式即為準則函數(shù)極小化的必要條件準則函數(shù)極小化的必要條件。 (式中YTY是一個是一個 矩陣矩陣)。Nn 1dd若其為若其為非奇異非奇異(即即(YTY)-1)存在存在，則可得到a的唯一解的唯一解(用用a*表示表示)。 a* = (YTY)-1YTb =Y+b式中 Y+=(YTY)-1YT 稱為Y的偽逆的偽逆（亦稱廣義逆廣義逆或M-P逆逆）。而 a*=Y+b 稱為a的偽逆解的偽逆解（即M

23、SE解解）。 當(YTY)-1不存在不存在時，可用偽逆法解偽逆法解的： a*= (YTY)+YTb 式中(YTY)+為為YTY的偽逆陣的偽逆陣。由于求偽逆計算量較大，誤差也較大求偽逆計算量較大，誤差也較大，所以這只在解析上可行解析上可行。偽逆性質(zhì)：偽逆性質(zhì)： 當 Y為非奇異方陣非奇異方陣時，Y的偽逆和它的逆相等的偽逆和它的逆相等。 Y+Y = I 但一般一般 YY+ I二二. 采用梯度法求采用梯度法求MSE解解Js(a) 的梯度的梯度為： aJs(a)= 2YT(Ya - b)這樣可得梯度下降算法梯度下降算法為： 任意給定初始權(quán)向量任意給定初始權(quán)向量a(1)； 如果第如果第k步不能滿足：步不能

24、滿足：YT(Ya-b) = 0 則按下式求第（第（k+1）步的權(quán)向量）步的權(quán)向量a(k+1) a(k+1) = a(k) - YT(Ya(k) - b)可以證明，如果選擇如果選擇 （ 為任意正常數(shù)）為任意正常數(shù)）則該算法使權(quán)向量序列權(quán)向量序列a(1), a(2),，收斂于滿足方程Js(a)=0的權(quán)向量的權(quán)向量a*（即（即MSE解）解）。kk11k而且該方法，不論不論YTY是否為奇異矩陣是否為奇異矩陣，總能產(chǎn)生一個解總能產(chǎn)生一個解（即得有用的權(quán)向量得有用的權(quán)向量）a*，且該算法該算法只需計算只需計算 方陣(YTY),這比計算比計算 N矩陣矩陣(YTY)-1YT的計算量要小的多的計算量要小的多。為

25、了進一步減少進一步減少計算量計算量和和存儲量存儲量，由于 YT(Ya - b) = (aTYk - bk) Yk 采用類似于“感知準則函數(shù)”中的單樣本修正法單樣本修正法，將梯度下降算梯度下降算法修改為法修改為： a(1) 任意給定初值 a(k+1) = a(k) + (bk - aT(k) Yk) Yk這稱為W-H(Widrow-Hoff)算法算法。kNk 1ddd說明：說明：不論用偽逆法偽逆法還是梯度法梯度法所求得的a*都依賴于都依賴于b，當b取某些特殊值時取某些特殊值時，MSE解將具有一些特殊的性質(zhì)特殊的性質(zhì)。(1) 設(shè)N為總的樣本數(shù)，為總的樣本數(shù)，N1和和N2分別為分別為1和和2類的樣本數(shù)類的樣本數(shù)，a*1為Fisher準則函數(shù)取最大值時的解準則函數(shù)取最大值時的解。當 時MSE解解a*等價于