本栏目（机器学习）下机器学习基石专题是个人对Coursera公开课机器学习基石（2014）的学习心得与笔记。所有内容均来自Coursera公开课Machine Learning Foundations中Hsuan-Tien Lin林轩田老师的讲解。（https://class.coursera.org/ntumlone-002/lecture）
第13讲——-Hazard of Overfitting
从这一节开始，我们开始探讨How Can Machines Learn Better的话题。
一、什么是Overfitting
。这里的fitting指的就是E_in。下图中，竖直的虚线左侧是"underfitting", 左侧是"overfitting”。
发生overfitting 的主要原因是：使用过于复杂的模型(d_vc 很大)；数据噪音；有限的训练数据。
二、噪声与Data Size
如上图所示，我们可以分别从噪声与Data Size的角度理解地简单些：
有噪音时，更复杂的模型会尽量去覆盖噪音点，即对数据过拟合！这样，即使训练误差E_in 很小（接近于零），由于没有描绘真实的数据趋势，E_out 反而会更大。即噪音严重误导了我们的假设。
还有一种情况，如果数据是由我们不知道的某个非常非常复杂的模型产生的，实际上有限的数据很难去“代表”这个复杂模型曲线。我们采用不恰当的假设去尽量拟合这些数据，效果一样会很差，因为部分数据对于我们不恰当的复杂假设就像是“噪音”，误导我们进行过拟合。
如下面的例子，假设数据是由50次幂的曲线产生的（下图右边，without噪声），与其通过10次幂的假设曲线去拟合它们，还不如采用简单的2次幂曲线来描绘它的趋势。
三、确定性噪声
接下来我们探讨：什么时候需要小心Overfit会发生。
之前说的噪音一般指随机噪音(stochastic noise)，服从高斯分布；还有另一种“噪音”，就是前面提到的由未知的复杂函数f(X) 产生的数据，对于我们的假设也是噪音，这种是确定性噪音。
接下来我们做一个更详细的实验：加入强度为δ^2的高斯噪声；产生数据的target function是某个多次的多项式，其中最高的次数为Q_f；训练数据大小N。我们要探讨的就是：这三个变量变化的时候，到底对Overfit的程度有什么样的影响？
如下图所示，我们就用两个学习器：二次多项式g_2与10次多项式g_10。我们将overfit的程度表示为E_out(g10) – E_out(g2)。
下图左右两边分别表示了随机噪音和确定性噪音对于Overfitting 的影响。
可见，数据规模一定时，随机噪音越大，或者确定性噪音越大（即目标函数越复杂），越容易发生overfitting。总之，容易导致overfitting 的因素是：数据过少；随机噪音过多；确定性噪音过多；假设过于复杂(excessive power)。
对于最后一点解释一下，右边这个图与左边的图有一些小小的不一样：靠下部分说明好像Q_f往小的方向走的时候也会有overfit的现象出现。大家接的我们overfit的衡量方式是E_out(g10) – E_out(g2)，，当target function是10次多项式以下的时候，那么学习器g_10就太强了。
如果我们的假设空间不包含真正的目标函数f(X)（未知的），那么无论如何H 无法描述f(X) 的全部特征。这时就会发生确定性噪音。它与随机噪音是不同的。例如，目标函数是50次的多项式，而hypothesis是10次多项式的话，一定找个target function有某些地方是没办法被任何一个hypothesis所描述的。我们可以类比的理解它：在计算机中随机数实际上是“伪随机数”，是通过某个复杂的伪随机数算法产生的，因为它对于一般的程序都是杂乱无章的，我们可以把伪随机数当做随机数来使用。确定性噪音的哲学思想与之类似。
接下来来一发练习题：
四、解决Overfitting
对应导致过拟合发生的几种条件，我们可以想办法来避免过拟合。
正规化(regularization) 也是限制模型复杂度的方法，在下一讲介绍。其他解决过拟合的方法在后面几讲介绍。
第14讲——-Regularization
一、正则化的Hypothesis Set
发生Overfitting 的一个重要原因可能是假设过于复杂了，我们希望在假设上做出让步，用稍简单的模型来学习，避免Overfitting。例如，原来的假设空间是10次曲线，很容易对数据过拟合；我们希望它变得简单些，比如w 向量只保持三个分量（其他分量为零）。
也就是Hypothesis Set需要从高阶step back到低阶，例如从从10次多项式H_10走回到2次多项式H_2，如下图左所示。实际上就是代表在原来的Learning问题上加上一些限制Constraint。如果现在将左图的限制放松一些，如下右图所示。
可是，右图中的优化问题是NP-Hard 的。如果对w 进行更soft/smooth 的约束，可以使其更容易优化。我们将此时的假设空间记为H(C)，这是“正则化的Hypothesis Set”。如果我们能够顺利地解决下图的最佳化问题，找出一个好的w_reg的话，那么就是regularized hypothesis。
二、Weight Decay Regularization
通过前面的分析，我们已经把优化问题变为：
看自家总在期待,不知将来好歹,新乐吧总在不断等待,
