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

16

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.

użytkownik1247
źródło
2
Witamy! Pamiętaj, że możesz zmienić swoją nazwę użytkownika na coś, co ludzie mogą rozpoznać, gdy stajesz się regularnym gościem.
Raphael

Odpowiedzi:

12

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ćABBBB={0,1}

1010 1010 1010 iZA=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 .|ZA|=|b|=16ZAbnnn

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 nZA=108bZAZAZA16BBAnma 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 jestTxB

minT. { l(T.)+do(x|T.):T.{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.do(x)xC(x|y)xy

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.xT.xx=pqpT

Juho
źródło
4

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ż zxαyxyzxyxyyzzmogą 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

Patrick87
źródło
Może być trudny do zdefiniowania i może być tak, że nie może on trywialnie polegać na ściśliwości, tak jak robi to „informacja”, ale wydaje się, że jest to ważniejsza definicja! W obecnej formie „informacja” wydaje się raczej pseudonimem dla „złożoności Kołmogorowa”, a nie poważną próbą zdefiniowania informacji w zwykłym znaczeniu, które w innych kontekstach muszą z definicji być przydatne! Czy to aktywny obszar badań? Czy są jakieś proponowane definicje?
użytkownik1247
@ user1247 Dlaczego uważasz, że złożoność Kołmogorowa nie jest poważna?
Juho
@mrm Uważam to za bardzo poważną i interesującą koncepcję, ale niekomfortowo nazywam to pojęcie „informacją”. Co to znaczy, że całkowicie losowy ciąg znaków zawiera informacje? „Przydatna informacja” wydaje się bardziej przydatna i interesująca, jeśli chodzi o omawianie informacji (gdzie „użyteczna” jest domniemana) w świecie rzeczywistym, na przykład w filozoficznych lub kwantowo-mechanicznych dyskusjach na temat przesyłania lub odbierania informacji.
użytkownik1247,
1
@ user1247 Prawdopodobnie interesującym sposobem interpretacji mojej odpowiedzi jest: informacja jest użyteczna lub bezużyteczna w zależności od sposobu jej interpretacji. W przypadku stałej interpretacji jedna wiadomość może zawierać mniej lub więcej przydatnych informacji niż inna. Każda teoria przydatnych informacji będzie, moim zdaniem, musiała brać pod uwagę takie interpretacje (robią to również zwykłe miary, takie jak entropia, choć domyślnie).
Patrick87
@ Patrick87 Absolutnie zgadzam się, że każda dobra teoria „przydatnych informacji” powinna uwzględniać mechanizm deszyfrowania. To sprawia, że ​​jest to interesujący problem! Jeśli wyślesz mi ciąg znaków i zasadniczo nie mogę go odszyfrować, to należy go zdefiniować, aby nie zawierał żadnych użytecznych informacji.
użytkownik1247,
4

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 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

(Most efficient representation of information in English)(Most efficient representation in Swedish)+(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.
SamM
źródło