Przekleństwo wymiarowości

Schemat siatki kwadratów 10x10. Każdy z małych kwadratów reprezentuje jeden milimetr kwadratowy (1 mm²); cała siatka reprezentuje jeden centymetr kwadratowy (1 cm²). Ma to na celu pokazanie, że choć na 1 cm przypada 10 mm, to na 1 cm² przypada 100 mm². Bardziej ogólnie, pokazuje to, że współczynnik konwersji między jednostkami powierzchni jest kwadratem współczynnika konwersji między odpowiednimi jednostkami długości.

Przekleństwo wymiarowości odnosi się do wielu właściwości przestrzeni wielowymiarowych i problemów kombinatorycznych. Przede wszystkim dotyczy wykładniczego wzrostu niezbędnych danych eksperymentalnych w zależności od wymiaru przestrzeni przy rozwiązywaniu problemów probabilistyczno-statystycznego rozpoznawania wzorców, uczenia maszynowego, klasyfikacji i analizy dyskryminacyjnej. Dotyczy to również wykładniczego wzrostu liczby wariantów w kombinatorycznych problemach w zależności od wielkości początkowych danych, co prowadzi do odpowiedniego zwiększenia złożoności algorytmów ponownego wyboru. Przekleństwo dotyczy również ciągłych metod optymalizacji, a także złożoności wielowymiarowej funkcji celu.

Określenia „przekleństwo wymiarowości” po raz pierwszy użyto w opracowaniu w wydanym w 1961 roku przez Richarda Ernesta Bellmana „Adaptive control processes”. Pojęcie występowało również  w pracach: White’a (1989), Bishopa (1995). Wystąpiło również pod pojęciem „zjawisko pustej przestrzeni” (ang. empty space phenomenon) w pracach Scotta i Thompsona (1983), Silvermana (1986).

Przekleństwo wymiarowości odnosi się do sytuacji, gdy poprawna klasyfikacja obiektów, wykorzystując pełny zbiór danych, jest niemal niemożliwa, a wielość charakterystyk w wektorze skutkuje wzrostem liczby parametrów, co skutkuje wzrostem złożoność klasyfikatora. Rośnie również ryzyko przeuczenia (ang. overfitting) i tym samym spadku zdolności uogólniających (ang. generalization) klasyfikatora. Jest to przyczyną powszechnego zmniejszenia wymiarowości cech. Przyczyną problemów jest identyfikacja podzbioru cech, który posłuży poprawnej klasyfikacji danych przez algorytm.

Zjawisko to stanowi poważną przeszkodę dla efektywności algorytmów eksploracji danych, analizy numerycznej, badań statystycznych, kombinatoryki oraz uczenia maszynowego.

Występowanie

Funkcja odległości

Dla różnych typów rozkładów losowych zbiorów danych różnica pomiędzy najmniejszą, a największą odległością pomiędzy zbiorami staje się nieznaczącą w porównaniu do najmniejszej odległości, gdy zwiększa się miara d (innymi słowy: najmniejsze i największe odległości różnią się tylko stosunkowo niewielkim wielkościami),  a zatem wyniki funkcji odległości i algorytmów na nich opartych), przestają być użyteczne  dla rozkładów w przestrzeniach wielowymiarowych.

Można to przedstawić za pomocą poniższego wzoru:

$\lim _{d\to \infty }E\left({\frac {\operatorname {dist} _{\max }(d)-\operatorname {dist} _{\min }(d)}{\operatorname {dist} _{\min }(d)}}\right)\to 0$

Najnowsze badania sugerują jednak że tylko „nieistotne” wymiary powodują ten efekt.

Jeżeli atrybuty są skorelowane, dane mogą stać się czytelniejsze i zapewnią wyższy kontrast a odległość i stosunek sygnału do szumu będą odpowiednie, oznacza to że, cecha powinna zostać uwzględniona.

Rozpoznawanie wzorców

W probabilistycznych problemach rozpoznawania istnieją dwie sytuacje, w których przekleństwo wymiarowości można przezwyciężyć :

Możliwe, że rozkład wektora wzajemnie zależnych zmiennych losowych jest skoncentrowany w podprzestrzeni o niższej wymiarowości, to znaczy, że wektor może być dobrze aproksymowany przez liniową funkcję mniejszej liczby zmiennych. W takim przypadku analiza głównych składowych (PCA) zmniejsza liczbę wymiarów. Ponadto przypisane zadania rozpoznawania (dyskryminacji) można rozwiązać już w przestrzeni o mniejszej ilości wymiarów.

Jest również możliwe, że zmienne losowe badanych wektorów są niezależne lub słabo skorelowane. W tym przypadku można odzyskać jednowymiarowe rozkłady zmiennych losowych i skonstruować wielowymiarowe rozkłady jako swoje produkty.

Powszechnie stosowanym algorytmem do analizy danych wielowymiarowych jest algorytm najbliższego sąsiada. Ta metoda może być stosowana przy badaniu próbek o dowolnym rozmiarze, niezależnie od wymiarów wektorów, jednakże podstawowym problemem tego algorytmu jest brak wystarczającej ilości informacji o obiekcie opisywanym dużą liczbą istotnych parametrów.

Zadania optymalizacyjne

Przekleństwo wymiarowości ma wpływ również na problemy optymalizacyjne.

W problemach związanych z optymalizacją dyskretną czas działania algorytmów można zredukować za pomocą algorytmu BnB oraz algorytmów heurystycznych.

Metody te są skuteczne jednak tylko w części przypadków i nie rozwiązują one problemu przekleństwa wymiarowości.

Uczenie maszynowe

W problemach z uczeniem maszynowym polegających na uczeniu się "stanu natury" ze skończonej liczby próbek danych w wielowymiarowej przestrzeni cech, przy czym każda cecha ma zakres możliwych wartości, zazwyczaj wymagana jest ogromna ilość danych szkoleniowych w celu zapewnienia że istnieje kilka próbek z każdą kombinacją wartości. Zasada mówi, że powinno być co najmniej 5 przykładów szkoleniowych dla każdego wymiaru. Przy ustalonej liczbie próbek treningowych najpierw zwiększa się moc predykcyjna klasyfikatora lub regresora, gdy liczba użytych wymiarów / cech jest zwiększana, a następnie maleje co jest znane jako zjawisko Hughesa lub zjawisko szczytowe.

Wykrywanie anomalii

W swoim badaniu Zimek zidentyfikował następujące problemy podczas wyszukiwania anomalii w danych wielowymiarowych:

1. Koncentracja wyników i odległości: wartości pochodne, takie jak odległości, stają się liczbowo podobne
2. Nieistotne cechy: w danych wielowymiarowych znaczna liczba atrybutów może być nieistotna
3. Definiowanie zestawów referencyjnych: w przypadku metod lokalnych zestawy odniesień są często oparte na najbliższym sąsiedztwie
4. Nieporównywalność wyników z różnych wymiarów: różne podprzestrzenie dają nieporównywalne wyniki
5. Problem z interpretacją wyników: wyniki często nie przekazują już znaczenia semantycznego
6. Przestrzenie wyszukiwania nie mogą być systematycznie skanowane
7. "Stronniczość danych": biorąc pod uwagę dużą przestrzeń poszukiwań, dla każdego pożądanego znaczenia można znaleźć hipotezę
8. "Stopnie koncentracji": niektóre obiekty występują częściej na listach sąsiadów niż inne.

Wiele specjalistycznych metod analiz rozwiązuje część z tych problemów, lecz pozostaje wiele otwartych pytań badawczych.