# 林軒田機器學習基石筆記 - 第十二講
###### tags: `林軒田` `Maching Learning` `機器學習基石`

---

>* **本文為一系列課程之筆記，建議從" [機器學習基石筆記-1](https://hackmd.io/s/ryxzB7LwN) "開始閱讀**
>>
>* **本文討論內容請參考:
機器學習基石第十二講 : Non-Linear Transformation**
>
>* **本篇所有圖片部分由筆者製作，其它均為機器學習基石課程內容講義**
>
---
<center>


</center>

上圖是一個 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$


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


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

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

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

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


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


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


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

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

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


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

---

後記 :

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