Nous allons tester expérimentalement ce qui a été vu en TD.
Ecrivez une fonction tirage : float -> float x float
prenant en un nombre paramètre réel {$m$} et retournant un point tiré aléatoirement selon la loi uniforme dans le carré {$ [-m, m] \times [-m,m] $}.
En utilisant la fonction précédente, écrivez une fonction monteCarlo : int -> float x float np.array x float np.array
prenant en paramètre {$N$}, le nombre de tirages, et retournant un triplet composé d'une estimation de {$\pi$} par Monte Carlo ainsi que du tableau numpy des {$N$} abscisses et du tableau des {$N$} ordonnées tirées qui ont permis d'obtenir cette estimation.
Tracez le carré {$ [-1, 1] \times [-1,1] $}, le cercle de centre l'origine {$(0,0)$} et de rayon 1, et les points tirés avec une couleur différente selon qu'ils sont dans le cercle ou non. Vous pouvez utiliser le code suivant afin de faire l'affichage.
Vous devriez obtenir une figure similaire à celle ci-dessous:
Nous travaillons sur des textes en anglais pour éviter les problèmes avec les accents.
1) Téléchargez le fichier countWar.pkl qui contient le modèle de bigrammes appris à partir du roman War and Peace de Tolstoï. Ce texte a été choisi car il contient plus de 3 millions de caractères, ce qui est assez long pour apprendre un modèle représentatif d'une langue. Téléchargez également le message secret.txt à décoder (ou celui-ci secret2.txt, même message codé différemment si vous avez des problèmes avec le premier fichier).
2) Exécutez le code suivant pour charger en python le modèle de bigrammes et le message secret.
count
est un dictionnaire : pour chaque lettre du roman War and Peace, il fournit son nombre d'occurrences dans le roman.
mu
et A
.
mu
est un vecteur qui contient la distribution de probabilité initiale sur les lettres.
A
est une matrice qui donne les probabilités d'une lettre étant donné une autre lettre.
secret
contient le message à décoder.
3) Les fonctions de décodage seront représentées comme un dictionnaire où la clé et la valeur stockée sont toutes deux de type caractère (une lettre est codée/décodée en une autre lettre).
Ecrivez une fonction swapF : (char,char) dict -> (char,char) dict
qui prend en argument une fonction de décodage {$\tau_t$} et qui retourne une nouvelle fonction de décodage {$\tau$} construite en écheangeant deux lettres {$c_1$} et {$c_2$} comme indiqué à la question 3.3 du TD:
Vous pouvez tester votre fonction avec le dictionnaire suivant :
4) Ecrivez une fonction decrypt : string x (char,char) dict -> string
qui, étant donné une chaine de caractères mess
et une fonction de décodage {$\tau$}, retourne la chaîne de caractères obtenue par décodage de mess
par {$\tau$}.
Vous pouvez tester votre fonction avec le code suivant :
qui vous produira l'affichage :
>>> decrypt ( "aabcd", tau ) 'bbcad' >>> decrypt ( "dcba", tau ) 'dacb'
5) Créer un dictionnaire (une table de hashage) associant à chaque caractère son indice dans mu/A
. Le code est simplement le suivant:
chars2index['a']
donne simplement accès à l'indice correspondant à la lettre a dans mu
ou A
Il est préférable d'utiliser le fichier des indices déjà généré. Lien : fichierHash.pkl
Attention aux tables de hash en python qui ne donnent plus accès à des listes de clés: il faut re-créer la liste quand on en a besoin.
6) Ecrivez une fonction logLikelihood : string x float np.array x float np.2D-array x (char,int) dict-> string
qui, étant donné un message mess
(chaîne de caractères), les tableaux mu
et A
créés à la question 2 à partir de pickle et du dictionnaire précédent chars2index
, renvoie la log-vraisemblance du message mess
par rapport au modèle bigramme (mu, A)
.
Vous pouvez tester votre fonction avec le code suivant :
qui vous produira l'affichage :
>>> logLikelihood( "abcd", mu, A, chars2index ) -24.600258560804818 >>> logLikelihood( "dcba", mu, A, chars2index ) -26.274828997400395
7) Codez la méthode de Métropolis-Hastings vue en TD sous la forme d'une fonction appelée MetropolisHastings(mess, mu, A, tau, N, chars2index)
en utilisant les fonctions swapF, decrypt et logLikelihood:
mess
est le message codé.
mu
et A
représentent le modèle de bigrammes.
tau
est la fonction de décodage initiale pour démarrer l'algorithme de Métropolis-Hastings.
N
est le nombre maximum d'itérations de l'algorithme.
chars2index
a déjà été vu.
La méthode est une simple boucle où on fait les étapes suivantes :
tau'
en appliquant swapF
avec pour paramètre la fonction de décodage courante tau
tau'
tau'
selon le rapport des vraisemblances
La fonction retourne le message décodé le plus vraisemblable. Vous afficherez la log-vraisemblance à chaque fois qu'elle est améliorée et le message décodé correspondant pour pouvoir observer l'évolution de l'algorithme.
Afin de tester votre fonction, vous pourrez exécuter le code suivant :
Attention: ce code (un peu bête) ne fonctionne pas avec secret.txt
, seulement avec secret2.txt
!
7) Pour accélérer les calculs, nous allons partir d'une fonction de décodage prenant les fréquences d'occurences des lettres (c'est-à-dire la lettre la plus fréquente du message codé sera décodée vers la lettre la plus fréquente observée dans le roman de Tolstoï; ensuite la deuxième lettre la plus fréquente du message codé sera décodée vers la deuxième lettre la plus fréquente observée du roman; et ainsi de suite...)
Vous pouvez utiliser le code suivant pour construire une telle fonction de décodage, nommée ici tau_init
.
Le message sera normalement intelligible lorsque vous arrivez à une log-vraisemblance de plus de -3090
. Toutefois, il reste en général des erreurs dans la traduction... A quel niveau?
Codez la méthode MCMC int x float -> float
vue en TD en utilisant la fonction tirage de l'exercice précédent.
Votre méthode prendra en paramètre la longueur {$N$} de la chaîne de Markov générée par l'algorithme (le nombre d'itérations de l'algorithme) ainsi que le déplacement {$p$} maximal (en abscisse et en ordonnée) que l'on peut effectuer à chaque étape.