• Langue : Anglais
• Discipline : Informatique
• Identifiant : Inconnu
• Type de mémoire : Habilitation à diriger des recherches
• Date de soutenance : 14/12/2015

Résumé en langue originale

Ce mémoire est une courte présentation d’une direction de recherche, à laquelle j’ai activement participé, sur l’apprentissage pour les bases de données à partir d’exemples. Cette recherche s’est concentrée sur les modèles et les langages, aussi bien traditionnels qu’émergents, pour l’interrogation, la transformation et la description du schéma d’une base de données. Concernant les schémas, nos contributions consistent en plusieurs langages de schémas pour les nouveau modèles de bases de données que sont XML non-ordonné et RDF. Nous avons ainsi étudié l’apprentissage à partir d’exemples des schémas pour XML non-ordonné, des schémas pour RDF, des requêtes twig pour XML, les requêtes de jointure pour bases de données relationnelles et les transformations XML définies par un nouveau modèle de transducteurs arbre-à-mot. Pour explorer si les langages proposés peuvent être appris, nous avons été obligés d’examiner de près un certain nombre de leurs propriétés fondamentales, souvent souvent intéressantes par elles-mêmes, y compris les formes normales, la minimisation, l’inclusion et l’équivalence, la cohérence d’un ensemble d’exemples et la caractérisation finie. Une bonne compréhension de ces propriétés nous a permis de concevoir des algorithmes d’apprentissage qui explorent un espace de recherche potentiellement très vaste grâce à un ensemble d’opérations de généralisation adapté à la recherche d’une solution appropriée. L’apprentissage (ou l’inférence) est un problème à deux paramètres : la classe précise de langage que nous souhaitons inférer et le type d’informations que l’utilisateur peut fournir. Nous nous sommes placés dans le cas où l’utilisateur fournit des exemples positifs, c’est-à-dire des éléments qui appartiennent au langage cible, ainsi que des exemples négatifs, c’est-à-dire qui n’en font pas partie. En général l’utilisation à la fois d’exemples positifs et négatifs permet d’apprendre des classes de langages plus riches que l’utilisation uniquement d’exemples positifs. Toutefois, l’utilisation des exemples négatifs est souvent difficile parce que les exemples positifs et négatifs peuvent rendre la forme de l’espace de recherche très complexe, et par conséquent, son exploration infaisable.

Résumé traduit

This dissertation is a summary of a line of research, that I was actively involved in, on learning in databases from examples. This research focused on traditional as well as novel database models and languages for querying, transforming, and describing the schema of a database. In case of schemas our contributions involve proposing an original languages for the emerging data models of Unordered XML and RDF. We have studied learning from examples of schemas for Unordered XML, schemas for RDF, twig queries for XML, join queries for relational databases, and XML transformations defined with a novel model of tree-to-word transducers. Investigating learnability of the proposed languages required us to examine closely a number of their fundamental properties, often of independent interest, including normal forms, minimization, containment and equivalence, consistency of a set of examples, and finite characterizability. Good understanding of these properties allowed us to devise learning algorithms that explore a possibly large search space with the help of a diligently designed set of generalization operations in search of an appropriate solution. Learning (or inference) is a problem that has two parameters: the precise class of languages we wish to infer and the type of input that the user can provide. We focused on the setting where the user input consists of positive examples i.e., elements that belong to the goal language, and negative examples i.e., elements that do not belong to the goal language. In general using both negative and positive examples allows to learn richer classes of goal languages than using positive examples alone. However, using negative examples is often difficult because together with positive examples they may cause the search space to take a very complex shape and its exploration may turn out to be computationally challenging.