線性判別函數(shù)1PPT課件

1、解決實際問題方法 在實際中存在問題 樣本特征空間的類條件概率密度形式常常很難確定 利用 Parzen 窗等非參數(shù)方法恢復分布往往需要大量樣本，而且隨著特征空間維數(shù)的增加所需樣本數(shù)急劇增加。 因此，在解決實際問題時，往往是利用樣本集直接設計分類器，而不恢復類條件概率密度。 即采用判別函數(shù)，首先給定某個判別函數(shù)類，然后利用樣本集確定出判別函數(shù)中的未知參數(shù)。第1頁/共130頁線性判別函數(shù) 線性判別函數(shù)法是一類較為簡單的判別函數(shù)。是統(tǒng)計模式識別的基本方法之一。 它首先假定判別函數(shù) g(x) 是 x 的線性函數(shù)，即 g(x)=wTx+ w0 ，對于 c 類問題，可以定義 c 個判別函數(shù)， gi(x)=w

2、iTx+ wi0 ， i=1,2 ， c 。 用樣本去估計各 wi 和 wi0 ，并把未知樣本 x 歸到具有最大判別函數(shù)值的類別中去。 關鍵是如何利用樣本集求得 wi 和 wi0 。第2頁/共130頁訓練和學習 “訓練”和“學習” 在待識別的模式中，挑選一批有代表性的樣本，經過人工判讀，成為已知分類的樣本，把這批樣本逐個輸入到計算機中的“訓練”程序或算法中，通過一次次的迭代，最后得到正確的線性判別函數(shù)。 這樣的迭代過程稱之為訓練過程，所構成的分類器稱為有人監(jiān)督或有教師的分類器。第3頁/共130頁 在正態(tài)分布的Bayesian判別中，已經遇到過在兩類情況下判別函數(shù)為線性的情況。 假設有1 和2

3、兩類模式，在二維模式特征空間可用一直線把這兩類模式劃分開，如圖 4.1 所示。第4頁/共130頁x1x2g(x) = w2x2+w1x1+w0 圖4.1兩類模式的一個簡單判別函數(shù)+劃分直線的方程參數(shù)坐標變量4.1.1 線性判別函數(shù)的基本概念第5頁/共130頁判別規(guī)則 若給定一個未知類別的模式x 當g(x)0 時，則決策 x 屬于1 ； 當 g(x)0，所以決策面的法向量是指向 R1 的。 因此，有時稱 R1 中的任何 x 在 H 的正側，相應地，稱 R2 中的任何 x 在 H 的負側。4.1.1 線性判別函數(shù)的基本概念第11頁/共130頁判別函數(shù) g(x) 是特征空間中某點 x 到超平面距離的

4、一種代數(shù)量度。 若把 x 表示成式中 xp ：是 x 在 H 上的投影向量； r ：是 x 到 H 的垂直距離；wwxxrpww：是w方向上的單位向量。wwwwxwwwxwxTTrrwwr0p0pT)()(g4.1.1 線性判別函數(shù)的基本概念第12頁/共130頁若 x 為原點，則 g(x)=w0 (4-7)將 (4-7) 代入 (4-6) ，就得到從原點到超平面 H 的距離w)x(gr (4-6) w0wr 判別函數(shù) g(x) 是特征空間中某點 x 到超平面距離的一種代數(shù)量度。4.1.1 線性判別函數(shù)的基本概念第13頁/共130頁w0wr 如果 w00 ，則原點在 H 的正側；若 w00 ，則

5、原點在 H 的負側。若w0=0 ，則 g(x) 具有齊次形式 wTx ，說明超平面 H 通過原點。判別函數(shù) g(x) 是特征空間中某點 x 到超平面距離的一種代數(shù)量度。4.1.1 線性判別函數(shù)的基本概念第14頁/共130頁圖 4.2 對這些結果作了幾何解釋。4.1.1 線性判別函數(shù)的基本概念第15頁/共130頁結論 利用線性判別函數(shù)進行決策，就是用一個超平面把特征空間分割成兩個決策區(qū)域。 超平面的方向由權向量 w 確定，它的位置由閾值權 w0 確定。 判別函數(shù) g(x) 正比于 x 點到超平面的代數(shù)距離（帶正負號）當 x 在 H 正側時， g(x) 0 ，在負側時， g(x) 0 。4.1.1

6、 線性判別函數(shù)的基本概念第16頁/共130頁 如圖 4.3 所示的二類問題。 設有一維樣本空間 X ，所希望的劃分是： 如果 xa ，則 x 屬于1 類； 如果 b x0 ，則決策 x1g(x)0 ，則決策 x2二次判別函數(shù)可寫成如下一般形式g(x)=c0+c1x+ c2x2(4-10)如果適當選擇 x y 的映射，則可把二次判別函數(shù)化為 y 的線性函數(shù)31)(iiiTyagyax4.1.2 廣義線性判別函數(shù)第19頁/共130頁式中213211xxyyyy210321cccaaaayaxTg)(稱為廣義判別函數(shù)，a叫做廣義權向量。 一般地，對于任意高次判別函數(shù) g(x)(這時的 g(x) 可看

7、作對任意判別函數(shù)作級數(shù)展開，然后取其截尾部分的逼近)，都可以通過適當?shù)淖儞Q，化為廣義線性判別函數(shù)來處理。31)(iiiTyagyax4.1.2 廣義線性判別函數(shù)第20頁/共130頁存在問題 經過變換后，維數(shù)大大增加了，這將使問題很快陷入所謂“維數(shù)災難”。 在統(tǒng)計學習理論中，對廣義線性分類器進行研究，克服了“維數(shù)災難”問題，進而發(fā)展出了最新的模式識別方法支持向量機，成為解決有限樣本情況下非線性分類問題的有效手段。4.1.2 廣義線性判別函數(shù)第21頁/共130頁 把 (4-1) 式定義的線性判別函數(shù)寫成下面的形式xy1121dxxxwa0210wwwwwd1 ddyaxTdiiidiiiyaxww

8、g110)(4-12)增廣特征向量Augmented feature vector增廣權向量(廣義權向量)Augmented weight vector4.1.2 廣義線性判別函數(shù)第22頁/共130頁結論 y 與 x 相比，雖然增加了一維，但保持了樣本間的歐氏距離不變，變換后的樣本向量仍然全部位于 d 維子空間，即原 X 空間中，方程0yaT(4-13)在Y空間確定了一個通過原點的超平面 。H它對 d 維子空間的劃分與原決策面 wTx+ w0=0 對原 X 空間的劃分完全相同。4.1.2 廣義線性判別函數(shù)第23頁/共130頁例子 這種方法的優(yōu)缺點可通過例子來說明?？紤]二次判別函數(shù)2321)(x

9、axaaxg得到三維向量y21xxy從x到y(tǒng)的映射如圖所示。4.1.2 廣義線性判別函數(shù)第24頁/共130頁例子4.1.2 廣義線性判別函數(shù)數(shù)據(jù)仍保持固有的一維，因為改變x將導致y沿著一個三維曲線運動。如果x服從某一個概率分布時，得到的密度函數(shù)是退化的，即曲線之外是0，在曲線上是無窮大，這是從低維空間到高維空間映射的普遍問題。第25頁/共130頁例子4.1.2 廣義線性判別函數(shù)圖中映射y=(1,x,x2)T把一條直線映射為三維空間中的一條拋物線。由于兩類問題，在三維空間中，一個平面就是一個分隔面。因此，由圖可見，這產生了原始一維x空間的不連通性第26頁/共130頁例子g(x)=1+x+ 2x2

10、x0.5時g(x)0a=(-1, 1,2)T4.1.2 廣義線性判別函數(shù)由aTy=0定義的平面將y空間分成兩個判別區(qū)域，如圖給出當a=(-1,1,2)T時的分類平面和x空間對應的判別區(qū)域。第27頁/共130頁結論aTy=0在2維空間不穿過原點4.1.2 廣義線性判別函數(shù)一個三維增廣特征空間y和增廣權向量a(在原點)。滿足aTy=0的點集是一個穿過y空間原點的超平面(用紅色表示)，這個平面垂直于a。這個平面在其原來的二維空間中不一定穿過原點(即立方體頂部虛線所示的判決邊界)。因此存在一個增廣權向量a，可以獲得x空間中任意的判定線。第28頁/共130頁設計線性分類器，就是建立線性判別函數(shù)(4-l)

11、式g(x) =wTx+w0或廣義線性判別函數(shù)(4-12)式y(tǒng)axTg)(這樣，設計線性分類器就轉化為，利用訓練樣本集尋找準則函數(shù)的極值點 和 或 。*a*w*0w第29頁/共130頁設計線性分類器的主要步驟如下： 要有一組具有類別標志的樣本集X=x1，x2，xN。 如果在樣本 xn 抽出后，把它看作一個確定的觀察值，則這組樣本集稱為確定性樣本集； 若把 xn 看作一個隨機變量，則這組樣本集稱為隨機樣本集。 有時也將樣本集 X 轉換成增廣樣本集 Y 來處理。4.1.3 設計線性分類器的主要步驟第30頁/共130頁n 要根據(jù)實際情況確定一個準則函數(shù) J 它必須滿足： J 的值反映分類器的性能，它的

12、極值解則對應于 最好 的決策。 J是樣本集X和w、w0或 a 的函數(shù)；設計線性分類器的主要步驟如下：4.1.3 設計線性分類器的主要步驟第31頁/共130頁*0*)(wgTxwx*0w用最優(yōu)化技術求出準則函數(shù)的極值解 和 w*或a*。這樣就可以得到線性判別函數(shù)yaxTg*)(或設計線性分類器的主要步驟如下：4.1.3 設計線性分類器的主要步驟第32頁/共130頁 Fisher線性判別函數(shù)是經典判別方法之一，應用非常廣泛。 應用統(tǒng)計方法解決模式識別問題時，困難之一是維數(shù)問題。 在低維空間里行得通的方法，在高維空間里往往行不通。 因此，降低維數(shù)有時就成為處理實際問題的關鍵。第33頁/共130頁 在

13、數(shù)學上通?？梢园?d 維空間的樣本投影到一條直線上，形成一維空間，即把維數(shù)壓縮到一維。 在一般情況下，總可以找到某個方向，使在這個方向的直線上，樣本的投影能分開得最好。 問題是如何根據(jù)實際情況找到這條最好的、使最易于分類的投影線。這就是Fisher法所要解決的基本問題 (見圖 4.4) 。4.2 Fisher線性判別第34頁/共130頁4.2 Fisher線性判別第35頁/共130頁從 d 維空間到一維空間的數(shù)學變換方法 假設有一集合 X 包含 N 個 d 維樣本 x1 ， x2 ，xN ，其中 N1 個屬于1 類的樣本記為子集 X1 ，N2 個屬于2 類的樣本記為 X2 ，若對 xn 的分量

14、作線性組合可得標量yn=wTxn, n=1 ， 2 ， Ni 這樣便得到 N 個一維樣本 yn 組成的集合，并可分為兩個子集 Y1 和 Y2 。4.2 Fisher線性判別第36頁/共130頁w* 就是最好的投影方向 從幾何上看，如果 |w|=1 ，則每個 yn 就是相對應的 xn 到方向為 w 的直線上的投影，實際上，w 的絕對值是無關緊要的，它僅使 yn 乘上一個比例因子，重要的是選擇 w 的方向。 w 的方向不同，將使樣本投影后的可分離程度不同，從而直接影響識別效果。 因此，前述所謂尋找最好投影方向的問題，在數(shù)學上就是尋找最好的變換向量 w*的問題。4.2 Fisher線性判別第37頁/

15、共130頁定義幾個基本參量 在 d 維 X 空間 各類樣本均值向量miiXxiiNxm1， i =1，2 n樣本類內離散度矩陣 Si 和總類內離散度矩陣 SwiXxTiiiS)(mxmx，i =1，2 Sw=S1+ S24.2 Fisher線性判別第38頁/共130頁n樣本類間離散度矩陣SbSb=(m1 m2)(m1 m2)T 其中 Sw 是對稱半正定矩陣，而且當 Nd 時通常是非奇異的。Sb 也是對稱半正定矩陣，在兩類條件下，它的秩最大等于 1 。定義幾個基本參量4.2 Fisher線性判別第39頁/共130頁在一維 Y Y 空間 各類樣本均值iYyiiyNm1，i =1，2 樣本類內離散度

16、 和總類內離散度2iSwS22)(iimyS2221SSSw4.2 Fisher線性判別第40頁/共130頁定義Fisher準則函數(shù) 希望投影后，在一維 Y 空間里各類樣本盡可能分得開些，即希望兩類均值之差越大越好； 希望各類樣本內部盡量密集，即希望類內離散度越小越好。因此，可以定義Fisher準則函數(shù)為：2221221)()(SSmmJFw4.2 Fisher線性判別第41頁/共130頁 尋找使JF(w) 盡可能大的 w 作為投影方向。但 JF(w)式并不顯含w，因此必須設法JF(w) 將變成w的顯函數(shù)。2221221)()(SSmmJFwiTXxYyiTTiYyiiiiiNNyNmmwxw

17、xw111盡可能大盡可能小Fisher準則函數(shù)4.2 Fisher線性判別第42頁/共130頁wwwmmmmwmwmwbTTTTTSmm)()()(2121221221wwwmxmxwmwxwiTXxTiiTiTXxTYyiiSmySiii)()()(222Fisher準則函數(shù)4.2 Fisher線性判別第43頁/共130頁wwwwwTTSSSSS)(212221wwwwwwTbTFSSJ)(Fisher準則函數(shù)4.2 Fisher線性判別第44頁/共130頁Fisher準則的合理性：JF(w)只與投影方向有關，與大小無關若w是一個最優(yōu)解， kw也是最優(yōu)解，k是任何不為零的常數(shù)。4.2 Fis

18、her線性判別第45頁/共130頁Fisher最佳投影方向的求解： 要求：Sw = S1 + S2正定。否則，存在投影方向w，使得wTSww=0，所有數(shù)據(jù)被投影到一點上。 JF(w)沒有極大值。 求出最佳投影方向上任何一個w即可。JF(w)有上界，最佳投影方向一定存在！(Sb)max，(Sw)min分別是Sb，Sw矩陣的最大、最小的特征根。minmax)()()(wbFSSJw4.2 Fisher線性判別第46頁/共130頁Fisher最佳投影方向的求解：一定存在一個最優(yōu)的w ，滿足wTSww=1，因為Sw 正定。wwwwwTbTSSmax無約束最優(yōu)化：等價于帶約束的最優(yōu)化： max wTSb

19、w wTSww=14.2 Fisher線性判別第47頁/共130頁 因為分母等于1是非零常數(shù)，wTSww=10 定義 Lagrange 函數(shù)為JF(w)是廣義Rayleigh商，帶等式約束的最優(yōu)化，可以用Lagrange乘子法求解。) 1(),(wwwwwwTbTSSLFisher最佳投影方向的求解：4.2 Fisher線性判別第48頁/共130頁) 1(),(wwwwwwTbTSSL式中 為Lagrange乘子，將上式對w求偏導數(shù)，得wwwwwbSSL),(Fisher最佳投影方向的求解：4.2 Fisher線性判別第49頁/共130頁最優(yōu)解滿足： 其中 w*就是 JF(w) 的極值解。0*

20、wwwbSS*wwwbSS因為Sw非奇異，上式兩邊左乘 ，可得 1wS*1wwbwSSFisher最佳投影方向的求解：4.2 Fisher線性判別第50頁/共130頁*1wwSSbw解上式是求一般矩陣 的本征值問題。bwSS1根據(jù)類間離散度Sb 的定義，上式左邊的 Sbw*可以寫成cSTb)(*)(*212121mmwmmmmwFisher最佳投影方向的求解：*)(21wmmTc*wbS注意 是一個數(shù)，所以 總是在向量(m1m2)的方向上。4.2 Fisher線性判別第51頁/共130頁 只關心投影的方向：cSSSwbw)(*)(*2111mmww)(*211mmwwSc)()()(*2112

21、1211mmmmwSSSww*就是使Fisher準則函數(shù)JF(w)取極大值時的解，也就是d維X空間到一維Y空間的最好投影方向。Fisher最佳投影方向的求解：4.2 Fisher線性判別第52頁/共130頁幾種分類閾值的確定 均值中點法221)1(0mmy類樣本數(shù)加權法mNNmNmNy212211)2(04.2 Fisher線性判別第53頁/共130頁 根據(jù)決策規(guī)則先驗概率加權法2)(/ )(ln(2212121)3(0NNPPmmy就可判斷x屬于什么類別。y y0 x120，n=1，2，N的權向量a即可。a被稱作分離向量(separating vector)或解向量(solution vec

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

23、1)開始，計算其梯度向量 J(a(1)， a(2)由自a(1)向下降最陡的方向移一段距離得到。)()()() 1(kJkkkaaa設定步長的學習率(learn rate)或正的比例因子。獲得權向量序列，使J(a)極小第66頁/共130頁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(kJ

24、kkkaaa第67頁/共130頁)()() 1(1kJHkkaaan其中H是赫森矩陣，是J(a)在a(k)的二階偏導：jiaaJ4.3.2 梯度下降算法 n梯度下降法存在問題：如何選擇學習率(k)？如果(k)太小，收斂將非常慢；而如果(k)太大的話可能會過沖(overshoot)，甚至發(fā)散。n牛頓下降法：第68頁/共130頁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 梯度下降算法 第69頁/共130頁

25、n簡單梯度下降法和牛頓下降法的比較:簡單梯度下降法牛頓(二階)算法每一步都給出更好的步長但求赫森逆矩陣的計算量很大4.3.2 梯度下降算法 第70頁/共130頁kYTPJyyaa)()(n構造這樣一個準則函數(shù)n式中Yk是被權向量a錯分類的樣本集合。n當y被錯分類時0yaTn也就是說，當且僅當不存在錯分樣本，即Yk為空集時0)(min)(*aaPPJJ第71頁/共130頁4.3.3 感知器準則函數(shù)kYTPJyyaa)()(kYPPJJyyaaa)()()(n求準則函數(shù)的梯度kYkkkyyaa)()() 1(第72頁/共130頁n感知器準則函數(shù)的算法(批處理)：Algorithm 3 (Batch

26、 Perceptron)1 begin initialize a; (), criterion , k 02 do k k + 13 a a + (k) yYky4 until |(k) yYky| 0所表示的不等式組，0Ya4.4.1解線性不等式組的共軛梯度法 第94頁/共130頁0Ya1211121NTNTTyyyyyyY22212NyyydNddyyy21n為使解更可靠，引入余量b 0，那么0Ya規(guī)范化增廣樣本矩陣dN4.4.1解線性不等式組的共軛梯度法 第95頁/共130頁1111個Nb對于(4-47)式可以定義準則函數(shù) 0bYa(4-47)21|)()(bYabYaaqJN維向量4.

27、4.1解線性不等式組的共軛梯度法 第96頁/共130頁如果 則 和 同號，因此， ，反之，如果有某些yi不滿足 ，則 和 異號，因此， 。不滿足的yi越多， 越大。 bYa)(bYa|bYa0)(1aqJiiTbya)(iiTbya|iiTbya0)(1aqJ)(1aqJ4.4.1解線性不等式組的共軛梯度法 第97頁/共130頁顯然， 取極小值時的a為最優(yōu)解a*。并且在不等式組一致的情況下， ，在不等式組不一致情況下， 。 )(1aqJ0*)(1aqJ0*)(1aqJ)(1aqJ稱為最小錯分樣本數(shù)準則1。 4.4.1解線性不等式組的共軛梯度法 第98頁/共130頁共軛梯度算法的基本概念 設B是

28、一個dd階對稱正定矩陣，若有兩個d維向量u和v使(u，Bv)=0，則稱u和v對于矩陣B互為共軛。 顯然，若u和v對于單位陣I互為共軛，則u和v正交，當x和y是B的本征向量時，有 (y，Bx)=(y,x)=(y，x) = 0 因此，一個正定矩陣B的本征向量對于B互為共軛。4.4.1解線性不等式組的共軛梯度法 第99頁/共130頁 共軛梯度算法就是以Ed空間中的一組對于B互為共軛的向量作為一維搜索方向，使二次正定函數(shù)f(x) = b0+bTx+xTBx 達到極小值的最優(yōu)化算法。 用共軛梯度法可以求得序列x0，x1，x2，使得f (x0)f (x1)f (x2) 可以證明，對于二次正定函數(shù)f (x)

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

30、.4.1解線性不等式組的共軛梯度法 )(|babapYY21|)()(bYabYaaqJ21g令第102頁/共130頁 這種算法的具體步驟如下：用k表示迭代步數(shù)，用 表示滿足于 的不等式的數(shù)目， 表示最優(yōu)解。a*a置k = 0，并任意給定初始權向量 ，計算 和 。 0a0aY0如果 ，則令20N000000,NYYaaaa然后繼續(xù)。 4.4.1解線性不等式組的共軛梯度法 如果 ，則令 ，停止；如果 ，則令 ，停止；否則繼續(xù)。Nkkaa *0kkaa*第103頁/共130頁計算gk。如果gk=0，則停止；否則計算 ，然后繼續(xù)。 k求k。如果k為r的整數(shù)倍，則令k= 0；否則令k=1，并計算kkk

31、kkgSS1Sk表示第k次搜索時的梯度下降方向。若 表示對 的第一次逼近，則 。可以證明，由上述表達式所產生的S1，S2，對于二次函數(shù)中的正定矩陣是互為共軛的。0a*a000gS4.4.1解線性不等式組的共軛梯度法 第104頁/共130頁尋找最佳步長vk，即計算使 取極小值時的v。 )(kkvSJa令 ， 并計算 。 kkkkSvaa1kkkkYSvYYaa11k令k = k + 1，轉向步驟2。 4.4.1解線性不等式組的共軛梯度法 第105頁/共130頁0 baYNagaraja和Krishna證明，對于 表示的分段二次函數(shù)，在 的一致條件下，上述算法可以在有限步內使序列收斂于最優(yōu)解。21

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

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

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

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

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

37、錯誤錐，記為C*。*n這樣，求使最多數(shù)目的不等式得到滿足的權向量 的問題，就轉化為尋找一個或多個最小錯誤錐C*的問題了。NiiqJ122)sgn(1)(ayadCCn由于對于每個CEd，存在著對稱反射，即 維權向量 和 所產生的分類情況恰好相反，所以，如果對于某個存在4.4.2解線性不等式組的搜索法 第117頁/共130頁NqJ)(2a為奇數(shù)，為偶數(shù)，NNNNN212n其中n則必有 。NqJ )(2an由于我們只關心最小錯誤錐，因此，我們只限于研究使NqJ)(2a錐就可以了。如果遇到的情況，則用 代替 。NqJ)(2aaa 的那些4.4.2解線性不等式組的搜索法 第118頁/共130頁尋找最小錯誤錐C*的搜索算法。 ddd)0() 1(d) 1(dn定理 假設Y滿足Haar(Y的每個 子陣的秩都是 )條件，令 是Ed中任何一條棱上的權向量，不失一般性，初始棱選作前 個樣本yi確定的 個超平面的交，即令：121)0(dHHH*Cn那么，最優(yōu)權向量 一定在下面定義的搜索序列中，4.4.2解線性不等式組的搜索法 第119頁/共130頁1|)1 (11321IiHHHHdi2|)2(21321IiHHHHdii) 1(|)1(1)1(321ddiiiiIdiHHHHd上式中的指標集Ik，k = 1，2，是使 ，且1d0) 1(kyiNqk