Annonce en lien avec l’Action/le Réseau : aucun

Laboratoire/Entreprise : LITIS (Rouen)
Durée : 36 mois
Contact : paul.honeine@univ-rouen.fr et benoit.gauzere@insa-rouen.fr
Date limite de publication : 2016-05-31

Contexte :
Mots-clés : Théorie des graphes, machine learning, méthodes d’apprentissage à noyaux, pré-image, noyaux sur graphes, reconnaissance de formes.

Sujet :
Les méthodes d’apprentissage automatique sont généralement définies dans des espaces euclidiens. Cependant, certains domaines, telles que la chémoinformatique ou la reconnaissance de formes, privilégient une représentation des données sous forme de graphes. L’utilisation des méthodes classiques d’apprentissage sur des graphes reposent sur des plongements de ces derniers dans des espaces euclidiens. Afin d’améliorer l’interprétabilité des résultats obtenus, il est intéressant de chercher à inverser ses fonctions de plongement et donc de reconstruire un graphe à partir de sa représentation vectorielle. Ce problème consiste alors à calculer la pré-image des vecteurs selon le plongement défini.

Depuis une dizaine d’années, le lien entre méthodes d’apprentissage automatique et graphes a bénéficié de l’astuce du noyau. La définition et l’utilisation de noyaux sur graphes a permis de se libérer des contraintes liées à une représentation explicite du plongement des graphes dans un espace euclidien. Cependant, le manque de représentation vectorielle explicite d’un graphe complique le calcul de la pré-image, c’est à dire la reconstruction d’un graphe à partir d’un point dans l’espace de Hilbert associé au noyau. De plus, la dimension de l’espace associé au noyau pouvant être infinie, la plupart des points de cet espace n’ont pas de pré-image exacte dans l’espace des graphes.

Le présent sujet de thèse concerne donc la résolution du problème du calcul de pré-image de noyaux sur graphes. Un premier aspect de ce projet consiste à étudier le calcul de pré-image à partir de noyaux sur graphes, dans la continuité des travaux effectués sur des noyaux conventionnels à représentation vectorielle [Honeine and Richard, 2011]. La principale difficulté de cette première problématique est liée au fait que les noyaux ne permettent généralement pas d’obtenir une représentation vectorielle explicite des données que l’on manipule. Toutefois, lorsque le plongement est basé sur une énumération d’un ensemble de sous-structures comme les noyaux basés sur des chemins [Ralaivola et al., 2005] ou sur des sous-arbres [Gaüzère et al., 2012], il peut être possible de reconstruire un graphe à partir d’une représentation vectorielle encodant le nombre d’occurrences de chaque sous-structure utilisée. Afin de reconstruire un graphe, il faut donc calculer une pré-image à partir d’un point dans l’espace du noyau [Honeine and Richard, 2011], cette pré-image encodant le nombre d’occurrences de chaque sous-structure. À partir de cette représentation, il faut ensuite s’intéresser à la reconstruction d’un graphe à partir d’un vecteur décrivant le nombre d’occurrences d’un ensemble de structures. La résolution de ces verrous scientifiques devrait améliorer la compréhension des résultats fournis par les algorithmes d’apprentissage automatique en permettant de sélectionner ou de générer des graphes représentatifs [Raveaux et al., 2011] à partir d’un grand ensemble de graphes initiaux.

Une des applications directes de ces travaux concerne la bio-informatique et la chémoinformatique. Les molécules sont naturellement représentées par des graphes, et cette représentation est souvent privilégiée dans le cadre de problèmes de prédiction de propriétés moléculaires. L’application des méthodes issues de cette thèse devrait permettre d’améliorer le retour donné à l’expert chimiste en reconstruisant des graphes moléculaires à partir de certains points clés utilisés par la méthode d’apprentissage. Cette représentation serait alors plus facilement interprétable par l’expert chimiste et contribuera à la compréhension du phénomène chimique sous-jacent.

Bibliographie :
[Gaüzère et al., 2012] Gaüzère, B., Brun, L., and Villemin, D. (2012). Two new graphs kernels in chemoinformatics. Pattern Recognition Letters, 33(15) :2038–2047.
[Honeine and Richard, 2011] Honeine, P. and Richard, C. (2011). Preimage problem in kernel- based machine learning. Signal Processing Magazine, IEEE, 28(2) :77–88.
[Ralaivola et al., 2005] Ralaivola, L., Swamidass, S. J., Saigo, H., and Baldi, P. (2005). Graph kernels for chemical informatics. Neural networks : the official journal of the International Neural Network Society, 18(8) :1093–110.
[Raveaux et al., 2011] Raveaux, R., Adam, S., Héroux, P., and Trupin, E. (2011). Learning graph prototypes for shape recognition. Computer Vision and Image Understanding, 115(7) :905 – 918. Special issue on Graph-Based Representations in Computer Vision.

Profil du candidat :
Master 2 en informatique, mathématiques appliquées, ou école d’ingénieur

Formation et compétences requises :
Formation : Master 2 en informatique, mathématiques appliquées, ou école d’ingénieur
Compétences recommandées : Théorie des graphes, Machine learning (méthodes à noyaux), Reconnaissance de formes.

Adresse d’emploi :
Equipe d’accueil : Equipe Apprentissage au laboratoire LITIS (Laboratoire d’Informatique, du Traitement de l’Information et des Systèmes), à Rouen.
http://www.litislab.fr/

Document attaché : litis_rouen.pdf