Entropi forklaret

I 1948 stillede en ingeniør hos Bell Labs, Claude Shannon, et spørgsmål, som ingen havde gjort præcist: hvor meget information indeholder en besked? Hans svar var et tal, målt i bit, som ikke afhænger af, hvad en besked betyder, men af hvor overraskende den er. Det tal, entropien, sætter grænserne for alle komprimeringsprogrammer, alle netværksforbindelser og alle lagringsmedier, og det forklarer, hvorfor nogle tekster skrumper til en brøkdel af deres størrelse, mens andre slet ikke kan presses sammen.

Søjler med bogstavsandsynligheder, der falmer fra hyppige til sjældne, med entropikurven, der falder, jo mere kontekst der er kendt
Søjler med bogstavsandsynligheder, der falmer fra hyppige til sjældne, med entropikurven, der falder, jo mere kontekst der er kendt

Information er overraskelse

Shannons indsigt var at måle information efter, hvor uventet en besked er, ikke efter hvad den betyder. Hvis du allerede kender svaret, fortæller det dig intet at høre det; hvis det kunne have været én af tusind ting, fortæller det dig meget. En besked, der udpeger én af to lige sandsynlige muligheder, bærer én bit. Én af fire kræver to bit, én af otte tre bit, og generelt kræver én af N lige sandsynlige muligheder log₂ N bit. Et symbol, der forekommer med sandsynligheden p, bærer derfor −log₂ p bit: jo sjældnere det er, desto mere fortæller det dig.

Shannons formel

Entropi er den gennemsnitlige information pr. symbol: H = −Σ p log₂ p, summeret over hvert symbol med dets sandsynlighed p. For en retfærdig mønt er H 1 bit. For en mønt, der lander på krone 90 % af gangene, er den kun 0,47 bit, fordi udfaldet sjældent er en overraskelse. Entropien er størst, når alle symboler er lige sandsynlige, log₂ n bit for n symboler, og nul, når ét symbol er sikkert. Shannon valgte navnet efter råd fra John von Neumann, fordi den samme formel optræder i fysikken, hvor entropi måler uorden.

Claude Shannon, der i 1948 hos Bell Labs gjorde det præcist, hvor megen information en meddelelse indeholder, og målte den i bits.
Claude Shannon, der i 1948 hos Bell Labs gjorde det præcist, hvor megen information en meddelelse indeholder, og målte den i bits.

Komprimeringens grænse

Shannons kildekodningssætning siger, at ingen tabsfri kode i gennemsnit kan bruge færre bit pr. symbol end kildens entropi, og at koder kan komme den så tæt på, som man vil. Huffman-kodning, opfundet af David Huffman i 1952, mens han var studerende, giver hyppige symboler korte koder og sjældne lange koder og kommer inden for én bit pr. symbol af entropien; aritmetisk kodning kommer endnu tættere på. Entropi er altså ikke bare en beskrivelse, men en hård grænse: en fil af tilfældige byte med 8 bit entropi pr. byte kan slet ikke komprimeres.

David Huffman, fotograferet som professor ved UC Santa Cruz. Som kandidatstuderende ved MIT fandt han i 1951 sin optimale kode i en semesteropgave til Robert Fanos kursus.
David Huffman, fotograferet som professor ved UC Santa Cruz. Som kandidatstuderende ved MIT fandt han i 1951 sin optimale kode i en semesteropgave til Robert Fanos kursus.

Kontekst og redundans

Bogstaverne i en tekst er ikke uafhængige. På engelsk kommer U efter Q, et stort bogstav efter et punktum, og et engelsk ord, der begynder med INFORMA, fortsætter næsten med sikkerhed med TION. Tager man de foregående symboler med i betragtning, får man den betingede entropi, som er lavere end entropien af symbolerne talt ét ad gangen. Forskellen er redundans: den del af beskeden, der kunne have været forudsagt. Komprimeringsprogrammer som ZIP, der bruger deflate-metoden, finder gentagne tegnfølger og erstatter dem med korte henvisninger, og moderne komprimeringsprogrammer forudsiger hvert symbol ud fra dets kontekst.

Hvor meget information er der i engelsk?

Talt bogstav for bogstav, med engelsks frekvenser, bærer et bogstav omkring 4,1 bit, mod 4,7 for tilfældigt valgte bogstaver. I 1951 gik Shannon videre: han viste folk begyndelsen af en tekst, bad dem gætte det næste bogstav og talte, hvor mange gæt de skulle bruge. Ud fra deres svar anslog han, at engelsk kun bærer omkring 0,6 til 1,3 bit pr. bogstav. Med andre ord er omkring tre fjerdedele af skrevet engelsk redundans, og derfor kan en tekst, hvor der mangler bogstaver, som regel stadig læses.

Tilfældighed og adgangskoder

Entropi måler også uforudsigelighed, og det er det, sikkerhed afhænger af. En nøgle eller adgangskode, der vælges ligeligt blandt N muligheder, har log₂ N bit entropi, og en angriber skal i gennemsnit prøve omkring halvdelen af dem. En tilfældig adgangskode på 12 bogstaver fra de 26 små bogstaver har omkring 56 bit; et almindeligt ord har langt færre, uanset hvor langt det er. Tilfældighedsgeneratorer testes ved at kontrollere, at deres output har den fulde entropi af en tilfældig kilde, og styresystemer indsamler entropi fra støj i tidsmålinger for at starte dem.

Hvor entropi dukker op

Entropi afgør, hvor mange bit et telefonopkald, et foto eller en videostream kræver, og hvor tæt et modem eller en wi-fi-forbindelse kan komme på sin kanals kapacitet. Biologer bruger den til at måle informationen i DNA, hvor fire baser højst kan bære 2 bit hver, og et økosystems diversitet. I maskinlæring vælger beslutningstræer det spørgsmål, der sænker entropien mest, og de fleste neurale netværk trænes med krydsentropi som tabsfunktion. Lingvister sammenligner sprog ud fra deres entropi pr. tegn og pr. ord.

Udforsk det

Åbn entropiberegneren for at måle enhver tekst efter tegn, ord eller byte. Sammenlign et afsnit med tilfældige bogstaver, bit, cifre og DNA, se overraskelsen ved hvert symbol, hvor meget information teksten rummer over for dens gemte størrelse, og hvordan antallet af bit pr. symbol falder, jo mere kontekst der er kendt, ved siden af hvad ZIP faktisk opnår.

Ofte stillede spørgsmål

Hvorfor måles entropi i bit?

Fordi Shannon brugte logaritmer med grundtal 2, så ét ja-nej-valg mellem lige muligheder tæller som én enhed. Med den naturlige logaritme er enheden nat, omkring 1,44 bit, og med grundtal 10 hartley, omkring 3,32 bit; fysikere og nogle statistikere bruger dem.

Kan en tekst have mere entropi end log₂ af sit alfabet?

Nej. Med n forskellige symboler er entropien højst log₂ n bit pr. symbol, og det nås kun, når de alle er lige hyppige. Enhver skævhed og enhver forudsigelighed ud fra konteksten sænker den.

Er entropi i informationsteori det samme som i fysik?

Formlerne har samme form: Boltzmann og Gibbs skrev den fysiske entropi som en sum over sandsynlighederne for et systems mikroskopiske tilstande. Betydningen er beslægtet, da begge måler, hvor meget man ikke ved, og fysikere har siden vist, at sletning af én bit information må frigive en lille mængde varme.

Hvorfor hjælper det ikke at komprimere en komprimeret fil?

Et godt komprimeringsprogram fjerner det meste af redundansen, så dets output er næsten tilfældigt, med næsten 8 bit entropi pr. byte. Der er intet tilbage at fjerne, og en ny komprimering gør som regel filen lidt større på grund af programmets eget overhead.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Åbn entropiberegneren