wordpress产品目录,昆明网站的优化,北京网站营销与推广,easyui 做的网站1. 计算学习理论概述
从理论上刻画了若干类型的机器学习问题中的困难和若干类型的机器学习算法的能力
这个理论要回答的问题是#xff1a;
在什么样的条件下成功的学习是可能的#xff1f;
在什么条件下某个特定的学习算法可保证成功运行#xff1f;
这里考虑两种框架
在什么样的条件下成功的学习是可能的
在什么条件下某个特定的学习算法可保证成功运行
这里考虑两种框架
可能近似正确PAC确定了若干假设类别判断它们能否从多项式数量的训练样例中学习得
到定义了一个对假设空间复杂度的自然度量由它可以界定归纳学习所需的训练样例数目。
出错界限框架考查了一个学习器在确定正确假设前可能产生的训练错误数量。
机器学习理论的一些问题
是否可能独立于学习算法确定学习问题中固有的难度能否知道为保证成功的学习有多少训练样例
是必要的或充足的如果学习器被允许向施教者提出查询而不是观察训练集的随机样本会对所
需样例数目有怎样的影响能否刻画出学习器在学到目标函数前会有多少次出错能否刻画出一类
学习问题中固有的计算复杂度
对所有这些问题的一般回答还未知但不完整的学习计算理论已经开始出现。本文阐述了该理论中
的一些关键结论并提供了在特定问题下一些问题的答案。主要讨论在只给定目标函数的训练样例
和候选假设空间的条件下对该未知目标函数的归纳学习问题。主要要解决的问题是需要多少训
练样例才足以成功地学习到目标函数以及学习器在达到目标前会出多少次错。
如果明确了学习问题的如下属性那么有可能给出前面问题的定量的上下界学习器所考虑的假设
空间的大小和复杂度目标概念须近似到怎样的精度学习器输出成功的假设的可能性训练样例
提供给学习器的方式。
本文不会着重于单独的学习算法而是在较宽广的学习算法类别中考虑问题样本复杂度学习器
要收敛到成功假设需要多少训练样例计算复杂度学习器要收敛到成功假设需要多大的计算
量出错界限在成功收敛到一个假设前学习器对训练样例的错误分类有多少次
为了解决这些问题需要许多特殊的条件设定比如“成功”的学习器的设定学习器是否输出等于
目标概念的假设只要求输出的假设与目标概念在多数时间内意见一致学习器通常输出这样的假
设。学习器如何获得训练样例由一个施教者给出由学习器自己实验获得按照某过程随机生成
本文会介绍可能近似正确PAC学习框架。在PAC框架下分析几种学习算法的样本复杂度和计
算复杂度介绍了假设空间复杂度的一个重要度量标准称为VC维并且将PAC分析扩展到假设
空间无限的情况介绍出错界限模型并提供了前面章节中几个学习算法出错数量的界限最后介
绍了加权多数算法。
2. 可能近似正确学习模型PAC 可能近似正确学习模型PAC指定PAC学习模型适用的问题在此模型下学习不同类别的目
标函数需要多少训练样例和多大的计算量本文的讨论将限制在学习布尔值概念且训练数据是无
噪声的许多结论可扩展到更一般的情形。
X表示所有实例的集合C代表学习器要学习的目标概念集合C中每个目标概念c对应于X的某
个子集或一个等效的布尔函数c: X-{0,1}假定实例按照某概率分布D从X中随机产生学习器L在
学习目标概念时考虑可能假设的集合H。在观察了一系列关于目标概念c的训练样例后L必须从H
中输出某假设h它是对c的估计我们通过h在从X中抽取的新实例上的性能来评估L是否成功。新
实例与训练数据具有相同的概率分布我们要求L足够一般以至可以从C中学到任何目标概念而
不管训练样例的分布如何因此我们会对C中所有可能的目标概念和所有可能的实例分布D进行
最差情况的分析。
2.1 假设的错误率
为了描述学习器输出的假设h对真实目标概念的逼近程度首先要定义假设h对应于目标概念c和实
例分布D的真实错误率h的真实错误率是应用h到将来按分布D抽取的实例时的期望的错误率定
义假设h的关于目标概念c和分布D的真实错误率为h误分类根据D随机抽取的实例的概率
。
真实错误率紧密地依赖于未知的概率分布D如果D是一个均匀的概率分布假设的错误率为h和c
不一致的空间在全部实例空间中的比例如果D恰好把h和c不一致区间中的实例赋予了很高的概
率相同的h和c将造成更高的错误率。
h关于c的错误率不能直接由学习器观察到L只能观察到在训练样例上h的性能训练错误率指
代训练样例中被h误分类的样例所占的比例问题h的观察到的训练错误率对真实错误率产生不正
确估计的可能性多大
2.2 PAC可学习性
我们的目标是刻画出这样的目标概念它们能够从合理数量的随机抽取训练样例中通过合理的计算
量可靠地学习。对可学习性的表述一种可能的选择为了学习到使errorD(h)0的假设h所需的
训练样例数这样的选择不可行首先要求对X中每个可能的实例都提供训练样例其次要求训练
样例无误导性可能近似学习首先只要求学习器输出错误率限定在某常数ε范围内的假设其次
要求对所有的随机抽取样例序列的失败的概率限定在某常数δ范围内只要求学习器可能学习到一
个近似正确的假设。
PAC可学习性的定义考虑定义在长度为n的实例集合X上的一概念类别C学习器L使用假设空间
H。当对所有c∈CX上的分布Dε和δ满足0εδ1/2学习器L将以至少1-δ输出一假设h∈H
使errorD(h)ε这时称C是使用H的L可PAC学习的所使用的时间为1/ε1/δn以及size(c)的多
项式函数。上面定义要求学习器L满足两个条件L必须以任意高的概率1-δ输出一个错误率任
意低ε的假设学习过程必须是高效的其时间最多以多项式方式增长。上面定义的说明1/ε
和1/δ表示了对输出假设要求的强度n和size(c)表示了实例空间X和概念类别C中固有的复杂度n
为X中实例的长度size(c)为概念c的编码长度。
在实践中通常更关心所需的训练样例数如果L对每个训练样例需要某最小处理时间那么为了
使c是L可PAC学习的L必须从多项式数量的训练样例中进行学习。实际上为了显示某目标概念
类别C是可PAC学习的一个典型的途径是证明C中每个目标概念可以从多项式数量的训练样例中
学习到且处理每个样例的时间也是多项式级。PAC可学习性的一个隐含的条件对C中每个目标
概念c假设空间H都包含一个以任意小误差接近c的假设。
2.3 有限假设空间的样本复杂度
PAC可学习性很大程度上由所需的训练样例数确定随着问题规模的增长所带来的所需训练样例的
增长称为该学习问题的样本复杂度我们把样本复杂度的讨论限定于一致学习器输出完美拟合训
练数据的学习器能够独立于特定算法推导出任意一致学习器所需训练样例数的界限变型空
间能正确分类训练样例D的所有假设的集合。 变型空间的重要意义是每个一致学习器都输出一个属于变型空间的假设。因此界定任意一个一致
学习器所需的样例数量只需要界定为保证变型中没有不可接受假设所需的样例数量。定义考虑
一假设空间H目标概念c实例分布D以及c的一组训练样例S。当VSH,D中每个假设h关于c和D错
误率小于ε时变型空间被称为c和D是ε-详尽的。
ε-详尽的变型空间表示与训练样例一致的所有假设的真实错误率都小于ε。从学习器的角度看所
能知道的只是这些假设能同等地拟合训练数据它们都有零训练错误率。只有知道目标概念的观察
者才能确定变型空间是否为ε-详尽的。但是即使不知道确切的目标概念或训练样例抽取的分布
一种概率方法可在给定数目的训练样例之后界定变型空间为ε-详尽的。
变型空间的ε-详尽化定理若假设空间H有限且D为目标概念c的一系列m1个独立随机抽取的
样例那么对于任意0ε1变型空间VSH,D不是ε-详尽的概率小于或等于
证明令h1,...,hk为H中关于c的真实错误率大于ε的所有假设。当且仅当k个假设中至少有一个恰好
与所有m个独立随机抽取样例一致时不能使变型空间ε-详尽化。任一假设真实错误率大于ε且与
一个随机抽取样例一致的可能性最多为1-ε因此该假设与m个独立抽取样例一致的概率最多为
。由于已知有k个假设错误率大于ε那么至少有一个与所有m个训练样例都不一致的概率最
多为。
基于训练样例的数目m、允许的错误率ε和H的大小给出了变型空间不是ε-详尽的概率的上界即
它对于使用假设空间H的任意学习器界定了m个训练样例未能将所有“坏”的假设错误率大于ε的假
设剔除出去的概率利用上面的结论来确定为了减少此“未剔除”概率到一希望程度δ所需的训练
样例数由解出m得到。
训练样例的数目m足以保证任意一致假设是可能可能性为1-δ近似错误率为ε正确的m随
着1/ε线性增长随着1/δ和假设空间的规模对数增长上面的界限可能是过高的估计主要来源
于|H|项它产生于证明过程中在所有可能假设上计算那些不可接受的假设的概率和。
2.4 不可知学习和不一致假设
如果学习器不假定目标概念可在H中表示而只简单地寻找具有最小训练错误率的假设这样的学
习器称为不可知学习器。基于的假定是学习器输出一零错误率假设在更一般的情形下学习器考虑
到了有非零训练错误率的假设时仍能找到一个简单的边界。令S代表学习器可观察到的特定训练
样例集合errorS(h)表示h的训练错误率即S中被h误分类的训练样例所占比例。令hbest表示H中
有最小训练错误率的假设问题是多少训练样例才足以保证其真实错误率errorD(hbest)不会多于
eerrorS(hbest)上一节问题是这个问题的特例
引入一般的Hoeffding边界。Hoeffding边界刻画的是某事件的真实概率及其m个独立试验中观察到
的频率之间的差异。Hoeffding边界表明当训练错误率errorS(h)在包含m个随机抽取样例的集合S
上测量时则。上式给出了一个概率边界说明任意选择的
假设训练错误率不能代表真实情况为保证L寻找到的最佳的假设的错误率有以上的边界我们必
须考虑这|H|个假设中任一个有较大错误率的概率 将上式左边概率称为δ问多少个训练样例m才足以使δ维持在一定值内求解得到
。适用于当最佳假设可能有非零训练错误率时学习器仍能选择到最
佳假设h∈H的情形。
2.5 布尔文字的合取是PAC可学习的
我们已经有了一个训练样例数目的边界表示样本数目为多少时才足以可能近似学习到目标概念
现在用它来确定某些特定概念类别的样本复杂度和PAC可学习性。考虑目标概念类C它由布尔文
字的合取表示。布尔文字是任意的布尔变量或它的否定。问题C是可PAC学习的吗若假设空
间H定义为n个布尔文字的合取则假设空间|H|的大小为3n得到关于n布尔文字合取学习问题的
样本复杂度。
布尔合取式的PAC可学习性布尔文字合取的类C是用Find-S算法PAC可学习的。
证明该概念类的样本复杂度是n、1/δ和1/ε的多项式级而且独立于size(c)。为增量地处理每个
训练样例Find-S算法要求的运算量根据n线性增长并独立于1/δ、1/ε和size(c)。因此这一概念类
别是Find-S算法PAC可学习的。
2.6 其他概念类别的PAC可学习性
无偏学习器无归纳偏置考虑一无偏概念类C它包含与X相关的所有可教授概念X中的实例
定义为n个布尔值特征则有
无偏的目标概念类在PAC模型下有指数级的样本复杂度。
K项DNF和K-CNF概念某概念类有多项式级的样本复杂度但不能够在多项式时间内被学习到。
概念类C为k项析取范式k项DNF的形式k项DNFT1∪...∪Tk其中每一个Ti为n个布尔属性
和它们的否定的合取。假定HC则|H|最多为3nk得到
因此k项DNF的样本复杂度为1/δ、1/ε、n和k的多项式级但是计算复杂度不是多项式级该问
题是NP完全问题等效于其他已知的不能在多项式时间内解决的问题因此虽然k项DNF有多
项式级的样本复杂度它对于使用HC的学习器没有多项式级的计算复杂度。
令人吃惊的是虽然k项DNF不是PAC可学习的但存在一个更大的概念类是PAC可学习的这个
更大的概念类是K-CNF它有每样例的多项式级时间复杂度又有多项式级的样本复杂度K-
CNF任意长度的合取式T1∪...∪Tj其中每个Ti为最多k个布尔变量的析取容易证明K-CNF包
含了K项DNF因此概念类k项DNF是使用HK-CNF的一个有效算法可PAC学习的。
3. 无限假设空间的样本复杂度
用|H|刻画样本复杂度有两个缺点可能导致非常弱的边界对于无限假设空间的情形无法应
用。本节考虑H的复杂度的另一种度量称为H的Vapnik-Chervonenkis维度简称VC维或
VC(H)。使用VC维代替|H|也可以得到样本复杂度的边界基于VC维的样本复杂度比|H|更紧凑
另外还可以刻画无限假设空间的样本复杂度。
VC维衡量假设空间复杂度的方法不是用不同假设的数量|H|而是用X中能被H彻底区分的不同实例
的数量。S是一个实例集H中每个h导致S的一个划分即h将S分割为两个子集{x∈S|h(x)1}和{x
属于S|h(x)0}。定义一实例集S被假设空间H打散当且仅当对S的每个划分存在H中的某假设
与此划分一致。如果一实例集合没有被假设空间打散那么必然存在某概念可被定义在实例集之
上但不能由假设空间表示。H的这种打散实例集合的能力是其表示这些实例上定义的目标概念的
能力的度量。
3.1 Vapnik-Chervonenkis维度
打散一实例集合的能力与假设空间的归纳偏置紧密相关无偏的假设空间能够打散所有实例组成的
集合X。直观上被打散的X的子集越大H的表示能力越强。定义定义在实例空间X上的假设空
间H的Vapnik-Chervonenkis维是可被H打散的X的最大有限子集的大小。如果X的任意有限大的
子集可被H打散则VC(H)∞。
对于任意有限的HVC(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维为r1。
假定X上每个实例由恰好3个布尔文字的合取表示而且假定H中每个假设由至多3个布尔文字描
述问VC(H)是多少
找到下面3个实例的集合instance1: 100instance2: 010instance3: 001
这三个实例的集合可被H打散可对如下任意所希望的划分建立一假设如果该划分要排除
instancei就将文字┐li加入到假设中。此讨论很容易扩展到特征数为n的情况n个布尔文字合取
的VC维至少为n。实际就是n但证明比较困难需要说明n1个实例的集合不可能被打散。
使用VC维作为H复杂度的度量就有可能推导出该问题的另一种解答类似于前面式子的边界即
Blumer el al. 1989。 样本复杂度的下界Ehrenfeucht et al. 1989考虑任意概念类C且VC(C)2任意学习器
L以及任意0ε1/80δ1/100。存在一个分布D以及C中一个目标概念当L观察到的样例数目
小于下式时
将以至少d的概率输出一假设h使errorD(h)ε。
若训练样例的数目太少那么没有学习器能够以PAC模型学习到任意非平凡的C中每个目标概念。
3.2 神经网络的VC维
计算分层无环网络的VC维。这个VC维可用于界定训练样例的数量该数达到多大才足以按照希望
的ε和δ值近似可能正确地学习一个前馈网络.考虑一个由单元组成的网络G它形成一个分层有向
无环图。分层有向无环图的特点节点可划分成层即所有第l层出来的有向边进入到第l1层节
点没有有向环即有向弧形成的回路。这样网络的VC维的界定可以基于其图的结构和构造该图
的基本单元的VC维。
定义一些术语G表示神经网络n是G的输入数目G只有1个输出节点G的每个内部单元Ni最
多有r个输入并实现一布尔函数ci:Rr-{0,1}形成函数类C。定义C的G-合成网络G能实现的所
有函数的类即网络G表示的假设空间表示成CG。
分层有向无环网络的VC维Kearns Vazirani 1994令G为一分层有向无环图有n个输入节
点和s2个内部节点每个至少有r个输入令C为VC维为d的Rr上的概念类对应于可由每个内
部节点s描述的函数集合令CG为C的G合成对应于可由G表示的函数集合则VC(CG)
2dslog(es)。
假定要考虑的分层有向无环网络中单个节点都是感知器由于单独的r输入感知器VC维为r1得
到
上面的结果不能直接应用于反向传播的网络原因有两个此结果应用于感知器网络而不是
sigmoid单元网络不能处理反向传播中的训练过程。
4. 学习的出错界限模型
计算学习理论考虑多种不同的问题框架训练样例的生成方式被动观察、主动提出查询数据
中的噪声有噪声或无噪声成功学习的定义必须学到正确的目标概念还是有一定的可能性和
近似性学习器所做得假定实例的分布情况以及是否C⊆H评估学习器的度量标准训练
样例数量、出错数量、计算时间。
机器学习的出错界限模型学习器的评估标准是它在收敛到正确假设前总的出错数学习器每接受
到一个样例x先预测目标值c(x)然后施教者给出正确的目标值考虑的问题是在学习器学习
到目标概念前它的预测会有多少次出错下面讨论中只考虑学习器确切学到目标概念前出错的
次数确切学到的含义∀x h(x)c(x)。
4.1 Find-S算法的出错界限
Find-S算法的一个简单实现将h初始化为最特殊假设l1∪l1∪...∪ln∪ln。对每个正例x从h中移
去任何不满足x的文字输出假设h。计算一个边界以描述Find-S在确切学到目标概念c前全部的
出错次数Find-S永远不会将一反例错误地划分为正例因此只需要计算将正例划分为反例的出错
次数遇到第一个正例初始假设中2n个项半数被删去对后续的被当前假设误分类的正例至少
有一项从假设中删去出错总数至多为n1。
4.2 Halving算法的出错界限
学习器对每个新实例x做出预测的方法是从当前变型空间的所有假设中取多数票得来将变型空
间学习和用多数票来进行后续预测结合起来的算法称为Halving算法Halving算法只有在当前变型
空间的多数假设不能正确分类新样例时出错此时变型空间至少可减少到它的一半大小因此出错
界线是log2|H|Halving算法有可能不出任何差错就确切学习到目标概念因为即使多数票是正确
的算法仍将移去那些不正确、少数票假设Halving算法的一个扩展是允许假设以不同的权值进
行投票如贝叶斯最优分类器和后面讨论的加权多数算法。
4.3 最优出错界限
问题对于任意概念类C假定HC最优的出错边界是什么
最优出错边界是指在所有可能的学习算法中最坏情况下出错边界中最小的那一个对任意学习算
法A和任意目标概念c令MA(c)代表A为了确切学到c在所有可能训练样例序列中出错的最大值
对于任意非空概念类C令MA(C)maxc∈CMA(c)。定义C为任意非空概念类C的最优出
错界限定义为Opt(C)是所有可能学习算法A中MA(C)的最小值。
非形式地说Opt(C)是C中最难的那个目标概念使用最不利的训练样例序列用最好的算法时的出错
次数。Littlestone1987证明了。
4.4 加权多数算法
Halving算法的更一般形式称为加权多数算法。加权多数算法通过在一组预测算法中进行加权投票
来作出预测并通过改变每个预测算法的权来学习。加权多数算法可以处理不一致的训练数据因
为它不会消除与样例不一致的假设只是降低其权。要计算加权多数算法的出错数量边界可以用
预测算法组中最好的那个算法的出错数量。
加权多数算法一开始将每个预测算法赋予权值1然后考虑训练样例只要一个预测算法误分类新
训练样例它的权被乘以某个系数β0β1。如果β0则是Halving算法如果β0则没有一
个预测算法会被完全去掉。如果一算法误分类一个样例那么它的权值变小。
ai代表算法池A中第i个预测算法wi代表与ai相关联的权值。对所有i初始化wi-1对每个训练样
例x, c(x)做初始化q0和q1为0对每个预测算法ai如果ai(x)0那么q0-q0wi如果
ai(x)1那么q1-q1wi。如果q1q0那么预测c(x)1如果q0q1那么预测c(x)0如果
q0q1那么对c(x)随机预测为0或1对每个预测算法ai。如果ai(x)≠c(x)那么wi-βwi。
加权多数算法的相对误差界限令D为任意的训练样例序列令A为任意n个预测算法集合令k为A
中任意算法对样例序列D的出错次数的最小值。那么使用β1/2的加权多数算法在D上出错次数最多
为2.4(klog2n)
证明可通过比较最佳预测算法的最终权和所有算法的权之和来证明。令aj表示A中一算法并且
它出错的次数为最优的k次则与aj关联的权wj将为(1/2)k。A中所有n个算法的权的和
W的初始值为n对加权多数算法的每次出错W被减小为最多其原因是加权投票占少数的
算法最少拥有整个权W的一半值而这一部分将被乘以因子1/2。令M代表加权多数算法对训练序
列D的总出错次数那么最终的总权W最多为n(3/4)M。由得
意义加权多数算法的出错数量不会大于算法池中最佳算法出错数量加上一个随着算法池大小对
数增长的项再乘以一常数因子。
可能近似正确模型PAC针对的算法从某概念类C中学习目标概念使用按一个未知但固定的概
念分布中随机抽取的训练样例它要求学习器可能学习到一近似正确的假设而计算量和训练样例
数都只随着1/δ、1/ε、实例长度和目标概念长度的多项式级增长。在PAC学习模型的框架下任何
使用有限假设空间H的一致学习器将以1-δ的概率输出一个误差在ε内的假设所需的训练样例数
m满足。
不可知学习考虑更一般的问题学习器不假定目标概念所在的类别学习器从训练数据中输出H中
有最小误差率的假设。学习保证以概率1-δ从H中最可能的假设中输出错误率小于ε的假设需要的随机抽取的训练样例数目m满足。
学习器考虑的假设空间的复杂度对所需样例的数目影响很大而衡量假设空间复杂度的一个有用的
度量是VC维。VC维是可被H打散的最大实例集的大小。
在PAC模型下以VC(H)表示的足以导致成功学习的训练样例数目的上界和下界分别是 另一种学习模式称为出错界限模式用于分析学习器在确切学习到目标概念之前会产生的误分类次
数Halving算法在学习到H中的任意目标概念前会有至多log2|H|次出错对任意概念类C最坏情
况下最佳算法将有Opt(C)次出错满足VC(C)Opt(C)log2|C|。
加权多数算法结合了多个预测算法的加权投票来分类新的实例它基于这些预测算法在样例序列中
的出错来学习每个算法的权值。加权多数算法产生的错误界限可用算法池中最佳预测算法的出错数
来计算。
