[筆記] 機器學習 支持向量機 ( Support Vector Machines )

• 簡稱 SVM
• 屬於監督式學習算法
• 主要用於找到一個決策邊界 ( decision boundary ) 讓兩類的邊界 ( margins ) 最大化
• 大間距分類器 ( Large margin classifiers )

SVM 的代價函數

• 

  • 將 邏輯回歸的代價函數 * $\dfrac{m}{λ}$
  • 可以將 C 看成 $\dfrac{1}{λ}$，優化目標相同，SVM 的 C 與邏輯函數的 λ 只是透過不同方法來控制權重

• 這裡 h_θ(x) 的定義 :

  • h_θ(x) = 1，if θ^Tx ≥ 0
  • h_θ(x) = 0，otherwise

• cost₁(z) 與 cost₀(z) 的圖 :

  

  • 支持向量機的條件更加嚴格 :

    • h_θ(x) = 1，if θ^Tx ≥ 1
    • h_θ(x) = 0，if θ^Tx ≤ -1

• C 值的大小 :

  • 當 C 非常大 :

    • 相當於 λ 非常小
    • 對於誤差點，也會進行很好的擬合
    • 造成過度擬合的情況

  • 當 C 非常小 :

    • 相當於 λ 非常大
    • 降低過度擬合的情況

SVM 的推導

內積

• $||u||$ = 向量長度 = $\sqrt{u_1^2 + u_2^2}$
• p = v 向量投影在 u 向量的長度 ( 當 u、v 夾角大於 90 度時，p 就會是負的 )
• u^Tv = $p \cdot ||u||$ = u₁v₁ + u₂v₂

SVM 如何選擇決策邊界

• = $\dfrac{1}{2}(θ_1^2 + θ_2^2)$ = $\dfrac{1}{2}(\sqrt{θ_1^2 + θ_2^2})^2$ = $\dfrac{1}{2}||θ||^2$

• θ^Tx⁽ⁱ⁾ = $p^{(i)} \cdot ||θ||$ = $θ_1x_1^{(i)} + θ_2x_2^{(i)}$

  • θ^Tx⁽ⁱ⁾ = $p^{(i)} \cdot ||θ||$ ≥ 1，if $y^{(i)}$ = 1
  • θ^Tx⁽ⁱ⁾ = $p^{(i)} \cdot ||θ||$ ≤ -1，if $y^{(i)}$ = 0

首先要知道向量 θ 會與決策邊界垂直，且 θ₀ = 0 表示決策邊界通過原點，糟糕的決策邊界與良好的決策邊界如下 :

• 此為糟糕的決策邊界 ( 綠線 ) 與其向量 θ ( 藍線 )

  • 將每個 x⁽ⁱ⁾ 投影在向量 θ 上，得到 p⁽ⁱ⁾
  • 當 p⁽ⁱ⁾ 都較小時，為了滿足 $p^{(i)} \cdot ||θ||$ ≥ 1，$||θ||$ 就必須非常大
  • 但當 $||θ||$ 非常大時，就會使 $\dfrac{1}{2}||θ||^2$ 也就是代價函數跟著變大，所以 SVM 就不會選擇此決策邊界

• 此為良好的決策邊界 ( 綠線 ) 與其向量 θ ( 藍線 )

  • 同上得到 p⁽ⁱ⁾
  • 當 p⁽ⁱ⁾ 都較大時，$||θ||$ 就可以小一點
  • $||θ||$ 較小時，$\dfrac{1}{2}||θ||^2$ 也就是代價函數跟著變小，所以 SVM 就會選擇此決策邊界

核函數 ( Kernels )

• 用來打造非線性的支持向量機

新的特徵值

• x 與標記點 ( l⁽¹⁾、l⁽²⁾、l⁽³⁾、… ) 通過相似度函數計算出新的特徵值 f₁、f₂、f₃、…

  • f₁ = Similarity(x, l⁽¹⁾) = $exp(-\dfrac{||x - l^{(1)}||^2}{2σ^2})$
  • f₂ = Similarity(x, l⁽²⁾) = $exp(-\dfrac{||x - l^{(2)}||^2}{2σ^2})$
  • f₃ = Similarity(x, l⁽³⁾) = $exp(-\dfrac{||x - l^{(3)}||^2}{2σ^2})$

• 相似度函數是一種核函數，這裡用的是高斯核函數 ( Gaussian Kernel )

核函數與相似度函數

• f₁ = Similarity(x, l⁽¹⁾) = $exp(-\dfrac{||x - l^{(1)}||^2}{2σ^2})$

• 如果 x ≈ l⁽¹⁾ :

  • f₁ ≈ $exp(-\dfrac{0^2}{2σ^2})$ ≈ 1

• 如果 x 與 l⁽¹⁾ 相差很遠 :

  • f₁ ≈ $exp(-\dfrac{(Large Number)^2}{2σ^2})$ ≈ 0

• $σ^2$ 較小 :

  

  • 當遠離 l⁽¹⁾ 時，f₁ 下降較快

• $σ^2$ 較大 :

  

  • 當遠離 l⁽¹⁾ 時，f₁ 下降較慢

應用示例

• 假設預測 y = 1，如果 θ₀ + θ₁f₁ + θ₂f₂ + θ₃f₃ ≥ 0

• θ₀ = -0.5，θ₁ = 1，θ₂ = 1，θ₃ = 0

  • 新的樣本 x 與標記點 l⁽¹⁾ 相近

    • f₁ ≈ 1，f₂ ≈ 0，f₃ ≈ 0
    • θ₀ + θ₁ 1 + θ₂ 0 + θ₃ * 0 = -0.5 + 1 = 0.5 ≥ 0
    • 預測 y = 1

  • 新的樣本 x 與標記點 l⁽³⁾ 相近

    • f₁ ≈ 0，f₂ ≈ 0，f₃ ≈ 1
    • θ₀ + θ₁ 0 + θ₂ 0 + θ₃ * 1 = -0.5 + 0 = -0.5 ≤ 0
    • 預測 y = 0

  • 新的樣本 x 與所有標記點都相遠

    • f₁ ≈ 0，f₂ ≈ 0，f₃ ≈ 0
    • θ₀ + θ₁ 0 + θ₂ 0 + θ₃ * 0 = -0.5 + 0 = -0.5 ≤ 0
    • 預測 y = 0

• 結論 :

  • 只要靠近標記點 l⁽¹⁾、l⁽²⁾ 就預測 y = 1，可以看出決策邊界如下 :

    

如何選擇標記點

• 把每個訓練資料看作是一個標記點 ( landmark )，所以會有 m 個標記點

支持向量機結合核函數

1. 使用 m 個資料 x⁽¹⁾ ~ x^(m) 選擇出標記點 l⁽¹⁾ = x⁽¹⁾ ~ l^(m) = x^(m)

2. 算出新的特徵量 f₁⁽ⁱ⁾ ~ f_m⁽ⁱ⁾，每個特徵量 x⁽ⁱ⁾ 會算出 m 個 f⁽ⁱ⁾

   f₁⁽ⁱ⁾ = Similarity(x⁽ⁱ⁾, l⁽¹⁾)
   f₂⁽ⁱ⁾ = Similarity(x⁽ⁱ⁾, l⁽²⁾)
   …
   f_m⁽ⁱ⁾ = Similarity(x⁽ⁱ⁾, l^(m))

3. 訓練出 θ

   

   • 上面的 n = m

   • = θ^Tθ

     • 在實際運作上可能會是 θ^T 乘上某個依賴核函數的矩陣再乘以 θ
     • 目的是使支持向量機能更有效率的運行

4. 預測

   • 如果 θ^Tf ≥ 0，預測 y = 1

P.S. 為什麼不在其他算法上使用核函數的概念

• 事實上是可以的，但會十分緩慢
• 因為支持向量機的設計細節上可以很適合核函數，但其他算法並沒有

如何選擇支持向量機中的參數

• C ( = $\dfrac{1}{λ}$ ) :

  • 較大的 C : 相當於較小的 λ，低偏差 ( bias )，高方差 ( variance )，過擬合
  • 較小的 C : 相當於較大的 λ，高偏差 ( bias )，低方差 ( variance )，欠擬合

• $σ^2$

  • 較大的 $σ^2$ : 特徵量 f_i 的變化較平滑，高偏差 ( bias )，低方差 ( variance )
  • 較小的 $σ^2$ : 特徵量 f_i 的變化較不平滑，低偏差 ( bias )，高方差 ( variance )

function [C, sigma] = dataset3Params(X, y, Xval, yval)

C_trial = [0.01 0.03 0.1 0.3 1 3 10 30];
sigma_trial = C_trial;

m = size(C_trial, 2);

% error 最大就是 1
initial_error = 1;

for i = 1:m

  for j = 1:m

    model = svmTrain(X, y, C_trial(i), @(x1, x2) gaussianKernel(x1, x2, sigma_trial(j)));
    predictions = svmPredict(model, Xval);

    error = mean(double(predictions ~= yval));

    if error < initial_error

      initial_error = error;
      C_temp = C_trial(i);
      sigma_temp = sigma_trial(j);

    endif

  endfor

endfor

C = C_temp;
sigma = sigma_temp;

end

• 在 Octave 上選擇 C 與 $σ^2$ 的函式

使用支持向量機 ( SVM )

• 使用 SVM 的軟件包 ( EX : liblinear、libsvm、… ) 來解出 θ

• 使用支持向量機需要做的事 :

  • 選擇參數 C

  • 選擇核函數

    • 沒有使用核函數 ( 又稱線性核函數 )

      • 適合特徵量 ( n ) 大，訓練資料量 ( m ) 小
      • θ^Tx ≥ 0，預測 y = 1

    • 使用高斯核函數

      • 適合特徵量 ( n ) 小，訓練資料量 ( m ) 大
      • θ^Tf ≥ 0，預測 y = 1
      • 需要選擇參數 $σ^2$
      • 需要提供所使用的核函數

高斯核函數 ( Gaussian Kernel )

• f 為 f⁽ⁱ⁾，x1 為 x⁽ⁱ⁾，x2 為 l^(j)

function sim = gaussianKernel(x1, x2, sigma)

x1 = x1(:);
x2 = x2(:);
sim = 0;

margin = sum((x1 - x2) .^ 2);
sigma2 = 2 * (sigma ^ 2);
sim = exp(- margin / sigma2);
    
end

• 在 Octave 上的高斯核函數函式

在使用高斯核函數前應該先進行特徵縮放 ( Feature Scaling )

• 這樣才能保證 SVM 會同等的關注到所有不同的特徵量

其他的核函數

不管甚麼核函數都必須滿足默塞爾定理 (Mercer’s Theorem)

• 多項式核函數 ( Polynomial Kernel )

  • k(x, l) = (x^Tl + constant)^degree

• 字串核函數 ( String Kernel ) : 資料為字符串時有時會用到

• 卡方核函數 ( chi-square Kernel )
• 直方圖交叉核函數 ( histogram intersection Kernel )

多類別分類

• 許多 SVM 的軟件包已經有內建多類別分類

• 如果沒有 :

  • 使用之前在邏輯回歸提過的 One-vs-all 方法
  • 訓練 K 個 SVM 去分類 K 個類別，得到 θ⁽¹⁾、θ⁽²⁾、…、θ^(K)
  • 將新數值帶入每個 SVM，取輸出值最大的 SVM ( (θ⁽ⁱ⁾)^Tx )

邏輯回歸 vs SVMs

• n : 特徵量

• m : 訓練資料量

• 如果 n 很大 ( n ≥ m ) :

  • 使用邏輯回歸或沒有 kernel ( 線性核函數 ) 的 SVM

• 如果 n 很小，m 適中 ( n = 1 ~ 1000，m = 10 ~ 10000 ) :

  • 使用有高斯核函數的 SVM

• 如果 n 很小，m 很大 ( n = 1 ~ 1000，m = 50000+ ) :

  • 使用有高斯核函數的 SVM 會很緩慢
  • 增加特徵量後，使用邏輯回歸或沒有 kernel ( 線性核函數 ) 的 SVM

• 神經網路在這些條件下都能有很好的表現，但訓練速度相對緩慢

tags: 筆記 機器學習 支持向量機SVM