« Bases de Datos en Gra… « || Inicio || » Redes Booleanas »

Cómo medir la Complejidad

Última modificación: 7 de Julio de 2015, y ha tenido 3284 vistas

¿Qué queremos decir con que un sistema dado muestra "comportamiento complejo"?, ¿podemos ofrecer medidas precisas para el grado de complejidad? En esta entrada se presenta un breve resumen sobre los diversos enfoques que ha habido para dar medidas concretas de esta complejidad.

La pregunta principal es... ¿podemos proporcionar una sola medida, o un pequeño número de medidas, que sean adecuadas para caracterizar el "grado de complejidad" de cualquier sistema dinámico? Esta pregunta, que cae dentro de la filosofía más que de las matemáticas, ha fascinado a los investigadores durante décadas y hasta el momento no hay respuestas definitivas, aunque sí aproximaciones a ellas.

La búsqueda de estas medidas de complejidad toca muchos temas interesantes de la teoría de sistemas dinámicos y ha dado lugar a una serie de potentes herramientas, aunque el objetivo original de desarrollar una medida que valga para medir la complejidad de cualquier sistema no parece realista y se ha eliminado de los objetivos científicos. Los sistemas dinámicos complejos muestran una gran variedad de comportamientos cualitativamente diferentes (que es una de las razones por las que la teoría de sistemas complejos es tan fascinante), y no parece apropiado intentar meter todos los sistemas complejos en una sola bolsa para medir su grado de complejidad siguiendo un único criterio.

La tarea de desarrollar una medida matemáticamente bien definida para la complejidad se ve obstaculizada por la falta de un objetivo claramente definido. Vamos a presentar algunos requisitos previos y algunas de las restricciones que deben postularse para obtener una medida de complejidad válida. Al final, sin embargo, es algo que depende de nuestra intuición el decidir si estos requisitos son apropiados o no para ello.

Complejidad frente a Aleatoriedad

Una propuesta habitual para medir la complejidad es la entropía informativa de Shannon: \(H[p]=-\sum_{x_i}p(x_i) log(p(x_i))\). Esta medida se anula cuando el sistema es regular (es decir, hay un solo evento probbale), lo que concuerda con nuestra intuición de que la complejidad es baja cuando no pasa nada, y sin embargo, es máxima para una dinámica completamente al azar.

Realmente, es una cuestión de punto de vista el que se considere que los sistemas aleatorios son complejos. Para algunas consideraciones, por ejemplo, cuando se trata de la "complejidad algorítmica" tiene sentido atribuir un grado de complejidad máximo a conjuntos completamente aleatorios de objetos. En general, sin embargo, se considera que las medidas de complejidad deben ser funciones cóncavas que alcanzan sus mínimos tanto para comportamientos regulares como para secuencias puramente aleatorias.

La complejidad de los sistemas formados por muchas componentes

Habitualmente, se considera que la complejidad debe ser una cantidad positiva, como ocurre con la entropía. Pero, ¿cómo se debe comportar respecto al tamaño del sistema?, ¿debe crecer con él, o debería ser independiente del tamaño?, ¿y si consideramos la agrupación de muchos sistemas idénticos e independientes? Intuitivamente, se podría esperar que no se ganara complejidad cuando se considera el comportamiento de un conjunto de \(N\) sistemas dinámicos independientes e idénticos; pero, por otro lado, no podemos descartar que la interacción de \(N\) sistemas dinámicos debería mostrar un comportamiento cada vez más complejo si se aumenta el número de subsistemas. Por ejemplo, consideramos intuitivamente que la dinámica global del cerebro debe ser más compleja que los patrones que se producen entre las neuronas individuales.

No existe una manera sencilla de resolver este dilema en la búsqueda de una sola medida de complejidad que sirva para todos los sistemas complejos, ya que parece que ambas opciones tienen aplicabilidad dependiendo del caso concreto que estemos analizando.

Complejidad y predecibilidad

Se pueden construir medidas de complejidad interesantes haciendo uso de herramientas estadísticas, por medio de la generalización de conceptos como la entropía de la información y la información mutua. Para ejemplificarlo, vamos a considerar series temporales generadas a partir de un conjunto finito de símbolos. Por supuesto, se puede cambiar el papel que juega el tiempo por el de cualquier otro parámetro, por ejemplo el espacio, si estuvieramos interesados en el estudio de la complejidad de estructuras espaciales.

Procesos Dinámicos Estacionarios

Como requisito previo, vamos a trabajar con procesos dinámicos estacionarios, es decir procesos dinámicos que no cambian su comportamiento ni sus propiedades estadísticas cualitativamente con el tiempo. En la práctica esto implica que la series temporales consideradas, generadas por algún sistema dinámico, tiene un horizonte de tiempo finito, es decir, para grandes valores de \(t\) las correlaciones entre los estados del sistema caen de forma exponencial. Ha de tenerse en cuenta que este requisito puede no ser válido para sistemas dinámicos críticos, que se caracterizan por correlaciones dinámicas y estadísticas que decaen muy lentamente, como una potencia inversa del tiempo.

Dado un conjunto de símbolos \(X\), y una serie temporal sobre \(X\), \(x_n, x_{n-1}, \dots, x_2, x_1\),  con \(x_i = x(t_i)\in X\), podemos definir la distribución de probabilidad conjunta, como \(p_n: p(x_n, ..., x_1)\).

Al estar trabajando con procesos dinámicos estacionarios, no tiene sentido tomar los valores temporales en un rango superior al horizonte de tiempo finito del sistema, es decir, aquel por encima del cual ya no hay correlación entre los valores de la dinámica.

Si consideramos la entropía de la distribución anterior:

\[H[p_n]=-\sum_{x_n,\dots,x_1\in X} p(x_n,\dots,x_1) log(p(x_n,\dots,x_1))\]

(que debe medirse sobre un conjunto de series temporales de longitud mayor o igual a \(n\)). A partir de estas entropías, podemos medir la densidad límite de ellas como:

\[h_\infty = \lim_{n\rightarrow \infty} \frac{1}{n}H[p_n]\]

que existe para los procesos dinámicos estacionarios (por tener horizonte de tiempo finito). De alguna forma, esta densidad mide el número medio de bits por unidad de tiempo que son necesarios para codificar las series temporales estadísticamente.

Se define el exceso de entropía como

\[E=\lim_{n\rightarrow \infty} (H[p_n]-nh_\infty)\]

De alguna forma, podemos expresar:

\(H[p_n] = n h_\infty + E + O(\frac{1}{n})\) cuando \(n\rightarrow \infty\)

Se puede probar que, en el caso de los procesos dinámicos estacionarios, el exceso de entropía E es positiva porque \(H[p_n]\) es una función cóncava en \(n\). Desde un punto de vista práctico, podemos aproximar el exceso de entropía por:

\(h_\infty=\lim_{n\rightarrow \infty} h_n\), donde \(h_n=H[p_{n+1}]-H[p_n]\)

Se puede comprobar que el exceso de entropía se anula tanto para los sistemas ordenados como para los completamente aleatorios, por lo que a veces se puede ver como una medida de complejidad más adecuada que la entropía.

El exceso de entropía es una buena herramienta para el análisis de series temporales, verificando varios criterios básicos de las medidas de complejidad, y que permite muchas posibles ampliaciones, como por ejemplo para los sistemas que muestran actividad dinámica estructurada tanto en el tiempo como en el dominio espacial. En contra, debe decirse que el exceso de entropía es muy difícil de evaluar numéricamente, por lo que su ámbito de aplicación está limitada a los estudios teóricos.

Complejidad algorítmica y generativa

Hasta ahora hemos presentado los enfoques descriptivos que hacen uso de métodos estadísticos para la construcción de medidas de complejidad. Pero, además de éstos, podemos estar interesados en el modelado del proceso generativo que da lugar al sistema complejo que es objeto de nuestro estudio. En este caso, la pregunta sería: ¿cuál es el modelo más simple que es capaz de explicar los datos observados?

A diferencia de lo que se ha visto en las partes anteriores, ahora vamos a tratar con objetos individuales compuestos por un número finito de \(n\) símbolos, como podrían ser las cadenas

\(0000000000000000000000\), \(0010000011101001011001\)

La pregunta es entonces: ¿qué modelo dinámico puede generar una cadena dada de símbolos? En particular, nos centramos en reproducir cadenas de bits por medios computacionales.

Como hay muchos lenguajes de programación con los que podríamos intentar reproducir las cadenas de bits, es necesario tomar un sistemas de computación como referencia para poder medir de manera uniforma cuán complicado resulta generarlas. En este caso, suele ser habitual tomar como referencia las "máquinas de Turing".

La definición exacta de qué es una máquina de Turing no es relevante en este momento (aunque es de importancia fundamental si queremos comprender de verdad qué se entiende por reproducir computacionalmente), y nos quedaremos con que es esencialmente una máquina de estados finitos trabajando sobre una conta de datos haciendo uso de un conjunto de instrucciones básicas. La máquina de Turing juega un papel central en la teoría de la computabilidad, por ejemplo, cuando uno está interesada en analizar lo difícil que es encontrar la solución a un determinado conjunto de problemas.

Complejidad Algorítmica

La noción de complejidad algorítmica trata de encontrar una respuesta a la cuestión de lo difícil que es reproducir una serie temporal dada en ausencia de conocimiento previo: la "complejidad algorítmica" (también llamada "complejidad Kolmogorov") de una cadena de bits es la longitud del programa más corto que produce dicha cadena dada de bits y luego se detiene.

Existe un resultado, llamado la tesis de Church-Turing, que asegura que cualquier modelo de computación habitual tiene la misma potencia computacional que las máquinas de Turing, por lo que al fijar uno de los modelos de computación como modelo de referencia (en nuestro caso, las máquinas de Turing) no perdemos fuerza en la definición anterior y, esencialmente, no depende del modelo elegido.

La complejidad algorítmica es un concepto muy potente para consideraciones teóricas en el contexto de la computabilidad óptima, pero tiene dos inconvenientes desde el punto de vista de las medida de complejidad que buscamos para sistemas complejos: no es computable y asigna la complejidad máxima a las secuencias aleatorias, ya que la única forma de generar números aleatorios por medio de máquinas de Turing (o cualquier modelo equivalente) sería haciendo uso de un código que tendría una longitud infinita. Esta es la razón por la que no es posible escribir programas que generen números aleatorios puros, y los códigos actuales sólo producen "números pseudo-aleatorios", que verifican ciertas propiedades estadísticas. Por tanto, la complejidad algorítmica entra en conflicto con el postulado buscado en las medidas de complejidad de anularse en los estados puramente aleatorios.

Complejidad determinista

Hay una gran línea de investigación tratando de entender el mecanismo generativo del comportamiento complejo no algorítmicamente sino desde la perspectiva de la teoría de sistemas dinámicos, en particular haciendo uso de sistemas deterministas. La pregunta en este caso sería: en ausencia de ruido, ¿cuáles son las características necesarias para producir trayectorias interesantes y complejas?

En este contexto, son de interés la sensibilidad a las condiciones iniciales que tienen los sistemas que presentan una transición entre estados caóticos y regulares en el espacio de fases; el efecto de las bifurcaciones y atractores no triviales (como son los atractores extraños); las consecuencias de la retroalimentación; y las tendencias hacia la sincronización y autoorganización.

Complejidad y Emergencia

Intuitivamente, atribuimos un alto grado de complejidad a la cambiante estructura que emerge de reglas subyacentes posiblemente simples. Esta relación entre complejidad y "emergencia" es, sin embargo, muy difícil de formalizar matemáticamente, y hasta la fecha no se ha propuesto ninguna medida precisa para medir esta emergencia.

« Bases de Datos en Gra… « || Inicio || » Redes Booleanas »