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.349077Si 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.837914Le 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.284649Cette 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