Improving inductive logic programming with constraint satisfaction techniques : applications to frequent query discovery
Jérôme Maloberti · OpenGrey (Institut de l'Information Scientifique et Technique) · 2005
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.