Overfitting
对于一个model，如果Ein(h)小，而Eout(h)大时，说明该h的generalization差。
一个算法在选择h的过程中，如果出现Ein(h) lower, Eout(h) larger，则说明产生了overfitting。
产生overfitting的原因有：
1.noise
2.limit data size
3.
太大（model的复杂度）
Noise
stochastic noise vs deterministic noise.
1. stochastic noise：
，满足高斯分布，其中
，f(x)是target function。
2. deterministic noise：当算法选出最好的模型
时，|h*(x)-f(x)|就是deterministic noise。
这两种noise都可能会产生overfitting
e.g
stochastic noise
现在有个target function f(x)是一个10次的多项式，由它产生一些data，再加上一些随机噪声，噪声满足高斯分布。
图中黑色的点就是带有noise的data。现在有两个H，H1只含有2次多项式，H2最多可以到达10次。现在利用算法在这两个H中分别选出最好的h*，使得Ein(h*)分别达到最小，叫做
（绿色）和
（红色）。
从上图看出，虽然10次的h可以做到的training error，即Ein，比2次的h要好，但是bad generalization，Eout要比2次的h大很多。
结论，当h从2次变到10次的时候，产生了overfitting。
deterministic noise
现在的target function 是一个50次的f(x)，由这个f(x)产生一些data，但是不要加上随机噪声，如图
现在同样有两个H，和上个例子一样是2次和10次的，然后算法找到的两个h如图
发现同样2次的h*要比10次的h*在Eout上表现好很多，可是这次的data并木有随机噪声，那么是什么产生了overfitting呢？
是target function的complexity，因为target function是个50次的多项式，是非常复杂的，这个复杂度可以看成是noise，也就是deterministic noise。之所以称为deterministic确定性，是因为这个噪声是来自target function本身的，可以计算而不是随机产生的。其实计算机产生的随机数称做伪随机数pseudo-random number的原因就是并不是真的随机数，而是用一个非常高次的，你没有办法看出规律的函数产生的。
蓝色是target function，红色是最好的h，图中阴影部分就是deterministic noise。如果target function次数越高，函数的抖动就越大，那么找到的h和target function的阴影面积就越大，噪声就越多，就越容易overfitting。
另外，关于噪声有一个讨论
左图，确定了Qf即target function的次数的情况。
是随机噪声的强度，为y-axis，N数据量，为x-axis。当数据量小的时候，为图左半边，为红色，代表overfitting很严重，如果N很大，并且
比较小，在右下角，为蓝色，表示overfitting很小，但是如果
增大，overfitting还是会变严重。
右图，确定了噪声强度
的情况。Qf表示target function的次数，为y-axis，N数据量，为x-axis。当Qf增大时，deterministic noise，为图的左半边，为红色，表示overfitting严重，但是N增大则会缓解overfitting，颜色往蓝色变。值得注意的是图左下角也为红色，意思是当targetfunction的次数并不高，而算法选择的h的
，即h的复杂度高，就是本文一开始讨论的第三种情况，这种情况下也会造成overfitting。
解决办法
1. make model simple
2. data cleaning and pruning(avoid noise)
3. data hinting(increase data size N)
4. regularization (l1, l2 penalty)
5. validation
