55
¿Es una máquina de estados finitos solo una implementación de una cadena de Markov? ¿Cuáles son las diferencias entre los dos?¿Es una cadena de Markov lo mismo que una máquina de estado finito?
A
Respuesta
45
Las cadenas de Markov se pueden representar mediante máquinas de estado finito. La idea es que una cadena de Markov describa un proceso en el que la transición a un estado en el tiempo t + 1 depende únicamente del estado en el momento t. Lo más importante a tener en cuenta es que las transiciones en una cadena de Markov son probabilísticas más que deterministas, lo que significa que no siempre se puede decir con certeza absoluta qué sucederá en el tiempo t + 1.
Los artículos de Wikipedia en Finite-state machines tienen una subsección en Finite Markov-chain processes, recomendaría leer eso para más información. Además, el artículo de Wikipedia en Markov chains tiene una breve oración que describe el uso de máquinas de estado finito para representar una cadena de Markov. Que estados:
Una máquina de estado finito se puede utilizar como una representación de una cadena de Markov. Suponiendo una secuencia de independiente y señales de entrada idénticamente distribuidas (por ejemplo, símbolos de un binario alfabeto elegido por lanzamientos de moneda), si la máquina está en el estado y en el tiempo n, entonces la probabilidad de que se mueve a estado x en el tiempo n + 1 depende solo de el estado actual.
+1
En realidad, lo que está reclamando aquí sobre una cadena de Markov no es 100% correcto. A lo que se refiere aquí es al "proceso de Markov de primer orden". Para un proceso de Markov de segundo orden, el siguiente estado dependerá de los últimos 2 estados de los pasos de tiempo, ...... Una máquina de estado es un caso especial de una cadena de Markov; ya que una cadena de Markov es de naturaleza estocástica. Una máquina de estado, hasta donde yo sé, es determinista. –
+3
No calificado, el término cadena de Markov significa un proceso estocástico en tiempo discreto con la propiedad de Markov, lo que significa que no depende de estados anteriores. El póster original no preguntó sobre los procesos de Markov de orden superior, por lo que no son tan relevantes. La máquina de estados finitos generalmente es un término de captura para los autómatas finitos, estos pueden ser de naturaleza determinista o no determinista. –
19
Mientras que una cadena de Markov es una máquina de estados finitos, se distingue por sus transiciones que son estocásticas, es decir, aleatorias, y se describen por probabilidades.
+2
Gracias por esto, exactamente lo que estaba buscando. –
+2
¿Puedo decir, estocásticos autómatas de estados finitos? –
15
Los dos son similares, pero las otras explicaciones aquí son un poco incorrectas. Solo las cadenas de FINITE Markov pueden ser representadas por un FSM. Las cadenas de Markov permiten un espacio de estado infinito. Como se señaló, las transiciones de una cadena de Markov se describen por probabilidades, pero también es importante mencionar que las probabilidades de transición solo pueden depender del estado actual. Sin esta restricción, se llamaría un "proceso estocástico de tiempo discreto".
+1
(+1) Buenos puntos de aclaración que vale la pena tomar. Gracias –
0
Si dejamos de lado los detalles internos de trabajo, la máquina de estado finito es como un valor simple, mientras que la cadena de markov es como una variable aleatoria (agregue probabilidad sobre el valor normal). Entonces la respuesta a la pregunta original es no, no son lo mismo. En el sentido probabilístico, la cadena de Markov es una extensión de la máquina de estados finitos.
6
Por favor, lea estos documentos:
Los vínculos entre los modelos probabilísticos Autómatas y Ocultos de Markov (por Pierre Dupont) http://www.info.ucl.ac.be/~pdupont/pdupont/pdf/HMM_PA_pres_n4.pdf
[El Manual de Teoría del Cerebro y Redes Neuronales] Modelos Ocultos de Markov y otros estados finitos Autómatas para procesamiento de secuencia http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.3344&rep=rep1&type=pdf
Cuestiones relacionadas
- 1. ¿Hay un término para una máquina de estado finito que se garantiza que se detenga?
- 2. ¿Qué es un transductor de estado finito?
- 3. es SSIS inserción masiva lo mismo que una inserción masiva
- 4. ¿Window.location() es lo mismo que una solicitud GET?
- 5. ¿Corba es lo mismo que SOA?
- 6. Diseñando una máquina de estado en C++
- 7. ¿Es LinqToSQL lo mismo que Linq?
- 8. ¿Cuál es la mejor forma de calcular la matriz fundamental de una cadena de Markov absorbente?
- 9. ¿Es '<? =' Lo mismo que 'eco'?
- 10. ¿C# incluye máquinas de estado finito?
- 11. ¿DbContext es lo mismo que DataContext?
- 12. YARD no es lo mismo que RDoc?
- 13. puntero NULL es lo mismo que desasignarlo?
- 14. Cadena de Markov simple en R (visualización)
- 15. ¿Es "extend self" lo mismo que "module_function"?
- 16. ¿Es 'yield self' lo mismo que instance_eval?
- 17. ¿No es 00.0 lo mismo que 0.0?
- 18. ¿Es dp lo mismo que dip?
- 19. ¿Currying es lo mismo que sobrecargar?
- 20. ¿Es AppendHeader exactamente lo mismo que AddHeader?
- 21. Cadena gráfica de markov en javascript
- 22. ¿Por qué no es Guid.ToString ("n") lo mismo que una cadena hexadecimal generada a partir de una matriz de bytes del mismo guid?
- 23. ¿Debería una máquina de estados exponer su estado actual?
- 24. ¿Es una línea en un programa Java lo mismo que una instrucción?
- 25. Markov proceso de toma
- 26. Encoding.Default no es lo mismo que ninguna codificación en File.ReadAllText?
- 27. C#: ¿Cómo evitar que dos instancias de una aplicación hagan lo mismo al mismo tiempo?
- 28. ¿Por qué ** ordenar ** no ordena lo mismo en cada máquina?
- 29. ¿La máquina virtual Java es realmente una máquina virtual en el mismo sentido que mi archivo VMWare o Parallels?
- 30. FST (transductores de estado finito) Bibliotecas, C++ o java
Puede pensar en una cadena de Markov como un FSM en el que las transiciones son probabilísticamente impulsadas –