Distance algorithmique

En théorie de l'information, la distance algorithmique entre deux objets finis est le nombre de bits du programme le plus court qui transforme l'un des objets en l'autre sur un ordinateur universel. Elle s'appuie sur la complexité de Kolmogorov^{[note 1]}. En termes de contenu d’information, la distance algorithmique est l'information minimale nécessaire pour passer d'un objet à l'autre. Elle a été définie et étudiée en 1992 par Ming Li et Paul Vitanyi.

Propriétés

Définition

La distance d'information ${\displaystyle ID(x,y)}$ entre ${\displaystyle x}$ et ${\displaystyle y}$ est définie par ${\displaystyle ID(x,y)=\min\{|p|:p(x)=y\;\wedge \;p(y)=x\},}$ où ${\displaystyle p}$ est un programme pour un ordinateur universel fixé ayant pour entrées des chaînes binaires ${\displaystyle x,y}$.

Bennett et al. démontrent^[1] que ${\displaystyle ID(x,y)=E(x,y)+O(\log \cdot \max\{K(x\mid y),K(y\mid x)\})}$ avec ${\displaystyle E(x,y)=\max\{K(x\mid y),K(y\mid x)\},}$ où ${\displaystyle K}$ est la complexité de Kolmogorov^[2],[3] que l'on applique à la paire ${\displaystyle (\cdot \mid \cdot )}$^{[note 2]}. ${\displaystyle E(x,y)}$ est la quantité pertinente. En effet, le terme correctif sert à assurer qu'il s'agit bien d'une métrique.

Universalité

Soit ${\displaystyle \Delta }$ la classe des distances ${\displaystyle D(x,y)}$ semi-calculables supérieurement (en) qui satisfont la condition de densité : ${\displaystyle \sum _{x\neq y}2^{-D(x,y)}\leq 1,\;\sum _{y\neq x}2^{-D(x,y)}\leq 1.}$ Cela exclut les distances non pertinentes telles que ${\displaystyle D(x,y)={\frac {1}{2}}}$ pour ${\displaystyle x\neq y}$, et cela assure que si la distance augmente, alors le nombre d'objets à cette distance d'un objet donné augmente. Si ${\displaystyle D\in \Delta }$, alors ${\displaystyle E(x,y)\leq D(x,y)}$ à un terme additif constant près^[1]. Ces expressions probabilistes de la distance constituent la première classe cohomologique en cohomologie symétrique de l'information^[4],[5], ce qui peut être considéré comme une propriété d'universalité.

Métrique

La distance ${\displaystyle E(x,y)}$ est une métrique au terme additif ${\displaystyle O(\log \cdot \max {K(x\mid y),K(y\mid x)})}$ près^[1]. La version probabiliste de la métrique est unique comme l'a montré Te Sun Han en 1981^[6].

Chevauchement maximal

Si ${\displaystyle E(x,y)=K(x\mid y)}$, alors il existe un programme ${\displaystyle p}$ de longueur ${\displaystyle K(x\mid y)}$ qui convertit ${\displaystyle y}$ en ${\displaystyle x}$, et un programme ${\displaystyle q}$ de longueur ${\displaystyle K(y\mid x)-K(x\mid y)}$ tel que le programme ${\displaystyle qp}$ convertit ${\displaystyle x}$ en ${\displaystyle y}$. Les programmes sont écrits sous forme auto-délimitée, ce qui signifie que l'on peut décider où un programme se termine et où l'autre commence dans la concaténation des programmes, autrement dit les programmes les plus courts passant d'un objet à l'autre peuvent être rendus maximaux en chevauchement^[1].

Chevauchement minimal

Les programmes de conversion entre les objets ${\displaystyle x}$ et ${\displaystyle y}$ peuvent également être rendus minimalement chevauchants : il existe un programme ${\displaystyle p}$ de longueur ${\displaystyle K(x\mid y)}$ (à un terme additif en ${\displaystyle O(\log(\max {K(x\mid y),K(y\mid x)}))}$ près) qui transforme ${\displaystyle y}$ en ${\displaystyle x}$ et a une petite complexité lorsque ${\displaystyle x}$ est connu (${\displaystyle K(p\mid x)\approx 0}$). En intervertissant les deux objets, nous obtenons l'autre programme^[7]. En gardant à l'esprit le parallélisme entre la théorie de l'information (de Shannon) et la théorie de la complexité de Kolmogorov, on peut dire que ce résultat est analogue aux théorèmes de Slepian-Wolf (en) et de Körner–Imre Csiszár–Marton.

Applications

Applications théoriques

Le théorème d'Andrej Muchnik sur le chevauchement minimal^[7] montre qu'à partir de n'importe quel objet, pour aller vers un objet cible, il existe un programme dont la complexité de Kolmogorov ne dépend presque que de l'objet cible ! Ce résultat est à peu près optimal, car le terme d'erreur ne peut pas être significativement amélioré^[8].

Applications pratiques

Pour déterminer la similarité entre des objets tels que les génomes, les langues, la musique, les virus informatiques, les logiciels, etc., des approximations de la distance algorithmique^{[note 3]} sont proposées; la complexité de Kolmogorov est remplacée par un algorithme de compression existant réellement^{[note 4]}. Le concept est alors la distance de compression normalisée (en) (NCD) entre les objets, qui sont donnés sous forme de fichiers informatiques, ainsi le génome d'une souris, le texte d'un livre, la partition d'une œuvre musicale, etc. Partant d'un identifiant d'un objet comme le « génome d'une souris », l'utilisateur d'une base de données et d'un moyen de rechercher dans la base de données (comme un moteur de recherche) obtient sous forme indirecte cette information (par exemple en décomptant les pages liées à ce nom), et il est ensuite possible de calculer (approximativement) la distance algorithmique^[9].^[pas clair]