[机器学习西瓜书] 第02章 模型评估与选择 笔记

人工智能AI|计算机 ComputerScience

   
   

@ZYX 写于2020年07月30日

第02章 模型评估与选择

2.1 经验误差与过拟合

  • 错误率
    分类错误的样本数占样本总数的比例称为”错误率”(error rate)

    • 如果在$m$个样本中有$a$个样本分类错误,则错误率$E=a/m$;
    • 精度
      $1-a/m$ 称为”精度”(accuracy)
      即”精度=1一错误率”
  • 误差
    学习器的实际预测输出与样本的真实输出之间的差异称为”误差” (error)

    • 训练误差||经验误差
      学习器在训练集上的误差称为”训练误差”(training error)或”经验误差”(empirical error)

      • 由于无法做到泛化误差最小号,实际能做的是努力使经验误差最小化
    • 泛化误差
      新样本上的误差称为”泛化误差”(generalization error).

      • 显然,我们希望得到泛化误差小的学习器
  • 过拟合
    训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质,称为”过拟合” (overfitting).

    • 这样就会导致泛化性能下降
    • 是机器学习面临的关键障碍
    • 无法彻底避免的,能做的只是”缓解”
      • 机器学习面临的问题通常是NP难甚至更难
    • 欠拟合
      “欠拟合” (underfitting) 是指对训练样本的一般性质尚未学好.

      • 通常是由于学习能力低下
      • 欠拟合较容易克服
  • 模型选择问题
    该选用哪一个学习算法、使用哪一种参数配置? 这是”模型选择”(model selection)问题

    • 解决
      1. 评估候选模型的泛化误差
      2. 选择泛化误差最小的那个模型

2.2 评估方法

  • 需使用一个测试集(testing set)来测试学习器对新样本的判别能力
    • 以测试集上的测试误差(testing error)作为泛化误差的近似
    • 假设测试样本也是从样本真实分布中独立同分布采样而得
    • 应尽可能与训练集互斥
    • 数学表达
      • 包含$m$个样例的数据集$D=\{(x_{1},y_{1}),(x_{2},y_{2}), \cdots, (x_{m},y_{m})\}$
      • 通过对$D$进行适当的处理,从中产生出
        1. 训练集$S$
        2. 测试集$T$

2.2.1 留出法

  • 直接将数据集D划分为两个互斥的集合:其中一个集合作为训练集S,另一个作为测试集T,
    即$D=S∪T, S∩T=\empty$
  • 训练/测试集的划分要尽可能保持数据分布的一致性,避免因数据划分过程引入额外的偏差而对最终结果产生影响,
    • 例:在分类任务中,至少要保持样本的类别比例相似.
      • 分层采样
        保留类别比例的采样方式通常称为”分层采样” (stratified sampling).
  • 一般要采用若干次随机划分、重复进行实验评估后取平均值作为留出法的评估结果
    • 单次使用留出法得到的估计结果不够稳定可靠
  • 窘境
    • 若令训练集S包含绝大多数样本
      • 则训练出的模型可能更接近于用D训练出的模型
      • 但由于T比较小评估结果可能不够稳定准确
    • 若令测试集T多包含一些样本, 则训练集SD差别更大了,被评估的模型与用D训练出的模型相比可能有较大差别,从而降低了评估结果的保真性(fidelity)
    • 常见做法是将大约2/3~4/5的样本用于训练,剩余样本用于测试.

2.2.2 交叉验证法

  • 步骤
    1. 数据集D划分为$k$个大小相似的互斥子集(也就是partition)
      • 每个子集$D_{i}$都尽可能保持数据分布的一致性, 即从D中通过分层采样得到.
    2. 每次用$k-1$个子集的并集作为训练集,剩余的那个子集作为测试集;
      • 可获得k组训练/测试集
    3. 进行$k$ 次训练和测试
    4. 返回这$k$ 个测试结果的均值
  • 评估结果的稳定性和保真性在很大程度上取决于k的取值
    • 通常称为”k折交叉验证” (k-fold cross validation)
    • k最常用的取值是10
  • 为减小因样本划分不同而引入的差别,k折交叉验证通常要
    1. 随机使用不同的划分重复$p$ 次
    2. 最终的评估结果是这$p$ 次k折交叉验证结果的均值
    • 常见的有”10次10折交叉验证”
  • 特例:留一法(Leave-One-Out,简称LOO)
    令$k=m$

    • 留一法不受随机样本划分方式的影响(每个只有1个样本)
    • 缺点
      • 在数据集比较大时,训练$m$ 个模型的计算开销可能是难以忍受的
      • 估计结果也未必永远比其他评估方法准确
        • 没有免费的午餐定理对实验评估方法同样适用.

2.2.3 自助法

  • 步骤
    1. 对它进行采样产生数据集$D’$
      1. 每次随机从D中挑选一个样本,将其拷贝放入D’
      2. 将该样本放回D中,使得该样本在下次采样时仍可被采到
      3. 重复执行$m$ 次
      • 得到包含$m$ 个样本的数据集$D’$,
      • 样本在m次采样中始终不被采到的概率是$(1-1/m)^{m}$ ——取极限得$\lim_{m \rightarrow \infty}\left(1-\frac{1}{m}\right)^{m} \mapsto \frac{1}{e} \approx 0.368$
        • 即D中约有36.8%的样本未出现在D’中
    2. 将D’用作训练集, D\D'(D-D’)用作测试集
  • 包外估计
    约1/3数据没在训练集中出现的样本用于测试.这样的测试结果,亦称”包外估计”(out-of-bag estimate)
  • 优点
    • 在数据集较小、难以有效划分训练/测试集时很有用
    • 能从初始数据集中产生多个不同的训练集,这对集成学习等方法有很大的好处.
  • 缺点
    • 改变了初始数据集的分布,这会引入估计偏差

2.2.4 调参与最终模型

  • 大多数学习算法都有些参数(parameter)需要设定
    • 参数配置不同,学得模型的性能往往有显著差别
  • 调参
    对算法参数进行设定,这就是通常所说的”参数调节”或简称”调参”(parameter tuning).
  • 学习算法的很多参数是在实数范围内取值
    • 对每种参数配置都训练出模型来是不可行的
    • 所以对每个参数选定一个范围变化步长
      • 选定的参数值往往不是”最佳”值
      • 是在计算开销性能估计之间进行折中的结果
        • 通过这个折中,学习过程才变得可行
  • 验证集
    模型评估与选择中用于评估测试的数据集,称为”验证集”(validation set).

2.3 性能度量

  • 衡量模型泛化能力的评价标准,这就是性能度量(performance measure)
  • 性能度量反映了任务需求
    • 这意味着模型的”好坏”是相对的
  • 数学表达
    • 样例集$D=\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots ,(x_{m},y_{m})\}$
      • $y_{i}$ 是示例$x_{i}$ 的真实标记
      • $f(x)$ 学习器预测结果
  • 均方误差”
    • 回归任务最常用的性能度量是”均方误差” (mean squared error)
      $E(f;D)=\frac{1}{m} \sum_{i=1}^{m}(f(x_{i})-y_{i})^{2}$
    • 一般化
      • 对于数据分布 $\mathcal{D}$概率密度函数 $p(\cdot)$
        $E(f ; \mathcal{D})=\int_{\boldsymbol{x} \sim \mathcal{D}}(f(\boldsymbol{x})-y)^{2} p(\boldsymbol{x}) \mathrm{d} \boldsymbol{x}$

2.3.1 错误率与精度

  • 错误率是分类错误的样本数占样本总数的比例
    • 定义:
      $E(f ; D)=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(f\left(\boldsymbol{x}_{i}\right) \neq y_{i}\right)$
    • 一般化
      $E(f ; \mathcal{D})=\int_{\boldsymbol{x} \sim \mathcal{D}} \mathbb{I}(f(\boldsymbol{x}) \neq y) p(\boldsymbol{x}) \mathrm{d} \boldsymbol{x}$
  • 精度则是分类正确的样本数占样本总数的比例
    • 定义
      $\begin{aligned} \operatorname{acc}(f ; D) &=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(f\left(\boldsymbol{x}_{i}\right)=y_{i}\right) \\ &=1-E(f ; D) \end{aligned}$
    • 一般化
      $\begin{aligned} \operatorname{acc}(f ; \mathcal{D}) &=\int_{\boldsymbol{x} \sim \mathcal{D}} \mathbb{I}(f(\boldsymbol{x})=y) p(\boldsymbol{x}) \mathrm{d} \boldsymbol{x} \\&=1-E(f ; \mathcal{D}) \end{aligned}$

2.3.2 查准率、查全率与Fl

  • 对于二分类问题,可将样例根据其真实类别与学习器预测类别的组合划分为
    1. 真正例(true positive) $TP$
    2. 假正例(false positive) $FP$
    3. 真反倒(true negative) $TN$
    4. 假反例(false negative) $FN$
    • TP+FP+TN+FN=样例总数
  • 分类结果的混淆矩阵(confusion matrix)
    | 真实情况 | 预测结果 | 预测结果 |
    | :————: | :————: | :————: |
    | \ | 正例 | 反例 |
    | 正例 | TP(真正例) | FN (假反例) |
    | 反例 | FP(假正例) | TN (真反例) |
  • 公式
    • 查准率 $P=\frac{TP}{TP+FP}$
    • 查全率 $R=\frac{TP}{TP+FN}$
    • 查准率和查全率是一对矛盾的度量,往往成反比
P-R图

图2.3 P-R曲线与平衡点示意图
– 可根据学习器的预测结果对样例进行排序
– 前面是被认为”最可能”是正例的样本
– 最后是被认为”最不可能”是正例的样本
P-R曲线
– 按排序逐个把样本作为正例进行预测,则每次可以计算出:
纵轴:查准率
横轴:查全率
– 就得到查准率-查全率曲线,简称”P-R曲线”
包住: 若一个的P-R曲线被另一个的完全”包住”,则可断言后者的性能优于前者
交叉: 如果两个学习器的P-R曲线发生了交叉,这时比较P-R曲线节面积的大小
平衡点
“平衡点” (Break-Event Point,简称BEP)是查准率==查全率时的取值
– BEP在外的更好
F1度量:
$F1=\frac{2\times P\times R}{P+R}=\frac{2\times TP}{|D|+TP-TN}$
– Fl 是基于查准率与查全率的调和平均(harinonicmean)定义的:
$\frac{1}{F 1}=\frac{1}{2} \cdot\left(\frac{1}{P}+\frac{1}{R}\right)$
– F1度量的一般形式——$F_{\beta}$
$F_{\beta}=\frac{\left(1+\beta^{2}\right) \times P \times R}{\left(\beta^{2} \times P\right)+R}$
– $\beta >0$ 度量了查全率对查准率的相对重要性
– $\beta =1$: 就是F1
– $\beta >1$: 查全率R更重要
– $\beta <1$: 查准率P更重要
– $n$ 个二分类混淆矩阵上综合考察查准率和查全率
– 第一种:在各混淆矩阵上分别计算出查准率和查全率
– 记为$\left(P_{1}, R_{1}\right),\left(P_{2}, R_{2}\right), \ldots,\left(P_{n}, R_{n}\right)$
宏查准率: $macro-P=\frac{1}{n}\sum_{i=1}^{n}P_{i}$
宏查全率: $macro-R=\frac{1}{n}\sum_{i=1}^{n}R_{i}$
宏F1: $macro-F1=\frac{2\times macroP\times macroR}{macroP+macroR}$
– 第二种:将各泪淆矩阵的对应元素进行平均
– 得到 $\overline{T P}, \overline{F P}, \overline{T N}, \overline{F N}$
微查准率:$microP=\frac{\overline{TP}}{\overline{TP}+\overline{FP}}$
徽查全率: $microR=\frac{\overline{TP}}{\overline{TP}+\overline{FN}}$
微F1: $micro-F1=\frac{2\times microP\times microR}{microP+microR}$

2.3.3 ROC与AUC

  • 很多学习器是
    1. 为测试样本产生一个实值或概率预测
    2. 然后将这个预测值与一个分类阔值(threshold)进行比较
      • 若大于阈值则分为正类
      • 否则为反类
  • 过程就相当于在这个排序中以某个”截断点” (cut point)将样本分为两部分
    • 前一部分判作正例,后一部分则判作反例.
    • 在不同的应用任务中,我们可根据任务需求来采用不同的截断点
      • 排序本身的质量,体现了综合考虑学习器在不同任务下的”期望泛化性能
ROC
  • 全称是”受试者工作特征”(Receiver Operating Characteristic)曲线
  • 纵轴:真正例率 (True Positive Rate,简称TPR)
  • 横轴:假正例率 (False Positive Rate,简称FPR)
  • TPR与FPR
    • $TPR=\frac{TP}{TP+FN}$
    • $FPR=\frac{FP}{TN+FP}$
  • ROC图
    • 显示ROC曲线的图称为”ROC 图”
      图2.4 ROC 曲线与AUC 示意图
    • 无法产生光滑ROC 曲线,只能绘制近似ROC曲线()
    • 步骤
      • 给定 $m^{+}$ 个正例和 $m^{-}$ 个反例,
      1. 根据学习器预测结果对样例进行排序
      2. 把分类阔值设为最大,即把所有样例均预测为反例
        • 此时真正例率和假正例率均为0,
        • 在坐标(0,0)处标记一个点
      3. 然后,将分类阐值依次设为每个样例的预测值,即依次将每个样例划分为正例
        • 设前一个标记点坐标为(x,y)
          • 当前若为真正例,则对应标记点的坐标为 $(x,y+\frac{1}{m^{+}})$;
          • $(x\frac{1}{m^{-}},y)$
    • 包住:若一个的ROC曲线被另一个的曲线完全”包住”,则后者的性能优
    • 若两个学习器的ROC曲线发生交叉:
      • 比较ROC曲线下的面积,即AUC(Area Under ROC Curve)
        • 可估算为 $AUC=\frac{1}{2}\sum_{i=1}^{m-1}(x_{i+1}-x_{i})\cdot (y_{i}+y_{i+1})$
        • AUC考虑的是样本预测的排序质量
          • 因此它与排序误差有紧密联系
        • 排序损失(loss)
          $\mathfrak{l}_{rank}=\frac{1}{m^{+}m^{-}}\sum_{x^{+}\in D^{+}}\sum_{x^{-}\in D^{-}}(\mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)<f\left(\boldsymbol{x}^{-}\right)\right)+\frac{1}{2} \mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)=f\left(\boldsymbol{x}^{-}\right)\right))$

          • 每一对正、反例:
            • 若正例的预测值<反例,则记一个”罚分”
            • 若相等,则记0.5 个”罚分”
          • $\mathfrak{l}_{rank}$ 对应的是ROC曲线之上的面积
            $AUC=1-\mathfrak{l}_{rank}$

2.3.4 代价敏感错误率与代价曲线

  • 非均等代价
    • 为权衡不同类型错误所造成的不同损失,可为错误赋予”非均等代价” (unequal cost)
    • 数学表达
      • $cost_{ij}$表示将第i类样本预测为第j类样本的代价.
        • 一般来说 $cost_{ii}=0$
        • $cost_{01}>cost_{10}$ : 将第0类判别为第1类所造成的损失更大
        • 损失程度相差越大, $cost_{01}$ 与 $cost_{10}$ 值的差别越大.
      • 代价矩阵(cost matrix)
        | 真实类别 | 预测类别 | 预测类别 |
        | ———— | ———— | ———— |
        | \ | 第0类 | 第1类 |
        | 第0类 | 0 | $cost_{01}$ |
        | 第1类 | $cost_{10}$ | 0 |
  • 总体代价
    • 在非均等代价下,希望最小化”总体代价” (total cost).
    • “代价敏感” (cost-sensitive)错误率
      令$D^{+}, D^{-}$ 代表 正例子集反例子集
      $E(f;D;cost)=\frac{1}{m}(\sum_{x_{i}\in D^{+}}\mathbb{I}(f(x_{i}\not =y_{i})\times cost_{01}+\sum_{x_{i}\in D^{-}}\mathbb{I}(f_{x_{i}\not =y_{i}})\times cost_{10})$
  • 代价曲线(cost curve)
    • 横轴:取值为[0,1]的正例概率代价
      $P(+)cost=\frac{p\times cost_{01}}{p \times cost_{01}+(1-p)\times cost_{10}}$

      • p:样例是正例的概率
    • 纵轴:取值为[0,1] 的归一化代价
      $cost_{norm}=\frac{FNR\times p \times cost_{01}+FPR\times (1-p)\times cost_{10}}{p \times cost_{01}+(1-p)\times cost_{10}}$

      • FPR 是假正例率
      • FNR = 1 – TPR 是假反例率
    • 绘制
      1. ROC曲线上每一点对应了代价平面上的一条线段
        • 设ROC曲线上点的坐标为(TPR, FPR) ,则可相应计算出FNR
      2. 然后绘制一条从(0,FPR)到(1,FNR)的线段
        图2.5 代价曲线与期望总体代价

2.4 比较检验

  • 我们希望比较的是泛化性能,然而通过实验评估方法,我们获得的是测试集上的性能,两者的对比结果可能未必相同
  • 测试集上的性能与测试集本身的选择有很大关系
  • 很多机器学习算法本身有一定的随机性
  • 统计假设检验(hypothesis test)
  • 以错误率为性能度量,用$\epsilon$ 表示.

2.4.1 假设检验

  • 设检验中的”假设”是对学习器泛化错误率分布的某种判断或猜想
    例如$\epsilon =\epsilon_{0} $.

    • 现实任务中,只能获知其测试错误率 $\hat{\epsilon}$
      • 可根据测试错误率估推出泛化错误率的分布
  • 二项检验
    • 二项(binomial)分布
      • 泛化错误率为$\epsilon$ 的学习器在一个样本上犯错的概率是$\epsilon$
      • 测试错误率$\hat{\epsilon}$ 意味着在$m$ 个测试样本中恰有$\hat{\epsilon}\times m$ 个被误分类
      • 泛化错误率为$\epsilon$ 的学习器被测得测试错误率为$\hat{\epsilon}$ 的概率:
        $P(\tilde{\epsilon};\epsilon)=\left(\begin{array}{c}m \\ \hat{\epsilon} \times m\end{array}\right) \epsilon^{\hat{\epsilon} \times m}(1-\epsilon)^{m-\hat{\epsilon} \times m}$

        • 假定测试样本是从样本总体分布中独立采样而得
          • 泛化错误率为$\epsilon$ 的学习器将其中m’个样本误分类,其余样本全部分类正确的概率是$\epsilon\^{m’}(1-\epsilon)^{m-m’}$
      • 这符合二项(binomial)分布
    • 步骤
      • 设 假设为$\epsilon \le \epsilon_{0}$
      • $1-\alpha $为置信度 confidence
      • 在$1-\alpha$ 的概率内所能观测到的最大错误率
        $\bar{\epsilon}=\max \epsilon \quad \text { s.t. } \quad \sum_{i=\epsilon_{0} \times m+1}^{m}\left(\begin{array}{c}m \\ i\end{array}\right) \epsilon^{i}(1-\epsilon)^{m-i}<\alpha$

        • 若测试错误率$\hat{\epsilon}$小于临界值$\bar{\epsilon}$
          • 在$\alpha $显著度下,不能拒绝假设
        • 否则,假设可被拒绝
  • t检验
    • 多次重复留出法或是交叉验证法等进行多次训练/测试,会得到多个测试错误率,可使用”t 检验” (t-test)
    • 令假设为$\mu=\epsilon_{0}$;显著度为$\alpha$
    • 数值
      • 平均测试错误率$\mu$
        $\mu=\frac{1}{k}\sum_{i=1}^{k}\hat{\epsilon_{i}}$
      • 方差$\sigma^{2}$
        $\sigma^{2}=\frac{1}{k-1}\sum_{i=1}^{k}(\hat{\epsilon}-\mu)^{2}$
      • 考虑到这k个测试错误率可看作泛化错误率$\epsilon_{0}$的独立采样,则变量
        $\tau_{t}=\frac{\sqrt{k}(\mu-\epsilon{0})}{\sigma}$

        • 自由度为k-1的t分布
    • 考虑双边(two-tailed)假设
      得临界值为$t_{-\alpha/2}, t_{\alpha/2}$

      • 若$|\mu-\epsilon_{0}|\in [t_{-\alpha/2}, t_{\alpha/2}]$
        则不能拒绝假设
      • 否则可拒绝假设

2.4.2 交叉验证t检验

  • 对两个学习器A和B,若我们使用k折交叉验证法得到的测试错误率分别为$\epsilon_{1}^{A}, \epsilon_{2}^{A}, \ldots, \epsilon_{k}^{A}$ 和 $\epsilon_{1}^{B}, \epsilon_{2}^{B}, \ldots, \epsilon_{k}^{B}$
    • $\epsilon_{i}^{A}$和$\epsilon_{i}^{B}$是在相同的第i折训练/测试集上得到的结果
    • 可用k折交叉验证”成对t检验” (paired t-tests)
  • 基本思想
    若两个学习器的性能相同,则它们使用相同的训练/测试集得到的测试错误率应相同
  • 步骤
    1. 对每对结果求差,$\Delta_{i}=\epsilon_{i}^{A}-\epsilon_{i}^{B}$
      • 若两性能相同,则差值均值班为零
    2. 令假设为”学习器A与B性能相同“,计算$\mu$和$\sigma^{2}$
    3. 在显著度α下,计算变量
      $\tau_{t}=\left|\frac{\sqrt{k}\mu}{\sigma}\right|$

      • 小于临界值$t_{\alpha/2,k-1}$,则假设不能被拒绝
        • $t_{\alpha/2,k-1}$ 是自由度为k-1的t分布上尾部累积分布为α/2的临界值
      • 否则,认为两学习器性能有显著差别
  • 一个重要前提是测试错误率均为泛化错误率的独立采样
  • 5 x 2 交叉验证
    • 通常情况下由于样本有限,不同轮次的训练集会有一定程度的重叠。为缓解这一问题,可采用”5 x 2 交叉验证”
    • 5×2 交叉验证是做5 次2 折交叉验证,在每次2 折交叉验证之前随机将数据打乱,使得5 次支又验证中的数据划分不重复.
    • 步骤
      1. 第i次二折交叉验证将产生2对测试错误率
      2. 分别求差
        • 第1折上差值为 $\Delta_{i}^{1}$
        • 第2折上差值为 $\Delta_{i}^{2}$
      3. 计算
        • 均值 $\mu=0.5(\Delta_{i}^{1}+\Delta_{i}^{2})$
        • 方差$\sigma_{i}^{2}=\left(\Delta_{i}^{1}-\frac{\Delta_{i}^{1}+\Delta_{i}^{2}}{2}\right)^{2}+\left(\Delta_{i}^{2}-\frac{\Delta_{i}^{1}+\Delta_{i}^{2}}{2}\right)^{2}$
      4. 得到变量
        $\tau_{t}=\frac{\mu}{\sqrt{0.2 \sum_{i=1}^{5} \sigma_{i}^{2}}}$

        • 服从自由度为5的t分布
        • 双边检验的临界值$t_{\alpha / 2,5}$

2.4.3 McNemar 检验

  • 对二分类问题, 可获得两学习器分类结果的差别
    即两者都正确都错误一个正确另一个错误的样本数

    • 列联表 (contingency table)
      | B | A | A |
      | ———— | ———— | ———— |
      | \ | 正确 | 错误 |
      | 正确 | $e_{00}$ | $e_{01}$ |
      | 错误 | $e_{10}$ | $e_{11}$ |
  • 假设是两学习器性能相同, 则 $e_{01}=e_{10}$
    • 变量$|e_{01}-e_{10}|$ 应服从正态分布
      • $mu=1$
      • $\sigma^{2}=e_{01}+e_{10}$
    • 卡方分布
      $\tau_{\chi^{2}}=\frac{\left(\left|e_{01}-e_{10}\right|-1\right)^{2}}{e_{01}+e_{10}}$

      • 服从自由度为1 的$\mathcal{X}^{2}$分布
        • 即标准正态分布变量的平方
      • 给定显著度α
        • 当以上变量恒小于临界值$\mathcal{X}^{2}$时,不能拒绝假设
        • 否则,可认为有显著差异

2.4.4 Friedman检验与Nemenyi后续检验

  • 在一组数据集上对多个算法进行比较
  • 例子
    • D1、 D2 、D3 和D4 四个数据集
    • 对算法A 、B 、C 进行比较
    1. 使用留出法或交叉验证法得到每个算法在每个数据集上的测试结果
    2. 然后,在每个数据集上根据测试性能由好到坏排序,并赋予序值1,2, …,
      • 若算法的测试性能相同,则平分序值.
        • 第二和第三名并列(2+3)/2=2.5
    3. Friedman检验来判断这些算法是否性能都相同
      • 若相同,则它们的平均序值应当相同
      • 若”所有算法的性能相同”这个假设被拒绝
        • 这时需进行后续检验(post-hoc test)来进一步区分各算法
          • 比如Nemenyi后续检验
  • 原始Friedman检验
    • N 个数据集上比较k 个算法
    • $r_{i}$ 表示第i个算法的平均序值
    • 此时$r_{i}$ 服从正态分布
      • $\mu=(k+1)/2$
      • $(k^{2}-1)/12$
    • 变量
      $\begin{aligned} \tau_{\chi^{2}} &=\frac{k-1}{k} \cdot \frac{12 N}{k^{2}-1} \sum_{i=1}^{k}\left(r_{i}-\frac{k+1}{2}\right)^{2} \\ &=\frac{12 N}{k(k+1)}\left(\sum_{i=1}^{k} r_{i}^{2}-\frac{k(k+1)^{2}}{4}\right) \end{aligned}$

      • 在k 和N 都较大时,服从自由度为k-1 的$\mathcal{X}^{2}$ 分布.
  • 现在通用的Friedman检验
    $\tau_{F}=\frac{(N-1) \tau_{\chi^{2}}}{N(k-1)-\tau_{\chi^{2}}}$

    • $\tau_{\mathcal{X}^{2}}$ 和原始一样
    • 服从自由度为k-1 和(k – l)(N – 1) 的F 分布,
  • Nemenyi检验
    • Nemenyi检验计算出平均序值差别的临界值域
      $C D=q_{\alpha} \sqrt{\frac{k(k+1)}{6 N}}$

      • 若两个算法的平均序值之差超出临界值域CD,则拒绝”两个算法性能相同”
    • 可以直观地用Friedman 检验图显示
      • 若两个算法的横线段有交叠,则说明这两个算法没有显著差别,否则即说明有显著差别
        图2.8 Friedman 检验图

2.5 偏差与方差

  • 偏差方差分解(bias-variance decomposition)是解释why学习算法泛化性能的一种重要工具
  • 对学习算法的期望泛化错误率进行拆解
    • 测试样本x
    • 令$y_{D}$ 为x在数据集中的标记, y为现实标记
    • $f(x;D)$为预测输出
  • 例子:回归任务
    • 学习算法的期望预测为
      $\bar{f}(\boldsymbol{x})=\mathbb{E}_{D}[f(\boldsymbol{x} ; D)]$
    • 使用样本数相同的不同训练集产生的方差为
      $\operatorname{var}(\boldsymbol{x})=\mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]$

      • 度量了同样大小的训练集的变动所导致的学习性能的变化
      • 即刻画了数据扰动所造成的影响
    • 噪声为
      $\varepsilon^{2}=\mathbb{E}_{D}\left[\left(y_{D}-y\right)^{2}\right]$

      • 假定噪声期望为0,即$E_{D}\left[y_{D}-y\right]=0$
      • 表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界
      • 即刻画了学习问题的难度
    • 期望输出与真实标记的差别称为偏差(bias)
      $\operatorname{bias}^{2}(\boldsymbol{x})=(\bar{f}(\boldsymbol{x})-y)^{2}$

      • 偏差度量了学习算法的期望预测与真实结果的偏离程度
      • 刻画了学习算法本身的拟合能力
  • 得到 $E(f ; D)=\operatorname{bias}^{2}(x)+\operatorname{var}(x)+\varepsilon^{2}$
    • 也就是说:
      • 泛化误差可分解为偏差、方差与噪声之和.
      • 泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的
  • 推导
    $\begin{aligned} E(f ; D)=& \mathbb{E}_{D}\left[\left(f(\boldsymbol{x} ; D)-y_{D}\right)^{2}\right] \\=& \mathbb{E}_{D}\left[\left(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x})+\bar{f}(\boldsymbol{x})-y_{D}\right)^{2}\right] \\=& \mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y_{D}\right)^{2}\right] \\ &+\mathbb{E}_{D}\left[2(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))\left(\tilde{f}(\boldsymbol{x})-y_{D}\right)\right] \\=& \mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y_{D}\right)^{2}\right] \\=& \mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y+y-y_{D}\right)^{2}\right] \\=& \mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[(\bar{f}(\boldsymbol{x})-y)^{2}\right]+\mathbb{E}_{D}\left[\left(y-y_{D}\right)^{2}\right] \\ &+2 \mathbb{E}_{D}\left[(\bar{f}(\boldsymbol{x})-y)\left(y-y_{D}\right)\right] \\=& \mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+(\bar{f}(\boldsymbol{x})-y)^{2}+\mathbb{E}_{D}\left[\left(y_{D}-y\right)^{2}\right] \end{aligned}$
  • 一般来说?偏差与方差是有冲突的,这称为偏差一方差窘境(bias-variance dilemma)
    • 在训练不足时
      • 学习器的拟合能力不够强
      • 训练数据的扰动不足以便学习器产生显著变化
      • 此时偏差主导了泛化错误率
    • 随着训练程度的加深
      • 学习器的拟合能力逐渐增强
      • 训练数据发生的扰动渐渐能被学习器学到
      • 方差逐渐主导了泛化错误率
        图2.9 泛化误差与偏差、方差的关系示意图