支持向量機的理論與算法研究.pdf

1、機器學(xué)習(xí)是研究計算機怎樣模擬或?qū)崿F(xiàn)人類的學(xué)習(xí)行為，以獲取新的知識或技能，重新組織已有的知識結(jié)構(gòu)，從而不斷改善自身性能。 支持向量機是20世紀(jì)90年代中期出現(xiàn)的機器學(xué)習(xí)技術(shù)，是近年來機器學(xué)習(xí)領(lǐng)域的研究熱點。這項技術(shù)從提出到現(xiàn)在不過十年時間，但其研究進展非常之快、之大。它有堅實的理論基礎(chǔ)，應(yīng)用上也是有口皆碑，在手寫體數(shù)字識別、文本分類等具體問題上創(chuàng)造和保持著目前的最好記錄。 支持向量機本質(zhì)上是一種非線性數(shù)據(jù)處理方法。與傳統(tǒng)的

2、人工神經(jīng)網(wǎng)絡(luò)不同，后者基于“經(jīng)驗風(fēng)險最小化原理”，前者基于“結(jié)構(gòu)風(fēng)險最小化原理”。“結(jié)構(gòu)風(fēng)險最小化原理”建立在嚴謹?shù)臄?shù)學(xué)理論基礎(chǔ)之上，令人耳目一新，使人們對學(xué)習(xí)機的認識發(fā)生了深刻變化。 支持向量機具有以下顯著特征。 (1)結(jié)構(gòu)簡單。 (2)凸優(yōu)化問題。有關(guān)的優(yōu)化問題無局部極小點。 (3)稀疏表示。最優(yōu)分離超平面之法向量W是訓(xùn)練樣本的線性組合，每個樣本的系數(shù)在某種意義上反映了該樣本的重要性。分類問題的有用信

3、息全部包含在系數(shù)不為零的那些樣本即支持向量中。如果從訓(xùn)練集中去掉非支持向量，或使其在原來位置附近有微小偏移，則重新訓(xùn)練后，所得最優(yōu)超平面與原來相同。即問題的解僅與支持向量有關(guān)。 (4)模塊化。它清楚地分成兩個模塊：一個通用的學(xué)習(xí)機和與具體問題有關(guān)的核函數(shù)。這使我們能夠把設(shè)計一個好的學(xué)習(xí)算法和設(shè)計一個好的核函數(shù)分開來研究。這種模塊化處理方法便于理論分析和工程實現(xiàn)。 (5)本質(zhì)上是線性學(xué)習(xí)機。它是核函數(shù)誘導(dǎo)的(隱含的)特征空

4、間上的線性函數(shù)，因而便于理論分析。 支持向量機體現(xiàn)了以下重要思想和方法。 (1)邊緣最大化思想。通過最優(yōu)超平面來構(gòu)造判決函數(shù)，實現(xiàn)了“結(jié)構(gòu)風(fēng)險最小化原理”，避免了對訓(xùn)練集過度擬合，保證了支持向量機的泛化能力。 (2)對偶表示。在對偶表示中訓(xùn)練數(shù)據(jù)僅以內(nèi)積形式出現(xiàn)，因此可以用核函數(shù)來代替內(nèi)積。 (3)核方法。從線性分類器轉(zhuǎn)變成非線性分類器，只需要以核函數(shù)替換原來的內(nèi)積。除此之外，原來的線性算法保持不變，線性

5、分類器的全部優(yōu)點都被繼承下來，如計算簡單、無局部極小點等。通過核函數(shù)能夠在輸入空間間接地完成高維特征空間(具有更豐富的結(jié)構(gòu))中的操作，計算復(fù)雜度沒有實質(zhì)性增加，但解決了復(fù)雜函數(shù)的表示問題。引進核函數(shù)之后，特征空間的維數(shù)變得不再重要了，甚至不必知道特征映射的具體形式，避免了維數(shù)災(zāi)難。通過改變核函數(shù)，可以得到不同的分類器。 支持向量機最初是用來解決分類問題的，其思想和方法后來被拓展到其他領(lǐng)域，如回歸分析、函數(shù)逼近、密度估計，還有主成

6、分分析、K-近鄰、費歇判決等。核方法也發(fā)展成了一種方法論，把許多重要的數(shù)據(jù)處理方法納入統(tǒng)一的框架，開辟了更加寬廣的研究天地。 本文僅研究用來分類的支持向量機。 支持向量機并非盡善盡美，作為發(fā)展中的機器學(xué)習(xí)技術(shù)，還有很多問題有待解決。例如，1．訓(xùn)練算法支持向量機的訓(xùn)練歸結(jié)為求解二次規(guī)劃問題，但該問題的Hessian矩陣通常是稠密的，處理大規(guī)模問題時存儲代價很高。例如，當(dāng)樣本個數(shù)為50000時，Hessian矩陣元素個數(shù)達2

7、5億之巨，普通計算機的內(nèi)存根本不夠用。所以，經(jīng)典的優(yōu)化方法不適用，開發(fā)耗時短且占用內(nèi)存少的算法成為人們追求的目標(biāo)。訓(xùn)練算法又可以分為線性SVM訓(xùn)練算法與非線性SVM訓(xùn)練算法、在線算法與離線算法、精確算法與近似算法等。訓(xùn)練算法一直是最活躍的研究課題。 2．模型選擇 模型選擇是指：對于具體問題，如何選擇核函數(shù)，以及支持向量機中的一些參數(shù)。這些參數(shù)包括：懲罰系數(shù)C，它在訓(xùn)練誤差與泛化能力之間進行平衡；核函數(shù)中的參數(shù)，如高斯核中

8、的σ和多項式核中的P等，不同的參數(shù)對應(yīng)著不同的特征空間和特征映射，它們與支持向量機的泛化能力密切相關(guān)。怎樣自動地進行模型選擇? 3．知識嵌入 所謂知識，是指除訓(xùn)練樣本外的信息，如問題領(lǐng)域的專業(yè)知識，專家經(jīng)驗等。標(biāo)準(zhǔn)的支持向量機是基于訓(xùn)練樣本的，隱含的特征映射使得嵌入知識很困難。但經(jīng)驗告訴我們，一個系統(tǒng)所含知識的多少，對知識的利用程度如何，反映了其能力的高低。這在解決具體問題時尤其重要，但SVM還沒有從根本上解決嵌入領(lǐng)域知

9、識的問題。 4．多類問題 最初，SVM是針對二分類問題的，但實際應(yīng)用中常常是多類問題。如何把它推廣到多類問題?多類問題訓(xùn)練集的規(guī)模通常很大，如何有效地訓(xùn)練? 我的論文就是圍繞這些問題開展研究。論文的主要貢獻是： (1)提出“有附加信息的統(tǒng)計學(xué)習(xí)理論框架”。經(jīng)典統(tǒng)計學(xué)習(xí)理論的重要結(jié)論，都是假設(shè)訓(xùn)練樣本服從某個固定分布，或者服從任意分布，這是兩個極端情形。實際情況是，人們對所處理的問題不全了解，但又知道一部分

10、信息，這個新框架能夠描述這種情況(見第二章)。 (2)分六個專題，即支持向量機訓(xùn)練算法、支持向量機的各種表現(xiàn)形式、支持向量機的泛化能力、模型選擇、多類問題和支持向量機的應(yīng)用，系統(tǒng)地論述了(分類)支持向量機的研究進展(見第三章)。 (3)提高支持向量機性能的關(guān)鍵，是設(shè)計適合特定問題的核函數(shù)，這要求對核函數(shù)本身有深入了解。針對三類重要核函數(shù)，即平移不變核函數(shù)、旋轉(zhuǎn)不變核函數(shù)和卷積核，提出了簡單易用的判別準(zhǔn)則，并給出數(shù)學(xué)證明(見第四章

11、)。 (4)支持向量機的優(yōu)勢在于處理非線性問題，但設(shè)計大規(guī)模、非線性支持向量機訓(xùn)練算法比較困難。本文深入研究了NPA算法，分析了該算法存在的不足，對第一、第二類檢驗下的迭代過程做了實質(zhì)性改進。實驗結(jié)果表明，新版本性能穩(wěn)定，在未增加計算代價的條件下，訓(xùn)練速度明顯提高(見第五章)。 (5)利用本文設(shè)計的訓(xùn)練算法，開發(fā)了一個自動分類模擬系統(tǒng)(見第六章)。 論文共分七章，具體組織如下： 第一章，什么是支持向量機。

12、本章由三部分構(gòu)成。第一部分闡述什么是支持向量機，先從簡單的線性分類器入手，然后推廣到更復(fù)雜的情況。第二部分概括了支持向量機的特征和重要思想。第三部分簡要分析支持向量機與傳統(tǒng)神經(jīng)網(wǎng)絡(luò)的異同。 第二章，支持向量機的理論基礎(chǔ)。本章用嚴謹、精煉的語言描述了統(tǒng)計學(xué)習(xí)理論的概貌，它與支持向量機的關(guān)系。在此基礎(chǔ)上，提出一個“有附加信息的統(tǒng)計學(xué)習(xí)理論框架”。 第三章，支持向量機研究進展。本章分六個專題，即訓(xùn)練算法、支持向量機的各種表現(xiàn)形

13、式、支持向量機的泛化能力、模型選擇、多分類問題和支持向量機的應(yīng)用，綜述支持向量機的研究進展，涵蓋了迄今為止主要的研究內(nèi)容和成果，從中可以了解人們所研究的問題、所付出的努力、所取得的成就和所面臨的困難。 第四章，核函數(shù)的性質(zhì)及其構(gòu)造方法。支持向量機由核函數(shù)與訓(xùn)練集完全刻畫。提高支持向量機性能的關(guān)鍵之一，是設(shè)計適合特定問題的核函數(shù)，這就要求對核函數(shù)本身有深入了解。本章由四部分組成：第一部分論述核函數(shù)與正定矩陣的關(guān)系及核函數(shù)的基本性質(zhì)

14、。第二部分對三類重要核函數(shù)，即平移不變核、旋轉(zhuǎn)不變核和卷積核，提出了簡單實用的判別準(zhǔn)則，并在此基礎(chǔ)上構(gòu)造了很多重要核函數(shù)。第三部分介紹了一種自適應(yīng)核函數(shù)。第四部分指出把問題領(lǐng)域的知識與核函數(shù)設(shè)計聯(lián)系起來，即通過設(shè)計特殊的核函數(shù)來嵌入領(lǐng)域知識，是今后努力的方向。 第五章，加速NPA算法的收斂。支持向量機的優(yōu)勢在于處理非線性問題，但設(shè)計大規(guī)模、非線性支持向量機訓(xùn)練算法比較困難。1998年P(guān)latt提出的SMO算法(Sequentia

15、l Minimal Optimization)，和2001年Keerthi等人提出的NPA算法(Nearest Point Algorithm)是目前常用的。NPA算法有明確的幾何背景,與SMO相比訓(xùn)練速度毫遜色，并且在懲罰系數(shù)較大時有顯著優(yōu)勢。本章分析了NPA算法存在的不足，對其第一、第二類檢驗下的迭代過程做了實質(zhì)性改進。實驗結(jié)果表明，新版本性能穩(wěn)定，在未增加計算代價的條件下，訓(xùn)練速度明顯提高。 第六章，支持向量機自動分類模擬