Support Vector Machines - Week_7

Large Margin Classification

Optimization Objective

這個章節我們會介紹最後一種SVM(Support Vector Machine)向量機的機器學習演算法，這種演算法是由邏輯回歸演算法(logisitic regression)所推導演化而成。

這兩個演算法基本上就是優化對象不一樣而已，logistic regression優化對象為正規項，SVM優化對象為前面一項，而 ƛ 和( 1 / m )基本上就算是常數項。

--------------------------------------------------------------------------------------------------------------------------
Large Margin Intuition

支持向量機(SVM)也被稱作最大間隔分類器(Large Margin Classifier)，其原因是因為支持向量機演算法可以嘗試發現一個與樣本數聚集之前有著最大間隔的判定邊界。

上圖是一個可以用線性來區分的分類問題，圖中青草綠和粉紅色兩條線代表著兩條邏輯回歸的判定邊界，而黑色的線代表示支持向量機所判定的邊界，從圖上可以看出來黑色的線分類似乎是比較合理的，藍色的兩條線代表支持向量機的判定邊界和樣本數據之間的間隔。

接著我們來思考支持向量機裡面的正規化常數C所扮演的角色，下面是向量支持機數學式：

假如我們選擇C是一個非常大的數值，那麼讓價值函數最小化的過程中，我們希望找出y=0和y=1兩種情況下都使得價值函數左邊這項盡量為零的參數，如果我們找到這樣的參數，則我們的最小化問題便轉成下面的數學式。

當上面這種情況下，我們可以得出支持向量機判定邊界就如同上面的黑線那樣，具有嘗試使得判斷邊界和樣本數據間的間隔最大的特性。

然而使得判定邊界與樣本數據之間的間隔最大並不總是好事。假使，我們的數據及如下圖：

我們在數據及中加入一個較為明顯的異常值，討論異常值的影響，如果我們再選取較大的C值時，會導致得到支持向量機判定界如同途中粉紅色所示，似乎不是非常的合理，但如果我們選擇較小的C值，那麼可能會如向量機判定邊界就如同黑色直線。也就是說C越小，支持向量機對異常值越不敏感。

回顧 C = 1 / 𝝺，因此總結其關係如下：

• C 較大時，相當 𝝺 於較小，可能會導致模型過擬合(overfitting)，造成高方差(high variance)。
• C 較小時，相當 𝝺 於較大，可能會導致模型低擬合(underfitting)，造成高偏差(high bias)。

--------------------------------------------------------------------------------------------------------------------------
Mathematics Behind Large Margin Classification

--------------------------------------------------------------------------------------------------------------------------
Kernels

Kernels I

因為要建造複雜的非線性分類器，所以使用核函數(kernel)來達到此目的，因此本章節會介紹核函數(kernel)及如何使用。如果你想擬合一個非線性的判定邊界來區分樣本，一種方法是建造複雜的多項式特徵變量，另種方法也可以使用kernel。以下面的例子來說：

之前的章節如果我們為了得上圖的判定邊界，模型可能是由多項式組成θ₀ + θ₁x₁ + θ₂x₂ + θ₃x₁x₂ + θ₄x₁² + θ₅x₂²...的形式，我們可以用一系列的新的特徵f來替代模型中的每一項。也就是說令多項式特徵項被f取代：f₁ = x₁, f₂ = x₂, f₃= x₁x₂, f₄ = x₁², f₅ = x₂².......，取代完後就得到h_θ(x) = f₁ + f₂ + f₃ +......+f_n。然而我們也考慮說除了對原有的特徵進行組合外，有沒有更好的方法來建構f₁, f₂, f₃ ?

我們想到可以利用核函數計算出新的特徵，因此給定一個訓練實例x，我們利用x各種特徵與我們預先選定的目標(landmark) l⁽¹⁾, l⁽²⁾, l⁽³⁾的近似程度來選取新的特徵f₁, f₂, f₃。

其中||x-l⁽¹⁾||2，就是代表實例x中與所有特徵與地標⁽¹⁾之間的距離和。上立中的similarity(x,l⁽¹⁾)就是核函數，具體而言，這裡的例子是高斯核函數。此高斯核函數與常態分布並沒有什麼實際上的關係。

這些地標是做什麼呢?!如果一個訓練實例x與地標L之間的距離接近於0，則新特徵f近似於1，如果訓練實例x與地標L之間距離較遠，則f近似於0。

假設我們的訓練實例含有兩個特徵[x1 x2]，給定地標l(1)與不同的𝜶值，請見下圖：

圖中水平面的座標 x1, x2 而垂直座標軸代表 f。可以看出，只有當 x 與 l⁽¹⁾ 重合時，f才具有最大值。隨著 x 的改變，f 值的改變的速率受到 𝜶² 的控制，可以發現說 𝜶 值較大，會造成 f 較為平緩，𝜶值較大，f 較為陡峭。

--------------------------------------------------------------------------------------------------------------------------
Kernels II

在下圖，當實例處於粉紅色的點位置處，因為其離l⁽¹⁾更近，離l⁽²⁾和l⁽³⁾較遠，因此f₁接近1，而f₂、f₃接近0。因此h(x) = θ₀+θ₁f₁+θ₂f₂+θ₁f₃ > 0，因此預測y=1，同理可以求出，對於離l⁽²⁾較近的青草綠色點，也預測y=1，但是對於天空藍色的點，因為其離三個地標都較遠，預測y=0。

這樣，圖中紅色的封閉曲線所表示的範圍，便是我們根據一個單一的訓練實例和我們選取的地標所得出的判定邊界，在預測時，我們採用的特徵不是訓練實例本身的特徵，而是通過核函數計算出的新特徵f₁, f₂, f₃。

如何選擇地標?
我們通常根據訓練及選擇地標的數量，如果訓練及中有m個實例，則我們選取m個地標，並且令：l⁽¹⁾ = x⁽¹⁾, l⁽²⁾ = x(2),...., l^(m) = x^(m)。這樣做的好處在於現在我們得到的新特徵是建立在原有特徵與訓練集中所有其他特徵之間距離的基礎上的，即如下圖

下面我們將核函數運用到向量機中，修改我們的支持向量機假設為：給定x，計算新特徵f，當θTf >=0時，預測y = 1，否則反之。相對應的要修改價值函數為下面：

在具體實踐過程中，我們還需要對最後一項(正規化項)進行些微調整，我們使用θ^TMθ代替θ^Tθ，其中M是根據我們選擇的核函數而不同的一個矩陣，這樣做的原因是為了要簡化計算。
理論上來說，我們也可以在邏輯回歸中使用核函數，但是上面使用M來簡化計算的方法不適用於邏輯回歸，因為計算將非常耗費時間。

--------------------------------------------------------------------------------------------------------------------------

SVMs in Practice

Using An SVM

在此，我們不介紹最小化支持向量機價值函數的方法，你可以使用你現有的套件包(如：liblinear, libsvm等)。在使用這些套件包最小化我們的代價函數之前，我們通常需要編寫核函數，如果我們使用高斯核函數，那麼在使用前進行特徵縮放是非常必要的。

另外，支持向量機也可以不使用核函數，不使用核函數又曾為線性核函數(linear kernel)，當我們不採用非常複雜的函數，或者我們的訓練及特徵非常多而實例非常少的時候，可以採用這種不帶核函數的支持向量機。

下面是支持向量機的兩個參數C和𝜶的影響：

• C 較大時，相當於 ƛ 較小，可能會導致過擬合，高方差
• C 較小時，相當於 ƛ 較大，可能會導致低擬合，高偏差
• 𝜶² 較大時，導致多項式特徵 f 比較平緩，導致高偏差，低方差
• 𝜶² 較小時，導致多項式特徵 f 比較陡峭，導致高方差，低偏差

核函數在高斯函數之外我們還有一些選擇，如：

• 多項式核函數(polynomial kernel)
• 字符串核函數(string kernel)
• 卡方核函數(chi-square kernel)
• 直方圖交集核函數(histogram intersection kernel)

這些核函數的目標也都是根據訓練及和地標之間的距離來建構新特徵，這些核函數需要滿足Mercer's定理，才能被支持向量機優化的模組正確處理。

面對多類分類的問題，假設我們利用之前介紹的一對多方法來解決一個多類分類問題。如果一共有k個分類，則我們需要k個模型以及k個參數向量θ。我們同樣也可以訓練k個支持向量機來解決多類分類問題。但是大多數支持向量機軟件包都有內置的多類分類功能，我們只要直接使用即可。

盡量不自己去寫SVM演算法，只要去套用別人優化的SVM套件包即可，但即使我們不需要去寫SVM的套件，但我們仍然需要去選擇SVM的參數C和SVM的核函數。

我們從邏輯回歸模型，推演得到向量機模型，在兩者之間我們該如何選擇呢?下面會介紹關於SVM和邏輯回歸演算法的個別使用時機，n是特徵個數，m是樣本數量。

• 相較於m而言，若n要大許多，也就是訓練及數量不構支持我們訓練一個複雜的非線性模型，我們選用邏輯回歸模型或者不帶核函數的支持向量機模型。
• 如果n較小(例如：n在1到1000之間)，m大小中等(例如：m在10-10000之間)，此狀況則使用帶高斯核函數的支持向量機模型。
• 如果n較小(例如：n在1-1000之間)，而m較大(例如：m大於50000)，此狀況使用支持向量機模型會非常慢，解決方法是創造或增加更多的特徵，然後使用邏輯回歸或不帶核函數的支持向量機。

值得一提的是，神經網路在以上三種情況下都可能有比較好的表現，但是訓練神經網路可能非常慢，選擇支持向量機的原因主要在於它的價值函數是凸函數，不存在局部最小值。