summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJan Aalmoes <jan.aalmoes@inria.fr>2024-09-25 15:24:16 +0200
committerJan Aalmoes <jan.aalmoes@inria.fr>2024-09-25 15:24:16 +0200
commitbd05e44ceb91c23e896677d49627a03aef56176f (patch)
treea039d1b4109e9b9c1d470f7907102e29fba150a3
parent5362d389988afb2750d27e7e6c5d401571dfba6e (diff)
Relecture Jan
-rw-r--r--background/alg.tex14
-rw-r--r--background/conf.tex75
-rw-r--r--background/dif.tex30
-rw-r--r--background/eq.tex128
-rw-r--r--background/main.tex14
-rw-r--r--background/ml.tex264
-rw-r--r--background/opti.tex52
-rw-r--r--background/proba.tex45
-rw-r--r--background/set.tex189
9 files changed, 420 insertions, 391 deletions
diff --git a/background/alg.tex b/background/alg.tex
index b2f6418..2c8a091 100644
--- a/background/alg.tex
+++ b/background/alg.tex
@@ -1,4 +1,4 @@
-\subsubsection{Espace vecotriel}
+\subsubsection{Espace vectoriel}
Les espaces vectoriels sont des structure fondamentales qui vont nous servir à comprendre comment fonctionne l'entraînement des réseaux de neurones.
\begin{definition}{Groupe}
Soit $E$ un ensemble et $+$ une opération sur $E$.
@@ -16,7 +16,7 @@ Les espaces vectoriels sont des structure fondamentales qui vont nous servir à
\begin{definition}{Espace vectoriel}
Soit $E$ un ensemble munit d'une loi interne $+$ et d'une loi externe $\cdot:\mathbb{R}\times E\rightarrow E$.
- Sout les conditions suivantes, nous dirons que $(E,+,\cdot)$ est un espace vectoriel.
+ Sous les conditions suivantes, nous dirons que $(E,+,\cdot)$ est un espace vectoriel.
\begin{enumerate}
\item $(E,+)$ est un groupe abélien.
\item $\forall (r,e,f)\in\mathbb{R}\times E\times E~r(e+f)=re+rf$
@@ -69,14 +69,16 @@ Où
\\
\end{matrix}
\end{equation*}
-On appelera par la suite $(e_0,\cdots,e_{m-1})$ \emph{base canonique} de $\mathbb{R}^m$.
-On note $f(e_j)_i = M_f(i,j)$, c'est l'entré de $M_f$ se situant à la ligne $i$ et colone $j$.
+On appellera par la suite $(e_0,\cdots,e_{m-1})$ \emph{base canonique} de $\mathbb{R}^m$.
+On note $f(e_j)_i = M_f(i,j)$, c'est l'entrée de $M_f$ se situant à la ligne $i$ et colonne $j$.
\begin{propriete}
La fonction $M_\square$ est une bijection.
\end{propriete}
-Nous définisson la mutliplication matricielle de la manière suiavante :
+Nous appelons $\mathbb{R}_{n,m}$ l'ensemble des matrices à $n$ lignes et $m$ colonnes.
+
+Nous définissons la multiplication matricielle de la manière suivante :
Soient $f\in\mathcal{L}(\mathbb{R}^m,\mathbb{R}^n)$ et $g\in\mathcal{L}(\mathbb{R}^n,\mathbb{R}^o)$.
Alors
\begin{equation*}
@@ -91,7 +93,7 @@ Alors
\begin{definition}
\label{def:background-alg-tr}
Soit $M$ une matrice à $n$ lignes et colonnes.
- Alors nous définisson la trace de $M$ de la manière suivante.
+ Alors nous définissons la trace de $M$ de la manière suivante.
\begin{equation*}
\text{Tr}(M)=\sum_{i=0}^{n-1}M(i,i)
\end{equation*}
diff --git a/background/conf.tex b/background/conf.tex
index 52ae9b9..a3f7e83 100644
--- a/background/conf.tex
+++ b/background/conf.tex
@@ -1,22 +1,22 @@
%Attacks which violate privacy and confidentiality in ML infer potentially sensitive unobservable information from observable information (e.g., model predictions).
\label{sec:bck_aia}
-Dans ce manuscrit nous considrons deux types de risques pour la confidentialité.
-Le premier concernce les données qui on servi à l'entraînement du modèle, le second concerne les donnée sui son utilisé lors de l'évaluation.
-Dans le cadre d'attaques nous parlerons de \emph{modèle cible} opour désigner le modèle utilisé par un adversaire pour apprendre des information confidentielles.
+Dans ce manuscrit nous considérons deux types de risques pour la confidentialité.
+Le premier concerne les données qui on servi à l'entraînement du modèle, le second concerne les donnée qui son utilisé lors de l'évaluation.
+Dans le cadre d'attaques nous parlerons de \emph{modèle cible} pour désigner le modèle utilisé par un adversaire pour apprendre des informations confidentielles.
\FloatBarrier
-\subsubsection{Risque sur les données d'entraîenemnt}
-L'attaque d'inférence d'apartenance (MIA) consiste à inférer si une donnée a servi à l'entraîenemnt du modèle cible.
-Cette attaque utilise le fait que le modèles d'apprentissage automatique ont en générale une moins bonne performance sur les donnée qui n'ont pas été utilisé à l'entraînement, c'est le sur-ajustement\footnote{\textit{Overfitting}}~\cite{hawkins2004problem,ying2019overview}.
+\subsubsection{Risque sur les données d'entraînement}
+L'attaque d'inférence d'appartenance (MIA) consiste à inférer si une donnée a servi à l'entraînement du modèle cible.
+Cette attaque utilise le fait que les modèles d'apprentissage automatique ont en générale une moins bonne performance sur les donnée qui n'ont pas été utilisés à l'entraînement, c'est le sur-ajustement\footnote{\textit{Overfitting}}~\cite{hawkins2004problem,ying2019overview}.
Ce problème peut survenir principalement quand le modèle cible est trop complexe par rapport à la tâche qui lui est demandé.
-Pour reprendre les mots de Hawkisn et al. : \textquote{Le sur-ajustement est l'utilisation de modèles ou de procédure qui vont à l'encontre de la parsimonie, c'est-à-dire qui utilisent plus de termes ou qui utilise des approches plus complexes que ce qui est necessaitre}
+Pour reprendre les mots de Hawkisn et al. : \textquote{Le sur-ajustement est l'utilisation de modèles ou de procédures qui vont à l'encontre de la parcimonie, c'est-à-dire qui utilisent plus de termes ou qui utilisent des approches plus complexe que ce qui est nécessaire}
\footnote{\textit{Overfitting is the use of models or procedures that violate
-parsimonysthat is, that include more terms than are neces-
+parsimony, that is, that include more terms than are neces-
sary or use more complicated approaches than are necessary.}}
-Nous voyons sur la Figure~\ref{fig:background-conf-mia} l'écart entre la valeur de fonction de cout évalué sur les données d'entraînement et d'évaluation.
-Le lien est assez claire, un écart significatif indique qu'un classifieur va être capable d'apprandre quel donnée à été utilisé pour l'entraînement.
-Pour vérifer cela, la Sous-figure~\ref{sfig:background-conf-mia-ba} montre comment une forêt aléatoire à put apprendre cette distinction.
+Nous voyons sur la Figure~\ref{fig:background-conf-mia} l'écart entre la valeur de la fonction de coût évalué sur les données d'entraînement et d'évaluation.
+Le lien est assez claire, un écart significatif indique qu'un classifieur va être capable d'apprendre quelles données ont été utilisées pour l'entraînement.
+Pour vérifier cela, la Sous-figure~\ref{sfig:background-conf-mia-ba} montre comment une forêt aléatoire a put apprendre cette distinction.
On observe une exactitude équilibrée autour de 0,625 indiquant une fuite du confidentialité.
\begin{figure}
@@ -24,31 +24,32 @@ On observe une exactitude équilibrée autour de 0,625 indiquant une fuite du co
\begin{subfigure}{0.3\linewidth}
\centering
\includegraphics[width=\linewidth]{background/figure/conf/mia_ba.pdf}
- \caption{Résulat de l'attaque MIA.}
+ \caption{Résultat de l'attaque MIA.}
\label{sfig:background-conf-mia-ba}
\end{subfigure}
\begin{subfigure}{0.65\linewidth}
\centering
\includegraphics[width=\linewidth]{background/figure/conf/mia.pdf}
- \caption{Ecart entre le coût calculer sur les données d'entraînemnt et sur les données d'évaluation.}
+ \caption{Écart entre le coût calculé sur les données d'entraînements et sur les données d'évaluation.}
\end{subfigure}
- \caption{Lien entre sur-ajustement et succès de l'attque MIA.}
+ \caption{Lien entre sur-ajustement et succès de l'attaque MIA.}
\label{fig:background-conf-mia}
\end{figure}
-L'étude de la fonction de cout est une possible quand l'adversaire possède des donnée pour lequelles il sait qu'elle ont apartenu à l'entraîenement.
-Grace à cela il peut construir un classifieur un utilisant cette conaissance comme étiquette.
-Si ce n'est pas le cas, l'adversaire utilise des modèles mirroires\footnote{\textit{Shadow models}} qui simulent le modèle cible est permettent d'apprendre à différencier le cout d'une donéne ayant servit à l'entraîenment d'une donnée jamais observé~\cite{shokri2017membership}.
-Un modèle d'attaque de MIA peut ensuite être utilser comme base pour d'autre type d'attaque comme par exemple reconstruir un attribut sensible de données ayanat servit à l'entraînement~\cite{yeom}.
+L'étude de la fonction de coût est possible quand l'adversaire possède des donnée pour lesquelles il sait qu'elles ont appartenues à l'entraînement.
+Grâce à cela il peut construire un classifieur en utilisant cette connaissance comme étiquette.
+Si ce n'est pas le cas, l'adversaire utilise des modèles miroirs\footnote{\textit{Shadow models}} qui simulent le modèle cible est permettent d'apprendre à différencier le coût d'une donnée ayant servit à l'entraînement d'une donnée jamais observé~\cite{shokri2017membership}.
-La confidentialité diférentielle\footnote{\textit{Differential privacy}} permet d'empêcher les attaque MIA~\cite{}.
-\begin{definition}{Confidentiatlié diferetielle}
+Un modèle d'attaque de MIA peut ensuite être utilisé comme base pour d'autre type d'attaque comme par exemple reconstruire un attribut sensible de données ayant servit à l'entraînement~\cite{yeom}.
+
+La confidentialité différentielle\footnote{\textit{Differential privacy}} permet d'empêcher les attaques MIA~\cite{chen2020differential,rahman2018membership}.
+\begin{definition}{Confidentialité différentielle}
Soit $(\Omega,\mathcal{T},P)$ un espace probabilisé.
- Soit $(S,\mathcal{S})$ un espace mesurable et $\mathcal{V}$ l'ensemble des fonctions de mesurables de $\Omega$ dans $S$.
+ Soit $(S,\mathcal{S})$ un espace mesurable et $\mathcal{V}$ l'ensemble des fonctions mesurables de $\Omega$ dans $S$.
Soient $E$ un ensemble et $M$ une fonction de $E$ dans $\mathcal{V}$.
Soit $R\subset E^2$.
Soient $(\varepsilon,\delta)\in {\mathbb{R}^+}^2$
- Alors $M$ satisfait la $(\varepsilon,\delta)$ confidentialité diférentielle si et seulemnt si
+ Alors $M$ satisfait la $(\varepsilon,\delta)$ confidentialité différentielle si et seulement si
\begin{equation*}
\forall (e_1,e_2,s)\in E\times E\times \mathcal{S}\quad
(e_1,e_2)\in R\implies
@@ -59,32 +60,32 @@ En pratique $E$ représente l'ensemble de toutes les bases de données possibles
$R$ est une relation telle que $(e_1,e_2)\in R$ si et seulement si $e_1$ et $e_2$ différent d'une donnée.
$S$ est l'ensemble des modèles possibles.
$M$ est l'algorithme d'apprentissage qui prend en entrée une basse de donnée et renvoie une variable aléatoire à valeur dans l'espace des modèles $S$.
-Cette définition signifie donc que pour des bases de données de données diférentes d'une ligne, l'algorithme d'apprentissage aura des sorties presques indistinguables l'une de l'autres.
+Cette définition signifie donc que pour des bases de données de données différentes d'une ligne, l'algorithme d'apprentissage aura des sorties presque indistinguables l'une de l'autre.
Le presque étant paramétré par $\varepsilon$ et $\delta$.
\FloatBarrier
\subsubsection{Risque sur les données d'évaluation}
-Le second risque pour la confidentialité que nous allons évoquer concerne les donnée des utilisateur de modèle d'apprentissage et non plus les données d'entraînement.
-Dans ce cas un utilisateur souhaite évalue une donnée sur le modèle cibel et la question que l'on se pose est :
-Que ce passe t'il si la prédiction fuite à un adversaire ?
+Le second risque pour la confidentialité que nous allons évoquer concerne les données des utilisateurs de modèles d'apprentissage et non plus les données d'entraînement.
+Dans ce cas un utilisateur souhaite évaluer une donnée sur le modèle cible et la question que l'on se pose est :
+Que se passe t'il si la prédiction fuite à un adversaire ?
Song et al.~\cite{Song2020Overlearning} introduisent le concept de \emph{sur-apprentissage}\footnote{\textit{Overlearning}}.
Ce terme désigne un modèle cible qui apprend plus que sa tâche principale.
Par exemple un modèle servant à inférer si une personne souris dans une image vas aussi apprendre la couleur de peau~\cite{malekzadeh2021honestbutcurious}.
-Ou encore, utiliser un modèle qui prédise l'admission dans un école ou l'obtention d'un pret pour inférer le genre.
+Ou encore, utiliser un modèle qui prédise l'admission dans une école ou l'obtention d'un prêt pour inférer le genre~\cite{Song2020Overlearning}.
Il s'agit donc d'inférer un attribut sensible en utilisant la prédiction d'un modèle cible qui n'a pas été entraîné pour inférer cet attribut sensible.
-Nous appelerons ce type d'attaque : inférence d'attribut sensible (AIA).
+Nous appellerons ce type d'attaque : inférence d'attribut sensible (AIA).
-Nous considérerons pour la suite que l'adversaire à uniquement accès à la prédiction du modèle cible et non pas à la donnée d'entrée.
-En effet le modèle cible n'ajoute pas plus d'information concernant l'attribut sensible que n'est contenus dans la donnée d'entrée~\cite{jayaraman2022attribute}.
+Nous considérerons pour la suite que l'adversaire a uniquement accès à la prédiction du modèle cible et non pas à la donnée d'entrée.
+En effet le modèle cible n'ajoute pas plus d'information concernant l'attribut sensible que n'en n'est contenus dans la donnée d'entrée~\cite{jayaraman2022attribute}.
-Une AIA qui cherche à inférer un attribut sensible présente dans le données d'entrée est appelé \emph{inversion de modèle}\footnote{\textit{modèle inversion}}.
-En effet comme l'adversaire cherche a inferer une entrée d'un modèle cible à partir de sa sortie, cette attaque est similaire à l'inversion d'un fonction.
-Fredrikson et al.~\cite{fredrikson2} donnent un exemple marquant en pharmacogenetics :
-La molecule Warfarin entre dans le traitement préventif des crises cardiaques cependant son dosage est complexe car il dépend de chaque patient.
-Ainsi des modèles ont été créés pour prédire le dosage à partire des donnée médicales du patient comme son génotype.
-Fredrikson et al. ont réussi à utiliser la prédiction de ces modèles pour retrouver les donnés médicales démontrant ainsi le risque de privacy inhérant aux sortie de modèles.
+Une AIA qui cherche à inférer un attribut sensible présent dans le données d'entrée est appelé \emph{inversion de modèle}\footnote{\textit{modèle inversion}}.
+En effet comme l'adversaire cherche à inférer une entrée d'un modèle cible à partir de sa sortie, cette attaque est similaire à l'inversion d'une fonction.
+Fredrikson et al.~\cite{fredrikson2} donnent un exemple marquant en pharmacogénétique :
+La molécule Warfarin entre dans le traitement préventif des crises cardiaques, cependant son dosage est complexe car il dépend de chaque patient.
+Ainsi des modèles ont été créés pour prédire le dosage à partir des données médicales du patient comme son génotype.
+Fredrikson et al. ont réussi à utiliser la prédiction de ces modèles pour retrouver les donnés médicales démontrant ainsi le risque de perte de confidentialité inhérent aux sorties des modèles.
-Les dévlopements nouveaux que proposent ce manuscrit se concentrerons sur les risque d'inférence liés à des attribut sensibles qui ne sont pas utilisé lors de l'entraînement.
+Les développements nouveaux que proposent ce manuscrit se concentrerons sur les risques d'inférences liés à des attributs sensibles qui ne sont pas utilisés lors de l'entraînement.
diff --git a/background/dif.tex b/background/dif.tex
index 2ba01f1..9435c24 100644
--- a/background/dif.tex
+++ b/background/dif.tex
@@ -1,5 +1,5 @@
-Le but du calcul diférentiel est l'étude des variation infinitésimale des fonctions.
-Nous allons nous contenter ici d'étudier les fonctionelles, c'est à dire des fonction de $\mathbb{R}^n$ dans $\mathbb{R}$ car c'est ce dont nous allons avoir besoin en aprentissage automatique.
+Le but du calcul différentiel est l'étude des variations infinitésimales des fonctions.
+Nous allons nous contenter ici d'étudier les fonctionnelles, c'est-à-dire des fonction de $\mathbb{R}^n$ dans $\mathbb{R}$ car c'est ce dont nous allons avoir besoin en apprentissage automatique.
\begin{definition}{Produit scalaire euclidien}
\label{def:background-dif-scal}
Soit $(x,y){\in\mathbb{R}^n}^2$ alors le produit scalaire euclidien est
@@ -9,7 +9,7 @@ Nous allons nous contenter ici d'étudier les fonctionelles, c'est à dire des f
\end{definition}
\begin{definition}{Norme euclidienne}
\label{def:background-dif-eucl}
- Soit $x\in\mathbb{R}^n$, nous definisson le norme euclidienne de $x$ par l'expression suivante
+ Soit $x\in\mathbb{R}^n$, nous définissons le norme euclidienne de $x$ par l'expression suivante
\begin{equation*}
||x||={\langle x,x\rangle}^{\frac{1}{2}}
\end{equation*}
@@ -23,37 +23,25 @@ Nous allons nous contenter ici d'étudier les fonctionelles, c'est à dire des f
\begin{equation*}
\forall\varepsilon>0\exists\delta>0\forall a\in\mathbb{R}^m~||a-x||<\delta\implies||f(a)-y||<\varepsilon
\end{equation*}
- Nouse ecrivons alors $lim_{a\rightarrow x}f(a)=y$ car $y$ est alors unique~\cite{Bourrigan2021-dd}.
+ Nous écrivons alors $lim_{a\rightarrow x}f(a)=y$ car $y$ est alors unique~\cite{Bourrigan2021-dd}.
\end{definition}
-\begin{definition}{Differentielle}
+\begin{definition}{Différentielle}
\label{def:background-dif-dif}
Soit $f$ une fonction de $\mathbb{R}^n$ dans $\mathbb{R}$.
Nous dirons que $f$ est différentiable en $a\in\mathbb{R}^n$ si et seulement si il existe
$df(a)\in\mathbb{L}(\mathbb{R}^n,\mathbb{R})$
- telle que il existe $\varepsilon:\mathbb{R}\rightarrow \mathbb{R}$ telle que pour tout $h\in\mathbb{R}^n$
+ telle que il existe $\varepsilon:\mathbb{R}^n\rightarrow \mathbb{R}$ telle que pour tout $h\in\mathbb{R}^n$
\begin{equation*}
f(a+h) = f(a)+df(a)h+||h||\varepsilon(h)
\end{equation*}
avec
$lim_{h\rightarrow 0}\varepsilon(h)=0$.
- $df(a)$ s'apelle la \emph{diférentielle} de $f$ en $a$.
+ $df(a)$ s'appelle la \emph{différentielle} de $f$ en $a$.
\end{definition}
-Dans le cas où $f$ est différentiable en tout point de $\mathbb{R}^n$ alors
-la fonction $f$ peut être vu comme $n$ fonction $f_0\cdots f_{n-1}$ de $\mathbb{R}$ dans $\mathbb{R}$ avec
-\begin{equation*}
- f(x)=\left(
- \begin{matrix}
- f_0(x_0)
- \cdots
- f_{n-1}(x_{n-1})
- \end{matrix}
- \right)
-\end{equation*}
-Toutes les fonctions de $f_i$ sont différentiables.
\begin{definition}
\label{def:background-math-grad}
- Pour tout $x\in\mathbb{R}$ nous définison la $i$ème dérivée partielle de $f$ par
+ Pour tout $x\in\mathbb{R}$ nous définissons la $i$ème dérivée partielle de $f$ par
\begin{equation*}
\partial_i f :\left\{
\begin{matrix}
@@ -79,7 +67,7 @@ Toutes les fonctions de $f_i$ sont différentiables.
\right.
\end{equation*}
\end{definition}
-Pour le.a lecteur.ice familier avec la dériviabilité notons que
+Pour le.a lecteur.ice familier avec la dérivabilité notons que
\begin{equation*}
lim_{h\rightarrow 0}\frac{f(x+he_i)-f(x)}{h} = \partial_i f(x)
\end{equation*}
diff --git a/background/eq.tex b/background/eq.tex
index a53f479..1bf9b19 100644
--- a/background/eq.tex
+++ b/background/eq.tex
@@ -1,18 +1,18 @@
\label{sec:bck_fair}
-L'équitée algorithmique à pour but de réduire les bias dans le modèle prédictif.
-C'est-à dire, comment peut on faire en sorte que le modèle ne désavantage pas ou n'avantge pas certain sous-groupes ?
-En effet, le fait qu'une donnée appratienne à certainne minorité peut avoir un impacte sur la qualitée de la prédiction.
-Par exemple en justice prédictie, la couleur de peau d'un peau d'un coupable jou un rôle qui n'est pas négligable dans la prédiction du récidivisme au Etats Unis~\cite{fairjustice}.
-Pour savoir si un attribut est sensible ou non, non pouvon non referer à la liste des vignt-cinq critère de disrimination présenté à la Section~\ref{sec:contexte-legal-discrimination}.
-Ces bias sont appris par le modèle car ils sont présent dans les donnés d'entraînement qui reflète la population dans laquelle ces donnée ont été prélevés.
-Nous représentons sur la Figure~\ref{fig:background-eq-logi} comment une regression logistique peut présenter une différence de traitement entre deux sous groupe de la population.
+L'équité algorithmique a pour but de réduire les biais dans les modèles prédictifs.
+C'est-à-dire, comment peut on faire en sorte que le modèle ne désavantage pas ou n'avantage pas certain sous-groupes ?
+En effet, qu'une donnée appartienne à certaine minorité peut avoir un impacte sur la qualité de la prédiction.
+Par exemple en justice prédictive, la couleur de peau d'un coupable joue un rôle qui n'est pas négligeable dans la prédiction du récidivisme au États Unis~\cite{fairjustice}.
+Pour savoir si un attribut est sensible ou non, nous pouvons nous référer à la liste des vingt-cinq critères de discrimination présenté à la Section~\ref{sec:contexte-legal-discrimination}.
+Ces biais sont appris par le modèle car ils sont présent dans les donnés d'entraînement qui reflètent la population dans laquelle ces donnée ont été prélevés.
+Nous représentons sur la Figure~\ref{fig:background-eq-logi} comment une régression logistique peut présenter une différence de traitement entre deux sous groupe de la population.
Nous observons que comme il y a moins de donnée de femmes, le modèle à appris une courbe qui se rapproche plus des données hommes.
-Comme le seuil de ce modèle est situé à $0,5$, nous voyons que tous le points rouges qui correspondent au femmes passent au dessus du seuil représenté par la ligne horizontale grise.
-Ainsi, bien que les étiquettes soient répartis équitablement chez les hommes et ches les femmes, le modèle classife toutes les femme dans la classe 1.
-Il sagit ici d'un cas scolaire sur des données générés mais supposons que la classe 1 soit désavantageuse.
-Par exemple, imaginons que ce modèle soit utilisé dans un programme de rectruement automatique.
-La classe 0 implique que le candidat est séléctioné, classe 1 implique que le candidat est réjété.
-Alors ce programme serait discriminatoire car bien que 50\% des femme et 50\% des homme ont une étiquette qui les rendent adminssibles, le programme ne sélectione que des candidats hommes.
+Comme le seuil de ce modèle est situé à $0,5$, nous voyons que tous le points rouges qui correspondent aux femmes passent au dessus du seuil représenté par la ligne horizontale grise.
+Ainsi, bien que les étiquettes soient répartis équitablement chez les hommes et chez les femmes, le modèle classifie toutes les femme dans la classe 1.
+Il s'agit ici d'un cas scolaire sur des données générés mais supposons que la classe 1 soit désavantageuse.
+Par exemple, imaginons que ce modèle soit utilisé dans un programme de recrutement automatique.
+La classe 0 implique que le candidat est sélectionné, la classe 1 implique que le candidat est rejeté.
+Alors ce programme serait discriminatoire car bien que 50\% des femme et 50\% des homme ont une étiquette qui les rendent admissibles, le programme ne sélectionne que des candidats hommes.
\begin{figure}
\centering
@@ -31,22 +31,22 @@ Alors ce programme serait discriminatoire car bien que 50\% des femme et 50\% de
\textbf{Exactitude}&1&0,5&0,92\\
\hline
\end{tabular}
- \caption{Exemple d'un regression logistique qui a une meilleur performance pour le homme que pour les femmes.
- Les donnée provienne d'une génération et servent uniquement à titre d'illustration.
- La regression logisitque à bien été optimisé sur les donnée générés en utilise l'algorithme de scikit learn~\cite{scikit-learn}}
+ \caption{Exemple d'une régression logistique qui a une meilleur performance pour les hommes que pour les femmes.
+ Les données proviennent d'une génération et servent uniquement à titre d'illustration.
+ La régression logistique à bien été optimisé sur les données générés en utilise l'algorithme de scikit learn~\cite{scikit-learn}}
\label{fig:background-eq-logi}
\end{figure}
-\subsubsection{Définitions de l'équitée}
-L'équitée en apprantissag automatique se présente sous deux aspect qui mettent lumière deux visions différentes :
+\subsubsection{Définitions de l'équité}
+L'équité en apprentissage automatique se présente sous deux aspects qui mettent lumière deux visions différentes :
-\textbf{L'équitée individuelle}\footnote{Individual fairness}
-cherche à faire en sorte que deux donnée, à toutes choses égale exepté l'attribut sensible, produisent la même prédiction.
+\textbf{L'équité individuelle}\footnote{Individual fairness}
+cherche à faire en sorte que deux données, à toutes choses égale excepté l'attribut sensible, produisent la même prédiction.
-\textbf{L'équitée de groupe}\footnote{Group fairness}
-Vient de l'idée que different sous groupes défini par un critère de discrimination devrait être traite de manière similaire.
-Il y a différentes définitions mathématiques de l'équite de groupe.
-Nous allons en regarder trois qui sont bien établis dans la litérature et souvant utilisé : l'effet différencié\footnote{disparate impact} la paritée demographique\footnote{Demographic parity} et l'équitée de chances\footnote{Equality of odds}.
+\textbf{L'équité de groupe}\footnote{Group fairness}
+vient de l'idée que différents sous groupes définis par un critère de discrimination devrait être traite de manière similaire.
+Il y a différentes définitions mathématiques de l'équité de groupe.
+Nous allons en regarder trois qui sont bien établis dans la littérature et souvent utilisé : l'effet différencié\footnote{disparate impact} la parité démographique\footnote{Demographic parity} et l'équité des chances\footnote{Equality of odds}.
Pour cela nous allons considérer le cadre suivant :
Nous avons un classifieur modélisé par une variable aléatoire $\hat{Y}$ qui essai d'inférer l'étiquette $Y$.
@@ -62,46 +62,45 @@ De plus, nous avons l'attribut sensible modélisé par $S$ qui prend ses valeurs
Cette notion ne fonctionne que pour $F=G=\{0,1\}$.
\end{definition}
-Cette définition est utilisé au Etats Unis pour montrer qu'une structure a une politique de discrimination à l'encontre d'une minorité comme nous l'avons vus à la Section~\ref{sec:contexte-legal}.
-
+Cette définition est utilisé au États Unis pour montrer qu'une structure a une politique discriminatoire à l'encontre d'une minorité comme nous l'avons vus à la Section~\ref{sec:contexte-legal}.
\begin{definition}
\label{def:background-eq-dp}
$\hat{Y}$ satisfait la \emph{parité démographique} pour $S$ si et seulement si : $\forall (y,s_1,s_2)\in F\times G\times G~P(\hat{Y}=y | S=s_1) = P(\hat{Y}=y | S=s_2)$.
\end{definition}
-La parité démographique ne prend pas en compte l'étiquette, cette définition est equivalante à dire que l'attribut sensbile est indépendante de la prédiction (même si l'étiquette ne l'est pas).
-Cela peut créer de cas où en cherchant à imposer cette metrique, nous obtenons des taux de vrais et de faux positif différents pour les sous groupes~\cite{dpbad}.
-Ainsi, la parité demographique peut être repsécté tout en dégradant l'effet différencié.
-Il n'est pas nécéssaire que si $\hat{Y}=Y$ (le classifieur infère parfaitement l'étiquette) alors la parite démographique soit respécté.
-Chercher à imposer cette définition revient à faire de la discrimination positive.
+La parité démographique ne prend pas en compte l'étiquette, cette définition est équivalente à dire que l'attribut sensible est indépendant de la prédiction (même si l'étiquette ne l'est pas).
+Cela peut créer des cas où en cherchant à imposer cette notion, nous obtenons des taux de vrais et de faux positif différents pour les sous groupes~\cite{dpbad}.
+Ainsi, la parité démographique peut être respecté tout en dégradant l'effet différencié.
+Il n'est pas nécessaire que si $\hat{Y}=Y$ (le classifieur infère parfaitement l'étiquette) alors la parie démographique soit respecté.
+Chercher à imposer cette définition peut revenir à faire de la discrimination positive.
-Pour certaines applications cette effet n'est pas souaitable.
+Pour certaines applications cet effet n'est pas souhaitable.
Ainsi Hardt et al.~\cite{fairmetric2} propose de modifier la parité démographique pour prendre en compte l'étiquette ce qui donne la définition suivante :
\begin{definition}
\label{def:background-eq-eoo}
- $\hat{Y}$ satisfait l'équitée des chances pour $S$ si et seulement si : $\forall (\hat{y},y,s_1,s_2)\in E\times E\times G\times G \quad
+ $\hat{Y}$ satisfait l'équité des chances pour $S$ si et seulement si : $\forall (\hat{y},y,s_1,s_2)\in E\times E\times G\times G \quad
P(\hat{Y}=\hat{y} | S=s_1,Y=y) = P(\hat{Y}=\hat{y} | S=s_2,Y=y)$.
\end{definition}
-\subsubsection{Imposer l'équitée comme contrainte d'optimisation}
+\subsubsection{Imposer l'équité comme contrainte d'optimisation}
Ces définitions peuvent être imposé au modèle de trois manières:
\begin{enumerate}
- \item Prétraitement\footnote{Preprocessing} :
- Le prétraitement consiste à modifier les données avant l'entraînement pour en retirer les bias.
- Pour cela le rééquilibrage des poids\footnote{Reweighing} s'attaque au problème des biais en attribuant un poid à chaque donnée pour corrigier le déséquilibre dans un attribut sensible~\cite{preprocessing}.
- \item Entraitement\footnote{Inprocessing} :
- Ces algorithmes, comme le rééquilibrage adversariel\footnote{Adversarial debiasing}~\cite{debiase} ou la descente de gradient exponentiée\footnote{Exponentiated gradient descent}~\cite{reductions}, modifient l'algorithme d'optimisation du modèle pour impose les définitions équité sous forme d'optimisation sous contrainte.
- \item Postraitement\footnote{Postprocessing} :
- Cette methode consiste à cacher les biais dans la sortie du modèle.
+ \item Prétraitement\footnote{\textit{Preprocessing}} :
+ Le prétraitement consiste à modifier les données avant l'entraînement pour en retirer les biais.
+ Pour cela le rééquilibrage des poids\footnote{\textit{Reweighting}} attribut un poids à chaque donnée et corrige le déséquilibre en augmentant le poids des certaines données pour qu'elle soient plus pris en compte~\cite{preprocessing}.
+ \item Entraitement\footnote{\textit{Inprocessing}} :
+ Ces algorithmes, comme le rééquilibrage adverse\footnote{\textit{Adversarial debiasing}}~\cite{debiase} ou la descente de gradient exponentiée\footnote{\textit{Exponentiated gradient descent}}~\cite{reductions}, modifient l'algorithme d'optimisation du modèle pour imposer les définitions d'équité sous forme d'un problème d'optimisation sous contraintes.
+ \item Postraitement\footnote{\textit{Postprocessing}} :
+ Cette méthode consiste à cacher les biais dans la sortie du modèle.
Le modèle est biaisé mais sa sortie est filtrée.
\end{enumerate}
-Comme nous nous intéressons au interaction entre équitée et confidentialité, le Chapitre~\ref{sec:aia} s'inscrit dans la lignée de travaux précédent qui se concentrent sur les méchanismes entraitements~\cite{chang2021privacy}.
+Comme nous nous intéressons aux interactions entre équité et confidentialité, le Chapitre~\ref{sec:aia} s'inscrit dans la lignée de travaux précédents qui se concentrent sur les mécanismes entraitements~\cite{chang2021privacy}.
Nous allons en présenter deux que nous allons utiliser dans la suite du manuscrit.
-\paragraph{Déscente de gradient exponentié}
-L'aproche par réduction pour une classification équitable\footnote{\textit{Reductions approaches to fair classification}} traduit une définition d'équité en termé de contraintes d'inégalités~\cite{reductions}.
-Par exemple la partié démographique peut se reformuler de la manière suivante
+\paragraph{Descente de gradient exponentié}
+L'approche par réduction pour une classification équitable\footnote{\textit{Reductions approaches for fair classification}} traduit une définition d'équité en terme de contraintes d'inégalités~\cite{reductions}.
+Par exemple la parité démographique peut se reformuler de la manière suivante
\begin{equation*}
\left\{
\begin{matrix}
@@ -112,33 +111,36 @@ Par exemple la partié démographique peut se reformuler de la manière suivante
\right.
\end{equation*}
Où $\epsilon_0$ et $\epsilon_1$ ont été rajouté pour relaxer la contrainte permettant de contrôler le compromis entre utilité en confidentialité.
-Ensuite ces contraintes sont utilisés avec le problème de minimisation sous la forme d'une lagrangien comme nous l'avons vu à la Section~\ref{sec:background-opti-sous}.
+Ensuite ces contraintes sont utilisés avec le problème de minimisation sous la forme d'un lagrangien comme nous l'avons vu à la Section~\ref{sec:background-opti-sous}.
-Pour trouver le point selle Agarwal et al. utilisent en algorithme qui produit un classifieur stochastique\footnote{randomized classifieur}.
+Pour trouver le point selle Agarwal et al. utilisent en algorithme qui produit un classifieur stochastique\footnote{\textit{Randomized classifieur}}.
C'est un classifieur particulier qui n'est pas déterministe.
-Lors de l'apprentissage, plusieurs solutions approchant le point selle sont trouvé qui correspondent à plusieur sous-classifieurs.
-Ensuite pour chaque prédiction un choix aléatoire est réalisé pour sélectione l'un des sous-classifieur qui sera évalué sur la donnée d'entré.
+Lors de l'apprentissage, plusieurs solutions approchant le point selle sont trouvé qui correspondent à plusieurs sous-classifieurs.
+Ensuite pour chaque prédiction un choix aléatoire est réalisé pour sélectionner l'un des sous-classifieur qui sera évalué sur la donnée d'entrée.
+Il s'agit donc d'une méthode d'apprentissage ensembliste.
+
+Le nom de la méthode vient de l'utilisation de l'algorithme \textit{Exponentiated Gradient}~\cite{kivinen1997exponentiated} pour la résolution du problème dual qui accélère le convergence comparativement à l'algorithme de descente de gradient.
-\paragraph{Rééquilibrage adversariel}\footnote{\textit{Adversarial debiasing}}
+\paragraph{Rééquilibrage adverse}\footnote{\textit{Adversarial debiasing}}
Cette méthode prend le problème sous un tout autre angle~\cite{10.1145/3278721.3278779}.
-Au lieu d'integrer les contraintes d'équitée lors de l'apprantissage, elle utilise l'idée suivante :
-La partié démographique signifie que l'attribut sensible est indépendant de la sortie, donc si il est impossible pour un adversaire de prédire l'attribut sensible à partir du logit, le modèle doit satisfaire cette définition.
-Cette une remarque très juste que nous allons étudié en détail et démontrer dans les Chapitres~\ref{sec:fini} et~\ref{sec:aia}.
-
-La méthode de Zhan et al. consiste donc utiliser deux réseaux de neuronnes.
-L'un infére la tâche principle, l'autre utilise le logit du premier pour inférer l'attribut sensible nous l'appelons adversaire.
-Ces deux classifieur sont entraîné simultanément dans un contexte adversariel.
-Cela signifi que la fonction de cout est de la forme
+Au lieu d'intégrer les contraintes d'équités lors de l'apprentissage, elle utilise l'idée suivante :
+La parité démographique signifie que l'attribut sensible est indépendant de la sortie, donc si il est impossible pour un adversaire de prédire l'attribut sensible à partir du logit, le modèle doit satisfaire cette définition.
+C'est une remarque très juste que nous allons étudié en détail et démontrer dans les Chapitres~\ref{sec:fini} et~\ref{sec:aia}.
+
+La méthode de Zhan et al. consiste donc à utiliser deux réseaux de neurones.
+L'un infère la tâche principale, l'autre utilise le logit du premier pour inférer l'attribut sensible : nous l'appelons adversaire.
+Ces deux classifieurs sont entraînés simultanément dans un contexte adverse\footnote{\textit{Adversarial setup}}.
+Cela signifie que la fonction de coût est de la forme
\begin{equation}
\label{eq:background-ml-adv}
C(x) = F(x) - sA(x)
\end{equation}
Où $F$ est le coût du classifieur principale et $A$ celui de l'adversaire.
-Nous voyons que minimiser $C$ à tendence à minimiser $F$ et maximiser $A$ ce qui signifie trouver les paramètres du classifieur de la tâche principle qui vas réaliser une bonne classification tout en empêchant l'adversaire d'inférer l'attribut sensible.
+Nous voyons que minimiser $C$ à tendance à minimiser $F$ et maximiser $A$ ce qui signifie trouver les paramètres du classifieur de la tâche principale qui vas réaliser une bonne classification tout en empêchant l'adversaire d'inférer l'attribut sensible.
L'avantage de cette méthode par rapport aux multiplicateurs de Lagrange est que ici on protège directement le logit au lieu de la prédiction ce qui est plus générale.
-Cela serai impossible et génererai une quantité infinie (non-dénombrable) de contraintes si on devais les écrire sous une forme acceptable pour un lagrangien.
+Cela serai impossible et générerai une quantité infinie (non-dénombrable) de contraintes si on devais les écrire sous une forme acceptable pour créer un lagrangien.
-Le principale désantage de cette methode est dans le paramètre $s$ de l'Equation~\ref{eq:background-ml-adv}.
-Ce paramètre sert à avoir un bon équilibre entre la tâche principle et contrer l'adversaire.
-Cependant, comme Zhang et al. le précise, il est très dificile de le trouver et rentre dans la catégorire de l'optimisation des hyperparamètre des réseaux de neuronnes.
+Le principale désavantage de cette méthode est dans le paramètre $s$ de l'Equation~\ref{eq:background-ml-adv}.
+Ce paramètre sert à avoir un bon équilibre entre la tâche principale et contrer l'adversaire.
+Cependant, comme Zhang et al. le précise, il est très difficile de le trouver et rentre dans la catégorie de l'optimisation des hyperparamètres des réseaux de neurones.
diff --git a/background/main.tex b/background/main.tex
index d5a1ce0..49d9c8f 100644
--- a/background/main.tex
+++ b/background/main.tex
@@ -1,13 +1,13 @@
Nous présentons dans ce chapitre les différentes théories et concepts sur les quelles se basent nos développements.
\section{Mathématiques}
\label{sec:background-math}
-L'originie de l'IA est mathématique~\cite{dartmouth,lecun2019quand}.
-Nous utilisons dans ce manuscrit principalement deux théories : l'optimisation pour entraîner les modèles et les probabilitées pour les évaluer.
-Ainsi nous présentons dans cette section les prérequi necessaire pour comprendre les prochains dévelopements.
-Cette section ne serai être en cours exhaustif mais a pour but de mettre en place les définitions et les principaux théorèmes qui nous allons utiliser.
-Nous supposons que le lecteur est familier du clacul des prédicats.
+L'origine de l'IA est mathématique~\cite{dartmouth,lecun2019quand}.
+Nous utilisons dans ce manuscrit principalement deux théories : l'optimisation pour entraîner les modèles et les probabilités pour les évaluer.
+Ainsi nous présentons dans cette section les prérequis nécessaires pour comprendre les prochains développements.
+Cette section ne serai être un cours exhaustif mais a pour but de mettre en place les définitions et les principaux théorèmes qui nous allons utiliser.
+Nous supposons que le lecteur est familier du calcul des prédicats.
Nous utiliserons les quantificateurs $\forall$ (pour tout) et $\exists$ (il existe tel que).
-Nous utiliserons aussi les opératuer logiques suivant que nous définissons par leur tables de véritée :
+Nous utiliserons aussi les opérateurs logiques suivant que nous définissons par leurs tables de vérités :
\begin{equation}
\begin{matrix}
a & b & a\iff b & a\implies b & a\wedge b & a\vee b & \neg a\\
@@ -52,7 +52,7 @@ a & b & a\iff b & a\implies b & a\wedge b & a\vee b & \neg a\\
\input{background/ml}
\FloatBarrier
- \subsection{Equité}
+ \subsection{Équité}
\label{sec:background-eq}
\input{background/eq}
diff --git a/background/ml.tex b/background/ml.tex
index 7372508..447e9d1 100644
--- a/background/ml.tex
+++ b/background/ml.tex
@@ -1,32 +1,32 @@
-L'aprantissiage automatique\footnote{\textit{Machine learning}} est le fondement de l'IA moderne.
-Les réseaux de neuronnes profonds notament ont révolutioné ce domaines notament grâce à l'augmentation de la puissance de calcul et des cartes graphiques~\cite{lecun2019quand}.
+L'apprentissage automatique\footnote{\textit{Machine learning}} est le fondement de l'IA moderne.
+Les réseaux de neurones profonds ont révolutionné ce domaines notamment grâce à l'augmentation de la puissance de calcul des cartes graphiques~\cite{lecun2019quand}.
\subsection{Principe}
-Repprenons la définition de L'IA donnée dans le reglement UE 2024/1689 pour une harmonisation des regulations relatives a l'IA~\cite{aiact} et notamant la Figure~\ref{fig:contexte-IAUE}.
-Cette definition exprime bien le fonctionement d'un modèle d'apprantissage automatique.
-Le modèle est un fonctione qui prend en entrée une donnée d'entrée et des parametre et qui renvoi un prédiction.
-Le vie d'un modèle se passe en deux étape.
+Reprenons la définition de L'IA donnée dans le règlement UE 2024/1689 pour une harmonisation des régulations relatives a l'IA~\cite{aiact} et notamment la Figure~\ref{fig:contexte-IAUE}.
+Cette définition exprime bien le fonctionnement d'un modèle d'apprentissage automatique.
+Le modèle est une fonction qui prend en entrée une donnée d'entrée et des paramètres et qui renvoi une prédiction.
+Le vie d'un modèle se passe en deux étapes.
Premièrement il faut trouver des paramètres qui assurent un bon fonctionnement du modèle.
-En générale le bon fonctionement se défini en disant que le modèle a une bonne utilité et respecte le contraintes qui lui sont demandé.
-Ces contraintes peuvent être pour impose l'équité ou la confidentialité par exemple.
-Ensuite, le paramètres sont utilisés pour réaliser de prédictions sur des données nouvelle, qui n'ont en générale pas été utilisés pour l'entraînement.
-Par exemple pour en revnir à la justice prédictive, les paramètre sont trouvé en utilisant des données historique de tribunaux.
-Le modèle est ensuite utilisé sur de nouveaux cas de comdanmé.
-Nous allons présenter ces deux aspects entraîenemnt et évaluation dans les Section qui suivent.
+En générale le bon fonctionnement se défini en disant que le modèle a une bonne utilité et respecte les contraintes qui lui sont demandé.
+Ces contraintes peuvent imposer l'équité ou la confidentialité par exemple.
+Ensuite, les paramètres sont utilisés pour réaliser des prédictions sur des données nouvelles, qui n'ont en générale pas été utilisés pour l'entraînement.
+Par exemple pour en revenir à la justice prédictive, les paramètre sont trouvé en utilisant des données historiques de tribunaux.
+Le modèle est ensuite utilisé sur de nouveaux cas de condamné.
+Nous allons présenter ces deux aspects, entraînent et évaluation, dans les Sections qui suivent.
\subsection{Entraîner un modèle}
\label{sec:background-ml-train}
-Les données qui servent à l'entraînement du modèle doivent posséder une étiquette : c'est-à dire le résultat atendu qui est consédéré comme vraie.
-Dans la justice prédictive il s'agit de savoir si le coupabe à été récidiviste après avoir été libéré.
-Pour prendre un exemple plus scolaire, sur le jeu de donnée Iris~\cite{iris_53}, on cherche à classifier l'éspèce d'Iris à partir de la longeur et de la largeur des sépales et des pétales.
-Nous utilisons, pour l'entraînement, des données de taille de sépale et pétale pour lesquelles nous conaissons l'espèce d'Iris.
-En utilisant ces données nous ajustons les paramètres pour que le prédiction soit la plus précise possible.
+Les données qui servent à l'entraînement du modèle doivent posséder une étiquette : c'est-à dire le résultat attendu qui est considéré comme vraie.
+Dans la justice prédictive il s'agit de savoir si le coupable à été récidiviste après avoir été libéré.
+Pour prendre un exemple plus scolaire, sur le jeu de donnée Iris~\cite{iris_53}, on cherche à classifier l'espèce d'iris à partir de la longueur et de la largeur des sépales et des pétales.
+Nous utilisons, pour l'entraînement, des données de taille de sépale et pétale pour lesquelles nous connaissons l'espèce d'iris.
+En utilisant ces données nous ajustons les paramètres pour que la prédiction soit la plus précise possible.
Pour ce faire nous utilisons une fonction de coût.
C'est une fonction qui sert à déterminer à quel point une prédiction est bonne.
-C'est-à dire que plus la fonction de coût renvoi un valeur petite, meilleur est le modèle.
+C'est-à-dire que plus la fonction de coût renvoi une valeur petite, meilleur est le modèle.
-Nous definisson le modèle suivant.
+Nous définissons le modèle suivant :
\begin{equation*}
f:
\left\{
@@ -56,19 +56,20 @@ Nous pouvons ainsi définir le coût induit par un choix de paramètres par la f
\end{matrix}
\right.
\end{equation*}
-Ainsi nous avons une fonctionelle $c:\theta\mapsto E(C(\theta))$ en prenant l'espérence de coût.
-Nous pouvons donc appliquer une descente de gradient comme vu à la Section~\ref{sec:background-opti-sgd} pour résoudre le probleme suivant :
+Ainsi nous avons une fonctionnelle $c:\theta\mapsto E(C(\theta))$ en prenant l'espérance de coût.
+Nous pouvons donc appliquer une descente de gradient comme vu à la Section~\ref{sec:background-opti-sgd} pour résoudre le problème suivant :
\begin{equation*}
\text{min}_{\theta\in\Theta}c(\theta)
\end{equation*}
-En pratique la quantité $c(\theta)$ est évalué avec la loi des grands nombres~\cite{proba}.
-$c$ n'étant pas forcément convexe, un fonction du point de départ ($x_0$) l'algorithme de descente de gradient peut converger ver un minimum locale qui donnera un modèle finale avec de piètre qualités.
-C'est ce que nous réprésentons dans la Figure~\ref{fig:background-opti-cvx} ou nous voyons un convergence ver un minimum local alors que le point rechercher étant au fond d'une vallée plus profonde.
+En pratique la quantité $c(\theta)$ est évalué en calculant la moyenne empirique sur un grande nombre de donnée ce qui converge vers l'espérance d'après la loi des grands nombres~\cite{proba}.
+$c$ n'étant pas forcément convexe, en fonction du point de départ ($x_0$) l'algorithme de descente de gradient peut converger vers un minimum local qui donnera un modèle finale avec de piètre qualités.
+C'est ce que nous représentons dans la Figure~\ref{fig:background-opti-cvx} où nous voyons une convergence vers un minimum local alors que le point recherché est au fond d'une vallée plus profonde.
-Très souvent l'algorithme d'optimisation utilisé est la déscente de gradient stochastique (SGD)\footnote{\textit{Stochastic gradient descent}}~\cite{amari1993back}, c'est une vérsion modifié de la descente de gradient adapté au réseaux de neurones qui permet d'accelerer la convergence~\cite{bottou2012stochastic} et d'éviter les minima locaux~\cite{bottou1991stochastic}.
-Cette algorithmes évalue l'espérence empirique de $C(\theta)$ sur chaque élément, appelé \textit{mini batch}, d'une partition des données d'entrainement.
+Très souvent l'algorithme d'optimisation utilisé est la descente de gradient stochastique (SGD)\footnote{\textit{Stochastic gradient descent}}~\cite{amari1993back}, c'est une version modifié de la descente de gradient adapté aux réseaux de neurones qui permet d'accélérer la convergence~\cite{bottou2012stochastic} et d'éviter les minima locaux~\cite{bottou1991stochastic}.
+Cet algorithme évalue l'espérance empirique de $C(\theta)$ sur chaque élément, appelé \textit{mini batch}, d'une partition des données d'entraînements.
-La recherche des paramètre d'entraînement comme la finesse de la partition ou le pas et en prétique réalisé par des algorithme qui parcours un espace de recherche et regarde l'entraînement pour quelques itérations~\cite{bergstra2015hyperopt}.
+La recherche des paramètre d'entraînement comme la finesse de la partition ou le pas est en pratique réalisé par des algorithmes qui parcours un espace de recherche et regarde l'entraînement pour quelques itérations~\cite{bergstra2015hyperopt}.
+Nous appelons cela l'\emph{optimisation des hyperparamètres}.
\begin{figure}
\begin{subfigure}{0.3\linewidth}
@@ -87,52 +88,52 @@ La recherche des paramètre d'entraînement comme la finesse de la partition ou
\label{fig:background-opti-cvx}
\end{figure}
-\subsection{Evaluer un modèle}
- Nous appelerons ici évaluation d'un modèle le calcule des metriques qui permettent de juger de son utilité.
- Ces métrique varient en fonction du type de modèle et du contexte dans lequel il est utilisé.
- Par exemple il est souhaitable qu'un modèle qui permette de prédir l'absence ou la présence d'une maladie ai un faible taux de faux négatifs.
- Cela permet d'éviter de penser à tords qu'une patient n'est pas malade ce qui pourrai entraîner un retard dans sa prise en charge.
+\subsection{Évaluer un modèle}
+ Nous appellerons ici évaluation d'un modèle, le calcul des métriques qui permettent de juger de son utilité.
+ Ces métriques varient en fonction du type de modèle et du contexte dans lequel il est utilisé.
+ Par exemple il est souhaitable qu'un modèle qui permette de prédire l'absence ou la présence d'une maladie ai un faible taux de faux négatifs.
+ Cela permet d'éviter de penser à tords qu'un patient n'est pas malade ce qui pourrai entraîner un retard dans sa prise en charge.
\subsubsection{Classification}
\label{sec:background-ml-classif}
- Les modèles de classification visent à attribuer à chaque point des données ébalué une classe parmis un ensemble fini.
- Par exemple, dans le cadre de la justice prédictive, inférer pour chaque coupable si il sera recidivise ou non~\cite{zhiyuan2020limits}.
- Quand il y a deux classes, comme dans l'exemple précédent avec \emph{récidivisite} ou \emph{non-récidiviste}, nous dirons que le modèle effectue un classification binaire.
- Ce cas est très présent en apprentissage automatique~\cite{li2020statistical, kumari2017machine} ainsi il existe beaucoup d'outils qui permettent d'evaluer ce genre de classifieur~\cite{canbek2022ptopi}.
+ Les modèles de classification visent à attribuer à chaque point des données évalué une classe parmi un ensemble fini.
+ Par exemple, dans le cadre de la justice prédictive, inférer pour chaque coupable si il sera récidiviste ou non~\cite{zhiyuan2020limits}.
+ Quand il y a deux classes, comme dans l'exemple précédent avec \emph{récidiviste} ou \emph{non-récidiviste}, nous dirons que le modèle effectue une classification binaire.
+ Ce cas est très présent en apprentissage automatique~\cite{li2020statistical, kumari2017machine} ainsi il existe beaucoup d'outils qui permettent d'évaluer ce genre de classifieur~\cite{canbek2022ptopi}.
- Nous modélisons le modèle que nous souhaite évaluer par une fonction $f:E\rightarrow \{0,1\}$
+ Nous représentons le modèle que nous souhaite évaluer par une fonction $f:E\rightarrow \{0,1\}$
C'est-à-dire que le modèle prend une donnée d'entrée dans $E$, cela peut être une image ou une ligne d'un tableau, et lui attribut soit la classe $0$ soit la classe $1$.
Nous dirons que $0$ est un résultat négatif et $1$ un résultat positif.
Pour évaluer correctement le modèle, nous devons prendre en compte la répartition dé données dans $E$.
- Nous modélisons cette repartition par les lois de probabilités de deux variables aléatoires :
+ Nous modélisons cette répartition par les lois de probabilités de deux variables aléatoires :
\begin{itemize}
- \item $X:\Omega\rightarrow \mathcal{X}$
+ \item $X:\Omega\rightarrow E$
\item $Y:\Omega\rightarrow \{0,1\}$
\end{itemize}
$(\Omega,\mathcal{T},P)$ est un espace probabilisé.
- Il n'est pas necessaire que nous définission de manière plus précise cet espace car nous ne nous interessons qu'aux mesure images de $X$ et $Y$ par $P$.
- Nous pouvons, de la même manière définire une variable aléatoire pour la sortie du modèle : $\hat{Y} = f\circ X$.
+ Il n'est pas nécessaire que nous définissons de manière plus précise cet espace car nous ne nous intéressons qu'aux mesure images de $X$ et $Y$ par $P$.
+ Nous pouvons, de la même manière définir une variable aléatoire pour la sortie du modèle : $\hat{Y} = f\circ X$.
- Grace à ces objets, nous allons définir des qunatités qui décrivent l'utilitée du modèle.
+ Grâce à ces objets, nous allons définir des quantités qui décrivent l'utilité du modèle.
La première est
- l'\emph{exactitude}\footnote{\textit{Accuracy}}, c'est la prababilté que le classifieur prédise la bonne classe. Nous la définissons par $P(\hat{Y}=Y)$.
- Cette définission, bien que très intuitive, souffre qu'elle est sensible au désequillibre de classe~\footnote{\textit{Class imablance}}.
- Considérons l'exemple suivant : imaginons un modèle depployé en 1982 qui chercheraià prédire si un employé cadre est une femme ou un homme.
- Supposons que ce modèle ai une exactitude de $79\%$, c'est-à-dire que le modèle prédit justement le genre huit fois sur dix, nous dirons certainement que ce modèle est performant ?
+ l'\emph{exactitude}\footnote{\textit{Accuracy}}, c'est la probabilité que le classifieur prédise la bonne classe. Nous la définissons par $P(\hat{Y}=Y)$.
+ Cette définition, bien que très intuitive, souffre qu'elle est sensible au déséquilibré de classe~\footnote{\textit{Class imablance}}.
+ Considérons l'exemple suivant : imaginons un modèle déployé en 1982 qui cherche à prédire si un employé cadre est une femme ou un homme.
+ Supposons que ce modèle ai une exactitude de $79\%$, c'est-à-dire que le modèle prédise justement le genre huit fois sur dix, nous dirons certainement que ce modèle est performant ?
Voici donc un modèle qui atteint cette performance :
\begin{equation}
f:
\left\{
\begin{matrix}
- \mathcal{X}\rightarrow \{\text{homme},\text{femme}\}\\
+ E\rightarrow \{\text{homme},\text{femme}\}\\
x\mapsto \text{homme}
\end{matrix}
\right.
\end{equation}
C'est-à-dire un modèle qui prédise toujours homme.
- Calculons son exactitude, pour plus lisibilité nons encodons homme par $0$ et femme par $1$.
+ Calculons son exactitude, pour plus de lisibilité nous encodons homme par $0$ et femme par $1$.
Comme le modèle prédit toujours homme, $P(\hat{Y}=0)=1$ et $P(\hat{Y}=1)=0$.
\begin{align}
&P(\hat{Y}=Y)\nonumber\\
@@ -141,30 +142,32 @@ La recherche des paramètre d'entraînement comme la finesse de la partition ou
=&1\cdot P(Y=0) + 0\cdot P(Y=1) = P(Y=0)\nonumber
\end{align}
- Or, en 1982 il y avait uniquement $21\%$ des cadres qui était des femmes~\cite{insee1982parite}, ansi $P(Y=0)=0,79$ et $P(Y=1)=0,21$.
+ Or, en 1982 il y avait uniquement $21\%$ des cadres qui était des femmes~\cite{insee1982parite}, ainsi $P(Y=0)=0,79$ et $P(Y=1)=0,21$.
Nous avons donc bien une exactitude de $79\%$ bien que le modèle n'ai aucune utilité pratique !
Ainsi l'exactitude est significative uniquement quand $Y$ suit une loi uniforme.
- Nous définisson donc une autre métrique : l'\emph{exactitude équillibrée}\footnote{\textit{balanced accuracy}}.
- Pour cela nous repartons de l'Equation~\ref{eq:background-ml-ac} et remplacons $P(Y=0)$ et $P(Y=1)$ par $\frac{1}{2}$.
- Ainsi l'exactitude équilibrée est la moyenne et $P(\hat{Y}=0|Y=0)$ et de $P(\hat{Y}=1|Y=1)$.
- C'est-à-dire que nous regardons pour chaque classes séparément (homme ou femme notre exemple) la probabilité qu'on point soit bien classifié.
- Ainsi, en calculant l'exactitude equilibrée avec l'exemple précedent nous obtenons $\frac{1+0}{2}=0,5$.
+ Nous définissons donc une autre métrique : l'\emph{exactitude équilibrée}\footnote{\textit{balanced accuracy}}.
+ Pour cela nous repartons de l'Equation~\ref{eq:background-ml-ac} et remplaçons $P(Y=0)$ et $P(Y=1)$ par $\frac{1}{2}$.
+ Ainsi l'exactitude équilibrée est la moyenne de $P(\hat{Y}=0|Y=0)$ et de $P(\hat{Y}=1|Y=1)$.
+ De manière plus générale, l'exactitude équilibrée est
+ $\sum_{e\in E}P(\hat{Y}=e\mid Y=e)$.
+ C'est-à-dire que nous regardons pour chaque classes séparément (homme ou femme dans notre exemple) la probabilité qu'un point soit bien classifié.
+ Ainsi, en calculant l'exactitude équilibrée avec l'exemple précèdent nous obtenons $\frac{1+0}{2}=0,5$.
Ce résultat montre bien que le modèle n'a pas d'utilité.
\paragraph{La courbe \textit{Receiver Operating Characteristic} (ROC)}
- Un grand nombre d'algorithme d'apprantissange automatiqeu pour la classification binaire optimise les paramètres d'un e fonctions à valeurs dans $[0,1]$ (ou dans un ensemble un bijection avec $[0,1]$).
- C'est le cas par exemple des résaux de neuronnes avec un unique neurones dans la couche finale, de la regression logistique, de la forêt aléatoire, etc.
+ Un grand nombre d'algorithme d'apprentissage automatique pour la classification binaire optimise les paramètres d'un e fonctions à valeurs dans $[0,1]$ (ou dans un ensemble un bijection avec $[0,1]$).
+ C'est le cas par exemple des réseaux de neurones avec un unique neurones dans la couche finale, de la régression logistique, de la forêt aléatoire, etc.
Nous appelons cette étape intermédiaire dans la classification, logit ou \textit{soft label}.
- La classification ce fait grace un seuil sur ce logit.
- C'est à dire que si on apelle $g(x)$ le logit de $x$, le modèle de classification peut se décomposer par : $f_\uptau = 1_{[\uptau,1]}\circ g$.
+ La classification ce fait grâce un seuil sur ce logit.
+ C'est à dire que si on appelle $g(x)$ le logit de $x$, le modèle de classification peut se décomposer par : $f_\uptau = 1_{[\uptau,1]}\circ g$.
- Ainsi si nous calculons l'exactitude, l'éxactitude équilibrée ou tout autre metrique que nous avons présenté précédament elle dépendra du seuil ($\uptau$).
- Pour palier cela nous regarons la ROC : une courbe parametrique qui au seuil associe le tau de faux positif (FPR)\footnote{\textit{False positive rate}} et le tau de vrai positif (TPR)\footnote{\textit{True positive rate}}.
- Nous definisson ces quantité comme suit :
+ Ainsi si nous calculons l'exactitude, l'exactitude équilibrée ou tout autre métrique que nous avons présenté précédemment elle dépendra du seuil ($\uptau$).
+ Pour palier cela nous regardons la ROC : une courbe paramétrique qui au seuil associe le taux de faux positif (FPR)\footnote{\textit{False positive rate}} et le taux de vrai positif (TPR)\footnote{\textit{True positive rate}}.
+ Nous définissons ces quantité comme suit :
\begin{itemize}
- \item $\text{fpr}(\uptau) = P(f_\uptau\circ X=1\mid Y=0)$
- \item $\text{tpr}(\uptau) = P(f_\uptau\circ X=1\mid Y=1)$
+ \item Taux de faux positifs : $\text{fpr}(\uptau) = P(f_\uptau\circ X=1\mid Y=0)$
+ \item Taux de vrais positifs $\text{tpr}(\uptau) = P(f_\uptau\circ X=1\mid Y=1)$
\end{itemize}
\begin{equation*}
\text{roc}:\left\{
@@ -196,23 +199,23 @@ La recherche des paramètre d'entraînement comme la finesse de la partition ou
\label{fig:background-ml-roc}
\end{figure}
- La courbe ROC montre que le seuil permet d'ajusté le compromis entre faux positif et vrai positif, en pratique ce compromis dépend de l'application.
- En effet, comme nous le voyons sur la Figure~\ref{fig:background-ml-roc}, si le seuil vaut $\uptau=0$, tous les points sont classifier positivement par le modèlé.
- Ainsi le taux de faux positif et maximal et vaux $1$.
- Dans le cas totalement opposé de $\uptau=1$ aucun point n'est classifier comme positif et donc il n'y a pas de faux positif mais il n'y a pas non plus de vrai positif.
- Il s'agit donc de trouver un équilibre entre ces deux extrèmes.
+ La courbe ROC montre que le seuil permet d'ajuster le compromis entre faux positif et vrai positif, en pratique ce compromis dépend de l'application.
+ En effet, comme nous le voyons sur la Figure~\ref{fig:background-ml-roc}, si le seuil vaut $\uptau=0$, tous les points sont classifié positivement par le modèle.
+ Ainsi le taux de faux positifs est maximal et vaux $1$.
+ Dans le cas totalement opposé de $\uptau=1$ aucun point n'est classifié comme positif et donc il n'y a pas de faux positif mais il n'y a pas non plus de vrai positif.
+ Il s'agit donc de trouver un équilibre entre ces deux extrêmes.
- Il peut être utile, pour comparer plusieur classifieur de résumer la ROC en une seule valuer.
- Pour cela nous utilise l'aire sous la courbe ROC, appele AUC~\footnote{\textit{Area Under the Curve}}.
- Comme nous le voyons sur la Figure~\ref{fig:background-ml-roc}, un classifieur qui malgré l'ajustement de son seuil reste un CCA a une AUC de $0,5$.
- Alors qu'un classifieur parfat, c'est-à dire pour lequel il exist un seuil qui produite un taux de faux positif nul et un tau de vrai positif égale à 1, a une AUC de $1$.
+ Il peut être utile, pour comparer plusieurs classifieurs de résumer la ROC en une seule valeur.
+ Pour cela nous utilisons l'aire sous la courbe ROC, appelé AUC~\footnote{\textit{Area Under the Curve}}.
+ Comme nous le voyons sur la Figure~\ref{fig:background-ml-roc}, un classifieur qui malgré l'ajustement de son seuil ne prédit pas correctement l'étiquette a une AUC de $0,5$.
+ Alors qu'un classifieur parfait, c'est-à-dire pour lequel il existe un seuil qui produit un taux de faux positif nul et un taux de vrai positif égale à 1, a une AUC de $1$.
- \subsubsection{Regression}
- La régression est un autre type de modèle qui cherche non pas à ranger une donnée dans une classe mais plutot à prédire un grandeur.
+ \subsubsection{Régression}
+ La régression est un autre type de modèle qui cherche non pas à ranger une donnée dans une classe mais plutôt à prédire une grandeur.
Par exemple prédire la masse d'une personne à partir de sa taille.
Nous avons vu dans la section précédente que certain modèle de classification utilise une étape intermédiaire de calcul de logit.
- Le calul de logit est une forme de regression car il s'agit de prédit une grandeur et non pas de choisir une classe.
- Pour mieux comprendre le lien entre ces deux type de modèle nous pouvons obsever l'exemple de la regression logistique.
+ Le calcul de logit est une forme de régression car il s'agit de prédit une grandeur et non pas de choisir une classe.
+ Pour mieux comprendre le lien entre ces deux type de modèles, nous pouvons observer l'exemple de la régression logistique.
\begin{figure}
\centering
\begin{subfigure}{0.3\linewidth}
@@ -233,33 +236,31 @@ La recherche des paramètre d'entraînement comme la finesse de la partition ou
\begin{subfigure}{0.6\linewidth}
\centering
\includegraphics[width=\linewidth]{background/figure/ml/logit/metric.pdf}
- \caption{Metriques de classifications en fonction du seuil.}
+ \caption{Métriques de classifications en fonction du seuil.}
\label{subfig:background-ml-logit-d}
\end{subfigure}
- \caption{Exemple de relation entre regression (logit) et prédiction.}
+ \caption{Exemple de relation entre régression (logit) et prédiction.}
\label{fig:background-ml-logit}
\end{figure}
- Dans la Figure~\ref{fig:background-ml-logit} nous avons l'exemple d'une regression logistique qui nous donne la coubre logit dans les trois premières sous-figures.
- Le seuil est représente par le changement de couleur tandis que les étiquettes sont réprésenté par la position sur l'axe de ordonée des points.
- Nous observons que changer la seuil permet d'influencer sur les différentes métriques que nous avons présenté en Section~\ref{sec:backgroung-ml-classif}.
- Le choix d'un seuil approrié est donc dépendant de l'application.
- Comme nous pouvons de le voir sur la Sous-figure~\ref{subfig:background-ml-logit-d}, seuil proche de $1$ permet de grandement réduire le FPR mais réduit les autres métriques.
- Le choix d'un seuil est aussi particulièrement important quand les données présentent un désequilibre, c'est-à-dire qu'une classe et majoritaire par rapport à une autre~\cite{zou2016finding}.
+ Dans la Figure~\ref{fig:background-ml-logit} nous avons l'exemple d'une régression logistique qui nous donne la courbe logit dans les trois premières sous-figures.
+ Le seuil est représenté par le changement de couleur tandis que les étiquettes sont représentées par la position sur l'axe de ordonnées.
+ Nous observons que changer le seuil permet d'influer sur les différentes métriques que nous avons présenté en Section~\ref{sec:backgroung-ml-classif}.
+ Le choix d'un seuil approprié est donc dépendant de l'application.
+ Comme nous pouvons de le voir sur la Sous-figure~\ref{subfig:background-ml-logit-d}, un seuil proche de $1$ permet de grandement réduire le FPR mais réduit les autres métriques.
+ Le choix d'un seuil est aussi particulièrement important quand les données présentent un déséquilibre, c'est-à-dire qu'une classe et majoritaire par rapport à une autre~\cite{zou2016finding}.
Dans la Figure~\ref{fig:background-ml-logit} il y $28\%$ de points positif représenté en rouge.
Cela explique la différence entre exactitude et exactitude équilibrée à seuil égale.
-
\subsection{Apprentissage profond}
-Pour le moment nous avons évoqué trois types de modèle, la forêt aléatoire, la regression logistique et les réseaux de neuronnes sans vraiment les présenter.
-Nous allons nous contenter de présenter en détail les réseaux de neuronnes car cela nous sera utile pour les Chapitres~\ref{sec:aia} et~\ref{sec:synth}.
+Nous allons présenter ici rapidement les réseaux de neurones dans un contexte d'inférence et de génération car cela nous sera utile pour les Chapitres~\ref{sec:aia} et~\ref{sec:synth}.
\subsubsection{Réseau de neurones}
-En apprentissage profond, l'expréssion explicite qui lie entrée, paramètre et sortie (que nous avons appelé $f(x,\theta)$ à la Section~\ref{sec:background-ml-train}) est appelé l'architecture du réseau de nerones.
-Dans cette section nous allons présenter quelques architectures calssiques.
-Pour en savoir plus à ce sujet et sur l'apprentissage automatiqeu en générale, nottamant pour avoir plus de détails sur l'entraînement, nous renvoyons le lecteur au livre de Yann Le Cun, \textit{Quand la machine apprend}~\cite{lecun2019quand}.
+En apprentissage profond, l'expression explicite qui lie entrée, paramètre et sortie (que nous avons appelé $f(x,\theta)$ à la Section~\ref{sec:background-ml-train}) est appelé l'architecture du réseau de neurones.
+Dans cette section nous allons présenter quelques architectures classiques.
+Pour en savoir plus à ce sujet et sur l'apprentissage automatique en générale, notamment pour avoir plus de détails sur l'entraînement, nous renvoyons le.la lecteur.rice au livre de Yann Le Cun, \textit{Quand la machine apprend}~\cite{lecun2019quand}.
-Un réseau de neuronnes est composé de plusieur couches successives qui on chacune des paramètre.
+Un réseau de neurones est composé de plusieurs couches successives qui on chacune des paramètres.
En d'autre termes un modèle
\begin{equation*}
f:\left\{
@@ -270,22 +271,22 @@ En d'autre termes un modèle
\right.
\end{equation*}
peut se décomposer comme une composition de modèle intermédiaires.
-Par exemple un modèle à $m$ couches peut s'ecrir :
+Par exemple un modèle à $m$ couches peut s'écrire :
\begin{equation*}
f(\Box,\theta) = f_{m-1}(\Box,\theta_{m-1})\circ\cdots\circ
f_{0}(\Box,\theta_0)
\end{equation*}
-Nous utiliserons deux types de couches : les couches entièrement connectée et les couches de convolution.
+Nous utiliserons deux types de couches : les couches entièrement connectée\footnote{\textit{Fully connected}} et les couches de convolution.
-Une couche entièrement connectée est elle même composé d'une multiplication matriciele, une addition à un vecteur et une fonctions d'activation.
-Considérons une couche intermédiare de $\mathbb{R}^o$ dans $\mathbb{R}^p$
-Nous diraons que cette couche a $p$ neurones.
-Nous utiliserons toujours la même fonction d'avivation : \textit{Rectified Linear} (ReLu).
+Une couche entièrement connectée est elle même composé d'une multiplication matricielle, une addition à un vecteur et une fonctions d'activation.
+Considérons une couche intermédiaire de $\mathbb{R}^o$ dans $\mathbb{R}^p$
+Nous dirons que cette couche a $p$ neurones.
+Nous utiliserons toujours la même fonction d'activation : \textit{Rectified Linear} (ReLu).
Cette fonction est définie de la manière suivante :
\begin{equation*}
\textit{ReLu}:\left\{
\begin{matrix}
- \mathbb{R}^n\rightarrow\left(\mathbb{R}^+\right)^n\\
+ \mathbb{R}^p\rightarrow\left(\mathbb{R}^+\right)^p\\
x\mapsto \left(
\begin{matrix}
1_{\mathbb{R}^+}(x_0)x_0\\
@@ -296,12 +297,12 @@ Cette fonction est définie de la manière suivante :
\end{matrix}
\right.
\end{equation*}
-Nous remarquons que cette fonction n'as pas de paramètre à opitmiser, son but et d'éviter que l'architecture gloable soit une fonction afine.
+Nous remarquons que cette fonction n'as pas de paramètre à optimiser, son but et d'éviter que l'architecture globale soit une fonction affine.
-La parite linéaire de la couche est paramétré par les coéficient de la matrie de l'application linéaire.
-Cette fonction $l$ admet donc comme expression $l(x)=Mx$ avec $M\in\mathcal{M}_{p,o}$
+La partie linéaire de la couche est paramétré par les coefficient de la matrice de l'application linéaire.
+Cette fonction $l$ admet donc comme expression $l(x)=Mx$ avec $M\in\mathbb{R}_{p,o}$
-Enfin la partie additive est appellée biais et s'écrit $B(x) = x+b$ avec $b\in\mathbb{R}^p$.
+Enfin la partie additive est appelée biais et s'écrit $B(x) = x+b$ avec $b\in\mathbb{R}^p$.
Ainsi la $i$-ième couche s'écrit :
\begin{equation*}
f_i(\Box,(M,b)) : \left\{
@@ -312,43 +313,58 @@ Ainsi la $i$-ième couche s'écrit :
\right.
\end{equation*}
-Regardon maintenant les couches de convolutions.
+Regardons maintenant les couches de convolutions.
L'idée de la convolution est d'extraire des représentations\footnote{\textit{Features extraction}} à partir d'un signal qui est généralement une image, un son ou la sortie d'un capteur analogique comme un gyroscope.
-Une architactre classque utilise les couches de convolution à l'entrée du réseau avant les couches linéaires.
-L'idée étant que le modèle comence par extraire de représntation pui les analysent.
+Une architecture classique utilise les couches de convolutions à l'entrée du réseau avant les couches entièrement connectées.
+L'idée étant que le modèle commence par extraire de représentations puis les analyse.
-Dans ce type de couche le paramètre $\theta_i$ est le noyeau de convolution.
-C'est la fonction par laquelle on mutlilpe le signal sous l'intégrale.
-Pour un noyeau de convolution de taille $c$
+Dans ce type de couche le paramètre $\theta_i$ est le noyau de convolution.
+C'est la fonction par laquelle on multiple le signal sous l'intégrale.
+Pour un noyau de convolution de taille $c$
\begin{equation}
f_i(x,\theta_i) = \left\{
\begin{matrix}
- \mathbb{R}^o\rightarrow\mathbb{R}^\mathbb{N}\\
+ \mathbb{R}^o\rightarrow\mathbb{R}^p\\
u\mapsto\int_{c}x'(u-t)\theta_i(t)d\sum_{j=0}^{c-1}\delta_j(t)
\end{matrix}
\right.
\end{equation}
-Où $x'$ est telque $x'(u-t)$ soit toujours bien défini par rembourrage\footnote{\textit{padding}}.
-
+Où $x'$ est tel que $x'(u-t)$ soit toujours bien défini par rembourrage\footnote{\textit{Padding}}.
-
-
-\subsubsection{Modèle generatif}
+\subsubsection{Modèle génératif}
\label{sec:background-generation}
-Une generateur est un fonction qui prend un entrée en jeu de données réel et renvoi un jeu de donnée sythetique.
-Cette définition est suffisament générale pour que l'identitée soit un générateur.
-Nous dirons que la sortie du generateur identité sont des données réels et nous appellerons donnée synthetique la sortie de n'importe quel autre générateur.
+Une générateur est une fonction qui prend en entrée un jeu de données réel et renvoi un jeu de donnée synthétique.
+Cette définition est suffisamment générale pour que l'identité soit un générateur.
+Nous dirons que la sortie du générateur identité sont des données réels et nous appellerons donnée synthétique la sortie de n'importe quel autre générateur.
-En plus du générateur identitée nous utiliserons des réseaux de neuronnes adversariels generatifs~\footnote{\textit{Genertaiv Adversarial Network}} (GAN)~\cite{gan}.
-Le but d'un GAN est de générer des échantillons réalisation étant donné une loi de probabilité.
-Pour arriver à cela, un GAN utilise deux réseaux de neuronnes : un générateur et un discriminateur.
+En plus du générateur identité nous utiliserons des réseaux de neurones adverse génératifs~\footnote{\textit{Genertaiv Adversarial Network}} (GAN)~\cite{gan}.
+Le but d'un GAN est de générer des échantillons réalistes étant donné une loi de probabilité.
+Pour arriver à cela, un GAN utilise deux réseaux de neurones : un générateur et un discriminateur.
Le domaine du générateur est de petit dimension relativement à son codomaine.
La dimension du codomaine est la même que celle des données que l'on souhaite générer.
Par exemple pour générer de images de taille 64 par 64, le codomaine est $\mathbb{R}_{64,64}$.
-Pour générer une donnée, nous évaluons le générateur sur un point generer à partir d'une loi normale multidimensionelle.
+Pour générer une donnée, nous évaluons le générateur sur un point généré à partir d'une loi normale multidimensionnelle.
La sortie de générateur est la nouvelle donnée généré.
-Le discriminateur est utilisé uniquement lors de l'entraînement du GAN et à a pour but de s'assurer que le générateur produise des données réalistes.
-Pour cela, le discriminateur est un réseau de neurones ayant une tâche de classification : inférer si une donnée est synthétique et réel.
-Ainsi, dans la procédure d'entraînement, le discriminateur et el générateur sont en compétition : le but du générateur est de tromper le discriminateur à classifier une donnée synthétique comme réel.
+Le discriminateur est utilisé uniquement lors de l'entraînement du GAN et a pour but de s'assurer que le générateur produise des données réalistes.
+Pour cela, le discriminateur est un réseau de neurones ayant une tâche de classification : inférer si une donnée est synthétique ou réel.
+Ainsi, dans la procédure d'entraînement, le discriminateur et le générateur sont en compétition : le but du générateur est de tromper le discriminateur à classifier une donnée synthétique comme réel.
+
+\subsection{Apprentissage ensembliste}
+L'apprentissage ensembliste\footnote{\textit{Ensemble learning}} vise à combiner plusieurs classifieurs pour en obtenir un nouveau plus performant.
+Cette procédure se passe en deux temps.
+Le premier consiste à créer un ensemble de classifieur faibles.
+Le second consiste à combiner ces classifieurs pour en obtenir un nouveau efficace.
+Bien sure ces deux étapes sont liées et doivent être réfléchies ensembles.
+
+L'apprentissage ensembliste intervient à deux niveau dans ce manuscrit.
+Déjà nous utiliserons beaucoup la forêt aléatoire\footnote{\textit{Random forest}} qui est un algorithme particulièrement efficace pour les bases de donnée tabulaires~\cite{shwartz2022tabular,grinsztajn2022tree}.
+La forêt aléatoire~\cite{breiman2001random} construit des arbres de décisions sur des sous ensembles de la base de donnée d'entraînement et sur des projections aléatoirement choisit des donnée\footnote{\textit{Feature bagging}}.
+
+Ensuite au Chapitre~\ref{sec:fini} nous allons crée un nouvel algorithme de votation\footnote{\textit{Voting}} : une manière de combiner plusieurs classifieurs.
+Cet algorithme se basera la notion d'espace de compréhension.
+Un espace de compréhension\footnote{\textit{Behavior knowledge space}} est une application qui associa aux prédictions d'une vecteur de classifieurs une prédiction optimale~\cite{1688199}.
+Pour $f_0,\cdots,f_n$ classifieurs à valeur dans $E$, l'espace de compréhension $e$ est une fonction de $E^n$ dans $E$.
+Ainsi, pour une donnée d'entrée $x$ la prédiction retenue sera $e(f_0(x),\cdots,f_n(x))$~\cite{1626170}.
+
diff --git a/background/opti.tex b/background/opti.tex
index 0472d26..bb2ec17 100644
--- a/background/opti.tex
+++ b/background/opti.tex
@@ -1,27 +1,27 @@
-L'optimisation est une branche des mathématiques appliquées qui cherche à trouver les points pour lequels une fonctions réalise un certain nombre d'exigences.
-Le lecteur pourra se reférer par exemple au libre de Phillipe G. Ciarlet \textit{Introduction à l'analyse numérique matricielle et à l'optimisation}~\cite{ciarlet} pour une présentation très complète d'un grand nombre de techniques.
-Dans ce manuscrit nous ne nous interesseront qu'a deux type de problèmes liées à l'apprantissange automatique et surtout au réseaux de neuronnes.
-Le premier de ces problèmes est la minimisation sans contrainte d'une fonctionelle convexe.
-Cela permet l'entraînement de modèle d'apprantissage automatique à l'aide d'une fonction de coût.
+L'optimisation est une branche des mathématiques appliquées qui cherche à trouver les points pour lesquels une fonction réalise un certain nombre d'exigences.
+Le lecteur pourra se référer par exemple au livre de Phillipe G. Ciarlet \textit{Introduction à l'analyse numérique matricielle et à l'optimisation}~\cite{ciarlet} pour une présentation très complète d'un grand nombre de techniques.
+Dans ce manuscrit nous ne nous intéresserons qu'a deux type de problèmes liées à l'apprentissage automatique et surtout au réseaux de neurones.
+Le premier de ces problèmes est la minimisation sans contrainte d'une fonctionnelle convexe.
+Cela permet l'entraînement de modèles d'apprentissage automatique à l'aide de fonctions de coûts.
Le second problème reprend le premier mais y ajoute des contraintes.
C'est à dire, comme minimise-t'on le coût tout en garantissant certaines conditions ?
\subsubsection{Optimisation sans contrainte : Descente de gradient}
\label{sec:background-opti-sgd}
-Nous appellons fonctionelles les fonctions $\mathbb{R}^n$ dans $\mathbb{R}$.
-Soit $J$ une fonctionelle convexe, nous cherchons à trouver $x\in\mathbb{R}$ tel que $J(x) = \text{inf}\{J(t)\mid t\in\mathbb{R}\}$.
-Pour simplifier cette rapide présentation, nous supposerons que $J$ à toujours les conditions de régularité (diférentiabilié) suffisante pour les opérations que nous appliquerons.
+Nous appelons fonctionnelles les fonctions de $\mathbb{R}^n$ dans $\mathbb{R}$.
+Soit $J$ une fonctionnelle convexe, nous cherchons à trouver $x\in\mathbb{R}^n$ tel que $J(x) = \text{inf}\{J(t)\mid t\in\mathbb{R}^n\}$.
+Pour simplifier cette rapide présentation, nous supposerons que $J$ à toujours les conditions de régularité (différentiabilité) suffisante pour les opérations que nous appliquerons.
Pour trouver $x$ qui minimise $J$ une des méthode les plus utilisé en apprentissage automatique est la descente de gradient.
-Il s'agit de construire une suite $(x_k)_{k\in\mathbb{N}}$ telle que à chauqe étape la direction de descente soit optimale.
-L'idée pour arriver à cela et de considérer une approximation de l'accroissement de $J$ en utiliant la définition du gradient.
+Il s'agit de construire une suite $(x_k)_{k\in\mathbb{N}}$ telle que à chaque étape la direction de descente soit optimale.
+L'idée pour arriver à cela est de considérer une approximation de l'accroissement de $J$ en utilisant la définition du gradient.
-On cherche $h$ tel que $||h||=1$ et $J(x_k+h)$ soit minimal.
+On cherche $h$ tel que $||h||=1$ et $J(x_k+h)$ soit minimal.
D'après la définition du gradient
\begin{equation*}
J(x_k+h) = J(x_k) + \langle\nabla J(x_k),h\rangle + ||h||\epsilon(h)
\end{equation*}
On cherche alors à résoudre (*) : $min_{||h||=1}\langle\nabla J(x_k),h\rangle$.
-D'après l'inégalite de Cauchy-Schwartz
+D'après l'inégalité de Cauchy-Schwartz
\begin{equation*}
\forall h~||h||=1\implies~|\langle\nabla J(x_k),h\rangle |\leq ||\nabla J(x_k)||
\end{equation*}
@@ -32,14 +32,14 @@ Et aussi
\end{equation*}
$h=-\frac{\nabla J(x_k)}{||\nabla J(x_k)||}$ est donc solution de (*) pour que $\langle\nabla J(x_k),h\rangle$ soit négatif.
-Ainsi la méthode de déscente de gradient est définit par la suite
+Ainsi la méthode de descente de gradient est définit par la suite
$x_{k+1}=x_k-l_k\nabla J(x_k)$.
$l_k$ est appelé le pas.
-En théorie nous pouvons lire dans le libre de Ciarlet qu'il existe de multiple manière de trouver un pas optimale ou approprié à la fonctionelle $J$.
-Cependant, en apprantissage automatique le hypothèse necessaire pour obtenir l'optimalité sont souvent absentes, en pratique le pas est souvant choisit constant $\exists c\forall k~l_k=c$.
+En théorie nous pouvons lire dans le livre de Ciarlet qu'il existe de multiple manières de trouver un pas optimale ou approprié à la fonctionnelle $J$.
+Cependant, en apprentissage automatique les hypothèses nécessaires pour obtenir l'optimale sont souvent absentes, en pratique le pas est souvent choisit constant $\exists c\forall k~l_k=c$.
-Nous montrons dans la Figure~\ref{fig:background-opti-gd} le fonctionement de la méthode de gradient à pas fixe en dimension un pour une fonctionelle convexe.
-Avec une illustration de la convergence de l'écart entre $J(x_k)$ et le minimum.
+Nous montrons dans la Figure~\ref{fig:background-opti-gd} le fonctionnement de la méthode de gradient à pas fixe en dimension un pour une fonctionnelle convexe
+avec une illustration de la convergence de l'écart entre $J(x_k)$ et le minimum.
\begin{figure}
\centering
\begin{subfigure}{0.45\linewidth}
@@ -60,21 +60,21 @@ Avec une illustration de la convergence de l'écart entre $J(x_k)$ et le minimum
\subsubsection{Optimisation sous contraintes : multiplicateurs de Lagrange}
-\label{ref:background-opti-sous}
-Pour expliquer ce qu'est l'optimisation sous contraintes, represnons les mots de Philipe G. Ciarlet :
-\textquote{On s'interesse au problème suivant : trouver des conditions \emph{nécessaires}, et des conditions \emph{suffisantes}, pour qu'un point d'un ensemble $U$ soit un extremum relatif de la restriction à l'ensemble $U$ d'une fonction $J$ définie sur un ensemble "plus grands". [...]
+\label{sec:background-opti-sous}
+Pour expliquer ce qu'est l'optimisation sous contraintes, reprenons les mots de Philipe G. Ciarlet :
+\textquote{On s'intéresse au problème suivant : trouver des conditions \emph{nécessaires}, et des conditions \emph{suffisantes}, pour qu'un point d'un ensemble $U$ soit un extremum relatif de la restriction à l'ensemble $U$ d'une fonction $J$ définie sur un ensemble "plus grands". [...]
Un premier exemple est celui des \emph{extremums relatifs liés}, où l'ensemble $U$ est de la forme
\begin{equation*}
U=\{v\in V \mid \forall i\in m-1~\varphi_i(v)\leq 0\}
\end{equation*}
}
-On introduit le Lagrangien de ce problèmes par la formule suivante:
+On introduit le lagrangien de ce problèmes par la formule suivante:
\begin{equation*}
L:\left\{
\begin{matrix}
V\times\mathbb{R}^m_+\\
- (v,\mu)\mapsto J(v)+\sum_{i=0}^{m-1}\mu_i\varphi(v)
+ (v,\mu)\mapsto J(v)+\sum_{i=0}^{m-1}\mu_i\varphi_i(v)
\end{matrix}
\right.
\end{equation*}
@@ -86,10 +86,10 @@ c'est-à-dire, un point $(u,\lambda)\in V\times \mathbb{R}^m_+$ tel que
\end{equation*}
$u$ est alors solution du problème.
-Il est donc suffisant de connaitre $\lambda$ appelé \emph{multiplicateurs de Lagrange} pour pouvoir trouver $u$ en se ramensant au cas sans contraintes de la section précédente.
-Trouver $\lambda$ s'apelle le \emph{problème dual} en contrepartie de la recheche de $u$ qui est le \emph{problème primal}.
-Le problème dual bénéficie du fait que ces contraintes sont plus simples car il sagi uniquement de la positivité des multiplicateur de Lagrange.
+Il est donc suffisant de connaître $\lambda$ appelé \emph{multiplicateurs de Lagrange} pour pouvoir trouver $u$ en se ramenant au cas sans contraintes de la section précédente.
+Trouver $\lambda$ s'appelle le \emph{problème dual} en contrepartie de la recherche de $u$ qui est le \emph{problème primal}.
+Le problème dual bénéficie du fait que les contraintes sont plus simples car il s'agit uniquement de la positivité des multiplicateur de Lagrange.
Le problème dual s'écrit donc $sup (inf_{v\in V}L(v,\square))$.
-Pour une présentation plus complète des multiplicateurs de Lagrange et de la dualité voir les Sections 7.2 et 9.3 du Livre de Ciarlet~\cite{ciarlet}
+Pour une présentation plus complète des multiplicateurs de Lagrange et de la dualité voir les Sections 7.2 et 9.3 du livre de Ciarlet~\cite{ciarlet}
diff --git a/background/proba.tex b/background/proba.tex
index 55bca7a..2ff37b7 100644
--- a/background/proba.tex
+++ b/background/proba.tex
@@ -1,19 +1,19 @@
-La théorie des probability est profondément liée à l'apprentissage automatique.
-Les propriétés de modèles comme la confidentialité différencielle, les définitions d'équitée, les métriques d'utilité, etc. que nous aborderons en Section~\ref{sec:background-ml} s'ecrivent en terme de probabilité.
-Ainsi nous présentons les notions de probabitlié et de théorie d la mesure que nous allons utiliser.
+La théorie des probabilités est profondément liée à l'apprentissage automatique.
+Les propriétés de modèles comme la confidentialité différentielle, les définitions d'équité, les métriques d'utilité, etc. que nous aborderons en Section~\ref{sec:background-ml} s'écrivent en terme de probabilité.
+Ainsi nous présentons les notions de probabilités et de théorie de la mesure que nous allons utiliser.
A la manière de la Section~\ref{sec:background-set}, notre présentation à principalement le but de fixer les objets que nous utiliserons dans les prochaines sections et non pas d'être un cours complet.
-Si le lecteur souhaite en apprendre plus sur la theorie de la mesur nous le renvoyons vers les notes de cours de Thierry Gallay de l'université Joseph Fourrier~\cite{mesure}.
-Si il souhait explorer plus en avant les probabilités il poura consulter les notes de cours de Jean-François Le Gall de l'Ecole Normale Supérieur de Paris~\cite{proba}.
+Si le.la lecteur.rice souhaite en apprendre plus sur la théorie de la mesure nous le renvoyons vers les notes de cours de Thierry Gallay de l'université Joseph Fourrier~\cite{mesure}.
+Si il.elle souhait explorer plus en avant les probabilités il.elle pourra consulter les notes de cours de Jean-François Le Gall de l'École Normale Supérieur de Paris~\cite{proba}.
Soit $A$ un ensemble.
-Nous appelons une tribue que nous notons $\mathcal{A}$ un sous esemble de $\mathcal{P}(A)$ qui contien $\emptyset$ et $A$, qui est stable par complémentaire et qui est stable par union dénombrable d'elements de $\mathcal{A}$.
-Nous disons que $(A,\mathcal{A})$ est un espace mesurable.
-Soit maintenant $A\subset\mathcal{P}(A)$, nous appellons $\sigma(A)$ la plus petite tribue pour l'intersection qui contienne tous les élements de $A$.
+Nous appelons une tribu que nous notons $\mathcal{A}$ un sous ensemble de $\mathcal{P}(A)$ qui contient $\emptyset$ et $A$, qui est stable par complémentaire et qui est stable par union dénombrable d'éléments de $\mathcal{A}$.
+Nous disons alors que $(A,\mathcal{A})$ est un espace mesurable.
+Soit maintenant $A\subset\mathcal{P}(A)$, nous appelons $\sigma(A)$ la plus petite tribu pour l'intersection qui contient tous les éléments de $A$.
Nous appelons mesure, une fonction $d$ :$\mathcal{A}$ $\rightarrow$ $[0,+\infty]$ telle que $d(\emptyset) = 0$ et $d\left(\bigcup_{i\in \mathbb{N}} A_i\right) = \sum_{i\in \mathbb{N}}d(A_i)$ pour tout $(A_1, A_2, \cdots) \in \mathcal{A}^\mathbb{N} $ avec $\forall (i,j) A_i\cap A_j = \emptyset$.
Nous disons alors que $(A, \mathcal{A}, d)$ est un espace mesuré.
-Pour un espace mesurable $(A,\mathcal{P}(A))$, la mesure de dirac est la mesure telle que pour $a\in A$
+Pour un espace mesurable $(A,\mathcal{P}(A))$, la mesure de Dirac est la mesure telle que pour $a\in A$
\begin{equation*}
\delta_a : \left\{
\begin{matrix}
@@ -44,7 +44,7 @@ Alors l'espace $(A\times B,\mathcal{A}\otimes\mathcal{B},d\otimes e)$ est un esp
Nous appelons fonction mesurable, une fonction de $A$ à $B$ telle que $\forall b\in\mathcal{B}$~$f^{-1}(b)\in\mathcal{A}$.
Nous notons alors $f:(A, \mathcal{A})\rightarrow (B, \mathcal{B})$ ou $f:(A, \mathcal{A},d)\rightarrow (B, \mathcal{B})$
-Nous definisson la mesure image de $f$ par $d$, que nous notons $d_f$, par l'expression suivante :
+Nous définissons la mesure image de $f$ par $d$, que nous notons $d_f$, par l'expression suivante :
\begin{equation}
d_f:
\left\{
@@ -59,7 +59,7 @@ Nous definisson la mesure image de $f$ par $d$, que nous notons $d_f$, par l'exp
\begin{definition}{Intégrale}
Soient $(E,\mathcal{E},\mu)$ un espace mesuré.
Pour une fonction $f=\sum_{i\in I}\alpha_i 1_{A_i}$, nous dirons étagé,
- Avec $\{A_i\mid i\in I\} \subset \mathcal{E}$ et $\alpha_i\in\mathbb{R}^+$.
+ avec $\{A_i\mid i\in I\} \subset \mathcal{E}$ et $\alpha_i\in\mathbb{R}^+$.
alors $\int_E f d\mu= \sum_{i\in I}\alpha_i \mu(A_i)$.
Soit $g$ un fonction mesurable de $(E,\mathcal{E},\mu)$ dans $\mathbb{R}^+$, alors
@@ -75,15 +75,24 @@ Nous definisson la mesure image de $f$ par $d$, que nous notons $d_f$, par l'exp
\end{definition}
-Dans le cas particulier où $d(A) = 1$, nous appelons $d$ une mesure de probabilité.
- $(A,\mathcal{A},d)$ est alors un espace probailisé et les fonctions mesurables sur cet espace sont appelés variables aléatoires.
-Le loi de probabilité d'une variable aléatoire $f$ sur $(X,\mathcal{X})$ est la mesure image de $f$ sur $d$.
-Nous dirons que deux variables aléatoire $f$ et $g$ sont indépendantes si et seulement si la loi de la variables aléatoire $h:\omega\mapsto (f(\omega),g(\omega))$ est la mesur produit de la loi de $f$ et $g$.
+Dans le cas particulier où $d(A) = 1$, nous appelons $d$ une mesure de probabilité
+ $(A,\mathcal{A},d)$ est alors un espace probabilisé et les fonctions mesurables sur cet espace sont appelés variables aléatoires.
+Pour un évènement $a\in\mathcal{A}$ tel que $d(a)\neq 0$, la probabilité conditionnelle est
+\begin{equation*}
+ d(\square\mid a):\left\{
+ \begin{matrix}
+ \mathcal{A}\rightarrow [0,1]\\
+ b\mapsto \frac{d(a\cap b)}{d(a)}
+ \end{matrix}
+ \right.
+\end{equation*}
+La loi de probabilité d'une variable aléatoire $f$ sur $(X,\mathcal{X})$ est la mesure image de $f$ sur $d$.
+Nous dirons que deux variables aléatoire $f$ et $g$ sont indépendantes si et seulement si la loi de la variables aléatoire $h:\omega\mapsto (f(\omega),g(\omega))$ est la mesure produit de la loi de $f$ et $g$.
-De plus, dans le cas des variables aléatoires, il est courant de d'écrir $\{f\in A\}$ pour $f^{-1}(A)$ et $\{f=a\}$ pour $f^{-1}(\{a\})$.
+De plus, dans le cas des variables aléatoires, il est courant d'écrire $\{f\in A\}$ pour $f^{-1}(A)$ et $\{f=a\}$ pour $f^{-1}(\{a\})$.
-\begin{definition}{Esperence}
- Pour une variable aléatoire $X$, on définit l'espérence de $X$ par la formule suivante.
+\begin{definition}{Espérance}
+ Pour une variable aléatoire $X$, on définit l'espérance de $X$ par la formule suivante.
\begin{equation*}
E(X) = \int_{\Omega}X(\omega)dP(\omega)
\end{equation*}
diff --git a/background/set.tex b/background/set.tex
index 5aaffdd..ee5c2c1 100644
--- a/background/set.tex
+++ b/background/set.tex
@@ -1,46 +1,46 @@
-Commencons donc cette section préliminaire avec les définitions et quelques porpiété des ensemble et de fonctions.
-Commencons par les ensembles.
+Commençons donc cette section préliminaire avec les définitions et quelques propriétés des ensembles et de fonctions.
+Commençons par les ensembles.
Nous utilisons ici la théorie des ensembles Zermelo–Fraenkel (ZF).
-Si nous avons, dans ce manuscrit, besoin d'objet plus grand que les ensembles, nous les appelerons classes bien qu'il soit hors de propos de présenter ici la théorie Von Neumann–Bernays–Gödel (NBG).
-Nous allons présenter ZF de manière assez succinte, juste suffisante pour réaliser les clalculs du Chapitre~\ref{sec:fini}.
-Si le lecteur souhaite plus de détail sur ces théories nous le renvoyons à \textit{Elements of set thoery} de Herbert B. Enderton~\cite{enderton1977elements}.
+Si nous avons, dans ce manuscrit, besoin d'objet plus grands que les ensembles, nous les appellerons classes bien qu'il soit hors de propos de présenter ici la théorie Von Neumann–Bernays–Gödel (NBG).
+Nous allons présenter ZF de manière assez succincte, juste suffisante pour réaliser les calculs du Chapitre~\ref{sec:fini}.
+Si le.la lecteur.rice souhaite plus de détails sur ces théories il.elle peut consulter \textit{Elements of set thoery} de Herbert B. Enderton~\cite{enderton1977elements}.
-\subsubsection{Axiomes de la théroie ZF}
+\subsubsection{Axiomes de la théorie ZF}
\label{sec:background-math-zf}
Nous présentons dans cette section les axiomes de la théorie ZF.
-Ces axiomes sont la pierre angulaire des tous les dévleppoements mathématiques que nous ferons dans ce manuscrit.
-Pour un lecteur qui ne serai pas familier de cette théorie, disons qu'il s'agit de modéliser formellement le principe d'ensemble.
-C'est à dire le principe de ranger des choses, les éléments, dans des boîtes, les ensembles.
+Ces axiomes sont la pierre angulaire des tous les développements mathématiques que nous ferons dans ce manuscrit.
+Pour un.e lecteur.rice qui ne serai pas familier.ère de cette théorie, disons qu'il s'agit de modéliser formellement le principe d'ensemble.
+C'est-à-dire le principe de ranger des choses, les éléments, dans des boîtes, les ensembles.
\paragraph{Axiome d'Extensionnalité}
-Deux ensemble $A$ et $B$ sont égaut si et seulement si ils ont les mêmes éléments.
-\begin{equation}
+Deux ensemble $A$ et $B$ sont égaux si et seulement si ils ont les mêmes éléments.
+\begin{equation*}
\forall A\forall B (\forall x~x\in A \iff x\in B) \implies A=B
-\end{equation}
+\end{equation*}
-\paragraph{Axiome de l'Ensemble vide}
-Il exite un ensemble qui ne contient aucun élément.
+\paragraph{Axiome de l'ensemble vide}
+Il existe un ensemble qui ne contienne aucun élément.
Nous le notons donc $\{\}$ ou $\emptyset$.
\paragraph{Axiome de la Paire}
-\begin{equation}
+\begin{equation*}
\forall A \forall B \exists \{A,B\}\forall c(c\in \{A,B\}\iff c=A\vee c=B)
-\end{equation}
+\end{equation*}
\paragraph{Axiome de l'Union}
-Pour tout ensembles $A$, il exist un ensemble $\bigcup A$ qui soit exactement composé des éléments de chaque élément de $A$.
-\begin{equation}
+Pour tout ensemble $A$, il existe un ensemble $\bigcup A$ qui soit exactement composé des éléments de chaque élément de $A$.
+\begin{equation*}
\forall A \exists \bigcup A \forall b \left(b\in\bigcup A\iff \exists a\in A~ b\in a\right)
-\end{equation}
+\end{equation*}
\paragraph{Axiome de l'ensemble des parties}
Pour tout ensemble $A$ il existe un ensemble $\mathcal{P}(A)$ qui est l'ensemble des sous-ensembles (ou parties) de $A$.
-\begin{equation}
+\begin{equation*}
\forall A \exists \mathcal{P}(A) ~ P\subset A \iff P\in \mathcal{P}(A)
-\end{equation}
+\end{equation*}
-\paragraph{Axiome \textit{Aussonderung}}
-Pour toute formule $F$ (au sens du clacul des prédicats et du vocabulaire $\in$, $=$) qui ne pédend pas de $B$ et tout ensemble A, il existe un ensemble $B = \{a\in A | F\}$ qui est tel que
+\paragraph{Axiome de séparation}\footnote{\textit{Aussonderung}}
+Pour toute formule $F$ (au sens du calcul des prédicats et du vocabulaire $\in$, $=$) qui ne dépend pas de $B$ et tout ensemble A, il existe un ensemble $B = \{a\in A | F\}$ qui est tel que
$\forall b\in B (b\in A \wedge F)$
\begin{definition}[Intersection]
@@ -63,23 +63,23 @@ $\forall b\in B (b\in A \wedge F)$
\textbf{Relation.}
Nous appelons \emph{relation} un ensemble de 2-uplets.
- L'\emph{ensemble de définision} d'une relation $R$ est
+ L'\emph{ensemble de définition} d'une relation $R$ est
$\mathcal{D}_R = \{x~|~\exists y~(x,y)\in R\}$.
L'\emph{image} d'une relation est $Img(R) = \{y~|~\exists x~(x,y)\in R\}$.
- Une relation symmetrique ($\forall x\forall y~(x,y)\in R \iff (y,x)\in R$),
- reflexive ($\forall x~(x,x)\in R$) et
+ Une relation symétrique ($\forall x\forall y~(x,y)\in R \iff (y,x)\in R$),
+ réflexive ($\forall x~(x,x)\in R$) et
transitive ($\forall x\forall y\forall z~(x,y)\in R\wedge (y,z)\in R\implies (x,z)\in R $)
- est appelé une \emph{relation d'équivalance}.
- Pour tout $a$, nous notons $[a]_R = \{b~|~(a,b)\in R\}$ la \emph{classes d'équivalance} de $a$.
- Nous notons $A/R$ l'ensemble des classes d'équivlance d'une relation $R$ sur un ensemble $A$.
+ est appelé une \emph{relation d'équivalence}.
+ Pour tout $a$, nous notons $[a]_R = \{b~|~(a,b)\in R\}$ la \emph{classes d'équivalence} de $a$.
+ Nous notons $A/R$ l'ensemble des classes d'équivalence d'une relation $R$ sur un ensemble $A$.
\textbf{Fonction.}
Une \emph{fonction} $f$ est un relation telle que
- \begin{equation}
+ \begin{equation*}
\forall x\in D_f\left((x,y)\in f\wedge (x,z)\in f\implies y=z\right)
- \end{equation}
+ \end{equation*}
Pour tout ensemble $E$ et $F$ tels que $D_f\subset E$ et $Img(f)\subset F$ nous notons
- \begin{equation}
+ \begin{equation*}
f:
\left\{
\begin{matrix}
@@ -87,9 +87,9 @@ $\forall b\in B (b\in A \wedge F)$
x\mapsto f(x)
\end{matrix}
\right.
- \end{equation}
+ \end{equation*}
Où la notation $x\mapsto f(x)$ signifie que $(x,f(x))\in f$.
- En particulier, la fonction identitée est telle que
+ En particulier, la fonction identité est telle que
\begin{equation*}
id_E:\left\{
\begin{matrix}
@@ -109,45 +109,42 @@ $\forall b\in B (b\in A \wedge F)$
\right.
\end{equation*}
- Pour une expression $f(x)$, quand cela est pertinant nous noterons $f(\square)$ la fonction $f:x\mapsto f(x)$ quand il n'y a pas d'ambiguitée sur le domaine et codomaine.
+ Pour une expression $f(x)$, quand cela est pertinent nous noterons $f(\square)$ la fonction $f:x\mapsto f(x)$ quand il n'y a pas d'ambiguïté sur le domaine et codomaine.
\textbf{Produit cartésien.}
Soit $A$ un ensemble $f$ une fonctions le produit cartésien est
- \begin{equation}
+ \begin{equation*}
\bigtimes_{a\in A}f(a) =
\left\{
g~|~D_g=A\wedge (\forall a\in A~g(a)\in f(a))
\right\}
- \end{equation}
+ \end{equation*}
Si $A=\{i,j\}$ et $f(i)=B$ et $f(j)=C$ nous notons le produit cartésien : $B\times C$.
Si pour tout $a\in A~f(a)=B$ nous notons le produit cartésien $B^{A}$.
\end{definition}
-
-
-
Nous dirons qu'une fonction $f:E\rightarrow F$ est injective si et seulement si $\forall (x,y)\in E^2(f(x)=f(y)\implies x=y$).
- Nous dirons aussi que $f$ est surjective si et sulement si $\forall y\in F\exists x\in E~f(x)=y$.
+ Nous dirons aussi que $f$ est surjective si et seulement si $\forall y\in F\exists x\in E~f(x)=y$.
Dans le cas où $f$ serait à la fois injective et surjective nous dirons qu'elle est bijective et que les ensembles $E$ et $F$ sont en bijection.
- Pour une bijection $f$ de $E$ dans $F$ nous notons $f^{-1} : y\mapsto x~\text{tel que}~f(x)=y$.
- Dans le cas où $f$ n'est pas bijective, nous définison cette notation de la manière suivant :
+ Pour une bijection $f$ de $E$ dans $F$ nous notons $f^{-1} : y\mapsto x~\text{tel que}~f(x)=y$, c'est la fonction inverse de $f$.
+ Dans le cas où $f$ n'est pas bijective, nous définissons cette notation de la manière suivant :
pour $B\subset F$,
- $f^{-1}(B)=\{x\in E\mid f(x)\in B$.
-
+ $f^{-1}(B)=\{x\in E\mid f(x)\in B\}$,
+ c'est l'image réciproque de $f$.
\paragraph{Axiome du choix}
-Cette axiome nous assure qui si tous les termers du produit cartérise sons non-vides alors le produits cartésien est non-vide.
-\begin{equation}
+Cette axiome nous assure qui si tous les termes du produit cartésien sons non-vides alors le produit cartésien est non-vide.
+\begin{equation*}
\forall a\in A f(a)\neq\emptyset \implies
\bigtimes_{a\in A}f(a) \neq\emptyset
-\end{equation}
+\end{equation*}
\paragraph{Axiome de l'infini}
-\begin{equation}
+\begin{equation*}
\exists A\forall a\in A~(\emptyset \in A \wedge a^+\in A)
-\end{equation}
+\end{equation*}
Où $a^+ = a\cup \{a\}$.
Nous appelons un tel $A$, un ensemble récursif.
@@ -158,54 +155,53 @@ Nous appelons un tel $A$, un ensemble récursif.
Soit $C$ la classe des ensembles récursif.
Soit $A$ un ensemble récursif.
Nous appelons $\mathbb{N}$ l'ensemble des entier naturels que nous définissons comme suit :
-\begin{equation}
+\begin{equation*}
\mathbb{N} = \{n\in A~|~\forall c\in C~n\in c\}
-\end{equation}
-$\mathbb{N}$ est bien en ensemble d'après l'axiome Aussonderung.
- Cette construction permet de définir les opérations d'addition ($+$) et de multiplication ($\cdot$)~\cite{enderton1977elements}.
+\end{equation*}
+$\mathbb{N}$ est bien en ensemble d'après l'axiome de séparation.
\textbf{Entiers relatifs.}
La relation
-\begin{equation}
+\begin{equation*}
R =
\left\{
((a,b),(c,d))\in{\mathbb{N}^2}^2~|~
a+d = b+c
\right\}
-\end{equation}
-est une relation d'équivalance sur $\mathbb{N}^2$.
+\end{equation*}
+est une relation d'équivalence sur $\mathbb{N}^2$.
Nous définissons alors l'ensemble des \emph{entiers relatifs} $\mathbb{Z}=\mathbb{N}^2/R$.
-\textbf{Nombres rationels.}
+\textbf{Nombres rationnels.}
La relation
-\begin{equation}
+\begin{equation*}
S =
\left\{
((a,b),(c,d))\in{\left(\mathbb{Z}\times\mathbb{Z}^*\right)}^2~|~
a\cdot d = b\cdot c
\right\}
-\end{equation}
- est une relation d'équivalance sur $\mathbb{Z}\times\mathbb{Z}^*$.
- Nous définissons alors l'ensemble des \emph{Nombres rationels} $\mathbb{Q}=\left(\mathbb{Z}\times\mathbb{Z}^*\right)/S$.
+\end{equation*}
+ est une relation d'équivalence sur $\mathbb{Z}\times\mathbb{Z}^*$.
+ Nous définissons alors l'ensemble des \emph{Nombres rationnels} $\mathbb{Q}=\left(\mathbb{Z}\times\mathbb{Z}^*\right)/S$.
\textbf{Nombres réels}
\begin{definition}[Suite de Cauchy]
Une \emph{suite} $u$ sur un ensemble de $A$ est une fonction de $\mathbb{N}$ dans $A$. On note $u(n) = u_n$ pour tout $n\in\mathbb{N}$.
- Une \emph{suite de Cauchy} $u$ sur $\mathbb{Q}$ est elle que
- \begin{equation}
+ Une \emph{suite de Cauchy} $u$ sur $\mathbb{Q}$ est telle que
+ \begin{equation*}
\forall \varepsilon\in\mathbb{Q}~
\exists N\in\mathbb{N}~
\forall (a,b) \in \mathbb{N}^2~
a\geq N\wedge b\geq N \implies
|u_a-u_b|\leq\varepsilon
- \end{equation}
+ \end{equation*}
Soit $C$ l'ensemble des suite de Cauchy sur $\mathbb{Q}$.
\end{definition}
La relation
-\begin{equation}
+\begin{equation*}
T =
\left\{
(u,v)\in C^2~|~
@@ -215,48 +211,48 @@ La relation
a\geq N\wedge b\geq N \implies
|u_a-v_b|\leq\varepsilon
\right\}
-\end{equation}
- est une relation d'équivalance sur $C^2$.
+\end{equation*}
+ est une relation d'équivalence sur $C^2$.
Nous définissons alors l'ensemble des \emph{Nombres réels} $\mathbb{R}=C/T$.
\end{definition}
-\paragraph{Axiome de régularitée}
+\paragraph{Axiome de régularité}
Tout ensemble non-vide a un élément disjoint de cet ensemble.
\paragraph{Axiome de remplacement}
-Soit $F(a,b)$ un formule qui ne dépend pas de $B$.
-\begin{equation}
+Soit $F(a,b)$ une formule qui ne dépend pas de $B$.
+\begin{equation*}
\forall A\forall y\forall z
\left(
- \forall (x\in A~F(x,y)\wedge F(x,z)\implies x=z)\implies
+ \forall (x\in A~F(x,y)\wedge F(x,z)\implies y=z)\implies
(\exists B~B=\{y~|~\exists x\in A~F(x,y)\})
\right)
-\end{equation}
+\end{equation*}
\subsubsection{Arithmétique}
\label{sec:background-set-ari}
Avec un niveau d'abstraction supplémentaire, nous considérons désormais que $\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R}$.
-Cela est possible grace aux injéctions canoniques suivantes :
-\begin{equation}
+Cela est possible grâce aux injections canoniques suivantes :
+\begin{equation*}
\left\{
\begin{matrix}
\mathbb{N}\rightarrow\mathbb{Z}\\
n\mapsto (n,0)
\end{matrix}
\right.
-\end{equation}
+\end{equation*}
-\begin{equation}
+\begin{equation*}
\left\{
\begin{matrix}
\mathbb{Z}\rightarrow\mathbb{Q}\\
(a,b)\mapsto ((a,b),(1,1))
\end{matrix}
\right.
-\end{equation}
+\end{equation*}
-\begin{equation}
+\begin{equation*}
\left\{
\begin{matrix}
\mathbb{Q}\rightarrow\mathbb{R}\\
@@ -271,36 +267,51 @@ Cela est possible grace aux injéctions canoniques suivantes :
\right]_T
\end{matrix}
\right.
-\end{equation}
+\end{equation*}
-Nous identifions aussi $\mathbb{R}$ aux réprésentation en base 10 de ses éléments.
+Nous identifions aussi $\mathbb{R}$ aux représentations en base 10 de ses éléments.
Et nous utiliserons les opérations usuelles $+$, $\cdot$, $-$ et $/$ ainsi que la relation d'ordre $<$ sur ces représentation.
En générale il est possible de construire ces opérations sans utiliser la représentation en base 10~\cite{enderton1977elements} mais une telle construction est hors de propos pour ce manuscrit.
-Outre les opératiosn usuelles, nous allons avoir aussi besoin de quelques fonction particulière :
+Outre les opérations usuelles, nous allons avoir aussi besoin de quelques fonction particulière :
\begin{itemize}
+ \item L'indicatrice de $A\subset E$ est
+ \begin{equation*}
+ 1_A:\left\{
+ \begin{matrix}
+ E\rightarrow\{0,1\}\\
+ x\mapsto\left\{
+ \begin{matrix}
+ 1~\text{si}~x\in A\\
+ 0~\text{sinon}
+ \end{matrix}
+ \right.
+ \end{matrix}
+ \right.
+ \end{equation*}
\item La factorielle : pour $n\in\mathbb{N}~n!=n(n-1)\cdots1$.
\item La division euclidienne : pour
$(a,b)\in\mathbb{N}\times\mathbb{N}^*~\exists (q,r)\in\left(\mathbb{N}^*\right)^2~
a=qb+r\wedge b(q+1)>a$.
- $q$ est appellé quotient et $r$ reste de la division de $a$ par $b$.
+ $q$ est appelé quotient et $r$ reste de la division de $a$ par $b$.
\end{itemize}
\subsubsection{Intervalle}
\label{sec:background-math-int}
-Pour $(a,b)\in\mathbb{R}^2$ avec $a\leq b$ nous définissone l'intervalle $[a,b]$ de la manière suivant : $\{x\in\mathbb{R}\mid a\leq x\wedge x\leq b\}$.
+Pour $(a,b)\in\mathbb{R}^2$ avec $a\leq b$ nous définissons l'intervalle $[a,b]$ de la manière suivant : $\{x\in\mathbb{R}\mid a\leq x\wedge x\leq b\}$.
Et aussi sa contrepartie entière : $[|a,b|] = [a,b]\cap\mathbb{N}$.
\subsubsection{Cardinal}
\label{sec:background-math-card}
La notion de cardinal cherche à comparer la taille d'ensembles arbitraires.
-Nous n'allons pas ici considérer la théorie de ordinaux de Van Neumann qui compléte notre simplification.
+Nous n'allons pas ici considérer la théorie de ordinaux de Van Neumann qui complète notre simplification.
Le lecteur souhaitant aller plus loin et apprendre cette théorie peut se référer aux chapitres 6,7,8 et 9 de \textit{Elements of set thoery} de Herbert B. Enderton~\cite{enderton1977elements}.
-Notre simplification est ce suffit à elle même pour les dévelopement qui nous allons présenter dans ce manuscrit.
+Notre simplification se suffit à elle même pour les développements qui nous allons présenter dans ce manuscrit.
-Nous dirons donc que tout ensemble $A$ à un cardinal que nous noterons $\#A$.
+Nous dirons donc que tout ensemble $A$ a un cardinal que nous noterons $\#A$.
Si $A$ est en bijection avec $n\in\mathbb{N}$ alors $\#A = n$.
Nous dirons alors que $A$ est un ensemble fini.
-Dans le cas contraite nous dirons que $A$ est infini.
-Si $A$ est en bijection avec un sous ensemble de $\mathbb{N}$ nous dirons que $A$ est dénombrable et que sons cardinal est $\#A = \aleph_0$.
+Dans le cas contraire nous dirons que $A$ est infini.
+Si $A$ est en bijection avec un sous ensemble de $\mathbb{N}$ nous dirons que $A$ est dénombrable.
+Si $A$ est en bijection avec $\mathbb{N}$ nous notons $\#A = \aleph_0$.
Enfin nous dirons que deux ensemble arbitraires ont le même cardinal si et seulement si ils sont en bijection.