Složitost (teorie informace)

Informačně-fluktuační složitost je informačně-teoretická hodnota definovaná jako fluktuace informace s ohledem na informační entropii . Je odvozen z kolísání převahy řádu a chaosu v dynamickém systému a používá se v různých oblastech znalostí k měření složitosti . Teorie byla představena v práci Batese a Sheparda v roce 1993 [1] .

Definice

Informačně-fluktuační složitost diskrétního dynamického systému je funkcí rozdělení pravděpodobnosti stavů tohoto systému vystavených náhodným datovým vstupům. Cílem řízení systému s bohatým zdrojem informací, jako je generátor náhodných čísel nebo signál bílého šumu , je prozkoumat vnitřní dynamiku systému v podstatě stejným způsobem , jako se při zpracování signálu používá frekvenčně bohatý pulz .

Pokud má systém možné stavy a jsou známy pravděpodobnosti stavů , pak je jeho informační entropie rovna ${\textstyle N}$ ${\textstyle p_{i}}$

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

kde je vlastní státní informace . ${\textstyle I_{i}=-\log p_{i}}$ ${\textstyle i}$

Informačně-fluktuační složitost systému je definována jako standardní odchylka nebo fluktuace od jeho střední hodnoty : ${\textstyle I}$ ${\textstyle \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))))

nebo

\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}}}.

Kolísání stavových informací je v maximálně neuspořádaném systému nulové se všemi ; systém jednoduše simuluje náhodné datové vstupy. je také nula, když je systém dokonale uspořádaný a má pouze jeden pevný stav , bez ohledu na vstupy. je nenulová mezi těmito dvěma extrémy, kdy stavy s vysokou pravděpodobností i stavy s nízkou pravděpodobností vyplňují stavový prostor. $\sigma _{I}$ $p_{i}=1/N$ $\sigma _{I}$ $(p_{1}=1)$ $\sigma _{I}$

Fluktuace informací poskytují paměť a výpočty

Jak se složitý dynamický systém vyvíjí v čase, přechází z jednoho stavu do druhého. Jak k těmto přechodům dochází, závisí nepravidelně na vnějších podnětech. V některých případech může být systém citlivější na vnější podněty (nestabilní), zatímco v jiných může být méně citlivý (stabilní). Pokud má určitý stav několik možných dalších stavů, externí informace určují, který z nich bude další, a systém tuto informaci získá sledováním určité trajektorie ve stavovém prostoru. Pokud ale několik různých stavů vede ke stejnému dalšímu stavu, pak při jeho vstupu systém ztratí informaci o tom, který stav mu předcházel. Tak, jak se vyvíjí v průběhu času, komplexní systém vykazuje střídavé zisky a ztráty informací. Střídání nebo kolísání informací se rovná zapamatování a zapomenutí – dočasnému uložení informace nebo paměti – to je základní rys netriviálních výpočtů.

Zisk nebo ztráta informace, která doprovází stavové přechody, může být spojena s vlastní stavovou informací. Čistý informační zisk během přechodu ze stavu do stavu je informace získaná při opuštění stavu mínus ztráta informace při vstupu do stavu : $i$ $j$ $i$ $j$

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

Zde je přímá podmíněná pravděpodobnost , že pokud je aktuální stav , bude další stav a je inverzní podmíněná pravděpodobnost , že pokud je aktuální stav , byl předchozí stav . Podmíněné pravděpodobnosti souvisejí s pravděpodobností přechodu , pravděpodobností, že dojde k přechodu ze stavu do stavu : ${\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}.

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

\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 tedy závisí pouze na nárůstu stavové informace z výchozího stavu do konečného stavu. Lze ukázat, že to platí i pro několik po sobě jdoucích přechodů [1] .

Vzorec připomíná vztah mezi silou a potenciální energií . je podobná potenciální energii a je to síla ve vzorci . Vnější informace „tlačí“ systém „nahoru“, do stavu s vyšším informačním potenciálem pro uchování paměti, stejně jako vytlačování tělesa s nějakou hmotou do kopce, do stavu s vyšším gravitačním potenciálem, vede k akumulaci energie. Množství akumulované energie závisí pouze na konečné výšce, nikoli na cestě do kopce. Stejně tak množství uložených informací je nezávislé na přechodové cestě mezi dvěma stavy. Jakmile systém dosáhne vzácného stavu vysokého informačního potenciálu, může „spadnout“ zpět do normálního stavu a ztratit dříve uložené informace. $\Gamma =\Delta I$ $já$ $E_{p}$ $\Gamma$ $\mathbf {F}$ $\mathbf {F} ={\nabla E_{p))$

Může být užitečné vypočítat směrodatnou odchylku od jejího průměru (který je nulový), konkrétně fluktuaci čistého informačního zisku [1] , ale bere v úvahu cykly vícepřechodové stavové paměti , a proto by měl být přesnější indikátor výpočetního výkonu systému. Navíc se to snadněji počítá, protože přechodů může být mnohem více než stavů. $\Gamma$ ${\displaystyle \sigma _{\Gamma ))$ $\sigma _{I}$ $\sigma _{I}$

Chaos a řád

Dynamický systém citlivý na vnější informace (nestabilní) vykazuje chaotické chování, zatímco systém, který je necitlivý na vnější informace (stabilní), vykazuje uspořádané chování. Pod vlivem bohatého zdroje informací vykazuje složitý systém obě chování a osciluje mezi nimi v dynamické rovnováze. Stupeň fluktuace se kvantitativně měří pomocí ; zachycuje střídání převahy chaosu a řádu ve složitém systému, jak se vyvíjí v čase. $\sigma _{I}$

Příklad: varianta elementárního celulárního automatu podle pravidla 110

Je prokázáno , že varianta elementárního celulárního automatu podle pravidla 110 je schopna univerzálních výpočtů . Důkaz je založen na existenci a interakci propojených a sebezáchovných buněčných konfigurací známých jako „kluzáky“ nebo „ kosmické lodě “, fenomén vynoření , který implikuje schopnost skupin buněk automatu zapamatovat si, že jimi prolétá kluzák. Proto je třeba očekávat, že ve stavovém prostoru budou docházet k paměťovým smyčkám, a to v důsledku střídání získávání a ztráty informací, nestability a stability, chaosu a řádu.

Uvažujme skupinu tří sousedních buněk buněčného automatu, které se řídí pravidlem 110:end-center-end. Další stav centrální buňky závisí na jejím aktuálním stavu a buňkách listu, jak je uvedeno v pravidle:

Pravidlo 110 elementárního buněčného automatu.

3 buněčné skupiny	1-1-1	1-1-0	1-0-1	1-0-0	0-1-1	0-1-0	0-0-1	0-0-0
další středová buňka	0	jeden	jeden	0	jeden	jeden	jeden	0

Pro výpočet složitosti informační fluktuace tohoto systému by bylo možné připojit buňku řidiče ke každému konci skupiny 3 buněk, aby poskytly náhodný vnější podnět, např.driver→end-center-end←driver, takže pravidlo lze aplikovat na dvě koncové buňky. Poté potřebuje určit, jaký je další stav pro každý možný aktuální stav a pro každou možnou kombinaci obsahu řídicí buňky, aby vypočítal přímé podmíněné pravděpodobnosti.

Stavový diagram tohoto systému je uveden níže. V něm kruhy představují stavy a šipky představují přechody mezi stavy. Osm stavů tohoto systému, od1-1-1před0-0-0jsou číslovány desetinnými ekvivalenty 3bitového obsahu skupiny 3 buněk: od 7 do 0. V blízkosti šipek přechodu jsou zobrazeny hodnoty přímých podmíněných pravděpodobností. Schéma ukazuje variabilitu v divergenci a konvergenci šipek, která odpovídá variabilitě v chaosu a řádu, citlivosti a necitlivosti, získávání a ztrátě externích informací z buněk řidiče.

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

Stavové pravděpodobnosti jsou vztaženy vzorcem

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

\sum _{i=0}^{7}p_{i}=1.

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

p0 _	p1 _	p2 _	p 3	p4 _	p5 _	p6 _	p 7
2/17	2/17	1/34	5/34	2/17	2/17	2/17	4/17

Informační entropii a složitost lze vypočítat z pravděpodobností stavu:

\mathrm {H} =-\sum _{i=0}^{7}p_{i}\log _{2}p_{i}=2,86

netopýr,

\sigma _{I}={\sqrt {\sum _{i=0}^{7}p_{i}\log _{2}^{2}p_{i}-\mathrm {H} ^{2}}}=0,56

bit.

Je třeba poznamenat, že maximální možná entropie pro osm stavů je rovna bitu, což odpovídá případu, kdy je všech osm stavů stejně pravděpodobných, s pravděpodobnostmi 1/8 (chaotické). Proto má pravidlo 110 relativně vysokou entropii nebo využití stavu 2,86 bitů. To však nevylučuje výrazné kolísání stavové informace s ohledem na entropii a tím i vysokou míru složitosti. Zatímco maximální entropie by vylučovala složitost . $\log _{2}8=3$

Pokud výše popsaná analytická metoda není proveditelná, lze k získání pravděpodobností stavu použít alternativní metodu. Spočívá v řízení systému přes jeho vstupy (buňky ovladače) náhodným zdrojem po mnoho generací a empirickém sledování pravděpodobnosti stavu. Po provedení počítačových simulací pro 10 milionů generací jsou výsledky následující: [2]

Informační proměnné pro elementární celulární automat podle pravidla 110

počet buněk	3	čtyři	5	6	7	osm	9	deset	jedenáct	12	13
$\mathrm{H}$ (bit)	2,86	3,81	4,73	5.66	6.56	7,47	8.34	9.25	10.09	10,97	11,78
$\sigma _{I}$ (bit)	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

Protože oba parametry a , rostou s velikostí systému, pro lepší srovnání systémů různých velikostí je navržen bezrozměrný vztah , relativní informačně-fluktuační složitost. Všimněte si, že empirické a analytické výsledky jsou konzistentní pro 3článkový automat. $\mathrm{H}$ $\sigma _{I}$ $\sigma _{I}/\mathrm {H}$

V práci Batese a Sheparda [1] se počítá pro všechna pravidla elementárních buněčných automatů a bylo zjištěno, že ty, které vykazují pomalu se pohybující „kluzáky“ a případně stacionární objekty, například pravidlo 110, jsou úzce spojeny s velkými hodnotami . Proto jej lze použít jako filtr při výběru pravidel schopných univerzálního výpočtu, což je únavné dokazovat. $\sigma _{I}$ $\sigma _{I}$ $\sigma _{I}$

Aplikace

Přestože odvození vzorce složitosti fluktuace informace je založeno na fluktuacích informací v dynamickém systému, samotný vzorec závisí pouze na pravděpodobnosti stavu, a proto může být také aplikován na libovolné rozdělení pravděpodobnosti, včetně těch odvozených ze statických obrázků nebo textu.

V průběhu let se na původní článek [1] odkazovali výzkumníci z mnoha různých oblastí: teorie složitosti [3] , věda o komplexních systémech [4] , chaotická dynamika [5] , environmentální inženýrství [6] , ekologická složitost [7] , analýza ekologických časových řad [8] , odolnost ekosystémů [9] , znečištění ovzduší [10] a vody [11] , hydrologická vlnková analýza [12] , modelování vodních toků v půdě [13] , půdní vlhkost [14] , povodí odtok [15] , hloubka podzemní vody [16] , řízení letového provozu [17] , schéma proudění [18] , topologie [19] , tržní prognózy cen kovů [20] a elektřiny [21] , zdravotnická informatika [22] , lidská kognice [23] , kinematika lidské chůze [24] neurologie [25] analýza EEG [26] analýza řeči [27] vzdělávání [28] investování [29] estetika [30] .

Odkazy

↑ 1 2 3 4 5 John E. Bates, Harvey K. Shepard. Měření složitosti pomocí fluktuace informací (anglicky) // Physics Letters A. — 1993-01-18. — Sv. 172 , iss. 6 . — S. 416–425 . — ISSN 0375-9601 . - doi : 10.1016/0375-9601(93)90232-O .
↑ Bates, John E. Měření složitosti pomocí fluktuace informací: návod . Brána výzkumu (30. března 2020). (neurčitý)
↑ Harald Atmanspacher. Kartézský střih, Heisenbergův střih a koncept složitosti // World Futures. - 1997-09-01. - T. 49 , č.p. 3-4 . — S. 333–355 . — ISSN 0260-4027 . - doi : 10.1080/02604027.1997.9972639 .
↑ Cosma Rohilla Shalizi. Metody a techniky vědy o komplexních systémech: Přehled // Věda o komplexních systémech v biomedicíně / Thomas S. Deisboeck, J. Yasha Kresh. — Boston, MA: Springer US, 2006. — S. 33–114 . — ISBN 978-0-387-33532-2 . - doi : 10.1007/978-0-387-33532-2_2 .
↑ Renate Wackerbauer. Hlukem indukovaná stabilizace systému Lorenz // Physical Review E. - 1995-11-01. - T. 52 , č.p. 5 . — S. 4745–4749 . - doi : 10.1103/PhysRevE.52.4745 .
↑ Singh, Vijay P. Teorie entropie a její aplikace v environmentálním a vodním inženýrství : [ eng. ] . — John Wiley & Sons, 2013-01-10. — ISBN 978-1-118-42860-3 .
↑ Parrott, Lael (2010-11-01). „Měření ekologické složitosti“ . Ekologické indikátory _ ]. 10 (6): 1069-1076. DOI : 10.1016/j.ecolind.2010.03.014 . ISSN 1470-160X .
↑ Holger Lange. Analýza časových řad v ekologii (anglicky) // eLS. - American Cancer Society, 2006. - ISBN 978-0-470-01590-2 . - doi : 10.1038/npg.els.0003276 .
↑ Wang, Chaojun; Zhao, Hongrui (2019-04-18). „Analýza dat časových řad dálkového průzkumu Země pro podporu udržitelnosti ekosystému: využití časové informační entropie“ . Mezinárodní žurnál dálkového průzkumu Země . 40 (8): 2880-2894. DOI : 10.1080/01431161.2018.1533661 . ISSN 0143-1161 .
↑ Klemm, Otto; Lange, Holger (1999-12-01). „Trendy znečištění ovzduší v pohoří Fichtelgebirge, Bavorsko“ . Environmentální věda a výzkum znečištění ]. 6 (4): 193-199. DOI : 10.1007/BF02987325 . ISSN 1614-7499 .
↑ Wang, Kang; Lin, Zhongbing (2018). „Charakteristika plošného znečištění řeky v různých prostorových měřítcích“ . Water and Environment Journal ]. 32 (3): 453-465. DOI : 10.1111/wej.12345 . ISSN 1747-6593 .
↑ Labát, David (2005-11-25). „Nedávné pokroky ve vlnkových analýzách: Část 1. Přehled pojmů“ . Journal of Hydrology ]. 314 (1): 275-288. DOI : 10.1016/j.jhydrol.2005.04.003 . ISSN 0022-1694 .
↑ Pachepskij, Jakov; Guber, Andrej; Jacques, Diederik; Šimůnek, Jiří; Van Genuchten, Marthinus Th.; Nicholson, Thomas; Cady, Ralph (2006-10-01). „Informační obsah a složitost simulovaných toků půdní vody“ . Geoderma . Fraktální geometrie aplikovaná na půdu a související hierarchické systémy -- fraktály , složitost a heterogenita ]. 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). „Informační teoretické vyhodnocení satelitního vyhledávání půdní vlhkosti“ . Dálkový průzkum prostředí ]. 204 : 392-400. DOI : 10.1016/j.rse.2017.10.016 . HDL : 2060/20180003069 . ISSN 0034-4257 .
↑ Hauhs, Michael; Lange, Holger (2008). "Klasifikace odtoku v povodích horní vody: Fyzikální problém?" . Zeměpisný kompas _ ]. 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). „Výzkum složitosti regionálních hloubek podzemních vod založených na víceúrovňové entropii: případová studie pobočky Jiangsanjiang Bureau v Číně“ . environmentální vědy o Zemi ]. 70 (1): 353-361. DOI : 10.1007/s12665-012-2132-y . ISSN 1866-6299 .
↑ Xing, Jing; Manning, Carol A. (duben 2005). "Zobrazení složitosti a automatizace řízení letového provozu : přehled literatury a analýza " ].
↑ Wang, Kang; Li, Li (listopad 2008). „Charakterizace heterogenních vzorců toku pomocí informačních měření“ . 2008 První mezinárodní konference o inteligentních sítích a inteligentních systémech : 654-657. DOI : 10.1109/ICINIS.2008.110 .
↑ Javaheri Javid, Mohammad Ali; Alghamdi, Wajdi; Zimmer, Robert & al-Rifaie, Mohammad Majid (2016), Bi, Yaxin; Kapoor, Supriya & Bhatia, Rahul, eds., Srovnávací analýza detekce symetrií v toroidní topologii , Studie výpočetní inteligence, Springer International Publishing, str. 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-331686- . Staženo 7. dubna 2020.
↑ On, Kaijian; Lu, Xingjing; Zou, Yingchao; Keung Lai, Kin (2015-09-01). „Prognózování cen kovů pomocí víceškálové metodiky založené na křivkách“ . Zásady zdrojů _ ]. 45 : 144-150. DOI : 10.1016/j.resourpol.2015.03.011 . ISSN 0301-4207 .
↑ On, Kaijian; Xu, Yang; Zou, Yingchao; Tang, Ling (2015-05-01). „Prognózy cen elektřiny pomocí přístupu založeného na odšumování křivek“ . Physica A: Statistická mechanika a její aplikace ]. 425 :1-9. DOI : 10.1016/j.physa.2015.01.012 . ISSN 0378-4371 .
↑ Mosabber Uddin Ahmed. Analýza složitosti ve zdravotnické informatice // Techniky zpracování signálů pro výpočetní zdravotnickou informatiku / Md Atiqur Rahman Ahad, Mosabber Uddin Ahmed. - Cham: Springer International Publishing, 2021. - S. 103–121 . — ISBN 978-3-030-54932-9 . - doi : 10.1007/978-3-030-54932-9_4 .
↑ Shi Xiujian; Sun Zhiqiang; Li Long; Xie Hongwei. „Analýza lidské kognitivní komplexity v dopravních systémech“ . Logistika . Sborník: 4361-4368. DOI : 10.1061/40996(330)637 .
↑ Zhang, Shutao; Qian, Jinwu; Shen, Linyong; Wu, Xi; Hu, Xiaowu (říjen 2015). „Analýzy složitosti chůze a obsahu frekvence u pacientů s Parkinsonovou chorobou“ . 2015 International Symposium on Bioelectronics and Bioinformatics (ISBB) : 87–90. DOI : 10.1109/ISBB.2015.7344930 .
↑ Wang, Jisung; No, Gyu-Jeong; Choi, Byung-Moon; Ku, Seung-Woo; Joo, Pangyu; Jung, Woo-Sung; Kim, Seunghwan; Lee, Heonsoo (2017-07-13). „Potlačená neurální komplexita během bezvědomí vyvolaného ketaminem a propofolem“ . Neuroscience Letters [ anglicky ] ]. 653 : 320-325. DOI : 10.1016/j.neulet.2017.05.045 . ISSN 0304-3940 .
↑ Michał Bola, Paweł Orłowski, Martyna Płomecka, Artur Marchewka. Diverzita signálu EEG během sedace propofolem: zvýšení sedativních, ale citlivých subjektů, snížení sedativních a nereagujících subjektů // bioRxiv . — 2019-01-30. - S. 444281 . - doi : 10.1101/444281 .
↑ Fan Yingle; Wu Chuanyan; Li Yi; Pang Quan (2006-12-15). „Studie o aplikaci měření složitosti fluktuace při detekci koncových bodů řeči“ . Letecká medicína a lékařské inženýrství . 19 (6). ISSN 1002-0837 .
↑ Dilger, Alexander (2012-01-01). „Endogenní komplexnost, specializace a všeobecné vzdělání“ . Na obzoru . 20 (1): 49-53. DOI : 10.1108/10748121211202062 . ISSN 1074-8121 .
↑ Ivanyuk, Vera Alekseevna Dynamický model řízení strategického investičního portfolia . elibrary.ru (2015). (neurčitý)
↑ Javid, Mohammad Ali Javaheri; Blackwell, Tim; Zimmer, Robert; al-Rifaie, Mohammad Majid (2016). Johnson, Collin; Ciesielski, Vic; Correia, João; Machado, Penousal, ed. „Korelace mezi lidským estetickým úsudkem a mírou prostorové složitosti“ . Evoluční a biologicky inspirovaná hudba, zvuk, umění a design . Poznámky z přednášek z informatiky ]. Cham: Springer International Publishing: 79-91. DOI : 10.1007/978-3-319-31008-4_6 . ISBN 978-3-319-31008-4 .