《机器学习与优化》试读：11.1 经验风险最小化

看上去是困难，事实上却是机会。 ——詹巴蒂斯塔􀀀维科 本书中各章节的次序在某种程度上是按照机器学习的历史发展排列的。① 在1980 年之前，大部分的学习方法集中于基于规则符号的专家系统，或精粒度亚符号的线性判别技术，这些技术都有着明确的理论属性。到了20 世纪80 年代，决策树和神经网络为非线性模型提供了有效的学习方法，但却缺少坚实的理论基础，而基于梯度下降的最优化技术也略显朴素。 到了20 世纪90 年代，得益于Vapnik 和Chervonenkis 的开创性工作，研究者为非线性函数建立了许多基于统计学习理论的有效学习算法。统计学习理论（SLT）解答了从数据中学习的根本问题：什么情况下一个模型可以从样本中学习？一个模型在一组样本上测得的性能是如何约束其泛化的性能的？ 这些理论结果是持久不变的，尽管这些定理的有效性在大部分的现实问题中几乎不可能得到验证。另一方面，这些研究人员计划复兴线性判别方法，他们为了加强模型的泛化能力，往线性判别方法中加入额外的优化目标，并把这种方法称作支持向量机（SVM）。 ------------------------------------------------------- ① Vapnik 教授的照片，来自 Yann LeCun 的网站“Vladimir Vapnik 与视频游戏亚文化的相遇”，http://yann.lecun.com/ex/fun/index.html#allyourbayes。 ------------------------------------------------------- SVM 听起来很专业，但其基本原理很容易掌握。考虑图11-1（左图）中的两类点（分别是灰色和白色），以及两条直线A 和B，它们都可以线性划分这些点，并分别是划分带标签训练数据这一常见机器学习方法的两种不同结果。当我们泛化划分结果时，就能发现这两种结果的不同之处。使用这个已训练好的系统时，新的样本来自与训练样本相同的概率分布，即两类点在图中的分布与训练样本类似，但是对于直线 B，样本点落入分类器错误一侧的概率会远大于直线 A。直线 B 离一些训练样本点很近，因此几乎不能分离这些点。而直线 A 离两类样本点的概率距离都是最远的，因此在它的附近有概率上最“安全的区域”，又称作间隔（margin）。SVM 就是具有最大可能安全间隔的线性分类器，其中的支持向量就是那些处于安全间隔两侧边缘的点（见图 11-1 右图）。其实，我们遇到过的最小二乘线性模型（见 4.3 节）和 SVM 很相似。最小二乘法最小化均方误差，而 SVM 最小化最大距离，不过二者的目标是一致的，都是为了得到类间健壮且安全的边界。 为了得到最大间隔线性分类器，通常使用标准二次规划，它可以在一定规模下解决此类优化问题。二次规划问题就是目标函数为二次函数、约束条件为线性的最优化问题。在多层感知器中存在的局部极小值问题 —— 由于局部极小值离全局最小值很远 —— 在二次规划中不会出现，因此可以放心使用 SVM。但众所周知，没有不带刺的玫瑰，如果训练样本不是线性可分的，那么 SVM 就会遇到很多问题。这种情况下，需要先对原始样本点做非线性的变换φ，从而将其变成（近似）线性可分的。可以将 φ 看作一个合适的特征生成函数，它使得变换之后的两类样本点 φ(x)是线性可分的。对于特定的问题，需人工生成特定的非线性变换，目前还没有通用的变换。 难道为了找到合适的 φ，还要重新做特征提取和特征工程？某种意义上是这样的，在使用φ 变换输入样本后，SVM 的特征就是要识别的样本和训练样本①之间所有的相似性值。SVM关键的一步就是，通过一些交叉验证的方式，人工确定最利于学习和泛化的相似度度量函数，其中就涉及核函数的选择。 ----------------------------------------------- ① 实际上只有支持向量才提供非零的贡献。 ----------------------------------------------- SVM 可以看作解决了两个问题：一方面，它找到了一个衡量输入向量之间相关性的合适方式，即核函数K(x, y)；另一方面，它构建了一个线性结构，该线性结构结合了训练样本的输出和新的测试样本，训练样本的输出用相似度来衡量。正如预期的那样，越相似的输入样本对输出的贡献越大，就像第 2 章中更原始的最近邻分类器一样，可以用类似下面的式子来描述： （􀀀 是训练样本的数量，yi 是训练样本 xi 的输出，x 是待分类的新测试样本。）这个式子在下面的理论描述中会再次出现。核在计算被函数 φ(x) 映射后数据点的点积（纯量积）时，实际上不用计算这个映射函数，这种方法被称作“核方法”（见图 11-2）： 一个包含一系列点对内核值的对称半正定格拉姆矩阵融合了数据和核的信息。① 为获得的数据而估计一个合适的具有最大泛化结果的核矩阵，这是一个正在开展的研究课题。 现在，SVM 的整体框架已经明确，下面就来深入数学的细节，其中有些细节非常复杂难解。幸运的是，使用 SVM 的时候，并不需要知道这些定理的证明，虽然了解主要的数学结果会帮助你更好地选择参数和核等。 11.1 经验风险最小化 之前提到过，最小化一系列样本的误差并不是一个合理的统计学习算法的唯一目标，也要考虑模型的结构。统计学习理论为基于观测的推导未知函数依赖关系提供了数学工具。 ------------------------------------------ ① 任何相似矩阵都可以被用作核，只需满足 Mercer 定理的条件。 ------------------------------------------ 统计学中的范式转换始于 20 世纪 60 年代：在此之前，基于费希尔在 19 世纪二三十年代的研究，研究者为了从观测样本中推导出函数依赖关系，必须了解所需依赖关系的详细形式，并且从实验数据中只能得到有限数量参数的值。而新的范式不需要详细了解依赖关系，并证明了一些未知依赖关系的函数集合的某些通用属性足以估计数据的依赖关系。非参数技术就是这些灵活模型的一种，研究者即使不了解输入–输出函数的详细形式也能使用该方法，例如之前的多层感知器（MLP）模型。 简单总结一下统计学习理论主要方法的要点，对于促进使用支持向量机（SVM）作为一个学习机制有巨大作用。令 P (x, y) 为抽样的未知概率分布，任务是学习映射 xi → yi，即得到函数 f(x, w) 的参数值。函数 f(x, w) 称作假设，集合 {f(x, w) : w ∈ W} 称作假设空间，记作 H，令 W 为抽象参数的集合。一个基于标记样本选择的参数 w ∈ W 就得到了一个“训练机”。 一个用于分类的训练机的期望测试误差或期望风险是： 一个基于经验风险最小化（ERM）原则的经典学习方法是：可以通过最小化经验风险 [式(11.2)] 来逼近函数 f(x, wˆ )，随后最小化期望风险 [式 (11.1)]，从而逼近函数 f(x, w∗)。 经验风险最小化的基本依据是：如果 Remp 依概率收敛于 R（由大数定律保证），那么Remp 的最小值可能收敛到 R 的最小值。如果这个依据不成立，那么经验风险最小化原则就被称作不一致。 Vapnik 和 Chervonenkis 指出，上述一致性成立，当且仅当 Remp 依概率收敛到 R 是一致的，即随着训练集的增加，Remp(w) 逼近 R(w) 的概率对于整个参数集合 W 一致地趋近 1。经验风险最小化的充要条件是假设空间 H 的 Vapnik-Chervonenkis 维（VC-dimension，VC维）是有限的。 一个假设空间的 VC 维，简单来说，就是能被函数集合 f(x, w) 分割成所有可能的两种类别的最大样本数。VC 维 h 描述了假设空间的复杂度和表达能力，通常与模型 f(x, w) 的自由参数的数量成正比。 Vapnik 和 Chervonenkis 规定了经验风险和期望风险之间偏离的界限，可以依概率 1 − p写成下式： 通过分析这个界限并忽视对数因子，为了得到较小的期望风险，我们要使经验风险和假设空间的 VC 维与训练样本数的比例 h/􀀀 变得很小。换句话说，要想在训练之后得到有效的泛化能力，就要使假设空间足够大，使得训练机经验风险较小，即能够正确训练样本，但假设空间又不能太大，否则会导致训练机仅仅简单地记忆训练样本，而没有提取出问题的结构。所以，为了得到更好的模型适应性，也需要更多的样本来实现类似的泛化水平。 尤其当样本数量有限制时，为了得到好的泛化效果，选择适当的 VC 维至关重要。 为了选择合适的 h 值的，Vapnik 在上述界限的基础上提出了结构风险最小化（structural risk minimization, SRM）的方法。对于 SRM 的原理，学习模型从一个嵌套的假设空间开始： 限制 w 的范数提供假设空间的约束的几何解释如下（见图 11-3）：如果 ||w||≤ A，那么从超平面 (w, b) 到最近的数据点的距离大于 1/A，因为只考虑与在每个数据点周围半径为 1/A的球不相交的超平面。在线性可分的情况下，最小化 ||w|| 来确定最大边界（两个训练类的凸包之间的沿着垂直于超平面测量的距离）的分离超平面。 这一问题可以形式化为：