林轩田机器学习基石课程个人笔记-第十三讲
上一讲学习了如何利用线性转换将非线性的问题转换成为另一个域中的线性问题进行求解。但是这样做会导致模型的复杂度上升，带来的一个很直接的结果就是可能会出现过拟合现象
这一讲学习过拟合是如何出现的以及如何处理过拟合问题
经过其他课程的学习，对于过拟合的相关内容已经有了一定的了解，再通过这门课加深下印象。我们知道如果模型出现了过拟合，那么模型在训练数据上表现会非常好，但是在未知数据上就会表现得很差，这显然不是想要的结果，这也可以说模型得泛化能力很差（Bad Generalization）。
例如下图所示，我们有图中得5个数据点，目标函数是一个二次的多项式，图中为蓝色的线，尽管有某些点不能很好的被拟合，但是总体的效果还是很不错的；但如果用4次多项式来拟合数据，看起来每一个点都在线上，效果很棒，但是这时就已经发生了过拟合现象。具体说来，使用2次多项式，我们的Ein很小，Eout也不会很大，但是4次多项式的Ein=0，但Eout会变得很大，这明显是不好的。
总的来说泛化能力差可以表示为Ein很小，但是Eout很大
下面再从上一讲的一张图来看一下，横轴为VC Dimension，纵轴为Error，Ein随着dvc的增大而下降，Eout随着dvc的增大先下降后增大，模型的复杂度随着dvc的增大持续增大。当dvc很小时，Ein和Eout都很大，这时是一种欠拟合；当dvc很大时，Ein会很小，但是Eout会很大，导致Eout-Ein会很大，这是发生了过拟合。最理想的情况就是位于d*vc处，这时Eout-Ein的差值最小，模型的效果最好
故从Eout和Ein的关系出发，过拟合可以表示为很小的Ein，但很大的Eout
那么过拟合现象是怎么发生的呢？我们拿生活中的一个例子对比看一下：我们知道发生车祸的原因可能有如下几个
• 开的太快了
• 路况不好
• 行车时观察不足
类比在过拟合中就是
• 模型复杂度太高，dvc太大
• 数据中噪声太多
• 数据量有限
总结来看和过拟合相关的几个因素就是：VC Dimension、noise、N
前面我们知道了dvc太大会导致模型复杂度太高，会出现过拟合。那么其他的两个因素是如何影响过拟合的呢？下面给出两个不同的模型分布，一个由目标函数是10阶多项式产生，以及存在噪声；另一个由目标函数是50阶多项式产生且没有噪声
在这两个数据分布上，我们分别使用2阶多项式和10阶多项式来对它们分别建模看一下。首先来看第一个，从中可以看出两个模型虽然都不能完全拟合所有的点，但是10阶多项式的拟合更好。2阶多项式模型的Ein和Eout都不是很大，10阶多项式的Ein比前面的小一些，但Eout却大很多，显然发生了过拟合。然后再同理看第二个，2阶多项式模型的Eout和Ein的值都很小，虽然10阶多项式的Ein非常的小但Eout也非常的大，仍然是发生了明显的过拟合现象
不同的两个数据分布，2次多项式的效果都比10次的好，虽然拟合效果差一些，但是它的Eout-Ein很小，即它的泛化能力很好。这就告诉我们一个道理，有时简单的东西反而是最有效、最好的
下面从学习曲线来看一下上面的现象，坐标图横轴是数据的个数N，纵轴是误差期望。粗略来看两个图中的Ein和Eout的曲线的走势是差不多的，当N很大时Ein都很小，且Ein和Eout的差距都不大，但是在N较小时，即图中的灰色部分，2阶多项式的Eout和Ein都不大且差值也很小，但是10阶多项式的Eout和Ein的差值却非常的大。这也同样说明了2阶多项式模型的泛化能力更好。也有人说不是N很大时Eout和Ein差值都很小且10阶多项式模型的拟合效果更好吗，我们把数据增加到很多很多不就行了吗？但实际中这不太可行，一是因为我们不容易获得非常的多的数据，另一方面数据量太大非常容易发生维度灾难的问题
另一个例子中，目标函数是50阶多项式，且没有加入noise。这种情况下，我们发现仍然是2阶的模型拟合的效果更好一些，明明没有noise，为什么是这样的结果呢？
其实不然，虽然数据集中不含有噪声，但是当数据分布足够复杂时，这里的复杂度就是一种“噪声”
下面再详细的看一下什么时候需要小心过拟合的出现。假设数据分布如下所示，由Qf阶的多项式的目标函数f(x)和服从高斯分布的噪声产生，数据集大小为N，那么噪声的强度是如何影响过拟合的？
通过之前的分析我们可以确信的一件事就是10阶多项式的Ein比2阶的要小
那么我们来看一下不同的(N,σ^2)和(N,Qf)对过拟合的影响。overfit可以量化为Eout-Ein，可视化后如下所示，图中横轴为数据集大小N纵轴分别代表噪声强度和目标函数的复杂度。红色程度越深表示过拟合越明显，蓝色越深表示过拟合越不明显。在左图中，目标函数复杂度固定为20，在N一定时噪声的强度越大，过拟合程度越高；在噪声强度一定时，数据量越大，过拟合越不容易出现。右图中噪声强度是固定的0.1，分析同理可得，N越大或是Qf越小，越不易出现过拟合
从上面的分析，我们发现噪声强度对过拟合是有很大的影响的，我们把这种noise称之为stochastic noise。同样地， Qf(模型复杂度)也对过拟合有很大影响，而且二者影响是相似的，所以我们把这种称之为deterministic noise。
总结下和过拟合有关的几个因素
• data size N
• stochastic noise
• deterministic noise
• excessive power
具体的如下图所示
前面讲到即使数据集中不含有噪声的数据，但如果模型的复杂度很高时，它其实也是一种噪声。因为我们能得到的最好的h与真实的f之间总会有差距，表象在图像上就是灰色的部分，将其称为deterministic noise。它的值与假设有关，且固定点x的deterministic noise值是固定的
上面我们知道了过拟合是什么以及相关的影响因素，那么有没有方法来避免它的出现呢？下图给出了几种方法，为了方便理解，同样和车祸的例子进行了类比
• start from simple model：从简单的模型开始建模
• data cleaning/pruning：数据的清洗处理
• data hinting：数据的增加
• regularization：正则化
• validataion：验证
data cleaning/pruning就是对训练数据集里label明显错误的样本进行修正（data cleaning），或者对错误的样本看成是noise，进行剔除（data pruning）。它的关键在于如何准确寻找label错误的点或者是noise的点，而且如果这些点相比训练样本N很小的话，对于模型的效果几乎没有影响
data hinting是指数据不够多时，如果没有办法获得更多的训练集，那么data hinting就可以对已知的样本进行简单的处理、变换，从而获得更多的样本。这种额外获得的例子称之为virtual examples。但是要注意，新获取的数据可能不再是独立同分布于某一具体的分布
最后总结一下，这几件明白了什么是过拟合，过拟合是怎么发生了，它的相关影响因素是哪些且如何对它造成影响，最后讲了避免过拟合现象出现的几种办法，但正则化和验证后面才会学