Wat is informatie? (slot) - hoe erg telt een fjord mee?

Vorige keer ben ik geëindigd met de vraag "Als je een nieuw woord invoert, wat het aantal mogelijkheden voor het teken '?' in een woord "f?...' met ééntje vergroot (bijvoorbeeld 'fjord' naast de Nederlandse mogelijkheden fiets, flits, falen), wat is dan de toename in informatie?"

Om die vraag te beantwoorden moeten we nog één ding weten. Hoe bereken je de informatie uit willekeurige kansen?

We weten wel dat als er twee keuzes zijn die even waarschijnlijk zijn er één bit informatie is.
Als er VIER keuzes zijn die even waarschijnlijk zijn is de informatie 2 bits
Bij acht keuzes drie bits.

Een slimme wiskundige heeft toen gezegd: laten we het als volgt doen.
We nemen voor elke mogelijkheid de kans op die mogelijkheid en vermenigvuldigen die met een speciale factor die van die kans afhangt. Het totaal tellen we op om de informatie te krijgen.

Dus: als je een munt opgooit is de informatie van de uitslag
kans(kop)*functie(kans_kop)+kans(munt)*functie(kans_munt) oftewel: 0.5*functie(0.5)+0.5*functie(0.5) = 1.0 * functie (0.5) = functie 0.5
Functie (0.5) is dus 1 (1 munt, 1 bit)
Als je TWEE munten opgooit krijg je iets dergelijks:
kans(kopkop)*functie(kans_kopkop)+ kans(kopmunt)*functie(kans_kopmunt)+ kans(muntkop)*functie(kans_muntkop)+ kans(muntmunt)*functie(kans_muntmunt) = 0,25*functie(0,25)+ 0,25*functie(0,25)+ 0,25*functie(0,25)+ 0,25*functie(0,25)+ 0,25*functie(0,25)+ 0,25*functie(0,25)+ 0,25*functie(0,25)+ 0,25*functie(0,25) = 1,00*functie(0,25).

Functie(0,25) is dus 2

We kunnen nu een tabel maken
Functie (0,5) = 1
Functie(0,25) = 2
Functie(0,125) = 3
Functie(0,0625) = 4
Functie( 0,03125) = 5

Herken je de functie al?
Het is gemakkelijker als je het in breuken opschrijft
Functie (1/2) = 1
Functie (1/4) = 2
Functie (1/8) = 3
Functie (1/16) = 4
Functie (1/32) = 5

Dat zijn allemaal machten van twee! (ook wel logisch als je het over munten hebt met halve kans op kop en munt). 2^1 = 2, 2^2 = 4, 2^3=8, 2^4=16, 2^5=32. Oftewel: functie(1/x) is de macht waartoe je 2 moet verheffen om x te krijgen, oftewel functie (x) = de macht waartoe je 1/2 moet verheffen om x te krijgen, oftewel in wiskundetermen: de functie die we zoeken is 0.5log(x) oftewel -2log(x). Op je rekenmachine kan je dat bijvoorbeeld als volgt uitrekenen. Je neemt bijvoorbeeld 1/8 (1/8=0,125), neemt daar het logaritme van (-0,9030899), deelt dat door het logaritme van 2 (0,30103) en neemt van het getal dat je dan krijgt (-3) de positieve variant (-3 -> 3). We hebben dus nu inderdaad een functie die 1/8 omzet in het getal dat we willen krijgen, 3!

Het prachtige aan deze algemene formule is dat we hem ook kunnen toepassen als kansen ongelijk zijn aan machten van een half. Bijvoorbeeld een dobbelsteen heeft zes mogelijkheden. Je zou al denken dat de informatie van een dobbelsteen die op een waarde rolt ergens tussen de 2 (4) en 3 (8 mogelijkheden) is. En inderdaad: -2log1/6 = 2,585.

Nu kan je je misschien afvragen of dat zinvol is: je moet toch een dobbelsteenuitslag in 3 bits coderen? En je kunt dus geen 0,415 bit besparen? Wel, bij één uitslag niet. Maar wat als er duizend uitslagen achter elkaar staan? Zie de volgende tabel eens voor je:

1 worp = 6 / 1 bit = 2
2 worpen = 36 / 2 bits = 4
3 worpen = 216 / 3 bits =8
4 worpen = 1296 / 4 bits = 16
(... 5 bits = 32, 6 bits = 64, 7 bits = 128, 8 bits = 256, 9 bits = 512, 10 bits = 1024)

Dat betekent dat 1 worp inderdaad 3 bits nodig heeft. En 2 worpen hebben 6 bits nodig. Maar 3 worpen hebben slechts 8 bits nodig in plaats van 9, wat betekent dat als je een code maakt waarbij 1-1-1 het getal 0 krijgt (binair 00000000), 1-1-2 het getal 1 (binair 00000001) enzovoorts totdat 6-6-6 gecodeerd wordt met 215 (binair 11010111) per worp ineens niet meer 3 bits nodig zijn, maar slechts 8/3=2,667 bits. Als je de dobbelsteenvolgordes nog langer maakt kun je steeds dichter bij het theoretisch minimum van 2,585 komen.

Het mooie is dat deze kansberekening niet alleen werkt voor gelijke kansen, zoals 1/6, maar ook voor ongelijke kansen. Bijvoorbeeld als je A, B en C wilt coderen, waarbij A in de helft van de gevallen voorkomt, en B en C elk maar een kwart, dan zou je intuitie misschien zeggen dat je meer dan 1 bit nodig hebt, maar minder dan 2. En dat klopt ook: 0,5*-2log0,5 + 0,25*-2log0,25+ 0,25*-2log0,25 = 0,5*1+0,25*2+0,25*2 = 1,5. En dat is ook wel logisch: je zou 'A' kunnen coderen met 0, B met '10' en C met '11', en de volgorde ABCA keurig kunnen omzetten in 010110 = 6 bits, voor deze vier letters is dat inderdaad anderhalve bit per letter.

Laten we nu dan eens kijken naar de fjord. Wat is de informatie van de tweede letter in 'f' woorden?

F in mijn Van Dale heeft ongeveer 23,30 pagina, met ongeveer 64 woorden op elke pagina, dat wil zeggen ongeveer 1500 woorden. Daarvan beginnen er ongeveer 213 met 'fa' 138 met 'fe' 304 met 'fi' 240 met 'fl', 272 met 'fo', 208 met 'fr' en ongeveer 100 met 'fu' en de resterende 25 met 'fy'. De entropie is dus (213/1500)*-2log(213/1500)+...+(25/1500)*-2log(25/1500) = 2,81
Dat is niet helemaal onverwacht, er zijn 8 mogelijkheden, dus er is maximaal 3 bits aan informatie. Zeker omdat alle mogelijkheden ongeveer even vaak voorkomen, komen we dicht bij het theoretische maximum van 3 (als 'fa' in 1430 gevallen voorkwam, en de rest elk maar in 10 gevallen zou er inderdaad minder informatie in zitten). Voegen we nu 1 fjord toe, dus 1 'fj'. De entropie wordt dan (213/1501)*-2log(213/1501)+...+(1/1501)*-2log(1/1501) = 2,81 (wel, eigenlijk gaat de informatie van 2,8071 naar 2,8132, neemt dus iets toe). Zoals je misschien al verwachtte: een enkel fjord zet weinig zoden aan de dijk in een zee van 'fa's en 'fi's.

Met deze theorie, die ook de informatietheorie wordt genoemd, kun je berekenen hoeveel informatie er in een tekst zit, dus ook in het woordje 'maar' (al zal ik dat als oefening overlaten aan de fanatieke lezer). En nu begrijp je ook waarom zip-programmas tekstbestanden zoveel kleiner kunnen maken - ze halen gewoon de overbodige informatie eruit. Een ideaal zip-programma zou dus de theoretische limiet kunnen halen van hoeveel informatie er echt in een stuk tekst zit. En dat is vaak 70% of meer% minder dan de schrijver erin gestopt heeft aan letters!

Informatietheorie heeft overigens nog meer toepassingen dan alleen zip-programma's, mijn collega Kai Ye heeft bijvoorbeeld informatietheorie gebruikt om een programma te bedenken dat eiwitten analyseert (zie hier). Maar voor dit blog is een blok van 4 afleveringen over informatietheorie voorlopig genoeg. Volgende keer wil ik het hebben over een ander leuk onderwerp: examens!