---
tags: 機器學習基石下：方法篇
---

Ch12 Nonlinear Transformation
===

## Content

[TOC]

## [Slides & Videos](https://www.csie.ntu.edu.tw/~htlin/mooc/)

## [Quadratic Hypothesis](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/nlWdl/quadratic-hypothesis)

在先前的章節中，學習的機器學習模型都為線性模型，即假設空間都為線性的（2D平面中為一條直線，3D空間為一個平面），使用的得分為線性得分（linear scores）$s=w^Tx$。其中 $x$ 為特徵值向量，$w$ 為權重。

### Linear Hypothesis

線性模型的優點是理論上可以使用 VC 限制來約束約束（假設是非線性的各種曲線或超平面，則每種假設都可以完全二分，即有 $2^N$ 種二分類。），這保證了 $E_{in} \approx E_{out}$（VC-Dimension比較小）。但對於線性不可分（non-linear separable）的問題（如下圖），$E_{in}$ 很大，從而導致 $E_{out}$ 也很大，導致分類結果不理想。


- linear 好處：VC dimension 是有限的，所以 $E_{in}$ 和 $E_{out}$ 通常很接近
- linear 壞處：$E_{in}$ 常常會很大
- 那要怎樣突破 linear 的限制?

### Circular Separable

為了解決線性模型的缺點，我們可以使用非線性模型來進行分類。基於這個非線性思想，先前討論的 PLA、Regression 問題也可以透過非線性的形式來求解。例如可以使用一個半徑為 $\sqrt{0.6}$ 圓心在原點的圓劃分，它的 hypotheses可以寫成：$h_{SEP}(x) = sign(-x^2_1 - x^2_2 + 0.6)$

此公式的意義為將樣本點到原點距離的平方與數值 0.6 作比較，圓形將樣本集分離，圓形內部是正類，標記為 +1，外部是負類，標記為 -1，此種方式稱作圓形可分（circular separable）。如下圖所示：


- 它不是線性可分，但我們可以說它圓圈圈可分XD
- 但這樣可能要再從頭來一次說，怎麼設計一個圓圈圈演算法，再從頭把線改成圓圈圈
- 接下來說明如何系統化地設計這些演算法。

### Circular Separable & Linear Separable

將公式（12-01）做如下轉換，變成熟悉的線性模型：


原公式中，$h(x)$ 的權重為 $w_0 = 0.6$，$w_1 = -1$，$w_2 = -1$，但是 $h(x)$ 的特徵不是線性模型的 $(1,x_1,x_2)$，而是$(x,x^2_1,x^2_2)$。通過令 $z_0 = 1, z_1 = x^2_1, z_2 = x^2_2$，$h(x)$ 可以變成上式。

這種 $x_n \rightarrow z_nx$ 的變換可以看作將 $X$ 空間中的點映射到 $Z$ 空間中去，即從 $X$ 空間的圓形可分割映射到 $Z$ 空間的線性可分。$Z$ 域中的直線對應於 $X$ 域中的圓形。背後的思想是透過非線性的特徵變換 $ \Phi$（feature transform） 將圓形可分（非線性可分）變成線性可分。


> - 我們先把 $x_0,x_1^2,x_2^2$ 用 $z_0,z_1,z_2$ 代替
> - 然後用 $\tilde w$ 代替 $w$，表示這不是原來針對 $x$ 的 weight
> - 然後就可以很簡潔的使用 $\text{sign}(\tilde w^Tz)$ 來代表我們的 hypothesis $h(x)$
> - 我們可以把它想成，從原來的空間 $\mathcal X$ 轉換到另一個空間 $\mathcal Z$，使得轉換後是 linear separable 的。
- **這樣的轉換我們稱為 feature transform $\phi$**
> - 反過來說，如果在新的空間 $\mathcal Z$ 是 linear separable 的，那就代表我在原來的空間 $\mathcal X$ 一定可以用圓圈圈分開嗎？

那麼問題來了，已知在 $X$ 域中圓形可分，在 $Z$ 域中線性可分；反過來，如果在 $Z$ 域中線性可分，是否在 $X$ 域中一定圓形可分呢？

答案是否定的。由於權重向量 $w$ 取值不同，$X$ 域中的 hypothesis 可能是圓形、橢圓、雙曲線等等多種情況。

### Linear Hypothesis in $\mathcal Z$ Space



### General Quadratic Hypothesis Set

透過這種形式轉換的 $Z$ 空間的直線對應原 $X$ 空間中特殊的二次曲線（quadratic curves）。說「特殊」是因為表示的圓只能是圓心過原點的圓，不能隨意表示各種情況的圓。如果想要表示 $X$ 空間中所有的二次曲面，應設計出一個更大的 $Z$ 空間，其特徵轉換如公式為：


透過以上特徵轉換，$Z$ 空間中的每個超平面就對應 $X$ 空間中各種不同情況的二次曲線（圓、橢圓、雙曲線）。則 $X$ 空間中的假設空間 $H$ 為：


上式中，$\widetilde{h}$ 表示 $Z$ 空間中的假設函數。

> - 這樣就包含了所有二次的 hypothesis
> - 在 $\mathcal Z$ 中的 perceptrons 等同於 $\mathcal X$ 中的 quadratic hypotheses
> - **這些 quadratic hypothesis 已經包含了 linear hypothesis 和 constants (as degenerate cases)**

## [Nonlinear Transform](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/8i4AH/nonlinear-transform)

### Good Quadratic Hypothesis

從 $X$ 空間轉換到 $Z$ 空間，則在 $Z$ 空間中獲得的好的線性假設函數，相當於在 $X$ 空間中獲得了好的二次假設函數，即在 $Z$ 空間中存在線性可分的直線對應於在 $X$ 中（非線性）可分的二次曲線。目標就是在 $Z$ 空間中找到一個最佳的分類線（假設函數）。


利用映射變換的思想，透過映射關係，把XXX空間中的最高階二次的多項式轉換為ZZZ空間中的一次向量z，即從二次假設轉換成了感知器問題。用z 值代替x 多項式，其中向量z 的個數與XXX空間中x 的多項式的個數相同（包含常數項）。這樣就可以在ZZZ域中利用線性分類器進行訓練。訓練好之後，再將z 替換為x 的多項式即可（反變換）。具體過程如下：

### The Nonlinear Transform Steps

$X$ 空間中的數據為 $\{(x_n,y_n)\}$，$Z$ 空間的資料集為 $\{(z_n= \Phi_2(x_n),y_n)\}$；
透過特徵變換函數 $\Phi$ 將 $X$ 空間中線性不可分的資料集 $\{(x_n,y_n)\}$ 變換為 $Z$ 空間中線性可分的資料集 $\{(z_n= \Phi_2(x_n),y_n)\}$；
使用線性分類演算法和 $Z$ 空間的資料集 $\{(z_n,y_n)\}$ 獲得表現良好的感知器模型（最優權重向量）$\widetilde{w}$；
最後得到最優的假設函數 $g(x) = (\widetilde{w}^T \ \Phi(x))$。


上圖中，最下邊兩張圖表達了這個想法的核心思想。判斷某個樣本屬於哪個類別，只需要將 $X$ 空間中的資料變換到 $Z$ 空間；然後使用 $Z$ 空間中的假設函數（線性分類器）將樣本分類；最後反變換到 $X$ 空間，得到真實類別。

這類模型由兩部分構成：

- 非線性變換函數 $\Phi$：透過特徵變換，將非線性可分問題轉換為線性可分問題；
- 線性模型：包括先前學習的二分類、線性迴歸和 Logistic 迴歸等；

使用以上求解非線性分類的思路可以解決二次 PLA，二次迴歸，三次迴歸，…，多項式迴歸等多種問題。

> - 注意這裡的反運算 $\phi^{-1}$ 不一定真的存在，只是想像說如果反運算回來可能長這樣
- 因為 $x$ 對應到 $z$ 不一定會是一對一的
> - 其實我們是在看說 $\mathcal X$ 裡面每一個點對應到 $\mathcal Z$ 之後會被分成哪一類，再畫出左邊那種圖。

### Nonlinear Model via Nonlinear $\phi$ + Linear Models

- 有了 **nonlinear transform 加上 linear model** 之後，我們就可以做很多事情了。

### Feature Transform $\phi$

特徵變換（feature transform）的想法非常常見，例如我們熟知的手寫數字辨識任務中，從原始的像素值特徵轉換為具體的特徵，例如密度、對稱性等：


## [Price(代價) of Nonlinear Transform](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/DbaXv/price-of-nonlinear-transform)

### Computation / Storage Price

如果 $X$ 的特徵維度為 $d$ 維，也就是包含 $d$ 個特徵，那麼二次多項式個數，即 $Z$ 空間的特徵維度為：$\breve{d} = 1 + C^1_d + C^2_d + d = \frac {d(d+3 )}{2} + 1$
如果 $X$ 特徵維度是 2 維的，即 $(x_1, x_2)$，那麼它的二次多項式為：$(1, x_1, x_2, x^2_1, x_1x_2, x^2_2)$，有六項。

如果階數為 $Q$，$X$ 空間的特徵維度為 $d$ 維，則它的 $Z$ 空間特徵維度為：$\breve{d} = C^Q_{Q+d} + C^d_{Q+d} = O(Q^d)$


> - 若想把 $d$ 個維度的 $x$ 轉換成 $Q$ 次多項式，會有 $1+\tilde d$ 個 dimension，那麼 $\tilde d$ 是多少呢？
- 這裡我們一樣在 $d$ 上面加波浪符表示是在 $\mathcal Z$ 空間發生的事。
> - 高中學的重複組合：$d$ 種不同的東西，可以重複取，取 $Q$ 個出來，有幾種取法？
- $H^d_Q=C^{Q+d}_Q=C^{Q+d}_d=O(Q^d)$
- 這應該是 $Q$ 次項的解，而 $Q-1,Q-2,...1$ 都會小於 $Q$ 次項的數量，所以我們給 upper bound $O(Q^d)$
> - 所以計算上、儲存上，我們都要花額外的力氣，要解這個問題變得很困難。

### Model Complexity Price

特徵轉換還帶來另一個問題。在前面的章節中講述過，模型參數的自由度大概是這個模型的 VC 維度。$z$ 域中特徵個數隨著 Q 和 d 增加變得很大，同時權重 w 也會增加，即自由度增加，VC-Dimension 增加。令 $z$ 域中的特徵維度為 $\breve{d} + 1$，在 $Z$ 域中，任何 $\breve{d} + 2$ 的輸入都不能被 shattered，同樣，在 $X$ 域中，任何 $\breve{d} + 2$ 的輸入也不能被 shattered；$\breve{d} + 1$是 VC-Dimension 的上界，如果 $\breve{d} + 1$ 很大，對應的 VC-Dimension 也會很大。根據先前章節課程的討論，VC-Dimenslon 過大，模型的泛化能力會比較差。


> - $Q$ 變大，則 VC dimension 也會變大
> - 我最多會有 $\tilde d+1$ 的 VC dimension，因為任何 $\tilde d+2$ 個點在 $\mathcal Z$-space 都沒辦法被 perceptron 給 shatter，這個之前證過了。

### Generalization Issue

下例解釋了 VC-Dimension 過大，導致分類效果不佳的原因：


左邊用直線進行線性分類，有部分點分類錯誤；右邊用四次曲線進行非線性分類，所有點都分類正確，那麼哪一個分類效果好呢？單從平面上這些訓練資料來看，四次曲線的分類效果更好，但是四次曲線模型很容易帶來過擬合的問題，雖然它的 $E_{in}$ 比較小；泛化能力上，左邊的分類器比較好。也就是說，VC-Dimension 過大會帶來過擬合問題，$\breve{d} + 1$ 不能過大。

### Danger of Visual Choices

那麼如何選擇合適的 Q，避免過度擬合，提高模型泛化能力呢？一般情況下，為了盡量減少特徵自由度，會根據訓練樣本的分佈情況，人為地減少、省略一些項。但是，這種人為地刪減特徵會帶來一些「自我分析」代價，雖然對訓練樣本分類效果好，但是對訓練樣本外的樣本，不一定效果好。所以，一般情況下，還是要保存所有的多項式特徵，避免對訓練樣本的人為選擇。


## [Structured Hypothesis Sets](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/ZyLyN/structured-hypothesis-sets)

### Polynomial Transform Revisited

下面討論 $X$ 空間到 $X$ 空間的多項式變換。

如果特徵維度是一維的，變換多項式只有常數項：
$Φ_0(x) =(1)$

如果特徵維度是兩維的，變換多項式包含了一維的 $Φ_0(x)$：
$Φ_1(x) = (Φ_0(x), x_1,x_2, . . . ,x_d)$

如果特徵維度是三維的，變換多項式包含了二維的 $Φ_1(x)$：

$Φ2(x) = (Φ_1(x), x^2_1,x1x2, . . . , x^2_d)$

以此類推，如果特徵維度是 Q 維的，則它的變換多項式為：

$Φ_Q(x) = (Φ_{Q−1}(x), x^Q_1,x^{Q−1}_1x2, . . . ,x^Q_d)$

這種結構稱為 **Structured Hypothesis Sets**：


### Structured Hypothesis Sets

對於這種 Structured Hypothesis Sets ，VC-Dimention 和 $E_{in}$ 滿足如下關係：


VC-Dimention 與錯誤率之間的關係如上曲線圖。

由上圖易知，隨著變換多項式的階數增大，雖然 $E_{in}$ 逐漸減小，但模型複雜度會逐漸增大，造成 $E_{out}$ 很大，所以階數不能太高。


如果選擇的階數很大，能使 $E_{in} \approx 0$，但泛化能力很差，這種情況叫做 tempting sin。所以，一般做法是先從低階開始，如先選擇一階假設，看看 $E_{in}$ 是否很小，如果 $E_{in}$ 夠小就選擇一階，如果很大就逐漸增加階數，直到滿足要求為止。也就是說，盡量選擇低階的假設，這樣才能得到泛化能力較強的模型。

> - 越高次多項式的 hypothesis set，VC dimension 越高，可以 shatter 越多點，$E_{in}$ 越低
- 然而 $E_{in}$ 和 $E_{out}$ 差距越大
> Linear Model First!

### Summary
本課介紹了非線性變換的整體流程（透過非線性變換，將非線性模型映射到另一個空間，轉換為線性模型，再來進行線性分類。

之後介紹了非線性變換存在的問題：時間複雜度和空間複雜度的增加。

最後介紹了在付出代價的情況下，使用非線性變換的最安全做法：盡可能使用簡單的模型，而不是模型越複雜越好。