Kolmogorov komplexitet

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 14 april 2022; kontroller kräver 2 redigeringar .

I algoritmisk informationsteori är Kolmogorov- komplexiteten hos ett objekt (som en text) ett mått på de beräkningsresurser som krävs för att exakt definiera det objektet.

Kolmogorov-komplexitet är också känd som beskrivande komplexitet, Kolmogorov -Khaitin- komplexitet , stokastisk komplexitet , algoritmisk entropi eller algoritmisk komplexitet .

Uttrycker möjligheten till en fraktal beskrivning.

Tänk till exempel på två strängar som är 64 tecken långa och bara innehåller gemener och siffror:

abababababababababababababababababababababababababababababababababababababababab 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf

Den första raden har en enkel beskrivning på naturligt språk, nämligen ab 32 gånger , bestående av 10 tecken. Den andra raden har ingen uppenbar enkel beskrivning som använder samma teckenuppsättning förutom själva raden, som är 64 tecken lång.

Mer formellt är komplexiteten hos en sträng längden på beskrivningen av den strängen i något universellt beskrivningsspråk . Komplexitetens förmåga att förändras med avseende på valet av beskrivningsspråk diskuteras nedan. Det kan visas att Kolmogorov-komplexiteten för en sträng inte kan vara mer än några byte mer än längden på själva strängen. Strängar vars Kolmogorov-komplexitet beror på storleken på själva strängen anses inte vara komplexa.

Definition

För att definiera Kolmogorov-komplexiteten måste vi först definiera strängbeskrivningsspråket. Ett sådant beskrivningsspråk kan baseras på vilket programmeringsspråk som helst som Lisp , Pascal eller Java . Om är ett program vars utdata är strängen , då är en beskrivning av . Längden på beskrivningen är längden som en sträng. Under bestämning av längden , längden på subrutinerna som används i . Längden på en heltalskonstant som visas i är antalet bitar som krävs för att representera , vilket är (ungefär) . $P$ $x$ $P$ $x$ $P$ $P$ $P$ $n$ $P$ $n$ $\log _{2}n$

Vi kan alternativt välja en kodning för Turingmaskinen , där kodning är en funktion som mappar varje Turingmaskin till en bitsträng . Om det är en Turing-maskin som ger en sträng som indata , så är den kombinerade strängen en beskrivning för . Detta är ett teoretiskt tillvägagångssätt som är mer lämpat för att konstruera detaljerade formella bevis och som föredras i forskningslitteraturen. Binär lambdakalkyl kan ge den enklaste definitionen av komplexitet. I den här artikeln tar vi ett informellt förhållningssätt. $M$ $\langle M\rangle$ $M$ $w$ $x$ $\langle M\rangle w$ $x$

Varje rad har minst en beskrivning, det vill säga ett program $s$

funktion GenerateFixedString() returnerar s

Om beskrivningen , är av minsta längd, det vill säga den använder det minsta antalet tecken, kallas den minsta beskrivningen , och längden , det vill säga antalet tecken i denna beskrivning, är Kolmogorov-komplexiteten , . Symboliskt: $s$ $d(s)$ $s$ $d(s)$ $s$ $K(s)$

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

Låt oss överväga hur valet av beskrivningsspråk påverkar värdet av , och visa att effekten av att ändra beskrivningsspråket är begränsad. $K$

Teorem . Om och är komplexitetsfunktioner relaterade till beskrivningsspråk och , så finns det en konstant (beroende endast på språk och ) så att $K_1$ $K_{2}$ $L_{1}$ $L_{2}$ $c$ $L_{1}$ $L_{2}$

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

Bevis . Omvänt räcker det för att bevisa att det finns någon konstant sådan för alla bitsträngar $c$ $s$

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

Anta att det finns ett program på språket som fungerar som tolk för : $L_{1}$ $L_{2}$

function InterpretLanguage( string p )

var är språkprogrammet . Tolken kännetecknas av följande egenskap: $sid$ $L_{2}$

Returvärdet som ett resultat av arbete InterpretLanguagemed indata blir resultatet av arbetet .

sid

sid

Således, om är ett program på ett språk som är den minsta beskrivningen av , returnerar ( ) en sträng . Längden på denna beskrivning är summan: $P$ $L_{2}$ $s$ InterpretLanguage $P$ $s$ $s$

Längden på programmet InterpretLanguage, som kan tas som en konstant . $c$
Längden definierad av . $P$ $K_{2}(s)$

Detta bevisar den nödvändiga övre gränsen.

Historik och sammanhang

Algoritmisk informationsteori är ett område inom datavetenskap som studerar Kolmogorovs komplexitet och andra komplexa mått för strängar (eller andra datastrukturer ).

Idén med Kolmogorovs komplexitetsteori är baserad på en nyckelsats som först upptäcktes av Ray Solomonoff , som publicerade den 1960, och beskrev den i A Preliminary Report on a General Theory of Inductive Inference [1] som en del av hans uppfinning av algoritmisk sannolikhet . Han gav en mer fullständig beskrivning i sina publikationer "A Formal Theory of Inductive Inference" , del 1 och 2 i tidskriften Information and Control [2] [3] , gjord 1964.

Senare publicerade A. N. Kolmogorov självständigt detta teorem i tidskriften Information Transmission Problems [4] , Gregory Khaitin presenterade också detta teorem i tidskriften J. ACM" . Khaitins papper skickades i oktober 1966, reviderades i december 1968 och citerar både Solomonoffs och Kolmogorovs papper. [5]

Satsen säger att bland de algoritmer som återställer (avkodar) strängar från deras beskrivningar (koder) finns det en optimal. Denna algoritm för alla strängar ger samma korta koder som de som tillhandahålls av andra algoritmer, med skillnaden med en konstant beroende på algoritmen, men inte på själva strängen. Solomonoff använde denna algoritm och kodlängderna den gav för att bestämma den "universella sannolikheten" för strängar, på vilken induktiv slutledning av efterföljande tecken i en sträng kunde baseras. Kolmogorov använde detta teorem för att definiera flera strängfunktioner: komplexitet, slumpmässighet och information.

När Kolmogorov lärde sig om Solomonoffs arbete, kände han igen sin prioritet [6] . Under flera år var Solomonoffs arbete mer känt i Sovjetunionen än i väst. Det är dock vanligt i det vetenskapliga samfundet att associera denna typ av komplexitet med Kolmogorov, som talade om slumpmässighet i sekvenser, medan algoritmisk sannolikhet har blivit associerad med Solomonoff, som fokuserade på förutsägelse med hjälp av sin upptäckt av den universella förutsättningsfördelningen.

Det finns några andra varianter av Kolmogorovs komplexitet eller algoritmisk information. En av de mest använda är baserad på självbegränsande program och är främst associerad med L. A. Levin (1974). Ett axiomatiskt förhållningssätt till Kolmogorovs komplexitet baserat på Blooms (1967) axiom introducerades av M. Burgin (1982).

Vissa människor tror att namnet "Kolmogorov komplexitet" är ett exempel på Matteus-effekten [7] .

Huvudkonsekvenser

I följande resonemang menar vi strängens komplexitet . $K(s)$ $s$

Det är lätt att se att den minsta beskrivningen av en sträng inte kan vara större än själva strängen: programmet ovan GenerateFixedString, vars produktion är större med ett fast belopp. $s$ $s$

Teorem . Det finns en konstant sådan $c$

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

Oberäknelighet av Kolmogorovs komplexitet

Den första konsekvensen är att det inte finns något effektivt sätt att beräkna . $K$

Teorem . är en oberäkningsbar funktion . $K$

Med andra ord är problemet med att beräkna den algoritmiska komplexiteten för en godtycklig sträng algoritmiskt olösligt - det finns inget program som skulle ta ett heltal som in- och utmatning . Låt oss visa detta med en motsägelse genom att skapa ett program som skapar en sträng som bara kan skapas av ett längre program. Anta att det finns ett program $s$ $s$ $K(s)$

funktion KolmogorovKomplexitet( sträng s )

som tar som input och returnerar . Överväg nu programmet $s$ $K(s)$

funktion GenerateComplexString( int n ) för i = 1 till oändligt: för varje sträng med längd exakt i om KolmogorovComplexity( s ) >= n returnerar s quit

Detta program anropar en subrutin KolmogorovComplexity. Programmet försöker varje rad, med början med den kortaste, tills det hittar en rad med minsta komplexitet , som det returnerar. Därför, givet ett positivt heltal , producerar det en sträng med Kolmogorov-komplexitet åtminstone . Detta program har sin egen fasta längd . Programinmatningen är ett heltal och storleken mäts med antalet bitar som behövs för att representera det, vilket är . Tänk sedan på följande program: $n$ $n$ $n$ $U$ GenerateComplexString $n$ $n$ $\log _{2}n$

funktion GenerateParadoxicalString() returnera GenerateComplexString(n 0 )

Detta program anropar GenerateComplexStringsom en subrutin och har även en ledig parameter . Detta program matar ut en sträng vars komplexitet är minst . Med ett gynnsamt val av parametern kommer vi fram till en motsägelse. För att välja detta värde, notera att det beskrivs av ett program vars längd inte är större än $n_{0}$ $s$ $n_{0}$ $n_{0}$ $s$ GenerateParadoxicalString

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

där konstanten läggs till på grund av programmet . Eftersom det växer snabbare än , så finns det ett värde som $C$ GenerateParadoxicalString $n$ $\log _{2}n$ $n_{0}$

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

Men detta motsäger definitionen att det finns en komplexitet av åtminstone . Det vill säga, per definition ( ), är det tillåtet att strängen som returneras av programmet GenerateParadoxicalString kan skapas av programmet med en längd eller större men kortare än . Så programmet kan faktiskt inte beräkna komplexiteten hos en slumpmässig sträng. $n_{0}$ $s$ $s$ $n_{0}$ GenerateParadoxicalString $n_{0}$ KolmogorovComplexity

Detta är ett motsägelsebevis, där motsägelsen liknar Berrys paradox : "Låt vara det minsta positiva heltal som inte kan kallas med mindre än tjugo engelska ord." [8] Det är också möjligt att visa icke-beräknelighet genom att reducera icke-beräknelighet till ett stoppande problem , eftersom och är Turing-ekvivalenta. [9] $n$ $K$ $H$ $K$ $H$

Det finns en följd i programmeringsgemenskapen känd som the full use theorem , som säger att det inte finns någon kompilator som är perfekt optimerad för storlek.

Kedjeregel för Kolmogorovs komplexitet

Kedjeregeln för Kolmogorovs komplexitet säger att

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

Den anger att det kortaste programmet som återger och högst är större än det program som återger , och det program som återger givet . Med hjälp av detta uttryck kan man definiera en analog av ömsesidig information för Kolmogorov-komplexiteten. $X$ $Y$ $\log K(X,Y)$ $X$ $Y$ $X$

Komprimering

Det är enkelt att beräkna den övre gränsen för : du behöver bara komprimera strängen med någon metod, implementera lämplig dekomprimerare på det valda språket, ansluta dekomprimeraren till den komprimerade strängen och mäta längden på den resulterande strängen. $K(s)$ $s$

Strängen komprimeras av om den har en beskrivning vars längd inte överstiger . Detta motsvarar ett uttalande . Om detta inte görs komprimeras det inte av . En sträng som inte är komprimerbar med 1 kallas helt enkelt inkompressibel; enligt Dirichlets princip måste inkompressibla strängar existera, eftersom det finns bitsträngar med längd , men bara strängar med längd mindre än [10] . $s$ $c$ $|s|-c$ $K(s)\leqslant |s|-c$ $s$ $c$ $2^{n}$ $n$ $2^{n}-1$ $n$

Av samma anledning är de flesta strängar komplexa i den meningen att de inte kan komprimeras avsevärt: inte mycket mindre än längden i bitar. För att förtydliga, låt oss fixa värdet på . Det finns bitsträngar av längd . Den enhetliga sannolikhetsfördelningen över utrymmet för dessa bitsträngar bestäms av exakt lika med viktningsfaktorn för varje längdsträng . $K(s)$ $|s|$ $s$ $n$ $2^{n}$ $n$ $2^{{-n}}$ $n$

Teorem . Sannolikheten att en sträng inte är komprimerad är åtminstone lika med en enhetlig sannolikhetsfördelning över utrymmet av bitsträngar av längd . $c$ ${\displaystyle 1-2^{-c+1}+2^{-n))$ $n$

För att bevisa detta teorem, noterar vi att antalet längdbeskrivningar inte överstiger , erhållet från en geometrisk progression : $n.c.$

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

Åtminstone kvar

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

bitsträngar som är inkompressibla på . Dividera med för att bestämma sannolikheten . $c$ $2^{n}$

Khaitins ofullständighetsteorem

Vi vet att i mängden av alla möjliga strängar är de flesta strängar komplexa i den meningen att de inte kan beskrivas på något tillräckligt kortfattat sätt. Det visar sig dock att det faktum att en viss sträng är komplex inte kan bevisas formellt om strängens komplexitet ligger över en viss tröskel. Den exakta formaliseringen presenteras nedan. Till att börja med fixar vi ett särskilt axiomatiskt system för naturliga tal . Det axiomatiska systemet måste vara tillräckligt kraftfullt så att en korrekt bedömning av en strängs komplexitet kan mappas till en formel i det axiomatiska systemet . Denna korrespondens måste ha följande egenskap: om den härleds från axiomen är motsvarande proposition sann. ${\mathbf {s}}$ $\mathbf {A}$ ${\mathbf {F}}_{{\mathbf {A}}}$ $s$ ${\mathbf {F}}_{{\mathbf {A}}}$ ${\mathbf {s}}$ $\mathbf {A}$

Teorem . Det finns en sådan konstant (som bara beror på ett visst axiomatiskt system och det valda beskrivningsspråket) att för varje rad uttalandet $L$

K(s)\geqslant L

kan inte bevisas inom . ${\mathbf {s}}$

Men som är lätt att förstå kommer påståendet att vara sant för ett oändligt antal rader, eller snarare för alla utom ett ändligt antal rader. $K(s)\geqslant L$

Beviset för satsen är baserat på den självrefererande konstruktionen som används i Berrys paradox . Bevis genom motsägelse. Om satsen inte är sann, då

Antagande (X) : För vilket heltal som helst finns det en sträng för vilken det finns en härledning av formeln " " (för vilken vi antog att den kan formaliseras i ).

n

s

{\mathbf {s}}

K(s)\geqslant n

{\mathbf {s}}

Överväg ett program som implementerar en effektiv uppräkning av alla formella bevis i ${\mathbf {s}}$

funktion NthProof( int n )

som tar n som indata och ger några bevis. Några av dem bevisar en formel som " ", där s och n är konstanter i språket . Det finns ett program som kontrollerar om det n :te beviset bevisar formeln " ": $K(s)\geqslant n$ ${\mathbf {s}}$ $K(s)\geqslant L$

function NthProofProvesComplexityFormula( int n )

Omvänt kan strängen s och talet L beräknas av programmen

funktion StringNthProof( int n ) funktion Komplexitet Nedre gränsN:teBevis( int n )

Tänk nu på följande program:

funktion GenerateProvablyComplexString( int n ) för i = 1 till oändlighet: if NthProofProvesComplexityFormula(i) och ComplexityLowerBoundNthProof(i) ≥ n return StringNthProof( i )

Givet n som indata , kontrollerar detta program varje bevis tills det hittar några strängar och ett bevis på formeln K ( s ) ≥L för några L ≥n . Detta program stannar vid Gissa (X) . Låt detta program ha längden U . Det finns ett tal n 0 så att U + log 2 n 0 + C < n 0 , där C är den extra längden av programmet

funktion GenerateProvablyParadoxicalString() return GenerateProvablyComplexString( n 0 )

Observera att numret n 0 också är kodat i detta program, vilket kräver logg 2 ( n 0 ) information. Programmet GenerateProvablyParadoxicalString producerar en sträng s för vilken det finns ett L så att K ( s ) ≥L kan slutas till , där L ≥n 0 . I synnerhet är K ( s ) ≥n 0 sant för det . Emellertid kan s beskrivas av ett program med längden U + log 2n 0 + C , så dess komplexitet är mindre än n 0 . Den resulterande motsägelsen bevisar att antagandet (X) är falskt . ${\mathbf {s}}$

Liknande idéer används för att bevisa egenskaperna hos Chaitins konstant .

Minsta meddelandelängd

Principen om minsta meddelandelängd i statistisk och induktiv slutledning och maskininlärning utvecklades av Wallace ( engelsk CS Wallace ) och Bolton ( engelsk DM Boulton ) 1968. MDS-principen är Bayesiansk (inkluderar tidigare sannolikheter) och informationsteoretisk. Den har de önskvärda egenskaperna statistisk invarians (inferenstransformerar med omparametrisering), statistisk anslutning (även för ett mycket svårt problem kommer principen att konvergera till den underliggande modellen) och effektivitet (en modell baserad på MDS-principen kommer att konvergera till alla giltiga underliggande modell så snabbt som möjligt). Wallace och Dowe ( eng. DL Dowe ) visade ett formellt samband mellan MDS-principen och algoritmisk informationsteori (eller Kolmogorov-komplexitet).

Kolmogorovs chans

Enligt definitionen av Kolmogorovs slumpmässighet (även algoritmisk slumpmässighet) sägs en sträng vara slumpmässig om och endast om den är kortare än något datorprogram som kan återskapa den. För att göra denna definition exakt måste en universell dator (eller en universell Turing-maskin ) fixeras, så att "datorprogram" skulle betyda programmet för den universella maskinen. Slumpmässigt i denna mening kommer strängen att vara "okomprimerbar". Genom att använda Dirichlet-principen är det lätt att visa att det för vilken universell maskin som helst finns algoritmiskt slumpmässiga strängar av vilken längd som helst, men egenskapen hos en sträng att vara algoritmiskt slumpmässig beror på valet av den universella maskinen.

Denna definition kan utökas till oändliga sekvenser av tecken från ett ändligt alfabet. Definitionen kan anges på tre likvärdiga sätt. Det första sättet använder en effektiv analog till måttteori; den andra använder en effektiv martingal . Det tredje sättet att definiera det är detta: en oändlig sekvens är slumpmässig om Kolmogorov-komplexiteten för dess initiala segment växer tillräckligt snabbt - det finns en konstant c så att komplexiteten för ett initialt segment med längden n är åtminstone n − c . Det visar sig att denna definition, till skillnad från definitionen av ändlig strängslumpmässighet, inte beror på valet av den universella maskinen.

Relation till entropi

Enligt Brudno-satsen är entropin i ett dynamiskt system och den algoritmiska komplexiteten för banor i det relaterad av relationen för nästan alla . [elva] $K(x;T)=h(T)$ $x$

Det kan visas [12] att Kolmogorov-komplexiteten i resultatet av arbetet med en Markov-informationskälla är relaterad till dess entropi . Närmare bestämt konvergerar Kolmogorov-komplexiteten hos utmatningen av en Markov-informationskälla, normaliserad till utmatningens längder, nästan alltid till källans entropi.

Anteckningar

↑ Solomonoff, Ray A Preliminary Report on a General Theory of Inductive Inference // Rapport V-131 : journal. - Cambridge, Ma.: Zator Co., 1960. - 4 februari. revision Arkiverad1 augusti 2020 påWayback Machine, november 1960.
↑ Solomonoff, Ray. En formell teori om induktiv slutledning Del I // Information och kontroll : journal. - 1964. - Mars ( vol. 7 , nr 1 ). - S. 1-22 . - doi : 10.1016/S0019-9958(64)90223-2 .
↑ Solomonoff, Ray. En formell teori om induktiv slutledning Del II // Information och kontroll : journal. - 1964. - Juni ( vol. 7 , nr 2 ). - S. 224-254 . - doi : 10.1016/S0019-9958(64)90131-7 .
↑ Kolmogorov, A. N. Tre tillvägagångssätt för definitionen av begreppet "mängd information" // Problem med informationsöverföring: journal. - 1965. - T. 1 , nr 1 . - S. 3-11 . (ryska)
↑ Chaitin, Gregory J. Om enkelheten och hastigheten hos program för att beräkna oändliga uppsättningar av naturliga tal // Journal of the ACM : journal. - 1969. - Vol. 16 . - S. 407 . - doi : 10.1145/321526.321530 . Arkiverad från originalet den 25 augusti 2011.
↑ Kolmogorov, A. Logisk grund för informationsteori och sannolikhetsteori (engelska) // IEEE Transactions on Information Theory : journal. - 1968. - Vol. 14 , nr. 5 . - s. 662-664 . - doi : 10.1109/TIT.1968.1054210 .
↑ Li, Ming; Paul Vitani. En introduktion till Kolmogorovs komplexitet och dess tillämpningar . — 2:a. - Springer, 1997. - ISBN 0387948686 .
↑ Original: "Låt vara det minsta positiva heltal som inte kan definieras i färre än tjugo engelska ord". $n$
↑ Peter Bro Miltersen. Kursanteckningar för datakomprimering. 2. Kolmogorovs komplexitet (otillgänglig länk) . Hämtad 17 februari 2011. Arkiverad från originalet 9 september 2009. (obestämd)
↑ Eftersom det finns strängar av längd , är antalet strängar av längd , vilket är en ändlig geometrisk progression med summa lika med . $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$
↑ Arkiverad kopia . Hämtad 6 juni 2013. Arkiverad från originalet 26 december 2011. (obestämd)
↑ http://arxiv.org/pdf/cs.CC/0404039

Litteratur

Vereshchagin N.K. Kolmogorovs komplexitetsförlopp .
Vereshchagin N. K., Shen V. A. Kolmogorov komplexitet och algoritmisk slumpmässighet . — MTsNMO, 2013.
Vyugin VV Kolmogorov komplexitet och algoritmisk slumpmässighet .

Ordböcker och uppslagsverk	stor kines Universalis