Support Vector Machines

?

Vapnik等學者從20世紀70年代開始研究統計學理論（SLT），到20世紀90年代之前都還處于初級研究和理論準備階段，最近10年才得到重視，其本身也趨向完善，并產生了支持向量機（SVMs），這一將理論付諸實現的有效的機器學習方法。SVMs算法在模式識別、回歸估計等方面都有良好的應用，例如，時間序列預測、人臉識別、手寫數字識別、語音識別以及網頁分類等問題。通過諸多學者的研究證明，SVMs算法在精度上已經超過傳統的統計學習算法或與之不相上下。就推廣而言，SVMs具有較好的推廣性，在統計意義上較少的支持向量對應很好的推廣能力。

?

支持向量機的基本思想基于1909年Mercer核展開定理，通過非線性映射Φ，把樣本空間映射到一個高維乃至無窮維的特征空間（Hilbert空間），使在特征空間中可以應用線性學習機的方法解決樣本空間中的高度非線性分類和回歸問題。支持向量機是建立在統計學習理論的VC維（Vapnik Chervonenks Dimension）理論和結構風險最小原理（Structural Risk Minimization Inductive Principle）基礎上的，根據有限的樣本信息在模型的復雜性（即對特定訓練樣本的學習精度，Accuracy）和學習能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力（Generalization Ability），能較好地解決小樣本、非線性、高維數和局部極小點等實際問題，已成為機器學習界的研究熱點之一。

?

?

#######################

統計學習理論基本思想

#######################

?

1) 統計學習理論由貝爾實驗室Vapnik于1992年首次提出。

2) 它是研究小樣本下機器學習規律的理論。

3) 基于統計學習理論(SLT)。

3) 基本思想：折衷考慮經驗風險和推廣的置信界限，取得實際期望風險的最小化。

兩大核心： VC維和結構風險最小化。

?

VC維的概念

1）描述函數復雜性的指標。
2）假如存在一個由h個樣本的樣本集能夠被一個函數集中的函數按照所有可能的2h??種形式分為兩類，則函數集能夠把樣本數為h的樣本集打散(shattering)。函數集的vc維就是用這個函數集中的函數所能夠打散的最大樣本集數的樣本數目。附圖是3個樣本被線性分類器打散的情況。
3）VC維是目前為止對函數集學習性能的最好描述指標。但遺憾的是目前尚沒有通用的關于如何計算任意函數集的VC維的理論。目前大多數的軟件只能給出VC維的結果范圍。

?

結構風險最小化的思想

1) Vapnik證明，期望風險與經驗風險之間的關系滿足如下公式：

R(w)=Remp(w)+Φ(n/h)

其中n表示樣本數，h為學習機器的VC維， Φ(n/h)稱為置信區間。Φ(n/h)是隨n/h增大而減小的函數。

從上面可以看出，學習機器的VC維h越大，Φ(n/h)越大經驗風險和期望風險之間的偏差越大。這樣即使在經驗誤差很小的情況下，其推廣誤差會越大。

2) 具體過程

將函數集構造為一個函數子集序列，使各個子集按照VC 維的大小(亦即φ的大小) 排列；在每個子集中尋找最小經驗風險，在子集間折衷考慮經驗風險和置信界限，取得實際風險的最小。

?

?

參數選擇問題

支持向量機的一個優點就是它的參數很少,只包括核函數參數以及C的選擇所以在使用支持向量機軟件時,算法運算過程中需要人為設定這兩類參數比如使用RBF核函數時,此時的SVM就有兩個參數:RBF寬度gamma以及C.不同的參數選擇得到的分類性能可能會顯著不同。現在SVM的研究的一個重要方向就是構造更有效的核函數但是目前被認可的主要有三種:RBF核函數, 多項式核函數以及多層感知器核函數一般RBF核函數被應用的較多。

?

函數估計模型

沒有什么比用一個概率模型描述或然的現實世界更加保險的了,沒有什么比用一個函數來描述一個計算過程更加有效的了.因果永遠是理性思維最拿手的.X與Y的發生分別服從各自的分布,但如果(y|x)的分布特殊到某種境界,人們就會有興趣去想象Y與X的因果關系.我們簡化現實模型,將兩者的關系夸張到y是x的函數的程度.目的是確定這個函數,根據任意未知的x,給出盡量接近y的預測.候選函數的集合由我們事先給定,計算機需要做的是根據已知的一些(x,y)從函數集合中選擇一個盡量使得預測性能最好.

?

風險最小化;經驗風險最小化(ERM)

最保守的風險最小化評價一定是要在真實(x,y)的概率分布下對差異積分.而真實概率分布是難以獲取的,因此根據類似大數定理的思維方式,能大膽地認為在樣例足夠多的時候,可以用經驗風險最小化的評價方法.也就是在評價時以學習樣例完全代替(x,y)的真實概率分布.

?

一致性;VC熵

問題是這兩種評價的結果是否總是在樣例無窮多的時候一致地逼近最優值呢.于是有了很多與一致性等價的命題.一個重要的概念是VC熵,反映了函數集在數目為l的樣本上期望的多樣性.它與l的比當l趨于無窮的時候如果收斂,等價于一個"一致雙邊收斂"的命題.

?

置信范圍;VC維

但無情的現實是樣例數往往難以達到讓我們認為它已經接近無窮多的程度,特別是在比如TC中還會遇到無處不在的Zipf定律.于是我們不得不估計樣例數與兩種評價結果差距的關系,這種差距叫做置信范圍.由此又得到很多不等式.再引入函數集的VC維h.h刻畫的是函數集肆意劃分樣例的能力,它也直接影響了置信范圍.這種肆意劃分的能力越小,說明置信范圍可能越小.

?

結構風險最小化(SRM)

于是在l一定的時候,我們需要折中的就是選用的函數集的大小.將原有函數集表示成一個嵌套序列,使得他們的VC維h單調.首先選擇風險上限(經驗風險+置信范圍)最低時對應的h和函數集子集,在從中選擇經驗風險最小的函數,這樣的優化策略稱為結構風險最小化.

?

支持向量機(SVM);支持向量

支持向量機(SVM)號稱可以在保證經驗風險固定較小的前提下,盡量最小化置信范圍.其方法是在一個特征空間(好像要是Hilbert空間)上,找出劃分兩個點集的最優超平面,即使得兩個點集沿該平面間隙最大.剛好落在這個間隙邊上的向量叫做支持向量.這樣的最大化據說就可以和置信范圍最小化等價.VC維在這樣的過程中是如何發生微妙變化的我還不太清楚.在兩個點集不能用超平面完全劃分的時候也有與此相適應的算法.推導顯示求這樣一個超平面,等價于求一個約束二次規劃問題.

?

核函數

還有一個令人慶幸的事實是如果只要求訓練這樣的超平面并對以后的數據做劃分.SVM并不需要知道樣例在特征空間中的向量表達或者甚至不需要知道特征空間的維數.它只需要知道任意兩個樣例映射到此空間后向量的內積.而這樣的內積可以在樣例(訓練集或測試集中的)被映射成某個不可琢磨的特征空間中的向量之前被計算出來,完成這樣計算的函數叫核函數.即使樣例到特征空間的映射關系都不知道,只要該核函數滿足偉大的Mercer定理,這樣的特征空間就總能存在,SVM就能工作.

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的svm涉及的一些概念的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。