1、第四章 線性判別函數(shù)Bayesian分類器設(shè)計(jì)辦法，已知類條件概率密度 p(x|i) 參數(shù)表示式先驗(yàn)概率 P(i) 利用樣本預(yù)計(jì) p(x| i) 未知參數(shù)用貝葉斯規(guī)則將其轉(zhuǎn)換成后驗(yàn)概率 P(i|x) ，并依據(jù)后驗(yàn)概率大小進(jìn)行分類決議。第1頁第1頁處理實(shí)際問題辦法在實(shí)際中存在問題樣本特性空間類條件概率密度形式經(jīng)常很難擬定利用 Parzen 窗等非參數(shù)辦法恢復(fù)分布往往需要大量樣本，并且伴隨特性空間維數(shù)增長所需樣本數(shù)急劇增長。因此，在處理實(shí)際問題時(shí)，往往是利用樣本集直接設(shè)計(jì)分類器，而不恢復(fù)類條件概率密度。即采用判別函數(shù)，首先給定某個(gè)判別函數(shù)類，然后利用樣本集擬定出判別函數(shù)中未知參數(shù)。第2頁第2頁線性

2、判別函數(shù)線性判別函數(shù)法是一類較為簡樸判別函數(shù)。是統(tǒng)計(jì)模式辨認(rèn)基本辦法之一。它首先假定判別函數(shù) g(x) 是 x 線性函數(shù)，即 g(x)=wTx+ w0 ，對于 c 類問題，能夠定義 c 個(gè)判別函數(shù)， gi(x)=wiTx+ wi0 ， i=1,2 ， c 。用樣本去預(yù)計(jì)各 wi 和 wi0 ，并把未知樣本 x 歸到含有最大判別函數(shù)值類別中去。關(guān)鍵是如何利用樣本集求得 wi 和 wi0 。第3頁第3頁訓(xùn)練和學(xué)習(xí)“訓(xùn)練”和“學(xué)習(xí)” 在待辨認(rèn)模式中，挑選一批有代表性樣本，通過人工判讀，成為已知分類樣本，把這批樣本逐一輸入到計(jì)算機(jī)中“訓(xùn)練”程序或算法中，通過一次次迭代，最后得到正確線性判別函數(shù)。這樣迭

3、代過程稱之為訓(xùn)練過程，所構(gòu)成分類器稱為有些人監(jiān)督或有教師分類器。第4頁第4頁4.1.1 線性判別函數(shù)基本概念在正態(tài)分布Bayesian判別中，已經(jīng)碰到過在兩類情況下判別函數(shù)為線性情況。假設(shè)有1 和2 兩類模式，在二維模式特性空間可用始終線把這兩類模式劃分開，如圖 4.1 所表示。第5頁第5頁x1x2g(x) = w2x2+w1x1+w0 圖4.1兩類模式一個(gè)簡樸判別函數(shù)+劃分直線方程參數(shù)坐標(biāo)變量4.1.1 線性判別函數(shù)基本概念第6頁第6頁判別規(guī)則若給定一個(gè)未知類別模式x當(dāng)g(x)0 時(shí)，則決議 x 屬于1 ；當(dāng) g(x)0，因此決議面法向量是指向 R1 。因此，有時(shí)稱 R1 中任何 x 在 H

4、 正側(cè)，相應(yīng)地，稱 R2 中任何 x 在 H 負(fù)側(cè)。4.1.1 線性判別函數(shù)基本概念第12頁第12頁判別函數(shù) g(x) 是特性空間中某點(diǎn) x 到超平面距離一個(gè)代數(shù)量度。若把 x 表示成式中 xp ：是 x 在 H 上投影向量； r ：是 x 到 H 垂直距離；：是w方向上單位向量。4.1.1 線性判別函數(shù)基本概念第13頁第13頁若 x 為原點(diǎn)，則 g(x)=w0 (4-7)將 (4-7) 代入 (4-6) ，就得到從原點(diǎn)到超平面 H 距離 (4-6) 判別函數(shù) g(x) 是特性空間中某點(diǎn) x 到超平面距離一個(gè)代數(shù)量度。4.1.1 線性判別函數(shù)基本概念第14頁第14頁假如 w00 ，則原點(diǎn)在 H

5、 正側(cè)；若 w00 ，則原點(diǎn)在 H 負(fù)側(cè)。若w0=0 ，則 g(x) 含有齊次形式 wTx ，闡明超平面 H 通過原點(diǎn)。判別函數(shù) g(x) 是特性空間中某點(diǎn) x 到超平面距離一個(gè)代數(shù)量度。4.1.1 線性判別函數(shù)基本概念第15頁第15頁圖 4.2 對這些結(jié)果作了幾何解釋。4.1.1 線性判別函數(shù)基本概念第16頁第16頁結(jié)論利用線性判別函數(shù)進(jìn)行決議，就是用一個(gè)超平面把特性空間分割成兩個(gè)決議區(qū)域。超平面方向由權(quán)向量 w 擬定，它位置由閾值權(quán) w0 擬定。判別函數(shù) g(x) 正比于 x 點(diǎn)到超平面代數(shù)距離（帶正負(fù)號）當(dāng) x 在 H 正側(cè)時(shí)， g(x) 0 ，在負(fù)側(cè)時(shí)， g(x) 0 。4.1.1 線

6、性判別函數(shù)基本概念第17頁第17頁4.1.2 廣義線性判別函數(shù)如圖 4.3 所表示二類問題。設(shè)有一維樣本空間 X ，所希望劃分是：假如 xa ，則 x 屬于1 類；假如 b x0 ，則決議 x1g(x)0 ，則決議 x2二次判別函數(shù)可寫成下列普通形式g(x)=c0+c1x+ c2x2(4-10)假如適當(dāng)選擇 x y 映射，則可把二次判別函數(shù)化為 y 線性函數(shù)4.1.2 廣義線性判別函數(shù)第20頁第20頁式中稱為廣義判別函數(shù)，a叫做廣義權(quán)向量。 普通地，對于任意高次判別函數(shù) g(x)(這時(shí) g(x) 可看作對任意判別函數(shù)作級數(shù)展開，然后取其截尾部分迫近)，都能夠通過適當(dāng)變換，化為廣義線性判別函數(shù)來

7、處理。4.1.2 廣義線性判別函數(shù)第21頁第21頁存在問題通過變換后，維數(shù)大大增長了，這將使問題不久陷入所謂“維數(shù)劫難”。在統(tǒng)計(jì)學(xué)習(xí)理論中，對廣義線性分類器進(jìn)行研究，克服了“維數(shù)劫難”問題，進(jìn)而發(fā)展出了最新模式辨認(rèn)辦法支持向量機(jī)，成為處理有限樣本情況下非線性分類問題有效手段。4.1.2 廣義線性判別函數(shù)第22頁第22頁把 (4-1) 式定義線性判別函數(shù)寫成下面形式(4-12)增廣特性向量Augmented feature vector增廣權(quán)向量(廣義權(quán)向量)Augmented weight vector4.1.2 廣義線性判別函數(shù)第23頁第23頁結(jié)論y 與 x 相比，即使增長了一維，但保持了樣

8、本間歐氏距離不變，變換后樣本向量仍然所有位于 d 維子空間，即原 X 空間中，方程(4-13)在Y空間擬定了一個(gè)通過原點(diǎn)超平面 。它對 d 維子空間劃分與原決議面 wTx+ w0=0 對原 X 空間劃分完全相同。4.1.2 廣義線性判別函數(shù)第24頁第24頁例子這種辦法優(yōu)缺點(diǎn)可通過例子來闡明。考慮二次判別函數(shù)得到三維向量y從x到y(tǒng)映射如圖所表示。4.1.2 廣義線性判別函數(shù)第25頁第25頁例子4.1.2 廣義線性判別函數(shù)數(shù)據(jù)仍保持固有一維，由于改變x將造成y沿著一個(gè)三維曲線運(yùn)動。假如x服從某一個(gè)概率分布時(shí)，得到密度函數(shù)是退化，即曲線之外是0，在曲線上是無窮大，這是從低維空間到高維空間映射普遍問題

9、。第26頁第26頁例子4.1.2 廣義線性判別函數(shù)圖中映射y=(1,x,x2)T把一條直線映射為三維空間中一條拋物線。由于兩類問題，在三維空間中，一個(gè)平面就是一個(gè)分隔面。因此，由圖可見，這產(chǎn)生了原始一維x空間不連通性第27頁第27頁例子g(x)=1+x+ 2x2x0.5時(shí)g(x)0a=(-1, 1,2)T4.1.2 廣義線性判別函數(shù)由aTy=0定義平面將y空間分成兩個(gè)判別區(qū)域，如圖給出當(dāng)a=(-1,1,2)T時(shí)分類平面和x空間相應(yīng)判別區(qū)域。第28頁第28頁結(jié)論aTy=0在2維空間不穿過原點(diǎn)4.1.2 廣義線性判別函數(shù)一個(gè)三維增廣特性空間y和增廣權(quán)向量a(在原點(diǎn))。滿足aTy=0點(diǎn)集是一個(gè)穿過y

10、空間原點(diǎn)超平面(用紅色表示)，這個(gè)平面垂直于a。這個(gè)平面在其本來二維空間中不一定穿過原點(diǎn)(即立方體頂部虛線所表示判決邊界)。因此存在一個(gè)增廣權(quán)向量a，能夠取得x空間中任意鑒定線。第29頁第29頁4.1.3 設(shè)計(jì)線性分類器主要環(huán)節(jié)設(shè)計(jì)線性分類器，就是建立線性判別函數(shù)(4-l)式g(x) =wTx+w0或廣義線性判別函數(shù)(4-12)式這樣，設(shè)計(jì)線性分類器就轉(zhuǎn)化為，利用訓(xùn)練樣本集尋找準(zhǔn)則函數(shù)極值點(diǎn) 和 或 。第30頁第30頁設(shè)計(jì)線性分類器主要環(huán)節(jié)下列： 要有一組含有類別標(biāo)志樣本集X=x1，x2，xN。假如在樣本 xn 抽出后，把它看作一個(gè)擬定觀測值，則這組樣本集稱為擬定性樣本集；若把 xn 看作一個(gè)

11、隨機(jī)變量，則這組樣本集稱為隨機(jī)樣本集。有時(shí)也將樣本集 X 轉(zhuǎn)換成增廣樣本集 Y 來處理。4.1.3 設(shè)計(jì)線性分類器主要環(huán)節(jié)第31頁第31頁 要依據(jù)實(shí)際情況擬定一個(gè)準(zhǔn)則函數(shù) J 它必須滿足： J 值反應(yīng)分類器性能，它極值解則相應(yīng)于 最好 決議。 J是樣本集X和w、w0或 a 函數(shù)；設(shè)計(jì)線性分類器主要環(huán)節(jié)下列：4.1.3 設(shè)計(jì)線性分類器主要環(huán)節(jié)第32頁第32頁用最優(yōu)化技術(shù)求出準(zhǔn)則函數(shù)極值解 和 w*或a*。這樣就能夠得到線性判別函數(shù)或設(shè)計(jì)線性分類器主要環(huán)節(jié)下列：4.1.3 設(shè)計(jì)線性分類器主要環(huán)節(jié)第33頁第33頁4.2 Fisher線性判別Fisher線性判別函數(shù)是典型判別辦法之一，應(yīng)用非常廣泛。應(yīng)

12、用統(tǒng)計(jì)辦法處理模式辨認(rèn)問題時(shí)，困難之一是維數(shù)問題。在低維空間里行得通辦法，在高維空間里往往行不通。因此，減少維數(shù)有時(shí)就成為處理實(shí)際問題關(guān)鍵。第34頁第34頁在數(shù)學(xué)上通常能夠把 d 維空間樣本投影到一條直線上，形成一維空間，即把維數(shù)壓縮到一維。在普通情況下，總能夠找到某個(gè)方向，使在這個(gè)方向直線上，樣本投影能分開得最好。問題是如何依據(jù)實(shí)際情況找到這條最好、使最易于分類投影線。這就是Fisher法所要處理基本問題 (見圖 4.4) 。4.2 Fisher線性判別第35頁第35頁4.2 Fisher線性判別第36頁第36頁從 d 維空間到一維空間數(shù)學(xué)變換辦法假設(shè)有一集合 X 包括 N 個(gè) d 維樣本

13、x1 ， x2 ，xN ，其中 N1 個(gè)屬于1 類樣本記為子集 X1 ，N2 個(gè)屬于2 類樣本記為 X2 ，若對 xn 分量作線性組合可得標(biāo)量yn=wTxn, n=1 ， 2 ， Ni這樣便得到 N 個(gè)一維樣本 yn 構(gòu)成集合，并可分為兩個(gè)子集 Y1 和 Y2 。4.2 Fisher線性判別第37頁第37頁w* 就是最好投影方向從幾何上看，假如 |w|=1 ，則每個(gè) yn 就是相對應(yīng) xn 到方向?yàn)?w 直線上投影，實(shí)際上，w 絕對值是無關(guān)緊要，它僅使 yn 乘上一個(gè)百分比因子，主要是選擇 w 方向。w 方向不同，將使樣本投影后可分離程度不同，從而直接影響識別效果。因此，前述所謂尋找最好投影方

14、向問題，在數(shù)學(xué)上就是尋找最好變換向量 w*問題。4.2 Fisher線性判別第38頁第38頁定義幾種基本參量在 d 維 X 空間各類樣本均值向量mi， i =1，2 樣本類內(nèi)離散度矩陣 Si 和總類內(nèi)離散度矩陣 Sw，i =1，2 Sw=S1+ S24.2 Fisher線性判別第39頁第39頁樣本類間離散度矩陣SbSb=(m1 m2)(m1 m2)T其中 Sw 是對稱半正定矩陣，并且當(dāng) Nd 時(shí)通常是非奇異。Sb 也是對稱半正定矩陣，在兩類條件下，它秩最大等于 1 。定義幾種基本參量4.2 Fisher線性判別第40頁第40頁在一維 Y 空間各類樣本均值，i =1，2 樣本類內(nèi)離散度 和總類內(nèi)

15、離散度4.2 Fisher線性判別第41頁第41頁定義Fisher準(zhǔn)則函數(shù)希望投影后，在一維 Y 空間里各類樣本盡也許分得開些，即希望兩類均值之差越大越好；希望各類樣本內(nèi)部盡也許密集，即希望類內(nèi)離散度越小越好。因此，能夠定義Fisher準(zhǔn)則函數(shù)為：4.2 Fisher線性判別第42頁第42頁尋找使JF(w) 盡也許大 w 作為投影方向。但 JF(w)式并不顯含w，因此必須設(shè)法JF(w) 將變成w顯函數(shù)。盡也許大盡也許小Fisher準(zhǔn)則函數(shù)4.2 Fisher線性判別第43頁第43頁Fisher準(zhǔn)則函數(shù)4.2 Fisher線性判別第44頁第44頁Fisher準(zhǔn)則函數(shù)4.2 Fisher線性判別第

16、45頁第45頁Fisher準(zhǔn)則合理性：JF(w)只與投影方向相關(guān)，與大小無關(guān)若w是一個(gè)最優(yōu)解， kw也是最優(yōu)解，k是任何不為零常數(shù)。4.2 Fisher線性判別第46頁第46頁Fisher最佳投影方向求解：要求：Sw = S1 + S2正定。不然，存在投影方向w，使得wTSww=0，所有數(shù)據(jù)被投影到一點(diǎn)上。 JF(w)沒有極大值。求出最佳投影方向上任何一個(gè)w即可。JF(w)有上界，最佳投影方向一定存在！(Sb)max，(Sw)min分別是Sb，Sw矩陣最大、最小特性根。4.2 Fisher線性判別第47頁第47頁Fisher最佳投影方向求解：一定存在一個(gè)最優(yōu)w ，滿足wTSww=1，由于Sw

17、正定。無約束最優(yōu)化：等價(jià)于帶約束最優(yōu)化： max wTSbw wTSww=14.2 Fisher線性判別第48頁第48頁由于分母等于1是非零常數(shù)，wTSww=10定義 Lagrange 函數(shù)為JF(w)是廣義Rayleigh商，帶等式約束最優(yōu)化，能夠用Lagrange乘子法求解。Fisher最佳投影方向求解：4.2 Fisher線性判別第49頁第49頁式中 為Lagrange乘子，將上式對w求偏導(dǎo)數(shù)，得Fisher最佳投影方向求解：4.2 Fisher線性判別第50頁第50頁最優(yōu)解滿足：其中 w*就是 JF(w) 極值解。由于Sw非奇異，上式兩邊左乘 ，可得 Fisher最佳投影方向求解：4.

18、2 Fisher線性判別第51頁第51頁解上式是求普通矩陣 本征值問題。依據(jù)類間離散度Sb 定義，上式左邊 Sbw*能夠?qū)懗蒄isher最佳投影方向求解：注意 是一個(gè)數(shù)，因此 總是在向量(m1m2)方向上。4.2 Fisher線性判別第52頁第52頁只關(guān)懷投影方向：w*就是使Fisher準(zhǔn)則函數(shù)JF(w)取極大值時(shí)解，也就是d維X空間到一維Y空間最好投影方向。Fisher最佳投影方向求解：4.2 Fisher線性判別第53頁第53頁幾種分類閾值擬定均值中點(diǎn)法類樣本數(shù)加權(quán)法4.2 Fisher線性判別第54頁第54頁依據(jù)決議規(guī)則先驗(yàn)概率加權(quán)法就可判斷x屬于什么類別。y y0 x120，n=1，2

19、，N權(quán)向量a即可。a被稱作分離向量(separating vector)或解向量(solution vector)。 樣本規(guī)范化 4.3.1 幾種基本概念 線性可分性第63頁第63頁 解向量和解區(qū)解向量假如存在，則必在 正側(cè)，由于只有在正側(cè)才干滿足 。4.3.1 幾種基本概念 線性可分性第64頁第64頁 解向量和解區(qū)4.3.1 幾種基本概念 線性可分性第65頁第65頁4.3.2 梯度下降算法 ，n=1,2，N，設(shè)有一組樣本y1，y2，yN，其中yn是規(guī)范化增廣樣本向量，目是找一個(gè)解向量 a，使采用辦法是：定義一個(gè)準(zhǔn)則函數(shù)J(a)，當(dāng)a是解向量時(shí)，J(a)最小。標(biāo)量函數(shù)最小化問題用梯度下降法。第

20、66頁第66頁4.3.2 梯度下降算法 梯度下降法原理：從隨意選擇權(quán)向量a(1)開始，計(jì)算其梯度向量 J(a(1)， a(2)由自a(1)向下降最陡方向移一段距離得到。設(shè)定步長學(xué)習(xí)率(learn rate)或正百分比因子。取得權(quán)向量序列，使J(a)極小第67頁第67頁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 end4.3.2 梯度下降算法 第68頁第68頁其中H是赫森

21、矩陣，是J(a)在a(k)二階偏導(dǎo)：4.3.2 梯度下降算法 梯度下降法存在問題：如何選擇學(xué)習(xí)率(k)？假如(k)太小，收斂將非常慢；而假如(k)太大話也許會過沖(overshoot)，甚至發(fā)散。牛頓下降法：第69頁第69頁牛頓下降法：Algorithm 2 (Newton descent)1 begin initialize a; criterion 2 do3 a aH1J(a)4 until |H1J(a)| 5 return a6 end4.3.2 梯度下降算法 第70頁第70頁簡樸梯度下降法和牛頓下降法比較:簡樸梯度下降法牛頓(二階)算法每一步都給出更加好步長但求赫森逆矩陣計(jì)算量很大

22、4.3.2 梯度下降算法 第71頁第71頁4.3.3 感知器準(zhǔn)則函數(shù)(perceptron criterion function)結(jié)構(gòu)這樣一個(gè)準(zhǔn)則函數(shù)式中Yk是被權(quán)向量a錯(cuò)分類樣本集合。當(dāng)y被錯(cuò)分類時(shí)也就是說，當(dāng)且僅當(dāng)不存在錯(cuò)分樣本，即Yk為空集時(shí)第72頁第72頁4.3.3 感知器準(zhǔn)則函數(shù)求準(zhǔn)則函數(shù)梯度第73頁第73頁感知器準(zhǔn)則函數(shù)算法(批處理)：Algorithm 3 (Batch Perceptron)1 begin initialize a; (), criterion , k 02 do k k + 13 a a + (k) yYky4 until |(k) yYky| 0所表示不等式

23、組，4.4.1解線性不等式組共軛梯度法 第95頁第95頁為使解更可靠，引入余量b 0，那么規(guī)范化增廣樣本矩陣4.4.1解線性不等式組共軛梯度法 第96頁第96頁對于(4-47)式能夠定義準(zhǔn)則函數(shù) (4-47)N維向量4.4.1解線性不等式組共軛梯度法 第97頁第97頁假如 則 和 同號，因此， ，反之，假如有一些yi不滿足 ，則 和 異號，因此， 。不滿足yi越多， 越大。 4.4.1解線性不等式組共軛梯度法 第98頁第98頁顯然， 取極小值時(shí)a為最優(yōu)解a*。并且在不等式組一致情況下， ，在不等式組不一致情況下， 。 稱為最小錯(cuò)分樣本數(shù)準(zhǔn)則1。 4.4.1解線性不等式組共軛梯度法 第99頁第9

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

25、 (x)，最多用d步，就能夠使序列x收斂于f (x)極值解x*。4.4.1解線性不等式組共軛梯度法 第101頁第101頁因此，在沿d個(gè)(對于增廣空間則為d+1個(gè))互為共軛向量進(jìn)行一維搜索后，有也許達(dá)不到準(zhǔn)則函數(shù)最小值，即算法通過d(或d+1)步也許不收斂，這時(shí)就要重新開始計(jì)算，若用r表示重新開始周期，則r = d(或d+1)。由于 式定義準(zhǔn)則函數(shù)不是一個(gè)二次正定函數(shù)，而是一個(gè)分段二次正定函數(shù)，4.4.1解線性不等式組共軛梯度法 第102頁第102頁在任意點(diǎn) ， 負(fù)梯度方向可表示為4.4.1解線性不等式組共軛梯度法 令第103頁第103頁這種算法詳細(xì)環(huán)節(jié)下列：用k表示迭代步數(shù)，用 表示滿足于 不

26、等式數(shù)目， 表示最優(yōu)解。置k = 0，并任意給定初始權(quán)向量 ，計(jì)算 和 。 假如 ，則令然后繼續(xù)。 4.4.1解線性不等式組共軛梯度法 假如 ，則令 ，停止；假如 ，則令 ，停止；不然繼續(xù)。第104頁第104頁計(jì)算gk。假如gk=0，則停止；不然計(jì)算 ，然后繼續(xù)。 求k。假如k為r整數(shù)倍，則令k= 0；不然令k=1，并計(jì)算Sk表示第k次搜索時(shí)梯度下降方向。若 表示對 第一次迫近，則 。能夠證實(shí)，由上述表示式所產(chǎn)生S1，S2，對于二次函數(shù)中正定矩陣是互為共軛。4.4.1解線性不等式組共軛梯度法 第105頁第105頁尋找最佳步長vk，即計(jì)算使 取極小值時(shí)v。 令 ， 并計(jì)算 。 令k = k +

27、1，轉(zhuǎn)向環(huán)節(jié)2。 4.4.1解線性不等式組共軛梯度法 第106頁第106頁Nagaraja和Krishna證實(shí)，對于 表示分段二次函數(shù)，在 一致條件下，上述算法能夠在有限步內(nèi)使序列收斂于最優(yōu)解。4.4.1解線性不等式組共軛梯度法 而在 不一致條件下，只要適當(dāng)選擇b，使在 唯一極小點(diǎn) 上，有，i=1，2，N第107頁第107頁則該算法產(chǎn)生序列a也在有限步內(nèi)收斂于 a* 。對于 表示準(zhǔn)則函數(shù)，在不等式組不一致情況下，對一些樣本，也許存在 因此就產(chǎn)生了一個(gè)閾值問題。這時(shí)，由于 aTyi0，yi應(yīng)被正確分類；但又由于 aTyi0收斂于解a*。在不一致情況下，由于Jq1(a)是嚴(yán)格凸函數(shù)，其唯一極小點(diǎn)是

28、a=0，并且有4.4.1解線性不等式組共軛梯度法 第109頁第109頁因此，aTyi bi(i=1，2，N)條件不成立，因此得不到解向量a*。4.4.1解線性不等式組共軛梯度法 作為準(zhǔn)則函數(shù)來處理上述問題。顯然，這時(shí)存在下列關(guān)系： 第110頁第110頁也就是說，使 最小，同在終止條件和 下使 最小是等價(jià)。這時(shí)需要將上述算法環(huán)節(jié)1和4改變下列：4.4.1解線性不等式組共軛梯度法 通過原有算法得到一個(gè)收斂點(diǎn)，記為 ，并以此作為補(bǔ)充算法起點(diǎn)。計(jì)算 和 ，并且繼續(xù)。第111頁第111頁能夠證實(shí)，這樣得到Sk仍然是 下降方向。同時(shí)能夠證實(shí)，假使Ya0是不一致，且在求Jq1(a)最小值過程中用環(huán)節(jié)代替原算

29、法環(huán)節(jié)4，若所得序列a是有限，則序列最后一個(gè)元素就相稱于F(a)一個(gè)局部最小值解。4.4.1解線性不等式組共軛梯度法 第112頁第112頁若序列是無限，則它趨向于F(a)一個(gè)局部最小值解。在進(jìn)行上述計(jì)算時(shí)，由于我們使用原算法收斂點(diǎn)as 作為起始點(diǎn)，它經(jīng)常是全局最優(yōu)解F(a)一個(gè)較好迫近，故能夠得到全局最優(yōu)解。4.4.1解線性不等式組共軛梯度法 第113頁第113頁4.4.2解線性不等式組搜索法 考慮齊次線性不等式組其中 矩陣 為規(guī)范化增廣樣本矩陣，每一行yi代表一個(gè)樣本，N為樣本數(shù)，為yi維數(shù)。且有第114頁第114頁式中 事實(shí)上是 所滿足不等式數(shù)目。稱之為最小錯(cuò)分樣本數(shù)準(zhǔn)則2。使Jq2(a)

30、取最大值a就是要求解 a*?，F(xiàn)在定義另一個(gè)形式最小錯(cuò)分樣本數(shù)準(zhǔn)則下列： 4.4.2解線性不等式組搜索法 第115頁第115頁因此，N個(gè)樣本向量所建立超平面把權(quán)空間劃分成為凸多棱錐有限集合，每個(gè)錐C都由有限個(gè)支撐超平面所構(gòu)成。對于每個(gè)yi，方程yia =0在權(quán)空間中建立了一個(gè)超平面Hi，并且所有超平面都通過原點(diǎn)。構(gòu)成錐一部分超平面，或超平面截取部分，稱為錐“前沿”，歐氏空間Ed中 個(gè)超平面交叫做錐棱。4.4.2解線性不等式組搜索法 第116頁第116頁圖4.10示出三維凸多棱錐及其前沿和棱一個(gè)例子。C+C+C+C原點(diǎn)前沿棱圖 4.10并且某個(gè)錐C中任何權(quán)向量對樣本集劃分都是相同，或者說，某個(gè)錐中

31、所有權(quán)向量所滿足不等式數(shù)目是相同。 錐C中每一個(gè)點(diǎn)，都相應(yīng)一個(gè)權(quán)向量a4.4.2解線性不等式組搜索法 第117頁第117頁假如某個(gè)錐C中任何權(quán)向量都能使上式準(zhǔn)則函數(shù)為最大，那么就稱這個(gè)錐為最小錯(cuò)誤錐，記為C*。這樣，求使最多數(shù)目的不等式得到滿足權(quán)向量 問題，就轉(zhuǎn)化為尋找一個(gè)或多個(gè)最小錯(cuò)誤錐C*問題了。由于對于每個(gè)CEd，存在著對稱反射，即 維權(quán)向量 和 所產(chǎn)生分類情況正好相反，因此，假如對于某個(gè)存在4.4.2解線性不等式組搜索法 第118頁第118頁其中則必有 。由于我們只關(guān)懷最小錯(cuò)誤錐，因此，我們只限于研究使錐就能夠了。假如碰到情況，則用 代替 。 那些4.4.2解線性不等式組搜索法 第119頁第119頁尋找最小錯(cuò)誤錐C*搜索算法。 定理 假設(shè)Y滿足Haar(Y每個(gè) 子陣秩都是 )條件，令 是Ed中任何一條棱上權(quán)