Vous êtes ici : Accueil » Kiosque » Annonce

Identification

Identifiant: 
Mot de passe : 

Mot de passe oublié ?
Détails d'identification oubliés ?

Annonce

11 avril 2017

Thèse au LITIS : Apprentissage de métriques sur graphes


Catégorie : Doctorant


Proposition de thèse en apprentissage de métrique sur graphe au LITIS EA 4108 - Université de Rouen Normandie

Les graphes disposent d'un fort pouvoir de description. Nombre de méthodes de reconnaissance de forme reposent sur le calcul d'une distance. Le calcul de la distance d'édition entre graphes a une complexité temporelle exponentielle. Cette distance repose sur des fonctions de coût associées aux opérations d'édition élémentaire (substitution, insertion ou suppression de nœuds ou d'arcs). Jusqu'à présent, les fonctions de coûts dépendant des étiquettes des nœuds/arcs étaient données ou déterminées par expertise humaine.

L'objectif de cette thèse est transposer l'aptitude qu'ont les réseaux neuroanatomiques profonds à déterminer automatiquement les caractéristiques pertinentes et leur pondération, au domaine des graphes dotés d'un fort pouvoir de représentation. Il s'agira de proposer une approche permettant de déterminer par apprentissage les fonctions de coût des opérations élémentaires utilisées dans le calcul d'édition de graphe, ou ses approximations. Cet apprentissage pourra se faire au regard de différents objectifs :

  • soit en respectant au mieux les valeurs de distance données dans une base d'apprentissage
  • soit en respectant au mieux des chaînes d'opérations d'édition données ou des mises en correspondance (nœud à nœud, sous-graphe à sous-graphes)

Des collaborations sont envisagées avec d'autres laboratoires d'informatique (LI Tours et GREYC Caen). Des applications en chémoinformatique sont envisagées avec des interactions avec les laboratoires LCMT (Caen), CERMN (Caen), COBRA (Rouen)

Sujet détaillé : http://www.litislab.fr/actu/proposition-de-these-apprentissage-de-metrique-graphes-metric-learning-on-graphs/

Équipe d’encadrement :

  • Sébastien Adam (PR à l’Université de Rouen Normandie)
  • Pierre Héroux (MCF à l’Université de Rouen Normandie)
  • Benoît Gaüzère (MCF à l’INSA Rouen Normandie)

Candidature : Le/la candidat(e) devra avoir une bonne connaissance théorique en apprentissage statistique et en théorie des graphes. De bonnes aptitudes en programmation sont souhaitées. La sélection des candidats se fera sur dossier (CV, notes à la partie théorique du master 2 + lettre de motivation + lettres de recommandation) puis audition, éventuellement en distanciel. Les dossiers sont à envoyer le plus rapidement possible (et au plus tard le 28 avril) à Sebastien.Adam@univ-rouen.fr, Pierre.Heroux@univ-rouen.fr et Benoit.Gauzere@insa-rouen.fr. Les candidatures seront traitées au fur et à mesure de leur réception et une décision pourra être prise avant la date limite si un candidat donne satisfaction.

 

Description du sujet

Les graphes sont des structures de données informatiques très souples qui permettent une description très riche et très fine d’une gamme très large d’objets, allant des molécules aux images, en passant par de l’écriture manuscrite ou des réseaux sociaux.

Paradoxalement, malgré l’important pouvoir de représentation des graphes, la communauté de l’apprentissage automatique (Machine Learning), dont les progrès ont été impressionnants ces dernières années, en particulier avec l’apprentissage profond, s’est encore assez peu attaquée au développement d’algorithmes performants pour l’analyse de données représentées par des graphes. Au niveau international, on peut d’ailleurs mentionner que la communauté Française est probablement l’une des plus dynamiques dans ce domaine. Outre leur dimensionnalité (nombre de nœuds et d’arcs) variable, une autre raison qui explique le peu de travaux relatifs à l’apprentissage à base de graphes est liée au fait que les algorithmes existant en apprentissage automatique s’appuient sur le calcul d’une distance (ou plus généralement d’un produit scalaire) entre les exemples d’apprentissage. Or, si ce calcul est immédiat dans des espaces vectoriels, il constitue à lui seul un problème scientifique complexe lorsque l’on manipule des données de type graphe.

Les méthodes existantes pour estimer la (di)similarité entre graphes reposent souvent sur le calcul d’une distance d’édition, c’est-à-dire une fonction de coût calculée comme étant la somme de coûts d’édition élémentaire transformant un graphe en un autre. Considérant la complexité exponentielle des algorithmes de calcul exact de telles distances, les travaux récents ont cherché à calculer plus rapidement des fonctions de coût d’appariement de graphe (matching complet, isomorphisme de sous-graphe) soit de façon exacte [4, 5, 7, 6], soit grâce à des approximations [3, 8, 11, 12, 13, 1, 9], permettant de repousser la limite en taille des graphes pouvant être traités. En revanche, dans la plupart des travaux, les fonctions de coût associées aux opérations élémentaires sont considérées données ou sont déterminées en optimisant un très faible nombre de paramètres (rapport du coût lié aux nœuds par rapport à celui lié aux arcs) au regard d’un objectif (optimisation du taux d’erreur sur une tâche de classification) [10]. Peu de travaux [2] ont porté sur l’étude de la fonction de coût des opérations d’édition élémentaire et son impact sur la qualité des résultats et sur le temps de calcul. Il existe donc un réel enjeu à développer des travaux fondamentaux et applicatifs à l’intersection de la théorie des graphes et de l’apprentissage automatique qui permettent d’apprendre une métrique entre graphes, afin de faire passer un cap aux algorithmes actuels. Les approches permettraient ainsi d’apprendre à comparer des graphes, comme les réseaux profonds apprennent à extraire des caractéristiques pertinentes.

Dans ce contexte, le sujet de thèse proposé visera dans un premier temps à étudier l’impact des fonctions de coût correspondant aux opérations d’édition élémentaire (substitution, insertion, suppression des nœuds et des arcs) sur la qualité des résultats et sur les temps de traitement. Il s’agira notamment de proposer des procédures permettant, étant donné un modèle paramétrique de la fonction de coût, de déterminer les valeurs optimales des paramètres au regard de différents objectifs. Ces objectifs peuvent être de plusieurs natures en fonction de l’information disponible dans les bases d’apprentissage. Il peut s’agir d’optimiser des performances en classification si seule la classe des objets représentés par les graphes est disponible, ou bien de respecter au mieux les appariements nœud à nœud et arc à arc, voire sous-graphe à sous-graphe, si ceux-ci sont connus.

L’étude portera également sur la nature du modèle paramétrique de la fonction de coût pour déterminer si la seule intégration des différentes dimensions des étiquettes est pertinente, par exemple dans un modèle linéaire dont il faudra déterminer les pondérations, ou si la prise en compte des informations de contexte structurel (centralité de nœuds, degré, factorisation de graphe, sous-graphes fréquents…) est de nature à accélérer la mise en correspondance. Enfin, considérant la complexité des algorithmes de mise en correspondance de graphes, on pourra également étudier l’impact de l’usage d’approximations pour la détermination des fonctions de coût optimales.

Applications

Les algorithmes développés seront appliqués prioritairement à des problématiques de chémo-informatique, en collaboration avec des laboratoires de chimie du territoire Normand (COBRA, CERMN, LCMT).

Contexte

Ce travail donnera lieu à des collaborations avec le laboratoire GREYC de Caen et le laboratoire LI de Tours, avec lesquels le LITIS mène des travaux communs depuis longtemps sur les problématiques d’analyse de graphes. Il est également envisagé de collaborer avec le Computer Vision Center de l’Université Autonome de Barcelone.

Financement

Cette thèse fait l’objet d’une demande de financement au sein de l’École doc- torale MIIS de Normandie Université. L’attribution définitive du financement demandé sera connue fin juin 2017.

Équipe d’encadrement

Les travaux seront encadrés par :

Candidature

Le/la candidat(e) devra avoir une bonne connaissance théorique en apprentissage statistique et en théorie des graphes. De bonnes aptitudes en programmation sont souhaitées. La sélection des candidats se fera sur dossier (CV, notes à la partie théorique du master 2 + lettre de motivation + lettres de recommandation) puis audition, éventuellement en distanciel. Les dossiers sont à envoyer le plus rapidement possible (et au plus tard le 28 avril) à Sebastien.Adam@univ-rouen.fr, Pierre.Heroux@univ-rouen.fr et Benoit.Gauzere@insa-rouen.fr. Les candidatures seront traitées au fur et à mesure de leur réception et une décision pourra être prise avant la date limite si un candidat donne satisfaction.

Références

[1] S. Bougleux, L. Brun, V. Carletti, P. Foggia, B. Gaüzère, and M. Vento. Graph edit distance as a quadratic assignment problem. Pattern Recognition Letters, 87 :38–46, 2017.

[2] Xavier Cortés and Francesc Serratosa. Learning graph-matching edit-costs based on the optimality of the oracle’s node correspondences. Pattern Recogn. Lett., 56 :22–29, 2015.

[3] Stefan Fankhauser, Kaspar Riesen, and Horst Bunke. Speeding up graph edit distance computation through fast bipartite matching. In Proc. of the 8th IAPR Int. Workshop on Graph-Based Repres. in Pattern Recogn., pages 102–111, 2011.

[4] Derek Justice and Alfred Hero. A binary linear programming formulation of the graph edit distance. IEEE Trans. Pattern Anal. Mach. Intell., 28(8) :1200–1214, 2006.

[5] Pierre Le Bodic, Pierre Héroux, Sébastien Adam, and Yves Lecourtier. An integer linear program for substitution-tolerant subgraph isomorphism and its use for symbol spotting in technical drawings. Pattern Recogn., 45(12) :4214 – 4224, 2012.

[6] Julien Lerouge, Zeina Abu-Aisheh, Romain Raveaux, Pierre Héroux, and Sébastien Adam. Graph edit distance : a new binary linear programming formulation. CoRR, abs/1505.05740, 2015.

[7] Julien Lerouge, Maroua Hammami, Pierre Héroux, and Sébastien Adam. Minimum cost subgraph matching using a binary linear program. Pattern Recognition Letters, 71 :45–51, 2016.

[8] Michel Neuhaus, Kaspar Riesen, and Horst Bunke. Fast suboptimal algorithms for the computation of graph edit distance. In SSPR/SPR, pages 163–172, 2006.3

[9] Kaspar Riesen. Structural Pattern Recognition with Graph Edit Distance – Approximation Algorithms and Applications. Advances in Comp. Vis. and Pattern Recogn. Springer, 2015.

[10] Kaspar Riesen and Horst Bunke. Iam graph database repository for graph based pattern recognition and machine learning. In Structural, Syntactic, and Statistical Pattern Recognition, volume 5342 of Lecture Notes in Computer Science, pages 287–297. 2008.

[11] Kaspar Riesen and Horst Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image Vision Comput., 27(7) :950–959, 2009.

[12] Francesc Serratosa. Fast computation of bipartite graph matching. Pattern Recogn. Lett., 45 :244–250, 2014.

[13] Francesc Serratosa. Computation of graph edit distance : Reasoning about optimality and speed-up. Image Vision Comp., 40 :38–48, 2015.

 

Dans cette rubrique

(c) GdR 720 ISIS - CNRS - 2011-2015.