From 4aae3ea0427a6c9e9a8519a38d9d9d0ac5f0ec9c Mon Sep 17 00:00:00 2001
From: Jan Aalmoes <jan.aalmoes@inria.fr>
Date: Sat, 21 Sep 2024 16:27:27 +0200
Subject: fin intro

---
 aia/theo.tex | 146 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 144 insertions(+), 2 deletions(-)

(limited to 'aia/theo.tex')

diff --git a/aia/theo.tex b/aia/theo.tex
index 2a826b1..3b8e49d 100644
--- a/aia/theo.tex
+++ b/aia/theo.tex
@@ -26,6 +26,7 @@ Ce résultat nous apprend que s'assurer que le modèle cible satisfait la \texti
 Dans le cas d'un modèle cible qui réalise une classifiction binaire et en considérant un attribut binaire nous avons une propriété plus précise.
 
 \begin{propriete}
+    \label{prop:aia-demparlvl}
     Soit $(\Omega,\mathcal{T},P)$ un espace probabilisé et $(\{0,1\}$, $\mathcal{P}(\{0,1\}))$ des espaces mesurables.
     Soit les variables aléatoires suivantes
     \begin{itemize}
@@ -83,7 +84,148 @@ De plus, nous voyons que la \textit{balanced accuracy} maximial d'attaque vaut $
 C'est à dire que $f$ satisfait DemPar est équivalant à dire que tout attaque à une \textit{balanced accuracy} égale à $\frac{1}{2}$.
 
 Grâce au Théorème~\ref{th:aia-dpgood} nous savons aussi que tout autre définition d'équtiée qui n'implique pas la paritée démographique ne permet pas de mitiger les AIA. 
-Par exemple, nous allons montrer que l'égalitée de chances de la Définition~\ref{def:background-eq-eoo} en permet pas de mitiger l'AIA dans le cas binaire que nous avons étuié précédement.
+Par exemple, nous allons montrer un cas ou l'égalitée des chances de la Définition~\ref{def:background-eq-eoo} est satisfaite mais om il existe une AIA qui donne une exactitude équillibrée suppérieur $0,5$.
 
-\subsection{Utiliser l'AIA pour contrôler le niveau d'équitée}.
+On représente le classifieur $\hat{Y}$ de l'étiquette $Y$ ainsi que la donnée d'entrée $X$ et l'attribut sensible $S$ dans le tableau suivant :
+\begin{equation*}
+    \begin{matrix}
+        X&Y&\hat{Y}&S\\
+        0&0&0&0\\
+        0&0&0&1\\
+        0&0&0&0\\
+        0&0&0&0\\
+        1&1&1&1\\
+        1&1&1&1\\
+        1&1&1&1\\
+        1&1&1&0\\
+    \end{matrix}
+\end{equation*}
+Nous utilisons le modèle cible utilisé est $\hat{Y}=id\circ X$.
+Ce classifieur satisfait l'équitée des chances car 
+$P(\hat{Y}=0\mid Y=0\wedge S=0) = P(\hat{Y}=0\mid Y=0\wedge S=1) = 1$
+et 
+$P(\hat{Y}=0\mid Y=1\wedge S=0) = P(\hat{Y}=0\mid Y=1\wedge S=1) = 0$.
+Alors si on choisit comme modèle d'attaque la fonctione identitée, nous avont comme accuracy de l'AIA $0,75$ ce qui indique une fuite de l'attribut sensible.
+
+%De manière plus précises et plus générale nous avancons le théorème suivant :
+%\begin{theorem}
+%\label{th:eoo}
+    %Si $\hat{Y}$ satisfait l'équitée des chances pour $Y$ et $S$, alors l'exactitude équilibrée de l'AIA est de $\frac{1}{\#F}$ si et seulement si $Y$ est independant de $S$ ou si 
+    %for $Y$ and $S$ then the balanced accuracy of AH is $\frac{1}{2}$ if and only if $Y$ is independent of $S$ or $\hat{Y}$ is independent of $Y$.
+%\end{theorem}
+%Those two conditions are unlikely to happen with real world dataset and target models.
+%Indeed, $Y$ is independent of $S$ means that the ground truth label is independent of the sensitive attribute which never happens as we have observed in the experiment section.
+%And $\hat{Y}$ is independent of $Y$ means that the target model did not managed to learn anything: it does not have any utility which defies the purpose of using it in a production and commercial environment. 
+%Since both of those conditions are not practical, we close the case of EO by saying that it is not fit as a defense against attribute inference attack at inference time.
+%We prove the theorem:
+%\begin{proof}
+%Let $a$ be the attack model trained for AS: $\hat{S}=a\circ \hat{Y}$.
+%By the total probability formula
+%\begin{align*}&P(\hat{S}=0|S=0)\\
+%=&P(\hat{S}=0|S=0Y=0)P(Y=0|S=0)\\
+%+&P(\hat{S}=0|S=0Y=1)P(Y=1|S=0)
+%\end{align*}
+%and as well
+%\begin{align*}&P(\hat{S}=1|S=1)\\
+        %=&P(\hat{S}=1|S=1Y=0)P(Y=0|S=1)\\
+        %+&P(\hat{S}=1|S=1Y=1)P(Y=1|S=1)
+%\end{align*}
+%Then we substitute those terms in the definition of the balanced accuracy of the target model.
+%\begin{align*}
+        %&\frac{P(\hat{S}=0|S=0)+P(\hat{S}=1|S=1)}{2}\\
+        %=&\frac{1}{2}+\frac{1}{2}\left(P(Y=0|S=0)-P(Y=0|S=1)\right)\\
+        %&\left(P(\hat{Y}\in a^{-1}(\{1\})|S=1Y=0) -
+        %P(\hat{Y}\in a^{-1}(\{1\})|S=1Y=1)\right)
+%\end{align*}
+%The balanced accuracy is equal to 0.5 if and only if $P(Y=0|S=0)=P(Y=0|S=1)$
+%or $\forall a~P(\hat{Y}\in a^{-1}(\{1\})|S=1Y=0)=P(\hat{Y}\in a^{-1}(\{1\})|S=1Y=1)$.
+%The first equation means that $Y$ is independent of $S$.
+%The second means that for $S=1$ the trained target model did not learn.
+%We can do the same computing for $S=0$ and obtain a similar conclusion. 
+%\end{proof}
+%
+\subsection{Utiliser l'AIA pour contrôler le niveau d'équitée}
+\label{sec:aia-theo-aia-eq}
+De manière réciproque, le lien que nous avons démontré peut ausi être utilié dans le cas suivant.
+Imaginons qu'un fournisseur de modèle d'IA ou un organisme de régulation comme la Défensseure des Droit souhaite contrôler si un modèle est équitable ou non.
+Si $\#F$ ou $\#G$ sont grands voir de cardinaux infinis, vérifier diréctement des propriétés d'indépendances entre la sortie du modèle et des attributs sensible peut entraîner un coût de calcul trop élevé pour être faisable~\cite{ofverstedt2022fast}.
+
+Grâce au Théorème~\ref{th:aia-dpgood} nous avons la garantie que que si toutes les modèles AIA ont une exactitude équilibrée égale à $\frac{1}{\#F}$ alors le modèle cible satisfait la parité démographique.
+Bien sûre cette technique atteint sa limite si $\#G$ est infini car alors l'exactitude équliibrée n'est plus définie.
+
+Calculer l'exactitude équilibrée de toutes les modèles d'AIA est impossible.
+Nous allons voir que si l'AIA qui donne une exactitdue équilibrée maximal vaut $\frac{1}{\#F}$ alors c'est le cas pour toutes.
+
+\begin{theorem}
+    \label{th:aia-bluey}
+    Soit $(\Omega,\mathcal{T},P)$ un espace probabilisé.
+    Soient $(E,\mathcal{E})$ et $(F,\mathcal{P}(F))$ des espaces mesurables avec $F$ un esemble fini.
+    Soient les varibles aléatoires suivantes :
+    \begin{itemize}
+        \item $X:\Omega\rightarrow E$
+        \item $Y:\Omega\rightarrow F$
+    \end{itemize}
+    Soit $A$ l'ensemble des fonctions mesurables de $(E,\mathcal{E})$ dans $(F,\mathcal{P}(F))$.
+    Nous appelons $BA$ la fonction qui à toutes fonction $a$ de $A$ associe l'exactitude équilibrée de $a \circ X$ pour l'étiquette $Y$.
+    \begin{equation*}
+    \exists a\in A~BA(a)< \frac{1}{\#F}
+    \implies
+    \exists a\in A~BA(a)>\frac{1}{\#F}
+    \end{equation*}
+\end{theorem}
+
+\begin{proof}
+    Soit $a\in A$ telle que $BA(a)<\frac{1}{\#F}$.
+    Nous allons montrer qu'il existe $b\in A$ telle que $BA(b)>\frac{1}{\#F}$
+
+    A la manière de la démonstration du Théorème~\ref{th:fini-bacca}, on se donne la matrice 
+    \begin{equation*}
+        M(i,j) = P(a\circ X = y_i\mid Y=y_j)
+    \end{equation*}
+
+    On note $S_{\#F}$ l'ensemble des bijections de $\#F$ sur lui-même.
+    Montrons qu'il existe 
+    $\varphi\in S_{\#F}$ telle que $\sum_{j\in\#F}M(\varphi(j),j) >1$.
+    Raisonons par l'absurde.
+    Nous supposont que 
+    \begin{equation*}
+        \forall \varphi\in S_{\#F}~\sum_{j\in\#F}M(\varphi(j),j)<1
+    \end{equation*}
+    Alors 
+    \begin{align*}
+        &\sum_{\varphi\in S_{\#F}}\sum_{j\in\#F}M(\varphi(j),j)<N!\\
+        \implies&\sum_{j\in\#F}\sum_{\varphi\in S_{\#F}}M(\varphi(j),j)<N!\\
+        \implies&\sum_{j\in\#F}\sum_{i\in\#F}(N-1)!M(i,j)<N!\\
+        \implies&\sum_{j\in\#F}\sum_{i\in\#F}M(i,j)<N\\
+    \end{align*}
+    Ce qui est absurde car 
+    \begin{equation*}
+        \sum_{i\in\#F} M(i,j) = 
+        \sum_{i\in\#F}P(a\circ X=y_i\mid Y=y_j)=1
+    \end{equation*}
+    Donc
+    \begin{equation*}
+        \sum_{j\in\#F}\sum_{i\in\#F}M(i,j) = N
+    \end{equation*}
+
+    Ainsi, nous avons $\varphi\in S_{\#F}$ telle que 
+    $\sum_{j\in\#F}M(\varphi(j),j)>1$.
+    Comme nous l'avons montré dans la preuve du Théorème~\ref{th:fini-bacca}, nous avons $u\in\mathcal{H}^{\#F}$ tel que en posant 
+    \begin{equation*}
+        b = u_{\#F-1}\circ\cdots\circ u_0\circ a
+    \end{equation*}
+    alors $BA(b)>\frac{1}{\#F}$.
+
+\end{proof}
+
+Nous allons utiliser ce théorème pour montrer que si l'AIA maximale à une exactidue équilibrée égale à $\frac{1}{\#G}$ alors toutes les AIA ont la même éxactiture equilibrée.
+On se donne $A$ l'ensemble des fonctions mesurable de $(F,\mathcal{F}$ dans $(G,\mathcal{P}(G)$.
+$A$ modélise l'ensemble des AIA possibles pour un modèle cible qui prédit dans $F$ et un attribut sensible dans $G$, un ensemble fini. 
+Supposons que $\text{max}_{a\in A} BA(a)=\frac{1}{\#G}$.
+Alors $\forall a\in A~BA(a)\leq\frac{1}{\#G}$.
+D'après la contraposée du Théorème~\ref{th:aia-bluey} nous avons alors $\forall a\in A~BA(a)\geq\frac{1}{\#G}$.
+Ainsi $\forall a\in A~BA(a)=\frac{1}{\#G}$.
 
+Pour contrôler si un classifieur vérifie la paritée demographique il est donc suffisant de connaitre l'exactitude équilibrée maximial de toutes les AIA.
+Comme nous venons de le voir, si cette valuer vaut $\frac{1}{\#G}$ alors le classifieur satisfait la paritée démographique.
+La recherche d'une AIA qui maximise l'exactitude équilibrée est discuté à la Section~\ref{sec:aia-aia}.
-- 
cgit v1.2.3

