上節課我們主要介紹了非線性分類模型，通過非線性變換，将非線性模型映射到另一個空間，轉換為線性模型，再來進行分類，分析了非線性變換可能會使計算複雜度增加。本節課介紹這種模型複雜度增加帶來機器學習中一個很重要的問題：過拟合（overfitting）。
首先，我們通過一個例子來介紹什麼bad generalization。假設平面上有5個點，目标函數f(x)是2階多項式，如果hypothesis是二階多項式加上一些小的noise的話，那麼這5個點很靠近這個hypothesis，E_{in}很小。如果hypothesis是4階多項式，那麼這5點會完全落在hypothesis上，E_{in}=0。雖然4階hypothesis的E_{in}比2階hypothesis的要好很多，但是它的E_{out}很大。因為根據VC Bound理論，階數越大，即VC Dimension越大，就會讓模型複雜度更高，E_{out}更大。我們把這種EinE_{in}很小，E_{out}很大的情況稱之為bad generation，即泛化能力差。
我們回過頭來看一下VC曲線：
hypothesis的階數越高，表示VC Dimension越大。随着VC Dimension增大，E_{in}是一直減小的，而E_{out}先減小後增大。在d^*位置，E_{out}取得最小值。在d_{VC}^*右側，随着VC Dimension越來越大，E_{in}越來越小，接近于0，E_{out}越來越大。即當VC Dimension很大的時候，這種對訓練樣本拟合過分好的情況稱之為過拟合（overfitting）。另一方面，在d_{VC}^*左側，随着VC Dimension越來越小，E_{in}和E_{out}都越來越大，這種情況稱之為欠拟合（underfitting），即模型對訓練樣本的拟合度太差，VC Dimension太小了。
bad generation和overfitting的關系可以了解為：overfitting是VC Dimension過大的一個過程，bad generation是overfitting的結果。
一個好的fit，E_{in}和E_{out}都比較小，盡管E_{in}沒有足夠接近零；而對overfitting來說，E_{in}\approx0，但是E_{out}很大。那麼，overfitting的原因有哪些呢？
我們舉個開車的例子，把發生車禍比作成overfitting，那麼造成車禍的原因包括：
車速太快（VC Dimension太大）；
道路崎岖（noise）；
對路況的了解程度（訓練樣本數量N不夠）；
也就是說，VC Dimension、noise、N這三個因素是影響過拟合現象的關鍵。
為了盡可能詳細地解釋overfitting，我們進行這樣一個實驗，試驗中的資料集不是很大。首先，在二維平面上，一個模型的分布由目标函數f(x)（x的10階多項式）加上一些noise構成，下圖中，離散的圓圈是資料集，目标函數是藍色的曲線。資料沒有完全落在曲線上，是因為加入了noise。
然後，同樣在二維平面上，另一個模型的分布由目标函數f(x)（x的50階多項式）構成，沒有加入noise。下圖中，離散的圓圈是資料集，目标函數是藍色的曲線。可以看出由于沒有noise，資料集完全落在曲線上。
現在，有兩個學習模型，一個是2階多項式，另一個是10階多項式，分别對上面兩個問題進行模組化。首先，對于第一個目标函數是10階多項式包含noise的問題，這兩個學習模型的效果如下圖所示：
由上圖可知，2階多項式的學習模型E_{in}=0.050，E_{out}=0.127；10階多項式的學習模型E_{in}=0.034，E_{out}=9.00。雖然10階模型的E_{in}比2階的小，但是其E_{out}要比2階的大得多，而2階的E_{in}和E_{out}相差不大，很明顯用10階的模型發生了過拟合。
然後，對于第二個目标函數是50階多項式沒有noise的問題，這兩個學習模型的效果如下圖所示：
由上圖可知，2階多項式的學習模型E_{in}=0.029，E_{out}=0.120；10階多項式的學習模型E_{in}=0.00001，E_{out}=7680。雖然10階模型的E_{in}比2階的小，但是其E_{out}要比2階的大得多的多，而2階的E_{in}和E_{out}相差不大，很明顯用10階的模型仍然發生了明顯的過拟合。
上面兩個問題中，10階模型都發生了過拟合，反而2階的模型卻表現得相對不錯。這好像違背了我們的第一感覺，比如對于目标函數是10階多項式，加上noise的模型，按道理來說應該是10階的模型更能接近于目标函數，因為它們階數相同。但是，事實卻是2階模型泛化能力更強。這種現象産生的原因，從哲學上來說，就是“以退為進”。有時候，簡單的學習模型反而能表現的更好。
下面從learning curve來分析一下具體的原因，learning curve描述的是E_{in}和E_{out}随着資料量N的變化趨勢。下圖中左邊是2階學習模型的learning curve，右邊是10階學習模型的learning curve。
我們的第9次課的筆記 NTU林軒田機器學習基石課程學習筆記9 – Linear Regression已經介紹過了learning curve。在learning curve中，橫軸是樣本數量N，縱軸是Error。E_{in}和E_{out}可表示為： E_{in}=noise level\ast (1-\frac{d+1}N) E_{out}=noise level\ast (1+\frac{d+1}N)
其中d為模型階次，左圖中d=2，右圖中d=10。
本節的實驗問題中，資料量N不大，即對應于上圖中的灰色區域。左圖的灰色區域中，因為d=2，E_{in}和E_{out}相對來說比較接近；右圖中的灰色區域中，d=10，根據E_{in}和E_{out}的表達式，E_{in}很小，而E_{out}很大。這就解釋了之前2階多項式模型的E_{in}更接近E_{out}，泛化能力更好。
值得一提的是，如果資料量N很大的時候，上面兩圖中E_{in}和E_{out}都比較接近，但是對于高階模型，z域中的特征很多的時候，需要的樣本數量N很大，且容易發生次元災難。關于次元災難的詳細生動解釋，請參考我另一篇博文：
機器學習中的次元災難
另一個例子中，目标函數是50階多項式，且沒有加入noise。這種情況下，我們發現仍然是2階的模型拟合的效果更好一些，明明沒有noise，為什麼是這樣的結果呢？
實際上，我們忽略了一個問題：這種情況真的沒有noise嗎？其實，當模型很複雜的時候，即50階多項式的目标函數，無論是2階模型還是10階模型，都不能學習的很好，這種複雜度本身就會引入一種‘noise’。是以，這種高階無noise的問題，也可以類似于10階多項式的目标函數加上noise的情況，隻是二者的noise有些許不同，下面一部分将會詳細解釋。
下面我們介紹一個更細節的實驗來說明 什麼時候小心overfit會發生。假設我們産生的資料分布由兩部分組成：第一部分是目标函數f(x)，Q_f階多項式；第二部分是噪聲ϵ，服從Gaussian分布。接下來我們分析的是noise強度不同對overfitting有什麼樣的影響。總共的資料量是N。
那麼下面我們分析不同的(N,\sigma^2)和(N,Q_f)對overfit的影響。overfit可以量化為E_{out}-E_{in}。結果如下：
上圖中，紅色越深，代表overfit程度越高，藍色越深，代表overfit程度越低。先看左邊的圖，左圖中階數Q_f固定為20，橫坐标代表樣本數量N，縱坐标代表噪聲水準\sigma^2。紅色區域集中在N很小或者\sigma^2很大的時候，也就是說N越大，\sigma^2越小，越不容易發生overfit。右邊圖中\sigma^2=0.1，橫坐标代表樣本數量N，縱坐标代表目标函數階數Q_f。紅色區域集中在N很小或者Q_f很大的時候，也就是說N越大，Q_f越小，越不容易發生overfit。上面兩圖基本相似。
從上面的分析，我們發現\sigma^2對overfit是有很大的影響的，我們把這種noise稱之為stochastic noise。同樣地，Q_f即模型複雜度也對overfit有很大影響，而且二者影響是相似的，是以我們把這種稱之為deterministic noise。之是以把它稱為noise，是因為模型高複雜度帶來的影響。
總結一下，有四個因素會導緻發生overfitting：
data size N\downarrow
stochastic noise σ2↑
deterministic noise Q_f\uparrow
excessive power ↑
我們剛才解釋了如果目标函數f(x)的複雜度很高的時候，那麼跟有noise也沒有什麼兩樣。因為目标函數很複雜，那麼再好的hypothesis都會跟它有一些差距，我們把這種差距稱之為deterministic noise。deterministic noise與stochastic noise不同，但是效果一樣。其實deterministic noise類似于一個僞随機數發生器，它不會産生真正的随機數，而隻産生僞随機數。它的值與hypothesis有關，且固定點x的deterministic noise值是固定的。
現在我們知道了什麼是overfitting，和overfitting産生的原因，那麼如何避免overfitting呢？避免overfitting的方法主要包括：
start from simple model
data cleaning/pruning
data hinting
regularization
validataion
這幾種方法類比于之前舉的開車的例子，對應如下：
regularization和validation我們之後的課程再介紹，本節課主要介紹簡單的data cleaning/pruning和data hinting兩種方法。
data cleaning/pruning就是對訓練資料集裡label明顯錯誤的樣本進行修正（data cleaning），或者對錯誤的樣本看成是noise，進行剔除（data pruning）。data cleaning/pruning關鍵在于如何準确尋找label錯誤的點或者是noise的點，而且如果這些點相比訓練樣本N很小的話，這種處理效果不太明顯。
data hinting是針對N不夠大的情況，如果沒有辦法獲得更多的訓練集，那麼data hinting就可以對已知的樣本進行簡單的處理、變換，進而獲得更多的樣本。舉個例子，數字分類問題，可以對已知的數字圖檔進行輕微的平移或者旋轉，進而讓N豐富起來，達到擴大訓練集的目的。這種額外獲得的例子稱之為virtual examples。但是要注意一點的就是，新擷取的virtual examples可能不再是iid某個distribution。是以新建構的virtual examples要盡量合理，且是獨立同分布的。
本節課主要介紹了overfitting的概念，即當E_{in}很小，E_{out}很大的時候，會出現overfitting。詳細介紹了overfitting發生的四個常見原因data size N、stochastic noise、deterministic noise和excessive power。解決overfitting的方法有很多，本節課主要介紹了data cleaning/pruning和data hinting兩種簡單的方法，之後的課程将會詳細介紹regularization和validataion兩種更重要的方法。
注明：
文章中所有的圖檔均來自中國台灣大學林軒田《機器學習基石》課程