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

---

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

## Regularization

上一篇介紹了 overfitting ，而 regularization 的目的就是希望當 overfitting 發生時，我們可以經過一些調整來避免其發生。

如果拿先前的多項式為例子，當我們 model complexity 太高，也就是我們使用比較高次方的 Hypothesis Set ，容易造成 overfitting ，那我們 regularization 的概念便是希望從原本的高次方 hypothesis set 往低次方的 hypothesis set 來移動，以避免 overfitting 的發生。


在林軒田的課程中，他利用「限制」的概念來一步一步湊出 L2 regularization，過程我這邊不贅述，可以去參考老師的 course slide，在這裡我想直接從數學的角度直接切入，比較直覺也可以同時理解 L1 及 L2 regularization 。

回到「限制」這個概念，我們要避免在進行 model training 的過程，( 以多項式為例 ) model 會為了貼近 training data 而讓自己的複雜度越來越複雜，次方越來越高，所以我們寧願他不要這麼 fit ，也可以盡量讓他不要 overfitting ，因此我們希望在整個權重上面加上一些限制。

那我們便加入了一個條件 ( constraint ) : $\mathbb{W}^T\mathbb{W}\leq C$

現在我們就是希望在訓練過程中，能找到一個 model 可以在這權重的條件下，找到相對應的最小 error，如若我們以一個回歸問題(error measure : square error)，整個式子便可以用下列方式來寫 :


就幾何意義來說，我們就是把權重限制在一個圓內，找尋在這個圓內的最小 error 會產生在哪裡。

### Lagrange Multiplier

我們現在不是只是單純求解 $E_{in}$ 的最小值，而是在符合條件 $\mathbb{W}^T\mathbb{W}\leq C$ 下的最小值，在數學上便是利用 Lagrange Multiplier 來求解有條件的極值問題 :

( 為了往後計算方便，將 Lagrange Multiplier 調整為 $\frac{\lambda}{N}$ )

所以我們要求解有條件的 $E_{in}$ 極值問題其實就等價於沒有條件的求解上式，於是就可以令上式導數為0來找出我們想要的權重


而我們也稱 $\frac{\lambda}{N}\mathbb{W}^T\mathbb{W}=\frac{\lambda}{N}\sum\limits_{q=0}^{Q}w_q^2=\|\mathbb{W}\|_2^2$ 為 L2 regularizer，加上 L2 regularizer 的正規化方式就稱為 L2 regularization

同樣的，我們可以改變一下我們的 constraint ，若把條件從 $\mathbb{W}^T\mathbb{W}\leq C$ 改為 $\|\mathbb{W}\|_1\leq C$ ，就稱為 L1 regularization ，而 L1 regularizer 為 $\frac{\lambda}{N}\sum\limits_{q=0}^{Q}\mid w_q\mid=\|\mathbb{W}\|_1$

( 想要更清楚理解可以參考 : " [L1 , L2 Regularization 到底正則化了什麼 ?](/SWy1q3M4SnO_qrN2AOaJZg) "一文 )

### $\lambda$ 對於 Regularization 的影響


這倒也是不難理解，當 $\lambda=0$ 時，就等同於沒有加上任何的正則化

而在這邊很有趣的，看似不相干的 $\lambda$ 卻其實也主宰著整個圓的半徑，概念其實我們可以從上圖看出來，當 $\lambda=0$ 時 $\Longrightarrow$ 沒有加上任何的正則化 $\Longrightarrow$ 其實可以當作我取了無窮大的半徑 ( 等於沒有限制 )。

### Regularization 在理論上的保證

求 $E_{in}(\mathbb{W})$ 滿足條件 $\mathbb{W}^T\mathbb{W}\leq C$ 的最優解 : $\underset{\mathbb{W}}{min}E_{in}(\mathbb{W})\ s.t\ \mathbb{W}^T\mathbb{W}\leq C$

$\Longrightarrow$ 求 $E_{aug}(\mathbb{W})$ 的最優解 : $\underset{\mathbb{W}}{min}E_{aug}(\mathbb{W})=E_{in}(\mathbb{W})+\frac{\lambda}{N}\mathbb{W}^T\mathbb{W}$

原始問題 (上式) 會對應到一個 VC Bound


而當我們在進行 $E_{aug}$ 最小化的過程中，其實就在間接地得到 VC Bound 的保證，而不用去找出 $\Omega(\mathbb{C})$

Why ?

我們來比較一下下圖兩式 :


我們可以把 regularizer 當作是單一個 hypothesis 的複雜度 $=\Omega(\mathbb{W})$，那麼 $\Omega(\mathbb{H})$ 便是整個 hypothesis set 整個的複雜度。
從這個方向來看，$E_{aug}$是 $E_{in}$ 加上單一hypothesis複雜度，直觀的來看會比 $E_{in}(\mathbb{W})+\Omega(\mathbb{H})$ 來的小、來的更接近 $E_{out}$。

換個角度來解釋

當我們利用 Lagrange method 來造出 $E_{aug}$ ，對其優化時，已經沒有任何限制，也就是把所有 $\mathbb{W}$ 都考慮進去 ( 把所有 $\mathbb{H}$ 都考慮進去 )，所以其 $d_{vc}=d+1$ 但是我們回到原來有條件的式子來看，事實上我們只考慮了 $\mathbb{H}(C)$，造成這兩個 $d_{vc}$ 差異的原因在於，我們並非直接對 $\mathbb{H}$ 來做限制，而是利用整個演算法來把 $\mathbb{H}$ 壓縮到 $\mathbb{H}(C)\Longrightarrow d_{vc}(\mathbb{H(C)})\overset{defn}{=}d_{eff}(\mathbb{H},\mathcal{A})$

### Choice of Redularizer

從上面 Lagrange Multiplier 的概念來看，我們可以任意地對權重 $w_i$ 加入任何的限制，而課程中林軒田整理了幾種選擇的方向 :


不管我們用什麼方式選擇、選擇了什麼樣子的 regulizer ，最後我們都還有 $\lambda$ 可以拿來做最終的調整。


若只有 L1 L2兩種選擇，我們該怎麼取捨呢?

我們看看 L1 的圖，很容易可以看出，不管 Loss Function 長什麼樣子，最佳解幾乎都會跑到四個頂點上面，而這樣的結果就是指出最優解會出現在大部分權重會等於0，少部分 (甚至只有一個) 權重不等於0的狀況 (我們稱這種情況為 Sparse )，也因此，當我們希望得到的解是 Sparse Solution 時，便建議使用 L1 regularizer 。

### Choice of $\lambda$


這張圖顯示了在某些參數固定的狀況下，我們可以找到的最優 $\lambda$，越多的 noise 就需要越多的 regularization 。

不過重點還是在，通常資料在手上，我們很難確定 noise 有多少，既然未知 noise ，又要怎麼找出比較好的 $\lambda$ 呢 ? 這時候就會面臨到如何選擇出一個最優 model 的問題........

---

## Validation

在這一段時間的課程中，我們在使用機器學習時，總是會遇到無數個選擇 :


沒有一種組合是可以適用於各式各樣的資料，因此我們必須要多方嘗試來選出一個最好的組合，最好的 $g\approx f$

### Model Selection
Given M models $\mathbb{H}_1,\mathbb{H}_2\ldots\mathbb{H}_M$ corresponding to algorithm $\mathcal{A}_1,\mathcal{A}_2\ldots\mathcal{A}_M$ and unknown $E_{out},\mathbb{P}(\mathbb{X}),\mathbb{P}(y\mid\mathbb{X})$
We want to select $\mathbb{H}_{m^*}$ s.t. $g_{m^*}=\mathcal{A}_{m^*}(\mathbb{D})$ and $E_{out}(g_{m^*})$ is low .

依照上面對於 model selection 的描述，我們可以有兩個面向來分析 :

**1. 從 「找出最低 $E_{in}$」的角度出發** : $m^*=arg\underset{1\leq m\leq M}{min}(E_m=E_{in}(\mathcal{A}_m(\mathbb{D})))$

$\Longrightarrow$ Overfitting : 高次方轉換必然比低次轉換來的好，$\lambda=0$ 表現得會比 $\lambda>0$ 更好

$\Longrightarrow$ Generalization 差 : 我們相當於是拿 $\mathbb{H}_1\cap\mathbb{H}_2\ldots\cap\mathbb{H}_M$ 來找一個 $g$ ，$d_{vc}=$ Model Complexity 太高

從這裡看的出來，由 $E_{in}$ 來做選擇會非常危險

**2.從「待測資料中找出 $E_{test}$ 最低」的角度出發** : $m^*=arg\underset{1\leq m\leq M}{min}(E_m=E_{test}(\mathcal{A}_m(\mathbb{D})))$

如果這樣做，的確可以有夠強的保證可以確保此模型可行

$E_{out}(g_{m^*})\leq E_{test}(g_{m^*})+O(\sqrt{\frac{\log M}{N_{test}}})$

但實務上，測試資料無法，也不該取得用來做 Model Selection。

## Validation

從上面的分析，第一個方向完全不可行，於是我們由第二個方向出發找出了一個折衷的作法 : 從手邊有的 $\mathbb{D}$ 中取一些資料來作為 Validation set ( $\mathbb{D}_{val}$ )

$\Longrightarrow \mathbb{D}=\mathbb{D}_{train}+\mathbb{D}_{val}$
( 原本 $\mathbb{D}$ 要拿來計算 error 又要拿來做 model selection，現在可以分開讓 $\mathbb{D}_{train}$ 做 model selection 而讓 $\mathbb{D}_{val}$ 計算 error )


* $g_m^-$ : 以負號代表 $\mathbb{D}_{train}$ 所用的資料數量比 $\mathbb{D}$ 少

* $\mathbb{D}_{val}$ : 為了使 $E_{out}$ 與 $E_{val}$ 有相關，因此 $\mathbb{D}_{val}$ 也必須是由 $\mathbb{D}$ 中隨機平均的抽出 K 個。

* 如此一來，我們仍然能有夠強的理論保證可行 : $E_{out}(g_m^-)\leq E_{val}(g_m^-)+\sqrt{\frac{\log M}{K}}$

* 一旦我們找出 $m^*=arg\underset{1\leq m\leq M}{min}(E_m=E_{val}(\mathcal{A}_m(\mathbb{D})))$ ，$g_{m^*}$ 一定表現的會比 $g_{m^*}^-$ 還好。 ( learning curve 告訴我們 N 增加，$E_{out}$ 會下降 )

* 在實務上我們找出 $m^*$ 後會利用 $\mathbb{D}$ 來找出 $g_m^*$

<center>


</center>

我們可以把 train set 與 validation set 的error 曲線畫出來如下


從這圖可以看出，我們切出 validation set 後可以得到的 error 雖然未必可以接近 optimal ，但卻可以在這中間取得一個折衷。

但要注意的地方是，$E_{val}$ 在 K 高達某一個數量時，error 表現得會非常不好，原因在於，當 K 增加，表示 $\mathbb{D}_{train}$ 的數量會減少，因而得到的 $g_m^-$ 就會相對增加，而當 $\mathbb{D}_{train}$ 的數量少到一個數量時，得到的 error 就可能會比用全部的 data set 所得到的 error 還要高。


這是一個在選擇上面的兩難

我們希望最後選到的 $g$ 所得到的 $E_{out}$ 能夠與我們利用 $g^-$ 所得到的 $E_{out}$ 夠接近 ( 這樣的K值必須小一些 )

但我們也希望我們用 $g^-$ 得到的 $E_{val}$ 與 $E_{out}$ 可以夠接近 ( 這樣的K值又必須要大一點 )

所以在選擇上面還是需要權衡，一般來說，實務上會以 $\frac{N}{5}$ 作為K值

以下介紹兩個不同的 validation 方式 :

### Leave-One-Out Cross Validation (K=1)

這是一個極端的情況 K=1

$\Longrightarrow$ Validation Set : $\mathbb{D}_{val}^{(n)}=\left\{(\mathbb{X}_n,y_n)\right\}$，而其 $E_{val}^{(n)}=err(g_n^-(\mathbb{X}_n),y_n)$

$\Longrightarrow E_{loocv}(\mathbb{H},\mathcal{A})=\frac{1}{N}\sum\limits_{n=1}^{N}e_n=\frac{1}{N}\sum\limits_{n=1}^{N}err(g_n^-(\mathbb{X}_n),y_n)$

### 試証 : $E_{loocv}(\mathbb{H},\mathcal{A})\approx E_{out}(g)$

$\underset{\mathbb{D}}{\mathbb{E}}(E_{loocv}(\mathbb{H},\mathcal{A}))=\underset{\mathbb{D}}{\mathbb{E}}(\frac{1}{N}\sum\limits_{n=1}^{N}e_n)=\frac{1}{N}\sum\limits_{n=1}^{N}\underset{\mathbb{D}}{\mathbb{E}}(e_n)$

$=\frac{1}{N}\sum\limits_{n=1}^{N}\underset{\mathbb{D}_n}{\mathbb{E}}(\underset{(\mathbb{X}_n,y_n)}{\mathbb{E}}(err(g_n^-(\mathbb{X}_n),y_n)))=\frac{1}{N}\sum\limits_{n=1}^{N}\underset{\mathbb{D}_n}{\mathbb{E}}(E_{out}(g_n^-))$

$=\frac{1}{N}\sum\limits_{n=1}^{N}\overline{E_{out}}(N-1)=\overline{E_{out}}(N-1)$ ##得証

實際上，Leave-one-out cross validation 並不常使用，原因如下 :

* 對每一個 model 都要進行 N 次訓練，而且每一次都要 N-1 個 data 來進行訓練，當 N 非常大的時候，計算會變得相對複雜。
* 單一 validation 計算會相當不穩定

### V-fold Cross Validation

隨機將 $\mathbb{D}$ 等分成 V 個部分，每次對 V-1 個部分進行訓練，並留一個部分作為 validation set。

$E_{cv}(\mathbb{H},\mathcal{A})=\frac{1}{V}\sum\limits_{i=1}^{V}E_{val}^{(i)}(g_i^-)$

$m^*=arg\underset{1\leq m\leq M}{min}(E_m=E_{cv}(\mathbb{H}_m,\mathcal{A}_m))$

在實務上，V=10就可以有不錯的表現。

## 簡單總結

* Traning : 從眾多的 $\mathbb{H}$ 中選擇一個
* Validaiton : 從 Training 出來的 list 中選擇
* Testin : 作為最後評估
* 而通常 Validation 的結果會比 Testing 樂觀