Meta-Interpretive Learning Based On Path Memo

Inductive logic programming generally refers to learning first-order logic rules based on a given sample,and the expression of the learning result is a Prolog program.Prolog language is a general-purpose,Turing-equivalent programming language.Its powerful automatic backtracking mechanism makes it outstanding in the problem of matching search.The interpreter that can learn Prolog programs by induction is called Prolog meta-interpreter.Meta-interpretive learning is the core part of the most advanced inductive logic programming learner.Unlike other inductive logic programming systems,it is an inductive logic learning framework that supports predicate invention and learning recursive logic programs.The logical clauses learned from this framework are constructed into a set of logic substitution by a modified Prolog meta-interpreter and eventually form a logic program.The working principle of the meta-interpretive learner is to summarize a program by a given goal and background knowledge.It unifies the goal with the head of an available first-order clause,and the atoms in the unified clause body will become new goal which subject to the same procedural constraints.The another feature is that meta-interpretive learning introduces metarules as strong constraints to normalize assumptions.Metarules reduce the textual complexity of hypothetical programs,and their reasonable use can improve learning efficiency.The meta-interpretive learner searches the hypothesis space using the left-most depth-first search.It aligns the given restricted clauses,background knowledge,and metarules until it finds a hypothetical procedure that meets all positive examples and reject all negative examples.The efficiency of violent search has been a hot issue all the time.This paper studys on meta-interpretative learning and put forward the improvement in the purpose of enhancing the search efficiency of it,The main work of this article is as follows: 1.The problem of redundant search in meta-learning learning technology is verified when the learner searchs hypothesis space.The metarules are strong constraints when the meta-interpretative learning framework learns the target program.They regulate the form of the hypothetical program,however,they bring some potential problems.First,this paper analyzes the role of metarules in the search process,and points out the possibility of redundant search in the process.Then,by analyzing the search process of a specific case,it is verified that the meta-interpretative learner has the problem of repeatedly learning the same state when it learns the target.2.An optimization algorithm of backtracking + "memo" is proposed and implemented the Metamemo System.Because the depth-first search mechanism of the meta-interpretative learner can not be changed,this paper makes use of the idea of space for time and a "memo" is used to optimize the search process.First,we need to record the node states that have been matched during the search and save them into a memo.Then,we should check whether the state of the node already exists in the memo before starting a new round of search.If the check result is true,the following work of the current node will be discarded directly and return to the decision point;if the check result is false,we save the state of the node firstly,and then the search is performed.3.Comparing Metagol and Metamemo by experiments,the results show the advantages of this optimization algorithm.The experimental results use predictive accuracy and learning time as reference standards.By comparing multiple experimental parameter indicators,it is confirmed that the algorithm proposed in this paper improves the efficiency of meta-interpretative learning under the premise of ensuring the predictive accuracy is same.