Kiedy dzisiaj ma znaczenie „najbliższy sąsiad”?

W 1999 r. Beyer i in. zapytał, kiedy „Nearest Neighbor” ma znaczenie?

Czy istnieją lepsze sposoby analizy i wizualizacji wpływu płaskości odległości na wyszukiwanie NN od 1999 r.?

Czy [dany] zestaw danych zawiera sensowne odpowiedzi na problem 1-NN? Problem 10-NN? Problem 100-NN?

Jak dziś eksperci podchodzą do tego pytania?

Edycje Poniedziałek 24 stycznia:

Co powiesz na „białą odległość” jako krótszą nazwę „płaskości odległości ze wzrostem wymiarów”?

Łatwym sposobem spojrzenia na „białą odległość” jest uruchomienie 2-NN i wyznaczenie odległości do najbliższego sąsiada i drugiego najbliższego sąsiada. Poniższy wykres pokazuje dist ₁ i dist ₂ dla szeregu klastrów i wymiarów według Monte Carlo. Ten przykład pokazuje całkiem dobry kontrast odległości dla skalowanej absolutnej różnicy | dist ₂ - dist ₁ |. (Różnice względne | dist ₂ / dist ₁ | → 1 jako wymiar → ∞, więc stają się bezużyteczne.)

To, czy błędy bezwzględne czy względne powinny być stosowane w danym kontekście, zależy oczywiście od „prawdziwego” obecnego hałasu: trudny.

Sugestia: zawsze uruchamiaj 2-NN; 2 sąsiedzi są przydatni, gdy są blisko, i przydatni, gdy nie są.

wprowadź opis zdjęcia tutaj

machine-learning k-nearest-neighbour

— denis
źródło

Beyer i in. wydaje się, że zajmuje się nieco innym aspektem problemu NN. Jednak dla celów (binarnej) klasyfikacji, w łagodnych warunkach, klasycznym wynikiem jest to, że klasyfikacja 1-NN ma w najgorszym przypadku dwukrotne prawdopodobieństwo błędu asymetrycznego klasyfikatora Bayesa (tj. Optymalnego). Innymi słowy, pierwszy najbliższy sąsiad zawiera „co najmniej połowę informacji” o etykiecie celu, tak jak robi to najlepszy klasyfikator. W tym sensie 1-NN wydaje się dość istotny. (Aby uzyskać więcej informacji, zobacz Cover & Hart (1967). Dziwię się, że Beyer i wsp. Nie cytują tego.)

— kardynał

@ cardinal, powiązanie Cover-Hart wydaje się wcale nie zależeć od wymiaru, jak mówisz inny aspekt?

— denis

tak, wierzę, że to prawda i to był w dużej mierze mój cel przywołania tego. 1-NN wydaje się w tym sensie dość istotny, tj. Fakt, że działa (więc) dobrze (teoretycznie) jednolicie w wymiarze przestrzeni cech, wydaje się, że pomaga mu stać samodzielnie, bez względu na zachowanie najbliższego i najdalsi sąsiedzi znajdują się w dużej przestrzeni wymiarowej. Zastanawiam się, czy Beyer był świadomy tego (klasycznego) wyniku.

— kardynał

@cardinal Góra strony 24 w Cover i Hart wygląda na miejsce, w którym potencjalnie może pojawić się problem w ich dowodzie, na etapie, w którym Cover i Hart twierdzą, że każdy RV x \ w X ma właściwość, którą ma każda otwarta kula o x niezerowa miara. Jeśli weźmiemy pod uwagę geometrię hipersfery, zauważymy, że objętość wnętrza hipersfery zmniejsza się wraz ze wzrostem wymiarów, więc w granicy otwarta kula około x zawiera tylko x w swoim wnętrzu. Alternatywnie, poprzez SLLN, iid RVs x w przestrzeni metrycznej X wszystkie leżą na powierzchni hipersfery z prawdopodobieństwem jeden.

— Bob Durrant

Zobacz także wskaźniki L1 lub L.5 dotyczące grupowania .

— denis

Odpowiedzi:

Nie mam pełnej odpowiedzi na to pytanie, ale mogę udzielić częściowej odpowiedzi na niektóre aspekty analityczne. Ostrzeżenie: Pracowałem nad innymi problemami od pierwszego artykułu poniżej, więc jest bardzo prawdopodobne, że istnieją inne dobre rzeczy, o których nie wiem.

Po pierwsze uważam, że warto zauważyć, że pomimo tytułu ich artykułu „Kiedy„ najbliższy sąsiad ”ma znaczenie”, Beyer i wsp. Odpowiedzieli na inne pytanie, a mianowicie kiedy NN nie ma znaczenia. Udowodniliśmy odwrotność do ich twierdzenia, przy pewnych dodatkowych łagodnych założeniach dotyczących wielkości próby, w When Is „Nearest Neighbor” Sens: A Converse Theorem and Implikations. Journal of Complexity, 25 (4), sierpień 2009, s. 385–397.i pokazał, że zdarzają się sytuacje, gdy (teoretycznie) koncentracja odległości nie powstanie (podajemy przykłady, ale w zasadzie liczba cech nieszumowych musi rosnąć wraz z wymiarowością, więc oczywiście rzadko pojawiają się w praktyce). Odwołania 1 i 7 cytowane w naszym artykule podają kilka przykładów sposobów ograniczenia koncentracji odległości w praktyce.

Artykuł mojego przełożonego, Aty Kabana, dotyczy tego, czy problemy z koncentracją odległości utrzymują się, pomimo zastosowania technik redukcji wymiarów w części Świadomość koncentracji odległości niektórych technik ograniczania danych. Rozpoznawanie wzorców. Vol. 44, wydanie 2, luty 2011, s. 265–277. . Tam też jest miła dyskusja.

Ostatni artykuł Radovanovica i in. Hubs in Space: Popular Najbliżsi sąsiedzi w danych wielowymiarowych. JMLR, 11 (wrzesień), wrzesień 2010, s. 2487–2531. omawia kwestię „hubness”, czyli gdy niewielki podzbiór punktów należą do najbliższych sąsiadów o wiele znakowanych obserwacji. Zobacz także pracę doktorską pierwszego autora, która jest dostępna w Internecie. $k$

— Bob Durrant
źródło

Dzięki Bob, +1. Powiązane pytanie, czy miałbyś ogólną zasadę wyboru wartości ułamkowej-metrycznej q (czy powinienem zadać to jako osobne pytanie)?

— denis

@Denis Prawdopodobnie zasługuje na własne pytanie, ponieważ myślę, że zależy to zarówno od danych, jak i od aplikacji. Te ułamkowe metryki z nie są tak naprawdę metrykami w sensie formalnym dla (poczucie nierówności trójkąta zostaje na przykład odwrócone, więc nie są wypukłe), a wraz ze wzrostem zbiega się `metryczny”. Zacznę od ponieważ nie jest tak problematyczne, jak gdy , i dopasowuje parametr z danych. Być może do tej pory ktoś znalazł zautomatyzowany sposób, ale nie wiem.

q = 1 / p

$q=1/p$

p > 1

$p>1$

p

$p$

l_{0}

$l_0$

p = 1

$p=1$

l_{1}

$l_{1}$

l_{q = 1 / p}

$l_{q=1/p}$

p > 1

$p>1$

p

$p$

— Bob Durrant

Bob, czy (bez zewnętrznego ) jest metryką dla 0 1, spełniającą nierówność trójkąta?

\sum | a_{j} - b_{j} |^{q}

$\sum |a_j - b_j|^q$

1 / q

$1/q$

< q <

$< q <$

— denis

Ale to tylko zwykła w przebraniu, prawda?

ℓ_{p}

$\ell_{p}$

— Bob Durrant

Równie dobrze możesz zainteresować się analizą komponentów sąsiedzkich autorstwa Goldbergera i in.

Tutaj uczy się transformacji liniowej, aby zmaksymalizować oczekiwane poprawnie sklasyfikowane punkty poprzez stochastyczny wybór najbliższego sąsiedztwa.

Na podstawie danych określa się (oczekiwaną) liczbę sąsiadów.

— bayerj
źródło

Dzięki Bayer. Wygląda na to, że „uczenie się na odległość” rozwija się dynamicznie - scholar.goo ma 50 tytułów od 2008 roku. Ale czy jest to papier boomowy, czy prawdziwe zastosowanie? Przypis, kod nca mówi „iteracje ... co najmniej 100000 dla dobrych wyników”. Przypis 2: większość pracy nad uczeniem się na odległość na odległość wydaje się modelować odległość Mahalanobisa; czy znasz inne modele odległości?

— denis

Mam różne doświadczenia z NCA - zwykle dla mnie dość szybko się zbiegają. Zapoznaj się z „redukcją wymiarów poprzez naukę niezmiennego mapowania” autorstwa LeCun i „Minimalizacją strat dla kompaktowych kodów binarnych” autorstwa Norouzi.

— bayerj