28 votos

¿Qué es un Chain de Markov?

¿Qué es una explicación intuitiva de un Chain de Markov, y cómo funcionan? Por favor proporcione al menos un ejemplo práctico.

25voto

Robert Höglund Puntos 5572

Una cadena de Markov es un aleatorio discreto proceso con la propiedad de que la siguiente estado sólo depende de la corriente estado (wikipedia)

Por lo que $P(X_n | X_1, X_2, \ldots X_n-1) = P(X_n | X_{n-1})$. Un ejemplo podría ser cuando se la modelización del clima. Entonces usted puede tomar la suposición de que el clima de hoy en día puede ser predicho por el sólo uso de los conocimientos de ayer.

Supongamos que tenemos Lluvioso y Soleado. Cuando llueve en un día, el siguiente día es Soleado con una probabilidad de 0.3. Cuando está Soleado, la probabilidad de Lluvia día siguiente es de 0.4.

Ahora, cuando se es hoy en día Soleado podemos predecir el clima en el día después de mañana, simplemente calcular la probabilidad de Lluvia para mañana, la multiplicación de que con la probabilidad de que el Sol después de la lluvia, más la probabilidad de Sol de la mañana veces la probabilidad de Sol después del sol. En total, la probabilidad de Sunny de el día después de mañana es de $P(R|S) \cdot P(S|R) + P(S|S) \cdot P(S|S) = 0.3 \cdot 0.4+0.6 \cdot 0.6 = 0.48$

9voto

Can Berk Güder Puntos 661

En pocas palabras, una cadena de Markov es (el comportamiento) de un proceso aleatorio que sólo se puede encontrar en un (no necesariamente finita) número de estados diferentes. El proceso se mueve de un estado a otro en diferentes tiempos (es decir, debe definir una secuencia de S(t) de los estados en el tiempo t=0,1,2,...), y para el cual la probabilidad de ir del estado i al estado R depende sólo de S y R; es decir, no hay una "memoria del pasado" y que el proceso es "atemporal". Esto significa que la cadena de Markov puede ser modelado como un n*n de la matriz, donde n es el número de estados posibles.

Un ejemplo de un proceso que puede ser modelado por una cadena de Markov es la secuencia de las caras de un dado muestra, si se le permite girar el dado wrt un borde. La matriz correspondiente es

    1   2   3   4   5   6
   ------------------------ 
1 | 0   1/4 1/4 1/4 1/4 0
2 | 1/4 0   1/4 1/4 0   1/4
3 | 1/4 1/4 0   0   1/4 1/4
4 | 1/4 1/4 0   0   1/4 1/4
5 | 1/4 0   1/4 1/4 0   1/4
1 | 0   1/4 1/4 1/4 1/4 0

Como de costumbre, Wikipedia y MathWorld son sus amigos.

3voto

Shawn Miller Puntos 3875

Las cadenas de Markov se utilizan en la Cadena de Markov Monte Carlo (MCMC). Esta técnica computacional es muy común en la estadística Bayesiana.

En la estadística Bayesiana, desea calcular las propiedades de una distribución posterior. Te gustaría dibujar muestras independientes a partir de esta distribución, pero a menudo esto no es factible. Así se construye una cadena de Markov que tiene como limitante de la distribución la distribución que desee. Así, por ejemplo, para obtener la media de la distribución posterior que podría tomar la media de los estados de la cadena de Markov. (Ergodic theory bendice a este proceso).

3voto

Iain Puntos 291

Yo tenía un proyecto de programación en la universidad donde se generaron grandes cantidades de pseudo-texto en inglés el uso de cadenas de Markov. La asignación está aquí, aunque no sé si ese enlace será bueno para siempre. A través de esta página:

Por ejemplo, supongamos que [nuestro cadenas de Markov son de longitud] 2 y el archivo de ejemplo contiene

I like the big blue dog better than the big elephant with the big blue hat on his tusk. 

Aquí es cómo la primera de tres palabras podría ser elegido:

  • Una de dos palabras de la secuencia es elegido al azar para convertirse en el inicial prefijo. Supongamos que "el grande" elegido.

  • La primera palabra debe ser elegido sobre la base de la probabilidad de que sigue al prefijo (en la actualidad "la grande") en la fuente. La fuente contiene tres apariciones de "la grande". Dos veces es seguido por "azul", y una vez que es seguido por "elefante". Por lo tanto, la palabra siguiente debe ser elegido de modo que no es de 2/3 de los posibilidad de que "azul" será el elegido, y un 1/3 de probabilidades de que "elefante", que será elegido. Supongamos que elegimos "azul" de este tiempo.

  • La siguiente palabra debe ser elegido sobre la base de la probabilidad de que sigue al prefijo (en la actualidad "grande azul") en la fuente. La fuente contiene dos ocurrencias de los "grandes azul". Una vez que es seguido por "perro", y el otro momento es seguido por "sombrero". Por lo tanto, la palabra siguiente debe ser elige de modo que hay un 50-50 probabilidad de elegir "perro" vs "sombrero". Supongamos que elegimos "sombrero" de este tiempo.

  • La siguiente palabra debe ser elegido sobre la base de la probabilidad de que sigue al prefijo (en la actualidad "azul sombrero") en la fuente. La fuente contiene sólo una ocurrencia de "azul sombrero", y es seguido por "en". Por lo tanto, la palabra siguiente debe estar en "on" (100% la probabilidad).

  • Por lo tanto, las tres primeras palabras en el texto de salida sería "sombrero azul ".

Que seguir así, la generación de texto que es completamente absurdo, pero termina con una especie de el mismo "tono" como el texto original. Por ejemplo, si su archivo de ejemplo es el texto completo de Alicia En el país de las Maravillas (uno de los textos que hemos probado), su tontería sale tipo de caprichosa y Carrollian (si se trata de una palabra). Si su archivo de ejemplo es El de Telltale Corazón, usted consigue un poco oscuro, morboso tonterías.

De todos modos, aunque no rigurosa, formal, definición, espero que esto ayuda a dar una idea de lo que una cadena de Markov es.

1voto

prakash Puntos 18075

Las cadenas de Markov, especialmente en modelos ocultos de Markov son muy importantes en el cálculo de la lingüística. Un modelo oculto de Markov es uno en el que no podemos ver directamente el estado, pero sí tenemos algo de información acerca de lo que el estado podría ser. Por ejemplo, considere una pena en lo que se llama "partes del discurso", tales como verbos, adjetivos, ect. No sabemos cuál de las partes de la oración, pero se puede intentar sacar de la palabra. Por ejemplo, la palabra de ejecución podría ser utilizado el 80% como un verbo, un 18% del tiempo como un sustantivo y el 2% del tiempo como un adjetivo. También tenemos (Markov) las relaciones entre las partes de la oración, así, por ejemplo, un adjetivo que podría ser seguido por un sustantivo 70% del tiempo y otro adjetivo 30% del tiempo.

Podemos utilizar el algoritmo de Viterbi para decidir cual es la secuencia más probable es que haya generado la observada frase. Este algoritmo toma en cuenta dos factores:

  • la probabilidad de una secuencia de las partes del discurso que aparecen juntos en una oración
  • la relativa probabilidad de que una secuencia de partes de la oración sería responsable de que nos la observación de la frase determinada.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X