Informationsabstand - Information distance

Der Informationsabstand ist der Abstand zwischen zwei endlichen Objekten (dargestellt als Computerdateien ), ausgedrückt als Anzahl von Bits im kürzesten Programm, das auf einem universellen Computer ein Objekt in das andere umwandelt oder umgekehrt . Dies ist eine Erweiterung der Kolmogorov-Komplexität . Die Kolmogorov-Komplexität eines einzelnen endlichen Objekts ist die Information in diesem Objekt; Der Informationsabstand zwischen einem Paar endlicher Objekte ist die minimale Information, die erforderlich ist, um von einem Objekt zum anderen oder umgekehrt zu gelangen. Der Informationsabstand wurde zuerst auf Basis thermodynamischer Prinzipien definiert und untersucht , siehe auch. Anschließend erreicht es die endgültige Form in. Es wird in der normalisierten Kompressionsdistanz und der normalisierten Google-Distanz angewendet .

Eigenschaften

Formal ist der Informationsabstand zwischen und definiert durch ${\displaystyle-ID(x,y)}$${\displaystyle x}$${\displaystyle y}$

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

mit einem endlichen Binärprogramm für den ortsfesten Universalrechner mit als Eingaben endlichen Binärstrings . Darin ist bewiesen, dass mit ${\displaystyle p}$${\displaystyle x,y}$${\displaystyle ID(x,y)=E(x,y)+O(\log\cdot\max\{K(x\mid y),K(y\mid x)\})}$

${\displaystyle E(x,y)=\max\{K(x\mid y),K(y\mid x)\},}$

wobei die Kolmogorov-Komplexität definiert durch des Präfixtyps ist. Dies ist die wichtige Größe. ${\displaystyle K(\cdot\mid\cdot)}$${\displaystyle E(x,y)}$

Universalität

Sei die Klasse der oberen halbberechenbaren Distanzen , die die Dichtebedingung erfüllen ${\displaystyle \Delta}$ ${\displaystyle D(x,y)}$

${\displaystyle \sum _{x:x\neq y}2^{-D(x,y)}\leq 1,\;\sum _{y:y\neq x}2^{-D(x, y)}\leq 1,}$

Dies schließt irrelevante Entfernungen wie für ; es sorgt dafür, dass, wenn die Entfernung zunimmt, die Anzahl der Objekte innerhalb dieser Entfernung eines bestimmten Objekts wächst. Wenn dann bis zu einem konstanten additiven Term. Die probabilistischen Distanzausdrücke sind die erste kohomologische Klasse in der informationssymmetrischen Kohomologie, die als Universalitätseigenschaft aufgefasst werden kann. ${\displaystyle D(x,y)={\frac {1}{2}}}$${\displaystyle x\neq y}$${\displaystyle D\in\Delta}$${\displaystyle E(x,y)\leq D(x,y)}$

Metrik

Der Abstand ist eine Metrik bis auf einen additiven Term in den metrischen (Un-)Gleichungen. Die probabilistische Version der Metrik ist in der Tat einzigartig, wie Han 1981 gezeigt hat. ${\displaystyle E(x,y)}$${\displaystyle O(\log .\max\{K(x\mid y),K(y\mid x)\})}$

Maximale Überlappung

Wenn , dann gibt es ein Programm mit einer Länge , daß konvertiert zu , und ein Programm mit einer Länge , so dass das Programm konvertiert zu . (Die Programme sind der selbstbegrenzenden Format , was bedeutet , dass man sich entscheiden , wo ein Programm endet und das andere beginnt in Verkettung der Programme.) Das heißt, die kürzeste Programme zwischen zwei Objekten konvertieren können maximal überlappende gemacht werden: Für sie kann in ein Programm unterteilt werden, das Objekt in Objekt konvertiert , und ein anderes Programm, das mit dem ersten verkettet ist, konvertiert in, während die Verkettung dieser beiden Programme das kürzeste Programm zum Konvertieren zwischen diesen Objekten ist. ${\displaystyle E(x,y)=K(x\mid y)}$${\displaystyle p}$${\displaystyle K(x\mid y)}$${\displaystyle y}$${\displaystyle x}$${\displaystyle q}$${\displaystyle K(y\mid x)-K(x\mid y)}$${\displaystyle qp}$${\displaystyle x}$${\displaystyle y}$${\displaystyle K(x\mid y)\leq K(y\mid x)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle y}$${\displaystyle x}$

Mindestüberlappung

Die Programme konvertieren zwischen Objekten und können auch minimal überlappend gemacht werden. Es gibt ein Programm mit einer Länge von bis zu einer Zusatzlaufzeit , dass die Karten auf und hat kleine Komplexität , wenn bekannt ist ( ). Wenn wir die beiden Objekte vertauschen, haben wir das andere Programm In Anbetracht der Parallelität zwischen der Shannon-Informationstheorie und der Kolmogorov-Komplexitätstheorie kann man sagen, dass dieses Ergebnis parallel zu den Sätzen von Slepian-Wolf und Körner-Imre Csiszár-Marton ist . ${\displaystyle x}$${\displaystyle y}$${\displaystyle p}$${\displaystyle K(x\mid y)}$${\displaystyle O(\log(\max\{K(x\mid y),K(y\mid x)\}))}$${\displaystyle y}$${\displaystyle x}$${\displaystyle x}$${\displaystyle K(p\mid x)\approx 0}$

Anwendungen

Theoretisch

Das Ergebnis von An.A. Muchnik über minimale Überlappung oben ist eine wichtige theoretische Anwendung, die zeigt, dass bestimmte Codes existieren: Um von jedem Objekt zu einem endlichen Zielobjekt zu gelangen, gibt es ein Programm, das fast nur vom Zielobjekt abhängt! Dieses Ergebnis ist ziemlich genau und der Fehlerterm kann nicht wesentlich verbessert werden. Die Information Distanz war Material im Lehrbuch, sie kommt in der Encyclopedia on Distances vor.

Praktisch

Um die Ähnlichkeit von Objekten wie Genomen, Sprachen, Musik, Internetangriffen und Würmern, Softwareprogrammen usw. zu bestimmen, wird der Informationsabstand normalisiert und die Kolmogorov-Komplexitätsterme durch reale Kompressoren angenähert (die Kolmogorov-Komplexität ist eine untere Grenze zu die Länge in Bit einer komprimierten Version des Objekts). Das Ergebnis ist der normalisierte Kompressionsabstand (NCD) zwischen den Objekten. Dies betrifft Objekte, die als Computerdateien vorliegen, wie das Genom einer Maus oder der Text eines Buches. Werden die Objekte nur mit Namen wie `Einstein' oder `Tabelle' oder dem Namen eines Buches oder dem Namen `Maus' angegeben, macht die Komprimierung keinen Sinn. Wir benötigen externe Informationen über die Bedeutung des Namens. Die Verwendung einer Datenbank (z. B. des Internets) und eines Mittels zum Durchsuchen der Datenbank (z. B. einer Suchmaschine wie Google) liefert diese Informationen. Jede Suchmaschine auf einer Datenbank, die aggregierte Seitenzahlen liefert, kann in der normalisierten Google-Distanz (NGD) verwendet werden. Ein Python-Paket zur Berechnung aller Informationsentfernungen und -volumina, multivariaten gegenseitigen Informationen, bedingten gegenseitigen Informationen, gemeinsamen Entropien, Gesamtkorrelationen in einem Datensatz von n Variablen ist verfügbar.

Verweise

Ähnliche Literatur

• Archangel'skii, AV; Pontryagin, LS (1990), Allgemeine Topologie I: Grundbegriffe und Konstruktionen Dimensionstheorie , Encyclopaedia of Mathematical Sciences, Springer , ISBN 3-540-18178-4