path: root/classification_finie/finit_classif.tex

\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$.
Soient $\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ées, comme il est en pratique utilisé en apprentissage automatique.
Nous pouvons alors construire un jeu de données 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ée 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 une approximation de l'exactitude équilibrée que nous avons définie plus haut.
\textbf{Le problème consiste à trouver une application $f:E\rightarrow F$ telle que l'exactitude équilibrée de $f$ sur $d$ est maximale.}

\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 ensembles 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 une 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 compte les spécificités des objets mathématiques dans ces ensembles.
En effet, le théorème~\ref{th:bij} nous dit que pour chaque fonction des indices de $E$ vers les indices de $F$ nous pouvons trouver une unique fonction 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ée quand on compose avec $\Phi$.
\begin{theorem}
    \label{th:BAphi=BA}
    Soient $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 bijection 
    $\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 donne 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 savons 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 de l'exactitude équilibrée 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ée 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}$ contient $n^m$ éléments.
L'algorithme direct a donc une complexité de $\mathcal{O}(on^m)$ opérations. 
Nous allons construire à la place un algorithme qui garantit de maximiser l'exactitude équilibrée 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ée optimale.
Pour cela, dans le lemme qui suit nous allons reformuler l'exactitude équilibrée.

\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ée 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éral 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 l'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ée de toutes les fonctions de  $B_{m\rightarrow n}$.
Nous cherchons donc le maximum de chaque ligne de $M$ ce qui fait que nous n'avons qu'à 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.