# Generalised Mutual Information: a Framework for Discriminative Clustering

Louis Ohl,Pierre-Alexandre Mattei, Charles Bouveyron, Warith Harchaoui,
Mickaël Leclercq, Arnaud Droit, Frédéric Precioso L. Ohl, P-A. Mattei, C.
Bouveyron and F. Precioso are with the Université Côte d’Azur, INRIA Maasai
team, CNRS M. Leclercq, A. Droit and L. Ohl are with the Université Laval, CHU
de Québec Research Centre W. Harchaoui is with Jellysmack, Artificial
Intelligence Lab in ParisManuscript under review

###### Abstract

In the last decade, recent successes in deep clustering majorly involved the
Mutual Information (MI) as an unsupervised objective for training neural
networks with increasing regularisations. While the quality of the
regularisations have been largely discussed for improvements, little attention
has been dedicated to the relevance of MI as a clustering objective. In this
paper, we first highlight how the maximisation of MI does not lead to
satisfying clusters. We identified the Kullback-Leibler divergence as the main
reason of this behaviour. Hence, we generalise the mutual information by
changing its core distance, introducing the Generalised Mutual Information
(GEMINI): a set of metrics for unsupervised neural network training. Unlike
MI, some GEMINIs do not require regularisations when training as they are
geometry-aware thanks to distances or kernels in the data space. Finally, we
highlight that GEMINIs can automatically select a relevant number of clusters,
a property that has been little studied in deep discriminative clustering
context where the number of clusters is a priori unknown.

###### Index Terms:

Clustering, discriminative clustering, unsupervised learning, information
theory, mutual information, machine learning

##  1 Introduction

Clustering is a fundamental learning task which consists in separating data
samples into several categories, each named cluster. This task hinges on two
main questions concerning the assessment of correct clustering and the actual
number of clusters that may be contained within the data distribution.
However, this problem is ill-posed since a cluster lacks formal definitions
which makes it a hard problem [40].

Model-based algorithms make assumptions about the true distribution of the
data as a result of some latent distribution of clusters [6]. These techniques
are able to find the most likely cluster assignment to data points. These
models are usually generative, exhibiting an explicit assumption of the prior
knowledge on the data.

Early deep models to perform clustering first relied on autoencoders, based on
the belief that an encoding space holds satisfactory properties [68, 23, 37].
However, the drawback of these architectures is that they do not guarantee
that data samples which should meaningfully be far apart remain so in the
feature space. Early models that dropped decoders notably used the Mutual
Information (MI) [41, 33] as an objective to maximise. The MI can be written
in two ways, either as measure of dependency between two variables
$\boldsymbol{x}$ and $y$, e.g. data distribution $p(\boldsymbol{x})$ and
cluster assignment $p(y)$:

$\mathcal{I}(\boldsymbol{x};y)=D_{\text{KL}}(p(\boldsymbol{x},y)||p(\boldsymbol{x})p(y)),$
(1)

or as an expected distance between implied distributions and the overall data:

$\mathcal{I}(\boldsymbol{x};y)=\mathbb{E}_{p(y)}[D_{\text{KL}}(p(\boldsymbol{x}|y)||p(\boldsymbol{x}))],$
(2)

with $D_{\text{KL}}$ being the Kullback-Leibler (KL) divergence. Related works
often relied on the notion of MI as a measure of coherence between cluster
assignments and data distribution [31]. Regularisation techniques were
employed to leverage the potential of MI, mostly by specifying model
invariances, for example with data augmentation [37].

The maximisation of MI thus gave way to contrastive learning objectives which
aim at learning stable representations of data through such invariance
specifications [13, 11]. The contrastive loss maximises the similarity between
the features of a sample and its augmentation, while decreasing the similarity
with any other sample. Clustering methods also benefited from recent
successful deep architectures [43, 61, 34] by encompassing regularisations in
the architecture. These methods correspond to discriminative clustering where
we seek to directly infer cluster given the data distribution. Initial methods
also focused on alternate schemes, for example with curriculum learning [12]
to iteratively select relevant data samples for training, by alternating
K-means cluster assignment with supervised learning using the inferred labels
[10], or by proceeding to multiple distinct training steps [64, 16, 53].

However, most of the methods above rarely discuss their robustness when the
number of clusters to find is different from the amount of preexisting known
classes. While previous work was essentially motivated by considering MI as a
dependence measure, we explore in this paper the alternative definition of the
MI as the expected distance between data distribution implied by the clusters
and the entire data. We extend it to incorporate cluster-wise comparisons of
implied distributions, and question the choice of the KL divergence with other
possible statistical distances.

Throughout the introduction of the Generalised Mutual Information (GEMINI),
the contributions of this paper are:

  * •

A demonstration of how the maxima of MI are not sufficient criteria for
clustering. This extends the contribution of [62] to the discrete case.

  * •

The introduction of a set of metrics called GEMINIs involving different
distances between distributions which can incorporate prior knowledge on the
geometry of the data. Some of these metrics do not require regularisations.

  * •

A highlight of the implicit selection of clusters from GEMINIs which allows to
select a relevant number of cluster during training.

  * •

A Python package using only for clustering with GEMINI: _gemclus_

##  2 Is MI a good clustering objective?

We consider in this section a dataset consisting in $N$ unlabelled samples
$\mathcal{D}=\\{\boldsymbol{x}_{i}\\}_{i=1}^{N}$. We distinguish two major use
cases of the mutual information: one where we measure the dependence between
two continuous variables, as is the case in representation learning, and one
where the random variable is discrete. In representation learning, the goal is
to construct a continuous representation $\boldsymbol{z}$ extracted from the
data $\boldsymbol{x}$ using a learnable distribution of parameters $\theta$.
In clustering, samples $\boldsymbol{x}$ are assigned to the discrete variable
$y$ through another learnable distribution.

###  2.1 Representation learning

Representation learning consists in finding high-level features
$\boldsymbol{z}_{i}$ extracted from the data $\boldsymbol{x}_{i}$ in order to
perform a _downstream task_ , e.g. clustering or classification. MI between
$\boldsymbol{x}$ and $\boldsymbol{z}$ is a common choice for learning
features[31]. However, estimating correctly MI between two random variables in
continuous domains is often intractable when
$p(\boldsymbol{x}|\boldsymbol{z})$ or $p(\boldsymbol{z}|\boldsymbol{x})$ is
unknown, thus lower bounds are preferred, e.g. variational estimators such as
MINE [4],
$\mathcal{I}_{\text{NCE}}$[63],$\mathcal{I}_{\text{BA}}$[3],$\mathcal{I}_{\text{DV}}$[18].
These bounds require more parameters: additional discriminator networks are
also trained to make a distinction between data and features issued from the
joint distribution or product of marginals. Most of these lower bounds often
present high-variance such as $\mathcal{I}_{\text{NJW}}$[50]. Poole et al.
[56] eventually bridged the gap between this high-variance estimators and the
high-bias low-variance $\mathcal{I}_{\text{NCE}}$ by introducing
$\mathcal{I}_{\alpha}$, an interpolated lower bound. Another common choice of
loss function to train features are contrastive losses such as NT-XENT [13]
where the similarity between the features $\boldsymbol{z}_{i}$ from data
$\boldsymbol{x}_{i}$ is maximised with the features $\tilde{\boldsymbol{z}}$
from a data-augmented $\tilde{\boldsymbol{x}}_{i}$ against any other features
$\boldsymbol{z}_{j}$. Recently, Do et al. [17] achieved excellent performances
in single-stage methods by highlighting the link between the
$\mathcal{I}_{\text{NCE}}$ estimator [63] and contrastive learning losses.
Representation learning therefore comes at the cost of a complex lower bound
estimator on MI, which often requires data augmentation. Moreover, it was
noticed that the MI is hardly predictive of downstream tasks [62] when the
variable $y$ is continuous, i.e. a high value of MI does not clarify whether
the discovered representations are insightful with regards to the target of
the downstream task.

###  2.2 Discriminative clustering

The MI has been first used as an objective for learning discriminative
clustering models [8]. Associated architectures went from simple logistic
regression [41] to deeper architectures [33, 37]. Beyond architecture
improvement, the MI maximisation was also carried with several
regularisations. These regularisations include penalty terms such as weight
decay [41] or Virtual Adversarial Training (VAT) [33, 49]). Data augmentation
was further used to provide invariances in clustering, as well as specific
architecture designs like auxiliary clustering heads [37]. Rewriting the MI in
terms of entropies:

$\mathcal{I}(\boldsymbol{x};y)=\mathcal{H}(y)-\mathcal{H}(y|\boldsymbol{x})$
(3)

highlights a requirement for balanced clusters, through the cluster entropy
term $\mathcal{H}(y)$. Indeed, a uniform distribution maximises the entropy.
This hints that an unregularised discrete mutual information for clustering
can possibly produce uniformly distributed clusters among samples, regardless
of how close they could be. We highlight this claim in section 2.3. As an
example of regularisation impact: maximising the MI with $\ell_{2}$ constraint
can be equivalent to a soft and regularised K-Means in a feature space [36].
In clustering, the number of clusters to find is usually not known in advance.
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 [58]. Cluster
selection through MI maximisation has been little studied in related works,
since experiments usually tasked models to find the (supervised) classes of
datasets. Furthermore, the literature diverged towards deep learning methods
focusing mainly on images, yet rarely on other type of data such as tabular
data [46].

###  2.3 Maximising the MI can lead to bad decision boundaries

Maximising the MI directly can be a poor objective: a high MI value is not
necessarily predictive of the quality of the features regarding downstream
tasks [62] when $y$ is continuous. We support a similar argument for the case
where the data $\boldsymbol{x}$ is a continuous random variable and the
cluster assignment $y$ a categorical variable. Indeed, the MI can be maximised
by setting appropriately a sharp decision boundary which partitions evenly the
data, i.e. when the distribution $p_{\theta}(y|\boldsymbol{x})$ converges to a
Dirac distribution. This reasoning can be seen in the entropy-based
formulation of the MI (Eq. 3): any sharp decision boundary minimises the
negative conditional entropy, while ensuring balanced clusters maximises the
entropy of cluster proportions. Consider for example Figure 1, where a mixture
of Gaussian distributions with equal variances is separated by a sharp
decision boundary. We highlight that both models will have the same mutual
information on condition that the misplaced decision boundary of Figure 1b
splits evenly the dataset (see Appendix A).

(a) Good decision boundary

(b) Misplaced boundary

Figure 1: Example of maximised MI for a Gaussian mixture
$\frac{1}{2}\mathcal{N}(\mu_{0},\sigma^{2})+\frac{1}{2}\mathcal{N}(\mu_{1},\sigma^{2})$.
It is clear that figure 1a presents the best decision boundary and posterior
between the two Gaussian distributions. Yet, as the posterior turns sharper,
the difference between both MIs converges to 0.

Globally, MI misses the idea in clustering that any two points close to one
another may be in the same cluster according to some chosen distance. Hence
regularisations are required to ensure this constraint. An early sketch of
these insights was mentioned by Bridle et al. [8] or Corduneanu et al. [14].
The non-predictiveness of MI was as well recently empirically highlighted by
Zhang and Boykov [70] in discrete cases. This can be also be seen as a problem
of invariance of the conditional distribution in low density areas [14].

##  3 Extending the MI to the GEMINI

Given the identified limitations of MI, we now describe the discriminative
clustering framework based on the expected distance equation of the mutual
information. We then detail the different statistical distances we can use to
extend MI to the Generalised Mutual Information (GEMINI).

###  3.1 The discriminative clustering framework for GEMINIs

We only consider two random variables: the data $\boldsymbol{x}$ which can be
continuous or discrete and the cluster assignment $y$ which is discrete.
Instead of viewing the mutual information as a dependence-seeking objective
(Eq. 1), we view it as a clustering objective that aims at separating the data
distribution given cluster assignments $p(\boldsymbol{x}|y)$ from the data
distribution $p(\boldsymbol{x})$ according to the KL divergence:

$\mathcal{I}(\boldsymbol{x};y)=\mathbb{E}_{y\sim
p(y)}\left[D_{\text{KL}}(p(\boldsymbol{x}|y)\|p(\boldsymbol{x}))\right].$ (4)

To highlight the discriminative clustering design, we explicitly do not set
any hypothesis on the data distribution by writing
$p_{\textup{data}}(\boldsymbol{x})$. The only part of the model that we design
is a conditional distribution $p_{\theta}(y|\boldsymbol{x})$ that assigns a
cluster $y$ to a sample $\boldsymbol{x}$ using the parameters $\theta$ of some
learnable function $\psi$ [47]:

$y|\boldsymbol{x}\sim\text{Categorical}(\psi_{\theta}(\boldsymbol{x})).$ (5)

This learnable function $\psi_{\theta}$ can typically be a neural network of
adequate design regarding the data, e.g. a CNN, or a logistic regression.
Consequently, the cluster proportions are controlled by $\theta$ because
$p_{\theta}(y)=\mathbb{E}[p_{\theta}(y|\boldsymbol{x})]$ and so is the
conditional distribution $p_{\theta}(\boldsymbol{x}|y)$ even though
intractable because we cannot compute the data distribution:

$p_{\theta}(\boldsymbol{x},y)=p_{\textup{data}}(\boldsymbol{x})p_{\theta}(y|\boldsymbol{x}).$
(6)

This questions how Eq. (4) can be computed. Fortunately, well-known properties
of MI can invert the distributions on which the KL divergence is computed [8,
41] via Bayes’ theorem:

$\mathcal{I}(\boldsymbol{x};y)=\mathbb{E}_{\boldsymbol{x}\sim
p_{\textup{data}}(\boldsymbol{x})}\left[D_{\text{KL}}(p_{\theta}(y|\boldsymbol{x})\|p_{\theta}(y))\right],$
(7)

which is possible to estimate. Since we highlighted earlier that the KL
divergence in the MI can lead to inappropriate decision boundaries, we are
interested in replacing it by other distances or divergences. However,
changing it in Eq. (7) would focus on the separation of cluster assignments
from the cluster proportions which may be irrelevant to the data distribution.
We rather alter Eq. (4) to clearly show that we separate data distributions
given clusters from the entire data distribution because it allows us to take
into account the data space geometry.

###  3.2 The GEMINI

####  3.2.1 Replacing the Kullback-Leibler divergence with other distances

The goal of the GEMINI is to separate data distributions according to an
arbitrary distance $D$, i.e. changing the KL divergence for another divergence
or distance in the MI. This brings the definition of our first GEMINI, the
_One-vs-All_ (OvA):

$\mathcal{I}^{\text{OvA}}_{D}(\boldsymbol{x};y)=\mathbb{E}_{y\sim
p_{\theta}(y)}\left[D(p_{\theta}(\boldsymbol{x}|y)\|p_{\textup{data}}(\boldsymbol{x}))\right],$
(8)

as it compares the distance between the distribution of a specific cluster
$p_{\theta}(\boldsymbol{x}|y)$ against the entire data distribution $p(x)$.
There exist other distances than the KL to measure how far two distributions
$p$ and $q$ are one from the other. We can make a clear distinction between
two types of distances, Csiszar’s $f$-divergences [15] and Integral
Probability Metrics (IPM) [60]. Unlike $f$-divergences, IPM-derived distances
like the Wasserstein distance or the Maximum Mean Discrepancy (MMD) [24, 27]
bring knowledge about the data throughout either a distance $c$ or a kernel
$\kappa$: these distances are geometry-aware.

####  3.2.2 $f$-divergence GEMINIs

These divergences involve a convex function
$f:\mathbb{R}^{+}\rightarrow\mathbb{R}$ such that $f(1)=0$. This function is
applied to evaluate the ratio between two distributions $p$ and $q$, as in Eq.
(9):

$D_{\text{f-div}}(p,q)=\mathbb{E}_{\boldsymbol{z}\sim
q(\boldsymbol{z})}\left[f\left(\frac{p(\boldsymbol{z})}{q(\boldsymbol{z})}\right)\right].$
(9)

We will focus on three $f$-divergences: the KL divergence, the Total Variation
(TV) distance and the squared Hellinger distance. While the KL divergence is
the usual divergence for the MI, the TV and the squared Hellinger distance
present different advantages among $f$-divergences. First of all, both of them
are bounded between 0 and 1. It is consequently easy to check when any GEMINI
using those is maximised contrarily to the MI that is bounded by the minimum
of the entropies of $\boldsymbol{x}$ and $y$ [26]. When used as distance
between data conditional distribution $p_{\theta}(\boldsymbol{x}|y)$ and data
distribution $p_{\textup{data}}(\boldsymbol{x})$, we can apply Bayes’ theorem
in order to get an estimable equation to maximise (see App. F), which only
involves cluster assignment $p_{\theta}(y|\boldsymbol{x})$ and marginals
$p_{\theta}(y)$ as summarised in Table I, generalising thus the work of Bridle
et al. [8]. Note that all $f$-divergences are maximised when the two
distributions $p$ and $q$ have disjoint supports [45]. Common $f$-divergence
like the KL, the squared Hellinger or the Pearson $\chi^{2}$ divergence,
except the total variation distance, are specific cases of the
$\alpha$-divergence subclass. The convex function of $\alpha$-divergence is
parameterized by a real number $\alpha$ with:

$f_{\alpha}(t)=\left\\{\begin{array}[]{cc}\frac{t^{\alpha}-\alpha
t+(\alpha-1)}{\alpha(\alpha-1)},&\alpha\neq 0,\alpha\neq 1,\\\
t\ln{t},&\alpha=1,\\\ -\ln{t},&\alpha=0.\end{array}\right.$ (10)

However, this class of $\alpha$-divergence is inappropriate in some cases for
clustering. Indeed, we show with Proposition 3.1 (proof in App. B) that the
maximisation of $\alpha$-divergences can lead to any clustering of the data
space with balanced clusters as the discriminative model
$p_{\theta}(y|\boldsymbol{x})$ converges to a Dirac distribution.

######  Proposition 3.1.

Let $\\{\mathcal{X}_{k}\\}_{k=1}^{K}$ a partition of $\mathcal{X}$ such that
$\mathbb{P}(\boldsymbol{x}\in\mathcal{X}_{k})=\frac{1}{K}$. Then for any
$\alpha$-divergence with $\alpha>0$, the OvA GEMINI is upper bounded by a
function which only depends on the proportions of the clusters. If the
clustering model follows a Dirac distribution:
$p_{\theta}(y=k|\boldsymbol{x})=\mathbf{1}_{[\boldsymbol{x}\in\mathcal{X}_{k}]}$,
then the upper bound is tight and the GEMINI cannot be improved.

It is worth mentioning in Proposition 3.1 that the proportions of the cluster
$p(y=k)$ do not matter for the specific case of $\alpha=2$ to achieve the
global maximum, i.e. for the Pearson $\chi^{2}$-divergence. We can infer from
Proposition 3.1 the specific Corollary 3.1 since the MI is a case of OvA
$\alpha$-divergence-GEMINI with $\alpha=1$. We conclude that MI maximisation
is a poor objective when a discriminative model can converge to a Dirac
distribution.

######  Corollary 3.1.

Let $\\{\mathcal{X}_{k}\\}_{k=1}^{K}$ a partition of $\mathcal{X}$. Then the
mutual information of a discriminative distribution $p(y|\boldsymbol{x})$ is
upper bounded by the entropy of $\boldsymbol{x}$ and the upper bound is tight
if the distribution is a Dirac model
$p(y=k|\boldsymbol{x})=\boldsymbol{1}_{[\boldsymbol{x}\in\mathcal{X}_{k}]}$.
The highest upper bound is reached when the partition is balanced.

####  3.2.3 IPM GEMINIs

The IPM is another class of distance that incorporates knowledge from the data
through a function $f$:

$D_{\text{ipm}}(p,q)=\sup_{f\in\mathcal{F}}\mathbb{E}_{\boldsymbol{z}\sim
p(\boldsymbol{z})}[f(\boldsymbol{z})]-\mathbb{E}_{\boldsymbol{z}\sim
q(\boldsymbol{z})}[f(\boldsymbol{z})],$ (11)

where $\mathcal{F}$ is a set of functions. As backpropagation through suprema
could be intractable, we choose to focus on two specific variations of the IPM
for the GEMINI: the MMD and the Wasserstein distance. Note however that not
all Wasserstein distances are IPMs and while some of our propositions are
formulated for IPMs, we consider as well the entire class of the Wasserstein
distances.

The MMD corresponds to the distance between the respective expected embedding
of samples from the distribution $p$ and the distribution $q$ in a
reproducible kernel Hilbert space (RKHS) $\mathcal{H}$:

$\text{MMD}(p\|q)=\|\mathbb{E}_{\boldsymbol{z}\sim
p(\boldsymbol{z})}[\varphi(\boldsymbol{z})]-\mathbb{E}_{\boldsymbol{z}\sim
q(\boldsymbol{z})}[\varphi(\boldsymbol{z})]\|_{\mathcal{H}},$ (12)

where $\varphi$ is the RKHS embedding. To compute this distance we can use the
kernel trick [27] by involving the kernel function
$\kappa(\boldsymbol{a},\boldsymbol{b})=\langle\varphi(\boldsymbol{a}),\varphi(\boldsymbol{b})\rangle$.
We use Bayes’ theorem to uncover a version of the MMD that can be estimated
through Monte Carlo using only the predictions $p_{\theta}(y|\boldsymbol{x})$.

The Wasserstein distance is an optimal transport distance. It corresponds to
the minimal amount of energy to transform a distribution into another
according to an energy function yielding the cost $c$ of moving the mass of a
sample from one location to another:

$\mathcal{W}_{c}^{d}(p,q)=\left(\inf_{\gamma\in\Gamma(p,q)}\mathbb{E}_{\boldsymbol{x},\boldsymbol{z}\sim\gamma(\boldsymbol{x},\boldsymbol{z})}\left[c(\boldsymbol{x},\boldsymbol{z})^{d}\right]\right)^{\frac{1}{d}},$
(13)

where $\Gamma(p,q)$ is the set of all couplings between $p$ and $q$, $c$ a
distance function in $\mathcal{X}$ and $d$ a real positive number. Computing
the Wasserstein-$d$ distance between two distributions
$p_{\theta}(\boldsymbol{x}|y=k)$ and $p_{\theta}(\boldsymbol{x})$ is difficult
in our discriminative context because we only have access to a finite set of
samples $N$. Note that in the remainder of the paper, we will focus on the
Wasserstein-1 metric. The idea of an expected Wasserstein distance was first
proposed by Harchaoui [29, Eq. 48] under the one-vs-rest name with an
additional cluster proportion factor. However, we found this additional factor
to be not grounded enough. Moreover, we can show that for the Wasserstein-1
metric the one-vs-rest Wasserstein preliminary work [29] is equivalent to the
one-vs-all Wasserstein-GEMINI. To achieve the Wasserstein-GEMINI, we instead
use approximations of the distributions with weighted sums of Diracs:

$p_{\theta}(\boldsymbol{x}|y=k)\approx\sum_{i=1}^{N}m_{i}^{k}\delta_{\boldsymbol{x}_{i}}=p_{N}^{k},\\\
\text{with}\quad
m_{i}^{k}=\frac{p_{\theta}(y=k|\boldsymbol{x}_{i})}{\sum_{j=1}^{N}p_{\theta}(y=k|\boldsymbol{x}_{j})},$
(14)

where $\delta_{\boldsymbol{x}_{i}}$ is a Dirac located on sample location
$\boldsymbol{x}_{i}\in\mathcal{X}$. For the distribution
$p_{\textup{data}}(\boldsymbol{x})$, we set all importance weights to $1/N$.
We state in Prop. 3.2 that this empirical estimate of the Wasserstein distance
converges to the correct Wasserstein distance. These importance weights are
compatible with the `emd2` function of the python optimal transport package
[20] which gracefully supports automatic differentiation. We describe other
maximisation strategies in Appendix G.

######  Proposition 3.2.

Let $p(\boldsymbol{x}|y=k_{1})$ and $p(\boldsymbol{x}|y=k_{2})$ two cluster
distributions that we empirically approximate with importance-weighed Dirac
estimators
$p_{N}^{k_{1}}=\sum_{i=1}^{N}m_{i}^{k_{1}}\delta_{\boldsymbol{x}_{i}}$, resp.
and $p_{N}^{k_{2}}=\sum_{i=1}^{N}m_{i}^{k_{2}}\delta_{\boldsymbol{x}_{i}}$.
Then the Wasserstein distance between estimates converges to the Wasserstein
distance between the cluster distributions.

We refer to Appendix F.3 for proof of convergence.

###  3.3 The One-vs-One GEMINI

We question the relevance of evaluating a distance between the distribution of
the data given a cluster assumption $p_{\theta}(\boldsymbol{x}|y)$ and the
entire data distribution $p_{\textup{data}}(\boldsymbol{x})$ when the geometry
is taken into account. We argue that it is intuitive in clustering to compare
the distribution of one cluster against the distribution of _another cluster_
rather than the data distribution. Indeed, considering the geometry of the
data space through a kernel in the case of the MMD or a distance in the case
of the Wasserstein metric implies that we can effectively measure how two
distributions are close to one another. In the formal design of the mutual
information, the distribution of each cluster $p(\boldsymbol{x}|y)$ is
compared to the complete data distribution $p(\boldsymbol{x})$. Therefore, if
one distribution of a specific cluster $p(\boldsymbol{x}|y)$ were to look
alike the data distribution $p(\boldsymbol{x})$, for example up to a constant
in some areas of the space, then its distance to the data distribution could
be 0, making it unnoticed when maximising the OvA GEMINI.

(a) OvA

(b) OvO

Figure 2: Here, 3 clusters of equal proportions from isotropic Gaussian
distributions are located in -2, 0 and 2 on the x-axis, with small covariance.
The complete data distribution hence has its expectation in 0 on the x-axis.
Consequently, maximising the OvA MMD-GEMINI with a logistic regression led to
2 clusters whereas the same model with the OvO MMD-GEMINI is able to see all 3
clusters.

Take the example of 3 distributions $\\{p(\boldsymbol{x}|y=i)\\}_{i=1}^{3}$
with respective different expectations $\\{\mu_{i}\\}_{i=1}^{3}$. We want to
separate them using the OvA MMD-GEMINI with linear kernel. The mixture of the
3 distributions creates a data distribution with expectation
$\mu=\sum_{i=1}^{3}p(y=i)\mu_{i}$. However, if the distributions satisfy that
this data expectation $\mu$ is equal to one of the sub-expectations $\mu_{i}$,
then the associated distribution $i$ will have will not provide any
information since its MMD to the data distribution is equal to 0. We
illustrate this example in figure 2.

To address this issue, we introduce the second GEMINI named _one-vs-one_ (OvO)
in which we compare cluster distributions from independently drawn cluster
assignments $y_{a}$ and $y_{b}$:

$\mathcal{I}^{\text{OvO}}_{D}(\boldsymbol{x};y)=\mathbb{E}_{y_{a},y_{b}\sim
p_{\theta}(y)}\left[D(p_{\theta}(\boldsymbol{x}|y_{a})\|p_{\theta}(\boldsymbol{x}|y_{b}))\right].$
(15)

The example of Figure 2 is tackled by the OvO GEMINI since the distance
between each pair of the 3 clusters is non-null. Conceptually, the idea of
optimising the OvO MMD-GEMINI in clustering can be found as well by França et
al. [21] who derived a regularised squared MMD in a one-vs-one setting through
restrictions to Dirac distributions. Note that for most distances, the OvO
GEMINI is an upper bound of the OvA GEMINI; proof of Proposition 3.3 in App.
C.

######  Proposition 3.3.

Let $D$ be an $f$-divergence or an IPM and $p_{\theta}(y|\boldsymbol{x})$ a
clustering distribution. Then:
$\mathcal{I}^{\text{ova}}_{D}(\boldsymbol{x},y)\leq\mathcal{I}^{\text{ovo}}_{D}(\boldsymbol{x},y)$.

In the case of binary clustering, using an IPM distance implies equality
between the OvA GEMINI and the OvO GEMINI; proof of Proposition 3.4 in App. D:

######  Proposition 3.4.

Let $D$ be an IPM and $p(y|\boldsymbol{x})$ a clustering distribution $y$
taking $K=2$ values. Then:
$\mathcal{I}^{\text{ova}}_{D}(\boldsymbol{x},y)=\mathcal{I}^{\text{ovo}}_{D}(\boldsymbol{x},y)$.

While the OvA GEMINI is maximised with Dirac clustering of the data space for
some $\alpha$-divergence, we can extend Proposition 3.1 to all $f$-divergences
for the OvO GEMINI with Proposition 3.5 (Proof in App. E). We notably conclude
that for the total variation and the squared Hellinger distance, Dirac
distributions on an even partition of the data space are the only optimal
solutions.

######  Proposition 3.5.

Let $D$ be an $f$-divergence, $p_{\theta}(y|\boldsymbol{x})$ a clustering
distribution such that $p_{\theta}(y=k)=\frac{1}{K}$. The OvO GEMINI is then
upper bounded by a function depending only on the cluster proportions. For the
upper bound to be tight, a sufficient condition is to have disjoint supports
between cluster distributions $p_{\theta}(\boldsymbol{x}|y=k)$. The condition
is necessary if the function $f$ satisfies $f(0)+g(0)<\infty$ where
$g(t)=tf\left(\frac{1}{t}\right)$ is the convex conjugate of $f$.

###  3.4 Using GEMINIs

TABLE I: Definition of the GEMINI for $f$-divergences, MMD and the Wasserstein distance. We directly write here the equation that can be optimised to train a discriminative model $p_{\theta}(y|\boldsymbol{x})$ via stochastic gradient descent since they are expectations over the data. Name | Equation
---|---
KL OvA/MI | $\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}\left[D_{\text{KL}}(p_{\theta}(y|\boldsymbol{x})\|p_{\theta}(y))\right]$
KL OvO | $\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}[D_{\text{KL}}(p_{\theta}(y|\boldsymbol{x})\|p_{\theta}(y)))+D_{\text{KL}}(p_{\theta}(y)\|p_{\theta}(y|\boldsymbol{x})))]$
Squared Hellinger OvA | $1-\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}[\mathbb{E}_{p_{\theta}(y)}[\sqrt{\frac{p_{\theta}(y|\boldsymbol{x})}{p_{\theta}(y)}}]]$
Squared Hellinger OvO | $\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}[\mathbb{V}_{p_{\theta}(y)}[\sqrt{\frac{p_{\theta}(y|\boldsymbol{x})}{p_{\theta}(y)}}]]$
TV OvA | $\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}[D_{\text{TV}}(p_{\theta}(y|\boldsymbol{x})\|p_{\theta}(y))]$
TV OvO | $\frac{1}{2}\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}[\mathbb{E}_{y_{a},y_{b}\sim p_{\theta}(y)}[|\frac{p_{\theta}(y_{a}|\boldsymbol{x})}{p_{\theta}(y_{a})}-\frac{p_{\theta}(y_{b}|\boldsymbol{x})}{p_{\theta}(y_{b})}|]]$
MMD OvA | $\mathbb{E}_{p_{\theta}(y)}\left[\mathbb{E}_{\boldsymbol{x}_{a},\boldsymbol{x}_{b}\sim p_{\textup{data}}(\boldsymbol{x})}\left[k(\boldsymbol{x}_{a},\boldsymbol{x}_{b})\left(\frac{p_{\theta}(y|\boldsymbol{x}_{a})p_{\theta}(y|\boldsymbol{x}_{b})}{p_{\theta}(y)^{2}}+1-2\frac{p_{\theta}(y|\boldsymbol{x}_{a})}{p_{\theta}(y)}\right)\right]^{\frac{1}{2}}\right]$
MMD OvO |  $\mathbb{E}_{y_{a},y_{b}\sim p_{\theta}(y)}\left[\mathbb{E}_{\boldsymbol{x}_{a},\boldsymbol{x}_{b}\sim p_{\textup{data}}(\boldsymbol{x})}\left[k(\boldsymbol{x}_{a},\boldsymbol{x}_{b})\left(\frac{p_{\theta}(y_{a}|\boldsymbol{x}_{b})p_{\theta}(y_{a}|\boldsymbol{x}_{b})}{p_{\theta}(y_{a})^{2}}\right.\right.\right.\\\ \left.\left.\left.+\frac{p_{\theta}(y_{b}|\boldsymbol{x}_{a})p_{\theta}(y_{b}|\boldsymbol{x}_{b})}{p_{\theta}(y_{b})^{2}}-2\frac{p_{\theta}(y_{a}|\boldsymbol{x}_{a})p_{\theta}(y_{b}|\boldsymbol{x}_{b})}{p_{\theta}(y_{a})p_{\theta}(y_{b})}\right)\right]^{\frac{1}{2}}\right]$
Wasserstein OvA | $\mathbb{E}_{p_{\theta}(y)}\left[\mathcal{W}_{c}\left(\sum_{i=1}^{N}m_{i}^{y}\delta_{\boldsymbol{x}_{i}},\sum_{i=1}^{N}\frac{1}{N}\delta_{\boldsymbol{x}_{i}}\right)\right]$
Wasserstein OvO | $\mathbb{E}_{y_{a},y_{b}\sim p_{\theta}(y)}\left[\mathcal{W}_{c}\left(\sum_{i=1}^{N}m_{i}^{y_{a}}\delta_{\boldsymbol{x}_{i}},\sum_{i=1}^{N}m_{i}^{y_{b}}\delta_{\boldsymbol{x}_{i}}\right)\right]$

####  3.4.1 Choosing a GEMINI

We stated in Section 3.1 that we present the GEMINI as a distance between
distributions evaluated in the data space $\mathcal{X}$ so that the distance
$D$ can take into account the topology of the data. In practice, we only
design a discriminative model $p_{\theta}(y|\boldsymbol{x})$. Thus, we need to
compute all formulas of the GEMINI through Bayes’ theorem to get equations
depending on $p_{\theta}(y|\boldsymbol{x})$ and $p_{\theta}(y)$. We summarise
the equations from all aforementioned GEMINIs in Table I (see Appendix F for
derivations). We give details on the complexity of GEMINIs in Appendix H to
help choose one. We propose as well some theoretical speed-ups in App. I. It
is also important to consider the experimental purposes and context to choose
a GEMINI. Indeed, when it is easier to design a distance than a kernel, the
Wasserstein-GEMINI is more compatible than the MMD-GEMINI and vice-versa.
Moreover, the MMD-GEMINI inherently computes expectations in a Hilbert Space
which allows computing centroids deemed representative of the clusters. This
notion of centroid is less straightforward when using the Wasserstein metric.

(a) OvA GEMINIs

(b) OvO GEMINIs

Figure 3: Mean Squared Error (log scale) of estimates with varying batch sizes
compared to the true value over a complete dataset of a 1000 samples. Each
estimate was performed 50 times per batch size and GEMINI.

####  3.4.2 Estimating a GEMINI

All GEMINIs in Table I can be estimated using Monte Carlo making them
compatible with mini-batch learning, with batch sizes of a few hundred for
large datasets similarly to prior works [33, 37, 31]. We highlight the
importance of the batch size when using GEMINIs. With the use of mini-batch
for training, the complete GEMINI is not evaluated on the entire dataset and
hence a bias may rise from the empirical estimate. This bias then has
consequences on the gradient, which in turn alters training. To illustrate
this point, we generated 1000 predictions from a Dirichlet distribution with
10 clusters. These predictions are a proxy for the output of any
discriminative model $p_{\theta}(y|\boldsymbol{x})$. We then compute the true
GEMINI on all samples before evaluating it 50 times for different randomly
sampled batches of increasing size. We report in Figure 3 the Mean Squared
Error of all GEMINIs. We see that past 200 samples for both the OvA and the
OvO models, the mean squared error is already close to or below $10^{-2}$,
except for the OvO Wasserstein- and MMD-GEMINIs. This implies an upper bound
of $10^{-2}$ for the bias of the estimates. We conclude that there is possibly
a bias in GEMINIs estimates, but it remains small enough to be negligible.

####  3.4.3 Code

The original implementation for all experiments regarding GEMINI can be found
here: https://github.com/oshillou/GEMINI. However, later works led to the
development of python package for small-scale datasets on CPU: _gemclus_ at
https://gemini-clustering.github.io/.

##  4 Experiments

For all experiments below, we report the Adjusted Rand Index (ARI) [35], a
common metric in clustering. This metric is external as it requires labels for
evaluation. It ranges from 0, when labels are independent from cluster
assignments, to 1, when labels are equivalent to cluster assignments up to
permutations. An ARI close to 0 is equivalent to the best accuracy when voting
constantly for the majority class, e.g. 10% on a balanced 10-class dataset.
Regarding the MMD- and Wasserstein-GEMINIs, we used by default a linear kernel
and the Euclidean distance unless specified otherwise. All discriminative
models are trained using the Adam optimiser [38]. We estimate a total of 450
hours of GPU consumption. (See Appendix K for the details of python packages
for experiments).

###  4.1 When the MI fails because of the modelling

(a) OvA KL (MI)

(b) OvA MMD with linear kernel

Figure 4: Clustering of a mixture of 3 Gaussian distributions with MI (left)
and a GEMINI (right) using categorical distributions. The MI does not have
insights on the data shape because of the model, and clusters points uniformly
between the 3 clusters (black dots, red triangles and blue crosses) whereas
the MMD is aware of the data shape through its kernel.

We first took the most simple discriminative clustering model, where each
cluster assignment according to the input datum follows a categorical
distribution:

$y|\boldsymbol{x}=\boldsymbol{x}_{i}\sim\text{Cat}(\theta_{i}^{1},\theta_{i}^{2},\cdots,\theta_{i}^{K}).$

We generated $N=100$ samples from a simple mixture of $K=3$ Gaussian
distributions. Each model thus only consists in $NK$ parameters to optimise.
This is a simplistic way of describing the most flexible deep neural network.
We then maximised on the one hand the OvA KL (MI) and on the other hand the
OvA MMD. Both clustering results can be seen in Figure 4. We concluded that
without any function, e.g. a neural network, to link the parameters of the
conditional distribution with $\boldsymbol{x}$, the MI struggles to find the
correct decision boundaries. Indeed, the position of $\boldsymbol{x}$ in the
2D space plays no role and the decision boundary becomes only relevant with
regards to cluster entropy maximisation: a uniform distribution between 3
clusters. However, it plays a major role in the kernel of the MMD-GEMINI thus
solving correctly the problem.

###  4.2 Resistance to outliers

TABLE II: Mean ARI (std) of a MLP fitting a mixture of 3 Gaussian and 1 Student-t multivariate distributions compared with Gaussian Mixture Models and K-Means. The model can be tasked to find either 4 or 8 clusters at best and the Student-t distribution has $\rho$=1 or 2 degrees of freedom. Bottom line presents the ARI for the maximum a posteriori of an oracle aware of all parameters of the data. Model | $\rho=2$ | $\rho=1$
---|---|---
4 clusters | 8 clusters | 4 clusters | 8 clusters
K-Means | 0.965 (0) | 0.897 (0.040) | 0 (0) | 0.657 (0.008)
GMM (full covariance) | 0.972 (0) | 0.868 (0.042) | 0 (0) | 0.610 (0.117)
GMM (diagonal covariance) | 0.973 (0) | 0.862 (0.048) | 0.024 (0.107) | 0.660 (0.097)
$\mathcal{I}_{\text{KL}}^{\text{ova}}$ | 0.883 (0.182) | 0.761 (0.101) | 0.939 (0.006) | 0.742 (0.092)
$\mathcal{I}_{\text{KL}}^{\text{ovo}}$ | 0.731 (0.140) | 0.891 (0.129) | 0.723 (0.114) | 0.755 (0.163)
$\mathcal{I}_{\text{H}^{2}}^{\text{ova}}$ | 0.923 (0.125) | 0.959 (0.043) | 0.906 (0.103) | 0.86 (0.087)
$\mathcal{I}_{\text{H}^{2}}^{\text{ovo}}$ | 0.926 (0.112) | 0.951 (0.059) | 0.858 (0.143) | 0.887 (0.074)
$\mathcal{I}_{\text{TV}}^{\text{ova}}$ | 0.940 (0.097) | 0.973 (0.004) | 0.904 (0.104) | 0.925 (0.103)
$\mathcal{I}_{\text{TV}}^{\text{ovo}}$ | 0.971 (0.005) | 0.620 (0.053) | 0.938 (0.005) | 0.595 (0.055)
$\mathcal{I}_{\text{MMD}}^{\text{ova}}$ | 0.953 (0.060) | 0.940 (0.033) | 0.922 (0.004) | 0.908 (0.016)
$\mathcal{I}_{\text{MMD}}^{\text{ovo}}$ | 0.968 (0.001) | 0.771 (0.071) | 0.921 (0.007) | 0.849 (0.048)
$\mathcal{I}_{\mathcal{W}}^{\text{ova}}$ | 0.897 (0.096) | 0.896 (0.021) | 0.915 (0.131) | 0.889 (0.051)
$\mathcal{I}_{\mathcal{W}}^{\text{ovo}}$ | 0.970 (0.002) | 0.803 (0.067) | 0.922 (0.006) | 0.817 (0.042)
Oracle | 0.991 | 0.989

(a) OvA KL (MI) Entropy Map

(b) OvO MMD Entropy Map

(c) OvO Wasserstein Entropy Map

Figure 5: Entropy maps of the predictions of each MLP trained using a GEMINI
or the MI. The bottom-left distribution (yellow) is a Student-t distribution
with 1 degree of freedom that produces samples far from the origin. The Rényi
entropy of prediction is highlighted from lowest (blue background) to highest
(red background). MI on the left has the most confident predictions overall
and the smallest uncertainty around the decision boundary, i.e. high entropy
variations.

To prove the strength of using neural networks for clustering trained with
GEMINI, we introduced extreme samples in Gaussian mixtures by replacing a
Gaussian distribution with a Student-t distribution for which the degree of
freedom $\rho$ is small. We fixed $K=4$ clusters, 3 being drawn from
multivariate Gaussian distributions and the last one from a multivariate
Student-t distribution in 2 dimensions for visualisation purposes with 1
degree of freedom or 2. Thus, the Student-t distribution produces samples that
can be perceived as outliers regarding a Gaussian mixture owing to its heavy
tail.

Each cluster distribution is centered around a mean $\mu_{i}$ which proximity
is controlled by a scalar $\alpha$. For simplicity, all covariance matrices
are the identity scaled by a scalar $\sigma$. We define:

$\displaystyle\mu_{1}$ $\displaystyle=[\alpha,\alpha],$ $\displaystyle\mu_{2}$
$\displaystyle=[\alpha,-\alpha],$ $\displaystyle\mu_{3}$
$\displaystyle=[-\alpha,\alpha],$ $\displaystyle\mu_{4}$
$\displaystyle=[-\alpha,-\alpha].$

To sample from a multivariate Student-t distribution, we first draw samples
$\boldsymbol{x}$ from a centered multivariate Gaussian distribution. We then
sample another variable $u$ from a $\chi^{2}$-distribution using the degrees
of freedom $\rho$ as parameter. Finally, $\boldsymbol{x}$ is multiplied by
$\sqrt{\frac{\rho}{u}}$, yielding samples from the Student-t distribution.

We report the ARIs of Multi-Layered Perceptron (MLP) trained 20 times with
GEMINIs in Table II. The presence of "outliers" leads K-Means and Gaussian
Mixture models to fail at grasping the 4 distributions when tring to find 4
clusters. Meanwhile, GEMINIs perform better. Note that the MMD and
Wasserstein-GEMINI present lower standard deviation for high scores compared
to $f$-divergence GEMINIs. We attribute these performances to both the MLP
that tries to find separating hyperplanes in the data space and the absence of
hypotheses regarding the data. Moreover, as mentioned in section 2.3, the
usual MI is best maximised when its decision boundary presents little entropy
$\mathcal{H}(p_{\theta}(y|\boldsymbol{x}))$. As neural networks can be
overconfident [28], MI is likely to yield overconfident clustering by
minimizing the conditional entropy. We highlight such behaviour in Figure 5
where the Rényi entropy [57] associated to each sample in the MI (Figure 5a)
is much lower, if not 0, compared to OvO MMD and OvO Wasserstein (figures 5b
and 5c). We conclude that Wasserstein- and MMD-GEMINIs train neural networks
not to be overconfident, hence yielding more moderate distributions
$p_{\theta}(y|\boldsymbol{x})$.

###  4.3 Leveraging a manifold geometry

(a) $\mathcal{I}^{\text{ova}}_{\text{kl}}$ for 2 clusters

(b) $\mathcal{I}^{\text{ova}}_{\text{kl}}$ for 5 clusters

(c) $\mathcal{I}^{\text{ovo}}_{\mathcal{W}}$ for 2 clusters

(d) $\mathcal{I}^{\text{ova}}_{\mathcal{W}}$ for 5 clusters

Figure 6: Fitting hand-generated moons using the GEMINI on top of an MLP for
different amount of clusters. The Wasserstein-ovo model with 5 clusters
eventually found 4 clusters.

We highlighted that MI can be maximised without requiring to find the suitable
decision boundary. Here, we show how the provided distance to the OvO
Wasserstein-GEMINI can leverage appropriate clustering when we have a good a
priori on the data.

The cluster assignment is drawn according to a Bernoulli distribution with
parameter 0.5. The points are then sampled using a uniformly distributed angle
in $[0,\pi]$. Axis symmetry is applied depending on the clusters. All points
are distributed at the same radius $\rho$ from some circle centre before
adding some Gaussian noise. The samples then undergo some offset so that both
moons are not linearly separable.

We generated a dataset consisting of two facing moons on which we trained a
MLP using either the MI or the OvO Wasserstein-GEMINI. To construct a distance
$c$ for the Wasserstein distance, we derived a distance from the Floyd-
Warshall algorithm [66, 59] on a sparse graph describing neighborhoods of
samples. This distance describes how many neighbors are in between two
samples, further details are provided in appendix J. We report the different
decision boundaries in Figure 6. We observe that the insight on the
neighborhood provided by our distance $c$ helped the MLP to converge to the
correct solution with an appropriate decision boundary unlike the MI. Note
that the usual Euclidean distance in the Wasserstein metric would have
converged to a solution similar to the MI. Indeed for 2 clusters, the optimal
transport plan has a larger value, using a distribution similar to Figure 6a,
than in Figure 6c. This toy example shows how an insightful metric provided to
the Wasserstein distance in GEMINIs can lead to correct decision boundaries
while only designing a discriminative distribution
$p_{\theta}(y|\boldsymbol{x})$ and a distance $c$.

In addition, we highlight an interesting behaviour of all GEMINIs. During
optimisation, it is possible that the model converges to using fewer clusters
than the number to find. For example in Figure 6, for 5 clusters, the model
can converge to 4 balanced clusters and 1 empty cluster (Figure 6d) unlike MI
that produced 5 misplaced clusters (Figure 6b). Indeed, the entropy on the
cluster proportion in the MI forces to use the maximum number of clusters.

###  4.4 Fitting MNIST

TABLE III: ARI for deep neural network trained with GEMINIs on MNIST for 500 epochs. Models were trained either with either 10 clusters to find or 15. We indicate in parentheses the number of used clusters by the model after training. GEMINI | 10 clusters | 15 clusters
---|---|---
MLP | LeNet-5 | MLP | LeNet-5
KL | OvA | 0.320 (10) | 0.138 (8) | 0.271 (15) | 0.136 (12)
OvO | 0.348 (7) | 0.123 (4) | 0.333 (8) | 0.104 (4)
Squared Hellinger | OvA | 0.301 (10) | 0.207 (6) | 0.224 (13) | 0.162 (7)
OvO | 0.287 (10) | 0.161 (6) | 0.305 (13) | 0.157 (7)
TV | OvA | 0.299 (10) | 0.171 (6) | 0.277 (15) | 0.140 (6)
OvO | 0.422 (10) | 0.161 (9) | 0.330 (15) | 0.182 (14)
MMD | OvA | 0.373 (10) | 0.382 (10) | 0.345 (15) | 0.381 (15)
OvO | 0.361 (10) | 0.373 (10) | 0.364 (15) | 0.379 (15)
Wasserstein | OvA |  0.471 (10) |  0.463 (10) | 0.390 (15) |  0.446 (11)
OvO | 0.450 (10) | 0.383 (10) |  0.415 (15) | 0.414 (15)
K-Means | 0.367 | 0.385

We trained a neural network using either MI or GEMINIs. Following Hu et al.
[33], we first tried with a MLP with one single hidden layer of dimension
1200. To further illustrate the robustness of the method and its adaptability
to other architectures, we also experimented using a LeNet-5 architecture [42]
since it is adequate to the MNIST dataset. We report our results in Table III.
Since we are dealing with a clustering method, we may not know the number of
clusters a priori in a dataset. The only thing that can be said about MNIST is
that there are _at least_ 10 clusters, one per digit. Indeed, writings of
digits could differ leading to more clusters than the number of classes. That
is why we further tested the same method with 15 clusters to find in Table
III. We first see that the scores of the MMD and Wasserstein GEMINIs are
greater than the MI. We also observe that no $f$-divergence-GEMINI always
yield best ARIs. Nonetheless, we observe better performances in the case of
the TV GEMINIs owing to its bounded gradient. This results in controlled
stepsize when doing gradient descent contrarily to KL- and squared Hellinger-
GEMINIs. Notice that the change of architecture from a MLP to a LeNet-5
unexpectedly halves the scores for the $f$-divergences. We believe this drop
is due to the change of notion of neighborhood implied by the network
architecture.

###  4.5 Number of non-empty clusters and architecture

(a) MLP

(b) LeNet5

Figure 7: Distributions of the ARI scores given a number of non-empty clusters
after 100 epochs of training on MNIST on two different architectures.

We repeat our previous experiment on the MNIST dataset from Sec. 4.4. We
choose this time to get 50 clusters at best for both the MI and the MMD GEMINI
and train the models for 100 epochs. We repeat the experiment 20 times per
model and plot the resulting scores in figures 7a and 7b. We did not choose to
test with the Wasserstein GEMINI because its complexity implies a long
training time for 50 clusters, as explained in App. H. We first observe in
Fig. 7 that the MMD-GEMINI with linear kernel has a tendency to exploit more
clusters than the MI. The model converges to approximately 30 clusters in the
case of the MLP and 25 for the LeNet-5 model with less variance. We can
further observe that for all metrics the choice of architecture impacted the
number of non-empty clusters after training. Indeed, by playing a key role in
the decision boundary shape, the architecture may limit the number of clusters
to be found: the MLP can draw more complex boundaries compared to the LeNet5
model. Moreover, we suppose that the cluster selection behaviour of GEMINI may
be due to optimisation processes. Indeed, we optimise estimators of the GEMINI
rather than the exact GEMINI. Finally, Fig. 7 also confirms from Table. III
the stability of the MMD-GEMINI regarding the ARI despite the change of
architecture whereas the MI is affected and shows poor performance with the
LeNet-5 architecture.

###  4.6 Cifar10 clustering using a SIMCLR-derived kernel

TABLE IV: ARI score of models trained for 200 epochs on CIFAR10 with different architectures using GEMINIs. The kernel for the MMD is either a linear kernel or the dot product between features extracted from a pretrained SIMCLR model. Both the Euclidean norm between images and SIMCLR features are considered for the Wasserstein metric. We report the ARI of related works when not using data augmentation for comparison.*: scores reported from Li et al., (2021) Architecture | No kernel | Linear kernel / $\ell_{2}$ norm | SIMCLR [13]
---|---|---|---
$\mathcal{I}_{\text{KL}}^{\text{ova}}$ | $\mathcal{I}_{\text{MMD}}^{\text{ova}}$ | $\mathcal{I}_{\text{MMD}}^{\text{ovo}}$ | $\mathcal{I}_{\mathcal{W}}^{\text{ova}}$ | $\mathcal{I}_{\mathcal{W}}^{\text{ovo}}$ | $\mathcal{I}_{\text{MMD}}^{\text{ova}}$ | $\mathcal{I}_{\text{MMD}}^{\text{ovo}}$ | $\mathcal{I}_{\mathcal{W}}^{\text{ova}}$ | $\mathcal{I}_{\mathcal{W}}^{\text{ovo}}$
LeNet-5 | 0.026 | 0.049 | 0.048 | 0.043 | 0.041 | 0.157 | 0.145 | 0.079 | 0.138
Resnet-18 | 0.008 | 0.047 | 0.044 | 0.037 | 0.036 | 0.122 | 0.145 | 0.052 | 0.080
KMeans (images / SIMCLR) | 0.041 | 0.147 | CC [43] | 0.030
IDFD [61] | 0.060 | JULE [69]* | 0.138

To further illustrate the benefits of the kernel or distance provided to
GEMINIs, we continue the same experiment as in section 4.4. However, we focus
this time on the CIFAR10 dataset. As improved distance, we chose a linear
kernel and $\ell_{2}$ norm between features extracted from a pretrained SIMCLR
model [13]. We provide results for two different architectures: LeNet-5 and
ResNet-18 both trained from scratch on raw images, the latter being a common
choice of models in deep clustering literature [64, 61]. We report the results
in Table IV and provide the baseline of MI. We also write the baselines from
related works when not using data augmentations to make a fair comparison.
Indeed, models trained with GEMINIs do not use data augmentation: only the
architecture and the kernel or distance function in the data space plays a
role. We observe here that the choice of kernel or distance can be critical in
GEMINIs. Indeed, while the Euclidean norm between images does not provide
insights on how images of cats and dogs are far as shown by K-Means, features
derived from SIMCLR carry much more insight on the proximity of images. This
shows that the performances of GEMINIs depend on the quality of distance
functions. Interestingly, we observe that for the Resnet-18 using SIMCLR
features to guide GEMINIs was not as successful as it has been on the LeNet-5.
We believe that the ability of this network to draw any decision boundary
makes it equivalent to a categorical distribution model as in Sec. 4.1.
Finally, to the best of our knowledge, we are the first to train from scratch
a standard discriminative neural network on CIFAR raw images without using
labels or direct data augmentations, while getting sensible clustering
results. However, other recent methods achieve best scores using data
augmentations which we do not [53].

###  4.7 A practical application with Graph Neural Networks: the Enron email
dataset

We focus in this experiment on the clustering of nodes in a graph representing
email interaction between individuals in the Enron dataset (available at
https://www.cs.cmu.edu/~./enron/. This famous company was filed for bankruptcy
on the 2nd of December 2001 following an investigation for fraud by the
Securities and Exchange Commision (SEC). Following Bouveyron et al. [7], we
focus on exchange of emails in the Enron corporation between the 1st of
September 2021 and the 31st of December 2001, which corresponds to the peak
period at which the company collapsed. We represent the dataset as a graph
where each node corresponds to an employee and each edge represents the
sending of at least one email. We choose to let the edges unweighted because
the number of emails sent between two persons is not necessarily reflexive of
how two persons can be close to each other. After filtering nodes that do not
communicate between September and December, the graph comprises 141 nodes and
872 symmetric edges. In order to use the Wasserstein metric, we choose as a
distance the all-pairs-shortest path as already used in Section 4.3 and
Appendix J. Due to the necessity of using a _symmetric_ distance for the
Wasserstein metric, we let the graph undirected. Thus, an edge between two
persons represent the exchange of at least one email anyhow.

To cluster the nodes of the graph, we adopt a simple Graph Convolution Network
(GCN) [39] inspired by Kipf et al. [39] and Liang et al.[44] with a hidden
size of dimension 64 and 10 clusters to find at best [7]. We vary the number
of hidden layers from 1 to 3. All models were run 30 times. We perform
clustering by maximising the OvO Wasserstein during 1000 epochs with a
learning rate of $2\times 10^{-3}$ for the Adam optimiser. Indeed, with a long
training time, we allow the model to find more clusters despite a stabilised
GEMINI. We also experimented using the MI with the same models and
hyperparameters. We eventually select the final model using the highest GEMINI
value for each different depth of GCN.

Similarly, we run 30 times as well two competitors with a number of clusters
to find ranging from 2 to 10: the LPM model [32] and the Deep LPM model [44]
which are generative methods based on the assumption of a latent position of
the nodes in the graph determining their interaction. Their respective best
models were selected according to the lowest bayesian information criterion
and the highest evidence lower bound. For Deep LPM, we used the architecture
proposed by the authors in [44] with a one-hidden-layer network.

(a) GEMINI complete graph (b) GEMINI summary graph

(c) Deep LPM complete graph (d) Deep LPM summary graph

Figure 8: Fruchterman Reingold representation of the Enron email interaction
graph. Nodes are coloured according to clusters. The summary graph is a
cluster-wise average of the positions of the nodes with edges as strong as the
number of interactions between two clusters.

(a) GEMINI clustering

(b) LPM clustering

(c) Deep LPM clustering

Figure 9: Interaction matrices: each black cell encodes an edge. Nodes were
reorganised according to their clustering for each model.

(a) MI with 1 hidden layer
PAC = 0.27

(b) MI with 3 hidden layers
PAC=0.36

(c) GEMINI with 1 hidden layer
PAC=0.13

(d) GEMINI with 3 hidden layers
PAC=0.22

Figure 10: CDFs of consensus between all clusterings produced by the models on the Enron Email dataset. The indicated PAC score is the difference of cdf between the quantiles 10% and 90%. A lower PAC score is better and highlights more consistent clustering assignments. TABLE V: Average ARI scores between 30 GEMINI-trained models and the best Deep LPM and LPM clustering according to ELBO criterion. $H$ represents the number of hidden layers in the trained model. GEMINI | $H$ | LPM | Deep LPM
---|---|---|---
MI | 1 | 0.47 (0.08) | 0.31 (0.10)
2 | 0.31 (0.07) | 0.17 (0.09)
3 | 0.29 (0.04) | 0.16 (0.05)
OvO Wasserstein | 1 | 0.58 (0.04) | 0.25 (0.03)
2 | 0.54 (0.06) | 0.22 (0.03)
3 | 0.49 (0.06) | 0.21 (0.04)

We start by showing the highest Wasserstein-GEMINI clustering in Figure 8
where the graph nodes are positioned according to the Fruchterman Reingold
algorithm [22].

When we look at the interaction matrices of the best models in Figure 9, we
can observe that the GEMINI clustering applied to graph using the all pair
shortest path distance yields dense clusters where nodes intensively connect
with each others (Figure 9a). The LPM model found fewer clusters that are as
well densely connected while the Deep LPM found 6 clusters including one
densely connected and another one which contains multiple nodes sparsely
connected. Interestingly, GEMINI managed to isolate graph nodes that act as
hub e.g. the 9th cluster in Fig. 9a with star-shaped interactions while Deep
LPM mixes hubs in its 3rd cluster in Figure 9c. A potential explanation for
this difference is that LPM models seek to cluster nodes based on supposedly
close latent representations whereas the GEMINI clustering uses the
Wasserstein distance, hence taking into account the flow of information
passing through each graph node. In Table V, we compared the average ARI
between our 30 GEMINI models with the best selected LPM and Deep LPM
clustering. It appears indeed that GEMINI models have a stronger ARI with the
LPM model than with the Deep LPM, as the former concentrated on dense
clusters. Interestingly, we can notice in Table V that the MI models with one
hidden layer are able to produce also satisfying results with an ARI close to
or better than the ARI between GEMINI and LPM methods. However, when the
models turn deeper, the performances of MI drop whereas the ARI between the
Wasserstein-GEMINI decreases more slowly.

To further compare the performances of these models, we chose to evaluate
their proportions of ambiguous clusters (PAC score) [71]. The PAC score is
evaluated using two steps: we first build a matrix where each entry $i,j$
contains the proportion of times two samples $i$ and $j$ where clustered
together by some model, then arrange these proportions to build a cdf which
highlights for given quantiles the proportions of paired samples that can be
clustered together. The PAC score corresponds to the difference of cdf between
two given quantiles, commonly 10% and 90%. Through Figure 10, we can see that
the models trained with the Wasserstein GEMINI have a lower PAC score compared
to MI-trained models which highlights a more consistent clustering assignment
through all 30 runs. We can further observe that for both objective functions,
a deeper model leads to higher PAC score which we can explain by the
difficulty to repeat the same decision boundary with deep models. Eventually,
we may conclude that while the MI may have competitive results with shallow
models compared to GEMINI and Deep LPM, it is unable to repeat a consistent
clustering as illustrated by a high PAC score.

##  5 Conclusions

We highlighted that the choice of distance at the core of MI can alter the
performances of deep learning models when used as an objective for a deep
discriminative clustering. We first showed that MI maximisation does not
necessarily reflect the best decision boundary in clustering when the
clustering model converges to a Dirac distribution. We introduced the GEMINI,
a method which only needs the specification of a neural network and a kernel
or distance in the data space. Moreover, we showed how the notion of
neighborhood built by the neural network can affect the clustering, especially
for MI. To the best of our knowledge, this is the first method that trains
single-stage neural networks from scratch using neither data augmentations nor
regularisations, yet achieving good clustering performances. We emphasised
that GEMINIs are only searching for a maximum number of clusters: after
convergence some may be empty. However, we do not have insights to explain
this convergence which is part of future work. Finally, we introduced several
versions of GEMINIs and would encourage the OvA MMD or OvA Wasserstein as a
default choice, since it proves to both incorporate knowledge from the data
using a kernel or distance while remaining the less complex than OvO MMD and
OvO Wasserstein in time and memory. OvO versions could be privileged for fine-
tuning steps. As follow-up, we focused on the introduction of sparsity in
GEMINI clustering for feature selection [51]. Future works could focus on the
joint learning of distances or kernels [67] while maximising the the GEMINI to
get both meaningful clustering and metrics in the data space. We will also
investigate why sometimes after convergence some clusters end up empty.

#### Acknowledgements

This work has been supported by the French government, through the 3IA Côte
d’Azur, Investment in the Future, project managed by the National Research
Agency (ANR) with the reference number ANR-19-P3IA-0002. We would also like to
thank the France Canada Research Fund (FFCR) for their contribution to the
project. This work was partly supported by the Fonds de recherche du Québec –
Santé (FRQS) and the Health-Data Hub, through the joint project AORTIC
STENOSIS . The authors are grateful to the OPAL infrastructure from Université
Côte d’Azur for providing resources and support.

## References

  * [1] M. Arjovsky, S. Chintala, and L. Bottou.  Wasserstein Generative Adversarial Networks.  In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 214–223. PMLR, Aug. 2017\.
  * [2] S. Arora, R. Ge, Y. Liang, T. Ma, and Y. Zhang.  Generalization and Equilibrium in Generative Adversarial Nets (GANs).  In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 224–232. PMLR, 06–11 Aug 2017.
  * [3] D. Barber and F. V. Agakov.  The im algorithm: A variational approach to information maximization.  In NIPS, 2003.
  * [4] M. I. Belghazi, A. Baratin, S. Rajeshwar, S. Ozair, Y. Bengio, A. Courville, and D. Hjelm.  Mutual Information Neural Estimation.  In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 531–540. PMLR, 10–15 Jul 2018.
  * [5] P. Billingsley.  Convergence of Probability Measures.  John Wiley & Sons, 2013.
  * [6] C. Bouveyron, G. Celeux, T. B. Murphy, and A. 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.
  * [7] C. Bouveyron, P. Latouche, and R. Zreik.  The stochastic topic block model for the clustering of vertices in networks with textual edges.  Statistics and Computing, 28(1):11–31, 2018.
  * [8] J. Bridle, A. Heading, and D. 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.
  * [9] U. Caglar.  Divergence And Entropy Inequalities For Log Concave Functions.  PhD thesis, Case Western Reserve University, 2014.
  * [10] M. Caron, P. Bojanowski, A. Joulin, and M. Douze.  Deep Clustering for Unsupervised Learning of Visual Features.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 132–149, 2018.
  * [11] M. Caron, I. Misra, J. Mairal, P. Goyal, P. Bojanowski, and A. Joulin.  Unsupervised Learning of Visual Features by Contrasting Cluster Assignments.  In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9912–9924. Curran Associates, Inc., 2020.
  * [12] J. Chang, L. Wang, G. Meng, S. Xiang, and C. Pan.  Deep Adaptive Image Clustering.  In 2017 IEEE International Conference on Computer Vision (ICCV), pages 5880–5888, 2017.
  * [13] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton.  A Simple Framework for Contrastive Learning of Visual Representations.  In International Conference on Machine Learning, pages 1597–1607. PMLR, 2020.
  * [14] A. Corduneanu and T. Jaakkola.  On Information Regularization.  In Proceedings of the Nineteenth conference on Uncertainty in Artificial Intelligence, pages 151–158, 2002.
  * [15] I. Csiszár.  Information-Type Measures of Difference of Probability Distributions and Indirect Observation.  studia scientiarum Mathematicarum Hungarica, 2:229–318, 1967.
  * [16] Z. Dang, C. Deng, X. Yang, K. Wei, and H. Huang.  Nearest Neighbor Matching for Deep Clustering.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13693–13702, 2021.
  * [17] K. Do, T. Tran, and S. Venkatesh.  Clustering by Maximizing Mutual Information Across Views.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9928–9938, 2021.
  * [18] M. D. Donsker and S. S. Varadhan.  Asymptotic evaluation of certain markov process expectations for large time. iv.  Communications on pure and applied mathematics, 36(2):183–212, 1983\.
  * [19] W. Falcon et al.  Pytorch Lightning.  GitHub. Note: https://github.com/PyTorchLightning/pytorch-lightning, 3, 2019.
  * [20] R. Flamary, N. Courty, A. Gramfort, M. Z. Alaya, A. Boisbunon, S. Chambon, L. Chapel, A. Corenflos, K. Fatras, N. Fournier, L. Gautheron, N. T. Gayraud, H. Janati, A. Rakotomamonjy, I. Redko, A. Rolet, A. Schutz, V. Seguy, D. J. Sutherland, R. Tavenard, A. Tong, and T. Vayer.  Pot: Python Optimal Transport.  Journal of Machine Learning Research, 22(78):1–8, 2021.
  * [21] G. França, M. L. Rizzo, and J. T. Vogelstein.  Kernel k-groups via hartigan’s method.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(12):4411–4425, 2020.
  * [22] T. M. Fruchterman and E. M. Reingold.  Graph drawing by force-directed placement.  Software: Practice and experience, 21(11):1129–1164, 1991.
  * [23] K. Ghasedi Dizaji, A. Herandi, C. Deng, W. Cai, and H. Huang.  Deep clustering via joint convolutional autoencoder embedding and relative entropy minimization.  In Proceedings of the IEEE International Conference on Computer Vision, pages 5736–5745, 2017.
  * [24] T. Gneiting and A. E. Raftery.  Strictly proper scoring rules, prediction, and estimation.  Journal of the American statistical Association, 102(477):359–378, 2007.
  * [25] H. Gouk, E. Frank, B. Pfahringer, and M. J. Cree.  Regularisation of Neural Networks by Enforcing Lipschitz Continuity.  Machine Learning, 110(2):393–416, Feb. 2021.
  * [26] R. M. Gray and P. C. Shields.  The Maximum Mutual Information between Two Random Processes.  Information and Control, 33(4):273–280, 1977.
  * [27] A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola.  A Kernel Two-Sample Test.  The Journal of Machine Learning Research, 13(1):723–773, 2012.  Publisher: JMLR. org.
  * [28] C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger.  On Calibration of Modern Neural Networks.  In International Conference on Machine Learning, pages 1321–1330. PMLR, 2017.
  * [29] W. Harchaoui.  Learning representations using neural networks and optimal transport.  PhD thesis, Université Paris Cité, 2020.
  * [30] C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N. J. Smith, R. Kern, M. Picus, S. Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. del Río, M. Wiebe, P. Peterson, P. Gérard-Marchant, K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T. E. Oliphant.  Array programming with NumPy.  Nature, 585(7825):357–362, Sept. 2020.
  * [31] R. D. Hjelm, A. Fedorov, S. Lavoie-Marchildon, K. Grewal, P. Bachman, A. Trischler, and Y. Bengio.  Learning deep representations by mutual information estimation and maximization.  In International Conference on Learning Representations, 2019\.
  * [32] P. D. Hoff, A. E. Raftery, and M. S. Handcock.  Latent space approaches to social network analysis.  Journal of the American Statistical Association, 97(460):1090–1098, 2002.
  * [33] W. Hu, T. Miyato, S. Tokui, E. Matsumoto, and M. Sugiyama.  Learning Discrete Representations via Information Maximizing Self-Augmented Training.  In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1558–1567. PMLR, Aug. 2017\.
  * [34] J. Huang, S. Gong, and X. 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.
  * [35] L. Hubert and P. Arabie.  Comparing partitions.  Journal of classification, 2(1):193–218, 1985.
  * [36] M. Jabi, M. Pedersoli, A. Mitiche, and I. B. Ayed.  Deep clustering: On the link between discriminative models and K-means.  IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 1–1, 2019.
  * [37] X. Ji, J. F. Henriques, and A. 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.
  * [38] D. P. Kingma and J. Ba.  Adam: A Method for Stochastic Optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [39] T. N. Kipf and M. Welling.  Variational graph auto-encoders.  arXiv preprint arXiv:1611.07308, 2016.
  * [40] J. 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.
  * [41] A. Krause, P. Perona, and R. 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.
  * [42] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [43] Y. Li, P. Hu, Z. Liu, D. Peng, J. T. Zhou, and X. Peng.  Contrastive Clustering.  In 2021 AAAI Conference on Artificial Intelligence (AAAI), 2021.
  * [44] D. Liang, M. Corneli, C. Bouveyron, and P. Latouche.  Clustering by deep latent position model with graph convolutional network.  2022\.
  * [45] F. Liese and I. Vajda.  On divergences and informations in statistics and information theory.  IEEE Transactions on Information Theory, 52(10):4394–4412, 2006\.
  * [46] E. Min, X. Guo, Q. Liu, G. Zhang, J. Cui, and J. Long.  A Survey of Clustering With Deep Learning: From the Perspective of Network Architecture.  IEEE Access, PP:1–1, 2018.
  * [47] T. Minka.  Discriminative models, not discriminative training.  Technical report, Technical Report MSR-TR-2005-144, Microsoft Research, 2005.
  * [48] T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida.  Spectral Normalization for Generative Adversarial Networks.  In International Conference on Learning Representations, 2018\.
  * [49] T. Miyato, S.-i. Maeda, M. Koyama, and S. 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.  Publisher: IEEE.
  * [50] X. Nguyen, M. J. Wainwright, and M. I. Jordan.  Estimating divergence functionals and the likelihood ratio by convex risk minimization.  IEEE Transactions on Information Theory, 56(11):5847–5861, 2010\.
  * [51] L. Ohl, P.-A. Mattei, C. Bouveyron, M. Leclercq, A. Droit, and F. Precioso.  Sparse gemini for joint discriminative clustering and feature selection.  arXiv preprint arXiv:2302.03391, 2023.
  * [52] A. B. Owen.  Monte Carlo theory, methods and examples.  Stanford, 2013.
  * [53] S. Park, S. Han, S. Kim, D. Kim, S. Park, S. Hong, and M. 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.
  * [54] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala.  Pytorch: An Imperative Style, High-Performance Deep Learning Library.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024–8035. Curran Associates, Inc., 2019.
  * [55] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine Learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.
  * [56] B. Poole, S. Ozair, A. Van Den Oord, A. Alemi, and G. Tucker.  On Variational Bounds of Mutual Information.  In K. Chaudhuri and R. 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.
  * [57] A. Rényi.  On measures of entropy and information.  In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, volume 4, pages 547–562. University of California Press, 1961.
  * [58] M. Ronen, S. E. Finder, and O. 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.
  * [59] B. Roy.  Transitivité et connexité.  Comptes Rendus Hebdomadaires Des Séances De L’Académie Des Sciences, 249(2):216–218, 1959.
  * [60] B. K. Sriperumbudur, K. Fukumizu, A. Gretton, B. Schölkopf, and G. R. Lanckriet.  On integral probability metrics,$\phi$-divergences and binary classification.  arXiv preprint arXiv:0901.2698, 2009.
  * [61] Y. Tao, K. Takagi, and K. Nakata.  Clustering-friendly representation learning via instance discrimination and feature decorrelation.  In International Conference on Learning Representations, 2021.
  * [62] M. Tschannen, J. Djolonga, P. K. Rubenstein, S. Gelly, and M. Lucic.  On Mutual Information Maximization for Representation Learning.  In International Conference on Learning Representations, 2020.
  * [63] A. Van den Oord, Y. Li, and O. Vinyals.  Representation Learning with Contrastive Predictive Coding.  arXiv e-prints, pages arXiv–1807, 2018.
  * [64] W. Van Gansbeke, S. Vandenhende, S. Georgoulis, M. Proesmans, and L. Van Gool.  Scan: Learning to Classify Images without Labels.  In European Conference on Computer Vision, pages 268–285. Springer, 2020.
  * [65] C. Villani.  Optimal transport: old and new, volume 338.  Springer, 2009.
  * [66] S. Warshall.  A Theorem on Boolean Matrices.  Journal of the ACM (JACM), 9(1):11–12, 1962.
  * [67] C. Wu, Z. Khan, S. Ioannidis, and J. G. Dy.  Deep kernel learning for clustering.  In Proceedings of the 2020 SIAM International Conference on Data Mining, pages 640–648. SIAM, 2020.
  * [68] J. Xie, R. Girshick, and A. Farhadi.  Unsupervised Deep Embedding for Clustering Analysis.  In M. F. Balcan and K. 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.
  * [69] J. Yang, D. Parikh, and D. Batra.  Joint Unsupervised Learning of Deep Representations and Image Clusters.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5147–5156, 2016.
  * [70] Z. Zhang and Y. Boykov.  Revisiting discriminative entropy clustering and its relation to k-means.  arXiv preprint arXiv:2301.11405, 2023.
  * [71] Y. Senbabaoğlu, G. Michailidis, and J. Z. Li.  Critical limitations of consensus clustering in class discovery.  Scientific reports, 4(1):6207, 2014.

|  Louis Ohl PhD Student at the Université Côte d’Azur and the Université
Laval from 2021 to 2024 and computer science graduate from the INSA Lyon and
KTH Royal Institute of Technology in 2021. His project mainly focuses on
clustering and the choices of the decision boundaries to discriminatively
separate samples with applications in medical research including
identification of phenogroups in aortic stenosis.
---|---
|  Pierre-Alexandre Mattei is a research scientist at Inria, in the Maasai
team located in Sophia-Antipolis (France). He graduated from Ecole Normale
Supérieure de Cachan in 2014, and received a PhD in applied mathematics from
Université Paris Cité in 2017. His research interests mostly revolve around
problems with latent variables: deep generative modelling, Bayesian inference,
clustering, missing data.
---|---
Charles Bouveyron Professor of Statistics at Université Côte d’Azur, Nice,
France. He holds a Chair on Artificial Intelligence and is the Director of the
Institut 3IA Côte d’Azur and head of the research team MAASAI from INRIA. His
research interests include statistical learning for clustering, classification
and regression in high dimension, statistical learning on networks applied to
different domains (medicine, image analysis, astrophysics, humanities…)
---
|  Warith Harchaoui holds a Ph.D. in Applied Mathematics and is deeply engaged
in the intersection of artificial intelligence (AI) and pattern analysis. He
commenced his academic journey at École Normale Supérieure de Cachan, where he
received his M.Sc. in 2008. His initial forays into the industry revolved
around Computer Vision applications in startups and global enterprises.
Harchaoui extended his academic pursuits at École Normale Supérieure de Paris,
contributing to research at the globally recognized Willow laboratory. His
scholarly interests encompass a range of topics within image, sound, video,
and text processing, a domain where he has consistently leveraged mathematical
models for innovative solutions. From 2014 to 2020, Dr. Harchaoui also
embraced a corporate role in Data Science, working with Oscaro.com the
e-commerce leader in the automotive parts sector. Balancing industry demands
with academic rigor, he completed his Ph.D. research between 2016 and 2020.
Today, Dr. Harchaoui serves at Jellysmack since 2021, where he combines his
expertise to help internet video creators through every stage from content
production, editing to social media promotion.
---|---
|  Mickaël Leclercq PhD in Computer Science from McGill University, Canada, in
2016. Since then, he’s been working as a research associate in the
computational biology laboratory of Prof. Droit, researcher at the CHU de
Québec - Université Laval. His role is to develop and supervise bioinformatics
research projects with an artificial intelligence component. He also
contributes to the organization and coordination of the laboratory’s research
activities and supervises the work of students and young research
professionals. He actively participates in the long-term vision of the
laboratory’s research themes as well as in the development of grant
applications and manuscripts.
---|---
|  Arnaud Droit PhD graduate in 2007 in bioinformatics from Université Laval,
Canada. Since 2012, he has been a Professor at Université Laval (Québec,
Canada) and leads a bioinformatics and proteomics laboratory at the CHU de
Québec. His research focuses on robust bioinformatics approaches, advanced
statistical methods, and machine/deep learning strategies to extract
information relevant to medical research from large biological datasets. Many
of his projects are related to cancer research, where the aim is to discover
biomarker signatures associated with various clinical outcomes. His expertise
is essential to many research sectors requiring bioinformatics, so he built a
large network of international collaborations, including the private sector.
---|---
Frederic Precioso Full Professor at the Université Côte d’Azur from 2011 and
Affiliated Professor at Université Laval from 2022, his research interests
cover active learning, foundation models, hybrid learning combining symbolic
and non-symbolic models, clustering, MLOps, applied to different domains
(health, biology, multimedia, autonomous vehicles, biodiversity).
---

##  Appendix A Demonstration of the convergence to 0 of the MI for a Gaussian
Mixture

###  A.1 Models definition

Let us consider a mixture of two Gaussian distributions, both with different
means $\mu_{0}$ and $\mu_{1}$, s.t. $\mu_{0}<\mu_{1}$ and of same standard
deviation $\sigma$:

$p(x|y=0)=\mathcal{N}(x|\mu_{0},\sigma^{2}),p(x|y=1)=\mathcal{N}(x|\mu_{1},\sigma^{2}),$

where $y$ is the cluster assignment. We take balanced clusters proportions,
i.e. $p(y=0)=p(y=1)=\frac{1}{2}$. This first model is the basis that generated
the complete dataset $p(x)$. When performing clustering with our
discriminative model, we are not aware of the distribution. Consequently: we
create other models. We want to compute the difference of mutual information
between two decision boundaries that discriminative models $p_{\theta}(y|x)$
may yield.

We define two decision boundaries: one which splits evenly the data space
called $p_{A}$ and another which splits it on a closed set $p_{B}$:

$p_{A}(y=1|x)=\left\\{\begin{array}[]{c
c}1-\epsilon&x>\frac{\mu_{1}-\mu_{0}}{2}\\\
\epsilon&\text{otherwise}\end{array}\right.,$ (16)

$p_{B}(y=1|x)=\left\\{\begin{array}[]{c c}1-\epsilon&x\in[\mu_{0},\mu_{1}]\\\
\epsilon&\text{otherwise}\end{array}\right..$ (17)

Our goal is to show that both models $p_{A}$ and $p_{B}$ will converge to the
same value of mutual information as $\epsilon$ converges to 0.

###  A.2 Computing cluster proportions

####  A.2.1 Cluster proportion of the correct decision boundary

To compute the cluster proportions, we estimate with samples $x$ from the
distribution $p_{\text{data}}(x)$. Since we are aware for this demonstration
of the true nature of the data distribution, we can use $p(x)$ for sampling.
Consequently, we can compute the two marginals:

$\displaystyle p_{A}(y=1)$
$\displaystyle=\int_{\mathcal{X}}p(x)p_{A}(y=1|x)dx,$
$\displaystyle=\int_{-\infty}^{\frac{\mu_{1}-\mu_{0}}{2}}p(x)\epsilon
dx+\int_{\frac{\mu_{1}-\mu_{0}}{2}}^{+\infty}p(x)(1-\epsilon)dx,$
$\displaystyle=\epsilon\left(\int_{-\infty}^{\frac{\mu_{1}-\mu_{0}}{2}}p(x)dx\right)+(1-\epsilon)\left(\int_{\frac{\mu_{1}-\mu_{0}}{2}}^{+\infty}p(x)dx\right),$
$\displaystyle=\frac{1}{2}.$

####  A.2.2 Cluster proportion of the misplaced decision boundary

For the misplaced decision boundary, the marginal is different:

$\begin{split}p_{B}(y=1)&=\int_{\mathcal{X}}p(x)p_{B}(y=1|x)dx,\\\
&=\epsilon\left(\int_{-\infty}^{\mu_{0}}p(x)dx+\int_{\mu_{1}}^{+\infty}p(x)dx\right)+(1-\epsilon)\int_{\mu_{0}}^{\mu_{1}}p(x)dx,\\\
&=\epsilon\left(1-\int_{\mu_{0}}^{\mu_{1}}p(x)dx\right)+(1-\epsilon)\int_{\mu_{0}}^{\mu_{1}}p(x)dx.\end{split}$

Here, we simply introduce a new variable named $\beta$ that will be a shortcut
for noting the proportion of data between $\mu_{0}$ and $\mu_{1}$:

$\beta=\int_{\mu_{0}}^{\mu_{1}}p(x)dx.$

And so can we simply write the cluster proportion of decision boundary model B
as:

$p_{B}(y=1)=\epsilon(1-\beta)+(1-\epsilon)\beta,$

Leading to the summary of proportions in Table VI. For convenience, we will
write the proportions of model B using the shortcuts:

$\pi_{B}=p_{B}(y=1)=\epsilon+\beta(1-2\epsilon),$
$\bar{\pi}_{B}=p_{B}(y=0)=1-\epsilon-\beta(1-2\epsilon).$

TABLE VI: Proportions of clusters for models A and B $\mathcal{M}$ | A | B
---|---|---
$p_{\mathcal{M}}(y=1)$ | $\frac{1}{2}$ | $\epsilon+\beta(1-2\epsilon)$
$p_{\mathcal{M}}(y=0)$ | $\frac{1}{2}$ | $1-\epsilon-\beta(1-2\epsilon)$

###  A.3 Computing the KL divergences

####  A.3.1 Correct decision boundary

We first start by computing the Kullback-Leibler divergence for some arbitrary
value of $x\in\mathbb{R}$:

$D_{\text{KL}}(p_{A}(y|x)||p_{A}(y))=\sum_{i=0}^{1}p_{A}(y=i|x)\log{\frac{p_{A}(y=i|x)}{p_{A}(y=i)}}.$

We now need to detail the specific cases, for the value of $p(y=i|x)$ is
dependent on $x$. We start $\forall x<\frac{\mu_{1}-\mu_{0}}{2}$:

$\displaystyle D_{\text{KL}}(p_{A}(y|x)||p_{A}(y))$
$\displaystyle=p_{A}(y=0|x)\log{\frac{p_{A}(y=0|x)}{\frac{1}{2}}}+p_{A}(y=1|x)\log{\frac{p_{A}(y=1|x)}{\frac{1}{2}}},$
$\displaystyle=(1-\epsilon)\log{2(1-\epsilon)}+\epsilon\log{2\epsilon}.$

The opposite case, $\forall x\geq\frac{\mu_{1}-\mu_{0}}{2}$ yields:

$\displaystyle D_{\text{KL}}(p_{A}(y|x)||p_{A}(y))$
$\displaystyle=p_{A}(y=0|x)\log{\frac{p_{A}(y=0|x)}{\frac{1}{2}}}+p_{A}(y=1|x)\log{\frac{p_{A}(y=1|x)}{\frac{1}{2}}},$
$\displaystyle=\epsilon\log{2\epsilon}+(1-\epsilon)\log{2(1-\epsilon)}.$

Since both cases are equal, we can write down:

$D_{\text{KL}}(p_{A}(y|x)||p_{A}(y))=\epsilon\log{2\epsilon}+(1-\epsilon)\log{2(1-\epsilon)},\forall
x\in\mathbb{R}.$ (18)

####  A.3.2 Misplaced boundary

We proceed to the same detailing of the Kullback-Leibler divergence
computation for the misplaced decision boundary. We start with the set
$x\in[\mu_{0},\mu_{1}]$:

$\displaystyle D_{\text{KL}}(p_{B}(y|x)||p_{B}(y))$
$\displaystyle=p_{B}(y=0|x)\log{\frac{p_{B}(y=0|x)}{p_{B}(y=0)}}+p_{B}(y=1|x)\log{\frac{p_{B}(y=1|x)}{p_{B}(y=1)}},$
$\displaystyle=\epsilon\log{\frac{\epsilon}{\bar{\pi}_{B}}}+(1-\epsilon)\log{\frac{1-\epsilon}{\pi_{B}}}.$

When $x$ is out of this set, the divergence becomes:

$\displaystyle D_{\text{KL}}(p_{B}(y|x)||p_{B}(y))$
$\displaystyle=p_{B}(y=0|x)\log{\frac{p_{B}(y=0|x)}{p_{B}(y=0)}}+p_{B}(y=1|x)\log{\frac{p_{B}(y=1|x)}{p_{B}(y=1)}},$
$\displaystyle=(1-\epsilon)\log{\frac{1-\epsilon}{\bar{\pi}_{B}}}+\epsilon\log{\frac{\epsilon}{\pi_{B}}}.$

To fuse the two results, we will write the KL divergence as such:

$D_{\text{KL}}(p_{B}(y|x)||p_{B}(y))=\epsilon\log{\epsilon}+(1-\epsilon)\log(1-\epsilon)-C(x),\forall
x\in\mathbb{R},$ (19)

where $C(x)$ is a constant term depending on $x$ defined by:

$C(x)=\left\\{\begin{array}[]{c
c}\epsilon\log{\bar{\pi}_{B}}+(1-\epsilon)\log{\pi_{B}}&x\in[\mu_{0},\mu_{1}]\\\
\epsilon\log{\pi_{B}}+(1-\epsilon)\log{\bar{\pi}_{B}}&x\in\mathbb{R}\setminus[\mu_{0},\mu_{1}]\\\
\end{array}.\right.$

For simplicity of later writings, we will shorten the notations by:

$C(x)=\left\\{\begin{array}[]{c c}\alpha_{1}&x\in[\mu_{0},\mu_{1}]\\\
\alpha_{0}&x\in\mathbb{R}\setminus[\mu_{0},\mu_{1}]\end{array}\right..$

###  A.4 Evaluating the mutual information

####  A.4.1 Correct decision boundary

We inject the value of the Kullback-Leibler divergence from Eq. (18) inside an
expectation performed over the data distribution $p_{\text{data}}(x)$:

$\displaystyle\mathcal{I}_{A}(x;y)$ $\displaystyle=\mathbb{E}_{x\sim
p_{\text{data}}(x)}\left[D_{\text{KL}}(p_{A}(y|x)||p_{A}(y))\right],$ (20)
$\displaystyle=\int_{\mathcal{X}}p(x)\left(\epsilon\log(2\epsilon)+(1-\epsilon)\log(2(1-\epsilon))\right)dx,$
(21) $\displaystyle=\epsilon\log(2\epsilon)+(1-\epsilon)\log(2(1-\epsilon)).$
(22)

Since the KL divergence was independent of $x$, we could leave the constant
outside of the integral which is equal to 1.

We can assess the coherence of Eq. (22) since its limit as $\epsilon$
approaches 0 is $\log 2$. In terms of bits, this is the same as saying that
the information on $X$ directly gives us information on the $Y$ of the
cluster.

####  A.4.2 Odd decision boundary

We inject the value of the KL divergence from Eq. (19) inside the expectation
of the mutual information:

$\displaystyle\mathcal{I}_{B}(x;y)$ $\displaystyle=\mathbb{E}_{x\sim
p_{\text{data}}(x)}\left[D_{\text{KL}}(p_{B}(y|x)||p_{B}(y))\right],$
$\displaystyle=\int_{\mathcal{X}}p(x)\left(\epsilon\log\epsilon+(1-\epsilon)\log(1-\epsilon)-C(x)\right),dx$
$\displaystyle=\epsilon\log\epsilon+(1-\epsilon)\log(1-\epsilon)-\int_{\mathcal{X}}p(x)C(x)dx.$

The first terms are constant with respect to $x$ and the integral of $p(x)$
over $\mathcal{X}$ adds up to 1. We finally need to detail the expectation of
the constant $C(x)$ from Eq. (A.3.2):

$\displaystyle\mathbb{E}_{x}[C(x)]$
$\displaystyle=\int_{-\infty}^{\mu_{0}}C(x)p(x)dx+\int_{\mu_{0}}^{\mu_{1}}C(x)p(x)dx+\int_{\mu_{1}}^{+\infty}C(x)p(x)dx,$
$\displaystyle=\alpha_{0}\left(\int_{-\infty}^{\mu_{0}}p(x)dx+\int_{\mu_{1}}^{+\infty}p(x)dx\right)+\alpha_{1}\int_{\mu_{0}}^{\mu_{1}}p(x)dx,$
$\displaystyle=\alpha_{0}(1-\beta)+\alpha_{1}\beta.$

This can be further improved by unfolding the description of $\alpha_{0}$ and
$\alpha_{1}$ from Eq. (A.3.2):

$\displaystyle\alpha_{0}(1-\beta)+\beta\alpha_{1}$
$\displaystyle=\alpha_{0}+\beta(\alpha_{1}-\alpha_{0}),$
$\displaystyle=\epsilon\log{\pi_{B}}+(1-\epsilon)\log{\bar{\pi}_{B}}+\beta\left[\epsilon\log{\bar{\pi}_{B}}+(1-\epsilon)\log{\pi_{B}}\right.$
$\displaystyle\quad\left.-\epsilon\log{\pi_{B}}-(1-\epsilon)\log{\bar{\pi}_{B}}\right],$
$\displaystyle=\left[1-\epsilon+\beta\epsilon-\beta+\beta\epsilon\right]\log{\bar{\pi}_{B}}+\left[\epsilon+\beta-\beta\epsilon-\beta\epsilon\right]\log{\pi_{B}},$
$\displaystyle=\log{\bar{\pi}_{B}}+\left[2\beta\epsilon-\beta-\epsilon\right]\log{\frac{\bar{\pi}_{B}}{\pi_{B}}}.$

We can finally write down the mutual information for the model B:

$\mathcal{I}_{B}(x;y)=\epsilon\log{\epsilon}+(1-\epsilon)\log(1-\epsilon)-\log{\bar{\pi}_{B}}-\left[2\beta\epsilon-\beta-\epsilon\right]\log{\frac{\bar{\pi}_{B}}{\pi_{B}}}.$

###  A.5 Differences of mutual information

Now that we have the exact value of both mutual informations, we can compute
their differences:

$\displaystyle\Delta_{\mathcal{I}}$
$\displaystyle=\mathcal{I}_{A}(x;y)-\mathcal{I}_{B}(x;y),$
$\displaystyle=\epsilon\log(2\epsilon)+(1-\epsilon)\log(2(1-\epsilon))-\epsilon\log{\epsilon}-(1-\epsilon)\log(1-\epsilon)$
$\displaystyle\quad+\log{\bar{\pi}_{B}}+\left[2\beta\epsilon-\beta-\epsilon\right]\log{\frac{\bar{\pi}_{B}}{\pi_{B}}},$
$\displaystyle=\epsilon\log{2}+(1-\epsilon)\log
2+\log{\bar{\pi}_{B}}+\left[2\beta\epsilon-\beta-\epsilon\right]\log{\frac{\bar{\pi}_{B}}{\pi_{B}}}.$

We then deduce how the difference of mutual information evolves as the
decision boundary becomes sharper, i.e. when $\epsilon$ approaches 0:

$\lim_{\epsilon\rightarrow
0}\Delta_{\mathcal{I}}=\log{2}+\log{\bar{\pi}_{B}}-\beta\log{\frac{\bar{\pi}_{B}}{\pi_{B}}}.$

However, the cluster proportions by B $\pi_{B}$ also take a different value as
$\epsilon$ approaches 0. Recalling Eq. (17):

$\lim_{\epsilon\rightarrow 0}p_{B}(y=1)=\beta,\lim_{\epsilon\rightarrow
0}p_{B}(y=0)=1-\beta.$

And finally can we write that:

$\begin{split}\lim_{\epsilon\rightarrow
0}\Delta_{\mathcal{I}}&=\log{2}+\log(1-\beta)-\beta\log\frac{1-\beta}{\beta},\\\
&=\log{2}+(1-\beta)\log(1-\beta)+\beta\log{\beta},\\\
&=\log{2}-\mathcal{H}(\beta).\end{split}$

(a) Differences of MI between models A and B

(b) Gaussian mixture distribution $p(x)$ with proportion $\beta$ in between
the two means $\mu_{0}$ and $\mu_{1}$

Figure 11: Value of the mutual information for the two models splitting a
Gaussian mixture depending on the distance between the two means $\mu_{0}$ and
$\mu_{1}$ of the two generating Gaussian distributions. We estimate the MI by
computing it 50 times on 1000 samples drawn from the Gaussian mixture.

To conclude, as the decision boundaries turn sharper, i.e. when $\epsilon$
approaches 0, the difference of mutual information between the two models is
controlled by the entropy of proportion of data $\beta$ between the two means
$\mu_{0}$ and $\mu_{1}$. We know that for binary entropies, the optimum is
reached for $\beta=0.5$. In other words having $\mu_{0}$ and $\mu_{1}$ distant
enough to ensure balance of proportions between the two clusters of model B
leads to a difference of mutual information equal to 0. We experimentally
highlight this convergence in Figure 11 where we compute the mutual
information of models A and B as the distance between the two means $\mu_{0}$
and $\mu_{1}$ increases in the Gaussian distribution mixture.

##  Appendix B Proof of Proposition 3.1

For the sake of clarity, we will use the notations $\pi_{k}\equiv p(y=k)$
during the demonstration.

###  B.1 Modelisation of the conditional distribution

We will consider two types of models. The first one is the _generic_
clustering model, where the cluster assignment follows a categorical
distribution:

$y|\boldsymbol{x}\sim\text{Cat}(\psi_{\theta}(\boldsymbol{x})),$

where $\psi_{\theta}:\mathcal{X}\rightarrow\Delta_{K}$ is a learnable function
of parameters $\theta$ and $\Delta_{K}$ is a $K$-simplex.

The second model is a Dirac distribution where the data space $\mathcal{X}$ is
divided into a partition $\mathcal{X}_{k},\forall k\in\\{1,\cdots,K\\}$:

$p(y=k|\boldsymbol{x})=\boldsymbol{1}_{[\boldsymbol{x}\in\mathcal{X}_{k}]},$

with $\boldsymbol{1}$ the indicator function. This is simply a sub-case of the
generic model.

For both models, we consider that clusters are not empty and that the model is
not degenerate, i.e. $\pi_{k}\in]0,1[\forall k\in\\{1,K\\}$.

###  B.2 Value of the GEMINI OvA and upper bounds

We first unfold the OvA GEMINI for the generic model and
$\alpha\in\mathbb{R}\setminus\\{0,1\\}$:

$\displaystyle\mathcal{I}^{\text{ova}}_{D_{\alpha}}(\boldsymbol{x};y)$
$\displaystyle=\mathbb{E}_{y\sim p(y)}\left[\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}\left[f_{\alpha}\left(\frac{p(\boldsymbol{x}|y)}{p(\boldsymbol{x})}\right)\right]\right],$
$\displaystyle=\sum_{k=1}^{K}\pi_{k}\int_{\mathcal{X}}p(\boldsymbol{x})\left(\frac{p(\boldsymbol{x}|y=k)^{\alpha}p(\boldsymbol{x})^{-\alpha}}{\alpha(\alpha-1)}-\frac{p(\boldsymbol{x}|y=k)p(\boldsymbol{x})^{-1}}{\alpha-1}+\frac{1}{\alpha}\right)d\boldsymbol{x},$
$\displaystyle=\sum_{k=1}^{K}\pi_{k}\int_{\mathcal{X}}\left(\frac{p(\boldsymbol{x})p(y=k|\boldsymbol{x})^{\alpha}}{\pi_{k}^{\alpha}\alpha(\alpha-1)}-\frac{p(\boldsymbol{x}|y=k)}{\alpha-1}+\frac{p(\boldsymbol{x})}{\alpha}\right)d\boldsymbol{x}.$

After distributing the factor $p(\boldsymbol{x})$ in the integral, we can
notice that the two last terms will be summed to 1, up to a factor depending
on $\alpha$.

$\displaystyle\mathcal{I}^{\text{ova}}_{D_{\alpha}}(\boldsymbol{x};y)$
$\displaystyle=\sum_{k=1}^{K}\pi_{k}\left(\frac{1}{\alpha}-\frac{1}{\alpha-1}+\frac{1}{\pi_{k}^{\alpha}\alpha(\alpha-1)}\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}\left[p(y=k|\boldsymbol{x})^{\alpha}\right]\right)$
$\displaystyle=\frac{-1}{\alpha(\alpha-1)}+\frac{1}{\alpha(\alpha-1)}\sum_{k=1}^{K}\pi_{k}^{1-\alpha}\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}\left[p(y=k|\boldsymbol{x})^{\alpha}\right],$
$\displaystyle=\left(\alpha(\alpha-1)\right)^{\alpha}\left[-1+\sum_{k=1}^{K}\pi_{k}^{1-\alpha}\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}\left[p(y=k|\boldsymbol{x})^{\alpha}\right]\right].$

Since we face a categorical distribution, we can affirm that
$p(y|\boldsymbol{x})\in[0,1]$. Therefore, depending on the value of $\alpha$,
we have either $p(y=k|\boldsymbol{x})^{\alpha}\in[1,\infty[$ if $\alpha$ is
negative, and $p(y=k|\boldsymbol{x})\in[0,1]$ for $\alpha$ positive. We now
inspect these different cases.

###  B.3 Case of $\alpha\in]1,+\infty[$

The upper bound we can get on the expectation involves the inequality
$p(y=k|\boldsymbol{x})^{\alpha}\leq p(y=k|\boldsymbol{x})$. Owing to the
linearity of the expectation, we can affirm that:

$\displaystyle\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}\left[p(y=k|\boldsymbol{x})^{\alpha}\right]$
$\displaystyle\leq\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}[p(y=k|\boldsymbol{x})],$ $\displaystyle\leq\pi_{k}.$

This allows us to derive the following upper bound on the OvA GEMINI:

$\displaystyle\mathcal{I}^{\text{ova}}_{D_{\alpha}}(\boldsymbol{x};y)$
$\displaystyle=\left(\alpha(\alpha-1)\right)^{-1}\left[-1+\sum_{k=1}^{K}\pi_{k}^{1-\alpha}\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}\left[p(y=k|\boldsymbol{x})^{\alpha}\right]\right],$
$\displaystyle\leq\left(\alpha(\alpha-1)\right)^{-1}\left[-1+\sum_{k=1}^{K}\pi_{k}^{2-\alpha}\right],$
$\displaystyle\leq\mathcal{B}_{]1,+\infty[}(\pi_{1},\cdots,\pi_{K}).$

The upper bound $\mathcal{B}_{]1,+\infty[}(\pi_{1},\cdots,\pi_{K})$ is a
convex function that is invariant to permutations of $\pi_{k}$. Interestingly,
this upper bound only depends on the proportions of the clusters. Its
maximimum is reached when $\pi_{k}=K^{-1}$. However, any solution is
acceptable for the special case of $\alpha=2$, i.e. the Pearson
$\chi^{2}$-divergence. In this case, the upper bound is a constant:
$\mathcal{B}^{+}_{2}=\frac{K-1}{2}$. In this situation, the proportions of the
clusters do not matter. Only getting a Dirac model is sufficient to maximise
the OvA GEMINI.

We can further conclude that the bound is tight when considering a Dirac model
since $1^{\alpha}=1$ and $0^{\alpha}=0$, leading to:

$\displaystyle\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}\left[\boldsymbol{1}_{\left[\boldsymbol{x}\in\mathcal{X}_{k}\right]}^{\alpha}\right]$
$\displaystyle=\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}\left[\boldsymbol{1}_{\left[\boldsymbol{x}\in\mathcal{X}_{k}\right]}\right],$
$\displaystyle=\pi_{k}.$

And so do we conclude:

$\displaystyle\mathcal{I}^{\text{ova}}_{D_{\alpha}}(\boldsymbol{x};y)$
$\displaystyle=\left(\alpha(\alpha-1)\right)^{-1}\left[-1+\sum_{k=1}^{K}\pi_{k}^{1-\alpha}\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}\left[p(y=k|\boldsymbol{x})^{\alpha}\right]\right],$
$\displaystyle=\left(\alpha(\alpha-1)\right)^{-1}\left[-1+\sum_{k=1}^{K}\pi_{k}^{2-\alpha}\right],$
$\displaystyle=\mathcal{B}_{]1,+\infty[}(\pi_{1},\cdots,\pi_{K})$

###  B.4 Case of a $\alpha\in]0,1[$

In this case, the front factor $(\alpha(\alpha-1))^{-1}$ is negative. Thus, we
are interested in minimising the second term and finding the lower bound. We
can already infer:

$\displaystyle p(y=k|\boldsymbol{x})$ $\displaystyle\leq
p(y=k|\boldsymbol{x})^{\alpha}$ $\displaystyle\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}[p(y=k|\boldsymbol{x})]$
$\displaystyle\leq\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}\left[p(y=k|\boldsymbol{x})^{\alpha}\right]$
$\displaystyle\pi_{k}$ $\displaystyle\leq\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}\left[p(y=k|\boldsymbol{x})^{\alpha}\right].$

This lower bound is tight for a Dirac model. We can finally compute for the
OvA GEMINI that:

$\displaystyle\mathcal{I}^{\text{ova}}_{D_{\alpha}}(\boldsymbol{x};y)$
$\displaystyle=\left(\alpha(\alpha-1)\right)^{-1}\left[-1+\sum_{k=1}^{K}\pi_{k}^{1-\alpha}\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}\left[p(y=k|\boldsymbol{x})^{\alpha}\right]\right],$
$\displaystyle\leq\left(\alpha(\alpha-1)\right)^{-1}\left[-1+\sum_{k=1}^{K}\pi_{k}^{2-\alpha}\right],$
$\displaystyle\leq\mathcal{B}_{]0,1[}.$

Hence, we conclude that
$\mathcal{B}_{]0,1[}=\mathcal{B}_{]1,+\infty[}=\mathcal{B}_{\mathbb{R}^{+*}\setminus\\{1\\}}$.
In both cases, using a Dirac model implies that the OvA GEMINI reaches its
upper bound.

###  B.5 Case of a negative $\alpha$

The upper bound of the OvA GEMINI in this case is the infinity. Indeed, taking
the example of the Dirac model is sufficient to consider regions of the data
space $\mathcal{X}$ where the clustering distribution has no support. Thus,
the expectation is undefined, or rather drifts towards infinity.

###  B.6 Specific case of $\alpha=1$, the KL divergence

In this case, we need to start the computations all over again using the
definition $f(t)=t\log{t}$. Indeed, we can skip the term $-t+1$ since it does
not affect the value of an $f$-divergence, i.e. for any convex function $f$
s.t. $f(1)=0$ and for any real constant $c$:

$D_{f(t)}(p\|q)=D_{f(t)+c(t-1)}(p\|q).$

We thus get:

$\displaystyle\mathcal{I}_{D_{1}}^{\text{ova}}(\boldsymbol{x};y)$
$\displaystyle=\mathbb{E}_{y\sim p(y)}\left[\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}\left[\frac{p(\boldsymbol{x}|y=k)}{p(\boldsymbol{x})}\log\frac{p(\boldsymbol{x}|y=k)}{p(\boldsymbol{x})}\right]\right],$
$\displaystyle=\sum_{k=1}^{K}\pi_{k}\int_{\mathcal{X}}p(\boldsymbol{x}|y=k)\log\left(\frac{p(\boldsymbol{x}|y=k)}{p(\boldsymbol{x})}\right)d\boldsymbol{x},$
$\displaystyle=\sum_{k=1}^{K}\int_{\mathcal{X}}p(y=k|\boldsymbol{x})p(\boldsymbol{x})\log\left(\frac{p(y=k|\boldsymbol{x})}{\pi_{k}}\right)d\boldsymbol{x}.$

We can then separate the log term to make appear the two different entropies
contributing to the mutual information:

$\displaystyle\mathcal{I}_{D_{1}}^{\text{ova}}(\boldsymbol{x};y)$
$\displaystyle=\sum_{k=1}^{K}\int_{\mathcal{X}}p(y=k|\boldsymbol{x})p(\boldsymbol{x})\log(p(y=k|\boldsymbol{x}))d\boldsymbol{x}-\log{\pi_{k}}\int_{\mathcal{X}}p(y=k|\boldsymbol{x})p(\boldsymbol{x})d\boldsymbol{x},$
$\displaystyle=\sum_{k=1}^{K}\int_{\mathcal{X}}p(y=k|\boldsymbol{x})p(\boldsymbol{x})\log(p(y=k|\boldsymbol{x}))d\boldsymbol{x}-\pi_{k}\log\pi_{k}$

We find once again an upper bound on the integral depending on
$p(y|\boldsymbol{x})$. We know that the function $g:t\mapsto t\log{t}$ is
convex and below 0 for $t\in[0,1]$. Hence:

$p(y=k|\boldsymbol{x})\log{p(y=k|\boldsymbol{x})}\leq 0,$

with strict equality iff $p(y=k|\boldsymbol{x})\in\\{0,1\\}$. This implies
that the Dirac model maximises the left integral. We deduce the upper bound of
the mutual information:

$\displaystyle\mathcal{I}_{D_{1}}^{\text{ova}}(\boldsymbol{x};y)$
$\displaystyle=\sum_{k=1}^{K}\int_{\mathcal{X}}p(y=k|\boldsymbol{x})p(\boldsymbol{x})\log(p(y=k|\boldsymbol{x}))d\boldsymbol{x}-\pi_{k}\log\pi_{k},$
$\displaystyle\leq\sum_{k=1}^{K}-\pi_{k}\log{\pi_{k}},$
$\displaystyle\leq\mathcal{B}_{1}.$

This shows that the cluster proportion entropy is the upper bound of the
mutual information. It is reached for any Dirac model.

###  B.7 Last subcase: the null alpha

In this case, the $\alpha$-divergence is defined by the function
$f(t)=-\log{t}$. Let us derive again the OvA GEMINI:

$\displaystyle\mathcal{I}_{D_{0}}^{\text{ova}}(\boldsymbol{x};y)$
$\displaystyle=\mathbb{E}_{y\sim p(y)}\left[\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}\left[-\log\frac{p(\boldsymbol{x}|y=k)}{p(\boldsymbol{x})}\right]\right],$
$\displaystyle=-\sum_{k=1}^{K}\pi_{k}\int_{\mathcal{X}}p(\boldsymbol{x})\log\left(\frac{p(\boldsymbol{x}|y=k)}{p(\boldsymbol{x})}\right)d\boldsymbol{x},$
$\displaystyle=-\sum_{k=1}^{K}\pi_{k}\int_{\mathcal{X}}p(\boldsymbol{x})\log\left(\frac{p(y=k|\boldsymbol{x})}{\pi_{k}}\right)d\boldsymbol{x}.$

We expand again the logarithm and compute the integral over constant terms
factorised by $p(\boldsymbol{x})$:

$\displaystyle\mathcal{I}_{D_{0}}^{\text{ova}}(\boldsymbol{x};y)$
$\displaystyle=\sum_{k=1}^{K}\pi_{k}\log{\pi_{k}}-\pi_{k}\int_{\mathcal{X}}p(\boldsymbol{x})\log{p(y=k|\boldsymbol{x})}d\boldsymbol{x}.$

Now we can see that this OvA GEMINI may converge to infinity. Indeed, for the
example of the Dirac model, we evaluate the integral with terms worth
$\lim_{t\rightarrow 0}\log{t}$. We cannot conclude on the upper bounds of this
case.

###  B.8 Maximal upper bound

We have shown so far that for $\alpha>0$, we can derive two different upper
bounds that only depend on the proportions of the clusters $\pi_{k}$. These
upper bounds can be reached by Dirac model of type
$p(y=k|\boldsymbol{x})=\boldsymbol{1}_{[\boldsymbol{x}\in\mathcal{X}_{k}]}$.

We can now question for the two upper bounds,
$\mathcal{B}_{\mathbb{R}^{+*}\setminus\\{1\\}}$ and $\mathcal{B}_{1}$ what are
the optimal cluster proportions $\pi_{k}$. By adding a Lagrangian constraint
to enforce $\sum_{k=1}^{K}\pi_{k}=1$ in each upper bound, we can show that the
maximal upper bound is reached iff $\pi_{k}=K^{-1}\forall k$. This concludes
our proof.

##  Appendix C Proof of Proposition 3.3

Let us consider the value of the OvO GEMINI when the distance $D$ is an
$f$-divergence or an IPM.

###  C.1 Demonstration for $f$-divergences

We first need to highlight that $f$-divergences come with a conjugate convex
function $g$. This conjugate enables the inversion of the arguments of the
$f$-divergence:

$D_{f}(p\|q)=D_{g}(q\|p),$

for any distributions $p$ and $q$. We can use this trick to revert first the
$f$-divergence between the distribution $p(y=k|\boldsymbol{x})$ and
$p(\boldsymbol{x})$:

$D_{f}(p(\boldsymbol{x}|y=k)\|p(\boldsymbol{x}))=D_{g}(p(\boldsymbol{x})\|p(\boldsymbol{x}|y=k)).$

We then write $p(\boldsymbol{x})$ as a sum marginalising the $y$ variable.
Using the convexity of the function $g$, we get a weighted upper bound of this
divergence:

$\displaystyle D_{g}(p(\boldsymbol{x})\|p(\boldsymbol{x}|y=k))$
$\displaystyle=D_{g}\left(\sum_{k^{\prime}=1}^{K}p(y=k^{\prime})p(\boldsymbol{x}|y=k^{\prime})\|\left(\sum_{k^{\prime}=1}^{K}p(y=k^{\prime})\right)p(\boldsymbol{x}|y=k)\right),$
$\displaystyle\leq\sum_{k^{\prime}=1}^{K}p(y=k^{\prime})D_{g}(p(\boldsymbol{x}|y=k^{\prime})\|p(\boldsymbol{x}|y=k)),$
$\displaystyle\leq\mathbb{E}_{k^{\prime}\sim
p(y)}\left[D_{g}(p(\boldsymbol{x}|y=k^{\prime})\|p(\boldsymbol{x}|y=k))\right].$

To retrieve the OvO form, we can compute the expectation of this inequality
over all possible combinations of $p(y)$:

$\displaystyle\mathbb{E}_{y\sim
p(y)}\left[D_{f}(p(\boldsymbol{x})\|p(\boldsymbol{x}|y=k))\right]$
$\displaystyle\leq\mathbb{E}_{y_{1},y_{2}\sim
p(y)}\left[D_{g}(p(\boldsymbol{x}|y_{1})\|p(\boldsymbol{x}|y_{2}))\right],$
$\displaystyle\mathcal{I}^{\text{ova}}_{D_{f}}(\boldsymbol{x};y)$
$\displaystyle\leq\mathcal{I}^{\text{ovo}}_{D_{g}}(\boldsymbol{x};y).$

Then, owing to the conjugate convex functions, we can observe that for any
$k,k^{\prime}\in\\{1,\cdots,K\\}$:

$D_{g}(p(\boldsymbol{x}|y=k)\|p(\boldsymbol{x}|y=k^{\prime}))+D_{g}(p(\boldsymbol{x}|y=k^{\prime})\|p(\boldsymbol{x}|y=k))=D_{f}(p(\boldsymbol{x}|y=k^{\prime})\|p(\boldsymbol{x}|y=k))\\\
+D_{f}(p(\boldsymbol{x}|y=k)\|p(\boldsymbol{x}|y=k^{\prime})).$

Consequently, the symmetry of OvO in its double expectation implies that:

$\mathcal{I}^{\text{ovo}}_{D_{f}}(\boldsymbol{x};y)=\mathcal{I}^{\text{ovo}}_{D_{g}}(\boldsymbol{x};y).$

And so do we conclude that:

$\mathcal{I}^{\text{ova}}_{D_{f}}(\boldsymbol{x};y)\leq\mathcal{I}^{\text{ovo}}_{D_{f}}(\boldsymbol{x};y).$
(23)

###  C.2 Demonstration for IPMs

For IPMs, we start from the OvA distance between the distribution of an
arbitrary cluster $i$ among $K$:

$D_{\text{IPM}}(p(\boldsymbol{x}|y=i)\|p(\boldsymbol{x}))=\sup_{f\in\mathcal{F}}\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=i)}[f(\boldsymbol{x})]-\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}[f(\boldsymbol{x})].$

We can extend the expectation of the data distribution over all clusters using
the sum rules of probabilities:

$\displaystyle D_{\text{IPM}}(p(\boldsymbol{x}|y=i)\|p(\boldsymbol{x}))$
$\displaystyle=\sup_{f\in\mathcal{F}}\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=i)}[f(\boldsymbol{x})]-\sum_{k=1}^{K}p(y=k)\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=k)}[f(\boldsymbol{x})],$
$\displaystyle=\sup_{f\in\mathcal{F}}\sum_{k=1}^{K}p(y=k)\left(\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=i)}[f(\boldsymbol{x})]-\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=k)}[f(\boldsymbol{x})]\right).$

We used in the second line the fact that the sum of $\sum_{k=1}^{K}p(y=k)=1$
to factorise the first expectation. Finally, we can use the property that the
supremum of a sum is lower or equal than a sum of suprema:

$\displaystyle D_{\text{IPM}}(p(\boldsymbol{x}|y=i)\|p(\boldsymbol{x}))$
$\displaystyle\leq\sum_{k=1}^{K}\sup_{f\in\mathcal{F}}p(y=k)\left(\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=i)}[f(\boldsymbol{x})]-\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=k)}[f(\boldsymbol{x})]\right),$
$\displaystyle\leq\sum_{k=1}^{K}p(y=k)D_{\text{IPM}}(p(\boldsymbol{x}|y=i)\|p(\boldsymbol{x}|y=k)).$

This upper bound corresponds to the expectation of the IPM between a specific
cluster distribution $i$ and all other cluster distributions. Finally, by
performing the expectation over all cluster of index $i$, we can conclude
that:

$\mathcal{I}^{\text{ova}}_{\text{IPM}}(\boldsymbol{x};y)\leq\mathcal{I}^{\text{ovo}}_{\text{IPM}}(\boldsymbol{x};y).$
(24)

##  Appendix D Proof of Proposition 3.4

We will show here that when the cluster variable $y$ is binary, the OvA and
OvO GEMINIs are equal if we use IPMs for distance between distributions.
Indeed we can first unfold both equations:

$\begin{split}\mathcal{I}_{\text{IPM}}^{\text{ova}}(\boldsymbol{x},y)&=\mathbb{E}_{y\sim
p(y)}\left[D_{\text{IPM}}(p(\boldsymbol{x}|y)\|p(\boldsymbol{x})\right]\\\
&=p(y=0)D_{\text{IPM}}(p(\boldsymbol{x}|y=0)\|p(\boldsymbol{x}))+p(y=1)D_{\text{IPM}}(p(\boldsymbol{x}|y=1)\|p(\boldsymbol{x}))\\\
&=p(y=0)\sup_{f\in\mathcal{F}}\\{\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=0)}[f(\boldsymbol{x})]-\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}[f(\boldsymbol{x})]\\}\\\
&\quad+p(y=1)\sup_{g\in\mathcal{F}}\\{\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=1)}[g(\boldsymbol{x})]-\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}[g(\boldsymbol{x})]\\},\end{split}$ (25)

and for the OvO, we simply use the symmetric property of IPMs:

$\begin{split}\mathcal{I}_{\text{IPM}}^{\text{ovo}}(\boldsymbol{x},y)&=\mathbb{E}_{y_{a},y_{b}\sim
p(y)}\left[D_{\text{IPM}}(p(\boldsymbol{x}|y_{a})\|p(\boldsymbol{x}|y_{b}))\right]\\\
&=p(y=0)p(y=1)D_{\text{IPM}}(p(\boldsymbol{x}|y=0)||p(\boldsymbol{x}|y=1))\\\
&\qquad+p(y=1)p(y=0)D_{\text{IPM}}(p(\boldsymbol{x}|y=1)||p(\boldsymbol{x}|y=0))\\\
&=2p(y=0)p(y=1)D_{\text{IPM}}(p(\boldsymbol{x}|y=0)||p(\boldsymbol{x}|y=1)).\end{split}$
(26)

Notice that in Eq. (26), we skipped the terms where both the random variables
$y_{1}$ and $y_{2}$ are equal, since the implied distance is necessarily 0.

Now, to show the equivalence of both equations (25) and (26), we simply need
to write the sum rule of probabilities leading to the marginalisation of
$\boldsymbol{x}$:

$p(\boldsymbol{x})=p(\boldsymbol{x}|y=0)p(y=0)+p(\boldsymbol{x}|y=1)p(y=1).$

Thus, we can rewrite the expectations depending on the distribution
$p(\boldsymbol{x})$ with other distributions for any function $f$:

$\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x})}[f(\boldsymbol{x})]=p(y=0)\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=0)}[f(\boldsymbol{x})]+p(y=1)\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=1)}[f(\boldsymbol{x})]],$

which we can incorporate back into Eq. (25) to get:

$\mathcal{I}_{\text{IPM}}^{\text{ova}}(\boldsymbol{x},y)=p(y=0)\sup_{f\in\mathcal{F}}\\{(1-p(y=0))\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=0)}[f(\boldsymbol{x})]-p(y=1)\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=1)}[f(\boldsymbol{x})]]\\}\\\
+p(y=1)\sup_{g\in\mathcal{F}}\\{(1-p(y=1))\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=1)}[g(\boldsymbol{x})]-p(y=0)\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=0)}[g(\boldsymbol{x})]\\}.$

Since we only use two clusters, we know that $p(y=1)=1-p(y=0)$. This helps us
factorising terms inside the sup expressions:

$\begin{split}\mathcal{I}_{\text{IPM}}^{\text{ova}}(\boldsymbol{x},y)&=p(y=0)\sup_{f\in\mathcal{F}}\left\\{p(y=1)\left[\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=0)}[f(\boldsymbol{x})]-\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=1)}[f(\boldsymbol{x})]\right]\right\\}\\\ &\qquad
p(y=1)\sup_{g\in\mathcal{F}}\left\\{p(y=0)\left[\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=1)}[g(\boldsymbol{x})]-\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=0)}[g(\boldsymbol{x})]\right]\right\\}.\end{split}$

Eventually, the factors $p(y=0)$ and $p(y=1)$ do not depend on the functions
$f$ and $g$, so we can pull them out of the supremum. The remaining
expressions are then symmetric and can be thus factorised:

$\begin{split}\mathcal{I}_{\text{IPM}}^{\text{ova}}(\boldsymbol{x},y)&=2p(y=0)p(y=1)\sup_{f\in\mathcal{F}}\left\\{\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=0)}[f(\boldsymbol{x})]-\mathbb{E}_{\boldsymbol{x}\sim
p(\boldsymbol{x}|y=1)}[f(\boldsymbol{x})]\right\\}\\\
&=2p(y=0)p(y=1)D_{\text{IPM}}(p(\boldsymbol{x}|y=0)||p(\boldsymbol{x}|y=1))\\\
&=\mathcal{I}_{\text{IPM}}^{\text{ovo}}(\boldsymbol{x},y)\end{split}$

This concludes the proof.

##  Appendix E Proof of Proposition 3.5

For any $f$-divergence and two distribution $p$ and $q$ taking value in the
space $\mathcal{X}$, then disjoint support between $p$ and $q$ implies the
maximisation of the $f$-divergence. Indeed, the bounds of an $f$-divergence
are:

$0\leq D_{f}(p,q)\leq f(0)+g(0),$

where the upper bound can be infinity depending on $f$ and its convex
conjugate $g:t\longrightarrow tf(1/t)$. Thus, for any two different clusters
$k\neq k^{\prime}$:

$0\leq D_{f}(p(\boldsymbol{x}|y=k)\|p(\boldsymbol{x}|y=k^{\prime}))\leq
f(0)+g(0).$

However, distributions for the same clusters have an $f$-divergence of 0. We
can therefore sum all the terms and their respective upper bounds:

$\displaystyle\sum_{k\neq
k^{\prime}}^{K}p(y=k)p(y=k^{\prime})D_{f}(p(\boldsymbol{x}|y=k)\|p(\boldsymbol{x}|y=k^{\prime}))$
$\displaystyle\leq\sum_{k\neq k^{\prime}}^{K}p(y=k)p(y=k^{\prime})(f(0)+g(0))$
$\displaystyle\mathcal{I}_{D_{f}}^{\text{ovo}}(\boldsymbol{x},y)$
$\displaystyle\leq\sum_{k=1}^{K}p(y=k)p(y\neq k)(f(0)+g(0)),$

Following [9, theorem 5], disjoint supports between the distribution
$p(\boldsymbol{x}|y=k)$ and $p(\boldsymbol{x}|y=k^{\prime})$ implies the
equality with the upper bound. Assume that the data space $\mathcal{X}$ is
separated into $K$ disjoint and supplementary spaces $\mathcal{X}_{k}$. To
each subspace $\mathcal{X}_{k}$ corresponds a cluster distribution
$p(\boldsymbol{x}|y=k)$. This disjoint supports are achieved for any model of
the form:

$p(y=k|\boldsymbol{x})=\boldsymbol{1}[\boldsymbol{x}\in\mathcal{X}_{k}],$

which implies the disjoint distributions:

$p(\boldsymbol{x}|y=k)\propto\boldsymbol{1}[\boldsymbol{x}\in\mathcal{X}_{k}]$

Each of these spaces control the proportion of data in the cluster $k$, and
hence controls $p(y=k)$. Thus, the OvO GEMINI is equal to its upper bound
owing to disjoint supports:

$\mathcal{I}^{\text{ovo}}_{D_{f}}(\boldsymbol{x},y)=\sum_{k=1}^{K}p(y=k)p(y\neq
k)(f(0)+g(0))$

We need to maximise the upper bound. This will be the maximum value of OvO
GEMINI reachable for models with disjoint supports. Adding a Lagrangian term
to respect the contraint of $\sum_{k=1}^{K}p(y=k)=1$ leads to the optimal
solution $p(y=k)=\frac{1}{K}$. This concludes the proof.

##  Appendix F Deriving GEMINIs

We show in this appendix how to derive all estimable forms of the GEMINI.

###  F.1 $f$-divergence GEMINI

We detail here the derivation for 3 $f$-divergences that we previously chose:
the KL divergence, the TV distance and the squared Hellinger distance, as well
as the generic scenario for any function $f$.

####  F.1.1 Generic scenario

First, we recall that the definition of an $f$-divergence involves a convex
function:

$\displaystyle f:\mathbb{R}^{+}$ $\displaystyle\rightarrow\mathbb{R}$
$\displaystyle x$ $\displaystyle\rightarrow f(x)$
$\displaystyle\text{s.t.}\quad f(1)$ $\displaystyle=0,$

between two distributions $p$ and $q$ as described:

$D_{\text{f-div}}(p,q)=\mathbb{E}_{\boldsymbol{x}\sim
q}\left[f\left(\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}\right)\right].$

We simply inject this definition in the OvA GEMINI and directly obtain both an
expectation on the cluster assignment $y$ and on the data variable
$\boldsymbol{x}$. We then merge the writing of the two expectations for the
sake of clarity.

$\displaystyle\mathcal{I}^{\text{ova}}_{\text{f-div}}(x;y)$
$\displaystyle=\mathbb{E}_{p_{\theta}(y)}\left[D_{\text{f-div}}(p_{\theta}(\boldsymbol{x}|y)||p_{\textup{data}}(\boldsymbol{x}))\right],$
$\displaystyle=\mathbb{E}_{p_{\theta}(y)}\left[\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}\left[f\left(\frac{p_{\theta}(\boldsymbol{x}|y)}{p_{\textup{data}}(\boldsymbol{x})}\right)\right]\right],$
$\displaystyle=\mathbb{E}_{p_{\theta}(y),p_{\textup{data}}(\boldsymbol{x})}\left[f\left(\frac{p_{\theta}(y|\boldsymbol{x})}{p_{\theta}(y)}\right)\right].$

Injecting the $f$-divergence in the OvO GEMINI first yields:

$\displaystyle\mathcal{I}^{\text{ovo}}_{\text{f-div}}(x;y)$
$\displaystyle=\mathbb{E}_{p_{\theta}(y_{a}),p_{\theta}(y_{b})}\left[D_{\text{f-div}}(p_{\theta}(\boldsymbol{x}|y_{a})||p_{\theta}(\boldsymbol{x}|y_{b}))\right],$
$\displaystyle=\mathbb{E}_{p_{\theta}(y_{a}),p_{\theta}(y_{b})}\left[\mathbb{E}_{p_{\theta}(\boldsymbol{x}|y_{b})}\left[f\left(\frac{p_{\theta}(\boldsymbol{x}|y_{a})}{p_{\theta}(\boldsymbol{x}|y_{b})}\right)\right]\right].$

Now, by using Bayes theorem, we can perform the inner expectation over the
data distribution. We then merge the expectations for the sake of clarity.

$\displaystyle\mathcal{I}^{\text{ovo}}_{\text{f-div}}(x;y)$
$\displaystyle=\mathbb{E}_{p_{\theta}(y_{a}),p_{\theta}(y_{b})}\left[\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}\left[\frac{p_{\theta}(y_{b}|\boldsymbol{x})}{p_{\theta}(y_{b})}f\left(\frac{p_{\theta}(\boldsymbol{x}|y_{a})}{p_{\theta}(\boldsymbol{x}|y_{b})}\right)\right]\right],$
$\displaystyle=\mathbb{E}_{p_{\theta}(y_{a}),p_{\theta}(y_{b}),p_{\textup{data}}(\boldsymbol{x})}\left[\frac{p_{\theta}(y_{b}|\boldsymbol{x})}{p_{\theta}(y_{b})}f\left(\frac{p_{\theta}(y_{a}|\boldsymbol{x})p_{\theta}(y_{b})}{p_{\theta}(y_{b}|\boldsymbol{x})p_{\theta}(y_{a})}\right)\right].$

Notice that we also changed the ratio of conditional distributions inside the
function by a ratio of posteriors through Bayes’ theorem, weighted by the
relative cluster proportions.

Now, we can derive into details these equations for the 3 $f$-divergences we
focused on: the KL divergence, the TV distance and the squared Hellinger
distance.

####  F.1.2 Kullback-Leibler divergence

The function for Kullback-Leibler is $f(t)=t\log t$. We do not need to write
the OvA equation: it is straightforwardly the usual MI. For the OvO, we inject
the function definition by replacing:

$t=\frac{p_{\theta}(y_{a}|\boldsymbol{x})p_{\theta}(y_{b})}{p_{\theta}(y_{b}|\boldsymbol{x})p_{\theta}(y_{a})},$

in order to get:

$\displaystyle\mathcal{I}^{\text{ovo}}_{\text{KL}}(x;y)$
$\displaystyle=\mathbb{E}_{p_{\theta}(y_{a}),p_{\theta}(y_{b}),p_{\textup{data}}(\boldsymbol{x})}\left[\frac{p_{\theta}(y_{b}|\boldsymbol{x})}{p_{\theta}(y_{b})}\times\frac{p_{\theta}(y_{a}|\boldsymbol{x})p_{\theta}(y_{b})}{p_{\theta}(y_{b}|\boldsymbol{x})p_{\theta}(y_{a})}\log{\frac{p_{\theta}(y_{a}|\boldsymbol{x})p_{\theta}(y_{b})}{p_{\theta}(y_{b}|\boldsymbol{x})p_{\theta}(y_{a})}}\right].$

We can first simplify the factors outside of the logs:

$\displaystyle\mathcal{I}^{\text{ovo}}_{\text{KL}}(x;y)$
$\displaystyle=\mathbb{E}_{p_{\theta}(y_{a}),p_{\theta}(y_{b}),p_{\textup{data}}(\boldsymbol{x})}\left[\frac{p_{\theta}(y_{a}|\boldsymbol{x})}{p_{\theta}(y_{a})}\log{\frac{p_{\theta}(y_{a}|\boldsymbol{x})p_{\theta}(y_{b})}{p_{\theta}(y_{b}|\boldsymbol{x})p_{\theta}(y_{a})}}\right].$

If we use the properties of the log, we can separate the inner term in two
sub-expressions:

$\displaystyle\mathcal{I}^{\text{ovo}}_{\text{KL}}(x;y)=\mathbb{E}_{p_{\theta}(y_{a}),p_{\theta}(y_{b}),p_{\textup{data}}(\boldsymbol{x})}\left[\frac{p_{\theta}(y_{a}|\boldsymbol{x})}{p_{\theta}(y_{a})}\log{\frac{p_{\theta}(y_{a}|\boldsymbol{x})}{p_{\theta}(y_{a})}}+\frac{p_{\theta}(y_{a}|\boldsymbol{x})}{p_{\theta}(y_{a})}\log{\frac{p_{\theta}(y_{b})}{p_{\theta}(y_{b}|\boldsymbol{x})}}\right].$

Hence, we can use the linearity of the expectation to separate the two terms
above. The first term is constant w.r.t. $y_{b}$, so we can remove this
variable from the expectation among the subscripts:

$\mathcal{I}^{\text{ovo}}_{\text{KL}}(\boldsymbol{x},y)=\mathbb{E}_{p_{\theta}(y_{a}),p_{\textup{data}}(\boldsymbol{x})}\left[\frac{p_{\theta}(y_{a}|\boldsymbol{x})}{p_{\theta}(y_{a})}\log{\frac{p_{\theta}(y_{a}|\boldsymbol{x})}{p_{\theta}(y_{a})}}\right]+\mathbb{E}_{p_{\theta}(y_{a}),p_{\theta}(y_{b}),p_{\textup{data}}(\boldsymbol{x})}\left[\frac{p_{\theta}(y_{a}|\boldsymbol{x})}{p_{\theta}(y_{a})}\log{\frac{p_{\theta}(y_{b})}{p_{\theta}(y_{b}|\boldsymbol{x})}}\right].$

Since the variables $y_{a}$ and $y_{b}$ are independent, we can use the fact
that:

$\mathbb{E}_{p_{\theta}(y_{a})}\left[\frac{p_{\theta}(y_{a}|\boldsymbol{x})}{p_{\theta}(y_{a})}\right]=\int
p_{\theta}(y_{a})\frac{p_{\theta}(y_{a}|\boldsymbol{x})}{p_{\theta}(y_{a})}dy_{a}=1,$

inside the second term to reveal the final form of the equation:

$\displaystyle\mathcal{I}^{\text{ovo}}_{\text{KL}}(x;y)=\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x}),p_{\theta}(y)}\left[\frac{p_{\theta}(y|\boldsymbol{x})}{p_{\theta}(y)}\log{\frac{p_{\theta}(y|\boldsymbol{x})}{p_{\theta}(y)}}\right]+\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x}),p_{\theta}(y)}\left[\log{\frac{p_{\theta}(y)}{p_{\theta}(y|\boldsymbol{x})}}\right].$

Notice that since both terms did not compare one cluster assignment $y_{a}$
against another $y_{b}$, we can switch to the same common variable $y$. Both
terms are in fact KL divergences depending on the cluster assignment $y$. The
first is the reverse of the second. This sum of KL divergences is sometimes
called the _symmetric_ KL, and so can we write in two ways the OvO KL-GEMINI:

$\displaystyle\mathcal{I}^{\text{ovo}}_{\text{KL}}(x;y)$
$\displaystyle=\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}\left[D_{\text{KL}}(p_{\theta}(y|\boldsymbol{x})||p_{\theta}(y))\right]+\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}\left[D_{\text{KL}}(p_{\theta}(y)||p_{\theta}(y|\boldsymbol{x}))\right],$
$\displaystyle=\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}\left[D_{\text{KL-
sym}}(p_{\theta}(y|\boldsymbol{x})||p_{\theta}(y))\right].$

We can also think of this equation as the usual MI with an additional term
based on the reversed KL divergence.

####  F.1.3 Total Variation distance

For the total variation, the function is $f(t)=\frac{1}{2}|t-1|$. Thus, the
OvA GEMINI is:

$\mathcal{I}^{\text{ova}}_{\text{TV}}(x;y)=\frac{1}{2}\mathbb{E}_{p_{\theta}(y),p_{\textup{data}}(\boldsymbol{x})}\left[|\frac{p_{\theta}(y|\boldsymbol{x})}{p_{\theta}(y)}-1|\right].$

And the OvO is:

$\displaystyle\mathcal{I}^{\text{ovo}}_{\text{TV}}(x;y)$
$\displaystyle=\frac{1}{2}\mathbb{E}_{p_{\theta}(y_{a}),p_{\theta}(y_{b}),p_{\textup{data}}(\boldsymbol{x})}\left[\frac{p_{\theta}(y_{b}|\boldsymbol{x})}{p_{\theta}(y_{b})}|\frac{p_{\theta}(y_{a}|\boldsymbol{x})p_{\theta}(y_{b})}{p_{\theta}(y_{b}|\boldsymbol{x})p_{\theta}(y_{a})}-1|\right],$
$\displaystyle=\frac{1}{2}\mathbb{E}_{p_{\theta}(y_{a}),p_{\theta}(y_{b}),p_{\textup{data}}(\boldsymbol{x})}\left[|\frac{p_{\theta}(y_{a}|\boldsymbol{x})}{p_{\theta}(y_{a})}-\frac{p_{\theta}(y_{b}|\boldsymbol{x})}{p_{\theta}(y_{b})}|\right].$

We did not find any further simplification of these equations.

####  F.1.4 Squared Hellinger distance

Finally, the squared Hellinger distance is based on $f(t)=2(1-\sqrt{t})$.
Hence the OvA unfolds as:

$\displaystyle\mathcal{I}^{\text{ova}}_{\text{H}^{2}}(x;y)$
$\displaystyle=\mathbb{E}_{p_{\theta}(y),p_{\textup{data}}(\boldsymbol{x})}\left[2\left(1-\sqrt{\frac{p_{\theta}(y|\boldsymbol{x})}{p_{\theta}(y)}}\right)\right],$
$\displaystyle=2-2\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x}),p_{\theta}(y)}\left[\sqrt{\frac{p_{\theta}(y|\boldsymbol{x})}{p_{\theta}(y)}}\right].$

The idea of the squared OvA Hellinger-GEMINI is therefore to minimise the
expected square root of the relative certainty between the posterior and
cluster proportion.

For the OvO setting, the definition yields:

$\mathcal{I}^{\text{ovo}}_{\text{H}^{2}}(x;y)=\mathbb{E}_{p_{\theta}(y_{a}),p_{\theta}(y_{b}),p_{\textup{data}}(\boldsymbol{x})}\left[\frac{p_{\theta}(y_{b}|\boldsymbol{x})}{p_{\theta}(y_{b})}\times
2\times\left(1-\sqrt{\frac{p_{\theta}(y_{a}|\boldsymbol{x})p_{\theta}(y_{b})}{p_{\theta}(y_{b}|\boldsymbol{x})p_{\theta}(y_{a})}}\right)\right],$

which we can already simplify by putting the constant 2 outside of the
expectation, and by inserting all factors inside the square root before
simplifying and separating the expectation:

$\displaystyle\mathcal{I}^{\text{ovo}}_{\text{H}^{2}}(x;y)$
$\displaystyle=2\mathbb{E}_{p_{\theta}(y_{a}),p_{\theta}(y_{b}),p_{\textup{data}}(\boldsymbol{x})}\left[\frac{p_{\theta}(y_{b}|\boldsymbol{x})}{p_{\theta}(y_{b})}-\frac{p_{\theta}(y_{b}|\boldsymbol{x})}{p_{\theta}(y_{b})}\sqrt{\frac{p_{\theta}(y_{a}|\boldsymbol{x})p_{\theta}(y_{b})}{p_{\theta}(y_{a})p_{\theta}(y_{b}|\boldsymbol{x})}}\right],$
$\displaystyle=2\mathbb{E}_{p_{\theta}(y_{a}),p_{\theta}(y_{b}),p_{\textup{data}}(\boldsymbol{x})}\left[\frac{p_{\theta}(y_{b}|\boldsymbol{x})}{p_{\theta}(y_{b})}\right]-2\mathbb{E}_{p_{\theta}(y_{a}),p_{\theta}(y_{b}),p_{\textup{data}}(\boldsymbol{x})}\left[\sqrt{\frac{p_{\theta}(y_{a}|\boldsymbol{x})p_{\theta}(y_{b}|\boldsymbol{x})}{p_{\theta}(y_{a})p_{\theta}(y_{b})}}\right].$

We can replace the first term by the constant 1, as shown for the OvO KL
derivation. Since we can split the square root into the product of two square
roots, we can apply twice the expectation over $y_{a}$ and $y_{b}$ because
these variables are independent:

$\mathcal{I}^{\text{ovo}}_{\text{H}^{2}}(x;y)=2-2\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}\left[\mathbb{E}_{p_{\theta}(y)}\left[\sqrt{\frac{p_{\theta}(y|\boldsymbol{x})}{p_{\theta}(y)}}\right]^{2}\right].$

To avoid computing this squared expectation, we use the equation of the
variance $\mathbb{V}$ to replace it. Thus:

$\displaystyle\mathcal{I}^{\text{ovo}}_{\text{H}^{2}}(x;y)$
$\displaystyle=2-2\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}\left[\mathbb{E}_{p_{\theta}(y)}\left[\frac{p_{\theta}(y|\boldsymbol{x})}{p_{\theta}(y)}\right]-\mathbb{V}_{p_{\theta}(y)}\left[\sqrt{\frac{p_{\theta}(y|\boldsymbol{x})}{p_{\theta}(y)}}\right]\right],$
$\displaystyle=2-2\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}\left[\mathbb{E}_{p_{\theta}(y)}\left[\frac{p_{\theta}(y|\boldsymbol{x})}{p_{\theta}(y)}\right]\right]+2\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}\left[\mathbb{V}_{p_{\theta}(y)}\left[\sqrt{\frac{p_{\theta}(y|\boldsymbol{x})}{p_{\theta}(y)}}\right]\right].$

Then, for the same reason as before, the second term is worth 1, which cancels
the first constant. We therefore end up with:

$\mathcal{I}^{\text{ovo}}_{\text{H}^{2}}(x;y)=2\mathbb{E}_{p_{\textup{data}}(\boldsymbol{x})}\left[\mathbb{V}_{p_{\theta}(y)}\left[\sqrt{\frac{p_{\theta}(y|\boldsymbol{x})}{p_{\theta}(y)}}\right]\right].$

Similar to the OvO KL case, the OvO squared Hellinger converges to an OvA
setting, i.e. we only need information about the cluster distribution itself
without comparing it to another. Furthermore, the idea of maximising the
variance of the cluster assignments is straightforward for clustering.

###  F.2 Maximum Mean Discrepancy

When using an IPM with a family of functions that project an input of
$\mathcal{X}$ to the unit ball of an RKHS $\mathcal{H}$, the IPM becomes the
MMD distance.

$\displaystyle\text{MMD}(p,q)$ $\displaystyle=\sup_{f:||f||_{\mathcal{H}}\leq
1}\mathbb{E}_{\boldsymbol{x}_{a}\sim
p}[f(\boldsymbol{x}_{a})]-\mathbb{E}_{\boldsymbol{x}_{b}\sim
q}[f(\boldsymbol{x}_{b})],$
$\displaystyle=\|\mathbb{E}_{\boldsymbol{x}_{a}\sim
p}[\varphi(\boldsymbol{x}_{a})]-\mathbb{E}_{\boldsymbol{x}_{b}\sim
q}[\varphi(\boldsymbol{x}_{b})]\|_{\mathcal{H}},$

where $\varphi$ is a embedding function of the RKHS.

By using a kernel function
$\kappa(\boldsymbol{x}_{a},\boldsymbol{x}_{b})=<\varphi(\boldsymbol{x}_{a}),\varphi(\boldsymbol{x}_{b})>$,
we can express the square of this distance thanks to inner product space