经验误差与过拟合

分类错误的样本数占样本总数的比例称之为错误率(error rate)。若在$m$个样本中有$a$个被错误分类的样本，则其错误率为$E=\frac{a}{m}$。相对的，$1-E$则称为精度(accuracy)。同时，我们用误差(error)这一概念来度量学习器的预测输出与样本真实输出之间的差异。在训练集上的误差被称为训练误差或经验误差(empirical error)；在新样本上的误差称为泛化误差。由于新样本的未知性，我们所应努力的方向为使学习器的经验误差达到最小。然而实际上在训练集上取得误差最小的学习器往往并不能成为我们最想要的那个。即使其分类精度达到100%，也不能表示能很好地适应新样本。

为了能让学习器在新样本上取得良好表现，我们应该从训练样本中尽可能地学习到适用于所有潜在样本的“普遍规律”，这样才能在遇到新样本时尽可能地做出正确选择。但这会出现以下两种状况：

学习器将训练集自身的一些特点当成所有样本都可能具有的一般性质来进行学习。这样会使得模型的泛化能力下降，从而引入过拟合(overfitting)的问题；
与过拟合相对的则是欠拟合(underfitting)，意思是模型并未能良好地学习到样本的一般性质。

过拟合是无法完全避免的，是机器学习的一道障碍。我们能做的只是减少其带来的风险。

评估方法

我们可以通过实验来对学习器的泛化误差进行评估。通常我们先用一个测试集来测试学习器对新样本的分类能力，然后用测试集上的测试误差来近似泛化误差。前提是测试集是通过对真实样本独立同分布采样而获得的，且其样本未在训练集中出现过。这样的训练集跟测试集可通过如下方法产生：

留出法(hold-out)

这种方法可以直接将数据集$D$划分为两个互斥的集合，其中一个作为训练集$S$，另一个作为测试集$T$。但我们需要注意，训练集跟测试集的划分应使得二者具有相同/相近的分布，从而避免因数据划分而引入额外的偏差。以二分类为例，若我们通过采样来划分数据，则通常使用分层采样(stratified sampling)这一方式。例如通过分层采样将$D$划分为含$70%$样本的训练集和含$30%$样本的测试集。若$D$有$500$个正例，$500$个负例。则训练集跟测试集中正，负例比例也应为$1:1$。

而另一个需要注意的问题就是，划分的方式并不唯一。即使给定比例，训练集与测试集的划分结果也不唯一。这将导致训练出来的模型的评估结果存在相应的差别。因此仅单次使用留出法所得到的模型评估结果往往不具有可靠性。使用留出法时，一般采用多次随机划分，重复实验评估后取平均值作为留出法的评估结果。

k折交叉验证

此方法思想为：先将数据集$D$划分为$k$个大小相似且互斥的子集，其中每个子集应尽可能地保持同分布。可以通过分层抽样得到。之后的每次训练使用其中的$k-1$个子集，剩余的$1$个子集用来测试。这样我们能获得$k$组$训练-测试$集，从而进行$k$次训练和测试。最终采用$k$次测试结果的均值作为整体测试结果。由此可见，$k$折交叉验证结果的稳定性和真实性很大一部分取决于$k$的大小。通常$k$的取值范围为$5-20$。整个过程如图：

当$k$取$m$时，该方法称为“留一法”。因为与数据集$D$相比，每次用于训练的样本数量只减少了$1$。因此用留一法训练评估的模型与用$D$训练得到的模型很相似。故其评估结果往往更为准确。但这种方法的局限性在于耗时长——若数据集包含1e6个样本，则我们需要训练1e6个模型。不管是时间方面还是内存方面开销都是难以忍受的。而且某些时候这种评估方法未必比其他更准确。

以上两种方法存在同一种缺陷：由于其均保留了一部分样本作为测试，在实际所评估的模型中所使用的训练集的规模总会小于数据集$D$。这样势必会导致因训练集规模不同而产生估计误差。

自助法（bootstrapping）

对于减少因训练集规模不同所产生的影响并高效地估计模型方面，自助法是一个比较好的解决方案。它以自助采样（bootstrap sampling）为基础。给定包含$m$个样本的数据集$D$，我们首先对其采样，得到$D’$。具体采样的过程为：每次有放回地从$D$中随机选择一个样本，将其复制到$D’$。这使得该样本能自始至终地保持同样的概率被选择。这样的过程持续$m$次即得到包含$m$个样本的$D’$。显然，这样有放回的抽取将使得一部分样本不止一次地被抽到，而一部分样本总不会被抽到。这样始终不被抽取的概率为$(1-\frac{1}{m})^m$。由于：
$$
\lim_{m->∞}(1-\frac{1}{m})^m→\frac{1}{e}\approx0.368
$$
即原始数据集$D$中将有$36.8%$的概率不出现于$D’$中。于是我们可以将$D’$作为训练集，$D\text{\}D’$作为测试集。这样，实际评估的模型与期望的模型所使用的训练样本的规模一致，且我们仍然有数据总量$1/3$规模的未在训练集中出现的样本用于测试。这种方法也称“包外估计（out-of-bag estimate）”。

当数据集规模较小且难以划分训练集/测试集时，自助法效果往往较好。而且自助法能从$D$中产生多个不同的训练集，这对集成学习等方法来说能带来较高的收益。这种方法的不足之处在于抽样将改变数据集的分布，会引入估计误差。因此当数据集规模较大时，往往采用留出法或交叉验证法。

调参与最终模型

调参

绝大多数的学习算法都有一些参数（parameter）需要提前设定。参数配置不同，学习得到的模型往往存在着显著的差别。因此，在模型评估与选择时，除了选择合适的算法之外，还应该进行所谓的“调参”。这时应该注意一点：学习算法的很多参数虽然在实数范围内取值，但我们不可能把所有参数都拿来学习一遍。通常我们采用的方法是为每个参数设置一个合理的范围和步长。在这里面我们选取一个“最优”参数（局部而非全局）。

确定最终模型

理想情况下，模型评估应该在未用于模型构建或微调的样本上进行，这样才能对模型效率进行无偏评估。因此如果我们有大量数据可用，则可以留出一部分样本集用于最终模型的评估。训练数据集指构建模型时使用的样本集，而测试数据集或验证数据集用于评估模型性能。以任何形式使用测试集中的信息都是一种“窥探”（peeking），因此应封存测试集，直到模型调整全部完成再作为最后的评估。当所有选择完成后（算法选择及参数调优），我们应该用所有的数据来重新训练模型，并将此得到的模型作为最终模型来提交。

性能度量

当我们对学习器进行评估时，除了要有科学可行的评估方法，还应该有能够衡量模型泛化能力的评价标准。即性能度量。

性能度量能够反应任务的需求。在衡量不同模型的好坏时，使用不同的性能度量指标往往会产生不同的评价。这说明模型的好坏往往也取决于任务需求。

假设给定数据集$D={(\textit{x}_1,y_1),(\textit{x}_2,y_2),\cdots,(\textit{x}_m,y_m)}$，其中$y_m$表示样本示例$\textit{x}_m$的真实label。要度量学习器的性能，就应该将学习器预测输出$f(\textit{x})$与样本真实label进行比较。基于不同的比较方法，我们能得到不同的性能度量指标。

均方误差（MSE）

回归任务中，最常用的性能度量指标就是“均方误差”（mean squared error）：

$$ MSE(f;D)=\frac{1}{m}\sum^m_{i=1}(f(\mathcal{x}_{i})-y_{i})^2 $$

一般而言，对于分布$\mathcal{D}$，概率密度函数$p(\cdot)$，MSE可按如下定义：

$$ MSE(f;\mathcal{D})=\int_{x\sim\mathcal{D}}(f(\mathcal{x})-y)^2p(\mathcal{x})\text{d}\mathcal(x) $$

分类任务中常用的性能度量指标：

错误率与精度

错误率即分类错误的样本数占样本总数的比例：
$$
E(f;D)=\frac{a}{m}
$$
其中$a$表示分类错误的样本数，$m$表示样本总数。

精度即分类正确的样本数占样本总数的比例：
$$
E(f;D)=\frac{m-a}{m}=1-E(f;D)
$$

查准率（precision）与查全率（recall）

错误率与精度虽然很常用，但是并不能满足所有任务需求。比如如果我们关心的是被预测为正样本中有多少比例是真的正样本，或者所有的正样本中有多少比例被预测为正样本，这个时候错误率就不够用了，还需要使用其他的性能度量。

对于二分类问题，我们可以将学习器产生的样例根据其真实类别与学习器所预测的类别组合划分为真阳（$TP$），假阳（$FP$），真阴（$TN$），假阴（$FN$）四种情形。则$TP+FP+TN+FN=1$。由此组合成的矩阵称为“混淆矩阵（confusion matrix）”：

其中查准率和查全率分别定义为：
$$
P=\frac{T P}{T P+F P}\
R=\frac{T P}{T P+F N}
$$
以信息检索为例，逐条向用户反馈其可能感兴趣的信息，即可计算对应的查准率和查全率。

我们可以根据学习器的预测结果对样例进行排序，排在前面的样例即为学习器“最可能”认为其是正例的样本，反之则为“最不可能”的样本。按照该顺序逐个将样本作为正例预测，则可计算出当前的查全率和查准率。以查准率为纵轴，查全率为横轴作图，可以得到$查准率-查全率$曲线图，即“$\text{P-R}$”图：

查全率

此图能直观地反映出学习器在样本总体上的查准率和查全率。在比较多个学习器时，将其$\text{P-R}$图放一起，若其中一个学习器能将另一个学习器完全包住，则可说明前者性能优于后者。

如图，横轴与纵轴指标相等时的点称为“平衡点”（Break-Event Point）。当曲线有交点时，可以通过比较平衡点的取值来评价模型好坏。

由于只根据平衡点来评估模型显得有点过于随意，我们通常使用$F1\text{ score}$：
$$
F 1=\frac{2 \times P \times R}{P+R}=\frac{2 \times T P}{\text { 样例总数 }+T P-T N}
$$
$F1\text{ score}$实际上是基于查准率和查全率的调和平均值定义的：
$$
\frac{1}{F 1}=\frac{1}{2} \cdot\left(\frac{1}{P}+\frac{1}{R}\right)
$$
用途更为广泛的是$F_{\beta}$，其定义为查准率和查全率的加权平均值的倒数：
$$
\frac{1}{F_{\beta}}=\frac{1}{1+\beta^{2}} \cdot\left(\frac{1}{P}+\frac{\beta^{2}}{R}\right),(\beta>0)\
F_{\beta}=\frac{\left(1+\beta^{2}\right) \times P \times R}{\left(\beta^{2} \times P\right)+R}
$$
我们可以通过控制$\beta$的取值来表达对查全率和查准率的不同偏好：

$\beta=1$时$F_\beta$退化为$F_1$值；
$\beta>1$时查全率占主导地位；
$\beta<1$时查准率占主导地位。

ROC与AUC

实际上我们的学习算法往往会根据输入样本产生一个对应的概率或实值，然后根据分类阈值来将其划分至对应的类别中，神经网络就是很好的例子。那么针对这种算法，我们可以根据其输出的实值或概率进行排序。对于二分类问题来说就会有“最正类”的样本排在最前，而“最负类”的样本排在最后。这样，我们可以从序列中找到一个点（$cut\ point$）将全体样本（测试）一分为二，其中一部分样本为“正例”，另一部分样本为“负例”，或针对多分类问题找到多个点。

当然这个划分标准是人为规定的，意思就是针对不同的问题，我们往往可以选择不同的$cut\ point$。如同上文提到的“查准率”和“查全率”。若我们重视前者，则可以将$cut\ point$设置的更靠前，反之亦然。因此排序的好坏可以在一定程度上体现学习算法针对不同问题的“泛化误差”的优劣。介于此，$ROC$曲线可以用来研究学习算法的“泛化”能力的好坏。

与$P-R$曲线类似，绘制$ROC$曲线需要我们先将样本按输出值排序，然后以该顺序逐个将样本判定为“正例”用于预测。在每次预测的时候计算出“假正例率”和“真正例率”并分别作为横、纵坐标。以此得到的曲线即为“$ROC$曲线”。其定义为：

$$
\text{TPR} = \frac{TP}{TP+FN}\
\text{FPR} = \frac{FP}{TN+FP}
$$

左边的图是理想情况，毕竟样本有限。而我们往往画出的曲线为右图所示，上文的$P-R$曲线也是如此（非光滑）。具体绘制的步骤是：

排序：设有$m+$个正例和$m-$个负例，根据学习算法的预测结果对样本排序；
设置初始点：将分类阈值设为最大。此时所有的样本均判为“负”。由此可计算出$TPR=0,FPR=0$，对应图中的原点；
调整阈值：将分类阈值依次设定为每个样本的预测值（即依次将每个样本判为“正”）。设前一坐标为$(x_{0},y_{0})$，若当前为“正”的样本则对应的坐标为$(x_0,y_0+\frac{1}{m+})$，反之则为$(x_0+\frac{1}{m+},y_0)$；
绘制图像：将所有坐标用线段相连即得$ROC$曲线。

当我们利用$ROC$曲线进行学习器的比较时，与$P-R$曲线类似，当一个学习器的曲线完全包裹另一个学习器时。可以判定前者优于后者。若有交叉，我们可以通过$AUC$来比较。所谓$AUC$实际上就是曲线对于横坐标的面积：

$$
\text{AUC} = \frac{1}{2}\sum^{m-1}_{i=1}(x_{i+1}-x_i)\cdot(y_i+y_{i+1})
$$

从定义上来看我们可以发现$AUC$衡量的是排序的好坏。因此我们可以将其与排序误差$loss_{rank}$联系到一起。给定$m+$和$m-$个正例和负例。设$D+$和$D-$分别表示正、负例集合。则排序误差可定义为：

$$
l_{rank} = \frac{1}{m+\cdot{m-}}\sum_{\mathcal{x+}\in D+}\sum_{x-\in D-}\large{(}\mathbb{I}(f(x+)<f(x-))+\frac{1}{2}\mathbb{I}(f(x+)=f(x-))\large{)}
$$

$l_{rank}$可以通俗理解为当正例预测值小于负例时记$1$分，相等记$0.5$分。在图像中我们也可以看出$l_{rank}$代表的是$AUC$之外的面积。

偏差与方差

评价学习器优劣既可以通过实验来进行，也可以通过“偏差-方差分解”来解释它为什么具有如此性能。该方法致力于对学习算法期望泛化的错误率进行拆解。学习算法往往在不同的训练集上有着不同的学习模型。就算这些数据集同分布结果也不尽相同。设测试样本为$\mathbf{x}$，令$y_{D}$为$\bf{x}$在数据集中的$label$，$y$为真实$label$，$f(\mathbf{x};D)$为在$D$上学得的模型在$\bf{x}$上的预测结果。在回归任务中，学习算法的期望预测为：

$$
\overline{f}(\mathbf{x}) = \mathbb{E}_{D}[f(\mathbf{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]
$$

而期望输出与真实标记的差别称为偏差（$bias$）：

$$
\operatorname{bias}^{2}(\boldsymbol{x})=(\bar{f}(\boldsymbol{x})-y)^{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(\bar{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}[2(f(x ; D)-\bar{f}(x)) \cdot \bar{f}(x)]-\mathbb{E}_{D}\left[2(f(x ; D)-\bar{f}(x)) \cdot y_{D}\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]\\
&+\bigg{(}2\bar{f}(\boldsymbol{x}) \cdot \mathbb{E}_{D}[f(\boldsymbol{x} ; D)]-2 \bar{f}(\boldsymbol{x}) \cdot \bar{f}(\boldsymbol{x})\bigg{)}\\
&+\bigg{(}2 \mathbb{E}_{D}[f(x ; D)] \cdot \mathbb{E}_{D}\left[y_{D}\right]-2 \bar{f}(x) \cdot \mathbb{E}_{D}\left[y_{D}\right]\bigg{)}\\
=& \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}$$