基于高阶逻辑的复杂结构归纳学习研究

归纳学习的目的在于发现样例与离散的类之间的映射关系,样例及归纳的映射都需用某个形式化语言描述.归纳学习器采用的形式化语言经历了属性-值语言、一阶逻辑、类型化的高阶逻辑三个阶段,后者能克服前二者在知识表达及学习过程中的很多缺点.本文首先阐述了基于高阶逻辑的复杂结构归纳学习产生的历史背景;其次介绍了基于高阶逻辑的编程语言--Escher的知识描述形式及目前已提出的三种学习方法;复杂结构的归纳学习在机器学习领域的应用及如何解决一些现实问题的讨论随后给出; 最后分析了复杂结构归纳学习的研究所面临的挑战性问题.     

基于高阶逻辑的复杂结构数据半监督聚类

半监督聚类近年来成为了机器学习和数据挖掘领域的研究热点.目前存在的半监督聚类方法都采用属性-值的知识表示方式.但属性-值语言在表示复杂结构数据时存在很多弊端,而基于高阶逻辑的知识表示语言Escher能较好地表示复杂结构数据.在Fscher的知识表示方式下,首先当先验知识是实例之间的约束信息时,提出了搜索K-Means算法的K个初始质心的方法;其次,时先验知识不完全、能够发现的初始质心的个数,r小于K的情况,提出了搜索其余的K-r个初始质心的算法MSS-KMeans和SMSS-KMeans;最后在复杂结构数据集上,验证了所提算法的可行性.最终的实验结果表明,基于高阶逻辑知识表示方式的丰监督聚类方法要优于基于属性-值语言的半监督聚类方法.     

归纳逻辑程序设计方法综述

归纳逻辑程序设计是机器学习与逻辑程序设计交叉所形成的一个研究领域,克服了传统机器学习方法的两个主要限制：即知识表示的限制和背景知识利用的限制,成为机器学习的前沿研究课题。首先从归纳逻辑程序设计的产生背景、定义、应用领域及问题背景介绍了归纳逻辑程序设计系统的概貌,对归纳逻辑程序设计方法的研究现状进行了总结和分析,最后探讨了该领域的进一步的研究方向。     

归纳逻辑程序设计综述

归纳逻辑程序设计(inductive logic programming, ILP)是以一阶逻辑归纳理论为基础,并以一阶逻辑为表达语言的符号规则学习方法. ILP学得的模型是易于理解的一阶逻辑符号规则,而非难以解释的黑箱模型;在学习中可以相对容易地显式利用以一阶逻辑描述的领域知识;学得模型能对领域中个体间的关系进行建模,而非仅仅对个体的标记进行预测. 然而,由于潜在假设空间巨大,进行高效学习有相当的困难.综述了ILP领域的研究情况,从不同一阶逻辑归纳理论的角度对主流的ILP方法做出了梳理.还介绍了近年来ILP基于二阶诱导推理理论的扩展、基于概率的扩展和引入可微构件的扩展.最后,介绍了ILP在实际任务中的代表性应用,探讨了ILP方法目前所遇到的挑战,并对其未来发展进行了展望.     

面向知识图谱补全的归纳学习研究综述

知识图谱补全能够使知识图谱更加完整。然而,传统的知识图谱补全方法假定在测试时所有实体和关系都出现在训练过程,由于现实世界知识图谱的演变性质,一旦出现不可见实体或不可见关系,就需要重新训练知识图谱。面向知识图谱补全的归纳学习旨在补全包含不可见实体或不可见关系的三元组,而无需从头开始训练知识图谱,因此近年来受到广泛关注。首先从知识图谱的基本概念出发,将知识图谱补全分为两大类,直推式和归纳式;其次从归纳式的知识图谱补全的理论角度出发,分为半归纳和全归纳这两类,并从该角度对模型进行总结归纳;然后从归纳式的知识图谱补全的技术角度出发,分为基于结构信息和基于额外信息这两大类,将基于结构信息的方法细分为基于归纳嵌入、基于逻辑规则和基于元学习这三类,将基于额外信息的方法细分为基于文本信息和其他信息这两类,并对当下方法进一步深入细分、分析和对比;最后对未来的研究方向进行展望。     

SMap:基于语义的关系数据库模式与OWL本体间映射方法

伴随语义网的发展,语义网本体数量激增.然而万维网上绝大多数的数据仍存储在关系数据库中.建立关系数据库模式与语义网本体间的映射是一种实现两者之间互操作性的有效途径.因此,提出了一种基于语义的关系数据库模式与OWL本体间的映射方法SMap,包含简单映射发现和复杂映射学习两个阶段.在简单映射发现阶段,首先通过逆向工程规则将关系数据库模式和本体中的元素对应地分为不同类别,再为每个元素构建虚拟文档并计算它们之间的相似度,其中针对不同类别的元素设计了不同的虚拟文档抽取方案.在复杂映射学习阶段,基于已发现的简单映射以及重叠的数据库记录和本体实例,自动化地生成训练事实数据,然后运用归纳逻辑编程算法学习出多种类型的基于Horn规则的复杂映射.真实数据集上的实验结果表明,SMap在简单映射发现和复杂映射学习上均明显优于现有的关系数据库模式与本体间映射方法.     

高阶逻辑下知识表示与聚类方法的研究*

针对一阶逻辑在复杂结构数据环境中存在模式搜索空间庞大和不能发明新谓词的缺点,提出了使用类型化的高阶逻辑知识表示语言Escher去表示各种复杂结构的数据,利用其强类型语法有效地约束知识发现过程中模式的搜索空间和高阶的特点去解决新谓词构造的问题。设计了以Escher为基础的复杂结构数据中的知识发现过程和基于复杂结构数据的聚类算法,并以实验验证了其有效性。     

基于位串编码的遗传归纳逻辑程序设计

归纳逻辑程序设计是基于一阶逻辑的数据挖掘新方法。一阶规则挖掘是目标谓词和背景知识谓词对应的各种原子的复杂组合优化问题。该文根据Occam’s razor原理提出原子的位串编码,设计相应的遗传箅子,基于sequential covering策略提出采用遗传算法作为搜索策略的遗传归纳逻辑程序设计算法GILP。在连通图问题和gcd问题上验证算法的可行性。     

基于归纳逻辑程序设计的学习方法及其实现的研究

归纳逻辑程序设计是机器学习领域中的一个新方法，它研究的是从实例和背景知识进行逻辑程序（新知识）的构造．本文介绍了归纳逻辑程序设计的基本理论和方法，并介绍了这种学习方法在专家系统中的应用情况．     

约束归纳逻辑程序设计方法的研究

提出了一种新的约束归纳逻辑程序设计方法。该方法能够与自顶向下的归纳逻辑程序设计系统结合,通过在自顶向下归纳方法的一步特殊化操作中引入Fisher判别分析等方法,使得系统能够导出不受变量个数限制的多种形式的线性约束,在不需要用户诱导,不依赖约束求解器的情况下,学习出覆盖正例而排斥负例的含约束的Horn子句程序。     

Relational Reinforcement Learning

Relational reinforcement learning is presented, a learning technique that combines reinforcement learning with relational learning or inductive logic programming. Due to the use of a more expressive representation language to represent states, actions and Q-functions, relational reinforcement learning can be potentially applied to a new range of learning tasks. One such task that we investigate is planning in the blocks world, where it is assumed that the effects of the actions are unknown to the agent and the agent has to learn a policy. Within this simple domain we show that relational reinforcement learning solves some existing problems with reinforcement learning. In particular, relational reinforcement learning allows us to employ structural representations, to abstract from specific goals pursued and to exploit the results of previous learning phases when addressing new (more complex) situations.     

Confirmation-Guided Discovery of First-Order Rules with Tertius

This paper deals with learning first-order logic rules from data lacking an explicit classification predicate. Consequently, the learned rules are not restricted to predicate definitions as in supervised inductive logic programming. First-order logic offers the ability to deal with structured, multi-relational knowledge. Possible applications include first-order knowledge discovery, induction of integrity constraints in databases, multiple predicate learning, and learning mixed theories of predicate definitions and integrity constraints. One of the contributions of our work is a heuristic measure of confirmation, trading off novelty and satisfaction of the rule. The approach has been implemented in the Tertius system. The system performs an optimal best-first search, finding the k most confirmed hypotheses, and includes a non-redundant refinement operator to avoid duplicates in the search. Tertius can be adapted to many different domains by tuning its parameters, and it can deal either with individual-based representations by upgrading propositional representations to first-order, or with general logical rules. We describe a number of experiments demonstrating the feasibility and flexibility of our approach.     

Separate-and-Conquer Rule Learning

This paper is a survey of inductive rule learning algorithms that use a separate-and-conquer strategy. This strategy can be traced back to the AQ learning system and still enjoys popularity as can be seen from its frequent use in inductive logic programming systems. We will put this wide variety of algorithms into a single framework and analyze them along three different dimensions, namely their search, language and overfitting avoidance biases.     

关系tri-training:利用无标记数据学习一阶规则

针对目前归纳逻辑程序设计(inductive logic programming,ILP)系统要求训练数据充分且无法利用无标记数据的不足,提出了一种利用无标记数据学习一阶规则的算法——关系tri-training(relational-tri-training,R-tri-training)算法。该算法将基于命题逻辑表示的半监督学习算法tri-training的思想引入到基于一阶逻辑表示的ILP系统,在ILP框架下研究如何利用无标记样例信息辅助分类器训练。R-tri-training算法首先根据标记数据和背景知识初始化三个不同的ILP系统,然后迭代地用无标记样例对三个分类器进行精化,即如果两个分类器对一个无标记样例的标记结果一致,则在一定条件下该样例将被标记给另一个分类器作为新的训练样例。标准数据集上实验结果表明:R-tri-training能有效地利用无标记数据提高学习性能,且R-tri-training算法性能优于GILP(genetic inductive logic programming)、NFOIL、KFOIL和ALEPH。     

基于归结的最大一般理论特化

提出一种基于归结的并有关于背景适应吸示例的一致特化理论,该理论给出了最大一般特化假设的归结构造方法,可将其作为一种蕴涵意义下的一般理论特化框架。基于该理论,进一步提出ｋ一般特化概念以解决特化的可计算性问题,并相应地给出特化算法。有关实验表明,该理论与算法能够正确并有效地进行一阶理论特化。     

A Polynomial Approach to the Constructive Induction of Structural Knowledge

The representation formalism as well as the representation language is of great importance for the success of machine learning. The representation formalism should be expressive, efficient, useful, and applicable. First-order logic needs to be restricted in order to be efficient for inductive and deductive reasoning. In the field of knowledge representation, term subsumption formalisms have been developed which are efficient and expressive. In this article, a learning algorithm, KLUSTER, is described that represents concept definitions in this formalism. KLUSTER enhances the representation language if this is necessary for the discrimination of concepts. Hence, KLUSTER is a constructive induction program. KLUSTER builds the most specific generalization and a most general discrimination in polynomial time. It embeds these concept learning problems into the overall task of learning a hierarchy of concepts.     

The Utility of Knowledge in Inductive Learning

In this paper, we demonstrate how different forms of background knowledge can be integrated with an inductive method for generating function-free Horn clause rules. Furthermore, we evaluate, both theoretically and empirically, the effect that these forms of knowledge have on the cost and accuracy of learning. Lastly, we demonstrate that a hybrid explanation-based and inductive learning method can advantageously use an approximate domain theory, even when this theory is incorrect and incomplete.     

基于模糊理论扩充的归纳学习方法和思想

归纳学习是机器学习最重要、最核心也是最成熟的一个分支，但在应用归纳学习所获得的知识以及改进归纳学习算法等方面存在着很多传统方法难以解决的问题。本文从归纳学习的本质--归纳依赖于数据间的相似性出发，尝试将能够较好地定量反映数据间相似性程度的模糊理论应用到归纳学习中去，为归纳学习和机器学习找出一个新的研究方法和思路。