In dit artikel onderzoekt Nathan Barry de theoretische gelijkwaardigheid tussen compressie en voorspelling. Hij stelt dat elk compressiealgoritme in feite een waarschijnlijkheidsmodel bevat: data die het model 'verwacht', kan namelijk efficiënter worden gecomprimeerd.
De auteur implementeerde dit concept in een tool genaamd gzipt. Deze tool gebruikt het DEFLATE-algoritme (via de Python zlib library) om tekst te genereren. Het proces werkt als volgt:
- Scoring: De kwaliteit van een kandidaat-vervolg wordt bepaald door de lengte van de gecomprimeerde data; hoe kleiner het resultaat, hoe waarschijnlijker de sequentie.
- Beam Search: Omdat gzip alleen gehele bytes teruggeeft (wat leidt tot kwantiseringsruis), gebruikt de tool een beam search. Hiermee kijkt het model trajecten vooruit om de meest comprimeerbare reeks bytes te vinden.
- Context: Er wordt gebruikgemaakt van een schuivend venster waarin een corpus en de recente output worden geplaatst om patronen te herkennen.
Het resultaat is een functioneel, zij het beperkt, taalmodel zonder neurale netwerken of training, puur gebaseerd op informatietheorie.
Kan gzip een taalmodel zijn?
Inleiding
Een tijdje geleden schreef ik over taalmodellering zonder neurale netwerken, waarbij ik Shakespeare genereerde met een onbegrensd n-grammodel: geen gewichten, geen training, alleen tellen. Toevalligerwijs stuitte ik op het artikel Language Modeling is Compression, waarin de equivalentie tussen compressie en voorspelling werd genoemd:
Elk voorspellingsmodel is inherent een compressor, en alle compressiealgoritmen zijn voorspellingsmodellen.
Dit leidde tot de natuurlijke vraag: kan gzip taalmodellering uitvoeren?¹
Geen neuraal netwerk, geen geleerde parameters, niets. Gewoon de compressor die bij je besturingssysteem wordt geleverd. Je voert het een corpus, geeft het een normale tekstprompt, en het zet die prompt voort door te zoeken naar de byte-sequenties die het beste comprimeren. Hier is een voorbeeld van echte, onbewerkte output nadat het model is gevoed met tiny Shakespeare:
gzipt --corpus data/tinyshakespeare.txt --prompt $'MENENIUS:\n' --length 200
Output:
MENENIUS:
'Though all at once canq
MARCIUS:
Pray now, nocamest thou to a morsel .
LARTIUS:
Hence, and
I' the end admire, where G
again; and after it ag .
Het blijkt dat het antwoord "soort van" is. Het is niet precies coherente tekst, maar het is duidelijk dat het model iets over de tekst weet. Veel meer dan ik had verwacht dat gzip zou weten.² Maar hoe kan een compressor dit genereren?
Compressie is voorspelling
Denk na over wat een compressor doet. Het besteedt weinig bytes aan data die het "verwacht" en veel bytes aan data die het niet verwacht. Als ik je een bestand geef waarin de letter A een miljoen keer wordt herhaald, kun je dat in één zin beschrijven. Een miljoen willekeurige bytes daarentegen hebben geen structuur om te exploiteren en comprimeren nauwelijks.
Dit is geen toeval; het is de kern van de informatietheorie. Het aantal bits dat nodig is om een symbool te coderen is $-\log_2 p$, waarbij $p$ de waarschijnlijkheid is die het model eraan toekent. Een hoge waarschijnlijkheid betekent weinig bits. Elk compressieprogramma heeft dus een waarschijnlijkheidsmodel in zich verborgen, ongeacht of iemand dat expliciet heeft opgeschreven.
gzip maakt gebruik van DEFLATE, dat de volgende bytes comprimeert door overeenkomsten te zoeken met de recente tekst in een schuivend venster (sliding window) van 32 KiB. Als een vervolgtekst iets weerspiegelt dat al in het venster staat, codeert DEFLATE dit als een goedkope back-referentie in plaats van als letterlijke bytes. Dus:
- Een vervolg dat gzip "verwachtte", omdat het tekst weerspiegelt die al in het venster staat, comprimeert tot bijna niets.
Dit geeft ons een score. Als ik een bepaalde context heb en wil weten hoe goed een kandidaat-vervolg is, meet ik simpelweg:
$$\text{score}(\text{kandidaat}) = \texttt{len(gzip(context + kandidaat))}$$
Hoe kleiner de gecomprimeerde lengte, hoe meer de kandidaat "voorspeld" is. Om het model voor te bereiden, neem ik een corpus op in het venster van gzip. Elk vervolg dat lijkt op het corpus comprimeert klein, en elk vervolg dat dat niet doet, comprimeert groot.
Genereren via beam search
Scoren is één ding; genereren is iets anders. De naïeve aanpak van het kiezen van de enkele volgende byte die het beste comprimeert, faalt volledig. De reden is subtiel: gzip geeft alleen een integer byte-lengte (geen fracties). Het toevoegen van één byte verandert de gecomprimeerde lengte vaak helemaal niet, waardoor veel kandidaten gelijkstaan en het signaal verloren gaat in kwantiseringsruis.
De oplossing is om een heel traject vooruit te kijken voordat er een keuze wordt gemaakt. gzipt voert een beam search uit over byte-sequenties. In elke stap is de huidige context:
corpus venster + recent uiteinde van (prompt + gegenereerde bytes)
Vervolgens probeert gzipt mogelijke volgende bytes. Elk kandidaat-vervolg wordt gescoord door de context + kandidaat te comprimeren en te controleren hoeveel bytes het gecomprimeerde resultaat inneemt.
Het proces verloopt als volgt:
- Prompt: Begin met de prompt van de gebruiker als de initiële tekst om mee verder te gaan. Er is geen starttoken; de prompt-bytes maken simpelweg deel uit van de context die gzip ziet.
- Context: Toon gzip het corpus-venster plus het recente uiteinde van de prompt/gegenereerde tekst.
- Zoeken: Behoud de
beamwidth meest-comprimeerbare partiële vervolgen. Breid elk uit met elke byte die in het corpus voorkomt, scoreer ze allemaal op gecomprimeerde lengte en snoei ze terug naar de beste beamwidth. Herhaal dit voor het aantal horizon bytes.
- Vastleggen: Neem het meest-comprimeerbare volledige traject (of sample uit de finalisten als de temperatuur positief is), voeg dit toe en begin de lus opnieuw.
Een belangrijk detail is dat alleen de laatste bytes van de gegenereerde output in de scorecontext blijven. DEFLATE codeert nabije overeenkomsten goedkoper dan verre. Als gzip zijn volledige geschiedenis zou kunnen zien, is de goedkoopste optie vaak om in letterlijke lussen te vervallen, waarbij tekst die net is uitgegeven herhaaldelijk wordt gekopieerd.
Het hele project bestaat uit één bestand in pure standaard-library Python (alleen zlib). De code is beschikbaar op GitHub.
***
¹ Het paper probeerde dit inderdaad, maar het resultaat was matig. Het toevoegen van beam search verbeterde de generatiekwaliteit aanzienlijk (een idee dat zij ook noemden), wat hieronder wordt besproken.
² De code gebruikt feitelijk zlib in plaats van een gzip-proces op te starten, maar de naam GziPT was te goed. Ik geloof dat ze beide hetzelfde DEFLATE-algoritme gebruiken.
Kan gzip een taalmodel zijn?
Inleiding
Een tijdje geleden schreef ik over taalmodellering zonder neurale netwerken, waarbij ik Shakespeare genereerde met een onbegrensd n-grammodel: geen gewichten, geen training, alleen tellen. Toevalligerwijs stuitte ik op het artikel Language Modeling is Compression, waarin de equivalentie tussen compressie en voorspelling werd genoemd:
Elk voorspellingsmodel is inherent een compressor, en alle compressiealgoritmen zijn voorspellingsmodellen.
Dit leidde tot de natuurlijke vraag: kan gzip taalmodellering uitvoeren?¹
Geen neuraal netwerk, geen geleerde parameters, niets. Gewoon de compressor die bij je besturingssysteem wordt geleverd. Je voert het een corpus, geeft het een normale tekstprompt, en het zet die prompt voort door te zoeken naar de byte-sequenties die het beste comprimeren. Hier is een voorbeeld van echte, onbewerkte output nadat het model is gevoed met tiny Shakespeare:
gzipt --corpus data/tinyshakespeare.txt --prompt $'MENENIUS:\n' --length 200
Output:
MENENIUS:
'Though all at once canq
MARCIUS:
Pray now, nocamest thou to a morsel .
LARTIUS:
Hence, and
I' the end admire, where G
again; and after it ag .
Het blijkt dat het antwoord "soort van" is. Het is niet precies coherente tekst, maar het is duidelijk dat het model iets over de tekst weet. Veel meer dan ik had verwacht dat gzip zou weten.² Maar hoe kan een compressor dit genereren?
Compressie is voorspelling
Denk na over wat een compressor doet. Het besteedt weinig bytes aan data die het "verwacht" en veel bytes aan data die het niet verwacht. Als ik je een bestand geef waarin de letter A een miljoen keer wordt herhaald, kun je dat in één zin beschrijven. Een miljoen willekeurige bytes daarentegen hebben geen structuur om te exploiteren en comprimeren nauwelijks.
Dit is geen toeval; het is de kern van de informatietheorie. Het aantal bits dat nodig is om een symbool te coderen is $-\log_2 p$, waarbij $p$ de waarschijnlijkheid is die het model eraan toekent. Een hoge waarschijnlijkheid betekent weinig bits. Elk compressieprogramma heeft dus een waarschijnlijkheidsmodel in zich verborgen, ongeacht of iemand dat expliciet heeft opgeschreven.
gzip maakt gebruik van DEFLATE, dat de volgende bytes comprimeert door overeenkomsten te zoeken met de recente tekst in een schuivend venster (sliding window) van 32 KiB. Als een vervolgtekst iets weerspiegelt dat al in het venster staat, codeert DEFLATE dit als een goedkope back-referentie in plaats van als letterlijke bytes. Dus:
- Een vervolg dat gzip "verwachtte", omdat het tekst weerspiegelt die al in het venster staat, comprimeert tot bijna niets.
Dit geeft ons een score. Als ik een bepaalde context heb en wil weten hoe goed een kandidaat-vervolg is, meet ik simpelweg:
$$\text{score}(\text{kandidaat}) = \texttt{len(gzip(context + kandidaat))}$$
Hoe kleiner de gecomprimeerde lengte, hoe meer de kandidaat "voorspeld" is. Om het model voor te bereiden, neem ik een corpus op in het venster van gzip. Elk vervolg dat lijkt op het corpus comprimeert klein, en elk vervolg dat dat niet doet, comprimeert groot.
Genereren via beam search
Scoren is één ding; genereren is iets anders. De naïeve aanpak van het kiezen van de enkele volgende byte die het beste comprimeert, faalt volledig. De reden is subtiel: gzip geeft alleen een integer byte-lengte (geen fracties). Het toevoegen van één byte verandert de gecomprimeerde lengte vaak helemaal niet, waardoor veel kandidaten gelijkstaan en het signaal verloren gaat in kwantiseringsruis.
De oplossing is om een heel traject vooruit te kijken voordat er een keuze wordt gemaakt. gzipt voert een beam search uit over byte-sequenties. In elke stap is de huidige context:
corpus venster + recent uiteinde van (prompt + gegenereerde bytes)
Vervolgens probeert gzipt mogelijke volgende bytes. Elk kandidaat-vervolg wordt gescoord door de context + kandidaat te comprimeren en te controleren hoeveel bytes het gecomprimeerde resultaat inneemt.
Het proces verloopt als volgt:
- Prompt: Begin met de prompt van de gebruiker als de initiële tekst om mee verder te gaan. Er is geen starttoken; de prompt-bytes maken simpelweg deel uit van de context die gzip ziet.
- Context: Toon gzip het corpus-venster plus het recente uiteinde van de prompt/gegenereerde tekst.
- Zoeken: Behoud de
beamwidth meest-comprimeerbare partiële vervolgen. Breid elk uit met elke byte die in het corpus voorkomt, scoreer ze allemaal op gecomprimeerde lengte en snoei ze terug naar de beste beamwidth. Herhaal dit voor het aantal horizon bytes.
- Vastleggen: Neem het meest-comprimeerbare volledige traject (of sample uit de finalisten als de temperatuur positief is), voeg dit toe en begin de lus opnieuw.
Een belangrijk detail is dat alleen de laatste bytes van de gegenereerde output in de scorecontext blijven. DEFLATE codeert nabije overeenkomsten goedkoper dan verre. Als gzip zijn volledige geschiedenis zou kunnen zien, is de goedkoopste optie vaak om in letterlijke lussen te vervallen, waarbij tekst die net is uitgegeven herhaaldelijk wordt gekopieerd.
Het hele project bestaat uit één bestand in pure standaard-library Python (alleen zlib). De code is beschikbaar op GitHub.
***
¹ Het paper probeerde dit inderdaad, maar het resultaat was matig. Het toevoegen van beam search verbeterde de generatiekwaliteit aanzienlijk (een idee dat zij ook noemden), wat hieronder wordt besproken.
² De code gebruikt feitelijk zlib in plaats van een gzip-proces op te starten, maar de naam GziPT was te goed. Ik geloof dat ze beide hetzelfde DEFLATE-algoritme gebruiken.
Groetjes,