Las cadenas estocásticas con memoria de longitud variable son una familia de cadenas estocásticas de orden finito en un alfabeto finito, tal como, por cada paso de tiempo, solo es necesario un sufijo finito del pasado, llamado contexto, para predecir el siguiente símbolo. Estos modelos fueron introducidos en la literatura sobre teoría de la información por Jorma Rissanen en 1983, [1] como una herramienta universal para la compresión de datos , pero recientemente se han utilizado para modelar datos en diferentes áreas como biología , [2] lingüística [3] y música. . [4]
Definición
Una cadena estocástica con memoria de longitud variable es una cadena estocástica , tomando valores en un alfabeto finito , y caracterizado por un árbol de contexto probabilístico , así que eso
- es el grupo de todos los contextos. Un contexto, ser el tamaño del contexto, es una porción finita del pasado , que es relevante para predecir el siguiente símbolo ;
- es una familia de probabilidades de transición asociadas con cada contexto.
Historia
La clase de cadenas estocásticas con memoria de longitud variable fue introducida por Jorma Rissanen en el artículo Un sistema universal para sistema de compresión de datos . [1] Esta clase de cadenas estocásticas fue popularizada en la comunidad estadística y probabilística por P. Bühlmann y AJ Wyner en 1999, en el artículo Cadenas de Markov de longitud variable . Llamadas por Bühlmann y Wyner como “ cadenas de Markov de longitud variable ” (VLMC), estas cadenas también se conocen como “ modelos de Markov de orden variable ” (VOM), “ árboles de sufijos probabilísticos ” [2] y “ modelos de árbol de contexto ”. [5 ] El nombre “cadenas estocásticas con memoria de longitud variable” parece haber sido introducido por Galves y Löcherbach, en 2008, en el artículo del mismo nombre [6].
Ejemplos de
Fuente de luz interrumpida
Considere un sistema por una lámpara, un observador y una puerta entre ambos. La lámpara tiene dos estados posibles : encendida, representada por 1, o apagada, representada por 0. Cuando la lámpara está encendida, el observador puede ver la luz a través de la puerta, dependiendo del estado de la puerta en ese momento: abierta, 1 , o cerrado, 0. tales estados son independientes del estado original de la lámpara.
Dejar una cadena de Markov que representa el estado de la lámpara, con valores en y deja ser una matriz de transición de probabilidad . Además, dejaser una secuencia de variables aleatorias independientes que representa los estados de la puerta, también tomando valores en, independiente de la cadena y tal que
dónde . Definir una nueva secuencia tal que
- para cada
Para determinar el último instante en el que el observador podría ver la lámpara encendida, es decir, para identificar el menor instante , con en el cual .
Usando un árbol de contexto es posible representar los estados pasados de la secuencia, mostrando cuáles son relevantes para identificar el siguiente estado.
La cadena estocástica es, entonces, una cadena con memoria de longitud variable, tomando valores en y compatible con el árbol de contexto probabilístico , dónde
Inferencias en cadenas de longitud variable
Dada una muestra , se puede encontrar el árbol de contexto apropiado utilizando los siguientes algoritmos.
El algoritmo de contexto
En el artículo Un sistema universal de compresión de datos , [1] Rissanen introdujo un algoritmo consistente para estimar el árbol de contexto probabilístico que genera los datos. La función de este algoritmo se puede resumir en dos pasos:
- Dada la muestra producida por una cadena con memoria de longitud variable, partimos del árbol máximo cuyas ramas son todas las candidatas a contextos de la muestra;
- A continuación, se cortan las ramas de este árbol hasta obtener el árbol más pequeño que se adapte bien a los datos. Decidir si el acortamiento del contexto se realiza a través de una función de ganancia determinada, como la razón de la probabilidad logarítmica.
Ser una muestra de un árbol probabilístico finito . Para cualquier secuencia con , es posible denotar por el número de ocurrencias de la secuencia en la muestra, es decir,
Rissanen primero construyó un candidato máximo de contexto, dado por , dónde y es una constante positiva arbitraria. La razón intuitiva de la elección de proviene de la imposibilidad de estimar las probabilidades de secuencia con longitudes mayores que basado en una muestra de tamaño .
A partir de ahí, Rissanen acorta el candidato máximo mediante el corte sucesivo de las ramas de acuerdo con una secuencia de pruebas basadas en la razón de probabilidad estadística. En una definición más formal, si bANnxk1b0 define el estimador de probabilidad de la probabilidad de transición por
dónde . Si, definir .
A , definir
dónde y
Tenga en cuenta que es la razón de la probabilidad logarítmica para probar la consistencia de la muestra con el árbol de contexto probabilístico contra la alternativa que es consistente con , dónde y difieren solo por un conjunto de nudos hermanos.
La longitud del contexto estimado actual se define por
dónde es cualquier constante positiva. Por fin, según Rissanen, [1] está el siguiente resultado. Dado de un árbol de contexto probabilístico finito , luego
Cuándo .
Criterio de información bayesiano (BIC)
El estimador del árbol de contexto por BIC con una constante de penalización Se define como
Criterio de maximizador más pequeño (SMC)
El criterio de maximizador más pequeño [3] se calcula seleccionando el árbol más pequeño τ de un conjunto de árboles campeones C de modo que
Ver también
Referencias
- ↑ a b c d 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 Bejenaro, G (2001). "Variaciones en árboles de sufijo probabilístico: modelado estadístico y predicción de familias de proteínas" . Bioinformática . 17 (5): 23–43. doi : 10.1093 / bioinformatics / 17.1.23 . PMID 11222260 .
- ^ a b Galves A, Galves C, García J, García NL, Leonardi F (2012). "Selección de árbol de contexto y recuperación de ritmos lingüísticos a partir de textos escritos" . The Annals of Applied Statistics . 6 (5): 186–209. arXiv : 0902.3619 . doi : 10.1214 / 11-AOAS511 .
- ^ Dubnov S, Assayag G, Lartillot O, Bejenaro G (2003). "Uso de métodos de aprendizaje automático para el modelado de estilos musicales". Computadora . 36 (10): 73–80. CiteSeerX 10.1.1.628.4614 . doi : 10.1109 / MC.2003.1236474 .
- ^ Galves A, Garivier A, Gassiat E (2012). "Estimación conjunta de modelos de árbol de contexto de intersección". Revista Escandinava de Estadística . 40 (2): 344–362. arXiv : 1102.0673 . doi : 10.1111 / j.1467-9469.2012.00814.x .
- ^ Galves A, Löcherbach E (2008). "Cadenas estocásticas con memoria de longitud variable" . Serie TICSP . 38 : 117-133.