人工智能基础-高济-25282AI-14本

人工智能基础,浙江大学计算机学院高济,6.2示例学习,归纳学习从教师或环境提供的事例中抽象出结论（对于概念的泛化描述）的知识获取过程。归纳推理的理论研究如何运用各种推理技术，在符号表示的空间中进行启发式搜索。常用推理技术：泛化(generalizing)特化(specializing)转换(transforming)知识表示的修正和提炼(correcting&refining)主要内容：示例学习的基本策略概念描述的搜索和获取三种示例学习策略：逐步泛化的学习策略逐步特化的学习策略双向学习策略。示例学习的一个变种决策树学习算法ID3,6.2.1示例学习的基本策略,示例学习是机器学习中研究得最深入的一种方法。结构化概念学习程序：七十年代中期，温斯顿(Winston)，积木块玩具世界的线条画；近似匹配、概念泛化和概念特化技术；从一系列正、反示例中归纳出某类积木块（例如拱形物）的概念定义：表示为语义网络的结构化描述。示例学习遵从一般的归纳推理模式:已知：）关于观察（观察到的事例）的描述；）初始的归纳断言；）问题域的背景知识；求：归纳断言，其应蕴涵关于观察的描述，并满足背景知识。,1概念描述的搜索和获取,解描述通过示例学习获取的知识：完全、一致地包含正、反例子集的概念描述：概括（覆盖）所有正例的概念描述，称为完全描述；不概括任何反例的概念描述则称为一致描述。一般情况下，解描述可以有无数个。背景知识提供约束和评判标准使归纳推理的结果集中于一个或几个有限的最优假设。例子空间和假设空间：例子空间所有可能的正、反例构成的空间；假设空间（又称概念空间）所有可能的概念描述（称为假设）构成的空间；假设空间中的每一假设都对应于例子空间中的一个子集，使得该子集中的例子均是该假设的例子。假设的泛化和特化：假设D2是D1的泛化D1所对应的例子集是D2所对应例子集的子集，假设D1是D2的特化。泛化关系反对称、可传递的，假设空间是半序集（偏序集）。示例学习的过程在假设空间（概念空间）中搜索的过程，米切尔（T.Mitchell,1982）。,1概念描述的搜索和获取,病态细胞的分类识别例：正例三个病细胞(P1,P2,P3)，反例二个正常细胞(N1,N2)；每个细胞由二个细胞体组成：细胞体表示为三元组：（核数、尾数、染色状），P1：(2,2,深)(1,1,浅)。学习任务从例子集中归纳出有病状的细胞概念描述。假设不必给每个特性（属性）都指明应取值：没有给出值的特性（以？指示）对于该概念的描述无关紧要；病细胞假设()：(2,?,?)(?,1,深)，一个细胞体有二个胞核；另一个有一个尾巴，且染色是深的。,1概念描述的搜索和获取,病细胞假设空间的半序图（图6.5）：图6.5假设之间的关系弧指示泛化/特化关系，假设空间上的一个泛化/特化关系（图6.4）：假设（）不考虑细胞体是否有尾巴，比假设（）复盖更多的例子；假设（）比假设（）泛化；假设（）比假设（）特化。底层假设最特化（具体）的概念描述：所有特性都给定特别值，图6.4对应于例子空间中的一个例子。顶层假设最泛化的概念描述：不指定任何具体的特性值，表示为(?)，(?)。,1概念描述的搜索和获取,假设空间中的搜索方式：特化搜索从最泛化的假设（概念描述）出发，每次取用一个新的例子，就产生一些特化的描述，直到将初始最泛化的假设特化为解描述。泛化搜索从最特化的假设（相应于例子空间中的一个例子）开始，每次取用一个新的例子时，就产生一些泛化的描述，直到产生出足够泛化的解描述。大多数示例学习方法都采用这二种方法或这二种方法的结合。2逐步泛化的学习策略采用宽度优先、自底向上的搜索方式：将第一个正例（P1）作为初始假设（H1）极端特化的假设；正例（P2）用于指导系统生成泛化的假设（H2和H3）：多个泛化的假设不同的映射会导致不同的假设，假设H1中包含了二个对象（细胞体）；采用保守原则最低限度的泛化：新的假设刚好覆盖现有的假设/例子。,2逐步泛化的学习策略,反例（N1）用来剪裁过于泛化的假设：图6.6H3是过于泛化的假设，因为其蕴涵了反例N1。基本策略：遇见正例就泛化某些假设以保证假设的完全描述性,遇见反例则删去某些假设以保证假设的一致描述性,直至得到一个既完全又一致的解描述(假设)为止。这个解描述作为满足给定例子集的概念定义学习系统获得的新知识。实现逐步泛化学习策略的算法。,3逐步特化的学习策略,采用宽度优先、自顶向下的搜索方式（与泛化策略相反）：新例子的加入会导致新假设的增加和已存在假设的删除（与泛化策略类似）。正例和反例所起的作用与泛化策略相反：反例生成一些特化假设；采用保守的原则最低限度的特化：新的假设在覆盖已有正例的同时只是刚好能排斥反例；正例剪裁过于特化的假设。实现逐步特化学习策略的算法（参见书上）。以特化策略获得的解描述（学习系统期望的概念描述）是特化程度最低的；以泛化策略获得的解描述则是泛化程度最低的；只要给出充分多的例子，二者的结果应是相同的概念描述。,4双向学习策略,将上述二种策略结合起来,同时从二个方向搜索假设（概念描述）空间；以期获得仅用单一策略所不具有的优点。版本空间法（米切尔）：用两个假设集、分别表示作泛化、特化搜索的假设空间。遇见一个新的正例时，如未被集包含，则在该集中进行泛化搜索；一个新的反例产生时，如被集包含，则在该集中进行特化搜索。和指示期望获取的最终解描述的上、下界，当、合一时，合一的解描述就是期望学到的概念描述（定义）。版本空间法的特点：系统不必保留正例和反例：本身蕴涵了已取用的所有正例，可用来删除集中过于特化的假设；本身蕴涵了对所有已取用反例的排斥，可用来消除集中过于泛化的假设。系统知道何时推理任务完成，即当、合一时。实现双向学习策略的算法（参见书上）。,6.2.2决策树构造法ID3,任务对大的例子集作分类概念的归纳定义：例子用无结构的属性-值对来表示：每一个例子用相同的一组属性来表示，每一个属性又有自身的属性值集；构造决策树的目的是为了对事物作出正确的分类；ID3昆兰（J.R.Quinlan，1986）。学习的结果决策树：判别树，转而表示为决策规则的一个集合，用于区分待识别事物的类属。决策树构成：非叶节点对应一个需测试的属性，每个分叉就是该属性可能的取值，树的叶节点指示一个例子事物的类别。,6.2.2决策树构造法ID3,优点归纳学习花费的时间和所给任务的困难度成线性增长关系：例子个数，对象的属性个数，所学习概念的复杂度决策树的节点数。人分类例（图6.11）：预先定义一组属性及其可取值：高度高，矮，发色黑色,红色，金色和眼睛兰色，棕色；人分为两类，分别以、来指示；选取属性“发色”为树的根节点：三值三个对象子集（分支）；按属性“眼睛”划分“金色”这一分支（对象子集）：二值对应于兰色和棕色的对象子集；二级决策树生成所有叶结点相应的对象子集只含同一类的对象；带有类别名的决策树用相应的类别名（和）来取代各子集（图6.12）。,6.2.2决策树构造法ID3,图6.11,图6.12,6.2.2决策树构造法ID3,属性的优先选用决策：选择一系列有用的属性来测试一个对象集，以使生成的决策树是最小的；香农（Shannon）信息论中的方法：决策树可看成一个信息源给定一个要检测的对象，可从决策树产生一个该对象所属类别的消息(比如类别+或-)。对给定的物体集C：M(C)从C集对应的决策树中得到消息的期望信息量：用于量度判别一个对象的类属所需的测试工作量，决策树传递的不同类别消息的概率用P+(对应于+类)和P-表示(对应于-类)，M(C)=-P+log2P+-P-log2P-，把概率近似地表示为对象类属在示例集中发生的频率。对于人分类例：C集有八个例子，三个为“+”，五为“-”，M(C)=-（3/8)log2(3/8）-（5/8log2(5/8）=0.954bits,6.2.2决策树构造法ID3,对给定的物体集C：B(C，A)按属性A构造决策树后，从树的其余部分得到消息的期望信息量：Ai为属性A的值且是互斥的，属性A将集合C划分为若干个子集的集合C1，C2，.，Cn，M(Ci)从对应于值为Ai的子集Ci，为判别一个对象的类属，能从子决策树中获取消息的期望信息量，期望信息量B(C，A)可通过权值平均而得到（图6.13）:B(C，A)(A值为Ai的概率)*M(Ci)。选定的测试属性应使决策树获得最大的信息增益：M(C)B(C，A)最大。,6.2.2决策树构造法ID3,图6.14以“高度”判别的决策树,6.3基于解释的学习,八十年代中期兴起的新型机器学习方法：通过应用领域理论（领域知识）对单一事例所作的分析，构造满足预定目标概念并遵从可操作准则的一个解释。知识密集型的，可克服归纳学习因缺乏领域知识的引导而面临的问题；与基于大量训练例作归纳推理的数据密集型学习方法不同。基于解释的学习是分析学习的主要方式：利用丰富的领域背景知识，将单一例子（或几个例子）泛化为对目标概念的解释；依赖于演绎推理，产生更有效的问题求解知识，如搜索控制知识；主要目的提高问题的求解效率而非获取新的概念描述。主要内容：基于解释的泛化（EBG，Explanation-basedGeneralization），基于解释学习的若干基本问题。,6.3.1基于解释的泛化（EBG),米切尔(T.Mitchell)，1986EBG的问题描述：给定：目标概念：对于所学概念的一个初始描述（其尚不满足可操作准则）；训练例子：目标概念的一个正例；领域理论：解释训练例子为何是目标概念正例可用的规则和事实集合；可操作准则：学到的知识（对于目标概念的解释）所需遵从的表示形式，以使这些知识能用于问题求解活动。获取：对于目标概念的一个特化描述，其是训练例子的泛化，且满足可操作准则。基于解释的泛化过程（二个阶段）：(1)解释：使用领域理论建立一个证明训练例子满足目标概念定义（初始描述）的解释结构；该结构可表示为一颗证明推理树，又称解释树，其每个分枝的叶节点上的表达式都必须满足可操作准则。(2)泛化：通过将解释结构中的常量变换为变量（实现对于训练例子的泛化），获得对于目标概念的一个特化描述，使其满足可操作准则：基于解释结构对目标概念进行回归(regressing)，对回归所得的表达式（相应于解释结构中的叶节点）加以合取。,6.3.1基于解释的泛化（EBG),EBG的第一个阶段（即解释阶段）：确定例子的哪些特性与目标概念有关，哪些特性是无关的，建立关于训练例子如何满足目标概念的一个解释：解释结构：一个证明演绎推理过程。,第二阶段（泛化阶段）：在解释结构中对目标概念Safetostack(x，y)进行回归（图6.16）；自顶向下地遵从解释结构去逆向应用推理规则；使目标概念回归到能推出它的泛化的（常量变换为变量）初始条件（相应于解释结构中的叶节点）；建立目标概念的特化描述：满足可操作准则，目标概念Safetostack(x，y)的充分解释，初始的目标概念是这个特化描述的推理结论。,6.3.1基于解释的泛化（EBG),EBG的重要特性：学习活动特别依赖于学习程序已经知道了什么:EBG方法对它的领域理论是高度依赖的，EBG方法是依赖领域理论中的知识对例子进行解释的。领域理论中知识结构的缺陷可能导致解释失败，从而EBG过程失败。规则矛盾、规则遗漏（不完全）等。可操作准则是学习程度的重要指标。本例中的可操作准则是静态（即不随系统性能的改善而变化）和离散的（即只将表达式分为可操作和不可操作二种）。为了提高利用（识别）目标描述的效率，可操作准则应可以随系统性能的提高而变化。,6.3.2基于解释学习的若干基本问题