Support Vector Machines 簡介 林宗勳.PDFVIP

Support Vector Machines 簡介 林宗勳 (daniel@.tw) 前言 Support Vector Machines(支持向量機，以下都以SVM稱呼)是一種分類 (Classification)演算法，由 Vapnik等根據統計學習理論提出的一種新的機器學習 方法。 SVM 在解決小樣本、非線性及高維模式識別問題中表現出許多特有的優勢。已 經應用於手寫體識別、三維目標識別、人臉識別、文本圖像分類等實際問題中， 性能優於已有的學習方法，表現出良好的學習能力。從有限訓練樣本得到的決策 規則對獨立的測試集仍能夠得到較小的誤差。 SVM 的概念 簡單來說，SVM 想要解決以下的問題：找出一個超平面(hyperplane) ，使之將兩 個不同的集合分開。為什麼使用超平面這個名詞，因為實際資料可能是屬於高維 度的資料，而超平面意指在高維中的平面。 以二維的例子來說，如下圖，我們希望能找出一條線能夠將黑點和白點分開，而 且我們還希望這條線距離這兩個集合的邊界(margin)越大越好，這樣我們才能夠 很明確的分辨這個點是屬於那個集合，否則在計算上容易因精度的問題而產生誤 差。 接下來我們將用更「數學」一點的方式來描述上面的問題 { } d { } 假設我們有一堆點集合x y i, , n1,..., and i i ∈ x R∈, +yi −1, 1 i 我們希望能找到一條直線f x w x (b ) − T 使所有y −1的點落在 的這 i ( f) x 0 一邊，且使所有y + 1的點落在 的這一邊，這樣我們就可以根據 的 i ( f) x 0 f (x ) 正負號來區分這個點是屬於這兩個集合之中的那一個。我們把這樣的超平面稱為 separating hyperplane ，而距離兩邊邊界最大的就稱為optimal separating hyperplane (OSH) 。接下來的問題就是我們要如何找出這個超平面。 Support Hyperplane 在解決這個問題之前，我先介紹一個新名詞： support hyperplane support hyperplane 是指與optimal separating hyperplane 平行，並且最靠近兩邊的 超平面。以上面二維的例子來說，那兩條虛線就是support hyperplane 。我們將 support hyperplane 寫成如下的式子： w x b T + δ w x b T − δ 這是一個有過多待解參數的問題(over-parameterized problem) 。假設我們對x, b,δ 都乘上任意一個常數，等式仍然成立，也就是說有無限多組的x, b,δ 滿足條件。