Teorija informacije

Teorija informacije je matematička disciplina nastala u 20. veku. Logaritamski izraz za količinu informacije je predložio Hartli 1928. godine, u svom radu „Prenos informacije“. Zatim ju je 1948. poopštio američki inženjer i matematičar Klod Šenon, i nešto ranije, ruski matematičar Andrej Nikolajevič Kolmogorov. Iste 1948. godine je američki matematičar Norbert Viner u svom radu „Kibernetika“ izneo svoj pristup količini informacije sistema. Desilo se da je matematička teorija informacije nastala „odjednom“, maltene u nekoliko radova začetnika i da je u tim radovima „nacrtan“ okvir za celu buduću disciplinu. Pokretačko mesto celog tog razvoja je otkriće, matematička definicija pojma „količina podataka“. I danas se smatra da je ideju za merenje količine informacije prvi dobio upravo američki inženjer Hartli 1928. godine, ali mu istorija matematike ne pridaje veliki značaj možda zbog nejasnoća i (matematički) nepreciznih objašnjenja.

Informacija

Matematičko tvrđenje, odnosno matematički iskaz je izraz, koji može biti Tačan, ili Netačan. To je osnova tzv. binarne logike, dela matematičke logike. Pomoću binarne logike je moguće definisati svaki iskaz polivalentne logike. Ove posljednje matematičke logike, pored binarnih vrednosti: $\top ,\bot$, tj. tačno, netačno, uključuju čitav spektar odgovora „možda“.

Hartlijeva definicija

Kada želimo jednostavan odgovor da ili ne postavljamo pitanja koja počinju sa: „Da li je ...“. Na primer pitanje „Da li je ova podloga bela?“ traži jednostavniji odgovor od pitanja: „Kakve je boje ova podloga?“. U prvom slučaju imamo samo dilemu da-ne, u drugom slučaju imamo spektar boja. Kada imamo spektar boja imamo veću dilemu, pa ćemo reći da je tada neizvesnost veća.

Na primer, kada postoji 8 jednako mogućih izbora za boju podloge, a nije unapred poznat sledeći izbor, mora se postavljati više od jednog binarnog pitanja da bi se došlo do odgovora. Zato je neodređenost izbora veća. Tačnije:

Neodređenost je najmanja količina podataka potrebnih za prepoznavanje datog elementa.

Neodređenost iskaza se može definisati kao najmanji broj pitanja čiji je jedini dopustiv odgovor da-ne, potrebnih da se dođe do odgovora. Svako tako postavljeno pitanje definišemo kao jedan bit. Dakle broj bita je broj binarnih pitanja.

Koliko binarnih pitanja treba postaviti, da bi se saznao jedan od 8 brojeva? Odgovor je 3. Na primer, zamislili ste broj 6.

1. pitanje: Da li je to jedan od brojeva 1, 2, 3, 4? Odgovor: Ne.

2. pitanje: Da li je to jedan od brojeva 5, 6? Odgovor: Da.

3. pitanje: Da li je to broj 5? Odgovor: Ne.

Rešenje: Zamišljeni broj je bio 6.

Broj (binarnih) pitanja je 3. Neodređenost zamišljenog broja bila je 3. Informacija koju dobijamo saznanjem zamišljenog broja je 3.

Koliko binarnih pitanja treba postaviti da bi se saznao jedan od 16 brojeva? Odgovor je 4. Uopšte, koliko binarnih pitanja treba postaviti da bi se saznao jedan od $2^{n}$ brojeva? Odgovor je n.

Američki inženjer R. V. L. Hartli je u svom radu „Prenos informacije“, 1928. godine predložio da se količina informacije definiše pomoću logaritma broja jednako verovatnih mogućnosti izbora. To je nastavak prethodnih primera.

Kada imamo $n=1,2,3,...$ jednako verovatnih elemenata, tada je verovatnoća izbora jednog od njih $p=P(n)={\frac {1}{n}}$. Informacija, tj. količina informacije koju dobijamo saznanjem jedne od n jednako verovatnih vesti, prema Hartliju je:

$I(p)=-log_{2}P(n)=log_{2}n$.

Na primer, logaritam po bazi dva od 1 je 0, od 2 je 1, od 4 je 2, od 8 je 3, od 16 je 4, itd.

Količina informacije, zovemo je kratko informacija, koju dobijamo nakon slučajnog opita sa jednakoverovatnim ishodima, je logaritam po bazi 2 verovatnoće tog opita.

Šenonova definicija

Hartlijeva informacija, formula, služi samo u slučaju merenja jednako verovatnih ishoda. Bar tako se čini na prvi pogled. Međutim, šta da radimo ako je slučaj složeniji. Kada imamo različito verovatne ishode i hoćemo da merimo informaciju za svaki od slučajeva. Pokazaćemo da se polazeći od Hartlijeve može doći do definicije informacije za složenije slučajeve, koristeći već poznati pojam matematičke srednje vrednosti. To je otkrio Klod Šenon u znamenitom radu „Matematička teorija komunikacije“, koji je napisao zajedno sa V. Viverom 1949. godine.

Ako imamo šest kuglica, po dve u bojama: crvenoj, plavoj i beloj. Recimo da biramo jednu od šest, jednako verovatnih, ali tražen je jedan od odgovora:

1. izvučena kuglica je bela - verovatnoća je 2/6;
2. izvučena kuglica nije bela - verovatnoća je 4/6.

Hartlijeva informacija za prvi i drugi slučaj bila bi: $I_{1}=-log_{2}{\frac {2}{6}}$, odnosno $I_{2}=-log_{2}{\frac {4}{6}}$. Srednja vrednost, tj. matematičko očekivanje za ova dva broja je: $I=-p_{1}I_{1}-p_{2}I_{2}$. Logaritmi verovatnoća su negativni brojevi! Dakle

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

Opštije, kada imamo dva ishoda, verovatnoća $p_{1}$ i $p_{2}$, tada nam rezultat slučajnog biranja donosi informaciju:

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

Uopšte, kada imamo niz $n=2,3,4,...$ ishoda, istih ili različitih verovatnoća $p_{1},p_{2},...,p_{n}$, tada nam rezultat slučajnog događaja donosi informaciju I koja je srednja vrednost, tj. matematičko očekivanje, pozitivnih vrednosti logaritama verovatnoća. Prema tome,

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

To je Šenonova definicija informacije. Otkriće da se informacija može meriti, koliko jednostavno, toliko je bilo neverovatno za matematičare. Bila je veoma iznenađujuća činjenica da možemo (matematički precizno) reći „ima toliko i toliko bita informacije u datoj novinskoj vesti“, baš kao kada kažemo „ovaj burek je težak 300 grama“. Matematičari su bili u šoku i neverici, ali tehnika nije čekala. U drugoj polovini 20. veka je nastupila revolucija informatike. Za to vreme je matematička teorija informacije polako, polako napredovala.

Neodređenost

Norbert Viner je 1948. godine u svom delu Kibernetika definisao informaciju u sistemu kao meru njegove organizovanosti, dok je neodređenost sistema mera njegove neorganizovanosti. Po Vineru je neodređenost samo negacija informacije kao odraz u ogledalu. Količinski su one jednake. Koliko imate neodređenosti u opitu pre, toliko imate informacije u opitu nakon realizacije slučajnog događaja. Drugim rečima, kada govorimo o količinama, u istim sistemima jedinica, moralo bi biti:

(informacija) = (neodređenost).

U jednakosti levo i desno, imamo iste količine nečega posle i pre saznanja. On nije znao za radove Šenona koji su objavljeni tek sledeće godine. Rešenje je pronašao u termodinamici!

Austrijski fizičar Ludvig Bolcman je još daleke 1872. godine izučavao, tada novu nauku, termodinamiku i otkrio entropiju gasa. Bolcman je uočio da je entropija mera nereda u termodinamičkom sistemu i da sistem vremenom teži većoj entropiji. Meru nereda sistema sa verovatnoćama ishoda $p_{1},p_{2},p_{3},...$, gde je $p_{1}+p_{2}+p_{3}+...=1$, označio je sa H i izveo je svoj čuveni izraz za nered termodinamičkog sistema:

$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}-...$.

Obzirom na prethodnu formulu Vinera, dobijamo da je informacija I = H, tj. da je Viner-Bolcmanova formula za količinu informacije tačno ista kao Šenonova.

Bolcman je svoju entropiju pojasnio na primeru čaše čiste vode u koju bi sipao mastilo. Vremenom sva voda postaje obojena, jer se u svom haotičnom kretanju čestice vode mešaju sa česticama mastila, praveći sve slabiju razliku između granice ovih dveju tečnosti. Tako se povećava nered, odnosno entropija sistema u čaši. Sistem teži stanju u kojem svi događaji imaju jednake verovatnoće. Obrnut proces se praktično ne događa i zato su termodinamički procesi ireverzibilni (nepovratni).

Danas možemo reći da je Bolcman opisivao tzv. ergodičke procese, kod kojih se entropija spontano povećava do svoje maksimalne vrednosti. Primer sa uljem, umesto mastila u Bolcmanovoj čaši bio bi suprotan, tzv. neergodički proces.

Osnovna teorema

Pitanje matematičke istinitosti nije stvar provere u laboratoriji, eksperimenta, ili verovanja u sopstvena čula. Matematička istina se ne dokazuje proverom u praksi.

Ovde se bavimo pitanjem može li se Hartlijeva definicija informacije, zasnovana na celim brojevima (naveli smo samo primere za 8 i 16) mogućnosti poopštiti na sve cele brojeve, i dalje na sve pozitivne realne brojeve?

1. Primer:

Fabrika proizvodi 16 vrsta košulja za čiju izradu koristi 64 vrste dezena. Pretpostavka je da je svaki model proizveden u istom broju komada. Koliko bita ima neodređenost jedne košulje?

Broj svih modela koje proizvodi fabrika je 16h64=1024.

(neodređenost) = $log_{2}1024$ = 10 bita,

$=log_{2}16+log_{2}64=4+6$ bita.

Količina neodređenosti je uvek pozitivan broj. Kada nema neizvesnosti, neodređenost je nula, i kažemo da nema informacije. Kada raste neizvesnost, raste i neodređenost, tačnije raste recipročna vrednost verovatnoće.

2. Primer:

Kada imamo n = 1, 2, 3, ... jednako verovatnih elemenata tada je verovatnoća izbora jednog od njih $p=P(n)={\frac {1}{n}}$, a informacija prema Hartliju je $I(p)=-log_{2}P(n)=log_{2}n$.

Sa samo jednim elementom n = 1 je slučaj bez neizvesnosti izbora, pa je i informacija nula (logaritam jedinice je nula), tj. nema informacije. Međutim, informacija je pozitivna, rastuća funkcija broja n mogućih ishoda. Takođe važi da je aditivna funkcija, u smislu:

logaritam proizvoda jednak je zbiru logaritama, tj.

$log_{2}mn=log_{2}m+log_{2}n$, pa je

$I(mn)=I(m)+I(n)$.

Dakle Hartlijeva informacija proizvoda jednaka je zbiru Hartlijevih informacija. Sada postavljamo pitanje da li je tačno i obrnuto.

Teorema

Neka je f(x) neprekidna funkcija definisana na skupu realnih brojeva x > 1. Ako je f(x):

(i) pozitivna, tj. za svako x > 1 je f(x) > 0,

(ii) rastuća, tj. za x < y je f(x) < f(y),

(iii) f(xy) = f(x) + f(y) za svako x, y iz skupa realnih brojeva i x, y > 1

tada je $f(x)=C\cdot log_{b}x$, gde su C > 0, b > 1 proizvoljni realni brojevi.

Dokaz. Za svako x > 1 i za svako r > 0 postoji broj k = 0, 1, 2, ... takav da je

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

Na osnovu ovoga i osobine (ii) je

$f(x^{k})\leq f(2^{r})<f(x^{k+1})$, odakle se zbog (iii) dobija

$k\cdot f(x)\leq r\cdot f(2)<(k+1)\cdot f(x)$. Kako prema (i) je f(x)> 0, deljenjem ovih nejednakosti sa

$r\cdot f(x)$ imamo

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

Funkcija $f(x)=log_{b}x$, b > 1 ima osobine (i)-(iii) pa gornje nejednakosti važe i za nju, tj.

${\frac {k}{r}}\leq {\frac {log_{2}b}{log_{b}x}}<{\frac {k}{r}}+{\frac {1}{r}}$. Na osnovu toga je

$\left|{\frac {log_{b}2}{log_{b}x}}-{\frac {f(x)}{f(2)}}\right|<{\frac {1}{r}}$, za svako r > 0 pa i za proizvoljno veliko r, zbog čega je izraz u aposlutnoj zagradi poslednje nejednakosti nula, tj.

$f(x)={\frac {f(2)}{log_{b}2}}\cdot log_{b}x$, odnosno

$f(x)=C\cdot log_{b}x$. Kraj dokaza.

Dakle, Hartlijevu informaciju je moguće samo toliko poopštiti da umesto logaritamske baze 2 uzmemo neki drugi broj, dozvoljen za bazu logaritma.

Na primer, ako za jedinicu informacije uzmemo decit, jedan od 10 jednako verovatnih događaja, tada radimo sa dekadnim logaritmima pa je $-I_{10}(x)=log_{10}x=log_{10}2\cdot log_{2}x$, te dobijamo 1 decit = 0,30103... bita.

Na primer, prirodna jedinica informacije, skraćeno „nat“ ili „nit“ koristi bazu prirodnog logaritma e = 2,71828.... Tada je $lnN=ln2\cdot log_{2}N$, pa je 1 nat = 0,69315... bita.

Literatura

• Claude Elwood Shannon (1948), "A Mathematical Theory of Communication", Bell System Technical Journal, 27, pp. 379–423 & 623–656, July & October, 1948. PDF. Arhivirano 1998-07-15 na Wayback Machine-u
  Notes and other formats. Arhivirano 1998-01-31 na Wayback Machine-u
• R.V.L. Hartley, "Transmission of Information" Arhivirano 2011-10-04 na Wayback Machine-u, Bell System Technical Journal, July 1928
• Andrey Kolmogorov (1968), "Three approaches to the quantitative definition of information" in International Journal of Computer Mathematics.
• J. L. Kelly, Jr., Saratoga.ny.us Arhivirano 2011-07-16 na Wayback Machine-u, "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. Develop. Vol. 5, No. 3, 1961
• Arndt, C. Information Measures, Information and its Description in Science and Engineering (Springer Series: Signals and Communication Technology), 2004, 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. Information Theory and Reliable Communication. New York: John Wiley and Sons, 1968. 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, TM, Thomas, JA. Elements of information theory, 1st Edition. New York: Wiley-Interscience, 1991. ISBN 0-471-06259-6.

2nd Edition. New York: Wiley-Interscience, 2006. ISBN 0-471-24195-4.

• Csiszar, I, Korner, J. Information Theory: Coding Theorems for Discrete Memoryless Systems Akademiai Kiado: 2nd edition, 1997. ISBN 963-05-7440-3
• MacKay, DJC. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
• Mansuripur, M. Introduction to Information Theory. New York: Prentice Hall, 1987. ISBN 0-13-484668-0
• 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, CE. Warren Weaver. The Mathematical Theory of Communication. Univ of Illinois Press, 1949. ISBN 0-252-72548-4
• 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, 2002. ISBN 0-306-46791-7.
• Yeung, RW. Information Theory and Network Coding Springer 2008, 2002. ISBN 978-0-387-79233-0
• Leon Brillouin, Science and Information Theory, Mineola, N.Y.: Dover, [1956, 1962] 2004. ISBN 0-486-43918-6
• James Gleick, The Information: A History, a Theory, a Flood, New York: Pantheon, 2011. ISBN 978-0-375-42372-7
• A. I. Khinchin, Mathematical Foundations of Information Theory, New York: Dover, 1957. 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
• Tom Siegfried, The Bit and the Pendulum, Wiley, 2000. ISBN 0-471-32174-5
• Charles Seife, Decoding The Universe, Viking, 2006. 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, Information Theory in Computer Vision and Pattern Recognition, Springer, 2009. ISBN 978-1-84882-296-2

Vanjske veze

• Erill I. (2012), "A gentle introduction to information content in transcription factor binding sites" (University of Maryland, Baltimore County)
• Hazewinkel Michiel, ur. (2001). „Information”. Encyclopaedia of Mathematics. Springer. 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
• Schneider T. D. (2014), "Information Theory Primer"
• Srinivasa, S., "A Review on Multivariate Mutual Information Arhivirano 2009-03-27 na Wayback Machine-u"
• IEEE Information Theory Society Arhivirano 2009-01-22 na Wayback Machine-u and ITSoc review articles Arhivirano 2009-01-22 na Wayback Machine-u