[2021] Introducción a las Cadenas de Markov {DH}

Las cadenas de Markov son una forma bastante común y relativamente simple de modelar estadísticamente procesos aleatorios. Se han utilizado en muchos campos diferentes, 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 utilizar conceptos estadísticos o matemáticos avanzados. Son una excelente manera de comenzar a aprender técnicas de modelado probabilístico y ciencia de datos.

guion

Comienzo, 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 una serie de transiciones determinadas por una distribución de probabilidad que satisface el Propiedad de Markov.

Tenga en cuenta que en el ejemplo, la distribución de probabilidad se obtiene únicamente considerando 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 crea. sin memoria. Esto generalmente resulta en su incapacidad para crear con éxito secuencias en las que se esperaría una tendencia subyacente. Por ejemplo, mientras que 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 textos que contengan un significado profundo o temático, ya que estos se desarrollan en secuencias de texto mucho más grandes. Por lo tanto, carecen de la capacidad de producir contenido contextual porque no pueden considerar toda la cadena de estados previos.

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 una cadena de Markov. matriz de transición. Si la cadena de Markov tiene norte posibles estados, la matriz será una N×N matriz por lo que la entrada (yo j) es la probabilidad de salir del estado sí para explicar j. Además, la matriz de transición debe ser una Matriz estocásticauna 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 una vector de estado inicialrepresentado como Nx1 Matriz (un vector) que describe la distribución de probabilidad de comenzar en cada uno de los norte estados posibles. entrada sí del vector describe la probabilidad de que la cadena comience en el estado sí.

Estas dos entidades suelen ser todo lo que se necesita para representar una cadena de Markov.

Ahora que sabemos cómo obtener la capacidad de hacer la transición de un estado a otro, ¿qué pasa si podemos encontrar una manera de que esa transición suceda en varios pasos? Para formalizar esto, ahora determinemos la probabilidad de pasar del estado I al estado J en M pasos. Resulta que en realidad es bastante fácil de averiguar. Se da una matriz de transición PAGSesto se puede determinar calculando el valor de entrada (yo j) de la matriz obtenida al levantar PAGS alto METRO. Para pequeños valores de METRO, esto se puede hacer fácilmente a mano multiplicando varias veces. Sin embargo, para valores grandes de METROSi 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 puede profundizar. 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 otros…