Odległość euklidesowa zwykle nie jest dobra dla rzadkich danych?

Widziałem gdzieś, że klasyczne odległości (takie jak odległość euklidesowa) stają się słabo dyskryminujące, gdy mamy wielowymiarowe i rzadkie dane. Dlaczego? Czy masz przykład dwóch rzadkich wektorów danych, w których odległość euklidesowa nie działa dobrze? W takim przypadku, jakiego podobieństwa powinniśmy użyć?

Oto prosty przykład zabawki ilustrujący wpływ wymiaru na problem dyskryminacji, np. Problem, z którym się zmagasz, gdy chcesz powiedzieć, czy coś jest obserwowane lub czy zaobserwowano tylko efekt losowy (ten problem jest klasyczny w nauce).

Heurystyczny. Kluczową kwestią jest tutaj to, że norma euklidesowa przywiązuje taką samą wagę do każdego kierunku. Stanowi to brak wcześniejszego, a jak z pewnością wiesz w dużym wymiarze, nie ma darmowego lunchu (tj. Jeśli nie masz wcześniejszego pojęcia, czego szukasz, to nie ma powodu, dla którego hałas nie wyglądałby tak jak jesteś szukanie, to jest tautologia ...).

Powiedziałbym, że w przypadku każdego problemu istnieje limit informacji niezbędnych do znalezienia czegoś innego niż hałas. Limit ten jest w jakiś sposób związany z „rozmiarem” obszaru, który próbujesz zbadać w odniesieniu do poziomu „szumu” (tj. Poziomu treści nieinformacyjnych).

W dużym wymiarze, jeśli masz wcześniejszy sygnał, że twój sygnał jest rzadki, możesz usunąć (tj. Ukarać) rzadki wektor za pomocą metryki, która wypełnia przestrzeń rzadkim wektorem lub za pomocą techniki progowej.

Framework Załóżmy, że jest wektorem gaussowskim o średnim i przekątnej kowariancji ( jest znany) i że chcesz przetestować prostą hipotezęν σ I d $\xi$$\nu$$\sigma Id$$\sigma$

θ ∈ R n

Testuj statystyki energią . Intuicja, którą z pewnością masz, polega na tym, że dobrym pomysłem jest ocena normy / energii twojej obserwacji aby zbudować statystykę testową. W rzeczywistości można zbudować znormalizowaną, wyśrodkowaną (pod ) wersję energii . To sprawia, że ​​region krytyczny na poziomie formy dla dobrze wybranego ξH0TnTn=∑iξ 2 i -σ$\mathcal{E}_n=\frac{1}{n}\sum_{i=1}^n\xi_i^2$$\xi$$H_0$$T_n$ α{Tn≥v1-α}v1-$T_n=\frac{\sum_i\xi_i^2-\sigma^2}{\sqrt{2n\sigma^4}}$$\alpha$$\{T_n\geq v_{1-\alpha}\}$$v_{1-\alpha}$

Moc testu i wymiar. W takim przypadku jest to proste ćwiczenie prawdopodobieństwa, aby pokazać następującą formułę mocy testu:

ZnE[Z]=0Var(Z)=

$$P_{\theta}(T\leq v_{1-\alpha})=P\left (Z\leq \frac{v_{1-\alpha}}{\sqrt{1+2\|\theta\|_2^2/(n\sigma^2)}}-\frac{\|\theta\|^2_2}{\sqrt{2n\sigma^4+2\sigma^2\|\theta\|_2^2/(n\sigma^2)}}\right )$$ z suma iid zmiennych losowych z i .$Z$$n$$\mathbb{E}[Z]=0$$Var(Z)=1$

Oznacza to, że moc twojego testu jest zwiększana przez energię twojego sygnału i zmniejszana o . Praktycznie oznacza to, że gdy zwiększa się rozmiar Twojego problemu, jeśli nie zwiększa siłę sygnału w tym samym czasie, a następnie dodajesz uninformative informacje do obserwacji (lub jesteś zmniejszenie odsetka użytecznych informacji w informacji masz): to jest jak dodawanie hałasu i zmniejsza moc testu (tzn. jest bardziej prawdopodobne, że powiesz, że nic nie jest obserwowane, podczas gdy w rzeczywistości coś jest). n $\|\theta\|^2_2$$n$$n$

W kierunku testu ze statystyką progową. Jeśli nie masz dużo energii w swoim sygnale, ale znasz liniową transformację, która może pomóc ci skoncentrować tę energię w małej części twojego sygnału, możesz zbudować statystykę testową, która będzie oceniać energię tylko dla małej część twojego sygnału. Jeśli wiesz z góry, gdzie jest ono skoncentrowane (na przykład wiesz, że w twoim sygnale nie może być wysokich częstotliwości), możesz uzyskać moc w poprzednim teście, gdzie zastąpione małą liczbą, a prawie to samo ... Jeśli nie wiesz tego z góry, musisz to oszacować, co prowadzi do dobrze znanych testów progowych.‖ θ ‖ 2 $n$$\|\theta\|^2_2$

Zauważ, że ten argument jest dokładnie u podstaw wielu dokumentów, takich jak

• A Antoniadis, F Abramowicz, T Sapatinas i B. Vidakovic. Metody falkowe do testowania w analizie funkcjonalnej modeli wariancyjnych. International Journal on Wavelets i jego zastosowania, 93: 1007–1021, 2004.
• MV Burnashef i Begmatov. Problem wykrycia sygnału prowadzący do stabilnej dystrybucji. Teoria prawdopodobieństwa i jej zastosowania, 35 (3): 556–560, 1990.
• Y. Baraud. Niesymptotyczna minimalna szybkość testowania w wykrywaniu sygnału. Bernoulli, 8: 577–606, 2002.
• J Fan. Test istotności oparty na progowaniu falkowym i obcinaniu neymana. JASA, 91: 674–688, 1996.
• J. Fan i SK Lin. Test znaczenia, gdy dane są krzywymi. JASA, 93: 1007–1021, 1998.
• V. Spokoiny. Adaptacyjne testowanie hipotez za pomocą falek. Annals of Statistics, 24 (6): 2477–2498, grudzień 1996.

Uważam, że to nie tyle rzadkość, co wysoka wymiarowość zwykle związana z rzadkimi danymi. Ale może jest jeszcze gorzej, gdy dane są bardzo rzadkie. Ponieważ wtedy odległość dowolnych dwóch obiektów będzie prawdopodobnie kwadratową średnią ich długości lub

To równanie jest trywialne, jeśli . Jeśli zwiększysz wymiarowość i rozrzedzenie wystarczająco, aby obejmowało prawie wszystkie atrybuty, różnica będzie minimalna.$\forall_i x_i=0 \vee y_i=0$

Co gorsza: jeśli znormalizujesz swoje wektory, aby miały długość , wówczas odległość euklidesowa dowolnych dwóch obiektów będzie z dużym prawdopodobieństwem .$||x||=1$$\sqrt{2}$

Zasadniczo więc, aby odległość euklidesowa była użyteczna (nie twierdzę, że jest użyteczna lub znacząca), obiekty powinny być niezerowe w atrybutów. Wtedy powinna istnieć rozsądna liczba atrybutów, w którychwięc różnica wektora staje się użyteczna. Dotyczy to również każdej innej różnicy wywołanej normą. Ponieważ w powyższej sytuacji$3/4$$|y_i| \neq |x_i-y_i| \neq |x_i|$$|x-y| \rightarrow_p |x + y|$

Nie wydaje mi się, aby było to pożądane zachowanie funkcji odległości w dużej mierze niezależnych od rzeczywistej różnicy lub różnicy absolutnej zbliżającej się do sumy absolutnej!

Częstym rozwiązaniem jest stosowanie odległości takich jak odległość Cosinus. W przypadku niektórych danych działają one bardzo dobrze. Z grubsza mówiąc, patrzą tylko na atrybuty, w których oba wektory są niezerowe. Ciekawe podejście omówiono w poniższym piśmiennictwie (nie wymyślili go, ale podoba mi się ich eksperymentalna ocena właściwości) polega na użyciu wspólnych najbliższych sąsiadów. Więc nawet jeśli wektory xiy nie mają wspólnych atrybutów, mogą mieć wspólnych sąsiadów. Zliczanie liczby obiektów łączących dwa obiekty jest ściśle związane z odległościami na wykresie.

Dużo dyskusji dotyczy funkcji odległości w:

• Czy odległości dzielone przez sąsiadów mogą pokonać przekleństwo wymiaru?
  ME Houle, H.-P. Kriegel, P. Kröger, E. Schubert i A.
  Zimek SSDBM 2010

a jeśli nie wolisz artykułów naukowych, również na Wikipedii: Curse of Dimensionality

Sugerowałbym rozpoczęcie od odległości Cosinus , a nie euklidesowej, dla wszystkich danych z większością wektorów prawie ortogonalnych, 0. Aby zobaczyć dlaczego, spójrz na . Jeśli 0, zmniejsza się to do : marna miara odległości, jak wskazuje Anony-Mousse.$x \cdot y \approx$
$|x - y|^2 = |x|^2 + |y|^2 - 2\ x \cdot y$
$x \cdot y \approx$$|x|^2 + |y|^2$

Odległość cosinus polega na użyciulub rzutowanie danych na powierzchnię kuli jednostkowej, więc wszystkie= 1. Zatem to zupełnie inna i zwykle lepsza metryka niż zwykły euklides. może być mały, ale nie jest maskowany przez głośne .$x / |x|$$|x|$$|x - y|^2 = 2 - 2\ x \cdot y$
$x \cdot y$$|x|^2 + |y|^2$

$x \cdot y$ jest prawie bliski zeru dla rzadkich danych. Na przykład, i mają po 100 terminów niezerowych 900 zer, to obie są niezerowe tylko w 10 warunkach (jeśli niezerowe warunki rozpraszają losowo).$x$$y$

Normalizowanie / =może być powolny w przypadku rzadkich danych; jest szybki w scikit-learn .$x$$|x|$

Podsumowanie: zacznij od odległości cosinusowej, ale nie oczekuj cudów na starych danych.
Pomyślne pomiary wymagają oceny, strojenia, znajomości domeny.

Częścią przekleństwa wymiarowości jest to, że dane zaczynają się rozprzestrzeniać z dala od centrum. Dotyczy to normalnej wielowymiarowej normalnej, a nawet gdy komponentami są IID (normalna sferyczna). Ale jeśli chcesz ściśle mówić o odległości euklidesowej, nawet w małej przestrzeni wymiarowej, jeśli dane mają strukturę korelacji, odległość euklidesowa nie jest odpowiednią miarą. Jeśli przypuszczamy, że dane są wielowymiarowe normalne z pewnymi niezerowymi kowariancjami i dla celów argumentu załóżmy, że znana jest macierz kowariancji. Zatem odległość Mahalanobisa jest odpowiednią miarą odległości i nie jest taka sama jak odległość euklidesowa, do której zmniejszyłaby się tylko, gdyby macierz kowariancji była proporcjonalna do macierzy tożsamości.

Wierzę, że jest to związane z przekleństwem wymiarowości / koncentracji miary, ale nie mogę już znaleźć dyskusji, która uzasadnia tę uwagę. Wydaje mi się, że na metaoptimize pojawił się wątek, ale nie udało mi się go Google ...

W przypadku danych tekstowych normalizacja wektorów za pomocą TF-IDF, a następnie zastosowanie podobieństwa kosinusowego prawdopodobnie przyniesie lepsze wyniki niż odległość euklidesowa, ponieważ długie dokumenty (z wieloma słowami) mogą mieć te same tematy, a zatem są bardzo podobne do krótkich dokumentów o dużej liczbie wspólnych słowa. Odrzucenie normy wektorów pomaga w tym konkretnym przypadku.

Aksjomatyczną miarą rzadkości jest tak zwana liczba , która zlicza (skończoną) liczbę niezerowych wpisów w wektorze. Za pomocą tej miary wektory i mają tę samą rzadkość. I absolutnie nie ta sama norma. I (bardzo rzadki) ma takie samo normę , bardzo płaski, nieliczny wektor. I absolutnie nie ta sama liczba.$\ell_0$$(1,0,0,0)$$(0,21,0,0)$$\ell_2$$(1,0,0,0)$$\ell_2$$\left(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}\right)$$\ell_0$

Ta funkcja, ani norma, ani quasinorm, nie jest gładka i nie wypukła. W zależności od dziedziny jej nazwy to legion, na przykład: funkcja liczności, miara liczebności lub po prostu parsymonia lub rzadkość. Jest to często uważane za niepraktyczne ze względów praktycznych, ponieważ jego stosowanie prowadzi do trudnych problemów NP .

Podczas gdy standardowe odległości lub normy (takie jak odległość ) są bardziej przystępne, jednym z ich problemów jest ich -jednorodność:dla . Może to być postrzegane jako nieintuicyjne, ponieważ iloczyn skalarny nie zmienia proporcji zerowych wpisów w danych ( jest -jednorodny). 1 ‖ a . x ‖ = | a | ‖ X ‖ a ≠ 0 ℓ 0$\ell_2$$1$

Tak więc, w praktyce, niektóre z nich na kombinacje ( ), takie jak regulacje lasso, kalenica lub elastyczna siatka. Szczególnie norma (odległość Manhattan lub taksówka) lub jej wygładzone awatary. Od prac E. Candèsa i innych można wyjaśnić, dlaczego jest dobrym przybliżeniem do : objaśnienie geometryczne . Inni zrobili w , za cenę problemów .p ≥ 1 ℓ 1 ℓ 1 ℓ 0 p < 1 ℓ p ( x $\ell_p(x)$$p \ge1$$\ell_1$$\ell_1$$\ell_0$$p < 1$$\ell_p(x)$

Inną interesującą ścieżką jest ponowna aksjomizacja pojęcia rzadkości. Jednym z ostatnich godnych uwagi prac jest „ Porównywanie miar rzadkości” autorstwa N. Hurleya i in., Zajmujących się rzadkością dystrybucji. Z sześciu aksjomatów (o śmiesznych nazwach, takich jak Robin Hood, Skalowanie, Rising Tide, Cloning, Bill Gates i Babies), pojawiło się kilka indeksów rzadkości: jeden oparty na indeksie Giniego, drugi oparty na wskaźnikach norm, zwłaszcza jeden ponad two stosunek norm, pokazany poniżej:$\frac{\ell_1}{\ell_2}$

Chociaż nie jest wypukła, niektóre dowody zbieżności i kilka odniesień historycznych są wyszczególnione w Euklidesa w taksówce: Sparse Blind Dekonwolucja z wygładzone regularyzacji$\frac{\ell _1}{\ell_2}$ .

W artykule o zaskakującym zachowaniu wskaźników odległości w przestrzeni wielowymiarowej omawia się zachowanie wskaźników odległości w przestrzeniach wielowymiarowych.

Biorą na normy i zaproponować manhattan normę jako najbardziej skuteczny w dużych przestrzeniach wymiarowych dla celów grupowania. Wprowadzają także normę ułamkową podobną do normy ale z .$L_k$L f L k f ∈ ( 0..1 $L_1$ $L_f$$L_k$$f \in (0..1)$

Krótko mówiąc, pokazują, że w przypadku przestrzeni o dużych wymiarach stosowanie normy euklidesowej jako domyślnej prawdopodobnie nie jest dobrym pomysłem; zwykle mamy mało intuicji w takich przestrzeniach, a wykładniczy wybuch ze względu na liczbę wymiarów jest trudny do uwzględnienia przy odległości euklidesowej.