Pratiquement, il existe 34226 fonctions de $\Bool^4$ dans lui même qui
vérifient ce graphe d'intéraction.
Cependant, nombreuses sont celles qui possèdent un comportement équivalent.
-Deux fonctions sont equivalentes si leurs \textsc{giu} sont isomorphes
+Deux fonctions sont équivalentes si leurs \textsc{giu} sont isomorphes
(au sens de l'isomorphisme de graphes). Il ne reste alors plus que
520 fonctions $f$ non équivalentes de graphe d'interactions $\Gamma(f)$.
On peut alors construire l'espace
$\mathcal{X}_u =
\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$
-et la fonction d'iteration $G_{f_u}$ définie de
+et la fonction d'itération $G_{f_u}$ définie de
$\mathcal{X}_u$
dans lui-même par
\begin{equation}
On peut tout d'abord démontrer que pour toute fonction booléenne $f$,
$G_{f_u}$ est continue sur $\mathcal{X}_u$ (cf annexe~\ref{anx:cont}).
-Pour charactérister les fonctions rendant chaotiques dans $\mathcal{X}_u$ les itérations de $G_{f_u}$
+Pour caractériser les fonctions rendant chaotiques dans $\mathcal{X}_u$ les itérations de $G_{f_u}$
on se focalise donc que sur la régularité et sur la transitivité de $G_{f_u}$.
Ceci se réalise en établissant les relations d'inclusion entre
les ensembles $\mathcal{T}$ des fonctions topologiquement transitives,
\end{itemize}
-On énnonce les théorèmes successifs suivants.
+On énonce les théorèmes successifs suivants.
Leur preuve est donnée en annexe~\ref{anx:chaos:unaire}.
\begin{theorem} $G_{f_u}$ est transitive si et seulement si
\section{Programmation logique par contraintes sur des domaines finis}
Tout d'abord, soit ${\mathsf{N}}$ le nombre d'éléments.
-Pour éviter d'avoir à gérér des fractions, on peut considérer que
+Pour éviter d'avoir à gérer des fractions, on peut considérer que
les matrices (d'incidence) à générer ont des lignes et des colonnes dont les
sommes valent ${\mathsf{N}}$ à chaque fois.
On cherche ainsi toutes les matrices $M$ de taille $2^{\mathsf{N}}\times 2^{\mathsf{N}}$ telles que
\item pour $j \neq i$, $0 \le M_{ij} \le 1$: on construit l'arc de $i$ à $j$
si et seulement si $M_{ij}$ vaut 1 (et 0 sinon)
-\item pour chque indice de ligne $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$:
+\item pour chaque indice de ligne $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$:
la matrice est stochastique à droite;
-\item pour chque indice de colonne $j$,
+\item pour chaque indice de colonne $j$,
$1 \le j\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le i\le 2^{\mathsf{N}}} M_{ij}$:
la matrice est stochastique à gauche;
\item Toutes les éléments de la somme $\sum_{1\le k\le 2^{\mathsf{N}}}M^k$ sont strictement positif, \textit{i.e.}, le graphe $\textsc{giu}(f)$ est fortement connexe;
\end{enumerate}
Ce problème s'exprime sur des domaines finis entiers avec des opérateurs
-arithmétiques simples (sommes et poduits). il pourrait théoriquement être
-traité par desdémarches de programation logique par contrainte
+arithmétiques simples (sommes et produits). il pourrait théoriquement être
+traité par des démarches de programmation logique par contrainte
sur des domaines finis (comme en PROLOG).
L'algorithme donné en Figure~\ref{fig:prolog}
est en effet le c{\oe}ur du programme PROLOG
\caption{Code PROLOG permettant de trouver toutes les matrices DSSC pour $n=2$}\label{fig:prolog}
\end{figure}
-Enfin, on définit la relation $\mathcal{R}$, qui est établie pourles deux
+Enfin, on définit la relation $\mathcal{R}$, qui est établie pour les deux
fonctions $f$ et $g$ si leur graphes
respectifs $\textsf{giu}(f)$ et $\textsf{giu}(g)$
sont isomorphes.
pour $n=4$.
Cette approche, basée sur une démarche de type \emph{générer, tester} ne peut
pas être retenue pour $n$ de grande taille, même
-en s'appuyant sur l'éfficience de l'algorithme de backtrack natif de PROLOG.
+en s'appuyant sur l'efficience de l'algorithme de backtrack natif de PROLOG.
Cependant, pour des valeurs de $n$ petites, nous avons
-comparé les fonctions non équivalantes selon leur proportion
+comparé les fonctions non équivalentes selon leur proportion
à engendrer des temps de mélange petits (cf. équation~\ref{eq:mt:ex}).
Ces fonctions étant générée, on s'intéresse à étudier à quelle vitesse
un générateur les embarquant converge vers la distribution uniforme.
-C'est l'objeftif de la section suivante.
+C'est l'objectif de la section suivante.
\section{Quantifier l'écart par rapport à la distribution uniforme}
On considère ici une fonction construite comme à la section précédente.
On s'intéresse ici à étudier de manière théorique les
-itérations définies à l'equation~(\ref{eq:asyn}) pour une
+itérations définies à l'équation~(\ref{eq:asyn}) pour une
stratégie donnée.
-Tout d'abord, celles-ci peuvent être inerprétées comme une marche le long d'un
+Tout d'abord, celles-ci peuvent être interprétées comme une marche le long d'un
graphe d'itérations $\textsc{giu}(f)$ tel que le choix de tel ou tel arc est donné par la
stratégie.
-On remaque que ce graphe d'itération est toujours un sous graphe
+On remarque que ce graphe d'itération est toujours un sous graphe
du ${\mathsf{N}}$-cube augmenté des
boucles sur chaque sommet, \textit{i.e.}, les arcs
$(v,v)$ pour chaque $v \in \Bool^{\mathsf{N}}$.
Pour une référence
générale à ce sujet on pourra se référer
au livre~\cite{LevinPeresWilmer2006},
-particulièrementau chapitre sur les temps d'arrêt.
+particulièrement au chapitre sur les temps d'arrêt.
\end{array}
\right.
$$
-La matrice $P$ de la chaine de Markov associée à $f^*$
+La matrice $P$ de la chaîne de Markov associée à $f^*$
est
\[
P=\dfrac{1}{6} \left(
$\nu$ est une distribution on $\Bool^{\mathsf{N}}$, on a
$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}.$$
-Soit $P$ une matrice d'une chaîne de Markovs sur $\Bool^{\mathsf{N}}$.
+Soit $P$ une matrice d'une chaîne de Markov sur $\Bool^{\mathsf{N}}$.
$P(X,\cdot)$ est la distribution induite par la $X^{\textrm{ème}}$ colonne
de $P$.
Si la chaîne de Markov induite par
Un \emph{temps d'arrêt aléatoire} pour la chaîne de
Markov est un temps d'arrêt pour
$(Z_t)_{t\in\mathbb{N}}$.
-Si la chaîne de Markov est irreductible et a $\pi$
+Si la chaîne de Markov est irréductible et a $\pi$
comme distribution stationnaire, alors un
\emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire
(qui peut dépendre de la configuration initiale $X$),
Sans entrer dans les détails de la preuve, on remarque que le calcul
de cette borne ne tient pas en compte le fait qu'on préfère enlever des
chemins hamiltoniens équilibrés.
-En intégrant cette contrainte, la borne supérieure pourraît être réduite.
+En intégrant cette contrainte, la borne supérieure pourrait être réduite.
à la génération de nombres pseudo aléatoires.
On présente tout d'abord le générateur
basé sur des fonctions chaotiques (section~\ref{sub:prng:algo}),
-puis comment intégrer la contrainte de distributionuniforme
+puis comment intégrer la contrainte de distribution uniforme
de la sortie
dans le choix de la fonction à itérer (section~\ref{sub:prng:unif}).
L'approche est évaluée dans la dernière section.
Cet algorithme est utilisée dans notre générateur pour construire la longueur
de la stratégie ainsi que les éléments qui la composent.
Pratiquement, il retourne des entiers dans $\llbracket 1 ; l \rrbracket$
-selon une distributionuniforme et utilise
+selon une distribution uniforme et utilise
\textit{XORshift} qui est une classe de générateurs de
nombres pseudo aléatoires conçus par George Marsaglia.
L'algorithme \textit{XORshift}
exploite itérativement l'opérateur $\oplus$
-sur des nombres obtenus grâce à des decalages de bits.
+sur des nombres obtenus grâce à des décalages de bits.
Cet opérateur, défini dans $\Bool^{n}$,
applique la fonction \og xor \fg{}
aux bits de même rang de ses deux opérandes (\og opération bit à bit \fg{}).
$$\exists k \in \mathds{N}^\ast, \forall i,j \in \llbracket 1; n \rrbracket, M_{ij}^k>0.$$
On énonce enfin le théorème suivant liant les
-vecteur de probabilite
-et les chaines de Markov.
+vecteur de probabilités
+et les chaînes de Markov.
Si $M$ est une matrice stochastique régulière, alors $M$
possède un unique vecteur stationnaire de probabilités $\pi$
($\pi.M = \pi$).
- De plus, si $\pi^0$ est un {vecteurDeProbabilite}
+ De plus, si $\pi^0$ est un {vecteur de probabilités}
et si on définit
la suite $(\pi^{k})^{k \in \Nats}$ par
$\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$
- alors la {chaineDeMarkov} $\pi^k$
+ alors la {chaîne de Markov} $\pi^k$
converge vers $\pi$ lorsque $k$ tend vers l'infini.
\end{theorem}
d'un tel processus
est $M_g = \frac{1}{2} \check{M}_g$,
où $\check{M}_g$ est la matrice d' adjacence donnée en
-figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$.
+figure~\ref{fig:g:incidence} (voir ci-après), et de manière similaire pour $M_h$.
\begin{figure}[h]
\begin{center}
le vecteur d’état de la chaîne de Markov
ait une distribution suffisamment proche de la distribution uniforme.
-On énnonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}.
+On énonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}.
\begin{theorem}
Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son
On reprend le graphe d'interactions $\Gamma(f)$ donné en figure~\ref{fig:G} à la section~\ref{sec:11FCT}.
On a vu qu'il y avait 520 fonctions $f$ non isomorphes de graphe d'interactions $\Gamma(f)$,
-dont seulement 16 d'entre elles possédent une matrice doublement stochastique.
+dont seulement 16 d'entre elles possèdent une matrice doublement stochastique.
La figure~\ref{fig:listfonction} explicite ces 16 fonctions en
définissant les images des éléments de la liste
passent avec succès cette batterie de tests.
Pour conclure cette section, on remarque que le générateur de nombres pseudo-aléatoires
-a été prouvé chaotique pour $b=1$, \textit{i.e.}, lorqu'il y a une sortie pour chaque itération.
-Ceci est difficilement compatible avec la volonté d'avoir une sortie uniformémement distribuée:
+a été prouvé chaotique pour $b=1$, \textit{i.e.}, lorsqu'il y a une sortie pour chaque itération.
+Ceci est difficilement compatible avec la volonté d'avoir une sortie uniformément distribuée:
se rapprocher de cette distribution nécessite en effet un nombre plus élevé
d'itérations $b$ entre chaque sortie. Par exemple, dans l'exemple précédent, il est nécessaire
d'itérer au moins 42 fois entre chaque sortie pour suivre une loi uniforme à $10^{-4}$ près.
\section{Un PRNG basé sur des itérations unaires qui est chaotique }
Cette section présente un espace métrique adapté au générateur de nombres pseudo-aléatoires
-pésenté à l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il représente
+présenté à l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il représente
est chaotique sur cet espace.
\subsection{Un espace $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ pour le PRNG de l'algorithme~\ref{CI Algorithm}}
$\mathsf{p}$ vaut 1 et $p_1=b$.
-Cet algorithme peut être vu comme $b$ compostions de la function $F_{f_u}$.
+Cet algorithme peut être vu comme $b$ compostions de la fonction $F_{f_u}$.
Ceci peut cependant se généraliser à $p_i$, $p_i \in \mathcal{P}$,
compositions fonctionnelles de $F_{f_u}$.
Ainsi, pour chaque $p_i \in \mathcal{P}$, on construit la fonction
La suite $(v^k)_{k \in \Nats}$ définit combien d'itérations sont exécutées au temps $k$ entre deux sorties.
La séquence $(u^k)_{k \in \Nats}$ définit quel élément est modifié (toujours au temps $k$).
-Définissons la fonction de décallage $\Sigma$ pour chaque élément de $\mathds{S}_{\mathsf{N},\mathcal{P}}$.
+Définissons la fonction de décalage $\Sigma$ pour chaque élément de $\mathds{S}_{\mathsf{N},\mathcal{P}}$.
$$\begin{array}{cccc}
\Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow
&\mathds{S}_{\mathsf{N},\mathcal{P}} \\
\end{array}
$$
En d'autres termes, $\Sigma$ reçoit deux suites $u$ et $v$ et
-effectue $v^0$ décallage vers la droite sur la première et un décallage vers la droite
+effectue $v^0$ décalage vers la droite sur la première et un décalage vers la droite
sur la seconde.
suivie par les différences entre $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ et
$\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc.
-Plus précisemment, soit
+Plus précisément, soit
$p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ et
$n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$.
\begin{itemize}
chaque terme étant codé sur $n=2$ éléments, soit 06.
Comme on itère au plus $\max{(\mathcal{P})}$ fois,
on complète cette valeur par des 0 de sorte que
-la chaine obtenue a $n\times \max{(\mathcal{P})}=22$ éléments, soit:
+la chaîne obtenue a $n\times \max{(\mathcal{P})}=22$ éléments, soit:
0600000000000000000000.
De manière similaire, les $\check{v}^0=2$ premiers
termes de $\check{u}$ sont représentés par
\subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant $\textsc{giu}(f)$}
A partir de $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$, on
-definit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suivante:
+définit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suivante:
\begin{itemize}
\item les n{\oe}uds sont les $2^\mathsf{N}$ configurations de $\mathds{B}^\mathsf{N}$,
%\item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples
}
\end{center}
- \caption{Graphes d'iterations $\textsc{giu}_{\mathcal{P}}(h)$ pour $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$}
+ \caption{Graphes d'itérations $\textsc{giu}_{\mathcal{P}}(h)$ pour $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$}
%\label{fig:xplgraphIter}
\end{figure}
Le graphe $\textsc{giu}_{\{1\}}(h)$ a déjà été donné à la figure~\ref{fig:h:iter}.
Les graphes $\textsc{giu}_{\{2\}}(h)$, $\textsc{giu}_{\{3\}}(h)$ et
$\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnés aux figure~\ref{fig:h2prng}, ~\ref{fig:h3prng} et ~\ref{fig:h23prng}.
-Le premier (repsectivement le second)
+Le premier (respectivement le second)
illustre le comportement du générateur lorsque qu'on itère exactement
2 fois (resp. 3 fois) puis qu'on affiche le résultat.
Le dernier donnerait le comportement d'un générateur qui s'autoriserait
Dans le schéma généralisé, à la $t^{\textrm{ème}}$ itération,
c'est l'ensemble
des $s_{t}^{\textrm{ème}}$ éléments (inclus dans $[n]$) qui
-sont mis à jour (c.f. équation~(\ref{eq:schema:generalise})).
+sont mis à jour (cf. équation~(\ref{eq:schema:generalise})).
On redéfinit la fonction la fonction
$F_{f_g}: \Bool^{\mathsf{N}} \times \mathcal{P}(\{1, \ldots, \mathsf{N}\})
\rightarrow \Bool^{\mathsf{N}}$ par
$X^0=(x^0,S)$
-On onstruit cette fois-ci l'espace
+On construit cette fois ci l'espace
$\mathcal{X}_g = \Bool^{\mathsf{N}} \times
\mathcal{P}(\{1, \ldots, {\mathsf{N}}\})^{\Nats}$
Les réseaux de neurones chaotiques ont été étudiés à de maintes reprises
par le passé en raison notamment de leurs applications potentielles:
%les mémoires associatives~\cite{Crook2007267}
-les composants utils à la sécurité comme les fonctions de
+les composants utiles à la sécurité comme les fonctions de
hachage~\cite{Xiao10},
le tatouage numérique~\cite{1309431,Zhang2005759}
ou les schémas de chiffrement~\cite{Lian20091296}.
Dans tous ces cas, l'emploi de fonctions chaotiques est motivé par
-leur comportement imprévisibile et proche de l'aléa.
+leur comportement imprévisible et proche de l'aléa.
Les réseaux de neurones chaotiques peuvent être conçus selon plusieurs
principes. Des neurones modifiant leur état en suivant une fonction non
linéaire son par exemple appelés neurones chaotiques~\cite{Crook2007267}.
L'architecture de réseaux de neurones de type Perceptron multi-couches
-(MLP) n'iterent quant à eux, pas nécesssairement de fonctions chaotiques.
+(MLP) n'itèrent quant à eux, pas nécessairement de fonctions chaotiques.
Il a cependant été démontré que ce sont des approximateurs
universels~\cite{Cybenko89,DBLP:journals/nn/HornikSW89}.
Ils permettent, dans certains cas, de simuler des comportements
Ainsi $G_{f_u}$ est chaotique d'après le théorème~\ref{Th:CaracIC}.
On considère ici le schéma unaire défini par l'équation (\ref{eq:asyn}).
-On construit un perceptron multi-couche associé à la fonction
+On construit un Perceptron multi-couches associé à la fonction
$F_{f_u}$.
Plus précisément, pour chaque entrée
$(x,s) \in \mathds{B}^n \times [n]$,
à travers les liens de retours.
\item Lorsque le réseau est activé à la $t^{th}$ itération, l'état du
système $x^t \in \mathds{B}^n$ reçu depuis la couche de sortie ainsi que le
- premier terme de la sequence $(S^t)^{t \in \Nats}$
+ premier terme de la séquence $(S^t)^{t \in \Nats}$
(\textit{i.e.}, $S^0 \in [n]$) servent à construire le nouveau vecteur de sortie.
Ce nouveau vecteur, qui représente le nouvel état du système dynamique, satisfait:
\begin{equation}
\begin{figure}
\centering
\includegraphics[scale=0.625]{images/perceptron}
- \caption{Un perceptron équivalent aux itérations unitaires}
+ \caption{Un Perceptron équivalent aux itérations unitaires}
\label{Fig:perceptron}
\end{figure}
\section{Vérifier si un réseau de neurones est chaotique}
\label{S3}
On s'intéresse maintenant au cas où l'on dispose d'un
-réseau de neurones de type perceptron multi-couches
+réseau de neurones de type Perceptron multi-couches
dont on cherche à savoir s'il est chaotique (parce qu'il a par exemple été
déclaré comme tel) au sens de Devaney.
On considère de plus que sa topologie est la suivante:
le vecteur
$\left(y_1,\dots,y_n\right) \in \mathds{B}^n$, où
$\left(y_1,\dots,y_n\right)$ sont les sorties du réseau neuronal
-àaprès l'initialisation de la couche d'entrée avec
+après l'initialisation de la couche d'entrée avec
$\left(s,\left(x_1,\dots, x_n\right)\right)$. Ensuite, on définie $f:
\mathds{B}^n \rightarrow \mathds{B}^n$ telle que
$f\left(x_1,x_2,\dots,x_n\right)$ est égal à
Cette section s'intéresse à étudier le comportement d'un réseau de neurones
face à des itérations unaires chaotiques, comme définies à
la section~\ref{sec:TIPE12}.
-Plus précésment, on considère dans cette partie une fonction dont le graphe
+Plus précisément, on considère dans cette partie une fonction dont le graphe
des itérations unaires est fortement connexe et une séquence dans
$[n]^{\mathds{N}}$. On cherche à construire un réseau de neurones
qui approximerait les itérations de la fonction $G_{f_u}$ comme définie
arbitrairement des configurations diamétralement
opposées dans le $n$-cube comme une puissance de
deux et la configuration immédiatement précédente: 10000 serait modélisée
-par 16 et et 01111 par 15 alros que leur distance de Hamming est 15.
+par 16 et et 01111 par 15 alors que leur distance de Hamming est 15.
De manière similaire, ce codage éloigne des configurations qui sont
très proches: par exemple 10000 et 00000 ont une distance de Hamming
de 1 et sont respectivement représentées par 16 et 0.
Pour ces raisons, le codage retenu est celui des codes de Gray~\cite{Gray47}.
Concentrons nous sur la traduction de la stratégie.
-Il n'est naturellement pas possible de traduire une stragtégie
+Il n'est naturellement pas possible de traduire une stratégie
infinie quelconque à l'aide d'un nombre fini d'éléments.
On se restreint donc à des stratégies de taille
-$l \in \llbracket 2,k\rrbracket$, où $k$ est un parametre défini
+$l \in \llbracket 2,k\rrbracket$, où $k$ est un paramètre défini
initialement.
Chaque stratégie est mémorisée comme un entier naturel exprimé en base
$n+1$: à chaque itération, soit aucun élément n'est modifié, soit un
Les sorties (stratégies et configurations) sont mémorisées
selon les mêmes règles.
-Concentrons nous sur la complexité du problèmew.
+Concentrons nous sur la complexité du problème.
Chaque entrée, de l'entrée-sortie de l'outil est un triplet
composé d'une configuration $x$, d'un extrait $S$ de la stratégie à
itérer de taille $l \in \llbracket 2, k\rrbracket$ et d'un nombre $m \in \llbracket 1, l-1\rrbracket$ d'itérations à exécuter.
2^n \times \left(\dfrac{(k-1)\times n^{k+1}}{n-1} - \dfrac{n^{k+1}-n^2}{(n-1)^2}\right) \enspace .
$$
Par exemple, pour $4$ éléments binaires et une stratégie d'au plus
-$3$~termes on obtient 2304 couples d'entrée-sorties.
+$3$~termes on obtient 2304 couples d'entrée-sortie.
\subsection{Expérimentations}
\label{section:experiments}
-On se focalise dans cette section sur l'entraînement d'un perceptron
-multi-couche pour apprendre des itérations chaotiques. Ce type de réseau
+On se focalise dans cette section sur l'entraînement d'un Perceptron
+multi-couches pour apprendre des itérations chaotiques. Ce type de réseau
ayant déjà été évalué avec succès dans la prédiction de
séries chaotiques temporelles. En effet, les auteurs de~\cite{dalkiran10}
ont montré qu'un MLP pouvait apprendre la dynamique du circuit de Chua.
Ce réseau avec rétropropagation est composé de deux couches
-et entrainé à l'aide d'une propagation arrière Bayesienne.
+et entraîné à l'aide d'une propagation arrière Bayesienne.
-Le choix de l'achitecture du réseau ainsi que de la méthode d'apprentissage
+Le choix de l'architecture du réseau ainsi que de la méthode d'apprentissage
ont été détaillé dans~\cite{bcgs12:ij}.
En pratique, nous avons considéré des configurations de
quatre éléments booléens
figures~\ref{Fig:chaotic_predictions} et~\ref{Fig:non-chaotic_predictions}.
De plus, comme dans le codage précédent, les stratégies ne peuvent pas être
prédites.
-On constate que ce second codage réduit certe le nombre de sorties, mais est
+On constate que ce second codage réduit certes le nombre de sorties, mais est
largement moins performant que le premier.
On peut expliquer ceci par le fait
que ce second codage garantit que deux entiers successifs correspondent
-à deux configurations voisines, \textit{ie.e}, qui ne diffèrent que d'un
+à deux configurations voisines, \textit{i.e.}, qui ne diffèrent que d'un
élément.
La réciproque n'est cependant pas établie et deux configurations voisines
-peuvent être traduitent par des entiers très éloignés et ainsi difficils
-àapprendre.
+peuvent être traduites par des entiers très éloignés et ainsi difficiles
+ à apprendre.
\begin{figure}[ht]
\section{Conclusion}
-Dans ce chapitre, nous avons établi une simlilitude entre les itérations
-chaotiques et une famille de perceptrons multicouches.
+Dans ce chapitre, nous avons établi une similitude entre les itérations
+chaotiques et une famille de Perceptrons multi-couches.
Nous avons d'abord montré comment construire un réseau de neurones
ayant un comportement chaotique.
Nous avons présenté ensuite comment vérifier si un réseau de neurones
\noindent sinon.
En démarrant de $x^0=00011$, le système atteint $x^1 = 01011$ et boucle entre
ces deux configurations. Pour une même stratégies, les itérations
-asynhrones divergent alors que les synchrones convergent.
+asynchrones divergent alors que les synchrones convergent.
Les sections suivantes de ce chapitre montrent comment résoudre ce problème.
\subsection{Itérations Mixes}
Cependant, même pour des réseaux discrets à peu d'éléments,
le nombre de configurations induites explose rapidement.
Les \emph{Model-Checkers}~\cite{Hol03,nusmv02,Blast07,MCErlang07,Bogor03}
-sont des classes d'outils qui addressent le problème de vérifier automatiquement
+sont des classes d'outils qui adressent le problème de vérifier automatiquement
qu'un modèle vérifie une propriété donnée. Pour traiter le problème d'explosion
combinatoire, ces outils appliquent des méthodes d'ordre partiel, d'abstraction,
de quotientage selon une relation d'équivalence.
\begin{xpl}
On considère un exemple à trois éléments dans $\Bool$.
- Chaque configuration est ainsi un élement de $\Bool^3$, \textit{i.e.},
+ Chaque configuration est ainsi un élément de $\Bool^3$, \textit{i.e.},
un nombre entre 0 et 7.
La \Fig{fig:map} précise la fonction $f$ considérée et
la \Fig{fig:xplgraph:inter:mc} donne son graphe d'intéraction.
}
\end{lstlisting}
\end{tiny}
-\caption{Process scheduler pour la stratégie pseudo pérodique.
+\caption{Process scheduler pour la stratégie pseudo périodique.
\label{fig:scheduler}}
\end{minipage}
\begin{minipage}[h]{.30\linewidth}
\subsection{La stratégie}\label{sub:spin:strat}
Regardons comment une stratégie pseudo périodique peut être représentée en PROMELA.
Intuitivement, un process \verb+scheduler+ (comme représenté à la {\sc Figure}~\ref{fig:scheduler})
-est iterrativement appelé pour construire chaque $s^t$ représentant
+est itérativement appelé pour construire chaque $s^t$ représentant
les éléments possiblement mis à jour à l'itération $t$.
Basiquement, le process est une boucle qui est débloquée lorsque la valeur du sémaphore
\item elle mémorise dans \texttt{Xd} la valeurs disponible pour chaque élément grâce à la fonction \texttt{fetch\_values}; cette fonction est détaillée
dans la section suivante;
\item une boucle %sur les \texttt{ar\_len} éléments qui peuvent être modifiés
- met à jour iterrativement la valeur de $j$ (grâce à l'appel de fonction \texttt{f(j)})
+ met à jour itérativement la valeur de $j$ (grâce à l'appel de fonction \texttt{f(j)})
pour peu que celui-ci doive être modifié, \textit{i.e.}, pour peu qu'il soit renseigné dans
\texttt{mods[count]}; le code source de \texttt{F} est donné en {\sc Figure}~\ref{fig:p} et est une
traduction directe de l'application $f$;
Les valeurs des éléments sont ajoutées dans ce canal au travers de la fonction \verb+diffuse_values+. L'objectif de cette fonction
est de stocker les valeurs de $x$ (représenté
dans le modèle par \verb+Xp+) dans le canal \verb+channels+.
-Il permet au modèle-checker SPIN d'exécuter
+Il permet au model-checker SPIN d'exécuter
le modèle PROMELA comme s'il pouvait y avoir des délais entre processus
Il y a deux cas différents pour la valeur de $X_{j}$:
\begin{itemize}
de l'exécution en SPIN de $\psi$ est bornée par $2^{m(\delta_0+1)+n(n+2)}$.
\end{theorem}
\begin{Proof}
- Une configuration est une valuation des variables globales.
+ Une configuration est une évaluation des variables globales.
Leur nombre ne dépend que de celles qui ne sont pas constantes.
Les variables \verb+Xp+ et \verb+X+ engendrent $2^{2n}$ états.
\begin{theorem}
Si $f_i$ ne dépend pas de $x_j$, alors pour tout $x\in [{\mathsf{N}}]$,
-$f_i(\overline{x}^j)$ est égal à $f_i(x)$, \textit{i.e},
+$f_i(\overline{x}^j)$ est égal à $f_i(x)$, \textit{i.e.},
$f'_{ij}(x)=0$. Ainsi $B(f)_{ij}$ est nulle. La réciproque est aussi vraie.
\end{theorem}
