林轩田《机器学习基石》（十三）—— Hazard of overfitting
上节课讲了如何解决非线性问题：通过特征变换，将非线性模型映射到另一个空间，转换为线性模型，再来进行分类。我们说这样会增加额外的模型复杂度。今天我们说这个额外的复杂度会造成机器学习过拟合（overfitting）现象。今天讲困难怎么产生的以及如何解决它。
一、什么是过拟合？
先从一个例子出发，我们现在要做一个一维的回归分析，资料中有五个点，然后输出一个实数。
资料：，N = 5
目标函数f：f是一个二次函数（图中为蓝色曲线）
label：，由f产生再加一点点很小的噪音
解决方案1：4次多项式做回归分析，即用四次多项式把x空间中的点转换到z空间，再进行线性回归。
我们知道，四次多项式通过五个点，会有一个唯一解。所以，图中为红色曲线。
我们发现红色曲线和真实的蓝色曲线一点都不像，实际上的很大，因为除了那五个点，其他未知点的效果都不是很好。
所以很小，而
很大，这是一种坏的泛化性。
我们回过头来看一下VC曲线：
就像上次说的，如果，那么实际上的
与
差距越来越大（
很大，
很小）
可以看到随着vc维越来越大，越来越小，in-sample error曲线一直下降，model complexity曲线就上升；
所以造成先下后上。
从最好的vc维往右看，
一直下降，
一直上升。我们看样子是把fitting做好了，但其实过头了（over）。所以
变小，
变高这个过程叫做overfitting，过拟合。（常见，不容易解决）
从最好的vc维往左看，
处于高位，
也比较大，我们做的fitting不够好，所以导致
也不够好（under），所以叫做underfitting，欠拟合。
给出一个比喻来描述overfitting，把overfitting比作出了车祸，那么我们分析产生的原因：
- 开太快，油门太重，即使用了太大的vc dimension。
- 道路崎岖，也就是有太多noise。
- 对路况不熟悉，在机器学习中就是资料太少。
二、noise与资料
我们从问题出发
资料：（图中为黑色圆圈）
目标函数f：f是一个十次函数（图中为蓝色曲线）
label：，由f产生再加一点点很小的噪音
可以看到由于加了噪音，数据并非全部落在蓝色曲线上
另一个问题：
资料：（图中为黑色圆圈）
目标函数f：f是一个50次函数（图中为蓝色曲线）
label：
此时，无噪音，数据全部落在蓝色曲线上
我们知道上面两个问题了，现在来看看我们选用的两个模型，一个是2阶多项式，另一个是10阶多项式
，分别对上面两个问题进行建模。
对于第一个问题来说，（目标函数f是一个十次多项式）
首先要明确是在已知样本上的err，是看线与圆圈的重合程度，重合越多，
越小。
是在未知样本上的err，是看我们模型的线与真实的线是否相同，模型的线越接近蓝色线，
越小。
可以看到，线与圆圈的重合程度方面，红线赢了，在模型的线与真实的线是否相同方面，在图像的左端和右端，红线和蓝线十分的不接近。于是通过计算有：
虽然10阶模型的比2阶的小，但是它的
要比2阶的大得多，而2阶的
和
相差不大，显然地，从二次切换到十次，发生了overfitting。
同样对于另一个高维问题：
可以看到，线与圆圈的重合程度方面，红线再一次赢了，也就是说10阶模型的比2阶的小；在模型的线与真实的线是否相同方面，红线和蓝线十分的不接近。也就是说
的
非常糟糕。
但是我们想，比如目标函数是十次的情况，用二阶多项式就是选择了放弃完美解（因为真实f是十次，只有选择十次多项式
才有可能找到一模一样的或者几乎接近的线）。实际上却常常是“以退为进”，意思是就算你知道真正的f是十次多项式，你也选择一个看起来好的十次多项式作为g，那么最终结果也不一定好。
来看看为什么会这样？
从learning curve来分析一下具体的原因，learning curve描述的是和
随着数据量N的变化趋势。下图中左边是2阶学习模型的learning curve，右边是10阶学习模型的learning curve。我们首先要认识一个事实：如果你选择我们已知的点靠近一点点，那么在已知err上会小一点点，就是
会小一点，在图中
的线会往下一点，但是在未知err会远离一点点（因为可能向noise靠近了一点点），
会大一点，在图中
的线会往上一点。之前讲过有noise的情况的公式，之前讲过d为多项式次数，所以可以发现10阶的偏移量更大（
受到noise的影响大）。
在左边区域，左右两张图比较，一定是右边的比较低，
则是右边比较高，那么在左边区域（资料量不够多的时候），高阶的多项式表现都不会好，都会overfitting。所以资料量不够多的时候，千万不要选择过于复杂的多项式作为g。
上面讲了资料，下面就讲noise。
另一个例子中，目标函数是50阶多项式，且没有加入noise。这种情况下，我们发现仍然是2阶的模型拟合的效果更好一些，明明没有noise，为什么是这样的结果呢？
刚才我们说，对于f是50阶的情况，和
都做不好，但
会稍微好一点。灵魂一问：真的没有noise吗？今天学的事情很复杂，无论
和
都做不好，这个复杂的行为就和noise一样。即复杂度造成了类似noise的影响。下一节会具体讲解这个问题。
三、什么时候要小心overfit可能发生？
我们把产生资料的过程分为两个步骤，一个是用目标函数f，阶多项式，但要注意的是我们是产生真正的这么多阶的多项式，而不是伪装的
阶多项式；再加上noise，noise服从高斯分布。接下来我们讨论Gaussian分布的noise强度不一样的时候（
），对我们的overfitting的影响是什么？（资料数设置为N），我们现在有三个变数，
（影响noise强度）、N、
。于是我们研究这三个变数对overfit的影响。
还是之前的两个模型和
，
,
, 以及显然有
我们用来度量过拟合的程度。
- 情况一
下面展示了在固定为20时候，横坐标为样本数量N，纵坐标为噪声水平
的图像，图里的颜色代表有多么overfit，越靠近红色，过拟合程度越大，越靠近蓝色，则过拟合没有那么严重。可以发现，好的情况一般发生在N大，noise水平小的情况。
- 情况二
下面展示了噪声水平在固定为0.1时候，横坐标为样本数量N，纵坐标为阶数
的图像。图里的颜色代表有多么overfit，越靠近红色，过拟合程度越大，越靠近蓝色，则过拟合没有那么严重。大部分情况下，和上面的图比较接近，坏的情况都发生在左上角，好的情况都发生在右下角，也就是说目标越复杂。
我们把上面情况一中的noise叫做stochastic noise，随机噪声；第二节中我们说了，模型复杂度也是一种噪声，于是把情况二中的这种noise叫做deterministic noise，可以计算出来的噪声。
总之，在给出定以后，我们从上面两个情况来看看发生过拟合的时间点有：
- 资料太少
- stochastic noise太多
- deterministic noise太多（目标函数f很复杂，目标函数一旦很复杂，那么它一定存在某个地方无法被任何一个h很完美的描述，这个地方也就产生了噪音，这些噪音如图中灰色的部分，在实际中也比较常见比如电脑生成伪随机。）
- vc维太多
overfitting其实很容易发生。如果教一个小朋友数数字，我们不会从实数的完备性开始讲起，我们只会举一些简单例子。同样，在学hypothesis也不用学太复杂，这样deterministic noise会小一些。
四、如何避免overfitting呢？
之前把overfitting比作出了车祸，我们分析了产生的原因，现在给出解决方法：
- 油门太重，即使用了太大的vc dimension。解决方法：开慢点，即从简单的模型开始学起。
- 道路崎岖，也就是有太多noise。解决方法：把这些崎岖的地方搞清楚，即数据清洗。数据提纯（data cleaning/pruning）。
- 对路况不熟悉，在机器学习中就是资料太少。解决方法：增加路况资料，即现有的资料或对这个问题的了解中产生新的、多的资料（data hinting）。
- 开太快。解决方法：适时地踩刹车，即添加正则项。
- 其他。解决方法：时时刻刻看看仪表板，即validation 验证/交叉验证。
本节课主要介绍简单的data cleaning/pruning和data hinting两种方法。
比如对于手写数字问题，如果有人字写得不好看，比如图中左上角，我们看不出它为什么是“5”.若是现在有一个方法，我们可以检测出它不是真的‘5’（比如是不是靠近不同的类，而与相同的类离得远；或者是这个点err很大），这样我们有理由相信这个点是noise，接下来怎么做？
data cleaning：把这个noise的label改过来。
data pruning：把这个noise丢掉。
这就是说如果知道那些点是noise，用上面两个方法做就行，难点是如何找到这个noise（现在还没有比较完美的找法）。
如果手写字稍微转了转角度，那么这些字也是属于同一个字的。比如现在我们一共就这么多资料，当我们没有更多的资料却想告诉电脑更多的知识，那么我们可以把手上的资料转一转角度，变成新资料，然后再学习。所以，data hinting是针对N不够大的情况，如果没有办法获得更多的训练集，那么data hinting就可以对已知的样本进行简单的处理、变换，从而获得更多的样本。但是加进来的这些资料要有道理，不要和原来的差太远，不然会偏离原来的资料的分布，导致学习效果不好。
总结：