复试人工智能机器学习05

1、第5章 评估假设动机估计假设精度采样理论基础推导置信区间的一般方法两个假设错误率间的差异学习算法比较小结和补充读物第5章 评估假设对假设的精度进行评估是机器学习中的基本问题。用统计方法估计假设精度，主要为解决以下三个问题：1）已知一个假设在有限数据样本上观察到的精度，怎样估计它在其他实例上的精度？2）如果一个假设在某些数据样本上好于另一个，那么一般情况下该假设是否更准确？3）当数据有限时，怎样高效地利用这些数据，通过它们既能学到假设，还能估计其精度？5.1 动机对假设进行性能评估的原因包括：1）为了知道是否可以使用该假设2）对假设的评估是许多学习方法的重要的组成部分5.1 动机当数据十分充足时

2、，假设精度的估计相对容易。然而当给定的数据集非常有限时，要学习一个概念并估计其将来的精度，存在两个很关键的困难：1）估计的偏差（Bias in the estimate）。首先，学习到的概念在训练样例上的观察精度通常不能很好地用于估计将来样例上的精度。尤其在学习器采用了很大的假设空间并过度拟合训练样例时2）估计的方差（Variance in the estimate）。即使假设精度在独立的无偏测试样例上测量，得到的精度仍可能与真实精度不同，这取决于特定测试样例集合的组成。测试样例越少，产生的方差越大。5.2 估计假设精度在评估一个假设时，一般对估计这个假设对未来实例的分类的精度更感兴趣。同时，

3、也需要知道这一精度估计中的误差（即与此估计相联系的误差门限）学习问题的框架如下：有一所有可能实例的空间X（如所有人的集合），其上定义了若干个目标函数（如计划本年度购买滑雪板的人）。假定X不同实例具有不同的出现频率，一种合适的建模方式是，假定存在一未知的概率分布D，它定义了X中每一实例出现的概率（如19岁的人的概率比109岁的人的概率高）。注意D并没有说明x是一正例还是一反例，只确定了其出现概率。学习任务是在假设空间H上学习一个目标概念（即目标函数）f。目标函数f的训练样例由施教者提供给学习器：每一个实例按照分布D被独立地抽取，然后连同正确的目标值f(x)被提供给学习器。5.2 估计假设精度在一

4、般的框架中，感兴趣的是以下两个问题：1）给定假设h和包含若干按D分布随机抽取的样例的数据集，如何针对将来按同样分布抽取的实例，得到对h的精度的最好的估计？2）这一精度估计的可能的误差是多少？5.2.1 样本错误率和真实错误率需要确切地分出两种精度（或两种错误率）。其一是可用数据样本上该假设的错误率。其二是在分布为D的整个实例集合上该假设的错误率。它们分别被称为样本错误率和真实错误率。定义：假设h关于目标函数f和数据样本S的样本错误率（标记为errors(h)为：定义：假设h关于目标函数f和分布的真实错误率（标记为error (h)，为h按分布随机抽取实例被误分类的概率。本节所考虑的主要问题是e

5、rrors(h)在何种程度上提供了对error (h)的估计？5.2.2 离散值假设的置信区间基于某离散值假设h在样本S上观察到的样本错误率估计它的真实错误率。其中 样本S包含n个样例，它们的抽取按照概率分布，抽取过程是相互独立的，并且不依赖于h。 n=30 假设h在这n个样例上犯了r个错误（例如errors(h)=r/n)已知这些条件，统计理论可给出以下断言： 没有其他信息的话， error (h)最可能的值是errors(h) 有大约95%的可能性，真实错误率处于下面的区间内：5.2.2 离散值假设的置信区间上面的95%置信区间表达式可推广到一般情形以计算任意置信度。一般表达式为：该表达式

6、只提供了近似的置信区间，在至少包含30个样例并且样本错误率不太靠近0或1时很接近真实情况。判断这一近似是否接近真实，更精确的规则为n errors(h)(1- errors(h)=55.3 采样理论基础随机变量（random variable）可看作是有概率输出的一个实验的名字。它的值为实验的输出结果。某随机变量Y的概率分布（probability distribution）指定了取值为任一可能值yi的可能性Pr(Y=yi)随机变量Y的期望值（expected value）或均值（mean）为随机变量的方差（variance）为它描述了Y关于其均值分布的宽度或分散度5.3 采样理论基础Y的标准

7、差（Standard deviation）为通常用符号来表示正态分布（二项分布（Binominal distribution）是在硬币投掷问题中，若出现正面的概率为p，那么在n个独立的实验中出现r次正面的分布情况正态分布（Normal distribution）是一个钟形的概率分布，它在许多自然现象中都会出现。5.3 采样理论基础中心极限定理（Central limit theorem）：说明独立同分布的随机变量的总和遵循正态分布估计量（Estimator）为一个随机变量Y，它被用来估计一个基准总体的某一参数pY的估计偏差（estimation bias）作为p的估计量是（EY-p）。无偏估计

8、量是指该偏差为0N%置信区间（confidence interval）用于估计参数p，该区间包含p的概率为N%5.3.1 错误率估计和二项比例估计测量样本错误率相当于在作一个有随机输出的实验。我们先从分布中随机抽取n个独立的实例，形成样本S，然后测量样本错误率errors(h)。如果将实验重复多次，每次抽取大小为n的不同的样本Si，将可以得到不同的的值error Si(h)，它取决于不同Si组成中的随机差异。在这种情况下，第i个实验的输出error Si(h)被称为一随机变量（random variable）。一般情况下，可以将随机变量看成一个有随机输出的实验。随机变量值即为随机实验的观察输出

9、。当k不断增长，5-3表中描述的概率分布称为二项分布（Binomial distribution）5.3.2 二项分布二项分布描述的是对任一可能的r值（r从0到n），这个正面概率为p的硬币投掷n次恰好出现r次正面的概率。应用二项分布的条件包括：1）有一基本实验，其输出可被描述为一随机变量Y。随机变量Y有两种取值2）在实验的任一次尝试中Y=1的概率为常数p。它与其他的实验无关。一般p为预先未知的，面临的问题就在于如何估计它3）基本实验的n次独立尝试按序列执行，生成一个独立同分布的随机变量序列Y1, Y2, Yn，另R代表实验中出现Yi=1的次数。4）随机变量R取特定值r的概率由二项分布给出。5.

10、3.3 均值和方差定义：考虑随机变量Y可能的取值为y1, y2,yn，Y的期望值（expected value）EY为：定义：随机变量Y的方差（variance）VarY为：定义：随机变量Y的标准差（standard deviation）为：5.3.4 估计量、偏差和方差定义：针对任意参数p估计量Y的估计偏差为：如果估计偏差为0，称Y为p的无偏估计量（unbiased estimator）。在此情况下由多次重复实验生成的Y的多个随机值的平均（即EY)将收敛于p5.3.5 置信区间描述某估计的不确定性的方法是使用置信区间，真实的值以一定的概率落入该区间中。这样的估计成为置信区间（confiden

11、ce interval）估计。定义：某个参数p的N%置信区间是一个以N%的概率包含p的区间。5.3.6 双侧和单侧边界由一个有下界L和上界U的100(1-a)%置信区间，可得到一个下界为L且无上界的100(1-a/2)%置信区间，或得到一个上界为R且无下界的100(1-a/2)%置信区间。5.4 推导置信区间的一般方法前面介绍的是针对某一特定情况推导置信区间估计：基于独立抽取的n个样本，估计离散值假设的errorD(h)。这里介绍的方法是在许多估计问题中用到的通用的方法，将此看做是基于大小为n的随机抽取样本的均值，来估计总体均值的问题。通用的过程包括以下步骤：）确定基准总体中要估计的参数p，例

12、如errorD(h)）定义一个估计量Y（如errorS(h) ），它的选择应是最小方差的无偏估计量。）确定控制估计量Y的概率分布DY，包括其均值和方差。）通过寻找阀值L和U确定N%置信区间，以使这个按DY分布的随机变量有N%机会落入L和U之间。中心极限定理中心极限定理是简化置信区间推导的一个基本依据。考虑如下的一般框架：在n个独立抽取的且服从同样概率分布的随机变量Y1Yn中观察实验值（如一枚硬币的n次抛掷）。令代表每一变量Yi服从的未知分布的均值，并令代表标准差，称这些变量Yi为独立同分布（independent, identically distributed）随机变量。因为它们描述的是各自

13、独立且服从同样概率分布的实验。为估计Yi服从的分布的均值，计算样本的均值（如n次投掷硬币中出现正面的比例）中心极限定理说明在时所服从的概率分布为一正态分布，且不论Yi本身服从什么样的分布。中心极限定理考虑独立同分布的随机变量Y1Yn的集合，它们服从一任意的概率分布，均值为，有限方差为。定义样本均值则当时下面的式子服从正态分布，均值为且标准差为。结论令人吃惊，因为它说明在不知道独立的Yi所服从的基准分布的情况下，可以得知样本均值的分布形式。中心极限定理说明了怎样使用 的均值和方差来确定独立的Yi的均值和方差。中心极限定理中心极限定理是一个非常有用的结论，因为它表示任意样本均值的估计量（如erro

14、rS(h)为平均错误率）服从的分布在n足够大时可近似为正态分布。如果还知道这一近似的正态分布的方差，就可以计算置信区间。一个通常的规则是在n大于30时可使用这一近似5.6 两个假设错误率间的差异考虑对某离散目标函数有两个假设h1和h2。假设h1在一拥有n1个随机抽取的样本S1上测试，且h2在拥有n2个从相同分布中抽取的样例的样本S2上测试。假定要估计这两个假设的真实错误率间的差异：在确定d为待估计的参数后，下面要定义一估计量。显然，这里可选择样本错误率之间的差异作为估计量这里虽不加证明，但可以认为即为d的无偏估计量，即5.6 两个假设错误率间的差异随机变量服从的概率分布是什么？对于较大的n1和

15、n2，errorss1(h1)和 errorss2(h2)都近似遵从正态分布。由于两个正态分布的差仍为一正态分布，因此也近似遵从正态分布，均值为d。同时可得出分布的方差为两个方差的和：已经确定了估计量所服从的概率分布，很容易推导出置信区间以说明使用来估计d的可能误差。随机变量服从均值d方差的正态分布，其N%置信区间估计为5.6 两个假设错误率间的差异虽然上面的分析考虑的是h1和h2在相互独立的数据样本上测试的情况，但是在一个样本S（S仍然独立于h1和h2）上测试h1和h2并计算置信区间也是可接受的。被重新定义为：当用S来代替S1和S2时，新的的方差通常小于式中给出的方差。这是因为使用单个的样本

16、S消除了由S1和S2组合带来的随机差异假设检验我们感兴趣的是某个特定的猜想正确的概率，而不是对某参数的置信区间的估计。比如下面的问题errorD(h1) errorD(h2)的可能性多大？假定要测量h1和h2的样本错误率，使用大小为100的独立样本S1和S2，并且知道errorsS1(h1)0.3和errorsS2(h2)0.2，因此差异为0.1。当然，由于数据样本的随机性，即使errorsD(h1) errorsD(h2)的概率是多少？如何计算在=0.1时，d0的概率？假设检验概率Pr(d0)等于对d的过高估计不大于0.1的概率，也就是这个概率为落入单侧区间 errorD(h2)这一假设，置

17、信度为0.95。5.6 学习算法比较我们感兴趣的是比较两个学习算法LA和LB的性能，而不是具体的两个假设本身。怎样近似地检验多个学习算法，如何确定两个算法之间的差异在统计学上是有意义的？在机器学习领域，关于学习算法比较哪个方法最好仍存在激烈的争论。通常，先指定要估计的参数，假定有LA和LB两个算法，要确定为了学习一特定目标函数f，平均来说哪个算法最好。定义“平均”的一种合理方法是，从一基准实例分布D中抽取包含n个样例的训练集合，在所有这样的集合中测量两个算法的平均性能。换句话说，需要估计假设错误率之间差异的期望值：其中L(S)代表在给定训练数据的样本S时，学习算法L输出的假设。下标表示期望值是

18、在基准分布D中抽取的样本S上计算。5.6 学习算法比较在实际的学习算法比较中，只有一个有限的样本D0。在这种情况下，需要将D0分割成训练集合S0和与之不相交的测试集合T0 。训练数据既可以用来训练LA ，又训练LB 。而测试数据则用来比较两个学习到的假设的准确度。一种改进的方法是将数据D0多次分割为不相交的训练和测试集合，然后在其中计算这些不同的试验的错误率的平均值。该过程首先将数据拆分为k个不相交的相等子集，子集的大小至少为30，然后训练和测试算法k次，每次使用其中一个子集作为测试数据集，其他k-1个子集为训练集。使用这种方法，学习算法在k个独立测试集上测试，而把错误率的差异的均值作为学习算法间差异的估计。5.6 学习算法比较估计两个学习算法LA和LB错误率差