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

Теорија информације је математичка дисциплина настала у 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_{2}P(n)=log_{2}n$.

На пример, логаритам по бази два од 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_{1}I_{1}-p_{2}I_{2}$. Логаритми вероватноћа су негативни бројеви! Дакле

$I=-{\frac {2}{6}}log_{2}{\frac {2}{6}}-{\frac {4}{6}}log_{2}{\frac {4}{6}}$.

Општије, када имамо два исхода, вероватноћа $p_{1}$ и $p_{2}$, тада нам резултат случајног бирања доноси информацију:

$I=-p_{1}log_{2}p_{1}-p_{2}log_{2}p_{2}$.

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

$I=-p_{1}log_{2}p_{1}-p_{2}log_{2}p_{2}-...-p_{n}log_{2}p_{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_{1}log_{2}p_{1}-p_{2}log_{2}p_{2}-p_{3}log_{2}p_{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_{2}P(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_{b}x$, где су C > 0, b > 1 произвољни реални бројеви.

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

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

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

$f(x^{k})\leq f(2^{r})<f(x^{k+1})$, одакле се због (iii) добија

$k\cdot f(x)\leq r\cdot f(2)<(k+1)\cdot f(x)$. Како према (i) је f(x)> 0, дељењем ових неједнакости са

$r\cdot f(x)$ имамо

${\frac {k}{r}}\leq {\frac {f(2)}{f(x)}}<{\frac {k}{r}}+{\frac {1}{r}}$.

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

${\frac {k}{r}}\leq {\frac {log_{2}b}{log_{b}x}}<{\frac {k}{r}}+{\frac {1}{r}}$. На основу тога је

$\left|{\frac {log_{b}2}{log_{b}x}}-{\frac {f(x)}{f(2)}}\right|<{\frac {1}{r}}$, за свако r > 0 па и за произвољно велико r, због чега је израз у апослутној загради последње неједнакости нула, тј.

$f(x)={\frac {f(2)}{log_{b}2}}\cdot log_{b}x$, односно

$f(x)=C\cdot log_{b}x$. Крај доказа.

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

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

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

Теорија информације у психологији

За више информација погледајте: Теорија информације у психологији

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

Literatura

• Andrey Kolmogorov (1968), "„Three approaches to the quantitative definition of information”. doi:10.1080/00207166808803030. " in International Journal of Computer Mathematics.
• J. L. Kelly, Jr., Betbubbles.com, "A New Interpretation of Information Rate" Bell System Technical Journal, Vol. 35, July 1956, pp. 917–26.
• R. Landauer, IEEE.org, "Information is Physical" Proc. Workshop on Physics and Computation PhysComp'92 (IEEE Comp. Sci.Press, Los Alamitos, 1993) pp. 1–4.
• R. Landauer, IBM.com, "Irreversibility and Heat Generation in the Computing Process" IBM J. Res. Dev. „IBM Research Publications | IBM Research” (PDF). 5 (3). 9. 2. 2021. CS1 одржавање: Формат датума (веза), 1961
• Timme, Nicholas; Alford, Wesley; Flecker, Benjamin; Beggs, John M. (2012). „Multivariate information measures: an experimentalist's perspective”. arXiv:1111.6857  [cs.IT]. 
• Arndt, C (2004). Information Measures, Information and its Description in Science and Engineering. Springer Series: Signals and Communication Technology. ISBN 978-3-540-40855-0. 
• Ash, RB. Information Theory. New York: Interscience, 1965. ISBN 0-470-03445-9. . New York: Dover. 1990. ISBN 0-486-66521-6. 
• Gallager, R (1968). Information Theory and Reliable Communication. New York: John Wiley and Sons. ISBN 0-471-29048-3. 
• Goldman, S. Information Theory. New York: Prentice Hall, 1953. New York: Dover 1968 ISBN 0-486-62209-6. 2005. ISBN 0-486-44271-3.
• Cover, Thomas; Thomas, Joy A. (2006). Elements of information theory (2nd изд.). New York: Wiley-Interscience. ISBN 0-471-24195-4. 
• Csiszar, I, Korner, J. Information Theory: Coding Theorems for Discrete Memoryless Systems Akademiai Kiado:. (2nd изд.). 1997. ISBN 963-05-7440-3. 
• MacKay, David J. C (2003). Information Theory, Inference, and Learning Algorithms. Cambridge: Cambridge University Press. ISBN 0-521-64298-1. 
• Mansuripur, M (1987). Introduction to Information Theory. New York: Prentice Hall. ISBN 0-13-484668-0. 
• McEliece, R. The Theory of Information and Coding". Cambridge. 2002. ISBN 978-0521831857.
• Pierce, JR. "An introduction to information theory: symbols, signals and noise". Dover (2nd Edition). 1961 (reprinted by Dover 1980).
• Reza, F. An Introduction to Information Theory. New York: McGraw-Hill 1961. . New York: Dover. 1994. ISBN 0-486-68210-2. 
• Shannon, Claude; Weaver, Warren (1949). The Mathematical Theory of Communication (PDF). Urbana, Illinois: University of Illinois Press. ISBN 0-252-72548-4. LCCN 49-11922. 
• Stone, JV. Chapter 1 of book "Information Theory: A Tutorial Introduction", University of Sheffield, England. 2014. ISBN 978-0956372857.
• Yeung, RW. A First Course in Information Theory Kluwer Academic/Plenum Publishers, . Yeung, Raymond W. (2002). A First Course in Information Theory. Springer. ISBN 0-306-46791-7. .
• Yeung, RW. Information Theory and Network Coding Springe2002. ISBN 978-0-387-79233-0. стр. 2008.
• Leon Brillouin, Science and Information Theory, Mineola, N.Y.: Dover, [1956, 1962]. 2004. ISBN 0-486-43918-6.
• Gleick, James (2011). The Information: A History, a Theory, a Flood. New York: Pantheon. ISBN 978-0-375-42372-7. 
• Khinchin, A. I. (1957). Mathematical Foundations of Information Theory. New York: Dover. ISBN 0-486-60434-9. 
• H. S. Leff and A. F. Rex, Editors, Maxwell's Demon: Entropy, Information, Computing, Princeton University Press, Princeton, New Jersey. 1990. ISBN 0-691-08727-X.
• Robert K. Logan. What is Information? - Propagating Organization in the Biosphere, the Symbolosphere, the Technosphere and the Econosphere, Toronto: DEMO Publishing.
• Siegfried, Tom (2000). The Bit and the Pendulum. Wiley. ISBN 0-471-32174-5. 
• Seife, Charles (2006). Decoding the Universe. Viking. ISBN 0-670-03441-X. 
• Jeremy Campbell, Grammatical Man, Touchstone/Simon & Schuster. 1982. ISBN 0-671-44062-4.
• Henri Theil, Economics and Information Theory, Rand McNally & Company - Chicago, 1967.
• Escolano, Suau, Bonev (2009). Information Theory in Computer Vision and Pattern Recognition. Springer. ISBN 978-1-84882-296-2. CS1 одржавање: Вишеструка имена: списак аутора (веза)
• Vedral, Vlatko (2010). Decoding Reality: The Universe as Quantum Information. Oxford University Press. ISBN 978-0-19-923769-2. 
• Raymond W. Yeung, "Information Theory Архивирано на сајту Wayback Machine (20. октобар 2019)" (The Chinese University of Hong Kong)

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

• Hazewinkel, Michiel, ур. (2001) [1994], „Information”, Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4 
• Lambert F. L. (1999), "Shuffled Cards, Messy Desks, and Disorderly Dorm Rooms - Examples of Entropy Increase? Nonsense!", Journal of Chemical Education
• IEEE Information Theory Society and ITSOC Monographs, Surveys, and Reviews Архивирано на сајту Wayback Machine (12. јун 2018)