Apprentissage relationnel polynomial pour la classification d'arbres

Résumé : Après avoir rappelé le cadre général de la programmation logique inductive, nous proposons une sous-famille des clauses de Horn nommée MQD. Visant des applications de classification de document XML, nous définissons un langage de clauses permettant de représenter des arbres et des motifs d'arbres. Ce langage nous fournit exemples et hypothèses. Nous montrons que ce langage est inclus dans les MQD et proposons des algorithmes dédiés pour les opérations de base nécessaires à l'apprentissage, à savoir les calculs de theta-subsomption et de moindre généralisé. Nos algorithmes étant polynomiaux et non exponentiels comme dans le cas général des clauses de Horn, ils peuvent participer à la classification supervisée d'arbres, l'apprentissage relationnel devenant alors de complexité polynomiale.