- P18
- P23
- P25
P18
可以好好想一下ROC曲线是如何形成的：我们设置不同的二分类的阈值，就会有不同的(TPR,FPR)对；如果我们将所有数据按照其置信度从大到小排序，然后让阈值逐渐减小，并在ROC曲线上进行描点，那么我们可以发现，如果遇到一个正例，那么当前点会竖直向上走\(\frac{1}{m_+}\)，如果遇到一个负例，那么当前点会水平向右走\(\frac{1}{m_-}\)；所以真正的ROC曲线一定是由一个一个小矩形组成的（不会画出像PPT里面的那种折线图）；我们要算AUC，那么只需要把这些小矩形的面积全部加起来就可以了；根据上面的分析，小矩形宽度和高度的增量都是固定的，所以我们只需要算出满足负例得分比正例得分低的正负例对的数量即可（就是说，现在有一个正负例对，如果这个正例的置信度比负例高，那么计数器就加一，否则计数器不变），这个样子统计出来就是AUC=\(\frac{1}{m_+\times m_-}\sum\sum I(f(x^+)>f(x^-))\)，也就是PPT里面那个式子的等价形式
有了上面的过程就不难理解为什么AUC越大越好了，这就说明正例和负例之间分的很开，就很好区分（如果AUC为1那么就是完全可分的情形），如果AUC很低，那么正例和负例之间就夹杂在一起了
P23
假设现在有多个数据集，然后有三个算法，每个算法在每个数据集上进行测试，于是可以求出每个算法在所有数据集上测试分数的平均，PPT里说的平均序值就是这个平均
伸出来的那个线是
P25
我们来给出一个非常严格和形式化的机器学习泛化误差定义。
在统计学习理论的框架下，我们通常假设数据 \((x, y)\) 从一个固定的、未知的概率分布 \(\mathcal{D}\) 中独立同分布（i.i.d.）地采样得到。
设：
- \(\mathcal{X}\) 为输入空间（特征空间）。
- \(\mathcal{Y}\) 为输出空间（标签空间）。
- \(\mathcal{D}\) 是 \(\mathcal{X} \times \mathcal{Y}\) 上的联合概率分布。
- \(\mathcal{H}\) 为假设空间（Hypothesis Space），是我们考虑的所有可能模型的集合。一个假设 \(h \in \mathcal{H}\) 是一个从 \(\mathcal{X}\) 到 \(\mathcal{Y}\) 的映射（\(h: \mathcal{X} \rightarrow \mathcal{Y}\)）。
- \(l: \mathcal{Y} \times \mathcal{Y} \rightarrow \mathbb{R}^{+}\) 是一个非负的损失函数（Loss Function），用于度量预测值 \(h(x)\) 与真实值 \(y\) 之间的差异。常见的例子包括0-1损失（\(l(h(x), y) = \mathbb{I}[h(x) \neq y]\)）和平方损失（\(l(h(x), y) = (h(x) - y)^2\)）。
给定一个假设 \(h \in \mathcal{H}\)，我们定义两个关键的误差概念：
1. 经验误差 (Empirical Error / Risk)
经验误差是假设 \(h\) 在某个给定的、有限的训练样本集 \(S = \{(x_1, y_1), (x_2, y_2), ..., (x_m, y_m)\}\)（从 \(\mathcal{D}\) 中采样得到）上的平均损失。
这是一个我们可以直接从数据中计算得到的、可观测的量。
2. 期望误差 / 泛化误差 (Expected Error / Generalization Error)
泛化误差是假设 \(h\) 在整个数据分布 \(\mathcal{D}\) 上的期望损失。它衡量的是当面对从分布 \(\mathcal{D}\) 中随机抽取的、在训练时未曾见过的新数据样本时，模型 \(h\) 的预期表现。
严格来说，这里的期望 \(\mathbb{E}\) 是在分布 \(\mathcal{D}\) 上关于 \((x, y)\) 的联合分布求取的。
3. 泛化误差 Gap (Generalization Gap)
泛化误差 Gap 定义为期望误差（真实误差）与经验误差（训练误差）之间的差异：
机器学习算法的终极目标是找到一个假设 \(h\)，使得其泛化误差 \(R(h)\) 尽可能小。然而，我们无法直接计算 \(R(h)\)，因为我们不知道真实的分布 \(\mathcal{D}\)。我们只能通过计算 \(\hat{R}_S(h)\) 来近似它，并通过在保留的测试集上评估性能来无偏地估计它。我们通常考虑期望泛化误差 \(\mathbb{E}_D [R(h_D)]\)，其中\(D\)是从 \(\mathcal{D}\)中随机抽样的数据集（也就是说\(D\)是一个随机变量）。
我们注意到：
-
期望泛化误差可以对输入 \(x\) 取期望：首先对 \(y\) 给定 \(x\) 取期望，然后再对 \(x\) 取期望。即：
\[\mathbb{E}_D [R(h_D)] = \mathbb{E}_D \left[ \mathbb{E}_{(x, y) \sim \mathcal{D}} \left[ (h_D(x) - y)^2 \right] \right] = \mathbb{E}_x \left[ \mathbb{E}_{D, y|x} \left[ (y - \hat{f}(x; D))^2 \right] \right] \]上面过程的推导如下
-
泛化误差的定义：
对于一个固定的训练集 \(D\)，模型 \(h_D\) 的泛化误差 \(R(h_D)\) 定义为在数据分布 \(\mathcal{D}\) 上的期望损失（使用平方损失）：\[R(h_D) = \mathbb{E}_{(x, y) \sim \mathcal{D}} \left[ (h_D(x) - y)^2 \right] \]其中 \((x, y)\) 是从分布 \(\mathcal{D}\) 中独立采样的测试数据点。
-
期望泛化误差：
由于训练集 \(D\) 本身是从 \(\mathcal{D}\) 中随机采样的，我们关心的是期望泛化误差，即对 \(D\) 取期望：\[\mathbb{E}_D [R(h_D)] = \mathbb{E}_D \left[ \mathbb{E}_{(x, y) \sim \mathcal{D}} \left[ (h_D(x) - y)^2 \right] \right] \] -
分解联合期望：
内部的期望 \(\mathbb{E}_{(x, y) \sim \mathcal{D}} [\cdot]\) 是对联合分布取的。根据概率论，联合期望可以分解为先对 \(x\) 取期望，再对 \(y\) 给定 \(x\) 取期望：\[\mathbb{E}_{(x, y) \sim \mathcal{D}} \left[ (h_D(x) - y)^2 \right] = \mathbb{E}_{x} \left[ \mathbb{E}_{y|x} \left[ (h_D(x) - y)^2 \right] \right] \]这里，\(\mathbb{E}_{x}\) 表示对 \(x\) 的边缘分布 \(p(x)\) 取期望，\(\mathbb{E}_{y|x}\) 表示在给定 \(x\) 下对 \(y\) 的条件分布 \(p(y|x)\) 取期望。
-
代入期望泛化误差：
将上述分解代入期望泛化误差：\[\mathbb{E}_D [R(h_D)] = \mathbb{E}_D \left[ \mathbb{E}_{x} \left[ \mathbb{E}_{y|x} \left[ (h_D(x) - y)^2 \right] \right] \right] \] -
交换期望顺序：
我们可以交换期望顺序。具体地，将 \(\mathbb{E}_{x}\) 提到外层：\[\mathbb{E}_D \left[ \mathbb{E}_{x} \left[ \cdot \right] \right] = \mathbb{E}_{x} \left[ \mathbb{E}_D \left[ \cdot \right] \right] \]因此：
\[\mathbb{E}_D [R(h_D)] = \mathbb{E}_{x} \left[ \mathbb{E}_D \left[ \mathbb{E}_{y|x} \left[ (h_D(x) - y)^2 \right] \right] \right] \] -
合并内部期望：
内部的期望 \(\mathbb{E}_D \left[ \mathbb{E}_{y|x} \left[ \cdot \right] \right]\) 涉及两个随机变量：训练集 \(D\) 和条件输出 \(y|x\)。我们可以将这两个期望合并为一个联合期望：\[\mathbb{E}_D \left[ \mathbb{E}_{y|x} \left[ (h_D(x) - y)^2 \right] \right] = \mathbb{E}_{D, y|x} \left[ (h_D(x) - y)^2 \right] \]这里，\(\mathbb{E}_{D, y|x}\) 表示对 \(D\) 和 \(y\) 给定 \(x\) 的联合分布取期望。
-
最终形式：
代入上式，得到：\[\mathbb{E}_D [R(h_D)] = \mathbb{E}_{x} \left[ \mathbb{E}_{D, y|x} \left[ (y - h_D(x))^2 \right] \right] \]通常，我们用 \(\hat{f}(x; D)\) 表示模型预测，即 \(\hat{f}(x; D) = h_D(x)\)，因此：
\[\mathbb{E}_D [R(h_D)] = \mathbb{E}_{x} \left[ \mathbb{E}_{D, y|x} \left[ (y - \hat{f}(x; D))^2 \right] \right] \]
-
-
从点误差分解中，我们知道对于每个 \(x\)，有：
\[\mathbb{E}_{D, y|x} \left[ (y - \hat{f}(x; D))^2 \right] = \text{bias}^2(x) + \text{var}(x) + \sigma^2 \]这是因为：
假设数据生成过程遵循以下形式：- 真实模型： $ y = f(x) + \epsilon $，其中 $ f(x) $ 是真实的潜在函数，$ \epsilon $ 是噪声项，满足 $ \mathbb{E}[\epsilon] = 0 $ 和 $ \mathbb{E}[\epsilon^2] = \sigma^2 $（即噪声方差为 $ \sigma^2 $)。这个真实模型取决于我们的定义，比如说让泛化误差最小的，或者其他的满足特定条件的模型，反正就是我们想要的那个模型
- 学习算法从训练集 $ D $ 中学习得到预测函数 \(\hat{f}(x; D)\)。这里，\(D\) 是从真实分布中独立同分布（i.i.d.）采样的训练集，因此 \(\hat{f}(x; D)\) 是一个随机变量（依赖于 \(D\)）。
对于固定的输入 $ x $，泛化误差（期望预测误差）定义为：
\[E(f; D) = \mathbb{E}_{D, y} \left[ (y - \hat{f}(x; D))^2 \right] \]其中期望是对训练集 $ D $ 和测试输出 $ y $（给定 $ x $）的联合求取。由于 $ y $ 和 $ D $ 独立，我们可以先对 $ y $ 求期望，再对 $ D $ 求期望。
步骤1: 对 $ y $ 求期望（固定 $ D $ 和 $ x $）
令 $ \hat{f} = \hat{f}(x; D) $，对于固定 $ D $ 和 $ x $，有：\[\mathbb{E}_{y | x} \left[ (y - \hat{f})^2 \right] = \mathbb{E}_{y | x} \left[ (y - f(x) + f(x) - \hat{f})^2 \right] \]展开平方项：
\[= \mathbb{E}_{y | x} \left[ (y - f(x))^2 + 2 (y - f(x))(f(x) - \hat{f}) + (f(x) - \hat{f})^2 \right] \]由于 \(\mathbb{E}_{y | x}[y] = f(x)\)，所以 \(\mathbb{E}_{y | x}[y - f(x)] = 0\)，中间项为零：
\[= \mathbb{E}_{y | x} \left[ (y - f(x))^2 \right] + (f(x) - \hat{f})^2 \]第一项是噪声方差： $ \mathbb{E}_{y | x} \left[ (y - f(x))^2 \right] = \sigma^2 $，因此：
\[\mathbb{E}_{y | x} \left[ (y - \hat{f})^2 \right] = \sigma^2 + (f(x) - \hat{f})^2 \]步骤2: 对 $ D $ 求期望
现在对训练集 $ D $ 求期望：\[\mathbb{E}_{D} \left[ \mathbb{E}_{y | x} \left[ (y - \hat{f})^2 \right] \right] = \mathbb{E}_{D} \left[ \sigma^2 + (f(x) - \hat{f})^2 \right] = \sigma^2 + \mathbb{E}_{D} \left[ (f(x) - \hat{f})^2 \right] \]定义平均预测函数： \(\bar{f}(x) = \mathbb{E}_{D} \left[ \hat{f}(x; D) \right]\)，则分解 $ \mathbb{E}_{D} \left[ (f(x) - \hat{f})^2 \right] $：
\[\mathbb{E}_{D} \left[ (f(x) - \hat{f})^2 \right] = \mathbb{E}_{D} \left[ (f(x) - \bar{f}(x) + \bar{f}(x) - \hat{f})^2 \right] \]展开平方项：
\[= \mathbb{E}_{D} \left[ (f(x) - \bar{f}(x))^2 + 2 (f(x) - \bar{f}(x))(\bar{f}(x) - \hat{f}) + (\bar{f}(x) - \hat{f})^2 \right] \]由于 \(\mathbb{E}_{D} [\hat{f}] = \bar{f}(x)\)，所以 $\mathbb{E}_{D} [\bar{f}(x) - \hat{f}] = 0 $，中间项为零：
\[= (f(x) - \bar{f}(x))^2 + \mathbb{E}_{D} \left[ (\bar{f}(x) - \hat{f})^2 \right] \]这里：
- 第一项是偏差的平方： $ \text{bias}^2(x) = (f(x) - \bar{f}(x))^2 $，表示平均预测与真实值的差异。
- 第二项是方差： $ \text{var}(x) = \mathbb{E}_{D} \left[ (\hat{f} - \bar{f}(x))^2 \right] $，表示预测值围绕平均预测的波动。
因此，泛化误差为：
\[E(f; D) = \sigma^2 + \text{bias}^2(x) + \text{var}(x) \]与图中的式子对应：
\[E(f; D) = \text{bias}^2(x) + \text{var}(x) + \varepsilon^2 \]其中 $ \varepsilon^2 = \sigma^2 $ 是噪声方差。
-
因此，代入上式：
\[\mathbb{E}_D [R(h_D)] = \mathbb{E}_x \left[ \text{bias}^2(x) + \text{var}(x) + \sigma^2 \right] \]
这意味着整体泛化误差是所有点 \(x\) 的误差（偏差平方、方差和噪声）的平均值，其中平均是针对输入分布 \(p(x)\) 取的。换句话说，整体误差是点误差在输入空间上的积分或加权平均，权重由 \(p(x)\) 决定。于是我们要研究泛化误差，就可以研究点误差。
读了上面的文字之后，有一点很重要，就是我们要知道，泛化误差这个东西不是衡量一个具体的模型怎么样，而是去衡量一个算法他怎么样。所以我们需要采集很多个数据集（也就是把\(D\)当做一个随机变量），期望是在\(D\)上面求的。关于CS229对偏差和方差的解释一和解释二也是从\(D\)是一个随机变量的角度出发的
)
)
)
