人工智能课件-计算学习理论.pptVIP

Vapnik-Chervonenkis维度（2） 对于任意有限的H，VC(H)=log2|H| VC维举例 假定实例空间X为实数集合，而且H为实数轴上的区间的集合，问VC(H)是多少？ 只要找到能被H打散的X的最大子集，首先包含2个实例的集合能够被H打散，其次包含3个实例的集合不能被H打散，因此VC(H)=2 实例集合S对应x、y平面上的点，令H为此平面内所有线性决策面的集合，问H的VC维是多少？ 能够找到3个点组成的集合，被H打散，但无法找到能够被H打散的4个点组成的集合，因此VC(H)=3 更一般地，在r维空间中，线性决策面的VC维为r+1 * Vapnik-Chervonenkis维度（3） 假定X上每个实例由恰好3个布尔文字的合取表示，而且假定H中每个假设由至多3个布尔文字描述，问VC(H)是多少？ 找到下面3个实例的集合 instance1: 100 instance2: 010 instance3: 001 这三个实例的集合可被H打散，可对如下任意所希望的划分建立一假设：如果该划分要排除instancei，就将文字?li加入到假设中 此讨论很容易扩展到特征数为n的情况，n个布尔文字合取的VC维至少为n 实际就是n，但证明比较困难，需要说明n+1个实例的集合不可能被打散 * 样本复杂度和VC维 使用VC维作为H复杂度的度量，就有可能推导出该问题的另一种解答，类似于式子7.2的边界，即（Blumer el al. 1989） 定理7.3：样本复杂度的下界（Ehrenfeucht et al. 1989） 考虑任意概念类C，且VC(C)=2，任意学习器L，以及任意0?1/8，0?1/100。存在一个分布D以及C中一个目标概念，当L观察到的样例数目小于下式时： L将以至少?的概率输出一假设h，使errorD(h)? * 样本复杂度和VC维（2） 定理7.3说明，若训练样例的数目太少，那么没有学习器能够以PAC模型学习到任意非平凡的C中每个目标概念 式子7.7给出了保证充足数量的上界，而定理7.3给出了下界 * 神经网络的VC维 本节给出一般性的结论，以计算分层无环网络的VC维。这个VC维可用于界定训练样例的数量，该数达到多大才足以按照希望的?和?值近似可能正确地学习一个前馈网络 考虑一个由单元组成的网络G，它形成一个分层有向无环图 分层有向无环图的特点： 节点可划分成层，即所有第l层出来的有向边进入到第l+1层节点 没有有向环，即有向弧形成的回路 这样网络的VC维的界定可以基于其图的结构和构造该图的基本单元的VC维 * 神经网络的VC维（2） 定义一些术语 G表示神经网络 n是G的输入数目 G只有1个输出节点 G的每个内部单元Ni最多有r个输入，并实现一布尔函数ci:Rr?{0,1}，形成函数类C 定义C的G-合成：网络G能实现的所有函数的类，即网络G表示的假设空间，表示成CG * 神经网络的VC维（3） 定理7.4分层有向无环网络的VC维（Kearns Vazirani 1994） 令G为一分层有向无环图，有n个输入节点和s?2个内部节点，每个至少有r个输入，令C为VC维为d的Rr上的概念类，对应于可由每个内部节点s描述的函数集合，令CG为C的G合成，对应于可由G表示的函数集合，则VC(CG)=2dslog(es) * 神经网络的VC维（4） 假定要考虑的分层有向无环网络中单个节点都是感知器，由于单独的r输入感知器VC维为r+1，代入定理7.4和式子7.7，得到 上面的结果不能直接应用于反向传播的网络，原因有两个： 此结果应用于感知器网络，而不是sigmoid单元网络 不能处理反向传播中的训练过程 * 学习的出错界限模型 计算学习理论考虑多种不同的问题框架 训练样例的生成方式（被动观察、主动提出查询） 数据中的噪声（有噪声或无噪声） 成功学习的定义（必须学到正确的目标概念还是有一定的可能性和近似性） 学习器所做得假定（实例的分布情况以及是否C?H） 评估学习器的度量标准（训练样例数量、出错数量、计算时间） * 计算学习理论 * 概述 本章从理论上刻画了若干类型的机器学习问题中的困难和若干类型的机器学习算法的能力 这个理论要回答的问题是： 在什么样的条件下成功的学习是可能的？ 在什么条件下某个特定的学习算法可保证成功运行？ 这里考虑两种框架： 可能近似正确（PAC） 确定了若干假设类别，判断它们能否从多项式数量的训练样例中学习得到 定义了一个对假设空间复杂度的自然度量，由它可以界定归纳学习所需的训练样例数目 出错界限框架 考查了一个学习器在确定正确假设前可能产生的训练错误数量 * 简介 机器学习理论的一些问题： 是否可能独立于学习算法确定学习问题中固有的难度？ 能否知道为保证成功的学习有多少训练样例是