From: Jean-François Couchot Date: Wed, 14 Sep 2011 15:22:11 +0000 (+0200) Subject: asynchronous pour chaotic X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/chaos1.git/commitdiff_plain/8f2ca538d4cca28cafc98b78ce0c0e697085f3ee asynchronous pour chaotic --- diff --git a/main.tex b/main.tex index c134123..545524f 100644 --- 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 -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. @@ -85,6 +86,7 @@ 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 @@ -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 -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 @@ -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 -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 @@ -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 -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 @@ -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. -\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 -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. @@ -273,32 +275,33 @@ $f$ has {\bf sensitive dependence on initial conditions} if there 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}. -\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 + 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*} @@ -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 -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. @@ -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 -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 @@ -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} -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 @@ -536,7 +545,7 @@ 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$. -Theoretically speakig, such iterations of $F_f$ are thus a formal model of +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''. @@ -584,7 +593,7 @@ transitivity property implies indecomposability. \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} @@ -658,11 +667,11 @@ of $(\mathcal{X},G_{f_0})$ is infinite. \begin{figure} \centering \includegraphics[scale=0.625]{scheme} - \caption{Summary of addressed membership problems} + \caption{Summary of addressed neural networks and chaos problems} \label{Fig:scheme} \end{figure} -The Figure~\ref{Fig:scheme} is a summary of the addressed problems. +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 @@ -807,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 -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