Le cas d'un classifieur constant, comme nous l'avons à 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érale 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 si 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 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é d'un potimarron à partir la couleur de mes chaussettes le jour pu 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})$, un 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 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 exactitude équilibré égale à $\frac{1}{\# F}$. \end{propriete} \begin{proof} Soit $f: E\rightarrow F$ un CCA. On pause $\hat{Y} = f\circ X$ L'exactitude équilibré 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 Proposition~\ref{prop:CCA_BA} nous apprend que si l'exactitude équilibré est différente de $0,5$ alors le classifieur n'est pas un CCA. Il est intéressant de noter que si un classifieur à une exactitude équilibré 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é 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 l'exactitude équilibré 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é 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 l'exactitude équilibré 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é é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 résultat suivant : \begin{theorem} \label{th:fini-bacca} En notant $BA(f)$ l'exactitude équilibré 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éfinissons 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 permettre et 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$ ai une exactitude équilibré 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 l'exactitude équilibré de $f$ est égale $\frac{\text{Tr}(M)}{\#F}$. $h_{z,z'}$ peut aussi s'exprimer en terme matricielle. 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 à intervertie 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$ intervertis 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ésultante des permutations contiennent les éléments sélectionnés par la bijections. Nous allons montrer qu'il existe une sélection 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é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é.