Czytam książkę Kevina Murphy'ego: Machine Learning - A probabilistic Perspective. W pierwszym rozdziale autor wyjaśnia przekleństwo wymiarowości i jest część, której nie rozumiem. Jako przykład autor stwierdza:
Zastanów się, czy dane wejściowe są równomiernie rozmieszczone wzdłuż sześcianu jednostki D-wymiarowej. Załóżmy, że szacujemy gęstość etykiet klas, powiększając hiper sześcian wokół x, aż będzie zawierać pożądaną część punktów danych. Oczekiwana długość krawędzi tego sześcianu to .
To ostatnia formuła, której nie potrafię zrozumieć. wydaje się, że jeśli chcesz pokryć, powiedz, że 10% punktów niż długość krawędzi powinna wynosić 0,1 wzdłuż każdego wymiaru? Wiem, że moje rozumowanie jest błędne, ale nie rozumiem, dlaczego.
self-study
k-nearest-neighbour
high-dimensional
użytkownik42140
źródło
źródło
Odpowiedzi:
To jest dokładnie nieoczekiwane zachowanie odległości w dużych wymiarach. Dla 1 wymiaru masz interwał [0, 1]. 10% punktów znajduje się w segmencie o długości 0,1. Ale co się dzieje, gdy wzrasta wymiar przestrzeni cech?
To wyrażenie mówi ci, że jeśli chcesz mieć 10% punktów dla 5 wymiarów, musisz mieć długość dla kostki 0,63, w 10 wymiarach 0,79 i 0,98 dla 100 wymiarów.
Jak widać, w celu zwiększenia wymiarów należy odwrócić wzrok, aby uzyskać taką samą liczbę punktów. Co więcej, mówi ci, że większość punktów znajduje się na granicy sześcianu wraz ze wzrostem liczby wymiarów. Co jest nieoczekiwane.
źródło
Myślę, że najważniejsze jest to, że wyrażenie
na początku jest naprawdę stroma. Oznacza to, że rozmiar krawędzi, który będziesz musiał objąć określoną część objętości, drastycznie wzrośnie, szczególnie na początku. tzn. potrzebna krawędź stanie się absurdalnie duża wraz ze wzrostemD
Aby to jeszcze bardziej wyjaśnić, przypomnij sobie fabułę, którą pokazuje Murphy:
jeśli zauważysz, dla wartości nachylenie jest naprawdę duże, a zatem funkcja rośnie naprawdę gwałtownie na początku. Można to lepiej docenić, jeśli weźmiesz pochodną :D>1 eD(f)
Ponieważ rozważamy tylko zwiększenie wymiaru (które są wartościami całkowitymi), dbamy tylko o wartości całkowite . Oznacza to, że . Rozważ wyrażenie dla krawędzi w następujący sposób:D>1 1−D<0
Zauważa, że podnosimy do mocy mniejszej niż 0 (tj. Ujemnej). Kiedy podnosimy liczbę do potęg ujemnych, w pewnym momencie robimy odwrotność (tj. ). Wykonanie odwrotności do liczby, która jest już naprawdę bardzo mała (przypominamy ponieważ rozważamy tylko ułamek objętości, ponieważ wykonujemy KNN, tj. najbliższych punktów danych z całkowitej liczby ), oznacza, że liczba „rośnie los". W związku z tym otrzymujemy pożądane zachowanie, tj. Że wraz ze wzrostem moc staje się jeszcze bardziej ujemna, a zatem wymagana krawędź rośnie znacznie w zależności od tego, jak duże zwiększa wykładnik potęgi.f x−1=1x f<1 k N D D
(zauważ, że rośnie wykładniczo w porównaniu do podziału który szybko staje się nieistotny).f1−D 1D
źródło
Tak, więc jeśli masz kostkę jednostkową lub w twoim przypadku linię jednostkową, a dane są równomiernie rozmieszczone, musisz przejść na długość 0,1, aby przechwycić 10% danych. Teraz, gdy zwiększasz wymiary, zwiększa się D, co zmniejsza moc if mniejszą niż 1, wzrośnie, tak że jeśli D przejdzie w nieskończoność, musisz przejąć całą kostkę, e = 1.
źródło
Myślę, że dla kNN odległość odgrywa większą rolę. To, co dzieje się z (hiper) sześcianem, jest analogiczne do tego, co dzieje się z odległością między punktami. Wraz ze wzrostem liczby wymiarów rośnie stosunek między najbliższą odległością do średniej odległości - oznacza to, że najbliższy punkt znajduje się prawie tak daleko, jak punkt średni, wtedy ma tylko nieco większą moc predykcyjną niż punkt średni. Ten artykuł ładnie to wyjaśnia
źródło