X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/dd837d463f86ebb399eb1cac274139e98815fdd1..b7ce5574dead7f7c53fe6362ac1655d8d54fcd0c:/chaosANN.tex?ds=inline diff --git a/chaosANN.tex b/chaosANN.tex index 1754b80..22d5258 100644 --- a/chaosANN.tex +++ b/chaosANN.tex @@ -152,138 +152,121 @@ $\left(x_1^0,\dots,x_n^0\right)$ et $S \in [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}}$. Les itérations de $F_{f_u}$ -sont donc un modèle formel de ce genre de réseau de neurones. -Pour vérifier s'il est chaotique, il suffit ainsi +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{Suitability of Feedforward Neural Networks -for Predicting Chaotic and Non-chaotic Behaviors} - -In the context of computer science different topic areas have an -interest in chaos, as for steganographic -techniques~\cite{1309431,Zhang2005759}. Steganography consists in -embedding a secret message within an ordinary one, while the secret -extraction takes place once at destination. The reverse ({\it i.e.}, -automatically detecting the presence of hidden messages inside media) -is called steganalysis. Among the deployed strategies inside -detectors, there are support vectors -machines~\cite{Qiao:2009:SM:1704555.1704664}, neural -networks~\cite{10.1109/ICME.2003.1221665,10.1109/CIMSiM.2010.36}, and -Markov chains~\cite{Sullivan06steganalysisfor}. Most of these -detectors give quite good results and are rather competitive when -facing steganographic tools. However, to the best of our knowledge -none of the considered information hiding schemes fulfills the Devaney -definition of chaos~\cite{Devaney}. Indeed, one can wonder whether -detectors continue to give good results when facing truly chaotic -schemes. More generally, there remains the open problem of deciding -whether artificial intelligence is suitable for predicting topological -chaotic behaviors. - -\subsection{Representing Chaotic Iterations for Neural Networks} +\section{Un réseau de neurones peut-il approximer un +des itération unaires chaotiques?} + +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{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