第一章 绪论

1.1 引言

通过买西瓜的例子引入。机器学习致力于研究如何通过计算的手段，利用经验来改善系统自身的性能。 
机器学习形式化的定义：假设用P来评估计算机程序在某任务类T上的性能，若一个程序通过利用经验E在T中任务上获得了性能改善，则我们就说关于T和P，该程序对E进行了学习。

1.2 基本术语

数据集中的每条记录是一个示例或样本。 
反映事件或对象在某方面的表现或性质的事项，成为属性或特征。 
属性上的取值，成为属性值。 
属性张成的空间，成为属性空间、样本空间或输入空间。 
由于属性空间中所得每个点对应一个坐标向量，因此也把一个示例称为一个特征向量。 
所有标记的集合称为标记空间、输出空间。

有监督： 
若预测离散值，此类学习任务称为分类（分为二分类和多分类）； 
若预测连续值，此类学习任务称为回归。 
无监督： 
聚类

学的模型适用于新样本的能力，称为泛化能力。 
样本获得：独立同分布。

1.3 假设空间

机器学习可以理解为归纳学习。但是归纳学习中的概念学习太难，目前大多是产生‘黑箱’模型。 
学习过程可以看做一个在所有假设组成的空间中进行搜索的过程，最终得到与训练集一致（即对所有训练样本能够进行正确判断）的假设。

可能有多个假设与训练集一致，即存在着一个与训练集一致的‘假设集合’，我们称之为‘版本空间’。

1.4 归纳偏好

版本空间中的假设在面临新样本时可能会有不同的输出。 
机器学习算法在学习过程中对某种类型假设的偏好，称为‘归纳偏好’。 
任何有效的机器学习算法必有其偏好，否则无法产生确定的学习结果。 
归纳偏好可看做学习算法自身在一个可能很庞大的假设空间中对假设进行选择的启发式或‘价值观’。 
奥卡姆剃刀：若有多个假设与观察一直，则选最简单的那个。 
没有免费的午餐定理（NFL）：所有‘问题’出现的机会相同、或所有问题同等重要的情况下，无论什么算法期望性能一样。——脱离具体问题，空泛地谈论‘什么学习算法更好’毫无意义。

1.5 发展历程

机器学习是人工智能研究发展的必然产物。

二十世纪五十年代到七十年代初，人工智能研究处于‘推理期’，那时人们以为只要能赋予及其逻辑推理能力，机器就能具有智能。（e.g A.Newell和H. Simon的‘逻辑理论家’） 
二十世纪七十年代中期开始，人工智能研究进入了‘知识期’。大量专家系统问世。（e.g E.A. Feigenbaum）

1950年，图灵提到了机器学习的可能； 
二十世纪五十年代初，已有机器学习的相关研究；（e.g A. Samuel的跳棋程序） 
五十年代中后期，基于神经网络的‘连接主义’学习出现。 
在六七十年代，基于逻辑表示的‘符号主义’学习技术蓬勃发展。 
二十世纪八十年代是机器学习称为一个独立的学科领域，各种机器学习技术百花初绽的一个时期。‘从样例中学习’的一大主流是符号主义学习，其代表包括决策树和基于逻辑的学习。 
二十世纪九十年代中期之前，‘从样例中学习’的另一主流技术是基于神经网络的连接主义学习。 
二十世纪九十年代中期，‘统计学习’闪亮登场并迅速占据主流五代，代表性技术是支持向量机以及更一般的‘核方法’。 
二十一世纪初，连接主义学习卷土重来，掀起了以‘深度学习’为名的热潮。在处理语音、图像等复杂对象的应用中，深度学习技术取得了优越的性能。主要靠调参。

1.6 应用现状

在计算机科学的诸多分支学科领域中，机器学习已成为最重要的技术进步源泉之一。机器学习还为许多交叉学科提供了重要的技术支撑。 
机器学习提供数据分析能力，云计算提供数据处理能力，众包提供数据标记能力。 
数据挖掘&机器学习：数据库领域的研究为数据挖掘提供数据管理技术，而机器学习和统计学的研究为数据挖掘提供数据分析技术。

第 2 章 模型评估与选择

2.1 经验误差与过拟合

错误率&精度：在m个样本中有a个样本分类错误，则错误率为E=a/m，精度为1-a/m。 
误差：学习器的实际预测输出与样本的真是输出之间的差异。 
训练误差/经验误差：在训练器上的误差。 
过拟合（过配）： 
1. 定义：学习器把训练样本自身的一些特点当作了所有潜在样本都会具有的性质，这样就会导致泛化能力下降。 
2. 原因：学习能力过于强大，以至于把训练样本所包含的不太一般的特性都学到了。 
3. 特点：机器学习面临的关键障碍，难以克服，是无法避免的，只能尽量‘缓解’。 
对过拟合无法避免的理解：机器学习面临的问题通常是NP难甚至更难，而有效的学习算法必然是在多项式时间内运行完成，若可彻底避免过拟合，则通过经验误差最小化就能获得最优解，这就意味着我们构造性地证明了“P=NP”；因此，只要相信P≠NPP≠NP，过拟合就不可避免 
欠拟合（欠配）： 
1. 定义：指对训练样本的一般性质尚未学好。 
2. 原因：学习能力低下。 
3. 特点：容易克服，例如在决策树学习中扩展分之、在神经网格学习中增加训练轮数。

2.2 评估方法

使用测试集来测试学习期对新样本的判别能力，然后以‘测试误差’作为泛化误差的近似。注意测试集应该尽可能与训练集互斥。

2.2.1 留出法

“留出法”(hold-out)直接将数据集D划分为两个互斥的集合，其中一个集合作为训练集S，另一个作为测试集T，即D=S∪T,S∩T=∅D=S∪T,S∩T=∅。 
注意： 
1. 训练/测试集的划分要尽可能保持数据分布的一致性，避免因数据划分过程引入额外的偏差而对最终结果产生影响。 
2. 单次使用留出法得到的估计结果往往不够稳定可靠，一般要采用若干次随机划分、重复进行实验评估后取平均值作为留出法的评估结果。 
3. 将大约2/3~4/5的样本用于训练，剩余样本用于测试。——为保证训练所得模型接近于用D训练出的模型，且评估结果尽量稳定准确、真实。

2.2.2 交叉验证法

“交叉验证法”：先将数据集D划分为k个大小相似的互斥子集，即D=D1∪D2∪…∪Dk,Di∩Dj=∅(i≠j)D=D1∪D2∪…∪Dk,Di∩Dj=∅(i≠j). 每个自己DiDi都尽可能保持数据分布的一致性，即从D中通过分层采样得到，然后，每次用k-1个子集的并集作为训练集，余下的那个子集作为测试集；这样就可以获得k组训练/测试集，从而可进行k次训练和测试，最终返回的是这k个测试结果的均值。

‘留一法’ 
1. 交叉验证法的一个特例，假定数据集D中包含m个样本，令k=m，即为留一法。 
2. 不受随机样本划分方式的影响，且训练集只比原始数据集少一个样本，这就使得在绝大多数情况下，留一法中被实际评估的模型与期望评估的用D训练出的模型很相似，因此留一法的评估结果被认为比较准确。 
3. 缺陷：1. 数据集较大时，开销难以忍受。2. 未必永远比其他评估方法准确，‘没有免费的午餐’定理对实验评估方法同样适用。

2.2.3 自助法

“自助法”（bootstrapping）：可以减少训练样本规模不同造成的影响，同时还能比较高效地进行实验估计。 
介绍：以自助采样法为基础。给定包含m个样本的数据集D，我们对它进行采样产生数据集D′D′:每次随机从D中挑选一个样本，将其拷贝放入D′D′,然后再将该样本放回初始数据及D中，重复m次得到包含m个样本的数据集D′D′。 
操作：取样后约有1/3的样本未出现在D′D′中。于是我们可将D′D′用作训练集，D∖D′D∖D′用作测试集。 
适用范围：数据集较小、难以有效划分训练/测试集时很有用；此外，自助法能从初始数据集产生多个不同的训练集，这对集成学习等方法有很大好处。 
缺点：产生的数据改变了初试数据集的分布，会引入估计偏差。因此初始数据量足够，留出法和交叉验证法使用更多。

2.2.4 调参与最终模型

在模型评估与选择过程中需要流出一部分数据进行评估测试，事实上我们只是用了一部分数据训练模型。因此模型选择完成后，学习算法和参数配置已选定，此时应该用数据集D重新训练模型，使用所有m个样本，这才是我们最终提交给用户的模型。 
注意：通常把学的模型在实际使用中遇到的数据成为测试数据，为加以区分，模型评估与选择中用语评估测试的数据集常称为“验证集”。 
如：在研究对不不同算法的泛化性能时，我们用测试集上的判别效果来估计模型在实际使用时的泛化能力，而把训练数据另外划分为训练集和验证集，基于验证集上的性能来进行模型选择和调参。

2.3 性能度量

回归任务最常用的性能度量是“均方误差”。 
下面介绍分类任务中常用的性能度量。

2.3.1 错误率与精度

错误率：

E(f;D)=∫x∼D⨿(f(x)≠y)p(x)dxE(f;D)=∫x∼D⨿(f(x)≠y)p(x)dx

精度：

acc(f;D)=∫x∼D⨿(f(x)=y)p(x)dx=1−E(f;D)acc(f;D)=∫x∼D⨿(f(x)=y)p(x)dx=1−E(f;D)

 

2.3.2 查准率，查全率与F1

分类结果混淆矩阵 

真实情况正例反例预测结果正例TP(真正例)FP(假反例)反例FN(假反例)TN(真反例)真实情况预测结果正例反例正例TP(真正例)FN(假反例)反例FP(假反例)TN(真反例)

查准率P——真正例中真正例占所有预测正例的比率：

P=TPTP+FPP=TPTP+FP

查全率R——真正例中真正例占所有正例的比率：

R=TPTP+FNR=TPTP+FN

P-R图：以查准率为纵轴、查全率为横轴作图，得到查准率-查全率曲线。 
关于P-R图： 
1. 若一个学习器的P-R曲线被另一个学习器的曲线完全“包住”，则可断言后者的性能优于前者。 
2. 如果发生了交叉，可以在某一查准率或查全率的条件下进行比较，或者比较面积。 
3. 比较平衡点（BEP）——“查准率=查全率”时的取值 
4. BEP太过简单，常用F1

F1=2×P×RP+R=2×TP样例总数+TP−TNF1=2×P×RP+R=2×TP样例总数+TP−TN

5. F1的一般形式——FβFβ，能让我们表达出对查准率/查全率的不同偏好，他定义为

Fβ=(1+β2)×P×Rβ2×P+Rβ>0Fβ=(1+β2)×P×Rβ2×P+Rβ>0

β>1β>1时查全率有更大影响，β<1β<1时查准率有更大影响。注：F1是基于查准率和查全率的调和平均，与算术平均和几何平均相比更重视较小值 
6. 若希望在n个二分类混淆矩阵上综合考察查准率和查全率，有两种做法：1)、先在各混淆矩阵上分别计算出查准率和查全率，再计算平均值，得到“宏查准率(macro-P)”“宏查全率(macro-R)”并可计算得“宏F1”

macro-P=1n∑i=1nPi,macro-R=1n∑i=1nRi,macro-F1=2×macro-P×macro-Rmacro−P+macro−Rmacro-P=1n∑i=1nPi,macro-R=1n∑i=1nRi,macro-F1=2×macro-P×macro-Rmacro−P+macro−R

2)、先将各混淆矩阵的对应元素进行平均，得到TP、FP、TN、FN的平均值，然后基于这些平均值计算出“微查准率”(micro-P)、“微查全率”(micro-R)并可计算出“微F1”(micro-F1)

micro-P=1n∑i=1nPi,micro-R=1n∑i=1nRi,micro-F1=2×micro-P×micro-Rmicro−P+micro−Rmicro-P=1n∑i=1nPi,micro-R=1n∑i=1nRi,micro-F1=2×micro-P×micro-Rmicro−P+micro−R

 

2.3.3 ROC与AUC

ROC：受试者工作特征。 
我们根据学习器的预测结果对样例进行排序，按此顺序逐个把样本作为正例进行预测。 
纵轴是“真正例率”——真正例在所有正例中的比率。

TPR=TPTP+FNTPR=TPTP+FN

，横轴是“假正例率”——假正例在所有反例中的比率

FPR=FPTN+FPFPR=FPTN+FP

显示ROC曲线的图称为“ROC图”，对角线对应于“随机猜测”模型，而点(0,1)则对应于将所有正例排在所有反例之前的“理想模型”。（着重理解下=-=） 
若一个学习器的ROC曲线被另一个学习器的曲线完全“包住”，则可断言后者的性能优于前者；若两个学习器的ROC发生交叉，可以比较ROC曲线下的面积，即AUC。AUC可估算为

AUC=12∑i=1m−1(xi+1−xi)(yi+yi+1)AUC=12∑i=1m−1(xi+1−xi)(yi+yi+1)

给定m+m+个正例和m−m−个反例，令D+D+和D−D−分别表示正、反例集合，则排序“损失”（loss）表示为：

lrank=1m+m−∑x+∈D+∑x−∈D−⟮⨿(f(x+)<f(x−))+12⨿(f(x+)=f(x−))⟯lrank=1m+m−∑x+∈D+∑x−∈D−⟮⨿(f(x+)<f(x−))+12⨿(f(x+)=f(x−))⟯

即考虑每一对正、反例，若正例的预测值小于反例，则记一个“罚分”，若相等则记0.5个“罚分”。容易看出，lranklrank对应的是ROC曲线之上的面积：若一个正例在ROC曲线上对应的标记点的坐标是(x,y)，则x恰是排序在其之前的反例所占的比例，即假正例律。（此处不太懂=-=）因此有：

AUC=1−lrankAUC=1−lrank

 

2.3.4 代价敏感错误率与代价曲线（没有仔细看）

在非均等代价下，我们所希望的不再是简单的最小化错误次数，而是希望最小化“总体代价”。可以推导出“代价敏感”错误率，精度的代价敏感版本等等。 
在非均等代价下，ROC曲线不能直接反映出学习器的期望总体代价，而“代价曲线”则可达到该目的。代价曲线图的横轴是取值为[0,1]的正例概率代价

P(+)cost=p×cost01p×cost01+(1−p)×cost10P(+)cost=p×cost01p×cost01+(1−p)×cost10

其中p是样例为正例的概率；纵轴是取值为[0,1]的归一化代价

costnorm=FNR×p×cost01+FPR×(1−p)×cost10p×cost01+(1−p)×cost10costnorm=FNR×p×cost01+FPR×(1−p)×cost10p×cost01+(1−p)×cost10

其中，FPR是假正例律，FNR=1-TPR是假反例率。

 

2.4 比较检验(这里不懂！各种检验什么的)

机器学习中性能比较涉及的因素： 
1. 希望对比泛化性能，然而得到的是测试集上的性能，两者未必相同。 
2. 测试集上的性能与测试集本身有很大的关系。 
3. 机器学习算法本身有一定的随机性，运行结果可能不同。 
本节默认以错误率为性能度量，用ϵϵ表示。

2.4.1 假设检验

假设检验中的“假设”是对学习器泛化错误率的某种判断或猜想。 
泛化错误率为ϵϵ的学习器在一个样本上犯错的概率是ϵϵ；测试错误率ϵ^ϵ^意味着在m个测试样本中恰有ϵ^×mϵ^×m个被误分类。 
在包含了m个样本的测试集上，泛化错误率为ϵϵ的学习器被测得测试错误率为ϵ^ϵ^的概率：

P(ϵ^;ϵ)=(mϵ^×m)ϵϵ^×m(1−ϵ)m−ϵ^×mP(ϵ^;ϵ)=(mϵ^×m)ϵϵ^×m(1−ϵ)m−ϵ^×m

给定测试错误率，解∂P(ϵ^;ϵ)/∂ϵ=0∂P(ϵ^;ϵ)/∂ϵ=0可知，P(ϵ^;ϵ)P(ϵ^;ϵ)在ϵ=ϵ^ϵ=ϵ^时最大。符合二项分布。 
“二项检验”可对“ϵ≤ϵ0ϵ≤ϵ0”进行检验。考虑上述假设，则在1−α1−α的概率内所能观测到的错误率如下式计算。

ϵ¯=max∈ s.t. ∑i=ϵ0×m+1m(mi)ϵi(1−ϵ)m−i<αϵ¯=max∈ s.t. ∑i=ϵ0×m+1m(mi)ϵi(1−ϵ)m−i<α

此时若测试错误率ϵ^<ϵ¯ϵ^<ϵ¯，则根据二项检验可得出结论：在αα的显著度下，假设“ϵ≤ϵ0ϵ≤ϵ0”不能被拒绝。 
t检验 
常使用多次重复留出法或交叉验证法进行多次训练/测试，得到多个测试错误率。 
平均测试错误率μμ和方差σ2σ2：

μ=1k∑i=1kϵi^σ2=1k−1∑i=1k(ϵ^i−μ)2μ=1k∑i=1kϵi^σ2=1k−1∑i=1k(ϵ^i−μ)2

这k个测试错误率可看做泛化错误率ϵ0ϵ0的独立采样，则变量

τt=k−−√(μ−ϵ0)στt=k(μ−ϵ0)σ

服从自由度为k-1的t分布。 
对于假设“μ=ϵ0μ=ϵ0”和显著度αα，当测试错误率均值为ϵ0ϵ0时，在1−α1−α概率内能观测到最大错误率，即临界值。

 

上述两种方法都是对关于单个学习器泛化性能的假设进行检验。

2.4.2 交叉验证t检验

思想：若两个学习器的性能想通，则它们使用相同的训练/测试集得到的测试错误率应相同，即ϵAi=ϵBiϵiA=ϵiB. 
对k折交叉验证产生的k对测试错误率：先对每对结果求差，Δi=ϵAi=ϵBiΔi=ϵiA=ϵiB；若两个学习器性能相同，则差值均值应为零。

2.4.3 McNemar检验

对于二分类问题，可获得列联表： 

算法B正确错误算法A正确e00e10错误e01e11算法B算法A正确错误正确e00e01错误e10e11

若我们做的假设是两学习器性能相同，则应有e01=e10e01=e10，那么变量|e01−e10||e01−e10|应当服从正态分布。McNemar检验考虑变量

τχ2=(|e01−e10|−1)2e01+e10τχ2=(|e01−e10|−1)2e01+e10

服从自由度为1的χ2χ2分布。

 

2.4.4 Friedman检验与Nemenyi后续检验

交叉验证t检验和McNemar检验都是在一个数据集上比较两个算法的性能。 
现在在一个数据集上比较多个算法。常用基于算法排序的Friedman检验。 
首先，使用留出法或交叉验证法得到每个算法在每个数据集上的测试结果，然后得到每个算法在各个数据集上性能的平均序值。然后，使用Friedman检验来判断这些算法是否性能都相同——平均序值是否相同。若不相同，则需进行“后续检验”来进一步区分各算法。常用Nemenyi后续检验。（关于Friedman和Nemenyi的具体公式在此略去~）

2.5 偏差和方差

对学习算法除了通过实验估计其泛化性能，人们往往还希望了解它“为什么”具有这样的性能。“偏差-方差分解”是解释学习算法泛化性能的重要工具。 
偏差度量了学习算法的期望预测与真是结果的偏离程度，即刻画了学习算法本身的你和能力。bias2(x)=(f¯(x)−y)2bias2(x)=(f¯(x)−y)2 
方差度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响。var(x)=ED[(f(x;D)−f¯(x))2]var(x)=ED[(f(x;D)−f¯(x))2] 
噪声则表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度。ε2=ED[(yD−y)2]ε2=ED[(yD−y)2] 
偏差-方差分解说明，泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的。给定学习任务，为了取得好的泛化性能，则需使偏差较小，即能够充分拟合数据，并且使方差较小，即是的数据扰动产生的影响小。 
偏差与方差有冲突——“偏差-方差窘境”