周志华《机器学习》笔记

经验误差和过拟合

• $\textbf{错误率}=\frac{分类错误的样本数}{总样本数}$
• $\textbf{精度}=\frac{分类正确的样本数}{总样本数}=1-错误率$
• $\textbf{误差}=实际预测输出-样本的真实输出$
  训练误差（经验误差）：学习器在训练集上的误差
  泛化误差：在新样本上的误差
• 过拟合：学习器把训练样本自身的一些特点当做所有潜在样本都会具有的一般性质而导致泛化性能下降
  欠拟合：对训练样本的一般性质没学好
• 过拟合是及其学习面临的关键障碍
  欠拟合通常是学习能力低下，往往在决策树学习中扩展分支、在神经网络学习中增加训练轮数即可克服；
  过拟合很麻烦，无法彻底避免，只能“缓解”或减小风险

评估方法

通常需要对模型的泛化误差进行评估，来减小过拟合的风险
一般会将已有的数据集划分为“训练集”和“测试集”两个独立的部分
训练集用于学习器的训练，测试集用来测试训练模型，并用测试集的测试误差来近似估计泛化误差

留出法

从数据集中划分一定比例的数据构成测试集

• 训练/测试集划分时要尽可能确保数据分布一致（如样本的标签分类的比例一致）
• 一般进行若干次的随机划分、重复实验评估后取测试误差的平均值作为泛化误差的评估
• 训练集越大，评估结果可能越不稳定不准确
  测试集越大，则数据集与训练集的差异越大，评估结果可能越不具真实性
  通常取2/3~4/5的数据作为训练集

交叉验证法

将数据划分为k个子集（分布一致），将其中1个子集作为测试集，其余子集的并集作为训练集
逐个子集作为测试集，共测试k组数据，最后取平均值，称“k折交叉验证法”

• 如果进行n次重复实验，最后取平均值，则称“n次k折交叉验证法”
• 特例：留一法
  每个子集只有一个样本
  优点：评估结果与实际泛化误差非常接近，往往被认为是比较准确的
  缺点：当数据集比较大时，开销会变得非常大
  当然，“没有免费的午餐”，其评估结果未必永远比其他方法都准确

自助法

每次从数据集D取出一个数据拷贝到D’，重复拷贝m个样本到D’中（允许样本重复）
某样本始终不被采集到的概率为 $(1-\frac{1}{m})^m$
则D中不被采集的样本比例为 $\lim_{m \rightarrow \infty}{(1-\frac{1}{m})^m} \rightarrow \frac{1}{e} \approx 0.368$
即D’包含D中63.2%的样本，取D’作为训练集，D-D’为测试集进行评估
适合：数据集比较小、难以有效划分训练/测试集的情形
缺点：改变了初始数据集的分布，引入估计偏差

调参与最终模型

• 算法参数（超参数）：数目通常在10以内，通常由人工设定
  模型参数：数目庞大，由机器通过学习来设定
• 设定算法参数时，通常选定一个范围和变化步长来获取一系列的候选值
  依次通过学习算法构造模型并进行评估，从而寻找最佳的参数组合

性能度量

错误率与精度

错误率：$E(f;D)=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I} (f(x_i) \neq y_i)$

精度：$acc(f;D)=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I} (f(x_i)=y_i)=1-E(f;D)$

其中，$\mathbb{I}(\cdot)$为指示函数，当$\cdot$为真时，其值为1，否则为0

查准率、查全率、F1

【准确性、完备性的度量与权衡】
查准率（准确率）：$P = \frac{预测为A且预测正确的样本数}{预测为A的总样本数}$
查全率（召回率）：$R = \frac{预测为A且预测正确的样本数}{实际为A的总样本数}$

• 通常，查准率和查全率相互矛盾
  查准率越高，查全率越低；反之亦然
• 查准率-查全率曲线（P-R曲线）
  根据学习器的预测结果对样例进行排序
  依次将前1个、前2个、前3个……样例作为正例，得到一组查准率/查全率，进而绘制成曲线
  
  • 如果一个学习算法的P-R曲线被另一个算法的P-R曲线完全包围（更加外凸）则可以断言后者性能优于前者
  • 简单的性能度量：平衡点（Break-Even Point, BEP）
    BEP即查准率=查全率时的取值，BEP越高则认为该算法性能更好
  • 更常用的性能度量：F1度量
    基于调和平均：$\frac{1}{F} = \frac{1}{2} \cdot (\frac{1}{P} + \frac{1}{R})$
    $F1 = \frac{2 \times P \times R}{P + R} = \frac{2 \times TP}{样例总数 + TP -TN}$
    其中，TP为真正例的样本数，TN为真反例的样本数（类似的，FP、FN是假正例、假反例的样本数）
    正/反指的是预测结果，真/假指的是预测是否正确
  • 带权重的性能度量：$\mathbf{F_\beta 度量}$
    基于加权调和平均数：$\frac{1}{F_\beta} = \frac{1}{1 + \beta ^ 2} \cdot (\frac{1}{P} + \frac{\beta ^ 2}{R})$
    $F_\beta = \frac{(1 + \beta ^ 2) \times P \times R}{(\beta ^ 2 \times P) + R}$
    其中$\beta > 0$，是查全率R相对查准率P的权重比（当$\beta = 1$时，退化为F1）
  • 二分类混淆矩阵的度量
    有时候估计多分类算法性能时，会将各分类两两组合得到二分类混淆矩阵，进而综合考察他的P/R
    此时有两种度量方式——
    1. 宏F1
       分别计算P和Q，最后取平均值
       $macro-P = \frac{1}{n} \sum_{i=1}^{n} P_i$
       $macro-R = \frac{1}{n} \sum_{i=1}^{n} R_i$
       $macro-F1 = \frac{2 \times macro-P \times macro-R}{macro-P + macro-R}$
    2. 微F1
       分别计算$\overline{TP}$、$\overline{TN}$、$\overline{FP}$、$\overline{FN}$，再代入F1公式
       $micro-P = \frac{\overline{TP}}{\overline{TP} + \overline{FP}}$
       $micro-R = \frac{\overline{TP}}{\overline{TP} + \overline{FN}}$
       $micro-F1 = \frac{2 \times micro-P \times micro-R}{micro-P + micro-R}$

ROC、AUC

【预测值质量的度量】
真正例率：即分类正确时正例的比例，$TPR = \frac{TP}{TP + FN}$
假正例率：即分类错误时正例的比例，$FPR = \frac{FP}{TN + FP}$
受试者工作特征（Receiver Operating Characteristic，ROC）
类似P-R曲线的绘制，先根据预测值（预测概率）将预测结果排序，
依次将前1个、前2个、前3个……样例作为正例，得到一组TPR/FNR，进而绘制成ROC曲线（TPR为纵，FNR为横）

• 对角线TPR=FNR对应“随机猜测”的模型
• 如果一个学习算法的P-R曲线被另一个算法的P-R曲线完全包围（更加外凸）则可以断言后者性能优于前者
  否则，通常比较两个算法的ROC曲线下的面积即AUC（Area Under ROC Curve），面积越大性能越优
• AUC考虑的是样本预测的排序质量，与排序误差有紧密联系
  通常为测试结果进行计分——
  考虑每对实际的正、反例，
  若正例预测值较小（即对这一组预测结果而言，预测出现错误），则计1分；
  若预测值相等，则计0.5分；
  累计得分后最后计算平均值，得到排序的“损失”
  也即$\ell_{rank} = \frac{1}{m^+ \cdot m^-} \sum_{x^+ \in D^+} \sum_{x^- \in D^-} \left( \mathbb{I} \left( f(x^+) < f(x^-) \right) + \frac{1}{2} \mathbb{I} \left( f(x^+) = f(x^-) \right) \right)$
  其中，$m^+$、$m^-$分别是实际中正例、反例的样本数，$D^+$、$D^-$分别是实际中正例、反例的集合
  并且可以推导得出：$\mathbf{ AUC = 1 - \ell_{rank} }$

代价敏感错误率、代价曲线

【非均等代价下的性能度量】
考虑分类错误的代价不均等的情况
假设假正例、假反例的代价分别为$cost_{FN}$、$cost_{FP}$
则总体代价为$E(f;D;cost) = \frac{1}{m} \left( \sum_{x_i \in D^+} \mathbb{I}( f(x_i) \neq y_i ) \times cost_{FN} + \sum_{x_i \in D^-} \mathbb{I}( f(x_i) \neq y_i ) \times cost_{FP} \right)$
由此可以绘制代价曲线（即图中的红色曲线）——

• 横轴是正例概率代价：即分类出错中，预测为正例的加权比例
  $$P(+)cost = \frac{p \times cost_{FN}}{p \times cost_{FN} + (1 - p) \times cost_{FP}}$$
  其中p为样例实际为正例的概率
• 纵轴是归一化代价
  $$cost_{norm} = \frac{FNR \times p \times cost_{FN} + FPR \times (1 - p) \times cost_{FP}}{p \times cost_{FN} + (1 - p) \times cost_{FP}}$$
• ROC曲线上的一点(FPR, TPR)是代价曲线上的一条直线（过(0, FPR)和(1, FNR)）
• 期望总体代价：即ROC曲线上所有点映射过来的所有直线的线下面积的公共部分的面积（即图中阴影部分面积）
  其包围曲线（不含横轴）即为代价曲线

比较检验

评估度量的值与测试集的选择、学习算法的随机性有关，往往不能直接比较，而是采用统计假设检验的方法来进行比较
这里以错误率$\epsilon$为性能度量

• 假设检验
  T检验，检验小样本得出的假设的显著程度，要求样本来自正态分布总体且为随机样本
  参考：T检验的步骤
• 交叉验证t检验：交叉验证 + T检验
  分别对两学习器做k折交叉验证，得到两组测试错误率，计算每一折的测试错误率之差
  假设“两学习器性能相同”，用T检验判断假设在某一显著度下是否能够拒绝
  如果能够拒绝假设，则两学习器性能显著不同，平均测试错误率较低的学习器性能更优
  • 但假设检验的前提是测试错误率应为泛化错误率的独立采样，显然这里不同折次的采样有重叠，从而过高估计假设成立的概率
    为了缓解这个问题，可以采用“5次2折交叉验证”
  • 每次交叉验证都随机打乱数据
    为了进一步缓解非独立性
    通常以第一次2折的平均值为总的估计均值，以五次2折的方差均值作为总的估计方差
• McNemar检验：留出法 + 卡方检验
  用留出法得到两学习器的差别（都正确、都错误、A正确B错误、A错误B正确）
  假设“两学习器性能相同”，利用A正确B错误、A错误B正确的样本数进行卡方检验
• Friedman检验 与 Nemenyi后续检验：留出法或交叉验证法 + F检验
  多个学习器参与比较时，可以两两进行比较检验，也可以直接采用下述F检验、N后续检验——
  用多个数据集测试算法，并且对于每个数据集对几个学习器的测试结果进行排序，最后取得每个学习器的平均序值
  假设“学习器性能相同”，利用平均序值进行卡方检验
  若能够拒绝假设，则用Nemenyi后续检验进一步区分每两个算法

偏差与方差

如果希望了解学习器“为什么”具有这样的性能，可以采用“偏差-方差分解”
即将学习器的期望泛化误差进行展开、分解——
$$
\begin{equation}
\begin{aligned}
E(f;D) &= bias^2(x) + var(x) + \epsilon^2 \\
&= \mathbb{E}_D( (f(x;D) - \overline{f}(x))^2 ) + (\overline{f}(x))^2 + \mathbb{E}_D((y_D - y)^2)
\end{aligned}
\end{equation}
$$

• $bias^2(x)$为偏差，度量了期望预测与真实结果的偏离程度，刻画了算法的拟合能力
• $var(x)$为方差，度量了同样大小的训练集的变动引起的算法性能变化程度，刻画了数据扰动对算法造成的影响
• $\epsilon^2$为噪声，度量的当前任务下任何学习算法所能达到的期望泛化误差的最小值，刻画了学习任务本身的难度

偏差-方差窘境：
假设能够控制算法的训练程度（如决策树层数、神经网络轮数、集成学习方法的基学习器数）

• 训练不足时，学习器拟合能力不佳，偏差主导了泛化错误率；
• 训练程度加深，学习器拟合能力加强，方差主导了泛化错误率；
• 训练程度太强，学习器拟合能力过强，发生过拟合