Micro-Diffusion Compression -- Binary Tree Tweedie Denoising for Online Probability Estimation

Each language version is independently generated for its own context, not a direct translation.

Stel je voor dat je een heel lange, saaie lijst met instructies moet opslaan op een harde schijf. Je wilt dat deze lijst zo klein mogelijk is, zodat je ruimte bespaart. Dit noemen we data-compressie.

De meeste moderne methoden (zoals xz of gzip) zijn als slimme archivarissen die zoeken naar herhalingen. Als je de zin "de kat zat op de mat" tien keer hebt, zeggen ze: "Oké, ik schrijf dat één keer op en tel er '10x' bij."

Maar Midicoth, de uitvinding uit dit paper, werkt anders. Het is geen archivaar die zoekt naar herhalingen; het is een profeet die de toekomst voorspelt.

Hier is hoe het werkt, vertaald naar alledaagse taal:

1. De Profeet die te voorzichtig is (Het PPM-probleem)

Stel je een profeet voor die probeert te raden welk woord je als volgende gaat zeggen.

Als hij je kent (hij heeft je veel tekst gezien), is hij heel zeker: "Je gaat zeggen 'de'."
Maar als hij je nog niet kent (een nieuw woord of een rare zin), is hij bang om fout te zitten. Hij zegt dan: "Ik denk dat het 'de' is, maar het kan ook 'een', 'het', of 'een' zijn..." Hij verdeelt zijn zekerheid over alle mogelijke woorden.

In de wereld van computers heet dit Jeffreys-prior. Het is een veilige, maar saaie voorspelling. Omdat hij te voorzichtig is, "verspil" hij bits. Het is alsof je een zware jas draagt op een zomerdag: het werkt, maar het is niet efficiënt.

2. De "Micro-Diffusie": Het terugdraaien van de tijd

Hier komt het magische deel van Midicoth. De schrijver noemt dit Micro-Diffusie.

Stel je voor dat je een foto hebt van een gezicht, maar de foto is wazig gemaakt (vervuild met ruis).

De "normale" profeet kijkt naar die wazige foto en zegt: "Het is waarschijnlijk een mens, maar het kan ook een hond zijn."
Midicoth doet iets anders. Het zegt: "Wacht even. Ik weet dat deze foto wazig is gemaakt door een specifieke filter (de veilige jas). Ik ga die filter terugdraaien."

Het gebruikt een wiskundige formule (de Tweedie-formule) om te berekenen: "Als de profeet zo voorzichtig was, hoe zeker had hij dan moeten zijn?"

Het is alsof je een wazige foto van een kat kijkt, en je zegt: "Omdat de lens zo wazig was, moet die vlek in het midden eigenlijk een scherpe kat zijn." Midicoth "ontruist" de voorspelling van de profeet en maakt hem weer scherp.

3. De Boomstructuur: Van groot naar klein

Om dit "ruis verwijderen" slim te doen, breekt Midicoth het probleem op in kleine stukjes, net als een boom.

Stel je voor dat je moet raden welk lettertje (A-Z) als volgende komt.

Stap 1: Is het een hoofdletter of een kleine letter? (Ja/Nee)
Stap 2: Als het een hoofdletter is, is het een klinker of een medeklinker? (Ja/Nee)
Stap 3: Is het een 'A', 'B' of 'C'? (Ja/Nee)

In plaats van te raden welke van de 256 mogelijke bytes het is (wat heel moeilijk is om precies te kalibreren), maakt Midicoth 8 keer een simpel Ja/Nee-keuze.

Dit is als het oplossen van een raadsel door eerst te vragen: "Is het groter dan een huis?" en dan pas: "Is het een koe?"
Omdat het maar Ja/Nee-vragen zijn, kan het systeem heel snel en nauwkeurig leren welke "ruis" er zit in de voorspelling.

4. De 5-Lagen Keten

Midicoth is niet één ding, maar een fabriekslijn met 5 stations die door elkaar werken:

De Basis: Kijkt naar de recente tekst (PPM).
De Herhaling: Kijkt of dit woord al eerder in de tekst is voorgekomen (Match-model).
De Woorden: Kijkt of we een zin aan het voltooien zijn (Woord-model).
De Lange Context: Kijkt naar patronen die verder weg staan.
De "Ruis-Verwijderaar" (Micro-Diffusie): Dit is de laatste stap. Alle vorige stations hebben een voorspelling gedaan, maar die voorspelling is nog steeds een beetje "wazig" door de voorzichtigheid. De Micro-Diffusie-laag pakt die voorspelling, kijkt naar de "ruis" (hoe zeker was de profeet eigenlijk?), en maakt hem scherp.

Waarom is dit zo cool?

Geen AI, geen zware computers: De meeste super-slimme compressieprogramma's (zoals die van Google of Meta) gebruiken enorme neurale netwerken die dagenlang getraind moeten worden en enorme videokaarten nodig hebben. Midicoth doet dit zonder training. Het leert terwijl het werkt, net als een mens die een taal leert spreken.
Snelheid: Het werkt op één processor-kern van je computer en is razendsnel.
Resultaat: Het slaat bestanden kleiner op dan de beste standaardprogramma's (zoals xz), zelfs zonder dat het "weet" wat de tekst inhoudt.

Samenvatting in één zin

Midicoth is als een slimme vertaler die niet alleen kijkt naar wat je zegt, maar ook begrijpt hoe je het zegt, en vervolgens de onzekerheid uit je woorden haalt om ze in een nog kleiner pakketje te stoppen, zonder dat hij daarvoor ooit een boek heeft gelezen.

Het bewijst dat je niet altijd de zwaarste AI nodig hebt om slimme dingen te doen; soms is een slimme wiskundige truc (het "terugdraaien" van voorzichtigheid) genoeg om de wereld te veranderen.

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het paper "Micro-Diffusion Compression: Binary Tree Tweedie Denoising for Online Probability Estimation" in het Nederlands.

Titel en Context

Titel: Micro-Diffusion Compression: Binary Tree Tweedie Denoising for Online Probability Estimation
Auteur: Roberto Tacconelli (Onafhankelijk Onderzoeker)
Doel: Het presenteren van Midicoth, een verliesvrij compressiesysteem dat geavanceerde statistische modellering combineert met een nieuw concept: "micro-diffusion" (gebaseerd op Tweedie's empirische Bayes-formule), zonder gebruik te maken van neurale netwerken, vooraf getrainde data of GPU's.

1. Het Probleem

Bij adaptieve statistische compressie (zoals PPM - Prediction by Partial Matching) is de kwaliteit van compressie afhankelijk van hoe goed het model de volgende symbool kan voorspellen. Een fundamenteel knelpunt in bestaande systemen is de gladheidsproblematiek (smoothing):

Om te voorkomen dat onbekende symbolen een kans van nul krijgen, gebruiken modellen een prior (zoals de Jeffreys-prior).
Deze prior werkt als een "shrinkage-operator" die de empirische verdeling trekt naar een uniforme verdeling.
Gevolg: Bij contexten met weinig observaties is de voorspelde verdeling veel vlakker dan de werkelijke bronverdeling. Dit leidt tot verspilde bits omdat het model niet scherp genoeg kan voorspellen.
Bestaande modellen hebben geen mechanisme om te onderscheiden tussen een situatie waar de prior domineert (weinig data) en een situatie waar de data domineert (veel data), waardoor ze de "ruis" (de prior) niet kunnen verwijderen.

2. Methodologie: De Midicoth-pijplijn

Midicoth is een volledig online, parameter-vrij systeem dat in één doorloop (single-pass) werkt. Het bestaat uit een cascade van vijf lagen die de waarschijnlijkheidsverdeling stap voor stap verfijnen voordat deze wordt ingesloten door een arithmetische coder.

De Vijf Lagen:

Adaptieve PPM (Order 0–4): De basislaag gebruikt PPMC (met exclusie) en de Jeffreys-prior. Het houdt tellers bij voor byte-voorkomens in verschillende contexten.
Extended Match Model: Detecteert lange-range herhalingen (repetities) in de data via hash-tabellen.
Trie-gebaseerd Woordmodel: Voorspelt de volgende byte binnen woorden (gebaseerd op een trie) en de eerste byte van het volgende woord (bigram).
High-Order Context Model (Order 5–8): Aggregeert contexten van hogere orde die buiten het bereik van de standaard PPM vallen, maar gebruikt een andere blend-mechanisme dan PPM om problemen met schaarse data te voorkomen.
Micro-Diffusion Laag (De Kerninnovatie): Dit is de laatste correctiestap, toegepast na het mengen (blending) van alle bovenstaande modellen.

De Micro-Diffusion Laag (Tweedie Denoising):

Deze laag behandelt de gecombineerde voorspelling als een "ruisig" signaal dat hersteld moet worden.

Concept: De Jeffreys-prior wordt gezien als een toegevoegde ruis (shrinkage) die de verdeling naar uniform trekt. Het doel is om dit proces om te draaien (reverse diffusion) met behulp van Tweedie's formule.
Binair Boom Decompositie: In plaats van een 256-wegige verdeling direct te kalibreren (wat veel data vereist), wordt elke byte-voorspelling opgebroken in een binomiale boom van 8 beslissingen (van MSB tot LSB).
- Dit verhoogt de data-efficiëntie enorm: elke knoop in de boom heeft slechts twee uitkomsten (links/rechts).
- Het biedt een hiërarchische context (bijv. MSB onderscheidt controlekarakters van printbare ASCII, LSB maakt fijne onderscheidingen).
Niet-parametrische Correctie: Voor elke knoop in de boom wordt een Tweedie-score geschat via kalibratietabellen. De correctie is additief: $\hat{p}' = \hat{p} + \delta$ , waarbij $\delta = E[\theta|\hat{p}] - E[\hat{p}]$ .
Multi-stap Denoising: Het proces wordt uitgevoerd in $K=3$ opeenvolgende stappen. Elke stap gebruikt een onafhankelijke kalibratietabel om de resterende ruis van de vorige stap te verwijderen.
James-Stein Shrinkage: Om te voorkomen dat ruisige correcties in schaarse kalibratiebakjes de compressie verslechteren, wordt de correctie afgezwakt (geschrubben) als het signaal-ruisverhouding (SNR) te laag is.

3. Belangrijkste Bijdragen

Binair Boom Tweedie Denoising: Een multi-stap score-gebaseerd reverse diffusion proces dat byte-voorspellingen decomposeert en de additieve Tweedie-correctie schat via kalibratietabellen (ongeveer 4,7 MB groot, 155.520 entries).
Binair Boom Decompositie voor Kalibratie: Zet 256-wegige kalibratie om naar binair, wat de data-efficiëntie drastisch verbetert en rijke contextmodelling mogelijk maakt via ouder-bits.
Gecascadeerde Vijf-Lagen Pijplijn: Een zorgvuldig geordende reeks modellen waarbij de Tweedie-denoising als laatste stap wordt toegepast. Dit stelt het systeem in staat om systematische biases van het hele ensemble te corrigeren, niet alleen die van de basis-PPM.
Comprehensieve Ablatie-studie: Toont aan dat elke component bijdraagt, waarbij de post-blend micro-diffusion laag consistent 2,3% tot 2,7% verbetering levert.

4. Resultaten

Midicoth presteert opvallend goed, vooral gezien het gebrek aan neurale netwerken of GPU's.

enwik8 Benchmark (100 MB Wikipedia):
- Midicoth: 1,753 bpb (bits per byte) / 21,9 MB.
- Vergelijking: Verslaat xz -9 (1,989 bpb) met 11,9%.
- Opmerking: Het blijft achter bij zware context-mixers zoals PAQ (~~1,27 bpb) en CMIX (~~1,17 bpb), maar doet dit met een veel eenvoudiger architectuur.
alice29.txt (152 KB Canterbury Corpus):
- Midicoth: 2,119 bpb.
- Vergelijking: Verslaat xz -9 (2,551 bpb) met 16,9%.
Out-of-Distribution (Overheidsrapport 2025, 334 KB):
- Midicoth: 1,525 bpb.
- Vergelijking: Verslaat xz -9 (1,739 bpb) met 12,3%. Dit toont sterke generalisatie aan onbekende tekststijlen.
Snelheid en Implementatie:
- Geschreven in ~2.000 regels C (geen externe afhankelijkheden).
- Compressiesnelheid: ~60 KB/s op één CPU-kern.
- Volledig deterministisch en verliesvrij.

5. Betekenis en Conclusie

Het paper demonstreert dat er nog aanzienlijke ruimte is voor verbetering in klassieke statistische compressie door innovatieve algoritmen, zonder terug te grijpen naar zware neurale netwerken.

Paradigmaverschuiving: Het behandelt de "ruis" veroorzaakt door smoothing (prior) als een denoising-probleem dat opgelost kan worden met Tweedie's formule, een concept dat eerder vooral in deep learning (diffusion models) werd gebruikt.
Efficiëntie: Door de calibratie te beperken tot binaire beslissingen in een boomstructuur, kan het systeem effectief leren met beperkte data, zelfs op kleine bestanden.
Post-Blend Correctie: De ontdekking dat het toepassen van de denoising na het mengen van modellen het meest effectief is, is een cruciaal inzicht. Het corrigeert de gecombineerde bias van het hele ensemble.
Beperkingen: Het systeem is geoptimaliseerd voor tekst. Voor binaire data (zoals executables of afbeeldingen) presteert het minder goed dan gespecialiseerde compressoren, en het is momenteel single-threaded.

Kortom, Midicoth sluit de kloof tussen lichte statistische compressoren en zware context-mixers, en toont aan dat "micro-diffusion" een krachtig hulpmiddel is voor online waarschijnlijkheidsschatting.