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.
| Date | 10 Aug 2020 |
|---|
| Original language | American English |
|---|
| Awarding Institution | - École de technologie supérieure
|
|---|
| Supervisor | Ismail Ben Ayed (Supervisor) & Éric Granger (Co-supervisor) |
|---|