筆記の筆記---如何不糾結計算過程來理解SVM

所以我關心的問題是怎麼把機器學慣用到我的研究中來，而不是去研發機器學習。對於我來說，很多東西我只需要在matlab上下載個工具包，然後寫個腳本，再點擊run就可以出來一堆也許很漂亮的結果了。甚至有很多搞心理學的人根本就不知道fMRI的信號是怎麼 產生的，仍然去做fMRI實驗，照樣處理數據，出來一個顯著的結果。

但我並不是說其中的各種原理和推算過程並不重要，而且我也反對上面說的那種無腦點擊的做法，我想說的是我們應該從中取我們所需的，不需要的東西就不必花時間去糾結。

相信很多學心理學的搞認知神經科學的時候，都會有覺得自己在學計算機的錯覺，至少我就有（藍瘦），但我一直致力於讓自己變得不那麼像學計算機的，因此我堅定的目標仍然是只要學我要用到的東西就可以了。

我在學習機器學習的時候，一開始就被各種公式計算推演搞得稀里糊塗的，但當我仔細想想，我好像並不需要這些啊，這些工具包裡面的計算，不是都有那些搞數學和計算機的人幫我做好了嗎（在此感謝各位計算機從業者，深覺你們的辛苦）？我只要知道裡面的原理和理論背景，知道我在用工具包的時候，每一步到底是做了什麼就可以了呀。

從此我發現了新大陸，哈哈。

不過事情並不就是那麼簡單的，那些計算過程其實是核心的東西，如果直接跳過，會導致自己的理解流於表面。因此我採取的做法就是儘力去看計算過程的每一步到底是在做什麼，而不是怎麼做的。我覺得對於學心理學的人來說，這樣就夠了。

關於SVM，有一個非常棒的介紹，來自於v_JULY_v的博客《支持向量機通俗導論（理解SVM的三層境界）》，本文就是根據這篇導論來做的筆記，但是沒有其中複雜的計算過程推演。但我自己的確是有認真看裡面的計算推演的，如果你只是想要對SVM有一個簡單的了解，那麼你只看我這篇筆記大概就夠了，但是如果想要理解更深刻，那我推薦你點進去好好看看。

--------以下正文---------

1.什麼是支持向量機？

顧名思義，支持向量機可以拆分為「支持向量」和「機」。

支持向量：首先它是一些向量，在二維平面里向量是一個個的點，如下圖：

中間的紅線是一個超平面（超平面在2D空間中顯示為一條直線），其實也是一個分類函數f(x)，假定藍色的點都是y=-1，紅色的點都是y=1，那麼這個分類函數的作用就是把這兩種不同值的點分開，而一個點到超平面之間的距離就代表分類的準確率（這個距離叫做幾何間隔），而我們總是希望這個準確率越大越好，換句話說，就是我們希望這n個點中間隔中最小的間隔最大化，這一點需要通過我們選擇的超平面來做到。

而SVM是通過最大間隔分類器Maximum Margin Classifier來設計決策最優分類超平面的，它會得出像下圖一樣的3個超平面：

我們的目的就是要做到上下的2個超平面與中間的最優化超平面之間的間隔最大化。

然後我們可以看到上下2條線上都有一些向量點，而這些向量點就叫做support vector，意思是「支撐」這兩個超平面的向量點。

機：其實就是「演算法」的意思，在機器學習領域，演算法常常被叫做「機」。

另外，SVM是是一種監督演算法。

在機器學習中，特徵的意思是輸入分類器的數據。

2.線性可分與線性不可分

首先要講清楚的是，線性可分是指只要一條直線就可以把空間中的所有點成功分類的情況，而線性不可分（即非線性）就是用一條直線不能成功分類的情況。

我們之前說我們要解決的問題是幾何間隔最大化，這是原始問題，這個問題的求解方法依靠下面的目標函數：

而到了這裡：

原始問題就變成了凸優化問題（亦即二次優化問題，即目標函數是二次的，約束條件是線性的），這可以用QP (QuadraticnProgramming)優化包解決，但因為這個問題的特殊結構，我們也可以用Lagrange Duality的方法把它變換到對偶變數(dual variable)的優化問題。因此我們最後就是通過求解對偶問題來得到最優解，其實這就是線性可分條件下SVM的對偶演算法。

我們這樣做的優點在於：一是因為對偶問題往往容易求解，而是可以自然引入核函數，進而推廣到非線性分類問題。

然後我們繼續講怎麼樣推廣到非線性分類上。

繼續關注超平面，我們要對一個數據點x進行分類，就是要把x代入f(x)中，算出結果然後看其正負號來進行分類的，而事實上對於x的預測，只要計算它與訓練數據點的向量內積即可（這是之後使用核函數進行非線性推廣的前提）。

然後我們看看怎樣從對偶形式的問題上使用核函數推廣到非線性分類問題上。

簡單來說，對於非線性情況，SVM其實是選擇一個核函數，通過把數據映射到高維空間上，來解決在原始空間線性不可分的問題。

下圖就很好地說明了這個過程：

在高維空間中有可能在訓練數據中實現超平面的分割。

3.核函數

SVM數據集形成的分類函數具有這樣的性質：它是一組以支持向量為參數的非線性函數的線性組合，因此分類函數的表達式僅和支持向量的數量有關，而獨立於空間的維度，在處理高維輸入空間的分類時，這種方法尤其有效，其工作原理如下圖所示：

如果我們要用線性分類器學習一個非線性關係，就要應用一個特定的非線性映射，將數據映射到特徵空間，在特徵空間中使用線性學習器。因此，建立非線性學習器就分為兩步：先使用一個非線性映射將數據變換到一個特徵空間F，然後在特徵空間使用線性學習器分類。

但如果我們有一種方式可以直接在特徵空間F中計算內積，這樣就可以把兩步合為一步了，而這種直接計算方法就是核函數。

核函數處理非線性數據的方法是將所有數據X映射到高維空間F中，在F中X就會變成線性可分的，然後就可以繼續應用原來的線性分類演算法，在原來的輸入空間里計算內積了。

舉個栗子：

上面這樣的數據是線性不可分的，於是我們採用非線性方法來進行分類。

我們把這些數據映射到三維空間（這裡本來是要映射到五維空間的，但是生成數據時採用了特殊情形，就變成了三維），然後再把坐標軸適當旋轉一下，就可以得到下圖：

我們可以看出，這裡的數據就可以用一個平面來分割開了，這樣接下來的計算還是線性SVM。

但這裡又會出現一個很大的問題，就是我們對二維空間做映射，會得到5維空間，如果是三維空間的映射，就會得到19維空間，這樣的維度增長是指數爆炸式的。而核函數則可以避開直接在高維空間進行計算的尷尬，改為在原始空間進行計算，因為核函數可以計算兩個向量在隱式映射後的空間的內積，亦即在原來的輸入空間中進行內積的計算。這樣計算出來的內積與在顯式映射後的高維空間里計算的內積是等價的，也就是說，核函數可以簡化映射空間中的內積計算，而且我們的SVM里所要計算的地方數據向量總是以內積形式出現的，因此核函數在SVM中總是可用的。

但其實要找到合適的映射是很難的，因此我們也不精確地去找某個映射對應的核函數，只是選擇一個核函數，知道它對應了某個映射，雖然不知道這個映射具體是什麼，但是我們只要計算這個核函數就可以了。

4.鬆弛變數

雖然上面的這些方法很管用，但是仍然會出現一些很難解決的問題。例如數據中存在雜訊，亦即一些偏離正常位置很遠的數據點（outlier），他們會對SVM模型造成很大的影響，因為超平面本來就是由幾個支持向量組成的，如果這些支持向量中又存在outlier中的話，就會產生像下面這樣的問題：

用黑圈圈起來的那個藍點是一個outlier，它偏離了它所屬的半個空間，本應該是紅線的超平面，就變成了黑色虛線的那個超平面，使得間隔變小了。如果這個雜訊點再往右移一點點，這樣我們可能就找不出能夠分割數據的超平面。

為了處理這種情況，我們在SVM的目標函數中引入鬆弛變數，允許數據點偏離超平面一點點，在上圖中，黑色實線表示該outlier偏離的距離，如果我們把它移動回來，就不會對超平面產生影響了，而加入鬆弛變數就可以做到這一點。這樣的SVM就可以容忍雜訊和outlier了。

5.梯度下降法

我們在SVM中構建的超平面其實並不是唯一的，我們可以用梯度下降法等方法來進行優化，來得到不同的分類器。例如下圖就有direction1和2：

我們可以認為direction2的分類效果比direction1要好，因為前者的裕量比後者大（裕量其實跟餘量的意思差不多，就是多出來的部分的意思）。

因此我們就要從各個分類器中選出一個最優的，而SVM是根據統計學習理論依照結構風險最小化的原則提出的，要求實現兩個目的：1）兩類問題能夠分開（經驗風險最小）；2）margin最大化（風險上界最小），即是在保證風險最小的子集中選擇經驗風險最小的函數。

最後再來講一些比較細的東西。

感知機演算法：這個演算法其實就是不斷訓練試錯，進行調整，然後找到一個合適的超平面。為了避免這樣的調整無限循環下去，演算法會進行在線性條件下進行收斂。而且感知機演算法只能告訴你分類的結果，並不能告訴你分類的準確率，這是一個很大的不足。

最小二乘法：通過最小化誤差的平方和尋找數據的最佳函數匹配。

SMO演算法：通過將原問題分解為一系列小規模凸二次規劃問題而獲得原問題解的方法，每次迭代只優化由2個點組成的工作集，SMO演算法每次啟發式地選擇兩個因子同時固定其它因子來找到這兩個因子的最優值，直到達到停止條件。（參考《Minimal Optimization:A Fast Algorithm for Training Support VectornMachines》和支持向量機（五）SMO演算法，SVM學習——Sequential Minimal Optimization）

Reference：

支持向量機通俗導論（理解SVM的三層境界）

作者：July、pluskid ；致謝：白石、jerrylead

如果你覺得我的筆記對你有些用處的話，請給每天都在電腦前面讀文獻查資料的本寶寶點個贊啦（求贊的眼神?_?）