人工智能之支持向量機(jī)課件

支持向量機(jī)

SupportVectorMachines支持向量機(jī)

SupportVectorMachin內(nèi)容提要統(tǒng)計(jì)學(xué)習(xí)方法概述統(tǒng)計(jì)學(xué)習(xí)問(wèn)題學(xué)習(xí)過(guò)程的泛化能力支持向量機(jī)SVM尋優(yōu)算法應(yīng)用內(nèi)容提要統(tǒng)計(jì)學(xué)習(xí)方法概述支持向量機(jī)SVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法，它是由Boser,Guyon,Vapnik在COLT-92上首次提出，從此迅速發(fā)展起來(lái)VapnikVN.1995.TheNatureofStatisticalLearningTheory.Springer-Verlag,NewYorkVapnikVN.1998.StatisticalLearningTheory.Wiley-IntersciencePublication,JohnWiley&Sons,Inc目前已經(jīng)在許多智能信息獲取與處理領(lǐng)域都取得了成功的應(yīng)用。

支持向量機(jī)SVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法，它是由支持向量機(jī)SVMSVMsarelearningsystemsthatuseahyperplaneoflinearfunctionsinahighdimensionalfeaturespace—Kernelfunctiontrainedwithalearningalgorithmfromoptimizationtheory—LagrangeImplementsalearningbiasderivedfromstatisticallearningtheory—GeneralisationSVMisaclassifierderivedfromstatisticallearningtheorybyVapnikandChervonenkis支持向量機(jī)SVMSVMsarelearningsys25

線(xiàn)性分類(lèi)器ayestf

xf(x,w,b)=sign(w.x

-b)denotes+1denotes-1Howwouldyouclassifythisdata?25線(xiàn)性分類(lèi)器ayestfxf(x,w,26線(xiàn)性分類(lèi)器f

xayestdenotes+1denotes-1f(x,w,b)=sign(w.x

-b)Howwouldyouclassifythisdata?26線(xiàn)性分類(lèi)器fxayestdenotes27線(xiàn)性分類(lèi)器f

xayestdenotes+1denotes-1f(x,w,b)=sign(w.x

-b)Howwouldyouclassifythisdata?27線(xiàn)性分類(lèi)器fxayestdenotes28線(xiàn)性分類(lèi)器f

xayestdenotes+1denotes-1f(x,w,b)=sign(w.x

-b)Howwouldyouclassifythisdata?28線(xiàn)性分類(lèi)器fxayestdenotes29線(xiàn)性分類(lèi)器f

xayestdenotes+1denotes-1f(x,w,b)=sign(w.x

-b)Howwouldyouclassifythisdata?哪一個(gè)分界面是最優(yōu)的？？29線(xiàn)性分類(lèi)器fxayestdenotes210分類(lèi)超平面Trainingset:(xi,yi),i=1,2,…N;yi{+1,-1}Hyperplane:wx+b=0Thisisfullydeterminedby(w,b)w1x+b1=0w2x+b2=0w3x+b3=0210分類(lèi)超平面Trainingset:(xi,yi)211最大間隔一個(gè)超平面，如果它能將訓(xùn)練樣本沒(méi)有錯(cuò)誤地分開(kāi)，并且兩類(lèi)訓(xùn)練樣本中離超平面最近的樣本與超平面之間的距離是最大的，則把這個(gè)超平面稱(chēng)作最優(yōu)分類(lèi)超平面（optimalseparatinghyperplane），兩類(lèi)樣本中離分類(lèi)面最近的樣本到分類(lèi)面的距離稱(chēng)為分類(lèi)間隔，最優(yōu)超平面也可以稱(chēng)作最大間隔超平面。211最大間隔一個(gè)超平面，如果它能將訓(xùn)練樣本沒(méi)有錯(cuò)誤地分開(kāi)，212最大間隔原則Note1:decisionfunctions(w,b)and

(cw,cb)arethesameNote2:butmarginsasmeasuredbytheoutputsofthefunctionxwx+barenotthesameifwetake(cw,cb).Definition:geometricmargin:themargingivenbythecanonicaldecisionfunction,whichiswhenc=1/||w||Strategy: 1)weneedtomaximisethegeometricmargin!(cfresultfromlearningtheory) 2)subjecttotheconstraintthattrainingexamplesareclassifiedcorrectlywwx+b=0wx+b>0wx+b<0212最大間隔原則Note1:decisionfunct213支持向量Thetrainingpointsthatarenearesttotheseparatingfunctionarecalledsupportvectors.Whatistheoutputofourdecisionfunctionforthesepoints?213支持向量Thetrainingpointstha214分類(lèi)問(wèn)題的數(shù)學(xué)表示已知：訓(xùn)練集包含個(gè)樣本點(diǎn)：

說(shuō)明：是輸入指標(biāo)向量，或稱(chēng)輸入，或稱(chēng)模式，其分量稱(chēng)為特征，或?qū)傩?，或輸入指?biāo)；是輸出指標(biāo)，或輸出.問(wèn)題：對(duì)一個(gè)新的模式，推斷它所對(duì)應(yīng)的輸出是1還是-1.實(shí)質(zhì)：找到一個(gè)把上的點(diǎn)分成兩部分的規(guī)則.

2維空間上的分類(lèi)問(wèn)題)n維空間上的分類(lèi)問(wèn)題.214分類(lèi)問(wèn)題的數(shù)學(xué)表示2維空間上的分類(lèi)問(wèn)題)215根據(jù)給定的訓(xùn)練集其中，，尋找上的一個(gè)實(shí)值函數(shù)，用決策函數(shù)

判斷任一模式對(duì)應(yīng)的值.sgn()為符號(hào)函數(shù)，取自變量的符號(hào)。

可見(jiàn)，分類(lèi)學(xué)習(xí)機(jī)——構(gòu)造決策函數(shù)的方法(算法)，兩類(lèi)分類(lèi)問(wèn)題多類(lèi)分類(lèi)問(wèn)題線(xiàn)性分類(lèi)學(xué)習(xí)機(jī)非線(xiàn)性分類(lèi)學(xué)習(xí)機(jī)

分類(lèi)學(xué)習(xí)方法215分類(lèi)學(xué)習(xí)方法216SVM分類(lèi)問(wèn)題大致有三種：線(xiàn)性可分問(wèn)題、近似線(xiàn)性可分問(wèn)題、線(xiàn)性不可分問(wèn)題。分類(lèi)學(xué)習(xí)方法Chap8SVMZhongzhiShi216SVM分類(lèi)問(wèn)題大致有三種：線(xiàn)性可分問(wèn)題、近似線(xiàn)性可分問(wèn)217考慮上的線(xiàn)性可分的分類(lèi)問(wèn)題.這里有許多直線(xiàn)能將兩類(lèi)點(diǎn)正確分開(kāi).如何選取和？簡(jiǎn)單問(wèn)題：設(shè)法方向已選定，如何選??？解答：選定平行直線(xiàn)極端直線(xiàn)和取和的中間線(xiàn)為分劃直線(xiàn)如何選??？對(duì)應(yīng)一個(gè)，有極端直線(xiàn)，稱(chēng)和之間的距離為“間隔”.顯然應(yīng)選使“間隔”最大的。

最大間隔法的直觀導(dǎo)出217考慮上的線(xiàn)性可分的分類(lèi)問(wèn)題.最大間隔法的直觀218數(shù)學(xué)語(yǔ)言描述調(diào)整，使得令，則兩式可以等價(jià)寫(xiě)為與此相應(yīng)的分劃直線(xiàn)表達(dá)式:給定適當(dāng)?shù)姆ǚ较蚝?，這兩條極端直線(xiàn)可表示為Chap8SVMZhongzhiShi218數(shù)學(xué)語(yǔ)言描述調(diào)整，使得令，則219如何計(jì)算分劃間隔？考慮2維空間中極端直線(xiàn)之間的間隔情況求出兩條極端直線(xiàn)的距離：Chap8SVMZhongzhiShi219如何計(jì)算分劃間隔？求出兩條極端直線(xiàn)的距離：Chap8220Margin=

H1平面：

H2平面：

…..(2)

…..(1)

Chap8SVMZhongzhiShi220Margin=H1平面：H2平面：…..(2)221分劃直線(xiàn)表達(dá)式為“間隔”為極大化“間隔”的思想導(dǎo)致求解下列對(duì)變量和的最優(yōu)化問(wèn)題說(shuō)明：只要我們求得該問(wèn)題的最優(yōu)解，從而構(gòu)造分劃超平面，求出決策函數(shù)。上述方法對(duì)一般上的分類(lèi)問(wèn)題也適用.原始問(wèn)題Chap8SVMZhongzhiShi221分劃直線(xiàn)表達(dá)式為222求解原始問(wèn)題為求解原始問(wèn)題，根據(jù)最優(yōu)化理論，我們轉(zhuǎn)化為對(duì)偶問(wèn)題來(lái)求解對(duì)偶問(wèn)題為原始問(wèn)題中與每個(gè)約束條件對(duì)應(yīng)的Lagrange乘子。這是一個(gè)不等式約束條件下的二次函數(shù)尋優(yōu)問(wèn)題，存在唯一解222求解原始問(wèn)題為求解原始問(wèn)題，根據(jù)最優(yōu)化理論，我們轉(zhuǎn)化為223線(xiàn)性可分問(wèn)題計(jì)算，選擇的一個(gè)正分量,并據(jù)此計(jì)算事實(shí)上，的每一個(gè)分量都與一個(gè)訓(xùn)練點(diǎn)相對(duì)應(yīng)。而分劃超平面僅僅依賴(lài)于不為零的訓(xùn)練點(diǎn)，而與對(duì)應(yīng)于為零的那些訓(xùn)練點(diǎn)無(wú)關(guān)。稱(chēng)不為零的這些訓(xùn)練點(diǎn)的輸入為支持向量(SV)構(gòu)造分劃超平面,決策函數(shù)根據(jù)最優(yōu)解223線(xiàn)性可分問(wèn)題計(jì)算224近似線(xiàn)性可分問(wèn)題不要求所有訓(xùn)練點(diǎn)都滿(mǎn)足約束條件，為此對(duì)第個(gè)訓(xùn)練點(diǎn)引入松弛變量(SlackVariable),把約束條件放松到。體現(xiàn)了訓(xùn)練集被錯(cuò)分的情況，可采用作為一種度量來(lái)描述錯(cuò)劃程度。兩個(gè)目標(biāo)：1.間隔盡可能大2.錯(cuò)劃程度盡可能小顯然，當(dāng)充分大時(shí)，樣本點(diǎn)總可以滿(mǎn)足以上約束條件。然而事實(shí)上應(yīng)避免太大，所以需在目標(biāo)函數(shù)對(duì)進(jìn)行懲罰（即“軟化”約束條件）Chap8SVMZhongzhiShi224近似線(xiàn)性可分問(wèn)題不要求所有訓(xùn)練點(diǎn)都滿(mǎn)足約束條件225因此，引入一個(gè)懲罰參數(shù)，新的目標(biāo)函數(shù)變?yōu)?體現(xiàn)了經(jīng)驗(yàn)風(fēng)險(xiǎn)，而則體現(xiàn)了表達(dá)能力。所以懲罰參數(shù)實(shí)質(zhì)上是對(duì)經(jīng)驗(yàn)風(fēng)險(xiǎn)和表達(dá)能力匹配一個(gè)裁決。當(dāng)時(shí)，近似線(xiàn)性可分SVC的原始問(wèn)題退化為線(xiàn)性可分SVC的原始問(wèn)題。近似線(xiàn)性可分問(wèn)題Chap8SVMZhongzhiShi225因此，引入一個(gè)懲罰參數(shù)，新的目標(biāo)函數(shù)226(廣義)線(xiàn)性支持向量分類(lèi)機(jī)算法設(shè)已知訓(xùn)練集，其中2.選擇適當(dāng)?shù)膽土P參數(shù)，構(gòu)造并求解最優(yōu)化問(wèn)題3.計(jì)算，選擇的一個(gè)分量，并據(jù)此計(jì)算出4.構(gòu)造分劃超平面,決策函數(shù)求得226(廣義)線(xiàn)性支持向量分類(lèi)機(jī)算法設(shè)已知訓(xùn)練集227非線(xiàn)性分類(lèi)例子:227非線(xiàn)性分類(lèi)例子:228Non-linearClassificationWhatcanwedoiftheboundaryisnonlinear?Idea:transformthedatavectorstoaspacewheretheseparatorislinearChap8SVMZhongzhiShi228Non-linearClassificationWh229Non-linearClassificationThetransformationmanytimesismadetoaninfinitedimensionalspace,usuallyafunctionspace.Example:xcos(uTx)Chap8SVMZhongzhiShi229Non-linearClassificationTh230Non-linearSVMsTransformx

(x)Thelinearalgorithmdependsonlyonxxi,hencetransformedalgorithmdependsonlyon(x)(xi)UsekernelfunctionK(xi,xj)suchthatK(xi,xj)=(x)(xi)

230Non-linearSVMsTransformx231設(shè)訓(xùn)練集，其中假定可以用平面上的二次曲線(xiàn)來(lái)分劃：現(xiàn)考慮把2維空間映射到6維空間的變換上式可將2維空間上二次曲線(xiàn)映射為6維空間上的一個(gè)超平面：非線(xiàn)性分類(lèi)231設(shè)訓(xùn)練集232可見(jiàn)，只要利用變換，把所在的2維空間的兩類(lèi)輸入點(diǎn)映射到所在的6維空間，然后在這個(gè)6維空間中，使用線(xiàn)性學(xué)習(xí)機(jī)求出分劃超平面：最后得出原空間中的二次曲線(xiàn)：怎樣求6維空間中的分劃超平面？(線(xiàn)性支持向量分類(lèi)機(jī))非線(xiàn)性分類(lèi)232可見(jiàn)，只要利用變換，把所在的2維空間的兩類(lèi)輸233需要求解的最優(yōu)化問(wèn)題其中非線(xiàn)性分類(lèi)233需要求解的最優(yōu)化問(wèn)題其中非線(xiàn)性分類(lèi)234在求得最優(yōu)化問(wèn)題的解后，得到分劃超平面其中最后得到?jīng)Q策函數(shù)或線(xiàn)性分劃－>非線(xiàn)性分劃

代價(jià)：2維空間內(nèi)積－>6維空間內(nèi)積非線(xiàn)性分類(lèi)234在求得最優(yōu)化問(wèn)題的解235為此，引進(jìn)函數(shù)有比較(2)和(3)，可以發(fā)現(xiàn)這是一個(gè)重要的等式，提示6維空間中的內(nèi)積可以通過(guò)計(jì)算中2維空間中的內(nèi)積得到。非線(xiàn)性分類(lèi)235為此，引進(jìn)函數(shù)有比較(2)和(3)，可以發(fā)現(xiàn)這是一個(gè)重236實(shí)現(xiàn)非線(xiàn)性分類(lèi)的思想給定訓(xùn)練集后，決策函數(shù)僅依賴(lài)于而不需要再考慮非線(xiàn)性變換如果想用其它的非線(xiàn)性分劃辦法，則可以考慮選擇其它形式的函數(shù)，一旦選定了函數(shù)，就可以求解最優(yōu)化問(wèn)題得，而決策函數(shù)236實(shí)現(xiàn)非線(xiàn)性分類(lèi)的思想給定訓(xùn)練集后，決策函數(shù)僅依賴(lài)于得237決策函數(shù)其中實(shí)現(xiàn)非線(xiàn)性分類(lèi)的思想237決策函數(shù)其中實(shí)現(xiàn)非線(xiàn)性分類(lèi)的思想238多項(xiàng)式內(nèi)核徑向基函數(shù)內(nèi)核RBFSigmoind內(nèi)核目前研究最多的核函數(shù)主要有三類(lèi)：得到q階多項(xiàng)式分類(lèi)器每個(gè)基函數(shù)中心對(duì)應(yīng)一個(gè)支持向量，它們及輸出權(quán)值由算法自動(dòng)確定包含一個(gè)隱層的多層感知器，隱層節(jié)點(diǎn)數(shù)是由算法自動(dòng)確定核函數(shù)的選擇Chap8SVMZhongzhiShi238多項(xiàng)式內(nèi)核目前研究最多的核函數(shù)主要有三類(lèi)：得到q階多SVM算法實(shí)現(xiàn)軟件LIBSVM：臺(tái)灣大學(xué)林智仁教授等開(kāi)發(fā)，有各種版本，應(yīng)用很廣泛LS-SVMLAB：Matlab界面，分類(lèi)、回歸都可OSU_SVM：用于分類(lèi)，可以實(shí)現(xiàn)多分類(lèi)SVMtoolbox:Matlab界面，代碼簡(jiǎn)單，適合初學(xué)者了解原理，但算法效率較低39SVM算法實(shí)現(xiàn)軟件LIBSVM：臺(tái)灣大學(xué)林智仁教授等開(kāi)發(fā)，有有關(guān)SVM的網(wǎng)站

.tw/~cjlin/libsvm

www.esat.kuleuven.ac.be/sista/lssvmlab/Top/Computers/Artificial_Intelligence/Support_Vector_Machines40有關(guān)SVM的網(wǎng)站www.kernel-machines.orSVM預(yù)測(cè)模型的建立核函數(shù)的選擇在實(shí)驗(yàn)中選取RBF函數(shù)作為核函數(shù)的首選，原因：1.RBF函數(shù)可以將樣本非線(xiàn)性地規(guī)劃到更高維的空間中，從而實(shí)現(xiàn)非線(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ì)趨于不定值或零值且冪值更高；Sigmoid核函數(shù)在取某些參數(shù)值時(shí)則可能無(wú)效。41SVM預(yù)測(cè)模型的建立核函數(shù)的選擇41SVM預(yù)測(cè)模型的建立（續(xù)）C和r和選?。ㄒ苑诸?lèi)為例）

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

性能比較SVMRBF神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)最大誤差2.992%3.259%平均相對(duì)誤差1.872%1.976%43用SVM實(shí)現(xiàn)煤炭需求量的預(yù)測(cè)性能比較SVMRBF神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)用SVM實(shí)現(xiàn)煤炭需求量的預(yù)測(cè)用訓(xùn)練好的SVM模型來(lái)預(yù)測(cè)將來(lái)2003-2006年的煤炭需求量，其需求趨勢(shì)如下圖：2003-2006年的預(yù)測(cè)值44用SVM實(shí)現(xiàn)煤炭需求量的預(yù)測(cè)用訓(xùn)練好的SVM模型來(lái)預(yù)測(cè)將來(lái)2有待解決的問(wèn)題1.如何合選擇SVM的參數(shù)：怎樣合理選擇支持向量的核參數(shù)，目前尚無(wú)定論。格子搜索法比較常見(jiàn)，有的學(xué)者已提出用遺傳算法、粒子群算法等優(yōu)化參數(shù)2.如何實(shí)現(xiàn)時(shí)間序列的動(dòng)態(tài)預(yù)測(cè)：動(dòng)態(tài)預(yù)測(cè)要求SVM的參數(shù)能適應(yīng)序列的動(dòng)態(tài)變化，即建立基于SVM自適應(yīng)預(yù)測(cè)控制系統(tǒng)45有待解決的問(wèn)題1.如何合選擇SVM的參數(shù)：怎樣合理選擇支持向246SVMapplicationsPatternrecognitionFeatures:wordscountsDNAarrayexpressiondataanalysisFeatures:expr.levelsindiff.conditionsProteinclassificationFeatures:AAcomposition246SVMapplicationsPatternrec247HandwrittenDigitsRecognition247HandwrittenDigitsRecognit248ApplyingSVMstoFaceDetectionTheSVMface-detectionsystem1.Rescaletheinputimageseveraltimes2.Cut19x19windowpatternsoutofthescaledimage3.Preprocessthewindowusingmasking,lightcorrectionandhistogramequalization4.ClassifythepatternusingtheSVM5.Iftheclasscorrespondstoaface,drawarectanglearoundthefaceintheoutputimage.248ApplyingSVMstoFaceDetec249ApplyingSVMstoFaceDetectionExperimentalresultsonstaticimagesSetA:313high-quality,samenumberoffacesSetB:23mixedquality,totalof155faces249ApplyingSVMstoFaceDetec250ApplyingSVMstoFaceDetectionExtensiontoareal-timesystemAnexampleoftheskindetectionmoduleimplementedusingSVMsFaceDetectiononthePC-basedColorRealTimeSystem250ApplyingSVMstoFaceDetec251ReferencesVladimirVapnik.TheNatureofStatisticalLearningTheory,Springer,1995AndrewW.Moore.cmsc726:SVMs./~awm/tutorialsC.Burges.Atutorialonsupportvectormachinesforpatternrecognition.DataMiningandKnowledgeDiscovery,2(2):955-974,1998./burges98tutorial.htmlVladimirVapnik.StatisticalLearningTheory.Wiley-Interscience;1998ThorstenJoachims(joachims_01a):AStatisticalLearningModelofTextClassificationforSupportVectorMachinesBenRubinstein.StatisticalLearningTheory.

Dept.ComputerScience&SoftwareEngineering,UniversityofMelbourne;andDivisionofGenetics&Bioinformatics,Walter&ElizaHallInstitute251References支持向量機(jī)

SupportVectorMachines支持向量機(jī)

SupportVectorMachin內(nèi)容提要統(tǒng)計(jì)學(xué)習(xí)方法概述統(tǒng)計(jì)學(xué)習(xí)問(wèn)題學(xué)習(xí)過(guò)程的泛化能力支持向量機(jī)SVM尋優(yōu)算法應(yīng)用內(nèi)容提要統(tǒng)計(jì)學(xué)習(xí)方法概述支持向量機(jī)SVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法，它是由Boser,Guyon,Vapnik在COLT-92上首次提出，從此迅速發(fā)展起來(lái)VapnikVN.1995.TheNatureofStatisticalLearningTheory.Springer-Verlag,NewYorkVapnikVN.1998.StatisticalLearningTheory.Wiley-IntersciencePublication,JohnWiley&Sons,Inc目前已經(jīng)在許多智能信息獲取與處理領(lǐng)域都取得了成功的應(yīng)用。

支持向量機(jī)SVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法，它是由支持向量機(jī)SVMSVMsarelearningsystemsthatuseahyperplaneoflinearfunctionsinahighdimensionalfeaturespace—Kernelfunctiontrainedwithalearningalgorithmfromoptimizationtheory—LagrangeImplementsalearningbiasderivedfromstatisticallearningtheory—GeneralisationSVMisaclassifierderivedfromstatisticallearningtheorybyVapnikandChervonenkis支持向量機(jī)SVMSVMsarelearningsys256

線(xiàn)性分類(lèi)器ayestf

xf(x,w,b)=sign(w.x

-b)denotes+1denotes-1Howwouldyouclassifythisdata?25線(xiàn)性分類(lèi)器ayestfxf(x,w,257線(xiàn)性分類(lèi)器f

xayestdenotes+1denotes-1f(x,w,b)=sign(w.x

-b)Howwouldyouclassifythisdata?26線(xiàn)性分類(lèi)器fxayestdenotes258線(xiàn)性分類(lèi)器f

xayestdenotes+1denotes-1f(x,w,b)=sign(w.x

-b)Howwouldyouclassifythisdata?27線(xiàn)性分類(lèi)器fxayestdenotes259線(xiàn)性分類(lèi)器f

xayestdenotes+1denotes-1f(x,w,b)=sign(w.x

-b)Howwouldyouclassifythisdata?28線(xiàn)性分類(lèi)器fxayestdenotes260線(xiàn)性分類(lèi)器f

xayestdenotes+1denotes-1f(x,w,b)=sign(w.x

-b)Howwouldyouclassifythisdata?哪一個(gè)分界面是最優(yōu)的？？29線(xiàn)性分類(lèi)器fxayestdenotes261分類(lèi)超平面Trainingset:(xi,yi),i=1,2,…N;yi{+1,-1}Hyperplane:wx+b=0Thisisfullydeterminedby(w,b)w1x+b1=0w2x+b2=0w3x+b3=0210分類(lèi)超平面Trainingset:(xi,yi)262最大間隔一個(gè)超平面，如果它能將訓(xùn)練樣本沒(méi)有錯(cuò)誤地分開(kāi)，并且兩類(lèi)訓(xùn)練樣本中離超平面最近的樣本與超平面之間的距離是最大的，則把這個(gè)超平面稱(chēng)作最優(yōu)分類(lèi)超平面（optimalseparatinghyperplane），兩類(lèi)樣本中離分類(lèi)面最近的樣本到分類(lèi)面的距離稱(chēng)為分類(lèi)間隔，最優(yōu)超平面也可以稱(chēng)作最大間隔超平面。211最大間隔一個(gè)超平面，如果它能將訓(xùn)練樣本沒(méi)有錯(cuò)誤地分開(kāi)，263最大間隔原則Note1:decisionfunctions(w,b)and

(cw,cb)arethesameNote2:butmarginsasmeasuredbytheoutputsofthefunctionxwx+barenotthesameifwetake(cw,cb).Definition:geometricmargin:themargingivenbythecanonicaldecisionfunction,whichiswhenc=1/||w||Strategy: 1)weneedtomaximisethegeometricmargin!(cfresultfromlearningtheory) 2)subjecttotheconstraintthattrainingexamplesareclassifiedcorrectlywwx+b=0wx+b>0wx+b<0212最大間隔原則Note1:decisionfunct264支持向量Thetrainingpointsthatarenearesttotheseparatingfunctionarecalledsupportvectors.Whatistheoutputofourdecisionfunctionforthesepoints?213支持向量Thetrainingpointstha265分類(lèi)問(wèn)題的數(shù)學(xué)表示已知：訓(xùn)練集包含個(gè)樣本點(diǎn)：

說(shuō)明：是輸入指標(biāo)向量，或稱(chēng)輸入，或稱(chēng)模式，其分量稱(chēng)為特征，或?qū)傩?，或輸入指?biāo)；是輸出指標(biāo)，或輸出.問(wèn)題：對(duì)一個(gè)新的模式，推斷它所對(duì)應(yīng)的輸出是1還是-1.實(shí)質(zhì)：找到一個(gè)把上的點(diǎn)分成兩部分的規(guī)則.

2維空間上的分類(lèi)問(wèn)題)n維空間上的分類(lèi)問(wèn)題.214分類(lèi)問(wèn)題的數(shù)學(xué)表示2維空間上的分類(lèi)問(wèn)題)266根據(jù)給定的訓(xùn)練集其中，，尋找上的一個(gè)實(shí)值函數(shù)，用決策函數(shù)

判斷任一模式對(duì)應(yīng)的值.sgn()為符號(hào)函數(shù)，取自變量的符號(hào)。

可見(jiàn)，分類(lèi)學(xué)習(xí)機(jī)——構(gòu)造決策函數(shù)的方法(算法)，兩類(lèi)分類(lèi)問(wèn)題多類(lèi)分類(lèi)問(wèn)題線(xiàn)性分類(lèi)學(xué)習(xí)機(jī)非線(xiàn)性分類(lèi)學(xué)習(xí)機(jī)

分類(lèi)學(xué)習(xí)方法215分類(lèi)學(xué)習(xí)方法267SVM分類(lèi)問(wèn)題大致有三種：線(xiàn)性可分問(wèn)題、近似線(xiàn)性可分問(wèn)題、線(xiàn)性不可分問(wèn)題。分類(lèi)學(xué)習(xí)方法Chap8SVMZhongzhiShi216SVM分類(lèi)問(wèn)題大致有三種：線(xiàn)性可分問(wèn)題、近似線(xiàn)性可分問(wèn)268考慮上的線(xiàn)性可分的分類(lèi)問(wèn)題.這里有許多直線(xiàn)能將兩類(lèi)點(diǎn)正確分開(kāi).如何選取和？簡(jiǎn)單問(wèn)題：設(shè)法方向已選定，如何選??？解答：選定平行直線(xiàn)極端直線(xiàn)和取和的中間線(xiàn)為分劃直線(xiàn)如何選??？對(duì)應(yīng)一個(gè)，有極端直線(xiàn)，稱(chēng)和之間的距離為“間隔”.顯然應(yīng)選使“間隔”最大的。

最大間隔法的直觀導(dǎo)出217考慮上的線(xiàn)性可分的分類(lèi)問(wèn)題.最大間隔法的直觀269數(shù)學(xué)語(yǔ)言描述調(diào)整，使得令，則兩式可以等價(jià)寫(xiě)為與此相應(yīng)的分劃直線(xiàn)表達(dá)式:給定適當(dāng)?shù)姆ǚ较蚝?，這兩條極端直線(xiàn)可表示為Chap8SVMZhongzhiShi218數(shù)學(xué)語(yǔ)言描述調(diào)整，使得令，則270如何計(jì)算分劃間隔？考慮2維空間中極端直線(xiàn)之間的間隔情況求出兩條極端直線(xiàn)的距離：Chap8SVMZhongzhiShi219如何計(jì)算分劃間隔？求出兩條極端直線(xiàn)的距離：Chap8271Margin=

H1平面：

H2平面：

…..(2)

…..(1)

Chap8SVMZhongzhiShi220Margin=H1平面：H2平面：…..(2)272分劃直線(xiàn)表達(dá)式為“間隔”為極大化“間隔”的思想導(dǎo)致求解下列對(duì)變量和的最優(yōu)化問(wèn)題說(shuō)明：只要我們求得該問(wèn)題的最優(yōu)解，從而構(gòu)造分劃超平面，求出決策函數(shù)。上述方法對(duì)一般上的分類(lèi)問(wèn)題也適用.原始問(wèn)題Chap8SVMZhongzhiShi221分劃直線(xiàn)表達(dá)式為273求解原始問(wèn)題為求解原始問(wèn)題，根據(jù)最優(yōu)化理論，我們轉(zhuǎn)化為對(duì)偶問(wèn)題來(lái)求解對(duì)偶問(wèn)題為原始問(wèn)題中與每個(gè)約束條件對(duì)應(yīng)的Lagrange乘子。這是一個(gè)不等式約束條件下的二次函數(shù)尋優(yōu)問(wèn)題，存在唯一解222求解原始問(wèn)題為求解原始問(wèn)題，根據(jù)最優(yōu)化理論，我們轉(zhuǎn)化為274線(xiàn)性可分問(wèn)題計(jì)算，選擇的一個(gè)正分量,并據(jù)此計(jì)算事實(shí)上，的每一個(gè)分量都與一個(gè)訓(xùn)練點(diǎn)相對(duì)應(yīng)。而分劃超平面僅僅依賴(lài)于不為零的訓(xùn)練點(diǎn)，而與對(duì)應(yīng)于為零的那些訓(xùn)練點(diǎn)無(wú)關(guān)。稱(chēng)不為零的這些訓(xùn)練點(diǎn)的輸入為支持向量(SV)構(gòu)造分劃超平面,決策函數(shù)根據(jù)最優(yōu)解223線(xiàn)性可分問(wèn)題計(jì)算275近似線(xiàn)性可分問(wèn)題不要求所有訓(xùn)練點(diǎn)都滿(mǎn)足約束條件，為此對(duì)第個(gè)訓(xùn)練點(diǎn)引入松弛變量(SlackVariable),把約束條件放松到。體現(xiàn)了訓(xùn)練集被錯(cuò)分的情況，可采用作為一種度量來(lái)描述錯(cuò)劃程度。兩個(gè)目標(biāo)：1.間隔盡可能大2.錯(cuò)劃程度盡可能小顯然，當(dāng)充分大時(shí)，樣本點(diǎn)總可以滿(mǎn)足以上約束條件。然而事實(shí)上應(yīng)避免太大，所以需在目標(biāo)函數(shù)對(duì)進(jìn)行懲罰（即“軟化”約束條件）Chap8SVMZhongzhiShi224近似線(xiàn)性可分問(wèn)題不要求所有訓(xùn)練點(diǎn)都滿(mǎn)足約束條件276因此，引入一個(gè)懲罰參數(shù)，新的目標(biāo)函數(shù)變?yōu)?體現(xiàn)了經(jīng)驗(yàn)風(fēng)險(xiǎn)，而則體現(xiàn)了表達(dá)能力。所以懲罰參數(shù)實(shí)質(zhì)上是對(duì)經(jīng)驗(yàn)風(fēng)險(xiǎn)和表達(dá)能力匹配一個(gè)裁決。當(dāng)時(shí)，近似線(xiàn)性可分SVC的原始問(wèn)題退化為線(xiàn)性可分SVC的原始問(wèn)題。近似線(xiàn)性可分問(wèn)題Chap8SVMZhongzhiShi225因此，引入一個(gè)懲罰參數(shù)，新的目標(biāo)函數(shù)277(廣義)線(xiàn)性支持向量分類(lèi)機(jī)算法設(shè)已知訓(xùn)練集，其中2.選擇適當(dāng)?shù)膽土P參數(shù)，構(gòu)造并求解最優(yōu)化問(wèn)題3.計(jì)算，選擇的一個(gè)分量，并據(jù)此計(jì)算出4.構(gòu)造分劃超平面,決策函數(shù)求得226(廣義)線(xiàn)性支持向量分類(lèi)機(jī)算法設(shè)已知訓(xùn)練集278非線(xiàn)性分類(lèi)例子:227非線(xiàn)性分類(lèi)例子:279Non-linearClassificationWhatcanwedoiftheboundaryisnonlinear?Idea:transformthedatavectorstoaspacewheretheseparatorislinearChap8SVMZhongzhiShi228Non-linearClassificationWh280Non-linearClassificationThetransformationmanytimesismadetoaninfinitedimensionalspace,usuallyafunctionspace.Example:xcos(uTx)Chap8SVMZhongzhiShi229Non-linearClassificationTh281Non-linearSVMsTransformx

(x)Thelinearalgorithmdependsonlyonxxi,hencetransformedalgorithmdependsonlyon(x)(xi)UsekernelfunctionK(xi,xj)suchthatK(xi,xj)=(x)(xi)

230Non-linearSVMsTransformx282設(shè)訓(xùn)練集，其中假定可以用平面上的二次曲線(xiàn)來(lái)分劃：現(xiàn)考慮把2維空間映射到6維空間的變換上式可將2維空間上二次曲線(xiàn)映射為6維空間上的一個(gè)超平面：非線(xiàn)性分類(lèi)231設(shè)訓(xùn)練集283可見(jiàn)，只要利用變換，把所在的2維空間的兩類(lèi)輸入點(diǎn)映射到所在的6維空間，然后在這個(gè)6維空間中，使用線(xiàn)性學(xué)習(xí)機(jī)求出分劃超平面：最后得出原空間中的二次曲線(xiàn)：怎樣求6維空間中的分劃超平面？(線(xiàn)性支持向量分類(lèi)機(jī))非線(xiàn)性分類(lèi)232可見(jiàn)，只要利用變換，把所在的2維空間的兩類(lèi)輸284需要求解的最優(yōu)化問(wèn)題其中非線(xiàn)性分類(lèi)233需要求解的最優(yōu)化問(wèn)題其中非線(xiàn)性分類(lèi)285在求得最優(yōu)化問(wèn)題的解后，得到分劃超平面其中最后得到?jīng)Q策函數(shù)或線(xiàn)性分劃－>非線(xiàn)性分劃

代價(jià)：2維空間內(nèi)積－>6維空間內(nèi)積非線(xiàn)性分類(lèi)234在求得最優(yōu)化問(wèn)題的解286為此，引進(jìn)函數(shù)有比較(2)和(3)，可以發(fā)現(xiàn)這是一個(gè)重要的等式，提示6維空間中的內(nèi)積可以通過(guò)計(jì)算中2維空間中的內(nèi)積得到。非線(xiàn)性分類(lèi)235為此，引進(jìn)函數(shù)有比較(2)和(3)，可以發(fā)現(xiàn)這是一個(gè)重287實(shí)現(xiàn)非線(xiàn)性分類(lèi)的思想給定訓(xùn)練集后，決策函數(shù)僅依賴(lài)于而不需要再考慮非線(xiàn)性變換如果想用其它的非線(xiàn)性分劃辦法，則可以考慮選擇其它形式的函數(shù)，一旦選定了函數(shù)，就可以求解最優(yōu)化問(wèn)題得，而決策函數(shù)236實(shí)現(xiàn)非線(xiàn)性分類(lèi)的思想給定訓(xùn)練集后，決策函數(shù)僅依賴(lài)于得288決策函數(shù)其中實(shí)現(xiàn)非線(xiàn)性分類(lèi)的思想237決策函數(shù)其中實(shí)現(xiàn)非線(xiàn)性分類(lèi)的思想289多項(xiàng)式內(nèi)核徑向基函數(shù)內(nèi)核RBFSigmoind內(nèi)核目前研究最多的核函數(shù)主要有三類(lèi)：得到q階多項(xiàng)式分類(lèi)器每個(gè)基函數(shù)中心對(duì)應(yīng)一個(gè)支持向量，它們及輸出權(quán)值由算法自動(dòng)確定包含一個(gè)隱層的多層感知器，隱層節(jié)點(diǎn)數(shù)是由算法自動(dòng)確定核函數(shù)的選擇Chap8SVMZhongzhiShi238多項(xiàng)式內(nèi)核目前研究最多的核函數(shù)主要有三類(lèi)：得到q階多SVM算法實(shí)現(xiàn)軟件LIBSVM：臺(tái)灣大學(xué)林智仁教授等開(kāi)發(fā)，有各種版本，應(yīng)用很廣泛LS-SVMLAB：Matlab界面，分類(lèi)、回歸都可OSU_SVM：用于分類(lèi)，可以實(shí)現(xiàn)多分類(lèi)SVMtoolbox:Matlab界面，代碼簡(jiǎn)單，適合初學(xué)者了解原理，但算法效率較低90SVM算法實(shí)現(xiàn)軟件LIBSVM：臺(tái)灣大學(xué)林智仁教授等開(kāi)發(fā)，有有關(guān)SVM的網(wǎng)站

.tw/~cjlin/libsvm

www.esat.kuleuven.ac.be/sista/lssvmlab/Top/Computers/Artificial_Intelligence/Support_Vector_Machines91有關(guān)SVM的網(wǎng)站www.kernel-machines.orSVM預(yù)測(cè)模型的建立核函數(shù)的選擇在實(shí)驗(yàn)中選取RBF函數(shù)作為核函數(shù)的首選，原因：1.RBF函數(shù)可以將樣本非線(xiàn)性地規(guī)劃到更高維的空間中，從而實(shí)現(xiàn)非線(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ì)趨于不定值或零值且冪值更高；Sigmoid核函數(shù)在取某些參數(shù)值時(shí)則可能無(wú)效。92SVM預(yù)測(cè)模型的建立核函數(shù)的選擇41SVM預(yù)測(cè)模型的建立（續(xù)）C和r和選?。ㄒ苑诸?lèi)為例）

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

性能比較SVMRBF神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)