【正文】 這樣再回頭看就會(huì)明白為什么一對(duì)一方法盡管要訓(xùn)練的兩類分類器數(shù)量多，但總時(shí)間實(shí)際上比一對(duì)其余方法要少了，因?yàn)橐粚?duì)其余方法每次訓(xùn)練都考 慮了所有樣本（只是每次把不同的部分劃分為正類或者負(fù)類而已），自然慢上很多。 一個(gè)具體的算法，BunchKaufman訓(xùn)練算法，典型的時(shí)間復(fù)雜度在O(Nsv3+LNsv2+dLNsv) 和O(dL2)之間，其中Nsv是支持向量的個(gè)數(shù)，L是訓(xùn)練集樣本的個(gè)數(shù)，d是每個(gè)樣本的維數(shù)（原始的維 數(shù)，沒有經(jīng)過向高維空間映射之前的維數(shù)）。求數(shù)值解的過程非常像窮舉法，從一個(gè)數(shù)開始，試一試它當(dāng)解效果怎樣，不滿足一定 條件（叫做停機(jī)條件，就是滿足這個(gè)以后就認(rèn)為解足夠精確了，不需要繼續(xù)算下去了）就試下一個(gè)，當(dāng)然下一個(gè)數(shù)不是亂選的，也有一定章法可循。對(duì)SVM來說，求得解析解的時(shí)間復(fù)雜度最壞可以達(dá)到O(Nsv3)， 其中Nsv是支持向量的個(gè)數(shù)，而雖然沒有固定的比例，但支持向量的個(gè)數(shù)多少也和訓(xùn)練集的大小有關(guān)。 解析解就是理論上的解，它的形式是表達(dá)式，因此它是精確的，一個(gè)問題只要有解（無解的問題還跟著摻和什么呀，哈哈），那它的解析解是一定存 在的。 大Tips：SVM的計(jì)算復(fù)雜度 使用SVM進(jìn)行分類的時(shí)候，實(shí)際上是訓(xùn)練和分類兩個(gè)完全不同的過程，因而討論復(fù)雜度就不能一概而論，我們這里所說的主要是訓(xùn)練階段的復(fù)雜 度，即解那個(gè)二次規(guī)劃問題的復(fù)雜度。而一對(duì)其余和一對(duì)一方法中，盡管每一個(gè)兩類分類器的泛化誤差限是知道的，但是合起來做多類分類的時(shí)候，誤差上界是多少， 沒人知道，這意味著準(zhǔn)確率低到0也是有可能的，這多讓人郁悶。好處在哪？我們其實(shí)只調(diào)用了4個(gè)分類器（如果類別數(shù)是k，則只 調(diào)用k1個(gè)），分類速度飛快，且沒有分類重疊和不可分類現(xiàn)象！缺點(diǎn)在哪？假如最一開始的分類器回答錯(cuò)誤（明明是類別1的文章，它說成了5），那么后面的 分類器是無論如何也無法糾正它的錯(cuò)誤的（因?yàn)楹竺娴姆诸惼鲏焊鶝]有出現(xiàn)“1”這個(gè)類別標(biāo)簽），其實(shí)對(duì)下面每一層的分類器都存在這種錯(cuò)誤向下累積的現(xiàn)象?？雌饋韷蚝妹?？其實(shí)不然，想想分類一篇文章，我們調(diào)用了多少個(gè)分類器？10個(gè)，這還是 類別數(shù)為5的時(shí)候，類別數(shù)如果是1000，要調(diào)用的分類器數(shù)目會(huì)上升至約500,000個(gè)（類別數(shù)的平方量級(jí)）。雖然分類器的數(shù)目多了，但是在訓(xùn)練階段（也就是算出這些分類器的分 類平面時(shí)）所用的總時(shí)間卻比“一類對(duì)其余”方法少很多，在真正用來分類的時(shí)候，把一篇文章扔給所有分類器，第一個(gè)分類器會(huì)投票說它是“1”或者“2”，第 二個(gè)會(huì)說它是“1”或者“3”，讓每一個(gè)都投上自己的一票，最后統(tǒng)計(jì)票數(shù)，如果類別“1”得票最多，就判這篇文章屬于第1類。 因此我們還得再退一步，還是解兩類分類問題，還是每次選一個(gè)類的樣本作正類樣本，而負(fù)類樣本則變成只選一個(gè)類（稱為“一對(duì)一單挑”的方法， 哦，不對(duì)，沒有單挑，就是“一對(duì)一”的方法，呵呵），這就避免了偏斜。分類重疊倒還好辦，隨便選一個(gè)結(jié)果 都不至于太離譜，或者看看這篇文章到各個(gè)超平面的距離，哪個(gè)遠(yuǎn)就判給哪個(gè)。這種方法的好處是 每個(gè)優(yōu)化問題的規(guī)模比較小，而且分類的時(shí)候速度很快（只需要調(diào)用5個(gè)分類器就知道了結(jié)果）。比如我們有5個(gè)類別，第一次就把類別1的樣本定為 正樣本，其余2，3，4，5的樣本合起來定為負(fù)樣本，這樣得到一個(gè)兩類分類器，它能夠指出一篇文章是還是不是第1類的；第二次我們把類別2 的樣本定為正樣本，把1，3，4，5的樣本合起來定為負(fù)樣本，得到一個(gè)分類器，如此下去，我們可以得到5個(gè)這樣的兩類分類器（總是和類別的數(shù)目一致）。 看起來很美對(duì)不對(duì)？只可惜這種算法還基本停留在紙面上，因?yàn)橐淮涡郧蠼獾姆椒ㄓ?jì)算量實(shí)在太大，大到無法實(shí)用的地步。如何由兩類分類器得到多類分類器，就是一個(gè)值得研究的問題。 SVM入門（十）將SVM用于多類分類從 SVM的那幾張圖可以看出來，SVM是一種典型的兩類分類器，即它只回答屬于正類還是負(fù)類的問題。 但是這 樣還不夠好，因?yàn)橛械念悇e樣本確實(shí)很集中，這不是提供的樣本數(shù)量多少的問題，這是類別本身的特征（就是某些話題涉及的面很窄，例如計(jì)算機(jī)類的文章就明顯不 如文化類的文章那么“天馬行空”），這個(gè)時(shí)候即便超球的半徑差異很大，也不應(yīng)該賦予兩個(gè)類別不同的懲罰因子。比如可以算算他們?cè)诳臻g中占據(jù)了多大的體積，例如給負(fù)類找一個(gè)超球——就是高維空間里的球啦——它可以包含所 有負(fù)類的樣本，再給正類找一個(gè)，比比兩個(gè)球的半徑，就可以大致確定分布的情況。 但是這樣并不夠好，回看剛才的圖，你會(huì)發(fā)現(xiàn)正類之所以可以“欺負(fù)”負(fù)類，其實(shí)并不是因?yàn)樨?fù)類樣本 少，真實(shí)的原因是負(fù)類的樣本分布的不夠廣（沒擴(kuò)充到負(fù)類本應(yīng)該有的區(qū)域）。 那C+和C怎 么確定呢？它們的大小是試出來的（參數(shù)調(diào)優(yōu)），但是他們的比例可以有些方法來確定。其中i=1…p都是正樣 本，j=p+1…p+q都是負(fù)樣本。但現(xiàn)在由于偏斜的現(xiàn)象存在，使得數(shù)量多的正類可以把分類面向負(fù)類的方向“推”，因而影響 了結(jié)果的準(zhǔn)確性。比如說正類有10，000個(gè)樣本，而負(fù)類只給了100 個(gè)，這會(huì)引起的問題顯而易見，可以看看下面的圖：方形的點(diǎn)是負(fù)類。 當(dāng) 然實(shí)際使用的時(shí)候并沒有這么極端，但一種很常用的變形可以用來解決分類問題中樣本的“偏斜”問題?；仡^看一眼引入了松弛 變量以后的優(yōu)化問題：注意其中C的位置，也可 以回想一下C所起的作用（表征你有多么重視離群點(diǎn)，C越大越重視，越不想丟掉它們）。 下一節(jié)會(huì)說說松弛變量剩下的一點(diǎn)點(diǎn)東西，順便搞個(gè)讀者調(diào)查，看看大家還想侃侃SVM的哪些方面。 本節(jié)中的（式1）也確實(shí)是支持向量機(jī)最最常用的形式。一般的過程應(yīng)該是這樣，還以文本分類為例。 從大的方面說優(yōu)化問題解的過程，就是先試著確定一下w，也就是確定了前面圖中的三條直線，這時(shí)看看間隔有多大，又有多少點(diǎn)離群，把目標(biāo)函數(shù)的值算一 算，再換一組三條直線（你可以看到，分類的直線位置如果移動(dòng)了，有些原來離群的點(diǎn)會(huì)變得不再離群，而有的本來不離群的點(diǎn)會(huì)變成離群點(diǎn)），再把目標(biāo)函數(shù)的值 算一算，如此往復(fù)（迭代），直到最終找到目標(biāo)函數(shù)最小時(shí)的w。 四是懲罰因子C不是一個(gè)變量，整個(gè)優(yōu)化問題在解的時(shí) 候，C是一個(gè)你必須事先指定的值，指定這個(gè)值以后，解一下，得到一個(gè)分類器，然后用測(cè)試數(shù)據(jù)看看結(jié)果怎么樣，如果不夠好，換一個(gè)C的值，再解一次優(yōu)化問 題，得到另一個(gè)分類器，再看看效果，如此就是一個(gè)參數(shù)尋優(yōu)的過程，但這和優(yōu)化問題本身決不是一回事，優(yōu)化問題在解的過程中，C一直是定值，要記住。 二是松弛變量的值實(shí)際上標(biāo)示出了對(duì)應(yīng)的點(diǎn)到底離群有多遠(yuǎn)，值越大，點(diǎn)就越遠(yuǎn)。把損失加入 到目標(biāo)函數(shù)里的時(shí)候，就需要一個(gè)懲罰因子（cost，也 就是libSVM的諸多參數(shù)中的C），原來的優(yōu)化問題就變成了下面這樣：這個(gè)式子有這么幾點(diǎn)要注意： 一是并非所有的樣本點(diǎn)都有一個(gè)松弛變量與其對(duì)應(yīng)。兩種方法沒有大的區(qū)別?；仡櫸覀?cè)嫉挠查g隔分類對(duì)應(yīng)的 優(yōu)化問題：||w||2就是我們的目標(biāo)函數(shù)（當(dāng)然系數(shù)可有可無），希望它越小越好，因而損失就必然是一個(gè)能使之變大的量（能使它變小就 不叫損失了，我們本來就希望目標(biāo)函數(shù)值越小越好）。顯然我們必須權(quán)衡這種損失和好處。但是當(dāng)某些點(diǎn)出現(xiàn)這種間隔比1小的情況時(shí)（這些點(diǎn)也叫離群點(diǎn)），意味著我們放棄了對(duì)這 些點(diǎn)的精確分類，而這對(duì)我們的分類器來說是種損失。意思是說離分類面最近的樣本點(diǎn)函數(shù)間隔也要比1大。由于不同的訓(xùn)練集各點(diǎn)的間距尺度不太一樣，因此用間隔（而不 是幾何間隔）來衡量有利于我們表達(dá)形式的簡(jiǎn)潔。 因此由上面的例子中也可以看出，硬間隔的分類法其結(jié)果容易受少數(shù)點(diǎn)的控制，這是很危險(xiǎn)的（盡管有句話說真理總是掌握在少數(shù)人手中，但那不過是那一小撮人聊以自慰的詞句罷了，咱還是得民主）。由于我們?cè)镜膬?yōu)化問題的表達(dá)式中，確實(shí)要考慮所有的樣本點(diǎn)（不能忽略某一個(gè)，因?yàn)槌绦?它怎么知道該忽略哪一個(gè)呢？），在此基礎(chǔ)上尋找正負(fù)類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負(fù)的，像上面這種有噪聲的情況會(huì)使得整個(gè)問題 無解。所以我們會(huì)簡(jiǎn)單的忽略這個(gè)樣本 點(diǎn)，仍然使用原來的分類器，其效果絲毫不受影響。這樣類似的問題（僅有少 數(shù)點(diǎn)線性不可分）叫做“近似線性可分”的問題?，F(xiàn)在想象我們有另一個(gè)訓(xùn)練集，只比原先這個(gè)訓(xùn)練集多了一篇文 章，映射到高維空間以后（當(dāng)然，也使用了相同的核函數(shù)），也就多了一個(gè)樣本點(diǎn)，但是這個(gè)樣本的位置是這樣的：就像下圖這樣： SVM入門（八）松弛變量 （我做文本分類系統(tǒng)的時(shí)候，使用徑向基核函數(shù)，沒有參數(shù)調(diào)優(yōu)的情況下，絕 大部分類別的準(zhǔn)確和召回都在85%以上，可見。 回想我們上節(jié)說的求一個(gè)線性分類器，它的形式應(yīng)該是： 現(xiàn)在這個(gè)就是高維空間里的線性函數(shù)（為了區(qū)別低維和高維空間里的函數(shù)和向量，我改了函數(shù)的名字，并且給w和x都加上了 ’），我們就可以用一個(gè)低維空間里的函數(shù)（再一次的，這個(gè)低維空間里的函數(shù)就不再是線性的啦）來代替， 又發(fā)現(xiàn)什么了？f(x’) 和g(x)里的α，y，b全都是一樣一樣的！這就是說，盡管給的問題是線性不可分的，但是我們就硬當(dāng)它是線性問題來求解，只不過求解過程中，凡是要求內(nèi)積 的時(shí)候就用你選定的核函數(shù)來算。核函數(shù)的基本作用就是接受兩個(gè)低維空間里的向量，能夠計(jì)算出經(jīng)過某個(gè)變換后在高維空間里的向量內(nèi)積值。這讓我們幻想，是否能有這樣一種函數(shù)K(w,x),他接受低維空間的 輸入值，卻能算出高維空間的內(nèi)積值w’,x’？ 如果有這樣的函數(shù)，那么當(dāng)給了一個(gè)低維空間的輸入x以后， g(x)=K(w,x)+bf(x’)=w’,x’+b這兩個(gè)函數(shù)的計(jì)算結(jié)果就完全一樣，我們也就用不著費(fèi)力找那個(gè)映