retouche preuve gray

[hdrcouchot.git] / chaosANN.tex

Les réseaux de neurones chaotiques ont été étudiés à de maintes reprises 
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},
le tatouage numérique~\cite{1309431,Zhang2005759}
ou les schémas de chiffrement~\cite{Lian20091296}.  
Dans tous ces cas, l'emploi de fonctions chaotiques est motivé par 
leur comportement imprévisible et proche de l'aléa. 


Les réseaux de neurones chaotiques peuvent être conçus selon plusieurs 
principes. Des neurones modifiant leur état en suivant une fonction non 
linéaire son par exemple appelés neurones chaotiques~\cite{Crook2007267}.
L'architecture de réseaux de neurones de type Perceptron multi-couches
(MLP) n'itèrent quant à eux, pas nécessairement de fonctions chaotiques.
Il a cependant été démontré  que ce sont des approximateurs 
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 et celle 
d'initialisation sont toutes les deux définies à l'aide de 
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 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.

La section~\ref{S2} définit la construction d'un réseau de neurones 
chaotique selon Devanay. La section~\ref{S3} présente l'approche duale 
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 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^{\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}^{\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.
On obtient une réseau de neurones dont le comportement est le suivant 
(voir Figure.~\ref{Fig:perceptron}):

\begin{itemize}
\item   Le réseau est initialisé avec le vecteur d'entrée
  $\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é 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}^{\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 [{\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}^{\mathsf{N}} \enspace .
  \end{equation}
\end{itemize}

\begin{figure}
  \centering
  \includegraphics[scale=0.625]{images/perceptron}
  \caption{Un Perceptron équivalent  aux itérations unitaires}
  \label{Fig:perceptron}
\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}^{\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}.
Mathématiquement, cela signifie que si on utilise les mêmes vecteurs d'entrées
les deux approches génèrent successivement les mêmes sorties.
En d'autres termes ce réseau de neurones modélise le comportement de  
$G_{f_u}$,  dont les itérations sont chaotiques sur $\mathcal{X}_u$.
On peut donc le  qualifier de chaotique au sens de Devaney.

\section{Vérifier si un réseau de neurones est chaotique}
\label{S3}
On s'intéresse maintenant au cas où l'on dispose d'un
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  ${\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  ${\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_{\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 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_{\mathsf{N}}\right),s\right)    \in   \mathds{B}^{\mathsf{N}} \times[{\mathsf{N}}]$ 
le vecteur 
$\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_{\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_{\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$, $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_{\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_{\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 
de vérifier si le graphe d'itérations
$\textsc{giu}(f)$ est fortement connexe.


\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 
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 
$[{\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}).

Sans perte de généralité, on considère dans ce qui suit une instance
de de fonction à quatre éléments.

\subsection{Construction du réseau} 
\label{section:translation}

On considère par exemple les deux fonctions $f$ and $g$ de $\Bool^4$
dans $\Bool^4$ définies par:

\begin{eqnarray*}
f(x_1,x_2,x_3,x_4) &= &
(x_1(x_2+x_4)+ \overline{x_2}x_3\overline{x_4},
x_2,
x_3(\overline{x_1}.\overline{x_4}+x_2x_4+x_1\overline{x_2}),
x_4+\overline{x_2}x_3) \\
g(x_1,x_2,x_3,x_4) &= &
(\overline{x_1},
\overline{x_2}+ x_1.\overline{x_3}.\overline{x_4},
\overline{x_3}(x_1 + x_2+x_4),
\overline{x_4}(x_1 + \overline{x_2}+\overline{x_3}))
\end{eqnarray*}
On peut vérifier facilement que le graphe $\textsc{giu}(f)$ 
n'est pas fortement connexe car $(1,1,1,1)$ est un point fixe de $f$
tandis que le graphe $\textsc{giu}(g)$ l'est.   

L'entrée du réseau est une paire de la forme 
$(x,(S^t)^{t  \in  \Nats})$ et sa sortie correspondante est
de la forme  $\left(F_{h_u}(S^0,x), \sigma((S^t)^{t          \in
  \Nats})\right)$ comme définie à l'équation~(\ref{eq:sch:unaire}).

On s'intéresse d'abord aux différentes manières de  
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^{\mathsf{N}}$ 
l'entier naturel naturel correspondant.
Cependant, une telle représentation rapproche 
arbitrairement des configurations diamétralement
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 
très proches: par exemple 10000 et 00000 ont une distance de Hamming 
de 1 et sont respectivement représentées par 16 et 0.
Pour ces raisons, le codage retenu est celui des codes de Gray~\cite{Gray47}.

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$, $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 
${\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 [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.

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$, $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 {\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{({\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 {\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^{\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: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.
Ce réseau avec rétropropagation est composé de  deux couches 
et entraîné à l'aide d'une  propagation arrière Bayesienne.

Le choix de l'architecture du réseau ainsi que de la méthode d'apprentissage 
ont été détaillé dans~\cite{bcgs12:ij}.
En pratique, nous avons considéré des configurations de
quatre éléments booléens 
et une stratégie fixe de longueur 3.
Pour le premier codage, nous avons ainsi 6~entrées et 5~sorties
tandis que pour le second, uniquement  3 entrées et 2 sorties.
Cela engendre ainsi 2304~combinaisons possibles comme détaillé à la 
section précédente.



\begin{table}[htbp!]
\centering {\small
\begin{tabular}{|c|c||c|c|c|}
\hline 
\multicolumn{5}{|c|}{Topologie du réseau: 6~entrées, 5~sorties, 1~couche cachée} \\
\hline
\hline
\multicolumn{2}{|c||}{Neurones cachés} & \multicolumn{3}{c|}{10 neurones} \\
\hline
\multicolumn{2}{|c||}{Epochs} & 125 & 250 & 500 \\ 
\hline
\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$}}&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} \\
\hline
\multicolumn{2}{|c||}{Epochs} & 125 & 250 & 500 \\ %& 125 & 250 & 500 \\ 
\hline
\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$}}&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
\end{tabular}
}
\caption{Taux de prédiction lorsque les configurations sont exprimées comme un vecteur booléen.}
\label{tab1}
\end{table}
Le tableau~\ref{tab1} synthétise les résultats obtenus avec le premier 
codage. Sans surprise, la précision de la prédiction croit 
avec l'Epoch et le nombre de neurones sur la couche cachée.
Dans tous les cas, les résultats sont plus précis dans le cas non 
chaotique que dans l'autre. Enfin, le réseau ne parvient jamais à
apprendre le comportement de la stratégie.

\begin{table}[b]
\centering
\begin{tabular}{|c|c||c|c|c|}
\hline 
\multicolumn{5}{|c|}{Topologie du réseau: 3~entrées, 2~sorties, 1~couche cachée} \\
\hline
\hline
& Neurones cachés & \multicolumn{3}{c|}{10 neurones} \\
\cline{2-5}
& Epochs & 125 & 250 & 500 \\ %& 1000 
\hline
\multirow{2}{*}{Chaotique $g$}& Config.~(1) & 13.29\% & 13.55\% & 13.08\% \\ %& 12.5\%
& Stratégie~(2) & 0.50\% & 0.52\% & 1.32\% \\ %& 1.42\%
\hline
\multirow{2}{*}{Non-Chaotique $f$}&Config.~(1) & 77.12\% & 74.00\% & 72.60\% \\ %& 75.81\% 
& Stratégie~(2) & 0.42\% & 0.80\% & 1.16\% \\ %& 1.42\% 
\hline
\hline
& Neurones cachés& \multicolumn{3}{c|}{25 neurones} \\
\cline{2-5}
& Epochs & 125 & 250 & 500 \\ %& 1000 
\hline
\multirow{2}{*}{Chaotique $g$ }& Config.~(1) & 12.27\% & 13.15\% & 13.05\% \\ %& 15.44\%
& Stratégie~(2) & 0.71\% & 0.66\% & 0.88\% \\ %& 1.73\%
\hline
\multirow{2}{*}{Non-Chaotique $f$}&Config.~(1) & 73.60\% & 74.70\% & 75.89\% \\ %& 68.32\%
& Stratégie~(2) & 0.64\% & 0.97\% & 1.23\% \\ %& 1.80\%
\hline
\end{tabular}
\caption{Taux de prédiction lorsque les configurations sont exprimées 
à l'aide de codes de Gray.}
\label{tab2}
\end{table}



Les résultats concernant le second codage  (\textit{i.e.},  avec les codes
de   Gray) sont synthétisés dans le tableau~\ref{tab2}. On constate 
que le réseau apprend cinq fois mieux les comportement non chaotiques
que ceux qui le sont. Ceci est est illustré au travers des 
figures~\ref{Fig:chaotic_predictions} et~\ref{Fig:non-chaotic_predictions}.
De plus, comme dans le codage précédent, les stratégies ne peuvent pas être 
prédites.  
On constate que ce second codage réduit certes le nombre de sorties, mais est 
largement moins performant que le premier.
On peut expliquer ceci par le fait
que ce second codage garantit que deux entiers successifs correspondent 
à deux configurations voisines, \textit{i.e.}, qui ne diffèrent que d'un 
élément.
La réciproque n'est cependant pas établie et deux configurations voisines
peuvent être traduites par des entiers très éloignés et ainsi difficiles 
 à apprendre. 


\begin{figure}[ht]
  \begin{center}
    \subfigure[Fonction chaotique $g$]{
      \begin{minipage}{0.48\textwidth}
        \begin{center}
          \includegraphics[scale=0.37]{images/chaotic_trace2}
        \end{center}
      \end{minipage}
      \label{Fig:chaotic_predictions}
    }
    \subfigure[Fonction non-chaotique $f$]{
      \begin{minipage}{0.48\textwidth}
        \begin{center}
          \includegraphics[scale=0.37]{images/non-chaotic_trace2} 
        \end{center}
      \end{minipage}
      \label{Fig:non-chaotic_predictions}
    }
  \end{center}
  \caption {Prédiction lorsque les configurations sont exprimées 
à l'aide de codes de Gray.}
\end{figure}


\section{Conclusion}
Dans ce chapitre, nous avons établi une similitude entre les itérations 
chaotiques et une famille  de Perceptrons multi-couches.
Nous avons d'abord montré comment  construire un réseau de neurones 
ayant un comportement chaotique.
Nous avons présenté ensuite comment vérifier si un réseau de neurones 
établi était chaotique.
Nous avons enfin montré en pratique qu'il est difficile pour un 
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, ce que propose la partie
suivante.


% \appendix{}

% \begin{Def} \label{def2}
% A continuous function $f$  on a topological space $(\mathcal{X},\tau)$
% is defined  to be  {\emph{topologically transitive}}  if for any  pair of
% open  sets $U$,  $V  \in  \mathcal{X}$ there  exists  
% $k \in
% \mathds{N}^{\ast}$
%  such  that
% $f^k(U) \cap V \neq \emptyset$.
% \end{Def}

%\bibliography{chaos-paper}% Produces the bibliography via BibTeX.

%\end{document}
%
% ****** End of file chaos-paper.tex ******