Cours

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]))
to:
cles = np.array(list(set(secret2))) # tous les caracteres de secret2
rankSecret = np.argsort(-np.array([secret2.count(c) for c in cles]))
Added lines 114-115:

Lien : [[(Attach:)fichierHash.pkl]]
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:
# 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()))))
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:
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 () )

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))])

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:
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).

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 () )
to:
logLikelihood( "abcd", 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:
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''':
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
.
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) 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 :
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( "abcd", mu, A, count.keys () )
logLikelihood
( "dcba", mu, A, count.keys () )
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:)

Deleted line 231:
Added line 69:
# si vos fichiers sont dans un repertoire "ressources"
Changed lines 69-70 from:
(count, mu, A) = pkl.load(file("countWar.pkl", "rb"))
secret
= (open("secret.txt", "r")).read()[0:-1] # -1 pour supprimer le saut de ligne
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
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

 
Changed lines 138-140 from:

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$}.
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:)
Deleted lines 174-179:
def identityF(keys):
  f = {}
  for k in keys:
      f[k] = k
  return f

Changed lines 205-206 from:
fInit = identityF(count.keys())
fInit = mostFrequentF(mp, count, fInit)
to:
tau_init = mostFrequentF(mp, count, identityTau () )

MetropolisHastings(secret, mu, A
, tau_init, 50000 )
Deleted lines 209-212:
8) Lancer le script suivant pour tester vos fonctions :
(:source lang=python:)
MetropolisHastings(secret, mu, A, fInit, int(5e4))
(:sourceend:)
Changed lines 80-83 from:
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@@.
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@@.
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.
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.
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
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
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()$}.
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).
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.
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.
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$}.
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$}.

Changed lines 49-55 from:
!!%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.


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.

Added line 65:
Changed line 80 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.
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:
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.
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.
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 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.

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.
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:
Coder la méthode {$MCMC$} vu en TD en utilisant la fonction tirage.
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()
to:
import matplotlib.pyplot as plt

plt
.figure()
Changed lines 27-28 from:
pl.plot([-1, -1, 1, 1], [-1, 1, 1, -1], '-')
to:
plt.plot([-1, -1, 1, 1], [-1, 1, 1, -1], '-')
Changed lines 32-34 from:
pl.plot(x, y, 'b')
pl.plot(x, -y, 'b')
to:
plt.plot(x, y, 'b')
plt.plot(x, -y, 'b')
Changed lines 40-42 from:
pl.plot(x[dist <=1], y[dist <=1], "go")
pl.plot(x[dist>1], y[dist>1], "ro")
pl.show()
to:
plt.plot(x[dist <=1], y[dist <=1], "go")
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 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 qui suppose que la fonction {$monteCarlo$} retourne l'estimation de pi et l'ensemble des coordonnées tirées.
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.
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:
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.
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.
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
.
Changed line 78 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)$}.
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:
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$}.
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:
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...)
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:
7) Lancer le script suivant pour tester vos fonctions :
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:
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.

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:)
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 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$}.
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$}.
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.
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.
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:
fonction...
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)
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:
)
Changed lines 36-37 from:

2) Exécuter
le code suivant pour charger en python le modèle de bigrammes.
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. 
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 codecs
import numpy as np
import numpy.random as npr
import copy
Changed lines 66-69 from:
- 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.
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.
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.
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.
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é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.
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.
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'$}
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.
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.
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)