Przekleństwo wymiarowości - Curse of dimensionality

Przekleństwo wymiarowości odnosi się do różnych zjawisk, które powstają podczas analizowania i organizowania danych w wysokich-wymiarowej przestrzeni , które nie występują w ustawieniach niskowymiarowych takich jak trójwymiarowej przestrzeni fizycznej w codziennym doświadczeniu. Wyrażenie zostało ukute przez Richarda E. Bellmana przy rozważaniu problemów programowania dynamicznego .

Zjawiska przeklęte wymiarowo występują w dziedzinach takich jak analiza numeryczna , próbkowanie , kombinatoryka , uczenie maszynowe , eksploracja danych i bazy danych . Wspólnym motywem tych problemów jest to, że gdy zwiększa się wymiarowość, objętość przestrzeni rośnie tak szybko, że dostępne dane stają się rzadkie. Ta rzadkość jest problematyczna dla każdej metody, która wymaga istotności statystycznej . W celu uzyskania statystycznie poprawnego i wiarygodnego wyniku, ilość danych potrzebnych do poparcia wyniku często rośnie wykładniczo wraz z wymiarowością. Ponadto organizowanie i wyszukiwanie danych często opiera się na wykrywaniu obszarów, w których obiekty tworzą grupy o podobnych właściwościach; jednak w przypadku danych wielowymiarowych wszystkie obiekty wydają się być rzadkie i pod wieloma względami niepodobne, co uniemożliwia skuteczność wspólnych strategii organizacji danych.

Domeny

Kombinatoryka

W niektórych problemach każda zmienna może przyjąć jedną z kilku wartości dyskretnych lub zakres możliwych wartości jest dzielony tak, aby dać skończoną liczbę możliwości. Biorąc zmienne razem, należy wziąć pod uwagę ogromną liczbę kombinacji wartości. Efekt ten jest również znany jako eksplozja kombinatoryczna . Nawet w najprostszym przypadku zmiennych binarnych liczba możliwych kombinacji jest już wykładnicza w wymiarze. Naiwnie każdy dodatkowy wymiar podwaja wysiłek potrzebny do wypróbowania wszystkich kombinacji.

Próbowanie

Istnieje wykładniczy wzrost objętości związany z dodawaniem dodatkowych wymiarów do przestrzeni matematycznej . Na przykład, 10 2  = 100 równomiernie rozmieszczonych punktów próbkowania wystarczy, aby próbkować interwał jednostkowy („jednowymiarowy sześcian”) z nie większą niż 10 -2 = 0,01 odległości między punktami; równoważne próbkowanie 10-wymiarowego hipersześcianu jednostkowego z siecią o odstępach 10-2 = 0,01 między sąsiednimi punktami wymagałoby 10 20 = [(10 2 ) 10 ] punktów próbkowania. Ogólnie rzecz biorąc, przy odległości 10 n 10-wymiarowy hipersześcian wydaje się mieć czynnik równy 10 n (10−1) = [(10 n ) 10 /(10 n )] „większy” niż jednowymiarowy hipersześcian, który jest interwałem jednostkowym. W powyższym przykładzie n = 2: przy użyciu odległości próbkowania 0,01 10-wymiarowy hipersześcian wydaje się być o 10 18 „większy” niż przedział jednostkowy. Efekt ten jest kombinacją powyższych problemów kombinatoryki i wyjaśnionych poniżej problemów funkcji odległości.

Optymalizacja

Podczas rozwiązywania problemów optymalizacji dynamicznej za pomocą numerycznej indukcji wstecznej funkcja celu musi być obliczona dla każdej kombinacji wartości. Jest to istotna przeszkoda, gdy wymiar „zmiennej stanu” jest duży.

Nauczanie maszynowe

W problemach z uczeniem maszynowym , które obejmują uczenie 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, zwykle wymagana jest ogromna ilość danych uczących, aby zapewnić że istnieje kilka próbek z każdą kombinacją wartości.

Typową praktyczną zasadą jest to, że dla każdego wymiaru reprezentacji powinno być co najmniej 5 przykładów uczących. W uczeniu maszynowym i jeśli chodzi o przewidywanie wydajności, przekleństwo wymiarowości jest używane zamiennie ze zjawiskiem szczytowania , które jest również znane jako zjawisko Hughesa . Zjawisko to stwierdza, że ​​przy ustalonej liczbie próbek uczących średnia (oczekiwana) moc predykcyjna klasyfikatora lub regresora najpierw wzrasta wraz ze wzrostem liczby wykorzystywanych wymiarów lub funkcji, ale poza pewną wymiarowością zaczyna się pogarszać zamiast stale się poprawiać.

Niemniej jednak w kontekście prostego klasyfikatora ( liniowa analiza dyskryminacyjna w wielowymiarowym modelu Gaussa przy założeniu powszechnie znanej macierzy kowariancji) Zollanvari et al. wykazali zarówno analitycznie, jak i empirycznie, że dopóki względna skumulowana skuteczność dodatkowego zestawu cech (w odniesieniu do cech, które są już częścią klasyfikatora) jest większa (lub mniejsza) niż wielkość tego dodatkowego zestawu cech, oczekiwany błąd klasyfikator skonstruowany przy użyciu tych dodatkowych funkcji będzie mniejszy (lub większy) niż oczekiwany błąd klasyfikatora skonstruowanego bez nich. Innymi słowy, zarówno wielkość dodatkowych cech, jak i ich (względny) skumulowany efekt dyskryminacyjny są ważne w obserwowaniu spadku lub wzrostu średniej mocy predykcyjnej.

Funkcje odległości

Gdy miara, taka jak odległość euklidesowa, jest definiowana przy użyciu wielu współrzędnych, różnica w odległościach między różnymi parami próbek jest niewielka.

Jednym ze sposobów zilustrowania „ogromności” wysokowymiarowej przestrzeni euklidesowej jest porównanie proporcji hipersfery wpisanej o promieniu i wymiarze , do hipersześcianu o krawędziach o długości Objętość takiej sfery wynosi , gdzie jest funkcją gamma , podczas gdy objętość sześcianu wynosi . Wraz ze wzrostem wymiaru przestrzeni hipersfera staje się nieistotną objętością w stosunku do hipersześcianu. Można to wyraźnie widać porównując proporcje jak wymiar dąży do nieskończoności:

jak .

Ponadto odległość między środkiem a rogami wynosi , co zwiększa się bez ograniczeń dla ustalonego r. W tym sensie prawie cała przestrzeń wielowymiarowa jest „daleko” od centrum. W dużych wymiarach objętość d- wymiarowej jednostki hipersześcianu (ze współrzędnymi wierzchołków ) jest skoncentrowana w pobliżu kuli o promieniu dla dużego wymiaru d . Rzeczywiście, dla każdej współrzędnej średnia wartość w sześcianie wynosi

.

Wariancja dla rozkładu równomiernego w sześcianie wynosi

Zatem kwadrat odległości od początku ma średnią wartość d /3 i wariancję 4 d /45. Dla dużego d rozkład jest zbliżony do rozkładu normalnego ze średnią 1/3 i odchyleniem standardowym zgodnie z centralnym twierdzeniem granicznym . Tak więc w dużych wymiarach zarówno „środek” hipersześcianu, jak i rogi są puste, a cała objętość koncentruje się w pobliżu kuli o „pośrednim” promieniu .

Pomaga to również zrozumieć rozkład chi-kwadrat . Rzeczywiście, (niecentralny) rozkład chi-kwadrat związany z losowym punktem w przedziale [-1, 1] jest taki sam jak rozkład długości kwadratu losowego punktu na sześcianie d . Zgodnie z prawem wielkich liczb rozkład ten koncentruje się w wąskim paśmie wokół d razy kwadrat odchylenia standardowego (σ 2 ) pierwotnego wyprowadzenia. To wyjaśnia rozkład chi-kwadrat, a także ilustruje, że większość objętości d- cube koncentruje się w pobliżu powierzchni kuli o promieniu .

Dalszy rozwój tego zjawiska jest następujący. Wszelkie stałe rozkład na liczbach rzeczywistych indukuje rozkład produktów na punkty w ℝ d . Dla dowolnego ustalonego n okazuje się, że minimalna i maksymalna odległość między losowym punktem odniesienia Q a listą n losowych punktów danych P 1 ,..., P n stają się nieodróżnialne w porównaniu z odległością minimalną:

.

Jest to często cytowane jako funkcje odległości, które tracą swoją przydatność (na przykład dla kryterium najbliższego sąsiedztwa w algorytmach porównywania cech) w dużych wymiarach. Jednak ostatnie badania wykazały, że ma to zastosowanie tylko w sztucznym scenariuszu, gdy rozkłady jednowymiarowe ℝ są niezależne i mają identyczny rozkład . Gdy atrybuty są skorelowane, dane mogą stać się łatwiejsze i zapewnić większy kontrast odległości, a stosunek sygnału do szumu odgrywa ważną rolę, dlatego należy zastosować wybór cech .

Wyszukiwanie najbliższego sąsiada

Efekt komplikuje wyszukiwanie najbliższego sąsiada w przestrzeni wielowymiarowej. Nie można szybko odrzucić kandydatów, używając różnicy w jednej współrzędnej jako dolnej granicy dla odległości opartej na wszystkich wymiarach.

Jednak ostatnio zaobserwowano, że sama liczba wymiarów niekoniecznie powoduje trudności, ponieważ odpowiednie dodatkowe wymiary mogą również zwiększyć kontrast. Ponadto dla wynikowego rankingu przydatne jest rozróżnianie bliskich i dalekich sąsiadów. Jednak nieistotne ("szum") wymiary zmniejszają kontrast w sposób opisany powyżej. W analizie szeregów czasowych , gdzie dane są z natury wielowymiarowe, funkcje odległości również działają niezawodnie, o ile stosunek sygnału do szumu jest wystarczająco wysoki.

k – klasyfikacja najbliższego sąsiada

Innym efektem dużej wymiarowości na funkcjach odległość obaw k -nearest sąsiada ( k -nn) wykresy skonstruowane z zestawu danych przy użyciu funkcji odległości. Wraz ze wzrostem wymiar, indegree rozkład k -NN dwuznakiem staje wypaczone ze szczytem z prawej strony, ze względu na pojawienie się nieproporcjonalna liczba węzłów , czyli punkty danych, które pojawiają się w wielu innych k -NN wykazów inne punktów danych niż średnia. Zjawisko to może mieć znaczny wpływ na różne techniki klasyfikacji (w tym klasyfikator k- NN ), częściowo nadzorowane uczenie się i grupowanie , a także wpływa na wyszukiwanie informacji .

Wykrywanie anomalii

W badaniu z 2012 r. Zimek i in. zidentyfikowali 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 atrybuty: w danych wielowymiarowych znaczna liczba atrybutów może być nieistotna
  3. Definicja zbiorów referencyjnych: w przypadku metod lokalnych, zbiory referencyjne są często oparte na najbliższym sąsiedztwie
  4. Nieporównywalne wyniki dla różnych wymiarowości: różne podprzestrzenie dają nieporównywalne wyniki
  5. Interpretowalność partytur: partytury często nie mają już znaczenia semantycznego
  6. Wykładnicza przestrzeń wyszukiwania: przestrzeń wyszukiwania nie może być już systematycznie skanowana
  7. Błąd wyszukiwania danych : biorąc pod uwagę dużą przestrzeń wyszukiwania, dla każdego pożądanego znaczenia można znaleźć hipotezę
  8. Hubness: niektóre obiekty występują częściej na listach sąsiadów niż inne.

Wiele z analizowanych metod specjalistycznych zajmuje się jednym lub drugim z tych problemów, pozostaje jednak wiele otwartych pytań badawczych.

Błogosławieństwo wymiarowości

Co zaskakujące i pomimo spodziewanych trudności „przekleństwa wymiarowości”, zdroworozsądkowe heurystyki oparte na najprostszych metodach „mogą dawać wyniki, które są prawie na pewno optymalne” w przypadku problemów wielowymiarowych. Termin „błogosławieństwo wymiarowości” został wprowadzony pod koniec lat dziewięćdziesiątych. Donoho w swoim „ Manifeście milenijnym” jasno wyjaśnił, dlaczego „błogosławieństwo wymiarowości” będzie stanowić podstawę przyszłej eksploracji danych. Skutki błogosławieństwa wymiarowości zostały odkryte w wielu zastosowaniach i znalazły swoje podstawy w koncentracji zjawisk miarowych . Jednym z przykładów błogosławieństwa zjawiska wymiarowości jest liniowa rozdzielność losowego punktu od dużego skończonego zbioru losowego z dużym prawdopodobieństwem, nawet jeśli zbiór ten jest wykładniczo duży: liczba elementów w tym zbiorze losowym może rosnąć wykładniczo wraz z wymiarem. Co więcej, ten funkcjonał liniowy może być wybrany w postaci najprostszego liniowego dyskryminatora Fishera . To twierdzenie o separowalności zostało udowodnione dla szerokiej klasy rozkładów prawdopodobieństwa: ogólnych rozkładów równomiernie logarytmicznie wklęsłych, rozkładów iloczynów w sześcianie i wielu innych rodzin (opisanych ostatnio w ).

„Błogosławieństwo wymiarowości i przekleństwo wymiarowości to dwie strony tej samej monety”. Na przykład typową właściwością zasadniczo wysokowymiarowych rozkładów prawdopodobieństwa w przestrzeni wielowymiarowej jest: kwadrat odległości losowych punktów do wybranego punktu jest, z dużym prawdopodobieństwem, zbliżony do średniej (lub mediany) kwadratu odległości. Właściwość ta znacznie upraszcza oczekiwaną geometrię danych i indeksowanie danych wielkowymiarowych (błogosławieństwo), ale jednocześnie sprawia, że ​​poszukiwanie podobieństwa w dużych wymiarach jest trudne, a nawet bezużyteczne (przekleństwo).

Zimek i in. zauważył, że podczas gdy typowe formalizacje klątwy wymiarowości wpływają na dane iid , posiadanie danych, które są oddzielone w każdym atrybucie, staje się łatwiejsze nawet w dużych wymiarach i argumentował, że stosunek sygnału do szumu ma znaczenie: dane stają się łatwiejsze z każdym dodanym atrybutem sygnał, a trudniej z atrybutami, które dodają tylko szum (nieistotny błąd) do danych. W szczególności w przypadku nienadzorowanej analizy danych efekt ten określany jest jako bagno.

Zobacz też

Bibliografia