2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 1
机器学习第 5章 评估假设
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
对假设的精度进行评估是机器学习中的基本问题
本章介绍用统计方法估计假设精度，主要解决以下三个问题：
– 已知一个假设在有限数据样本上观察到的精度，怎样估计它在其他实例上的精度？
– 如果一个假设在某些数据样本上好于另一个，那么一般情况下该假设是否更准确？
– 当数据有限时，怎样高效地利用这些数据，通过它们既能学习到假设，还能估计其精度？
统计的方法，结合有关数据基准分布的假定，使我们可以用有限数据样本上的观察精度来逼近整个数据分布上的真实精度
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
动机
对学习到的假设进行尽可能准确地性能评估十分重要
– 为了知道是否可以使用该假设
– 是许多学习方法的重要组成部分
当给定的数据集有限时，要学习一个概念并估计其将来的精度，存在两个很关键的困难：
– 估计的困难
使用与训练样例和假设无关的测试样例
– 估计的方差
即使假设精度在独立的无偏测试样例上测量，得到的精度仍可能与真实精度不同。
测试样例越少，产生的方差越大
本章讨论了对学到的假设的评估、对两个假设精度的比较、两个学习算法精度的比较
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
学习问题的框架
有一所有可能实例的空间 X，其中定义了多个目标函数，我们假定 X中不同实例具有不同的出现频率。一种合适的建模方式是，假定存在一未知的概率分布 D，它定义了 X中每一实例出现的概率。
学习任务是在假设空间上学习一个目标概念，
训练样例的每一个实例按照分布 D独立地抽取，
然后连同正确的目标值提供给学习器。
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
评估假设的问题
给定假设 h和包含若干按 D分布抽取的样例的数据集，如何针对将来按同样分布抽取的实例，得到对 h的精度最好估计
这一精度估计的可能的误差是多少
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
样本错误率和真实错误率
定义：假设 h关于目标函数 f和数据样本 S的样本错误率（标记为 errors(h)）
定义：假设 h关于目标函数 f和分布 D的真实错误率（标记为 errorD(h)）
Sxs xhxfnhe rro r ))(),((1)(?
o th e r w is exhxfxhxf )()(01))(),((?
||Sn?
)]()([Pr)( xhxfhe rror DxD
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
样本错误率和真实错误率（ 2）
我们想知道的是假设的真实误差，因为这是在分类未来样例时可以预料到的误差。
我们所能测量的只是样本错误率，因为样本数据是我们知道的。
本节要考虑的问题是：样本错误率在何种程度上提供了对真实错误率的估计？
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
离散值假设的置信区间
先考虑离散值假设的情况，比如：
– 样本 S包含 n个样例，它们的抽取按照概率分布 D，
抽取过程是相互独立的，并且不依赖于假设 h
– n>=30
– 假设 h在这 n个样例上犯了 r个错误
根据上面的条件，统计理论可以给出以下断言：
– 没有其他信息的话，真实错误率 errorD(h)最可能的值是样本错误率 errorS(h)=r/n
– 有大约 95%的可能性，真实错误率处于下面的区间内：
n he r r o rhe r r o rhe r r o r SSS ))(1)((96.1)(
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
举例说明
数据样本 S包含 n=40个样例，并且假设 h在这些数据上产生了 r=12个错误，这样样本错误率为
errorS(h)=12/40=0.3
如果没有更多的信息，对真实错误率 errorD(h)的最好的估计即为 0.3
如果另外收集 40个随机抽取的样例 S’，样本错误率
errorS’(h)将与原来的 errorS(h)存在一些差别
如果不断重复这一实验，每次抽取一个包含 40样例的样本，将会发现约 95%的实验中计算所得的区间包含真实错误率
将上面的区间称为 errorD(h)的 95%置信区间估计
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
置信区间表达式的推广
常数 1.96是由 95%这一置信度确定的
定义 zN为计算 N%置信区间的常数（取值见表 5-
1），计算 errorD(h)的 N%置信区间的一般表达式（公式 5.1）为：
可以求得同样情况下的 68%置信区间，从直觉上可以看出 68%置信区间要小于 95%置信区间，
因为减小了要求 errorD(h)落入的概率
n he r r o rhe r r o rzhe r r o r SSNS ))(1)(()(
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
置信区间表达式的推广（ 2）
公式 5.1只能应用于离散值假设，它假定样本 S
抽取的分布与将来的数据抽取的分布相同，并且假定数据不依赖于所测试的假设
公式 5.1只提供了近似的置信区间，这一近似在至少包含 30个样例，并且 errorS(h)不太靠近 0或
1时很接近真实情况
判断这种近似是否接近真实的更精确规则是：
5))(1)(( he rro rhe rro rn SS
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
统计学中的基本定义和概念
随机变量
某随机变量 Y的概率分布
随机变量 Y的期望值或均值
随机变量的方差
Y的标准差
二项分布
正态分布
中心极限定理
估计量
Y的估计偏差
N%置信区间
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
错误率估计和二项比例估计
样本错误率和真实错误率之间的差异与数据样本大小的依赖关系如何？
给定从总体中随机抽取的某些样本的观察比例，估计某个属性在总体的比例
此处，我们感兴趣的属性是：假设 h对实例错误分类
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
错误率估计和二项比例估计（ 2）
测量样本错误率相当于在作一个有随机输出的实验
从分布 D中随机抽取 n个独立的实例，形成样本
S，然后测量样本错误率 errorS(h)
将实验重复多次，每次抽取大小为 n的不同的样本 Si，得到不同的,取决于 Si的组成中的随机差异
被称为一随机变量，一般情况下，可以将随机变量看成一个有随机输出的实验。随机变量值即为随机实验的观察输出
)(herroriS
)(herroriS
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
错误率估计和二项比例估计（ 3）
设想要运行 k个这样的随机实验，得到 k
个随机变量值，以图表的形式显示观察到的每个错误率值的频率
当 k不断增长，该图表将呈现如表 5-3所显示的分布，称为二项分布
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
二项分布
有一非均质硬币，要估计在抛硬币时出现正面的概率 p
投掷硬币 n次并计算出现正面的次数 r，那么 p的一个合理估计是 r/n
如果重新进行一次实验，生成一个新的 n次抛硬币的集合，出现正面的次数 r可能与前不同，
得到对 p的另一个估计
二项分布描述的是对任一可能的 r值，这个正面概率为 p的硬币抛掷 n次恰好出现 r次正面的概率
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
二项分布（ 2）
从抛掷硬币的随机样本中估计 p与在实例的随机样本上测试 h以估计 errorD(h)是相同的问题
一次硬币抛掷对应于从 D中抽取一个实例并测试它是否被 h误分类
一次随机抛掷出现正面的概率 p对应于随机抽取的实例被误分类的概率 errorD(h)
二项分布给出了一个一般形式的概率分布，无论用于表示 n次硬币出现正面的次数还是在 n个样例中假设出错的次数
二项分布的具体形式依赖于样本大小 n以及概率 p或
errorD(h)
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
应用二项分布的条件
有一基本实验，其输出可被描述为一随机变量
Y，随机变量 Y有两种取值
在实验的任一次尝试中 Y=1的概率为常数 p，它与其他实验尝试无关，因此 Y=0的概率为 1-p
p为预先未知，面临的问题是如何估计
基本实验的 n次独立尝试按序列执行，生成一个独立同分布的随机变量序列
随机变量 R表示 n次实验中出现 Yi=1的次数，它取特定值 r的概率由二项分布给出
rnr pprnr nrR )1()!(! !)Pr (
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
均值
期望值是重复采样随机变量得到的值的平均
定义：考虑随机变量 Y可能的取值为
y1...yn,Y的期望值 E[Y]定义如下：
如果随机变量 Y服从二项分布，那么可得
E[Y]=np
ni ii yYyYE 1 )P r(][
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
方差
方差描述的是概率分布的宽度或散度，描述了随机变量与其均值之间的差有多大
定义：随机变量 Y的方差 Var[Y]定义如下：
描述了从 Y的一个观察值估计其均值 E[Y]的误差平方的期望
随机变量 Y的标准差?Y
若随机变量 Y服从二项分布，则方差和标准差分别为：
Var[Y]=np(1-p)
]))([(][ 2YEYEYV ar
]])[[( 2YEYEY
)1( pnpY
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
估计量、偏差和方差
回到问题：我们得出了随机变量 errorS(h)服从二项分布，那么 errorS(h)和 errorD(h)之间可能的差异是多少？
用 5.2式定义的二项分布，可得
errorS(h)=r/n
errorD(h)=p
统计学中将 errorS(h)称为 errorD(h)的一个估计量
估计量是用来估计总体的某一参数的随机变量，
最关心的是它平均来说是否能产生正确估计
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
估计量、偏差和方差（ 2）
估计偏差衡量估计量的期望值同真实参数值之间的差异
定义：针对任意参数 p的估计量 Y的估计偏差是：
E[Y]-p
如果估计偏差为 0，称 Y为 p的无偏估计量，在此情况下，由多次重复实验生成的 Y的多个随机值的平均将收敛于 p
由于 errorS(h)服从二项分布，因此 errorS(h)是
errorD(h)的一个无偏估计量
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
估计量、偏差和方差（ 3）
对估计偏差的补充说明：
– 要使 errorS(h)是 errorD(h)的无偏估计，假设 h和样本 S
必须独立选取
– 估计偏差不能与第 2章介绍的学习器的归纳偏置相混淆
估计量的另一重要属性是它的方差，给定多个无偏估计量，选取其中方差最小的
由方差的定义，所选择的应为参数值和估计值之间期望平方误差最小的
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
估计量、偏差和方差（ 4）
一个例子
– n=40个随机样例
– r=12个错误
– errorS(h)的标准差
一般地，若在 n个随机选取的样本中有 r
个错误,errorS(h)的标准差是：
近似地
n ppnrherro rS )1()(
n he r r o rhe r r o r SShe r r o rS ))(1)(()(
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
置信区间
通常描述某估计的不确定性的方法是使用置信区间，
真实的值以一定的概率落入该区间中，这样的估计称为置信区间估计
定义：某个参数 p的 N%置信区间是一个以 N%的概率包含 p的区间
由于估计量 errorS(h)服从二项分布，这一分布的均值为
errorD(h)，标准差可由式 5.9计算，因此，为计算 95%置信区间，只需要找到一个以 errorD(h)为中心的区间，它的宽度足以包含该分布全部概率的 95%
这提供了一个包围 errorD(h)的区间，使 errorS(h)有 95%
机会落入其中，同样它也指定了 errorD(h)有 95%的机会落入包围 errorS(h)的区间的大小
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
置信区间（ 2）
对于二项分布，计算置信区间很烦琐，多数情况下，计算它的近似值
对于足够大的样本，二项分布可以由正态分布来近似，而正态分布的置信区间容易得到
如果随机变量 Y服从均值为?，标准差为?的一个正态分布，那么 Y的任一观察值 y有 N%的机会落入下面的区间
相似地，均值?有 N%的机会落入下面的区间
Nz?
Nzy?
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
置信区间（ 3）
式子 5.1的三步推导过程
– errorS(h)遵从二项分布，其均值为 errorD(h)，标准差如式 5.9所示
– 对于足够大的样本 n，二项分布非常近似于正态分布
– 式 5.11告诉我们如何根据正态分布的均值求出 N%置信区间
式子 5.1的推导中有两个近似
– 估计 errorS(h)的标准差，我们将 errorD(h)近似为 errorS(h)
– 用正态分布近似二项分布
统计学的一般规则表明，这两个近似在 n>=30或 np(1-
p)>=5时工作得很好，对于较小的 n值，最好使用列表的形式给出二项分布的具体值
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
双侧和单侧边界
上述的置信区间是双侧的，有时用到单侧边界
例如问题,errorD(h)至多为 U的概率”，在只要限定 h
的最大错误率，而不在乎真实错误率是否小于估计错误率时，很自然提出这种问题
由于正态分布关于其均值对称，因此，任意正态分布上的双侧置信区间能够转换为相应的单侧区间，置信度为原来的两倍（见图 5-1b）
由一个有下界 L和上界 U的 100(1-?)%置信区间，可得到一个下界为 L且无上界的 100(1-?/2)%置信区间，也得到一个有上界 U且无下界的 100(1-?/2)%置信区间
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
推导置信区间的一般方法
前面介绍的是针对一特定情况推导置信区间估计：基于独立抽取的 n个样本，估计离散值假设的 errorD(h)
本节介绍的方法是在许多估计问题中用到的通用的方法
基于大小为 n的随机抽取样本的均值，来估计总体均值的问题
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
通用的过程的步骤
确定基准总体中要估计的参数 p，例如 errorD(h)
定义一个估计量 Y（如 errorS(h)），它的选择应为最小方差的无偏估计量
确定控制估计量 Y的概率分布 DY，包括其均值和方差
通过寻找阈值 L和 U确定 N%置信区间，以使这个按 DY分布的随机变量有 N%机会落入 L和 U之间
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
中心极限定理
考虑如下的一般框架
– 在 n个独立抽取的且服从同样概率分布的随机变量
Y1...Yn中观察试验值
– 令?代表每一变量 Yi服从的未知分布的均值，并令?
代表标准差，称这些变量 Yi为独立同分布随机变量
– 为了估计 Yi服从的分布的均值?，我们计算样本的均值
– 中心极限定理说明在 n时，所服从的概率分布为一正态分布，而不论 Yi本身服从什么样的分布
– 服从的分布均值为?，而标准差为
ni in YnY 11
nY
nY n
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
中心极限定理（ 2）
定理 5.1（中心极限定理）考虑独立同分布的随机变量 Y1...Yn的集合，它们服从一任意的概率分布，均值为?，有限方差为?2，定义样本均值为,当 n时，式子 服从正态分布，
均值为 0且标准差为 1
中心极限定理说明在不知道独立的 Yi所服从的基准分布的情况下，我们可以得知样本均值的分布形式，说明了怎样使用 的均值和方差来确定独立的 Yi的均值和方差
中心极限定理说明了任意样本均值的估计量服从的分布在 n足够大时可以近似为正态分布
ni in YnY 11
n
Yn
YY
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
两个假设错误率间的差异
问题：
– 考虑某离散目标函数的两个假设 h1和 h2,h1
在一拥有 n1个随机抽取的样例的样本 S1上测试,h2在一拥有 n2个从相同分布中抽取的样例的样本 S2上测试，要估计这两个假设的真实错误率间的差异
d=errorD(h1)-errorD(h2)
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
两个假设错误率间的差异（ 2）
使用 5.4节中描述的四个步骤来推导 d的置信区间估计
– 确定待估计的参数，如上所述的 d
– 定义一估计量，
– 是 d的无偏估计量，即 E[ ]=d。由于对于较大的 n1
和 n2,errorS1(h1)和 errorS2(h2)都近似遵从正态分布，
两个正态分布的差仍为正态分布，方差为两个正态分布的方差的和
– 现在知道了 服从均值为 d、方差为?2的正态分布，
因此 d的 N%置信区间是
)()(? 21 21 herro rherro rd SS
d? d?
2
22
1
112? ))(1)(())(1)(( 2211 n he r r o rhe r r o rn he r r o rhe r r o r SSSSd
d?
Nzd
d?
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 35
两个假设错误率间的差异（ 3）
上面分析的是 h1和 h2在相互独立的数据样本上测试的情况，如果在同一个样本上测试 h1和 h2，
那么也可以使用公式 5.13计算置信区间
这种情况下的方差通常小于式子 5.12给出的方差，这是因为单个样本消除了两个样本组合带来的随机差异，这样，由式子 5.13给出的置信区间一般来说偏于保守，但结果是正确的
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 36
假设检验
有时感兴趣的是某个特定猜想正确的概率，而不是对某参数的置信区间估计。比如：
errorD(h1)>errorD(h2)的可能性有多大？
例子，假定分别用大小为 100的独立样本 S1和
S2测量 h1和 h2的样本错误率为 0.30和 0.20，给定,问 errorD(h1)>errorD(h2)的概率是多少？
d>0的概率是多少？
概率 Pr(d>0)等于 对 d的过高估计不大于 0.1的概率，也就是这个概率为 落入单侧区间
<d+0.10= +0.10的概率
10.0d
d?
d?
d? d
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 37
假设检验（ 2）
对于 落入单侧区间 < +0.10的概率，可以通过计算分布在该区间的概率质量来确定 落入这个单侧区间的概率
将区间 < +0.10用允许偏离均值的标准差的数目来重新表示，根据式 5.12可得?0.061，所以这一区间可近似表示为
查表 5-1知，关于均值的 1.64标准差对应置信度 90%的双侧区间，因此这个单侧区间具有 95%的置信度
因此给定观察 =0.1,errorD(h1)>errorD(h2)的概率约为
95%。使用统计学术语表述为：接受
errorD(h1)>errorD(h2)假设的置信度是 95%
d? d? d
d?
d? d
d
dddddd 64.110.0
d?
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 38
学习算法比较
有时感兴趣的是比较两个学习算法的性能，而不是两个具体的假设本身
– 如何近似地检验多个学习算法？
– 如何确定两个算法之间的差异在统计上是有意义的？
假定有 LA和 LB两个算法，要确定为了学习一特定目标函数 f，平均来说那个算法更好
定义“平均”的一种合理方法是，从一基准实例分布中抽取包含 n个样例的训练集合，在所有这样的集合中测量两个算法的平均性能，即
) ) ](())(([ SLe r r o rSLe r r o rE BDADDS
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 39
学习算法比较（ 2）
在实际的学习算法比较中，我们只有一个有限的样本
D0，把它分割成训练集合 S0和测试集合 T0，使用下式比较两个学习到的假设的准确度
上式与 5.14有两个重要的不同
– 使用 errorT0(h)来近似 errorD(h)
– 错误率的差异测量是在一个训练集合 S0上，而不是在从分布 D
中抽取的所有样本 S上计算的期望值
改进 5.15式的一种方法是，将数据 D0多次分割为不相交的训练和测试集合，然后在其中计算这些不同的实验的错误率的平均值，见表 5-5
))(())(( 00 00 SLe rrorSLe rror BTAT?
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 40
学习算法比较（ 3）
表 5-5返回的 可被用作对公式 5.14的一个估计，更合适的说法是把 看作下式的估计
估计式 5.17的近似的 N%置信区间可表示成,其中
tN,k-1是一常数，其意义类似于前面的 zN，第一个下标表示所需的置信度，第二个下标表示自由度，常记作 v，
它与生成随机变量的值时独立的随机事件数目相关。
而 代表 所服从的概率分布的标准差的估计，定义如下
注意当自由度 v时,tN,v的值趋向常数 zN。
) ) ](())(([0 SLe rro rSLe rro rE BDADDS
st kN 1,
ki ikks 1 2)()1( 1
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 41
学习算法比较（ 4）
这里描述的比较学习算法的过程要在同样的测试集合上测试两个假设，这与 5.5节中描述的比较两个用独立测试集合评估过的假设不同。
使用相同样本来测试假设被称为配对测试，配对测试通常会产生更紧密地置信区间，因为在配对测试中任意的差异都来源于假设之间的差异。
若假设在分开的数据样本上的测试，两个样本错误率之间的差异也可能部分来源于两个样本组成的不同。
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 42
配对 t测试
本节讨论给定固定数据集时比较两个学习算法的过程，并论证公式 5.18和 5.19
为了理解 5.18中的置信区间，考虑一下的估计问题
– 给定一系列独立同分布的随机变量 Y1…Yk
的观察值
– 要估计这些 Yi所服从的概率分布的均值?
– 使用的估计量为样本均值?
k
i YikY 1
1
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 43
配对 t测试（ 2）
这一基于样本均值估计分布均值的问题非常普遍（比如，早先的用 errorS(h)估计 errorD(h)）
由式 5.18和 5.19描述的 t测试应用于该问题的一特殊情形，即每个单独的 Yi都遵循正态分布
考虑表 5-5比较学习算法的过程的一个理想化形式，假定不是拥有固定样本数据 D0，而是从基准实例分布中抽取新的训练样例，使每一次循环需要的训练集 Si和测试集 Ti是从基准实例分布中抽取
这一理想化方法能很好地匹配上面的估计问题，该过程所测量的?i对应独立同分布的随机变量 Yi，其分布的均值?对应两学习算法错误率的期望差异。
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 44
配对 t测试（ 3）
测试集 Ti至少包含 30个样例，因此，单独的?i将近似遵循正态分布，因此，我们也要求 Yi服从近似的正态分布，样本均值 也遵循正态分布
由此，可以考虑使用前面的计算置信区间的表达式。
然而，该公式要求我们知道这个分布的标准差，但这个标准差未知
t测试正好用于这样的情形，即估计一系列独立同正态分布的随机变量的样本均值
当 k趋近于无穷时,t分布趋近于正态分布，即 tN,k-1趋近于正态分布，因为样本规模 k增加时,收敛到真实的标准差，并且当标准差确切已知时可使用 zN。
Y
Ys
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 45
实际考虑
上面的讨论说明了在使用样本均值来估计一个包含 k个独立同正态分布的随机变量的样本均值时，可使用式
5.18来估计置信区间
这个结论假定对于目标函数的样例可进行无限存取，
实际问题是随机变量之间并不独立，因为它们基于从有限子集中抽取的相互重叠的训练样例
当只有一个有限的数据样本可用时，有几种重叠采用的方法。
– 表 5-5描述了 k-fold方法
– 随机抽取至少有 30个样例的测试集合，剩余样例组成训练集合，重复这一过程直到足够的次数
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 46
实际考虑（ 2）
随机方法的好处是能够重复无数次，以减少置信区间到需要的宽度，而 k-fold方法受限于样例的总数
随机方法的缺点是，测试集合不再被看作是从基准实例分布中独立抽取，而 k-fold交叉验证生成的测试集合是独立的，因为一个实例只在测试集合中出现一次
概括而言，统计学模型在数据有限时很少能完美地匹配学习算法验证中的所有约束。然而，
它们确实提供了近似的置信区间。
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 47
小结
统计理论提供了一个基础，从而基于在数据样本 S上的观察错误率，估计真实错误率。
估计置信区间的问题可通过一待估计的参数以及相对应的估计量来完成。由于估计量是一个随机变量，它可由其服从的概率分布来描述。
置信区间的计算可通过确定该分布下包含所需概率质量的区间来描述。
估计假设精度中的一种可能误差为估计偏差。
如果 Y为对某参数 p的估计量,Y的估计偏差为
Y的期望值和 p之间的差
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 48
小结（ 2）
估计产生误差的第二种原因是估计方差。即使对于无偏估计，估计量的观察值也可能在各实验中不同，估计量分布的方差描述了该估计与真实值的不同有多大。
方差在数据样本增大时降低。
比较两个学习算法效果的问题在数据和时间无限时是一个相对容易的估计问题，但在资源有限时要困难得多。本章描述的一种途径是在可用数据的不同子集上运行学习算法，在剩余数据上测试学到的假设，然后取这些结果的平均值。
本章考虑的多数情况中，推导置信区间需要多个假定和近似。近似计算分布的方差，以及假定实例从一固定不变的概率分布中生成。
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 49
补充读物
Billingsley et al.提供了对统计学的一个很简明的介绍，详尽讨论本章涉及的一些问题
DeGroot,Casella & Berger,Duda & Hart在数值模式识别领域提出了对这些问题的解决方法
Segre et al.,Etzioni & Etzioni,Gordon & Segre
讨论了评估学习算法的统计意义测试
Geman et al.讨论了在同时最小化偏差和最小化方差之间作出的折中。 Dietterich讨论了在不同训练测试数据分割下使用配对差异 t测试带来的风险
机器学习第 5章 评估假设
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
对假设的精度进行评估是机器学习中的基本问题
本章介绍用统计方法估计假设精度，主要解决以下三个问题：
– 已知一个假设在有限数据样本上观察到的精度，怎样估计它在其他实例上的精度？
– 如果一个假设在某些数据样本上好于另一个，那么一般情况下该假设是否更准确？
– 当数据有限时，怎样高效地利用这些数据，通过它们既能学习到假设，还能估计其精度？
统计的方法，结合有关数据基准分布的假定，使我们可以用有限数据样本上的观察精度来逼近整个数据分布上的真实精度
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
动机
对学习到的假设进行尽可能准确地性能评估十分重要
– 为了知道是否可以使用该假设
– 是许多学习方法的重要组成部分
当给定的数据集有限时，要学习一个概念并估计其将来的精度，存在两个很关键的困难：
– 估计的困难
使用与训练样例和假设无关的测试样例
– 估计的方差
即使假设精度在独立的无偏测试样例上测量，得到的精度仍可能与真实精度不同。
测试样例越少，产生的方差越大
本章讨论了对学到的假设的评估、对两个假设精度的比较、两个学习算法精度的比较
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
学习问题的框架
有一所有可能实例的空间 X，其中定义了多个目标函数，我们假定 X中不同实例具有不同的出现频率。一种合适的建模方式是，假定存在一未知的概率分布 D，它定义了 X中每一实例出现的概率。
学习任务是在假设空间上学习一个目标概念，
训练样例的每一个实例按照分布 D独立地抽取，
然后连同正确的目标值提供给学习器。
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
评估假设的问题
给定假设 h和包含若干按 D分布抽取的样例的数据集，如何针对将来按同样分布抽取的实例，得到对 h的精度最好估计
这一精度估计的可能的误差是多少
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
样本错误率和真实错误率
定义：假设 h关于目标函数 f和数据样本 S的样本错误率（标记为 errors(h)）
定义：假设 h关于目标函数 f和分布 D的真实错误率（标记为 errorD(h)）
Sxs xhxfnhe rro r ))(),((1)(?
o th e r w is exhxfxhxf )()(01))(),((?
||Sn?
)]()([Pr)( xhxfhe rror DxD
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
样本错误率和真实错误率（ 2）
我们想知道的是假设的真实误差，因为这是在分类未来样例时可以预料到的误差。
我们所能测量的只是样本错误率，因为样本数据是我们知道的。
本节要考虑的问题是：样本错误率在何种程度上提供了对真实错误率的估计？
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
离散值假设的置信区间
先考虑离散值假设的情况，比如：
– 样本 S包含 n个样例，它们的抽取按照概率分布 D，
抽取过程是相互独立的，并且不依赖于假设 h
– n>=30
– 假设 h在这 n个样例上犯了 r个错误
根据上面的条件，统计理论可以给出以下断言：
– 没有其他信息的话，真实错误率 errorD(h)最可能的值是样本错误率 errorS(h)=r/n
– 有大约 95%的可能性，真实错误率处于下面的区间内：
n he r r o rhe r r o rhe r r o r SSS ))(1)((96.1)(
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
举例说明
数据样本 S包含 n=40个样例，并且假设 h在这些数据上产生了 r=12个错误，这样样本错误率为
errorS(h)=12/40=0.3
如果没有更多的信息，对真实错误率 errorD(h)的最好的估计即为 0.3
如果另外收集 40个随机抽取的样例 S’，样本错误率
errorS’(h)将与原来的 errorS(h)存在一些差别
如果不断重复这一实验，每次抽取一个包含 40样例的样本，将会发现约 95%的实验中计算所得的区间包含真实错误率
将上面的区间称为 errorD(h)的 95%置信区间估计
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
置信区间表达式的推广
常数 1.96是由 95%这一置信度确定的
定义 zN为计算 N%置信区间的常数（取值见表 5-
1），计算 errorD(h)的 N%置信区间的一般表达式（公式 5.1）为：
可以求得同样情况下的 68%置信区间，从直觉上可以看出 68%置信区间要小于 95%置信区间，
因为减小了要求 errorD(h)落入的概率
n he r r o rhe r r o rzhe r r o r SSNS ))(1)(()(
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
置信区间表达式的推广（ 2）
公式 5.1只能应用于离散值假设，它假定样本 S
抽取的分布与将来的数据抽取的分布相同，并且假定数据不依赖于所测试的假设
公式 5.1只提供了近似的置信区间，这一近似在至少包含 30个样例，并且 errorS(h)不太靠近 0或
1时很接近真实情况
判断这种近似是否接近真实的更精确规则是：
5))(1)(( he rro rhe rro rn SS
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
统计学中的基本定义和概念
随机变量
某随机变量 Y的概率分布
随机变量 Y的期望值或均值
随机变量的方差
Y的标准差
二项分布
正态分布
中心极限定理
估计量
Y的估计偏差
N%置信区间
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
错误率估计和二项比例估计
样本错误率和真实错误率之间的差异与数据样本大小的依赖关系如何？
给定从总体中随机抽取的某些样本的观察比例，估计某个属性在总体的比例
此处，我们感兴趣的属性是：假设 h对实例错误分类
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
错误率估计和二项比例估计（ 2）
测量样本错误率相当于在作一个有随机输出的实验
从分布 D中随机抽取 n个独立的实例，形成样本
S，然后测量样本错误率 errorS(h)
将实验重复多次，每次抽取大小为 n的不同的样本 Si，得到不同的,取决于 Si的组成中的随机差异
被称为一随机变量，一般情况下，可以将随机变量看成一个有随机输出的实验。随机变量值即为随机实验的观察输出
)(herroriS
)(herroriS
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
错误率估计和二项比例估计（ 3）
设想要运行 k个这样的随机实验，得到 k
个随机变量值，以图表的形式显示观察到的每个错误率值的频率
当 k不断增长，该图表将呈现如表 5-3所显示的分布，称为二项分布
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
二项分布
有一非均质硬币，要估计在抛硬币时出现正面的概率 p
投掷硬币 n次并计算出现正面的次数 r，那么 p的一个合理估计是 r/n
如果重新进行一次实验，生成一个新的 n次抛硬币的集合，出现正面的次数 r可能与前不同，
得到对 p的另一个估计
二项分布描述的是对任一可能的 r值，这个正面概率为 p的硬币抛掷 n次恰好出现 r次正面的概率
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
二项分布（ 2）
从抛掷硬币的随机样本中估计 p与在实例的随机样本上测试 h以估计 errorD(h)是相同的问题
一次硬币抛掷对应于从 D中抽取一个实例并测试它是否被 h误分类
一次随机抛掷出现正面的概率 p对应于随机抽取的实例被误分类的概率 errorD(h)
二项分布给出了一个一般形式的概率分布，无论用于表示 n次硬币出现正面的次数还是在 n个样例中假设出错的次数
二项分布的具体形式依赖于样本大小 n以及概率 p或
errorD(h)
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
应用二项分布的条件
有一基本实验，其输出可被描述为一随机变量
Y，随机变量 Y有两种取值
在实验的任一次尝试中 Y=1的概率为常数 p，它与其他实验尝试无关，因此 Y=0的概率为 1-p
p为预先未知，面临的问题是如何估计
基本实验的 n次独立尝试按序列执行，生成一个独立同分布的随机变量序列
随机变量 R表示 n次实验中出现 Yi=1的次数，它取特定值 r的概率由二项分布给出
rnr pprnr nrR )1()!(! !)Pr (
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
均值
期望值是重复采样随机变量得到的值的平均
定义：考虑随机变量 Y可能的取值为
y1...yn,Y的期望值 E[Y]定义如下：
如果随机变量 Y服从二项分布，那么可得
E[Y]=np
ni ii yYyYE 1 )P r(][
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
方差
方差描述的是概率分布的宽度或散度，描述了随机变量与其均值之间的差有多大
定义：随机变量 Y的方差 Var[Y]定义如下：
描述了从 Y的一个观察值估计其均值 E[Y]的误差平方的期望
随机变量 Y的标准差?Y
若随机变量 Y服从二项分布，则方差和标准差分别为：
Var[Y]=np(1-p)
]))([(][ 2YEYEYV ar
]])[[( 2YEYEY
)1( pnpY
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
估计量、偏差和方差
回到问题：我们得出了随机变量 errorS(h)服从二项分布，那么 errorS(h)和 errorD(h)之间可能的差异是多少？
用 5.2式定义的二项分布，可得
errorS(h)=r/n
errorD(h)=p
统计学中将 errorS(h)称为 errorD(h)的一个估计量
估计量是用来估计总体的某一参数的随机变量，
最关心的是它平均来说是否能产生正确估计
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
估计量、偏差和方差（ 2）
估计偏差衡量估计量的期望值同真实参数值之间的差异
定义：针对任意参数 p的估计量 Y的估计偏差是：
E[Y]-p
如果估计偏差为 0，称 Y为 p的无偏估计量，在此情况下，由多次重复实验生成的 Y的多个随机值的平均将收敛于 p
由于 errorS(h)服从二项分布，因此 errorS(h)是
errorD(h)的一个无偏估计量
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
估计量、偏差和方差（ 3）
对估计偏差的补充说明：
– 要使 errorS(h)是 errorD(h)的无偏估计，假设 h和样本 S
必须独立选取
– 估计偏差不能与第 2章介绍的学习器的归纳偏置相混淆
估计量的另一重要属性是它的方差，给定多个无偏估计量，选取其中方差最小的
由方差的定义，所选择的应为参数值和估计值之间期望平方误差最小的
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
估计量、偏差和方差（ 4）
一个例子
– n=40个随机样例
– r=12个错误
– errorS(h)的标准差
一般地，若在 n个随机选取的样本中有 r
个错误,errorS(h)的标准差是：
近似地
n ppnrherro rS )1()(
n he r r o rhe r r o r SShe r r o rS ))(1)(()(
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
置信区间
通常描述某估计的不确定性的方法是使用置信区间，
真实的值以一定的概率落入该区间中，这样的估计称为置信区间估计
定义：某个参数 p的 N%置信区间是一个以 N%的概率包含 p的区间
由于估计量 errorS(h)服从二项分布，这一分布的均值为
errorD(h)，标准差可由式 5.9计算，因此，为计算 95%置信区间，只需要找到一个以 errorD(h)为中心的区间，它的宽度足以包含该分布全部概率的 95%
这提供了一个包围 errorD(h)的区间，使 errorS(h)有 95%
机会落入其中，同样它也指定了 errorD(h)有 95%的机会落入包围 errorS(h)的区间的大小
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
置信区间（ 2）
对于二项分布，计算置信区间很烦琐，多数情况下，计算它的近似值
对于足够大的样本，二项分布可以由正态分布来近似，而正态分布的置信区间容易得到
如果随机变量 Y服从均值为?，标准差为?的一个正态分布，那么 Y的任一观察值 y有 N%的机会落入下面的区间
相似地，均值?有 N%的机会落入下面的区间
Nz?
Nzy?
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
置信区间（ 3）
式子 5.1的三步推导过程
– errorS(h)遵从二项分布，其均值为 errorD(h)，标准差如式 5.9所示
– 对于足够大的样本 n，二项分布非常近似于正态分布
– 式 5.11告诉我们如何根据正态分布的均值求出 N%置信区间
式子 5.1的推导中有两个近似
– 估计 errorS(h)的标准差，我们将 errorD(h)近似为 errorS(h)
– 用正态分布近似二项分布
统计学的一般规则表明，这两个近似在 n>=30或 np(1-
p)>=5时工作得很好，对于较小的 n值，最好使用列表的形式给出二项分布的具体值
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
双侧和单侧边界
上述的置信区间是双侧的，有时用到单侧边界
例如问题,errorD(h)至多为 U的概率”，在只要限定 h
的最大错误率，而不在乎真实错误率是否小于估计错误率时，很自然提出这种问题
由于正态分布关于其均值对称，因此，任意正态分布上的双侧置信区间能够转换为相应的单侧区间，置信度为原来的两倍（见图 5-1b）
由一个有下界 L和上界 U的 100(1-?)%置信区间，可得到一个下界为 L且无上界的 100(1-?/2)%置信区间，也得到一个有上界 U且无下界的 100(1-?/2)%置信区间
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
推导置信区间的一般方法
前面介绍的是针对一特定情况推导置信区间估计：基于独立抽取的 n个样本，估计离散值假设的 errorD(h)
本节介绍的方法是在许多估计问题中用到的通用的方法
基于大小为 n的随机抽取样本的均值，来估计总体均值的问题
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
通用的过程的步骤
确定基准总体中要估计的参数 p，例如 errorD(h)
定义一个估计量 Y（如 errorS(h)），它的选择应为最小方差的无偏估计量
确定控制估计量 Y的概率分布 DY，包括其均值和方差
通过寻找阈值 L和 U确定 N%置信区间，以使这个按 DY分布的随机变量有 N%机会落入 L和 U之间
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
中心极限定理
考虑如下的一般框架
– 在 n个独立抽取的且服从同样概率分布的随机变量
Y1...Yn中观察试验值
– 令?代表每一变量 Yi服从的未知分布的均值，并令?
代表标准差，称这些变量 Yi为独立同分布随机变量
– 为了估计 Yi服从的分布的均值?，我们计算样本的均值
– 中心极限定理说明在 n时，所服从的概率分布为一正态分布，而不论 Yi本身服从什么样的分布
– 服从的分布均值为?，而标准差为
ni in YnY 11
nY
nY n
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
中心极限定理（ 2）
定理 5.1（中心极限定理）考虑独立同分布的随机变量 Y1...Yn的集合，它们服从一任意的概率分布，均值为?，有限方差为?2，定义样本均值为,当 n时，式子 服从正态分布，
均值为 0且标准差为 1
中心极限定理说明在不知道独立的 Yi所服从的基准分布的情况下，我们可以得知样本均值的分布形式，说明了怎样使用 的均值和方差来确定独立的 Yi的均值和方差
中心极限定理说明了任意样本均值的估计量服从的分布在 n足够大时可以近似为正态分布
ni in YnY 11
n
Yn
YY
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
两个假设错误率间的差异
问题：
– 考虑某离散目标函数的两个假设 h1和 h2,h1
在一拥有 n1个随机抽取的样例的样本 S1上测试,h2在一拥有 n2个从相同分布中抽取的样例的样本 S2上测试，要估计这两个假设的真实错误率间的差异
d=errorD(h1)-errorD(h2)
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
两个假设错误率间的差异（ 2）
使用 5.4节中描述的四个步骤来推导 d的置信区间估计
– 确定待估计的参数，如上所述的 d
– 定义一估计量，
– 是 d的无偏估计量，即 E[ ]=d。由于对于较大的 n1
和 n2,errorS1(h1)和 errorS2(h2)都近似遵从正态分布，
两个正态分布的差仍为正态分布，方差为两个正态分布的方差的和
– 现在知道了 服从均值为 d、方差为?2的正态分布，
因此 d的 N%置信区间是
)()(? 21 21 herro rherro rd SS
d? d?
2
22
1
112? ))(1)(())(1)(( 2211 n he r r o rhe r r o rn he r r o rhe r r o r SSSSd
d?
Nzd
d?
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 35
两个假设错误率间的差异（ 3）
上面分析的是 h1和 h2在相互独立的数据样本上测试的情况，如果在同一个样本上测试 h1和 h2，
那么也可以使用公式 5.13计算置信区间
这种情况下的方差通常小于式子 5.12给出的方差，这是因为单个样本消除了两个样本组合带来的随机差异，这样，由式子 5.13给出的置信区间一般来说偏于保守，但结果是正确的
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 36
假设检验
有时感兴趣的是某个特定猜想正确的概率，而不是对某参数的置信区间估计。比如：
errorD(h1)>errorD(h2)的可能性有多大？
例子，假定分别用大小为 100的独立样本 S1和
S2测量 h1和 h2的样本错误率为 0.30和 0.20，给定,问 errorD(h1)>errorD(h2)的概率是多少？
d>0的概率是多少？
概率 Pr(d>0)等于 对 d的过高估计不大于 0.1的概率，也就是这个概率为 落入单侧区间
<d+0.10= +0.10的概率
10.0d
d?
d?
d? d
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 37
假设检验（ 2）
对于 落入单侧区间 < +0.10的概率，可以通过计算分布在该区间的概率质量来确定 落入这个单侧区间的概率
将区间 < +0.10用允许偏离均值的标准差的数目来重新表示，根据式 5.12可得?0.061，所以这一区间可近似表示为
查表 5-1知，关于均值的 1.64标准差对应置信度 90%的双侧区间，因此这个单侧区间具有 95%的置信度
因此给定观察 =0.1,errorD(h1)>errorD(h2)的概率约为
95%。使用统计学术语表述为：接受
errorD(h1)>errorD(h2)假设的置信度是 95%
d? d? d
d?
d? d
d
dddddd 64.110.0
d?
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 38
学习算法比较
有时感兴趣的是比较两个学习算法的性能，而不是两个具体的假设本身
– 如何近似地检验多个学习算法？
– 如何确定两个算法之间的差异在统计上是有意义的？
假定有 LA和 LB两个算法，要确定为了学习一特定目标函数 f，平均来说那个算法更好
定义“平均”的一种合理方法是，从一基准实例分布中抽取包含 n个样例的训练集合，在所有这样的集合中测量两个算法的平均性能，即
) ) ](())(([ SLe r r o rSLe r r o rE BDADDS
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 39
学习算法比较（ 2）
在实际的学习算法比较中，我们只有一个有限的样本
D0，把它分割成训练集合 S0和测试集合 T0，使用下式比较两个学习到的假设的准确度
上式与 5.14有两个重要的不同
– 使用 errorT0(h)来近似 errorD(h)
– 错误率的差异测量是在一个训练集合 S0上，而不是在从分布 D
中抽取的所有样本 S上计算的期望值
改进 5.15式的一种方法是，将数据 D0多次分割为不相交的训练和测试集合，然后在其中计算这些不同的实验的错误率的平均值，见表 5-5
))(())(( 00 00 SLe rrorSLe rror BTAT?
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 40
学习算法比较（ 3）
表 5-5返回的 可被用作对公式 5.14的一个估计，更合适的说法是把 看作下式的估计
估计式 5.17的近似的 N%置信区间可表示成,其中
tN,k-1是一常数，其意义类似于前面的 zN，第一个下标表示所需的置信度，第二个下标表示自由度，常记作 v，
它与生成随机变量的值时独立的随机事件数目相关。
而 代表 所服从的概率分布的标准差的估计，定义如下
注意当自由度 v时,tN,v的值趋向常数 zN。
) ) ](())(([0 SLe rro rSLe rro rE BDADDS
st kN 1,
ki ikks 1 2)()1( 1
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 41
学习算法比较（ 4）
这里描述的比较学习算法的过程要在同样的测试集合上测试两个假设，这与 5.5节中描述的比较两个用独立测试集合评估过的假设不同。
使用相同样本来测试假设被称为配对测试，配对测试通常会产生更紧密地置信区间，因为在配对测试中任意的差异都来源于假设之间的差异。
若假设在分开的数据样本上的测试，两个样本错误率之间的差异也可能部分来源于两个样本组成的不同。
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 42
配对 t测试
本节讨论给定固定数据集时比较两个学习算法的过程，并论证公式 5.18和 5.19
为了理解 5.18中的置信区间，考虑一下的估计问题
– 给定一系列独立同分布的随机变量 Y1…Yk
的观察值
– 要估计这些 Yi所服从的概率分布的均值?
– 使用的估计量为样本均值?
k
i YikY 1
1
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 43
配对 t测试（ 2）
这一基于样本均值估计分布均值的问题非常普遍（比如，早先的用 errorS(h)估计 errorD(h)）
由式 5.18和 5.19描述的 t测试应用于该问题的一特殊情形，即每个单独的 Yi都遵循正态分布
考虑表 5-5比较学习算法的过程的一个理想化形式，假定不是拥有固定样本数据 D0，而是从基准实例分布中抽取新的训练样例，使每一次循环需要的训练集 Si和测试集 Ti是从基准实例分布中抽取
这一理想化方法能很好地匹配上面的估计问题，该过程所测量的?i对应独立同分布的随机变量 Yi，其分布的均值?对应两学习算法错误率的期望差异。
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 44
配对 t测试（ 3）
测试集 Ti至少包含 30个样例，因此，单独的?i将近似遵循正态分布，因此，我们也要求 Yi服从近似的正态分布，样本均值 也遵循正态分布
由此，可以考虑使用前面的计算置信区间的表达式。
然而，该公式要求我们知道这个分布的标准差，但这个标准差未知
t测试正好用于这样的情形，即估计一系列独立同正态分布的随机变量的样本均值
当 k趋近于无穷时,t分布趋近于正态分布，即 tN,k-1趋近于正态分布，因为样本规模 k增加时,收敛到真实的标准差，并且当标准差确切已知时可使用 zN。
Y
Ys
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 45
实际考虑
上面的讨论说明了在使用样本均值来估计一个包含 k个独立同正态分布的随机变量的样本均值时，可使用式
5.18来估计置信区间
这个结论假定对于目标函数的样例可进行无限存取，
实际问题是随机变量之间并不独立，因为它们基于从有限子集中抽取的相互重叠的训练样例
当只有一个有限的数据样本可用时，有几种重叠采用的方法。
– 表 5-5描述了 k-fold方法
– 随机抽取至少有 30个样例的测试集合，剩余样例组成训练集合，重复这一过程直到足够的次数
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 46
实际考虑（ 2）
随机方法的好处是能够重复无数次，以减少置信区间到需要的宽度，而 k-fold方法受限于样例的总数
随机方法的缺点是，测试集合不再被看作是从基准实例分布中独立抽取，而 k-fold交叉验证生成的测试集合是独立的，因为一个实例只在测试集合中出现一次
概括而言，统计学模型在数据有限时很少能完美地匹配学习算法验证中的所有约束。然而，
它们确实提供了近似的置信区间。
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 47
小结
统计理论提供了一个基础，从而基于在数据样本 S上的观察错误率，估计真实错误率。
估计置信区间的问题可通过一待估计的参数以及相对应的估计量来完成。由于估计量是一个随机变量，它可由其服从的概率分布来描述。
置信区间的计算可通过确定该分布下包含所需概率质量的区间来描述。
估计假设精度中的一种可能误差为估计偏差。
如果 Y为对某参数 p的估计量,Y的估计偏差为
Y的期望值和 p之间的差
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 48
小结（ 2）
估计产生误差的第二种原因是估计方差。即使对于无偏估计，估计量的观察值也可能在各实验中不同，估计量分布的方差描述了该估计与真实值的不同有多大。
方差在数据样本增大时降低。
比较两个学习算法效果的问题在数据和时间无限时是一个相对容易的估计问题，但在资源有限时要困难得多。本章描述的一种途径是在可用数据的不同子集上运行学习算法，在剩余数据上测试学到的假设，然后取这些结果的平均值。
本章考虑的多数情况中，推导置信区间需要多个假定和近似。近似计算分布的方差，以及假定实例从一固定不变的概率分布中生成。
2003.12.18 机器学习 -评估假设 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 49
补充读物
Billingsley et al.提供了对统计学的一个很简明的介绍，详尽讨论本章涉及的一些问题
DeGroot,Casella & Berger,Duda & Hart在数值模式识别领域提出了对这些问题的解决方法
Segre et al.,Etzioni & Etzioni,Gordon & Segre
讨论了评估学习算法的统计意义测试
Geman et al.讨论了在同时最小化偏差和最小化方差之间作出的折中。 Dietterich讨论了在不同训练测试数据分割下使用配对差异 t测试带来的风险
