# A Tutorial on Discriminative Clustering and Mutual Information

Louis Ohl, Pierre-Alexandre Mattei, Frederic Precioso

<figure><img src="image_1.png" /></figure>

## To cite this version:

Louis Ohl, Pierre-Alexandre Mattei, Frederic Precioso. A Tutorial on Discriminative Clustering and Mutual Information. ACM Computing Surveys, 2025, 58 (4), pp.1-36. 10.1145/3748255. hal-05419674

HAL Id: hal-05419674

https://hal.science/hal-05419674v1

Submitted on 16 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# A tutorial on discriminative clustering and mutual information

Louis Ohl¹, Pierre-Alexandre Mattei²,³, and Frédéric Precioso²,⁴

¹Linköping University, Division of Statistics and Machine Learning - Linköping, Sweden

²Inria, Université Côte d'Azur, Maasai team - Nice, France

³CNRS - LJAD

⁴CNRS - I3S

## Abstract

To cluster data is to separate samples into distinctive groups that should ideally have some cohesive properties. Today, numerous clustering algorithms exist, and their differences lie essentially in what can be perceived as “cohesive properties”. Therefore, hypotheses on the nature of clusters must be set: they can be either generative or discriminative. As the last decade witnessed the impressive growth of deep clustering methods that involve neural networks to handle high-dimensional data often in a discriminative manner; we concentrate mainly on the discriminative hypotheses. In this paper, our aim is to provide an accessible historical perspective on the evolution of discriminative clustering methods and notably how the nature of assumptions of the discriminative models changed over time: from decision boundaries to invariance critics. We notably highlight how mutual information has been a historical cornerstone of the progress of (deep) discriminative clustering methods. We also show some known limitations of mutual information and how discriminative clustering methods tried to circumvent those. We then discuss the challenges that discriminative clustering faces with respect to the selection of the number of clusters. Finally, we showcase these techniques using the dedicated Python package, GemClus, that we have developed for discriminative clustering.

## 1 Introduction

Clustering is a fundamental learning task that involves separating data samples into several groups, each named cluster, without using labels. A cluster should be a cohesive set of elements that share some common properties. Ideally, these commonly shared properties should allow us to discriminate one cluster from the other. Therefore, this task is useful for exploring and uncovering knowledge in data analysis, e.g. biology with microarray analysis (McLachlan et al., 2002; Sturn et al., 2002), customer segmentation (Kashwan and Velu, 2013; Kansal et al., 2018), social network analysis (Bedi and Sharma, 2016; Himelboim et al., 2017), political campaign analysis (Bode et al., 2015) or disease phenogroup discovery (Kwak et al., 2020).

Given a potentially large collection of data samples $x_i$ gathered into a dataset $\mathcal{D}$, a clustering algorithm is a model $f$ that assigns each sample $x_i$ to a cluster $y_i$. While $x_i$ may be from a high-dimensional space $\mathcal{X}$ e.g. images, tabular entries, or graphs, the cluster assignment $y$ is only an integer bounded by the maximum desired number of clusters $K$. Formally:

$$f: \mathcal{X} \rightarrow [K], \\ x_i \mapsto f(x_i) = y_i. \tag{1}$$

Conceptually, clustering belongs to the family of unsupervised learning. This means that the dataset does not contain any information about a potential ideal target. Therefore, we do not have explicit information guiding the optimisation of the model $f$.

In the absence of such targets, clustering hinges on two main questions (Hennig, 2015):
1. The first main question concerns the assessment of correct clustering. We are interested here in knowing if the discovered clusters are insightful and teach us something about the data. However, we must emphasise that there is no global consensus on the definition of a cluster. Indeed, it was shown that each clustering algorithm cannot satisfy simultaneously desirable properties (Kleinberg, 2003). In general, the use case drives the need, and the "clustering is in part in the eye of the beholder" (Estivill-Castro, 2002). We may thus say that there are no absolute best clustering algorithm, yet some may be relatively better depending on the context.

2. The second major question to address in clustering is the actual, sometimes called optimal, number of clusters i.e. the value of $K$ in Eq. (1). For instance, a clustering algorithm could find more insightful clusters when searching only for 5 of them instead of 10. Perhaps more clusters would be more beneficial. Yet again, the lack of a formal definition of clusters implies that no method can be absolutely better than others in finding the correct number of clusters if that number is even existing. However, by restricting clusters to a narrow definition, there are methods to assess the quality of the number of clusters (Tibshirani et al., 2001; Davies and Bouldin, 1979; Rousseeuw, 1987; Biernacki et al., 2000).

During the last decade, clustering algorithms benefitted from the integration of neural networks e.g. Li et al. (2021); Park et al. (2021); Ronen et al. (2022). The main motivation is that "conventional clustering methods usually have poor performance on high-dimensional data, due to the inefficiency of similarity measures used in these methods" (Min et al., 2018). Therefore, the integration of neural networks in clustering, called deep clustering, is "expected to continue the tradition of clustering algorithms and to expand their ability to elucidate the hidden structure in big data [...]" (Nutakki et al., 2019) owing to their representation power. As proposals of deep clustering algorithm increase, taxonomy proposals have followed through surveys. We can start with Min et al. (2018) who proposed to classify clustering algorithms depending on the nature of their neural network architecture: auto-encoder, Deep Neural Network (DNN), variational auto-encoder (VAE), or generative adversarial network (GAN). It is interesting that VAE and GANs are considered as different from DNNs because they are themselves built using DNNs. The initial motivation is that the DNN category only employs a single clustering loss. It is notable that such a taxonomy omits the nature of the clustering loss function, as Min et al. (2018) argue that "since the essence of deep clustering is to learn a clustering-oriented representation, it is not suitable to classify methods according to the clustering loss". This taxonomy is still presented for the single-view clustering algorithms category in a survey by Ren et al. (2024).

Later reviews motivated that loss functions should be also part of the taxonomy, notably because a "good cost or loss function [...] captures what a good representation or clustering is" (Nutakki et al., 2019). In this sense, Nutakki et al. (2019) classified deep clustering algorithms depending on their training procedure: sequential i.e. one algorithm after another, joint, i.e. simultaneously training the deep learning backbone and learning clusters, or closed-loop multistep clustering, i.e. iteratively refining the training of multiple algorithms. Under slightly different names, this taxonomy is kept by Zhou et al. (2022), with the addition of generative models as a different category. For an overview of current deep clustering algorithm, we recommend reading Ren et al. (2024), and for understanding the current definitions and limitations of deep clustering building blocks as well as current benchmark procedures, we recommend Zhou et al. (2022).

Our goal in this tutorial is not to introduce a specific novel taxonomy. Instead, we propose to focus on discriminative clustering algorithms. These models are underlying some of the categories above: joint clustering, iterative clustering Nutakki et al. (2019), and are often based on DNN architectures in the taxonomy of Min et al. (2018). Discriminative clustering is the opposite approach to generative clustering, which encompass GANs and VAEs. In line with the deep clustering hope of leveraging powerful representation, discriminative clustering models do not set parametric assumptions on the data distribution. Therefore, such deep discriminative methods seem to partially address (or omit) the major question of assessment (1): we hope to get a good representation for clustering, but do not question if the mean to obtain such a representation guarantees that they are insightful. When learning representations or clustering using discriminative models, assumptions remain and are hidden in other
details, especially the objective function. This is the case the case of the mutual information between
data and clusters that has been a cornerstone of the development of discriminative clustering. In order
to discuss the current state of such deep clustering methods, we propose to review the historical joint
evolution of discriminative clustering and mutual information. We will draw parallels with generative
models and classification methods for further understanding. The contributions of this paper are:

* An accessible introduction to the field of discriminative clustering (Sections 2, 3 and 4)

* A historical account on the usage of mutual information for discriminative clustering leading to modern deep clustering methods. Notably, we present links between lines of research corresponding to different views on mutual information in discriminative clustering. (Section 5)

* A highlight on the interpretation of clustering models in contrastive learning context. We show how the optimisation of a lower bound on MI implicitly minimises a variational inference problem between data and augmentations. (Section 5)

* An emphasis on the call for model selection strategies that are in line with those novel clustering models, a topic that is often omitted. (Section 6)

* A showcase of the discussed methods using GemClus, a Python package that we developed. (Section 7)

To the best of our knowledge, this tutorial is the first of a kind on discriminative clustering and the different lines of research that arose in this field. In related surveys Jain et al. (1999); Min et al. (2018); Nutakki et al. (2019); Zhou et al. (2022); Ren et al. (2024); Wei et al. (2024), the word discriminative appears to qualify learnt features, often in the sense of their ability to make a distinction between two samples.

We start by discussing in Section 2 the two different types of modelling for clustering: generative and discriminative. We first detail the nature of the hypotheses in generative clustering, and existing solutions for major questions (1) and (2).

We continue with the challenges arising from the discriminative formulation of clustering in Section 3 for optimising the parameters of the models. By drawing a parallel with classification tasks, we show how mutual information is introduced as a natural objective for learning the model parameters. We finish the section by highlighting the known limitations of mutual information. Then, we complete the presentation of objectives by detailing other clustering objectives, e.g. K-means, in Section 4.

In Section 5, we dive in the history of mutual information as a clustering objective function. We start by discriminative models perceived as decision boundaries decoupled from the objective function (Bridle et al., 1992) and show how the progressive implicit need to regularise mutual information led to more intricate models where the model is no longer decoupled from the objective function, as in contrastive learning (Li et al., 2021).

We then draw our attention in Section 6 to choosing a number of clusters. We notably insist that the selection strategy should be aligned with the clustering hypotheses set by the dual combination model and objective.

We finish in Section 7 by presenting an example of discriminative clustering application on a simple dataset. We notably present here *GemClus*, a package that covers discriminative clustering methods presented in Section 5.

The notations used throughout the paper are listed in Table 1.

## 2 Modelling frameworks

Clustering is the task of grouping data samples. Each data sample is formally described as a random variable $x$, taking values from $\mathcal{X}$. This variable is uni- or multidimensional, with a mix of continuous and/or discrete dimensions. It also possible that $\mathcal{X}$ concerns graphs. We consider that we have a
<table><caption>Table 1: Notations used in this paper.</caption><thead><tr><th>Notation</th><th>Description</th><th>Notation</th><th>Description</th></tr></thead><tbody><tr><td>n</td><td>Number of observations/samples</td><td>d</td><td>Number of features per sample</td></tr><tr><td>K</td><td>Number of clusters</td><td>Δ<sup>K−1</sup></td><td>The K − 1-simplex</td></tr><tr><td>X</td><td>Data space</td><td>x</td><td>An observation from X</td></tr><tr><td>x<sub>ij</sub></td><td>The j-th feature of the i-th observation in the dataset D</td><td>[[n]]</td><td>The set of natural integers from 1 to n</td></tr><tr><td>C</td><td>Cluster containing samples</td><td>y</td><td>The cluster membership</td></tr><tr><td>Z</td><td>An intermediate representation space</td><td>z</td><td>A continuous variable from Z</td></tr><tr><td>H</td><td>Reproducing kernel Hilbert space</td><td>|·|</td><td>Cardinal</td></tr><tr><td>p<sub>θ</sub></td><td>Distribution with parameters θ</td><td>H(·)</td><td>Entropy of a random variable</td></tr><tr><td>E<sub>p</sub>[·]</td><td>Expectation of a random variable under distribution p</td><td>V<sub>p</sub>[·]</td><td>Variance of a random variable under distribution p</td></tr><tr><td>N</td><td>Multivariate and univariate Gaussian distribution</td><td>δ<sub>x</sub></td><td>Delta Dirac distribution located in position x</td></tr><tr><td>1</td><td>Indicator function</td><td>I</td><td>Mutual information</td></tr><tr><td>L</td><td>An objective function</td><td>E</td><td>Energy of an energy-based model</td></tr><tr><td>||·||</td><td>Norm</td><td>D<sub>KL</sub>(·||·)</td><td>Kullback-Leibler divergence</td></tr><tr><td>c(·, ·)</td><td>A distance function (or cost) between samples in X</td><td>κ(·, ·)</td><td>A kernel function between samples in X</td></tr></tbody></table>

dataset of $n$ independent and identically distributed samples $\mathcal{D} = \{\mathbf{x}_i\}_{i=1}^n$. The membership of the cluster is indicated by $y$, a discrete random variable taking values in $\llbracket K \rrbracket$, where $K$ is the number of clusters to determine.

To link these two random variables, a model is required. However, the nature of the assumptions made for the model greatly impacts the algorithmic procedures for learning. Here we describe two major contrasting frameworks: the *generative* and the *discriminative* models.

## 2.1 Starting from Bayes theorem

A clustering algorithm can be described as a probability distribution $p$ that assigns a cluster membership $y$ to a given sample $\mathbf{x}$. This distribution is controlled by a set of parameters $\theta$. Thus, a clustering model is the parameterisation of the distribution $p$ by $\theta$ and so it is the conditional probability $p_{\theta}(y | \mathbf{x})$. According to the Bayes theorem, we can devise a definition of the clustering model $p_{\theta}(y | \mathbf{x})$:

$$p_{\theta}(y | \mathbf{x}) = \frac{p_{\theta}(\mathbf{x} | y)p_{\theta}(y)}{p_{\theta}(\mathbf{x})} \qquad (2)$$

This theorem highlights that building a distribution binding clusters $y$ and data $\mathbf{x}$ necessarily implies the existence of three other distributions: one for the generation of the data given a cluster $p_{\theta}(\mathbf{x} | y)$, one for the proportion of clusters $p_{\theta}(y)$ and one for the probability of observing the data $p_{\theta}(\mathbf{x})$, often called *likelihood*. We further note that as the clustering distribution is dependent on $\theta$, other distributions are consequently also dependent on $\theta$, unless specified otherwise.

Given a clustering model $p_{\theta}(y | \mathbf{x})$, the final clustering of a dataset is the assignment of each sample in the dataset $\mathcal{D}$ to the cluster for which the conditional probability is maximal. The $k$-th cluster is defined as:

$$C_k = \{\mathbf{x} \in \mathcal{D} | k = \arg \max_{y} p_{\theta}(y | \mathbf{x})\}. \qquad (3)$$

The definition offered by the Bayes theorem on the clustering models brings two different ways of defining the clustering model and its parameters. The first one is the *generative* modelling which views the clustering membership as a latent variable explaining how the data was generated, and the
<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /><figcaption>Figure 1: The generative and discriminative modelling frameworks for clustering models. Observed variables are shaded.</figcaption></figure>

second one is the discriminative modelling which seeks immediately the clusters from the data. With probabilistic graphical models (Koller and Friedman, 2009, Chapter 1), we can summarise both views with Figure 1.

## 2.2 Generative models

### 2.2.1 Definition

In generative modelling, knowing the latent cluster $y$ is sufficient to describe the distribution of its associated data $\boldsymbol{x}$, see Figure 1a. The design of this model is therefore focused on the right hand-side factors of the Bayes theorem in Eq. (2): a generative model is the design of $p_{\theta}(\boldsymbol{x} | y)$, with learnable proportions $p_{\theta}(y)$ (Bouveyron et al., 2019). Often, the distribution $p_{\theta}(\boldsymbol{x} | y)$ is very simple, e.g. Gaussian distribution. The generative approach can be interpreted as creating a ready-made template of how clusters would look like, then stretching the template until it fits as best as possible the observed data. The central idea of fitness is often measured with the likelihood:

$$p_{\theta}(\boldsymbol{x}) = \sum_{k=1}^{K} p_{\theta}(\boldsymbol{x} | y=k) p_{\theta}(y=k). \qquad (4)$$

The intuition is that a model similar to the true process that generated the data should be likely to generate similar samples to those observed. The clustering distribution $p_{\theta}(y | \boldsymbol{x})$ is then a consequence of the modelling. In fact, a generative model indirectly specifies the clustering distribution because it is implicitly proportional to the generative process $p_{\theta}(\boldsymbol{x} | y)p_{\theta}(y)$.

We give a simple example of a generative model where each cluster obeys a Gaussian distribution in Figure 2. Therefore, each cluster distribution is written $p_{\theta}(\boldsymbol{x} | y) = N(\boldsymbol{x} | \boldsymbol{\mu}_{y}, \boldsymbol{\sigma}_{y}^{2})$ and each cluster proportion $p_{\theta}(y) = \pi_{y}$. The parameters $\theta$ comprise the location $\boldsymbol{\mu}_{y}$, the scale $\boldsymbol{\sigma}_{y}^{2}$ and proportion $\pi_{y}$ for each cluster. In the one-dimensional binary example from Figure 2, we have a total of 6 parameters with $\theta = \{\boldsymbol{\mu}_{\text{red}}, \boldsymbol{\sigma}_{\text{red}}^{2}, \pi_{\text{red}}, \boldsymbol{\mu}_{\text{blue}}, \boldsymbol{\sigma}_{\text{blue}}^{2}, \pi_{\text{blue}}\}$. The resulting likelihood is defined as:

$$p_{\theta}(\boldsymbol{x}) = p_{\theta}(y = \text{red})p_{\theta}(\boldsymbol{x} | y = \text{red}) + p_{\theta}(y = \text{blue})p_{\theta}(\boldsymbol{x} | y = \text{blue}) \qquad (5)$$

$$= \pi_{\text{red}}N(\boldsymbol{x} | \boldsymbol{\mu}_{\text{red}}, \boldsymbol{\sigma}_{\text{red}}^{2}) + \pi_{\text{blue}}N(\boldsymbol{x} | \boldsymbol{\mu}_{\text{blue}}, \boldsymbol{\sigma}_{\text{blue}}^{2}). \qquad (6)$$

For a mixture of 2 $d$-dimensional Gaussian distribution with proportions $\pi_1, \pi_2$, locations $\boldsymbol{\mu}_1, \boldsymbol{\mu}_2$ and the same covariance $\boldsymbol{\Sigma}$, it is possible to show that the clustering distribution is defined by (Bishop, 2007, Eq. 4.64):

$$p_{\theta}(y = 1 | \boldsymbol{x}) = \text{Sigmoid}(\boldsymbol{w}^{\top}\boldsymbol{x} + b), \qquad (7)$$

where the sigmoid function is defined for all real values $a$:

$$\text{Sigmoid}(a) = \frac{1}{1 - e^{-a}}, \qquad (8)$$

and the coefficients are:

$$\boldsymbol{w} = \boldsymbol{\Sigma}^{-1}(\boldsymbol{\mu}_1 - \boldsymbol{\mu}_2), \qquad (9)$$

and:

$$b = -\frac{1}{2}\boldsymbol{\mu}_{1}^{\top}\boldsymbol{\Sigma}^{-1}\boldsymbol{\mu}_{1} + \frac{1}{2}\boldsymbol{\mu}_{2}^{\top}\boldsymbol{\Sigma}^{-1}\boldsymbol{\mu}_{2} + \log \frac{\pi_{1}}{\pi_{2}}. \qquad (10)$$
<figure><img src="image_5.png" /><figcaption>Figure 2: An example of generative models with 2 clusters in 1 dimension. The parameters $\theta$ of the model comprise the Gaussian distribution locations $\mu_{\text{red}} = -1$, $\mu_{\text{blue}} = 2$, the scales $\sigma_{\text{red}}^2 = \sigma_{\text{blue}}^2 = 1$ and the proportions of each clusters.</figcaption></figure>

We observe in Eq. (7) that the clustering distribution $p_{\theta}(y | \mathbf{x})$ is therefore drawn around a linear decision boundary of coefficients $\mathbf{w}$ and $b$ when the covariances are equal between 2 Gaussian distributions.

### 2.2.2 Learning

To optimise the parameters, the most straightforward method is maximum likelihood, i.e. maximising the value of the likelihood $p_{\theta}(\mathbf{x})$ over all samples $\mathbf{x}_i$ in the dataset $\mathcal{D}$. Under the common assumption of i.i.d. samples in the dataset, the maximum likelihood parameter is defined as:

$$ \hat{\theta}_{\text{MLE}} \in \arg \max_{\theta} \prod_{\mathbf{x} \in \mathcal{D}} p_{\theta}(\mathbf{x}). \qquad (11) $$

However, this likelihood is often challenging to maximise, due to the unobserved and latent nature of the cluster membership $y$. In such a case, an Expectation-Maximisation (EM) algorithm can be used to find a local maximum for the likelihood (McLachlan and Krishnan, 2007). This algorithm alternates between two steps. In the first step, called Expectation, the probability of cluster membership is estimated using the current state of the model parameters $\theta$. In the second step, called Maximisation, the parameters $\theta$ are optimised to maximise the likelihood given the current cluster membership probabilities. This procedure is repeated multiple times until convergence. Still today, this algorithm remains one of the most commonly used in mixture modelling.

The most common example of a generative clustering model is the Gaussian Mixture Model (GMM), where each cluster is assumed to follow a Gaussian distribution (Banfield and Raftery, 1993; Bouveyron et al., 2019). Other examples comprise mixtures Gaussian copulae for handling mixed types of variables (Marbac et al., 2017), mixtures of multivariate $t$-distribution (Peel and McLachlan, 2000) for robustness against outliers thanks to heavily tailed distributions, for instance, applied on Box-Cox transformed data (Lo et al., 2008), mixtures of Poisson distributions (Karlis and Tsiamyrtzis, 2008), or mixtures of multinomial distributions (Goodman, 1974).

### 2.2.3 Selecting a number of clusters

Model-based clustering benefits from a large panel of statistical tools. In particular, it is possible to assess the adequation of the model to the data and validate a correct choice for the number of clusters with internal scores. For example, the Bayesian Information Criterion (BIC, Schwarz, 1978) is defined for the parameters $\hat{\theta}_{\text{MLE}}$ obtained after training:

$$ \text{BIC}(K) = 2 \sum_{\mathbf{x} \in \mathcal{D}} \log p_{\hat{\theta}_{\text{MLE}}}(\mathbf{x}) - \nu_K \log n, \qquad (12) $$

where $\nu_K$ is the number of free parameters in $\hat{\theta}_{\text{MLE}}$ for $K$ clusters. For example: in the previous GMM example, we had $\nu_K = 5$ because the proportions of the clusters $\pi_{\text{red}}$ and $\pi_{\text{blue}}$ depend on each other: $\pi_{\text{blue}} = 1 - \pi_{\text{red}}$. BIC encourages models to fit well the data with a strong likelihood while maintaining
a low number of parameters. This criterion focuses on the good number of components that fit well the data in terms of likelihood. However, this does not imply that it is correct for clustering the data. A more adequate internal score for mixture-based clustering models is the Integrated Complete Likelihood (ICL, Biernacki et al., 2000) for K clusters and M components:

$$ \text{ICL}(K, M) = \text{BIC}(M) - \sum_{\mathbf{x} \in \mathcal{D}} \sum_{y=1}^{K} p_{\hat{\theta}_{\text{MLE}}}(y | \mathbf{x}) \log p_{\hat{\theta}_{\text{MLE}}}(y | \mathbf{x}). \quad (13) $$

The ICL penalises the BIC by subtracting the entropy of the cluster memberships of the model. As the entropy becomes smaller when the model decisions are clear-cut, ICL encourages models for which the number of clusters leads to distinct separations.

### 2.2.4 Generative hypotheses

The difficulty of generative models for clustering lies essentially in the choice of the generative distribution $p_{\theta}(\mathbf{x} | y)$. In practice, the choice of distribution, e.g. Poisson, Gaussian, is often guided by the expertise developed on the dataset. However, the statistical challenges emerging from the high-dimensional nature of modern data call for adequate regularisations and constraints over the distributions (Bouveyron et al., 2019, Chapter 8).

Beyond the usage of well-known distributions with scalar or matrix parameters, the last decade witnessed the rise of generative modelling with neural networks, notably with the Variational Auto-Encoders (VAE, Kingma and Ba, 2014; Rezende et al., 2014) and the Generative Adversarial Networks (GAN, Goodfellow et al., 2014). Both methods aim to build generative models in which the latent variable z is continuous contrary to generative clustering models. Starting from easy-to-sample distributions, these models transform low-dimensional latent variables into high-dimensional variables using complex non-linear transformations. VAEs, as part of the broader class of Deep Latent Variable Models (DLVM), parameterise the generative distribution with the output of a function g from the latent variable: $p(x | g(z))$. For example, g can be a neural network that returns the mean and diagonal covariance of a Gaussian distribution. To optimise the generative process, an amortised variational inference method is often used with an encoder network as the proposal distribution for approximating the posterior distribution of the latent variable, hence the name variational auto-encoder. GANs focus instead on optimising a zero-sum game, where the generative distribution must produce samples of sufficient quality to fool a discriminative network, sometimes called a critic. The goal of this discriminator is to differentiate true samples coming from a target distribution (defined by the data), from samples created de novo by the generator. The core limitation of these initial models in the context of clustering is the usage of a continuous latent variable, the code, rather than a discrete variable, the cluster. There are proposals to make the latent variable categorical (Jang et al., 2017), but this does not imply that they were intended for clustering. Thus, extensions were proposed to adapt VAEs and GANs for clustering (Jiang et al., 2017; Dilokthanakul et al., 2016; Springenberg, 2015; Mello et al., 2022).

In general, generative modelling presents compelling tools for clustering. However, the difficulty in making assumptions on the data distribution is one of the main limitations to the success of the model. Moreover, in the context of mixed types of variables, this choice of parametric assumption becomes even harder. Often, assumptions of independence between categorical and continuous variables are made to achieve clustering with mixture models, of mixed-type variables (Marbac et al., 2017; Marbac and Sedki, 2017; Ma et al., 2020).

## 2.3 Discriminative models

To avoid the burden of choosing parametric assumptions following the generative modelling, we turn to the discriminative point of view. In this context, we do not take any assumption at all regarding the data distribution and denote it $p_{\text{data}}(\mathbf{x})$. However, we assume to be able to sample from a given dataset
D. The discriminative framework can be interpreted as taking the data as is, and inferring clusters instead of finding assignments suiting a notion of likelihood. Thus, we only design a discriminative model $p_{\theta}(y | \mathbf{x})$ and we obtain:

$$p_{\theta}(\mathbf{x}, y) = p_{\text{data}}(\mathbf{x})p_{\theta}(y | \mathbf{x}). \qquad (14)$$

From a generative perspective, the discriminative modelling corresponds to the joint distribution of a data distribution and clustering model with decoupled parameters (Minka, 2005). The data is generated by a set of external parameters $\theta'$ and the complete model is written $p_{\theta,\theta'}(\mathbf{x}, y) = p_{\theta}(y | \mathbf{x})p_{\theta'}(\mathbf{x})$. In contrast to this generative view, we do not even assume the existence of such parameters in our discriminative models when writing $p_{\text{data}}(\mathbf{x})$.

In this paper, we use the term discriminative in the sense, for instance, of Minka (2005) and Bishop (2007). Note that some other clustering methods employ the term discriminative to designate the finding of discriminative subspaces, e.g. using Fisher discriminant analysis, linear discriminant analysis (De la Torre and Kanade, 2006; Ye et al., 2007; Bouveyron and Brunet, 2012).

This framework can be used conveniently with any function $\psi_{\theta}$ whose outputs lie in the $K-1$ simplex, where $K$ is the number of clusters. This output can then be considered as the parameters of a categorical distribution defining the conditional cluster membership:

$$y | \mathbf{x} \sim \text{Categorical}(\psi_{\theta}(\mathbf{x})). \qquad (15)$$

Thanks to the degrees of freedom for the definition of $\psi_{\theta}$, the discriminative clustering framework can tolerate various softmax-ended neural networks. For example, we can consider logistic regressions where the discriminative model takes the form:

$$\psi_{\theta}(\mathbf{x}) = \text{Softmax}(\mathbf{W}^{\top}\mathbf{x} + \mathbf{b}), \qquad (16)$$

where the parameters are $\theta = \{\mathbf{W}, \mathbf{b}\}$. The softmax function is defined for any real vector and returns a stochastic vector:

$$\text{Softmax}(\mathbf{z}) = \left[ \frac{e^{\mathbf{z}_1}}{Z}, \dots, \frac{e^{\mathbf{z}_i}}{Z}, \dots, \frac{e^{\mathbf{z}_d}}{Z} \right]^{\top}, \quad \text{with} \quad Z = \sum_{i=1}^{d} e^{\mathbf{z}_i}. \qquad (17)$$

Thus, in contrast to generative modelling, discriminative modelling encompasses our hypotheses through the design of the decision boundary. For example, Eq. (16) shows that a logistic regression is the discriminative equivalent of a mixture of Gaussian distributions with equal variances: both their decision boundaries are linear, as we showed in Eq. (7).

Beyond the scope of clustering, discriminative modelling is the core approach used for classification with neural networks. Thus, a neural network that was well designed for a classification task on a specific type of data can be used immediately for clustering. However, the discriminative perspective in the context of clustering severely affects the procedures to learn optimal parameters.

# 3 The challenge of learning in discriminative clustering

We now discuss how discriminative models can be trained and the implied properties.

## 3.1 The shortcomings of classical statistical tools

Due to the absence of a model on the data distribution $p_{\text{data}}(\mathbf{x})$, we cannot use maximum likelihood to learn the optimal parameters, and consequently neither expectation-maximisation nor variational inference. Additionally, we cannot construct a generative cluster distribution $p_{\theta}(\mathbf{x} | y)$, because we do not have access to the distribution $p_{\text{data}}(\mathbf{x})$. In other words, a discriminative model cannot generate
samples outside the dataset. One quantity we can actually estimate is the vector of proportions of the clusters through marginalisation:

$$p_{\theta}(y) = \mathbb{E}_{\mathbf{x} \sim p_{\text{data}}(\mathbf{x})} [p_{\theta}(y | \mathbf{x})]. \qquad (18)$$

In practice, we cannot evaluate the density $p_{\text{data}}(\mathbf{x})$. This means that the value of the cluster proportions is only estimated by Monte Carlo on the dataset:

$$p_{\theta}(y) \approx \frac{1}{|\mathcal{D}|} \sum_{\mathbf{x} \in \mathcal{D}} p_{\theta}(y | \mathbf{x}). \qquad (19)$$

In summary, the absence of parametric assumptions on the data distribution leads to the absence of joint modelling:

$$\underbrace{p_{\theta}(y | \mathbf{x})}_{\text{Known}} \times \underbrace{p_{\text{data}}(\mathbf{x})}_{\text{Unknown}} = \underbrace{p_{\theta}(\mathbf{x} | y)}_{\text{Unknown}} \times \underbrace{p_{\theta}(y)}_{\text{Estimable}} = \underbrace{p_{\theta}(\mathbf{x}, y)}_{\text{Unknown}}. \qquad (20)$$

The only thing we assume to be able to do is sampling from the data distribution, owing to the presence of a dataset $\mathcal{D} = \{\mathbf{x}_i\}_{i=1}^n$, which we use to estimate Eq. (18).

Therefore, a different approach must be taken for training discriminative models in clustering. To build such an approach, we will draw inspiration from the supervised models in classification that are often discriminative. These models leverage learning with an objective function that is decoupled from the model.

## 3.2 Objective functions in classification

In the absence of parametric assumptions on the data, we are interested only in grouping the samples based on some meaningful criterion. In classification tasks, in contrast to clustering, we have access to labels that provide us with this guiding criterion. Therefore, we know that there exists an ideal distribution $p_{\text{data}}(y | \mathbf{x})$ that we must match as best as possible with our model $p_{\theta}(y | \mathbf{x})$. To that end, we must measure the distance of our current model from this ideal distribution and make it as close as possible. The most common distance between two distributions is the Kullback-Leibler (KL) divergence. For two arbitrary distributions $q_1$ and $q_2$, the KL divergence is defined as:

$$D_{\text{KL}}(q_1(\mathbf{z})) \| q_2(\mathbf{z})) = \mathbb{E}_{\mathbf{z} \sim q_1(\mathbf{z})} \left[ \log \frac{q_1(\mathbf{z})}{q_2(\mathbf{z})} \right]. \qquad (21)$$

Note that the KL is in fact not a distance since it does not respect symmetry. Incorporating in this divergence the definition of our target model $p_{\text{data}}(y | \mathbf{x})$ and our classification model $p_{\theta}(y | \mathbf{x})$ would only tell us how far apart these two distributions are for a specific datum $\mathbf{x}$. Therefore, we wrap up this divergence in an expectation over the data distribution to ensure that on average, our model sticks as best as possible to the targets. This data distribution is part of the ideal model $p_{\text{data}}(\mathbf{x})$. Thus, we obtain the average distance of our parameters to the data distribution $\mathcal{L}(\theta)$:

$$\mathcal{L}(\theta) = \mathbb{E}_{\mathbf{x} \sim p_{\text{data}}(\mathbf{x})} [D_{\text{KL}}(p_{\text{data}}(y | \mathbf{x}) \| p_{\theta}(y | \mathbf{x}))], \qquad (22)$$

$$= \mathbb{E}_{\mathbf{x} \sim p_{\text{data}}(\mathbf{x}), y \sim p_{\text{data}}(y | \mathbf{x})} \left[ \log \frac{p_{\text{data}}(y | \mathbf{x})}{p_{\theta}(y | \mathbf{x})} \right], \qquad (23)$$

$$= \mathbb{E}_{\mathbf{x} \sim p_{\text{data}}(\mathbf{x}), y \sim p_{\text{data}}(y | \mathbf{x})} [\log p_{\text{data}}(y | \mathbf{x})] - \mathbb{E}_{\mathbf{x} \sim p_{\text{data}}(\mathbf{x}), y \sim p_{\text{data}}(y | \mathbf{x})} [\log p_{\theta}(y | \mathbf{x})], \qquad (24)$$

$$= \text{constant} - \mathbb{E}_{\mathbf{x} \sim p_{\text{data}}(\mathbf{x})} \left[ \sum_{k=1}^{K} p_{\text{data}}(y = k | \mathbf{x}) \log p_{\theta}(y = k | \mathbf{x}) \right]. \qquad (25)$$

The constant here depends only on the ideal distribution and thus is not impacted by our choice of discriminative parameters $\theta$. Under the assumption that we have access to a dataset containing $n$ samples independently and identically distributed from $p_{\text{data}}(\mathbf{x}, y)$, we can estimate the expectation
using Monte Carlo. Noting the dataset $\mathcal{D} = \{(\mathbf{x}_i, y_i)\}_{i=1}^n$ which specifies the class to which each sample should belong, the target distribution can be approximated using a delta Dirac distribution for all $\mathbf{x}_i$: $p_{\text{data}}(y | \mathbf{x} = x_i) \approx 1[y = y_i]$. As we ignore the constant first term from Eq. (25), we get:

$$ \mathcal{L}(\theta) = -\mathbb{E}_{\mathbf{x} \sim p_{\text{data}}(\mathbf{x})} \left[ \sum_{k=1}^{K} p_{\theta}(y=k | \mathbf{x}) \log p_{\theta}(y=k | \mathbf{x}) \right], \quad (26) $$

$$ \approx -\frac{1}{|\mathcal{D}|} \sum_{\mathbf{x}_i, y_i \in \mathcal{D}} \sum_{k=1}^{K} 1[y_i = k] \log p_{\theta}(y = k | \mathbf{x} = \mathbf{x}_i), \quad (27) $$

$$ = -\frac{1}{|\mathcal{D}|} \sum_{\mathbf{x}_i, y_i \in \mathcal{D}} \log p_{\theta}(y = y_i | \mathbf{x} = \mathbf{x}_i). \quad (28) $$

This objective is called cross-entropy and is one of the most natural objective functions (sometimes called costs), in classification tasks and enjoys good properties: it is convex w.r.t. to the outputs of the model and ensures the minimisation of the KL divergence to the empirical estimate of $p_{\text{data}}$. Moreover, minimising the cross-entropy is equivalent to maximising the likelihood of the data distribution in classification.

Owing to its differentiability and its sole dependence on the output of the model, this objective can be optimised by gradient descent under the condition that the model's outputs are differentiable w.r.t. $\theta$. This means differentiating the cross-entropy and backpropagating the derivative throughout the complete model parameters such that the cross-entropy gets lowered. When the derivative of the objective is 0, the model found a local minimum.

Throughout this example, we see that the notion of objective function depending on the output of the model providing a convenient gradient is an efficient solution for training discriminative models. The cross-entropy naturally emerged from the distance comparison between our model and a target model, thus guiding the gradient descent. We are interested in finding such an objective function that would fit into the context of clustering for discriminative models.

## 3.3 Mutual information as a promising objective

For the classification task, we relied on the distance in the KL sense to a target distribution to train the model. This led us to the cross-entropy loss. For the clustering task with generative modelling, we relied on the likelihood of the data describing how our model fits the data. Therefore, we must focus on a key property that is desirable in the discriminative clustering case. That key property is that the final clustering should reflect insights on the data distribution. Indeed, clusters inform us about the data and conversely, knowing the data informs us about the cluster. This notion is conveyed through the dependence between two random variables. In our specific case: the clusters $y$ and the data $\mathbf{x}$ must be as dependent as possible.

To seek dependence between two random variables $\alpha$ and $\beta$, there exists a score that we can use as an objective function based on the KL divergence as well: Mutual Information (MI), defined as:

$$ \mathcal{I}(\alpha; \beta) = D_{\text{KL}}(p(\alpha, \beta) \| p(\alpha)p(\beta)). \quad (29) $$

Mutual information can be seen as a measure of how dependent two random variables are: the greater, the more dependent. In fact, following Theorem 1, a null mutual information value indicates that the clusters $y$ and the data $\mathbf{x}$ are independent, i.e. unrelated.

**Theorem 1 (Independence in mutual information)** Let $\alpha$ and $\beta$ be two random variables. Both variables are independent if and only if their mutual information is equal to 0.

**Remark 1** Theorem 1 is a direct consequence of $D_{\text{KL}}(p \| q) = 0 \iff p = q$.
Maximising mutual information to increase dependence between data and clusters seems a coherent objective. The upper bound of mutual information is the minimum of the entropies of y and x.

The definition from Eq. (29) cannot be optimised as such because the joint model $p_{\theta}(\mathbf{x}, y)$ and the data distribution $p_{\text{data}}(\mathbf{x})$ are unknown in the discriminative context. Fortunately, well-known properties of MI can invert the distributions on which the KL divergence is computed (Bridle et al., 1992; Krause et al., 2010) via the product rule:

$$ \mathcal{I}(\mathbf{x}; y) = D_{\text{KL}}(p_{\theta}(\mathbf{x}, y) \| p_{\text{data}}(\mathbf{x})p_{\theta}(y)), \quad (30) $$

$$ = \mathbb{E}_{\mathbf{x}, y \sim p_{\theta}(\mathbf{x}, y)} \left[ \log \frac{p_{\theta}(\mathbf{x}, y)}{p_{\text{data}}(\mathbf{x})p_{\theta}(y)} \right], \quad (31) $$

$$ = \mathbb{E}_{\mathbf{x} \sim p_{\text{data}}(\mathbf{x})} \left[ \mathbb{E}_{y \sim p_{\theta}(y|\mathbf{x})} \left[ \log \frac{p_{\theta}(y|\mathbf{x})p_{\text{data}}(\mathbf{x})}{p_{\text{data}}(\mathbf{x})p_{\theta}(y)} \right] \right]. \quad (32) $$

Then, we can simplify the factors on the data distribution inside the log and reidentify the KL divergence between a conditional distribution and a single marginal within an expectation:

$$ \mathcal{I}(\mathbf{x}; y) = \mathbb{E}_{\mathbf{x} \sim p_{\text{data}}(\mathbf{x})} [D_{\text{KL}}(p_{\theta}(y | \mathbf{x}) \| p_{\theta}(y))]. \quad (33) $$

Owing to the expectation on the data distribution, we can derive estimates of mutual information and its gradients w.r.t. $\theta$ using Monte Carlo. Thus, the usage of the product rule within the KL divergence to obtain an estimate is the key property to compute mutual information in discriminative modelling. This estimate, depends only on the output of the model $p_{\theta}(y | \mathbf{x})$ from which we can estimate the proportions of the clusters through marginalisation, recalling Eq. (18). Note that the cost function for clustering in Eq. (33) is interestingly similar to the KL we minimised in supervised learning from Eq. (22). In both equations, we sample on a data distribution and optimise the KL divergence between the model's clustering outputs and a target. In Eq. (22), this target to reach is the ideal classifier on the dataset, and we minimise the KL. In Eq. (33), the sampling distribution is the empirical approximation of the data distribution, the target is the cluster proportions, and we maximise the KL. Finally, we can maximise mutual information through gradient ascent.

However, we must remember that we do not maximise the true mutual information. Indeed, we previously showed with Eq. (18) that the proportions $p_{\theta}(y)$ are estimated with Monte Carlo. This means that the true proportions of the clusters are often not known in practice. Consequently, by rewriting this estimate as a proposal distribution $q(y)$ for the proportions of the cluster, we can unfold mutual information as follows (Poole et al., 2019):

$$ \mathcal{I}(\mathbf{x}; y) = \mathbb{E}_{\mathbf{x} \sim p_{\text{data}}(\mathbf{x})} \left[ D_{\text{KL}} \left( p_{\theta}(y | \mathbf{x}) \| p_{\theta}(y) \times \frac{q(y)}{q(y)} \right) \right], \quad (34) $$

$$ = \mathbb{E}_{\mathbf{x} \sim p_{\text{data}}(\mathbf{x})} [D_{\text{KL}}(p_{\theta}(y | \mathbf{x}) \| q(y))] - D_{\text{KL}}(p_{\theta}(y) \| q(y)), \quad (35) $$

$$ \leq \mathbb{E}_{\mathbf{x} \sim p_{\text{data}}(\mathbf{x})} [D_{\text{KL}}(p_{\theta}(y | \mathbf{x}) \| q(y))] . \quad (36) $$

This implies that we maximise only an upper bound of MI, even though the KL divergence between the estimated cluster proportions and the true proportions may be empirically negligible due to our unbiased estimate.

However, multiple works in the past and still today point to the inexpressivity of local maxima of MI (Bridle et al., 1992; Corduneanu and Jaakkola, 2002). In essence, inexpressivity means here a maximised mutual information with respect to the parameters of the model does not translate into good clustering. For example, Ver Steeg et al. (2014) showed with a mixture of uniform distributions how MI fails to properly separate the initial bins, and Corduneanu and Jaakkola (2002) empirically showed that the associated clusters to samples do not affect MI as long as the clusters are balanced. We can also give the example of Ohl et al. (2022) in Figure 3 where a nonparametric model is trained using mutual information. This nonparametric model takes the form:

$$ p_{\theta}(y = k | \mathbf{x} = \mathbf{x}_i) = \tau_{ki}. \quad (37) $$
<figure><img src="image_6.png" /></figure>

```python
from sklearn import datasets
X, _ = datasets.make_blobsto(centers=3, cluster_std=0.5, random_state=0)
# Take a nonparametric model and fit it using MI as objective
from gemclus.nonparametric import CategoricalModel
mi_model = CategoricalModel(n clusters=3, gemini="mi")
y_pred = mi_model.fitPredict(X)
# Same nonparametric model, optimise a distance-regularised MI
gemini_model = CategoricalModel(gemini="mmd_ova", random_state=0,
learning_rate=1e-2)
y_pred_regularised = gemini_model.fitPredict(X)
```

(d) Snippet of code to reproduce the example

Figure 3: Clustering of mixture of 3 isotropic Gaussian distributions by a nonparametric model. When the cluster memberships are directly optimised by mutual information, the clusters do not correspond to any of the initial Gaussian distributions because the cluster memberships are not derived from the position of the samples. In constrast, MI regularised by maximum mean discrepancy can optimise correctly the nonparametric model. This example is taken from Ohl et al. (2022) and can be reproduced using their package GemClus (Ohl et al., 2023b).

In other words, a cluster membership for the cluster k to the i-th sample is directly assigned. The “nonparametric” model has N × K parameters: $\theta = \{\tau_{ki}\}_{i=1,k=1}^{n,K}$ that are constrained such that $\sum_{k=1}^{K} \tau_{ki} = 1$ and $\tau_{ik}$ is positive. These cluster memberships $\tau_{ik}$ do not depend on the value of the sample $\mathbf{x}_i$ and only match $\mathbf{x}_i$ by indexing. Consequently, the nonparametric model creates only a partition of the dataset, but it cannot generalise to unseen samples.

Due to the absence of relationship to the values of the samples in the model parameters, their optimisation with regard to mutual information produces clusters that plainly create a balanced partition of the dataset, regardless of its shape (Ohl et al., 2023a, Corollary 1). This limitation of MI justifies the usage of regularisations to constrain sufficiently the clustering models. We will see that these regularisations were part of the discriminative clustering framework from the very start in Section 5.1. To the best of our knowledge, few works did question the quality of MI as an objective in itself. Among them, Ohl et al. (2022) proposed to replace the Kullback-Leibler divergence $D_{KL}$ by any other distance $D$:

$$ \mathcal{I}_D(\mathbf{x}; y) = \mathbb{E}_{y \sim p_{\theta}(y)} [D(p_{\theta}(\mathbf{x} | y) || p_{\text{data}}(\mathbf{x}))], \quad (38) $$

preferably using geometry-based distances like the Wasserstein distance (Peyré and Cuturi, 2019) or the maximum mean discrepancy (Gretton et al., 2012). An example of non-geometry-based distance is the $\chi^2$ divergence, which was explored by Sugiyama et al. (2011). This objective, named *generalised mutual information* (GEMINI), tackles the inexpressivity of local maxima by enforcing the hypothesis that samples that are close to each other should remain in the same cluster. The GEMINI objective preserves the key property of independence and null value of the initial MI.
# 4 Other clustering models

Between generative and discriminative models, there exist other clustering models. We discuss some of these objectives and compare their (dis)advantages with mutual information.

## 4.1 K-means

K-means is the most standard clustering algorithm (Likas et al., 2003). The algorithm consists of two alternating steps. Starting from a set of K centroids: $\{\mu_k\}_{k=1}^K$, all samples in the dataset are assigned to the cluster $C_k$ matching their closest centroid $\mu_k$. Then each centroid is recomputed as the mean of all samples assigned to the corresponding cluster. Overall, the K-means algorithm minimises the following objective (Lloyd, 1982; Elkan, 2003), although there are no guarantees of reaching the global optimum:

$$ \mu_{1...K}^* \in \arg \min_{\mu_{1...K}} \sum_{k=1}^{K} \sum_{\mathbf{x} \in C_k} \|\mathbf{x} - \mu_k\|_2^2. \quad (39) $$

The simplicity of K-means makes it a standard basis for clustering algorithms. However, its decision boundaries are linear because they appear for all samples that lay equidistantly between two close means. Consequently, this does not allow complex cluster shapes when the Euclidean distance is used between data samples. An alternative called kernel K-means (Dhillon et al., 2004) can be used to alleviate more complex boundaries. Instead of drawing a boundary in the Euclidean space, it is drawn in a reproducing kernel Hilbert space $\mathcal{H}$ endowed with projection $\varphi$ (Hofmann et al., 2008). The new objective is described:

$$ \mathcal{L}(\{\mu_k\}_{k=1}^K) = \sum_{k=1}^{K} \sum_{\mathbf{x} \in C_k} \|\varphi(\mathbf{x}) - \mu_k\|_{\mathcal{H}}^2. \quad (40) $$

Beyond its wide applicability, K-means offers multiple advantages. First, the definition of fixed centroids also allows the clustering of unseen samples, i.e. samples that were not part of the training dataset. Second of all, this algorithm is fast as it scales linearly to the number of samples $n$ and the number of input features $d$. However, K-means has several drawbacks: it is very sensitive to outliers, i.e. samples far away from the main modes of the data, and it displays high sensitivity to the initialisation. Moreover, the clustering model conveyed by K-means is a mixture of Dirac models, which does not provide a fine-grained quantification of the cluster conditional probability. This is often referred to as *hard clustering*.

If we disregard the hard membership assignments, K-means can be seen as a generative clustering model as it is similar to a mixture of isotropic Gaussian distributions. Indeed, both algorithms produce linear decision boundaries. The K-means score can also be seen and used as an objective function for discriminative clustering, where the model is non-parametric as in Eq.37. Indeed, Ohl et al. (2024b) showed that by using the equality:

$$ \sum_{\mathbf{x} \in C_k} \|\varphi(\mathbf{x}) - \underbrace{\frac{1}{|C_k|} \sum_{\mathbf{y} \in C_k} \varphi(\mathbf{y})}_{\mu_k} \|_{\mathcal{H}}^2 = \frac{1}{2|C_k|} \sum_{\mathbf{x}, \mathbf{y} \in C_k} \|\varphi(\mathbf{x}) - \varphi(\mathbf{y})\|_{\mathcal{H}}^2. \quad (41) $$

and the kernel trick with a kernel function $\kappa$, the kernel K-means objective to minimise becomes, constants aside:

$$ \mathcal{L}(\{C_k\}_{k=1}^K) = - \sum_{k=1} \frac{\sum_{\mathbf{x}, \mathbf{y} \in C_k} \kappa(\mathbf{x}, \mathbf{y})}{|C_k|}. \quad (42) $$

This objective is now a function of the partition, i.e. the clustering, instead of parametric centroids $\mu_k$ that are iteratively updated. An equivalent formulation using can be found in França et al. (2020).
**Remark 2** The Equation (40) is often referred to as the average intra-cluster similarity although it uses distances (Soler et al., 2013), the objective from Eq. (42) could be described as the average cluster kernel, which is different from distances or similarities.

## 4.2 Spectral clustering

Related to kernel K-means, spectral clustering is a multi-step algorithm (von Luxburg, 2007) in which an alternative representation of the data is derived and used as input for a K-means algorithm. At the start of the algorithm, an affinity matrix is computed between all samples. The choice of the notion of affinity is arbitrary: $\epsilon$-neighbourhood, $n$ nearest neighbours, or a kernel like radial basis function (RBF), polynomial. This affinity matrix allows us to define a Laplacian matrix that views the complete dataset as a graph. The nature of the Laplacian can vary, e.g. being normalised or symmetrised (Shi and Malik, 2000; Ng et al., 2001). Then, an alternative representation of the data emerges from the spectrum of this Laplacian matrix. Specifically, the first $K$ eigenvectors of the Laplacian matrix are used as new features. Consequently, each sample is associated with a vector of dimension $K$ where its $k$-th component is its weight for the $k$-th eigenvector.

While spectral clustering is efficient when cluster structures are non-convex, its strong requirement is the construction of a graph between all samples which enforces the fusion of modalities when several modalities are present. Moreover, the identification of the spectrum of the Laplacian prevents the model from generalising to unseen samples. Once again, due to the final K-means algorithm, the spectral clustering can be seen as a delta Dirac distribution which only delivers hard membership to clusters for all samples.

# 5 Thrive of mutual information: from clustering to representation learning

Mutual information is an elegant objective function that can train through gradient ascent various differentiable models as we showed in Section 3.3. We trace here the multiple usages it has met for the past 30 years in the context of clustering.

## 5.1 Early usage of mutual information for clustering

To the best of our knowledge, MI was first used as an objective for learning discriminative clustering models by Bridle et al. (1992). They described MI as an objective that maximises the *fairness* of a model, i.e. the entropy of the cluster proportions, and aim to maximise *firmness*, i.e. minimising the conditional entropy. By rewriting mutual information, we have:

$$ \mathcal{I}(\mathbf{x}; y) = \underbrace{\mathbb{H}(y | \mathbf{x})}_{\text{Firmness}} - \underbrace{\mathbb{H}(y)}_{\text{Fairness}}. \qquad (43) $$

Thus, a good clustering model is fair but firm.

Two decades later, Krause et al. (2010) initiated again the work on discriminative clustering models with mutual information. Similarly to Bridle et al. (1992), they first propose to train a logistic regression but specifically add a $\ell_2$ constraint to alleviate the constraint on the firmness of the classifier model. Indeed, in line with the criticisms from Section 3.3, a model that is too firm, i.e. has very low conditional entropy, produces overconfident clustering probabilities, and so should the $\ell_2$ regularisation avoid an excessive firmness. Among the multiple proposals of this framework called regularised mutual information (RIM), Krause et al. (2010) also propose to learn a regularised logistic model on a positive semi-definite kernel matrix of some dataset instead of the sample features to get a non-linear decision boundary.
These two approaches decouple the model $p_{\theta}(y | \mathbf{x})$ that makes assumptions about the shape of the decision boundary from the objective. Such methods are proposed and implemented in the GemClus software (Ohl et al., 2023b).

Another interesting approach, named the information bottleneck, focuses on the notion of information relevance. Indeed: “The problem of extracting a relevant summary of data, a compressed description that captures only the relevant or meaningful information, is not well-posed without a suitable definition of relevance” (Tishby et al., 2000).

The information bottleneck framework is derived from signal processing theory and is related to rate-distortion theory (Tishby et al., 2000). As such, it considers an input variable $Z$, that must be quantised into a lower-dimensional or discrete variable called code $\tilde{Z}$. However, this quantisation must be done such that another output variable $\tilde{Z}$, can be recovered from the code. The final model is written:

$$p^*(\tilde{Z} | Z) \in \arg\min_{p(\tilde{Z}|Z)} \mathcal{I}(\tilde{Z}; Z) - \beta \mathcal{I}(\tilde{Z}; \tilde{Z}). \quad (44)$$

The hyperparameter $\beta$ controls the trade-off between a highly detailed compression ($\beta = \infty$) and an independent compression ($\beta = 0$) of $Z$ into $\tilde{Z}$ (Tishby et al., 2000). The distribution we seek to optimise $p(\tilde{Z} | Z)$ can be parametric or nonparametric.

Initially, the information bottleneck was designed in a supervised context: Tishby et al. (2000) explicitly assumes that they have access to some distribution $p(Z, \tilde{Z})$. In this context, we can interpret the input variable $Z$ as the data $\mathbf{x}$ and the output variable $\tilde{Z}$ as the targets, i.e. observed labels, $l$. Only the quantised variable $\tilde{Z}$ remains to be defined. We can define this variable as the cluster membership that we seek to enhance classification. In other words: we seek to compress the data into several clusters that we then use to alleviate the classification task. The corresponding objective is:

$$\mathcal{L} = \mathcal{I}(\mathbf{x}; y) - \beta \mathcal{I}(l; y), \quad (45)$$

For example, Slonim and Tishby (2000) used this objective to discover word clusters using documents as inputs $\mathbf{x}$, words as classes $l$ and word clusters $y$ to compress the documents. Similarly, Dhillon et al. (2003) proposed using word clusters to improve document classification. In their case, the targets $l$ are labels that should be assigned to documents instead of words. However, they framed the information bottleneck differently. If we seek more clusters than classes, the targets can then seem as more compressed representation than the clusters. Dhillon et al. (2003) permute the role of classes and clusters in the information bottleneck and optimise:

$$\mathcal{L} = \mathcal{I}(l; \mathbf{x}) - \mathcal{I}(l; y). \quad (46)$$

Thus, the information bottleneck compresses the words into clusters $y$ that suffice to guess the class of documents. Notice that in this context, the hyperparameter $\beta$ was set to 1. Slonim et al. (2005) adapted as well this framework for doing only clustering and without the goal of recovering a target contained in the dataset. To that end, they replaced the first mutual information by the expectation of the cluster similarity measure $\mathbf{sim}$. Taking a random subset of $r$ samples per cluster to evaluate the similarity, their objective is:

$$\mathcal{L} = \mathbb{E}_{y \sim p_{\theta}(y)} \left[ \mathbb{E}_{\mathbf{x}_{1 \dots r} \sim \prod_{i=1}^{r} p_{\theta}(\mathbf{x}_{i} | y)} \left[ \mathbf{sim}(\mathbf{x}_{1 \dots r}) \right] \right] - \beta \mathcal{I}(\mathbf{x}; y). \quad (47)$$

It is interesting to see that in this specific example, one of the mutual information objectives was replaced to take into account distances between samples of clusters to regulate mutual information between the clusters and the data. This joins the observations of Ohl et al. (2022) and their introduction of distances to regularise mutual information itself. This introduction of a notion of similarity will play a key role in entangling clustering hypotheses in mutual information, as we will see in Section 5.3. In contrast to the work of Bridle et al. (1992) and Krause et al. (2010), the early works using the information bottleneck framework used nonparametric models (Dhillon et al., 2003; Slonim et al., 2005), which we defined in Eq. (37).
## 5.2 Towards deeper networks

Two years after the RIM model, Krizhevsky et al. (2012) introduced the AlexNet model, an example of strong modern deep learning success. Inspired from this success, depth also affected the neural networks involved in clustering tasks. For instance, Xie et al. (2016) proposed to use autoencoder architectures combined with K-means clustering in the compressed space to benefit from nonlinear architectures. To the best of our knowledge, the first deep clustering model involving mutual information was proposed by Hu et al. (2017) who replaced the $l_2$ constraint of Krause et al. (2010) by a virtual adversarial constraint (Miyato et al., 2018). The key idea is to add small perturbations to the input sample and ensure that the assigned cluster is consistent with the clustering of the initial sample:

$$ \theta^* \in \arg \max_{\theta} \mathcal{I}(\mathbf{x}; y) \quad \text{s.t.} \quad D_{\text{KL}}(p_{\theta}(y | \mathbf{x}) \| p_{\theta}(y | \mathbf{x} + \boldsymbol{\epsilon})) \approx 0, \qquad (48) $$

where $\epsilon$ is a very small noise. Augmentations such as random cropping, scaling, or rotations were also used to perturb the initial sample. The key idea is that these perturbations provide invariances in clustering (Ji et al., 2019). This can also be seen as designing a specific neighbourhood in which we can sample the perturbation $\epsilon$.

Deep clustering methods progressively used deeper and deeper networks, e.g. ResNets (He et al., 2016). Moreover, they sought to improve architectures by providing regularisations through auxiliary loss terms (Ren et al., 2024), e.g. auxiliary clustering heads (Ji et al., 2019). As an example of regularisation impact: maximising MI with $l_2$ constraint can be equivalent to a soft and regularised K-Means in a feature space (Jabi et al., 2019). This drift towards deep networks and the introduction of data augmentation led to the emergence of contrastive learning as a core basis for deep discriminative clustering methods. We now detail its relationship with mutual information.

## 5.3 From discrete to continuous output variables: contrastive learning and infoMax

### 5.3.1 Mutual information lower bounds

With the introduction of deep neural networks in clustering, the field of deep clustering rapidly gave way to the development of discriminative models that predict a continuous variable $\mathbf{z} \in \mathcal{Z}$ instead of a simple cluster assignment $y \in [K]$. These models are no longer designed for clustering, but are compatible with clustering in the space of learnt representations. For example, a simple continuous distribution based on a discriminative network could be:

$$ p_{\theta}(\mathbf{z} | \mathbf{x}) = \mathcal{N}(\mathbf{z} | \psi_{\theta}(\mathbf{x}), \sigma^2 \mathbf{I}). \qquad (49) $$

However, we cannot optimise representation learning model parameters directly using mutual information. In Section 3, we benefited from the discrete nature of the target $y$ that yielded a finite sum to estimate mutual information. Now, our target variable is a continuous representation $\mathbf{z}$, which implies that we must compute an intractable integral to get $p_{\theta}(\mathbf{z})$. As a workaround, lower bounds of the mutual information between $\mathbf{x}$ and $\mathbf{z}$ are used as objective functions to learn such models.

Several lower bounds have been designed, as named by Poole et al. (2019): MINE (Belghazi et al., 2018), NCE (Van den Oord et al., 2018), BA (Barber and Agakov, 2003). We offer some insight on their derivation in the next paragraphs. For more in-depth details regarding the derivations, we refer to Poole et al. (2019).

To get a lower bound, let us express mutual information using $p(\mathbf{x} | \mathbf{z})$. Since we do not know its value by our discriminative assumptions, we will try to approximate this distribution using a proposal
distribution $q(\mathbf{x} | \mathbf{z})$. This allows us to rewrite MI (Barber and Agakov, 2003) as:

$$ \mathcal{I}(\mathbf{x}; \mathbf{z}) = \mathbb{E}_{p(\mathbf{z})} \left[ D_{\text{KL}} \left( p(\mathbf{x} | \mathbf{z}) \frac{q(\mathbf{x} | \mathbf{z})}{q(\mathbf{x} | \mathbf{z})} \| p(\mathbf{x}) \right) \right], \quad (50) $$

$$ = \mathbb{E}_{p(\mathbf{x}, \mathbf{z})} [\log q(\mathbf{x} | \mathbf{z})] + \mathbb{H}(\mathbf{x}) + \mathbb{E}_{p(\mathbf{z})} [D_{\text{KL}}(p(\mathbf{x} | \mathbf{z}) \| q(\mathbf{x} | \mathbf{z}))], \quad (51) $$

$$ \geq \mathbb{E}_{p(\mathbf{x}, \mathbf{z})} [\log q(\mathbf{x} | \mathbf{z})] + \mathbb{H}(\mathbf{x}). \quad (52) $$

In order to connect this expression to other lower bounds, Poole et al. (2019) suggest to take $q$ from the energy-based variational family:

$$ q(\mathbf{x} | \mathbf{z}) = \frac{p_{\text{data}}(\mathbf{x})}{Z(\mathbf{z})} e^{E(\mathbf{x}, \mathbf{z})}, \quad (53) $$

where $Z(\mathbf{z}) = \mathbb{E}_{p_{\text{data}}(\mathbf{x})} [e^{E(\mathbf{x}, \mathbf{z})}]$.

Integrating this proposal distribution in our lower bound cancels the entropy term on $\mathbf{x}$, and we obtain:

$$ \mathcal{I}(\mathbf{x}; \mathbf{z}) \geq \mathbb{E}_{p(\mathbf{x}, \mathbf{z})} \left[ \log \frac{e^{E(\mathbf{x}, \mathbf{z})}}{Z(\mathbf{z})} \right] \quad (54) $$

Evaluating this lower bound requires the value of the denominator $Z(\mathbf{z})$. The suggestion of Poole et al. (2019) is to directly use Monte Carlo:

$$ Z(\mathbf{z}) \approx \frac{1}{n} \sum_{i=1}^{n} e^{E(x_i, \mathbf{z})}. \quad (55) $$

Using such an estimate requires that we have access to a batch of $n$ i.i.d. samples $\mathbf{x}_i$. This has been our main assumption so far in discriminative clustering. We can here benefit from the independence assumption to further enhance our estimator of the mutual information lower bound. Indeed, mutual information is invariant to the addition of a variable $\mathbf{v}$ independent of $\mathbf{x}$ and $\mathbf{z}$, noted: $\mathcal{I}(\mathbf{x}, \mathbf{v}; \mathbf{z}) = \mathcal{I}(\mathbf{x}; \mathbf{z})$. Consequently, looking at each sample as individual independent random variables and detailing the probability distribution over all samples yields the following:

$$ \mathcal{I}(\mathbf{x}_1; \mathbf{z}) = \mathcal{I}(\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_n; \mathbf{z}). \quad (56) $$

We now assume that we have i.i.d. pairs of variables $(\mathbf{x}_i, \mathbf{z}_i)$. Owing to this assumption, we can estimate mutual information by summing the mutual informations between each representation $\mathbf{z}_i$ and each individual samples $\mathbf{x}_i$. Each term of this sum has exactly the same value:

$$ \mathcal{I}(\mathbf{x}_1, \dots, \mathbf{x}_n; \mathbf{z}) = \frac{1}{n} \sum_{i=1}^{n} \mathcal{I}(\mathbf{x}_i; \mathbf{z}_i). \quad (57) $$

We can wrap up the mutual information in an expectation over the distribution of all remaining samples. Thus:

$$ \mathcal{I}(\mathbf{x}_1; \mathbf{z}) = \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{\Pi_{j \neq i}^{n} p_{\text{data}}(\mathbf{x}_j)} [\mathcal{I}(\mathbf{x}_i; \mathbf{z}_i)]. \quad (58) $$

Each expectation can be seen as the tool to get our Monte Carlo samples for estimating $Z(\mathbf{z})$ from Eq. (55). We then incorporate the lower bounds from Eq. (54) for each mutual information term:

$$ \mathcal{I}(\mathbf{x}; \mathbf{z}) \geq \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{p_{\text{data}}(\mathbf{x}_1, \dots, \mathbf{x}_n) p_{\theta}(\mathbf{z} | \mathbf{x}_i)} \left[ \log \frac{e^{E(\mathbf{x}_i, \mathbf{z}_i)}}{\sum_{j=1}^{n} e^{E(\mathbf{x}_j, \mathbf{z}_i)}} \right] + \log n. \quad (59) $$

The proof that this is an actual lower bound can be found in Poole et al. (2019). Note that this demonstration is also valid for a discrete variable $y$ instead of $\mathbf{z}$.
Notice that the constant log n, which comes from our Monte Carlo estimate of the denominator, introduces a bias in the lower bound. In this final expression, the samples $\mathbf{x}_1, \dots, n$ that we use to estimate our initial denominator $Z(\mathbf{z})$ are the same ones from the outer expectation. This lower bound as the Info NCE and can be linked to the temperature-scaled cross-entropy of contrastive learning (NT-XENT, Chen et al., 2020).

There exist an optimal distribution for our variational proposal. It is the energy as the log of the output of the model:

$$E(\mathbf{x}, \mathbf{z}) = \log p(\mathbf{z} | \mathbf{x}). \qquad (60)$$

Consequently, the proposal distribution $q(\mathbf{x} | \mathbf{z})$ becomes equal to $p_\theta(\mathbf{x} | \mathbf{z})$. If we insert this proposal directly into the lower bound from Eq (59), we finally have an objective for training our parameters $\theta$ with a continuous output for the model:

$$\mathcal{I}(\mathbf{x}; \mathbf{z}) \geq \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{p_{\text{data}}(\mathbf{x}_1, \dots, \mathbf{x}_n) p_\theta(\mathbf{z} | \mathbf{x}_i)} \left[ \log \frac{p_\theta(\mathbf{z}_i | \mathbf{x}_i)}{\sum_{j=1}^{n} p_\theta(\mathbf{z}_i | \mathbf{x}_j)} \right] + \log n. \qquad (61)$$

In this equation, our estimate of the denominator $Z(\mathbf{z})$ directly corresponds to the estimate of $p(\mathbf{z})$. Although, Eq. (61) seems like a compelling objective to train representation models, i.e. $p_\theta(\mathbf{z} | \mathbf{x})$, it would not be reasonable to directly use it because the estimate of $p(\mathbf{z})$ is precisely the limitation we sought to avoid. We initially motivated at the beginning of this section that the continuous, and potentially high-dimension nature of $\mathbf{z}$ is responsible of the intractability of $p(\mathbf{z})$.

Now that we have a lower bound on MI that we can potentially use in high-dimensional spaces, we need to adapt our model for clustering instead of predicting a continuous representation. An easy solution would be to use a second clustering algorithm to cluster the samples in the space $\mathcal{Z}$. Although this is a valid approach, this implies our model $p_\theta(\mathbf{z} | \mathbf{x})$ is not any longer the one to achieve clustering. To maintain the clustering nature of our model, we need to consider differently the meaning of the continuous representation $\mathbf{z}$. Instead of considering $\mathbf{z}$ as an output from the model we want to learn, we will use it as a joint property of $\mathbf{x}$ using augmentations: we turn to contrastive learning.

### 5.3.2 Contrastive learning

Contrastive learning is an integral part of representation learning through the lens of self-supervised learning. Representation learning consists in finding high-level features $\mathbf{z}_i$ extracted from the data $\mathbf{x}_i$ to perform a downstream task, e.g. clustering or classification. However, the nature of the model is different with regards to mutual information in Eq. (59).

The key idea of contrastive learning is to perform a set of random augmentations on a sample $\mathbf{x}_i$, then maximise the similarity between the representation associated with this sample and its augmentation, while decreasing the similarity with any other sample. This choice implies that we no longer maximise the mutual information between the data $\mathbf{x}$ and the representation variable $\mathbf{z}$, but a variable corresponding to the augmentation of the data: Aug($\mathbf{x}$) Do et al. (2021). This also means that the conditional distribution $p(\text{Aug}(\mathbf{x}) | \mathbf{x})$ is unknown. Nevertheless, we assume that we can sample augmentations of $\mathbf{x}$ easily. We can rewrite Eq. (59) in the context of contrastive clustering as:

$$\mathcal{I}(\mathbf{x}; \text{Aug}(\mathbf{x})) \geq \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{p(\mathbf{x}_1, \dots, \mathbf{x}_n) p(\text{Aug}(\mathbf{x}) | \mathbf{x}_i)} \left[ \log \frac{e^{E_{\text{constrastive}}(\mathbf{x}_i, \text{Aug}(\mathbf{x}_i))}}{\sum_{j=1}^{n} e^{E_{\text{constrastive}}(\mathbf{x}_i, \text{Aug}(\mathbf{x}_j))}} \right] + \log n. \qquad (62)$$

In this context, the distributions on which we perform the expectations are not parameterised any longer by $\theta$. In fact, mutual information between $\mathbf{x}$ and Aug($\mathbf{x}$) is constant because we fixed an augmentation strategy. The parameters of our neural networks are now *hidden in the critic* function $E_{\text{constrastive}}$, which must favour high similarities between samples and their respective augmentations:

$$E_{\text{constrastive}}(\mathbf{x}_i, \text{Aug}(\mathbf{x}_j)) = \text{sim}(\psi_\theta(\mathbf{x}_i), \psi_\theta(\text{Aug}(\mathbf{x}_j))). \qquad (63)$$
Our model does not aim any longer at maximising mutual information $\mathcal{I}(\mathbf{x}; \text{Aug}(\mathbf{x}))$, which is a constant, but try to approximate a distribution. Indeed, in our initial lower bound from Eq. (52), the optimal solution is to get $q(\mathbf{x} | \mathbf{z})$ equal to $p(\mathbf{x} | \mathbf{x})$, in which case the first term becomes the entropy of $\mathbf{x}$ given $\mathbf{z}$ and the sum recovers the exact MI. That is why contrastive learning is about learning the distribution $p(\mathbf{x} | \text{aug}(\mathbf{x}))$ using the approximate $q(\mathbf{x} | \text{aug}(\mathbf{x}))$.

Contrastive learning provides a convenient framework that takes advantage of the key idea that the neighbourhood of a sample should remain in the neighbourhood of the representation of this sample. The nature of the neighbourhood is dependent on the choices of data augmentation. Although it is not related to clustering, this approach indirectly views each sample in an individual cluster because we maximise MI between two variations of $\mathbf{x}$. This means that the only elements that can go in the same cluster are the augmentations of the samples and are called positive pairs, while all the others, including their augmentations, are called negative pairs and must be excluded. However, such setup completely loses the end goal of clustering that is to put samples into K categories. Therefore, additional tricks are required to bring back the continuous representations to a clustering model. We give now some examples of such tricks. Note that we purposefully omit some details for the sake of clarity, especially regarding how augmentations are handled through batches during learning and regularisations.

In the spirit of the SIMCLR model (Chen et al., 2020), Do et al. (2021) propose to decompose the model in two different parts. One is a backbone $\psi$ learning common representations for the second part that comprises two different projection heads: one for clustering $\chi$, i.e. a softmax-ended function, and $\varphi$ a projection to the continuous domain. Note that we omit the parameters for brevity. The model thus comprises two functions, the clustering function:

$$ \chi \circ \psi : \mathcal{X} \quad \mapsto \quad \Delta^{K-1}, \\ \mathbf{x}_i \quad \mapsto \quad \chi \circ \psi(\mathbf{x}_i) = y_i. \qquad (64) $$

and the representation function:

$$ \varphi \circ \psi : \mathcal{X} \quad \mapsto \quad \mathcal{Z}, \\ \mathbf{x}_i \quad \mapsto \quad \varphi \circ \psi(\mathbf{x}_i) = z_i. \qquad (65) $$

Then, by summing two mutual informations with different critics $E_1$ and $E_2$, one for the representation and one for the clustering, Do et al. (2021) achieve a model with features presenting high intra-cluster variability and low inter-group similarity:

$$ \mathcal{L} = \underbrace{\mathcal{I}_{E_1}(\mathbf{x}; \text{Aug}(\mathbf{x}))}_{E_1(\cdot, \cdot)=\text{sim}(\varphi \circ \psi(\cdot), \varphi \circ \psi(\cdot))} + \underbrace{\mathcal{I}_{E_2}(\mathbf{x}; \text{Aug}(\mathbf{x}))}_{E_2(\cdot, \cdot)=\text{sim}(\chi \circ \psi(\cdot), \chi \circ \psi(\cdot))}. \qquad (66) $$

Another line of work proposes instead to construct a critic function $E$ that evaluates the similarity between the distribution of the clusters rather than the representations. We describe the notations in Figure 4. Let us note the conditional distribution as a vector:

$$ \mathbf{h}_k^\top = [p_\theta(y = k | \mathbf{x}_1), \dots, p_\theta(y = k | \mathbf{x}_i), \dots, p_\theta(y = k | \mathbf{x}_n)] \in \mathbb{R}^n. \qquad (67) $$

Using this formulation, Huang et al. (2020) proposed to maximise $\mathcal{I}(\mathbf{h}_1, \dots, \mathbf{h}_K)$ where $\bar{\mathbf{h}}$ is the cluster distribution obtained after applying random augmentations on the samples. Li et al. (2021) extended this idea by adding a second mutual information between the representations, as we explained for Do et al. (2021).

The example of Huang et al. (2020) offers a different perspective on the usage of MI. Instead of constraining the neural network output with a softmax to obtain the probabilities of a discrete variable $y$, we can directly seek to optimise MI between samples and a set of $K$ cluster centroids $\mu_k$. We assume that the centroids are i.i.d. and can therefore chain two times in a row the multi-sample definition of MI from Eq. (57):

$$ \mathcal{I}(\mathbf{x}_1, \dots, \mathbf{x}_n; \mu_1, \dots, \mu_K) = \frac{1}{K} \sum_{k=1}^{K} \mathbb{E}_{\Pi_{i \neq k}^{K}} p(\mu_i) \left[ \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{\Pi_{j \neq i}^{n}} p(\mathbf{x}_j) [\mathcal{I}(\mathbf{x}_i; \mu_k)] \right]. \qquad (68) $$
<figure><img src="image_7.png" /><figcaption>Figure 4: Graphical explanation of notations used for deep clustering models.</figcaption></figure>

In practice, the centroids $\mu_k$ are sampled them Dirac distributions whose locations are learnt. We then have the freedom of choosing either the proposal distribution $q(\mu | \mathbf{x})$, in which case the normalisation constant must be estimated using the centroids $\mu_k$, or the proposal $q(\mathbf{x} | \mu)$, in which case we estimate the normalisation constant using the batch of samples $\mathbf{x}_i$. Let us choose the former. We obtain a new lower bound on MI that seeks to connect a batch of samples to a batch of centroids:

$$ \mathcal{I}(\mathbf{x}_{1,...,n}; \boldsymbol{\mu}_{1,...,K}) \geq \frac{1}{K} \sum_{k=1}^{K} \mathbb{E}_{\Pi_{l \neq k}^{K} p(\boldsymbol{\mu}_{l})} \left[ \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{p(\boldsymbol{\mu}_{k}|\mathbf{x}_{i})p(\mathbf{x}_{1},...,\mathbf{x}_{n})} \left[ \log \frac{e^{E(\mathbf{x}_{i},\boldsymbol{\mu}_{k})}}{\sum_{l=1}^{K} e^{E(\mathbf{x}_{i},\boldsymbol{\mu}_{l})}} \right] \right]. \quad (69) $$

This new lower bound on MI corresponds to the objective of representation models using swapping assignments (Caron et al., 2020). To show this link, let us consider now that our samples $\mathbf{x}_i$ are in fact $n$ different augmentations of the same original sample, noted $\mathbf{x}_i | \tilde{\mathbf{x}} \equiv \text{Aug}^{(i)}(\tilde{\mathbf{x}})$. This addition holds with our statistical assumptions because the samples $\mathbf{x}_i$ remain i.i.d. given $\tilde{\mathbf{x}}$. We can then rewrite the lower bound on MI by adding the condition on $\tilde{\mathbf{x}}$ and get:

$$ \mathcal{I}(\mathbf{x}_{1,...,n} | \tilde{\mathbf{x}}; \boldsymbol{\mu}_{1,...,K}) \geq \frac{1}{K} \sum_{k=1}^{K} \mathbb{E}_{\Pi_{l \neq k}^{K} p(\boldsymbol{\mu}_{l})} \left[ \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{p(\boldsymbol{\mu}_{k}|\mathbf{x}_{i},\tilde{\mathbf{x}})p(\mathbf{x}_{1},...,\mathbf{x}_{n}|\tilde{\mathbf{x}})} \left[ \log \frac{e^{E(\mathbf{x}_{i},\boldsymbol{\mu}_{k})}}{\sum_{l=1}^{K} e^{E(\mathbf{x}_{i},\boldsymbol{\mu}_{l})}} \right] \right]. \quad (70) $$

Owing to this additional condition on $\tilde{\mathbf{x}}$ and the independence of all samples $\mathbf{x}_j$ to $\mathbf{x}_i$ and $\mu_k$, we can use the product rule of probabilities to change the distributions on which the innermost expectation is done. Thus:

$$ p(\boldsymbol{\mu}_{k} | \mathbf{x}_{i}, \tilde{\mathbf{x}}) p(\mathbf{x}_{1}, \dots, \mathbf{x}_{n} | \tilde{\mathbf{x}}) = p(\boldsymbol{\mu}_{k}, \mathbf{x}_{1}, \dots, \mathbf{x}_{n} | \tilde{\mathbf{x}}) \quad (71) $$

$$ = p(\boldsymbol{\mu}_{k}, \mathbf{x}_{1}, \dots, \mathbf{x}_{i-1}, \mathbf{x}_{i+1}, \dots, \mathbf{x}_{n} | \tilde{\mathbf{x}}, \mathbf{x}_{i}) p(\mathbf{x}_{i} | \tilde{\mathbf{x}}), \quad (72) $$

(73)

Finally, this rewritten distribution gives us a generalised swapping representation model for $n$ augmentations that we seek to map to $K$ centroids:

$$ \mathcal{I}(\mathbf{x}_{1,...,n} | \tilde{\mathbf{x}}; \boldsymbol{\mu}_{1,...,K}) \geq \frac{1}{K} \sum_{k=1}^{K} \mathbb{E}_{\Pi_{l \neq k}^{K} p(\boldsymbol{\mu}_{l})} \left[ \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{p(\mathbf{x}_{i}|\tilde{\mathbf{x}})p(\boldsymbol{\mu}_{k},\mathbf{x}_{1},...,\mathbf{x}_{i-1},\mathbf{x}_{i+1},...,\mathbf{x}_{n}|\tilde{\mathbf{x}},\mathbf{x}_{i})} \left[ \log \frac{e^{E(\mathbf{x}_{i},\boldsymbol{\mu}_{k})}}{\sum_{l=1}^{K} e^{E(\mathbf{x}_{i},\boldsymbol{\mu}_{l})}} \right] \right]. \quad (74) $$

The example of Caron et al. (2020) corresponds to only two augmentations ($n = 2$). In their work, the distribution $p(\boldsymbol{\mu}_{k}, \mathbf{x}_{j} | \tilde{\mathbf{x}}, \mathbf{x}_{i})$, $j \neq i \in \{1, 2\}$ is estimated with a regularised optimal transport
problem on a batch of B samples $\tilde{x}$, and the energy function E is the temperature-scaled similarity between the centroid $\mu_k$ and the representation of the augmented sample by the neural network $\psi_\theta(\mathbf{x}_i)$.

To conclude, the advantage of contrastive learning is the single-stage nature of training. However, the performances of these methods are tied to the choices of augmentations, which may not always be clear cut depending on the data. For example, basic transformations such as translations, Gaussian blur, and scaling were shown to be efficient augmentations for classification and segmentation tasks of CT scans (Chlap et al., 2021; Garcea et al., 2023). Yet, this does not imply that these augmentations could be beneficial in an unsupervised context.

### 5.3.3 The InfoMax principle

Aside contrastive clustering, the InfoMax principle is another framework involving mutual information for learning continuous representations. It was started by Linsker (1988) and its goal was to construct a network such that: “The information that reaches a layer is processed so that the maximum amount of information is preserved. We have seen that this does not in general lead to a trivial one-to-one identity mapping [...]” (Linsker, 1988).

This principle was later refined by Hjelm et al. (2019) into the Deep InfoMax principle (DIM). Instead of focussing on a layer-wise maximisation of mutual information, the key proposal is to both maximise the mutual information between data and clusters as we previously described, but also enforce high mutual information between subsets of visual features of an image and the clusters. Denoting $g_{\theta_1}$ the local feature learning function and $\psi_{\theta_2}$ the representation function, the DIM can be written as follows:

$$ \theta_1^*, \theta_2^* \in \arg \max_{\theta_1, \theta_2} \mathcal{I}(\mathbf{x}; \psi_{\theta_2} \circ g_{\theta_1}(\mathbf{x})) + \lambda \sum_{i=1}^{M} \mathcal{I}(g_{\theta_1}(\mathbf{x})^{(i)}; \psi_{\theta_2} \circ g_{\theta_1}(\mathbf{x})), \quad (75) $$

where $g_{\theta_1}^{(i)}$ is the i-th subset of M subsets of features, e.g. some pixels in an image. Notice that we omitted the prior matching constraint of Hjelm et al. (2019) for clarity. In this original work, the NCE estimator was used for mutual information (Van den Oord et al., 2018), see Eq. (59).

The DIM framework has been extended, for example, to focus beyond local subsets of data features and instead consider augmentations of the data (Bachman et al., 2019). It was also incorporated into GANs (Lee et al., 2021) to avoid mode collapse. Nonetheless, we find that the modern meaning of InfoMax differs from mutual information for clustering as seen in the previous sections.

## 5.4 Dissonance between MI and performances

Evaluating the mutual information between two continuous random variables is challenging due to the intractability of the underlying integrals. Therefore, lower bounds were derived to alleviate the maximisation of mutual information. However, these bounds can come with either high variance or high bias. That is why Poole et al. (2019) proposed an interpolated lower bound to offer a trade-off between variance and bias: $\mathcal{I}_\alpha$. Nonetheless, it was noticed that MI is hardly predictive of downstream tasks (Tschannen et al., 2020) with the output continuous variable $z$. In other words, a high value of mutual information does not clarify whether the learnt continuous representations are insightful and can leverage a second-step task such as clustering or classification. This joins the criticism on mutual information directly maximised for clustering that we discussed in Section 3.3. Additionally, McAllester and Stratos (2020) proved that any lower bound on mutual information with $n \ge 50$ samples per batch cannot be greater than $\mathcal{O}(\log n)$. To conclude on mutual information, especially in contrastive models, since its value is constant and the model is often an ernegy-based variational approximation of $p_\theta(\mathbf{x} | z)$, perhaps a revision of what the objective actually is should be done. In this sense, McAllester and Stratos (2020) presented an estimation of mutual information via lower bound on entropies, even though their proposal might neither be an upper bound nor a lower bound on MI.

These observations stands in contrast to the most recent articles on deep clustering that achieve good performance in supervised datasets, e.g. CIFAR10 and ImageNet (Lee et al., 2022; Park et al.,
2021; Dang et al., 2021). Interestingly, the datasets used for benchmarking often focus on images and rarely other types of data such as tabular data (Min et al., 2018). Overall, it is plausible that the success of these methods may be due to the good design of the discriminative model's architecture which encompasses the underlying assumptions and its regularisations, rather than mutual information itself. Ren et al. (2024) noted that:

> "Due to the complexity brought by massive data, most of the existing deep clustering models are designed for specific data sets. Complex data from different sources and forms bring more uncertainties and challenges to clustering."

Consequently, we empirically observe that the number of clusters to find is an often overlooked question when the evaluation protocol lies on datasets in which the number of classes, not clusters, is known. Therefore, an interesting clustering algorithm should be able to find a relevant number of clusters, i.e. perform model selection. However, model selection for parametric deep clustering models is expensive (Ronen et al., 2022).

# 6 Model selection in discriminative clustering

We have seen so far that discriminative clustering initially started with a decoupling between the model, i.e. the type of decision boundary that we allow between clusters, and the objective function to optimise the model's parameters: mutual information. With the thrive of self-supervised learning, and especially contrastive learning, discriminative clustering took a turn where the model is no longer a decision boundary in the data space, but a critic function to identify samples from a common neighbourhood. Therefore, maximisation of mutual information in a contrastive fashion enforces a different interpretation on the nature of clusters: model and objective become entangled. The clustering hypotheses now concern the nature of neighbourhoods: we search how many augmentations away a sample is still the same sample. Finally, we further saw that mutual information was an objective that required regularisations to become a relevant discriminative objective, both for categorical and continuous predictions.

Once the hypotheses on the nature of the clusters are clearly defined, the second question to address is the number of clusters. To that end, we need internal metrics, i.e. scores that work on at most two inputs: the model's parameters and its predictions on the dataset. In contrast, unsupervised learning external metrics like the adjusted rand index (ARI Hubert and Arabie, 1985) require external labels that tell us how correct our clustering is. While it makes sense in a synthetic case where we have knowledge of what the model should discover and where we control the definition of the clusters, this is inapplicable to true unsupervised cases. In an exploratory scenario, we do not have access to any ground truth. That is why model selection must not rely on external metrics.

## 6.1 Existing internal metrics

In discriminative clustering, there exist internal metrics that are based on the model's predictions over the dataset: the K-means score, the silhouette score (Rousseeuw, 1987), the Davies-Bouldin index (Davies and Bouldin, 1979), or the Dunn index (Dunn, 1974) for example. As we covered the K-means score in Section 4, here we detail the silhouette score. For each sample $x$ belonging to the cluster $k$, we start by computing its average intra-cluster distance:

$$ \text{Intra}(\boldsymbol{x}) = \frac{1}{|C_k| - 1} \sum_{\boldsymbol{x}' \in C_k \setminus \boldsymbol{x}} c(\boldsymbol{x}, \boldsymbol{x}'), \qquad (76) $$

and its minimal average outer-cluster distance:

$$ \text{Outer}(\boldsymbol{x}) = \min_{k' \neq k} \frac{1}{|C_{k'}|} \sum_{\boldsymbol{x}' \in C_{k'}} c(\boldsymbol{x}, \boldsymbol{x}'), \qquad (77) $$
where c is the distance or cost of moving $\boldsymbol{x}$ to $\boldsymbol{x}'$. Note that both terms are sometimes referred to as average similarities. The silhouette score of the sample $\boldsymbol{x}$ is then the ratio between the difference of both terms divided by the greatest:

$$ \text{Silhouette}(\boldsymbol{x}) = \frac{\text{Outer}(\boldsymbol{x}) - \text{Intra}(\boldsymbol{x})}{\max\{\text{Intra}(\boldsymbol{x}), \text{Outer}(\boldsymbol{x})\}} \qquad (78) $$

The global silhouette score used to describe a model is the average between the individual silhouette values of each sample. In the same spirit, other scores like the Dunn index or the Davies-Bouldin index employ a notion of distance c.

To select a number of clusters, the common practice for the K-means score is to plot its value for all models trained on an increasing number of clusters. Finding the spot where the curve bends the most, called elbow, is expected to highlight a relevant number of clusters. However, such an approach can be criticised or discouraged due to the absence of proper definition of an elbow (Schubert, 2023), leading to unclear values of the number of clusters to retain. Instead, statistical methods that compare the score decrease on the dataset against bootstrap samples can be preferred, such as the gap statistic (Tibshirani et al., 2001). When the score decreases in a greater manner than its expectation over bootstrap samples, perhaps the model did find a suitable decision boundary. For other internal metrics, such as the Silhouette score, finding the highest value is common practice to choose the number of clusters.

This is just a brief overview of the existing metrics. Vendramin et al. (2010) compared for instance 40 different internal criteria for assessing clustering quality, a majority of which being available in Python for instance with the permetrics library (Thieu, 2024).

## 6.2 The necessity of adapting the internal metric to the model

There is however a critical dissonance in using such metrics in a raw manner: they do not respect the nature of the clustering hypotheses. To illustrate that point, let us take a kernelised model:

$$ p_{\theta}(y = k | \boldsymbol{x}) \propto \exp \left( \sum_{i=1}^{n} a_{ik} \kappa(\boldsymbol{x}_i, \boldsymbol{x}) \right), \qquad (79) $$

where $\kappa$ is a kernel tied to an RKHS $\mathcal{H}$ and the parameters $a_{ik}$ weight the kernel terms between the sample $\boldsymbol{x}$ and the i-th dataset sample $\boldsymbol{x}_i$ for the k-th cluster. Such a model can be trained by maximising mutual information, which is known as kernel RIM (Krause et al., 2010). This model seeks a linear boundary in a high-dimensional space. If the kernel is Gaussian, that space has infinite dimension. If the kernel is linear, then that space has the same dimension has $\mathcal{X}$. This consequently means that the model seeks to have a maximal distance between sample in this high-dimensional space, rather than the initial data space. Consequently, evaluating the clustering performances of this model using for instance a silhouette score or a kernel K-means that were not adequately changed to take into account the kernelised nature of the data will mislead the conclusions.

This reasoning can be extended to most cases where we seek decision boundaries that are nonlinear between the samples: internal scores based on distances must be changed. Moreover, when the nature of hypotheses diverges from decision boundaries to invariances, perhaps distance-based internal scores should be replaced by more relevant internal scores.

This limitation stands in contrast to generative scores, e.g. ICL or AIC. Indeed, generative scores for model selection can incorporate the likelihood value, therefore tacitly encompassing the generative hypotheses of the model within their definition. Discriminative scores rather come with their own set of hypotheses on the nature of clusters in a post hoc fashion, rather than being based on the definition of the clustering model.

A potential solution to address this duality would be to incorporate the model selection mechanism within the model. For example, Ronen et al. (2022) proposed a mechanism of cluster merging and splitting within their deep network architecture inspired by the Dirichlet process Gaussian mixture models (DPGMM, Antoniak, 1974). Using a Hastings ratio to accept split or merge proposals, they
```python
1 from sklearn import datasets
2 X, y = datasets.make_circles(n Samples=200, noise=0.05, factor=0.1,
3                               random_state=0)
3 X = (X - X.mean(axis=0)) / X.std(axis=0)
```

<caption>Listing 1: Sampling of the circle dataset.</caption>

progressively duplicate or create new neurons in the clustering layer. The architecture is composed of 3 main parts: a feature extractor, which could be trained using contrastive learning techniques, a main clustering layer, and sub-clustering multi-layered perceptrons that break down each cluster in two parts. Thus, without having any prior knowledge on the number of clusters ahead of training, the model can be tuned during optimisation to perform selection.

It is important to note that in recent surveys Ren et al. (2024); Min et al. (2018); Zhou et al. (2022) for deep clustering, model selection is often overlooked. Some of them mention the question of selecting the right number of clusters but not deeply explore this challenging issue. Wei et al. (2024) give some examples of deep learning models that successfully integrate mechanisms for selecting a number of cluster. These surveys encompass both generative and discriminative clustering models.

# 7 A complete example

Let us give a complete example on how to use some discriminative clustering models. We detail this entire example with matching code snippets for reproducibility. The code of this section can also be found in the following companion notebook: https://github.com/gemini-clustering/A-tutorial-on-discriminative-clustering.

We solve this example with distinct parts. In the first part, we use models that define $p(y | x)$, using the packages NumPy v1.26.4, Scikit-Learn v1.5.2 and GemClus v1.0.0. This covers the sections 7.3, 7.4 and 7.5. In the second part, Section 7.6, we identify the clusters using a contrastive model with PyTorch v2.5.0. No CUDA acceleration is needed.

## 7.1 GemClus: a package for discriminative clustering

Among the packages cited above, GemClus is a specialised package for discriminative clustering models. It was initially built around models trained using GEMINI (Ohl et al., 2022, 2024a), see Eq. (38). Today, it is extended and welcomes any discriminative clustering methods, e.g. RIM Krause et al. (2010), logistic regression with feature selection using MI Kong et al. (2015). An up-to-date list of implemented methods is available at: https://gemini-clustering.github.io/main/user_guide.html#a-summary-of-what-is-implemented. The package aims at keeping a decoupling between a choice of architecture, i.e. decision boundary, and the training objective, as discussed in Section 5.1.

## 7.2 The dataset

For this example, we will focus on a simple dataset consisting of two concentric circles, also known as two rings, using Listing 1.

## 7.3 Linear boundary models

In a generative modelling perspective, we would assume that data is distributed according to two concentric circles. The challenge here would lie in building such nonlinear distributions. In a discriminative clustering perspective, assumptions are made on the shape of the decision boundary. We can start with linear decision boundaries. It is clear that they will not be efficient for these datasets, as it is impossible to separate the two circles with a straight line. Consequently, models such as KMeans (see
```python
from sklearn import cluster, metrics
import gemclus
# Create a KMeans model
kmeans_model = cluster.KMeans(n Clusters=2, random_state=0)
# Fit to the data. Note the absence 'y' in the fit function.
y_kmeans = kmeans_model.fitPredict(X)
# Evaluate ARI with known targets.
ari_kmeans = metrics .adjusted rand score(y, y_kmeans)
print(f"ARI of KMeans predictions: {ari_kmeans :.3f} ") # 0.174
# Create a linear RIM clustering model
linear_rim_model = gemclus. linear .RIM(n Clusters=2, random_state=0)
y linear_rim = linear_rim_model.fitPredict(X)
ari linear = metrics .adjusted rand score(y, y linear_rim)
print(f"ARI of Linear RIM predictions: {ari linear :.3f} ") # -0.003
```

<caption>Listing 2: Clustering of circle dataset by models with linear decision boundaries.</caption>

Section 4.1) or RIM Krause et al. (2010) (see Section 5.1) are expected to not perform well. We give a snippet of code in Listing 2 where KMeans clustering gets an ARI of 0.178 and RIM an ARI of -0.003. For KMeans, the model is written as follows:

$$p_{\theta}(y = k | \mathbf{x}) = 1 \left[ k = \arg \min_{k'} \|\mathbf{x} - \boldsymbol{\mu}_{k'}\|_{2}^{2} \right], \qquad (80)$$

where $\theta = \{\boldsymbol{\mu}_k\}$, $\mu_k \in \mathbb{R}^2$ are the centroid parameters. For RIM, it is a logistic regression model:

$$p_{\theta}(y | \mathbf{x}) = \mathrm{SoftMax}(\mathbf{W}^{\top} \mathbf{x} + \mathbf{b}), \qquad (81)$$

where $\theta = \{\mathbf{W}, \mathbf{b}\}$, and $\mathbf{W} \in \mathbb{R}^{2 \times 2}$ and $\mathbf{b} \in \mathbb{R}^2$ are the parameters.

## 7.4 Projection models

To enhance the performances for this dataset, we have a visual cue that a straight line is not sufficient to separate both circles. A first approach we can try in this context is to project the dataset into a space where it is easier to separate. We can do this with both Spectral clustering, see Section 4.2, or kernel RIM, see Section 5.1. The spectral clustering is trained using the default parameters of scikit-learn. For kernel RIM, we use a radial-basis function kernel, which is known to produce a satisfying space for separating these circles, and no $\ell_2$ penalty.

We can summarise the spectral model with:

$$p_{\theta}(y = k | \mathbf{x}) = 1 \left[ k = \arg \min_{k'} \|\gamma(\mathbf{x}) - \boldsymbol{\mu}_{k'}\|_{2}^{2} \right], \qquad (82)$$

where $\gamma$ is the spectral embedding of $\mathbf{x}$ after finding the K largest eigenvalues of the proximity matrix of the dataset. This novel space is of dimension 2 because we seek two clusters. The parameters are therefore both $\boldsymbol{\mu}_k$ due to the final KMeans clustering algorithm, and $\gamma$, which hides assumptions on the relevant notion of proximity.

For kernel RIM, the model is written as follows:

$$p_{\theta}(y | \mathbf{x}) = \mathrm{Softmax}(\mathbf{W}^{\top} \boldsymbol{\kappa}(\mathbf{x}) + \mathbf{b}) \qquad (83)$$

where $\kappa(\mathbf{x}) = [\kappa(\mathbf{x}_i, \mathbf{x})] \in \mathbb{R}^n$ is the vector that describes the kernel value between the sample $\mathbf{x}$ and all dataset samples. Consequently, the parameters are $\mathbf{W} \in \mathbb{R}^{n \times 2}$, $\mathbf{b} \in \mathbb{R}^2$, and the choice of a kernel function $\kappa$.
```R
1
2
3
4
5
6
7
8
9
10

# Create a spectral clustering model
spectral_model = cluster.SpectralClustering(n Clusters=2)
y spectral = spectral_model.fitpredict(X)
ari spectral = metrics.adjusted rand score(y, y spectral)
print(f"ARI of Spectral predictions: {ari spectral: .3f}") # 1.000
# Create a kernel RIM clustering model without 12 penalty
kernel_rim model = gemclus. linear.KernelRIM(n Clusters=2, base kernel="rbf"
, reg=0, random_state=0)
y kernel_rim = kernel_rim_model.fitpredict(X)
ari kernel = metrics.adjusted rand score(y, y kernel_rim)
print(f"ARI of Kernel RIM predictions: {ari kernel: .3f}") # 1.000
```

<caption>Listing 3: Clustering of circle dataset by projection/kernel based models.</caption>

```R
1
2
3
4
5
6
7
8
9
10

# Create a neural network with MI objective
mlp mi model = gemclus.mlp.MLPModel(n Clusters=2, gemini="mi", n hidden dim
=20, random_state=0)
y mlp mi = mlp mi model.fitpredict(X)
ari mlp mi = metrics.adjusted rand score(y, y mlp mi)
print(f"ARI of MLP MI predictions: {ari mlp mi: .3f}") # 0.278
# Create a neural network with GEMINI objective
mlp gemini model = gemclus.mlp.MLPMMD(n Clusters=2, n hidden dim=20, kernel
="rbf", random_state=0)
y mlp gemini = mlp gemini model.fitpredict(X)
ari mlp gemini = metrics.adjusted rand score(y, y mlp gemini)
print(f"ARI of MLP MMD-GEMINI predictions: {ari mlp gemini: .3f}") #1
```

<caption>Listing 4: Clustering of circle dataset by neural network-based models.</caption>

We can then seek to enhance the properties of the algorithms. For instance, spectral clustering cannot generalise. It cannot assign a clustering probability to any sample outside of the training dataset. This means that we cannot observe the decision boundary of this algorithm. Generalising can be a desirable property, for example when we want to evaluate the conditional entropy around the decision boundary or find adversarial examples against the model. In the case of kernel RIM, although generalisation is possible, it requires to compute the kernel with all samples from the training set. This implies that the generalisation will scale linearly with the number of samples and may be expensive for large training datasets.

## 7.5 Small neural networks

Neural networks can simultaneously generalise and derive a projection of the dataset. In this case, a small neural network will suffice: we just need a single hidden layer with a couple nodes to place hyperplanes in a circular manner. Then, the final layer will draw the clustering hyperplane in the hidden representation. In the example of Listing 4, we train 2 neural networks with 20 hidden nodes. The first one is trained using MI. However, due to a lack of regularisation on a flexible architecture, this model does not perform well and gets an ARI of 0.278. This follows the critics on MI we discussed in Section 3.3. In contrast, the second model is trained with GEMINI, a distance-based generalisation of MI where the involvement of a distance in the objective acts as a regulariser. As we did with kernel RIM, we use an RBF kernel in the objective of this model. This model achieves perfect ARI.

For both models, the underlying architecture is:

$$ \psi_{\theta}(\boldsymbol{x}) = \boldsymbol{W}_{2}^{\top}\text{ReLU}(\boldsymbol{W}_{1}^{\top}\boldsymbol{x} + \boldsymbol{b}_{1}) + \boldsymbol{b}_{2}. \quad (84) $$

We can observe in Figure 5 the final clusterings obtained by each model in this example. For the models that can generalise, i.e. all but spectral clustering and kernel RIM, we plot the decision
<figure><img src="image_8.png" /><figcaption>Figure 5: Final clustering and decision boundaries of the example models on a circle dataset. Blue stands for low probability of cluster 2, red for high.</figcaption></figure>

boundary by showing the probability of cluster 2.

## 7.6 Identifying clusters with contrastive learning

For completeness of the example, we now expand the methods by showing how the clusters can be found using a contrastive learning method.

If we want to tackle the concentric circles using contrastive learning, we need to think in terms of invariances, as discussed in Section 5.3. This invariance will guide the choice of augmentations we can employ. For this dataset, it is clear that there is an invariance to rotation: no matter the angle of rotation around the origin, the clusters we aim for remain the same. Consequently, a rotation-based augmentation with a random angle may be a good strategy for using a contrastive loss. In contrast, adding random Gaussian noise may not be a good strategy as it will not necessarily suffice to make a good distinction between inner and outer circles. Let us compare both.

We take the exact same neural network architecture as before: a single hidden layer with 20 nodes. The only difference we may have is that there will not be a softmax activation at the end of this neural network. Indeed, the goal of this network is to discriminate between the respective augmented samples and the remaining samples, recalling Eq. (62). In other words, this network does not define a clustering distribution. In this example, we use the cosine similarity between two vectors. This implies that we need to normalise the output representations:

$$E_{\text{contrastive}}(\mathbf{x}_i, \text{Aug}(\mathbf{x}_j)) = \left\langle \frac{\psi_{\theta}(\mathbf{x}_i)}{\|\psi_{\theta}(\mathbf{x}_i)\|}, \frac{\psi_{\theta}(\text{Aug}(\mathbf{x}_j))}{\|\psi_{\theta}(\text{Aug}(\mathbf{x}_j))\|} \right\rangle. \quad (85)$$

The model is:

$$q_{\theta}(\mathbf{x} | \text{Aug}(\mathbf{x})) \propto p_{\text{data}}(\mathbf{x})e^{E_{\text{contrastive}}(\mathbf{x}, \text{Aug}(\mathbf{x}))}, \quad (86)$$

and we optimise its parameters $\theta$ such that $q_{\theta}$ approximates $p(\mathbf{x} | \text{Aug}(\mathbf{x}))$.

To extract a clustering out of this model, we choose to have 2 output dimensions, 1 per cluster, and will take the argmax as the final cluster, following the examples from Section 5.3.2. We give with Listing 5 an example of training such a model using a random rotation per batch in $[0, 2\pi]$ during 5000 epochs and a learning rate of $10^{-4}$ in an Adam optimiser.
import torch
torch.manual_seed(0)
model = torch.nnSequential(
    torch.nn Linear X shape [1], 20),
    torch.nn ReLU(),
    torch.nn Linear 20, 2) # Observe the absence of softmax
)
optimiser = torch.optimAdam(model.parameters(), lr=1e-4)
X = torch parter X
for i in tqdm(range(5000)):
    # AUGMENTATION
theta = 2*torch pi*torch .rand(1) # [0, 2*pi]
rotation_matrix = torch parter (
    [[torch .cos theta), -torch .sin theta)],
    [torch .sin theta), torch .cos theta)]])
augmentedSamples = X@rotation_matrix.T
# PREDICTION
original = model(X)
with torch .noGrad():
    # For simplicity, we do not backpropagate on augmented samples
    augmentedprediction = model(augmentedSamples)
# LOSS
## Softmax of cosine similarity energy
original_normalised = originalentection /
    torch .norm (original _prediction, dim=1, keepdim = True)
augmented_normalised = augmented _prediction /
    torch .norm (augmented _prediction, dim=1, keepdim = True)
similarities = original_normalised @ augmented_normalised.T
loss = torch .diag (torch .softmax (similarities, dim=0))
loss = -loss .sum() # Negate because we seek to maximise
# GRADIENT DESCENT
optimiser .zeroGrad()
loss .backward()
optimiser.step()

<caption>Listing 5: Clustering of circle dataset using invariances in contrastive learning.</caption>
<figure><img src="image_9.png" /><figcaption>Figure 6: Decision boundary using the maximal dimension of the contrastive critic function depending on the choice of augmentation on the data. We either add Gaussian noise or randomly rotate the dataset around the origin.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 7: Unnormalised 2d intermediate representation of the dataset produced by the discriminating neural network. Decision boundary is made depending on the location above or below the identity axis. Samples are coloured according to inner/outer circles.</figcaption></figure>

Exactly as in the previous case, using a neural network allows us to generalise. However, we must keep in mind that the predictions we use here to draw a decision boundary correspond to the highest value of a 2-dimensional vector intended to discriminate between augmented and original sample pairs. The plotted values do not therefore represent a clustering conditional probability $p_\theta(y | x)$.

Using the same parameters and initial weights, we can compare the decision boundary obtained by this model depending on the augmentation strategy. We show the different boundaries in Figure 6, and the matching 2d representation returned by the model in Figure 7. When adding unit Gaussian noise, the scale of the noise overlaps all the dataset. Consequently, all samples are considered close to each other and a suitable choice of decision boundary is to cut in the middle. Reducing the noise scale does not solve the issue.

Rotation invariance may not be sufficient for more challenging datasets. If we generalise to multiple circles, rotation would not guarantee a one-to-one relationship between clusters and circles: a model could put two circles in the same cluster, and would remain invariant to rotation. So ideally, we should seek a combination of a small-scale Gaussian noise and rotation to have both invariance to small radius change and angle variations.

One final criticism we can elaborate on this example is that we *knew* the form of the clusters we were looking for. This means that we rigged the choice of augmentations, distance or model to achieve the desired clusters. In a data analysis context, we would not necessarily have such a "prior" on the choice of models for clustering, and expert knowledge would be expected to build reasonable hypotheses on invariances or decision boundary shapes.
# 8 Take-aways

We presented here an overview of the historical evolution of discriminative clustering and how mutual information was a cornerstone of its development. We started by detailing how the discriminative clustering assumptions are different from generative models that assume probability distributions on the data. We showed that the initial hypotheses focused more on using a specific type of decision boundary with shallow models. Then, we saw how that notion of decision boundary was dropped by the usage of nonparametric models in different fashions, especially with neural networks growing deeper and deeper. Finally, we observed how the nature of the discriminative hypotheses changed to defining neighbourhoods of samples through invariances and augmentations to construct clusters. The ensuing objectives, lower bounds on mutual information, then became entangled with the model in the clustering hypotheses. Consequently, models trained today rather correspond to critic functions that aim at identifying similar samples, rather than a straightforward distribution $p_{\theta}(y | x)$. We notably highlighted that the objective is the lower bound on a constant value of mutual information, and that the true underlying model is an energy-based model aiming at recovering true samples $x$ given an augmentation $z: q_{\theta}(x | z)$.

Concentrating on mutual information, we covered some of its limitations that are often depicted by related works. We observed that the rise of mutual information in discriminative clustering was therefore accompanied by increases in the attempts to regularise its limitations: weight decay, adversarial penalty, contrastive invariances. It is likely that the recent successes of deep clustering methods using mutual information should be granted to the clever design of such regularisations, rather than the objective itself. Moreover, the identification of the actual energy-based model in contrastive learning questions whether mutual information is actually the objective we need to learn deep clustering method, or whether novel objectives should be considered for optimising their parameters.

Finally, we observed that discriminative clustering, especially regarding deep methods, calls for an adaptation of model selection strategies. The internal metrics should typically be in line with the clustering hypotheses that are used to construct clustering instead of being post hoc tools in an evaluation protocol. The crucial questions of clustering revolve both on clustering hypotheses and their consequential impact on what could be deemed a good number of clusters. In this sense, incorporating model selection mechanisms within the architecture of the training procedure could be a promising direction.

# References

Charles E Antoniak. Mixtures of dirichlet processes with applications to bayesian nonparametric problems. *The annals of statistics*, pages 1152–1174, 1974.

Philip Bachman, R. Devon Hjelm, and William Buchwalter. Learning Representations by Maximizing Mutual Information Across Views. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett, editors, *Advances in Neural Information Processing Systems*, volume 32. Curran Associates, Inc., 2019.

Jeffrey D Banfield and Adrian E Raftery. Model-Based Gaussian and Non-Gaussian Clustering. *Biometrics*, pages 803–821, 1993. Publisher: JSTOR.

David Barber and Felix V Agakov. The IM Algorithm: A Variational Approach to Information Maximization. In *NIPS*, 2003.

Punam Bedi and Chhavi Sharma. Community Detection in Social Networks. *WIREs Data Mining and Knowledge Discovery*, 6(3):115–135, 2016. doi: 10.1002/widm.1178.

Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual Information Neural Estimation. In Jennifer Dy and Andreas
Krause, editors, *Proceedings of the 35th International Conference on Machine Learning*, volume 80 of *Proceedings of Machine Learning Research*, pages 531–540. PMLR, July 2018.

Christophe Biernacki, Gilles Celeux, and Gérard Govaert. Assessing a Mixture Model for Clustering with the Integrated Completed Likelihood. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 22(7):719–725, 2000. doi: 10.1109/34.865189.

Christopher M. Bishop. *Pattern Recognition and Machine Learning (Information Science and Statistics)*. Springer, 1 edition, 2007. ISBN 0-387-31073-8.

Leticia Bode, Alexander Hanna, Junghwan Yang, and Dhavan V. Shah. Candidate Networks, Citizen Clusters, and Political Expression: Strategic Hashtag Use in the 2010 Midterms. *The ANNALS of the American Academy of Political and Social Science*, 659(1):149–165, 2015. doi: 10.1177/0002716214563923.

Charles Bouveyron and Camille Brunet. Simultaneous model-based clustering and visualization in the fisher discriminative subspace. *Statistics and Computing*, 22(1):301–324, 2012.

Charles Bouveyron, Gilles Celeux, T Brendan Murphy, and Adrian E Raftery. *Model-Based Clustering and Classification for Data Science: With Applications in R*. in Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.

John Bridle, Anthony Heading, and David MacKay. Unsupervised Classifiers, Mutual Information and 'Phantom' Targets. In J. Moody, S. Hanson, and R. P. Lippmann, editors, *Advances in Neural Information Processing Systems*, volume 4. Morgan-Kaufmann, 1992.

Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised Learning of Visual Features by Contrasting Cluster Assignments. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, *Advances in Neural Information Processing Systems*, volume 33, pages 9912–9924. Curran Associates, Inc., 2020.

Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A Simple Framework for Contrastive Learning of Visual Representations. In *International Conference on Machine Learning*, pages 1597–1607. PMLR, 2020.

Phillip Chlap, Hang Min, Nym Vandenberg, Jason Dowling, Lois Holloway, and Annette Haworth. A Review of Medical Image Data Augmentation Techniques for Deep Learning Applications. *Journal of Medical Imaging and Radiation Oncology*, 65(5):545–563, 2021. Publisher: Wiley Online Library.

Adrian Corduneanu and Tommi Jaakkola. On Information Regularization. In *Proceedings of the Nineteenth conference on Uncertainty in Artificial Intelligence*, pages 151–158, 2002.

Zhiyuan Dang, Cheng Deng, Xu Yang, Kun Wei, and Heng Huang. Nearest Neighbor Matching for Deep Clustering. In *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*, pages 13693–13702, 2021.

David L. Davies and Donald W. Bouldin. A Cluster Separation Measure. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, PAMI-1(2):224–227, 1979. doi: 10.1109/TPAMI.1979.4766909.

Fernando De la Torre and Takeo Kanade. Discriminative cluster analysis. In *Proceedings of the 23rd International Conference on Machine Learning*, ICML '06, page 241–248, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595933832. doi: 10.1145/1143844.1143875.

Inderjit S Dhillon, Subramanyam Mallela, and Rahul Kumar. A Divisive Information Theoretic Feature Clustering Algorithm for Text Classification. *JMLR*, 3:1265–1287, 2003. Publisher: JMLR.org.
Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Kernel K-Means: Spectral Clustering and Normalized Cuts. In *Proceedings of the Tenth Acm Sigkdd International Conference on Knowledge Discovery and Data Mining*, pages 551–556, 2004.

Nat Dilokthanakul, Pedro AM Mediano, Marta Garnelo, Matthew CH Lee, Hugh Salimbeni, Kai Arulukmaran, and Murray Shanahan. Deep Unsupervised Clustering with Gaussian Mixture Variational Autoencoders. *arXiv preprint arXiv:1611.02648*, 2016.

Kien Do, Truyen Tran, and Svetha Venkatesh. Clustering by Maximizing Mutual Information Across Views. In *Proceedings of the IEEE/CVF International Conference on Computer Vision*, pages 9928–9938, 2021.

Joseph C Dunn. Well-Separated Clusters and Optimal Fuzzy Partitions. *Journal of Cybernetics*, 4(1): 95–104, 1974. Publisher: Taylor & Francis.

Charles Elkan. Using the Triangle Inequality to Accelerate K-Means. In *Proceedings of the 20th International Conference on Machine Learning (icml-03)*, pages 147–153, 2003.

Vladimir Estivill-Castro. Why so Many Clustering Algorithms: A Position Paper. *Acm Sigkdd Explorations Newsletter*, 4(1):65–75, 2002. Publisher: ACM New York, NY, USA.

Guilherme França, Maria L Rizzo, and Joshua T Vogelstein. Kernel K-Groups via Hartigan's Method. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 43(12):4411–4425, 2020. Publisher: IEEE.

Fabio Garcea, Alessio Serra, Fabrizio Lamberti, and Lia Morra. Data Augmentation for Medical Imaging: A Systematic Literature Review. *Computers in Biology and Medicine*, 152:106391, 2023. ISSN 0010-4825. doi: doi.org/10.1016/j.compbiomed.2022.106391.

Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative Adversarial Nets. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, *Advances in Neural Information Processing Systems*, volume 27. Curran Associates, Inc., 2014.

Leo A Goodman. Exploratory Latent Structure Analysis Using Both Identifiable and Unidentifiable Models. *Biometrika*, 61(2):215–231, 1974. Publisher: Oxford University Press.

Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A Kernel Two-Sample Test. *The Journal of Machine Learning Research*, 13(1):723–773, 2012.

Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pages 770–778, 2016.

Christian Hennig. What are the True Clusters? *Pattern Recognition Letters*, 64:53–62, 2015. ISSN 0167-8655. doi: 10.1016/j.patrec.2015.04.009.

Itai Himelboim, Marc A. Smith, Lee Rainie, Ben Shneiderman, and Camila Espina. Classifying Twitter Topic-Networks Using Social Network Analysis. *Social Media + Society*, 3(1):2056305117691545, 2017. doi: 10.1177/2056305117691545.

R. Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning Deep Representations by Mutual Information Estimation and Maximization. In *International Conference on Learning Representations*, 2019.

Thomas Hofmann, Bernhard Schölkopf, and Alexander J Smola. Kernel Methods in Machine Learning. *The Annals of Statistics*, 36(3):1171–1220, 2008.
Weihua Hu, Takeru Miyato, Seiya Tokui, Eiichi Matsumoto, and Masashi Sugiyama. Learning Discrete Representations via Information Maximizing Self-Augmented Training. In Doina Precup and Yee Whye Teh, editors, *Proceedings of the 34th International Conference on Machine Learning*, volume 70 of *Proceedings of Machine Learning Research*, pages 1558–1567. PMLR, August 2017.

Jiabo Huang, Shaogang Gong, and Xiatian Zhu. Deep Semantic Clustering by Partition Confidence Maximisation. In *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*, pages 8849–8858, 2020.

Lawrence Hubert and Phipps Arabie. Comparing Partitions. *Journal of Classification*, 2(1):193–218, 1985. Publisher: Springer.

Mohammed Jabi, Marco Pedersoli, ar Mitiche, A, and Ismail Ben Ayed. Deep Clustering: On the Link Between Discriminative Models and K-means. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, pages 1–1, 2019. doi: 10.1109/TPAMI.2019.2962683.

Anil K. Jain, Narasimha N. Murty, and Patrick J. Flynn. Data clustering: a review. *ACM Comput. Surv.*, 31(3):264–323, September 1999. ISSN 0360-0300. doi: 10.1145/331499.331504.

Eric Jang, Shixiang Gu, and Ben Poole. Categorical Reparameterization with Gumbel-Softmax. In *International Conference on Learning Representations*, 2017.

Xu Ji, Joao F Henriques, and Andrea Vedaldi. Invariant Information Clustering for Unsupervised Image Classification and Segmentation. In *Proceedings of the IEEE/CVF International Conference on Computer Vision*, pages 9865–9874, 2019.

Zhuxi Jiang, Yin Zheng, Huachun Tan, Bangsheng Tang, and Hanning Zhou. Variational Deep Embedding: An Unsupervised and Generative Approach to Clustering. In *Proceedings of the 26th International Joint Conference on Artificial Intelligence*, IJCAI’17, pages 1965–1972. AAAI Press, 2017. ISBN 978-0-9992411-0-3. Place: Melbourne, Australia.

Tushar Kansal, Suraj Bahuguna, Vishal Singh, and Tanupriya Choudhury. Customer Segmentation Using K-Means Clustering. In *2018 International Conference on Computational Techniques, Electronics and Mechanical Systems (ctems)*, pages 135–139. IEEE, 2018.

Dimitris Karlis and Panagiotis Tsiamyrtzis. Exact Bayesian Modeling for Bivariate Poisson Data and Extensions. *Statistics and Computing*, 18:27–40, 2008. Publisher: Springer.

Kishana R Kashwan and CM Velu. Customer Segmentation using Clustering and Data Mining Techniques. *International Journal of Computer Theory and Engineering*, 5(6):856, 2013. Publisher: IACSIT Press.

Diederik P Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. *arXiv preprint arXiv:1412.6980*, 2014.

Jon Kleinberg. An Impossibility Theorem for Clustering. In S. Becker, S. Thrun, and K. Obermayer, editors, *Advances in Neural Information Processing Systems*, volume 15. MIT Press, 2003.

Daphne Koller and Nir Friedman. *Probabilistic graphical models: principles and techniques*. MIT press, 2009.

Youyong Kong, Yue Deng, and Qionghai Dai. Discriminative Clustering and Feature Selection for Brain MRI Segmentation. *IEEE Signal Processing Letters*, 22(5):573–577, 2015. doi: 10.1109/LSP.2014.2364612.

Andreas Krause, Pietro Perona, and Ryan Gomes. Discriminative Clustering by Regularized Information Maximization. In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, *Advances in Neural Information Processing Systems*, volume 23. Curran Associates, Inc., 2010.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet Classification with Deep Convolutional Neural Networks. *Advances in Neural Information Processing Systems*, 25, 2012.

Soongu Kwak, Yunhwan Lee, Taehoon Ko, Seokhun Yang, In-Chang Hwang, Jun-Bean Park, Yeonyee E. Yoon, Hack-Lyoung Kim, Hyung-Kwan Kim, Yong-Jin Kim, Goo-Yeong Cho, Dae-Won Sohn, Sungho Won, and Seung-Pyo Lee. Unsupervised Cluster Analysis of Patients With Aortic Stenosis Reveals Distinct Population With Different Phenotypes and Outcomes. *Circulation: Cardiovascular Imaging*, 13(5):e009707, May 2020. doi: 10.1161/CIRCIMAGING.119.009707. Publisher: American Heart Association.

Dong Hoon Lee, Sungik Choi, Hyunwoo J Kim, and Sae-Young Chung. Unsupervised Visual Representation Learning via Mutual Information Regularized Assignment. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, *Advances in Neural Information Processing Systems*, volume 35, pages 29610–29623. Curran Associates, Inc., 2022.

Kwot Sin Lee, Ngoc-Trung Tran, and Ngai-Man Cheung. InfoMax-GAN: Improved Adversarial Image Generation via Information Maximization and Contrastive Learning. In *Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)*, pages 3942–3952, January 2021.

Yunfan Li, Peng Hu, Zitao Liu, Dezhong Peng, Joey Tianyi Zhou, and Xi Peng. Contrastive Clustering. In *2021 AAAI Conference on Artificial Intelligence (AAAI)*, 2021.

Aristidis Likas, Nikos Vlassis, and Jakob J. Verbeek. The Global K-Means Clustering Algorithm. *Pattern Recognition*, 36(2):451–461, 2003. ISSN 0031-3203. doi: doi.org/10.1016/S0031-3203(02)00060-2.

Ralph Linsker. Self-Organization in a Perceptual Network. *Computer*, 21(3):105–117, 1988. doi: 10.1109/2.36.

Stuart Lloyd. Least Squares Quantization in PCM. *Ieee Transactions on Information Theory*, 28(2): 129–137, 1982. Publisher: IEEE.

Kenneth Lo, Ryan Remy Brinkman, and Raphael Gottardo. Automated Gating of Flow Cytometry Data via Robust Model-Based Clustering. *Cytometry Part a: The Journal of the International Society for Analytical Cytology*, 73(4):321–332, 2008. Publisher: Wiley Online Library.

Chao Ma, Sebastian Tschiatschek, Richard Turner, José Miguel Hernández-Lobato, and Cheng Zhang. VAEM: a Deep Generative Model for Heterogeneous Mixed Type Data. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, *Advances in Neural Information Processing Systems*, volume 33, pages 11237–11247. Curran Associates, Inc., 2020.

Matthieu Marbac and Mohammed Sedki. Variable Selection for Model-Based Clustering using the Integrated Complete-Data Likelihood. *Statistics and Computing*, 27(4):1049–1063, 2017. Publisher: Springer.

Matthieu Marbac, Christophe Biernacki, and Vincent Vandewalle. Model-Based Clustering of Gaussian Copulas for Mixed Data. *Communications in Statistics-Theory and Methods*, 46(23):11635–11656, 2017. Publisher: Taylor & Francis.

David McAllester and Karl Stratos. Formal Limitations on the Measurement of Mutual Information. In Silvia Chiappa and Roberto Calandra, editors, *Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics*, volume 108 of *Proceedings of Machine Learning Research*, pages 875–884. PMLR, August 2020.

Geoffrey J McLachlan and Thriyambakam Krishnan. *The EM Algorithm and Extensions*. John Wiley & Sons, 2007.
Geoffrey J. McLachlan, Richard W. Bean, and David Peel. A Mixture Model-Based Approach to the Clustering of Microarray Expression Data. *Bioinformatics*, 18(3):413-422, March 2002. ISSN 1367-4803. doi: 10.1093/bioinformatics/18.3.413.

Daniel P. M. de Mello, Renato M. Assunção, and Fabricio Murai. Top-Down Deep Clustering with Multi-Generator GANs. In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 36, pages 7770-7778, June 2022. doi: 10.1609/aaai.v36i7.20745.

Erxue Min, Xifeng Guo, Qiang Liu, Gen Zhang, Jianjing Cui, and Jun Long. A Survey of Clustering With Deep Learning: From the Perspective of Network Architecture. *IEEE Access*, PP:1-1, 2018. doi: 10.1109/ACCESS.2018.2855437.

Tom Minka. Discriminative Models, not Discriminative Training. Technical report, Technical Report MSR-TR-2005-144, Microsoft Research, 2005.

Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii. Virtual Adversarial Training: A Regularization Method for Supervised and Semi-Supervised Learning. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 41(8):1979-1993, 2018.

Andrew Ng, Michael Jordan, and Yair Weiss. On Spectral Clustering: Analysis and an Algorithm. *Advances in Neural Information Processing Systems*, 14, 2001.

Gopi Chand Nutakki, Behnoush Abdollahi, Wenlong Sun, and Olfa Nasraoui. An Introduction to Deep Clustering. *Clustering Methods for Big Data Analytics: Techniques, Toolboxes and Applications*, pages 73-89, 2019.

Louis Ohl, Pierre-Alexandre Mattei, Charles Bouveyron, Warith Harchaoui, Mickaël Leclercq, Arnaud Droit, and Frederic Precioso. Generalised Mutual Information for Discriminative Clustering. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, *Advances in Neural Information Processing Systems*, volume 35, pages 3377-3390. Curran Associates, Inc., 2022.

Louis Ohl, Pierre-Alexandre Mattei, Charles Bouveyron, Warith Harchaoui, Mickaël Leclercq, Arnaud Droit, and Frédéric Precioso. Generalised Mutual Information: a Framework for Discriminative Clustering, 2023a. _eprint: 2309.02858_.

Louis Ohl, Pierre-Alexandre Mattei, and Frederic Precioso. GemClus, November 2023b.

Louis Ohl, Pierre-Alexandre Mattei, Charles Bouveyron, Mickaël Leclercq, Arnaud Droit, and Frédéric Precioso. Sparse and geometry-aware generalisation of the mutual information for joint discriminative clustering and feature selection. *Statistics and Computing*, 34(5):155, July 2024a. ISSN 1573-1375. doi: 10.1007/s11222-024-10467-9.

Louis Ohl, Pierre-Alexandre Mattei, Mickaël Leclercq, Arnaud Droit, and Frédéric Precioso. Kernel KMeans clustering splits for end-to-end unsupervised decision trees, 2024b.

Sungwon Park, Sungwon Han, Sundong Kim, Danu Kim, Sungkyu Park, Seunghoon Hong, and Meeyoung Cha. Improving Unsupervised Image Clustering With Robust Learning. In *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*, pages 12278-12287, 2021.

David Peel and Geoffrey J McLachlan. Robust Mixture Modelling using the t Distribution. *Statistics and computing*, 10:339-348, 2000. Publisher: Springer.

Gabriel Peyré and Marco Cuturi. Computational Optimal Transport: With Applications to Data Science. *Foundations and Trends in Machine Learning*, 11(5-6):355-607, 2019. ISSN 1935-8237. Publisher: Now Publishers, Inc.
Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On Variational Bounds of Mutual Information. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, *Proceedings of the 36th International Conference on Machine Learning*, volume 97 of *Proceedings of Machine Learning Research*, pages 5171–5180. PMLR, June 2019.

Yazhou Ren, Jingyu Pu, Zhimeng Yang, Jie Xu, Guofeng Li, Xiaorong Pu, S Yu Philip, and Lifang He. Deep clustering: A comprehensive survey. *IEEE Transactions on Neural Networks and Learning Systems*, 2024.

Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic Backpropagation and Approximate Inference in Deep Generative Models. In Eric P. Xing and Tony Jebara, editors, *Proceedings of the 31st International Conference on Machine Learning*, volume 32 of *Proceedings of Machine Learning Research*, pages 1278–1286. PMLR, June 2014.

Meitar Ronen, Shahaf E. Finder, and Oren Freifeld. DeepDPM: Deep Clustering With an Unknown Number of Clusters. In *2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)*, pages 9851–9860, 2022. doi: 10.1109/CVPR52688.2022.00963.

Peter J Rousseeuw. Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis. *Journal of Computational and Applied Mathematics*, 20:53–65, 1987. Publisher: Elsevier.

Erich Schubert. Stop Using the Elbow Criterion for K-Means and How to Choose the Number of Clusters Instead. *SIGKDD Explor. Newsl.*, 25(1):36–42, July 2023. ISSN 1931-0145. doi: 10.1145/3606274.3606278. Place: New York, NY, USA Publisher: Association for Computing Machinery.

Gideon Schwarz. Estimating the Dimension of a Model. *The Annals of Statistics*, 6(2):461–464, 1978. doi: 10.1214/aos/1176344136. Publisher: Institute of Mathematical Statistics.

Jianbo Shi and Jitendra Malik. Normalized Cuts and Image Segmentation. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 22(8):888–905, 2000. Publisher: IEEE.

Noam Slonim and Naftali Tishby. Document Clustering using Word Clusters via the Information Bottleneck Method. In *Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval*, pages 208–215, 2000.

Noam Slonim, Gurinder Singh Atwal, Gašper Tkačik, and William Bialek. Information-Based Clustering. *Proceedings of the National Academy of Sciences*, 102(51):18297–18302, 2005. Publisher: National Academy of Sciences.

Julien Soler, Fabien Tencé, Laurent Gaubert, and Cédric Buche. Data Clustering and Similarity. In *The Twenty-Sixth International FLAIRS Conference*, 2013.

Jost Tobias Springenberg. Unsupervised and Semi-Supervised Learning with Categorical Generative Adversarial Networks. *arXiv preprint arXiv:1511.06390*, 2015.

Alexander Sturn, John Quackenbush, and Zlatko Trajanoski. Genesis: Cluster Analysis of Microarray Data. *Bioinformatics*, 18(1):207–208, 2002. Publisher: Oxford University Press.

Masashi Sugiyama, Makoto Yamada, Manabu Kimura, and Hirotaka Hachiya. On information-maximization clustering: Tuning parameter selection and analytic solution. In *Proceedings of the 28th International Conference on Machine Learning (ICML-11)*, pages 65–72, 2011.

Nguyen Van Thieu. PerMetrics: A Framework of Performance Metrics for Machine Learning Models. *Journal of Open Source Software*, 9(95):6143, March 2024. doi: 10.21105/joss.06143.
Robert Tibshirani, Guenther Walther, and Trevor Hastie. Estimating the Number of Clusters in a Data
Set via the Gap Statistic. *Journal of the Royal Statistical Society: Series B (Statistical Methodology)*, 63(2):411–423, 2001. ISSN 13697412. doi: 10.1111/1467-9868.00293.

Naftali Tishby, Fernando C Pereira, and William Bialek. The Information Bottleneck Method. *arXiv preprint physics/0004057*, 2000.

Michael Tschannen, Josip Djolonga, Paul K. Rubenstein, Sylvain Gelly, and Mario Lucic. On Mutual Information Maximization for Representation Learning. In *International Conference on Learning Representations*, 2020.

Aaron Van den Oord, Yazhe Li, and Oriol Vinyals. Representation Learning with Contrastive Predictive Coding. *arXiv e-prints*, pages arXiv-1807, 2018.

Lucas Vendramin, Ricardo JGB Campello, and Eduardo R Hruschka. Relative Clustering Validity Criteria: A Comparative Overview. *Statistical analysis and data mining: the ASA data science journal*, 3(4):209–235, 2010. Publisher: Wiley Online Library.

Greg Ver Steeg, Aram Galstyan, Fei Sha, and Simon DeDeo. Demystifying Information-Theoretic Clustering. In *International Conference on Machine Learning*, pages 19–27. PMLR, 2014.

Ulrike von Luxburg. A Tutorial on Spectral Clustering. *Statistics and Computing*, 17(4):395–416, December 2007. ISSN 1573-1375. doi: 10.1007/s11222-007-9033-z.

Xiuxi Wei, Zhihui Zhang, Huajuan Huang, and Yongquan Zhou. An Overview on Deep Clustering. *Neurocomputing*, 590:127761, 2024. ISSN 0925-2312. doi: 10.1016/j.neucom.2024.127761.

Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised Deep Embedding for Clustering Analysis. In Maria Florina Balcan and Kilian Q. Weinberger, editors, *Proceedings of The 33rd International Conference on Machine Learning*, volume 48 of *Proceedings of Machine Learning Research*, pages 478–487, New York, New York, USA, June 2016. PMLR.

Jieping Ye, Zheng Zhao, and Mingrui Wu. Discriminative k-means for clustering. *Advances in neural information processing systems*, 20, 2007.

Sheng Zhou, Hongjia Xu, Zhuonan Zheng, Jiawei Chen, Zhao Li, Jiajun Bu, Jia Wu, Xin Wang, Wenwu Zhu, and Martin Ester. A comprehensive survey on deep clustering: Taxonomy, challenges, and future directions. *ACM Computing Surveys*, 2022.