iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 4
1

注意:整篇文章極度數學高能!!

沒有把前一篇文章看完的朋友別擔心,我們會在開頭先回顧一下。在一番數學技巧的替換過後,我們的 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

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

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

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

非線性轉換

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

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

我們就先假設有個非線性轉換,可以把原本的非線性資料 https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7Bx_i%7D 轉成線性資料 https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7Bz_i%7D

https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7Bz_i%7D%20%3D%20%5Cphi(%5Cmathbf%7Bx_i%7D)

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

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 裏面算之前,要先計算出 https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7Bz_i%7D%5ET%5Cmathbf%7Bz_j%7D

計算這所有的組合可是非常花時間(https://chart.googleapis.com/chart?cht=tx&chl=O(N%5E2))的好嗎!!尤其你的資料點很多的時候,大數據都算不下去了。

Kernel method

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

我們想像中的二次多項式應該是 https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi_2(x)%20%3D%20(1%2C%20x%2C%20x%5E2),這邊有三項,可是廣義的二次多項式會有:

https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7Bz%7D%20%3D%20%5Cphi_2(%5Cmathbf%7Bx%7D)%20%3D%20(1%2C%20x_1%2C%20x_2%2C%20%5Cdots%2C%20x_d%2C%20%5C%5C%20%20%20%20%20x_1%5E2%2C%20x_1x_2%2C%20%5Cdots%2C%20x_1x_d%2C%20%5C%5C%20%20%20%20%20x_2x_1%2C%20x_2%5E2%2C%20%5Cdots%2C%20x_2x_d%2C%20%5C%5C%20%20%20%20%20%5Cdots%2C%20x_d%5E2)

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

然後再讓 https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7Bz_i%7Dhttps://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7Bz_j%7D 兩兩內積,利用內積的交換性扣掉一些不用算的,好歹也需要算 https://chart.googleapis.com/chart?cht=tx&chl=N%20%2B%20%5Cfrac%7B1%7D%7B2%7D%20N(N%2B1) 次內積,是 https://chart.googleapis.com/chart?cht=tx&chl=O(N%5E2)

總共應該會有 https://chart.googleapis.com/chart?cht=tx&chl=O(d%5E2N%5E2)

註:d 為資料維度,N 為資料筆數

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

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

https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi_2(%5Cmathbf%7Bx%7D)%5ET%5Cphi_2(%5Cmathbf%7Bx'%7D)%20%3D%201%20%2B%20%5Csum_%7Bi%3D1%7D%5E%7Bd%7D%20x_ix_i'%20%2B%20%5Csum_%7Bi%3D1%7D%5E%7Bd%7D%20%5Csum_%7Bj%3D1%7D%5E%7Bd%7D%20x_ix_jx_i'x_j'

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

https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi_2(%5Cmathbf%7Bx%7D)%5ET%5Cphi_2(%5Cmathbf%7Bx'%7D)%20%3D%201%20%2B%20%5Csum_%7Bi%3D1%7D%5E%7Bd%7D%20x_ix_i'%20%2B%20%5Csum_%7Bi%3D1%7D%5E%7Bd%7D%20x_ix_i'%20%5Csum_%7Bj%3D1%7D%5E%7Bd%7D%20x_jx_j'%20%5C%5C%5C%5C
https://chart.googleapis.com/chart?cht=tx&chl=%3D%201%20%2B%20%5Cmathbf%7Bx%7D%5ET%5Cmathbf%7Bx'%7D%20%2B%20(%5Cmathbf%7Bx%7D%5ET%5Cmathbf%7Bx'%7D)(%5Cmathbf%7Bx%7D%5ET%5Cmathbf%7Bx'%7D)%20%5C%5C%5C%5C%20%3D%201%20%2B%20%5Cmathbf%7Bx%7D%5ET%5Cmathbf%7Bx'%7D%20%2B%20(%5Cmathbf%7Bx%7D%5ET%5Cmathbf%7Bx'%7D)%5E2

這樣的話需要多少時間複雜度呢?掐指一算,https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7Bx%7D%5ET%5Cmathbf%7Bx'%7D 需要 $O(d)$,https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi_2(%5Cmathbf%7Bx%7D)%5ET%5Cphi_2(%5Cmathbf%7Bx'%7D) 總共需要 https://chart.googleapis.com/chart?cht=tx&chl=O(d)%20%2B%201

大大降低了!!

所以我們就把這樣的方法稱為 kernel method,並且定義 https://chart.googleapis.com/chart?cht=tx&chl=K_%5Cphi(%5Cmathbf%7Bx%7D%2C%20%5Cmathbf%7Bx'%7D)%20%3D%20%5Cphi(%5Cmathbf%7Bx%7D)%5ET%5Cphi(%5Cmathbf%7Bx'%7D)

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

https://chart.googleapis.com/chart?cht=tx&chl=K_2(%5Cmathbf%7Bx%7D%2C%20%5Cmathbf%7Bx'%7D)%20%3D%201%20%2B%202%20%5Cmathbf%7Bx%7D%5ET%5Cmathbf%7Bx'%7D%20%2B%20(%5Cmathbf%7Bx%7D%5ET%5Cmathbf%7Bx'%7D)%5E2%20%3D%20(1%20%2B%20%5Cmathbf%7Bx%7D%5ET%5Cmathbf%7Bx'%7D)%5E2

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

https://chart.googleapis.com/chart?cht=tx&chl=K_2(%5Cmathbf%7Bx%7D%2C%20%5Cmathbf%7Bx'%7D)%20%3D%201%20%2B%202%20%5Cgamma%20%5Cmathbf%7Bx%7D%5ET%5Cmathbf%7Bx'%7D%20%2B%20%5Cgamma%5E2%20(%5Cmathbf%7Bx%7D%5ET%5Cmathbf%7Bx'%7D)%5E2%20%3D%20(1%20%2B%20%5Cgamma%20%5Cmathbf%7Bx%7D%5ET%5Cmathbf%7Bx'%7D)%5E2

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

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

無限維度 kernel

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

有!

他長成這樣:

https://chart.googleapis.com/chart?cht=tx&chl=K(x%2C%20x')%20%3D%20exp(-(x%20-%20x')%5E2)

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

那就來證明一下啦-~~

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))

https://chart.googleapis.com/chart?cht=tx&chl=%3D%20%5Cphi(x)%5ET%5Cphi(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)

所以這種 kernel 叫作 Gaussian kernel,使用上也是有個參數可以調整強度。

https://chart.googleapis.com/chart?cht=tx&chl=K(%5Cmathbf%7Bx%7D%2C%20%5Cmathbf%7Bx'%7D)%20%3D%20exp(-%20%5Cgamma%20%5Cleft%5ClVert%20%5Cmathbf%7Bx%7D%20-%20%5Cmathbf%7Bx'%7D%20%5Cright%5CrVert%20%5E2)%2C%20%5Cgamma%20%5Cgt%200

在現在的支持向量機(Support vector machine, SVM)預設是會使用 Gaussian kernel 的,這就是這個模型強大的祕密!


上一篇
04 從感知器到 maximum-margin classifier
下一篇
06 從 hard-margin SVM 到 soft-margin SVM
系列文
機器學習模型圖書館:從傳統模型到深度學習31

尚未有邦友留言

立即登入留言