機器學習基石系列(9) — 非線性轉換
前面的系列文，討論的基本上是「資料線性可分」的大前提。意思是說資料基本上線性可分；即使有一些資料無法線性可分，那也可以當作雜訊，或者是誤差來處理，在最後歸納的分類上，是可以做出線性分割的趨勢的。
那這一篇，就來討論「資料線性不可分」的情況。大部分的資料都無法線性分割的時候要怎麼辦?先來考慮一下線性可分這件事情，它在資料分布圖裡面的意義就是可以用直線分割，如下：
很直觀。線性不可分就是資料沒辦法用一條直線清楚的劃分楚河漢界：
也很直觀。圖2.其實用眼睛可以大概看出分割的趨勢：
用一個圓可以做到分割。那我們接下來該怎麼做?
特徵轉換
我們為圖3增添一些條件好了，例如，這個圓的半徑是0.6，而其圓心所在位置剛好是座標軸原點(0,0)。那麼每一個資料點，可以藉由和原點之間的距離是否超過0.6來分類，其h(x)可以寫為
這樣也算是找到一個分割的方法，可以用數學式表示。不過，比起線性，當然是複雜的。有沒有什麼其他方法?
式1裡面，在等號右邊的sign裡有三個項，分別是
- (x_1)²項，其係數為-1。
- (x_2)²項，其係數亦為-1。
- 常數項，其係數為0.6。
如果把(x_1)²項替換成另一個變數z_1，(x_2)²換成z_2，常數項換成z_0，則原本的式子可以寫為
其中w是對應的係數，因為z所在的空間座標已非x的，所以讓他們長一隻蚯蚓以示區別。再把他用矩陣的方式表列，就可以縮寫回
這個我們在前面謝列文章中提到，線性分類的核心式。在x坐標系的時候，資料線性不可分，圓形可分；到了z坐標系，資料線性可分。畫成圖比較一下：原本在x坐標系的資料分布是圖3，到了z坐標系變成：
這樣的過程稱作特徵轉換(feature transform，φ)。在這裡就是非線性轉換。經過轉換的資料點(z_0, z_1, z_2)，可以表示為
至於假設h(z)，可以表示為
我們把注意力先放到長蚯蚓的w們。這些係數經過調整，在x坐標系上可變換成許多不一樣的圖形。例如：
- (0.6,-1,-1)：圓圈分隔(圈圈在圓圈內)
- (-0.6,+1,+1)：圓圈分隔(圈圈在圓圈外)
- (0.6,-1,-2)：橢圓分隔
- (0.6,-1,+2)：雙曲線分隔
- (0.6,+1,+2)：全部都是圈圈
當然，目前因為我們沒有x的一次項，所以還有一些限制。如果圓心不在圓點，一定會出現x的一次項。所以我們再調整一下，讓φ變成
φ_2表示其為二次轉換，把一次項，還有相乘項也放進去了。那其對應的，位在z坐標系上的hypothesis sets就可以表示為
這樣一來就可以囊括所有的二次曲線，圓形、橢圓、斜橢圓、雙曲線、拋物線都不是問題。其實，他也包括直線，所有的二次項係數設為0就可以了。
所以，利用特徵轉換處理分類問題的流程大約如下：
- 把資料從x坐標系投影到z坐標系。
- 在z空間找到好的分隔線，就是式2。
- 最後回傳x坐標系。
- 預測的時候，把資料轉換到z坐標系上面判斷就可以了，而不需要把z坐標系的分隔線投影回x坐標系，然後再來看資料到底屬於哪一邊。
那所以現在問題就變成：如何在z空間找到好的分界線，以及要投影到哪個空間了。因為可以投射到二次空間，那當然也可以投射到三次，或甚至更高維度的空間。這兩個問題的排列組合千變萬化。
甜蜜的毒藥?
這裡先暫停一下，有一個問題可以先弄清楚：如果資料要做二次轉換，是不是只能在二維空間?意即，資料只能投影到二維空間才能做二次轉換嗎?
不是的。資料可以在更高維的空間進行二次轉換，其最低要求是二維。例如在d維的空間，其有x_1, x_2, x_3,…x_d及常數項。如果要在d維空間進行二次轉換，在二次項的部分可以從d個裡面選兩個，以及選同一個項兩次；一次項的部分有d個可以選；常數項就是一個，總共湊起來是
維度空間。
現在我們進行Q次特徵轉換，其式為：
x有d個，總維度則是d+1，因為還有常數項。在這之中要挑選滿足Q次多項式的項目，等於把前述的在d維空間進行二次轉換擴大到Q次。這叫做「重複組合」：
然後如果加入常數項的1，得到
d若為常數，則上式的項數約略為Q^d。
計算項數做什麼呢?這就表示，越高次的多項式轉換，需要越多的資源進行儲存和運算。每一個項都需要額外的資源來儲存及運算它。
同時，這些項目對應的w(長蚯蚓的)也有d+1。這就是自由度，它們的變化影響挑選的分割線，所以能有多少變化也是它們的項數決定的。自由度的數值和VC dimension約略相當。
如何挑選適合的模型?
回來看看機器學習可行的基本精神：E_in夠小，以及E_in和E_out相當。套用在非線性轉換的這些高維度模型，發現了什麼?
如果我們用人眼來挑選模型，可行嗎?像圖2那樣的資料分布，一眼就看的出來。不過，這後面有兩個問題：首先當然是萬一資料是投影到高維的抽象空間才線性可分時，肉眼要怎麼看?
另一個問題則是肉眼判斷的盲區：模型的複雜度被你的眼睛和腦袋取代了。假設現在資料真的是像圖2分布好了，我們用二次曲線的話，
本來是VC dimension為6的。後來，發現他在原點，一次項跟相乘項都可以不用，變成
VC dimension變成3。然後再看一看，發現他用正圓就好，所以
只剩2了。最後發現他的半徑只要0.6，所以
VC dimension剩下1。注意，當你把這個式子寫下來並得到結論的時候，這個過程本來應該是機器學習要做的。所以總成本沒有變，指是你負擔了一部分的成本。同樣的道理，這有可能在高維去做嗎?回到根本，機器學習的目的不就是取代這個過程嗎?怎麼又用人力把它搶回去做了呢?
因此，用視覺的方法實際上並沒有提升效率，而且遇到高維度的投射資料也不可行。那還有什麼方法沒有?
先把Q次多項式用遞迴的方式表達：例如，假設
其常數項用0次轉換的方式表示，則一次轉換為
二次轉換為
前面是一次轉換。常數項被包括在一次轉換裡面。以此類推，到了Q次轉換時為
從遞迴表示式可以發現，每當Q推往新的維度時，舊的維度也被包在裡面，算是一個係數為0的特殊狀況。於是，
為求方便，把φ拿掉，畫成邏輯圖：
是一種巢狀結構。他們的VC dimension關係就是
照這樣看起來，只要把維度增加，可以保證E_in只減不增，為何?因為就有機會讓E_in更小，如果後來發現增加維度之後找到的所有hypothesis都比原本維度的更大，那跳回舊維度(常數項)就好了。所以E_in的關係是
作圖如下。這張圖，在系列(4)的文章中已經出現過了。
雖然維度增加會讓E_in有機會越來越小，但機器學習的另一個核心精神 — E_in和E_out接近 — 卻越來越難做到。這就牽涉到我們下一個單元要討論的過度配適(over fitting)，同樣也是深度學習裡面的一個挑戰。
所以最後，我們到底該如何克服這個甜蜜的毒藥呢?那就是不要吃它。不要一開始就直接選高維度的模型，而應該慢慢爬，從低維度的開始。如果在低維度舊找到小的E_in，那就解決啦，因為這時候E_in和E_out的差距也是比較小的。如果不行，才慢慢往上增加維度，去降低E_in，但不要忘記隨時檢視E_in和E_out的差距，是否還在可以忍受的範圍。
