网站ip如何做跳转,重庆百度seo,下载页面设计图片,网站首页开发机器学习第十二章——计算学习理论 12.计算学习理论12.1 基础知识12.1 可能学习近似正确假设#xff08;PAC#xff09;12.3 有限假设空间12.4 VC维 12.计算学习理论
12.1 基础知识 从理论上刻画了若干类型的机器学习问题中的困难和若干类型的机器学习算法的能力 这个理论要… 机器学习第十二章——计算学习理论 12.计算学习理论12.1 基础知识12.1 可能学习近似正确假设PAC12.3 有限假设空间12.4 VC维 12.计算学习理论
12.1 基础知识 从理论上刻画了若干类型的机器学习问题中的困难和若干类型的机器学习算法的能力 这个理论要回答的问题是: 在什么样的条件下成功的学习是可能的?在什么条件下某个特定的学习算法可保证成功运行? 机器学习理论的一些问题: 是否可能独立于学习算法确定学习问题中固有的难度?能否知道为保证成功的学习有多少训练样例是必要的或充足的?如果学习器被允许向施加者提出查询而不是观察训练集的随机样本会对所需样例数目有怎样的影响?能否刻画出学习器在学到目标函数前会有多少次出错?能否刻画出一类学习问题中固有的计算复杂度? 主要解决的问题是: 需要多少训练样例才足以成功地学习到目标函数学习器在达到目标前会出多少次错
12.1 可能学习近似正确假设PAC
可能近似正确学习模型(PAC) 指定PAC学习模型适用的问题在此模型下学习不同类别的目标函数需要多少训练样例和多大的计算量
X表示所有实例的集合C代表学习器要学习的目标概念集合C中每个目标概念c对应于X的某个子集或一个等效的布尔函数c: X → { 0 , 1 } X→\{0,1\} X→{0,1}
假定实例按照某概率分布D从X中随机产生
学习器L在学习目标概念时考虑可能假设的集合H。在观察了一系列关于目标概念c的训练样例后L必须从H中输出某假设h它是对c的估计
我们通过h在从X中抽取的新实例上的性能来评估L是否成功。新实例与训练数据具有相同的概率分布
我们要求L足够一般以至可以从C中学到任何目标概念而不管训练样例的分布如何因此我们会对C中所有可能的目标概念和所有可能的实例分布D进行最差情况的分析
12.3 有限假设空间
PAC可学习性很大程度上由所需的训练样例数确定随着问题规模的增长所带来的所需训练样例的增长称为该学习问题的样本复杂度我们把样本复杂度的讨论限定于一致学习器(输出完美拟合训练数据的学习器)能够独立于特定算法推导出任意一致学习器所需训练样例数的界限变型空间:能正确分类训练样例D的所有假设的集合。 V S H , D { h ∈ H ∣ ( ∀ x , c ( x ) ∈ D ( h ( x ) c ( x ) ) ) } VS_{H,D}\{h\in H|(\forall\quad x,c(x)\quad\in D(h(x)c(x)))\} VSH,D{h∈H∣(∀x,c(x)∈D(h(x)c(x)))} 变型空间的重要意义是每个一致学习器都输出一个属于变型空间的假设 因此界定任意一个一致学习器所需的样例数量只需要界定为保证变型中没有不可接受假设所需的样例数量 定义:考虑一假设空间H目标概念c实例分布D以及c的一组训练样例S。当 V S H , D VS_{H,D} VSH,D 中每个假设h关于c和D错误率小于ε时变型空间被称为c和D是ε-详尽的。 ( ∀ h ∈ V S H , D ) e r r o r D ( h ) ε (\forall h\in VS_{H,D})error_D(h)ε (∀h∈VSH,D)errorD(h)ε 详尽的变型空间表示与训练样例一致的所有假设的真实错误率都小于ε 从学习器的角度看所能知道的只是这些假设能同等地拟合训练数据它们都有零训练错误率 只有知道目标概念的观察者才能确定变型空间是否为ε-详尽的 但是即使不知道确切的目标概念或训练样例抽取的分布一种概率方法可在给定数目的训练样例之后界定变型空间为ε-详尽的 定理7.1(变型空间的ε-详尽化 若假设空间H有限且D为目标概念c的一系列m1个独立随机抽取的样例那么对于任意0ε1变型空间不是ε-详尽的概率小于或等于: ∣ H ∣ e − ε m |H|e^{-εm} ∣H∣e−εm 证明: 令 h 1 , . . . , h k h_1,...,h_k h1,...,hk 为H中关于c的真实错误率大于ε的所有假设。当且仅当k个假设中至少有一个恰好与所有m个独立随机抽取样例一致时不能使变型空间ε-详尽化。 任一假设真实错误率大于ε且与一个随机抽取样例一致的可能性最多为1-ε因此该假设与m个独立抽取样例一致的概率最多为 ( 1 − ε ) m (1-ε)^m (1−ε)m 由于已知有k个假设错误率大于ε那么至少有一个与所有m个训练样例都不一致的概率最多为 当 0 ≤ ε ≤ 1 , 则 1 − ε ≤ e ε k ( 1 − ε ) m ≤ ∣ H ∣ ( 1 − ε ) m ≤ ∣ H ∣ e − ε m ( 7.2 ) 当0\leqε\leq1,则1-ε\leq e^ε\\ k(1-ε)^m\leq|H|(1-ε)^m\leq|H|e^{-εm}\quad\quad(7.2) 当0≤ε≤1,则1−ε≤eεk(1−ε)m≤∣H∣(1−ε)m≤∣H∣e−εm(7.2) 定理7.1基于训练样例的数目m、允许的错误率ε和H的大小给出了变型空间不是ε-详尽的概率的上界 即它对于使用假设空间H的任意学习器界定了m个训练样例未能将所有“坏”的假设错误率大于ε的假设)剔除出去的概率 利用上面的结论来确定为了减少此“未剔除”概率到一希望程度ε所需的训练样例数 由 ∣ H ∣ e − ε m ≤ δ → m ≥ 1 ε ( ln ∣ H ∣ ln ( 1 / δ ) ) 由|H|e^{-εm}\leq\delta→m\geq\frac{1}{ε}(\ln|H|\ln(1/\delta)) 由∣H∣e−εm≤δ→m≥ε1(ln∣H∣ln(1/δ)) 式子7.2提供了训练样例数目的一般边界该数目的样例足以在所期望的值ε和δ程度下使任何一致学习器成功地学习到H中的任意目标概念 训练样例的数目m足以保证任意一致假设是可能可能性为1-δ近似错误率为ε正确的 m随着1/ε线性增长随着1/δ和假设空间的规模对数增长 上面的界限可能是过高的估计主要来源于|H|项它产生于证明过程中在所有可能假设上计算那些不可接受的假设的概率和
12.4 VC维 分层有向无环图的特点: 节点可划分成层即所有第1层出来的有向边进入到第l1层节点没有有向环即有向弧形成的回路 这样网络的VC维的界定可以基于其图的结构和构造该图的基本单元的VC维 定义一些术语 G表示神经网络 n是G的输入数目 G只有1个输出节点 G的每个内部单元Ni最多有r个输入并实现布尔函数 c i : R r → { 0 , 1 } c_i:R^r→\{0,1\} ci:Rr→{0,1} 形成函数类C 定义C的G-合成:网络G能实现的所有函数的类即网络G表示的假设空间表示成 C G C_G CG 定理7.4分层有向无环网络的VC维 令G为一分层有向无环图有n个输入节点和s2个内部节点每个至少有r个输入令C为VC维为d的 R r R^r Rr 上的概念类对应于可由每个内部节点s描述的函数集合令 C G C_G CG 为C的G合成对应于可由G表示的函数集合则 V C ( C G ) 2 d s log ( e s ) VC(C_G)2ds\log(es) VC(CG)2dslog(es) 假定要考虑的分层有向无环网络中单个节点都是感知器由于单独的r输入感知器VC维为r1代入定理7.4和式子7.7得到 V C ( C G p e r c e p t i o n s ) ≤ 2 ( r 1 ) s log ( e s ) VC(C_G^{perceptions})\leq2(r1)s\log(es) VC(CGperceptions)≤2(r1)slog(es) m ≥ 1 ε ( 4 log ( 2 / δ ) 16 ( r 1 ) s log ( e s ) log ( 13 / ε ) ) m\geq\frac{1}{\varepsilon}(4\log(2/\delta)16(r1)s\log(es)\log(13/\varepsilon)) m≥ε1(4log(2/δ)16(r1)slog(es)log(13/ε)) 上面的结果不能直接应用于反向传播的网络原因有两个: 此结果应用于感知器网络而不是sigmoid单元网络不能处理反向传播中的训练过程
