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

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

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

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

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

. [4]

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

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

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

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

Дефиниција[уреди]

Шенон је дефинисао ентропију дискретног извора без меморије (дискретне случајне променљиве) над коначним алфабетом на следећи начин. Прво се додели свакој вероватноћи неког догађаја њена количина информације . Тада је ентропија по симболу дефинисана као очекивана вредност (математичко очекивање) количине информација

,

Нека је , тада је вероватноћа да се догоди симбол из алфабета, или еквивалентно[6]:11[7]:19–20

,

За граничну вредност се може показати да је нула. Према томе, сабирци са вероватноћом једнаком нули не доприносе укупном збиру (тј. ентропији).

Ентропија за речи дужине је дата са

,

где је вероватноћа да ће се догодити реч . Ентропија је тада гранична вредност:

.

Ако су симболи статистички независни, тада за свако , као и .

Интерпретација[уреди]

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

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

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

Види још[уреди]

Референце[уреди]

  1. ^ Shannon, Claude E. (1948). „A Mathematical Theory of Communication”. Bell System Technical Journal. 27 (3): 379—423. doi:10.1002/j.1538-7305.1948.tb01338.x. hdl:11858/00-001M-0000-002C-4314-2.  (PDF, archived from here)
  2. ^ Schneier, B: Applied Cryptography, Second edition, page 234. John Wiley and Sons.
  3. ^ Shannon, Claude E.: Prediction and entropy of printed English, The Bell System Technical Journal, 30:50-64, January 1951.
  4. ^ Pathria, R. K.; Beale, Paul (2011). Statistical Mechanics (Third Edition). Academic Press. стр. 51. ISBN 978-0123821881. 
  5. ^ Shannon, Claude E. (1948). „A Mathematical Theory of Communication” (PDF). Bell System Technical Journal. 27. , July and October
  6. ^ Borda, Monica (2011). Fundamentals in Information Theory and Coding. Springer. ISBN 978-3-642-20346-6. 
  7. ^ Han, Te Sun & Kobayashi, Kingo (2002). Mathematics of Information and Coding. American Mathematical Society. ISBN 978-0-8218-4256-0. 
  8. ^ Лукатела, Г: Статистичка теорија телекомуникација и теорија информација, pp. 258-259. Грађевинска књига, Београд, 1981.

Литература[уреди]

Спољашње везе[уреди]