Overfit 詮釋和新的解法

by allenlu2007

不論在 machine learning or deep learning 中最重要的問題就是 over-fitting.

當 feature/weight/model/parameter space >> data space 就會造成 overfit.  

 

之前提到 overfit 的解法是:

1. Reduce features to reduce the parameter space.

2. Early stop (training) or cut/prune tree depth (decision tree), etc.

3. Add regularization (L2 or L1 penalty).

 

1 and 2 都很直覺。就是減少 model complexity.  但容易造成 bias error. 

3 是最常用的方式。可以用 regularization parameter 來 trade-off between variance error and bias error.

 

林軒田用 model complexity 和 VC dimension 來說明

overfit (model complexity >> data complexity) 會讓 generalization/learning break.

這說明 overfit 會造成 learning (generalization fail),但缺乏具體或 insightful 解釋 why overfit cause problem.

 

* 為何 regularization 可以解決 overfit 的問題?

1. SNR 觀點:  yn (w’ xn + b) > = 1  where yn = +1 or -1.  

因此 |wn| 愈小,代表 |xn| cos(theta) 愈大。xn 基本上是定值,所以 cos(theta) 變大,也就是 xn 在 decision boundary 的法向量投影愈大,也就是 margin 最大。在有 noise 的時候,仍可以 reliably detect/classify。或許會疑惑 overfit 和  noise 有什麼關係。可以參考林軒田教授的 ML foundation lecture.

Model complexity (due to overfit) 可以視為 deterministic noise.  因此 regularization by minimize |w| 所造出的 margin 可以對抗 overfit 的問題。

 

2. Model complexity 觀點: 同樣參考林軒田的 lectures.  Regularization 的效果是等效 VC (Vanpnik .) dimension 變小。根據 learning theory (請參林軒田 lecture), regularization 雖然不會讓 in-sample/training error 變小,但會讓 out-sample/test error 變小,這非常重要。也是 learning theory 最 critical 的部份。

 

其他的 regularization 的用途:

* Prior knowledge:  ||x||  is small.  (Baysian view)

* Small signal optimal design:  Ax ~ b holds when x is small

* Robust design:  || (A + ΔA) x – b || = || Ax -b + ΔA.x ||.   Robust design when x is small

 

 

新的想法:

最好的方法是 Big data, 儘量用更多的 data 來解決。

如果 data 就是不夠怎麼辦?  製造更多的 data!!!!

如何製造更多的 data?  就是用 prior knowledge to create. 

 

例如做 digit recognition or image recognition, 可以把 input image 做 shift, rotation, … 來 train model.

例如 translation invariant or rotation invariant 等 prior knowledge, 傳統的想法是 model 做成 

translation invariant or rotation invariant!!  這是把 prior knowledge embedded 到 model 中,

新的想法則是 create 更多的 input data based on translation/rotation invariant, 來 train model (e.g. neural net). 

但不硬 create model 本身是 translation or rotation invariant. 

 

Hinton 的說明:如何解釋 overfitting

Machine learning or deep learning model 本身是要 fit general 的 structure 規律。

由於 training data 是 finite sample, 本身也會有 (spurious) structure due to finite samples.

 

當 parameter space 遠大於 data, 在 training 過程中,model 就會不止 fit general structure, 同時

fit 到 spurious structure (error).  甚至可能完全 fit 到 spurious structure 而非 general structure.  (見樹不見林).  

 

Hinton 也給了一個解釋為什麼 neural network training 時,early stop (from small weight) 或是 regularization 可以避免 overfitting.  主要是 early stop 或是 regularization 都是儘量 drive small weights.  當 small weights 時 neural network 基本上是接近 linear network (assuming arctan with zero bias).  Linear network 的 dimension 完全由 input/output 決定。和 hidden unit/layer 無關。當 weight 增加時,nonlinearity starts to kick-in.  系統的複雜度增加,極致時就會產生 over fitting.

 

解法是:

More data!! 正解,消除 spurious structure (error).  

如果沒有足夠 data:

* Prior knowledge:  create synthesized data based on prior knowledge!

* Enhance subset of data:  bagging or random forest or boost (?)

* Add noise to the model

* Bayesian

* Combine many models

 

Hinton 另一個解釋為什麼一般的 training 會有 overfit 問題是因為心中有(唯一)最佳解。就像在 SVM 或是 neural network 的 forward/backward prop 都是在 learning for THE optimal solution.

Bayesian 則是從 prior 和 posterior 都否定唯一解。而認為是 probability distribution!!

在 Bayesian 下沒有所謂 overfit 問題。因為 overfit 的 high variance 情況是由 pdf 決定,而非一個固定的 function. 

 

Advertisements