Introducción a las cadenas de Markov
¿Qué son las cadenas de Markov, cuándo usarlas y cómo funcionan?
Devin Soni 👑
5 de marzo de 2018·4 min de lectura
Las cadenas de Markov son una forma bastante común y relativamente simple de modelar estadísticamente procesos aleatorios. Se han utilizado en muchos dominios diferentes, que van desde la generación de texto hasta el modelado financiero. Un ejemplo popular es r / SubredditSimulator, que usa cadenas de Markov para automatizar la creación de contenido para un subreddit completo. En general, las cadenas de Markov son conceptualmente bastante intuitivas y muy accesibles, ya que pueden implementarse sin el uso de conceptos estadísticos o matemáticos avanzados. Son una excelente manera de comenzar a aprender sobre modelado probabilístico y técnicas de ciencia de datos.
Guión
Empezar, Los describiré con un ejemplo muy común:
Imagine that there were two possible states for weather: sunny or cloudy. You can always directly observe the current weather state, and it is guaranteed to always be one of the two aforementioned states.Now, you decide you want to be able to predict what the weather will be like tomorrow. Intuitively, you assume that there is an inherent transition in this process, in that the current weather has some bearing on what the next day’s weather will be. So, being the dedicated person that you are, you collect weather data over several years, and calculate that the chance of a sunny day occurring after a cloudy day is 0.25. You also note that, by extension, the chance of a cloudy day occurring after a cloudy day must be 0.75, since there are only two possible states.You can now use this distribution to predict weather for days to come, based on what the current weather state is at the time.
Este ejemplo ilustra muchos de los conceptos clave de una cadena de Markov. Una cadena de Markov consiste esencialmente en un conjunto de transiciones, que están determinadas por alguna distribución de probabilidad, que satisface la Propiedad de Markov.
Observe cómo en el ejemplo, la distribución de probabilidad se obtiene únicamente observando las transiciones del día actual al siguiente. Esto ilustra la propiedad de Markov, la característica única de los procesos de Markov que los convierte en sin memoria. Por lo general, esto los deja incapaces de producir con éxito secuencias en las que se esperaría que ocurriera alguna tendencia subyacente. Por ejemplo, si bien una cadena de Markov puede imitar el estilo de escritura de un autor en función de la frecuencia de las palabras, no podría producir texto que contenga un significado profundo o temático, ya que estos se desarrollan en secuencias de texto mucho más largas. Por lo tanto, carecen de la capacidad de producir contenido dependiente del contexto, ya que no pueden tener en cuenta la cadena completa de estados anteriores.
El modelo
Formalmente, una cadena de Markov es un autómata probabilístico. La distribución de probabilidad de las transiciones de estado se representa típicamente como la cadena de Markov. matriz de transición. Si la cadena de Markov tiene norte posibles estados, la matriz será un N x N matriz, tal que la entrada (Yo, j) es la probabilidad de pasar del estado I a estado J. Además, la matriz de transición debe ser una matriz estocástica, una matriz cuyas entradas en cada fila deben sumar exactamente 1. Esto tiene mucho sentido, ya que cada fila representa su propia distribución de probabilidad.
Además, una cadena de Markov también tiene un vector de estado inicial, representado como un N x 1 matriz (un vector), que describe la distribución de probabilidad de comenzar en cada uno de los norte estados posibles. Entrada I del vector describe la probabilidad de que la cadena comience en el estado I.
Estas dos entidades suelen ser todo lo que se necesita para representar una cadena de Markov.
Ahora sabemos cómo obtener la posibilidad de pasar de un estado a otro, pero ¿qué tal si encontramos la posibilidad de que esa transición se produzca en varios pasos? Para formalizar esto, ahora queremos determinar la probabilidad de pasar del estado I al estado J en M pasos. Resulta que, en realidad, es muy sencillo averiguarlo. Dada una matriz de transición PAG, esto se puede determinar calculando el valor de entrada (Yo, j) de la matriz obtenida elevando PAG al poder de METRO. Para pequeños valores de METRO, esto se puede hacer fácilmente a mano con multiplicaciones repetidas. Sin embargo, para grandes valores de METRO, si está familiarizado con el álgebra lineal simple, una forma más eficiente de elevar una matriz a una potencia es primero diagonalizar la matriz.
Conclusión
Ahora que conoce los conceptos básicos de las cadenas de Markov, debería poder implementarlas fácilmente en el idioma que elija. Si la codificación no es su fuerte, también hay muchas propiedades más avanzadas de las cadenas de Markov y los procesos de Markov en las que sumergirse. En mi opinión, la progresión natural a lo largo de la ruta de la teoría sería hacia los Procesos Ocultos de Markov o MCMC. Las cadenas de Markov simples son los componentes básicos de otras técnicas de modelado más sofisticadas, por lo que con este conocimiento, ahora puede pasar a varias técnicas dentro de temas como el modelado de creencias y el muestreo.