Kolmogorovova komplexita

Kolmogorovova komplexita meria, aký krátky program stačí na presné vygenerovanie daného objektu (reťazca, súboru, obrazu). Formálne: komplexita K(x) je dĺžka najkratšieho programu, ktorý vypíše x a skončí. Je to matematicky najčistejšia definícia toho, čo znamená „mať vzor" — a v ére veľkých jazykových modelov nečakane praktická optika: tréning LLM sa dá čítať ako hľadanie krátkeho popisu internetu.

1. Intuícia

  • Nízka komplexita: objekt má pravidlo alebo vzor.
    • Príklad: 010101... opakované 1000× vieš popísať krátko („vypíš 01 tisíckrát").
  • Vysoká komplexita: objekt nemá skrátený popis.
    • Príklad: náhodný 1000-bitový reťazec sa typicky nedá výrazne skomprimovať — najkratší „program" je vypísať ho celý.

Inými slovami: Kolmogorovova komplexita je dĺžka najlepšieho vysvetlenia. Občianske meno tej istej myšlienky je Occamova britva; K(x) jej dáva jednotky (bity).

2. Dôležité teoretické nuansy

  • Závislosť od univerzálneho stroja: hodnota K(x) závisí od voľby referenčného univerzálneho stroja, ale len do aditívnej konštanty (invariance theorem) — interpreter iného jazyka má fixnú dĺžku.
  • Algoritmická náhodnosť: objekt je algoritmicky náhodný, ak jeho K(x) je blízko jeho vlastnej dĺžke — neexistuje preň žiadna skratka.
  • Vzťah ku kompresii: čo je dobre komprimovateľné, má nižšiu Kolmogorovovu komplexitu. Každý kompresor je horný odhad K(x); dokonalý kompresor by ju dosiahol.
  • Vzťah k Shannonovej entropii: entropia je priemerná vlastnosť distribúcie, K(x) vlastnosť jedného konkrétneho objektu. Pre typické vzorky z distribúcie sa zbiehajú; pre jednotlivé objekty sa môžu rozchádzať.

3. Prečo je nevyčísliteľná

Pre ľubovoľné x neexistuje algoritmus, ktorý by vždy presne spočítal K(x). Dôvod súvisí s halting problémom: museli by sme vedieť, ktoré krátke programy vôbec zastavia. Elegantný dôkaz je Berryho paradox v algoritmickom prevedení — program „nájdi prvý reťazec, ktorého K presahuje N" by sám bol krátkym popisom toho reťazca, spor.

Praktický dôsledok: K(x) je teoretický ideál; v praxi používame horné odhady cez kompresory (gzip, zstd, LZMA), MDL a — najnovšie — jazykové modely.

4. Prepojenie na ML/AI: kompresia ako učenie

  • Minimum Description Length (MDL): preferuj model minimalizujúci dĺžka(model) + dĺžka(dáta|model). To je formálny podklad regularizácie a výberu jednoduchších modelov — rovnováha fit vs. generalizácia.
  • Solomonoffova indukcia: vážené predikcie cez všetky programy konzistentné s dátami, kratšie programy s vyššou váhou. Nevyčísliteľný ideál učenia — Bayes + Occam v jednom. Hutterov AIXI na tom stavia definíciu univerzálneho agenta.
  • „Language modeling is compression": predikcia ďalšieho tokenu a kompresia sú matematicky to isté (aritmetické kódovanie premieňa pravdepodobnosti na bity). LLM použitý ako kompresor poráža gzip aj na dátach, na ktorých nebol trénovaný — a kvalita modelu sa dá merať tým, ako krátko vie dáta zapísať.
  • Hutter Prize: dlhoročná súťaž v kompresii Wikipédie postavená presne na téze, že lepšia kompresia = lepšie porozumenie = krok k inteligencii.
  • Praktické ozveny: knowledge distillation (krátky popis správania veľkého modelu), grokking (sieť nájde krátky všeobecný algoritmus namiesto dlhej memorizácie), tokenizácia (sub-word slovník ako prvá kompresná vrstva).

5. Praktické príklady

  • Text s opakujúcim sa vzorom: nízka K(x), vysoká kompresia.
  • Šifrované alebo náhodné dáta: vysoká K(x), minimálna kompresia — dobrá šifra je od náhody nerozoznateľná.
  • Detekcia anomálií kompresiou: vzorka, ktorá výrazne zhorší kompresný pomer datasetu, sa od neho štrukturálne líši — trik použiteľný bez akéhokoľvek trénovania.
  • Deduplikácia tréningových dát: near-duplicate dokumenty majú nízku podmienenú komplexitu voči sebe navzájom; kompresné metriky ich lacno odhalia.

6. Časté omyly

  • K(x) ≠ Shannonova entropia (pozri nuansy vyššie).
  • „Neviem komprimovať" ≠ „absolútne náhodné"; znamená to len, že daný kompresor nenašiel kratší popis.
  • Vysoká komplexita ≠ užitočnosť; náhodný šum má maximálnu K(x) a nulovú hodnotu. Zaujímavé objekty (život, jazyk, kód) ležia medzi extrémami — majú štruktúru aj hĺbku.
  • Kolmogorovova komplexita nemeria čas — krátky program môže bežať prakticky večne (na to je logical depth).

7. Quick Reference

Pojem Význam
K(x) dĺžka najkratšieho programu generujúceho x
Nízka komplexita krátky popis, pravidelný vzor
Vysoká komplexita slabá kompresia, bez krátkeho popisu
Teoretický status nevyčísliteľná vo všeobecnosti (halting problém)
Praktické odhady kompresory, MDL, jazykové modely
Solomonoff/AIXI nevyčísliteľný ideál indukcie a univerzálneho agenta
Relevancia pre AI model selection, regularizácia, „LM = kompresia", dedup dát

8. Zdroje

  • Li, Vitányi: An Introduction to Kolmogorov Complexity and Its Applications — štandardná monografia.
  • Rissanen: pôvodné práce o Minimum Description Length.
  • Delétang et al.: Language Modeling Is Compression (DeepMind, 2023).
  • Hutter: Universal Artificial Intelligence (AIXI) a Hutter Prize.

Zhrnutie

  • Kolmogorovova komplexita formalizuje, ako krátko vieme opísať konkrétny objekt — Occamova britva v bitoch.
  • Je nevyčísliteľná; prakticky ju zhora odhadujeme kompresormi a modelmi.
  • Pre AI je to zjednocujúca optika: MDL, Solomonoffova indukcia aj moderné „language modeling is compression" hovoria to isté — učenie je hľadanie krátkeho popisu sveta.