Information fluctuation complexity - Enciclopedia
Complejidad de fluctuación de información es una cantidad teórica de la información definida como la fluctuación de información sobre la entropía. Se deriva de las fluctuaciones en la predominancia del orden y el caos en un sistema dinámico y se ha utilizado como una medida de complejidad en muchos campos diversos. Fue introducida en un artículo de 1993 por Bates y Shepard.
Definición
La complejidad de fluctuación de información de un sistema dinámico discreto es una función de la distribución de probabilidad de sus estados cuando está sometido a datos de entrada externos aleatorios. El propósito de impulsar el sistema con una fuente de información rica 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 utiliza un impulso rico en frecuencia en el procesamiento de señales.
Si un sistema tiene
N
{\displaystyle N}
posibles estados y las probabilidades de estado
p
i
{\displaystyle p_{i}}
son conocidas, entonces su entropía de información es
H
=
∑
i
=
1
N
p
i
I
i
=
−
∑
i
=
1
N
p
i
log
p
i
,
{\displaystyle \mathrm {H} =\sum _{i=1}^{N}p_{i}I_{i}=-\sum _{i=1}^{N}p_{i}\log p_{i},}
donde
I
i
=
−
log
p
i
{\textstyle I_{i}=-\log p_{i}}
es el contenido de información del estado
i
{\displaystyle i}
.
La complejidad de fluctuación de información del sistema se define como la desviación estándar o fluctuación de
I
{\displaystyle I}
sobre su media
H
{\displaystyle \mathrm {H} }
:
σ
I
=
∑
i
=
1
N
p
i
(
I
i
−
H
)
2
=
∑
i
=
1
N
p
i
I
i
2
−
H
2
{\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}}}}
o
σ
I
=
∑
i
=
1
N
p
i
log
2
p
i
−
(
∑
i
=
1
N
p
i
log
p
i
)
2
.
{\displaystyle \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 información del estado
σ
I
{\displaystyle \sigma _{I}}
es cero en un sistema altamente desordenado con todas las
p
i
=
1
N
{\textstyle p_{i}={\frac {1}{N}}}
; el sistema simplemente mimica sus entradas aleatorias. La fluctuación de información del estado
σ
I
{\displaystyle \sigma _{I}}
también es cero si el sistema está perfectamente ordenado con solo un estado fijo
(
p
1
=
1
)
{\textstyle (p_{1}=1)}
, independientemente de las entradas. La fluctuación de información del estado
σ
I
{\displaystyle \sigma _{I}}
es no cero entre estos dos extremos con una mezcla de estados de alta y baja probabilidad que ocupan el espacio de estados.
Fluctuación de información permite la memoria y la computación
A medida que un sistema dinámico complejo evoluciona con el tiempo, cómo transita entre estados depende de estímulos externos de manera irregular. A veces puede ser más sensible a los estímulos externos (inestable) y en otras veces menos sensible (estable). Cuando un estado dado tiene múltiples posibles estados siguientes, la información externa determina cuál será el siguiente y el sistema obtiene esta información al seguir una trayectoria particular en el espacio de estados. Sin embargo, si varios estados diferentes conducen al mismo estado siguiente, al entrar en el estado siguiente el sistema pierde información sobre qué estado lo precedió. Por lo tanto, un sistema complejo muestra ganancia y pérdida de información alternada a medida que evoluciona con el tiempo. Esta alternancia o fluctuación de información es equivalente a recordar y olvidar, almacenamiento temporal de información o memoria, una característica esencial de la computación no trivial.
La ganancia o pérdida de información asociada con las transiciones entre estados puede relacionarse con la información del estado. La ganancia neta de información de una transición desde el estado
i
{\displaystyle i}
al estado
j
{\displaystyle j}
es la información obtenida al salir del estado
i
{\displaystyle i}
menos la información perdida al entrar en el estado
j
{\displaystyle j}
:
Γ
i
j
=
−
log
p
i
→
j
+
log
p
i
←
j
.
{\displaystyle \Gamma _{ij}=-\log p_{i\rightarrow j}+\log p_{i\leftarrow j}.}
Aquí
p
i
→
j
{\textstyle p_{i\rightarrow j}}
es la probabilidad condicional forward que si el estado presente es
i
{\displaystyle i}
entonces el estado siguiente será
j
{\displaystyle j}
y
p
i
←
j
{\textstyle p_{i\leftarrow j}}
es la probabilidad condicional reverse que si el estado presente es
j
{\displaystyle j}
entonces el estado anterior fue
i
{\displaystyle i}
. Las probabilidades condicionales están relacionadas con la probabilidad de transición
p
i
j
{\displaystyle p_{ij}}
, la probabilidad de que ocurra una transición desde el estado
i
{\displaystyle i}
al estado
j
{\displaystyle j}
, por:
p
i
j
=
p
i
p
i
→
j
=
p
i
←
j
=
p
j
.
{\displaystyle p_{ij}=p_{i}p_{i\rightarrow j}=p_{i\leftarrow j}p_{j}.}
Eliminando las probabilidades condicionales:
Γ
i
j
=
−
log
(
p
i
j
/
p
i
)
+
log
(
p
i
j
/
p
j
)
=
log
p
i
−
log
p
j
=
I
j
−
I
i
.
{\displaystyle \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 ganancia neta de información del sistema como resultado de la transición depende solo del aumento en la información del estado desde el estado inicial al final. Se puede demostrar que esto es cierto incluso para múltiples transiciones consecutivas.
Γ
=
Δ
I
{\textstyle \Gamma =\Delta I}
recuerda la relación entre la fuerza y la energía potencial. La información
I
{\displaystyle I}
es como la energía potencial
Φ
{\displaystyle \Phi }
y la información
Γ
{\displaystyle \Gamma }
es como la fuerza
F
{\displaystyle \mathbf {F} }
en
F
=
∇
Φ
{\textstyle \mathbf {F} ={\nabla \Phi }}
. La información externa "empuja" a un sistema "hacia arriba" a un estado de mayor información potencial para lograr el almacenamiento de información, de la misma manera que empujar una masa hacia arriba a un estado de mayor potencial gravitatorio almacena energía. La cantidad de energía almacenada depende solo de la altura final, no del camino hacia arriba. Del mismo modo, la cantidad de información almacenada no depende del camino de transición entre un estado común inicial y un estado raro final. Una vez que un sistema alcanza un estado raro con alto potencial de información, puede "caer" de vuelta a un estado común, perdiendo información almacenada previamente.
Puede ser útil calcular la desviación estándar de
Γ
{\displaystyle \Gamma }
sobre su media (que es cero), es decir, la fluctuación de la ganancia neta de información
σ
Γ
{\displaystyle \sigma _{\Gamma }}
, pero
σ
I
{\displaystyle \sigma _{I}}
tiene en cuenta los bucles de memoria de múltiples transiciones en el espacio de estados y, por lo tanto, debería ser más indicativa de la potencia computacional de un sistema. Además, la fluctuación de información del estado
σ
I
{\displaystyle \sigma _{I}}
es más fácil de aplicar porque puede haber muchas más transiciones que estados.
Caos y orden
Un sistema dinámico sensible a la información externa (inestable) muestra comportamiento caótico mientras que uno insensible a la información externa (estable) muestra comportamiento ordenado. Un sistema complejo muestra ambos comportamientos, fluctuando entre ellos en un equilibrio dinámico cuando se somete a una fuente de información rica. El grado de fluctuación se cuantifica por
σ
I
{\displaystyle \sigma _{I}}
; captura la alternancia en la predominancia del caos y el orden en un sistema complejo a medida que evoluciona con el tiempo.
Ejemplo: variante de la regla 110 del automata celular elemental
Fuente:
La variante de la regla 110 del automata celular elemental ha sido demostrada que es capaz de computación universal. La prueba se basa en la existencia e interacción de patrones de celdas cohesivos y auto-perpetuantes conocidos como gliders, que son ejemplos de fenómenos emergentes asociados con sistemas complejos y que implican la capacidad de grupos de celdas autómata para recordar que un glider está pasando por ellos. Por lo tanto, se espera que haya bucles de memoria en el espacio de estados debido a la alternancia de ganancia y pérdida de información, inestabilidad y estabilidad.
Considere un grupo de 3 celdas adyacentes de automata celular que obedecen la regla 110: extremo-centro-extremo. El estado siguiente de la celda central depende de su propio estado presente y el de las celdas extremas según lo especificado por la regla:
Para calcular la complejidad de fluctuación de información de este sistema, adjunte una celda impulsora a cada extremo del grupo de 3 celdas para proporcionar estímulos externos aleatorios como sigue, impulsor→extremo-centro-extremo←impulsor, de manera que se pueda aplicar la regla a las dos celdas extremas. A continuación, determine qué será el estado siguiente para cada estado presente posible y para cada combinación posible de contenido de la celda impulsora, para determinar las probabilidades condicionales forward. El diagrama de estados de este sistema se representa a continuación, con círculos que representan estados y flechas que representan transiciones entre estados. Los ocho posibles estados de este sistema, 1-1-1 a 0-0-0, se etiquetan con el equivalente octal del contenido de 3 bits del grupo de 3 celdas: 7 a 0. Las flechas de transición se etiquetan con probabilidades condicionales forward. Notar que hay variabilidad en la divergencia y convergencia de las flechas correspondiente a la variabilidad en la ganancia y pérdida de información originada de las celdas impulsoras.
Las probabilidades condicionales forward se determinan por la proporción de combinaciones posibles de contenido de la celda impulsora que impulsan una transición particular. Por ejemplo, para las cuatro combinaciones posibles de contenido de dos celdas impulsoras, el estado 7 conduce a los estados 5, 4, 1 y 0, por