西瓜书第二章-经验误差与过拟合
经验误差与过拟合
通常，错误部分占总样本的比例数称为错误率。如果m中有a个是错误分类的，那么错误率E = a/m。相应的，1-a/m叫做精度即精度=1-错误率。一般来说，学习到的预测输出和真实输出的差值称之为误差（error）。训练集上的计算误差叫做训练误差或者经验误差，在新样本上的叫做泛化误差。显然，我们希望有一个更小误差的学习器。然而，由于新样本的细节在训练阶段是不可知的，在实践中我们进可以尝试最小化经验误差。通常，我们得到的学习器在训练集上表现良好，很小甚至0的经验误差，也就是说百分百准确。然而，我们需要什么样的学习器呢？不幸的是，这样的学习器大多数情况下都不是很好。
我们在寻找的好的学习器应该是在新样本上表现良好的。因此，一个好的学习器需要学习训练样例中普遍的规则，这样学到的规则就可以用于所有的可能的样本。然而当学习者把样本学习的太好时，很可能一些样本的某些特殊性当做所有潜在样本的一般属性。导致泛化性能变差。在机器学习中，这种现象叫做过拟合。对应的想象叫做欠拟合，这是学习者无法学习训练样本的一半性质
如图所示过拟合和欠拟合。
在许多可能的原因中，过度强大的学习能力是导致过拟合的常见原因，如学习器 可以学习到训练样本中非普遍的特性。相比这下，欠拟合通常是由于学习力低下导致的。事实上，欠拟合是相对容易克服的。我们可以在决策树学习中做更多的分支，或者添加更多的训练轮数在神经网络中。然而我们稍后会看到，过拟合是机器学习中一个基本的难题，几乎每一种学习算法都实现了一些处理过拟合的机制。尽管如此，我们需要知道过拟合是不可避免的，我们所能做的就是减轻和减少他的风险。这个论点可以简单的证明如下。机器学习问题通常是NP-hard甚至更难的，但是实际的学习算法必须在多项式时间内完成。因此，如果过拟合是可避免的，他最小化误差然后得到最优解，我们就有了建设性的证明P=NP。换句话说，只要我们相信P！=NP 过拟合就是不可避免的。
在实践中，通常有多个候选学习算法，即使是同一种算法在不同的参数设置下也会产生不同的模型。所以，我们应该选择哪种算法，我们该用哪种参数设置？这就是模型选择（model selection）问题。理想的解决方案是评价候选模型，选择最小化泛化误差的一个。然而就如刚才提到的我们不能直接得到泛化误差，经验误差会受到过拟合的影响，所以实践中我们如何评估和选择一个模型呢？
评估方式
通常，我们可以通过测试实验评估泛化误差。就这样我们使用了测试集来评估学习器对新样本分类的能力，使用测试误差作为泛化误差的近似值。通常，我们假设测试样本是独立的，从真实输出分布中相同采样。注意测试集和训练集应该尽可能的互斥。测试样本需要避免出现在训练集中或者在训练过程中被任意使用。
我们要让测试集避免出现在训练集中呢？为了理解这点，让我们考虑如下场景。假设我们在考试和练习中使用同样的十道题，那么考试能反映出学生的学习成功吗？答案是“不”，因为有些学生即使只知道如何解决这十个问题，也能取得好成绩。相应的，训练集代表测试，测试集代表考试。因此，如果训练过程中已经可以看到测试样本，则估计可能过于乐观。
然而给定m个样本的唯一数据集 D = {(x1,y1),(x2,y2),....,(xm,ym)},我们怎样才能同时进行培训和测试？答案是从数据集D中生成训练集S和测试集T。下面我们讨论几种常用的方法。
留出法
留出法划分了数据集D成为不相交的子集。一个训练集S和另一个测试集T，D=S∪T同时S∩T=∅（即S和T没有交集），我们在训练集S中训练模型，在训练集T中计算测试误差来估计泛化误差。
以二分类问题为例，设D为数据集的1000个样本，我们切分700个样本到训练集S中，给测试集T300个样本。在S上训练之后，假设模型在T上错误分类了90个样本，我们得出错误率（90/300）x100%=30%，相应的正确率是70%。
值得一提的是拆分应该保持原有的数据分布避免移入额外的偏差。已分类问题为例，我们需要保持样本的类别比例相似。如果从来样(sampling) 的角度来看待数据=集的划分过程，则保留类别比例的采样方式通常称为"分层采样" (stratified sampling)。例如，假设我们用D数据集包括了500个正例，500个反例，我们希望划分训练集S占样本的70%，训练集T占样本的30%。分层采样方法会确保S包含350个正例和350个反例，T包含150个正例和150个反例。没有分层采样，不同类型比例的在S和T中会导致估计偏差，因为数据的分布发生了变化。
然而，即使按分类比例相同，原始数据集仍然存在不同的分割方法。举个例子，我们可以在D中对样本进行排序然后使用前350个样本进行训练，其余的用于测试。不同的分割方式会导致不同的训练集和测试集，并得出不同的模型评估结果。因此单次留出法测试可能导致结果不够可靠。在实践中，我们通常进行多次留出测试，每次试验分割随机数据，我们使用平均偏差表示我们的最终估计。举个例子，我们可以随机切分数据集100次以产生100个评估结果，然后取平均值，作为留出误差的评估。
留出法分割了D到训练集和测试集中，但是我们希望评估的是用D训练出的模型的性能。我们陷入窘境。如果我们让大部分样例在训练集S中，那么训练集会很好的接近模型D的训练结果。然而，评估的可信度较小因为T的估摸很小。另一方面如果我们让更多的样例在测试集中，S和D的训练结果将会相差很大，评价的保真度降低这种困境没有解决办法，我们必须做出权衡。一个常规是使用大约2/3到4/5的示例进行训练，其余的用于测试。
交叉验证
交叉验证将数据集D分成k个大小相似的不相交数据集，D=D1∪D2∪...∪Dk,Di∩Dj=∅(i != j),每个子集Di通过分层采样保持原始数据分布。在每次交叉验证中，我们使用k-1个子集的并集作为训练集使用剩下的子集作为测试集去评估模型。我们重复这个过程k次，并将每个子集作为测试集正好使用一次。最终，我们对k次试验求平均值，得到评价结果。因为交叉验证的稳定性和保真度在很大程度上取决于k的值，这个方法也被称为k折交叉验证。最长用的k值是10，相应叫做10折交叉验证。其他常见的值包括5和20。2.2展示了10折交叉验证。
与留出法相似，将数据集D划分为k个子集同样存在多种划分方式。为了减小因样本呢划分不同而引入的差别，k折交叉验证通常要随机使用不同的划分重复p次，最终的评估结果是这p次k折交叉折叠验证结果的均值，例如常见的有10次10折交叉验证。
对于有m个样本的数据集D（k=m）一个交叉验证的特例是留一法leave-one-out（LOO）。在这个例子中，随机切分不重要，因为只有一个方法可以将m个样本分割成m个子集。在留一法中，每个自己都包含了单一的样例，训练集只比原始数据少一个样本。因此在大多数情况下，留一法的评估非常接近在D上训练模型的理想评估。因此留一法的评估结果通常被认为是准确的。然而留一法也有缺点，那就是训练m个模型的计算代价对于大型数据集来说可能过高。（一百万个样本意味着一百万个模型），如果我们考虑参数的调整，此外，留一法的评估结果未必永远比其他评估方法准确，没有免费的午餐定理对于评估方法同样适用。
"没有免费的午餐"(No Free Lunch, NFL)定理是一个重要的概念,它在优化理论和机器学习领域有广泛应用。
这个定理的核心思想是:
没有一种优化算法或机器学习模型能在所有问题上都优于其他算法或模型。换句话说,任何算法在某些问题上的表现都会优于其他算法,但在另一些问题上则会表现不如其他算法。
这意味着,我们不能期望找到一种"银弹"式的通用算法或模型,可以在各种不同的问题上都取得最优的表现。这也说明了优化算法和机器学习模型的选择都需要根据具体问题而定。
自助法
我们想要评估的是D训练后的模型。然而，无论我们使用交叉验证还是留出法，训练集总是小于D。因此，估算偏差是不可避免的因为训练集的大小规模和D是不一样的。我们可以用留一法减小这个偏差，但是计算复杂性却让人望而却步。然而是否有可能在保持计算的效率的同时减少训练集的影响？
一个解决方案是自助法，它使用了自主采样技术。给定一个一个包含了m个样例的数据集D，自助法通过从D中随机抽取一个样本复制到D'，然后把他放回D，这样下次还有机会被选中。重复这个过程m次返回自主采样的数据集合D'包含了m个样例。由于替换，一些样本在D中而不在D'而其他可能会出现不止一次。让我们快速估计：在m轮中未被选中的概率是1-1/m因此取极限
$$ \lim_{m\to\infty}\left(1 - \frac{1}{m}\right)^m=\frac{1}{e} \approx 0.368 $$
这意味着大约有36.8%的原生样本没有出现在集合D'中。然后我们可以使用D'表示训练集DD'表示测试集，这样，实际评估的模型与期望评估的模型都是用m个训练样本，而我们仍有数据总量约1/3的、没在训练集中出现的样本用于测试。这样的测试结果亦称包外估计（out-of-bag estimate）
自助法在数据集很小或者没有有效方法去切分数据集的情况下表现良好。此外，自助法可以创建多个数据集，这对于诸如集成学习之类的方法是有用的。然而，原始数据分布会因为自助法而改变，估计也会产生偏差。因此，当我们拥有丰富的数据时，通常会使用保留和交叉验证。
参数参数调整与最终模型
大多数的学习算法都需要有参数的设置，不同的参数设置通常导致不同的表现。因此模型评估和选择不只是选择学习算法也是配置参数。程序找到正确的参数这个过程叫做调参（parameter tuning）。
读者可能会认为调参和算法选择没有本质的区别：每个参数设置都会导致一个模型，我们选择一个产生最好作为最终模型的参数。这个想法基本上是合理的，然而有一个问题：参数通常需要重新评估，尝试每一个参数是不可能的。因此，在实践中，我们通常设置给参数设置范围和步长，即，范围是[0,02]步长是0.05，这就导致只有5个候选参数设定。这种计算代价和估算质量之间的权衡使得学习是可行的，虽然选出的参数通常不是最佳的。事实上，即使在做出这样的权衡之后，调参依旧相同具有挑战性。我们可以做一个简单的估计。假设算法有三个参数每个参数有五个选择，那么我们需要为每对训练集和测试集评估5^3 = 125个模型。强大的学习算法通常有非常多的参数需要设置，导致大量的参数调优工作。在真实世界的应用中优质的调参通常是至关重要的。
我们需要注意到训练过程不使用所有数据，因为不分数据被保留用于模型的评估和选择。因此，在我们经由模型选择后有了确定的算法和参数之后，这个数据集用来重新训练模型作为最终交付。
最后同样重要的，我们应该将用于模型选择的数据与模型选择后遇到的测试数据区分开来。我们通常把模型选择中使用的数据集叫做验证集。举个例子，我们可以将数据分成训练模型的训练集，用于模型选择和参数调整的验证集，和用于评估模型泛化能力的测试集。
性能度量
要评价模型的泛化能力，我们需要不止需要真实和有评估方法，还需要一些性能度量他可以测定泛化能力。不同的性能度量反应了任务的各种需求也产生了不同的评估结果。换句话说，模型的质量是一个相对的概念他取决于算法和数据以及任务的需求。
在预测问题中，我们给定数据集D{(x1,y1), (x2,y2), . . . , (xm,ym)}。y1是样例x1真实值。为了评估学习者f的表现，我们将它预测f(x)与真实标签y进行比较。
对于回归问题，最常用的性能度量是均方误差Mean Squared Error（MSE）：
$$ E(f;D)=\frac{1}{m}\sum_{i=1}^{m}(f(x_i)-y_i)^2 $$
更广泛的说，对于数据分布D和概率密度函数p(.)均方误差是
这是一个常见的机器学习损失函数的定义
$$ E(f;D)=\int_{x \sim D} (f(x) - y)^2 p(x) dx $$
本章其他的部分会介绍一写分类问题的常见性能度量。
错误率和精度
在本章的开头，我们讨论了错误率与准确性，哪些是分类问题中最常用的性能度量，包括二分类问题和多分类问题。错误率是错误分类样本所占的比例，而准确率则是正确分类样本的比例。给定数据集D，我们定义错误率
$$ E(f;D)=\frac{1}{m}\sum_{i=1}^{m} \mathbb{I}(f(x_i) \neq y_i) $$
精度是
$$ E(f;D)=\frac{1}{m}\sum_{i=1}^{m} \mathbb{I}(f(x_i) = y_i) =1-E(f;D) $$
一般来说，数据分布D和概率密度函数p(.)，错误率和精度可以分别表示为：
$$ E(f;D)=\int_{x \sim D} \mathbb{I}(f(x) \neq y)^2 p(x) dx\\ acc(f;D)=\int_{x \sim D} \mathbb{I}(f(x) = y)^2 p(x) dx\\ =1-E（f;D ） $$
查准率，查全率，和F1
错误率和正确率是最常用的，但是它们并不适合所有任务。以我们的西瓜问题为例，假设我们使用机器学习对新的一批西瓜进行分类。错误率表示这批西瓜中被错误分类的西瓜占所有西瓜的比例。然而，我们可能需要知道，摘下来的西瓜熟了的比例是多少？或者所有熟了的西瓜中有多少被摘了出来，不幸的是，错误率不能回答这个问题，因此我们需要其他的性能度量。
这些问题通常发生在信息检索和网络查询中。举个例子，在信息检索中我们通常需要知道 用户感兴趣的检索信息的百分比是多少，和检索到的用户感兴趣的信息是多少？对于这个问题，查准率和查全率是更好的选择。
在二分类问题中，真值和预测值有四种组合：分为真正例(true positive) 、假正例 (false positive) 、真反倒(true negative)假反例 (false negative) 四种情形。我们分别表示每种情况样本的数量TP，FP，TN和FN。TP+FP+TN+FN=总样本数。四类结果可以展示位混合矩阵。如图所示：
查准率P和查全率R分别表示为
$$ P=\frac{TP}{TP+FP},\\ R=\frac{TP}{TP+FN}. $$
一般来说查准率和查全率是相互矛盾的。一般来说，当查准率较高时一般查全率较低，查全率高时查准率就低。举个例子，摘更多的熟西瓜，我们可以增加摘西瓜的数量，在极端环境下，如果我摘取了所有西瓜，就能把全部成熟的西瓜摘下来。然而这样子做查准率会很低。另一方面，如果我们希望提高西瓜成熟的比例，我们需要只摘取我们确定的西瓜。注意，在简单问题中，我们可以实现高查准率和高查全率。
经常性的，我们可以使用学习器对预测结果进行排序，最可能是正例子的样本位于排名的顶部，最不可能是正例的排到排名底部。从排名榜首开始，我们可以递增的将样本标记为阳性，以计算每次递增的查准率和查全率。然后我们将查准率绘制为y轴，召回率绘制为x轴，给出了查准率查全率曲线Precision Recall Curve (P-R curve)，显示该曲线的图成为PR图，如下图
P-r曲线直观的展示了整体的查准率和学习器的查全率，当比较俩条曲线，如果PR一个PR学习器完全包含了另一个学习器，那么前者的学习器更好。举个例子，图2.3中，学习器A比C更好。然而当P-R曲线相交时，例如A和B，我们不能说那个学习器输出结果更好，只能在特定的查准率和查全率下进行比较。然而，人们通常减枝要找出最好的学习者，即使他们存在交叉。一个合理的方案是比较曲线下方的面积，在某种程度上，它表示正确率和召回率相对较高的情况比例。然而这个面积不容易计算，因此我们通常采取其他的衡量标准，同时考虑查准率与查全率。
一个选择是平衡点 Break-Even Point (BEP)，这是当准确率和召回率相当时的值。例如2.3中，平衡点在学习器C的0.64，根据平衡点，学习器A比学习器B更好。
然而平衡点过于简化了，更一般使用F1作为替代。
$$ F1=\frac{2\times P \times R}{P+R}=\frac{2\times TP}{样本总数+TP-TN}. $$
在一些应用中查准率和查全率是不同的。举个例子，查准率在推荐系统中是非常关键的，更理想的是，推荐的内容是用户感兴趣的，并且尽可能的少干扰用户。另一方面，最烦信息检索系统中查全率是最重要的，我们希望少错过几个罪犯。f1测度的一般形式是Fβ，这能让我们明确自己对查准率和查全率的偏好，
$$ F_β = \frac{(1 + \beta^2) \times P \times R}{(\beta^2 \times P) + R} $$
其中β>0，度量了查全率对查准率的相对重要性。当β=1，他退化为F1；当β>1，查全率更重要，当β<1查准率更重要。
一般来说当F1是等于平衡点的。
很多时候我们有多个二分类混淆矩阵，例如，每一次训练和测试都有一个混淆矩阵。此外，当我们训练和测试多个数据集去评估整体性能时，会有多个混淆矩阵。此外，在多分类问题中每个类都有一个混淆矩阵。在所有这些情况下，我们需要研究总查准率和n个二元混淆矩阵的查全率。简单的方法是计算每个混淆矩阵中的查准率与查全率，记为(P1,R1),(P2, R2), . . . , (Pn,Rn)。我们得到了宏查准率（macro-P）宏查全率（macro-R），以及相应的宏F1（macro-F1）
$$ 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} $$
我们还可以计算跨混淆矩阵的元素平均来得到,再基于这些平均值计算出，微查准率（micro-P）、微查全率（micro-R）、微F1（micro-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
由于学习者的预测值通常是以真实值或者以概率的形式，我们可以比较预测值和分类阈值（threshold），即如果预测的值大于阈值则为正例，否则将它归类为反例。例如，典型的神经网络预测样本在[0.0,1.0]区间内的真实值。我们可以比较预测值和0.5进行比较，对样本进行分类，如果预测值大于0.5，其他都是反例。因此，预测的真值或者概率直接确定了泛化能力。在实践中，我们排序测试样例的根据预测的真值或者概率降序进行排序，以便潜在的正例样本在列表的顶部。之后，我们我们在排完序的列表中设置截断点（cut point）对上面的样本进行分类。它是正的其余是负的。
临界点的位置取决于特定的应用。例如如果查准率比查全率重要，我们移动临界点到列表的顶部。否则就将它移动到底部。因此，排名质量反应了学习器对于不同任务的期望泛化能力或特例的泛化能力。ROC的全称是受试者工作特征Receiver Operating Characteristics 曲线遵循着上述子项来衡量学习器的泛化能力。
ROC曲线最初是在第二次世界大战中为敌机的雷达探测而开发的，然后在1960-1970年推广到了心里和医疗应用。之后在1989年被推广到了机器学习。类似于P-R曲线。我们根据预测排序样本，按此顺序逐个把样本作为正例进行预测，通过将切点从排名列表的顶部移动到底部来获得俩个指标。使用这个俩个指标在x轴和y轴上绘制ROC曲线。不像查准率和P-R查全率曲线，ROC中的y轴是真正例率(True Positive Rate ）横轴是假正例率（False Positive Rate ）重复使用2.1中的符号，俩个度量分别定义是
$$ TPR=\frac{TP}{TP+FN}(2.18)\\ FPR=\frac{FP}{TN+FP}(2.19) $$
展示了ROC曲线的叫做ROC图。2.4给了ROC图的例子，对角线对应于随机猜测模型，(0,1)点对应将所有正例排在反例之前的理想模型。（即根据排序后所有正例都比反例权重大）
实践中，我们都只有有限对的FPR，TPR坐标来绘制ROC图，因为测试样例是有限的。因此，ROC曲线可能看起来不像2.4中的a而只是一个近似的，就像2.4b一样。绘图的过程如下：给定m+哥正例和m-个反例，我们首先根据学习器的预测排序所有样例，然后分类阈值设为最大，此时TPR和FPR是0，所以我们标记(0,0)。然后，我们逐渐降低阈值知道每个样本的预测值沿着排序列表，将样本一次归类为阳性。设这个坐标为(x,y)，如果当前的样本是真正例我们设置标记为(x,y+1/m+)如果当前样本是假正例我们标记为(x+1/m-,y)。连接附近所有的点我们就有了ROC曲线。
简单来说根据当前为正例或者概率排一个列表，然后设置一条基准线从高概率到低概率扫过列表，然后逐渐绘制出这个曲线。一开始只计算高概率的准确性所以准确度非常贴近于1，然后计算了低概率的曲线，所以准确性就下来了。
如同P-R图，如果A的AOC曲线完全覆盖了B的AOC曲线我们说学习器A比学习器B更好，然而当他们存在交集，没有一个学习器比另一个学习器更好。一个比较相交的AOC曲线的方法是计算ROC曲线下的面积，即ROC曲线面积（Area Under ROC Curve）AUC
根据定义可知，AUC可以通过对ROC曲线步长下面的面积进行积分计算。假设ROC曲线是依次连接这些点得到的{(x1, y1), (x2, y2), . . . , (xm, ym)},x1=0,xm=1。图2.4说明了AUC估计为
$$ AUC=\frac{1}{2}\sum^{m-1}_{i-1}(x_{i+1}-x_i)\cdot(y_i + y_{i+1}) $$
AUC与排名误差密切相关，因为它考虑了排名的质量。设m+代表正例的数量，m-代表反例数量，D+代表正例的集合，D-代表着反例的集合。那么排名的loss可以定义为
$$ l_{\text{rank}}=\frac{1}{m^+m^-}\sum_{x^+ \in D^+} \sum_{x^- \in D^-} (\mathbb{I}(f(x^+) < f(x^-)) \frac{1}{2} \mathbb{I}(f(x^+) = f(x^-))) $$
每一个正例x+和反例x-，如果预测值正例小于他反例的预测值，则对排序损失记一个罚分，当预测值相等时，惩罚为0.5。假设(x,y)是正例坐标的AOC曲线。那么x是正例样本上反例样本的比例（即FPR）。因此lrank是对应ROC曲线之上的面积
$$ AUC=1-l_{rank} $$
代价敏感错误率和代价曲线
在一些问题中不同类型的错误造成的后果不同。以医学诊断为例，根据我们之前的讨论，我们将某人错误的分为健康和不健康将会受到相同的罚分。错误的将病人到健康人群是更严重的，因为病人的生命受到了危险。另一个例子是控制访问系统，拒绝中场用户访问会导致不好的用户体验，但是通过了入侵者会导致安全问题。在这些例子中我们需要为不同的错误赋予非均等代价。
对于二分类问题，我们可以根据任务领域的知识设定一个代价矩阵（cost matrix）
其中costij代表将i类样本错误的分为j类的代价。一般costii=0，如果错误的将0类当做1类的代价比相反更大那么cost01>cost10。代价之间的差异越大，const01就和cost10之间的差距越大（一般来说我们更关心他们的比例而不是绝对值比如cost01:cost10=5:1等同于cost01：cost10=50:10）
到目前为止我们讨论的性能度量都假设它等于代价。例如错误率在不考虑后果的情况下计算错误数量，没有考虑不同错误的代价。然而在代价相同的情况下，我们不再最小化错误次数，而是最小化总代价。对于二分类问题，我们称正例为0类反例为1类。设D+和D-分别表示正例集合与反例集合。那么基于表2.2代价敏感的错误率定义为
$$ E(f; D; cost) = \frac{1}{m}(\sum_{x_i∈D^+} \mathbb{I}(f(x_i) ≠ y_i) × cost_{01} + \sum_{x_i∈D^-} \mathbb{I}(f(x_i) ≠ yi) × cost_{10}) $$
同样，我们也可以定义基于分布的代价敏感错误率和代价敏感版本的准确率。通过costij的i和j取0和1以外的值，则可以定义多累任务的敏感性能度量。
在非均等代价下，我们从代价曲线中而不是ROC曲线中找到学习者的期望总代价。代价曲线的x轴是正例的代价概率
$$ P(+)cost = \frac{(p × cost_{01})} {(p × cost_{01} + (1 - p) × cost_{10})} $$
p取值在[0,1]之间是样例为正的概率，y轴是归一化代价取值为[0,1]
规范化 Normalization是将不同范围的值映射到固定范围的过程
归一化代价是一种计算模型性能的方法，用于将不同尺度的损失函数统一到一个共同的范围内，以便更好的比较和评估模型在不同性能下的表现
$$ \text{cost}_\text{norm} = \frac{FNR \times p \times \text{cost}_{01} + FPR \times (1 - p) \times \text{cost}_{10}}{p \times \text{cost}_{01} + (1 - p) \times \text{cost}_{10}} $$
其中FRP是假正例率，FNR=1-TPC是假反例率。我们可以绘制代价曲线根据：因为在ROC曲线上的每一个点 (FPR,TPR)对应着代价平面上的线段。我们可以计算FNR和绘制线段从（0，FPR）到（1，FNR）。然后，线段下的面积表示给定p的期望总成本，FPR和TPR。
通过将ROC曲线上所有的点转换为代价平面上的线段，期望总成本由所有线段下界下的面积给出，如图。
比较检验
一种看起来很简单的比较学习器的方式是实用评估方法和性能度量，例如，我们使用评估方法去度量学习器的性能并比较它们。那么我们如何进行比较呢？我们如何检查测量值中哪个更好？性能比较由于以下原因比我们想象的要复杂。首先我们希望比较俩个模型的泛化性能，但是评估方式只能是我们去评定测试集。这样对比也许无法反应真实的泛化性能。其次测试集的性能取决于测试集的选择。俩个不同大小测试集的结果，或者俩个相同大小但是不同样例的测试集都可能导致结果不同。最后，很多的机器学习算法都有一些内置的随机行为，这意味着我们及时使用同一个参数和测试集也可能会得到不同的结果。那么有什么合适的方法来比较学习器的性能吗。
统计假设检验是一个比较学习器性能的方法。假设我们观察到学习器A在测试集上的表现由于学期B。统计假设验证可以帮助我们检查，学习器A是否在统计学意义上由于学习器B，并且这个优势有多显著。在下面的讨论中，我们将介绍俩种基础的统计假设检验和几种比较学习器的方法。为了便于讨论，本届假设错误率为性能度量，用ε表示。
假设检验
在假设经验中，假设是关于学习者泛化错误率分布的判断或者猜测。即ε=ε0，实践中，我们只有测试泛化误差率没有泛化误差率。即便这俩这可能是相等的，直觉上它们可能很接近。因此我们可以使用测试错误率分布推断泛化错误率分布。
泛化错误率ε意味着学习器做出错误预测的可能性。测试错误率代表着学习器对错误分类了 测试集错误率 x m数量的样本，在m个样例中。假设测试样本是在样例中随机分布的。然后，学习器的泛化错误率ε，错误分类的m'个样例，和其余的分类样本全都正确分类的概率是ε^m'(1-ε)^(m-m')。所以对于泛化错误率ε，泛化错误率为ε的学习器被测得错误率为 测试集错误率的概率为
$$ P(\hat\epsilon; \epsilon) =\begin{pmatrix} m\\ \hat\epsilon \times m\end{pmatrix}\epsilon^{\hat\epsilon\times m} (1-\epsilon)^{m-\hat\epsilon \times m}\\ $$
给定错误率，则解
$$ ∂P(\hat e;e)/∂\epsilon=0 可知\epsilon=\hat\epsilon时最大|\epsilon-\hat\epsilon|增大时，P(\epsilon;\epsilon)减小 $$
这符合二项(binomial 分布，如 2.6 所示，若 = ，则 10个样本中测得 个被误分类的概率最大.
w我们可以用二项检测来检验假设ε<=0.3，概率错误率不大于0.3，更一般的说，假设ε<=ε0（2.27）。给出概率在1−α范围内的最大可观察错误率。这个概率也被称为置信度，对于非阴影的部分。
如果在测试集中的错误率$\hat \epsilon$小于临界值$\overline\epsilon$,根据二项式检验，假设$\epsilon\leq \epsilon_0$不能被拒绝，即能以1-a的置信度认为，学习器的泛化错误率不大于$\epsilon_0$否则该假设可能被拒绝，即在a的显著度下可认为机器学习的错误率大于$\epsilon_0$
我们通常获得多个测试错误率通过交叉验证或者多次留出法评估。在这个例子中，我们可以使用t-检验（t-test），设$\hat \epsilon_1,\hat \epsilon_2,....\hat \epsilon_k$表示k个测试错误率平均错误率μ和方差为$\sigma^2$，则分别有
对假设$μ=\epsilon_0$和显著度a，我们可以计算出当测试错误率均值为$\epsilon_0$时，在1-a概率内能观测到最大错误率，即临界值。这里考虑双边（two-tailed）假设如图2.7，俩边阴影各有a/2的面积；假设阴影部分范围分别为$[-∞,t_{a/2}]和pt_{-a/2},∞]$。若平均错误率μ与$\epsilon_0$之差$|μ-\epsilon_0$|位于临界值范围$[-∞,t_{a/2}]和pt_{-a/2},∞]$内，则不能拒绝假设μ=$\epsilon_0,$即可认为泛化错误率为$\epsilon_0$,执行度为1-a，否则可拒绝该假设，即在该显著度下认为泛化的错误率与$\epsilon_0$有显著的不同，a常用的取值有0.05和0.1，
交叉验证t检测
对于学习器A和B，设为$\epsilon_1^A\epsilon_2^A...\epsilon_k^A和\epsilon_1^B...\epsilon_k^B$，代表是从k折交叉验证中取到的，i表示第i折，那么，我们可以使用k折交叉验证配对t-检验来比较俩个学习器。其基本的思想是，如果俩个学习者表现的性能相同，那么在相同的训练集和测试集上，测试错误率应该是相同的。$\epsilon_i^A=\epsilon_i^B$
具体来说，对于从k折中得到的k个测试错误率对，我们计算每一对的结果$Δ_i=\epsilon^A_i-\epsilon^B_i$，如果差异为0则俩个学习器的性能应用。基于$Δ_1,Δ_2....Δ_k$，来对学习器A与B性能相同这个假设做t检验，计算出差值的均值μ和方差$sigma^2，再显著度a下，若变量
$$ T_t = \frac{\sqrt{k\mu}}{\sigma} $$
小于临界值$t_α/2,k-1$则假设不能被拒绝。即认为俩个学习器的性能没有显著的差别；否则认为俩个学习器有显著的差别，，且平均错误率较小的那个学习器性能较优。这里$t_{\alpha/2，k-1}$是自由度为k-1的t分布上尾部累计分布为a/2的临界值
欲进行有效的假设检验，一个重要前提是测试错误率均为泛化错误率的独立采样。然而因为样本是有限的，在交叉验证等评估方法中，训练集往往是重叠的。因此，错误率确实不是独立的，导致假设成立的概率被高估。为了缓解这个问题，我们可以使用5x2交叉验证。因为在2折交叉验证之前数据是随机分布的，所以在5轮的交叉验证中，数据分布是不同的。我们获取学习器A和B的第i个二折交叉验证的错误率。我们计算他第一次折叠的误差记为$Δ_i^1$和第二次的差值$Δ_i^1$。为了缓解测试错误率的独立性，我们计算每个2折交叉验证的方差。
$$ \sigma^2_i=\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 $$
变量服从自用度为5的t分布，其双边检验的临界值$t_{\alpha/2,5}$当a=0.05是，为2.5706，a=0.1是为2.0150
McNemar校验
对于二分类问题，留出方法不仅估计了学习者A和学习者B的测试错误率，也评估了俩个不同的学习者的错误分类。俩者的数字都正确，错误和一个正确另一个错误。如列联表所示
如果俩个学习器的性能相同，我们则有e01=e10.w如果不同变量|e01 − e10|，因此变量
$$ \tau_x^2 = \frac{(|e_{01} - e_{10}| - 1)^2}{e_{01} + e_{10}} $$
服从自由度为1的卡方分布，即标注状态分布变量的平方。当给定显著度a，当以上变量值小于临界值$x_a^2$时，不能拒绝该假设，即认为俩个学习器的性能没有显著差异；否则就拒绝该假设，认为俩者性能有显著差别，切平均错误率较小的性能较优。自由度为1的卡方检测的临界值当a=0.05时为3.8415，a=0.1时为2.7055
Friedman检验和Nemenyi后续检验
交叉验证t检验和McNemar检验都是在单个数据集上比较两种算法。然而，一些时候要对多个数据集的多个算法进行比较。这种情况下，我们可以使用交叉验证t检验或McNemar检验来比较每个数据集上的每对算法。或者我们可以使用基于算法排序的Friedman测试来比较算法来一次比较所有数据集上的所有算法。
假设我们有算法ABC在D1，D2，D3和D4四个数据集上。我们首先使用hold-out或交叉验证来获得每个算法在每个数据集上的测试结果。然后我们根据他们的测试表现对数据集上的每个算法进行排序，1,2,...因此，其中具有相同测试性能的算法共享平均排名，例如图2.5所示
在数据集D1和D3上，A是最好的，B是第二的C是最后的。在数据集D2上，A是最好的，B和C的性能是应用的。在收集了所有数据集之后，我们计算每个算法的平均排名在最下面一行。根据Friedman测试判断算法性能是否都相同，如果相同它们的平均值应该相同。设k个算法n个数据集，ri表示第i个算法的平均值。为了简化讨论，暂时不考虑平均序值的情况，则ri服从正态分布，其均值和方差分别为(2+1)/2和（k^2-1）/12
$$ \tau_x^2 = \frac{k-1}{k} \cdot \frac{12N}{k^2-1} \sum_{i=1}^k \left(r_i - \frac{k+1}{2}\right)^2 = \frac{12N}{k(k+1)} \left(\sum_{i=1}^k r_i^2 - \frac{k(k+1)^2}{4}\right)(公式2.34) $$
在k和N都较大时，服从自由度为k-1的卡方分布。
然而上述的原始Friedman校验过于保守，现在通常使用变量
$$ \tau_F = \frac{(N - 1)\tau_x^2}{N(k - 1) - \tau_x^2}（公式2.35） $$
其中$\tau_{x^2}$由2.34得到$\tau_F$服从自由度为k-1和(k-1)(N-1)的F分布，表2.6给出了一些常用的临界值
如果假设算法的性能是相同的这个假说被拒绝，那么算法的性能是显著不同的。然后我们使用后续检验来进一步区分各算法。常用的有Nemenyi后续检验。Nemenyi检验计算平均序值差别的临界值域
$$ CD = q_\alpha \sqrt{\frac{k(k+1)}{6N}} $$
表2.7给出了a=0.05和0.1时常用的qa值。若俩个算法的平均值之差超出了临界值域，则以相应的置信度拒绝“俩个算法性能相同这一假设”
以表2.5的数据为例，先根据2.34和2.35计算 出$\tau_F$=24.429,以表2.5中的数据为例，先根据式(2.34)和(2.35)计算出TF=24.429，由表
2.6可知，它大于α=0.05时的F检验临界值5.143，因此拒绝“所有算法性能相同“这个假设.然后使用Nemenyi后续检验，在表2.7中找到k=3时根据式(2.36)计算出临界值域CD=1.657，由表2.5中的平均序值可知，算法A与B的差距，以及算法B与℃的差距均未超过临界值域，而算法A与C的差距超过临界值域，因此检验结果认为算法A与C的性能显著不同，而算法A与B、以及算法B与C的性能没有显著差别，上述检验比较可以直观地用Friedman检验图显示.例如根据表2.5的序值结果可绘制出图2.8，图中纵轴显示各个算法，横轴是平均序值.对每个算法，用一个圆点显示其平均序值，以圆点为中心的横线段表示临界值域的大小.然后就可从图中观察，若两个算法的横线段有交叠，则说明这两个算法没有显著差别，否则即说明有显著差别.从图2.8中可容易地看出，算法A与B没有显著差别，因为它们的横线段有交叠区域，而算法A显著优于算法C，因为它们的横线段没有交叠区域
偏差与方差
除了估算学习算法的泛化性能，大家通常希望理解为什么学习算法有这样的性能。偏差-方差分解（bias-variance decomposition）是解释学习算法泛化性能的重要工具。
对于不同的训练集学习输出通常是不一样的，尽管训练样本取自相同的分布。设x为训练样本，yD为x在数据集中的标记，y为x的真值标记，f(x;D)是训练集D上学得模型f在x上的预测输出。以回归问题为例，学习算法的期望预测为
$\overline f(x)$：这是模型f对输入x的期望预测。这里的“期望”是指统计学意义上的平均值，即如果我们从相同的数据分布中抽取多个数据集D，并在每个数据集上训练模型f，然后对输入x进行预测，$\overline f(x)$就是这些预测值的平均。
yD就是给定D之后，y的预期输出结果
在数学和统计学中，ED表示的是关于数据集 D的期望值（Expectation）。这里的ED 具体指的是在所有可能的数据集 D上取平均，这些数据集都来自同一个数据生成分布。
在机器学习上下文中，这意味着如果你有无限次机会从相同的分布中抽样得到不同的数据集 D，那么 ED 就是基于所有这些可能的数据集计算出的某个量的平均值。在这个场景下，$\mathbb{E}_{D}[f(x; D)]$就是基于所有可能数据集 D 上训练出的模型 f 对于输入 x 的预测结果的平均。
$$ \overline f(x) = \mathbb{E}_{D}[f(x; D)].（公式2.37） $$
使用不同的样本，样本数量相同的训练集的方差为
var一般表示方差
$$ var(x)=\mathbb E[(f(x;D)-\overline f(x))^2]（公式2.38） $$
噪声为
噪声指的是观察到的目标变量yD与真实（无噪声）目标y之间的差异
$$ ε^2=\mathbb E_D[(y_D-y)^2]（公式2.39） $$
期望输出和真实标签之间的差异称为偏差，即
$$ bias^2(x)=(\overline f(x)-y)^2 （公式2.40） $$
为了便于讨论，我们假设噪声的期望为0，即$\mathbb E_D[(y_D-y)]=0$
通过展开和组合多项式，我们可以将期望泛化误差分解为
$$ E(f; D) = \mathbb{E}_D\left[(f(x; D) - y_D)^2\right]\\ = \mathbb{E}_D\left[\left(f(x; D) - \bar{f}(x) + \bar{f}(x) - y_D\right)^2\right]\\ = \mathbb{E}_D\left[\left(f(x; D) - \bar{f}(x)\right)^2\right] + \mathbb{E}_D\left[\left(\bar{f}(x) - y_D\right)^2\right]\\ + \mathbb{E}_D[2\left(f(x; D) - \bar{f}(x)\right)\left(\bar{f}(x) - y_D\right)]\\ = \mathbb{E}_D\left[\left(f(x; D) - \bar{f}(x)\right)^2\right] + \mathbb{E}_D\left[\left(\bar{f}(x) - y_D\right)^2\right]\\ = \mathbb{E}_D\left[\left(f(x; D) - \bar{f}(x)\right)^2\right] + \mathbb{E}_D\left[\left(\bar{f}(x) - y + y - y_D\right)^2\right]\\ = \mathbb{E}_D\left[\left(f(x; D) - \bar{f}(x)\right)^2\right] + \mathbb{E}_D\left[\left(\bar{f}(x) - y\right)^2\right]\\ + \mathbb{E}_D[ (y - y_D)^2 ] + 2\mathbb{E}_D\left[\left(\bar{f}(x) - y\right)(y - y_D)\right]\\ = \mathbb{E}_D\left[\left(f(x; D) - \bar{f}(x)\right)^2\right] + (\bar{f}(x) - y)^2 + \mathbb{E}_D[(y_D - y)^2].（公式2.41） $$
即
- 偏差（Bias）： 偏差是指模型预测值的期望与真实值之间的差异。高偏差意味着模型在训练数据上的表现就不好，它可能过于简单，不能捕捉数据中的复杂模式，这种情况通常被称为欠拟合（Underfitting）。偏差反映了模型的灵活性和能力，偏差越低，模型越能精确地逼近真实函数。
- 方差（Variance）： 方差描述了模型预测结果在不同数据集上的变化程度。高方差意味着模型对训练数据的微小变化非常敏感，这可能导致在训练集上表现很好，但在新的数据上表现不佳，这种情况通常被称为过拟合（Overfitting）。方差体现了模型的稳定性，方差越低，模型对新数据的预测就越稳定。
简而言之，统计学中的方差是用来度量数据的离散程度，而机器学习中的方差是用来度量模型预测的不稳定性，特别是在面对数据集的轻微变化时模型表现的差异性。机器学习的方差关注的是模型的泛化能力，而非单一数据集内部的数值分布。- 噪声（Noise）： 噪声是指数据中固有的随机性或不确定性，这是模型无法控制的。即使最完美的模型也无法降低这部分误差，因为噪声来源于数据采集过程中的随机误差或其他不可预测的因素。噪声限制了模型能够达到的最佳性能。
这个公式表明，减少泛化误差需要同时降低偏差和方差
$$ E(f;D)=bias^2(x)+var(x)+ε^2（公式2.42） $$
这意味着泛化误差可以分解为，偏差 方差和噪声
偏差衡量的是学习算法的预期预测与真实值标签之间的差异，即表示学习算法的拟合能力。方差衡量的是由于同等大小训练集的变化，引起的学习性能的变化，即数据变动对于学习结果的影响。噪声代表了泛化误差的下限，可以通过任何给定的学习器来实现，也就是学习问题的固有难度。偏差-方差充分说明，泛化性能由学习算法的能力，数据准确性和问题的固有难度共同决定。为了实验较好的泛化性，充分拟合数据需要一个极小的偏差，方差同样需要保持在最小以最小化数据变化带来的影响。
- 偏差指的是模型预测的期望值与真实值之间的差异。高偏差意味着模型过于简化，没有很好地捕捉数据的复杂性，这通常称为欠拟合（underfitting）。
- 方差衡量的是模型预测结果在不同训练数据集上的变化程度。高方差意味着模型对训练数据过于敏感，可能学习到了训练数据中的噪声，这通常称为过拟合（overfitting）。
个人觉得着学习的过程一般是从欠拟合到过拟合的过程，所以才有了下文描述
一般来说，偏差和方差彼此之间是冲突的，这称为偏差-方差窘境（ bias-variance dilemma.）如图2.9所示
对于一个问题和一个学习器，假设我们可以控制训练程度。如果我们限制训练程度，使得学习者训练不足，它的拟合能力会受限，因此学习器上的数据扰动产生的影响有限，所以，偏差主导着泛化误差。随着训练的进行，学习器的泛化性能提高了，因此学习者开始学习数据扰动，所以，方差开始主导的泛化误差。在大量的训练后，学习器的拟合能力变得非常强了，也因此训练集轻量的扰动将会导致学习器显著的变化。这时候，学习器可能会开始学习训练数据的特征，因此过拟合发生了