Lecture5 - SVM （上）

02-04

前面幾講，給大家介紹了統計機器學習中非常典型的regression和classification問題。這講開始，講給大家繼續介紹一個數學理論非常漂亮的新model，支撐向量機（support vector machine），為什麼叫支撐向量機呢？其實這個演算法叫支撐向量就夠了，machine是強行加上去的，就好比xxx演算法一樣。大家應該明白，這個演算法所關注的重點就是支撐向量了，到底什麼是支撐向量，該演算法有什麼作用？下文將會慢慢講解。

其實有的時候，SVM也被叫做最優間隔分類器，其實，不論SVM被叫做什麼，只要我們能夠從本質上理解SVM所要表達的思想，以及SVM到底需要我們去做什麼，我們該怎麼樣使用SVM，能否將其做出新的推廣和延伸，那麼這樣的話，目的就達到了。

Support Vector Machine

有關SVM的歷史，在這裡就不多說了，可以說他的開創養活了在深度學習出現之前的大多數phd，那麼，儘管現在SVM出現的場合不多了，但是這麼重要和完美的演算法，我們還是要必須掌握的。

SVM可以說是最棒的「off-the-shelf」監督學習演算法了，要學習SVM，我們首先必須要學會margins的概念。以及在分類數據的時候，所使用到的「gap」。知道了這兩個點後，我們就要去談論一下最優間隔分類器，拉格朗日的對偶性。這兩個點知道後，我們在來學習有關kernels的概念，藉助kernel的概念來幫我們解決在高維空間的分類問題。最後，我們需要掌握的就是SMO演算法，通過SMO演算法完美的實現SVM演算法。

Margins：

通過辣雞郵件分類的例子，我們想要找到一個分類面，使得該分類面能夠將ham郵件和spam郵件區別開來。從圖中，可以看出，這兩類數據一定是可以線性可分的。那麼，我們首先畫出一個決策面。

沒毛病，這條決策邊界將兩類數據完美的分開了。

老鐵，沒毛病，這條決策邊界也將兩類數據完美的分開了。

同樣沒毛病，，，這三條決策邊界都可以當成我們最終需要的solution。

那麼，問題就來了，既然這個問題有這麼多的solution，我需要找一個optim的solution，我們該怎麼做呢？該用什麼量來衡量各個solution之間的好壞呢？

還是繼續回到我們先前學到的東西，logistics regression。為什麼要再次拿出來logistics regression呢，因為logistics regression在我們進行supervised learning的學習過程中，可以說是非常重要的一個演算法，不論是deep learning還是各種有關AI的領域都能看到他的影子。

回顧下，logistics regression是如何做二分類的。

我們首先將 $p(y=1|x;theta)$ 通過 $h_{theta}(x) = g(theta^Tx)$ 進行建模。
如果 $h_{theta}(x) >=0.5$ ，我們就將input的x判定為Class1，該式子的等價形式就是 $theta^Tx >=0$
關於將Input的x判定為Class2，同理分析。

那在logistics regression中，我們是如何評價分類性能的好壞的呢？

$theta^Tx$ 越大，也就是說 $h_{theta}(x)$ 越接近1，我們就有很高的confidence去說，該input的x很大可能性被分配到Class2
將上述要說明的進行定性分析就是，

當 $theta^Tx gg0$ 的時候，我們有很大的confidence確定 $y=1$
當 $theta^Tx ll 0$ 的時候，我們有很大的confidence確定 $y = 0$

那麼，在求解logistics regression問題的過程中，我們需要通過給定的training set來找到一個這樣的 $theta$ ，使得該 $theta$ 滿足這樣的性質：

無論何時 $y = 1$ ，都能得到 $theta^Tx gg0$
無論何時 $y=0$ ，都能得到 $theta^Tx ll0$

那這個時候，問題又來了，我們該怎麼在沒有概率表示的情況下，來定義一個classifier的confidence呢？

繼續回到辣雞郵件分類的例子

我們觀察到圖中的三個點，分別為A，B，C。圖中的黑色實線，為該問題的一個決策面。發現點A距離決策面非常的近，然後是點B。點C距離決策面非常的遠。

那麼，我如果現在問你這樣的問題，你覺得點C屬於哪個類別？你肯定會毫不猶豫的說點C一定屬於Spam類。但是，我如果問你點A呢，你可能並不會像判斷點C那麼有自信，因為點A距離決策面實在是太近了，如果我稍微的改變下這個決策面，點A也許就有可能被分類到Ham類別去了。對於點B的回答，你的confidence肯定是處在點A和點C之間。

通過這個問題，我們知道了，對於一個分類器，如果，我們能夠將training set中的所有正確的分類的sample都以非常大的confidence分對，那麼，這個classifier的就是一個非常nice的classifier了。（想一想，是不是這個意思？）

Notation

還是回顧下，我們前面是怎麼做二分類的。

定義一個決策面 $w^Tx+b=0，z=w^Tx+b=0$
如果 $z > 0$ ，那麼，我們就能得到 $g(z) = 1$
如果 $z<0$ ，那麼，我們就能得到 $g(z) = -1$

接下里，我們就要引入SVM問題的兩個基本概念。

函數間隔(function margin)
幾何間隔(geometric margin)

先來說說函數間隔

當給定一個training set $(x^{(i)},y^{(i)})$ ，函數間隔這樣定義 $hat{gamma}^{(i)} = y^{(i)}(w^Tx+b)$

如果 $y^{(i)}=1$ ，那麼 $(w^Tx+b)$ 就應該是一個非常大的正數。
如果 $y^{(i)}=-1$ ，那麼 $(w^Tx+b)$ 就應該是一個絕對值非常大的負數。
如果 $hat{gamma}^{(i)} = y^{(i)}(w^Tx+b) >0$ ，我們就說，這個classifier對於第i個sample的判斷是正確的。
函數間隔的取值越大，就越說明這個classifier所做的正確分類的confidence就越大。

關於上面這4點，請務必搞清楚，其實說的清楚了，只要這些概念理解了，那麼函數間隔就沒什麼問題了。最後，由於training set有n個sample，那麼就會算出來n個函數間隔，我們只要選取其中最小的一個函數間隔作為整個classifier的函數間隔就行了

$hat{gamma}^{} = min_{i=1,2,3,..,n}hat{gamma}^{(i)}$

OK. 函數間隔的內容介紹完了，接下來，就講講什麼是幾何間隔(geometirc margin)

咦?剛剛不是已經定義了一個叫做函數間隔的變數了么？並且函數間隔已經可以很清楚的表達我們一開始所需要解決的confidence問題了，那為什麼還要多此一舉的在定義一個叫做幾何間隔的東西？

繼續回到剛剛上面的式子 $y^{(i)}(w^Tx+b)$ ，假如現在 $y=1$ ，那麼只要求 $(w^Tx+b)$ 是一個正數，並且越大越好，不就能滿足我們所謂的最大confidence了嗎？

但是，如果我們將最初的 $(w,b)$ 替換成了 $(2w,2b)$ ，那麼函數間隔自然而然也被擴大了2倍。這也就是說，在我們探索 $(w,b)$ 對於classifier分類性能的影響的時候，任意改變 $(w,b)$ 的值後，會使得我們先前所要表述的東西缺少了實際的含義。

那麼解決方法就是最常見的規則化了。 $(||w||_2)$

考慮上面這個圖， $gamma^{(i)}$ 來表示線段AB的長度，且對於A點的描述是這樣的：

input為 $x^{(i)}$
label為 $y^{(i)}=1$
點A到決策邊界的距離是 $gamma^{(i)}$

那麼，通過上面的信息，我們就能得出點的B的信息：

input為 $x^{(i)}-gamma^{(i)}*frac{w}{||w||}$
由於B點在決策面上，所以 $w^Tx+b=0$

通過將input帶入到決策面方程，得到

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

解出來：

$gamma^{(i)} = frac{w^Tx^{(i)}+b}{||w||} = (frac{w}{||w||})^Tx^{(i)}+frac{b}{||w||}$

接下來，後面的定義，就和函數間隔是一樣的了。

注意到，當 $||w||=1$ 的時候，函數間隔和幾何間隔就相等了。

在回到剛剛那個問題，如果此時的 $(w,b)$ 變成了 $(2w,2b)$ ，那麼幾何間隔的值是不會發生變化的。

同樣，求取一個classifier的幾何間隔

${gamma}^{} = min_{i=1,2,3,..,n}{gamma}^{(i)}$

Optimal Margin Classifier

通過上面的函數間隔和幾何間隔的學習，我們接下來看看如何通過這兩個間隔來得到一個最優的間隔分類器。通過將我們的目標公式化：

$max_{gamma,w,b}hat{gamma} = frac{hat{gamma}}{||w||}$

$s.t. y^{(i)}(w^Tx^{(i)}+b)>=hat{gamma}，i=1,2,...,n$

通過上面的分析，我們知道如何任意增加 $(w,b)$ 的倍數將不會改變幾何間隔對於整個model所帶來的影響。那麼我們令 $hat{gamma} = 1$ ，則就把原問題轉化為了一個更加nice的問題

$min_{gamma,w,b} frac{1}{2}||w||^2$

$s.t. y^{(i)}(w^Tx^{(i)}+b)>=1，i=1,2,...,n$

看到這個問題，很多人就很開心了，因為這是一個凸的二次規劃問題，並且這個問題的約束也是線性的，那麼通過現成的QP程序就可以求解了。

有了上面這三個知識點：

函數間隔
幾何間隔
最優間隔分類器

如果你沒搞懂，請不要往下看了，繼續回啃上面的內容，因為上面這些內容是下面更近一步介紹SVM的基礎，請務必搞清楚每個公式和概念之間的關係。

Linearly Separable SVM

Input：一個線性可分的training set $（x^{(i)},y^{(i)}），i=1,2,3,...,n$
Output：一個決策函數和一個可以分開兩類數據的超平面
Solution： $max_{gamma,w,b} frac{1}{2}||w||^2$ ， $s.t. y^{(i)}(w^Tx^{(i)}+b)>=1，i=1,2,...,n$ 通過解決上面這個優化問題，從而得到最optim的解 $(w^*,b^*)$
我們就得到了分類超平面： $w^*x+b^*=0$ ，決策函數： $sign(w^*x+b^*)$

好了，有了線性可分的SVM了，那麼下來，就說說什麼是support vector？support vector其實就是分離超平面上的點，

那麼對於所有的support vector，滿足 $y(w^Tx+b)=1$
函數間隔： $hat{gamma} = 1$
幾何間隔： $gamma = frac{1}{||w||}$
Margin： $frac{2}{||w||}$

Lagrange duality

關於優化問題，我們在學高數的時候就學過，使用拉格朗日數乘法來做，當時講的約束都是等式約束，即下面的形式：

$min_{w}f(w)$
$s.t. h_i(w)=0,i=1,2,3,...,l$
那麼使用拉格朗日數乘法得到： $L(w,b)=f(w)+sum_{i=1}^lbeta_ih_i(w)$
我們只需要分別對 $w$ 和 $beta_i$ 求偏導，令其等於0就可以得optim solution

當我們把優化問題的約束改成不等式約束的時候，就會得到下面的形式：

$min_{w}f(w)$
$s.t. h_i(w)=0,i=1,2,3,...,l$
$s.t. g_i(w)<=0,i=1,2,3,...,k$
這裡比上面的式子，多一步，把這個優化問題叫做primal optim problem.
那麼使用拉格朗日數乘法得到： $L(w,b)=f(w)+sum_{i=1}^kalpha_ig_i(w)+sum_{i=1}^lbeta_ih_i(w)$

考慮下面的等式:

$theta_P(w) = max_{alpha,beta,alpha_i>=0}L(w,alpha,beta)$

其中的以P為下標表示的是該問題的primal問題，也就是說，上述等式在 $g_i(x)<=0$ 和 $h_i(x)=0$ 的情況下是成立的，也即 $theta_P(w) = f(w)$ 。

如果上面兩個條件不成立的話，那麼 $theta_P(w) =infty$

比如拿 $g_i(x) > 0$ 來說，由於所有的 $alpha_i >=0$ ，那麼 $L(w,b)=f(w)+sum_{i=1}^kalpha_ig_i(w)+sum_{i=1}^lbeta_ih_i(w)$ 中的第二項將趨向無窮大
同理，當 $h_i(x)ne0$ 的時候，上式的第三項也將區域無窮大

通過上面的分析，我們就知道了，我們的優化問題就是為了求

$min_{w}theta_P(w) =min_w max_{alpha,beta,alpha_i>=0}L(w,alpha,beta)$

為了在下面的式子中方便推導，我們令 $p^*=min_wtheta_P(w)$

類比原問題的定義，我們在定義一個該問題的對偶問題，

$theta_D(alpha,beta)=min_wL(w,alpha,beta)$

那麼接下來，我們就能定義一個對偶問題的優化問題：

$max_{alpha,beta,a_i>=0}theta_D(alpha,beta)=max_{alpha,beta,a_i>=0}min_wL(w,alpha,beta)$

為了方便今後再次使用，我們令 $d^*=max_{alpha,beta,a_i>=0}theta_D(w)$

有了上面一系列的描述後，我們來看看 $p^*$ 和 $d^*$ 有什麼關係。

因為 $p^*$ 實質上是求取max，而 $d^*$ 實質上是求取min，所以說，本質上的話

$p^*>=q^*$

但是在某些條件下， $p^*=q^*$ 是成立的。而我們需要的就是這樣的等式，使得原問題不好解的問題，我們通過解決他的對偶問題就可以得到解決。

通過查閱相關資料，知道了等號成立的條件是：

f和g分別是凸的函數
$h_i(x)$ 是仿射的
$g_i(x)$ 是有意義的

這個時候，我們就一定能找到 $(w^*,alpha^*,beta^*)$ 使得他們成為原始問題的解，同樣也是對偶問題的解。

這裡就要介紹一個非常重要的概念，KKT條件

KKT條件

$frac{partial}{partial w_i}L(w^*,alpha^*,beta^*) = 0,i=1,2,3...,n$
$frac{partial}{partial beta_i}L(w^*,alpha^*,beta^*) = 0,i=1,2,3...,l$
$alpha^*_ig_i(w^*)=0,i=1,2,3,...,k$ KKT的對偶互補條件，相當的重要
$g_i(w)<=0,i=1,2,3,...,k$
$alpha^*>=0,i=1,2,3,...,k$

因為KKT條件後，我們就知道，如果找到能夠滿足KKT條件的 $(w^*,alpha^*,beta^*)$ ，那麼它就一定是是原問題也是對偶問題的解。

關於上面的KKT對偶互補條件，是非常重要的，現在對其做一個簡要的分析

由 $alpha^*_ig_i(w^*)=0,i=1,2,3,...,k$ 知

當 $alpha_i^* > 0$ ，則 $g_i(w^*)=0$
當 $alpha_i^* =0$ ，則 $g_i(w^*)<=0$

這兩點有什麼作用呢？在後面，我們會看到，其實SVM中真正起作用的只有少量的support vector。

好了，該講的基礎都講完了，現在，我們再次回到最優間隔分類器的講解，其對應的優化問題為：

$min_{gamma,w,b} frac{1}{2}||w||^2$

$s.t. y^{(i)}(w^Tx^{(i)}+b)>=1，i=1,2,...,n$

我們通過重新改寫s.t.裡面的內容，得到：

$g_i(w)= 1-y^{(i)}(w^Tx^{(i)}+b)<=0$

那麼結合上面的分析，當 $alpha_i^* > 0$ 的時候， $g_i(w)= 1-y^{(i)}(w^Tx^{(i)}+b)=0$ ，說明此時的input為支撐平面上的點，這些點就叫做support vector。而當 $alpha_i^* =0$ 的時候， $g_i(w)= 1-y^{(i)}(w^Tx^{(i)}+b)<=0$ ，說明此時的點都是分類正確的點，他們要麼在Class1的一側，要麼在Class2的一側。

對於 $alpha_i$ 的理解，可以把它當做是一個權重。為什麼呢？當其大於0的時候，說明它在整個優化問題中起到了作用，那麼大於0的時候，對應的向量就是support vector。當其等於0的時候，說明此時它所對應的input不起作用，對應的都是那些分類正確的點。我們知道，在整個training set中，support vector的數量是遠遠小於整個training set的。

圖中，處於虛線上的點就是support vector

這個時候，我們就能通過拉格朗日數乘法來求解我們的優化問題了

$L(w,b,alpha)=frac{1}{2}||w||^2-sum_{i=1}^nalpha_i[y^{(i)}(w^Tx^{(i)}+b)-1]$

上面這個等式中，只有 $alpha_i$ ，而沒有 $beta_i$ ，因為我們僅僅只有不等式的約束，而沒有等式的約束，所以不需要 $beta_i$

下面，我們就來找找這個問題對應的對偶問題。通過固定 $alpha$ ，來尋找 $w,b$ 使得 $L(w,b,alpha)$ 達到最小，也即 $theta_D(alpha)=min_{w,b}L(w,b,alpha)$

那麼，還是用最常規的套路來求解，分別求目標函數對於 $w$ 和 $b$ 的偏導數，然後令其為0

我們得到下面的兩個等式：

$w = sum_{i=1}^n alpha_iy^{(i)}x^{(i)}$
$sum_{i=1}^nalpha_iy^{(i)}=0$

把它們分別帶入 $L(w,b,alpha)$ 中，我們得到

$L(w,b,alpha)=sum_{i=1}^malpha_i-frac{1}{2}sum_{i,j=1}^my^{(i)}y^{(j)}alpha_ialpha_j(x^{(i)})^Tx^{(j)}$

則，對偶形式的優化問題就為：

$max_{alpha}W(alpha) =sum_{i=1}^nalpha_i-frac{1}{2}sum_{i,j=1}^ny^{(i)}y^{(j)}alpha_ialpha_j(x^{(i)})^Tx^{(j)}$
s.t. $alpha_i>=0,i=1,2,3,...,n$
$sum_{i=1}^malpha_iy^{(i)}=0$

關於 $alpha$ 怎麼求，後面會講一個通過SMO演算法來求解。

好了，有了上面的一步一步的推導，我們現在的目標是求出optim的 $(w^*,b^*)$

通過上面求導後得到的式子知

$w^* = sum_{i=1}^n alpha_i^*y^{(i)}x^{(i)}$

下面來求 $b^*$ ，我們知道了在支撐面上的點滿足 $y^{(i)}(w^{T}x+b)=1$

對等號兩邊同時乘以 $y^{(i)}$ ，則我們得到 $(w^{T}x+b)=y^{(i)}$

通過前面對於 $alpha$ 的分析，我們知道，如果input對應為support vector，那麼其值大於0，

如果對應於那些分類正確的點， $alpha$ 的值為0，如果其值為0，則求出來的 $w=0$ ，關於分離超平面方程 $w^Tx+b=0$ ，則得到 $b=0$ ，所以，這並不是我們想要的。故，我們所討論的 $alpha$ 都應該是大於0的，也就是那些對應support vector。

則我們得到

$b^*=y^{(j)}-sum_{i=1}^nalpha_i^*y^{(i)}(x^{(i)})^Tx^{(j)}$

有了 $w^*$ 和 $b^*$ ，

那麼分離超平面方程為： $sum_{i=1}^n alpha_i^*y^{(i)}x^{(i)}x+b^*=0$
決策函數為： $f_{(w,b)}(x) = sign(sum_{i=1}^n alpha_i^*y^{(i)}x^{(i)}x+b^*)$

好了，有關線性可分的SVM就講完了，我們來做一個conclusion

一定要記住， $alpha_i>0$ 對應的是support vector，且support vector僅僅是整個training set中的一小部分數據
在計算 $w^*和b^*$ 的時候，我們僅僅需要做的就是計算training set中的每個x與support vector的x的對應內積，就能夠求出optim的 $(w^*,b^*)$

其實上面所講的這些，又有一個新的名字，叫做 hard-margin SVM。那麼有hard-margin，自然而然就會對應 soft-margin，我們下面就來講講什麼是soft-margin。

Soft-Margin SVM

如果在平面上，對應的兩類數據不能夠線性可分了，這個時候，我們該怎麼使用SVM來求解呢？（那就說明，hard-margin對應的都是在平面上可以線性可分的數據）

我們可以通過引入鬆弛變數 $xi_i$ 來允許這種誤分類和雜訊數據，通過這樣的方法來進行SVM就叫做soft-margin。

那麼，新的約束條件就是：

$y^{(i)}(w^Tx^{(i)}+b)>=1-xi_i$

在增加一個懲罰項： $sum_{i=1}^nxi_i$

那麼，此時的優化問題就變成了

$min_{w,b}frac{1}{2}||w||^2+Csum_{i=1}^nxi_i$

$s.t. y^{(i)}(w^Tx^{(i)}+b)>=1-xi_i，i=1,2,3,...,n$

$xi_i>=0,i=1,2,3,...,n$

繼續將該問題轉化為拉格朗日數乘法來做，以及還是先尋求原問題的對偶問題，操作和hard-margin是一模一樣的，過程我就不寫了，畢竟手碼公式，我就寫出最終的結果。

$w = sum_{i=1}^n alpha_iy^{(i)}x^{(i)}$
$sum_{i=1}^malpha_iy^{(i)}=0$
$C-alpha_i-eta_i=0$

對偶形式的優化問題為：

$max_{alpha}W(alpha) =sum_{i=1}^nalpha_i-frac{1}{2}sum_{i,j=1}^ny^{(i)}y^{(j)}alpha_ialpha_j(x^{(i)})^Tx^{(j)}$
$C>=alpha_i>=0,i=1,2,3,...,n$
$sum_{i=1}^malpha_iy^{(i)}=0$