人工智能之支持向量機(jī)PPT學(xué)習(xí)課件

1、支持向量機(jī) Support Vector Machines,內(nèi)容提要,統(tǒng)計(jì)學(xué)習(xí)方法概述 統(tǒng)計(jì)學(xué)習(xí)問題 學(xué)習(xí)過程的泛化能力 支持向量機(jī) SVM尋優(yōu)算法 應(yīng)用,支持向量機(jī),SVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法，它是由Boser,Guyon, Vapnik在COLT-92上首次提出，從此迅速發(fā)展起來 Vapnik V N. 1995. The Nature of Statistical Learning Theory. Springer-Verlag, New York Vapnik V N. 1998. Statistical Learning Theory. Wiley-Interscie

2、nce Publication, John Wiley yi+1,-1 Hyperplane: wx+b=0 This is fully determined by (w,b),w1x+b1=0,w2x+b2=0,w3x+b3=0,2,11,最大間隔,一個(gè)超平面，如果它能將訓(xùn)練樣本沒有錯(cuò)誤地分開，并且兩類訓(xùn)練樣本中離超平面最近的樣本與超平面之間的距離是最大的，則把這個(gè)超平面稱作最優(yōu)分類超平面（optimal separating hyperplane），兩類樣本中離分類面最近的樣本到分類面的距離稱為分類間隔，最優(yōu)超平面也可以稱作最大間隔超平面。,2,12,最大間隔原則,Note1: decis

3、ion functions (w,b) and (cw, cb) are the same Note2: but margins as measured by the outputs of the function xwx+b are not the same if we take (cw, cb). Definition: geometric margin: the margin given by the canonical decision function, which is when c=1/|w| Strategy: 1) we need to maximise the geomet

4、ric margin! (cf result from learning theory) 2) subject to the constraint that training examples are classified correctly,w,wx+b=0,wx+b0,wx+b0,2,13,支持向量,The training points that are nearest to the separating function are called support vectors. What is the output of our decision function for these p

5、oints?,2,14,分類問題的數(shù)學(xué)表示,已知：訓(xùn)練集包含 個(gè)樣本點(diǎn)： 說明： 是輸入指標(biāo)向量，或稱輸入，或稱模式，其分 量稱為特征，或?qū)傩裕蜉斎胫笜?biāo)； 是輸出指標(biāo)，或輸出. 問題：對一個(gè)新的模式 ，推斷它所對應(yīng)的輸出 是1還是-1. 實(shí)質(zhì)：找到一個(gè)把 上的點(diǎn)分成兩部分的規(guī)則.,2維空間上的分類問題) n維空間上的分類問題.,2,15,根據(jù)給定的訓(xùn)練集 其中， ，尋找 上的一個(gè)實(shí) 值函數(shù) ，用決策函數(shù) 判斷任一模式 對應(yīng)的 值.sgn()為符號函數(shù)，取自變量的符號。 可見，分類學(xué)習(xí)機(jī)構(gòu)造決策函數(shù)的方法(算法)， 兩類分類問題 多類分類問題 線性分類學(xué)習(xí)機(jī) 非線性分類學(xué)習(xí)機(jī),分類學(xué)習(xí)方法,2

6、,16,SVM分類問題大致有三種：線性可分問題、近似線性可分問題、線性不可分問題。,分類學(xué)習(xí)方法,Chap8 SVM Zhongzhi Shi,2,17,考慮 上的線性可分的分類問題. 這里有許多直線 能將兩類點(diǎn)正確分開. 如何選取 和 ？ 簡單問題：設(shè)法方向 已選定，如何選取 ？ 解答： 選定 平行直線 極端直線 和 取 和 的中間線為分劃直線 如何選取 ？ 對應(yīng)一個(gè) ，有極端直線 ，稱 和 之間的距 離為“間隔”.顯然應(yīng)選使“間隔”最大的 。,最大間隔法的直觀導(dǎo)出,2,18,數(shù)學(xué)語言描述,調(diào)整 ，使得,令 ，則兩式可以等價(jià)寫為,與此相應(yīng)的分劃直線表達(dá)式:,給定適當(dāng)?shù)姆ǚ较?后，這兩條極端直

7、線 可表示為,Chap8 SVM Zhongzhi Shi,2,19,如何計(jì)算分劃間隔？ 考慮2維空間中極端直線之間的間隔情況,求出兩條極端直線的距離：,Chap8 SVM Zhongzhi Shi,2,20,Margin =,H1平面：,H2平面：,.(2),.(1),Chap8 SVM Zhongzhi Shi,2,21,分劃直線表達(dá)式為 “間隔” 為 極大化“間隔”的思想導(dǎo)致求解下列對變量 和 的最優(yōu)化問題 說明：只要我們求得該問題的最優(yōu)解 ，從而構(gòu)造分劃 超平面 ，求出決策函數(shù) 。 上述方法對一般 上的分類問題也適用.,原始問題,Chap8 SVM Zhongzhi Shi,2,22,

8、求解原始問題,為求解原始問題，根據(jù)最優(yōu)化理論，我們轉(zhuǎn)化為對偶問題來求解,對偶問題,為原始問題中與每個(gè)約束條件對應(yīng)的Lagrange乘子。這是 一個(gè)不等式約束條件下的二次函數(shù)尋優(yōu)問題，存在唯一解,2,23,線性可分問題,計(jì)算 ，選擇 的一個(gè)正分量 , 并據(jù)此計(jì)算,事實(shí)上， 的每一個(gè)分量 都與一個(gè)訓(xùn)練點(diǎn)相對應(yīng)。而分劃超平面僅僅依賴于 不為零的訓(xùn)練點(diǎn) ，而與對應(yīng)于 為零的那些訓(xùn)練點(diǎn)無關(guān)。,稱 不為零的這些訓(xùn)練點(diǎn)的輸入 為支持向量(SV),構(gòu)造分劃超平面 ,決策函數(shù),根據(jù)最優(yōu)解,2,24,近似線性可分問題,不要求所有訓(xùn)練點(diǎn)都滿足約束條件 ，為此 對第 個(gè)訓(xùn)練點(diǎn) 引入松弛變量(Slack Variabl

9、e) , 把約束條件放松到 。,體現(xiàn)了訓(xùn)練集被錯(cuò)分的情況，可采用 作 為一種度量來描述錯(cuò)劃程度。,兩個(gè)目標(biāo)：1. 間隔 盡可能大 2. 錯(cuò)劃程度 盡可能小,顯然，當(dāng) 充分大時(shí)，樣本點(diǎn) 總可以滿足以上約束條件。 然而事實(shí)上應(yīng)避免 太大，所以需在目標(biāo)函數(shù)對 進(jìn)行懲罰,（即“軟化” 約束條件）,Chap8 SVM Zhongzhi Shi,2,25,因此，引入一個(gè)懲罰參數(shù) ，新的目標(biāo)函數(shù)變?yōu)?,體現(xiàn)了經(jīng)驗(yàn)風(fēng)險(xiǎn)，而 則體現(xiàn)了表達(dá)能力。所以 懲罰參數(shù) 實(shí)質(zhì)上是對經(jīng)驗(yàn)風(fēng)險(xiǎn)和表達(dá)能力匹配一個(gè)裁決。 當(dāng) 時(shí)，近似線性可分SVC的原始問題退化為線性可分 SVC的原始問題。,近似線性可分問題,Chap8 SVM

10、Zhongzhi Shi,2,26,(廣義)線性支持向量分類機(jī)算法,設(shè)已知訓(xùn)練集 ，其中,2. 選擇適當(dāng)?shù)膽土P參數(shù) ，構(gòu)造并求解最優(yōu)化問題,3. 計(jì)算 ，選擇 的一個(gè)分量 ，并據(jù)此 計(jì)算出,4. 構(gòu)造分劃超平面 ,決策函數(shù),求得,2,27,非線性分類,例子:,2,28,Non-linear Classification,What can we do if the boundary is nonlinear ?,Idea:,transform the data vectors to a space where the separator is linear,Chap8 SVM Zhongzhi

11、Shi,2,29,Non-linear Classification,The transformation many times is made to an infinite dimensional space, usually a function space. Example: x cos(uTx),Chap8 SVM Zhongzhi Shi,2,30,Non-linear SVMs,Transform x (x) The linear algorithm depends only on xxi, hence transformed algorithm depends only on (

12、x)(xi) Use kernel function K(xi,xj) such that K(xi,xj)= (x)(xi),2,31,設(shè)訓(xùn)練集 ，其中 假定可以用 平面上的二次曲線來分劃：,現(xiàn)考慮把2維空間 映射到6維空間的變換,上式可將2維空間上二次曲線映射為6維空間上的一個(gè)超平面：,非線性分類,2,32,可見，只要利用變換，把 所在的2維空間的兩類輸入點(diǎn)映射到 所在的6維空間，然后在這個(gè)6維空間中，使用線性學(xué)習(xí)機(jī)求出分劃超平面：,最后得出原空間中的二次曲線：,怎樣求6維空間中的分劃超平面？(線性支持向量分類機(jī)),非線性分類,2,33,需要求解的最優(yōu)化問題,其中,非線性分類,2,34,在

13、求得最優(yōu)化問題的解 后，得到分劃超平面,其中,最后得到?jīng)Q策函數(shù),或,線性分劃非線性分劃代價(jià)：2維空間內(nèi)積6維空間內(nèi)積,非線性分類,2,35,為此，引進(jìn)函數(shù),有,比較(2)和(3)，可以發(fā)現(xiàn),這是一個(gè)重要的等式，提示6維空間中的內(nèi)積 可以通過計(jì)算 中2維空間中的內(nèi)積 得到。,非線性分類,2,36,實(shí)現(xiàn)非線性分類的思想,給定訓(xùn)練集后，決策函數(shù)僅依賴于 而不需要再考慮非線性變換 如果想用其它的非線性分劃辦法，則可以考慮選擇其它形式 的函數(shù) ，一旦選定了函數(shù)，就可以求解最優(yōu)化問題,得 ，而決策函數(shù),2,37,決策函數(shù),其中,實(shí)現(xiàn)非線性分類的思想,2,38,多項(xiàng)式內(nèi)核 徑向基函數(shù)內(nèi)核RBF Sigmoi

14、nd內(nèi)核,目前研究最多的核函數(shù)主要有三類：,得到q 階多項(xiàng)式分類器,每個(gè)基函數(shù)中心對應(yīng)一個(gè)支持向量，它們及輸出權(quán)值由算法自動(dòng)確定,包含一個(gè)隱層的多層感知器，隱層節(jié)點(diǎn)數(shù)是由算法自動(dòng)確定,核函數(shù)的選擇,Chap8 SVM Zhongzhi Shi,SVM算法實(shí)現(xiàn)軟件,LIBSVM：臺灣大學(xué)林智仁教授等開發(fā)，有各種版本，應(yīng)用很廣泛 LS-SVMLAB：Matlab界面，分類、回歸都可 OSU_SVM：用于分類，可以實(shí)現(xiàn)多分類 SVM toolbox: Matlab界面，代碼簡單，適合初學(xué)者了解原理，但算法效率較低,39,有關(guān)SVM的網(wǎng)站, www.sup

15、port- .tw/cjlin/libsvm www.esat.kuleuven.ac.be/sista/lssvmlab ,40,SVM預(yù)測模型的建立,核函數(shù)的選擇 在實(shí)驗(yàn)中選取RBF函數(shù)作為核函數(shù)的首選，原因： 1.RBF函數(shù)可以將樣本非線性地規(guī)劃到更高維的空間中，從而實(shí)現(xiàn)非線形影射。Sigmoid核函數(shù)取某些特定參數(shù)時(shí)性能和RBF相同。 2.RBF函數(shù)的參數(shù)只有一個(gè)。相比之下多項(xiàng)式核函數(shù)參數(shù)比RBF核函數(shù)多，因此其模型選擇更為復(fù)雜。 3.RBF函數(shù)的數(shù)值限制條件少。RBF函數(shù)使數(shù)值被限制在0和1之間，而多項(xiàng)式核函數(shù)的值可能會(huì)趨于不定值 或零值 且冪值更高；

16、Sigmoid核函數(shù)在取某些參數(shù)值時(shí)則可能無效。,41,SVM預(yù)測模型的建立（續(xù)）,C和r和選?。ㄒ苑诸悶槔?選定一組C,r的范圍 和 ,然后將它們的準(zhǔn)確率用等高線連接起來繪出類似下圖。,42,用SVM實(shí)現(xiàn)煤炭需求量的預(yù)測,任務(wù)：用1980-2002年的我國煤炭需求量來預(yù)測2003-2006年的煤炭需求量 將歷年的煤炭消費(fèi)量X(t)看作時(shí)間序列，則其預(yù)測模型可以描述為 其中為非線形函數(shù)，p為嵌入維數(shù)， 根據(jù)上式,可以得到輸入樣本和輸出樣本,這里用1999-2002年的數(shù)據(jù)作為檢驗(yàn)樣本, 分別用SVM和神經(jīng)網(wǎng)絡(luò)預(yù)測，結(jié)果為:,43,用SVM實(shí)現(xiàn)煤炭需求量的預(yù)測,用訓(xùn)練好的SVM模型來預(yù)測將來2

17、003-2006年的煤炭需求量，其需求趨勢如下圖：,2003-2006年的預(yù)測值,44,有待解決的問題,1.如何合選擇SVM的參數(shù)：怎樣合理選擇支持向量的核參數(shù)，目前尚無定論。格子搜索法比較常見，有的 學(xué)者已提出用遺傳算法、粒子群算法等優(yōu)化參數(shù) 2.如何實(shí)現(xiàn)時(shí)間序列的動(dòng)態(tài)預(yù)測：動(dòng)態(tài)預(yù)測要求SVM的參數(shù)能適應(yīng)序列的動(dòng)態(tài)變化，即建立基于SVM自適應(yīng)預(yù)測控制系統(tǒng),45,2,46,SVM applications,Pattern recognition Features: words counts DNA array expression data analysis Features: expr. l

18、evels in diff. conditions Protein classification Features: AA composition,2,47,Handwritten Digits Recognition,2,48,Applying SVMs to Face Detection,The SVM face-detection system,1. Rescale the input image several times,2. Cut 19x19 window patterns out of the scaled image,3. Preprocess the window usin

19、g masking, light correction and histogram equalization,4. Classify the pattern using the SVM,5. If the class corresponds to a face, draw a rectangle around the face in the output image.,2,49,Applying SVMs to Face Detection,Experimental results on static images Set A: 313 high-quality, same number of faces Set B: 23 mixed quality, total of 155 faces,2,50,Applying SVMs to Face Detection,Extension to a real-time system,An example of the skin detection module implemented using SVMs,Face Detection