\subsection{Mise en place du problème}
Nous nous donnons deux ensembles finis, un ensemble $E$ de données d'entrée et un espace d'étiquette $F$.
Nous notons $m=\#E$ et $n=\#F$.
Soit $\varphi$ une bijection de $E$ dans $[|0,m-1|]$ et $\psi$ une bijection de $F$ dans $[|0,n-1|]$.
Nous supposons que nous avons un $o$-uplet $d: [|0,o-1] \rightarrow E\times F$.
$d$ modélise une jeu de donnée en pratique comme il est utilisé en apprentissage automatique.
Nous pouvons alors construire un jeu de donnée d'indices :
\begin{equation*}
    d' : \left\{
        \begin{matrix}
            [|0,o-1|]&\longrightarrow&[|0,m-1|]\times[|0,n-1|]\\
            i&\mapsto&\left(\varphi(d_0(i)),\psi(d_1(i))\right)
        \end{matrix}
        \right.
\end{equation*}

\begin{definition}
    \label{def:BA}
    L'exactitude équilibré empirique de $f$ sur le $o$-uplet $d$ relativement à $F$, que l'on appelle $BA_F^d(f)$, est un nombre dans $[0,1]$ tel que 
    \begin{equation*}
        BA_F^d(f) = \frac{1}{n}
            \sum_{y\in F} 
            \frac{
                \#\left\{j\in [|0,o-1|]\quad| f(d_0(j))=d_1(j)\wedge d_1(j) = y\right\}
            }
            {\#\{j\in [|0,o-1|]\quad| d_1(j)=y\}}
    \end{equation*}
\end{definition}
Cette définition est un approximation de l'exactitude équilibré que nous avons définit plus haut.
\textbf{Le problème consiste à trouver une application $f:E\rightarrow F$ telle que l'exactitude équilibré de $f$ sur $d$ est maximal.}

\subsection{Relation entre éléments et indices}
Nous commençons par noter par $B_{E\rightarrow F}$ l'ensemble des fonctions de $E$ dans $F$.
Pour simplifier un peu les notations, nous appellerons $B_{m\rightarrow n}$ l'ensemble des fonctions de $[|0,m-1|]$ dans $[|0,n-1|]$.

\begin{theorem}
    \label{th:bij}
    Soient $E$ et $F$ deux ensemble finis de cardinaux $m$ et $n$. 
    Il existe une bijection de $B_{E\rightarrow F}$ dans $B_{m\rightarrow n}$.
\end{theorem}

\begin{proof}
    Nous procédons en explicitant une telle bijection.
    Soit
    \begin{equation}
        \Phi :\left\{
            \begin{matrix}
                B_{E\rightarrow F} &\longrightarrow& B_{m\rightarrow n}&\\
                f&\mapsto &\psi\circ f\circ\varphi^{-1}
            \end{matrix}
            \right.
    \end{equation}
    
    Montrons maintenant que $\Phi$ est un bijection.
    Soit $(u,v)\in \left(B_{E\rightarrow F}\right)^2$ telle que
    $\Phi(u) = \Phi(v)$.
    Alors
    \begin{align*}
        & \psi\circ u\circ\varphi^{-1} = \psi\circ v\circ\varphi^{-1}\\
        \Leftrightarrow& \psi^{-1}\circ\psi\circ u\circ\varphi^{-1} = \psi^{-1}\circ\psi\circ v\circ\varphi^{-1}\\
         \Leftrightarrow&u\circ\varphi^{-1} =  v\circ\varphi^{-1}\\
         \Leftrightarrow&u\circ\varphi^{-1}\circ\varphi =  v\circ\varphi^{-1}\circ\varphi\\
         \Leftrightarrow&u = v\\
    \end{align*}
    Ainsi $\Phi$ est injective. 

    Montrons maintenant que $\Phi$ est surjective.
    Soit $g\in B_{m\rightarrow n}$.
    Alors
    $\Phi(\psi^{-1}\circ g\circ\varphi) = 
    \psi\circ\psi^{-1}\circ g\circ\varphi\circ\varphi^{-1} = g$
    Ainsi $\Phi$ est surjective. 

    En conclusion $\Phi$ est à la fois injective et surjective : c'est une bijection.
\end{proof}

$\varphi$ et $\psi$ peuvent être vus comme des indices sur $E$ et $F$.
Par exemple, chaque élément $e$ dans $E$ a un unique index $\varphi(e)$.
Cette étape d'abstraction nous permet de construire des fonctions explicites de $E$ dans $F$ sans prendre en comptes les spécificités de objets mathématiques dans ses ensembles.
En effet, le théorème~\ref{th:bij} nous donne que pour chaque fonction des indices de $E$ vers les indices de $F$ nous pouvons trouver une unique fonction de de $E$ dans $F$.
Et la preuve étant constructive nous indique que pour trouver cette fonction nous pouvons utiliser $\Phi^{-1}$.

    Étudions donc comment se comporte l'exactitude équilibré quand on compose avec $\Phi$.
\begin{theorem}
    \label{th:BAphi=BA}
    Soit $E$ et $F$ deux ensembles finis.
    Soit $d$ un uplet de $E\times F$.
    Alors nous avons l'égalité suivante :
    \begin{equation*}
        BA^{d'}_{[|0,\#F-1|]}\circ\Phi = BA^d_F
    \end{equation*}
\end{theorem}

\begin{proof}
    Soit $E$ et $F$ deux ensembles finis.
    Nous avons deux bijections :
    $\varphi$ de $E$ dans $[|0,\#E-1|]$ et
    $\psi$ de $F$ dans $[|0,\#F-1|]$.
    Avec ces deux fonctions nous allons construire une troisième bijections 
    $\Phi$ de $B_{E\rightarrow F}$ dans $B_{\#E\rightarrow \#F }$  similaire à celle de la preuve du théorème~\ref{th:bij}.
    Soient $o\in\mathbb{N}^*$ et $d$ un $o$-uplet de $E\times F$.
    
    Soit $f\in B_{E\rightarrow F}$ 
    alors
    \begin{equation}
        \label{eq:BAdp}
        \left(BA^{d'}_{[|0,\#F-1|]}\circ\Phi\right)(f) =  
        \frac{1}{\#F}
        \sum_{i=0}^{\#F-1}\frac{
            \#\left\{j\in[|0,o-1|]\quad | \Phi(f)(d'_0(j))=d'_1(j)\wedge d'_1(j)=i\right\}}
        {\#\left\{j\in[|0,o-1|]\quad | d'_1(j)=i\right\}}\\
    \end{equation}
    
    Nous remarquons aussi que 
    \begin{equation*}
    \Phi(f)\circ d'_0= 
    \psi\circ f\circ\varphi^{-1}\circ d'_0 = 
    \psi\circ f\circ\varphi^{-1}\circ \varphi\circ d_0=
    \psi\circ f\circ d_0
    \end{equation*}

    Ainsi, soit $j\in[|0,o-1|]$
    \begin{align*}
        &\left(\Phi(f)\circ d'_0\right)(j) = d'_1(j)\\
        \Leftrightarrow &\left(\psi\circ f\circ d_0\right)(j)= d'_1(j)\\
        \Leftrightarrow &\left(\psi\circ f\circ d_0\right)(j) = \psi\circ d_1(j)\\
        \Leftrightarrow &\left(f\circ d_0\right)(j) = d_1(j)\\
    \end{align*}

    Ce qui nous donnes les assertions suivantes :
    \begin{equation}
        \label{eq:d1j}
        \forall j\in[|0,o-1|]\quad
        \left[
            (\Phi(f)\circ d'_0)(j) = d'_1(j)
            \Leftrightarrow
            (f\circ d_0)(j) = d_1(j)\\
            \right]
    \end{equation}

    De même, passons des indices aux éléments sur "$d'_1(j) = i$".
    Let $i\in[|0,\#F-1|]$ and $j\in[|0,o-1|]$.
    \begin{align*}
        &d'_1(j) = i\\
        \Leftrightarrow & (\psi\circ d_1)(j) = i\\
        \Leftrightarrow & d_1(j) = \psi^{-1}(i)
    \end{align*}

    Ainsi avec les équations \ref{eq:BAdp} et \ref{eq:d1j} nous obtenons
    \begin{align}
        &\left(BA^{d'}_{[|0,\#F-1|]}\circ\Phi\right)(f) =  
        \frac{1}{\#F}
        \sum_{y=0}^{\#F-1}\frac{
            \#\left\{j\in[|0,o-1|]\quad | f(d_0(j))=d_1(j)\wedge d_1(j)=\psi^{-1}(i)\right\}}
        {\#\left\{j\in[|0,o-1|]\quad | d_1(j)=\psi^{-1}(i)\right\}}\\\nonumber
        &=
        \frac{1}{\#F}
        \sum_{y=\psi^{-1}(0),\cdots,\psi^{-1}(\#F-1)}\frac{
            \#\left\{j\in[|0,o-1|]\quad | f(d_0(j))=d_1(j)\wedge d_1(j)=y\right\}}
        {\#\left\{j\in[|0,o-1|]\quad | d_1(j)=y\right\}}\\\nonumber
        &=
        \frac{1}{\#F}
        \sum_{y\in F}\frac{
            \#\left\{j\in[|0,o-1|]\quad | f(d_0(j))=d_1(j)\wedge d_1(j)=y\right\}}
        {\#\left\{j\in[|0,o-1|]\quad | d_1(j)=y\right\}}\\
        \label{eq:fini-egaba}
    \end{align}

    D'après la définition~\ref{def:BA} l'expression~\ref{eq:fini-egaba} est égale à $BA_F^d(f)$
\end{proof}

En utilisant le théorème~\ref{th:BAphi=BA} nous déduisons le corollaire suivant qui jouera un rôle clé dans le recherche de la solution à $\text{argmax}\left(BA_F^d\right)$.

\begin{corollary}
    \label{co:argmax}
    \begin{equation*}
        \text{argmax}\left(BA_F^d\right)
         = \Phi^{-1}\left(\text{argmax}\left(BA_{[|0,\#F-1|]}^{d'}\right)\right)
    \end{equation*}
\end{corollary}

\begin{proof}
    Soit $f' = \text{argmax}\left(BA_{[|0,\#F-1|]}^{d'}\right)$. 
    Alors, pour tout $g$ dans $B_{E\rightarrow F}$,
    $BA_F^d(g) = BA_{[|0,\#F-1|]}^{d'}(\Phi(g)) \leq
    BA_{[|0,\#F-1|]}^{d'}(f') = BA_F^d(\Phi^{-1}(f'))$
\end{proof}

Grâce au corollaire~\ref{co:argmax} nous avons que, pour résoudre le problème de classification sur n'importe quel ensemble, il est suffisant de le résoudre sur l'ensemble d'indices correspondant.
L'objectif de la prochaine section est donc la recherche d'un algorithme de résolution d'un tel problème.

\subsection{Maximisation l'exactitude équilibré sur $B_{m\rightarrow n}$}

Soient $m$, $n$ et $p$ des entiers naturels non-nuls.
Soit aussi $d$, un $o$-uplet de $[|0,m-1|]\times[|0,n-1|]$.
Comme nous savons que nous allons travailler sur les indices, nous ne nous préoccupons pas d'ensembles quelconques $E$ et $F$ comme à la section précédente.
A la place nous prenons $E=\{0,1,\cdots,m-1\}$ and $F=\{0,1,\cdots,n-1\}$.

L'approche la plus directe pour maximiser $BA_{[|0,n-1|]}^d$ serait l'algorithme qui consiste à essayer de calculer l'exactitude équilibré pour toutes les fonctions de $B_{m\rightarrow n}$.
Cette méthode est viable pour des petites valeurs de $m$ et $n$ mais devient rapidement impossible à calculer pour des grandes valeurs.
En effet, par dénombrement nous savons que $B_{m\rightarrow n}$ contiens $n^m$ éléments.
L'algorithme directe a donc une complexité de $\mathcal{O}(on^m)$ opérations. 
Nous allons construire à la place un algorithme que garantie de maximiser l'exactitude équilibré en $\mathcal{O}(onm)$ opérations.

Pour le construire nous allons, d'une certaine manière, distribuer l'opérateur argmax, simplifiant ainsi l'expression de l'exactitude équilibré optimale.
Pour cela, dans le lemme qui suit nous allons reformuler l'exactitude équilibré.

\begin{lemma}
    \label{lem:sumei}
    Pour tout $i$ dans $[|0,m-1|]$, nous définissons le $n$-uplet suivant.
    \begin{equation*}
        e_i:\left\{
            \begin{matrix}
                [|0,n-1|]&\longrightarrow&\mathbb{N}\\
                l&\mapsto&
                \frac{
                \#\{j\in[|0,o-1|]\quad| d_0(j)=i\wedge d_1(j)=l\}
            }{
                \#\{j\in[|0,o-1|]\quad| d_1(j)=l\}
            }\\
            \end{matrix}
            \right.
    \end{equation*}

    Nous pouvons alors écrire l'exactitude équilibré de la manière suivant :
    \begin{equation*}
        BA_{[|0,n-1|]}^d(h) = \frac{1}{n}
        \sum_{i=0}^{m-1} e_i(h(i))
    \end{equation*}
    Où $h\in B_{m\rightarrow n}$.
\end{lemma}
\begin{proof}
    Soit $l\in[|0,n-1|]$ et $h$, une fonction dans $B_{m\rightarrow n}$.
    \begin{align*}
        &
        \frac{
            \#\{j\in[|0,o-1|]\quad| h(d_0(j))=d_1(j)\wedge d_1(j)=l\}
        }{
            \#\{j\in[|0,o-1|]\quad| d_1(j)=l\}
        }\\
        =&
        \frac{
            \#\{j\in[|0,o-1|]\quad| h(d_0(j))=l\wedge d_1(j)=l\}
        }{
            \#\{j\in[|0,o-1|]\quad| d_1(j)=l\}
        }
    \end{align*}
    \begin{align*}
        =&
        \frac{
            \#\{j\in[|0,o-1|]\quad| h(d_0(j))=l\wedge d_1(j)=h(d_0(j))\}
        }{
            \#\{j\in[|0,o-1|]\quad| d_1(j)=l\}
        }
    \end{align*}
    \begin{align}
        \label{eq:sansi}
        =&
        \frac{
            \#\left(\{j\in[|0,o-1|]\quad| h(d_0(j))=l\}\cap\{j\in[|0,o-1|]\quad| d_1(j)=h(d_0(j))\}\right)
        }{
            \#\{j\in[|0,o-1|]\quad| d_1(j)=l\}
        }
    \end{align}

    Dans l'expression précédente, $l$ est un élément de l'ensemble des indices $F$.
    Pour montrer le résultat, on remplace $h(d_0(j))$~\ref{eq:sansi} par une expression qui contient $i$ : un élément de $E$.
    Le but de faire apparaître la quantité qui nous intéresse : $e_{i,j}$.

    Nous commençons par remarquer que pour tout $j$ dans $[|0,o-1|]$
    \begin{equation*}
        h(d_0(j))=l
        \Leftrightarrow d_0(j)\in h^{-1}(\{l\})
        \Leftrightarrow \exists i\in h^{-1}(\{l\}), d_0(j)=i
    \end{equation*}

    Ce qui signifie que 
    \begin{align*}
        &\left\{
            j\in[|0,o-1|]\quad| h(d_0(j)) = l
        \right\}\\
        =&\left\{
            j\in[|0,o-1|]\quad| \exists i\in h^{-1}(\{l\}), d_0(j)=i
        \right\}\\
    =&\bigcup_{i\in h^{-1}(\{l\})}
        \left\{
            j\in[|0,o-1|]\quad| d_0(j)=i
        \right\}
    \end{align*}

    Ainsi, par substitution de $\{j\in[|0,o-1|]\quad| h(d_0(j)) = l\}$ dans l'équation \ref{eq:sansi}, nous obtenons
    \begin{align*}
        &\frac{
            \#\left(
                \left(
                    \bigcup_{i\in h^{-1}(\{l\})}
                    \left\{
                        j\in[|0,o-1|]\quad| d_0(j)=i
                    \right\}
                \right)
                \cap\{j\in[|0,o-1|]\quad| d_1(j)=h(d_0(j))\}
            \right)
        }{
            \#\{j\in[|0,o-1|]\quad| d_1(j)=l\}
        }\\
        =&\frac{
            \#\left(
                \bigcup_{i\in h^{-1}(\{l\})}
                \left\{
                    j\in[|0,o-1|]\quad| d_0(j)=i
                    \wedge
                    d_1(j)=h(d_0(j))
                \right\}
            \right)
        }{
            \#\{j\in[|0,o-1|]\quad| d_1(j)=l\}
        }\\
        =&\sum_{i\in h^{-1}(\{l\})}
        \frac{
            \#\left\{
                j\in[|0,o-1|]\quad| d_0(j)=i
                \wedge
                d_1(j)=h(i)
            \right\}
        }{
            \#\{j\in[|0,o-1|]\quad| d_1(j)=h(i)\}
        }
    \end{align*}
    \begin{align}
        \label{eq:sumei}
        =&\sum_{i\in h^{-1}(\{l\})}
        e_i(h(i))
    \end{align}

    Ensuite, d'après la définition~\ref{def:BA} 
    \begin{equation*}
        BA_{[|0,n-1|]}^d(h) = \frac{1}{n}
            \sum_{l=0}^{n-1} 
            \frac{
                \#\left\{j\in [|0,o-1|]\quad| h(d_0(j))=d_1(j)\wedge d_1(j) = l\right\}
            }
            {\#\{j\in [|0,o-1|]\quad| d_1(j)=l\}}
    \end{equation*}

    Par substitution du terme générale de cette somme par le résultat obtenu dans l'équation~\ref{eq:sumei} :
    \begin{align*}
        &BA_{[|0,n-1|]}^d(h)\\
        =&\frac{1}{n}
        \sum_{l=0}^{n-1}\sum_{i\in h^{-1}(\{l\})} e_i(h(i))\\
        =&\frac{1}{n}
        \sum_{l=0}^{n-1}\sum_{i=0}^{m-1}1_{h^{-1}(\{l\})}(i) e_i(h(i))\\
        =&\frac{1}{n}
        \sum_{i=0}^{m-1} e_i(h(i))\sum_{l=0}^{n-1}1_{h^{-1}(\{l\})}(i)\\
    \end{align*}
    
    Comme $1_{h^{-1}(\{l\})}(i) = 1$ si et seulement si $l=h(i)$, nous avons  
    $\sum_{l=0}^{n-1}1_{h^{-1}(\{l\})}(i) = 1$.
    Ce qui donne le résultat attendu.
\end{proof}

Ce lemme nous permet de calculer l'argmax souhaité en calculant le entrée de la matrice $M = \left(e_i(l)\right)_{i\in[|0,m-1|],l\in[|0,m-1|]}$
au lieu de calculer l'exactitude équilibré de toutes le fonctions de  $B_{m\rightarrow n}$.
Nous cherchons donc le maximum de chaque ligne de $M$ ce qui fait que nous n'avons qu'a parcourir une fois chaque élément de $M$.
Nous formalisons cette idée dans le théorème suivant :

\begin{theorem}
    \label{th:fini-em}
    Soit $e_i$ le $n$-uplet de $\mathbb{N}$ suivant :
    \begin{equation*}
        e_i:\left\{
            \begin{matrix}
                [|0,n-1|]&\longrightarrow&\mathbb{N}\\
                l&\mapsto&
                \frac{
                \#\{j\in[|0,o-1|]\quad| d_0(j)=i\wedge d_1(j)=l\}
            }{
                \#\{j\in[|0,o-1|]\quad| d_1(j)=l\}
            }\\
            \end{matrix}
            \right.
    \end{equation*}
    Soit $f\in B_{m\rightarrow n}$ telle que pour tout $i$ dans $[|0,m-1|]$
    \begin{equation*}
        f(i) = \text{argmax}\left(e_i\right)
    \end{equation*}

    Alors
    \begin{equation*}
        f = \text{argmax}\left(BA_{[|0,n-1|]}^d\right)
    \end{equation*}
\end{theorem}

\begin{proof}
    Soit $g\in B_{m\rightarrow n}$. 
    Nous allons montrer que $BA_{[|0,n-1|]}^d(g)\leq BA_{[|0,n-1|]}^d(f)$.
    Nous commençons par dire que 
    pour tout $i\in[|0,n-1|]$, $0\leq e_i(g(i))\leq e_i(f(i))$.
    Ce qui donne que
    \begin{equation*}
        \sum_{i=0}^{m-1}e_i(g(i)) \leq \sum_{i=0}^{m-1}e_i(f(i))
    \end{equation*}
    et donc
    \begin{equation*}
        \frac{1}{n}\sum_{i=0}^{m-1}e_i(g(i)) \leq \frac{1}{n}\sum_{i=0}^{m-1}e_i(f(i))
    \end{equation*}

    Enfin, en appliquant le lemme~\ref{lem:sumei} nous avons le résultat attendu.
\end{proof}

En utilisant ce résultat, nous pouvons maintenant écrire l'algorithme suivant en $\mathcal{O}(onm)$ pour résoudre notre problème d'optimisation.

\begin{algorithm}
    \caption{Optimisation: recherche de l'$\text{argmax}\left(BA^d_{[|0,n-1|]}\right)$}
    \label{algo:argmax}
    \begin{algorithmic}
        \For{$i\gets 0,\cdots,m-1$} 
            \For{$l\gets 0,\cdots,n-1$}
                \State $e_{i,l}\gets
                \frac{
                \#\{j\in[|0,o-1|]\quad | d_0(j)=i\wedge d_1(j)=l\}
            }{
                \#\{j\in[|0,o-1|]\quad | d_1(j)=l\}
            }$
                \footnotesize
                \Comment{Calcul de $e_i(l)$}
                \normalsize
            \EndFor
        \EndFor
        \For{$i\gets 0,\cdots,n-1$}
            \State $f(i)\gets\text{argmax}_l(e_{i,l})$
            \footnotesize
            \Comment{Valeur de $l$ que maximise $e_{i,l}$}
            \normalsize
        \EndFor
        \State \Return $f$
    \end{algorithmic}
\end{algorithm}

\FloatBarrier
%Alogrithm \ref{algo:argmax} is an efficient algorithm to find a classifier the maximizes balanced accuracy on the set of indices. 
%From the result $f$ of this alogrithm we find a classifier that solves the problem of maximizing the balanced accuracy on element by applying the inversse of $\Phi$.
%Hence $\Phi^{-1}(f)$ is solution.
%Computing it requires $\mathcal{O}(on)$ operations resulting in an overall complexity of $\mathcal{O}(onm)$.

%This classifier algorithm is limited to finite feature space but there are cases where we can find workaround to still use it.
%For instance, by using clusturing prior to our method we can reduce to a finit feature space.
%Also, if $(E, O)$ is a sub-topology we can match any element of the englobing set to its nearest counterpart in $E$.
%We did that on LAW and COMPAS dataset and compare our approach to a random forest.


%The main takeaway from figures \ref{fig:ba} and \ref{fig:time} is that our finite classifier alogirthm outperforms state of the art in terms of balanced accuracy and is way faster at achieving this result.