Komplexitás (információelmélet)

Az információ-fluktuáció komplexitása  egy információelméleti érték, amelyet az információ információs entrópiához viszonyított fluktuációjaként határoznak meg . Egy dinamikus rendszerben a rend és a káosz elterjedtségének ingadozásaiból származik, és a tudás különböző területein használják a komplexitás mérésére . Az elméletet Bates és Shepard munkájában mutatták be 1993-ban [1] .

Definíció

Egy diszkrét dinamikus rendszer információ-fluktuációs komplexitása ennek a rendszernek a véletlenszerű adatbevitelnek kitett állapotainak valószínűségi eloszlásának függvénye. A gazdag információforrással, például véletlenszám-generátorral vagy fehérzajjellel rendelkező rendszer vezérlésének célja a rendszer belső dinamikájának feltárása, ugyanúgy , mint a jelfeldolgozásban frekvenciában gazdag impulzusok használata .

Ha a rendszernek vannak lehetséges állapotai és ismertek az állapotok valószínűségei , akkor információs entrópiája egyenlő

hol  van a saját állapotinformáció .

Egy rendszer információ-fluktuációs komplexitását az átlagértéktől való szórásként vagy fluktuációként határozzuk meg :

vagy

Az állapotinformáció fluktuációja nulla egy maximálisan rendezetlen rendszerben minden ; a rendszer egyszerűen szimulálja a véletlenszerű adatbevitelt. akkor is nulla, ha a rendszer tökéletesen rendezett, és csak egy rögzített állapota van , függetlenül a bemenetektől. nem nulla e két szélsőség között, ha nagy valószínűségű és kis valószínűségű állapotok is lehetségesek kitölteni az állapotteret.

Az információ fluktuációja memóriát és számítást biztosít

Ahogy egy összetett dinamikus rendszer időben fejlődik, egyik állapotból a másikba kerül. Az, hogy ezek az átmenetek hogyan történnek, szabálytalan módon a külső ingerektől függ. Egyes esetekben a rendszer érzékenyebb lehet a külső ingerekre (instabil), míg más esetekben kevésbé érzékeny (stabil). Ha egy adott állapotnak több lehetséges következő állapota van, akkor a külső információ határozza meg, hogy melyik lesz a következő, és a rendszer ezt az információt az állapottérben egy bizonyos pályát követve szerzi meg. De ha több különböző állapot vezet ugyanahhoz a következő állapothoz, akkor a belépéskor a rendszer elveszti az információt arról, hogy melyik állapot előzte meg. Így, ahogyan az idő múlásával fejlődik, egy összetett rendszer váltakozó információnyereséget és -veszteséget mutat. Az információ váltakozása vagy fluktuációja egyenértékű az emlékezéssel és a felejtéssel – az információ vagy az emlékezet átmeneti tárolásával – ez a nem triviális számítások lényeges jellemzője.

Az állapotátmeneteket kísérő információnyerés vagy -vesztés saját állapotinformációihoz társítható. Az állapotból állapotba való átmenet során a nettó információnyereség az állapotból való  kilépéskor kapott információ mínusz az állapotba lépéskor keletkező információveszteség :

Itt  van annak a közvetlen feltételes valószínűsége , hogy ha az aktuális állapot , akkor a következő állapot lesz, és  az az inverz feltételes valószínűsége annak , hogy ha az aktuális állapot , akkor az előző állapot volt . A feltételes valószínűségek az átmenet valószínűségéhez kapcsolódnak, annak a valószínűségéhez, hogy az állapotból állapotba kerül átmenet :

A feltételes valószínűségeket kiküszöbölve a következőket kapjuk:

Ezért az átmenet eredményeként a rendszer által nyert nettó információ csak a kezdeti állapotból a végső állapotba való állapotinformáció növekedésétől függ. Kimutatható, hogy ez több egymást követő átmenetre is igaz [1] .

A képlet hasonlít az erő és a potenciális energia kapcsolatára . hasonló a potenciális energiához , és a képletben  szereplő erő . A külső információ "felfelé löki" a rendszert, egy magasabb információs potenciállal rendelkező állapotba az emlékezetmegőrzés szempontjából, ahogyan egy bizonyos tömegű test felfelé, nagyobb gravitációs potenciálú állapotba taszítása is energia felhalmozódásához vezet. A tárolt energia mennyisége csak a végmagasságtól függ, a felfelé vezető úttól nem. Hasonlóképpen, a tárolt információ mennyisége független a két állapot közötti átmeneti úttól. Amint egy rendszer elér egy ritka, magas információs potenciállal rendelkező állapotot, „visszaeshet” a normál állapotba, elveszítve a korábban tárolt információkat.

Hasznos lehet kiszámítani az átlagtól (ami nulla) a szórást, vagyis a nettó információnyereség ingadozását [1] , de figyelembe veszi a több átmenetes állapottér memóriaciklusokat , ezért pontosabbnak kell lennie. a rendszer feldolgozási teljesítményének mutatója. Sőt, könnyebb is kiszámolni, hiszen sokkal több átmenet lehet, mint állapot.

Káosz és rend

Egy dinamikus rendszer, amely érzékeny a külső információkra (instabil) , kaotikus viselkedést mutat, míg a külső információkra érzéketlen (stabil) rendszer rendezett viselkedést mutat. A gazdag információforrás hatására egy komplex rendszer mindkét viselkedést felmutatja, dinamikus egyensúlyban ingadozva közöttük. A fluktuáció mértékét mennyiségileg mérjük ; a káosz és a rend túlsúlyának váltakozását örökíti meg egy összetett rendszerben, ahogyan az idővel alakul.

Példa: az elemi cellás automata egy változata a 110. szabály szerint

Bebizonyosodott , hogy az elemi cellás automata 110-es szabály szerinti változata képes univerzális számításokra . A bizonyíték a "vitorlázó" vagy " űrhajó " néven ismert összekapcsolt és önmegtartó sejtkonfigurációk létezésén és kölcsönhatásán alapul , a felbukkanás jelenségén , amely magában foglalja az automata sejtcsoportok azon képességét, hogy emlékezzenek arra, hogy egy sikló halad át rajtuk. Ezért arra kell számítani, hogy az állapottérben memóriahurkok lépnek fel, az információszerzés és -veszteség váltakozása, instabilitás és stabilitás, káosz és rend eredményeként.

Tekintsünk egy cellás automata három szomszédos cellájából álló csoportot, amelyek engedelmeskednek a 110-es szabálynak:vég-közép-vég. A középső cella következő állapota az aktuális állapotától és a levélsejtektől függ, a szabályban meghatározottak szerint:

Elemi sejtautomatika 110. szabály.
3 sejtcsoport 1-1-1 1-1-0 1-0-1 1-0-0 0-1-1 0-1-0 0-0-1 0-0-0
következő középső cella 0 egy egy 0 egy egy egy 0

Ennek a rendszernek az információ-ingadozási komplexitásának kiszámításához egy vezérlőcellát kell csatlakoztatni egy 3 sejtből álló csoport mindkét végéhez, hogy véletlenszerű külső ingert, pl.driver→end-center-end←illesztőprogram, így a szabály alkalmazható a két végcellára. Ezután meg kell határoznia, hogy mi a következő állapot minden lehetséges aktuális állapothoz és az illesztőprogram-cellatartalom minden lehetséges kombinációjához, hogy kiszámítsa a közvetlen feltételes valószínűségeket.

A rendszer állapotdiagramja az alábbiakban látható. Ebben a körök az állapotokat, a nyilak pedig az állapotok közötti átmeneteket jelölik. Ennek a rendszernek a nyolc állapota, től1-1-1előtt0-0-0egy 3 cellából álló csoport 3 bites tartalmának decimális megfelelőivel vannak számozva: 7-től 0-ig. Az átmeneti nyilak közelében a közvetlen feltételes valószínűségek értékei láthatók. A séma változékonyságot mutat a nyilak divergenciájában és konvergenciájában, ami megfelel a káosz és a rend változékonyságának, az érzékenységnek és az érzéketlenségnek, a külső információ megszerzésének és elvesztésének a vezetőcellákból.

A közvetlen feltételes valószínűségeket az adott átmenetet szabályozó meghajtócella lehetséges tartalmának aránya határozza meg. Például két illesztőprogram-cella tartalmának négy lehetséges kombinációja esetén a 7-es állapot az 5-ös, 4-es, 1-es és 0-s állapotokhoz vezet, tehát , , és 1/4 vagy 25%. Hasonlóképpen, a 0 állapot a 0, 1, 0 és 1 állapotokhoz vezet, tehát 1/2 vagy 50% felel meg. Stb.

Az állapotvalószínűségeket a képlet kapcsolja össze

és

Ezek a lineáris algebrai egyenletek manuálisan vagy számítógépes programmal megoldhatók állapotvalószínűségek meghatározására, a következő eredményekkel:

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

Az információ entrópiája és összetettsége az állapotvalószínűségből számítható ki:

denevér, bit.

Meg kell jegyezni, hogy nyolc állapot esetén a lehetséges maximális entrópia egy bittel egyenlő, ami megfelel annak az esetnek, amikor mind a nyolc állapot egyenlő valószínűséggel, 1/8 valószínűséggel (kaotikus). Ezért a 110-es szabály viszonylag magas entrópiával vagy állapothasználattal rendelkezik, 2,86 bit. Ez azonban nem zárja ki az állapotinformáció szignifikáns ingadozását az entrópiához képest, és ebből következően a nagyfokú komplexitást. Míg a maximális entrópia kizárná a bonyolultságot.

Egy alternatív módszer használható az állapotvalószínűségek meghatározására, ha a fent leírt analitikai módszer nem kivitelezhető. Ez abból áll, hogy a rendszert a bemenetein (meghajtó cellákon) keresztül vezetjük véletlenszerű forrással sok generáción keresztül, és empirikusan megfigyeljük az állapotvalószínűségeket. 10 millió generáción keresztül végzett számítógépes szimulációval az eredmények a következők: [2]

Információs változók egy elemi cellás automatához a 110. szabály szerint
sejtek száma 3 négy 5 6 7 nyolc 9 tíz tizenegy 12 13
(bit) 2.86 3.81 4.73 5.66 6.56 7.47 8.34 9.25 10.09 10.97 11.78
(bit) 0,56 0,65 0,72 0,73 0,79 0,81 0,89 0,90 1.00 1.01 1.15
0,20 0.17 0,15 0.13 0.12 0.11 0.11 0.10 0.10 0,09 0.10

Mivel mindkét paraméter és , növekszik a rendszer méretével, a különböző méretű rendszerek jobb összehasonlítása érdekében a dimenzió nélküli relációt , a relatív információ-fluktuáció összetettségét javasoljuk. Megjegyezzük, hogy az empirikus és analitikai eredmények konzisztensek egy 3 cellás automatánál.

Bates és Shepard [1] munkájában az elemi sejtautomaták összes szabályára kiszámították, és észrevették, hogy azok, amelyek lassan mozgó "vitorlázógépeket" és esetleg álló objektumokat mutatnak, például a 110-es szabály, szorosan összefüggnek. nagy értékekkel . Ezért szűrőként használható univerzális számításra alkalmas szabályok kiválasztásakor, amit fárasztó bizonyítani.

Alkalmazások

Bár az információingadozási komplexitás képletének levezetése egy dinamikus rendszerben lévő információ ingadozásain alapul, maga a képlet csak az állapotvalószínűségtől függ, ezért bármilyen valószínűségi eloszlásra is alkalmazható, beleértve a statikus képekből vagy szövegekből származókat is.

Az évek során az eredeti cikkre [1] számos különböző terület kutatói hivatkoztak: komplexitáselmélet [3] , komplex rendszertudomány [4] , kaotikus dinamika [5] , környezetmérnöki [6] , ökológiai komplexitás [7]. , ökológiai idősor elemzés [8] , ökoszisztéma ellenálló képessége [9] , légszennyezés [10] és víz [11] , hidrológiai hullámelem elemzés [12] , vízáramlások modellezése a talajban [13] , talajnedvesség [14] , vízgyűjtő lefolyás [15] , talajvízmélység [16] , légiforgalmi irányítás [17] , áramlási minta [18] , topológia [19] , fémek [20] és villamos energia árának piaci előrejelzése [21] , egészségügyi informatika [22] , emberi megismerés [23] , emberi járáskinematika [24] neurológia [25] EEG analízis [26] beszédelemzés [27] oktatás [28] befektetés [29] esztétika [30] .

Linkek

  1. 1 2 3 4 5 John E. Bates, Harvey K. Shepard. Bonyolultság mérése információs fluktuáció segítségével  (angol)  // Physics Letters A. — 1993-01-18. — Vol. 172 , iss. 6 . — P. 416–425 . — ISSN 0375-9601 . - doi : 10.1016/0375-9601(93)90232-O .
  2. Bates, John E. A komplexitás mérése információ-fluktuáció segítségével: oktatóanyag . Kutatási kapu (2020. március 30.).
  3. Harald Atmanspacher. Descartes-vágás, Heisenberg-vágás és a komplexitás fogalma  // World Futures. - 1997-09-01. - T. 49 , sz. 3-4 . – S. 333–355 . — ISSN 0260-4027 . - doi : 10.1080/02604027.1997.9972639 .
  4. Cosma Rohilla Shalizi. A komplex rendszertudomány módszerei és technikái: áttekintés  //  Komplex rendszertudomány a biomedicinában / Thomas S. Deisboeck, J. Yasha Kresh. – Boston, MA: Springer US, 2006. – P. 33–114 . — ISBN 978-0-387-33532-2 . - doi : 10.1007/978-0-387-33532-2_2 .
  5. Renate Wackerbauer. A Lorenz-rendszer zaj által kiváltott stabilizálása  // Fizikai Szemle E. - 1995-11-01. - T. 52 , sz. 5 . — S. 4745–4749 . - doi : 10.1103/PhysRevE.52.4745 .
  6. Singh, Vijay P. Az entrópiaelmélet és alkalmazása a környezet- és vízmérnökökben  : [ eng. ] . – John Wiley & Sons, 2013. 01. 10. — ISBN 978-1-118-42860-3 .
  7. Parrott, Lael (2010-11-01). „Az ökológiai komplexitás mérése” . Ökológiai mutatók _ ]. 10 (6): 1069-1076. DOI : 10.1016/j.ecolind.2010.03.014 . ISSN 1470-160X . 
  8. Holger Lange. Idősoros elemzés az ökológiában  (angol)  // eLS. - American Cancer Society, 2006. - ISBN 978-0-470-01590-2 . - doi : 10.1038/npg.els.0003276 .
  9. Wang, Chaojun; Zhao, Hongrui (2019-04-18). „A távérzékelési idősoros adatok elemzése az ökoszisztéma fenntarthatóságának elősegítésére: az időbeli információs entrópia használata ” International Journal of Remote Sensing . 40 (8): 2880-2894. DOI : 10.1080/01431161.2018.1533661 . ISSN  0143-1161 .
  10. Klemm Ottó; Lange, Holger (1999-12-01). „A légszennyezés tendenciái a Fichtelgebirge-hegységben, Bajorország” . Környezettudományi és környezetszennyezési kutatás ]. 6 (4): 193-199. DOI : 10.1007/BF02987325 . ISSN 1614-7499 . 
  11. Wang, Kang; Lin, Zhongbing (2018). „A folyó nem pontszerű forrású szennyezésének jellemzése különböző térbeli léptékekben” . Water and Environment Journal ]. 32 (3): 453-465. DOI : 10.1111/wej.12345 . ISSN 1747-6593 . 
  12. Labat, David (2005-11-25). „A wavelet elemzések legújabb eredményei: 1. rész. A fogalmak áttekintése” . Hidrológiai folyóirat _ ]. 314 (1): 275-288. DOI : 10.1016/j.jhydrol.2005.04.003 . ISSN  0022-1694 .
  13. Pacsepszkij, Jakov; Guber, Andrej; Jacques, Diederik; Simunek, Jiri; Van Genuchten, Marthinus Th.; Nicholson, Thomas; Cady, Ralph (2006-10-01). „A szimulált talajvízáramlások információtartalma és összetettsége” . Geoderma . Fraktálgeometria a talajra és a kapcsolódó hierarchikus rendszerekre - Fraktálok , összetettség és heterogenitás ]. 134 (3): 253-266. DOI : 10.1016/j.geoderma.2006.03.003 . ISSN  0016-7061 .
  14. Kumar, Sujay V.; Dirmeyer, Paul A.; Peters-Lidard, Christa D.; Bindlish, Rajat; Bolten, John (2018-01-01). „Műholdas talajnedvesség-lekérdezések információelméleti értékelése” . A környezet távérzékelése ]. 204 , 392-400. DOI : 10.1016/j.rse.2017.10.016 . HDL : 2060/20180003069 . ISSN 0034-4257 . 
  15. Hauhs, Michael; Lange, Holger (2008). „A lefolyás osztályozása a felső vízgyűjtőkben: fizikai probléma?” . Földrajzi iránytű _ ]. 2 (1): 235-254. DOI : 10.1111/j.1749-8198.2007.00075.x . ISSN 1749-8198 . 
  16. Liu, Meng; Liu Dong; Liu, Le (2013-09-01). „A többléptékű entrópián alapuló regionális talajvízmélységi sorozatok komplexitási kutatása: a Jiangsanjiang Branch Bureau Kínában esettanulmánya” . környezeti földtudományok _ ]. 70 (1): 353-361. DOI : 10.1007/s12665-012-2132-y . ISSN  1866-6299 .
  17. Xing, Jing; Manning, Carol A. (2005. április). „A légiforgalmi irányítás összetettsége és automatizálása : Irodalom áttekintése és elemzése ” ].
  18. Wang, Kang; Li, Li (2008. november). „Heterogén áramlási minták jellemzése információs mérések segítségével” . 2008. első nemzetközi konferencia az intelligens hálózatokról és intelligens rendszerekről : 654-657. DOI : 10.1109/ICINIS.2008.110 .
  19. Javaheri Javid, Mohammad Ali; Alghamdi, Wajdi; Zimmer, Robert és al-Rifaie, Mohammad Majid (2016), Bi, Yaxin; Kapoor, Supriya & Bhatia, Rahul, eds., A Comparative Analysis of Detecting Symmetries in Toroidal Topology , Studies in Computational Intelligence, 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-1336 > . Letöltve: 2020. április 7. 
  20. Ő, Kaijian; Lu, Xingjing; Zou, Yingchao; Keung Lai, Kin (2015-09-01). „Fémárak előrejelzése görbe alapú többléptékű módszertannal” . Erőforrás -irányelv _ ]. 45 , 144-150. DOI : 10.1016/j.resourpol.2015.03.011 . ISSN 0301-4207 . 
  21. Ő, Kaijian; Xu, Yang; Zou, Yingchao; Tang, Ling (2015-05-01). „Villamosáram-előrejelzések Curvelet zajtalanítás alapú megközelítéssel” . Physica A: Statisztikai mechanika és alkalmazásai ]. 425 :1-9. DOI : 10.1016/j.physa.2015.01.012 . ISSN  0378-4371 .
  22. Mosabber Uddin Ahmed. Complexity Analysis in Health Informatics  //  Signal Processing Techniques for Computational Health Informatics / 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 .
  23. Shi Xiujian; Sun Zhiqiang; Li Long; Xie Hongwei. „Az emberi kognitív komplexitás elemzése a közlekedési rendszerekben” . Logisztika . Eljárás: 4361-4368. DOI : 10.1061/40996(330)637 .
  24. Zhang, Shutao; Qian, Jinwu; Shen, Linyong; Wu, Xi; Hu, Xiaowu (2015. október). „Parkinson-kóros betegek járáskomplexitásának és gyakoriságának tartalmi elemzése” . 2015 International Symposium on Bioelectronics and Bioinformatics (ISBB) : 87–90. DOI : 10.1109/ISBB.2015.7344930 .
  25. Wang, Jisung; Noh, Gyu-Jeong; Choi, Byung-Moon; Ku, Seung-Woo; Joo, Pangyu; Jung, Woo-Sung; Kim, Seunghwan; Lee, Heonsoo (2017-07-13). „Elnyomott idegi komplexitás a ketamin és propofol által kiváltott eszméletvesztés során ” Neuroscience Letters [ angol ] ]. 653 , 320-325. DOI : 10.1016/j.neulet.2017.05.045 . ISSN  0304-3940 .
  26. Michał Bola, Paweł Orłowski, Martyna Płomecka, Artur Marchewka. Az EEG-jelek sokfélesége a propofol szedáció során: a szedált, de reagáló betegek számának növekedése, a szedált és nem reagáló alanyok számának csökkenése   // bioRxiv . — 2019-01-30. - P. 444281 . - doi : 10.1101/444281 .
  27. Fan Yingle; Wu Chuanyan; Li Yi; Pang Quan (2006. 12. 15.). „Tanulmány a fluktuációs komplexitás mérésének alkalmazásáról a beszédvégpont-észlelésben” . Repülési gyógyászat és orvostechnika . 19. (6). ISSN  1002-0837 .
  28. Dilger, Alexander (2012-01-01). „Endogén komplexitás, specializáció és általános műveltség” . A Horizonton . 20 (1), 49-53. DOI : 10.1108/10748121211202062 . ISSN  1074-8121 .
  29. Ivanyuk, Vera Alekseevna A stratégiai befektetési portfóliókezelés dinamikus modellje . elibrary.ru (2015).
  30. Javid, Mohammad Ali Javaheri; Blackwell, Tim; Zimmer, Robert; al-Rifaie, Mohammad Majid (2016). Johnson, Collin; Ciesielski, Vic; Correia, João; Machado, Penousal, szerk. „Az emberi esztétikai megítélés és a térbeli komplexitás mérése közötti összefüggés” . Evolúciós és biológiai ihletésű zene, hang, művészet és design . Előadásjegyzetek számítástechnikából ]. Cham: Springer International Publishing: 79-91. DOI : 10.1007/978-3-319-31008-4_6 . ISBN  978-3-319-31008-4 .