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

支持向量機(jī)

SupportVectorMachines支持向量機(jī)

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

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

線性分類器ayestf

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

-b)denotes+1denotes-1Howwouldyouclassifythisdata?25線性分類器ayestfxf(x,w,26線性分類器f

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

-b)Howwouldyouclassifythisdata?26線性分類器fxayestdenotes27線性分類器f

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

-b)Howwouldyouclassifythisdata?27線性分類器fxayestdenotes28線性分類器f

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

-b)Howwouldyouclassifythisdata?28線性分類器fxayestdenotes29線性分類器f

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

-b)Howwouldyouclassifythisdata?哪一個分界面是最優(yōu)的？？29線性分類器fxayestdenotes210分類超平面Trainingset:(xi,yi),i=1,2,…N;yi{+1,-1}Hyperplane:wx+b=0Thisisfullydeterminedby(w,b)w1x+b1=0w2x+b2=0w3x+b3=0210分類超平面Trainingset:(xi,yi)211最大間隔一個超平面，如果它能將訓(xùn)練樣本沒有錯誤地分開，并且兩類訓(xùn)練樣本中離超平面最近的樣本與超平面之間的距離是最大的，則把這個超平面稱作最優(yōu)分類超平面（optimalseparatinghyperplane），兩類樣本中離分類面最近的樣本到分類面的距離稱為分類間隔，最優(yōu)超平面也可以稱作最大間隔超平面。211最大間隔一個超平面，如果它能將訓(xùn)練樣本沒有錯誤地分開，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分類問題的數(shù)學(xué)表示已知：訓(xùn)練集包含個樣本點(diǎn)：

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

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

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

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

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

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

H1平面：

H2平面：

…..(2)

…..(1)

Chap8SVMZhongzhiShi220Margin=H1平面：H2平面：…..(2)221分劃直線表達(dá)式為“間隔”為極大化“間隔”的思想導(dǎo)致求解下列對變量和的最優(yōu)化問題說明：只要我們求得該問題的最優(yōu)解，從而構(gòu)造分劃超平面，求出決策函數(shù)。上述方法對一般上的分類問題也適用.原始問題Chap8SVMZhongzhiShi221分劃直線表達(dá)式為222求解原始問題為求解原始問題，根據(jù)最優(yōu)化理論，我們轉(zhuǎn)化為對偶問題來求解對偶問題為原始問題中與每個約束條件對應(yīng)的Lagrange乘子。這是一個不等式約束條件下的二次函數(shù)尋優(yōu)問題，存在唯一解222求解原始問題為求解原始問題，根據(jù)最優(yōu)化理論，我們轉(zhuǎn)化為223線性可分問題計算，選擇的一個正分量,并據(jù)此計算事實(shí)上，的每一個分量都與一個訓(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)解223線性可分問題計算224近似線性可分問題不要求所有訓(xùn)練點(diǎn)都滿足約束條件，為此對第個訓(xùn)練點(diǎn)引入松弛變量(SlackVariable),把約束條件放松到。體現(xiàn)了訓(xùn)練集被錯分的情況，可采用作為一種度量來描述錯劃程度。兩個目標(biāo)：1.間隔盡可能大2.錯劃程度盡可能小顯然，當(dāng)充分大時，樣本點(diǎn)總可以滿足以上約束條件。然而事實(shí)上應(yīng)避免太大，所以需在目標(biāo)函數(shù)對進(jìn)行懲罰（即“軟化”約束條件）Chap8SVMZhongzhiShi224近似線性可分問題不要求所有訓(xùn)練點(diǎn)都滿足約束條件225因此，引入一個懲罰參數(shù)，新的目標(biāo)函數(shù)變?yōu)?體現(xiàn)了經(jīng)驗風(fēng)險，而則體現(xiàn)了表達(dá)能力。所以懲罰參數(shù)實(shí)質(zhì)上是對經(jīng)驗風(fēng)險和表達(dá)能力匹配一個裁決。當(dāng)時，近似線性可分SVC的原始問題退化為線性可分SVC的原始問題。近似線性可分問題Chap8SVMZhongzhiShi225因此，引入一個懲罰參數(shù)，新的目標(biāo)函數(shù)226(廣義)線性支持向量分類機(jī)算法設(shè)已知訓(xùn)練集，其中2.選擇適當(dāng)?shù)膽土P參數(shù)，構(gòu)造并求解最優(yōu)化問題3.計算，選擇的一個分量，并據(jù)此計算出4.構(gòu)造分劃超平面,決策函數(shù)求得226(廣義)線性支持向量分類機(jī)算法設(shè)已知訓(xùn)練集227非線性分類例子:227非線性分類例子: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)考慮把2維空間映射到6維空間的變換上式可將2維空間上二次曲線映射為6維空間上的一個超平面：非線性分類231設(shè)訓(xùn)練集232可見，只要利用變換，把所在的2維空間的兩類輸入點(diǎn)映射到所在的6維空間，然后在這個6維空間中，使用線性學(xué)習(xí)機(jī)求出分劃超平面：最后得出原空間中的二次曲線：怎樣求6維空間中的分劃超平面？(線性支持向量分類機(jī))非線性分類232可見，只要利用變換，把所在的2維空間的兩類輸233需要求解的最優(yōu)化問題其中非線性分類233需要求解的最優(yōu)化問題其中非線性分類234在求得最優(yōu)化問題的解后，得到分劃超平面其中最后得到?jīng)Q策函數(shù)或線性分劃－>非線性分劃

代價：2維空間內(nèi)積－>6維空間內(nèi)積非線性分類234在求得最優(yōu)化問題的解235為此，引進(jìn)函數(shù)有比較(2)和(3)，可以發(fā)現(xiàn)這是一個重要的等式，提示6維空間中的內(nèi)積可以通過計算中2維空間中的內(nèi)積得到。非線性分類235為此，引進(jìn)函數(shù)有比較(2)和(3)，可以發(fā)現(xiàn)這是一個重236實(shí)現(xiàn)非線性分類的思想給定訓(xùn)練集后，決策函數(shù)僅依賴于而不需要再考慮非線性變換如果想用其它的非線性分劃辦法，則可以考慮選擇其它形式的函數(shù)，一旦選定了函數(shù)，就可以求解最優(yōu)化問題得，而決策函數(shù)236實(shí)現(xiàn)非線性分類的思想給定訓(xùn)練集后，決策函數(shù)僅依賴于得237決策函數(shù)其中實(shí)現(xiàn)非線性分類的思想237決策函數(shù)其中實(shí)現(xiàn)非線性分類的思想238多項式內(nèi)核徑向基函數(shù)內(nèi)核RBFSigmoind內(nèi)核目前研究最多的核函數(shù)主要有三類：得到q階多項式分類器每個基函數(shù)中心對應(yīng)一個支持向量，它們及輸出權(quán)值由算法自動確定包含一個隱層的多層感知器，隱層節(jié)點(diǎn)數(shù)是由算法自動確定核函數(shù)的選擇Chap8SVMZhongzhiShi238多項式內(nèi)核目前研究最多的核函數(shù)主要有三類：得到q階多SVM算法實(shí)現(xiàn)軟件LIBSVM：臺灣大學(xué)林智仁教授等開發(fā)，有各種版本，應(yīng)用很廣泛LS-SVMLAB：Matlab界面，分類、回歸都可OSU_SVM：用于分類，可以實(shí)現(xiàn)多分類SVMtoolbox:Matlab界面，代碼簡單，適合初學(xué)者了解原理，但算法效率較低39SVM算法實(shí)現(xiàn)軟件LIBSVM：臺灣大學(xué)林智仁教授等開發(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ù)測模型的建立核函數(shù)的選擇在實(shí)驗中選取RBF函數(shù)作為核函數(shù)的首選，原因：1.RBF函數(shù)可以將樣本非線性地規(guī)劃到更高維的空間中，從而實(shí)現(xiàn)非線形影射。Sigmoid核函數(shù)取某些特定參數(shù)時性能和RBF相同。2.RBF函數(shù)的參數(shù)只有一個。相比之下多項式核函數(shù)參數(shù)比RBF核函數(shù)多，因此其模型選擇更為復(fù)雜。3.RBF函數(shù)的數(shù)值限制條件少。RBF函數(shù)使數(shù)值被限制在0和1之間，而多項式核函數(shù)的值可能會趨于不定值或零值且冪值更高；Sigmoid核函數(shù)在取某些參數(shù)值時則可能無效。41SVM預(yù)測模型的建立核函數(shù)的選擇41SVM預(yù)測模型的建立（續(xù)）C和r和選取（以分類為例）

選定一組C,r的范圍和,然后將它們的準(zhǔn)確率用等高線連接起來繪出類似下圖。42SVM預(yù)測模型的建立（續(xù)）C和r和選?。ㄒ苑诸悶槔?2用SVM實(shí)現(xiàn)煤炭需求量的預(yù)測任務(wù)：用1980-2002年的我國煤炭需求量來預(yù)測2003-2006年的煤炭需求量將歷年的煤炭消費(fèi)量X(t)看作時間序列，則其預(yù)測模型可以描述為其中為Φ非線形函數(shù)，p為嵌入維數(shù)，根據(jù)上式,可以得到輸入樣本和輸出樣本,這里用1999-2002年的數(shù)據(jù)作為檢驗樣本,分別用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ù)測性能比較SVMRBF神經(jīng)網(wǎng)絡(luò)預(yù)測用SVM實(shí)現(xiàn)煤炭需求量的預(yù)測用訓(xùn)練好的SVM模型來預(yù)測將來2003-2006年的煤炭需求量，其需求趨勢如下圖：2003-2006年的預(yù)測值44用SVM實(shí)現(xiàn)煤炭需求量的預(yù)測用訓(xùn)練好的SVM模型來預(yù)測將來2有待解決的問題1.如何合選擇SVM的參數(shù)：怎樣合理選擇支持向量的核參數(shù)，目前尚無定論。格子搜索法比較常見，有的學(xué)者已提出用遺傳算法、粒子群算法等優(yōu)化參數(shù)2.如何實(shí)現(xiàn)時間序列的動態(tài)預(yù)測：動態(tài)預(yù)測要求SVM的參數(shù)能適應(yīng)序列的動態(tài)變化，即建立基于SVM自適應(yīng)預(yù)測控制系統(tǒng)45有待解決的問題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)計學(xué)習(xí)方法概述統(tǒng)計學(xué)習(xí)問題學(xué)習(xí)過程的泛化能力支持向量機(jī)SVM尋優(yōu)算法應(yīng)用內(nèi)容提要統(tǒng)計學(xué)習(xí)方法概述支持向量機(jī)SVM是一種基于統(tǒng)計學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法，它是由Boser,Guyon,Vapnik在COLT-92上首次提出，從此迅速發(fā)展起來VapnikVN.1995.TheNatureofStatisticalLearningTheory.Springer-Verlag,NewYorkVapnikVN.1998.StatisticalLearningTheory.Wiley-IntersciencePublication,JohnWiley&Sons,Inc目前已經(jīng)在許多智能信息獲取與處理領(lǐng)域都取得了成功的應(yīng)用。

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

線性分類器ayestf

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

-b)denotes+1denotes-1Howwouldyouclassifythisdata?25線性分類器ayestfxf(x,w,257線性分類器f

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

-b)Howwouldyouclassifythisdata?26線性分類器fxayestdenotes258線性分類器f

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

-b)Howwouldyouclassifythisdata?27線性分類器fxayestdenotes259線性分類器f

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

-b)Howwouldyouclassifythisdata?28線性分類器fxayestdenotes260線性分類器f

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

-b)Howwouldyouclassifythisdata?哪一個分界面是最優(yōu)的？？29線性分類器fxayestdenotes261分類超平面Trainingset:(xi,yi),i=1,2,…N;yi{+1,-1}Hyperplane:wx+b=0Thisisfullydeterminedby(w,b)w1x+b1=0w2x+b2=0w3x+b3=0210分類超平面Trainingset:(xi,yi)262最大間隔一個超平面，如果它能將訓(xùn)練樣本沒有錯誤地分開，并且兩類訓(xùn)練樣本中離超平面最近的樣本與超平面之間的距離是最大的，則把這個超平面稱作最優(yōu)分類超平面（optimalseparatinghyperplane），兩類樣本中離分類面最近的樣本到分類面的距離稱為分類間隔，最優(yōu)超平面也可以稱作最大間隔超平面。211最大間隔一個超平面，如果它能將訓(xùn)練樣本沒有錯誤地分開，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分類問題的數(shù)學(xué)表示已知：訓(xùn)練集包含個樣本點(diǎn)：

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

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

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

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

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

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

H1平面：

H2平面：

…..(2)

…..(1)

Chap8SVMZhongzhiShi220Margin=H1平面：H2平面：…..(2)272分劃直線表達(dá)式為“間隔”為極大化“間隔”的思想導(dǎo)致求解下列對變量和的最優(yōu)化問題說明：只要我們求得該問題的最優(yōu)解，從而構(gòu)造分劃超平面，求出決策函數(shù)。上述方法對一般上的分類問題也適用.原始問題Chap8SVMZhongzhiShi221分劃直線表達(dá)式為273求解原始問題為求解原始問題，根據(jù)最優(yōu)化理論，我們轉(zhuǎn)化為對偶問題來求解對偶問題為原始問題中與每個約束條件對應(yīng)的Lagrange乘子。這是一個不等式約束條件下的二次函數(shù)尋優(yōu)問題，存在唯一解222求解原始問題為求解原始問題，根據(jù)最優(yōu)化理論，我們轉(zhuǎn)化為274線性可分問題計算，選擇的一個正分量,并據(jù)此計算事實(shí)上，的每一個分量都與一個訓(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)解223線性可分問題計算275近似線性可分問題不要求所有訓(xùn)練點(diǎn)都滿足約束條件，為此對第個訓(xùn)練點(diǎn)引入松弛變量(SlackVariable),把約束條件放松到。體現(xiàn)了訓(xùn)練集被錯分的情況，可采用作為一種度量來描述錯劃程度。兩個目標(biāo)：1.間隔盡可能大2.錯劃程度盡可能小顯然，當(dāng)充分大時，樣本點(diǎn)總可以滿足以上約束條件。然而事實(shí)上應(yīng)避免太大，所以需在目標(biāo)函數(shù)對進(jìn)行懲罰（即“軟化”約束條件）Chap8SVMZhongzhiShi224近似線性可分問題不要求所有訓(xùn)練點(diǎn)都滿足約束條件276因此，引入一個懲罰參數(shù)，新的目標(biāo)函數(shù)變?yōu)?體現(xiàn)了經(jīng)驗風(fēng)險，而則體現(xiàn)了表達(dá)能力。所以懲罰參數(shù)實(shí)質(zhì)上是對經(jīng)驗風(fēng)險和表達(dá)能力匹配一個裁決。當(dāng)時，近似線性可分SVC的原始問題退化為線性可分SVC的原始問題。近似線性可分問題Chap8SVMZhongzhiShi225因此，引入一個懲罰參數(shù)，新的目標(biāo)函數(shù)277(廣義)線性支持向量分類機(jī)算法設(shè)已知訓(xùn)練集，其中2.選擇適當(dāng)?shù)膽土P參數(shù)，構(gòu)造并求解最優(yōu)化問題3.計算，選擇的一個分量，并據(jù)此計算出4.構(gòu)造分劃超平面,決策函數(shù)求得226(廣義)線性支持向量分類機(jī)算法設(shè)已知訓(xùn)練集278非線性分類例子:227非線性分類例子: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)考慮把2維空間映射到6維空間的變換上式可將2維空間上二次曲線映射為6維空間上的一個超平面：非線性分類231設(shè)訓(xùn)練集283可見，只要利用變換，把所在的2維空間的兩類輸入點(diǎn)映射到所在的6維空間，然后在這個6維空間中，使用線性學(xué)習(xí)機(jī)求出分劃超平面：最后得出原空間中的二次曲線：怎樣求6維空間中的分劃超平面？(線性支持向量分類機(jī))非線性分類232可見，只要利用變換，把所在的2維空間的兩類輸284需要求解的最優(yōu)化問題其中非線性分類233需要求解的最優(yōu)化問題其中非線性分類285在求得最優(yōu)化問題的解后，得到分劃超平面其中最后得到?jīng)Q策函數(shù)或線性分劃－>非線性分劃

代價：2維空間內(nèi)積－>6維空間內(nèi)積非線性分類234在求得最優(yōu)化問題的解286為此，引進(jìn)函數(shù)有比較(2)和(3)，可以發(fā)現(xiàn)這是一個重要的等式，提示6維空間中的內(nèi)積可以通過計算中2維空間中的內(nèi)積得到。非線性分類235為此，引進(jìn)函數(shù)有比較(2)和(3)，可以發(fā)現(xiàn)這是一個重287實(shí)現(xiàn)非線性分類的思想給定訓(xùn)練集后，決策函數(shù)僅依賴于而不需要再考慮非線性變換如果想用其它的非線性分劃辦法，則可以考慮選擇其它形式的函數(shù)，一旦選定了函數(shù)，就可以求解最優(yōu)化問題得，而決策函數(shù)236實(shí)現(xiàn)非線性分類的思想給定訓(xùn)練集后，決策函數(shù)僅依賴于得288決策函數(shù)其中實(shí)現(xiàn)非線性分類的思想237決策函數(shù)其中實(shí)現(xiàn)非線性分類的思想289多項式內(nèi)核徑向基函數(shù)內(nèi)核RBFSigmoind內(nèi)核目前研究最多的核函數(shù)主要有三類：得到q階多項式分類器每個基函數(shù)中心對應(yīng)一個支持向量，它們及輸出權(quán)值由算法自動確定包含一個隱層的多層感知器，隱層節(jié)點(diǎn)數(shù)是由算法自動確定核函數(shù)的選擇Chap8SVMZhongzhiShi238多項式內(nèi)核目前研究最多的核函數(shù)主要有三類：得到q階多SVM算法實(shí)現(xiàn)軟件LIBSVM：臺灣大學(xué)林智仁教授等開發(fā)，有各種版本，應(yīng)用很廣泛LS-SVMLAB：Matlab界面，分類、回歸都可OSU_SVM：用于分類，可以實(shí)現(xiàn)多分類SVMtoolbox:Matlab界面，代碼簡單，適合初學(xué)者了解原理，但算法效率較低90SVM算法實(shí)現(xiàn)軟件LIBSVM：臺灣大學(xué)林智仁教授等開發(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ù)測模型的建立核函數(shù)的選擇在實(shí)驗中選取RBF函數(shù)作為核函數(shù)的首選，原因：1.RBF函數(shù)可以將樣本非線性地規(guī)劃到更高維的空間中，從而實(shí)現(xiàn)非線形影射。Sigmoid核函數(shù)取某些特定參數(shù)時性能和RBF相同。2.RBF函數(shù)的參數(shù)只有一個。相比之下多項式核函數(shù)參數(shù)比RBF核函數(shù)多，因此其模型選擇更為復(fù)雜。3.RBF函數(shù)的數(shù)值限制條件少。RBF函數(shù)使數(shù)值被限制在0和1之間，而多項式核函數(shù)的值可能會趨于不定值或零值且冪值更高；Sigmoid核函數(shù)在取某些參數(shù)值時則可能無效。92SVM預(yù)測模型的建立核函數(shù)的選擇41SVM預(yù)測模型的建立（續(xù)）C和r和選取（以分類為例）

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

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