Apprentissage supervisé d'ultramétrique – ULTRA-LEARN

Dans ce projet, nous proposons d’étudier le problème de l’optimisation de regroupements hiérarchiques sous l’angle de l’optimisation d’ultramétriques qui sont une représentation duale et continue de ces premiers. En topologie, une distance ultramétrique est obtenue en remplaçant l’inégalité triangulaire par l’inégalité ultramétrique, qui impose que tout triplet de points forme un triangle isocèle où les deux côtés égaux sont au moins aussi grands que le troisième côté. Cette inégalité ultramétrique correspond à une contrainte non-convexe difficile à gérer. On peut néanmoins reformuler le problème d’optimisation d’ultramétrique afin de rendre cette contrainte implicite. Il devient alors possible d’optimiser des ultramétriques avec des algorithmes de descente de gradient. Ce projet vise à développer cette possibilité afin d’obtenir des méthodes d’apprentissage supervisées de regroupements hiérarchiques fonctionnant sur de grandes masses de données. En d’autres termes, nous formulerons le problème d’apprentissage supervisé de regroupements hiérarchiques sur l’espace continu des ultramétriques, d’où le nom du projet : ULTRA-LEARN.

Cette avancée reposera sur deux ingrédients principaux. Le premier est le développement de réseaux ultramétriques, c’est-à-dire de modèles entrainables et produisant en sortie une ultramétrique. Un réseau ultramétrique sera lui-même constitué de deux éléments, un réseau neuronal multicouches pour l’extraction de caractéristiques et une couche ultramétrique qui sera capable de produire une ultramétrique à partir des caractéristiques fournies par le réseau neuronal. Cette couche ultramétrique sera différentiable afin de permettre un apprentissage de bout-en-bout du réseau. Le deuxième ingrédient de la méthode sera la définition de fonctions de coût capables de mesurer efficacement et de manière différentiable la dissimilarité entre deux ultramétriques.

Nous avons développé une première méthode permettant d’optimiser une fonction de coût hiérarchique différentiable avec un algorithme de descente de gradient. Cette méthode repose sur l’opérateur d’ultramétrique sous-dominante qui permet d’associer une ultramétrique à toute fonction de dissimilarité et ce, de manière sous-différentiable. Nous avons montré comment il est alors possible de calculer efficacement cet opérateur et son gradient dans le cadre de l’analyse de graphs parcimonieux. Ces développements nous ont permis de fournir des solutions efficaces pour l’optimisation de fonction de coûts hiérarchiques dont l’optimisation est NP-difficile. Nous avons également montré comment cette approche permet de facilement construire de nouvelles fonctions de coût hiérarchiques par combinaison de termes d’attaches aux données et de termes de régularisation pouvant inclure des informations de supervision.

Les réseaux ultramétriques développés seront mis en pratique sur trois applications. Nous proposerons un réseau ultramétrique pour estimer des segmentations hiérarchiques d’images, c’est-à-dire la décomposition d’une image en objets et le raffinement itératif de ces objets en sous objets. La deuxième application visera le développement d’un classifieur capable de tirer parti d’une ontologie de classes connue a priori, par exemple nous savons qu’un chat et un chien sont tous deux des mammifères et qu’ils sont sémantiquement plus proches que d’un oiseau. Finalement la troisième application considérée est le regroupement hiérarchique semi-supervisé de données ; dans ce cas on cherchera à construire un regroupement hiérarchique optimal à partir d’informations partielles données a priori par un expert.

-G. Chierchia and B. Perret. Ultrametric fitting by gradient descent. Journal of Statistical Mechanics: Theory and Experiment, 2020(12), 124004.
-G. Chierchia and B. Perret. Ultrametric fitting by gradient descent. Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.

Un regroupement hiérarchique correspond à diviser récursivement un ensemble de données en groupes de plus en plus petits. L’hypothèse fondamentale de cette approche est que la structure visible dans les données dépend de l’échelle d’observation choisie. Cette hypothèse a été confirmée, en théorie et en pratique, sur de nombreuses données complexes telles que les réseaux sociaux, les réseaux électriques, les réseaux d'acteurs, les réseaux informatiques, les réseaux du cerveau cortical, les réseaux linguistiques, etc. Construire des représentations hiérarchiques de bonne qualité constitue donc une étape importante de l’analyse et la compréhension de ces données. Les méthodes de regroupement hiérarchique utilisées aujourd’hui sont essentiellement non supervisées et reposent sur des algorithmes heuristiques : le regroupement hiérarchique obtenu ne correspond donc pas à l’optimisation d’un critère explicite. Ces limitations sont imputables aux difficultés de résolution de problème d’optimisation sur ces structures qui sont généralement NP-complets.

Dans ce projet, nous proposons d’étudier le problème de l’optimisation de regroupement hiérarchique sous l’angle de l’optimisation d’ultramétriques qui sont une représentation duale et continue de ces premiers. En topologie, une distance ultramétrique est obtenue en remplaçant l’inégalité triangulaire par l’inégalité ultramétrique, qui impose que tout triplet de points forme un triangle isocèle où les deux côtés égaux sont au moins aussi grands que le troisième côté. Cette inégalité ultramétrique impose une nouvelle contrainte non-convexe difficile à gérer. On peut néanmoins reformuler le problème d’optimisation d’ultramétrique afin de rendre cette contrainte implicite. Il devient alors possible d’optimiser des ultramétriques avec des algorithmes de descente de gradient. Ce projet vise à développer cette possibilité afin d’obtenir des méthodes d’apprentissage supervisées de regroupement hiérarchiques fonctionnant sur de grandes masses de données. En d’autres termes nous formulerons le problème d’apprentissage supervisé de regroupements hiérarchiques sur l’espace continu des ultramétriques, d’où le nom du projet : ULTRA-LEARN.

Cette avancée reposera sur deux ingrédients principaux. Le premier est le développement de réseaux ultramétriques, c’est-à-dire de modèles entrainables et produisant en sortie une ultramétrique. Un réseau ultramétrique sera lui-même constitué de deux éléments, un réseau neuronal multicouches pour l’extraction de caractéristiques et une couche ultramétrique qui sera capable de produire une ultramétrique à partir des caractéristiques fournies par le réseau neuronal. Cette couche ultramétrique sera différentiable afin de permettre un apprentissage de bout-en-bout du réseau. Le deuxième ingrédient de la méthode sera la définition de fonctions de coût capables de mesurer efficacement et de manière différentiable la dissimilarité entre deux ultramétriques. Tous ces éléments devront également faire l’objet de développement algorithmiques afin de fonctionner sur des matériels hautement parallèles comme les GPU pour permettre le traitement de grands ensembles de données.

Les réseaux ultramétriques développés seront mis en pratique sur trois applications. Nous proposerons un réseau ultramétrique pour estimer des segmentations hiérarchiques d’images, c’est-à-dire la décomposition d’une image en objets et le raffinement itératif de ces objets en sous objets. La deuxième application visera le développement d’un classifieur capable de tirer parti d’une ontologie de classes connue a priori, par exemple nous savons qu’un chat et un chien sont tous deux des mammifères et qu’ils sont sémantiquement plus proches que d’un oiseau. Finalement la troisième application considérée est le regroupement hiérarchique semi-supervisé de données ; dans ce cas on cherchera à construire un regroupement hiérarchique optimal à partir d’informations partielles données a priori par un expert.