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

 

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

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

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

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

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

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

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

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

比如說你看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è)位置比其他位置更重要，而相對的，第1個(gè)位置又比第3個(gè)位置更重要。

識別時(shí)，我們只在那些重要的位置上采樣。當(dāng)今的指紋識別系統(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ù)什么來轉(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)出來的，而是在我們特征選擇的時(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)（特征選擇）選出來的，有一篇文章的向量形式是

（2，5）

另一篇

（3，4）

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

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

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

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

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

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

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

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

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

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

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

因此我們還得再退一步，還是解兩類分類問題，還是每次選一個(gè)類的樣本作正類樣本，而負(fù)類樣本則變成只選一個(gè)類（稱為“一對一單挑”的方法，哦，不對，沒有單挑，就是“一對一”的方法，呵呵），這就避免了偏斜。因此過程就是算出這樣一些分類器，第一個(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í)間卻比“一類對其余”方法少很多，在真正用來分類的時(shí)候，把一篇文章扔給所有分類器，第一個(gè)分類器會投票說它是“1”或者“2”，第二個(gè)會說它是“1”或者“3”，讓每一個(gè)都投上自己的一票，最后統(tǒng)計(jì)票數(shù)，如果類別“1”得票最多，就判這篇文章屬于第1類。這種方法顯然也會有分類重疊的現(xiàn)象，但不會有不可分類現(xiàn)象，因?yàn)榭偛豢赡芩蓄悇e的票數(shù)都是0?？雌饋韷蚝妹矗科鋵?shí)不然，想想分類一篇文章，我們調(diào)用了多少個(gè)分類器？10個(gè)，這還是類別數(shù)為5的時(shí)候，類別數(shù)如果是1000，要調(diào)用的分類器數(shù)目會上升至約500,000個(gè)（類別數(shù)的平方量級）。這如何是好？

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

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

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

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

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

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

解析解就是理論上的解，它的形式是表達(dá)式，因此它是精確的，一個(gè)問題只要有解（無解的問題還跟著摻和什么呀，哈哈），那它的解析解是一定存在的。當(dāng)然存在是一回事，能夠解出來，或者可以在可以承受的時(shí)間范圍內(nèi)解出來，就是另一回事了。對SVM來說，求得解析解的時(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ī)條件也各不相同，最終得到的解精度也各不相同，可見對求數(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ù)雜度會有變化，是因?yàn)樗还飧斎雴栴}的規(guī)模有關(guān)（不光和樣本的數(shù)量，維數(shù)有關(guān)），也和問題最終的解有關(guān)（即支持向量有關(guān)），如果支持向量比較少，過程會快很多，如果支持向量很多，接近于樣本的數(shù)量，就會產(chǎn)生O(dL²)這個(gè)十分糟糕的結(jié)果（給10，000個(gè)樣本，每個(gè)樣本1000維，基本就不用算了，算不出來，呵呵，而這種輸入規(guī)模對文本分類來說太正常了）。

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

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

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

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

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

對分類系統(tǒng)來說，類別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è)值所攜帶的信息量就是上式中的這么多。

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

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

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

我們計(jì)算分類系統(tǒng)不包含特征t的時(shí)候，就使用情況（2）來代替，就是計(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è)值，然后取均值才是條件熵。而取均值也不是簡單的加一加然后除以n，而是要用每個(gè)值出現(xiàn)的概率來算平均（簡單理解，就是一個(gè)值出現(xiàn)的可能性比較大，固定在它上面時(shí)算出來的信息量占的比重就要多一些）。

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

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

這是指特征X被固定時(shí)的條件熵，注意與上式在意義上的區(qū)別。從剛才計(jì)算均值的討論可以看出來，第二個(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í)的符號與特征t本身的符號，我們用T代表特征，而用t代表T出現(xiàn)，那么：

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

另一半就可以展開為：

因此特征T給系統(tǒng)帶來的信息增益就可以寫成系統(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)一樣，是比較全面的，因而效果不錯。但信息增益最大的問題還在于它只能考察特征對整個(gè)系統(tǒng)的貢獻(xiàn)，而不能具體到某個(gè)類別上，這就使得它只適合用來做所謂“全局”的特征選擇（指所有的類都使用相同的特征集合），而無法做“本地”的特征選擇（每個(gè)類別有自己的特征集合，因?yàn)橛械脑~，對這個(gè)類別很有區(qū)分度，對另一個(gè)類別則無足輕重）。

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

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

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

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

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

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

方形的點(diǎn)是負(fù)類。H，H₁，H₂是根據(jù)給的樣本算出來的分類面，由于負(fù)類的樣本很少很少，所以有一些本來是負(fù)類的樣本點(diǎn)沒有提供，比如圖中兩個(gè)灰色的方形點(diǎn)，如果這兩個(gè)點(diǎn)有提供的話，那算出來的分類面應(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)確性。

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

 

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

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

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

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

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

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

 

圓形和方形的點(diǎ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來判斷，說有一萬個(gè)點(diǎn)都符合某種規(guī)律（因而線性可分），有一個(gè)點(diǎn)不符合，那這一個(gè)點(diǎn)是否就代表了分類規(guī)則中我們沒有考慮到的方面呢（因而規(guī)則應(yīng)該為它而做出修改）？

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

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

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

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

 

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

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

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

而有人喜歡用

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

有！其思想說來也簡單，來用一個(gè)二維平面中的分類問題作例子，你一看就會明白。事先聲明，下面這個(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ù)值，會發(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分別回帶一下，看看等不等于原來的g(x)。用內(nèi)積的形式寫你可能看不太清楚，實(shí)際上f(y)的形式就是：

g(x)=f(y)=ay

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

看出妙在哪了么？原來在二維空間中一個(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í)沒看明白?；叵胍幌挛覀兌S空間里的函數(shù)定義
  g(x)=ax+b
變量x是一維的，為什么說它是二維空間里的函數(shù)呢？因?yàn)檫€有一個(gè)變量我們沒寫出來，它的完整形式其實(shí)是
  y=g(x)=ax+b
即
  y=ax+b
看看，有幾個(gè)變量？兩個(gè)。那是幾維空間的函數(shù)？（作者五歲的弟弟答：五維的。作者：……）
再看看
f(y)=ay
里面的y是三維的變量，那f(y)是幾維空間里的函數(shù)？（作者五歲的弟弟答：還是五維的。作者：……）

用一個(gè)具體文本分類的例子來看看這種向高維空間映射從而分類的方法如何運(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)格說來這個(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è)值算出來了，分類結(jié)果就算出來了。而從理論上說， x^’是經(jīng)由x變換來的，因此廣義上可以把它叫做x的函數(shù)（有一個(gè)x，就確定了一個(gè)x^’，對吧，確定不出第二個(gè)），而w^’是常量，它是一個(gè)低維空間里的常量w經(jīng)過變換得到的，所以給了一個(gè)w 和x的值，就有一個(gè)確定的f(x^’)值與其對應(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哦）。

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

回想我們上節(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è)問題：

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

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

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

對第二個(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比較，無論正一還是負(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才是變量。

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

樣本確定了w，用數(shù)學(xué)的語言描述，就是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ù)字與向量的乘積和向量間的乘積，我會用α₁x₁表示數(shù)字和向量的乘積，而用<x₁,x₂>表示向量x₁,x₂的內(nèi)積（也叫點(diǎn)積，注意與向量叉積的區(qū)別）。因此g(x)的表達(dá)式嚴(yán)格的形式應(yīng)該是：

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

但是上面的式子還不夠好，你回頭看看圖中正樣本和負(fù)樣本的位置，想像一下，我不動所有點(diǎn)的位置，而只是把其中一個(gè)正樣本點(diǎn)定為負(fù)樣本點(diǎn)（也就是把一個(gè)點(diǎn)的形狀從圓形變?yōu)榉叫危Y(jié)果怎么樣？三條直線都必須移動（因?yàn)閷@三條直線的要求是必須把方形和圓形的點(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才對w起決定作用），這部分不等于0的拉格朗日乘子后面所乘的樣本點(diǎn)，其實(shí)都落在H1和H2上，也正是這部分樣本（而不需要全部樣本）唯一的確定了分類函數(shù)，當(dāng)然，更嚴(yán)格的說，這些樣本的一部分就可以確定，因?yàn)槔绱_定一條直線，只需要兩個(gè)點(diǎn)就可以，即便有三五個(gè)都落在上面，我們也不是全都需要。這部分我們真正需要的樣本點(diǎn)，就叫做支持（撐）向量?。诌€挺形象吧，他們“撐”起了分界線）

式子也可以用求和符號簡寫一下：

 

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

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

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

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

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

（式1）

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

關(guān)于這個(gè)式子可以這樣來理解：式中的x是自變量，但不限定它的維數(shù)必須為1（視乎你解決的問題空間維數(shù)，對我們的文本分類來說，那可是成千上萬啊）。要求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è)額外好的特性，它們可以使不等式約束取得等號！而邊界內(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ī)定）。

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

（式2）

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

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

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

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

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

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

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

上節(jié)說到我們有了一個(gè)線性分類函數(shù)，也有了判斷解優(yōu)劣的標(biāo)準(zhǔn)——即有了優(yōu)化的目標(biāo)，這個(gè)目標(biāo)就是最大化幾何間隔，但是看過一些關(guān)于SVM的論文的人一定記得什么優(yōu)化的目標(biāo)是要最小化||w||這樣的說法，這是怎么回事呢？回頭再看看我們對間隔和幾何間隔的定義：

間隔：δ=y(wx+b)=|g(x)|

幾何間隔：

 

可以看出δ=||w||δ_幾何。注意到幾何間隔與||w||是成反比的，因此最大化幾何間隔與最小化||w||完全是一回事。而我們常用的方法并不是固定||w||的大小而尋求最大幾何間隔，而是固定間隔（例如固定為1），尋找最小的||w||。

而凡是求一個(gè)函數(shù)的最小值（或最大值）的問題都可以稱為尋優(yōu)問題（也叫作一個(gè)規(guī)劃問題），又由于找最大值的問題總可以通過加一個(gè)負(fù)號變?yōu)檎易钚≈档膯栴}，因此我們下面討論的時(shí)候都針對找最小值的過程來進(jìn)行。一個(gè)尋優(yōu)問題最重要的部分是目標(biāo)函數(shù)，顧名思義，就是指尋優(yōu)的目標(biāo)。例如我們想尋找最小的||w||這件事，就可以用下面的式子表示：

但實(shí)際上對于這個(gè)目標(biāo)，我們常常使用另一個(gè)完全等價(jià)的目標(biāo)函數(shù)來代替，那就是：

(式1)

不難看出當(dāng)||w||²達(dá)到最小時(shí)，||w||也達(dá)到最小，反之亦然（前提當(dāng)然是||w||描述的是向量的長度，因而是非負(fù)的）。之所以采用這種形式，是因?yàn)楹竺娴那蠼膺^程會對目標(biāo)函數(shù)作一系列變換，而式（1）的形式會使變換后的形式更為簡潔（正如聰明的讀者所料，添加的系數(shù)二分之一和平方，皆是為求導(dǎo)數(shù)所需）。

接下來我們自然會問的就是，這個(gè)式子是否就描述了我們的問題呢？（回想一下，我們的問題是有一堆點(diǎn)，可以被分成兩類，我們要找出最好的分類面）

如果直接來解這個(gè)求最小值問題，很容易看出當(dāng)||w||=0的時(shí)候就得到了目標(biāo)函數(shù)的最小值。但是你也會發(fā)現(xiàn)，無論你給什么樣的數(shù)據(jù)，都是這個(gè)解！反映在圖中，就是H1與H2兩條直線間的距離無限大，這個(gè)時(shí)候，所有的樣本點(diǎn)（無論正樣本還是負(fù)樣本）都跑到了H1和H2中間，而我們原本的意圖是，H1右側(cè)的被分為正類，H2 左側(cè)的被分為負(fù)類，位于兩類中間的樣本則拒絕分類（拒絕分類的另一種理解是分給哪一類都有道理，因而分給哪一類也都沒有道理）。這下可好，所有樣本點(diǎn)都進(jìn)入了無法分類的灰色地帶。

造成這種結(jié)果的原因是在描述問題的時(shí)候只考慮了目標(biāo)，而沒有加入約束條件，約束條件就是在求解過程中必須滿足的條件，體現(xiàn)在我們的問題中就是樣本點(diǎn)必須在H1或H2的某一側(cè)（或者至少在H1和H2上），而不能跑到兩者中間。我們前文提到過把間隔固定為1，這是指把所有樣本點(diǎn)中間隔最小的那一點(diǎn)的間隔定為1（這也是集合的間隔的定義，有點(diǎn)繞嘴），也就意味著集合中的其他點(diǎn)間隔都不會小于1，按照間隔的定義，滿足這些條件就相當(dāng)于讓下面的式子總是成立：

    y_i[(w·x_i)+b]≥1 (i=1,2,…,l) （l是總的樣本數(shù)）

但我們常常習(xí)慣讓式子的值和0比較，因而經(jīng)常用變換過的形式：

    y_i[(w·x_i)+b]-1≥0 (i=1,2,…,l) （l是總的樣本數(shù)）

因此我們的兩類分類問題也被我們轉(zhuǎn)化成了它的數(shù)學(xué)形式，一個(gè)帶約束的最小值的問題：

下一節(jié)我們從最一般的意義上看看一個(gè)求最小值的問題有何特征，以及如何來解。

按:之前的文章重新匯編一下,修改了一些錯誤和不當(dāng)?shù)恼f法，一起復(fù)習(xí),然后繼續(xù)SVM之旅.

（一）SVM的八股簡介

支持向量機(jī)(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問題中[10]。
支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC 維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性（即對特定訓(xùn)練樣本的學(xué)習(xí)精度，Accuracy）和學(xué)習(xí)能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力[14]（或稱泛化能力）。

以上是經(jīng)常被有關(guān)SVM 的學(xué)術(shù)文獻(xiàn)引用的介紹，有點(diǎn)八股，我來逐一分解并解釋一下。

Vapnik是統(tǒng)計(jì)機(jī)器學(xué)習(xí)的大牛，這想必都不用說，他出版的《Statistical Learning Theory》是一本完整闡述統(tǒng)計(jì)機(jī)器學(xué)習(xí)思想的名著。在該書中詳細(xì)的論證了統(tǒng)計(jì)機(jī)器學(xué)習(xí)之所以區(qū)別于傳統(tǒng)機(jī)器學(xué)習(xí)的本質(zhì)，就在于統(tǒng)計(jì)機(jī)器學(xué)習(xí)能夠精確的給出學(xué)習(xí)效果，能夠解答需要的樣本數(shù)等等一系列問題。與統(tǒng)計(jì)機(jī)器學(xué)習(xí)的精密思維相比，傳統(tǒng)的機(jī)器學(xué)習(xí)基本上屬于摸著石頭過河，用傳統(tǒng)的機(jī)器學(xué)習(xí)方法構(gòu)造分類系統(tǒng)完全成了一種技巧，一個(gè)人做的結(jié)果可能很好，另一個(gè)人差不多的方法做出來卻很差，缺乏指導(dǎo)和原則。

所謂VC維是對函數(shù)類的一種度量，可以簡單的理解為問題的復(fù)雜程度，VC維越高，一個(gè)問題就越復(fù)雜。正是因?yàn)镾VM關(guān)注的是VC維，后面我們可以看到，SVM解決問題的時(shí)候，和樣本的維數(shù)是無關(guān)的（甚至樣本是上萬維的都可以，這使得SVM很適合用來解決文本分類的問題，當(dāng)然，有這樣的能力也因?yàn)橐肓撕撕瘮?shù)）。

結(jié)構(gòu)風(fēng)險(xiǎn)最小聽上去文縐縐，其實(shí)說的也無非是下面這回事。

機(jī)器學(xué)習(xí)本質(zhì)上就是一種對問題真實(shí)模型的逼近（我們選擇一個(gè)我們認(rèn)為比較好的近似模型，這個(gè)近似模型就叫做一個(gè)假設(shè)），但毫無疑問，真實(shí)模型一定是不知道的（如果知道了，我們干嗎還要機(jī)器學(xué)習(xí)？直接用真實(shí)模型解決問題不就可以了？對吧，哈哈）既然真實(shí)模型不知道，那么我們選擇的假設(shè)與問題真實(shí)解之間究竟有多大差距，我們就沒法得知。比如說我們認(rèn)為宇宙誕生于150億年前的一場大爆炸，這個(gè)假設(shè)能夠描述很多我們觀察到的現(xiàn)象，但它與真實(shí)的宇宙模型之間還相差多少？誰也說不清，因?yàn)槲覀儔焊筒恢勒鎸?shí)的宇宙模型到底是什么。

這個(gè)與問題真實(shí)解之間的誤差，就叫做風(fēng)險(xiǎn)（更嚴(yán)格的說，誤差的累積叫做風(fēng)險(xiǎn)）。我們選擇了一個(gè)假設(shè)之后（更直觀點(diǎn)說，我們得到了一個(gè)分類器以后），真實(shí)誤差無從得知，但我們可以用某些可以掌握的量來逼近它。最直觀的想法就是使用分類器在樣本數(shù)據(jù)上的分類的結(jié)果與真實(shí)結(jié)果（因?yàn)闃颖臼且呀?jīng)標(biāo)注過的數(shù)據(jù)，是準(zhǔn)確的數(shù)據(jù)）之間的差值來表示。這個(gè)差值叫做經(jīng)驗(yàn)風(fēng)險(xiǎn)R_emp(w)。以前的機(jī)器學(xué)習(xí)方法都把經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化作為努力的目標(biāo)，但后來發(fā)現(xiàn)很多分類函數(shù)能夠在樣本集上輕易達(dá)到100%的正確率，在真實(shí)分類時(shí)卻一塌糊涂（即所謂的推廣能力差，或泛化能力差）。此時(shí)的情況便是選擇了一個(gè)足夠復(fù)雜的分類函數(shù)（它的VC維很高），能夠精確的記住每一個(gè)樣本，但對樣本之外的數(shù)據(jù)一律分類錯誤?；仡^看看經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則我們就會發(fā)現(xiàn)，此原則適用的大前提是經(jīng)驗(yàn)風(fēng)險(xiǎn)要確實(shí)能夠逼近真實(shí)風(fēng)險(xiǎn)才行（行話叫一致），但實(shí)際上能逼近么？答案是不能，因?yàn)闃颖緮?shù)相對于現(xiàn)實(shí)世界要分類的文本數(shù)來說簡直九牛一毛，經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則只在這占很小比例的樣本上做到?jīng)]有誤差，當(dāng)然不能保證在更大比例的真實(shí)文本上也沒有誤差。

統(tǒng)計(jì)學(xué)習(xí)因此而引入了泛化誤差界的概念，就是指真實(shí)風(fēng)險(xiǎn)應(yīng)該由兩部分內(nèi)容刻畫，一是經(jīng)驗(yàn)風(fēng)險(xiǎn)，代表了分類器在給定樣本上的誤差；二是置信風(fēng)險(xiǎn)，代表了我們在多大程度上可以信任分類器在未知文本上分類的結(jié)果。很顯然，第二部分是沒有辦法精確計(jì)算的，因此只能給出一個(gè)估計(jì)的區(qū)間，也使得整個(gè)誤差只能計(jì)算上界，而無法計(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)會變大。

泛化誤差界的公式為：

R(w)≤R_emp(w)+Ф(n/h)

公式中R(w)就是真實(shí)風(fēng)險(xiǎn)，R_emp(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)的算法。

SVM其他的特點(diǎn)就比較容易理解了。

小樣本，并不是說樣本的絕對數(shù)量少（實(shí)際上，對任何算法來說，更多的樣本幾乎總是能帶來更好的效果），而是說與問題的復(fù)雜度比起來，SVM算法要求的樣本數(shù)是相對比較少的。

非線性，是指SVM擅長應(yīng)付樣本數(shù)據(jù)線性不可分的情況，主要通過松弛變量（也有人叫懲罰變量）和核函數(shù)技術(shù)來實(shí)現(xiàn)，這一部分是SVM的精髓，以后會詳細(xì)討論。多說一句，關(guān)于文本分類這個(gè)問題究竟是不是線性可分的，尚沒有定論，因此不能簡單的認(rèn)為它是線性可分的而作簡化處理，在水落石出之前，只好先當(dāng)它是線性不可分的（反正線性可分也不過是線性不可分的一種特例而已，我們向來不怕方法過于通用）。

高維模式識別是指樣本維數(shù)很高，例如文本的向量表示，如果沒有經(jīng)過另一系列文章（《文本分類入門》）中提到過的降維處理，出現(xiàn)幾萬維的情況很正常，其他算法基本就沒有能力應(yīng)付了，SVM卻可以，主要是因?yàn)镾VM 產(chǎn)生的分類器很簡潔，用到的樣本信息很少（僅僅用到那些稱之為“支持向量”的樣本，此為后話），使得即使樣本維數(shù)很高，也不會給存儲和計(jì)算帶來大麻煩（相對照而言，kNN算法在分類時(shí)就要用到所有樣本，樣本數(shù)巨大，每個(gè)樣本維數(shù)再一高，這日子就沒法過了……）。

下一節(jié)開始正式討論SVM。別嫌我說得太詳細(xì)哦。

 

SVM入門（二）線性分類器Part 1

線性分類器(一定意義上,也可以叫做感知機(jī)) 是最簡單也很有效的分類器形式.在一個(gè)線性分類器中,可以看到SVM形成的思路,并接觸很多SVM的核心概念.

用一個(gè)二維空間里僅有兩類樣本的分類問題來舉個(gè)小例子。如圖所示

^­C₁和C₂是要區(qū)分的兩個(gè)類別，在二維平面中它們的樣本如上圖所示。中間的直線就是一個(gè)分類函數(shù)，它可以將兩類樣本完全分開。一般的，如果一個(gè)線性函數(shù)能夠?qū)颖就耆_的分開，就稱這些數(shù)據(jù)是線性可分的，否則稱為非線性可分的。

什么叫線性函數(shù)呢？在一維空間里就是一個(gè)點(diǎn)，在二維空間里就是一條直線，三維空間里就是一個(gè)平面，可以如此想象下去，如果不關(guān)注空間的維數(shù)，這種線性函數(shù)還有一個(gè)統(tǒng)一的名稱——超平面（Hyper Plane）！

實(shí)際上，一個(gè)線性函數(shù)是一個(gè)實(shí)值函數(shù)（即函數(shù)的值是連續(xù)的實(shí)數(shù)），而我們的分類問題（例如這里的二元分類問題——回答一個(gè)樣本屬于還是不屬于一個(gè)類別的問題）需要離散的輸出值，例如用1表示某個(gè)樣本屬于類別C₁，而用0表示不屬于（不屬于C₁也就意味著屬于C₂），這時(shí)候只需要簡單的在實(shí)值函數(shù)的基礎(chǔ)上附加一個(gè)閾值即可，通過分類函數(shù)執(zhí)行時(shí)得到的值大于還是小于這個(gè)閾值來確定類別歸屬。 例如我們有一個(gè)線性函數(shù)

g(x)=wx+b

我們可以取閾值為0，這樣當(dāng)有一個(gè)樣本x_i需要判別的時(shí)候，我們就看g(x_i)的值。若g(x_i)>0，就判別為類別C₁，若g(x_i)<0，則判別為類別C₂（等于的時(shí)候我們就拒絕判斷，呵呵）。此時(shí)也等價(jià)于給函數(shù)g(x)附加一個(gè)符號函數(shù)sgn()，即f(x)=sgn [g(x)]是我們真正的判別函數(shù)。

關(guān)于g(x)=wx+b這個(gè)表達(dá)式要注意三點(diǎn)：一，式中的x不是二維坐標(biāo)系中的橫軸，而是樣本的向量表示，例如一個(gè)樣本點(diǎn)的坐標(biāo)是(3,8)，則x^T=(3,8) ，而不是x=3（一般說向量都是說列向量，因此以行向量形式來表示時(shí)，就加上轉(zhuǎn)置）。二，這個(gè)形式并不局限于二維的情況，在n維空間中仍然可以使用這個(gè)表達(dá)式，只是式中的w成為了n維向量（在二維的這個(gè)例子中，w是二維向量，為了表示起來方便簡潔，以下均不區(qū)別列向量和它的轉(zhuǎn)置，聰明的讀者一看便知）；三，g(x)不是中間那條直線的表達(dá)式，中間那條直線的表達(dá)式是g(x)=0，即wx+b=0，我們也把這個(gè)函數(shù)叫做分類面。

實(shí)際上很容易看出來，中間那條分界線并不是唯一的，我們把它稍微旋轉(zhuǎn)一下，只要不把兩類數(shù)據(jù)分錯，仍然可以達(dá)到上面說的效果，稍微平移一下，也可以。此時(shí)就牽涉到一個(gè)問題，對同一個(gè)問題存在多個(gè)分類函數(shù)的時(shí)候，哪一個(gè)函數(shù)更好呢？顯然必須要先找一個(gè)指標(biāo)來量化“好”的程度，通常使用的都是叫做“分類間隔”的指標(biāo)。下一節(jié)我們就仔細(xì)說說分類間隔，也補(bǔ)一補(bǔ)相關(guān)的數(shù)學(xué)知識。

SVM入門（三）線性分類器Part 2

上回說到對于文本分類這樣的不適定問題（有一個(gè)以上解的問題稱為不適定問題），需要有一個(gè)指標(biāo)來衡量解決方案（即我們通過訓(xùn)練建立的分類模型）的好壞，而分類間隔是一個(gè)比較好的指標(biāo)。

在進(jìn)行文本分類的時(shí)候，我們可以讓計(jì)算機(jī)這樣來看待我們提供給它的訓(xùn)練樣本，每一個(gè)樣本由一個(gè)向量（就是那些文本特征所組成的向量）和一個(gè)標(biāo)記（標(biāo)示出這個(gè)樣本屬于哪個(gè)類別）組成。如下：

D_i=(x_i,y_i)

x_i就是文本向量（維數(shù)很高），y_i就是分類標(biāo)記。

在二元的線性分類中，這個(gè)表示分類的標(biāo)記只有兩個(gè)值，1和-1（用來表示屬于還是不屬于這個(gè)類）。有了這種表示法，我們就可以定義一個(gè)樣本點(diǎn)到某個(gè)超平面的間隔：

δ_i=y_i(wx_i+b)

這個(gè)公式乍一看沒什么神秘的，也說不出什么道理，只是個(gè)定義而已，但我們做做變換，就能看出一些有意思的東西。

首先注意到如果某個(gè)樣本屬于該類別的話，那么wx_i+b>0（記得么？這是因?yàn)槲覀兯x的g(x)=wx+b就通過大于0還是小于0來判斷分類），而y_i也大于0；若不屬于該類別的話，那么wx_i+b<0，而y_i也小于0，這意味著y_i(wx_i+b)總是大于0的，而且它的值就等于|wx_i+b|?。ㄒ簿褪莬g(x_i)|）

現(xiàn)在把w和b進(jìn)行一下歸一化，即用w/||w||和b/||w||分別代替原來的w和b，那么間隔就可以寫成

這個(gè)公式是不是看上去有點(diǎn)眼熟？沒錯，這不就是解析幾何中點(diǎn)x_i到直線g(x)=0的距離公式嘛?。ㄍ茝V一下，是到超平面g(x)=0的距離， g(x)=0就是上節(jié)中提到的分類超平面）

小Tips：||w||是什么符號？||w||叫做向量w的范數(shù)，范數(shù)是對向量長度的一種度量。我們常說的向量長度其實(shí)指的是它的2-范數(shù)，范數(shù)最一般的表示形式為p-范數(shù)，可以寫成如下表達(dá)式

    向量w=(w₁, w₂, w₃,…… w_n)

它的p-范數(shù)為

看看把p換成2的時(shí)候，不就是傳統(tǒng)的向量長度么？當(dāng)我們不指明p的時(shí)候，就像||w||這樣使用時(shí)，就意味著我們不關(guān)心p的值，用幾范數(shù)都可以；或者上文已經(jīng)提到了p的值，為了敘述方便不再重復(fù)指明。

當(dāng)用歸一化的w和b代替原值之后的間隔有一個(gè)專門的名稱，叫做幾何間隔，幾何間隔所表示的正是點(diǎn)到超平面的歐氏距離，我們下面就簡稱幾何間隔為“距離”。以上是單個(gè)點(diǎn)到某個(gè)超平面的距離（就是間隔，后面不再區(qū)別這兩個(gè)詞）定義，同樣可以定義一個(gè)點(diǎn)的集合（就是一組樣本）到某個(gè)超平面的距離為此集合中離超平面最近的點(diǎn)的距離。下面這張圖更加直觀的展示出了幾何間隔的現(xiàn)實(shí)含義：

H是分類面，而H₁和H₂是平行于H，且過離H最近的兩類樣本的直線，H₁與H，H₂與H之間的距離就是幾何間隔。

之所以如此關(guān)心幾何間隔這個(gè)東西，是因?yàn)閹缀伍g隔與樣本的誤分次數(shù)間存在關(guān)系：

 

其中的δ是樣本集合到分類面的間隔，R=max ||xi||  i=1,...,n，即R是所有樣本中（xi是以向量表示的第i個(gè)樣本）向量長度最長的值（也就是說代表樣本的分布有多么廣）。先不必追究誤分次數(shù)的具體定義和推導(dǎo)過程，只要記得這個(gè)誤分次數(shù)一定程度上代表分類器的誤差。而從上式可以看出，誤分次數(shù)的上界由幾何間隔決定?。ó?dāng)然，是樣本已知的時(shí)候）

至此我們就明白為何要選擇幾何間隔來作為評價(jià)一個(gè)解優(yōu)劣的指標(biāo)了，原來幾何間隔越大的解，它的誤差上界越小。因此最大化幾何間隔成了我們訓(xùn)練階段的目標(biāo)，而且，與二把刀作者所寫的不同，最大化分類間隔并不是SVM的專利，而是早在線性分類時(shí)期就已有的思想。

簡單的說,比較兩個(gè)int型或long型的數(shù)據(jù)沒有什么問題,可以用==來判斷,但對浮點(diǎn)數(shù)(float與double)來說,需要對Float.NaN和0.0這個(gè)兩個(gè)特殊數(shù)字作額外的處理。
Float.NaN嚴(yán)格說來不是一個(gè)數(shù)字（它的字面意思也就是Not a Number），但是因?yàn)檫@個(gè)值可以被保存在一個(gè)float型的變量中（因?yàn)樗３Ｊ浅?的結(jié)果），所以暫且當(dāng)它是個(gè)數(shù)字吧。但它與一般的浮點(diǎn)數(shù)有些許不同，就是兩個(gè)NaN用==比較的結(jié)果會得到false。
可以用下面的代碼驗(yàn)證：

輸出結(jié)果為false

我用另一種除0的方法得到NaN，可以看到使用==判斷仍然得到false。代碼如下：


而當(dāng)我們使用Float.compare()這個(gè)方法來比較兩個(gè)NaN時(shí)，卻會得到相等的結(jié)果。可以用下面的代碼驗(yàn)證：

compare()方法如果返回0，就說明兩個(gè)數(shù)相等，返回-1，就說明第一個(gè)比第二個(gè)小，返回1則正好相反。
上面這兩行語句的返回結(jié)果都是0。
一般來說，基本類型的compare()方法與直接使用==的效果“應(yīng)該”是一樣的，但在NaN這個(gè)問題上不一致，是利是弊，取決于使用的人作何期望。當(dāng)程序的語義要求兩個(gè)NaN不應(yīng)該被認(rèn)為相等時(shí)（例如用NaN來代表兩個(gè)無窮大，學(xué)過高等數(shù)學(xué)的朋友們都記得，兩個(gè)無窮看上去符號是一樣，但不應(yīng)該認(rèn)為是相等的兩樣?xùn)|西），就使用==判斷；如果NaN被看得無足輕重（畢竟，我只關(guān)心數(shù)字，兩個(gè)不是數(shù)字的東西就劃歸同一類好了嘛）就使用Float.compare()。

另一個(gè)在==和compare()方法上表現(xiàn)不一致的浮點(diǎn)數(shù)就是正0和負(fù)0（當(dāng)然這也是計(jì)算機(jī)表示有符號數(shù)字的老大難問題），我們（萬能的）人類當(dāng)然知道0.0f和-0.0f應(yīng)該是相等的數(shù)字，但是試試下面的代碼：

返回的結(jié)果是true和-1?？吹搅嗣?，==認(rèn)為正0和負(fù)0相等，而compare()方法認(rèn)為正0比負(fù)0要大。所以對0的比較來說，==是更好的選擇。

目前為止不管后臺寫了多少邏輯（已經(jīng)登錄了Google，取了相冊數(shù)據(jù)），我們的Gadget都還是那個(gè)看上去白白的Gadget。而要想讓它看上去有所不同，就要在main.xml這個(gè)文件中，制定我們想要的“長相”（就跟征婚啟事里寫的一樣，身高1米6至1米7，體重不超過55公斤，相貌端正，賢良淑惠）。

如果你已經(jīng)下載了我提供的源碼，就可以打開看看，對照實(shí)際效果來看代碼，應(yīng)該很好理解。我們總計(jì)在界面上放了幾樣?xùn)|西：

•  一張背景圖（就是白白的那個(gè)）
•  一張Picasa的Logo
•  兩行表示歡迎的文字（就是label啦）
•  一個(gè)用來顯示相冊信息的列表（listbox），當(dāng)然，目前列表中還一個(gè)列表項(xiàng)都沒有（列表項(xiàng)稱之為item）
•  最后又貼了兩張圖，其中一張是某企業(yè)的logo（笑）

其中值得注意的事情有這么幾件：

一是背景圖片絕非可有可無，按google的說法，像label這種東西，如果沒有放在一張背景圖片之上的話，是顯示不出來的。

二是Gadget中界面的內(nèi)容，樣式和布局都在這一個(gè)文件中指定。

三是Gadget的界面沒有HTML那種流動布局的效果，就是說，所有要顯示的元素，必須明明白白的指出它的位置，也就是每個(gè)元素的x和y屬性，是從該元素的父元素左上角開始計(jì)算的坐標(biāo)。如果你先寫了一個(gè)label（拿label舉個(gè)例子，實(shí)際上用什么效果都是一樣的），再挨著它寫了一個(gè)label，兩個(gè)label你都沒有指定x和y的值，那么這個(gè)兩個(gè)label會重疊著顯示在一起。不信你可以試一試。

四是圖片的源文件位置，從代碼中可以看到指定本機(jī)上的相對目錄是可以的，那么指定一個(gè)網(wǎng)絡(luò)上的url可以么？例如http://www.sina.com.cn/images/logo.gif？如果你頭腦中還存在著HTML的印象，可能想當(dāng)然的以為可以這么做，而事實(shí)上不行，Gadget與Web沒有天然的聯(lián)系（沒記錯的話，我已經(jīng)說過四次了）。后面處理相冊縮略圖的時(shí)候，我們會看到怎么把網(wǎng)絡(luò)上的圖片顯示出來。

寫過圖形用戶界面程序的人一定想問，如何讓界面上的元素與代碼產(chǎn)生聯(lián)系呢？例如我們的列表，我想在代碼中對它作些修改的時(shí)候，如何取得它的引用呢？在Gadget中這一點(diǎn)還比較方便，主要有兩個(gè)途徑：一是只要你給元素賦了name屬性，例如我就給列表項(xiàng)起了一個(gè)名字叫做contentListBox，在main.xml中的這一行：

 

之后就可以直接在代碼中用contentListBox這個(gè)值來訪問這個(gè)列表項(xiàng)了（而且任你在代碼中怎么找，也找不到聲明或者初始化這個(gè)變量的地方）——當(dāng)然前提是起的名字必須是唯一的。有意思吧？

第二種方式比較傳統(tǒng)也比較少用，可以通過DOM對象訪問每個(gè)元素。

廢話不多說，來看看在代碼中給列表插入列表項(xiàng)怎么做。

列表項(xiàng)對應(yīng)著Gadget API提供的一個(gè)名為item的對象實(shí)例，但我們要用new item()這樣的語法來得到一個(gè)新的列表項(xiàng)并逐一設(shè)置它的屬性么？不不，有更簡便也更好玩的方法，我們只要新建一個(gè)字符串：

然后調(diào)用列表contentListBox的方法來添加就可以，像這樣：

方便么？這種用法使得開發(fā)人員不需要為一個(gè)圖形界面的組件掌握兩套語法（XML的和JavaScript的），非常貼心。

好，現(xiàn)在來說另一個(gè)問題，既然不能為一個(gè)img對象的src屬性指定一個(gè)網(wǎng)絡(luò)地址，那到底如何顯示網(wǎng)絡(luò)上的圖片呢？答案很長，如果你有了圖片的url（就是 http://開頭的那種啦），首先要通過XmlHttpRequest把圖片的數(shù)據(jù)取回來，然后把這部分?jǐn)?shù)據(jù)賦給src屬性。

具體點(diǎn)，記得一個(gè)請求最重要的四部分?jǐn)?shù)據(jù)么？url：就是該圖片的url；請求類型：因?yàn)槭且髷?shù)據(jù)，自然是“GET”；請求頭：對本請求來說沒有；消息體：同樣沒有。

所以發(fā)請求的部分并不困難，待請求的狀態(tài)變?yōu)?/span>4，也就是說明回傳數(shù)據(jù)已到達(dá)的時(shí)候，就可以從請求的responseStream這個(gè)屬性得到圖片的二進(jìn)制數(shù)據(jù)。假設(shè)在代碼中我們要顯示的圖片是<img name=”myImg”/>,記得么，使用名字可以直接訪問這個(gè)圖片，再假設(shè)我們的請求對象取名為xhRequest，像下面這樣：

如此就可以了！哈哈，簡單吧（我當(dāng)初倒是找了半天，讀過了YouTube Gadget的代碼才參透呢，愚笨愚笨）。

在我們剩下的唯一一個(gè)重要函數(shù)Main的fetchAlbumThumbnail()中，就是使用這種方法來取得相冊縮略圖的圖片并顯示在Gadget的界面中的。

這個(gè)函數(shù)我就不逐一分解了，相信你一定看得懂。

大的方向上說，從Picasa服務(wù)器上取數(shù)據(jù)，有兩種方式，一種是使用Google已經(jīng)開放的各種語言的API，可以在頁面http://code.google.com/apis/picasaweb/developers_guide_protocol.html找到很多相關(guān)的信息。另一種方式便是使用最樸素的網(wǎng)絡(luò)請求方式來自己構(gòu)造請求并解析回傳的數(shù)據(jù)。

由于Picasa只提供了Java,.NET,Python和PHP的接口，而Gadget目前只能使用JavaScript，因此我們只能使用樸素方式。

繼續(xù)第三節(jié)的路子，仍然使用XmlHttpRequest向Picasa服務(wù)發(fā)起請求，也要處理好四部分信息。

請求發(fā)向哪個(gè)URL：為了獲取Picasa的相冊信息，要向http://picasaweb.google.com/data/feed/api/user/default發(fā)請求，這個(gè)URL其實(shí)可以有很多變化的地方。例如user/default這個(gè)地方是請求所附token所屬的用戶相冊信息，這里當(dāng)然可以明確的指定用戶名。”api”可以換成”base”，這個(gè)將影響回傳數(shù)據(jù)的格式，但Goolge推薦使用api而不是base。

請求的類型：我們是要索取數(shù)據(jù)，因此這是一個(gè)查詢的動作，應(yīng)該使用GET。

請求頭：只需要把token放進(jìn)去就好。這樣來放：

消息體：對于我們查詢相冊的請求，不需要任何的消息體。

具體的代碼都在Main.prototype.fetchAlbumsInfo()函數(shù)中，就像這樣：

最后兩個(gè)函數(shù)是下一步要做的工作：解析回傳的相冊數(shù)據(jù)，并下載每個(gè)相冊的縮略圖。

 

要想解析回傳數(shù)據(jù)，首先得知道回傳的數(shù)據(jù)是什么。你可以把這些數(shù)據(jù)打印出來看看，應(yīng)該是類似下面的樣子：

怎么，看著有點(diǎn)眼熟？沒錯，這個(gè)回傳數(shù)據(jù)所使用的格式正是標(biāo)準(zhǔn)的Atom Feed（更多的描述可以參考W3C的標(biāo)準(zhǔn)和下面的鏈接：http://code.google.com/intl/zh-CN/apis/picasaweb/developers_guide_protocol.html）。

可以根據(jù)Atom Feed的格式來編寫我們解析回傳數(shù)據(jù)的函數(shù)parseAlbumFeed()，這個(gè)函數(shù)的作用是從回傳的xml數(shù)據(jù)中找出我們關(guān)心的幾樣?xùn)|西：該用戶目前擁有的所有的相冊信息，包括每個(gè)相冊的標(biāo)題，描述，訪問權(quán)限以及縮略圖的地址。找出這些信息以后，將會拼成一個(gè)包含相冊（Album）的數(shù)組作為函數(shù)返回值。

具體代碼如下：

這個(gè)函數(shù)中用到了一些我們還沒有新建的類，相冊（Album）以及縮略圖(Thumbnail)。這些類的聲明可以放在一個(gè)新的名為album.js的文件中，并在我們整個(gè)Gadget的main.xml文件中指名要導(dǎo)入它。因此main.xml的最后幾行應(yīng)該看上去是這個(gè)樣子：

而album.js的內(nèi)容大體如下：

最后還要在main.js里面添加一個(gè)函數(shù)createDomDocument()，用來提供一個(gè)DOM對象供我們解析XML用。代碼如下：

下一節(jié)來說說怎么取得相冊的縮略圖并顯示在Gadget的界面中。

向Google的服務(wù)器發(fā)起登錄請求之后，得到了免死金牌token，以后就可以拿著這個(gè)token去犯罪，不是，去Google的其它服務(wù)取數(shù)據(jù)，但是在此之前應(yīng)該第一，從響應(yīng)的消息中把token找出來；第二，這個(gè)token應(yīng)該想辦法保存起來，以備以后使用。

上一節(jié)已經(jīng)把響應(yīng)的內(nèi)容打印了出來，它的格式也很簡單，因此用下面的代碼很容易就可以把響應(yīng)的內(nèi)容轉(zhuǎn)成方便我們使用的形式，即一個(gè)map的形式，通過鍵值對來存儲：

在我們的相應(yīng)回調(diào)函數(shù)里，就可以調(diào)用這個(gè)函數(shù)處理一下響應(yīng)，從結(jié)果中取鍵為”Auth”這一項(xiàng)的值，并保存在Gadget Host為我們準(zhǔn)備好的一個(gè)負(fù)責(zé)持久化的對象options中。找到上一節(jié)Main.prototype.login的代碼，把響應(yīng)的回調(diào)函數(shù)改成下面的樣子：

最后加的一行main.onLoginSuccess()就是我們下一步動作的起點(diǎn)，在這里應(yīng)該開始去取用戶mymail2009.test@gmail.com所擁有的相冊信息了，我們先聲明一個(gè)空函數(shù)放在那里。

繼續(xù)之前多扯兩句options這個(gè)對象，這是Gadget Host提供的持久化對象，你可以從代碼中看到它還有對存儲的內(nèi)容進(jìn)行加密的功能，Google的文檔中提到這個(gè)options對象在后臺實(shí)際上是把內(nèi)容保存在一個(gè)XML文件中，當(dāng)然該文件的位置是不會告訴你的啦，哈哈。

下一節(jié)將向Picasa服務(wù)發(fā)起請求！

Google帳戶最早用來申請巨大的Gmail郵箱（如今看來，一般個(gè)大吧），隨著后來的Blogger，Picasa，Docs等各種服務(wù)上線，也就順路繼承了過來?，F(xiàn)在使用一個(gè)Google帳戶，就可以同時(shí)使用這些服務(wù)。

既然我們打算寫一個(gè)從Picasa取相冊數(shù)據(jù)的Gadget，就免不了要先了解一些和Goolge帳戶有關(guān)的知識。因?yàn)?/span>Picasa的數(shù)據(jù)也是受保護(hù)的，并非誰要看都可以（公開的相冊除外哦，那都是炫耀冊，巴不得全天下人都看見呢），我們的程序也不例外，要想取到相冊的數(shù)據(jù)，程序必須向Google的服務(wù)器證明自己得到了相應(yīng)用戶的授權(quán)。

一個(gè)人類用戶當(dāng)然可以這樣做：打開Picasa的首頁，發(fā)現(xiàn)要求登錄，于是輸入自己的用戶名密碼，成功后就查看自己的相冊。我們的程序可干不了，它不會打開瀏覽器，好吧，這個(gè)它會，但打開以后它找不著用戶名的輸入框在哪，即便找到了，也不知該往里面填什么，即便填對了，也不知要看什么，即便看到了，也看不懂，即便看懂了也學(xué)不會……（讀者：你貧不貧？）

所以一切的一切都還要咱們自己來寫，當(dāng)然少不了Google的幫忙。

為了方便應(yīng)用程序的登錄，Google在自己的服務(wù)器上開放了被稱之為“Google Account Authentication”的服務(wù)，我們只用到其中一種方式：ClientLogin。使用這種方式訪問Google的服務(wù)大致是下面的流程：

很容易看出來，這基本上是一個(gè)兩步驟的工作：首先使用一個(gè)Google帳戶訪問Google Account Authentication 服務(wù)，并得到一個(gè)可以合法訪問服務(wù)數(shù)據(jù)的token（Google把它叫做得到一個(gè)“授權(quán)”，不過習(xí)慣上還是叫token吧，就是令牌，拿了以后皇帝不能砍你頭的那種，此過程也叫做申請一個(gè)token）；使用上一步得到的token去訪問具體的服務(wù)并取得數(shù)據(jù)（我們的例子中就是訪問Picasa服務(wù)）。

有一些東西從圖上看不出，我來說一說。一是程序訪問Gmail的時(shí)候使用的不是這種方式（畢竟Gmail太早啦，那時(shí)連Google自己都沒有考慮清楚吧），但其他大部分Goolge服務(wù)，包括Calendar,Docs,Picasa,Blogger,Contacts,Google Apps等等，都是上面這個(gè)流程。二是并非申請了一個(gè)token以后，就可以訪問Google所有的服務(wù)，實(shí)際上需要為每個(gè)服務(wù)申請不同的token。

具體到代碼中，我們使用XmlHttpRequest對象來發(fā)送請求并且接受回傳的數(shù)據(jù)。

XmlHttpRequest是Gadget Host提供的一個(gè)類型（注意我沒有說對象，因此要用的時(shí)候你還得自己初始化，也就是new一下，哈哈），其行為與W3C所指定的標(biāo)準(zhǔn)XmlHttpRequest相同。再一次的，不要聯(lián)想到瀏覽器，你不能假設(shè)這個(gè)XmlHttpRequest與IE或者FireFox提供的XmlHttpRequest有任何聯(lián)系，更不能依賴這樣的假設(shè)來編寫程序。

好，廢話少說，還用上一節(jié)新建的“白Gadget“（笑），在main.js文件里添加這樣一個(gè)函數(shù)：

調(diào)用這個(gè)函數(shù)就可以得到一個(gè)XmlHttpRequest的對象啦。

然后為我們的Gadget添加一個(gè)主類，并把需要的對象引用也聲明好，這些都寫在main.js文件中，像這樣：

我們就要在Main.login()函數(shù)中寫我們?nèi)?/span>token的邏輯。

詳細(xì)說說申請token的過程。請求是通過XmlHttpRequest對象發(fā)起的，而對一個(gè)請求來說，最重要的信息有四個(gè)：請求的URL，請求的類型，請求頭和消息體。

URL是說你的請求要發(fā)往哪里，既然我們要使用Google的服務(wù)，那當(dāng)然要往Google那里發(fā)了，具體應(yīng)該為：

https://www.google.com/accounts/ClientLogin

如果你沒有看出這是一個(gè)安全的https請求，那我提醒一下（如果你看出來了，我就不提醒了，笑）。

請求的類型是指你要Google的服務(wù)器替你做什么事情，是返回你要查詢的數(shù)據(jù)？還是為你更新已有的數(shù)據(jù)，抑或僅僅是提交一些數(shù)據(jù)，還是要服務(wù)器幫你刪除一些數(shù)據(jù)？

Google的服務(wù)器通過你提交請求的類型來做相應(yīng)的操作，每一種操作的類型對應(yīng)如下：

•  查詢　　GET
•  提交　　POST
•  更新　　PUT
•  刪除　　DELETE

看著眼熟么？沒錯，正是輕量級的Web Service接口REST！

我們做登錄顯然是一個(gè)提交的動作， 要把我們的用戶名和密碼告訴Google，因此我們的請求類型是POST。

對登錄來說，請求頭沒有特殊要求，只需要請求頭Content-Type，其值為application/x-www-form-urlencoded

所需的用戶名，密碼等信息被統(tǒng)一稱為“屬性”，屬性的值將放在消息體中發(fā)送。因此你的消息體看起來是下面這個(gè)樣子的一個(gè)字符串：

Email=mymail2009.test%40gmail.com&Passwd=mymail2009&service=lh2&source=gd-picasa-gadget-1.0.0.0&accountType=HOSTED_OR_GOOGLE

注意其中紅色的部分，用戶名和密碼的位置你當(dāng)然很容易找到，”service=lh2”這一項(xiàng)就指明了你要為訪問什么服務(wù)申請token，lh2是指Picasa，如果訪問Google Docs則要填writely，詳細(xì)的列表可以看這一節(jié)最后的附錄。

好，把登錄的代碼整個(gè)貼出來，你應(yīng)該很容易找到以上四部分對應(yīng)的地方。

在請求的回調(diào)函數(shù)中，目前只是先簡單的打印了相應(yīng)的文本內(nèi)容，實(shí)際上應(yīng)該在這里做更多的事，詳情咱們下節(jié)再聊。如果你看到類似下面這樣的輸出內(nèi)容，說明登錄的請求成功了。如果沒有成功，很可能是因?yàn)槲乙呀?jīng)換掉了用戶名和密碼，用你自己的Google帳戶試試看。

應(yīng)該看到的內(nèi)容：

SID＝

DQAAAHYAAADYQ4hToTAEYRu0uEXP9yXZ1uc_W3-kBtZFpug78XQDGiykOb-Sv2qdXtdUOL-
npRJm9SSq-AEvSBodrcuy3UwgFM8SX_z6fXzpGaJzHzQx5YTzR0AJHCEkFh
4yOoBFs0iCE2LI0LWQs6_2BFyIuLLMwRA8m3vfuVzNE3CHjrUHZA

LSID＝

DQAAAHgAAAClSiMWRfKAonW8zIytZ7NEizJNMQZojiNqsDxm3elei36MV
7GzM72bMiqdQawt8Fd1Dpp68p5bs1XYOXUPmDunUsZM1BZsAiXbIEouAJz1XjlysUQG-0p9969zYCvUm2tqWkA1BFVU2UqvjMAaBSgj10VkZzvcAbZB8nQf_mwRyg

Auth＝

DQAAAHcAAAClSiMWRfKAonW8zIytZ7NEizJNMQZojiNqsDxm3elei36
MV7GzM72bMiqdQawt8FcmxySIt75kfLxcis5BZnNCsyVuCwKM-DtNZcToUtm9IWoJyvNbUD9UTFYZPdBu1OyXsfY_QJHZfZdAT2QC
cExSIYKMvLfhhit9RPz4Gk2xlQ/n

Auth那一項(xiàng)后面的值就是token啦，可以不被砍頭了。

附錄：已知的Google服務(wù)及服務(wù)名

Calendar Data API	cl
Google Base Data API	gbase
Blogger Data API	blogger
Contacts Data API	cp
Documents List Data API	writely
Picasa Web Albums Data API	lh2
Google Apps Provisioning API	apps
Spreadsheets Data API	wise
YouTube Data API	youtube

前文說道開發(fā)一個(gè)Gadget可以分為兩個(gè)步驟：先寫界面的XML文件，再寫邏輯部分的JavaScript。我們就遵循這個(gè)步驟來寫一個(gè)再簡單也不過的Gadget。

用到的工具有兩個(gè)，一個(gè)是隨Google Desktop SDK附帶的Gadget Designer，用來編寫并有限的預(yù)覽界面，還可以調(diào)試JavaScript（這個(gè)就更有限了）；一個(gè)是Google Desktop，用來測試寫好的Gadget。下面要寫的例子是我在為某研究院某個(gè)項(xiàng)目策劃階段作POC時(shí)所寫的一個(gè)小例子，可以顯示一個(gè)Google用戶的Picasa相冊中的Album名稱和縮略圖。雖然很小，但包含了Google賬戶的自動登錄，顯示網(wǎng)絡(luò)圖片，XmlHttpRequest的使用等很多實(shí)用技巧。整個(gè)完成之后是這個(gè)樣子：

 

請跟我一起來。現(xiàn)在打開Gadget Designer，選擇File->New Gadget，輸入了名稱“Picasa”之后，就可以看到一個(gè)完整Gadget的雛形了。你可以找到這個(gè)項(xiàng)目所在的文件夾，雙擊其中的gadget.gmanifest，此時(shí)如果你已經(jīng)安裝了Google Desktop，就可以看到Desktop自動啟動，并把這個(gè)很“白”的Gadget（別笑，除了一張白色背景圖片以外，確實(shí)什么也沒有）顯示在Sidebar中。如圖：

到項(xiàng)目文件夾里可以看到一個(gè)main.xml文件和一個(gè)main.js文件。我們的界面就是在main.xml文件里指定的，打開它，可以看見它指定了一張GadgetDesigner幫我們生成的白色png圖片作背景，還指定了我們要導(dǎo)入哪些個(gè).js文件。我們來小改兩個(gè)地方：

一是把view的height改成250，二是給img元素添加一個(gè)屬性name并給一個(gè)值，就像這樣：

 

然后雙擊gadget.gmanifest，看看更改效果：

乍一看貌似沒什么改變，但是注意看我用黑色線圈出來的那一條橫杠，那是我們的Gadget的下邊沿，說明它的高度還是變化了，但是白色的背景沒有變，因?yàn)槲覀儧]有改變背景圖片的大小?，F(xiàn)在通過.js文件中代碼的方式來改變背景圖片的高度，可以看出些有意思的東西。

打開main.js文件，你應(yīng)該會看到一個(gè)view_onOpen()函數(shù)，這就是Gadget啟動時(shí)會自動調(diào)用的第一個(gè)函數(shù)（好吧，并不嚴(yán)格，但是在調(diào)用的順序上，它的確是相當(dāng)靠前的），我們就在這個(gè)函數(shù)內(nèi)部添加下面這一句：

再雙擊gadget.gmanifest運(yùn)行看看，白色背景也變高了吧。

我知道你一定會問，代碼里的bgImage是什么東西？怎么沒見在任何地方聲明這個(gè)變量，也沒見任何地方作初始化呢？回想我們剛才在main.xml文件里做了什么？我們給背景圖片取了一個(gè)名字，叫bgImage，而且別懷疑，你在代碼里訪問的這個(gè)bgImage，正是那張圖片！背后的工作就是Gadget Host通過JavaScript引擎為我們做的，凡是在.xml文件里放置的東西（無論什么，圖片也好，按鈕也好，一個(gè)抽象的div也好），只要你給了一個(gè)name屬性，在JavaScript代碼中就可以直接使用這個(gè)名字來訪問該對象（前提是你給的名字得是獨(dú)一無二的），這與瀏覽器中隨時(shí)可以訪問document對象而不用做任何聲明一樣，那是瀏覽器這個(gè)運(yùn)行環(huán)境提供的對象，隨時(shí)可用。

另一個(gè)值得注意的地方是在.xml文件里，屬性的值都必須加上引號，像height=”250”（因?yàn)槟抢锸褂玫氖菢?biāo)準(zhǔn)的xml語法），而在JavaScript代碼中，就要根據(jù)屬性具體的類型來決定，像高度這種整數(shù)型的值，就不用加。

你可能還會問，那么bgImage這個(gè)對象，是什么類型的，它有些什么屬性和方法可供我使用呢？它是一個(gè)img類型的對象，參考http://code.google.com/intl/zh-CN/apis/desktop/docs/gadget_apiref.html這個(gè)鏈接，這也是Google Desktop Gadget的API參考頁面，列出了Gadget Host提供的各種對象屬性和方法的說明（雖然事實(shí)驗(yàn)證，Google自己列的這些都不全面，后話）。

最后叮囑一句：盡管main.xml文件里的東西（什么img啊，以后還會加進(jìn)div啊，checkbox之類的東西）看起來多么的像HTML，Gadget都和Web沒有天然的聯(lián)系。Google自己發(fā)布了一些Gadget，例如Gmail和Google Docs，外觀與這兩個(gè)服務(wù)的網(wǎng)頁非常像，再加上Gadget也主要使用JavaScript開發(fā)（也少不了Universal Gadget跟著摻合），間接導(dǎo)致了總有人把Gadget顯示的地方考慮成一個(gè)小的瀏覽器窗口，而想把Web的一些東西簡單的放在這里，到底行不行呢？李寧說：一切皆有可能。阿迪說：沒有不可能。匹克說：我能，無限可能。我要說：可能，但很難（笑）。

所以在編寫Gadget的時(shí)候，最好的方法是把它當(dāng)成純粹的桌面程序，忘掉Web的那一套。

這一節(jié)給大家入個(gè)門，下一節(jié)開始說說在Gadget中怎么做Google帳戶的登錄，還會很羅嗦的，請見諒（笑）。

在Gadget開發(fā)人員看來——我當(dāng)然是指你我這樣的IT民工，來開發(fā)一個(gè)Gadget的人，而不是Google大樓里成天琢磨怎么和微軟對著干的那幫子人——一個(gè)Gadget由三大部分組成：描述UI的一系列.xml文件；存放程序邏輯的.js文件以及資源。

下面是一個(gè)Gadget項(xiàng)目在Google Desktop Disigner里面的結(jié)構(gòu)截圖。

資源這東西好理解，無非是程序要用到的各種圖片啦，字符串啦等等。讀者：字符串？什么意思？答：把程序會用到的一系列字符串統(tǒng)一存放，想引用的時(shí)候使用一個(gè)常量名字就可以，而不必在需要這些字符串的地方每次都重寫一遍，和Java中的property文件作用類似。

其余的兩部分會分節(jié)來詳細(xì)講解。

當(dāng)然說只有三部分，是指我們大多只關(guān)心這么多，實(shí)際上還有第四部分，一個(gè)Gadget Settings文件，其中大多是關(guān)于這個(gè)Gadget的元信息，什么作者啊，創(chuàng)建日期啊，uuid啊，戶口所在地啊，最高學(xué)歷啊，婚姻狀況啊，哦，我給說成簡歷了（笑）。

前面也說到過，一個(gè)Gadget其實(shí)就是一個(gè)桌面應(yīng)用程序（再一次的，不管寫起來某些語法多么得像HTML，Gadget與Web都沒有天然的聯(lián)系），只不過這個(gè)程序在Gadget Host的管理之下，行話叫“托管”。Windows下沒有單獨(dú)的Gadget Host，它被合并在Google Desktop里面（算是另一種捆綁吧）。而Linux下的確有干干凈凈的Gadget Host，且有源碼下載，我們所有對Gadget的理解也都源于這個(gè)版本和相關(guān)的文檔。

那么在Gadget Host看來，一個(gè)Gadget是什么東西呢？

以我寫的一個(gè)小Picasa Gadget為例，在Picasa Gadget初次加載之前，它是一個(gè).gg的壓縮包（其實(shí)就是一個(gè)標(biāo)準(zhǔn)的zip包，被改了后綴名而已），Gadget Host會從中讀取需要的文件，然后做相應(yīng)的解釋。

Gadget Host可以看成只有兩部分組成：一個(gè)UI的渲染器和一個(gè)JavaScript引擎。

說UI渲染器之前就不得不回頭重提剛才說到的一個(gè)Gadget包括了一系列.xml文件這件事。實(shí)際上這些.xml文件就是用來指定你想寫的Gadget的界面的，就是說，你的Gadget跑起來以后長成什么樣子，是由這些個(gè).xml文件來決定的（當(dāng)然，嚴(yán)格說來可以使用JavaScript在運(yùn)行時(shí)改變一些內(nèi)容，但請不要抬杠，笑）。

這些.xml文件中最主要的是main.xml這個(gè)文件，你的Gadget窗口有多大，在什么位置有幾個(gè)按鈕，列表有沒有滾動條，背景是什么顏色等等，都在這里指定。還包括這些東西上的事件監(jiān)聽函數(shù)也一并在這里聲明（不知為何，讓我莫名的想起微軟的MFC，當(dāng)然，嚴(yán)格說來可以使用JavaScript在運(yùn)行時(shí)動態(tài)改變這些內(nèi)容，但請不要再次抬杠，笑）。

UI渲染器干什么呢？就是來把這個(gè).xml所要求的界面轉(zhuǎn)換成具體的系統(tǒng)調(diào)用，讓操作系統(tǒng)來完成繪圖（好吧好吧，你喜歡嚴(yán)格，那我告訴你，Linux版本下首先被轉(zhuǎn)換為Qt的C++類，由Qt來發(fā)起對系統(tǒng)繪圖的調(diào)用）。

既然Gadget的程序邏輯都使用JavaScript來編寫，理所應(yīng)當(dāng)?shù)模珿adget Host必然要包含一個(gè)JavaScript解釋器來解釋這些代碼，這個(gè)解釋器也被叫做JavaScript引擎。Gadget Host里確實(shí)有這么個(gè)東西，叫做Spider Monkey，它恰好也是FireFox所使用的JavaScript引擎。廣義上說，一個(gè)引擎的作用主要是解釋它遇到的一切JavaScript代碼，如果代碼使用到核心JavaScript的功能和對象，它便直接提供；如果代碼使用到了一些依賴于底層的對象（例如Gadget Host就提供了很多專有的JavaScript對象和方法供使用，這些都是核心JavaScript之外的東西），則引擎還要負(fù)責(zé)轉(zhuǎn)發(fā)這樣的請求（你可以說，這實(shí)際上是適配器做的事，我這樣簡化有助于理解，請不要一再抬杠，笑）。

也可以這樣從邏輯上看Gadget的組成：即一個(gè)Gadget就是一組圖形界面，加這些界面上每個(gè)控件（按鈕啊，列表啊，輸入框等等）的事件監(jiān)聽函數(shù)，這種界面描述與事件邏輯分離的程序模型，和微軟的XAML+C#簡直如出一轍。因此一個(gè)Gadget的開發(fā)實(shí)際上也就可以分為這兩大步驟：先寫界面的XML文件，再寫邏輯部分的JavaScript。下面一節(jié)就用一個(gè)小例子來看看具體如何做。別嫌我說得太詳細(xì)哦。

去年這一年被研究生院和所里揪著干了不少自己并不擅長的事，其中就包括為各種大小活動設(shè)計(jì)PPT，邀請函，節(jié)目表之類的東西。年底了，拿出來看看也能理一理自己從無到有，從門外漢到菜鳥的成長過程。共賞，共析哈。

最早的一張，元旦晚會時(shí)為模特隊(duì)做的。本來他們自己做了一套共計(jì)3張的PPT，趕巧我這張已經(jīng)做好了，便讓他們自己選，結(jié)果還是選了我的，呵呵。

 

同一場晚會為舞蹈隊(duì)做的，沒太多東西，只是字體和配色斟酌了一陣子。

 

青年博客大賽決賽頒獎晚會的主題PPT，剛提交第一版便遭到老師表揚(yáng)，結(jié)果一點(diǎn)修改都沒有做便獲通過。

 

同一場晚會的領(lǐng)導(dǎo)致辭圖，風(fēng)格還挺一致的吧？（笑）

 

仍然是博客大賽決賽頒獎晚會，那一次晚會因?yàn)橥庹埞?jié)目比較多，整體水平著實(shí)不低呢。

 

計(jì)算所青年歌手大賽的節(jié)目單，其實(shí)參考了很有名氣的設(shè)計(jì)，所以才能做成這個(gè)樣子，不敢專美，特此聲明。

 

計(jì)算所青歌賽的主題PPT，多虧有設(shè)計(jì)的四大原則幫忙啊。后來一個(gè)計(jì)算所的師兄還問我把這張片子討了去，說是只看一眼就喜歡上了里面的女孩，還一個(gè)勁的問我她是誰，是咱所的么，我趕緊解釋說不是不是……

 

最近一次為街舞社的表演做的PPT，發(fā)現(xiàn)自己的風(fēng)格算是定型了，怎么看都似曾相識，當(dāng)然也可以說，是黔驢技窮了……

按：系列文章，將談及Google Gadget的體系結(jié)構(gòu)和開發(fā)入門，后期還會有和類似技術(shù)Mozilla Prism的對比。

開始之前先澄清一件事，這里所說的Gadget實(shí)際上是指Google Desktop Gadget，而不是指在iGoogle或者FaceBook上運(yùn)行的Gadget，那個(gè)叫做Universal Gadget。

細(xì)說起來，其實(shí)Gadget和Universal Gadget不僅名稱不同，在實(shí)現(xiàn)上也完全是兩回事。從使用者的角度看，Univeral Gadget就是一個(gè)HTML的頁面，只不過在顯示的時(shí)候是實(shí)時(shí)從iGoogle之類的容器網(wǎng)站上下載過來并展現(xiàn)在一個(gè)iframe里面的。而Desktop Gadget則是一個(gè)不折不扣的桌面應(yīng)用程序（雖然運(yùn)行在Google Desktop這個(gè)容器中）。

從開發(fā)人員的角度看，Universal Gadget是一個(gè)JavaScript文件和XML文件的集合，由容器網(wǎng)站（例如iGoogle，Facebook等等）來渲染成HTML頁面并呈現(xiàn)給最終用戶。在一個(gè)Universal Gadget中使用的技術(shù)都是標(biāo)準(zhǔn)的Web技術(shù)，其能量也限制在瀏覽器的框架中。

而在開發(fā)一個(gè)Desktop Gadget時(shí)，雖然也使用XML文件來指定程序的UI，使用JavaScript來實(shí)現(xiàn)程序的邏輯，但與Web或者瀏覽器都沒有天然的聯(lián)系，說是完全的另一套程序開發(fā)體系也不為過（使用的XML語法與Universal Gadget不同，能夠使用的JavaScript的對象及功能也不同）。

但另一方面的情況導(dǎo)致兩者時(shí)常被人混為一談，那就是，一個(gè)Universal Gadget是可以被加載到Desktop Gadget的面板中并正常運(yùn)行的（嚴(yán)格的說只有一部分），而一部分Desktop Gadget也可以加載到iGoogle網(wǎng)站中運(yùn)行（因而使它看上去像一個(gè)Universal Gadget，當(dāng)然需要系統(tǒng)已安裝了Google Desktop才可以）。

書歸正傳，下面就來說Gadget到底是什么，以及它的體系結(jié)構(gòu)和背后思想。

（注：以下如果沒有特別指明，提起Gadget全都是指Desktop Gadget，而iGoogle上的Gadget會指明為Universal Gadget）