Ist der relative Kontrastsatz von Beyer et al. Papier: "Über das überraschende Verhalten von Distanzmetriken im hochdimensionalen Raum" irreführend?

Dies wird sehr oft zitiert, wenn der Fluch der Dimensionalität erwähnt wird und geht

(rechte Formel genannt relativer Kontrast)

lim_{d \to \infty} var (\frac{| | X_{d} | |_{k}}{E [| | X_{d} | |_{k}]}) = 0, then : \frac{D_{{max}_{d}^{k}} - D_{{min}_{d}^{k}}}{D_{{min}_{d}^{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$

Das Ergebnis des Theorems zeigt, dass die Differenz zwischen dem maximalen und dem minimalen Abstand zu einem bestimmten Abfragepunkt nicht so schnell zunimmt wie der nächste Abstand zu einem Punkt im hochdimensionalen Raum. Dies macht eine Annäherungsabfrage bedeutungslos und instabil, da zwischen dem nächsten und dem am weitesten entfernten Nachbarn nur eine geringe Unterscheidung besteht.

Verknüpfung

Wenn man jedoch tatsächlich versucht, den relativen Kontrast für Stichprobenwerte zu berechnen, bedeutet dies, dass man einen Vektor mit sehr kleinen Werten nimmt und den Abstand zum Nullvektor berechnet und dasselbe für einen Vektor mit viel größeren Werten tut, und man vergleicht dann die Werte für Bei einer Dimension von 3 und einer Dimension, die $10^9$ Mal größer ist, wird man sehen, dass die Änderung zwar abnimmt, die Änderung jedoch so verschwindend gering ist, dass sie für die Anzahl der tatsächlich in der Praxis verwendeten Dimensionen irrelevant ist (oder kennt jemand jemanden, der arbeitet) Bei Daten mit Abmessungen ist die Größe von Grahams Zahl - was meiner Meinung nach die Größe ist, die erforderlich ist, damit der beschriebene Effekt das Papier tatsächlich relevant macht - glaube ich nicht.

Wie bereits erwähnt, wird dieser Satz sehr oft zitiert, um die Aussage zu stützen, dass die Messung der Nähe auf der Grundlage des euklidischen Raums eine schlechte Strategie in einem hochdimensionalen Raum ist, sagen die Autoren selbst, und dennoch findet das vorgeschlagene Verhalten nicht tatsächlich statt, was mich dazu veranlasst Ich denke, dieser Satz wurde irreführend verwendet.

Beispiel: mit dder Dimension

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

für d = 3
9999999999.0
für d = 1e8
9999999998.9996738

Und mit 1e1 anstelle von 1e5 (sagen wir, die Daten sind normalisiert)
für d = 3
99.0
für d = 1e8
98.999999999989527

machine-learning distance-functions high-dimensional Nimitz14
quelle

Wie haben Sie eine Datenstichprobe in Dimension ? Verwechseln Sie vielleicht "Dimension" mit "Skala"?

3 + 10^{9}

$3 + 10^9$

whuber

Haben Sie die Bedingung für die Varianz überprüft?

Aksakal

Nein, der Satz ist nicht irreführend. Es kann sicherlich falsch angewendet werden, aber das gilt für jeden Satz.

Hier ist ein einfaches MATLAB-Skript, um zu demonstrieren, wie es funktioniert:

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

Die Ausgabe:

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

In meinem Code res1 und res2 sind die beiden Ausdrücke in Ihrer Gleichung aus dem Papier: einer für die Varianz und der zweite für den Kontrast.

Sie können sehen, wie beide wie angenommen auf Null gehen, wenn die Abmessungen von 1 auf 10.000 gehen.

Aksakal
quelle

Jetzt fühle ich mich die Frage, für welche Verteilungen, von denen Xdie Varianz auf Null geht?

Nimitz14

@ Nimitz14 Das wäre eine ausgezeichnete Frage für sich.

Sycorax sagt Reinstate Monica

@ Nimitz14 Dieser Satz sollte für Cauchy nicht funktionieren. Sie können ihn leicht testen, indem Sie normal durch student t (1) ersetzen. Ansonsten denke ich, dass alle regulären Distributionen wie Normal, Uniform, Beta usw. abgedeckt werden sollten.

Aksakal

Ist der relative Kontrastsatz von Beyer et al. Papier: "Über das überraschende Verhalten von Distanzmetriken im hochdimensionalen Raum" irreführend?

Antworten: