Éviter le déterminisme à l'aide de la logique markovienne

Question

Je viens de commencer à en savoir plus sur les générateurs de chaînes de Markov aujourd'hui, et je suis vraiment intriguée par l'ensemble du processus de construction d'une chaîne. D'après ce que je comprends, l'état futur dépend des états statistiques passés jusqu'à présent.

Exemple:

Bonjour tout le monde. Bonjour Dolly. Bonjour le monde.

"Monde" suit "Bonjour" ~ 66% du temps dans cette source.

Si c'est toujours le cas, comment évitez-vous de sortir les mêmes résultats à chaque fois? Les occurrences statistiques ne changeront pas avec une chaîne statique, donc ai-je raison de supposer qu'aucune variante ne sera générée, à moins que les données sources ne soient modifiées d'une manière ou d'une autre?

Comment pourrais-je obtenir des variations d'une source statique, compte tenu des valeurs statistiques, tout en permettant une certaine flexibilité? En utilisant mon exemple ci-dessus, comment puis-je permettre à mon générateur de suivre "Bonjour" avec "Dolly", alors que "Dolly" ne suit que "Bonjour" 33% du temps?

Je suppose que ce que je demande est, comment puis-je baser la probabilité de ma prochaine sélection sur la présence statistique des mots qui suivent ma sélection actuelle? De cette façon, "Dolly" apparaît 33% du temps, et "World" apparaît 66% du temps - ou suis-je complètement perdu ici?

Answer 1

Vous utilisez un générateur de nombres aléatoires pour choisir le chemin que vous descendez. Vous devez enregistrer chaque état (qui est en réalité un historique de N éléments précédents) et les probabilités pour cet état. Ensuite, vous choisissez un nombre aléatoire et décidez en fonction de ce que le prochain état de transition est.

Dans votre exemple, vous avez une chaîne de Markov avec un N de 1 vous auriez une structure de la chaîne qui avait l'air quelque chose comme ceci:

<start> -> Hello : 1.0 

Hello -> World. : 0.66666 
Hello -> Dolly. : 0.33333 

Dolly. -> Hello : 1.0 

World. -> <end> : 0.5 
World. -> Hello : 0.5 

Si votre état actuel est Bonjour, alors vos prochains états possibles sont du monde . et Dolly .. Générez un nombre aléatoire compris entre 0 et 1 et choisissez Monde. s'il est inférieur à 0,666666, sinon choisissez Dolly.

Avec une chaîne de Markov N = 2, vous obtenez un comportement presque déterministe avec cette entrée:

<start> <start> -> <start> Hello : 1.0 

<start> Hello -> Hello World. : 1.0 

Hello World. -> World. Hello : 0.5 
Hello World. -> World. <end> : 0.5 

World. Hello -> Hello Dolly. : 1.0 

Hello Dolly. -> Dolly. Hello : 1.0 

Dolly. Hello -> Hello World. : 1.0 

Answer 2

Deux commentaires:

1) pour produire des échantillons à partir d'un processus aléatoire, si oui ou non un certain le choix est tout à fait probable (> 50%), et d'autres moins, nécessite simplement un "coin flip" pondéré: générer un nombre réel aléatoire uniformément sur [0,1), et considérer les possibilités dans le même ordre fixe, en gardant une somme des probabilités jusqu'à présent. Dès que cette somme dépasse votre nombre choisi au hasard, sélectionnez ce choix. Si vos choix ont des probabilités non normalisées (non cumulées à 1), vous devez d'abord calculer la somme des probabilités s, et soit les diviser toutes par s, soit choisir votre nombre aléatoire sur [0, s)

2) Pour évitez les surajustements lors de l'estimation de votre modèle à partir d'une petite quantité de données d'apprentissage (par rapport au nombre de paramètres), utilisez les a priori bayésiens sur les paramètres du modèle. Pour un exemple vraiment cool, où le nombre de paramètres du modèle (taille de l'historique) n'est pas fixé à un nombre fini à l'avance, voir le Infinite HMM.Si vous n'utilisez pas les méthodes bayésiennes, vous devez choisir la longueur de l'historique en fonction de la quantité de données d'entraînement que vous possédez et/ou appliquer un lissage ad hoc (par exemple, interpolation linéaire entre un ordre 2 et un ordre). 1 modèle).