Różnica między „informacją” a „użyteczną informacją” w algorytmicznej teorii informacji

Według Wikipedii :

Nieformalnie, z punktu widzenia algorytmicznej teorii informacji, zawartość informacyjna ciągu jest równoważna długości możliwie najkrótszej możliwej niezależnej reprezentacji tego ciągu.

Jaka jest analogiczna nieformalna rygorystyczna definicja „użytecznych informacji”? Dlaczego „użyteczne informacje” nie są uważane za bardziej naturalne lub bardziej podstawowe pojęcie; naiwnie wydaje się, że czysto przypadkowy ciąg musi z definicji zawierać informacje zerowe, więc staram się przekonać, że według standardowej definicji ma on maksymalną ilość informacji.

Główną koncepcją tutaj jest złożoność Kołmogorowa , a ściślej ściśliwość . Aby uzyskać intuicyjne poczucie ściśliwości, rozważ dwa ciągi i B ∈ B ∗ , gdzie B = { 0 , 1 } . Pozwolić$A \in \mathbb{B}^*$$B \in \mathbb{B}^*$$\mathbb{B} = \{ 0,1 \}$

1010 1010 1010 i$A = 1010$ $1010$ $1010$ $1010$

0110 0111 1001 .$B = 1011$ $0110$ $0111$ $1001$

Zauważ, że . Jak możemy obliczyć, ile informacji ma A lub B ? Jeśli myślimy o klasycznej teorii informacji, ogólnie, przesłanie ciągu o długości n zajmuje średnio n bitów. Nie możemy jednak powiedzieć, ile bitów potrzebujemy do przesłania określonego ciągu o długości n .$|A| = |B| = 16$$A$$B$$n$$n$$n$

Dlaczego zawartość informacyjna losowego ciągu nie jest równa zero?

Przy bliższym przyjrzeniu możemy zauważyć, że w rzeczywistości . Jednak o wiele trudniej jest powiedzieć, czy B ma żadnych wyraźnych wzorców w swojej strukturze, przynajmniej wydaje i czuje się bardziej przypadkowy niż A . Ponieważ możemy znaleźć wzór w A , możemy łatwo skompresować A i przedstawić go za pomocą mniej niż 16 bitów. Podobnie, ponieważ nie jest łatwo wykryć jakiekolwiek wzorce w B , nie możemy go tak mocno skompresować. Dlatego możemy powiedzieć, że B ma więcej informacji niż A . Ponadto losowy ciąg długości $A = 10^8$$B$$A$$A$$A$$16$$B$$B$$A$$n$ma maksymalną informację, ponieważ nie ma możliwości, abyśmy ją skompresowali, a zatem reprezentują ją za pomocą mniej niż bitów.$n$

Jakie są zatem przydatne informacje?

Do użytecznych informacji , tak, istnieje definicja za pomocą maszyny Turinga . Przydatną informacją w x ∈ B ∗ jest$T$$x \in \mathbb{B}^*$

$$\min_T \space \{\space l(T) + C(x|T) : T \in \{ T_0, T_1, ... \} \},$$

gdzie oznacza długość samoograniczającą kodowania dla maszyny Turingowi T . Zapis jest zwykle taki, że C ( x ) oznacza złożoność Kołmogorowa x, a C ( x | y ) warunkową złożoność Kołmogorowa x dla danego y .$l(T)$$T$$C(x)$$x$$C(x|y)$$x$$y$

Tutaj ucieleśnia ilość użytecznych informacji zawartych w x . Możemy zapytać, który T wybrać spośród tych, które spełniają ten wymóg. Problemem jest oddzielenie najkrótsza programu x * w części x * = P P St P oznacza odpowiednią T . Jest to właściwie sam pomysł, który zrodził minimalną długość opisu (MDL) .$T$$x$$T$$x^*$$x^* = pq$$p$$T$

Może tak być, ponieważ określenie „użyteczny” jest trudne do zdefiniowania. Powiedzmy, że mamy wysoce ustrukturyzowaną, bogatą w informacje wiadomość która może być skompresowana co najwyżej o współczynnik α względem wiadomości y . Intuicyjnie, x i y zawierają taką samą ilość użytecznych danych; w rzeczywistości zawierają taką samą ilość informacji zgodnie ze zwykłą definicją. Teraz wyobraź sobie prefiksu Z o X o tej samej długości co y ; nie powinien zawierać więcej użytecznych informacji niż x , stąd nie więcej niż y . Jednak y jest bardziej „losowy” niż z , ponieważ $x$$\alpha$$y$$x$$y$$z$$x$$y$$x$$y$$y$$z$$z$mogą być kompresowane i nie. Jeśli więc spróbujemy powiązać „przydatne” informacje ze ściśliwością, moglibyśmy spotkać się z następującym paradoksem: prefiks wiadomości może zawierać więcej „przydatnych” informacji niż cała wiadomość, co wydaje się sprzecznością.$y$

Z mniej formalnego punktu widzenia myślę, że może to pomóc, jeśli odłączysz się od słowa „losowy”, ponieważ masz rację, że zestaw naprawdę losowych bitów nie przechowuje żadnych informacji w sensie praktycznym. (Jeśli zaszyfruję zestaw nazw i wyślę do Ciebie zaszyfrowane wartości, mogą one mieć bardzo wysoką złożoność Kołmogorowa, ale nie pomoże ci to w ustaleniu nazw).

Ale pomyśl o tym w ten sposób. Jeśli zobaczysz witrynę w języku obcym (np. Szwedzkim, zakładając, że nie mówisz), będzie ona wyglądać mniej więcej losowo. Słowa będą uporządkowane, ale niewiele. Jeśli jednak spojrzysz na stronę z tekstem, który wygląda tak: 123456123456123456123456 ... i tak dalej, będziesz w stanie zrozumieć to szybciej. Jeśli nie mówisz po szwedzku, prawdopodobnie będziesz w stanie uzyskać z niego znacznie więcej, nawet jeśli szwedzka strona podała odpowiednik „pierwszych sześciu liczb powtarzanych kolejno”. Witryny zawierają te same informacje, ale jedna wygląda na losową. A jeśli chodzi o ilość miejsca, ten, który rozumiesz, jest znacznie mniej wydajny niż szwedzka strona internetowa, mimo że przechowuje te same informacje. Informacje te mogą nie być „przydatne”, ponieważ „

Pojęcie „informacji” ma być uniwersalne, więc to, co wygląda na przypadkowe - a zatem bezużyteczne - bity dla ciebie, może przechowywać wiele informacji dla kogoś innego. Miara informacji ma być nieodłączną własnością łańcucha i nie może zależeć od tego, co ma i nie ma dla ciebie sensu oraz od tego, co możesz i czego nie możesz interpretować.

Kolejnym (bardziej technicznym) punktem, który może pomóc, jest to, że jestem tu nieco nieuczciwy. Jak zauważa Juho, informacje sązdefiniowany w stosunku do tego, kto to interpretuje. Może się okazać, że szwedzka strona internetowa jest całkowicie bezużyteczna jako narzędzie informacyjne, ale ktoś, kto mówi po szwedzku, może mieć dużą ilość informacji. Definicja to odzwierciedla. Jednak z matematyki możemy dowiedzieć się, że różnica między najkrótszą (najbardziej pouczającą dla strony) stroną do komunikacji z tą witryną a najkrótszą stroną, która może ją przekazać osobie, która mówi po szwedzku, może różnić się jedynie stałą addytywną. Dlaczego? Ponieważ dla ciebie, jako nie-szwedzkiego mówcy, najkrótszym sposobem na zapisanie strony, którą możesz zrozumieć, jest „pierwsze sześć liczb całkowitych powtarzanych sekwencyjnie”. To może być nieco dłużej niż szwedzki.

Ale nawet jeśli umiesz mówić po szwedzku, będziesz w stanie wyciąć tylko stałą dodatków z długości! Dlaczego? Ponieważ zawsze można było kupić słownik szwedzko-angielski. Wtedy bardzo krótkie szwedzkie strony miałyby dla ciebie sens. Jasne, mają sens tylko wtedy, gdy masz słownik, ale słownik ma stałą długość. Więc

$$(\mbox{Most efficient representation of information in English}) \leq (\mbox{Most efficient representation in Swedish}) + (\mbox{Length of Swedish-English dictionary})$$ . To trochę nie na temat twojego pierwotnego pytania, ale próbuję podkreślić, że nie ma większego znaczenia, kto czyta informacje. Ta losowo wyglądająca szwedzka strona internetowa nie była dla ciebie „przydatna”, ale „użyteczna” dla kogoś innego, a masz tylko stałą ilość informacji, abyś mógł z niej skorzystać samodzielnie.