Jaka jest klątwa wymiarowości?

21

W szczególności szukam odniesień (artykułów, książek), które rygorystycznie pokażą i wyjaśnią przekleństwo wymiarowości. Pytanie to pojawiło się po tym, jak zacząłem czytać białą księgę autorstwa Lafferty i Wassermana. W akapicie trzecim wspominają o „dobrze znanym” równaniu, które implikuje, że najlepszym wskaźnikiem konwergencji jest ; jeśli ktokolwiek może to wyjaśnić (i wyjaśnić), byłoby to bardzo pomocne. $n^{-4/(4-d)}$

Czy ktoś może wskazać mi odniesienie, które wywodzi się z „dobrze znanego” równania?

theory khoda
źródło

7

Nie umiem tego wyjaśnić, ale wydaje mi się, że słyszałem, jak brzmią trzy różne wersje klątwy: 1) wyższe wymiary oznaczają wykładniczo rosnącą ilość pracy, a 2) w wyższych wymiarach dostaniesz coraz mniej przykładów w dowolnej części przestrzeni próbki i 3) w wysokich wymiarach wszystko jest w zasadzie jednakowo odległe, co utrudnia rozróżnienie.

Wayne,

5

Można to interpretować geometrycznie. Powiedz, że masz kulę w wymiarach D o promieniu r = 1. Następnie możesz zadać pytanie o to, jaki ułamek objętości sfery leży między promieniem r = 1 i r = 1-e. Ponieważ wiemy, że objętość kuli skaluje się jak k (d) * r ^ (d), gdzie d jest liczbą wymiarów, możemy wywnioskować, że ułamek jest określony przez 1- (1-e) ^ d. Tak więc w przypadku kulek o dużych wymiarach większość objętości jest skoncentrowana w cienkiej skorupce blisko powierzchni. Zobacz więcej na ten temat w książce Biskupów „Rozpoznawanie wzorców i uczenie maszynowe”.

Dr Mike

@Wayne Sure; plus 5) więcej ściemnień zwykle oznacza większy hałas.

Dr Mike, nie podążam za logiką. Wygląda na to, że mówisz, że „ponieważ większość objętości jest skoncentrowana w cienkiej skorupie w pobliżu powierzchni kuli o dużych wymiarach, jesteś przeklęty przez wymiarowość”. Czy możesz wyjaśnić dalej i być może wyraźnie pokazać mi, jak analogia łączy się ze statystykami?

khoda

9

W nawiązaniu do richiemorrisroe znajduje się odpowiedni obraz z elementów uczenia statystycznego , rozdział 2 (str. 22–27):

ESL strona 25

Jak widać w prawym górnym panelu, jest więcej sąsiadów o 1 jednostkę w jednym wymiarze niż sąsiadów o 1 jednostkę w 2 wymiarach. 3 wymiary byłyby jeszcze gorsze!

Zach
źródło

7

To nie odpowiada bezpośrednio na twoje pytanie, ale David Donoho ma fajny artykuł na temat analizy danych wielowymiarowych: Przekleństwa i błogosławieństwa wymiaru (powiązane slajdy są tutaj ), w którym wspomina trzy przekleństwa:

$D$ $(1/\epsilon)^D$ $\epsilon$
$d$ $(1/\epsilon)^D$ $\epsilon$
$D$ $(1/\epsilon)^D$ $\epsilon$

raegtin
źródło

6

Wiem, że ciągle się do tego odwołuję , ale jest na to świetne wytłumaczenie: elementy uczenia statystycznego , rozdział 2 (str. 22–27). Zasadniczo zauważają, że wraz ze wzrostem wymiarów ilość danych musi się z nim zwiększać (wykładniczo), w przeciwnym razie w większej przestrzeni próbki nie będzie wystarczającej liczby punktów, aby można było przeprowadzić jakąkolwiek przydatną analizę.

Odwołują się do artykułu Bellmana (1961) jako źródła, które wydaje się być jego książką Adaptive Control Processes, dostępną w Amazon tutaj

richiemorrisroe
źródło

+1. Wyjaśnienie w ESL jest świetne, a powiązane diagramy bardzo pomagają.

Zach.

2

wprowadź opis zdjęcia tutaj

Być może najbardziej znany wpływ jest uwidoczniony przez następujący limit (który (pośrednio) pokazano na powyższym obrazku):

lim_{re ja m \to \infty} \frac{re ja s t_{m za x} - re ja s t_{m ja n}}{re ja s t_{m ja n}}

$\lim_{dim\rightarrow\infty}\frac{dist_{max}-dist_{min}}{dist_{min}}$

$L_2$ $k$ $L_k$

Wpływ wymiaru na dane w obrazach

Raffael
źródło

Jaka jest klątwa wymiarowości?

Odpowiedzi: