第二章 模型评估与选择
第二章 模型评估与选择
  2.1 经验误差与过拟合
    基本概念
      “误差”均指误差期望
      机器学习的关键障碍，无法彻底避免，只能“缓解”
      P = NP 问题：P就是能在多项式时间内解决的问题，NP就是能在多项式时间验证答案正确与否的问题
      错误率（error rate）
        把分类错误的样本数占样本总数的比例
      精度（accuracy）
        精度 = 1 - 错误率
      误差（error）
        目标：得到泛化误差小的学习器
        把学习器的实际预测输出与样本的真实输出之间的差异称为误差
        学习器在训练集上的误差称为 “训练误差”（training error）或 “经验误差”（empirical error）
        在新样本上的误差称为 “泛化误差”（generalization error）
      过拟合（overfitting）
        把训练样本自身的一些特点当作了潜在样本都会有的一般性质
        又称 “过配”
      欠拟合（underfitting）
        指对训练样本的一般性质尚未学好
        又称 “欠配”
      学习能力是否 “强大”
        共同作用
        学习算法
        数据内涵
    模型选择（model selection）问题
  2.2 评估方法
    实验测试
      测试集（testing set）
        从样本真实分布中独立同分布采样的
        测试机与训练集尽可能互斥
      分层采样（stratified sampling）
      自助采样（bootstrap sampling）
      留出法（hold-out）
        直接将数据集划分为两个互斥的集合
        测试集较小时，评估结果的方差较大；训练集小时，评估结果的偏差较大
        常见做法 2/3 ~ 4/5 的样本作为训练集，剩余样本用于测试
      交叉验证法（cross validation）
        每个子集都应该尽可能保持数据分布的一致性，即从D中分层采样得到
        与留出法相似，每次划分会影响结果，因此需要使用不同的划分重复 p 次，即 p 次 k 折交叉验证 == p * k 次留出法
        将数据集划分为k个大小相似的互斥子集
        每次用k-1个子集的并集作为训练集，余下的那个子集作为测试集
          拥有k组的训练和测试集
          可进行k次训练和测试
          最终结果为k次结果取均值
          当k和数据集数量一致时，称之为留一法（Leave One Out）简称：LOO
            相当准确，不受划分影响
            模型计算开销大
      自助法（bootstrapping）
        自助采样过程
          D' 中会有一部分重复样本
        通过自助采样，初始数据集中约有36.8%的样本未出现在采样数据集中
          测试结果，称为 “包外估计” （out of bag estimate）
          实际评估的模型和期望评估的模型都有使用m个训练样本
          越有 1/3 的数据没有出现在训练集中，用于测试
      特点
        保留类别比例的采样方式
        因为每次划分都会对应一个结果，所以需要取平均值作为留出法的评估结果
          随机划分
          重复试验
      特点
        改变了初始数据集的分布
        数据集较小、难以有效划分训练/测试集时很有用
    调参与最终模型
      调参（parameter tuning）
        实际上是不可能的
        参数类型
          超参数
            算法本身的参数
            数目常在10个以内
            人工设定多个参数候选值后产生模型
          参数
            模型的参数
            数目可能很多
            通过学习来产生多个候选模型
        理想状态是对每种取值都做模型训练
        对每一个参数选定一个选参范围和变化步长
      最终模型
  2.3 性能度量
    定义
    回归任务最常用
    分类任务最常用
    对学习器的泛化性能进行评估，不仅需要有效可行的实验估计方法，还需要有衡量模型泛化能力的评价标准，这就是性能度量（performance measure）
    均方误差（mean squared error）
      评估学习器的性能，就是比较学习器预测结果f(x)和真实标记y
      条件
      标准型
      一般型
    错误率和精度
      错误率（error rate）
        定义
        标准型
        一般型
        分类错误的样本数占样本总数的比例
      精度（accuracy）
        定义
        标准型
        一般型
        分类正确的样本数占样本总数的比例
    查全率 & 查准率 & F1
      分类混淆矩阵
          纵向是预测，横向是真实
          纵向排在真实后
        四种情况
          真正例（true positive）TP
          假正例（false positive）FP
          真反例（true negative）TN
          假反例（false negative）FN
          TP+FP+TN+FN=样例总数
      查准率 P（precision）& 准确率
        “挑出的西瓜中有多少是好瓜”
      查全率 R（recall）& 召回率
        “所有好瓜中有多少的比例被挑了出来”
      P-R 曲线
        以查准率为纵轴，查全率为横轴作图
          利用P-R曲线判定两个学习器的性能
            最准确
            标准型
            一般型
            比较曲线下的面积的大小
            “平衡点”（Break-Even Point）BEP
              “查准率=查全率”时的取值
              源于查准率与查全率的调和平均（harmonic mean）
              源于查准率与查全率的加权调和平均
        n次二分类实现的多分类问题
          先分别计算，再求平均值
            宏查准率 macro-P
            宏查全率 macro-R
            宏F1 macro-F1
          先求平均值，再分别计算
            微查准率 micro-P
            微查全率 micro-R
            微F1 micro-F1
      查准率越高的时候查全率越低
    ROC与AUC
      变更阈值（threshold）之后依据正反例变化的比率来绘制的图像
      “受试者工作特征”曲线（Receiver Operating Characteristic）
      纵轴是“真正例率”（True Positive Rate，简称TPR），横轴是“假正例率”（False Positive Rate，简称FPR）
        判断两个学习器孰优孰劣
        AUC（Area Under ROC Curve）
          ROC曲线与X轴围成的面积
          ROC曲线下的面积
          AUC是考虑样本预测的排序质量，因此它与排序误差有紧密联系
            排序导致的损失公式
              ROC曲线与Y轴围城的面积
              考虑每一个正反例，如果预测值小于反例，记1，若相等，记0.5
    代价敏感错误率与代价曲线
      核心理念
      非均等代价（unequal cost）
        为权衡不同类型错误所造成的不同损失
      二分类任务
        代价矩阵（cost matrix）
          在非均等代价下，我们所希望的不再是简单地最小化错误次数，而是希望最小化“总体代价”（total cost）
          代价敏感（cost-sensitive）错误率公式
      代价曲线（cost curve）
        代价曲线的由来
        在非均等代价下，ROC曲线不能直接反映出学习器的期望总体代价
          形式是直线定义的表达是，目的是归一化，作用是将值域映射到相同的范围
          横轴
            取值为 [0, 1] 的正例概率代价
          纵轴
            取值为 [0, 1] 的归一化代价
          当判断阈值threshold一定时，就确定了一组相应的混淆矩阵，而根据样例中的正样例数量的比率的不同，产生了不同的代价期望
        目的：根据正例在样本中的比值的不同，找到使得代价总期望最小的模型的阈值
  2.4 比较检验
    核心思想：根据测试错误率可估测推出泛化错误率的分布
    问题
      1、测试集上的性能与真实的泛化性能未必相同
      2、测试集的不同反映出来的性能不同
      3、机器学习算法本身有一定的随机性，同一测试集上的性能也不同
    测试错误率与泛化错误率未必相同，但二者理论上相近
      真实情况下
      统计情况下
    统计假设检验（hypothesis test）
      核心问题
      若在测试集上观察到学习器A比学习器B好，则A的泛化性能是否在统计意义上优于B，以及这个结论的把握有多大
      参见知乎答案
      符号
        真实值
        假设值
        计算值
        观测值
        泛化错误率
          是学习器的内在属性，是客观存在的值，但是无法观测
        泛化错误率
          是人为设定的一个值，用于推测真实的泛化错误率
            通常默认都会选择闭区间
        测试错误率
          是经过实验观测到的测试错误率，跟泛化错误率存在某种关系
        检验临界值
          是测试错误率的上限，为了使得假设条件得到满足的最大测试错误率的值
      理念
        求偏导
          符合二项（binomial）分布
            误分类样本数量的概率分布图
            阴影部分的面积代表
            每个柱子的代表实验中出现误分类样本数目的概率
          二项检验（binomial test）
            一个测试集一个算法
            假设抛一枚质量均匀的硬币1000次，求其正面出现的概率
                真实的泛化错误率
                人为设定的泛化错误率
              假设
            进行实验统计正面出现的次数
              可以得到正面出现的次数落在[0, 1000]的区间中
              假设某次的实验得到的正面出现的次数是 600 次
                  实验得到的测试错误率
                但无法下结论说明初始设定的泛化错误率是错的
            什么情况下我们才能接受实验得到的测试错误率可以推断出人为设定的泛化错误率是对的或者是错的？
              引入新的参数
                显著度
                置信度
      常用方法
        多个测试集一种算法
        多个测试集两种算法
        一个测试集两种算法
        多个测试集多种方法
        t 检验（t-test)
            平均测试错误率
            方差
                用于根据小样本来估计呈正态分布且方差未知的总体的均值
                自由度越小，曲线越平坦，自由度越大，越接近标准正态分布
                其本质是一族曲线，每一个自由度的值都可以确定其中唯一一条曲线
                双边检验的临界值
                结论
                  则假设不能被拒绝，即认为两个学习器的性能没有显著差别
                  则假设被拒绝，且平均错误率较小的那个学习器性能更优
        交叉验证 t 检验
          基本思想
          重要前提：测试错误率均为泛化错误率的独立采样（实际情况：不同轮次的训练集会有一定程度上的重叠）
          若两个学习期的性能相同，则它们使用相同的训练集和测试机得到的测试错误率应相同
          k折交叉验证法
            步骤
              自由度为k-1的t分布
          5x2交叉验证法
            5次2折交叉验证
            为了缓解k折交叉验证法过高估计假设成立提出的解决方案
            步骤
              自由度为5的t分布
        McNemar 检验
          二分类问题
          列联表（contingency table）
            服从自由度为1的卡方分布，即标准正态分布变量的平方
            如果通过卡方分布进行评估，则通过将上表的e01与e10两个频率中较小的一个加上0.5、较大的一个减去0.5来进行连续性校正。这种纠正在统一降低差异的绝对值e01-e10中具有明显的效果。提出后为式子 -1
            最终结论看平均错误率较小的学习器性能更优
        Friedman 检验 与 Nemenyi 后续检验
          只能确认算法之间是否存在显著性性能不同
          Friedman 检验
            在不考虑平分序值的情况下
            步骤
                均值
                方差
            原始Friedman检验
              过于保守
              引发变形
          Nemenyi 后续检验（Nemenyi post-hoc test）
            计算平均序值差别的临界值域
              若两个算分的平均序值之差超过了临界值域，则以相应的置信度拒绝“两个算法性能相同”这一假设
          Friedman 检验图
              纵轴是各个算法，横轴是平均序值
              每个算法以原点显示其平均序值，然后线段的长度描述临界值域的大小
              若线段重叠，则说明算法之间没有显著性能差别，否则即说有显著性能差别
  2.5 偏差与方差
    核心公式：泛化误差期望=偏差+方差+噪声
    "偏差-方差分解"（bias-variance decomposition）用来解释其学习器为什么具备这样的性能
      噪声会导致数据集中的标记不一定正确
      学习算法的期望预测
      使用样本数相同的不同训练集产生的方差
      噪声
      偏差
    结论
      偏差：度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力
      方差：度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响
      噪声：表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度
      泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的
        使得偏差较小，即能充分拟合数据
        使得方差较小，即使得数据扰动产生的影响小
    推导过程
      两处省略：第一次省略是因为噪声不依赖于学习器，第二次是因为噪声期望为0
s.t. 是 “subject to” 的简写，使左边式子在右边条件满足时成立