模式識(shí)別第十三章

模式識(shí)別第十三章第1頁，共42頁，2023年，2月20日，星期五2）經(jīng)驗(yàn)非線性方法如人工神經(jīng)網(wǎng)絡(luò)（ANN）利用已知樣本建立非線性模型。缺點(diǎn)：缺乏一種統(tǒng)一的數(shù)學(xué)理論統(tǒng)計(jì)學(xué)習(xí)理論

—針對(duì)小樣本統(tǒng)計(jì)估計(jì)和預(yù)測(cè)的最佳理論第2頁，共42頁，2023年，2月20日，星期五1.統(tǒng)計(jì)學(xué)習(xí)理論基本思想由貝爾實(shí)驗(yàn)室Vapnik于1992年首次提出

研究小樣本下機(jī)器學(xué)習(xí)規(guī)律的理論。針對(duì)小樣本統(tǒng)計(jì)問題，建立了一套新的理論體系基本思想：折衷考慮經(jīng)驗(yàn)風(fēng)險(xiǎn)和推廣的置信界限，取得實(shí)際期望風(fēng)險(xiǎn)的最小化。即根據(jù)有限樣本信息在模型復(fù)雜性和學(xué)習(xí)能力之間尋求最佳折中兩大核心概念：VC維和結(jié)構(gòu)風(fēng)險(xiǎn)最小化。第3頁，共42頁，2023年，2月20日，星期五在這一理論基礎(chǔ)上，發(fā)展了一種新的通用模式識(shí)別方法——支持向量機(jī)（SVM）發(fā)展迅速，已經(jīng)在許多領(lǐng)域都取得了成功的應(yīng)用。

VC維的概念：（VC是取Vapnik和Chervonenkis名字的首字而成）描述函數(shù)集或?qū)W習(xí)機(jī)器的復(fù)雜性的指標(biāo)，即描述機(jī)器學(xué)習(xí)能力的重要指標(biāo)第4頁，共42頁，2023年，2月20日，星期五打散:若存在一個(gè)有h個(gè)樣本的樣本集，被一函數(shù)集里的某個(gè)函數(shù)按照所有可能的2h種形式分為兩類，則稱函數(shù)集能夠把樣本數(shù)為h的樣本集打散(shattering)。若對(duì)于任意的樣本數(shù)，總能找到一個(gè)樣本集能夠被這個(gè)函數(shù)集打散，則函數(shù)集的VC維就是無窮大。函數(shù)集的vc維：用這個(gè)函數(shù)集中的函數(shù)所能夠打散的最大樣本集的樣本數(shù)目。也就是說，如果存在h個(gè)樣本的樣本集能夠被函數(shù)集打散，而不存在有h＋1個(gè)樣本的樣本集能被函數(shù)集打散，則函數(shù)集的VC維就是h。第5頁，共42頁，2023年，2月20日，星期五例如：3個(gè)樣本被線性分類器打散的情況有2h＝23＝8種分類形式第6頁，共42頁，2023年，2月20日，星期五能打散VC維為3不能打散第7頁，共42頁，2023年，2月20日，星期五

VC維是目前為止對(duì)函數(shù)集學(xué)習(xí)性能的最好描述指標(biāo)。但遺憾的是目前尚沒有通用的關(guān)于如何計(jì)算任意函數(shù)集的VC維的理論。第8頁，共42頁，2023年，2月20日，星期五結(jié)構(gòu)風(fēng)險(xiǎn)最小化的思想Vapnik證明，期望風(fēng)險(xiǎn)與經(jīng)驗(yàn)風(fēng)險(xiǎn)之間的關(guān)系滿足如下公式：其中n表示樣本數(shù)，h為學(xué)習(xí)機(jī)器的VC維，稱為置信區(qū)間。是隨n/h增大而減小的函數(shù)。

VC維h越大，越大，經(jīng)驗(yàn)風(fēng)險(xiǎn)和期望風(fēng)險(xiǎn)之間的偏差越大。這樣即使在經(jīng)驗(yàn)誤差很小的情況下，其推廣誤差會(huì)越大。第9頁，共42頁，2023年，2月20日，星期五將函數(shù)集構(gòu)造為一個(gè)函數(shù)子集序列S1S2Sk,使各個(gè)子集按照VC維的大小排列（h1h2hk）。在每個(gè)子集中尋找最小經(jīng)驗(yàn)風(fēng)險(xiǎn),隨子集復(fù)雜度增加而減小，在子集間折衷考慮經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信界限,取得實(shí)際風(fēng)險(xiǎn)的最小

第10頁，共42頁，2023年，2月20日，星期五結(jié)構(gòu)風(fēng)險(xiǎn)最小就是根據(jù)函數(shù)集的性質(zhì)將它劃分成一系列嵌套的子集，學(xué)習(xí)問題就是選擇最好的子集(根據(jù)推廣能力)和在子集中選擇最好的函數(shù)（根據(jù)經(jīng)驗(yàn)風(fēng)險(xiǎn)）

SVM是一種比較好地實(shí)現(xiàn)了結(jié)構(gòu)風(fēng)險(xiǎn)最小化思想的方法第11頁，共42頁，2023年，2月20日，星期五分類超平面的一些基本概念W是超平面H的法向量,決定超平面的方向；b決定超平面的位置。兩類問題：g(x)表示分類面第12頁，共42頁，2023年，2月20日，星期五2.支持向量機(jī)算法找到一個(gè)超平面，使得它能夠盡可能多的將兩類數(shù)據(jù)點(diǎn)正確的分開，同時(shí)使分開的兩類數(shù)據(jù)點(diǎn)距離分類面最遠(yuǎn)。目標(biāo)：解決方法：構(gòu)造一個(gè)在約束條件下的優(yōu)化問題。

SVM是利用核函數(shù)將輸入向量映射到一個(gè)高維特征空間,并在該空間內(nèi)構(gòu)造一個(gè)最優(yōu)超平面來逼近分類函數(shù)。最優(yōu)分類超平面的構(gòu)造最終可以歸結(jié)為二次尋優(yōu)問題。第13頁，共42頁，2023年，2月20日，星期五由于SVM在解決小樣本，非線性及高維模式識(shí)別問題中表現(xiàn)出許多特有的優(yōu)勢(shì)，因此受到廣泛的關(guān)注。最優(yōu)分類面：1）線性可分情況：對(duì)于線性可分問題，是在經(jīng)驗(yàn)風(fēng)險(xiǎn)為零時(shí)，最小化置信范圍。第14頁，共42頁，2023年，2月20日，星期五使兩類無錯(cuò)誤的分開，且使兩類的分類空隙最大，前者是保證經(jīng)驗(yàn)風(fēng)險(xiǎn)盡可能小,后者是使真實(shí)風(fēng)險(xiǎn)最小。第15頁，共42頁，2023年，2月20日，星期五SVM問題的數(shù)學(xué)表示（線性可分情況）設(shè)兩類線性可分訓(xùn)練樣本集為，d維空間，線性判別函數(shù)的一般形式為：第16頁，共42頁，2023年，2月20日，星期五存在超平面為：使得訓(xùn)練樣本中的正類輸入和負(fù)類輸入分別位于該超平面兩側(cè)。決策面方程許多決策平面都可以將兩類樣本分開，應(yīng)選擇哪一個(gè)呢？存在參數(shù)（w，b），使得：第17頁，共42頁，2023年，2月20日，星期五Class1Class2目標(biāo)：最優(yōu)分類面滿足條件：經(jīng)驗(yàn)風(fēng)險(xiǎn)最?。ㄥe(cuò)分最少） 推廣能力最大（空白最大）第18頁，共42頁，2023年，2月20日，星期五Class1Class2H2H3W’H1H如圖所示，假定劃分直線的法方向已給定。直線H1是一條以w’為法向量且能正確劃分兩類樣本的直線。如何尋找最優(yōu)面？第19頁，共42頁，2023年，2月20日，星期五這樣的直線并不唯一。如果平行推移直線H1

，直到碰到某類訓(xùn)練點(diǎn)，就可得到兩條極端直線H2和H3

，在直線H2和H3之間的平行直線都能正確分類。顯然在H2和H3中間的那條直線H為最好。

以上給出了在已知法向量w’情況下構(gòu)造劃分直線的方法。這樣就把問題歸結(jié)為尋求法向量w及b。要讓H滿足wTx＋b＝0，則必須尋找最佳(w、b)第20頁，共42頁，2023年，2月20日，星期五判別函數(shù)歸一化：假如H可表示為：因?yàn)镠在中間，顯然H2可表示為：H3可表示為：兩邊同除以k，令，第21頁，共42頁，2023年，2月20日，星期五則H為：H2為：H3為：該過程稱為分類直線的規(guī)范化過程（即判別函數(shù)歸一化）。此時(shí)兩條直線H2和H3之間的間隔為：第22頁，共42頁，2023年，2月20日，星期五如前所述，對(duì)于適當(dāng)?shù)姆ㄏ蛄?，?huì)有兩條極端的直線，這兩條直線之間有間隔。最優(yōu)分類直線就應(yīng)該是兩直線間隔最大的那個(gè)法向量所表示的直線。第23頁，共42頁，2023年，2月20日，星期五分類平面應(yīng)使兩類之間的間隔最大。歸一化后分類面方程應(yīng)滿足：即：如何尋找w及b對(duì)于任意樣本x有：第24頁，共42頁，2023年，2月20日，星期五Class1Class2m圖中分類間隔為第25頁，共42頁，2023年，2月20日，星期五SVM基本思想：就是最大化分類間隔，因此等價(jià)于

最小化。因此，求取最優(yōu)平面問題就轉(zhuǎn)化為優(yōu)化問題。因?qū)τ谒袠颖荆?）

滿足式（1），且使最小的分類面就是最優(yōu)分類面第26頁，共42頁，2023年，2月20日，星期五求極值：可用拉格朗日乘子法求解引入拉格朗日乘子i0，設(shè)Lagrange函數(shù)為：（2）使式(1)等號(hào)成立的樣本（即H2

和H3

上的樣本）就叫支持向量。在條件式（1）下，求函數(shù)的最小值。第27頁，共42頁，2023年，2月20日，星期五（2）式是一個(gè)二次優(yōu)化問題，存在唯一最優(yōu)解。把該式分別對(duì)w、b求偏導(dǎo)，并使其等于零，即：將上面兩式帶入（2），可得到下式：第28頁，共42頁，2023年，2月20日，星期五于是，對(duì)w和b求拉個(gè)朗日函數(shù)的極小值來求解最優(yōu)分類面問題，可轉(zhuǎn)化為在如下約束條件下（為樣本數(shù)目）（３）對(duì)i求解下列函數(shù)的最大值（４）為與約束條件

對(duì)應(yīng)的拉格朗日乘子。訓(xùn)練樣本之間的內(nèi)積第29頁，共42頁，2023年，2月20日，星期五這也是一個(gè)二次函數(shù)尋優(yōu)問題，存在唯一解。解中只有支持向量對(duì)應(yīng)的系數(shù)i為非零值，即：只有支持向量影響最終的劃分結(jié)果。若為最優(yōu)解，則任取，可求得（可用支持向量求得）。第30頁，共42頁，2023年，2月20日，星期五由任一支持向量通過式(1)可求得b*。則最優(yōu)分類函數(shù)為：（6）

式中求和實(shí)際只對(duì)支持向量進(jìn)行（非支持向量對(duì)應(yīng)的為0），b*是分類閾值，可用任意支持向量（滿足（1）式的等號(hào)）求得，或通過兩類中任意一對(duì)支持向量取中值求得。待分樣本x與支持向量xi的內(nèi)積第31頁，共42頁，2023年，2月20日，星期五2.線性不可分情況約束條件：（7）（8）引入松弛項(xiàng)，使得允許存在錯(cuò)分樣本，對(duì)應(yīng)的優(yōu)化問題變?yōu)椋旱?2頁，共42頁，2023年，2月20日，星期五在約束條件下，求式（7）的極小值，可得線性不可分情況下的最優(yōu)分類面，稱為廣義最優(yōu)分類面。對(duì)i

求解下式的最大值。同理，利用拉格朗日乘子法，可把求解廣義最優(yōu)分類面問題轉(zhuǎn)化為在如下約束條件下：C為可調(diào)參數(shù)，即懲罰因子（C越大，懲罰越重），稱這種SVM為C—SVM訓(xùn)練樣本之間的內(nèi)積第33頁，共42頁，2023年，2月20日，星期五

在保留松馳項(xiàng)i的基礎(chǔ)上，引入一新的參數(shù)V來控制支持向量的數(shù)目和誤差，改進(jìn)算法：V－SVM約束條件：，第34頁，共42頁，2023年，2月20日，星期五對(duì)應(yīng)的對(duì)偶問題：在如下約束條件下：求最小值，即（9）第35頁，共42頁，2023年，2月20日，星期五相應(yīng)的判別函數(shù)也變?yōu)椋涸嫉腟VM是兩類分類器，對(duì)于多類分類問題需進(jìn)行擴(kuò)展，常用的方法有一類對(duì)余類和一類對(duì)一類。

（10）第36頁，共42頁，2023年，2月20日，星期五3.非線性SVM：可通過某種非線性變換轉(zhuǎn)化為另一空間的線性問題，在此線性空間求解最優(yōu)或廣義最優(yōu)分類面，即將非線性問題映射為線性問題。注意到無論訓(xùn)練樣本是否線性可分，求解其對(duì)應(yīng)的優(yōu)化問題以及最終得到的最優(yōu)分類超平面都只需計(jì)算原始特征空間中樣本間的內(nèi)積，而不需要知道從原始特征空間到高維特征空間的非線性映射的具體形式第37頁，共42頁，2023年，2月20日，星期五

非線性SVM采用核函數(shù)，將引入向量x，通過映射：RnH，即映射到Hilert空間。設(shè)核函數(shù)k滿足下式：第38頁，共42頁，2023年，2月20日，星期五一般不需要知道的具體形式和所屬空間，只需一種核函數(shù)滿足Mercer條件，它就對(duì)應(yīng)某一變換空間中的內(nèi)積，即對(duì)函數(shù)g(x)不恒為0,且所以采用引入適當(dāng)核函數(shù)k的方法，就可實(shí)現(xiàn)非線性變換后的線性分類。事實(shí)上，在取核函數(shù)為點(diǎn)積形式時(shí)，就是線性SVM。則有：第39頁，共42頁，2023年，2月20日，星期五對(duì)不同的核函數(shù)，對(duì)應(yīng)不同的SVM，常用的幾種有：1、線性SVM：2、多項(xiàng)式SVM：（為多項(xiàng)式的階數(shù)）3、高斯核函數(shù)SVM：（為方差）