第一章 绪论
1.独立同分布
通常 假设 样本空间 中 全 体样 本 服 从 一 个 未 知 “ 分 布 ” ( d i s t r i b u t i o n ) D , 我们获得的每个样本都是独立地从这个分布上采样获得的， 即 “ 独 立同 分布 ” ( i n d e p e n d e n t a n d i d e n t ic a lly di s t r i b u t e d , 简 称 i . i . d . ) . 一 般 而 言 ， 训 练样 本越 多 ， 我 们 得 到 的 关 于 D 的 信息 越多，这样就越有可能通过学习获得具有强泛化能力的模型.
2.假设空间
我们可以把学习过程看作一个在所有假设(hypothesis)组成的空间中进行 搜索的过程，搜索目标是找到与训练集“匹配”(ft)的假设， 即 能够 将 训 练集 中 的瓜 判 断 正确的 假 设 . 假 设 的 表 示一旦确定 ， 假 设 空 间及 其规模 大 小 就 确 定 了 . 这里我们的 假 设 空间由形如 “ ( 色 泽= ? ) A ( 根蒂= ?) A ( 敲 声= ? ) ” 的 可 能 取 值 所形成 的 假 设 组 成 .
3.归纳偏好
对于一个具体的学习算法而言，它必须要产生一个模型.这时，学习算 法本身的“偏好”就会起到关键的作用.例如，若我们的算法喜欢“尽可能特 殊”的模型，则它会选择“好瓜→(色泽=*)^(根蒂=蜷缩)A(敲声=浊响)”; 但若我们的算法喜欢“尽可能一般”的模型，并且由于某种原因它更“相信” 根蒂，则它会选择“好瓜→(色泽=*)^(根蒂=蜷缩)A(敲声=*)”.机器学习 算法在学习过程中 对某种类型 假设的偏 好，称为 “归纳偏好 ”( inductive bias), 或简称为“偏好”
"奥卡姆剃刀”(Occam's razor)是一种常用的、自然科学研究中最基本的原则，即“若有多个假设与观察一致，则选最简单的那个”.如果采用这个原则，并且假设我们认为“更平滑”意味着“更简单”(例如曲线A更易于描述，其方程式是y=-x²+6x+1,而曲线B则要复杂得多),则在图1.3中我们会自然地偏好“平滑”的曲线A.
4.NFL定理
公式推导：
假设样本空 间X和假设 空间都 是离散 的.令P(h|X,
) 代表算法 基于训练数据X产生假设h的概率，再令f代表我们希望学习的 真实目标函数. 的“训练集外误差”,即 在训练集之外的所有样本上的 误差 为
这个公式说明，在所有假设的情况下，误差与算法无关。所以，NFL定理最重要的寓意，是让我们清楚地认识到，脱离具体问题，空泛地谈论“什么学习算法更好”毫无意义，因为若考虑所有潜在的问题，则所有学习算法都一样好.要谈论算法的相对优劣，必须要针对具体的学习问题；在某些问题上表现好的学习算法，在另一些问题上却可能不尽如人意，学习算法自身的归纳偏好与问题是否相配，往往会起到决定性的作用.
第二章 模型评估与选择
1.训练集与测试集的划分
（1）留出法
“留出法”(hold-out)直接将数据集D划分为两个互斥的集合，其中一个 集合作为训练集S,另一个作为测试集T
（2）交叉验证法
“交叉验证法”(cross validation)先将数据集D划分为k个大小相似的互斥子集，每个子集都
尽可能保持数据分布的一致性，即从D中通过分层采样得到.然后，每次用 k-1个子集的并集作为训练集，余下的那个子集作为测试集；重复k次， 最终返回的是这k个测试结果 的均值.
（3）自助法
给定包含m个样本的数据集D,我们对它进行采样产生数据集D':每次随机从D中挑选一个
样本，将其拷贝放入D',然后再将该样本放回初始数据集D中，使得该样本在下次采样时仍有可能被采到；这个过程重复执行m次后，我们就得到了包含m个样本的数据集D',这就是自助采样的结果.显然，D中有一部分样本会在D'中多次出现，而另一部分样本不出现.样本在m次采样中始终不被采到的概率是：
即通过自助采样，初始数据集D中约有36.8%的样本未出现在采样数据集D'中.于是我们可将D'用作训练集，D\D′用作测试集；这样，实际评估的模型与期望评估的模型都使用m个训练样本，而我们仍有数据总量约1/3的、没在训练集中出现的样本用于测试.这样的测试结果，亦称“包外估计”(out-of-bag est i m a t e ) .
自助法在数据集较小、难以有效划分训练/测试集时很有用
2.模型估计与选择
模型评估与选择中用于评估测试的数据集常称为“验证集”(validation set).
3.性能度量
（1）错误率与准确度
（2）查准率、查全率与F1
错误率衡 量了有多少比例的瓜被判别错误.但是若我们关心的是“挑出的西瓜中有多少
比例是好瓜”,或者“所 有好瓜中有多 少比例被挑 了出来”,那么错误率显然 就不够用了，这时需要使用其他的性能度量.
PR曲线
F1度量（调和均值）
F1度量的一般形式
,能让我们表达出对查准率/查全率的不同偏 好， 它 定义为
很多时 候我 们 有 多 个 二 分 类 混 淆矩 阵 ， 例 如进行 多 次训练 / 测 试 ， 每 次得 到 一个混淆矩 阵； 或 是 在 多个 数 据集 上 进 行 训 练/ 测 试 ，希 望 估 计 算法 的 “ 全 局 ” 性能 ；
一种 直接 的做 法是 先在 各混 淆矩 阵上分 别计 算出 查 准率 和查 全 率，再计算平均值
还可先将各混淆矩阵的对应元素进行平均：
（3）ROC与AUC
很多学习器是为测试样本产生一个实 值或概率预 测，然后将这个预测值与 一个 分 类 阈值 ( t hr es h o ld ) 进 行 比 较 ， 若 大 于 阈 值 则 分 为 正 类 ， 否 则 为 反 类 .
在不 同 的应用 任务中 ， 我们 可 根 据 任务 需 求 来 采 用不同的 截 断点 ， 例 如 若 我们更重 视 “ 查准 率 ” , 则 可 选 择 排序 中 靠 前 的 位 置 进 行 截断 ； 若 更 重 视 “ 查 全率”,则可选择靠后的位置进行截断.
ROC曲线的纵轴是“真正 例率”(True Positive Rat e,简称TPR ),横轴是“ 假正例 率”(False Positive
Rate,简称FPR)：
AUC可通过对ROC曲线下各部分的面积求和而得.
4.代价敏感错误率与代价曲线
不同类型的错误所造成的后果不同. 例如在医疗诊断中，错误地把患者诊断 为健康人与错 误地把健康人诊断为患者， 看起来都是犯了“一次错误”,但后者的影响是增加 了进一步检查的麻烦，前
者的后果却可能是丧失了拯救生命的最佳时机； 为权衡不同类型错误所造成的不同损失，可为错误赋予“非均等代价”(unequal cost).
则“代价敏感”(cost-sensitive)错误率为：
在非均等代价下，ROC曲线不能直接反映出学习器的期望总体代价，而 “代价曲线”(cost curve)则可达到该目的.代价曲线图的横轴是取值为[0,1] 的正例概率代价： 
其中p是样例为正例的概率；纵轴是取值为[0,1]的归一化代价
其中FPR是式(2.19)定义的假正例率，FNR=1-TPR是假反例率.代价曲线的绘制很简单：ROC曲线上每一点对应了代价平面上的一条线段，设ROC曲线上点的坐标为(TPR,FPR),则可相应计算出FNR,然后在代价平面上绘制一条从(0,FPR)到(1,FNR)的线段，线段下的面积即表示了该条件下的期望总体代价；如此将ROC曲线上的每个点转化为代价平面上的一条线段，然后取所有线段的下界，围成的面积即为在所有条件下学习器的期望总体代价，如图2.5所示.
4.比较检验
机器学习中性能比较这件事要比大家想象的复杂得多.这里面涉及几个重要因素：首先，我们希望比较的是泛化性能，然而通过实验评估方法我们获得的是测试集上的性能，两者的对比结果可能未必相同；第二，测试集上的性能与测试集本身的选择有很大关系，且不论使用不同大小的测试集会得到不同的结果，即便用相同大小的测试集，若包含的测试样例不同，测试结果也会有不同；第三，很多机器学习算法本身有一定的随机性，即便用相同的参数设置在同一个测试集上多次运行，其结果也会有不同.
统计假设检验(hypothesis test)为我们进行学习器性能比较提供了重要依据.
（1）假设检验
接下来查表，若t>临界值，落入拒绝域内，则拒绝原假设，否则接受原假设。认为测试错误率与泛化错误率相等。
（2）交叉验证t检验
交叉验证t检验是使用的配对样本的t检验，假设学习器A,B测试错误率相等。
（3）McNemar检验
（4）Friedman检验 与 Nemenyi后续检验
McNemar检验：
五.偏差与方差
首先，引入学习算法的期望预测：
偏差(2.40)度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力；
方差(2.38)度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响；
噪声(2.39)则表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度.
偏差-方差分解说明，泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的.给定学习任务，为了取得好的泛化性能，则需使偏差较小，即能够充分拟合数据，并且使方差较小，即使得数据扰动产生的影响小.
一般来说，偏差与方差是有冲突的，这称为偏差-方差窘境(bias-variancedilemma).图2.9给出了一个示意图.给定学习任务，假定我们能控制学习算法的训练程度，则在训练不足时，学习器的拟合能力不够强，训练数据的扰动不足以使学习器产生显著变化，此时偏差主导了泛化错误率；随着训练程度的加深，学习器的拟合能力逐渐增强，训练数据发生的扰动渐渐能被学习器学到，方差逐渐主导了泛化错误率；在训练程度充足后，学习器的拟合能力已非常强，训练数据发生的轻微扰动都会导致学习器发生显著变化，若训练数据自身的、非全局的特性被学习器学到了，则将发生过拟合.
