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

tags: 林軒田 Maching Learning 機器學習基石

---

• 本文為一系列課程之筆記，建議從" 機器學習基石筆記-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 因此必須在二次項部分做一個轉換

$\varphi$ :

$X⟶Z$

$\varphi (\mathbb{X})=\mathbb{Z}⟹\varphi ((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}}_1{z}_1+{\tilde{w}}_2{z}_2+{\tilde{w}}_0{z}_0)=Sign({\tilde{\mathbb{W}}}^T\varphi (\mathbb{X}))$

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

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

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

$\mathbb{W}$ 的型態 :

General Quadratic Hypothesis Set

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

$\varphi$ :

$X\to Z$ via

$(1,x_1,x_2)\to (1,x_1,x_2,x_1^2,x_1{x}_2,x_2^2)=(z_0,z_1,...,z_5)$

$⟹{\mathbb{H}}_{\varphi }=\{h(\mathbb{X})\mid h(\mathbb{X})=\tilde{h}(\varphi (\mathbb{X}))\}$

$⟹$ 在 Z-space 中的 perceptron 可對應到 X-space 中的 quadratic hypothesis

$⟹$ 在 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\varphi (\mathbb{X}))$

Q次多項式轉換 on d-dimension

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

$\varphi$ :

$X⟶Z$
via

$(1,x_1,x_2,...,x_d)⟶(1,x_1,...,x_d,x_1^2,x_1{x}_2,...,x_d^2,......,x_1^Q,x_1^{Q-1}{x}_2,...,x_d^Q)$

從上式我們可以知道
經過Q次方轉換後的 Z-space 維度

$(d_{vc}({\mathbb{H}}_{{\varphi }_Q}))=1+\tilde{d}=(\genfrac{}{}{0ex}{}{Q+d}{Q})=(\genfrac{}{}{0ex}{}{Q+d}{d})\in O(Q^d)$

$\therefore Q\uparrow ⟹d_{vc}({\mathbb{H}}_{{\varphi }_Q})\uparrow$

我們該如何選擇 Q 值 ?

機器學習中有兩個最核心的問題 :

• $E_{out}\approx E_{in}?$
• $E_{in}$ 夠小嗎 ?

(1) 如果我們使用了較高次方的多項式轉換，複雜度較高，

$E_{in}\downarrow$ 但

$E_{out}\uparrow$

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

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

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

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

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

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

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

當我們的 Hypothesis Set 變大，相當於我們可以被 shatter 的點變多，
於是

$d_{vc}$ 會持續增加

當我們的 Hypothesis Set 變大，也相當於我們更有機會找到更低的

$E_{in}$

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

從上面這些結果來看，我們如果一開始使用較高的Q值，容易出現

$E_{out}$ 過大的情況，最好的方式我們還是從低次方開始向上迭代，找到最好的

$d_{vc}^{\ast }$

---

後記 :

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