Jan check du classification fini

1 files changed, 44 insertions, 58 deletions

diff --git a/classification_finie/finit_classif.tex b/classification_finie/finit_classif.tex
index df1fb9f..c7c9fbf 100644
--- a/classification_finie/finit_classif.tex
+++ b/classification_finie/finit_classif.tex
@@ -1,20 +1,9 @@
-
-\subsection{Notations}
-%\begin{itemize}
-    %\item $(x_0,x_1,\cdots,x_n)\in X_0\times X_1 \times\cdots\times X_n$
-    %\item If $A$ is a finite set, then $\# A$ denotes the cardinal number of $A$
-    %\item $f:\left\{\begin{matrix}A&\rightarrow &B\\ a&\mapsto & f(b)\end{matrix}\right.$ 
-    %        Denotes a function from $A$ to $B$ mapping each element $a$ in $A$ to $f(a)$ in $B$.
-    %\item $f\circ g$ is the composition of $f$ and $g$.
-    %\item $f^{-1}$ can be either the inverse function of $f$ if $f$ is a bijection or its inverse image otherwise.
-%\end{itemize}
-
-\subsection{Problem setup}
-Nous nous donnons deux ensembles finits, un ensemble $E$ de données d'entrée et un espace d'étiquette $F$.
+\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|]$.
+Soit $\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 apprantissage automatique.
+$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 :
 \begin{equation*}
     d' : \left\{
@@ -27,7 +16,7 @@ Nous pouvons alors construire un jeu de donnée d'indices :
 
 \begin{definition}
     \label{def:BA}
-    La \textit{balanced accuracy} empirique de $f$ sur le $o$-uplet $d$ relativements à $F$, que l'on appelle $BA_F^d(f)$, est un nombre dans $[0,1]$ tel que 
+    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 
     \begin{equation*}
         BA_F^d(f) = \frac{1}{n}
             \sum_{y\in F} 
@@ -37,13 +26,12 @@ 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 la \textit{balanced accuracy} qui nous avons définit plus haut.
-\textbf{Le problème consiste à trouver une application $f:E\rightarrow F$ telle que la \textit{balanced accuracy} de $f$ sur $d$ et maximal.}
-
-\subsection{D'un proclème sur les élément à un problème sur les indices}
+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.}
 
-Nous commencons par noter par $B_{E\rightarrow F}$ l'ensemble des fonctions de $E$ dans $F$.
-Pour simplifier un peu les notations, nous appelerons $B_{m\rightarrow n}$ l'ensemble des fnoctins de $[|0,m-1|]$ dans $[|0,n-1|]$.
+\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$.
+Pour simplifier un peu les notations, nous appellerons $B_{m\rightarrow n}$ l'ensemble des fonctions de $[|0,m-1|]$ dans $[|0,n-1|]$.
 
 \begin{theorem}
     \label{th:bij}
@@ -83,33 +71,32 @@ Pour simplifier un peu les notations, nous appelerons $B_{m\rightarrow n}$ l'ens
     \psi\circ\psi^{-1}\circ g\circ\varphi\circ\varphi^{-1} = g$
     Ainsi $\Phi$ est surjective. 
 
-    En conclusion $\Phi$ est à la fois injéctive et surjéctive : c'est une bijection.
+    En conclusion $\Phi$ est à la fois injective et surjective : c'est une bijection.
 \end{proof}
 
-$\varphi$ et $\psi$ peuvent être vus comme des indives sur $E$ et $F$.
-Par exemple, chaque élément $e$ dans $E$ a un unqiue index $\varphi(e)$.
-Cette étape d'abstraction nous permet de contruire des fonctions explicites de $E$ dans $F$ sans prendre en comptes les spécificités de objets mathématiques dans ses ensembles.
+$\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}$.
 
-    Etudions donc comment se comporte la \textit{balanced accuracy} quand on compose avec $\Phi$.
+    Étudions donc comment se comporte l'exactitude équilibré quand on compose avec $\Phi$.
 \begin{theorem}
     \label{th:BAphi=BA}
     Soit $E$ et $F$ deux ensembles finis.
     Soit $d$ un uplet de $E\times F$.
-    Alors nous avons l'égalitée suivante :
+    Alors nous avons l'égalité suivante :
     \begin{equation*}
         BA^{d'}_{[|0,\#F-1|]}\circ\Phi = BA^d_F
     \end{equation*}
 \end{theorem}
 
 \begin{proof}
-    Soit $E$ et $F$ deux ensemle finis.
+    Soit $E$ et $F$ deux ensembles finis.
     Nous avons deux bijections :
-    We have two bijections : 
     $\varphi$ de $E$ dans $[|0,\#E-1|]$ et
     $\psi$ de $F$ dans $[|0,\#F-1|]$.
-    Avec ces deux fonctions nous allons contruire une troisième bijections 
+    Avec ces deux fonctions nous allons construire une troisième bijections 
     $\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$.
     
@@ -151,7 +138,7 @@ Et la preuve étant constructive nous indique que pour trouver cette fonction no
             \right]
     \end{equation}
 
-    De même, passons des indices aux élements sur "$d'_1(j) = i$".
+    De même, passons des indices aux éléments sur "$d'_1(j) = i$".
     Let $i\in[|0,\#F-1|]$ and $j\in[|0,o-1|]$.
     \begin{align*}
         &d'_1(j) = i\\
@@ -159,7 +146,7 @@ Et la preuve étant constructive nous indique que pour trouver cette fonction no
         \Leftrightarrow & d_1(j) = \psi^{-1}(i)
     \end{align*}
 
-    Ansin avec les equations \ref{eq:BAdp} et \ref{eq:d1j} nous obtenons
+    Ainsi avec les équations \ref{eq:BAdp} et \ref{eq:d1j} nous obtenons
     \begin{align}
         &\left(BA^{d'}_{[|0,\#F-1|]}\circ\Phi\right)(f) =  
         \frac{1}{\#F}
@@ -179,10 +166,10 @@ Et la preuve étant constructive nous indique que pour trouver cette fonction no
         \label{eq:fini-egaba}
     \end{align}
 
-    D'après la définition~\ref{def:BA} l'experession~\ref{eq:fini-egaba} est égale à $BA_F^d(f)$
+    D'après la définition~\ref{def:BA} l'expression~\ref{eq:fini-egaba} est égale à $BA_F^d(f)$
 \end{proof}
 
-En utilisant le théorème~\ref{th:BAphi=BA} nous déduisons le corollère suivant qui jouera un rôle clé dans le recherche de la solution à $\text{argmax}\left(BA_F^d\right)$.
+En utilisant le théorème~\ref{th:BAphi=BA} nous déduisons le corollaire suivant qui jouera un rôle clé dans le recherche de la solution à $\text{argmax}\left(BA_F^d\right)$.
 
 \begin{corollary}
     \label{co:argmax}
@@ -199,28 +186,28 @@ En utilisant le théorème~\ref{th:BAphi=BA} nous déduisons le corollère suiva
     BA_{[|0,\#F-1|]}^{d'}(f') = BA_F^d(\Phi^{-1}(f'))$
 \end{proof}
 
-Grâce au corollère~\ref{co:argmax} nous avons que, pour résoudres le problème de classification sur n'importe quel ensemble, il est suffisant de le résoudre sur l'ensemble d'indices correspondant.
-L'objetif de la prochaine section est donc la recherche d'un algortihme de résolution d'un tel problème.
+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.
+L'objectif de la prochaine section est donc la recherche d'un algorithme de résolution d'un tel problème.
 
-\subsection{Contruiction d'un algorithme de classification sur $B_{m\rightarrow n}$}
+\subsection{Maximisation l'exactitude équilibré 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|]$.
-Come nous savons que nous allons travailler sur les indices, nous ne nous préocupons pas d'ensembles quelconqus $E$ et $F$ comme à la section précedente.
+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\}$.
 
-L'aproche la plus directe pour maximiser $BA_{[|0,n-1|]}^d$ serait l'algorithme qui consiste à essayer de calculer la \textit{balanced accuracy} pour toutes les fonctions de $B_{m\rightarrow n}$.
-Cette methode est viable pour des petites valeures de $m$ et $n$ mais devient rapidement impossible à calculer pour des grandes valeures.
-En effet, par denombrement nous savons que $B_{m\rightarrow n}$ contiens $n^m$ éléments.
-L'algorithme directe à donc une complexite de $\mathcal{O}(on^m)$ operations. 
-Nous allons construire à la place un algoritheme que garantie de maximiser la \textit{balanced accuracy} en $\mathcal{O}(onm)$ operations.
+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}$.
+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.
 
-Pour le constuire nous allons, d'une certaine manière, distribuer l'opératuer argmax, simplifiant ainsi l'expression de la \textit{balanced accuracy} optimale.
-Pour cela, dans le lemme qui suit nous allons reformuler la \textit{balanced accuracy}.
+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é.
 
 \begin{lemma}
     \label{lem:sumei}
-    Pour tout $i$ dans $[|0,m-1|]$, nous definissons le $n$-uplet suivant.
+    Pour tout $i$ dans $[|0,m-1|]$, nous définissons le $n$-uplet suivant.
     \begin{equation*}
         e_i:\left\{
             \begin{matrix}
@@ -235,12 +222,12 @@ Pour cela, dans le lemme qui suit nous allons reformuler la \textit{balanced acc
             \right.
     \end{equation*}
 
-    Nous pouvons alors écrir la \textit{balanced accuracy} de la manière suivant :
+    Nous pouvons alors écrire l'exactitude équilibré 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))
     \end{equation*}
-    Where $h\in B_{m\rightarrow n}$.
+    Où $h\in B_{m\rightarrow n}$.
 \end{lemma}
 \begin{proof}
     Soit $l\in[|0,n-1|]$ et $h$, une fonction dans $B_{m\rightarrow n}$.
@@ -276,11 +263,11 @@ Pour cela, dans le lemme qui suit nous allons reformuler la \textit{balanced acc
         }
     \end{align}
 
-    Dans l'expression précédente, $l$ est un élément de l'ensemble des indeices $F$.
+    Dans l'expression précédente, $l$ est un élément de l'ensemble des indices $F$.
     Pour montrer le résultat, on remplace $h(d_0(j))$~\ref{eq:sansi} par une expression qui contient $i$ : un élément de $E$.
-    Le but de faire aparaitre la quantité qui nous intersse : $e_{i,j}$.
+    Le but de faire apparaître la quantité qui nous intéresse : $e_{i,j}$.
 
-    Nous commencons par remarquer que pour tout $j$ dans $[|0,o-1|]$
+    Nous commençons par remarquer que pour tout $j$ dans $[|0,o-1|]$
     \begin{equation*}
         h(d_0(j))=l
         \Leftrightarrow d_0(j)\in h^{-1}(\{l\})
@@ -301,7 +288,7 @@ Pour cela, dans le lemme qui suit nous allons reformuler la \textit{balanced acc
         \right\}
     \end{align*}
 
-    Aninsi, par substitution de $\{j\in[|0,o-1|]\quad| h(d_0(j)) = l\}$ dans l'équation \ref{eq:sansi}, nous obtenons
+    Ainsi, par substitution de $\{j\in[|0,o-1|]\quad| h(d_0(j)) = l\}$ dans l'équation \ref{eq:sansi}, nous obtenons
     \begin{align*}
         &\frac{
             \#\left(
@@ -372,7 +359,7 @@ Pour cela, dans le lemme qui suit nous allons reformuler la \textit{balanced acc
 \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 calcule la \textit{balanced accuracy} de toutes le fonctions de  $B_{m\rightarrow n}$.
+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$.
 Nous formalisons cette idée dans le théorème suivant :
 
@@ -406,7 +393,7 @@ Nous formalisons cette idée dans le théorème suivant :
 \begin{proof}
     Soit $g\in B_{m\rightarrow n}$. 
     Nous allons montrer que $BA_{[|0,n-1|]}^d(g)\leq BA_{[|0,n-1|]}^d(f)$.
-    Nous commencons par dire que 
+    Nous commençons par dire que 
     pour tout $i\in[|0,n-1|]$, $0\leq e_i(g(i))\leq e_i(f(i))$.
     Ce qui donne que
     \begin{equation*}
@@ -417,10 +404,10 @@ Nous formalisons cette idée dans le théorème suivant :
         \frac{1}{n}\sum_{i=0}^{m-1}e_i(g(i)) \leq \frac{1}{n}\sum_{i=0}^{m-1}e_i(f(i))
     \end{equation*}
 
-    Enfin, en appliquant le lemme~\ref{lem:sumei} nous avons le résultat attedu.
+    Enfin, en appliquant le lemme~\ref{lem:sumei} nous avons le résultat attendu.
 \end{proof}
 
-En utiliant ce résulat, nous pouvons maintenant écrir l'algorithm suivant en $\mathcal{O}(onm)$ pour résoudre notre problème d'optimisation.
+En utilisant ce résultat, nous pouvons maintenant écrire l'algorithme suivant en $\mathcal{O}(onm)$ pour résoudre notre problème d'optimisation.
 
 \begin{algorithm}
     \caption{Optimisation: recherche de l'$\text{argmax}\left(BA^d_{[|0,n-1|]}\right)$}
@@ -450,7 +437,6 @@ En utiliant ce résulat, nous pouvons maintenant écrir l'algorithm suivant en $
 \end{algorithm}
 
 \FloatBarrier
-\subsection{Extention to unseen data}
 %Alogrithm \ref{algo:argmax} is an efficient algorithm to find a classifier the maximizes balanced accuracy on the set of indices. 
 %From the result $f$ of this alogrithm we find a classifier that solves the problem of maximizing the balanced accuracy on element by applying the inversse of $\Phi$.
 %Hence $\Phi^{-1}(f)$ is solution.