Le théorème du contraste relatif de Beyer et al. papier: «Sur le comportement surprenant des métriques de distance dans l'espace de grande dimension» trompeur?

Ceci est cité très souvent en mentionnant la malédiction de la dimensionnalité et va

(formule de droite appelée contraste relatif)

lim_{ré \to \infty} var (\frac{| | X_{ré} | |_{k}}{E [| | X_{ré} | |_{k}]}) = 0, alors : \frac{{ré}_{{max}_{ré}^{k}} - {ré}_{{min}_{ré}^{k}}}{{ré}_{{min}_{ré}^{k}}} \to 0

$\lim_{d\rightarrow \infty} \text{var} \left(\frac{||X_d||_k}{E[||X_d||_k]} \right) = 0, \text{then}: \frac{D_{\max^{k}_{d}} - D_{\min^{k}_{d}}}{D_{\min^{k}_{d}}} \rightarrow 0$

Le résultat du théorème montre que la différence entre les distances maximale et minimale à un point d'interrogation donné n'augmente pas aussi vite que la distance la plus proche de n'importe quel point dans un espace dimensionnel élevé. Cela rend une requête de proximité vide de sens et instable car il y a une mauvaise discrimination entre le voisin le plus proche et le plus éloigné.

lien

Pourtant, si l'on essaie réellement de calculer le contraste relatif pour les valeurs d'échantillon, cela signifie que l'on prend un vecteur contenant de très petites valeurs et calcule la distance au vecteur zéro et fait de même pour un vecteur contenant des valeurs beaucoup plus grandes, et on compare ensuite les valeurs pour une dimension de 3 et une dimension $10^9$ fois plus grande, on verra que, bien que le rapport diminue, le changement est si petit qu'il est sans pertinence pour le nombre de dimensions réellement utilisées dans la pratique (ou quelqu'un connaît-il quelqu'un qui travaille avec des données avec des dimensions la taille du nombre de Graham - qui, je suppose, est la taille nécessaire pour que l'effet décrit le document soit réellement pertinent - je ne pense pas).

Comme mentionné précédemment, ce théorème est très souvent cité pour soutenir l'affirmation selon laquelle la mesure de la proximité basée sur l'espace euclidien est une mauvaise stratégie dans un espace de grande dimension, les auteurs le disent eux-mêmes, et pourtant le comportement proposé n'a pas réellement lieu, ce qui me rend pense que ce théorème a été utilisé de manière trompeuse.

Exemple: avec dla dimension

a=np.ones((d,)) / 1e5
b=np.ones((d,)) * 1e5
dmin,dmax=norm(a), norm(b)
(dmax-dmin)/dmin

pour d = 3
9999999999.0
pour d = 1e8
9999999998.9996738

Et avec 1e1 au lieu de 1e5 (disons que les données sont normalisées)
pour d = 3
99.0
pour d = 1e8
98.999999999989527

machine-learning distance-functions high-dimensional Nimitz14
la source

Comment avez-vous obtenu un échantillon de données dans la dimension ? Vous confondez peut-être "dimension" avec "échelle"?

3 + 10^{9}

$3 + 10^9$

whuber

Avez-vous vérifié l'état de l'écart?

Aksakal

Non, le théorème n'est pas trompeur. Cela peut certainement être appliqué incorrectement, mais c'est vrai pour n'importe quel théorème.

Voici un simple script MATLAB pour montrer comment cela fonctionne:

xd = randn(1e5,10000);
%%
cols = [1,10,100,1000,10000];
for c = cols
    xdt = table(xd(:,1:c));
    res = table2array(rowfun(@norm,xdt));
    mr = mean(res);
    res1 = var(res/mr);
    res2 = (max(res) - min(res))/min(res);
    fprintf('res1: %f, res2: %f\n',res1,res2)
end

Le résultat:

res1: 0.568701, res2: 2562257.458668
res1: 0.051314, res2: 9.580602
res1: 0.005021, res2: 0.911065
res1: 0.000504, res2: 0.221981
res1: 0.000050, res2: 0.063720

Dans mon code res1 et res2 sont les deux expressions de votre équation du papier: une pour la variance et la seconde pour le contraste.

Vous pouvez voir comment les deux vont à zéro comme prévu lorsque les dimensions vont de 1 à 10 000.

Aksakal
la source

Maintenant, je pense que la question devient: pour quelles distributions d'où Xvient la variance aller à zéro?

Nimitz14

@ Nimitz14 Ce serait une excellente question à poser à part entière.

Sycorax dit Réintégrer Monica

@ Nimitz14 ce théorème ne devrait pas fonctionner pour Cauchy, vous pouvez le tester facilement en remplaçant normal par étudiant t (1). Sinon, je pense que toutes les distributions régulières telles que normal, uniforme, beta etc. devraient être couvertes.

Aksakal

Le théorème du contraste relatif de Beyer et al. papier: «Sur le comportement surprenant des métriques de distance dans l'espace de grande dimension» trompeur?

Réponses: