Czy twierdzenie o względnym kontraście z Beyer i in. artykuł: „O zaskakującym zachowaniu wskaźników odległości w przestrzeni wielowymiarowej” wprowadzający w błąd?

Jest to często cytowane, gdy wspomina się o przekleństwie wymiarowości i odchodzi

(formuła z prawej strony zwana kontrastem względnym)

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$

Wynik twierdzenia pokazuje, że różnica między maksymalnymi i minimalnymi odległościami do danego punktu zapytania nie rośnie tak szybko, jak najbliższa odległość do dowolnego punktu w przestrzeni o dużych wymiarach. To sprawia, że zapytanie zbliżeniowe nie ma znaczenia i jest niestabilne, ponieważ istnieje słaba dyskryminacja między najbliższym a najdalszym sąsiadem.

połączyć

Jednak jeśli ktoś faktycznie próbuje obliczyć względny kontrast dla wartości próbki, to znaczy bierze wektor zawierający bardzo małe wartości i oblicza odległość do wektora zerowego i robi to samo dla wektora zawierającego znacznie większe wartości, a następnie porównuje wartości dla wymiar 3 i wymiar $10^9$ razy większy, można zauważyć, że chociaż współczynnik maleje, zmiana jest tak znikomo mała, że nie ma znaczenia dla liczby wymiarów faktycznie stosowanych w praktyce (lub czy ktoś zna kogoś pracującego z danymi o wymiarach rozmiar liczby Grahama - który, jak sądzę, jest rozmiarem potrzebnym, aby efekt opisany w dokumencie był rzeczywiście istotny - nie sądzę).

Jak wspomniano wcześniej, to twierdzenie jest bardzo często cytowane w celu poparcia twierdzenia, że pomiar bliskości w oparciu o przestrzeń euklidesową jest złą strategią w przestrzeni wielowymiarowej, autorzy twierdzą, że tak, a mimo to proponowane zachowanie nie ma miejsca, co czyni mnie myślę, że to twierdzenie zostało zastosowane w sposób wprowadzający w błąd.

Przykład: z dwymiarem

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

dla d = 3
9999999999.0
dla d = 1e8
9999999998.9996738

I z 1e1 zamiast 1e5 (powiedzmy, że dane są znormalizowane)
dla d = 3
99.0
dla d = 1e8
98.999999999989527

machine-learning distance-functions high-dimensional Nimitz14
źródło

Jak uzyskano próbkę danych w wymiarze ? Czy może mylicie „wymiar” z „skalą”?

3 + 10^{9}

$3 + 10^9$

whuber

Czy sprawdziłeś warunek wariancji?

Aksakal,

Nie, twierdzenie to nie wprowadza w błąd. Z pewnością można go zastosować nieprawidłowo, ale dotyczy to każdego twierdzenia.

Oto prosty skrypt MATLAB, który pokazuje, jak to działa:

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

Wyjście:

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

W moim kodzie res1 i res2 to dwa wyrażenia w twoim równaniu z papieru: jedno dla wariancji, a drugie dla kontrastu.

Możesz zobaczyć, jak oba idą do zera, jak powinno, gdy wymiary zwiększają się od 1 do 10 000.

Aksakal
źródło

Teraz czuję, że Xpowstaje pytanie, dla jakich rozkładów, z których pochodzi wariancja, spada do zera?

Nimitz14,

@ Nimitz14 To samo byłoby doskonałe pytanie.

Sycorax mówi Przywróć Monikę

@ Nimitz14 to twierdzenie nie powinno działać dla Cauchy'ego, możesz je łatwo przetestować, zastępując normalne uczniem t (1). W przeciwnym razie uważam, że należy uwzględnić wszystkie regularne dystrybucje, takie jak normalne, jednolite, beta itp.

Aksakal,

Czy twierdzenie o względnym kontraście z Beyer i in. artykuł: „O zaskakującym zachowaniu wskaźników odległości w przestrzeni wielowymiarowej” wprowadzający w błąd?

Odpowiedzi: