模式識別課件第四章線性判別函數(shù)1

1、第四章第四章 線性判別函數(shù)線性判別函數(shù)nbayesian分類器設計方法，已知n類條件概率密度 p(x|i) 參數(shù)表達式n先驗概率 p(i) n利用樣本估計 p(x| i) 的未知參數(shù)n用貝葉斯規(guī)則將其轉換成后驗概率 p(i|x) ，并根據(jù)后驗概率的大小進行分類決策。解決實際問題方法解決實際問題方法n在實際中存在問題n樣本特征空間的類條件概率密度形式常常很難確定n利用 parzen 窗等非參數(shù)方法恢復分布往往需要大量樣本，而且隨著特征空間維數(shù)的增加所需樣本數(shù)急劇增加。n因此，在解決實際問題時，往往是利用樣本集直接設計分類器，而不恢復類條件概率密度。n即采用判別函數(shù)，首先給定某個判別函數(shù)類，然后利

2、用樣本集確定出判別函數(shù)中的未知參數(shù)。線性判別函數(shù)線性判別函數(shù)n線性判別函數(shù)法是一類較為簡單的判別函數(shù)。是統(tǒng)計模式識別的基本方法之一。n它首先假定判別函數(shù) g(x) 是 x 的線性函數(shù)，即 g(x)=wtx+ w0 ，對于 c 類問題，可以定義 c 個判別函數(shù)， gi(x)=witx+ wi0 ， i=1,2 ， c 。n用樣本去估計各 wi 和 wi0 ，并把未知樣本 x 歸到具有最大判別函數(shù)值的類別中去。n關鍵是如何利用樣本集求得 wi 和 wi0 。訓練和學習訓練和學習n“訓練”和“學習” n在待識別的模式中，挑選一批有代表性的樣本，經(jīng)過人工判讀，成為已知分類的樣本，把這批樣本逐個輸入到計

3、算機中的“訓練”程序或算法中，通過一次次的迭代，最后得到正確的線性判別函數(shù)。n這樣的迭代過程稱之為訓練過程，所構成的分類器稱為有人監(jiān)督或有教師的分類器。n在正態(tài)分布的bayesian判別中，已經(jīng)遇到過在兩類情況下判別函數(shù)為線性的情況。n假設有1 和2 兩類模式，在二維模式特征空間可用一直線把這兩類模式劃分開，如圖 4.1 所示。x1x2g(x) = w2x2+w1x1+w0 圖4.1兩類模式的一個簡單判別函數(shù)+劃分直線的方程參數(shù)坐標變量4.1.1 線性判別函數(shù)的基本概念線性判別函數(shù)的基本概念判別規(guī)則判別規(guī)則n若給定一個未知類別的模式xn當g(x)0 時，則決策 x 屬于1 ；n當 g(x)0，

4、所以決策面的法向量是指向 r1 的。n因此，有時稱 r1 中的任何 x 在 h 的正側，相應地，稱 r2 中的任何 x 在 h 的負側。4.1.1 線性判別函數(shù)的基本概念線性判別函數(shù)的基本概念判別函數(shù)判別函數(shù) g(x) 是特征空間中某點是特征空間中某點 x 到超平到超平面距離的一種代數(shù)量度。面距離的一種代數(shù)量度。n若把 x 表示成式中 xp ：是 x 在 h 上的投影向量； r ：是 x 到 h 的垂直距離；wwxxrpww：是w方向上的單位向量。wwwwxwwwxwxttrrwwr0p0pt)()(g4.1.1 線性判別函數(shù)的基本概念線性判別函數(shù)的基本概念若 x 為原點，則 g(x)=w0

5、(4-7)將 (4-7) 代入 (4-6) ，就得到從原點到超平面 h 的距離w)x(gr (4-6) w0wr 判別函數(shù)判別函數(shù) g(x) 是特征空間中某點是特征空間中某點 x 到超平到超平面距離的一種代數(shù)量度。面距離的一種代數(shù)量度。4.1.1 線性判別函數(shù)的基本概念線性判別函數(shù)的基本概念w0wr 如果 w00 ，則原點在 h 的正側；若 w00 ，則原點在 h 的負側。若w0=0 ，則 g(x) 具有齊次形式 wtx ，說明超平面 h 通過原點。判別函數(shù)判別函數(shù) g(x) 是特征空間中某點是特征空間中某點 x 到超平到超平面距離的一種代數(shù)量度。面距離的一種代數(shù)量度。4.1.1 線性判別函數(shù)

6、的基本概念線性判別函數(shù)的基本概念圖 4.2 對這些結果作了幾何解釋。4.1.1 線性判別函數(shù)的基本概念線性判別函數(shù)的基本概念結論結論n利用線性判別函數(shù)進行決策，就是用一個超平面把特征空間分割成兩個決策區(qū)域。n超平面的方向由權向量 w 確定，它的位置由閾值權 w0 確定。n判別函數(shù) g(x) 正比于 x 點到超平面的代數(shù)距離（帶正負號）當 x 在 h 正側時， g(x) 0 ，在負側時， g(x) 0 。4.1.1 線性判別函數(shù)的基本概念線性判別函數(shù)的基本概念n如圖 4.3 所示的二類問題。n設有一維樣本空間 x ，所希望的劃分是：n如果 xa ，則 x 屬于1 類；n如果 b x0 ，則決策

7、x1g(x)0 ，則決策 x2二次判別函數(shù)可寫成如下一般形式g(x)=c0+c1x+ c2x2(4-10)如果適當選擇 x y 的映射，則可把二次判別函數(shù)化為 y 的線性函數(shù)31)(iiityagyax4.1.2 廣義線性判別函數(shù)廣義線性判別函數(shù)式中式中213211xxyyyy210321cccaaaayaxtg)(稱為廣義判別函數(shù)，a叫做廣義權向量。 一般地，對于任意高次判別函數(shù) g(x)(這時的 g(x) 可看作對任意判別函數(shù)作級數(shù)展開，然后取其截尾部分的逼近)，都可以通過適當?shù)淖儞Q，化為廣義線性判別函數(shù)來處理。31)(iiityagyax4.1.2 廣義線性判別函數(shù)廣義線性判別函數(shù)存在問

8、題存在問題n經(jīng)過變換后，維數(shù)大大增加了，這將使問題很快陷入所謂“維數(shù)災難”。n在統(tǒng)計學習理論中，對廣義線性分類器進行研究，克服了“維數(shù)災難”問題，進而發(fā)展出了最新的模式識別方法支持向量機，成為解決有限樣本情況下非線性分類問題的有效手段。4.1.2 廣義線性判別函數(shù)廣義線性判別函數(shù)n把 (4-1) 式定義的線性判別函數(shù)寫成下面的形式xy1121dxxxwa0210wwwwwd1 ddyaxtdiiidiiiyaxwwg110)(4-12)增廣特征向量augmented feature vector增廣權向量(廣義權向量)augmented weight vector4.1.2 廣義線性判別函數(shù)廣

9、義線性判別函數(shù)結論結論ny 與 x 相比，雖然增加了一維，但保持了樣本間的歐氏距離不變，變換后的樣本向量仍然全部位于 d 維子空間，即原 x 空間中，方程0yat(4-13)在y空間確定了一個通過原點的超平面 。h它對 d 維子空間的劃分與原決策面 wtx+ w0=0 對原 x 空間的劃分完全相同。4.1.2 廣義線性判別函數(shù)廣義線性判別函數(shù)例子例子n這種方法的優(yōu)缺點可通過例子來說明?？紤]二次判別函數(shù)2321)(xaxaaxg得到三維向量y21xxy從x到y(tǒng)的映射如圖所示。4.1.2 廣義線性判別函數(shù)廣義線性判別函數(shù)例子例子4.1.2 廣義線性判別函數(shù)廣義線性判別函數(shù)數(shù)據(jù)仍保持固有的一維，因為

10、改變x將導致y沿著一個三維曲線運動。如果x服從某一個概率分布時，得到的密度函數(shù)是退化的，即曲線之外是0，在曲線上是無窮大，這是從低維空間到高維空間映射的普遍問題。例子例子4.1.2 廣義線性判別函數(shù)廣義線性判別函數(shù)圖中映射y=(1,x,x2)t把一條直線映射為三維空間中的一條拋物線。由于兩類問題，在三維空間中，一個平面就是一個分隔面。因此，由圖可見，這產生了原始一維x空間的不連通性例子例子g(x)=1+x+ 2x2x0.5時g(x)0a=(-1, 1,2)t4.1.2 廣義線性判別函數(shù)廣義線性判別函數(shù)由aty=0定義的平面將y空間分成兩個判別區(qū)域，如圖給出當a=(-1,1,2)t時的分類平面和

11、x空間對應的判別區(qū)域。結論結論aty=0在2維空間不穿過原點4.1.2 廣義線性判別函數(shù)廣義線性判別函數(shù)一個三維增廣特征空間y和增廣權向量a(在原點)。滿足aty=0的點集是一個穿過y空間原點的超平面(用紅色表示)，這個平面垂直于a。這個平面在其原來的二維空間中不一定穿過原點(即立方體頂部虛線所示的判決邊界)。因此存在一個增廣權向量a，可以獲得x空間中任意的判定線。設計線性分類器，就是建立線性判別函數(shù)(4-l)式g(x) =wtx+w0或廣義線性判別函數(shù)(4-12)式y(tǒng)axtg)(這樣，設計線性分類器就轉化為，利用訓練樣本集尋找準則函數(shù)的極值點 和 或 。*a*w*0w設計線性分類器的主要步驟

12、如下：設計線性分類器的主要步驟如下：n 要有一組具有類別標志的樣本集x=x1，x2，xn。n如果在樣本 xn 抽出后，把它看作一個確定的觀察值，則這組樣本集稱為確定性樣本集；n若把 xn 看作一個隨機變量，則這組樣本集稱為隨機樣本集。n有時也將樣本集 x 轉換成增廣樣本集 y 來處理。4.1.3 設計線性分類器的主要步驟設計線性分類器的主要步驟n 要根據(jù)實際情況確定一個準則函數(shù) j 它必須滿足： j 的值反映分類器的性能，它的極值解則對應于 最好 的決策。 j是樣本集x和w、w0或 a 的函數(shù)；設計線性分類器的主要步驟如下：設計線性分類器的主要步驟如下：4.1.3 設計線性分類器的主要步驟設計

13、線性分類器的主要步驟*0*)(wgtxwx*0w用最優(yōu)化技術求出準則函數(shù)的極值解 和 w*或a*。這樣就可以得到線性判別函數(shù)yaxtg*)(或設計線性分類器的主要步驟如下：設計線性分類器的主要步驟如下：4.1.3 設計線性分類器的主要步驟設計線性分類器的主要步驟nfisher線性判別函數(shù)是經(jīng)典判別方法之一，應用非常廣泛。n應用統(tǒng)計方法解決模式識別問題時，困難之一是維數(shù)問題。n在低維空間里行得通的方法，在高維空間里往往行不通。n因此，降低維數(shù)有時就成為處理實際問題的關鍵。n在數(shù)學上通?？梢园?d 維空間的樣本投影到一條直線上，形成一維空間，即把維數(shù)壓縮到一維。n在一般情況下，總可以找到某個方向，

14、使在這個方向的直線上，樣本的投影能分開得最好。n問題是如何根據(jù)實際情況找到這條最好的、使最易于分類的投影線。這就是fisher法所要解決的基本問題 (見圖 4.4) 。4.2 fisher線性判別線性判別4.2 fisher線性判別線性判別從從 d 維空間到一維空間的數(shù)學變換方法維空間到一維空間的數(shù)學變換方法n假設有一集合 x 包含 n 個 d 維樣本 x1 ， x2 ，xn ，其中 n1 個屬于1 類的樣本記為子集 x1 ，n2 個屬于2 類的樣本記為 x2 ，若對 xn 的分量作線性組合可得標量yn=wtxn, n=1 ， 2 ， nin這樣便得到 n 個一維樣本 yn 組成的集合，并可分

15、為兩個子集 y1 和 y2 。4.2 fisher線性判別線性判別w* 就是最好的投影方向n從幾何上看，如果 |w|=1 ，則每個 yn 就是相對應的 xn 到方向為 w 的直線上的投影，實際上，w 的絕對值是無關緊要的，它僅使 yn 乘上一個比例因子，重要的是選擇 w 的方向。nw 的方向不同，將使樣本投影后的可分離程度不同，從而直接影響識別效果。n因此，前述所謂尋找最好投影方向的問題，在數(shù)學上就是尋找最好的變換向量 w*的問題。4.2 fisher線性判別線性判別定義幾個基本參量定義幾個基本參量n在 d 維 x 空間n各類樣本均值向量miixxiinxm1， i =1，2 n樣本類內離散度

16、矩陣 si 和總類內離散度矩陣 swixxtiiis)(mxmx，i =1，2 sw=s1+ s24.2 fisher線性判別線性判別n樣本類間離散度矩陣sbsb=(m1 m2)(m1 m2)tn其中 sw 是對稱半正定矩陣，而且當 nd 時通常是非奇異的。nsb 也是對稱半正定矩陣，在兩類條件下，它的秩最大等于 1 。定義幾個基本參量定義幾個基本參量4.2 fisher線性判別線性判別在一維在一維 y y 空間空間n各類樣本均值iyyiiynm1，i =1，2 樣本類內離散度 和總類內離散度2isws22)(iimys2221sssw4.2 fisher線性判別線性判別定義定義fisher準

17、則函數(shù)準則函數(shù)n希望投影后，在一維 y 空間里各類樣本盡可能分得開些，即希望兩類均值之差越大越好；n希望各類樣本內部盡量密集，即希望類內離散度越小越好。因此，可以定義fisher準則函數(shù)為：2221221)()(ssmmjfw4.2 fisher線性判別線性判別n尋找使jf(w) 盡可能大的 w 作為投影方向。但 jf(w)式并不顯含w，因此必須設法jf(w) 將變成w的顯函數(shù)。2221221)()(ssmmjfwitxxyyittiyyiiiiinnynmmwxwxw111盡可能大盡可能小fisher準則函數(shù)準則函數(shù)4.2 fisher線性判別線性判別wwwmmmmwmwmwbtttttsm

18、m)()()(2121221221wwwmxmxwmwxwitxxtiititxxtyyiismysiii)()()(222fisher準則函數(shù)準則函數(shù)4.2 fisher線性判別線性判別wwwwwttsssss)(212221wwwwwwtbtfssj)(fisher準則函數(shù)準則函數(shù)4.2 fisher線性判別線性判別fisher準則的合理性：準則的合理性：njf(w)只與投影方向有關，與大小無關若w是一個最優(yōu)解， kw也是最優(yōu)解，k是任何不為零的常數(shù)。4.2 fisher線性判別線性判別fisher最佳投影方向的求解：最佳投影方向的求解：n要求：sw = s1 + s2正定。否則，存在投影

19、方向w，使得wtsww=0，所有數(shù)據(jù)被投影到一點上。 jf(w)沒有極大值。n求出最佳投影方向上任何一個w即可。njf(w)有上界，最佳投影方向一定存在！(sb)max，(sw)min分別是sb，sw矩陣的最大、最小的特征根。minmax)()()(wbfssjw4.2 fisher線性判別線性判別fisher最佳投影方向的求解：最佳投影方向的求解：n一定存在一個最優(yōu)的w ，滿足wtsww=1，因為sw 正定。wwwwwtbtssmax無約束最優(yōu)化：等價于帶約束的最優(yōu)化： max wtsbw wtsww=14.2 fisher線性判別線性判別n因為分母等于1是非零常數(shù)，wtsww=10n定義

20、lagrange 函數(shù)為jf(w)是廣義rayleigh商，帶等式約束的最優(yōu)化，可以用lagrange乘子法求解。) 1(),(wwwwwwtbtsslfisher最佳投影方向的求解：最佳投影方向的求解：4.2 fisher線性判別線性判別) 1(),(wwwwwwtbtssl式中 為lagrange乘子，將上式對w求偏導數(shù)，得wwwwwbssl),(fisher最佳投影方向的求解：最佳投影方向的求解：4.2 fisher線性判別線性判別最優(yōu)解滿足：最優(yōu)解滿足：n其中 w*就是 jf(w) 的極值解。0*wwwbss*wwwbss因為sw非奇異，上式兩邊左乘 ，可得 1ws*1wwbwssfi

21、sher最佳投影方向的求解：最佳投影方向的求解：4.2 fisher線性判別線性判別*1wwssbw解上式是求一般矩陣 的本征值問題。bwss1根據(jù)類間離散度sb 的定義，上式左邊的 sbw*可以寫成cstb)(*)(*212121mmwmmmmwfisher最佳投影方向的求解：最佳投影方向的求解：*)(21wmmtc*wbs注意 是一個數(shù)，所以 總是在向量(m1m2)的方向上。4.2 fisher線性判別線性判別n只關心投影的方向：cssswbw)(*)(*2111mmww)(*211mmwwsc)()()(*21121211mmmmwsssww*就是使fisher準則函數(shù)jf(w)取極大值

22、時的解，也就是d維x空間到一維y空間的最好投影方向。fisher最佳投影方向的求解：最佳投影方向的求解：4.2 fisher線性判別線性判別幾種分類閾值的確定幾種分類閾值的確定n均值中點法221)1(0mmy類樣本數(shù)加權法mnnmnmny212211)2(04.2 fisher線性判別線性判別n根據(jù)決策規(guī)則先驗概率加權法2)(/ )(ln(2212121)3(0nnppmmy就可判斷x屬于什么類別。y y0 x120，n=1，2，n的權向量a即可。a被稱作分離向量(separating vector)或解向量(solution vector)。 樣本的規(guī)范化樣本的規(guī)范化 4.3.1 幾個基本概

23、念幾個基本概念 線性可分性線性可分性 解向量和解區(qū)解向量和解區(qū)nh解向量如果存在，則必在 的正側，因為只有在正側才能滿足 。0ntya4.3.1 幾個基本概念幾個基本概念 線性可分性線性可分性 解向量和解區(qū)解向量和解區(qū)4.3.1 幾個基本概念幾個基本概念 線性可分性線性可分性，n=1,2，n，0ntya設有一組樣本y1，y2，yn，其中yn是規(guī)范化增廣樣本向量，目的是找一個解向量 a，使n采用的方法是：定義一個準則函數(shù)j(a)，當a是解向量時，j(a)最小。標量函數(shù)最小化問題用梯度下降法。4.3.2 梯度下降算法梯度下降算法 n梯度下降法的原理：從隨意選擇的權向量a(1)開始，計算其梯度向量

24、j(a(1)， a(2)由自a(1)向下降最陡的方向移一段距離得到。)()()() 1(kjkkkaaa設定步長的學習率(learn rate)或正的比例因子。獲得權向量序列，使j(a)極小algorithm 1 (basic gradient descent) ：1 begin initialize a; criterion , (), k 02 do k k + 13 a a (k) j(a)4 until |(k) j(a)| 5 return a6 end)()()() 1(kjkkkaaa4.3.2 梯度下降算法梯度下降算法 )()()() 1(kjkkkaaa)()() 1(1kj

25、hkkaaan其中h是赫森矩陣，是j(a)在a(k)的二階偏導：jiaaj4.3.2 梯度下降算法梯度下降算法 n梯度下降法存在問題：如何選擇學習率(k)？如果(k)太小，收斂將非常慢；而如果(k)太大的話可能會過沖(overshoot)，甚至發(fā)散。n牛頓下降法：n牛頓下降法：algorithm 2 (newton descent)1 begin initialize a; criterion 2 do3 a ah1j(a)4 until |h1j(a)| 5 return a6 end4.3.2 梯度下降算法梯度下降算法 n簡單梯度下降法和牛頓下降法的比較:簡單梯度下降法牛頓(二階)算法每一

26、步都給出更好的步長但求赫森逆矩陣的計算量很大4.3.2 梯度下降算法梯度下降算法 kytpjyyaa)()(n構造這樣一個準則函數(shù)n式中yk是被權向量a錯分類的樣本集合。n當y被錯分類時0yatn也就是說，當且僅當不存在錯分樣本，即yk為空集時0)(min)(*aappjj4.3.3 感知器準則函數(shù)感知器準則函數(shù)kytpjyyaa)()(kyppjjyyaaa)()()(n求準則函數(shù)的梯度kykkkyyaa)()() 1(n感知器準則函數(shù)的算法(批處理)：algorithm 3 (batch perceptron)1 begin initialize a; (), criterion , k

27、02 do k k + 13 a a + (k) yyky4 until |(k) yyky| 0所表示的不等式組，0ya4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 0ya1211121ntnttyyyyyyy22212nyyydnddyyy21n為使解更可靠，引入余量b 0，那么0ya規(guī)范化增廣樣本矩陣dn4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 1111個nb對于(4-47)式可以定義準則函數(shù) 0bya(4-47)21|)()(byabyaaqjn維向量4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 如果 則 和 同號，因此， ，反

28、之，如果有某些yi不滿足 ，則 和 異號，因此， 。不滿足的yi越多， 越大。 bya)(bya|bya0)(1aqjiitbya)(iitbya|iitbya0)(1aqj)(1aqj4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 顯然， 取極小值時的a為最優(yōu)解a*。并且在不等式組一致的情況下， ，在不等式組不一致情況下， 。 )(1aqj0*)(1aqj0*)(1aqj)(1aqj稱為最小錯分樣本數(shù)準則1。 4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 共軛梯度算法的基本概念共軛梯度算法的基本概念n設b是一個dd階對稱正定矩陣，若有兩個d維向量u和v使(u

29、，bv)=0，則稱u和v對于矩陣b互為共軛。n顯然，若u和v對于單位陣i互為共軛，則u和v正交，當x和y是b的本征向量時，有 (y，bx)=(y,x)=(y，x) = 0n因此，一個正定矩陣b的本征向量對于b互為共軛。4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 n共軛梯度算法就是以ed空間中的一組對于b互為共軛的向量作為一維搜索方向，使二次正定函數(shù)f(x) = b0+btx+xtbx n達到極小值的最優(yōu)化算法。n用共軛梯度法可以求得序列x0，x1，x2，使得f (x0)f (x1)f (x2)n可以證明，對于二次正定函數(shù)f (x)，最多用d步，就可以使序列x收斂于f (x)

30、的極值解x*。4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 n因此，在沿d個(對于增廣空間則為d+1個)互為共軛的向量進行一維搜索后，有可能達不到準則函數(shù)的最小值，即算法經(jīng)過d(或d+1)步可能不收斂，這時就要重新開始計算，若用r表示重新開始的周期，則r = d(或d+1)。由于 式定義的準則函數(shù)不是一個二次正定函數(shù)，而是一個分段二次正定函數(shù)，21|)()(byabyaaqj4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 在任意點 ， 的負梯度方向可表示為a0)(1aqjpbabaaattqyyyyjg)(|)(41)(14.4.1解線性不等式組的共軛梯度法解

31、線性不等式組的共軛梯度法 )(|babapyy21|)()(byabyaaqj21g令n這種算法的具體步驟如下：用k表示迭代步數(shù)，用 表示滿足于 的不等式的數(shù)目， 表示最優(yōu)解。a*a置k = 0，并任意給定初始權向量 ，計算 和 。 0a0ay0如果 ，則令20n000000,nyyaaaa然后繼續(xù)。 4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 如果 ，則令 ，停止；如果 ，則令 ，停止；否則繼續(xù)。nkkaa *0kkaa*計算gk。如果gk=0，則停止；否則計算 ，然后繼續(xù)。 k求k。如果k為r的整數(shù)倍，則令k= 0；否則令k=1，并計算kkkkkgss1sk表示第k次搜

32、索時的梯度下降方向。若 表示對 的第一次逼近，則 ?？梢宰C明，由上述表達式所產生的s1，s2，對于二次函數(shù)中的正定矩陣是互為共軛的。0a*a000gs4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 尋找最佳步長vk，即計算使 取極小值時的v。 )(kkvsja令 ， 并計算 。 kkkksvaa1kkkkysvyyaa11k令k = k + 1，轉向步驟2。 4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 0 baynagaraja和krishna證明，對于 表示的分段二次函數(shù)，在 的一致條件下，上述算法可以在有限步內使序列收斂于最優(yōu)解。21|)()(byaby

33、aaqj4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 而在 不一致條件下，只要適當?shù)倪x擇b，使在 的唯一極小點 上，有0bay)(1aqj*a，i=1，2，niitbya*則該算法產生的序列a也在有限步內收斂于 a* 。對于 表示的準則函數(shù)，在不等式組不一致的情況下，對某些樣本，可能存在 iitbya021|)()(byabyaaqj因此就產生了一個閾值問題。這時，由于 atyi0，yi應被正確分類；但又由于 atyi0收斂于的解a*。在不一致情況下，由于jq1(a)是嚴格的凸函數(shù)，其唯一極小點是a=0，而且有0)(1aqj4.4.1解線性不等式組的共軛梯度法解線性不等式組的

34、共軛梯度法 因此，atyi bi(i=1，2，n)的條件不成立，所以得不到解向量a*。4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 作為準則函數(shù)來解決上述問題。顯然，這時存在下列關系： 22|)(aaaayyf0)(2)()(1aaaafjfq也就是說，使 最小，同在終止條件)(afaaa)(2)(1fjq和 下使 最小是等價的。這時需要將上述算法的步驟1和4改變如下：0)(a)(1aqj4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 通過原有算法得到一個收斂點，記為 ，并以此作為補充算法的起點。sa計算 和 ，并且繼續(xù)。2kktkkagakkkksga 可以

35、證明，這樣得到的sk仍然是 的下降方向。)(1aqj同時可以證明，假使ya0是不一致的，且在求jq1(a)最小值的過程中用步驟代替原算法的步驟4，若所得的序列a是有限的，則序列的最后一個元素就相當于f(a)的一個局部最小值的解。4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 若序列是無限的，則它趨向于f(a)的一個局部最小值的解。在進行上述計算時，由于我們使用原算法的收斂點as 作為起始點，它常常是全局最優(yōu)解f(a)的一個很好的逼近，故可以得到的全局最優(yōu)解。4.4.1解線性不等式組的共軛梯度法解線性不等式組的共軛梯度法 n考慮齊次線性不等式組0)(aydnnnddyyyyyyy

36、yyy212222111211dnn其中 矩陣 n為規(guī)范化增廣樣本矩陣，每一行yi代表一個樣本，n為樣本數(shù)，d為yi的維數(shù)。dnn且有niiqj122)sgn(1)(aya式中0101)sgn(ayayayiii，對于，對于 實際上是 所滿足的不等式的數(shù)目。)(2aqja稱之為最小錯分樣本數(shù)準則2。使jq2(a)取最大值的a就是要求的解 a*。n現(xiàn)在定義另一種形式的最小錯分樣本數(shù)準則如下： 4.4.2解線性不等式組的搜索法解線性不等式組的搜索法 n因此，n個樣本向量所建立的超平面把權空間劃分成為凸多棱錐的有限集合，每個錐c都由有限個支撐超平面所組成。對于每個yi，方程yia =0在權空間中建立

37、了一個超平面hi，而且所有超平面都通過原點。) 1( dn組成錐的一部分超平面，或超平面的截取部分，稱為錐的“前沿”，歐氏空間ed中 個超平面的交叫做錐的棱。4.4.2解線性不等式組的搜索法解線性不等式組的搜索法 n圖4.10示出三維凸多棱錐及其前沿和棱的一個例子。c+c+c+c原點前沿棱圖 4.10而且某個錐c中的任何權向量對樣本集的劃分都是相同的，或者說，某個錐中的所有權向量所滿足的不等式的數(shù)目是相同的。 錐c中的每一個點，都對應一個權向量a4.4.2解線性不等式組的搜索法解線性不等式組的搜索法 n如果某個錐c中的任何權向量都能使上式的準則函數(shù)為最大，那么就稱這個錐為最小錯誤錐，記為c*。

38、*n這樣，求使最多數(shù)目的不等式得到滿足的權向量 的問題，就轉化為尋找一個或多個最小錯誤錐c*的問題了。niiqj122)sgn(1)(ayadccn由于對于每個ced，存在著對稱反射，即 維權向量 和 所產生的分類情況恰好相反，所以，如果對于某個存在4.4.2解線性不等式組的搜索法解線性不等式組的搜索法 nqj)(2a為奇數(shù)，為偶數(shù)，nnnnn212n其中n則必有 。nqj )(2an由于我們只關心最小錯誤錐，因此，我們只限于研究使nqj)(2a錐就可以了。如果遇到的情況，則用 代替 。nqj)(2aaa 的那些4.4.2解線性不等式組的搜索法解線性不等式組的搜索法 尋找最小錯誤錐尋找最小錯誤錐c*的搜索算法。的搜索算法。 ddd)0() 1(d) 1(dn定理 假設y滿足haar(y的每個 子陣的秩都是 )條件，令 是ed中任何一條棱上的權向量，不失一般性，初始棱選作前 個樣本yi確定的 個超平面的交，即令：121)0(dhhh*cn那么，最優(yōu)權向量 一定在下面定義的搜索序列中，4.4.2解線性不等式組的搜索法解線性不等式組的搜索法 1|)1 (11321iihhhhdi2|)2(21321iihhhhdii) 1(|)1(1)1(321ddiiiiidihhhhd上式中的指標集ik，k =