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écésment, 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
+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{Representing Chaotic Iterations for Neural Networks}
+\subsection{Construction du réseau}
\label{section:translation}
-The problem of deciding whether classical feedforward ANNs are
-suitable to approximate topological chaotic iterations may then be
-reduced to evaluate such neural networks on iterations of functions
-with Strongly Connected Component (SCC)~graph of iterations. To
-compare with non-chaotic iterations, the experiments detailed in the
-following sections are carried out using both kinds of function
-(chaotic and non-chaotic). Let us emphasize on the difference between
-this kind of neural networks and the Chaotic Iterations based
-multilayer peceptron.
-
-We are then left to compute two disjoint function sets that contain
-either functions with topological chaos properties or not, depending
-on the strong connectivity of their iterations graph. This can be
-achieved for instance by removing a set of edges from the iteration
-graph $\Gamma(f_0)$ of the vectorial negation function~$f_0$. One can
-deduce whether a function verifies the topological chaos property or
-not by checking the strong connectivity of the resulting graph of
-iterations.
-
-For instance let us consider the functions $f$ and $g$ from $\Bool^4$
-to $\Bool^4$ respectively defined by the following lists:
-$$[0, 0, 2, 3, 13, 13, 6, 3, 8, 9, 10, 11, 8, 13, 14,
- 15]$$ $$\mbox{and } [11, 14, 13, 14, 11, 10, 1, 8, 7, 6, 5, 4, 3, 2,
- 1, 0] \enspace.$$ In other words, the image of $0011$ by $g$ is
-$1110$: it is obtained as the binary value of the fourth element in
-the second list (namely~14). It is not hard to verify that
-$\Gamma(f)$ is not SCC (\textit{e.g.}, $f(1111)$ is $1111$) whereas
-$\Gamma(g)$ is. The remaining of this section shows how to translate
-iterations of such functions into a model amenable to be learned by an
-ANN. Formally, input and output vectors are pairs~$((S^t)^{t \in
- \Nats},x)$ and $\left(\sigma((S^t)^{t \in
- \Nats}),F_{f}(S^0,x)\right)$ as defined in~Eq.~(\ref{eq:Gf}).
-
-Firstly, let us focus on how to memorize configurations. Two distinct
-translations are proposed. In the first case, we take one input in
-$\Bool$ per component; in the second case, configurations are
-memorized as natural numbers. A coarse attempt to memorize
-configuration as natural number could consist in labeling each
-configuration with its translation into decimal numeral system.
-However, such a representation induces too many changes between a
-configuration labeled by a power of two and its direct previous
-configuration: for instance, 16~(10000) and 15~(01111) are close in a
-decimal ordering, but their Hamming distance is 5. This is why Gray
-codes~\cite{Gray47} have been preferred.
-
-Secondly, let us detail how to deal with strategies. Obviously, it is
-not possible to translate in a finite way an infinite strategy, even
-if both $(S^t)^{t \in \Nats}$ and $\sigma((S^t)^{t \in \Nats})$ belong
-to $\{1,\ldots,n\}^{\Nats}$. Input strategies are then reduced to
-have a length of size $l \in \llbracket 2,k\rrbracket$, where $k$ is a
-parameter of the evaluation. Notice that $l$ is greater than or equal
-to $2$ since we do not want the shift $\sigma$~function to return an
-empty strategy. Strategies are memorized as natural numbers expressed
-in base $n+1$. At each iteration, either none or one component is
-modified (among the $n$ components) leading to a radix with $n+1$
-entries. Finally, we give an other input, namely $m \in \llbracket
-1,l-1\rrbracket$, which is the number of successive iterations that
-are applied starting from $x$. Outputs are translated with the same
-rules.
-
-To address the complexity issue of the problem, let us compute the
-size of the data set an ANN has to deal with. Each input vector of an
-input-output pair is composed of a configuration~$x$, an excerpt $S$
-of the strategy to iterate of size $l \in \llbracket 2, k\rrbracket$,
-and a number $m \in \llbracket 1, l-1\rrbracket$ of iterations that
-are executed.
-
-Firstly, there are $2^n$ configurations $x$, with $n^l$ strategies of
-size $l$ for each of them. Secondly, for a given configuration there
-are $\omega = 1 \times n^2 + 2 \times n^3 + \ldots+ (k-1) \times n^k$
-ways of writing the pair $(m,S)$. Furthermore, it is not hard to
-establish that
+On considère par exemple les deux fonctions $f$ and $g$ de0 $\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^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
+deux et la configuration immédiatement précédente: 10000 serait modélisée
+par 16 et et 01111 par 15 alros 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 stragté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 parametre 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
+é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
+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èmew.
+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
+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$
+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
\end{equation}
-then
+donc
\begin{equation}
\omega =
\dfrac{(k-1)\times n^{k+1}}{n-1} - \dfrac{n^{k+1}-n^2}{(n-1)^2} \enspace . \nonumber
\end{equation}
-\noindent And then, finally, the number of input-output pairs for our
-ANNs is
+\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 .
$$
-For instance, for $4$ binary components and a strategy of at most
-$3$~terms we obtain 2304~input-output pairs.
+Par exemple, pour $4$ éléments binaires et une stratégie d'au plus
+$3$~termes on obtient 2304 couples d'entrée-sorties.
-\subsection{Experiments}
+\subsection{Expérimentations}
\label{section:experiments}
-
-To study if chaotic iterations can be predicted, we choose to train
-the multilayer perceptron. As stated before, this kind of network is
-in particular well-known for its universal approximation property
-\cite{Cybenko89,DBLP:journals/nn/HornikSW89}. Furthermore, MLPs have
-been already considered for chaotic time series prediction. For
-example, in~\cite{dalkiran10} the authors have shown that a
-feedforward MLP with two hidden layers, and trained with Bayesian
-Regulation back-propagation, can learn successfully the dynamics of
-Chua's circuit.
+On se focalise dans cette section sur l'entraînement d'un perceptron
+multi-couche 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 entrainé à l'aide d'une propagation arrière Bayesienne.
In these experiments we consider MLPs having one hidden layer of
sigmoidal neurons and output neurons with a linear activation
