Support Vector Machines(支持向量機)

支持向量機是最基礎同時也是最為知名的機器學習方法之一，本篇lecture note由簡至繁展開分述討論支持向量機的內容。

第一部分：二分類線性可分的最大間隔問題；

以什麼樣的分割超平面是好的分割超平面這個問題出發，將多類不可分的問題逐步簡化簡化再簡化，最終決定從尋找線性可分數據集的最大間隔分類超平面開始，雖然這個在圖上可以很容易理解並能直觀的找到我們感覺最好的答案，但當維度較高的時候，我們就會較難進行可視化，所以還得將其轉化為數學表示的形式，此處就是一步步將最大間隔的思想進行轉化為數學優化的形式，進而再對獲得的數學形式進行簡化求解；

第二部分：Lagrange對偶求解；

上面求解推導重點引入了Lagrange對偶求解的方式，雖然Lagrange對偶通常求的是原問題的一個下界，但是在SVM的優化形式中，Lagrange對偶求得的最優解等價於原問題的最優解,另外Lagrange對偶求解中的點積形式也為後續引入kernel SVM作鋪墊；這邊可以考慮一下對偶形式下如何理解最大分割超平面;

第三部分：將問題逐步泛化，當原數據存在噪音，數據並非完全可分的時候；

這一部分將問題慢慢變複雜,當問題不再線性可分,我們通過引入懲罰項來構建數學模型;(此處的推導和之前的類似,注意對偶形式的時候多了一個C，懲罰係數)，此處還有一個注意點就是hinge loss和引入懲罰項的優化形式的解的等價性問題；

第四部分：進一步泛化，當原問題是多分類問題，或者原數據需要複雜的非線性超平面才能分割時該如何處理；

對於多分類問題，常用的有兩種方法，一個就是構造多個二分類的SVM(常見的有OVA,OVO兩種形式);另外一個則是將最大margin的思想拓展到多分類的情況，然後通過求解單個優化式子來求解多分類問題(具體的可以參加SVM相關論文)。

對於複雜非線性分類超平面，SVM常常採用的是核方法 (Kernel trick)，核方法的本質可以理解為數據變換，將x變為f(x)，然後在新的空間中尋找最大間隔的線性分割超平面. 此處還有一些知識點例如：Mercer條件，如何判斷有效核函數以及常見的核函數也是很重要的，方便在使用工具包的時候了解參數的意義。

第五部分：一點點補充的知識點(參加ppt最後一頁)

文章鏈接：http://dl.acm.org/citation.cfm?id=944968https://cs.nju.edu.cn/wujx/paper/SVM.pdf

ppt鏈接：http://pan.baidu.com/s/1slfRtKxhttps://pan.baidu.com/s/1slGzDV3

推薦閱讀：