林軒田機器學習基石筆記 - 第十二講

發表於 更新於 分類於 ， 閱讀次數： Disqus：

  • 本文為一系列課程之筆記，建議從" 機器學習基石筆記-1 "開始閱讀

  • 本文討論內容請參考: 機器學習基石第十二講 : Non-Linear Transformation

  • 本篇所有圖片部分由筆者製作，其它均為機器學習基石課程內容講義

上圖是一個 Non-Linear Separable ( Circle Separable ) 的情況，在現實中，絕大多數的情況都是非線性可分。

Linear Separable 的情況下， \(d_{vc}\) ( 複雜度 ) 受到控制，很容易可以確保 \(E_{in}\) 與 \(E_{out}\) 會很接近，但是在 Non-Linear 的情形下， \(d_{vc}\) 是不受控制的，用任何的直線都會造成 \(E_{in}\) 極高。

Z-space transformation

我們從上例來看 :

這樣的 Circle Separable 我們可以輕易的造出一個圓來作為 hypothesis

\(h_{SEP}(\mathbb{X})=Sign(-x_1^2-x_2^2+0.6)\) ( 過原點，半徑為 \(\sqrt{0.6}\) 的圓 )

這導致整個 hypothesis 變成一個 Quadratic (二次) Hypothesis，為了想要使用我們先前學過的 linear classification 因此必須在二次項部分做一個轉換

\(\phi\) : \(X\longrightarrow Z\) \(\phi(\mathbb{X})=\mathbb{Z}\Longrightarrow \phi((1,x_1,x_2))=(1=z_0,x_1^2=z_1,x_2^2=z_2)\)

\(\therefore \tilde{h}(\mathbb{Z})=Sign((-1)\cdot z_1+(-1)\cdot z_2+(0.6)\cdot z_0 )\)

\(=Sign(\tilde{w}_1z_1+\tilde{w}_2z_2+\tilde{w}_0z_0)=Sign(\tilde{\mathbb{W} }^T\phi(\mathbb{X}))\)

這一連串的步驟其實就是把原本 X 空間的向量轉成 Z 空間的一次方向量，然後我們再於 Z 空間裡面進行我們先前所學的線性操作。

(我借用 SVM 的 wiki 其中一張圖，我覺得可以很明確表達出整個 Transformation 的概念 )

截至目前為止我們都僅討論「特殊」的 Quadratic Hypothesis ( 過原點、無一次項 )，下列條列出這些特殊形態經過轉換後 \(\mathbb{W}\) 的型態 :

General Quadratic Hypothesis Set

如果我們的二次式並沒有像上述一樣這麼特殊呢 ? 應該說，現實的狀況都沒有這麼的特殊，我們必須要有一套一般化的 Transformation :

\(\phi\) : \(X\rightarrow Z\) via \((1,x_1,x_2)\rightarrow(1,x_1,x_2,x_1^2,x_1x_2,x_2^2)=(z_0,z_1,...,z_5)\)

\(\Longrightarrow \mathbb{H}_{\phi}=\left\{h(\mathbb{X})\mid h(\mathbb{X})=\tilde{h}(\phi(\mathbb{X}))\right\}\)

\(\Longrightarrow\) 在 Z-space 中的 perceptron 可對應到 X-space 中的 quadratic hypothesis

\(\Longrightarrow\) 在 Z-space 中好的 perceptron 理應可對應到 X-space 中好的 quadratic hypothesis

The Non-Linear Transformation Steps

Step 1 : 將 \((\mathbb{X}_n,y_n)\) 轉換成 \((\mathbb{Z}_n,y_n)\)

Step 2 : 於 Z-space 中進行 linear 操作找出 \(\tilde{\mathbb{W} }\)

Step 3 : \(g(\mathbb{X})=Sign(\tilde{\mathbb{W} }^T\phi(\mathbb{X}))\)

Q次多項式轉換 on d-dimension

上面說的多項式轉換，除了在二次式上進行一般化外，我們更可以泛化到更高次方。

\(\phi\) : \(X\longrightarrow Z\) via \((1,x_1,x_2,...,x_d)\longrightarrow(1,x_1,...,x_d,x_1^2,x_1x_2,...,x_d^2,......,x_1^Q,x_1^{Q-1}x_2,...,x_d^Q)\)

從上式我們可以知道 經過Q次方轉換後的 Z-space 維度\((d_{vc}(\mathbb{H}_{ {\phi}_Q}))=1+\tilde{d}={ {Q+d}\choose{Q} }={ {Q+d}\choose{d} }\in O(Q^d)\)

\(\therefore Q\uparrow\Longrightarrow d_{vc} (\mathbb{H}_{ {\phi}_Q})\uparrow\)

我們該如何選擇 Q 值 ?

機器學習中有兩個最核心的問題 : * \(E_{out}\approx E_{in} ?\) * \(E_{in}\) 夠小嗎 ?

  1. 如果我們使用了較高次方的多項式轉換，複雜度較高，\(E_{in}\downarrow\) 但 \(E_{out}\uparrow\)

  1. 那我們反過來試著讓複雜度盡量小呢 ? 從本篇筆記最初的那個 Circle Separable的例子來看，我們好像可以找到複雜度很小的 Hypothesis

這在機器學習中人們常常會犯的錯誤，從資料本身，經由人類使用者來做修正，這樣的修正並非機器學習而得，而是經由我們人腦運作後的結果，這些本該是機器學習的計算成本，但我們將其忽略。

這樣的方式往往會高估了我們產生的 model。

那到底我們該怎麼做選擇呢 ?

我們來重新思考並重述整個多項式變換的過程 :

從低次方轉換我們可以迭代到高次方轉換，從這樣子的代換過程我們可以了解整個 Hypothesis Set 的結構

從上圖我們可以推出下列結果 :

當我們的 Hypothesis Set 變大，相當於我們可以被 shatter 的點變多， 於是 \(d_{vc}\) 會持續增加

當我們的 Hypothesis Set 變大，也相當於我們更有機會找到更低的 \(E_{in}\)

這樣的結果我們其實也在前面已經有看過了 :

從上面這些結果來看，我們如果一開始使用較高的Q值，容易出現 \(E_{out}\) 過大的情況，最好的方式我們還是從低次方開始向上迭代，找到最好的 \(d_{vc}^*\)

後記 :

這一篇章感覺來的有點突兀，但其實它非常的重要，我們在機器學習中常聽到的 支持向量機 (SVM) 便是由這樣的概念出發，不同的變換 (不一定是多項式轉換)，也會形成不同的 kernel ，這些都不斷的圍繞在往後機器學習技法課程中。