Kolmogorovova složitost

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 14. dubna 2022; kontroly vyžadují 2 úpravy .

V teorii algoritmické informace je Kolmogorovova složitost objektu (jako je text) mírou výpočetních zdrojů požadovaných k přesné definici toho objektu.

Kolmogorovova složitost je také známá jako deskriptivní složitost, Kolmogorovova – Khaitinova složitost , stochastická složitost , algoritmická entropie nebo algoritmická složitost .

Vyjadřuje možnost fraktálního popisu.

Uvažujme například dva řetězce, které jsou dlouhé 64 znaků a obsahují pouze malá písmena a čísla:

abababababababababababababababababababababababababababababababab 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf

Na prvním řádku je jednoduchý popis v přirozeném jazyce, konkrétně ab 32 krát , skládající se z 10 znaků. Druhý řádek nemá žádný zřejmý jednoduchý popis používající stejnou znakovou sadu, kromě samotného řádku, který je dlouhý 64 znaků.

Více formálně, složitost řetězce je délka popisu tohoto řetězce v nějakém univerzálním popisném jazyce . Schopnost změny složitosti s ohledem na volbu jazyka popisu je diskutována níže. Lze ukázat, že Kolmogorovova složitost jakéhokoli řetězce nemůže být o více než několik bajtů větší než délka samotného řetězce. Struny, jejichž složitost podle Kolmogorova slabě závisí na velikosti samotné struny, nejsou považovány za složité.

Definice

Abychom mohli definovat Kolmogorovovu složitost, musíme nejprve definovat jazyk popisu řetězce. Takový popisný jazyk může být založen na jakémkoli programovacím jazyce , jako je Lisp , Pascal nebo Java . If je program, jehož výstupem je řetězec , pak je popis . Délka popisu je délka jako řetězec. V průběhu určování délky se délky podprogramů používaných v . Délka jakékoli celočíselné konstanty , která se objeví v, je počet bitů potřebných k reprezentaci , což je (zhruba) . $P$ $X$ $P$ $X$ $P$ $P$ $P$ $n$ $P$ $n$ $\log _{2}n$

Alternativně můžeme zvolit kódování pro Turingův stroj , kde kódování je funkce, která mapuje každý Turingův stroj na bitový řetězec . Jestliže je Turingův stroj, který dává řetězec jako vstup , pak kombinovaný řetězec je popisem pro . Toto je teoretický přístup, který je vhodnější pro konstrukci podrobných formálních důkazů a je preferován ve výzkumné literatuře. Binární lambda počet může poskytnout nejjednodušší definici složitosti. V tomto článku jsme zvolili neformální přístup. $M$ $\langle M\rangle$ $M$ $w$ $X$ $\langle M\rangle w$ $X$

Každý řádek má alespoň jeden popis, tedy program $s$

funkce GenerateFixedString() vrátí s

Pokud má popis minimální délku , to znamená, že používá nejmenší počet znaků, pak se nazývá minimální popis a délka , tedy počet znaků v tomto popisu, je Kolmogorovova složitost , . Symbolicky: $s$ $d(y)$ $s$ $d(y)$ $s$ $K(s)$

K(s)=|d(s)|.

Uvažujme, jak výběr jazyka popisu ovlivňuje hodnotu , a ukažme, že účinek změny jazyka popisu je omezený. $K$

Věta . Jestliže a jsou funkce složitosti související s popisnými jazyky a , pak existuje konstanta (v závislosti pouze na jazycích a ), taková, že $K_1$ $K_{2}$ $L_{1}$ $L_{2}$ $C$ $L_{1}$ $L_{2}$

\forall s|K_{1}(s)-K_{2}(s)|\leqslant c.

Důkaz . Naopak stačí dokázat, že existuje nějaká konstanta taková, že pro všechny bitové řetězce $C$ $s$

K_{1}(s)\leqslant K_{2}(s)+c.

Předpokládejme, že v jazyce existuje program , který funguje jako tlumočník pro : $L_{1}$ $L_{2}$

funkce InterpretLanguage( řetězec p )

kde je jazykový program . Interpret se vyznačuje následující vlastností: $p$ $L_{2}$

Návratová hodnota jako výsledek práce InterpretLanguagena vstupních datech bude výsledkem práce .

p

p

Pokud je tedy program v jazyce , který je minimálním popisem , pak ( ) vrací řetězec . Délka tohoto popisu je součet: $P$ $L_{2}$ $s$ InterpretLanguage $P$ $s$ $s$

Délka programu InterpretLanguage, kterou lze brát jako konstantu . $C$
Délka definovaná pomocí . $P$ $K_{2}(y)$

To dokazuje požadovanou horní hranici.

Historie a kontext

Algoritmická teorie informace je obor počítačové vědy, který studuje Kolmogorovovu složitost a další komplexní míry pro řetězce (nebo jiné datové struktury ).

Myšlenka Kolmogorovovy teorie složitosti je založena na klíčové větě poprvé objevené Rayem Solomonoffem , který ji publikoval v roce 1960 a popsal ji v A Preliminary Report on a General Theory of Inductive Inference [1] jako součást svého vynálezu algoritmické pravděpodobnosti. . Podrobnější popis podal ve svých publikacích „A Formal Theory of Inductive Inference“ , část 1 a 2 v časopise Information and Control [2] [3] , vydaném v roce 1964.

Později A. N. Kolmogorov nezávisle publikoval tuto větu v časopise Information Transmission Problems [4] , Gregory Khaitin také prezentoval tuto větu v časopise J. ACM" . Khaitinův dokument byl odeslán v říjnu 1966, revidován v prosinci 1968 a cituje jak Solomonoffovy, tak Kolmogorovovy dokumenty. [5]

Věta říká, že mezi algoritmy, které obnovují (dekódují) řetězce z jejich popisů (kódů), existuje jeden optimální. Tento algoritmus pro všechny řetězce poskytuje stejné krátké kódy jako ty, které poskytují jiné algoritmy, s rozdílem konstanty v závislosti na algoritmu, ale ne na samotném řetězci. Solomonoff použil tento algoritmus a délky kódu, které poskytoval, k určení „univerzální pravděpodobnosti“ řetězců, na kterých by mohla být založena induktivní inference následných znaků v řetězci. Kolmogorov použil tento teorém k definování několika řetězcových funkcí: složitost, náhodnost a informace.

Když se Kolmogorov dozvěděl o Solomonoffově práci, uznal jeho prioritu [6] . Po několik let bylo Solomonoffovo dílo známější v SSSR než na Západě. Ve vědecké komunitě je však běžné spojovat tento typ složitosti s Kolmogorovem, který mluvil o náhodnosti sekvencí, zatímco algoritmická pravděpodobnost se stala spojenou se Solomonoffem, který se zaměřil na predikci pomocí svého objevu univerzálního předchozího rozdělení pravděpodobnosti.

Existují některé další varianty Kolmogorovovy složitosti nebo algoritmické informace. Jeden z nejpoužívanějších je založen na sebeomezujících programech a je spojen především s L. A. Levinem (1974). Axiomatický přístup ke Kolmogorovově složitosti založený na Bloomových (1967) axiomech představil M. Burgin (1982).

Někteří lidé si myslí, že název „Kolmogorovova složitost“ je příkladem Matthewova efektu [7] .

Hlavní důsledky

V následující úvaze máme na mysli složitost řetězce . $K(s)$ $s$

Je snadné vidět, že minimální popis řetězce nemůže být větší než samotný řetězec: výše uvedený program GenerateFixedString, jehož výstup je větší o pevnou hodnotu. $s$ $s$

Věta . Existuje konstanta taková, že $C$

\forall s\,K(s)\leqslant |s|+c.

Nevyčíslitelnost Kolmogorovovy složitosti

Prvním důsledkem je, že neexistuje žádný účinný způsob výpočtu . $K$

Věta . je nevyčíslitelná funkce . $K$

Jinými slovy, problém výpočtu algoritmické složitosti libovolného řetězce je algoritmicky neřešitelný – neexistuje žádný program, který by bral jako vstup a výstup celé číslo . Ukažme si to s kontradikcí vytvořením programu, který vytvoří řetězec, který může vytvořit pouze delší program. Předpokládejme, že existuje program $s$ $s$ $K(s)$

funkce KolmogorovSložitost( řetězce s )

který bere jako vstup a vrací . Nyní zvažte program $s$ $K(s)$

funkce GenerateComplexString( int n ) for i = 1 až nekonečno: pro každý řetězec s délky přesně i, pokud KolmogorovComplexity( s ) >= n return s quit

Tento program volá podprogram KolmogorovComplexity. Program zkouší každý řádek, počínaje tím nejkratším, dokud nenajde řádek se složitostí alespoň , který vrátí. Proto, zadané kladné celé číslo , vytváří řetězec s Kolmogorovovou složitostí alespoň . Tento program má svou pevnou délku . Vstup programu je celé číslo a velikost se měří počtem bitů potřebných k jeho reprezentaci, což je . Dále zvažte následující program: $n$ $n$ $n$ $U$ GenerateComplexString $n$ $n$ $\log _{2}n$

funkce GenerateParadoxicalString() return GenerateComplexString(n 0 )

Tento program volá GenerateComplexStringjako podprogram a má také volný parametr . Tento program vypíše řetězec, jehož složitost je nejméně . Příznivou volbou parametru se dostáváme k rozporu. Chcete-li zvolit tuto hodnotu, všimněte si, že je popsána programem, jehož délka není větší než $n_{0}$ $s$ $n_{0}$ $n_{0}$ $s$ GenerateParadoxicalString

U+\log _{2}n_{0}+C,

kde je konstanta přidána kvůli programu . Protože roste rychleji než , existuje hodnota taková, že $C$ GenerateParadoxicalString $n$ $\log _{2}n$ $n_{0}$

U+\log _{2}n_{0}+C<n_{0}.

Ale to je v rozporu s definicí, že existuje složitost alespoň . To znamená, že podle definice ( ) je povoleno, aby řetězec vrácený programem GenerateParadoxicalString mohl být vytvořen programem s délkou nebo větší, ale kratší než . Program tedy ve skutečnosti nedokáže vypočítat složitost náhodného řetězce. $n_{0}$ $s$ $s$ $n_{0}$ GenerateParadoxicalString $n_{0}$ KolmogorovComplexity

Toto je důkaz kontradikcí, kde je rozpor podobný Berryho paradoxu : "Let být nejmenší kladné celé číslo, které nelze nazvat méně než dvaceti anglickými slovy." [8] Je také možné ukázat nevyčíslitelnost snížením nevyčíslitelnosti na problém zastavení , protože a jsou Turingově ekvivalentní. [9] $n$ $K$ $H$ $K$ $H$

V programátorské komunitě existuje důsledek známý jako teorém plného použití , který uvádí, že neexistuje žádný kompilátor, který by byl dokonale optimalizován pro velikost.

Řetězové pravidlo pro Kolmogorovovu složitost

Řetězové pravidlo pro Kolmogorovovu složitost to říká

K(X,Y)=K(X)+K(Y\mid X)+O{\big (}\log K(X,Y){\big )}.

Uvádí, že nejkratší program, který reprodukuje a je nanejvýš větší než program, který reprodukuje , a daný program, který reprodukuje . Pomocí tohoto výrazu lze definovat analogii vzájemné informace pro Kolmogorovovu složitost. $X$ $Y$ $\log K(X,Y)$ $X$ $Y$ $X$

Komprese

Výpočet horní hranice pro je snadný: stačí zkomprimovat řetězec pomocí nějaké metody, implementovat příslušný dekompresor ve zvoleném jazyce, připojit dekompresor ke komprimovanému řetězci a změřit délku výsledného řetězce. $K(s)$ $s$

Řetězec je komprimován, pokud má popis, jehož délka nepřesahuje . To je ekvivalentní prohlášení . Pokud se tak nestane, nebude komprimován pomocí . Řetězec, který není stlačitelný o 1, se jednoduše nazývá nestlačitelný; podle Dirichletova principu musí existovat nestlačitelné řetězce , protože existují bitové řetězce délky , ale pouze řetězce délky menší než [10] . $s$ $C$ $|s|-c$ $K(s)\leqslant |s|-c$ $s$ $C$ $2^{n}$ $n$ $2^{n}-1$ $n$

Ze stejného důvodu je většina řetězců složitá v tom smyslu, že je nelze výrazně komprimovat: ne o moc menší, než je délka v bitech. Abychom to objasnili, opravme hodnotu . Existují bitové řetězce délky . Rovnoměrné rozdělení pravděpodobnosti v prostoru těchto bitových řetězců je určeno přesně rovným váhovému faktoru pro každý řetězec délky . $K(s)$ $|s|$ $s$ $n$ $2^{n}$ $n$ $2^{{-n}}$ $n$

Věta . Pravděpodobnost, že řetězec není komprimován, je přinejmenším rovna rovnoměrnému rozdělení pravděpodobnosti v prostoru bitových řetězců délky . $C$ ${\displaystyle 1-2^{-c+1}+2^{-n))$ $n$

Abychom tuto větu dokázali, poznamenáme, že počet popisů délek nepřesahuje , získané z geometrické posloupnosti : $n.c.$

1+2+2^{2}+\ldots +2^{nc}=2^{n-c+1}-1.

Zůstává minimálně

2^{n}-2^{n-c+1}+1

bitové řetězce, které jsou na . Dělením určíte pravděpodobnost . $C$ $2^{n}$

Khaitinův teorém neúplnosti

Víme, že v množině všech možných řetězců je většina řetězců složitých v tom smyslu, že je nelze nijak dostatečně výstižně popsat. Ukazuje se však, že skutečnost, že konkrétní řetězec je složitý, nelze formálně prokázat, pokud je složitost řetězce nad určitou prahovou hodnotou. Přesná formalizace je uvedena níže. Nejprve si stanovíme konkrétní axiomatický systém pro přirozená čísla . Axiomatický systém musí být dostatečně silný, aby přesný úsudek o složitosti řetězce mohl být mapován na vzorec v axiomatickém systému . Tato korespondence musí mít následující vlastnost: pokud je odvozena z axiomů , pak je odpovídající tvrzení pravdivé. ${\mathbf {s))$ $\mathbf {A}$ ${\mathbf {F}}_{{\mathbf {A}}}$ $s$ ${\mathbf {F}}_{{\mathbf {A}}}$ ${\mathbf {s))$ $\mathbf {A}$

Věta . Existuje taková konstanta (která závisí pouze na konkrétním axiomatickém systému a zvoleném jazyku popisu), že pro libovolný řádek je příkaz $L$

K(s)\geqslant L

nelze v rámci . ${\mathbf {s))$

Jak je však snadné pochopit, tvrzení bude platit pro nekonečný počet řádků, nebo spíše pro všechny řádky kromě konečného počtu. $K(s)\geqslant L$

Důkaz teorému je založen na sebereferenční konstrukci použité v Berryho paradoxu . Důkaz kontradikcí. Pokud teorém není pravdivý, pak

Předpoklad (X) : Pro jakékoli celé číslo existuje řetězec, pro který existuje odvození vzorce " " (u kterého jsme předpokládali, že jej lze formalizovat v ).

n

s

{\mathbf {s))

K(s)\geqslant n

{\mathbf {s))

Zvažte program, který implementuje efektivní výčet všech formálních důkazů ${\mathbf {s))$

funkce NthProof( int n )

který bere n jako vstup a vytváří nějaký důkaz. Některé z nich dokazují formuli jako " ", kde s a n jsou konstanty v jazyce . Existuje program, který kontroluje, zda n-tý důkaz dokazuje vzorec " ": $K(s)\geqslant n$ ${\mathbf {s))$ $K(s)\geqslant L$

funkce NthProofProvesComplexityFormula( int n )

Naopak řetězec s a číslo L mohou programy vypočítat

funkce StringNthProof( int n ) funkce ComplexityLowerBoundNthProof( int n )

Zvažte nyní následující program:

funkce GenerateProvablyComplexString( int n ) pro i = 1 do nekonečna: if NthProofProvesComplexityFormula(i) a ComplexityLowerBoundNthProof(i) ≥ n return StringNthProof( i )

Dané n jako vstup , tento program kontroluje každý důkaz, dokud nenajde nějaký řetězec s a důkaz vzorce K ( s ) ≥ L pro nějaké L ≥ n . Tento program se zastaví na Guess (X) . Nechť má tento program délku U . Existuje číslo n 0 takové, že U + log 2 n 0 + C < n 0 , kde C je dodatečná délka programu

funkce GenerateProvablyParadoxicalString() return GenerateProvablyComplexString( n 0 )

Všimněte si, že v tomto programu je také zakódováno číslo n 0 , které vyžaduje informace log 2 ( n 0 ). Program GenerateProvablyParadoxicalString vytvoří řetězec s, pro který existuje L takové, že lze odvodit K ( s ) ≥ L , kde L ≥ n 0 . Konkrétně pro něj platí K ( s ) ≥ n 0 . S lze však popsat programem délky U + log 2 n 0 + C , takže jeho složitost je menší než n 0 . Výsledný rozpor dokazuje nepravdivost předpokladu (X) . ${\mathbf {s))$

Podobné myšlenky se používají k prokázání vlastností Chaitinovy konstanty .

Minimální délka zprávy

Princip minimální délky zprávy ve statistické a induktivní inferenci a strojovém učení vyvinuli Wallace ( anglicky CS Wallace ) a Bolton ( anglicky DM Boulton ) v roce 1968. Princip MDS je bayesovský (zahrnuje předchozí pravděpodobnosti) a informačně teoretický. Má žádoucí vlastnosti statistické invariance (odvozování se transformuje reparametrizací), statistické konektivity (i u velmi obtížného problému bude princip konvergovat k základnímu modelu) a účinnosti (model založený na principu MDS bude konvergovat k jakémukoli platnému základní model co nejrychleji). Wallace a Dowe ( angl. DL Dowe ) ukázali formální vztah mezi principem MDS a algoritmickou teorií informace (nebo Kolmogorovovou složitostí).

Kolmogorovova šance

Podle definice Kolmogorovovy náhodnosti (také algoritmické náhodnosti) se řetězec považuje za náhodný právě tehdy, když je kratší než jakýkoli počítačový program schopný jej reprodukovat. Aby byla tato definice přesná, univerzální počítač (nebo univerzální Turingův stroj ) musí být opraven, takže „počítačový program“ by znamenal program pro tento univerzální stroj. Náhodný v tomto smyslu bude řetězec "nestlačitelný". Pomocí Dirichletova principu je snadné ukázat, že pro jakýkoli univerzální stroj existují algoritmicky náhodné řetězce libovolné délky, ale vlastnost řetězce být algoritmicky náhodný závisí na volbě univerzálního stroje.

Tuto definici lze rozšířit na nekonečné sekvence znaků z konečné abecedy. Definici lze vyjádřit třemi ekvivalentními způsoby. První způsob využívá efektivní analogii teorie míry; druhý používá účinný martingal . Třetí způsob, jak ji definovat, je tento: nekonečná posloupnost je náhodná, pokud Kolmogorovova složitost jejího počátečního segmentu roste dostatečně rychle — existuje konstanta c taková, že složitost jakéhokoli počátečního segmentu délky n je alespoň n − c . Ukazuje se, že tato definice, na rozdíl od definice náhodnosti konečných řetězců, nezávisí na volbě univerzálního stroje.

Vztah k entropii

Podle Brudnova teorému souvisí entropie dynamického systému a algoritmická složitost trajektorií v něm vztahem téměř pro všechny . [jedenáct] $K(x;T)=h(T)$ $X$

Lze ukázat [12] , že Kolmogorovova složitost výsledku práce Markovova zdroje informací souvisí s jeho entropií . Přesněji řečeno, Kolmogorovova složitost výstupu Markovova zdroje informací, normalizovaná na délky výstupu, konverguje téměř vždy k entropii zdroje.

Poznámky

↑ Solomonoff, Ray Předběžná zpráva o obecné teorii induktivní inference // Zpráva V-131: časopis. - Cambridge, Ma.: Zator Co., 1960. - 4. února. revize Archivováno1. srpna 2020 naWayback Machine, listopad 1960.
↑ Solomonoff, Ray. Formální teorie induktivní inference Část I // Informace a řízení : deník. - 1964. - březen ( roč. 7 , č. 1 ). - str. 1-22 . - doi : 10.1016/S0019-9958(64)90223-2 .
↑ Solomonoff, Ray. Formální teorie induktivní inference Část II // Informace a řízení : deník. - 1964. - Červen ( 7. díl , č. 2 ). - str. 224-254 . - doi : 10.1016/S0019-9958(64)90131-7 .
↑ Kolmogorov, A. N. Tři přístupy k definici pojmu „množství informací“ // Problémy přenosu informací: časopis. - 1965. - T. 1 , č. 1 . - S. 3-11 . (Ruština)
↑ Chaitin, Gregory J. O jednoduchosti a rychlosti programů pro počítání nekonečných množin přirozených čísel // Journal of the ACM : journal. - 1969. - Sv. 16 . - str. 407 . - doi : 10.1145/321526.321530 . Archivováno z originálu 25. srpna 2011.
↑ Kolmogorov, A. Logický základ pro teorii informace a teorii pravděpodobnosti (anglicky) // IEEE Transactions on Information Theory : deník. - 1968. - Sv. 14 , č. 5 . - S. 662-664 . - doi : 10.1109/TIT.1968.1054210 .
↑ Li, Ming; Pavel Vitani. Úvod do Kolmogorovovy komplexity a jejích aplikací . — 2. - Springer, 1997. - ISBN 0387948686 .
↑ Originál: "Let být nejmenší kladné celé číslo, které nemůže být definováno v méně než dvaceti anglických slovech". $n$
↑ Peter Bro Miltersen. Poznámky ke kurzu pro kompresi dat. 2. Kolmogorovova složitost (nepřístupný odkaz) . Získáno 17. února 2011. Archivováno z originálu 9. září 2009. (neurčitý)
↑ Protože existují řetězce délky , počet řetězců délky je , což je konečná geometrická progrese se součtem rovným . $n_{L}=2^{L}$ $L$ $L=0,\ldots ,(n-1)$ ${\displaystyle n_{0}+n_{1}+\ldots +n_{n-1}=2^{0}+2^{1}+\ldots +2^{n-1))$ $2^{0}+2^{1}+\ldots +2^{n-1}=2^{0}\times (1-2^{n})/(1-2)=2 ^{n}-1$
↑ Archivovaná kopie . Získáno 6. června 2013. Archivováno z originálu dne 26. prosince 2011. (neurčitý)
↑ http://arxiv.org/pdf/cs.CC/0404039

Literatura

Vereshchagin N.K. Průběh složitosti Kolmogorova .
Vereshchagin N. K., Shen V. A. Kolmogorov složitost a algoritmická náhodnost . — MTsNMO, 2013.
Vyugin VV Kolmogorov složitost a algoritmická náhodnost .

Slovníky a encyklopedie	velká čínština Universalis