Premiers pas avec les modèles Markov cachés à l’aide de Perl

Un modèle de Markov (nommé d’après le mathématicien Andrey Markov) est utilisé pour la prévision dans les systèmes de changement aléatoire. L’idée de Markov est que de bonnes prédictions dans ce contexte ne peuvent être faites qu’à partir de l’occurrence la plus récente d’un événement, en ignorant toutes les occurrences antérieures à l’événement en cours. L’approche pourrait être décrite comme une prédiction sans mémoire ou sans historique.
Le premier exemple de Markov (en 1913) a prédit des occurrences de voyelle dans le poème de Pouchkine « Eugeny Onegin ». Le défi aujourd’hui est de trouver un domaine de recherche dans lequel les modèles de Markov ne jouent aucun rôle. Ces modèles sont utilisés pour étudier la thermodynamique et la mécanique statistique; bioinformatique, activité enzymatique et dynamique des populations; l’irradiance solaire et l’énergie éolienne; évolution des prix; reconnaissance et génération de la parole; compression de données et reconnaissance de formes; apprentissage par renforcement et reconnaissance des gestes. La liste se rallonge de plus en plus.
Cet article couvre le modèle de Markov caché (HMM), un raffinement de l’original. Une introduction à HMM et à l’algorithme de Viterbi, qui convient bien aux HMM, configure un exemple de code complet en Perl.

1. Randonnées aléatoires avec la propriété Markov

Imaginez un renard qui se nourrit et se trouve actuellement à l’emplacement C (par exemple, près d’un buisson à côté d’un ruisseau). Les emplacements précédents sur le chemin de recherche du renard sont P1, P2, P3, etc. Le problème est de savoir comment prédire le prochain emplacement du renard.
Une approche consisterait à utiliser l’intégralité de l’historique de recherche P1, P2,…, C pour prédire l’emplacement suivant. Par exemple, les emplacements déjà visités dans la recherche du renard peuvent avoir une très faible probabilité d’être le prochain emplacement au motif que le renard est assez intelligent pour ne pas répéter les emplacements de recherche échoués. En revanche, les emplacements à proximité mais non visités (par exemple, un affleurement à travers le ruisseau) pourraient avoir une probabilité élevée.
Une approche plus simple consiste à supposer que l’emplacement suivant du renard N peut être prédit aussi précisément à partir de l’emplacement actuel C seul que de tout l’historique de recherche P1, P2,…, C. Si tel est le cas, la recherche du renard peut être modélisée comme un processus avec la propriété Markov. Dans cet exemple, la propriété signifie que la distribution de probabilité pour le prochain emplacement de recherche du renard dépend uniquement de l’emplacement actuel du renard – et non des emplacements précédents. Un processus de Markov peut ainsi être décrit comme une marche aléatoire qui présente la propriété Markov.
La propriété Markov peut être exprimée succinctement en utilisant la notation de probabilité conditionnelle: P (A | B) est la probabilité de A étant donné B. Dans l’exemple fox, la propriété Markov prend en charge une égalité: P (N|P1,P2,…,C) = P (N|C) où C et N sont respectivement l’emplacement actuel et l’emplacement suivant.

2. HMM et l’algorithme de Viterbi

Dans l’exemple du renard, chaque état d’intérêt dans le processus (recherche de nourriture à un endroit particulier) est, par hypothèse, visible pour un observateur: aucun état n’est caché. Dans le raffinement HMM, les états sont masqués, mais chaque état a un ou plusieurs jetons de sortie associés (ou observations), qui ne sont pas masqués. Le but est de déduire la séquence d’états des observations. Un exemple classique est le problème de l’urne.
Imaginez une pièce cachée qui contient plusieurs urnes, chacune avec des boules étiquetées B1, B2, etc. On ne sait pas si chaque urne contient les mêmes boules. Un robot, en secret, sélectionne une urne et en prend une balle au hasard, en plaçant une copie de l’étiquette de la balle sur un tapis roulant que l’observateur voit. L’observateur connaît ainsi la séquence des boules cueillies (par exemple, B9, B4, B13,…) mais pas l’urne dans laquelle une balle donnée est cueillie. Après avoir ramassé une balle dans une urne et copié l’étiquette, le robot renvoie la balle dans son urne hôte avant le prochain choix.
Une urne ramassée appartient à l’état caché dans ce processus, et les copies des étiquettes à billes placées sur la bande transporteuse sont les jetons de sortie. Le robot a une recette (quoique secrète) pour choisir chaque urne; par conséquent, cette cueillette d’urne peut être modélisée comme un processus de Markov avec un état caché – un HMM.
L’algorithme de Viterbi, de la fin des années 1960, peut être utilisé pour déduire la séquence probable des états cachés (dans cet exemple, la séquence des pics d’urnes) à partir des événements observés (dans ce cas, les étiquettes sur la bande transporteuse). La séquence déduite est appelée le chemin de Viterbi en l’honneur de Viterbi.
À titre d’exemple, considérons cette tranche des jetons de sortie:

B9,B4,B13,B27,B6,B13,B29 ## séquence de 7 observations

Le chemin sous-jacent de Viterbi peut être:

L’algorithme de Viterbi déduit les transitions d’état cachées du robot (pics d’urnes) à partir des étiquettes observées sur la bande transporteuse. L’inférence est, bien sûr, de nature statistique. Il y a des suppositions, mais l’algorithme de Viterbi devrait en faire la saveur instruite.

3. L’algorithme de Viterbi en détail

L’algorithme Viterbi utilise six entrées pour générer le chemin Viterbi:

• le espace d’observation se compose des jetons de sortie ou des observations possibles (par exemple, B1, B2, B3, etc.).
• le observations séquencées est l’ordre dans lequel les jetons sont observés (par exemple, B9, B4, B13, etc.).
• le territoire de l’État se compose des états masqués possibles (par exemple, UrnA, UrnB, etc.).
• le probabilités initiales sont les probabilités qu’une urne particulière représente l’état de départ dans le processus de sélection du robot.
• le probabilités de transition sont les probabilités d’une transition d’une urne à une autre, y compris vers elle-même.
• le probabilités d’émission sont les probabilités qu’une balle observée provienne d’une urne spécifique.

La sortie est:

• La séquence d’état caché déduite (dans cet exemple, la séquence d’urne sélectionnée), qui est le chemin de Viterbi.

Ces contributions peuvent être tirées d’exemples plutôt que stipulées arbitrairement. Par conséquent, il existe deux sections dans l’exemple de code court qui suit. La première section simule l’apprentissage automatique à partir d’exemples, et la deuxième section utilise les résultats de cet apprentissage pour déduire un HMM qui sous-tend la séquence d’étiquettes de balle observées.

4. Le programme hmm

Le programme hmm ci-dessous est disponible sur mon site Web. Les systèmes de type Unix sont livrés avec Perl installé, mais ce programme nécessite le Algorithme :: Viterbi package qui est disponible sur CPAN et d’autres référentiels Perl. Le package optionnel Données :: Dumper peut être utilisé pour afficher les entrées Viterbi dans leur intégralité; pour ce faire, décommentez la dernière ligne du programme.

Exemple 1. Le programme hmm

Le programme hmm utilise cinq urnes (UrnA à UrnE), mais avec des boules différentes dans chacune des urnes:

Les boules sont stockées dans une carte avec l’urne comme clé et une liste de boules contenues comme valeur de cette clé.
La section d’apprentissage du programme hmm utilise des données de test générées aléatoirement, qui se composent de 64 000 paires de balles-urnes comme celle-ci:

B5, UrnD ## preuve

Cette paire confirme que UrnD contient une balle étiquetée B5, mais d’autres paires confirment qu’une balle B5 pourrait provenir d’une autre urne:

B5, UrnA ## plus de preuves

Les deux exemples ensemble indiquent qu’une balle B5 pourrait provenir d’UrnA ou d’UrnD. Les paires d’apprentissage ne fournissent aucune information sur le robot, sauf qu’il peut choisir une balle particulière dans une urne particulière.
Les données de test de la section d’apprentissage sont stockées dans une liste, qui est transmise au train méthode d’un Algorithme :: Viterbi exemple:

Les résultats de cet appel à train sont clarifiés ensuite.

5. Résultats de la formation

le train détecte cinq états (urnes) possibles dans le HMM sous-jacent, car chaque urne se produit au moins une fois dans les données de test générées aléatoirement. Voici les états dans l’ordre détecté:

États => [[UrnA, UrnD, Urne, UrnB, UrnC]

Rappelons que les trois probabilités requises pour l’algorithme de Viterbi sont les probabilités initiales (pour l’urne de début); les probabilités de transition (passage du robot de l’urne actuelle à l’urne suivante); et les probabilités d’émission (la probabilité qu’une étiquette observée identifie une balle dans une urne particulière). La formation donne ces résultats pour les probabilités initiales:

Les valeurs, qui totalisent 1, donnent à chacune des cinq urnes environ une chance sur cinq d’être le choix initial du robot. UrnD a un léger avantage sur UrnB, mais les résultats sont fondamentalement un coup sec.
Voici les probabilités de transition dérivées des tests, avec UrnC comme exemple:

Avec UrnC comme état actuel, la transition vers n’importe quelle urne (y compris UrnC à nouveau) est probable à environ 20%.
Les probabilités d’émission sont intéressantes en ce que toutes les urnes n’ont pas toutes les balles. Par exemple, B6 se produit uniquement dans UrnC. Néanmoins, l’algorithme de Viterbi ne peut pas exclure, sur la base des exemples d’entraînement, qu’une autre urne puisse également contenir cette balle. Le résultat de l’entraînement ne donne qu’une probabilité prudente de 20% qu’une étiquette B6 émise provienne d’une balle dans UrnC:

B6 => {UrnC => 0.201110329189147}

En revanche, un B7 se produit dans quatre des urnes, et les données de formation incluent de telles occurrences de sorte qu’il existe des probabilités pour un B7 provenant de chacune des quatre urnes:

D’après les données d’entraînement, UrnB est la source la plus probable d’une balle B7, tandis que UrnA est la source la moins probable de cette balle. (UrnA et UrnB contiennent tous deux une balle B7.)
En résumé, les données de formation étayent des inférences statistiques sur trois points clés:

• L’urne que le robot est susceptible de ramasser initialement. Dans ce cas, chaque urne a à peu près les mêmes chances d’être cueillie.
• Étant donné une urne choisie, l’urne que le robot est susceptible de prendre ensuite, qui pourrait être la même urne à nouveau. Les données de formation suggèrent que toutes les transitions urne à urne sont également probables.
• L’urne dans laquelle une balle particulière (par exemple, B7) a été choisie. Ici, les probabilités diffèrent considérablement car toutes les urnes ne contiennent pas les mêmes balles.

L’algorithme de Viterbi utilise les trois probabilités d’entrée, et surtout la dernière sur les émissions, pour essayer de déterminer – à partir d’une séquence d’étiquettes observées – la séquence d’urnes dont les boules avec les étiquettes observées ont été prélevées.

6. Les observations

La dernière entrée de l’algorithme de Viterbi consiste en des observations – les étiquettes visibles sur la bande transporteuse. Le programme hmm génère également ces valeurs de manière aléatoire:

Avec les observations en main, la dernière étape consiste à les transmettre comme argument au forward_viterbi , qui déduit le HMM sous-jacent et le renvoie comme chemin de Viterbi:

mon $ v_path = ($ viterbi->forward_viterbi( @tokens))[[1]; ## Chemin Viterbi

Le programme génère ensuite le résultat sous la forme d’une séquence de transitions d’état:

UrnB->Urne->Urne->UrnB->UrnC-> ...->UrnB->Urne->UrnB->UrnA

Sur cet exemple, seul UrnD n’apparaît pas dans le chemin Viterbi. Chaque balle dans UrnD se produit dans au moins une autre urne, et les probabilités de transition ne favorisent pas UrnD comme cible. L’algorithme peut ainsi présenter une séquence d’état plausible qui exclut UrnD du HMM.
le forward_viterbi La méthode renvoie également deux probabilités, qui représentent les niveaux de confiance dans le chemin de Viterbi déduit. Par souci de simplicité, seul le chemin Viterbi est affiché ici.

7. Diviser pour mieux régner contre la programmation dynamique

Le programme hmm est rapide, ce qui pose la question du fonctionnement de l’algorithme de Viterbi. L’algorithme construit un treillis, qui est un graphe dont les nœuds sont en tranches verticales: les tranches supérieures représentent les temps antérieurs et les tranches inférieures représentent les temps ultérieurs. La figure 1 est un exemple général de Wikipédia, avec le chemin de gauche à droite le plus court indiqué en rouge:

Figure 1. Un treillis

La
L’algorithme de Viterbi, commençant à un nœud dans la tranche supérieure, calcule le chemin le plus court à travers le treillis. Il s’agit du chemin de Viterbi, dont les nœuds représentent les états HMM déduits des observations. L’algorithme utilise une technique de programmation dynamique classique pour plus d’efficacité. Un exemple plus simple (et probablement plus familier) clarifie cette technique, mettant en évidence la mémorisation si facile en Perl.
Envisager une approche diviser pour mieux calculer les nombres de Fibonacci, en utilisant une méthode récursive mensonge fonctionner comme la mise en œuvre:

Pour calculer une valeur telle que fib (40), la fonction divise le problème en sous-problèmes de fib (39) et fib (38). Les divisions continuent jusqu’à ce qu’un sous-problème soit suffisamment petit pour être résolu directement; dans ce cas, le calcul de la valeur de fib (0) ou fib (1).
La valeur de fib (40) est 102 334 155, mais le calcul récursif nécessite 331 160 281 appels au mensonge , qui souligne la complexité exponentielle dans le temps de cette conception diviser pour mieux régner. La difficulté est que trop de valeurs sont recalculé encore et encore à cause des appels récursifs avec n-1 et n-2 comme arguments. Par exemple, fib (40) appels fib (39) et fib (38); mais fib (39) appelle à nouveau fib (38). Chacun des deux derniers appels se traduit par un appel à fib (37), etc.
Un changement de conception est nécessaire. le mensonge La fonction telle qu’elle est écrite peut être mémorisée, ce qui change la conception de la division et de la conquête à la programmation dynamique. Les deux conceptions décomposent un problème en sous-problèmes plus gérables jusqu’à ce qu’un sous-problème puisse être résolu directement. Les deux approches diffèrent en ce que la programmation dynamique met en cache des solutions de sous-problème afin que celles-ci puissent être réutilisées au besoin. En bref, la mise en cache remplace le recalcul. Le résultat peut considérablement améliorer l’efficacité.
Une version mémorisée de mensonge est facile à obtenir en Perl, ne nécessitant aucune modification du code source d’origine:

Avec la version mémorisée, fib (40) nécessite seulement 41 appels pour calculer la valeur. Sous le capot, le mémoriser fournit, comme argument supplémentaire à la mensonge , une table de hachage qui stocke les valeurs de Fibonacci déjà calculées; par conséquent, chaque valeur de Fibonacci requise est calculée exactement une fois. La complexité temporelle exponentielle de la version diviser pour régner est réduite à une complexité temporelle linéaire.
L’algorithme de Viterbi utilise la même approche de mise en cache pour calculer le chemin le plus court à travers le treillis, un chemin qui représente le HMM. Le programme hmm est efficace car l’algorithme de Viterbi l’est.