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čí.

1. Intuícia

  • Nízka komplexita: objekt má pravidlo alebo vzor.
    • Príklad: 010101... opakované 1000x vieš popísať krátko.
  • Vysoká komplexita: objekt nemá skrátený popis.
    • Príklad: náhodný 1000-bitový reťazec sa často nedá výrazne skomprimovať.

Inými slovami: Kolmogorovova komplexita je „dĺžka najlepšieho vysvetlenia".

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.
  • Algoritmická náhodnosť: objekt je algoritmicky náhodný, ak jeho K(x) je blízko jeho vlastnej dĺžke.
  • Vzťah ku kompresii: čo je dobre komprimovateľné, má typicky nižšiu Kolmogorovovu komplexitu.

3. Prečo je to nevyčísliteľné (uncomputable)

Pre ľubovoľné x neexistuje všeobecný algoritmus, ktorý by vždy presne spočítal K(x). Intuitívny dôvod súvisí s halting problémom: ak by sa K(x) dalo presne rátať, vedeli by sme riešiť problémy, ktoré sú dokázateľne nerozhodnuteľné.

Praktický dôsledok:

  • K(x) je teoretický ideál,
  • v praxi používame odhady cez kompresory (gzip, zstd, LZMA), MDL a aproximácie.

4. Prepojenie na ML/AI

Kolmogorovova komplexita je základná intuícia za princípom:

  • Minimum Description Length (MDL): preferuj model, ktorý minimalizuje
    • dĺžku opisu modelu,
    • plus dĺžku opisu dát pod tým modelom.

To je blízke praktickým voľbám v ML:

  • penalizácia príliš zložitých modelov,
  • voľba jednoduchšieho vysvetlenia, ak má podobnú predikčnú kvalitu,
  • rovnováha medzi fitom a generalizáciou (bias-variance trade-off).

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.
  • Model checkpointy: veľké modely môžu mať vysokú deskriptívnu zložitosť, ale výstupy v konkrétnej úlohe môžu byť dobre komprimovateľné.

6. Časté omyly

  • K(x) nie je to isté ako Shannonova entropia (tá je priemerná vlastnosť distribúcie, nie jedného konkrétneho objektu).
  • „Neviem komprimovať" neznamená automaticky „absolútna náhodnosť"; znamená to len, že daná metóda kompresie nenašla kratší popis.
  • Vysoká komplexita neznamená praktickú užitočnosť; ide o deskriptívnu vlastnosť, nie priamo o hodnotu informácie pre úlohu.

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
Praktický nástupca odhady cez kompresiu a MDL
Relevancia pre AI model selection, regularizácia, generalizácia

8. Zdroje

  • Li, Vitányi: An Introduction to Kolmogorov Complexity and Its Applications.
  • Ming Li, Paul Vitanyi (survey chapters on algorithmic information theory).
  • Rissanen (MDL): pôvodné práce o minimum description length.

Zhrnutie

  • Kolmogorovova komplexita formalizuje, ako krátko vieme opísať konkrétny objekt.
  • Je silná teoretická idea pre rozdiel medzi štruktúrou a náhodnosťou.
  • V praxi ju nepočítame presne, ale používame aproximácie, ktoré sú veľmi užitočné aj v modernom ML.