Modelo de Markov de orden variable

Procesos basados ​​en Markov con "memoria" variable

En la teoría matemática de los procesos estocásticos , los modelos de Markov de orden variable (VOM) son 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 agradable mediante árboles de sufijos probabilísticos coloreados (PST). ^[2] La flexibilidad en el número de variables aleatorias condicionantes resulta ser una verdadera ventaja para muchas aplicaciones, como el análisis estadístico , la clasificación y la predicción . ^{[3] [4] [5]}

Ejemplo

Consideremos, por ejemplo, una secuencia de variables aleatorias , cada una de las cuales toma un valor del alfabeto ternario { a , b , c } . En concreto, 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 utilizando 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, uno debe 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, uno debe 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 hay datos suficientes para estimar con precisión el número exponencialmente creciente de componentes de probabilidad condicional a medida que aumenta el orden de la cadena de Markov.

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

Definición

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

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

Dado un conjunto de entrenamiento de estados observados, , 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. ${\displaystyle x_{1}^{n}}$

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

Los modelos VOM intentan estimar distribuciones condicionales de la forma en que la longitud del contexto varía en función de las estadísticas disponibles. Por el contrario, los modelos Markov convencionales intentan estimar estas distribuciones condicionales suponiendo una longitud de contexto fija y, por lo tanto, pueden considerarse casos especiales de los modelos VOM. ${\displaystyle P(x_{i}\mid s)}$ ${\displaystyle |s|\leq D}$ ${\displaystyle |s|=D}$

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

Áreas de aplicación

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

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

Véase también

• 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

Referencias

1. Rissanen, J. (septiembre de 1983). "Un sistema universal de compresión de datos". IEEE Transactions on Information Theory . 29 (5): 656–664. doi :10.1109/TIT.1983.1056741.
2. Gabadinho, Alexis; Ritschard, Gilbert (2016). "Análisis de secuencias de estados con árboles de sufijos probabilísticos: el paquete PST R". Revista de software estadístico . 72 (3). doi : 10.18637/jss.v072.i03 . ISSN  1548-7660. S2CID  63681202.
3. Shmilovici, A.; Ben-Gal, I. (2007). "Uso de un modelo VOM para reconstruir regiones de codificación potenciales en secuencias EST". Computational Statistics . 22 (1): 49–69. doi :10.1007/s00180-007-0021-8. S2CID  2737235.
4. Begleiter, R.; El-Yaniv, R.; Yona, G. (2004). "Sobre la predicción utilizando modelos de Markov de orden variable". Revista de investigación en inteligencia artificial . 22 : 385–421. arXiv : 1107.0051 . doi : 10.1613/jair.1491 .
5. Ben-Gal, I.; Morag, G.; Shmilovici, A. (2003). "Control estadístico de procesos basado en el contexto: un procedimiento de monitoreo para procesos dependientes del estado" (PDF) . Technometrics . 45 (4): 293–311. doi :10.1198/004017003000000122. ISSN  0040-1706. S2CID  5227793.
6. Grau J.; Ben-Gal I.; Posch S.; Grosse I. (2006). "VOMBAT: Predicción de sitios de unión de factores de transcripción utilizando árboles bayesianos de orden variable" (PDF) . Nucleic Acids Research . 34 (número del servidor web). Nucleic Acids Research, vol. 34, número W529–W533.: W529-33. doi :10.1093/nar/gkl212. PMC 1538886 . PMID  16845064. 
7. Bratko, A.; Cormack, G. V.; Filipic, B.; Lynam, T.; Zupan, B. (2006). "Filtrado de spam mediante modelos de compresión de datos estadísticos" (PDF) . Journal of Machine Learning Research . 7 : 2673–2698.
8. Browning, Sharon R. "Mapeo de asociaciones de múltiples loci utilizando cadenas de Markov de longitud variable". The American Journal of Human Genetics 78.6 (2006): 903–913.
9. Smith, A.; Denenberg, J.; Slack, T.; Tan, C.; Wohlford, R. (1985). "Aplicación de un sistema de aprendizaje de patrones secuenciales al reconocimiento de voz conectado". ICASSP '85. IEEE International Conference on Acoustics, Speech, and Signal Processing . Vol. 10. Tampa, FL, EE. UU.: Instituto de Ingenieros Eléctricos y Electrónicos. págs. 1201–1204. doi :10.1109/ICASSP.1985.1168282. S2CID  60991068.