Przekleństwo wymiarowości
Z Wikipedii, wolnej encyclopedia
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[1][2].
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)[3].
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[4]. 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[5][6].
Zjawisko to stanowi poważną przeszkodę dla efektywności algorytmów eksploracji danych, analizy numerycznej, badań statystycznych, kombinatoryki oraz uczenia maszynowego.