\subsection{Notations}
%\begin{itemize}
    %\item $(x_0,x_1,\cdots,x_n)\in X_0\times X_1 \times\cdots\times X_n$
    %\item If $A$ is a finite set, then $\# A$ denotes the cardinal number of $A$
    %\item $f:\left\{\begin{matrix}A&\rightarrow &B\\ a&\mapsto & f(b)\end{matrix}\right.$ 
    %        Denotes a function from $A$ to $B$ mapping each element $a$ in $A$ to $f(a)$ in $B$.
    %\item $f\circ g$ is the composition of $f$ and $g$.
    %\item $f^{-1}$ can be either the inverse function of $f$ if $f$ is a bijection or its inverse image otherwise.
%\end{itemize}

\subsection{Problem setup}
Nous nous donnons deux ensembles finits, 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 apprantissage 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}
    La \textit{balanced accuracy} empirique de $f$ sur le $o$-uplet $d$ relativements à $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 la \textit{balanced accuracy} qui nous avons définit plus haut.
\textbf{Le problème consiste à trouver une application $f:E\rightarrow F$ telle que la \textit{balanced accuracy} de $f$ sur $d$ et maximal.}

\subsection{D'un proclème sur les élément à un problème sur les indices}

Nous commencons par noter par $B_{E\rightarrow F}$ l'ensemble des fonctions de $E$ dans $F$.
Pour simplifier un peu les notations, nous appelerons $B_{m\rightarrow n}$ l'ensemble des fnoctins 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 injéctive et surjéctive : c'est une bijection.
\end{proof}

$\varphi$ et $\psi$ peuvent être vus comme des indives sur $E$ et $F$.
Par exemple, chaque élément $e$ dans $E$ a un unqiue index $\varphi(e)$.
Cette étape d'abstraction nous permet de contruire 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}$.

    Etudions donc comment se comporte la \textit{balanced accuracy} 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ée suivante :
    \begin{equation*}
        BA^{d'}_{[|0,\#F-1|]}\circ\Phi = BA^d_F
    \end{equation*}
\end{theorem}

\begin{proof}
    Soit $E$ et $F$ deux ensemle finis.
    Nous avons deux bijections :
    We have two bijections : 
    $\varphi$ de $E$ dans $[|0,\#E-1|]$ et
    $\psi$ de $F$ dans $[|0,\#F-1|]$.
    Avec ces deux fonctions nous allons contruire 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 élements 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*}

    Ansin avec les equations \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'experession~\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 corollère 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 corollère~\ref{co:argmax} nous avons que, pour résoudres le problème de classification sur n'importe quel ensemble, il est suffisant de le résoudre sur l'ensemble d'indices correspondant.
L'objetif de la prochaine section est donc la recherche d'un algortihme de résolution d'un tel problème.

\subsection{Contruiction d'un algorithme de classification 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|]$.
Come nous savons que nous allons travailler sur les indices, nous ne nous préocupons pas d'ensembles quelconqus $E$ et $F$ comme à la section précedente.
A la place nous prenons $E=\{0,1,\cdots,m-1\}$ and $F=\{0,1,\cdots,n-1\}$.

L'aproche la plus directe pour maximiser $BA_{[|0,n-1|]}^d$ serait l'algorithme qui consiste à essayer de calculer la \textit{balanced accuracy} pour toutes les fonctions de $B_{m\rightarrow n}$.
Cette methode est viable pour des petites valeures de $m$ et $n$ mais devient rapidement impossible à calculer pour des grandes valeures.
En effet, par denombrement nous savons que $B_{m\rightarrow n}$ contiens $n^m$ éléments.
L'algorithme directe à donc une complexite de $\mathcal{O}(on^m)$ operations. 
Nous allons construire à la place un algoritheme que garantie de maximiser la \textit{balanced accuracy} en $\mathcal{O}(onm)$ operations.

Pour le constuire nous allons, d'une certaine manière, distribuer l'opératuer argmax, simplifiant ainsi l'expression de la \textit{balanced accuracy} optimale.
Pour cela, dans le lemme qui suit nous allons reformuler la \textit{balanced accuracy}.

\begin{lemma}
    \label{lem:sumei}
    Pour tout $i$ dans $[|0,m-1|]$, nous definissons 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 écrir la \textit{balanced accuracy} 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*}
    Where $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 indeices $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 aparaitre la quantité qui nous intersse : $e_{i,j}$.

    Nous commencons 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*}

    Aninsi, 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 calcule la \textit{balanced accuracy} 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}
    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 commencons 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 attedu.
\end{proof}

En utiliant ce résulat, nous pouvons maintenant écrir l'algorithm 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
\subsection{Extention to unseen data}
%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.