path: root/classification_finie/ba.tex

Le cas d'un classifieur constant, comme nous l'avons à la Section~\ref{sec:backgroung-ml-classif}, n'est qu'un exemple de Classifieur qui réalise un Choix Aléatoire (CCA).
En anglais la litterature parle en générale de \textit{random guess}~\cite{chicco2021matthews}.
Cependant, à notre conaissance, il n'y a pas de definition mathématique qui unifie l'idée générale de CCA qui est :
un classifieur qui se comporte comme si il n'avait aucune conaissance sur sa tâche de classification.
Un CCA n'est pas un classifieur qui utilise l'aléatoire mais plutot un classifieur hasardeux, comme une personne qui choisirai au hasard.
C'est le cas pour un classifieur constant mais aussi pour un classifieur binaire qui tire à pile ou face son résultat.

Nous pourrions dire qu'un CCA est un classifieur qui n'utilise pas les données d'entrée.
Cependant cela ne prend pas un compte le cas où les données d'entrée ne servent à rien pour la tâche de classification. 
Par exemple nous voudrions que notre définition englobe n'importe quelle classifieur qui cherche à prédire la qualitée d'un potimaron à partir la coleur de mes chaussettes le jour pù il a été ramassé.
Nous proposons donc la définition suivante :
\begin{definition}
    Un CCA est un classifieur ayant une prédiction indépendante de l'étiquette.
    C'est à dire que pour un classifeur $f: E\rightarrow F$.
    Avec une étiquette $Y:\Omega\rightarrow F$
    et une entrée $X:\Omega\rightarrow E$.
    Alors pour $\hat{Y}=f\circ X$, nous avons 
    $P_{(Y,\hat{Y})} = P_Y\otimes P_{\hat{Y}}$
\end{definition}
\begin{lemma}
    \label{lemme:aia-xycca}
    Soit $(\Omega,\mathcal{T},P)$ un espace probabilisé.
    Soient $X:(\Omega,\mathcal{T}) \rightarrow (E,\mathcal{E})$ et $Y:\Omega \rightarrow (F,\mathcal{F})$ des variables aléatoires.
    Les deux propositions suivantes sont équivalantes :
    \begin{enumerate}
        \item $P_{(X,Y)} = P_X\otimes P_Y$.
        \item Toute fonction mesurable $f:(E,\mathcal{T})\rightarrow (F,\mathcal{F})$ est un CCA pour prédire $Y$ à partir de $X$.
    \end{enumerate}
\end{lemma}
\begin{proof}
    En gardant les objets définis dans le Lemme~\ref{lemme:aia-xycca}.
    Nous allons prouver séparément les deux implications.
    \paragraph{$(1)\implies(2)$}
    Nous supposons que $P_{(X,Y)} = P_X\otimes P_Y$.
    Soit $f:(E,\mathcal{T})\rightarrow (F,\mathcal{F})$, un fonction mesurerable, 
    nous allons montrer que $f$ est un CCA, c'est-à dire que $P_{(f\circ X,Y)} = P_{f\circ X}\otimes P_Y$.

    Soient $(A,B)\in\mathcal{E}\times\mathcal{F}$
    \begin{align*}
        &P_{(f\circ X,Y)}(A,B)&\\
        =&P(\{f\circ X\in A\}\cap\{Y\in B\})&\\
        =&P(\{X\in f^{-1}(A)\}\cap\{Y\in B\})&\\
        &&\textit{Comme $X$ et $Y$ sont indépendantes.}\\
        =&P_X(f^{-1}(A))P_Y(B)&\\
        =&P_{f\circ X}(A)P_Y(B)&
    \end{align*}

    Ainsi, $\forall (A,B)\in\mathcal{E}\times\mathcal{F}~P_{(f\circ X,Y)}(A,B) = P_{f\circ X}(A)P_Y(B)$.
    D'après la définition de le mesure produit donnée à la Section~\ref{sec:background-proba}, nous avons donc bien $P_{(f\circ X,Y)} = P_{f\circ X}\otimes P_Y$.
    Ce qui est bien la définition de l'indépendant donnée en Section~\ref{sec:background-proba}.

    \paragraph{$(2)\implies (1)$}
    Nous supposons que tout classifieur de $Y$ à partir de $X$ est un CCA.
    Montrons que $P_{(X,Y)} = P_{f\circ X}\otimes P_Y$.
    Soit $(A,B)\in\mathcal{E}\times\mathcal{F}$.
    Nous allons montrer que 
    $P(X\in A\cap Y\in B) = P(X\in A)P(Y\in B)$.

    \paragraph{Cas 1 : $\mathcal{F}=\{\emptyset,F\}$}
    Si $B=\emptyset$ alors 
    $P(X\in A\cap Y\in B) = P(X\in A)P(Y\in B) = \emptyset$.
    Si $B=F$ alors 
    $P(X\in A\cap Y\in B) = P(X\in A)P(Y\in B) = P(X\in A)$.

    \paragraph{Cas 2 : $\#\mathcal{F}>2$}
    Alors il existe $C\in\mathcal{F}$ tel que $C\neq\emptyset$ et $F\backslash C\neq\emptyset$.
    Nous pouvons donc choisir $c$ dans $C$ et $c'$ dans $F\backslash C$.
    Nous construisons la fonction suivante:
    \begin{equation*}
        f:\left\{
            \begin{matrix}
                E\rightarrow F\\
                e\mapsto\left\{
                    \begin{matrix}
                        c~\text{si}~e\in A\\
                        c'~\text{sinon}
                    \end{matrix}
                \right.
            \end{matrix}
        \right.
    \end{equation*}
    Alors $f:(E,\mathcal{E})\rightarrow (F,\mathcal{F})$ est une fonction mesurable et $f^{-1}(C) = A$.
    Ainsi
    \begin{align*}
        &P(X\in A\cap Y\in B)\\
        =&P(X\in f^{-1}(C)\cap Y\in B)\\
        \text{Comme $f$ est un CCA.}&\\
        =&P(f\circ X\in C)P(Y\in B)\\
        =&P(X\in A)P(Y\in B)
    \end{align*}

\end{proof}

\begin{propriete}
    \label{prop:CCA_BA}
    Les CCA ayant comme image $ F$ ont une \textit{balanced accuracy} égale à $\frac{1}{\# F}$.
\end{propriete}

\begin{proof}
    Soit $f: E\rightarrow F$ un CCA.
    On pause $\hat{Y} = f\circ X$
    La \textit{balanced accuracy} de $f$ est alors
    \begin{align*}
        &\frac{1}{\# F}\sum_{y\in F}
        P(\hat{Y}=y\mid Y=y)\\
        =&\frac{1}{\# F}\sum_{y\in F}
        \frac{P(\{\hat{Y}=y\}\cap \{Y=y\})}{P(Y=y)}\\
        =&\frac{1}{\# F}\sum_{y\in F}
        \frac{P_{(\hat{Y},Y)}(\{y\}\times \{y\})}{P(Y=y)}\\
        \text{Comme $f$ est un CCA.}\\
        =&\frac{1}{\# F}\sum_{y\in F}
        \frac{P(\hat{Y}=y)P(Y=y)}{P(Y=y)}\\
        =&\frac{1}{\# F}\sum_{y\in F}
        P(\hat{Y}=y)\\
        =&\frac{1}{\# F}
    \end{align*}
\end{proof}

La contraposé de la Propositon~\ref{prop:CCA_BA} nous apprend que si la \textit{balanced accuracy} est différente de $0,5$ alors le classifieur n'est pas un CCA.

    Il est interessant de noter que si un classifieur à une \textit{balanced accuracy} de $\frac{1}{\#F}$ il n'est pas necessaire qu'il soit un CCA. 
    Pour prouver cette remarque il suffit de trouver un exemple de classifieur ayant une \textit{balanced accuracy} de $\frac{1}{\#F}$ et qui ne soit pas un CCA.

Nous appelons $r(a,b)$ le reste de la division euclidienne de $a$ par $b$.
Soient les ensembles suivant :
$E = [|0,8|]$ et
$F = [|0,2|]$.
En considérant l'espace probabilisé
$(E,\mathcal{P}(E),\frac{1}{9}\sum_{i=0}^8\delta_{i})$
nous définissons les variables aléatoire suivantes :
$X=\textit{id}_E$
\begin{equation*}
    Y:\left\{
        \begin{matrix}
            E\rightarrow F\\
            e\mapsto r(e,3)
        \end{matrix}
    \right.
\end{equation*}

Ainsi que la fonction mesurable suivante qui est l'exemple de classifieur que nous exhibons pour montrer la remarque :
\begin{equation*}
    f:\left\{
        \begin{matrix}
            E\rightarrow F\\
            e\mapsto \left\{
                \begin{matrix}
                    r(e,3)~\text{si $e<3$}\\
                    r(e+1,3)~\text{si $3\leq e<6$}\\
                    r(e+2,3)~\text{si $6\leq e<8$}\\
                    0~\text{sinon}
                \end{matrix}
                \right.
        \end{matrix}
    \right.
\end{equation*}

Montrons que la \textit{balanced accuracy} de $f$ vaut $\frac{1}{3}$. 
En notant $\hat{Y} = f\circ X$, nous réprésentons cette situation par le tableau suivant.
\begin{equation*}
    \begin{matrix}
        X&Y&\hat{Y}\\
        0&0&0\\
        1&1&1\\
        2&2&2\\
        3&0&1\\
        4&1&2\\
        5&2&0\\
        6&0&2\\
        7&1&0\\
        8&2&0
    \end{matrix}
\end{equation*}

Il nous permet de calculer facilement les quantités suivantes.
Déjà la \textit{balanced accuracy} est égale à $\frac{1}{3}$ car
$\forall y\in F~P(\hat{Y}=y\mid Y=y)=\frac{1}{3}$.
Enfin nous voyons que $f$ n'est pas un CCA car 
$P(\hat{Y}=1\cap Y=2) = 0$ et 
$P(\hat{Y}=1)P(Y=2) = \frac{2}{9}\frac{1}{3} = \frac{2}{27}$.

Remarquons que le réciproque de la Propriété~\ref{prop:CCA_BA} est vrai dans le cas d'une classifieur binaire, c'est-à dire $\#F=2$.
En effet dans ce cas, supposons que la \textit{balanced accuracy} vale $0,5$, alors
\begin{align*}
    &P(f\circ X=0\mid Y=0)+P(f\circ X=1\mid Y=1) = 1\\
    \implies&\left\{
        \begin{matrix}
            &P(f\circ X=1\mid Y=0)=P(f\circ X=1\mid Y=1)\\      
            \text{et}&\\
            &P(f\circ X=0\mid Y=0)=P(f\circ X=0\mid Y=1)      
        \end{matrix}
        \right.\\
    \implies&\text{$f$ est un CCA}
\end{align*}

Bien qu'une \textit{balanced accuracy} égale à $\frac{1}{\#F}$ ne soit pas un critère de CCA, nous pouvons utiliser cette métrique pour savoir si il existe un classifieur qui soit un CCA. 
En effet nous avons le resultat suivant :

\begin{theorem}
    \label{th:fini-bacca}
    En notant $BA(f)$ la \textit{balanced accuracy} de $f$.
    \begin{equation*}
        \forall f~BA(f)=\frac{1}{\#F} \iff
        \forall f~\text{$f$ est un CCA}
    \end{equation*}
\end{theorem}

\begin{proof}
    L'implication réciproque est une conséquence directe de la Propriété~\ref{prop:CCA_BA}.

    Pour le sens directe, nous allons montrer la contraposée, c'est à dire l'assertion suivante :
    \begin{equation*}
        \exists f~\text{$f$ n'est pas un CCA} \implies
        \exists f~BA(f)\neq \frac{1}{\#F}
    \end{equation*}

    Nous avons donc $E$ un ensemble et $F$ un ensemble fini.
    Nous avons les variables aléatoires $X:\Omega\rightarrow E$
    et $Y:\Omega\rightarrow \mathcal{P}(F)$.
    Nous supposons que nous avons $f:(E,\mathcal{E})\rightarrow (F,\mathcal{F})$, une fonction mesurable qui ne soit pas un CCA pour prédire $Y$ en utilisant $X$.

    Nous avons donc $(A,B)\in{\mathcal{P}(F)}^2$ tel que 
    \begin{equation*}
        P(f\circ X\in A\cap Y\in B)\neq P(f\circ X\in A)P(Y\in B)
    \end{equation*}

    Or
    \begin{equation*}
        P(f\circ X\in A\cap Y\in B) = \sum_{a\in A}\sum_{b\in B}P(f\circ X=a\cap Y=b)
    \end{equation*}
    et
    \begin{equation*}
        P(f\circ X\in A)P(\cap Y\in B) = \sum_{a\in A}\sum_{b\in B}P(f\circ X=a)P(Y=b)
    \end{equation*}
    Ainsi
    \begin{equation*}
        \exists (a,b)\in A\times B~
        P(f\circ X=a\cap Y=b)\neq P(f\circ X=a)P(Y=b)
    \end{equation*}

    Nous définisson les fonctions suivante pour tout $z$ et $z'$, éléments de $F$ :
    \begin{equation*}
        h_{z,z'}:\left\{
            \begin{matrix}
                F\rightarrow F\\
                y\mapsto \left\{
                    \begin{matrix}
                        &z&\text{si}&y=z'\\
                        &z'&\text{si}&y=z\\
                        &y&\text{sinon}&
                    \end{matrix}
                    \right.
            \end{matrix}
            \right.
    \end{equation*}

    $h_{z,z'}$ vas nous permetre et permuter les inférences faitent par $f$.
    Ainsi à partir de $f$ nous créons de nouveaux classifieurs.
    Soit $\mathcal{H}=\{h_{z,z'}\mid (z,z')\in F^2\}$ nous allons montrer qu'il existe $\#F$-uplet de $\mathcal{H}$, $u$, tel que le classifieur $u_{\#F-1}\circ\cdots\circ u_0\circ f$ ai une \textit{balanced accuracy} différent de $\frac{1}{\#F}$.

    Considérons la matrice
    \begin{equation*}
        M_f(i,j) = P(f\circ X=y_i\mid Y=y_j)
    \end{equation*}
    Où $y_\square:\#F\rightarrow F$ est une bijection.
    Alors la \textit{balanced accuracy} de $f$ est égale $\frac{\text{Tr}(M)}{\#F}$.
    $h_{z,z'}$ peut aussi s'exprimer en terme matriciel.
    La fonction suivainte est une bijection :
    \begin{equation*}
        \Phi:\left\{
            \begin{matrix}
                \mathcal{H}\rightarrow\mathcal{H}'\\
                h_{y_i,y_j}\mapsto H_{i,j}
            \end{matrix}
            \right.
    \end{equation*}
    Où $\mathcal{H}'=\{H_{i,j}\mid(i,j)\in\#F^2\}$ avec
    \begin{equation*}
        H_{i,j} = \left(
        \begin{matrix}
            %1&&&&&&&&&\\
            \ddots&&&&&&&&\\
            &1&&&&&&&\\
            &&0&&&&1&&\\
            &&&1&&&&&\\
            &&&&\ddots&&&&\\
            &&&&&1&&&\\
            &&1&&&&0&&\\
            &&&&&&&1&\\
            &&&&&&&&\ddots\\
            %&&&&&&&&&&1
        \end{matrix}
        \right)
        \begin{matrix}
            \\
            \\
            i\\
            \\
            \\
            \\
            j\\
            \\
            \\
        \end{matrix}
    \end{equation*}

    De plus, $M_{h_{y_i,y_j}\circ f}$ correspond à intervertire les lignes des $M_f$,
    c'est-à dire que $M_{h_{y_i,y_j}\circ f} = H_{i,j}M_f$.
    En effet, $h_{y_i,y_j}$ est une bijection telle que 
    $h_{y_i,y_j}^{-1} = h_{y_i,y_j}$.
    Alors, soit $(k,l)\in\#F^2$,
    \begin{align*}
        &M_{h_{y_i,y_j}\circ f}(k,l)\\
        =&P\left(h_{y_i,y_j}\circ f\circ X=y_k\mid Y=y_l\right)\\
        =&P\left(f\circ X=h_{y_i,y_j}(y_k)\mid Y=y_l\right)\\
        =&\left\{
            \begin{matrix}
                P\left(f\circ X=y_i\mid Y=y_l\right)&\text{si}& k=j\\
                P\left(f\circ X=y_j\mid Y=y_l\right)&\text{si}&k=i\\
                P\left(f\circ X=y_k\mid Y=y_l\right)&\text{sinon}&
            \end{matrix}
        \right.\\
        =&\left\{
            \begin{matrix}
                M(i,l)&\text{si}&k=j\\
                M(j,l)&\text{si}&k=i\\
                M(k,l)&\text{sinon}&
            \end{matrix}
        \right.\\
        &=H_{i,j}M_f(k,l)
    \end{align*}

Ainsi l'existence de $u$ est équivalante à l'existance d'une matrice $H = H_{i_{\#F-1},j_{\#F-1}}\cdots H_{i_0,j_0}$ telle que $\text{Tr}(HM_f)\neq 1$.
Montrons l'existence d'une telle matrice $H$.

Commencons par montrer que pour chaque ligne de $M_f$ il est possible de choisir arbitrairement l'élement de la ligne qui sera dans la diagonale de $HM_f$ tant qu'on ne choisit pas deux fois un élément dans une même colone.
C'est-à dire montrons que 
\begin{align*}
    \{\{M(i,\varphi(i))\mid i\in\#F\}\mid \text{$\varphi$ est une bijection sur $\#F$}\}\\
    \subset\{\text{Diag}(HM_f)\mid \exists I\in \left(\mathcal{H}'\right)^{\#F}~H=I_{\#F-1}\cdots I_0\}
\end{align*}
Soit $\varphi$ une bijection sur $\#F$, nous posons 
\begin{equation*}
    \psi:\left\{
        \begin{matrix}
            \#F\rightarrow \#F\\
            i\mapsto \left\{
                \begin{matrix}
                    \varphi^{-1}(i)&\text{si}&\varphi^{-1}(i)\geq i\\
                    \varphi^{-1}\left(\varphi^{-1}(i)\right)&\text{sinon}&
                \end{matrix}
                \right.
        \end{matrix}
        \right.
\end{equation*}
Nous posons 
\begin{equation}
    \label{eq:fini-H}
    H=H_{\psi(\#F-1),\#F-1}\cdots H_{\psi(1),1}H_{\psi(0),0}
\end{equation}
Pour montrer l'inclusion précédente, il suffit alors de montrer que 
\begin{equation*}
\{M(i,\varphi(i))\mid i\in\#F\} = 
\text{Diag}(HM_f)
\end{equation*}
Montrons donc que 
$\forall i\in\#F~M_f(i,\varphi(i))=HM_f(\varphi(i),\varphi(i))$.
Soit $i\in\#F$.
$H$ intervertis les lignes de $M_f$, la colone $\varphi(i)$ est à la même place dans $M_f$ et dans $HM_f$.
Il suffit donc de montrer que la $i$ème ligne de $M_f$ est la $\varphi(i)$ème de $HM_f$.
Isolons les termes qui modifient la position de la $i$ème ligne de $H$.
Si $i\geq\varphi(i)$ alors 
\begin{align*}
    &HM_f(\varphi(i),\varphi(i))\\
    =&H_{\psi(\varphi(i)),\varphi(i)}M_f(\varphi(i),\varphi(i))\\
    =&H_{i,\varphi(i)}M_f(\varphi(i),\varphi(i))\\
    =&M_f(i,\varphi(i))
\end{align*}
si $i<\varphi(i)$ alors
\begin{align*}
    &HM_f(\varphi(i),\varphi(i))\\
    =&H_{\psi(\varphi(i)),\varphi(i)}H_{\varphi^{-1}(i),i}M_f(\varphi(i),\varphi(i))\\
    =&H_{\varphi^{-1}(i),\varphi(i)}H_{\varphi^{-1}(i),i}M_f(\varphi(i),\varphi(i))\\
    =&M_f(i,\varphi(i))
\end{align*}

Ainsi grâce à l'Equation~\ref{eq:fini-H}, pour toute bijection sur $\#F$ nous pouvons construir une suite de $\#F$ permutations de lignes telle que la diagonale de la matrice résultante des permutations contienent les éléments sélectionés par la bijections.
Nous allons montrer qu'il existe une séléction d'éléments telle que la somme de ses éléments soit différente de $1$.
Pour ce faire, nous allons montrer la proposition ($\dag$) : si toutes les séléctions donnent une somme égale à $1$ alors necessairement tous les élement de chaque ligne de $M_f$ sont égaux entre eux.

Supposons donc, que pour toutes les bijections $\varphi$ sur $\#F$, nous ayons 
\begin{equation*}
    \sum_{i\in\#F}M_f(i,\varphi(i)) = 1
\end{equation*}
Nous savons qu'il existe $\#F!$ bijections sur $\#F$.
De plus, 
\begin{equation*}
    \forall j\in\#F~\sum_{i\in\#F}M_f(i,j)=
    \sum_{i\in\#F}P(f\circ X=y_i\mid Y=y_j) =1
\end{equation*}

Ces deux conditions impliquent que pour toute ligne $i$ et colone $j$ :
\begin{align*}
    &\sum_{\varphi\in B(i,j)}\sum_{k\in\#F}M_f(k,\varphi(k))
    +\sum_{k\in\#F}M_f(k,j) = (\#F-1)!+1\\
    \iff&
    ((\#F-1)!+1)M(i,j)+
    \sum_{k\in\#F\backslash\{i\}}M_f(k,j) + 
    \sum_{\varphi\in B(i,j)}M_f(k,\varphi(k))\\
    &= (\#F-1)!+1\\
    \iff&
    ((\#F-1)!+1)M(i,j)+
    \sum_{k\in\#F\backslash\{i\}}M_f(k,j) 
    \sum_{l\in\#F}M_f(k,l)
    = (\#F-1)!+1\\
    \iff&
    M(i,j)
    = 
    \frac{1}{(\#F-1)!+1}
    \left(
    (\#F-1)!+1-
    \sum_{k\in\#F\backslash\{i\}} 
    \sum_{l\in\#F}M_f(k,l)
    \right)
\end{align*}

Ainsi $\exists u \forall j\in\#F~M(i,j)= u$, cela achève la preuve de la proposition ($\dag$).
Or dans notre cas nous avons $(a,b)\in A\times B$
\begin{equation*}
    P(f\circ X=a\cap Y=b)\neq P(f\circ X=a)P(Y=b)
\end{equation*}
Ainsi, comme nous avons $(i,j)\in\#F^2$ tel que $y_i=a \wedge y_j=b$,
\begin{equation*}
    P(f\circ X=y_i\mid Y=y_j)\neq P(f\circ X=y_i)
\end{equation*}
Et donc, il existe $k\in\#F$ tel que
\begin{equation*}
    P(f\circ X=y_i\mid Y=y_j)\neq P(f\circ X=y_i\mid Y=y_k)
\end{equation*}
C'est à dire que $M_f(i,j)=\neq M_f(i,k)$.

D'après la contraposée de la propostion ($\dag$), nous avons une selection $\varphi$ telle que 
$\sum_{i\in\#F}M(\varphi(i),\varphi(i))\neq 1$.
Donc en définisant $H$ de la même manière qu'à l'Equation~\ref{eq:fini-H} nous avons $\text{Tr}(HM_f)\neq 1$.
Il existe alors un $\#F$-uplet $u\in\mathcal{H}^{\#F}$ tel que 
, pour 
\begin{equation*}
    g = u_{\#F-1}\circ\cdots\circ u_0\circ f
\end{equation*}
\begin{equation*}
    BA(g)\neq \frac{1}{\#F}
\end{equation*}



\end{proof}

Nous allons construire un classifieur qui maximise la \textit{balanced accuracy}.