\date{\today}
\newcommand{\CG}[1]{\begin{color}{red}\textit{#1}\end{color}}
+\newcommand{\JFC}[1]{\begin{color}{blue}\textit{#1}\end{color}}
+
+
+
+
\begin{abstract}
%% Text of abstract
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
-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.
\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
\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.
+REVOIR TOUT L'INTRO et l'ABSTRACT en fonction d'asynchrone, chaotic
+
+
+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.
+\JFC{Michel, peux-tu donner une ref la dessus}
+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
-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
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 asynchronous
+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
-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
+sequence giving which component to update at each iteration. It 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 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
+section is devoted to the basics of 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.
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 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
+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.
In what follows and for any function $f$, $f^n$ means the composition
-$f \circ f \circ \hdots \circ f$ ($n$ times).
+$f \circ f \circ \hdots \circ f$ ($n$ times) and an \emph{iteration}
+of a \emph{dynamical system} is the step that consists in
+updating the global state $x^t$ at time $t$ with respect to a function $f$
+s.t. $x^{t+1} = f(x^t)$.
\subsection{Devaney's chaotic dynamical systems}
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
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.
Topological transitivity is checked when, for any point, any
neighborhood of its future evolution eventually overlap with any other
-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
-$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
+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.
-\begin{definition} \label{def3}
-A point $x$ is called a {\bf periodic point} for $f$ of period~$n \in
-\mathds{N}^{\ast}$ if $f^{n}(x)=x$.
-\end{definition}
-
-\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
+However, chaos need some regularity to ``counteracts''
+the effects of transitivity.
+%\begin{definition} \label{def3}
+We recall that a point $x$ is {\emph{periodic point}} for $f$ of
+period~$n \in \mathds{N}^{\ast}$ if $f^{n}(x)=x$.
+%\end{definition}
+Then, the map
+%\begin{definition} \label{def4}
+$f$ is {\emph{ regular}} on $(\mathcal{X},\tau)$ if the set of
+ 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}
+%\end{definition}
+ Thus,
+ due to these two properties, two points close to each other can behave
+ in a completely different manner, leading to unpredictability for the
+ whole system.
-This regularity ``counteracts'' the effects of transitivity. Thus,
-due to these two properties, two points close to each other can behave
-in a completely different manner, leading to unpredictability for the
-whole system. Then,
-
-\begin{definition} \label{sensitivity}
-$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
- {\bf constant of sensitivity} of $f$.
-\end{definition}
+Let we recall that $f$
+has {\emph{ 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 $. The value $\delta$ is called the
+ {\emph{constant of sensitivity}} of $f$.
-Finally,
+Finally, The dynamical system that iterates $f$ is {\emph{ 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 \emph{chaotic according Devaney}
+when corresponding dynamical system is chaotic according Devaney.
-\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.
-\end{definition}
-Let us notice that for a metric space the last condition follows from
-the two first ones~\cite{Banks92}.
+%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
-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
-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
- configuration} of the system at discrete time $t$ (also said at {\it
- iteration} $t$) is the vector
+takes its value $x_i$ among the domain $\Bool=\{0,1\}$.
+A \emph{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*}
obtained by switching the $i-$th component of $x$ ($\overline{x_i}$ is
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,
+oriented \emph{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 \emph{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 \emph{asynchronous iterations}.
+More precisely, we have here for any $i$, $1\le i \le n$,
+$$
+\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}
+ \end{array}
+\right.
+\end{array} \right.
+$$
+
+Next section shows the link between asynchronous iterations and
+Devaney's Chaos.
+
+\subsection{On the link between asynchronous iterations and
+ Devaney's Chaos}
-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
+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.
\right.
\end{equation}
-\noindent With such a notation, configurations are defined for times
+\noindent With such a notation, configurations
+asynchronously obtained are defined for times
$t=0,1,2,\ldots$ by:
\begin{equation}\label{eq:sync}
\left\{\begin{array}{l}
\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 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$.
+strategy ({\it i.e.},~$S^0$).
+This definition allows to links asynchronous iterations with
+classical iterations of a dynamical system.
-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}
+%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$.
-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
-\times \Bool^{n}$ is defined by
+To study topological properties of these iterations, we are then left to
+introduce a {\emph{ 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
\begin{equation}
d((S,x);(\check{S},\check{x}))=d_{e}(x,\check{x})+d_{s}(S,\check{S})
\enspace ,
}\frac{|S^{t}-\check{S}^{t}|}{10^{t+1}} \in [0 ; 1] \enspace .
\end{equation}
-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
+Notice that the more two systems have different components,
+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
-strategy $s$ such that the parallel iteration of $G_f$ from the
+strategy $s$ such that iterations of $G_f$ from the
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}
-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
-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
-obviously strongly connected, then $G_{f_1}$ is a chaotic map.
+Checking if a graph is strongly connected is not difficult
+(by the Tarjan's algorithm for instance).
+Let be given a strategy $S$ and a function $f$ such that
+$\Gamma(f)$ is strongly connected.
+In that 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
+$\Bool^n\to\Bool^n$ that are used all along this article.
+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 $f_1\left(x_1,\dots,x_n\right)=\left(
+\overline{x_1},x_1,x_2,\dots,x_{n-1}\right)$.
+It is not hard to see that $\Gamma(f_0)$ and $\Gamma(f_1)$ are
+both strongly connected, then iterations of $G_{f_0}$ and of
+$G_{f_1}$ are chaotic according to Devaney.
With this material, we are now able to build a first chaotic neural
network, as defined in the Devaney's formulation.
\section{A chaotic neural network in the sense of Devaney}
\label{S2}
-Let us firstly introduce the vectorial negation
-$f_{0}(x_{1},\dots,x_{n}) =(\overline{x_{1}},\dots,\overline{x_{n}})$,
-which is such that $\Gamma(f_0)$ is strongly connected. Considering
-the map $F_{f_0}:\llbracket 1; n \rrbracket \times \mathds{B}^n \to
-\mathds{B}^n$ associated to the vectorial negation, we can build a
-multilayer perceptron neural network modeling $F_{f_0}$. Hence, for
-all inputs $(s,x) \in \llbracket 1;n\rrbracket \times \mathds{B}^n$,
-the output layer will produce $F_{f_0}(s,x)$. It is then possible to
+Firstly, let us build a
+multilayer perceptron neural network modeling
+$F_{f_0}:\llbracket 1; n \rrbracket \times \mathds{B}^n \to
+\mathds{B}^n$ associated to the vectorial negation.
+More precisely, for all inputs
+$(s,x) \in \llbracket 1;n\rrbracket \times \mathds{B}^n$,
+the output layer produces $F_{f_0}(s,x)$. It is then possible to
link the output layer and the input one, in order to model the
dependence between two successive iterations. As a result we obtain a
global recurrent neural network that behaves as follows (see
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, then the sequence of successive published
+given as outside input,
+\JFC{en dire davantage sur l'outside world}
+ 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:CIs}). 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 build to
-model the behavior of $G_{f_0}$, which is chaotic according to
+$\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.
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
perceptrons defined below, and for the Devaney's formulation of chaos.
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.
+extended to a large variety of neural networks.
+
-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 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
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
by $F: \llbracket 1;n \rrbracket \times \mathds{B}^n \rightarrow
\mathds{B}^n$ the function that maps the value
$\left(s,\left(x_1,\dots,x_n\right)\right) \in \llbracket 1;n
-\rrbracket \times \mathds{B}^n$ into the value
+\rrbracket \times \mathds{B}^n$
+\JFC{ici, cela devait etre $S^t$ et pas $s$, nn ?}
+ into the value
$\left(y_1,\dots,y_n\right) \in \mathds{B}^n$, where
$\left(y_1,\dots,y_n\right)$ is the response of the neural network
after the initialization of its input layer with
-$\left(s,\left(x_1,\dots, x_n\right)\right)$. Secondly, we define $f:
+$\left(s,\left(x_1,\dots, x_n\right)\right)$.
+\JFC{ici, cela devait etre $S^t$ et pas $s$, nn ?}
+Secondly, we define $f:
\mathds{B}^n \rightarrow \mathds{B}^n$ such that
$f\left(x_1,x_2,\dots,x_n\right)$ is equal to
\begin{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
-\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
-\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''.
contrarily, their unpredictable behavior. An example of such a study
is given in the next section.
+\JFC{Ce qui suit est davantage qu'un exemple.Il faudrait
+motiver davantage, non?}
+
+
\section{Topological properties of chaotic neural networks}
\label{S4}
theory of chaos.
\begin{definition} \label{def8}
-A function $f$ is said to be {\bf expansive} if $\exists
+A function $f$ is said to be {\emph{ expansive}} if $\exists
\varepsilon>0$, $\forall x \neq y$, $\exists n \in \mathds{N}$ such
that $d\left(f^n(x),f^n(y)\right) \geq \varepsilon$.
\end{definition}
\begin{definition} \label{def9}
-A discrete dynamical system is said to be {\bf topologically mixing}
+A discrete dynamical system is said to be {\emph{ 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}
+\JFC{Donner un sens à ces definitions}
+
-As proven in Ref.~\cite{gfb10:ip}, chaotic iterations are expansive
-and topologically mixing when $f$ is the vectorial negation $f_0$.
+It has been proven in Ref.~\cite{gfb10:ip}, that 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
-transitivity property implies indecomposability.
+Let us then focus on the consequences for a neural network to be chaotic
+according to Devaney's definition. Intuitively, the topological
+transitivity property implies indecomposability, which is formally defined
+as follows:
+
\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
+A dynamical system $\left( \mathcal{X}, f\right)$ is
+{\emph{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}
strongly transitive:
\begin{definition} \label{def11}
-A dynamical system $\left( \mathcal{X}, f\right)$ is {\bf strongly
-transitive} if $\forall x,y \in \mathcal{X}$, $\forall r>0$, $\exists
+A dynamical system $\left( \mathcal{X}, f\right)$ is {\emph{ strongly
+transitive}} if $\forall x,y \in \mathcal{X}$, $\forall r>0$, $\exists
z \in \mathcal{X}$, $d(z,x)~\leq~r \Rightarrow \exists n \in
\mathds{N}^{\ast}$, $f^n(z)=y$.
\end{definition}
Furthermore, those recurrent neural networks exhibit the instability
property:
\begin{definition}
-A dynamical system $\left( \mathcal{X}, f\right)$ is unstable if for
+A dynamical system $\left( \mathcal{X}, f\right)$ is \emph{unstable}
+if for
all $x \in \mathcal{X}$, the orbit $\gamma_x:n \in \mathds{N}
\longmapsto f^n(x)$ is unstable, that means: $\exists \varepsilon >
0$, $\forall \delta>0$, $\exists y \in \mathcal{X}$, $\exists n \in
\varepsilon)$ the maximum cardinality of an $(n,
\varepsilon)$-separated set,
\begin{definition}
-The {\it topological entropy} of the map $f$ is defined by (see e.g.,
+The \emph{topological entropy} of the map $f$ is defined by (see e.g.,
Ref.~\cite{Adler65} or Ref.~\cite{Bowen})
$$h(f)=\lim_{\varepsilon\to 0} \left(\limsup_{n\to \infty}
\frac{1}{n}\log H(n,\varepsilon)\right) \enspace .$$
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.
+
+
+
+
+
+
\section{Suitability of Artificial Neural Networks
for Predicting Chaotic Behaviors}
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
This section presents how (not) chaotic iterations of $G_f$ are
translated into another model more suited to artificial neural
-networks. Formally, input and output vectors are pairs~$((S^t)^{t \in
+networks.
+\JFC{détailler le more suited}
+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}).
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
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.
-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
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.
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}
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}
will be stated. Lastly, thresholds separating systems depending on
the ability to learn their dynamics will be established.
+% \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
+% 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}
+
+
\bibliography{chaos-paper}% Produces the bibliography via BibTeX.
\end{document}
