SVM問題定義、推導

05-20

SVM問題定義、推導

來自專欄機器學習

本片將介紹Support Vector Machine(SVM)學習演算法，SVM是最好的「off-the-shelf」監督學習演算法。

1. Margins and Separating Hyperplane

第一部分介紹margin，以及預測的可信度，隨後會將本章的概念進行形式化，用來定義SVM問題。

考慮logistic regression中我們講過，概率 $p(y=1|x; heta)=h_{ heta}(x)=g( heta^{T}x)=frac{1}{1+e^{- heta^{T}x}}$ ，表示當 $h_{ heta}(x)>0.5$ ，我們將y估計為1；也就是當且僅當 $heta^{T}xgeq 0$ ，則針對 $x$ 的 $y$ 估計為1.

考慮一個訓練樣本 $(y=1)$ ， $heta^{T}x$ 越大，則 $h_{ heta}(x)=g( heta^{T}x)=frac{1}{1+e^{- heta^{T}x}}$ 越大，則可信度(confidence that the label is 1)越大. 因此我們可以將邏輯回歸看作

如果 $heta^{T}xgg 0$ ，則產生a very confident prediction that $y=1$
如果 $heta^{T}xll 0$ ，則產生a very confident prediction that $y=0$

那麼在給定一個訓練樣本集的情況下，如果我們找到了參數 $heta$ 滿足

如果 $y^{(i)}=1$ ，則 $heta^{T}xgg 0$
如果 $y^{(i)}=0$ ，則 $heta^{T}xll 0$

則我們找到了對訓練樣本集的一個很好的fit.

為了更直觀，我們看圖1，圖中的 $imes$ 表示positive training example，圖中的 $circ$ 表示negative training example，圖中的直線 $heta^{T}x=0$ 稱為separating hyperplane(分離超平面)

如上圖1所示，圖中的A可以給一個confident prediction that y=1；對於點C，我們就比較不confident，因為decision boundary的小的變化可能會改變C的分類；對於B則介於兩者之間。

可以看出，如果一個點遠離分離超平面，那麼我們就能給出一個非常confident的prediction. 推廣來說，給定一個訓練集合，我們希望找到一個decision boundary使得我們可以make all correct and confident predictions on the training examples.

2. 符號介紹

為了讓SVM討論更加容易，我們採用不同的符號，考慮一個linear classifier 並針對二分類問題

feature為 $x$
label 為 $y in left{ -1,1 ight}$ ,而不是之前的 $left{ 0,1 ight}$
採用參數 $w,b$ 來描述線性分類器， $w^{T}x+b$
分類器為 $h_{w,b}(x)=g(w^{T}x+b)$ . 其中g是一個類似於 $tanh$ 或者perceptron的函數，對於 $zgeq 0$ ， $g(z)=1$ ;否則 $g(z)=-1$

這裡注意兩點與之前不同，尤其是與邏輯回歸的不同

邏輯回歸裡面直接採用 $heta=[ heta_{0}, heta_{1},..., heta_{n}]$ 作為參數，而這裡b相當於 $heta_{0}$ ，而 $w$ 相當於 $[ heta_{1},..., heta_{n}]$ ，這樣能夠將b與其他參數分離開進行討論
SVM直接預測1或者-1，邏輯回歸中是首先預測y是1的概率，雖然兩者都是discriminative learning analysis

3. 函數間隔和幾何間隔

3.1 一些簡單的幾何概念

高考結束八年了，還是回憶一些高中幾何學過的知識先

斜率表示一條直線(或曲線的切線)關於(橫)坐標軸傾斜程度的量。它通常用直線(或曲線的切線)與(橫)坐標軸夾角的正切，或兩點的縱坐標之差與橫坐標之差的比來表示。曲線的上某點的斜率則反映了此曲線的變數在此點處的變化的快慢程度。曲線的變化趨勢仍可以用過曲線上一點的切線的斜率即導數來描述。導數的幾何意義是該函數曲線在這一點上的切線斜率。
切線對於一個函數，如果函數某處有導數,那麼此處的導數就是過此處的切線的斜率，該點和斜率所構成的直線就為該函數的一個切線。
法線法線，始終垂直於某平面的虛線。曲線的法線是垂直於曲線上一點的切線的直線，曲面上某一點的法線指的是經過這一點並且與該點切平面垂直的那條直線（即向量）

如上圖所示，假設我們的樣本點 $x in R^{2}, x = (x_{1},x_{2})$ ，則對於二維平面中的點得到的分離超平面如圖中直線所示，圖中分離超平面的直線的法線為 $w=(1,1)$ ，切線斜率為 $tg alpha = -1$

3.2 函數間隔

對於一個訓練樣本點 $(x^{(i)},y^{(i)})$ ，我們定義 $(w,b)$ 的functional margin為

$hatgamma^{(i)}=y^{(i)}(w^{T}x+b)$

顯然我們希望

如果 $y^{(i)}=1$ ，則希望 $w^{T}x+bgg 0$ ；如果 $y^{(i)}=-1$ ，則希望 $w^{T}x+bll 0$
如果函數間隔 $y^{(i)}(w^{T}x+b) >0$ ，則針對該點的預測是對的。

因此一個很大的函數間隔意味著a confident and correct prediction.

但是函數間隔的一個特性使得它not a very good measure of confidence. 給定函數 $g$ ，如果 $w ightarrow 2w, b ightarrow 2b$ ， $h_{w,b}(x)$ 不做任何變化，因為它是依賴於 $w^{T}x+b$ 的正負sign的而不依賴於絕對值的大小，而functional margin變成了兩倍。

同時我們定義最小函數間隔，給定訓練集中所有樣本點的函數間隔中的最小間隔

$hatgamma=min hatgamma^{(i)}$

3.3 幾何間隔(geometric margins)

如圖所示，圖中點A是一個positive training example，A點到decision boundary的距離稱為幾何間隔 $gamma^{(i)}$ ，如圖中AB之間的線段所示。

點A為 $(x^{(i)},y^{(i)})$ ,法線的單位長度向量為 $frac{w}{||w||}$ ,則點B為 $x^{(i)}-r^{(i)}cdot frac{w}{||w||}$ ，顯然點B是在分離超平面上的點，因此帶入的到：

$w^{T}(x^{(i)}-r^{(i)}cdot frac{w}{||w||})+b=0$

求解即可得到 $gamma^{(i)}=frac{w^{T}x^{(i)}+b}{||w||}=(frac{w}{||w||})^{T}x^{(i)}+frac{b}{||w||}$

當點為positive example的時候，上式成立，但是為negative example的時候， $w^{T}x^{(i)}+b<0$ ，不用改用來衡量距離，因此我們定義如下：

$gamma^{(i)}=y^{(i)}(frac{w^{T}x^{(i)}+b}{||w||})=y^{(i)}((frac{w}{||w||})^{T}x^{(i)}+frac{b}{||w||})$

當 $||w||=1$ 的時候，functional margin和geometric margin就是相同的；
geometric margin對於參數的rescale無關，可以任意縮放，但是幾何間隔不變
由於invariant to rescaling of parameter，因此我們在求解的時候，可以對參數加上限制，例如我們可以要求 $||w||=1$ ,或者 $|w_{1}|=5$ 。

最後我們規定最小几何間隔，表示所有點中幾何間隔最小的那個

$gamma=min gamma^{(i)}$

4. The optimal margin classifier

給定一個linearly separable的訓練數據集，也就是存在分離超平面使得能夠將所有的positive和negative進行區分，我們如何實現maximum geometric margin？

我們可以定義問題如下

問題形式化1

希望能夠最大化(最小函數間隔)， $||w||=1$ 的約束保證了函數間隔等於幾何間隔，因此我們保證了所有的函數間隔都 $geq 1$ ，因此求解這個問題將會得到最大的幾何間隔。

但是 $||w||=1$ 的約束是不好的，是non-convex constraint. 這個問題無法轉化為標準優化軟體可以解的形式，因此我們將這個問題進行轉換，去掉non-convex constraint約束得到：

問題形式化2

我們要最大化 $hatgamma/||w||$ ，subject to 函數間隔最小為 $hatgamma$ . 我們去掉了的約束，但是得到了一個non-convex的目標函數 $frac{hatgamma}{||w||}$ ,並且依然沒有軟體可以求解這類問題。

記得我們之前說過我們可以給參數加任意的縮放限制而不改變任何東西嗎？這裡我們加一個限制使得 $hatgamma=1$ ,這可以通過rescale做到，因此問題形式化2轉化為：

問題形式化3

因為max $frac{1}{||w||}$ 等同於min $||w||^{2}$ ，這個問題可以進行求解，轉化成了一個凸二次目標函數和線性條件的優化問題，這個問題可以用商業的quadratic programming進行求解，解即是optimal margin classifier。

接下來我們介紹通過求解dual form來求解該問題，通常比QP軟體要快速很多。