Entropija (teorija informacija)

Dva bita entropije: U slučaju dva bacanja novčića, informaciona entropija u bitima je logaritam osnove-2 broja mogućih ishoda; sa dva novčića postoje četiri moguća ishoda, i dva bita entropije. Generalno, informaciona entropija je prosečna količina informacije prenesena događajem, imajući u vidu sve moguće ishode.

U teoriji informacije, entropija je mera neodređenosti pridružena slučajnoj promenljivoj. U ovom kontekstu, obično se misli na Šenonovu entropiju, koja kvantifikuje očekivanu vrednost informacije sadržane u poruci, obično u jedinicama kao što su biti. Ekvivalentno, Šenonova entropija je mera prosečnog informacionog sadržaja koji se propušta kada se ne zna vrednost slučajne promenljive. Koncept je uveo Klod Šenon u svom čuvenom radu iz 1948. godine „Matematička teorija komunikacija“. Šenonova entropija predstavlja apsolutnu granicu najbolje moguće kompresije bez gubitaka bilo kakve komunikacije, pod izvesnim ograničenjima: ako tretiramo poruke da su kodovane kao niz nezavisnih slučajnih promenljivih sa istom raspodelom, prva Šenonova teorema pokazuje da, u graničnom slučaju, srednja dužina najkraće moguće reprezentacije za kodovanje poruka u datom alfabetu je njihova entropija podeljena sa logaritmom broja simbola u ciljnom alfabetu.

Jedno bacanje fer novčića nosi entropiju od jednog bita. Dva bacanja - dva bita. Brzina entropije za novčić je jedan bit po bacanju. Međutim, ako novčić nije fer, tada je neodređenost manja (ako bismo morali da se kladimo na ishod narednog pokušaja, verovatno ćemo se kladiti na češći rezultat), pa je i Šenonova entropija manja. Matematički, jedno bacanje novčića (fer ili ne) predstavlja Bernulijev eksperiment, a njegova entropija data je binarnom entropijskom funkcijom. Niz bacanja novčića sa dve glave imaće nultu entropiju, jer su ishodi potpuno predvidljivi. Brzina entropije teksta na engleskom je od 1 do 1,5 bita po slovu, odnosno od 0,6 do 1,3 bita po slovu, prema procenama baziranim na eksperimentima.

Mera informacione entropije asocirane sa svakom mogućom vrednošću podataka je negativni logaritam funkcije verovatnoće mase vrednosti:

$S=-\sum _{i}P_{i}\log {P_{i}}$.

Kada izvor podataka ima vrednost niže verovatnoće (tj., kad se javi događaj manje verovatnoće), događaj nosi više „informacija”, nego kad izvor podataka ima vrednost veće verovatnoće. Količina informacije presene svakim događajem na ovaj način postaje slučajna promenljiva čija očekivana vrednost je informaciona entropija. Generalno, entropija se odnosi na nered ili nesigurnost, i definicija entropije koja se koristi u informacionoj teoriji je direktno analogna definiciji korištenoj u statističkoj termodinamici.

Osnovni model sistema prenosa podataka se sastoji od tri elementa, izvora podataka, komunikacijskog kanala, i primaoca, i prema Šanonu „fundamentalni problem komunikacije” je za primaoca da može da identifikuje koji podaci su generisani u izvoru na bazi signala koji su primljeni kroz kanal. Entropija pruža apsolutni limit najkraće moguće prosečne dužine bezgubitačne kompresije kodiranja podataka proizvedenih u izvoru, i ako je entropija izvora manja od kanalnog kapaciteta komunikacionog kanala, podaci generisani u izvoru se mogu pozdano preneti do primaoca (bar u teoriji, eventualno zanemarujući neke praktične aspekte, kao što je složenost sistema potrebnog za prenos podataka i vremena koje može biti neophodno).

Informaciona entropija se tipično meri u bitovima (alternativno zvanim „šenoni”) ili ponekad u „prirodnim jedinicama” (natovi) ili decimalnim brojevima (zvanim „ditovi”, „banovi”, ili „hartliji”). Jedinica mera zavisi od baze logaritma koji se koristi za definisanje entropije.

Logaritam verovatnoće je koristan kao mera entropije jer je aditivan za nezavisne izvore. Na primer, entropija bacanja novčića je jedan bit, i entropija m bacanja je m bitova. U jednostavnom prikazu, log₂(n) bitova je potrebno za prikazivanje promenljive koja može da poprimi n vrednosti, ako je n stepen od 2. Ako su te vrednosti jednako verovatne, entropija (u bitovima) je jednaka tom broju. Ako je jedna od vrednosti verovatnija od drugih, zapažanje da se ta vrednost javila je manje informativna nego da se neki manje zastupljeni ishod odvio. Konsekventno, ređi događaji pružaju više informacija kad su uočeni. Pošto se uočavanja manje verovatnih događaja dešavaju ređe, neto efekat je da je entropija (koja se smatra prosečnom informacijom) dobijena iz neuniformne distribucije podataka uvek manja ili jednaka od log₂(n). Entropija je nula kad je izvesno da će se jedan ishod dogoditi. Entropija kvantifikuje ova razmatranja kada je poznata distribucija verovatnoće izvornih podataka. Smisao uočenog događaja (smisao poruke) nije važan u definiciji entropije. Entropija jedino uzima u obzir verovatnoću uočavanja specifičnog događaja, tako da informacija koju ona sadrži predstavlja informaciju o ishodišnoj distribuciji verovatnoće, a ne o značenju samih događaja.

Definicija

Šenon je definisao entropiju $H$ diskretnog izvora bez memorije (diskretne slučajne promenljive) $X$ nad konačnim alfabetom $Z=\{z_{1},z_{2},\dots ,z_{m}\}$ na sledeći način. Prvo se dodeli svakoj verovatnoći $p$ nekog događaja njena količina informacije $I(p)=-\log _{2}p$. Tada je entropija po simbolu definisana kao očekivana vrednost (matematičko očekivanje) količine informacija

$H_{1}=\sum _{z\in Z}p_{z}\cdot I(p_{z})=-\sum _{z\in Z}p_{z}\cdot \log _{2}p_{z}$,

Neka je $z\in Z$, tada je $p_{z}=P(X=z)$ verovatnoća da se dogodi simbol $z$ iz alfabeta, ili ekvivalentno

$(1)\qquad H_{1}=-\sum _{i=1}^{m}p_{i}\cdot \log _{2}p_{i}$,

Za graničnu vrednost $\lim _{p_{i}\rightarrow 0}p_{i}\cdot \log _{2}p_{i}$ se može pokazati da je nula. Prema tome, sabirci sa verovatnoćom jednakom nuli ne doprinose ukupnom zbiru (tj. entropiji).

Entropija $H_{n}$ za reči $w$ dužine $n$ je data sa

$H_{n}=-\sum _{w\in Z^{n}}p_{w}\cdot \log _{2}p_{w}$,

gde je $p_{w}=P(X=w)$ verovatnoća da će se dogoditi reč $w$. Entropija $H$ je tada granična vrednost:

$(2)\qquad H=\lim _{n\to \infty }{\frac {H_{n}}{n}}$.

Ako su simboli statistički nezavisni, tada $H_{n}=nH_{1}$ za svako $n$, kao i $H=H_{1}$.

Elermanova definicija

Dejvid Elerman je želeo da objasni zašto uslovna entropija i druge funkcije imaju svojstva slična funkcijama u teoriji verovatnoće. On tvrdi da su prethodne definicije zasnovane na teoriji mera funkcionisale samo sa stepenom 2.

Interpretacija

Entropija predstavlja meru prosečnog informacionog sadržaja po simbolu izvora koji predstavlja neki sistem ili informacionu sekvencu. U teoriji informacija, kao mera za količinu informacije u nekoj poruci može poslužiti koliko se promenila verovatnoća događaja pod uticajem te poruke. Na primer, ako za vreme leta vremenska prognoza za sutrašnji dan najavi 30° C, to nam neće doneti mnogo informacija, jer ne sadrži ništa neočekivano. Međutim, ako se ista takva prognoza dogodi zimi, to predstavlja potpuno neočekivanu vest i samim tim sadrži mnogo informacija. Pod informacijom se može smatrati i mera uklonjene nesigurnosti. Što se više simbola primi od izvora, dobijamo više informacija i opada nesigurnost oko onoga šta je moglo biti poslato.

Definicija informacionog sadržaja se može na sledeći način opisati: ako se desi događaj čija je verovatnoća $p_{i}$, tada je kroz to izabran jedan konkretan događaj iz hipotetičkog skupa od ${\tfrac {1}{p_{i}}}$ jednako verovatnih događaja. Da bi se ovi događaji međusobno razlikovali, potrebno im je dodeliti $\log _{2}\left({\tfrac {1}{p_{i}}}\right)=-\log _{2}(p_{i})$ bita. Ova vrednost predstavlja količinu informacije jednog određenog događaja u bitima. Kada se količina informacije svakog događaja ponderiše sa verovatnoćom istog događaja, i kada se saberu (tj. pronađe se matematičko očekivanje količine informacije), dobijamo srednju ili očekivanu količinu informacije po simbolu.

Jedinica Šenon definiše količinu informacije koju sadrži poruka o događaju sa verovatnoćom $p=0,5$. Na primer, saopštenje o tome da je metalni novčić pao na određenu stranu donosi informaciju od 1 Šenona. Ili, ako na prijemnoj strani binarnog telekomunikacionog sistema, čiji je signal sastavljen od bipolarnih impulsa konstantne amplitude, merimo polarnost dolazećih impulsa, i ako je verovatnoća pojavljivanja pozitivnih i negativnih amplituda jednaka, onda svaki impuls nosi informaciju od 1 Šenona. Međutim, ako verovatnoće pojavljivanja pozitivnih i negativnih amplituda nisu jednake, onda jedan impuls donosi prijemniku neku drugu količinu informacija koja nije 1 Šenon. Treba razlikovati pojam binarni digit, skraćeno bit, od pojma Šenon. Bit je samo nosilac informacije i fizički je predstavljen impulsom koji može da ima dva stanja. U zavisnosti od verovatnoće pojavljivanja stanja, bit može da donosi prijemniku veću ili manju količinu informacija. Samo kad su verovatnoće pojavljivanja dva stanja kod bita jednake, onda bit nosi količinu informacije od 1 Šenona.

Vidi još

• Entropija

Literatura

• Han, Te Sun; Kobayashi, Kingo (2002). Mathematics of Information and Coding. American Mathematical Society. ISBN 978-0-8218-4256-0. 
• Arndt, C (2004). Information Measures: Information and its Description in Science and Engineering. Springer. ISBN 978-3-540-40855-0. 
• Borda, Monica (2011). Fundamentals in Information Theory and Coding. Springer. ISBN 978-3-642-20346-6. 
• Pathria, R. K.; Beale, Paul (2011). Statistical Mechanics (Third Edition). Academic Press. str. 51. ISBN 978-0123821881. 
• Cover, T. M., Thomas, J. A. Elements of information theory, Wiley-Interscience. (2nd изд.). 2006. ISBN 978-0-471-24195-9. .
• Gray, R. M. (2011), Entropy and Information Theory, Springer.
• MacKay, David J. C.. Information Theory, Inference, and Learning Algorithms Cambridge. . Cambridge University Press. 2003. ISBN 978-0-521-64298-9. 
• Pathria, R. K.; Beale, Paul (2011). Statistical Mechanics (Third Edition). Academic Press. ISBN 978-0123821881. 
• Martin, Nathaniel F.G.; England, James W. (2011). Mathematical Theory of Entropy. Cambridge University Press. ISBN 978-0-521-17738-2. 
• Shannon, C.E., Weaver, W. (1949). The Mathematical Theory of Communication. University of Illinois Press. ISBN 978-0-252-72548-7. CS1 održavanje: Višestruka imena: spisak autora (veza)
• Stone, J. V. Chapter 1 of Information Theory: A Tutorial Introduction, University of Sheffield, England. 2014. ISBN 978-0956372857..

Spoljašnje veze

• Hazewinkel Michiel, ur. (2001). „Entropy”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
• Introduction to entropy and information on Principia Cybernetica Web
• Entropy an interdisciplinary journal on all aspects of the entropy concept. Open access.
• Description of information entropy from "Tools for Thought" by Howard Rheingold
• A java applet representing Shannon's Experiment to Calculate the Entropy of English
• Slides on information gain and entropy
• An Intuitive Guide to the Concept of Entropy Arising in Various Sectors of Science – a wikibook on the interpretation of the concept of entropy.
• Network Event Detection With Entropy Measures, Dr. Raimund Eimann, University of Auckland, PDF; 5993 kB – a PhD thesis demonstrating how entropy measures may be used in network anomaly detection.
• Rosetta Code repository of implementations of Shannon entropy in different programming languages.
• "Information Theory for Intelligent People" Архивирано на сајту Wayback Machine (13. јун 2020). Short introduction to the axioms of information theory, entropy, mutual information, Kullback–Liebler divergence, and Jensen–Shannon distance.
• Online tool for calculating entropy (plain text)
• Online tool for calculating entropy (binary)