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 --- classification_finie/finit_classif.tex | 269 +++++++++++++++++---------------- classification_finie/main.tex | 69 +-------- 2 files changed, 140 insertions(+), 198 deletions(-) (limited to 'classification_finie') 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} -- 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 --- classification_finie/ba.tex | 372 +++++++++++++++++++++++++++++++++ classification_finie/finit_classif.tex | 1 + 2 files changed, 373 insertions(+) create mode 100644 classification_finie/ba.tex (limited to 'classification_finie') diff --git a/classification_finie/ba.tex b/classification_finie/ba.tex new file mode 100644 index 0000000..7069668 --- /dev/null +++ b/classification_finie/ba.tex @@ -0,0 +1,372 @@ +Le cas d'un classifieur constant, comme nous l'avons à la Section~\ref{sec:backgroung-ml-classif}, n'est qu'un exemple de Classifieur qui réalise un Choix Aléatoire (CCA). +En anglais la litterature parle en générale de \textit{random guess}~\cite{chicco2021matthews}. +Cependant, à notre conaissance, il n'y a pas de definition mathématique qui unifie l'idée générale de CCA qui est : +un classifieur qui se comporte comme si il n'avait aucune conaissance sur sa tâche de classification. +Un CCA n'est pas un classifieur qui utilise l'aléatoire mais plutot un classifieur hasardeux, comme une personne qui choisirai au hasard. +C'est le cas pour un classifieur constant mais aussi pour un classifieur binaire qui tire à pile ou face son résultat. + +Nous pourrions dire qu'un CCA est un classifieur qui n'utilise pas les données d'entrée. +Cependant cela ne prend pas un compte le cas où les données d'entrée ne servent à rien pour la tâche de classification. +Par exemple nous voudrions que notre définition englobe n'importe quelle classifieur qui cherche à prédire la qualitée d'un potimaron à partir la coleur de mes chaussettes le jour pù il a été ramassé. +Nous proposons donc la définition suivante : +\begin{definition} + Un CCA est un classifieur ayant une prédiction indépendante de l'étiquette. + C'est à dire que pour un classifeur $f: E\rightarrow F$. + Avec une étiquette $Y:\Omega\rightarrow F$ + et une entrée $X:\Omega\rightarrow E$. + Alors pour $\hat{Y}=f\circ X$, nous avons + $P_{(Y,\hat{Y})} = P_Y\otimes P_{\hat{Y}}$ +\end{definition} + +\begin{propriete} + \label{prop:CCA_BA} + Les CCA ayant comme image $ F$ ont une \textit{balanced accuracy} égale à $\frac{1}{\# F}$. +\end{propriete} + +\begin{proof} + Soit $f: E\rightarrow F$ un CCA. + On pause $\hat{Y} = f\circ X$ + La \textit{balanced accuracy} de $f$ est alors + \begin{align*} + &\frac{1}{\# F}\sum_{y\in F} + P(\hat{Y}=y\mid Y=y)\\ + =&\frac{1}{\# F}\sum_{y\in F} + \frac{P(\{\hat{Y}=y\}\cap \{Y=y\})}{P(Y=y)}\\ + =&\frac{1}{\# F}\sum_{y\in F} + \frac{P_{(\hat{Y},Y)}(\{y\}\times \{y\})}{P(Y=y)}\\ + \text{Comme $f$ est un CCA.}\\ + =&\frac{1}{\# F}\sum_{y\in F} + \frac{P(\hat{Y}=y)P(Y=y)}{P(Y=y)}\\ + =&\frac{1}{\# F}\sum_{y\in F} + P(\hat{Y}=y)\\ + =&\frac{1}{\# F} + \end{align*} +\end{proof} + +La contraposé de la Propositon~\ref{prop:CCA_BA} nous apprend que si la \textit{balanced accuracy} est différente de $0,5$ alors le classifieur n'est pas un CCA. + + Il est interessant de noter que si un classifieur à une \textit{balanced accuracy} de $\frac{1}{\#F}$ il n'est pas necessaire qu'il soit un CCA. + Pour prouver cette remarque il suffit de trouver un exemple de classifieur ayant une \textit{balanced accuracy} de $\frac{1}{\#F}$ et qui ne soit pas un CCA. + +Nous appelons $r(a,b)$ le reste de la division euclidienne de $a$ par $b$. +Soient les ensembles suivant : +$E = [|0,8|]$ et +$F = [|0,2|]$. +En considérant l'espace probabilisé +$(E,\mathcal{P}(E),\frac{1}{9}\sum_{i=0}^8\delta_{i})$ +nous définissons les variables aléatoire suivantes : +$X=\textit{id}_E$ +\begin{equation*} + Y:\left\{ + \begin{matrix} + E\rightarrow F\\ + e\mapsto r(e,3) + \end{matrix} + \right. +\end{equation*} + +Ainsi que la fonction mesurable suivante qui est l'exemple de classifieur que nous exhibons pour montrer la remarque : +\begin{equation*} + f:\left\{ + \begin{matrix} + E\rightarrow F\\ + e\mapsto \left\{ + \begin{matrix} + r(e,3)~\text{si $e<3$}\\ + r(e+1,3)~\text{si $3\leq e<6$}\\ + r(e+2,3)~\text{si $6\leq e<8$}\\ + 0~\text{sinon} + \end{matrix} + \right. + \end{matrix} + \right. +\end{equation*} + +Montrons que la \textit{balanced accuracy} de $f$ vaut $\frac{1}{3}$. +En notant $\hat{Y} = f\circ X$, nous réprésentons cette situation par le tableau suivant. +\begin{equation*} + \begin{matrix} + X&Y&\hat{Y}\\ + 0&0&0\\ + 1&1&1\\ + 2&2&2\\ + 3&0&1\\ + 4&1&2\\ + 5&2&0\\ + 6&0&2\\ + 7&1&0\\ + 8&2&0 + \end{matrix} +\end{equation*} + +Il nous permet de calculer facilement les quantités suivantes. +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}$ + +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 : + +\begin{theorem} + En notant $BA(f)$ la \textit{balanced accuracy} de $f$. + \begin{equation*} + \forall f~BA(f)=\frac{1}{\#F} \iff + \forall f~\text{$f$ est un CCA} + \end{equation*} +\end{theorem} + +\begin{proof} + L'implication réciproque est une conséquence directe de la Propriété~\ref{prop:CCA_BA}. + + Pour le sens directe, nous allons montrer la contraposée, c'est à dire l'assertion suivante : + \begin{equation*} + \exists f~\text{$f$ n'est pas un CCA} \implies + \exists f~BA(f)\neq \frac{1}{\#F} + \end{equation*} + + Nous avons donc $E$ un ensemble et $F$ un ensemble fini. + Nous avons les variables aléatoires $X:\Omega\rightarrow E$ + et $Y:\Omega\rightarrow \mathcal{P}(F)$. + Nous supposons que nous avons $f:(E,\mathcal{E})\rightarrow (F,\mathcal{F})$, une fonction mesurable qui ne soit pas un CCA pour prédire $Y$ en utilisant $X$. + + Nous avons donc $(A,B)\in{\mathcal{P}(F)}^2$ tel que + \begin{equation*} + P(f\circ X\in A\cap Y\in B)\neq P(f\circ X\in A)P(Y\in B) + \end{equation*} + + Or + \begin{equation*} + P(f\circ X\in A\cap Y\in B) = \sum_{a\in A}\sum_{b\in B}P(f\circ X=a\cap Y=b) + \end{equation*} + et + \begin{equation*} + P(f\circ X\in A)P(\cap Y\in B) = \sum_{a\in A}\sum_{b\in B}P(f\circ X=a)P(Y=b) + \end{equation*} + Ainsi + \begin{equation*} + \exists (a,b)\in A\times B~ + P(f\circ X=a\cap Y=b)\neq P(f\circ X=a)P(Y=b) + \end{equation*} + + Nous définisson les fonctions suivante pour tout $z$ et $z'$, éléments de $F$ : + \begin{equation*} + h_{z,z'}:\left\{ + \begin{matrix} + F\rightarrow F\\ + y\mapsto \left\{ + \begin{matrix} + &z&\text{si}&y=z'\\ + &z'&\text{si}&y=z\\ + &y&\text{sinon}& + \end{matrix} + \right. + \end{matrix} + \right. + \end{equation*} + + $h_{z,z'}$ vas nous permetre et permuter les inférences faitent par $f$. + Ainsi à partir de $f$ nous créons de nouveaux classifieurs. + Soit $\mathcal{H}=\{h_{z,z'}\mid (z,z')\in F^2\}$ nous allons montrer qu'il existe $\#F$-uplet de $\mathcal{H}$, $u$, tel que le classifieur $u_{\#F-1}\circ\cdots\circ u_0\circ f$ ai une \textit{balanced accuracy} différent de $\frac{1}{\#F}$. + + Considérons la matrice + \begin{equation*} + M_f(i,j) = P(f\circ X=y_i\mid Y=y_j) + \end{equation*} + Où $y_\square:\#F\rightarrow F$ est une bijection. + Alors la \textit{balanced accuracy} de $f$ est égale $\text{Tr}(M)$. + $h_{z,z'}$ peut aussi s'exprimer en terme matriciel. + La fonction suivainte est une bijection : + \begin{equation*} + \Phi:\left\{ + \begin{matrix} + \mathcal{H}\rightarrow\mathcal{H}'\\ + h_{y_i,y_j}\mapsto H_{i,j} + \end{matrix} + \right. + \end{equation*} + Où $\mathcal{H}'=\{H_{i,j}\mid(i,j)\in\#F^2\}$ avec + \begin{equation*} + H_{i,j} = \left( + \begin{matrix} + %1&&&&&&&&&\\ + \ddots&&&&&&&&\\ + &1&&&&&&&\\ + &&0&&&&1&&\\ + &&&1&&&&&\\ + &&&&\ddots&&&&\\ + &&&&&1&&&\\ + &&1&&&&0&&\\ + &&&&&&&1&\\ + &&&&&&&&\ddots\\ + %&&&&&&&&&&1 + \end{matrix} + \right) + \begin{matrix} + \\ + \\ + i\\ + \\ + \\ + \\ + j\\ + \\ + \\ + \end{matrix} + \end{equation*} + + De plus, $M_{h_{y_i,y_j}\circ f}$ correspond à intervertire les lignes des $M_f$, + c'est-à dire que $M_{h_{y_i,y_j}\circ f} = H_{i,j}M_f$. + En effet, $h_{y_i,y_j}$ est une bijection telle que + $h_{y_i,y_j}^{-1} = h_{y_i,y_j}$. + Alors, soit $(k,l)\in\#F^2$, + \begin{align*} + &M_{h_{y_i,y_j}\circ f}(k,l)\\ + =&P\left(h_{y_i,y_j}\circ f\circ X=y_k\mid Y=y_l\right)\\ + =&P\left(f\circ X=h_{y_i,y_j}(y_k)\mid Y=y_l\right)\\ + =&\left\{ + \begin{matrix} + P\left(f\circ X=y_i\mid Y=y_l\right)&\text{si}& k=j\\ + P\left(f\circ X=y_j\mid Y=y_l\right)&\text{si}&k=i\\ + P\left(f\circ X=y_k\mid Y=y_l\right)&\text{sinon}& + \end{matrix} + \right.\\ + =&\left\{ + \begin{matrix} + M(i,l)&\text{si}&k=j\\ + M(j,l)&\text{si}&k=i\\ + M(k,l)&\text{sinon}& + \end{matrix} + \right.\\ + &=H_{i,j}M_f(k,l) + \end{align*} + +Ainsi l'existence de $u$ est équivalante à l'existance d'une matrice $H = H_{i_{\#F-1},j_{\#F-1}}\cdots H_{i_0,j_0}$ telle que $\text{Tr}(HM_f)\neq 1$. +Montrons l'existence d'une telle matrice $H$. + +Commencons par montrer que pour chaque ligne de $M_f$ il est possible de choisir arbitrairement l'élement de la ligne qui sera dans la diagonale de $HM_f$ tant qu'on ne choisit pas deux fois un élément dans une même colone. +C'est-à dire montrons que +\begin{align*} + \{\{M(i,\varphi(i))\mid i\in\#F\}\mid \text{$\varphi$ est une bijection sur $\#F$}\}\\ + \subset\{\text{Diag}(HM_f)\mid \exists I\in \left(\mathcal{H}'\right)^{\#F}~H=I_{\#F-1}\cdots I_0\} +\end{align*} +Soit $\varphi$ une bijection sur $\#F$, nous posons +\begin{equation*} + \psi:\left\{ + \begin{matrix} + \#F\rightarrow \#F\\ + i\mapsto \left\{ + \begin{matrix} + \varphi^{-1}(i)&\text{si}&\varphi^{-1}(i)\geq i\\ + \varphi^{-1}\left(\varphi^{-1}(i)\right)&\text{sinon}& + \end{matrix} + \right. + \end{matrix} + \right. +\end{equation*} +Nous posons +\begin{equation} + \label{eq:fini-H} + H=H_{\psi(\#F-1),\#F-1}\cdots H_{\psi(1),1}H_{\psi(0),0} +\end{equation} +Pour montrer l'inclusion précédente, il suffit alors de montrer que +\begin{equation*} +\{M(i,\varphi(i))\mid i\in\#F\} = +\text{Diag}(HM_f) +\end{equation*} +Montrons donc que +$\forall i\in\#F~M_f(i,\varphi(i))=HM_f(\varphi(i),\varphi(i))$. +Soit $i\in\#F$. +$H$ intervertis les lignes de $M_f$, la colone $\varphi(i)$ est à la même place dans $M_f$ et dans $HM_f$. +Il suffit donc de montrer que la $i$ème ligne de $M_f$ est la $\varphi(i)$ème de $HM_f$. +Isolons les termes qui modifient la position de la $i$ème ligne de $H$. +Si $i\geq\varphi(i)$ alors +\begin{align*} + &HM_f(\varphi(i),\varphi(i))\\ + =&H_{\psi(\varphi(i)),\varphi(i)}M_f(\varphi(i),\varphi(i))\\ + =&H_{i,\varphi(i)}M_f(\varphi(i),\varphi(i))\\ + =&M_f(i,\varphi(i)) +\end{align*} +si $i<\varphi(i)$ alors +\begin{align*} + &HM_f(\varphi(i),\varphi(i))\\ + =&H_{\psi(\varphi(i)),\varphi(i)}H_{\varphi^{-1}(i),i}M_f(\varphi(i),\varphi(i))\\ + =&H_{\varphi^{-1}(i),\varphi(i)}H_{\varphi^{-1}(i),i}M_f(\varphi(i),\varphi(i))\\ + =&M_f(i,\varphi(i)) +\end{align*} + +Ainsi grâce à l'Equation~\ref{eq:fini-H}, pour toute bijection sur $\#F$ nous pouvons construir une suite de $\#F$ permutations de lignes telle que la diagonale de la matrice résultante des permutations contienent les éléments sélectionés par la bijections. +Nous allons montrer qu'il existe une séléction d'éléments telle que la somme de ses éléments soit différente de $1$. +Pour ce faire, nous allons montrer la proposition ($\dag$) : si toutes les séléctions donnent une somme égale à $1$ alors necessairement tous les élement de chaque ligne de $M_f$ sont égaux entre eux. + +Supposons donc, que pour toutes les bijections $\varphi$ sur $\#F$, nous ayons +\begin{equation*} + \sum_{i\in\#F}M_f(i,\varphi(i)) = 1 +\end{equation*} +Nous savons qu'il existe $\#F!$ bijections sur $\#F$. +De plus, +\begin{equation*} + \forall j\in\#F~\sum_{i\in\#F}M_f(i,j)= + \sum_{i\in\#F}P(f\circ X=y_i\mid Y=y_j) =1 +\end{equation*} + +Ces deux conditions impliquent que pour toute ligne $i$ et colone $j$ : +\begin{align*} + &\sum_{\varphi\in B(i,j)}\sum_{k\in\#F}M_f(k,\varphi(k)) + +\sum_{k\in\#F}M_f(k,j) = (\#F-1)!+1\\ + \iff& + ((\#F-1)!+1)M(i,j)+ + \sum_{k\in\#F\backslash\{i\}}M_f(k,j) + + \sum_{\varphi\in B(i,j)}M_f(k,\varphi(k))\\ + &= (\#F-1)!+1\\ + \iff& + ((\#F-1)!+1)M(i,j)+ + \sum_{k\in\#F\backslash\{i\}}M_f(k,j) + \sum_{l\in\#F}M_f(k,l) + = (\#F-1)!+1\\ + \iff& + M(i,j) + = + \frac{1}{(\#F-1)!+1} + \left( + (\#F-1)!+1- + \sum_{k\in\#F\backslash\{i\}} + \sum_{l\in\#F}M_f(k,l) + \right) +\end{align*} + +Ainsi $\exists u \forall j\in\#F~M(i,j)= u$, cela achève la preuve de la proposition ($\dag$). +Or dans notre cas nous avons $(a,b)\in A\times B$ +\begin{equation*} + P(f\circ X=a\cap Y=b)\neq P(f\circ X=a)P(Y=b) +\end{equation*} +Ainsi, comme nous avons $(i,j)\in\#F^2$ tel que $y_i=a \wedge y_j=b$, +\begin{equation*} + P(f\circ X=y_i\mid Y=y_j)\neq P(f\circ X=y_i) +\end{equation*} +Et donc, il existe $k\in\#F$ tel que +\begin{equation*} + P(f\circ X=y_i\mid Y=y_j)\neq P(f\circ X=y_i\mid Y=y_k) +\end{equation*} +C'est à dire que $M_f(i,j)=\neq M_f(i,k)$. + +D'après la contraposée de la propostion ($\dag$), nous avons une selection $\varphi$ telle que +$\sum_{i\in\#F}M(\varphi(i),\varphi(i))\neq 1$. +Donc en définisant $H$ de la même manière qu'à l'Equation~\ref{eq:fini-H} nous avons $\text{Tr}(HM_f)\neq 1$. +Il existe alors un $\#F$-uplet $u\in\mathcal{H}^{\#F}$ tel que +, pour +\begin{equation*} + g = u_{\#F-1}\circ\cdots\circ u_0\circ f +\end{equation*} +\begin{equation*} + BA(g)\neq \frac{1}{\#F} +\end{equation*} + + + +\end{proof} + +Nous allons construire un classifieur qui maximise la \textit{balanced accuracy}. + + diff --git a/classification_finie/finit_classif.tex b/classification_finie/finit_classif.tex index f518cdc..df1fb9f 100644 --- a/classification_finie/finit_classif.tex +++ b/classification_finie/finit_classif.tex @@ -377,6 +377,7 @@ Nous cherchons donc le maximum de chaque ligne de $M$ ce qui fait que nous n'avo Nous formalisons cette idée dans le théorème suivant : \begin{theorem} + \label{th:fini-em} Soit $e_i$ le $n$-uplet de $\mathbb{N}$ suivant : \begin{equation*} e_i:\left\{ -- 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 --- classification_finie/ba.tex | 89 ++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 88 insertions(+), 1 deletion(-) (limited to 'classification_finie') 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 : -- 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 --- classification_finie/ba.tex | 3 +- classification_finie/figure/ba/COMPAS.pdf | Bin 0 -> 13097 bytes classification_finie/figure/ba/LAW.pdf | Bin 0 -> 12684 bytes .../figure/cezanne/cezanne/colage.png | Bin 0 -> 27809765 bytes .../figure/cezanne/cezanne/collage.svg | 77 +++++++++++++++++++++ classification_finie/figure/cezanne/colage.png | Bin 0 -> 27809765 bytes classification_finie/figure/cezanne/collage.svg | 77 +++++++++++++++++++++ classification_finie/figure/time/COMPAS.pdf | Bin 0 -> 12220 bytes classification_finie/figure/time/LAW.pdf | Bin 0 -> 12458 bytes classification_finie/main.tex | 1 + classification_finie/tabular.tex | 16 +++-- 11 files changed, 167 insertions(+), 7 deletions(-) create mode 100644 classification_finie/figure/ba/COMPAS.pdf create mode 100644 classification_finie/figure/ba/LAW.pdf create mode 100644 classification_finie/figure/cezanne/cezanne/colage.png create mode 100644 classification_finie/figure/cezanne/cezanne/collage.svg create mode 100644 classification_finie/figure/cezanne/colage.png create mode 100644 classification_finie/figure/cezanne/collage.svg create mode 100644 classification_finie/figure/time/COMPAS.pdf create mode 100644 classification_finie/figure/time/LAW.pdf (limited to 'classification_finie') diff --git a/classification_finie/ba.tex b/classification_finie/ba.tex index 21e272c..ff0dacd 100644 --- a/classification_finie/ba.tex +++ b/classification_finie/ba.tex @@ -197,6 +197,7 @@ Bien qu'une \textit{balanced accuracy} égale à $\frac{1}{\#F}$ ne soit pas un En effet nous avons le resultat suivant : \begin{theorem} + \label{th:fini-bacca} En notant $BA(f)$ la \textit{balanced accuracy} de $f$. \begin{equation*} \forall f~BA(f)=\frac{1}{\#F} \iff @@ -262,7 +263,7 @@ En effet nous avons le resultat suivant : M_f(i,j) = P(f\circ X=y_i\mid Y=y_j) \end{equation*} Où $y_\square:\#F\rightarrow F$ est une bijection. - Alors la \textit{balanced accuracy} de $f$ est égale $\text{Tr}(M)$. + Alors la \textit{balanced accuracy} de $f$ est égale $\frac{\text{Tr}(M)}{\#F}$. $h_{z,z'}$ peut aussi s'exprimer en terme matriciel. La fonction suivainte est une bijection : \begin{equation*} diff --git a/classification_finie/figure/ba/COMPAS.pdf b/classification_finie/figure/ba/COMPAS.pdf new file mode 100644 index 0000000..0252902 Binary files /dev/null and b/classification_finie/figure/ba/COMPAS.pdf differ diff --git a/classification_finie/figure/ba/LAW.pdf b/classification_finie/figure/ba/LAW.pdf new file mode 100644 index 0000000..298a04e Binary files /dev/null and b/classification_finie/figure/ba/LAW.pdf differ diff --git a/classification_finie/figure/cezanne/cezanne/colage.png b/classification_finie/figure/cezanne/cezanne/colage.png new file mode 100644 index 0000000..ebe43f3 Binary files /dev/null and b/classification_finie/figure/cezanne/cezanne/colage.png differ diff --git a/classification_finie/figure/cezanne/cezanne/collage.svg b/classification_finie/figure/cezanne/cezanne/collage.svg new file mode 100644 index 0000000..2170529 --- /dev/null +++ b/classification_finie/figure/cezanne/cezanne/collage.svg @@ -0,0 +1,77 @@ + + + + diff --git a/classification_finie/figure/cezanne/colage.png b/classification_finie/figure/cezanne/colage.png new file mode 100644 index 0000000..ebe43f3 Binary files /dev/null and b/classification_finie/figure/cezanne/colage.png differ diff --git a/classification_finie/figure/cezanne/collage.svg b/classification_finie/figure/cezanne/collage.svg new file mode 100644 index 0000000..2170529 --- /dev/null +++ b/classification_finie/figure/cezanne/collage.svg @@ -0,0 +1,77 @@ + + + + diff --git a/classification_finie/figure/time/COMPAS.pdf b/classification_finie/figure/time/COMPAS.pdf new file mode 100644 index 0000000..b677e3a Binary files /dev/null and b/classification_finie/figure/time/COMPAS.pdf differ diff --git a/classification_finie/figure/time/LAW.pdf b/classification_finie/figure/time/LAW.pdf new file mode 100644 index 0000000..beb9fee Binary files /dev/null and b/classification_finie/figure/time/LAW.pdf differ diff --git a/classification_finie/main.tex b/classification_finie/main.tex index 91fdd27..901499a 100644 --- a/classification_finie/main.tex +++ b/classification_finie/main.tex @@ -1,2 +1,3 @@ \input{classification_finie/ba} \input{classification_finie/finit_classif} +\input{classification_finie/tabular} diff --git a/classification_finie/tabular.tex b/classification_finie/tabular.tex index ca2caaa..6112f77 100644 --- a/classification_finie/tabular.tex +++ b/classification_finie/tabular.tex @@ -1,12 +1,11 @@ -\FloatBarrier \begin{figure} \centering \begin{subfigure}{0.44\textwidth} - \includegraphics[width=\textwidth]{figure/ba/COMPAS.pdf} + \includegraphics[width=\textwidth]{classification_finie/figure/ba/COMPAS.pdf} \caption{COMPAS} \end{subfigure} \begin{subfigure}{0.44\textwidth} - \includegraphics[width=\textwidth]{figure/ba/LAW.pdf} + \includegraphics[width=\textwidth]{classification_finie/figure/ba/LAW.pdf} \caption{LAW} \end{subfigure} @@ -18,11 +17,11 @@ \begin{figure} \centering \begin{subfigure}{0.44\textwidth} - \includegraphics[width=\textwidth]{figure/time/COMPAS.pdf} + \includegraphics[width=\textwidth]{classification_finie/figure/time/COMPAS.pdf} \caption{COMPAS} \end{subfigure} \begin{subfigure}{0.44\textwidth} - \includegraphics[width=\textwidth]{figure/time/LAW.pdf} + \includegraphics[width=\textwidth]{classification_finie/figure/time/LAW.pdf} \caption{LAW} \end{subfigure} @@ -31,4 +30,9 @@ } \label{fig:time} \end{figure} -\FloatBarrier + +\begin{figure} + \centering + \includegraphics[width=\linewidth]{classification_finie/figure/cezanne/colage.png} + \caption{Classification du style des tableaux de Paul Cezanne}. +\end{figure} -- cgit v1.2.3