統(tǒng)計(jì)學(xué)習(xí)理論與支持向量機(jī)

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

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

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

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

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