Compressie is voorspelling

In dit artikel loop ik door de basisprincipes van compressie om de diepe relatie met taalmodellering te begrijpen.

Hoe compressie werkt

Er zijn veel manieren om data te verkleinen. Neem bijvoorbeeld minificatie: dit werkt door code te strippen tot het absolute minimum dat machines nodig hebben om het te analyseren. Mensvriendelijke variabelen worden gereduceerd tot enkele letters; witruimte en commentaren worden verwijderd.

Voorbeeld van minificatie:

Originele bron (156 tekens):

// Sum every number in the list
function sumNumbers(numbers) {
  let total = 0;
  for (const number of numbers) {
    total += number;
  }
  return total;
}

Geminificeerd (62 tekens — 60 procent kleiner): function sumNumbers(n){let t=0;for(const r of n){t+=r}return t}

Het resulterende bestand is aanzienlijk kleiner, maar je zult minificatie bijna nooit horen noemen in het veld van datacompressie. Waarom is dat? Minificatie is vrij eenvoudig: het gooit simpelweg alle syntax weg die niet vereist is door machines. Maar "echte" compressie vertrouwt op redundantie om data samen te persen.

Stel je de string AAAAAAAAABBBBCCDAAADDDDDDDDD voor (negen A's, vier B's, twee C's, één D, drie A's en negen D's). Hier is veel redundantie aanwezig. We kunnen dit coderen als een kortere string door de totale reeks van elk teken op volgorde te noteren:

• Originele string: 28 tekens (224 bits bij standaard 8-bit ASCII-codering).
• Gecomprimeerde string (A9B4C2D1A3D9): 12 tekens (96 bits), wat 57 procent kleiner is.

Deze techniek wordt run-length encoding genoemd, maar we kunnen veel beter presteren. Actuele compressors zoals gzip en Brotli vertrouwen op verschillende methoden om data te verkleinen.

De anatomie van een compressor

Moderne compressietools bestaan grofweg uit drie "organen": transforms (transformaties), modellen en entropiecodeerders. Hoewel de lijnen soms vervagen, worden ze zelden in isolatie gebruikt.

Transforms

Transforms zijn voorbewerkingsstappen die onze data gemakkelijker comprimeerbaar maken. Run-length encoding is een voorbeeld van een transform. Het is belangrijk om te weten dat transforms de data niet altijd direct verkleinen; soms worden ze gebruikt om juist meer redundantie te creëren, waardoor we later meer kunnen comprimeren.

Modellen

Modellen beschrijven de vorm van onze data op basis van de frequenties van elk symbool (ongeacht of dit letters, cijfers, tokens of binaire code zijn). Je kunt een model zien als een tabel die elk symbool koppelt aan een waarschijnlijkheid.

Voorbeeld gebaseerd op onze eerdere string: String: AAAAAAAAABBBBCCDAAADDDDDDDDD (28 tekens) Telling per symbool: 12 A's, 10 D's, 4 B's, 2 C's.

Symbool	Waarschijnlijkheid
A	0.429
D	0.357
B	0.143
C	0.071

Entropiecodeerders

De entropiecodeerder is bijna altijd de laatste stap in een compressie-algoritme en produceert het uiteindelijke gecomprimeerde artefact: een ruwe bitstream (een pure reeks bits zonder de structuur van een bestandsformaat).

Het proces werkt als volgt: het datamodel geeft de entropiecodeerder een set waarschijnlijkheden, en de codeerder zet deze zo efficiënt mogelijk om in een bitstream.

Data samenpersen met waarschijnlijkheden

Elke entropiecodeerder werkt anders. Om het simpel te houden, focussen we op arithmetic coding (rekenkundige codering), omdat dit het beste illustreert hoe betere waarschijnlijkheden leiden tot betere compressie.

Arithmetic coding

Bij arithmetic coding kan een volledige dataset worden gerepresenteerd door één enkel getal. Stel dat we de string ABABAAC willen comprimeren. Eerst bepalen we de waarschijnlijkheden:

• String: 4 A's, 2 B's, 1 C (totaal 7 tekens).
• Waarschijnlijkheden: A = 0.571, B = 0.286, C = 0.143.

We kunnen deze waarschijnlijkheden weergeven op een bereik van 0 tot 1. De ruimte wordt verdeeld in secties:

• A beslaat 0 tot 0.571
• B beslaat 0.571 tot 0.857
• C beslaat 0.857 tot 1

Voor elk symbool in onze string verkleinen we het bereik om binnen de sectie van dat specifieke symbool te passen. We blijven dit nieuwe, kleinere bereik vervolgens weer verdelen met dezelfde waarschijnlijkheden. Wanneer alle symbolen zijn verwerkt, houden we een zeer klein bereik over (bijvoorbeeld [0.38730, 0.38855)).

Elk getal binnen dit bereik kan onze data representeren. Ideaal gezien kiezen we het getal dat de minste bits vereist. In dit geval is dat 0.3876953125. Terwijl de originele string in 8-bit ASCII 56 bits nodig heeft, heeft dit uiteindelijke getal (als binaire fractie) er slechts 10 nodig.

Decompressie van arithmetic codes

Om te decoderen, heeft de decompressor het "magische getal" en dezelfde waarschijnlijkheden nodig om het startbereik [0, 1) te herbouwen. De decompressor kijkt in welke sectie het getal valt, noteert dat symbool, verkleint het bereik tot die sectie en herhaalt het proces totdat de volledige string is hersteld.

Hoe waarschijnlijkheden compressie beïnvloeden

Wat gebeurt er als symbolen vaker herhaald worden? Neem een nieuwe string waarbij de letter A domineert: AAAAAAAAAABC.

• Telling: 10 A's, 1 B, 1 C (totaal 12 tekens).
• Waarschijnlijkheden: A = 0.833, B = 0.083, C = 0.083.

Vergelijking van de resultaten bij arithmetic coding:

Kenmerk	String 1 (ABABAAC)	String 2 (AAAAAAAAAABC)
Lengte	7 symbolen	12 symbolen
Raw ASCII	56 bits	96 bits
Gecomprimeerd formaat	~10 bits	~10 bits
Gem. bits per symbool	1.38 bits	0.82 bits

Wanneer data meer "scheef" is (hogere waarschijnlijkheden voor bepaalde symbolen), is de compressieratio beter. Dit gemiddelde aantal bits per symbool wordt entropie genoemd en vormt de basis van compressie. Dit is Shannon-entropie uit de informatietheorie, waarvan de formule bijna identiek is aan de Gibbs-formule voor entropie in de thermodynamica.

Entropie

Stel je de volgende zin voor: "Gisteren zag ik een dier toen ik door het centrum liep. Het was een _."

Hoeveel gokken zou je gemiddeld nodig hebben om het gat in te vullen? Als het antwoord "vogel" is (zeer waarschijnlijk), heb je het misschien meteen goed. Is het "beer", dan duurt het langer.

Stel de volgende waarschijnlijkheden vast:

• Vogel: 1/2
• Eekhoorn: 1/4
• Kat: 1/8
• Vos: 1/16
• Beer: 1/16

Als we een ja/nee-beslissingsboom maken, zien we dat vaker voorkomende dieren minder "gokken" (bits) nodig hebben. Dit is in essentie wat Huffman coding doet: het wijst kortere codewoorden toe aan symbolen met een hogere waarschijnlijkheid.

De absolute minimale hoeveelheid bits die nodig is om een symbool te representeren, kan worden berekend met de formule: aantal bits = -log2(waarschijnlijkheid)

Als we het gemiddelde van -log2(waarschijnlijkheid) voor alle symbolen nemen, vinden we de entropie. Dit is de "vloer": de kleinste hoeveelheid bits per symbool die haalbaar is zonder data te verliezen (lossless compression). (Bij lossy compression, zoals JPEG of MP3, kan men verder gaan door details weg te gooien).

Context is cruciaal

Tot nu toe gebruikten we simpele modellen die alleen keken naar de totale frequentie van een symbool. Maar context beïnvloedt de waarschijnlijkheid enorm. In de Engelse taal heeft de letter 'U' een algemene waarschijnlijkheid van ~0.028. Maar als er direct een 'Q' aan voorafgaat, schiet die waarschijnlijkheid omhoog naar ~0.999.

Dit verschil in bits is enorm:

• U (algemeen): -log2(0.028) $\approx$ 5.158 bits
• U (na Q): -log2(0.999) $\approx$ 0.001 bits

Een model dat één symbool context meeneemt, heet een order-1 model. Dit kan worden uitgebreid naar order-2, order-3, enzovoort.

Voorbeeld: "TO BE OR NOT TO BE" Bij het gebruik van arithmetic coding op deze zin, ziet men een enorm verschil tussen een model zonder context en een order-1 model:

Metriek	Geen context	Order-1 model
Lengte	18 symbolen	18 symbolen
Raw ASCII	144 bits	144 bits
Gecomprimeerd formaat	~47 bits	~21 bits
Gem. bits per symbool	2.59 bits	1.16 bits

Context zorgt voor sterkere waarschijnlijkheden, wat betekent dat we beter kunnen voorspellen welk symbool volgt.

Taalmodellering en compressie

De overlap tussen LLM's en compressie is fundamenteel; Google DeepMind stelde in 2023 zelfs dat taalmodellering en compressie twee manieren zijn om naar hetzelfde ding te kijken.

LLM's worden vaak omschreven als "geavanceerde autocomplete". Wanneer je een prompt invoert, gebruikt het model dit als context om waarschijnlijkheden voor het volgende token (een woord of deel van een woord) te genereren.

In compressie gebruiken we LLM's op dezelfde manier, maar we kiezen niet zelf het volgende woord—we weten immers al wat het volgende woord is in de tekst die we willen comprimeren. Het model voorspelt de waarschijnlijkheden, en de werkelijke kosten in bits worden bepaald door de waarschijnlijkheid die het model aan het werkelijk volgende symbool heeft toegekend.

• Goed getraind model: Geeft het juiste volgende woord een hoge waarschijnlijkheid → weinig bits nodig → sterke compressie.
• Slecht getraind model: Geeft het juiste volgende woord een lage waarschijnlijkheid → veel bits nodig → zwakke compressie.

Ter illustratie: bij het comprimeren van een beroemd citaat van Charles Dickens presteerde een order-1 model met 434 bits, terwijl GPT-2 dit kon reduceren tot slechts 176 bits.

Compressie in de praktijk

Als LLM's zo goed zijn in compressie, waarom gebruiken we ze dan niet overal? Het antwoord ligt bij de resourcebeperkingen.

Bij HTTP-responses gebruikt een browser bijvoorbeeld gzip of Brotli. De overhead is minimaal omdat het model klein en ingebouwd is. Als we hiervoor een LLM zouden gebruiken, zouden zowel de server als de browser een kopie van het model (meerdere gigabytes) moeten hebben. Het compute-vermogen dat nodig is voor het comprimeren en decomprimeren zou de laadtijden van webpagina's onbruikbaar maken.

Voor kleine taken zoals HTTP-responses zijn LLM's simpelweg overkill. De winst in bits weegt niet op tegen de kosten in rekenkracht en geheugen.

Twee kanten van dezelfde medaille

Het comprimeren van data tot aan de entropie is in principe een opgelost probleem; arithmetic coding komt zeer dicht bij de theoretische limiet. De open vraag is hoe klein we die entropie kunnen maken door betere voorspellers (modellen) te bouwen.

LLM's zijn fantastisch in het verlagen van dit getal. Sterker nog: LLM's worden getraind om precies dit aantal bits-per-symbool te minimaliseren (bij LLM's heet dit cross-entropy).

Uiteindelijk zijn zowel LLM's als compressie-algoritmen voorspellers. Ze zijn twee uitingen van dezelfde onderliggende wiskunde. Compressie is voorspelling, en LLM's zijn compressors.