机器学习中的Overfitting

1、浅谈机器学习中的Overfitting在机器学习中，常会出现这样一种的现象：一个假设在训练数据上表现很好(in-sample error 很小，即很小)，但是在训练数据外的数据集上却变现很差(out-of-sample error很大，即很大)，这时，我们称发生了过度拟合(overfitting)。1. Overfitting的原因Overfitting，字面上讲，就是“fitting the data more than is warranted.”。overfitting自然是我们不愿意看到的，那么是什么原因导致了overfitting呢？如果我们的训练数据中含有noise，那么我们在拟合

2、时，为了追求最小 (in-sample error)，一不小心，就可能用了过于复杂的模型不仅fit了data，还fit了noise，也恰恰是因为overfit了noise，造成学习出来的函数其实出现了很大的偏差，因此在新的数据上变现不好(很大)也就不足为奇了。可见，数据中含有noise是造成overfitting的一个原因。其实，造成overfitting的原因远不只是数据中noise一种，即使数据中没有noise，也有可能造成overfitting。例如，我们来看下面一个例子，目标函数是一个50阶多项式，数据如下面左图所示(这里没有任何noise),我们分别用2阶和10阶的多项式来拟合，拟合

3、结果如下面右图所示。 10阶的多项式的拟合结果竟然比2阶多项式的差，结果多少让人意外。我们想象两个人来解决同一个拟合问题，一个人比较聪明，会10阶的多项式，而令一个人只会2阶的多项式，但是，结果很奇怪，一个笨笨的人最后居然赢了，聪明人好像“聪明反被聪明误”。其实如果你知道VC theory, 就不难理解，用10阶的函数来拟合得到较差的概率要比用2阶的函数来拟合得到一个同样差的概率要大的多。如果你不知道VC theory，我们可以来看下面两个曲线，我们称之为学习曲线，表示了用2阶和10阶多项式拟合时错误率随测试数据量的大小的变化情况(左面的图是用2阶多项式的结果，右面的图是10阶多项式的结果)。

4、我们上面的例子中，数据量不够多，这时候从曲线可以看出，10阶多项式拟合后虽然很小，但是很大。 但是，我们也应该注意到，当数据足够多时(data size N足够大)，用10阶函数拟合会比2阶函数好（小）。因此，我们可以得到结论，overfitting跟目标函数的复杂度有关，复杂的目标函数更容易发生overfitting， 另外，overfitting还跟data size有关，当数据量较小时，我们应该选取较简单的模型来拟合，选择复杂的模型就容易产生overfitting。于是，我们得到了产生overfitting的三个最主要的原因：Data size，noise和 target complex

5、ity。上面例子中，如果我们将10阶多项式的值和2阶多项式的值的差作为overfitting的一种度量，那么ovefiting与Data size，noise和 target complexity的关系可以表示为如下两个图(图中由蓝色边到红色表示overfitting的概率逐渐变大)： 我们再次回头看刚才的例子，里面真的没有“noise”吗？如果目标函数太复杂，那么对于每一个模型来说，都没有办法来描述好目标函数，但是每一个模型的假设函数集中一定有一个对目标函数f(x)的最好的近似h*，他们之间的差异可以看做是一种noise，为了与data中的那种random noise(stochastic

6、noise)区分，我们称这种noise为deterministic noise。右图中,蓝线表示target function，红线表示best fit to f, 阴影部分就表示deterministic noise。Deterministic noise 和 stochastic noise对overfitting的影响非常相似（由上面的两个图形对比可以看出）。2. Overfitting的对策如何尽量避免overfitting呢？方法有很多，有一些简单的技巧，比如，从简单的模型开始尝试；数据清洗等；还有非常重要的两个手段，就是regularization和validation。2.1 R

7、egularizationRegularization是通过添加约束的方式来寻找一个简单的假设来拟合目标函数，从而避免过度拟合。以上面10阶多项式拟合的问题为例，可以表示为如下无约束的优化问题：那么利用2次多项式拟合，可以表示为一个有约束的优化问题，如下：将这个问题的约束放松一点，则有：将这个问题在进一步放松，得到如下形式：最后的式子，虽然仍然是使用10阶多项式在做拟合，但是它的约束却可以使得权重w比较小，或者说非0的w的分量的个数少，这就是Regularization，它在一定程度上尽量避免了overfitting。更一般地，Regularized的回归问题可以表示如下：或者矩阵形式下面要讲

8、如何来解这个有约束的规划了，那就是利用拉格朗日乘子法，上述问题等价于无约束优化问题：其中叫做lagrange乘子，为了一下表示方便，我们把上面的式子写成如下形式：对w求导，令其等于0，得 (Ridge Regression)注意只要，总是可逆的(是半正定的，正定的，正定矩阵总是可逆的)。我们称这种上面这种形如的regularizer 为weight-decay regularizer (weight decay就是指让weight变小), 或者叫L2 regularizer, 它是凸的，处处可微，并且很容易最优化。另外，还有一种常见的regularizer，叫做L1 regularizer，也

9、叫Lasso regularizer ，形如: ，它也是凸的，几乎处处可微，解释稀疏的。我们希望指出的是，如果做polynomial regression, 通常选择Legendre polynomial，即 比一般的polynomial，即 效果会好一些。选择了合适的regularizer之后，还有一个问题就是如何选择？那就需要用到下面将要介绍的validation。2.2 Validation 机器学习中，我们常常会把数据集分为互不相交的两部分，一部分叫做训练集，一部分叫做验证集（通常取1/5的数据量来作验证）。用来学习出一个最终的假设函数，来评估这个学习结果的好坏（近似估计学习出来的假设

10、函数在新的数据上的表现）。其实，验证集的作用不仅仅是用来评估最终的学习结果的好坏，还有一个重要的作用，那就是指导我们学习过程中模型的选择。例如，选择线性模型还是飞线性模型，选择多项式的阶数，选择regularization中的参数（不同的对应不同的模型）等等。当有很多模型可以选择时，可以用训练集分别学习得到不同的最终假设，我们再用验证集来分别估计各个模型学习出来的假设函数的好坏，从中选择出最好的一个假设对应的模型；这时候我们用选出来的模型在整个数据集上重新学习，得到最终的假设（注意用整个数据集学习出来的假设往往比仅仅用训练集学习出来的假设要好一些）。为了近可能准确地评估学习结果的好坏，我们希望

11、训练集尽可能地大；然而，训练集大就会导致训练集小，使得学习结果不好。如何选择训练集才能既满足评估学习结果的要求，又满足有足够的训练数据呢？一种方法就是Cross Validation。Leave-one-out Cross Validation：每次从数据集中取一个数据作为validation data, 其余作为training data。显然，用一个数据评估的结果并不能反映出学习结果的好坏，但是，这里选取的方式有N种，我们可以用所有的的平均值来估计学习结果的好坏。V-fold Cross Validation：上面模型的推广。如果数据量很大时，我们用Leave-one-out就太浪费时间了（有多少数据，Leave-one-out就做多少遍）。这时，把数据集分成大小相等并且互不相交的份（通常取），每次取一份（不是仅仅一个数据）拿来做validation，其余的做training。其余的跟Leave-one-out完全一样。实际中, 我们通常用V-fold Cross Validation, 而不是Leave-one-out Cross Validation。最后，我们简单比较一下tr