Preuve existe f pas cca equivalant exists f BA pas randomguess

2 files changed, 373 insertions, 0 deletions

diff --git a/classification_finie/ba.tex b/classification_finie/ba.tex
new file mode 100644
index 0000000..7069668
--- /dev/null
+++ b/classification_finie/ba.tex
@@ -0,0 +1,372 @@
+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{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}$
+
+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}
+    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 $\text{Tr}(M)$.
+    $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}.
+
+
diff --git a/classification_finie/finit_classif.tex b/classification_finie/finit_classif.tex
index f518cdc..df1fb9f 100644
--- a/classification_finie/finit_classif.tex
+++ b/classification_finie/finit_classif.tex
@@ -377,6 +377,7 @@ Nous cherchons donc le maximum de chaque ligne de $M$ ce qui fait que nous n'avo
 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\{