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