AI - Ch17 機器學習(5), 支持向量機 Support vector machine, SVM

SVM簡介
SVM是一種監督式學習的方法，可廣泛地應用於統計分類以及回歸分析。在解決小樣本、非線性及高維模式識別問題中表現出許多特有的優勢。基本上是這三年來最好的有監督學習算法了，因為支持向量機具有較完備的統計學習理論基礎。

SVM想要解決的問題
找出一個超平面(hyperplane)，使之將兩個不同的集合分開。以二維平面來說，我們希望能找出一條線能夠將兩種不同的點分開，而且我們還希望這條線距離這兩個集合的邊界越大越好。

*超平面：不用被超平面這個詞嚇到，超平面就是指在高維中的平面，因為通常訓練和測試的資料都是高維度的資料。

學svm應有的「感覺」
分類執行時我們應該關心靠近中間分割線的點(例如點C)，讓他們盡可能地遠離中間線，而不是在所有點(例如點A)上達到最優。
也就是說，是考慮局部，關心在兩類交界很難分辨的點，而不是考慮全局，因為考慮全局已經遠離的點可能通過調整中間線使其能夠更加遠離也對分類沒有更好的幫助。

定義問題 (用wiki加一點自己的看法)

我們考慮以下形式的n個點的訓練樣本

\mathcal{D}

\mathcal{D}=\{(\mathbf{x}_i,y_i)| \mathbf{x}_i \in \mathbb{R}^p, y_i \in \{-1,1\} \}_{i=1}^{n}

。

xi是你放進來的訓練樣本，P個維度，在平面中表示就是2維。
yi是-1或者+1，也就是分類結果，"-1"這類或"+1"那類，這個y不是下圖的座標軸y喔。

找一超平面用正負號來區分這個點是屬於這兩個集合之中的那一個，我們把這樣的超平面稱為分離超平面。(separating hyperplane)，而距離兩邊邊界最大的就稱為最佳分離超平面(optimal separating hyperplane)，而支持超平面(support hyperplane)是指與最佳分離超平面平行，並且最靠近兩邊的超平面。

\mathbf{w}\cdot\mathbf{x} - b=0

......分離超平面(separating hyperplane)

\mathbf{w}\cdot\mathbf{x} - b=1

......支持超平面[1](support hyperplane)

\mathbf{w}\cdot\mathbf{x} - b=-1

......支持超平面[2](support hyperplane)

舉例來說，在高中學的二維平面中，就是找到一直線ax+by+c=0，之後帶入各個點(x,y)，大於0就是"+1"這類，小於0就是"-1"這類。等式右邊的1和-1只是為計算方便而取的常量，其他常量只要互為相反數亦可。

找出最佳分離超平面的問題就等於找出相距最遠的支持超平面，兩支持超平面最遠距離

margin = 2d = 2/|w| 。
(二維空間中就是算高中數學的兩線距離，|d1-d2|/法向量長...)

算 2/|w|的極大值等價於算(1/2)*|w|^2的極小值。
(寫成這個形式是為了數學上表達的方便。)

同時為了使得樣本數據點都在超平面的間隔區以外，我們需要保證對於所有的i滿足其中的一個條件

\mathbf{w}\cdot\mathbf{x_i} - b \ge 1\qquad\mathrm{or}

\mathbf{w}\cdot\mathbf{x_i} - b \le -1\qquad\mathrm{}

這兩個式子可以寫成一個：

y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1, \quad 1 \le i \le n.\qquad\qquad (1)

現在尋找最佳超平面這個問題就變成了在（1）這個約束條件下最小化|w|.這是一個二次規劃QP (quadratic programming)最優化中的問題。
更清楚的表示：

\arg\min_{\mathbf{w},b}{||\mathbf{w}||^2\over2}

，滿足

y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1

其中

i = 1, \dots, n

。

主問題就這麼確定下來了，接下來就是用Lagrange duality把它解出來。
請待下回分解，累惹XD

[未完待續]

Pages

2015年3月25日星期三