iT邦幫忙

2021 iThome 鐵人賽

DAY 29
0
AI & Data

30天搞懂機器學習是否搞錯了什麼系列 第 29

【Day 29】支援向量機(Support Vector Machine, SVM)(下)

昨天講完Hinge Loss,今天要繼續介紹SVM的第二個特色:Kernel Method。

Dual Representation

我們實際找出來可以最小化Loss function的weight https://chart.googleapis.com/chart?cht=tx&chl=w%5E*,其實是我們data points的linear combination。昨天提到我們可以用Gradient Descent來minimize SVM,更新參數的式子如下圖所示,假設我們初始化的時候 https://chart.googleapis.com/chart?cht=tx&chl=w 是一個zero vector,而你每次在更新參數的時候,你都是加上data points的linear combination。

如果今天用的是Hinge Loss,他作用在 https://chart.googleapis.com/chart?cht=tx&chl=max%20%3D%200 的region的情況,它的 https://chart.googleapis.com/chart?cht=tx&chl=c%5En(w) 就會是0,所以當你在用Hinge Loss的時候,https://chart.googleapis.com/chart?cht=tx&chl=c%5En(w) 往往都會是0,也就是說不是所有的 https://chart.googleapis.com/chart?cht=tx&chl=x%5En 都會被拿來加到 https://chart.googleapis.com/chart?cht=tx&chl=w 裡面去,所以最後解出來的 https://chart.googleapis.com/chart?cht=tx&chl=w%5E* 的linear combination的weight可能會是sparse,也就是可能有很多的data point對應的 https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha%5E* 值等於0,對最後的結果不會有影響,而那些 https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha%5E* 的值不等於0的 https://chart.googleapis.com/chart?cht=tx&chl=x%5En,就是support vector

SVM相較於其他方法可能是比較robust的,如果Loss function選的是Cross Entropy,就沒有sparse的特性。

我們可以將 https://chart.googleapis.com/chart?cht=tx&chl=w 原本的式子改寫成 https://chart.googleapis.com/chart?cht=tx&chl=w%20%3D%20X%20%5Cbf%20a,接著在步驟一我們就可以改一下function的樣子,如下圖所示,而 https://chart.googleapis.com/chart?cht=tx&chl=x%5ENhttps://chart.googleapis.com/chart?cht=tx&chl=x 做內積這件事,我們可以把它寫成一個function https://chart.googleapis.com/chart?cht=tx&chl=K(x%5EN%2C%20x),這個function我們就稱之為Kernel function

再來步驟二、三我們要找到一組最好的 https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha%5EN 可以讓我們的Total Loss最小,從下面的式子可以發現,我們不再需要知道 https://chart.googleapis.com/chart?cht=tx&chl=x 的vector是多少,我們只要知道 https://chart.googleapis.com/chart?cht=tx&chl=x 和另外一個vector https://chart.googleapis.com/chart?cht=tx&chl=z 之間的內積值,或是只要知道Kernel function就可以做所有的optimization,這件事我們就稱為Kernel Trick

Kernel Trick

我們之前有說過如果是linear的model會有很多限制,你可能要對輸入的feature做一個feature transform,它才能用linear model來處理,如果再Neural Network裡面,就用好幾個hidden layer來做feature transform。

假設有一筆data是二維的,我們想要先對他做feature transform,在feature transform以後再去apply linear SVM。假設feature transform的結果是 https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi(x),如果要算 https://chart.googleapis.com/chart?cht=tx&chl=xhttps://chart.googleapis.com/chart?cht=tx&chl=z 的Kernel function,我們就可以把值帶到feature transform的function裡面再做內積,簡化一下就會發現算出來的值會等同於 https://chart.googleapis.com/chart?cht=tx&chl=x%2C%20z 在做feature transform之前,先做內積以後再平方算出來的值。

Sigmoid Kernel

Sigmoid Kernel是 https://chart.googleapis.com/chart?cht=tx&chl=K(x%2C%20z)%20%3D%20tanh(x%20%5Ccdot%20z),如果我們使用的是Sigmoid Kernel,這個 https://chart.googleapis.com/chart?cht=tx&chl=f(x) 就可以想成它其實是一個只有一個hidden layer的Neural Network,因為你的 https://chart.googleapis.com/chart?cht=tx&chl=x 會跟所有的 https://chart.googleapis.com/chart?cht=tx&chl=x%5En 做內積,就好像是有一個Neuron的weight就是某一筆data,而Neuron的數目就是看有幾個support vector。

https://chart.googleapis.com/chart?cht=tx&chl=x 是有structure的data,我們其實就可以直接設計一個Kernel function,例如 https://chart.googleapis.com/chart?cht=tx&chl=x 是一個sequence,我們就很難把它表示成vector,那我們只要知道怎麼計算兩個sequence之間的similarity就有機會把這個similarity當作Kernel來使用,而我們還可以透過Mercer's theory來檢查你設計的function可不可以拆成兩個vector做內積以後的結果。

在語音上,假設現在要做的分類對象是Audio Segment,每一段聲音訊號會用vector sequence來表示,但你不需要知道一段聲音訊號變成vector之後長什麼樣子,你只要直接定一個Kernel function,就可以直接用Kernel Trick在SVM。

Deep Learning vs SVM

我們之前說,Deep Learning的前幾個layer可以看做是Feature Transformation,最後一個layer可以看做是Linear Classifier。而SVM做的也是很類似的事情,它前面先apply一個Kernel function,把feature轉到high dimension上面,接著在high dimension space上面就可以apply Linear Classifier,只是在SVM裡面一般Linear Classifier都會用Hinge Loss。


參考資料

李宏毅老師 - ML Lecture 20


上一篇
【Day 28】支援向量機(Support Vector Machine, SVM)(上)
下一篇
【Day 30】完賽 --- 30天搞懂機器學習真的搞錯了什麼
系列文
30天搞懂機器學習是否搞錯了什麼30

尚未有邦友留言

立即登入留言