Improving inductive logic programming with constraint satisfaction techniques : applications to frequent query discovery
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
The work presented aims at a principled integration of constraint satisfaction problems (csp) algorithms for inductive logic programming (ilp) and relational data-mining, based on the fact that the theta-subsumption test, intensively used for assessing relational hypotheses and queries, is equivalent to a csp problem. Three algorithms are presented: django, which combines prominent csp procedures (forward checking, arc consistency, dynamic variable ordering) and heuristics (first fail principle) to achieve theta-subsumption, jivaro, built on the top of django, achieves clause reduction by exploiting the theta-subsumption of the clause by itself, and jimi, built on the top of jivaro and django, ensures a non-redundant search for frequent queries in a datalog database. Csp and theta-subsumption both have an exponential worst casecomplexity, thus django is evaluated after the so-called phase transition framework, which has been imported from the csp (cheeseman and kanefsky 1991) to the ilp setting by giordana and saitta(2000). In this framework, the focus is shifted from a worst-case complexity analysis to a statistical complexity analysis. Experiments on large-size artificial, and real-world datasets, show an improvement on the state of the art by two or more orders of magnitude.
Abstract FR:
Le travail presente vise a l'integration d'algorithmes de problemes de satisfaction de contraintes (psc) en programmation logique inductive (pli) et en fouille de donnees relationnelles. Cette integration est fondee sur le fait que le test de theta-subsomption, intensivement utilise pour evaluer des hypotheses et des requetes relationnelles, est equivalent a un psc. Trois algorithmes sont presentes : django, un algorithme de theta-subsomption qui combine des procedures (forward checking, coherence par arc, ordonnancement dynamique des variables) et des heuristiques (first fail principle) classiques en psc, jivaro, base sur django, permet la reduction d'une clause en utilisant la theta-subsomption de cette clause sur elle-meme, et jimi, construit sur jivaro et django, recherche iterativement les motifs frequents dans une base de donnees en datalog. Les psc et la theta-subsomption ayant tous les deux une complexite dans le pire cas exponentielle, django est evalue en utilisant le cadre de la transition de phase, qui a ete initialement decouverte dans les psc (cheeseman et kanefsky 1991), giordana et saitta (2000) ayant montre que la transition de phase etait egalement presente den pli. Dans ce cadre experimental, le probleme est deplace d'une analyse dans le pire cas, vers une analyse statistique. Des experimentations sur des problemes de grande taille artificiellement engendres ainsi que des problemes reels, montrent une amelioration sur l'etat de l'art d'un ou plusieurs ordres de grandeur.