Coursera機器學習 Week7 筆記

程式設計作業放到了github上：coursera_machine_learning

Support Vector Machine

支援向量機的目的，是将線性可分的資料集用一個超平面分開，而且讓兩個類的資料集都距離這個超平面盡可能的遠。

将線性可分的資料集分開的超平面可以有無數個，這個用Perceptron就可以做到，但是讓所有的點距離這個超平面盡可能的遠，這樣的解就是唯一的，使用SVM來求解。

接下來将分别從cost function、intuition和kernel來介紹SVM。

1. Optimization Objective

本節将從Logistic Regression來類比SVM。

先看Logistic Regression的“分類決策函數 h(x) ”以及“損失函數 J(θ) ”：

h(x)=11+e−θTx

J(θ)=−ylogh(x)−(1−y)log(1−h(x))

損失函數随着 z=θTx 的變化如下圖。

當 y=1 時， J(θ)=−logh(x)=−log11+e−θTx

當 y=0 時， J(θ)=−log(1−h(x))=−log(1−11+e−θTx)

現在對上面的 J(θ) 做一些改變。

當 y=1 時， J(θ) 為下圖中的紫色線：

當 y=0 時， J(θ) 為下圖中的紫色線：

從上面的圖中，可以知道，這個損失函數是希望，所有的負樣例( y=0 )的 θTx<−1 的，所有的正樣例( y=1 )的 θTx>1 的。

θTx 的含義其實是樣例點到超平面的距離矢量。也就是說，損失函數希望所有的樣例到超平面的距離都大于1，正負号代表方向(在超平面之上或者之下)。至于為什麼是“1”，下面會詳細講到。

在SVM中，分類決策函數 h(x) 定義如下：

h(x)={1if θTx>00 otherwise

h(x) 的目的很簡單，就是用一個超平面把正負樣例分開。

損失函數 J(θ) 定義如下：

J(θ)=C∑i=1m[y(i)×cost1(θTx(i))+(1−y(i))×cost0(θTx(i))]+12∑j=1nθ2j

cost1(θTx)={0if              y=1, θTx>1some value   y=1, otherwise

cost0(θTx)={0if                y=0, θTx<−1some value   y=0, otherwise

J(θ) 的目的是讓正負樣例盡可能地分開，距離超平面有一定的距離。希望： y=1 時， θTx>1 ； y=0 時， θTx<−1 。

2. Large Margin Intuition 1

SVM有如下optimization objective：

minθC∑i=1m[y(i)×cost1(θTx(i))+(1−y(i))×cost0(θTx(i))]+12∑j=1nθ2j

其中 C 是一個類似于λ的權衡因子，可以了解為 C=1λ 。

現在來看資料集線性可分的情況下，SVM選擇超平面的政策，來看看SVM的intuition。

當資料集線性可分的時候，SVM挑選的超平面必須能夠滿足：

對所有的正樣例有 θTx>1 ，所有的負樣例有 θTx<−1 。

也就是說，所有的樣例距離超平面都有一定的距離，就像下圖中的藍線所示：

如此一來，所有的 cost1=0 ，所有的 cost0=0 ，則優化目标變成如下形式：

minθ12∑j=1nθ2j

s.t. θTx>1  if y=1

  θTx<−1if y=0

接下來看看SVM會選擇怎樣的超平面， θ 是超平面的法向量。

樣例點 x 到超平面的距離p：

p=θTx∥θ∥

則

θTx=p∥θ∥

優化目标改寫成：

minθ12∑j=1nθ2j

s.t. p∥θ∥>1  if y=1

   p∥θ∥<−1if y=0

第一種，margin非常小的時候：

0<p(1)≪1 的時候，為了使 p(1)∥θ∥>1 ，則 ∥θ∥ 需要很大；

−1≪p(2)<0 的時候，為了使 p(2)∥θ∥<−1 ，則 ∥θ∥ 需要很大；

這樣一來，就違背了 minθ12∑nj=1θ2j ，是以，SVM不會選擇這樣的超平面。

第二種，margin比較大的時候：

p(1)>1 的時候， ∥θ∥ 不用很大，也能使 p(2)∥θ∥>1 ；

p(2)<−1 的時候， ∥θ∥ 不用很大，也能使 p(2)∥θ∥<−1 ；

這種情況符合 minθ12∑nj=1θ2j ，是以，SVM會選擇這樣的超平面。

3. Large Margin Intuition 2

上面Ng将的intuition沒有解釋為什麼 θTx>1 ，這裡的1究竟是怎麼選擇出來的。接下來結合李航的講解來說明一下。

首先，定義幾個術語。

定義1 (關于樣例點的幾何間隔)：樣例點到超平面的距離矢量 p(i) ，即:

p(i)=y(i)θTx(i)∥θ∥

定義2 (關于訓練集的幾何間隔)：訓練集中所有樣例點的幾何間隔的最小值，即：

p=minip(i)

SVM的目的就是找到使 p 最大的超平面。是以其optimization objective又可以寫成如下形式：

maxθp

s.t. y(i)θTx(i)∥θ∥⩾p

明顯地， p 取值的變化，并不會影響到不等式的成立，隻要∥θ∥随之等比例變動即可，而 ∥θ∥ 的等比例變動也不會改變超平面。

是以不如就令 p=1∥θ∥ ，如此一來，optimization objective被改寫成如下形式：

maxθ1∥θ∥

s.t. y(i)(θTx(i))⩾1

又因為 maxθ1∥θ∥ 等價與 minθ12∥θ∥2 ，是以最終優化目為：

minθ12∥θ∥2

s.t. y(i)(θTx(i))⩾1

與上面Ng的optimization objective吻合。

需要注意的是：正如intuition1中所言，這個優化目标的使用是有限制條件的，其限制條件就是任意的  y(i)(θTx(i))⩾1 都要成立，也就是說，一定能夠有一個超平面完美地分開資料集，即這個資料集是線性可分的。

總結一下，對于線性可分的資料集：

其分類決策函數 h(x) 定義如下：

h(x)={1if θTx>00 otherwise

其優化目标／損失函數為：

minθ12∥θ∥2

s.t.y(i)(θTx(i))⩾1

4. Outlier - 存在特異值的資料集

上面讨論的都是資料集是線性可分的情況，實際上這種資料集太少了，實際操作中的資料集多多少少都有特異值(outlier)的幹擾，除去這些outlier，剩下大部分樣例點組成的資料是線性可分的。

那麼對于這種存在少數的樣例點不滿足 y(i)(θTx(i))⩾1 的情況，SVM應該如何處理呢？

解決方法就是給每個樣例點 x(i) 加上一個松弛變量 ε(i) ，使得限制條件變成：

y(i)(θTx(i))⩾1−ε(i)

對于每一個松弛變量，都要支付一個代價，于是優化目标變成：

minθ12∥θ∥2+C∑i=1mε(i)

再回過來看Ng在最開始給出的損失函數 J(θ) :

J(θ)=C∑i=1m[y(i)×cost1(θTx(i))+(1−y(i))×cost0(θTx(i))]+12∑j=1nθ2j

可以認為：

ε(i)=y(i)×cost1(θTx(i))+(1−y(i))×cost0(θTx(i))

但實際求解中，不需要這樣代換，因為 cost1 和 cost0 在 y(i)(θTx(i))<1 情況下的值是未知的，是以還不如直接将這個整體看成一個未知數，然後用其他的求最優解的算法來求得最優解即可。

總結一下，對于有outlier的資料集：

其分類決策函數 h(x) 定義如下：

h(x)={1if θTx>00 otherwise

其優化目标／損失函數為：

minθ12∥θ∥2+C∑i=1mε(i)

s.t.y(i)(θTx(i))⩾1−ε(i)

5. Kernel - 核函數

上面的資料集都是基本上線性可分的，但是有些資料集，就是線性不可分的，比如像這樣的：

之前講Linear Regression的時候也出現過這種例子，那時候的處理方法也可以用在這裡。

假設分類決策函數 h(x) 如下：

h(x)=θ0+θ1x1+θ2x2+θ3x1x2+θ4x21+θ5x22+...

令 f1=x1 ， f2=x2 ， f3=x1x2 ， f4=x21 ， f5=x22 ，則：

h(x)=θ0+θ1f1+θ2f2+θ3f3+θ4f4+θ5f5+...

這就又轉化成了線性的。

把這些個 f1,f2,f3,f4,f5.... 稱為新生成的特征，也就是說，需要生成一系列新的特征，把非線性的問題拉回到線性問題上來。

那麼怎麼生成這些新的特征？

在SVM中，使用核函數(kernel)來基于“現有特征”生成“新的特征”。

令:

l(1)=x(1)

l(2)=x(2)

...

l(m)=x(m)

然後對于第i個資料，其新的特征計算如下：

f1=kernel(x,l(1))

f2=kernel(x,l(2))

...

fm=kernel(x,l(m))

這裡的 kernel() 是一個核函數，常用的核函數有“Guassian Kernel”，定義如下：

kernel(x,l)=exp(−∥x−l∥22σ2)

這樣就将資料集由原來的 n 維特征空間映射到了新的m維特征空間中。如果，訓練集大小 m 比較大的話，就相當于引入了更多的新特征。

接下來的步驟就和上面處理線性可分資料集一樣咯，隻不過，現在SVM的輸入不是x，而是 f 了。

這裡還有一個不确定的參數σ， σ 越大， fi 的變化就越平緩，反之。

6. 最優化問題求解

一般使用SMO算法來快速求解SVM。

詳細過程涉及到數學相關的知識點，如“拉格朗日算子”、“對偶問題”。目前還沒有弄得特别清楚，迷迷糊糊的。

實際操作中，這一步不需要自己去實作，套用現有的架構就可以實作了。