LIFAT Defense - Galisot Gaetan

Résumé

L'apprentissage automatique a récemment révolutionné l'exploitation et l’analyse des données numériques et symboliques. Parallèlement, en raison du fort pouvoir d'expressivité de la structure de données « graphe », un volume important de données structurelles est continuellement produit. Faute d'algorithmes suffisamment rapides, la dimension structurelle des données, vecteur de connaissances haut niveau, est pour l'heure insuffisamment exploitée dans les applications réelles et grands publics (fouille de données, analyse des réseaux sociaux, bio-informatiques, vision par ordinateur, ...).

Du fait de leur forte complexité (temps de calcul trop longs et espaces mémoire nécessaires importants), les chercheurs travaillant dans le domaine de la comparaison ou de la mise en correspondance de graphes ont porté une attention particulière sur les méthodes dites « approchées » plus rapides mais dont on ne peut garantir la qualité de la solution fournie (surtout lorsque les graphes deviennent grands).

Au contraire, cette thèse se focalise sur les méthodes dites « exactes » capables de fournir des solutions optimales. Les travaux menés proposent plusieurs solutions originales d'optimisation et d'amélioration de la précision des algorithmes permettant de comparer de grands graphes complexes.

Dans un premier temps, un algorithme de mise en correspondance de graphes utilisant une recherche arborescente et travaillant en profondeur d’abord (Depth-First GED) pour consommer moins de mémoire et de temps de calcul est proposé. Ensuite, pour permettre un compromis entre vitesse et optimalité, une version améliorée de Depth-First GED (appelée Anytime) est construite. Cette méthode très originale est capable de délivrer une première solution très rapidement pour ensuite, avec plus de temps, améliorer progressivement cette solution initiale dans le but de proposer de meilleures solutions jusqu’à converger vers la solution optimale si le temps alloué le permet.

De techniques de parallélisation et de distribution des calculs sur plusieurs machines sont également développées pour réduire encore le temps d’exécution des algorithmes à l’aide de stratégie d’équilibrage des charges.

Afin d’analyser les performances des méthodes proposées, celles-ci sont testées dans divers contextes de classification (comparaison de formules chimiques, mise en correspondance d’images, reconnaissance de caractères, …) mais aussi à un niveau plus détaillé en mesurant la qualité de la mise en correspondance obtenues. Pour cela, une base de graphes (GDR4GED) avec une vérité terrain dédiée à l’évaluation des méthodes de mise en correspondance de graphes a été construite. Les évaluations sont effectuées sous diverses contraintes de temps de calcul et d’espace mémoire disponibles. De par les résultats obtenus, ces expérimentations remettent en cause les réticences à l’utilisation des méthodes exactes d’appariement de grands graphes dans la pratique.

Ces méthodes d’évaluations, ainsi que les méthodes proposées durant cette thèse, constituent le cœur d’une compétition internationale qui aura lieu au Mexique en décembre 2016 dans le cadre de la plus renommée des conférences du domaine de la reconnaissance des formes (ICPR). Voir ce lien http://www.icpr2016.org/site/session/graph-distance-contest/ pour plus d’informations.