L'Extraction de Connaissances dans les Bases de Données (ECD)
est un domaine de recherche actuellement très actif.
Une problématique importante pour l'ECD
est l'apprentissage supervisé,
dont le but est de trouver une définition en intension d'un concept
représenté par un ensemble d'exemples étiquetés comme appartenant
ou non à ce concept.
Dans un contexte relationnel, cette tâche,
pour des raisons à la fois théoriques et pratiques,
nécessite l'utilisation de biais pour
adapter l'algorithme d'apprentissage
aux caractéristiques du problème considéré.
Nous proposons un cadre unifié et déclaratif
pour la spécification et l'exploitation des biais sur l'espace des hypothèses.
Notre approche repose sur la définition d'un nouveau formalisme,
qui raffine les grammaires d'arbres par un langage de contraintes.
Nous montrons notamment que ce formalisme
permet de définir l'espace des hypothèses par unions et intersections de biais.
Nous nous intéressons ensuite à l'exploration d'un tel espace,
en étudiant deux approches, l'une déterministe et l'autre stochastique.
Dans la première, nous proposons une nouvelle
définition des opérateurs de raffinement sur les clauses
utilisés en programmation logique inductive.
Cette définition utilise explicitement l'espace des hypothèses et les biais,
ce qui permet un élagage optimal lors de la recherche.
Nous appliquons cette approche à l'ECD,
en utilisant la structure de la base de données pour optimiser la
recherche.
Notre deuxième approche repose sur les algorithmes d'évolution.
Nous montrons que le formalisme des grammaires d'arbres avec contraintes
est particulièrement adapté à la spécification
des biais en programmation génétique.
Il étend en effet l'expressivité des formalismes existants,
permet de modéliser les biais sur la population
initiale, et de contrôler la validité des descendants lors des opérations génétiques.
Nous proposons d'appliquer ce nouveau cadre
pour l'induction de concepts exprimés en Algèbre Relationnelle.
Manuscrit (non définitif) en ps.gz