An information-theoretic approach to higher-order Markov processes: Theory and applications

Abstract

[eng] Accurately modeling the temporal evolution of a stochastic process, which is essential in many fields in complex systems, requires a thorough understanding of the correlations in the system. This is particularly relevant for higher-order Markov chains, where the likelihood to make a transition to a future state only depends on a finite number of past outcomes. However, without previous knowledge of the system dynamics, it is not straightforward to quantify these temporal dependencies. In this thesis, we demonstrate that information theory provides a comprehensive framework for describing correlations within a system. In particular, the block entropy, an extension of Shannon entropy defined for consecutive repetitions of the process, and its discrete derivatives, are shown to be effective tools for quantifying step by step the influence of previous outcomes in the evolution of the system. Within this approach, we redefine the order, or memory, of a process completely in terms of information-theoretic measures, allowing us to develop a method to determine this memory value. Adapting the proposed method to data samples of finite length requires estimating the entropy, which led us to introduce two new estimators designed to account for correlations in the data, and to compare these estimators with other well-known methods when applied to Markovian sequences. Combining the theoretical results that link the memory of a process with information theory, the entropy estimator that we find to have an overall minimum mean squared error when acting on correlated sequences and statistical methods from hypothesis testing, we develop a memory estimator that shows high accuracy and is independent on model selection. Subsequently, we apply the previous results to two real-world datasets. First, we analyze the correlations in sequences of precipitation occurrence across Spain, observing that the strength of these correlations varies seasonally, being stronger in winter than in summer, and across regions, with more pronounced temporal dependencies observed in Northern Spain. The second application involves analyzing correlations within sequences of parts of speech for a large number of contemporary languages, observing that the syntactic structure of these languages is effectively captured by the probability distribution of three consecutive parts of speech. Defining a distance metric between languages based on these distributions, we identify well-known language families and groups, and we observe that languages that are geographically closer tend to have more similar syntactic structures than those located further apart. Overall, through a combination of theoretical and statistical methods, this thesis develops a framework for quantifying and analyzing correlations and memory effects in stochastic processes using information theory, demonstrating the effectiveness of these methods in the analysis of real-world data.

[cat] Per modelar amb precisió l'evolució temporal d'un procés estocàstic, quelcom essencial en molts camps dels sistemes complexos, es requereix una comprensió profunda de les correlacions del sistema. Això és particularment rellevant per a les cadenes de Markov d'ordre alt, on la probabilitat de dur a terme una transició a un estat futur depèn únicament d'un nombre finit de resultats passats. No obstant això, sense un coneixement previ de la dinàmica del sistema, no és senzill quantificar aquestes dependències temporals. En aquesta tesi, demostrem que la teoria de la informació proporciona un marc integral per descriure les correlacions dins d'un sistema. En particular, l'entropia de bloc, una extensió de l'entropia de Shannon definida per a repeticions consecutives del procés, i les seves derivades discretes, es mostren com a eines efectives per quantificar, pas a pas, la influència dels resultats previs en l'evolució del sistema. Dins d'aquest enfocament, redefinim l'ordre, o memòria, d'un procés completament en termes de mesures de teoria de la informació, cosa que ens permet desenvolupar un mètode per determinar aquest valor de memòria. Si volem adaptar el mètode proposat a seqüències de dades de longitud finita, necessitem estimar l'entropia, cosa que ens porta a introduir dos nous estimadors dissenyats per tenir en compte les correlacions en les dades i a comparar aquests estimadors amb altres mètodes coneguts quan s'apliquen a seqüències markovianes. Combinant els resultats teòrics que vinculen la memòria d'un procés amb la teoria de la informació, l'estimador d'entropia que hem trobat que té, en general, un error quadràtic mitjà mínim quan s'aplica a seqüències correlacionades i mètodes estadístics de proves d'hipòtesis, desenvolupem un estimador de la memòria que mostra una alta precisió i no depèn de cap selecció de models. A continuació, apliquem els resultats anteriorment assolits a dos conjunts de dades empíriques. En primer lloc, analitzem les correlacions en seqüències de precipitacions en Espanya, observant que la intensitat d'aquestes correlacions varia estacionalment, sent més fortes a l'hivern que a l'estiu, i entre regions, amb dependències temporals més marcades al nord d'Espanya. La segona aplicació implica l'anàlisi de correlacions en seqüències de categories gramaticals en un gran nombre de llengües contemporànies, observant que l'estructura sintàctica d'aquestes llengües es descriu de manera efectiva mitjançant la distribució de probabilitat de tres categories gramaticals consecutives. Definint una mètrica de distància entre llengües basada en aquestes distribucions, identifiquem famílies i grups de llengües ben coneguts i observem que les llengües geogràficament més properes tendeixen a tenir estructures sintàctiques més similars que aquelles situades més lluny. En conjunt, mitjançant una combinació de mètodes teòrics i estadístics, aquesta tesi desenvolupa un marc per quantificar i analitzar les correlacions i efectes de memòria en processos estocàstics utilitzant la teoria de la informació, demostrant l'efectivitat d'aquests mètodes en l'anàlisi de dades reals.

[spa] Modelar con precisión la evolución temporal de un proceso estocástico, algo esencial en muchos campos de los sistemas complejos, requiere una comprensión profunda de las correlaciones del sistema. Esto es particularmente relevante para las cadenas de Markov de orden alto, donde la probabilidad de llevar a cabo una transición a un estado futuro depende únicamente de un número finito de resultados pasados. Sin embargo, sin un conocimiento previo de la dinámica del sistema, no es sencillo cuantificar estas dependencias temporales. En esta tesis, demostramos que la teoría de la información proporciona un marco integral para describir las correlaciones dentro de un sistema. En particular, la entropía de bloque, una extensión de la entropía de Shannon definida para repeticiones consecutivas del proceso, y sus derivadas discretas, se muestran como herramientas efectivas para cuantificar, paso a paso, la influencia de los resultados previos en la evolución del sistema. Dentro de este enfoque, redefinimos el orden, o memoria, de un proceso completamente en términos de medidas de teoría de la información, lo cual nos permite desarrollar un método para determinar este valor de la memoria. Para adaptar el método propuesto a secuencias de datos de longitud finita, se necesita estimar la entropía, lo que nos lleva a introducir dos nuevos estimadores diseñados para tener en cuenta las correlaciones en los datos y a comparar estos estimadores con otros métodos conocidos cuando se aplican a secuencias markovianas. Combinando los resultados teóricos que vinculan la memoria de un proceso con la teoría de la información, el estimador de entropía que encontramos que tiene, en general, un error cuadrático medio mínimo al ser aplicado en secuencias correlacionadas y métodos estadísticos de pruebas de hipótesis, desarrollamos un estimador de la memoria que muestra una precisión alta y no depende de ninguna selección de modelos. A continuación, aplicamos los resultados anteriormente alcanzados a dos conjuntos de datos empíricos. En primer lugar, analizamos las correlaciones en secuencias de precipitaciones en España, observando que la intensidad de estas correlaciones varía estacionalmente, siendo más fuertes en invierno que en verano, y entre regiones, con dependencias temporales más marcadas en el norte de España. La segunda aplicación implica el análisis de correlaciones en secuencias de categorías gramaticales en un gran número de lenguas contemporáneas, observando que la estructura sintáctica de estas lenguas se describe de manera efectiva mediante la distribución de probabilidad de tres categorías gramaticales consecutivas. Definiendo una métrica de distancia entre lenguas basada en estas distribuciones, identificamos familias y grupos de lenguas bien conocidos y observamos que las lenguas geográficamente más cercanas tienden a tener estructuras sintácticas más similares que aquellas ubicadas más lejos. En conjunto, a través de una combinación de métodos teóricos y estadísticos, esta tesis desarrolla un marco para cuantificar y analizar las correlaciones y efectos de memoria en procesos estocásticos utilizando la teoría de la información, demostrando la efectividad de estos métodos en el análisis de datos reales.