Responsable HDR : Sławek Staworko
Encadrants : Slawek Staworko
Les problèmes de qualité de données affecte de manière négative une partie importante de tout processus de traitement de données dans les domaines de business. Les statistiques montrent que les données de basse qualité peuvent représenter un coût de 20-30% de chiffres d'affaires pour une entreprise.
L'objectif de ce TER est une comparaison des approches existantes pour le nettoyage de données sur un corpus d'une grande bases de données des livres. En particulier, le travail se concentrera sur l'identification des doublons (deux entrées dans la bases de données qui représentent le même livre).
Un candidat potentiel pour ce TER doit être capable d'un travail autonome, doit maîtriser la programmation et les bases de données, doit être capable de lire la documentation technique en anglais.
Pour tout candidat intéressé je propose un petit test de compétences. Le but est d'importer le contenu de Open Library Data Dumps à une base de données relationnelle (comme SQLite3). Il faut comprendre bien le format JSON et comment programmer avec. L'astuce importante est de développer vos scriptes d'importation de données sur une petit échantillon de fichiers dumps (les premières 100 lignes). À vos claviers.
Équipe : Mostrare
Responsable HDR : Remi Gilleron
Encadrants : Slawek Staworko et Fabien Torre
Un des événements les plus importants de l'informatique et des bases de données durant la dernière décade est l'adoption de XML comme un standard d'échange des données sur le Web et la profusion de données utilisant ce format qui a suivi. Plusieurs langages permettant le traitement des données XML ont été proposées par la communauté informatique, il s'agit de XPath, XSLT et XQuery. De plus, des implémentations efficaces d'outils basés sur ces langages ont rapidement été proposés. Cependant, ces langages restent difficiles à utiliser par M. Dupont.
Nous proposons d'assister un tel utilisateur lambda à l'aide d'algorithmes d'apprentissage automatique de requêtes XPath. Dans ce cadre l'utilisateur indique sur un fragment du document XML des noeuds qu'il veut sélectionner. L'algorithme calcule une requête en généralisant la sélection de l'utilisateur. Ensuite, l'utilisateur observe sur un fragment plus grand du document XML si la requête se comporte comme voulu. L'utilisateur peut alors soit ajouter de nouveaux éléments à la sélection pour indiquer que la généralisation n'était pas assez robuste, soit marquer certains noeuds comme interdits si l'algorithme a trop généralisé. Cette interaction se poursuit jusqu'à ce que l'algorithme produise une requête qui satisfait l'utilisateur.
Notre recherche se concentre sur un fragment de XPath très souvent utilisé en pratique et connu sous le nom de « requêtes Twig » (d'après la représentation graphique de ces requêtes). Nos résultats préliminaires indiquent que cette classe n'est pas apprenable. Cependant, nous avons étendu cette classe avec l'opérateur d'union, obtenant ainsi une nouvelle classe UTwig. Chose étonnante, cette classe étant plus puissante elle permet d'éviter les problèmes qui rendent Twig impossible à apprendre. Nous avons également identifié un ensemble d'opérations de généralisation simples et intuitives que nous pensons suffisant pour permettre d'inférer les requêtes d'utilisateur. Nous avons également construit une première version d'algorithme d'inférence des requêtes basée sur ces opérations de généralisation.
Le but du stage est une implémentation de l'algorithme d'inférence de requêtes UTwig à partir d'exemples donnés par l'utilisateur. A priori, l'algorithme devrait suivre les grandes lignes données ci-dessus. Il s'agira également de construire une suite de tests qui permettant d'évaluer le fonctionnement de l'algorithme et de l'approche en elle-même. Comme beaucoup de questions théoriques sur l'apprenabilité des requêtes XPath sont toujours ouvertes, il est envisageable de continuer ce projet en stage voire en thèse.
Équipe : Mostrare
Responsable HDR : Remi Gilleron
Encadrants : Slawek Staworko et Fabien Torre
Récemment nous avons développé une suite d'algorithmes d'apprentissage des requêtes XPath à partir des exemples donnés par un utilisateur. Un tel algorithme prend un ensemble des documents XML avec certains éléments annotés comme requis (exemples positives) et certains éléments annotés comme interdits (exemples négatives). Le résultat de l'algorithme est une requête XPath qui sélectionne tous les noeuds requis et aucun noeud interdit (la requête peut aussi englober à volonté des noeuds non-annotés). Nous avons construit une famille d'algorithmes qui travaillent uniquement avec des exemples positives et une famille d'algorithmes qui acceptent des exemples positives et négatives. En plus, nous avons évalué ses algorithmes sur plusieurs corpus XML.
Nos résultats montrent que nos algorithmes apprennent des requêtes contentant des conditions essentielles pour sélectionner des noeuds requis. Cependant, les documents typiquement suivent une certaine schéma qui est souvent donnée en forme d'un DTD ou XML Schema. Comme certains de nos algorithmes d'apprentissage sont basés sur l'identification de tous les motives commun aux exemples positives, les requêtes contiendront beaucoup de conditions qui suivent du schéma des documents. Ces conditions, étant toujours satisfaites par les documents du domaine, servent essentiellement à rien, mais leur présence augmente la taille de la requête, peut la rendre illisible et augmente le temps de l'évaluation de la requête.
Le but de ce projet est de trouver des mécanismes permettant de profiter du schéma des documents afin d'éviter l'ajout des conditions redondantes pendant l'apprentissage des requêtes. Le premier étape comprendra une étude de la complexité du problème intrinsèque à l'identification des redondances: le problème d'inclusion et d'équivalence des requêtes en présence du schéma. Il est bien connu que ce genre de problèmes sont typiquement (coNP-)dures. Le but ici sera d'identifier les sous-classes des requêtes et les classes de schéma pour lesquelles ce problème devient décidable en temps polynomial. Ensuite, il faudra utiliser ses résultat pour modifier des algorithmes d'apprentissage pour améliorer la qualité des requêtes construites.
Équipe : Mostrare
Responsable HDR : Sophie Tison
Encadrants : Slawek Staworko et Sophie Tison
La distance d'édition entre deux objets est définie comme le nombre minimal d'opérations élémentaires d'édition pour transformer l'objet de départ en l'objet cible. Les variants les plus connus et étudiés sont la distance d'édition des mots et la distance d'édition des arbres. Les deux variants ont de nombreux applications dans presque tous les domaines de l'informatique comme bioinformatique, compression et cryptographie.
La distance d'édition est généralisée en remplaçant l'objet cible par un ensemble d'objets cibles possibles et le but est d'attendre un objet cible avec le nombre minimal d'opérations élémentaires. L'ensemble d'objets cibles est typiquement représenté avec un formalisme régulière comme un automate des mot ou un automate des arbres.
Le calcul de la distance d'édition entre un mot et un langage régulier est effectué avec un algorithme qui généralise l'algorithme standard du calcul de la distance d'édition entre deux mot. Cependant, le calcul de la distance d'édition entre un arbre et un langage régulier d'arbres n'a pas toujours été abordé. Le but de ce projet sera généraliser les algorithmes du calcul de la distance d'édition entre deux arbres. Il est évident que ce but est atteignable mais la complexité de l'algorithme final peut être peu attrayant. Par conséquent, le projet visera aussi à développer des heuristiques permettant un calcul plus rapide.
Équipe : Mostrare
Responsable HDR : Remi Gilleron
Encadrants : Slawek Staworko et Fabien Torre
While the XML standard stores the relative order between the children of a node, very rarely is this order used in practice. Consequently, an unordered model for XML has recently become an enlivened topic of research both from theoretical and practical angle. For the ordered XML, two most popular schema formalism, DTD and XML Schema, are based on regular expressions which define the allowed sequences of labels of the consecutive children of a node. These formalisms rely considerably on documents being ordered and therefore new formalisms need to be explored for unordered XML.
The goal of this internship is a bibliographical study of the existing schema formalisms for unranked including the related decision problems (inclusion of two schemas, inclusion of two queries in the presence of a schema, satisfiability of a query in the presence of a schema, exactness of ordered schema approximation, etc.). Additionally, we will study inference of selected unordered schema formalisms and continue to investigate the use of the (inferred) schema to benefit the process of learning. Finally, the end result could be a new formalism for unordered schema that fits the best the needs of schema learning and query learning in the presence of schema.