gzip skriver Shakespeare uten en eneste vekt, bare med beam search

En språkmodell trenger vanligvis vekter, en treningskjøring og en GPU. Nathan Barry klarer seg med komprimeringsbiblioteket som allerede ligger i operativsystemet ditt. På bloggen sin viser han gzipt, en modell uten ett eneste lært parameter, primet på tiny Shakespeare og bedt om å fortsette replikken til MENENIUS. Resultatet er ikke sammenhengende tekst, men den vet tydelig noe om korpuset.

«Enhver prediksjonsmodell er i seg selv en kompressor, og alle komprimeringsalgoritmer er prediksjonsmodeller.» — «Language Modeling is Compression», sitert i innlegget

Antall bits som trengs for å kode et symbol er minus log2 av sannsynligheten modellen gir det, så en kompressor har alltid en sannsynlighetsmodell inni seg, enten noen skrev den ned eller ikke. gzip bruker DEFLATE, som koder de neste bytene ved å lete etter treff i et glidende vindu på 32 KiB. Barry gjør det om til en score: komprimer konteksten pluss kandidaten, og tell hvor mange bytes resultatet tar. Jo mindre, desto mer «forventet» er fortsettelsen.

Den naive varianten feiler. Velger du bare den neste byten som komprimerer best, oppgir gzip en heltallslengde i bytes, og én ekstra byte endrer ofte ikke den lengden i det hele tatt. Kandidatene blir like, og signalet drukner i kvantiseringsstøy. Løsningen er å se et helt spenn framover: gzipt kjører beam search, beholder de mest komprimerbare delkandidatene, utvider hver av dem med hver byte som finnes i korpuset, og beskjærer tilbake igjen. Barry peker på at papiret prøvde metoden uten beam search og fikk dårlige resultater.

En siste detalj avgjør om det fungerer. Bare de siste bytene av det som allerede er generert får bli liggende i scoringskonteksten. DEFLATE koder nære treff billigere enn fjerne, så hvis gzip ser hele sin egen historikk, blir det billigste trekket å kopiere det den nettopp skrev, og genereringen låser seg i ordrette løkker. Hele implementasjonen er én fil ren standardbibliotek-Python, bare zlib, og koden ligger på GitHub.