Lecture 12 支持向量機 Support Vector Machines

12.1 優化目標 Optimization Objective

支持向量機(Support Vector Machine) 是一個更加強大的算法，廣泛應用于工業界和學術界。與邏輯回歸和神經網絡相比， SVM在學習復雜的非線性方程時提供了一種更為清晰，更加強大的方式。我們通過回顧邏輯回歸，一步步將其修改為SVM。

首先回顧一下邏輯回歸：

其 cost function 公式如下（這里稍微有點變化，將負號移到了括號內）：

現在只考慮一個訓練數據 x ，把 h_θ(x)=1/(1+e^-_θT_x) 帶入公式，得到下面的式子：

?

下一步， 使用 z 標示其中的 θ^Tx， 則之前的目標變為：

If y = 1， we want h_θ(x) ≈ 1， z>>0；
If y = 0， we want h_θ(x) ≈ 0， z<<0；?

?

當 y = 1 或 y = 0 時， 上面邏輯回歸的 cost function 分別只剩下一項， 對應下面兩張圖中的灰色曲線：

????? 當 y=1 時，隨著 z 增大，h(x)=1/(1+e^-z）逼近1，cost逐漸減小。　??? 當 y=0 時，隨著 z 減小，h(x)=1/(1+e^-z）逼近0，cost逐漸減小。

現在我們用新的 cost function 來代替邏輯回歸中的cost function，即上圖中玫瑰色的曲線，它分為直線和斜線兩部分。左邊的函數稱為cost₁(z)，右邊函數稱為 cost₀(z)。

在之后的優化問題中，這種形式的 cost function 會為 SVM 帶來計算上的優勢。

現在開始構建SVM

邏輯回歸的 cost function 分為A、B 兩個部分。 我們做下面的操作：

（a） 使用之前定義的 cost1() 和 cost0() 替換公式中對應的項。

（b） 根據 SVM 的習慣，除去 1/m 這個系數

因為1/m 僅是個常量，去掉它也會得出同樣的 θ 最優值。

（c）同樣根據 SVM 的習慣，做一點變動

對于邏輯回歸， cost function 為 A + λ × B ，通過設置不同的 λ 達到優化目的。 對于SVM， 我們刪掉 λ，引入常數 C， 將 cost function 改為 C × A + B， 通過設置不同的 C 達到優化目的。 （在優化過程中，其意義和邏輯回歸是一樣的。可以理解為 C = 1 / λ）

最終得到 SVM 的代價函數：

另外，邏輯回歸中假設的輸出是一個概率值。 而 SVM 直接預測 y = 1，還是 y = 0。

當θ^Tx?≥ 0 時，SVM 會預測結果為1，其他情況下，預測結果為0。

12.2 大間距分類的直觀理解 Large Margin Intuition

SVM 經常被看作是一個"大間距分類器"，也就是找到一條與正類、負類的距離最大的分隔線。 例如下圖中的黑線：

在這一節，我們將得出結論： 為了增加魯棒性，得到更好的結果(避免欠擬合、過擬合，應對線性不可分的情況)，SVM 做的不僅僅是將間距最大化，而是做了一些優化：

（1）之前的定義中，θ^Tx ≥ 0 被分為正類，θ^Tx?< 0 被分為負類。

事實上，SVM 的要求更嚴格： θ^Tx ≥ 1 被分為正類；θ^Tx?≤ -1 被分為負類。

這就相當于在支持向量機中嵌入了一個額外的安全因子，或者說安全的間距因子。

（2）只有當C 特別大的時候， SVM 才是一個最大間隔分類器

當 C 特別大時，在優化過程中，第一項會接近于0，目標變為最小化第二項：

我們在訓練集中加入一個異常點 outlier ，如下：

?

（a）如果想將樣本用最大間距分開，即將 C 設置的很大。那么僅因為一個異常點，決策邊界會從黑線變成那條粉線，這實在是不明智的。

（b）如果 C 設置的小一點，最終得到這條黑線。它可以忽略一些異常點的影響，而且當數據線性不可分的時候，也可以將它們恰當分開，得到更好地決策邊界。

另外，因為 C = 1 / λ，因此:

C 較小時，相當于 λ 較大。可能會導致欠擬合，高偏差 variance。

C 較大時，相當于 λ 較小。可能會導致過擬合，高方差 bias。

（注：這個性質在習題中考察多次）

12.3 大間距分類背后的數學 Mathematics Behind Large Margin Classification

（1） 向量內積

先看一下向量內積的知識： 假設有兩個二維向量 u 和 v ，u^Tv 叫做向量 u 和 v 之間的內積。

∥u∥ 表示 u 的范數norm，即向量 u 的歐幾里得長度，是一個實數。根據畢達哥拉斯定理：

第一種內積計算方式：首先將 v 投影至 u 向量，記其長度為p（有正負，與u同向為正，反向為負，標量），則兩向量的內積

u^Tv = ||u|| · ||v|| · cosθ = ||u|| · p

（注：||u|| 是一個實數，p也是一個實數，因此u^Tv就是兩個實數正常相乘。）

第二種內積計算公式：
u^Tv = u₁ × v₁ + u₂ × v₂? = v^Tu

（2）SVM 代價函數的另一種理解

SVM的 cost function 如下：

如果將C設的很大，cost function只剩下后面的那項。 為簡化設 θ₀ = 0，只剩下 θ₁和θ₂，則 cost function 為：

J(θ) = 1/2 × ||θ||^2

而根據上面內積的公式，我們知道有 θ^Tx = p · ||θ||，其中 p 是 x 在 θ 上的投影。 使用p⁽ⁱ⁾ ? ∥θ∥ 代替之前約束中的 θ^Tx⁽ⁱ⁾ ，得到：

（3） SVM 如何選擇更優的決策邊界

考察優化目標函數時， 假設我們的到一條綠色的決策邊界。樣本在決策邊界上的投影 p 是粉色的線：

對于正樣本 x⁽¹⁾ 而言，想要p⁽¹⁾ ? ∥θ∥ >= 1，現在 p⁽¹⁾ 長度非常短，就意味著 ||θ|| 需要非常大；

對于負樣本 x⁽²⁾ 而言，想要p⁽¹⁾ ?∥θ∥ <= ?1，現在p⁽²⁾ 長度非常短，就意味著 ||θ|| 需要非常大。

?

但我們的目標函數是希望最小化參數 θ 的范數，因此我們希望： 投影長度 p⁽ⁱ⁾ 盡可能大。例如下面這條綠色的決策邊界，就更好一些：

θ₀ = 0的意思是我們讓決策界通過原點。如果θ₀?≠ 0，決策邊界不過原點 ，SVM 產生大間距分類器的結論同樣成立（在 C 特別大的情況下）。

12.4 核函數 Kernels I?

使用高級數的多項式模型，可以解決無法用直線進行分隔的分類：

可以用一系列的新的特征 f 來替換模型中的每一項。例如令: f₁ = x₁ ， f₂ = x₂ ， f₃ = x₁ x₂ ， f₄ = x₁² ， f₅= x₂²... 得到h_θ(x) = f₁ + f₂ +. . . +f_n 。有沒有更好的
方法來構造 f₁ ， f₂ ， f₃ ? 我們可以利用核函數來計算出新的特征。

給定一個訓練實例 x ，我們利用 x 的各個特征與我們預先選定的 landmarks l⁽¹⁾ ， l⁽²⁾ ， l⁽³⁾ 的近似程度來選取新的特征 f₁ ， f₂ ， f₃ 。

其中: ||x ? l ⁽¹⁾ || 為實例 x 中所有特征與 landmark? l⁽¹⁾ 距離的和。

上例中的 similarity(x， l ⁽¹⁾ )就是核函數，具體來說是一個高斯核函數(Gaussian Kernel)。
（注：這個函數與正態分布沒什么實際上的關系，只是看上去像而已。）

如果一個訓練實例 x 與 l 很近，則 f 近似于e^?0 = 1；如果一個訓練實例 x 與 l 很遠，則 f 近似于e^{?( 較大的數 )} = 0。 如下：

?

假設 x 含有兩個特征[x₁ x₂ ]， 不同的 σ 值會有不同效果。 圖中水平面的坐標為 x₁， x ₂ 而垂直坐標軸代表 f。只有當 x 與 l⁽¹⁾ 重合時， f 才具有最大值。隨著 x 的改變 f 值的變化速率受到 σ² 的控制。 σ²越小，曲線越瘦

下圖中，粉色點離 l ⁽¹⁾ 更近，所以 f₁ 接近 1，而 f₂ ，f₃ 接近 0。因此h θ(x)?≥ 0，因此預測y = 1；同理，綠色點離 l⁽²⁾ 較近的，也預測y = 1；但藍綠色點離三個 landmark 都較遠，預測y = 0。

圖中紅色封閉曲線便是決策邊界。在預測時我們采用的特征不是訓練實例本身的特征，而是通過核函數計算出的新特征f₁ ， f₂ ， f₃ 。

12.5 核函數 Kernels II

（1） 如何選擇 landemark

通常如果訓練集有m個實例，則選取m個landmark，并將 l^（i）初始化為x⁽ⁱ⁾ ：

好處：新特征建立在原有特征與訓練集中所有其他特征之間距離的基礎之上。

?

對實例 (x⁽ⁱ⁾，y⁽ⁱ⁾)，有：

其中

（2）將 kernel 引入 SVM

我們將Gaussian Kernel 代入 SVM 的 cost function，如下圖所示：

這里與之前的 cost function的區別在于用核函數 f 代替了x。?

預測一個實例 x 對應結果的方法：? 給定x，計算新特征 f，當 θ^Tf >= 0 時預測 y = 1； 否則反之。

（3）簡化計算

最后，為了簡化計算， 在計算正則項 θ^Tθ 時，用 θ^TMθ 代替 θ^Tθ ，其中 M 是一個矩陣，核函數不同則M不同。
（注：理論上也可以在邏輯回歸中使用核函數，但使用 M 簡化計算的方法不適用于邏輯回歸，計算將非常耗時。）

（4）線性核函數

不使用核函數又稱為線性核函數(linear kernel)。線性核函數SVM 適用于函數簡單，或特征非常多而實例非常少的情況。

（5）SVM 的參數

帶有 kernel 的 SVM 有兩個參數 C 和 σ，對結果的影響如下：

1. C

當 C 較大，相當于 λ 小，可能會導致過擬合，高方差 variance;
當 C 較小，相當于 λ 大，可能會導致欠擬合，高偏差 bias;

2. σ
當 σ 較大時，圖像扁平，可能會導致低方差，高偏差 bias;
當 σ 較小時，圖像窄尖，可能會導致低偏差，高方差 variance。

12.6 使用支持向量機 Using An SVM

（1）使用現有軟件包

我們通常需要自己寫核函數，然后使用現有的軟件包(如 liblinear，libsvm 等) 來最小化 SVM 代價函數。強烈建議使用高優化軟件庫中的一個，而不是嘗試自己實現。

（2）對比一下兩種 SVM

一種是No kernel（linear kernel），h_θ(x)=g(θ₀x₀+θ₁x₁+…+θ_nx_n)，predict y=1 if θ^Tx>=0;
另一種是使用kernel f（比如Gaussian Kernel），hθ(x)=g(θ₀f₀+θ₁f₁+…+θ_nf_n)，這里需要選擇方差參數σ2

（3）特征縮放

特別地，如果使用高斯核函數，需要進行特征縮放。

（4）其他 kernel

在高斯核函數之外，還有其他一些選擇，如：
多項式核函數(Polynomial Kernel)， 字符串核函數(String kernel)， 卡方核函數( chi-square kernel) ，直方圖交集核函數(histogram intersection kernel) 等。
它們的目標也都是根據訓練集和地標之間的距離來構建新特征。一個核函數需要滿足 Mercer's 定理，才能被 SVM 的優化軟件正確處理。 但是Andrew表示他不用其他kernel函數。

?（5）多分類問題

可以訓練k個支持向量機來解決多類分類問題。 但是大多數支持向量機軟件包都有內置的多類分類功能，我們只要直接使用即可。

（6） 參數設置

盡管有現成的庫，但是我們也需要做幾件事:
1、參數C的選擇。
2、選擇內核參數或你想要使用的相似函數?? （注：如果選擇不需要任何內核參數，還稱為使用了線性核函數 SVM。）

（7）邏輯回歸模型 和 SVM 的選擇

下面是一些普遍使用的準則：
n為特征數，m為訓練樣本數。
(a) 如果 n ? m，即訓練集數據量不夠支持我們訓練一個復雜的非線性模型，選用邏輯回歸模型或者不帶核函數的 SVM。
(b) 如果 n較小，m中等，例如n在 1-1000 之間，而m在 10-10000 之間，使用高斯核函數的 SVM。
(c) 如果 n較小，m較大，例如n在 1-1000 之間，而m大于 50000，則使用 SVM 會非常慢。解決方案是創造、增加更多的特征，然后使用邏輯回歸或不帶核函數的 SVM。

如果訓練集非常大，高斯核函數的SVM 會非常慢。 通常Andrew會嘗試手動創建特征，然后用邏輯回歸或者不帶核函數的 SVM。

（注： 邏輯回歸和不帶核函數的SVM 非常相似。但是根據實際情況，其中一個可能會更有效。隨著 SVM 的復雜度增加、特征數量相當大時，不帶核函數的SVM 就會表現得相當突出。）

一個設計得很好的神經網絡也很有可能會非常有效。有一個缺點是，可能會特別慢。一個非常好的 SVM 實現包可能會運行得比較快比神經網絡快很多，而且它的代價函數是凸函數，不存在局部最優解。 (黃海廣注:當時 GPU 計算比較慢，神經網絡還不流行。)

轉載于:https://www.cnblogs.com/maxiaodoubao/p/10213597.html

總結

以上是生活随笔為你收集整理的【原】Coursera—Andrew Ng机器学习—课程笔记 Lecture 12—Support Vector Machines 支持向量机...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。