Huis van verrassingen – A woven web of guesses

Entropy House is de naam die Claude en Betty Shannon gaven aan het huis in Winchester, Massachusetts, waarin ze samen 30 jaar gewoond hebben. Op een foto staat Shannon in een van de kamers van het huis, vol uitvindingen en onderzoeksgadgets, trots met een arm vol kegels. Naast zijn wetenschappelijke verdiensten was hij ook een begaafd jongleur. De enige foto van het huis die ik kon vinden staat in het boek A Mind at Play uit 2017. In deze biografie van Shannon kun je ook lezen wat er in het huis was, van een formele ontvangstkamer met al zijn prijzen en onderscheidingen tot een forse werkplaats waar hij al die speelse onderzoeksvoorwerpen en – installaties maakte.

Entropy House is letterlijk een huis van verrassingen. Het huis en alle schatten komen uitgebreid in beeld in de documentaire over het leven van Shannon, gemaakt ter gelegenheid van Shannons’ 100e geboortedag in 2016. In deze film, The Bit Player, worden onder meer Claude en Betty Shannon geïnterviewd. De interviews zijn nagespeeld maar wel gebaseerd op echte interviews.

In zo’n interview in de film gooit Shannon op enig moment een muntje naar de interviewster en roept al “kop” voor ze het gevangen heeft. Het blijkt te kloppen ook, als zij vertelt welke kant boven is. Shannon heeft haar bericht echter niet nodig, hij weet dat het een valse munt is met aan weerszijden kop. Er is voor hem geen onzekerheid, geen verrassing in het bericht, dus geen informatie. De entropie is nul. Anders zou het zijn met een eerlijke munt, kop of munt, 0 of 1. Je hebt dan 1 bit nodig om de informatie over wat boven ligt door te geven. Als je 100 keer gooit heb je 100 bits nodig om alle worpen door te geven, omdat de uitkomsten onafhankelijk zijn. De entropie is maximaal.
Het korte fragment bevat veel kernelementen uit de informatietheorie.

Informatie: een niet-intuïtief concept

In de bundel uit 1949 met het oorspronkelijke artikel van Shannon staat ook een artikel van Weaver met de dienstbare titel: Recent Contributions to the Mathematical Theory of Communication. Weaver geeft daarin welkome toelichtingen en overwegingen bij het artikel van Shannon, die zelf niet scheutig is met uitleg en context.

NB Een aantal van de overwegingen heb ik uitgewerkt in het bericht over Shannon en Weaver, voor de leesbaarheid herhaal ik er hier een paar.

Informatie

Weaver benadrukt dat het woord informatie hier in een speciale context wordt gebruikt en niet verward moet worden met het normale gebruik van het woord. Preciezer: informatie moet niet verward worden met betekenis. Eerder hadden Hartley, en ook Shannon zelf, al afscheid genomen van de psychologische factoren resp. de semantische aspecten.

Informatie is een eigenschap van de bron. Die betreft de probabilistische aard van de volledige informatiebron, en richt zich niet op de individuele berichten. Het is een engineering concept want een communicatiesysteem moet alle berichten kunnen hanteren die een bron kan produceren, de ‘whole ensemble of messages‘…

Niet wat je overbrengt, maar wat je zou kunnen overbrengen – daar draait het om. Informatie is een maat voor keuzevrijheid als je een bericht (of symbool in een bericht) moet kiezen en evenredig aan de logaritme van het aantal mogelijke keuzes. Dat is de oorspronkelijke opzet van Hartley, Shannon volgt die. Met 2 als grondtal voor de logaritme leidt dat tot de bit als eenheid van informatie, bij twee mogelijke keuzes (bijv. 0 of 1) geldt: $log_22=1$ bit.

Stochastisch model

Het kiezen van symbolen uit de beschikbare verzameling om een bericht te maken, is vanuit het communicatiesysteem gezien een stochastisch proces. Elk te kiezen symbool heeft een kans om gekozen te worden voor het bericht, maar de verschillende kansen hoeven niet gelijk of onafhankelijk te zijn en zijn dat in werkelijkheid ook meestal niet. In een taal komen de symbolen (letters en cijfers) in een voor elk symbool verschillende frequentie voor, daardoor alleen al hebben niet alle symbolen evenveel kans om gekozen te worden. Belangrijker is dat een bericht in opbouw al gekozen symbolen bevat, er is al een sequentie -een stukje tekst als het ware- , waar de kans voor de eerstvolgende keuze van afhankelijk is. In het Engels bijvoorbeeld komt er na de letter j eigenlijk nooit een b, c, d, f, g, …. Bij woorden gelden dezelfde overwegingen: de kans dat er na het woordje ‘the’ een werkwoord komt is zeer klein.
Zulke stochastische processen worden Markov processen genoemd, of Markov ketens.

Entropie

Shannon heeft in zijn artikel drie eisen geformuleerd waaraan een maat $H$ voor keuzevrijheid, of onzekerheid, zou moeten voldoen, zie daar. Hij toont aan dat $H$ er dan als volgt uit moet zien:

$H=-K\sum_{i=1}^{n}p_ilogp_i$

NB Ik gebruik hier de ‘werkversie’ van de formule, en laat de fraaiere versie aan de T-shirts.

Shannon gebruikt de term entropie voor deze formule en Weaver zegt het hem na. Ik heb wel moeten nadenken over het waarom van deze woordkeuze en van het instrumentarium zelf, de formule met zijn componenten. Entropie was voor mij (te) nauw met thermodynamica verbonden. Eigenlijk geeft Shannon zelf de aanwijzing dat hij het begrip ‘leent’ uit de statistische mechanica, hij schrijft:

The form of $H$ will be recognized as that of entropy as defined in certain formulations of statistical mechanics where $p_i$ is
the probability of a system being in cell $i$ of its phase space. $H$ is then, for example, the $H$ in Boltzmann’s famous $H$ theorem.

Weaver voegt er aan toe:

… it is most significant that an entropy-like expression appears in the theory as a measure of information. Introduced by Clausius nearly one hundred years ago, closely associated with the name of Boltzmann, and given deep meaning by Gibbs in his classic work on statistical mechanics, entropy has become so basic and pervasive a concept …

Weaver noemt entropie in natuurwetenschappelijke context een instrument om de mate van toevalligheid, van ‘shuffledness‘, te bepalen.

Ik moet zeggen dat ik de genoemde ‘entropy-like expressions‘ niet zomaar uit mijn mouw schud, maar in Wikipedia kun je alles vinden. Zoals de de entropieformule van Boltzmann: $S=k_Blog W$ .
Hier is $k_B$ de constante van Boltzmann en $W$ het aantal (micro)toestanden van een natuurkundig systeem waarin de interne vrijheidsgraden (bijv. voor positie en snelheid van een deeltje) vastliggen. Verandering van zo’n vrijheidsgraad leidt tot een andere microtoestand in het systeem.

NB De tegenhanger van microtoestand, niet verbazend macrotoestand genoemd, hangt alleen af van macroscopische variabelen als druk, temperatuur, volume e.d. Elke macrotoestand correspondeert met zeer veel microtoestanden die -in statistische verdeling- de macrovariabelen bepalen.

De entropieformule van Gibbs wordt op veel manieren geformuleerd, bijvoorbeeld: $S=- k_Bln P$ waar $P$ staat voor het aantal mogelijke microtoestanden. Het systeem hoeft bij Gibbs niet in een enkelvoudige, welbepaalde (macro)toestand te zijn, zoals bij Boltzmann.

De formules die gebruikt worden voor entropie, zowel door Boltzmann als Gibbs, zijn inderdaad nauw verwant aan de formule van Shannon. Voor mijn eigen begrip van de overeenkomsten helpt het dat ook de manier van denken zo sterk overeenkomt, het in- en uitzoomen van micro naar macro en terug, zeg maar.

Grip op de entropie formule

Om gevoel te krijgen voor de Shannon-entropie probeer ik een paar getalsmatige uitwerkingen, eerst een rechttoe rechtaan rekenvoorbeeld daarna een uitwerking van randsituaties.

Rekenvoorbeeld

Stel, een variabele $x$ , bijvoorbeeld in berichten, kan 3 waarden aannemen: a, b, c. In de helft van de gevallen waar een letter gekozen wordt heeft de variabele de waarde a, in een kwart van de gevallen waarde b en in een kwart van de gevallen waarde c.

Laten we eens zien hoe we in dit voorbeeld de entropie van $x$ kunnen berekenen met de formule van Shannon. We weten de kansverdeling:

$p(a)= \frac{1}{2}$
$p(b)= \frac{1}{4}$
$p(c)= \frac{1}{4}$

Samen zijn de kansen keurig gelijk aan 1.

Als we in de formule het min-teken weer naar binnen brengen, dan is $H(x)$ , de entropie van $x$ , gelijk aan de som van de logaritmen $p(x)log(\frac{1}{p(x)})$ , ofwel: $p(a)log(\frac{1}{p(a)})+p(b)log(\frac{1}{p(b)})+p(c)log(\frac{1}{p(c)})$

Bij grondtal 2 is $log(\frac{1}{\frac{1}{2}})=log(2)$ gelijk aan 1, $log(\frac{1}{\frac{1}{4}})=log(4)$ is gelijk aan 2.
Met de getallen uit het voorbeeld: $H(x)=\frac{1}{2}*1+\frac{1}{4}*2+\frac{1}{4}*2=1,5$ bits

Codering en compressie

Als een bericht vanaf de informatiebron via het kanaal naar een bestemming gaat wordt het in de transmitter gecodeerd naar een signaal zodat de receiver het weer kan decoderen tot een bericht voor de bestemming. Dat is de kern van het Shannon-model. Er is veel te zeggen over die codering, zeker in combinatie met ruis, en Shannon doet dat ook zijn artikel. Voor hier volsta ik met de constatering dat er verschillende coderingen van eenzelfde bericht mogelijk zijn (zolang de andere kant maar weet wat je gebruikt hebt), de ene manier gebruikt meer bits dan een andere. Een rechttoe rechtaan codering is over het algemeen niet de zuinigste manier, slimmere (zuinigere) manieren worden compressie genoemd.

In ons voorbeeld zou je met een zuinige codering de waarde a van de variabele $x$ met 1 bit kunnen vastleggen (“0”), de waarde b met 2 bits (“10”) en c ook met 2 bits (“11”).

Wat is op deze manier het aantal bits dat nodig is om de variabele $x$ vast te leggen? Voor waarde a heb je 1 bit nodig in de helft van de gevallen, voor b 2 bits in een kwart van de gevallen, net als voor c. Het gemiddelde over alle gevallen genomen is $0,5*1 + 0,25*2 + 0,25*2 = 1,5$ bits.

NB Scheidingscodes heb je op deze manier niet nodig: kom je een 0 tegen dan weet je dat het a is, kom je een 1 tegen dan moet je nog even verder lezen om te kijken of het b of c is. Dit is een voorbeeld van de Huffman codering, een bekende compressietechniek, maar dat zijpad zou ons echt te ver weg voeren.

Randgevallen

Om goed te begrijpen hoe een formule of wiskundige expressie in elkaar zit, kijk ik graag hoe die zich aan de randen van het domein gedraagt.

Stel, onze informatiebron produceert maar twee berichten met waarschijnlijkheid $p_1$ voor het eerste bericht en $p_2=1-p_1$ voor het tweede. Als je nu de numerieke waarde van $H$ berekent dan zie je dat $H$ de grootste waarde heeft als $p_1$ en $p_2$ gelijk zijn, $p_1=p_2=\frac{1}{2}$ . Dan geldt: $H=1$ .

In het algemeen geldt dat de entropiewaarde van een informatiebron maximaal is als alle kansen gelijk zijn, en elk bericht (of symbool om het te maken) vrij en onafhankelijk gekozen kan worden. Deze bron produceert de maximale hoeveelheid informatie (=entropie).

Nu het andere uiterste: stel dat $p_1$ erg hoog is, bijna 1 en $p_2$ bijgevolg erg laag, bijna 0, dan is ook de waarde van $H$ zeer laag. En mocht $p_2$ helemaal 0 zijn, en dus $p_1=1$ , dan geldt $H=0$ . Er is geen keuzevrijheid en dus geen informatie. Dit is de beschreven situatie met de valse munt met aan weerszijden kop.