# 2.7 Model Selection and Generalization


在一個 boolean function 裡面，所有的 input 和 output 都是 binary 的，所以 $d$ 個 binary values 就有 $2^d$ 種可能，也就是說，如果我們有 $d$ 個 input，我們的 training set 最多就只會有 $2^d$ 個 examples。
> 舉例來說：
>
> 上圖中我們有兩個 input $x_1$ 和 $x_2$，也就是我們的 $d=2$，所以我們最多就只會有 $2^2=4$ 個 examples，也就是
>
> $[x_1,\ x_2] = [0,\ 0],\ [0,\ 1],\ [1,\ 0],\ [1,\ 1]$

然後對這些 examples，每一個我們都可以將它 label 成 $0/1$，所以 $d$ 個 inputs 共會有 $2^{2^d}$ 種可能的 boolean functions。
> 從這個例子來看就是上面四個 examples，每個可標 $0/1$，因此有 $2^4=16$ 種可能性，也就是圖中的 $h_1,...,h_{16}$

:::success
每個不同的 training example 都會汰除一半的 hypothesis。
:::
> 舉例來說：
>
> 假設我們的兩個 input $x_1 = 0, \ x_2 = 1$（也就是對應到上圖框起來的部分）output 應該要是 $0$，但有一半的 hypothesis （$h_5, h_6, h_7, h_8, h_{13}, h_{14}, h_{15}, h_{16}$）的 output 是 $1$。
>
> 這樣一來，我們就能踢除了這一半（八個） hypothesis。

這樣的做法也是一種去理解 learning 的方式：

從所有可能的 hypotheses 開始，再一步一步去移除那些和 training data 不是 consistent 的。

在像上述 boolean function 的例子中，我們要去找出最終的 hypothesis，我們需要看過所有 $2^d$ 個 training examples。但是在通常的情況下，我們能夠得到的 ++training set 只是一個所有 possible instances 的 subset++，也就是說，只有很小部分比例的 cases 我們能夠得知正確的 output 應該是什麼，這樣的話，我們的 ++solution 就並非 unique++。

$\rightarrow$ 在我們看過 $N$ 個 example cases 以後，我們就剩下 $2^{{2^d}-N}$ 種可能的 functions。
> 因為指數的 $2^d$ 是 $d$ 個 input 的情況下所有的可能性，我們看過 $N$ 個所以減掉 $N$。
>
> 或是從另個角度去想，前面說過每檢查一個 training example，我們都能踢除一半的 hypothesis，那我們每看一個就 $\times \frac{1}{2}$，總共乘 $N$ 次，也就是在指數減掉 $N$ 了。

上述這樣的情況就是一個 <font color = "snake">ill-posed problem</font> 的例子，也就是我們的 data 不夠充分到足以讓我們找到一個 unique solution。

同樣的問題也會發生在像是 classification 或 regression 等其他的 learning applications 中。在我們看更多 trainging examples 的同時，我們就能知道更多關於 underlying function 的事情，我們能找到更多和 hypothesis class 並非 consistent 的 hypotheses，但我們仍然會剩下很多 consistent 的 hypotheses。

所以，正因為 learning 是 ill-posed，我們的 data 本身不夠充分到可以讓我們找到 solution，所以我們應該要根據我們現有的 data 去++做一些 extra assumptions 來得到一個 unique solution++。而這些我們製造出來使得 learning possible 的 ++assumptions 的 set++，就叫做 learning algorithm 的 <font color = "snake">inductive bias</font>。

$\rightarrow$ 其中一個引進 inductive bias 的方法就是去假設一個 hypothesis class $H$。
> 舉例來說：
> - 在 learning family car 的 class 時，我們有無限種方式可以去區分 positive examples 和 negative examples，那麼去假設我們的形狀是一個長方形就是一種 inductive bias，假設 margin 最大的長方形又是另一種 inductive bias。
> - 在 linear regression 的例子裡，去假設一個 linear function 是一個 inductive bias，去選擇 squared error 最小的那個 linear function 又是另一種 inductive bias。

但是我們也知道的是：

每一個 hypothesis class 都有一個特定的 capacity，並且只能 learn 特定的 functions。我們可以去擴展「能夠 learn 的 functions 的 class」使得它具有更大的 capacity、包含更多更複雜的 hypothesis。
> 舉例來說：
>
> 我們可以去聯集兩個長方形就能得到更大的 capacity，但是它的 hypotheses 也會更複雜；同樣地在 regression 裡面，如果我們去增加 polynomial 的 degree，capacity 和 complexity 就會增加。

$\rightarrow$ 現在的問題就變成：++如何去決定要停在哪？++

因此我們可以明白說 learning 在缺少 inductive bias 的情況下是不可能的，那問題就在於 ++要怎麼挑出正確的 bias++？這件事就叫做 <font color = "snake">model selection</font>，也就是++在可能的 $H$ 間做選擇++。

在回答這個問題時我們要記得的是 ML 的目的基本上不會是去重現我們的 data，而是要去對新的 cases 做 prediction。

也就是說，我們希望能夠對每個 training set 之外的 input instance 產生正確的 output，而這個正確的 output 並沒有在 training set 中。而我們說++一個藉由某個 training set 去 train 的 model 到底被 train 的多好，多能夠正確地預測新的 instances 的 output++，這件事叫做 <font color = "snake">generalization</font>。

為了要得到最好的 generalization，我們應該要讓我們的 hypothesis class $H$ 的 complexity 能夠 match data 背後的 function。如果 $H$ 比起實際背後的 function 要沒那麼複雜，那它就是 <font color = "snake">underfitting</font>；另一方面，如果 $H$ 過度複雜，除了背後的 function，連 noise 都考慮進去，那就是 <font color = "snake">overfitting</font>。
> 舉例來說：
>
> 假設我們的 data 是從一個三次多項式中去取樣得來，當我們試圖去把這些 data 用一條直線去 fit 時，如果我們去提升 complexity，training error 就會減少。
>
> 但如果我們的 $H$ 相對之下太過複雜，舉例來說，像是我們的 data 從一個長方形中去取樣，但是我們拿兩個長方形去 fit、我們的 data 從三次多項式中取樣，卻拿六次多項式去 fit，這樣就會是個 bad fit。
>
> $\rightarrow$ 在這種情況下，去++增加 training data 的數量雖然還是有幫助，但是幫助不大++。

所以假設給定一個 hypothesis class $H$，我們可以從中找出某個 $h \in H$ 使得 training error 最小，但是如果我們的 $H$ 挑得不好，無論我們怎麼去挑 $h$，都沒辦法有好的 generalization。

總結來說，在所有從 example data 去 train 的 learning algorithms 間有個 ==triple trade-off==：

1. hypothesis 的 complexity（hypothesis class 的 capacity）
2. training data 的量
3. 對新的 examples 的 generalization error

當 training data 的數量增加時， generalization error 就會下降；當 $H$ 的 complexity 增加時，generalization error 會先下降，再接著上升。對一個過於複雜的 $H$ 來說，我們可以藉由增加 training data 的數量來控制 generalization error，但是效果有限。

我們可以去衡量一個 hypothesis generalization 的能力（也就是她的 inductive bias 的品質。）

如果我們能夠取得 training set 之外的 data，我們就可以藉由把我們所擁有的 dataset 一分為二來模擬一個對 generalization ability 的測試，這兩個部分是：

1. training set
2. validation set

也就是說，假設我們有一個 set，裡面是很多 hypothesis classes $H_i$，對每個 $H_i$ 我們都去 fit 一個最好的 $h_i \in H_i$，然後假設我們的 training set 和 validation set 都夠大，那對 validation set 來說表現最正確的那個 hypothesis 就是最好的那個（有最好的 inductive bias），這樣過程就叫做 <font color = "snake">cross validation</font>。
> 舉例來說：
>
> 如果我們想要在做 polynomial regression 時找到最適合的 order，給定一些不同 order 的候選 polynomials，我們將它們根據 order 區分成對應的 hypothesis class $H_i$（例如二次多項式$\Rightarrow$ $H_2$）
>
> 對每個 order 我們都用 training set 去找適合的係數，再用 validation set 去計算他們各自的 errors，再取 validation error 最小的那個去作為最佳的 polynomial。

必須注意的是，如果我們需要去回報 error 的值，讓我們對現在找到的這個最佳的 model 預期會有多少 error 有個概念，我們不能用 validation error。

當我們已經用 validation set 去選擇最適合的 model 了以後，validation set 就變成了 training set 的一部分，因此我們需要第三個 set，也就是 <font color = "snake">test set</font>，或者也叫做 <font color = "snake">publication set</font>，這個 set 包含的是++不是用來做 training 或 validation++ 的 examples。
> 如果用生活中的例子來打個比方，假設我們現在在修課，上課時老師舉的例題是 training set，考試的題目是 validation set，然後最終我們在研究所時解決的問題就是 test set。
>
> 我們也不能不斷地重複去使用同個 training / validation 的切割方式，因為當我們用過一次以後，validation set 就會成為 training set 的一部分，這就好像是如果老師每一年都用同樣的題目來當考題，聰明的學生就能發現說不用上課，只要靠著記下相同題目的答案就能拿到好成績。

最後，我們要記得的是我們所使用的 training data 不過是個 random 的 sample，也就是說，如果我們再多蒐集一次 data，我們就會得到一個稍微不一樣的 dataset，fit 出來的 $h$ 也就會有些微的不同，最後也會得到不太一樣的 validation error。

或者，即便我們有個固定的 set，根據切割出 training / validation / test set 的不同，我們一樣也會得到不同的 error。

這些些微的差異讓我們能夠去估計說到底多大的誤差要被視作 significant，而不單純只是機率問題。

舉例來說，在從兩個 hypothesis classes $H_i$ 和 $H_j$ 之間去做選擇時，我們會把他們用在好幾組 training 和 validation sets 上，然後去檢查 $h_i$ 和 $h_j$ 之間平均 error 的差異是否有比很多個 $h_i$ 之間的 error 差異來得大。

:::info
第十九章會講到如何用 limited data 去設計 ML 實驗，來回答像是「哪一個是最好的 hypothesis class」這種問題，以及分析得到的結果，讓我們能下出最小程度地被機率影響的結論。
:::