Question

回顾第5.1.3节，粗略地说，监督学习算法是给定一组输入x和输出y的训练集，学习如何关联输入和输出。在许多情况下，输出y很难自动收集，必须由人来提供“监督”，不过该术语仍然适用于训练集目标可以被自动收集的情况。

5.7.1　概率监督学习

本书的大部分监督学习算法都是基于估计概率分布p(y｜x)的。我们可以使用最大似然估计找到对于有参分布族p(y｜x;θ)最好的参数向量θ。

我们已经看到，线性回归对应于分布族

通过定义一族不同的概率分布，我们可以将线性回归扩展到分类情况中。如果我们有两个类，类0和类1，那么只需要指定这两类之一的概率。类1的概率决定了类0的概率，因为这两个值加起来必须等于1。

我们用于线性回归的实数正态分布是用均值参数化的。我们提供这个均值的任何值都是有效的。二元变量上的的分布稍微复杂些，因为它的均值必须始终在0和1之间。解决这个问题的一种方法是使用logistic sigmoid函数将线性函数的输出压缩进区间（0，1）。该值可以解释为概率：

这个方法被称为逻辑回归（logistic regression），这个名字有点奇怪，因为该模型用于分类而非回归。

线性回归中，我们能够通过求解正规方程以找到最佳权重。相比而言，逻辑回归会更困难些。其最佳权重没有闭解。反之，我们必须最大化对数似然来搜索最优解。我们可以通过梯度下降算法最小化负对数似然来搜索。

通过确定正确的输入和输出变量上的有参条件概率分布族，相同的策略基本上可以用于任何监督学习问题。

5.7.2　支持向量机

支持向量机（support vector machine，SVM）是监督学习中最有影响力的方法之一（Boser et al.，1992；Cortes and Vapnik，1995）。类似于逻辑回归，这个模型也是基于线性函数的。不同于逻辑回归的是，支持向量机不输出概率，只输出类别。当为正时，支持向量机预测属于正类。类似地，当为负时，支持向量机预测属于负类。

支持向量机的一个重要创新是核技巧（kernel trick）。核技巧观察到许多机器学习算法都可以写成样本间点积的形式。例如，支持向量机中的线性函数可以重写为

其中，x⁽ⁱ⁾是训练样本，α是系数向量。学习算法重写为这种形式允许我们将x替换为特征函数φ(x)的输出，点积替换为被称为核函数（kernel function）的函数k(x，x⁽ⁱ⁾)=φ(x)·φ(x⁽ⁱ⁾)。运算符·表示类似于的点积。对于某些特征空间，我们可能不会书面地使用向量内积。在某些无限维空间中，我们需要使用其他类型的内积，如基于积分而非加和的内积。这种类型内积的完整介绍超出了本书的范围。

使用核估计替换点积之后，我们可以使用如下函数进行预测

这个函数关于x是非线性的，关于φ(x)是线性的。α和f(x)之间的关系也是线性的。核函数完全等价于用φ(x)预处理所有的输入，然后在新的转换空间学习线性模型。

核技巧十分强大有两个原因：其一，它使我们能够使用保证有效收敛的凸优化技术来学习非线性模型（关于x的函数）。这是可能的，因为我们可以认为φ是固定的，仅优化α，即优化算法可以将决策函数视为不同空间中的线性函数。其二，核函数k的实现方法通常比直接构建φ(x)再算点积高效很多。

在某些情况下，φ(x)甚至可以是无限维的，对于普通的显式方法而言，这将是无限的计算代价。在很多情况下，即使φ(x)是难算的，k(x,x')却会是一个关于x非线性的、易算的函数。举个无限维空间易算的核的例子，我们构建一个作用于非负整数x上的特征映射φ(x)。假设这个映射返回一个由开头x个1，随后是无限个0的向量。我们可以写一个核函数，完全等价于对应的无限维点积。

最常用的核函数是高斯核（Gaussian kernel），

其中是标准正态密度。这个核也被称为径向基函数（radial basis function，RBF）核，因为其值沿ν中从u向外辐射的方向减小。高斯核对应于无限维空间中的点积，但是该空间的推导没有整数上最小核的示例那么直观。

我们可以认为高斯核在执行一种模板匹配（template matching）。训练标签y相关的训练样本x变成了类别y的模板。当测试点x/到x的欧几里得距离很小，对应的高斯核响应很大时，表明x'和模板x非常相似。该模型进而会赋予相对应的训练标签y较大的权重。总的来说，预测将会组合很多这种通过训练样本相似度加权的训练标签。

支持向量机不是唯一可以使用核技巧来增强的算法。许多其他的线性模型也可以通过这种方式来增强。使用核技巧的算法类别被称为核机器（kernel machine）或核方法（kernel method）（Williams and Rasmussen，1996；Schölkopf et al.，1999）。

核机器的一个主要缺点是计算决策函数的成本关于训练样本的数目是线性的。因为第i个样本贡献α_ik(x,x⁽ⁱ⁾)到决策函数。支持向量机能够通过学习主要包含零的向量α，以缓和这个缺点。那么判断新样本的类别仅需要计算非零α_i对应的训练样本的核函数。这些训练样本被称为支持向量（support vector）。

当数据集很大时，核机器的计算量也会很大。我们将会在第5.9节回顾这个想法。带通用核的核机器致力于泛化得更好。我们将在第5.11节解释原因。现代深度学习的设计旨在克服核机器的这些限制。当前深度学习的复兴始于Hinton et al.（2006b）表明神经网络能够在MNIST基准数据上胜过RBF核的支持向量机。

5.7.3　其他简单的监督学习算法

我们已经简要介绍过另一个非概率监督学习算法，最近邻回归。通常，k-最近邻是一类可用于分类或回归的技术。作为一个非参数学习算法，k-最近邻并不局限于固定数目的参数。我们通常认为k-最近邻算法没有任何参数，而是使用训练数据的简单函数。事实上，它甚至也没有一个真正的训练阶段或学习过程。反之，在测试阶段我们希望在新的测试输入x上产生y，我们需要在训练数据X上找到x的k-最近邻。然后返回训练集上对应的y值的平均值。这几乎适用于任何类型可以确定y值平均值的监督学习。在分类情况中，我们可以关于one-hot编码向量c求平均，其中c_y=1，其他的i值取c_i=0。然后，我们可以解释这些one-hot编码的均值为类别的概率分布。作为一个非参数学习算法，k-近邻能达到非常高的容量。例如，假设我们有一个用0-1误差度量性能的多分类任务。在此设定中，当训练样本数目趋向于无穷大时，1-最近邻收敛到两倍贝叶斯误差。超出贝叶斯误差的原因是它会随机从等距离的临近点中随机挑一个。而存在无限的训练数据时，所有测试点x周围距离为零的邻近点有无限多个。如果我们使用所有这些临近点投票的决策方式，而不是随机挑选一个，那么该过程将会收敛到贝叶斯错误率。k-最近邻的高容量使其在训练样本数目大时能够获取较高的精度。然而，它的计算成本很高，另外在训练集较小时泛化能力很差。k-最近邻的一个弱点是它不能学习出哪一个特征比其他更具识别力。例如，假设我们要处理一个回归任务，其中是从各向同性的高斯分布中抽取的，但是只有一个变量x₁和结果相关。进一步假设该特征直接决定了输出，即在所有情况中y=x₁。最近邻回归不能检测到这个简单模式。大多数点x的最近邻将取决于x₂到x₁₀₀的大多数特征，而不是单独取决于特征x₁。因此，小训练集上的输出将会非常随机。

决策树（decision tree）及其变种是另一类将输入空间分成不同的区域，每个区域有独立参数的算法（Breiman et al.，1984）。如图5.7所示，决策树的每个节点都与输入空间的一个区域相关联，并且内部节点继续将区域分成子节点下的子区域（通常使用坐标轴拆分区域）。空间由此细分成不重叠的区域，叶节点和输入区域之间形成一一对应的关系。每个叶结点将其输入区域的每个点映射到相同的输出。决策树通常有特定的训练算法，超出了本书的范围。如果允许学习任意大小的决策树，那么它可以被视作非参数算法。然而实践中通常有大小限制，作为正则化将其转变成有参模型。由于决策树通常使用坐标轴相关的拆分，并且每个子节点关联到常数输出，因此有时解决一些对于逻辑回归很简单的问题很费力。例如，假设有一个二分类问题，当x₂＞x₁时分为正类，则决策树的分界不是坐标轴对齐的。因此，决策树将需要许多节点近似决策边界，坐标轴对齐使其算法步骤不断地来回穿梭于真正的决策函数。

图5.7　描述一个决策树如何工作的示意图。（上）树中每个节点都选择将输入样本送到左子节点（0）或者右子节点（1）。内部的节点用圆圈表示，叶节点用方块表示。每一个节点可以用一个二值的字符串识别并对应树中的位置，这个字符串是通过给起父亲节点的字符串添加一个位元来实现的（0表示选择左或者上，1表示选择右或者下）。（下）这个树将空间分为区域。这个二维平面说明决策树可以分割。这个平面中画出了树的节点，每个内部点穿过分割线并用来给样本分类，叶节点画在样本所属区域的中心。结果是一个分块常数函数，每一个叶节点一个区域。每个叶需要至少一个训练样本来定义，所以决策树不可能用来学习一个局部极大值比训练样本数量还多的函数

正如我们已经看到的，最近邻预测和决策树都有很多的局限性。尽管如此，在计算资源受限制时，它们都是很有用的学习算法。通过思考复杂算法和k-最近邻或决策树之间的相似性和差异，我们可以建立对更复杂学习算法的直觉。

读者可以参考Murphy（2012）；Bishop（2006）；Hastie et al.（2001）或其他机器学习教科书了解更多的传统监督学习算法。