台湾大学林轩田老师的《机器学习基石》课程由浅入深、内容全面，基本涵盖了机器学习领域的很多方面，作为机器学习的入门资料非常适合。很久之前看过这门课，但是有些地方还是不太明白，二刷这门课，把重要的知识总结起来，算是做一个复习，加深理解，也方便之后查阅。这篇文章介绍了第四部分How Can Machine Learn Better？

How Can Machine Learn？

Hazard of Overfitting

首先，介绍因为模型复杂度增加带来机器学习中一个很重要的问题：过拟合（overfitting）。

What is Overfitting?

假设平面上有5个点，目标函数f(x)是2阶多项式，如果hypothesis是二阶多项式加上一些小的noise的话，那么这5个点很靠近这个hypothesis，$E_{in}$很小。如果hypothesis是4阶多项式，那么这5点会完全落在hypothesis上，$E_{in}=0$。虽然4阶hypothesis的$E_{in}$比2阶hypothesis的要好很多，但是它的$E_{out}$很大。因为根据VC Bound理论，阶数越大，即VC Dimension越大，就会让模型复杂度更高，$E_{out}$更大。我们将这种$E_{in}$很小，$E_{out}$很大的情况称之为bad generation，即泛化能力差，这种对训练样本拟合过分好的情况称之为过拟合（overfitting）。

另一方面，随着VC Dimension越来越小，$E_{in}$和$E_{out}$都越来越大，这种情况称之为欠拟合（underfitting），即，模型对训练样本的拟合度太差，VC Dimension太小了。

一个好的fit，$E_{in}$和$E_{out}$都比较小，尽管$E_{in}$没有足够接近零，而对overfitting来说，$E_{in}\approx 0$，但是$E_{out}$很大。那么，overfitting的原因都有哪些呢？

我们举个开车的例子， 把发生车祸比作为overfitting，那么造成车祸的原因包括：

• 车速太快（VC Dimension太大）
• 道路崎岖（noise）
• 对路况的了解程度（训练样本数量N不够）

也就说是，VC Dimension、noise、N这三个因素是影响过拟合现象的关键。

The Role of Noise and Data Size

为了尽可能详细地解释overfitting，我们进行这样一个实验，试验中的数据集不是很大。首先，在二维平面上，一个模型的分布由目标函数f(x)（x的10阶多项式）加上一些noise构成，下图中，离散的圆圈是数据集，目标函数是蓝色的曲线。数据没有完全落在曲线上，是因为加入了noise。

然后，同样在二维平面上，另一个模型的分布由目标函数f(x)（x的50阶多项式）构成，没有加入noise。下图中，离散的圆圈是数据集，目标函数是蓝色的曲线。可以看出由于没有noise，数据集完全落在曲线上。

现在，有两个学习模型，一个是2阶多项式，另一个是10阶多项式，分别对上面两个问题进行建模。首先，对于第一个目标函数是10阶多项式包含noise的问题，这两个学习模型的效果如下图所示：

由上图可知，2阶多项式的学习模型$E_{in}=0.050，E_{out}=0.127$，10阶多项式的学习模型$E_{in}=0.034，E_{out}=9$。虽然10阶模型的$E_{in}$比2阶的小，但是其$E_{out}$要比2阶的大得多，而2阶的$E_{in}$和$E_{out}$相差不大，很明显用10阶的模型发生了过拟合。

然后，对于第二个目标函数是50阶多项式没有noise的问题，这两个学习模型的效果如下图所示：

由上图可知，2阶多项式的学习模型$E_{in}=0.029，E_{out}=0.12$，10阶多项式的学习模型$E_{in}=0.00001，E_{out}=7680$。虽然10阶模型的$E_{in}$比2阶的小，但是其$E_{out}$要比2阶的大得多，而2阶的$E_{in}$和$E_{out}$相差不大，很明显用10阶的模型发生了过拟合。

上面两个问题中，10阶模型都发生了过拟合，反而2阶的模型却表现得相对不错。这好像违背了我们的第一感觉，比如对于目标函数是10阶多项式，加上noise的模型，按道理来说应该是10阶的模型更能接近于目标函数，因为它们阶数相同。但是，事实却是2阶模型泛化能力更强。这种现象产生的原因，从哲学上来说，就是“以退为进”。有时候，简单的学习模型反而能表现的更好。

Deterministic Noise

假设我们产生的数据分布由两部分组成：第一部分是目标函数f(x)，$Q_f$阶多项式；第二部分是噪声$\epsilon$，服从Gaussian分布。接下来我们分析的是noise强度不同对overfitting有什么样的影响。总共的数据量是N。

$y=f(x)+\epsilon \sim Gaussian(\sum^{Q_t}_{q=0}\alpha_q, \sigma ^2)$

那么下面我们分析不同的$(N, \sigma ^2)$和 $(N, Q_f)$ 对overfitting的影响，量化为 $E_{out}- E_{in}$。结果如下：

上图中，红色越深，代表overfit程度越高，蓝色越深，代表overfit程度越低。先看左边的图，左图中阶数$Q_f$固定为20，横坐标代表样本数量N，纵坐标代表噪声水平$\sigma ^2$。红色区域集中在N很小或者$\sigma ^2$很大的时候，也就是说N越大，$\sigma ^2$越小，越不容易发生overfit。右边图中$\sigma ^2=0.1$，横坐标代表样本数量N，纵坐标代表目标函数阶数$Q_f$。红色区域集中在N很小或者$Q_f$很大的时候，也就是说N越大，$Q_f$越小，越不容易发生overfit。上面两图基本相似。

从上面的分析，我们发现$\sigma ^2$对overfit是有很大的影响的，我们把这种noise称之为stochastic noise。同样地，$Q_f$即模型复杂度也对overfit有很大影响，而且二者影响是相似的，所以我们把这种称之为deterministic noise。之所以把它称为noise，是因为模型高复杂度带来的影响。总结一下，有四个因素会导致发生overfitting：

• data size N ↓
• stochastic noise $\sigma ^2$↑
• deterministic noise $Q_f$↑
• excessive power ↑

我们刚才解释了如果目标函数f(x)的复杂度很高的时候，那么跟有noise也没有什么两样。因为目标函数很复杂，那么再好的hypothesis都会跟它有一些差距，我们把这种差距称之为deterministic noise。deterministic noise与stochastic noise不同，但是效果一样。其实deterministic noise类似于一个伪随机数发生器，它不会产生真正的随机数，而只产生伪随机数。它的值与hypothesis有关，且固定点x的deterministic noise值是固定的。

Dealing with Overfitting

现在我们知道了什么是overfitting，和overfitting产生的原因，那么如何避免overfitting呢？避免overfitting的方法主要包括：

• start from simple model
• data cleaning/pruning
• data hinting
• regularization
• validataion

这几种方法类比于之前举的开车的例子，对应如下：

data cleaning/pruning就是对训练数据集里label明显错误的样本进行修正（data cleaning），或者对错误的样本看成是noise，进行剔除（data pruning）。data cleaning/pruning关键在于如何准确寻找label错误的点或者是noise的点，而且如果这些点相比训练样本N很小的话，这种处理效果不太明显。

data hinting是针对N不够大的情况，如果没有办法获得更多的训练集，那么data hinting就可以对已知的样本进行简单的处理、变换，从而获得更多的样本。举个例子，数字分类问题，可以对已知的数字图片进行轻微的平移或者旋转，从而让N丰富起来，达到扩大训练集的目的。这种额外获得的例子称之为virtual examples。但是要注意一点的就是，新获取的virtual examples可能不再是iid某个distribution。所以新构建的virtual examples要尽量合理，且是独立同分布的。

Regularization

我们介绍了过拟合发生的原因：excessive power, stochastic/deterministic noise 和limited data。其中Regularization正则化是解决overfitting一个有效的简单方法。

接下来，介绍两种Regularizer正则化项：L1和L2。L2 Regularizer一般比较通用，其形式如下：

$\sum^{Q}_{q=0}w_{q}^2=||w||_{2}^2$

这种形式的regularizer计算的是w的平方和，是凸函数，比较平滑，易于微分，容易进行最优化计算。L1 Regularizer的表达式如下：

$\sum^{Q}_{q=0}|w_q|=||w||_1$

Validation

K折交叉验证(k-fold cross-validation)首先将所有数据分割成K个子样本，不重复的选取其中一个子样本作为测试集，其他K-1个样本用来训练。共重复K次，平均K次的结果或者使用其它指标，最终得到一个单一估测。

Two Learning Principles

Occam’s Razor

奥卡姆剃刀定律（Occam’s Razor），是由14世纪逻辑学家、圣方济各会修士奥卡姆的威廉（William of Occam，约1285年至1349年）提出。奥卡姆（Ockham）在英格兰的萨里郡，那是他出生的地方。他在《箴言书注》2卷15题说“切勿浪费较多东西去做用较少的东西同样可以做好的事情。” 这个原理称为“如无必要，勿增实体”（Entities must not be multiplied unnecessarily），就像剃刀一样，将不必要的部分去除掉。

Occam’s Razor反映到机器学习领域中，指的是在所有可能选择的模型中，我们应该选择能够很好地解释已知数据并且十分简单的模型。

上图就是一个模型选择的例子，左边的模型很简单，可能有分错的情况；而右边的模型非常复杂，所有的训练样本都分类正确。但是，我们会选择左边的模型，它更简单，符合人类直觉的解释方式。这样的结果带来两个问题：一个是什么模型称得上是简单的？另一个是为什么简单模型比复杂模型要好？

简单的模型一方面指的是简单的hypothesis h，简单的hypothesis就是指模型使用的特征比较少，例如多项式阶数比较少。简单模型另一方面指的是模型H包含的hypothesis数目有限，不会太多，这也是简单模型包含的内容。

那为什么简单的模型更好呢？下面从哲学的角度简单解释一下。机器学习的目的是“找规律”，即分析数据的特征，总结出规律性的东西出来。假设现在有一堆没有规律的杂乱的数据需要分类，要找到一个模型，让它的$E_{in}=0$，是很难的，大部分时候都无法正确分类，但是如果是很复杂的模型，也有可能将其分开。反过来说，如果有另一组数据，如果可以比较容易找到一个模型能完美地把数据分开，那表明数据本身应该是有某种规律性。也就是说杂乱的数据应该不可以分开，能够分开的数据应该不是杂乱的。如果使用某种简单的模型就可以将数据分开，那表明数据本身应该符合某种规律性。相反地，如果用很复杂的模型将数据分开，并不能保证数据本身有规律性存在，也有可能是杂乱的数据，因为无论是有规律数据还是杂乱数据，复杂模型都能分开。这就不是机器学习模型解决的内容了。所以，模型选择中，我们应该尽量先选择简单模型，例如最简单的线性模型。

Sampling Bias

首先引入一个有趣的例子：1948年美国总统大选的两位热门候选人是Truman和Dewey。一家报纸通过电话采访，统计人们把选票投给了Truman还是Dewey。经过大量的电话统计显示，投给Dewey的票数要比投个Truman的票数多，所以这家报纸就在选举结果还没公布之前，信心满满地发表了“Dewey Defeats Truman”的报纸头版，认为Dewey肯定赢了。但是大选结果公布后，让这家报纸大跌眼镜，最终Truman赢的了大选的胜利。

为什么会出现跟电话统计完全相反的结果呢？是因为电话统计数据出错还是投票运气不好？都不是。其实是因为当时电话比较贵，有电话的家庭比较少，而正好是有电话的美国人支持Dewey的比较多，而没有电话的支持Truman比较多。也就是说样本选择偏向于有钱人那边，可能不具有广泛的代表性，才造成Dewey支持率更多的假象。

这个例子表明，抽样的样本会影响到结果，用一句话表示“If the data is sampled in a biased way, learning will produce a similarly biased outcome.”意思是，如果抽样有偏差的话，那么学习的结果也产生了偏差，这种情形称之为抽样偏差Sampling Bias。

从技术上来说，就是训练数据和验证数据要服从同一个分布，最好都是独立同分布的，这样训练得到的模型才能更好地具有代表性。