X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/chaos1.git/blobdiff_plain/9e6c76e39059d7f227f7ed48ad71195374a2f2a5..refs/heads/master:/main.tex?ds=inline

diff --git a/main.tex b/main.tex
index de92eaa..49564db 100644
--- a/main.tex
+++ b/main.tex
@@ -40,7 +40,7 @@ preprint,%
 \begin{document}
 
 \title[Neural Networks and Chaos]{Neural Networks and Chaos:
-Construction, Evaluation of Chaotic Networks \\
+Construction, Evaluation of Chaotic Networks, \\
 and Prediction of Chaos with Multilayer Feedforward Networks
 }
 
@@ -88,7 +88,6 @@ far more difficult to learn.
 \maketitle
 
 \begin{quotation}
-
 Chaotic neural  networks have received a  lot of attention  due to the
 appealing   properties  of   deterministic   chaos  (unpredictability,
 sensitivity,  and so  on). However,  such networks  are  often claimed
@@ -97,7 +96,7 @@ work  a theoretical  framework based  on the  Devaney's  definition of
 chaos is  introduced.  Starting  with a relationship  between discrete
 iterations  and  Devaney's chaos,  we  firstly  show  how to  build  a
 recurrent  neural network  that is  equivalent  to a  chaotic map  and
-secondly  a way  to check  whether  an already  available network,  is
+secondly  a way  to  check  whether an  already  available network  is
 chaotic  or not.  We  also study  different topological  properties of
 these  truly  chaotic neural  networks.   Finally,  we  show that  the
 learning,  with   neural  networks  having   a  classical  feedforward
@@ -110,7 +109,7 @@ chaotic maps, is far more difficult than non chaotic behaviors.
 \label{S1}
 
 Several research  works have proposed or used  chaotic neural networks
-these last  years.  The  complex dynamics of  such a network  leads to
+these  last years.   The complex  dynamics  of such  networks lead  to
 various       potential      application       areas:      associative
 memories~\cite{Crook2007267}  and  digital  security tools  like  hash
 functions~\cite{Xiao10},                                       digital
@@ -136,8 +135,8 @@ are  suitable to model  nonlinear relationships  between data,  due to
 their            universal            approximator            capacity
 \cite{Cybenko89,DBLP:journals/nn/HornikSW89}.   Thus,   this  kind  of
 networks can  be trained  to model a  physical phenomenon known  to be
-chaotic such as Chua's circuit \cite{dalkiran10}.  Sometimes, a neural
-network  which is build  by combining  transfer functions  and initial
+chaotic such  as Chua's circuit \cite{dalkiran10}.   Sometime a neural
+network, which  is build by  combining transfer functions  and initial
 conditions  that are  both chaotic,  is itself  claimed to  be chaotic
 \cite{springerlink:10.1007/s00521-010-0432-2}.
 
@@ -151,10 +150,10 @@ a  dynamical  system:  ergodicity,   expansivity,  and  so  on.   More
 precisely, in  this paper,  which is an  extension of a  previous work
 \cite{bgs11:ip},   we  establish   the  equivalence   between  chaotic
 iterations  and  a  class  of  globally  recurrent  MLP.   The  second
-contribution is a  study of the converse problem,  indeed we study the
-ability  of classical  multiLayer  perceptrons to  learn a  particular
+contribution is a study of the converse problem, indeed we investigate
+the ability of classical  multilayer perceptrons to learn a particular
 family of discrete chaotic  dynamical systems.  This family is defined
-by a Boolean vector, an update function, and a sequence defining which
+by a Boolean vector, an update function, and a sequence defining the
 component  to  update  at  each  iteration.  It  has  been  previously
 established that  such dynamical systems are  chaotically iterated (as
 it  is defined by  Devaney) when  the chosen  function has  a strongly
@@ -234,14 +233,15 @@ point dependence on initial conditions.
 neighborhood of its future evolution eventually overlap with any other
 given region.  This property implies that a dynamical system cannot be
 broken into simpler subsystems.   Intuitively, its complexity does not
-allow any  simplification.  On the  contrary, a dense set  of periodic
-points is an element of regularity that a chaotic dynamical system has
-to exhibit.
+allow any  simplification.  
 
 However, chaos needs some regularity to ``counteracts'' the effects of
-transitivity.
+transitivity. % Thus, two points close to each other can behave in a completely different manner, the first one visiting the whole space whereas the second one has a regular orbit.
+In the Devaney's formulation, a dense set  of periodic
+points is the element of regularity that a chaotic dynamical system has
+to exhibit.
 %\begin{definition} \label{def3}
-We recall that a  point $x$ is  {\bf periodic point} for $f$ of 
+We recall that a  point $x$ is a {\bf periodic point} for $f$ of 
 period~$n \in \mathds{N}^{\ast}$ if $f^{n}(x)=x$.
 %\end{definition}
 Then, the map 
@@ -261,12 +261,12 @@ Let  us recall  that  $f$  has {\bf  sensitive  dependence on  initial
 $n  > 0$ such  that $d\left(f^{n}(x),  f^{n}(y)\right) >\delta  $. The
 value $\delta$ is called the {\bf constant of sensitivity} of $f$.
 
-Finally,  The  dynamical system  that  iterates  $f$  is {\bf  chaotic
+Finally,  the  dynamical system  that  iterates  $f$  is {\bf  chaotic
   according  to Devaney}  on $(\mathcal{X},\tau)$  if $f$  is regular,
 topologically transitive, and has  sensitive dependence to its initial
 conditions.   In  what follows,  iterations  are  said  to be  chaotic
-according  Devaney  when  corresponding  dynamical system  is  chaotic
-according Devaney.
+(according  to Devaney)  when  the corresponding  dynamical system  is
+chaotic, as it is defined in the Devaney's formulation.
 
 %Let us notice that for a  metric space the last condition follows from
 %the two first ones~\cite{Banks92}.
@@ -311,15 +311,15 @@ $i$ from $x$ to $N(i,x)$ if and only if $f_i(x)$ is $N(i,x)$.
 In the  sequel, the  {\it strategy} $S=(S^{t})^{t  \in \Nats}$  is the
 sequence defining  which component to  update at time $t$  and $S^{t}$
 denotes its $t-$th term.  This iteration scheme that only modifies one
-element at each iteration is classically referred as {\it asynchronous
+element at each iteration is usually referred as {\it asynchronous
   iterations}.  More precisely, we have for any $i$, $1\le i \le n$,
 \begin{equation}
 \left\{ \begin{array}{l}
 x^{0}  \in \Bool^n \\ 
 x^{t+1}_i = \left\{ 
 \begin{array}{l}
-  f_i(x^t) \textrm{ if $S^t = i$} \\
-  x_i^t \textrm{ otherwise} 
+  f_i(x^t) \textrm{ if $S^t = i$}\enspace , \\
+  x_i^t \textrm{ otherwise}\enspace . 
  \end{array}
 \right.
 \end{array} \right.
@@ -373,15 +373,17 @@ X^{k+1}& = & G_{f}(X^{k})\\
 \right.
 \label{eq:Gf}
 \end{equation}
-where  $\sigma$ is the  function that  removes the  first term  of the
-strategy  ({\it  i.e.},~$S^0$).    This  definition  allows  to  links
-asynchronous  iterations  with  classical  iterations of  a  dynamical
+where $\sigma$ is the so-called  shift function that removes the first
+term of  the strategy ({\it i.e.},~$S^0$).  This  definition allows to
+link asynchronous iterations with  classical iterations of a dynamical
 system. Note that it can be extended by considering subsets for $S^t$.
 
 To study topological properties of  these iterations, we are then left
 to  introduce a  {\bf distance}  $d$  between two  points $(S,x)$  and
-$(\check{S},\check{x})\in \mathcal{X} = \llbracket1;n\rrbracket^\Nats
-\times \Bool^{n}$. It is defined by
+$(\check{S},\check{x})$           in           $\mathcal{X}          =
+\llbracket1;n\rrbracket^\Nats \times \Bool^{n}$. Let $\Delta(x,y) = 0$
+if   $x=y$,  and   $\Delta(x,y)  =   1$   else,  be   a  distance   on
+$\mathds{B}$. The distance $d$ is defined by
 \begin{equation}
 d((S,x);(\check{S},\check{x}))=d_{e}(x,\check{x})+d_{s}(S,\check{S})
 \enspace ,
@@ -406,10 +408,10 @@ these  requirements: on  the one  hand  its floor  value reflects  the
 difference between  the cells, on  the other hand its  fractional part
 measures the difference between the strategies.
 
-The relation  between $\Gamma(f)$ and  $G_f$ is clear: there  exists a
+The relation  between $\Gamma(f)$ and  $G_f$ is obvious: there  exists a
 path from  $x$ to $x'$  in $\Gamma(f)$ if  and only if there  exists a
 strategy  $s$ such  that iterations  of $G_f$  from the  initial point
-$(s,x)$   reaches   the   configuration   $x'$.   Using   this   link,
+$(s,x)$   reach   the   configuration   $x'$.   Using   this   link,
 Guyeux~\cite{GuyeuxThese10} has proven that,
 \begin{theorem}%[Characterization of $\mathcal{C}$]
 \label{Th:Caracterisation   des   IC   chaotiques}  
@@ -424,7 +426,7 @@ case, iterations of the function $G_f$ as defined in Eq.~(\ref{eq:Gf})
 are chaotic according to Devaney.
 
 
-Let   us  then   define  two   function  $f_0$   and  $f_1$   both  in
+Let   us  then   define  two   functions  $f_0$   and  $f_1$   both  in
 $\Bool^n\to\Bool^n$ that are used all along this paper.  The former is
 the   vectorial  negation,   \textit{i.e.},  $f_{0}(x_{1},\dots,x_{n})
 =(\overline{x_{1}},\dots,\overline{x_{n}})$.      The     latter    is
@@ -460,9 +462,9 @@ we obtain  a global recurrent  neural network that behaves  as follows
 \item When  the network  is activated at  the $t^{th}$  iteration, the
   state of the system $x^t  \in \mathds{B}^n$ received from the output
   layer and  the initial  term of the  sequence $(S^t)^{t  \in \Nats}$
-  ($S^0  \in \llbracket 1;n\rrbracket$)  are used  to compute  the new
-  output vector.  This  new vector, which represents the  new state of
-  the dynamical system, satisfies:
+  (\textit{i.e.},  $S^0  \in \llbracket  1;n\rrbracket$)  are used  to
+  compute the  new output vector.   This new vector,  which represents
+  the new state of the dynamical system, satisfies:
   \begin{equation}
     x^{t+1}=F_{f_0}(S^0, x^t) \in \mathds{B}^n \enspace .
   \end{equation}
@@ -477,20 +479,17 @@ we obtain  a global recurrent  neural network that behaves  as follows
 
 The behavior of the neural network is such that when the initial state
 is  $x^0~\in~\mathds{B}^n$ and  a  sequence $(S^t)^{t  \in \Nats}$  is
-given  as outside  input,
-\JFC{en dire davantage sur l'outside world} %% TO BE UPDATED
-then  the sequence  of  successive published
+given  as outside  input, then  the sequence  of  successive published
 output vectors $\left(x^t\right)^{t \in \mathds{N}^{\ast}}$ is exactly
 the  one produced  by  the chaotic  iterations  formally described  in
-Eq.~(\ref{eq:Gf}).  It  means that  mathematically if we  use similar
+Eq.~(\ref{eq:Gf}).   It means  that mathematically  if we  use similar
 input  vectors   they  both  generate  the   same  successive  outputs
 $\left(x^t\right)^{t \in \mathds{N}^{\ast}}$,  and therefore that they
 are  equivalent  reformulations  of  the iterations  of  $G_{f_0}$  in
 $\mathcal{X}$. Finally, since the  proposed neural network is built to
-model  the  behavior  of  $G_{f_0}$,  whose iterations are
-  chaotic  according  to
-Devaney's definition  of chaos,  we can conclude  that the  network is
-also chaotic in this sense.
+model  the  behavior  of   $G_{f_0}$,  whose  iterations  are  chaotic
+according to the  Devaney's definition of chaos, we  can conclude that
+the network is also chaotic in this sense.
 
 The previous construction scheme  is not restricted to function $f_0$.
 It can  be extended to any function  $f$ such that $G_f$  is a chaotic
@@ -527,7 +526,6 @@ to an input one.
   compute the new output one $\left(x^{t+1}_1,\dots,x^{t+1}_n\right)$.
   While  the remaining  input receives  a new  integer value  $S^t \in
   \llbracket1;n\rrbracket$, which is provided by the outside world.
-\JFC{en dire davantage sur l'outside world}
 \end{itemize}
 
 The topological  behavior of these  particular neural networks  can be
@@ -558,7 +556,7 @@ condition  $\left(S,(x_1^0,\dots,  x_n^0)\right)  \in  \llbracket  1;n
 \rrbracket^{\mathds{N}}  \times \mathds{B}^n$.
 Theoretically  speaking, such iterations  of $F_f$  are thus  a formal
 model of these kind of recurrent  neural networks. In the rest of this
-paper,  we will  call such  multilayer perceptrons  CI-MLP($f$), which
+paper, we will call such multilayer perceptrons ``CI-MLP($f$)'', which
 stands for ``Chaotic Iterations based MultiLayer Perceptron''.
 
 Checking  if CI-MLP($f$)  behaves chaotically  according  to Devaney's
@@ -640,7 +638,7 @@ of the output space can be discarded when studying CI-MLPs: this space
 is  intrinsically   complicated  and   it  cannot  be   decomposed  or
 simplified.
 
-Furthermore, those  recurrent neural networks  exhibit the instability
+Furthermore, these  recurrent neural networks  exhibit the instability
 property:
 \begin{definition}
 A dynamical  system $\left( \mathcal{X}, f\right)$ is {\bf unstable}
@@ -701,7 +699,7 @@ Figure~\ref{Fig:scheme} is a summary  of addressed neural networks and
 chaos  problems.   In  Section~\ref{S2}   we  have  explained  how  to
 construct    a    truly    chaotic    neural   networks,    $A$    for
 instance. Section~\ref{S3} has shown how  to check whether a given MLP
-$A$ or $C$ is chaotic or not  in the sens of Devaney, and how to study
+$A$ or $C$ is chaotic or not in the sense of Devaney, and how to study
 its  topological  behavior.   The  last  thing  to  investigate,  when
 comparing neural networks and Devaney's chaos, is to determine whether
 an  artificial neural network  $C$ is  able to  learn or  predict some
@@ -720,7 +718,7 @@ 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
+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
@@ -827,7 +825,7 @@ $3$~terms we obtain 2304~input-output pairs.
 \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
+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
@@ -861,10 +859,10 @@ trainings of two data sets, one of them describing chaotic iterations,
 are compared.
 
 Thereafter we give,  for the different learning setups  and data sets,
-the mean prediction success rate obtained for each output. A such rate
-represent the  percentage of input-output pairs belonging  to the test
+the mean prediction success rate obtained for each output. Such a rate
+represents the percentage of  input-output pairs belonging to the test
 subset  for  which  the   corresponding  output  value  was  correctly
-predicted.  These values  are computed  considering  10~trainings with
+predicted.   These values are  computed considering  10~trainings with
 random  subsets  construction,   weights  and  biases  initialization.
 Firstly, neural networks having  10 and 25~hidden neurons are trained,
 with   a  maximum   number  of   epochs  that   takes  its   value  in
@@ -880,7 +878,7 @@ hidden layer up to 40~neurons and we consider larger number of epochs.
 \centering {\small
 \begin{tabular}{|c|c||c|c|c|}
 \hline 
-\multicolumn{5}{|c|}{Networks topology: 6~inputs, 5~outputs and one hidden layer} \\
+\multicolumn{5}{|c|}{Networks topology: 6~inputs, 5~outputs, and one hidden layer} \\
 \hline
 \hline
 \multicolumn{2}{|c||}{Hidden neurons} & \multicolumn{3}{c|}{10 neurons} \\
@@ -932,32 +930,39 @@ is observed (from 36.10\% for 10~neurons and 125~epochs to 70.97\% for
 25~neurons  and  500~epochs). We  also  notice  that  the learning  of
 outputs~(2)   and~(3)  is   more  difficult.    Conversely,   for  the
 non-chaotic  case the  simplest training  setup is  enough  to predict
-configurations.  For all those  feedforward network topologies and all
+configurations.  For all these  feedforward network topologies and all
 outputs the  obtained results for the non-chaotic  case outperform the
 chaotic  ones. Finally,  the rates  for the  strategies show  that the
-different networks are unable to learn them.
-
-\newpage
+different feedforward networks are unable to learn them.
 
 For  the  second  coding   scheme  (\textit{i.e.},  with  Gray  Codes)
 Table~\ref{tab2} shows  that any network learns about  five times more
-non-chaotic  configurations  than chaotic  ones.  As  in the  previous
-scheme, the strategies cannot be predicted.
+non-chaotic  configurations than  chaotic  ones.  As  in the  previous
+scheme,       the      strategies      cannot       be      predicted.
+Figures~\ref{Fig:chaotic_predictions}                              and
+\ref{Fig:non-chaotic_predictions} present the predictions given by two
+feedforward multilayer  perceptrons that were  respectively trained to
+learn chaotic  and non-chaotic data,  using the second  coding scheme.
+Each figure  shows for  each sample of  the test  subset (577~samples,
+representing 25\%  of the 2304~samples) the  configuration that should
+have been predicted and the one given by the multilayer perceptron. It
+can be  seen that for  the chaotic data  the predictions are  far away
+from the  expected configurations.  Obviously,  the better predictions
+for the non-chaotic data reflect their regularity.
 
 Let us now compare the  two coding schemes. Firstly, the second scheme
 disturbs  the   learning  process.   In   fact  in  this   scheme  the
 configuration is always expressed as  a natural number, whereas in the
-first one  the number  of inputs follows  the increase of  the boolean
+first one  the number  of inputs follows  the increase of  the Boolean
 vectors coding configurations. In this latter case, the coding gives a
 finer information on configuration evolution.
-\JFC{Je n'ai pas compris le paragraphe precedent. Devrait Ãªtre repris}
 \begin{table}[b]
 \caption{Prediction success rates for configurations expressed with Gray code}
 \label{tab2}
 \centering
 \begin{tabular}{|c|c||c|c|c|}
 \hline 
-\multicolumn{5}{|c|}{Networks topology: 3~inputs, 2~outputs and one hidden layer} \\
+\multicolumn{5}{|c|}{Networks topology: 3~inputs, 2~outputs, and one hidden layer} \\
 \hline
 \hline
 & Hidden neurons & \multicolumn{3}{c|}{10 neurons} \\
@@ -984,12 +989,26 @@ finer information on configuration evolution.
 \end{tabular}
 \end{table}
 
+\begin{figure}
+  \centering
+  \includegraphics[scale=0.5]{chaotic_trace2}
+  \caption {Second coding scheme - Predictions obtained for a chaotic test subset.}
+  \label{Fig:chaotic_predictions}
+\end{figure}
+
+\begin{figure}
+  \centering
+  \includegraphics[scale=0.5]{non-chaotic_trace2} 
+  \caption{Second coding scheme - Predictions obtained for a non-chaotic test subset.}
+  \label{Fig:non-chaotic_predictions}
+\end{figure}
+
 Unfortunately, in  practical applications the number  of components is
 usually  unknown.   Hence, the  first  coding  scheme  cannot be  used
 systematically.   Therefore, we  provide  a refinement  of the  second
 scheme: each  output is learned  by a different  ANN. Table~\ref{tab3}
 presents the  results for  this approach.  In  any case,  whatever the
-considered  feedforward network topologies,  the maximum  epoch number
+considered feedforward  network topologies, the  maximum epoch number,
 and the kind of iterations, the configuration success rate is slightly
 improved.   Moreover, the  strategies predictions  rates  reach almost
 12\%, whereas in Table~\ref{tab2} they never exceed 1.5\%.  Despite of
@@ -1002,7 +1021,7 @@ appear to be an open issue.
 \centering
 \begin{tabular}{|c||c|c|c|}
 \hline 
-\multicolumn{4}{|c|}{Networks topology: 3~inputs, 1~output and one hidden layer} \\
+\multicolumn{4}{|c|}{Networks topology: 3~inputs, 1~output, and one hidden layer} \\
 \hline
 \hline
 Epochs & 125 & 250 & 500 \\ 
@@ -1064,21 +1083,17 @@ Chaotic/non chaotic & \multicolumn{3}{c|}{Output = Strategy} \\
 \end{tabular}
 \end{table}
 
-%
-% TO BE COMPLETED
-%
-
 \section{Conclusion}
 
 In  this paper,  we have  established an  equivalence  between chaotic
 iterations,  according to  the Devaney's  definition of  chaos,  and a
-class  of  multilayer perceptron  neural  networks.  Firstly, we  have
+class  of multilayer  perceptron  neural networks.   Firstly, we  have
 described how to build a neural network that can be trained to learn a
-given chaotic map function.  Then,  we found a condition that allow to
-check whether the iterations induced by a function are chaotic or not,
-and thus  if a chaotic map  is obtained. Thanks to  this condition our
-approach is not limited to a particular function. In the dual case, we
-show  that  checking  if  a  neural network  is  chaotic  consists  in
+given chaotic map function. Secondly,  we found a condition that allow
+to check whether  the iterations induced by a  function are chaotic or
+not, and thus  if a chaotic map is obtained.  Thanks to this condition
+our  approach is not  limited to  a particular  function. In  the dual
+case, we show that checking if a neural network is chaotic consists in
 verifying  a property  on an  associated  graph, called  the graph  of
 iterations.   These results  are valid  for recurrent  neural networks
 with a  particular architecture.  However,  we believe that  a similar
@@ -1092,10 +1107,7 @@ implemented  in a  new steganographic  method  \cite{guyeux10ter}.  As
 steganographic   detectors  embed  tools   like  neural   networks  to
 distinguish between  original and stego contents, our  studies tend to
 prove that such  detectors might be unable to  tackle with chaos-based
-information hiding schemes.  Furthermore, iterations such that not all
-of  the  components  are updated  at  each  step  are very  common  in
-biological  and  physics mechanisms.   Therefore,  one can  reasonably
-wonder whether neural networks should be applied in these contexts.
+information  hiding  schemes.
 
 In  future  work we  intend  to  enlarge  the comparison  between  the
 learning   of  truly   chaotic  and   non-chaotic   behaviors.   Other
@@ -1104,13 +1116,10 @@ be investigated  too, to  discover which tools  are the  most relevant
 when facing a truly chaotic phenomenon.  A comparison between learning
 rate  success  and  prediction  quality will  be  realized.   Concrete
 consequences in biology, physics, and computer science security fields
-will be  stated.  Lastly,  thresholds separating systems  depending on
-the ability to learn their dynamics will be established.
+will then be stated.
 
 % \appendix{}
 
-
-
 % \begin{definition} \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
@@ -1121,7 +1130,6 @@ the ability to learn their dynamics will be established.
 % $f^k(U) \cap V \neq \emptyset$.
 % \end{definition}
 
-
 \bibliography{chaos-paper}% Produces the bibliography via BibTeX.
 
 \end{document}
