Learning search-control heuristics for logic programs: Applications tospeed-up learning and languageacquisitions

摘要: This paper presents a general framework, learning search-control heuristics for logic programs, which can be used to improve both the e ciency and accuracy of knowledgebased systems expressed as de nite-clause logic programs. The approach combines techniques of explanation-based learning and recent advances in inductive logic programming to learn clause-selection heuristics that guide program execution. Two speci c applications of this framework are detailed: dynamic optimization of Prolog programs (improving e ciency) and natural language acquisition (improving accuracy). In the area of program optimization, a prototype system, Dolphin is able to transform some intractable speci cations into polynomial-time algorithms, and outperforms competing approaches in several benchmark speedup domains. A prototype language acquisition system, Chill is also described. It is capable of automatically acquiring semantic grammars, which uniformly incorprate syntactic and semantic constraints to parse sentences into case-role representations. Initial experiments show that this approach is able to construct accurate parsers which generalize well to novel sentences and signi cantly outperform previous approaches to learning case-role mapping based on connectionist techniques. Planned extensions of the general framework and the speci c applications as well as plans for further evaluation are also discussed.