Evitar el determinismo con la lógica markoviana

Question

Recién comencé a leer más sobre los generadores de cadena de Markov hoy y estoy realmente intrigado por todo el proceso de construcción de uno.Según tengo entendido, el estado futuro depende de los estados estadísticos del pasado hasta el presente.

Ejemplo:

Hola Mundo.Hola muñequita.Hola Mundo.

"Mundo" sigue a "Hola" aproximadamente el 66% del tiempo en esa fuente.

Si ese es siempre el caso, ¿cómo se puede evitar obtener los mismos resultados cada vez?Las ocurrencias estadísticas no cambiarán con una cadena estática, entonces, ¿tengo razón al suponer que no se generarán variantes, a menos que los datos fuente se modifiquen de alguna manera?

¿Cómo podría obtener variaciones de una fuente estática, considerando los valores estadísticos y permitiendo cierta flexibilidad?Usando mi ejemplo anterior, ¿cómo puedo permitir que mi generador siga a "Hola" con "Dolly", cuando "Dolly" solo sigue a "Hola" el 33% del tiempo?

Supongo que lo que pregunto es: ¿Cómo baso la probabilidad de mi próxima selección en la presencia estadística de las palabras que siguen a mi selección actual?De esa manera, "Dolly" aparece el 33% de las veces y "World" aparece el 66% de las veces, ¿o estoy completamente perdido aquí?

Answer 1

Se utiliza un generador de números aleatorios para recoger el camino que va hacia abajo. Tienes que salvar cada estado (que es realmente una historia de N elementos anteriores) y las probabilidades para ese estado. Después debe elegir un número aleatorio y decidir en base a lo que el siguiente estado que la transición a es.

En el ejemplo que tiene una cadena de Markov con una N de 1 tendría una estructura de cadena que parecía algo como esto:

<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 su estado actual es Hola, a continuación, sus próximos estados posibles son Mundial. y Dolly .. Generar un número aleatorio entre 0 y 1 y elija Mundial. si es menos de 0,666666, de lo contrario elegir Dolly.

Con una cadena de Markov N = 2, se obtiene un comportamiento casi determinista con esa entrada:

<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

Dos observaciones:

1) Para generar muestras de un proceso aleatorio, si o no un determinado elección es bastante (> 50%) probable, y otras no tanto, sólo requiere un ponderada "flip moneda": generar un número real aleatorio uniforme en [ 0,1), y considerar las posibilidades en el mismo orden fijo, manteniendo una suma de probabilidades hasta ahora. Tan pronto como la suma excede su número elegido al azar, seleccione esa opción. Si sus opciones han unnormalized (no sumando a 1) las probabilidades, primero tiene que calcular la suma de probabilidades s, y, o bien dividir a todos ellos por s, o elegir el número al azar en [0, s)

2) Para evitar el sobreajuste al estimar el modelo de una pequeña cantidad de datos de entrenamiento de la muestra (en comparación con el número de parámetros), utilice priores bayesianos en los parámetros del modelo. Para un ejemplo muy fresco de este, donde el número de parámetros del modelo (tamaño historia) no está fijado a cualquier número finito con antelación, consulte la Infinito HMM . Si usted no utiliza métodos bayesianos, entonces usted querrá elegir la longitud de la historia adecuada para la cantidad de datos de entrenamiento que tiene, y / o poner en práctica algunas de suavizado ad-hoc (por ejemplo, interpolación lineal entre una orden-2 y orden- 1 modelo).