11 · Prawa i prawdy · 3 min czytania · Interaktywne · aktualizacja
Czym jest przekleństwo wymiarowości i dlaczego szkodzi modelom?
W skrócie
Wraz z liczbą wymiarów przestrzeń pustoszeje wykładniczo, a odległości między punktami stają się prawie równe. Metody oparte na sąsiedztwie tracą sens.
Co to jest
Liczba przykładów potrzebnych do równie gęstego pokrycia przestrzeni rośnie wykładniczo z liczbą wymiarów, a w wysokich wymiarach odległości do najbliższego i najdalszego punktu stają się niemal równe. Termin wprowadził Richard Bellman w 1957 roku, pisząc o programowaniu dynamicznym; zjawisko koncentracji odległości opisali Kevin Beyer i współautorzy w 1999 roku.
Przykład: żeby mieć jeden punkt na każdą dziesiątą część przedziału [0, 1], wystarczy 10 punktów. Dla kwadratu potrzeba 100, dla sześcianu 1000, a dla 20 wymiarów — 10²⁰. Żaden zbiór danych tego nie pokryje, więc „najbliższy sąsiad” w wysokim wymiarze wcale nie jest blisko.
To nie jedno zjawisko, tylko rodzina efektów: pustka przestrzeni, koncentracja odległości, cała objętość „przy ściankach”, ogromna liczba możliwych interakcji między cechami.
Mechanizm — dlaczego tak działa
Objętość ucieka do brzegów. Koło wpisane w kwadrat zajmuje 79% jego pola, kula wpisana w sześcian — 52% objętości, przy 5 wymiarach — 16%, a przy 10 — zaledwie 0,25%. W hipersześcianie warstwa o grubości 5% przy każdej ściance zawiera 19% objętości w 2 wymiarach, 65% w 10 i praktycznie 100% w 100. Typowy punkt leży przy brzegu, nie w środku.
Odległości się koncentrują. Kwadrat odległości euklidesowej to suma wkładów z wielu niezależnych wymiarów. Z prawa wielkich liczb taka suma rośnie jak d, a jej rozrzut tylko jak √d. Stosunek rozrzutu do średniej maleje jak 1/√d, więc wszystkie odległości stają się „mniej więcej takie same”. Metody oparte na podobieństwie — kNN, k-średnie, jądra RBF — tracą wtedy informację, który punkt jest naprawdę bliski.
Szum zagłusza sygnał. Jeśli tylko kilka cech niesie informację, a reszta jest szumem, każda nieistotna cecha dokłada swój wkład do odległości. Przy setkach takich cech sygnał ginie.
Zastrzeżenie: przekleństwo dotyczy danych rozłożonych w pełni wymiarowo. Prawdziwe dane (obrazy, tekst) zwykle leżą blisko powierzchni o znacznie niższym wymiarze — dlatego modele na tysiącach pikseli w ogóle działają. To jest treść hipotezy rozmaitości.
Na przykładzie
Losowaliśmy 500 punktów z jednostajnego hipersześcianu i mierzyliśmy odległości do losowego punktu zapytania. Stosunek najdalszej do najbliższej odległości wyniósł 92,9 w 2 wymiarach, 2,55 w 10, 1,34 w 100, 1,11 w 1000 i 1,035 w 10 000. Przy 10 000 wymiarów najbliższy punkt jest tylko o 3,5% bliżej niż najdalszy.
Na zbiorze Wine (178 win, 13 cech) kNN ze standaryzacją ma w 5-krotnej walidacji krzyżowej dokładność 0,96. Dołożenie 10 kolumn czystego szumu obniża ją do 0,94, 50 kolumn — do 0,88, 100 — do 0,80, 500 — do 0,61, a 1000 — do 0,56, czyli niewiele ponad zgadywanie najczęstszej klasy (0,40). Informacja w 13 prawdziwych cechach się nie zmieniła; utonęła w odległościach liczonych po szumie.
Dane: Wine (wina z Piemontu)
W praktyce
- Przed kNN, SVM z jądrem RBF czy klasteryzacją ogranicz wymiar:
SelectKBest,PCA, wiedza dziedzinowa. - Standaryzuj cechy (
StandardScaler) — inaczej wymiar o dużej skali dominuje odległość niezależnie od wymiarowości. - Modele z wbudowaną selekcją (lasso, drzewa, gradient boosting) są znacznie odporniejsze na nieistotne cechy niż kNN.
- Kodowanie one-hot zmiennej o tysiącach kategorii to prosty sposób, by nieświadomie wejść w wysoki wymiar.
- Typowy błąd: wybór cech na całym zbiorze przed walidacją krzyżową — daje fałszywie dobre wyniki (wyciek danych).
Najczęstsze pytania
- Od ilu wymiarów zaczyna się przekleństwo?
- Nie ma progu. Liczy się stosunek liczby przykładów do liczby wymiarów i to, ile wymiarów niesie sygnał. Dla kNN problemy widać już przy kilkudziesięciu nieistotnych cechach.
- Czy sieci neuronowe są odporne na przekleństwo wymiarowości?
- Nie są odporne z definicji, ale dobrze wykorzystują strukturę danych: lokalność i hierarchię w obrazach, sekwencyjność w tekście. Bez takiej struktury też potrzebowałyby wykładniczo wielu przykładów.
- Czym różni się to od zjawiska Hughesa?
- Zjawisko Hughesa to jeden konkretny skutek: przy stałej liczbie przykładów dokładność klasyfikatora najpierw rośnie z liczbą cech, a potem spada. Przekleństwo wymiarowości jest szerszą nazwą na wszystkie te geometryczne efekty.
Źródła
- Bellman R. (1961). Adaptive Control Processes: A Guided Tour. Princeton University Press.
- Beyer K., Goldstein J., Ramakrishnan R., Shaft U. (1999). When Is „Nearest Neighbor” Meaningful? International Conference on Database Theory (ICDT 1999), 217–235.
- Aggarwal C. C., Hinneburg A., Keim D. A. (2001). On the Surprising Behavior of Distance Metrics in High Dimensional Space. ICDT 2001, 420–434.
- Hastie T., Tibshirani R., Friedman J. (2009). The Elements of Statistical Learning, 2nd ed. Springer, rozdz. 2.5.