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

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

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

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

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

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

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

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

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

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

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

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

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

13、丄c表示，剩余 的其它類(lèi)看作是另一類(lèi)，用Bj =At,L ,AtA、,L ATT R(c網(wǎng),i =1丄c表示.MTSVM基本思想是對(duì)于c類(lèi)問(wèn)題，為每一類(lèi)找到一個(gè)超平面+b =0,i =1丄，c.使得除第i類(lèi)之外的的數(shù)據(jù)點(diǎn)盡可能靠近這一超平面，同時(shí)盡可 能的排斥第i類(lèi)數(shù)據(jù).MTSVM第i類(lèi)數(shù)據(jù)點(diǎn)對(duì)應(yīng)的原始問(wèn)題為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對(duì)偶為min丄、c2心Tt1 Tct|： i Gi Hi HiGi ： iiTe2i(2.5)s.t0g,i

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

15、持向量機(jī)(MBSVM)MBSVM基本思想是對(duì)于c類(lèi)問(wèn)題，為每一類(lèi)找到一個(gè)超平面Wi, +h =0,i =1丄,c.使得第i類(lèi)的數(shù)據(jù)點(diǎn)盡可能靠近這一超平面,同時(shí)盡可能的排斥 其它類(lèi)數(shù)據(jù).MBSVM與MTSVM不同之處在于MBSVM是把數(shù)據(jù)中的一類(lèi)數(shù)據(jù)點(diǎn)放到約束條件中 其它類(lèi)點(diǎn)作為另一類(lèi)，放在目標(biāo)函數(shù)中.MBSVM第i類(lèi)數(shù)據(jù)點(diǎn)對(duì)應(yīng)的原始問(wèn)題為mjn 三 BiW +胡| +Ge：q1w，bj, Q 2s.t (AWi +乂2匕)+ Gk -0,0.其中 q R(cs 1, eb RCi1, G此規(guī)劃的wolfe對(duì)偶為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.對(duì)每一個(gè) r 1L ,c,取 X：-Xi，X_-X Xi.選擇適當(dāng)?shù)膮?shù)Ci 0,求解問(wèn)題(2.6),得最優(yōu)解：=(叮，叮)T,i =1, L ,c. 令 Ui =w；bl，計(jì)算 u-(HiTHi)JGi*.構(gòu)造分離超平面七0和決策函數(shù)fj(x) *”,x b”.,則判斷屬第k類(lèi).Wi |對(duì)任一測(cè)試點(diǎn)% Rm ,若fk(% = max非線性支持向量機(jī)在日常生活中遇到的分類(lèi)問(wèn)題，大部分是線性不可分的問(wèn)題.對(duì)于線性不可分問(wèn)題， 通過(guò)引入核函數(shù)k： Rm Rm R,利用核函數(shù)的特征映射將數(shù)據(jù)映射到高維特征空間，

17、使得映射后的數(shù)據(jù)是(近似)線性可分的.常見(jiàn)的核函數(shù)主要有：?jiǎn)J斯徑向基核：2 2 2 2k(x, y) =exp - x - y| / - 或 k(x, y) =exp - x - y / 2二，(二.0).多項(xiàng)式核：k(x,y) =(：x,y c)d,(c R,d 0).利用核函數(shù)定義，minas.t問(wèn)題(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.(加核二類(lèi)SVM)步1.給出訓(xùn)練集( *$)：4匸Rm1.步2.選擇適當(dāng)?shù)膮?shù)C 0,求解問(wèn)題(1.1),得最優(yōu)解】=：(打，,

18、n)T .步3.計(jì)算八；斗i人.選擇廠的一個(gè)正分量0 ： :- j :：: C ,計(jì)算b j -、1 yi: i k:Xj, Xj -.步4.構(gòu)造分離超平面 -X b=o和決策函數(shù)f(x)=sgn(k-,x bj.利用核函數(shù)定義，問(wèn)題(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í)了一些其它支持向量機(jī)

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

20、門(mén)課程我了解到了許多與分類(lèi)相關(guān)的知識(shí).今后將會(huì)在此基礎(chǔ)上不斷改進(jìn) 繼續(xù)學(xué)習(xí).隨著研究的不斷深入,新問(wèn)題、新思想將會(huì)不斷涌現(xiàn)，這必將促進(jìn)SVM方法在實(shí)際應(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)崗 , 寧克歐 . 模式識(shí)別 . 哈爾濱工業(yè)大學(xué)出版社 , 1998.S.Haykin. Neural networks: A comprehensive Foundation. Pearson Education Inc. 1999.高雋. 人工神經(jīng)網(wǎng)絡(luò)原理及仿真實(shí)例 . 北京 :