統(tǒng)計學習理論與支持向量機

統(tǒng)計學習理論與支持向量機機器學習概述Simon對學習的論述：“如果一個系統(tǒng)能夠通過執(zhí)行某個過程改進它的性能，這就是學習?！?983年simon進一步指出：“學習就是系統(tǒng)的適應性，這意味著這些改進使得系統(tǒng)能夠更有效的完成同樣的工作或者類似的工作?！睓C器學習就是通過對已知事實的分析總結規(guī)律，預測無法直接預測的事實。目的：設計某種方法，通過對已知數(shù)據(jù)的學習，找到數(shù)據(jù)內(nèi)在的相互依賴關系，從而對未知數(shù)據(jù)進行預測或?qū)ζ湫再|(zhì)進行判斷。泛化能力：推廣能力，對未知數(shù)據(jù)進行預測和判斷的能力。機器學習問題的一般表示

系統(tǒng)S是研究對象，符合某一未知的聯(lián)合概率分布F(x,y)。在給定的輸入x下得到系統(tǒng)的輸出y。在訓練過程中，輸入與輸出組成獨立同分布的訓練樣本(x,y)求出學習機器，在測試過程中，訓練后的學習機器對于輸入x給出預測y’Assumption:(iid)Hypothesisspace:Lossfunction:Objectivefunction

從一組獨立同分布的觀測樣本出發(fā)，通過最小化期望風險R(w)，確定學習機器的廣義參數(shù)w的過程。經(jīng)驗風險最小化根據(jù)概率論中大數(shù)定律的思想，用算術平均代替設計學習算法時，用對w求經(jīng)驗風險的最小值代替求期望風險的最小值，實現(xiàn)所謂的經(jīng)驗風險最小化原則。大數(shù)定律說明當樣本數(shù)趨于無窮多時，概率意義下趨于，并不保證在同一點上取最小值。當前提不成立時，能否找到更合理的原則？統(tǒng)計學習理論的簡介：統(tǒng)計學習理論研究小樣本情況下機器學習理論。始于60年代。1962年，rosenblatt提出了第一個機器學習的模型—感知機，標志人們對學習問題進行研究的真正開始。Vapnic在1974年提出的結構風險最小化原則對統(tǒng)計機器學習具有劃時代的意義。統(tǒng)計學習理論用VC維來描述學習機器的性能，并從控制學習機器的性能的角度出發(fā)，結合經(jīng)驗風險和訓練樣本，導出學習機器的泛化上界。學習機器的VC維VC維的直觀定義：對一個指示函數(shù)集，如果存在h個樣本能夠被函數(shù)集中的函數(shù)按所有可能的2種形式分開，函數(shù)集的VC維是h目前沒有通用的關于任意函數(shù)集VC維的計算理論，只有一些特殊函數(shù)知道其VC維。n維實數(shù)空間中線性分類器和線性實函數(shù)的VC維是n+1，而的VC維則為無窮大。h推廣性的界統(tǒng)計學習理論從VC維的概念出發(fā)，推導出經(jīng)驗風險和實際風險之間關系的重要結論，稱作推廣性的界。Vapnik證明，下列邊界以成立：

h是函數(shù)集的VC維，n是樣本數(shù)，是置信范圍。為最小化期望風險，應同時最小化經(jīng)驗風險和假設空間的VC維。結構風險最小化原理把函數(shù)集分解為一個函數(shù)子集序列，使各個子集按照VC維的大小排列，在每個子集中尋找最小經(jīng)驗風險，在子集間折衷考慮經(jīng)驗風險和置信范圍，取得實際風險最小。實現(xiàn)結構風險最小化的兩種思路：一是在每個子集中求最小經(jīng)驗風險，然后選擇使最小經(jīng)驗風險和置信范圍之和最小的子集。顯然這種方法比較費時，當子集數(shù)目很大甚至是無窮時不可行。二是設計函數(shù)集的某種結構使每個子集中都能夠取得最小的經(jīng)驗風險（如使訓練誤差為0），然后選擇適當?shù)淖蛹怪眯欧秶钚?，則這個子集使經(jīng)驗風險最小的函數(shù)便是最優(yōu)函數(shù)。支持向量機簡介支持向量機(SVM)是由Vapnik領導的AT＆TBell實驗室研究小組在1963年提出。1995年Cortes和Vapnic首先提出比較完善的SVM方法。支持向量機是建立在統(tǒng)計學習理論的VC維理論和結構風險最小化原理基礎上的，根據(jù)有限樣本信息在模型復雜性和學習能力之間尋求最佳折衷，以期獲得最好的泛化能力。支持向量機優(yōu)點針對有限樣本情況。算法最終將轉(zhuǎn)化為一個二次型尋優(yōu)問題，從理論上講，得到的將是全局最優(yōu)點，解決了在神經(jīng)網(wǎng)絡中無法避免的局部極值問題。算法將實際問題通過特征映射，映射到高維特征空間，在高維空間中構造線性判別函數(shù)來實現(xiàn)原空間中的非線性判別函數(shù)。解決了維數(shù)災難問題，其算法復雜度與樣本維數(shù)無關。邊緣的概念及其泛化界統(tǒng)計學習理論中，泛化界是通過VC維得到的，通過控制函數(shù)集的VC維，以便獲得最好的學習機器泛化性能。引入一種基于邊緣的泛化界思想，將邊緣的概念引入到學習算法中去。難以計算泛化不等式泛化不等式告訴我們可以通過控制邊緣來控制泛化界，從而可以將優(yōu)化目標定為求取最大邊緣分類器，也即所謂的最大邊緣算法。直觀上看，樣本點離分界面越遠，邊緣越大，泛化性能越好。線性可分情形最大邊緣算法假設給定訓練樣本集：其中服從獨立同分布，為樣本類別標簽。

支持向量機本質(zhì)上是處理二分類問題的。支持向量機的目的是構造最優(yōu)超平面，將兩類正確分開（錯誤率為0），且分類邊緣最大。分類面方程：歸一化：分類邊緣：使分類邊緣最大等價于使求解：利用Lagrange乘子法轉(zhuǎn)化為對偶優(yōu)化問題構造Lagrange函數(shù)為對應的Lagrange乘子對w,b分別求偏導將和代入Lagrange化簡為對偶式：由上式求得最優(yōu)解其中為一類的任意支持向量，為另一類的任意支持向量。支持向量是在中滿足等號的那些向量，也就是落在兩側邊界超平面上的向量。支持向量在w的展開式中對應的系數(shù)a非零，權向量w是支持向量集合的線性組合，各個支持向量對這個線性組合的貢獻就是它們Lagrange系數(shù)與y的乘積。分類超平面函數(shù)：支持向量方法的優(yōu)點通過化簡為對偶優(yōu)化形式，變成一個凸二次優(yōu)化問題，其局部解一定是全局最優(yōu)解，這是神經(jīng)網(wǎng)絡研究多年沒有實現(xiàn)的目標。僅與樣本點內(nèi)積運算有關，不涉及樣本點本身計算，為核技巧處理非線性問題奠定了基礎。支持向量只占全體樣本中很少一部分。線性不可分問題的軟邊緣算法由于樣本中小概率事件和噪聲的存在，極個別的樣本點就會嚴重影響分類器泛化性能，即導致對訓練樣本線性不可分。C.coters和V.Vapnic通過引入松弛變量提出軟邊緣算法。第一項控制的是泛化能力，第二項是懲罰項，控制分類錯誤?？煽醋魇怯柧殬颖娟P于（廣義）分類超平面的偏差，為線性可分情況。C為預先確定好的正實數(shù)，實現(xiàn)算法復雜度與錯分樣本間的折中。當=1時，稱為l1范數(shù)C-SVM；當=2時，稱為l2范數(shù)C-SVM。采用Lagrange乘子法求解，約束條件為線性可分與不可分超平面對比非線性問題與核技巧非線性問題可以通過適當?shù)奶卣饔成渥儞Q為另一個空間的線性可分問題，變換空間的維數(shù)一般會增加。增加空間的維數(shù)會陷入“維數(shù)災難”?！痢痢痢痢痢痢痢痢痢痢痢痢痢痢痢痢痢義1、x2××××××××z3z1z2核技巧的基本思想我們注意到了在討論最大邊緣和軟邊緣算法時，其最終的分類判別函數(shù)式中只包含待分類樣本與訓練樣本中的內(nèi)積運算，不涉及樣本本身的運算。于是要解決一個特征空間中的最優(yōu)線性分類問題，只需要知道在原空間中的內(nèi)積運算，而不需要具體的映射函數(shù)，因此可以避免“維數(shù)災難”問題這就是核技巧的基本思想。常用核函數(shù)類型：多項式類型:徑向基