diff options
| -rw-r--r-- | background/proba.tex | 16 | ||||
| -rw-r--r-- | background/set.tex | 52 | ||||
| -rw-r--r-- | classification_finie/ba.tex | 89 |
3 files changed, 153 insertions, 4 deletions
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. diff --git a/classification_finie/ba.tex b/classification_finie/ba.tex index 7069668..21e272c 100644 --- a/classification_finie/ba.tex +++ b/classification_finie/ba.tex @@ -17,6 +17,79 @@ Nous proposons donc la définition suivante : Alors pour $\hat{Y}=f\circ X$, nous avons $P_{(Y,\hat{Y})} = P_Y\otimes P_{\hat{Y}}$ \end{definition} +\begin{lemma} + \label{lemme:aia-xycca} + Soit $(\Omega,\mathcal{T},P)$ un espace probabilisé. + Soient $X:(\Omega,\mathcal{T}) \rightarrow (E,\mathcal{E})$ et $Y:\Omega \rightarrow (F,\mathcal{F})$ des variables aléatoires. + Les deux propositions suivantes sont équivalantes : + \begin{enumerate} + \item $P_{(X,Y)} = P_X\otimes P_Y$. + \item Toute fonction mesurable $f:(E,\mathcal{T})\rightarrow (F,\mathcal{F})$ est un CCA pour prédire $Y$ à partir de $X$. + \end{enumerate} +\end{lemma} +\begin{proof} + En gardant les objets définis dans le Lemme~\ref{lemme:aia-xycca}. + Nous allons prouver séparément les deux implications. + \paragraph{$(1)\implies(2)$} + Nous supposons que $P_{(X,Y)} = P_X\otimes P_Y$. + Soit $f:(E,\mathcal{T})\rightarrow (F,\mathcal{F})$, un fonction mesurerable, + nous allons montrer que $f$ est un CCA, c'est-à dire que $P_{(f\circ X,Y)} = P_{f\circ X}\otimes P_Y$. + + Soient $(A,B)\in\mathcal{E}\times\mathcal{F}$ + \begin{align*} + &P_{(f\circ X,Y)}(A,B)&\\ + =&P(\{f\circ X\in A\}\cap\{Y\in B\})&\\ + =&P(\{X\in f^{-1}(A)\}\cap\{Y\in B\})&\\ + &&\textit{Comme $X$ et $Y$ sont indépendantes.}\\ + =&P_X(f^{-1}(A))P_Y(B)&\\ + =&P_{f\circ X}(A)P_Y(B)& + \end{align*} + + Ainsi, $\forall (A,B)\in\mathcal{E}\times\mathcal{F}~P_{(f\circ X,Y)}(A,B) = P_{f\circ X}(A)P_Y(B)$. + D'après la définition de le mesure produit donnée à la Section~\ref{sec:background-proba}, nous avons donc bien $P_{(f\circ X,Y)} = P_{f\circ X}\otimes P_Y$. + Ce qui est bien la définition de l'indépendant donnée en Section~\ref{sec:background-proba}. + + \paragraph{$(2)\implies (1)$} + Nous supposons que tout classifieur de $Y$ à partir de $X$ est un CCA. + Montrons que $P_{(X,Y)} = P_{f\circ X}\otimes P_Y$. + Soit $(A,B)\in\mathcal{E}\times\mathcal{F}$. + Nous allons montrer que + $P(X\in A\cap Y\in B) = P(X\in A)P(Y\in B)$. + + \paragraph{Cas 1 : $\mathcal{F}=\{\emptyset,F\}$} + Si $B=\emptyset$ alors + $P(X\in A\cap Y\in B) = P(X\in A)P(Y\in B) = \emptyset$. + Si $B=F$ alors + $P(X\in A\cap Y\in B) = P(X\in A)P(Y\in B) = P(X\in A)$. + + \paragraph{Cas 2 : $\#\mathcal{F}>2$} + Alors il existe $C\in\mathcal{F}$ tel que $C\neq\emptyset$ et $F\backslash C\neq\emptyset$. + Nous pouvons donc choisir $c$ dans $C$ et $c'$ dans $F\backslash C$. + Nous construisons la fonction suivante: + \begin{equation*} + f:\left\{ + \begin{matrix} + E\rightarrow F\\ + e\mapsto\left\{ + \begin{matrix} + c~\text{si}~e\in A\\ + c'~\text{sinon} + \end{matrix} + \right. + \end{matrix} + \right. + \end{equation*} + Alors $f:(E,\mathcal{E})\rightarrow (F,\mathcal{F})$ est une fonction mesurable et $f^{-1}(C) = A$. + Ainsi + \begin{align*} + &P(X\in A\cap Y\in B)\\ + =&P(X\in f^{-1}(C)\cap Y\in B)\\ + \text{Comme $f$ est un CCA.}&\\ + =&P(f\circ X\in C)P(Y\in B)\\ + =&P(X\in A)P(Y\in B) + \end{align*} + +\end{proof} \begin{propriete} \label{prop:CCA_BA} @@ -104,7 +177,21 @@ Déjà la \textit{balanced accuracy} est égale à $\frac{1}{3}$ car $\forall y\in F~P(\hat{Y}=y\mid Y=y)=\frac{1}{3}$. Enfin nous voyons que $f$ n'est pas un CCA car $P(\hat{Y}=1\cap Y=2) = 0$ et -$P(\hat{Y}=1)P(Y=2) = \frac{2}{9}\frac{1}{3} = \frac{2}{27}$ +$P(\hat{Y}=1)P(Y=2) = \frac{2}{9}\frac{1}{3} = \frac{2}{27}$. + +Remarquons que le réciproque de la Propriété~\ref{prop:CCA_BA} est vrai dans le cas d'une classifieur binaire, c'est-à dire $\#F=2$. +En effet dans ce cas, supposons que la \textit{balanced accuracy} vale $0,5$, alors +\begin{align*} + &P(f\circ X=0\mid Y=0)+P(f\circ X=1\mid Y=1) = 1\\ + \implies&\left\{ + \begin{matrix} + &P(f\circ X=1\mid Y=0)=P(f\circ X=1\mid Y=1)\\ + \text{et}&\\ + &P(f\circ X=0\mid Y=0)=P(f\circ X=0\mid Y=1) + \end{matrix} + \right.\\ + \implies&\text{$f$ est un CCA} +\end{align*} Bien qu'une \textit{balanced accuracy} égale à $\frac{1}{\#F}$ ne soit pas un critère de CCA, nous pouvons utiliser cette métrique pour savoir si il existe un classifieur qui soit un CCA. En effet nous avons le resultat suivant : |