机器学习中几个重要算法常识

这篇给大家介绍一些机器学习中必须要了解的几个算法常识，这些算法常识在之后从事机器学习方面研究和工作时是非常重要的。

1 欠拟合与过拟合

我们已经知道，我们希望通过机器学习学得的模型的泛化能力比较强，直白来说就是使得学得的模型不仅仅在在训练样本中工作得很好，更应该在新的样本中工作很好。

通常我们把分类错误的样本数占总样本数的比例称为错误率（error rate），而准确度（accuracy）= 1 - 错误率。举例来说，如果在 m 个样本有 a 个样本分类错误，那么错误率为 a/m，准确度为 1 - a/m。

更一般地，我们将模型在训练集上的误差称为训练误差（train error），在测试集上的误差称为测试误差（test error），在假设测试数据与真实数据独立同分布的前提下，测试误差可以作为泛化误差（generalization error）的近似。我们当然是希望能够得到泛化误差小的模型，但是由于我们事先不知道测试集是什么样子，所以我们在使用机器学习算法时，不会提前固定参数，而是调整参数去降低训练误差。在整个过程中，泛化误差的期望会大于等于训练误差的期望。

想要保证模型效果好，也就是泛化误差比较小，可以通过以下两个因素来实现：

降低训练误差。

缩小训练误差和泛化误差的差距。

这两个因素分别对应机器学习的两个主要挑战：欠拟合（underfitting）和过拟合（overfitting）。欠拟合是指模型不能再训练集上获得足够低的误差，而过拟合是指训练误差和泛化误差之间的差距太大。

欠拟合相对容易理解点，过拟合可能不太容易理解，这里给出一个形象的比喻。上学考试的时候，有的人采取题海战术，把每个题目都背下来。但是题目稍微一变，他就不会做了。因为他非常复杂的记住了每道题的做法，而没有抽象出通用的规则。直观理解，这种情况就属于过拟合。

我们再来通过一张图片来直观地理解下欠拟合与过拟合的区别。有一组数据集包含了特征X和标签Y，简单起见，我们只考虑一个特征，现在我们通过三个假设函数来拟合这批相同的数据，得到结果如下：

解释下图片的内容：(左) 用一个线性函数拟合数据得到的模型导致欠拟合——它无法捕捉数据中的曲率信息。(中) 用二次函数拟合数据得到的模型在未观察到的点上泛化得很好。这并不会导致明显的欠拟合或者过拟合。 (右) 用一个高阶的多项式拟合数据得到的模型会导致过拟合。

相比于欠拟合，过拟合在实际工作中更为常见，出现过拟合的原因常见的有以下几种：

训练集和测试集分布不一致。

训练集的数量级和模型的复杂度不匹配。训练集的数量级小于模型的复杂度。

样本里的噪音数据干扰过大，大到模型过分记住了噪音特征，反而忽略了真实的输入输出间的关系。

2 没有免费的午餐定理

我们经常听人谈论“什么算法更好”或者“A算法比B算法好”这样类似说法，其实这样的说法忽略了一个前提，那就是在解决某一个具体的问题（任务）上。为什么这么说呢，因为如果考虑所有潜在的问题，所有的学习算法都一样好。要谈论算法的相对优劣，必须要针对具体的问题和任务才有意义。

举个例子，我们有两组数据集，将它们分别切分成训练集和测试集之后，然后通过假设函数A和B分别拟合对应的两个训练集，得到结果如下：

在图（a）中的数据分布下，模型A和B都完美地拟合了所有的训练样本，但是在测试样本上的表现，模型A的拟合效果超过了模型B；在图（b）中的数据分布下，模型A和B同样完美地拟合了所有的训练样本，但是在测试样本上的表现，模型B的拟合效果超过了模型A。

上面的例子充分说明了没有哪个算法是绝对完美的，每个算法都有它适合的数据集，也就是说它适合的任务。

没有免费的午餐定理（No Free Lunch Theorem，简称 NFL）说的就是无论我们能设想到的最先进的算法还是多么笨拙的算法（比如胡乱猜测），它们的期望性能其实都是相同的。

这个结论看起来非常地“匪夷所思”，但实际上它是成立的。不过它成立的前提在所有可能出现的数据分布上。但是在实际生活中，我们很多时候只关注自己试图解决的问题，希望为它找到一个好的解决方案。举个实际生活中的场景，比如说你的家里地铁口有800m，你上班时想快速到达地铁口，这时候选择共享单车就是一个不错的方案；但如果说你想快速从北京到上海，这时候，共享单车显然不是一个好的选择。所以我们关注的就是在当前要解决的问题下（或者任务下），为它找到一个合适的解决方案。

所以说，机器学习研究的目标不是找一个通用学习算法或是绝对最好的学习算法。反之，我们的目标是理解什么样的分布与机器学习获取经验的“真实世界”相关，什么样的学习算法在我们关注的数据生成分布上效果最好。

3 偏差和方差

我们希望在能够得到一个泛化误差比较小的模型的同时，也希望能够解释为什么模型的泛化误差比较小（或者比较大）。我们可以将模型的期望泛化误差分解为两部分：偏差（bias）和方差（variance）之和。即：

泛化误差 = 偏差 + 方差

偏差度量了学习算法的期望预测与真实结果偏离程度，即刻画了学习算法本身的拟合能力。方差度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响，或者说学习算法的稳定性。

偏差-方差分解说明，泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的。给定学习任务，为了取得好的泛化性能，则需使偏差较小，既能够充分拟合数据，并且使方差较小，即使得数据扰动产生的影响小。

这里我们通过一张扔飞镖的图片来解释下偏差和方差。

image

左上角的低偏差、低方差是理想中的模型，类似于把飞镖扔到了离靶心很近的地方，并且聚集效果也很好；右上角的低偏差、高方差是模型过拟合的表现，类似于把飞镖扔到了离靶心很近的地方，但是聚集效果效果不好；左下角的高偏差、低方差是模型欠拟合的表现，类似于把飞镖扔到了离靶心很远的地方，但是都集中在一个位置；右下角的高偏差、高方差是最差的模型了，类似于把飞镖扔到了靶子上，但是飞镖离靶心也很远，而且彼此间很分散。

一般来说，偏差和方差是有冲突的，也就是说，当模型复杂度较低时，模型的偏差较高，方差较低；当模型复杂度较高时，模型的偏差较低，方差较高。下图给出了他们之间的一个关系。