Contrairement aux méthodes supervisées d’apprentissage machine, les méthodes non supervisées n’ont pas accès à des connaissances a priori, ce qui rend leur conception et optimisation difficiles. La communauté de chercheurs en apprentissage machine a entreprit d’importants efforts dans l’étude des algorithmes de partitionnement (clustering), en tant qu’outils d’analyse de données pour extraire des représentations similaires, et ce de manière non supervisée. Plus récemment, des recherches sur des algorithmes de partitionnement équitable ont vu le jour, visant ainsi à contrer des biais inhérents aux données, qui se traduisent souvent par des décisions biaisées envers certains groupes possédant des attributs sensibles (tel que le genre). Aussi, la recherche sur les méthodes d’apprentissage du type Few-Shot s’est rapidement développée. Le but est de transporter des connaissances acquises par un modèle entrainé sur un large jeu de données vers un domaine cible ne contenant que peu d’exemples annotés, avec de nouvelles classes. A travers cette thèse, nous explorons ces trois axes de recherches et proposons des modèles et techniques d’optimisation alliant flexibilité et scalabilité.
Cette thèse présente des algorithmes flexibles avec des méthodes d’optimisation de borne efficaces et extensibles à grande échelle. Nous optimisons des fonctionnelles qui intègrent des termes de groupement avec des contraintes de régularisation pour: (1) résoudre conjointement partitionnement et estimation de modes de densité; (2) assurer des solutions équitables de partitionnement en évitant des biais envers des groupes démographiques sensibles; et (3) résoudre les problèmes difficiles mais populaires d’apprentissage avec peu d’exemples annotés grâce à une approche simple de partitionnement de graphes sous contraintes, sans avoir recours aux méthodes complexes de méta-apprentissage. Les méthodes proposées sont validées avec des expériences exhaustives sur différents jeux de données références, et démontrent des performances très prometteuses en comparaison avec les méthodes dans la littérature.
En tant que première contribution, nous formulons la méthode Laplacian K-modes de partitionnement de graphes et d’estimation de modes de densité. Nous proposons une relaxation concave-convex du problème, ce qui nous permet d’obtenir un algorithme parallélisable, qui s’adapte bien à de larges jeux de données, ainsi qu’à de grandes dimensions. Nous optimisons une borne étroite (ou fonction auxiliaire) de notre relaxation, qui consiste, à chaque itération, à mettre à jour indépendamment chaque variable d’affectation de partition, avec garantie de convergence. Ainsi, notre méthode peut être trivialement parallélisée sur des jeux de données à grande échelle. De plus, nous montrons que les modes de densité peuvent être obtenus comme produit collatéral des variables d’affectation via de simples opérations de recherche de maximum, dont le coût additionnel évolue linéairement avec le nombre de points. Notre formulation ne nécessite pas de stocker et de diagonaliser une matrice d’affinité. Elle ne nécessite pas non plus d’effectuer de coûteuse projections et itérations internes pour résoudre le problème dual de Lagrange associé à la contrainte de simplexe pour chaque point. De plus, et contrairement à laméthode mean-shift, notre méthode d’estimation de mode de densité ne requiert pas d’effectuer des itérations internes de descente de gradient. Sa complexité est indépendante de la dimension de l’espace des données. Enfin, notre méthode permet d’obtenir des modes qui représentent des échantillons valides du jeu de données utilisé, et s’applique aussi bien à des domaine discrets qu’à des noyaux arbitraires. Nous reportons des expériences exhaustives sur une variété de jeu de données, qui témoignent toutes de la compétitivité de notre méthode en termes de qualité d’optimisation (c’est à dire la valeur de la fonction à convergence) et de précision de partitionnement.
Comme seconde contribution, nous explorons une forme variationnelle générale de partitionnement équitable, qui est capable d’intégrer des contraintes d’équitabilité dans une vaste classe d’objectifs de partitionnement. Les algorithmes de partitionnement traditionnels s’avèrent souvent biaisés envers des populations démographiques en raison des biais qui peuvent, par exemple, exister au sein même du jeu de données utilisé. Contrairement aux méthodes de partitionnement équitable qui existent déjà, notre formulation permet d’imposer n’importe quelle proportion désirée de groupes cibles dans chaque partition. De plus, elle permet de contrôler le compromis entre terme de partitionnement et terme d’équitabilité. Nous obtenons une fonction auxiliaire (borne supérieure étroite) de notre pénalité d’équitabilité basée sur la divergence de Kullback-Leibler (KL), via une décomposition concave-convexe, une propriété Lipschitzienne du gradient et l’inégalité de Pinsker. Notre borne supérieure peut être optimisée conjointement avec une variété de fonctions de partitionnement, incluant ceux basés sur les prototypes tels que K-means et K-median, ou encore ceux basés sur des graphes comme Normalized Cut. Il est intéressant de noter que, pour chaque itération, notre algorithme de partitionnement équitable effectue des mises à jour indépendantes pour chaque variable d’affectation, tout en garantissant la convergence. Ainsi, l’algorithme peut être facilement parallélisé pour des jeux de données à grande échelle. Une telle capacité d’adaptation est importante, car elle permet d’explorer différent niveaux de compromis entre équitabilité et partitionnement. En opposition aux algorithmes de partitionnement équitables spectraux, notre formulation ne nécessite pas de stocker et de diagonaliser une matrice d’affinité. Nous montrons l’efficacité, la flexibilité et l’adaptabilité de notre approche via des évaluations et comparaisons exhaustives aux méthodes existantes, sur plusieurs jeux de données.
Comme troisième contribution, nous explorons les problèmes d’apprentissage du type Few-Shot. A partir de peu d’échantillons annotés provenant de nouvelles classes, qui n’ont jamais été vues durant la phase d’entraînement, ce type de problèmes tente de généraliser à des échantillons non annotés provenant de ces nouvelles classes. Récemment, ce type de problèmes a reçu beaucoup d’attention de la part de la communauté, avec un vaste corps de travaux basés sur des méthodes complexes de méta-apprentissage, et des architectures alambiquées. Nous proposons un objectif basé sur une régularisation Laplacienne pour les tâches dy type Few-Shot, qui inclut deux types de potentiels: (1) Potentiels unaires assignant chaque échantillon requête au prototype de la classe le plus proche; et (2) Potentiels Laplaciens par paire encourageant des prédictions cohérentes pour des échantillons de requête voisins. Nous optimisons une borne supérieur étroite d’une relaxation concave-convexe de notre fonction, garantissant ainsi la convergence, tout en calculant des mises à jour indépendantes pour chaque échantillon requête. Suivant les protocoles expérimentaux standards, notre méthode LaplacianShot surpasse l’état de l’art par une grande marge, et uniformément sur tous les jeux de données, tout en conservant un entraînement basé sur une simple entropie croisée sur les classes de base et sans avoir recours à des méthodes de méta-apprentissage.
| Date | 10 août 2020 |
|---|
| langue originale | Anglais américain |
|---|
| Établissement diplômant | - École de technologie supérieure
|
|---|
| Superviseur | Ismail Ben Ayed (Directeur(-trice)) & Éric Granger (Codirecteur(-trice)) |
|---|