정보 거리

정보 거리는 범용 컴퓨터에서 하나의 물체를 다른 물체로 변환하거나 그 반대로 변환하는 최단 프로그램의 비트 수로 표현되는 두 개의 유한 물체(컴퓨터 파일로 표현) 사이의 거리다. 이것은 콜모고로프 복잡성의 연장선이다.^[1] 단일 유한 물체의 콜모고로프 복잡성은 그 물체 내의 정보다. 유한 물체 쌍 사이의 정보 거리는 한 물체에서 다른 물체 또는 그 반대로 가는 데 필요한 최소한의 정보다. 정보 거리는 열역학 원리에 기초하여 먼저 정의되고 조사되었다(참조).^[3] 그 후에, 그것은 최종적인 형태를 이루었다.^[4] 표준화된 압축 거리와 표준화된 구글 거리에 적용된다.

특성.

$공식적$으로 x ${\displaystyle x}$과(${\displaystyle 와}$) $y{\displaystyle }$ ${\$displaystyle $id(x,y$$)}$ 사이의$$ 정보 거리 $I{\displaystyle }$ ${\displaystyle D(x}$, y${\displaystyle }$) ${\$$displaystyle id$(x,y)}은 다음과 같이 정의된다$$.

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

with ${\displaystyle p}$ a finite binary program for the fixed universal computer with as inputs finite binary strings ${\displaystyle x,y}$. In ^[4] it is proven that ${\displaystyle ID(x,y)=E(x,y)+O(\log \cdot \max\{K(x\mid y),K(y\mid x)\})}$ with

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

여기서 $K{\displaystyle (}$ ${\displaystyle \cdot }$ ${\displaystyle \mid \cdot }$ ) ${\displaystyle K(\cdot \mid \cdot )}$은 접두사 유형에 의해 정의된 Kolmogorov 복잡성이다.^[5] 이 $E{\displaystyle }$( ${\displaystyle x}$, ${\displaystyle y}$) ${\displaystyle E(x,y)}$이(가) 중요한 수량이다$$.

보편성

$\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta }$을(를) 밀도 조건을 충족하는$$ 상위 반투명 거리 $D{\displaystyle (x}$, ${\displaystyle y}$) ${\displaystyle D(x,y)$의 클래스로$$ 설정

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

여기에는 x ${\displaystyle \ne }$ ${\displaystyle y}$ ${\displaystyle x\neq y}$에 $대해{\displaystyle }$ D${\displaystyle (}$ ${\displaystyle x}$, y${\displaystyle }$)${\displaystyle }$= 1 ${\displaystyle \frac{2}{}}$ ${\$}{2$}}:}$와 같은 관련 없는 거리는 제외된다$.$ 거리 증가가 발생하면 해당 물체의 거리 내에 있는 물체의 수가 증가하도록 주의해야 한다. $D{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle \mathrm{\Delta }}$ ${\displaystyle D\in \Delta }$인 경우 $E{\displaystyle }$(${\displaystyle x}$, ${\displaystyle y}$)${\displaystyle \le }$ ${\displaystyle D(x,}$y${\displaystyle )}$ ${\displaystyle E(x,y)\leq D(x,y)}$을(를) 일정한 가법 항까지 증가시킨다$$.^[4] 거리에 대한 확률적 표현은 정보 대칭적 동족학에서 최초의 동족학급으로 보편성 속성으로 간주될 수 있다.^[6]

미터법

거리 $E{\displaystyle (x}$ ${\displaystyle ,}$ y${\displaystyle }$) ${\displaystyle E(x,y)}$은(는) 미터법(평)의 $최대값$인 ${\displaystyle O(최대값}${ ${\displaystyle K(x\mid }$ ${\displaystyle y}$)${\displaystyle }$,$(\log .\max\mid y),$^[4] K(y\mid x$)\}}$까지의 메트릭이다. 이 측정지표의 확률적 버전은 1981년 한씨가 보여준 독특한 것이다.^[7]

최대 겹침

If ${\displaystyle E(x,y)=K(x\mid y)}$, then there is a program ${\displaystyle p}$ of length ${\displaystyle K(x\mid y)}$ that converts ${\displaystyle y}$ to ${\displaystyle x}$, and a program ${\displaystyle q}$ of length ${\displayst$$프로그램$ ${\displaystyle q}$$p {\$displaystyle$$qp}이$($가) x ${\displaystyle x}$을(를) $y{\displaystyle }$ ${\displaystyle y}$로 변환하는 yle $K$$($y$$$\backslash$$mid x)-K(x\mid$ y)}. (프로그램은 한 프로그램이 종료되는 위치를 결정할 수 있는 자체 지연 형식이다.) 즉, 두 개체 간에 변환할 수 있는 가장 짧은 프로그램을 최대 중복으로 만들 수 있다. For ${\displaystyle K(x\mid y)\leq K(y\mid x)}$ it can be divided into a program that converts object ${\displaystyle x}$ to object ${\displaystyle y}$, and another program which concatenated with the first converts ${\displaystyle y}$ to ${\displaystyle x}$ while the concatenation of 이 두 프로그램은 이 객체들 사이에서 변환하는 가장 짧은 프로그램이다.^[4]

최소 겹침

개체 $x{\displaystyle }$ ${\displaystyle x}$과(와) $y{\displaystyle }$ ${\displaystyle y}$ 간에 변환하는 프로그램도 겹치지 않도록 할 수 있다$$. There exists a program ${\displaystyle p}$ of length ${\displaystyle K(x\mid y)}$ up to an additive term of ${\displaystyle O(\log(\max\{K(x\mid y),K(y\mid x)\}))}$ that maps ${\displaystyle y}$ to ${\displaystyle x}$ and has small complexity when $$${\displaystyle x}$ ${\displaystyle$ x$}$을(를) 알고 있다(${\displaystyle \mathrm{K}}$(${\displaystyle }$∣${\displaystyle x}$ )${\displaystyle \approx }$ 0$(\displaystyle$ K($p\mid$ x$)\약 0}).$ 우리가 가지고 있는 다른 두^[8] 물체들 상호교체 섀넌 정보 이론과 콜모고로프 복잡성 이론의 평행성을 염두에 두고, 이 결과는 슬레피안-늑대와 쾨르너-임레 치사르-마톤 이론과 평행하다고 말할 수 있다.

적용들

이론적

안 원장의 결과.A. 위의 최소 중첩에 관한 Muchnik은 특정 코드가 존재함을 보여주는 중요한 이론적 응용 프로그램이다: 대상 객체에만 거의 의존하는 프로그램이 있는 어떤 물체에서 유한 대상 객체로 가는 것이다! 이 결과는 상당히 정밀하며 오차항은 크게 개선할 수 없다.^[9] 정보 거리는 교과서에서 중요한 자료였고,^[10] 그것은 거리에 관한 백과사전에서 발생한다.^[11]

실용적인

게놈, 언어, 음악, 인터넷 공격과 웜, 소프트웨어 프로그램 등 물체의 유사성을 판단하기 위해 정보 거리가 정규화되고 실제 압축기에 의해 Kolmogorov 복잡성 용어가 근사하게 계산된다(Kolmogorov 복잡성은 개체의 압축된 버젼의 비트 단위 길이에 대한 하한이다). 그 결과 물체 사이의 정규화된 압축 거리(NCD)가 된다. 이것은 마우스의 게놈이나 책의 텍스트와 같은 컴퓨터 파일로 주어진 물체와 관련이 있다. '아인슈타인'이나 '테이블' 같은 이름이나 책의 이름이나 '쥐'라는 이름만으로 사물을 붙인다면 압축은 이치에 맞지 않는다. 우리는 그 이름이 무엇을 의미하는지 외부 정보가 필요하다. 데이터 베이스(인터넷 등)와 데이터베이스(구글과 같은 검색엔진 등)를 검색하는 수단을 사용하면 이러한 정보가 제공된다. 집계 페이지 수를 제공하는 데이터 베이스의 모든 검색 엔진은 표준화된 구글 거리(NGD)에서 사용될 수 있다. n 변수의 데이터 집합에서 모든 정보 거리 및 볼륨, 다변량 상호 정보, 조건부 상호 정보, 공동 엔트로피, 총 상관 관계를 계산하기 위한 python 패키지를 이용할 수 있다.^[12]

참조

관련 문헌

• Arkhangel'skii, A. V.; Pontryagin, L. S. (1990), General Topology I: Basic Concepts and Constructions Dimension Theory, Encyclopaedia of Mathematical Sciences, Springer, ISBN 3-540-18178-4