粗集和多关系学习综述

文中给出了多关系学习的产生、实质以及任务,指出多关系学习具有狭义和广义两个层面。对粗集和多关系学习给出了简单综述,表明粗集理论在多关系学习中占有重要地位。分析研究了粗集和归纳逻辑程序设计方法用于多关系学习的几种结合途径,尤其重点介绍了RSILP系列模型,并在文中给出其一般模型。文中对用于多关系学习中其它粗集方法也作了简单介绍。RSILP模型的完善扩展以及粗集方法在多关系学习中的进一步应用是今后的工作方向。     

基于多核学习的双稀疏关系学习算法

在关系学习中样本无法在R n空间中表示.与其他机器学习问题有很大不同,因为无法利用R n空间的几何结构使得其解决异常困难.将多核学习方法用于关系学习中. 首先,可以证明当用逻辑规则生成的核矩阵进行多核学习时,其他核都可以等价转化为线性核.在此基础上,通过用修正FOIL算法迭代生成规则,构造相应的线性核然后进行多核优化,由此实现了由规则诱导出的特征空间上的线性分类器.算法具有"双稀疏"特性,即:可以同时得到支持向量和支持规则.此外,可以证明在规则诱导出的特征空间上的多核学习可以转化为平方l1 SVM,这是首次提出的新型SVM算法.在6个生物化学和化学信息数据集上与其他算法进行了对比实验.结果表明不仅预测准确率有明显提高,而且得到的规则集数目更小,解释更为直接.     

基于差异半监督学习的相关理论分析

基于差异的半监督学习属于半监督学习和集成学习的结合,是近年来机器学习领域的研究热点.但相关的理论研究较缺乏,且都未考虑存在分布噪声的情况.文中首先针对基于差异的半监督学习的特点,定义一种分类噪声和分布噪声的混合噪声(HCAD).其次给出算法在HCAD噪声下的可能近似正确(PAC)理论分析及其应用实例.最后基于投票边缘函数,推导出在HCAD噪声下多分类器系统的泛化误差上界,并给出相关证明.文中开展的理论研究可用于设计基于差异的半监督学习算法及评估算法的泛化能力,具有广阔的应用前景.     

多关系数据挖掘方法研究*

目前大多数数据挖掘方法是从单关系中发现模式,而多关系数据挖掘（MRDM）则可直接从关系数据库的多表中抽取有效模式。MRDM可以解决原有命题数据挖掘方法不能解决的问题,它不仅有更强的信息表示能力,可以表示和发现更复杂的模式,还可以在挖掘进程中有效地利用背景知识来提高挖掘效率和准确率。近年来,借鉴归纳逻辑程序设计（ILP）技术,已经形成许多多关系数据挖掘方法,如关系关联规则挖掘方法、关系分类聚类方法等。     

一种基于ILP和ASP的学习B语言描述的动作模型方法

动作模型学习可以使Agent主动适应动态环境中的变化,从而提高Agent的自治性,同时也可为动态域建模提供一个初步模型,为后期的模型完善和修改提供了基础.通过结合归纳逻辑程序设计(Inductive Logic Program-ming,ILP)和回答集程序设计(Answer Set Programming,ASP),设计了一个学习B语言描述的动作模型算法,该算法可以在混合规模的动态域中进行学习,并采用经典规划实例验证了该学习算法的有效性.     

从规划解中学习一阶派生谓词规则

派生谓词是描述动作非直接效果的主要方式.但是由人类专家设计的派生谓词规则(即领域理论)不能保证总是正确或者完备的,因此有时很难解释一个观察到的规划解为什么是有效的.结合归纳学习与分析学习的优点,文中提出一种称为FODRL(First-Order Derived Rules Learning)的算法,在不完美的初始领域理论的引导下从观察到的规划解中学习一阶派生谓词规则.FODRL基于归纳学习算法FOIL(First-Order Inductive Learning),最主要的改进是可以使用派生谓词的激活集来扩大搜索步,从而提高学习到的规则的精确度.学习过程分为两个步骤:先从规划解中提取训练例,然后学习能够最好拟合训练例和初始领域理论的一阶规则集.在PSR和PROME-LA两个派生规划领域进行实验,结果表明,在大部分情况下FODRL比FOIL(甚至包括其变型算法FOCL)学习到的规则的精确度都要高.     

基于低秩表示的标记分布学习算法

针对标记分布学习算法忽略标记相关性信息及数据存在异常和噪声值的情况,文中提出基于低秩表示的标记分布学习算法(LDL-LRR).利用特征空间的基线性表示样本信息,实现对原始特征空间数据的降维.将低轶表示(LRR)迁移至标记空间,对模型施加低秩约束,把握数据的全局结构.分别使用增广拉格朗日乘子法和拟牛顿法求解LRR和目标函数,再通过最大熵模型预测标记分布.在10个数据集上的对比实验表明,LDL-LRR性能良好,效果稳定.     

统计关系学习模型Markov逻辑网综述*

统计关系学习是人工智能研究的热点,在生物信息学、地理信息系统和自然语言理解等领域有着重要应用,Markov逻辑网是将Markov网与一阶逻辑相结合的一种全新的统计关系学习模型。介绍了Markov逻辑网的理论模型和学习方法,并探讨了目前存在的问题和研究方向。     

序关系优化的多超平面排序学习模型

在经典排序学习模型RankSVM的基础上,提出一种序关系优化的多超平面排序模型。该模型首先根据训练数据所属等级之间的序关系进行多个超平面的构建,然后将多个超平面得到的排序列表进行聚合获得最终的排序结果。在LETOR OHSUMED数据集上对所提出的模型进行实验测试,使用信息检索领域的多个经典指标对模型的性能进行评测,并与RankSVM等方法进行比较。实验结果显示该模型不仅获得更优的排序性能,而且能显著缩短训练时间。     

一种面向数据学习的快速PCA算法

高维数据的主成分分析较难处理,因为计算时间和空间复杂度随着数据维数的增加而急剧增加.文中提出一种直接面向数据学习的PCA算法,即在迭代中新的权向量等于所有样本向量的加权和,因而不需要计算数据协方差矩阵.在解决给定样本向量或平稳随机过程的PCA问题时,该算法能够弥补目前批最算法和增量算法存在的不足.此外,在理论上证明该算法的收敛性.实验结果表明,该算法能在很少迭代次数内迅速收敛到精确解.     

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.     

归纳逻辑程序设计综述

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

Unsupervised Learning of Word Segmentation Rules with Genetic Algorithms and Inductive Logic Programming

This article presents a combination of unsupervised and supervised learning techniques for the generation of word segmentation rules from a raw list of words. First, a language bias for word segmentation is introduced and a simple genetic algorithm is used in the search for a segmentation that corresponds to the best bias value. In the second phase, the words segmented by the genetic algorithm are used as an input for the first order decision list learner CLOG. The result is a set of first order rules which can be used for segmentation of unseen words. When applied on either the training data or unseen data, these rules produce segmentations which are linguistically meaningful, and to a large degree conforming to the annotation provided.     

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.     

约束归纳逻辑程序设计系统

提出了一种新的约束归纳逻辑程序设计方法,并初步实现了一个自顶向下的约束归纳逻辑程序原型系统。该系统能够导出不受变量个数限制的多种形式的线性约束,得出覆盖正例而排斥负例的含约束的Hom子句程序。     

Predictive Software

We examine the adaptation of classical machine learning selection criteria to ensure or improve the predictiveness of specifications. Moreover, inspired in incremental learning, software construction is also seen as an incremental process which must generate and revise the specification with the main goal of being predictive to requirements evolution. The new goal is not necessarily to achieve the highest accuracy at the end of a first prototype or version, but to maximise the cumulative benefits obtained throughout the entire software life-cycle. This suggests a new software life-cycle, whose main characteristic is to move modifications earlier, by using more eager inductive techniques, and reducing overall modification probability. This new predictive software life-cycle is particularised for the case of (functional) logic programming, placing the deductive/inductive techniques necessary for each stage of the life-cycle. The maturity of each stage and the practical possibilities for a (semi-)automation of the cycle based on declarative techniques are also discussed.     

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.     

Relational Instance-Based Learning with Lists and Terms

The similarity measures used in first-order IBL so far have been limited to the function-free case. In this paper we show that a lot of power can be gained by allowing lists and other terms in the input representation and designing similarity measures that work directly on these structures. We present an improved similarity measure for the first-order instance-based learner ribl that employs the concept of edit distances to efficiently compute distances between lists and terms, discuss its computational and formal properties, and empirically demonstrate its additional power on a problem from the domain of biochemistry. The paper also includes a thorough reconstruction of ribl's overall algorithm.