Complejidad (teoría de la información)

La complejidad de la fluctuación de la información es un valor teórico de la información definido como la fluctuación de la información con respecto a la entropía de la información . Se deriva de las fluctuaciones en la prevalencia del orden y el caos en un sistema dinámico y se utiliza en varios campos del conocimiento para medir la complejidad . La teoría fue presentada en el trabajo de Bates y Shepard en 1993 [1] .

Definición

La complejidad de la fluctuación de la información de un sistema dinámico discreto es una función de la distribución de probabilidad de los estados de este sistema sujeto a entradas de datos aleatorias. El objetivo de controlar un sistema con una rica fuente de información, como un generador de números aleatorios o una señal de ruido blanco , es explorar la dinámica interna del sistema de la misma manera que se usa un pulso rico en frecuencia en el procesamiento de señales .

Si el sistema tiene estados posibles y se conocen las probabilidades de los estados , entonces su entropía de información es igual a ${\ estilo de texto N}$ ${\ estilo de texto p_ {i}}$

\mathrm {H} =\sum_{i=1}^{N}p_{i}I_{i}=-\sum_{i=1}^{N}p_{i}\log p_ {i},

donde está la información del propio estado . ${\textstyle I_{i}=-\log p_{i}}$ ${\ estilo de texto i}$

La complejidad de la fluctuación de la información de un sistema se define como la desviación estándar o la fluctuación de su valor medio : ${\ estilo de texto I}$ ${\ estilo de texto \ mathrm {H} }$

{\displaystyle \sigma _{I}={\sqrt {\sum _{i=1}^{N}p_{i}(I_{i}-\mathrm {H} )^{2))}={ \sqrt {\sum _{i=1}^{N}p_{i}I_{i}^{2}-\mathrm {H} ^{2))))

\sigma_{I}={\sqrt {\sum_{i=1}^{N}p_{i}\log ^{2}p_{i}-{\Biggl (}\sum_{ i=1}^{N}p_{i}\log p_{i}{\Biggr)}^{2}}}.

La fluctuación de la información de estado es cero en un sistema máximamente desordenado con todo ; el sistema simplemente simula entradas de datos aleatorias. también es cero cuando el sistema está perfectamente ordenado y tiene un solo estado fijo , independientemente de las entradas. es distinto de cero entre estos dos extremos cuando tanto los estados de alta probabilidad como los de baja probabilidad son posibles para llenar el espacio de estados. ${\ estilo de visualización \ sigma _ {I}}$ $p_{i}=1/N$ ${\ estilo de visualización \ sigma _ {I}}$ ${\ estilo de visualización (p_ {1} = 1)}$ ${\ estilo de visualización \ sigma _ {I}}$

Las fluctuaciones en la información proporcionan memoria y computación

A medida que un sistema dinámico complejo se desarrolla en el tiempo, pasa de un estado a otro. Cómo se producen estas transiciones depende de estímulos externos de forma irregular. En algunos casos, el sistema puede ser más sensible a los estímulos externos (inestable), mientras que en otros puede ser menos sensible (estable). Si un estado particular tiene varios estados siguientes posibles, la información externa determina cuál será el siguiente y el sistema obtiene esta información siguiendo una determinada trayectoria en el espacio de estado. Pero si varios estados diferentes conducen al mismo estado siguiente, al entrar en él, el sistema pierde información sobre qué estado lo precedió. Así, a medida que evoluciona con el tiempo, un sistema complejo presenta ganancias y pérdidas de información alternas. Las alternancias o fluctuaciones de información equivalen a recordar y olvidar, el almacenamiento temporal de información o memoria, esta es una característica esencial de los cálculos no triviales.

La ganancia o pérdida de información que acompaña a las transiciones de estado puede asociarse con su propia información de estado. La ganancia neta de información durante la transición de un estado a otro es la información obtenida al salir del estado menos la información perdida al entrar al estado : $i$ $j$ $i$ $j$

\Gamma _{ij}=-\log p_{i\rightarrow j}+\log p_{i\leftarrow j}.

Esta es la probabilidad condicional directa de que si el estado actual es , entonces el estado siguiente será y es la probabilidad condicional inversa de que si el estado actual es , entonces el estado anterior fue . Las probabilidades condicionales están relacionadas con la probabilidad de transición , la probabilidad de que ocurra una transición de estado a estado , por: ${\textstyle p_{i\rightarrow j))$ $i$ $j$ ${\displaystyle p_{i\leftarrow j))$ $j$ $i$ $p_{{ij}}$ $i$ $j$

p_{ij}=p_{i}p_{i\rightarrow j}=p_{j}p_{i\leftarrow j}.

Eliminando las probabilidades condicionales, obtenemos:

\Gamma _{ij}=-\log(p_{ij}/p_{i})+\log(p_{ij}/p_{j})=\log p_{i}-\log p_{ j}=I_{j}-I_{i}.

Por lo tanto, la información neta que obtiene el sistema como resultado de la transición depende únicamente del aumento de la información de estado desde el estado inicial hasta el estado final. Se puede demostrar que esto es cierto incluso para varias transiciones consecutivas [1] .

La fórmula se asemeja a la relación entre la fuerza y la energía potencial . es similar a la energía potencial , y es la fuerza en la fórmula . La información externa "empuja" el sistema "hacia arriba", a un estado con un mayor potencial de información para la preservación de la memoria, al igual que empujar un cuerpo con cierta masa cuesta arriba, a un estado con un mayor potencial gravitatorio, conduce a la acumulación de energía. La cantidad de energía almacenada depende únicamente de la altura final y no del camino cuesta arriba. Asimismo, la cantidad de información almacenada es independiente del camino de transición entre dos estados. Una vez que un sistema alcanza un estado poco común de alto potencial de información, puede "recaer" en un estado normal, perdiendo información previamente almacenada. ${\ estilo de visualización \ Gamma = \ Delta I}$ $yo$ $E_{p}$ $\Gama$ $\mathbf {F}$ $\mathbf {F} ={\nabla E_{p))$

Puede ser útil calcular la desviación estándar de su media (que es cero), es decir, la fluctuación de la ganancia de información neta [1] , pero tiene en cuenta los ciclos de memoria de espacio de estado de transición múltiple y, por lo tanto, debería ser una forma más precisa indicador de la potencia de procesamiento del sistema. Además, es más fácil de calcular, ya que puede haber muchas más transiciones que estados. $\Gama$ ${\ estilo de visualización \ sigma _ {\ gamma}}$ ${\ estilo de visualización \ sigma _ {I}}$ ${\ estilo de visualización \ sigma _ {I}}$

Caos y orden

Un sistema dinámico que es sensible a la información externa (inestable) exhibe un comportamiento caótico , mientras que un sistema que es insensible a la información externa (estable) exhibe un comportamiento ordenado. Bajo la influencia de una rica fuente de información, un sistema complejo exhibe ambos comportamientos, oscilando entre ellos en un equilibrio dinámico. El grado de fluctuación se mide cuantitativamente con ; captura la alternancia del predominio del caos y el orden en un sistema complejo a medida que se desarrolla con el tiempo. ${\ estilo de visualización \ sigma _ {I}}$

Ejemplo: una variante del autómata celular elemental según la regla 110

Se demuestra que una variante del autómata celular elemental según la regla 110 es capaz de realizar cálculos universales . La prueba se basa en la existencia e interacción de configuraciones celulares conectadas y autoconservadas conocidas como "planeadores" o " naves espaciales ", el fenómeno de emergencia , que implica la capacidad de grupos de células autómatas para recordar que un planeador pasa a través de ellas. Por lo tanto, debe esperarse que se produzcan bucles de memoria en el espacio de estado, como resultado de la alternancia de ganancia y pérdida de información, inestabilidad y estabilidad, caos y orden.

Considere un grupo de tres celdas adyacentes de un autómata celular que obedece la regla 110:extremo-centro-extremo. El siguiente estado de la celda central depende de su estado actual y de las celdas hoja, como se especifica en la regla:

Autómata celular elemental regla 110.

grupo de 3 células	1-1-1	1-1-0	1-0-1	1-0-0	0-1-1	0-1-0	0-0-1	0-0-0
siguiente celda central	0	una	una	0	una	una	una	0

Para calcular la complejidad de la fluctuación de la información de este sistema, se conectaría una celda controladora a cada extremo de un grupo de 3 celdas para proporcionar un estímulo externo aleatorio, p.controlador→extremo-centro-extremo←controlador, para que la regla se pueda aplicar a las dos celdas finales. Luego necesita determinar cuál es el próximo estado para cada estado actual posible y para cada combinación posible de contenido de celda de controlador para calcular las probabilidades condicionales directas.

El diagrama de estado de este sistema se muestra a continuación. En él, los círculos representan estados y las flechas representan transiciones entre estados. Los ocho estados de este sistema, desde1-1-1antes de0-0-0están numerados con equivalentes decimales de los contenidos de 3 bits de un grupo de 3 celdas: del 7 al 0. Cerca de las flechas de transición, se muestran los valores de las probabilidades condicionales directas. El esquema muestra la variabilidad en la divergencia y convergencia de las flechas, lo que corresponde a la variabilidad en el caos y el orden, la sensibilidad y la insensibilidad, la adquisición y pérdida de información externa de las células conductoras.

Las probabilidades condicionales directas están determinadas por la proporción de los posibles contenidos de la celda conductora que gobierna una transición particular. Por ejemplo, para cuatro combinaciones posibles del contenido de dos celdas de control, el estado 7 conduce a los estados 5, 4, 1 y 0, por lo que , y son 1/4 o 25 %. Del mismo modo, el estado 0 conduce a los estados 0, 1, 0 y 1, por lo que corresponde 1/2 , o 50% . Y así. $p_{7\rightarrow 5}$ $p_{7\rightarrow 4}$ $p_{7\rightarrow 1}$ $p_{7\rightarrow 0}$ $p_{0\rightarrow 1}$ $p_{0\rightarrow 0}$

Las probabilidades de estado están relacionadas por la fórmula

{\displaystyle p_{j}=\sum _{i=0}^{7}p_{i}p_{i\rightarrow j))

{\ estilo de visualización \ suma _ {i = 0} ^ {7} p_ {i} = 1.}

Estas ecuaciones algebraicas lineales se pueden resolver manualmente o con un programa de computadora para probabilidades de estado, con los siguientes resultados:

p0 _	p1_ _	p2_ _	pág . 3	p4_ _	p5 _	p6 _	pág . 7
2/17	2/17	1/34	5/34	2/17	2/17	2/17	4/17

La entropía y la complejidad de la información se pueden calcular a partir de las probabilidades de estado:

\mathrm {H} =-\sum_{i=0}^{7}p_{i}\log_{2}p_{i}=2,86

murciélago,

\sigma_{I}={\sqrt {\sum_{i=0}^{7}p_{i}\log_{2}^{2}p_{i}-\mathrm {H} ^{2}}}=0,56

un poco.

Cabe señalar que la máxima entropía posible para ocho estados es igual a un bit, lo que corresponde al caso en que los ocho estados son igualmente probables, con probabilidades 1/8 (caótico). Por lo tanto, la regla 110 tiene una entropía o uso de estado relativamente alta de 2,86 bits. Sin embargo, esto no descarta una fluctuación significativa de la información de estado con respecto a la entropía y, en consecuencia, una gran complejidad. Mientras que la máxima entropía descartaría la complejidad. $\ log _ {2} 8 = 3$

Se puede usar un método alternativo para obtener probabilidades de estado cuando el método analítico descrito anteriormente no es factible. Consiste en conducir el sistema a través de sus entradas (células conductoras) con una fuente aleatoria durante muchas generaciones y observar empíricamente las probabilidades de estado. Cuando se hace con simulaciones por computadora durante 10 millones de generaciones, los resultados son los siguientes: [2]

Variables de información para un autómata celular elemental según la regla 110

número de celdas	3	cuatro	5	6	7	ocho	9	diez	once	12	13
$\mathrm{H}$ (un poco)	2.86	3.81	4.73	5.66	6.56	7.47	8.34	9.25	10.09	10.97	11.78
${\ estilo de visualización \ sigma _ {I}}$ (un poco)	0,56	0,65	0.72	0.73	0.79	0.81	0.89	0.90	1.00	1.01	1.15
$\sigma _{I}/\mathrm {H}$	0.20	0.17	0.15	0.13	0.12	0.11	0.11	0.10	0.10	0.09	0.10

Dado que ambos parámetros, y , aumentan con el tamaño del sistema, para una mejor comparación de sistemas de diferentes tamaños, se propone una relación adimensional , relativa Información-fluctuación complejidad. Tenga en cuenta que los resultados empíricos y analíticos son consistentes para un autómata de 3 celdas. $\mathrm{H}$ ${\ estilo de visualización \ sigma _ {I}}$ $\sigma _{I}/\mathrm {H}$

En el trabajo de Bates y Shepard [1] , se calcula para todas las reglas de los autómatas celulares elementales, y se notó que aquellos que exhiben "planeadores" de movimiento lento y posiblemente objetos estacionarios, por ejemplo, la regla 110, están estrechamente asociados con valores grandes de . Por lo tanto, puede usarse como filtro al elegir reglas capaces de computación universal, lo cual es tedioso de probar. ${\ estilo de visualización \ sigma _ {I}}$ ${\ estilo de visualización \ sigma _ {I}}$ ${\ estilo de visualización \ sigma _ {I}}$

Aplicaciones

Aunque la derivación de la fórmula de complejidad de la fluctuación de la información se basa en las fluctuaciones de la información en un sistema dinámico, la fórmula en sí depende solo de las probabilidades de estado y, por lo tanto, también se puede aplicar a cualquier distribución de probabilidad, incluidas las derivadas de imágenes estáticas o texto.

A lo largo de los años, el artículo original [1] ha sido referenciado por investigadores de muchos campos diferentes: teoría de la complejidad [3] , ciencia de sistemas complejos [4] , dinámica caótica [5] , ingeniería ambiental [6] , complejidad ecológica [7] , análisis de series temporales ecológicas [8] , resiliencia de los ecosistemas [9] , contaminación del aire [10] y del agua [11] , análisis hidrológico de ondículas [12] , modelado de flujos de agua en el suelo [13] , humedad del suelo [14] , cuenca hidrográfica escorrentía [15] , profundidad de las aguas subterráneas [16] , control del tráfico aéreo [17] , patrón de flujo [18] , topología [19] , pronóstico de mercado de los precios de los metales [20] y la electricidad [21] , informática de la salud [22] , cognición humana [23] , cinemática de la marcha humana [24] neurología [25] análisis EEG [26] análisis del habla [27] educación [28] inversión [29] estética [30] .

Enlaces

↑ 1 2 3 4 5 John E. Bates, Harvey K. Shepard. Midiendo la complejidad utilizando la fluctuación de la información (inglés) // Physics Letters A. — 1993-01-18. — vol. 172 , edición. 6 _ — P. 416–425 . — ISSN 0375-9601 . -doi : 10.1016 / 0375-9601(93)90232-O .
↑ Bates, John E. Medición de la complejidad mediante la fluctuación de la información: un tutorial . Puerta de investigación (30 de marzo de 2020). (indefinido)
↑ Harald Atmanspacher. Corte cartesiano, corte de Heisenberg y el concepto de complejidad // World Futures. - 1997-09-01. - T. 49 , n. 3-4 . — S. 333–355 . — ISSN 0260-4027 . -doi : 10.1080/ 02604027.1997.9972639 .
↑ Cosma Rohilla Shalizi. Métodos y técnicas de la ciencia de sistemas complejos: una descripción general // Ciencia de sistemas complejos en biomedicina / Thomas S. Deisboeck, J. Yasha Kresh. — Boston, MA: Springer EE. UU., 2006. — P. 33–114 . — ISBN 978-0-387-33532-2 . -doi : 10.1007 / 978-0-387-33532-2_2 .
↑ Renate Wackerbauer. Estabilización inducida por ruido del sistema Lorenz // Physical Review E. - 1995-11-01. - T. 52 , n. 5 . — S. 4745–4749 . -doi : 10.1103/ PhysRevE.52.4745 .
↑ Singh, Vijay P. Teoría de la entropía y su aplicación en ingeniería ambiental y del agua : [ ing. ] . — John Wiley & Sons, 2013-01-10. — ISBN 978-1-118-42860-3 .
↑ Parrot, Lael (2010-11-01). “Medición de la complejidad ecológica” . Indicadores ecológicos _ ]. 10 (6): 1069-1076. DOI : 10.1016/j.ecolind.2010.03.014 . ISSN 1470-160X .
↑ Holger Lange. Análisis de series temporales en ecología (inglés) // eLS. - Sociedad Americana del Cáncer, 2006. - ISBN 978-0-470-01590-2 . -doi : 10.1038/ npg.els.0003276 .
↑ Wang, Chaojun; Zhao, Hongrui (2019-04-18). “Análisis de datos de series temporales de teledetección para fomentar la sostenibilidad de los ecosistemas: uso de la entropía de la información temporal” . Revista Internacional de Teledetección . 40 (8): 2880-2894. DOI : 10.1080/01431161.2018.1533661 . ISSN 0143-1161 .
↑ Klemm, Otto; Lange, Holger (1999-12-01). “Tendencias de la contaminación del aire en las montañas Fichtelgebirge, Baviera” . Investigación en Ciencias Ambientales y Contaminación ]. 6 (4): 193-199. DOI : 10.1007/BF02987325 . ISSN 1614-7499 .
↑ Wang, Kang; Lin, Zhongbing (2018). “Caracterización de la contaminación de fuentes difusas en ríos a diferentes escalas espaciales” . Revista Agua y Medio Ambiente ]. 32 (3): 453-465. DOI : 10.1111/wej.12345 . ISSN 1747-6593 .
↑ Labat, David (2005-11-25). "Avances recientes en análisis de wavelet: Parte 1. Una revisión de conceptos" . Revista de hidrología ]. 314 (1): 275-288. DOI : 10.1016/j.jhydrol.2005.04.003 . ISSN 0022-1694 .
↑ Pachepsky, Yakov; Guber, Andrei; Jacques, Diederik; Simunek, Jiri; Van Genuchten, Marthinus Th.; Nicholson, Thomas; Cady, Ralph (2006-10-01). “Contenido de información y complejidad de los flujos de agua del suelo simulados” . Geoderma . Geometría Fractal Aplicada al Suelo y Sistemas Jerárquicos Relacionados - Fractales , Complejidad y Heterogeneidad ]. 134 (3): 253-266. DOI : 10.1016/j.geoderma.2006.03.003 . ISSN 0016-7061 .
↑ Kumar, Sujay V.; Dirmeyer, Paul A.; Peters-Lidard, Christa D.; Bindlish, Rajat; Bolten, John (2018-01-01). “Evaluación teórica de la información de las recuperaciones satelitales de humedad del suelo” . Detección Remota del Medio Ambiente ]. 204 : 392-400. DOI : 10.1016/j.rse.2017.10.016 . HDL : 2060/20180003069 . ISSN 0034-4257 .
↑ Hauhs, Michael; Lange, Holger (2008). “Clasificación de la escorrentía en las cabeceras de captación: ¿un problema físico?” . Brújula de geografía _ ]. 2 (1): 235-254. DOI : 10.1111/j.1749-8198.2007.00075.x . ISSN 1749-8198 .
↑ Liu, Meng; Liu Dong; Liu, Le (2013-09-01). “Investigación de la complejidad de las series regionales de profundidad de aguas subterráneas basadas en la entropía multiescala: un estudio de caso de la sucursal de Jiangsanjiang en China” . ciencias ambientales de la tierra ]. 70 (1): 353-361. DOI : 10.1007/s12665-012-2132-y . ISSN 1866-6299 .
↑ Xing, Jing; Manning, Carol A. (abril de 2005). “Complejidad y Automatización de Pantallas de Control de Tránsito Aéreo : Revisión y Análisis de Literatura ” ].
↑ Wang, Kang; Li, Li (noviembre de 2008). “Caracterización de patrones de flujo heterogéneos utilizando medidas de información” . 2008 Primera Conferencia Internacional sobre Redes Inteligentes y Sistemas Inteligentes : 654-657. DOI : 10.1109/ICINIS.2008.110 .
↑ Javaheri Javid, Mohammad Ali; Alghamdi, Wajdi; Zimmer, Robert y al-Rifaie, Mohammad Majid (2016), Bi, Yaxin; Kapoor, Supriya & Bhatia, Rahul, eds., Un análisis comparativo de la detección de simetrías en topología toroidal , Estudios en inteligencia computacional, Springer International Publishing, p. 323–344, ISBN 978-3-319-33386-1 , doi : 10.1007/978-3-319-33386-1_16 , < https://doi.org/10.1007/978-3-319-33386-1_16 > . Consultado el 7 de abril de 2020.
↑ Él, Kaijian; Lu, Xingjing; Zou, Yingchao; Keung Lai, pariente (2015-09-01). “Predicción de los precios de los metales con una metodología multiescala basada en curvas” . Política de recursos _ ]. 45 : 144-150. DOI : 10.1016/j.resourpol.2015.03.011 . ISSN 0301-4207 .
↑ Él, Kaijian; Xu, Yang; Zou, Yingchao; Tang, Ling (2015-05-01). “Previsiones de precios de la electricidad utilizando un enfoque basado en la eliminación de ruido de Curvelet” . Physica A: Mecánica Estadística y sus Aplicaciones ]. 425 : 1-9. DOI : 10.1016/j.physa.2015.01.012 . ISSN 0378-4371 .
↑ Mosaber Uddin Ahmed. Análisis de complejidad en informática sanitaria // Técnicas de procesamiento de señales para informática sanitaria computacional / Md Atiqur Rahman Ahad, Mosabber Uddin Ahmed. - Cham: Springer International Publishing, 2021. - P. 103–121 . — ISBN 978-3-030-54932-9 . -doi : 10.1007 / 978-3-030-54932-9_4 .
↑ Shi Xiujian; Sol Zhiqiang; Li largo; Xie Hongwei. “Análisis de la Complejidad Cognitiva Humana en Sistemas de Transporte” . logística _ Actas: 4361-4368. DOI : 10.1061/40996(330)637 .
↑ Zhang, Shutao; Qian, Jinwu; Shen, Linyong; Wu, Xi; Hu, Xiaowu (octubre de 2015). “Complejidad de la marcha y análisis del contenido de frecuencia de pacientes con enfermedad de Parkinson” . Simposio internacional sobre bioelectrónica y bioinformática (ISBB) de 2015 : 87–90. DOI : 10.1109/ISBB.2015.7344930 .
↑ Wang, Jisung; Noh, Gyu-Jeong; Choi, Byung-Moon; Ku, Seung Woo; Joo, Pangyu; Jung, Woo-Sung; Kim, Seunghwan; Lee, Heonsoo (2017-07-13). "Complejidad neural suprimida durante la inconsciencia inducida por ketamina y propofol" . Cartas de Neurociencia [ Español ] ]. 653 : 320-325. DOI : 10.1016/j.neulet.2017.05.045 . ISSN 0304-3940 .
↑ Michał Bola, Paweł Orłowski, Martyna Płomecka, Artur Marchewka. Diversidad de señales de EEG durante la sedación con propofol: un aumento en sujetos sedados pero que responden, una disminución en sujetos sedados y que no responden // bioRxiv . — 2019-01-30. - Pág. 444281 . -doi : 10.1101/ 444281 .
↑ Ventilador Yingle; Wu Chuanian; Li Yi; Pang Quan (2006-12-15). “Estudio sobre la aplicación de la medición de la complejidad de la fluctuación en la detección de punto final del habla” . Medicina Aeroespacial e Ingeniería Médica . 19 (6). ISSN 1002-0837 .
↑ Dilger, Alejandro (2012-01-01). “Complejidad endógena, especialización y educación general” . En el Horizonte . 20 (1): 49-53. DOI : 10.1108/10748121211202062 . ISSN 1074-8121 .
↑ Ivanyuk, Vera Alekseevna Modelo dinámico de gestión de cartera de inversiones estratégicas . elibrary.ru (2015). (indefinido)
↑ Javid, Mohammad Ali Javaheri; Blackwell, Tim; Zimmer, Roberto; al-Rifaie, Mohammad Majid (2016). Johnson, Colin; Ciesielski, Vic; Correia, João; Machado, Penousal, eds. “Correlación entre el juicio estético humano y la medida de la complejidad espacial” . Música, sonido, arte y diseño evolutivos y biológicamente inspirados . Apuntes de clase en informática ]. Cham: publicación internacional de Springer: 79-91. DOI : 10.1007/978-3-319-31008-4_6 . ISBN 978-3-319-31008-4 .