什么是过拟合、欠拟合？

读书时，身边经常有一些学生，没日没夜的刷题，练习册上的题几乎都能背下来。但是一到考试遇到没见过的题时就不会做了。这就是过拟合。过拟合指一种现象：如果当前的假设空间存在“真”模型，学习时选择的参数过多以至于对训练集有很高的拟合能力，而对未知数据的拟合能力很差。
而有另外一些学生，那些平时不怎么学，考试时自然不会。欠拟合：如果当前的假设空间存在“真”模型，学习的参数太少了，对当前和未知数据的拟合能力都很差。

对于欠拟合的学生，唯一的办法就是改变他们的态度，多学点，多刷题，多总结。放到机器学习里面就是，特征工程多增加点有用特征、增加样本量。
而对于过拟合的学生，处理起来就没那么简单粗暴了。题是无穷无尽的，不可能把所有的题都给刷完，得教会他用现有知识解决未知问题。

过拟合可能的原因：

• VC Dimension太大了。公式那么多，每次都想把所有的数学公式用上，反而把自己给绕进去了。
• 数据本身存在噪音。参考书都错了，我们还能怎样。。。
• 训练样本不够。虽然刷题了，但每次都是刷的同样的题，见得少了。

VC Dimension太大了

对于一个数据集，只要特征（一般情况下VC Dimension约等于特征自由度）足够多，能完全正确预测训练集。对于每个样本构造一个函数$f_i(x_i)=0$fi​(xi​)=0，则每一个样本都是$\prod f_i(x_i)$∏fi​(xi​)的解。正确率为100%！！！
上一篇文章提到，我们需要选择不大不小的$d_{vc}$dvc​，所以我们需要限制特征的数量。
通常我们会构造很多的特征，然后挑选出其中有用 特征。挑选的方法：

• 子集搜索和评价。第一步：子集搜索。以前向搜索为例：先对每个特征看着一个子集，选出最优特征集{$x_i$xi​},然后以此为基础，一步一步地增加最优特征，直到选择的最优特征不如上一轮为止。类似的方法还有后向搜索和双向搜索。
  第二步：子集评价。可以用信息熵来作为评价标准，其他能判断划分的差异的机制也可以作为评价标准。
• 根据相关性挑选：计算特征与target的相关性，选择出相关性高的特征。有可能是一阶线性相关，有可能是平方相关，立方相关，所以对于一些线性模型可能会排除掉一些好的特征。我们可以对数据做出散点图，再决定要计算几阶相关性。
• 过滤式：计算各个特征的发散性或相关性，移除或选择Top K个的特征，或者满足阈值的特征。特点：与学习器无关，简单、易于运行、易于理解。通常对于理解数据有较好的效果。但在特征优化、提高泛化能力上效果一般。常用的有方差选择法、卡方系数法、皮尔逊相关系数法、互信息系数法。
  方差选择法：通常如果特征的方差很小，则各个样本之间在此特征上无明显差异，不易于区分样本间的差距。所以通常去掉方差小的特征。另方差选择法简单但效果一般，故通常用来做初步筛选，然后再用其他方法选择特征。例如买房时，我们可以把有2个厕所作为一个可能有用的特征，但是绝对不会拿有没有厕所作为参考的特征。
  卡方系数法：卡方检验值越大，相关性越强。卡方分布是一种由各种正太分布求和后构造的分布，当自由度很大时接近正太分布。
  皮尔逊相关系数法：相关系数绝对值越大，相关性越强。只对线性关系敏感。要求数据是近正太分布。
  互信息系数法：能够衡量各种相关性的特征集，计算相对复杂。例如ID3算法就使用了互信息。
• 包裹式：过滤法不考虑与学习器的性能,包裹使用了最终将要使用的学习器性能来作为评价标准。具体做法如下图：
  这里使用了拉斯维加斯法的随机策略来做子集搜索。
  优点：结合了学习器的性能，效果一般比过滤发好。
  缺点：①每次的子集评价都要训练模型，运算开销大；②如果特征数量很大，运行时间有限，有可能得不到解。
• 嵌入式：包裹式虽然考虑了学习器性能，但是特征选择和学习器训练过程是分开的，运算开销太大，我们希望特征选择和学习器训练过程在同一优化过程中完成。即训练过程中自动完成了特征提取。
  例如L1正则化。由于L1的等高线为一超矩形，容易得到稀疏解，这样部分特征的系数为0，自动完成了特征的选择。
  当我们使用L2正则化时，可以通过岭脊图来选择特征。例如当某个特征的线波动特别大且无规律时，有极点时，这个特征通常对模型是一个干扰效果，可以排除。

数据本身存在噪音

当数据存在噪音时，我们无论如何都是不能做出正确有效的预测的？那噪音对我们的影响有多大呢？
当数据量很大，特征很多时，我们很容易获得$E_{in} \approx E_{out} $，但是很容易发生维度灾难。即运算量呈指数增长。其实模型本身就引入了一种噪音。这从侧面印证了我们需要做特征选择。 现在我们仅仅来考虑样本噪音。噪音分为随机噪音和确定性噪音。假设我们的数据由两部分构成：第一部分是目标函数f(x)，$，但是很容易发生维度灾难。即运算量呈指数增长。其实模型本身就引入了一种噪音。这从侧面印证了我们需要做特征选择。现在我们仅仅来考虑样本噪音。噪音分为随机噪音和确定性噪音。假设我们的数据由两部分构成：第一部分是目标函数f(x)，Q_f$阶多项式；第二部分是噪声ϵ，服从Gaussian分布。当数据量N确定时，对于随机噪音——方差越大，对模型影响越大；而确定性噪音：$阶多项式；第二部分是噪声ϵ，服从Gaussian分布。当数据量N确定时，对于随机噪音——方差越大，对模型影响越大；而确定性噪音：Q_f$对过拟合有很大影响。具体如下图：

overfitting的解决方法：

• 从简单模型做起：根据剃刀原理，从最简单的模型做起，性能差不多时，优先选择简单的模型。因为就像上面提到的，模型复杂度本身就是一种噪音。
• 数据清洗：校正或剔除明显为噪音的样本。关键在于如何确定噪音。这个一般需要业务知识为基础。一般的数学方法有箱线图、$3\sigma$3σ、$6\sigma$6σ选择。
• data hinting：获取更多的数据
• 正则化：一般为L1、L2正则化，对当前的模型做惩罚。
• 交叉验证