1. 關於SVM：SVM的理論背景

支持向量機(Support Vector Machines)是一種分類器，最早由Vapnik在
1979年提出，當時沒有得到重視，隨後Vapnik等人花了很長時間完善統計
模式識別的基本數學理論，隨着結構風險最小準則的提出，SVM的理論基
礎基本完備，終於引起注意。直到最近，它才成為一個研究上的熱點，並
開始得到非常廣泛的應用。和傳統的分類器如神經網絡相比，它從理論上
解決了神經網絡難以控制自身推廣能力的問題。說到這一點大家可能都有
體會，神經網絡的收斂條件是比較難定的，理論上，訓練時的分類誤差可
以一直減小，但是並不是在訓練時誤差越小，識別時的錯誤率就越小。為
什麼會這樣，說起來非常簡單，就是因為訓練的錯誤率，並不等於識別的
錯誤率，它們之間也不成簡單的正比例關係。因此難以控制，就會有過學
習現象的出現。

Vapnik極其推崇理論指導實際，強烈反對"只要在工程上有用就是正確
的"這種說法，這或許是他對神經網絡嗤之以鼻而窮數十年心力另起SVM這個
爐灶的原因所在。（說到這裡只有兩個字：弓雖，～～汗……）

支持向量機克服了推廣能力難以控制的問題，其根本就在於，找到了
計算實際識別中分類器錯誤率上界（注意只是上界）的方法。

關於具體的數學推導，可參考Vapnik著，張學工譯的“統計學習理
論的本質”，Savy已經在前面隆重推介過了。觀點明確，論證也很清晰，
可惜其中的數學推導比較複雜，偶到現在還是只能看個大概：（

大概說來，Vapnik等人推導出，分類器識別率的上界由訓練時的錯誤
率（也稱經驗風險）及分類器的複雜程度共同決定，而分類器的複雜度
，又是一個關於分類函數（Vapnik認為一個分類器等效於一族分類函數）
VC維的函數。這個複雜度對識別的影響，就是統計學習理論中所強調的結
構風險。

以二分類問題為例，在SVM的實際學習過程中，其目標是，找到一個
特徵空間的分類超平面，在兩類完全可分的條件下，使兩類之間的
"margin"最大。這個"margin"，就是訓練樣本到平面的最小距離的兩倍。
如果有一些樣本點是無法分開的，或者，有時為了達到最大化"margin"
的目的，需要犧牲一些樣本，而使"margin"儘可能大，這個時候，對
"margin"內部的點，在計算分類代價時要加懲罰。這樣一個過程，相當
於在經驗風險固定的情況下，最小化結構風險。

按我的理解，這樣的訓練過程，基本上可以說是有控制的，但是
仍然無法從理論上保證得到最小實際風險。不知道對不對，歡迎
大家指正。

2. 關於SVM：優化算法的研究

SVM的研究，包括具體應用、核函數的研究及算法優化三大主題（
也許有更多，恕鄙人孤陋寡聞）。由於應用往往由性能決定，因此先
說算法。

前文提到，尋找最優分類面，最大化"margin"是SVM的學習終點，但
是要實現談何容易。為了說明其中的難點，必須提到一些數學。

假設分類超平面為w(*)x-b=0，其中(*)為點積，根據分類公式：
f(x)=sgn(w(*)x-b)，將所有樣本分成兩類。這個超平面還有兩個平行的
超平面，分別定義為：

H1: y=w(*)x-b=1, H2: y=w(*)x-b=-1

在完全可分的情況下，如果不允許這兩個平面之間有樣本點，而允許平面
上有樣本點存在，則這兩個平面的距離就是上面說的"margin"。

數學上的目標至此定下來了，就是在平面之間無樣本點，平面上可以
有樣本點的條件下，不斷調整w和b，使兩個平面的距離最大。如果樣本非
完全可分，還要考慮分類懲罰，給每個樣本加入一個鬆弛變量。

暫時只考慮完全可分的情況，求解目標可寫為：

min||w(*)w||, subject to y(w(*)x-b)>=1, i=1...N

這是一個典型的二次優化問題。它的標準解法是有的，就是引入拉格
朗日算子把這些式子合併成一個方程，然後當方程關於w和b的偏導數為零
時，即得最優解。

問題不在這裡，問題是，一個樣本對應於一個約束條件方程，一個方
程要解出一個拉格朗日算子，那麼，如果樣本有10000個，這10000多個方
程，解起來是個什麼概念？

不要說我們有線性代數。一個10000×10000的浮點數矩陣(當然大
部分都是零)，就算只想一次放到計算機內存里，也實在是一件非常奢侈的
事情，何況大部分計算程序根本對付不了這麼大塊頭的東東，更不用提矩
陣相乘、求逆等等運算了。

因此SVM的首要任務就是：如何解決這個問題？直觀的看，當然是想辦
法把一個大規模的問題分解成一系列小規模問題，還要考慮效率等因素，
這方面的研究是比較多的。

比較有影響的算法包括Vapnik本人的Chunking算法，Mit的Osuna等人
提出的Osuna算法，及微軟的J.Platt提出的SMO算法等。這個問題根本是
個最優化問題。

目前SVM研究的幾個比較難以解決的問題有：

1）實現算法；
這個就不多說了

2）模型選擇；
即解決如何確定核函數參數和正則參數。

3）簡化SVM；
如何在保證學習機器推廣能力的基礎上，減少SV數目。加快決策過程。

4）多類分類；
雖然有很多方法，但目前就實驗結果來看，還是1VS1的好。

5）向無監督學習的推廣
理論和方法方面的研究都不多。

如果只是將SVM作為工具，建議用LIBSVM，VC++實現，寫得比較易懂，
容易修改。並提供了很多功能。

3. 關於SVM：核函數

SVM中的核函數是非常重要的。它大致有兩個作用，一是將線性分類面擴展
為非線性分類面，然後實現非線性可分；二是確保分類超平面是平滑的，避
免overfiting現象。

SVM的標準核函數有三個：多項式、RBF（徑向基函數）和多層感知機
,核函數和實際問題可能是有聯繫的。這三個核函數是不夠用的。其它
的比較經典的核函數算法包括：

Kernel Fisher Discriminant核函數(FD Kernel)；
Kernel Principal Component Analysis(PCA Kernel);
Relevance Vector Machines;
Kernel Independent Component Analysis (Kernel ICA);

關於核函數的研究，我所知不多，所用過的，只有FD Kernel,
這是一種基於類內類間判據的核函數，至少在樣本集稀疏的情況下，
效果要比標準核函數好得多。

以上關於核函數的說明，歡迎高人補充。

4. 關於SVM：一些感想和重要的網絡資源

關於SVM的應用，由於實在太多，我就不敢班門弄斧了。目前
應該主要有數據挖掘、分類、回歸等等。

Vapnik在推進統計學習理論研究的過程中有兩個比較著名的觀
點，一是不贊同"有用即合理"，二是下面這句話：

"Never try to solve a problem that is more general than the
one you actually want to solve!"

大概的意思，可能是一要有嚴格的理論指導，二是不要把具體問題轉
換成一個更一般化的問題來解決(可能是因為一般化的問題更難)。

因此，對於缺乏嚴格數學基礎的理論，如神經網絡，遺傳算法(這
個還好些)等，相信他是持不樂觀的態度的。貫穿統計學習理論的，就
是數學數學數學，只有推導，很少見到進化之類的觀點。不知道這個在
以後是否會有所變化。也許推動這個變化的，就是看到這篇的諸位也說
不定：）

下面是一些關於SVM的網絡資源。

http://www.cs.ualberta.ca/~newton/mlrg/links.html
幾乎所有研究SVM的牛人和著名的網站在上面都有收錄，推薦

http://svmlight.joachims.org/
SVMlight的網站，提供源碼和使用說明，如果下不了，可以向
joachims本人要，我這裡也有：）

http://www.csie.ntu.edu.tw/~cjlin/
有LIBSVM，是一個台灣人，這個人好像比較活躍。

http://www.research.microsoft.com/~jplatt/
從上面某個鏈接可以下SVM-SMO源碼，如果找不到就跟我要吧

還有一個osusvm的MATLAB工具箱，但是不開放源碼，是從LIBSVM
改寫過來的，網址找不到了，上GOOGLE搜一把吧。

http://www.ics.uci.edu/~mlearn/MLRepository.html
UCI Machine Learning Repository download
研究機器學習, 發表paper必備，推薦