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

支持向量機(jī)

SupportVectorMachines內(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í)方法;它是由BoserGuyon;Vapnik在COLT-92上首次提出;從此迅速發(fā)展起來VapnikVN.1995.TheNatureofStatisticalLearningTheory.Springer-Verlag;NewYorkVapnikVN.1998.StatisticalLearningTheory.Wiley-IntersciencePublication;JohnWiley&Sons;Inc目前已經(jīng)在許多智能信息獲取與處理領(lǐng)域都取得了成功的應(yīng)用&

支持向量機(jī)SVMSVMsarelearningsystemsthatuseahyperplaneoflinearfunctionsinahighdimensionalfeaturespace—Kernelfunctiontrainedwithalearningalgorithmfromoptimizationtheory—LagrangeImplementsalearningbiasderivedfromstatisticallearningtheory—GeneralisationSVMisaclassifierderivedfromstatisticallearningtheorybyVapnikandChervonenkis

線性分類器ayestf

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

-b)denotes+1denotes-1Howwouldyouclassifythisdata?線性分類器f

xayestdenotes+1denotes-1fx

w;b=signw.x

-bHowwouldyouclassifythisdata?線性分類器f

xayestdenotes+1denotes-1fx

w;b=signw.x

-bHowwouldyouclassifythisdata?線性分類器f

xayestdenotes+1denotes-1fx

w;b=signw.x

-bHowwouldyouclassifythisdata?線性分類器f

xayestdenotes+1denotes-1fx

w;b=signw.x

-bHowwouldyouclassifythisdata?哪一個(gè)分界面是最優(yōu)的？？分類超平面Trainingset:xiyi;i=1;2;…N;yi{+1;-1}Hyperplane:wx+b=0Thisisfullydeterminedbyw;bw1x+b1=0w2x+b2=0w3x+b3=0最大間隔一個(gè)超平面;如果它能將訓(xùn)練樣本沒有錯(cuò)誤地分開;并且兩類訓(xùn)練樣本中離超平面最近的樣本與超平面之間的距離是最大的;則把這個(gè)超平面稱作最優(yōu)分類超平面optimalseparatinghyperplane;兩類樣本中離分類面最近的樣本到分類面的距離稱為分類間隔;最優(yōu)超平面也可以稱作最大間隔超平面&最大間隔原則Note1:decisionfunctionswband

cw;cbarethesameNote2:butmarginsasmeasuredbytheoutputsofthefunctionx

wx+barenotthesameifwetakecw;cb.Definition:geometricmargin:themargingivenbythecanonicaldecisionfunction;whichiswhenc=1/||w||Strategy: 1weneedtomaximisethegeometricmargincfresultfromlearningtheory 2subjecttotheconstraintthattrainingexamplesareclassifiedcorrectlywwx+b=0wx+b>0wx+b<0支持向量Thetrainingpointsthatarenearesttotheseparatingfunctionarecalledsupportvectors.Whatistheoutputofourdecisionfunctionforthesepoints?分類問題的數(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維空間上的分類問題.根據(jù)給定的訓(xùn)練集其中;;尋找上的一個(gè)實(shí)值函數(shù);用決策函數(shù)

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

可見;分類學(xué)習(xí)機(jī)——構(gòu)造決策函數(shù)的方法算法;兩類分類問題多類分類問題線性分類學(xué)習(xí)機(jī)非線性分類學(xué)習(xí)機(jī)

分類學(xué)習(xí)方法SVM分類問題大致有三種：線性可分問題、近似線性可分問題、線性不可分問題&分類學(xué)習(xí)方法2024/1/3016考慮上的線性可分的分類問題.這里有許多直線能將兩類點(diǎn)正確分開.如何選取和？簡單問題：設(shè)法方向已選定;如何選?。拷獯穑哼x定平行直線極端直線和取和的中間線為分劃直線如何選??？對應(yīng)一個(gè);有極端直線;稱和之間的距離為“間隔”.顯然應(yīng)選使“間隔”最大的&

最大間隔法的直觀導(dǎo)出數(shù)學(xué)語言描述調(diào)整;使得令;則兩式可以等價(jià)寫為與此相應(yīng)的分劃直線表達(dá)式:給定適當(dāng)?shù)姆ǚ较蚝?這兩條極端直線可表示為2024/1/3018如何計(jì)算分劃間隔？考慮2維空間中極端直線之間的間隔情況求出兩條極端直線的距離：2024/1/3019Margin=

H1平面：

H2平面：

…..2

…..1

2024/1/3020分劃直線表達(dá)式為“間隔”為極大化“間隔”的思想導(dǎo)致求解下列對變量和的最優(yōu)化問題說明：只要我們求得該問題的最優(yōu)解;從而構(gòu)造分劃超平面;求出決策函數(shù)&上述方法對一般上的分類問題也適用.原始問題2024/1/3021求解原始問題為求解原始問題;根據(jù)最優(yōu)化理論;我們轉(zhuǎn)化為對偶問題來求解對偶問題為原始問題中與每個(gè)約束條件對應(yīng)的Lagrange乘子&這是一個(gè)不等式約束條件下的二次函數(shù)尋優(yōu)問題;存在唯一解線性可分問題計(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)解近似線性可分問題不要求所有訓(xùn)練點(diǎn)都滿足約束條件;為此對第個(gè)訓(xùn)練點(diǎn)引入松弛變量SlackVariable把約束條件放松到&體現(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)行懲罰即“軟化”約束條件2024/1/3024因此;引入一個(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的原始問題&近似線性可分問題2024/1/3025廣義線性支持向量分類機(jī)算法設(shè)已知訓(xùn)練集;其中2.選擇適當(dāng)?shù)膽土P參數(shù);構(gòu)造并求解最優(yōu)化問題3.計(jì)算;選擇的一個(gè)分量;并據(jù)此計(jì)算出4.構(gòu)造分劃超平面

決策函數(shù)求得非線性分類例子:Non-linearClassificationWhatcanwedoiftheboundaryisnonlinear?Idea:transformthedatavectorstoaspacewheretheseparatorislinear2024/1/3028Non-linearClassificationThetransformationmanytimesismadetoaninfinitedimensionalspaceusuallyafunctionspace.Example:xcosuTx2024/1/3029Non-linearSVMsTransformx

xThelinearalgorithmdependsonlyonxxihencetransformedalgorithmdependsonlyonx

xiUsekernelfunctionKxi;xjsuchthatKxi;xj=

x

xi

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

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

.tw/~cjlin/libsvm

www.esat.kuleuven.ac.be/sista/lssvmlab/Top/Computers/Artificial_Intelligence/Support_Vector_MachinesSVM預(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ì)趨于不定值或零值且冪值更高；Sigmoid核函數(shù)在取某些參數(shù)值時(shí)則可能無效&SVM預(yù)測模型的建立續(xù)C和r和選取以分類為例

選定一組Cr的范圍和;然后將它們的準(zhǔn)確率用等高線連接起來繪出類似下圖&用SVM實(shí)現(xiàn)煤炭需求量的預(yù)測任務(wù)：用1980-2002年的我國煤炭需求量來預(yù)測2003-2006年的煤炭需求量將歷年的煤炭消費(fèi)量Xt看作時(shí)間序列;則其預(yù)測模型可以描述為其中為Φ非線形函數(shù);p為嵌入維數(shù);根據(jù)上式

可以得到輸入樣本和輸出樣本;這里用1999-2002年的數(shù)據(jù)作為檢驗(yàn)樣本;分別用SVM和神經(jīng)網(wǎng)絡(luò)預(yù)測;結(jié)果為:

性能比較SVMRBF神經(jīng)網(wǎng)絡(luò)預(yù)測最大誤差2.992%3.259%平均相對誤差1.872%1.976%43用SVM實(shí)現(xiàn)煤炭需求量的預(yù)測用訓(xùn)練好的SVM模型來預(yù)測將來2003-2006年的煤炭需求量;其需求趨勢如下圖：2003-2006年的預(yù)測值有待解決的問題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)SVMapplicationsPatternrecognitionFeatures:wordscountsDNAarrayexpressiondataanalysisFeatures:expr.levelsindiff.conditionsProteinclassificationFeatures:AAcompositionHandwrittenDigitsRecognitionApplyingSVMstoFaceDetectionTheSVMface-detectionsystem1.Rescaletheinputimageseveraltimes2.Cut19x19windowpatternsoutofthescaledimage3.Preprocessthewindowusingmaskinglightcorrectionandhistogramequalization4.ClassifythepatternusingtheSVM5.Iftheclasscorrespondstoafacedrawarectanglearoundthefaceintheoutputimage.ApplyingSVMstoFaceDetectionExperimentalresultsonstaticimagesSetA:313high-qualitysamenumbero