Przybliżenie złożoności Kołmogorowa

22

Studiowałem coś na temat złożoności Kołmogorowa , przeczytałem kilka artykułów i książek Vitanyi i Li i wykorzystałem koncepcję znormalizowanej odległości kompresji, aby zweryfikować stilometrię autorów (określić, w jaki sposób każdy autor pisze niektóre dokumenty tekstowe i grupowe według ich podobieństwa).

W takim przypadku zastosowano kompresory danych w celu przybliżenia złożoności Kołmogorowa, ponieważ kompresor danych można wykorzystać jako maszynę Turinga.

Oprócz kompresji danych i języków programowania (w których napisałbyś jakiś kompresor), czego jeszcze można by użyć do przybliżenia złożoności Kołmogorowa? Czy można zastosować jakieś inne podejście?

— woliveirajr
źródło

Nie jestem pewien, czy rozumiem twoje pytanie: Definicja KC obejmuje maszyny Turinga, których programy tworzą przykłady (w odniesieniu do niektórych tłumaczeń). Co oznacza przybliżenie złożoności Kołmogorwa „bez języków programowania”?

— cody

1

Skompresuj ciąg przy użyciu dowolnego oprogramowania do kompresji, takiego jak GZip. Rozmiar wyniku jest górną granicą KC ciągu.

— M. Alaggan,

@cody: dokładnie, użyłem kompresorów danych w swoich badaniach (zip, bzip, ppmd) do przybliżenia KC. Kompresor danych nie jest dokładnie programem. Poszukuję więc sugestii na temat tego, czego można używać w KC oprócz języków (= napisz program w C / prolog / cokolwiek) i kompresorów danych (= użyj zip, gzip, ppmc, ppmd ...) :)

— woliveirajr,

1

Wydaje mi się, że po prostu wydaje mi się, że definicja programu do kompresji danych to dokładnie: program, który aproksymuje KC ciągu przez program („dekompresor”) i inny ciąg (ciąg skompresowany).

— cody

9

Chyba jedna z możliwych odpowiedzi na to pytanie jest taka: Weź generator liczb pseudolosowych . Spróbuj wybrać generator, który ma kilka potężnych ataków przeciwko niemu: atak generatora liczb losowych dla jest (dla naszych celów), algorytmem który po podaniu ciągu imputacyjnego określa ziarno , takie że . Następnie przybliż KC : $G$ $G$ $A$ $s$ $A(s)$ $G(A(s))=s$ $s$

input: s
Compute A(s);
if |A(s)| + |G| > |s| output: |s|
otherwise output: |A(s)| + |G|

Gdzie to długość programu obliczającego (często dość krótki, jak w przypadku generatorów liniowych). $|G|$ $G(s)$

Należy zauważyć, że w praktyce ataki generatora liczb losowych są niezgodne z opisem: mogą zawieść lub spowodować niepełne wyniki. W takim przypadku możesz dostosować algorytm, aby zwracał gdy wynik ataku jest niezadowalający. Ta sama uwaga dotyczy algorytmów kompresji. $|s|$

Zastrzeżeniem tego podejścia, w przeciwieństwie do algorytmów kompresji, jest to, że algorytmy kompresji są zasadniczo znacznie bardziej odpowiednie do obliczania KC, ponieważ są dostosowane do pracy na dowolnym łańcuchu, podczas gdy atak może działać tylko wtedy, gdy jest na obrazie ( bardzo mało prawdopodobne ). $s$ $G$

— cody
źródło

7

$p(x)$ $-\log p(x)$

To dlatego złożoność Kołmogorowa jest tak interesująca, nie dlatego, że jest to ostateczny algorytm kompresji (i tak zależy na kompresji), ale dlatego, że jest to najlepszy algorytm uczenia się . Kompresja i uczenie się to w zasadzie to samo: znajdowanie wzorców w danych. Ramy statystyczne zbudowane na tej idei nazywane są Minimalną długością opisu i zostały bezpośrednio zainspirowane złożonością Kołmogorowa.

Zobacz także to pytanie na cStheory StackExchange.

— Piotr
źródło

5

kodowanie gramatyczne jest rzadziej używaną wersją algorytmu kompresji i może być traktowane jako „przybliżona” ocena złożoności Kołmogorowa. kodowanie gramatyczne nie jest tak powszechnie stosowane jako algorytm kompresji, jak inne bardziej powszechne podejścia, być może głównie dlatego, że nie poprawia znacznie kompresji z np. Lempel-Ziv na korpusach tekstowych, ale może dobrze radzić sobie z innymi rodzajami danych. chodzi o „skompresowanie” łańcucha przy użyciu reguł gramatycznych. wyprowadzenie gramatyki może skutkować DAG (w porównaniu z mniej złożonym drzewem), więc możliwa jest znaczna złożoność reprezentacyjna.

inną opcją jest znalezienie najmniejszych / minimalnych obwodów reprezentujących łańcuch, ale wiadomo, że ma on bardzo dużą złożoność obliczeń i może odnieść sukces tylko na małych łańcuchach.

$K(x)$

istnieją również inne metody algorytmu kompresji oprócz podejść typu „kodowania długości przebiegu” Lempela-Ziva, na przykład algebra wektorowa i SVD mogą być użyte jako algorytm kompresji. również transformaty Fouriera są często używane do kompresji obrazów, np. w standardzie JPG.

— vzn
źródło

1

K (x)

$K(x)$

dobra uwaga, jednak algorytmy stratne zwykle mają regulowany parametr, który określa „stratę” i mogą teoretycznie osiągnąć bezstratność z wystarczającą liczbą „terminów” lub „częstotliwości”, że tak powiem, i zależy to również od próbek wejściowych, tak że wartość parametru bezstratnego będzie zależeć na temat ich „względnej kolejności vs losowości” widzianej przez „soczewkę” algorytmu kompresji ...

— dniu

1

@cody and vzn: Dziękuję za odpowiedź, dałeś mi kilka dobrych pomysłów dla mojego doktora na temat bezstratnej x stratnej kompresji :)

— woliveirajr

JPEG używa DCT, a nie DFT.

— Zły