Flexible and scalable models for clustering and few-shot learning

Ziko, Imtiaz Masud (2020). Flexible and scalable models for clustering and few-shot learning. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation

PDF Télécharger (4MB) | Prévisualisation

Résumé

Unsupervised learning methods are difficult to design, and often lead to challenging optimization problems, due to the lack of prior knowledge. In particular, clustering algorithms have been studied extensively in machine learning, as a tool to analyze data through extracting similar patterns, in an unsupervised manner. More recently, research on fair clustering algorithms have emerged to avoid data-inherent biases in the decisions made by traditional clustering methods, for instance, with respect to some specific groups or sensitive attributes (e.g. gender). Also, few-shot learning problems have recently attracted substantial research efforts: The purpose is to transfer the knowledge from models supervised on large amounts of annotated data to target few-shot tasks, with new (unseen) classes and a few annotated samples per new class.

In this thesis, we investigate bound-optimization based clustering methods, which integrate various constraints and regularizers, e.g., fairness constraints or Laplacian regularization, and can deal efficiently with large-scale problems. Specifically, we propose flexible models, which optimize multi-term functionals, each integrating clustering objectives with some constraints or regularizers. We further derive tight upper bounds (auxiliary functions) of the functionals to provide scalable (parallel-update) solutions, with convergence guarantee and competitive performances. We propose: (1) Joint graph clustering and prototype density-mode estimation for large-scale problems (Scalable Laplacian K-modes); (2) A general and flexible variational paradigm for fair clustering, which enables to control the trade-off levels between the clustering and fairness terms (Variational Fair Clustering); (3) A fast Laplacian-regularized few-shot inference, which can be viewed as a constrained graph clustering, and outperforms state-of-theart few-shot methods by significant margins (Laplacian Regularized Few-Shot Learning).

As a first contribution, we advocate the Laplacian K modes model for a joint graph clustering and density mode estimation method. We propose a concave-convex relaxation of the problem, which yields a parallel algorithm that scales up to large datasets and high dimensions. We optimize a tight bound (auxiliary function) of our relaxation, which, at each iteration, amounts to computing an independent update for each cluster assignment variable, with guaranteed convergence. Therefore, our bound optimizer can be trivially distributed for large-scale data sets. Furthermore, we show that the density modes can be obtained as byproducts of the assignment variables via simple maximum-value operations whose additional computational cost is linear in the number of data points. Our formulation does not need storing a full affinity matrix and computing its eigenvalue decomposition, neither does it perform expensive projection steps and Lagrangian-dual inner iterates for the simplex constraints of each point. Furthermore, unlike mean-shift, our density-mode estimation does not require inner-loop gradient-ascent iterates. It has a complexity independent of feature space dimension, yields modes that are valid data points in the input set and is applicable to discrete domains as well as arbitrary kernels. We report comprehensive experiments over various data sets, which show that our algorithm yields very competitive performances in terms of optimization quality (i.e., the value of the discrete variable objective at convergence) and clustering accuracy.

As a second contribution, we investigate a general variational formulation of fair clustering, which can integrate fairness constraints with a large class of clustering objectives. Traditional clustering algorithms exhibit biases towards specific demographic groups due to, for instance, the biases that exist within the data. Unlike the existing fair clustering methods, our formulation can impose any desired (target) demographic proportions within each cluster. Furthermore, it enables to control the trade-off between the fairness and clustering terms. We derive an auxiliary function (tight upper bound) of our Kullback–Leibler (KL) based fairness penalty via its concave-convex decomposition, its Lipschitz-gradient property and the Pinsker inequality. Our upper bound can be optimized jointly with various clustering objectives, including prototype-based, such as K-means and K-median, or graph-based such as Normalized Cut. Interestingly, at each iteration, our general fair-clustering algorithm performs an independent update for each assignment variable, while guaranteeing convergence. Therefore, it can be easily distributed for large-scale data sets. Such scalability is important as it enables to explore different trade-off levels between the fairness and clustering objectives. Unlike fairness-constrained spectral clustering, our formulation does not need storing an affinity matrix, nor computing its eigenvalue decomposition. We show the effectiveness, flexibility and scalability of our approach through comprehensive evaluations and comparisons to the existing methods over several data sets.

As a third contribution, we investigate few-shot learning problems, which attempt to generalize to unlabeled query samples of new classes, which are unseen during training, given just a few labeled examples of those classes. Few shot learning has recently received substantial research interest, with a large body of works based on complex meta-learning strategies and architecture choices. We propose a Laplacian-regularization objective for few-shot tasks, which integrates two types of potentials: (1) unary potentials assigning query samples to the nearest class prototype, and (2) pairwise Laplacian potentials encouraging nearby query samples to have consistent predictions. We optimize a tight upper bound of a concave-convex relaxation of our objective, thereby guaranteeing convergence, while computing independent updates for each query sample. Following the standard experimental settings for few-shot learning, our technique outperforms state-of-the-art methods by significant margins, consistently across different benchmarks, without resorting to complex meta-learning strategies.

Titre traduit

Modèles flexibles et efficaces pour clustering et apprentissage du type few-shot

Résumé traduit

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.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Manuscript-based thesis presented to École de technologie supérieure in partial fulfillment for the degree of doctor of philosophy". Comprend des références bibliographiques (pages 107-117).
Mots-clés libres:	apprentissage non supervisé, groupement, contraintes d’équitabilité, régularisation laplacienne, apprentissage few-shot, optimisation de bornes, relaxation de contraintes
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Ben Ayed, Ismail
Codirecteur:	Codirecteur Granger, Éric
Programme:	Doctorat en génie > Génie
Date de dépôt:	13 janv. 2021 18:22
Dernière modification:	13 janv. 2021 18:22
URI:	https://espace.etsmtl.ca/id/eprint/2613

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt