Contraintes & Apprentissage

Domaines de recherche de l'équipe CA : Contraintes et Apprentissage (CA)

On s'intéresse à la sémantique et à l'apprentissage de systèmes de règles exprimées dans un formalisme relationnel. Les domaines d'application sont, par exemple, la mise au point de programmes dans le cadre de la Programmation par Contraintes ou encore l' extraction de connaissances dans des bases de données relationnelles ou avancées (travaux en cours d'une part, dans un projet RNTL, d'autre part, en collaboration avec le BRGM). Les méthodes développées reposent principalement sur des mécanismes de déduction ou d'induction étudiés dans un cadre logique où la notion de contraintes joue un rôle prépondérant. En Apprentissage, les recherches se situent principalement en Programmation Logique Inductive (PLI), domaine qui regroupe les travaux sur l'apprentissage de connaissances exprimées dans un formalisme relationnel. Ce formalisme est particulièrement intéressant pour des Applications à l'Extraction de Connaissances dans les Bases de Données (ECD), car il prend en compte la nature relationnelle des données. Cependant, les applications réelles imposent de ne pas traiter seulement des données symboliques mais d'autres types de données : numériques, spatiales, ... Le paradigme de la Programmation par Contraintes semble un cadre naturel pour formaliser l'Apprentissage dans ce contexte, suivant ainsi une évolution similaire à celle de la Programmation Logique.

Thèmes de recherche actuels

Diagnostic déclaratif d'erreurs en Programmation en Logique avec Contraintes

La notion classique de trace s'avère difficilement utilisable à cause de l'imbrication complexe des différents processus qui concourent à la résolution d'un système de contraintes. Un niveau d'abstraction convenable est indispensable, en particulier l'usage d'outils s'appuyant sur une sémantique déclarative, c'est à dire indépendante d'une stratégie particulière de résolution. Une partie importante de nos travaux dans les domaines finis est consacrée au débogage déclaratif de programmes avec contraintes et est menée en relation avec le projet RNTL OADymPPaC. Le travail effectué a pour objectif principal la définition de techniques de mise au point reposant sur la notion d'explication de retrait de valeur, c'est à dire l'explication de l'élimination d'un élément d'un domaine, élément inconsistant en un certain sens. Nous avons proposé une notion d'explication arborescente, qui permet par exemple d'expliquer un échec de façon déclarative et que nous allons utiliser comme fondement pour le diagnostic d'erreur.

Apprentissage automatique de solveurs

La vision du calcul des consistances locales comme enchaînement de règles nous a naturellement conduit à la question de l'apprentissage automatique de ces règles, d'autant plus que la conception des solveurs est une activité difficile rendue de plus en plus complexe par l'émergence de contraintes globales adaptées à des problèmes spécifiques comme l'ordonnancement. C'est le thème du projet "Apprentissage de Solveurs de Contraintes", action "Jeune equipe" du programme ATIP jeunes chercheurs du CNRS.

Etude formelle de l'apprentissage relationnel - Classification

Nous étudions la problématique de l'apprentissage (définition d'une relation de généralité entre clauses contraintes et ses propriétés, algorithmes de recherche) dans le cadre de la Programmation Logique avec Contraintes et des Bases de Données Contraintes, en nous intéressant principalement à la tâche de classification.

Nous étudions les spécificités apportées par les applications à l'ECD, en particulier la prise en compte de la structure de la base de données et les problèmes de complexité. Dans ce cadre, nous avons travaillé sur les méthodes stochastiques de recherche, en particulier la programmation génétique et les algorithmes génétiques. Pour ces derniers, nous avons étudié comment ils pouvaient être appliqués à la propositionnalisation, méthode qui permet de reformuler un problème d'apprentissage spécifié dans un formalisme relationnel en un problème attribut-valeur multi-instances.

Etude des mesures de similarité

Nous étudions les mesures de similarité, importantes que ce soit pour la classification et/ou le regroupement d'objets par similitude. L'idée sous-jacente de nos travaux est que la similarité entre deux objets ne dépend pas seulement des valeurs des attributs des objets, mais plus particulièrement du contexte d'apprentissage, c'est à dire de l'ensemble des définitions de concepts pertinentes pour le problème considéré.

Extraction des règles d'association

La collaboration avec le service Ressources Minérales du BRGM (Bureau de Recherche Géologique et Minière) nous a conduit à étudier la tâche d'extraction de règles d'association. Une phase importante mais coûteuse en temps d'exécution est la découverte des ensembles d'items fréquents. Dans ce contexte, nous avons proposé une nouvelle approche basée sur une représentation booléenne de la base de données, vue comme une table de vérité à n variables n étant le nombre d'items possibles de la base de transactions. Un prototype a été développé et des expérimentations sont en cours.

Caractérisation

La caractérisation est une tâche supervisée de fouille de données permettant de résumer de manière succincte et concise un ensemble de données. Une réflexion sur ce thème a débuté, dans le cadre de la collaboration avec le BRGM, et un prototype est en cours de réalisation, implantant un cadre général d'extraction de règles de caractérisation et s'appliquant aux données géographiques.

Applications de l'apprentissage à la fouille de textes

Nos travaux s'orientent vers l'extraction de connaissances à partir de textes, en nous fondant principalement sur une recherche statistique de récurrences existantes dans un ensemble de textes : associations polylexicales, recherche des concepts liés aux mots clefs d'une requête et des relations entre concepts.

Autres thèmes abordés

• Etude de diverses théories des arbres et contraintes du 1er ordre, en collaboration avec Alain Colmerauer.
• Parallélisme pour les contraintes
• Développement de l'environnement de programmation hypertexte pour la Programmation en Logique avec Contraintes
• Etude des formalismes de spécification de biais de langage en Apprentissage basé sur les grammaires d'arbres et un langage de contraintes
• Etude de la parallélisation d'algorithmes génétiques en nous basant sur le modèle BSP.

Collaborations et autres formes de participation à la recherche

Actions nationales

• CANAR (2006-2009) Cette action constitue un projet non thématique ANR. Elle a pour but d'établir l'état de l'art en acquisition de contraintes et reformulation. Elle est menée en partenariat avec les Universités de Montpellier, Nantes, Caen.
• GD2GS - From Genomic Data To Graph Structure (2005-2008) Semi-supervised learning of structure with statistical and relational approaches: application to the identification of regulatory networks
• BIOTIM (2003-2006) ACI, exploitation de gisement texte-image en biodiversité.
• Résolution de contraintes quantifiées sur les domaines finis (2006-2007) Projet Studium (agence régionale financement)
• "Apprentissage de Solveurs de Contraintes" (2000-2004), action "Jeune equipe" du programme ATIP jeunes chercheurs du CNRS.
• participation au projet RNTL ``Outils pour l'Analyse DYnamique et la Mise au Point de Programmes avec Contraintes'' (OADymPPaC) de 2000 à 2004. Ce projet regroupe quatre partenaires académiques : l'INRIA-Rocquencourt, l'École des Mines de Nantes, l'INSA-IRISA-Renneset le LIFO, et deux partenaires industriels: COSYTEC et ILOG.
• "Apprentissage de Solveurs de Contraintes", action "Jeune equipe" du programme ATIP jeunes chercheurs du CNRS.
• Organisation à Orléans de la Conférence Francophone d'Apprentissage, CAP 2002.
• Organisation à Orléans du séminaire de l'AFPLC (Association Française de Programmation en Logique et par Contraintes) du 18 janvier 2001.
• participation à l'action spécifique GaFoDonnées (Fouille de Bases de Données) du département STIC.
• participation au groupe de travail A3CTE (Applications, Apprentissage, Acquisition de Connaissances à partir de Textes Electroniques)

Actions europénnes

• LEarnIng Lexical Associations (2005, reconduit en 2007) Action Universitaire Intégrée Luso-Française, soutien financier de la Conférence des Présidents d'Université (CPU).
• Projet Résolution de contraintes temporelles avec granularités (2004) Projet bilatéral France-Bavière.

Collaborations recherche et industrielles

• IRHT (Institut de Recherche et d'Histoire des Textes, CNRS).
• ICOA (Institut de Chimie Organique et Analytique, CNRS / Université d'Orléans).
• BRGM (Bureau de Recherche Géologique et Minière).

Actions de recherche en cours

• GRAPHEM