归纳学习 Inductive Learning 高级人工智能 第七章 归纳学习 Inductive Learning 史忠植 中国科学院计算技术研究所

内容提要 7.1 归纳学习的逻辑基础 7.2 偏置变换 7.3 变型空间方法 7.4 AQ归纳学习算法 7.5 产生与测试方法 7.6 决策树学习 7.7 可学习的计算理论 2018/11/16 史忠植 高级人工智能

概 述 给定关于某个概念的一系列已知的正例和反例，其任务是从中归纳出一个一般的概念描述。归纳学习能够获得新的概念，创立新的规则，发现新的理论。 泛化(generalization)用来扩展一假设的语义信息， 以使其能够包含更多的正例，应用于更多的情况。 特化(specialization)是泛化的相反的操作，用于限制概念描述的应用范围。 2018/11/16 史忠植 高级人工智能

归纳学习的一般模式 给定: ① 观察语句集(事实)F：这是有关某类对象中个别 具体对象的知识或某一对象的部分特征的知识。 ② 假定的初始归纳断言(可空)：是关于目标的泛化项或泛化描述。 ③ 背景知识：背景知识定义了在观察语句和所产生的候选归纳断言上的假定和限制，以及任何有关问题领域知识。有关问题领域知识包括特化所找归纳断言的期望性质的择优标准。 寻找: 归纳断言H(hypothesis), H 重言或弱蕴涵观察语句并满足背景知识。 2018/11/16 史忠植 高级人工智能

基本符号表 ~ 非 &合取（逻辑乘）  析取（逻辑加）  蕴涵  逻辑等价  项重写  异或 F事实集 H 假设 |> 特化 ~ 非 &合取（逻辑乘）  析取（逻辑加）  蕴涵  逻辑等价  项重写  异或 F事实集 H 假设 |> 特化 |< 泛化 2018/11/16 史忠植 高级人工智能

基本符号表 |= 重新形式化 vi存在量词约束变项vi Ivi 数值存在量词约束变项vi vi 全称量词约束变项vi Di 概念描述 Ki 判断一个概念的名字的谓词 ::> 将概念描述与概念名连接的蕴涵 ei 一个事件（对一种情况的描述） Ei 仅对概念ki的事件为真的谓词 Xi 属性 LEF 评价函数 DOM(P) 描述符P的定义域 2018/11/16 史忠植 高级人工智能

概念获取 概念获取的一类特殊情况，它的观察语句集F是一个蕴涵的集合, 其形式如下： F: {eik ::> Ki} i  I 其中，eik(Ki的训练事件)是概念Ki的第k个例子的符号描述。概念的谓词Ki, I是Ki的下标集合。 eik ::> Ki的含义是“凡符合描述eik的事件均可被断言为概念Ki的例子。 2018/11/16 史忠植 高级人工智能

概念获取 学习程序要寻求的归纳断言H可以用概念识别规则集来刻画, 形式如下： H:{Di ::> Ki} i  I 其中Di是概念Ki的描述，即表达式Di是事件的逻辑推论， 该事件可被断言为概念Ki的一个例子。 2018/11/16 史忠植 高级人工智能

完整性条件  i  I (Ei  Di) 2018/11/16 史忠植 高级人工智能

一致性条件  i,j  I (Di  ~ Ej), 若 i  j 2018/11/16 史忠植 高级人工智能

描述符类型 (1) 名称性描述符。这种描述符的定义域由独立的符号或名字组成，即值集中值之间没有结构关系。例如水果、人名等。 (2) 线性描述符。该类描述符值集中的元素是一个全序集。例如，资金、温度、重量、产量等都是线性描述符。表示序数、区间、比率和绝对标度的变量都是线性描述符的特例。将一个集合映射成一个完全有序集的函数也是线性描述符。 2018/11/16 史忠植 高级人工智能

描述符类型 (3) 结构描述符。其值集是一个树形的图结构，反映值之间的生成层次。 在这样的结构中，父节点表示比子节点更一般的概念。例如，在“地名”的值集中，“中国”是节点“北京”、“上海”、“江苏”、“广东”等的父节点。 结构描述符的定义域是通过问题背景知识说明的一组推理规则来定义的。结构描述符也能进一步细分为有序和无序的结构描述符。描述符的类型对确定应用描述符的操作是很重要的。 2018/11/16 史忠植 高级人工智能

选择型泛化规则 (1) 消除条件规则 CTX & S ::> K |< CTX ::> K (2) 增加选择项规则 CTX1 ::> K |< CTX1  CTX2 ::> K 通过增加选择项将概念描述泛化 2018/11/16 史忠植 高级人工智能

选择型泛化规则 (3) 扩大引用范围规则 CTX & [L = R1] ::> K |< CTX \& [L = R_2] ::> K 其中R1 R2  DOM(L), DOM(L) 为L的域，L是一个项， Ri是L取值的一个集合。 (4) 闭区间规则 CTX & [L = a] ::> K CTX & [L = b] ::> K |< CTX & [L = a..b] ::> K 2018/11/16 史忠植 高级人工智能

选择型泛化规则 (5) 爬山泛化树规则 CTX & [L = a] ::> K CTX & [L = b] ::> K … CTX & [L = i] ::> K |< CTX & [L = S] ::> K 其中L是结构描述符，在L的泛化树域中，S表示后继为a,b,…, i的最低的父节点。 2018/11/16 史忠植 高级人工智能

选择型泛化规则 (6) 将常量转换为变量规则 F[a] F[b] … F[i] |<  x, F[x] 其中F[x]是依赖于变量x的描述符，a,b, …, i是常量。 对于描述F[x], 若x的某些值(a,b, … , i)使F[x]成立，则可得到假设：对于x的所有值，F[x]成立。 2018/11/16 史忠植 高级人工智能

选择型泛化规则 (7) 将合取转换为析取规则 F1 & F2 ::> K |< F1  F2 ::> K 2018/11/16 史忠植 高级人工智能

选择型泛化规则 (8) 扩充量词范围规则  x,F[x] ::> k |<  x, F[x] ::> k  (I1)x,F[x] ::> K |< (I2)x, F[x]::> K 其中I1,I2是量词的域（整数集合）， 且I1  I2 2018/11/16 史忠植 高级人工智能

选择型泛化规则 (9) 泛化分解规则 用于概念获取 P & F1 ::> K ~ P & F2 ::> K |< F1  F2 ::> K 用于描述泛化 P & F1  ~ P & F2 |< F1 & F2 这里P均为谓词。 2018/11/16 史忠植 高级人工智能

选择型泛化规则 (10) 反扩充规则 CTX1 & [L = R1] ::> K CTX2 & [L = R2] ::> ~ K 其中R1,R2是析取式。 2018/11/16 史忠植 高级人工智能

构造型泛化规则 构造性泛化规则能生成一些归纳断言，这些归纳断言使用的描述符不出现在初始的观察陈述中，也就是说，这些规则对初始表示空间进行了变换。 (1) 通用构造型规则 CTX & F1 ::> K F1  F2 |< CTX & F2 ::> K 该规则表示，若一个概念描述含有一部分F1, 已知F1蕴涵另一概念F2,则通过用F2替代F1可得到一个更一般的描述。 2018/11/16 史忠植 高级人工智能

构造型泛化规则 (2) 计算变量规则。 计算量词变量CQ规则:  V1,V2, … ,Vk F[V1,V2, … ,Vk] CQ规则将产生一个新的描述符“#v-COND”, 表示满足某条件COND的vi的个数。 2018/11/16 史忠植 高级人工智能

构造型泛化规则 (3) 产生链属性规则。 概念描述中，若一个概念描述中传递关系不同出现的变量形成一条链,该规则能生成刻画链中某些特定对象的特征的描述符。这种对象可能是： LST-对象： “最小的对象”，或链的开始对象。 MST-对象： 链的结束对象。 MID-对象： 链中间的对象。 Nth-对象： 链中第N个位置上的对象。 (4) 检测描述符之间的相互依靠关系规则。 2018/11/16 史忠植 高级人工智能

偏置变换 偏置在概念学习中具有重要作用。所谓偏置，是指概念学习中除了正、反例子外，影响假设选择的所有因素。这些因素包括： ①描述假设的语言。 ②程序考虑假设的空间。 ③按什么顺序假设的过程。 ④承认定义的准则，即研究过程带有已知假设可以终止还是应该继续挑选一个更好的假设。采用偏置方法，学习部分选择不同的假设，会导致不同的归纳跳跃。 2018/11/16 史忠植 高级人工智能

偏置变换 偏置有两个特点： (1) 强偏置是把概念学习集中于相对少量的假设；反之，弱偏置允许概念 学习考虑相对大量的假设。 (2) 正确偏置允许概念学习选择目标概念，不正确偏置就不能选择目标概念。 2018/11/16 史忠植 高级人工智能

偏置变换 偏置 程序 假设 搜索程序 知识 训练集 训练例 2018/11/16 史忠植 高级人工智能

变型空间 变型空间(Version Space)方法以整个规则空间为初始的假设规则集合H。依据训练例子中的信息，它对集合 H进行泛化或特化处理，逐步缩小集合 H。最后使 H收敛为只含有要求的规则。由于被搜索的空间 H逐步缩小，故称为变型空间。 2018/11/16 史忠植 高级人工智能

变型空间 变型空间方法的初始 G集是最上面的一个点（最一般的概念），初始 S集是最下面的直线上的点（训练正例），初始 H集是整个规则空间。在搜索过程中，G 集逐步下移（进行特化），S 集逐步上移（进行泛化），H 逐步缩小。最后 H收敛为只含一个要求的概念。 没有描述 训练例子 G S 更特殊 更一般 2018/11/16 史忠植 高级人工智能

初始变型空间 2018/11/16 史忠植 高级人工智能

第一个训练实例(sm cir) 2018/11/16 史忠植 高级人工智能

第二个训练实例(lg,tri) 2018/11/16 史忠植 高级人工智能

第三个训练实例(lg cir) 2018/11/16 史忠植 高级人工智能

消除候选元素算法 (1) 正规的初始 H集是整个规则空间，这时 S包含所有可能的训练正例（最特殊的概念）。这时 S集规模太大。实际算法的初始 S集只包含第一个训练正例, 这种 H就不是全空间了。 (2) 接收一个新的训练例子。如果是正例，则首先由 G中去 掉不覆盖新正例的概念，然后修改 S为由新正例和 S原有元素共 同归纳出的最特殊的结果（这就是尽量少修改 S，但要求 S覆盖新正例）。如果这是反例，则首先由 S中去掉覆盖该反例的概念，然后修改 G为由新反例和 G原有元素共同作特殊化的最一般的结果（这就是尽量少修改 G，但要求 G不覆盖新反例）。 2018/11/16 史忠植 高级人工智能

消除候选元素算法 (3) 若 G=S且是单元素集，则转 (4)，否则转 (2)。 (4) 输出 H中的概念（即 G和 S）。 2018/11/16 史忠植 高级人工智能

改进算法 冲突匹配算法 (Hayes-Roth和 McDormott) 它用于学习“参数化结构表示”所表达的概念。在上述的修改 S过程中，总是对 S作尽量少的泛化，以便覆盖新的正例。如果描述形式为谓词表达式，则这个过程相当于寻找最大的公共子表达式，这只需要去掉最少的合取条件。 最大的合一泛化 这个算法用于寻找谓词表达式的最大的合一泛化。它类似于冲突匹配算法，但是它使用的表示语言允许在匹配中多对一的参数联系。 2018/11/16 史忠植 高级人工智能

变型空间缺点 (1) 抗干扰能力差 (2) 不能学习析取概念 2018/11/16 史忠植 高级人工智能

AQ归纳学习算法 1969年, Michalski提出了AQ学习算法, 这是一种基于实例的学习方法。AQ算法生成的选择假设的析取, 覆盖全部正例, 而不覆盖任何反例。 1978年提出了AQ11 AQ18 AQ19 2018/11/16 史忠植 高级人工智能

简单的AQ学习算法 它是利用覆盖所有正例，排斥所有反例的思想来寻找规则。 比较典型的有Michalski的AQ11方法 洪家荣的AE5方法 2018/11/16 史忠植 高级人工智能

简单的AQ学习算法 (1) 集中注意一个实例(作为种子); (2) 生成该实例的一致性泛化式(称作star); (4) 如果该假设覆盖了全部实例, 则停止; 否则选择一个未被假设覆盖的实例, 转到 (2)。 2018/11/16 史忠植 高级人工智能

简单的AQ学习算法 AE方法 AE系列方法是在扩张矩阵中寻找覆盖正例排斥反例的字段值的规则 2018/11/16 史忠植 高级人工智能

AQ学习算法 Michalski等采用AQ11程序学习15种黄豆病害的诊断规则。提供给程序630种患病黄豆植株的描述，每个描述是35个特征的特征向量。同时送入每个描述的专家诊断结论。选择例子程序从中选出290种样本植株作为训练例子。选择准则是使例子间相差较大。其余340种植株留作测试集合，用来检验得到的规则。 2018/11/16 史忠植 高级人工智能

决策树 发现概念描述空间一种特别有效的方法是形成决策树。 Hunt、Marin、和 Stone于1966年研制了一个概念学习系统 CLS, 可以学习单个概念，并用此学到的概念分类新的实例。 Quinlan于1983年研制了ID3(1983)。 Schlimmer和 Fisher于1986年构造了ID4算法，允许递增式地 构造决策树。 Utgoff于1988年提出ID5算法，它允许通过修改决策树来增加 新的训练实例，而无需重建决策树 2018/11/16 史忠植 高级人工智能

决策树 2018/11/16 史忠植 高级人工智能

决策树 2018/11/16 史忠植 高级人工智能

决策树Decision Trees Tree structure Node = query on attribute Link = attribute value Leaf = class Recursively separate data into sub-populations Prediction: Traverse path, yield most probable class 2018/11/16 史忠植 高级人工智能

CLS算法 (2) 根据值V，将训练实例$C$划分为子集C1, …, Cn。 (3) 对每个集合Ci递归地应用此算法。 (1) 如果C中全部实例为正例，则建立一个YES结点，并且停止。如果C中全部实例为反例，则建立一个NO结点，并且停止。否则选择一个属性A, 根据它的值v1, …, vn 建立决策树。 (2) 根据值V，将训练实例$C$划分为子集C1, …, Cn。 (3) 对每个集合Ci递归地应用此算法。 2018/11/16 史忠植 高级人工智能

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

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

决策树 I(p,n) = - p/p+n log2 (p/(p+n)) - n/p+n log2 (n/(p+n)) 2018/11/16 史忠植 高级人工智能

决策树 决策树根的属性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) 2018/11/16 史忠植 高级人工智能

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

信息熵 Informative Entropy Establishes Good decision trees Measure how informative is a node Definition: P=(p1,p2,…,pn) Then Entropy of P is : I(P)= -(p1*log(p1) + p2*log(p2) +…+ pn*log(pn) ) 2018/11/16 史忠植 高级人工智能

Golf Example Outlook Temperature Humidity Windy Play Sunny 85 False Don’t Play 80 90 True Overcast 83 78 Rain 70 96 68 65 64 72 95 69 75 81 71 2018/11/16 史忠植 高级人工智能

信息熵 Entropy For example: Entropy of previous golf example If P=(0.5,0.5)  I(P)=1 If P=(2/3,1/3)  I(P)=0.92 If P= (1,0)  I(P)=0 What do u see ?  Entropy of previous golf example I(P)=I(9/14,5/14)=-(9/14*log(9/14) + 5/14*log(5/14)) = 0.94 2018/11/16 史忠植 高级人工智能

信息熵 Entropy of an attribute For example: I(Outlook,T)= 5/14 * I(2/5,3/5) + 4/14 * I(4/4,0) + 5/14 * I)(3/5,2/5) = 0.694 While I(windy,T)=0.892 2018/11/16 史忠植 高级人工智能

信息增益 Information Gain Gain(T, A) = I(T) – I(T,A) I(T) = expected information for distinguishing classes = -(p/(p+n)log2(p/(p+n))+n/(p+n)log2(n/(p+n))) I(T, A) = expected information of tree with A as root = i(pi+ni)/(p+n)*I(Ti) p, n: number of positive/negative training data pi, ni: number of positive/negative training data in the training data Ti partitioned by the attribute value Ai Select an attribute with highest information gain Prefer an attribute A with smallest I(T,A) i.e., Prefer the attribute that makes non-uniform distribution 2018/11/16 史忠植 高级人工智能

信息增益 The initial information The information for Outlook attribute Sunny, Overcast, Rain I(T,Outlook) = 5/14*I(2/5,3/5) + 4/14*I(4/4,0/4) + 5/14*I(3/5,2/5) = 0.694 Gain(T,Outlook) = 0.94-0.694 = 0.246 The information for Windy attribute True, False I(T,Windy) = 6/14*I(3/6,3/6) + 8/14*I(6/8,2/8) = 0.892 Gain(T,Windy) = 0.94-0.892 = 0.048 select Outlook attribute for the first partition 2018/11/16 史忠植 高级人工智能

信息增益 Entropy of an attribute Definition of Gain() Gain(X,T) = I(T) – I(X,T) Gain(Outlook,T) = I(T) – I(Outlook,T) = 0.94 – 0.694 = 0.246 Gain(Windy,T) = I(T) – I(Windy,T) = 0.94 – 0.892 = 0.048 We say, Outlook is more informative than Windy, Why?  2018/11/16 史忠植 高级人工智能

ID3 算法 (1)选择给定训练实例的随机子集（称为窗口）。 (2)重复 (a) 形成一条规则解释当前窗口。 (b) 从其余实例中寻找该规则的例外。 (c) 由当前窗口和规则例外生成新的窗口。 直到该规则没有例外为止。 2018/11/16 史忠植 高级人工智能

决策树学习算法 ID3 Decision Tree Learning Algorithm ID3(Examples, Target, Attributes) Create a root node If all Examples have the same Target value, give the root this label Else if Attributes is empty label the root according to the most common value Else begin Calculate the information gain for each attribute, according to the average entropy formula Select the attribute, A, with the lowest average entropy (highest information gain) and make this the attribute tested at the root end 2018/11/16 史忠植 高级人工智能

决策树学习算法 For each possible value, v, of this attribute Add a new branch below the root, corresponding to A = v Let Examples(v) be those examples with A = v If Examples(v) is empty, make the new branch a leaf node labelled with the most common value among Examples Else let the new branch be the tree created by ID3(Examples(v), Target, Attributes - {A}) end 2018/11/16 史忠植 高级人工智能

C4.5 Extensions C4.5 is an extensions of ID3 accounts for Depth-first strategy is used Unavailable values Ex: only given Outlook to be Sunny Continuous attribute value ranges Ex: humidity is greater than 75 Pruning of decision trees Rule derivation 2018/11/16 史忠植 高级人工智能

c4.5 –f golf decision tree represented graphically 2018/11/16 史忠植 高级人工智能

c4.5 rules –f golf: induced rules 2018/11/16 史忠植 高级人工智能

Decision Trees: Training [C4.5, Quinlan, 1993] Generate_tree(R, C, T) // R: set of non-categorical attribute // C: categorical attribute, T: training data if T has the same categorical value then return a single node with the value if R={} then return a single node with most frequent categorical value in T A = attribute with highest information gain, Gain(T,A) among R Let A1, A2, .., Am the attribute values of A Let T1, T2, .., Tm the subsets of T partitioned by of Ai return a node with A and m links as follows for i = 1 to m do Generate_tree(R-{A}, C, Ti) 2018/11/16 史忠植 高级人工智能

Discrete vs. Continuous Attributes Suppose A is an attribute with continuous values e.g., Humidity in Golf example A1, A2, .., Am are the values in the training data, in increasing order For each Aj TL = Partition of training data whose A values are <= Aj TH = Partition of training data whose A values are > Aj Calculate Gain(T,A) or GainRatio(T,A) Select the best partition 2018/11/16 史忠植 高级人工智能

决策树学习算法 的优点 Comprehensibility Fast classification Mature technology There are many systems C4.5 [Quinlan, 1993] C5.0(See-5) 2018/11/16 史忠植 高级人工智能

Common Decision Tree / Rule-Induction Software c4.5 DOS-based decision tree and rule induction software based on Ross Quinlan’s ID3 algorithm. (Free) c5.0 / See-5 Windows-compatible version of c4.5. More flexible analysis. Replaces ID3 with a better-performing, less resource-intensive algorithm. Evaluation copy (maximum 500 cases) is free. Non-case-limited version is $475. SPSS AnswerTree (UNICEF, financial firms) Gives users the choice of several algorithms in constructing trees, depending on type of data. Impressive output, but very expensive. ($1999) SPSS AnswerTree is used by UNICEF to provide strategic direction for their direct-mail fundraising campaigns. 2018/11/16 史忠植 高级人工智能

See 5 See 5 is very similar to c4.5. The basic interface displays the data set currently in use, along with all the constituent files that you have created and/or See 5 has computed 2018/11/16 史忠植 高级人工智能

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

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

决策树ID4 (d) 如果没有根，或者最大属性不在根结点，则创建新树。 (i) 如果最大属性是 x2 依赖关系，那么用它作为这棵树的根结点。 (ii) 链接根到每个根属性的值 (e) 跳转到步骤(1)，下面创建的子树链到该实例的根属性值。 2018/11/16 史忠植 高级人工智能

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

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

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

决策树 的问题 Multivalued attributes Continuous valued attributes Missing values Multivalued attributes Continuous valued attributes 2018/11/16 史忠植 高级人工智能

归纳学习的计算理论 学习的计算理论主要研究学习算法 样本复杂性 计算复杂性。 2018/11/16 史忠植 高级人工智能

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

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

Gold学习理论 Gold的语言学习理论研究引入两个基本概念，即 极限辨识 枚举辨识, 2018/11/16 史忠植 高级人工智能

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

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

枚举辨识算法 枚举辨识算法。 输入： 一组表达式的集合 E = e1,e2,…。 谕示(oracle) TE提供足够的目标实例集。 输出： 一系列假设断言H1, H2, …, 每个假设Hi都在E中，并与第i 个实例一致。 2018/11/16 史忠植 高级人工智能

枚举辨识算法 过程： 1. 初始化，i  1; 2. examples  emptyset; 3. Loop: 3.1 调用TE(), 将example 加到集合examples; 3.2 While LE(ei,+x) = no, 对正例集+x, 或者 LE(ei,-x) = yes, 对反例集-x, i  i + 1; 4. 输出ei 2018/11/16 史忠植 高级人工智能

模型推理系统 模型推理问题是科学家所面临的问题抽象，他们在具有固定概念框架的某种领域里工作，进行试验，试图找到一种理论可以解释他们的结果。在这种抽象中研究的领域是对给定的一阶语言 L某种未知模型 M的领域，实验是检测 M中 L语句的真值，目标是寻找一组正确假设，它们包含全部正确的可测试的句子。 L 语句分成两个子集：观测语言 Lo和假设语言 Lh 。假设    Lo  Lh  L‘ 其中 是空语句。 2018/11/16 史忠植 高级人工智能

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

模型推理系统 h 是整个递归函数。 设Sfalse为 ，Strue为{}，k 为 0。 repeat 读入下一个事实Fn =< ,V>， 加到Sv, while  ∈Sfalse以致于 Tk n  或有一个i ∈ Strue以致于 Tk ni i do k = k+1， 输出 Tk forever 2018/11/16 史忠植 高级人工智能

Valiant学习理论 哈佛大学计算机科学家莱斯利•瓦伦特（Leslie Valiant）获2010年图灵奖，他的最杰出贡献是probably approximately correct (PAC) 学习理论，被认为是机器学习的鼻祖。 2018/11/16 史忠植 高级人工智能

Valiant学习理论 BIRTH: 28 March 1949, Budapest, Hungary EDUCATION: Latymer Upper School, London England; King’s College, Cambridge, England (BA, Mathematics, 1970); Imperial College, London, England (DIC in Computing Science); University of Warwick, England (PhD, Computer Science, 1974) 被引用 4215 次 2018/11/16 史忠植 高级人工智能

Valiant学习理论 PAC learning. Invented by L.Valiant in 1984. L.G.Valiant. A theory of the learnable , Communications. of the ACM, 1984, vol 27, 11, pp. 1134-1142. This probably approximately correct (PAC) model has given rise to a fruitful research area now known as computational learning theory. 被引用 4215 次 2018/11/16 史忠植 高级人工智能

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

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

Valiant学习理论 假设 X是实例空间，一个概念是 X的一个子集。如果实例在概念中则为正例，否则为反例。概念表示是一种概念的描述，概念类是一组概念表示。学习模型是概念类的有效的可学习性。Valiant 学习理论仅要求对目标概念的很好近似具有极高的概率。允许学习者产生的概念描述与目标概念有一个小的偏差 ，它是学习算法的一个输入参数。并且，允许学习者失败的概率为 ，这也是一个输入参数。两种概念之间的差别采用在实例空间 X的分布概率 D来评测： diffD(c1,c2) =  D(x) 2018/11/16 史忠植 高级人工智能

Valiant学习理论 根据协议，一个概念类 C是可学习的当且仅当有一种算法 A，使用协议，对所有的目标概念表示 c*  C 和全部分布 D， (1) 执行时间是与 1/  、1/  、c* 数目和其它相关参数有关的多项式。 (2) 输出 C中的概念 c具有概率 1-  ， diffD(c,c*)< 2018/11/16 史忠植 高级人工智能

基本概念 X - instance space (in general, an arbitrary set) cX - concept (each subset of X is a concept) C{c|cX} - class of concepts to be learned TC - the unknown concept to be learned Examples X R2 {0,1}n C set of rectangles CNF with n variables T a given rectangle a given CNF It may be more convenient for the learning algorithm to represent T in other way, and not simply as a subset of X.

学习算法- 输入 P - fixed probability distribution defined on X Learning algorithm receives a sequence of examples (x0,v0),(x1,v1),(x2,v2),(x3,v3),... where xiX and vi = “+”, if xiT, vi = “–”, if xiT, and the probability that xi appears as a current element in the sequence is in accordance with P.  - accuracy parameter  - confidence parameter

学习算法- 输入 A model where all vi = “+” can be considered, in which case we say that an algorithm is learning from positive examples. In general case we can say that algorithm is learning from positive and negative examples. A learning from only negative examples can also be considered.

学习算法- 输出 After the processing a finite sequence of inputs a learning algorithm outputs a concept SC. ST - the symmetric difference of S and T P(ST) - the error rate of concept S, i.e. the probability that T and S classify a random example differently.

可学习定义 A concept S is approximately correct, if P(ST) The learning algorithm is probably approximately correct, if the probability that the output S is approximately correct is at least 1– In this case we say that a learning algorithm pac-learns the concept class C, and that the concept class C is pac-learnable

多项式可学习 1 A learning algorithm L is a polynomial PAC-learning algorithm for C, and C is polynomially PAC-learnable, if L PAC-learns C with time complexity (and sample complexity) which are polynomial in 1/ and 1/. It is useful to consider similar classes of concepts with different sizes n, and require polynomial complexity also in n, but then we must focus on specific instance spaces dependent from parameter n (eg. X= {0,1}n).

多项式可学习 2 We consider C = {(Xn,Cn)|n>0} A learning algorithm L is a polynomial PAC-learning algorithm for C, and C is polynomially PAC-learnable, if L PAC-learns C with time complexity (and sample complexity) which are polynomial in n, 1/ and 1/.

决策树学习 x1 1 x2 x3 1 1 1 x4 1 1 1 Decision tree for formula ¬x1¬x3 + x1¬x2x4 + x1x2

决策树学习 Let k-DT be the set of all boolean functions defined by decision trees of depth at most k

决策树学习 true x1¬x3 ¬x1x2x5 ¬x3¬x4 true false 1

决策树学习 Let k-DL be the set of all boolean functions defined by decision lists containing clauses contatining at most k literals. Theorem [R.Rivest] For any positive integer k the class of k-DL formulas is polynomially PAC-learnable.

决策树学习 k-CNF k-DNF k-CNFk-DNF k-clause-CNF k-term-DNF k-DT k-clause-CNF and k-term-DNF are not learnable in their “own” hypotheses space!

Question! Thank You Intelligence Science http://www.intsci.ac.cn/ NN 1 10-00 Thank You Question! Intelligence Science http://www.intsci.ac.cn/ 2018/11/16 史忠植 智能科学 Elene Marchiori