Komplexitet (informationsteori)

Informationsfluktuationskomplexitet är ett informationsteoretiskt värde definierat som fluktuationen av information med avseende på informationsentropi . Det härrör från fluktuationer i förekomsten av ordning och kaos i ett dynamiskt system och används inom olika kunskapsområden för att mäta komplexitet . Teorin presenterades i Bates och Shepards arbete 1993 [1] .

Definition

Informationsfluktuationskomplexiteten hos ett diskret dynamiskt system är en funktion av sannolikhetsfördelningen av tillstånden i detta system som utsätts för slumpmässiga datainmatningar. Målet med att styra ett system med en rik informationskälla, såsom en slumptalsgenerator eller en signal med vitt brus , är att utforska systemets interna dynamik på ungefär samma sätt som en frekvensrik puls används vid signalbehandling .

Om systemet har möjliga tillstånd och sannolikheterna för tillstånd är kända, är dess informationsentropi lika med ${\textstyle N}$ ${\textstyle p_{i))$

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

var är den egna statens information . ${\textstyle I_{i}=-\log p_{i}}$ ${\textstyle i}$

Informationsfluktuationskomplexiteten för ett system definieras som standardavvikelsen eller fluktuationen från dess medelvärde : ${\textstyle I}$ ${\textstil \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))))

eller

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

Fluktuationen av tillståndsinformation är noll i ett maximalt oordnat system med alla ; systemet simulerar helt enkelt slumpmässiga datainmatningar. är också noll när systemet är perfekt ordnat och bara har ett fast tillstånd , oavsett ingångarna. är icke-noll mellan dessa två ytterligheter när både tillstånd med hög sannolikhet och tillstånd med låg sannolikhet är möjliga att fylla tillståndsutrymmet. $\sigma _{I}$ $p_{i}=1/N$ $\sigma _{I}$ $(p_{1}=1)$ $\sigma _{I}$

Fluktuationer i information ger minne och beräkning

När ett komplext dynamiskt system utvecklas med tiden, går det från ett tillstånd till ett annat. Hur dessa övergångar sker beror på yttre stimuli på ett oregelbundet sätt. I vissa fall kan systemet vara mer känsligt för yttre stimuli (instabilt), medan det i andra kan vara mindre känsligt (stabilt). Om ett visst tillstånd har flera möjliga nästa tillstånd, avgör extern information vilket som kommer att bli nästa, och systemet erhåller denna information genom att följa en viss bana i tillståndsrummet. Men om flera olika tillstånd leder till samma nästa tillstånd, förlorar systemet information om vilket tillstånd som föregick det när det går in i det. Allt eftersom det utvecklas över tiden, uppvisar ett komplext system alternerande vinster och förluster av information. Växlingar eller fluktuationer av information är liktydigt med att komma ihåg och glömma - tillfällig lagring av information eller minne - detta är ett väsentligt inslag i icke-triviala beräkningar.

Vinsten eller förlusten av information som åtföljer tillståndsövergångar kan associeras med dess egen tillståndsinformation. Nettoinformationsvinsten under övergången från stat till stat är informationen som erhålls när du lämnar staten minus informationsförlusten när du går in i staten : $i$ $j$ $i$ $j$

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

Här är den direkta villkorade sannolikheten att om det nuvarande tillståndet är så kommer nästa tillstånd att vara och är den omvända villkorade sannolikheten att om det nuvarande tillståndet är så var det föregående tillståndet . Villkorliga sannolikheter är relaterade till övergångssannolikheten , sannolikheten för att en övergång från tillstånd till tillstånd kommer att inträffa , genom: ${\textstil p_{i\högerpil 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}.

Om vi eliminerar villkorade sannolikheter får vi:

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

Nettoinformationen som erhålls av systemet som ett resultat av övergången beror därför endast på ökningen av tillståndsinformation från det initiala tillståndet till det slutliga tillståndet. Det kan visas att detta är sant även för flera på varandra följande övergångar [1] .

Formeln liknar förhållandet mellan kraft och potentiell energi . liknar den potentiella energin och är kraften i formeln . Extern information "skjuter" systemet "uppåt", till ett tillstånd med högre informationspotential för minnesbevarande, precis som att driva en kropp med viss massa uppför, till ett tillstånd med högre gravitationspotential, leder till ackumulering av energi. Mängden lagrad energi beror bara på den slutliga höjden och inte på vägen uppför. På samma sätt är mängden lagrad information oberoende av övergångsvägen mellan två tillstånd. När ett system väl når ett sällsynt tillstånd med hög informationspotential kan det "falla" tillbaka till ett normalt tillstånd och förlora tidigare lagrad information. $\Gamma =\Delta I$ $jag$ $E_{p}$ $\Gamma$ $\mathbf {F}$ $\mathbf {F} ={\nabla E_{p))$

Det kan vara användbart att beräkna standardavvikelsen från dess medelvärde (som är noll), nämligen fluktuationen av nettoinformationsförstärkningen [1] , men det tar hänsyn till multi-transition state-space minnescykler och bör därför vara en mer exakt indikator på systemets processorkraft. Dessutom är det lättare att beräkna, eftersom det kan finnas många fler övergångar än stater. $\Gamma$ ${\displaystyle \sigma _{\Gamma ))$ $\sigma _{I}$ $\sigma _{I}$

Kaos och ordning

Ett dynamiskt system som är känsligt för extern information (instabilt) uppvisar ett kaotiskt beteende, medan ett system som är okänsligt för extern information (stabilt) uppvisar ett ordnat beteende. Under påverkan av en rik informationskälla uppvisar ett komplext system båda beteendena, och pendlar mellan dem i en dynamisk balans. Graden av fluktuation mäts kvantitativt med ; den fångar växlingen av dominansen av kaos och ordning i ett komplext system när det utvecklas över tiden. $\sigma _{I}$

Exempel: en variant av den elementära cellulära automaten enligt regel 110

Det är bevisat att en variant av den elementära cellulära automaten enligt regel 110 är kapabel till universella beräkningar . Beviset är baserat på förekomsten och interaktionen av anslutna och självbevarande cellulära konfigurationer kända som "glidare" eller " rymdskepp ", fenomenet emergens , vilket innebär förmågan hos grupper av automatceller att komma ihåg att ett glidflygplan passerar genom dem. Därför bör det förväntas att minnesslingor kommer att uppstå i tillståndsutrymmet, som ett resultat av växlingen av vinst och förlust av information, instabilitet och stabilitet, kaos och ordning.

Betrakta en grupp av tre intilliggande celler i en cellulär automat som följer regel 110:slut-center-ände. Nästa tillstånd för mittcellen beror på dess nuvarande tillstånd och bladcellerna, enligt regeln:

Elementär cellulär automatregel 110.

3-cellsgrupp	1-1-1	1-1-0	1-0-1	1-0-0	0-1-1	0-1-0	0-0-1	0-0-0
nästa mittcell	0	ett	ett	0	ett	ett	ett	0

För att beräkna informationsfluktuationskomplexiteten för detta system, skulle man fästa en drivcell vid varje ände av en grupp av 3 celler för att ge en slumpmässig extern stimulans, t.ex.förare→end-center-end←förare, så att regeln kan tillämpas på de två slutcellerna. Den behöver sedan bestämma vad nästa tillstånd är för varje möjligt aktuellt tillstånd och för varje möjlig kombination av drivarcellinnehåll för att beräkna de direkta villkorliga sannolikheterna.

Tillståndsdiagrammet för detta system visas nedan. I den representerar cirklar tillstånd och pilar representerar övergångar mellan tillstånd. De åtta tillstånden i detta system, från1-1-1innan0-0-0är numrerade med decimalekvivalenter av 3-bitars innehållet i en grupp med 3 celler: från 7 till 0. Nära övergångspilarna visas värdena för direkta villkorliga sannolikheter. Schemat visar variabilitet i divergens och konvergens av pilar, vilket motsvarar variabilitet i kaos och ordning, känslighet och okänslighet, inhämtning och förlust av extern information från förarceller.

Direkta villkorade sannolikheter bestäms av andelen av det möjliga innehållet i förarcellen som styr en viss övergång. Till exempel, för fyra möjliga kombinationer av innehållet i två drivceller, leder tillstånd 7 till tillstånd 5, 4, 1 och 0, så , , och är 1/4 eller 25 %. På samma sätt leder tillstånd 0 till tillstånd 0, 1, 0 och 1, så 1/2, eller 50 % , motsvarar. Och så vidare. $p_{7\rightarrow 5}$ $p_{7\rightarrow 4}$ $p_{7\rightarrow 1}$ $p_{7\rightarrow 0}$ $p_{0\rightarrow 1}$ $p_{0\rightarrow 0}$

Tillståndssannolikheterna är relaterade med formeln

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

och

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

Dessa linjära algebraiska ekvationer kan lösas manuellt eller med ett datorprogram för tillståndsannolikheter, med följande resultat:

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

Informationsentropi och komplexitet kan beräknas från tillståndssannolikheter:

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

fladdermus,

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

bit.

Det bör noteras att den maximala möjliga entropin för åtta tillstånd är lika med en bit, vilket motsvarar fallet när alla åtta tillstånd är lika sannolika, med sannolikheter 1/8 (kaotiskt). Därför har regel 110 en relativt hög entropi eller tillståndsanvändning på 2,86 bitar. Detta utesluter dock inte en betydande fluktuation av tillståndsinformationen med avseende på entropin och följaktligen en hög mängd komplexitet. Medan maximal entropi skulle utesluta komplexitet. $\log _{2}8=3$

En alternativ metod kan användas för att erhålla tillståndssannolikheter när den ovan beskrivna analysmetoden inte är genomförbar. Det består i att driva systemet genom dess ingångar (drivarceller) med en slumpmässig källa i många generationer och observera tillståndssannolikheterna empiriskt. När det är gjort med datorsimuleringar i 10 miljoner generationer är resultaten följande: [2]

Informationsvariabler för en elementär cellulär automat enligt regel 110

antal celler	3	fyra	5	6	7	åtta	9	tio	elva	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

Eftersom båda parametrarna, och , ökar med storleken på systemet, för en bättre jämförelse av system av olika storlekar, föreslås en dimensionslös relation , relativ informations-fluktuationskomplexitet. Observera att de empiriska och analytiska resultaten är konsekventa för en 3-cellsautomat. $\mathrm{H}$ $\sigma _{I}$ $\sigma _{I}/\mathrm {H}$

I Bates och Shepards arbete [1] beräknas det för alla regler för elementära cellulära automater, och det märktes att de som uppvisar långsamma "glidare" och möjligen stationära föremål, till exempel regel 110, är nära associerade med stora värden på . Därför kan det användas som ett filter när man väljer regler som kan beräkningar för universell, vilket är tråkigt att bevisa. $\sigma _{I}$ $\sigma _{I}$ $\sigma _{I}$

Applikationer

Även om härledningen av informationsfluktuationskomplexitetsformeln är baserad på fluktuationerna av information i ett dynamiskt system, beror formeln i sig endast på tillståndssannolikheter och kan därför också tillämpas på vilken sannolikhetsfördelning som helst, inklusive de som härrör från statiska bilder eller text.

Under årens lopp har den ursprungliga artikeln [1] refererats av forskare från många olika områden: komplexitetsteori [3] , komplex systemvetenskap [4] , kaotisk dynamik [5] , miljöteknik [6] , ekologisk komplexitet [7] , ekologisk tidsserieanalys [8] , ekosystemresiliens [9] , luftföroreningar [10] och vatten [11] , hydrologisk våganalys [12] , modellering av vattenflöden i mark [13] , markfuktighet [14] , vattendelare avrinning [15] , grundvattendjup [16] , flygledning [17] , flödesmönster [18] , topologi [19] , marknadsprognoser för priser på metaller [20] och el [21] , hälsoinformatik [22] , mänsklig kognition [23] , mänsklig gångkinematik [24] neurologi [25] EEG-analys [26] talanalys [27] utbildning [28] investera [29] estetik [30] .

Länkar

↑ 1 2 3 4 5 John E. Bates, Harvey K. Shepard. Mätning av komplexitet med hjälp av informationsfluktuation (engelska) // Physics Letters A. — 1993-01-18. — Vol. 172 , iss. 6 . — S. 416–425 . — ISSN 0375-9601 . - doi : 10.1016/0375-9601(93)90232-O .
↑ Bates, John E. Att mäta komplexitet med hjälp av informationsfluktuationer: en handledning . Research Gate (30 mars 2020). (obestämd)
↑ Harald Atmanspacher. Cartesian cut, Heisenberg cut, and the concept of complexity // World Futures. - 1997-09-01. - T. 49 , nej. 3-4 . — S. 333–355 . — ISSN 0260-4027 . - doi : 10.1080/02604027.1997.9972639 .
↑ Cosma Rohilla Shalizi. Methods and Techniques of Complex Systems Science: An Overview // Complex Systems Science in Biomedicine / 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. Bullerinducerad stabilisering av Lorenz-systemet // Physical Review E. - 1995-11-01. - T. 52 , nej. 5 . — S. 4745–4749 . - doi : 10.1103/PhysRevE.52.4745 .
↑ Singh, Vijay P. Entropy Theory and its application in Environmental and Water Engineering : [ eng. ] . — John Wiley & Sons, 2013-01-10. — ISBN 978-1-118-42860-3 .
↑ Parrott, Lael (2010-11-01). "Mäta ekologisk komplexitet" . Ekologiska indikatorer _ ]. 10 (6): 1069-1076. DOI : 10.1016/j.ecolind.2010.03.014 . ISSN 1470-160X .
↑ Holger Lange. Tidsserieanalys i ekologi (engelska) // eLS. - American Cancer Society, 2006. - ISBN 978-0-470-01590-2 . - doi : 10.1038/npg.els.0003276 .
↑ Wang, Chaojun; Zhao, Hongrui (2019-04-18). "Analys av fjärranalys av tidsseriedata för att främja ekosystems hållbarhet: användning av tidsinformationsentropi" . International Journal of Remote Sensing . 40 (8): 2880-2894. DOI : 10.1080/01431161.2018.1533661 . ISSN 0143-1161 .
↑ Klemm, Otto; Lange, Holger (1999-12-01). "Trender av luftföroreningar i Fichtelgebirge-bergen, Bayern" . Miljövetenskap och föroreningsforskning ]. 6 (4): 193-199. DOI : 10.1007/BF02987325 . ISSN 1614-7499 .
↑ Wang, Kang; Lin, Zhongbing (2018). "Karakterisering av icke-punktföroreningar i floder i olika rumsliga skalor" . Vatten och miljötidning ]. 32 (3): 453-465. DOI : 10.1111/wej.12345 . ISSN 1747-6593 .
↑ Labat, David (2005-11-25). "Senaste framsteg i wavelet-analyser: Del 1. En genomgång av begrepp" . Journal of Hydrology ]. 314 (1): 275-288. DOI : 10.1016/j.jhydrol.2005.04.003 . ISSN 0022-1694 .
↑ Pachepsky, Yakov; Guber, Andrey; Jacques, Diederik; Simunek, Jiri; Van Genuchten, Marthinus Th.; Nicholson, Thomas; Cady, Ralph (2006-10-01). "Informationsinnehåll och komplexitet för simulerade markvattenflöden" . Geoderma . Fraktalgeometri tillämpad på jord och relaterade hierarkiska system - fraktaler , komplexitet och heterogenitet ]. 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). "Informationsteoretisk utvärdering av satellitinsamlingar av jordfuktighet" . Fjärranalys av miljön ]. 204 : 392-400. DOI : 10.1016/j.rse.2017.10.016 . HDL : 2060/20180003069 . ISSN 0034-4257 .
↑ Hauhs, Michael; Lange, Holger (2008). "Klassificering av avrinning i huvudvattenavrinningsområde: ett fysiskt problem?" . Geografikompass _ _ ]. 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). "Komplexitetsforskning av regionala grundvattendjupserier baserade på flerskalig entropi: en fallstudie av Jiangsanjiang Branch Bureau i Kina" . miljögeovetenskap _ _ ]. 70 (1): 353-361. DOI : 10.1007/s12665-012-2132-y . ISSN 1866-6299 .
↑ Xing, Jing; Manning, Carol A. (april 2005). "Komplexitets- och automationsvisningar av flygtrafikledning : litteraturgranskning och analys " ].
↑ Wang, Kang; Li, Li (november 2008). "Karakterisera heterogena flödesmönster med hjälp av informationsmätningar" . 2008 första internationella konferens om intelligenta nätverk och intelligenta system : 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, red., A Comparative Analysis of Detecting Symmetries in Toroidal Topology , Studies in Computational Intelligence, Springer International Publishing, sid. 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-316 > . Hämtad 7 april 2020.
↑ Han, Kaijian; Lu, Xingjing; Zou, Yingchao; Keung Lai, Kin (2015-09-01). "Prognos av metallpriser med en kurvbaserad multiskalmetodik" . Resurspolicy _ _ ]. 45 : 144-150. DOI : 10.1016/j.resourpol.2015.03.011 . ISSN 0301-4207 .
↑ Han, Kaijian; Xu, Yang; Zou, Yingchao; Tang, Ling (2015-05-01). "Prognoser för elpriser med en Curvelet denoising-baserad metod" . Physica A: Statistisk mekanik och dess tillämpningar ]. 425 :1-9. DOI : 10.1016/j.physa.2015.01.012 . ISSN 0378-4371 .
↑ Mosabber Uddin Ahmed. Komplexitetsanalys inom hälsoinformatik // Signalbehandlingstekniker för beräkningshälsoinformatik / 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. "Human Cognitive Complexity Analysis in Transportation Systems" . Logistik . Handlingar: 4361-4368. DOI : 10.1061/40996(330)637 .
↑ Zhang, Shutao; Qian, Jinwu; Shen, Linyong; Wu, Xi; Hu, Xiaowu (oktober 2015). "Gångkomplexitet och frekvensinnehållsanalyser av patienter med Parkinsons sjukdom" . 2015 International Symposium on Bioelectronics and Bioinformatics (ISBB) : 87–90. DOI : 10.1109/ISBB.2015.7344930 .
↑ Wang, Jisung; Nej, Gyu-Jeong; Choi, Byung-Moon; Ku, Seung-Woo; Joo, Pangyu; Jung, Woo-Sung; Kim, Seunghwan; Lee, Heonsoo (2017-07-13). "Undertryckt neural komplexitet under ketamin- och propofol-inducerad medvetslöshet" . Neurovetenskapsbrev [ engelska ] ]. 653 : 320-325. DOI : 10.1016/j.neulet.2017.05.045 . ISSN 0304-3940 .
↑ Michał Bola, Paweł Orłowski, Martyna Płomecka, Artur Marchewka. EEG-signaldiversitet under propofolsedering: en ökning av sederade men lyhörda, en minskning av sederade och icke-svarande patienter // bioRxiv . — 2019-01-30. - P. 444281 . - doi : 10.1101/444281 .
↑ Fan Yingle; Wu Chuayan; Li Yi; Pang Quan (2006-12-15). "Studie om tillämpningen av fluktuationskomplexitetsmätning i taländpunktsdetektering" . Flygmedicin och medicinsk teknik . 19 (6). ISSN 1002-0837 .
↑ Dilger, Alexander (2012-01-01). "Endogen komplexitet, specialisering och allmänbildning" . På horisonten . 20 (1):49-53. DOI : 10.1108/10748121211202062 . ISSN 1074-8121 .
↑ Ivanyuk, Vera Alekseevna Dynamisk modell för strategisk investeringsportföljförvaltning . elibrary.ru (2015). (obestämd)
↑ Javid, Mohammad Ali Javaheri; Blackwell, Tim; Zimmer, Robert; al-Rifaie, Mohammad Majid (2016). Johnson, Collin; Ciesielski, Vic; Correia, João; Machado, Penousal, red. "Korrelation mellan mänskligt estetiskt omdöme och rumslig komplexitetsmått" . Evolutionär och biologiskt inspirerad musik, ljud, konst och design . Föreläsningsanteckningar i datavetenskap ]. Cham: Springer International Publishing: 79-91. DOI : 10.1007/978-3-319-31008-4_6 . ISBN 978-3-319-31008-4 .