Création d'un modèle de Markov à entropie maximale à partir d'un classificateur d'entropie maximale à entrées multiples existant

9

Je suis intrigué par le concept d'un modèle de Markov à entropie maximale (MEMM) et je songe à l'utiliser pour un marqueur de partie de la parole (POS). En ce moment, j'utilise un classificateur conventionnel d'entropie maximale (ME) pour baliser chaque mot individuel. Cela utilise un certain nombre de fonctionnalités, y compris les deux balises précédentes.

Les MEMM utilisent l'algorithme de Viterbi pour trouver le chemin optimal à travers la chaîne de Markov (c'est-à-dire pour trouver un ensemble optimal complet de balises pour la phrase plutôt que des optimums individuels pour chaque mot). En lisant à ce sujet, cela semble avoir une merveilleuse élégance et simplicité. Cependant, chaque étape ne repose que sur les "résultats" de l'étape précédente (c'est-à-dire selon une chaîne de Markov).

Cependant, mon modèle ME utilise les deux étapes précédentes (c'est-à-dire les balises des deux mots précédents). Il semble que j'ai deux approches possibles:

  • Comme avec une implémentation Viterbi conventionnelle, utilisez un ensemble de chemins stockés selon une étape (la précédente). Mon classificateur ME utiliserait ceci et une étape «gelée» avant cela (figée dans le chemin considéré) pour produire la fonction de transfert.

  • Ou j'écris l'algorithme pour suivre deux étapes. Ceci est plus compliqué et ne serait plus un vrai modèle de Markov car chaque fonction de transfert (c'est-à-dire du modèle ME) dépendrait des deux étapes précédentes et non d'une étape.

Il me semble que le second sera plus précis, même s'il sera plus compliqué.

Je n'ai pas encore trouvé d'exemples de cela lors de ma recherche documentaire. At-il été essayé? L'approche en deux étapes a-t-elle amélioré la précision globale?

winwaed
la source

Réponses:

4

(C'est vraiment une vraie question à laquelle je suis confronté et la mise en ligne du site ML StackExchange était à peu près parfaite: j'avais fait quelques jours de lecture de livres et de recherche en ligne et j'étais sur le point de commencer à l'implémenter. Voici mes résultats. Bien que ils ne sont pas rigoureux, je pense qu'ils répondent à ma propre question. Je vais laisser la question ouverte pour le moment au cas où quelqu'un aurait une contribution utile, aurait essayé quelque chose de similaire ou aurait des références utiles.)

D'accord au cours des deux derniers jours, j'ai codé cela. Le code n'est pas très efficace - beaucoup de création et de copie de collection, mais le but de l'exercice était de voir si cela fonctionnerait et comment cela fonctionne.

Je divise mes données au hasard en deux listes: les données d'entraînement et les données de test. J'exécute les données de test via le Tagger POS à Entropie Maximum conventionnelle; et mon nouveau tagueur MEMM. Par conséquent, ils voient les mêmes données de test, permettant des comparaisons directes - en raison du caractère aléatoire des données choisies, je constate une certaine variation entre les tests (généralement environ 0,2-0,4%).

Le premier test utilise un marqueur MEMM avec une seule étape (c'est-à-dire une véritable chaîne de Markov). Cela a toujours mieux performé que le simple marqueur ME d'environ 0,1-0,25%.

Ensuite, j'ai essayé l'approche en deux étapes qui semble être plus correcte. Mais les résultats étaient encore plus marginaux. Souvent, les résultats étaient identiques, parfois ils étaient légèrement inférieurs, mais probablement la majorité des fois, ils étaient légèrement meilleurs (donc +/- 0,05%).

Le tagueur MEMM est lent. D'accord, je n'ai appliqué aucune optimisation, mais l'étape 1 (véritable chaîne de Markov) est N fois plus lente (où N = nombre d'étiquettes) car il s'agit du nombre de chemins qui sont transférés entre chaque étape. L'implémentation en 2 étapes est N * N plus lente (en raison du plus grand nombre de chemins transférés). Bien que les optimisations puissent améliorer les choses, c'est probablement trop lent pour la plupart des applications pratiques.

Une chose que j'essaie est d'appliquer une limite de probabilité inférieure aux chemins. C'est à dire. les chemins de Viterbi sont élagués à chaque itération avec tous les chemins inférieurs à une certaine probabilité (actuellement Log (chemin total P) <- 20,0) sont élagués. Cela fonctionne un peu plus rapidement, mais la question demeure de savoir si cela en vaut la peine. Je pense que ce n'est probablement pas le cas.

Pourquoi ne voyons-nous aucune amélioration? Je pense que cela est principalement dû au comportement des balises POS et au modèle d'entropie maximale. Bien que le modèle prenne des fonctionnalités basées sur les deux balises précédentes, la balise précédente immédiate est beaucoup plus importante que celle qui la précède. Intuitivement, cela aurait du sens pour la langue anglaise (par exemple, un adjectif est généralement suivi d'un nom ou d'un autre adjectif, mais cela ne dépend pas vraiment de ce qui était avant l'adjectif).

winwaed
la source