第5章
CHAPTER 5


机器学习的性能与评估







正如第1章中“没有免费午餐定理”所述，没有一种机器学习模型是对所有问题普遍适用的，正因为如此，机器学习领域中
出现众多的不同模型。第3章和第4章介绍了基本的回归和分类模型，在第6章之后仍将继续介绍多种常用的机器学习模型。在这样一个节点，本章偏离机器学习模型和学习算法的介绍，以一章的篇幅集中介绍机器学习中训练和性能评价的一些基本问题，这是一个很大的问题，本章的介绍仅仅是入门和概要性质的。


当用模型表示一类问题时，对模型性能的理想描述是期望风险，即从完整的统计意义上刻画模型相对于目标的偏差。但在机器学习领域，缺乏对目标完整的概率描述，因此无法获得期望风险，而是
从有限数据中学习模型，评价准则也以经验风险代替期望风险。由于数据集的代表能力有限，以经验风险最优确定的模型对真实目标的总体表达能力如何，即泛化能力如何？这是一个非常关键的问题。


泛化性能好是一个机器学习模型可用的基本要求，因此必须对泛化性能进行评价。一种比较实际的评价泛化性能的方法是通过数据集进行测试，将数据集划分为训练集和测试集，用训练集学习模型，在测试集上近似估计其泛化性能； 
另一种评价方法是给出理论上的泛化界并研究泛化误差与数据集规模的关系，这是机器学习理论讨论的基本问题。遗憾的是，目前这两类方法之间仍存在鸿沟。利用机器学习理论，对于在要求的泛化误差下给出的样本规模并不能很精确地指导许多实际机器学习模型的训练，逾越这道鸿沟仍需努力。


本章由两部分组成，第1部分包括5.1节和5.2节，讨论如何利用实际数据集有效地训练和评价一个机器学习模型； 第2部分
由5.3节和5.4节组成，讨论机器学习理论中的一些基本概念和结论。

5.1模型的训练、验证与测试


在1.3节介绍机器学习的基本元素时，为了讨论问题方便，将数据集分为训练集和测试集。本节结合实际机器学习系统的学习过程，对数据的划分和作用再做一些更深入的讨论。


在机器学习的许多模型中，存在一些称为超参数的量，超参数是不能直接通过训练过程确定得到的，
例如多项式拟合的阶M、KNN的参数K或正则项的控制参数λ。可以通过学习理论或贝叶斯框架下的学习确定这些超参数，但目前实际中更常用的是通过验证过程确定。


在最简单的情况下，不需要确定超参数，数据集仍划分为训练集和测试集，或两个集合独立地产生自同一个数据生成分布，训练集训练模型，通过测试误差近似评价泛化性能。


更复杂的情况下可将数据集划分为3个集合： 训练集、验证集(validation set)和测试集。若数据集数据量充分，可以直接按一定比例划分3个集合，例如训练集占80%，验证集占10%，测试集占10%，各集合的比例可根据数据集的总量做适当调整，数据集划分如图5.1.1(a)所示。在一般的学习过程中，在超参数的取值空间内，按一定方式(等间隔均匀取值或随机取值)取一个(或一组，复杂模型可能有多个超参数)超参数值，用这组确定的超参数，通过训练集训练模型，将训练得到的模型用于验证集，计算验证(集)误差。取不同的超参数，重复这个过程，最后确定效果最好的超参数及对应的模型。然后用测试集测试性能，计算测试误差，估计泛化性能。若测试性能达不到要求，还可能回到原点，选择不同的模型，重复以上过程，直到达到要求或在可能选择的模型中取得最好结果。在整个过程中测试集是不参与学习过程的，这样才能够可信地评估模型的泛化能力。





一些情况下，数据集规模较小，若固定地分成3个集合，则每个集合数据量小使训练过程和验证过程都缺乏可靠性。这种情况下可采用交叉验证(cross validation)方法。数据集仍划分为测试集和训练集，测试集留作最后的测试用。将训练集分为
K折(K folds)，用于训练和验证，对于一组给出的超参数，做多轮训练，每次训练留出一折作为验证集，其余作为训练集，进行一次训练和验证，然后循环操作，过程如图5.1.1(b)所示。做完一个循环，将每次验证集的误差做平均，作为验证误差。选择一组新的超参数重复该过程，直到全部需要实验的超参数取值完成后，比较所有超参数取值下的验证误差，确定超参数的值，其后再用全部训练集样本训练出模型。将以上学习过程确定的模型用于测试集计算测试误差，评价是否达到目标。




图5.1.1用于训练和测试的数据集划分



在数据集样本相当匮乏的情况下，以上交叉验证可取其极限情况，每轮只留一个样本作为验证集，称为留一验证(leaveone out cross validation，LOOCV)。


以上介绍了用数据集获得一个机器学习模型的基本方法。实践中可能还有各种灵活的组合方式。
后续章节介绍的各种算法在实际中应用时，一般用上述某种方式完成学习和测试过程。

5.2机器学习模型的性能评估


一个机器学习模型确定后，性能是否符合任务的需求，需要对其进行评估。一般来讲，对于较复杂的实际任务，性能评估方法可能与任务是相关的，因此性能评估方式有很多，本书作为以机器学习算法为主的基本教材，不对各种与任务相关的评
估方法做过多讨论，本节只对几个最基本的性能评价方法进行概要介绍，并只讨论监督学习中的回归和分类的性能评估。


对一个机器学习模型h(x)做准确的性能评估是困难的，实际中一般是在样本集(例如测试集)
上对其进行性能评估，当样本集中样本数充分多且可充分表示实际样本分布时，用在样本集上的评估作为近似的泛化性能评估。本节为了叙述简单，假设样本集中的标注y均是标量。样本集表示为


D={(xi,yi)}Ni=1(5.2.1)


1. 回归的性能评估


对于回归问题，模型h(x)的输出和样本标注均为实数，在样本集上评价其性能的常用方法是均方误差，即



Emse(h)=1N∑Ni=1
［h(xi)-yi］2(5.2.2)


均方误差重点关注了大误差的影响，在一些应用中，也可能采用平均绝对误差或最大误差，分别表示为



Eabs(h)=1N∑Ni=1|h(xi)-yi|(5.2.3)
E∞(h)= max1≤i≤N{|h(xi)-yi|}(5.2.4)


尽管存在一些其他评价函数，在回归问题中，均方误差评价使用最多。

2. 分类的性能评估


分类的性能评估比回归要复杂。这里讨论只有两类的情况，将我们更关心的一类称为正类，另一类称为负类。

评价分类的最基本准则是分类错误率和分类准确率，当对一个样本(xi,yi)做分类测试时，若分类器输出h(xi)与样本标注相等，则分类正确，否则产生一个分类错误。对于式(5.2.1)的样本集中所有样本
，统计对h(x)能够进行正确分类和错误分类的比例，可得到在样本集上的分类错误率和分类准确率，分别表示为



E=1N∑Ni=1I［h(xi)≠yi］(5.2.5)
Acc=1N∑Ni=1I［h(xi)=yi］=1-E(5.2.6)


其中，I(x)是示性函数，x是逻辑变量。当x为真时，I(x)=1，否则I(x)=0。当一个样本集中正
类样本和负类样本分布均衡(大致数目相当)，各种分类错误(将正
类错分为负类或反之)代价相当时，分类准确率(或分类错误率)可较好
地评价分类器的性能。但当式(5.2.1)所示的样本集中正
类样本和负类样本分布很不均衡时，分类正确率不能客观反映分类器性能，甚至引起误导。例如，在一个检测某癌症的数据集中有10000个样本，正类样本(患癌症)的数目只有300，其余的均为负类样本(非患者)，对于这样的样本集，若一个分类器简单地将所有样本分类为负类，则分类准确率仍为0.97，这个指标相当好，但对本任务该分类器毫无用处。


为了进一步讨论怎样构造更合理的评价方法，对于一个分类器h(x)，将式(5.2.1)的样本集分为4类： 
①真正类，即样本为正样，分类器将其分为正类； ②真负类，即样本是负样，分类器将其分类为负类； 
③假负类，即样本为正样，分类器将其分为负类； 
④假正类，即样本是负样，分类器将其分类为正类。样本集中各类的数目如表5.2.1所示。


表5.2.1样本的类型



标注的真实类型

分类器返回的类型

正类负类

正类NTPNFN
负类NFPNTN



用表5.2.1的符号，样本总数N=NFP+NFN+NTP+NTN，可重写分类错误率和分类准确率为


E=NFP+NFNNFP+NFN+NTP+NTN
Acc=NTP+NTNNFP+NFN+NTP+NTN



对于前述癌症的例子，若将所有样本均分类为负类，则NFP=NTP=0，NFN=300，
NTN=9700，E=0.03,Acc=0.97。在这种情况下，分类错误率和分类准确率几乎无法告诉我们分类器的实际效用
。下面定义两个更有针对性的性能评价： 精度(precision)和查全率(recall)。


精度定义为真正类NTP与被分类器识别为正类的所有样本NTP+NFP的比例，即


Pr=NTPNTP+NFP(5.2.7)


查全率定义为正类样本被分类器正确识别为正类的概率，即真正类数目NTP与正类样本总数NTP+NFN之比


Re=NTPNTP+NFN(5.2.8)


通过一个例子说明两个参数的意义。

例5.2.1针对癌症的例子，设一个分类器对样本集的分类情况如表5.2.2中“/”上侧所示。


表5.2.2样本的类型



标注的真实类型

分类器返回的类型

正类负类

正类210/26090/40
负类200/4009500/9300


可计算出精度和查全率分别为Pr≈0.51，Re=0.7，分类准确率Acc=0.971。


若改变分类器参数，使输出为正类的概率提高，则可能同时负类样本被判定为正类的数目也增加了，如表
1.3.2中“/”下侧的数据，则精度和查全率为Pr≈0.39，Re≈0.87，分类准确率Acc=0.956。


例5.2.1给出了两组数据，所代表的分类器均比将所有样本都分类为负类的“负分类器”有价值，但就分类准确率来讲，
第1组数据没有改善，第2组数据反而下降了。对两组数据自身做比较可见，第2组(“/”之下)数据将更多的
正类样本(癌症)做了正确分类，但同时也将更多的负类样本判别为正类，因此
查全率提高
但精度降低。对于该任务，可以认为第2组数据表示的分类器更有用，它将更多的患者检查出来，以免耽误治疗，对于
将负类样本判别为正类的错误分类，一般可通过后续检查予以改正。在这个应用任务中
查全率的提高是更有意义的，但也有的任务希望有更高的精度。在实际中精度和查全率往往是矛盾的，哪个指标更重要往往取决于具体任务的需求。


可以将精度和查全率综合在一个公式中，即如下的Fβ


Fβ=(β2+1)×Pr×Reβ2×Pr+Re(5.2.9)



对于Fβ，当β>1时，查全率将得到更大权重； 当0≤β<1时，精度得到更大权重。当取β=1时，查全率和精度有等重的比例，得到一个简单的综合性能指标


F1=2×Pr×RePr+Re(5.2.10)





图5.2.1PR曲线示意

当调整一个分类器的参数使其性能变化时，常利用PR曲线或ROC曲线评价分类器在不同参数下的表现。


PR曲线是以精度为纵轴、以查全率为横轴的曲线，一般随着查全率提高，精度下降，图5.2.1为一个典型PR曲线的示意图。



ROC最初来自雷达检测技术，是接收机工作特性的缩写(receiver operating characteristic)。对于分类器，可
定义正类样本分类准确率为


PAc=NTPNTP+NFN(5.2.11)


和负类样本错误率为


Ne=NFPNTN+NFP(5.2.12)



当改变分类器参数时，PAc和Ne都变化，以PAc为纵轴，以Ne为横轴，可画出一条曲线，则称为ROC曲线。一个理想的分类器，可取到PAc=1和Ne=0点，但现实中难以实现这样的分类器。实际分类器曲线示例如图5.2.2所示。


对于一个实际分类器，若控制参数将所有样本分类为负类，则对应(Ne,PAc)=(0,0)； 若将所有样本分类为正
类，则(Ne,PAc)=(1,1)，则曲线可通过坐标原点和(1,1)点。设有两个分类器对应的
ROC曲线c1和c2画在同一图中，若c1总是位于c2之上，则分类器1性能总是优于分类器2； 若两条曲线有交叉，
则在不同参数下两个分类器表现各有优劣。对于ROC曲线有交叉的不同分类器，一种比较其总体优劣的方法是采用AUG(area under ROC curve)参数，一个分类器的AUG参数表示为其ROC曲线之下到坐标横轴之间的面积。



图5.2.2分类器ROC曲线示例


针对各类应用任务还有许多特别的参数，例如对于医学应用和金融应用，人们关注的性能可能非常不同，本书不再进一步讨论针对实际任务的性能评价。



5.3机器学习模型的误差分解

本节以回归学习作为对象，讨论模型复杂度与误差的关系，即模型的偏和方差的折中问题。在
3.3节的多项式基函数例子中(例3.3.3)，已经看到对于固定规模的训练数据集，随着模型复杂度变化，训练误差和测试误差的
变化关系。为了清楚起见，将该图重示于图5.3.1(a)中。
以多项式阶M表示模型的复杂度，可以看到，随着M增加，训练误差单调减少，但测试误差先减小
后上升，也就是模型出现过拟合。用测试误差逼近所学模型的泛化误差，故模型的泛化误差不是随着模型的表达能力
增强而减小，一般泛化误差与模型复杂度的关系是一个U形曲线。图5.3.1(b)给出了训练误差与测试误差的一种更一般的示意图，横坐标表示模型的复杂性，类似地，训练误差单调减
小，测试误差类似U形曲线。对于一个给定的学习任务，可选择对应测试误差U
形曲线底端的模型复杂度。对于具体例子，图5.3.1(a)中M取3~7这样一个较宽的范围，测试误差都处于U形的底端，都是可选的模型复杂度。



图5.3.1模型复杂度与误差的关系



接下来讨论更一般的泛化误差问题，以一般的回归模型作为讨论对象，不限于本书前面讨论的线性回归或基函数回归。假设一个数据集D={(xn,yn)}Nn=1是
对一个联合概率密度函数p(x,y)的采样，通过一个数据集学习得到的模型
为y^(x)，注意这里模型没有显式地依赖参数w，可表示更一般的模型。定义误差函数为


L［y^(x),y］=
［y^(x)-y］2(5.3.1)


其中，y表示回归模型要逼近的真实值。针对p(x,y)可得到模型的误差期望为



E(L)=∫∫L［y^(x),y］p(x,y)dxdy
=∫∫［y^(x)-y］2p(x,y)dxdy(5.3.2)


其中，E(L)是针对模型y^(x)的泛化误差。


对于回归问题，由第2章讨论的决策理论可知，若已知p(x,y)，则最优的回归模型为



h(x)=∫yp(y|x)dy=E(y|x)(5.3.3)


机器学习中，由于一般不知道准确的p(y|x)，无法直接获得最优回归模型h(x)，但是从原理上可以将h(x)作为一个比较基准，得到如下误差分解



E(L)=∫∫［y^(x)-y］2p(x,y)dxdy
=∫∫［y^(x)-h(x)+h(x)-y］2p(x,y)dxdy
=∫∫［y^(x)-h(x)］2p(x,y)dxdy+∫∫［h(x)-y］2p(x,y)dxdy+
2∫∫［y^(x)-h(x)］［h(x)-y］p(x,y）dxdy
=∫［y^(x)-h(x)］2p(x)dx+∫∫［E(y|x)-y］2p(x,y)dxdy(5.3.4)


式中，y^(x)-h(x)与y无关，交叉项积分为0，误差项由两项组成，其中第2项是随机变量的不可完全预测性的结果，这是一个固有量，与模型选择、学习过程均无关。式(5.3.4)最后一行的第1项是与模型和学习过程有关的，接下来仔细分析这一项。


假设只给出一个数据集D={(xn,yn)}Nn=1，在这个数据集上学习回归模型，学习到的模型是与数据集相关的，为了清楚表示与数据集的相关性，将学习到的模型表示为y^(x;D)，若可以获得若干数据集，将每个数据集学习的模型做平均，当数据集数目很大时，这个平均逼近一个期望，用符号ED
［y^(x;D)］表示。使用这个符号，将针对一个指定数据集时的误差项［y^(x)-h(x)］2分解为


［y^(x;D)-h
(x)］2=
{y^(x;D)-ED
［y^(x;D)］+ED［y^(x;D)］-h(x)}2

={y^(x;D)-ED
［y^(x;D)］}2+
{ED［y^(x;D)］-h(x)}2+
2{y^(x;D)-
ED［y^(x;D
)］}{ED［y^(x;D
)］-h(x)}
(5.3.5)


将以上误差项对所有不同数据集进行平均，即取ED(·)，则注意到交叉项为0，故



ED{［y^(x;D)-h(x)］2}
=ED{［y^(x;D)-ED(y^(x;D))］2}+ED{［ED(y^(x;D))-h(x)］2}
=［ED(y^(x;D))-h(x)］2+ED{［y^(x;D)-ED(y^(x;D))］2}(5.3.6)


式(5.3.6)的第1项是偏差，从多个数据集分别学习得到模型的y^(x;D)做平均的结果ED(y^(x;D))仍与最优模型h(x)之间存在偏差； 第2项是学习得到的模型的方差，即每
个数据集训练得到的模型与模型期望之间的偏离程度，这个方差越大，不同数据集训练出的模型的起伏程度越大。由于式(5.3.6)对所有数据集D取了期望，其与具体数据集无关，可以看作
［y^(x)-h(x)］2
，带入式(5.3.4)得


E(L)=∫［ED(y^(x;D))-h(x)］2p(x)dx+
∫ED{［y^(x;D)-ED(y^(x;D))］2}p(x)dx+
∫∫［E(y|x)-y］2p(x,y)dxdy
=(偏)2+方差+固有误差
(5.3.7)

式(5.3.7)说明，对于一个给出的模型，其泛化误差由3部分组成： 偏(实际是偏的平方，为了叙述简单，这里称为偏)、方差和固有误差。固有误差与模型、数据集和学习过程均无关，不需要进一步讨论。偏和方差确实与模型选择有关，一般地，若选择比较简单的模型，则偏比较大，这是由于模型的表示能力有限，即使从多次训练获得的模型平均也仍偏离最优模型h(x)。若选择比较复杂的模型，可以使偏比较小，但方差变大。设模型是参数模型，则复杂模型具有更多的参数，在给定数据集规模的条件下，每个参数的平均有效样本数较小。第2章讨论过，方差与有效样本数成反比，因此方差变大。即模型简单，方差小，偏大； 模型复杂，方差大，偏小。当模型取得比较合适时，既不算复杂也不算简单，即相对折中的模型，可能偏和方差都比较小，总误差最小。图5.3.2给出了偏、方差和泛化误差随模型复杂度的变化曲线。



图5.3.2模型的误差分解



例5.3.1为了给出误差分解的直观解释，考虑一个简单的学习模型的例子。


设函数f(x)无法直接观测，为了对该函数进行预测，通过采样获得数据集，采样过程为


y=f(x)+v(5.3.8)


由于无法直接观测f(x)，故采样样本存在误差v，设v为零均值、方差为σ2v的高斯噪声。为了讨论问题简单，采样时各输入xi是预先确定的。由采样数据构成I.I.D数据集{xi,yi}Ni=1，由数据集训练一个模型，作为说明，这里采用K近邻回归算法，模型为


y^= f^(x)=1K∑Kl=1y(l)(5.3.9)



这里用y(l)表示对于给定的x，最近邻的K个训练集样本的标注值，用(l)表示最近邻样本的下标。

为了讨论误差分解，首先注意到，通过式(5.3.8)的观测，可得到最优模型为


h(x)=E(y|x)=f(x)


因此，固有误差为σ2v。由于本例较为简单，直接使用式(5.3.4)的最后一行，则有


E(L)=E{(y^-h(x))2}+σ2v
=E1K∑Kl=1f(x(l))+vl
-f(x)2+σ2v
=E1K∑Kl=1f(x(l))-f(x)
2+E1K∑Kl=1vl
2+σ2v
=1K∑Kl=1f(x(l))-f(x)
2+σ2vK+σ2v(5.3.10)



式(5.3.10)从倒数第二行到最后一行，是考虑做预测时，x是一个给出的固定值。式(5.3.10)的最后一行分别是如式(5.3.7)所示的： 偏差、方差和固有误差。对于K近邻方法，K越大代表模型表达力越弱，K=1代表最强表达能力。显然，对于变化的内在函数f(x)，K越大1K∑Kl=1f(x(l))与f(x)偏差越大(越多偏离x更远的函数值参与平均)，但方差σ2vK越小。
K=1时则由最近邻的函数f(x(l))逼近f(x)，因此偏差最小，这时方差σ2vK最大。不管K取何值，最后一项的固有误差σ2v不变。

对于线性回归模型，也可导出闭式结果说明误差的分解，只是推导过程更加复杂一些。


对于机器学习的模型选择来讲，对于给定的问题和数据集，并不是选择越复杂的模型越好，要选择适中的模型。这是一个基本的原则，在实际中怎样使用这个原则，却不是一个简单的问题。从原理上讲，从最大似然准则过渡到完全的贝叶斯框架下，可以解决模型选择的问题，但对于一般非线性模型，贝叶斯框架下的求解要复杂得多。一个更实际的方法是通过正则化和交叉验证来合理地选择模型。


本节注释图5.3.1的测试误差和图5.3.2的泛化误差曲线都呈现一种类似
U形曲线。对于传统的单一机器学习模型，U形曲线具有一般性。但在深度学习中，当深度网络复杂度达到一定规模后，测试误差的表现更加复杂，对于集成学习中一些方法，如随机森林和提升算法，测试误差一般也并没有呈现出
U形曲线，换言之，集成学习更不易出现过拟合问题。机器学习
仍在快速发展，一些传统结论可能会被不断补充和修改。

5.4机器学习模型的泛化性能

5.3节以回归问题为例，讨论了偏和方差的折中问题，本节将以分类问题为例，讨论机器学习的另一个理论问题
——泛化界。偏和方差的折中与泛化界是机器学习理论中关注的两个基本问题，都是关于泛化误差的，两者之间也有密切的联系。


在机器学习模型的训练过程中，一般只有一组训练集，通过训练误差的最小化学习到一个模型，但真正关心的是泛化误差，即对不存在于训练集中的新样本，模型的预测性能如何？所以我们要关心一个基本问题： 训练误差和泛化误差之间有多大的差距？机器学习的概率近似正确(probably approximately correct，PAC)理论对这个问题进行了研究。
下面对该理论给出一个极为简要的介绍。


本节以二分类问题为例，讨论PAC理论的一些最基本概念和结论。假设所面对的样本可表示为
(x,y)，x是输入特征向量，x∈
X，X表示输入空间，y∈{0，1}表示类型，(x,y)满足概率分布pD(x,y)，简写为pD，故可用(x,y)~pD表示样本服从的分布。从pD中采样得到满足独立同分布的训练样本集



D={(xi,yi)}Ni=1(5.4.1)


其中，每个样本(xi,yi)~pD。


用机器学习理论常用的术语，将一个机器学习模型称为一个假设h，h(x)输出{0，1}表示类型，即h完成映射h:X→{0,1}。在一个机器学习过程中，所有可能选择的假设构成一个假设空间H。对于任意假设h∈H，其在训练样本集上的分类错误率定义为训练误差或经验风险，经验风险表示为



R^(h)=1N∑Ni=1I(h(xi)≠yi)(5.4.2)


经验风险表示假设h在训练集上的误分类率，这里I(·)为示性函数。可定义一般的泛化误差为


R(h)=P(x,y)~pD［h(x)≠y］(5.4.3)


对于任意样本(x,y)~pD，不管其是否存在于训练集中，
泛化误差均表示
其总体统计意义上的
误分类率。注意，用R表示泛化误差，用“带帽”的符号R^表示经验风险。


若不考虑可实现性，理论上，希望学习到的假设是从H空间找到使泛化误差最小的假设，即


h*= argminh∈HR(h)(5.4.4)


实际上，由于无法准确获得pD(x,y)，故无法通过泛化误差优化获得最优假设，实际上总是通过经验风险最小化(empirical risk minimization，ERM)得到一个假设，即



h^= argminh∈HR^(h)(5.4.5)


我们关心的一个理论问题： 通过ERM得到的假设h^与真正的泛化误差最小的h*之间的泛化误差差距有多大？即R(h*)与R(h^)差距有多大？


在继续讨论之前，首先通过一个例子进一步理解以上概念。


例5.4.1一个假设空间的例子。在4.2节的感知机的例子中，为了与本节分类输出用{0，1}表示相符，将分类假设修改为


h(x)=I(w-Tx-≥0)(5.4.6)



这里x-包含了哑元，w-包含了偏置系数，是（K+1）维参数向量。式(5.4.6)是一个假设，则假设空间为


H={hw-|h
w-(x)=I(w-Tx-≥0),w-∈
RK+1}(5.4.7)



H表示K维向量空间中的所有线性分类器集合，其中RK+1为K+1维实数集合。由于不同w-构成H的不同成员，故式(5.4.5)可具体化为


h^= argminw-∈RK+1R^(hw-)(5.4.8)


h^是ERM意义下的假设，一般不能通过学习得到h*w-。


实际上，感知机的目标函数式(4.2.21)是式(5.4.2)的经验风险的一种逼近，故训练得到的感知机是对h^的一种逼近。


逻辑回归也可做类似理解，其目标函数交叉熵也是式(5.4.2)经验风险函数的一种近似。


为了研究R(h*)与R(h^)的关系，给出以下引理。


引理5.4.1设Z1,Z2,…,ZN是N个独立同分布的随机变量，均服从伯努利分布，且P(Zi=1)=μ，定义样本均值为μ^=1N∑Ni=1Zi，令ε>0为一个固定值，则



P(|μ-μ^|>ε)≤2exp(-2ε2N)(5.4.9)



该引理说明，对于独立同分布样本，当N充分大时，对于给定的ε>0，均值估计和实际概率值之差大于ε的概率是
很小的。


接下来，对于H有限的情况，利用引理5.4.1导出训练误差和泛化误差的误差界，然后将结论推广到H无限的情况。

5.4.1假设空间有限时的泛化误差界


首先假设空间H是有限的，即H={h1,h2,…,hK}，假设空间成员数目K=|H|可能很大，但
有限。例如4.4节介绍的朴素贝叶斯方法，
当特征分量取离散值时，
其假设空间是有限的。若每个特征变量取有限值，则第7章介绍的决策树假设空间也是有限的。对于例5.4.1，若w-取值为实数，则假设空间是无限的，但若w-的每个分量是由有限位二进制表示的数值，则其假设空间是有限的(详细讨论见
例5.4.2)。首先讨论H有限的情况。


可从H空间选择一个固定的假设hk，利用引理5.4.1容易得到对于hk，其训练误差和泛化误差的关系。为此定义一个随机变量，对于(x,y)~pD，定义



Z=I［hk(x)≠y］(5.4.10)


即当hk对样本(x,y)不能正确分类时Z=1。对式(5.4.1)所示的每个样本有
Zi=I［hk(xi)≠yi］，显然，hk的训练误差为



R^(hk)=1N∑Ni=1Zj(5.4.11)


对比引理5.4.1，Zi是I.I.D的伯努利随机变量，R^(hk)是对R(hk)的样本均值估计，则由式(5.4.9)直接得到


P［|R(hk)-R^(hk)|>ε］≤2exp(-2ε2N)(5.4.12)


以上是对于一个固定的hk，泛化误差和训练误差之差(绝对值)大于ε的概率。对于给定ε，若样本数N足够大，则泛化误差与训练误差相差大于ε的概率很小。


利用式(5.4.12)可导出一个
更一般的结果。因此，定义事件Ak为|R(hk)-R^(hk)|>ε
，则有P(Ak)≤2exp(-2ε2N)。利用概率性质，至少存在一个h(表示为h)，其|R(h)-R^(h)|>ε的概率为



P［h∈H,|R(h)-R^(h)|>ε］=P(A1∪A2∪…∪AK)
≤∑|H|k=1P(Ak)
≤∑|H|k=12exp(-2ε2N)
=2|H|exp(-2ε2N)(5.4.13)


由于是概率值，由互补性，式(5.4.13)等价表示为，对于所有h，有


P［|R(h)-R^(h)|≤ε，h∈H］≥1-2|H|exp(-2ε2N)(5.4.14)


在式(5.4.14)中，令


δ=2|H|exp(-2ε2N)(5.4.15)


式(5.4.14)有丰富的内涵，其中有3个量： δ、ε、N，以下从几个方面讨论式(5.4.14)的含义，并讨论这3个量的关系。


(1) 将式(5.4.14)重写为


P［|R(h)-R^(h)|≤ε］≥1-δ,h∈H(5.4.16)


对于给定的ε，所有假设h∈H都以不小于1-δ的概率满足|R(h)-R^(h)|≤ε，即泛化误差和训练误差之差不大于界ε。这里1-δ是一个置信概率，当N很大时，δ很小，以很高的概率满足|R(h)-R^(h)|≤ε。


(2) 假设空间的元素数目|H|是确定的，若给出ε和δ，则可得到满足以1-δ为概率达到|R(h)-R^(h)|≤ε所需的样本数目。固定δ,ε从式(5.4.15)反解N为


N=12ε2ln2|H|δ(5.4.17)


由式(5.4.15)，N增大，δ减小，故可将式(5.4.17)看作满足δ,ε约束的最小样本数。故对于给定δ、ε，样本数可取为


N≥12ε2ln2|H|δ(5.4.18)


(3) 在式(5.1.15)中，固定δ、N，解得



ε=12Nln2|H|δ(5.4.19)


这给出式(5.4.16)的另一种解释，对于给定的δ、N，误差界满足


|R(h)-R^(h)|≤12Nln2|H|δ(5.4.20)


将以上解释总结为定理5.4.1。


定理5.4.1对于假设空间H，固定δ、N，则以概率不小于1-δ，泛化误差与训练误差满足


|R(h)-R^(h)|≤12Nln2|H|δ



或固定δ、ε，若样本数目取


N≥12ε2ln2|H|δ


则以概率不小于1-δ满足|R(h)-R^(h)|≤ε。


以上结论对于假设空间中的任意假设h∈H均成立。我们更感兴趣的一个问题是，对于以经验风险最小化学习得到的假设h^和理论上泛化误差最小对应的h*之间的泛化误差的比较。由以上结果，若对h∈H有|R(h)-R^(h)|≤ε，则


R(h)≤R^(h)+ε(5.4.21)


对于h^，可得到如下不等式


R(h^)≤R^(h^)+ε≤R^(h*)+ε≤R(h*)+2ε(5.4.22)


式（5.4.22）中第1个不等式只是将h^带入式(5.4.21)
； 第2个不等式用了R^(h^)
≤R^(h*)，这是因为h^是经验误差最小的假设； 第3个不等式对h*再次使用式(5.4.21)。式(5.4.22)的结论是： ERM学习得到的假设h^与泛化误差最优的h*，其泛化误差之差不大于2ε。将该结论总结为重要的定理5.4.2。


定理5.4.2对于假设空间H，固定δ、N，则以概率不小于1-δ，泛化误差满足不等式


R(h^)≤minh∈HR(h)+212Nln2|H|δ(5.4.23)



或固定δ、ε，若样本数目取


N≥12ε2ln2|H|δ



则以概率不小于1-δ满足R(h^)≤minh∈HR(h)+2ε。


由两个定理可见，若固定δ、N，式(5.4.19)计算了一个界ε，对于任意h∈H，训练误差和泛化误差之差以概率1-δ不大于ε，同时EMR最小化得到的假设h^与最小泛化误差之间的差距不大于2ε。


例5.4.2讨论例5.4.1的假设空间


H={hw-|hw-(x)=I(w-Tx-≥0),w-∈RK+1}



w-
有K+1个系数，若w-的每个分量用字长L的二进制表示(计算机中常取L为16、32或64，近期一些研究采用低比特实现神经网络时，甚至取L为8、4)，则表示w-所需的二进制位数为L(K+1)，故假设空间H共有|H|=2L(K+1)个元素，由式(5.4.18)可得，对于固定δ、ε时，样本数需满足


N≥12ε2ln2|H|δ=12ε2ln2×2L(K+1)δ=OKLε2ln1δ=Oε,δ(K)(5.4.24)


或记为


N~Oε,δ(K)(5.4.25)


式中，O(·)表示量级； Oε,δ(·)表示量级函数，其中δ、ε是其参数。式(5.4.25)尽管有比例系数存在，但需要的样本数N与模型的参数数目K是呈线性关系的。

*5.4.2假设空间无限时的泛化误差界


将定理5.4.2的结论推广到假设空间H无限的情况。如前所述，例5.4.1所示的线性模型或后续章节介绍的
支持向量机和神经网络等模型，当参数取实数时，假设空间是无限的，即|H|=∞，这种情况下式(5.4.23)变得无意义。需要对其进行推广。这里对假设空间无限的情况，只做一个非常扼要的介绍。


当|H|=∞时，为了表示假设空间的表示能力(或容量)，给出两个概念： 打散(shatters)和VC维(VapnikChervonenkis dimension)，这里只给出其简单、直观性的介绍。


首先给出打散的概念，对于一个包含d个点的集合S={x1,x2,…,xd}，其中xi∈X，称H可打散S是指： 对点集S对应加上一个任意标注集{y1,y2,…,yd}，则必存在h∈H，使h(xi)=yi,i=1,2,…,d。


对于一个假设空间H，其VC维的定义为： 至少存在一个最大元素数为d的点集合S，H可打散S，则H的VC维为d，记为VC(H)=d。这里d是最大能被H打散的点集的元素数，对于有d+1个元素的点集合，H均不可能打散它。

例5.4.3图5.4.1给出二维平面上的3个点组成的点集和其对应的各种标注，直线表示判决线，假设空间为二维线性分类器，即


H={h(x)=θ1x1+θ2x2+θ0|θ0,θ1,θ2∈R}


图中每条判决线属于H，对这个3个元素的点集，H可将其打散。如果是4个点，则对于标注是异或运算，H不能正确分类，故H不能打散4个点的点集，因此，平面线性分类器的VC维为3，即VC(H)=3。



图5.4.1可由线性分类器打散的点集



若用VC维d表示一个假设空间的容量，则可得到与定理5.4.2类似的结论，这里只给出对应的定理。

定理5.4.3对于假设空间H，若其VC维为d=VC(H)，则对于所有h∈H，以概率不小于1-δ，有不等式


|R(h)-R^(h)|≤OdNlnN
d+1Nln1δ(5.4.26)



对于h^有不等式


R(h^)≤minh∈HR(h)+OdNlnNd+1Nln1δ(5.4.27)



对于以概率不小于1-δ满足R(h^)≤minh∈HR(h)+2ε，样本数目需要求


N~Oε,δ(d)(5.4.28)



注意，这里只用了量级函数O(·)而忽视了表达式中的一些具体常数系数，对于了解性能界，这就够了。从式(5.4.28)看，对于无限假设空间，所需样本数与假设空间的VC维呈线性关系。


机器学习理论给出对学习性能的整体性洞察，是非常有意义的，但目前对于一类实际模型的学习算法(如逻辑回归、神经网络、决策树等)，其给出的一些要求
（如样本数等）与具体算法的实际需求还有较大距离，在指导一类具体算法的参数选择上的实际意义还有待改善，故实际中仍更常用交叉验证等技术确定机器学习模型的各类参数。

5.5本章小结


本章介绍了基本的机器学习性能与评估，从两个方面进行讨论。首先从实用方面，介绍了利用数据集通过交叉验证和测试的实际技术训练一个机器学习模型的基本过程，并介绍了几个实际中常用的机器学习性能评估指标。然后从理论上讨论了机器学习的性质。为了讨论上的直观，结合回归介绍了偏和方差的折中问题，结合分类介绍了泛化界定理。

本书更侧重于机器学习算法的介绍，有关机器学习理论的讨论非常简略，对机器学习理论更感兴趣的读者，可参考Mohri等的教材（参考文献［32］）和Shai SS等的著作
(参考文献［44］)，这两本书对机器学习理论进行了较为深入的讨论，均由张文生等译成了中文。Vapnik对于统计学习理论给出了一个简明版的读本(参考文献［50］)，已由张学工译成中文。

习题

1. 什么是交叉验证？假设有1000个带标注的样本，设计一个参数模型
y^=h(x;w)，讨论你可能选择的样本集划分方式和交叉验证过程。

2. 对于如下表示的线性分类器的假设空间



H={hw-|hw-(x)=I(w-Tx-≥0),w-∈RK+1}


设w-有11个系数，若w-的每个分量用字长8比特的二进制表示，若得到模型的经验误差和泛化误差的差距以0.95的概率不大于0.05，则样本数应至少取多少？ 









第二部分
PART2





经 典 算 法