從 SVM的那幾張圖可以看出來(lái)，SVM是一種典型的兩類(lèi)分類(lèi)器，即它只回答屬于正類(lèi)還是負(fù)類(lèi)的問(wèn)題。而現(xiàn)實(shí)中要解決的問(wèn)題，往往是多類(lèi)的問(wèn)題（少部分例外，例如垃圾郵件過(guò)濾，就只需要確定“是”還是“不是”垃圾郵件），比如文本分類(lèi)，比如數(shù)字識(shí)別。如何由兩類(lèi)分類(lèi)器得到多類(lèi)分類(lèi)器，就是一個(gè)值得研究的問(wèn)題。

還以文本分類(lèi)為例，現(xiàn)成的方法有很多，其中一種一勞永逸的方法，就是真的一次性考慮所有樣本，并求解一個(gè)多目標(biāo)函數(shù)的優(yōu)化問(wèn)題，一次性得到多個(gè)分類(lèi)面，就像下圖這樣：

clip_image001

多個(gè)超平面把空間劃分為多個(gè)區(qū)域，每個(gè)區(qū)域?qū)?yīng)一個(gè)類(lèi)別，給一篇文章，看它落在哪個(gè)區(qū)域就知道了它的分類(lèi)。

看起來(lái)很美對(duì)不對(duì)？只可惜這種算法還基本停留在紙面上，因?yàn)橐淮涡郧蠼獾姆椒ㄓ?jì)算量實(shí)在太大，大到無(wú)法實(shí)用的地步。

稍稍退一步，我們就會(huì)想到所謂“一類(lèi)對(duì)其余”的方法，就是每次仍然解一個(gè)兩類(lèi)分類(lèi)的問(wèn)題。比如我們有5個(gè)類(lèi)別，第一次就把類(lèi)別1的樣本定為正樣本，其余2，3，4，5的樣本合起來(lái)定為負(fù)樣本，這樣得到一個(gè)兩類(lèi)分類(lèi)器，它能夠指出一篇文章是還是不是第1類(lèi)的；第二次我們把類(lèi)別2 的樣本定為正樣本，把1，3，4，5的樣本合起來(lái)定為負(fù)樣本，得到一個(gè)分類(lèi)器，如此下去，我們可以得到5個(gè)這樣的兩類(lèi)分類(lèi)器（總是和類(lèi)別的數(shù)目一致）。到了有文章需要分類(lèi)的時(shí)候，我們就拿著這篇文章挨個(gè)分類(lèi)器的問(wèn)：是屬于你的么？是屬于你的么？哪個(gè)分類(lèi)器點(diǎn)頭說(shuō)是了，文章的類(lèi)別就確定了。這種方法的好處是每個(gè)優(yōu)化問(wèn)題的規(guī)模比較小，而且分類(lèi)的時(shí)候速度很快（只需要調(diào)用5個(gè)分類(lèi)器就知道了結(jié)果）。但有時(shí)也會(huì)出現(xiàn)兩種很尷尬的情況，例如拿一篇文章問(wèn)了一圈，每一個(gè)分類(lèi)器都說(shuō)它是屬于它那一類(lèi)的，或者每一個(gè)分類(lèi)器都說(shuō)它不是它那一類(lèi)的，前者叫分類(lèi)重疊現(xiàn)象，后者叫不可分類(lèi)現(xiàn)象。分類(lèi)重疊倒還好辦，隨便選一個(gè)結(jié)果都不至于太離譜，或者看看這篇文章到各個(gè)超平面的距離，哪個(gè)遠(yuǎn)就判給哪個(gè)。不可分類(lèi)現(xiàn)象就著實(shí)難辦了，只能把它分給第6個(gè)類(lèi)別了……更要命的是，本來(lái)各個(gè)類(lèi)別的樣本數(shù)目是差不多的，但“其余”的那一類(lèi)樣本數(shù)總是要數(shù)倍于正類(lèi)（因?yàn)樗浅?lèi)以外其他類(lèi)別的樣本之和嘛），這就人為的造成了上一節(jié)所說(shuō)的“數(shù)據(jù)集偏斜”問(wèn)題。

因此我們還得再退一步，還是解兩類(lèi)分類(lèi)問(wèn)題，還是每次選一個(gè)類(lèi)的樣本作正類(lèi)樣本，而負(fù)類(lèi)樣本則變成只選一個(gè)類(lèi)（稱(chēng)為“一對(duì)一單挑”的方法，哦，不對(duì)，沒(méi)有單挑，就是“一對(duì)一”的方法，呵呵），這就避免了偏斜。因此過(guò)程就是算出這樣一些分類(lèi)器，第一個(gè)只回答“是第1類(lèi)還是第2類(lèi)”，第二個(gè)只回答“是第1類(lèi)還是第3類(lèi)”，第三個(gè)只回答“是第1類(lèi)還是第4類(lèi)”，如此下去，你也可以馬上得出，這樣的分類(lèi)器應(yīng)該有5 X 4/2=10個(gè)（通式是，如果有k個(gè)類(lèi)別，則總的兩類(lèi)分類(lèi)器數(shù)目為k(k-1)/2）。雖然分類(lèi)器的數(shù)目多了，但是在訓(xùn)練階段（也就是算出這些分類(lèi)器的分類(lèi)平面時(shí)）所用的總時(shí)間卻比“一類(lèi)對(duì)其余”方法少很多，在真正用來(lái)分類(lèi)的時(shí)候，把一篇文章扔給所有分類(lèi)器，第一個(gè)分類(lèi)器會(huì)投票說(shuō)它是“1”或者“2”，第二個(gè)會(huì)說(shuō)它是“1”或者“3”，讓每一個(gè)都投上自己的一票，最后統(tǒng)計(jì)票數(shù)，如果類(lèi)別“1”得票最多，就判這篇文章屬于第1類(lèi)。這種方法顯然也會(huì)有分類(lèi)重疊的現(xiàn)象，但不會(huì)有不可分類(lèi)現(xiàn)象，因?yàn)榭偛豢赡芩蓄?lèi)別的票數(shù)都是0。看起來(lái)夠好么？其實(shí)不然，想想分類(lèi)一篇文章，我們調(diào)用了多少個(gè)分類(lèi)器？10個(gè)，這還是類(lèi)別數(shù)為5的時(shí)候，類(lèi)別數(shù)如果是1000，要調(diào)用的分類(lèi)器數(shù)目會(huì)上升至約500,000個(gè)（類(lèi)別數(shù)的平方量級(jí)）。這如何是好？

看來(lái)我們必須再退一步，在分類(lèi)的時(shí)候下功夫，我們還是像一對(duì)一方法那樣來(lái)訓(xùn)練，只是在對(duì)一篇文章進(jìn)行分類(lèi)之前，我們先按照下面圖的樣子來(lái)組織分類(lèi)器（如你所見(jiàn)，這是一個(gè)有向無(wú)環(huán)圖，因此這種方法也叫做DAG SVM）

clip_image002

這樣在分類(lèi)時(shí),我們就可以先問(wèn)分類(lèi)器“1對(duì)5”（意思是它能夠回答“是第1類(lèi)還是第5類(lèi)”），如果它回答5，我們就往左走，再問(wèn)“2對(duì)5”這個(gè)分類(lèi)器，如果它還說(shuō)是“5”，我們就繼續(xù)往左走，這樣一直問(wèn)下去，就可以得到分類(lèi)結(jié)果。好處在哪？我們其實(shí)只調(diào)用了4個(gè)分類(lèi)器（如果類(lèi)別數(shù)是k，則只調(diào)用k-1個(gè)），分類(lèi)速度飛快，且沒(méi)有分類(lèi)重疊和不可分類(lèi)現(xiàn)象！缺點(diǎn)在哪？假如最一開(kāi)始的分類(lèi)器回答錯(cuò)誤（明明是類(lèi)別1的文章，它說(shuō)成了5），那么后面的分類(lèi)器是無(wú)論如何也無(wú)法糾正它的錯(cuò)誤的（因?yàn)楹竺娴姆诸?lèi)器壓根沒(méi)有出現(xiàn)“1”這個(gè)類(lèi)別標(biāo)簽），其實(shí)對(duì)下面每一層的分類(lèi)器都存在這種錯(cuò)誤向下累積的現(xiàn)象。。

不過(guò)不要被DAG方法的錯(cuò)誤累積嚇倒，錯(cuò)誤累積在一對(duì)其余和一對(duì)一方法中也都存在，DAG方法好于它們的地方就在于，累積的上限，不管是大是小，總是有定論的，有理論證明。而一對(duì)其余和一對(duì)一方法中，盡管每一個(gè)兩類(lèi)分類(lèi)器的泛化誤差限是知道的，但是合起來(lái)做多類(lèi)分類(lèi)的時(shí)候，誤差上界是多少，沒(méi)人知道，這意味著準(zhǔn)確率低到0也是有可能的，這多讓人郁悶。

而且現(xiàn)在DAG方法根節(jié)點(diǎn)的選取（也就是如何選第一個(gè)參與分類(lèi)的分類(lèi)器），也有一些方法可以改善整體效果，我們總希望根節(jié)點(diǎn)少犯錯(cuò)誤為好，因此參與第一次分類(lèi)的兩個(gè)類(lèi)別，最好是差別特別特別大，大到以至于不太可能把他們分錯(cuò)；或者我們就總?cè)≡趦深?lèi)分類(lèi)中正確率最高的那個(gè)分類(lèi)器作根節(jié)點(diǎn)，或者我們讓兩類(lèi)分類(lèi)器在分類(lèi)的時(shí)候，不光輸出類(lèi)別的標(biāo)簽，還輸出一個(gè)類(lèi)似“置信度”的東東，當(dāng)它對(duì)自己的結(jié)果不太自信的時(shí)候，我們就不光按照它的輸出走，把它旁邊的那條路也走一走，等等。

大Tips：SVM的計(jì)算復(fù)雜度

使用SVM進(jìn)行分類(lèi)的時(shí)候，實(shí)際上是訓(xùn)練和分類(lèi)兩個(gè)完全不同的過(guò)程，因而討論復(fù)雜度就不能一概而論，我們這里所說(shuō)的主要是訓(xùn)練階段的復(fù)雜度，即解那個(gè)二次規(guī)劃問(wèn)題的復(fù)雜度。對(duì)這個(gè)問(wèn)題的解，基本上要?jiǎng)澐譃閮纱髩K，解析解和數(shù)值解。

解析解就是理論上的解，它的形式是表達(dá)式，因此它是精確的，一個(gè)問(wèn)題只要有解（無(wú)解的問(wèn)題還跟著摻和什么呀，哈哈），那它的解析解是一定存在的。當(dāng)然存在是一回事，能夠解出來(lái)，或者可以在可以承受的時(shí)間范圍內(nèi)解出來(lái)，就是另一回事了。對(duì)SVM來(lái)說(shuō)，求得解析解的時(shí)間復(fù)雜度最壞可以達(dá)到O(Nsv3)，其中Nsv是支持向量的個(gè)數(shù)，而雖然沒(méi)有固定的比例，但支持向量的個(gè)數(shù)多少也和訓(xùn)練集的大小有關(guān)。

數(shù)值解就是可以使用的解，是一個(gè)一個(gè)的數(shù)，往往都是近似解。求數(shù)值解的過(guò)程非常像窮舉法，從一個(gè)數(shù)開(kāi)始，試一試它當(dāng)解效果怎樣，不滿足一定條件（叫做停機(jī)條件，就是滿足這個(gè)以后就認(rèn)為解足夠精確了，不需要繼續(xù)算下去了）就試下一個(gè)，當(dāng)然下一個(gè)數(shù)不是亂選的，也有一定章法可循。有的算法，每次只嘗試一個(gè)數(shù)，有的就嘗試多個(gè)，而且找下一個(gè)數(shù)字（或下一組數(shù)）的方法也各不相同，停機(jī)條件也各不相同，最終得到的解精度也各不相同，可見(jiàn)對(duì)求數(shù)值解的復(fù)雜度的討論不能脫開(kāi)具體的算法。

一個(gè)具體的算法，Bunch-Kaufman訓(xùn)練算法，典型的時(shí)間復(fù)雜度在O(Nsv3+LNsv2+dLNsv)和O(dL2)之間，其中Nsv是支持向量的個(gè)數(shù)，L是訓(xùn)練集樣本的個(gè)數(shù)，d是每個(gè)樣本的維數(shù)（原始的維數(shù)，沒(méi)有經(jīng)過(guò)向高維空間映射之前的維數(shù)）。復(fù)雜度會(huì)有變化，是因?yàn)樗还飧斎雴?wèn)題的規(guī)模有關(guān)（不光和樣本的數(shù)量，維數(shù)有關(guān)），也和問(wèn)題最終的解有關(guān)（即支持向量有關(guān)），如果支持向量比較少，過(guò)程會(huì)快很多，如果支持向量很多，接近于樣本的數(shù)量，就會(huì)產(chǎn)生O(dL2)這個(gè)十分糟糕的結(jié)果（給10，000個(gè)樣本，每個(gè)樣本1000維，基本就不用算了，算不出來(lái)，呵呵，而這種輸入規(guī)模對(duì)文本分類(lèi)來(lái)說(shuō)太正常了）。

這樣再回頭看就會(huì)明白為什么一對(duì)一方法盡管要訓(xùn)練的兩類(lèi)分類(lèi)器數(shù)量多，但總時(shí)間實(shí)際上比一對(duì)其余方法要少了，因?yàn)橐粚?duì)其余方法每次訓(xùn)練都考慮了所有樣本（只是每次把不同的部分劃分為正類(lèi)或者負(fù)類(lèi)而已），自然慢上很多。