《神經(jīng)網(wǎng)絡(luò)》課件第10章

10.1統(tǒng)計學(xué)習(xí)理論的一般概念10.2最優(yōu)化理論基礎(chǔ)10.3支持向量機10.4支持向量機的實現(xiàn)

10.5

SVM在故障診斷中的應(yīng)用

10.6小結(jié)

習(xí)題

在第3章，我們研究了由反向傳播算法訓(xùn)練的多層感知器。在第8章，我們研究了另一類分層前饋網(wǎng)絡(luò)，即徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)。這兩種神經(jīng)網(wǎng)絡(luò)按它們自己的方式都可以稱為通用函數(shù)逼近器。本章我們將討論基于統(tǒng)計學(xué)習(xí)理論而發(fā)展的一種新的通用學(xué)習(xí)方法——支持向量機(SupportVectorMachine，SVM)。像多層感知器網(wǎng)絡(luò)和徑向基函數(shù)網(wǎng)絡(luò)一樣，支持向量機也能用于模式分類和非線性回歸。10.1統(tǒng)計學(xué)習(xí)理論的一般概念

基于數(shù)據(jù)的機器學(xué)習(xí)是現(xiàn)代智能技術(shù)中的重要方面，它研究從觀測數(shù)據(jù)(樣本)出發(fā)尋找規(guī)律，并利用這些規(guī)律對未來數(shù)據(jù)或無法觀測的數(shù)據(jù)進行預(yù)測。機器學(xué)習(xí)的過程就是構(gòu)建學(xué)習(xí)機的過程。機器學(xué)習(xí)含有多種方法，如決策樹、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)、隱Markov鏈(HMM)等。迄今為止，關(guān)于機器學(xué)習(xí)還沒有一種被共同接受的理論框架，關(guān)于其實現(xiàn)方法大致可以分為下述三種。第一種是經(jīng)典的(參數(shù))統(tǒng)計估計方法，包括模式識別、神經(jīng)網(wǎng)絡(luò)等在內(nèi)?，F(xiàn)有機器學(xué)習(xí)方法共同的重要理論基礎(chǔ)之一是統(tǒng)計學(xué)，參數(shù)方法正是基于傳統(tǒng)統(tǒng)計學(xué)的。在這種方法中，參數(shù)的相關(guān)形式是已知的，練樣本用來估計參數(shù)的值。這種方法存在很大的局限性：首先，它需要已知樣本分布形式，這需要花費很大代價；其次，傳統(tǒng)統(tǒng)計學(xué)研究的是樣本數(shù)目趨于無窮大時的漸近理論，現(xiàn)有學(xué)習(xí)方法也多是基于此假設(shè)，但在實際問題中，樣本數(shù)往往是有限的，因此一些理論上很優(yōu)秀的學(xué)習(xí)方法在實際中的表現(xiàn)卻可能不盡人意。第二種方法是經(jīng)驗非線性方法，如人工神經(jīng)網(wǎng)絡(luò)(ANN)。這種方法利用已知樣本建立非線性模型，克服了傳統(tǒng)參數(shù)估計方法的困難。但是，這種方法缺乏一種統(tǒng)一的數(shù)學(xué)理論。

第三種方法是20世紀60年代后期發(fā)展起來的統(tǒng)計學(xué)習(xí)理論(StatisticalLearningTheory，SLT)，它是一種專門研究有限樣本情況下非參數(shù)估計問題的機器學(xué)習(xí)理論。與傳統(tǒng)統(tǒng)計學(xué)相比，該理論針對有限樣本統(tǒng)計問題建立了一套新的理論體系，在這種體系下的統(tǒng)計推理規(guī)則不僅考慮了對漸近性能的要求，而且追求在現(xiàn)有有限信息的條件下得到最優(yōu)結(jié)果。統(tǒng)計學(xué)習(xí)理論是建立在一套較堅實的理論基礎(chǔ)之上的，為解決有限樣本學(xué)習(xí)問題提供了一個統(tǒng)一的框架。它能將很多現(xiàn)有方法納入其中，有望幫助解決許多原來難以解決的問題(比如神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)選擇問題、局部極小點問題等)；同時，在這一理論基礎(chǔ)上發(fā)展了一種新的通用學(xué)習(xí)方法——支持向量機，它已初步表現(xiàn)出很多優(yōu)于已有方法的性能。一些學(xué)者認為，SLT和SVM正在成為繼神經(jīng)網(wǎng)絡(luò)研究之后新的研究熱點，并將推動機器學(xué)習(xí)理論和技術(shù)的重大發(fā)展。10.1.1機器學(xué)習(xí)問題的表示

機器學(xué)習(xí)的目的是根據(jù)給定的訓(xùn)練樣本求取系統(tǒng)輸入、輸出之間依賴關(guān)系的估計，使它能夠?qū)ο到y(tǒng)行為做出盡可能準確的預(yù)測。機器學(xué)習(xí)問題的基本模型可以用圖10-1表示。其中，系統(tǒng)S是我們研究的對象，它在給定輸入x下得到一定的輸出y，LM是我們所求的學(xué)習(xí)機，其輸出為。圖10-1機器學(xué)習(xí)的基本模型定義10.1設(shè)變量y與變量x之間存在一定的未知依賴關(guān)系，即遵循某一未知的聯(lián)合概率分布P(x,y)，機器學(xué)習(xí)問題就是根據(jù)l個獨立同分布(i.i.d)的觀測樣本：

(x1,y1),(x2,y2),…,(xl,yl)(10-1)在一組函數(shù){f(x,ω)}中按某個準則選擇一個最優(yōu)的函數(shù)f(x,ω0)對依賴關(guān)系進行估計，其中，ω是參數(shù)；而f(x,ω)就是一個學(xué)習(xí)機(LearningMachine，LM)。如果對于給定的輸入x和ω的一個選擇，其輸出f(x,ω)總是相同的，則這個學(xué)習(xí)機f(x,ω)是確定性的(Deterministic)，否則稱為不確定性的(Uncertainty)對于確定性學(xué)習(xí)機中的ω的一個特定選擇，就稱其為訓(xùn)練過的學(xué)習(xí)機(TrainedMachine)。

定義10.2

對于一個學(xué)習(xí)機，損失函數(shù)(LossFunction)

L(y,f(x,ω))表示用f(x,ω)對y進行預(yù)測而造成的損失。有三類基本的機器學(xué)習(xí)問題，即模式識別、函數(shù)逼近和概率密度估計，不同類型的學(xué)習(xí)問題有不同形式的損失函數(shù)。

(1)模式識別問題(這里僅討論監(jiān)督模式識別問題)：輸出變量y是類別標號。在兩類情況下，

y={0,1}或{-1,1}是二值函數(shù)，這時f(x,ω)稱為指示函數(shù)(IndicatorFunction)，也稱為判別函數(shù)。模式識別問題中損失函數(shù)的一般定義為(10-2)

(2)函數(shù)逼近問題(回歸問題)：輸出變量y是連續(xù)變量(這里假設(shè)為單值函數(shù))，損失函數(shù)一般定義為

L(y,f(x,ω))=(y-f(x,ω))2(10-3)

即采用最小平方誤差準則。

(3)概率密度估計問題：學(xué)習(xí)的目的是根據(jù)訓(xùn)練樣本確定x的概率密度，設(shè)估計的密度函數(shù)為p(x,ω)，則損失函數(shù)一般定義為

L(p(x,ω))=－logp(x,ω)(10-4)10.1.2經(jīng)驗風(fēng)險最小化

定義10.3

對于一個學(xué)習(xí)機，損失函數(shù)的期望：

R(ω)=∫L(y,f(x,ω))dP(x,y)(10-5)

稱為期望風(fēng)險(ExpectedRisk)或真實風(fēng)險(ActualRisk)。而經(jīng)驗風(fēng)險(EmpiricalRisk)

則是訓(xùn)練集上的平均誤差，即：

(10-6)學(xué)習(xí)的目標在于使期望風(fēng)險最小化，但是，期望風(fēng)險R(ω)要依賴聯(lián)合概率P(x,y)的信息，實際問題中無法計算。因此傳統(tǒng)的學(xué)習(xí)方法中采用了所謂經(jīng)驗風(fēng)險最小化(ERM)準則，即用樣本定義經(jīng)驗風(fēng)險如式(10-6)所示。作為對式(10-5)的估計，設(shè)計學(xué)習(xí)算法使它最小化。對于損失函數(shù)式(10-2)，經(jīng)驗風(fēng)險就是訓(xùn)練樣本錯誤率；對于式(10-3)的損失函數(shù)，經(jīng)驗風(fēng)險就是平方訓(xùn)練誤差；而采用式(10-4)，損失函數(shù)的ERM準則就等價于最大似然方法。事實上，神經(jīng)網(wǎng)絡(luò)與其他經(jīng)典學(xué)習(xí)算法將ERM準則視為當然的出發(fā)點，并未研究其合理性、適用范圍、可達到的近似質(zhì)量等理論問題，只是直觀上想當然的做法。如此做法存在以下幾個問題：

(1)經(jīng)驗風(fēng)險最小不等于期望風(fēng)險最小，不能保證學(xué)習(xí)機的推廣能力。算法或方法對未來輸出進行正確預(yù)測的能力稱為推廣能力或泛化能力。

(2)從概率論中的大數(shù)定律可知，經(jīng)驗風(fēng)險只有在樣本數(shù)無窮大時才趨近于期望風(fēng)險，需要非常多的樣本才能保證學(xué)習(xí)機的性能。

(3)某些情況下，當經(jīng)驗風(fēng)險過小時，推廣能力反而下降，這就是神經(jīng)網(wǎng)絡(luò)中令人頭疼的所謂過學(xué)習(xí)(Overfitting)問題。

(4)使經(jīng)驗風(fēng)險最小的點與期望風(fēng)險最小的點并非同一個點(如圖10-2所示)。圖10-2期望風(fēng)險與經(jīng)驗風(fēng)險之間的關(guān)系圖在早期神經(jīng)網(wǎng)絡(luò)研究中，人們總是把注意力集中在如何使Remp更小，但很快發(fā)現(xiàn)，一味追求小的訓(xùn)練誤差并不是總能達到好的預(yù)測效果。在某些情況下，訓(xùn)練誤差過小反而會導(dǎo)致推廣能力的下降，即出現(xiàn)過學(xué)習(xí)現(xiàn)象。之所以出現(xiàn)過學(xué)習(xí)現(xiàn)象，一是因為學(xué)習(xí)樣本不充分，二是學(xué)習(xí)機設(shè)計不合理，這兩個問題是相互關(guān)聯(lián)的。假設(shè)我們有一組訓(xùn)練樣本(x,y)，x分布在實數(shù)范圍內(nèi)，而y取值在[0,1]之間，那么不論這些樣本是依據(jù)什么函數(shù)模型產(chǎn)生的，只要我們用一個函數(shù)f(x,α)來擬合這些樣本，其中α是待定參數(shù)，總能夠找到一個α使訓(xùn)練誤差為零，如圖10-3所示，但顯然這個“最優(yōu)函數(shù)”不能正確代表原來的函數(shù)模型。原因就是試圖用一個復(fù)雜的模型來擬合有限的樣本，結(jié)果導(dǎo)致喪失了推廣能力。在神經(jīng)網(wǎng)絡(luò)中，如果對于有限的訓(xùn)練樣本來說網(wǎng)絡(luò)的學(xué)習(xí)能力過強，足以記住每一個訓(xùn)練樣本，此時經(jīng)驗風(fēng)險很快可以收斂到很小甚至零，但卻根本無法保證它對新的樣本能夠得到好的預(yù)測。這就是有限樣本下學(xué)習(xí)機的復(fù)雜性與推廣性之間的矛盾。圖10-3用三角函數(shù)擬合任意點的例子由此可看出，有限樣本情況下：①經(jīng)驗風(fēng)險最小并不一定意味著期望風(fēng)險最??；②學(xué)習(xí)機的復(fù)雜性不但應(yīng)與所研究的系統(tǒng)有關(guān)，而且要和有限數(shù)目的樣本相適應(yīng)。我們需要一種能夠指導(dǎo)我們在小樣本情況下建立有效的學(xué)習(xí)和推廣方法的理論。10.1.3學(xué)習(xí)機的VC維與風(fēng)險界

統(tǒng)計學(xué)習(xí)理論就是研究小樣本統(tǒng)計估計和預(yù)測的理論。它從理論上較系統(tǒng)地研究了經(jīng)驗風(fēng)險最小化原則成立的條件、有限樣本下經(jīng)驗風(fēng)險與期望風(fēng)險的關(guān)系及如何利用這些理論找到新的學(xué)習(xí)原則和方法等問題。其主要涉及的內(nèi)容包括：

(1)經(jīng)驗風(fēng)險最小化準則下統(tǒng)計學(xué)習(xí)一致性的條件；

(2)在這些條件下關(guān)于統(tǒng)計學(xué)習(xí)方法推廣性的界的結(jié)論；

(3)在這些界的基礎(chǔ)上建立的小樣本歸納推理準則；

(4)實現(xiàn)新的準則的實際方法(算法)。

其中，最有指導(dǎo)性的理論結(jié)果是推廣性的界，與此相關(guān)的一個核心概念是VC維(VapnikChervonenkisDimension)。

經(jīng)驗風(fēng)險Remp(ω)到期望風(fēng)險R(ω)的一致收斂性理論包括收斂速度的解，它們基于稱為VC維的重要參數(shù)。VC維是由學(xué)習(xí)機實現(xiàn)的分類函數(shù)族的容量或表示能力的測度。

在給出VC維定義之前，首先討論線性分類問題。兩類問題的分類通常用一個實值函數(shù)按照這樣的方式操作：當f(x)≥0時，輸入x∈X被標記為正類，否則被標記為負類。

考慮f(x)，x∈X是線性函數(shù)的情況，函數(shù)可以寫

(10-7)其中w是一個n維權(quán)值向量，b是偏置，學(xué)習(xí)算法意味著一定要從數(shù)據(jù)中學(xué)習(xí)到這些參數(shù)。決策規(guī)則由sgn(f(x))給出，sgn(·)是一符號函數(shù)，即：這類假設(shè)的幾何解釋是，wTx+b=0定義的判別邊界將輸入空間X分為兩半(見圖10-4)。當n=2時，二維情況的判別邊界為一直線；當n=3時，判別邊界為一平面;n>3時，則判別邊界為一超平面。超平面是維數(shù)為n-1的仿射子空間，它將輸入空間分為兩部分，這兩部分對應(yīng)輸入中的兩類。在圖10-4中，當b的值變化時，超平面平行于自身移動。因此，如果想表達Rn中的所有可能超平面，包括n+1個可調(diào)參數(shù)的表達式是必要的。圖10-4二維情況下的分類超平面定義10.4考慮兩類分類問題，其中函數(shù)f(x,w)∈{0,1}，。對于給定的一組l個點，可以按所有2l個可能的方式進行標識；對于每一個可能的標識，如果在{f(w)}中總能取得一個函數(shù)，這個函數(shù)能夠用來正確地區(qū)分這些標識，則稱這l個點構(gòu)成的點集能夠被{f(w)}分隔(Shattered)。函數(shù)族{f(w)}的VC維定義為能夠被{f(w)}分隔的訓(xùn)練點l的最大數(shù)目。若對任意數(shù)目的樣本都有函數(shù)能夠?qū)⑺鼈兎指?，則函數(shù)集的VC維是無限大的。用更熟悉的話說，分類函數(shù)集{f(w)}的VC維是能被機器學(xué)習(xí)的訓(xùn)練樣本的最大數(shù)量，這種學(xué)習(xí)對于分類函數(shù)所有可能的二分標記是無錯誤的。VC維反映了函數(shù)集的學(xué)習(xí)能力，VC維越大則學(xué)習(xí)機越復(fù)雜(容量越大)。遺憾的是，目前尚沒有通用的關(guān)于任意函數(shù)集VC維計算的理論，只對一些特殊的函數(shù)集知道其VC維。比如在n維實數(shù)空間中線性分類器和線性實函數(shù)的VC維是n+1。為了說明Rn中超平面集合的VC維是n+1這一結(jié)論，考慮圖10-5所描述的二維空間(即n=2)的情況。在圖10-5(a)中，對于空間的任意三個點的集合{x1,x2,x3}，分為“左”、“上”、“下”，而且有8種(23)可能的標記。對于這些標記，總可以找到一組有向直線將不同的標記點進行分隔(注意標識不是

賦值)。在圖10-5(b)中，對于空間的四個點的集合{x1,x2,x3,

x4}，點x2和x3標記為0，點x1和x4標記為1?？墒沁@一次，我們看到點x1和x4不能用一條直線與點x2和x3分隔開來。式(10-7)中所描述的n=2判定規(guī)則的VC維是3。圖10-5二維空間的VC維(a)三個點被有向直線分隔;(b)四個點不能被有向直線分隔注：在Rn中至少可以找到一組n+1個點能夠被超平面分隔，但不是任意一組n+1個點都能夠被超平面分隔。例如將所有點集中在一條直線上的情況就不能被分隔。我們不加證明地給出下述有用的定理。定理10.1

Rn中兩個點集能夠被一個超平面分隔的充分與必要條件是其凸包(包含該點集的最小凸集)的交集為空集。

定理10.2考慮Rn中l(wèi)個點的集合，選擇其中任意一點作為原點，那么l個點能夠被超平面分隔的充分與必要條件是除了原點外其余點的位置向量是線性獨立的。

統(tǒng)計學(xué)習(xí)理論系統(tǒng)地研究了對于各種類型的函數(shù)集，經(jīng)驗風(fēng)險和實際風(fēng)險之間的關(guān)系，即推廣性的界。關(guān)于兩類分類問題，結(jié)論是：對指示函數(shù)集中的所有函數(shù)(包括使經(jīng)驗風(fēng)險最小的函數(shù))，經(jīng)驗風(fēng)險Remp(ω)和實際風(fēng)險R(ω)之間滿足如下關(guān)系。

定義10.5對于一個學(xué)習(xí)機，假定損失函數(shù)以概率1-η取值，其中0≤η≤1，那么下面的誤差界成立：其中h是學(xué)習(xí)機的VC維，l是樣本數(shù)目。不等式(10-8)的右邊稱為風(fēng)險界(RiskBound)，它由兩部分組成:第一項是經(jīng)驗風(fēng)險(訓(xùn)練誤差);另一部分稱為置信范圍，它和學(xué)習(xí)機的VC維及訓(xùn)練樣本數(shù)有關(guān)，是隨l/h增大而減小的函數(shù)。實際風(fēng)險可以簡單地表示為(10-9)它表明，在有限訓(xùn)練樣本下，學(xué)習(xí)機器的VC維越高(復(fù)雜性越高),則置信范圍越大，導(dǎo)致實際風(fēng)險與經(jīng)驗風(fēng)險之間可能的差別越大。這就是為什么會出現(xiàn)過學(xué)習(xí)現(xiàn)象的原因。機器學(xué)習(xí)過程不但要使經(jīng)驗風(fēng)險最小，還要使VC維盡量小以縮小置信范圍，才能取得較小的實際風(fēng)險，即對未來樣本有較好的推廣性。關(guān)于風(fēng)險界，需要指出，推廣性的界是對于最壞情況的結(jié)論，在很多情況下是較松的，尤其當VC維較高時更是如此。而且，這種界只在對同一類學(xué)習(xí)函數(shù)進行比較時有效，可以指導(dǎo)我們從函數(shù)集中選擇最優(yōu)的函數(shù)，在不同函數(shù)集之間比較卻不一定成立。10.1.4結(jié)構(gòu)風(fēng)險最小化

下面將討論結(jié)構(gòu)風(fēng)險最小化(StructuralRiskMinimiza

tion，SRM)問題。由學(xué)習(xí)機的風(fēng)險界的構(gòu)成看到，要控制學(xué)習(xí)機的實際風(fēng)險，必須同時控制經(jīng)驗風(fēng)險和置信范圍。

因為VC維是整數(shù)，難以使其平滑變化，于是，結(jié)構(gòu)風(fēng)險最小化的思想是，將函數(shù)集構(gòu)造為一個函數(shù)子集序列，使各個子集按照VC維的大小(亦即的大小)排列；在每個子集中尋

找最小經(jīng)驗風(fēng)險，在子集間折中考慮經(jīng)驗風(fēng)險和置信界限，取得實際風(fēng)險最小。具體方法如下：

令z=(x,y)代表輸入、輸出樣本數(shù)據(jù)對，將函數(shù)L(y,f(x,w))簡記為Q(z,w)。選擇函數(shù)Q(z,w)，使其具有一種嵌套結(jié)構(gòu)：

其中Sk={Q(z,w):滿足第k種約束}為函數(shù)集的子集，其VC維hk為有限的。在此結(jié)構(gòu)中，嵌套子集按其復(fù)雜度(即VC維大小)的順序排列：(10-10)此外，還要求子集Sk中的函數(shù)有界。此時機器學(xué)習(xí)的任務(wù)是在每個子集中尋找經(jīng)驗風(fēng)險最小的同時，在子集間折中考慮經(jīng)驗風(fēng)險和置信范圍，使得實際風(fēng)險最小，如圖10-6所示。圖10-6按VC維排序使函數(shù)嵌套的結(jié)構(gòu)風(fēng)險最小

SRM原理實際上提供了一種對于給定的樣本數(shù)據(jù)在近似精度和模型近似函數(shù)復(fù)雜性之間折中的定量方法，即在近似函數(shù)集的結(jié)構(gòu)中找出一個最佳子集，使實際風(fēng)險確保上界達到極小。實現(xiàn)SRM原則可以有兩種思路：一是在每個子集中求最小經(jīng)驗風(fēng)險，然后選擇使最小經(jīng)驗風(fēng)險和置信范圍之和最小的子集；二是設(shè)計函數(shù)集的某種結(jié)構(gòu)使每個子集中都能取得最小的經(jīng)驗風(fēng)險(如使訓(xùn)練誤差為0)，然后只需選擇適當?shù)淖蛹怪眯欧秶钚?，則這個子集中使經(jīng)驗風(fēng)險最小的函數(shù)就是最優(yōu)函數(shù)，支持向量機方法實際上就是這種思想的具體實現(xiàn)。例如神經(jīng)網(wǎng)絡(luò)的構(gòu)造過程，函數(shù)集為(10-12)其中y是估計對象的實際輸出，是神經(jīng)網(wǎng)絡(luò)的輸出。若隱節(jié)點數(shù)可變，則函數(shù)集(10-12)式具有嵌套結(jié)構(gòu)：(10-13)其中Sk={Q(z,w):滿足第k種約束}中的神經(jīng)網(wǎng)絡(luò)都具有相同的結(jié)構(gòu)，隱節(jié)點數(shù)為k，其近似函數(shù)為(10-14)已經(jīng)證明，上述神經(jīng)網(wǎng)絡(luò)的VC維數(shù)取決于S函數(shù)的類型和權(quán)重的數(shù)目，并且在一般條件下是有界的(盡管它可能很大)。因此在選定的嵌套結(jié)構(gòu)式(10-13)中，子集是按VC維數(shù)(即近似函數(shù)的復(fù)雜性)遞增的順序排列的，符合SRM歸納原理的要求。通常神經(jīng)網(wǎng)絡(luò)的設(shè)計，首先利用已有的先驗知識或經(jīng)驗確定隱節(jié)點數(shù)目，從SRM原理的觀點來看，這就是選定了一個子集Sk，該子集中所有的函數(shù)有一個確定不變的VC維數(shù)，即f(l/h)確定；隨后通過訓(xùn)練確定最優(yōu)權(quán)值，相當于最小化經(jīng)驗風(fēng)險Remp(ω)。目前存在的問題是神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的確定大多是憑經(jīng)驗選取的，有一定的盲目性，無法確定泛化的置信界限，所以無法保證網(wǎng)絡(luò)的泛化能力。即使經(jīng)驗誤差很小，但可能推廣或泛化能力很差。這就是神經(jīng)網(wǎng)絡(luò)中的過學(xué)習(xí)難題。10.2最優(yōu)化理論基礎(chǔ)

最優(yōu)化理論是數(shù)學(xué)上的一個分支，它研究某些數(shù)學(xué)上定義的問題的最優(yōu)解。根據(jù)特定的代價函數(shù)和約束的本質(zhì)，可以得出許多類最優(yōu)化問題，這些問題已經(jīng)過深入研究并找到了很有效的解決方法。為了訓(xùn)練支持向量機，其中涉及到線性約束、二次目標函數(shù)等問題。10.2.1二次規(guī)劃

凸性在最優(yōu)化理論和方法的研究中起著重要作用。本節(jié)簡要地介紹凸集和凸函數(shù)的基本概念和基本結(jié)果。

定義10.6(凸集)設(shè)集合，如果對任意x1,x2∈X，有：(10-15)則稱X是凸集。這個定義表明，如果x1、x2屬于凸集X，則連接x1和x2的線段仍屬于X。

定義10.7(凸組合)設(shè)x1,…,xl∈Rn，若：其中，，αi≥0，i=1,…,l；則稱x是x1,…,xl的一個凸組合。定理10.3(凸集的充要條件)集合是凸集的充分必要條件是X中任意若干點的任一凸組合仍屬于X?，F(xiàn)舉例說明：

【例10-1】超平面是凸集，其中w∈Rn是非零向量，b∈R。

事實上，對任意的x1，x2∈H和α∈[0,1]，有：

wT(αx1+(1-α)x2)+b=0

故(αx1+(1-α)x2)∈H

【例10-2】閉半空間H-={x|wTx≤β}和H+={x|wTx≥β}為凸集。

注意到對任意x1，x2∈H-和α∈[0,1]，有：

wT(αx1+(1-α)x2)=αwTx1+(1-α)wTx2≤β

故(αx1+(1-α)x2)∈H-,其余類似。

定理10.4

若X1和X2是凸集，則交集X1∩X2也是凸集。

【例10-3】由有限個半閉空間的交組成的集合

叫多面集，即

其中wi是非零向量；βi是數(shù)。則該多面集是閉凸集。定義10.8(凸函數(shù))設(shè)集合是非空凸集，f是定義在X上的函數(shù)。稱函數(shù)f是X上的凸函數(shù)，如果對任意的x1，x2∈X，α∈(0,1),都有：

f(αx1+(1-α)x2)≤αf(x1)+(1-α)f(x2)

(10-17)

稱f為X上的嚴格凸函數(shù)。如果對任意x1≠x2時,則式(10-17)中

的嚴格不等號成立。

凸函數(shù)的定義表示兩點的線性插值大于函數(shù)值，其幾何解釋為，一個凸函數(shù)的圖形總是位于相應(yīng)弦的下方。如果凸函數(shù)是可微的，可以用下面的特征描述凸函數(shù)。定理10.5(凸函數(shù)的充要條件)設(shè)X是非空凸集，f(x)是X上的可微函數(shù)，則f(x)是凸函數(shù)的充要條件是，對任意的X中的點，都有

(10-18)

類似地，f(x)是嚴格凸函數(shù)的充要條件是，對于任意的X中的點，都有：

(10-19)

定理10.5表明了根據(jù)局部導(dǎo)數(shù)的線性近似是函數(shù)的低估。

定理10.6

考慮Rn上的二次函數(shù)：

(10-20)

其中G是n×n矩陣，r是n維向量，δ是實數(shù)。若G是半正定矩陣，則f(x)是Rn上的凸函數(shù)；若G是正定矩陣，則f(x)是Rn上的嚴格凸函數(shù)。定義10.9

一般的最優(yōu)化問題描述如下：

這里f(x)稱為目標函數(shù)，剩下的關(guān)系分別稱為不等式約束和等式約束。目標函數(shù)的最優(yōu)值稱為最優(yōu)化問題的值。

對目標函數(shù)和約束的本質(zhì)的不同假設(shè)會產(chǎn)生不同的優(yōu)化問題。

定義10.10對于目標函數(shù)，等式或不等式約束都是凸函數(shù)的最優(yōu)化問題稱為凸約束問題。對于目標函數(shù)是二次的，而約束都是線性函數(shù)下的最優(yōu)化問題，稱為二次規(guī)劃問題。(10-21)定義10.11

可行區(qū)域是指目標函數(shù)的約束滿足的區(qū)域，可以表示為

最優(yōu)化問題的解是指存在一個點，使得不存在其他的點x∈Ω滿足

。這個點也稱為f(x)全局最小。如果滿足，并且，滿足，那么點稱為f(x)局部最小。(10-22)

定理10.7考慮凸約束問題。設(shè)Ω是問題的可行域，

則：

(1)若問題有局部解，則是問題的全局解；

(2)問題的全局解組成的集合是凸集；

(3)若問題有局部解，f(x)是Ω上的嚴格凸函數(shù)，則

是問題的唯一全局解。

為了訓(xùn)練支持向量機(SVM)，只考慮線性約束、凸二次目標函數(shù)的問題，并且

Ω∈Rn，即考慮處理凸二次規(guī)劃問題。下一小節(jié)將介紹拉格朗日(Lagrange)乘子技術(shù)及其擴展，并將其限制在二次規(guī)劃問題之內(nèi)。

10.2.2拉格朗日理論

解決約束非線性規(guī)劃問題的方法大致有三類：直接處理約束、用線性規(guī)劃逼近、轉(zhuǎn)化成無約束問題。拉格朗日(Lagrange)乘子法是一種將約束問題變?yōu)闊o約束優(yōu)化問題的方法，它揭示了條件極值的基本特性，也是最優(yōu)準則法的理論基礎(chǔ)?，F(xiàn)在來尋求目標函數(shù)z=f(x,y)在約束條件為φ(x,y)=0下,在點(x0,y0)取得極值的必要條件。因(x0,y0)是條件極值點，故有：

j(x0,y0)=0(10-23)

設(shè)函數(shù)f(x,y)與j

(x,y)在點(x0,y0)的某個鄰域內(nèi)有連續(xù)的偏導(dǎo)數(shù)，并且φy(x,y)≠0。由隱函數(shù)存在定理可知，方程j(x,y)=0確定一個具有連續(xù)導(dǎo)數(shù)的函數(shù)y=y(x)，將其代入到目標函數(shù),有：

z=f(x,y)=f(x,y(x))(10-24)由于函數(shù)f(x,y)在(x0,y0)處取得極值，從而函數(shù)f(x,y(x))在x=x0處取得極值，必有：(10-25)由隱含數(shù)求導(dǎo)公式：將其代入(10-25)式有：(10-26)式(10-23)和式(10-26)就是函數(shù)z=f(x,y)在點(x0,y0)處取得極值的必要條件。記則上述條件可寫成：(10-27)根據(jù)以上分析，引進函數(shù)：(10-28)此函數(shù)稱為拉格朗日函數(shù)，其中λ叫做拉格朗日乘子。從式(10-27)不難看出，(x0,y0)適合方程組：

Lx=0,Ly=0,Lλ=0(10-29)

即(x0，y0)是拉格朗日函數(shù)的駐點。

設(shè)函數(shù)f(x,y)與j(x,y)有連續(xù)的偏導(dǎo)數(shù)，作拉格朗日函數(shù)

L(x,y,λ)=f(x,y)+λj(x,y)，如果(x0,y0)是方程組(10-27)

的解，則點(x0,y0)是目標函數(shù)z=f(x,y)在約束條件j(x,y)=0下的可疑極值點。

現(xiàn)在考慮最一般的情況，最優(yōu)化問題既包含等式約束又包含不等式約束。首先，給出廣義拉格朗日的定義。定義10.12

給定一個在域上的最優(yōu)化問題：(10-30)定義廣義拉格朗日函數(shù)為(10-31)其中αi(i=1,…,k)、βi(i=1,…,m)為拉格朗日乘子。在約束問題的最優(yōu)解中，包含了對應(yīng)的拉格朗日乘子向量。如果能事先知道這個拉格朗日乘子，常常會減少求解原始約束問題的困難，這產(chǎn)生了求解約束問題的一個新途徑——對偶方法。定義10.13

定義10.12中原問題的拉格朗日對偶問題如下：

這里θ(α,β)=infx∈ΩL(x,α,β)，目標函數(shù)在最優(yōu)解的值稱為問題的解。(我們使用“下確界inf”而不使用“極小值min”，原因是可能不存在極小值。)

下面根據(jù)弱對偶定理及兩個推論，給出原問題和對偶問題的基本關(guān)系。(10-32)定理10.8令x∈Ω是定義10.12中原問題的一個可行解，而(α,β)是定義10.13中對偶問題的可行解,則f(x)≥θ(α,β)。

推論1

對偶問題的值的上界由原問題的值給出：

sup{θ(α,β)|α≥0}≤inf{f(x)|g(x)≤0,h(x)=0}

推論2

如果f(x′)=θ(α′,β′)，其中α′≥0，并且

g(x′)≤0,h(x′)=0，則x′和(α′,β′)分別是原問題和對偶問題的解。在這種情況下,i=1,…,k。

注：原問題的解和對偶問題的解的值之差稱為對偶間隙。檢測對偶間隙消失的方法是鞍點的出現(xiàn)。

定理10.9對于原問題，三元組(x′,α′,β′)是拉格朗日方程的鞍點，當且僅當其組成是原問題和對偶問題的最優(yōu)解并且沒有對偶間隙時，原問題和對偶問題的值關(guān)系為

f(x′)=θ(α′,β′)

現(xiàn)在提出強對偶定理，該定理保證對于討論的最優(yōu)化的原問題和對偶問題有相同的值。

定理10.10給定域Ω∈Rn上的最優(yōu)化問題：

其中g(shù)i和hi是仿射函數(shù)，也就是對于某個矩陣A和向量b有：

其對偶間隙為零。

下面介紹Kuhn-Tucker定理，該定理給出了一般的最優(yōu)化問題有最優(yōu)解的條件。定理10.11

給定一個定義在凸域上的最優(yōu)化問題：

其中f是可微且凸函數(shù)，gi和hi是仿射函數(shù)，一般地，一個點x′是最優(yōu)點的充分必要條件是存在滿足：其中L是廣義拉格朗日函數(shù)。注：上式中的第三個關(guān)系稱為KarushKuhnTucker互補條件(簡稱KKT條件)。它意味著對于積極約束(或有效約束)，有，但是對于非積極約束(或非有效約束)，有。10.2.3二次規(guī)劃的對偶

使用拉格朗日理論理解凸最優(yōu)化問題可以使用一個對偶表示替代原問題，該對偶問題通常比原問題更易處理。因為直接處理不等式約束是困難的。對偶問題通過引入又稱為對偶變量的拉格朗日乘子來解。對偶方法來源于將對偶變量作為問題的基本未知量的思想。下面把對偶性應(yīng)用到凸二次目標函數(shù)的一個重要而特殊的場合，這是對偶性的一種實際應(yīng)用。定理10.12

考慮二次規(guī)劃問題(10-33)其中G是一個n×n正定矩陣，，，。假設(shè)可行域非空，則這個問題可重寫為：在x上的最小值是無約束的，最小值在x=-G-1(ATα+r)上得到。將該式代入原問題，得到其對偶形式：(10-34)注：二次規(guī)劃的對偶形式是另一個二次規(guī)劃問題，但是其約束更為簡單。二次規(guī)劃問題已成為支持向量機理論的標準技術(shù)，并且鋪平了從最優(yōu)化理論到算法技術(shù)的道路。進一步的問題是，KKT互補條件意味著只有積極約束有非零對偶變量，這就意味著一些最優(yōu)化問題的實際變量數(shù)目要比全部訓(xùn)練集的規(guī)模小很多。后面將使用到的“支持向量”這個術(shù)語是指那些對偶變量非零的訓(xùn)練樣本。10.3支持向量機

前面兩節(jié)已經(jīng)介紹了支持向量機的基礎(chǔ)理論知識，而要使理論在實際中發(fā)揮作用，還要求它能夠?qū)崿F(xiàn)，這就是所謂的支持向量機(SupportVectorMachine，SVM)方法。這也是統(tǒng)計學(xué)習(xí)理論中最“年輕”的部分，其主要內(nèi)容在1992~1995年間基本完成，目前仍處于不斷發(fā)展階段。因為它從某種意義上可以表示成類似神經(jīng)網(wǎng)絡(luò)的形式，所以支持向量機在起初也曾被稱為支持向量網(wǎng)絡(luò)。什么是SVM？這個問題首先應(yīng)從模式識別開始講解。10.3.1分類超平面的幾何性質(zhì)

假定f(x)=wTx+b=0決定一個決策界面，當f(x)為線性時，這個決策界面便是一個超平面H。其中w是超平面H的法向

量，決定超平面的方向；b決定超平面的位置。一般來說，超平面H把輸入空間分成兩個半空間,即R1、R2空間。當x在R1空間時，f(x)>0,指向R1，為H的正側(cè)；反之為H的負側(cè),如圖10-7所示。圖10-7超平面的幾何解釋超平面具有以下性質(zhì)：

(1)w與H正交(如圖10-7所示)。

假設(shè)x1和x2是H上的兩個向量，因為，則，向量必在H上，所以w與(x1-x2)垂直，即w與H正交。

(2)任意點x∈Rn到超平面的代數(shù)距離，即f(x)正比于x到H的代數(shù)距離。

證明：任意點x到超平面H的距離為(10-35)點s在超平面H上滿足，用Lagrange乘子法解決約束最優(yōu)問題。令非負變量，建立Lagrange函數(shù)：(10-36)J(s,λ)對s和λ求微分并置結(jié)果等于零，得：(10-37)令xi-si=ti，代入上式，得：(10-38)解得，于是：(10-39)對于點x，若f(x)>0，則x點為H的正側(cè)；若f(x)<0，則x點為H的負側(cè)。因此，點x到超平面的代數(shù)距離為(10-40)

(3)原點到超平面的代數(shù)距離

，即原點到H的代數(shù)距離與偏置b成正比。

證明：因為f(x)=wTx+b=b(x=0)，所以。

(4)若b>0，則H在原點的正側(cè)；若b<0，則H在原點的負側(cè)；若b=0，則f(x)=wTx，說明超平面H通過原點。10.3.2線性可分支持向量機

設(shè)兩類問題訓(xùn)練樣本集為S=(x1,y1),(x2,y2),…,(xl,yl)，其中xi∈Rn，yi={1,-1},i=1,…,l。問題線性可分是指，存在著超平面wTx+b=0，使得訓(xùn)練樣本中的正類輸入和負類輸入分別位于該超平面的兩側(cè),或者說存在著參數(shù)對(w,b),使得：yi=sgn(wTxi+b)i=1,…,l(10-41)

觀察圖10-8，存在許多決策超平面都可以將兩類樣本分開。我們應(yīng)該選擇哪一個呢？圖10-8用超平面劃分兩類的情況假定劃分直線的法向已經(jīng)給定，如圖10-9所示。直線H1是一條以w為法向量且能正確劃分兩類樣本的直線。顯然這樣的直線并不唯一，如果平行地向右上方或左下方推移直線H1，直到碰到某類訓(xùn)練點,這樣就得到了兩條極端直線H2和H3，在直線H2和H3之間的平行直線都能正確劃分兩類。顯然在H2和H3中間的那條直線H為最好。圖10-9最優(yōu)分類超平面以上給出了在已知法向量w1的情況下構(gòu)造劃分直線的方法。這樣就把問題歸結(jié)為尋求法向量w1的問題。

假如此時H表示為，因為其在中間，顯然H2、H3可以分別表示為

(10-42)

兩邊同除以k，令，b1/k=b，則H表示為wTx+b=0，H2、H3分別變換為

wTx+b=-1,wTx+b=1(10-43)上述過程稱為劃分超平面的規(guī)范化過程。那么，此時兩條直線H2和H3之間的間隔為(10-44)如前所述，對于適當?shù)姆ㄏ蛄?，會有兩條極端的直線，這兩條直線之間有間隔，最優(yōu)分類直線就應(yīng)該是間隔最大的那個法向量所表示的超平面。即分類平面應(yīng)該使兩類之間的間隔最大(m最大)，同時滿足下面的約束條件：(10-45)因此可以將求取最優(yōu)平面問題轉(zhuǎn)化為下列優(yōu)化問題?？紤]一個線性可分訓(xùn)練集S，尋找最優(yōu)參數(shù)對(w,b)的過程，可轉(zhuǎn)化為下列的約束優(yōu)化問題：(10-46)這是一個二次歸化問題，上式也可以寫成如下形式：(10-47)現(xiàn)在考慮如何采用10.2節(jié)的策略將優(yōu)化問題轉(zhuǎn)化為相應(yīng)的對偶問題。原始拉格朗日函數(shù)為

這里αi≥0是約束的拉格朗日乘子。因為都是不等式約束，所以這些乘子都是非負的。

通過對相應(yīng)的w和b求偏導(dǎo)，可以找到相應(yīng)的對偶形式：

(10-48)(10-49)將得到的關(guān)系式：(10-50)代入到原始拉格朗日函數(shù)，得到：(10-51)由優(yōu)化理論中的對偶理論知，最小化式(10-48)等于最大化以式(10-48)約束的拉格朗日乘子為變量的式(10-51),即：(10-52)這是一個凸二次規(guī)劃問題，有全局最優(yōu)解。求解得到權(quán)重向量的最優(yōu)解為

(10-53)同時因為這個優(yōu)化問題的最優(yōu)解必須滿足如下KKT條件，條件要求最優(yōu)解α′，w′,b′必須滿足：

(10-54)任取αi≠0，可求得b。由上式可知，結(jié)果可得大部分αi為零。將αi不為零所對應(yīng)的樣本稱為支持向量(SupportVector，SV)。因此在權(quán)重向量的表達式中，只有這些點包括在內(nèi)，即式(10-53)變?yōu)?10-55)這樣優(yōu)化超平面就可以表示為(10-56)線性可分支持向量機說明如下：

(1)分類超平面由支持向量確定。也就是說，只需少量樣本就可構(gòu)成最優(yōu)分類面，而且定量給出了每個訓(xùn)練點在所得解中的重要性。不是支持向量的點沒有影響，在未退化的情況下，這些點輕微的擾動不影響解。

(2)對偶目標函數(shù)和最優(yōu)分類面有一個顯著的特性，就是數(shù)據(jù)僅出現(xiàn)在內(nèi)積中。這為使用核技術(shù)在特征空間中找到并使用超平面成為可能。

(3)Vapnik證明線性分類器VC維滿足：

h≤‖w‖2r2+1

(10-57)

式中r為包絡(luò)訓(xùn)練樣本的最小球半徑。這說明，SVM在使訓(xùn)練樣本被正確劃分的同時，又最小化了分類面的VC維；SVM體現(xiàn)了結(jié)構(gòu)風(fēng)險最小化的思想，所以具有較好的泛化能力。10.3.3近似線性可分支持向量機

最大間隔分類器是一個很重要的概念，是分析和構(gòu)造更加復(fù)雜的支持向量機的起點，但它在許多實際應(yīng)用中并不完全使用。如果數(shù)據(jù)有噪聲，輸入空間(特征空間)一般不能線性可分。最大間隔分類器的主要問題使它總是完美地產(chǎn)生一個沒有訓(xùn)練誤差的一致假設(shè)。當訓(xùn)練集近似線性可分時，任何劃分超平面的方法都必有錯分，所以不能再要求訓(xùn)練點滿足約束條件yi(wTxi+b)≥1,i=1,…,l。為此，對i個訓(xùn)練點(xi,yi)引入松弛變量，把約束條件放松為yi(wTxi+b)≥1-ζi,i=1,…,l。顯然向量ζ=(ζ1,ζ2,…,ζl)T體現(xiàn)了訓(xùn)練集被錯分的情況?？梢圆捎?/p>

作為一種度量，描述訓(xùn)練集被錯分的程度。這樣，現(xiàn)在就有兩個目標：仍希望間隔2/‖w‖盡可能大,同時希望錯分程度

盡可能小。引進懲罰參數(shù)C把兩個目標綜合為一個目標，即極小化：上式的目標函數(shù)實質(zhì)上由兩部分組成:一部分是控制分類器的VC維(h)，另一部分是經(jīng)驗風(fēng)險。實踐中，懲罰系數(shù)C>0是對分類錯誤的懲罰，用于調(diào)整置信范圍和經(jīng)驗誤差間的均衡。C增大，則被壓制，經(jīng)驗風(fēng)險小。(10-58)

ζi是優(yōu)化理論中的松弛變量，圖10-10顯示了兩個誤分點對應(yīng)于標準超平面的間隔松弛變量。特別地，若xi沒有錯分，則ζi=0。圖10-10分類問題中的松弛變量近似線性可分支持向量機的原優(yōu)化問題：(10-59)同樣，我們可以得到近似線性可分的對偶表示，即：(10-60)對比線性可分情況與近似線性可分情況的對偶表示，二者最大化的目標函數(shù)是相同的；不同之處在于，約束條件αi≥0被替換為條件更強的0≤αi≤C。10.3.4非線性可分支持向量機

超平面的分類能力畢竟有限，為此需要考慮分離曲面。令x為輸入空間的向量，則通過事先確定的非線性映射函數(shù)：

f:x→f(x),Rn→F

(10-61)

把x映射到一個高維特征空間F，然后在F空間求最優(yōu)分類超平面，如圖10-11所示。

圖10-11簡化分類任務(wù)的特征映射可以注意到，在上面的支持向量機算法的對偶表示中，不論是尋優(yōu)目標函數(shù)式(10-52)還是最優(yōu)的超平面式(10-56)，都只涉及訓(xùn)練樣本之間的內(nèi)積運算。如果能夠找到一個函數(shù)k使得k(xi,xj)=(xi)Tf(xj)，這樣在特征空間F實際上只需進行內(nèi)積運算；而這種內(nèi)積運算是可以用原輸入空間中的函數(shù)實現(xiàn)的，我們甚至沒有必要知道非線性函數(shù)的具體形式。這實際上就是支持向量機的另一吸引人的地方，即核的表示方法。通過選擇使用恰當?shù)暮撕瘮?shù)來代替內(nèi)積，可以隱式地將訓(xùn)練數(shù)據(jù)非線性映射到高維特征空間，以增強線性分類器的計算能力。

[例10-4]考慮二維輸入空間的情況。設(shè)一非線性映射函數(shù)將輸入空間的點映射到三維特征空間，非線性函數(shù)為：

任選輸入空間兩點和，這樣該兩點在特征空間的內(nèi)積為：如定義核函數(shù)為輸入空間兩點內(nèi)積的平方，則：因此，有：滿足Mercer條件的常用核函數(shù)：

(1)多項式核函數(shù)

(2)徑向基核函數(shù)

(3)Sigmoid核函數(shù)或?qū)τ诜蔷€性分類問題，首先將輸入樣本經(jīng)非線性隱函數(shù)投影到某個特征空間。變換后在空間的分類平面為：尋找最優(yōu)參數(shù)對的過程，可轉(zhuǎn)化為下列的約束優(yōu)化問題：(10-62)(10-63)類似線性情況，引入拉格朗日乘子后，優(yōu)化方程為：所得分類超平面為：(10-64)(10-65)以上在解決非線性可分問題過程中，其特點是在原空間構(gòu)造一個核函數(shù)使之等于變換后空間的內(nèi)積運算，盡管通過非線性變換將樣本數(shù)據(jù)映射到高維甚至無窮維空間，并在高維空間中構(gòu)造最優(yōu)分類超平面，但在求解最優(yōu)化問題和計算分類平面時并不需要顯式計算該非線性函數(shù)，甚至不需知道其具體形式，而只需計算函數(shù)。

[例10-5]若有5個數(shù)據(jù)點分別為：且第1、2和5為正類，第3和4為負類，即：定義多項式核函數(shù)為優(yōu)化方程為利用二次規(guī)劃算法，求得：因此，支持向量是。分類判別函數(shù)為其中，b的求解按照、或，并且在，可得：分類判別函數(shù)(見圖10-12)為：圖10-12分類曲線支持向量機算法的基本步驟如下：

(1)訓(xùn)練樣本歸一化；

(2)選擇合適的核函數(shù)k(xi,xj)；

(3)確定核函數(shù)參數(shù)及懲罰系數(shù)C；

(4)執(zhí)行訓(xùn)練算法，并求得拉格朗日系數(shù)αi，i=1,…,l；(5)得到分類判別函數(shù)。10.3.5支持向量回歸機支持向量的方法應(yīng)用于回歸問題，仍保留了最大間隔算法的所有主要特征：非線性函數(shù)可以通過高維特征空間中的線性學(xué)習(xí)算法得到，同時系統(tǒng)的容量由與特征空間維數(shù)不相關(guān)的參數(shù)控制；同分類算法一樣，學(xué)習(xí)算法要最小化一個凸函數(shù)，并且它的解是稀疏的。

1.ε不敏感損失函數(shù)

若以魯棒性為設(shè)計目標，對于任何魯棒性的數(shù)值度量必須考慮到由于微小噪聲的影響而可能產(chǎn)生最大性能退化。這需要定義一個損失函數(shù)，它可以忽略真實值某個上下范圍內(nèi)的誤差,可以描述為(10-66)其中ε是指定的參數(shù)，損失函數(shù)Lε(d,y)稱為ε不敏感損失函數(shù)(ε-insensitiveLossFunction)。如果估計器輸出y和期望輸出d的偏差的絕對值小于ε，則損失函數(shù)等于零，否則它等于偏差絕對值減去ε。圖10-13說明了Lε(d,y)和誤差d-y的依賴關(guān)系。探討ε不敏感損失函數(shù)的另一個動機是如同分類SVM一樣，它可以確保對偶變量的稀疏性。使用訓(xùn)練點的一個小的子集表示解可帶來很大的計算優(yōu)勢，同時確保全局最小解的存在和可靠泛化界的優(yōu)化。圖10-13ε不敏感損失函數(shù)

2.非線性SVR考慮非線性回歸模型，標量d對向量x的依賴可描述為

d=f(x)+v(10-67)其中f(·)是自變量的一個確定性函數(shù)，加性噪聲v統(tǒng)計獨立于輸入向量x，二者的統(tǒng)計特性是未知的。我們將所有可用的信息描述成一組訓(xùn)練數(shù)據(jù)，其中xi是輸入向量x的一個樣本值，di是模型輸出d的相應(yīng)值，l為樣本個數(shù)。如果在線性函數(shù)集合f(x)=(w·f(x))+b中估計回歸函數(shù)，求解問題的經(jīng)驗風(fēng)險為其中是高維特征空間的點?？梢砸雰山M非負的松弛變量和描述式(10-66)定義的e不敏感損失函數(shù)，有：(10-68)(10-69)

ε-SVR就是在式(10-69)約束下，求下式的最小化代價泛函數(shù)：其中，懲罰因子C是事先給定的參數(shù)。為了構(gòu)造相應(yīng)的對偶問題，定義Lagrange乘子ai、，上面的凸二次規(guī)劃問題可轉(zhuǎn)化為求解下式的新形式：(10-71)式中是滿足Mercer定理的內(nèi)積核。注意同模式識別問題的解一樣，Lagrange乘子中僅有一部分不為零，對應(yīng)的數(shù)據(jù)點定義為支持向量(SupportVector，SV)。e和兩者都必須由用戶選擇，和控制的估計函數(shù)為：(10-72)

e和C選擇的原則方法一直是一個未解決的研究領(lǐng)域。從概念上講，e和C選擇的提出和模式分類中參數(shù)C的選擇具有同樣的復(fù)雜性。然而，在實際應(yīng)用中回歸的復(fù)雜性控制是一個更困難的問題，這是由于，①參數(shù)e和C必須同時調(diào)整；②回歸本質(zhì)上比模式分類更困難。10.4支持向量機的實現(xiàn)

支持向量機所涉及到的數(shù)學(xué)知識是比較難的，自己編程實現(xiàn)該算法難度就更大了。但是現(xiàn)在的網(wǎng)絡(luò)資源非常發(fā)達，而且國際上的科學(xué)研究者把他們的研究成果已經(jīng)放在網(wǎng)絡(luò)上，免費提供給用于研究目的，這樣方便大多數(shù)的研究者，不必要花費大量的時間理解SVM算法的深奧數(shù)學(xué)原理和計算機程序設(shè)計。目前有關(guān)SVM計算的相關(guān)軟件有很多，如LIBSVM、mySVM、SVMLight等，這些軟件大部分的免費下載地址和簡單介紹都可以在/上獲得。10.4.1

LIBSVM軟件包簡介

LIBSVM是臺灣大學(xué)林智仁博士開發(fā)設(shè)計的一個簡單、易于使用和快速有效地SVM模式識別與回歸的軟件包。他不僅提供了LIBSVM的C＋＋語言的算法源代碼，還提供了Python、Java、MATLAB、LabVIEW等語言的接口，可以方便的在Windows或UNIX平臺下使用，也便于人們根據(jù)自己的需要進行改進(例如設(shè)計使用符合自己特定問題需要并且在進行模型參數(shù)選擇時可以繪制出交叉驗證精度的等高線圖)。另外還提供了WINDOWS平臺下的可視化操作工具SVM-toy。LIBSVM軟件包可以在.tw/~cjlin/免費獲得。

LIBSVM可以解決分類問題(包括C-SVC、n-SVC)、回歸問題(包括e-SVR、n-SVR)以及分布估計(one-class-SVM)等問題，提供了線性、多項式、徑向基和S形函數(shù)四種常用的核函數(shù)供選擇。SVM用于模式識別或回歸時，SVM方法及其參數(shù)、核函數(shù)及其參數(shù)的選擇，目前國際上還沒有形成一個統(tǒng)一的模式，也就是說最優(yōu)SVM算法、參數(shù)選擇還只能是憑借經(jīng)驗、實驗對比、大范圍的搜尋或者利用軟件包提供的交互檢驗功能進行尋優(yōu)。10.4.2

LIBSVM使用方法

LIBSVM在給出源代碼的同時還提供了Windows操作系統(tǒng)下的可執(zhí)行文件，包括：進行SVM訓(xùn)練的svmtrain.exe；根據(jù)已獲得的SVM模型對數(shù)據(jù)集進行預(yù)測的svmpredict.exe；以及對訓(xùn)練數(shù)據(jù)與測試數(shù)據(jù)進行簡單縮放操作的svmscale.exe。它們都可以直接在DOS環(huán)境中使用。如果下載的包中只有C++的源代碼，則也可以自己在VC等軟件上編譯生成可執(zhí)行文件。

LIBSVM使用的一般步驟是：⑴按照LIBSVM軟件包所要求的格式準備數(shù)據(jù)集；⑵對數(shù)據(jù)進行簡單的縮放操作；⑶考慮選用RBF核函數(shù)；⑷采用交叉驗證選擇最佳參數(shù)與；⑸采用最佳參數(shù)與對整個訓(xùn)練集進行訓(xùn)練獲取SVM模型；⑹利用獲取的模型進行測試與預(yù)測。

1)LIBSVM使用的數(shù)據(jù)格式該軟件使用的訓(xùn)練數(shù)據(jù)和檢驗數(shù)據(jù)文件格式如下：<label><index1>:<value1><index2>:<value2>…其中<label>是訓(xùn)練數(shù)據(jù)集的目標值，對于分類，它是標識某類的整數(shù)(支持多個類)；對于回歸，是任意實數(shù)。<index>是以1開始的整數(shù)，可以是不連續(xù)的；<value>為實數(shù)，也就是我們常說的特征值或自變量。檢驗數(shù)據(jù)文件中的label只用于計算準確度或誤差，如果它是未知的，只需用一個數(shù)填寫這一欄，也可以空著不填。在程序包中，還包括有一個訓(xùn)練數(shù)據(jù)實例：heart_scale，方便參考數(shù)據(jù)文件格式以及練習(xí)使用軟件。

2)

svmscale.exe的用法對數(shù)據(jù)集進行縮放，其目的是：⑴避免一些特征值范圍過大而另一些特征值范圍過??；⑵避免在訓(xùn)練時為了計算核函數(shù)而計算內(nèi)積的時候引起數(shù)值計算的困難，通常將數(shù)據(jù)縮放到[-1,1]或者是[0,1]之間。指令格式：svmscale[-llower][-uupper][-yy_lower

y_upper]

[-ssave_filename][-rrestore_filename]

filename

(缺省值：lower=-1，upper=1，沒有對y進行縮放)其中，-l：數(shù)據(jù)下限標記；lower：縮放后數(shù)據(jù)下限；-u：數(shù)據(jù)上限標記；upper：縮放后數(shù)據(jù)上限；-y：是否對目標值同時進行縮放；y_lower為下限值，y_upper為上限值；-ssave_filename：表示將縮放的規(guī)則保存為文件save_filename；-rrestore_filename：表示將縮放規(guī)則文件restore_filename載入后按此縮放；filename：待縮放的數(shù)據(jù)文件(要求滿足前面所述的格式)?？s放規(guī)則文件可以用文本瀏覽器打開，看到其格式為：lowerupper；lval1uval1；lval2uval2其中的lower與upper與使用時所設(shè)置的lower與upper含義相同；index表示特征序號；lval為該特征對應(yīng)轉(zhuǎn)換后下限lower的特征值；uval為對應(yīng)于轉(zhuǎn)換后上限upper的特征值。數(shù)據(jù)集的縮放結(jié)果在此情況下通過DOS窗口輸出，當然也可以通過DOS的文件重定向符號“>”將結(jié)果另存為指定的文件。使用實例：⑴svmscale–strain3.rangetrain3>train3.scale表示采用缺省值(即對屬性值縮放到[-1,1]的范圍，對目標值不進行縮放)，對數(shù)據(jù)集train3進行縮放操作，其結(jié)果縮放規(guī)則文件保存為train3.range，縮放集的縮放結(jié)果保存為train3.scale。⑵svmscale–rtrain3.rangetest3>test3.scale表示載入縮放規(guī)則train3.range后按照其上下限對應(yīng)的特征值和上下限值線性的地對數(shù)據(jù)集test3進行縮放，結(jié)果保存為test3.scale。

3.

svmtrain的用法

svmtrain實現(xiàn)對訓(xùn)練數(shù)據(jù)集的訓(xùn)練，獲得SVM模型。指令格式：svmtrain[options]training_set_file[model_file]其中，options(操作參數(shù))：可用的選項即表示的涵義如下所示。

(1)-ssvm類型：設(shè)置SVM類型，默認值為0，可選類型有：

0－C-SVC

1－n-SVC

2－one-class-SVM

3－e-SVR

4－n-SVR

(2)-t核函數(shù)類型：設(shè)置核函數(shù)類型，默認值為2，可選類型有：

0－線性核

1－多項式核

2－RBF核

3－sigmoid核

(3)-ccost：設(shè)置C-SVC、e-SVR、n-SVR中的懲罰系數(shù)C，默認值為1；

(4)-nn：設(shè)置n-SVC、one-class-SVM與n-SVR中參數(shù)n，默認值0.5；

(5)-pe：設(shè)置n-SVR的損失函數(shù)中的e，默認值為0.1；

(6)-mcachesize：設(shè)置cache內(nèi)存大小，以MB為單位，默認值為40；

(7)-ee：設(shè)置終止準則中的可容忍偏差，默認值為0.001；

(8)-hshrinking：是否使用啟發(fā)式，可選值為0或1，默認值為1；

(9)-b概率估計：是否計算SVC或SVR的概率估計，可選值0或1，默認0；

(10)-wiweight：對各類樣本的懲罰系數(shù)C加權(quán)，默認值為1；

(11)-vn：n折交叉驗證模式。

操作參數(shù)-v隨機地將數(shù)據(jù)剖分為n部分并計算交叉檢驗準確度和均方根誤差。以上這些參數(shù)設(shè)置可以按照SVM的類型和核函數(shù)所支持的參數(shù)進行任意組合，如果設(shè)置的參數(shù)在函數(shù)或SVM類型中沒有也不會產(chǎn)生影響，程序不會接受該參數(shù)；如果應(yīng)有的參數(shù)設(shè)置不正確，參數(shù)將采用默認值。training-set-file是要進行訓(xùn)練的數(shù)據(jù)集；model-file是訓(xùn)練結(jié)束后產(chǎn)生的模型文件，該參數(shù)如果不設(shè)置將采用默認的文件名，也可以設(shè)置成自己慣用的文件名。使用實例：svmtraintrain3.scaletrain3.model表示訓(xùn)練train3.scale，將模型保存為文件train3.model，并在dos窗口中輸出如下結(jié)果：

optimizationfinished,＃iter=1756

nu=0.464223

obj=-551.002342,rho=-0.337784

nSV=604,nBSV=557

TotalnSV=604其中，＃iter為迭代次數(shù)；nu與前面的操作參數(shù)－nn相同；obj為SVM文件轉(zhuǎn)換的二次規(guī)劃求解得到的最小值；rho為判決函數(shù)的常數(shù)項b；nSV為支持向量個數(shù)；nBSV為邊界上的支持向量個數(shù)；TotalnSV為支持向量總個數(shù)。訓(xùn)練后的模型保存為文件train3.model，用記事本等文本瀏覽器打開可以看到其內(nèi)容。

4.svmpredict的用法

svmpredict根據(jù)訓(xùn)練獲得的模型，對數(shù)據(jù)集合進行預(yù)測。指令格式：svmpredict[options]test-filemodel-fileoutput-file

options(操作參數(shù))bprobability-estimates：是否需要進行概率估計預(yù)測，可選值為0或者1，默認值為0。

model-file是由svmtrain產(chǎn)生的模型文件；test-file是要進行預(yù)測的數(shù)據(jù)文件；output-file是svmpredict的輸出文件，表示預(yù)測的結(jié)果值。svmpredict沒有其它的選項。

應(yīng)用LIBSVM，需要依次運行svmscale.exe，svmtrain.exe，svmpredict.exe等命令，其實更簡單的方法是使用easy.py，可以很方便地從MATLAB中用dos或system命令調(diào)用。10.4.3SVM在MATLAB中的實現(xiàn)

SVM的研究方興未艾，有關(guān)SVM計算的軟件有很多，其中STPRtool是另外一種應(yīng)用廣泛的軟件包?，F(xiàn)舉例說明其用法。

Riply數(shù)據(jù)集是一個用來檢驗分類算法性能的標準數(shù)據(jù)集，該數(shù)據(jù)集分為兩類，訓(xùn)練樣本數(shù)為250，測試樣本數(shù)為1000。由于測試樣本數(shù)遠大于訓(xùn)練樣本數(shù)，因而測試結(jié)果可以反映算法的泛化性能。具體程序如下(本例M文件見光盤中的FLch10eg1)，其中核函數(shù)選用徑向基核函數(shù)(RBF)，核參數(shù)s=1，懲罰因子C=10。圖10-14表示訓(xùn)練結(jié)果，“×”為正類，“○”為負類，大圓圈的樣本為支持向量。圖10-14SVM對訓(xùn)練集分類結(jié)果trn=load(’riply_trn’);

%loadtrainingdataoptions.ker=’rbf’;

%useRBFkerneloptions.arg=1;

%kernelargumentoptions.C=10;

%regularizationconstantmodel=smo(trn,options);

%trainSVMclassifierppatterns(trn);%visualizationpsvm(model);tst=load(’riply_tst’);%loadtestingdataypred=svmclass(tst.X,model);%classifydata10.5

SVM在故障診斷中的應(yīng)用

系統(tǒng)的故障診斷某種程度上可以理解為模式識別過程。設(shè)被測對象全部可能發(fā)生的狀態(tài)(正常和故障狀態(tài))組成狀態(tài)空間S，它的可測量特征的取值范圍的全體構(gòu)成特征空間Y。當系統(tǒng)處于某一狀態(tài)s時，系統(tǒng)具有確定的特征y，即存在映射g:S→Y；反之，一定的特征也對應(yīng)確定的狀態(tài)，即存在映射f:Y→S。狀態(tài)空間與特征空間的關(guān)系可用圖10-15表示。

圖10-15狀態(tài)空間與特征空間的關(guān)系故障診斷的目的在于根據(jù)可測量的特征向量來判斷系統(tǒng)處于何種狀態(tài)，也就是找出映射f。若系統(tǒng)可能發(fā)生的狀態(tài)是有限的，例如可能發(fā)生n故障，這里假設(shè)系統(tǒng)正常狀態(tài)為s0,各個故障狀態(tài)為s1,s2,…,sn。當系統(tǒng)處于狀態(tài)si時，對應(yīng)的可測量特征向量為yi=(yi1,yi2,…,yim)T。故障診斷過程就是由特