2.2 可学习性

模型的学习可以分为两部分：结构和参数。结构由特定算法进行选择，通常是不可变的（除了在模型提供重新建模功能的情况下），而参数是优化的目标。考虑n个无界参数，共同组成一个n维空间（给参数加入边界约束将生成该空间的一个子空间）。在这个空间中，每个点与待估计函数的固定部分（以及参数的特定集合）共同构成参数学习的假设H：

参数学习过程的目标是找到预测误差最小、泛化能力足以避免过拟合的最佳假设。图2-1是一个数据集的示例，将其中的点划分为红色（A类）或蓝色（B类）。当前有三个假设：第一个（从左边开始的中间的线）错误分类了3个样本，而下面和上面的线分别错误分类了13和23个样本。

很显然，第一个假设最优，应该被优先选择。但是另一方面，了解可能存在的过拟合的基本概念是非常重要的。考虑一个n维二分类问题。如果存在一个超平面，它将空间分成两个子空间，每个子空间仅包含属于同一类的样本，那么我们说数据集X是线性可分的（不进行变换）。去除线性约束，我们有无限个可替代的一般超平面。然而，参数模型仅采用非周期性和近似函数的族，其振荡和拟合数据集的能力（有时以非常复杂的方式）是由参数数量确定的。

考虑图2-2所示的例子。

蓝色分类器是直线，而橘红色分类器是一条非线性的三次曲线。很显然，非线性策略似乎表现得更好，由于非线性策略的凹性，该策略可以有更好的分类效果。但是，如果按照最后四个（从右边）定义的趋势添加新样本，则用非线性策略进行分类将是完全错误的。事实上，线性函数的整体表现更好，但不能反映出第0到第4个样本所表现出的振荡特性，而三次非线性曲线几乎可以完美地分类这部分数据，但却失去了保持整体线性趋势的能力。基于以上分析，有两种可能性：

如果将来的预测数据具有和训练样本一样的分布，复杂的模型可以捕获较低阶模型可能丢弃的小的变化，其可能是一个很好的选择。而在这个例子中，线性（或较低阶）模型可能导致欠拟合，因为它无法精确地表现出数据的小的趋势。

如果将来的预测数据与训练样本局部分布可能不同，那么为保持整体趋势，则最好选择具有较高残余错误分类误差以及更好泛化能力的模型。使用仅关注训练数据的复杂模型可能会导致过拟合。

2.2.1 欠拟合和过拟合

机器学习模型的目的是找到将输入数据与输出数据近似关联的未知函数（对于分类器，我们称之为类）。虽然训练集通常表示样本的全局分布，但该集合不包含所有可能的数据，否则该问题可以通过一对一关联得到解决。同样地，我们不知道可能的函数的解析表达式，因此在训练时有必要考虑拟合模型，在未知输入时保持模型能够实现泛化。在这方面，引入模型的表征能力的概念是有用的，因为它能够在数据集上学习少量/大量可能的分布。显然，模型的低表征能力通常与较简单的模型相关联，例如无法解决非线性问题，而高表征能力（既是基础模型的函数又是参数的函数）将导致更复杂的分离超平面。考虑上一节中的最后一个例子，很容易理解线性分类器等效于线性等式：

在这种情况下，有两个参数，m和q，曲线永远不会改变其斜率（由m定义）。相反，第二个分类器可以想象为一个三次方程：

现在，我们有四个参数和两个输入值的幂。这些条件允许对可以改变其斜率两次的函数进行建模，并且可以适应更复杂的场景。显然，我们可以通过考虑通用多项式函数来继续这种分析：

复杂性（以及因此的容量）与p度成比例。加入多项式和非线性函数，我们可以获得极其复杂的表示（例如使用神经网络实现的表示），这些表示可以足够灵活地捕获非一般数据集的细节。但是，重要的是要记住增加容量通常是不可逆的操作。换句话说，更复杂的模型总是会更复杂，即使更简单的模型可取。学习过程可以拉伸或弯曲曲线，但它永远无法消除斜率变化（有关更完整的解释，请查看《Mastering Machine Learning Algorithms》）。这种情况会导致两种不同的潜在危险。

欠拟合：意味着可能是因为数据量有限，模型无法得到训练集所呈现出的特征。

过拟合：模型拟合能力过剩，但由于过多考虑数据的变化而导致泛化能力不足。模型可以将所有已知样本几乎完全关联到相应的输出值，但是当出现未知的输入时，相应的预测误差可能非常高。

图2-3显示了具有较少数据（欠拟合）、正常数据（正常拟合）和过量数据（过拟合）的例子，其中橘红色曲线代表实际的模型，蓝色曲线代表拟合后产生的模型。

欠拟合的模型通常具有高偏差，偏差被定义为参数θ的估计值与真实值之间的差值：

当偏差为零时，模型被定义为无偏。另一方面，偏差的存在意味着算法不能学习θ的可接受的表示。在图2-3的第一个例子中，直线在两点（约0.3和0.8）的邻域中只有一个可忽略的误差，并且由于直线的斜率不改变，偏差将迫使误差在其他地方增加。相反，过拟合通常与高方差相关，其定义如下：

高方差是高表征能力的结果。该模型现在能够改变并多次变化其斜率，但它不再是原来的简单表示。图2-3中的右侧示例显示了极其复杂的曲线，可能无法对大多数从未见过的样本进行分类。考虑到预测误差，欠拟合更容易检测，而过拟合可能更难以发现，因为它最初可能被认为是完美拟合的结果。事实上，在分类任务中，高方差模型可以很容易地学习到训练阶段使用的数据集的结构，但是，由于过度的复杂性，它可能变得很特殊。这通常意味着它将以较低的准确度预测从未见过的样本，因为这些特征不能被识别为属于哪一个类别。模型捕获每个小的变化，现在可以更自由地调整其分离面，因此相似性（这是泛化能力的基础）更难以被检测到。我们将在以下章节中讨论的交叉验证和其他技术可以较容易地显示模型如何与在训练阶段与从未见过的测试样本一起工作。这样，就可以在更广泛的情况下评估泛化能力（不是处理所有可能的值，而是始终使用应该反映原始分布的子集）并做出最合理的决策。请读者记住，机器学习模型的真正目标不是过拟合训练集（我们将在第3章中讨论这个），但是要使用新样本，在进入生产阶段之前有必要注意性能指标。

2.2.2 误差度量和成本函数

一般来说，在使用监督样本时，我们会定义一个非负的误差值em，它包含了期望输出yi和预测输出，整个数据集（由N个样本组成）的总误差和可以通过下式计算：

基于样本集上的期望输出和预测输出的误差和取决于隐含的具体假设H，因此，对误差和的优化意味着找到最优的假设。考虑到具体的优化问题，误差和可能不是最好的估计函数，但最少是可接受的近似评价。很多情况下，一般会考虑均方误差（Mean Square Error，MSE）：

其初始值表示最初要优化的函数表面的n个点。通用的训练算法必须找到该指标的全局最小值或与之非常接近的点，为避免过多的迭代次数和随之而来的过拟合风险，一般会有一个松弛量。该指标也被称为损失函数（Loss Function）或成本函数（Cost Function），通过优化问题的求解来最小化损失函数。当优化方法易于对最大化问题进行求解时，相应的损失函数将是它的倒数。

另一个有用的损失函数称为0-1损失（zero-one-loss），对于二分类（如一对多策略）特别有效：

该损失函数是隐含的一个指标，可以很容易地使用在基于错误分类概率的损失函数中。

通用（和连续）损失函数还可以从潜在能量的角度来解释：

预测函数就像一个粗糙表面的球，总是从能量（相当于误差和）相当高的随机点开始移动，直到达到其能量为零的稳定平衡点（相对于全局最小值）。图2-4是在球移动过程中可能遇到的不同情况的示意图。

与在物理场中类似，当起始点在没有任何外部扰动时是稳定的。因而，要让球开始滚动，需要为它提供初始的能量。然而，如果这个能量太大，那么当球沿着斜坡下降后，不能停在全局最小点，剩余的能量会使球越过山岭到达右面的山谷。如果没有其他能量，球就会被困在平坦的山谷，不能再移动了，这就是优化问题的局部最小化。当然，很多技术已经被提出来避免局部最小化问题。另一个常见问题（特别是在使用深度模型时）由鞍点表示，其特征在于零梯度和半正定Hessian矩阵。这意味着该点既不是局部最小值，也不是最大值，但它可以表现为在一个方向上移动的最小值，并且像最大值一样在另一个方向上移动。在图2-5中，我们可以看到这样的三维示例。

必须始终仔细分析每种情况，以了解可接受的剩余能量（或误差）的水平，或采用不同的策略是否更好。特别是，所有明确基于损失/成本函数的模型通常可以使用不同的优化算法进行训练，这些算法可以克服简单的解决方案无法解决的问题。我们将在接下来的章节中讨论其中的一些内容。

2.2.3 PAC学习

很多情况下，机器学习似乎可以完美地工作。但是，如何定义可学习的概念？1984年，计算机科学家L.Valiant提出了一种数学方法来确定问题对于计算机来讲是否可学习。这种技术称为PAC，或者称为可能近似正确（probably approximately correct）。考虑一个分类问题，PAC（见A Theory of the Learnable）基于特定的假设，在这个分类问题中当没有大的精度损失时，算法A需要学习一组概念。特别地，该组概念是确定相同输出数据的输入模式X的子集。因此，学习概念意味着最小化特定类的损失函数，同时学习所有可能的概念（属于同一个域）意味着找到全局损失函数的最小值。

然而，对于一个给定的问题，可能的假设有很多，甚至在理论上是无穷多的假设，此时需要进行概率的权衡。因此，可以接受基于有限数量的输入数据并以多项式时间产生的高概率的良好近似。因此，如果能够通过复杂度为O（nk）的程序找到假设H，从而使A以概率p将所有模式在最大允许错误me时正确地分类，那么算法A被认为可以学习类C的所有概念。当然，这必须对X上的所有统计分布以及大于或等于仅依赖p和me的最小数目的多个训练样本是有效的。

对计算复杂度进行约束是很重要的。事实上，即使当问题相当复杂时，我们也期望算法能够在合理的时间内有效地进行学习。当数据集很大或者优化的初始点远离可接受的最小值时，可能导致指数级增长的计算时间，从而导致计算量的爆炸。特别是维数灾难（curse of dimensionality）现象的出现，在训练或预测时间与维数成比例（通常不是线性的）的某些模型中经常发生。当这种现象出现时，意味着特征数量增加，模型的性能剧烈下降，所以减少输入的维数在避免维数灾难时是很有效的。此外，很多情况下，为了获得完整的表现力，有必要拥有一个非常大的数据集，没有足够的训练数据，这种近似可能会有问题，这就是所谓的休斯现象（Hughes phenomenon）。基于此，寻找多项式时间的算法不仅仅是简单的努力，而是可以确定机器学习成败的关键因素。因而，接下来的章节中将介绍一些可用于有效降低数据集维度但不会有任何信息丢失的技术。