过拟合和正则化
Bad generalization指的是一个状态，在这个VC维下，Error_in小，Error_out大。
Overfitting指的是一个过程，在VC维变大过程中，Error_in变小，Error_out变大。
Overfitting（过拟合）指的是当VC维很大时，学到的MODEL不能很好的举一反三。在训练数据上取得很好的效果，但是对于训练数据以外的其他数据（如测试数据），预测结果与实际值差别很大。
导致Overfitting的因素有：
（1）use excessive d_vc。使用的Hypothesis的model complexity过大
（2）noise。训练数据的noise过大
（3）limited data size N。训练数据量太小
如何解决Overfitting：
（1）start from simple model。优先选择简单的model进行训练
（2）data cleaning/pruning。使得训练数据更为精确，减少noise的影响
（3）data hinting。从现有训练数据或对问题的了解产生新的训练数据
（4）regularization
（5）validation
data cleaning/pruning
判别标准：例如classifier的错误超过一定的阈值，或者数据点离其他label的数据点集距离过近等。通过一定的判别标准，判定某些数据点的label可能出错（出错原因是由于noise的影响）
采取措施：data cleaning采取的措施是将该数据点的label修正过来；data pruning采取的措施是将该数据点从训练数据中删除。
该方法有时会有用。但不是总是有用。
原因例如：
判别数据点label错误的判别标准通常要依靠经验值选取。
当训练数据很多时，某些数据点label的修正与否对最终结果影响不大。
data hintin*生新的训练数据
例如对手写数字图片进行平移或旋转产生新的训练数据virtual examples。
并不是总是有效。需要确保加进去的data有道理，并且不能太偏离原来的分布。
virtual examples not i.i.d. subject to p(x,y)
concession for advantage现象
训练数据1由10次多项式，添加noise产生。
训练数据2由50次多项式，不添加noise产生。
现在用两个Hypothesis set来训练数据。H2是2次多项式的Hypothesis set。H10是10次多项式的Hypothesis set。
g2是H2中Error_in最小的model。
g10是H10中Error_in最小的model。
现在比较这两个model在训练数据和测试数据上的错误，Error_in和Error_out。
对于训练数据1，在从g2切换到g10时，发生了overfitting。
通过对learning curve分析，发现，当训练数据量N小时，简单的Hypothesis往往容易取胜。
对于训练数据2，在从g2切换到g10时，也发生了overfitting。
通过分析，目标函数的复杂性target complexity会造成与noise类似的情形，这种noise被称为deterministic noise。
deterministic noise 与 stochastic noise
分析3个变量对overfitting的影响：训练数据量N，Gaussian噪声强度\delta^2，目标函数复杂度Qf
定义overfit measure = Error_out(g10)-Error_out(g2)
分析得结论为：
<stochastic noise影响>当Qf固定时，noise大，训练数据量小时，会发生overfit；
<deterministic noise影响>当noise强度固定时，Qf越大，会造成overfit。
对deterministic noise的理解：
当目标函数比Hypothesis更复杂时，例如目标函数是50次多项式，而Hypothesis set是10次多项式，这时会产生deterministic noise。因为最好的g10也会在训练数据上有错误。
例如计算机中用复杂的deterministic function来产生pseudo-random随机数据。
deterministic noise与stochasticnoise区别
（1）deterministic noise与Hypothesis set有关。理论上，使用更复杂的Hypothesis，deterministic noise会下降。当然复杂的H也会带来训练的困难。
（2）fixed for a given x。对于同样的训练数据，deterministic noise是固定的。