網(wǎng)店的Logo。那大腿不是別人的，正是韓國歌星寶兒……

她跟我說上面這張圖最大的問題就在于太有夜店風(fēng)格，與她的店不符。不過用著用著，她自己倒也喜歡上了。

這個是剛出爐的5月新款的預(yù)告，照片里的人可全是她……

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

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

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

看起來很美對不對？只可惜這種算法還基本停留在紙面上，因為一次性求解的方法計算量實在太大，大到無法實用的地步。

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

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

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

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

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

而且現(xiàn)在DAG方法根節(jié)點的選?。ㄒ簿褪侨绾芜x第一個參與分類的分類器），也有一些方法可以改善整體效果，我們總希望根節(jié)點少犯錯誤為好，因此參與第一次分類的兩個類別，最好是差別特別特別大，大到以至于不太可能把他們分錯；或者我們就總?cè)≡趦深惙诸愔姓_率最高的那個分類器作根節(jié)點，或者我們讓兩類分類器在分類的時候，不光輸出類別的標(biāo)簽，還輸出一個類似“置信度”的東東，當(dāng)它對自己的結(jié)果不太自信的時候，我們就不光按照它的輸出走，把它旁邊的那條路也走一走，等等。

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

使用SVM進(jìn)行分類的時候，實際上是訓(xùn)練和分類兩個完全不同的過程，因而討論復(fù)雜度就不能一概而論，我們這里所說的主要是訓(xùn)練階段的復(fù)雜度，即解那個二次規(guī)劃問題的復(fù)雜度。對這個問題的解，基本上要劃分為兩大塊，解析解和數(shù)值解。

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

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

一個具體的算法，Bunch-Kaufman訓(xùn)練算法，典型的時間復(fù)雜度在O(N_sv³+LN_sv²+dLN_sv)和O(dL²)之間，其中N_sv是支持向量的個數(shù)，L是訓(xùn)練集樣本的個數(shù)，d是每個樣本的維數(shù)（原始的維數(shù)，沒有經(jīng)過向高維空間映射之前的維數(shù)）。復(fù)雜度會有變化，是因為它不光跟輸入問題的規(guī)模有關(guān)（不光和樣本的數(shù)量，維數(shù)有關(guān)），也和問題最終的解有關(guān)（即支持向量有關(guān)），如果支持向量比較少，過程會快很多，如果支持向量很多，接近于樣本的數(shù)量，就會產(chǎn)生O(dL²)這個十分糟糕的結(jié)果（給10，000個樣本，每個樣本1000維，基本就不用算了，算不出來，呵呵，而這種輸入規(guī)模對文本分類來說太正常了）。

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

前文提到過，除了開方檢驗（CHI）以外，信息增益（IG，Information Gain）也是很有效的特征選擇方法。但凡是特征選擇，總是在將特征的重要程度量化之后再進(jìn)行選擇，而如何量化特征的重要性，就成了各種方法間最大的不同。開方檢驗中使用特征與類別間的關(guān)聯(lián)性來進(jìn)行這個量化，關(guān)聯(lián)性越強(qiáng)，特征得分越高，該特征越應(yīng)該被保留。

在信息增益中，重要性的衡量標(biāo)準(zhǔn)就是看特征能夠為分類系統(tǒng)帶來多少信息，帶來的信息越多，該特征越重要。

因此先回憶一下信息論中有關(guān)信息量（就是“熵”）的定義。說有這么一個變量X，它可能的取值有n多種，分別是x₁，x₂，……，x_n，每一種取到的概率分別是P₁，P₂，……，P_n，那么X的熵就定義為：

意思就是一個變量可能的變化越多（反而跟變量具體的取值沒有任何關(guān)系，只和值的種類多少以及發(fā)生概率有關(guān)），它攜帶的信息量就越大（因此我一直覺得我們的政策法規(guī)信息量非常大，因為它變化很多，基本朝令夕改，笑）。

對分類系統(tǒng)來說，類別C是變量，它可能的取值是C₁，C₂，……，C_n，而每一個類別出現(xiàn)的概率是P(C₁)，P(C₂)，……，P(C_n)，因此n就是類別的總數(shù)。此時分類系統(tǒng)的熵就可以表示為：

有同學(xué)說不好理解呀，這樣想就好了，文本分類系統(tǒng)的作用就是輸出一個表示文本屬于哪個類別的值，而這個值可能是C₁，C₂，……，C_n，因此這個值所攜帶的信息量就是上式中的這么多。

信息增益是針對一個一個的特征而言的，就是看一個特征t，系統(tǒng)有它和沒它的時候信息量各是多少，兩者的差值就是這個特征給系統(tǒng)帶來的信息量，即增益。系統(tǒng)含有特征t的時候信息量很好計算，就是剛才的式子，它表示的是包含所有特征時系統(tǒng)的信息量。

問題是當(dāng)系統(tǒng)不包含t時，信息量如何計算？我們換個角度想問題，把系統(tǒng)要做的事情想象成這樣：說教室里有很多座位，學(xué)生們每次上課進(jìn)來的時候可以隨便坐，因而變化是很大的（無數(shù)種可能的座次情況）；但是現(xiàn)在有一個座位，看黑板很清楚，聽老師講也很清楚，于是校長的小舅子的姐姐的女兒托關(guān)系（真輾轉(zhuǎn)?。堰@個座位定下來了，每次只能給她坐，別人不行，此時情況怎樣？對于座次的可能情況來說，我們很容易看出以下兩種情況是等價的：（1）教室里沒有這個座位；（2）教室里雖然有這個座位，但其他人不能坐（因為反正它也不能參與到變化中來，它是不變的）。

對應(yīng)到我們的系統(tǒng)中，就是下面的等價：（1）系統(tǒng)不包含特征t；（2）系統(tǒng)雖然包含特征t，但是t已經(jīng)固定了，不能變化。

我們計算分類系統(tǒng)不包含特征t的時候，就使用情況（2）來代替，就是計算當(dāng)一個特征t不能變化時，系統(tǒng)的信息量是多少。這個信息量其實也有專門的名稱，就叫做“條件熵”，條件嘛，自然就是指“t已經(jīng)固定“這個條件。

但是問題接踵而至，例如一個特征X，它可能的取值有n多種（x₁，x₂，……，x_n），當(dāng)計算條件熵而需要把它固定的時候，要把它固定在哪一個值上呢？答案是每一種可能都要固定一下，計算n個值，然后取均值才是條件熵。而取均值也不是簡單的加一加然后除以n，而是要用每個值出現(xiàn)的概率來算平均（簡單理解，就是一個值出現(xiàn)的可能性比較大，固定在它上面時算出來的信息量占的比重就要多一些）。

因此有這樣兩個條件熵的表達(dá)式：

這是指特征X被固定為值x_i時的條件熵，

這是指特征X被固定時的條件熵，注意與上式在意義上的區(qū)別。從剛才計算均值的討論可以看出來，第二個式子與第一個式子的關(guān)系就是：

具體到我們文本分類系統(tǒng)中的特征t，t有幾個可能的值呢？注意t是指一個固定的特征，比如他就是指關(guān)鍵詞“經(jīng)濟(jì)”或者“體育”，當(dāng)我們說特征“經(jīng)濟(jì)”可能的取值時，實際上只有兩個，“經(jīng)濟(jì)”要么出現(xiàn)，要么不出現(xiàn)。一般的，t的取值只有t（代表t出現(xiàn)）和（代表t不出現(xiàn)），注意系統(tǒng)包含t但t 不出現(xiàn)與系統(tǒng)根本不包含t可是兩回事。

因此固定t時系統(tǒng)的條件熵就有了，為了區(qū)別t出現(xiàn)時的符號與特征t本身的符號，我們用T代表特征，而用t代表T出現(xiàn)，那么：

與剛才的式子對照一下，含義很清楚對吧，P(t)就是T出現(xiàn)的概率，就是T不出現(xiàn)的概率。這個式子可以進(jìn)一步展開，其中的

另一半就可以展開為：

因此特征T給系統(tǒng)帶來的信息增益就可以寫成系統(tǒng)原本的熵與固定特征T后的條件熵之差：

公式中的東西看上去很多，其實也都很好計算。比如P(C_i)，表示類別C_i出現(xiàn)的概率，其實只要用1除以類別總數(shù)就得到了（這是說你平等的看待每個類別而忽略它們的大小時這樣算，如果考慮了大小就要把大小的影響加進(jìn)去）。再比如P(t)，就是特征T出現(xiàn)的概率，只要用出現(xiàn)過T的文檔數(shù)除以總文檔數(shù)就可以了，再比如P(C_i|t)表示出現(xiàn)T的時候，類別C_i出現(xiàn)的概率，只要用出現(xiàn)了T并且屬于類別C_i的文檔數(shù)除以出現(xiàn)了T的文檔數(shù)就可以了。

從以上討論中可以看出，信息增益也是考慮了特征出現(xiàn)和不出現(xiàn)兩種情況，與開方檢驗一樣，是比較全面的，因而效果不錯。但信息增益最大的問題還在于它只能考察特征對整個系統(tǒng)的貢獻(xiàn)，而不能具體到某個類別上，這就使得它只適合用來做所謂“全局”的特征選擇（指所有的類都使用相同的特征集合），而無法做“本地”的特征選擇（每個類別有自己的特征集合，因為有的詞，對這個類別很有區(qū)分度，對另一個類別則無足輕重）。

看看，導(dǎo)出的過程其實很簡單，沒有什么神秘的對不對。可有的學(xué)術(shù)論文里就喜歡把這種本來很直白的東西寫得很晦澀，仿佛只有讀者看不懂才是作者的真正成功。

咱們是新一代的學(xué)者，咱們沒有知識不怕被別人看出來，咱們有知識也不怕教給別人。所以咱都把事情說簡單點，說明白點，大家好，才是真的好。

接下來要說的東西其實不是松弛變量本身，但由于是為了使用松弛變量才引入的，因此放在這里也算合適，那就是懲罰因子C?；仡^看一眼引入了松弛變量以后的優(yōu)化問題：

注意其中C的位置，也可以回想一下C所起的作用（表征你有多么重視離群點，C越大越重視，越不想丟掉它們）。這個式子是以前做SVM的人寫的，大家也就這么用，但沒有任何規(guī)定說必須對所有的松弛變量都使用同一個懲罰因子，我們完全可以給每一個離群點都使用不同的C，這時就意味著你對每個樣本的重視程度都不一樣，有些樣本丟了也就丟了，錯了也就錯了，這些就給一個比較小的C；而有些樣本很重要，決不能分類錯誤（比如中央下達(dá)的文件啥的，笑），就給一個很大的C。

當(dāng)然實際使用的時候并沒有這么極端，但一種很常用的變形可以用來解決分類問題中樣本的“偏斜”問題。

先來說說樣本的偏斜問題，也叫數(shù)據(jù)集偏斜（unbalanced），它指的是參與分類的兩個類別（也可以指多個類別）樣本數(shù)量差異很大。比如說正類有10，000個樣本，而負(fù)類只給了100個，這會引起的問題顯而易見，可以看看下面的圖：

方形的點是負(fù)類。H，H₁，H₂是根據(jù)給的樣本算出來的分類面，由于負(fù)類的樣本很少很少，所以有一些本來是負(fù)類的樣本點沒有提供，比如圖中兩個灰色的方形點，如果這兩個點有提供的話，那算出來的分類面應(yīng)該是H’，H₂’和H₁，他們顯然和之前的結(jié)果有出入，實際上負(fù)類給的樣本點越多，就越容易出現(xiàn)在灰色點附近的點，我們算出的結(jié)果也就越接近于真實的分類面。但現(xiàn)在由于偏斜的現(xiàn)象存在，使得數(shù)量多的正類可以把分類面向負(fù)類的方向“推”，因而影響了結(jié)果的準(zhǔn)確性。

對付數(shù)據(jù)集偏斜問題的方法之一就是在懲罰因子上作文章，想必大家也猜到了，那就是給樣本數(shù)量少的負(fù)類更大的懲罰因子，表示我們重視這部分樣本（本來數(shù)量就少，再拋棄一些，那人家負(fù)類還活不活了），因此我們的目標(biāo)函數(shù)中因松弛變量而損失的部分就變成了：

其中i=1…p都是正樣本，j=p+1…p+q都是負(fù)樣本。libSVM這個算法包在解決偏斜問題的時候用的就是這種方法。

那C₊和C_-怎么確定呢？它們的大小是試出來的（參數(shù)調(diào)優(yōu)），但是他們的比例可以有些方法來確定。咱們先假定說C₊是5這么大，那確定C_-的一個很直觀的方法就是使用兩類樣本數(shù)的比來算，對應(yīng)到剛才舉的例子，C_-就可以定為500這么大（因為10，000：100=100：1嘛）。

但是這樣并不夠好，回看剛才的圖，你會發(fā)現(xiàn)正類之所以可以“欺負(fù)”負(fù)類，其實并不是因為負(fù)類樣本少，真實的原因是負(fù)類的樣本分布的不夠廣（沒擴(kuò)充到負(fù)類本應(yīng)該有的區(qū)域）。說一個具體點的例子，現(xiàn)在想給政治類和體育類的文章做分類，政治類文章很多，而體育類只提供了幾篇關(guān)于籃球的文章，這時分類會明顯偏向于政治類，如果要給體育類文章增加樣本，但增加的樣本仍然全都是關(guān)于籃球的（也就是說，沒有足球，排球，賽車，游泳等等），那結(jié)果會怎樣呢？雖然體育類文章在數(shù)量上可以達(dá)到與政治類一樣多，但過于集中了，結(jié)果仍會偏向于政治類！所以給C₊和C_-確定比例更好的方法應(yīng)該是衡量他們分布的程度。比如可以算算他們在空間中占據(jù)了多大的體積，例如給負(fù)類找一個超球——就是高維空間里的球啦——它可以包含所有負(fù)類的樣本，再給正類找一個，比比兩個球的半徑，就可以大致確定分布的情況。顯然半徑大的分布就比較廣，就給小一點的懲罰因子。

但是這樣還不夠好，因為有的類別樣本確實很集中，這不是提供的樣本數(shù)量多少的問題，這是類別本身的特征（就是某些話題涉及的面很窄，例如計算機(jī)類的文章就明顯不如文化類的文章那么“天馬行空”），這個時候即便超球的半徑差異很大，也不應(yīng)該賦予兩個類別不同的懲罰因子。

看到這里讀者一定瘋了，因為說來說去，這豈不成了一個解決不了的問題？然而事實如此，完全的方法是沒有的，根據(jù)需要，選擇實現(xiàn)簡單又合用的就好（例如libSVM就直接使用樣本數(shù)量的比）。

現(xiàn)在我們已經(jīng)把一個本來線性不可分的文本分類問題，通過映射到高維空間而變成了線性可分的。就像下圖這樣：

圓形和方形的點各有成千上萬個（畢竟，這就是我們訓(xùn)練集中文檔的數(shù)量嘛，當(dāng)然很大了）?，F(xiàn)在想象我們有另一個訓(xùn)練集，只比原先這個訓(xùn)練集多了一篇文章，映射到高維空間以后（當(dāng)然，也使用了相同的核函數(shù)），也就多了一個樣本點，但是這個樣本的位置是這樣的：

就是圖中黃色那個點，它是方形的，因而它是負(fù)類的一個樣本，這單獨的一個樣本，使得原本線性可分的問題變成了線性不可分的。這樣類似的問題（僅有少數(shù)點線性不可分）叫做“近似線性可分”的問題。

以我們?nèi)祟惖某ＷR來判斷，說有一萬個點都符合某種規(guī)律（因而線性可分），有一個點不符合，那這一個點是否就代表了分類規(guī)則中我們沒有考慮到的方面呢（因而規(guī)則應(yīng)該為它而做出修改）？

其實我們會覺得，更有可能的是，這個樣本點壓根就是錯誤，是噪聲，是提供訓(xùn)練集的同學(xué)人工分類時一打瞌睡錯放進(jìn)去的。所以我們會簡單的忽略這個樣本點，仍然使用原來的分類器，其效果絲毫不受影響。

但這種對噪聲的容錯性是人的思維帶來的，我們的程序可沒有。由于我們原本的優(yōu)化問題的表達(dá)式中，確實要考慮所有的樣本點（不能忽略某一個，因為程序它怎么知道該忽略哪一個呢？），在此基礎(chǔ)上尋找正負(fù)類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負(fù)的，像上面這種有噪聲的情況會使得整個問題無解。這種解法其實也叫做“硬間隔”分類法，因為他硬性的要求所有樣本點都滿足和分類平面間的距離必須大于某個值。

因此由上面的例子中也可以看出，硬間隔的分類法其結(jié)果容易受少數(shù)點的控制，這是很危險的（盡管有句話說真理總是掌握在少數(shù)人手中，但那不過是那一小撮人聊以自慰的詞句罷了，咱還是得民主）。

但解決方法也很明顯，就是仿照人的思路，允許一些點到分類平面的距離不滿足原先的要求。由于不同的訓(xùn)練集各點的間距尺度不太一樣，因此用間隔（而不是幾何間隔）來衡量有利于我們表達(dá)形式的簡潔。我們原先對樣本點的要求是：

意思是說離分類面最近的樣本點函數(shù)間隔也要比1大。如果要引入容錯性，就給1這個硬性的閾值加一個松弛變量，即允許

因為松弛變量是非負(fù)的，因此最終的結(jié)果是要求間隔可以比1小。但是當(dāng)某些點出現(xiàn)這種間隔比1小的情況時（這些點也叫離群點），意味著我們放棄了對這些點的精確分類，而這對我們的分類器來說是種損失。但是放棄這些點也帶來了好處，那就是使分類面不必向這些點的方向移動，因而可以得到更大的幾何間隔（在低維空間看來，分類邊界也更平滑）。顯然我們必須權(quán)衡這種損失和好處。好處很明顯，我們得到的分類間隔越大，好處就越多?；仡櫸覀冊嫉挠查g隔分類對應(yīng)的優(yōu)化問題：

||w||²就是我們的目標(biāo)函數(shù)（當(dāng)然系數(shù)可有可無），希望它越小越好，因而損失就必然是一個能使之變大的量（能使它變小就不叫損失了，我們本來就希望目標(biāo)函數(shù)值越小越好）。那如何來衡量損失，有兩種常用的方式，有人喜歡用

而有人喜歡用

其中l(wèi)都是樣本的數(shù)目。兩種方法沒有大的區(qū)別。如果選擇了第一種，得到的方法的就叫做二階軟間隔分類器，第二種就叫做一階軟間隔分類器。把損失加入到目標(biāo)函數(shù)里的時候，就需要一個懲罰因子（cost，也就是libSVM的諸多參數(shù)中的C），原來的優(yōu)化問題就變成了下面這樣：

這個式子有這么幾點要注意：

一是并非所有的樣本點都有一個松弛變量與其對應(yīng)。實際上只有“離群點”才有，或者也可以這么看，所有沒離群的點松弛變量都等于0（對負(fù)類來說，離群點就是在前面圖中，跑到H2右側(cè)的那些負(fù)樣本點，對正類來說，就是跑到H1左側(cè)的那些正樣本點）。

二是松弛變量的值實際上標(biāo)示出了對應(yīng)的點到底離群有多遠(yuǎn)，值越大，點就越遠(yuǎn)。

三是懲罰因子C決定了你有多重視離群點帶來的損失，顯然當(dāng)所有離群點的松弛變量的和一定時，你定的C越大，對目標(biāo)函數(shù)的損失也越大，此時就暗示著你非常不愿意放棄這些離群點，最極端的情況是你把C定為無限大，這樣只要稍有一個點離群，目標(biāo)函數(shù)的值馬上變成無限大，馬上讓問題變成無解，這就退化成了硬間隔問題。

四是懲罰因子C不是一個變量，整個優(yōu)化問題在解的時候，C是一個你必須事先指定的值，指定這個值以后，解一下，得到一個分類器，然后用測試數(shù)據(jù)看看結(jié)果怎么樣，如果不夠好，換一個C的值，再解一次優(yōu)化問題，得到另一個分類器，再看看效果，如此就是一個參數(shù)尋優(yōu)的過程，但這和優(yōu)化問題本身決不是一回事，優(yōu)化問題在解的過程中，C一直是定值，要記住。

五是盡管加了松弛變量這么一說，但這個優(yōu)化問題仍然是一個優(yōu)化問題（汗，這不廢話么），解它的過程比起原始的硬間隔問題來說，沒有任何更加特殊的地方。

從大的方面說優(yōu)化問題解的過程，就是先試著確定一下w，也就是確定了前面圖中的三條直線，這時看看間隔有多大，又有多少點離群，把目標(biāo)函數(shù)的值算一算，再換一組三條直線（你可以看到，分類的直線位置如果移動了，有些原來離群的點會變得不再離群，而有的本來不離群的點會變成離群點），再把目標(biāo)函數(shù)的值算一算，如此往復(fù)（迭代），直到最終找到目標(biāo)函數(shù)最小時的w。

啰嗦了這么多，讀者一定可以馬上自己總結(jié)出來，松弛變量也就是個解決線性不可分問題的方法罷了，但是回想一下，核函數(shù)的引入不也是為了解決線性不可分的問題么？為什么要為了一個問題使用兩種方法呢？

其實兩者還有微妙的不同。一般的過程應(yīng)該是這樣，還以文本分類為例。在原始的低維空間中，樣本相當(dāng)?shù)牟豢煞郑瑹o論你怎么找分類平面，總會有大量的離群點，此時用核函數(shù)向高維空間映射一下，雖然結(jié)果仍然是不可分的，但比原始空間里的要更加接近線性可分的狀態(tài)（就是達(dá)到了近似線性可分的狀態(tài)），此時再用松弛變量處理那些少數(shù)“冥頑不化”的離群點，就簡單有效得多啦。

本節(jié)中的（式1）也確實是支持向量機(jī)最最常用的形式。至此一個比較完整的支持向量機(jī)框架就有了，簡單說來，支持向量機(jī)就是使用了核函數(shù)的軟間隔線性分類法。

下一節(jié)會說說松弛變量剩下的一點點東西，順便搞個讀者調(diào)查，看看大家還想侃侃SVM的哪些方面。