05 從 maximum-margin classifier 到 kernel SVM

2019 iT 邦幫忙鐵人賽

DAY 4

AI & Data

機器學習模型圖書館：從傳統模型到深度學習系列第 5 篇

2019鐵人賽 machine learning 機器學習 svm kernel

杜岳華

2018-10-05 23:12:37

4045 瀏覽

分享至

注意：整篇文章極度數學高能！！

沒有把前一篇文章看完的朋友別擔心，我們會在開頭先回顧一下。在一番數學技巧的替換過後，我們的 maximum-margin classifier 會被化成一個最佳化問題。這個最佳化問題可以用二次規劃（quadratic programming, QP）來解。

$https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Balign%7D%20%5Carg%5Cmin%20_%7B%5Cmathbf%7Bw%7D%2C%20b%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Cfrac%7B1%7D%7B2%7D%20%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bw%7D%20%5C%5C%5C%5C%20%5Ctext%7Bsubject%20to%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Cforall%20i%2C%20y_i%20(%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20b)%20%5Cge%201%20%5Cend%7Balign%7D$

當模型被轉化成一個最佳化問題之後，~~你還有什麼不滿的？~~ 問題都解決了嗎？

當然還沒有阿！雖然說我們解決了前面的第二個缺點，但是第一個缺點還是在啊！

那如果資料不是線性可分的話，是不是支援非線性的分類問題就可以了？

非線性轉換

那問題簡單！既然這個分類器只能處理線性問題，那就把所有非線性問題透過一個轉換變成線性問題不就可以了？

當然用講的比較簡單...

我們就先假設有個非線性轉換，可以把原本的非線性資料 $\mathbf{x_i}$ 轉成線性資料 $\mathbf{z_i}$ ：

$\mathbf{z_i} = \phi(\mathbf{x_i})$

然後再把線性資料塞進模型裡不就得了？

$https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Balign%7D%20%5Carg%5Cmin%20_%7B%5Cmathbf%7Bw%7D%2C%20b%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Cfrac%7B1%7D%7B2%7D%20%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bw%7D%20%5C%5C%20%5Ctext%7Bsubject%20to%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Cforall%20i%2C%20y_i%20(%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bz_i%7D%20%2B%20b)%20%5Cge%201%20%5Cend%7Balign%7D$

嗯......可是瑞凡，你知道要放到 QP 裏面算之前，要先計算出 $\mathbf{z_i}^T\mathbf{z_j}$ 。

計算這所有的組合可是非常花時間（ $O(N^2)$ ）的好嗎！！尤其你的資料點很多的時候，大數據都算不下去了。

Kernel method

我們先來看一下比較簡單的非線性轉換好了，假設是二次多項式的轉換。

我們想像中的二次多項式應該是 $\phi_2(x) = (1, x, x^2)$ ，這邊有三項，可是廣義的二次多項式會有：

$\mathbf{z} = \phi_2(\mathbf{x}) = (1, x_1, x_2, \dots, x_d, \\ x_1^2, x_1x_2, \dots, x_1x_d, \\ x_2x_1, x_2^2, \dots, x_2x_d, \\ \dots, x_d^2)$

有一個常數項、d 個一次項跟 $https://chart.googleapis.com/chart?cht=tx&chl=d%20%2B%20%5Cfrac%7B1%7D%7B2%7D%20d(d%2B1)$ 個二次項，如果這個向量內積的話，乘法的時間複雜度就有 $O(d^2)$ 了。

然後再讓 $\mathbf{z_i}$ 跟 $\mathbf{z_j}$ 兩兩內積，利用內積的交換性扣掉一些不用算的，好歹也需要算 $https://chart.googleapis.com/chart?cht=tx&chl=N%20%2B%20%5Cfrac%7B1%7D%7B2%7D%20N(N%2B1)$ 次內積，是 $O(N^2)$ 。

總共應該會有 $O(d^2N^2)$ 。

註：d 為資料維度，N 為資料筆數

有沒有什麼方法可以降低這個時間呢？

我們把內積的部份拿出來看看。

$\phi_2(\mathbf{x})^T\phi_2(\mathbf{x'}) = 1 + \sum_{i=1}^{d} x_ix_i' + \sum_{i=1}^{d} \sum_{j=1}^{d} x_ix_jx_i'x_j'$

咦！是不是可以進一步整理成這樣。

$\phi_2(\mathbf{x})^T\phi_2(\mathbf{x'}) = 1 + \sum_{i=1}^{d} x_ix_i' + \sum_{i=1}^{d} x_ix_i' \sum_{j=1}^{d} x_jx_j' \\\\$
$= 1 + \mathbf{x}^T\mathbf{x'} + (\mathbf{x}^T\mathbf{x'})(\mathbf{x}^T\mathbf{x'}) \\\\ = 1 + \mathbf{x}^T\mathbf{x'} + (\mathbf{x}^T\mathbf{x'})^2$

這樣的話需要多少時間複雜度呢？掐指一算， $\mathbf{x}^T\mathbf{x'}$ 需要 $O(d)$， $\phi_2(\mathbf{x})^T\phi_2(\mathbf{x'})$ 總共需要 $O(d) + 1$ ！

大大降低了！！

所以我們就把這樣的方法稱為 kernel method，並且定義 $K_\phi(\mathbf{x}, \mathbf{x'}) = \phi(\mathbf{x})^T\phi(\mathbf{x'})$ 。

不過大家常用的是比較廣義的版本：

$K_2(\mathbf{x}, \mathbf{x'}) = 1 + 2 \mathbf{x}^T\mathbf{x'} + (\mathbf{x}^T\mathbf{x'})^2 = (1 + \mathbf{x}^T\mathbf{x'})^2$

然後使用者通常會想要細緻控制 kernel 的強度，所以會引入一個參數：

$K_2(\mathbf{x}, \mathbf{x'}) = 1 + 2 \gamma \mathbf{x}^T\mathbf{x'} + \gamma^2 (\mathbf{x}^T\mathbf{x'})^2 = (1 + \gamma \mathbf{x}^T\mathbf{x'})^2$

我們來看一下用起來的效果如何？

picture from coursera, 《機器學習技法》 - 林軒田

無限維度 kernel

既然可以有二次的那是不是到 M 次都可以？那有沒有無限次的呢？

有！

他長成這樣：

$K(x, x') = exp(-(x - x')^2)$

嗯？你不要騙我！你以為擺到次方項就可以變成無限維度？

那就來證明一下啦-~~

$https://chart.googleapis.com/chart?cht=tx&chl=%3D%20exp(-x%5E2%20%2B%202xx'%20-%20x'%5E2)%20%5C%5C%5C%5C%20%3D%20exp(-x%5E2)%20exp(-x'%5E2)%20exp(2xx')%20%5C%5C%5C%5C%20%3D%20exp(-x%5E2)%20exp(-x'%5E2)%20(%5Csum_%7Bi%3D0%7D%5E%7B%5Cinfty%7D%20%5Cfrac%7B(2xx')%5Ei%7D%7Bi%7D)%5Ctext%7B%20(Taylor%20expansion)%7D$

透過泰勒展開式展開之後我們就看到無限維度的影子了，再進一步簡化。

$https://chart.googleapis.com/chart?cht=tx&chl=%3D%20%5Csum_%7Bi%3D0%7D%5E%7B%5Cinfty%7D%20%5Cbig%20(%20exp(-x%5E2)%20exp(-x'%5E2)%20%5Cfrac%7B2%5Ei%7D%7Bi%7D%20x%5Ei%20x'%5Ei)%20%5Cbig%20)$ )

$https://chart.googleapis.com/chart?cht=tx&chl=%3D%20%5Csum_%7Bi%3D0%7D%5E%7B%5Cinfty%7D%20%5Cbig%20(%20exp(-x%5E2)%20exp(-x'%5E2)%20%5Cfrac%7B%5Csqrt%7B2%5Ei%7D%7D%7Bi%7D%20%5Cfrac%7B%5Csqrt%7B2%5Ei%7D%7D%7Bi%7D%20x%5Ei%20x'%5Ei)%20%5Cbig%20)$ )

$https://chart.googleapis.com/chart?cht=tx&chl=%3D%20%5Csum_%7Bi%3D0%7D%5E%7B%5Cinfty%7D%20%5Cbig%20(%20%5Cfrac%7B%5Csqrt%7B2%5Ei%7D%7D%7Bi%7D%20x%5Ei%20exp(-x%5E2)%20%5Cbig%20)%20%5Csum_%7Bi%3D0%7D%5E%7B%5Cinfty%7D%20%5Cbig%20(%20%5Cfrac%7B%5Csqrt%7B2%5Ei%7D%7D%7Bi%7D%20x'%5Ei%20exp(-x'%5E2))%20%5Cbig%20)$ )

$= \phi(x)^T\phi(x')$

我們的無限維度非線性轉換就完成啦！

$https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi(x)%20%3D%20exp(-x%5E2)%20%5Ccdot%20%5Cbig%20(%201%2C%20%5Cfrac%7B%5Csqrt%7B2%7D%7D%7B1%7D%20x%2C%20%5Cfrac%7B%5Csqrt%7B2%5E2%7D%7D%7B2%7D%20x%5E2%2C%20%5Cdots%2C%20%5Cbig%20)$