diff options
Diffstat (limited to 'classification_finie')
| -rw-r--r-- | classification_finie/ba.tex | 78 | ||||
| -rw-r--r-- | classification_finie/finit_classif.tex | 58 | ||||
| -rw-r--r-- | classification_finie/tabular.tex | 32 |
3 files changed, 84 insertions, 84 deletions
diff --git a/classification_finie/ba.tex b/classification_finie/ba.tex index a9fcb78..c155a7a 100644 --- a/classification_finie/ba.tex +++ b/classification_finie/ba.tex @@ -1,17 +1,17 @@ -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}. +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 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. +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 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é. +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$. + 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 @@ -32,7 +32,7 @@ Nous proposons donc la définition suivante : 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, + 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}$ @@ -46,8 +46,8 @@ Nous proposons donc la définition suivante : \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}. + 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. @@ -93,13 +93,13 @@ Nous proposons donc la définition suivante : \begin{propriete} \label{prop:CCA_BA} - Les CCA ayant comme image $ F$ ont une exactitude équilibré égale à $\frac{1}{\# F}$. + 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 pause $\hat{Y} = f\circ X$ - L'exactitude équilibré de $f$ est alors + 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)\\ @@ -116,18 +116,18 @@ Nous proposons donc la définition suivante : \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. +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 à 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. + 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 suivant : +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éatoire suivantes : +nous définissons les variables aléatoires suivantes : $X=\textit{id}_E$ \begin{equation*} Y:\left\{ @@ -155,7 +155,7 @@ Ainsi que la fonction mesurable suivante qui est l'exemple de classifieur que no \right. \end{equation*} -Montrons que l'exactitude équilibré de $f$ vaut $\frac{1}{3}$. +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} @@ -173,14 +173,14 @@ En notant $\hat{Y} = f\circ X$, nous représentons cette situation par le tablea \end{equation*} Il nous permet de calculer facilement les quantités suivantes. -Déjà l'exactitude équilibré est égale à $\frac{1}{3}$ car +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 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 +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\{ @@ -193,12 +193,12 @@ En effet dans ce cas, supposons que l'exactitude équilibré vaille $0,5$, alors \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. +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é de $f$. + 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} @@ -208,7 +208,7 @@ En effet nous avons le résultat suivant : \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 : + 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} @@ -238,7 +238,7 @@ En effet nous avons le résultat suivant : 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$ : + Nous définissons les fonctions suivantes pour tout $z$ et $z'$, éléments de $F$ : \begin{equation*} h_{z,z'}:\left\{ \begin{matrix} @@ -254,17 +254,17 @@ En effet nous avons le résultat suivant : \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}$. + $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é de $f$ est égale $\frac{\text{Tr}(M)}{\#F}$. - $h_{z,z'}$ peut aussi s'exprimer en terme matricielle. + 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\{ @@ -304,8 +304,8 @@ En effet nous avons le résultat suivant : \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$. + 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$, @@ -334,7 +334,7 @@ Ainsi l'existence de $u$ est équivalente à l'existence d'une matrice $H = H_{i 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 +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\} @@ -366,7 +366,7 @@ Pour montrer l'inclusion précédente, il suffit alors de montrer que 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$. +$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 @@ -384,8 +384,8 @@ si $i<\varphi(i)$ alors =&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$. +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 @@ -437,7 +437,7 @@ 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)$. +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$. @@ -455,6 +455,6 @@ Il existe alors un $\#F$-uplet $u\in\mathcal{H}^{\#F}$ tel que \end{proof} -Nous allons construire un classifieur qui maximise l'exactitude équilibré. +Nous allons construire un classifieur qui maximise l'exactitude équilibrée. diff --git a/classification_finie/finit_classif.tex b/classification_finie/finit_classif.tex index c7c9fbf..b958275 100644 --- a/classification_finie/finit_classif.tex +++ b/classification_finie/finit_classif.tex @@ -1,10 +1,10 @@ \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$. -Soit $\varphi$ une bijection de $E$ dans $[|0,m-1|]$ et $\psi$ une bijection de $F$ dans $[|0,n-1|]$. +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ée en pratique comme il est utilisé en apprentissage automatique. -Nous pouvons alors construire un jeu de donnée d'indices : +$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} @@ -16,7 +16,7 @@ Nous pouvons alors construire un jeu de donnée d'indices : \begin{definition} \label{def:BA} - L'exactitude équilibré 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 + 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} @@ -26,8 +26,8 @@ Nous pouvons alors construire un jeu de donnée d'indices : {\#\{j\in [|0,o-1|]\quad| d_1(j)=y\}} \end{equation*} \end{definition} -Cette définition est un approximation de l'exactitude équilibré que nous avons définit plus haut. -\textbf{Le problème consiste à trouver une application $f:E\rightarrow F$ telle que l'exactitude équilibré de $f$ sur $d$ est maximal.} +Cette définition est une approximation de l'exactitude équilibrée que nous avons défini 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$. @@ -35,7 +35,7 @@ Pour simplifier un peu les notations, nous appellerons $B_{m\rightarrow n}$ l'en \begin{theorem} \label{th:bij} - Soient $E$ et $F$ deux ensemble finis de cardinaux $m$ et $n$. + 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} @@ -51,7 +51,7 @@ Pour simplifier un peu les notations, nous appellerons $B_{m\rightarrow n}$ l'en \right. \end{equation} - Montrons maintenant que $\Phi$ est un bijection. + 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 @@ -76,14 +76,14 @@ Pour simplifier un peu les notations, nous appellerons $B_{m\rightarrow n}$ l'en $\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 comptes les spécificités de objets mathématiques dans ses ensembles. -En effet, le théorème~\ref{th:bij} nous donne que pour chaque fonction des indices de $E$ vers les indices de $F$ nous pouvons trouver une unique fonction de de $E$ dans $F$. -Et la preuve étant constructive nous indique que pour trouver cette fonction nous pouvons utiliser $\Phi^{-1}$. +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 ses 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é quand on compose avec $\Phi$. + Étudions donc comment se comporte l'exactitude équilibrée quand on compose avec $\Phi$. \begin{theorem} \label{th:BAphi=BA} - Soit $E$ et $F$ deux ensembles finis. + Soient $E$ et $F$ deux ensembles finis. Soit $d$ un uplet de $E\times F$. Alors nous avons l'égalité suivante : \begin{equation*} @@ -96,7 +96,7 @@ Et la preuve étant constructive nous indique que pour trouver cette fonction no 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 bijections + 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$. @@ -127,7 +127,7 @@ Et la preuve étant constructive nous indique que pour trouver cette fonction no \Leftrightarrow &\left(f\circ d_0\right)(j) = d_1(j)\\ \end{align*} - Ce qui nous donnes les assertions suivantes : + Ce qui nous donne les assertions suivantes : \begin{equation} \label{eq:d1j} \forall j\in[|0,o-1|]\quad @@ -186,24 +186,24 @@ En utilisant le théorème~\ref{th:BAphi=BA} nous déduisons le corollaire suiva BA_{[|0,\#F-1|]}^{d'}(f') = BA_F^d(\Phi^{-1}(f'))$ \end{proof} -Grâce au corollaire~\ref{co:argmax} nous avons 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. +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 l'exactitude équilibré sur $B_{m\rightarrow n}$} +\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\}$. +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é pour toutes les fonctions de $B_{m\rightarrow n}$. +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}$ contiens $n^m$ éléments. -L'algorithme directe a donc une complexité de $\mathcal{O}(on^m)$ opérations. -Nous allons construire à la place un algorithme que garantie de maximiser l'exactitude équilibré en $\mathcal{O}(onm)$ opérations. +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é optimale. -Pour cela, dans le lemme qui suit nous allons reformuler l'exactitude équilibré. +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} @@ -222,7 +222,7 @@ Pour cela, dans le lemme qui suit nous allons reformuler l'exactitude équilibrà \right. \end{equation*} - Nous pouvons alors écrire l'exactitude équilibré de la manière suivant : + 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)) @@ -342,7 +342,7 @@ Pour cela, dans le lemme qui suit nous allons reformuler l'exactitude équilibrà {\#\{j\in [|0,o-1|]\quad| d_1(j)=l\}} \end{equation*} - Par substitution du terme générale de cette somme par le résultat obtenu dans l'équation~\ref{eq:sumei} : + 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} @@ -358,9 +358,9 @@ Pour cela, dans le lemme qui suit nous allons reformuler l'exactitude équilibrà Ce qui donne le résultat attendu. \end{proof} -Ce lemme nous permet de calculer l'argmax souhaité en calculant le 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é de toutes le fonctions de $B_{m\rightarrow n}$. -Nous cherchons donc le maximum de chaque ligne de $M$ ce qui fait que nous n'avons qu'a parcourir une fois chaque élément de $M$. +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 le 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} diff --git a/classification_finie/tabular.tex b/classification_finie/tabular.tex index 10af8c9..3f98b6b 100644 --- a/classification_finie/tabular.tex +++ b/classification_finie/tabular.tex @@ -1,9 +1,9 @@ -Dans cette section nous allons évaluer comme se comporte notre algorithme dans des cas d'usage pratiques. +Dans cette section nous allons évaluer comment se comporte notre algorithme dans des cas d'usage pratiques. \subsection{Classification de données tabulaires} Nous allons évaluer notre nouvel algorithme sur les jeux de données COMPAS et sur LAW. Nous présenterons plus en détail ces bases de données à la Section~\ref{sec:aia-méthodo-jeu}. -Disons pour le moment que COMPAS est un jeu tabulaire utilisé en justice prédictive pour créer des RAI comme nous les avons présenté en Section~\ref{sec:contexte-insti} et que LAW sert aux école de droit au États Unis pour sélectionner les étudiants en première année. +Disons pour le moment que COMPAS est un jeu tabulaire utilisé en justice prédictive pour créer des RAI comme nous les avons présentés en Section~\ref{sec:contexte-insti} et que LAW sert aux écoles de droit aux États-Unis pour sélectionner les étudiants en première année. Nous allons entraîner notre algorithme ainsi qu'une forêt aléatoire pour prédire si un coupable est récidiviste ou non sur COMPAS et pour prédire si un étudiant en droit va réussir l'examen du barreau par LAW. \begin{figure} @@ -17,15 +17,15 @@ Nous allons entraîner notre algorithme ainsi qu'une forêt aléatoire pour pré \caption{LAW} \end{subfigure} - \caption{Comparaison de l'exactitude équilibré entre une forêt aléatoire (random forest) et notre algorithme (finit classifier).} + \caption{Comparaison de l'exactitude équilibrée entre une forêt aléatoire (random forest) et notre algorithme (finit classifier).} \label{fig:ba} \end{figure} -Nous observons les résultats de l'exactitude équilibré sur la Figure~\ref{fig:ba}. -Les boîtes à moustache ont été obtenus grâce au processus de validations croisée\footnote{\textit{Cross validation}}. -Nous, n'observons pas de différence significative d'exactitude équilibré pour COMPAS, en revanche sur LAW notre algorithme est meilleur de plus de 10 points d'exactitude équilibré. +Nous observons les résultats de l'exactitude équilibrée sur la Figure~\ref{fig:ba}. +Les boîtes à moustache ont été obtenues grâce au processus de validations croisées\footnote{\textit{Cross validation}}. +Nous n'observons pas de différence significative d'exactitude équilibrée pour COMPAS ; en revanche sur LAW notre algorithme est meilleur de plus de 10 points d'exactitude équilibrée. Sur COMPAS nous observons que pour certaines étapes de validation la forêt aléatoire dépasse notre algorithme. -Cela ne vas pas à l'encontre du fait que notre algorithme produise la meilleur exactitude équilibré car cette assertion est vrai pour les données d'entraînement et ces résultats sont obtenus sur les donnes d'évaluations qui n'ont jamais été vus à l'entraînement. +Cela ne va pas à l'encontre du fait que notre algorithme produise la meilleure exactitude équilibrée car cette assertion est vraie pour les données d'entraînement et ces résultats sont obtenus sur les données d'évaluation qui n'ont jamais été vues à l'entraînement. \begin{figure} \centering @@ -42,7 +42,7 @@ Cela ne vas pas à l'encontre du fait que notre algorithme produise la meilleur \label{fig:time} \end{figure} -Comme nous l'avons vu à la Section~\ref{sec:contexte-conso} la consommation d'énergie est un enjeu capitale de l'IA. +Comme nous l'avons vu à la Section~\ref{sec:contexte-conso} la consommation d'énergie est un enjeu capital de l'IA. Nous avons donc enregistré le temps que prend l'ordinateur pour apprendre le modèle. Nous comparons donc notre algorithme à une forêt aléatoire dans la Figure~\ref{fig:time}. Nous utilisons l'implémentation de forêt aléatoire de scikit-learn~\cite{scikit-learn} sur un ordinateur portable Dell Latitude 5420 avec un processeur i7-1165G7 @ 2.8 GHz. @@ -50,15 +50,15 @@ Notre algorithme est trois fois plus rapide sur LAW et quatre fois plus rapide s \FloatBarrier \subsection{Classification de données disparates} -Les données disparates sont de formes et de types hétérogènes comme par exemple des images de dimension différentes. -C'est un cas courant qui se produit après avoir récupérer des données brute et rend l'application directe de la plus part des algorithme d'apprentissage automatique impossible sans prétraitement\footnote{\textit{Preprocessing}} ou intervention manuelle~\cite{ben2002theoretical}. -Notre algorithme développé plus haut ne soufre pas de tel problème car il nous travaillons uniquement sur le indices des éléments que l'on souhaite classifier. +Les données disparates sont de formes et de types hétérogènes comme par exemple des images de dimensions différentes. +C'est un cas courant qui se produit après avoir récupéré des données brutes et rend l'application directe de la plupart des algorithmes d'apprentissage automatique impossible sans prétraitement\footnote{\textit{Preprocessing}} ou intervention manuelle~\cite{ben2002theoretical}. +Notre algorithme développé plus haut ne soufre pas de tel problème car nous travaillons uniquement sur les indices des éléments que l'on souhaite classifier. -Nous explorons cet aspect avec l'expérience suivante : nous avons demandé à un panel d'utilisateur.ice.s de décrire en quelques mots les styles des tableaux de Paul Cezanne, un peintre impressionniste connu principalement pour ses tableaux de Provence. -Les utilisateur.ices.s ont vu défile les tableaux un-à -un. -Pour chaque tableau il.elle.s devaient remplir en champ de texte n'imposant aucune restriction. +Nous explorons cet aspect avec l'expérience suivante : nous avons demandé à un panel d'utilisateur.ice.s de décrire en quelques mots les styles des tableaux de Paul Cézanne, un peintre impressionniste connu principalement pour ses tableaux de Provence. +Les utilisateur.ices.s ont vu défiler les tableaux un-à -un. +Pour chaque tableau il.elle.s devaient remplir un champ de texte n'imposant aucune restriction. Cela a créé des réponses très hétérogènes comme par exemple \textit{Paul Alexis lisant à Émile Zola} montré en Figure~\ref{fig:zola} qui à été classifié comme \textquote{Hôpital psychiatrique}. -Les utilisateur.rice.s peuvent être vus comme l'ensemble des classifieurs faibles dont notre algorithme vas cumuler les prédiction pour un créer une qui crée consensus au sens de la maximisation de l'exactitude équilibré. +Les utilisateur.rice.s peuvent être vu.e.s comme l'ensemble des classifieurs faibles dont notre algorithme va cumuler les prédictions pour en créer une qui fai consensus au sens de la maximisation de l'exactitude équilibrée. C'est donc une méthode qui se rapproche de la votation. \begin{figure} @@ -68,6 +68,6 @@ C'est donc une méthode qui se rapproche de la votation. \label{fig:zola} \end{figure} -Nous obtenons un exactitude équilibré de 0,48 pour une évaluation sur 20 tableaux, soit un aléatoire à $\frac{1}{20}=0,005$. +Nous obtenons un exactitude équilibrée de 0,48 pour une évaluation sur 20 tableaux, soit un aléatoire à $\frac{1}{20}=0,005$. \FloatBarrier |