From 57715cacec8d0f0d3d1436a26f92ae5c0f0e128e Mon Sep 17 00:00:00 2001 From: Jan Aalmoes Date: Tue, 27 Aug 2024 21:07:18 +0200 Subject: debut du background sur ZF --- background/conf.tex | 101 +++++++++++++++++++++++++++++++++++++++++++++++++++ background/eq.tex | 42 +++++++++++++++++++++ background/main.tex | 78 +++++++++++++++++++++++++++++++++++++++ background/proba.tex | 42 +++++++++++++++++++++ background/set.tex | 77 +++++++++++++++++++++++++++++++++++++++ 5 files changed, 340 insertions(+) create mode 100644 background/conf.tex create mode 100644 background/eq.tex create mode 100644 background/main.tex create mode 100644 background/proba.tex create mode 100644 background/set.tex (limited to 'background') diff --git a/background/conf.tex b/background/conf.tex new file mode 100644 index 0000000..4ee8d9f --- /dev/null +++ b/background/conf.tex @@ -0,0 +1,101 @@ + +%Attacks which violate privacy and confidentiality in ML infer potentially sensitive unobservable information from observable information (e.g., model predictions). +\label{sec:bck_aia} + +Attacks which violate privacy and confidentiality in ML infer potentially sensitive information from observable information (e.g., model predictions). +This leakage of information is a privacy risk if adv learns something about $traindata$ -or the inputs- which would be impossible to learn without access to $targetmodel$. This differentiates between a privacy risk and simple statistical inference~\cite{cormode}. +Among the various privacy risks explored in literature pertaining to ML models, attribute inference attacks~\cite{fredrikson2,Mahajan2020DoesLS,yeom,Song2020Overlearning,malekzadeh2021honestbutcurious,MehnazAttInf} infer the specific value of a sensitive attribute for a specific input to ML model given some model observables (e.g., model predictions, parameters, intermediate layerwise outputs) and background information. Based on attack surface being exploited, aia{s} can be categorized into (a) imputation-based attacks and (b) representation-based attacks. + +Let's introduce some notations to guide us in understanding the zoology of those attacks. + +We have a dataset $d:I\rightarrow \mathcal{X}\times\mathcal{S}\times\mathcal{Y}$ containing as column: the features, the sensitive attribute and the ground truth. +$I$ is a finite set of indices. +To access features, sensitive attribute and labels from there indices, we define respectively the following functions: +\begin{itemize} + \item $X:I\rightarrow \mathcal{X},~i\mapsto (d(i))_0$ + \item $S:I\rightarrow \mathcal{S},~i\mapsto (d(i))_1$ + \item $Y:I\rightarrow \mathcal{Y},~i\mapsto (d(i))_2$ +\end{itemize} +Let $(I_0,I_1)$ be a partition of $I$. +$d$ is split in two datasets $d_0 = d_{{|I_0}}$ and $d_1 = d_{{|I_1}}$ which we call respectively the target dataset and the auxiliary dataset. +$d_0$ is used to train a machine learning model to infer the ground truth from the features: we call it the target model $targetmodel$. + +Regarding attribute inference attack, we differentiate between training time attacks that target $d_0$: the dataset used in training. +And inference time attack that target data used as input of an already trained target model. +Our work focuses on the later (see figure \ref{fig:tm2}) but for clear positioning of our contributions, we are going to present both types of attack in this background section. + +\noindent\textbf{\underline{Imputation-based attacks}} assume adv has access to non-sensitive attributes in addition to model's predictions and background information (e.g., marginal prior over sensitive attribute and confusion matrix). We review these different imputation-based attacks below: + + + +\setlength\tabcolsep{3pt} +\begin{table*}[!htb] +\caption{Comparison of prior work based on: attack surface exploited (e.g., model predictions ($targetmodel(X(i))$), $X(i)$, $Y(i)$, distribution over $S(i)$ ($P_S$) and confusion matrix between true and predicted output across all training data records ($C(Y(i),targetmodel(X(i)))$), whether $S(i)$ is censored, i.e., included in $traindata$ or inputs, whether they account for class imbalance in $S(i)$, whether adv is active or passive and whether the threat model is blackbox or whitebox. All the attacks assume the knowledge of auxiliary data $auxdata$.} +\begin{center} +\footnotesize +\begin{tabular}{ |c|c|c|c|c|c| } + \hline + \textbf{Literature} & \textbf{Attack Vector} & \textbf{$S$ is censored?} & \textbf{Imbalance in $S$?} & \textbf{adv} & \textbf{Threat Model} \\ + \hline + \multicolumn{6}{|c|}{\textbf{Imputation-based Attacks}}\\ + \hline + \textbf{Fredrikson et al.}~\cite{fredrikson2} & $X$, $Y$, $targetmodel(X(i))$, \textbf{$P_S$}, $C(Y(i),targetmodel(X(i)))$ & $\checkmark$ & $\times$ & Passive & Blackbox\\ + \textbf{Yeom et al.}~\cite{yeom} & $X(i)$, $Y(i)$, $targetmodel()$, \textbf{$P_S$} & $\checkmark$ & $\times$ & Passive & Blackbox\\ + \textbf{Mehnaz et al.}~\cite{MehnazAttInf} & $X(i)$, $Y(i)$, $targetmodel()$, \textbf{$P_S$}, $C(Y(i),targetmodel(X(i)))$ & $\checkmark$ & $\times$ & Passive & Blackbox\\ + \textbf{Jayaraman and Evans}~\cite{jayaraman2022attribute} & $X(i)$, $Y(i)$, $targetmodel()$, \textbf{$P_S$}, $C(Y(i),targetmodel(X(i)))$ & $\times$, $\checkmark$ & $\times$ & Passive & Whitebox\\ + \hline + \multicolumn{6}{|c|}{\textbf{Representation-based Attacks}}\\ + \hline + \textbf{Song et al.}~\cite{Song2020Overlearning} & $targetmodel(X(i))$ & $\times$ & $\times$ & Passive & Both\\ + \textbf{Mahajan et al.}~\cite{Mahajan2020DoesLS} & $targetmodel(X(i))$ & $\checkmark$ & $\times$ & Passive & Blackbox\\ + \textbf{Malekzadeh et al.}~\cite{malekzadeh2021honestbutcurious} & $targetmodel(X(i))$ & $\times$ & $\times$ & Active & Blackbox\\ + \textbf{Our Work} & $targetmodel(X(i))$ & $\times$, $\checkmark$ & $\checkmark$ & Passive & Blackbox \\ + \hline +\end{tabular} +\end{center} +\label{tab:summary} +\end{table*} + +\label{sec:bck_aia} + +\begin{itemize} + \item \textbf{Fredrikson et al.~\cite{fredrikson2}} assumes that adv has access to $targetmodel(X(i))$. + For this attack it is required that $X$ can be written $X(i) = (\cdots,S(i),\cdots)$. + We will refer to this case as "\textit{S is in the input}". + Fredrikson et al. attack generates an input with different possible values of the sensitive attribute + It then chooses the most likely value based on $targetmodel(X(i))$. + + \item \noindent\textbf{Yeom et al.~\cite{yeom}} assumes a distribution $P_S$ over $S$ which is used to estimate the value of $S$ for an arbitrary data record. They propose three different variants of AS based on assumptions on $P_S$: Attack 1 leverages membership oracle to determine the value of $S(i)$ and Attack 2 and 3 assume different types of distributions over $S$. + For this attack to work, $S$ is in the input and the data points being attacked belong to the target dataset + + \item \textbf{Mehnaz et al.~\cite{MehnazAttInf}} improves upon Fredrikson et al.~\cite{fredrikson1,fredrikson2} by exploiting $targetmodel\circ X$ and $X$, with $S$ in the input. The attack relies on the intuition that $targetmodel$'s output confidence is higher when the input has the correct value of $S$ as $targetmodel$ encountered the target record with that attribute during training. Their attack involves generating multiple instances of input with different values of $S(i)$ (similar to Fredrikson et al.~\cite{fredrikson1,fredrikson2}) and identifying the most likely value of $S$. +\end{itemize} + +An appropriate baseline to identify whether such attacks are indeed a privacy risk is to use data imputation, i.e., train an ML model to infer value of missing attribute from other non-sensitive attributes without $targetmodel(X(i))$~\cite{jayaraman2022attribute}. Jayaraman and Evans~\cite{jayaraman2022attribute} find that existing blackbox imputation-based attacks~\cite{yeom,fredrikson2,MehnazAttInf} do not perform any better than data imputation. In other words, the perceived privacy risk is actually stemming from statistical inference and hence not an actual privacy risk. + +To address this, Jayaraman and Evans~\cite{jayaraman2022attribute} propose a whitebox aia which outperforms prior blackbox attacks as well as data imputation in the setting where there is limited knowledge of data for adv. However, since the attack is in a whitebox setting, we omit a detailed description of the attack. All these attacks require that: + +\begin{itemize} + \item $S$ is in the input data records which is not always the case in realistic settings, + \item $X(i)$ being attacked belong to the target dataset. +\end{itemize} + +\noindent\textbf{\underline{Representation-based attacks}} exploit the distinguishable intermediate layer outputs or predictions for different values of sensitive attributes~\cite{Song2020Overlearning,Mahajan2020DoesLS,malekzadeh2021honestbutcurious}. For instance, the distribution of $targetmodel\circ X$ for \textit{males} is different from the output prediction distribution for \textit{females}. We describe the existing attacks of this category below: + +\begin{itemize} +\item \textbf{Song et al.~\cite{Song2020Overlearning} / Mahajan et al.~\cite{Mahajan2020DoesLS}} assume that $S$ is not in the input. adv only observes $targetmodel\circ X$. adv trains an ML attack model $ackmodel$ to map the output predictions $targetmodel(X(i))$ to $S(i)$. +In other words, the statistic $\hat{S}$ used to infer $S$ is of the form: $ \hat{S} = 1_{[0.5,1]}\circ ackmodel\circ targetmodel\circ X$, where $attackmodel: [0,1]\rightarrow[0,1]$. + + +\item \textbf{Malekzadeh et al.~\cite{malekzadeh2021honestbutcurious}} considers the setting where adv trains $targetmodel$ with a special loss function to explicitly encode information about $S(i)$ in $targetmodel(X(i))$. +It makes it easier to extract the sensitive attribute during inference. In this setting, the model builder is malicious and actively introduces a ``backdoor''. +\end{itemize} + +Our work focuses on representation-based aia in a blackbox setting at inference time. We focus on Song et al.~\cite{Song2020Overlearning} and Mahajan et al.~\cite{Mahajan2020DoesLS} as our baselines. +These attacks do not account for class imbalance in sensitive attribute commonly present in data from real-world applications which could effect adv's attack success~\cite{classIMb1,classIMb2}. +In our evaluation, we consider an aia using an adaptive threshold which outperforms these baselines attacks (Section~\ref{sec:evalAIA}). +Malekzadeh et al.~\cite{malekzadeh2021honestbutcurious} has a different threat model where adv explicitly modifies the training to enhance the leakage of $S$. +We do not assume such access to $targetmodel$ in a blackbox setting. +In addition, these attacks did not take into consideration the possibility to infer the sensitive attribute solely from the hard labels. +We summarize relevant prior work in Table~\ref{tab:summary}. + diff --git a/background/eq.tex b/background/eq.tex new file mode 100644 index 0000000..8a76ee7 --- /dev/null +++ b/background/eq.tex @@ -0,0 +1,42 @@ + +\label{sec:bck_fair} +Algorithmic fairness aims at reducing biases in ML model predictions. +Indeed, data records belonging to certain subgroups influence $targetmodel$'s predictions more than others. +For instance in criminal justice, the ethnicity of a culprit plays a non-negligible role in the prediction of them reoffending~\cite{fairjustice}. Generally, data records in the minority subgroup face unfair prediction behaviour compared to data records in the majority subgroup. These subgroups are identified based on a sensitive attribute (e.g., race or sex). +Those biases are learnt by $targetmodel$ as they are part of the distribution of the training dataset. +There is two main categories of fairness of a ML model: + +\textbf{Individual fairness} ensures that two data records with same attributes except for $S$ have the same model prediction. +This notion does not dwell on sensitive attribute and as such is not really useful in our goal of mitigating attribute inference attack at inference time. +So we set it aside for the rest of the paper. + +\textbf{Group fairness} comes from the idea that different subgroups defined by an attribute such a skin color or gender should be treated equally. +We focus our study on group fairness where $S$ represents either sex or race (i.e., $S(i)$ equals to 0 for woman, 1 for man, and 0 for black, 1 for white, respectively). +There are different definitions of group fairness which have been introduced in prior work. +We discuss two well-established and commonly used metrics: demographic parity and equality of odds. + +\begin{definition} +\label{def:dp} + $\hat{Y}$ satisfies demparity for $S$ if and only if: $P(\hat{Y}=0 | S=0) = P(\hat{Y}=0 | S=1)$. + From that, we will call $|P(\hat{Y}=0 | S=0) - P(\hat{Y}=0 | S=1)|$ the demPar-level of $\hat{Y}$. +\end{definition} + +demparity is the historical definition of fairness. +Legally, disparate impact is the fairness definition recognized by law, where 80\% disparity is an agreed upon tolerance decided in the legal arena. +demparity ensures that the number of correct prediction is the same for each population. +However, this may result in different false positive and true positive rates if the true outcome does actually vary with $S$~\cite{dpbad}. +Hardt et al.~\cite{fairmetric2} proposed eo as a modification of demparity to ensure that both the true positive rate and false positive rate will be the same for each population. + +\begin{definition} + \label{def:eo} + $\hat{Y}$, classifier of $Y$, satisfies equality of odds for $S$ if and only if: $\forall (\hat{y},y)\in\{0,1\}^2 \quad + P(\hat{Y}=\hat{y} | S=0,Y=y) = P(\hat{Y}=\hat{y} | S=1,Y=y)$. +\end{definition} + +The above fairness definitions can be achieved using three main fairness mechanisms: (a) pre-processing, (b) in-processing and (c) post-processing. \textit{Pre-processing} algorithms such as reweighing requires access to the training data and assigns weights to the data records to remove discrimination~\cite{preprocessing}. +\textit{In-processing} algorithms such as advdebias~\cite{debiase} and egd~\cite{reductions} add constraint during $targetmodel$'s training to ensure fairness. %reductions +\textit{Post-processing} techniques, in turn, hide the bias in output predictions to satisfy the above fairness constraints but the underlying model is still biased. +Similar to previous work~\cite{chang2021privacy}, we focus on in-processing algorithms. + +Our work focuses on the theoretical guaranties on attribute inference attacks given by the different fairness notions and not so much on how to implement in-processing fairness mechanism. +Nevertheless in the experiment section we try production ready state of the art implementations of those fairness constraints along unconstrained ML algorithm. diff --git a/background/main.tex b/background/main.tex new file mode 100644 index 0000000..93ee12b --- /dev/null +++ b/background/main.tex @@ -0,0 +1,78 @@ +Nous présentons dans ce chapitre les différentes théories et concepts sur les quelles se basent nos développements. +\section{Mathématiques} +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. +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 : +\begin{equation} +\begin{matrix} +a & b & a\iff b & a\implies b & a\wedge b & a\vee b & \neg a\\ +0 & 0 & 1 & 1 & 0 & 0 & 1\\ +0 & 1 & 0 & 1 & 0 & 1 & 1\\ +1 & 0 & 0 & 0 & 0 & 1 & 0\\ +1 & 1 & 1 & 1 & 1 & 1 & 0\\ +\end{matrix} +\end{equation} +\subsection{Ensembles et fonctions} + \input{background/set} + +\subsection{Algèbre linéaire} + \subsubsection{Espace vectoriel} + \subsubsection{Application linéaires} + \subsubsection{Matrices} + +\subsection{Mesurer le hasard pour prédire et inférer} + \label{sec:background-proba} + \input{background/proba} + %\subsection{Théorie de la mesure} + %\subsection{Probabilitées} + %\subsection{Statistiques} + +\subsection{Topologie} + \subsubsection{Distances et normes} + \subsubsection{Espaces topologiques} + \subsubsection{Application aux fonctions} + +\subsection{Calcul différentiel} + \subsubsection{Différentiel} + \subsubsection{Gradient} + +\subsection{Optimisation} + \label{sec:background-opti} + \subsubsection{Multiplicateurs de Lagrange} + + \subsubsection{Descente de gradient} + \paragraph{Descente de gradient stochastique} + + \paragraph{Descente de gradient exponentiée} + +\section{Apprentissage automatique} + \label{sec:background-ml} + \subsection{Principe} + \subsection{Entraîner un modèle} + \subsubsection{Fonction de coût} + \subsection{Evaluer un modèle} + \subsubsection{Classification} + \paragraph{La courbe ROC} + \paragraph{La courbe de precision/recall} + \subsubsection{Regression} + \subsection{Décentralisation} + \subsubsection{Federated learning} + \subsection{Modèles génératifs} + \label{sec:background-generation} + +\section{Equité} + \label{sec:background-eq} + \input{background/eq} + %\subsection{Différentes notions d'équité} + +\section{Confidentialité} + \label{sec:background-conf} + \input{background/conf} + %\subsection{Mitiger l'inéquitée} + %\subsubsection{Preprocessing} + % \subsubsection{Inprocessing} + %\subsubsection{Postprocessing} diff --git a/background/proba.tex b/background/proba.tex new file mode 100644 index 0000000..bea43e7 --- /dev/null +++ b/background/proba.tex @@ -0,0 +1,42 @@ + +Probability theory is deeply linked with machine learning and most of the properties of machine learning, such as differential privacy, fairness definitions, utility metrics... are often mathematically written within this framework. +This paper does not differ and hence we provide a short background of this field and how it connects with the previously defined notions of ML introduced in section \ref{sec:ml}. + +Soit $A$ un ensemble. +L'ensemble des parties de $A$ est $\mathcal{P}(A)$. +Chaque élément $a \in \mathcal{P}(A)$ est tel que $a \subset A$. +Une tribue $\mathcal{A}$ est un sous esemble de $\mathcal{P}(A)$ qui contien $\emptyset$, $A$ par complémentaire est union dénombrable. +Nous disons que $(A,\mathcal{A})$ est un espace mesurable. +Une mesure $d$ est 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 chaque $(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é. +Nous appelons fonction mesurable un 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})$ + +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 de probabilite suivante : +$d_X :\mathcal{X}\rightarrow [0,1]$, $x\mapsto d(X^{-1}(x))$. + +Having introduced probability theory, we explicit the relation with the ML theory described previously. +Let $I$ a finite set, $\mathcal{X}$, $\mathcal{S}$ and $\mathcal{Y}$ the sets of features, sensitive attribute and label. +Let $d:I\rightarrow \mathcal{X}\times\mathcal{S}\times\mathcal{Y}$ a dataset. +Let $\#$ be the measure on $(I,\mathcal{P}(I))$ which maps to every $a$ in $\mathcal{P}(I)$ the number of elements of $a$. +Let $P:\mathcal{P}(I)\rightarrow [0,1]$, $a\mapsto \frac{\#(a)}{\#(I)}$. +Then $(I, \mathcal{P}(I), P)$ is a probability space. +On this space we can define the following random variables: +\begin{itemize} + \item $X:I\rightarrow \mathcal{X},~i\mapsto (d(i))_0$ + \item $S:I\rightarrow \mathcal{S},~i\mapsto (d(i))_1$ + \item $Y:I\rightarrow \mathcal{Y},~i\mapsto (d(i))_2$ +\end{itemize} +Where for a vector $u$, $u_j$ refers to the $j$th element of $u$. + +From there we can define various random variables that will be useful in the rest of the paper. +For instance $\hat{Y}=f\circ X$ is random variable that represents the prediction of a trained machine learning model $f$. +We can use it to write the accuracy in a compact way: $P(\hat{Y}=Y)$ by using the well accepted abuse of notations that for a random variable $A$ and an event $a$, +$\{A\in a\} = \{i\in\mathcal{P}(I)~|~A(i)\in a\} = A^{-1}(a)$. +The accuracy is a reliable metric of a trained model's utility when $P(Y=0) = P(Y=1) = \frac{1}{2}$ but not so much when there is unbalance in $Y$. +To take into account an eventual unbalanced distribution of the labels, we will consider the balanced accuracy : +$\frac{P(\hat{Y}=0|Y=0) + P(\hat{Y}=1|Y=1)}{2}$. + +Finally in the context of attribute inference attack at inference time, we define the random variable $\hat{S}=a\circ \hat{Y}$ where here $a$ is a machine learning model trained to infer sensitive attribute from model's output. diff --git a/background/set.tex b/background/set.tex new file mode 100644 index 0000000..c058648 --- /dev/null +++ b/background/set.tex @@ -0,0 +1,77 @@ +Commencons donc cette section préliminaire avec les définitions et quelques porpiété des ensemble et de fonctions. +Commencons 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}. + +\subsubsection{Axiomes de la théroie 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. + +\paragraph{Axiome d'Extensionnalité} +Deux ensemble $A$ et $B$ sont égaut 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} + +\paragraph{Axiome de l'Ensemble vide} +Il exite un ensemble qui ne contient aucun élément. +Nous le notons donc $\{\}$ ou $\emptyset$. + +\paragraph{Axiome de la Paire} +\begin{equation} +\forall A \forall B \exists \{A,B\}\forall c(c\in \{A,B\}\iff c=A\vee c=B) +\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} +\forall A \exists \bigcup A \forall b \left(b\in\bigcup A\iff \exists a\in A~ b\in a\right) +\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} +\forall A \exists \mathcal{P}(A) ~ P\subset A \iff P\in \mathcal{P}(A) +\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 +$\forall b\in B (b\in A \wedge F)$ + +\paragraph{Axiome du choix} +\begin{definition}[Fonction] +qsdf +\end{definition} + +\paragraph{Axiome de l'infini} +\begin{equation} +\exists A\forall a\in A~(\emptyset \in A \wedge a^+\in A) +\end{equation} +Où $a^+ = a\cup \{a\}$. +Nous appelons un tel $A$, un ensemble récursif. + +\begin{definition}[Ensemble usuels] +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} +\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~\cite{enderton1977elements} ainsi que les autres ensembles usuels qui nous utiliserons dans ce manuscrit. +Ainsi nous définisson $\mathbb{Z} = \{$ : l'ensemble des entiers relatifs l'union de $\mathbb{N}$ et de $-\mathbb{N} = \{$ + +\end{definition} + +\paragraph{Axiome de remplacement} + +\paragraph{Axiome de régularitée} + + + + + -- cgit v1.2.3 From dc5a898dc39326fa3f733f3d9e006bbe3d1f8e4c Mon Sep 17 00:00:00 2001 From: Jan Aalmoes Date: Thu, 29 Aug 2024 10:58:32 +0200 Subject: Fin ensemble et fonctions, debut ML et Mesure/Proba --- background/main.tex | 14 +--- background/ml.tex | 20 ++++++ background/proba.tex | 18 ++++-- background/set.tex | 176 +++++++++++++++++++++++++++++++++++++++++++++++++-- 4 files changed, 202 insertions(+), 26 deletions(-) create mode 100644 background/ml.tex (limited to 'background') diff --git a/background/main.tex b/background/main.tex index 93ee12b..9a9f287 100644 --- a/background/main.tex +++ b/background/main.tex @@ -17,6 +17,7 @@ a & b & a\iff b & a\implies b & a\wedge b & a\vee b & \neg a\\ \end{matrix} \end{equation} \subsection{Ensembles et fonctions} +\label{sec:background-set} \input{background/set} \subsection{Algèbre linéaire} @@ -51,18 +52,7 @@ a & b & a\iff b & a\implies b & a\wedge b & a\vee b & \neg a\\ \section{Apprentissage automatique} \label{sec:background-ml} - \subsection{Principe} - \subsection{Entraîner un modèle} - \subsubsection{Fonction de coût} - \subsection{Evaluer un modèle} - \subsubsection{Classification} - \paragraph{La courbe ROC} - \paragraph{La courbe de precision/recall} - \subsubsection{Regression} - \subsection{Décentralisation} - \subsubsection{Federated learning} - \subsection{Modèles génératifs} - \label{sec:background-generation} + \input{background/ml} \section{Equité} \label{sec:background-eq} diff --git a/background/ml.tex b/background/ml.tex new file mode 100644 index 0000000..2482b40 --- /dev/null +++ b/background/ml.tex @@ -0,0 +1,20 @@ +\subsection{Principe} +\subsection{Entraîner un modèle} + \subsubsection{Fonction de coût} +\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. + \subsubsection{Classification} + 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{} ainsi il existe beaucoup d'outil qui permette d'evaluer ce genre de classifieur. + \paragraph{La courbe ROC} + \paragraph{La courbe de precision/recall} + \subsubsection{Regression} +\subsection{Décentralisation} + \subsubsection{Federated learning} +\subsection{Modèles génératifs} +\label{sec:background-generation} diff --git a/background/proba.tex b/background/proba.tex index bea43e7..6050ef7 100644 --- a/background/proba.tex +++ b/background/proba.tex @@ -1,15 +1,19 @@ -Probability theory is deeply linked with machine learning and most of the properties of machine learning, such as differential privacy, fairness definitions, utility metrics... are often mathematically written within this framework. -This paper does not differ and hence we provide a short background of this field and how it connects with the previously defined notions of ML introduced in section \ref{sec:ml}. +La théorie des probability est profondément liée au machine learning. +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. +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 nous 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 cour de Jean-François Le Gall de l'Ecole Normale Supérieur de Paris~\cite{proba}. Soit $A$ un ensemble. -L'ensemble des parties de $A$ est $\mathcal{P}(A)$. -Chaque élément $a \in \mathcal{P}(A)$ est tel que $a \subset A$. -Une tribue $\mathcal{A}$ est un sous esemble de $\mathcal{P}(A)$ qui contien $\emptyset$, $A$ par complémentaire est union dénombrable. +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'un nombre dénombrable d'elements de $\mathcal{A}$. Nous disons que $(A,\mathcal{A})$ est un espace mesurable. -Une mesure $d$ est 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 chaque $(A_1, A_2, \cdots) \in \mathcal{A}^\mathbb{N} $ avec $\forall (i,j) A_i\cap A_j = \emptyset$. + +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é. -Nous appelons fonction mesurable un fonction de $A$ à $B$ telle que $\forall b\in\mathcal{B}$~$f^{-1}(b)\in\mathcal{A}$. + +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})$ Dans le cas particulier où $d(A) = 1$, nous appelons $d$ une mesure de probabilité. diff --git a/background/set.tex b/background/set.tex index c058648..2e660f6 100644 --- a/background/set.tex +++ b/background/set.tex @@ -42,11 +42,58 @@ Pour tout ensemble $A$ il existe un ensemble $\mathcal{P}(A)$ qui est l'ensemble 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 $\forall b\in B (b\in A \wedge F)$ -\paragraph{Axiome du choix} -\begin{definition}[Fonction] -qsdf +\begin{definition}[Fonctions] + + \textbf{2-uplet.} + Nous définissons pour tout ensemble $A$ et $B$ le \emph{2-uplet} $(A,B)$ par $\{\{A\},\{A,B\}\}$. + + \textbf{Relation.} + Nous appelons \emph{relation} un ensemble de 2-uplets. + L'\emph{ensemble de définision} 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 + 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$. + + \textbf{Fonction.} + Une \emph{fonction} $f$ est un relation telle que + \begin{equation} + \forall x\in D_f\left((x,y)\in f\wedge (x,z)\in f\implies y=z\right) + \end{equation} + Pour tout ensemble $E$ et $F$ tels que $D_f\subset E$ et $Img(f)\subset F$ nous notons + \begin{equation} + f: + \left\{ + \begin{matrix} + E\rightarrow F\\ + x\mapsto f(x) + \end{matrix} + \right. + \end{equation} + Où la notation $x\mapsto f(x)$ signifie que $(x,f(x))\in f$. + + \textbf{Produit cartésien.} + Soit $A$ un ensemble $f$ une fonctions + \begin{equation} + \bigtimes_{a\in A}f(a) = + \left\{ + g~|~D_g=A\wedge (\forall a\in A~g(i)\in f(i)) + \right\} + \end{equation} + \end{definition} +\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} + \forall a\in A f(a)\neq\emptyset \implies + \bigtimes_{a\in A}f(a) \neq\emptyset +\end{equation} + \paragraph{Axiome de l'infini} \begin{equation} \exists A\forall a\in A~(\emptyset \in A \wedge a^+\in A) @@ -55,6 +102,8 @@ Où $a^+ = a\cup \{a\}$. Nous appelons un tel $A$, un ensemble récursif. \begin{definition}[Ensemble usuels] + + \textbf{Entiers.} 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 : @@ -62,16 +111,129 @@ Nous appelons $\mathbb{N}$ l'ensemble des entier naturels que nous définissons \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~\cite{enderton1977elements} ainsi que les autres ensembles usuels qui nous utiliserons dans ce manuscrit. -Ainsi nous définisson $\mathbb{Z} = \{$ : l'ensemble des entiers relatifs l'union de $\mathbb{N}$ et de $-\mathbb{N} = \{$ + Cette construction permet de définir les opérations d'addition ($+$) et de multiplication ($\cdot$)~\cite{enderton1977elements}. -\end{definition} +\textbf{Entiers relatifs.} +La relation +\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$. + Nous définissons alors l'ensemble des \emph{entiers relatifs} $\mathbb{Z}=\mathbb{N}^2/R$. -\paragraph{Axiome de remplacement} +\textbf{Nombres rationels.} +La relation +\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$. + +\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} + \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} + + Soit $C$ l'ensemble des suite de Cauchy sur $\mathbb{Q}$. + \end{definition} + +La relation +\begin{equation} + T = + \left\{ + (u,v)\in C^2~|~ + \forall\varepsilon~ + \exists N\in\mathbb{N}~ + \forall (a,b)\in\mathbb{N}^2~ + 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$. + Nous définissons alors l'ensemble des \emph{Nombres réels} $\mathbb{R}=C/T$. + +\end{definition} \paragraph{Axiome de régularitée} +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} + \forall A\forall y\forall z + \left( + \forall (x\in A~F(x,y)\wedge F(x,z)\implies x=z)\implies + (\exists B~B=\{y~|~\exists x\in A~F(x,y)\}) + \right) +\end{equation} +\subsubsection{Arithmétique} +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} + \left\{ + \begin{matrix} + \mathbb{N}\rightarrow\mathbb{Z}\\ + n\mapsto (n,0) + \end{matrix} + \right. +\end{equation} +\begin{equation} + \left\{ + \begin{matrix} + \mathbb{Z}\rightarrow\mathbb{Q}\\ + (a,b)\mapsto ((a,b),(1,1)) + \end{matrix} + \right. +\end{equation} +\begin{equation} + \left\{ + \begin{matrix} + \mathbb{Q}\rightarrow\mathbb{R}\\ + (a,b)\mapsto + \left[ + \left\{ + \begin{matrix} + \mathbb{N}\rightarrow \mathbb{Q}\\ + n\mapsto (a,b) + \end{matrix} + \right. + \right]_T + \end{matrix} + \right. +\end{equation} +Nous identifions aussi $\mathbb{R}$ aux réprésentation 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. + +\subsubsection{Cardinal} +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. +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. + +Nous dirons donc que tout ensemble $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$. +Enfin nous dirons que deux ensemble arbitraires ont le même cardinal si et seulement si ils sont en bijection. -- cgit v1.2.3 From 0e95544f85b523a95fb05b36c4e6b8789c73abfa Mon Sep 17 00:00:00 2001 From: Jan Aalmoes Date: Wed, 4 Sep 2024 00:12:49 +0200 Subject: traduction classification fini --- background/figure/ml/convex/conv_local.pdf | Bin 0 -> 15273 bytes background/figure/ml/convex/f_local3.1.pdf | Bin 0 -> 17254 bytes background/figure/ml/convex/f_local8.28.pdf | Bin 0 -> 11480 bytes background/figure/ml/roc.pdf | Bin 0 -> 8114 bytes background/figure/ml/roc_perfect.pdf | Bin 0 -> 7096 bytes background/figure/ml/roc_random.pdf | Bin 0 -> 7095 bytes background/figure/opti/conv.pdf | Bin 0 -> 13344 bytes background/figure/opti/f.pdf | Bin 0 -> 8666 bytes background/main.tex | 7 +- background/ml.tex | 193 +++++++++++++++++++++++++++- background/opti.tex | 49 +++++++ background/proba.tex | 87 ++++++++----- background/set.tex | 4 + 13 files changed, 297 insertions(+), 43 deletions(-) create mode 100644 background/figure/ml/convex/conv_local.pdf create mode 100644 background/figure/ml/convex/f_local3.1.pdf create mode 100644 background/figure/ml/convex/f_local8.28.pdf create mode 100644 background/figure/ml/roc.pdf create mode 100644 background/figure/ml/roc_perfect.pdf create mode 100644 background/figure/ml/roc_random.pdf create mode 100644 background/figure/opti/conv.pdf create mode 100644 background/figure/opti/f.pdf create mode 100644 background/opti.tex (limited to 'background') diff --git a/background/figure/ml/convex/conv_local.pdf b/background/figure/ml/convex/conv_local.pdf new file mode 100644 index 0000000..ca1717b Binary files /dev/null and b/background/figure/ml/convex/conv_local.pdf differ diff --git a/background/figure/ml/convex/f_local3.1.pdf b/background/figure/ml/convex/f_local3.1.pdf new file mode 100644 index 0000000..52d5e5c Binary files /dev/null and b/background/figure/ml/convex/f_local3.1.pdf differ diff --git a/background/figure/ml/convex/f_local8.28.pdf b/background/figure/ml/convex/f_local8.28.pdf new file mode 100644 index 0000000..817a7c3 Binary files /dev/null and b/background/figure/ml/convex/f_local8.28.pdf differ diff --git a/background/figure/ml/roc.pdf b/background/figure/ml/roc.pdf new file mode 100644 index 0000000..81888f0 Binary files /dev/null and b/background/figure/ml/roc.pdf differ diff --git a/background/figure/ml/roc_perfect.pdf b/background/figure/ml/roc_perfect.pdf new file mode 100644 index 0000000..9e7d294 Binary files /dev/null and b/background/figure/ml/roc_perfect.pdf differ diff --git a/background/figure/ml/roc_random.pdf b/background/figure/ml/roc_random.pdf new file mode 100644 index 0000000..06957d7 Binary files /dev/null and b/background/figure/ml/roc_random.pdf differ diff --git a/background/figure/opti/conv.pdf b/background/figure/opti/conv.pdf new file mode 100644 index 0000000..0e78124 Binary files /dev/null and b/background/figure/opti/conv.pdf differ diff --git a/background/figure/opti/f.pdf b/background/figure/opti/f.pdf new file mode 100644 index 0000000..489ce5f Binary files /dev/null and b/background/figure/opti/f.pdf differ diff --git a/background/main.tex b/background/main.tex index 9a9f287..76c5a6f 100644 --- a/background/main.tex +++ b/background/main.tex @@ -43,12 +43,7 @@ a & b & a\iff b & a\implies b & a\wedge b & a\vee b & \neg a\\ \subsection{Optimisation} \label{sec:background-opti} - \subsubsection{Multiplicateurs de Lagrange} - - \subsubsection{Descente de gradient} - \paragraph{Descente de gradient stochastique} - - \paragraph{Descente de gradient exponentiée} + \input{background/opti} \section{Apprentissage automatique} \label{sec:background-ml} diff --git a/background/ml.tex b/background/ml.tex index 2482b40..a4c9e1d 100644 --- a/background/ml.tex +++ b/background/ml.tex @@ -1,20 +1,199 @@ +L'aprantissiage automatique\footnote{\textit{Machine learning}} est le fondement de l'IA moderne. + + \subsection{Principe} +Repprenosn 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. +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. + \subsection{Entraîner un modèle} - \subsubsection{Fonction de coût} +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}, 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. + +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. + +Nous definisson le modèle suivant. +\begin{equation*} + f: + \left\{ + \begin{matrix} + E\times\Theta\rightarrow \mathbb{R}^n\\ + x\mapsto f(x,\theta) + \end{matrix} + \right. +\end{equation*} +Alors une fonctions de coût, est une fonction $l$ de $\mathbb{R}^n\times\mathbb{R}^n$ dans $\mathbb{R}^+$. +On se donne l'espace probabilisé $(\Omega,\mathcal{T},P)$. +Soit $\mathcal{V}$ l'ensemble des variables aléatoire de $\Omega$ dans $\mathbb{R}^+$. + +Nous pouvons ainsi définir le coût induit par un choix de paramètres par la fonction +\begin{equation*} + C:\left\{ + \begin{matrix} + \Theta\rightarrow \mathcal{V}\\ + \theta\mapsto + \left\{ + \begin{matrix} + \Omega\rightarrow\mathbb{R}^+\\ + \omega\mapsto + l(f(X(\omega),\theta),Y(\omega)) + \end{matrix} + \right. + \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 un des algorithmes de minimisation vu à la Section~\ref{sec:background-opti-sgd} pour résoudre le probleme 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}. + +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. + \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. + \subsubsection{Classification} + \label{sec:backgroung-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{} ainsi il existe beaucoup d'outil qui permette d'evaluer ce genre de classifieur. - \paragraph{La courbe ROC} - \paragraph{La courbe de precision/recall} + 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}. + + Nous modélisons 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 : + \begin{itemize} + \item $X:\Omega\rightarrow \mathcal{X}$ + \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$. + + Grace à ces objets, nous allons définir des qunatités qui décrivent l'utilitée du modèle. + La première est + l'\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 \textit{accuracy} 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 ? + Voici donc un modèle qui atteint cette performance : + \begin{equation} + f: + \left\{ + \begin{matrix} + \mathcal{X}\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 \textit{accuracy}, pour plus lisibilité nons 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\\ + &\text{Par la formule des probabilités totale}\nonumber\\ + =&P(\hat{Y}=0|Y=0)P(Y=0) + P(\hat{Y}=1|Y=1)P(Y=1)\label{eq:background-ml-ac}\\ + =&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$. + Nous avons donc bien une accuracy de $79\%$ bien que le modèle n'ai aucune utilité pratique ! + + Ainsi l'accuracy est significative uniquement quand $Y$ suit une loi uniforme. + Nous définisson donc une autre métrique : la \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 la \textit{balanced accuracy} 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 la \textit{balanced accuracy} avec l'exemple précedent 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. + 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$. + + Ainsi si nous calculons l'\textit{accuracy}, la \textit{balance accuracy} 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 : + \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)$ + \end{itemize} + \begin{equation*} + \text{roc}:\left\{ + \begin{matrix} + [0,1]\rightarrow [0,1]\times[0,1]\\ + \uptau\mapsto (\text{fpr}(\uptau),\text{tpr}(\uptau)) + \end{matrix} + \right. + \end{equation*} + + \begin{figure} + \centering + \begin{subfigure}{0.3\linewidth} + \centering + \includegraphics[width=\linewidth]{background/figure/ml/roc.pdf} + \caption{ROC d'une foret aléatoire sur un problème scolaire ($\textit{AUC}\approx 0,8$).} + \end{subfigure} + \begin{subfigure}{0.3\linewidth} + \centering + \includegraphics[width=\linewidth]{background/figure/ml/roc_perfect.pdf} + \caption{ROC parfaite ($\textit{AUC}=1$).} + \end{subfigure} + \begin{subfigure}{0.3\linewidth} + \centering + \includegraphics[width=\linewidth]{background/figure/ml/roc_random.pdf} + \caption{ROC \textit{random guess} ($\textit{AUC}=\frac{1}{2}$).} + \end{subfigure} + \caption{La courbe ROC.} + \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. + + 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$. + \subsubsection{Regression} -\subsection{Décentralisation} - \subsubsection{Federated learning} -\subsection{Modèles génératifs} + 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. + 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. + + +\subsection{Apprentissage profond} +\subsubsection{Réseau de neurones} +\subsubsection{Modèle generatif} \label{sec:background-generation} diff --git a/background/opti.tex b/background/opti.tex new file mode 100644 index 0000000..9d346d6 --- /dev/null +++ b/background/opti.tex @@ -0,0 +1,49 @@ +L'optimisation est une branche est des mathématiques appliquées qui cherche à trouver les points pour lequels une fonctions réalise un certain nombre d'exigence. +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. +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{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}\}$. + +\begin{figure} + \centering + \begin{subfigure}{0.45\linewidth} + \centering + \includegraphics[width=0.66\linewidth]{background/figure/opti/f.pdf} + \caption{La suite $u$ approche un minimum locale de la fonction $f$.} + \end{subfigure} + \hspace{1cm} + \begin{subfigure}{0.45\linewidth} + \centering + \includegraphics[width=0.66\linewidth]{background/figure/opti/conv.pdf} + \caption{Convergence des l'écart entre $u$ et le minimum vers $0$ en fonction des itérations.} + \label{fig:background-opti-gd} + \end{subfigure} +\end{figure} + + +\begin{figure} + \begin{subfigure}{0.3\linewidth} + \includegraphics[width=\linewidth]{background/figure/ml/convex/f_local3.1.pdf} + \caption{L'algorithme tombe dans un minimum locale ($u_0=3,1$).} + \end{subfigure} + \begin{subfigure}{0.3\linewidth} + \includegraphics[width=\linewidth]{background/figure/ml/convex/f_local8.28.pdf} + \caption{L'algorithme tombe dans un minimum globale ($u_0=8,28$).} + \end{subfigure} + \begin{subfigure}{0.3\linewidth} + \includegraphics[width=\linewidth]{background/figure/ml/convex/conv_local.pdf} + \caption{Convergence vers un minimum locale et globale.} + \end{subfigure} + \caption{Impacte de la convexité sur la convergence.} + \label{fig:background-opti-cvx} +\end{figure} +\subsubsection{Multiplicateurs de Lagrange} + +\paragraph{Descente de gradient exponentiée} diff --git a/background/proba.tex b/background/proba.tex index 6050ef7..2cb0098 100644 --- a/background/proba.tex +++ b/background/proba.tex @@ -1,46 +1,73 @@ -La théorie des probability est profondément liée au machine learning. +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. -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 nous pas d'être un cours complet. +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 cour de Jean-François Le Gall de l'Ecole Normale Supérieur de Paris~\cite{proba}. +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}. 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'un nombre dénombrable d'elements de $\mathcal{A}$. +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 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é. +Soit $(A, \mathcal{A}, d)$ et $(B, \mathcal{B}, e)$ deux espaces mesurés. +Nous définissons alors +\begin{equation*} + \mathcal{A}\otimes\mathcal{B} = \sigma\left( + \left\{ + a\times b \mid a\in\mathcal{A}\wedge b\in\mathcal{B} + \right\}\right) +\end{equation*} +et de plus la mesure produit de $d$ et $e$, que l'on note $d\otimes e$, est l'unique mesure telle que +\begin{equation*} + \forall a\in\mathcal{A}\forall b\in\mathcal{B}~d\otimes e(a\times b) = d(a)\cdot e(b) +\end{equation*} +Alors l'espace $(A\times B,\mathcal{A}\otimes\mathcal{B},d\otimes e)$ est un espace mesuré. + 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 : +\begin{equation} + d_f: + \left\{ + \begin{matrix} + \mathcal{B}\rightarrow [0,+\infty]\\ + b\mapsto d\left(f^{-1}(b)\right) + + \end{matrix} + \right. +\end{equation} 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 de probabilite suivante : -$d_X :\mathcal{X}\rightarrow [0,1]$, $x\mapsto d(X^{-1}(x))$. - -Having introduced probability theory, we explicit the relation with the ML theory described previously. -Let $I$ a finite set, $\mathcal{X}$, $\mathcal{S}$ and $\mathcal{Y}$ the sets of features, sensitive attribute and label. -Let $d:I\rightarrow \mathcal{X}\times\mathcal{S}\times\mathcal{Y}$ a dataset. -Let $\#$ be the measure on $(I,\mathcal{P}(I))$ which maps to every $a$ in $\mathcal{P}(I)$ the number of elements of $a$. -Let $P:\mathcal{P}(I)\rightarrow [0,1]$, $a\mapsto \frac{\#(a)}{\#(I)}$. -Then $(I, \mathcal{P}(I), P)$ is a probability space. -On this space we can define the following random variables: -\begin{itemize} - \item $X:I\rightarrow \mathcal{X},~i\mapsto (d(i))_0$ - \item $S:I\rightarrow \mathcal{S},~i\mapsto (d(i))_1$ - \item $Y:I\rightarrow \mathcal{Y},~i\mapsto (d(i))_2$ -\end{itemize} -Where for a vector $u$, $u_j$ refers to the $j$th element of $u$. - -From there we can define various random variables that will be useful in the rest of the paper. -For instance $\hat{Y}=f\circ X$ is random variable that represents the prediction of a trained machine learning model $f$. -We can use it to write the accuracy in a compact way: $P(\hat{Y}=Y)$ by using the well accepted abuse of notations that for a random variable $A$ and an event $a$, -$\{A\in a\} = \{i\in\mathcal{P}(I)~|~A(i)\in a\} = A^{-1}(a)$. -The accuracy is a reliable metric of a trained model's utility when $P(Y=0) = P(Y=1) = \frac{1}{2}$ but not so much when there is unbalance in $Y$. -To take into account an eventual unbalanced distribution of the labels, we will consider the balanced accuracy : -$\frac{P(\hat{Y}=0|Y=0) + P(\hat{Y}=1|Y=1)}{2}$. - -Finally in the context of attribute inference attack at inference time, we define the random variable $\hat{S}=a\circ \hat{Y}$ where here $a$ is a machine learning model trained to infer sensitive attribute from model's output. +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$. + + +%Having introduced probability theory, we explicit the relation with the ML theory described previously. +%Let $I$ a finite set, $\mathcal{X}$, $\mathcal{S}$ and $\mathcal{Y}$ the sets of features, sensitive attribute and label. +%Let $d:I\rightarrow \mathcal{X}\times\mathcal{S}\times\mathcal{Y}$ a dataset. +%Let $\#$ be the measure on $(I,\mathcal{P}(I))$ which maps to every $a$ in $\mathcal{P}(I)$ the number of elements of $a$. +%Let $P:\mathcal{P}(I)\rightarrow [0,1]$, $a\mapsto \frac{\#(a)}{\#(I)}$. +%Then $(I, \mathcal{P}(I), P)$ is a probability space. +%On this space we can define the following random variables: +%\begin{itemize} +% \item $X:I\rightarrow \mathcal{X},~i\mapsto (d(i))_0$ +% \item $S:I\rightarrow \mathcal{S},~i\mapsto (d(i))_1$ +% \item $Y:I\rightarrow \mathcal{Y},~i\mapsto (d(i))_2$ +%\end{itemize} +%MWhere for a vector $u$, $u_j$ refers to the $j$th element of $u$. + +%From there we can define various random variables that will be useful in the rest of the paper. +%For instance $\hat{Y}=f\circ X$ is random variable that represents the prediction of a trained machine learning model $f$. +%We can use it to write the accuracy in a compact way: $P(\hat{Y}=Y)$ by using the well accepted abuse of notations that for a random variable $A$ and an event $a$, +%$\{A\in a\} = \{i\in\mathcal{P}(I)~|~A(i)\in a\} = A^{-1}(a)$. +%The accuracy is a reliable metric of a trained model's utility when $P(Y=0) = P(Y=1) = \frac{1}{2}$ but not so much when there is unbalance in $Y$. +%To take into account an eventual unbalanced distribution of the labels, we will consider the balanced accuracy : +%$\frac{P(\hat{Y}=0|Y=0) + P(\hat{Y}=1|Y=1)}{2}$. +% +%Finally in the context of attribute inference attack at inference time, we define the random variable $\hat{S}=a\circ \hat{Y}$ where here $a$ is a machine learning model trained to infer sensitive attribute from model's output. diff --git a/background/set.tex b/background/set.tex index 2e660f6..b45e302 100644 --- a/background/set.tex +++ b/background/set.tex @@ -85,6 +85,10 @@ $\forall b\in B (b\in A \wedge F)$ \right\} \end{equation} + 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$. + 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. + \end{definition} \paragraph{Axiome du choix} -- cgit v1.2.3 From 294b3293c6710a63b96195ec9785412aa175c245 Mon Sep 17 00:00:00 2001 From: Jan Aalmoes Date: Wed, 4 Sep 2024 23:20:36 +0200 Subject: ML background presque finit, ne manque plus que la partie generatif --- background/ml.tex | 128 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 128 insertions(+) (limited to 'background') diff --git a/background/ml.tex b/background/ml.tex index a4c9e1d..d1c08a3 100644 --- a/background/ml.tex +++ b/background/ml.tex @@ -15,6 +15,7 @@ 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. \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}, on cherche à classifier l'éspèce d'Iris à partir de la longeur et de la largeur des sépales et des pétales. @@ -191,9 +192,136 @@ Cette algorithmes évalue l'espérence empirique de $C(\theta)$ sur chaque élé 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. + \begin{figure} + \centering + \begin{subfigure}{0.3\linewidth} + \centering + \includegraphics[width=\linewidth]{background/figure/ml/logit/logit0.3.pdf} + \caption{$\uptau=0,3$} + \end{subfigure} + \begin{subfigure}{0.3\linewidth} + \centering + \includegraphics[width=\linewidth]{background/figure/ml/logit/logit0.5.pdf} + \caption{$\uptau=0,5$} + \end{subfigure} + \begin{subfigure}{0.3\linewidth} + \centering + \includegraphics[width=\linewidth]{background/figure/ml/logit/logit0.7.pdf} + \caption{$\uptau=0,7$} + \end{subfigure} + \begin{subfigure}{0.6\linewidth} + \centering + \includegraphics[width=\linewidth]{background/figure/ml/logit/metric.pdf} + \caption{Metriques de classifications en fonction du seuil.} + \label{subfig:background-ml-logit-d} + \end{subfigure} + \caption{Exemple de relation entre regression (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} il y $28\%$ de points positif représenté en rouge. + Cela explique la différence entre \textit{accuracy} et \textit{balanced accuracy} à 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}. + \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}. + +Un réseau de neuronnes est composé de plusieur couches successives qui on chacune des paramètre. +En d'autre termes un modèle +\begin{equation*} + f:\left\{ + \begin{matrix} + E\times \Theta\rightarrow \mathbb{R}^n\\ + (x,\theta)\mapsto f(x,\theta) + \end{matrix} + \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 : +\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. + +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). +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\\ + x\mapsto \left( + \begin{matrix} + 1_{\mathbb{R}^+}(x_0)x_0\\ + \vdots\\ + 1_{\mathbb{R}^+}(x_{n-1})x_{n-1}\\ + \end{matrix} + \right) + \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. + +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}$ + +Enfin la partie additive est appellé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\{ + \begin{matrix} + \mathbb{R}^o\rightarrow\mathbb{R}^p\\ + x\mapsto\text{ReLu}(Mx+b) + \end{matrix} + \right. +\end{equation*} + +Regardon maintenant les couches de convolutions. +L'idée de la convolution est d'extraire des représentations\footnote{\textit{Features extraction}}. + +\begin{equation} + f_i(x,\theta_i) = \left\{ + \begin{matrix} + \mathbb{N}^\mathbb{}\rightarrow\mathbb{N}^\mathbb{N}\\ + u\mapsto\int_{\mathbb{N}}x(u\bowtie t)\theta(\#J\bowtie t)d\sum_{j\in\mathbb{N}}\delta_j(t) + \end{matrix} + \right. +\end{equation} + + + + \subsubsection{Modèle generatif} \label{sec:background-generation} + +A generator is a function that takes as input a real dataset and outputs a synthetic dataset. +This definition is general enough so that the identity function is a generator. +Even though synthetic datasets are supposedly different than real world datasets. +We refer to the output of the identity generator as real data while referring to the output of another generator as synthetic data. + +In addition to the identity generator we use General Adversarial Networks (GAN)~\cite{gan}. +The goal of a GAN is to generate realistic samples given a distribution of multivariate data. +To do so a GAN leverages two neural networks: a generator and a discriminator. +The domain of the generator (its input space) is of low dimension with respect to its codomain (its output space) which has the same dimension as the data we want to generate. +For instance with 64 by 64 images, the codomain is a matrix with 64 rows and 64 columns. +To generate a new sample, we evaluate the generator on a sample of a multivariate standard normal distribution where the dimension is the domain's dimension. +This output is the new generated synthetic data point. + +The discriminator is only used when training the GAN with the goal of making sure that the generator produces realistic data. +To do so, the discriminator is a neural network with a classification goal: infer if a sample is synthetic or real. +Hence in the training procedure, the discriminator and the generator are in competition: the generator goal is to fool the discriminator into classifying synthetic data as real data. -- cgit v1.2.3 From 03556b31409ac5e8b81283d3a6481691c11846d7 Mon Sep 17 00:00:00 2001 From: Jan Aalmoes Date: Wed, 4 Sep 2024 23:56:27 +0200 Subject: background gan --- background/ml.tex | 32 ++++++++++++++++---------------- 1 file changed, 16 insertions(+), 16 deletions(-) (limited to 'background') diff --git a/background/ml.tex b/background/ml.tex index d1c08a3..d1f95b0 100644 --- a/background/ml.tex +++ b/background/ml.tex @@ -309,19 +309,19 @@ L'idée de la convolution est d'extraire des représentations\footnote{\textit{F \subsubsection{Modèle generatif} \label{sec:background-generation} -A generator is a function that takes as input a real dataset and outputs a synthetic dataset. -This definition is general enough so that the identity function is a generator. -Even though synthetic datasets are supposedly different than real world datasets. -We refer to the output of the identity generator as real data while referring to the output of another generator as synthetic data. - -In addition to the identity generator we use General Adversarial Networks (GAN)~\cite{gan}. -The goal of a GAN is to generate realistic samples given a distribution of multivariate data. -To do so a GAN leverages two neural networks: a generator and a discriminator. -The domain of the generator (its input space) is of low dimension with respect to its codomain (its output space) which has the same dimension as the data we want to generate. -For instance with 64 by 64 images, the codomain is a matrix with 64 rows and 64 columns. -To generate a new sample, we evaluate the generator on a sample of a multivariate standard normal distribution where the dimension is the domain's dimension. -This output is the new generated synthetic data point. - -The discriminator is only used when training the GAN with the goal of making sure that the generator produces realistic data. -To do so, the discriminator is a neural network with a classification goal: infer if a sample is synthetic or real. -Hence in the training procedure, the discriminator and the generator are in competition: the generator goal is to fool the discriminator into classifying synthetic data as real data. +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. + +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. +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. +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. -- cgit v1.2.3 From bf5b05a84e877391fddd1b0a0b752f71ec05e901 Mon Sep 17 00:00:00 2001 From: Jan Aalmoes Date: Wed, 11 Sep 2024 00:10:50 +0200 Subject: Preuve existe f pas cca equivalant exists f BA pas randomguess --- background/figure/ml/logit/logit0.1.pdf | Bin 0 -> 16646 bytes background/figure/ml/logit/logit0.2.pdf | Bin 0 -> 16649 bytes background/figure/ml/logit/logit0.3.pdf | Bin 0 -> 16676 bytes background/figure/ml/logit/logit0.30000000000000004.pdf | Bin 0 -> 16617 bytes background/figure/ml/logit/logit0.4.pdf | Bin 0 -> 16623 bytes background/figure/ml/logit/logit0.5.pdf | Bin 0 -> 16646 bytes background/figure/ml/logit/logit0.6.pdf | Bin 0 -> 16637 bytes background/figure/ml/logit/logit0.7.pdf | Bin 0 -> 16687 bytes background/figure/ml/logit/logit0.7000000000000001.pdf | Bin 0 -> 16635 bytes background/figure/ml/logit/logit0.8.pdf | Bin 0 -> 16643 bytes background/figure/ml/logit/logit0.9.pdf | Bin 0 -> 17263 bytes background/figure/ml/logit/metric.pdf | Bin 0 -> 11081 bytes 12 files changed, 0 insertions(+), 0 deletions(-) create mode 100644 background/figure/ml/logit/logit0.1.pdf create mode 100644 background/figure/ml/logit/logit0.2.pdf create mode 100644 background/figure/ml/logit/logit0.3.pdf create mode 100644 background/figure/ml/logit/logit0.30000000000000004.pdf create mode 100644 background/figure/ml/logit/logit0.4.pdf create mode 100644 background/figure/ml/logit/logit0.5.pdf create mode 100644 background/figure/ml/logit/logit0.6.pdf create mode 100644 background/figure/ml/logit/logit0.7.pdf create mode 100644 background/figure/ml/logit/logit0.7000000000000001.pdf create mode 100644 background/figure/ml/logit/logit0.8.pdf create mode 100644 background/figure/ml/logit/logit0.9.pdf create mode 100644 background/figure/ml/logit/metric.pdf (limited to 'background') diff --git a/background/figure/ml/logit/logit0.1.pdf b/background/figure/ml/logit/logit0.1.pdf new file mode 100644 index 0000000..51d3a38 Binary files /dev/null and b/background/figure/ml/logit/logit0.1.pdf differ diff --git a/background/figure/ml/logit/logit0.2.pdf b/background/figure/ml/logit/logit0.2.pdf new file mode 100644 index 0000000..7245ed3 Binary files /dev/null and b/background/figure/ml/logit/logit0.2.pdf differ diff --git a/background/figure/ml/logit/logit0.3.pdf b/background/figure/ml/logit/logit0.3.pdf new file mode 100644 index 0000000..1665fec Binary files /dev/null and b/background/figure/ml/logit/logit0.3.pdf differ diff --git a/background/figure/ml/logit/logit0.30000000000000004.pdf b/background/figure/ml/logit/logit0.30000000000000004.pdf new file mode 100644 index 0000000..8ffe883 Binary files /dev/null and b/background/figure/ml/logit/logit0.30000000000000004.pdf differ diff --git a/background/figure/ml/logit/logit0.4.pdf b/background/figure/ml/logit/logit0.4.pdf new file mode 100644 index 0000000..772d3ff Binary files /dev/null and b/background/figure/ml/logit/logit0.4.pdf differ diff --git a/background/figure/ml/logit/logit0.5.pdf b/background/figure/ml/logit/logit0.5.pdf new file mode 100644 index 0000000..ffb170a Binary files /dev/null and b/background/figure/ml/logit/logit0.5.pdf differ diff --git a/background/figure/ml/logit/logit0.6.pdf b/background/figure/ml/logit/logit0.6.pdf new file mode 100644 index 0000000..31df9bc Binary files /dev/null and b/background/figure/ml/logit/logit0.6.pdf differ diff --git a/background/figure/ml/logit/logit0.7.pdf b/background/figure/ml/logit/logit0.7.pdf new file mode 100644 index 0000000..690278c Binary files /dev/null and b/background/figure/ml/logit/logit0.7.pdf differ diff --git a/background/figure/ml/logit/logit0.7000000000000001.pdf b/background/figure/ml/logit/logit0.7000000000000001.pdf new file mode 100644 index 0000000..c24731f Binary files /dev/null and b/background/figure/ml/logit/logit0.7000000000000001.pdf differ diff --git a/background/figure/ml/logit/logit0.8.pdf b/background/figure/ml/logit/logit0.8.pdf new file mode 100644 index 0000000..b7d276e Binary files /dev/null and b/background/figure/ml/logit/logit0.8.pdf differ diff --git a/background/figure/ml/logit/logit0.9.pdf b/background/figure/ml/logit/logit0.9.pdf new file mode 100644 index 0000000..a37dc4f Binary files /dev/null and b/background/figure/ml/logit/logit0.9.pdf differ diff --git a/background/figure/ml/logit/metric.pdf b/background/figure/ml/logit/metric.pdf new file mode 100644 index 0000000..bdaa5a8 Binary files /dev/null and b/background/figure/ml/logit/metric.pdf differ -- cgit v1.2.3 From 7fc151d6a198d13dc9e1374522ec396d72905d3f Mon Sep 17 00:00:00 2001 From: Jan Aalmoes Date: Wed, 11 Sep 2024 11:08:02 +0200 Subject: Ajout notations --- background/proba.tex | 16 ++++++++++++++++ background/set.tex | 52 +++++++++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 65 insertions(+), 3 deletions(-) (limited to 'background') diff --git a/background/proba.tex b/background/proba.tex index 2cb0098..5bce111 100644 --- a/background/proba.tex +++ b/background/proba.tex @@ -13,6 +13,20 @@ Soit maintenant $A\subset\mathcal{P}(A)$, nous appellons $\sigma(A)$ la plus pet 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$ +\begin{equation*} + \delta_a : \left\{ + \begin{matrix} + \mathcal{P}(A)\rightarrow \{0,1\}\\ + B\mapsto\left\{ + \begin{matrix} + 1&\text{si}&a\in B\\ + 0&\text{sinon}& + \end{matrix} + \right. + \end{matrix} + \right. +\end{equation*} Soit $(A, \mathcal{A}, d)$ et $(B, \mathcal{B}, e)$ deux espaces mesurés. Nous définissons alors @@ -47,6 +61,8 @@ Dans le cas particulier où $d(A) = 1$, nous appelons $d$ une mesure de probabil 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$. +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\})$. + %Having introduced probability theory, we explicit the relation with the ML theory described previously. %Let $I$ a finite set, $\mathcal{X}$, $\mathcal{S}$ and $\mathcal{Y}$ the sets of features, sensitive attribute and label. diff --git a/background/set.tex b/background/set.tex index b45e302..e011510 100644 --- a/background/set.tex +++ b/background/set.tex @@ -42,6 +42,17 @@ Pour tout ensemble $A$ il existe un ensemble $\mathcal{P}(A)$ qui est l'ensemble 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 $\forall b\in B (b\in A \wedge F)$ +\begin{definition}[Intersection] + Pour des ensembles $A$ et $B$, + \begin{equation*} + A\cap B=\{a\in A\mid a\in B\} + \end{equation*} + et + \begin{equation*} + A\backslash B=\{a\in A\mid \neg(a\in B)\} + \end{equation*} +\end{definition} + \begin{definition}[Fonctions] \textbf{2-uplet.} @@ -75,21 +86,43 @@ $\forall b\in B (b\in A \wedge F)$ \right. \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 + \begin{equation*} + id_E:\left\{ + \begin{matrix} + E\rightarrow E\\ + x\mapsto x + \end{matrix} + \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. \textbf{Produit cartésien.} - Soit $A$ un ensemble $f$ une fonctions + Soit $A$ un ensemble $f$ une fonctions le produit cartésien est \begin{equation} \bigtimes_{a\in A}f(a) = \left\{ - g~|~D_g=A\wedge (\forall a\in A~g(i)\in f(i)) + g~|~D_g=A\wedge (\forall a\in A~g(a)\in f(a)) \right\} \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$. 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. -\end{definition} + 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 $B\subset F$, + $f^{-1}(B)=\{x\in E\mid f(x)\in B$. + \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. @@ -229,6 +262,19 @@ Nous identifions aussi $\mathbb{R}$ aux réprésentation en base 10 de ses élé 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 : +\begin{itemize} + \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$. +\end{itemize} + +\subsubsection{Intervalle} +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\}$. +Et aussi sa contrepartie entière : $[|a,b|] = [a,b]\cap\mathbb{N}$. + \subsubsection{Cardinal} 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. -- cgit v1.2.3 From faa07a8f3337c5d191597ea9b9587cc0969d663c Mon Sep 17 00:00:00 2001 From: Jan Aalmoes Date: Fri, 13 Sep 2024 00:07:42 +0200 Subject: =?UTF-8?q?avnac=C3=A9=20aia,=20remerciement=20notations,=20notes?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- background/eq.tex | 30 ++++++++++++++++-------------- 1 file changed, 16 insertions(+), 14 deletions(-) (limited to 'background') diff --git a/background/eq.tex b/background/eq.tex index 8a76ee7..446ad95 100644 --- a/background/eq.tex +++ b/background/eq.tex @@ -1,22 +1,24 @@ \label{sec:bck_fair} -Algorithmic fairness aims at reducing biases in ML model predictions. -Indeed, data records belonging to certain subgroups influence $targetmodel$'s predictions more than others. -For instance in criminal justice, the ethnicity of a culprit plays a non-negligible role in the prediction of them reoffending~\cite{fairjustice}. Generally, data records in the minority subgroup face unfair prediction behaviour compared to data records in the majority subgroup. These subgroups are identified based on a sensitive attribute (e.g., race or sex). -Those biases are learnt by $targetmodel$ as they are part of the distribution of the training dataset. -There is two main categories of fairness of a ML model: +L'équitée algorithmique à pour but de réduire les bias dans le modèle prédictif. +En effet, le fait qu'une donnée d'entraînement 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}. +Les minoritée sont identifié par un attribut sensible comme la couleur de peau, le genre ou l'orientation sexuelle. +Pour savoir si un attribut est sensible ou non, nous pouvons nous référer à l'observatoire de inégalités. +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. -\textbf{Individual fairness} ensures that two data records with same attributes except for $S$ have the same model prediction. -This notion does not dwell on sensitive attribute and as such is not really useful in our goal of mitigating attribute inference attack at inference time. -So we set it aside for the rest of the paper. +L'équitée en apprantissag automatique se présente sous deux aspect qui mettent lumière deux visions différentes : -\textbf{Group fairness} comes from the idea that different subgroups defined by an attribute such a skin color or gender should be treated equally. -We focus our study on group fairness where $S$ represents either sex or race (i.e., $S(i)$ equals to 0 for woman, 1 for man, and 0 for black, 1 for white, respectively). -There are different definitions of group fairness which have been introduced in prior work. -We discuss two well-established and commonly used metrics: demographic parity and equality of odds. +\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é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 deux qui sont bien établis dans la litérature et souvant utilisé : la paritée demographique\footnote{Demographic parity} et l'équitée de chances\footnote{Equality of odds}. \begin{definition} -\label{def:dp} +\label{def:background-eq-dp} $\hat{Y}$ satisfies demparity for $S$ if and only if: $P(\hat{Y}=0 | S=0) = P(\hat{Y}=0 | S=1)$. From that, we will call $|P(\hat{Y}=0 | S=0) - P(\hat{Y}=0 | S=1)|$ the demPar-level of $\hat{Y}$. \end{definition} @@ -28,7 +30,7 @@ However, this may result in different false positive and true positive rates if Hardt et al.~\cite{fairmetric2} proposed eo as a modification of demparity to ensure that both the true positive rate and false positive rate will be the same for each population. \begin{definition} - \label{def:eo} + \label{def:background-eq-eoo} $\hat{Y}$, classifier of $Y$, satisfies equality of odds for $S$ if and only if: $\forall (\hat{y},y)\in\{0,1\}^2 \quad P(\hat{Y}=\hat{y} | S=0,Y=y) = P(\hat{Y}=\hat{y} | S=1,Y=y)$. \end{definition} -- cgit v1.2.3 From 4aae3ea0427a6c9e9a8519a38d9d9d0ac5f0ec9c Mon Sep 17 00:00:00 2001 From: Jan Aalmoes Date: Sat, 21 Sep 2024 16:27:27 +0200 Subject: fin intro --- background/alg.tex | 99 ++++++++++++++++++++++++++++++++++++ background/dif.tex | 95 ++++++++++++++++++++++++++++++++++ background/eq | 0 background/eq.tex | 99 ++++++++++++++++++++++++++++-------- background/figure/eq/reg_unfair.pdf | Bin 0 -> 17023 bytes background/main.tex | 21 +++----- background/ml.tex | 63 ++++++++++++++++------- background/opti.tex | 59 +++++++++++++-------- background/proba.tex | 22 ++++++++ background/set.tex | 17 +++++++ 10 files changed, 403 insertions(+), 72 deletions(-) create mode 100644 background/alg.tex create mode 100644 background/dif.tex create mode 100644 background/eq create mode 100644 background/figure/eq/reg_unfair.pdf (limited to 'background') diff --git a/background/alg.tex b/background/alg.tex new file mode 100644 index 0000000..b2f6418 --- /dev/null +++ b/background/alg.tex @@ -0,0 +1,99 @@ +\subsubsection{Espace vecotriel} +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$. + Nous dirons que $(E,+)$ est un groupe si et seulement si + \begin{enumerate} + \item $\forall (e,f)\in E^2~e+f\in E$ (loi interne) + \item $\forall (e,f,g)\in E^2~(e+f)+g=e+(f+g)$ + \item $\exists 0\in E~\forall e\in E~e+0=e\wedge0+e=e$ + \item $\forall a\in E\exists b\in E~a+b=e\wedge b+e=e$ + \end{enumerate} + Dans le cas où en plus de ces trois points + $\forall (e,f)\in E^2~e+f=f+e$ + Nous dirons que le groupe $(E,+)$ est abélien. +\end{definition} + +\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. + \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$ + \item $\forall (r,s,e)\in\mathbb{R}\times\mathbb{R}\times E~(r+s)e=re+se$ + \item $\forall (r,s,e)\in\mathbb{R}\times\mathbb{R}\times E~(rs)e=r(se)$ + \item $\forall e\in E~1e=e$ + \end{enumerate} +\end{definition} + +Alors $\forall n\in\mathbb{N}~\mathbb{R}^n$ est un espace vectoriel. + +\subsubsection{Application linéaire} +\label{sec:background-alg-L} +Soit $E$ et $F$ deux espaces vectoriels. +Une application linéaire $h:E\rightarrow F$ est telle que +$\forall (r,e,f)\in \mathbb{R}\times E\times E~h(re+f)=rh(e)+h(f)$ +Et on note $\mathcal{L}(E,F)$ l'ensemble des applications linéaire de $E$ dans $F$. +Si $E=\mathbb{R}^m$ et $F=\mathbb{R}^n$ alors +la matrice de $f$ est +\begin{equation*} + M_f= + \left( + \begin{matrix} + f(e_0)_0&\cdots&f(e_{m-1})_0\\ + \vdots&\vdots&\vdots\\ + f(e_{0})_{n-1}&\cdots&f(e_{m-1})_{n-1}\\ + \end{matrix} + \right) +\end{equation*} +Où +\begin{equation*} + \forall i\in m~e_i=\left( + \begin{matrix} + 0\\ + \vdots\\ + 0\\ + 1\\ + 0\\ + \vdots\\ + 0 + \end{matrix} + \right) + \begin{matrix} + \\ + \\ + \\ + i\\ + \\ + \\ + \\ + \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$. + +\begin{propriete} + La fonction $M_\square$ est une bijection. +\end{propriete} + +Nous définisson la mutliplication matricielle de la manière suiavante : +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*} + M_gM_f=M{g\circ f} +\end{equation*} +\begin{propriete} +\begin{equation*} + M_gM_f(i,j)=\sum_{k=0}^n M_g(i,k)M_f(k,j) +\end{equation*} +\end{propriete} + +\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. + \begin{equation*} + \text{Tr}(M)=\sum_{i=0}^{n-1}M(i,i) + \end{equation*} +\end{definition} + diff --git a/background/dif.tex b/background/dif.tex new file mode 100644 index 0000000..2ba01f1 --- /dev/null +++ b/background/dif.tex @@ -0,0 +1,95 @@ +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. +\begin{definition}{Produit scalaire euclidien} + \label{def:background-dif-scal} + Soit $(x,y){\in\mathbb{R}^n}^2$ alors le produit scalaire euclidien est + \begin{equation*} + \langle x,y \rangle = \sum_{i=0}^{n-1}x_iy_i + \end{equation*} +\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 + \begin{equation*} + ||x||={\langle x,x\rangle}^{\frac{1}{2}} + \end{equation*} +\end{definition}  + +\begin{definition}{Limite} + \label{def:background-dif-lim} + Soit $f$ une fonction de $\mathbb{R}^m$ dans $\mathbb{R}^n$. + Soit $x\in\mathbb{R}^m$. + Nous dirons que $f$ admet une limite en $x$ si il existe $y\in\mathbb{R}^n$ tel que + \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}. +\end{definition} + +\begin{definition}{Differentielle} + \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$ + \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$. +\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 + \begin{equation*} + \partial_i f :\left\{ + \begin{matrix} + \mathbb{R}\rightarrow \mathbb{R}\\ + x\mapsto df(x)e_i + \end{matrix} + \right. + \end{equation*} + Où $e_i$ est le $i$ème vecteur de la base canonique de $\mathbb{R}^n$. + Et nous définissons le gradient de $f$ par la formule suivante : + \begin{equation*} + \nabla f:\left\{ + \begin{matrix} + \mathbb{R}^n\rightarrow \mathbb{R}^n\\ + x\mapsto\left( + \begin{matrix} + \partial_0 f(x)\\ + \vdots\\ + \partial_{n-1} f(x)\\ + \end{matrix} + \right) + \end{matrix} + \right. + \end{equation*} +\end{definition} +Pour le.a lecteur.ice familier avec la dériviabilité notons que +\begin{equation*} + lim_{h\rightarrow 0}\frac{f(x+he_i)-f(x)}{h} = \partial_i f(x) +\end{equation*} + + +\begin{propriete} + Soit $f:\mathbb{R}^n\rightarrow \mathbb{R}$ différentiable. + \begin{equation*} + \forall (x+h)\in{\mathbb{R}^n}^2~df(x)h = + \langle \nabla f(x),h\rangle + \end{equation*} +\end{propriete} + diff --git a/background/eq b/background/eq new file mode 100644 index 0000000..e69de29 diff --git a/background/eq.tex b/background/eq.tex index 446ad95..b756361 100644 --- a/background/eq.tex +++ b/background/eq.tex @@ -1,12 +1,43 @@ - \label{sec:bck_fair} L'équitée algorithmique à pour but de réduire les bias dans le modèle prédictif. -En effet, le fait qu'une donnée d'entraînement appratienne à certainne minorité peut avoir un impacte sur la qualitée de la prédiction. +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}. -Les minoritée sont identifié par un attribut sensible comme la couleur de peau, le genre ou l'orientation sexuelle. -Pour savoir si un attribut est sensible ou non, nous pouvons nous référer à l'observatoire de inégalités. +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. +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. + +\begin{figure} + \centering + \includegraphics[width=0.5\linewidth]{background/figure/eq/reg_unfair.pdf} + \begin{tabular}{|c|c|c|c|} + \hline + &\textbf{Homme}&\textbf{Femme}&\textbf{Total}\\ + \hline + \textbf{Effectif}&100&20&120\\ + \hline + \makecell{ + \textbf{Répartition}\\ + $\#\{Y=0\}/\#\{Y=1\}$} + &10/10&50/50&60/60\\ + \hline + \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}} + \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 : \textbf{L'équitée individuelle}\footnote{Individual fairness} @@ -15,30 +46,58 @@ cherche à faire en sorte que deux donnée, à toutes choses égale exepté l'at \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 deux qui sont bien établis dans la litérature et souvant utilisé : la paritée demographique\footnote{Demographic parity} et l'équitée de chances\footnote{Equality of odds}. +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}. + +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$. +Ces deux variables prennent leurs valeurs dans un ensemble $F$. +De plus, nous avons l'attribut sensible modélisé par $S$ qui prend ses valeurs dans $G$. + +\begin{definition} +\label{def:background-eq-di} + L'\emph{effet différencié} de $\hat{Y}$ est + \begin{equation*} + \frac{P(\hat{Y}=Y\mid S=0)}{P(\hat{Y}=Y\mid S=1)} + \end{equation*} + 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}. + \begin{definition} \label{def:background-eq-dp} - $\hat{Y}$ satisfies demparity for $S$ if and only if: $P(\hat{Y}=0 | S=0) = P(\hat{Y}=0 | S=1)$. - From that, we will call $|P(\hat{Y}=0 | S=0) - P(\hat{Y}=0 | S=1)|$ the demPar-level of $\hat{Y}$. + $\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} -demparity is the historical definition of fairness. -Legally, disparate impact is the fairness definition recognized by law, where 80\% disparity is an agreed upon tolerance decided in the legal arena. -demparity ensures that the number of correct prediction is the same for each population. -However, this may result in different false positive and true positive rates if the true outcome does actually vary with $S$~\cite{dpbad}. -Hardt et al.~\cite{fairmetric2} proposed eo as a modification of demparity to ensure that both the true positive rate and false positive rate will be the same for each population. +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. +Pour certaines applications cette effet n'est pas souaitable. +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}$, classifier of $Y$, satisfies equality of odds for $S$ if and only if: $\forall (\hat{y},y)\in\{0,1\}^2 \quad - P(\hat{Y}=\hat{y} | S=0,Y=y) = P(\hat{Y}=\hat{y} | S=1,Y=y)$. + $\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 + P(\hat{Y}=\hat{y} | S=s_1,Y=y) = P(\hat{Y}=\hat{y} | S=s_2,Y=y)$. \end{definition} -The above fairness definitions can be achieved using three main fairness mechanisms: (a) pre-processing, (b) in-processing and (c) post-processing. \textit{Pre-processing} algorithms such as reweighing requires access to the training data and assigns weights to the data records to remove discrimination~\cite{preprocessing}. -\textit{In-processing} algorithms such as advdebias~\cite{debiase} and egd~\cite{reductions} add constraint during $targetmodel$'s training to ensure fairness. %reductions -\textit{Post-processing} techniques, in turn, hide the bias in output predictions to satisfy the above fairness constraints but the underlying model is still biased. -Similar to previous work~\cite{chang2021privacy}, we focus on in-processing algorithms. +\subsubsection{Imposer l'équitée 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. + 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}. + +\paragraph{Déscente de gradient exponentiée} -Our work focuses on the theoretical guaranties on attribute inference attacks given by the different fairness notions and not so much on how to implement in-processing fairness mechanism. -Nevertheless in the experiment section we try production ready state of the art implementations of those fairness constraints along unconstrained ML algorithm. +\paragraph{Rééquilibrage adversariel} diff --git a/background/figure/eq/reg_unfair.pdf b/background/figure/eq/reg_unfair.pdf new file mode 100644 index 0000000..f177bc6 Binary files /dev/null and b/background/figure/eq/reg_unfair.pdf differ diff --git a/background/main.tex b/background/main.tex index 76c5a6f..e386396 100644 --- a/background/main.tex +++ b/background/main.tex @@ -1,5 +1,6 @@ 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. @@ -17,13 +18,12 @@ a & b & a\iff b & a\implies b & a\wedge b & a\vee b & \neg a\\ \end{matrix} \end{equation} \subsection{Ensembles et fonctions} -\label{sec:background-set} + \label{sec:background-set} \input{background/set} \subsection{Algèbre linéaire} - \subsubsection{Espace vectoriel} - \subsubsection{Application linéaires} - \subsubsection{Matrices} + \label{sec:background-evr} + \input{background/alg} \subsection{Mesurer le hasard pour prédire et inférer} \label{sec:background-proba} @@ -32,14 +32,9 @@ a & b & a\iff b & a\implies b & a\wedge b & a\vee b & \neg a\\ %\subsection{Probabilitées} %\subsection{Statistiques} -\subsection{Topologie} - \subsubsection{Distances et normes} - \subsubsection{Espaces topologiques} - \subsubsection{Application aux fonctions} - \subsection{Calcul différentiel} - \subsubsection{Différentiel} - \subsubsection{Gradient} + \label{sec:background-dif} + \input{background/dif} \subsection{Optimisation} \label{sec:background-opti} @@ -49,12 +44,12 @@ a & b & a\iff b & a\implies b & a\wedge b & a\vee b & \neg a\\ \label{sec:background-ml} \input{background/ml} -\section{Equité} +\subsection{Equité} \label{sec:background-eq} \input{background/eq} %\subsection{Différentes notions d'équité} -\section{Confidentialité} +\subsection{Confidentialité} \label{sec:background-conf} \input{background/conf} %\subsection{Mitiger l'inéquitée} diff --git a/background/ml.tex b/background/ml.tex index d1f95b0..7372508 100644 --- a/background/ml.tex +++ b/background/ml.tex @@ -1,8 +1,8 @@ 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}. \subsection{Principe} -Repprenosn 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}. +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. @@ -18,7 +18,7 @@ Nous allons présenter ces deux aspects entraîenemnt et évaluation dans les Se \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}, on cherche à classifier l'éspèce d'Iris à partir de la longeur et de la largeur des sépales et des pétales. +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. @@ -57,15 +57,36 @@ Nous pouvons ainsi définir le coût induit par un choix de paramètres par la f \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 un des algorithmes de minimisation vu à la Section~\ref{sec:background-opti-sgd} pour résoudre le probleme suivant : +Nous pouvons donc appliquer une descente de gradient comme vu à la Section~\ref{sec:background-opti-sgd} pour résoudre le probleme 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. 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. +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}. + +\begin{figure} + \begin{subfigure}{0.3\linewidth} + \includegraphics[width=\linewidth]{background/figure/ml/convex/f_local3.1.pdf} + \caption{L'algorithme tombe dans un minimum locale ($u_0=3,1$).} + \end{subfigure} + \begin{subfigure}{0.3\linewidth} + \includegraphics[width=\linewidth]{background/figure/ml/convex/f_local8.28.pdf} + \caption{L'algorithme tombe dans un minimum globale ($u_0=8,28$).} + \end{subfigure} + \begin{subfigure}{0.3\linewidth} + \includegraphics[width=\linewidth]{background/figure/ml/convex/conv_local.pdf} + \caption{Convergence vers un minimum locale et globale.} + \end{subfigure} + \caption{Impacte de la convexité sur la convergence.} + \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é. @@ -73,7 +94,7 @@ Cette algorithmes évalue l'espérence empirique de $C(\theta)$ sur chaque élé 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. \subsubsection{Classification} - \label{sec:backgroung-ml-classif} + \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. @@ -95,10 +116,10 @@ Cette algorithmes évalue l'espérence empirique de $C(\theta)$ sur chaque élé Grace à ces objets, nous allons définir des qunatités qui décrivent l'utilitée du modèle. La première est - l'\textit{accuracy}, c'est la prababilté que le classifieur prédise la bonne classe. Nous la définissons par $P(\hat{Y}=Y)$. + 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 \textit{accuracy} 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 ? + 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 ? Voici donc un modèle qui atteint cette performance : \begin{equation} f: @@ -111,7 +132,7 @@ Cette algorithmes évalue l'espérence empirique de $C(\theta)$ sur chaque élé \end{equation} C'est-à-dire un modèle qui prédise toujours homme. - Calculons son \textit{accuracy}, pour plus lisibilité nons encodons homme par $0$ et femme par $1$. + Calculons son exactitude, pour plus lisibilité nons 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\\ @@ -121,14 +142,14 @@ Cette algorithmes évalue l'espérence empirique de $C(\theta)$ sur chaque élé \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$. - Nous avons donc bien une accuracy de $79\%$ bien que le modèle n'ai aucune utilité pratique ! + Nous avons donc bien une exactitude de $79\%$ bien que le modèle n'ai aucune utilité pratique ! - Ainsi l'accuracy est significative uniquement quand $Y$ suit une loi uniforme. - Nous définisson donc une autre métrique : la \textit{balanced accuracy}. + 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 la \textit{balanced accuracy} est la moyenne et $P(\hat{Y}=0|Y=0)$ et de $P(\hat{Y}=1|Y=1)$. + 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 la \textit{balanced accuracy} avec l'exemple précedent nous obtenons $\frac{1+0}{2}=0,5$. + Ainsi, en calculant l'exactitude equilibrée avec l'exemple précedent 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)} @@ -138,7 +159,7 @@ Cette algorithmes évalue l'espérence empirique de $C(\theta)$ sur chaque élé 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$. - Ainsi si nous calculons l'\textit{accuracy}, la \textit{balance accuracy} ou tout autre metrique que nous avons présenté précédament elle dépendra du seuil ($\uptau$). + 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 : \begin{itemize} @@ -226,7 +247,7 @@ Cette algorithmes évalue l'espérence empirique de $C(\theta)$ sur chaque élé 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} il y $28\%$ de points positif représenté en rouge. - Cela explique la différence entre \textit{accuracy} et \textit{balanced accuracy} à seuil égale. + Cela explique la différence entre exactitude et exactitude équilibrée à seuil égale. \subsection{Apprentissage profond} @@ -292,16 +313,22 @@ Ainsi la $i$-ième couche s'écrit : \end{equation*} Regardon maintenant les couches de convolutions. -L'idée de la convolution est d'extraire des représentations\footnote{\textit{Features extraction}}. +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. +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$ \begin{equation} f_i(x,\theta_i) = \left\{ \begin{matrix} - \mathbb{N}^\mathbb{}\rightarrow\mathbb{N}^\mathbb{N}\\ - u\mapsto\int_{\mathbb{N}}x(u\bowtie t)\theta(\#J\bowtie t)d\sum_{j\in\mathbb{N}}\delta_j(t) + \mathbb{R}^o\rightarrow\mathbb{R}^\mathbb{N}\\ + 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}}. diff --git a/background/opti.tex b/background/opti.tex index 9d346d6..03d01a6 100644 --- a/background/opti.tex +++ b/background/opti.tex @@ -1,4 +1,4 @@ -L'optimisation est une branche est des mathématiques appliquées qui cherche à trouver les points pour lequels une fonctions réalise un certain nombre d'exigence. +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. @@ -6,11 +6,34 @@ Cela permet l'entraînement de modèle d'apprantissage automatique à l'aide d'u 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{Descente de gradient} +\subsubsection{Optimisation sant 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. +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 $J(x_k)$ soit strictement décroissante ($\forall k\in\mathbb{N}~J(x_{k+1})