人工智能之支持向量機

支持向量機

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

支持向量機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?哪一個分界面是最優(yōu)的？？分類超平面Trainingset:xiyi;i=1;2;…N;yi{+1;-1}Hyperplane:wx+b=0Thisisfullydeterminedbyw;bw1x+b1=0w2x+b2=0w3x+b3=0最大間隔一個超平面;如果它能將訓練樣本沒有錯誤地分開;并且兩類訓練樣本中離超平面最近的樣本與超平面之間的距離是最大的;則把這個超平面稱作最優(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ù)學表示已知：訓練集包含個樣本點：

說明：是輸入指標向量;或稱輸入;或稱模式;其分量稱為特征;或?qū)傩?或輸入指標；是輸出指標;或輸出.問題：對一個新的模式;推斷它所對應的輸出是1還是-1.實質(zhì)：找到一個把上的點分成兩部分的規(guī)則.

2維空間上的分類問題n維空間上的分類問題.根據(jù)給定的訓練集其中;;尋找上的一個實值函數(shù);用決策函數(shù)

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

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

分類學習方法SVM分類問題大致有三種：線性可分問題、近似線性可分問題、線性不可分問題&分類學習方法2024/1/3016考慮上的線性可分的分類問題.這里有許多直線能將兩類點正確分開.如何選取和？簡單問題：設法方向已選定;如何選??？解答：選定平行直線極端直線和取和的中間線為分劃直線如何選?。繉粋€;有極端直線;稱和之間的距離為“間隔”.顯然應選使“間隔”最大的&

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

H1平面：

H2平面：

…..2

…..1

2024/1/3020分劃直線表達式為“間隔”為極大化“間隔”的思想導致求解下列對變量和的最優(yōu)化問題說明：只要我們求得該問題的最優(yōu)解;從而構(gòu)造分劃超平面;求出決策函數(shù)&上述方法對一般上的分類問題也適用.原始問題2024/1/3021求解原始問題為求解原始問題;根據(jù)最優(yōu)化理論;我們轉(zhuǎn)化為對偶問題來求解對偶問題為原始問題中與每個約束條件對應的Lagrange乘子&這是一個不等式約束條件下的二次函數(shù)尋優(yōu)問題;存在唯一解線性可分問題計算;選擇的一個正分量

并據(jù)此計算事實上;的每一個分量都與一個訓練點相對應&而分劃超平面僅僅依賴于不為零的訓練點;而與對應于為零的那些訓練點無關(guān)&稱不為零的這些訓練點的輸入為支持向量SV構(gòu)造分劃超平面

決策函數(shù)根據(jù)最優(yōu)解近似線性可分問題不要求所有訓練點都滿足約束條件;為此對第個訓練點引入松弛變量SlackVariable把約束條件放松到&體現(xiàn)了訓練集被錯分的情況;可采用作為一種度量來描述錯劃程度&兩個目標：1.間隔盡可能大2.錯劃程度盡可能小顯然;當充分大時;樣本點總可以滿足以上約束條件&然而事實上應避免太大;所以需在目標函數(shù)對進行懲罰即“軟化”約束條件2024/1/3024因此;引入一個懲罰參數(shù);新的目標函數(shù)變?yōu)?體現(xiàn)了經(jīng)驗風險;而則體現(xiàn)了表達能力&所以懲罰參數(shù)實質(zhì)上是對經(jīng)驗風險和表達能力匹配一個裁決&當時;近似線性可分SVC的原始問題退化為線性可分SVC的原始問題&近似線性可分問題2024/1/3025廣義線性支持向量分類機算法設已知訓練集;其中2.選擇適當?shù)膽土P參數(shù);構(gòu)造并求解最優(yōu)化問題3.計算;選擇的一個分量;并據(jù)此計算出4.構(gòu)造分劃超平面

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

xThelinearalgorithmdependsonlyonxxihencetransformedalgorithmdependsonlyonx

xiUsekernelfunctionKxi;xjsuchthatKxi;xj=

x

xi

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

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

.tw/~cjlin/libsvm

www.esat.kuleuven.ac.be/sista/lssvmlab/Top/Computers/Artificial_Intelligence/Support_Vector_MachinesSVM預測模型的建立核函數(shù)的選擇在實驗中選取RBF函數(shù)作為核函數(shù)的首選;原因：1.RBF函數(shù)可以將樣本非線性地規(guī)劃到更高維的空間中;從而實現(xiàn)非線形影射&Sigmoid核函數(shù)取某些特定參數(shù)時性能和RBF相同&2.RBF函數(shù)的參數(shù)只有一個&相比之下多項式核函數(shù)參數(shù)比RBF核函數(shù)多;因此其模型選擇更為復雜&3.RBF函數(shù)的數(shù)值限制條件少&RBF函數(shù)使數(shù)值被限制在0和1之間;而多項式核函數(shù)的值可能會趨于不定值或零值且冪值更高；Sigmoid核函數(shù)在取某些參數(shù)值時則可能無效&SVM預測模型的建立續(xù)C和r和選取以分類為例

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

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

性能比較SVMRBF神經(jīng)網(wǎng)絡預測最大誤差2.992%3.259%平均相對誤差1.872%1.976%43用SVM實現(xiàn)煤炭需求量的預測用訓練好的SVM模型來預測將來2003-2006年的煤炭需求量;其需求趨勢如下圖：2003-2006年的預測值有待解決的問題1.如何合選擇SVM的參數(shù)：怎樣合理選擇支持向量的核參數(shù);目前尚無定論&格子搜索法比較常見;有的學者已提出用遺傳算法、粒子群算法等優(yōu)化參數(shù)2.如何實現(xiàn)時間序列的動態(tài)預測：動態(tài)預測要求SVM的參數(shù)能適應序列的動態(tài)變化;即建立基于SVM自適應預測控制系統(tǒng)SVMapplicationsPatternrecognitionFeatures:wordscountsDNAarrayexpressiondataanalysisFeatures:expr.levelsindiff.conditionsProteinclassificationFeatures:AAcompositionHandwrittenDigitsRecognitionApplyingSVMstoFaceDetectionTheSVMface-detectionsystem1.Rescaletheinputimageseveraltimes2.Cut19x19windowpatternsoutofthescaledimage3.Preprocessthewindowusingmaskinglightcorrectionandhistogramequalization4.ClassifythepatternusingtheSVM5.Iftheclasscorrespondstoafacedrawarectanglearoundthefaceintheoutputimage.ApplyingSVMstoFaceDetectionExperimentalresultsonstaticimagesSetA:313high-qualitysamenumbero