第1章 绪论
1.1 训练集外误差
对于算法，它的训练集外误差，即
在训练集之外的所有样本上的误差为：
其中为对假设的求和。同一算法对于训练集外（测试集）的不同数据产生的不同的假设，每个假设有不同的概率。
其中我们假设样本空间和假设空间
均为离散的，
为】代表算法基于训练数据
产生假设
的概率，
代表我们希望学习的真实目标函数。
需要说明的是，为指示函数，若
为真则取值1，否则取值0。
部分公式及原理解释：
，即训练集外误差；
：即样本空间中训练集外的数据；
1.2 NFL定理
对训练集外误差公式继续推导：
考虑二分类问题（即通俗意义上的“是否”、“有无”问题）。我们想要求得的真实目标函数往往不止一个，因为满足版本空间中的假设的函数都可以是真实目标函数。
对于同一个样本的这个预测值，对于样本空间中的某个样本x，如果
, 那么这就是两个不同的真实目标函数。
所以对于某个样本可以区分出两个真实目标函数，一共有个样本，所以一共有
个真实目标函数。
这些真实目标函数是等可能分布的(均匀分布)，所以对于某个假设h(x)，如果h(x)=0那么就有1/2的概率与真实目标函数相等。
故我们对所有可能的按均匀分布对误差求和：
注意到
故
从式子中可以得到，总误差与学习算法无关。故对于任意两个学习算法，我们都有：
也就可得到NFL定理(No Free Lunch Theorem)，大致内容如下：
在所有“问题”出现的机会相同、或所有问题同等重要的前提下，对所有可能的目标函数求平均，得到的所有学习算法的“非训练集误差”的期望值相同。
第2章 模型评估与选择
2.1评估方法
①留出法：直接将数据集划分为两个互斥的集合，其中一个集合作为训练集
,另一个作为测试集
，即
。
单次使用留出法得到的估计结果往往不够稳定可靠。使用留出法时，一般要采用若干次随机划分、重复进行试验评估后取平均值作为留出法的评估结果。
缺点：若S包括绝大多数样本，则训练出的模型可能更接近于用D训练出的模型。但由于T较小，评估结果不够稳定准确；若T多包含一些样本，则S与D的差别更大了，被评估的模型与用D训练出的模型相比可能有较大差别，从而降低了评估结果的保真性(fidelity)
常见做法是将的样本用于训练，其余用于测试。
②交叉验证法（又称"k折交叉验证"(k-fold cross validation)）：先将数据集划分为
个大小相似的互斥子集，每个子集
都尽可能保持数据分布的一致性，即从
中通过分层采样得到。然后每次用
个子集的并集作为训练集，余下的那个子集作为测试集；这样就可获得
组训练/测试集，从而可进行
次训练和测试。最终返回这
个人测试结果的均值。
若令k=m，可得到特例：留一法（Leave-One-Out,LOO）
因为m个样本只有唯一的方式划分为m个子集——每个子集包含一个样本，故留一法不受随机样本划分方式的影响。
留一法使用的训练集与初始数据集相比只少了一个样本，被实际评估的模型往往被认为比较准确。
缺点：在未考虑算法调参的情况下，计算开销就已经非常大；留一法的估计结果未必永远准确；NFL定理适用于该方法
③自助法：给定包含m个样本的数据集D，我们对它进行采样产生数据集D'：每次随机从D中挑选1个样本，将其拷贝放入D'，然后再将该样本放回初始数据集D中，使得该样本在下次采样时仍有可能被采到。
此过程重复执行m次，即可得到包含m个样本的数据集D'。
显然，D中一部分样本不会在D'中出现。简单估计下，样本在m次采样后始终不被猜到的概率是
即通过自助采样，初始数据集D中约有36.8%的样本未出现在采样数据集D'中。
故我们可将D'作为训练集，D\D'用做测试集。
自助法在数据集较小、难以有效划分训练/测试集时很有用。
2.2 性能衡量
1）回归任务常用性能度量：均方误差
更一般的，对于数据分布D和概率密度函数，均方误差为:
2）分类任务常用性能度量：错误率、精度
错误率：
精度：
更一般的，对于数据分布D和概率密度函数
错误率：
精度：
3)更泛用的性能度量：查准率和查全率
TP(真正例):真实情况正例，预测结果正例
FN(假反例):真实情况正例，预测结果反例
FP(假正例):真实情况反例，预测结果正例
TN(真反例):真实情况反例，预测结果反例
查准率
查全率
以P为纵轴，R为横轴作图，就得到“P-R”曲线。
平衡点(BEP)：P=R时的取值。基于BEP的比较，可比较学习器的优劣。
F1度量（优于BEP）：基于查准率与查全率的调和平均
F1度量的一般形式:加权调和平均
，其中
度量了查全率对查准率的相对重要性。
时退化为标准的F1，
时查全率有更大影响，
时查准率有更大影响。
宏查准率
宏查全率
宏F1
