Model Selection and Evaluation

topic
4.5k 词 
    <p>前面两篇分别写了机器学习的简介和一些必备的基础知识，这一篇打算写下模型评估和选择。</p>

我们把学习器实际预测输出和样本真实输出之间的差异称为误差。学习器在训练集上的误差称为经验误差；在新样本上的误差称为泛化误差。显然，我们希望得到泛化误差小的学习器。然而，在现实中，我们并不知道新的样本什么样，能做的只是去最小化经验误差。

我们希望得到泛化能力强的学习器，即希望学习器在训练样本中学到适合所有潜在样本的“普遍规律”。然而，学习器学习能力过强时，会将训练样本自身拥有的一些特点当作是适合所有潜在样本的规律，这样在新样本上的泛化误差必然会变大。这种现象叫做过拟合。与过拟合相对的是欠拟合，欠拟合一般是由于学习器学习能力太弱导致的。造成过拟合的因素有很多，比较常见的是学习器学习能力过强，而样本相对太少；这样学习器就会学到训练样本中不太一般的特性。过拟合往往是不可避免的，但是可以缓解。暂时打算在后面维度诅咒的博客里，举一些过拟合的例子。

评估方法

在现实任务中，对于同一个问题，我们可以选择很多种学习算法；甚至对于同一个学习算法，当选择参数不同的时候，就会产生不同的模型。我们该选择哪一种学习算法，哪一种参数配置呢？这时就要用到模型选择了 (Model Selection).

通常我们拿到一个新的数据集，先将数据集 (D) 的30%(不超过(frac{1}{3}))用作测试集(test set)，然后再用剩下的数据(D_{1}) 来训练和选择模型(即用做训练集(training set)和验证集(validation set)). 对于训练集和验证集的划分，在不同情况下，有不同的适合划分的方法。

留出法

留出法直接将 (D_{1}) 划分为两个互斥的集合，其中一个集合作为训练集，一个作为验证集。需要注意的是，划分数据集时应尽量保持数据的分布一致性。不然会因为划分数据的过程引入额外的误差从而对最终结果产生影响。比如二分类问题，(D_{1}) 有1000个样本，其中正例500个，负例500个。我们现在选70%作为训练集，30%作为验证集。为了保持样本数据分布一致性，我们从正例中取70%负例中取70%作为训练数据。正例和负例中剩下的部分作为验证集。如果从采样角度来看数据划分的话，保留类别比例的采样方式通常称为分层采样。

留出法需要对数据集(D_{1})进行划分，这就会导致一种窘境：如果训练集S包括绝大多数样本，则训练出的模型可能更接近用(D_{1})训练出的模型，但由于验证集V样本数量过少，评估结果可能不够稳定准确。如果验证集V多包括一些样本，则用训练集S训练出的模型和用(D_{1})训练出的模型可能有较大的差别。这个问题没有十分完美的解决方案，常见的做法就是用大约(frac{2}{3} sim frac{4}{5})样本作为训练集，其他用做验证集。留出法的好处在于简单，而且只需要训练一次模型；缺点在于上面提到的窘境。

交叉验证法 (Cross Validation)

交叉验证法先将数据集(D_{1})划分为k个互斥的子集，并且每个子集尽可能保持数据分布的一致性(从(D_{1})中分层采样)。然后每次用k－1个子集作为训练集，用剩下的作为验证集。这样我们就得到了K组训练集/测试集。最终我们把k个验证集评估结果的平均值来作为该模型的评估值。交叉验证的稳定性和保真性(fidelity)很大程度上取决于k的取值。为了突出这一点，通常又称为k折交叉验证(k-fold cross validation)。 k最常用的取值是10.

当k等于(D_{1})样本个数m的时候，就得到交叉验证的一个特例：留一法 (LOOCV). 留一法每次只有一个样本作为验证集，这样就免除了随机划分样本方式的影响。同时，留一法每次用m－1个样本来训练数据，使得训练出的模型和在(D_{1})上训练出的模型很相似。但是，留一法每次要跑m次模型学习和预测的算法，当m比较大或者模型的复杂度比较高时，运行时间是很长的。通常留一法用在训练数据比较少的情况。

性能度量 (Evaluation)：

性能度量是衡量模型泛化能力的评价标准。 在对比不同模型的能力时，选择不同的性能度量，往往会导致不同的评判结果。

均方误差 (Mean Square Error):

回归问题常用的性能度量是均方误差(MSE):
$$E(f,D) = frac{1}{m} sum_{i = i}^{m} (f(mathbf{x_i}) - y_i)^2$$

其中，(D = {(mathbf{x_1},y_1),(mathbf{x_2},y_2),…(mathbf{x_m},y_m)}) 为训练集，(y_i)为样例(mathbf{x_i})的label。(f) 为我们学到的模型(预测函数)。 均方误差评估的是学习器 (f) 的预测结果和真实结果差异。

下面介绍分类任务中常用的性能度量。

错误率与精度：

错误率和精度是分类任务中经常用到的性能度量标准，即可用在二分类任务上，也可用在多分类任务上。
错误率是分类错误的样本占总样本数的比例，精度是分类正确的样本占样本数的比例，错误率＝ 1 - 精度。用公式表示就是：
$$E(f;D) = frac{1}{m}sum_{i=1}^{m} mathbb{1}(f(x_i) neq y_i)$$
$$acc(f;D) = frac{1}{m}sum_{i=1}^{m} mathbb{1}(f(x_i) = y_i)$$

准确率 (Precision)、召回率 (Recall) 与 F1：

错误率和精度虽然很常用，但是并不能满足所有的任务需求。比如在信息检索，web搜索应用中，我们想知道“检索出的信息中有多少比例是用户感兴趣的”(准确率)，或者“在用户感兴趣的信息中，有多少被检索出来”(召回率)。

下面以一个例子说明，precision 和 recall 的具体计算公式。对应检索信息和用户兴趣这个例子，有如下混淆矩阵：

用户感兴趣(真实情况) 用户不感兴趣(真实情况)
被检索出(预测结果) True Positive (TP) False Positive (FP)
未被检索出(预测结果) False Negative (FN) True Negative (TN)

其中，TP＋FP＋FN + TN = 样本总数。

则准确率：
$$ P = frac{TP}{TP+FP}$$

召回率：
$$ R = frac{TP}{TP + FN}$$

通常来讲，准确率和召回率是一对矛盾的度量。一般来说，准确率高时，召回率低；召回率高时，准确率偏低。比如一共有m个样本，其中p个正样例，n个负样例。取极限情况，当只检测出一个样本，且它是正样例，则准确率为100%，而召回率为(frac{1}{p}). 当全部样本都被检测出来，召回率为100%, 而准确率为(frac{p}{m}).

以准确率为纵轴，召回率为横轴，绘制的P-R曲线，常被用作衡量模型优劣的一个标准。如果P-R曲线中，一个曲线(l_1)完全包住另一个曲线，则认为(l_1)对应的学习器效果好。“平衡点” (Break-Even Point 简称：BEP)为P-R曲线上召回率＝准确率处的点。若模型的BEP点高，说明该模型的准确率和召回率取得相对“双高”的比例，则该模型的效果较好。

但是BEP还是过于简化了些，更常用的是F1度量：
$$F1 = frac{2times P times R}{P + R} = frac{2times TP}{m-TN + TP}$$

F1 是基于准确率和召回率的调和平均 (harmonic mean) 来定义的.
$$frac{1}{F_1} = frac{1}{2}(frac{1}{P} + frac{1}{R})$$.

然而在一些应用中，对准确率和召回率的重视程度是不同的。例如在商品推荐系统中，为了尽可能少的打扰客户，更希望推荐的内容是客户感兴趣的，这时准确率更重要；在逃犯信息检索系统中，更希望尽可能少的漏掉逃犯，此时召回率更重要。F1的一般形式(F_{beta})，能让我们表达出对准确率和召回率的不同偏好。
$$ F_{beta} = frac{(1+ beta^2)times P times R}{(beta^2 times P) + R}$$
(beta = 1) 时，(F_{beta}) 变为(F1); (beta < 1) 时，准确率有更大影响；(beta > 1) 时， 召回率有更大影响。

当我们有n个混淆矩阵的时候(多分类任务，或者进行多次训练／测试等)，我们如何来求准确率和召回率呢？
一种直接的做法是在每个混淆矩阵上分别求出准确率和召回率，然后将这n个准确率和召回率的平均值来作为这n个矩阵的准确率(bar P)、召回率(bar R)，然后用(bar P)和(bar R)算出相应的F1。另一种做法是对n个混淆矩阵的对应元素取平均值，得到(bar {TP} bar {FP} bar {TN} bar {FN} ), 在基于这些平均值来计算准确率、召回率和F1.

(R^2) (Coefficient of Determination)

这学期在上王浩老师的机器学习课程，在课上他提到，现在业界很多都通过(R^2)来看学习器性能好坏。(R^2)衡量的是数据有多大程度上fit我们的model。
$$R^2 = 1 - frac{sum_{i=1}^{m} (f(mathbf{x_i}) - y_{i})^2}{sum_{j=1}^{m} (y_{j} - bar y)^2} = 1- frac{SS_{res}}{SS_{tot}}$$.

(R^2)多用于回归问题上，当(R^2)越接近1时，说明我们的regression line越完美的fit数据；当(R^2)越接近0时，说明regression line 越不fit数据。

非均等代价

在现实生活中经常会遇到这种情况，不同类型的错误会造成不同的后果。比如将一个患者诊断为健康人和将一个健康人诊断为患者。后者的影响是增加了进一步检查的麻烦，而前者的后果却可能是失去了拯救生命的最佳时机。为了权衡不同类型错误所造成的不同损失，可以使用非均等代价。 在前面的性能度量中，都隐性的假设了均等代价。而在非均等代价中，我们希望最小化的是“总体代价”。更详细的描述可以参考周志华老师机器学习新书.

比较检验：

当我们在测试集上得到了学习器的某个性能度量的结果，我们可以用这个数值通过比大小的方式来比较不同学习器的泛化能能力吗？在机器学习中，比较这件事比通常想象的要复杂。对于学习器泛化能力的比较，我们要用统计假设检验来说明若在测试集上观察学习器A比学习器B要好，则在统计意义上A的泛化性能是否优于B。更多详细描述可以参考周志华老师新书.

Reference