16  机器学习与大数据

16.1 简介

近年来，数据的激增以及快速计算能力的提升，催生了多种估算概率的技术，这些技术较少依赖于假设特定的数据模型，而更多地利用海量历史数据。这类技术通常被称为机器学习（machine learning）。本章将介绍几种流行的机器学习技术。

在 章节 16.2 中，我们引入了一个原型模型：在拥有大量历史数据的情况下，估算某架特定的跨国航班晚点到达目的地的概率。我们假设任何单次航班都可以由一个值组成的“特征向量”来描述，该向量的分量在性质上是定性描述性的。

随后的章节将介绍估算此类概率的方法。在 章节 16.3 中，我们引入了朴素贝叶斯（naive Bayes）方法，该方法尝试通过将晚点概率写为给定航班特征下的条件概率来对其进行估算。接着，利用贝叶斯定理，在满足关于特征向量分量独立性的特定假设时，我们可以得到该概率的表达式，且其中的各部分均可被估算。在 章节 16.3.1 中，我们给出了一种改进的朴素贝叶斯方法，当独立性假设明显不成立时，该方法可以提高估算精度。

在 章节 16.4 中，我们引入了“最近邻”规则。这些规则利用历史数据集中那些特征向量与目标航班特征向量接近的数据，来估算目标航班晚点的概率。要使用此类规则，首先要为每一个历史数据定义其特征向量与目标航班特征向量之间的距离。然后，该规则会充分利用那些距离最小的历史数据。例如，其中一种规则选取 \(k\) 个与目标航班最接近的历史数据值（即 \(k\) 个最近邻），并将这 \(k\) 架航班中晚点航班所占的比例作为晚点概率的估计值。章节 16.4.1 介绍了最近邻规则的变体，这些变体利用了所有的历史数据值，并给予那些特征向量与目标航班最接近的数据更多的“权重”。最近邻规则的一个明显弱点是，在确定特征向量之间的距离时，给予了向量的所有分量相同的权重，而没有考虑到某些分量可能比其他分量重要得多。章节 16.4.2 通过允许给予分量的权重取决于该分量本身，从而解决了这一问题。

在 章节 16.5 中，我们讨论了如何评估所介绍的这些程序在确定航班晚点概率方面的效果。

到目前为止，我们一直假设特征向量的元素在性质上是定性的，而在 章节 16.6 中，我们假设它们是定量的。假设一个实验的结果要么是成功要么是失败，章节 16.6.1 和 章节 16.6.2 分别介绍了最近邻规则和逻辑回归方法，用于估算具有特征向量 \((x_1, \dots, x_n)\) 的实验成功的概率。

在 章节 16.7 中，我们考虑了一个不同类型的问题。该通用模型的一个原型示例是：假设有两种可以开出的不同药物，每种药物 \(i\) 的使用都会导致治愈（即成功），概率为 \(p_i\) (\(i = 1, 2\))，其中 \(p_1\) 和 \(p_2\) 是未知的。假设开出某种特定药物的结果（治愈与否）可以立即获知，问题在于如何根据之前所有选择的结果，顺序地决定为接下来的每个病人开出哪种药物。这类问题被称为多臂老虎机问题（bandit problems）。我们提出了一种随机化决策程序；即在每个阶段，它指定一个概率 \(\alpha\)，并要求决策者以概率 \(\alpha\) 使用药物 1，以概率 \(1 - \alpha\) 使用药物 2。

16.2 晚点航班概率

假设我们有兴趣估算一架从加利福尼亚飞往纽约市的直达航班晚点的概率（这里“晚点”定义为比预定到达时间晚点至少三十分钟）。在没有任何关于该航班的额外信息时，我们可能会通过查阅所有此类航班的历史数据，并使用其中晚点航班的比例作为估计值。然而，我们通常对某次特定的航班更感兴趣。因此，让我们根据以下变量的值对每次航班进行分类：

\(X_1\)：航空公司 \(X_2\)：起飞城市 \(X_3\)：到达机场 \(X_4\)：星期几 \(X_5\)：起飞时间 \(X_6\)：飞机的尺寸 \(X_7\)：天气状况

假设这些变量的可能取值为：

\(X_1\)：1 = 美国航空（American），2 = 达美航空（Delta），3 = 联合航空（United），4 = 捷蓝航空（Jet Blue）； \(X_2\)：1 = 洛杉矶，2 = 旧金山，3 = 圣地亚哥，4 = 奥克兰； \(X_3\)：1 = 纽约肯尼迪机场，2 = 纽约拉瓜迪亚机场，3 = 纽瓦克机场； \(X_4\)：1, …, 7，其中 1 = 星期一，2 = 星期二，依此类推； \(X_5\)：1 = 清晨，2 = 上午，3 = 下午，4 = 傍晚，5 = 傍晚时分，6 = 深夜； \(X_6\)：1 = 小型，2 = 中型，3 = 大型； \(X_7\)：1 = 优于平均，2 = 平均，3 = 有暴风雨。

因此，例如，一架在周三傍晚从奥克兰飞往纽瓦克的联合航空大型飞机，且天气状况优于平均水平，其特征向量将被编码为 \((X_1, X_2, X_3, X_4, X_5, X_6, X_7) = (3, 4, 3, 3, 5, 3, 1)\)。我们使用向量 \((3, 4, 3, 3, 5, 3, 1)\) 来标识这样一次航班，并称其为该航班的特征向量（characterizing vector）。我们如何估算这样一次航班晚点的概率呢？当然，一种方法是查找历史数据库中所有具有相同特征向量的航班，并以这些航班中晚点的比例来估算晚点概率。然而，由于可能出现的航班数量非常多（根据计数的基本原理，共有 \(4 \cdot 4 \cdot 3 \cdot 7 \cdot 6 \cdot 3 \cdot 3 = 18,144\) 种可能），即使拥有庞大的历史数据集，也可能没有多少次完全相同类型的航班，因此此类估计可能不太准确。在接下来的章节中，我们将给出解决上述问题的几种不同方法。

16.3 朴素贝叶斯方法

假设我们想要估算特征向量为 \(X_1 = x_1, X_2 = x_2, \dots, X_7 = x_7\) 的航班将要晚点的概率。令 \(L\) 为航班晚点的事件，我们将上述概率写为条件概率 \(P(L | X_1 = x_1, \dots, X_7 = x_7)\)。现在，根据贝叶斯定理，我们有：

\[ \begin{align} P(L | X_1 = x_1, \dots, X_7 = x_7) &= \frac{P(L, X_1 = x_1, \dots, X_7 = x_7)}{P(X_1 = x_1, \dots, X_7 = x_7)} \\ &= \frac{P(L) P(X_1 = x_1, \dots, X_7 = x_7 | L)}{P(X_1 = x_1, \dots, X_7 = x_7)} \end{align} \tag{16.1}\]

因为 \(P(L)\) 是随机选择的航班晚点的概率，它的自然估计值是我们的历史数据库中晚点航班所占的比例，这也是我们将要使用的估计值。然而，\(P(X_1 = x_1, \dots, X_7 = x_7)\) 的自然估计量，即数据库中具有特征向量 \((x_1, \dots, x_7)\) 的航班比例，通常是不准确的，因为历史航班中具有该特定特征向量的航班数量有限。同样地，\(P(X_1 = x_1, \dots, X_7 = x_7 | L)\) 的相应自然估计量（即数据库中特征向量为 \((x_1, \dots, x_7)\) 的晚点航班比例）也会面临同样的困难。为了克服这一困难，我们将假定 \(X_1, X_2, \dots, X_7\) 是独立的随机变量，并且当我们已知航班晚点时，它们仍然保持独立（但不必具有相同的概率）。现在，在此假设下，我们将得到：

\[ P(X_1 = x_1, \dots, X_7 = x_7) = P(X_1 = x_1) P(X_2 = x_2) \dots P(X_7 = x_7) \]

我们可以通过数据库中特征向量具有 \(X_i = x_i\) 的所有航班的比例来估计 \(P(X_i = x_i)\)。例如，我们会通过数据库中由联合航空（United）承运的所有航班的比例来估计 \(P(X_1 = 3)\)。此外，因为我们也假设当我们已知航班晚点时 \(X_1, X_2, \dots, X_7\) 仍然保持独立，所以我们有：

\[ P(X_1 = x_1, \dots, X_7 = x_7 | L) = P(X_1 = x_1 | L) P(X_2 = x_2 | L) \dots P(X_7 = x_7 | L) \]

因此，我们可以通过所有晚点航班中特征向量具有 \(X_i = x_i\) 的航班比例来估计 \(P(X_i = x_i | L)\)。因此，如果 \(f(L)\) 是数据库中到达晚点的航班比例；\(f_i(x)\) 是数据库中特征向量具有 \(X_i = x\) 的航班比例；而 \(f_i(x|L)\) 是数据库中特征向量具有 \(X_i = x\) 的晚点航班比例，那么我们对下式的估计：

\[ P(L | X_1 = x_1, \dots, X_7 = x_7) = \frac{P(L) P(X_1 = x_1, \dots, X_7 = x_7 | L)}{P(X_1 = x_1, \dots, X_7 = x_7)} \]

被称为朴素贝叶斯估计量（naive Bayes estimator），即：

\[ \frac{f(L) f_1(x_1 | L) f_2(x_2 | L) \dots f_7(x_7 | L)}{f_1(x_1) f_2(x_2) \dots f_7(x_7)} \]

例子 16.1 表格 16.1 给出了 79 架从单一机场起飞的航班的历史晚点数据。假设这些航班由向量 \((x_1, x_2, x_3, x_4)\) 描述，其中 \(x_1\) 的可能取值为 1 和 2，\(x_2\) 的可能取值为 1 和 2，\(x_3\) 的可能取值为 1, 2 和 3，而 \(x_4\) 的可能取值为 1 和 2。使用朴素贝叶斯方法估算特征向量为 \((2, 1, 2, 2)\) 的航班将要晚点的概率。

表格 16.1: 历史航班数据

航班向量	此类航班数量	晚点数量
(1,1,1,1)	2	1
(1,1,1,2)	2	0
(1,1,2,1)	2	0
(1,1,2,2)	1	0
(1,1,3,1)	3	1
(1,1,3,2)	3	0
(1,2,1,1)	4	1
(1,2,1,2)	3	1
(1,2,2,1)	5	2
(1,2,2,2)	3	1
(1,2,3,1)	3	1
(1,2,3,2)	4	2
(2,1,1,1)	4	2
(2,1,1,2)	3	1
(2,1,2,1)	5	2
(2,1,2,2)	4	1
(2,1,3,1)	3	1
(2,1,3,2)	2	0
(2,2,1,1)	3	1
(2,2,1,2)	4	1
(2,2,2,1)	5	2
(2,2,2,2)	5	3
(2,2,3,1)	3	1
(2,2,3,2)	3	0

解答： 由于这 79 架航班中有 25 架晚点，因此 \(P(L)\) 的估计值为 \(f(L) = 25/79\)。 因为 79 架航班中有 44 架的 \(x_1 = 2\)，所以 \(P(X_1 = 2)\) 的估计值为 \(f_1(2) = 44/79\)。 因为 79 架航班中有 34 架的 \(x_2 = 1\)，所以 \(P(X_2 = 1)\) 的估计值为 \(f_2(1) = 34/79\)。 因为 79 架航班中有 30 架的 \(x_3 = 2\)，所以 \(P(X_3 = 2)\) 的估计值为 \(f_3(2) = 30/79\)。 因为 79 架航班中有 37 架的 \(x_4 = 2\)，所以 \(P(X_4 = 2)\) 的估计值为 \(f_4(2) = 37/79\)。 因为 25 架晚点航班中有 15 架的 \(x_1 = 2\)，所以 \(P(X_1 = 2 | L)\) 的估计值为 \(f_1(2 | L) = 15/25\)。 因为 25 架晚点航班中有 9 架的 \(x_2 = 1\)，所以 \(P(X_2 = 1 | L)\) 的估计值为 \(f_2(1 | L) = 9/25\)。 因为 25 架晚点航班中有 12 架的 \(x_3 = 2\)，所以 \(P(X_3 = 2 | L)\) 的估计值为 \(f_3(2 | L) = 12/25\)。 因为 25 架晚点航班中有 10 架的 \(x_4 = 2\)，所以 \(P(X_4 = 2 | L)\) 的估计值为 \(f_4(2 | L) = 10/25\)。

特征向量为 \((2, 1, 2, 2)\) 的航班的朴素贝叶斯估计晚点概率为：

\[ \frac{f(L) f_1(2 | L) f_2(1 | L) f_3(2 | L) f_4(2 | L)}{f_1(2) f_2(1) f_3(2) f_4(2)} = \frac{25 \cdot 15 \cdot 9 \cdot 12 \cdot 10 \cdot 79^4}{79 \cdot 25^4 \cdot 44 \cdot 34 \cdot 30 \cdot 37} = .3078 \]

将此估计值与 \(1/4 = .25\)（即特征向量为 \((2, 1, 2, 2)\) 且晚点的航班比例）进行比较，或与 \(25/79 = .3165\)（即所有航班中晚点的比例）进行比较，是很有趣的。 \(\blacksquare\)

16.3.1 朴素贝叶斯方法的一种变体

如前一节所示，我们有兴趣使用历史数据来估算由向量 \((x_1, \dots, x_n)\) 表征的情况将导致某种结果的概率。正如所指出的，朴素贝叶斯方法通过假设 \(X_1, \dots, X_n\) 是独立的来估算 \(P(X_1 = x_1, \dots, X_n = x_n)\)，因此有：

\[ P(X_1 = x_1, \dots, X_n = x_n) = P(X_1 = x_1) \dots P(X_n = x_n) \]

然后使用历史数据中第 \(i\) 个分量取值为 \(x_i\) 的比例作为 \(P(X_i = x_i)\) 的估计值 (\(i = 1, \dots, n\))。然而，在许多例子中，\(X_1, \dots, X_n\) 独立的假设显然是不可行的。例如，假设患有克罗恩病（Crohn’s disease）类似身体症状的患者接受了一组 \(n\) 次医疗测试，测试 \(i\) 的结果（记为 \(X_i\)）如果对该疾病呈阳性则为 1，如果是阴性则为 0。现在，假设测试具有一定的有效性，那么 \(X_i = 1\) 会使得患者患有该疾病的可能性增加，从而使得 \(X_j = 1\) 的可能性也增加。因此，\(X_1, \dots, X_n\)（即测试结果）显然不是独立的。然而，虽然它们不独立，但如果我们知道该患者是否患有该疾病，那么假设它们是独立的可能是合理的。也就是说，在给定患者是否患有该疾病的条件下，可以合理地假设测试结果是独立的。假设如此，如果我们令 \(D\) 为患者患病的事件，我们可以利用等式：

\[ \begin{align} P(X_1 = x_1, \dots, X_n = x_n) &= P(X_1 = x_1, \dots, X_n = x_n | D) P(D) \\ &\quad + P(X_1 = x_1, \dots, X_n = x_n | D^c) (1 - P(D)) \end{align} \]

假设当我们知道患者是否患病时，\(X_1, \dots, X_n\) 是独立的，则有：

\[ P(X_1 = x_1, \dots, X_n = x_n | D) = P(X_1 = x_1 | D) \dots P(X_n = x_n | D) \] \[ P(X_1 = x_1, \dots, X_n = x_n | D^c) = P(X_1 = x_1 | D^c) \dots P(X_n = x_n | D^c) \]

现在，我们可以通过考虑历史数据库中患有该疾病的患者，并让估计值作为这些患者中测试 \(i\) 值为 \(x_i\) 的比例，来估计 \(P(X_i = x_i | D)\)。类似地，我们可以通过考虑历史数据库中未患有该疾病的患者，并让估计值作为这些患者中测试 \(i\) 值为 \(x_i\) 的比例，来估计 \(P(X_i = x_i | D^c)\)。此外，\(P(D)\) 将通过历史数据库中患有该疾病的患者比例来估算，而 \(P(D^c)\) 则通过未患有该疾病的比例来估算。

例子 16.2 向每位表现出某种医疗状况症状的患者提供一系列三次测试，三次测试的结果由向量 \((x_1, x_2, x_3)\) 表征，其中 \(x_1\) 的可能取值为 1 和 2，\(x_2\) 的可能取值为 1 和 2，而 \(x_3\) 的可能取值为 1, 2 和 3。历史数据涉及 68 名接受过测试的患者，给出了每名患者的测试结果以及最终是否被发现患有该病症。数据总结在 表格 16.2 中。

表格 16.2: 医疗测试历史数据

特征向量	患者数量	患病人数	未患病人数
(1,1,1)	4	1	3
(1,1,2)	3	0	3
(1,1,3)	5	1	4
(1,2,1)	6	1	5
(1,2,2)	7	2	5
(1,2,3)	5	3	2
(2,1,1)	6	3	3
(2,1,2)	7	2	5
(2,1,3)	5	1	4
(2,2,1)	6	2	4
(2,2,2)	9	4	5
(2,2,3)	5	1	4

例如，历史数据库详述的 68 名患者中，有 7 名具有特征向量 \((2, 1, 2)\)，其中 2 名患有该病症。使用上述方法估算特征向量为 \((2, 1, 2)\) 的新患者患有该病症的概率。

解答： 令 \(\mathbf{X} = (X_1, X_2, X_3)\)。那么，令 \(C\) 为患者患有该医疗状况的事件，我们从下式开始：

\[ \begin{align} P(C | \mathbf{X} = (2, 1, 2)) &= \frac{P(C, \mathbf{X} = (2, 1, 2))}{P(\mathbf{X} = (2, 1, 2))} \\ &= \frac{P(C) P(\mathbf{X} = (2, 1, 2) | C)}{P(\mathbf{X} = (2, 1, 2))} \\ &= \frac{P(C) P(\mathbf{X} = (2, 1, 2) | C)}{P(\mathbf{X} = (2, 1, 2) | C) P(C) + P(\mathbf{X} = (2, 1, 2) | C^c) P(C^c)} \end{align} \]

现在，如果我们假设当我们知道患者是否患病时 \(X_1, X_2, X_3\) 变得独立，那么我们有：

\[ P(\mathbf{X} = (2, 1, 2) | C) = P(X_1 = 2 | C) P(X_2 = 1 | C) P(X_3 = 2 | C) \] \[ P(\mathbf{X} = (2, 1, 2) | C^c) = P(X_1 = 2 | C^c) P(X_2 = 1 | C^c) P(X_3 = 2 | C^c) \]

我们现在准备估计测试向量为 \((2, 1, 2)\) 的患者患病的概率。 因为 68 名患者中有 21 名患有该病症，所以 \(P(C)\) 的估计值为 \(21/68\)。 在患有该病症的 21 名患者中： 13 名的 \(x_1 = 2\)，所以 \(P(X_1 = 2 | C)\) 的估计值为 \(13/21\)。 8 名的 \(x_2 = 1\)，所以 \(P(X_2 = 1 | C)\) 的估计值为 \(8/21\)。 8 名的 \(x_3 = 2\)，所以 \(P(X_3 = 2 | C)\) 的估计值为 \(8/21\)。

因为 68 名患者中有 47 名没有患有该病症，所以 \(P(C^c)\) 的估计值为 \(47/68\)。 在没有患有该病症的 47 名患者中： 25 名的 \(x_1 = 2\)，所以 \(P(X_1 = 2 | C^c)\) 的估计值为 \(25/47\)。 22 名的 \(x_2 = 1\)，所以 \(P(X_2 = 1 | C^c)\) 的估计值为 \(22/47\)。 18 名的 \(x_3 = 2\)，所以 \(P(X_3 = 2 | C^c)\) 的估计值为 \(18/47\)。

\(P(\mathbf{X} = (2, 1, 2) | C)\) 的估计值因此为 \(\frac{13 \cdot 8 \cdot 8}{21^3} = .08984\)。 \(P(\mathbf{X} = (2, 1, 2) | C^c)\) 的估计值因此为 \(\frac{25 \cdot 22 \cdot 18}{47^3} = .09535\)。 \(P(C | \mathbf{X} = (2, 1, 2))\) 的估计值为：

\[ \frac{(21/68)(.08984)}{(21/68)(.08984) + (47/68)(.09535)} = .2963 \]

也就是说，我们对具有特征向量 \((2, 1, 2)\) 的患者患有该病症的概率的估计值为 .2963。 \(\blacksquare\)

注： 上述变体利用了条件独立（conditional independence）的概念，当不需要相互独立的随机变量 \(X_1, \dots, X_n\) 在已知一些额外信息的情况下变得独立时，就会产生条件独立。例如，假设有 2 枚硬币，硬币 1 在每次抛掷中出现正面的概率为 .8，硬币 2 出现正面的概率为 .3。假设这些硬币中有一枚是以同样的可能性被选中的。现在假设所选的硬币被抛掷 8 次。令 \(X_i = 1\) 如果第 \(i\) 次抛硬币结果为正面，令 \(X_i = 0\) 如果第 \(i\) 次抛硬币结果为反面。现在，如果我们知道前 5 次抛掷的结果都是正面，那么我们就非常有可能使用的是硬币 1，这使得下一次抛掷也出现正面的可能性更大（相对于我们没有关于前 5 次抛掷的信息时）。因此，\(X_1, \dots, X_8\) 不是独立的。然而，如果我们知道选择了哪枚硬币，那么关于之前抛掷的信息对于确定即将到来的抛掷结果将没有用处。也就是说，如果我们令 \(Y\) 为所选的硬币，那么知道 \(Y = 1\) 还是 \(Y = 2\) 都会使得 \(X_1, \dots, X_n\) 独立。在这种情况下，我们说 \(X_1, \dots, X_n\) 在给定 \(Y\) 的值时是条件独立的。这意味着，例如：

\[ \begin{align} P(X_1 = 1, X_2 = 1, X_3 = 1 | Y = 1) &= P(X_1 = 1 | Y = 1) P(X_2 = 1 | Y = 1) P(X_3 = 1 | Y = 1) \\ &= (.8)(.8)(.8) = .512 \end{align} \] \(\blacksquare\)

16.4 基于距离的估计量：\(k\)-最近邻规则

让我们定义两个特征向量 \(\mathbf{x} = (x_1, x_2, \dots, x_7)\) 和 \(\mathbf{y} = (y_1, y_2, \dots, y_7)\) 之间的距离（记为 \(d\)）：

\[ d(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^7 I\{x_i \neq y_i\} \]

其中

\[ I\{x_i \neq y_i\} = \begin{cases} 0, & \text{若 } x_i = y_i \\ 1, & \text{若 } x_i \neq y_i \end{cases} \]

也就是说，两个特征向量之间的距离是它们取值不同的坐标数量。基于距离的航班晚点概率估计量（针对特征向量为 \((x_1, x_2, \dots, x_7)\) 的航班）是基于这样一种假设：距离较小的两个特征向量应该具有相似的晚点概率。\(k\)-最近邻规则（\(k\)-nearest neighbor rule）是一种流行的估计方法。要使用它，首先需要确定 \((x_1, x_2, \dots, x_7)\) 与历史数据库中所有特征向量之间的距离。该规则会选出与 \((x_1, x_2, \dots, x_7)\) 距离最小的 \(k\) 个历史向量，然后使用这 \(k\) 架航班中晚点航班所占的比例，作为该特征向量为 \((x_1, x_2, \dots, x_7)\) 的航班晚点概率的估计值。另一种基于距离的估计方法是，选择历史数据库中所有位于 \((x_1, x_2, \dots, x_7)\) 固定距离之内的向量，然后使用这些航班中晚点航班的比例作为该特征向量为 \((x_1, x_2, \dots, x_7)\) 的航班晚点概率的估计值。

例子 16.3 考虑 例子 16.1 中的数据。使用固定距离 1，与 \((2, 1, 2, 2)\) 距离至多为 1 的特征向量有：\((2, 1, 2, 2)\)、\((1, 1, 2, 2)\)、\((2, 2, 2, 2)\)、\((2, 1, 1, 2)\)、\((2, 1, 3, 2)\)、\((2, 1, 2, 1)\)。由于数据集中具有这些特征向量之一的 20 架航班中有 7 架晚点，因此对 \((2, 1, 2, 2)\) 航班晚点概率的估计值为 \(7/20 = .35\)。 \(\blacksquare\)

16.4.1 距离加权方法

另一种仅使用部分历史数据值进行估计的方法是使用全部数据，但对于那些特征向量最接近目标向量的数据值给予更大的权重。假设历史数据库中有 \(N\) 个特征向量，我们想利用它们来估算特征向量为 \((x_1, x_2, \dots, x_7)\) 的航班晚点的概率。令 \(d_j\) 为历史数据集中第 \(j\) 个特征向量与 \((x_1, x_2, \dots, x_7)\) 之间的距离（对于 \(j = 1, \dots, N\)）。同时，令 \(w_1, \dots, w_N\) 定义为：

\[ w_j = \frac{1}{1 + d_j}, \quad j = 1, \dots, N \]

数量 \(w_j\) 是我们在估算特征向量为 \((x_1, x_2, \dots, x_7)\) 的航班晚点概率时，给予第 \(j\) 个历史数据值的权重。因此，一个特征向量与目标向量相同的历史数据值被赋予权重 1，一个向量距离为 1 的数据值被赋予权重 1/2，依此类推。估算出的特征向量为 \((x_1, x_2, \dots, x_7)\) 的航班晚点概率的最终结果，是所有晚点航班的权重之和除以所有航班的权重之和。具体而言，定义 \(I_j\) 在第 \(j\) 架历史航班晚点时等于 1，不晚点时等于 0，我们估算所需的概率为：

\[ \frac{\sum_{j=1}^N I_j w_j}{\sum_{j=1}^N w_j} \tag{16.2}\]

例子 16.4 表格 16.3 给出了 例子 16.1 中的历史数据，以及每个向量相对于 \((2, 1, 2, 2)\) 的距离和相应的权重。利用这些数据获得 \((2, 1, 2, 2)\) 航班晚点概率的距离加权估计值。

表格 16.3: 历史航班数据（含权重）

航班向量	此类航班数量	晚点数量	(2122) 距离	权重
(1,1,1,1)	2	1	3	1/4
(1,1,1,2)	2	0	2	1/3
(1,1,2,1)	2	0	2	1/3
(1,1,2,2)	1	0	1	1/2
(1,1,3,1)	3	1	3	1/4
(1,1,3,2)	3	0	2	1/3
(1,2,1,1)	4	1	4	1/5
(1,2,1,2)	3	1	3	1/4
(1,2,2,1)	5	2	3	1/4
(1,2,2,2)	3	1	2	1/3
(1,2,3,1)	3	1	4	1/5
(1,2,3,2)	4	2	3	1/4
(2,1,1,1)	4	2	2	1/3
(2,1,1,2)	3	1	1	1/2
(2,1,2,1)	5	2	1	1/2
(2,1,2,2)	4	1	0	1
(2,1,3,1)	3	1	2	1/3
(2,1,3,2)	2	0	1	1/2
(2,2,1,1)	3	1	3	1/4
(2,2,1,2)	4	1	2	1/3
(2,2,2,1)	5	2	2	1/3
(2,2,2,2)	5	3	1	1/2
(2,2,3,1)	3	1	3	1/4
(2,2,3,2)	3	0	2	1/3

解答： 在 79 架航班中，7 架权重为 1/5，23 架权重为 1/4，29 架权重为 1/3，16 架权重为 1/2，4 架权重为 1。所有 79 架航班的权重之和为 \(7/5 + 23/4 + 29/3 + 16/2 + 4 = 28.8167\)。另一方面，在 25 架晚点航班中，2 架权重为 1/5，9 架权重为 1/4，7 架权重为 1/3，6 架权重为 1/2，1 架权重为 1。因此，晚点航班的权重之和为 \(2/5 + 9/4 + 7/3 + 6/2 + 1 = 8.9833\)。由此得出特征向量为 \((2, 1, 2, 2)\) 的航班晚点的估计概率为 \(8.9833/28.8167 = .3117\)。 \(\blacksquare\)

还有其他权衡历史数据结果的方法。例如，可以选择一个介于 0 和 1 之间的数字 \(\beta\)，然后对于与 \((x_1, \dots, x_7)\) 距离为 \(d\) 的历史数据赋予权重 \(\beta^d\)；或者我们可以根据历史数据向量与 \((x_1, \dots, x_7)\) 的接近程度对其进行排序，然后对第 \(j\) 个最近邻赋予权重 \(\beta^j\)。

16.4.2 分量加权距离

假设我们想估算特征向量为 \((x_1, \dots, x_7)\) 的航班晚点的概率。令 \(X_i\) 为随机选择的历史特征向量的第 \(i\) 个分量值。现在，如果无论 \(X_i = x_i\) 是否成立，航班晚点的概率变化都不大，那么在尝试评估向量为 \((x_1, \dots, x_7)\) 的航班晚点概率时，似乎不需要给分量 \(i\) 赋予太多的权重。令 \(p_L(x_i)\) 为特征向量具有 \(X_i = x_i\) 的历史航班中晚点航班的比例，而 \(p_L(\bar{x}_i)\) 为特征向量中 \(X_i \neq x_i\) 的历史航班中晚点航班的比例，令 \(a_i = |p_L(x_i) - p_L(\bar{x}_i)|\) 为这两个比例之间的绝对差。因此，\(a_i\) 是对 \(X_i = x_i\) 这一事实对航班晚点概率产生影响的一个估计。考虑到这一点，我们可以定义待考查航班向量 \(\mathbf{x} = (x_1, \dots, x_7)\) 与历史向量 \(\mathbf{y} = (y_1, \dots, y_7)\) 之间的分量加权距离（component weighted distance）为：

\[ d(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^7 a_i I\{x_i \neq y_i\} \]

16.5 评估方法

我们现在讨论如何评估上述所提出的各种确定航班晚点概率的方法。为了评估任何一种方法的价值，我们从历史数据库开始，并从中随机选择一个数据子集，称为测试集（testing set），该子集将用于评估该程序。例如，假设我们有 3000 架航班的记录。我们应当从中随机选择一个大小为 1000 的子集构成测试集，然后看看每个程序在使用剩余 2000 架航班的数据作为历史数据来估算测试集中航班晚点概率时的表现。这一过程的结果将是 1000 个测试集航班晚点的估计概率，以及关于其中每一个航班是否实际晚点的信息。也就是说，结果将是 1000 个对 \((p_i, l_i)\)，\(i = 1, \dots, 1000\)。其中 \(p_i\) 是对测试集中第 \(i\) 架航班将要晚点的概率的估计值，而 \(l_i\) 如果该航班实际晚点则等于 1，否则等于 0。

为了评估每一个程序，我们给每一对赋予一个“损失”，其中给予对 \((p_i, l_i)\) 的损失（loss）为：

\[ L = \begin{cases} (1 - p_i)^2, & \text{若 } l_i = 1 \\ p_i^2, & \text{若 } l_i = 0 \end{cases} \]

换句话说，损失就是未发生事件（要么不晚点，要么晚点）被赋予的概率的平方。也就是说，如果该方法得出的晚点估计概率等于 \(p\)，那么如果该飞机晚点，产生的损失为 \((1 - p)^2\)，如果没有晚点，产生的损失为 \(p^2\)。例如，如果估计的晚点概率为 0，那么如果晚点则损失 1，如果不晚点则损失 0；如果估计的晚点概率为 .2，那么如果晚点则损失 .64，如果不晚点则损失 .04；如果估计的晚点概率为 .5，那么无论是否晚点，都损失 .25。无论正在考虑哪种程序，其总损失之和最低的程序就被认为是最好的程序。

要理解上述损失规则的原理，假设某架特定飞机晚点的实际（尽管未知）概率为 \(\alpha\)，令 \(L\) 表示当估计晚点概率为 \(p\) 时所产生的损失。因为如果飞机晚点（概率为 \(\alpha\)），损失为 \((1 - p)^2\)；如果飞机不晚点（概率为 \(1 - \alpha\)），损失为 \(p^2\)，由此得出期望损失为：

\[ \begin{align} E[L] &= \alpha(1 - p)^2 + (1 - \alpha)p^2 \\ &= \alpha - 2p\alpha + p^2 \\ &= \alpha + (p - \alpha)^2 - \alpha^2 \end{align} \]

因此，使 \(E[L]\) 尽可能小的估计值 \(p\) 是 \(p = \alpha\)。也就是说，当估计概率等于实际概率 \(\alpha\) 时，期望损失最低，且随着估计概率 \(p\) 越偏离 \(\alpha\)，期望损失也随之增加。因此，在 1000 个测试案例中产生最低总损失和的程序，最有可能就是估算晚点概率的最佳程序。

虽然上述方法可用于比较朴素贝叶斯、\(k\)-最近邻和固定距离方法，以观察哪种方法在特定应用中表现更好，但它仍然没有解决这些方法中是否有任何一个是真正好用的这一问题。检查这一点的一种方法是将这些程序的测试数据产生的平均损失，与一项忽略特征向量并始终通过历史数据集中所有航班中晚点的比例来估计测试案例的晚点概率的策略的平均损失进行比较。为了推导该数值，假设 3000 架航班中晚点的比例为 \(\beta\)，并假设每架航班的预测晚点概率均为 \(\beta\)。那么，当航班晚点时损失为 \((1 - \beta)^2\)，当不晚点时损失为 \(\beta^2\)，由于晚点航班的比例为 \(\beta\)，所以平均损失为：

\[ \beta(1 - \beta)^2 + (1 - \beta)\beta^2 = \beta(1 - \beta) \]

例子 16.5 为了了解平均损失比忽略特征向量的策略能减少多少，假设已知特征向量下的历史晚点概率可以被视为独立的连续型均匀分布 \((0, 1)\) 随机变量的值。由于历史航班中有 1/2 会晚点，始终估计晚点概率为 1/2 的规则将具有平均损失 1/4。另一方面，假设我们有一个始终给出正确概率的最佳估计程序。由于当为发生概率为 \(p\) 的事件给出估计值 \(p\) 时产生的平均损失为 \((1 - p)^2 p + p^2 (1 - p) = p - p^2\)，因此该最佳程序的平均损失为 \(\int_0^1 (p - p^2) dp = 1/6\)。 \(\blacksquare\)

注： 假设有 \(N\) 个数据值。当 \(N\) 不太大时，我们可以通过观察每个估计器在将其他 \(N - 1\) 个值用作历史数据点时对每个单独数据值的处理效果来对其进行评估。

16.6 当特征向量是定量的时候

在本节中，我们再次假设我们有兴趣估算特征向量为 \((x_1, \dots, x_n)\) 的实验成功的概率，但现在我们假设向量 \((x_1, \dots, x_n)\) 的元素在性质上是定量的 (quantitative)，而不是定性的。也就是说，例如，\(x_1\) 可以代表个人的体重。在 章节 16.6.1 中，我们将展示如何使用最近邻规则，在 章节 16.6.2 中，我们考虑逻辑回归模型。

16.6.1 最近邻规则

与定性特征向量的情况一样，在估算具有定量特征向量 \((x_1, \dots, x_n)\) 的实验结果成功的概率时，最近邻规则会对那些特征向量最接近 \((x_1, \dots, x_n)\) 的历史数据给予更多的权重。因此，首先我们需要定义两个特征向量（例如 \(\mathbf{x} = (x_1, \dots, x_n)\) 和 \(\mathbf{y} = (y_1, \dots, y_n)\)）之间的距离。虽然使用欧几里得距离 \(\sqrt{\sum_{i=1}^n (x_i - y_i)^2}\) 或 \(\sum_{i=1}^n |x_i - y_i|\) 似乎很自然，但我们必须首先考虑到向量的分量指的是不同的实体，因此它们将具有不同的单位，这会影响它们的值。例如，假设我们有兴趣估算某件物品因爆炸而受到严重损坏的概率，且 \(x_1\) 指的是该物品与爆炸点之间的距离。如果距离以英尺为单位测量，那么 \(|x_1 - y_1|\) 将是如果以码为单位测量时的 3 倍，从而改变了哪些历史特征向量 \((x_1, \dots, x_m)\) 最接近 \((y_1, \dots, y_n)\)。为了修正这一异常现象，我们首先对数据进行标准化。令 \(m_i\) 和 \(s_i\) 分别为所有历史特征向量第 \(i\) 个分量值的样本均值和方差（\(i = 1, \dots, n\)），重新定义所有历史特征向量以及当前正在考虑的向量，使得特征向量 \((x_1, \dots, x_n)\) 变为 \((\frac{x_1 - m_1}{s_1}, \dots, \frac{x_n - m_n}{s_n})\)。通过这种方式，我们对历史向量和待考查向量进行了标准化，使得每个分量值的样本均值为 0，样本方差为 1。现在，利用这些标准化后的向量，定义 \(\mathbf{x} = (x_1, \dots, x_n)\) 和 \(\mathbf{y} = (y_1, \dots, y_n)\) 之间的距离为其欧几里得距离 \(\sqrt{\sum_{i=1}^n (x_i - y_i)^2}\)。（虽然欧几里得距离最常用，但有时也会使用距离函数 \(\sum_{i=1}^n |x_i - y_i|\)。）

用于估计 \(p(x_1, \dots, x_n)\)（即特征向量为 \((x_1, \dots, x_n)\) 的实验产生成功结果的概率）的 \(k\)-最近邻规则 会找到 \(k\) 个特征向量最接近 \((x_1, \dots, x_n)\) 的历史数据，然后取其中产生成功结果的数据所占的比例作为估计值。

虽然用于估计 \(p(x_1, \dots, x_n)\) 的 \(k\)-最近邻规则仅使用 \(k\) 个最近的历史数据值的结果，并给予所有这些数据相等的权重，但一种改进方法是使用所有历史数据的结果，给予那些特征向量最接近 \((x_1, \dots, x_n)\) 的数据更多的权重。假设有 \(N\) 个历史数据结果。一种可能性是令 \(I_j\) 在第 \(j\) 个最近的历史结果成功时等于 1，否则等于 0，然后通过下式估计 \(p(x_1, \dots, x_n)\)：

\[ \frac{\sum_{j=1}^N \beta^{j-1} I_j}{\sum_{j=1}^N \beta^{j-1}} = \frac{1 - \beta}{1 - \beta^N} \sum_{j=1}^N \beta^{j-1} I_j \]

其中 \(0 < \beta < 1\) 是待选参数。也就是说，该规则分别为与 \((x_1, \dots, x_n)\) 最接近、次接近等实验的结果赋予连续的权重 \(1, \beta, \beta^2, \dots, \beta^{N-1}\)。

16.6.2 逻辑回归

逻辑回归也可以用来估计 \(p(x_1, \dots, x_n)\)，即特征向量为 \(x_1, \dots, x_n\) 的实验产生成功结果的概率。该模型假设对于某些常数 \(b_0, b_1, \dots, b_n\)（需要进行估算），有：

\[ p(x_1, \dots, x_n) = \frac{e^{b_0 + \sum_{i=1}^n b_i x_i}}{1 + e^{b_0 + \sum_{i=1}^n b_i x_i}} \tag{16.3}\]

R 可用于估算参数 \(b_0, b_1, \dots, b_n\)。例如，假设 \(n = 5\)，且有 6 个具有特征向量：

(3, 7, 9, 4, 12) (8, 10, 4, 5, 16) (14, 9, 11, 10, 15) (18, 20, 12, 8, 7) (2, 9, 13, 8, 17) (7, 13, 21, 15, 19)

的实验分别产生了结果 (1, 0, 1, 1, 0, 1)，其中 1 表示成功，0 表示失败。（因此，具有特征向量 (8, 10, 4, 5, 16) 和 (2, 9, 13, 8, 17) 的实验结果为失败，而其他的均为成功。）要使用 R 估算参数，对于 \(i = 1, \dots, 5\)，令 \(vi\) 为 6 个已运行实验的特征向量第 \(i\) 个坐标的连续值，然后键入以下内容：

> v1 = c(3, 8, 14, 18, 2, 7)
> v2 = c(7, 10, 9, 20, 9, 13)
> v3 = c(9, 4, 11, 12, 8, 15)
> v4 = c(4, 5, 10, 8, 8, 15)
> v5 = c(12, 16, 15, 7, 17, 19)
> y = c(1, 0, 1, 1, 0, 1)
> model = glm(y ~ v1 + v2 + v3 + v4 + v5, family = "binomial")
> model

注意：在 R 中使用 glm() 进行逻辑回归时，必须指定 family = "binomial" 参数。

按回车键后会产生以下输出：

Call: glm(formula = y ~ v1 + v2 + v3 + v4 + v5, family = "binomial")

Coefficients:
(Intercept)      v1       v2       v3       v4       v5
  -5.25116    0.09965  0.04360  0.45959 -0.49604  0.29124

也就是说，逻辑回归模型中的 \(a\) 和 \(b\) 估计值为：

\[ p(x_1, \dots, x_6) = \frac{\exp\{-5.25116 + 0.09965x_1 + 0.04360x_2 + 0.45959x_3 - 0.49604x_4 + 0.29124x_5\}}{1 + \exp\{-5.25116 + 0.09965x_1 + 0.04360x_2 + 0.45959x_3 - 0.49604x_4 + 0.29124x_5\}} \]

16.7 选择最佳概率：多臂老虎机问题

假设有两种不同的药物可以治疗某种疾病，每种药物 \(i\) 的使用都会导致成功（即治愈），其概率为 \(p_i\)，\(i = 1, 2\)，其中 \(p_1\) 和 \(p_2\) 是未知的。假设开出某种特定药物的结果（治愈与否）可以立即获知，问题在于如何根据之前所有的选择结果，顺序地决定为后续的每位病人开出哪种药物。由于此类问题的早期论文常涉及到一个有两个摇臂（左臂和右臂）的赌场老虎机（这种机器常被称为“两臂老虎机”），玩家在每次博弈时可以选择拉动哪个摇臂，因此这类问题被称为多臂老虎机问题（bandit problems）。由于 \(p_1\) 和 \(p_2\) 是未知的，每次选择使用哪种药物都涉及到一种权衡：是选择目前看起来最好的药物，还是选择一种药物以收集更多关于其成功概率的信息。我们现在提出一种在绝大多数情况下表现非常出色的策略，它能选出较好的药物。该策略是随机化的，即在每个阶段它都会指定使用药物 1 的概率。该策略如下：

• 每种药物先使用一次。
• 假设在药物 \(i\) 已被使用 \(n_i\) 次且总共治愈 \(s_i\) 次（\(i = 1, 2\)）的情况下做出决策。令： \[ f_1 = \frac{s_1 + 1}{n_1 + 2}, \quad f_2 = \frac{s_2 + 1}{n_2 + 2} \] 并令： \[ r = \frac{f_1 - f_2}{\sqrt{f_1(1 - f_1)/n_1 + f_2(1 - f_2)/n_2}} \] 设 \(\Phi\) 为标准正态分布函数，令： \[ x = \Phi(r) \] 现在以概率 \(x\) 使用药物 1，以概率 \(1 - x\) 使用药物 2。

例如，假设在某个阶段，药物 1 已使用了 9 次，治愈了 5 次；药物 2 已使用了 5 次，治愈了 2 次。在这种情况下，\(n_1 = 9, s_1 = 5, n_2 = 5, s_2 = 2\)，得到 \(f_1 = 6/11, f_2 = 3/7\)。因此，

\[ r = \frac{6/11 - 3/7}{\sqrt{\frac{30}{121 \times 9} + \frac{12}{49 \times 5}}} = .4225 \]

得出： \(x = \Phi(.4225) = .6637\)。

因此，该程序要求以 .6637 的概率使用药物 1，以 \(1 - .6637 = .3363\) 的概率使用药物 2。这可以通过计算机生成的均匀分布 \((0, 1)\) 随机变量 \(U\)（称为随机数）来实现。因为对于 \(0 < x < 1\)，均匀分布 \((0, 1)\) 随机变量小于 \(x\) 的概率为 \(x\)，所以如果 \(U < .6637\)，则该程序将使用药物 1，如果 \(U \geq .6637\)，则使用药物 2。

注： 1. R 可用于确定每个阶段的操作。因为命令 runif(k) 会生成 \(k\) 个均匀分布 \((0, 1)\) 随机变量的值，所以在药物 \(i\) 使用了 \(n_i\) 次并产生 \(s_i\) 次成功结果（\(i = 1, 2\)）时，我们可以执行以下操作来获取下一步行动： R > f1 = (s1 + 1) / (n1 + 2) > f2 = (s2 + 1) / (n2 + 2) > r = (f1 - f2) / sqrt(f1 * (1 - f1) / n1 + f2 * (1 - f2) / n2) > x = pnorm(r) > x > runif(1) 倒数第二个输出给出 \(x\)，最后一个输出给出随机数的值。如果随机数小于 \(x\)，则下一步应使用药物 1；如果不是，则应使用药物 2。 例如，假设药物 1 已使用 9 次，成功 5 次；药物 2 已使用 5 次，成功 2 次。要确定下一步操作，请执行： R > f1 = 6/11 > f2 = 3/7 > r = (f1 - f2) / sqrt(f1 * (1 - f1) / 9 + f2 * (1 - f2) / 5) > x = pnorm(r) > x [1] 0.6636754 > runif(1) [1] 0.2600016 因为 .2600（随机数的值）小于 \(x = .6637\)，所以下一步应使用药物 1。 2. 值 \(f_1\) 和 \(f_2\) 是对使用每种药物获得的成功比例的轻微变体，实际比例被稍作修改，以使其值不等于 0 或 1。 3. 上述考虑的老虎机问题类型除了药物测试外还有许多应用。例如，广告商可能希望在两种不同的互联网广告之间进行选择，广告注册为“成功”的前提是用户点击了它。 4. 老虎机问题的结果可以推广到有两种以上可能选择的情况。

16.8 习题

1. 一家保险公司在设定其汽车保险费率时，会为每位保单持有人保留一个特征向量 \((x_1, \dots, x_7)\)。在该向量中：

   • \(x_1\) 指保单持有人的性别，1 表示男性，2 表示女性；
   • \(x_2\) 指年龄，1 表示 25 岁以下，2 表示 25 到 40 岁，3 表示 40 到 60 岁，4 表示 60 到 70 岁，5 表示 70 岁以上；
   • \(x_3\) 指最喜欢的音乐类型，1 表示古典，2 表示乡村或轻音乐，3 表示说唱或重金属；
   • \(x_4\) 指教育程度，1 表示未高中毕业，2 表示高中毕业但未大学毕业，3 表示大学毕业但无更高学位，4 表示研究生学位；
   • \(x_5\) 指身体质量指数（BMI），1 表示 22 以下，2 表示 22 到 27，3 表示 27 到 33，4 表示 33 以上；
   • \(x_6\) 指身高，1 表示 5 英尺 2 英寸以下，2 表示 5 英尺 2 英寸到 5 英尺 8 英寸，3 表示 5 英尺 8 英寸到 6 英尺，4 表示 6 英尺以上；
   • \(x_7\) 指每年驾驶里程，1 表示低，2 表示中，3 表示高。

   以下是仅与上述特征向量的前 2 个坐标相关的历史随机样本。对于每个向量 \((x_1, x_2)\)，它给出了具有该向量的保单持有人人数，以及其中在过去一年中至少发生过一次事故的人数。

   向量	保单持有人数	发生事故人数
   (1,1)	240	9
   (1,2)	1050	18
   (1,3)	1400	20
   (1,4)	457	15
   (1,5)	145	12
   (2,1)	226	5
   (2,2)	940	12
   (2,3)	1420	14
   (2,4)	420	11
   (2,5)	142	13

   1. 使用朴素贝叶斯方法估计一位 36 岁的女性在未来一年内发生事故的概率。
   2. 使用朴素贝叶斯方法的改进版本来估计一位 36 岁的女性在未来一年内发生事故的概率。
   3. 使用朴素贝叶斯方法估计一位 26 岁的男性在未来一年内发生事故的概率。
   4. 使用朴素贝叶斯方法的改进版本来估计一位 24 岁的男性在未来一年内发生事故的概率。

2. 在前一个问题中，使用加权距离法估计以下人员在未来一年内发生事故的概率：

   1. 一位 36 岁的女性；
   2. 一位 26 岁的男性。

3. 使用 章节 16.5 的损失函数方法，评估哪种技术（朴素贝叶斯法或加权距离法）最适合估计以下人员的概率：

   1. 一位 36 岁的女性在未来一年内发生事故；
   2. 一位 26 岁的男性在未来一年内发生事故。 在所有情况下，请使用除当前考虑的个体数据值以外的所有数据，来估计具有该特征向量的人发生事故的概率。

4. 对于上表（习题 1 的表格）中给出的 6440 个数据值中的每一个，请确定当其事故概率是通过使用其他 6439 个值的数据通过以下方法估计时所产生的损失：

   1. 朴素贝叶斯法；
   2. 加权距离法。
   3. 在本例中哪种方法效果更好？

5. 虽然 章节 16.5 中提出的损失函数假设在发生估计概率为 \(p\) 的事件时会产生损失 \((1 - p)^2\)，但另一种流行的损失函数假设在发生估计概率为 \(p\) 的事件时会产生损失 \(-\log(p)\)。证明后一种损失函数也具有如下性质：如果事件发生的实际（虽然未知）概率为 \(\alpha\)，那么当 \(p = \alpha\) 时，期望损失最小。

6. 收集定量的真实数据，并研究逻辑回归或最近邻规则是否能产生更好的结果。

7. 假设药物 1 已被使用 55 次，其中 36 次成功；药物 2 已被使用 22 次，其中 12 次成功。章节 16.7 的程序下一步使用药物 1 的概率是多少？使用 R 进行随机选择。