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

Из Википедије, слободне енциклопедије

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

Шенонова ентропија представља апсолутну границу најбоље могуће компресије без губитака било какве комуникације, под извесним ограничењима: ако третирамо поруке да су кодоване као низ независних случајних променљивих са истом расподелом, прва Шенонова теорема показује да, у граничном случају, средња дужина најкраће могуће репрезентације за кодовање порука у датом алфабету је њихова ентропија подељена са логаритмом броја симбола у циљном алфабету.

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

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

Шенон је дефинисао ентропију 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.

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

Ентропија представља меру просечног информационог садржаја по симболу извора који представља неки систем или информациону секвенцу. У теорији информација, као мера за количину информације у некој поруци може послужити колико се променила вероватноћа догађаја под утицајем те поруке. На пример, ако за време лета временска прогноза за сутрашњи дан најави 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 Шенона.[3]

Извори[уреди]

  1. ^ Schneier, B: Applied Cryptography, Second edition, page 234. John Wiley and Sons.
  2. ^ Shannon, Claude E.: Prediction and entropy of printed English, The Bell System Technical Journal, 30:50-64, January 1951.
  3. ^ Лукатела, Г: Статистичка теорија телекомуникација и теорија информација, pp. 258-259. Грађевинска књига, Београд, 1981.