Complexitatea (teoria informației)

Complexitatea informației-fluctuație este o valoare teoretică a informațiilor definită ca fluctuația informației în raport cu entropia informației . Este derivat din fluctuațiile prevalenței ordinii și haosului într-un sistem dinamic și este utilizat în diferite domenii de cunoaștere pentru a măsura complexitatea . Teoria a fost prezentată în lucrarea lui Bates și Shepard în 1993 [1] .

Definiție

Complexitatea informației-fluctuație a unui sistem dinamic discret este o funcție a distribuției de probabilitate a stărilor acestui sistem supus intrărilor aleatorii de date. Scopul controlului unui sistem cu o sursă bogată de informații, cum ar fi un generator de numere aleatoare sau un semnal de zgomot alb , este de a explora dinamica internă a sistemului în același mod în care este utilizat un impuls bogat în frecvență în procesarea semnalului .

Dacă sistemul are stări posibile și probabilitățile stărilor sunt cunoscute, atunci entropia sa informațională este egală cu ${\textstyle N}$ ${\textstyle p_{i))$

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

unde se află informaţia de stat propriu . ${\textstyle I_{i}=-\log p_{i}}$ ${\textstyle i}$

Complexitatea informației-fluctuație a unui sistem este definită ca abaterea standard sau fluctuația de la valoarea sa medie : ${\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))))

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

Fluctuația informațiilor de stare este zero într-un sistem maxim dezordonat cu toate ; sistemul simulează pur și simplu intrări aleatorii de date. este de asemenea zero atunci când sistemul este perfect ordonat și are o singură stare fixă , indiferent de intrări. este diferit de zero între aceste două extreme atunci când atât stările cu probabilitate mare, cât și stările cu probabilitate scăzută sunt posibile umplerea spațiului de stări. $\sigma _{I}$ $p_{i}=1/N$ $\sigma _{I}$ $(p_{1}=1)$ $\sigma _{I}$

Fluctuațiile în informații oferă memorie și calcul

Pe măsură ce un sistem dinamic complex se dezvoltă în timp, acesta trece de la o stare la alta. Modul în care apar aceste tranziții depinde de stimulii externi într-o manieră neregulată. În unele cazuri, sistemul poate fi mai sensibil la stimuli externi (instabil), în timp ce în altele poate fi mai puțin sensibil (stabil). Dacă o anumită stare are mai multe stări posibile următoare, informațiile externe determină care va fi următoarea, iar sistemul obține această informație urmând o anumită traiectorie în spațiul stărilor. Dar dacă mai multe stări diferite duc la aceeași stare următoare, atunci când intră în ea, sistemul pierde informații despre starea care a precedat-o. Astfel, pe măsură ce evoluează în timp, un sistem complex prezintă câștiguri și pierderi alternative de informații. Alternanțele sau fluctuațiile informațiilor echivalează cu amintirea și uitarea - stocarea temporară a informațiilor sau a memoriei - aceasta este o caracteristică esențială a calculelor non-triviale.

Câștigul sau pierderea de informații care însoțește tranzițiile de stat pot fi asociate cu propriile informații de stare. Câștigul net de informații în timpul trecerii de la stare la stare este informația obținută la ieșirea din stare minus pierderea de informații la intrarea în stare : $i$ $j$ $i$ $j$

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

Iată probabilitatea condițională directă ca dacă starea curentă este , atunci starea următoare va fi și este probabilitatea condiționată inversă ca dacă starea curentă este , atunci starea anterioară a fost . Probabilitățile condiționate sunt legate de probabilitatea de tranziție , probabilitatea ca o tranziție de la stare la stare să se producă , prin: ${\textstyle p_{i\rightarrow j}}$ $i$ $j$ $p_{i\leftarrow j)$ $j$ $i$ $p_{{ij}}$ $i$ $j$

p_{ij}=p_{i}p_{i\rightarrow j}=p_{j}p_{i\leftarrow j}.

Eliminând probabilitățile condiționate, obținem:

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

Prin urmare, informația netă obținută de sistem ca urmare a tranziției depinde doar de creșterea informațiilor de stare de la starea inițială la starea finală. Se poate demonstra că acest lucru este adevărat chiar și pentru mai multe tranziții consecutive [1] .

Formula seamănă cu relația dintre forță și energia potențială . este similară cu energia potențială și este forța din formulă . Informația externă „împinge” sistemul „în sus”, la o stare cu un potențial de informare mai mare pentru conservarea memoriei, la fel cum împingerea unui corp cu o anumită masă în sus, la o stare cu un potențial gravitațional mai mare, duce la acumularea de energie. Cantitatea de energie stocată depinde doar de înălțimea finală și nu de drumul în sus. De asemenea, cantitatea de informații stocate este independentă de calea de tranziție între două stări. Odată ce un sistem atinge o stare rară de potențial informațional ridicat, poate „cădea” înapoi la o stare normală, pierzând informațiile stocate anterior. $\Gamma =\Delta I$ $eu$ $E_{p}$ $\Gamma$ $\mathbf {F}$ $\mathbf {F} = {\nabla E_ {p)}$

Poate fi util să se calculeze abaterea standard de la media ei (care este zero), și anume fluctuația câștigului net de informații [1] , dar ia în considerare ciclurile memoriei cu mai multe tranziții în spațiul de stare și, prin urmare, ar trebui să fie mai precisă. indicator al puterii de procesare a sistemului. În plus, este mai ușor de calculat, deoarece pot exista mult mai multe tranziții decât stări. $\Gamma$ $\sigma _{\Gamma }$ $\sigma _{I}$ $\sigma _{I}$

Haos și ordine

Un sistem dinamic care este sensibil la informațiile externe (instabil) prezintă un comportament haotic , în timp ce un sistem care este insensibil la informațiile externe (stabil) prezintă un comportament ordonat. Sub influența unei surse bogate de informații, un sistem complex prezintă ambele comportamente, oscilând între ele într-un echilibru dinamic. Gradul de fluctuație se măsoară cantitativ cu ; surprinde alternanța predominanței haosului și ordinii într-un sistem complex pe măsură ce se dezvoltă în timp. $\sigma _{I}$

Exemplu: o variantă a automatului celular elementar conform regulii 110

Este dovedit că o variantă a automatului celular elementar conform regulii 110 este capabilă de calcule universale . Dovada se bazează pe existența și interacțiunea unor configurații celulare conectate și auto-conservabile cunoscute sub denumirea de „planare” sau „ nave spațiale ”, fenomenul apariției , care implică capacitatea grupurilor de celule automate de a-și aminti că un planor trece prin ele. Prin urmare, este de așteptat ca buclele de memorie să apară în spațiul de stare, ca urmare a alternanței câștigului și pierderii de informații, instabilității și stabilității, haosului și ordinii.

Luați în considerare un grup de trei celule adiacente ale unui automat celular care respectă regula 110:capăt-centru-capăt. Următoarea stare a celulei centrale depinde de starea sa curentă și de celulele frunzelor, așa cum se specifică în regulă:

Regula 110 a automatului celular elementar.

grup de 3 celule	1-1-1	1-1-0	1-0-1	1-0-0	0-1-1	0-1-0	0-0-1	0-0-0
următoarea celulă centrală	0	unu	unu	0	unu	unu	unu	0

Pentru a calcula complexitatea fluctuației informațiilor din acest sistem, se va atașa o celulă driver la fiecare capăt al unui grup de 3 celule pentru a furniza un stimul extern aleatoriu, de ex.driver→end-center-end←driver, astfel încât regula să poată fi aplicată celor două celule de capăt. Apoi trebuie să determine care este următoarea stare pentru fiecare stare curentă posibilă și pentru fiecare combinație posibilă de conținut de celule driver pentru a calcula probabilitățile condiționate directe.

Diagrama de stare a acestui sistem este prezentată mai jos. În ea, cercurile reprezintă stări, iar săgețile reprezintă tranziții între stări. Cele opt stări ale acestui sistem, de la1-1-1inainte de0-0-0sunt numerotate cu echivalente zecimale ale conținutului de 3 biți al unui grup de 3 celule: de la 7 la 0. Lângă săgețile de tranziție, sunt afișate valorile probabilităților condiționale directe. Schema arată variabilitatea divergenței și convergenței săgeților, care corespunde variabilității haosului și ordinii, sensibilității și insensibilității, achiziției și pierderii de informații externe din celulele driver.

Probabilitățile condiționale directe sunt determinate de proporția conținutului posibil al celulei driver care guvernează o anumită tranziție. De exemplu, pentru patru combinații posibile ale conținutului a două celule driver, starea 7 duce la stările 5, 4, 1 și 0, deci , , și sunt 1/4 sau 25%. De asemenea, starea 0 duce la stările 0, 1, 0 și 1, deci 1/2, sau 50% , corespunde. Si asa mai departe. $p_{7\rightarrow 5}$ $p_{7\rightarrow 4}$ $p_{7\rightarrow 1}$ $p_{7\rightarrow 0}$ $p_{0\rightarrow 1}$ $p_{0\rightarrow 0}$

Probabilitățile de stare sunt legate prin formula

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

și

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

Aceste ecuații algebrice liniare pot fi rezolvate manual sau cu un program de calculator pentru probabilități de stare, cu următoarele rezultate:

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

Entropia și complexitatea informațiilor pot fi calculate din probabilitățile de stare:

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

băţ,

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

pic.

Trebuie remarcat faptul că entropia maximă posibilă pentru opt stări este egală cu un bit, ceea ce corespunde cazului în care toate cele opt stări sunt la fel de probabile, cu probabilități 1/8 (haotice). Prin urmare, regula 110 are o entropie relativ mare sau o utilizare a stării de 2,86 biți. Totuși, acest lucru nu exclude o fluctuație semnificativă a informațiilor de stare în raport cu entropia și, în consecință, o cantitate mare de complexitate. În timp ce entropia maximă ar exclude complexitatea. $\log _{2}8=3$

O metodă alternativă poate fi utilizată pentru a obține probabilități de stare atunci când metoda analitică descrisă mai sus nu este fezabilă. Constă în conducerea sistemului prin intrările sale (celule driver) cu o sursă aleatorie timp de mai multe generații și observarea empiric a probabilităților de stare. Când se termină cu simulări pe computer pentru 10 milioane de generații, rezultatele sunt următoarele: [2]

Variabile de informare pentru un automat celular elementar conform regulii 110

numărul de celule	3	patru	5	6	7	opt	9	zece	unsprezece	12	13
$\mathrm{H}$ (pic)	2,86	3,81	4,73	5,66	6,56	7.47	8.34	9.25	10.09	10.97	11.78
$\sigma _{I}$ (pic)	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

Întrucât ambii parametri, și , cresc odată cu dimensiunea sistemului, pentru o mai bună comparare a sistemelor de dimensiuni diferite, se propune o relație adimensională , complexitate relativă Informație-fluctuație. Rețineți că rezultatele empirice și analitice sunt consistente pentru un automat cu 3 celule. $\mathrm{H}$ $\sigma _{I}$ $\sigma _{I}/\mathrm {H}$

În lucrarea lui Bates și Shepard [1] , se calculează pentru toate regulile automatelor celulare elementare și s-a observat că cele care prezintă „planoare” cu mișcare lentă și eventual obiecte staționare, de exemplu, regula 110, sunt strâns asociate. cu valori mari de . Prin urmare, poate fi folosit ca filtru atunci când alegeți reguli capabile de calcul universal, ceea ce este obositor de demonstrat. $\sigma _{I}$ $\sigma _{I}$ $\sigma _{I}$

Aplicații

Deși derivarea formulei de complexitate a fluctuației informației se bazează pe fluctuațiile informațiilor într-un sistem dinamic, formula în sine depinde doar de probabilitățile de stare și, prin urmare, poate fi aplicată și oricărei distribuții de probabilitate, inclusiv celor derivate din imagini sau text statice.

De-a lungul anilor, lucrarea originală [1] a fost menționată de cercetători din multe domenii diferite: teoria complexității [3] , știința sistemelor complexe [4] , dinamica haotică [5] , ingineria mediului [6] , complexitatea ecologică [7] , analiza serii temporale ecologice [8] , reziliența ecosistemului [9] , poluarea aerului [10] și a apei [11] , analiza waveletelor hidrologice [12] , modelarea debitelor de apă în sol [13] , umiditatea solului [14] , bazin hidrografic scurgere [15] , adâncimea apei subterane [16] , controlul traficului aerian [17] , modelul de curgere [18] , topologia [19] , prognoza pieței de prețuri pentru metale [20] și electricitate [21] , informatica sanitară [22] , cogniția umană [23] , cinematica mersului uman [24] neurologie [25] Analiza EEG [26] analiza vorbirii [27] educație [28] investiție [29] estetică [30] .

Link -uri

↑ 1 2 3 4 5 John E. Bates, Harvey K. Shepard. Măsurarea complexității folosind fluctuația informației (engleză) // Physics Letters A. — 1993-01-18. — Vol. 172 , iss. 6 . — P. 416–425 . — ISSN 0375-9601 . - doi : 10.1016/0375-9601(93)90232-O .
↑ Bates, John E. Măsurarea complexității folosind fluctuația informațiilor: un tutorial . Poarta cercetării (30 martie 2020). (nedefinit)
↑ Harald Atmanspacher. Tăiere carteziană, tăietură Heisenberg și conceptul de complexitate // World Futures. - 1997-09-01. - T. 49 , nr. 3-4 . — S. 333–355 . — ISSN 0260-4027 . - doi : 10.1080/02604027.1997.9972639 .
↑ Cosma Rohilla Shalizi. Metode și tehnici ale științei sistemelor complexe: o privire de ansamblu // Știința sistemelor complexe în biomedicină / 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 .
↑ Renate Wackerbauer. Stabilizarea sistemului Lorenz indusă de zgomot // Physical Review E. - 1995-11-01. - T. 52 , nr. 5 . — S. 4745–4749 . - doi : 10.1103/PhysRevE.52.4745 .
↑ Singh, Vijay P. Teoria entropiei și aplicația sa în ingineria mediului și a apei : [ ing. ] . — John Wiley & Sons, 2013-01-10. — ISBN 978-1-118-42860-3 .
^ Parrott, Lael (01.11.2010) . „Măsurarea complexității ecologice” . Indicatori ecologici _ ]. 10 (6): 1069-1076. DOI : 10.1016/j.ecolind.2010.03.014 . ISSN 1470-160X .
↑ Holger Lange. Analiza serii temporale în ecologie (engleză) // eLS. - Societatea Americană de Cancer, 2006. - ISBN 978-0-470-01590-2 . - doi : 10.1038/npg.els.0003276 .
↑ Wang, Chaojun; Zhao, Hongrui (18.04.2019). „Analiza datelor din seria temporală de teledetecție pentru a promova sustenabilitatea ecosistemului: utilizarea entropiei informaționale temporale” . Jurnalul Internațional de Teledetecție . 40 (8): 2880-2894. DOI : 10.1080/01431161.2018.1533661 . ISSN 0143-1161 .
↑ Klemm, Otto; Lange, Holger (1999-12-01). „Tendințe ale poluării aerului în Munții Fichtelgebirge, Bavaria” . Știința mediului și cercetarea poluării ]. 6 (4): 193-199. DOI : 10.1007/BF02987325 . ISSN 1614-7499 .
↑ Wang, Kang; Lin, Zhongbing (2018). „Caracterizarea sursei nepunctuale de poluare în râu la diferite scări spațiale” . Jurnalul de apă și mediu ]. 32 (3): 453-465. DOI : 10.1111/wej.12345 . ISSN 1747-6593 .
↑ Labat, David (25.11.2005). „Progrese recente în analizele wavelet: Partea 1. O revizuire a conceptelor” . Jurnalul de Hidrologie ]. 314 (1): 275-288. DOI : 10.1016/j.jhydrol.2005.04.003 . ISSN 0022-1694 .
↑ Pachepski, Iakov; Guber, Andrey; Jacques, Diederik; Simunek, Jiri; Van Genuchten, Marthinus Th.; Nicholson, Thomas; Cady, Ralph (01-10-2006). „Conținutul de informații și complexitatea fluxurilor simulate de apă din sol” . Geoderma . Geometrie fractală aplicată solului și sistemelor ierarhice înrudite - fractali , complexitate și eterogenitate ]. 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 (01.01.2018). „Evaluarea teoretică informațională a extragerii de umiditate a solului prin satelit” . Teledetecția mediului _ ]. 204 : 392-400. DOI : 10.1016/j.rse.2017.10.016 . HDL : 2060/20180003069 . ISSN 0034-4257 .
↑ Hauhs, Michael; Lange, Holger (2008). „Clasificarea scurgerii în captarea apelor de apă: o problemă fizică?” . busolă geografică _ ]. 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). „Cercetarea complexității seriilor regionale de adâncime a apei subterane bazate pe entropia multiscale: un studiu de caz al Biroului filialei Jiangsanjiang din China” . științe ale pământului mediului ]. 70 (1): 353-361. DOI : 10.1007/s12665-012-2132-y . ISSN 1866-6299 .
↑ Xing, Jing; Manning, Carol A. (aprilie 2005). „Afișări de complexitate și automatizare ale controlului traficului aerian : revizuire și analiză a literaturii ” ].
↑ Wang, Kang; Li, Li (noiembrie 2008). „Caracterizarea tiparelor de flux eterogene folosind măsurători de informații” . 2008 Prima conferință internațională privind rețelele inteligente și sistemele inteligente : 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., 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-33386-1_ . Preluat la 7 aprilie 2020.
↑ El, Kaijian; Lu, Xingjing; Zou, Yingchao; Keung Lai, Kin (01.09.2015). „Prognoza prețurilor metalelor cu o metodologie multiscale bazată pe curvele” . Politica de resurse _ ]. 45 : 144-150. DOI : 10.1016/j.resourpol.2015.03.011 . ISSN 0301-4207 .
↑ El, Kaijian; Xu, Yang; Zou, Yingchao; Tang, Ling (01.05.2015). „Prognozele prețului energiei electrice folosind o abordare bazată pe curbelet denoising” . Fizica A: Mecanica statistică și aplicațiile sale ]. 425 : 1-9. DOI : 10.1016/j.physa.2015.01.012 . ISSN 0378-4371 .
↑ Mosabber Uddin Ahmed. Analiza complexității în informatica sănătății // Tehnici de procesare a semnalului pentru informatica de sănătate computațională / 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 .
↑ Shi Xiujian; Sun Zhiqiang; Li Long; Xie Hongwei. „Analiza complexității cognitive umane în sistemele de transport” . Logistica . Procese: 4361-4368. DOI : 10.1061/40996(330)637 .
↑ Zhang, Shutao; Qian, Jinwu; Shen, Linyong; Wu, Xi; Hu, Xiaowu (octombrie 2015). „Complexitatea mersului și analiza conținutului de frecvență a pacienților cu boala Parkinson” . 2015 Simpozion internațional de bioelectronică și bioinformatică (ISBB) : 87–90. DOI : 10.1109/ISBB.2015.7344930 .
↑ Wang, Jisung; Noh, Gyu-Jeong; Choi, Byung-Moon; Ku, Seung-Woo; Joo, Pangyu; Jung, Woo-Sung; Kim, Seunghwan; Lee, Heonsoo (13.07.2017). „Suprimarea complexității neuronale în timpul inconștienței induse de ketamina și propofol” . Scrisori de neuroștiință [ engleză ] ]. 653 : 320-325. DOI : 10.1016/j.neulet.2017.05.045 . ISSN 0304-3940 .
↑ Michał Bola, Paweł Orłowski, Martyna Płomecka, Artur Marchewka. Diversitatea semnalului EEG în timpul sedării cu propofol: o creștere a numărului de subiecți sedați, dar sensibili, o scădere a subiecților sedați și care nu răspund // bioRxiv . — 30.01.2019. - P. 444281 . - doi : 10.1101/444281 .
↑ Fan Yingle; Wu Chuanyan; Li Yi; Pang Quan (2006-12-15). „Studiu privind aplicarea măsurării complexității fluctuațiilor în detectarea punctului final al vorbirii” . Medicina aerospațială și inginerie medicală . 19 (6). ISSN 1002-0837 .
↑ Dilger, Alexander (01.01.2012). „Complexitate endogenă, specializare și educație generală” . La Orizont . 20 (1):49-53. DOI : 10.1108/10748121211202062 . ISSN 1074-8121 .
↑ Ivanyuk, Vera Alekseevna Model dinamic de management strategic al portofoliului de investiții . biblioteca.ru (2015). (nedefinit)
↑ Javid, Mohammad Ali Javaheri; Blackwell, Tim; Zimmer, Robert; al-Rifaie, Mohammad Majid (2016). Johnson, Collin; Ciesielski, Vic; Correia, João; Machado, Penousal, eds. „Corelația dintre judecata estetică umană și măsurarea complexității spațiale” . Muzică, sunet, artă și design evolutiv și de inspirație biologică . Note de curs în informatică ]. Cham: Springer International Publishing: 79-91. DOI : 10.1007/978-3-319-31008-4_6 . ISBN 978-3-319-31008-4 .