最優(yōu)化理論與支持向量機

1、最優(yōu)化理論與支持向量機摘要 近幾年來，機器學(xué)習(xí)方法得到了廣泛的應(yīng)用，在其理論研究和算法實現(xiàn)方面都取 得了重大進(jìn)展成為機器學(xué)習(xí)領(lǐng)域的前沿?zé)狳c課題.支持向量機也受到廣泛的關(guān)注，它以統(tǒng)計學(xué)習(xí)為基礎(chǔ)，建立在計算學(xué)習(xí)理論的結(jié)構(gòu)風(fēng)險最小化原則之上，具有簡潔的數(shù)學(xué)形式，已成為機器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域的主要工具.本文主要是對最優(yōu)化理論的概述以及對支持 向量機的簡單介紹.通過對最優(yōu)化理論與支持向量機的學(xué)習(xí)，進(jìn)一步深入研究相關(guān)理論與 實驗知識關(guān)鍵詞：樣本集 類標(biāo)識 支持向量機 回歸1 最優(yōu)化理論本學(xué)期主要學(xué)習(xí)了最優(yōu)化的一些基本理論，一類分類問題，二類分類問題，多類分類 問題,回歸問題分類問題的主要思想是通過給定的樣

2、本集 T =（,生）：4 Rm R尋找一 個定值函數(shù)f ：Rm R.以便利用f來判斷任一輸入Rm的類標(biāo)識.另外,分類問題根 據(jù)數(shù)據(jù)樣本的個數(shù)可分為一類分類問題，二類分類問題，多類分類問題根據(jù)定值函數(shù)的 線性和非線性性，可分為線性分類問題和非線性分類問題對于分類問題研究最多的是二 類分類問題和多類分類問題近幾年來，機器學(xué)習(xí)方法得到了廣泛的應(yīng)用，在其理論研究和算法實現(xiàn)方面都取得了 重大進(jìn)展成為機器學(xué)習(xí)領(lǐng)域的前沿?zé)狳c課題.不少學(xué)者將機器學(xué)習(xí)的方法應(yīng)用與機械產(chǎn)品 壽命的預(yù)測，而其中人工神經(jīng)網(wǎng)絡(luò)和支持向量機等方法在壽命預(yù)測中應(yīng)用較多由于人工神經(jīng)網(wǎng)絡(luò)存在對樣本數(shù)量與質(zhì)量具有高依賴性，且對于小樣本情況易陷入

3、局部最優(yōu)等問題而以統(tǒng)計學(xué)理論為基礎(chǔ)的支持向量機，具有嚴(yán)格的理論和數(shù)學(xué)基礎(chǔ)，可以不像神經(jīng)網(wǎng)絡(luò)的 結(jié)構(gòu)設(shè)計需要依賴于設(shè)計者的經(jīng)驗知識和先驗知識，因此，利用支持向量機理論實現(xiàn)趨勢 預(yù)測分析已成為研究新熱點基于數(shù)據(jù)的機器學(xué)習(xí)是一種重要的知識發(fā)現(xiàn)方法，是人工智能最具智能特征、最前言 的研究領(lǐng)域之一 機器學(xué)習(xí)主要研究計算機如何模擬或?qū)崿F(xiàn)人類的學(xué)習(xí)能力，以獲取新的知識技能，重新組織已有的知識結(jié)構(gòu)，使之不斷改善自身的性能機器學(xué)習(xí)是人類智能的 核心問題，是使計算機具有人工智能的根本途徑，基于數(shù)據(jù)的機器學(xué)習(xí)問題作為人工智能 研究領(lǐng)域的一個重要方面.其研究的主要問題是從一組觀測數(shù)據(jù)集出發(fā)，得到一些不能通 過原理分析

4、而得到的規(guī)律，進(jìn)而利用這些規(guī)律對未來數(shù)據(jù)或無法觀測到的數(shù)據(jù)進(jìn)行預(yù)測和 分析迄今為止，關(guān)于機器學(xué)習(xí)還沒有一種被共同接受的理論框架，關(guān)于其實現(xiàn)方法大致可 以分為以下三種1.第一種是經(jīng)典的統(tǒng)計預(yù)測方法2.現(xiàn)有機器學(xué)習(xí)方法共同的重要理論基礎(chǔ)之一是統(tǒng)計 學(xué).在這類方法中，模型中參數(shù)的相關(guān)形式是已知的，用訓(xùn)練樣本來估計參數(shù)需要已知樣 本的分布形式，因此具有很大的局限性.另外傳統(tǒng)的統(tǒng)計學(xué)研究的是樣本數(shù)目趨于無窮大 時的漸進(jìn)理論，但在實際問題中，樣本數(shù)量卻是有限的，因此一些理論上很優(yōu)秀的學(xué)習(xí)方 法在實際應(yīng)用中可能表現(xiàn)的不盡人意.第二種方法是經(jīng)驗非線性方法 , 如人工神經(jīng)網(wǎng)絡(luò) (ANN) 方法 34, 神經(jīng)網(wǎng)絡(luò)

5、學(xué)習(xí)方法 對于逼近實數(shù)值、離散值或向量值的目標(biāo)函數(shù)提供了一種健壯性很強的方法 . 對于某些類 型的問題 , 如學(xué)習(xí)解釋復(fù)雜的現(xiàn)實世界中的傳感器數(shù)據(jù) , 人工神經(jīng)網(wǎng)絡(luò)是目前知道的最有 效的學(xué)習(xí)方法 , 這種方法利用已知樣本建立非線性模型 , 克服了傳統(tǒng)參數(shù)估計方法的困難 , 人工神經(jīng)網(wǎng)絡(luò)已在很多的實際問題中取得了驚人的成功 , 如手寫識別 , 圖像識別 , 語音識 別 . 但是這種方法缺少統(tǒng)一的教學(xué)理論 , 過度擬合訓(xùn)練也是人工神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)中的重要問 題 . 盡管人工神經(jīng)網(wǎng)絡(luò)對訓(xùn)練數(shù)據(jù)表現(xiàn)非常好 , 過度擬合也會導(dǎo)致數(shù)據(jù)泛化到新的數(shù)據(jù)時 性能很差.第三種方法是統(tǒng)計學(xué)習(xí)理論 ( Statistic

6、al Learning Theory, SLT) 5, 與傳統(tǒng)的統(tǒng)計學(xué)習(xí)相 比, SLT 是一種專門研究小樣本情況下機器學(xué)習(xí)規(guī)律的理論 . 該理論針對小樣本統(tǒng)計問題 建立了一套新的理論體系 , 在這種體系下的統(tǒng)計推理規(guī)則不僅考慮了對漸進(jìn)性能的要求 , 而且追求在現(xiàn)有有限信息條件下得到的最優(yōu)結(jié)果.Vapnik等人從20世紀(jì)60年代開始致力于此方面的研究 , 到 90年代中期隨著其理論的不斷發(fā)展成熟 , 也由于神經(jīng)網(wǎng)絡(luò)等學(xué)習(xí)方法 在理論上缺乏實質(zhì)性的進(jìn)展 , SLT 開始受到越來越廣泛的重視 .支持向量機(SVM)6是Cortes和Vapnik于1995年在VC維理論和結(jié)構(gòu)風(fēng)險最這種小 原理基礎(chǔ)上

7、提出的一種機器學(xué)習(xí)方法 , 它是借助優(yōu)化方法解決機器學(xué)習(xí)問題的新工具 , 能 夠盡量提高學(xué)習(xí)機的推廣能力 , 即使由有限數(shù)據(jù)集得到的判別函數(shù)對獨立的測試集仍能夠 得到較小的誤差 . 此外 SVM 是一個凸二次規(guī)劃 , 能夠保證找到的解釋全局最優(yōu)解 . 這些特 點使SVM成為一種優(yōu)秀的基于數(shù)據(jù)的機器學(xué)習(xí)方法，SVM是機器理論中最新的內(nèi)容，也是 最實用的部分, 其主要內(nèi)容在 1992年到1995年間基本完成, 目前仍處于基本發(fā)展階段 . 可 以說SLT之所以從20世紀(jì)90年代以來受到越來越多的重視,很大程度上是因為它發(fā)展出 來了 SVM 這一通用的基于數(shù)據(jù)的機器學(xué)習(xí)方法 .SVM 在解決小樣本、

8、非線性及高維模式識別問題中表現(xiàn)出特別的優(yōu)勢 , 并能夠推廣到 函數(shù)擬合等其他機器學(xué)習(xí)問題中 . 與傳統(tǒng)機器學(xué)習(xí)方法不同 , SVM 首先通過非線性變換將 原始的樣本空間映射到高維的特征空間 , 然后在這個行空間中求取最優(yōu)線性分類面 , 而這 種非線性變換是通過定義適當(dāng)?shù)膬?nèi)積函數(shù)實現(xiàn)的 .SVM 成功的解決了高維問題和局部極小 值問題. 在 SVM 中只要定義不同的內(nèi)積函數(shù) , 就可以實現(xiàn)多項式逼近、貝葉斯分類器、徑 向基函數(shù)(RBF)方法、多層感知器網(wǎng)絡(luò)等很多現(xiàn)有的學(xué)習(xí)算法.在解決高維問題中，神經(jīng)網(wǎng) 絡(luò)等方法容易陷入一個又一個局部極小值 . SVM 使用了大因子來控制學(xué)習(xí)機器的訓(xùn)練過 程，使其

9、只選擇具有最大分類間隔的分類超平面 . 最優(yōu)超平面對線性不可分的情況引入松 弛項來控制經(jīng)驗風(fēng)險從而使其在滿足分類要求的情況下具有好的推廣能力 , 尋找最優(yōu)超平 面的過程最終轉(zhuǎn)化為凸二次型優(yōu)化問題而得到全局最優(yōu)解 .SVM 方法具有較好的理論基礎(chǔ) , 在一些領(lǐng)域的應(yīng)用中表現(xiàn)出來與眾不同的優(yōu)秀的泛 化性能, 因此, SVM 在解決分類、回歸和密度函數(shù)估計等機器學(xué)習(xí)方面獲得了非常好的效 果, 并成功應(yīng)用在模式識別、回歸估計和概率密度函數(shù)估計等方面 . 例如在模式識別方面 , TOC o 1-5 h z SVM在手寫數(shù)字識別、語音識別、文本分類、信號處理、圖像分類和識別等多個領(lǐng)域都有 不俗的表現(xiàn).SV

10、M在精度上已經(jīng)超過傳統(tǒng)的學(xué)習(xí)算法或與之不相上下.SVM在解決有限樣本、高維模式識別、非線性等復(fù)雜問題中表現(xiàn)出許多特有的優(yōu)勢，目前SVM已被成功應(yīng)用于識別、回歸、分類問題中.線性支持向量機所謂最優(yōu)化技術(shù)就是找出使得目標(biāo)函數(shù)值達(dá)到最小或最大的自變量值的方法最優(yōu)化問題從其分類看有經(jīng)典無約束最優(yōu)化問題和有約束最優(yōu)化問題.無約束極值問題的數(shù)學(xué)模型為min f (x)x其中x 亠b)空；，i = 1,L ,n,(vw,k b) - yi 乞；,i =1,L ,n,其中；是大于0的參數(shù).其Wolfe對偶形式為Xi,X八邁上+冃)-Z ：訂(3 -冃)(2.4)郭2瓦工1妙一冃爐s.t. : i 一 匚=0,

11、 0i C, 0 豈乞 C, i =1,L ,n.其中,:是 Lagrange乘子向量.通過求解問題(2.4),可得分類超平面：:w,x b = 0.具體算法如下. 算法3.(線性支持向量回歸機)步 1.給出訓(xùn)練集( X,yi)：#u Rmx1.步2.選擇適當(dāng)?shù)膮?shù)C .0, ; .0,求解問題(1.4),得最優(yōu)解宀陽，陽，護(hù)=w：)t.步3.計算；八；4( - -i*)Xi .選擇廠的一個正分量0 ： :- j : C ,計算b =y - : w*,Xj -；,或者選擇的一個正分量 0 ： / : C ,計算 b = y - : w*,Xj -；步4.構(gòu)造決策函數(shù)f (x) = ： ，x *

12、 b .步5.對任一測試點% Rn,其輸出f(%=：w*,%b*.此外還學(xué)習(xí)了一些多類支持向量機的模型.如多元雙生支持向量機(Multi-twin support vector machine,簡記為 MTSVM),多生支持向量機(Multiple birth support vector machine, 簡記為MBSVM)等.2.4.多元雙生支持向量機(MTSVM)多元雙生支持向量機是在TSVM基礎(chǔ)上采用了一對余的方法處理數(shù)據(jù)的，為每一類數(shù) 據(jù)利用最小二乘原理構(gòu)造一個分類超平面，使得該類數(shù)據(jù)點盡可能靠近這一超平面，同時 盡可能的排斥其它類數(shù)據(jù).本文中用到的數(shù)據(jù)點中的第i類用A Rci =1

13、丄c表示，剩余 的其它類看作是另一類，用Bj =At,L ,AtA、,L ATT R(c網(wǎng),i =1丄c表示.MTSVM基本思想是對于c類問題，為每一類找到一個超平面+b =0,i =1丄，c.使得除第i類之外的的數(shù)據(jù)點盡可能靠近這一超平面，同時盡可 能的排斥第i類數(shù)據(jù).MTSVM第i類數(shù)據(jù)點對應(yīng)的原始問題為1 2 1mb先2卜側(cè)+射|右瓦j$占弋s.t-(BiWi 勺20)丨一勺，i -0, i, j =1丄，c,其中 ei Rct $2 e R(cf T Ci0.此規(guī)劃的wolfe對偶為min丄、c2心Tt1 Tct|： i Gi Hi HiGi ： iiTe2i(2.5)s.t0g,i

14、=1,L ,c,其中 Hi =A,eJ, G 二田鳥.通過求解問題(2.5),得到第i類數(shù)據(jù)點對應(yīng)的分類超平面 vw,x+bi=0. 具體算法如下.算法 4. (MTSVM)步 1.給出訓(xùn)練集(x,yi)i：u Rmx1,L ,c.步 2.對每一個 r 1, L ,c,取 X：一 Xi,X-=X Xi.步3.選擇適當(dāng)?shù)膮?shù)Ci 0,求解問題(2.5),得最優(yōu)解 汀珥叮，,J)T,i可,L ,c. 步 4.令 ui 二Mb,計算 u* (HiTHi)9：步5.構(gòu)造分離超平面b0和決策函數(shù)(x) =： J”,x 巾：步6.對任一測試點% Rm,若fk(%p wjJ夠，則判斷屬第k類.2.5.多生支

15、持向量機(MBSVM)MBSVM基本思想是對于c類問題，為每一類找到一個超平面Wi, +h =0,i =1丄,c.使得第i類的數(shù)據(jù)點盡可能靠近這一超平面,同時盡可能的排斥 其它類數(shù)據(jù).MBSVM與MTSVM不同之處在于MBSVM是把數(shù)據(jù)中的一類數(shù)據(jù)點放到約束條件中 其它類點作為另一類，放在目標(biāo)函數(shù)中.MBSVM第i類數(shù)據(jù)點對應(yīng)的原始問題為mjn 三 BiW +胡| +Ge：q1w，bj, Q 2s.t (AWi +乂2匕)+ Gk -0,0.其中 q R(cs 1, eb RCi1, G此規(guī)劃的wolfe對偶為m istT n i2.0 . + h = 0 .具體算法如下.算法 6. (MBS

16、VM)步1.步2.步3.步4.步5.步6.給出訓(xùn)練集(xi,yi)nd Rm 1,L,c.對每一個 r 1L ,c,取 X：-Xi，X_-X Xi.選擇適當(dāng)?shù)膮?shù)Ci 0,求解問題(2.6),得最優(yōu)解：=(叮，叮)T,i =1, L ,c. 令 Ui =w；bl，計算 u-(HiTHi)JGi*.構(gòu)造分離超平面七0和決策函數(shù)fj(x) *”,x b”.,則判斷屬第k類.Wi |對任一測試點% Rm ,若fk(% = max非線性支持向量機在日常生活中遇到的分類問題，大部分是線性不可分的問題.對于線性不可分問題， 通過引入核函數(shù)k： Rm Rm R,利用核函數(shù)的特征映射將數(shù)據(jù)映射到高維特征空間，

17、使得映射后的數(shù)據(jù)是(近似)線性可分的.常見的核函數(shù)主要有：咼斯徑向基核：2 2 2 2k(x, y) =exp - x - y| / - 或 k(x, y) =exp - x - y / 2二，(二.0).多項式核：k(x,y) =(：x,y c)d,(c R,d 0).利用核函數(shù)定義，minas.t問題(2.1)可改進(jìn)為如下1 n nni八iryiyjkXXj) -v yrn i ： i% =0,0 乞：i c,i =1,L , n.(3.1)算法1可改進(jìn)為算法3.(加核二類SVM)步1.給出訓(xùn)練集( *$)：4匸Rm1.步2.選擇適當(dāng)?shù)膮?shù)C 0,求解問題(1.1),得最優(yōu)解】=：(打，,

18、n)T .步3.計算八；斗i人.選擇廠的一個正分量0 ： :- j :：: C ,計算b j -、1 yi: i k:Xj, Xj -.步4.構(gòu)造分離超平面 -X b=o和決策函數(shù)f(x)=sgn(k-,x bj.利用核函數(shù)定義，問題(2.2)和(2.3)改進(jìn)為如下DTSVM 1 mr as.t1_1in： tG H TH- e2：-20 _： _ q,(3.2)DTSVM 2 mins.t-tG HtHGt 1 _eT 120 -c2,(3.3)其中:,-是 Lagrange乘子向量,H 二K(A,X) e1, G=K(B,X) e2.算法與算法 2是 相同的.此外還學(xué)習(xí)了一些其它支持向量機

19、的模型，此處不再一一列舉.4.結(jié)論近年來，支持向量機受到廣泛的關(guān)注，SVM是在統(tǒng)計學(xué)習(xí)理論 VC維理論和結(jié)構(gòu)風(fēng)險 最小原理的基礎(chǔ)上發(fā)展起來的一種新的機器學(xué)習(xí)方法.它以統(tǒng)計學(xué)習(xí)為基礎(chǔ)，建立在計算學(xué)習(xí)理論的結(jié)構(gòu)風(fēng)險最小化原則之上，具有簡潔的數(shù)學(xué)形式，能進(jìn)行直觀的幾何解釋并具 有良好的泛化能力，避免了局部最優(yōu)解，且需要人為設(shè)定的參數(shù)較少，便于使用，為小樣 本機器學(xué)習(xí)提供了一種新方法，以用于模式識別、回歸分析和函數(shù)逼近等領(lǐng)域.支持向量 機已成為機器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域的主要工具.由于它具有一些傳統(tǒng)機器學(xué)習(xí)方法所不能 匹敵的優(yōu)勢而成為目前國內(nèi)外研究的一個熱點問題，并已成功應(yīng)用于眾多模式識別領(lǐng)域.通過學(xué)習(xí)本

20、門課程我了解到了許多與分類相關(guān)的知識.今后將會在此基礎(chǔ)上不斷改進(jìn) 繼續(xù)學(xué)習(xí).隨著研究的不斷深入,新問題、新思想將會不斷涌現(xiàn)，這必將促進(jìn)SVM方法在實際應(yīng)用中發(fā)揮更大的作用參考文獻(xiàn)F.Mulier.Vapnik-Chervonenkis(VC) learning theory and its applications. IEEE Transactions on Neural Network, 1999, 10(5): 985-987.黃風(fēng)崗 , 寧克歐 . 模式識別 . 哈爾濱工業(yè)大學(xué)出版社 , 1998.S.Haykin. Neural networks: A comprehensive Foundation. Pearson Education Inc. 1999.高雋. 人工神經(jīng)網(wǎng)絡(luò)原理及仿真實例 . 北京 :