归纳逻辑编程通常泛指根据给定的样例归纳学习出一阶逻辑规则,并以一段Prolog程序表示其学习结果。Prolog语言是一个通用的、图灵等价的程序设计语言,其强大的自动回溯机制使其在匹配搜索的问题上优势明显,通过归纳习得Prolog程序的解释器被称为Prolog元解释器。元解释学习是目前最先进的归纳逻辑编程学习器的核心部分,与其他归纳逻辑编程系统不同的是,它是一种支持谓词发明和学习递归逻辑的学习框架。通过该框架所习得的逻辑子句会由修改后的Prolog元解释器构建成一组逻辑替代,并最终形成逻辑程序。元解释学习器的工作原理是通过给定的目标以及背景知识归纳出一个程序,将目标和一个可用的一阶子句的头统一起来,统一后的子句主体中的原子将成为受同一约束的新目标。元解释学习的另一个特别之处在于,它引入了元规则作为规范假设形式的强约束。元规则不仅可以降低假设程序的文本复杂性,而且它的合理使用还有助于学习效率的提高。元解释学习器对假设空间的搜索方式是最左深度优先搜索,对给定的受限子句、背景知识以及元规则进行组合排列,并按顺序合一匹配,直到找到一个满足所有正例、拒绝所有反例的假设程序。而暴力搜索的效率问题一直都是热点问题。本文以提高元解释学习的搜索效率为目的,对该框架进行研究并提出了改进方法。本文的主要工作如下:1.验证了元解释学习技术在搜索假设空间时存在冗余搜索的问题。元规则是元解释学习器学习目标程序时的强约束,它规范了假设程序的形式,但同时也带来了一些潜在问题。首先,本文通过对元规则在学习过程中充当的角色进行分析,指出了中间搜索过程存在冗余搜索的可能性。然后,通过对一个具体案例的学习过程进行解析,验证了元解释学习器在学习目标时,存在重复学习同一个状态的问题。2.提出了回溯+“备忘录”的优化算法并实现了Metamemo系统。基于元解释学习框架的深度优先搜索机制不能改变,本文采用空间换时间的思想,提出了用“备忘录”优化学习过程。首先,记录搜索过程中已经匹配过的结点状态。接下来,在开启新一轮搜索之前,先检查该结点的状态是否已经存在于备忘录。如果检查结果为真,那么直接丢弃掉针对当前结点的后续工作,回到决策点;如果检查结果为假,那么先保存该结点状态,然后继续学习。3.通过实验比较Metagol与Metamemo系统,展示了优化算法的优势。实验结果以预测准确率和学习时间作为参考标准,通过对比多个案例的参数指标,证实在保证预测准确率的前提下,本文提出的算法使得元解释学习的效率提高。