首页 | 本学科首页   官方微博 | 高级检索  
     


Fast Theta-Subsumption with Constraint Satisfaction Algorithms
Authors:Maloberti  Jérôme  Sebag   Michèle
Affiliation:(1) Laboratoire de Recherche en Informatique, CNRS UMR 8623, Bât 490, Université Paris-Sud, F-91405, Orsay
Abstract:Relational learning and Inductive Logic Programming (ILP) commonly use as covering test the theta-subsumption test defined by Plotkin. Based on a reformulation of theta-subsumption as a binary constraint satisfaction problem, this paper describes a novel theta-subsumption algorithm named Django,1 which combines well-known CSP procedures and theta-subsumption-specific data structures. Django is validated using the stochastic complexity framework developed in CSPs, and imported in ILP by Giordana et Saitta. Principled and extensive experiments within this framework show that Django improves on earlier theta-subsumption algorithms by several orders of magnitude, and that different procedures are better at different regions of the stochastic complexity landscape. These experiments allow for building a control layer over Django, termed Meta-Django, which determines the best procedures to use depending on the order parameters of the theta-subsumption problem instance. The performance gains and good scalability of Django and Meta-Django are finally demonstrated on a real-world ILP task (emulating the search for frequent clauses in the mutagenesis domain) though the smaller size of the problems results in smaller gain factors (ranging from 2.5 to 30).
Keywords:relational learning  constraint satisfaction  phase transition  meta-learning  k-locality
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号