X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/chaos1.git/blobdiff_plain/e041c0c5dd32ff38f533543cc17b6b2e8ce090ce..ab09441f8e3a9e5926d268f1d06dc420abad97c3:/main.tex?ds=sidebyside

diff --git a/main.tex b/main.tex
index aa920cb..717ae3e 100644
--- a/main.tex
+++ b/main.tex
@@ -105,70 +105,71 @@ is far more difficult than non chaotic behaviors.
 \section{Introduction}
 \label{S1}
 
-Several research  works have proposed or used  chaotic neural networks
-these last years. This interest  comes from their complex dynamics and
-the various  potential application areas. Chaotic  neural networks are
-particularly     considered    to    build     associative    memories
-\cite{Crook2007267}  and digital  security tools  like  hash functions
-\cite{Xiao10},  digital  watermarking \cite{1309431,Zhang2005759},  or
-cipher schemes \cite{Lian20091296}.  In the first case, the background
-idea is to  control chaotic dynamics in order  to store patterns, with
-the  key advantage  of offering  a  large storage  capacity.  For  the
-computer security field,  the use of chaotic dynamics  is motivated by
-their    unpredictability   and    random-like    behaviors.   Indeed,
-investigating  new concepts  is  crucial in  this  field, because  new
-threats  are constantly  emerging.   As an  illustrative example,  the
-former  standard in hash  functions, namely  the SHA-1  algorithm, has
-been recently weakened after flaws were discovered.
+Several research  works have proposed  or run chaotic  neural networks
+these last  years.  The complex dynamics  of such a  networks leads to
+various       potential      application       areas:      associative
+memories~\cite{Crook2007267}  and  digital  security tools  like  hash
+functions~\cite{Xiao10},                                       digital
+watermarking~\cite{1309431,Zhang2005759},           or          cipher
+schemes~\cite{Lian20091296}.  In the  former case, the background idea
+is to  control chaotic dynamics in  order to store  patterns, with the
+key advantage  of offering a  large storage capacity.  For  the latter
+case,   the  use   of   chaotic  dynamics   is   motivated  by   their
+unpredictability and  random-like behaviors.  Thus,  investigating new
+concepts is crucial in this  field, because new threats are constantly
+emerging.   As an illustrative  example, the  former standard  in hash
+functions,  namely the  SHA-1  algorithm, has  been recently  weakened
+after flaws were discovered.
 
 Chaotic neural networks have  been built with different approaches. In
 the context of associative  memory, chaotic neurons like the nonlinear
-dynamic state neuron \cite{Crook2007267}  are frequently used to build
-the network. These neurons have an inherent chaotic behavior, which is
-usually assessed through the computation of the Lyapunov exponent.  An
-alternative  approach  is  to  consider a  well-known  neural  network
-architecture: the  MultiLayer Perceptron.  MLP  networks are basically
-used  to model  nonlinear  relationships between  data,  due to  their
-universal approximator  capacity. Thus, this  kind of networks  can be
-trained to  model a  physical phenomenon known  to be chaotic  such as
+dynamic  state neuron  \cite{Crook2007267}  frequently constitute  the
+nodes of the network. These neurons have an inherent chaotic behavior,
+which  is usually  assessed through  the computation  of  the Lyapunov
+exponent.  An alternative approach  is to consider a well-known neural
+network architecture: the  MultiLayer Perceptron (MLP). These networks
+are  suitable to model  nonlinear relationships  between data,  due to
+their universal approximator capacity. 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 using transfer functions and initial conditions that are both
+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}.
 
 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 purpose  of  this paper  is  to fill  this  gap, using  a
+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
 precisely, in  this paper,  which is an  extension of a  previous work
-\cite{bgs11:ip},   we  establish   an   equivalence  between   chaotic
-iterations and  a class of globally  recurrent multilayer perceptrons.
-We  investigate the  converse problem  too, that  is, the  ability for
-classical MultiLayer Perceptrons (MLP) to learn a particular family of
+\cite{bgs11:ip},   we  establish   the  equivalence  between   chaotic
+iterations and  a class of globally  recurrent MLP.
+The investigation the  converse problem is the second contribution: 
+we indeed study the  ability for
+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  the component  to update at  each iteration.   It has
+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
-a  strongly connected  iterations graph.   In this  document,  we will
+a  strongly connected  iterations graph.   In this  document,  we 
 experiment several MLPs and try to learn some iterations of this kind.
-We will show that non-chaotic iterations can be learned, whereas it is
+We  show that non-chaotic iterations can be learned, whereas it is
 far  more  difficult  for chaotic  ones.   That  is  to say,  we  have
 discovered at  least one  family of problems  with a  reasonable size,
-such  that artificial  neural networks  should not  be applied  in the
-presence of chaos,  due to their inability to  learn chaotic behaviors
-in this context.
+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
 section is devoted  to the basics of chaotic  iterations and Devaney's
 chaos.   Section~\ref{S2} formally  describes  how to  build a  neural
-network  that operates  chaotically.  The  following  two~sections are
-devoted to the dual case:  checking whether an existing neural network
-is chaotic  or not (Section  \ref{S3}), and discussion  on topological
-properties  of   chaotic  neural  networks   (Section~\ref{S4}).   The
+network  that operates  chaotically.  Section~\ref{S3} is 
+devoted to the dual case of  checking whether an existing neural network
+is chaotic  or not. 
+Topological properties  of   chaotic  neural  networks  
+are discussed in Sect.~\ref{S4}.   The
 Section~\ref{section:translation}   shows   how   to  translate   such
 iterations  into  an Artificial  Neural  Network  (ANN),  in order  to
 evaluate the  capability for this  latter to learn  chaotic behaviors.
@@ -182,11 +183,11 @@ is summed up and intended future work is exposed.
 \section{Link between Chaotic Iterations and Devaney's Chaos}
 
 In this section, the well-established notion of Devaney's mathematical
-chaos is  firstly presented.  Preservation of  the unpredictability of
+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
-iterations and Devaney's chaos is  finally recalled at the end of this
+iterations and Devaney's chaos is  finally presented at the end of this
 section.
 
 In what follows and for  any function $f$, $f^n$ means the composition
@@ -210,7 +211,7 @@ mathematically this  kind of unpredictability  is also referred  to as
 deterministic chaos.  For example, many weather forecast models exist,
 but they give only suitable predictions for about a week, because they
 are initialized with conditions  that reflect only a partial knowledge
-of the current weather.  Even  if initially the differences are small,
+of the current weather.  Even  the  differences are  initially small,
 they are  amplified in the course  of time, and thus  make difficult a
 long-term prediction.  In fact,  in a chaotic system, an approximation
 of  the current  state is  a  quite useless  indicator for  predicting
@@ -219,8 +220,8 @@ future states.
 From  mathematical  point  of   view,  deterministic  chaos  has  been
 thoroughly studied  these last decades, with  different research works
 that  have   provide  various  definitions  of   chaos.   Among  these
-definitions,   the  one  given   by  Devaney~\cite{Devaney}   is  well
-established.    This   definition   consists  of   three   conditions:
+definitions,   the  one  given   by  Devaney~\cite{Devaney}   is  
+well-established.    This   definition   consists  of   three   conditions:
 topological  transitivity, density of  periodic points,  and sensitive
 point dependence on initial conditions.
 
@@ -231,13 +232,17 @@ given region. More precisely,
 \begin{definition} \label{def2}
 A continuous function $f$  on a topological space $(\mathcal{X},\tau)$
 is defined  to be  {\bf topologically transitive}  if for any  pair of
-open  sets $U$,  $V  \in  \mathcal{X}$ there  exists  $k>0$ such  that
+open  sets $U$,  $V  \in  \mathcal{X}$ there  exists  
+$k \in
+\mathds{N}^{\ast}$
+ such  that
 $f^k(U) \cap V \neq \emptyset$.
 \end{definition}
 
 This property  implies that a  dynamical system cannot be  broken into
-simpler  subsystems.  It  is intrinsically  complicated and  cannot be
-simplified.  On  the contrary,  a dense set  of periodic points  is an
+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.
 
 \begin{definition} \label{def3}
@@ -247,7 +252,7 @@ A point $x$ is called a  {\bf periodic point} for $f$ of period~$n \in
 
 \begin{definition} \label{def4}
 $f$ is said to be {\bf  regular} on $(\mathcal{X},\tau)$ if the set of
-  periodic points  for $f$ is  dense in $\mathcal{X}$ ($\forall  x \in
+  periodic points  for $f$ is  dense in $\mathcal{X}$ ( for any $x \in
   \mathcal{X}$, we can find at least  one periodic point in any of its
   neighborhood).
 \end{definition}
@@ -261,7 +266,7 @@ whole system. Then,
 $f$  has {\bf  sensitive dependence  on initial  conditions}  if there
   exists $\delta  >0$ such  that, for any  $x\in \mathcal{X}$  and any
   neighborhood $V$ of $x$, there exist  $y\in V$ and $n > 0$ such that
-  $d\left(f^{n}(x), f^{n}(y)\right) >\delta  $. $\delta$ is called the
+  $d\left(f^{n}(x), f^{n}(y)\right) >\delta  $. The value $\delta$ is called the
   {\bf constant of sensitivity} of $f$.
 \end{definition}
 
@@ -312,7 +317,7 @@ indeed  the negation  of $x_i$).   Intuitively, $x$  and  $N(i,x)$ are
 neighbors.   The discrete  iterations of  $f$ are  represented  by the
 oriented  {\it graph  of iterations}  $\Gamma(f)$.  In  such  a graph,
 vertices are configurations  of $\Bool^n$ and there is  an arc labeled
-$i$ from $x$ to $N(i,x)$ iff $f_i(x)$ is $N(i,x)$.
+$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}$
@@ -389,12 +394,12 @@ d_{s}(S,\check{S})=\frac{9}{2n}\sum_{t=0}^{\infty
 
 This    distance    is    defined    to    reflect    the    following
 information. Firstly, the more  two systems have different components,
-the  larger the  distance  between them.  Secondly,  two systems  with
+the  larger the  distance  between them is.  Secondly,  two systems  with
 similar components and strategies, which have the same starting terms,
 must  induce only  a small  distance.  The  proposed  distance fulfill
 these  requirements: on  the one  hand  its floor  value reflects  the
 difference between  the cells, on  the other hand its  fractional part
-measure the difference between the strategies.
+measures the difference between the strategies.
 
 The relation  between $\Gamma(f)$ and  $G_f$ is clear: there  exists a
 path from  $x$ to $x'$  in $\Gamma(f)$ if  and only if there  exists a
@@ -409,7 +414,7 @@ if and only if  $\Gamma(f)$ is strongly connected.
 
 Checking  if a  graph  is  strongly connected  is  not difficult.  For
 example,  consider the  function $f_1\left(x_1,\dots,x_n\right)=\left(
-\overline{x_1},x_1,x_2,\dots,x_\mathsf{n}\right)$. As $\Gamma(f_1)$ is
+\overline{x_1},x_1,x_2,\dots,x_{n-1}\right)$. As $\Gamma(f_1)$ is
 obviously strongly connected, then $G_{f_1}$ is a chaotic map.
 
 With this  material, we are now  able to build a  first chaotic neural
@@ -479,11 +484,11 @@ alternative functions  $f$ for $f_0$  through a simple check  of their
 graph of  iterations $\Gamma(f)$.  For  example, we can  build another
 chaotic neural network by using $f_1$ instead of $f_0$.
 
-\section{Checking if a neural network is chaotic or not}
+\section{Checking whether a neural network is chaotic or not}
 \label{S3}
 
 We focus now on the case  where a neural network is already available,
-and for which we  want to know if it is chaotic  or not. Typically, in
+and for which we  want to know if it is chaotic. Typically, in
 many research papers neural network  are usually claimed to be chaotic
 without any  convincing mathematical proof. We propose  an approach to
 overcome  this  drawback  for  a  particular  category  of  multilayer
@@ -492,13 +497,13 @@ In  spite of  this restriction,  we think  that this  approach  can be
 extended to  a large variety  of neural networks.  We plan to  study a
 generalization of this approach in a future work.
 
-We consider a multilayer perceptron  of the following form: as inputs
-it has $n$ binary digits and  one integer value, while it produces $n$
+We consider a multilayer perceptron  of the following form: inputs
+are $n$ binary digits and  one integer value, while outputs are  $n$
 bits.   Moreover, each  binary  output is  connected  with a  feedback
 connection to an input one.
 
 \begin{itemize}
-\item At  initialization, the network is feeded  with $n$~bits denoted
+\item During  initialization, the network if we seed it 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
@@ -558,20 +563,20 @@ that $d\left(f^n(x),f^n(y)\right) \geq \varepsilon$.
 \begin{definition} \label{def9}
 A discrete dynamical  system is said to be  {\bf topologically mixing}
 if  and only  if,  for any  pair  of disjoint  open  sets $U$,$V  \neq
-\emptyset$, $n_0  \in \mathds{N}$  can be found  such that  $\forall n
-\geq n_0$, $f^n(U) \cap V \neq \emptyset$.
+\emptyset$, we can find some $n_0  \in \mathds{N}$ such that  for any $n$, 
+$n\geq n_0$, we have $f^n(U) \cap V \neq \emptyset$.
 \end{definition}
 
 As  proven in Ref.~\cite{gfb10:ip},  chaotic iterations  are expansive
 and  topologically mixing when  $f$ is  the vectorial  negation $f_0$.
 Consequently,  these  properties are  inherited  by the  CI-MLP($f_0$)
-recurrent neural network presented  previously, which induce a greater
+recurrent neural network previously presented, which induce a greater
 unpredictability.  Any  difference on the  initial value of  the input
 layer is  in particular  magnified up to  be equal to  the expansivity
 constant.
 
-Now,  what are the  consequences for  a neural  network to  be chaotic
-according  to  Devaney's definition?  First  of  all, the  topological
+Let us then focus on the consequences for  a neural  network to  be chaotic
+according  to  Devaney's definition.  First  of  all, the  topological
 transitivity property implies indecomposability.
 
 \begin{definition} \label{def10}
@@ -694,7 +699,7 @@ Perceptron.
 
 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 iteration  graph.  This  can be
+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
@@ -730,7 +735,7 @@ configuration: for instance, 16~(10000) and 15~(01111) are closed in a
 decimal ordering, but  their Hamming distance is 5.   This is why Gray
 codes~\cite{Gray47} have been preferred.
 
-Secondly,  how do  we  deal  with strategies.   Obviously,  it is  not
+Let us secondly 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
@@ -884,7 +889,8 @@ 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.
 
-For the second coding  scheme, Table~\ref{tab2} shows that any network
+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.
 
@@ -937,7 +943,8 @@ 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  this
-improvement, a long term prediction of chaotic iterations appear to be
+improvement, a long term prediction of chaotic iterations still 
+appear to be
 an open issue.
 
 \begin{table}
