這回是幫自己家小妞的網(wǎng)店做的店標(biāo),宣傳什么的,所以風(fēng)格相似恰恰是我想要的。

 

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

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

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

在文本分類的過程中，特征（也可以簡(jiǎn)單的理解為“詞”）從人類能夠理解的形式轉(zhuǎn)換為計(jì)算機(jī)能夠理解的形式時(shí)，實(shí)際上經(jīng)過了兩步驟的量化——特征選擇階段的重要程度量化和將具體文本轉(zhuǎn)化為向量時(shí)的特征權(quán)重量化。初次接觸文本分類的人很容易混淆這兩個(gè)步驟使用的方法和各自的目的，因而我經(jīng)常聽到讀者有類似“如何使用TFIDF做特征選擇”或者“卡方檢驗(yàn)量化權(quán)重后每篇文章都一樣”等等困惑。

文本分類本質(zhì)上也是一個(gè)模式識(shí)別的問題，因此我想借用一個(gè)更直觀的例子來(lái)說說特征選擇和權(quán)重量化到底各自是什么東西，當(dāng)然，一旦解釋清楚，你馬上就會(huì)覺得文本分類這東西實(shí)在白癡，實(shí)在沒什么技術(shù)含量，你也就不會(huì)再繼續(xù)看我的技術(shù)博客，不過我不擔(dān)心，因?yàn)槟阋呀?jīng)踏上了更光明的道路（笑），我高興還來(lái)不及。

想想通過指紋來(lái)識(shí)別一個(gè)人的身份，只看一個(gè)人的指紋，當(dāng)然說不出他姓甚名誰(shuí)，識(shí)別的過程實(shí)際上是比對(duì)的過程，要與已有的指紋庫(kù)比較，找出相同的，或者說相似到一定程度的那一個(gè)。

首要的問題是，人的指紋太復(fù)雜，包含太多的位置和幾何形狀，要完全重現(xiàn)一個(gè)人的指紋，存儲(chǔ)和計(jì)算都是大麻煩。因此第一步總是一個(gè)特征選擇的問題，我們把全人類的指紋都統(tǒng)計(jì)一下，看看哪幾個(gè)位置能夠最好的區(qū)分不同的人。顯然不同的位置效果很不一樣，在有的位置上，我的指紋是是什么形狀，其他人也大都是這個(gè)形狀，這個(gè)位置就不具有區(qū)分度，或者說不具有表征性，或者說，對(duì)分類問題來(lái)說，它的重要程度低。這樣的位置我們就傾向于在識(shí)別的時(shí)候根本不看它，不考慮它。

那怎么看誰(shuí)重要誰(shuí)不重要呢？這就依賴于具體的選擇方法如何來(lái)量化重要程度，對(duì)卡方檢驗(yàn)和信息增益這類方法來(lái)說，量化以后的得分越大的特征就越重要（也就是說，有可能有些方法，是得分越小的越重要）。

比如說你看10個(gè)位置，他們的重要程度分別是：

   1 2   3   4   5 6   7 8 9  10

（20，5，10，20，30，15，4，3，7， 3）

顯然第1，第3，4，5，6個(gè)位置比其他位置更重要，而相對(duì)的，第1個(gè)位置又比第3個(gè)位置更重要。

識(shí)別時(shí)，我們只在那些重要的位置上采樣。當(dāng)今的指紋識(shí)別系統(tǒng)，大都只用到人指紋的5個(gè)位置（驚訝么？只要5個(gè)位置的信息就可以區(qū)分60億人），這5個(gè)位置就是經(jīng)過特征選擇過程而得以保留的系統(tǒng)特征集合。假設(shè)這個(gè)就是剛才的例子，那么該集合應(yīng)該是：

（第1個(gè)位置，第3個(gè)位置，第4個(gè)位置，第5個(gè)位置，第6個(gè)位置）

當(dāng)然，具體的第3個(gè)位置是指紋中的哪個(gè)位置你自己總得清楚。

確定了這5個(gè)位置之后，就可以把一個(gè)人的指紋映射到這個(gè)只有5個(gè)維度的空間中，我們就把他在5個(gè)位置上的幾何形狀分別轉(zhuǎn)換成一個(gè)具體的值，這就是特征權(quán)重的計(jì)算。依據(jù)什么來(lái)轉(zhuǎn)換，就是你選擇的特征權(quán)重量化方法，在文本分類中，最常用的就是TFIDF。

我想一定是“權(quán)重“這個(gè)詞誤導(dǎo)了所有人，讓大家以為TFIDF計(jì)算出的值代表的是特征的重要程度，其實(shí)完全不是。例如我們有一位男同學(xué)，他的指紋向量是：

（10，3，4，20，5）

你注意到他第1個(gè)位置的得分（10）比第3個(gè)位置的得分（3）高，那么能說第1個(gè)位置比第3個(gè)位置重要么？如果再有一位女同學(xué)，她的指紋向量是：

（10，20，4，20，5）

看看，第1個(gè)位置得分（10）又比第3個(gè)位置（20）低了，那這兩個(gè)位置到底哪個(gè)更重要呢？答案是第1個(gè)位置更重要，但這不是在特征權(quán)重計(jì)算這一步體現(xiàn)出來(lái)的，而是在我們特征選擇的時(shí)候就確定了，第1個(gè)位置比第3個(gè)位置更重要。

因此要記住，通過TFIDF計(jì)算一個(gè)特征的權(quán)重時(shí)，該權(quán)重體現(xiàn)出的根本不是特征的重要程度！

那它代表什么？再看看兩位同學(xué)的指紋，放到一起：

（10， 3，4，20，5）

（10，20，4，20，5）

在第三個(gè)位置上女同學(xué)的權(quán)重高于男同學(xué)，這不代表該女同學(xué)在指紋的這個(gè)位置上更“優(yōu)秀“（畢竟，指紋還有什么優(yōu)秀不優(yōu)秀的分別么，笑），也不代表她的這個(gè)位置比男同學(xué)的這個(gè)位置更重要，3和20這兩個(gè)得分，僅僅代表他們的”不同“。

在文本分類中也是如此，比如我們的系統(tǒng)特征集合只有兩個(gè)詞：

（經(jīng)濟(jì)，發(fā)展）

這兩個(gè)詞是使用卡方檢驗(yàn)（特征選擇）選出來(lái)的，有一篇文章的向量形式是

（2，5）

另一篇

（3，4）

這兩個(gè)向量形式就是用TFIDF算出來(lái)的，很容易看出兩篇文章不是同一篇，為什么？因?yàn)樗麄兊奶卣鳈?quán)重根本不一樣，所以說權(quán)重代表的是差別，而不是優(yōu)劣。想想你說“經(jīng)濟(jì)這個(gè)詞在第二篇文章中得分高，因此它在第二篇文章中比在第一篇文章中更重要“，這句話代表什么意義呢？你自己都不知道吧（笑）。

所以，當(dāng)再說起使用TFIDF來(lái)計(jì)算特征權(quán)重時(shí)，最好把“權(quán)重“這個(gè)字眼忘掉，我們就把它說成計(jì)算得分好了（甚至”得分“也不太好，因?yàn)槿丝倳?huì)不自覺的認(rèn)為，得分高的就更重要），或者就僅僅說成是量化。

如此，你就再也不會(huì)拿TFIDF去做特征選擇了。

小Tips：為什么有的論文里確實(shí)使用了TFIDF作特征選擇呢？

嚴(yán)格說來(lái)并不是不可以，而且嚴(yán)格說來(lái)只要有一種方法能夠從一堆特征中挑出少數(shù)的一些，它就可以叫做一種特征選擇方法，就連“隨機(jī)選取一部分“都算是一種，而且效果并沒有差到驚人的地步哦！還是可以分對(duì)一大半的哦！所以有的人就用TFIDF的得分來(lái)把特征排排序，取得分最大的幾個(gè)進(jìn)入系統(tǒng)特征集合，效果也還行（畢竟，連隨機(jī)選取效果也都還行），怎么說呢，他們?cè)敢膺@么干就這么干吧。就像咱國(guó)家非得實(shí)行戶口制度，這個(gè)制度說不出任何道理，也不見他帶來(lái)任何好處，但不也沒影響二十一世紀(jì)成為中國(guó)的世紀(jì)么，呵呵。

又小忙了幾天。打算寫一篇澄清特征選擇和特征權(quán)重計(jì)算中許多容易誤解的問題的文章，不知大家有沒有興趣。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在信息增益中，重要性的衡量標(biāo)準(zhǔn)就是看特征能夠?yàn)榉诸愊到y(tǒng)帶來(lái)多少信息，帶來(lái)的信息越多，該特征越重要。

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

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

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

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

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

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

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

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

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

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

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

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

具體到我們文本分類系統(tǒng)中的特征t，t有幾個(gè)可能的值呢？注意t是指一個(gè)固定的特征，比如他就是指關(guān)鍵詞“經(jīng)濟(jì)”或者“體育”，當(dāng)我們說特征“經(jīng)濟(jì)”可能的取值時(shí)，實(shí)際上只有兩個(gè)，“經(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時(shí)系統(tǒng)的條件熵就有了，為了區(qū)別t出現(xiàn)時(shí)的符號(hào)與特征t本身的符號(hào)，我們用T代表特征，而用t代表T出現(xiàn)，那么：

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

另一半就可以展開為：

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

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

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

看看，導(dǎo)出的過程其實(shí)很簡(jiǎn)單，沒有什么神秘的對(duì)不對(duì)?？捎械膶W(xué)術(shù)論文里就喜歡把這種本來(lái)很直白的東西寫得很晦澀，仿佛只有讀者看不懂才是作者的真正成功。

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

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

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

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

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

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

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

 

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

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

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

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

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

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

 

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

 

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

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

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

但這種對(duì)噪聲的容錯(cuò)性是人的思維帶來(lái)的，我們的程序可沒有。由于我們?cè)镜膬?yōu)化問題的表達(dá)式中，確實(shí)要考慮所有的樣本點(diǎn)（不能忽略某一個(gè)，因?yàn)槌绦蛩趺粗涝摵雎阅囊粋€(gè)呢？），在此基礎(chǔ)上尋找正負(fù)類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負(fù)的，像上面這種有噪聲的情況會(huì)使得整個(gè)問題無(wú)解。這種解法其實(shí)也叫做“硬間隔”分類法，因?yàn)樗残缘囊笏袠颖军c(diǎn)都滿足和分類平面間的距離必須大于某個(gè)值。

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

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

 

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

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

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

而有人喜歡用

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

這個(gè)式子有這么幾點(diǎn)要注意：

一是并非所有的樣本點(diǎn)都有一個(gè)松弛變量與其對(duì)應(yīng)。實(shí)際上只有“離群點(diǎn)”才有，或者也可以這么看，所有沒離群的點(diǎn)松弛變量都等于0（對(duì)負(fù)類來(lái)說，離群點(diǎn)就是在前面圖中，跑到H2右側(cè)的那些負(fù)樣本點(diǎn)，對(duì)正類來(lái)說，就是跑到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ú)解，這就退化成了硬間隔問題。

四是懲罰因子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一直是定值，要記住。

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

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

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

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

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

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

生存？還是毀滅？——哈姆雷特

可分？還是不可分？——支持向量機(jī)

之前一直在討論的線性分類器,器如其名（汗，這是什么說法?。荒軐?duì)線性可分的樣本做處理。如果提供的樣本線性不可分，結(jié)果很簡(jiǎn)單，線性分類器的求解程序會(huì)無(wú)限循環(huán)，永遠(yuǎn)也解不出來(lái)。這必然使得它的適用范圍大大縮小，而它的很多優(yōu)點(diǎn)我們實(shí)在不原意放棄，怎么辦呢？是否有某種方法，讓線性不可分的數(shù)據(jù)變得線性可分呢？

有！其思想說來(lái)也簡(jiǎn)單，來(lái)用一個(gè)二維平面中的分類問題作例子，你一看就會(huì)明白。事先聲明，下面這個(gè)例子是網(wǎng)絡(luò)早就有的，我一時(shí)找不到原作者的正確信息，在此借用，并加進(jìn)了我自己的解說而已。

例子是下面這張圖：

我們把橫軸上端點(diǎn)a和b之間紅色部分里的所有點(diǎn)定為正類，兩邊的黑色部分里的點(diǎn)定為負(fù)類。試問能找到一個(gè)線性函數(shù)把兩類正確分開么？不能，因?yàn)槎S空間里的線性函數(shù)就是指直線，顯然找不到符合條件的直線。

但我們可以找到一條曲線，例如下面這一條：

顯然通過點(diǎn)在這條曲線的上方還是下方就可以判斷點(diǎn)所屬的類別（你在橫軸上隨便找一點(diǎn)，算算這一點(diǎn)的函數(shù)值，會(huì)發(fā)現(xiàn)負(fù)類的點(diǎn)函數(shù)值一定比0大，而正類的一定比0?。?。這條曲線就是我們熟知的二次曲線，它的函數(shù)表達(dá)式可以寫為：

問題只是它不是一個(gè)線性函數(shù)，但是，下面要注意看了，新建一個(gè)向量y和a：

這樣g(x)就可以轉(zhuǎn)化為f(y)=<a,y>，你可以把y和a分別回帶一下，看看等不等于原來(lái)的g(x)。用內(nèi)積的形式寫你可能看不太清楚，實(shí)際上f(y)的形式就是：

g(x)=f(y)=ay

在任意維度的空間中，這種形式的函數(shù)都是一個(gè)線性函數(shù)（只不過其中的a和y都是多維向量罷了），因?yàn)樽宰兞縴的次數(shù)不大于1。

看出妙在哪了么？原來(lái)在二維空間中一個(gè)線性不可分的問題，映射到四維空間后，變成了線性可分的！因此這也形成了我們最初想解決線性不可分問題的基本思路——向高維空間轉(zhuǎn)化，使其變得線性可分。

而轉(zhuǎn)化最關(guān)鍵的部分就在于找到x到y(tǒng)的映射方法。遺憾的是，如何找到這個(gè)映射，沒有系統(tǒng)性的方法（也就是說，純靠猜和湊）。具體到我們的文本分類問題，文本被表示為上千維的向量，即使維數(shù)已經(jīng)如此之高，也常常是線性不可分的，還要向更高的空間轉(zhuǎn)化。其中的難度可想而知。

小Tips:為什么說f(y)=ay是四維空間里的函數(shù)?

大家可能一時(shí)沒看明白。回想一下我們二維空間里的函數(shù)定義
  g(x)=ax+b
變量x是一維的，為什么說它是二維空間里的函數(shù)呢？因?yàn)檫€有一個(gè)變量我們沒寫出來(lái)，它的完整形式其實(shí)是
  y=g(x)=ax+b
即
  y=ax+b
看看，有幾個(gè)變量？?jī)蓚€(gè)。那是幾維空間的函數(shù)？（作者五歲的弟弟答：五維的。作者：……）
再看看
f(y)=ay
里面的y是三維的變量，那f(y)是幾維空間里的函數(shù)？（作者五歲的弟弟答：還是五維的。作者：……）

用一個(gè)具體文本分類的例子來(lái)看看這種向高維空間映射從而分類的方法如何運(yùn)作，想象一下，我們文本分類問題的原始空間是1000維的（即每個(gè)要被分類的文檔被表示為一個(gè)1000維的向量），在這個(gè)維度上問題是線性不可分的?，F(xiàn)在我們有一個(gè)2000維空間里的線性函數(shù)

f(x^’)=<w^’,x^’>+b

注意向量的右上角有個(gè) ’哦。它能夠?qū)⒃瓎栴}變得可分。式中的 w^’和x^’都是2000維的向量，只不過w^’是定值，而x^’是變量（好吧,嚴(yán)格說來(lái)這個(gè)函數(shù)是2001維的,哈哈），現(xiàn)在我們的輸入呢，是一個(gè)1000維的向量x，分類的過程是先把x變換為2000維的向量x^’，然后求這個(gè)變換后的向量x^’與向量w^’的內(nèi)積，再把這個(gè)內(nèi)積的值和b相加，就得到了結(jié)果，看結(jié)果大于閾值還是小于閾值就得到了分類結(jié)果。

你發(fā)現(xiàn)了什么？我們其實(shí)只關(guān)心那個(gè)高維空間里內(nèi)積的值，那個(gè)值算出來(lái)了，分類結(jié)果就算出來(lái)了。而從理論上說， x^’是經(jīng)由x變換來(lái)的，因此廣義上可以把它叫做x的函數(shù)（有一個(gè)x，就確定了一個(gè)x^’，對(duì)吧，確定不出第二個(gè)），而w^’是常量，它是一個(gè)低維空間里的常量w經(jīng)過變換得到的，所以給了一個(gè)w 和x的值，就有一個(gè)確定的f(x^’)值與其對(duì)應(yīng)。這讓我們幻想，是否能有這樣一種函數(shù)K(w,x),他接受低維空間的輸入值，卻能算出高維空間的內(nèi)積值<w^’,x^’>？

如果有這樣的函數(shù)，那么當(dāng)給了一個(gè)低維空間的輸入x以后，

g(x)=K(w,x)+b

f(x^’)=<w^’,x^’>+b

這兩個(gè)函數(shù)的計(jì)算結(jié)果就完全一樣，我們也就用不著費(fèi)力找那個(gè)映射關(guān)系，直接拿低維的輸入往g(x)里面代就可以了（再次提醒，這回的g(x)就不是線性函數(shù)啦，因?yàn)槟悴荒鼙ＷCK(w,x)這個(gè)表達(dá)式里的x次數(shù)不高于1哦）。

萬(wàn)幸的是，這樣的K(w,x)確實(shí)存在（發(fā)現(xiàn)凡是我們?nèi)祟惸芙鉀Q的問題，大都是巧得不能再巧，特殊得不能再特殊的問題，總是恰好有些能投機(jī)取巧的地方才能解決，由此感到人類的渺?。?，它被稱作核函數(shù)（核，kernel），而且還不止一個(gè)，事實(shí)上，只要是滿足了Mercer條件的函數(shù)，都可以作為核函數(shù)。核函數(shù)的基本作用就是接受兩個(gè)低維空間里的向量，能夠計(jì)算出經(jīng)過某個(gè)變換后在高維空間里的向量?jī)?nèi)積值。幾個(gè)比較常用的核函數(shù)，俄，教課書里都列過，我就不敲了（懶?。?。

回想我們上節(jié)說的求一個(gè)線性分類器，它的形式應(yīng)該是：

現(xiàn)在這個(gè)就是高維空間里的線性函數(shù)（為了區(qū)別低維和高維空間里的函數(shù)和向量，我改了函數(shù)的名字，并且給w和x都加上了 ’），我們就可以用一個(gè)低維空間里的函數(shù)（再一次的，這個(gè)低維空間里的函數(shù)就不再是線性的啦）來(lái)代替，

又發(fā)現(xiàn)什么了？f(x’) 和g(x)里的α，y，b全都是一樣一樣的！這就是說，盡管給的問題是線性不可分的，但是我們就硬當(dāng)它是線性問題來(lái)求解，只不過求解過程中，凡是要求內(nèi)積的時(shí)候就用你選定的核函數(shù)來(lái)算。這樣求出來(lái)的α再和你選定的核函數(shù)一組合，就得到分類器啦！

明白了以上這些，會(huì)自然的問接下來(lái)兩個(gè)問題：

1． 既然有很多的核函數(shù)，針對(duì)具體問題該怎么選擇？

2． 如果使用核函數(shù)向高維空間映射后，問題仍然是線性不可分的，那怎么辦？

第一個(gè)問題現(xiàn)在就可以回答你：對(duì)核函數(shù)的選擇，現(xiàn)在還缺乏指導(dǎo)原則！各種實(shí)驗(yàn)的觀察結(jié)果（不光是文本分類）的確表明，某些問題用某些核函數(shù)效果很好，用另一些就很差，但是一般來(lái)講，徑向基核函數(shù)是不會(huì)出太大偏差的一種，首選。（我做文本分類系統(tǒng)的時(shí)候，使用徑向基核函數(shù)，沒有參數(shù)調(diào)優(yōu)的情況下，絕大部分類別的準(zhǔn)確和召回都在85%以上，可見。雖然libSVM的作者林智仁認(rèn)為文本分類用線性核函數(shù)效果更佳，待考證）

對(duì)第二個(gè)問題的解決則引出了我們下一節(jié)的主題：松弛變量。

讓我再一次比較完整的重復(fù)一下我們要解決的問題：我們有屬于兩個(gè)類別的樣本點(diǎn)（并不限定這些點(diǎn)在二維空間中）若干，如圖，

圓形的樣本點(diǎn)定為正樣本（連帶著，我們可以把正樣本所屬的類叫做正類），方形的點(diǎn)定為負(fù)例。我們想求得這樣一個(gè)線性函數(shù)（在n維空間中的線性函數(shù)）：

g(x)=wx+b

使得所有屬于正類的點(diǎn)x₊代入以后有g(shù)(x₊)≥1，而所有屬于負(fù)類的點(diǎn)x_-代入后有g(shù)(x_-)≤-1（之所以總跟1比較，無(wú)論正一還是負(fù)一，都是因?yàn)槲覀児潭碎g隔為1，注意間隔和幾何間隔的區(qū)別）。代入g(x)后的值如果在1和-1之間，我們就拒絕判斷。

求這樣的g(x)的過程就是求w（一個(gè)n維向量）和b（一個(gè)實(shí)數(shù)）兩個(gè)參數(shù)的過程（但實(shí)際上只需要求w，求得以后找某些樣本點(diǎn)代入就可以求得b）。因此在求g(x)的時(shí)候，w才是變量。

你肯定能看出來(lái)，一旦求出了w（也就求出了b），那么中間的直線H就知道了（因?yàn)樗褪莣x+b=0嘛，哈哈），那么H1和H2也就知道了（因?yàn)槿呤瞧叫械模蚁喔舻木嚯x還是||w||決定的）。那么w是誰(shuí)決定的？顯然是你給的樣本決定的，一旦你在空間中給出了那些個(gè)樣本點(diǎn)，三條直線的位置實(shí)際上就唯一確定了（因?yàn)槲覀兦蟮氖亲顑?yōu)的那三條，當(dāng)然是唯一的），我們解優(yōu)化問題的過程也只不過是把這個(gè)確定了的東西算出來(lái)而已。

樣本確定了w，用數(shù)學(xué)的語(yǔ)言描述，就是w可以表示為樣本的某種組合：

w=α₁x₁+α₂x₂+…+α_nx_n

式子中的α_i是一個(gè)一個(gè)的數(shù)（在嚴(yán)格的證明過程中，這些α被稱為拉格朗日乘子），而x_i是樣本點(diǎn)，因而是向量，n就是總樣本點(diǎn)的個(gè)數(shù)。為了方便描述，以下開始嚴(yán)格區(qū)別數(shù)字與向量的乘積和向量間的乘積，我會(huì)用α₁x₁表示數(shù)字和向量的乘積，而用<x₁,x₂>表示向量x₁,x₂的內(nèi)積（也叫點(diǎn)積，注意與向量叉積的區(qū)別）。因此g(x)的表達(dá)式嚴(yán)格的形式應(yīng)該是：

g(x)=<w,x>+b

但是上面的式子還不夠好，你回頭看看圖中正樣本和負(fù)樣本的位置，想像一下，我不動(dòng)所有點(diǎn)的位置，而只是把其中一個(gè)正樣本點(diǎn)定為負(fù)樣本點(diǎn)（也就是把一個(gè)點(diǎn)的形狀從圓形變?yōu)榉叫危Y(jié)果怎么樣？三條直線都必須移動(dòng)（因?yàn)閷?duì)這三條直線的要求是必須把方形和圓形的點(diǎn)正確分開）！這說明w不僅跟樣本點(diǎn)的位置有關(guān)，還跟樣本的類別有關(guān)（也就是和樣本的“標(biāo)簽”有關(guān)）。因此用下面這個(gè)式子表示才算完整：

w=α₁y₁x₁+α₂y₂x₂+…+α_ny_nx_n （式1）

其中的y_i就是第i個(gè)樣本的標(biāo)簽，它等于1或者-1。其實(shí)以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于0（不等于0才對(duì)w起決定作用），這部分不等于0的拉格朗日乘子后面所乘的樣本點(diǎn)，其實(shí)都落在H1和H2上，也正是這部分樣本（而不需要全部樣本）唯一的確定了分類函數(shù)，當(dāng)然，更嚴(yán)格的說，這些樣本的一部分就可以確定，因?yàn)槔绱_定一條直線，只需要兩個(gè)點(diǎn)就可以，即便有三五個(gè)都落在上面，我們也不是全都需要。這部分我們真正需要的樣本點(diǎn)，就叫做支持（撐）向量?。诌€挺形象吧，他們“撐”起了分界線）

式子也可以用求和符號(hào)簡(jiǎn)寫一下：

 

因此原來(lái)的g(x)表達(dá)式可以寫為：

注意式子中x才是變量，也就是你要分類哪篇文檔，就把該文檔的向量表示代入到 x的位置，而所有的x_i統(tǒng)統(tǒng)都是已知的樣本。還注意到式子中只有x_i和x是向量，因此一部分可以從內(nèi)積符號(hào)中拿出來(lái)，得到g(x)的式子為：

發(fā)現(xiàn)了什么？w不見啦！從求w變成了求α。

但肯定有人會(huì)說，這并沒有把原問題簡(jiǎn)化呀。嘿嘿，其實(shí)簡(jiǎn)化了，只不過在你看不見的地方，以這樣的形式描述問題以后，我們的優(yōu)化問題少了很大一部分不等式約束（記得這是我們解不了極值問題的萬(wàn)惡之源）。但是接下來(lái)先跳過線性分類器求解的部分，來(lái)看看 SVM在線性分類器上所做的重大改進(jìn)——核函數(shù)。

從最一般的定義上說，一個(gè)求最小值的問題就是一個(gè)優(yōu)化問題（也叫尋優(yōu)問題，更文縐縐的叫法是規(guī)劃——Programming），它同樣由兩部分組成，目標(biāo)函數(shù)和約束條件，可以用下面的式子表示：

（式1）

約束條件用函數(shù)c來(lái)表示，就是constrain的意思啦。你可以看出一共有p+q個(gè)約束條件，其中p個(gè)是不等式約束，q個(gè)等式約束。

關(guān)于這個(gè)式子可以這樣來(lái)理解：式中的x是自變量，但不限定它的維數(shù)必須為1（視乎你解決的問題空間維數(shù)，對(duì)我們的文本分類來(lái)說，那可是成千上萬(wàn)啊）。要求f(x)在哪一點(diǎn)上取得最小值（反倒不太關(guān)心這個(gè)最小值到底是多少，關(guān)鍵是哪一點(diǎn)），但不是在整個(gè)空間里找，而是在約束條件所劃定的一個(gè)有限的空間里找，這個(gè)有限的空間就是優(yōu)化理論里所說的可行域。注意可行域中的每一個(gè)點(diǎn)都要求滿足所有p+q個(gè)條件，而不是滿足其中一條或幾條就可以（切記，要滿足每個(gè)約束），同時(shí)可行域邊界上的點(diǎn)有一個(gè)額外好的特性，它們可以使不等式約束取得等號(hào)！而邊界內(nèi)的點(diǎn)不行。

關(guān)于可行域還有個(gè)概念不得不提，那就是凸集，凸集是指有這么一個(gè)點(diǎn)的集合，其中任取兩個(gè)點(diǎn)連一條直線，這條線上的點(diǎn)仍然在這個(gè)集合內(nèi)部，因此說“凸”是很形象的（一個(gè)反例是，二維平面上，一個(gè)月牙形的區(qū)域就不是凸集，你隨便就可以找到兩個(gè)點(diǎn)違反了剛才的規(guī)定）。

回頭再來(lái)看我們線性分類器問題的描述，可以看出更多的東西。

（式2）

在這個(gè)問題中，自變量就是w，而目標(biāo)函數(shù)是w的二次函數(shù)，所有的約束條件都是w的線性函數(shù)（哎，千萬(wàn)不要把x_i當(dāng)成變量，它代表樣本，是已知的），這種規(guī)劃問題有個(gè)很有名氣的稱呼——二次規(guī)劃（Quadratic Programming，QP），而且可以更進(jìn)一步的說，由于它的可行域是一個(gè)凸集，因此它是一個(gè)凸二次規(guī)劃。

一下子提了這么多術(shù)語(yǔ)，實(shí)在不是為了讓大家以后能向別人炫耀學(xué)識(shí)的淵博，這其實(shí)是我們繼續(xù)下去的一個(gè)重要前提，因?yàn)樵趧?dòng)手求一個(gè)問題的解之前（好吧，我承認(rèn)，是動(dòng)計(jì)算機(jī)求……），我們必須先問自己：這個(gè)問題是不是有解？如果有解，是否能找到？

對(duì)于一般意義上的規(guī)劃問題，兩個(gè)問題的答案都是不一定，但凸二次規(guī)劃讓人喜歡的地方就在于，它有解（教科書里面為了嚴(yán)謹(jǐn)，常常加限定成分，說它有全局最優(yōu)解，由于我們想找的本來(lái)就是全局最優(yōu)的解，所以不加也罷），而且可以找到?。ó?dāng)然，依據(jù)你使用的算法不同，找到這個(gè)解的速度，行話叫收斂速度，會(huì)有所不同）

對(duì)比（式2）和（式1）還可以發(fā)現(xiàn)，我們的線性分類器問題只有不等式約束，因此形式上看似乎比一般意義上的規(guī)劃問題要簡(jiǎn)單，但解起來(lái)卻并非如此。

因?yàn)槲覀儗?shí)際上并不知道該怎么解一個(gè)帶約束的優(yōu)化問題。如果你仔細(xì)回憶一下高等數(shù)學(xué)的知識(shí)，會(huì)記得我們可以輕松的解一個(gè)不帶任何約束的優(yōu)化問題（實(shí)際上就是當(dāng)年背得爛熟的函數(shù)求極值嘛，求導(dǎo)再找0點(diǎn)唄，誰(shuí)不會(huì)??？笑），我們甚至還會(huì)解一個(gè)只帶等式約束的優(yōu)化問題，也是背得爛熟的，求條件極值，記得么，通過添加拉格朗日乘子，構(gòu)造拉格朗日函數(shù)，來(lái)把這個(gè)問題轉(zhuǎn)化為無(wú)約束的優(yōu)化問題云云（如果你一時(shí)沒想通，我提醒一下，構(gòu)造出的拉格朗日函數(shù)就是轉(zhuǎn)化之后的問題形式，它顯然沒有帶任何條件）。

讀者問：如果只帶等式約束的問題可以轉(zhuǎn)化為無(wú)約束的問題而得以求解，那么可不可以把帶不等式約束的問題向只帶等式約束的問題轉(zhuǎn)化一下而得以求解呢？

聰明，可以，實(shí)際上我們也正是這么做的。下一節(jié)就來(lái)說說如何做這個(gè)轉(zhuǎn)化，一旦轉(zhuǎn)化完成，求解對(duì)任何學(xué)過高等數(shù)學(xué)的人來(lái)說，都是小菜一碟啦。