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 amplían 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 de VOM este número de variables aleatorias condicionantes puede variar según la realización específica observada.
Esta secuencia de realización a menudo se denomina contexto ; por lo tanto, los modelos VOM también se denominan árboles de contexto . [1] La flexibilidad en el número de condicionantes de variables aleatorias resulta ser una ventaja real para muchas aplicaciones, como el análisis estadístico , la clasificación y la predicción . [2] [3] [4]
Ejemplo
Considere, por ejemplo, una secuencia de variables aleatorias , cada una de las cuales toma un valor del alfabeto ternario { a , b , c }. Específicamente, considere la cadena aaabcaaabcaaabcaaabc ... aaabc construida a partir de concatenaciones infinitas de la subcadena aaabc .
El modelo VOM de orden máximo 2 puede aproximarse a la cadena anterior usando 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 b más corto 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 de 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 condicionales: {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 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 asume que en escenarios 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.
Considere una secuencia con la propiedad de Markov de n realizaciones de variables aleatorias , dondees el estado (símbolo) en la posición i , y la concatenación de estados y se denota por .
Dado un conjunto de entrenamiento de estados observados, , el algoritmo de construcción de los modelos VOM [2] [3] [4] aprende un modelo P que proporciona una asignación de probabilidad para cada estado en la secuencia dado su pasado (símbolos observados previamente) o estados futuros.
Específicamente, el alumno genera una distribución de probabilidad condicional por un símbolo dado un contexto , 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 donde la longitud del contexto varía en función de las estadísticas disponibles. En contraste, los modelos de Markov convencionales intentan estimar estas distribuciones condicionales asumiendo una longitud de contextos fija y, por tanto, pueden considerarse como casos especiales de los modelos VOM.
Efectivamente, para una secuencia de entrenamiento dada, se encuentra que los modelos VOM obtienen una mejor parametrización del modelo que los modelos de Markov de orden fijo, lo que conduce a una mejor compensación de varianza- sesgos de los modelos aprendidos. [2] [3] [4]
Áreas de aplicación
Se han ideado varios algoritmos eficientes para estimar los parámetros del modelo VOM. [3]
Los modelos de VOM se han aplicado con éxito en áreas como el aprendizaje automático , la teoría de la información y la bioinformática , incluidas aplicaciones específicas como codificación y compresión de datos , [1] compresión de documentos, [3] clasificación e identificación de secuencias de ADN y proteínas , [5] [ 1] [2] control estadístico de procesos , [4] filtrado de spam , [6] haplotipado [7] y otros.
Ver 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-Markov
- Inteligencia artificial
Referencias
- ↑ a b c Rissanen, J. (septiembre de 1983). "Un sistema de compresión de datos universal". Transacciones IEEE sobre teoría de la información . 29 (5): 656–664. doi : 10.1109 / TIT.1983.1056741 .
- ^ a b c d Shmilovici, A .; Ben-Gal, I. (2007). "Uso de un modelo de VOM para reconstruir regiones de codificación potenciales en secuencias EST". Estadística computacional . 22 (1): 49–69. doi : 10.1007 / s00180-007-0021-8 .
- ^ a b c d e Begleiter, R .; El-Yaniv, R .; Yona, G. (2004). "Sobre la predicción utilizando modelos de Markov de orden variable" (PDF) . Revista de Investigación en Inteligencia Artificial . 22 : 385–421. doi : 10.1613 / jair.1491 . Archivado desde el original (PDF) el 28 de septiembre de 2007 . Consultado el 22 de abril de 2007 .
- ^ a b c d Ben-Gal, I .; Morag, G .; Shmilovici, A. (2003). "CSPC: un procedimiento de seguimiento para los procesos dependientes del estado" (PDF) . Tecnometría . 45 (4): 293–311. doi : 10.1198 / 004017003000000122 .
- ^ 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) . Investigación de ácidos nucleicos, vol. 34, edición W529 – W533. Cite journal requiere
|journal=
( ayuda ) - ^ Bratko, A .; Cormack, GV; Filipic, B .; Lynam, T .; Zupan, B. (2006). "Filtrado de correo no deseado mediante modelos de compresión de datos estadísticos" (PDF) . Revista de investigación sobre aprendizaje automático . 7 : 2673–2698.
- ^ Browning, Sharon R. "Mapeo de asociación multilocus utilizando cadenas de Markov de longitud variable". The American Journal of Human Genetics 78.6 (2006): 903–913.
[1]
- ^ Smith, AR; Denenberg, JN; Holgura, TB; Tan, CC; Wohlford, R. E (agosto de 1985). "Aplicación de un sistema de aprendizaje de patrones secuenciales para el reconocimiento de voz conectado" (PDF) . Actas de la Conferencia Internacional IEEE 1985 sobre Procesamiento de Acústica, Habla y Señales : 1201–1204.