AAI06归纳学习(2)高级人工智能史忠植

第六章归纳学习(2)史忠植中科院计算所2/6/20231史忠植高级人工智能决策树发现概念描述空间一种特别有效的方法是形成决策树。Hunt、Marin、和Stone于1966年研制了一个概念学习系统CLS,可以学习单个概念，并用此学到的概念分类新的实例。Quinlan于1983年研制了ID3(1983)。Schlimmer和Fisher于1986年构造了ID4算法，允许递增式地构造决策树。Utgoff于1988年提出ID5算法，它允许通过修改决策树来增加新的训练实例，而无需重建决策树2/6/20232史忠植高级人工智能决策树2/6/20233史忠植高级人工智能决策树2/6/20234史忠植高级人工智能决策树2/6/20235史忠植高级人工智能决策树2/6/20236史忠植高级人工智能决策树2/6/20237史忠植高级人工智能决策树2/6/20238史忠植高级人工智能决策树2/6/20239史忠植高级人工智能决策树2/6/202310史忠植高级人工智能决策树2/6/202311史忠植高级人工智能决策树2/6/202312史忠植高级人工智能CLS算法

(1)如果C中全部实例为正例，则建立一个YES结点，并且停止。如果C中全部实例为反例，则建立一个NO结点，并且停止。否则选择一个属性A,根据它的值v1,…,vn

建立决策树。(2)根据值V，将训练实例$C$划分为子集C1,…,Cn。(3)对每个集合Ci递归地应用此算法。2/6/202313史忠植高级人工智能决策树

CLS算法可以产生所有可能的决策树，正确分类训练实例，并能选择最简单的决策树。但是，它的学习问题不能太大。为了克服这种限止，ID3采用训练实例的子集，即可以选择窗口来形成决策树。这种树可以正确分类窗口中的所有对象。然后，使用该树可以分类训练集中的所有其它对象。如果该树对所有对象给以正确的解答，那么，它对整个训练集是正确的，算法就结束。如果不是这样，选择一个例外加到窗口继续处理，直到发现正确的决策树为止。2/6/202314史忠植高级人工智能决策树

ID3采用信息论方法，减小对象分类的测试期望值。属性选择是基于可能性假设，即决策树的复杂性与消息传递的信息量有关。设C包括类P的对象p和类N的对象n,假设：(1)任何C的正确决策树，以C中表示同样的比例将对象分类。任何对象属于类P的概率为p/(p+n)，

属于类N的概率为n/(p+n)。2/6/202315史忠植高级人工智能决策树

(2)当用决策树进行分类时，返回一个类。作为消息源`P'或`N'有关的决策树，产生这些消息所需的期望信息为：

I(p,n)=-p/p+nlog2(p/(p+n))-n/p+nlog2(n/(p+n))2/6/202316史忠植高级人工智能决策树

决策树根的属性A具有A1,A2,…,Am，它将C划分为C1,C2,…,Cm,其中Ci

包括C中属性$A$的值为Ai的那些对象。设Ci包括类P的对象pi和类N的对象ni。子树Ci所需的期望信息是I(pi,ni)。以属性A作为树根所要求的期望信息可以通过权值平均得到：E(A)={pi+ni}/{p+n}I(pi,ni)其中第i个分支的权值是与C中属于Ci的对象成比例。所以按A分支的信息增益为：

gain(A)=I(p,n)-E(A)2/6/202317史忠植高级人工智能决策树

ID3检查所有的候选属性，选择增益最大的属性A作为根结点，形成树。然后，对子树C1,C2,…,Cm以同样处理，递归地形成决策树。2/6/202318史忠植高级人工智能ID3算法

(1)选择给定训练实例的随机子集（称为窗口）。

(2)重复(a)形成一条规则解释当前窗口。(b)从其余实例中寻找该规则的例外。(c)由当前窗口和规则例外生成新的窗口。

直到该规则没有例外为止。2/6/202319史忠植高级人工智能ID3算法

ID3专门用于处理大量对象。事实上，时间计算增加仅与下面乘积成线性关系：(1)训练对象数,(2)

描述对象的属性数,(3)

决策树的结点数，它反映所求概念的复杂性。2/6/202320史忠植高级人工智能决策树

ID3DecisionTreeLearningAlgorithm

ID3(Examples,Target,Attributes)CreatearootnodeIfallExampleshavethesameTargetvalue,givetherootthislabelElseifAttributesisemptylabeltherootaccordingtothemostcommonvalueElsebeginCalculatetheinformationgainforeachattribute,accordingtotheaverageentropyformulaSelecttheattribute,A,withthelowestaverageentropy(highestinformationgain)andmakethistheattributetestedattherootend2/6/202321史忠植高级人工智能决策树

Foreachpossiblevalue,v,ofthisattributeAddanewbranchbelowtheroot,correspondingtoA=vLetExamples(v)bethoseexampleswithA=vIfExamples(v)isempty,makethenewbranchaleafnodelabelledwiththemostcommonvalueamongExamplesElseletthenewbranchbethetreecreatedbyID3(Examples(v),Target,Attributes-{A})end2/6/202322史忠植高级人工智能决策树ID4

1986,Schlimmer和Fisher设计了ID4学习算法,是一种递增式学习算法。他们修改ID3算法，在每个可能的决策树结点创建一系列表。每个表由全部未检测属性值和每个值的正例和反例数组成。当处理一个新例时，每个属性值的正例或反例递增计量。2/6/202323史忠植高级人工智能决策树ID4

输入:决策树，一个实例输出:决策树(1)若该实例是正例，正例数加1，否则，反例数加1。(2)如果实例全部为正例或反例，则返回决策树。(3)否则(a)计算期望信息分数。(b)实例中出现的每个属性、每个值，使之递增正例数或者反例数。(c)计算全部属性的信息分数。

2/6/202324史忠植高级人工智能决策树ID4

(d)如果没有根，或者最大属性不在根结点，则创建新树。

(i)如果最大属性是x2

依赖关系，那么用它作为这棵树的根结点。(ii)链接根到每个根属性的值

(e)跳转到步骤(1)，下面创建的子树链到该实例的根属性值。2/6/202325史忠植高级人工智能决策树ID5

在ID4的基础上Utgoff提出了ID5学习算法(Utgoff1988)。ID5与ID4的差别在于检测属性。ID5抛弃旧的检测属性下面的子树，从下面选出检测属性形成树。这种方法的优点是在树操纵时重新计算正例和反例的数，不要对实例重新处理。2/6/202326史忠植高级人工智能ID5算法

(1)对结点每个可能的检测属性，修改属性的正例和反例数，以及修改该属性值观察值的正例数和反例数。(2)如果非检测属性的最低信息论测度低于当前的检测属性，则将该检测属性提上来，重新构造决策树。(3)在给定结点仅观察到正例或反例，那么保存其余训练实例。结束停止。(4)在实例描述中，对所希望检测属性值下面的决策树进行递归修改。2/6/202327史忠植高级人工智能ID5属性提升算法

(1)递归地提升属性到最近子树的根结点。(2)对每个子树的分支值，将旧的检测属性推到新属性下，构造新的决策树。这样，形成一组子树，每个根结点都是所希望的检测属性。(3)合并子树，形成决策树，其根结点是所希望的检测属性。2/6/202328史忠植高级人工智能决策树

Missingvalues

MultivaluedattributesContinuousvaluedattributes2/6/202329史忠植高级人工智能归纳学习的计算理论

学习的计算理论主要研究学习算法样本复杂性计算复杂性。2/6/202330史忠植高级人工智能Gold学习理论

在形式语言学习的上下文中，Gold引入收敛的概念，有效地处理了从实例学习的问题。学习算法允许提出许多假设，无须知道什么时候它是正确的，只要确认某点它的计算是正确的假设。由于Gold算法的复杂性很高，因此这种风范并没有在实际学习中得到应用。2/6/202331史忠植高级人工智能Gold学习理论

基于Gold学习框架，Shapiro提出了模型推理算法研究形式语言与其解释之间的关系，也就是形式语言的语法与语义之间的关系。模型论把形式语言中的公式、句子理论和它们的解释─模型，当作数学对象进行研究。Shapiro模型推理算法只要输入有限的事实就可以得到一种理论输出(Shapiro1981)。2/6/202332史忠植高级人工智能Gold学习理论

Gold的语言学习理论研究引入两个基本概念，即极限辨识枚举辨识,这对早期的归纳推理的理论研究起了非常重要的作用(Gold1967)。2/6/202333史忠植高级人工智能Gold学习理论

极限辨识把归纳推理看作一种无限过程，归纳推理方法的最终或极限行为可以看作是它的成功标准。假设M是一种归纳推理方法，它企图正确地描述未知规则R。假设M重复运行，R的实例集合则愈耒愈大，形成M推测的无限序列g1,g2,…。如果存在某个数m，使得gm是R的正确描述， gm=gm＋1=gm＋2=…,

2/6/202334史忠植高级人工智能Gold学习理论

枚举辨识是第一种方法推测多项式序列的抽象，即对可能的规则空间进行系统搜索，直到发现与迄今为止的所有数据相一致的推测。假设规定了规则的具体领域，有一个描述枚举，即d1，d2,d3,…,以致于领域中的每一条规则在枚举中有一种或多种描述。给定一条规则的某个实例集合，枚举辨识方法将通过这个表，找到第一个描述d1，即与给定的实例相容，那么推测为d1。这种方法不能确定是否会达到正确的极限辨识。如果实例表示和相容关系满足下面两个条件，那么枚举方法保证极限辨识该领域中的全部规则：(1)一个正确假设总是与给定的实例相容。(2)任何不正确的假设与实例足够大的集合或与全部集合不相容。为了枚举方法是可计算的，枚举d1,d2,d3,…必须是可计算的，它必须能够计算给定的描述与给定的实例集合是相容的。2/6/202335史忠植高级人工智能枚举辨识算法枚举辨识算法。输入：一组表达式的集合E=e1,e2,…。

谕示(oracle)TE提供足够的目标实例集。

排序信息的谕示LE。输出：一系列假设断言H1,H_2,…,每个假设Hi都在E中，并与第i个实例一致。2/6/202336史忠植高级人工智能枚举辨识算法过程：1.初始化，i1;2.examples

emptyset;3.Loop:

3.1调用TE(),将example加到集合examples;3.2WhileLE(ei,+x)=no,对正例集+x,或者LE(ei,-x)=yes,对反例集-x,ii+1;

4.输出ei2/6/202337史忠植高级人工智能模型推理系统模型推理问题是科学家所面临的问题抽象，他们在具有固定概念框架的某种领域里工作，进行试验，试图找到一种理论可以解释他们的结果。在这种抽象中研究的领域是对给定的一阶语言L某种未知模型M的领域，实验是检测M中L语句的真值，目标是寻找一组正确假设，它们包含全部正确的可测试的句子。

L语句分成两个子集：观测语言Lo和假设语言Lh。假设

LoLh

L‘其中

是空语句。2/6/202338史忠植高级人工智能模型推理系统模型推理问题可以定义如下：假设给定一阶语言$L和两个子集：观测语言Lo和假设语言Lh。另外对L的未知模型M给定一种处理机制oracle。模型推理问题是寻找M的一种有限的Lo─完备公理化。求解模型推理问题的算法称为模型推理算法。模型M的枚举是一个无限序列F1,F2,F3,…，其中Fi是关于M的事实，Lo的每个语句发生在事实Fi=<,V>,i>0。模型推理算法一次读入给定观测语言Lo的模型的一种枚举，一个事实，产生假设语言Lh的语句的有限集称为算法的推测。2/6/202339史忠植高级人工智能模型推理系统

h是整个递归函数。设Sfalse为

，Strue为{}，k为0。repeat

读入下一个事实Fn=<,V>，

加到Sv,while

∈Sfalse以致于Tk

n或有一个i

∈

Strue以致于

Tk

niidok=k+1，输出Tkforever2/6/202340史忠植高级人工智能Valiant学习理论

Valiant认为一个学习机必须具备下列性质：(1)机器能够证明地学习所有类的概念。更进一步，这些类可以特征化。(2)对于通用知识概念类是合适的和不平常的。(3)机器演绎所希望的程序的计算过程要求在可行的步数内。2/6/202341史忠植高级人工智能Valiant学习理论

学习机由学习协议和演绎过程组成。学习协议规定从外部获得信息的方法。演绎过程是一种机制，学习概念的正确识别算法是演绎的。从广义来看，研究学习的方法是规定一种可能的学习协议，使用这种协议研究概念类，识别程序可以在多项式时间内演绎。具体协议允许提供两类信息。第一种是学习者对典型数据的访问，这些典型数据是概念的正例。要确切地说，假设这些正例本质上有一种任意确定的概率分布。调用子程序EXAMPLES产生一种这样的正例。产生不同例子的相对概率是分布确定的。第二个可用的信息源是ORACLE。在最基本的版本中，当提交数据时，它将告诉学习该数据是否是概念的正例示。2/6/202342史忠植高级人工智能Valiant学习理论

假设X是实例空间，一个概念是X的一个子集。如果实例在概念中则为正例，否则为反例。概念表示是一种概念的描述，概念类是一组概念表示。学习模型是概念类的有效的可学习性。Valiant学习理论仅要求对目标概念的很好近似具有极高的概率。允许学习者产生的概念描述与目标概念有一个小的偏差

，它是学习算法的一个输入参数。并且，允许学习者失败的概率为，这也是一个输入参数。两种概念之间的差别采用在实例空间X的分布概率D来评测：

diffD(c1,c2)=D(x)2/6/202343史忠植高级人工智能Valiant学习理论

根据协议，一个概念类C是可学习的当且仅当有一种算法A，使用协议，对所有的目标概念表示c*C和全部分布D，(1)执行时间是与1/、1/、c*数目和其它相关参数有关的多项式。(2)输出C中的概念c具有概率1-，

diffD(c,c*)<2/6/202344史忠植高级人工智能SupportVectorMachine(SVM)2/6/202345史忠植高级人工智能SupportVectorMachine(SVM)2/