Dimensions supérieures et distances

Il y a beaucoup de contextes en informatique, notamment en intelligence artificielle, où on voudrait pouvoir dire que deux objets sont semblables, en ayant une vision précise de ce que "semblable" veut dire. C'est ce qui permet par exemple à un algorithme de déterminer d'après une photo si elle représente un chat ou un chien. Pour y enir nous alons nous intéresser à la notion de distance en partant de ce qui vous a déjà été présenté.

Distance entre des points

Soient 2 points du plan \(A(a_0,a_1)\) et \(B(b_0, b_1)\) du plan

Pythagore nous dit que:

\[AB^2 = AH^2 + BH^2\]

donc :

\[ d(A, B) = \sqrt{(b_0 - a_0)^2 + (b_1 - a_1)^2} \]

où on notera toujours \(d(A, B)\) la distance entre \(A\) et \(B\).

Il est ici facile de concevoir que les points sont semblables si la distance est très petite. Plus la distance augmente, plus les 2 points nous paraissent dissemblables.

Maintenant, supposons que nous ayons 2 points A et B en dimension 3. Pythagore vient encore à la rescousse.

C'est exactement le même raisonnement, d'abord dans \(\triangle AMN\) pour obtenir \(AN^2\), puis dans \(\triangle ANB\) pour obtenir \(AB^2\).

On obtient alors:

\[ d(A, B) = \sqrt{(b_0 - a_0)^2 + (b_1 - a_1)^2 + (b_2 - a_2)^2} \]

Jusqu'à ce point, nous pouvons faire appel au sens de la vue pour déterminer si des choses sont proches ou pas et nous avons besoin de l'espace qui nous entoure pour concevoir cette distance physique.

Distances entre des fleurs

Prenons maintenant un ensemble de fleurs de 3 variétés différentes (des Iris) dont nous avons mesuré, pour chacune, 5 informations:

• L'espèce
• La longueur et la largeur des sépales
• La longueur et la largeur des pétales

Tout d'abord dressons une représentation graphique de la largeur des sépales en fonction de la longueur des sépales.

Chaque point sur ce graphique représente une fleur. Ces fleurs ne sont pas positionnées réellement dans le plan, ce sont des caractéristiques de ces fleurs qui sont dans ce plan, et ça ne gêne personne.

Lorsqu'on considère 2 fleurs proches dans le plan, il n'est pas difficile de s'imaginer qu'elles auront des sépales qui se ressembleront plus que deux fleurs qui sont plus éloignées l'une de l'autre.

Cependant, ici, nous ne considérons que les sépales, et pas la fleur dans son intégralité. Nous allons rajouter l'information de la largeur des pétales.

On commence à distinguer visuellement un groupe de fleurs qui se détache. Nous avons aussi l'information, pour chaque fleur, de sa variété. Il s'agit des variétés Setosa, Verticolor et Virginica. Colorions les avec des couleurs différentes.

Nous voyons maintenant distinctement 3 groupes se former sous nos yeux, car notre cerveau est capable d'estimer la distance entre ces groupes. On voit que le groupe 2 est "loin" des 2 autres, qui sont "collés". On se dit que les fleurs qui sont éloignées sont dissimilaires. Il ne s'agit pas de distance par rapport à la localisation, mais de distance par rapport à des caractéristiques choisies des fleurs. MAIS, il y a toujours une information qui nous manque visuellement pour avoir une idée de nos données, il s'agit ici de la longueur des pétales. Or nous avons épuisé les 3 dimensions physiques et la coloration, et nous savons que l'ajout d'une dimension peut bouleverser la donne. Ne vous fatiguez pas, il n'existe pas de magie pour "voir" les 4 dimensions numériques et ainsi pouvoir renouveler l'expérience de la distance visuelle en "voyant" des groupes se distinguer. Toute représentation graphique n'est qu'une projection de la réalité avec perte d'information. En réalité, rien ne nous empêche de caractériser les fleurs avec l'ensemble de leurs coordonnées dans un espace de dimension supérieure, même si on ne peut pas le voir avec nos yeux. Très basiquement, la dimension d'un ensemble d'éléments est le nombre de coordonnées dont vous avez besoin pour identifier un de ses éléments. Dans nos données, une fleur est identifiée par 5 coordonnées. La dimension de notre ensemble de fleurs est donc 5.

Note: Dans le dernier graphique, nous voyons une projection en dimension 2 (l'écran ou la feuille) d'une projection en dimension 4 (Spatialement 3 dimensions, plus une dimension de couleur) de la totalité des données en dimension 5.

Distances en dimension \(n\)

Oublions la dimension de la variété, concentrons nous sur les 4 coordonnées numériques et revenons à notre notion de distance. Comment établir une distance dans un espace à 4 dimensions?

En dimension 2, pour deux points \(A(a_0, a_1)\) et \(B(b_0, b_1)\) $$ d(A, B) = \sqrt{(b_0 - a_0)^2 + (b_1 - a_1)^2} $$

En dimension 3, pour deux points \(A(a_0, a_1, a_2)\) et \(B(b_0, b_1, b_2)\) $$ d(A, B) = \sqrt{(b_0 - a_0)^2 + (b_1 - a_1)^2 + (b_2 - a_2)^2} $$

En dimension 4, nous généralisons le principe pour \(A(a_0, a_1, a_2, a_3)\) et \(B(b_0, b_1, b_2, b_3)\)

\[ d(A, B) = \sqrt{(b_0 - a_0)^2 + (b_1 - a_1)^2 + (b_2 - a_2)^2 + (b_3 - a_3)^2} \]

Allons-y gaiement, pour un espace de dimension \(n\), pour \(A(a_0, ..., a_{n-1})\) et \(B(b_0, ..., b_{n-1})\)

\[ d(A, B) = \sqrt{(b_0 - a_0)^2 + ... + (b_{n-1} - a_{n-1})^2} \]

Autrement posé:

\[ d(A,B)=\sqrt{\sum_{i=0}^{n-1} (b_i-a_i)^2} \]

Bien sûr, le fait que nous généralisions aussi facilement n'est pas une garantie que la notion résultante est une définition "sensée" d'une distance. Ça soulève la question des propriétés que nous estimons nécessaires à la définition d'une distance pour qu'elle ait un sens, celui de la caractérisation d'une "proximité".

Soit X un ensemble de "points". Supposons qu'étant donnés 2 de ces points A et B, nous avons une manière d'assigner un nombre réel \(d(A, B)\) qu'on souhaiterait être la distance entre ces points. Les propriétés suivantes doivent être respectées pour que \(d\) soit une distance:

\[ \forall(A,B,C) \in X^3 \begin{cases} P_1: d(A, B) \ge 0 \\ P_2: d(A, B)=0 \iff A=B \\ P_3: d(A, B)=d(B, A) \\ P_4: d(A, B) + d(B, C) \ge d(A,C) \end{cases} \]

Dans un ensemble quelconque, n'importe quelle fonction qui satisfait à ces propriétés est, par définition, une distance. \(P_1\) et \(P_2\) signifient que la distance entre deux points est toujours positive (elle est définie positive), sauf quand les deux points sont égaux, ce qui équivaut à une distance de 0. \(P_3\) dit que la distance est une notion symétrique, c'est à dire que la distance entre A et B est la même qu'entre B et A. \(P_4\) s'appelle l'inégalité triangulaire. Si vous imaginez A, B et C comme les sommets d'un triangle, ça dit que si vous prenez la somme des longueurs de deux côtés, elle sera toujours supérieure ou égale à la longueur du côté restant.

La notion physique de distance entre deux objets n'est qu'un cas très particulier de distance.

Exemples de distances

La distance Euclidienne

C'est celle dont nous avons parlé tout du long. Si un élément d'un ensemble a pour coordonnées des éléments de \(\mathbb{R}\), alors les formules dérivées du théorème de Pythagore donnent une notion de distance conforme aux propriétés. L'ensemble muni de cette distance est alors appelé Espace Euclidien.

\[ d(A,B)=\sqrt{\sum_{i=0}^{n-1} (b_i-a_i)^2} \]

La distance de Manhattan

Là où la distance Euclidienne calcule la longueur du "vol d'oiseau" (le segment bleu), la distance de Manhattan calcule la longueur en rouge. Elle s'appelle ainsi car, les rues de Manhattan étant perpendiculaires, ça correspond à la longueur du trajet réel pour y marcher d'un point \(A\) à un point \(B\).

Sur le dessin, la distance de manhattan entre A et B est 14.

\[ d(A,B)=\sum_{i=0}^{n-1} |b_i-a_i| \]

Distance entre des chaînes de caractères

L'information est transmise aujourd'hui sous forme de 0 et de 1, comme "00111010010". La distance de Hamming entre deux de ces chaîne de caractères, de même taille, est définie comme le nombre de caractères qu'il faut modifier dans une chaîne pour obtenir l'autre. Par exemple, la distance entre les chaînes "00111010010" et "00100101" est 2, car il faut modifier les caractères aux indices 3 et 7 seulement. Il existe une autre distance plus poussée entre les chaînes de caractères utilisées dans les correcteurs orthographiques qui s'appelle la distance de Levenshtein. Elle prend en compte le nombre minimum d'ajouts, de suppressions et de remplacement de caractères pour obtenir l'autre chaîne. Lorsque votre correcteur orthographique souligne un mot en rouge, c'est qu'il ne le trouve pas dans le dictionnaire. Il vous propose alors les mots les plus similaires, ceux pour lesquels la distance de levenshtein est la plus petite.

La distance \(\tau\) de Kendall

Elle est utilisée en bio-informatique dans la comparaison de séquences génétiques, ainsi que plus généralement dans les problémes de classement. C'est une distance entre des listes. Elle est équivalente au nombre d'échanges nécessaires à l'algorithme de tri à bulle pour passer d'une liste à l'autre.

La distance de Minkowski

C'est une généralisation de la distance Euclidienne et de la distance de Manhattan.

La distance Euclidienne en dimension n peut se réécrire ainsi:

\[ d(A,B)=\left(\sum_{i=0}^{n-1} (b_i-a_i)^2 \right)^{1/2} \]

Minkowski propose de généraliser à la distance d'ordre \(p\):

\[ d(A,B)=\left(\sum_{i=0}^{n-1} |b_i-a_i|^p \right)^{1/p} \]

Sa seule existence permet d'affirmer qu'il existe une infinité de fonctions de distances possibles, attendu que le domaine de valeurs de \(p\) est infini.

On l'appelle la distance de Minkowski d'ordre \(p \in \mathbb{R}, p \ge 1\). Quand \(p<1\), la fonction viole l'inégalité triangulaire et ça n'est donc pas une distance, c'est alors une pseudo-distance.

• La distance de Minkowski d'ordre 1 est la distance de Manhattan.
• La distance de Minkowski d'ordre 2 est la distance Euclidienne.
• Sa limite quand \(p\) tend vers \(+\infin\) est appelée distance de Tchebychev.

Plus \(p\) est grand, plus on donne de l'importance aux grandes différences entre coordonnées. Faire varier \(p\) permet d'ajuster la sensibilité des modèles qu'on cherche à construire.

Distance de Tchebychev

La distance de Tchebychev est équivalente au plus grand écart entre chaques coordonnées de deux points. On l'appelle aussi distance de l'échiquier car c'est le nombre de tours minimal qu'il faut à un roi pour atteindre une case d'un échiquier à partir de sa position courante. Elle s'écrit aussi sous une forme plus simple que la limite de la distance de Minkowski:

\[ d(A, B) = \max_{0\le i <n}\, |b_i-a_i| \]