3.4 统计学习的全面胜利

3.4.1 VC维

1971 年，苏联数学家 弗拉基米尔·N.瓦普尼克（Vladimir N. Vapnik） 和 阿列克谢·切尔沃年基斯（Alexey Chervonenkis） 提出了统计学习理论，而其中最重要也是最核心的概念就是 瓦普尼克-切尔沃年基斯维度（Vapnik-Chervonenkis dimension，VC维）。

免争议小Tips：VC维最早提出是在1971年的论文 On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities 中首次提出

假设有以下两个场景，我们要让机器人识别猫和狗。

• 场景 1：所有有尖耳朵的都是猫。
• 场景 2：毛色是橘黄色、左眼有一个小黑点、尾巴上有 3 个环纹、喜欢在下午 3 点晒太阳的是猫.

当我们使用场景 1 判断猫狗时，由于太过简单，所以很容易出错，因为有些狗也有尖耳朵，有些猫没有尖耳朵。当我们使用场景2判断猫狗时，虽然可以精准识别某只特定的猫，但是对其他猫狗都没啥用，因为这些特征太具体了，只适用于某一只动物。

那么如何衡量这个”判断标准“的复杂度，就可以用 VC 维表示，我们可以把它简单理解为机器学习中衡量模型“智商”的指标。

再举个例子，想象我们要使用一条直线将二维平面上的红点、黑点分开（如图 3-8 所示）：

• 当平面有 1 个点时，显然可以轻松用直线分开不同颜色的点（点的一侧画线即可）。
• 当平面有 2 个点时，无论这 2 个点在哪个位置，都可以用一条直线分开不同颜色的点。
• 当平面有 3 个点时，抛开 3 点共线（即忽略3点在一条直线的情况），无论 3 点在哪个位置，都可以用一条直线分开不同颜色的点。
• 平面有 4 个点时，假如存在对角线的黑红标记方式，用一条直线永远无法分开不同颜色的点（同图 3-8 所示的异或问题）。

图 3-8 直线分类器示意图

据此我们可以得出结论，直线分类器的 VC 维等于 3，因为只能完美处理任意 3 个点的分类，超过 3 个点直线分类器就会出现无能为力的情况。

如果我们不用直线，而是使用更复杂的曲线分类，显然它的 VC 维更高。

准确来说，VC 维衡量的是模型的表达能力和泛化能力，表达能力指的是模型拟合复杂数据的能力，类似于“智商上限”。泛化能力指的是在新数据上的表现能力，也就是“举一反三”的能力。VC 维比较低时，模型很简单，例如上文识别猫狗的例子中“所有的尖耳朵都是猫”，它泛化能力很不错，因为无论针对什么样的新数据，都可以通过识别尖耳朵特征来判断猫狗。但是它的表达能力不行，因为很明显一只尖耳朵的狗也会被识别成猫。简单来说就是易泛化、欠拟合（模型过于简单，基于这些特征的判断表现误差和泛化误差都高）。

VC 维比较高时，模型比较复杂，例如上文之前识别猫狗的例子中“毛色是橘黄色、左眼有一个小黑点、尾巴上有3个环纹、喜欢在下午 3 点晒太阳的是猫”，它的表现能力相当不错，因为基于这些特征确实可以准确判断出已训练数据中的猫，但是泛化能力很差，因为一旦有新的猫狗数据让它识别，这些特征就“不好使”了，有点“死记硬背”的意思。简单来说就是强表达、过拟合（模型过于复杂，新数据的识别会“死记硬背”训练样本中的特征，样本数据表达误差低，但泛化误差会很大）。

因此，如何平衡模型的 VC 维，要看数据的复杂度，例如如线性数据使用低 VC 维即可，复杂数据就需要高 VC 维。而在高 VC 维模型中，为了避免泛化能力差（死记硬背），最优解就是提升训练数据量，只要训练数据量足够大，泛化能力就可以得到提升。用数学不等式表示如下：

VC 维越大，模型表达能力越强，但需要更多样本。样本数越多，泛化误差越接近训练误差。

有了 VC 维这个坚实的理论基础，瓦普尼克并没有止步于纸面上的数学公式。他开始思考一个关键问题：

能否设计出一个算法，既有强大的表达能力，又能严格控制 VC 维，从而在理论上保证良好的泛化性能？

3.4.2 支持向量机（SVM）

基于 VC 维理论，瓦普尼克又提出了 支持向量机（support vector machine，SVM），这是统计学习理论的完美体现。它既是一种理论，又是一种算法，SVM 不像 VC 维那样，画一条直线随便找一个能分离数据的分界面，而是要找到最优的分界面。

想象我们在二维平面上分离红黑点，用VC维方法就是找到一条可以分开两种颜色点的直线，无论直线在哪里都可以。而使用SVM则是要找到一条距离两类都最远的线。为什么是距离两类都最远的线？我们先看图 3-9。

图 3-9 线性可分 SVM 示意图

你觉得图 3-9 所示的 h1 绿色线和 h2 灰色线，哪一条是 SVM 最优分界线？正确答案是 h1，因为它符合 SVM 定义中“距离两类都最远的线”的定义，SVM 中称此为“最大间隔超平面”，超平面就是那条线。

为什么会是最远呢？难道不是越近越好吗？

其实选择距离最远的线是为了最大化模型的泛化能力，泛化能力我们上文中有介绍过，可以简单理解为模型在新数据上的表现能力。

h1 绿色线距离两类数据点都比较远，可以形成比较宽的“缓冲带”，我们称之为 “硬间隔”（hard margin），这样即使新数据稍微有些偏移，也可以被正确分类；而h2灰色线与最近的数据点只有很小的间隔，一旦新数据有一些噪声（无关或者干扰性信息），就很可能会被错误分类。我们可以简单理解为间隔距离越小，模型的想象空间越小。

现实中会有排列这么整齐等着被分割的数据类吗？在上面的示例中，我们假设训练数据是严格线性可分的，也就是存在一个超平面可以完全分割两类数据。但是，现实中的训练数据肯定不会这么整齐，解决这个问题的方法是允许 SVM 在少量样本数据上出错，也就是将之前的硬间隔最大化条件放宽一些，允许少量样本数据不满足约束，我们称之为 “软间隔”（soft margin）。

图 3-10 线性 SVM 示意图

OK，前文介绍的都是线性问题，如果我们遇到了非线性的问题怎么办？这就不得不提到我认为 SVM 中最巧妙的点了，它就是 “核技巧”（kernel trick）。核技巧的思路是使用映射，将原空间的数据映射到新空间（比如把二维平面数据映射到三维空间，如图 3-11 所示），然后在新空间里用线性方法从训练数据中得到模型。

图 3-11 非线性 SVM 示意图

关于如何把原空间数据映射到新空间，这超出了本书的讨论范围，有兴趣的同学可以自行了解。

SVM 是统计学习理论从纸面走向现实的重要里程碑，它的成功鼓舞了整个机器学习社区，让人们看到了统计方法的巨大潜力。这种成功很快就辐射到了其他领域，特别是自然语言处理。研究者开始意识到，传统基于规则的方法可能并非唯一选择，统计方法或许能够带来新的突破。

3.4.3 基于统计的自然语言处理

自然语言处理（natural language processing，NLP） 是人工智能的一个重要分支，目标是让计算机能够理解、处理和生成人类的自然语言。与编程语言不同，自然语言充满了歧义、语境依赖和文化背景，这使得 NLP 成为人工智能领域最具挑战性的问题之一。

前文我们介绍过，20 世纪 50 年代的早期机器翻译中，使用的是逐词翻译，局限性很大，问题有很多。早期的对话系统ELIZA聊天机器人模拟心理医生对话，使用的是模式匹配方法，匹配到某个词汇，然后针对词汇进行回答，这是早期 NLP 的探索阶段。

随着符号主义的兴起，依赖规则的方法成为 NLP 的主流方法。

• 词法： 用规则识别词汇边界和词性。
• 句法： 用语法规则分析句子结构。
• 语义： 用逻辑规则理解句子含义。

那时的机器翻译使用双语词典和转换规则在语言之间进行转换。这种方法需要语言学家花费大量时间手工编写规则，整个翻译系统十分复杂并且覆盖面有限，遇到新的语言现象就需要添加新规则，维护成本极高。

我们举例看看传统的依赖规则的方法，来看下面这句话：

“我看见了一个人用望远镜”

首先进行词法分析：

我（代词）+ 看见（动词）+ 了（助词）+ 一个（数词）+ 人（名词）+ 用（动词）+ 望远镜（名词）

接着开始分析句法句式，这需要语言学家编写大量的规则，如：

• 规则 1—— 代词 + 动词 + 了 → 完成时态的动词短语；
• 规则 2 —— 数词 + 名词 → 名词短语；
• 规则 3 —— 动词 + 名词 → 动词短语；
• 规则 4 —— 名词短语 + 动词短语 → 句子成分。

问题来了，按照上面的规则，系统会生成两种不同的语法树，机器无法确定“用望远镜”到底修饰的是“看见”还是“人”，那么就会有两种意思：

• 我（用望远镜）看见了一个人；
• 我看见了一个人（这个人在用望远镜）。

这个时候就需要第3步——语义消歧，语言学家需要再编写一些消除歧义的规则，如：

• 如果前面有表示“视觉”的动词，“用望远镜”要倾向于修饰动词；
• 如果“用”后面的名词是工具类，倾向于修饰最近的动作。
• ……

到这里，传统的依赖规则的方法就处理完了这句话，可以想象，随着语言越来越复杂，这些规则会变得极其庞大，还会互相冲突。面对着早期机器翻译系统需要语言学家花费数年编写复杂的语法规则，世界上有这么多种语言，总不能每种语言都找对应的专家花很长时间去编写规则，而且自然语言充满了歧义、语境依赖和文化背景，每天还在有新词、新句的诞生，规则将无穷无尽。

因此，IBM 想到让机器从大量双语对照文本中自动学习翻译规律。随着统计方法论的不断突破，1990 年，IBM 团队做了一个在当时看起来异想天开的决定——完全抛弃语法规则，用统计方法做机器翻译。这个决定改变了整个 NLP 领域， 统计机器翻译（statistical machine translation，SMT） 进入大众视野。

简单来说，IBM 的想法就是给定一个英文句子 E，然后找到最可能匹配的中文句子 F，数学公式如下：

这个公式是不是很熟悉。没错，它也是基于贝叶斯定理的，其中：

• P(F|E) 是给定英文句子 E 时，中文句子 F 的条件概率；
• P(E|F) 是翻译模型，表示中文句子 F 翻译成英文句子 E 的概率；
• P(F) 是语言模型，表示中文句子 F 本身的合理性概率。

这种方法完全不需要语言学家编写复杂的规则，而是让机器从大量的双语文本中自动学习统计规律。

举个具体的例子，我们看这样一句话（英译中）：

“I like apples”

首先翻译模型，也就是词对齐，从大量语料中学习单词的对应关系，计算翻译概率，比如：

• P(喜欢∣like)=0.9（“like”翻译成“喜欢”的概率）
• P(苹果∣apples)=0.8

接着语言模型，也就是统计中文句子合理性概率：

• “我喜欢苹果”在中文语料中出现的概率为5%；
• “苹果喜欢我”在中文语料中出现的概率为1%。

最后套用公式，计算整体概率：

• “我喜欢苹果”=P(I like apples∣我喜欢苹果)×P(我喜欢苹果)=0.9×0.8×0.05=0.036；
• “苹果喜欢我”=0.9×0.8×0.001=0.00072。

对比概率得出结论，“I like apples”的翻译大概率是“我喜欢苹果”。

1993 年，IBM 的 CANDIDE 系统首次将统计模型引入机器翻译，验证了数据驱动统计方法的可行性，它的翻译质量超过所有基于规则的机器翻译系统，开发时间也从数年缩短到数月，而且非常容易扩展新语言，其美中不足的是需要大量语料库数据，当时的计算能力也不是很好，但统计机器翻译的出现无疑让 NLP 的发展进入了高速通道。

3.4.4 N-Gram 语言模型

前文简单介绍了 IBM 基于统计的机器翻译理念，实际上，IBM 统计机器翻译的成功离不开一个重要的技术 —— n元语法（n-gram）。n-gram 是一种基于马尔可链的统计语言模型，在当时应用比较广泛。前文介绍 IBM 的机器翻译理念的示例中，将整个翻译系统流程划分为 3 步，其中第二步语言模型的作用就是判断句子的合理性概率。对句子合理性的判断就是基于 n-gram 完成的。

n-gram 的核心逻辑很简单：一个词出现的概率只依赖于它前面的 n-1 个词。

• 当 n=1 时，称为 “一元语法”（unigram，1-gram），在这种情况下会忽略上下文，直接计算句子中每个词本身出现的概率。
• 当 n=2 时，我们可以叫它 “二元语法”（bigram，2-gram），在这种情况下，会根据前一个词计算当前词出现的概率。
• 当 n=3 时，我们可以叫它 “三元语法”（trigram，3-gram），在这种情况下，会根据前两个词计算当前词出现的概率。

名词术语介绍起来总是那么枯燥，它的原理其实很简单，我们举个例子来进一步理解 n-gram 的原理。

想象一下我们有一个包含了 100 万个词的语料库，我们要分析”我喜欢苹果“这句话的概率。

首先进行分词，将“我喜欢苹果”这句话分为“我”“喜欢”“苹果”这 3 个词。

然后计算每个词在语料库中的出现频率，这其实就是 1-gram：

• 假设“我”在语料库中出现了 15 万次，频率=15万/100万=0.15；
• 假设“喜欢”在语料库中出现了 8 万次，频率=8万/100万=0.08；
• 假设“苹果”在语料库中出现了 3 万次，频率=3万/100万=0.03。

那么，“我”后面出现“喜欢”、“喜欢”后面出现“苹果”的概率有多高？

• 假设“我喜欢”这个词对出现了 6 万次，频率=6万/100万=0.06
• 假设“喜欢苹果”这个词对出现了 2 万次，频率=2万/100万=0.02

因此：

• P(喜欢|我)=6万/15万=0.4，也就是“我”后面出现“喜欢”的概率是 40%；
• P(苹果|喜欢)=2万/8万=0.25，也就是“喜欢”后面接“苹果”的概率是 25%。

这就是 2-gram。

按照 2-gram，我们希望整个句子的概率计算使用统一的历史长度（即每个词都基于前一个词），但句子的开头部分也就是“我”前面没有词，所以我们需要从低阶开始，这种策略称为 “回退”（backoff）。

最终，“我喜欢苹果”的概率为：

P(我喜欢吃苹果) = P(我) × P(喜欢|我) × P(苹果|喜欢) = 0.15 × 0.4 × 0.25 = 0.015

最终 1.5% 这个概率值就是语言模型基于当前具有 100 万个词的语料库对这句话自然度的统计结果。

上述示例比较简单，不需要使用 3-gram。如果一定要使用 3-gram，那么我们要先计算“我喜欢苹果”这句话的总频率。

假设“我喜欢苹果”在语料库中出现了 0.6 万次，频率=0.6万/100万=0.006。

因此，P(苹果|我,喜欢)=0.6万/6万=0.1，也就是说“我喜欢”之后出现“苹果”的概率是 10%。

按照 3-gram，每个词出现的概率都基于前两个词出现的概率进行计算。由于历史不足，仍然需要回退，从低阶开始。

最终，“我喜欢苹果”的概率为：

P(我喜欢吃苹果) = P(我) × P(喜欢|我) × P(苹果|我,喜欢) = 0.15 × 0.4 × 0.1 = 0.006

注意，本节主要介绍 n-gram 的概念，计算过程不是很严谨。如果更严谨一点，我们还需要为“我喜欢苹果”这句话添加起止标记，整句话则变成“我喜欢苹果”，起止标记也会作为词来参与计算，这一点读者了解即可。

从上文中可以发现，使用 3-gram 计算得到的概率比使用 2-gram 计算得到的概率小很多。这是因为 2-gram 只需要考虑前一个词，而 3-gram 需要考虑前两个词。假如语料库中有一个“他喜欢苹果”的句子，那么这个句子在使用 2-gram 时就会被命中，但是在使用 3-gram 时就不会被命中。因此，3-gram 的匹配概率更精准。

但是，这并不意味着 3-gram 一定比 2-gram 好。这要分情况讨论，这个例子并不单是使用“纯” 3-gram 或“纯” 2-gram，而是一种混合策略，不依赖于一个固定的阶数，比较常见的混合策略有“回退”和“插值”，这个例子中使用的就是回退策略，数据不足时借助低阶（短历史）统计信息，这是比较常规的做法。

假如我们使用真正意义上的“纯” 3-gram，就会面临一个致命弱点——数据稀疏性。还以“我喜欢苹果”举例，假如语料库中并没有完全命中“我喜欢苹果”的句子，那么使用“纯” 3-gram时，“我喜欢苹果”的出现频率就是 0，但显然“我喜欢苹果”是一个合理的句子，结果为 0 并不合理。在这种情况下，如果使用“纯” 2-gram，由于可以匹配到“我喜欢”以及“喜欢苹果”，那么使用“纯” 2-gram计算得到的“我喜欢苹果”的概率要使用“纯” 3-gram计算得到的概率更高。语言的组合爆炸特性导致可能的三元组数量极其庞大，即使是大语料库（如 1 亿词），绝大部分可能的三元组从未出现过（ 0 频），或者在语料库中只出现非常少的次数（低频统计不可靠）。

假如我们使用真正意义上的“纯” 2-gram，也会面临一个致命弱点——语言歧义。我们看这样两句话：“我买苹果”“我看苹果发布会”，这里的“买苹果”“看苹果”都是合理的双词组合，“纯” 2-gram 方法会认为这两个句子中的“苹果”含义相同，那么统计“苹果”的出现频率时，这两个句子中的“苹果”都会被统计到。但是，这个数据是不准确的，因为正常情况下“我看苹果发布会”中的“苹果”指的是“苹果”公司。这个时候如果我们使用“纯” 3-gram，那么计算得到的概率就会更精准，因为三元组依赖更多长历史信息。

因此，我们不需要考虑使用哪种方法更好，因为在现实场景中使用 n-garm 语言模型，肯定不会只用一个阶数，而是使用混合策略，“我喜欢苹果”这个例子中使用的回退策略也只是混合策略的一种。