From 75aa438e61284f634375e2c1e62c79f2af12678f Mon Sep 17 00:00:00 2001 From: couchot Date: Fri, 2 Sep 2016 17:56:54 +0200 Subject: [PATCH] correction prng chaos chap 5 --- 12TIPE.tex | 6 +- 14Secrypt.tex | 2 +- 15RairoGen.tex | 142 +++++++++++++++++++++++++---------------------- chaosANN.tex | 147 ++++++++++++++++++++++++++----------------------- 4 files changed, 157 insertions(+), 140 deletions(-) diff --git a/12TIPE.tex b/12TIPE.tex index afd6077..7c04d49 100644 --- a/12TIPE.tex +++ b/12TIPE.tex @@ -14,9 +14,11 @@ Pour une stratégie $s = \left(s_t\right)_{t \in \mathds{N}}$ de $[\mathsf{N}]$), on peut définir la fonction $F_{f_u}: \Bool^{\mathsf{N}} \times [\mathsf{N}]$ vers $\Bool^\mathsf{N}$ par -\[ + +\begin{equation} F_{f_u}(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_\mathsf{N}). -\] +\label{eq:iterations:unaires} +\end{equation} Dans le schéma des itérations unaires pour une configuration initiale $x^0\in\Bool^\mathsf{N}$ et une stratégie $s\in diff --git a/14Secrypt.tex b/14Secrypt.tex index bc59ba1..10a4f85 100644 --- a/14Secrypt.tex +++ b/14Secrypt.tex @@ -23,7 +23,7 @@ section~\ref{sec:prng:gray:general}. Finalement, des instances de PRNGS engendrés selon les méthodes détaillées dans ce chapitre sont présentés en section~\ref{sec:prng;gray:tests}. Les sections~\ref{sec:plc} à~\ref{sub:gray} ont été publiées -à~\ref{chgw+14:oip}. +à~\cite{chgw+14:oip}. % This aim of this section is to show diff --git a/15RairoGen.tex b/15RairoGen.tex index a950d85..06f84b1 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -5,15 +5,17 @@ a de \og bonnes\fg{} propriétés chaotiques, le mot $x^b$ devrait \og sembler ne plus dépendre\fg{} de $x^0$. On peut penser à exploiter une de ces fonctions $G_f$ comme un générateur aléatoire. -Enfin, un bon générateur aléatoire se doit de -fournir des nombres selon une distribution uniforme + +Ce chapitre présente une application directe +de la théorie développée ci-avant +à la génération de nombres pseudo aléatoires. + + La suite de ce document donnera une condition nécessaire est suffisante pour que cette propriété soit satisfaite. -Cette section présente une application directe de la théorie développée ci-avant -à la génération de nombres pseudo aléatoires. On présente tout d'abord le générateur basé sur des fonctions chaotiques (section~\ref{sub:prng:algo}), puis comment intégrer la contrainte de distribution uniforme @@ -33,16 +35,15 @@ L'approche est évaluée dans la dernière section. \begin{algorithm}[h] %\begin{scriptsize} \KwIn{une fonction $f$, un nombre d'itérations $b$, -une configuration initiale $x^0$ ($n$ bits)} -\KwOut{une configuration $x$ ($n$ bits)} +une configuration initiale $x^0$ (${\mathsf{N}}$ bits)} +\KwOut{une configuration $x$ (${\mathsf{N}}$ bits)} $x\leftarrow x^0$\; -$k\leftarrow b $\; %$k\leftarrow b + \textit{XORshift}(b+1)$\; -\For{$i=1,\dots,k$} +\For{$i=1,\dots,b$} { -$s\leftarrow{\textit{Random}(n)}$\; +$s\leftarrow{\textit{Random}({\mathsf{N}})}$\; %$s\leftarrow{\textit{XORshift}(n)}$\; -$x\leftarrow{F_{f_u}(s,x)}$\; +$x\leftarrow{F_{f_u}(x,s)}$\; } return $x$\; %\end{scriptsize} @@ -56,11 +57,11 @@ aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous. Celui-ci prend en entrée: une fonction $f$; -un entier $b$, qui assure que le nombre d'itérations -est compris entre $b+1 $ et $2b+1$ (et donc supérieur à $b$) +un entier $b$, qui est le nombre d'itérations à effectuer entre deux sorties et une configuration initiale $x^0$. Il retourne une nouvelle configuration $x$ en appliquant -la fonction $F_{f_u}$ vue au chapitre~\ref{chap:carachaos} et correspondant +la fonction $F_{f_u}$ (équation~\ref{eq:iterations:unaires} +vue au chapitre~\ref{chap:carachaos}) et correspondant à des itérations unaires. En interne, il exploite un algorithme de génération de nombres pseudo aléatoires donné en paramètre. @@ -105,10 +106,13 @@ Notre approche vise a donner des propriétés de chaos a ce générateur embarqu Nous avons vu au chapitre~\ref{chap:carachaos} que $G_{f_u}$ est chaotique dans l'espace $\mathcal{X}_u$ si et seulement le graphe d'itérations $\textsc{giu}(f)$ -doit être fortement connexe. +est fortement connexe. Pour $b=1$, l'algorithme itère la fonction $F_{f_u}$. -Regardons comment l'uniformité de la distribution a -contraint la fonction. + +Pour simuler au mieux l'aléa, un bon générateur de nombre pseudo-aléatoires +se doit de fournir des nombres selon une distribution uniforme. +Regardons comment l'uniformité de la distribution +contraint la fonction $f$ à itérer. \subsection{Un générateur à sortie uniformément distribuée}\label{sub:prng:unif} @@ -121,7 +125,7 @@ Enfin, une matrice stochastique de taille $n \times n$ est régulière si la propriété suivante est établie: $$\exists k \in \mathds{N}^\ast, \forall i,j \in \llbracket 1; n \rrbracket, M_{ij}^k>0.$$ -On énonce enfin le théorème suivant liant les +On énonce le théorème classique suivant liant les vecteur de probabilités et les chaînes de Markov. @@ -316,10 +320,12 @@ On énonce directement le théorème suivant dont la preuve est donnée en annex \subsection{Quelques exemples} -On reprend le graphe d'interactions $\Gamma(f)$ donné en figure~\ref{fig:G} à la section~\ref{sec:11FCT}. -On a vu qu'il y avait 520 fonctions $f$ non isomorphes de graphe d'interactions $\Gamma(f)$, -dont seulement 16 d'entre elles possèdent une matrice doublement stochastique. +On considère le graphe d'interactions $\Gamma(f)$ donné +en figure~\ref{fig:G}. C'est le même qui a été présenté +à la section~\ref{sec:11FCT}. +On a vu qu'il y avait 520 fonctions $f$ non isomorphes de graphe d'interactions $\Gamma(f)$. +Seulement 16 d'entre elles possèdent une matrice doublement stochastique. La figure~\ref{fig:listfonction} explicite ces 16 fonctions en définissant les images des éléments de la liste 0, 1, 2,\ldots, 14, 15 en respectant l'ordre. @@ -343,11 +349,11 @@ ce vecteur au vecteur $\pi=(\frac{1}{2^n},\ldots,\frac{1}{2^n})$ Ainsi, on a \begin{equation} b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} -\{ -\min \{ +\left\{ +\min \left\{ t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4} -\} -\}. +\right\} +\right\}. \label{eq:mt:ex} \end{equation} @@ -444,7 +450,7 @@ Ceci est difficilement compatible avec la volonté d'avoir une sortie uniformém se rapprocher de cette distribution nécessite en effet un nombre plus élevé d'itérations $b$ entre chaque sortie. Par exemple, dans l'exemple précédent, il est nécessaire d'itérer au moins 42 fois entre chaque sortie pour suivre une loi uniforme à $10^{-4}$ près. -Montrer les sous-séquences de suites chaotiques ainsi générées demeurent chaotiques +Montrer que les sous-séquences de suites chaotiques ainsi générées demeurent chaotiques est l'objectif de la section suivante. @@ -464,15 +470,14 @@ Intuitivement, c'est le nombre d'itérations qu'il est autorisé de faire. On ordonne les $\mathsf{p}$ éléments de $\mathcal{P}$ comme suit: $\mathcal{P} = \{ p_1, p_2, \hdots, p_\mathsf{p}\}$ et $p_1< p_2< \hdots < p_\mathsf{p}$. + Dans l'algorithme~\ref{CI Algorithm}, $\mathsf{p}$ vaut 1 et $p_1=b$. - - Cet algorithme peut être vu comme $b$ compostions de la fonction $F_{f_u}$. Ceci peut cependant se généraliser à $p_i$, $p_i \in \mathcal{P}$, compositions fonctionnelles de $F_{f_u}$. Ainsi, pour chaque $p_i \in \mathcal{P}$, on construit la fonction -$F_{{f_u},p_i} : \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^{p_i} +$F_{{f_u},p_i} : \mathds{B}^\mathsf{N} \times [\mathsf{N}]^{p_i} \rightarrow \mathds{B}^\mathsf{N}$ définie par $$ @@ -484,11 +489,11 @@ $$ on construit l'espace $\mathcal{X}_{\mathsf{N},\mathcal{P}}= \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, où $\mathds{S}_{\mathsf{N},\mathcal{P}}= -\llbracket 1, \mathsf{N} \rrbracket^{\Nats}\times +[\mathsf{N}]^{\Nats}\times \mathcal{P}^{\Nats}$. Chaque élément de l'espace est une paire où le premier élément est un $\mathsf{N}$-uplet de $\Bool^{\mathsf{N}}$ (comme dans $\mathcal{X}_u$). -Le second élément est aussi une paire $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats})$ de suites infinies. +Le second élément est une paire $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats})$ de suites infinies. La suite $(v^k)_{k \in \Nats}$ définit combien d'itérations sont exécutées au temps $k$ entre deux sorties. La séquence $(u^k)_{k \in \Nats}$ définit quel élément est modifié (toujours au temps $k$). @@ -529,7 +534,7 @@ Soit $x=(e,s)$ et $\check{x}=(\check{e},\check{s})$ dans $\mathcal{X}_{\mathsf{N},\mathcal{P}} = \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}} $, où $s=(u,v)$ et $\check{s}=(\check{u},\check{v})$ sont dans $ \mathds{S}_{\mathsf{N},\mathcal{P}} = \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. -\begin{itemize} +\begin{enumerate} \item $e$ et $\check{e}$ sont des entiers appartenant à $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. La distance de Hamming $d_{\mathds{B}^\mathsf{N}}$ sur entre les décompositions binaires de $e$ et de $\check{e}$ (\textit{i.e.}, le @@ -544,7 +549,7 @@ $\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v Plus précisément, soit $p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ et $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$. -\begin{itemize} +\begin{enumerate} \item Les $p$ premiers éléments de $d(x,\check{x})$ sont $|v^0-\check{v}^0|$ écrits en base 10 et sur $p$ indices; \item les $n\times \max{(\mathcal{P})}$ éléments suivants servent @@ -552,7 +557,7 @@ $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$. $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$. Les $n$ premiers éléments sont $|u^0-\check{u}^0|$. Il sont suivis de $|u^1-\check{u}^1|$ écrits à l'aide de $n$ éléments, etc. -\begin{itemize} +\begin{enumerate} \item Si $v^0=\check{v}^0$, alors le processus se continue jusqu'à $|u^{v^0-1}-\check{u}^{\check{v}^0-1}|$ et la @@ -563,10 +568,10 @@ $p+n\times \max{(\mathcal{P})}$ éléments. éléments sont $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$, $\check{u}^{v^0}$ (sur $n$ éléments), ..., $\check{u}^{\check{v}^0-1}$ (sur $n$ éléments), suivi par des 0, si besoin. \item Le cas $v^0>\check{v}^0$ est similaire, et donc omis -\end{itemize} +\end{enumerate} \item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc. -\end{itemize} -\end{itemize} +\end{enumerate} +\end{enumerate} La fonction $d$ peut se formaliser comme suit: @@ -606,8 +611,10 @@ $\check{s}=\left\{ \check{v}=2,1,... \end{array} \right.$. - -Ainsi $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$ +Ainsi +\[ +d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = +0.01~0004000000000000000000~01~1005 \dots\] En effet, les $p=2$ premiers éléments sont 01, c'est-à-dire $|v^0-\check{v}^0|=1$, et on utilise $p$ éléments pour représenter cette différence @@ -621,35 +628,35 @@ la chaîne obtenue a $n\times \max{(\mathcal{P})}=22$ éléments, soit: De manière similaire, les $\check{v}^0=2$ premiers termes de $\check{u}$ sont représentés par 0604000000000000000000. -LA valeur absolue de leur différence est égale à +La valeur absolue de leur différence est égale à 0004000000000000000000. Ces éléments sont concaténés avec 01. On peut construire alors le reste de la séquence. \end{xpl} -\begin{xpl} -On considère à présent que $\mathsf{N}=9$, que $\mathcal{P}=\{2,7\}$ et que -$$s=\left\{ -\begin{array}{l} -u=\underline{6,7,} ~ \underline{4,2,} ...\\ -v=2,2,... -\end{array} -\right.$$ -avec -$$\check{s}=\left\{ -\begin{array}{l} -\check{u}=\underline{4, 9, 6, 3, 6, 6, 7,} ~ \underline{9, 8}, ...\\ -\check{v}=7,2,... -\end{array} -\right. -$$ +% \begin{xpl} +% On considère à présent que $\mathsf{N}=9$, que $\mathcal{P}=\{2,7\}$ et que +% $$s=\left\{ +% \begin{array}{l} +% u=\underline{6,7,} ~ \underline{4,2,} ...\\ +% v=2,2,... +% \end{array} +% \right.$$ +% avec +% $$\check{s}=\left\{ +% \begin{array}{l} +% \check{u}=\underline{4, 9, 6, 3, 6, 6, 7,} ~ \underline{9, 8}, ...\\ +% \check{v}=7,2,... +% \end{array} +% \right. +% $$ -Ainsi $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, -puisque -$|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$, -et $|9800000-4200000| = 5600000$. -\end{xpl} +% Ainsi $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, +% puisque +% $|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$, +% et $|9800000-4200000| = 5600000$. +% \end{xpl} @@ -668,8 +675,9 @@ définit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suiva %\item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples % having their elements in $\llbracket 1, \mathsf{N} \rrbracket $. \item il y a un arc libellé $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ entre les n{\oe}uds $x$ et $y$ si et seulement si $p_i$ est un élément de -$\mathcal{P}$ (\textit{i.e.}, on peut itérer $p_i$ fois), -chaque $u_k$ de la suite appartient à $[\mathsf{N}]$ et +$\mathcal{P}$ (\textit{i.e.}, on peut itérer $p_i$ fois), et pour chaque +$k$, $0 \le k \le p_i-1$, on a + $u_k$ qui apaprtient à $[\mathsf{N}]$ et $y=F_{f_u,p_i} (x, (u_0, \hdots, u_{p_i-1})) $. \end{itemize} Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{giu}(f)$. @@ -683,7 +691,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g \subfigure[$\textsc{giu}_{\{2\}}(h)$]{ \begin{minipage}{0.30\textwidth} \begin{center} - \includegraphics[height=4cm]{images/h2prng} + \includegraphics[scale=0.5]{images/h2prng} \end{center} \end{minipage} \label{fig:h2prng} @@ -691,7 +699,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g \subfigure[$\textsc{giu}_{\{3\}}(h)$]{ \begin{minipage}{0.40\textwidth} \begin{center} - \includegraphics[height=4cm]{images/h3prng} + \includegraphics[scale=0.5]{images/h3prng} \end{center} \end{minipage} \label{fig:h3prng} @@ -699,7 +707,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{ \begin{minipage}{0.40\textwidth} \begin{center} - \includegraphics[height=4cm]{images/h23prng} + \includegraphics[scale=0.5]{images/h23prng} \end{center} \end{minipage} \label{fig:h23prng} @@ -732,7 +740,7 @@ Le dernier donnerait le comportement d'un générateur qui s'autoriserait \subsection{le PRNG de l'algorithme~\ref{CI Algorithm} est chaotique sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$} -Le théorème suivant, similaire à celui dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$ +Le théorème suivant, similaire à ceux dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$ est prouvé en annexes~\ref{anx:generateur}. \begin{theorem} @@ -751,7 +759,7 @@ On alors corollaire suivant \end{corollary} \begin{proof} Dans cet algorithme, $\mathcal{P}$ est le singleton $\{b\}$. - Que $b$ soit pair ou impair, $\textsc{giu}_{\mathcal{b}}(f)$ + Que $b$ soit pair ou impair, $\textsc{giu}_{\{b\}}(f)$ n'est pas fortement connexe. \end{proof} diff --git a/chaosANN.tex b/chaosANN.tex index 4ea34b9..89ac939 100644 --- a/chaosANN.tex +++ b/chaosANN.tex @@ -1,6 +1,6 @@ Les réseaux de neurones chaotiques ont été étudiés à de maintes reprises -par le passé en raison notamment de leurs applications potentielles: +en raison de leurs applications potentielles: %les mémoires associatives~\cite{Crook2007267} les composants utiles à la sécurité comme les fonctions de hachage~\cite{Xiao10}, @@ -20,7 +20,7 @@ universels~\cite{Cybenko89,DBLP:journals/nn/HornikSW89}. Ils permettent, dans certains cas, de simuler des comportements physiques chaotiques comme le circuit de Chua~\cite{dalkiran10}. Parfois~\cite{springerlink:10.1007/s00521-010-0432-2}, -la fonction de transfert de cette famille de réseau celle +la fonction de transfert de cette famille de réseau et celle d'initialisation sont toutes les deux définies à l'aide de fonctions chaotiques. @@ -28,7 +28,8 @@ fonctions chaotiques. Ces réseaux de neurones partagent le fait qu'ils sont qualifiés de ``chaotiques'' sous prétexte qu'ils embarquent une fonction de ce type -et ce sans aucune preuve rigoureuse. Ce chapitre caractérise la +et ce sans aucune preuve rigoureuse ne soit fournie. +Ce chapitre caractérise la classe des réseaux de neurones MLP chaotiques. Il s'intéresse ensuite à l'étude de prévisibilité de systèmes dynamiques discrets chaotiques par cette famille de MLP. @@ -39,21 +40,22 @@ de vérification si un réseau de neurones est chaotique ou non. La section~\ref{sec:ann:approx} s'intéresse à étudier pratiquement si un réseau de neurones peut approximer des itération unaires chaotiques. Ces itérations -étant obtenues à partir de fonction générées à l'aide du chapitre précédent. - +étant obtenues à partir de fonctions issues de la démarche détaillée dans +le chapitre précédent. +Ce travail a été publié dans~\cite{bcgs12:ij}. \section{Un réseau de neurones chaotique au sens de Devaney} \label{S2} On considère une fonction -$f:\Bool^n\to\Bool^n$ telle que $\textsc{giu}(f)$ est fortement connexe. +$f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$ telle que $\textsc{giu}(f)$ est fortement connexe. Ainsi $G_{f_u}$ est chaotique d'après le théorème~\ref{Th:CaracIC}. On considère ici le schéma unaire défini par l'équation (\ref{eq:asyn}). On construit un Perceptron multi-couches associé à la fonction $F_{f_u}$. Plus précisément, pour chaque entrée - $(x,s) \in \mathds{B}^n \times [n]$, + $(x,s) \in \mathds{B}^{\mathsf{N}} \times [{\mathsf{N}}]$, la couche de sortie doit générer $F_{f_u}(x,s)$. On peut ainsi lier la couche de sortie avec celle d'entrée pour représenter les dépendance entre deux itérations successives. @@ -62,18 +64,18 @@ On obtient une réseau de neurones dont le comportement est le suivant \begin{itemize} \item Le réseau est initialisé avec le vecteur d'entrée - $\left(x^0,S^0\right) \mathds{B}^n \times [n]$ + $\left(x^0,S^0\right) \mathds{B}^{\mathsf{N}} \times [{\mathsf{N}}]$ et calcule le vecteur de sortie $x^1=F_{f_u}\left(x^0,S^0\right)$. - Ce vecteur est publié comme une sortie et est aussi retournée sur la couche d'entrée + Ce vecteur est publié comme une sortie et est aussi retourné sur la couche d'entrée à travers les liens de retours. \item Lorsque le réseau est activé à la $t^{th}$ itération, l'état du - système $x^t \in \mathds{B}^n$ reçu depuis la couche de sortie ainsi que le + système $x^t \in \mathds{B}^{\mathsf{N}}$ reçu depuis la couche de sortie ainsi que le premier terme de la séquence $(S^t)^{t \in \Nats}$ - (\textit{i.e.}, $S^0 \in [n]$) servent à construire le nouveau vecteur de sortie. + (\textit{i.e.}, $S^0 \in [{\mathsf{N}}]$) servent à construire le nouveau vecteur de sortie. Ce nouveau vecteur, qui représente le nouvel état du système dynamique, satisfait: \begin{equation} - x^{t+1}=F_{f_u}(x^t,S^0) \in \mathds{B}^n \enspace . + x^{t+1}=F_{f_u}(x^t,S^0) \in \mathds{B}^{\mathsf{N}} \enspace . \end{equation} \end{itemize} @@ -85,7 +87,7 @@ On obtient une réseau de neurones dont le comportement est le suivant \end{figure} Le comportement de ce réseau de neurones est tel que lorsque l'état -initial est composé de $x^0~\in~\mathds{B}^n$ et d'une séquence +initial est composé de $x^0~\in~\mathds{B}^{\mathsf{N}}$ et d'une séquence $(S^t)^{t \in \Nats}$, alors la séquence contenant les vecteurs successifs publiés $\left(x^t\right)^{t \in \mathds{N}^{\ast}}$ est exactement celle produite par les itérations unaires décrites à la section~\ref{sec:TIPE12}. @@ -102,41 +104,44 @@ réseau de neurones de type Perceptron multi-couches dont on cherche à savoir s'il est chaotique (parce qu'il a par exemple été déclaré comme tel) au sens de Devaney. On considère de plus que sa topologie est la suivante: -l'entrée est constituée de $n$ bits et un entier, la sortie est constituée de $n$ bits +l'entrée est constituée de ${\mathsf{N}}$ bits et un entier, +la sortie est constituée de ${\mathsf{N}}$ bits et chaque sortie est liée à une entrée par une boucle. \begin{itemize} -\item Le réseau est initialisé avec $n$~bits - $\left(x^0_1,\dots,x^0_n\right)$ et une valeur entière $S^0 \in [n]$. +\item Le réseau est initialisé avec ${\mathsf{N}}$~bits + $\left(x^0_1,\dots,x^0_{\mathsf{N}}\right)$ et une valeur entière $S^0 \in [{\mathsf{N}}]$. \item A l'itération~$t$, le vecteur - $\left(x^t_1,\dots,x^t_n\right)$ permet de construire les $n$~bits - servant de sortie $\left(x^{t+1}_1,\dots,x^{t+1}_n\right)$. + $\left(x^t_1,\dots,x^t_{\mathsf{N}}\right)$ permet de construire les ${\mathsf{N}}$~bits + servant de sortie $\left(x^{t+1}_1,\dots,x^{t+1}_{\mathsf{N}}\right)$. \end{itemize} Le comportement de ce type de réseau de neurones peut être prouvé comme -étant chaotique en suivant la démarche énoncée maintenant. -On nomme tout d'abord $F: \mathds{B}^n \times [n] \rightarrow -\mathds{B}^n$ la fonction qui associe +étant chaotique en suivant la démarche suivante. +On nomme tout d'abord $F: \mathds{B}^{\mathsf{N}} \times [{\mathsf{N}}] \rightarrow +\mathds{B}^{\mathsf{N}}$ la fonction qui associe au vecteur -$\left(\left(x_1,\dots,x_n\right),s\right) \in \mathds{B}^n \times[n]$ +$\left(\left(x_1,\dots,x_{\mathsf{N}}\right),s\right) \in \mathds{B}^{\mathsf{N}} \times[{\mathsf{N}}]$ le vecteur -$\left(y_1,\dots,y_n\right) \in \mathds{B}^n$, où -$\left(y_1,\dots,y_n\right)$ sont les sorties du réseau neuronal +$\left(y_1,\dots,y_{\mathsf{N}}\right) \in \mathds{B}^{\mathsf{N}}$, où +$\left(y_1,\dots,y_{\mathsf{N}}\right)$ sont les sorties du réseau neuronal après l'initialisation de la couche d'entrée avec -$\left(s,\left(x_1,\dots, x_n\right)\right)$. Ensuite, on définie $f: -\mathds{B}^n \rightarrow \mathds{B}^n$ telle que -$f\left(x_1,x_2,\dots,x_n\right)$ est égal à +$\left(s,\left(x_1,\dots, x_{\mathsf{N}}\right)\right)$. Ensuite, on définie $f: +\mathds{B}^{\mathsf{N}} \rightarrow \mathds{B}^{\mathsf{N}}$ telle que +$f\left(x_1,x_2,\dots,x_{\mathsf{N}}\right)$ est égal à \begin{equation} -\left(F\left(\left(x_1,x_2,\dots,x_n\right),1\right),\dots, - F\left(\left(x_1,x_2,\dots,x_n\right)\right),n\right) \enspace . +\left( + F\left(\left(x_1,x_2,\dots,x_{\mathsf{N}}\right),1\right),\dots, + F\left(\left(x_1,x_2,\dots,x_{\mathsf{N}}\right),{\mathsf{N}}\right) +\right). \end{equation} -Ainsi pour chaque $j$, $1 \le j \le n$, on a -$f_j\left(x_1,x_2,\dots,x_n\right) = -F\left(\left(x_1,x_2,\dots,x_n\right),j\right)$. +Ainsi pour chaque $j$, $j \in [{\mathsf{N}}]$, on a +$f_j\left(x_1,x_2,\dots,x_{\mathsf{N}}\right) = +F\left(\left(x_1,x_2,\dots,x_{\mathsf{N}}\right),j\right)$. Si ce réseau de neurones est initialisé avec -$\left(x_1^0,\dots,x_n^0\right)$ et $S \in [n]^{\mathds{N}}$, +$\left(x_1^0,\dots,x_{\mathsf{N}}^0\right)$ et $S \in [{\mathsf{N}}]^{\mathds{N}}$, il produit exactement les même sorties que les itérations de $F_{f_u}$ avec une -condition initiale $\left((x_1^0,\dots, x_n^0),S\right) \in \mathds{B}^n \times [n]^{\mathds{N}}$. +condition initiale $\left((x_1^0,\dots, x_{\mathsf{N}}^0),S\right) \in \mathds{B}^{\mathsf{N}} \times [{\mathsf{N}}]^{\mathds{N}}$. Les itérations de $F_{f_u}$ sont donc un modèle formel de cette classe de réseau de neurones. Pour vérifier si un de ces représentants est chaotique, il suffit ainsi @@ -144,7 +149,7 @@ de vérifier si le graphe d'itérations $\textsc{giu}(f)$ est fortement connexe. -\section{Un réseau de neurones peut-il approximer +\section[Approximation des itérations unaires chaotiques par RN]{Un réseau de neurones peut-il approximer des itération unaires chaotiques?}\label{sec:ann:approx} Cette section s'intéresse à étudier le comportement d'un réseau de neurones @@ -152,7 +157,7 @@ face à des itérations unaires chaotiques, comme définies à la section~\ref{sec:TIPE12}. Plus précisément, on considère dans cette partie une fonction dont le graphe des itérations unaires est fortement connexe et une séquence dans -$[n]^{\mathds{N}}$. On cherche à construire un réseau de neurones +$[{\mathsf{N}}]^{\mathds{N}}$. On cherche à construire un réseau de neurones qui approximerait les itérations de la fonction $G_{f_u}$ comme définie à l'équation~(\ref{eq:sch:unaire}). @@ -191,11 +196,11 @@ mémoriser des configurations. On en considère deux principalement. Dans le premier cas, on considère une entrée booléenne par élément tandis que dans le second cas, les configurations sont mémorisées comme des entiers naturels. Dans ce dernier cas, une approche naïve pourrait -consister à attribuer à chaque configuration de $\Bool^n$ +consister à attribuer à chaque configuration de $\Bool^{\mathsf{N}}$ l'entier naturel naturel correspondant. Cependant, une telle représentation rapproche arbitrairement des configurations diamétralement -opposées dans le $n$-cube comme une puissance de +opposées dans le ${\mathsf{N}}$-cube comme une puissance de deux et la configuration immédiatement précédente: 10000 serait modélisée par 16 et et 01111 par 15 alors que leur distance de Hamming est 15. De manière similaire, ce codage éloigne des configurations qui sont @@ -207,13 +212,13 @@ Concentrons nous sur la traduction de la stratégie. Il n'est naturellement pas possible de traduire une stratégie infinie quelconque à l'aide d'un nombre fini d'éléments. On se restreint donc à des stratégies de taille -$l \in \llbracket 2,k\rrbracket$, où $k$ est un paramètre défini +$l$, $2 \le l \le k$, où $k$ est un paramètre défini initialement. Chaque stratégie est mémorisée comme un entier naturel exprimé en base -$n+1$: à chaque itération, soit aucun élément n'est modifié, soit un +${\mathsf{N}}+1$: à chaque itération, soit aucun élément n'est modifié, soit un élément l'est. -Enfin, on donne une dernière entrée: $m \in \llbracket -1,l-1\rrbracket$, qui est le nombre d'itérations successives que l'on applique +Enfin, on donne une dernière entrée: $m \in [l-1] +$, qui est le nombre d'itérations successives que l'on applique en commençant à $x$. Les sorties (stratégies et configurations) sont mémorisées selon les mêmes règles. @@ -221,33 +226,33 @@ selon les mêmes règles. Concentrons nous sur la complexité du problème. Chaque entrée, de l'entrée-sortie de l'outil est un triplet composé d'une configuration $x$, d'un extrait $S$ de la stratégie à -itérer de taille $l \in \llbracket 2, k\rrbracket$ et d'un nombre $m \in \llbracket 1, l-1\rrbracket$ d'itérations à exécuter. -Il y a $2^n$ configurations $x$ et $n^l$ stratégies de +itérer de taille $l$, $2 \le l \le k$ et d'un nombre $m \in [l-1]$ d'itérations à exécuter. +Il y a $2^{\mathsf{N}}$ configurations $x$ et ${\mathsf{N}}^l$ stratégies de taille $l$. De plus, pour une configuration donnée, il y a -$\omega = 1 \times n^2 + 2 \times n^3 + \ldots+ (k-1) \times n^k$ +$\omega = 1 \times {\mathsf{N}}^2 + 2 \times {\mathsf{N}}^3 + \ldots+ (k-1) \times {\mathsf{N}}^k$ manières d'écrire le couple $(m,S)$. Il n'est pas difficile d'établir que \begin{equation} -\displaystyle{(n-1) \times \omega = (k-1)\times n^{k+1} - \sum_{i=2}^k n^i} \nonumber +\displaystyle{({\mathsf{N}}-1) \times \omega = (k-1)\times {\mathsf{N}}^{k+1} - \sum_{i=2}^k {\mathsf{N}}^i} \nonumber \end{equation} donc \begin{equation} \omega = -\dfrac{(k-1)\times n^{k+1}}{n-1} - \dfrac{n^{k+1}-n^2}{(n-1)^2} \enspace . \nonumber +\dfrac{(k-1)\times {\mathsf{N}}^{k+1}}{{\mathsf{N}}-1} - \dfrac{{\mathsf{N}}^{k+1}-{\mathsf{N}}^2}{({\mathsf{N}}-1)^2} \enspace . \nonumber \end{equation} \noindent Ainsi le nombre de paire d'entrée-sortie pour les réseaux de neurones considérés est $$ -2^n \times \left(\dfrac{(k-1)\times n^{k+1}}{n-1} - \dfrac{n^{k+1}-n^2}{(n-1)^2}\right) \enspace . +2^{\mathsf{N}} \times \left(\dfrac{(k-1)\times {\mathsf{N}}^{k+1}}{{\mathsf{N}}-1} - \dfrac{{\mathsf{N}}^{k+1}-{\mathsf{N}}^2}{({\mathsf{N}}-1)^2}\right) \enspace . $$ Par exemple, pour $4$ éléments binaires et une stratégie d'au plus $3$~termes on obtient 2304 couples d'entrée-sortie. \subsection{Expérimentations} -\label{section:experiments} -On se focalise dans cette section sur l'entraînement d'un Perceptron -multi-couches pour apprendre des itérations chaotiques. Ce type de réseau +\label{section:ann:experiments} +On se focalise dans cette section sur l'entraînement d'un MLP +pour apprendre des itérations chaotiques. Ce type de réseau ayant déjà été évalué avec succès dans la prédiction de séries chaotiques temporelles. En effet, les auteurs de~\cite{dalkiran10} ont montré qu'un MLP pouvait apprendre la dynamique du circuit de Chua. @@ -274,39 +279,40 @@ section précédente. \hline \hline \multicolumn{2}{|c||}{Neurones cachés} & \multicolumn{3}{c|}{10 neurones} \\ -\cline{3-5} +\hline \multicolumn{2}{|c||}{Epochs} & 125 & 250 & 500 \\ \hline -\multirow{6}{*}{\rotatebox{90}{Chaotique $g$ }}&Entrée~(1) & 90.92\% & 91.75\% & 91.82\% \\ -& Entrée~(2) & 69.32\% & 78.46\% & 82.15\% \\ -& Entrée~(3) & 68.47\% & 78.49\% & 82.22\% \\ -& Entrée~(4) & 91.53\% & 92.37\% & 93.4\% \\ +\multirow{6}{*}{\rotatebox{90}{Chaotique $g$ }}&Sortie~(1) & 90.92\% & 91.75\% & 91.82\% \\ +& Sortie~(2) & 69.32\% & 78.46\% & 82.15\% \\ +& Sortie~(3) & 68.47\% & 78.49\% & 82.22\% \\ +& Sortie~(4) & 91.53\% & 92.37\% & 93.4\% \\ & Config. & 36.10\% & 51.35\% & 56.85\% \\ & Stratégie~(5) & 1.91\% & 3.38\% & 2.43\% \\ \hline -\multirow{6}{*}{\rotatebox{90}{Non-chaotic $f$}}&Entrée~(1) & 97.64\% & 98.10\% & 98.20\% \\ -& Entrée~(2) & 95.15\% & 95.39\% & 95.46\% \\ -& Entrée~(3) & 100\% & 100\% & 100\% \\ -& Entrée~(4) & 97.47\% & 97.90\% & 97.99\% \\ +\multirow{6}{*}{\rotatebox{90}{Non-chaotic $f$}}&Sortie~(1) & 97.64\% & 98.10\% & 98.20\% \\ +& Sortie~(2) & 95.15\% & 95.39\% & 95.46\% \\ +& Sortie~(3) & 100\% & 100\% & 100\% \\ +& Sortie~(4) & 97.47\% & 97.90\% & 97.99\% \\ & Config. & 90.52\% & 91.59\% & 91.73\% \\ & Stratégie~(5) & 3.41\% & 3.40\% & 3.47\% \\ \hline \hline \multicolumn{2}{|c||}{Neurones cachés} & \multicolumn{3}{c|}{25 neurones} \\ -\cline{3-5} \\%& \multicolumn{3}{|c|}{40 neurons} \\ +%\cline{3-5} \\%& \multicolumn{3}{|c|}{40 neurons} \\ +\hline \multicolumn{2}{|c||}{Epochs} & 125 & 250 & 500 \\ %& 125 & 250 & 500 \\ \hline -\multirow{6}{*}{\rotatebox{90}{Chaotique $g$}}&Entrée~(1) & 91.65\% & 92.69\% & 93.93\% \\ %& 91.94\% & 92.89\% & 94.00\% \\ -& Entrée~(2) & 72.06\% & 88.46\% & 90.5\% \\ %& 74.97\% & 89.83\% & 91.14\% \\ -& Entrée~(3) & 79.19\% & 89.83\% & 91.59\% \\ %& 76.69\% & 89.58\% & 91.84\% \\ -& Entrée~(4) & 91.61\% & 92.34\% & 93.47\% \\% & 82.77\% & 92.93\% & 93.48\% \\ +\multirow{6}{*}{\rotatebox{90}{Chaotique $g$}}&Sortie~(1) & 91.65\% & 92.69\% & 93.93\% \\ %& 91.94\% & 92.89\% & 94.00\% \\ +& Sortie~(2) & 72.06\% & 88.46\% & 90.5\% \\ %& 74.97\% & 89.83\% & 91.14\% \\ +& Sortie~(3) & 79.19\% & 89.83\% & 91.59\% \\ %& 76.69\% & 89.58\% & 91.84\% \\ +& Sortie~(4) & 91.61\% & 92.34\% & 93.47\% \\% & 82.77\% & 92.93\% & 93.48\% \\ & Config. & 48.82\% & 67.80\% & 70.97\% \\%& 49.46\% & 68.94\% & 71.11\% \\ & Stratégie~(5) & 2.62\% & 3.43\% & 3.78\% \\% & 3.10\% & 3.10\% & 3.03\% \\ \hline -\multirow{6}{*}{\rotatebox{90}{Non-chaotique $f$}}&Entrée~(1) & 97.87\% & 97.99\% & 98.03\% \\ %& 98.16\% \\ -& Entrée~(2) & 95.46\% & 95.84\% & 96.75\% \\ % & 97.4\% \\ -& Entrée~(3) & 100\% & 100\% & 100\% \\%& 100\% \\ -& Entrée~(4) & 97.77\% & 97.82\% & 98.06\% \\%& 98.31\% \\ +\multirow{6}{*}{\rotatebox{90}{Non-chaotique $f$}}&Sortie~(1) & 97.87\% & 97.99\% & 98.03\% \\ %& 98.16\% \\ +& Sortie~(2) & 95.46\% & 95.84\% & 96.75\% \\ % & 97.4\% \\ +& Sortie~(3) & 100\% & 100\% & 100\% \\%& 100\% \\ +& Sortie~(4) & 97.77\% & 97.82\% & 98.06\% \\%& 98.31\% \\ & Config. & 91.36\% & 91.99\% & 93.03\% \\%& 93.98\% \\ & Stratégie~(5) & 3.37\% & 3.44\% & 3.29\% \\%& 3.23\% \\ \hline @@ -412,7 +418,8 @@ réseau de neurones d'apprendre le comportement global d'itérations chaotiques. Comme il est difficile (voir impossible) d'apprendre le comportement de telles fonction, il paraît naturelle de savoir si celles ci peuvent être -utilisées pour générer des nombres pseudo aléatoires. +utilisées pour générer des nombres pseudo aléatoires, ce que propose la partie +suivante. % \appendix{} -- 2.39.5