Odległość informacyjna

Odległość informacyjna to odległość między dwoma obiektami skończonymi (reprezentowanymi jako pliki komputerowe ) wyrażona liczbą bitów w najkrótszym programie przekształcającym jeden obiekt w drugi lub odwrotnie na komputerze uniwersalnym . Jest to rozszerzenie złożoności Kołmogorowa . Złożoność Kołmogorowa pojedynczego skończonego obiektu to informacja zawarta w tym obiekcie; odległość informacyjna między parą obiektów skończonych to minimalna informacja wymagana do przejścia z jednego obiektu do drugiego lub odwrotnie. Odległość informacyjna została po raz pierwszy zdefiniowana i zbadana w oparciu o zasady termodynamiki , patrz także. Następnie uzyskał ostateczną postać w r. Stosowany jest w znormalizowanej odległości kompresji i znormalizowanej odległości Google .

Nieruchomości

Formalnie odległość informacyjna między i $Displaystyle$ jest definiowana przez $ID (x,$$)}$

${\ Displaystyle ID (x, y) = \ min \ {| p |: p (x) = y \; \ & \; p (y) =x\},}$

z skończonym programem binarnym dla stacjonarnego $komputera$ uniwersalnego z wejściowymi skończonymi łańcuchami binarnymi $\ displaystyle x, y}$ . Udowodniono, że ${\ Displaystyle ID (x, y) = E (x, y) + O (\ log \ cdot \ max \ {K (x \ mid y), K (y \ mid x) \} )}$ z

${\ Displaystyle E (x, y) = \ max \ {K (x \ mid y), K (y \ środek x)\},}$

gdzie $złożonością$ . _ _ Ta ${\ Displaystyle E (x, y)}$ jest ważną wielkością.

Uniwersalność

Niech $będzie$ klasą górnych półobliczalnych odległości spełniających warunek gęstości $}$

${\ Displaystyle \ suma _ {x: x \ neq y} 2 ^ {-D(x,y)}\równik 1,\;\suma _{y:y\neq x}2^{-D(x,y)}\równik 1,}$

Wyklucza to nieistotne odległości, takie jak ${\ Displaystyle D (x, y) = {\ Frac {1} {2}}}$ dla ${\ Displaystyle x \ neq y}$ ; dba o to, aby wraz ze wzrostem odległości rosła liczba obiektów w tej odległości od danego obiektu. re $D \ in \ Delta}$ to $aż do$ składnika addytywnego. Probabilistyczne wyrażenia odległości to pierwsza klasa kohomologiczna w kohomologii symetrycznej informacji, którą można pojmować jako właściwość uniwersalności.

Metryka

mi $y)}$${\ Displaystyle O (\log .\max\{K(x\mid y),K(y\mid x)\})}$ jest metryką aż do dodatku wyraz w metryce (w)równościach. Wersja probabilistyczna metryki jest rzeczywiście wyjątkowa, co pokazał Han w 1981 roku.

Maksymalne nakładanie się

mi ${\ Displaystyle E (x, y) = K (x \ mid y)}$ to istnieje program $p {\ displaystyle p}$ długości $\ mid y)}$${\ displaystyle x}$$i$ , który konwertuje na $program$ o długości ${\ Displaystyle K (y \ mid x) -K (x \ mid y)}$ tak, że program konwertuje ${\ displaystyle qp}$${\ displaystyle x}$ na ${\ displaystyle y}$ . (Programy mają samoograniczający się format co oznacza, że ​​można zadecydować gdzie kończy się jeden program a zaczyna drugi w konkatenacji programów.) Oznacza to, $maksymalnie$$się$ można go podzielić na program, który konwertuje obiekt $i inny program, który połączył$ obiekt z pierwszym konwertuje na ${\ displaystyle y}$${\ displaystyle x}$ , podczas gdy połączenie tych dwóch programów jest najkrótszym programem do konwersji między tymi obiektami.

Minimalne nakładanie się

Programy do konwersji między obiektami i $displaystyle$$y}$ można również minimalnie nakładać. Istnieje program $długości$${\ Displaystyle K (x \ mid y)}$ aż do addytywnego składnika p {\ displaystyle p} ${\ Displaystyle O (\ log (\ max \ {K (x \ mid y), K (y \ mid x) \})}}, który odwzorowuje$ y $\ Displaystyle y}$ na ${\ Displaystyle x }$ i ma niewielką złożoność, gdy $\ Displaystyle K (p \ mid x) \ około 0}$ znana ( ( $)$ ). Zamieniając dwa obiekty mamy drugi program Mając na uwadze paralelizm między teorią informacji Shannona a złożonością Kołmogorowa można powiedzieć, że wynik ten jest równoległy do ​​twierdzeń Slepiana-Wolfa i Körnera-Imre Csiszára-Martona.

Aplikacje

Teoretyczny

Wynik An.A. Muchnik o minimalnym nakładaniu się powyżej jest ważnym zastosowaniem teoretycznym pokazującym, że istnieją pewne kody: aby przejść do skończonego obiektu docelowego z dowolnego obiektu, istnieje program, który prawie tylko zależy od obiektu docelowego! Wynik ten jest dość precyzyjny i składnika błędu nie można znacząco poprawić. Informacja o odległości była istotna w podręczniku, występuje w Encyklopedii o odległościach.

Praktyczny

Aby określić podobieństwo obiektów, takich jak genomy, języki, muzyka, ataki internetowe i robaki, programy itd., normalizuje się odległość informacji, a terminy złożoności Kołmogorowa przybliża się za pomocą rzeczywistych kompresorów (złożoność Kołmogorowa jest dolną granicą długość w bitach skompresowanej wersji obiektu). Wynikiem jest znormalizowana odległość kompresji (NCD) między obiektami. Dotyczy to obiektów przekazywanych w postaci plików komputerowych, takich jak genom myszy czy tekst książki. Jeśli obiekty są podane tylko z nazwy, takiej jak „Einstein” lub „tabela”, albo nazwa książki, albo nazwa „mysz”, kompresja nie ma sensu. Potrzebujemy zewnętrznych informacji o tym, co oznacza ta nazwa. Korzystanie z bazy danych (takiej jak Internet) i środków do przeszukiwania bazy danych (takich jak wyszukiwarka taka jak Google) dostarcza tych informacji. Każda wyszukiwarka w bazie danych, która zapewnia zbiorcze liczby stron, może być używana w znormalizowana odległość Google (NGD). Dostępny jest pakiet Pythona do obliczania wszystkich odległości i objętości informacji, wielowymiarowych informacji wzajemnych, warunkowych informacji wzajemnych, wspólnych entropii, całkowitych korelacji w zbiorze danych zawierającym n zmiennych.

Powiązana literatura

•   Archangielski, AV; Pontryagin, LS (1990), Topologia ogólna I: podstawowe pojęcia i konstrukcje Teoria wymiarów , Encyklopedia nauk matematycznych, Springer , ISBN 3-540-18178-4