情報距離

情報距離は、2つの有限オブジェクト（コンピュータファイルとして表される）間の距離であり、汎用コンピュータ上で1つのオブジェクトを他のオブジェクトに変換する（またはその逆）最短プログラムのビット数として表現さ れます。これは、コルモゴロフ複雑性の拡張です。^[1]単一の有限オブジェクトのコルモゴロフ複雑性はそのオブジェクト内の情報です。一対の有限オブジェクト間の情報距離は、1つのオブジェクトから他のオブジェクトへ、またはその逆へ移動するために必要な最小限の情報です。情報距離は、^[2]で熱力学原理に基づいて最初に定義され、調査されました（ ^[3]も参照）。その後、で最終的な形になりました。^[4]これは、正規化圧縮距離と正規化Google距離に適用されます。

正式には、と間の情報距離は次のように定義される。 ${\displaystyle ID(x,y)}$${\displaystyle x}$${\displaystyle y}$

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

有限バイナリ文字列を入力とする固定汎用コンピュータ用の有限バイナリプログラム。^[4]では 、 ${\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)\},}$

ここで、はプレフィックス型^[1]で定義されるコルモゴロフ複雑度である。 ^[5]これは重要な量である。 ${\displaystyle K(\cdot \mid \cdot )}$${\displaystyle E(x,y)}$

密度条件を満たす上側半計算可能距離 のクラスを${\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,}$

これには、のような無関係な距離は含まれません。距離が増加する場合、特定のオブジェクトのその距離内にあるオブジェクトの数が増えることに注意してください。 の場合、定数の加法項まで増加します。^[4] 距離の確率的表現は、情報対称コホモロジーにおける最初のコホモロジークラスであり、^[6]普遍性特性として考えることができます。 ${\displaystyle D(x,y)={\frac {1}{2}}}$${\displaystyle x\neq y}$${\displaystyle D\in \Delta }$${\displaystyle E(x,y)\leq D(x,y)}$

距離は 、計量等式（不等式）における加法項を除けば計量である。 ^[4]計量の確率的バージョンは確かに唯一であり、1981年にハンによって示された。^[7]${\displaystyle E(x,y)}$${\displaystyle O(\log .\max\{K(x\mid y),K(y\mid x)\})}$

の場合、に変換する長さのプログラムと、を に変換する長さのプログラムがあります。(プログラムは自己区切り形式であり、プログラムの連結において、1 つのプログラムがどこで終了し、別のプログラムがどこで開始するかを決定できます。) つまり、2 つのオブジェクト間の変換を行う最短のプログラムは、最大限に重複させることができます。これは、オブジェクト をオブジェクト に変換するプログラムと、最初のプログラムと連結して に変換する別のプログラムに分割できますが、これら 2 つのプログラムを連結すると、これらのオブジェクト間の変換を行う最短のプログラムになります。[ ^4]${\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}$

オブジェクトとを変換するプログラムも、重複を最小限に抑えることができます。 の加法項までの長さのプログラムが存在し、がわかっている場合、 は小さな複雑性を持ちます( )。2 つのオブジェクトを交換すると、他のプログラムが得られます^[8]シャノン情報理論とコルモゴロフ複雑性理論の類似性を念頭に置くと、この結果はSlepian-Wolf定理と Körner–Imre Csiszár–Marton 定理に類似していると言えます。 ${\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}$

上記のAn.A. Muchnikの最小重なりに関する結果は、特定のコードが存在することを示す重要な理論的応用です。つまり、任意のオブジェクトから有限のターゲットオブジェクトに移動するには、ターゲットオブジェクトにほぼのみ依存するプログラムがあります。この結果はかなり正確であり、誤差項を大幅に改善することはできません。^[9] 情報距離は教科書で取り上げられており、^[10]距離百科事典に記載されています。^[11]

ゲノム、言語、音楽、インターネット攻撃やワーム、ソフトウェア プログラムなどのオブジェクトの類似性を判断するために、情報距離が正規化され、コルモゴロフ複雑度の項が実際の圧縮器によって近似されます (コルモゴロフ複雑度は、オブジェクトの圧縮バージョンのビット単位の長さの下限です)。結果は、オブジェクト間の正規化圧縮距離(NCD) です。これは、マウスのゲノムや本のテキストなど、コンピュータ ファイルとして提供されるオブジェクトに関係します。オブジェクトが「アインシュタイン」や「テーブル」、本の名前、または「マウス」の名前などの名前でのみ指定されている場合、圧縮は意味がありません。名前の意味に関する外部情報が必要です。データベース (インターネットなど) とデータベースを検索する手段 (Google などの検索エンジンなど) を使用すると、この情報が得られます。データベース上の集計ページ数を提供するすべての検索エンジンは、正規化 Google 距離(NGD) で使用できます。 n変数のデータセット内のすべての情報距離と情報量、多変量相互情報量、条件付き相互情報量、結合エントロピー、総相関を計算するPythonパッケージが利用可能です。^[12]

• Arkhangel'skii, AV; Pontryagin, LS (1990)、一般位相幾何学 I: 基本概念と構成 次元理論、数学科学百科事典、Springer、ISBN 3-540-18178-4