Složitost fluktuace informací - Information fluctuation complexity - Wikipedia

Složitost fluktuace informací je informační teoretik množství definované jako fluktuace informací o entropie. Dá se odvodit z fluktuací převahy řádu a chaosu v dynamickém systému a byl použit jako míra složitost v mnoha různých oblastech. To bylo představeno v dokumentu z roku 1993 Batesem a Shepardem.^[1]

Definice

Složitost fluktuace informací diskrétního dynamického systému je funkcí rozdělení pravděpodobnosti jeho stavů, když podléhá náhodným externím vstupním datům. Účelem řízení systému s bohatým zdrojem informací, jako je a generátor náhodných čísel nebo a signál bílého šumu je zkoumat vnitřní dynamiku systému podobně jako a frekvenčně bohatý impuls se používá v zpracování signálu.

Pokud systém má ${ textstyle N}$ možné státy a pravděpodobnosti stavu ${ textový styl p_ {i}}$jsou známy, pak jeho informační entropie je

${ displaystyle mathrm {H} = součet _ {i = 1} ^ {N} p_ {i} I_ {i} = - součet _ {i = 1} ^ {N} p_ {i} log p_ {i},}$

kde ${ textstyle I_ {i} = - log p_ {i}}$ je informační obsah státu ${ textový styl i}$.

The složitost fluktuace informací systému je definován jako standardní odchylka nebo fluktuace ${ textový styl I}$ o jeho průměru ${ textstyle mathrm {H}}$:

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

nebo

${ 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}}}.}$

The fluktuace informací o stavu ${ displaystyle sigma _ {I}}$ je nula v maximálně neuspořádaném systému se všemi ${ displaystyle p_ {i} = 1 / N}$; systém jednoduše napodobuje své náhodné vstupy. ${ displaystyle sigma _ {I}}$ je také nula, když je systém dokonale uspořádán pouze s jedním pevným stavem ${ displaystyle (p_ {1} = 1)}$, bez ohledu na vstupy. ${ displaystyle sigma _ {I}}$ je nenulová mezi těmito dvěma extrémy se směsí obou stavů s vyšší pravděpodobností a stavů s nízkou pravděpodobností státní prostor.

Kolísání informací umožňuje paměť a výpočet

Jak se složitý dynamický systém vyvíjí v čase, jeho přechod mezi stavy závisí na vnějších podnětech nepravidelným způsobem. Někdy může být citlivější na vnější podněty (nestabilní) a jindy méně citlivé (stabilní). Pokud má konkrétní stát několik možných dalších stavů, určí externí informace, který bude další, a systém tyto informace získá sledováním konkrétní trajektorie ve stavovém prostoru. Pokud ale všechny různé stavy vedou ke stejnému dalšímu stavu, pak při vstupu do dalšího stavu systém ztratí informace o tom, který stát mu předcházel. Komplexní systém tedy vykazuje střídavý zisk a ztrátu informací, jak se vyvíjí v čase. Střídání nebo fluktuace informací je ekvivalentní zapamatování a zapomenutí - dočasné uložení informací nebo paměť - základní vlastnost netriviálního výpočtu.

Zisk nebo ztráta informací spojených s přechody mezi stavy mohou souviset se stavovými informacemi. The čistý zisk informací přechodu ze státu ${ displaystyle i}$ do stavu ${ displaystyle j}$ jsou informace získané při opuštění státu ${ displaystyle i}$ méně informací ztracených při vstupu do stavu ${ displaystyle j}$:

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

Tady ${ textový styl p_ {i rightarrow j}}$ je podmíněná pravděpodobnost vpřed že pokud je současný stav ${ displaystyle i}$ pak je další stav ${ displaystyle j}$ a ${ displaystyle p_ {i leftarrow j}}$ je reverzní podmíněná pravděpodobnost že pokud je současný stav ${ displaystyle j}$ pak byl předchozí stav ${ displaystyle i}$. Podmíněné pravděpodobnosti se vztahují k pravděpodobnost přechodu ${ displaystyle p_ {ij}}$, pravděpodobnost, že přechod ze stavu ${ displaystyle i}$ do stavu ${ displaystyle j}$ nastane:

${ displaystyle p_ {ij} = p_ {i} p_ {i rightarrow j} = p_ {j} p_ {i leftarrow j}.}$

Odstranění podmíněných pravděpodobností:

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

Čisté informace získané systémem v důsledku přechodu proto závisí pouze na nárůstu informací o stavu z počátečního do konečného stavu. Je možné ukázat, že to platí i pro několik po sobě jdoucích přechodů.^[1]

${ displaystyle Gamma = Delta I}$ připomíná vztah mezi silou a potenciální energie. ${ displaystyle I}$ je jako potenciál ${ displaystyle Phi}$ a ${ displaystyle Gamma}$ je jako síla ${ displaystyle mathbf {F}}$ v ${ displaystyle mathbf {F} = { nabla Phi}}$. Externí informace „tlačí“ systém „do kopce“ do stavu vyššího informačního potenciálu k dosažení paměti, podobně jako tlačí hmotnost do kopce do stavu vyššího gravitačního potenciálu a ukládá energii. Množství akumulace energie závisí pouze na konečné výšce, nikoli na cestě do kopce. Podobně množství úložiště informací nezávisí na cestě přechodu mezi dvěma stavy ve stavovém prostoru. Jakmile systém dosáhne vzácného stavu s vysokým informačním potenciálem, může „spadnout“ do běžnějšího stavu a ztratit dříve uložené informace.

Může být užitečné vypočítat standardní odchylka z ${ displaystyle Gamma}$ o jeho průměru (což je nula), konkrétně fluktuace čistého zisku informací ${ displaystyle sigma _ { Gamma}}$,^[1] ale ${ displaystyle sigma _ {I}}$ bere v úvahu více přechodů paměťové smyčky ve stavovém prostoru, a proto by měl být lepším ukazatelem výpočetní síly systému. Navíc, ${ displaystyle sigma _ {I}}$ je snadnější vypočítat, protože přechodů může být mnohem více než stavů.

Chaos a pořádek

Vykazuje dynamický systém, který je citlivý na externí informace (nestabilní) chaotický chování, zatímco ten, který je necitlivý na externí informace (stabilní), vykazuje řádné chování. Složitý systém vykazuje obě chování a kolísá mezi nimi v dynamické rovnováze, když podléhá bohatému zdroji informací. Míra fluktuace je kvantifikována pomocí ${ displaystyle sigma _ {I}}$; zachycuje střídání v převaze chaosu a řádu ve složitém systému, jak se vyvíjí v čase.

Příklad: varianta elementárního buněčného automatu podle pravidla 110

The pravidlo 110 varianta základní buněčný automat byl prokázáno být schopen univerzální výpočet. Důkaz je založen na existenci a interakcích soudržných a sebezachovávajících buněčných vzorů známých jako kluzáky nebo kosmické lodě, vznikající jevy, které naznačují schopnost skupin automatických buněk pamatovat si, že nimi prochází kluzák. Lze tedy očekávat, že ve stavovém prostoru budou existovat paměťové smyčky vyplývající ze střídání zisku a ztráty informací, nestability a stability, chaosu a řádu.

Vezměme si tříčlánkovou skupinu sousedních buněk automatu, které se řídí pravidlem 110: konec-střed-konec. Další stav středové buňky závisí na současném stavu samotné a na koncových buňkách, jak je uvedeno v pravidle:

Chcete-li vypočítat složitost fluktuace informací tohoto systému, připojte a buňka řidiče na každý konec 3-buněčné skupiny, aby poskytl náhodný vnější podnět, jako je tento, ovladač → konec-střed-konec ← ovladač, takže pravidlo lze použít na dvě koncové buňky. Dále určete, jaký je další stav pro každý možný současný stav a pro každou možnou kombinaci obsahu buňky ovladače, abyste určili dopředu podmíněné pravděpodobnosti.

The stavový diagram tohoto systému je znázorněno níže, přičemž kruhy představují státy a šipky představují přechody mezi státy. Osm stavů tohoto systému, 1-1-1 na 0-0-0 jsou označeny desetinným ekvivalentem 3bitového obsahu 3článkové skupiny: 7 až 0. Šipky přechodu jsou označeny dopřednými podmíněnými pravděpodobnostmi. Všimněte si, že existuje variabilita v divergenci a konvergenci šipek odpovídajících variabilitě chaosu a řádu, citlivosti a necitlivosti, zisku a ztráty externích informací z buněk ovladače.

Stavový diagram se třemi buňkami pro elementární buněčný automat pravidla 110, ukazující pravděpodobnosti podmíněného přechodu vpřed s náhodnou stimulací.

Přední podmíněné pravděpodobnosti jsou určeny podílem možného obsahu buňky ovladače, který řídí určitý přechod. Například pro čtyři možné kombinace dvou obsahů buněk ovladače stav 7 vede ke stavům 5, 4, 1 a 0 ${ displaystyle p_ {7 rightarrow 5}}$, ${ displaystyle p_ {7 rightarrow 4}}$, ${ displaystyle p_ {7 rightarrow 1}}$, a ${ displaystyle p_ {7 rightarrow 0}}$ jsou každý 1/4 nebo 25%. Podobně stav 0 vede ke stavům 0, 1, 0 a 1 ${ displaystyle p_ {0 rightarrow 1}}$a ${ displaystyle p_ {0 rightarrow 0}}$jsou každý 1/2 nebo 50%. A tak dále.

Pravděpodobnosti stavu souvisí s

${ displaystyle p_ {j} = součet _ {i = 0} ^ {7} p_ {i} p_ {i rightarrow j}}$ a ${ displaystyle sum _ {i = 0} ^ {7} p_ {i} = 1.}$

Tyto lineární algebraické rovnice lze vyřešit ručně nebo pomocí počítačového programu pro pravděpodobnosti stavu s následujícími výsledky:

Entropii informací a složitost lze poté vypočítat ze stavových pravděpodobností:

${ displaystyle mathrm {H} = - součet _ {i = 0} ^ {7} p_ {i} log _ {2} p_ {i} = 2,86 { text {bits}},}$

${ displaystyle sigma _ {I} = { sqrt { sum _ {i = 0} ^ {7} p_ {i} log _ {2} ^ {2} p_ {i} - mathrm {H} ^ {2}}} = 0,56 { text {bits}}.}$

Všimněte si, že maximální možná entropie pro osm stavů je ${ displaystyle log _ {2} 8 = 3 { text {bits}},}$ což by byl případ, kdyby všech osm států bylo stejně pravděpodobných s pravděpodobností 1/8 (náhodnost). Pravidlo 110 má tedy relativně vysokou entropii nebo využití stavu na 2,86 bitu. To ale nevylučuje podstatné kolísání stavových informací o entropii, a tedy podstatnou hodnotu složitosti. Zatímco maximální entropie bych vyloučit složitost.

K získání stavových pravděpodobností lze použít alternativní metodu, pokud je výše uvedená analytická metoda neproveditelná. Jednoduše řídit systém na jeho vstupech (buňky ovladače) s náhodným zdrojem po mnoho generací a empiricky sledovat pravděpodobnosti stavu. Pokud k tomu dojde pomocí počítačové simulace po dobu 10 milionů generací, budou výsledky následující:^[2]

Informační proměnné pro elementární buněčný automat pravidla 110

počet buněk	3	4	5	6	7	8	9	10	11	12	13
${ displaystyle mathrm {H}}$ (bity)	2.86	3.81	4.73	5.66	6.56	7.47	8.34	9.25	10.09	10.97	11.78
${ displaystyle sigma _ {I}}$(bity)	0.56	0.65	0.72	0.73	0.79	0.81	0.89	0.90	1.00	1.01	1.15
${ displaystyle 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

Protože oba ${ displaystyle mathrm {H}}$ a ${ displaystyle sigma _ {I}}$ rostou s velikostí systému, jejich bezrozměrným poměrem ${ displaystyle sigma _ {I} / mathrm {H}}$, relativní složitost fluktuace informací, je zahrnuto pro lepší srovnání systémů různých velikostí. Všimněte si, že empirické a analytické výsledky se shodují pro 3článkový automat.

V příspěvku Batesa a Sheparda,^[1] ${ displaystyle sigma _ {I}}$ se počítá pro všechna pravidla elementárních celulárních automatů a bylo pozorováno, že ty, které vykazují pomalu se pohybující kluzáky a případně stacionární objekty, jak to dělá pravidlo 110, vysoce korelují s velkými hodnotami ${ displaystyle sigma _ {I}}$. ${ displaystyle sigma _ {I}}$ lze tedy použít jako filtr pro výběr pravidel kandidátů pro univerzální výpočet, což je zdlouhavé prokazovat.

Aplikace

Ačkoli je odvození vzorce složitosti fluktuace informací založeno na fluktuacích informací v dynamickém systému, vzorec závisí pouze na pravděpodobnostech stavu, a je tedy použitelný i pro jakékoli rozdělení pravděpodobnosti, včetně těch odvozených ze statických obrázků nebo textu.

V průběhu let původní papír^[1] byl doporučeno výzkumníci v mnoha různých oblastech: teorie složitosti,^[3] komplexní systémy vědy,^[4] chaotická dynamika,^[5] environmentální inženýrství,^[6] ekologická složitost,^[7] ekologická analýza časových řad,^[8] udržitelnost ekosystému,^[9] vzduch^[10] a voda^[11] znečištění, hydrologická vlnková analýza,^[12] průtok půdy,^[13] vlhkost půdy,^[14] odtok horní vody,^[15] hloubka podzemní vody,^[16] řízení letového provozu,^[17] vzory proudění,^[18] topologie,^[19] tržní prognóza kovů^[20] a elektřinu^[21] ceny, lidské poznání,^[22] kinematika lidské chůze,^[23] neurologie,^[24] EEG analýza,^[25] analýza řeči,^[26] vzdělání,^[27] investování,^[28] a estetika.^[29]

Reference