最新计算学习理论未讲课件.ppt

1、2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏2概述 本章从理论上刻画了若干类型的机器学习问题中的困难和若干类型的机器学习算法的能力 这个理论要回答的问题是：在什么样的条件下成功的学习是可能的？在什么条件下某个特定的学习算法可保证成功运行？这里考虑两种框架：可能近似正确（PAC）确定了若干假设类别，判断它们能否从多项式数量的训练样例中学习得到 定义了一个对假设空间复杂度的自然度量，由它可以界定归纳学习所需的训练样例数目 出错界限框架 考查了一个学习器在确定正确假设前可能产生的训练错误数量2003.12.18机器学习-计算学习理论 作者：Mitc

2、hell 译者：曾华军等 讲者：陶晓鹏9问题框架X表示所有实例的集合，C代表学习器要学习的目标概念集合，C中每个目标概念c对应于X的某个子集或一个等效的布尔函数c:X0,1假定实例按照某概率分布D从X中随机产生学习器L在学习目标概念时考虑可能假设的集合H。在观察了一系列关于目标概念c的训练样例后，L必须从H中输出某假设h，它是对c的估计我们通过h在从X中抽取的新实例上的性能来评估L是否成功。新实例与训练数据具有相同的概率分布我们要求L足够一般，以至可以从C中学到任何目标概念而不管训练样例的分布如何，因此，我们会对C中所有可能的目标概念和所有可能的实例分布D进行最差情况的分析2003.12.18

3、机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏10假设的错误率 为了描述学习器输出的假设h对真实目标概念的逼近程度，首先要定义假设h对应于目标概念c和实例分布D的真实错误率 h的真实错误率是应用h到将来按分布D抽取的实例时的期望的错误率 定义：假设h的关于目标概念c和分布D的真实错误率为h误分类根据D随机抽取的实例的概率)()(Pr)(xhxcherrorDxD2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏11假设的错误率（2）图7-1：h关于c的错误率是随机选取的实例落入h和c不一致的区间的概率真实错误率紧密地依

4、赖于未知的概率分布D 如果D是一个均匀的概率分布，那么图7-1中假设的错误率为h和c不一致的空间在全部实例空间中的比例 如果D恰好把h和c不一致区间中的实例赋予了很高的概率，相同的h和c将造成更高的错误率h关于c的错误率不能直接由学习器观察到，L只能观察到在训练样例上h的性能训练错误率：指代训练样例中被h误分类的样例所占的比例问题：h的观察到的训练错误率对真实错误率产生不正确估计的可能性多大？2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏12PAC可学习性 我们的目标是刻画出这样的目标概念，它们能够从合理数量的随机抽取训练样例中通过合理的计算量

5、可靠地学习 对可学习性的表述 一种可能的选择：为了学习到使errorD(h)=0的假设h，所需的训练样例数 这样的选择不可行：首先要求对X中每个可能的实例都提供训练样例；其次要求训练样例无误导性 可能近似学习：首先只要求学习器输出错误率限定在某常数范围内的假设，其次要求对所有的随机抽取样例序列的失败的概率限定在某常数范围内 只要求学习器可能学习到一个近似正确的假设2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏13PAC可学习性（2）PAC可学习性的定义 考虑定义在长度为n的实例集合X上的一概念类别C，学习器L使用假设空间H。当对所有cC，X上的

6、分布D，和满足0,=1个独立随机抽取的样例，那么对于任意0=1，变型空间VSH,D不是-详尽的概率小于或等于：证明：令h1,.,hk为H中关于c的真实错误率大于的所有假设。当且仅当k个假设中至少有一个恰好与所有m个独立随机抽取样例一致时，不能使变型空间-详尽化。任一假设真实错误率大于，且与一个随机抽取样例一致的可能性最多为1-，因此，该假设与m个独立抽取样例一致的概率最多为(1-)m 由于已知有k个假设错误率大于，那么至少有一个与所有m个训练样例都不一致的概率最多为（当 ，则 ）meH|mmmeHHk|)1(|)1(10e12003.12.18机器学习-计算学习理论 作者：Mitchell 译

7、者：曾华军等 讲者：陶晓鹏19有限假设空间的样本复杂度（5）定理7.1基于训练样例的数目m、允许的错误率和H的大小，给出了变型空间不是-详尽的概率的上界 即它对于使用假设空间H的任意学习器界定了m个训练样例未能将所有“坏”的假设（错误率大于的假设）剔除出去的概率 利用上面的结论来确定为了减少此“未剔除”概率到一希望程度所需的训练样例数 由 解出m，得到 meH|)/1ln(|ln1Hm2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏20有限假设空间的样本复杂度（6）式子7.2提供了训练样例数目的一般边界，该数目的样例足以在所期望的值和程度下，使任

8、何一致学习器成功地学习到H中的任意目标概念 训练样例的数目m足以保证任意一致假设是可能（可能性为1-）近似（错误率为）正确的 m随着1/线性增长，随着1/和假设空间的规模对数增长 上面的界限可能是过高的估计，主要来源于|H|项，它产生于证明过程中在所有可能假设上计算那些不可接受的假设的概率和 在7.4节讨论一个更紧凑的边界以及能够覆盖无限大的假设空间的边界2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏21不可知学习和不一致假设 如果学习器不假定目标概念可在H中表示，而只简单地寻找具有最小训练错误率的假设，这样的学习器称为不可知学习器 式7.2基

9、于的假定是学习器输出一零错误率假设，在更一般的情形下学习器考虑到了有非零训练错误率的假设时，仍能找到一个简单的边界 令S代表学习器可观察到的特定训练样例集合，errorS(h)表示h的训练错误率，即S中被h误分类的训练样例所占比例 令hbest表示H中有最小训练错误率的假设，问题是：多少训练样例才足以保证其真实错误率errorD(hbest)不会多于+errorS(hbest)？（上一节问题是这个问题的特例）2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏22不可知学习和不一致假设（2）前面问题的回答使用类似定理7.1的证明方法，这里有必要引入一

10、般的Hoeffding边界 Hoeffding边界刻画的是某事件的真实概率及其m个独立试验中观察到的频率之间的差异 Hoeffding边界表明，当训练错误率errorS(h)在包含m个随机抽取样例的集合S上测量时，则 上式给出了一个概率边界，说明任意选择的假设训练错误率不能代表真实情况，为保证L寻找到的最佳的假设的错误率有以上的边界，我们必须考虑这|H|个假设中任一个有较大错误率的概率22)()(PrmSDeherrorherror22|)()(PrmSDeHherrorherrorHh2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏23不可知学

11、习和不一致假设（3）将上式左边概率称为，问多少个训练样例m才足以使维持在一定值内，求解得到 式7.3是式7.2的一般化情形，适用于当最佳假设可能有非零训练错误率时，学习器仍能选择到最佳假设hH的情形。)/1ln(|ln212Hm2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏24布尔文字的合取是PAC可学习的 我们已经有了一个训练样例数目的边界，表示样本数目为多少时才足以可能近似学习到目标概念，现在用它来确定某些特定概念类别的样本复杂度和PAC可学习性 考虑目标概念类C，它由布尔文字的合取表示。布尔文字是任意的布尔变量，或它的否定。问题：C是可P

12、AC学习的吗？若假设空间H定义为n个布尔文字的合取，则假设空间|H|的大小为3n，得到关于n布尔文字合取学习问题的样本复杂度140)05.0/1ln(3ln101.01)/1ln(3ln1nm2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏25布尔文字的合取是PAC可学习的（2）定理7.2：布尔合取式的PAC可学习性 布尔文字合取的类C是用Find-S算法PAC可学习的 证明：式7.4显示了该概念类的样本复杂度是n、1/和1/的多项式级，而且独立于size(c)。为增量地处理每个训练样例，Find-S算法要求的运算量根据n线性增长，并独立于1/、

13、1/和size(c)。因此这一概念类别是Find-S算法PAC可学习的。2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏26其他概念类别的PAC可学习性 无偏学习器（无归纳偏置）考虑一无偏概念类C，它包含与X相关的所有可教授概念，X中的实例定义为n个布尔值特征，则有 无偏的目标概念类在PAC模型下有指数级的样本复杂度nXCH2|22|)/1ln(2ln21nm2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏27其他概念类别的PAC可学习性（2）K项DNF和K-CNF概念 某概念类有多项式级的样本复杂

14、度，但不能够在多项式时间内被学习到 概念类C为k项析取范式（k项DNF）的形式 k项DNF：T1.Tk，其中每一个Ti为n个布尔属性和它们的否定的合取 假定H=C，则|H|最多为3nk，代入式7.2，得到 因此，k项DNF的样本复杂度为1/、1/、n和k的多项式级 但是计算复杂度不是多项式级，该问题是NP完全问题（等效于其他已知的不能在多项式时间内解决的问题）因此，虽然k项DNF有多项式级的样本复杂度，它对于使用H=C的学习器没有多项式级的计算复杂度)/1ln(3ln1nkm2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏28其他概念类别的PAC

15、可学习性（3）令人吃惊的是，虽然k项DNF不是PAC可学习的，但存在一个更大的概念类是PAC可学习的 这个更大的概念类是K-CNF，它有每样例的多项式级时间复杂度，又有多项式级的样本复杂度 K-CNF：任意长度的合取式T1.Tj，其中每个Ti为最多k个布尔变量的析取 容易证明K-CNF包含了K项DNF，因此概念类k项DNF是使用H=K-CNF的一个有效算法可PAC学习的2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏29无限假设空间的样本复杂度 式子7.2用|H|刻画样本复杂度有两个缺点：可能导致非常弱的边界 对于无限假设空间的情形，无法应用 本

16、节考虑H的复杂度的另一种度量，称为H的Vapnik-Chervonenkis维度（简称VC维或VC(H)）使用VC维代替|H|也可以得到样本复杂度的边界，基于VC维的样本复杂度比|H|更紧凑，另外还可以刻画无限假设空间的样本复杂度2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏30打散一个实例集合 VC维衡量假设空间复杂度的方法不是用不同假设的数量|H|，而是用X中能被H彻底区分的不同实例的数量 S是一个实例集，H中每个h导致S的一个划分，即h将S分割为两个子集xS|h(x)=1和xS|h(x)=0 定义：一实例集S被假设空间H打散，当且仅当对S

17、的每个划分，存在H中的某假设与此划分一致 如果一实例集合没有被假设空间打散，那么必然存在某概念可被定义在实例集之上，但不能由假设空间表示 H的这种打散实例集合的能力是其表示这些实例上定义的目标概念的能力的度量2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏31Vapnik-Chervonenkis维度 打散一实例集合的能力与假设空间的归纳偏置紧密相关 无偏的假设空间能够打散所有实例组成的集合X 直观上，被打散的X的子集越大，H的表示能力越强 定义：定义在实例空间X上的假设空间H的Vapnik-Chervonenkis维，是可被H打散的X的最大有限

18、子集的大小 如果X的任意有限大的子集可被H打散，则VC(H)=2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏32Vapnik-Chervonenkis维度（2）对于任意有限的H，VC(H)=2，任意学习器L，以及任意01/8，0)/13(log)(8)/2(log4122HVCm321)(),/1log(1maxCVC2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏35样本复杂度和VC维（2）定理7.3说明，若训练样例的数目太少，那么没有学习器能够以PAC模型学习到任意非平凡的C中每个目标概念 式

19、子7.7给出了保证充足数量的上界，而定理7.3给出了下界2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏36神经网络的VC维 本节给出一般性的结论，以计算分层无环网络的VC维。这个VC维可用于界定训练样例的数量，该数达到多大才足以按照希望的和值近似可能正确地学习一个前馈网络 考虑一个由单元组成的网络G，它形成一个分层有向无环图 分层有向无环图的特点：节点可划分成层，即所有第l层出来的有向边进入到第l+1层节点 没有有向环，即有向弧形成的回路 这样网络的VC维的界定可以基于其图的结构和构造该图的基本单元的VC维2003.12.18机器学习-计算学习

20、理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏37神经网络的VC维（2）定义一些术语 G表示神经网络 n是G的输入数目 G只有1个输出节点 G的每个内部单元Ni最多有r个输入，并实现一布尔函数ci:Rr0,1，形成函数类C 定义C的G-合成：网络G能实现的所有函数的类，即网络G表示的假设空间，表示成CG2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏38神经网络的VC维（3）定理7.4分层有向无环网络的VC维（Kearns&Vazirani 1994）令G为一分层有向无环图，有n个输入节点和s2个内部节点，每个至少有r个输入，令C为V

21、C维为d的Rr上的概念类，对应于可由每个内部节点s描述的函数集合，令CG为C的G合成，对应于可由G表示的函数集合，则VC(CG)=2dslog(es)2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏39神经网络的VC维（4）假定要考虑的分层有向无环网络中单个节点都是感知器，由于单独的r输入感知器VC维为r+1，代入定理7.4和式子7.7，得到 上面的结果不能直接应用于反向传播的网络，原因有两个：此结果应用于感知器网络，而不是sigmoid单元网络 不能处理反向传播中的训练过程)log()1(2)(essrCVCsperceptronG)/13lo

22、g()log()1(16)/2log(4(1essrm2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏40学习的出错界限模型 计算学习理论考虑多种不同的问题框架 训练样例的生成方式（被动观察、主动提出查询）数据中的噪声（有噪声或无噪声）成功学习的定义（必须学到正确的目标概念还是有一定的可能性和近似性）学习器所做得假定（实例的分布情况以及是否CH）评估学习器的度量标准（训练样例数量、出错数量、计算时间）2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏41学习的出错界限模型（2）机器学习的出错界限模型

23、学习器的评估标准是它在收敛到正确假设前总的出错数 学习器每接受到一个样例x，先预测目标值c(x)，然后施教者给出正确的目标值 考虑的问题是：在学习器学习到目标概念前，它的预测会有多少次出错 下面讨论中，只考虑学习器确切学到目标概念前出错的次数，确切学到的含义是x h(x)=c(x)2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏42Find-S算法的出错界限 Find-S算法的一个简单实现 将h初始化为最特殊假设l1l1.lnln 对每个正例x 从h中移去任何不满足x的文字 输出假设h 计算一个边界，以描述Find-S在确切学到目标概念c前全部的

24、出错次数 Find-S永远不会将一反例错误地划分为正例，因此只需要计算将正例划分为反例的出错次数 遇到第一个正例，初始假设中2n个项半数被删去，对后续的被当前假设误分类的正例，至少有一项从假设中删去 出错总数至多为n+12003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏43Halving算法的出错界限 学习器对每个新实例x做出预测的方法是：从当前变型空间的所有假设中取多数票得来 将变型空间学习和用多数票来进行后续预测结合起来的算法称为Halving算法 Halving算法只有在当前变型空间的多数假设不能正确分类新样例时出错，此时变型空间至少可减少到

25、它的一半大小，因此出错界线是log2|H|Halving算法有可能不出任何差错就确切学习到目标概念，因为即使多数票是正确的，算法仍将移去那些不正确、少数票假设 Halving算法的一个扩展是允许假设以不同的权值进行投票（如贝叶斯最优分类器和后面讨论的加权多数算法）2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏44最优出错界限 问题：对于任意概念类C，假定H=C，最优的出错边界是什么？最优出错边界是指在所有可能的学习算法中，最坏情况下出错边界中最小的那一个 对任意学习算法A和任意目标概念c，令MA(c)代表A为了确切学到c，在所有可能训练样例序列

26、中出错的最大值 对于任意非空概念类C，令MA(C)=maxcCMA(c)定义：C为任意非空概念类，C的最优出错界限定义为Opt(C)是所有可能学习算法A中MA(C)的最小值)(min)(学习CMCOptAA算法2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏45最优出错界限（2）非形式地说，Opt(C)是C中最难的那个目标概念使用最不利的训练样例序列用最好的算法时的出错次数 Littlestone1987证明了|log)()()(2CCMCOptCVCHalving2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等

27、 讲者：陶晓鹏46加权多数算法 Halving算法的更一般形式称为加权多数算法 加权多数算法通过在一组预测算法中进行加权投票来作出预测，并通过改变每个预测算法的权来学习 加权多数算法可以处理不一致的训练数据，因为它不会消除与样例不一致的假设，只是降低其权 要计算加权多数算法的出错数量边界，可以用预测算法组中最好的那个算法的出错数量2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏47加权多数算法（2）加权多数算法一开始将每个预测算法赋予权值1，然后考虑训练样例，只要一个预测算法误分类新训练样例，它的权被乘以某个系数，0=0，则没有一个预测算法会被完

28、全去掉。如果一算法误分类一个样例，那么它的权值变小2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏48加权多数算法（3）ai代表算法池A中第i个预测算法，wi代表与ai相关联的权值 对所有i，初始化wi1 对每个训练样例做：初始化q0和q1为0 对每个预测算法ai 如果ai(x)=0，那么q0q0+wi 如果ai(x)=1，那么q1q1+wi 如果q1q0，那么预测c(x)=1 如果q0q1，那么预测c(x)=0 如果q0=q1，那么对c(x)随机预测为0或1 对每个预测算法ai 如果ai(x)c(x)，那么wiwi2003.12.18机器学习-

29、计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏49加权多数算法（4）定理7.5：加权多数算法的相对误差界限 令D为任意的训练样例序列，令A为任意n个预测算法集合，令k为A中任意算法对样例序列D的出错次数的最小值。那么使用=1/2的加权多数算法在D上出错次数最多为：2.4(k+log2n)证明：可通过比较最佳预测算法的最终权和所有算法的权之和来证明。令aj表示A中一算法，并且它出错的次数为最优的k次，则与aj关联的权wj将为(1/2)k。A中所有n个算法的权的和 ，W的初始值为n，对加权多数算法的每次出错，W被减小为最多 ，其原因是加权投票占少数的算法最少拥有整个权W的一半值

30、，而这一部分将被乘以因子1/2。令M代表加权多数算法对训练序列D的总出错次数，那么最终的总权W最多为n(3/4)M 由 ，得意义：加权多数算法的出错数量不会大于算法池中最佳算法出错数量，加上一个随着算法池大小对数增长的项，再乘以一常数因子niiwW1W43Mkn4321)log(4.2)43(log)log(222nknkM2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏50小结 可能近似正确模型（PAC）针对的算法从某概念类C中学习目标概念，使用按一个未知但固定的概念分布中随机抽取的训练样例，它要求学习器可能学习到一近似正确的假设，而计算量和训

31、练样例数都只随着1/、1/、实例长度和目标概念长度的多项式级增长 在PAC学习模型的框架下，任何使用有限假设空间H的一致学习器，将以1-的概率输出一个误差在内的假设，所需的训练样例数m满足|ln)/1ln(1Hm2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏51小结（2）不可知学习考虑更一般的问题：学习器不假定目标概念所在的类别，学习器从训练数据中输出H中有最小误差率的假设。学习保证以概率1-从H中最可能的假设中输出错误率小于的假设，需要的随机抽取的训练样例数目m满足 学习器考虑的假设空间的复杂度对所需样例的数目影响很大，而衡量假设空间复杂度的

32、一个有用的度量是VC维。VC维是可被H打散的最大实例集的大小|ln)/1ln(212Hm2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏52小结（3）在PAC模型下以VC(H)表示的足以导致成功学习的训练样例数目的上界和下界分别是：另一种学习模式称为出错界限模式，用于分析学习器在确切学习到目标概念之前会产生的误分类次数 Halving算法在学习到H中的任意目标概念前会有至多log2|H|次出错 对任意概念类C，最坏情况下最佳算法将有Opt(C)次出错，满足VC(C)=Opt(C)=log2|C|)/13(log)(8)/2(log4122HVCm

33、321)(),/1log(1maxCVCm2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏53小结（4）加权多数算法结合了多个预测算法的加权投票来分类新的实例，它基于这些预测算法在样例序列中的出错来学习每个算法的权值。加权多数算法产生的错误界限可用算法池中最佳预测算法的出错数来计算2003.12.18机器学习-计算学习理论 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏54补充读物计算学习理论中许多早期的工作针对的问题是：学习器能否在极限时确定目标概念Gold1967给出了极限模型下的确定算法Angluin1992给出了一个好的综述Vapnik1982详细考察了一致收敛Valiant1984给出了PAC学习模型Haussler1988讨论了-详尽变型空间Bluer et al.1989给出了PAC模型下的一组有用的结论Kearns&Vazirani1994提供了计算学习理论中许多结论的优秀的阐述会议：计算学习理论年会COLT杂志：机器学习的特殊栏目55 结束语结束语