@String{IEEETPDS = {IEEE Trans. Parallel Distrib. Systems}}\r
@String{IEEETPAMI = {IEEE Trans. Pattern Analysis Machine Intelligence}}\r
@String{IEEETSMC = {IEEE Trans. on Systems, Man and Cybernetics}}\r
-\r
+@String{TESC = {Turkish Journal of Electrical Engineering and Computer Sciences}}\r
%% 1989 - Cybenko\r
\r
@article{DBLP:journals/jpdc/Cybenko89,\r
\r
@inproceedings {lecun-98b,\r
original = "orig/lecun-98b.ps.gz",\r
-author = "LeCun, Y. and Bottou, L. and Orr, G. and Muller, K.",\r
+author = "LeCun, Yann and Bottou, L\'eon. and Orr, Genevieve B. and Muller, Klaus-Robert",\r
title = "Efficient BackProp",\r
booktitle = "Neural Networks: Tricks of the trade",\r
-editor = "Orr, G. and Muller K.",\r
+editor = "Orr, Genevieve B. and Muller Klaus-Robert",\r
publisher = "Springer",\r
year = 1998\r
}\r
affiliation = {Chongqing University College of Computer Science 400044 Chongqing China},\r
title = {A novel Hash algorithm construction based on chaotic neural network},\r
journal = {Neural Computing and Applications},\r
- publisher = {Springer London},\r
+ publisher = {Springer},\r
issn = {0941-0643},\r
keyword = {Computer Science},\r
pages = {1-9},\r
author = {Ilker Dalkiran and Kenan Danisman},\r
affiliation = {Faculty of Engineering Erciyes University 38039 Kayseri Turkey},\r
title = {Artificial neural network based chaotic generator for cryptology},\r
- journal = {Turk. J.Elec. Eng. \& Comp. Sci.},\r
+ journal = TESC,\r
volume = {18},\r
number = {2},\r
pages = {225-240},\r
location = {Atlanta, Georgia, USA},\r
pages = {2723--2728},\r
numpages = {6},\r
- url = {http://portal.acm.org/citation.cfm?id=1704555.1704664},\r
- acmid = {1704664},\r
- publisher = {IEEE Press},\r
- address = {Piscataway, NJ, USA},\r
+ publisher = {IEEE Press}\r
} \r
\r
\r
+\r
+\r
@ARTICLE{Sullivan06steganalysisfor,\r
- author = {Kenneth Sullivan and Upamanyu Madhow and Shivkumar Ch and B. S. Manjunath},\r
+ author = {Sullivan, Kenneth and Madhow,Upamanyu and Chandrasekaran,Shivkumar and Manjunath,B. S. },\r
title = {Steganalysis for Markov cover data with applications to images},\r
- journal = {IEEE Trans. Inform. Forensics and Security},\r
+ journal = {IEEE Transactions on Information Forensics and Security},\r
year = {2006},\r
volume = {1},\r
pages = {275--287}\r
\r
@misc{Gray47,\r
year=1953, \r
-author = "F. Gray",\r
+author = "Gray, Frank",\r
title = "Pulse code communication",\r
-note = "US Patent 2,632,058, March 17 1953,(filed November 13 1947)"}\r
+note = "{US} Patent 2,632,058, March 17 1953,(filed November 13 1947)"}\r
\r
\r
\r
@INPROCEEDINGS{guyeux10ter,\r
author = {Bahi, Jacques and Guyeux, Christophe},\r
title = {A new chaos-based watermarking algorithm},\r
- booktitle = {SECRYPT'10, Int. conf. on security and cryptography},\r
+ booktitle = {SECRYPT'10, International Conference on Security \r
+and Cryptography},\r
year = {2010},\r
pages = {455--458},\r
address = {Athens, Greece},\r
}\r
\r
@ARTICLE{Banks92,\r
- author = {J. Banks and J. Brooks and G. Cairns and P. Stacey},\r
+ author = {Banks, John and J. Brooks and G. Cairns and P. Stacey},\r
title = {On Devaney's Definition of Chaos},\r
journal = {Amer. Math. Monthly},\r
year = {1992},\r
@INPROCEEDINGS{gfb10:ip,\r
author = {Guyeux, Christophe and Friot, Nicolas and Bahi, Jacques},\r
title = {Chaotic iterations versus Spread-spectrum: chaos and stego security},\r
- booktitle = {IIH-MSP'10, 6-th Int. Conf. on Intelligent Information Hiding and\r
+ booktitle = {IIH-MSP'10, 6-th International Conference on Intelligent Information Hiding and\r
Multimedia Signal Processing},\r
year = {2010},\r
pages = {208--211},\r
@ARTICLE{Adler65,\r
author = {R. L. Adler and A. G. Konheim and M. H. McAndrew},\r
title = {Topological entropy},\r
- journal = {Trans. Amer. Math. Soc.},\r
+ journal = {Transactions of the American Mathematical Society},\r
year = {1965},\r
volume = {114},\r
pages = {309-319},\r
}\r
\r
@ARTICLE{Bowen,\r
- author = {R. Bowen},\r
+ author = {Rufus Bowen},\r
title = {Entropy for group endomorphisms and homogeneous spaces},\r
- journal = {Trans. Amer. Math. Soc.},\r
+ journal = {Transactions of the American Mathematical Society},\r
year = {1971},\r
volume = {153},\r
pages = {401-414},\r
\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.
\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
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.
\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}
\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}
$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}
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}$
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
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
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
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
\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}
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
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
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.
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}
