【機器學習】支持向量機原理及例題詳解

專欄持續更新中，歡迎訂閱~
Linux
資料結構與演算法
機器學習

優化目標

引入

我們先從回顧一下Logistic回歸，看看Logistic回歸是如何演變為支持向量機的，

當 y = 1 y=1 y=1時，如果我們希望 h θ ( x ) ≈ 1 h_{\theta}(x)≈1 hθ?(x)≈1，則 θ T x \theta^{T}x θTx遠大于0.

當 y = 0 y=0 y=0時，如果我們希望 h θ ( x ) ≈ 0 h_{\theta}(x)≈0 hθ?(x)≈0，則 θ T x \theta^{T}x θTx遠小于0.

下面是每個樣本的代價函式，注意沒有求和，代表每個單獨的訓練樣本對Logistic回歸的總體目標函式的貢獻，

然后我們將 h θ ( x ) h_{\theta}(x) hθ?(x)的具體公式帶入進去，得到的就是每個訓練樣本對總體函式的具體貢獻：

現在我們再來考慮 y = 1 , y = 0 y=1,y=0 y=1,y=0的情況，函式影像如下：

下面我們 y = 1 y=1 y=1為例，用兩條直線近似等效曲線，來向支持向量機轉換，例如我以 z = 1 z=1 z=1為起點，作兩條直線近似取代曲線 ? l o g 1 1 + e ? z -log\frac{1}{1+e^{-z}} ?log1+e?z1?，同理 y = 0 y=0 y=0時也一樣，

當 y = 1 y=1 y=1時，兩條直線記為 C o s t 1 ( z ) Cost_1(z) Cost1?(z)，

當 y = 0 y=0 y=0時，兩條直線記為 C o s t 0 ( z ) Cost_0(z) Cost0?(z)，

構建支持向量機

這是我們在Logistic回歸中使用的正規化代價函式 J ( θ ) J(\theta) J(θ)

然后我們用 C o s t 1 ( θ T x ( i ) ) Cost_1(\theta^{T}x^{(i)}) Cost1?(θTx(i))和 C o s t 0 ( θ T x ( i ) ) Cost_0(\theta^{T}x^{(i)}) Cost0?(θTx(i))將 ? l o g h θ ( x ( i ) ) -logh_{\theta}(x^{(i)}) ?loghθ?(x(i))和 ? l o g ( 1 ? h θ ( x ( i ) ) ) -log(1-h_{\theta}(x^{(i)})) ?log(1?hθ?(x(i)))代替，去掉 1 m \frac{1}{m} m1?，然后對于正規項，我們不再用 λ \lambda λ來控制正規項的權重，而選擇用不同的常數C來控制第一項的權重，最后我們得到支持向量機的總體優化目標如下：

與Logistic回歸不同的是，sigmoid函式輸出的不是概率，而是直接輸出0或者1，

直觀理解SVM

這是SVM的代價函式和影像：

下面我們來想一下如何讓代價函式最小化，

若 y = 1 y=1 y=1，則當 θ T x ≥ 1 \theta^{T}x≥1 θTx≥1時， C o s t 1 ( z ) = 0 Cost_1(z)=0 Cost1?(z)=0.

若 y = 0 y=0 y=0，則當 θ T x ≤ ? 1 \theta^{T}x≤-1 θTx≤?1時， C o s t 2 ( z ) = 0 Cost_2(z)=0 Cost2?(z)=0.

下面我們想象一下，如果將常數C設得比較大，例如C=100000，那么當進行最小化時，我們將迫切希望找到一個合適的值，使第一項等于0，那么現在我們試著在這種情況下來理解優化問題，

要使第一項為0，則有以下兩種情況：

若 y = 1 y=1 y=1，則 θ T x ≥ 1 \theta^{T}x≥1 θTx≥1，即 y = 1 y=1 y=1的樣本點在超平面 H 1 : θ T x ≥ 1 H_1:\theta^{T}x≥1 H1?:θTx≥1上，

若 y = 0 y=0 y=0，則 θ T x ≤ ? 1 \theta^{T}x≤-1 θTx≤?1，即 y = 0 y=0 y=0的樣本點在超平面 H 2 : θ T x ≤ ? 1 H_2:\theta^{T}x≤-1 H2?:θTx≤?1上，

如下圖所示，在 H 1 、 H 2 H_1、H_2 H1?、H2?上的點就是支持向量：

這里兩個超平面 H 1 、 H 2 H_1、H_2 H1?、H2?平行，它們中間沒有樣本點， H 1 、 H 2 H_1、H_2 H1?、H2?之間的距離成為間隔（margin），

間隔依賴于分離超平面的法向量 θ \theta θ，等于 2 ∣ ∣ θ ∣ ∣ \frac{2}{||\theta||} ∣∣θ∣∣2?， H 1 、 H 2 H_1、H_2 H1?、H2?是間隔邊界，

核函式（kernel）

簡單介紹

如下圖，我們需要得到一個非線性的決策邊界：

按我們之前學的方法，可以通過增加項數來進行擬合，如下：

現在我們用一些新的符號 f 1 , f 2 , f 3 . . . f_1,f_2,f_3... f1?,f2?,f3?...來表示新的特征值：

θ 0 + θ 1 f 1 + θ 2 f 2 + θ 3 f 3 + θ 4 f 4 + θ 5 f 5 + . . . ≥ 0 \theta_0+\theta_1f_1+\theta_2f_2+\theta_3f_3+\theta_4f_4+\theta_5f_5+...≥0 θ0?+θ1?f1?+θ2?f2?+θ3?f3?+θ4?f4?+θ5?f5?+...≥0

f 1 = x 1 , f 2 = x 2 , f 3 = x 1 x 2 , f 4 = x 1 2 . . . f_1=x_1,f_2=x_2,f_3=x_1x_2,f_4=x_1^2... f1?=x1?,f2?=x2?,f3?=x1?x2?,f4?=x12?...

現在我們用 f 1 , f 2 , f 3 f_1,f_2,f_3 f1?,f2?,f3?來舉例：

如圖，我們在圖上選擇三個標記 l ( 1 ) , l ( 2 ) ， l ( 3 ) l^{(1)},l^{(2)}，l^{(3)} l(1),l(2)，l(3)

然后來定義新的特征：

給定一個實體x，然后將 f 1 f_1 f1?定義為度量實體 x x x與標記點 l ( 1 ) l^{(1)} l(1)的相似度

f 1 = s i m i l a r i t y ( x , l ( 1 ) ) = e x p ( ? ∣ ∣ x ? l ( 1 ) ∣ ∣ 2 2 σ 2 ) f_1=similarity(x,l^{(1)})=exp(-\frac{{||x-l^{(1)}||}^2}{2\sigma^2}) f1?=similarity(x,l(1))=exp(?2σ2∣∣x?l(1)∣∣2?)

類似地，

f 2 = s i m i l a r i t y ( x , l ( 2 ) ) = e x p ( ? ∣ ∣ x ? l ( 2 ) ∣ ∣ 2 2 σ 2 ) f_2=similarity(x,l^{(2)})=exp(-\frac{{||x-l^{(2)}||}^2}{2\sigma^2}) f2?=similarity(x,l(2))=exp(?2σ2∣∣x?l(2)∣∣2?)

f 3 = s i m i l a r i t y ( x , l ( 3 ) ) = e x p ( ? ∣ ∣ x ? l ( 3 ) ∣ ∣ 2 2 σ 2 ) f_3=similarity(x,l^{(3)})=exp(-\frac{{||x-l^{(3)}||}^2}{2\sigma^2}) f3?=similarity(x,l(3))=exp(?2σ2∣∣x?l(3)∣∣2?)

這種函式我們稱為高斯核函式，后面我們還會學到其他的核函式，

下面來看看這些核函式的運算式有什么含義，

假設現在有一點非常接近與標記點 l ( 1 ) l^{(1)} l(1)，那么歐氏距離 ∣ ∣ x ? l ( 1 ) ∣ ∣ 2 {||x-l^{(1)}||}^2 ∣∣x?l(1)∣∣2就會接近于0，此時 f 1 ≈ e x p ( 0 ) = 1 f_1≈exp(0)=1 f1?≈exp(0)=1，

相反，如果這點離 l ( 1 ) l^{(1)} l(1)很遠，歐式距離 ∣ ∣ x ? l ( 1 ) ∣ ∣ 2 {||x-l^{(1)}||}^2 ∣∣x?l(1)∣∣2會變得很大，此時 f 1 ≈ 0 f_1≈0 f1?≈0，

講完了特征值的定義，接下來我們看看核函式是如何應用于決策邊界的，

給定一個訓練樣本，當 θ 0 + θ 1 f 1 + θ 2 f 2 + θ 3 f 3 ≥ 0 \theta_0+\theta_1f_1+\theta_2f_2+\theta_3f_3≥0 θ0?+θ1?f1?+θ2?f2?+θ3?f3?≥0時，預測 y = 1 y=1 y=1，

假設我們已經得到了引數 θ \theta θ的值：

θ 0 = ? 0.5 , θ 1 = 1 , θ 2 = 1 , θ 3 = 0 \theta_0=-0.5,\theta_1=1,\theta_2=1,\theta_3=0 θ0?=?0.5,θ1?=1,θ2?=1,θ3?=0

現在我們有一個實體 x x x（藍點），落在如圖所示位置，顯然，該實體與標記點 l ( 1 ) l^{(1)} l(1)間距離很近，故 f 1 = 1 f_1=1 f1?=1，與標記點 l ( 2 ) ， l ( 3 ) l^{(2)}，l^{(3)} l(2)，l(3)相距較遠，故 f 2 , f 3 = 0 f_2,f_3=0 f2?,f3?=0，然后我們代入 θ 0 + θ 1 f 1 + θ 2 f 2 + θ 3 f 3 \theta_0+\theta_1f_1+\theta_2f_2+\theta_3f_3 θ0?+θ1?f1?+θ2?f2?+θ3?f3?得 θ 0 + θ 1 = 0.5 ＞ 0 \theta_0+\theta_1=0.5＞0 θ0?+θ1?=0.5＞0，所以預測 y = 1 y=1 y=1，

若一個實體如綠點所示，與 l ( 1 ) , l ( 2 ) , l ( 3 ) l^{(1)},l^{(2)},l^{(3)} l(1),l(2),l(3)的距離都很遠，此時 f 1 , f 2 , f 3 = 0 f_1,f_2,f_3=0 f1?,f2?,f3?=0

代入 θ 0 + θ 1 f 1 + θ 2 f 2 + θ 3 f 3 \theta_0+\theta_1f_1+\theta_2f_2+\theta_3f_3 θ0?+θ1?f1?+θ2?f2?+θ3?f3?得 θ 0 = ? 0.5 ＜ 0 \theta_0=-0.5＜0 θ0?=?0.5＜0，所以預測 y = 0 y= 0 y=0，

如此，便會得到一個可以區分正負樣本的非線性的決策邊界，

那么現在大家可能會想如何去得到我們的標記點 l ( 1 ) , l ( 2 ) , l ( 3 ) l^{(1)},l^{(2)},l^{(3)} l(1),l(2),l(3)，并且在一些復雜的分類問題中，也許我們需要更多的標記點，

一般情況下，我們會直接選擇訓練樣本作為標記點，

如下給定 m m m個訓練樣本，然后選定與 m m m個訓練樣本完全一樣的位置作為標記點，

轉化為向量：

f = [ f 0 f 1 f 2 f 3 . . . ] ∈ R m + 1 f=\left[ \begin{matrix} f_0 \\ f_1 \\ f_2 \\ f_3\\... \end{matrix} \right]∈R^{m+1} f=???????f0?f1?f2?f3?...????????∈Rm+1

則當 θ T f ≥ 0 \theta^Tf≥0 θTf≥0時，預測 y = 1 y= 1 y=1.

最小化函式

引數選擇

• 首先我們看看引數 C C C，前面我們知道 C C C和 1 λ \frac{1}{\lambda} λ1?作用一樣，如果選擇了較大的 C C C,則意味著選擇了較大的 λ \lambda λ，則是一個高偏差，低方差的模型（欠擬合），

  如果選擇了較小的 C C C，則意味著選擇了較小的 λ \lambda λ，則是一個高方差，低偏差的模型（過擬合），

• 還有一個引數 σ 2 \sigma^2 σ2，如果 σ 2 \sigma^2 σ2比較大，則高斯核函式 e x p ( ? ∣ ∣ x ? l ( i ) ∣ ∣ 2 2 σ 2 ) exp(-\frac{{||x-l^{(i)}||}^2}{2\sigma^2}) exp(?2σ2∣∣x?l(i)∣∣2?)相對平滑，模型高偏差低方差，反之則相對陡峭，模型低偏差高方差，

例題

在本次代碼練習中，我們先從基礎的線性分類出發，再到非線性分類來熟悉SVM的作業原理，最后再構建區分垃圾郵件的分類器，

import numpy as np
import pandas as pd
import seaborn as sb
import matplotlib.pyplot as plt
import scipy.io as sio

線性SVM

df = sio.loadmat('E:\\happy\\ML&DL\\My_exercise\\ex5-SVM\\data\\ex6data1.mat')
data = pd.DataFrame(df['X'], columns=['X1', 'X2'])
data['y'] = df['y']
data.head()

fig = plt.subplots(figsize=(8,6))
plt.scatter(data['X1'], data['X2'], s=50, c=data['y'], cmap='Spectral')
plt.xlabel('X1')
plt.ylabel('X2')
plt.show()

from sklearn import svm

C=1

#C=1
svc_1 = svm.LinearSVC(C=1, loss='hinge', max_iter=10000)
svc_1.fit(data[['X1', 'X2']], data['y'])
svc_1.score(data[['X1', 'X2']], data['y'])

0.9803921568627451

#C=1時，畫圖看看每個類別預測的置信度
data['SVM1 Confidence'] = svc_1.decision_function(data[['X1', 'X2']])
data.head()

fig = plt.subplots(figsize=(8,6))
plt.scatter(data['X1'], data['X2'], s=50, c=data['SVM1 Confidence'], cmap='RdBu')
plt.title('SVM (C=1) Decision Confidence')
plt.show()

C=100

#C=100時，畫圖看看每個類別預測的置信度
data['SVM100 Confidence'] = svc_100.decision_function(data[['X1', 'X2']])
fig = plt.subplots(figsize=(8,6))
plt.scatter(data['X1'], data['X2'], s=50, c=data['SVM100 Confidence'], cmap='RdBu')
plt.title('SVM (C=100) Decision Confidence')
plt.show()

非線性SVM

#高斯核函式
def gaussian_kernel(x1, x2, sigma):
    return np.exp(-np.power(x1 - x2, 2).sum() / (2 * (sigma ** 2)))

#測驗一下
x1 = np.array([1, 2, 3])
x2 = np.array([2, 0, 1])
sigma = 2
gaussian_kernel(x1, x2, sigma)

0.32465246735834974

df = sio.loadmat('E:\\happy\\ML&DL\\My_exercise\\ex5-SVM\\data\\ex6data2.mat')
data = pd.DataFrame(df['X'], columns=['X1', 'X2'])
data['y'] = df['y']
data

fig = plt.subplots(figsize=(8,6))
plt.scatter(data['X1'], data['X2'], s=30, c=data['y'], cmap='Spectral')
plt.xlabel('X1')
plt.ylabel('X2')
plt.show()

#用內置的高斯核函式求解
svc = svm.SVC(C=100, gamma=10, probability=True)

svc.fit(data[['X1', 'X2']], data['y'])
svc.score(data[['X1', 'X2']], data['y'])

0.9698725376593279

#選一類按照概率畫出來
prob = svc.predict_proba(data[['X1', 'X2']])[:, 0]

fig = plt.subplots(figsize=(8,6))
plt.scatter(data['X1'], data['X2'], s=30, c=prob, cmap='Reds')

網路搜索尋找最優引數

#讀取訓練集和驗證集
df = sio.loadmat('E:\\happy\\ML&DL\\My_exercise\\ex5-SVM\\data\\ex6data3.mat')
df.keys()

gamma = 1 2 σ 2 \frac{1}{2\sigma^2} 2σ21?

X = df['X']
Xval = df['Xval']
y = df['y']
yval = df['yval']

candidate = [0.01, 0.03, 0.1, 0.3, 1, 3, 10, 30, 100]
gamma_values = [0.01, 0.03, 0.1, 0.3, 1, 3, 10, 30, 100]

best_score = 0
best_params = {'C': None, 'gamma': None}

for C in candidate:
    for gamma in gamma_values:
        svc = svm.SVC(C=C, gamma=gamma)
        svc.fit(X, y)
        score = svc.score(Xval, yval)
        
        if score > best_score:
            best_score = score
            best_params['C'] = C
            best_params['gamma'] = gamma

best_score, best_params

(0.965, {'C': 0.3, 'gamma': 100})

實作垃圾郵件過濾器

train = sio.loadmat('E:\\happy\\ML&DL\\My_exercise\\ex5-SVM\\data\\spamTrain.mat')
test = sio.loadmat('E:\\happy\\ML&DL\\My_exercise\\ex5-SVM\\data\\spamTest.mat')
train.keys(),test.keys()

#X是一個二進制向量，1表示郵件中存在該單詞，0表示不存在
X = train['X']
y = train['y'].ravel()
Xtest = test['Xtest']
ytest = test['ytest'].ravel()

svc = svm.SVC()
svc.fit(X, y)
svc.score(Xtest, ytest)

0.987

例題資料和jupyter獲取

關注公眾號“大撥鼠Code”，回復“機器學習”可領取上面例題的源檔案，jupyter版本的，例題和資料也一起打包了，之前的練習也在里面，感謝支持，

參考資料：

[1] https://www.bilibili.com/video/BV164411b7dx

[2] https://github.com/fengdu78/Coursera-ML-AndrewNg-Notes