积跬步以致千里,积怠惰以致深渊
注：本篇文章在整理时主要参考了 周志华 的《机器学习》。
主要内容
在上一篇文章中，我们知道要根据具体的问题选择具体的算法和归纳偏好。那么我们怎么判定我们的选择是正确的呢？这就需要拥有一套规范的模型评估与选择方法论了。
经验误差与过拟合
首先，我们要理解机器学习为什么需要一套模型评估与选择方法论？
在前一章的学习中，我们知道机器学习是对数据集的泛化过程，即从输入的数据中归纳出一套能适用于所有潜在样本的“普遍规律”。可因为训练数据不够充分，机器学习出来的模型并没办法涵盖所有的情况，这就会导致学习器的实际预测输出与样本的真实输出之间存在“误差”。
学习器在训练集上的误差称为“经验误差”，在新样本上的误差称为“泛化误差”。把分类错误的样本数占样本总数的比例称为“错误率” (error rate) ；相应的，1-“错误率”称为“精度”。很明显，要使得分类器尽可能的有用，我们应该要让泛化误差尽可能的小。可惜在现实环境中，我们很难知道新样本是什么样的，所以我们实际能做的只有努力使经验误差最小化。
说到这里，也许有的心急的同学已经迫不及待的去将算法设计的尽可能百分百的满足所有训练样本了，把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质，可却忘了学习器真正要达到的是泛化误差尽可能小，而不是目前的折中方案降低经验误差。而在降低经验误差的道路上，驻守着机器学习领域最大的拦路虎之一：“过拟合”
“过拟合”是指学习器对训练样本学的太好了，导致泛化程度不够（还记得机器学习就是一个泛化过程吗），没法适应新的数据样本。与之相反的还有一个“欠拟合”的概念，就是对训练样本中的一般规律都没学习好。举个例子，让机器来学习天鹅的特征，经过训练后，学习了天鹅是有翅膀的，天鹅的嘴巴是长长的弯曲的，天鹅的脖子是长长的有点曲度，天鹅的整个体型像一个“2”且略大于鸭子。这时候你的机器已经基本能区别天鹅和其他动物了。然而，很不巧你的训练天鹅数据全是白色的，于是机器经过学习后，会认为天鹅的羽毛都是白的，以后看到羽毛是黑的天鹅就会认为那不是天鹅，那就是过拟合；而如果没能学习到天鹅的基本特征，那就是欠拟合了。
图1. 不能够很好的反映数据样本的“普遍规律” (欠拟合) 图3. 太过于纠结训练数据的分布，从而无法很好的适应新的数据样本 (过拟合) 。
所以，我们知道了吧，我们为什么需要一套模型评估与选择的方法论呢？因为我们的训练数据没法真正代表真实的样本空间，而泛化误差无法直接获得，经验误差又因为过拟合的存在而不适合作为标准，所以我们才需要一套模型评估与选择的方法论。
评估方法
我们知道了为什么要对模型进行评估，那么在不知道泛化误差的情况下，我们该如何进行评估呢？
一个常用的思路是：既然我们没法拿到新样本来进行泛化误差计算，那么我们可以从训练样本中取出一部分来，假装它是一组新样本，并用这些样本计算出来的误差作为泛化误差的近似。这组选出来的样本被称为“测试集”，测试集上的误差被称为测试误差。但需注意的是，测试集应该尽量不与训练集重合，否则测试集计算出的误差将没法准确代表该学习器的泛化能力。
为了理解这一点，不妨考虑这样一个场景：老师出了10道习题供同学们练习，考试时又用同样的10道题作为试题，这个考试成绩能否反映出同学们写的好不好呢？答案是否定的，可能有的同学只会做这10道题却能得高分。
综上所述，我们运用一下几种常见的做法把一个包含m个样例的数据集D进行适当的处理，从中产生出训练集S和测试集T。
1、留出法（hold-out）
直接将D划分为互斥的两部分S和T，在S上训练出模型后，用T来评估测试误差。
需要注意的是：应避免因数据划分过程引入额外的偏差而对最终结果产生影响，例如通过对D进行分层采样 (保留类别比例的采样方式) 而获得含70%样本的训练集S和含30%样本的训练集T，若D包含500个正例子、500个反例，则分层采样得到的S应包含350个正例、350个反例。而T则包含150个正例和150个反例；若S、T中样本类别比例差别很大，则误差估计将由于训练／测试数据分布的差异而产生偏差。另外，同样可以把D中的样本排序，然后把前350个正例放到训练集中，也可以把后350个正例放到训练集中，......
不同的划分方案将导致不同的训练／测试集，相应的模型评估也会有所差异。因此，一般采用若干次随机划分、重复进行实验评估后取平均值作为留出法的评估结果。
特点：测试集小时，评估结果的方差较大，被评估的模型与用D训练出的模型相比可能有较大区别，从而降低了评估结果的保真性；训练集小时，评估结果的偏差较大，评估结果可能不够稳定准确。
2、交叉验证法（cross validation）
将D分层采样划分为互斥的k个子集，每次训练用其中(k-1)个数据子集，用剩下的一个子集作为测试集。这样就能获得k组训练/测试集，对这k组分别进行训练和测试，最终返回k个测试结果的均值。
特点：评估结果的稳定性和保真性在很大程度上取决于k的取值 (k折交叉验证)
3、留一法 (Leave-One-Out)
交叉验证法的一个特例：假定数据集D中包含m个样本，令k=m。
特点：不受随机样本划分方式的影响；评估结果往往被认为比较准确；训练m个模型的计算开销比较大。
4、自助法（bootstrapping）
每次从D中随机复制一个样本到D1中，重复m次，会得到一个拥有m个数据样本的D1数据集 (自主采样法：可重复采样或又放回采样) 。显然，D中的一部分数据会多次出现在D1中，而另一部分样本不出现。根据平均分布概率计算，初始数据集D中约有36.8%的样本未出现在采样数据集D1中。我们将D1用作训练集，D\D1用作测试集 (“\”表示集合减法) 。
5、适用性
自助法在数据集较小、难以有效划分训练／测试集时很有用；此外，自助法能从初始数据集中产生多个不同的训练集，这对集成学习等方法有很大的好处。然而，自助法产生的数据集改变了初始数据集的分布，这会引入估计偏差。因此，在初始数据量足够时，留出法和交叉验证法更常用一些。
6、调参
参数配置不同，学得模型的性能往往有着显著差别。需注意的是，在研究对比不同算法的泛化性能时，我们用测试集上的判别效果来估计模型在实际使用时的泛化能力，而把训练数据另外划分为训练集和验证集，基于验证集上的性能来进行模型选择和调参。
（数据集 （训练数据（训练集）（验证集）） （测试集））
性能度量（performance measure）
了解了如何有效可行地实验评估方法，还需要有衡量模型泛化能力的评价标准，这就是性能度量。这意味着模型的“好坏”是相对的，什么样的模型是好的，不仅取决于算法和数据，还决定于任务需求。
回归任务中最常用的性能度量是“均方误差”，即用模型的输出与实际输出计算输出结果的方差。
1、错误率与精度
错误率：分类错误的样本数占样本总数的比例；
精度：分类正确的样本数占样本总数的比例；
2、查准率、查全率与F1
查准率（precision）：被模型预测为正的样本中，真正为正的样本比例（被预测为好瓜的西瓜中，真的是好瓜的西瓜比例）
查全率（recall）：在所有正的样本上，被学习器预测为正的样本比例（在所有好瓜中，被学习器正确识别的好瓜比例）
F1：（2x查准率x查全率）/（查准率＋查全率）。 F1是基于查准率和查全率的调和平均。
“平衡点”（Break-Even Point）：“查准率＝查全率”时的取值。
查准率和查全率是一对矛盾的度量。一般来说，查准率高时，查全率往往偏低；而查全率高时，查准率往往偏低。例如，若希望将好瓜尽可能多地选出来，则可通过增加选瓜的数量来实现，如果将所有西瓜都选上，那么所有的好瓜也必然都被选上了，但这样查准率就会较低；若希望选出的瓜中好瓜比例尽可能高，则可只挑选最有把握的瓜，但这样就难免会漏掉不少好瓜，使得查全率较低。通常只有在一些简单任务中，才可能使查全率和查准率都很高。
以查准率为纵轴、查全率为横轴作图，就得到了查准率－查全率曲线，简称“P-R曲线”。
在进行比较时，若一个学习器的P-R曲线被另一个学习器的曲线完全“包住”，则可断言后者的性能优于前者。当曲线有相交时，很难断言两者的优劣。真要判别时，“平衡点”（Break-Even Point）是一个不错的度量方法。
3、ROC与AUC
ROC曲线是从“一般情况下”泛化性能的好坏出发来研究学习器泛化性能的有力工具。ROC：“受试者工作特征”（receiver operating characteristic）曲线，与P-R 曲线类似，只不过取用“真正利率”（TPR ）作为纵轴，“假正例率”（FPR）作为横轴。
对角线对应于“随机猜测”模型，而点(0,1)则对应于将所有正例排在所有反例之前的“理想模型”。
进行学习器的比较时，与P-R图相似，若一个学习器的ROC曲线被另一个学习器的曲线完全“包住”，则可断言后者的性能优于前者；若两个学习器的ROC曲线发生交叉，则难以一般性地断言两者孰优孰劣。此时如果一定要进行比较，则较为合理的判据是比较ROC曲线下的面积，即AUC (Area Under ROC Curve)。
4、代价敏感错误率与代价曲线
在现实生活中，不同类型的错误所造成的后果不同。例如在医疗诊断中，错误地把患者诊断为健康人与错误地把健康人诊断为患者，看起来都是犯了“一次错误”，但后者的影响是增加了进一步检查的麻烦，前者的后果却可能是丧失了拯救生命的最佳时机。因此，为权衡不同类型错误所造成的不同损失，可为错误赋予“非均等代价” (unequal cost)。代价敏感错误率代表数据的平均总体代价。
在均等代价下，错误率是直接计算“错误次数”，并没有考虑不同错误会造成不同的后果。在非均等代价下，我们所希望的不再是简单地最小化错误次数，而是希望最小化“总体代价” (total cost)。
比较检验
有了实验评估方法和性能度量，表面上看就能对学习器的性能进行评估比较了。但怎么来做“比较”呢？
这里面涉及几个重要因素：
第一，我们希望比较的是泛化性能，然而通过实验评估方法我们获得的是测试集上的性能，两者的对比结果可能未必相同；
第二，测试集上的性能与测试集本身的选择有很大的关系，且不论使用不同大小的测试集会得到不同的结果，即便用相同大小的数据集，若包含的测试样例不同，测试结果也会有所不同；
第三，很多机器学习算法本身有一定的随机性，即便用相同的参数设置在同一个测试集上多次运行，其结果也会有所不同。
为了解决这些问题，统计假设检验（hypothesis test）为我们提供了重要的依据。
假设检验中的“假设”是对学习器泛化错误率分布的某种猜想或判断，然后通过假设的验证结果来对不同的学习器或模型的性能进行判断。泛化错误率与测试错误率在直观上比较接近，因此，可根据测试错误率估推出泛化错误率的分布。
给定测试错误率，则求解样本误分类概率公式的偏导可知，错误率符合二项（binomial）分布。
如图所示，若 错误率=0.3，则10个样本中测得3个被误分类的概率最大。
［1］设定一个假设，比如“一个机器学习真正的泛化错误率不大于0.3”
［2］设定一个置信概率“显著度a”，a的一般取值为0.05、0.1；a代表的意思是当我们的假设成立的概率在（1-a，1］的范围内时，我们认为是成立的。
［3］计算使假设在置信范围内成立的最大值是多少，比如根据上边［1］中的假设，要使泛化错误率不大于0.3成立，即泛化错误率小于0.3的概率大于（1-a）。要计算这个，我们要算出要使错误率大于0.3的概率之和小于a时的最大泛化错误率是多少。
［4］比较计算出的满足假设的最大值和我们实际计算出的值，如果我们实际计算出来的错误率已经大于最大可能的错误率了，说明假设不成立。
［5］在这里的假设中，假设不成立说明我们的学习器错误率要大于0.3啊，这是个很烂的学习器，我们还需要继续调优。
在实际实验时，我们会多次使用留出法或交叉验证法进行多次训练/测试，那么我们实际上会得到多个测试错误率（这里假设为k个）。我们可以通过求这些错误率的平均和方差来将假设检验转换为自由度为k-1的 t 分布。通过查询 t 检验常用临界表可以很方便的计算出假设是否成立。
偏差与方差
对学习算法除了通过实验估计其泛化性能，我们还需要理解“为什么”具有这样的性能，“偏差与方差分解”（bias-variance decomposition）是解释学习算法泛化性能的一种重要工具。
泛化误差可分解为偏差、方差和噪音之和。
偏差度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力；方差度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响；噪声则表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度。
偏差－方差分解说明，泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的。
一般来说，偏差与方差是有冲突的。给定学习任务，假定我们能控制学习算法的训练程度，则在训练不足时，学习器的拟合能力不够强，训练数据的扰动不足以使学习器产生显著变化，此时偏差主导了泛化错误率；随着训练程度的加深，学习器的拟合能力逐渐增强，训练数据的扰动渐渐能被学习器学到，方差逐渐主导了泛化错误率；在训练程度充足后，学习器的拟合能力已非常强，训练数据发生的轻微的扰动都会导致学习器发生显著变化，若训练数据自身的、非全局的特性被学习器学到了，则将发生过拟合。
总结
泛化误差无法获得，经验误差因为过拟合的存在而不适合作为标准，导致我们需要专门的模型评估方法来测量学习器的效果
专门的模型评估方法是通过从数据集中选取一部分数据作为测试集来对训练出的模型进行验证，以测试误差来近似泛化误差实现的
测试误差体现在具体的性能度量指标上，我们要根据具体情况选择对应的指标
假设检验是我们对学习器性能进行比较的有效方法
泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的
（额外阅读）数据比算法要更重要的一个例子：对一批数据使用高明的算法，比不上用普通算法但是引入一部分外部数据源的效果要好（ http://anand.typepad.com/datawocky/2008/03/more-data-usual.html ）
具体的章节思路请参考下图理解：
