机器学习应该知道的事（下）

新的一周又开始了，作为引子的review，还是有点长的，大家可以耐心的读读，绝对会让你有种豁然开朗的感觉。下周的重点是统计语言模型，别想的那么复杂，实际上就是贝叶斯概率和线性代数。窃以为，所谓以代码来讲解算法的，就是在培训码农，而不是一名合格的程序员。虽然，作为应用的学科，证明并不是那么像纯数学那样重要，但总归还是得明白原理吧。

ps1：新一季的《黑镜》还是那么的让人看完后，流下阵阵冷汗。 ps2：下周要好好弄下排版了，这两天晚上都是玩游戏去了，懒。

5.多面性的过拟合

如果我们所拥有的知识和数据不足以完全确定正确的分类器，怎么办？那我们运行的只是幻觉的一个分类器（或其中的一部分）的风险，却不是基于现实的基础，并且只是在数据中奇怪的编码随机。这个问题被称为过拟合，是机器学习的bug。当你的学习者输出一个对训练数据100％准确的分类器，但是对测试数据只有50％的精确度时，事实上它可以输出一个对两者都75％精确的分类器，就已经过拟合了。

机器学习领域的每个人都知道过拟合，但它有许多形式，并不那么显而易见。了解过拟合的一种方法是将广义误差分解为偏差和方差。偏差是学习者总是具有学习同样错误的东西的倾向。方差是学习随机事物的趋势，而不考虑真实信号。图1通过在板上投掷飞镖的类比来说明这一点。线性学习者具有高偏差，因为当两个类之间的边界不是超平面时，学习者不能归纳它。决策树没有这个问题，因为他们可以表示任何布尔函数，但另一方面，他们可以从高方差：在不同训练集中的相同现象学习再泛化的决策树通常是不同的，事实上，他们应该是相同的。类似的推理适用于优化方法的选择上：束搜索具有比贪婪搜索更低的偏差，但更高的方差，因为它尝试更多的假设。因此，与直觉相反，更强大的学习者不一定比不那么强大的学习者更好。

图2说明了这一点。即使真正的分类器是一组规则，最多1000个例子朴素贝叶斯比规则学习者更准确。这依然发生了，尽管朴素贝叶斯的假设前沿是线性的！这样的情况在机器学习中是常见的：强假假设可能优于弱假假设，因为学习者需要更多的数据来避免过拟合。

交叉验证可以帮助对抗过拟合，例如通过使用它来选择最佳尺寸的决策树来学习。但它不是灵丹妙药，因为如果我们使用它做出太多的参数选择，它本身可以开始过拟合了。

除了交叉验证，还有许多方法来对抗过度。最流行的一种是向评估函数添加正则化项。例如，这可以惩罚有着更复杂结构的分类器，从而是的较小的分类器只有较少的空间去过拟合。另一个选择是在添加新结构之前执行像卡方检验那样的统计学意义检验，以确定类的分布是否是不同的并且具有/不具有这种结构。当数据非常稀缺时，这些技术特别有用。然而，你应该怀疑有一种特定技术可“解决”过拟合的说。避免了过拟合（方差），却很容易落入了相反的误差，欠拟合（偏差）。同时避免两者都需要学习一个完美的分类器，在缺乏知识的情况下，没有唯一的技术可以永远做的最好（没有免费的午餐）。

关于过拟合的一个常见误解是，它是由噪声引起的，例如标记有错误类的训练样本。这确实可以加深过拟合，通过使学习者画一个反复无常的边界，以保持这些它自认为是正确的样本。但是即使在没有噪声的情况下也可能发生严重的过拟合。例如，假设我们学习一个布尔分类器，它只是训练集中标记为“真”的示例的分离。（换句话说，分类器是一个析取范式的布尔公式，其中每个项是一个特定训练样本的特征值的连接）。这个分类器得到所有的正确的训练样本和所有错误的积极的测试样本，而不考虑训练数据是否有噪声。

多重测试的问题与过拟合密切相关。标准统计检验假设只有一个假设正在测试，但现代学习者可以在他们完成之前轻松测试数百万数据。因此，看起来有意义的实际上可能没有意义。例如，一个连续十年打破市场的共同基金看起来非常令人印象深刻，直到你意识到，如果有1000个基金，每个基金在任何一年有50％的机会击败市场，很可能有一个将成功十次，这只是运气而已。这个问题可以通过纠正显著性检验来去考虑相当数量的假设来解决，但这可能导致欠拟合。更好的方法是控制错误接受的非零假设的分数，这称之为假发现率。

6.高维度下的直觉丧失

过拟合之后，机器学习中最大的问题是维度的诅咒。这个表达是由贝尔曼在1961年提出的，指的是当输入是高维时，许多在低维中工作的算法会变得棘手。但在机器学习中它指的是更多。 由于固定大小的训练集会导致输入空间逐渐减少覆盖，因此随着样本维度（特征数目）的增加，正确地泛化成指数地的难度增加。即使中等的维度为100的训练集和巨大的具有一万亿个样本的训练集，后者仅覆盖输入空间的大约10-18的部分。这就是为什么会使得机器学习既必要又困难。

更严重的是，机器学习算法共性的毛病是依赖（基于显式或隐式）在高维度上的分解。考虑hamming距离的k近邻分类器作为相似性度量，并假设该类只是x1∧x2。 如果没有其他特征，这是一个简单的问题。但是如果存在98个不相关的特征x3，...，x100，则来自它们的噪声完全可以在x1和x2中的信号进行求和，并且距离最近的样本可以有效地进行随机预测。

更令人不安的是，即使所有100个特征都相关，距离最近的样本仍然有问题！这是因为在高维度中，所有样本都相似。 例如，假设样本布局在规则网格上，并考虑测试样本xt。如果网格是d维的，xt的2D最近的样本都离它具有相同的距离。因此，随着维数的增加，越来越多的样本成为xt的最近邻，直到最近邻（以及类的）的选择是有效随机。

这只是高维度下一个更一般问题的一个实例：我们来自三维世界的直觉，通常不适用于高维度。在高维度中，多元高斯分布的大部分权重不是接近平均值，而是在它周围越来越远的“壳”; 并且大部分的高维度的橙色是在皮肤，而不是纸浆。如果恒定数量的样本均匀分布在高维超立方体中，再比他高一些的维度里大多数样本比它们最近邻更靠近超立方体的面。如果我们通过在超立方体中写入超球面来近似超球面，在高维度中，超立方体的几乎所有体积都在超球面之外。这是机器学习的坏消息，其中一种类型的形状通常由另一种的形状近似。

在二维或三维上构建分类器很容易; 我们可以通过可视化发现在不同类别的样本之间找到合理的边界。（甚至有人说，如果人们可以看到高维度，机器学习是没有必要的。）但在高维度很难理解发生了什么。这反过来使得设计一个好的分类器变得困难。原来，人们可能认为收集更多的特征从来就不会有事，因为在最坏的情况下，他们也不提供关于类的新信息。但事实上，他们的优点可能超过维度的诅咒。

幸运的是，有一个效应部分地抵消掉了诅咒，这可以被称为“非均匀性的祝福”。在大多数应用中，样本不是均匀地遍布整个实例空间，而是集中在较低维度的多面体上或其附近。例如，即使数字的图像每个像素具有一个维度，k-最近邻也能很好地用于手写数字识别，因为数字图像的空间比所有可能的图像的空间小得多。学习者可以隐含地利用这个较低的效率维度，或者可以使用用于显式地减少维度的算法

7.并非想像中的维度

机器学习论文充满了理论保证。最常见的类型是确保良好泛化所需的样本数量的界限。 你应该怎么做这些保证？首先，它是令人惊讶的，甚至他们存在可能。归纳在传统上与推理形成对照：在推理过程中，您可以保证结论是正确的; 在归纳中，所有赌注是关闭的。或许是几个世纪的传统智慧。 近几十年的主要发展之一是认识到，事实上，我们可以对归纳的结果有保证，特别是如果我们能够解决概率保证。

基本的论点非常简单。假设如果分类器的真实错误率大于ǫ，则它是坏的。然后，坏的分类器与n个随机，独立训练样本一致的概率小于（1-ǫ）n。令b是学习者假设空间H中的坏分类器的数量。通过联合界知至少其中一个一致概率小于b（1-ǫ）n。假设学习者总是返回一致的分类器，则该分类器是坏的概率小于|H|（1-ǫ）n，其中我们使用b|H|的事实。 因此，如果我们希望这个概率小于δ，它使得n> ln（）/ ln（1-ǫ）（ln|H|+ln）。

不幸的是，这种类型的保证必须有保留的。这是因为以这种方式获得的边界通常非常宽松。上述约束精彩的特征是所需数量的样本仅与|H|对数增长和1 /δ。不幸的是，最有趣的假设空间是特征数量d阶的双指数函数，这仍然使我们需要相当样本数量的d阶指数。例如，考虑d个布尔变量的布尔函数的空间。如果拥有e个可能不同的样本，就会有2e个可能不同的函数，因此有2d可能函数，总函数数为。即使对于“只是”指数的假设空间，界限仍然非常松散，因为联合界是非常悲观的。例如，如果有100个布尔特征，并且假设空间是具有多达10个水平的决策树，我们需要50万个样本去保证在上述约束中δ= ǫ = 1％。但在实践中，只有其中的小部分用于精确学习。

此外，我们必须小心思考边界是什么意思。 例如，并不是说，如果你的学习者返回一个符合特定训练集的假设，那么这个假设可能泛化得很好。准确而言是给定一个足够大的训练集，很可能你的学习者将返回一个泛化的很好或不能找到一个一致的假设的假设。边界也没有提供如何选择一个好的假设空间。它只告诉我们，如果假设空间包含真正的分类器，那么学习者输出不好的分类器的概率随训练集大小而减小。如果我们减少假设空间，改善边界，那么它包含真正的分类器的机会也缩小。（对于真实分类器的边界存在不在假设空间的情况，但是类似的考虑同样适用于它们。）

另一种常见类型的理论保证是渐近：在有限数据集中，学习者保证输出正确的分类器。 这是令人放心的，但由于其渐近的保证，选择一个学习者而不是另一个学习者会是轻率的选择。在实践中，我们很少使用渐近机制（也称为“渐近”）。并且，由于我们上面讨论的偏差 - 方差平衡，如果在给定的有限数据集中学习者A比给出的学习者B更好，B通常比A在给定的无限数据集中更好。

理论保证在机器学习中的主要作用不是作为实际决策的标准，而是作为算法设计的理解来源和驱动力。在这方面，他们是非常有用的; 确实，理论与实践的密切相互作用是机器学习多年来取得如此巨大进步的主要原因之一。 但是需要注意的是：学习是一个复杂的现象，仅仅因为学习者同时拥有理论上的支撑和实践中的可运行，而不是意味着前者是后者的原因。

8.关键在于特征工程

在一天结束时，一些机器学习项目成功了，一些失败了。是什么造成了这些差异？ 简单的来讲，最重要的因素是使用的特征。 如果你有许多独立的功能，每个都与类很好地相关，学习很容易。另一方面，如果类是一个非常复杂的特征的函数，你可能无法学习它。 通常，原始数据不是以适合学习的形式，但是你可以从它构造特征。 这通常占据机器学习项目中的大部分时间，通常也是最有趣的部分之一，其中直觉，创造力和“黑色艺术”与技术stuff一样重要。

初学者通常对机器学习项目花费在机器学习上时间之少感到惊讶。 但是，如果您考虑收集数据，整合数据，清理数据和对数据进行预处理以及在特征设计中可以进行多少试验和错误，这是很有意义的。此外，机器学习不是构建数据集和运行学习者的一次性过程，而是运行学习者，分析结果，修改数据和/或学习者并重复的迭代过程。学习通常是这方面最快的部分，但这是因为我们已经掌握的很好了！ 特征工程更加困难，因为它是特定领域，而学习者可以在很大程度上是通用的。 然而，两者之间没有分明的边界，这是最有用的学习者是能轻易结合知识的另一个原因。

当然，机器学习的一个圣杯是自动化越来越多的特征工程的处理过程。 这种方法今天经常进行的一种方式是自动生成大量的候选特征，并通过相对于类的（例如）信息增益来选择最佳。但请记住，在单独空间中看起来无关的特征可能是相关的。 例如，如果类是k个输入特征的XOR，则它们中的每一个本身不携带关于类的信息。 （如果你想惹恼机器学习者，提出XOR。）另一方面，运行一个携带大量特征的学习者，以找出哪些是有用的组合可能太费时，或导致过拟合。所以，没有一种最终没有可替代性的智能让你节省掉特征工程。

9.更多的数据打败了更聪明的算法

假设你已经构建了最好的特征集，但是你得到的分类器仍然不够准确。你现在能做什么？ 有两个主要的选择：设计一个更好的学习算法，或收集更多的数据（更多的样本，可能更多的原始特征，臣服于受到维度的诅咒）。机器学习研究者主要关注前者，但实际上，最快的成功之路往往是获得更多的数据。 作为一个经验法则，具有大量的哑算法和大量数据可以击败一个更聪明的算法。（毕竟，机器学习是关于让数据做主要工作的。）

但是这又带来了另一个问题：可扩展性。在大多数计算机科学中，两个主要的有限资源是时间和空间。 在机器学习中，有第三个：训练数据。无论哪一个瓶颈的改变都需要数十年的时间。在20世纪80年代，它往往是数据。今天经常是时间。有大量的数据可用，但没有足够的时间来处理它，所以它没有使用。这也导致了矛盾：即使原则上更多的数据意味着可以学习更复杂的分类器，在实践中更简单的分类器被使用，因为复杂的分类器花费太长时间来学习。 答案的一部分是提出快速的方法来学习复杂的分类器，并且在这个方向上已经取得了显着的进步。

使用更聪明的算法的部分原因可以比你预期的具有更小的回报，对于第一次近似而言，他们做的都一样的。 这是令人惊讶的，例如当你考虑将表示视为不同的规则集合和神经网络。但实际上命题规则容易编码为神经网络，并且其他表示之间存在类似的关系。 所有学习者基本上通过将附近的样本分组到同一类中来工作;关键差异在于“附近”的含义上。由于非均匀分布的数据，学习者可以产生广泛而不同的边界，同时仍然在重要的地区（那些具有大量的训练样本，因此也是大多数测试样本很可能出现的地方）。这也有助于解释为什么强大的学习者可能不稳定，但仍然准确。图3在2-D中展示出了这一点;该效应在高维度上更强。

作为一个规则，首先应该尝试最简单的学习者（例如，朴素贝叶斯之前的logistic回归，k近邻算法之前的支持向量机）。 更复杂的学习者是诱人的，但他们通常更难使用，因为他们有更多的参数，你需要调整来得到好的结果，并且因为他们的内部更不透明。

学习者可以分为两种主要类型：表示具有固定大小的那些，如线性分类器，以及其表示可以随数据一起增长的那些，例如决策树。 （后者有时被称为非参数学习者，但这是有点不幸，因为他们通常学习的参数比参数的更多）。固定大小的学习者只能利用这么多的数据。（注意图2中朴素贝叶斯渐近的精确度在70％左右。）大小可变的学习者原则上可以学习给定足够数据的任何函数，但在实践中他们可能不会，因为算法的限制（例如，贪婪搜索落入局部最优）或计算成本。此外，由于维度的诅咒，没有现有的数据量可能是足够的。因为这些原因，聪明的算法 - 那些能够充分利用数据和计算资源的算法 - 如果您愿意投入足够多的努力，通常最终会给予你回报。在设计学习者和学习分类器之间没有尖锐的边界;相反，任何给定的知识都可以在学习者中编码或从数据学习。因此，机器学习项目经常在结束时有一个学习者设计的重要组成部分，并且参与者需要有一些专业知识。

最后，最大的瓶颈不是数据或CPU周期，而是人类周期。在研究论文中，学习者通常在准确度和计算成本的度量上进行比较。人类的节省的精力和获得的洞察，虽然更难以衡量，但往往更重要。这有利于产生人类可理解输出的学习者（例如规则集）。充分利用机器学习的组织是那些具有基础设施的组织，这些组织使得许多不同的学习者，数据源和学习问题的实验变得容易和有效，以及机器学习专家和应用领域之间联系更加紧密。

10.学习许多模型，而不是一个

在机器学习的早期，每个人都有他们最喜欢的学习者，再掺杂上一些先验的理由从而相信它的优越性。大多数人都试图尝试许多版本，并选择最好的一个。然后系统的经验比较表明，最好的学习者随着应用实践的变化而变化，包含许多不同的学习者的系统开始出现。努力的重心现在是尝试众多学习者的许多版本，并仍然选择最好的一个。但是后来研究人员注意到，如果不是选择发现的最佳版本，而是我们结合了许多版本，结果更好 - 通常更好 - 并且对用户只需要一点额外的努力。

创建这样的模型集是现在的标准。在最简单的技术，称为装袋（bagging），我们简单地通过重采样生成训练集的随机变化，学习每个分类器，并通过投票（voting）结合结果。 这是因为它大大减少方差，而只是稍微增加偏差。 在boosting中，训练样本具有权重，并且这些权重是不同的，因此每个新的分类器都关注之前的样本。在stacking中，单个分类器的输出成为“更高级”学习者的输入，以确定如何最好地组合它们。

存在许多其他技术，并且趋势是朝向更大的集合。 在Netflix奖中，来自世界各地的团队竞相制作最好的视频推荐系统（http：// net fl ixprize.com）。 随着比赛的进行，团队发现他们通过将学习者与其他团队结合在一起，获得了最好的结果，并被合并成了更大的团队。获胜者和亚军都是超过100名学生的堆叠的团队，并结合两个团队进一步改善了结果。 毫无疑问，我们将来会看到更大的。

模型集合不应与贝叶斯模型平均（BMA）混淆。BMA是理论上学习的优化方法。在BMA中，通过对假设空间中所有分类器的个体预测进行平均来对新样本进行预测，通过分类器解释训练数据的程度以及我们相信它们的先验程度进行加权加权。尽管他们的超级相似，集合和BMA是非常不同的。集合改变假设空间（例如，从单个决策树到它们的线性组合），并且可以采取各种各样的形式。 BMA根据固定的公式对原始空间中的假设分配权重。 BMA权重与（例如）装袋（bagging）或增强（boosting）产生的BMA权重非常不同：后者是相当均匀的，而前者是非常不均的，直到单个最高权重分类器经常占据主导地位，使BMA有效等同的选择它。这样做的一个实际结果是，尽管模型集合是机器学习工具包的关键部分，BMA是很少有有价值的麻烦。

11.简单而不是精确的

有名的奥卡姆剃刀论述到实体不应该超越必要性。 在机器学习中，这往往意味着，给定两个具有相同训练误差的分类器，两者中较简单的可能具有最低的测试误差。这种说法的证据经常出现在文献中，但实际上有许多反例，“天下没有免费午餐”定理意味着它不是真的。

我们在上一节中看到了一个反例：模型集合。 即使在训练误差已经达到零之后，通过添加分类器，增强集合的泛化误差仍然得到了改善。 另一个反例是支持向量机，它可以有效地拥有无限数量的参数，而没有过拟合。相反，sign（sin（ax））可以区分x轴上任意大的任意标记的点集合，即使它只有一个参数。 因此，与直觉相反，模型的参数数量及其过拟合倾向之间没有必要的联系。

更复杂的视图代之以与假设空间的相同大小的复杂度，因为较小的空间允许假设由较短的代码表示。类似上述理论保证部分中的边界可能被视图化暗示着较短的假设泛化的更好。这可以通过为我们有一些先验偏好的空间中的假设分配更短的代码来进一步定义。 但是这可以视为是准确性和简单性之间的“证明”是循环推理：我们做出了假设，我们更喜欢简单的设计，如果他们是准确的，这是因为我们的偏好是准确的，而不是因为在我们选择的表示种假设是“简单的”。

进一步的复杂性产生于以下事实：少数学习者穷尽地搜索其假设空间。 具有更大假设空间的学习者尝试更少的假设，比从更小的空间尝试更多假设的学习者具有更少的过拟合。正如Pearl指出的，假设空间的大小只是粗略的指导对于相关的训练和测试误差真正重要的是：选择哪一个假设的步骤。

Domingos调查了关于机器学习中奥卡姆剃刀问题的主要论点和证据。结论是，更简单的假设应该是优选的，因为简单性本身就是一种美德，而不是因为与假设连接的精确性。这可能是Occam在第一个地方的意思。

13.表示不明确

基本上，可变大小学习器中使用的所有表示都具有“每个函数可以被表示或使用该表示来任意接近近似”形式的相关定理。由此表示的支持的粉丝经常进行忽略所有其他。然而，只是因为一个函数可以表示并不意味着它可以学习。例如，标准决策树学习者不能学习具有比训练样本更多的树的枝叶。在连续空间中，表示甚至是使用固定的一组基元的简单函数通常都需要无限数量的成分。此外，如果假设空间具有评估函数的许多局部最优值，通常情况下，学习者可能不能找到真实函数，即使它是可表示的。给定有限数据，时间和空间，标准学习者只能学习所有可能函数的一小部分，这些子集对于具有不同表示的学习者是不同的。因此，关键问题不是“它能代表吗？”，这个的答案往往是不值得关心的，但是“可以学习吗？”它值得不同的学习者去尝试（可能结合它们）。

对于某些函数，某些表示比其他表示在指数上更紧凑。因此，他们也可能需要呈指数减少的数据来学习这些函数。 许多学习者通过形成简单基函数的线性组合来工作。例如，支持向量机形成以一些训练样本（支持向量）为中心的内核的组合。 以这种方式表示n位的奇偶性需要2n个基函数。 但是使用具有更多层的表示（即在输入和输出之间更多的步长），可以在线性大小的分类器中对奇偶性进行编码。寻找方法来学习这些更深刻的表示是机器学习的主要研究前沿之一。

14.相关性不意味着因果性

相关性并不意味着因果关系的这一点经常发生，以至于它可能不值得一章。 但是，即使我们一直在讨论的那种学习者只能学习相关性，他们的结果通常被视为代表因果关系。这是不是错了？ 如果是这样，那么为什么人们做呢？

通常，学习预测模型的目的是使用它们作为行动指南。 如果我们发现啤酒和尿布经常在超市一起买，那么或许把啤酒放在尿布部分旁边会增加销售。（这是数据挖掘世界中一个着名的例子。）但是实际上能否做到这个实验的效果是很难分辨的。机器学习通常应用于观察数据，其中预测变量不在学习者的控制之下，也不是在实验数据的地方。一些学习算法可能从观测数据中提取因果信息，但它们的适用性相当有限。另一方面，相关性是潜在的因果关系的标志，我们可以使用它作为进一步调查的指南（例如，试图了解因果链可能是什么）。

许多研究人员认为因果关系只是一个方便的选择。 例如，物理法则中没有因果关系的概念。 是否存在因果关系是一个深刻的哲学问题，没有明确的答案，但机器学习者的实用点是两个。首先，无论我们称之为“因果”，我们都希望预测我们行动的影响，而不仅仅是可观察变量之间的相关性。 第二，如果你可以获得实验数据（例如通过随机分配访问者到一个网站的不同版本），那就尽管这样做。

14.结论

像任何学科一样，机器学习有很多很难实现的“民间智慧”，但是对成功至关重要。 本文总结了一些最突出的项目。 一个学习好地方是我的书“The Master Algorithm”，一个非技术的机器学习介绍。 有关完整的在线机器学习课程，请访问http://www.cs.washington.edu/homes/pedrod/class。 还有一个机器学习讲座的宝库在http://www.videolectures.net。广泛使用的开源机器学习工具包是Weka。快乐学习！