Cours
# caracteres correspondants char => index (pour recherche dans mu/A)
#chars2index = dict(zip(np.array(list(count.keys()))[rankFreq], rankFreq))
chars2index = dict(zip(np.array(list(count.keys())), np.arange(len(count.keys()))))
import numpy.random as npr
def updateOccurrences(text, count):
for c in text:
if c == u'\n':
continue
try:
count[c] += 1
except KeyError as e:
count[c] = 1
def mostFrequent(count):
bestK = []
bestN = -1
for k in count.keys():
if (count[k]>bestN):
bestK = [k]
bestN = count[k]
elif (count[k]==bestN):
bestK.append(k)
return bestK
def replaceF(f, kM, k):
try:
for c in f.keys():
if f[c] == k:
f[c] = f[kM]
f[kM] = k
return
except KeyError as e:
f[kM] = k
def mostFrequentF(message, count1, f={}):
count = dict(count1)
countM = {}
updateOccurrences(message, countM)
while len(countM) > 0:
bestKM = mostFrequent(countM)
bestK = mostFrequent(count)
if len(bestKM)==1:
kM = bestKM[0]
else:
kM = bestKM[npr.random_integers(0, len(bestKM)-1)]
if len(bestK)==1:
k = bestK[0]
else:
k = bestK[npr.random_integers(0, len(bestK)-1)]
replaceF(f, kM, k)
countM.pop(kM)
count.pop(k)
return f
tau_init = mostFrequentF(mp, count, identityTau () )
5) Ecrivez une fonction '''logLikelihood''' @@: string x float np.array x float np.2D-array x char list -> 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 une liste de caractères @@chars@@, renvoie la log-vraisemblance du message @@mess@@ par rapport au modèle bigramme @@(mu, A)@@. Comme @@mu@@ et @@A@@ sont des matrices, il faut assurer la correspondance entre une lettre du message et son indice correspondant dans @@mu@@ et @@A@@.
Le dernier paramètre (@@chars@@) est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre, par exemple, en utilisant @@chars.index('a')@@ pour récupérer l'indice de la lettre 'a'. Pour la valeur de @@chars@@, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que @@count.keys()@@ (vous avez créé la variable @@count@@ à la question 2 à partir de pickle).
6) 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)@@ en utilisant les fonctions '''swapF''', '''decrypt''' et '''logLikelihood''':
5)Ecrivez une fonction '''logLikelihood''' @@: string x float np.array x float np.2D-array x char list -> 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 une liste de caractères @@chars@@, renvoie la log-vraisemblance du message @@mess@@ par rapport au modèle bigramme @@(mu, A)@@. Comme @@mu@@ et @@A@@ sont des matrices, il faut assurer la correspondance entre une lettre du message et son indice correspondant dans @@mu@@ et @@A@@.
Le dernier paramètre (@@chars@@) est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre, par exemple, en utilisant @@chars.index('a')@@ pour récupérer l'indice de la lettre 'a'. Pour la valeur de @@chars@@, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que @@count.keys()@@ (vous avez créé la variable @@count@@ à la question 2 à partir de pickle).
Vous pouvez tester votre fonction avec le codesuivant :
logLikelihood( "abcd", mu, A, count.keys () )
logLikelihood( "dcba", mu, A, count.keys () )
(count, mu, A) = pkl.load(file("countWar.pkl", "rb"))
secret = (open("secret.txt", "r")).read()[0:-1] # -1 pour supprimer le saut de ligne
7) Pour accélérer les calculs, nous allons partir d'une fonction de décodage prenant les fréquences d'occurence des lettres (c'est-à-dire la lettre la plus fréquente du message encodé 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ée 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 {$fInit$}.
def identityF(keys):
f = {}
for k in keys:
f[k] = k
return f
fInit = identityF(count.keys())
fInit = mostFrequentF(mp, count, fInit)
8) Lancer le script suivant pour tester vos fonctions :
(:source lang=python:)
MetropolisHastings(secret, mu, A, fInit, int(5e4))
(:sourceend:)
4) Ecrivez une fonction '''decrypt''' @@: string x (char,char) dict -> string@@ qui, étant donné une chaine de caractères @@m@@ et une fonction de décodage {$\tau$}, retourne la chaîne de caractères obtenue par décodage de @@m@@ par {$\tau$}.
5) Ecrivez une fonction '''logLikelihood''' @@: string x float np.array x float np.2D-array x char list -> string@@ qui, étant donné un message @@m@@ (chaîne de caractères), les tableaux @@mu@@ et @@A@@ créés à la question 2 à partir de pickle et une liste de caractères @@chars@@, renvoie la log-vraisemblance du message @@m@@ par rapport au modèle bigramme @@(mu, A)@@. Comme @@mu@@ et @@A@@ sont des matrices, il faut assurer la correspondance entre une lettre du message et son indice correspondant dans @@mu@@ et @@A@@.
La fonction retourne le message décodé le plus vraisemblable.
!!%section% Estimation de {$\pi$} par MCMC
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.
Ecrire une fonction {$swapF(f)$} qui prend en argument une fonction de décodage et qui retourne une nouvelle fonction de décodage construite à partir de f où deux lettres choisies au hasard ont été échangées.
Télécharger également le message [[(Attach:)secret.txt | secret.txt]] (ou celui-ci [[(Attach:)secret2.txt | secret2.txt]], même message codé différemment si vous avez des problèmes avec le premier fichier) à décoder.
2)Exécuter le code suivant pour charger en python le modèle de bigrammes et le message secret.
La variable{$count$} est un dictionnaire, pour chaque lettre du roman ''War and Peace'', il fournit son nombre d'occurrence dans le roman.
Le modèle de bigrammes est décrit par les variables{$mu$} et {$A$}.
La variable{$mu$} est un vecteur qui contient la distribution de probabilité initiale sur les lettres.
La variable{$A$} est une matrice qui donne les probabilités d'une lettre étant donné une autre lettre.
La variable{$secret$} contient le message à décoder.
Vous devriez obtenir une figure similaire à celle ci-dessous:
%block text-align=center% %width=500px% Attach:2015_tme9_montCarlo.png
Coder la méthode {$MCMC$} vu en TD en utilisant la fonction tirage.
pl.plot([-1, -1, 1, 1], [-1, 1, 1, -1], '-')
pl.plot(x, y, 'b')
pl.plot(x, -y, 'b')
pl.plot(x[dist <=1], y[dist <=1], "go")
pl.plot(x[dist>1], y[dist>1], "ro")
pl.show()
Ecrire une fonction {$tirage$} prenant en paramètre {$m$} et retournant un point tiré aléatoirement selon la loi uniforme dans le carré {$ [-m, m]^2 $}
En utilisant la fonction précédente, écrire une fonction {$monteCarlo$} prenant en paramètre {$N$}, le nombre de tirages et retournant une estimation de {$\pi$} par Monte Carlo.
Tracer le carré {$ [-1, 1]^2 $}, le cercle de centre l'origine et de rayon 1, et les points tirés avec une couleur différente selon qu'ils sont dans le cercle ou non.
def mostFrequent(count):
bestK = []
bestN = -1
for k in count.keys():
if (count[k]>bestN):
bestK = [k]
bestN = count[k]
elif (count[k]==bestN):
bestK.append(k)
return bestK
def updateOccurrences(text, count):
for c in text:
if c == u'\n':
continue
try:
count[c] += 1
except KeyError as e:
count[c] = 1
4) Ecrire une fonction {$logLikelihood(m, mu, A, chars)$} qui calcule la log-vraisemblance d'un message {$m$} à partir du modèle bigramme {$(mu, A)$}.
5) Coder la méthode de Métropolis-Hastings vu en TD sous la forme d'une fonction appelée {$MetropolisHastings(m, mu, A, f, N)$} en utilisant les fonctions {$swapF$}, {$decrypt$} et {$logLikelihood$}.
6) Pour accélérer les calculs, nous allons partir d'une fonction de décodage prenant les fréquences d'occurence des lettres (c'est-à-dire la lettre la plus fréquente du message encodé 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ée sera décodée vers la deuxième lettre la plus fréquente observée du roman; et ainsi de suite...)
7) Lancer le script suivant pour tester vos fonctions :
Ecrire une fonction ''tirage'' prenant en paramètre {$m$} et retournant un point tiré aléatoirement selon la loi uniforme dans le carré {$ [-m, m]^2 $}
En utilisant la fonction précédente, écrire une fonction ''monteCarlo'' prenant en paramètre {$N$}, le nombre de tirages et retournant une estimation de {$\pi$} par Monte Carlo.
Vous pourrez tracer le carré {$ [-1, 1]^2 $}, le cercle de centre l'origine et de rayon 1, et les points tirés avec une couleur différente selon qu'ils sont dans le cercle ou non.
fonction...
2) Exécuter le code suivant pour charger en python le modèle de bigrammes.
import codecs
import numpy as np
import numpy.random as npr
import copy
- tirage de {$f'$} grâce à {$swapF$} à partir de {$f$}
- calcul de la log-vraisemblance du message décodée grâce à {$f'$}
- tirage pour accepter ou non la transition selon le rapport des vraisemblances
- si la transition est acceptée, conserver le message décodé avec la plus haute vraisemblance.
Cours.TME9 History
Hide minor edits - Show changes to output
Changed lines 115-116 from:
Lien : [[(Attach:)fichierHash.pkl]]
to:
Il est préférable d'utiliser le fichier des indices déjà généré. Lien : [[(Attach:)fichierHash.pkl]]
Changed lines 179-180 from:
cles = np.array(list(set(secret))) # tous les caracteres de secret
rankSecret = np.argsort(-np.array([secret.count(c) for c in cles]))
rankSecret = np.argsort(-np.array([
to:
cles = np.array(list(set(secret2))) # tous les caracteres de secret2
rankSecret = np.argsort(-np.array([secret2.count(c) for c in cles]))
rankSecret = np.argsort(-np.array([secret2.count(c) for c in cles]))
Changed line 159 from:
MetropolisHastings( secret2, mu, A, identityTau (), 10000, chars2index)
to:
MetropolisHastings( secret2, mu, A, identityTau (count), 10000, chars2index)
Changed line 159 from:
MetropolisHastings( secret2, mu, A, identityTau (), 10000 )
to:
MetropolisHastings( secret2, mu, A, identityTau (), 10000, chars2index)
Changed line 183 from:
MetropolisHastings(secret2, mu, A, tau_init, 50000 )
to:
MetropolisHastings(secret2, mu, A, tau_init, 50000, chars2index)
Changed line 186 from:
Le message sera normalement décodé lorsque vous arrivez à une log-vraisemblance de plus de @@-3090@@
to:
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?
Deleted lines 174-176:
#chars2index = dict(zip(np.array(list(count.keys()))[rankFreq], rankFreq))
chars2index = dict(zip(np.array(list(count.keys())), np.arange(len(count.keys()))))
Changed lines 162-163 from:
to:
'''Attention''': ce code (un peu bête) ne fonctionne pas avec @@secret.txt@@, seulement avec @@secret2.txt@@!
Added line 166:
Changed lines 168-221 from:
def updateOccurrences(text, count):
for c in text:
if c == u'\n':
continue
try:
count[c] += 1
except KeyError as e:
count[c] = 1
def mostFrequent(count):
bestK = []
bestN = -1
for k in count.keys():
if (count[k]>bestN):
bestK = [k]
bestN = count[k]
elif (count[k]==bestN):
bestK.append(k)
return bestK
def replaceF(f, kM, k):
try:
for c in f.keys():
if f[c] == k:
f[c] = f[kM]
f[kM] = k
return
except KeyError as e:
f[kM] = k
def mostFrequentF(message, count1, f={}):
count = dict(count1)
countM = {}
updateOccurrences(message, countM)
while len(countM) > 0:
bestKM = mostFrequent(countM)
bestK = mostFrequent(count)
if len(bestKM)==1:
kM = bestKM[0]
else:
kM = bestKM[npr.random_integers(0, len(bestKM)-1)]
if len(bestK)==1:
k = bestK[0]
else:
k = bestK[npr.random_integers(0, len(bestK)-1)]
replaceF(f, kM, k)
countM.pop(kM)
count.pop(k)
return f
tau_init = mostFrequentF(mp, count, identityTau () )
to:
# ATTENTION: mu = proba des caractere init, pas la proba stationnaire
# => trouver les caractères fréquents = sort (count) !!
# distribution stationnaire des caracteres
freqKeys = np.array(list(count.keys()))
freqVal = np.array(list(count.values()))
# indice des caracteres: +freq => - freq dans la references
rankFreq = (-freqVal).argsort()
# caracteres correspondants char => index (pour recherche dans mu/A)
#chars2index = dict(zip(np.array(list(count.keys()))[rankFreq], rankFreq))
chars2index = dict(zip(np.array(list(count.keys())), np.arange(len(count.keys()))))
# analyse mess. secret: indice les + freq => - freq
cles = np.array(list(set(secret))) # tous les caracteres de secret
rankSecret = np.argsort(-np.array([secret.count(c) for c in cles]))
# ATTENTION: 37 cles dans secret, 77 en général... On ne code que les caractères les plus frequents de mu, tant pis pour les autres
# alignement des + freq dans mu VS + freq dans secret
tau_init = dict([(cles[rankSecret[i]], freqKeys[rankFreq[i]]) for i in range(len(rankSecret))])
# => trouver les caractères fréquents = sort (count) !!
# distribution stationnaire des caracteres
freqKeys = np.array(list(count.keys()))
freqVal = np.array(list(count.values()))
# indice des caracteres: +freq => - freq dans la references
rankFreq = (-freqVal).argsort()
# caracteres correspondants char => index (pour recherche dans mu/A)
#chars2index = dict(zip(np.array(list(count.keys()))[rankFreq], rankFreq))
chars2index = dict(zip(np.array(list(count.keys())), np.arange(len(count.keys()))))
# analyse mess. secret: indice les + freq => - freq
cles = np.array(list(set(secret))) # tous les caracteres de secret
rankSecret = np.argsort(-np.array([secret.count(c) for c in cles]))
# ATTENTION: 37 cles dans secret, 77 en général... On ne code que les caractères les plus frequents de mu, tant pis pour les autres
# alignement des + freq dans mu VS + freq dans secret
tau_init = dict([(cles[rankSecret[i]], freqKeys[rankFreq[i]]) for i in range(len(rankSecret))])
Added line 189:
Le message sera normalement décodé lorsque vous arrivez à une log-vraisemblance de plus de @@-3090@@
Changed line 154 from:
def identityTau ():
to:
def identityTau (count):
Added lines 113-114:
@@chars2index['a']@@ donne simplement accès à l'indice correspondant à la lettre a dans @@mu@@ ou @@A@@
Changed lines 117-119 from:
Le dernier paramètre (@@chars@@) est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre, par exemple, en utilisant @@chars.index('a')@@ pour récupérer l'indice de la lettre 'a'. Pour la valeur de @@chars@@, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que @@count.keys()@@ (vous avez créé la variable @@count@@ à la question 2 à partir de pickle).
to:
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)@@.
Changed lines 122-123 from:
logLikelihood( "abcd", mu, A, count.keys () )
logLikelihood("dcba", mu, A, count.keys () )
logLikelihood(
to:
logLikelihood( "abcd", mu, A, chars2index )
logLikelihood( "dcba", mu, A, chars2index )
logLikelihood( "dcba", mu, A, chars2index )
Changed line 128 from:
>>> logLikelihood( "abcd", mu, A, count.keys () )
to:
>>> logLikelihood( "abcd", mu, A, chars2index )
Changed line 130 from:
>>> logLikelihood( "dcba", mu, A, count.keys () )
to:
>>> logLikelihood( "dcba", mu, A, chars2index )
Changed lines 134-135 from:
to:
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''':
Changed lines 139-140 from:
* Enfin, l'argument @@N@@ est le nombre maximum d'itérations de l'algorithme.
to:
* L'argument @@N@@ est le nombre maximum d'itérations de l'algorithme.
* L'argument @@chars2index@@ a déjà été vu.
* L'argument @@chars2index@@ a déjà été vu.
Changed line 156 from:
for k in count.keys ():
to:
for k in list(count.keys ()):
Changed line 233 from:
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.
to:
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.
Changed lines 108-113 from:
5)
Le dernier paramètre (@@chars@@) est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre, par exemple, en utilisant @@chars.index('a')@@ pour récupérer l'indice de la lettre 'a'. Pour la valeur de @@chars@@, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que @@count.keys()@@ (vous avez créé la variable @@count@@ à la question 2 à partir de pickle).
Vous pouvez tester votre fonction avec le code
to:
5) Créer un dictionnaire (une table de hashage) associant à chaque caractère son indice dans @@mu/A@@. Le code est simplement le suivant:
Changed lines 110-111 from:
logLikelihood
to:
chars2index = dict(zip(np.array(list(count.keys())), np.arange(len(count.keys()))))
Added lines 113-124:
'''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.
5) Ecrivez une fonction '''logLikelihood''' @@: string x float np.array x float np.2D-array x char list -> 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 une liste de caractères @@chars@@, renvoie la log-vraisemblance du message @@mess@@ par rapport au modèle bigramme @@(mu, A)@@. Comme @@mu@@ et @@A@@ sont des matrices, il faut assurer la correspondance entre une lettre du message et son indice correspondant dans @@mu@@ et @@A@@.
Le dernier paramètre (@@chars@@) est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre, par exemple, en utilisant @@chars.index('a')@@ pour récupérer l'indice de la lettre 'a'. Pour la valeur de @@chars@@, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que @@count.keys()@@ (vous avez créé la variable @@count@@ à la question 2 à partir de pickle).
Vous pouvez tester votre fonction avec le code suivant :
(:source lang=python:)
logLikelihood( "abcd", mu, A, count.keys () )
logLikelihood( "dcba", mu, A, count.keys () )
(:sourceend:)
5) Ecrivez une fonction '''logLikelihood''' @@: string x float np.array x float np.2D-array x char list -> 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 une liste de caractères @@chars@@, renvoie la log-vraisemblance du message @@mess@@ par rapport au modèle bigramme @@(mu, A)@@. Comme @@mu@@ et @@A@@ sont des matrices, il faut assurer la correspondance entre une lettre du message et son indice correspondant dans @@mu@@ et @@A@@.
Le dernier paramètre (@@chars@@) est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre, par exemple, en utilisant @@chars.index('a')@@ pour récupérer l'indice de la lettre 'a'. Pour la valeur de @@chars@@, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que @@count.keys()@@ (vous avez créé la variable @@count@@ à la question 2 à partir de pickle).
Vous pouvez tester votre fonction avec le code suivant :
(:source lang=python:)
logLikelihood( "abcd", mu, A, count.keys () )
logLikelihood( "dcba", mu, A, count.keys () )
(:sourceend:)
Deleted line 231:
Added line 69:
# si vos fichiers sont dans un repertoire "ressources"
Changed lines 69-70 from:
secret
to:
with open("./ressources/countWar.pkl", 'rb') as f:
(count, mu, A) = pkl.load(f, encoding='latin1')
with open("./ressources/secret.txt", 'r') as f:
secret = f.read()[0:-1] # -1 pour supprimer le saut de ligne
(count, mu, A) = pkl.load(f, encoding='latin1')
with open("./ressources/secret.txt", 'r') as f:
secret = f.read()[0:-1] # -1 pour supprimer le saut de ligne
Deleted line 224:
Changed line 207 from:
MetropolisHastings(secret, mu, A, tau_init, 50000 )
to:
MetropolisHastings(secret2, mu, A, tau_init, 50000 )
Added lines 107-121:
Vous pouvez tester votre fonction avec le code suivant :
(:source lang=python:)
logLikelihood( "abcd", mu, A, count.keys () )
logLikelihood( "dcba", mu, A, count.keys () )
(:sourceend:)
qui vous produira l'affichage :
>>> logLikelihood( "abcd", mu, A, count.keys () )
-24.600258560804818
>>> logLikelihood( "dcba", mu, A, count.keys () )
-26.274828997400395
(:source lang=python:)
logLikelihood( "abcd", mu, A, count.keys () )
logLikelihood( "dcba", mu, A, count.keys () )
(:sourceend:)
qui vous produira l'affichage :
>>> logLikelihood( "abcd", mu, A, count.keys () )
-24.600258560804818
>>> logLikelihood( "dcba", mu, A, count.keys () )
-26.274828997400395
Changed lines 138-140 from:
7) Pour accélérer les calculs
Vous pouvez utiliser le code suivant pour construire une telle fonction de décodage, nommée ici {$fInit$}.
to:
Afin de tester votre fonction, vous pourrez exécuter le code suivant :
Added lines 141-152:
def identityTau ():
tau = {}
for k in count.keys ():
tau[k] = k
return tau
MetropolisHastings( secret2, mu, A, identityTau (), 10000 )
(:sourceend:)
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@@.
(:source lang=python:)
tau = {}
for k in count.keys ():
tau[k] = k
return tau
MetropolisHastings( secret2, mu, A, identityTau (), 10000 )
(:sourceend:)
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@@.
(:source lang=python:)
Deleted lines 174-179:
f = {}
for k in keys:
f[k] = k
return f
Changed lines 205-206 from:
to:
tau_init = mostFrequentF(mp, count, identityTau () )
MetropolisHastings(secret, mu, A, tau_init, 50000 )
MetropolisHastings(secret, mu, A, tau_init, 50000 )
Deleted lines 209-212:
(:source lang=python:)
MetropolisHastings(secret, mu, A, fInit, int(5e4))
(:sourceend:)
Changed lines 80-83 from:
5) Ecrivez une fonction '''logLikelihood''' @@: string x float np.array x float np.2D-array x char list -> string@@ qui, étant donné un message @@m@@ (chaîne de caractères), les tableaux @@mu@@ et @@A@@ créés à la question 2 à partir de pickle et une liste de caractères @@chars@@, renvoie la log-vraisemblance du message @@m@@ par rapport au modèle bigramme @@(mu, A)@@. Comme @@mu@@ et @@A@@ sont des matrices, il faut assurer la correspondance entre une lettre du message et son indice correspondant dans @@mu@@ et @@A@@.
to:
Vous pouvez tester votre fonction avec le dictionnaire suivant :
(:source lang=python:)
tau = {'a' : 'b', 'b' : 'c', 'c' : 'a', 'd' : 'd' }
(:sourceend:)
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 :
(:source lang=python:)
tau = {'a' : 'b', 'b' : 'c', 'c' : 'a', 'd' : 'd' }
decrypt ( "aabcd", tau )
decrypt ( "dcba", tau )
(:sourceend:)
qui vous produira l'affichage :
>>> decrypt ( "aabcd", tau )
'bbcad'
>>> decrypt ( "dcba", tau )
'dacb'
5) Ecrivez une fonction '''logLikelihood''' @@: string x float np.array x float np.2D-array x char list -> 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 une liste de caractères @@chars@@, renvoie la log-vraisemblance du message @@mess@@ par rapport au modèle bigramme @@(mu, A)@@. Comme @@mu@@ et @@A@@ sont des matrices, il faut assurer la correspondance entre une lettre du message et son indice correspondant dans @@mu@@ et @@A@@.
(:source lang=python:)
tau = {'a' : 'b', 'b' : 'c', 'c' : 'a', 'd' : 'd' }
(:sourceend:)
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 :
(:source lang=python:)
tau = {'a' : 'b', 'b' : 'c', 'c' : 'a', 'd' : 'd' }
decrypt ( "aabcd", tau )
decrypt ( "dcba", tau )
(:sourceend:)
qui vous produira l'affichage :
>>> decrypt ( "aabcd", tau )
'bbcad'
>>> decrypt ( "dcba", tau )
'dacb'
5) Ecrivez une fonction '''logLikelihood''' @@: string x float np.array x float np.2D-array x char list -> 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 une liste de caractères @@chars@@, renvoie la log-vraisemblance du message @@mess@@ par rapport au modèle bigramme @@(mu, A)@@. Comme @@mu@@ et @@A@@ sont des matrices, il faut assurer la correspondance entre une lettre du message et son indice correspondant dans @@mu@@ et @@A@@.
Changed lines 107-111 from:
6) Coder la méthode de Métropolis-Hastings vu en TD sous la forme d'une fonction appelée {$MetropolisHastings(m, mu, A, f, N)$} en utilisant les fonctions {$swapF$}, {$decrypt$} et {$logLikelihood$}.
Le paramètre{$m$} est le message codé.
Les paramètres{$mu$}, {$A$} représentent le modèle de bigrammes.
L'argument{$f$} est la fonction de décodage initiale pour démarrer l'algorithme de Métropolis-Hastings.
Enfin, l'argument{$N$} est le nombre maximum d'itérations de l'algorithme.
Le paramètre
Les paramètres
L'argument
Enfin, l'argument
to:
6) 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)@@ en utilisant les fonctions '''swapF''', '''decrypt''' et '''logLikelihood''':
* Le paramètre @@mess@@ est le message codé.
* Les paramètres @@mu@@ et @@A@@ représentent le modèle de bigrammes.
* L'argument @@tau@@ est la fonction de décodage initiale pour démarrer l'algorithme de Métropolis-Hastings.
* Enfin, l'argument @@N@@ est le nombre maximum d'itérations de l'algorithme.
* Le paramètre @@mess@@ est le message codé.
* Les paramètres @@mu@@ et @@A@@ représentent le modèle de bigrammes.
* L'argument @@tau@@ est la fonction de décodage initiale pour démarrer l'algorithme de Métropolis-Hastings.
* Enfin, l'argument @@N@@ est le nombre maximum d'itérations de l'algorithme.
Changed lines 115-117 from:
* tirage de {$f'$} grâce à {$swapF$} à partir de la fonction courante {$f$}
* calcul de la log-vraisemblance du message décodée grâce à {$f'$}
* tirage pour accepter ou non la transition vers {$f'$} selon le rapport des vraisemblances
* calcul
* tirage pour accepter ou non la transition vers {$f
to:
* tirage d'une nouvelle fonction de décodage @@tau'@@ en appliquant @@swapF@@ avec pour paramètre la fonction de décodage courante @@tau@@
* calcul de la log-vraisemblance du message décodé grâce à @@tau'@@
* tirage pour accepter ou non la transition vers @@tau'@@ selon le rapport des vraisemblances
* calcul de la log-vraisemblance du message décodé grâce à @@tau'@@
* tirage pour accepter ou non la transition vers @@tau'@@ selon le rapport des vraisemblances
Changed lines 119-120 from:
La fonction retourne le message décodé la plus vraisemblable.
to:
La fonction retourne le message décodé le plus vraisemblable.
Added line 122:
Changed lines 83-86 from:
5) Ecrire une fonction {$logLikelihood(m, mu, A, chars)$} qui calcule la log-vraisemblance d'un message {$m$} à partir du modèle bigramme {$(mu, A)$}.
Comme {$mu$} et {$A$} sont des matrices, il faut assurer la correspondance entre une lettre et un indice (de {$mu$} ou de {$A$}).
Le paramètre {$chars$} est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre, par exemple, en utilisant {$chars.index('a')$} pour récupérer l'indice de la lettre 'a'.
Pour la valeur de {$chars$}, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que {$count.keys()$} ou {$f.keys()$}.
Comme {$mu$} et {$A$} sont des matrices, il faut assurer la correspondance entre une lettre et un indice (
Le paramètre {$
Pour la valeur de {$chars$}, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que {$count.keys
to:
5) Ecrivez une fonction '''logLikelihood''' @@: string x float np.array x float np.2D-array x char list -> string@@ qui, étant donné un message @@m@@ (chaîne de caractères), les tableaux @@mu@@ et @@A@@ créés à la question 2 à partir de pickle et une liste de caractères @@chars@@, renvoie la log-vraisemblance du message @@m@@ par rapport au modèle bigramme @@(mu, A)@@. Comme @@mu@@ et @@A@@ sont des matrices, il faut assurer la correspondance entre une lettre du message et son indice correspondant dans @@mu@@ et @@A@@.
Le dernier paramètre (@@chars@@) est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre, par exemple, en utilisant @@chars.index('a')@@ pour récupérer l'indice de la lettre 'a'. Pour la valeur de @@chars@@, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que @@count.keys()@@ (vous avez créé la variable @@count@@ à la question 2 à partir de pickle).
Le dernier paramètre (@@chars@@) est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre, par exemple, en utilisant @@chars.index('a')@@ pour récupérer l'indice de la lettre 'a'. Pour la valeur de @@chars@@, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que @@count.keys()@@ (vous avez créé la variable @@count@@ à la question 2 à partir de pickle).
Changed lines 15-18 from:
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.
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.
to:
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.
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.
Changed lines 74-76 from:
Ecrivez une fonction '''swapF(f)''' qui prend en argument une fonction de décodage et qui retourne une nouvelle fonction de décodage construite à partir de '''f''' où deux lettres choisies au hasard ont été échangées.
4) Ecrire une fonction{$decrypt(m, f)$} qui retourne une chaîne de caractères. Elle décode le message {$m$} grâce à la fonction {$f$}.
4) Ecrire une fonction
to:
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:
* {$\tau(c) = \tau_t(c)$} pour tout {$c$} tel que {$c \neq c_1$} et {$c \neq c_2$};
* {$\tau(c_1) = \tau_t(c_2)$};
* {$\tau(c_2) = \tau_t(c_1)$}.
4) Ecrivez une fonction '''decrypt''' @@: string x (char,char) dict -> string@@ qui, étant donné une chaine de caractères @@m@@ et une fonction de décodage {$\tau$}, retourne la chaîne de caractères obtenue par décodage de @@m@@ par {$\tau$}.
* {$\tau(c) = \tau_t(c)$} pour tout {$c$} tel que {$c \neq c_1$} et {$c \neq c_2$};
* {$\tau(c_1) = \tau_t(c_2)$};
* {$\tau(c_2) = \tau_t(c_1)$}.
4) Ecrivez une fonction '''decrypt''' @@: string x (char,char) dict -> string@@ qui, étant donné une chaine de caractères @@m@@ et une fonction de décodage {$\tau$}, retourne la chaîne de caractères obtenue par décodage de @@m@@ par {$\tau$}.
Changed lines 49-55 from:
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.
to:
Changed lines 164-177 from:
(:sourceend:)
to:
(:sourceend:)
----
!! %part%Partie optionnelle%%
----
!!%section% Estimation de {$\pi$} par MCMC
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.
----
!! %part%Partie optionnelle%%
----
!!%section% Estimation de {$\pi$} par MCMC
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.
Added line 65:
Changed line 80 from:
to:
Ecrivez une fonction '''swapF(f)''' qui prend en argument une fonction de décodage et qui retourne une nouvelle fonction de décodage construite à partir de '''f''' où deux lettres choisies au hasard ont été échangées.
Changed line 60 from:
1) Télécharger le fichier [[(Attach:)countWar.pkl | countWar.pkl]] qui contient le modèle de bigrammes appris à partir du roman ''War and Peace'' de Tolstoï.
to:
1) Téléchargez le fichier [[(Attach:)countWar.pkl | countWar.pkl]] qui contient le modèle de bigrammes appris à partir du roman ''War and Peace'' de Tolstoï.
Changed lines 62-69 from:
2)
La variable
Le modèle de bigrammes est décrit par les variables
La variable
La variable
La variable
to:
Téléchargez également le message [[(Attach:)secret.txt | secret.txt]] à décoder (ou celui-ci [[(Attach:)secret2.txt | 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.
* La variable @@count@@ est un dictionnaire : pour chaque lettre du roman ''War and Peace'', il fournit son nombre d'occurrences dans le roman.
* Le modèle de bigrammes est décrit par les variables @@mu@@ et @@A@@.
* La variable @@mu@@ est un vecteur qui contient la distribution de probabilité initiale sur les lettres.
* La variable @@A@@ est une matrice qui donne les probabilités d'une lettre étant donné une autre lettre.
* La variable @@secret@@ contient le message à décoder.
2) Exécutez le code suivant pour charger en python le modèle de bigrammes et le message secret.
* La variable @@count@@ est un dictionnaire : pour chaque lettre du roman ''War and Peace'', il fournit son nombre d'occurrences dans le roman.
* Le modèle de bigrammes est décrit par les variables @@mu@@ et @@A@@.
* La variable @@mu@@ est un vecteur qui contient la distribution de probabilité initiale sur les lettres.
* La variable @@A@@ est une matrice qui donne les probabilités d'une lettre étant donné une autre lettre.
* La variable @@secret@@ contient le message à décoder.
Changed lines 51-57 from:
Codez la méthode '''MCMC''' vue en TD en utilisant la fonction '''tirage''' de l'exercice précédent.
Votre méthode prendra en paramètre lavaleur {$m$}, le "burnin time" (c'est-à-dire le nombre d'itérations initiales que l'on saute) et le "mixing time" (c'est-à-dire le nombre d'itérations entre deux échantillons) :
* le burnin time permet de garantir que la distribution des états devient proche de la distribution stationnaire
* le mixing time permet de garantir que deux tirages successifs sont décorrélés
Comme première approche, vous pouvez supposer que ces deux valeurs sont nulles, c'est-à-dire qu'on fait un tirage par transition dans la chaîne de Markov.
En calculant l'erreur d'estimation, c'est-à-dire, la valeur absolue de la différence entre l'estimation et {$\pi$} (à moyenner bien sûr sur plusieurs essais), vous pourrez chercher les meilleurs valeurs des paramètres.
Votre méthode prendra en paramètre la
* le burnin time permet de garantir que la distribution des états devient proche de la distribution stationnaire
* le mixing time permet de garantir que deux tirages successifs sont décorrélés
Comme première approche, vous pouvez supposer que ces deux valeurs sont nulles, c'est-à-dire qu'on fait un tirage par transition dans la chaîne de Markov.
En calculant l'erreur d'estimation, c'est-à-dire, la valeur absolue de la différence entre l'estimation et {$\pi$} (à moyenner bien sûr sur plusieurs essais), vous pourrez chercher les meilleurs valeurs des paramètres
to:
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.
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.
Added lines 44-47:
Vous devriez obtenir une figure similaire à celle ci-dessous:
%block text-align=center% %width=500px% Attach:2015_tme9_montCarlo.png
Changed line 47 from:
Codez la méthode {$MCMC$} vue en TD en utilisant la fonction tirage de l'exercice précédent.
to:
Codez la méthode '''MCMC''' vue en TD en utilisant la fonction '''tirage''' de l'exercice précédent.
Changed lines 17-18 from:
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ée tirées qui ont permis d'obtenir cette estimation.
to:
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.
Changed line 47 from:
to:
Codez la méthode {$MCMC$} vue en TD en utilisant la fonction tirage de l'exercice précédent.
Changed lines 17-18 from:
En utilisant la fonction précédente, écrivez une fonction '''monteCarlo''' @@int -> float x (float,float) np.array@@ prenant en paramètre {$N$}, le nombre de tirages, et retournant un couple composé d'une estimation de {$\pi$} par Monte Carlo ainsi que de le tableau numpy des {$N$} coordonnées tirées qui ont permis d'obtenir cette estimation.
to:
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ée tirées qui ont permis d'obtenir cette estimation.
Changed lines 22-25 from:
import matplotlib.pyplot as pl
pl.figure()
pl
to:
import matplotlib.pyplot as plt
plt.figure()
plt.figure()
Changed lines 27-28 from:
to:
plt.plot([-1, -1, 1, 1], [-1, 1, 1, -1], '-')
Changed lines 32-34 from:
to:
plt.plot(x, y, 'b')
plt.plot(x, -y, 'b')
plt.plot(x, -y, 'b')
Changed lines 40-42 from:
to:
plt.plot(x[dist <=1], y[dist <=1], "go")
plt.plot(x[dist>1], y[dist>1], "ro")
plt.show()
plt.plot(x[dist>1], y[dist>1], "ro")
plt.show()
Changed lines 15-20 from:
Ecrivez une fonction '''tirage''' @@int -> float x float@@ prenant en paramètre {$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$} prenant en paramètre {$N$}, le nombre de tirages, et retournant une estimation de {$\pi$} par Monte Carlo.
Tracez le carré {$ [-1, 1] \times [-1,1]$}, le cerclede 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 qui suppose que la fonction {$monteCarlo$} retourne l'estimation de pi et l'ensemble des coordonnées tirées.
En utilisant la fonction précédente, écrivez une fonction
Tracez le carré {$ [-1, 1] \times [-1,1]$}, le cercle
to:
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,float) np.array@@ prenant en paramètre {$N$}, le nombre de tirages, et retournant un couple composé d'une estimation de {$\pi$} par Monte Carlo ainsi que de le tableau numpy des {$N$} coordonné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.
En utilisant la fonction précédente, écrivez une fonction '''monteCarlo''' @@int -> float x (float,float) np.array@@ prenant en paramètre {$N$}, le nombre de tirages, et retournant un couple composé d'une estimation de {$\pi$} par Monte Carlo ainsi que de le tableau numpy des {$N$} coordonné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.
Changed line 15 from:
Ecrivez une fonction {$tirage$} prenant en paramètre {$m$} et retournant un point tiré aléatoirement selon la loi uniforme dans le carré {$[-m, m] \times [-m,m]$}.
to:
Ecrivez une fonction '''tirage''' @@int -> float x float@@ prenant en paramètre {$m$} et retournant un point tiré aléatoirement selon la loi uniforme dans le carré {$ [-m, m] \times [-m,m] $}.
Changed lines 15-19 from:
En utilisant la fonction précédente
to:
Ecrivez une fonction {$tirage$} prenant en paramètre {$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$} prenant en paramètre {$N$}, le nombre de tirages, et retournant une estimation de {$\pi$} par Monte Carlo.
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.
En utilisant la fonction précédente, écrivez une fonction {$monteCarlo$} prenant en paramètre {$N$}, le nombre de tirages, et retournant une estimation de {$\pi$} par Monte Carlo.
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.
Added line 21:
Changed lines 3-4 from:
to:
%define=part apply=block bgcolor=#e6d8c0%
Added line 8:
!! %part%Partie obligatoire%%
Added lines 112-122:
def mostFrequent(count):
bestK = []
bestN = -1
for k in count.keys():
if (count[k]>bestN):
bestK = [k]
bestN = count[k]
elif (count[k]==bestN):
bestK.append(k)
return bestK
Added lines 103-111:
def updateOccurrences(text, count):
for c in text:
if c == u'\n':
continue
try:
count[c] += 1
except KeyError as e:
count[c] = 1
Changed line 61 from:
Télécharger également le message [[(Attach:)secret.txt | secret.txt]] à décoder.
to:
Télécharger également le message [[(Attach:)secret.txt | secret.txt]] (ou celui-ci [[(Attach:)secret2.txt | secret2.txt]], même message codé différemment si vous avez des problèmes avec le premier fichier) à décoder.
Changed lines 46-49 from:
Votre méthode prendra en paramètre la valeur {$m$}, le "burnin time" (c'est-à-dire le nombre d'itérations initiales que l'on saute) et le "mixing time" (c'est-à-dire le nombre d'itérations entre deux échantillons).
to:
Votre méthode prendra en paramètre la valeur {$m$}, le "burnin time" (c'est-à-dire le nombre d'itérations initiales que l'on saute) et le "mixing time" (c'est-à-dire le nombre d'itérations entre deux échantillons) :
* le burnin time permet de garantir que la distribution des états devient proche de la distribution stationnaire
* le mixing time permet de garantir que deux tirages successifs sont décorrélés
Comme première approche, vous pouvez supposer que ces deux valeurs sont nulles, c'est-à-dire qu'on fait un tirage par transition dans la chaîne de Markov.
* le burnin time permet de garantir que la distribution des états devient proche de la distribution stationnaire
* le mixing time permet de garantir que deux tirages successifs sont décorrélés
Comme première approche, vous pouvez supposer que ces deux valeurs sont nulles, c'est-à-dire qu'on fait un tirage par transition dans la chaîne de Markov.
Changed line 78 from:
to:
5) Ecrire une fonction {$logLikelihood(m, mu, A, chars)$} qui calcule la log-vraisemblance d'un message {$m$} à partir du modèle bigramme {$(mu, A)$}.
Changed line 83 from:
to:
6) Coder la méthode de Métropolis-Hastings vu en TD sous la forme d'une fonction appelée {$MetropolisHastings(m, mu, A, f, N)$} en utilisant les fonctions {$swapF$}, {$decrypt$} et {$logLikelihood$}.
Changed line 96 from:
to:
7) Pour accélérer les calculs, nous allons partir d'une fonction de décodage prenant les fréquences d'occurence des lettres (c'est-à-dire la lettre la plus fréquente du message encodé 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ée sera décodée vers la deuxième lettre la plus fréquente observée du roman; et ainsi de suite...)
Changed line 141 from:
to:
8) Lancer le script suivant pour tester vos fonctions :
Changed line 45 from:
Coder la méthode ''MCMC'' vu en TD en utilisant la fonction tirage.
to:
Coder la méthode {$MCMC$} vu en TD en utilisant la fonction tirage.
Changed line 18 from:
Vous pouvez utiliser le code suivant qui suppose que la fonction {$monteCarlo$} retourne l'estimation de pi, l'ensemble des coordonnées tirées.
to:
Vous pouvez utiliser le code suivant qui suppose que la fonction {$monteCarlo$} retourne l'estimation de pi et l'ensemble des coordonnées tirées.
Changed lines 13-19 from:
En utilisant la fonction précédente, écrire une fonction ''monteCarlo'' prenant en paramètre {$N$}, le nombre de tirages et retournant une estimation de {$\pi$} par Monte Carlo.
Vous pourrez tracer le carré {$ [-1, 1]^2 $}, le cercle de centre l'origine et de rayon 1, et les points tirés avec une couleur différente selon qu'ils sont dans le cercle ou non.
to:
Ecrire une fonction {$tirage$} prenant en paramètre {$m$} et retournant un point tiré aléatoirement selon la loi uniforme dans le carré {$ [-m, m]^2 $}
En utilisant la fonction précédente, écrire une fonction {$monteCarlo$} prenant en paramètre {$N$}, le nombre de tirages et retournant une estimation de {$\pi$} par Monte Carlo.
Tracer le carré {$ [-1, 1]^2 $}, le cercle de centre l'origine 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 qui suppose que la fonction {$monteCarlo$} retourne l'estimation de pi, l'ensemble des coordonnées tirées.
(:source lang=python:)
import matplotlib.pyplot as pl
pl.figure()
# trace le carré
pl.plot([-1, -1, 1, 1], [-1, 1, 1, -1], '-')
# trace le cercle
x = np.linspace(-1, 1, 100)
y = np.sqrt(1- x*x)
pl.plot(x, y, 'b')
pl.plot(x, -y, 'b')
# estimation par Monte Carlo
pi, x, y = monteCarlo(int(1e4))
# trace les points dans le cercle et hors du cercle
dist = x*x + y*y
pl.plot(x[dist <=1], y[dist <=1], "go")
pl.plot(x[dist>1], y[dist>1], "ro")
pl.show()
(:sourceend:)
En utilisant la fonction précédente, écrire une fonction {$monteCarlo$} prenant en paramètre {$N$}, le nombre de tirages et retournant une estimation de {$\pi$} par Monte Carlo.
Tracer le carré {$ [-1, 1]^2 $}, le cercle de centre l'origine 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 qui suppose que la fonction {$monteCarlo$} retourne l'estimation de pi, l'ensemble des coordonnées tirées.
(:source lang=python:)
import matplotlib.pyplot as pl
pl.figure()
# trace le carré
pl.plot([-1, -1, 1, 1], [-1, 1, 1, -1], '-')
# trace le cercle
x = np.linspace(-1, 1, 100)
y = np.sqrt(1- x*x)
pl.plot(x, y, 'b')
pl.plot(x, -y, 'b')
# estimation par Monte Carlo
pi, x, y = monteCarlo(int(1e4))
# trace les points dans le cercle et hors du cercle
dist = x*x + y*y
pl.plot(x[dist <=1], y[dist <=1], "go")
pl.plot(x[dist>1], y[dist>1], "ro")
pl.show()
(:sourceend:)
Changed line 48 from:
secret = (open("secret.txt", "r")).read()[0, -1] # -1 pour supprimer le saut de ligne
to:
secret = (open("secret.txt", "r")).read()[0:-1] # -1 pour supprimer le saut de ligne
Added lines 77-78:
import numpy.random as npr
Changed line 110 from:
replaceF(f, kM, k) #f[kM] = k
to:
replaceF(f, kM, k)
Changed line 40 from:
Le modèle bigramme est décrit par les variables {$mu$} et {$A$}.
to:
Le modèle de bigrammes est décrit par les variables {$mu$} et {$A$}.
Added line 43:
La variable {$secret$} contient le message à décoder.
Changed lines 54-59 from:
4) Ecrire une fonction {$logLikelihood(m, mu, A, chars)$} qui calcule la log-vraisemblance d'un message m à partir du modèle bigramme {$(mu, A)$}.
Comme mu et A sont des matrices, il faut assurer la correspondance entre une lettre et un indice (de {$mu$} ou de {$A$}).
Le paramètre chars est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre. Par exemple, {$chars.index('a')$}.
Pour la valeurde chars, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que {$count.keys()$} ou {$f.keys()$}.
5) Coder la méthode de Métropolis-Hastings vu en TD sous la forme d'une fonction appelée {$MetropolisHastings(m, mu, A, f, N)$} en utilisant les fonctions {$swapF$} et {$logLikelihood$}.
Comme mu et A sont des matrices, il faut assurer la correspondance entre une lettre et un indice (de
Pour la valeur
5) Coder la méthode
to:
4) Ecrire une fonction {$decrypt(m, f)$} qui retourne une chaîne de caractères. Elle décode le message {$m$} grâce à la fonction {$f$}.
4) Ecrire une fonction {$logLikelihood(m, mu, A, chars)$} qui calcule la log-vraisemblance d'un message {$m$} à partir du modèle bigramme {$(mu, A)$}.
Comme {$mu$} et {$A$} sont des matrices, il faut assurer la correspondance entre une lettre et un indice (de {$mu$} ou de {$A$}).
Le paramètre {$chars$} est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre, par exemple, en utilisant {$chars.index('a')$} pour récupérer l'indice de la lettre 'a'.
Pour la valeur de {$chars$}, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que {$count.keys()$} ou {$f.keys()$}.
5) Coder la méthode de Métropolis-Hastings vu en TD sous la forme d'une fonction appelée {$MetropolisHastings(m, mu, A, f, N)$} en utilisant les fonctions {$swapF$}, {$decrypt$} et {$logLikelihood$}.
4) Ecrire une fonction {$logLikelihood(m, mu, A, chars)$} qui calcule la log-vraisemblance d'un message {$m$} à partir du modèle bigramme {$(mu, A)$}.
Comme {$mu$} et {$A$} sont des matrices, il faut assurer la correspondance entre une lettre et un indice (de {$mu$} ou de {$A$}).
Le paramètre {$chars$} est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre, par exemple, en utilisant {$chars.index('a')$} pour récupérer l'indice de la lettre 'a'.
Pour la valeur de {$chars$}, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que {$count.keys()$} ou {$f.keys()$}.
5) Coder la méthode de Métropolis-Hastings vu en TD sous la forme d'une fonction appelée {$MetropolisHastings(m, mu, A, f, N)$} en utilisant les fonctions {$swapF$}, {$decrypt$} et {$logLikelihood$}.
Changed line 63 from:
Les paramètres {$mu$}, A représentent le modèle de bigrammes.
to:
Les paramètres {$mu$}, {$A$} représentent le modèle de bigrammes.
Changed line 67 from:
* tirage de {$f'$} grâce à {$swapF$} à partir de {$f$}
to:
* tirage de {$f'$} grâce à {$swapF$} à partir de la fonction courante {$f$}
Changed lines 69-71 from:
* tirage pour accepter ou non la transition selon le rapport des vraisemblances
* si la transition est acceptée,conserver le message décodé avec la plus haute vraisemblance.
* si la transition est acceptée,
to:
* tirage pour accepter ou non la transition vers {$f'$} selon le rapport des vraisemblances
* si la transition est acceptée, sauvegarder le message décodé avec la plus haute vraisemblance.
La fonction retourne le message décodé la plus vraisemblable.
* si la transition est acceptée, sauvegarder le message décodé avec la plus haute vraisemblance.
La fonction retourne le message décodé la plus vraisemblable.
Changed line 75 from:
Vous pouvez utiliser la fonction suivante pour construire une telle fonction de décodage.
to:
Vous pouvez utiliser le code suivant pour construire une telle fonction de décodage, nommée ici {$fInit$}.
Changed lines 77-114 from:
to:
def identityF(keys):
f = {}
for k in keys:
f[k] = k
return f
def replaceF(f, kM, k):
try:
for c in f.keys():
if f[c] == k:
f[c] = f[kM]
f[kM] = k
return
except KeyError as e:
f[kM] = k
def mostFrequentF(message, count1, f={}):
count = dict(count1)
countM = {}
updateOccurrences(message, countM)
while len(countM) > 0:
bestKM = mostFrequent(countM)
bestK = mostFrequent(count)
if len(bestKM)==1:
kM = bestKM[0]
else:
kM = bestKM[npr.random_integers(0, len(bestKM)-1)]
if len(bestK)==1:
k = bestK[0]
else:
k = bestK[npr.random_integers(0, len(bestK)-1)]
replaceF(f, kM, k) #f[kM] = k
countM.pop(kM)
count.pop(k)
return f
fInit = identityF(count.keys())
fInit = mostFrequentF(mp, count, fInit)
f = {}
for k in keys:
f[k] = k
return f
def replaceF(f, kM, k):
try:
for c in f.keys():
if f[c] == k:
f[c] = f[kM]
f[kM] = k
return
except KeyError as e:
f[kM] = k
def mostFrequentF(message, count1, f={}):
count = dict(count1)
countM = {}
updateOccurrences(message, countM)
while len(countM) > 0:
bestKM = mostFrequent(countM)
bestK = mostFrequent(count)
if len(bestKM)==1:
kM = bestKM[0]
else:
kM = bestKM[npr.random_integers(0, len(bestKM)-1)]
if len(bestK)==1:
k = bestK[0]
else:
k = bestK[npr.random_integers(0, len(bestK)-1)]
replaceF(f, kM, k) #f[kM] = k
countM.pop(kM)
count.pop(k)
return f
fInit = identityF(count.keys())
fInit = mostFrequentF(mp, count, fInit)
Changed lines 117-120 from:
7)
to:
7) Lancer le script suivant pour tester vos fonctions :
(:source lang=python:)
MetropolisHastings(secret, mu, A, fInit, int(5e4))
(:sourceend:)
(:source lang=python:)
MetropolisHastings(secret, mu, A, fInit, int(5e4))
(:sourceend:)
Changed lines 36-37 from:
2) Exécuter
to:
Télécharger également le message [[(Attach:)secret.txt | secret.txt]] à décoder.
2) Exécuter le code suivant pour charger en python le modèle de bigrammes et le message secret.
2) Exécuter le code suivant pour charger en python le modèle de bigrammes et le message secret.
Added line 47:
secret = (open("secret.txt", "r")).read()[0, -1] # -1 pour supprimer le saut de ligne
Changed line 34 from:
1) Télécharger le fichier ''countWar.pkl'' qui contient le modèle de bigrammes appris à partir du roman ''War and Peace'' de Tolstoï.
to:
1) Télécharger le fichier [[(Attach:)countWar.pkl | countWar.pkl]] qui contient le modèle de bigrammes appris à partir du roman ''War and Peace'' de Tolstoï.
Deleted lines 42-45:
import numpy as np
import numpy.random as npr
import copy
Changed lines 66-69 from:
to:
* tirage de {$f'$} grâce à {$swapF$} à partir de {$f$}
* calcul de la log-vraisemblance du message décodée grâce à {$f'$}
* tirage pour accepter ou non la transition selon le rapport des vraisemblances
* si la transition est acceptée, conserver le message décodé avec la plus haute vraisemblance.
* calcul de la log-vraisemblance du message décodée grâce à {$f'$}
* tirage pour accepter ou non la transition selon le rapport des vraisemblances
* si la transition est acceptée, conserver le message décodé avec la plus haute vraisemblance.
Changed line 34 from:
1) Télécharger le fichier ''countWar.pkl'' qui contient le modèle de bigrammes appris à partir du roman "War and Peace" de Tolstoï.
to:
1) Télécharger le fichier ''countWar.pkl'' qui contient le modèle de bigrammes appris à partir du roman ''War and Peace'' de Tolstoï.
Changed lines 38-41 from:
La variable count est un dictionnaire, pour chaque lettre du roman "War and Peace", il fournit son nombre d'occurrence dans le roman.
Le modèle bigramme est décrit par les variables $mu$ et $A$.
La variable mu est un vecteur qui contient la distribution de probabilité initiale sur les lettres.
La variable A est une matrice qui donne les probabilités d'une lettre étant donné une autre lettre.
Le modèle bigramme est décrit par les variables $mu$ et $A$.
La variable mu est un vecteur qui contient la distribution de probabilité initiale sur les lettres.
La variable A est une matrice qui donne les probabilités d'une lettre étant donné une autre lettre.
to:
La variable {$count$} est un dictionnaire, pour chaque lettre du roman ''War and Peace'', il fournit son nombre d'occurrence dans le roman.
Le modèle bigramme est décrit par les variables {$mu$} et {$A$}.
La variable {$mu$} est un vecteur qui contient la distribution de probabilité initiale sur les lettres.
La variable {$A$} est une matrice qui donne les probabilités d'une lettre étant donné une autre lettre.
Le modèle bigramme est décrit par les variables {$mu$} et {$A$}.
La variable {$mu$} est un vecteur qui contient la distribution de probabilité initiale sur les lettres.
La variable {$A$} est une matrice qui donne les probabilités d'une lettre étant donné une autre lettre.
Changed lines 53-64 from:
Ecrire une fonction swapF(f) qui prend en argument une fonction de décodage et qui retourne une nouvelle fonction de décodage construite à partir de f où deux lettres choisies au hasard ont été échangées.
4) Ecrire une fonction logLikelihood(m, mu, A, chars) qui calcule la log-vraisemblance d'un message m à partir du modèle bigramme (mu, A).
Comme mu et A sont des matrices, il faut assurer la correspondance entre une lettre et un indice (de mu ou de A).
Le paramètre chars est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre. Par exemple, chars.index('a').
Pour la valeur de chars, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que count.keys() ou f.keys().
5) Coder la méthode de Métropolis-Hastings vu en TD sous la forme d'une fonction appeléeMCMC(m, mu, A, f, N) en utilisant les fonctions swapF et logLikelihood.
Le paramètre m est le message codé.
Les paramètres mu, A représentent le modèle de bigrammes.
L'argument f est la fonction de décodage initiale pour démarrer l'algorithme de Métropolis-Hastings.
Enfin, l'argument N est le nombre maximum d'itérations de l'algorithme.
4) Ecrire une fonction logLikelihood(m, mu, A, chars) qui calcule la log-vraisemblance d'un message m à partir du modèle bigramme (mu, A).
Comme mu et A sont des matrices, il faut assurer la correspondance entre une lettre et un indice (de mu ou de A).
Le paramètre chars est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre. Par exemple, chars.index('a').
Pour la valeur de chars, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que count.keys() ou f.keys().
5) Coder la méthode de Métropolis-Hastings vu en TD sous la forme d'une fonction appelée
Le paramètre m est le message codé.
Les paramètres mu, A représentent le modèle de bigrammes.
L'argument f est la fonction de décodage initiale pour démarrer l'algorithme de Métropolis-Hastings.
Enfin, l'argument N est le nombre maximum d'itérations de l'algorithme.
to:
Ecrire une fonction {$swapF(f)$} qui prend en argument une fonction de décodage et qui retourne une nouvelle fonction de décodage construite à partir de f où deux lettres choisies au hasard ont été échangées.
4) Ecrire une fonction {$logLikelihood(m, mu, A, chars)$} qui calcule la log-vraisemblance d'un message m à partir du modèle bigramme {$(mu, A)$}.
Comme mu et A sont des matrices, il faut assurer la correspondance entre une lettre et un indice (de {$mu$} ou de {$A$}).
Le paramètre chars est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre. Par exemple, {$chars.index('a')$}.
Pour la valeur de chars, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que {$count.keys()$} ou {$f.keys()$}.
5) Coder la méthode de Métropolis-Hastings vu en TD sous la forme d'une fonction appelée {$MetropolisHastings(m, mu, A, f, N)$} en utilisant les fonctions {$swapF$} et {$logLikelihood$}.
Le paramètre {$m$} est le message codé.
Les paramètres {$mu$}, A représentent le modèle de bigrammes.
L'argument {$f$} est la fonction de décodage initiale pour démarrer l'algorithme de Métropolis-Hastings.
Enfin, l'argument {$N$} est le nombre maximum d'itérations de l'algorithme.
4) Ecrire une fonction {$logLikelihood(m, mu, A, chars)$} qui calcule la log-vraisemblance d'un message m à partir du modèle bigramme {$(mu, A)$}.
Comme mu et A sont des matrices, il faut assurer la correspondance entre une lettre et un indice (de {$mu$} ou de {$A$}).
Le paramètre chars est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre. Par exemple, {$chars.index('a')$}.
Pour la valeur de chars, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que {$count.keys()$} ou {$f.keys()$}.
5) Coder la méthode de Métropolis-Hastings vu en TD sous la forme d'une fonction appelée {$MetropolisHastings(m, mu, A, f, N)$} en utilisant les fonctions {$swapF$} et {$logLikelihood$}.
Le paramètre {$m$} est le message codé.
Les paramètres {$mu$}, A représentent le modèle de bigrammes.
L'argument {$f$} est la fonction de décodage initiale pour démarrer l'algorithme de Métropolis-Hastings.
Enfin, l'argument {$N$} est le nombre maximum d'itérations de l'algorithme.
Changed lines 66-67 from:
- tirage de f' grâce à swapF à partir de f
- calcul de la log-vraisemblance du message décodée grâce à f'
to:
- tirage de {$f'$} grâce à {$swapF$} à partir de {$f$}
- calcul de la log-vraisemblance du message décodée grâce à {$f'$}
- calcul de la log-vraisemblance du message décodée grâce à {$f'$}
Changed line 34 from:
1) Télécharger le fichier countWar.pkl qui contient le modèle de bigrammes appris à partir du roman "War and Peace" de Tolstoï.
to:
1) Télécharger le fichier ''countWar.pkl'' qui contient le modèle de bigrammes appris à partir du roman "War and Peace" de Tolstoï.
Changed line 39 from:
Le modèle bigramme est décrit par les variables mu et A.
to:
Le modèle bigramme est décrit par les variables $mu$ et $A$.
Changed lines 13-16 from:
Ecrire une fonction tirage prenant en paramètre {$m$} et retournant un point tiré aléatoirement selon la loi uniforme dans le carré {$ [-m, m]^2 $}
En utilisant la fonction précédente, écrire une fonction monteCarlo prenant en paramètre {$N$}, le nombre de tirages et retournant une estimation de {$\pi$} par Monte Carlo.
En utilisant la fonction précédente, écrire une fonction monteCarlo prenant en paramètre {$N$}, le nombre de tirages et retournant une estimation de {$\pi$} par Monte Carlo.
to:
Ecrire une fonction ''tirage'' prenant en paramètre {$m$} et retournant un point tiré aléatoirement selon la loi uniforme dans le carré {$ [-m, m]^2 $}
En utilisant la fonction précédente, écrire une fonction ''monteCarlo'' prenant en paramètre {$N$}, le nombre de tirages et retournant une estimation de {$\pi$} par Monte Carlo.
En utilisant la fonction précédente, écrire une fonction ''monteCarlo'' prenant en paramètre {$N$}, le nombre de tirages et retournant une estimation de {$\pi$} par Monte Carlo.
Changed line 23 from:
Coder la méthode MCMC vu en TD en utilisant la fonction tirage.
to:
Coder la méthode ''MCMC'' vu en TD en utilisant la fonction tirage.
Changed line 17 from:
Vous pourrez tracer le carré { $[-1, 1]^2$ }, le cercle de centre l'origine et de rayon 1, et les points tirés avec une couleur différente selon qu'ils sont dans le cercle ou non.
to:
Vous pourrez tracer le carré {$ [-1, 1]^2 $}, le cercle de centre l'origine et de rayon 1, et les points tirés avec une couleur différente selon qu'ils sont dans le cercle ou non.
Changed line 17 from:
Vous pourrez tracer le carré {$[-1, 1]^2$}, le cercle de centre l'origine et de rayon 1, et les points tirés avec une couleur différente selon qu'ils sont dans le cercle ou non.
to:
Vous pourrez tracer le carré { $[-1, 1]^2$ }, le cercle de centre l'origine et de rayon 1, et les points tirés avec une couleur différente selon qu'ils sont dans le cercle ou non.
Changed line 13 from:
Ecrire une fonction tirage prenant en paramètre {$m$} et retournant un point tiré aléatoirement selon la loi uniforme dans le carré {$\[-m, m\]^2$}
to:
Ecrire une fonction tirage prenant en paramètre {$m$} et retournant un point tiré aléatoirement selon la loi uniforme dans le carré {$ [-m, m]^2 $}
Changed line 13 from:
Ecrire une fonction tirage prenant en paramètre {$m$} et retournant un point tiré aléatoirement selon la loi uniforme dans le carré {$[-m, m]^2$}
to:
Ecrire une fonction tirage prenant en paramètre {$m$} et retournant un point tiré aléatoirement selon la loi uniforme dans le carré {$\[-m, m\]^2$}
Added lines 1-79:
%define=subsection color=purple%
%define=section color=blue%
! TME 9: Monte-Carlo par chaînes de Markov (MCMC)
Nous allons tester expérimentalement ce qui a été vu en TD.
!!%section% Estimation de {$\pi$} par Monte Carlo
Ecrire une fonction tirage prenant en paramètre {$m$} et retournant un point tiré aléatoirement selon la loi uniforme dans le carré {$[-m, m]^2$}
En utilisant la fonction précédente, écrire une fonction monteCarlo prenant en paramètre {$N$}, le nombre de tirages et retournant une estimation de {$\pi$} par Monte Carlo.
Vous pourrez tracer le carré {$[-1, 1]^2$}, le cercle de centre l'origine et de rayon 1, et les points tirés avec une couleur différente selon qu'ils sont dans le cercle ou non.
!!%section% Estimation de {$\pi$} par MCMC
Coder la méthode MCMC vu en TD en utilisant la fonction tirage.
Votre méthode prendra en paramètre la valeur {$m$}, le "burnin time" (c'est-à-dire le nombre d'itérations initiales que l'on saute) et le "mixing time" (c'est-à-dire le nombre d'itérations entre deux échantillons).
En calculant l'erreur d'estimation, c'est-à-dire, la valeur absolue de la différence entre l'estimation et {$\pi$} (à moyenner bien sûr sur plusieurs essais), vous pourrez chercher les meilleurs valeurs des paramètres.
!!%section% Décodage par la méthode de Metropolis-Hastings
Nous travaillons sur des textes en anglais pour éviter les problèmes avec les accents.
1) Télécharger 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.
2) Exécuter le code suivant pour charger en python le modèle de bigrammes.
La variable count est un dictionnaire, pour chaque lettre du roman "War and Peace", il fournit son nombre d'occurrence dans le roman.
Le modèle bigramme est décrit par les variables mu et A.
La variable mu est un vecteur qui contient la distribution de probabilité initiale sur les lettres.
La variable A est une matrice qui donne les probabilités d'une lettre étant donné une autre lettre.
(:source lang=python:)
import codecs
import numpy as np
import numpy.random as npr
import copy
import pickle as pkl
(count, mu, A) = pkl.load(file("countWar.pkl", "rb"))
(:sourceend:)
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).
Ecrire une fonction swapF(f) qui prend en argument une fonction de décodage et qui retourne une nouvelle fonction de décodage construite à partir de f où deux lettres choisies au hasard ont été échangées.
4) Ecrire une fonction logLikelihood(m, mu, A, chars) qui calcule la log-vraisemblance d'un message m à partir du modèle bigramme (mu, A).
Comme mu et A sont des matrices, il faut assurer la correspondance entre une lettre et un indice (de mu ou de A).
Le paramètre chars est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre. Par exemple, chars.index('a').
Pour la valeur de chars, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que count.keys() ou f.keys().
5) Coder la méthode de Métropolis-Hastings vu en TD sous la forme d'une fonction appelée MCMC(m, mu, A, f, N) en utilisant les fonctions swapF et logLikelihood.
Le paramètre m est le message codé.
Les paramètres mu, A représentent le modèle de bigrammes.
L'argument f est la fonction de décodage initiale pour démarrer l'algorithme de Métropolis-Hastings.
Enfin, l'argument N est le nombre maximum d'itérations de l'algorithme.
La méthode est une simple boucle où on fait les étapes suivantes :
- tirage de f' grâce à swapF à partir de f
- calcul de la log-vraisemblance du message décodée grâce à f'
- tirage pour accepter ou non la transition selon le rapport des vraisemblances
- si la transition est acceptée, conserver le message décodé avec la plus haute vraisemblance.
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.
6) Pour accélérer les calculs, nous allons partir d'une fonction de décodage prenant les fréquences d'occurence des lettres (c'est-à-dire la lettre la plus fréquente du message encodé 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ée sera décodée vers la deuxième lettre la plus fréquente observée du roman; et ainsi de suite...)
Vous pouvez utiliser la fonction suivante pour construire une telle fonction de décodage.
(:source lang=python:)
fonction...
(:sourceend:)
7)
%define=section color=blue%
! TME 9: Monte-Carlo par chaînes de Markov (MCMC)
Nous allons tester expérimentalement ce qui a été vu en TD.
!!%section% Estimation de {$\pi$} par Monte Carlo
Ecrire une fonction tirage prenant en paramètre {$m$} et retournant un point tiré aléatoirement selon la loi uniforme dans le carré {$[-m, m]^2$}
En utilisant la fonction précédente, écrire une fonction monteCarlo prenant en paramètre {$N$}, le nombre de tirages et retournant une estimation de {$\pi$} par Monte Carlo.
Vous pourrez tracer le carré {$[-1, 1]^2$}, le cercle de centre l'origine et de rayon 1, et les points tirés avec une couleur différente selon qu'ils sont dans le cercle ou non.
!!%section% Estimation de {$\pi$} par MCMC
Coder la méthode MCMC vu en TD en utilisant la fonction tirage.
Votre méthode prendra en paramètre la valeur {$m$}, le "burnin time" (c'est-à-dire le nombre d'itérations initiales que l'on saute) et le "mixing time" (c'est-à-dire le nombre d'itérations entre deux échantillons).
En calculant l'erreur d'estimation, c'est-à-dire, la valeur absolue de la différence entre l'estimation et {$\pi$} (à moyenner bien sûr sur plusieurs essais), vous pourrez chercher les meilleurs valeurs des paramètres.
!!%section% Décodage par la méthode de Metropolis-Hastings
Nous travaillons sur des textes en anglais pour éviter les problèmes avec les accents.
1) Télécharger 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.
2) Exécuter le code suivant pour charger en python le modèle de bigrammes.
La variable count est un dictionnaire, pour chaque lettre du roman "War and Peace", il fournit son nombre d'occurrence dans le roman.
Le modèle bigramme est décrit par les variables mu et A.
La variable mu est un vecteur qui contient la distribution de probabilité initiale sur les lettres.
La variable A est une matrice qui donne les probabilités d'une lettre étant donné une autre lettre.
(:source lang=python:)
import codecs
import numpy as np
import numpy.random as npr
import copy
import pickle as pkl
(count, mu, A) = pkl.load(file("countWar.pkl", "rb"))
(:sourceend:)
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).
Ecrire une fonction swapF(f) qui prend en argument une fonction de décodage et qui retourne une nouvelle fonction de décodage construite à partir de f où deux lettres choisies au hasard ont été échangées.
4) Ecrire une fonction logLikelihood(m, mu, A, chars) qui calcule la log-vraisemblance d'un message m à partir du modèle bigramme (mu, A).
Comme mu et A sont des matrices, il faut assurer la correspondance entre une lettre et un indice (de mu ou de A).
Le paramètre chars est une liste de caractères qui permet d'obtenir l'indice correspondant à une lettre. Par exemple, chars.index('a').
Pour la valeur de chars, vous pourrez utiliser les clés d'un dictionnaire contenant toutes les lettres, telles que count.keys() ou f.keys().
5) Coder la méthode de Métropolis-Hastings vu en TD sous la forme d'une fonction appelée MCMC(m, mu, A, f, N) en utilisant les fonctions swapF et logLikelihood.
Le paramètre m est le message codé.
Les paramètres mu, A représentent le modèle de bigrammes.
L'argument f est la fonction de décodage initiale pour démarrer l'algorithme de Métropolis-Hastings.
Enfin, l'argument N est le nombre maximum d'itérations de l'algorithme.
La méthode est une simple boucle où on fait les étapes suivantes :
- tirage de f' grâce à swapF à partir de f
- calcul de la log-vraisemblance du message décodée grâce à f'
- tirage pour accepter ou non la transition selon le rapport des vraisemblances
- si la transition est acceptée, conserver le message décodé avec la plus haute vraisemblance.
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.
6) Pour accélérer les calculs, nous allons partir d'une fonction de décodage prenant les fréquences d'occurence des lettres (c'est-à-dire la lettre la plus fréquente du message encodé 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ée sera décodée vers la deuxième lettre la plus fréquente observée du roman; et ainsi de suite...)
Vous pouvez utiliser la fonction suivante pour construire une telle fonction de décodage.
(:source lang=python:)
fonction...
(:sourceend:)
7)