diff options
author | Jan Aalmoes <jan.aalmoes@inria.fr> | 2024-09-04 00:12:49 +0200 |
---|---|---|
committer | Jan Aalmoes <jan.aalmoes@inria.fr> | 2024-09-04 00:12:49 +0200 |
commit | 0e95544f85b523a95fb05b36c4e6b8789c73abfa (patch) | |
tree | 4229bad597b487e2395a2fc91e7023c6672bb29d | |
parent | dc5a898dc39326fa3f733f3d9e006bbe3d1f8e4c (diff) |
traduction classification fini
26 files changed, 600 insertions, 245 deletions
diff --git a/background/figure/ml/convex/conv_local.pdf b/background/figure/ml/convex/conv_local.pdf Binary files differnew file mode 100644 index 0000000..ca1717b --- /dev/null +++ b/background/figure/ml/convex/conv_local.pdf diff --git a/background/figure/ml/convex/f_local3.1.pdf b/background/figure/ml/convex/f_local3.1.pdf Binary files differnew file mode 100644 index 0000000..52d5e5c --- /dev/null +++ b/background/figure/ml/convex/f_local3.1.pdf diff --git a/background/figure/ml/convex/f_local8.28.pdf b/background/figure/ml/convex/f_local8.28.pdf Binary files differnew file mode 100644 index 0000000..817a7c3 --- /dev/null +++ b/background/figure/ml/convex/f_local8.28.pdf diff --git a/background/figure/ml/roc.pdf b/background/figure/ml/roc.pdf Binary files differnew file mode 100644 index 0000000..81888f0 --- /dev/null +++ b/background/figure/ml/roc.pdf diff --git a/background/figure/ml/roc_perfect.pdf b/background/figure/ml/roc_perfect.pdf Binary files differnew file mode 100644 index 0000000..9e7d294 --- /dev/null +++ b/background/figure/ml/roc_perfect.pdf diff --git a/background/figure/ml/roc_random.pdf b/background/figure/ml/roc_random.pdf Binary files differnew file mode 100644 index 0000000..06957d7 --- /dev/null +++ b/background/figure/ml/roc_random.pdf diff --git a/background/figure/opti/conv.pdf b/background/figure/opti/conv.pdf Binary files differnew file mode 100644 index 0000000..0e78124 --- /dev/null +++ b/background/figure/opti/conv.pdf diff --git a/background/figure/opti/f.pdf b/background/figure/opti/f.pdf Binary files differnew file mode 100644 index 0000000..489ce5f --- /dev/null +++ b/background/figure/opti/f.pdf 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} @@ -33,8 +33,101 @@ note={Dernier accès: 2024-08-29} } +#Optimisation +@BOOK{ciarlet, + title = "Introduction {\`a} l'an{\'a}lyse num{\'e}rique matricielle et + {\`a} l'optimisation: cours et exercices corrig{\'e}s", + author = "Ciarlet, Philippe G", + year = 2006, + language = "fr" +} + + + #Machine learning +@article{bottou1991stochastic, + title={Stochastic gradient learning in neural networks}, + author={Bottou, L{\'e}on and others}, + journal={Proceedings of Neuro-N{\i}mes}, + volume={91}, + number={8}, + pages={12}, + year={1991}, + publisher={Nimes} +} + +@incollection{bottou2012stochastic, + title={Stochastic gradient descent tricks}, + author={Bottou, L{\'e}on}, + booktitle={Neural Networks: Tricks of the Trade: Second Edition}, + pages={421--436}, + year={2012}, + publisher={Springer} +} + +@article{amari1993back, + title={Backpropagation and stochastic gradient descent method}, + author={Amari, Shun-ichi}, + journal={Neurocomputing}, + volume={5}, + number={4-5}, + pages={185--196}, + year={1993}, + publisher={Elsevier} +} + +@article{kumari2017machine, + title={Machine learning: A review on binary classification}, + author={Kumari, Roshan and Srivastava, Saurabh Kr}, + journal={International Journal of Computer Applications}, + volume={160}, + number={7}, + year={2017}, + publisher={Foundation of Computer Science} +} +@article{li2020statistical, + title={Statistical hypothesis testing versus machine learning binary classification: Distinctions and guidelines}, + author={Li, Jingyi Jessica and Tong, Xin}, + journal={Patterns}, + volume={1}, + number={7}, + year={2020}, + publisher={Elsevier} +} +@article{canbek2022ptopi, + title={PToPI: A comprehensive review, analysis, and knowledge representation of binary classification performance measures/metrics}, + author={Canbek, G{\"u}rol and Taskaya Temizel, Tugba and Sagiroglu, Seref}, + journal={SN Computer Science}, + volume={4}, + number={1}, + pages={13}, + year={2022}, + publisher={Springer} +} + +@misc{insee1982parite, + howpublished={\url{https://www.insee.fr/fr/statistiques/4768237}}, + title={Les cadres : de plus en plus de femmes}, + author={Forment, Virginie and Vidalenc, Joëlle}, + note={Dernier accès: 2024-08-26} +} + +@article{chicco2021matthews, + title={The Matthews correlation coefficient (MCC) is more reliable than balanced accuracy, bookmaker informedness, and markedness in two-class confusion matrix evaluation}, + author={Chicco, Davide and T{\"o}tsch, Niklas and Jurman, Giuseppe}, + journal={BioData mining}, + volume={14}, + pages={1--22}, + year={2021}, + publisher={Springer} +} + + + + + + @@ -531,6 +624,14 @@ series = {AIES '18} note={Dernier accès: 2024-08-05} } +@misc{aiact, + howpublished={\url{https://eur-lex.europa.eu/eli/reg/2024/1689/oj}}, + + note={Dernier accès: 2024-09-02}, + title={Regulation (EU) 2024/1689 of the European Parliament and of the Council of 13 June 2024 laying down harmonised rules on artificial intelligence and amending Regulations (EC) No 300/2008, (EU) No 167/2013, (EU) No 168/2013, (EU) 2018/858, (EU) 2018/1139 and (EU) 2019/2144 and Directives 2014/90/EU, (EU) 2016/797 and (EU) 2020/1828 (Artificial Intelligence Act) (Text with EEA relevance)} +} + + ######################################### #Philosophie diff --git a/classification_finie/finit_classif.tex b/classification_finie/finit_classif.tex index 44aa173..f518cdc 100644 --- a/classification_finie/finit_classif.tex +++ b/classification_finie/finit_classif.tex @@ -1,21 +1,21 @@ \subsection{Notations} -\begin{itemize} - \item $(x_0,x_1,\cdots,x_n)\in X_0\times X_1 \times\cdots\times X_n$ - \item If $A$ is a finite set, then $\# A$ denotes the cardinal number of $A$ - \item $f:\left\{\begin{matrix}A&\rightarrow &B\\ a&\mapsto & f(b)\end{matrix}\right.$ - Denotes a function from $A$ to $B$ mapping each element $a$ in $A$ to $f(a)$ in $B$. - \item $f\circ g$ is the composition of $f$ and $g$. - \item $f^{-1}$ can be either the inverse function of $f$ if $f$ is a bijection or its inverse image otherwise. -\end{itemize} +%\begin{itemize} + %\item $(x_0,x_1,\cdots,x_n)\in X_0\times X_1 \times\cdots\times X_n$ + %\item If $A$ is a finite set, then $\# A$ denotes the cardinal number of $A$ + %\item $f:\left\{\begin{matrix}A&\rightarrow &B\\ a&\mapsto & f(b)\end{matrix}\right.$ + % Denotes a function from $A$ to $B$ mapping each element $a$ in $A$ to $f(a)$ in $B$. + %\item $f\circ g$ is the composition of $f$ and $g$. + %\item $f^{-1}$ can be either the inverse function of $f$ if $f$ is a bijection or its inverse image otherwise. +%\end{itemize} \subsection{Problem setup} -We dispose of two finite sets, a feature space $E$ and a classification space $F$. -The cardinal numbers of $E$ and $F$ are respectively $m\in\mathbb{N}^*$ and $n\in\mathbb{N}^*$. -Let $\varphi$ be a bijection from $E$ to $[|0,m-1|]$ and $\psi$ be a bijection from $F$ to $[|0,n-1|]$. -We also dispose of a $o$-tuple $d: [|0,o-1] \rightarrow E\times F$. -In machine learning we would say that $d$ models a dataset. -We build the "dataset of indices" as such : +Nous nous donnons deux ensembles finits, un ensemble $E$ de données d'entrée et un espace d'étiquette $F$. +Nous notons $m=\#E$ et $n=\#F$. +Soit $\varphi$ une bijection de $E$ dans $[|0,m-1|]$ et $psi$ une bijection de $F$ dans $[|0,n-1|]$. +Nous supposons que nous avons un $o$-uplet $d: [|0,o-1] \rightarrow E\times F$. +$d$ modélise une jeu de donnée en pratique comme il est utilisé en apprantissage automatique. +Nous pouvons alors construire un jeu de donnée d'indices : \begin{equation*} d' : \left\{ \begin{matrix} @@ -27,31 +27,33 @@ We build the "dataset of indices" as such : \begin{definition} \label{def:BA} - The balanced accuracy of $f$ on the $o$-tuple $d$ relatively to the set $F$, $BA_F^d(f)$, is a number in $[0,1]$ such that + La \textit{balanced accuracy} empirique de $f$ sur le $o$-uplet $d$ relativements à $F$, que l'on appelle $BA_F^d(f)$, est un nombre dans $[0,1]$ tel que \begin{equation*} BA_F^d(f) = \frac{1}{n} \sum_{y\in F} \frac{ - \#\left\{j\in [|0,o-1|]\quad| f(d_0(j))=d_1(j)\text{ and }d_1(j) = y\right\} + \#\left\{j\in [|0,o-1|]\quad| f(d_0(j))=d_1(j)\wedge d_1(j) = y\right\} } {\#\{j\in [|0,o-1|]\quad| d_1(j)=y\}} \end{equation*} - \end{definition} -\textbf{The problem consists in finding an application $f:E\rightarrow F$ such that the balanced accuracy of $f$ on $d$ is maximal.} +Cette définition est un approximation de la \textit{balanced accuracy} qui nous avons définit plus haut. +\textbf{Le problème consiste à trouver une application $f:E\rightarrow F$ telle que la \textit{balanced accuracy} de $f$ sur $d$ et maximal.} + +\subsection{D'un proclème sur les élément à un problème sur les indices} -\subsection{From a problem on elements to a problem on indices} -We call the set of functions from $E$ to $F$, $B_{E\rightarrow F}$. -To simplify notation, the set of function from $[|0,m-1|]$ to $[|0,n-1|]$ we call it $B_{m\rightarrow n}$. +Nous commencons par noter par $B_{E\rightarrow F}$ l'ensemble des fonctions de $E$ dans $F$. +Pour simplifier un peu les notations, nous appelerons $B_{m\rightarrow n}$ l'ensemble des fnoctins de $[|0,m-1|]$ dans $[|0,n-1|]$. \begin{theorem} \label{th:bij} - Let $E$ and $F$ be two finite sets of cardinal numbers $m$ and $n$. There exists a bijection from $B_{E\rightarrow F}$ to $B_{m\rightarrow n}$. + Soient $E$ et $F$ deux ensemble finis de cardinaux $m$ et $n$. + Il existe une bijection de $B_{E\rightarrow F}$ dans $B_{m\rightarrow n}$. \end{theorem} \begin{proof} - We proceed by expliciting such a bijection. - Let + Nous procédons en explicitant une telle bijection. + Soit \begin{equation} \Phi :\left\{ \begin{matrix} @@ -61,10 +63,10 @@ To simplify notation, the set of function from $[|0,m-1|]$ to $[|0,n-1|]$ we cal \right. \end{equation} - Let's show that $\Phi$ is an injection. - Let $(u,v)\in \left(B_{E\rightarrow F}\right)^2$ such that + Montrons maintenant que $\Phi$ est un bijection. + Soit $(u,v)\in \left(B_{E\rightarrow F}\right)^2$ telle que $\Phi(u) = \Phi(v)$. - Then + Alors \begin{align*} & \psi\circ u\circ\varphi^{-1} = \psi\circ v\circ\varphi^{-1}\\ \Leftrightarrow& \psi^{-1}\circ\psi\circ u\circ\varphi^{-1} = \psi^{-1}\circ\psi\circ v\circ\varphi^{-1}\\ @@ -72,53 +74,57 @@ To simplify notation, the set of function from $[|0,m-1|]$ to $[|0,n-1|]$ we cal \Leftrightarrow&u\circ\varphi^{-1}\circ\varphi = v\circ\varphi^{-1}\circ\varphi\\ \Leftrightarrow&u = v\\ \end{align*} - Hence $\Phi$ is injective. Let's show that $\Phi$ is surjective. - Let $g\in B_{m\rightarrow n}$. - Then + Ainsi $\Phi$ est injective. + + Montrons maintenant que $\Phi$ est surjective. + Soit $g\in B_{m\rightarrow n}$. + Alors $\Phi(\psi^{-1}\circ g\circ\varphi) = \psi\circ\psi^{-1}\circ g\circ\varphi\circ\varphi^{-1} = g$ - Hence $\Phi$ is surjective. - In conclusion $\Phi$ is both injective and surjective: it is a bijection. + Ainsi $\Phi$ est surjective. + + En conclusion $\Phi$ est à la fois injéctive et surjéctive : c'est une bijection. \end{proof} -$\varphi$ and $\psi$ can be seen as indices on $E$ and $F$. -For instance, each element $e$ in $E$ has a unique index $\varphi(e)$. -This abstraction step allows us to build explicit functions from $E$ to $F$ without taking into consideration the type of mathematical object that contains those sets. - Indeed, theorem \ref{th:bij} gives us that for each function mapping indices of $E$ to indices on $F$ we can find a unique function from $E$ to $F$. - And the proof even gives us how to find it: by using $\Phi^{-1}$. +$\varphi$ et $\psi$ peuvent être vus comme des indives sur $E$ et $F$. +Par exemple, chaque élément $e$ dans $E$ a un unqiue index $\varphi(e)$. +Cette étape d'abstraction nous permet de contruire des fonctions explicites de $E$ dans $F$ sans prendre en comptes les spécificités de objets mathématiques dans ses ensembles. +En effet, le théorème~\ref{th:bij} nous donne que pour chaque fonction des indices de $E$ vers les indices de $F$ nous pouvons trouver une unique fonction de de $E$ dans $F$. +Et la preuve étant constructive nous indique que pour trouver cette fonction nous pouvons utiliser $\Phi^{-1}$. - Let's now explore how the balanced accuracy behaves when composing with $\Phi$. + Etudions donc comment se comporte la \textit{balanced accuracy} quand on compose avec $\Phi$. \begin{theorem} \label{th:BAphi=BA} - Let $E$ and $F$ two finite sets. - Let $d$ a tuple of $E\times F$. - We have the following equality + Soit $E$ et $F$ deux ensembles finis. + Soit $d$ un uplet de $E\times F$. + Alors nous avons l'égalitée suivante : \begin{equation*} BA^{d'}_{[|0,\#F-1|]}\circ\Phi = BA^d_F \end{equation*} \end{theorem} \begin{proof} - Let $E$ and $F$ two finite sets. + Soit $E$ et $F$ deux ensemle finis. + Nous avons deux bijections : We have two bijections : - $\varphi$ from E to $[|0,\#E-1|]$ and - $\psi$ from F to $[|0,\#F-1|]$. - With those two functions we build a third bijection - $\Phi$ from $B_{E\rightarrow F}$ to $B_{\#E\rightarrow \#F }$ similarly as in the proof of theorem \ref{th:bij}. - Let $o\in\mathbb{N}^*$ and $d$ a $o$-tuple of $E\times F$. + $\varphi$ de $E$ dans $[|0,\#E-1|]$ et + $\psi$ de $F$ dans $[|0,\#F-1|]$. + Avec ces deux fonctions nous allons contruire une troisième bijections + $\Phi$ de $B_{E\rightarrow F}$ dans $B_{\#E\rightarrow \#F }$ similaire à celle de la preuve du théorème~\ref{th:bij}. + Soient $o\in\mathbb{N}^*$ et $d$ un $o$-uplet de $E\times F$. - Let $f\in B_{E\rightarrow F}$ - then + Soit $f\in B_{E\rightarrow F}$ + alors \begin{equation} \label{eq:BAdp} \left(BA^{d'}_{[|0,\#F-1|]}\circ\Phi\right)(f) = \frac{1}{\#F} \sum_{i=0}^{\#F-1}\frac{ - \#\left\{j\in[|0,o-1|]\quad | \Phi(f)(d'_0(j))=d'_1(j)\text{ and }d'_1(j)=i\right\}} + \#\left\{j\in[|0,o-1|]\quad | \Phi(f)(d'_0(j))=d'_1(j)\wedge d'_1(j)=i\right\}} {\#\left\{j\in[|0,o-1|]\quad | d'_1(j)=i\right\}}\\ \end{equation} - We also remark that + Nous remarquons aussi que \begin{equation*} \Phi(f)\circ d'_0= \psi\circ f\circ\varphi^{-1}\circ d'_0 = @@ -126,7 +132,7 @@ This abstraction step allows us to build explicit functions from $E$ to $F$ with \psi\circ f\circ d_0 \end{equation*} - Hence, let $j\in[|0,o-1|]$ + Ainsi, soit $j\in[|0,o-1|]$ \begin{align*} &\left(\Phi(f)\circ d'_0\right)(j) = d'_1(j)\\ \Leftrightarrow &\left(\psi\circ f\circ d_0\right)(j)= d'_1(j)\\ @@ -134,7 +140,7 @@ This abstraction step allows us to build explicit functions from $E$ to $F$ with \Leftrightarrow &\left(f\circ d_0\right)(j) = d_1(j)\\ \end{align*} - Which gives us the following assertion: + Ce qui nous donnes les assertions suivantes : \begin{equation} \label{eq:d1j} \forall j\in[|0,o-1|]\quad @@ -145,7 +151,7 @@ This abstraction step allows us to build explicit functions from $E$ to $F$ with \right] \end{equation} - Let's now do the same work of switching from indices to elements on "$d'_1(j) = i$". + De même, passons des indices aux élements sur "$d'_1(j) = i$". Let $i\in[|0,\#F-1|]$ and $j\in[|0,o-1|]$. \begin{align*} &d'_1(j) = i\\ @@ -153,30 +159,30 @@ This abstraction step allows us to build explicit functions from $E$ to $F$ with \Leftrightarrow & d_1(j) = \psi^{-1}(i) \end{align*} - Hence from equations \ref{eq:BAdp} and \ref{eq:d1j} we obtain - - \begin{align*} + Ansin avec les equations \ref{eq:BAdp} et \ref{eq:d1j} nous obtenons + \begin{align} &\left(BA^{d'}_{[|0,\#F-1|]}\circ\Phi\right)(f) = \frac{1}{\#F} \sum_{y=0}^{\#F-1}\frac{ - \#\left\{j\in[|0,o-1|]\quad | f(d_0(j))=d_1(j)\text{ and }d_1(j)=\psi^{-1}(i)\right\}} - {\#\left\{j\in[|0,o-1|]\quad | d_1(j)=\psi^{-1}(i)\right\}}\\ + \#\left\{j\in[|0,o-1|]\quad | f(d_0(j))=d_1(j)\wedge d_1(j)=\psi^{-1}(i)\right\}} + {\#\left\{j\in[|0,o-1|]\quad | d_1(j)=\psi^{-1}(i)\right\}}\\\nonumber &= \frac{1}{\#F} \sum_{y=\psi^{-1}(0),\cdots,\psi^{-1}(\#F-1)}\frac{ - \#\left\{j\in[|0,o-1|]\quad | f(d_0(j))=d_1(j)\text{ and }d_1(j)=y\right\}} - {\#\left\{j\in[|0,o-1|]\quad | d_1(j)=y\right\}}\\ + \#\left\{j\in[|0,o-1|]\quad | f(d_0(j))=d_1(j)\wedge d_1(j)=y\right\}} + {\#\left\{j\in[|0,o-1|]\quad | d_1(j)=y\right\}}\\\nonumber &= \frac{1}{\#F} \sum_{y\in F}\frac{ - \#\left\{j\in[|0,o-1|]\quad | f(d_0(j))=d_1(j)\text{ and }d_1(j)=y\right\}} + \#\left\{j\in[|0,o-1|]\quad | f(d_0(j))=d_1(j)\wedge d_1(j)=y\right\}} {\#\left\{j\in[|0,o-1|]\quad | d_1(j)=y\right\}}\\ - \end{align*} + \label{eq:fini-egaba} + \end{align} - The final quantity in this sequence of equalities is equal to $BA_F^d(f)$ according to definition \ref{def:BA}. + D'après la définition~\ref{def:BA} l'experession~\ref{eq:fini-egaba} est égale à $BA_F^d(f)$ \end{proof} -Using theorem \ref{th:BAphi=BA} we can deduce the following result which will be key to finding $\text{argmax}\left(BA_F^d\right)$. +En utilisant le théorème~\ref{th:BAphi=BA} nous déduisons le corollère suivant qui jouera un rôle clé dans le recherche de la solution à $\text{argmax}\left(BA_F^d\right)$. \begin{corollary} \label{co:argmax} @@ -187,41 +193,41 @@ Using theorem \ref{th:BAphi=BA} we can deduce the following result which will be \end{corollary} \begin{proof} - Let $f' = \text{argmax}\left(BA_{[|0,\#F-1|]}^{d'}\right)$. - Then for all $g$ in $B_{E\rightarrow F}$, + Soit $f' = \text{argmax}\left(BA_{[|0,\#F-1|]}^{d'}\right)$. + Alors, pour tout $g$ dans $B_{E\rightarrow F}$, $BA_F^d(g) = BA_{[|0,\#F-1|]}^{d'}(\Phi(g)) \leq BA_{[|0,\#F-1|]}^{d'}(f') = BA_F^d(\Phi^{-1}(f'))$ \end{proof} -With corollary \ref{co:argmax} we have that, to solve the classification problem on any dataset, it is sufficient to solve on one of the corresponding indices dataset. -The focus of the next section is on finding an algorithm to solve such a problem. +Grâce au corollère~\ref{co:argmax} nous avons que, pour résoudres le problème de classification sur n'importe quel ensemble, il est suffisant de le résoudre sur l'ensemble d'indices correspondant. +L'objetif de la prochaine section est donc la recherche d'un algortihme de résolution d'un tel problème. -\subsection{Building a classification algorithm on $B_{m\rightarrow n}$} -Let $m$, $n$ and $o$ be natural numbers greater than zero. -We take $d$, a $o$-tuple of $[|0,m-1|]\times[|0,n-1|]$. -Since we already know that we are going to work on indices, we don't bother with the general sets $E$ and $F$ from the previous section. -Instead we use $E=\{0,1,\cdots,m-1\}$ and $F=\{0,1,\cdots,n-1\}$. +\subsection{Contruiction d'un algorithme de classification sur $B_{m\rightarrow n}$} -The direct approach to find an algorithm that maximizes $BA_{[|0,n-1|]}^d$ would be to compute the balanced accuracy for every function of $B_{m\rightarrow n}$. -This method works fine for small values of $m$ and $n$ but becomes quickly impossible to compute as those values increase. -Indeed, we know from combinatorics that $B_{m\rightarrow n}$ contains $n^m$ elements. -It results in an algorithm with a number of $\mathcal{O}(on^m)$ operations. -Instead, we propose an algorithm in $\mathcal{O}(onm)$ operations. +Soient $m$, $n$ et $p$ des entiers naturels non-nuls. +Soit aussi $d$, un $o$-uplet de $[|0,m-1|]\times[|0,n-1|]$. +Come nous savons que nous allons travailler sur les indices, nous ne nous préocupons pas d'ensembles quelconqus $E$ et $F$ comme à la section précedente. +A la place nous prenons $E=\{0,1,\cdots,m-1\}$ and $F=\{0,1,\cdots,n-1\}$. -To build it we are going to "distribute" the argmax operator, simplifying the expression of the optimal balanced accuracy. -This distribution requires to find an expression of the balanced accuracy that is context-wise more appropriate. -We express this alternative form of the balanced accuracy in the following lemma. +L'aproche la plus directe pour maximiser $BA_{[|0,n-1|]}^d$ serait l'algorithme qui consiste à essayer de calculer la \textit{balanced accuracy} pour toutes les fonctions de $B_{m\rightarrow n}$. +Cette methode est viable pour des petites valeures de $m$ et $n$ mais devient rapidement impossible à calculer pour des grandes valeures. +En effet, par denombrement nous savons que $B_{m\rightarrow n}$ contiens $n^m$ éléments. +L'algorithme directe à donc une complexite de $\mathcal{O}(on^m)$ operations. +Nous allons construire à la place un algoritheme que garantie de maximiser la \textit{balanced accuracy} en $\mathcal{O}(onm)$ operations. + +Pour le constuire nous allons, d'une certaine manière, distribuer l'opératuer argmax, simplifiant ainsi l'expression de la \textit{balanced accuracy} optimale. +Pour cela, dans le lemme qui suit nous allons reformuler la \textit{balanced accuracy}. \begin{lemma} \label{lem:sumei} - For every $i$ in $[|0,m-1|]$, we introduction the following $n$-tuple: + Pour tout $i$ dans $[|0,m-1|]$, nous definissons le $n$-uplet suivant. \begin{equation*} e_i:\left\{ \begin{matrix} [|0,n-1|]&\longrightarrow&\mathbb{N}\\ l&\mapsto& \frac{ - \#\{j\in[|0,o-1|]\quad| d_0(j)=i\text{ and }d_1(j)=l\} + \#\{j\in[|0,o-1|]\quad| d_0(j)=i\wedge d_1(j)=l\} }{ \#\{j\in[|0,o-1|]\quad| d_1(j)=l\} }\\ @@ -229,7 +235,7 @@ We express this alternative form of the balanced accuracy in the following lemma \right. \end{equation*} - Then we can write the balanced accuracy as: + Nous pouvons alors écrir la \textit{balanced accuracy} de la manière suivant : \begin{equation*} BA_{[|0,n-1|]}^d(h) = \frac{1}{n} \sum_{i=0}^{m-1} e_i(h(i)) @@ -237,17 +243,17 @@ We express this alternative form of the balanced accuracy in the following lemma Where $h\in B_{m\rightarrow n}$. \end{lemma} \begin{proof} - Let $l\in[|0,n-1|]$ and $h$, a function in $B_{m\rightarrow n}$. + Soit $l\in[|0,n-1|]$ et $h$, une fonction dans $B_{m\rightarrow n}$. \begin{align*} & \frac{ - \#\{j\in[|0,o-1|]\quad| h(d_0(j))=d_1(j)\text{ and }d_1(j)=l\} + \#\{j\in[|0,o-1|]\quad| h(d_0(j))=d_1(j)\wedge d_1(j)=l\} }{ \#\{j\in[|0,o-1|]\quad| d_1(j)=l\} }\\ =& \frac{ - \#\{j\in[|0,o-1|]\quad| h(d_0(j))=l\text{ and }d_1(j)=l\} + \#\{j\in[|0,o-1|]\quad| h(d_0(j))=l\wedge d_1(j)=l\} }{ \#\{j\in[|0,o-1|]\quad| d_1(j)=l\} } @@ -255,7 +261,7 @@ We express this alternative form of the balanced accuracy in the following lemma \begin{align*} =& \frac{ - \#\{j\in[|0,o-1|]\quad| h(d_0(j))=l\text{ and }d_1(j)=h(d_0(j))\} + \#\{j\in[|0,o-1|]\quad| h(d_0(j))=l\wedge d_1(j)=h(d_0(j))\} }{ \#\{j\in[|0,o-1|]\quad| d_1(j)=l\} } @@ -270,17 +276,18 @@ We express this alternative form of the balanced accuracy in the following lemma } \end{align} - In the previous expression, $l$ refers to an element of the label set $F$. - To prove the result we substitute in equation \ref{eq:sansi} $h(d_0(j))$ by an expression containing $i$: an element of $E$. - The end goal is to exhibit the quantity of interest $e_{i,j}$. - We first remark that for all $j$ in $[|0,o-1|]$ + Dans l'expression précédente, $l$ est un élément de l'ensemble des indeices $F$. + Pour montrer le résultat, on remplace $h(d_0(j))$~\ref{eq:sansi} par une expression qui contient $i$ : un élément de $E$. + Le but de faire aparaitre la quantité qui nous intersse : $e_{i,j}$. + + Nous commencons par remarquer que pour tout $j$ dans $[|0,o-1|]$ \begin{equation*} h(d_0(j))=l \Leftrightarrow d_0(j)\in h^{-1}(\{l\}) \Leftrightarrow \exists i\in h^{-1}(\{l\}), d_0(j)=i \end{equation*} - Which means that + Ce qui signifie que \begin{align*} &\left\{ j\in[|0,o-1|]\quad| h(d_0(j)) = l @@ -294,7 +301,7 @@ We express this alternative form of the balanced accuracy in the following lemma \right\} \end{align*} - Hence, by substitution of $\{j\in[|0,o-1|]\quad| h(d_0(j)) = l\}$ en equation \ref{eq:sansi}, we obtain + Aninsi, par substitution de $\{j\in[|0,o-1|]\quad| h(d_0(j)) = l\}$ dans l'équation \ref{eq:sansi}, nous obtenons \begin{align*} &\frac{ \#\left( @@ -314,7 +321,7 @@ We express this alternative form of the balanced accuracy in the following lemma \bigcup_{i\in h^{-1}(\{l\})} \left\{ j\in[|0,o-1|]\quad| d_0(j)=i - \text{ and } + \wedge d_1(j)=h(d_0(j)) \right\} \right) @@ -325,7 +332,7 @@ We express this alternative form of the balanced accuracy in the following lemma \frac{ \#\left\{ j\in[|0,o-1|]\quad| d_0(j)=i - \text{ and } + \wedge d_1(j)=h(i) \right\} }{ @@ -338,17 +345,17 @@ We express this alternative form of the balanced accuracy in the following lemma e_i(h(i)) \end{align} - Then, according to definition \ref{def:BA} + Ensuite, d'après la définition~\ref{def:BA} \begin{equation*} BA_{[|0,n-1|]}^d(h) = \frac{1}{n} \sum_{l=0}^{n-1} \frac{ - \#\left\{j\in [|0,o-1|]\quad| h(d_0(j))=d_1(j)\text{ and }d_1(j) = l\right\} + \#\left\{j\in [|0,o-1|]\quad| h(d_0(j))=d_1(j)\wedge d_1(j) = l\right\} } {\#\{j\in [|0,o-1|]\quad| d_1(j)=l\}} \end{equation*} - We substitute the general term of this sum by the result obtained in equation \ref{eq:sumei}: + Par substitution du terme générale de cette somme par le résultat obtenu dans l'équation~\ref{eq:sumei} : \begin{align*} &BA_{[|0,n-1|]}^d(h)\\ =&\frac{1}{n} @@ -359,82 +366,82 @@ We express this alternative form of the balanced accuracy in the following lemma \sum_{i=0}^{m-1} e_i(h(i))\sum_{l=0}^{n-1}1_{h^{-1}(\{l\})}(i)\\ \end{align*} - Since $1_{h^{-1}(\{l\})}(i) = 1$ if and only if $l=h(i)$, + Comme $1_{h^{-1}(\{l\})}(i) = 1$ si et seulement si $l=h(i)$, nous avons $\sum_{l=0}^{n-1}1_{h^{-1}(\{l\})}(i) = 1$. - - Hence we have the expected result. + Ce qui donne le résultat attendu. \end{proof} -This lemma allows us to shift the computing of the argmax from all possible functions of $B_{m\rightarrow n}$ to the entries of the matrix $M = \left(e_i(l)\right)_{i\in[|0,m-1|],l\in[|0,m-1|]}$. -More precisely, we find the maximum of each row of $M$ resulting in parcouring once every element of $M$. -We formalise this idea in the following theorem. +Ce lemme nous permet de calculer l'argmax souhaité en calculant le entrée de la matrice $M = \left(e_i(l)\right)_{i\in[|0,m-1|],l\in[|0,m-1|]}$ +au lieu de calcule la \textit{balanced accuracy} de toutes le fonctions de $B_{m\rightarrow n}$. +Nous cherchons donc le maximum de chaque ligne de $M$ ce qui fait que nous n'avons qu'a parcourir une fois chaque élément de $M$. +Nous formalisons cette idée dans le théorème suivant : \begin{theorem} - Let $e_i$ be the following $n$-tuples of $\mathbb{N}$: + Soit $e_i$ le $n$-uplet de $\mathbb{N}$ suivant : \begin{equation*} e_i:\left\{ \begin{matrix} [|0,n-1|]&\longrightarrow&\mathbb{N}\\ l&\mapsto& \frac{ - \#\{j\in[|0,o-1|]\quad| d_0(j)=i\text{ and }d_1(j)=l\} + \#\{j\in[|0,o-1|]\quad| d_0(j)=i\wedge d_1(j)=l\} }{ \#\{j\in[|0,o-1|]\quad| d_1(j)=l\} }\\ \end{matrix} \right. \end{equation*} - Let $f\in B_{m\rightarrow n}$ such that for all $i$ in $[|0,m-1|]$ + Soit $f\in B_{m\rightarrow n}$ telle que pour tout $i$ dans $[|0,m-1|]$ \begin{equation*} f(i) = \text{argmax}\left(e_i\right) \end{equation*} - Then + Alors \begin{equation*} f = \text{argmax}\left(BA_{[|0,n-1|]}^d\right) \end{equation*} \end{theorem} \begin{proof} - Let $g\in B_{m\rightarrow n}$. - We are going to show that $BA_{[|0,n-1|]}^d(g)\leq BA_{[|0,n-1|]}^d(f)$. - We start by saying that - for all $i\in[|0,n-1|]$, $0\leq e_i(g(i))\leq e_i(f(i))$. - Which gives us that + Soit $g\in B_{m\rightarrow n}$. + Nous allons montrer que $BA_{[|0,n-1|]}^d(g)\leq BA_{[|0,n-1|]}^d(f)$. + Nous commencons par dire que + pour tout $i\in[|0,n-1|]$, $0\leq e_i(g(i))\leq e_i(f(i))$. + Ce qui donne que \begin{equation*} \sum_{i=0}^{m-1}e_i(g(i)) \leq \sum_{i=0}^{m-1}e_i(f(i)) \end{equation*} - and hence + et donc \begin{equation*} \frac{1}{n}\sum_{i=0}^{m-1}e_i(g(i)) \leq \frac{1}{n}\sum_{i=0}^{m-1}e_i(f(i)) \end{equation*} - And finally, according to lemma \ref{lem:sumei} we have the result. + Enfin, en appliquant le lemme~\ref{lem:sumei} nous avons le résultat attedu. \end{proof} -According to this result, we can write the following algorithm in $\mathcal{O}(onm)$ to solve our optimisation problem. +En utiliant ce résulat, nous pouvons maintenant écrir l'algorithm suivant en $\mathcal{O}(onm)$ pour résoudre notre problème d'optimisation. \begin{algorithm} - \caption{Optimisation: finding $\text{argmax}\left(BA^d_{[|0,n-1|]}\right)$} + \caption{Optimisation: recherche de l'$\text{argmax}\left(BA^d_{[|0,n-1|]}\right)$} \label{algo:argmax} \begin{algorithmic} \For{$i\gets 0,\cdots,m-1$} \For{$l\gets 0,\cdots,n-1$} \State $e_{i,l}\gets \frac{ - \#\{j\in[|0,o-1|]\quad | d_0(j)=i\text{ and }d_1(j)=l\} + \#\{j\in[|0,o-1|]\quad | d_0(j)=i\wedge d_1(j)=l\} }{ \#\{j\in[|0,o-1|]\quad | d_1(j)=l\} }$ \footnotesize - \Comment{Compute $e_i(l)$} + \Comment{Calcul de $e_i(l)$} \normalsize \EndFor \EndFor \For{$i\gets 0,\cdots,n-1$} \State $f(i)\gets\text{argmax}_l(e_{i,l})$ \footnotesize - \Comment{Value of $l$ that maximizes $e_{i,l}$} + \Comment{Valeur de $l$ que maximise $e_{i,l}$} \normalsize \EndFor \State \Return $f$ @@ -443,16 +450,16 @@ According to this result, we can write the following algorithm in $\mathcal{O}(o \FloatBarrier \subsection{Extention to unseen data} -Alogrithm \ref{algo:argmax} is an efficient algorithm to find a classifier the maximizes balanced accuracy on the set of indices. -From the result $f$ of this alogrithm we find a classifier that solves the problem of maximizing the balanced accuracy on element by applying the inversse of $\Phi$. -Hence $\Phi^{-1}(f)$ is solution. -Computing it requires $\mathcal{O}(on)$ operations resulting in an overall complexity of $\mathcal{O}(onm)$. +%Alogrithm \ref{algo:argmax} is an efficient algorithm to find a classifier the maximizes balanced accuracy on the set of indices. +%From the result $f$ of this alogrithm we find a classifier that solves the problem of maximizing the balanced accuracy on element by applying the inversse of $\Phi$. +%Hence $\Phi^{-1}(f)$ is solution. +%Computing it requires $\mathcal{O}(on)$ operations resulting in an overall complexity of $\mathcal{O}(onm)$. -This classifier algorithm is limited to finite feature space but there are cases where we can find workaround to still use it. -For instance, by using clusturing prior to our method we can reduce to a finit feature space. -Also, if $(E, O)$ is a sub-topology we can match any element of the englobing set to its nearest counterpart in $E$. -We did that on LAW and COMPAS dataset and compare our approach to a random forest. +%This classifier algorithm is limited to finite feature space but there are cases where we can find workaround to still use it. +%For instance, by using clusturing prior to our method we can reduce to a finit feature space. +%Also, if $(E, O)$ is a sub-topology we can match any element of the englobing set to its nearest counterpart in $E$. +%We did that on LAW and COMPAS dataset and compare our approach to a random forest. -The main takeaway from figures \ref{fig:ba} and \ref{fig:time} is that our finite classifier alogirthm outperforms state of the art in terms of balanced accuracy and is way faster at achieving this result. +%The main takeaway from figures \ref{fig:ba} and \ref{fig:time} is that our finite classifier alogirthm outperforms state of the art in terms of balanced accuracy and is way faster at achieving this result. diff --git a/classification_finie/main.tex b/classification_finie/main.tex index 2f40530..91fdd27 100644 --- a/classification_finie/main.tex +++ b/classification_finie/main.tex @@ -1,67 +1,2 @@ -\documentclass{article} - -\usepackage{graphicx} -\usepackage{amsmath} -\usepackage{amsthm} -\usepackage{amsfonts} -\usepackage{algpseudocode} -\usepackage{algorithm} -\usepackage{placeins} -\usepackage{subcaption} -\usepackage{graphicx} -\usepackage{setspace} - -\newtheorem{definition}{Definition} -\newtheorem{theorem}{Theorem} -\newtheorem{lemma}{Lemma} -\newtheorem{corollary}{Corollary}[theorem] - -\doublespace - -\begin{document} -\begin{abstract} - The abstract -\end{abstract} -\tableofcontents -\newpage -\section{Introduction} -\input{introduction} - -\section{Finit classification} -\input{finit_classif} - -\section{Applications} -\input{utility} - \subsection{Attribute inference attack} - \subsection{Painting classification} - \subsection{Lora} - \subsection{Tabular data} - \input{tabular} - \subsection{Movie recommender system} - \subsection{labeled faces in the wild} - - -\section{Computing cost} - \subsection{Cost of training} - \subsection{Cost of inference} - -\section{Decentralization} - \subsection{Sharing indexes} - \subsection{Sharing matrix of probability law} - -\section{Privacy} - \subsection{Private indexing} - \subsection{Differential privacy} - -\section{Fairness} - \subsection{Preprocessing} - \subsection{Inprocessing and postprocessing} - -\section{Explainability} - \subsection{Transparancy} - \subsection{Interpretability} - \subsection{Explainability} - -\section{Conclusion} - -\end{document} +\input{classification_finie/ba} +\input{classification_finie/finit_classif} diff --git a/contexte/avertissement.tex b/contexte/avertissement.tex new file mode 100644 index 0000000..1c5d88f --- /dev/null +++ b/contexte/avertissement.tex @@ -0,0 +1,7 @@ +Ce manuscrit aborde des notions de discirimination notament de genre, d'origine et de couleur de peau. +En France, les statistiques éthnique sont intérdites~\cite{} ce qui n'est pas le cas aux USA. +Les résultats de statistiques descriptives, nottament sur les crimes comis en fonction de la couleur de peau, sont à mettre en parallèle avec un grand nombre de facteurs socio-économiques~\cite{} +Ainsi, ils ne doivent pas être interprété comme indiquant une différence de comportement social entre sous groupes ethniques. + +De plus, la Seciont~\ref{sec:contexte-phi} invite le lecteur à des expériences de pensées qui peuvent être angoissantes pour certaines personnes~\cite{}. +Nous invitons donc le lecteur à ne pas s'attarder sur cette section si il ne se juge pas émotionelement prêt. diff --git a/contexte/ckoi.tex b/contexte/ckoi.tex index 6663a5e..0dce14d 100644 --- a/contexte/ckoi.tex +++ b/contexte/ckoi.tex @@ -145,7 +145,7 @@ Ainsi, l'expression intelligence artificielle est trompeuse car bien que ces pro C'est pourquoit la définition de légale d'IA est si éloignée de ces considération. L'Union Européene a établie le règlement (UE) 2024/1689 du parlement européen et du conseil du 13 juin 2024 -établissant des règles harmonisées concernant l’intelligence artificielle. +établissant des règles harmonisées concernant l’intelligence artificielle~\cite{aiact}. Nous reviendrons plus en détail dessus dans la Section~\ref{sec:contexte-legal}. Pour le moment, regardons l'article 3: il s'agit d'une liste de définitions concernant l'IA. Nous y trouvons la définition de (UE 2024/1689 3§1) : \textquote{système IA}. diff --git a/contexte/figure/bad_ai.png b/contexte/figure/bad_ai.png Binary files differnew file mode 100644 index 0000000..5b2968e --- /dev/null +++ b/contexte/figure/bad_ai.png diff --git a/contexte/figure/chatgpt/penses.png b/contexte/figure/chatgpt/penses.png Binary files differnew file mode 100644 index 0000000..134665e --- /dev/null +++ b/contexte/figure/chatgpt/penses.png diff --git a/contexte/figure/tikz/function.tex b/contexte/figure/tikz/function.tex new file mode 100644 index 0000000..93d2a58 --- /dev/null +++ b/contexte/figure/tikz/function.tex @@ -0,0 +1,14 @@ +\begin{tikzpicture} + \node[rectangle,draw] (ia) at (0,0) {IA}; + \node (ent) at (-2,0) {Entrée}; + \node (sor) at (2,0) {Sorties}; + \node (par) at (0,-1) {Paramètres}; + + \draw[->] (ent) to (ia); + \draw[->] (ia) to (sor); + \draw[->] (par) to (ia); + + \node[align=left] (par) at (4,0) {Prédiction\\Décision\\Contenu}; + \draw [decorate,decoration = {brace}] (3,-0.6) -- (3,0.6); + +\end{tikzpicture} Binary files differ@@ -2,7 +2,9 @@ \usepackage[french]{babel} \usepackage{placeins} -\usepackage[draft]{graphicx} +%\usepackage[draft]{graphicx} +\usepackage{graphicx} +\usepackage{upgreek} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} @@ -45,7 +47,7 @@ breaklines=true \textbf{Jan Aalmoes} \large - Sous la "supervison" de \\ + Sous la supervison de \\ Antoine Boutet et Mathieu Cunche \vfill @@ -80,7 +82,7 @@ breaklines=true \chapter{Classification finie} \label{sec:fini} - \input{classification_finie/finit_classif} + \input{classification_finie/main} \chapter{Attaque d'inférence d'attribut sensible} diff --git a/theorem.tex b/theorem.tex index 0518a88..1021fc1 100644 --- a/theorem.tex +++ b/theorem.tex @@ -1,5 +1,6 @@ \newtheorem{definition}{Définition}[chapter] \newtheorem{theorem}{Théoreme}[chapter] +\newtheorem{propriete}{Propriété}[chapter] \newtheorem{lemma}[theorem]{Lemme} \newtheorem{corollary}{Corollère}[theorem] diff --git a/tikz_assets/data.tex b/tikz_assets/data.tex new file mode 100644 index 0000000..663b59c --- /dev/null +++ b/tikz_assets/data.tex @@ -0,0 +1,20 @@ +\makeatletter +\tikzset{ + database/.style={ + path picture={ + \draw (0, 1.5*\database@segmentheight) circle [x radius=\database@radius,y radius=\database@aspectratio*\database@radius]; + \draw (-\database@radius, 0.5*\database@segmentheight) arc [start angle=180,end angle=360,x radius=\database@radius, y radius=\database@aspectratio*\database@radius]; + \draw (-\database@radius,-0.5*\database@segmentheight) arc [start angle=180,end angle=360,x radius=\database@radius, y radius=\database@aspectratio*\database@radius]; + \draw (-\database@radius,1.5*\database@segmentheight) -- ++(0,-3*\database@segmentheight) arc [start angle=180,end angle=360,x radius=\database@radius, y radius=\database@aspectratio*\database@radius] -- ++(0,3*\database@segmentheight); + }, + minimum width=2*\database@radius + \pgflinewidth, + minimum height=3*\database@segmentheight + 2*\database@aspectratio*\database@radius + \pgflinewidth, + }, + database segment height/.store in=\database@segmentheight, + database radius/.store in=\database@radius, + database aspect ratio/.store in=\database@aspectratio, + database segment height=0.1cm, + database radius=0.25cm, + database aspect ratio=0.35, +} +\makeatother diff --git a/tikz_assets/param.tex b/tikz_assets/param.tex new file mode 100644 index 0000000..17df939 --- /dev/null +++ b/tikz_assets/param.tex @@ -0,0 +1,14 @@ +\makeatletter +\tikzset{ + param/.style={ + path picture={ + \fill[color=blue] (0,0) circle[radius=5pt]; + \fill[color=blue] (1,0) circle[radius=5pt]; + \fill[color=blue] (0,1) circle[radius=5pt]; + \fill[color=blue] (0.5,0) circle[radius=5pt]; + \fill[color=blue] (0,0.5) circle[radius=5pt]; + \fill[color=blue] (0.5,0.5) circle[radius=5pt]; + }, + }, +} +\makeatother |