Essayer de mieux comprendre l'algorithme de VITERBI

Question

J'essaye actuellement d'implémenter l'algorithme de viterbi en python, plus précisément la version présentée dans un cours en ligne. En l'état, l'algorithme est présenté de la façon suivante: étant donné une phrase avec K jetons, nous devons générer des K tags.

Nous supposons que balise K-1 = étiquette K-2 = '*', alors pour k allant de 0 à K, nous avons mis la balise pour le jeton comme suit: tag (WORD_k) = arg (p (k-1, tag_k-2, tag_k-1) * e (mot_k, tag_k) * q (tag_k, tag_k-1, tag_k-1))

D'après ce que je comprends c'est simple car les paramètres p sont déjà calculé sur chaque étape (on passe de 1 en avant, et on sait déjà p0), et max pour les params e et q peuvent être calculés par une itération à travers les tags (puisque nous ne pouvons pas trouver 2 tags différents, nous fondamentalement doit trouver l'étiquette T pour laquelle le produit q * e est maximal, et renvoyer cela). Cela économise beaucoup de temps, puisque nous sommes presque au temps linéaire en termes de notation O, au lieu de complexité exponentielle, ce que nous obtiendrions si nous parcourions toutes les combinaisons mot/étiquette possibles. Est-ce que j'obtiens le noyau de l'algorithme correctement ou est-ce que je rate quelque chose?

Merci à l'avance

Answer 1

puisque nous ne pouvons pas venir avec 2 étiquettes différentes, nous avons essentiellement à trouver la balise T pour laquelle le q * produit e est maximale, et le retour que

Ouais, ça sonne à peu près juste. q est la probabilité de trigramme (transition) et e est appelée probabilité d'émission. Comme vous l'avez dit est inchangé entre les différents chemins dans chaque étape, de sorte que le maximum dépend uniquement des deux autres. Chaque séquence d'étiquettes doit commencer par deux astérisques aux positions -2 et -1. La première hypothèse est correcte:

Si nous supposons être la probabilité maximale que les deux dernières balises à la position k sont u et v, d'après ce que nous venons de dire sur les astérisques commençant, la le cas de base serait

.

Vous avez cependant eu deux erreurs dans le cas général. La probabilité d'émission est conditionnelle. Toujours dans le trigramme, est répété deux fois et la formule donnée est incorrecte: