The LZ78 Source

Titel: The LZ78 Source: Definition, Entropic Properties, and Application to In-Context Learning

Auteurs: Naomi Sagan, Amir Dembo, Matthew Ho, en Tsachy Weissman
Publicatie: IEEE Transactions on Information Theory

---

1. Probleemstelling en Context

Het artikel introduceert en analyseert een nieuwe familie van stochastische processen, de "LZ78 Source", die wordt gegenereerd door de sequentiële kans-toewijzingen (Sequential Probability Assignments - SPAs) die voortkomen uit het beroemde LZ78-compressiealgoritme.

Hoewel LZ78 al decennialang wordt bestudeerd als een universeel compressiemiddel voor deterministische sequenties, is het nog niet grondig onderzocht als een probabilistische bron (een data-genererend proces). Bestaande studies beperkten zich vaak tot verliesbeperkte compressie of gebruikten het als hulpmiddel voor gambling en voorspelling.

De kernvragen die dit artikel beantwoordt zijn:

• Wat zijn de fundamentele entropische eigenschappen van een proces dat gegenereerd wordt door de LZ78-SPA?
• Hoe gedraagt de entropie, de compressibiliteit en de convergentie van log-kansen zich in dit proces?
• Kan deze bron dienen als een uitdagende benchmark voor het bestuderen van In-Context Learning (ICL) in transformer-modellen (zoals LLM's), gezien de bron niet-stationair en niet-Markoviaans is?

2. Methodologie: Definitie van de LZ78 Bron

De auteurs definiëren de LZ78 bron ($Q_{LZ,\Pi}$) als een stochastisch proces $X = (X_1, X_2, \dots)$ over een alfabet $\mathcal{A}$, gekoppeld aan een hulpproces $B$ van kansverdelingen.

Het generatieproces:

1. Er wordt een prior-verdeling $\Pi$ gekozen over het simplex van kansverdelingen $\mathcal{M}(\mathcal{A})$.
2. Er wordt een reeks onafhankelijke en identiek verdeelde (i.i.d.) parameters $\Theta_0, \Theta_1, \dots$ getrokken uit $\Pi$.
3. Een LZ78 prefix-boom wordt dynamisch opgebouwd:
   • Bij elke stap $t$ bevindt men zich in een knoop in de boom.
   • Als de knoop geen $\Theta$-waarde heeft, wordt de volgende $\Theta$ uit de reeks toegewezen aan deze knoop.
   • De volgende symbool $X_t$ wordt getrokken volgens de verdeling $B_t$ (de $\Theta$-waarde van de huidige knoop).
   • De boom wordt ververst: als $X_t$ een nieuwe tak creëert, wordt een nieuwe knoop toegevoegd en een nieuwe $\Theta$ toegewezen, waarna men terugkeert naar de wortel.

Dit proces is niet-stationair en niet-Markoviaans. De context die nodig is om de volgende symbolen te voorspellen, groeit met de lengte van de sequentie.

3. Belangrijkste Bijdragen en Theoretische Resultaten

De paper levert rigoureuze wiskundige karakteriseringen van deze bron:

A. Entropie en Convergentie (Shannon-McMillan-Breiman)

• Entropiesnelheid: De entropiesnelheid van de LZ78 bron is gelijk aan de verwachte entropie van de prior: $E_{\Theta \sim \Pi}[H(\Theta)]$.
• Convergentie: De genormaliseerde log-kans van een gerealiseerde sequentie convergeert bijna zeker (almost surely) naar deze entropiesnelheid. Dit is een variant van het Shannon-McMillan-Breiman-theorema, wat aangeeft dat de bron "bijna stationair en ergodisch" is in termen van log-kansen.

B. De "Jensen Gap" en Finite-State Compressibiliteit

Dit is een van de meest opvallende bevindingen.

• Voor een stationaire ergodische bron is de finite-state compressibiliteit gelijk aan de entropiesnelheid.
• Voor de LZ78 bron is de finite-state compressibiliteit (en de optimale log-loss van een Markov-model) bijna zeker gelijk aan $H(E[\Theta])$.
• Omdat de entropie-functie $H(\cdot)$ concave is, geldt volgens de ongelijkheid van Jensen:
  $$H(E[\Theta]) \geq E[H(\Theta)]$$
• Het verschil tussen deze twee waarden is de "Jensen gap", die gelijk is aan de wederzijdse informatie $I(\Theta; Y)$.
• Conclusie: Elke model met een eindige geheugen (zoals een $k$-de orde Markov-model) zal een hogere log-loss hebben dan de werkelijke entropiesnelheid van de bron. De bron is fundamenteel moeilijker te comprimeren met eindige geheugenmodellen dan de entropiesnelheid suggereert.

C. Empirische Verdelingen

Ondanks de complexe afhankelijkheidsstructuur, zijn de realisaties van de bron lokaal "bijna i.i.d.". De eindig-dimensionale empirische verdelingen van de sequenties convergeren bijna zeker naar een deterministische i.i.d. wet met verdeling $E[\Theta]$. Dit betekent dat, hoewel de bron niet-stationair is, de frequenties van patronen stabiliseren naar een vaste verdeling.

D. Divergentie met Markov-wetten

De paper toont aan dat de relatieve entropie (Kullback-Leibler divergentie) tussen de LZ78 bron en elke $k$-de orde Markov-wet niet naar nul convergeert, maar naar een positieve waarde die de Jensen-gap en een extra divergentie-term bevat. Dit bevestigt dat Markov-modellen de bron asymptotisch niet perfect kunnen benaderen.

4. Experimentele Validatie en Toepassing op In-Context Learning (ICL)

De auteurs gebruiken de LZ78 bron als een testbed voor In-Context Learning in transformer-modellen.

• Opzet: Transformers (met 1 tot 5 lagen) worden getraind op data gegenereerd door de LZ78 bron met verschillende priors (bijv. Dirichlet-priors).
• Doel: Onderzoeken of transformers kunnen leren om een voorspellingsalgoritme toe te passen op de context (in-context), zelfs wanneer de data niet-Markoviaans is en de contextlengte groeit.
• Resultaten:
  • Transformers met voldoende lagen (3-5) tonen een afnemende log-loss naarmate de context groeit, wat wijst op succesvol ICL.
  • Ze presteren beter dan klassieke algoritmen zoals Context Tree Weighting (CTW) en Markov-modellen van vaste orde.
  • Er is echter nog steeds een kloof tussen de prestaties van de transformer en de theoretische ondergrens (de entropiesnelheid), wat aangeeft dat het leren van de complexe LZ78-afhankelijkheden uitdagend blijft.
  • Generalisatie: Wanneer getrainde modellen worden getest op echte genomische data, vertonen ze vergelijkbare patronen (afnemende log-loss), wat suggereert dat de geleerde ICL-heuristieken generaliseren naar real-world data.

5. Significance en Impact

Deze paper is significant om de volgende redenen:

1. Nieuw theoretisch inzicht: Het vult een gat in de literatuur door LZ78 niet alleen als compressor, maar als een probabilistische bron te analyseren. Het onthult de unieke eigenschap van de "Jensen gap" tussen entropiesnelheid en finite-state compressibiliteit.
2. Benchmark voor AI: De LZ78 bron biedt een nieuwe, moeilijkere benchmark dan bestaande Markov- of variabele-orde Markov-bronnen. Omdat de contextlengte oneindig groeit, is het een ideale test voor de capaciteit van moderne deep learning-modellen om lange-termijn afhankelijkheden en niet-stationaire patronen te leren zonder expliciete training op die specifieke patronen.
3. Inzicht in Transformers: De experimenten tonen aan dat transformers in staat zijn om complexe, niet-Markovian voorspellingsstrategieën te leren via in-context learning, maar dat er fundamentele beperkingen blijven die gerelateerd zijn aan de complexiteit van de bron en de modelgrootte.

Kortom, het artikel verbindt klassieke informatie-theorie (LZ78, entropie) met moderne deep learning (transformers, ICL) en biedt zowel wiskundige bewijzen als empirisch bewijs voor de prestaties en grenzen van deze modellen op complexe, niet-stationaire data.