# 4.8 Model Selection Procedures
# 背景
講這節之前我們先來回顧前一節，有關筆記「[4.7 Tuning Model Complexity: Bias / Variance Dilemma](https://hackmd.io/@pipibear/Sy7Fs2VOA)」的內容。
前一節的一開始，我們在講要 minimize estimate $g(x)$ 和 real value $r$ 之間的 error 時，一開始是針對單一個 sample 去討論，看依據這個 sample 建立出來的 $g()$ 在 input 為某個特定的 $x$ 時，expected square error 會是什麼樣的情形，也就是：
\begin{equation}
E[(r - g(x))^2|x]
\end{equation}
接著我們發現這個值可以拆成兩部分，一部分是不管我們的 estimator $g()$ 怎麼選，都沒辦法去除的 noise，還有另一部分是會因為 $g()$ 的不同而改變的 squared error：
\begin{equation}
(E[r|x] - g(x))^2
\end{equation}
也就是平均來說當 input 為 $x$ 時我們預期的 output （$E[r|x]$），和我們的 estimate $g(x)$ 之間的差距平方。
從這個式子我們會發現，如果我們的 estimator $g()$ 不同，那 predict 的 $g(x)$ 就會不一樣，進而影響到整個 error 的值。並且，這個 estimator 怎麼來的？是根據我們的 sample 去估計得來，所以我們就發現當 error depends on sample 時，只取一個 sample 好像不太恰當。
因此我們就想，假如我們取 $M$ 個 samples，再取它們各自產生的 squared error 的平均作為 expected error，這樣好像更好，也就是：
\begin{equation}
E_{\chi}[(E[r|x] - g(x))^2|x]
\end{equation}
我們接著發現這個東西可以拆成兩部分，一部分是 bias，另一部分是 variance。因此，為了要 minimize error，我們就去討論什麼樣的情形 mean 會比較小、什麼樣的情形 variance 會比較小，也介紹了 bias / variance dilemma 來說明他們之間的 trade-off，以及 complexity 對他們的影響，也就是本節要延續的主題。
---
# cross validation
前一節有講到，high complexity 會使得 bias 小，但 variance 大，如果 low complexity 則相反。
那麼，我們要如何在這之間取得一個平衡，決定一個 model 的 complexity 呢？
在實務上，我們會用一個方法叫做 <font color = "snake">cross-validation</font>，也就是 given 一個 dataset，我們將它分成兩部分：
- training set
- validation set
> cross-validation 其實在「[2.7 Model Selection and Generalization](https://hackmd.io/@pipibear/S14QwU4VC)」也有講過。
我們用 training set 來 train 具有不同 complexities 的 candidate models，再用 validation set 來測試它們的 error。
延續我們前一節的內容：
:::warning
當 model complexity 增加，training error 會不斷下降；但是對於 validation set 的 error，當 complexity 增加到某個程度以後，就不會再下降了，甚至如果 data 裡有 noise 的話可能還會上升。
:::
> 因為 model complexity 的增加，意味著我們更貼近 training set 的 data，所以當我們再去對 validation set 做測試時，這個 high complexity 的 model 就不夠 generalize，反倒可能使 error 上升。
>> 例如 learn 到 training set 的 noise 的時候。
> 前一小節的圖裡面我們只用了 $5$ 組 samples，對每種 order 產生對應的五個 models；這個圖則是將 model 的數量提升到 $100$ 個。
>
> 我們可以看到當 complexity 為 order$=3$ 時具有最小的 error，再繼續增加 order 就會因為 variance 的增加而使 error 反倒上升。
- 不過在現實生活中，我們無法知道 true underlying function $f()$，所以我們也沒辦法像上圖一樣去計算 bias（因此也就不能計算 error。）
下圖是我們把 noise 的 variance 也考量進去以後，對 validation error 的 estimate。
:::warning
把 noise 的 variance 也考量進來就會使得：
++即便我們有一個「正確的」model 使得沒有 bias++（能 fit 每個點），且我們++有夠多的 data 使得 variance negligible++，++仍然可能存在非零的 validation error++。
:::
> Recall：因為 bias $= \frac{1}{N}\sum_{t=1}^N[\bar{g}(x^t) - f(x^t)]^2$，所以即使沒有 bias，也就是 $\bar{g}(x^t) - f(x^t)=0, \ \forall t$，這裡我們也沒有考慮到 noise。
> 延續前一節例子的設定，我們總共有 $100$ 個 data points，但當時我們是取五個 samples，每個 sample 各 $20$ 個 data points，並且針對每個 sample 產生一個 estimator；這裡我們是產生各含 $50$ 個 data points 的 training / validation set。
>
> （a）：$+$ 字記號是 training set 中的 $50$ 個點，我們畫出八個 functions，分別是 degree $1$ 到 $8$ 來 fit 這些點。
>
> （b）：實線對應到每個 degree 的 function 和（a）中 training set 的那些點之間的 error；虛線則是每個 degree 的 function 和剩下 validation set 中的點之間的 error。
>
> - Note：（b）裡的 validation error 並不像前一張圖 $4.6$ 一樣 error 呈 $V$ 字形（order 大時 error 仍較平緩），因為這裡我們有更多的 training data，且我們前一節講過，training data 越多，就越可以限制 variance 的增加。
# regularization
## augmented error function
另一種常用來決定 model 的 optimal complexity 的方式叫做 <font color = "snake">regularization</font>。
在這種方式裡，我們會定義一個 <font color = "snake">augmented error function</font> ==$E'$==：
:::info
\begin{equation}
E' = \text{error on data} + \lambda \times \text{model complexity}
\end{equation}
:::
$E'$ 除了像一般的 error function 一樣計算 error on data，另外又多出一部分 $\lambda \times \text{model complexity}$，用來++懲罰因為比較複雜，所以 variance 比較高的 models++。
> 目的在於避免 overfitting，減少選擇會去 fit taining data 中的 noise 的 complex models。
其中 $\lambda$ 代表 penalty 的 weight。如果 $\lambda$ 很大的話，只有很簡單的 models 才有可能具有小的 $E'$，因此當我們要選擇 $\min E'$ 時，過於複雜的 models 就不可能被選到，因此也會有 bias 比較高的風顯。
> 也就是說 $\lambda$ 用來控制 penalty 的強度，越大代表越鼓勵去取簡單的 models。
$\rightarrow$ 我們用 cross-validation 來 optimize $\lambda$ 的值。
另一種解讀上面 augmented error function 式子的方式，是++將 $E'$ 視為 error on new test data++。
## optimism
前面的那項 error on data 視為 training error，後面的 $\lambda \times \text{model complexity}$ 視為 <font color = "snake">optimism</font>。解釋如下圖：
有一些方法，像是 Akaike's information criterion (AIC)、Bayesian information criterion (BIC) 就是在想辦法估計這個 optimism，讓我們可以在將它加上 training error 以後去估計 test error，而不用任何的 validation。
### 特性
optimism 的大小：
- <font color = "green">$\propto d$</font>，$d=$ input 的數量
> （詳細說明比較長，放在下方）
- <font color = "green">$\propto \frac{1}{N}$</font>，$N=$ training set size
> 因為當 training set 有越多的 data points，每個點對整個 model 的影響就越小。這樣的情形減少了 overfit 的可能性，因為我們的 model 變成要去想辦法 fit 更大（也意味著更 generalize）的 dataset，而不是去 fit 一個小小的 dataset 中的 noise。
>
> $\rightarrow$ data 越多，就對 model 造成更多的限制，對parameters 的 estimate 也就越 stable（因為越不容易因為少數幾個點而改變），因此 variance 也較低。
- 隨著 <font color = "green">$\sigma^2$</font> 變大而變大（但關係不一定 linear），$\sigma^2=$ noise 的 variance
> 如果 noise 的 variance 越大，代表 data points 離背後真正的 function 越分散。
>
> 因此，如果一個 model complexity 越高，它越容易去 fit 這些 noise，在 noise variance 越大的情況下，我們的 model 就離真正的 function 越遠，雖然因為 complexity 高所以 training error 低，但當應用到新的 data 時，這個 model 的 performance 就會因為在 training set 中的 noise 不在新的 data 裡而變差。
### linear model
課本在這裡提到：
:::info
如果 model 並非 linear，那麼我們的 $d$ 就要用「有效的」parameter 數量來取代。
:::
Q：什麼意思？如果 parameter 有 $d$ 個，為什麼還能說這個 model 是 linear？（linear 不是應該只有一個斜率、一個截距，兩個 parameters 嗎？）
A：在 machine learning 或 statistics 裡，我們說 <font color = "snake">linear model</font>，指的是 input features 和 output 之間的關係是 ++linear in the parameters++，而不一定是 linear in input features。
兩者之間差在哪，什麼意思？
- <font color = "snake">linear in the parameters</font>：意思是 dependent variable (output) 可以用 coefficients (parameters) 的線性組合表示。
> 也就是每個 parameter 會乘上某個 input features 的 function，再把它們加總。
>> 看完下方的例子會比較清楚。
- <font color = "snake">linear in input features</font>：意思是 input features 和 output 之間的關係是一條直線（如果是在 higher dimension 就是 hyperplane），input features 沒有像 linear in parameters 一樣，經過 function 的 transoformation。
例子：
1. 兩種 linear 都滿足
\begin{equation}
y = \beta_0 + \beta_1x
\end{equation}
> - linear in the parameters：parameters 為 $\beta_0, \beta_1$，所以 $y$ 是它們的線性組合。
> - linear in input features：input feature $x$ 沒有被 transformed，且 $x,y$ 之間的關係是 linear 的。
2. 滿足 linear in the parameters 但不滿足 linear in input features
\begin{equation}
y = \beta_0 + \beta_1x + \beta_2x^2 + \beta_3x^3
\end{equation}
> - linear in the parameters：parameters 為 $\beta_0, \beta_1,\beta_2,\beta_3$，$y$ 是它們的線性組合。
> - linear in input features：input feature $x$ 有被 transformed（變成 $x^2,x^3$），且 $x,y$ 之間的關係不是一條直線，而是一條多項式曲線。
所以，linear model （滿足 linear in the parameters）用數學式表示，即為滿足：
:::info
\begin{equation}
y = \beta_0 + \sum_{i=1}^d \beta_i f_i(x)
\end{equation}
:::
$\rightarrow$ 只要 model 為 linear in parameters $\beta_i$，那它就是一個 linear model，不管 $f_i(x)$ 是否為 linear。
說了這麼多，那什麼樣的 model 是 nonlinear 呢？
舉個例子，logistic regression 就非 linear，見下圖：
> 在 logistic model 裡，我們用了 logistic (sigmoid) function $\sigma(z) = \frac{1}{1+e^{-z}}$，雖然在代入 $z$ 時 $b_0 + b_1x$ 為 linear combination，但 parameters $b_0,b_1$ 和 output $p$ 之間的關係並非 linear（$p$ 不是 $b_0,b_1$ 的線性組合。）
# 其餘決定 model 的方式
最後課本簡單介紹三種在 fit 和 complexity 的 trade-off 之間選擇 model 的方式，像上面講的 regularization 一樣，它們也會對 model 的 complexity 產生某種形式的 penalty，下面我們再分別好好說明。
## SRM: Structural Risk Minimization
<font color = "snake">Structural Risk Minimization (SRM)</font> 將 models 根據它們的 complexities 分成 nested subsets，再根據 order 選擇 simplest 且 empirical error 最小的 model。
詳細說明和例子如下圖：
> 圖中提到常用的衡量 complexity 的方式為 VC dimension，相關說明可參考筆記「[2.2 Vapnik-Chervonenkis Dimension](https://hackmd.io/@pipibear/Sy1E6rEV0)」。
## MDL: Minimum description length
先定義一個名詞 <font color = "snake">Kolmogorov complexity</font>：
:::info
一個 dataset 的 Kolmogorov complexity 定義為 ++the shortest description of the data++。
:::
什麼意思呢？
舉例來說：
如果我們的 data is simple，例如是一串零，那我們可以用 $0$ 和 sequence 的長度表示；但是如果我們的 data is completely random，那我們就沒辦法找到比 data 本身更短的 description 來描述它。
如果我們有一個 model 能夠 good fit data，那麼與其直接儲存 data，我們能 send / store model description。
從所有描述 data 的 models 裡面，我們挑出一個最 simple 的 model，有著最短的 description。
和之前的其他方式一樣，我們仍舊會面臨到 model simple 的程度和 model 能好好描述 data 的程度，兩者之間的 trade-off。
## Bayesian Model Selection
最後一種就像我們前幾節在講的 Bayes' 相關的概念一樣，當我們對適合的 approximating functions 的 class 有一些 prior information 時，我們就可以用 <font color = "snake">Bayesian Model Selection</font>。
> 翻成中文有點拗口，課本原話為：
> Bayesian Model Selection is used when we have some ++prior knowledge about the appropriate class of approximating functions++.
像我們之前定義 prior probability 一樣，我們這樣的 prior knowledge 也由一個 prior distribution over models ==$p(\text{model})$== 所定義。
如果給定 data，然後針對一個 model，我們也可以利用 Bayes' rule 去計算 posterior probability ==$p(\text{model}|\text{data})$==：
\begin{equation}
p(\text{model}|\text{data}) = \frac{p(\text{data}|\text{model})p(\text{model})}{p(\text{data})}
\end{equation}
依據這個 posterior probability，我們可以在選擇 model 時直接選 posterior probability 最高的 model，或是用 posterior probability 當 weight，取所有 models 的平均。
接著，如果我們對這個式子取 $\log$ 會得到：
這樣的結果其實和前面提到的 augmented error function 有相同的意義：
為什麼這樣說呢？舉個例子比較清楚：
那麼在挑 model parameters $\vec{w}$ 時，我們就選能夠使 error 最小的那個，如果我們的 error function 定義如下：
那麼我們會發現，除了前面那項 sum of squared error 等同於 $E'$ 中的 error on data 之外，後面的各個 weight 平方和其實作用也等同去代表 complexity。
詳細解釋如下：
> 在這個圖中有提到，如果我們要去 fit 一組 data，隨著 function 的 degree 增加，function 的係數通常也會變大。
>
> 課本對這部分幾乎沒有任何說明，但我很好奇到底這個結論從哪來的，所以查了一些資料，寫一寫發現篇幅太大了，所以有興趣的話可參考這篇筆記：「[補充：large coefficients for high-order polynomials](https://hackmd.io/@pipibear/BkyBvBjOR)」。
>> 不過這篇筆記受限於我的能力，沒有寫得很詳細，也不算是有一個結論，所以就參考一下就好。
> [!Note]課本將這部分的詳細內容留到第十六章再說明。
---
最後，這節提到的不管是 Bayesian approach, regularization, SRM, MDL，都是建立在 Occam's razor 的概念下，也就是越簡單的通常越好。
> 忘記之前在哪一小節有講過 Occam's razor，但這也沒有很重要，有興趣就看看 wiki 介紹就好。
並且，雖然只有 Bayesian approach explicitly 去定義一個 prior probablity，但是其他方式也都用不同的做法來去對 high complexity 的 models 施加額外的 penalty，這也可以被視為 implicitly 去選擇 使較為 simple 的 model 機率會較高的 prior。
唯一跟其他 methods 不同的只有 cross-validation。
$\rightarrow$ cross-validation 沒有對 model 的 parameters 做出任何 prior assumption。
因此：
:::warning
如果我們有夠大的 validation dataset，那麼 cross-validation 就是最好的 approach；但是當 sample 比較小的時候，其他的方法就變得比較有用。
:::
這一小節和這章就結束在這裡！
---
# 參考資料
- [Structural Risk Minimization](https://www.svms.org/srm/)
Sign in with Wallet
Connect another wallet