Prostym językiem o koncepcji wyspecyfikowanej złożoności: informacja shannonowska i informacja kołmogorowskaCzas czytania: 11 min

W pierwszym wydaniu książki Wnioskowanie o projekcie¹ oraz w jej kontynuacji, czyli książce Nic za darmo², położyłem fundamenty pod ścisłą definicję miary wyspecyfikowanej złożoności w ujęciu teorii informacji. Należało jednak popracować jeszcze nad klarownym przedstawieniem tej koncepcji. W obu wspomnianych książkach wyspecyfikowana złożoność była traktowana jako połączenie małego prawdopodobieństwa bądź złożoności ze specyfikacją.

W tych książkach było to jak połączenie oleju z octem, ponieważ złożoność i specyfikacja były traktowane jako dwie różne rodzaje rzeczy i nie było jasne, co mają one ze sobą wspólnego. W żadnej z tych książek wyspecyfikowana złożoność nie była więc sformułowana jako zunifikowana miara informacji, chociaż przedstawiłem w nich kluczowe idee pozwalające na zdefiniowanie takiej miary. W niniejszym artykule omówię te kluczowe idee z zakresu teorii informacji. W kolejnym artykule połączę je w zunifikowaną całość.

Zacznijmy od zagadnienia złożoności. Jak zauważyłem w jednym z wcześniejszych artykułów, między prawdopodobieństwem a złożonością istnieje głęboki związek. Jasno uzmysławia to shannonowska teoria informacji. W ramach tej teorii prawdopodobieństwa przekształcane są na bity. Aby zrozumieć, jak to działa, rozważmy przykład 100 rzutów monetą, przy którym mamy do czynienia ze zdarzeniem o prawdopodobieństwie 1 na 2¹⁰⁰. Ta liczba odpowiada jednak również 100 bitom informacji, ponieważ do opisania dowolnego ciągu 100 rzutów monetą potrzebne jest 100 bitów („1” mogą oznaczać orły, a „0” – reszki).

Ogólnie rzecz biorąc, każdemu prawdopodobieństwu p odpowiada –log(p), przy czym należy pamiętać, że logarytm zawsze ma w takich przypadkach podstawę 2 (jest to konieczne do przekształcenia prawdopodobieństw w bity). Logarytm można uznać za wykładnik potęgi: jest to wykładnik potęgi, do którego trzeba podnieść podstawę (wynoszącą tutaj zawsze 2), aby otrzymać liczbę, do której stosuje się funkcja logarytmiczna. Na przykład prawdopodobieństwo p = 1/10 odpowiada mierze informacji –log(1/10) ≈ 3,322 bitu (równoważnie: 2^(–3,322) ≈ 1/10). Takie ułamkowe bity umożliwiają wyrażenie ścisłej korespondencji między prawdopodobieństwami a miarami informacji.

Złożoność w koncepcji wyspecyfikowanej złożoności jest więc informacją shannonowską. Claude Shannon (1916–2001)³ wprowadził tę ideę informacji w latach czterdziestych XX wieku. Miała ona pomóc w zrozumieniu transmisji sygnałów (głównie bitów, ale również innych ciągów znaków) przez kanały komunikacyjne. Im dłuższy ciąg bitów zostaje przekazany, tym większą niesie on ilość informacji, a więc tym większa jego złożoność.

Ponieważ w przypadku kanałów komunikacyjnych zawsze mamy do czynienia z szumem, więc im większa złożoność sygnału, tym większe szanse na jego zniekształcenie i tym większa potrzeba odpowiedniego zakodowania sygnału oraz odpowiedniej korekty błędów przy jego przekazywaniu. Złożoność przekazywanego ciągu bitów była więc ważnym elementem teorii Shannona.

Shannonowską miarę informacji łatwo rozszerzyć na każde zdarzenie E o prawdopodobieństwie P(E). Informację shannonowską w zdarzeniu E definiujemy wówczas jako –log(P(E)) = I(E). Zauważmy, że znak minusa występuje tutaj po to, aby zagwarantować, że w miarę zmniejszania się wartości prawdopodobieństwa E ilość informacji związanej z E będzie rosła. Tak właśnie powinno być. Informacja zawsze jest związana z zawężaniem możliwości. Im możliwości będą bardziej zawężone, tym bardziej będzie maleć prawdopodobieństwo związane z tymi możliwościami, a jednocześnie tym bardziej będzie rosnąć ilość informacji związanej z zawężaniem możliwości.

Rozważmy na przykład ciąg dziesięciu rzutów prawidłową monetą oraz dwa zdarzenia – E oraz F. Niech E denotuje zdarzenie, w którym przy pierwszych pięciu z tych dziesięciu rzutów moneta ukazuje orła, ale nie wiemy, jaki jest wynik pozostałych rzutów. Natomiast F niech denotuje zdarzenie, w którym przy wszystkich dziesięciu rzutach otrzymujemy orły. To jasne, że F zawęża zakres możliwości dla dziesięciu rzutów w większym stopniu niż E. Ponieważ w przypadku E znamy tylko wyniki pierwszych pięciu rzutów, więc jego prawdopodobieństwo wynosi P(E) = 2^(–5) = 1/2⁽⁵⁾ = 1/32. Natomiast w przypadku F znamy wyniki wszystkich dziesięciu rzutów, a w związku z tym jego prawdopodobieństwo wynosi P(F) = 2^(–10) = 1/2⁽¹⁰⁾ = 1/1024. W tej sytuacji ilość informacji shannonowskiej związanej z E oraz F wynosi – odpowiednio – I(E) = 5 bitów oraz I(F) = 10 bitów.

Idea informacji shannonowskiej nie wystarczy jednak do zrozumienia koncepcji wyspecyfikowanej złożoności. Potrzebujemy także idei informacji kołmogorowskiej, czyli tego, co nazywane jest złożonością Kołmogorowa. Andriej Kołmogorow (1903–1987)⁴ był największym probabilistą XX wieku. W latach sześćdziesiątych podjął próbę zrozumienia, co to znaczy, że dany ciąg liczb jest losowy. Aby nie komplikować sprawy, ale jednocześnie nie utracić nic na ogólności, skupię się na ciągach bitów (ponieważ wszystkie liczby lub znaki można przedstawić za pomocą kombinacji bitów). Zauważmy, że takie samo upraszczające założenie przyjąłem w odniesieniu do informacji shannonowskiej.

Kołmogorow rozważał problem polegający na tym, że każdy ciąg bitów traktowany jako wynik rzutów prawidłową monetą ma równe prawdopodobieństwo. Na przykład każdy ciąg 100 rzutów monetą ma prawdopodobieństwo 1/(2¹⁰⁰), co jest równe 100 bitom informacji shannonowskiej. Kołmogorow dostrzegał jednak ogromną różnicę między następującymi dwoma ciągami 100 rzutów monetą („0” denotuje reszki, a „1” – orły):

0000000000000000000000000

0000000000000000000000000

0000000000000000000000000

0000000000000000000000000

oraz

1001101111101100100010011

0001010001010010101110001

0101100000101011000100110

1100110100011000000110001

Pierwszy ciąg to po prostu stukrotne powtórzenie tego samego wyniku rzutu monetą. Nie wygląda on na losowy. Drugi ciąg nie wykazuje natomiast żadnego wyrazistego wzorca i dlatego wygląda na losowy (otrzymałem go przed chwilą za pomocą internetowego generatora losowych bitów). Co jednak mamy tutaj na myśli, używając słowa „losowy”? Czy chodzi o to, że otrzymania jednego z tych ciągów powinniśmy się spodziewać po rzutach monetą, a drugiego – nie? Jeśli tak, to w takim razie prawdopodobieństwa nie mówią nam nic o tym, jak odróżnić od siebie te dwa ciągi, ponieważ oba ciągi mają tak samo małe prawdopodobieństwo nastąpienia.

Błyskotliwym posunięciem Kołmogorowa było nadanie tym ciągom nie ujęcia probabilistycznego, lecz obliczeniowego. Co ciekawe, idee sformułowane przez Kołmogorowa wisiały w powietrzu w połowie lat sześćdziesiątych. Na to samo wpadli Ray Solomonoff⁵ oraz Gregory Chaitin⁶ (który wówczas był jeszcze nastolatkiem). Kołmogorow, być może niesprawiedliwie, otrzymał lwią część uznania za opracowanie obliczeniowego ujęcia losowości. Większość książek na temat teorii informacji⁷, omawiając to ujęcie losowości, koncentruje się na Kołmogorowie, a jego koncepcję określa mianem algorytmicznej teorii informacji.

Krótko mówiąc, zgodnie z zaproponowanym przez Kołmogorowa ujęciem losowości ciąg bitów jest losowy wówczas, gdy nie istnieje krótki program komputerowy, który ten ciąg by generował. Pierwszy z wyżej przedstawionych ciągów jest więc nielosowy, ponieważ generuje go bardzo krótki program – na przykład program wyglądający po prostu tak: „powtórz »0« sto razy”. O ile wiemy, nie istnieje natomiast żaden krótki program, który generowałby drugi ciąg.

Jest faktem kombinatorycznym⁸ (czyli faktem dotyczącym matematyki liczenia lub wyliczania możliwości), że ogromnej większości ciągów bitów nie da się scharakteryzować za pomocą programu krótszego od samego konkretnego ciągu. Każdy ciąg da się oczywiście scharakteryzować za pomocą programu, który po prostu zawiera cały ciąg i go powtarza. Taki program nie umożliwia jednak skompresowania ciągu. Ciągi nielosowe mają programy krótsze niż same ciągi, a w związku z tym są kompresowalne. Pierwszy z wyżej przedstawionych ciągów jest kompresowalny, a drugi – o ile nam wiadomo – jest niekompresowalny.

Koncepcja informacji kołmogorowskiej (nazywanej też złożonością Kołmogorowa) to teoria obliczeniowa, ponieważ koncentruje się na identyfikacji najkrótszego programu, który generuje dany ciąg bitów. Mamy tutaj jednak do czynienia z pewną ironią: rzadko jest możliwe ustalenie z całkowitą pewnością, że dany ciąg bitów rzeczywiście jest losowy w tym sensie, że nie istnieje kompresowalny program, który by go generował. Dzięki ustaleniom kombinatoryki, w której obowiązują matematyczne zasady obliczeniowe, wiemy, że ogromna większość ciągów bitów musi mieć charakter losowy w sensie Kołmogorowa. To dlatego, że liczba krótkich programów jest bardzo ograniczona i może generować tylko bardzo niewiele dłuższych ciągów. Większość dłuższych ciągów wymaga dłuższych programów.

Jeśli jednak dla jakiegoś dowolnego ciągu D zdefiniujemy K(D) jako długość najkrótszego programu, który generuje D, to okazuje się, że nie istnieje żaden program komputerowy umożliwiający obliczenie K(D). Mówiąc prosto, funkcja K jest nieobliczalna. Ten fakt z dziedziny informatyki teoretycznej jest zgodny z naszym powszechnym doświadczeniem, że coś może wydawać się przez jakiś czas losowe, ale nigdy nie możemy mieć pewności, że jest to losowe, możemy bowiem odkryć wzorzec jasno wskazujący, że to coś w istocie nie jest losowe (na przykład w czymś, co wygląda na „losowy” kleks, po bliższym przyjrzeniu się możemy dostrzec wizerunek ludzkiej twarzy).

Mimo jednak że funkcja K jest nieobliczalna, w praktyce stanowi użyteczną miarę, zwłaszcza gdy staramy się zrozumieć, czym jest nielosowość. Z powodu swojej nieobliczalności K nie pomaga nam zidentyfikować jakichś konkretnych niekompresowalnych ciągów, a więc są to ciągi losowe. Mimo że K jest dobrze zdefiniowaną funkcją matematyczną, w większości sytuacji nie jesteśmy w stanie precyzyjnie określić jej wartości. Niemniej K pomaga nam identyfikować ciągi kompresowalne i możemy wówczas oszacować wartość K, choć niekoniecznie dokładnie ją obliczyć.

W takich sytuacjach w ciągu zwykle dostrzegamy jakiś wyrazisty wzorzec, który umożliwia nam wykazanie, że ten ciąg jest kompresowalny. W tym celu potrzebujemy ogólnie pojętej miary długości ciągów bitów. W związku z tym dla każdego ciągu bitów D definiujemy |D| jako jego długość (czyli jako całkowitą liczbę bitów). Ponieważ każdy ciąg można zdefiniować za pomocą niego samego, więc |D| stanowi górną granicę złożoności Kołmogorowa. Przypuśćmy teraz, że dzięki naszej wnikliwości bądź pomysłowości opracowujemy program, który w znacznym stopniu kompresuje D. Długość tego programu (określmy ją jako n) będzie wówczas znacznie mniejsza niż |D| – inaczej mówiąc, n < |D|.

Chociaż ta długość n programu będzie znacznie mniejsza niż D, to zwykle nie sposób wykazać, że ten program o długości n jest najkrótszym programem, który generuje D. Nic to jednak nie szkodzi. Biorąc pod uwagę taki program o długości n, wiemy, że K(D) nie może być większa od n, ponieważ K(D) stanowi miarę najkrótszego programu, który generuje D. Znajdując więc jakiś krótki program o długości n, wiemy, że K(D) ≤ n ≤ |D|. W praktyce wystarczy znaleźć krótki program o długości n, który jest znacznie krótszy od |D|. Tym samym liczba n stanowi górną granicę K(D). W praktyce używamy n jako szacunkowej wartości K(D). Jak przekonamy się w kolejnym artykule, taka szacunkowa wartość ma zastosowanie jako zachowawczy szacunek złożoności Kołmogorowa.

William A. Dembski

Oryginał: Specified Complexity Made Simple, „Bill Dembski: Freedom, Technology, Education” 2024, February 26 [dostęp: 26 VII 2024].

Przekład z języka angielskiego: Dariusz Sagan

Literatura: