Hidden Markov Model - Exemples d'utilisation

Un ami lointain

Cet exemple est tiré de Wikipédia (anglais), il n'a été modifié que pour la traduction en français.

Supposons que vous ayez un ami vivant loin de vous. Il vous envoie chaque jour un mail dans lequel il vous dit ce qu'il a fait de sa journée. Comme il n'est pas très imaginatif, il n'a que trois activités : soit il se balade, soit il fait du shopping, soit il nettoie son appartement. Le choix de son activité du jour est fait uniquement en fonction du temps qu'il fait : soit il pleut, soit il fait soleil. Pour finir, comme vous le connaissez bien, vous connaissez les probabilités qu'il choississe chacune des trois activités en fonction du temps qu'il fait.

Vous n'avez que l'information sur son activité du jour, mais vous souhaitez savoir le temps qu'il fait chez lui. Pour chaque jour, vous souhaitez savoir s'il pleut ou s'il fait soleil. Pour cela, vous construisez un HMM.

Ce HMM a deux états : Soleil et Pluie.
Il a également trois observations possibles : Shopping, Nettoyage et Balade.

Vous estimez que les probabilités de transition entre Soleil et Pluie sont les suivantes :
    - s'il fait soleil un jour, il y a 60% de chances qu'il fasse soleil le lendemain et 40% qu'il pleuve ;
    - s'il pleut un jour, il y a 70% de chances qu'il pleuve le lendemain et 30% de chance qu'il fasse soleil ;
Pour le choix des activités, c'est à dire les probabilités d'émission, vous estimez, connaissant votre ami, qu'elles sont comme suit :
    - s'il fait soleil, il y a 60% de chances qu'il fasse une balade, 30% qu'il fasse du shopping et 10% qu'il fasse du nettoyage ;
    - s'il pleut, il y a 10% de chances qu'il fasse une balade, 40% qu'il fasse du shopping et 50% qu'il fasse du nettoyage ;
Enfin pour les probabilités de départ, vous pensez qu'il y a un peu plus de chance qu'il pleuve :
    60% Pluie, 40% Soleil.

Cette semaine, votre ami vous a rapporté les activités suivantes :
    nettoyage, shopping, balade, shopping, shopping, balade, nettoyage.
Vous avez votre séquence d'observations, vous écrivez donc le code suivant (en Python 2.7):

#Les états
states = ('Pluie', 'Soleil')

#Les observations possibles
observations = ('balade', 'shopping', 'nettoyage')

#La matrice des transitions entres les états
transition_probability = {
	'Pluie' : {'Pluie': 0.7, 'Soleil': 0.3},
	'Soleil' : {'Pluie': 0.4, 'Soleil': 0.6},
	}

#La matrice des émissions
emission_probability = {
	'Pluie' : {'balade': 0.1, 'shopping': 0.4, 'nettoyage': 0.5},
	'Soleil' : {'balade': 0.6, 'shopping': 0.3, 'nettoyage': 0.1},
	}

#Les probabilités de départs, c'est à dire les proba que chaque état soit celui de départ
start_probability = {'Pluie': 0.6, 'Soleil': 0.4}

#La fonction d'affichage des étapes de l'algorithme de Viterbi
def print_dptable(V):
	print "      ",
	for i in range(len(V)): print "%8d" % i,
	print

	for y in V[0].keys():
		print "%7.7s: " % y,
		for t in range(len(V)):
			print "%.8s" % ("%f" % V[t][y]),
		print


def viterbi(states, obs_seq, start_prob, trans_prob, emit_prob):
	#Initialisation
	V = [{}]
	path = {}
	for state in states:
		V[0][state]=start_prob[state]*emit_prob[state][obs_seq[0]]
		path[state]=[state];

	#Algorithme de Viterbi
	for t in range(1, len(obs_seq)):
		V.append({})
		newpath = {}
		for state in states:
			(p,s) = max([(V[t-1][i]*trans_prob[i][state]*emit_prob[state][obs_seq[t]],i) for i in states])
			V[t][state] = p;
			newpath[state] = path[s] + [state];
		path = newpath

	print_dptable(V)

	#final
	(p,s) = max([(V[len(obs_seq)-1][y], y) for y in states])
	return (p, path[s])

#Appel de l'algorithme de Viterbi avec la séquence d'observations de la semaine
print viterbi(states,  ['nettoyage', 'shopping', 'balade', 'shopping', 'shopping', 'balade', 'nettoyage'], start_probability, transition_probability, emission_probability)
Vous lancez le programme et vous obtenez le résultat :


	     0        1        2        3        4        5        6
 Soleil:  0.040000 0.027000 0.015120 0.002722 0.000490 0.000176 0.000011
  Pluie:  0.300000 0.084000 0.005880 0.002419 0.000677 0.000047 0.000035
(3.5271935999999995e-05, ['Pluie', 'Pluie', 'Soleil', 'Soleil', 'Soleil', 'Soleil', 'Pluie'])
Cela signifie que la séquence d'états la plus probable est "Pluie, Pluie, Soleil, Soleil, Soleil, Soleil, Pluie" et que sa probabilité d'apparition est environ 3,53x10-5. La réponse à la question "Quelle est la séquence d'états la plus probable qui a générée cette séquence d'observations ?" vous a donc permis d'estimer le temps qu'il fait chez votre ami en ne connaissant que son emploi du temps.

Entrainement linguistique

Cet exemple m'a été inspiré par une de mes lectures autour des HMM. A l'origine, l'idée était de définir un HMM "vierge" (c'est à dire, presque équiprobable) à 2 états et 27 observations. Les 27 observations étaient en fait les 26 lettres de l'alphabet ainsi que l'"espace". Le but étant de répondre à la question "Maximiser la probabilité d'une séquence d'observations" en utilisant une certaine séquence.

La séquence en question était un texte en anglais dont tous les caractères autre que les lettres et espaces avaient été retirés. De plus, tout était écrit en minuscule. Cela donnait bien une séquence ne contenant que nos 27 observations. En répondant à la question grâce à l'algorithme de Baum-Welch, on s'appercevait que le HMM séparait les voyelles et les consonnes dans chacun des 2 états. Cela montre qu'il y a bien une signification statistique à cette séparation que nous connaissons tous depuis que nous savons lire.

Pour l'exemple qui va être présenté ici, le principe est à peu près le même. Les sources de code (encore une fois en Python 2.7) sont à votre disposition, mais étant donnée leur longueur, je ne les afficherai pas directement dans cette page.

Le but de l'exemple est d'entrainer un HMM à deux états sur un texte en français puis d'observer ce qui se passe sur un texte en anglais. Bien entendu, les deux textes ont été préparés à l'avance pour ne contenir que les 26 lettres de l'alphabet en minuscules et des espaces. Le texte en français est à l'origine "Horace", de George Sand, tandis que le texte en anglais est un agglomérat d'extraits de la section P du Brown Corpus : texte français (préparé), texte anglais (préparé).

Le HMM a été entraîné sur les 50 000 premiers caractères du texte français, c'est à dire que nous lui avons demandé de "Maximiser la probabilité d'apparition de cette séquence". Après plus de 600 itérations, le résultat a été le suivant :

Nombre d'état: 2, Nombre d'observations: 27
Probabilité de départ
       1        2
    1.000000 0.000000

Probabilité de transitions
       1        2
  1 0.203875 0.796125
  2 0.655800 0.344200

Probabilité d'émissions (transposée)
	   1        2
      a 0.016430 0.107239
      b 0.013061 0.000879
      c 0.056308 0.000000
      d 0.066501 0.000000
      e 0.000000 0.262201
      f 0.018004 0.000000
      g 0.016239 0.000000
      h 0.014209 0.000000
      i 0.011219 0.099780
      j 0.015577 0.000000
      k 0.000000 0.000073
      l 0.086889 0.000000
      m 0.053704 0.000000
      n 0.127663 0.000000
      o 0.000000 0.081718
      p 0.047621 0.001531
      q 0.024579 0.000000
      r 0.111468 0.000000
      s 0.145314 0.000000
      t 0.123250 0.000000
      u 0.003183 0.097260
      v 0.032434 0.000000
      w 0.000000 0.000000
      x 0.007458 0.000000
      y 0.004652 0.000241
      z 0.004236 0.000000
	0.000000 0.349077
Si vous souhaitez reproduire l'expérience et qu'attendre 2h devant votre écran ne vous dit rien, voici la sauvegarde de ce HMM.
Nous remarquons qu'il y a une nette tendance à ce que les voyelles et les consonnes soient séparées dans les deux états. Le "Y" semble être plus une consonne qu'une voyelle et le "K" plus une voyelle qu'une consonne... statistiquement bien sûr. Pour le "K", le résultat n'est pas très significatif, la séquence d'entraînement n'en contenant que 2 (sur 50 000 au total). Nous remarquons également que l'espace est statistiquement une voyelle.

Une fois le HMM entraîné et sauvegardé, nous sommes prêts à faire l'expérience de reconnaissance, c'est à dire à demander au HMM : "Quelle est la probabilité d'apparition" de telle ou telle séquence ?
Sur chacun des textes, français et anglais, nous lui soumettons donc 6 séquences de 50 000 caractères :
    - du 0 au 49999 inclus ;
    - du 50000 au 99999 inclus ;
    - du 100000 au 149999 inclus ;
    - du 150000 au 199999 inclus ;
    - du 200000 au 249999 inclus ;
    - du 250000 au 299999 inclus ;
Il est important de soumettre des séquences de même longeur pour que les résultats soient comparables.

Les résultats du texte en français sont les suivants :

Log[P(Obs[0:50000])] = -131655.486217
Log[P(Obs[50000:100000])] = -131937.168372
Log[P(Obs[100000:150000])] = -131979.453439
Log[P(Obs[150000:200000])] = -131786.942275
Log[P(Obs[200000:250000])] = -131956.523973
Log[P(Obs[250000:300000])] = -131730.837914
Le meilleur résultat est celui de la première séquence, c'est logique puisque le HMM a été entraîné dessus. Les probabilités des autres séquences sont légèrement plus faibles mais restent dans le même ordre de grandeur.

Les résultats du texte en anglais sont les suivants :

Log[P(Obs[0:50000])] = -176589.462375
Log[P(Obs[50000:100000])] = -180926.020071
Log[P(Obs[100000:150000])] = -176317.903231
Log[P(Obs[150000:200000])] = -179248.463063
Log[P(Obs[200000:250000])] = -178826.503654
Log[P(Obs[250000:300000])] = -175592.284649
Cette fois, ce ne sont plus du tout les mêmes ordres de grandeur. En effet, la distribution statistique des lettres en français n'est pas du tout la même qu'en anglais. Par exemple, il y a beaucoup de 'w' en anglais, pas en français. A l'inverse, il y a beaucoup de 'e' en français et pas spécialement en anglais. Notre HMM, après entraînement, est donc capable de reconnaître si le texte qu'on lui soumet est en français ou non.

Si vous souhaitez faire l'expérience vous-même, le programme Python a deux modes de fonctionnement :
    - si vous l'appelez sans paramètre, il lira son entrée standard, extraiera les 50 000 premiers caractères et s'entraînera dessus (et sauvegardera le HMM à la fin de l'algorithme) ;
    - si vous l'appelez avec une sauvegarde en paramètre, il chargera le HMM sauvegardé, lira son entrée standard et affichera les probabilités d'apparition des 6 premières séquences de 50 000 caractères.
Si vous avez téléchargé les 4 fichiers de cette page, vous pouvez lancer :

$./hmm.py < texte-francais-prep.txt
			Pour entraîner le HMM sur le texte français.
$./hmm.py save_hmm_training_french.sav < texte-francais-prep.txt
			Pour obtenir les probabilités d'apparition des séquences du texte français.
$./hmm.py save_hmm_training_french.sav < texte-anglais-prep.txt
			Pour obtenir les probabilités d'apparition des séquences du texte anglais.

Aller à la Conclusion