Modelo de Markov de orden variable

En la teoría matemática de los procesos estocásticos , los modelos de Markov de orden variable (VOM) constituyen una clase importante de modelos que extienden los conocidos modelos de cadena de Markov . A diferencia de los modelos de cadena de Markov, donde cada variable aleatoria en una secuencia con una propiedad de Markov depende de un número fijo de variables aleatorias, en los modelos VOM este número de variables aleatorias condicionantes puede variar en función de la realización observada específica.

Esta secuencia de realización se denomina a menudo contexto ; por lo tanto, los modelos VOM también se denominan árboles de contexto . ^{[ 1 ]} Los modelos VOM se representan de forma atractiva mediante árboles de sufijos probabilísticos (PST) coloreados. ^{[ 2 ]} La flexibilidad en el número de variables aleatorias de condicionamiento resulta ser una ventaja real para muchas aplicaciones, como el análisis estadístico , la clasificación y la predicción . ^{[ 3 ] [ 4 ] [ 5 ]}

Consideremos, por ejemplo, una secuencia de variables aleatorias , cada una de las cuales toma un valor del alfabeto ternario { a , b , c } . Específicamente, consideremos la cadena construida a partir de concatenaciones infinitas de la subcadena aaabc : aaabcaaabcaaabcaaabc…aaabc .

El modelo VOM de orden máximo 2 puede aproximar la cadena anterior utilizando solo los siguientes cinco componentes de probabilidad condicional : Pr( a | aa ) = 0.5 , Pr( b | aa ) = 0.5 , Pr( c | b ) = 1.0 , Pr( a | c )= 1.0 , Pr( a | ca ) = 1.0 .

En este ejemplo, Pr( c | ab ) = Pr( c | b ) = 1.0 ; por lo tanto, el contexto más corto b es suficiente para determinar el siguiente carácter. De manera similar, el modelo VOM de orden máximo 3 puede generar la cadena exactamente usando solo cinco componentes de probabilidad condicional, que son todos iguales a 1.0.

Para construir la cadena de Markov de orden 1 para el siguiente carácter en esa cadena, se deben estimar los siguientes 9 componentes de probabilidad condicional: Pr( a | a ) , Pr( a | b ) , Pr( a | c ) , Pr( b | a ) , Pr( b | b ) , Pr( b | c ) , Pr( c | a ) , Pr( c | b ) , Pr( c | c ) . Para construir la cadena de Markov de orden 2 para el siguiente carácter, se deben estimar 27 componentes de probabilidad condicional: Pr( a | aa ) , Pr( a | ab ) , … , Pr( c | cc ) . Y para construir la cadena de Markov de orden tres para el siguiente carácter, se deben estimar los siguientes 81 componentes de probabilidad condicional: Pr( a | aaa ) , Pr( a | aab ) , … , Pr( c | ccc ) .

En la práctica, rara vez se dispone de datos suficientes para estimar con precisión el número de componentes de probabilidad condicional , que aumenta exponencialmente a medida que aumenta el orden de la cadena de Markov.

El modelo de Markov de orden variable supone que, en entornos realistas, existen ciertas realizaciones de estados (representadas por contextos) en las que algunos estados pasados ​​son independientes de los estados futuros; por consiguiente, "se puede lograr una gran reducción en el número de parámetros del modelo". ^{[ 1 ]}

Sea A un espacio de estados ( alfabeto finito ) de tamaño${\displaystyle |A|}$.

Consideremos una secuencia con la propiedad de Markov.${\displaystyle x_{1}^{n}=x_{1}x_{2}\dots x_{n}}$de n realizaciones de variables aleatorias , donde${\displaystyle x_{i}\in A}$es el estado (símbolo) en la posición i${\displaystyle \scriptstyle (1\leq i\leq n)}$y la concatenación de estados${\displaystyle x_{i}}$y${\displaystyle x_{i+1}}$se denota por${\displaystyle x_{i}x_{i+1}}$.

Dado un conjunto de entrenamiento de estados observados,${\displaystyle x_{1}^{n}}$, el algoritmo de construcción de los modelos VOM ^{[ 3 ] [ 4 ] [ 5 ]} aprende un modelo P que proporciona una asignación de probabilidad para cada estado en la secuencia dados sus estados pasados ​​(símbolos observados previamente) o futuros.

Específicamente, el aprendiz genera una distribución de probabilidad condicional.${\displaystyle P(x_{i}\mid s)}$para un símbolo${\displaystyle x_{i}\in A}$ dado un contexto${\displaystyle s\in A^{*}}$, donde el signo * representa una secuencia de estados de cualquier longitud, incluido el contexto vacío.

Los modelos VOM intentan estimar distribuciones condicionales de la forma${\displaystyle P(x_{i}\mid s)}$donde la longitud del contexto${\displaystyle |s|\leq D}$varía según las estadísticas disponibles. En contraste, los modelos de Markov convencionales intentan estimar estas distribuciones condicionales asumiendo una longitud de contexto fija.${\displaystyle |s|=D}$y, por lo tanto, pueden considerarse casos especiales de los modelos VOM.

En efecto, para una secuencia de entrenamiento dada, se observa que los modelos VOM obtienen una mejor parametrización del modelo que los modelos de Markov de orden fijo , lo que conduce a un mejor equilibrio entre varianza y sesgo de los modelos aprendidos. ^{[ 3 ] [ 4 ] [ 5 ]}

Se han ideado varios algoritmos eficientes para estimar los parámetros del modelo VOM. ^{[ 4 ]}

Los modelos VOM se han aplicado con éxito a áreas como el aprendizaje automático , la teoría de la información y la bioinformática , incluyendo aplicaciones específicas como la codificación y la compresión de datos , ^{[ 1 ]} la compresión de documentos, ^{[ 4 ]} la clasificación e identificación de secuencias de ADN y proteínas , ^{[ 6 ][ 3 ]} control estadístico de procesos, ^{[ 5 ]} filtrado de spam, ^{[ 7 ]} haplotipado, ^{[ 8 ]} reconocimiento de voz, ^{[ 9 ]} análisis de secuencias en ciencias sociales, ^{[ 2 ]} y otros.

• Cadenas estocásticas con memoria de longitud variable
• Ejemplos de cadenas de Markov
• Red bayesiana de orden variable
• proceso de Markov
• Cadena de Markov Monte Carlo
• Proceso semi-Markoviano
• Inteligencia artificial