iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 3
0

上次我們完成了感知器的介紹,感知器也有他相對應的學習演算法:perceptron learning algorithm (PLA)。

不過我們今天沒有要講 PLA,我們來講講感知器的缺點。

感知器這個模型有很多的缺點,但是因為他是最簡單的模型,我們就放他一馬(?)。

他的缺點有:

  1. 只能處理線性可分(linear-separable)的資料
  2. 只要能分,大家都是好的分類器(黑貓白貓,能抓老鼠的就是好貓?)

線性可分

我們一項一項來講,什麼是線性可分(linear-separable)?

像這樣是線性可分的,可以用一條直線把不同的點分開。

像這樣根本找不到一條線可以將點分開的,不是線性可分。

差一點點也不行!很尷尬,差一點就可以變成線性可分的了!但是他就不是!

所以整體說起來,感知器在使用上限制頗大。

好的分類器?

接下來,什麼叫作一個好的分類器?

以上三張圖,大家有沒有認為哪一張分的最好?

每個人可能有不同的答案,但是有沒有覺得第一張是比較好的分類器?

為什麼?

資料點都多多少少會有一些誤差,而資料我們都假設他比較相似的會在一起,所以當新的資料點出現的時候,我們通常預期他會在舊的資料點附近。所以說,如果線可以離資料點遠一點比較好,這樣的話就不會不小心分錯。

其實你心裡想的是這個樣子的:

我們可以定一個東西叫作 margin,他就是線到最近的資料點的距離,然後希望 margin 可以越大越好。

Maximum-margin classifier

所以我們希望的是一個讓 margin 最大化的分類器,也就是 Maximum-margin classifier。

那麼他要怎麼以數學表達呢?

注意:以下數學高能!!

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Balign%7D%20%5Carg%5Cmax_%7B%5Cmathbf%7Bw%7D%2C%20b%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Ctext%7Bmargin%7D(%5Cmathbf%7Bw%7D%2C%20b)%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%5Ctext%7Bclassify%20%7D%20(%5Cmathbf%7Bx_n%7D%2C%20y_n)%20%5Ctext%7B%20correctly%7D%20%5Cend%7Balign%7D
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Balign%7D%20%5Ctext%7B%20%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Ctext%7Bmargin%7D(%5Cmathbf%7Bw%7D%2C%20b)%20%3D%20%5Cmin%20_%7Bi%20%3D%201%20%5Cdots%20n%7D%20%5Ctext%7Bdistance%7D(%5Cmathbf%7Bx_n%7D%2C%20%5Cmathbf%7Bw%7D%2C%20b)%20%5Cend%7Balign%7D

總的來說,你希望 margin 越大越好,那就是我們的最佳化目標,但是會帶有一些條件,像是我們需要將點都分對,以及 margin 的定義是線到各個點的距離最短的那個。

上方式子中的 argmax 指的是改變某些變數(https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7Bw%7D%2C%20b),讓後方的式子的值最大。subject to 則是限制式,也就是必須要滿足的條件。

但是這樣的式子無法直接套用數學方法計算,所以我們要進一步將式子公式化。

進一步公式化

注意:以下極度數學高能!!

談到距離的話,我們要先講講高中數學裡的點到線距離公式:

https://chart.googleapis.com/chart?cht=tx&chl=%5Ctext%7Bdistance%7D(%5Cmathbf%7Bx_i%7D%2C%20%5Cmathbf%7Bw%7D%2C%20b)%20%3D%20%5Cfrac%7B%7Cax_i%20%2B%20by_i%20%2B%20c%7C%7D%7B%5Csqrt%7Ba%5E2%20%2B%20b%5E2%7D%7D

不記得的話,回去翻翻課本或是 google 一下。可以觀察一下,會發現分子是線的權重向量跟資料點向量的相乘再相加,再加上一個常數項。相乘再相加的動作其實就是兩個向量的 內積運算。分母部份是線的權重向量的 長度。我們可以把這個二維的公式擴充到 n 維,就變成了:

https://chart.googleapis.com/chart?cht=tx&chl=%5Ctext%7Bdistance%7D(%5Cmathbf%7Bx_i%7D%2C%20%5Cmathbf%7Bw%7D%2C%20b)%20%3D%20%5Cfrac%7B%7C%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20b%7C%7D%7B%7C%7C%20%5Cmathbf%7Bw%7D%20%7C%7C%7D

是不是看起來漂亮許多?

接著,如果要把資料點分對,那就表示說,將資料點 https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7Bx_i%7D 代入模型中算出來的值會跟真實答案 https://chart.googleapis.com/chart?cht=tx&chl=y_i 在線的同側,也就是正負號是相同的。利用這點,我們發現如果將資料點代入模型中算出來的值 https://chart.googleapis.com/chart?cht=tx&chl=(%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20b) 與真實答案 https://chart.googleapis.com/chart?cht=tx&chl=y_i 相乘的話,必定為正,所以 https://chart.googleapis.com/chart?cht=tx&chl=y_i%20(%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20b)%20%5Cgt%200

整個問題會被進一步變成這樣:

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Balign%7D%20%5Carg%5Cmax%20_%7B%5Cmathbf%7Bw%7D%2C%20b%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Ctext%7Bmargin%7D(%5Cmathbf%7Bw%7D%2C%20b)%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%5Cgt%200%20%5Cend%7Balign%7D
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Balign%7D%20%5Ctext%7B%20%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Ctext%7Bmargin%7D(%5Cmathbf%7Bw%7D%2C%20b)%20%3D%20%5Cmin_%7Bi%20%3D%201%20...%20n%7D%20%5Cfrac%7B%7C%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20b%7C%7D%7B%7C%7C%20%5Cmathbf%7Bw%7D%20%7C%7C%7D%20%5Cend%7Balign%7D

https://chart.googleapis.com/chart?cht=tx&chl=%7C%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20b%7C 的絕對值部份不是那麼好處理,我們可以把他替換成 https://chart.googleapis.com/chart?cht=tx&chl=y_i%20(%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20b),反正他一定恆正。

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Balign%7D%20%5Carg%5Cmax%20_%7B%5Cmathbf%7Bw%7D%2C%20b%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Ctext%7Bmargin%7D(%5Cmathbf%7Bw%7D%2C%20b)%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%5Cgt%200%20%5Cend%7Balign%7D
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Balign%7D%20%5Ctext%7B%20%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Ctext%7Bmargin%7D(%5Cmathbf%7Bw%7D%2C%20b)%20%3D%20%5Cmin_%7Bi%20%3D%201%20...%20n%7D%20%5Cfrac%7By_i%20(%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20b)%7D%7B%7C%7C%20%5Cmathbf%7Bw%7D%20%7C%7C%7D%20%5Cend%7Balign%7D

Scalling trick

對於以下的部份,我們可以進一步簡化。

https://chart.googleapis.com/chart?cht=tx&chl=%5Ctext%7Bmargin%7D(%5Cmathbf%7Bw%7D%2C%20b)%20%3D%20%5Cmin_%7Bi%20%3D%201%20%5Cdots%20n%7D%20%5Cfrac%7By_i%20(%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20b)%7D%7B%7C%7C%20%5Cmathbf%7Bw%7D%20%7C%7C%7D

對於一條直線 https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20b%20%3D%200 來說,縮放 c 倍基本上是沒有影響的 https://chart.googleapis.com/chart?cht=tx&chl=c%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20cb%20%3D%200。所以我們就乾脆將這個值縮放成剛好是 1,像下面這樣:

https://chart.googleapis.com/chart?cht=tx&chl=%5Cmin%20_%7Bi%20%3D%201%20%5Cdots%20n%7D%20y_i%20(%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20b)%20%3D%201

這樣有什麼好處呢?如果你把他代回去我們的最佳化目標的話,margin 的大小是不是變成這樣了呢?

https://chart.googleapis.com/chart?cht=tx&chl=%5Ctext%7Bmargin%7D(%5Cmathbf%7Bw%7D%2C%20b)%20%3D%20%5Cfrac%7B1%7D%7B%7C%7C%20%5Cmathbf%7Bw%7D%20%7C%7C%7D

而且我們也省掉了 https://chart.googleapis.com/chart?cht=tx&chl=y_i%20(%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20b)%20%5Cgt%200 這個限制,畢竟最小的資料點計算出來至少有 1。整個問題就變成了這樣:

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Balign%7D%20%5Carg%5Cmax%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%7B%7C%7C%20%5Cmathbf%7Bw%7D%20%7C%7C%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%5Cmin%20_%7Bi%20%3D%201%20...%20n%7D%20y_i%20(%5Cmathbf%7Bw%7D%5ET%20%5Cmathbf%7Bx_i%7D%20%2B%20b)%20%3D%201%20%5C%5C%5C%5C%20%5Cend%7Balign%7D

min 還是個不好處理的運算,我們與其求某個資料點代入最小值會是 1,我們不如放寬限制,變成所有資料點帶入公式都會 https://chart.googleapis.com/chart?cht=tx&chl=%5Cge%201

https://chart.googleapis.com/chart?cht=tx&chl=%5Cmin%20_%7Bi%20%3D%201%20%5Cdots%20n%7D%20y_i%20(%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20b)%20%3D%201%20%5CRightarrow%20y_i%20(%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20b)%20%5Cge%201

最後,數學家都會有點潔癖,將問題變成他們喜歡的形式。像是求倒數的最大值,不如我們求最小值。要求 https://chart.googleapis.com/chart?cht=tx&chl=%5Cmathbf%7Bw%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%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

maximum-margin classifier 的最終形式就完成了!這也是支持向量機(support vector machine)的雛型。


上一篇
03 從線性迴歸到感知器
下一篇
05 從 maximum-margin classifier 到 kernel SVM
系列文
機器學習模型圖書館:從傳統模型到深度學習31

尚未有邦友留言

立即登入留言