Теорија информације

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

Теорија информације је математичка дисциплина настала у 20. веку. Логаритамски израз за количину информације је предложио Хартли 1928. године, у свом раду „Пренос информације“. Затим ју је 1948. поопштио амерички инжењер и математичар Клод Шенон, и нешто раније, руски математичар Андреј Николајевич Колмогоров. Исте 1948. године је амерички математичар Норберт Винер у свом раду „Кибернетика“ изнео свој приступ количини информације система. Десило се да је математичка теорија информације настала „одједном“, малтене у неколико радова зачетника и да је у тим радовима „нацртан“ оквир за целу будућу дисциплину. Покретачко место целог тог развоја је откриће, математичка дефиниција појма „количина података“. И данас се сматра да је идеју за мерење количине информације први добио управо амерички инжењер Хартли 1928. године, али му историја математике не придаје велики значај можда због нејасноћа и (математички) непрецизних објашњења.

Информација[уреди]

Математичко тврђење, односно математички исказ је израз, који може бити Тачано, или Нетачан. То је основа тзв. бинарне логике, дела математичке логике. Помоћу бинарне логике је могуће дефинисати сваки исказ поливалентне логике. Ове посљедње математичке логике, поред бинарних вредности: \top, \bot, тј. тачно, нетачно, укључују читав спектар одговора „можда“.

Хартлијева дефиниција[уреди]

Када желимо једноставан одговор да или не постављамо питања која почињу са: „Да ли је ...“. На пример питање „Да ли је ова подлога бела?“ тражи једноставнији одговор од питања: „Какве је боје ова подлога?“. У првом случају имамо само дилему да-не, у другом случају имамо спектар боја. Када имамо спектар боја имамо већу дилему, па ћемо рећи да је тада неизвесност већа.

На пример, када постоји 8 једнако могућих избора за боју подлоге, а није унапред познат следећи избор, мора се постављати више од једног бинарног питања да би се дошло до одговора. Зато је неодређеност избора већа. Тачније:

Неодређеност је најмања количина података потребних за препознавање датог елемента.

Неодређеност исказа се може дефинисати као најмањи број питања чији је једини допустив одговор да-не, потребних да се дође до одговора. Свако тако постављено питање дефинишемо као један бит. Дакле број бита је број бинарних питања.

Колико бинарних питања треба поставити, да би се сазнао један од 8 бројева? Одговор је 3. На пример, замислили сте број 6.

1. питање: Да ли је то један од бројева 1, 2, 3, 4? Одговор: Не.

2. питање: Да ли је то један од бројева 5, 6? Одговор: Да.

3. питање: Да ли је то број 5? Одговор: Не.

Решење: Замишљени број је био 6.

Број (бинарних) питања је 3. Неодређеност замишљеног броја била је 3. Информација коју добијамо сазнањем замишљеног броја је 3.

Колико бинарних питања треба поставити да би се сазнао један од 16 бројева? Одговор је 4. Уопште, колико бинарних питања треба поставити да би се сазнао један од 2^n бројева? Одговор је n.

Амерички инжењер Р. В. Л. Хартли је у свом раду „Пренос информације“, 1928. године предложио да се количина информације дефинише помоћу логаритма броја једнако вероватних могућности избора. То је наставак претходних примера.

Када имамо n=1,2,3,... једнако вероватних елемената, тада је вероватноћа избора једног од њих p=P(n)=\frac{1}{n}. Информација, тј. количина информације коју добијамо сазнањем једне од n једнако вероватних вести, према Хартлију је:

I(p)=-log_2P(n)=log_2n.

На пример, логаритам по бази два од 1 је 0, од 2 је 1, од 4 је 2, од 8 је 3, од 16 је 4, итд.

Количина информације, зовемо је кратко информација, коју добијамо након случајног опита са једнаковероватним исходима, је логаритам по бази 2 вероватноће тог опита.

Шенонова дефиниција[уреди]

Хартлијева информација, формула, служи само у случају мерења једнако вероватних исхода. Бар тако се чини на први поглед. Међутим, шта да радимо ако је случај сложенији. Када имамо различито вероватне исходе и хоћемо да меримо информацију за сваки од случајева. Показаћемо да се полазећи од Хартлијеве може доћи до дефиниције информације за сложеније случајеве, користећи већ познати појам математичке средње вредности. То је открио Клод Шенон у знаменитом раду „Математичка теорија комуникације“, који је написао заједно са В. Вивером 1949. године.

Ако имамо шест куглица, по две у бојама: црвеној, плавој и белој. Рецимо да бирамо једну од шест, једнако вероватних, али тражен је један од одговора:

  1. извучена куглица је бела - вероватноћа је 2/6;
  2. извучена куглица није бела - вероватноћа је 4/6.

Хартлијева информација за први и други случај била би: I_1=-log_2\frac{2}{6}, односно I_2=-log_2\frac{4}{6}. Средња вредност, тј. математичко очекивање за ова два броја је: I=-p_1I_1-p_2I_2. Логаритми вероватноћа су негативни бројеви! Дакле

I=- \frac{2}{6}log_2 \frac{2}{6}- \frac{4}{6}log_2 \frac{4}{6}.

Општије, када имамо два исхода, вероватноћа p_1 и p_2, тада нам резултат случајног бирања доноси информацију:

I=-p_1log_2p_1-p_2log_2p_2.

Уопште, када имамо низ n=2,3,4,... исхода, истих или различитих вероватноћа p_1,p_2,...,p_n, тада нам резултат случајног догађаја доноси информацију I која је средња вредност, тј. математичко очекивање, позитивних вредности логаритама вероватноћа. Према томе,

I=-p_1log_2p_1-p_2log_2p_2-...-p_nlog_2p_n.

То је Шенонова дефиниција информације. Откриће да се информација може мерити, колико једноставно, толико је било невероватно за математичаре. Била је веома изненађујућа чињеница да можемо (математички прецизно) рећи „има толико и толико бита информације у датој новинској вести“, баш као када кажемо „овај бурек је тежак 300 грама“. Математичари су били у шоку и неверици, али техника није чекала. У другој половини 20. века је наступила револуција информатике. За то време је математичка теорија информације полако, полако напредовала.


Неодређеност[уреди]

Норберт Винер је 1948. године у свом делу Кибернетика дефинисао информацију у систему као меру његове организованости, док је неодређеност система мера његове неорганизованости. По Винеру је неодређеност само негација информације као одраз у огледалу. Количински су оне једнаке. Колико имате неодређености у опиту пре, толико имате информације у опиту након реализације случајног догађаја. Другим речима, када говоримо о количинама, у истим системима јединица, морало би бити:

(информација) = (неодређеност).

У једнакости лево и десно, имамо исте количине нечега после и пре сазнања. Он није знао за радове Шенона који су објављени тек следеће године. Решење је пронашао у термодинамици!

Аустријски физичар Лудвиг Болцман је још далеке 1872. године изучавао, тада нову науку, термодинамику и открио ентропију гаса. Болцман је уочио да је ентропија мера нереда у термодинамичком систему и да систем временом тежи већој ентропији. Меру нереда система са вероватноћама исхода p_1, p_2, p_3, ..., где је p_1+p_2+p_3+...=1, означио је са H и извео је свој чувени израз за неред термодинамичког система:

H(p_1,p_2,p_3,...)=-p_1log_2p_1-p_2log_2p_2-p_3log_2p_3-....

Обзиром на претходну формулу Винера, добијамо да је информација I = H, тј. да је Винер-Болцманова формула за количину информације тачно иста као Шенонова.

Болцман је своју ентропију појаснио на примеру чаше чисте воде у коју би сипао мастило. Временом сва вода постаје обојена, јер се у свом хаотичном кретању честице воде мешају са честицама мастила, правећи све слабију разлику између границе ових двеју течности. Тако се повећава неред, односно ентропија система у чаши. Систем тежи стању у којем сви догађаји имају једнаке вероватноће. Обрнут процес се практично не догађа и зато су термодинамички процеси иреверзибилни (неповратни).

Данас можемо рећи да је Болцман описивао тзв. ергодичке процесе, код којих се ентропија спонтано повећава до своје максималне вредности. Пример са уљем, уместо мастила у Болцмановој чаши био би супротан, тзв. неергодички процес.

Основна теорема[уреди]

Питање математичке истинитости није ствар провере у лабораторији, експеримента, или веровања у сопствена чула. Математичка истина се не доказује провером у пракси.

Овде се бавимо питањем може ли се Хартлијева дефиниција информације, заснована на целим бројевима (навели смо само примере за 8 и 16) могућности поопштити на све целе бројеве, и даље на све позитивне реалне бројеве?

1. Пример:

Фабрика производи 16 врста кошуља за чију израду користи 64 врсте дезена. Претпоставка је да је сваки модел произведен у истом броју комада. Колико бита има неодређеност једне кошуље?

Број свих модела које производи фабрика је 16х64=1024.

(неодређеност) = log_2 1024 = 10 бита,
= log_2 16 + log_2 64 = 4 + 6 бита.

Количина неодређености је увек позитиван број. Када нема неизвесности, неодређеност је нула, и кажемо да нема информације. Када расте неизвесност, расте и неодређеност, тачније расте реципрочна вредност вероватноће.

2. Пример:

Када имамо n = 1, 2, 3, ... једнако вероватних елемената тада је вероватноћа избора једног од њих p=P(n)=\frac{1}{n}, а информација према Хартлију је I(p)=-log_2P(n)=log_2 n.

Са само једним елементом n = 1 је случај без неизвесности избора, па је и информација нула (логаритам јединице је нула), тј. нема информације. Међутим, информација је позитивна, растућа функција броја n могућих исхода. Такође важи да је адитивна функција, у смислу:

логаритам производа једнак је збиру логаритама, тј.
 log_2 mn=log_2 m + log_2 n , па је
 I(mn)=I(m)+I(n).

Дакле Хартлијева информација производа једнака је збиру Хартлијевих информација. Сада постављамо питање да ли је тачно и обрнуто.

Теорема 
Нека је f(x) непрекидна функција дефинисана на скупу реалних бројева x > 1. Ако је f(x):
(i) позитивна, тј. за свако x > 1 је f(x) > 0,
(ii) растућа, тј. за x < y је f(x) < f(y),
(iii) f(xy) = f(x) + f(y) за свако x, y из скупа реалних бројева и x, y > 1
тада је f(x)=C \cdot log_bx, где су C > 0, b > 1 произвољни реални бројеви.

Доказ. За свако x > 1 и за свако r > 0 постоји број k = 0, 1, 2, ... такав да је

x^k \le 2^r < x^{k+1}.

На основу овога и особине (ii) је

f(x^k) \le f(2^r) < f(x^{k+1}), одакле се због (iii) добија
k \cdot f(x) \le r \cdot f(2) < (k+1) \cdot f(x) . Како према (i) је f(x)> 0, дељењем ових неједнакости са
r \cdot f(x) имамо
\frac{k}{r} \le \frac{f(2)}{f(x)} < \frac{k}{r}+ \frac{1}{r}.

Функција f(x)=log_b x, b > 1 има особине (i)-(iii) па горње неједнакости важе и за њу, тј.

\frac{k}{r} \le \frac{log_2b}{log_bx}<\frac{k}{r}+\frac{1}{r}. На основу тога је
\left| \frac{log_b2}{log_bx} - \frac{f(x)}{f(2)} \right|<\frac{1}{r}, за свако r > 0 па и за произвољно велико r, због чега је израз у апослутној загради последње неједнакости нула, тј.
f(x)=\frac{f(2)}{log_b2} \cdot log_bx, односно
f(x)=C \cdot log_bx. Крај доказа.

Дакле, Хартлијеву информацију је могуће само толико поопштити да уместо логаритамске базе 2 узмемо неки други број, дозвољен за базу логаритма.

На пример, ако за јединицу информације узмемо децит, један од 10 једнако вероватних догађаја, тада радимо са декадним логаритмима па је -I_{10}(x)=log_{10}x=log_{10}2 \cdot log_2x, те добијамо 1 децит = 0,30103... бита.

На пример, природна јединица информације, скраћено „нат“ или „нит“ користи базу природног логаритма е = 2,71828.... Тада је ln N = ln 2 \cdot log_2 N, па је 1 нат = 0,69315... бита.

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