這回是幫自己家小妞的網店做的店標,宣傳什么的,所以風格相似恰恰是我想要的。

 

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

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

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

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

文本分類本質上也是一個模式識別的問題，因此我想借用一個更直觀的例子來說說特征選擇和權重量化到底各自是什么東西，當然，一旦解釋清楚，你馬上就會覺得文本分類這東西實在白癡，實在沒什么技術含量，你也就不會再繼續看我的技術博客，不過我不擔心，因為你已經踏上了更光明的道路（笑），我高興還來不及。

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

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

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

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

   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個位置比其他位置更重要，而相對的，第1個位置又比第3個位置更重要。

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

（第1個位置，第3個位置，第4個位置，第5個位置，第6個位置）

當然，具體的第3個位置是指紋中的哪個位置你自己總得清楚。

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

我想一定是“權重“這個詞誤導了所有人，讓大家以為TFIDF計算出的值代表的是特征的重要程度，其實完全不是。例如我們有一位男同學，他的指紋向量是：

（10，3，4，20，5）

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

（10，20，4，20，5）

看看，第1個位置得分（10）又比第3個位置（20）低了，那這兩個位置到底哪個更重要呢？答案是第1個位置更重要，但這不是在特征權重計算這一步體現出來的，而是在我們特征選擇的時候就確定了，第1個位置比第3個位置更重要。

因此要記住，通過TFIDF計算一個特征的權重時，該權重體現出的根本不是特征的重要程度！

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

（10， 3，4，20，5）

（10，20，4，20，5）

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

在文本分類中也是如此，比如我們的系統特征集合只有兩個詞：

（經濟，發展）

這兩個詞是使用卡方檢驗（特征選擇）選出來的，有一篇文章的向量形式是

（2，5）

另一篇

（3，4）

這兩個向量形式就是用TFIDF算出來的，很容易看出兩篇文章不是同一篇，為什么？因為他們的特征權重根本不一樣，所以說權重代表的是差別，而不是優劣。想想你說“經濟這個詞在第二篇文章中得分高，因此它在第二篇文章中比在第一篇文章中更重要“，這句話代表什么意義呢？你自己都不知道吧（笑）。

所以，當再說起使用TFIDF來計算特征權重時，最好把“權重“這個字眼忘掉，我們就把它說成計算得分好了（甚至”得分“也不太好，因為人總會不自覺的認為，得分高的就更重要），或者就僅僅說成是量化。

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

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

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

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

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

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

多個超平面把空間劃分為多個區域，每個區域對應一個類別，給一篇文章，看它落在哪個區域就知道了它的分類。

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

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

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

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

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

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

而且現在DAG方法根節點的選取（也就是如何選第一個參與分類的分類器），也有一些方法可以改善整體效果，我們總希望根節點少犯錯誤為好，因此參與第一次分類的兩個類別，最好是差別特別特別大，大到以至于不太可能把他們分錯；或者我們就總取在兩類分類中正確率最高的那個分類器作根節點，或者我們讓兩類分類器在分類的時候，不光輸出類別的標簽，還輸出一個類似“置信度”的東東，當它對自己的結果不太自信的時候，我們就不光按照它的輸出走，把它旁邊的那條路也走一走，等等。

大Tips：SVM的計算復雜度

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

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

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

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

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

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

在信息增益中，重要性的衡量標準就是看特征能夠為分類系統帶來多少信息，帶來的信息越多，該特征越重要。

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

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

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

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

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

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

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

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

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

因此有這樣兩個條件熵的表達式：

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

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

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

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

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

另一半就可以展開為：

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

 

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

 

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

以我們人類的常識來判斷，說有一萬個點都符合某種規律（因而線性可分），有一個點不符合，那這一個點是否就代表了分類規則中我們沒有考慮到的方面呢（因而規則應該為它而做出修改）？

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

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

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

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

 

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

因為松弛變量是非負的，因此最終的結果是要求間隔可以比1小。但是當某些點出現這種間隔比1小的情況時（這些點也叫離群點），意味著我們放棄了對這些點的精確分類，而這對我們的分類器來說是種損失。但是放棄這些點也帶來了好處，那就是使分類面不必向這些點的方向移動，因而可以得到更大的幾何間隔（在低維空間看來，分類邊界也更平滑）。顯然我們必須權衡這種損失和好處。好處很明顯，我們得到的分類間隔越大，好處就越多。回顧我們原始的硬間隔分類對應的優化問題：

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

而有人喜歡用

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

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

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

二是松弛變量的值實際上標示出了對應的點到底離群有多遠，值越大，點就越遠。

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

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

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

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

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

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

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

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

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

可分？還是不可分？——支持向量機

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

有！其思想說來也簡單，來用一個二維平面中的分類問題作例子，你一看就會明白。事先聲明，下面這個例子是網絡早就有的，我一時找不到原作者的正確信息，在此借用，并加進了我自己的解說而已。

例子是下面這張圖：

我們把橫軸上端點a和b之間紅色部分里的所有點定為正類，兩邊的黑色部分里的點定為負類。試問能找到一個線性函數把兩類正確分開么？不能，因為二維空間里的線性函數就是指直線，顯然找不到符合條件的直線。

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

顯然通過點在這條曲線的上方還是下方就可以判斷點所屬的類別（你在橫軸上隨便找一點，算算這一點的函數值，會發現負類的點函數值一定比0大，而正類的一定比0小）。這條曲線就是我們熟知的二次曲線，它的函數表達式可以寫為：

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

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

g(x)=f(y)=ay

在任意維度的空間中，這種形式的函數都是一個線性函數（只不過其中的a和y都是多維向量罷了），因為自變量y的次數不大于1。

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

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

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

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

用一個具體文本分類的例子來看看這種向高維空間映射從而分類的方法如何運作，想象一下，我們文本分類問題的原始空間是1000維的（即每個要被分類的文檔被表示為一個1000維的向量），在這個維度上問題是線性不可分的。現在我們有一個2000維空間里的線性函數

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

注意向量的右上角有個 ’哦。它能夠將原問題變得可分。式中的 w^’和x^’都是2000維的向量，只不過w^’是定值，而x^’是變量（好吧,嚴格說來這個函數是2001維的,哈哈），現在我們的輸入呢，是一個1000維的向量x，分類的過程是先把x變換為2000維的向量x^’，然后求這個變換后的向量x^’與向量w^’的內積，再把這個內積的值和b相加，就得到了結果，看結果大于閾值還是小于閾值就得到了分類結果。

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

如果有這樣的函數，那么當給了一個低維空間的輸入x以后，

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

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

這兩個函數的計算結果就完全一樣，我們也就用不著費力找那個映射關系，直接拿低維的輸入往g(x)里面代就可以了（再次提醒，這回的g(x)就不是線性函數啦，因為你不能保證K(w,x)這個表達式里的x次數不高于1哦）。

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

回想我們上節說的求一個線性分類器，它的形式應該是：

現在這個就是高維空間里的線性函數（為了區別低維和高維空間里的函數和向量，我改了函數的名字，并且給w和x都加上了 ’），我們就可以用一個低維空間里的函數（再一次的，這個低維空間里的函數就不再是線性的啦）來代替，

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

明白了以上這些，會自然的問接下來兩個問題：

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

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

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

對第二個問題的解決則引出了我們下一節的主題：松弛變量。

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

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

g(x)=wx+b

使得所有屬于正類的點x₊代入以后有g(x₊)≥1，而所有屬于負類的點x_-代入后有g(x_-)≤-1（之所以總跟1比較，無論正一還是負一，都是因為我們固定了間隔為1，注意間隔和幾何間隔的區別）。代入g(x)后的值如果在1和-1之間，我們就拒絕判斷。

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

你肯定能看出來，一旦求出了w（也就求出了b），那么中間的直線H就知道了（因為它就是wx+b=0嘛，哈哈），那么H1和H2也就知道了（因為三者是平行的，而且相隔的距離還是||w||決定的）。那么w是誰決定的？顯然是你給的樣本決定的，一旦你在空間中給出了那些個樣本點，三條直線的位置實際上就唯一確定了（因為我們求的是最優的那三條，當然是唯一的），我們解優化問題的過程也只不過是把這個確定了的東西算出來而已。

樣本確定了w，用數學的語言描述，就是w可以表示為樣本的某種組合：

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

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

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

但是上面的式子還不夠好，你回頭看看圖中正樣本和負樣本的位置，想像一下，我不動所有點的位置，而只是把其中一個正樣本點定為負樣本點（也就是把一個點的形狀從圓形變為方形），結果怎么樣？三條直線都必須移動（因為對這三條直線的要求是必須把方形和圓形的點正確分開）！這說明w不僅跟樣本點的位置有關，還跟樣本的類別有關（也就是和樣本的“標簽”有關）。因此用下面這個式子表示才算完整：

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

其中的y_i就是第i個樣本的標簽，它等于1或者-1。其實以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于0（不等于0才對w起決定作用），這部分不等于0的拉格朗日乘子后面所乘的樣本點，其實都落在H1和H2上，也正是這部分樣本（而不需要全部樣本）唯一的確定了分類函數，當然，更嚴格的說，這些樣本的一部分就可以確定，因為例如確定一條直線，只需要兩個點就可以，即便有三五個都落在上面，我們也不是全都需要。這部分我們真正需要的樣本點，就叫做支持（撐）向量！（名字還挺形象吧，他們“撐”起了分界線）

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

 

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

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

發現了什么？w不見啦！從求w變成了求α。

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

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

（式1）

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

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

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

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

（式2）

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

一下子提了這么多術語，實在不是為了讓大家以后能向別人炫耀學識的淵博，這其實是我們繼續下去的一個重要前提，因為在動手求一個問題的解之前（好吧，我承認，是動計算機求……），我們必須先問自己：這個問題是不是有解？如果有解，是否能找到？

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

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

因為我們實際上并不知道該怎么解一個帶約束的優化問題。如果你仔細回憶一下高等數學的知識，會記得我們可以輕松的解一個不帶任何約束的優化問題（實際上就是當年背得爛熟的函數求極值嘛，求導再找0點唄，誰不會啊？笑），我們甚至還會解一個只帶等式約束的優化問題，也是背得爛熟的，求條件極值，記得么，通過添加拉格朗日乘子，構造拉格朗日函數，來把這個問題轉化為無約束的優化問題云云（如果你一時沒想通，我提醒一下，構造出的拉格朗日函數就是轉化之后的問題形式，它顯然沒有帶任何條件）。

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

聰明，可以，實際上我們也正是這么做的。下一節就來說說如何做這個轉化，一旦轉化完成，求解對任何學過高等數學的人來說，都是小菜一碟啦。

上節說到我們有了一個線性分類函數，也有了判斷解優劣的標準——即有了優化的目標，這個目標就是最大化幾何間隔，但是看過一些關于SVM的論文的人一定記得什么優化的目標是要最小化||w||這樣的說法，這是怎么回事呢？回頭再看看我們對間隔和幾何間隔的定義：

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

幾何間隔：

 

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

而凡是求一個函數的最小值（或最大值）的問題都可以稱為尋優問題（也叫作一個規劃問題），又由于找最大值的問題總可以通過加一個負號變為找最小值的問題，因此我們下面討論的時候都針對找最小值的過程來進行。一個尋優問題最重要的部分是目標函數，顧名思義，就是指尋優的目標。例如我們想尋找最小的||w||這件事，就可以用下面的式子表示：

但實際上對于這個目標，我們常常使用另一個完全等價的目標函數來代替，那就是：

(式1)

不難看出當||w||²達到最小時，||w||也達到最小，反之亦然（前提當然是||w||描述的是向量的長度，因而是非負的）。之所以采用這種形式，是因為后面的求解過程會對目標函數作一系列變換，而式（1）的形式會使變換后的形式更為簡潔（正如聰明的讀者所料，添加的系數二分之一和平方，皆是為求導數所需）。

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

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

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

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

但我們常常習慣讓式子的值和0比較，因而經常用變換過的形式：

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

因此我們的兩類分類問題也被我們轉化成了它的數學形式，一個帶約束的最小值的問題：

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

按:之前的文章重新匯編一下,修改了一些錯誤和不當的說法，一起復習,然后繼續SVM之旅.

（一）SVM的八股簡介

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

以上是經常被有關SVM 的學術文獻引用的介紹，有點八股，我來逐一分解并解釋一下。

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

所謂VC維是對函數類的一種度量，可以簡單的理解為問題的復雜程度，VC維越高，一個問題就越復雜。正是因為SVM關注的是VC維，后面我們可以看到，SVM解決問題的時候，和樣本的維數是無關的（甚至樣本是上萬維的都可以，這使得SVM很適合用來解決文本分類的問題，當然，有這樣的能力也因為引入了核函數）。

結構風險最小聽上去文縐縐，其實說的也無非是下面這回事。

機器學習本質上就是一種對問題真實模型的逼近（我們選擇一個我們認為比較好的近似模型，這個近似模型就叫做一個假設），但毫無疑問，真實模型一定是不知道的（如果知道了，我們干嗎還要機器學習？直接用真實模型解決問題不就可以了？對吧，哈哈）既然真實模型不知道，那么我們選擇的假設與問題真實解之間究竟有多大差距，我們就沒法得知。比如說我們認為宇宙誕生于150億年前的一場大爆炸，這個假設能夠描述很多我們觀察到的現象，但它與真實的宇宙模型之間還相差多少？誰也說不清，因為我們壓根就不知道真實的宇宙模型到底是什么。

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

統計學習因此而引入了泛化誤差界的概念，就是指真實風險應該由兩部分內容刻畫，一是經驗風險，代表了分類器在給定樣本上的誤差；二是置信風險，代表了我們在多大程度上可以信任分類器在未知文本上分類的結果。很顯然，第二部分是沒有辦法精確計算的，因此只能給出一個估計的區間，也使得整個誤差只能計算上界，而無法計算準確的值（所以叫做泛化誤差界，而不叫泛化誤差）。

置信風險與兩個量有關，一是樣本數量，顯然給定的樣本數量越大，我們的學習結果越有可能正確，此時置信風險越小；二是分類函數的VC維，顯然VC維越大，推廣能力越差，置信風險會變大。

泛化誤差界的公式為：

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

公式中R(w)就是真實風險，R_emp(w)就是經驗風險，Ф(n/h)就是置信風險。統計學習的目標從經驗風險最小化變為了尋求經驗風險與置信風險的和最小，即結構風險最小。

SVM正是這樣一種努力最小化結構風險的算法。

SVM其他的特點就比較容易理解了。

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

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

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

下一節開始正式討論SVM。別嫌我說得太詳細哦。

 

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

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

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

^­C₁和C₂是要區分的兩個類別，在二維平面中它們的樣本如上圖所示。中間的直線就是一個分類函數，它可以將兩類樣本完全分開。一般的，如果一個線性函數能夠將樣本完全正確的分開，就稱這些數據是線性可分的，否則稱為非線性可分的。

什么叫線性函數呢？在一維空間里就是一個點，在二維空間里就是一條直線，三維空間里就是一個平面，可以如此想象下去，如果不關注空間的維數，這種線性函數還有一個統一的名稱——超平面（Hyper Plane）！

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

g(x)=wx+b

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

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

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

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

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

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

D_i=(x_i,y_i)

x_i就是文本向量（維數很高），y_i就是分類標記。

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

δ_i=y_i(wx_i+b)

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

首先注意到如果某個樣本屬于該類別的話，那么wx_i+b>0（記得么？這是因為我們所選的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)|）

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

這個公式是不是看上去有點眼熟？沒錯，這不就是解析幾何中點x_i到直線g(x)=0的距離公式嘛！（推廣一下，是到超平面g(x)=0的距離， g(x)=0就是上節中提到的分類超平面）

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

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

它的p-范數為

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

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

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

之所以如此關心幾何間隔這個東西，是因為幾何間隔與樣本的誤分次數間存在關系：

 

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

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

簡單的說,比較兩個int型或long型的數據沒有什么問題,可以用==來判斷,但對浮點數(float與double)來說,需要對Float.NaN和0.0這個兩個特殊數字作額外的處理。
Float.NaN嚴格說來不是一個數字（它的字面意思也就是Not a Number），但是因為這個值可以被保存在一個float型的變量中（因為它常常是除0的結果），所以暫且當它是個數字吧。但它與一般的浮點數有些許不同，就是兩個NaN用==比較的結果會得到false。
可以用下面的代碼驗證：

輸出結果為false

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


而當我們使用Float.compare()這個方法來比較兩個NaN時，卻會得到相等的結果。可以用下面的代碼驗證：

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

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

返回的結果是true和-1。看到了么，==認為正0和負0相等，而compare()方法認為正0比負0要大。所以對0的比較來說，==是更好的選擇。

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

如果你已經下載了我提供的源碼，就可以打開看看，對照實際效果來看代碼，應該很好理解。我們總計在界面上放了幾樣東西：

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

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

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

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

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

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

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

 

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

第二種方式比較傳統也比較少用，可以通過DOM對象訪問每個元素。

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

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

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

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

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

具體點，記得一個請求最重要的四部分數據么？url：就是該圖片的url；請求類型：因為是要求數據，自然是“GET”；請求頭：對本請求來說沒有；消息體：同樣沒有。

所以發請求的部分并不困難，待請求的狀態變為4，也就是說明回傳數據已到達的時候，就可以從請求的responseStream這個屬性得到圖片的二進制數據。假設在代碼中我們要顯示的圖片是<img name=”myImg”/>,記得么，使用名字可以直接訪問這個圖片，再假設我們的請求對象取名為xhRequest，像下面這樣：

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

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

這個函數我就不逐一分解了，相信你一定看得懂。

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

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

繼續第三節的路子，仍然使用XmlHttpRequest向Picasa服務發起請求，也要處理好四部分信息。

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

請求的類型：我們是要索取數據，因此這是一個查詢的動作，應該使用GET。

請求頭：只需要把token放進去就好。這樣來放：

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

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

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

 

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

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

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

具體代碼如下：

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

而album.js的內容大體如下：

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

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

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

上一節已經把響應的內容打印了出來，它的格式也很簡單，因此用下面的代碼很容易就可以把響應的內容轉成方便我們使用的形式，即一個map的形式，通過鍵值對來存儲：

在我們的相應回調函數里，就可以調用這個函數處理一下響應，從結果中取鍵為”Auth”這一項的值，并保存在Gadget Host為我們準備好的一個負責持久化的對象options中。找到上一節Main.prototype.login的代碼，把響應的回調函數改成下面的樣子：

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

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

下一節將向Picasa服務發起請求！

Google帳戶最早用來申請巨大的Gmail郵箱（如今看來，一般個大吧），隨著后來的Blogger，Picasa，Docs等各種服務上線，也就順路繼承了過來。現在使用一個Google帳戶，就可以同時使用這些服務。

既然我們打算寫一個從Picasa取相冊數據的Gadget，就免不了要先了解一些和Goolge帳戶有關的知識。因為Picasa的數據也是受保護的，并非誰要看都可以（公開的相冊除外哦，那都是炫耀冊，巴不得全天下人都看見呢），我們的程序也不例外，要想取到相冊的數據，程序必須向Google的服務器證明自己得到了相應用戶的授權。

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

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

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

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

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

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

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

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

調用這個函數就可以得到一個XmlHttpRequest的對象啦。

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

我們就要在Main.login()函數中寫我們取token的邏輯。

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

URL是說你的請求要發往哪里，既然我們要使用Google的服務，那當然要往Google那里發了，具體應該為：

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

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

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

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

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

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

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

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

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

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

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

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

在請求的回調函數中，目前只是先簡單的打印了相應的文本內容，實際上應該在這里做更多的事，詳情咱們下節再聊。如果你看到類似下面這樣的輸出內容，說明登錄的請求成功了。如果沒有成功，很可能是因為我已經換掉了用戶名和密碼，用你自己的Google帳戶試試看。

應該看到的內容：

SID＝

DQAAAHYAAADYQ4hToTAEYRu0uEXP9yXZ1uc_W3-kBtZFpug78XQDGiykOb-Sv2qdXtdUOL-
npRJm9SSq-AEvSBodrcuy3UwgFM8SX_z6fXzpGaJzHzQx5YTzR0AJHCEkFh
4yOoBFs0iCE2LI0LWQs6_2BFyIuLLMwRA8m3vfuVzNE3CHjrUHZA

LSID＝

DQAAAHgAAAClSiMWRfKAonW8zIytZ7NEizJNMQZojiNqsDxm3elei36MV
7GzM72bMiqdQawt8Fd1Dpp68p5bs1XYOXUPmDunUsZM1BZsAiXbIEouAJz1XjlysUQG-0p9969zYCvUm2tqWkA1BFVU2UqvjMAaBSgj10VkZzvcAbZB8nQf_mwRyg

Auth＝

DQAAAHcAAAClSiMWRfKAonW8zIytZ7NEizJNMQZojiNqsDxm3elei36
MV7GzM72bMiqdQawt8FcmxySIt75kfLxcis5BZnNCsyVuCwKM-DtNZcToUtm9IWoJyvNbUD9UTFYZPdBu1OyXsfY_QJHZfZdAT2QC
cExSIYKMvLfhhit9RPz4Gk2xlQ/n

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

附錄：已知的Google服務及服務名

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

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

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

 

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

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

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

 

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

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

打開main.js文件，你應該會看到一個view_onOpen()函數，這就是Gadget啟動時會自動調用的第一個函數（好吧，并不嚴格，但是在調用的順序上，它的確是相當靠前的），我們就在這個函數內部添加下面這一句：

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

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

另一個值得注意的地方是在.xml文件里，屬性的值都必須加上引號，像height=”250”（因為那里使用的是標準的xml語法），而在JavaScript代碼中，就要根據屬性具體的類型來決定，像高度這種整數型的值，就不用加。

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

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

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

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

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

下面是一個Gadget項目在Google Desktop Disigner里面的結構截圖。

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

其余的兩部分會分節來詳細講解。

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

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

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

以我寫的一個小Picasa Gadget為例，在Picasa Gadget初次加載之前，它是一個.gg的壓縮包（其實就是一個標準的zip包，被改了后綴名而已），Gadget Host會從中讀取需要的文件，然后做相應的解釋。

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

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

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

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

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

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

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

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

 

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

 

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

 

同一場晚會的領導致辭圖，風格還挺一致的吧？（笑）

 

仍然是博客大賽決賽頒獎晚會，那一次晚會因為外請節目比較多，整體水平著實不低呢。

 

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

 

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

 

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

按：系列文章，將談及Google Gadget的體系結構和開發入門，后期還會有和類似技術Mozilla Prism的對比。

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

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

從開發人員的角度看，Universal Gadget是一個JavaScript文件和XML文件的集合，由容器網站（例如iGoogle，Facebook等等）來渲染成HTML頁面并呈現給最終用戶。在一個Universal Gadget中使用的技術都是標準的Web技術，其能量也限制在瀏覽器的框架中。

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

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

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

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

Java號稱對Unicode提供天然的支持，這話在很久很久以前就已經是假的了（不過曾經是真的），實際上，到JDK5.0為止，Java才算剛剛跟上Unicode的腳步，開始提供對增補字符的支持。
現在的Unicode碼空間為U+0000到U+10FFFF，一共1114112個碼位，其中只有1,112,064 個碼位是合法的（我來替你做算術，有2048個碼位不合法），但并不是說現在的Unicode就有這么多個字符了，實際上其中很多碼位還是空閑的，到Unicode 4.0 規范為止，只有96,382個碼位被分配了字符（但無論如何，仍比很多人認為的65536個字符要多得多了）。其中U+0000 到U+FFFF的部分被稱為基本多語言面（Basic Multilingual Plane，BMP）。U+10000及以上的字符稱為補充字符。在Java中（Java1.5之后），補充字符使用兩個char型變量來表示，這兩個char型變量就組成了所謂的surrogate pair（在底層實際上是使用一個int進行表示的）。第一個char型變量的范圍稱為“高代理部分”（high-surrogates range,從"uD800到"uDBFF，共1024個碼位）, 第二個char型變量的范圍稱為low-surrogates range（從"uDC00到"uDFFF，共1024個碼位），這樣使用surrogate pair可以表示的字符數一共是1024的平方計1048576個，加上BMP的65536個碼位，去掉2048個非法的碼位，正好是1,112,064個碼位。

關于Unicode的碼空間實際上有一些稍不小心就會讓人犯錯的地方。比如我們都知道從U+0000到U+FFFF的部分被稱為基本多語言面（Basic Multilingual Plane，BMP），這個范圍內的字符在使用UTF-16編碼時，只需要一個char型變量就可以保存。仔細看看這個范圍，應該有65536這么大，因此你會說單字節的UTF-16編碼能夠表示65536個字符，你也會說Unicode的基本多語言面包含65536個字符，但是再想想剛才說過的surrogate pair，一個UTF-16表示的增補字符（再一次的，需要兩個char型變量才能表示的字符）怎樣才能被正確的識別為增補字符，而不是兩個普通的字符呢？答案你也知道，就是通過看它的第一個char是不是在高代理范圍內，第二個char是不是在低代理范圍內來決定，這也意味著，高代理和低代理所占的共2048個碼位（從0xD800到0xDFFF）是不能分配給其他字符的。
但這是對UTF-16這種編碼方法而言，而對Unicode這樣的字符集呢？在Unicode的編號中，U+D800到U+DFFF是否有字符分配？答案是也沒有！這是典型的字符集為方便編碼方法而做的安排（你問他們這么做的目的？當然是希望基本多語言面中的字符和一個char型的UTF-16編碼的字符能夠一一對應，少些麻煩，從中我們也能看出UTF-16與Unicode間很深的淵源與結合）。也就是說，無論Unicode還是UTF-16編碼后的字符，在0x0000至0xFFFF這個范圍內，只有63488個字符。這就好比最初的CPU被勉強拿來做多媒體應用，用得多了，CPU就不得不修正自己從硬件上對多媒體應用提供支持了。

盡管不情愿，但說到這里總還得扯扯相關的概念：代碼點和代碼單元。
代碼點（Code Point）就是指Unicode中為字符分配的編號，一個字符只占一個代碼點，例如我們說到字符“漢”，它的代碼點是U+6C49。
代碼單元（Code Unit）則是針對編碼方法而言，它指的是編碼方法中對一個字符編碼以后所占的最小存儲單元。例如UTF-8中，代碼單元是一個字節，因為一個字符可以被編碼為1個，2個或者3個4個字節；在UTF-16中，代碼單元變成了兩個字節（就是一個char），因為一個字符可以被編碼為1個或2個char（你找不到比一個char還小的UTF-16編碼的字符，嘿嘿）。說得再羅嗦一點，一個字符，僅僅對應一個代碼點，但卻可能有多個代碼單元（即可能被編碼為2個char）。
以上概念絕非學術化的繞口令，這意味著當你想以一種統一的方式指定自己使用什么字符的時候，使用代碼點（即你告訴你的程序，你要用Unicode中的第幾個字符）總是比使用代碼單元更好（因為這樣做的話你還得區分情況，有時候提供一個16進制數字，有時候要提供兩個）。
例如我們有一個增補字符？？？（哈哈，你看到了三個問號對吧？因為我的系統顯示不出這個字符），它在Unicode中的編號是U+2F81A，當在程序中需要使用這個字符的時候，就可以這樣來寫：

后面的for循環把這個字符的UTF-16編碼打印了出來，結果是
d87edc1a
注意到了嗎？這個字符變成了兩個char型變量，其中0xd87e就是高代理部分的值，0xdc1a就是低代理的值。