Cadenas de Markov

Una cadena de Markov es un proceso estocástico que transita entre los estados de un conjunto —el clima de mañana, la posición de una ficha en un tablero, la palabra siguiente de una frase— siguiendo reglas de probabilidad. Su rasgo definitorio es la propiedad de Markov, o «falta de memoria»: la probabilidad del próximo estado depende únicamente del estado actual, no de todo el camino recorrido para llegar hasta él. El presente contiene toda la información necesaria para predecir el futuro inmediato; una vez sabido dónde está el sistema, su pasado es irrelevante.

La propiedad de Markov y la matriz de transición

Cuando el conjunto de estados es finito, la dinámica de la cadena se resume en una matriz de transición: cada casilla indica la probabilidad de pasar de un estado a otro en un paso, y cada fila suma uno, porque desde cualquier estado algo tiene que ocurrir. Multiplicar la distribución actual de probabilidades por esa matriz produce la del paso siguiente; repetir la operación proyecta el comportamiento de la cadena a lo largo del tiempo. Toda la memoria del sistema cabe, así, en una tabla de números.

La distribución estacionaria

Muchas cadenas tienden, a la larga, a una distribución estacionaria: un reparto de probabilidad que ya no cambia al aplicarle la matriz de transición. Es el equilibrio hacia el que converge el sistema con independencia de dónde empezó. No toda cadena lo alcanza; hacen falta dos condiciones. La irreducibilidad exige que sea posible llegar de cualquier estado a cualquier otro; la aperiodicidad, que la cadena no quede atrapada en ciclos rígidos. Cumplidas ambas, una cadena finita converge a una única distribución estacionaria, sin importar su punto de partida. Ese resultado es la razón de fondo por la que las cadenas de Markov resultan tan útiles: garantizan un comportamiento predecible a largo plazo.

Usos en IA: HMM, MCMC y PageRank

Sobre esta base se levantan herramientas centrales de la IA. Los modelos ocultos de Márkov (HMM) —populares en el reconocimiento de voz gracias, entre otros, a los trabajos de Lawrence Rabiner— suponen una cadena cuyos estados no se observan directamente, sino a través de señales emitidas. El muestreo de Montecarlo por cadenas de Markov (MCMC), con algoritmos como Metropolis-Hastings y el muestreo de Gibbs, construye a propósito una cadena cuya distribución estacionaria es la que se quiere estudiar, y luego la deja correr para tomar muestras; es la maquinaria de buena parte de la estadística bayesiana. Y el PageRank de Sergey Brin y Larry Page, corazón original de Google, no es más que un paseo aleatorio por la web: la importancia de cada página es su probabilidad en la distribución estacionaria de un navegante que salta de enlace en enlace.

Conviene no confundir la cadena de Markov con el proceso de decisión de Markov (MDP), su pariente del aprendizaje por refuerzo: el MDP añade acciones y recompensas, de modo que ya no se observa un sistema, sino que se decide cómo actuar dentro de él.