机器学习理论：假设评估¶

定义 1：实例空间（Instance Space）\(X\)

所有可能的实例（样本）构成的集合。例如：每一天由属性（天空、气温、湿度、风、水、预报）描述，则 \(X\) 为所有可能的属性组合。

定义 2：假设空间（Hypothesis Space）\(H\)

学习器可能输出的所有假设的集合。例如：一个假设可以是 if (温度 = 寒冷 AND 湿度 = 高) then 打网球 = 否。

定义 3：样例空间（Sample Space）\(S\)

实际能够获取到的样例集合，是 \(X\) 的子集。即 \(S \subseteq X\)。

定义 4：目标概念（Target Concept）\(c\)

样例的真实标记函数 \(c: X \to \{0, 1\}\)（二分类情形）。给定标注样本 \(\langle x_1, c(x_1)\rangle, \dots, \langle x_m, c(x_m)\rangle\)。

定义 5：真实错误率（True Error）\(\text{error}_D(h)\)

假设 \(h\) 在分布 \(D\) 下误分类一个随机采样实例的概率：

定义 6：样本错误率（Sample Error）\(\text{error}_S(h)\)

假设 \(h\) 在样本集 \(S\) 上的错误率，可直接观测：

其中 \(\delta(\cdot)\) 是指示函数，条件成立时为 \(1\)，否则为 \(0\)。

Q1.1 最佳估计

给定一个假设在有限量数据上的准确率，能否准确估计它在其他未见数据（同实例空间）上的效果？

Q1.2 估计的不确定性

该准确率的估计可能包含多少错误？即 \(\text{error}_S(h)\) 对 \(\text{error}_D(h)\) 的估计有多好？

问题 2

\(h_1\) 在数据的一个样本集上表现优于 \(h_2\)，\(h_1\) 总体上更好的概率有多大？

问题 3

如何最好地使用有限数据 —— 既用于学习，也用于评估？数据分布可能与真实情况不同。

定义 7：伯努利实验

只有两种输出的随机实验：成功（概率 \(p\)）或失败（概率 \(q = 1-p\)）。用随机变量 \(X\) 记录成功次数。

定义 8：二项分布 \(B(n, p)\)

\(n\) 次独立伯努利实验中成功次数 \(R\) 的分布：

适用条件

• 两个可能的输出（\(Y = 0\) 或 \(Y = 1\)）
• 每次尝试成功概率相等：\(\Pr(Y_i = 1) = p\)，\(p\) 为常数
• \(n\) 次独立尝试，随机变量 \(Y_1, \dots, Y_n\) 独立同分布（i.i.d.）

定义 9：估计的偏差（Bias）

定义 10：估计的方差（Variance）

定义 11：置信区间（Confidence Interval）

参数 \(p\) 的 \(N\%\) 置信区间是一个以 \(N\%\) 的概率包含 \(p\) 的区间。\(N\%\) 称为 置信度（Confidence Level）。

正态分布 \(\mathcal{N}(\mu, \sigma^2)\)

概率密度函数：

• \(\mathbb{E}[Y] = \mu\)
• \(\operatorname{Var}[Y] = \sigma^2\)

正态分布的置信区间

• 80% 的面积落在区间 \(\mu \pm 1.28\sigma\)
• \(N\%\) 的面积落在区间 \(\mu \pm z_N \sigma\)，其中 \(z_N\) 以标准差为单位给定了区间一半的宽度

真实错误率的置信区间

若满足条件：\(S\) 包含 \(n \geq 30\) 个样本，与 \(h\) 独立产生，且每个样本独立采样，则有约 95% 的概率 \(\text{error}_D(h)\) 落在区间：

双边置信区间（Two-sided）

同时给出上限和下限：\(\Pr(L \leq p \leq U) = 1 - \alpha\)。

单边置信区间（One-sided）

只关心单侧边界：\(\Pr(p \leq U) = 1 - \alpha/2\) 或 \(\Pr(p \geq L) = 1 - \alpha/2\)。

问题 1 完整解答

设定： - \(S\)：\(n\) 个随机独立样本，且独立于假设 \(h\) - \(h\) 在 \(S\) 上有 \(r\) 个错误 - \(n \geq 30\) 且 \(n \cdot \frac{r}{n} \cdot (1 - \frac{r}{n}) > 5\)

结论：真实错误率 \(\text{error}_D(h)\) 以 \(N\%\) 置信度落在区间

其中 \(\text{error}_S(h) = \frac{r}{n}\)。

一般步骤

1. 确定需要估计的变量 \(p\)，例如 \(\text{error}_D(h)\)
2. 确定估计量 \(Y\)（需考虑其偏差和方差），例如 \(\text{error}_S(h)\)
3. 选择方差尽可能小的 无偏估计
4. 确定 \(Y\) 的分布 \(D_Y\)（包括均值和方差）
5. 确定 \(N\%\) 置信区间 \([L, U]\)
6. 可能有 \(L = -\infty\) 或 \(U = \infty\)
7. 对于正态分布，利用 \(z_N\) 表查询相关值
8. 此方法可应用于其他类似问题

定理 1：中心极限定理（CLT）

设 \(Y_1, Y_2, \dots, Y_n\) 为独立同分布（i.i.d.）的随机变量，来自 任意分布，具有均值 \(\mu\) 和有限方差 \(\sigma^2\)。

定义样本均值 \(\bar{Y}_n = \frac{1}{n}\sum_{i=1}^{n} Y_i\)。则当 \(n \to \infty\) 时：

等价地，标准化后收敛到标准正态分布：

问题 2

\(h_1\) 在数据的一个样本集上表现优于 \(h_2\)，\(h_1\) 总体上更好的概率有多大？

定义 12：错误率差异估计量 \(\hat{d}\)

其期望为真实错误率之差：

\(\hat{d}\) 是 \(d\) 的 无偏估计。

\(\hat{d}\) 的分布

由中心极限定理，\(\text{error}_{S_1}(h_1)\) 和 \(\text{error}_{S_2}(h_2)\) 均近似正态分布。两个独立正态随机变量之差仍为正态分布，因此 \(\hat{d}\) 也近似服从正态分布：

其中方差为两估计量方差之和：

假设检验（Hypothesis Test）

判断某个陈述为真的概率。例如：\(\text{error}_D(h_1) > \text{error}_D(h_2)\) 的概率，即 \(d > 0\) 的概率。

\(z\) 检验步骤

1. 计算 \(\hat{d} = \text{error}_{S_1}(h_1) - \text{error}_{S_2}(h_2)\)
2. 估计标准差 \(\sigma_{\hat{d}}\)
3. 计算 \(z_N = \hat{d} / \sigma_{\hat{d}}\)
4. 查正态分布表得双边置信度，转换为单边置信度

问题 3

如何最好地使用有限数据 —— 既用于学习，也用于评估？数据分布可能与真实情况不同。

定义 13：\(k\) 折交叉验证

将数据集 \(D_0\) 划分为 \(k\) 个大小相等、互不相交的子集，每个子集至少 30 个样本。依次以每个子集作为测试集，其余 \(k-1\) 个子集作为训练集，进行 \(k\) 次训练和测试。

定义 14：两样本 \(t\) 检验（Welch's \(t\)-test）

设模型 \(h_1\) 的 \(n_1\) 次重复实验结果 \(x_{11}, x_{12}, \dots, x_{1n_1}\)，样本均值 \(\bar{x}_1\)，样本方差 \(s_1^2\)；模型 \(h_2\) 同理。

在样本量和方差不等的假设下：

自由度：

根据 \(t\) 和 \(df\) 查 \(t\) 分布表可得置信度。

定义 15：配对 \(t\) 检验

若 \(n_1 = n_2 = n\) 且 \(d_i = x_{1i} - x_{2i}\) 独立且来自正态分布（即两个模型在 同样划分 的交叉验证或同样测试集的重复对比实验），可使用更强大的配对 \(t\) 检验：

自由度为 \(n - 1\)。