path: root/classification_finie/ba.tex

Le cas d'un classifieur constant, comme nous l'avons vu à la Section~\ref{sec:background-ml-classif}, n'est qu'un exemple de Classifieur qui réalise un Choix Aléatoire (CCA).
En anglais, la littérature parle en général de \textit{random guess}~\cite{chicco2021matthews}.
Cependant, à notre connaissance, il n'y a pas de définition mathématique qui unifie l'idée générale de CCA qui est :
un classifieur qui se comporte comme s'il n'avait aucune connaissance sur sa tâche de classification.
Un CCA n'est pas un classifieur qui utilise l'aléatoire mais plutôt un classifieur hasardeux, comme une personne qui choisirait 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 en 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 quel classifieur qui cherche à prédire la qualité d'un potimarron à partir de la couleur de mes chaussettes le jour où 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 classifieur $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 équivalentes :
    \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})$, une fonction mesurable, 
    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 la 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épendance 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 exactitude équilibrée égale à $\frac{1}{\# F}$.
\end{propriete}

\begin{proof}
    Soit $f: E\rightarrow F$ un CCA.
    On pose $\hat{Y} = f\circ X$
    L'exactitude équilibrée 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ée de la Proposition~\ref{prop:CCA_BA} nous apprend que si l'exactitude équilibrée est différente de $0,5$ alors le classifieur n'est pas un CCA.

    Il est intéressant de noter que si un classifieur a une exactitude équilibrée de $\frac{1}{\#F}$ il n'est pas nécessaire qu'il soit un CCA. 
    Pour prouver cette remarque il suffit de trouver un exemple de classifieur ayant une exactitude équilibrée 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 suivants :
$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éatoires 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 l'exactitude équilibrée de $f$ vaut $\frac{1}{3}$. 
En notant $\hat{Y} = f\circ X$, nous repré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à l'exactitude équilibrée 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 la réciproque de la Propriété~\ref{prop:CCA_BA} est vraie dans le cas d'un classifieur binaire, c'est-à-dire $\#F=2$.
En effet, dans ce cas, supposons que l'exactitude équilibrée vaille $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 exactitude équilibrée égale à $\frac{1}{\#F}$ ne soit pas un critère de CCA, nous pouvons utiliser cette métrique pour savoir s'il existe un classifieur qui soit un CCA. 
En effet nous avons le résultat suivant :

\begin{theorem}
    \label{th:fini-bacca}
    En notant $BA(f)$ l'exactitude équilibrée 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 direct, 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éfinissons les fonctions suivantes 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'}$ va nous permettre de permuter les inférences faites 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$ ait une exactitude équilibrée différente 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 l'exactitude équilibrée de $f$ est égale $\frac{\text{Tr}(M)}{\#F}$.
    $h_{z,z'}$ peut aussi s'exprimer en terme matriciel.
    La fonction suivante 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 à intervertir 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 équivalente à l'existence 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$.

Commençons par montrer que pour chaque ligne de $M_f$ il est possible de choisir arbitrairement l'élément 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 colonne.
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$ intervertit les lignes de $M_f$, la colonne $\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 construire une suite de $\#F$ permutations de lignes telle que la diagonale de la matrice résultant des permutations contienne les éléments sélectionnés par la bijection.
Nous allons montrer qu'il existe une sélection d'éléments telle que la somme de ces éléments soit différente de $1$.
Pour ce faire, nous allons montrer la proposition ($\dag$) : si toutes les sélections donnent une somme égale à $1$ alors nécessairement tous les éléments 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 colonne $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 proposition ($\dag$), nous avons une sélection $\varphi$ telle que 
$\sum_{i\in\#F}M(\varphi(i),\varphi(i))\neq 1$.
Donc en définissant $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 l'exactitude équilibrée.