X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/1863b8b84356fa645dafb42dc9fe4028d825e54f..b7ce5574dead7f7c53fe6362ac1655d8d54fcd0c:/chaosANN.tex?ds=inline

diff --git a/chaosANN.tex b/chaosANN.tex
index cdcd912..22d5258 100644
--- a/chaosANN.tex
+++ b/chaosANN.tex
@@ -164,111 +164,109 @@ 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{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
