Ентропија (теорија информација)

Два бита ентропије: У случају два бацања новчића, информациона ентропија у битима је логаритам основе-2 броја могућих исхода; са два новчића постоје четири могућа исхода, и два бита ентропије. Генерално, информациона ентропија је просечна количина информације пренесена догађајем, имајући у виду све могуће исходе.

У теорији информације, ентропија је мера неодређености придружена случајној променљивој. У овом контексту, обично се мисли на Шенонову ентропију, која квантификује очекивану вредност информације садржане у поруци, обично у јединицама као што су бити. Еквивалентно, Шенонова ентропија је мера просечног информационог садржаја који се пропушта када се не зна вредност случајне променљиве. Концепт је увео Клод Шенон у свом чувеном раду из 1948. године „Математичка теорија комуникација“. Шенонова ентропија представља апсолутну границу најбоље могуће компресије без губитака било какве комуникације, под извесним ограничењима: ако третирамо поруке да су кодоване као низ независних случајних променљивих са истом расподелом, прва Шенонова теорема показује да, у граничном случају, средња дужина најкраће могуће репрезентације за кодовање порука у датом алфабету је њихова ентропија подељена са логаритмом броја симбола у циљном алфабету.

Једно бацање фер новчића носи ентропију од једног бита. Два бацања - два бита. Брзина ентропије за новчић је један бит по бацању. Међутим, ако новчић није фер, тада је неодређеност мања (ако бисмо морали да се кладимо на исход наредног покушаја, вероватно ћемо се кладити на чешћи резултат), па је и Шенонова ентропија мања. Математички, једно бацање новчића (фер или не) представља Бернулијев експеримент, а његова ентропија дата је бинарном ентропијском функцијом. Низ бацања новчића са две главе имаће нулту ентропију, јер су исходи потпуно предвидљиви. Брзина ентропије текста на енглеском је од 1 до 1,5 бита по слову, односно од 0,6 до 1,3 бита по слову, према проценама базираним на експериментима.

Мера информационе ентропије асоциране са сваком могућом вредношћу података је негативни логаритам функције вероватноће масе вредности:

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

Када извор података има вредност ниже вероватноће (тј., кад се јави догађај мање вероватноће), догађај носи више „информација”, него кад извор података има вредност веће вероватноће. Количина информације пресене сваким догађајем на овај начин постаје случајна променљива чија очекивана вредност је информациона ентропија. Генерално, ентропија се односи на неред или несигурност, и дефиниција ентропије која се користи у информационој теорији је директно аналогна дефиницији кориштеној у статистичкој термодинамици.

Основни модел система преноса података се састоји од три елемента, извора података, комуникацијског канала, и примаоца, и према Шанону „фундаментални проблем комуникације” је за примаоца да може да идентификује који подаци су генерисани у извору на бази сигнала који су примљени кроз канал. Ентропија пружа апсолутни лимит најкраће могуће просечне дужине безгубитачне компресије кодирања података произведених у извору, и ако је ентропија извора мања од каналног капацитета комуникационог канала, подаци генерисани у извору се могу поздано пренети до примаоца (бар у теорији, евентуално занемарујући неке практичне аспекте, као што је сложеност система потребног за пренос података и времена које може бити неопходно).

Информациона ентропија се типично мери у битовима (алтернативно званим „шенони”) или понекад у „природним јединицама” (натови) или децималним бројевима (званим „дитови”, „банови”, или „хартлији”). Јединица мера зависи од базе логаритма који се користи за дефинисање ентропије.

Логаритам вероватноће је користан као мера ентропије јер је адитиван за независне изворе. На пример, ентропија бацања новчића је један бит, и ентропија m бацања је m битова. У једноставном приказу, log₂(n) битова је потребно за приказивање променљиве која може да поприми n вредности, ако је n степен од 2. Ако су те вредности једнако вероватне, ентропија (у битовима) је једнака том броју. Ако је једна од вредности вероватнија од других, запажање да се та вредност јавила је мање информативна него да се неки мање заступљени исход одвио. Консеквентно, ређи догађаји пружају више информација кад су уочени. Пошто се уочавања мање вероватних догађаја дешавају ређе, нето ефекат је да је ентропија (која се сматра просечном информацијом) добијена из неуниформне дистрибуције података увек мања или једнака од log₂(n). Ентропија је нула кад је извесно да ће се један исход догодити. Ентропија квантификује ова разматрања када је позната дистрибуција вероватноће изворних података. Смисао уоченог догађаја (смисао поруке) није важан у дефиницији ентропије. Ентропија једино узима у обзир вероватноћу уочавања специфичног догађаја, тако да информација коју она садржи представља информацију о исходишној дистрибуцији вероватноће, а не о значењу самих догађаја.

Дефиниција

Шенон је дефинисао ентропију $H$ дискретног извора без меморије (дискретне случајне променљиве) $X$ над коначним алфабетом $Z=\{z_{1},z_{2},\dots ,z_{m}\}$ на следећи начин. Прво се додели свакој вероватноћи $p$ неког догађаја њена количина информације $I(p)=-\log _{2}p$. Тада је ентропија по симболу дефинисана као очекивана вредност (математичко очекивање) количине информација

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

Нека је $z\in Z$, тада је $p_{z}=P(X=z)$ вероватноћа да се догоди симбол $z$ из алфабета, или еквивалентно

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

За граничну вредност $\lim _{p_{i}\rightarrow 0}p_{i}\cdot \log _{2}p_{i}$ се може показати да је нула. Према томе, сабирци са вероватноћом једнаком нули не доприносе укупном збиру (тј. ентропији).

Ентропија $H_{n}$ за речи $w$ дужине $n$ је дата са

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

где је $p_{w}=P(X=w)$ вероватноћа да ће се догодити реч $w$. Ентропија $H$ је тада гранична вредност:

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

Ако су симболи статистички независни, тада $H_{n}=nH_{1}$ за свако $n$, као и $H=H_{1}$.

Елерманова дефиниција

Дејвид Елерман је желео да објасни зашто условна ентропија и друге функције имају својства слична функцијама у теорији вероватноће. Он тврди да су претходне дефиниције засноване на теорији мера функционисале само са степеном 2.

Интерпретација

Ентропија представља меру просечног информационог садржаја по симболу извора који представља неки систем или информациону секвенцу. У теорији информација, као мера за количину информације у некој поруци може послужити колико се променила вероватноћа догађаја под утицајем те поруке. На пример, ако за време лета временска прогноза за сутрашњи дан најави 30° C, то нам неће донети много информација, јер не садржи ништа неочекивано. Међутим, ако се иста таква прогноза догоди зими, то представља потпуно неочекивану вест и самим тим садржи много информација. Под информацијом се може сматрати и мера уклоњене несигурности. Што се више симбола прими од извора, добијамо више информација и опада несигурност око онога шта је могло бити послато.

Дефиниција информационог садржаја се може на следећи начин описати: ако се деси догађај чија је вероватноћа $p_{i}$, тада је кроз то изабран један конкретан догађај из хипотетичког скупа од ${\tfrac {1}{p_{i}}}$ једнако вероватних догађаја. Да би се ови догађаји међусобно разликовали, потребно им је доделити $\log _{2}\left({\tfrac {1}{p_{i}}}\right)=-\log _{2}(p_{i})$ бита. Ова вредност представља количину информације једног одређеног догађаја у битима. Када се количина информације сваког догађаја пондерише са вероватноћом истог догађаја, и када се саберу (тј. пронађе се математичко очекивање количине информације), добијамо средњу или очекивану количину информације по симболу.

Јединица Шенон дефинише количину информације коју садржи порука о догађају са вероватноћом $p=0,5$. На пример, саопштење о томе да је метални новчић пао на одређену страну доноси информацију од 1 Шенона. Или, ако на пријемној страни бинарног телекомуникационог система, чији је сигнал састављен од биполарних импулса константне амплитуде, меримо поларност долазећих импулса, и ако је вероватноћа појављивања позитивних и негативних амплитуда једнака, онда сваки импулс носи информацију од 1 Шенона. Међутим, ако вероватноће појављивања позитивних и негативних амплитуда нису једнаке, онда један импулс доноси пријемнику неку другу количину информација која није 1 Шенон. Треба разликовати појам бинарни дигит, скраћено бит, од појма Шенон. Бит је само носилац информације и физички је представљен импулсом који може да има два стања. У зависности од вероватноће појављивања стања, бит може да доноси пријемнику већу или мању количину информација. Само кад су вероватноће појављивања два стања код бита једнаке, онда бит носи количину информације од 1 Шенона.

Види још

• Ентропија

Литература

• 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. стр. 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 одржавање: Вишеструка имена: списак аутора (веза)
• Stone, J. V. Chapter 1 of Information Theory: A Tutorial Introduction, University of Sheffield, England. 2014. ISBN 978-0956372857..

Спољашње везе

• Hazewinkel Michiel, ур. (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)