X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/chaos1.git/blobdiff_plain/a1b71af0bb07232355e939a1e1a6a7aedd40b2d2..999fadfcb0b5ed18bd495364a07850278fade07d:/main.tex?ds=inline diff --git a/main.tex b/main.tex index b72eb6d..cee8840 100644 --- a/main.tex +++ b/main.tex @@ -58,6 +58,11 @@ IUT de Belfort-Montb\'eliard, BP 527, \\ \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 @@ -134,7 +139,9 @@ 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 +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 by combining transfer functions and initial conditions that are both @@ -197,9 +204,9 @@ section. In what follows and for any function $f$, $f^n$ means the composition $f \circ f \circ \hdots \circ f$ ($n$ times) and an \emph{iteration} -of a \emph{dynamical system} the step that consists in -updating the global state $x$ with respect to a function $f$ s.t. -$x^{t+1} = f(x^t)$. +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} @@ -235,57 +242,39 @@ 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 {\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} - -This property implies that a dynamical system cannot be broken into -simpler subsystems. +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 {\emph{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 {\emph{ regular}} on $(\mathcal{X},\tau)$ if the set of - periodic points for $f$ is dense in $\mathcal{X}$ ( for any $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} - -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 {\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 +%\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. + +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$. -\end{definition} - -Finally, -\begin{definition} \label{def5} -The dynamical system that iterates $f$ is {\emph{ chaotic according to Devaney}} -on $(\mathcal{X},\tau)$ if $f$ is regular, topologically transitive, +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. -\end{definition} - In what follows, iterations are said to be \emph{chaotic according Devaney} when corresponding dynamical system is chaotic according Devaney. @@ -310,8 +299,8 @@ 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$ 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*} @@ -328,23 +317,26 @@ $N(i,x)=(x_1,\ldots,\overline{x_i},\ldots,x_n)$ is the configuration 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)$ 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 +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 clasically refered as \emph{asynchronous iterations}. -More préciselly, we have here +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 @@ -407,7 +399,7 @@ classical iterations of a dynamical system. %element. But it can be extended by considering subsets for $S^t$. -To study topological properties of these iteations, we are then left to +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 @@ -436,7 +428,7 @@ 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}$] @@ -453,8 +445,8 @@ In that case, iterations of the function $G_f$ as defined in Eq.~(\ref{eq:Gf}) are chaotic according to Devaney. -Let us then consider two function $f_0$ and $f_1$ both in -$\Bool^n\to\Bool^n$ defined as follows that are used all along this article. +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( @@ -508,15 +500,18 @@ Fig.~\ref{Fig:perceptron}). 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 built to -model the behavior of $G_{f_0}$, which is chaotic according 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. @@ -539,8 +534,8 @@ 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: inputs are $n$ binary digits and one integer value, while outputs are $n$ @@ -556,6 +551,7 @@ connection to an input one. 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 @@ -563,11 +559,15 @@ proven to be chaotic through the following process. Firstly, we denote 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} @@ -596,6 +596,10 @@ like topology to establish, for example, their convergence or, 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} @@ -614,9 +618,12 @@ if and only if, for any pair of disjoint open sets $U$,$V \neq \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 previously presented, which induce a greater unpredictability. Any difference on the initial value of the input @@ -624,8 +631,10 @@ layer is in particular magnified up to be equal to the expansivity constant. 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. +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 @@ -657,7 +666,8 @@ intrinsically complicated and it cannot be decomposed or simplified. 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 @@ -688,7 +698,7 @@ at least $\varepsilon$ apart in the metric $d_n$. Denote by $H(n, \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 .$$ @@ -784,7 +794,9 @@ such functions into a model amenable to be learned by an ANN. 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}). @@ -965,7 +977,7 @@ configuration is always expressed as a natural number, whereas in the 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} @@ -1119,6 +1131,21 @@ consequences in biology, physics, and computer science security fields 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}