Andrew Ng機器學習公開課筆記 -- 支援向量機

網易公開課，第6，7，8課 

先繼續前面對線性分類器的讨論， 

通過機器學習算法找到的線性分類的線，不是唯一的，對于一個訓練集一般都會有很多線可以把兩類分開，這裡的問題是我們需要找到best的那條線

首先需要定義margin， 

直覺上來講，best的那條線，應該是在可以正确分類的前提下，離所有的樣本點越遠越好，why？ 

因為越靠近分類線，表示該點越容易被分錯，比如圖中的c點，此時y=1，但是隻要分類線略微調整一下角度，就有可能被分為y=-1 

但對于a點，就可以非常confident的被分為y=1 

是以分類線越遠離樣本點，表示我們的分類越confident

那麼如果定義“遠”這個概念？ 

functional margin 

圖中的分類線為，wx+b=0 

那麼點離這條線越遠，有wx+b>>0或<<0，比如a點 

是以functional margin定義為，前面加上y保證距離非負 

可以看出當點離線越遠時，這個margin會越大，表示分類越confident 

并且margin>0時，證明這個點的分類是正确的 

因為比如訓練集中y=1，而由線性分類器wx+b得到的結果-0.8，這樣表示分錯了，margin一定是<0的

對于訓練集中m的樣本，有 

即，整體的margin由最近的那個決定 

如果要用functional margin來尋找best分類線， 

geometric margins 

再來看另外一種margin，從幾何角度更加直覺的表示“遠” 

可以看到a和分類線垂直相交于b，b是滿足wx+b=0的等式的 

于是有， 

求得， 

考慮y=-1的情況，最終得到如下， 

可以看到，如果||w|| = 1，那麼functional margin 等于geometric margin 

那麼對于geometric margin，無論w，b的取值都不會改變margin的值，其實就是對functional margin做了norm化

the optimal margin classifier

先簡單看看凸優化的概念

凸優化問題 用一個比較通俗的方式了解  為什麼要凸優化？  這種優化是一定可以找到全局最優的，因為不存在局部最優，隻有一個最優點  是以對于梯度下降或其他的最優化算法而言，在非凸的情況下，很可能找到的隻是個局部最優 很好了解，對于二維的情況比較形象，作為例子  集合中任意兩點的連線都在集合中 

函數圖上任意兩點的連線都在above這個圖（這個應該取決于上凸或下凸，都below也一樣）  換個說法，就是他的epigraph是個凸集，其中epigraph就是the set of points on or above the graph of the function 

凸優化問題的定義 在凸集上尋找凸函數的全局最值的過程稱為凸優化  即，目标函數(objective function)是凸函數，可行集(feasible set)為凸集 為何目标函數需要是凸函數？  這個比較容易了解，不是凸函數會有多個局部最優，如下圖，不一定可以找到全局最優 

為何可行集需要為凸集？  稍微難了解一些，看下圖  雖然目标函數為凸函數，但是如果可行集非凸集，一樣無法找到全局最優 

接着看這個問題，根據上面的說法，要找到最優的classifier就是要找到geometric margin最大的那個超平面

這裡假設||w||=1，是以function margin等同于geometric margin，這裡用的是function margin的公式

這個優化的問題是，限制||w||=1會導緻非凸集，想想為什麼？

是以要去掉這個限制，得到

繼續，由于function margin通過w，b的縮放可以是任意值， 

于是就有， 

為什麼要加上平方，因為二次函數是典型的凸函數，是以這樣就把非凸函數轉換為凸函數

最終得到，

這是一個凸優化問題，可以用最優化工具去解

lagrange duality

先偏下題，說下拉格朗日乘數法，為什麼要說這個？ 

因為我們在上面看到這種極值問題是帶限制條件的，這種極值問題如何解？好像有些困難

拉格朗日乘數法就是用來解決這種極值問題的，将一個有n 個變量與k 個限制條件的最優化問題轉換為一個有n + k個變量的方程組的極值問題 

定義， 對于如下的極值問題，求最小化的f(w)，同時需要滿足i個限制條件h(w)

利用拉格朗日數乘法，變成如下的極值問題

最終，求這個方程組 

解出w和拉格朗日算子β，求出f(w)的極值

再看看wiki上的例子，好了解一些

假設有函數：，要求其極值（最大值/最小值），且滿足條件

看圖，畫出f(x,y)的等高線，和限制條件g(x,y)=c的路徑，會有多處相交 

但隻有當等高線和限制條件線相切的時候， 才是極值點 

因為如果是相交，你想象沿着g(x,y)=c繼續前進，一定可以到達比現在f值更高或更低的點 

那麼求相切點，就是求解f和g的偏導為0的方程組

說到這裡，還不夠，因為你發現上面的限制條件是不等式。。。 

于是繼續看更通用化的拉格朗日數乘法

既有等式，也有不等式的限制，稱為generalized lagrangian

這裡先引入primal optimization problem

這個啥意思？

即， 

是以，primal optimization problem就等價于最開始的minf(), 并且primal optimization problem是沒有限制條件的，因為已經隐含了限制條件 

min的那個一定不是無窮大，是以一定是滿足限制條件的

再引入dual optimization problem

而且可以看到和prime問題不一樣的隻是交換了min和max的順序

并且簡單可以證明，

這不是l的特殊特性，而是對于任意函數maxmin都是小于等于minmax的，可以随便找個試試呵呵

并且在特定的條件下，

這樣我們就可以解dual問題來替代prime問題

為何這麼麻煩？要引入dual問題，因為後面會看到dual問題有比較有用的特性，求解會比較簡單

前面說了，隻有在特定條件下，才可以用dual問題替代prime問題 

那麼這條件是什麼？這些條件先列在這裡，不了解沒事

suppose f and the gi’s are convex, and the hi’s are affine. 

suppose further that the constraints gi are (strictly) feasible; this means that there exists some w so that gi(w) < 0 for all i.

意思應該是，存在w可以讓g限制成立的，即g是嚴格可行的

under our above assumptions, there must exist w∗, α∗, β∗ so that w∗ is the solution to the primal problem, α∗, β∗ are the solution to the dual problem, and moreover p∗ = d∗ = l(w∗, α∗, β∗). moreover, w∗, α∗ and β∗ satisfy the karush-kuhn-tucker (kkt) conditions, which are as follows: 

滿足上面的假設後，就一定存在w∗, α∗, β∗滿足p∗ = d∗ = l(w∗, α∗, β∗)，并且這時的w∗, α∗ and β∗ 還滿足kkt條件，

并且，隻要任意w∗, α∗ and β∗滿足kkt條件，那麼它們就是prime和dual問題的解 

注意其中的(5), 稱為kkt dual complementarity condition 

要滿足這個條件，α和g至少有一個為0，當α>0時，g=0，這時稱“gi(w) ≤ 0” constraint is active，因為此時g限制由不等式變為等式 

在後面可以看到這意味着什麼？g=0時是限制的邊界，對于svm就是那些support vector

optimal margin classifiers – continuing

談論了那麼多晦澀的東西，不要忘了目的，我們的目的是要求解optimal margin 問題，是以現在繼續

前面說了optimal margin問題描述為， 

其中，g限制表示為， 

那麼什麼時候g=0？當functional margin為1（前面描述optimal margin問題的時候，已經假設funtional margin為1） 

是以隻有靠近超平面最近的點的functional margin為1，即g=0，而其他訓練點的functional margin都>1 

該圖中隻有3個點滿足這個條件，這些點稱為support vector，隻有他們會影響到分類超平面 

實作在訓練集中隻有很少的一部分資料點是support vector，而其他的絕大部分點其實都是對分類沒有影響的

前面說了半天prime問題和dual問題，就是為了可以用解dual問題來替代解prime問題 

好，下面就來求解optimal margin的dual問題， 

和上面讨論的廣義拉格朗日相比，注意符号上的兩個變化， 

w變量—>w,b兩個變量 

隻有α，而沒有β，因為隻有不等式限制而沒有等式限制

對于dual問題，先求

這裡就是對于w，b求l的min，做法就是求偏導為0的方程組 

首先對w求偏導， 

得到如下式子，這樣我們在解出dual問題後，可以通過α，進一步算出w 

接着對b求偏導，得到下面的式子

現在把9，10，代入8，得到

于是有，第一個限制本來就有，第二個限制是對b求偏導得到的結果

you should also be able to verify that the conditions required for p∗ =d∗ and the kkt conditions (equations 3–7) to hold are indeed satisfied in our optimization problem. 

你可以verify我們這個問題是滿足kkt條件的，是以可以解出這個dual問題來代替原來的prime問題 

先不談如何求解上面的極值問題（後面會介紹具體算法），我們先談談如果解出α，如何解出prime問題的w和b

w前面已經說過了，通過等式9就可以解出 

那麼如何解出b，

其實了解就是， 找出-1和1中靠超平面最近的點，即支援向量，用他們的b的均值作為b* 

因為w定了，即超平面的方向定了，剩下的就是平移，平移到正負支援向量的中間位置為最佳

再想的多點，求出w，b後，我們的支援向量機就已經ready了，下面可以對新的資料點進行分類 

這裡也把9代入， 

你可能覺得多此一舉，這樣每次分類都要把訓練集都周遊一遍 

其實無論是使用dual優化問題或是這裡，都是為了避免直接計算x，而是代替的計算x的内積，因為後面談到kernel，對于高維或無限維資料直接計算x是不可行的，而我們可以使用kernel函數來近似計算x的内積，這是後話

而且其實，這裡的計算量并不大，因為前面介紹了，α隻有支援向量是不為0的，而支援向量是很少的一部分

kernels

先談談feature mapping，

其實将低維資料映射到高維資料的主要原因是，因為一些在低次元線性不可分的資料，到了高次元就是線性可分的了 

沒找到合适的圖，想想在二維上看不可分的，到3維或更高維，也許就比較容易用一個超平面劃分，這是合理的

這裡我們稱，"original” input value(比如x)為input attributes 

we will also let φ denote the feature mapping, 

在将低次元的x mapping到高次元的φ(x)後，隻需要把φ(x)代入之前dual problem的式子求解就ok

但問題在于，之前dual problem的<x,z>是比較容易算的，但是高次元或無限維的<φ(x), φ(z)>是很難算出的，是以這裡無法直接算

是以kernel函數出場，

我們可以通過計算kernel函數來替代計算<φ(x), φ(z)>，kernel函數是通過x，z直接算出的 

是以往往都是直接使用kernel函數去替換<x,z>，将svm映射到高維，而其中具體的φ()你不用關心(因為計算φ本身就是很expensive的)，你隻要知道這個kernel函數确實對應于某一個φ()就可以

polynomial kernel

我們先看一個簡單的kernel函數的例子，稱為polynomial kernel（多項式核）

這個kernel是可以推導出φ()的， 

可以看出最終的結果是，φ将x mapping成xx，如下（假設n=3）

而計算k函數，複雜度就隻有o(n)

推廣一下，加上常數項

這個推導出的φ為，n=3

再推廣一下，

雖然上面都找到了φ， 其實你根本不用關心φ是什麼， 或者到底mapping到多高的次元

gaussian kernel

在來看另外一種kernel函數， 

來想一想内積的含義，當兩個向量越相近的時候，内積值是越大的，而越遠的時候，内積值是越小的 

是以我們可以把kernel函數，看成是用來衡量兩個向量有多相似

于是給出下面的kernel函數，這個函數由于描述x，z的相似度是合理的

(this kernel is called the gaussian kernel, and corresponds to an infinite dimensional feature mapping φ.)

這個kernel函數對于的φ是個無限維的映射，你不用關心到底是什麼

好到這裡，自然有個問題？我随便找個函數就可以做kernel函數嗎 

如果判定一個kernel函數是否valid？即can we tell if there is some feature mapping φ so that k(x, z) = φ(x)tφ(z) for all x, z? 

當然上面這個不太好操作，因為找到φ本身就是很困難的

下面就來證明一個判定方法，

假設，k is indeed a valid kernel corresponding to some feature mapping φ.

我們可以得到一個m-by-m的kernel matrix k，其中 

這裡如果k是個valid的kernel函數，那麼有 

于是可以證明，k是個半正定矩陣 (positive semi-definite) 

(這個沒有找到比較通俗易懂的解釋方式，隻知道定義是對于任何非0向量z，都有ztkz>=0，那麼k稱為半正定矩陣。誰可以通俗的解釋一下) 

這裡隻證明必要條件，即k函數是valid kernel函數，那麼k矩陣一定是半正定矩陣，其實這是個充分必要條件，即mercer kernel的定義

是以有了這個定理，就比較友善了，你不用去找是否有對應的φ，隻需要判定k矩陣是否為半正定矩陣即可

下面ng講了個很典型的使用svm kernel的例子，

for instance, consider the digit recognition problem, in which given an image (16x16 pixels) of a handwritten digit (0-9), we have to figure out 

which digit it was.

就是根據16×16的像素點，來判斷是否是0～9的數字 

傳統的方法是，神經網絡本證明是解這個問題的最好的算法 

可是這裡用polynomial kernel or the gaussian kernel，svm也得到了很好的效果，和神經網絡的結果一樣好 

這是很讓人吃驚的，因為初始輸入隻是256維的向量，并且沒有任何prior knowledge的情況下，可以得到和精心定制的神經網絡一樣好的效果

ng還講了另外一個例子，即初始輸入的維素不固定的情況下，例如輸入字元串的長度不固定，如何産生固定的維數的輸入，參考講義吧呵呵

這裡看到kernel在svm裡面的應用已經非常清晰了，但是其實kernel不是隻是可以用于svm 

其實它是個通用的方法，隻要學習算法可以隻含有輸入的内積，那麼都可以使用kernel trick來替換它 

for instance, this kernel trick can be applied with the perceptron to to derive a kernel perceptron algorithm.

regularization and the non-separable case

讨論異常點，或離群點，比如下圖，是否值得為了左上角那個點，将劃分線調整成右邊這樣 

從圖上直覺的看，應該不值得，右邊的劃分線遠沒有左邊的合理，而且那個資料點很有可能是個異常點，可以忽略掉

we reformulate our optimization (using ℓ1 regularization) as follows:

其實就是加上修正值ξi，使得某些點的functional margin可以小于1，即容忍一些異常點

同時在目标函數上有做了相應的修正，

the parameter c controls the relative weighting between the twin goals of making the ||w||2 small (which we saw earlier makes the margin large) and of ensuring that most examples have functional margin at least 1.

列出拉格朗日，

最終得到的dual problem是，

和之前的相比，隻是α的取值範圍有了變化，現在還要<=c

對于這個dual problem的kkt dual-complementarity conditions變化為，

the smo algorithm by john platt

前面都是給出了dual problem，可是沒有說怎麼解，現在就來談如何解svm的dual problem

coordinate ascent (descent)

坐标上升或下降，取決于求max或min 

想法很簡單，求解m維的最優問題

算法，不停疊代，每次疊代都是隻改變某一個次元來做最優化，其他次元保持不變

這個算法從圖上看起來就像這樣，

前面學過梯度下降和牛頓法，有啥差別 

牛頓，收斂很快，但每次收斂的代價比較大 

坐标上升，收斂比較慢，但是每次收斂的代價都很小 

梯度下降，不适合高維，因為每次疊代都需要算出梯度，需要考慮所有次元

smo (sequential minimal optimization)

我們先再列出前面的dual優化問題，看看用坐标上升是否可解

注意到19這個限制，這個限制注定無法使用坐标上升

因為你如果隻改變一個α值，就無法繼續保證整個等式為0

因為在固定其他的α時，α1的值也是固定的

是以提出smo算法，

想法也簡單，既然單獨改一個不行，我同時改兩個α，就有可能仍然保持等式為0

the key reason that smo is an efficient algorithm is that the update to αi, αj can be computed very efficiently. 

下面就來看看smo如何在每次疊代中高效的求的局部最優的α1和α2

上面的19可以改寫成，

由于這個值是個常量，因為你要保持除α1和α2以外的都不變，是以寫成

現在把α1和α2的限制用圖表示出來，要保持限制就隻能在這條線上移動，并且要滿足<c 

是以a2的取值在[l,h]

繼續變換20，得到

代入目标函數，我們先求出α2，然後根據上面的式子算出α1

treating α3, . . . , αm as constants, you should be able to verify that this is just some quadratic function in α2.

因為a3到am都是常數，你試着代入原來的w(), 會發現一定是得到α2的二次函數

即是這樣的形式，

這個求極值，大家都應該沒問題，很簡單

問題是這樣求出的極值點不一定在[l,h]的範圍内

是以有，在範圍内最好，不在範圍内的話，也需要clip到範圍内

there’re a couple more details that are quite easy but that we’ll leave you to read about yourself in platt’s paper: one is the choice of the heuristics used to select the next αi, αj to update; the other is how to update b as the smo algorithm is run.

本文章摘自部落格園，原文釋出日期：2014-04-24