RESUME DU MEMOIRE

Le projet ATASH s’intéresse au développement de modèles d’apprentissage pour la conversion automatique de bases de documents semi-structurés hétérogènes de type HTML ou XML. Il propose d’automatiser, à partir d’exemples, un processus qui est aujourd’hui principalement réalisé manuellement à travers l’utilisation de scripts ou programme de conversions spécifiques à chaque application envisagée. Cette problématique est une problématique clefs dans les domaines du document numérique, des bases de données et de façon plus large, de l’intégration de source de données hétérogènes, comme le Web par exemple, au sein d’un système informatique.

Dans le cadre du projet, les partenaires ont exploré plusieurs familles de méthodes d’apprentissage afin d’apprendre à transformer des documents. Ces méthodes se distinguent par les classes de transformation envisagées – correspondant à plusieurs applications réelles comme la conversion HTML vers XML, ou la conversion PDF vers XML par exemple - par leur temps et besoin en apprentissage – certaines méthodes apprennent vite avec peu d’exemples, d’autres sont plus gourmandes – et par leur performances. Ces méthodes ont été évaluées sur des jeux de données issus du projet.

De manière globale, les nouvelles méthodes développées ont permis le traitement de tâches de conversion complexe pour lesquelles aucun modèle n’existait au début du projet. Principalement, le projet a permis de faire émerger trois types de méthodes compétitives :

  • Les méthodes à base de transducteurs d’arbres permettant l’apprentissage de transformation avec peu d’exemples. Ces méthodes ont par exemple une application à la création automatique de flux RSS à partir de pages Web étiquetées par un utilisateur lambda.
  • Les méthodes à base d’apprentissage incrémental permettant de gérer des transformations beaucoup plus complexes moyennant un nombre d’exemples substantiel et un temps d’apprentissage beaucoup plus long.
  • Les méthodes d'apprentissage interactif pour l'annotation de documents

Ces méthodes ont été implémentées dans plusieurs démonstrateurs dédiés à la tâche de conversion de documents semi-structurés.

ENJEUX ET PROBLEMATIQUE, ETAT DE L’ART

CONTEXTE

L'évolution des technologies numériques a bouleversé à plusieurs reprises la gestion de l'information dans les sociétés et les organisations. Aujourd'hui il devient indispensable d'intégrer des nouveaux types de données sémantiquement riches et hétérogènes comme les documents textuels sous différents formats, les services Web, les différents flux issus du Web, le multimédia. L'intégration de ces nouvelles données doit se faire en respectant de nombreuses règles qui garantissent un usage optimal de l'information. Mais la nature hétérogène et répartie de ces sources d'informations complexifie la conception des systèmes de traitement d’information. Un grand effort de standardisation a ouvert la voie vers une intégration des données plus abordable à travers l'apparition des technologies XML. Le typage des documents d'abord à travers des DTD puis des schémas a permis la naissance de normes ou applications XML pour décrire une grande variété de contenus différents. On peut citer XHTML pour la description d'hypertextes, SVG pour le dessin vectoriel, et toutes les applications tournées vers les Web services. Malgré cet effort de normalisation, la grande liberté laissée aux concepteurs et gestionnaires de contenu ne garantit pas un accès uniforme, à ces données toujours fortement hétérogènes, aussi simple qu'un accès à une base de données classique. Même si les technologies XML définissent des outils suffisamment expressifs d'interrogation, la transformation des données issues de sources différentes et/ ou des requêtes est nécessaire pour autoriser une interrogation uniforme. De telles transformations de documents XML font aussi le sujet de normes et de langages comme XSLT, XQuery.

Cependant l'écriture de programmes dans ces langages reste le domaine d'informaticiens spécialistes. De plus, la grande variété et la rapide évolution de ces sources d'information (par exemple sur Internet) a une conséquence importante sur ce fonctionnement. Il n'est plus possible de figer à l'avance ces transformations. La création de tels programmes doit se faire à l'instant même où le besoin s'exprime. La solution se trouve donc certainement vers l'automatisation de la génération des transformations.

Outre la complexité intrinsèque de cette tâche expliquée par l'hétérogénéité des sources de données, plusieurs obstacles rendent difficile cette automatisation et obligent l'usager à intervenir trop fortement dans ce processus. Le premier est la présence d'imprécisions, de fautes, de cas rares qui nécessitent la mise en place de procédures probabilistes, ou simplement pondérées. Le second est lié à l'ambiguïté des données. Pour tenter de palier ce second problème qui dépasse d'ailleurs le problème des transformations, la réponse de la communauté a été de définir un ensemble de technologies permettant d'accompagner les données de meta-données leur donnant une sémantique. Des normes de description ont été définies dans le cadre du W3C comme RDF et OWL (voir état de l’art) pour décrire des ontologies de données. L'usage d'ontologies peut alors simplifier l'automatisation des transformations en se reposant sur une logique de description plus précise que quelques règles syntaxiques. Mais si ces concepts peuvent être utilisés au niveau d'un domaine ou d'un système d'information d'entreprise, l'avenir du Web sémantique pour l'Internet reste incertain.

OBJECTIF DU PROJET

L’information de contenu tend aujourd’hui à être représentée sous une forme semi-structurée c'est-à-dire dans un format alliant conjointement contenu et relations entre les différents éléments de contenu. Ces modes de représentation se sont progressivement imposés dans différents domaines de l’informatique : Dans les BD avec les entrepôts XML, le pair à pair et les Web services, Dans la Recherche d’Information avec les documents HTML, XML, les nouveaux formats des bibliothèques numériques (SGML par exemple) et le multimédia, Dans le Web avec en particulier la vision Web sémantique qui doit permettre de s’appuyer sur des représentations semi-structurées complexes comme les thésaurus ou les ontologies. Dans les bases de données de documents d’entreprises et les ressources des bibliothèques ou des éditeurs.

La maîtrise de l’hétérogénéité des descriptions et des formats liée à la diversité des sources l’information est au cœur de l’accès au contenu informationnel et du développement de services pour le traitement et l’échange de contenu. Un des points clé de cette maîtrise est la connaissance des relations de correspondance entre les différents schémas, modèles de description ou structures logiques, ou bien encore la connaissance des règles de passage d’un format faiblement structuré (HTML) voire structuré par une DTD ne visant que la visualisation (le rendu des documents PDF) à un format sémantiquement riche spécifié par une DTD ou un schéma XML prédéfini. La figure 1 illustre, sur un exemple issu des données de Xerox, un problème de conversion de documents structurés dans le domaine des documents d’entreprise. Un autre exemple concernant l’interrogation par un moteur de recherche de bases de documents hétérogènes est fourni en annexe 1. Cette connaissance obtenue le plus souvent manuellement est actuellement un goulot d'étranglement pour les échanges dans les systèmes d'information hétérogènes et répartis. L’automatisation de ce processus de transformation de documents semi structurés est devenu un enjeu essentiel pour l’exploitation de contenu.

Le projet attaque le problème de l’hétérogénéité sous l’angle de l’apprentissage automatique à partir d’exemples des correspondances (mapping) entre formats et schémas de documents semi-structurés. Un ensemble de méthodes issues de l’apprentissage seront développées pour traiter les différents aspects du problème. Elles serviront à construire des composants génériques capables de répondre aux besoins liés aux transformations. Ces outils seront testés sur une gamme de problèmes représentatifs issus de différents domaines (systèmes d’information répartis, recherche d’information, Web sémantique, systèmes d’information documentaires). Un prototype sera développé pour le traitement complet d’une application cible au cœur de métier de XRCE : la conversion de documents d’entreprises vers un format médiateur. Le projet s’attachera aussi au développement, d’une part de ressources, notamment des corpus de documents, permettant l’évaluation des techniques pour des applications représentatives et d’autre part de protocoles de tests et des mesures d’évaluation afin de comparer les différentes approches entre elles.

L’approche que nous développons est « centrée documents » et exploite, c’est son originalité, à la fois le contenu (texte, image,…) des documents et leur structure logique ainsi que la sémantique des balises, quand elle existe. A ce titre nous considérons en premier lieu les problèmes d’hétérogénéités concernant des applications dans les domaines de la recherche d’information, du Web et des documents d’entreprise. En arrière plan, les méthodes que nous développons peuvent également être utiles pour certains problèmes rencontrés dans les approches « centrées données » comme les BD XML et dans la mise en correspondance d’ontologies. Dans ce cas, elles viennent en complément des approches développées par ces communautés. Par rapport aux approches développées en BD, nous traitons en premier lieu des données sémantiquement plus riches.

APPROCHE SCIENTIFIQUE ET TECHNIQUE

Dans le cadre du projet nous avons adopté la démarche suivante :

  • Nous avons focalisé notre effort sur le cas de documents semi structurés à fort contenu sémantique provenant de sources hétérogènes. Suivant les applications, ces documents peuvent obéir à une DTD, à un schéma ou ne pas respecter un format de ce type. Dans le premier cas, le schéma formel sera le plus souvent inconnu, sa connaissance (incomplète) provenant alors des données. C’est le cas de la majorité des données issues du Web. Le second cas correspond par exemple aux problèmes de conversion de documents d’entreprise en format PDF, WORD ou autre vers un format médiateur. Les documents sont bien structurés mais n’obéissent pas à un schéma prédéfini.
  • Nous avons proposé des approches basées essentiellement sur l’apprentissage à partir de données pour apprendre ces transformations. Les différentes approches sont détaillées plus loin. Ces modèles d’apprentissage s’appuient sur différentes familles de techniques (apprentissage statistique, inférence grammaticale, grammaires stochastiques). Une des originalités des méthodes développées est le traitement conjoint des informations de contenu et structurelles. Ces modèles permettent de couvrir un ensemble de problèmes génériques propres à la problématique de transformation automatique posée ci-dessus.
  • Les approches développées ont été validées sur une large gamme d’applications. Un prototype a été développé et mis en œuvre sur une application cible de Xerox.

METHODES DEVELOPPEES

Les partenaires ont principalement développé des méthodes à l’aide de deux familles de modèles : les approches incrémentales et les approches par champs de Markov conditionnels.

Approches incrémentales

Contrairement aux méthodes d’apprentissage classiques qui cherchent à modéliser à quoi ressemble une bonne solution puis de chercher cette solution parmi l’ensemble des solutions possibles, les méthodes incrémentales proposent de modéliser comment construire la bonne solution directement. Ces méthodes originales sont développées au LIP6 depuis quelques années et trouvent une application dans le cadre de la transformation de documents XML.

Dans le cadre du projet, nous avons proposé de modéliser la problématique de transformation automatique sous la forme d’un processus incrémental : nous considérons que la transformation d’un document d’entrée en un document de sortie s’effectue par l’utilisation séquentielle de transformations élémentaires appliquées au document source.

L’apprentissage dans de tel processus est loin d’être trivial et nous avons proposé des solutions originales basées sur les méthodes d’apprentissage par renforcement pour résoudre ce problème. Les résultats obtenus ont été très satisfaisants.

Approches par champs de markov conditionnels

Afin d'apprendre à effectuer ces transformations, nous avons adapté donc dans un premier temps au cas des arbres XML le modèle des champs aléatoires conditionnels ou Conditional Random Fields (CRF). Les CRFs sont un modèle graphique non dirigé conditionnel pour l'annotation : ils modélisent la probabilité conditionnelle d'une annotation sachant une observation. Ils ont, jusqu'à présent, été essentiellement utilisés dans le cadre de tâches d'annotation de séquences, à la fois dans le domaine de l'extraction d'informations ou en traitement automatiques des langues naturelles. Notre adaptation des CRFs au cas de l'annotation d'arbres XML porte à la fois sur le modèle de dépendances et sur les algorithmes d'inférence exacte (recherche de la meilleure annotation) et d'apprentissage. De plus, nous avons proposé deux méthodes d'amélioration de la complexité de ces algorithmes afin de permettre l'utilisation des champs aléatoires conditionnels dans le cadre d'applications à grande échelle. Ces méthodes s'appuient toutes deux sur l'utilisation des connaissances du domaine. La première consiste en l'intégration de contraintes sur l'annotation. Celles-ci viennent restreindre l'espace des annotations possibles d'un arbre en interdisant des configurations de labels. La seconde technique d'amélioration de la complexité que nous proposons consiste en l'approximation d'un CRF par la composition de plusieurs CRFs de complexité moindre, définis sur des sous-parties de l'alphabet des labels. Ces travaux ont été validés par diverses expériences sur des données artificielles et réelles, montrant ainsi non seulement la qualité des transformations effectuées à l'aide de nos méthodes, mais aussi leur intérêt dans des tâches réelles.

Apprentissage intéractif pour l'annotation de documents

Une autre partie de notre travail a été dédiée au clustering visuel, qui applique le principe de coordonnées sphérique, en projetant des données multi dimensionnelles dans l’espace visuel 3D. Par rapport à l’étape précédente, le système a été enrichi en projetant des données à K dimensions dans l’espace visuel, ou 3D. Le système permet de combiner la manipulation manuelle visuelle de données et la technique d'optimisation pour séparer les données dans l’espace visuel. Un prototype de clustering visuel est implémenté ou plusieurs méthodes ont pu d’être testées.

De plus, nous avons proposé l’utilisation d'une interface d'annotation interactive dans les modes supervisé, semi-supervisé et non-supervisé, avec annotation totale ou partiale. L’outil interactif permet de visualiser en 3D les clusters, de les manipuler, d’optimiser la vue des clusters, d’annoter les éléments, de montrer l’incertitude des éléments non encore annotés, etc. Le prototype de l’interface Web est réalisé avec les technologies Adobe Frash et Flex Open Source.