Heterocera scientia

A mostani számban információelméletről lesz szó. Sokan tudják, hogy milyen fontos a XXI. században az információ, de én ebben a cikkben nem az információs társadalomról fogok írni, vagy az információ jelentősségéről, hanem arról, hogy vajon hogyan mérhető az információ? Amit használok: Rényi Alfréd Napló az információelméletről c. írása, ami jelenleg új kiadásban az Ars Mathematica c. könyvében található meg.
Rényi Alfréd az egyik legnagyobb matematikusunk volt, 1921-ben született, és 48 éves korában halt meg, ebbe a nem túl hosszú életbe viszont rengeteg minden belefért. Eredetileg analízissel foglakozott, Riesz Frigyesnél írta a disszertációját. A máig megoldatlan Goldbach-sejtésben ő jutott legközelebb a teljes megoldáshoz: valószínűség-számítást alkalmazott számelméletben. Kb. 350 publikációja született, mindezt rengeteg kávéval és dohányzással katalizálta, tőle ered a mondás, amit tévesen Erdős Pálnak tulajdonítanak: A matematikus egy automata, ami kávéból matematikai tételeket gyárt. A szervezői tevékenységekben is otthon volt, meghatározó szerepe volt az alkalmazott Matematikai Intézet létrehozásában, ami ma már az ő nevét viseli (MTA Rényi Alfréd Matematikai Kutatóintézet).

Amiért most itt mégis megemlítésre kerül az nem más, mint a tudományt népszerűsítő munkája. Bár mindig nagyon optimista ember volt, 1956-ra kiábrándult az elvekből, nem volt hajlandó visszalépni a pártba, így helyét nála sokkal alkalmatlanabb emberek foglalták el. Viták kezdődtek a matematika alkalmazhatóságáról, ekkor fordult a figyelme a matematika népszerűsítése felé, ennek gyümölcsei a Dialógusok a matematikáról, a Levelek a valószínűségről és a Napló az információelméletről. Nagy történelmi és irodalmi műveltsége lehetővé tette, hogy gondolatait Pascal és Fermat levelezésének álcájába bújtassa, illetve Szókratész és Hippokratész, Arkhimédész és Hierón fiktív párbeszédébe illessze, ezáltal nagyon szórakoztató mégis mély írásokat létrehozva; műveit sok nyelvre lefordították, külföldön is nagy népszerűségre tettek szert. A jelenleg taglalt írást a Napló az információelméletrőlt sajnos nem tudta már befejezni, de így félkészen is nagyon elgondolkodtató, élvezetes művet hagyott hátra.
Egy egyetemi diák bőrébe bújva mesél az információelméletről:
„Ma volt az első előadás az információelméletről. (…) Rögtön el is határoztam, hogy e tárgyról nem jegyzetet írok, hanem naplót; nemcsak az előadáson hallottakat rögzítem, hanem saját gondolatimat is feljegyzem: azokat a kérdéseket, amelyeket önmagamnak felteszek és, persze, a válaszokat is, ha tudok rájuk válaszolni. (…) Az előadó először néhány szót szólt az információfogalom alapvető jelentőségéről. (…) Rámutatott, hogy minden élő szervezetben állandóan áramlik az információ: például az emberi szervezetben az érzékszervek információt gyűjtenek a külvilágból, ezt az idegrendszer továbbítja az agyba, az agy az így kapott információt feldolgozza, és ennek alapján utasítást – ami szintén információ – ad az izmoknak, amelyet szintén idegsejtek továbbítanak, stb. (…) Az elektronikus számítógépek lényege éppen abban áll, hogy e gépek nagy mennyiségű információt dolgoznak fel nagy sebességgel megadott program (vagyis információ) alapján, az automatizálás egyik fő problémája éppen az automatikus berendezés egyes részei közötti információcsere.(…) Azt mondotta, hogy az információ matematikai elmélete annak köszönhető, hogy felismerték: az információmennyiséget számmal lehet jellemezni, -hasonlóan ahhoz, ahogyan számmal lehet kifejezni távolságot, az időt, a tömeget, a hőmennyiséget stb.”
Először is megtudjuk, hogyan lehet a legegyszerűbben reprezentálni az információ mérhetőségét: a barkochba játék segítéségével! Az, hogy mennyi információra van szükségünk ahhoz, hogy kitaláljuk mire gondoltak a többiek, azzal mérhető, hogy hány (leginkább célravezető) kérdést kellett feltenni. A kérdés itt csakis eldöntendő kérdést jelöl. Például ha az előadáson éppen 32-en ülnek, és az előadó gondolt közülük valakire, akkor hány kérdésből lehet kitalálni, hogy ki az illető? A válasz: öt kérdés. Miért? Írjuk fel a neveket ábécésorrendben a táblára, és először tegyük fel azt a kérdést, hogy „Az első 16 név között van-e a gondolt személy?” Ha a válasz „igen”, akkor úgy folytatjuk, hogy „Az első 8-ban van-e?”, ha pedig nemleges volt a válasz akkor úgy, hogy „A második 16 név között az első 8-ban van-e?”. Jól látható, hogy ezzel a kérdezési móddal folyamatosan feleződik a lehetséges nevek halmaza, így 32=2^5 mellett valóban 5 kérdésből kitalálható kire gondolt az előadó. Vajon igaz-e az is, hogy ha egyszerre tehetem csak fel a kérdéseket (azaz az egyes kérdéseknél nem tudom az előző kérdésekre kapott válaszokat), akkor is kitalálható-e a név 5 kérdésből? A válasz szintén igen: a hallgatókat meg kell számozni 0-tól 31-ig, átváltani ezeket a sorszámokat kettes számrendszerbe, így összes névhez tartozik egy ötjegyű, 0-kból és 1-esekből álló számsorozat. Ez már előrevetít egyfajta kódolást a barkochbához: ha kérdésünkre a felelet „igen”, írjunk 1-est, ha pedig „nem” akkor 0-t, így helyettesíthető bármely felelet egy kettes számrendszerbeli számmal. Ez persze idáig nem szabályos matematikai definíció, de igen intuitív. Amikor az információ mennyiségét számokkal akarjuk kifejezni, szándékosan hagyjuk figyelmen kívül az információ jelentősségét. Tehát ha egy lánytól azt kérdezik, hogy „Kisasszony, szereti a sajtot?” illetve „Kisasszony, hozzám jön feleségül?”, akkor akármi is a válasz, egy egységnyi információt tartalmaz, a válaszok tartalma és jelentőségbeli eltérésének dacára. Más szavakkal: az információ egysége egyetlen 0-val illetve 1-gyel kifejezhető információ mennyisége. Tehát egy kettes számrendszerben felírt 20 jegyű szám minden egyes számjegye egy egységnyi információt tartalmaz. Innen ered az információ egységének elnevezése: binary digit, azaz bit (ami egyben egy szójáték is, mert a bit morzsát jelent), azaz egy bit egy morzsányi információ.

Néhány további példa:

Ha Magyarországon kereken 7,5 millió felnőtt állampolgárnak van személyi igazolványa, akkor egy tetszőleges felnőtt állampolgárra gondolva, hány kérdéssel tudjuk kitalálni, hogy kire gondoltam? Mivel 2^22=4194304 és 2^23=8388608, így 23 kérdésre van szükség. Ennek fényében igaz-e, hogy a személyi igazolvány sorszáma pontosa 23 bit információt tartalmaz? A válasz nem, hiszen csak akkor lenne igaz, ha a személyi igazolványokból pontosan 8388608 darab lenne, így az információ valahol 22 és 23 bit között van, egész pontosan kettes alapú logaritmus 7500000 (azaz az a kitevő, amire a kettőt emelve 7,5 milliót kapunk). Tehát ha úgy módosítjuk a barkochba szabályait, hogy N különböző dolog valamelyikére szabad csak gondolni, akkor a dolog kitalálásához log_2 N bit információra van szükségünk.

Ha 27 aranyérménk van, amelyből 1 hamis (azaz más fémből van, csak be van aranyozva – szemre nem lehet megkülönböztetni, de a súlya egy kicsivel kisebb, mint a valódié), akkor egy kétkarú mérleg segítségével hány mérésből lehet megtalálni biztosan a hamis érmét?
A megoldás a következő: a mérésnek három eredménye lehet: a serpenyő bal karja nehezebb, jobb karja nehezebb, vagy egyforma súlyúak. Ekkor tehát egy mérés eredménye log_2 3 információt adhat. Mivel log_2 27= 3× log_2 3, így legalább 3 mérés szükséges. Nézzük valóban így van-e:
Először tegyünk mindkét serpenyőbe 9-9 érmét, ha az egyik serpenyő felszáll, akkor abban van a hamis pénz, ha egyenlő súlyú a két kupac, akkor a harmadikban van. Ekkor azt a 9-est szétbontjuk 3-3-ra megismételve az előző gyakorlatot eldöntjük, hogy melyik hármasban van, végül három közül ugyanígy megtudjuk melyik a hamis.

Világos, hogyha eldöntendő kérdésre adott válasz egységnyi, azaz egy bit információt tartalmat, de akkor mi történik, ha bénán kérdezünk, és mondjuk 5 kérdésből ki lehetne találni, de mégsem tudom 5 kérdés után kitalálni? Hogyan lehetséges ez, hiszen 5 kérdésből 5 bitnyi információhoz kellene jutnunk! Vagy mi van akkor, ha kétszer teszem fel ugyanazt a kérdést? Akkor nyilván nem jutok 5 bitnyi információhoz; ezt általánosítva kaphatjuk meg a választ az „elveszett információra”: mi történik, ha nem „felezem” a halmazt, hanem egymást átfedő halmazokra kérdezek rá? Például, ha 1-10 közötti számot keresek, és azt a kérdést teszem fel elsőnek, hogy benne van-e a szám a 1,4,5,7,8 halmazban, aztán pedig, hogy benne van-e az 1,2,6,7,8 halmazban, akkor nyilván nem nyerek egy újabb bitnyi információt, hiszen néhány számra többször kérdezek rá, így 2 bitnek a „fele közös”. Tehát a két kérdésből együtt nem 2 bitet, hanem csak másfelet nyerek – ebből pedig az következik, hogy van nem egészértékű információ. Mit is jelent az, hogy valamit log_2 N kérdéssel lehet kitalálni, ha log_2 N nem egész szám? Általánosítsuk egy kicsit a barkochbát, és tegyük fel, hogy nem egyforma valószínűséggel gondolunk az egyes dolgokra, hanem mindegyikhez tartozik egy p_i valószínűség. Ekkor az információnyereséget úgy tudjuk kiszámolni, hogy minden egyes dolognak külön számoljuk ki az információértékét: azaz vesszük az adott dolog gyakoriságának logaritmusát, és beszorozzuk azzal a valószínűséggel, amivel őrá gondolunk. Ezeket összegezve kapjuk meg az átlagos információmennyiséget.

Például dobjunk két pénzdarabbal, és legyen x jelentése az, hogy az érmék közül hány mutat fejet, így x értéke lehet 0,1,2, rendre ¼, ½, ¼ valószínűséggel. Ekkor kódoljuk a következőképpen:

Ha egy dobásnál egy fejet dobunk, akkor ezt az eredményt az 1-es számjegy leírásával kódoljuk,
ha mindkét érme írást mutat, akkor 00 jelsorozattal kódoljuk
ha mindkét érme fejet mutat, akkor pedig a 01 jelsorozattal.
Így minden dobást egy 1 vagy 2 számjeggyel kódoljuk annak fényében, hogy x 1-et vagy pedig más értéket vesz fel. Ugyanakkor ha x=1 (azaz pontosan egy fejet dobtunk), annak valószínűsége ½ hiszen vagy elsőre vagy másodikra dobtunk fejet, a másik két lehetőség viszont csak egyféleképp jöhet ki, tehát valószínűségük ¼, ¼. Tehát a kódszó hosszának valószínűsége ½ eséllyel 1 és ½ eséllyel 2, tehát a hossz várható értéke: 1,5, átlagosan másfél hosszú kódszóra van szükségünk: így értelmet nyert a nem egész információmennyiség. Ennek az átlagos információmennyiségnek a képletét Shannon és Wiener is teljesen függetlenül felfedezte. Ami érdekes, hogy Boltzmann fél évszázaddal megelőzte mindkettejüket, méghozzá úgy, hogy egész más témában kutatott: statisztikus mechanikai vizsgálatai során az entrópiára adta meg ily módon a képletet. Az ő formulája azt mutatja meg, hogyha egy nagyszámú molekulából álló gázban az egyes molekulák lehetséges állapotát jelöljók p_i-vel (ahogy előbb az egyes dolgok gondolására való valószínűséget), akkor a Shanonn-féle képlet konstansszorosát kapjuk. Ugyanakkor tudjuk, hogy a fizikai rendszer entrópiája a rendszer rendezetlenségének mértékét méri. Ezt úgy is lehet értelmezni, hogy „a rendszer entrópiája a molekulái állapotára vonatkozó bizonytalanság mértékszáma.”

Így már érthetővé válik, miért kapta Shannon és Wiener ugyanazt az értéket, mint Boltzmann. Ha belegondolunk a bizonytalanság nem más, mint információ-hiány, vagyis negatív információ, azaz az információ a bizonytalanság csökkenésével egyezik meg. Az átlagos információ-mennyiség akkor lesz a legnagyobb, hogyha a valószínűségek egyformák (azaz, ha minden dolgokra ugyanolyan valószínűséggel gondolok), hiszen ekkor nyerhetek egy kérdésből a lehető legtöbb információt. Vagy visszatérve a korábbi példára „ha megkérdezem egy lánytól, hogy akar-e a felségem lenni, a válasz információtartalma attól függ, hogy mekkora a valószínűsége, hogy igennel fog válaszolni. Ha e valószínűség igen kicsi, vagy ha közel van egyhez [azaz igen nagy], akkor a válasz kevés információt fog tartalmazni, hiszen szinte biztosan azt a választ kapom, amire számítok.” A legnagyobb a bizonytalanságom, amikor egyenlő eséllyel mondhat igent és nemet is: és az ilyenkor kapott válasz csökkenti legnagyobb mértékben a bizonytalanságomat, ezért ilyenkor a legnagyobb az információmennyiség.

A fentiekkel még messze nem mondott el mindent Rényi Alfréd arról, amit érdemes tudni az információelméletről. Kétségtelen, hogy igényel némi gondolkozást ezeknek a fogalmaknak a tisztázása, ugyanakkor az egyik legnagyobb információtartalmú írás, amihez hozzájuthat egy matematikában nem feltétlenül jártas, de érdeklődő olvasó. A továbbiakban még olvashatunk arról, hogy mennyire redundáns egy nyelv, mik a legjobb kódolások, vagy mi az az információelméleti távolság – mindezt továbbra is élvezetes stílusban tárolva. Csak ajánlani tudom a valaha élt egyik legjobb matematikusunk írását, aki szívét-lelkét beletette, hogy közvetítse a matematika alkalmazhatóságát a laikusok felé is.

Az e havi válogatást @HAri karcával kezdeném, aki Simone Elkeles: Perfect Chemistry – Tökéletes kémia című könyvét elemezte zseniálisan és – nagyon viccesen – borító alapján.

Maradva @HArinál két Mérő idézet következik, az első az intelligenciáról:

egy a matematikusokról (mert minden szentnek maga felé hajlik a keze…)

Egy karc Einsteinről @balageshtől:

@Pável kitűnő értékelése Csányi Vilmos új könyvéről, az Ironikus etológiáról:

És ugyanehhez a könyvhöz egy karc @n-től:

Végezetül még egy karc @ÁrnyékVirágtól Jared Diamond Háborúk, járványok, technikák c. könyvéhez kapcsolódóan: