asynchronous pour chaotic

[chaos1.git] / main.tex

diff --git a/main.tex b/main.tex
index 717ae3e688d7b36d00dcd58280383073825e8c46..545524feed5c07a727395d780b39820755607c45 100644 (file)
--- a/main.tex
+++ b/main.tex
@@ -65,14 +65,15 @@ Many  research works  deal with  chaotic neural  networks  for various
 fields  of application. Unfortunately,  up to  now these  networks are
 usually  claimed to be  chaotic without  any mathematical  proof.  The
 purpose of this paper is to establish, based on a rigorous theoretical
 fields  of application. Unfortunately,  up to  now these  networks are
 usually  claimed to be  chaotic without  any mathematical  proof.  The
 purpose of this paper is to establish, based on a rigorous theoretical

-framework, an equivalence between  chaotic iterations according to the
-Devaney's  formulation  of chaos  and  a  particular  class of  neural
+framework, an equivalence between  chaotic iterations according to 
+Devaney  and  a  particular  class of  neural

 networks. On the one hand we show  how to build such a network, on the
 other  hand we provide  a method  to check  if a  neural network  is a
 chaotic one.  Finally, the ability of classical feedforward multilayer
 perceptrons to  learn sets of  data obtained from a  chaotic dynamical
 system is regarded.  Various  Boolean functions are iterated on finite
 networks. On the one hand we show  how to build such a network, on the
 other  hand we provide  a method  to check  if a  neural network  is a
 chaotic one.  Finally, the ability of classical feedforward multilayer
 perceptrons to  learn sets of  data obtained from a  chaotic dynamical
 system is regarded.  Various  Boolean functions are iterated on finite

-states, some  of them  are proven to  be chaotic  as it is  defined by
+states. Iterations of some of them  are proven to  be chaotic 
+ as it is  defined by

 Devaney.  In that context, important differences occur in the training
 process,  establishing  with  various  neural  networks  that  chaotic
 behaviors are far more difficult to learn.
 Devaney.  In that context, important differences occur in the training
 process,  establishing  with  various  neural  networks  that  chaotic
 behaviors are far more difficult to learn.


@@ -85,6 +86,7 @@ behaviors are far more difficult to learn.
 \maketitle
 
 \begin{quotation}
 \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
 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


@@ -138,8 +140,8 @@ chaotic,      is      itself      claimed      to      be      chaotic
 
 What all of these chaotic neural  networks have in common is that they
 are claimed to be chaotic  despite a lack of any rigorous mathematical
 
 What all of these chaotic neural  networks have in common is that they
 are claimed to be chaotic  despite a lack of any rigorous mathematical

-proof.   The first contribution of  this paper  is  to fill  this  gap, using  a
-theoretical  framework  based on  the  Devaney's  definition of  chaos
+proof.   The first contribution of  this paper  is  to fill  this  gap, 
+using  a theoretical  framework  based on  the  Devaney's  definition of  chaos

 \cite{Devaney}.   This  mathematical  theory  of chaos  provides  both
 qualitative and quantitative tools to evaluate the complex behavior of
 a  dynamical  system:  ergodicity,   expansivity,  and  so  on.   More
 \cite{Devaney}.   This  mathematical  theory  of chaos  provides  both
 qualitative and quantitative tools to evaluate the complex behavior of
 a  dynamical  system:  ergodicity,   expansivity,  and  so  on.   More


@@ -152,8 +154,8 @@ classical MultiLayer Perceptrons  to learn a particular family of
 discrete  chaotic  dynamical  systems.   This family,  called  chaotic
 iterations, is defined by a  Boolean vector, an update function, and a
 sequence giving  which component  to update at  each iteration.   It has
 discrete  chaotic  dynamical  systems.   This family,  called  chaotic
 iterations, is defined by a  Boolean vector, an update function, and a
 sequence giving  which component  to update at  each iteration.   It has

-been  previously established  that such  dynamical systems  can behave
-chaotically, as it is defined by Devaney, when the chosen function has
+been  previously established  that such  dynamical systems is 
+chaotically iterated (as it is defined by Devaney) when the chosen function has

 a  strongly connected  iterations graph.   In this  document,  we 
 experiment several MLPs and try to learn some iterations of this kind.
 We  show that non-chaotic iterations can be learned, whereas it is
 a  strongly connected  iterations graph.   In this  document,  we 
 experiment several MLPs and try to learn some iterations of this kind.
 We  show that non-chaotic iterations can be learned, whereas it is


@@ -163,7 +165,7 @@ such  that artificial  neural networks  should not  be applied
 due to their inability to  learn chaotic behaviors in this context.
 
 The remainder of this research  work is organized as follows. The next
 due to their inability to  learn chaotic behaviors in this context.
 
 The remainder of this research  work is organized as follows. The next

-section is devoted  to the basics of chaotic  iterations and Devaney's
+section is devoted  to the basics of Devaney's

 chaos.   Section~\ref{S2} formally  describes  how to  build a  neural
 network  that operates  chaotically.  Section~\ref{S3} is 
 devoted to the dual case of  checking whether an existing neural network
 chaos.   Section~\ref{S2} formally  describes  how to  build a  neural
 network  that operates  chaotically.  Section~\ref{S3} is 
 devoted to the dual case of  checking whether an existing neural network


@@ -180,13 +182,13 @@ system.  Prediction success rates are  given and discussed for the two
 sets.  The paper ends with a conclusion section where our contribution
 is summed up and intended future work is exposed.
 
 sets.  The paper ends with a conclusion section where our contribution
 is summed up and intended future work is exposed.
 

-\section{Link between Chaotic Iterations and Devaney's Chaos}
+\section{Chaotic Iterations according to  Devaney}

 
 In this section, the well-established notion of Devaney's mathematical
 chaos is  firstly recalled.  Preservation of  the unpredictability of
 such dynamical  system when implemented  on a computer is  obtained by
 
 In this section, the well-established notion of Devaney's mathematical
 chaos is  firstly recalled.  Preservation of  the unpredictability of
 such dynamical  system when implemented  on a computer is  obtained by

-using  some discrete iterations  called ``chaotic  iterations'', which
-are thus introduced.  The result establishing the link between chaotic
+using  some discrete iterations  called ``asynchronous  iterations'', which
+are thus introduced.  The result establishing the link between such

 iterations and Devaney's chaos is  finally presented at the end of this
 section.
 
 iterations and Devaney's chaos is  finally presented at the end of this
 section.
 


@@ -273,32 +275,33 @@ $f$  has {\bf  sensitive dependence  on initial  conditions}  if there
 Finally,
 
 \begin{definition} \label{def5}
 Finally,
 
 \begin{definition} \label{def5}

-$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.
+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.

 \end{definition}
 
 Let us notice that for a  metric space the last condition follows from
 the two first ones~\cite{Banks92}.
 
 \end{definition}
 
 Let us notice that for a  metric space the last condition follows from
 the two first ones~\cite{Banks92}.
 

-\subsection{Chaotic Iterations}
+\subsection{Asynchronous Iterations}

 
 

-This section  presents some basics on  topological chaotic iterations.
+%This section  presents some basics on  topological chaotic iterations.

 Let us  firstly discuss about the  domain of iteration.  As  far as we
 Let us  firstly discuss about the  domain of iteration.  As  far as we

-know, no result rules that the chaotic behavior of a function that has
-been theoretically proven on  $\R$ remains valid on the floating-point
+know, no result rules that the chaotic behavior of a dynamical system 
+that has been theoretically proven on  $\R$ remains valid on the
+floating-point

 numbers, which is  the implementation domain.  Thus, to  avoid loss of
 chaos this  work presents an  alternative, that is to  iterate Boolean
 maps:  results that  are  theoretically obtained  in  that domain  are
 preserved in implementations.
 
 Let us denote by $\llbracket  a ; b \rrbracket$ the following interval
 numbers, which is  the implementation domain.  Thus, to  avoid loss of
 chaos this  work presents an  alternative, that is to  iterate Boolean
 maps:  results that  are  theoretically obtained  in  that domain  are
 preserved in implementations.
 
 Let us denote by $\llbracket  a ; b \rrbracket$ the following interval

-of integers:  $\{a, a+1,  \hdots, b\}$, where $a~<~b$.  A  {\it system}
+of integers:  $\{a, a+1,  \hdots, b\}$, where $a~<~b$.  
+In that section,  a  system 

 under   consideration    iteratively   modifies   a    collection   of
 $n$~components.   Each component  $i \in  \llbracket 1;  n \rrbracket$
 takes  its  value  $x_i$  among the  domain  $\Bool=\{0,1\}$.   A~{\it
 under   consideration    iteratively   modifies   a    collection   of
 $n$~components.   Each component  $i \in  \llbracket 1;  n \rrbracket$
 takes  its  value  $x_i$  among the  domain  $\Bool=\{0,1\}$.   A~{\it

-  configuration} of the system at discrete time $t$ (also said at {\it
-  iteration} $t$) is the vector
+  configuration} of the system at discrete time $t$  is the vector

 %\begin{equation*}   
 $x^{t}=(x_1^{t},\ldots,x_{n}^{t}) \in \Bool^n$.
 %\end{equation*}
 %\begin{equation*}   
 $x^{t}=(x_1^{t},\ldots,x_{n}^{t}) \in \Bool^n$.
 %\end{equation*}


@@ -320,8 +323,21 @@ vertices are configurations  of $\Bool^n$ and there is  an arc labeled
 $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
 $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 the  component to  update at  time $t$  and $S^{t}$
-denotes its  $t-$th term.  We  introduce the function $F_{f}$  that is
+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 clasically refered as \emph{asynchronous iterations}. 
+Next section shows the link between asynchronous iterations and 
+Devaney's Chaos.
+
+\subsection{On the link between asynchronous iterations and
+  Devaney's Chaos}
+
+In  this subsection  we recall  the link  we have  established between
+asynchronous iterations and Devaney's  chaos.  The theoretical framework is
+fully described in \cite{guyeux09}.
+
+We  introduce the function $F_{f}$  that is

 defined  for  any given  application  $f:\Bool^{n}  \to \Bool^{n}$  by
 $F_{f}:   \llbracket1;n\rrbracket\times   \mathds{B}^{n}   \rightarrow
 \mathds{B}^{n}$, s.t.
 defined  for  any given  application  $f:\Bool^{n}  \to \Bool^{n}$  by
 $F_{f}:   \llbracket1;n\rrbracket\times   \mathds{B}^{n}   \rightarrow
 \mathds{B}^{n}$, s.t.


@@ -362,17 +378,10 @@ X^{k+1}& = & G_{f}(X^{k})\\
 where  $\sigma$ is the  function that  removes the  first term  of the
 strategy  ({\it i.e.},~$S^0$).   This definition  means that  only one
 component  of the  system is  updated  at an  iteration: the  $S^t$-th
 where  $\sigma$ is the  function that  removes the  first term  of the
 strategy  ({\it i.e.},~$S^0$).   This definition  means that  only one
 component  of the  system is  updated  at an  iteration: the  $S^t$-th

-element.  But it can be extended by considering subsets for $S^t$.
+element. But it can be extended by considering subsets for $S^t$.

 
 

-Let us finally remark that, despite the use of the term {\it chaotic},
-there is {\it  priori} no connection between these  iterations and the
-mathematical theory of chaos presented previously.

 
 

-\subsection{Chaotic Iterations and Devaney's Chaos}

 
 

-In  this subsection  we recall  the link  we have  established between
-chaotic iterations and Devaney's  chaos.  The theoretical framework is
-fully described in \cite{guyeux09}.

 
 The   {\bf   distance}   $d$    between   two   points   $(S,x)$   and
 $(\check{S},\check{x})\in  \mathcal{X} = \llbracket1;n\rrbracket^\Nats
 
 The   {\bf   distance}   $d$    between   two   points   $(S,x)$   and
 $(\check{S},\check{x})\in  \mathcal{X} = \llbracket1;n\rrbracket^\Nats


@@ -408,8 +417,8 @@ initial  point $(s,x)$  reaches  the configuration  $x'$.  Using  this
 link, Guyeux~\cite{GuyeuxThese10} has proven that,
 \begin{theorem}%[Characterization of $\mathcal{C}$]
 \label{Th:Caracterisation   des   IC   chaotiques}  
 link, Guyeux~\cite{GuyeuxThese10} has proven that,
 \begin{theorem}%[Characterization of $\mathcal{C}$]
 \label{Th:Caracterisation   des   IC   chaotiques}  

-Let $f:\Bool^n\to\Bool^n$. $G_f$ is chaotic  (according to  Devaney) 
-if and only if  $\Gamma(f)$ is strongly connected.
+Let $f:\Bool^n\to\Bool^n$. Iterations of $G_f$ are chaotic  according 
+to  Devaney if and only if  $\Gamma(f)$ is strongly connected.

 \end{theorem}
 
 Checking  if a  graph  is  strongly connected  is  not difficult.  For
 \end{theorem}
 
 Checking  if a  graph  is  strongly connected  is  not difficult.  For


@@ -503,7 +512,7 @@ bits.   Moreover, each  binary  output is  connected  with a  feedback
 connection to an input one.
 
 \begin{itemize}
 connection to an input one.
 
 \begin{itemize}

-\item During  initialization, the network if we seed it with $n$~bits denoted
+\item During  initialization, the network is seeded with $n$~bits denoted

   $\left(x^0_1,\dots,x^0_n\right)$  and an  integer  value $S^0$  that
   belongs to $\llbracket1;n\rrbracket$.
 \item     At     iteration~$t$,     the     last     output     vector
   $\left(x^0_1,\dots,x^0_n\right)$  and an  integer  value $S^0$  that
   belongs to $\llbracket1;n\rrbracket$.
 \item     At     iteration~$t$,     the     last     output     vector


@@ -529,12 +538,15 @@ $f\left(x_1,x_2,\dots,x_n\right)$ is equal to
 \left(F\left(1,\left(x_1,x_2,\dots,x_n\right)\right),\dots,
   F\left(n,\left(x_1,x_2,\dots,x_n\right)\right)\right) \enspace .
 \end{equation}
 \left(F\left(1,\left(x_1,x_2,\dots,x_n\right)\right),\dots,
   F\left(n,\left(x_1,x_2,\dots,x_n\right)\right)\right) \enspace .
 \end{equation}

-Then $F=F_f$  and this recurrent  neural network produces  exactly the
-same      output      vectors,      when     feeding      it      with
+Then $F=F_f$. If this recurrent  neural network is seeded with 

 $\left(x_1^0,\dots,x_n^0\right)$    and   $S   \in    \llbracket   1;n
 $\left(x_1^0,\dots,x_n^0\right)$    and   $S   \in    \llbracket   1;n

-\rrbracket^{\mathds{N}}$, than  chaotic iterations $F_f$  with initial
+\rrbracket^{\mathds{N}}$, it produces  exactly the
+same      output      vectors  than the 
+chaotic iterations of $F_f$  with initial

 condition  $\left(S,(x_1^0,\dots,  x_n^0)\right)  \in  \llbracket  1;n
 condition  $\left(S,(x_1^0,\dots,  x_n^0)\right)  \in  \llbracket  1;n

-\rrbracket^{\mathds{N}}  \times \mathds{B}^n$.   In the  rest  of this
+\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
 stands for ``Chaotic Iterations based MultiLayer Perceptron''.
 
 paper,  we will  call such  multilayer perceptrons  CI-MLP($f$), which
 stands for ``Chaotic Iterations based MultiLayer Perceptron''.
 


@@ -581,7 +593,7 @@ transitivity property implies indecomposability.
 
 \begin{definition} \label{def10}
 A   dynamical   system   $\left(   \mathcal{X},  f\right)$   is   {\bf
 
 \begin{definition} \label{def10}
 A   dynamical   system   $\left(   \mathcal{X},  f\right)$   is   {\bf

-indecomposable}  if it  is not  the  union of  two closed  sets $A,  B
+not decomposable}  if it  is not  the  union of  two closed  sets $A,  B

 \subset \mathcal{X}$ such that $f(A) \subset A, f(B) \subset B$.
 \end{definition}
 
 \subset \mathcal{X}$ such that $f(A) \subset A, f(B) \subset B$.
 \end{definition}
 


@@ -652,15 +664,32 @@ $\left( \mathcal{X},d\right)$  is compact and  the topological entropy
 of $(\mathcal{X},G_{f_0})$ is infinite.
 \end{theorem}
 
 of $(\mathcal{X},G_{f_0})$ is infinite.
 \end{theorem}
 

-We have explained how to  construct truly chaotic neural networks, how
-to check whether a  given MLP is chaotic or not, and  how to study its
-topological behavior.   The last thing to  investigate, when comparing
-neural  networks   and  Devaney's  chaos,  is   to  determine  whether
-artificial neural networks  are able to learn or  predict some chaotic
-behaviors, as  it is defined  in the Devaney's formulation  (when they
+\begin{figure}
+  \centering
+  \includegraphics[scale=0.625]{scheme}
+  \caption{Summary of addressed neural networks and chaos problems}
+  \label{Fig:scheme}
+\end{figure}
+
+The Figure~\ref{Fig:scheme} is a summary of addressed neural networks and chaos problems.
+Section~\ref{S2} has 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 its topological behavior. 
+The last thing to  investigate, when comparing
+neural  networks   and  Devaney's  chaos,  is to  determine  whether
+an artificial neural network $A$  is able to learn or  predict some chaotic
+behaviors of $B$, as  it is defined  in the Devaney's formulation  (when they

 are not specifically constructed for this purpose).  This statement is
 studied in the next section.
 
 are not specifically constructed for this purpose).  This statement is
 studied in the next section.
 

+
+
+
+
+
+

 \section{Suitability of Artificial Neural Networks 
 for Predicting Chaotic Behaviors}
 
 \section{Suitability of Artificial Neural Networks 
 for Predicting Chaotic Behaviors}
 


@@ -787,10 +816,10 @@ in   particular    well-known   for   its    universal   approximation
 property. 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
 property. 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 backpropagation, can  learn successfully the
+with Bayesian  Regulation back-propagation, can  learn successfully the

 dynamics of Chua's circuit.
 
 dynamics of Chua's circuit.
 

-In these experimentations we consider  MLPs having one hidden layer of
+In these experiments  we consider  MLPs having one hidden layer of

 sigmoidal  neurons  and  output   neurons  with  a  linear  activation
 function.     They    are    trained    using    the    Limited-memory
 Broyden-Fletcher-Goldfarb-Shanno quasi-newton algorithm in combination
 sigmoidal  neurons  and  output   neurons  with  a  linear  activation
 function.     They    are    trained    using    the    Limited-memory
 Broyden-Fletcher-Goldfarb-Shanno quasi-newton algorithm in combination