監(jiān)督學(xué)習(xí)算法基礎(chǔ)知識(shí)整理

第三章監(jiān)督學(xué)習(xí)算法監(jiān)督學(xué)習(xí)又稱為分類(Classification)或者歸納學(xué)習(xí)(InductiveLearning)。幾乎適用于所有領(lǐng)域，包括文本和網(wǎng)頁(yè)處理。給出一個(gè)數(shù)據(jù)集D,機(jī)器學(xué)習(xí)的目標(biāo)就是產(chǎn)生一個(gè)聯(lián)系屬性值集合A和類標(biāo)集合C的分類/預(yù)測(cè)函數(shù)(Classification/PredictionFunction),這個(gè)函數(shù)可以用于預(yù)測(cè)新的屬性集合的類標(biāo)。這個(gè)函數(shù)又被稱為分類模型(ClassificationModel)、預(yù)測(cè)模型(PredictionModel)。這個(gè)分類模型可以是任何形式的，例如決策樹(shù)、規(guī)則集、貝葉斯模型或者一個(gè)超平面。在監(jiān)督學(xué)習(xí)(SupervisedLearning)中，已經(jīng)有數(shù)據(jù)給出了類標(biāo)；與這一方式相對(duì)的是無(wú)監(jiān)督學(xué)習(xí)(UnsupervisedLearning)，在這種方式中，所有的類屬性都是未知的，算法需要根據(jù)數(shù)據(jù)集的特征自動(dòng)產(chǎn)生類屬性。其中算法中用于進(jìn)行學(xué)習(xí)的數(shù)據(jù)集叫做訓(xùn)練數(shù)據(jù)集，當(dāng)使用學(xué)習(xí)算法用訓(xùn)練數(shù)據(jù)集學(xué)習(xí)得到一個(gè)模型以后，我們使用測(cè)試數(shù)據(jù)集來(lái)評(píng)測(cè)這個(gè)模型的精準(zhǔn)度。機(jī)器學(xué)習(xí)的最基本假設(shè)：訓(xùn)練數(shù)據(jù)的分布應(yīng)該與測(cè)試數(shù)據(jù)的分布一致。訓(xùn)練算法：訓(xùn)練算法就是給定一組樣本，我們計(jì)算這些參數(shù)的方法。本節(jié)簡(jiǎn)要介紹以下幾種常用的機(jī)器學(xué)習(xí)算法，比如決策樹(shù)，樸素貝葉斯，神經(jīng)網(wǎng)絡(luò)，支持向量機(jī)，線性最小平方擬合，kNN，最大熵等。3.1兩類感知器見(jiàn)課本3.2多類感知器見(jiàn)課本3.3決策樹(shù)算法決策樹(shù)學(xué)習(xí)算法是分類算法中最廣泛應(yīng)用的一種技術(shù)，這種算法的分類精度與其他算法相比具有相當(dāng)?shù)母?jìng)爭(zhēng)力，并且十分高效。決策樹(shù)是一個(gè)預(yù)測(cè)模型；他代表的是對(duì)象屬性與對(duì)象值之間的一種映射關(guān)系。樹(shù)中每個(gè)節(jié)點(diǎn)表示某個(gè)對(duì)象屬性，而每個(gè)分叉路徑則代表的某個(gè)可能的屬性值，而每個(gè)葉結(jié)點(diǎn)則對(duì)應(yīng)從根節(jié)點(diǎn)到該葉節(jié)點(diǎn)所經(jīng)歷的路徑所表示的對(duì)象的值(類別)。決策樹(shù)僅有單一輸出，若欲有復(fù)數(shù)輸出，可以建立獨(dú)立的決策樹(shù)以處理不同輸出。如何構(gòu)造精度高、規(guī)模小的決策樹(shù)是決策樹(shù)算法的核心內(nèi)容。決策樹(shù)構(gòu)造可以分兩步進(jìn)行。決策樹(shù)的生成：由訓(xùn)練樣本集生成決策樹(shù)的過(guò)程。一般情況下，訓(xùn)練樣本數(shù)據(jù)集是根據(jù)實(shí)際需要有歷史的、有一定綜合程度的，用于數(shù)據(jù)分析處理的數(shù)據(jù)集。樹(shù)以代表訓(xùn)練樣本的單個(gè)結(jié)點(diǎn)開(kāi)始。如果樣本都在同一個(gè)類.則該結(jié)點(diǎn)成為樹(shù)葉，并用該類標(biāo)記。否則，算法選擇最有分類能力的屬性作為決策樹(shù)的當(dāng)前結(jié)點(diǎn)。4?根據(jù)當(dāng)前決策結(jié)點(diǎn)屬性取值的不同，將訓(xùn)練樣本數(shù)據(jù)集分為若干子集，每個(gè)取值形成一個(gè)分枝。針對(duì)上一步得到的一個(gè)子集，重復(fù)進(jìn)行先前步驟，形成每個(gè)劃分樣本上的決策樹(shù)。遞歸劃分步驟僅當(dāng)下列條件之一成立時(shí)停止：給定結(jié)點(diǎn)的所有樣本屬于同一類。沒(méi)有剩余屬性可以用來(lái)進(jìn)一步劃分樣本。以樣本組中個(gè)數(shù)最多的類別作為類別標(biāo)記。AlgiJiithmdecisionTreefD,A,T)】 ifDcontainsonlytrainingexamplesofthesameclassqgCthenmakeTaleafnodelabeledwithclassy;dsdf.4—0thenmakeTaleafnodelabeledwithc$whichisthemostfrequentclassinDelse!!Dcontainsexamplesbelongingtoamixtureofclasses.Weselectasingle!!atcributetopartitionDintoSubsetssoLhateachsubseti￡purer-impurityEval-1(D);foreachattributeA,eA(={A坯…，禺})dopf三impurityEval-2(AhD)endfoiSelecte 衛(wèi)工，亠“thatgivesthebiggestimpurityreduction,computedusing-p占ifpo—<thresholdthen//屏甘docsnotsignificantlyreduceimpuritypGmakeTaleafnodelabeledwithCj,themostfrequentclassinD.dse // isabletoredixeimpurityp0MakeTadecisionnodeonLetthepossiblevaluesofbeV|,5卩對(duì)PartitionDintomdisjointsubsetsD^D》、…、basedonthemvaluesofAforeachD)in{DhD》,…,doi『0H0thimcreateabranch(edge)node7}forVjasachildnodeofJ;decisionTree(D^AT』/5丁)HA營(yíng)也removedendifendfoi*endifendif決策樹(shù)的剪技：決策樹(shù)的剪枝是對(duì)上一階段生成的決策樹(shù)進(jìn)行檢驗(yàn)、校正和修下的過(guò)程，主要是用新的樣本數(shù)扼集(稱為測(cè)試數(shù)據(jù)集)中的數(shù)據(jù)校驗(yàn)決策樹(shù)生成過(guò)程中產(chǎn)生的初步規(guī)則，將那些影響預(yù)衡準(zhǔn)確性的分枝剪除。由于數(shù)據(jù)表示不當(dāng)、有噪聲或者由于決策樹(shù)生成時(shí)產(chǎn)生重復(fù)的子樹(shù)等原因，都會(huì)造成產(chǎn)生的決策樹(shù)過(guò)大。因此，簡(jiǎn)化決策樹(shù)是一個(gè)不可缺少的環(huán)節(jié)。尋找一棵最優(yōu)決策樹(shù)，主要應(yīng)解決以下3個(gè)最優(yōu)化問(wèn)題：生成最少數(shù)目的葉子節(jié)點(diǎn)；生成的每個(gè)葉子節(jié)點(diǎn)的深度最??；

生成的決策樹(shù)葉子節(jié)點(diǎn)最少且每個(gè)葉子節(jié)點(diǎn)的深度最小。例如，對(duì)于表3-1所示的貸款申請(qǐng)的數(shù)據(jù)集，可以學(xué)習(xí)到一種決策樹(shù)結(jié)構(gòu),表示為圖3-1。ID12ID123456789101112131415AgeOwnhouseCreditratingClassyoungfalsefalsefairXoyoungfalsefalsegoodXoyoungtruefalsegoodYesyoungtruetruefairYesyoungfalsefalsefairXomiddlefalsefalsefairXomiddlefalsefalsegood\omiddletruetnic呂oodYesmiddlefalsetrueexcellentYesmiddlefalsetrueexcellentYesoldfalsetrueexcellentYesoldfalsetrue呂oodYesoldtruefalsegoodYesoldtruefalseexcellentYesoldfalsefalsefairNd表3-1貸款申請(qǐng)數(shù)據(jù)根據(jù)數(shù)據(jù)集建立的一種決策樹(shù)結(jié)構(gòu)如下:Youngmiddle1HasJob?Ownhouse?Creditrating?7\truefalse/ xtrue/zxfalse\fairgoodexcellent1、YesNoYesNoNoYesYes(2/2)(3/3)(2/2)(1/1)(2/2)(2⑵圖3-1對(duì)應(yīng)與表3-1的決策樹(shù)樹(shù)中包含了決策點(diǎn)和葉子節(jié)點(diǎn)，決策點(diǎn)包含針對(duì)數(shù)據(jù)實(shí)例某個(gè)屬性的一些測(cè)試，而一個(gè)葉子節(jié)點(diǎn)則代表了一個(gè)類標(biāo)。一棵決策樹(shù)的構(gòu)建過(guò)程是不斷的分隔訓(xùn)練數(shù)據(jù)，以使得最終分隔所得到的各個(gè)子集盡可能的純。一個(gè)純的子集中的數(shù)據(jù)實(shí)例類標(biāo)全部一致。決策樹(shù)的建立并不是唯一的，在實(shí)際中，我們希望得到一棵盡量小且準(zhǔn)確的決策樹(shù)。決策樹(shù)的典型算法有ID3,C4.5,CART（分類與回歸樹(shù)）等。依次得到改進(jìn)。相對(duì)于其它算法，決策樹(shù)易于理解和實(shí)現(xiàn)，人們?cè)谕ㄟ^(guò)解釋后都有能力去理解決策樹(shù)所表達(dá)的意義。決策樹(shù)可以同時(shí)處理不同類型的屬性，并且在相對(duì)短的時(shí)間內(nèi)能夠?qū)Υ笮蛿?shù)據(jù)源做出可行且效果良好的結(jié)果。3.4貝葉斯分類算法貝葉斯分類器的分類原理是通過(guò)某對(duì)象的先驗(yàn)概率，利用貝葉斯公式計(jì)算出其后驗(yàn)概率，即該對(duì)象屬于某一類的概率，選擇具有最大后驗(yàn)概率的類作為該對(duì)象所屬的類。目前研究較多的貝葉斯分類器主要有四種，分別是：NaiveBayes、TAN、BAN和GBN。▲準(zhǔn)備知識(shí)條件概率：設(shè)A,B是兩個(gè)事件，且Pr(A)>0稱Pr(BIA)二pr(AB)為在條件A下Pr(A)發(fā)生的條件事件B發(fā)生的條件概率。乘法公式：設(shè)Pr(A)>0則有Pr(AB)二Pr(BIA)Pr(A)TOC\o"1-5"\h\z\o"CurrentDocument"全概率公式：設(shè)隨機(jī)事件A],A2,...，An以及B滿足：⑴A],A2，…，An兩兩互不相容；(2)UA=S或者BuUA；(3)Pr(A)>0(n=l,2,...)，則有n nn=1 n=1Pr(B)=FPr(A)Pr(B|A)，稱為全概率公式。n nn=1全概率公式的應(yīng)用：把事件B看作是某一個(gè)過(guò)程的結(jié)果，把A1，A2,…，An看作該過(guò)程的若干個(gè)原因，根據(jù)歷史資料，每個(gè)原因發(fā)生的概率已知(即Pr(Ai)已知)，且每一個(gè)原因?qū)Y(jié)果的影響已知(即Pr(B|Ai)已知)則可用全概率公式計(jì)算結(jié)果發(fā)生的概率，即求Pr(B)。貝葉斯公式：設(shè)隨機(jī)事件A1，A2，…，An以及B滿足：(1)A1，A2，…，An兩兩互不相容；(2)UA=S或者BuUA；(3)Pr(A)>0(n=1,2,...)，則TOC\o"1-5"\h\zn nn=1 n=1PrAB=)PrAnB=—田(AJ APr(稱為貝葉斯公式。n PrB)￡P(guān)rBA)PAr()\o"CurrentDocument"j jn=1貝葉斯公式的使用：把事件B看作某一過(guò)程的結(jié)果，把A1，A2，…，An看作該過(guò)程的若干原因，根據(jù)歷史資料，每一原因發(fā)生的概率已知(即Pr(An)已知)，如果已知事件B已經(jīng)發(fā)生，要求此時(shí)是由第i個(gè)原因引起的概率，用貝葉斯公式(即求Pr(AJB))?！鴺闼刎惾~斯(NaiveBayes,NB)算法在貝葉斯分類中，在數(shù)據(jù)集合D中，令A(yù)1?A2,…A為用離散值表示的屬性1 2 n

集合，設(shè)C具有IC個(gè)不同值的類別屬性，即c1,c2,^,c|c|,我們?cè)O(shè)所有的屬性都是條件獨(dú)立于類別，給定一個(gè)測(cè)試樣例d觀察到屬性值a1到a⑷，其中ai是Ai可能的一個(gè)取值，那么預(yù)測(cè)值就是類別j使得Pr(C=c.I4幻,...比=。⑷)最大。c被稱為最大后驗(yàn)概率假設(shè)。根據(jù)貝葉斯公式，有Pr(C二c)FIpr(A二aIC二c)TOC\o"1-5"\h\zj ii jPr(A=a A=aIC=c)=1 1 IAI IAI j百 可乙Pr(C=c)11Pr(A=aIC=c)k ii kk=1 i=1因?yàn)榉帜笇?duì)每一個(gè)訓(xùn)練類別都是一樣的，所以如果僅僅需要總體上最可能的類別為所有測(cè)試樣例做預(yù)測(cè)，那么只需要上式的分子部分即可。通過(guò)下式來(lái)判斷最有可能的類別：c=argmaxPr(C=c?jc)FIpr(A=aIC=c=argmaxPr(C=c?jjiiji=1例如，假設(shè)我們有圖4-1中的訓(xùn)練數(shù)據(jù)，有兩個(gè)屬性A和B,還有類別C，對(duì)于一個(gè)測(cè)試樣例：A=mB=q求C=?ABCmbtmstgqthstgqtgqfgsfhbfhqfrnibf圖4-1訓(xùn)練數(shù)據(jù)計(jì)算如下：對(duì)于類別為t的概率Pr(C=t)1pr(A=aIC=t)=Pr(C=t)-Pr(A=mIC=t)-Pr(B=qIC=t)=-x-xjj 25j=11類似的，對(duì)于類別為f的概率1Pr(C=f)弘(Ajj=1因此C=t的可能性較大，因此將此種情況下的類別判斷為t。樸素貝葉斯分類將每篇文檔看作一“袋子”的詞，需要做以下假設(shè)，這也是稱作“樸素的”貝葉斯的由來(lái)：?文檔中的詞都是獨(dú)立于語(yǔ)境生成的。?單詞被生成的概率是與它在文檔中的位置無(wú)關(guān)的。?文檔的長(zhǎng)度與類別是無(wú)關(guān)的。通過(guò)公式推導(dǎo)，最后可以得到分類函數(shù)Pr(cId)xPr(c汕Pr(wIc)i i jij=1其中，Pr(wIc)=一入+(wj'ci)_。Tf(w,c)是詞w在c.類訓(xùn)練文檔

j'九IVI+蘭TF(w,c) j' JJkik=1集中出現(xiàn)的頻率，九是一個(gè)因子，一般設(shè)為九=l/n,n為訓(xùn)練數(shù)據(jù)的總數(shù)，當(dāng)九=1時(shí)，稱為拉普拉斯延續(xù)率。加入平滑算子的目的是解決不經(jīng)常出現(xiàn)的單詞零概率估計(jì)的問(wèn)題，需要對(duì)概率進(jìn)行平滑處理來(lái)避免出現(xiàn)0或1概率?！鴺闼刎惾~斯文本分類的優(yōu)缺點(diǎn)雖然樸素貝葉斯學(xué)習(xí)所做的大部分假設(shè)都與實(shí)際情況不符，但研究表明樸素貝葉斯學(xué)習(xí)仍然能產(chǎn)生準(zhǔn)確的模型。樸素貝葉斯學(xué)習(xí)效率很高，它只需要對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行一次掃描就可以估計(jì)出所有需要的概率，所以樸素貝葉斯在文本分類中得到了廣泛的應(yīng)用。3.5k最近鄰算法(kNN算法)其他學(xué)習(xí)算法是從數(shù)據(jù)中得到一個(gè)模型，稱為迫切學(xué)習(xí)，因?yàn)樗麄冊(cè)跍y(cè)試之前學(xué)習(xí)得到了數(shù)據(jù)對(duì)應(yīng)的模型。相反，k-近鄰(kNearestNeighbor，kNN)是一種惰性的學(xué)習(xí)方法，因?yàn)椴恍枰獜挠?xùn)練數(shù)據(jù)中學(xué)習(xí)得到模型。學(xué)習(xí)僅僅在測(cè)試樣例需要分類時(shí)發(fā)生。k近鄰的想法很直接但是在很多場(chǎng)合很有效，例如文本分類。它是如下實(shí)現(xiàn)的：令D為訓(xùn)練數(shù)據(jù)集。不需要對(duì)訓(xùn)練樣本做任何操作。當(dāng)測(cè)試樣例d出現(xiàn)時(shí)，算法將d和D中所有訓(xùn)練樣例比較，計(jì)算它們之間的相似度(或者距離)。從D中選出前k個(gè)最相似(相近)的樣本。這個(gè)樣例集合被稱為k-近鄰。d的類別由k近鄰中最常見(jiàn)的類別決定。如圖6-1所示。

I-nearstneighbornearstneighbornearstneighborI-nearstneighbornearstneighbornearstneighbor圖6-1k-近鄰分類圖示優(yōu)點(diǎn)：kNN方法相當(dāng)于非參數(shù)密度估計(jì)方法，在決策時(shí)只與極少量的相鄰樣本有關(guān)。另外，由于kNN方法主要靠周圍有限的鄰近的樣本，因此對(duì)于類域的交叉或重疊較多的非線性可分?jǐn)?shù)據(jù)來(lái)說(shuō)，kNN方法較其他方法更為適合。缺點(diǎn)：kNN的一個(gè)不足是判斷一個(gè)樣本的類別時(shí)，需要把它與所有已知類別的樣本都比較一遍，這樣計(jì)算開(kāi)銷是相當(dāng)大的。比如一個(gè)文本分類系統(tǒng)有上萬(wàn)個(gè)類，每個(gè)類即便只有20個(gè)訓(xùn)練樣本，為了判斷一個(gè)新樣本的類別，也要做20萬(wàn)次的向量比較。這個(gè)問(wèn)題可以通過(guò)對(duì)樣本空間建立索引來(lái)彌補(bǔ)。kNN也有另一個(gè)不足是當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很大，而其他類樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的k個(gè)鄰居中大容量類的樣本占多數(shù)，導(dǎo)致分類錯(cuò)誤。因此可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來(lái)改進(jìn)。產(chǎn)生了第一個(gè)不足。總結(jié)：目前常用的解決方法是事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯，事先去除對(duì)分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。3?6、支持向量機(jī)（SVM）支持向量機(jī)（SupportVectorMachine）是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識(shí)別中表現(xiàn)出許多特有的優(yōu)勢(shì)，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問(wèn)題中。支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜（即對(duì)特定訓(xùn)練樣本的學(xué)習(xí)精度,Accuracy）和學(xué)習(xí)能力（即無(wú)錯(cuò)誤地識(shí)別任意樣本的能力）之間尋求最佳折衷,以期獲得最好的推廣（泛化）能力?！鳹C維：是對(duì)函數(shù)類的一種度量，可以簡(jiǎn)單的理解為問(wèn)題的復(fù)雜程度，VC維越高，一個(gè)問(wèn)題就越復(fù)雜。正是因?yàn)镾VM關(guān)注的是VC維，后面可以看到，SVM解決問(wèn)題的時(shí)候，和樣本的維數(shù)是無(wú)關(guān)的（甚至樣本是上萬(wàn)維的都可以，這使得SVM很適合用來(lái)解決文本分類的問(wèn)題，當(dāng)然，有這樣的能力也因?yàn)橐肓撕撕瘮?shù)）。核函數(shù)將原始的樣本空間向高維空間進(jìn)行變換，能夠解決原始樣本線性不可分的問(wèn)題?！Y(jié)構(gòu)風(fēng)險(xiǎn)：機(jī)器學(xué)習(xí)本質(zhì)上就是一種對(duì)問(wèn)題真實(shí)模型的逼近（選擇一個(gè)我們認(rèn)為比較好的近似模型，這個(gè)近似模型就叫做一個(gè)假設(shè)），但毫無(wú)疑問(wèn)，真實(shí)模型一定是不知道的，既然真實(shí)模型不知道，那么我們選擇的假設(shè)與問(wèn)題真實(shí)解之間究竟有多大差距，我們就沒(méi)法得知。這個(gè)與問(wèn)題真實(shí)解之間的誤差，就叫做風(fēng)險(xiǎn)（更嚴(yán)格的說(shuō)，誤差的累積叫做風(fēng)險(xiǎn)）。我們選擇了一個(gè)假設(shè)之后（更直觀點(diǎn)說(shuō)，我們得到了一個(gè)分類器以后），真實(shí)誤差無(wú)從得知，但我們可以用某些可以掌握的量來(lái)逼近它。最直觀的想法就是使用分類器在樣本數(shù)據(jù)上的分類的結(jié)果與真實(shí)結(jié)果（因?yàn)闃颖臼且呀?jīng)標(biāo)注過(guò)的數(shù)據(jù)，是準(zhǔn)確的數(shù)據(jù)）之間的差值來(lái)表示。這個(gè)差值叫做經(jīng)驗(yàn)風(fēng)險(xiǎn)Remp（w）o以前的機(jī)器學(xué)習(xí)方法都把經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化作為努力的目標(biāo)，但后來(lái)發(fā)現(xiàn)很多分類函數(shù)能夠在樣本集上輕易達(dá)到100%的正確率，在真實(shí)分類時(shí)卻一塌糊涂（即所謂的推廣能力差，或泛化能力差）。此時(shí)的情況即便是選擇了一個(gè)足夠復(fù)雜的分類函數(shù)（它的VC維很高），能夠精確的記住每一個(gè)樣本，但對(duì)樣本之外的數(shù)據(jù)一律分類錯(cuò)誤?；仡^看看經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則我們就會(huì)發(fā)現(xiàn)，此原則適用的大前提是經(jīng)驗(yàn)風(fēng)險(xiǎn)要確實(shí)能夠逼近真實(shí)風(fēng)險(xiǎn)才行，但實(shí)際上能逼近么？答案是不能，因?yàn)闃颖緮?shù)相對(duì)于現(xiàn)實(shí)世界要分類的文本數(shù)來(lái)說(shuō)簡(jiǎn)直九牛一毛，經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則只在這占很小比例的樣本上做到?jīng)]有誤差，當(dāng)然不能保證在更大比例的真實(shí)文本上也沒(méi)有誤差。統(tǒng)計(jì)學(xué)習(xí)因此而引入了泛化誤差界的概念，就是指真實(shí)風(fēng)險(xiǎn)應(yīng)該由兩部分內(nèi)容刻畫(huà)，一是經(jīng)驗(yàn)風(fēng)險(xiǎn)，代表了分類器在給定樣本上的誤差；二是置信風(fēng)險(xiǎn)，代表了我們?cè)诙啻蟪潭壬峡梢孕湃畏诸惼髟谖粗谋旧戏诸惖慕Y(jié)果。很顯然，第二部分是沒(méi)有辦法精確計(jì)算的，因此只能給出一個(gè)估計(jì)的區(qū)間，也使得整個(gè)誤差只能計(jì)算上界，而無(wú)法計(jì)算準(zhǔn)確的值（所以叫做泛化誤差界，而不叫泛化誤差）。置信風(fēng)險(xiǎn)與兩個(gè)量有關(guān)，一是樣本數(shù)量，顯然給定的樣本數(shù)量越大，我們的學(xué)習(xí)結(jié)果越有可能正確，此時(shí)置信風(fēng)險(xiǎn)越小；二是分類函數(shù)的VC維，顯然VC維越大，推廣能力越差，置信風(fēng)險(xiǎn)會(huì)變大。（匹配的可能性越?。┓夯`差界的公式為：R（w}<Remp（w}+^（n/h）公式中R（w）就是真實(shí)風(fēng)險(xiǎn)，Remp（w）就是經(jīng)驗(yàn)風(fēng)險(xiǎn)，①（n/h）就是置信風(fēng)險(xiǎn)。統(tǒng)計(jì)學(xué)習(xí)的目標(biāo)從經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化變?yōu)榱藢で蠼?jīng)驗(yàn)風(fēng)險(xiǎn)與置信風(fēng)險(xiǎn)的和最小，即結(jié)構(gòu)風(fēng)險(xiǎn)最小。SVM正是這樣一種努力最小化結(jié)構(gòu)風(fēng)險(xiǎn)的算法。▲支持向量機(jī)：是將向量映射到一個(gè)更高維的空間里，在這個(gè)空間里建立有一個(gè)最大間隔超平面。在分開(kāi)數(shù)據(jù)的超平面的兩邊建有兩個(gè)互相平行的超平面。分隔超平面使兩個(gè)平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。?先從最簡(jiǎn)單的線性可分學(xué)習(xí)，如果一個(gè)線性函數(shù)能夠?qū)颖就耆_的分開(kāi)，就稱這些數(shù)據(jù)是線性可分的（如圖5-1所示），否則稱為非線性可分的。在一維空間里線性函數(shù)就是一個(gè)點(diǎn)，在二維空間里就是一條直線，三維空間里就是一個(gè)平面，可以如此想象下去，如果不關(guān)注空間的維數(shù)，這種線性函數(shù)還有一個(gè)統(tǒng)一的名稱 超平面（HyperPlane）圖5-1線性可分的例子實(shí)際上，一個(gè)線性函數(shù)是一個(gè)實(shí)值函數(shù)（即函數(shù)的值是連續(xù)的實(shí)數(shù)），而我們的分類問(wèn)題（例如這里的二元分類問(wèn)題一一回答一個(gè)樣本屬于還是不屬于一個(gè)類別的問(wèn)題）需要離散的輸出值，例如用1表示某個(gè)樣本屬于類別C1,而用0表示不屬于（不屬于C1也就意味著屬于C2），這時(shí)候只需要簡(jiǎn)單的在實(shí)值函數(shù)的基礎(chǔ)上附加一個(gè)閾值即可，通過(guò)分類函數(shù)執(zhí)行時(shí)得到的值大于還是小于這個(gè)閾值來(lái)確定類別歸屬。（前面提到的兩類感知器類似）例如我們有一個(gè)線性函數(shù)g(x)=wx+b其中，x是樣本的向量表示，wx+b=0是超平面，w是超平面的法向量。超平面不止一個(gè)，例如和圖5-1中所示的超平面平行且可劃分類別的直線都是一個(gè)超平面，因此，使用“分類間隔”來(lái)區(qū)分超平面的好壞。定義一個(gè)樣本點(diǎn)到某個(gè)超平面的距離：8=y（wx+b）（稱為函數(shù)間隔），III進(jìn)行歸一化，用旦和丄分別代替w和b,得8=—I（X，其中l(wèi)lwII是wIIw|| ||w|| ||wi的2-范數(shù)°（IIwII叫做向量w的范數(shù)，范數(shù)是對(duì)向量長(zhǎng)度的一種度量。）歸一化后的8?稱作幾何間隔，表示點(diǎn)到超平面的歐氏距離。誤分次數(shù)與幾何間隔存在關(guān)i系:誤分次數(shù)＜迭代次數(shù)5是樣本集合到分類面的幾何間隔，R=maxllxII,i=l,...,n,即R是所有樣i本中（氣是以向量表示的第i個(gè)樣本）向量長(zhǎng)度最長(zhǎng)的值。誤分次數(shù)一定程度上代表分類器的誤差。所以幾何間隔越大，誤分次數(shù)的上界越小。因此要選擇幾何間隔最大的超平面作為支持向量機(jī)米用的超平面。HlOHOH2 、°O\O—□wOD」■O□□margin=2w||圖5-2支持向量機(jī)的超平面其中斗：wx+b=1；H：wx+b=O；H2：wx+b=-1支持向量：落在分類界面上的點(diǎn)（如落在H1和H2上的點(diǎn)）稱作支持向量。?如何尋找最佳超平面，即最大化幾何間隔，是訓(xùn)練階段的目標(biāo)。要使用通過(guò)二次優(yōu)化問(wèn)題（指目標(biāo)函數(shù)為二次函數(shù)，約束條件為線性約束的最優(yōu)化問(wèn)題），得到的是全局最優(yōu)解。由于：函數(shù)間隔：5i=yi（wxi+b）=lg（xi）l15二 Ig（x）l幾何間隔：HwHi可以看出幾何間隔與llwll是成反比的，因此最大化幾何間隔與最小化llwll等價(jià)。而我們常用的方法并不是固定llwll的大小而尋求最大幾何間隔，而是固定間隔即函數(shù)間隔，尋找最小的llwll。凡是求一個(gè)函數(shù)的最值的問(wèn)題都可以稱為尋優(yōu)問(wèn)題（也叫作一個(gè)規(guī)劃問(wèn)題）,又由于找最大值的問(wèn)題總可以通過(guò)加一個(gè)負(fù)號(hào)變?yōu)檎易钚≈档膯?wèn)題，因此我們下面討論的時(shí)候都針對(duì)找最小值的過(guò)程來(lái)進(jìn)行。一個(gè)尋優(yōu)問(wèn)題最重要的部分是目標(biāo)函數(shù)。例如我們想尋找最小的llwll這件事，就可以用下面完全等價(jià)的目標(biāo)函數(shù)來(lái)表示，那就是：不難看出當(dāng)IIwll2達(dá)到最小時(shí)，llwll也達(dá)到最小，反之亦然（前提當(dāng)然是llwll描述的是向量的長(zhǎng)度，因而是非負(fù)的）。之所以采用這種形式，是因?yàn)楹竺娴那蠼膺^(guò)程會(huì)對(duì)目標(biāo)函數(shù)作一系列變換，會(huì)使變換后的形式更為簡(jiǎn)潔（如求導(dǎo)）。目標(biāo)函數(shù)已求出，如果不考慮約束條件同樣會(huì)造成錯(cuò)誤，例如，IIwII最小化可以為0值，反映在圖中，就是H1與H2兩條直線間的距離無(wú)限大，這個(gè)時(shí)候，所有的樣本點(diǎn)（無(wú)論正樣本還是負(fù)樣本）都跑到了H1和H2中間。所以要加入約束條件，約束條件就是在求解過(guò)程中必須滿足的條件，體現(xiàn)在我們的問(wèn)題中就是樣本點(diǎn)必須在H1或H2的某一側(cè)（或者至少在H1和H2上），而不能在兩者中間。方便推導(dǎo)和優(yōu)化的目的我們把間隔固定為1這是指把所有樣本點(diǎn)中間隔最小的那一點(diǎn)的間隔定為1，也就意味著集合中的其他點(diǎn)間隔都不會(huì)小于1，按照間隔的定義，滿足這些條件就相當(dāng)于讓下面的式子總是成立：yi[（w?xi）+b]-1$0（i=1,2,…,n）（n是總的樣本數(shù)）因此我們的兩類分類問(wèn)題也被我們轉(zhuǎn)化成了它的數(shù)學(xué)形式，一個(gè)帶約束的最小值的問(wèn)題：min斗11"『subjectto對(duì)（wx）]+b]-lM0（i=l,2,???,n）（n是總的樣本數(shù)）自變量就是W，而目標(biāo)函數(shù)是w的二次函數(shù)，所有的約束條件都是w的線性函數(shù)，這種規(guī)劃稱二次規(guī)劃（QuadraticProgramming，QP），由于它的可行域是一個(gè)凸集，也是一個(gè)凸二次規(guī)劃（特點(diǎn)：有解，同時(shí)也可以找到）。含有了帶不等式的約束條件。將其轉(zhuǎn)化為帶等式的約束條件。使用拉格朗日理論求出條件極值。由于w由樣本和類別確定，用數(shù)學(xué)的語(yǔ)言描述，就是w可以表示為樣本的某種組合：w=ayx+ayx+...+ayx111 222 nnn這些a被稱為拉格朗日乘子，而xi是樣本點(diǎn)即向量，yi就是第i個(gè)樣本的標(biāo)簽，n就是總樣本點(diǎn)的個(gè)數(shù)。其中只有支持向量樣本對(duì)應(yīng)的a不為0，其他a都為0。式子也可以用求和符號(hào)簡(jiǎn)寫(xiě)一下：因此原來(lái)的g（x）表達(dá)式可以寫(xiě)為：g（x）=<W,X>r=l由于式子中只有xi和x是向量，因此一部分可以從內(nèi)積符號(hào)中拿出來(lái)，得到g（x）的式子為：3g（x）=》>M<p>+bi=l其中X是變量，也就是你要分類哪篇文檔，而所有的xi都是已知的樣本。所以對(duì)于新點(diǎn)x的預(yù)測(cè)，只需要計(jì)算它與訓(xùn)練數(shù)據(jù)點(diǎn)的內(nèi)積即可，這一點(diǎn)至關(guān)重要，是之后使用核函數(shù)進(jìn)行非線性推廣的基本前提。由于非SupportingVector所對(duì)應(yīng)的系數(shù)a都是等于零的，因此對(duì)于新點(diǎn)的內(nèi)積計(jì)算實(shí)際上只要針對(duì)少量的“支持向量”而不是所有的訓(xùn)練數(shù)據(jù)。有該式還可以看出對(duì)w的求解轉(zhuǎn)化為對(duì)a求解。（對(duì)偶變量dualvariable的優(yōu)化問(wèn)題：是解決此凸優(yōu)化問(wèn)題的第二種更為高效的解--對(duì)偶變量的優(yōu)化求解。）完成了一個(gè)弱的SVM即只能處理線性的情況，不過(guò)，在得到了對(duì)偶dual形式之后，通過(guò)核函數(shù)（Kernel）推廣到非線性的情況就變成了一件非常容易的事情了。?核函數(shù)前面已經(jīng)了解到了SVM處理線性可分的情況，而對(duì)于非線性的情況，SVM的處理方法是選擇一個(gè)核函數(shù)K（；），通過(guò)將數(shù)據(jù)映射到高維空間，來(lái)解決在原始空間中線性不可分的問(wèn)題。由于核函數(shù)的優(yōu)良品質(zhì)，這樣的非線性擴(kuò)展在計(jì)算量上并沒(méi)有比原來(lái)復(fù)雜多少。當(dāng)然，這要?dú)w功于核函數(shù)一一除了SVM之外,任何將計(jì)算表示為數(shù)據(jù)點(diǎn)的內(nèi)積的方法，都可以使用核函數(shù)進(jìn)行非線性擴(kuò)展。在線性不可分的情況下，支持向量機(jī)通過(guò)某種事先選擇的非線性映射（核函數(shù)）將輸入變量映射到一個(gè)高維特征空間，在這個(gè)空間中構(gòu)造最優(yōu)分類超平面。我們使用SVM進(jìn)行數(shù)據(jù)集分類工作的過(guò)程首先是同預(yù)先選定的一些非線性映射將輸入空間映射到高維特征空間（下圖很清晰的表達(dá)了通過(guò)映射到高維特征空間，而把平面上本身不好分的非線性數(shù)據(jù)分了開(kāi)來(lái)）：Separationmayheeiisierinhrglierdimensionsconripl^jcinlowdimensions simpleinhigherdimensionsconripl^jcinlowdimensions simpleinhigherdimensions使得在高維屬性空間中有可能將訓(xùn)練數(shù)據(jù)實(shí)現(xiàn)超平面的分割，避免了在原輸入空間中進(jìn)行非線性曲面分割計(jì)算。SVM數(shù)據(jù)集形成的分類函數(shù)具有這樣的性質(zhì)：它是一組以支持向量為參數(shù)的非線性函數(shù)的線性組合，因此分類函數(shù)的表達(dá)式僅和支持向量的數(shù)量有關(guān)，而獨(dú)立于空間的維度，在處理高維輸入空間的分類時(shí)，這種方法尤其有效。用一個(gè)二維平面中的分類問(wèn)題作例子：我們把橫軸上端點(diǎn)a和b之間紅色部分里的所有點(diǎn)定為正類，兩邊的黑色部分里的點(diǎn)定為負(fù)類。試問(wèn)能找到一個(gè)線性函數(shù)把兩類正確分開(kāi)么？不能，因?yàn)槎S空間里的線性函數(shù)就是指直線，顯然找不到符合條件的直線。但我們可以找到一條曲線，例如下面這一條：顯然通過(guò)點(diǎn)在這條曲線的上方還是下方就可以判斷點(diǎn)所屬的類別（你在橫軸上隨便找一點(diǎn)，算算這一點(diǎn)的函數(shù)值，會(huì)發(fā)現(xiàn)負(fù)類的點(diǎn)函數(shù)值一定比0大，而正類的一定比0?。?。這條曲線就是我們熟知的二次曲線，它的函數(shù)表達(dá)式可以寫(xiě)為:它不是一個(gè)線性函數(shù)，轉(zhuǎn)換為線性函數(shù)，新建一個(gè)向量y和a：￡■"1_X,a■■這樣g(x)就可以轉(zhuǎn)化為f(y)=va,y>，實(shí)際上f(y)的形式就是：g(x)=f(y)=ay在任意維度(四維)的空間中，這種形式的函數(shù)都是一個(gè)線性函數(shù)(其中的a和y都是多(二)維向量，自變量y的次數(shù)不大于1)。而轉(zhuǎn)化最關(guān)鍵的部分就在于找到x到y(tǒng)的映射方法。具體到文本分類問(wèn)題，文本被表示為上千維的向量，即使維數(shù)已經(jīng)如此之高，也常常是線性不可分的，還要向更高的空間轉(zhuǎn)化。Eg：舉具體文本分類的例子，看看這種向高維空間映射從而分類的方法如何運(yùn)作，我們文本分類問(wèn)題的原始空間是1000維的(即每個(gè)要被分類的文檔被表示為一個(gè)1000維的向量)，在這個(gè)維度上問(wèn)題是線性不可分的?，F(xiàn)在我們有一個(gè)2000維空間里的線性函數(shù)f(x')=vw',x'>+b它能夠?qū)⒃瓎?wèn)題變得可分。式中的w'和x'都是2000維的向量，只不過(guò)w'是定值，而x'是變量，現(xiàn)在我們的輸入是一個(gè)1000維的向量X，分類的過(guò)程是先把x變換為2000維的向量x'，然后求這個(gè)變換后的向量x'與向量w'的內(nèi)積，再把這個(gè)內(nèi)積的值和b相加，就得到了結(jié)果，看結(jié)果大于閾值還是小于閾值就得到了分類結(jié)果。只關(guān)心那個(gè)高維空間里內(nèi)積的值，分類結(jié)果就算出來(lái)了。核函數(shù)K(w,x)接受低維空間的輸入值，卻能算出高維空間的內(nèi)積值vw',x'>。如果有這樣的函數(shù)，那么當(dāng)給了一個(gè)低維空間的輸入x以后，g(x)=K(w,x)+b〃低維非線性函數(shù)f(x')=vw',x'>+b〃高維線性函數(shù)K(w,x)被稱作核函數(shù)(核，kernel)，核函數(shù)的基本作用就是接受兩個(gè)低維空間里的向量，能夠計(jì)算出經(jīng)過(guò)某個(gè)變換后在高維空間里的向量?jī)?nèi)積值。高維線性分類器，它的形式應(yīng)該是：fax》唄VK>+bi=l可以用一個(gè)低維空間里的函數(shù)來(lái)代替，如下:g（H）=力oy店（抵x）+bi=if(x')和g(x)里的a,y,b是一樣的，凡是要求內(nèi)積的時(shí)候就用選定的核函數(shù)來(lái)算。這樣求出來(lái)的a再和選定的核函數(shù)一組合，就得到分類器。針對(duì)具體問(wèn)題，如何選擇核函數(shù)對(duì)核函數(shù)的選擇？現(xiàn)在還缺乏指導(dǎo)原則！?引入松弛變量問(wèn)題引入：如果使用核函數(shù)向高維空間映射后，問(wèn)題仍然是線性不可分的。圓形和方形的點(diǎn)各有成千上萬(wàn)個(gè)。假如，我們有另一個(gè)訓(xùn)練集，只比原先這個(gè)訓(xùn)練集多了一篇文章，映射到高維空間以后，也就多了一個(gè)樣本點(diǎn)，但是這個(gè)樣本的位置是這樣的：圖中黃色那個(gè)點(diǎn)，它是方形的丿因而它是負(fù)類的一個(gè)樣本，這單獨(dú)的一個(gè)樣本，使得原本線性可分的問(wèn)題變成了線性不可分的。僅有少數(shù)點(diǎn)線性不可分叫做“近似線性可分”的問(wèn)題。以我們?nèi)祟惖某ＷR(shí)來(lái)判斷，說(shuō)有一萬(wàn)個(gè)點(diǎn)都符合某種規(guī)律(因而線性可分)，有一個(gè)點(diǎn)不符合，那這一個(gè)點(diǎn)是否就代表了分類規(guī)則中我們沒(méi)有考慮到的方面呢(因而規(guī)則應(yīng)該為它而做出修改)？其實(shí)更有可能的是，這個(gè)樣本點(diǎn)壓根就是錯(cuò)誤，是噪聲，是提供訓(xùn)練集的人工分類時(shí)不小心錯(cuò)放進(jìn)去的。所以我們會(huì)簡(jiǎn)單的忽略這個(gè)樣本點(diǎn)，仍然使用原來(lái)的分類器，其效果絲毫不受影響。但這種對(duì)噪聲的容錯(cuò)性是人的思維帶來(lái)的，程序可沒(méi)有。由于優(yōu)化問(wèn)題的表達(dá)式中，要考慮所有的樣本點(diǎn)，在此基礎(chǔ)上尋找正負(fù)類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負(fù)的，像上面這種有噪聲的情況會(huì)使得整個(gè)問(wèn)題無(wú)解。這種解法其實(shí)也叫做“硬間隔”分類法，因?yàn)樗残缘囊笏袠颖军c(diǎn)都滿足和分類平面間的距離必須大于某個(gè)值。因此由上面的例子中也可以看出，硬間隔的分類法其結(jié)果容易受少數(shù)點(diǎn)的控制。解決方法就是引入松弛變量，允許一些點(diǎn)到分類平面的距離不滿足原先的要求。由于不同的訓(xùn)練集各點(diǎn)的間距尺度不太一樣，因此用間隔（而不是幾何間隔）來(lái)衡量有利于我們表達(dá)形式的簡(jiǎn)潔。原先對(duì)樣本點(diǎn)的要求是：y[（wx）+b]>1（i=1,2,...,n）（n是樣本數(shù)）ii意思是離分類面最近的樣本點(diǎn)函數(shù)間隔也要比1大。如果要引入容錯(cuò)性，就給1這個(gè)硬性的閾值加一個(gè)松弛變量，即允許yi[（wxi）+b]>1-^i（i=1,2,???，n）（n為樣本數(shù)）1/1/1/:i>0因?yàn)樗沙谧兞渴欠秦?fù)的，因此最終的結(jié)果是要求間隔可以比1小。但是當(dāng)某些點(diǎn)出現(xiàn)這種間隔比1小的情況時(shí)（這些點(diǎn)也叫離群點(diǎn)），意味著放棄了對(duì)這些點(diǎn)的精確分類，而這對(duì)我們的分類器來(lái)說(shuō)是種損失。但是放棄這些點(diǎn)也帶來(lái)了好處,那就是使分類面不必向這些點(diǎn)的方向移動(dòng)，因而可以得到更大的幾何間隔（在低維空間看來(lái)，分類邊界也更平滑）。顯然我們必須權(quán)衡這種損失和好處。好處很明顯，我們得到的分類間隔越大，好處就越多?；仡櫸覀?cè)嫉挠查g隔分類對(duì)應(yīng)的優(yōu)化問(wèn)題：win i||w||2subjectto耳Ki眄）+切一40W'F）5是總的樣本數(shù)），-Iw||22""就是我們的目標(biāo)函數(shù)，越小越好，因而損失就必然是一個(gè)能使之變大的量。那如何來(lái)衡量損失，有兩種常用的方式￡匚2①i=1'

其中n都是樣本的數(shù)目。兩種方法沒(méi)有大的區(qū)別。如果選擇了第一種，得到的方法的就叫做二階軟間隔分類器，第二種就叫做一階軟間隔分類器。把損失加入到目標(biāo)函數(shù)里的時(shí)候，就需要一個(gè)懲罰因子（cost，也就是libSVM的諸多參數(shù)中的C）,原來(lái)的優(yōu)化問(wèn)題就變成了下面這樣：minminsubjecttoy[(wx)+b]>1-Q(i=1,2,...,n)(n是樣本數(shù))(式1)i i iQ>0這個(gè)式子有這么幾點(diǎn)要注意：一、 并非所有的樣本點(diǎn)都有一個(gè)松弛變量與其對(duì)應(yīng)。實(shí)際上只有“離群點(diǎn)”才有，沒(méi)離群的點(diǎn)松弛變量都等于0（對(duì)負(fù)類來(lái)說(shuō)，離群點(diǎn)就是在前面圖中，跑到H2右側(cè)的那些負(fù)樣本點(diǎn)，對(duì)正類來(lái)說(shuō)，就是跑到H1左側(cè)的那些正樣本點(diǎn)）。二、 松弛變量的值實(shí)際上標(biāo)示出了對(duì)應(yīng)的點(diǎn)到底離群有多遠(yuǎn)，值越大，點(diǎn)就越遠(yuǎn)。三、 懲罰因子C決定了你有多重視離群點(diǎn)帶來(lái)的損失，顯然當(dāng)所有離群點(diǎn)的松弛變量的和一定時(shí)，C越大，對(duì)目標(biāo)函數(shù)的損失也越大，此時(shí)就表示非常不愿意放棄這些離群點(diǎn)，最極端的情況是把C定為無(wú)限大，這樣只要稍有一個(gè)點(diǎn)離群，目標(biāo)函數(shù)的值變成無(wú)限大，讓問(wèn)題變成無(wú)解，這就退化成了硬間隔問(wèn)題。四、 懲罰因子C不是一個(gè)變量，整個(gè)優(yōu)化問(wèn)題在解的時(shí)候，C是一個(gè)你必須事先指定的值，指定這個(gè)值以后，解一下，得到一個(gè)分類器，然后用測(cè)試數(shù)據(jù)看看結(jié)果怎么樣，如果不夠好，換一個(gè)C的值，再解一次優(yōu)化問(wèn)題，得到另一個(gè)分類器，再看看效果，如此就是一個(gè)參數(shù)尋優(yōu)的過(guò)程，但這和優(yōu)化問(wèn)題本身決不是一回事，優(yōu)化問(wèn)題在解的過(guò)程中，C一直是定值。五、 盡管加了松弛變量，解它的過(guò)程比起原始的硬間隔問(wèn)題來(lái)說(shuō)是一樣的。從大的方面說(shuō)優(yōu)化問(wèn)題解的過(guò)程，就是先試著確定一下w，也就是確定了前面圖中的三條直線，這時(shí)看看間隔有多大，又有多少點(diǎn)離群，把目標(biāo)函數(shù)的值算一算，再換一組三條直線，再把目標(biāo)函數(shù)的值算一算，如此往復(fù)（迭代），直到最終找到目標(biāo)函數(shù)最小時(shí)的w。松弛變量和核函數(shù)的引入都是為了解決線性不可分的問(wèn)題。松弛變量進(jìn)一步解決線性不可分問(wèn)題。以文本分類為例。在原始的低維空間中，樣本相當(dāng)?shù)牟豢煞?，無(wú)論你怎么找分類平面，總會(huì)有大量的離群點(diǎn)，此時(shí)用核函數(shù)向高維空間映射一下，雖然結(jié)果仍然是不可分的，但比原始空間里的要更加接近線性可分的狀態(tài)（即達(dá)到了近似線性可分的狀態(tài)），此時(shí)再用松弛變量處理那些少數(shù)的離群點(diǎn)，就簡(jiǎn)單有效得多了。本節(jié)中的（式1）是支持向量機(jī)最最常用的形式。至此一個(gè)比較完整的支持向量機(jī)框架就有了。簡(jiǎn)單說(shuō)來(lái)，支持向量機(jī)就是使用了核函數(shù)的軟間隔線性分類法。?SVM用于多類分類SVM是一種典型的兩類分類器，即它只回答屬于正類還是負(fù)類的問(wèn)題。而現(xiàn)實(shí)中要解決的問(wèn)題，往往是多類的問(wèn)題（少部分例外，例如垃圾郵件過(guò)濾，就只需要確定“是”還是“不是”垃圾郵件），比如文本分類，比如數(shù)字識(shí)別。如何由兩類分類器得到多類分類器，在此有三種方法。以文本分類為例，現(xiàn)成的方法有很多，其中最好就是一次性考慮所有樣本，次性求解的方法計(jì)算量實(shí)在太大，基本實(shí)現(xiàn)不了。①一類對(duì)其余的方法，就是每次仍然解一個(gè)兩類分類的問(wèn)題。比如我們有5個(gè)類別，第一次就把類別1的樣本定為正樣本，其余2,3,4,5的樣本合起來(lái)定為負(fù)樣本，這樣得到一個(gè)兩類分類器，它能夠指出一篇文章是還是不是第1類的；第二次我們把類別2的樣本定為正樣本，把1，3,4,5的樣本合起來(lái)定為負(fù)樣本，得到一個(gè)分類器，如此下去，我們可以得到5個(gè)這樣的兩類分類器（總是和類別的數(shù)目一致）。文章分類時(shí)，挨個(gè)分類器進(jìn)行分類，最終確定文章的類別。這種方法的好處是每個(gè)優(yōu)化問(wèn)題的規(guī)模比較小，而且分類的時(shí)候速度很快（只需要調(diào)用5個(gè)分類器就知道了結(jié)果）。但有時(shí)也會(huì)出現(xiàn)兩種很尷尬的情況，

例如拿一篇文章問(wèn)了一圈，每一個(gè)分類器都說(shuō)它是屬于它那一類的，或者每一個(gè)分類器都說(shuō)它不是它那一類的，前者叫分類重疊現(xiàn)象，后者叫不可分類現(xiàn)象。分類重疊時(shí)隨便選一個(gè)結(jié)果都可，或者看看這篇文章到各個(gè)超平面的距離，哪個(gè)遠(yuǎn)就判給哪個(gè)。不可分類時(shí)很難解決，由于各個(gè)類別的樣本數(shù)目是差不多的，但“其余”的那一類樣本數(shù)總是要數(shù)倍于正類，這就人為的造成了“數(shù)據(jù)集偏斜”問(wèn)題。一對(duì)一的方法，還是解兩類分類問(wèn)題，還是每次選一個(gè)類的樣本作正類樣本，而負(fù)類樣本則變成只選一個(gè)類，這就避免了偏斜。過(guò)程就是算出這樣一些分類器，第一個(gè)只回答“是第1類還是第2類”，第二個(gè)只回答“是第1類還是第3類”，第三個(gè)只回答“是第1類還是第4類”，如此下去。這樣的分類器應(yīng)該有5X4/2=10個(gè)（通式是，如果有k個(gè)類別，則總的兩類分類器數(shù)目為k（k-1）/2）。