Monimutkaisuus (informaatioteoria)

Tietojen vaihtelun monimutkaisuus  on informaatioteoreettinen arvo, joka määritellään informaation vaihteluksi suhteessa informaation entropiaan . Se on johdettu järjestyksen ja kaaoksen esiintyvyyden vaihteluista dynaamisessa järjestelmässä, ja sitä käytetään monilla tiedon aloilla monimutkaisuuden mittaamiseen . Teoria esiteltiin Batesin ja Shepardin teoksissa vuonna 1993 [1] .

Määritelmä

Diskreetin dynaamisen järjestelmän informaation vaihtelun monimutkaisuus on funktio tämän järjestelmän satunnaisten datasyötteiden tilojen todennäköisyysjakaumasta . Runsaan tietolähteen, kuten satunnaislukugeneraattorin tai valkoisen kohinasignaalin , järjestelmän ohjaamisen tavoitteena on tutkia järjestelmän sisäistä dynamiikkaa samalla tavalla kuin signaalinkäsittelyssä käytetään taajuista pulssia .

Jos järjestelmällä on mahdollisia tiloja ja tilojen todennäköisyydet tunnetaan, niin sen informaatioentropia on yhtä suuri kuin

missä  on oma tilatieto .

Järjestelmän informaation vaihtelun monimutkaisuus määritellään standardipoikkeamaksi tai vaihteluksi sen keskiarvosta :

tai

Tilainformaation vaihtelu on nolla maksimaalisessa epäjärjestyneessä järjestelmässä, jossa on kaikki ; järjestelmä yksinkertaisesti simuloi satunnaisia ​​datasyötteitä. on myös nolla, kun järjestelmä on täysin järjestetty ja sillä on vain yksi kiinteä tila tuloista riippumatta. on nollasta erilainen näiden kahden ääripään välillä, kun sekä suuren todennäköisyyden tilat että pienen todennäköisyyden tilat ovat mahdollisia täyttämään tila-avaruuden.

Tiedon vaihtelut tarjoavat muistia ja laskentaa

Kun monimutkainen dynaaminen järjestelmä kehittyy ajan myötä, se siirtyy tilasta toiseen. Kuinka nämä siirtymät tapahtuvat, riippuu ulkoisista ärsykkeistä epäsäännöllisellä tavalla. Joissakin tapauksissa järjestelmä voi olla herkempi ulkoisille ärsykkeille (epävakaa), kun taas toisissa se voi olla vähemmän herkkä (vakaa). Jos tietyssä tilassa on useita mahdollisia seuraavaa tiloja, ulkoinen tieto määrittää, mikä niistä on seuraava, ja järjestelmä saa tämän tiedon seuraamalla tiettyä liikerataa tila-avaruudessa. Mutta jos useat eri tilat johtavat samaan seuraavaan tilaan, niin siihen tullessa järjestelmä menettää tiedon siitä, mikä tila sitä edelsi. Siten monimutkainen järjestelmä kehittyy ajan myötä, ja se tuottaa vuorotellen tiedon hyötyjä ja menetyksiä. Tiedon vuorottelut tai heilahtelut merkitsevät muistamista ja unohtamista - tiedon tai muistin väliaikaista tallentamista - tämä on ei-triviaalisten laskelmien olennainen piirre.

Tilasiirtymien mukana tuleva tiedon saanti tai menetys voidaan liittää sen omaan tilatietoon. Tiedon nettovoitto tilasta tilaan siirtymisen aikana  on tiedosta, joka saadaan tilasta poistuttaessa miinus tiedon menetys tilaan siirtyessä :

Tässä  on suora ehdollinen todennäköisyys sille , että jos nykyinen tila on , niin seuraava tila on ja  on käänteinen ehdollinen todennäköisyys sille , että jos nykyinen tila on , niin edellinen tila oli . Ehdolliset todennäköisyydet liittyvät siirtymän todennäköisyyteen, todennäköisyyteen, että siirtyminen tilasta tilaan tapahtuu , seuraavilla tavoilla:

Eliminoimalla ehdolliset todennäköisyydet, saamme:

Siksi järjestelmän siirtymän seurauksena saama nettoinformaatio riippuu vain tilainformaation lisääntymisestä alkutilasta lopputilaan. Voidaan osoittaa, että tämä pätee jopa useille peräkkäisille siirtymille [1] .

Kaava muistuttaa voiman ja potentiaalisen energian suhdetta . on samanlainen kuin potentiaalienergia ja on kaavan  voima . Ulkoinen informaatio "työntää" järjestelmän "ylös", tilaan, jossa on korkeampi tietopotentiaali muistin säilyttämiseksi, aivan kuten jonkin massan omaavan kehon työntäminen ylämäkeen tilaan, jossa on korkeampi gravitaatiopotentiaali, johtaa energian kertymiseen. Varastoidun energian määrä riippuu vain loppukorkeudesta, ei matkasta ylämäkeen. Samoin tallennetun tiedon määrä on riippumaton kahden tilan välisestä siirtymäpolusta. Kun järjestelmä saavuttaa harvinaisen korkean informaatiopotentiaalin tilan, se voi "pudota" takaisin normaalitilaan ja menettää aiemmin tallennetun tiedon.

Voi olla hyödyllistä laskea standardipoikkeama sen keskiarvosta (joka on nolla), eli nettoinformaatiovahvistuksen vaihtelu [1] , mutta se ottaa huomioon usean siirtymän tila-avaruusmuistin syklit ja sen pitäisi olla tarkempi. järjestelmän prosessointitehon indikaattori. Lisäksi se on helpompi laskea, koska siirtymiä voi olla paljon enemmän kuin tiloja.

Kaaos ja järjestys

Dynaaminen järjestelmä, joka on herkkä ulkoiselle informaatiolle (epävakaa) , käyttäytyy kaoottisesti , kun taas järjestelmä, joka ei ole herkkä ulkoiselle informaatiolle (stabiili), käyttäytyy järjestyneesti. Runsaan tietolähteen vaikutuksen alaisena monimutkainen järjestelmä osoittaa molempia käyttäytymismalleja, värähteleen niiden välillä dynaamisessa tasapainossa. Vaihtelun aste mitataan kvantitatiivisesti ; se vangitsee kaaoksen ja järjestyksen vallitsevan vaihtelun monimutkaisessa järjestelmässä, kun se kehittyy ajan myötä.

Esimerkki: alkeissoluautomaatin variantti säännön 110 mukaisesti

On osoitettu , että säännön 110 mukainen alkeissoluautomaatin muunnos kykenee universaaleihin laskelmiin . Todistus perustuu toisiinsa yhdistettyjen ja itsesäilyttävien solukokoonpanojen olemassaoloon ja vuorovaikutukseen, joka tunnetaan nimellä "liittimet" tai " avaruusalukset ", ilmaantumisen ilmiö , joka tarkoittaa automaatiosoluryhmien kykyä muistaa, että purjelentokone kulkee niiden läpi. Siksi on odotettavissa, että tila-avaruudessa esiintyy muistisilmukoita tiedon saannin ja menetyksen, epävakauden ja vakauden, kaaoksen ja järjestyksen vuorottelun seurauksena.

Tarkastellaan soluautomatin kolmen vierekkäisen solun ryhmää, jotka noudattavat sääntöä 110:pää-keskus-pää. Keskisolun seuraava tila riippuu sen nykyisestä tilasta ja lehtisoluista säännön mukaisesti:

Perussolukkoautomaatin sääntö 110.
3 solun ryhmä 1-1-1 1-1-0 1-0-1 1-0-0 0-1-1 0-1-0 0-0-1 0-0-0
seuraava keskisolu 0 yksi yksi 0 yksi yksi yksi 0

Tämän järjestelmän informaation vaihtelun monimutkaisuuden laskemiseksi kiinnittäisi ajurisolu 3 solun ryhmän kumpaankin päähän, jotta saataisiin satunnainen ulkoinen ärsyke, esim.kuljettaja→päätekeskus-pään←ohjain, jotta sääntöä voidaan soveltaa kahteen päätysoluun. Sen on sitten määritettävä, mikä on seuraava tila kullekin mahdolliselle nykyiselle tilalle ja kullekin mahdolliselle ajurisolujen sisällön yhdistelmälle laskeakseen suorat ehdolliset todennäköisyydet.

Tämän järjestelmän tilakaavio on esitetty alla. Siinä ympyrät edustavat tiloja ja nuolet tilojen välisiä siirtymiä. Tämän järjestelmän kahdeksan tilaa alkaen1-1-1ennen0-0-0on numeroitu 3 solun ryhmän 3-bittisen sisällön desimaalivastineilla: 7 - 0. Siirtymänuolien lähellä näytetään suorien ehdollisten todennäköisyyksien arvot. Kaaviossa näkyy vaihtelua nuolien hajoamisessa ja konvergenssissa, mikä vastaa vaihtelua kaaoksessa ja järjestyksessä, herkkyyttä ja epäherkkyyttä, ulkoisen tiedon hankintaa ja menetystä kuljettajasoluista.

Suorat ehdolliset todennäköisyydet määräytyvät tietyn siirtymän ohjaavan ajurisolun mahdollisen sisällön osuuden perusteella. Esimerkiksi neljälle mahdolliselle kahden ohjainsolun sisällön yhdistelmälle tila 7 johtaa tiloihin 5, 4, 1 ja 0, joten , , ja ovat 1/4 tai 25%. Samoin tila 0 johtaa tiloihin 0, 1, 0 ja 1, joten 1/2 eli 50 % vastaa . Ja niin edelleen.

Tilatodennäköisyydet suhteutetaan kaavalla

ja

Nämä lineaariset algebralliset yhtälöt voidaan ratkaista manuaalisesti tai tilatodennäköisyyksien tietokoneohjelmalla seuraavin tuloksin:

p0 _ p1_ _ p2 _ p 3 p4 _ p5_ _ p6 _ s. 7
2/17 2/17 1/34 5/34 2/17 2/17 2/17 4/17

Tiedon entropia ja monimutkaisuus voidaan laskea tilatodennäköisyyksistä:

lepakko, bitti.

On huomattava, että suurin mahdollinen entropia kahdeksalle tilalle on yhtä suuri kuin bitti, mikä vastaa tapausta, jossa kaikki kahdeksan tilaa ovat yhtä todennäköisiä, todennäköisyyksillä 1/8 (kaaoottinen). Siksi säännöllä 110 on suhteellisen korkea entropia tai tilan käyttö 2,86 bittiä. Tämä ei kuitenkaan sulje pois tilatiedon merkittävää vaihtelua suhteessa entropiaan ja näin ollen suurta monimutkaisuutta. Suurin entropia sulkee pois monimutkaisuuden.

Vaihtoehtoista menetelmää voidaan käyttää tilatodennäköisyyksien saamiseksi, kun edellä kuvattu analyyttinen menetelmä ei ole käyttökelpoinen. Se koostuu järjestelmän ohjaamisesta sen tulojen (ohjainsolujen) läpi satunnaisen lähteen kautta useiden sukupolvien ajan ja tilatodennäköisyyksien tarkkailemisesta empiirisesti. Kun tietokonesimulaatioita tehdään 10 miljoonan sukupolven ajan, tulokset ovat seuraavat: [2]

Tietomuuttujat alkeissoluautomaatille säännön 110 mukaan
solujen määrä 3 neljä 5 6 7 kahdeksan 9 kymmenen yksitoista 12 13
(bitti) 2.86 3.81 4.73 5.66 6.56 7.47 8.34 9.25 10.09 10.97 11.78
(bitti) 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

Koska molemmat parametrit ja , kasvavat järjestelmän koon myötä, erikokoisten järjestelmien paremman vertailun vuoksi ehdotetaan dimensioimatonta suhdetta , suhteellinen informaation vaihtelun monimutkaisuus. Huomaa, että empiiriset ja analyyttiset tulokset ovat yhdenmukaisia ​​3-kennoisen automaatin kohdalla.

Batesin ja Shepardin [1] teoksessa se on laskettu kaikille alkeissoluautomaattien säännöille, ja havaittiin, että ne, joissa on hitaasti liikkuvia "liitolaitteita" ja mahdollisesti paikallaan olevia esineitä, esimerkiksi sääntö 110, liittyvät läheisesti suurilla arvoilla . Siksi sitä voidaan käyttää suodattimena valittaessa yleiseen laskemiseen kykeneviä sääntöjä, minkä todistaminen on työlästä.

Sovellukset

Vaikka tiedon vaihtelun monimutkaisuuskaavan johtaminen perustuu dynaamisen järjestelmän informaation vaihteluihin, itse kaava riippuu vain tilatodennäköisyyksistä ja siksi sitä voidaan soveltaa myös mihin tahansa todennäköisyysjakaumaan, mukaan lukien staattisista kuvista tai tekstistä johdettuihin.

Alkuperäiseen artikkeliin [1] ovat vuosien varrella viitanneet useiden eri alojen tutkijat: monimutkaisuusteoria [3] , monimutkainen järjestelmätiede [4] , kaoottinen dynamiikka [5] , ympäristötekniikka [6] , ekologinen monimutkaisuus [7] . , ekologinen aikasarjaanalyysi [8] , ekosysteemin sietokyky [9] , ilmansaasteet [10] ja vesi [11] , hydrologinen aallokeanalyysi [12] , vesivirtausten mallintaminen maaperässä [13] , maaperän kosteus [14] , vedenjakaja valuma [15] , pohjaveden syvyys [16] , lennonjohto [17] , virtauskuvio [18] , topologia [19] , metallien [20] ja sähkön [21] hintojen markkinaennuste , terveysinformatiikka [22] , ihmisen kognitio [23] , ihmisen kävelykinematiikka [24] neurologia [25] EEG-analyysi [26] puheanalyysi [27] koulutus [28] investoiminen [29] estetiikka [30] .

Linkit

  1. 1 2 3 4 5 John E. Bates, Harvey K. Shepard. Monimutkaisuuden mittaaminen informaation fluktuaatiolla  (englanniksi)  // Physics Letters A. — 1993-01-18. — Voi. 172 , iss. 6 . — s. 416–425 . — ISSN 0375-9601 . - doi : 10.1016/0375-9601(93)90232-O .
  2. Bates, John E. Monimutkaisuuden mittaaminen tiedon vaihtelun avulla: opetusohjelma . Research Gate (30. maaliskuuta 2020).
  3. Harald Atmanspacher. Karteesinen leikkaus, Heisenberg-leikkaus ja monimutkaisuuden käsite  // World Futures. - 1.9.1997. - T. 49 , no. 3-4 . — S. 333–355 . — ISSN 0260-4027 . - doi : 10.1080/02604027.1997.9972639 .
  4. Cosma Rohilla Shalizi. Monimutkaisen järjestelmätieteen menetelmät ja tekniikat: Yleiskatsaus  //  Kompleksijärjestelmätiede biolääketieteessä / 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 .
  5. Renate Wackerbauer. Lorenz-järjestelmän melun aiheuttama stabilointi  // Physical Review E. - 1995-11-01. - T. 52 , no. 5 . — S. 4745–4749 . - doi : 10.1103/PhysRevE.52.4745 .
  6. Singh, Vijay P. Entropiateoria ja sen soveltaminen ympäristö- ja vesitekniikassa  : [ eng. ] . – John Wiley & Sons, 10.1.2013. — ISBN 978-1-118-42860-3 .
  7. Parrott, Lael (2010-11-01). "Ekologisen monimutkaisuuden mittaaminen" . Ekologiset indikaattorit _ ]. 10 (6): 1069-1076. DOI : 10.1016/j.ecolind.2010.03.014 . ISSN 1470-160X . 
  8. Holger Lange. Aikasarja-analyysi ekologiassa  (englanniksi)  // eLS. - American Cancer Society, 2006. - ISBN 978-0-470-01590-2 . - doi : 10.1038/npg.els.0003276 .
  9. Wang, Chaojun; Zhao, Hongrui (18.4.2019). "Kaukokartoituksen aikasarjatietojen analyysi ekosysteemin kestävyyden edistämiseksi: ajallisen tiedon entropian käyttö" . International Journal of Remote Sensing . 40 (8): 2880-2894. DOI : 10.1080/01431161.2018.1533661 . ISSN  0143-1161 .
  10. Klemm, Otto; Lange, Holger (1999-12-01). "Ilman saastumisen suuntaukset Fichtelgebirge-vuorilla, Baijerissa" . Ympäristötiede ja saastetutkimus ]. 6 (4): 193-199. DOI : 10.1007/BF02987325 . ISSN 1614-7499 . 
  11. Wang, Kang; Lin, Zhongbing (2018). "Epäpisteperäisen saastumisen karakterisointi jokeen eri tilamittakaavaissa" . Vesi ja ympäristö -lehti ]. 32 (3): 453-465. DOI : 10.1111/wej.12345 . ISSN 1747-6593 . 
  12. Labat, David (2005-11-25). "Viimeaikaiset edistysaskeleet wavelet-analyysissä: Osa 1. Käsitteiden katsaus" . Journal of Hydrology ]. 314 (1): 275-288. DOI : 10.1016/j.jhydrol.2005.04.003 . ISSN 0022-1694 . 
  13. Pachepsky, Jakov; Guber, Andrei; Jacques, Diederik; Simunek, Jiri; Van Genuchten, Marthinus Th.; Nicholson, Thomas; Cady, Ralph (2006-10-01). "Simuloitujen maaperän vesivirtojen tietosisältö ja monimutkaisuus" . Geoderma . Maaperään sovellettu fraktaaligeometria ja siihen liittyvät hierarkkiset järjestelmät - Fraktaalit , monimutkaisuus ja heterogeenisyys ]. 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). "Tietoteoreettinen arvio maaperän kosteuden satelliittihakuista" . Ympäristön kaukokartoitus _ ]. 204 : 392-400. DOI : 10.1016/j.rse.2017.10.016 . HDL : 2060/20180003069 . ISSN  0034-4257 .
  15. Hauhs, Michael; Lange, Holger (2008). "Järjestön valumavesien luokitus: fyysinen ongelma?" . Maantieteellinen kompassi _ ]. 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). "Monimittakaavaiseen entropiaan perustuva alueellisten pohjaveden syvyyssarjojen monimutkaisuustutkimus: Jiangsanjiang Branch Bureaun tapaustutkimus Kiinassa" . ympäristömaatieteet _ _ ]. 70 (1): 353-361. DOI : 10.1007/s12665-012-2132-y . ISSN  1866-6299 .
  17. Xing, Jing; Manning, Carol A. (huhtikuu 2005). "Lennonjohdon monimutkaisuus ja automaationäytöt : kirjallisuuden katsaus ja analyysi " ].
  18. Wang, Kang; Li, Li (marraskuu 2008). "Heterogeenisten virtauskuvioiden karakterisointi tietomittauksilla" . 2008 Ensimmäinen kansainvälinen älykkäitä verkkoja ja älykkäitä järjestelmiä käsittelevä konferenssi : 654-657. DOI : 10.1109/ICINIS.2008.110 .
  19. Javaheri Javid, Mohammad Ali; Alghamdi, Wajdi; Zimmer, Robert & al-Rifaie, Mohammad Majid (2016), Bi, Yaxin; Kapoor, Supriya & Bhatia, Rahul, toim., A Comparative Analysis of Detecting Symmetries in Toroidal Topology , Studies in Computational Intelligence, Springer International Publishing, s. 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-1_36 > . Haettu 7. huhtikuuta 2020. 
  20. Hän, Kaijian; Lu, Xingjing; Zou, Yingchao; Keung Lai, Kin (2015-09-01). "Metallien hintojen ennustaminen curvelet-pohjaisella monimittakaavaisella menetelmällä" . Resurssipolitiikka _ _ ]. 45 : 144-150. DOI : 10.1016/j.resourpol.2015.03.011 . ISSN  0301-4207 .
  21. Hän, Kaijian; Xu, Yang; Zou, Yingchao; Tang, Ling (2015-05-01). "Sähkön hintaennusteet Curveletin kohinanpoistoon perustuvalla lähestymistavalla" . Physica A: Tilastollinen mekaniikka ja sen sovellukset ]. 425 : 1-9. DOI : 10.1016/j.physa.2015.01.012 . ISSN  0378-4371 .
  22. Mosabber Uddin Ahmed. Terveysinformatiikan monimutkaisuusanalyysi  //  Signal Processing Techniques for Computational Health Informatics / 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 .
  23. Shi Xiujian; Sun Zhiqiang; Li Long; Xie Hongwei. "Ihmisen kognitiivisen monimutkaisuuden analyysi kuljetusjärjestelmissä" . Logistiikka . Menettely: 4361-4368. DOI : 10.1061/40996(330)637 .
  24. Zhang, Shutao; Qian, Jinwu; Shen, Linyong; Wu, Xi; Hu, Xiaowu (lokakuu 2015). "Parkinsonin tautia sairastavien potilaiden kävelyn monimutkaisuus ja tiheyssisältöanalyysit" . 2015 International Symposium on Bioelectronics and Bioinformatics (ISBB) : 87–90. DOI : 10.1109/ISBB.2015.7344930 .
  25. Wang, Jisung; Ei, Gyu-Jeong; Choi, Byung-Moon; Ku, Seung-Woo; Joo, Pangyu; Jung, Woo-Sung; Kim, Seunghwan; Lee, Heonsoo (13.7.2017). "Tukahdutti hermoston monimutkaisuutta ketamiinin ja propofolin aiheuttaman tajuttomuuden aikana " Neuroscience Letters [ englanti ] ]. 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. EEG-signaalien monimuotoisuus propofolisedaation aikana: sedatoituneiden mutta reagoivien lisääntyminen, rauhoittavien ja reagoimattomien koehenkilöiden väheneminen   // bioRxiv . – 30.1.2019. - P. 444281 . - doi : 10.1101/444281 .
  27. Fan Yingle; Wu Chuanyan; Li Yi; Pang Quan (15.12.2006). "Tutkimus fluktuaatiokompleksisuuden mittauksen soveltamisesta puheen päätepisteiden havaitsemiseen" . Ilmailulääketiede ja lääketieteellinen tekniikka . 19 (6). ISSN  1002-0837 .
  28. Dilger, Alexander (2012-01-01). "Endogeeninen monimutkaisuus, erikoistuminen ja yleinen koulutus" . Horisontissa . 20 (1):49-53. DOI : 10.1108/10748121211202062 . ISSN  1074-8121 .
  29. Ivanyuk, Vera Alekseevna Strategisen sijoitussalkun hallinnan dynaaminen malli . 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, toim. "Ihmisen esteettisen arvioinnin ja spatiaalisen monimutkaisuuden mittarin välinen korrelaatio" . Evolutionaarinen ja biologisesti inspiroitu musiikki, ääni, taide ja muotoilu . Tietojenkäsittelytieteen luentomuistiinpanot ]. Cham: Springer International Publishing: 79-91. DOI : 10.1007/978-3-319-31008-4_6 . ISBN  978-3-319-31008-4 .