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

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

直接用來(lái)對(duì)模式進(jìn)行分類(lèi)的準(zhǔn)則函數(shù)。例：一個(gè)二維的兩類(lèi)判別問(wèn)題，模式分布如圖示，這些分屬于、兩類(lèi)的模式可用一直線方程來(lái)劃分。（3-1）為坐標(biāo)變量，為方程參數(shù)。式中：一、判決函數(shù)(discriminantfunction)

顏色（綠/紅）似圓度判別函數(shù)(DiscriminantFunction)將某一未知模式X代入：若，則類(lèi)；若，則類(lèi)；若，則維數(shù)=3時(shí)：判別邊界為一平面。維數(shù)>3時(shí)：判別邊界為一超平面。b)注意：對(duì)判別線正負(fù)的理解和確定。判別界面正負(fù)側(cè)的確定，是在訓(xùn)練判別函數(shù)的權(quán)值時(shí)確定的，不要和幾何上的概念混淆。表示的是一種分類(lèi)的標(biāo)準(zhǔn)，它可以是1、2、3維的，也可以是更高維的。說(shuō)明：1、判決函數(shù)的幾何性質(zhì)。它可以是線性的或非線性的函數(shù)，維數(shù)在特征提取時(shí)已經(jīng)確定。如：已知三維線性分類(lèi)——判決函數(shù)的性質(zhì)就確定了判決函數(shù)的形式：二、確定判別函數(shù)的兩個(gè)因素例：非線性判決函數(shù)2.判決函數(shù)的系數(shù)。用所給的模式樣本確定?！?.2線性判別函數(shù)一、一般形式將二維模式推廣到n維，線性判別函數(shù)的一般形式為：(3-2)式中：：權(quán)向量，即參數(shù)向量。上式也可寫(xiě)為增廣向量的形式：式中：為增廣權(quán)向量，為增廣模式向量。二、線性判決函數(shù)的性質(zhì)識(shí)別時(shí)：若1、兩類(lèi)情況：訓(xùn)練時(shí)：（=0是不可判別情況，可以）模式可為M類(lèi)，、、……、，有三種劃分方式：2、多類(lèi)情況：兩分法兩分法兩分法特例兩分法(1)用線性判別函數(shù)將屬于ωi類(lèi)的模式與其余不屬于ωi類(lèi)的模式分開(kāi)。從而訓(xùn)練出第i類(lèi)判決函數(shù)的權(quán)向量將某個(gè)待分類(lèi)模式X分別代入M個(gè)類(lèi)的d

(X)中，若只有di(X)>0，其他d(X)均<0，則判為ωi類(lèi)。判別方法判決函數(shù)的訓(xùn)練方法：對(duì)每一類(lèi)的判決函數(shù)di(X)，分別將所有已知類(lèi)別模式依次代入，有：

全部＜０不屬任何類(lèi)

IR，可能

屬于1w或3w

1w2w3w0)(2=Xd0)(3=Xd++IR，可能

屬于3w或2w

+---0)(1=Xd0,,0312<>ddd0,,0321<>ddd0,0,321<>dddIR，可能屬于1w或2w

0,,0213<>ddd2x1x+對(duì)某一模式區(qū)，的條件超過(guò)一個(gè)，或全部的，分類(lèi)失效。相當(dāng)于不確定區(qū)（IndefiniteRegion，IR）。此法將M個(gè)多類(lèi)問(wèn)題分成M個(gè)兩類(lèi)問(wèn)題，識(shí)別每一類(lèi)均需M個(gè)判別函數(shù)。在識(shí)別分類(lèi)時(shí)：例1：設(shè)有一個(gè)三類(lèi)問(wèn)題，其判別式為：現(xiàn)有一模式，試判定應(yīng)屬于哪類(lèi)？解：將代入上三式，有：三個(gè)判別界面分別為：圖示如下：步驟：a)畫(huà)出界面直線。b)判別界面正負(fù)側(cè)：找特殊點(diǎn)帶入。c)找交集。例2：已知的位置和正負(fù)側(cè)，找區(qū)域?！?)(1=Xd+0)(2=Xd+—0)(3=Xd+—2w3w1w兩分法(2)一個(gè)判別界面只能分開(kāi)兩個(gè)類(lèi)別，不能把其余所有的類(lèi)別都分開(kāi)。判決函數(shù)為：。這里在M類(lèi)模式中，與i有關(guān)的M-1個(gè)判決函數(shù)全為正時(shí)，X∈ωi。其中若有一個(gè)為負(fù)，則為IR區(qū)。則類(lèi)，而在判別類(lèi)模式時(shí)不起作用。如：對(duì)一個(gè)三類(lèi)問(wèn)題，如果、判別方法訓(xùn)練方法：與值無(wú)關(guān)。例3：一個(gè)三類(lèi)問(wèn)題，三個(gè)判決函數(shù)為：?jiǎn)柲Ｊ綄儆谀念?lèi)？解：計(jì)算得可寫(xiě)成：(4,3)分類(lèi)時(shí)：每分離出一類(lèi)，需要與I有關(guān)的M-1個(gè)判決函數(shù)；要分開(kāi)M類(lèi)模式，共需M(M-1)/2個(gè)判決函數(shù)。對(duì)三類(lèi)問(wèn)題需要3(3-1)/2=3個(gè)判決函數(shù)。即：每次從M類(lèi)中取出兩類(lèi)的組合：例4：已知的位置和正負(fù)側(cè)，找區(qū)域。兩分法特例(3)對(duì)某類(lèi)問(wèn)題有M個(gè)判決函數(shù)：即：訓(xùn)練方法：判別方法

判別界面需要做差值。對(duì)ωi類(lèi)，應(yīng)滿足di>其他所有d。最大判別準(zhǔn)則特點(diǎn)：①是第二種情況的特例。因?yàn)榭梢远x：可證明：即：若各類(lèi)別在第三種情況下可分，則在第二種情況下也可分，但反之不一定。③把M類(lèi)情況分成了M-1個(gè)兩類(lèi)問(wèn)題。并且類(lèi)的判別界面全部與類(lèi)的判別界面相鄰(向無(wú)窮遠(yuǎn)處延伸的區(qū)域除外)。②除邊界區(qū)外，沒(méi)有不確定區(qū)域。例5：一個(gè)三類(lèi)模式（M=3）分類(lèi)器，其判決函數(shù)為：且分別給出三類(lèi)的判決界面。試判斷屬于哪一類(lèi)，解：①類(lèi)的判決函數(shù)：②判決界面如圖所示。類(lèi)的判決函數(shù)：類(lèi)的判決函數(shù)：例六：已知判決界面的位置和正負(fù)側(cè)，找區(qū)域。1、明確概念：線性可分。一旦線性判別函數(shù)的系數(shù)被確定以后，這些函數(shù)就可作為模式分類(lèi)的基礎(chǔ)。三、小結(jié)2、分法的比較：對(duì)于M類(lèi)模式的分類(lèi)，兩分法共需要M個(gè)判別函數(shù)，但兩分法需要M(M-1)/2個(gè)。當(dāng)時(shí)M>3時(shí)，后者需要更多個(gè)判別式（缺點(diǎn)），但對(duì)模式的線性可分的可能性要更大一些（優(yōu)點(diǎn)）。原因：一種類(lèi)別模式的分布要比M-1類(lèi)模式的分布更為聚集，分法受到的限制條件少，故線性可分的可能性大。§3.3廣義線性判別函數(shù)1、目的：對(duì)非線性邊界面：通過(guò)某映射，把模式空間X變成X*，以便將X空間中非線性可分的模式集，變成在X*空間中線性可分的模式集。2、定義：設(shè)一訓(xùn)練用模式集，在模式空間X中線性不可分，非線性判別函數(shù)形式如下：(3.3-1)式中是模式X的單值實(shí)函數(shù)，廣義形式的模式向量定義為：(3.3-2)的形式是多種多樣的。以X為二維時(shí)，選用二次多項(xiàng)式函數(shù)為例，如原判別的函數(shù)為：這里X*空間的維數(shù)k高于X空間的維數(shù)n，則(3.3-1)式寫(xiě)成簡(jiǎn)化的向量形式：上式是線性的。討論線性判別函數(shù)并不會(huì)失去一般性的意義。(3.3-3)定義：則可將線性化為即：。§3.4感知器算法一種設(shè)計(jì)線性分類(lèi)器的算法感知器的概念感知器線性閾值單元在（2）式中，令并且令：Y＝1和Y＝－1，分別表示兩種類(lèi)型，則（2）式演變?yōu)椋簡(jiǎn)栴}：已知訓(xùn)練樣本集，求加權(quán)向量W*?！?.4感知器算法一、概念理解只要求出權(quán)向量，分類(lèi)器的設(shè)計(jì)即告完成。本節(jié)開(kāi)始介紹如何通過(guò)各種算法，利用已知類(lèi)別的模式樣本訓(xùn)練出權(quán)向量W。（2）“感知器”：對(duì)一種分類(lèi)學(xué)習(xí)機(jī)模型的稱呼，屬于有關(guān)機(jī)器學(xué)習(xí)的仿生學(xué)領(lǐng)域中的問(wèn)題，由于無(wú)法實(shí)現(xiàn)非線性分類(lèi)而下馬。但“賞罰概念（TheReward-PunishmentConcept）”今天仍在模式識(shí)別中起著很大的作用。（1）“訓(xùn)練”：對(duì)于線性判別函數(shù)，當(dāng)模式的維數(shù)知道時(shí)，判別函數(shù)的形式實(shí)際上也就定了下來(lái)，如：三維時(shí)已知兩個(gè)訓(xùn)練模式集，分屬于和，任取權(quán)向量初始值W(1)，開(kāi)始迭代。二、感器學(xué)習(xí)算法（“賞——罰”過(guò)程）1、用全部訓(xùn)練模式集進(jìn)行一輪迭代，計(jì)算的值。2、分三種情況，更新權(quán)向量的值：c為正的校正增量。（3.4-1）則分類(lèi)器對(duì)第i個(gè)模式做了①錯(cuò)誤分類(lèi)，權(quán)向量校正為：為錯(cuò)誤分類(lèi)，有：若對(duì)的樣本乘以（-1），則（3.4-2）改寫(xiě)為：（3.4-2）（3.4-3）②③若不是以上兩種情況，表明分類(lèi)正確，權(quán)向量不變，即統(tǒng)一寫(xiě)為：式中c為正的校正增量。（3.4-4）3、只要有一個(gè)樣本判別錯(cuò)誤，則進(jìn)行第二輪迭代，直至用全部模式進(jìn)行訓(xùn)練都獲得正確分類(lèi)結(jié)果，迭代結(jié)束。感知器算法是一種賞罰過(guò)程：分類(lèi)正確時(shí)，對(duì)權(quán)向量“賞”——這里用“不罰”，即權(quán)向量不變；分類(lèi)錯(cuò)誤時(shí)，對(duì)權(quán)向量“罰”——對(duì)其修改，向正確的方向轉(zhuǎn)換。三、收斂性收斂性：經(jīng)過(guò)算法的有限次迭代運(yùn)算后，求出了一個(gè)使所有樣本都能正確分類(lèi)的W，則稱算法是收斂的?？梢宰C明感知器算法是收斂的。收斂條件：模式類(lèi)別線性可分。例：用感知器算法求出將圖示模式分為兩類(lèi)的權(quán)向量解。解：將模式特征向量寫(xiě)成增廣向量形式，將屬于的訓(xùn)練樣本乘以（-1）：取c=1，。則迭代過(guò)程為：第一輪：第一輪迭代中有兩個(gè)≤0的情況（判別錯(cuò)誤的情況），進(jìn)行第二輪迭代。第二輪：第三輪：第四輪：該輪迭代的分類(lèi)全部正確，故解向量相應(yīng)的判別函數(shù)為：判別界面d(X)=0如圖示。當(dāng)c、W(1)取其他值時(shí)，結(jié)果可能不一樣，所以感知器算法的解不是單值的。將兩個(gè)模式的分類(lèi)推廣到多個(gè)模式分類(lèi)的情況，采用3.2節(jié)中介紹的多類(lèi)情況中的第三種方法，即：四、感知器算法用于多類(lèi)情況若，則對(duì)于M類(lèi)模式應(yīng)存在M個(gè)判決函數(shù)：算法推導(dǎo)：設(shè)有M種模式類(lèi)別：設(shè)其權(quán)向量初值為：一個(gè)屬于類(lèi)的模式樣本X被送入分類(lèi)器，則：1.計(jì)算出M個(gè)判決函數(shù)：②若第l個(gè)權(quán)向量使，則相應(yīng)的權(quán)向量作調(diào)整，即：可以證明：只要該模式類(lèi)別用情況三判別函數(shù)時(shí)是可分的，則該算法經(jīng)過(guò)有限次迭代后收斂。，c為一正常數(shù)。①若則權(quán)向量不變；2.判別：采用多類(lèi)情況3的方法時(shí)，應(yīng)有：4.感知器算法用于多類(lèi)情況若，則對(duì)于M類(lèi)模式應(yīng)存在M個(gè)判決函數(shù)：算法主要內(nèi)容：設(shè)有M種模式類(lèi)別：設(shè)其權(quán)向量初值為：第k次迭代時(shí)，一個(gè)屬于ωi類(lèi)的模式樣本X

被送入分類(lèi)器，計(jì)算所有判別函數(shù)訓(xùn)練樣本為增廣向量形式，但不需要規(guī)范化處理。分二種情況修改權(quán)向量：②若第l個(gè)權(quán)向量使，則相應(yīng)的權(quán)向量作調(diào)整，即：可以證明：只要模式類(lèi)在情況3判別函數(shù)時(shí)是可分的，則經(jīng)過(guò)有限次迭代后算法收斂。，c為正的校正增量例3.9設(shè)有三個(gè)線性可分的模式類(lèi)，三類(lèi)的訓(xùn)練樣本分別為①若則權(quán)向量不變；現(xiàn)采用多類(lèi)情況3的方式分類(lèi)，試用感知器算法求出判別函數(shù)。解：增廣向量形式：注意，這里任一類(lèi)的樣本都不能乘以（－1）。任取初始權(quán)向量；c=1第一次迭代：三個(gè)權(quán)向量都需要修改：，但且不成立，第二次迭代：，但且不成立，修改權(quán)向量：第三次迭代：修改為權(quán)向量。，但且不成立，以上進(jìn)行的一輪迭代運(yùn)算中，三個(gè)樣本都未正確分類(lèi)，進(jìn)行下一輪迭代。第四次迭代：……在第五、六、七迭代中，對(duì)所有三個(gè)樣本都已正確分類(lèi)。權(quán)向量的解：判別函數(shù)：設(shè)函數(shù)f(Y)是向量的函數(shù)，則f(Y)的梯度定義為：§3.5梯度學(xué)習(xí)算法即：

梯度的方向是函數(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值得到不同的等高線。由、平面所截的等高線在平面的投影為L(zhǎng)1、L2。L1上A點(diǎn)的梯度方向與函數(shù)f(X)在點(diǎn)A的法線方向一致，是函數(shù)f(X)在點(diǎn)A增長(zhǎng)最快的方向。若從高度C1到達(dá)C2，顯然，若以同樣的速率增長(zhǎng)，沿梯度方向肯定是最快到達(dá)的。顯然：負(fù)梯度指出了最陡下降方向?！荻人惴ǖ囊罁?jù)。二、梯度法設(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)立不等式求解W的問(wèn)題，轉(zhuǎn)換成求準(zhǔn)則函數(shù)極小值的問(wèn)題?！狽個(gè)不等式準(zhǔn)則函數(shù)的選取原則：具有唯一的最小值，并且這個(gè)最小值發(fā)生在W

tXi>0時(shí)。因此：尋找滿足WtXi>0的W的問(wèn)題，變?yōu)閷ふ沂笿(W,X)達(dá)到極小值的W的問(wèn)題。即通過(guò)求準(zhǔn)則函數(shù)極小值求符合要求的權(quán)向量?；舅悸罚憾x一個(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是正的比例因子。 (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)的值，求出。a)選擇初始權(quán)向量W(1)。c)按(3.5-2)式修改權(quán)向量。若對(duì)所有樣本均有，則W不再變化，算法收斂。例：選擇準(zhǔn)則函數(shù)解：不妨簡(jiǎn)單地設(shè)X=1（標(biāo)量）。此時(shí)錯(cuò)誤分類(lèi)時(shí)：，對(duì)權(quán)向量校正。正確分類(lèi)時(shí)：，對(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不再改變，算法收斂?！獙⒏兄魉惴ㄖ新?lián)立不等式求解W的問(wèn)題，轉(zhuǎn)換為求函數(shù)J極小值的問(wèn)題。b)梯度算法是求解權(quán)向量的一般解法，算法的具體計(jì)算形式取決于準(zhǔn)則函數(shù)J(W,X)的選擇，J(W,X)的形式不同，得到的具體算法不同。a)c)c值的選擇很重要，如c值太小，收斂太慢；但若太大，搜索又可能過(guò)頭，甚至引起發(fā)散。§3.6最小均（平）方誤差算法（LeastMeanSquareError,LMSE；亦稱Ho-Kashyap算法）上述的感知器算法和由梯度導(dǎo)出的固定增量算法或其他類(lèi)似方法，只是當(dāng)被分模式可分離時(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)：、分類(lèi)器的不等式方程兩類(lèi)分類(lèi)問(wèn)題的解相當(dāng)于求一組線性不等式的解。如果給出分別屬于、兩個(gè)模式的訓(xùn)練樣本集，應(yīng)滿足：若將的模式乘以（-1），則對(duì)全部模式都有：(3.6-1)設(shè)模式樣本為n維，兩類(lèi)模式的訓(xùn)練樣本總數(shù)為N個(gè)，將上式分開(kāi)寫(xiě)有：寫(xiě)成矩陣形式為：令N×(n+1)維的長(zhǎng)方矩陣為X（正體），則(3.6-1)式變?yōu)椋?3.6-2)顯然式中：為零向量。感知器算法實(shí)際就是通過(guò)(3.6-2)不等式組求出W的。(3.6-2)二、LMSE算法（H-K算法）1、原理LMSE算法把對(duì)滿足的求解，改為滿足的求解。(3.6-3)∴兩式等價(jià)。定義準(zhǔn)則函數(shù)：(3.6-4)為各分量均為正值的矢量。式中：①在方程組中，當(dāng)行數(shù)>>列數(shù)時(shí)，通常無(wú)解，稱為矛盾方程組，一般求近似解。在模式識(shí)別中，通常訓(xùn)練樣本數(shù)N總是大于模式的維數(shù)n，因此方程的個(gè)數(shù)（行數(shù)）>>模式向量的維數(shù)（列數(shù)），即方程組為矛盾方程組，通常無(wú)精確解存在，但可求最小二乘解W*，即，W*為近似解。說(shuō)明：②LMSE算法的出發(fā)點(diǎn)：選擇一個(gè)準(zhǔn)則函數(shù)，使得當(dāng)J達(dá)到最小值時(shí)，可得到近似解（最小二乘解）。③LMSE算法的思路：轉(zhuǎn)化為轉(zhuǎn)化為④使J達(dá)到最小值的解W，就是矛盾方程組的最小二乘近似解，也稱最優(yōu)近似解?！白钚《恕薄钚?：使方程組兩邊誤差最小，也即使J最小?！耍豪ㄌ?hào)的次數(shù)為2，乘了兩次；也即“最小平方（誤差算法）“最優(yōu)近似解”——使方程組兩邊所有誤差之和最?。醋顑?yōu)）的解。矢量：準(zhǔn)則函數(shù)的推導(dǎo)：從(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，有更多的自由度供選擇求解，故可望改善算法的收斂速率。(3.6-3)(3.6-4)2、推導(dǎo)LMSE算法遞推公式與問(wèn)題相關(guān)的兩個(gè)梯度：

②

1)求W的迭代式：使J對(duì)W求最小，有：③由③式可知：只要求出B，就可求出W。求遞推公式：得：令稱為X的偽逆，X為階長(zhǎng)方陣，式中：為階。①2)求B的迭代式：利用梯度法中的(3.5-2)式有：②代入：令，定義#1④3)求W(k+1)的迭代式：將④代入③式有：#2式中：②=0設(shè)初值B(1)，須使其每一分量都為正值?！璚(k+1)、B(k+1)互相獨(dú)立，均只與有關(guān)。故迭代式中也可先算B(k+1)，然后按來(lái)計(jì)算，即：……求出B、W后，再迭代出下一個(gè)，從而計(jì)算出新的B、W?？偨Y(jié)LMSE算法迭代式：③#2④#1三、模式類(lèi)別可分性的判別及算法的特點(diǎn)：（一）可分性判別②如果，這時(shí)隱含，有解。如繼續(xù)迭代，可使。③如果的所有分量為負(fù)數(shù)或零（但不是全部為零），停止迭代，無(wú)解。此時(shí)若繼續(xù)迭代下去，數(shù)據(jù)不再發(fā)生變化。

可以證明：當(dāng)模式類(lèi)線性可分，且校正系數(shù)c滿足時(shí)，該算法收斂，可求得解W。理論上不能證明該算法到底需要迭代多少步才能達(dá)到收斂，通常在每次迭代計(jì)算后檢查一下和誤差向量，從而可以判斷是否收斂。①如果或（即），有解。分以下幾種情況：關(guān)于③的說(shuō)明：通過(guò)反證法可以證明：在線性可分情況下，算法進(jìn)行過(guò)程中不會(huì)出現(xiàn)的分量全為負(fù)的情況；若出現(xiàn)的分量全為負(fù)，則說(shuō)明模式類(lèi)線性不可分。b)所有分量為非正，繼續(xù)迭代數(shù)據(jù)無(wú)變化的情況分析：③如果的所有分量為負(fù)數(shù)或零（但不是全部為零），停止迭代，無(wú)解。此時(shí)若繼續(xù)迭代下去，數(shù)據(jù)不再發(fā)生變化。或綜上所述：只有當(dāng)中有大于零的分量時(shí)，才需要繼續(xù)迭代，一旦的全部分量只有0和負(fù)數(shù)，則立即停止。事實(shí)上，往往早在全部分量都達(dá)到非正值以前，就能看出其中有些分量向正值變化得極慢，可及早采取對(duì)策。（二）算法特點(diǎn)除了對(duì)可分模式是收斂的以外，對(duì)于線性不可分的模式，在算法迭代過(guò)程中就可明確的表示出來(lái)。例1：已知兩類(lèi)模式訓(xùn)練樣本：解：1）寫(xiě)出增廣矩陣：2）求偽逆矩陣求逆矩陣：若，則是的代數(shù)余子式，注意兩者的行和列的標(biāo)號(hào)互換。|A|——A的行列式A*——A的伴隨矩陣代數(shù)余子式定義：劃去aij所在的行和列的元素，余下元素構(gòu)成的行列式做aij的余子式，記作Mij，將叫做元素aij的代數(shù)余子式。例：行列式:3）開(kāi)始迭代：取和c=1.故W(1)就是解，即判斷函數(shù)為：圖示如下：例2：已知模式訓(xùn)練樣本：2）求：解：1）增廣矩陣：3）迭代：取和c=1.全部分量為負(fù)，無(wú)解，停止迭代。為線性不可分模式。

可以看出：2）算法盡管略為復(fù)雜一些，但它提供了線性可分的測(cè)試特征，并且收斂速度也比前面的梯度法（包括感知器算法）要快一些。1）LMSE算法的明顯缺點(diǎn)是需要對(duì)矩陣求逆，好在一個(gè)分類(lèi)問(wèn)題，只要進(jìn)行一次求逆。此外，當(dāng)新的一行加入X中時(shí)（即新的模式樣本加入），逆矩陣有迭代算法。小結(jié)：1、感知器法、梯度法、最小平方誤差算法討論的分類(lèi)算法都是通過(guò)模式樣本來(lái)確定判別函數(shù)的系數(shù)，所以要使一個(gè)分類(lèi)器設(shè)計(jì)完善，必須采用有代表性的數(shù)據(jù)，訓(xùn)練判別函數(shù)的權(quán)系數(shù)。它們能合理反映模式數(shù)據(jù)的總體。2、要獲得一個(gè)有較好判別性能的線性分類(lèi)器，所需要的訓(xùn)練樣本的數(shù)目的確定。用指標(biāo)二分能力Ck來(lái)決定訓(xùn)練樣本的數(shù)目：通常訓(xùn)練樣本的數(shù)目不能低于Ck，選為Ck的10~20倍左右。二維：不能低于6個(gè)樣本，最好選在60~120個(gè)樣本之間。三維：不能低于8個(gè)樣本，最好選在80~160個(gè)樣本之間。k為模式維數(shù)如復(fù)習(xí)：LMSE算法1、算法過(guò)程①由已知類(lèi)別的樣本寫(xiě)出增廣矩陣X，求出，設(shè)B(1)、c初值，B(1)每一分量必須全為正值