Skutecznie obliczalne warianty złożoności Kołmogorowa

28

Złożoność prefiksu Kołmogorowa (tj. to rozmiar minimalnego programu do rozgraniczania, który generuje ), ma kilka fajnych cech: $K(x)$ $x$

Odpowiada to intuicji nadawania łańcuchom z wzorami lub struktury mniejszej złożoności niż łańcuchy bez.
To pozwala nam na zdefiniowanie warunkowego złożoność , albo nawet lepiej jakiegoś oracle . $K(x|y)$ $K(x|O)$ $O$
Jest subaddytywny . $K(x,y) \leq K(x) + K(y)$

Ma to jednak okropny minus: zwracanie przy jest nierozstrzygalne. $K(x)$ $x$

Zastanawiałem się, czy istnieje wariant złożoności Kołmogorowa wykorzystujący ograniczony model obliczeń (albo przy użyciu słabszych języków niż TM, albo przy użyciu ograniczonej bazy TM), która zachowuje cechy (1) i (2) (funkcja ( 3) czy jest premią, ale nie koniecznością), a jednocześnie jest wydajnie obliczalna? $K'(x)$

Motywem tego pytania jest zastosowanie w badaniach symulacyjnych różnych zabawkowych modeli ewolucji. Dlatego preferowana jest odpowiedź, która była wcześniej stosowana jako „przybliżone przybliżenie” złożoności Kołmogorowa w pracy numerycznej. Jednak celem nie jest przejście w pełni na eksperymenty, dlatego preferowany jest stosunkowo prosty / czysty język opisu / model obliczeń dla , aby można było udowodnić pewne rozsądne twierdzenia o tym, jak drastycznie różni się od i na jakich ciągach. $K'$ $K'$ $K$

Odpowiada na pytania

Złożoność Kołmogorowa ze słabymi językami opisu

Czy istnieje rozsądne pojęcie algorytmu aproksymacyjnego dla nierozwiązywalnego problemu?

it.information-theory kolmogorov-complexity formal-modeling

— Artem Kaznatcheev
źródło

10

Gzip. Cilibrasi i Vitanyi mają naprawdę fajny artykuł, w którym używają gzip jako przybliżenia złożoności Kołmogorowa do tworzenia klastrów. Grupowanie przez kompresję

— Chad Brewbaker
źródło

1

jak definiują złożoność warunkową?

— Artem Kaznatcheev

1

Niech A i B będą dwoma dokumentami, a AB dwoma połączonymi. Patrzą na stosunek SIZE (gzip (A) + gzip (B)) do SIZE (gzip (AB)).

— Chad Brewbaker

1

Należy zdawać sobie sprawę, że istnieją wady używania gzip (i podobnych) w celu przybliżenia złożoności Kołmogorowa: bactra.org/notebooks/cep-gzip.html . Nie oznacza to, że nie jest użyteczny do tworzenia klastrów rzeczywistych zestawów danych, ale mówi, że jego użyteczność w zestawach danych rzeczywistych mówi nam coś o tym, jak te zestawy danych różnią się od, powiedzmy, wyjścia generatora liczb pseudolosowych ...

— Joshua Grochow

3

$n = 2^m$

$x$ $|x| = 2^m$ $f_x: \{0,1\}^m \rightarrow \{0,1\}$ $K'(x)$ $f_x$ $2^m$ , mamy skuteczny środek.

$i \in \{1,...,m\}$ $K(x|y)$ $|y| = 2^m$

$a$ $|a| = m$ $i$ $a_i$ $f_y(a)$ $K'(x|x) = 2$ $K'(x|y) \approx K(x)$ $y$

[Uwaga: nie jest jasne, czy złożoność warunkowa może być nadal skutecznie obliczana :(]

$x.y$ $0$ $x$ $1$ $y$ $K'(x.y) \leq K'(x) + K'(y)$

$K'(x)$ $x$ $|x| = 2^m$ $|y| = 2^l$ $m > l$ $K'(x.y) = K'(x) + K'(y)$

Niestety, moje podejście ma również pewne ograniczenia. Nie możemy wykroczyć daleko poza OBDD, jeśli weźmiemy pod uwagę drzewa decyzyjne lub tylko dyski BDD, wówczas zajmiemy się problemami trudnymi rozwiązanymi w tej odpowiedzi . Wydaje się, że nawet w przypadku zmiennego porządkowania OBDD wyniki są trudne do rozwiązania . Wygląda więc na to, że OBDD jest granicą tego nie tak podobnego do standardowego podejścia złożoności Kołmogorowa.

— Artem Kaznatcheev
źródło

2

Nie jestem ekspertem, ale jeśli potrzebujesz praktycznej miary złożoności ciągów, możesz rzucić okiem na miarę złożoności T Titchenera .

Zobacz stronę internetową Titchenera, aby zapoznać się z krótkim wprowadzeniem; jego prace można pobrać w formacie pdf .

Streszczenie - Nowa miara złożoności łańcucha dla łańcuchów skończonych została przedstawiona w oparciu o określony rekurencyjny hierarchiczny proces tworzenia łańcucha . Z maksymalnego ograniczenia wywnioskujemy związek między złożonością a całkowitą zawartością informacji. ..pełny artykuł...

Znalazłem też dokumenty na temat praktycznych wdrożeń (patrz na przykład „ Algorytm szybkiego rozkładu T ”)

— Marzio De Biasi
źródło

2

Zasadniczo prawie każda metoda uczenia maszynowego lub kompresji jest przybliżeniem złożoności Kołmogorowa:

$p(x)$ $- \log p(x)$
$n$ $K(x) \leq n + s_C$ $s_C$ $x$

Zatem możesz po prostu szukać wzorców z dowolnym kompresorem lub rozkładem prawdopodobieństwa, a im lepiej kompresują twoje dane, tym lepsza jest górna granica dla K (x). Pamiętaj tylko, aby dodać rozmiar samej sprężarki do wielkości skompresowanych danych, aby uzyskać oszacowanie.

$K(x)$

$K(x)$ $K$

Możesz także użyć terminu, aby zdefiniować klasę modelu, co prowadzi do odpowiedzi Suresha. Zasadniczo, jeśli przyjmiesz, że twoje źródło danych ma wielomianową złożoność czasową i wypróbujesz wszystkie wielomianowe maszyny Turinga, aby go skompresować, możesz być całkiem pewien, że dokładnie oszacowałeś złożoność Kołmogorowa. To może nadal nie być tak praktyczne, ale w niższych przedziałach czasowych możesz być w stanie obliczyć pełną mieszaninę bayesowską, co jest dobrym przybliżeniem.

Szczegóły techniczne znajdują się w tym dokumencie . Uwaga: Jestem jednym z autorów.

$K(x)$ $K(x)$

— Piotr
źródło

-1

Szukasz złożoności złożonej Kołmogorowa. Możesz zacząć od tego papieru i rozgałęzić się.

— Suresh Venkat
źródło

2

dzięki za link do artykułu wspominam o złożoności związanej z zasobami w pytaniu, ale tak naprawdę zainteresowanie wzbudza środki, które można skutecznie obliczyć. Wydaje się, że artykuł pokazuje, że „losowe ciągi” dla tych modeli odpowiadają zestawom o dużej złożoności. To sugeruje, że decydowanie o złożoności łańcucha w tych modelach nie jest wydajnie obliczalne, prawda?

— Artem Kaznatcheev