Wyjaśnij dziecku „Klątwę wymiarowości”

Słyszałem wiele razy o przekleństwie wymiarowości, ale jakoś wciąż nie jestem w stanie zrozumieć tego pomysłu, wszystko jest mgliste.

Czy ktoś może to wyjaśnić w najbardziej intuicyjny sposób, tak jak wyjaśniłbyś to dziecku, aby ja (i inni zdezorientowani jak ja) mogłem to zrozumieć na dobre?

EDYTOWAĆ:

Teraz powiedzmy, że dziecko jakoś słyszało o klastrowaniu (na przykład umie klastować swoje zabawki :)). W jaki sposób wzrost wymiarów utrudniłby grupowanie zabawek?

Na przykład rozważano tylko kształt zabawki i jej kolor (zabawki jednokolorowe), ale teraz należy również wziąć pod uwagę rozmiar i wagę zabawek. Dlaczego dziecku trudniej jest znaleźć podobne zabawki?

EDYCJA 2

W celu omówienia muszę wyjaśnić, że przez: „Dlaczego dziecku trudniej jest znaleźć podobne zabawki” - mam również na myśli, dlaczego pojęcie odległości jest tracone w przestrzeniach o dużych wymiarach?

Prawdopodobnie dziecko lubi jeść ciasteczka, więc załóżmy, że masz całą ciężarówkę z ciasteczkami o innym kolorze, innym kształcie, innym smaku, innej cenie ...

Jeśli dziecko musi wybrać, ale bierze pod uwagę tylko jedną cechę, np. Smak, ma cztery możliwości: słodki, słony, kwaśny, gorzki, więc dziecko musi spróbować tylko czterech ciastek, aby znaleźć to, co lubi najbardziej.

Jeśli dziecko lubi kombinacje smaku i koloru, a są 4 (jestem raczej optymistyczny tutaj :-)) różne kolory, to on już musi wybierać spośród 4x4 różnych typów;

Jeśli chce dodatkowo wziąć pod uwagę kształt ciasteczek i istnieje 5 różnych kształtów, będzie musiał wypróbować 4x4x5 = 80 ciasteczek

Moglibyśmy kontynuować, ale po zjedzeniu tych wszystkich ciastek może już boleć go brzuch ... zanim będzie mógł dokonać najlepszego wyboru :-) Oprócz bólu brzucha, naprawdę trudno jest zapamiętać różnice w smaku każdego pliku cookie.

Jak widać (@Almo), większość (wszystkich?) Rzeczy stają się bardziej skomplikowane wraz ze wzrostem liczby wymiarów, dotyczy to zarówno osób dorosłych, komputerów, jak i dzieci.

Analogia, którą lubię używać do przekleństwa wymiarowości, jest nieco bardziej geometryczna, ale mam nadzieję, że nadal będzie wystarczająco przydatna dla twojego dziecka.

Łatwo jest upolować psa i złapać go, gdyby biegał po równinie (dwa wymiary). O wiele trudniej jest polować na ptaki, które mają teraz dodatkowy wymiar, w który mogą się poruszać. Jeśli udajemy, że duchy są istotami o wyższych wymiarach (podobnie jak Sfera oddziałująca z A. Kwadratem w Flatland ), są one jeszcze trudniejsze do złapania. :)

Ok, przeanalizujmy przykład dziecka grupującego zabawki.
Wyobraź sobie, że dziecko ma tylko 3 zabawki:

1. niebieska piłka
   
2. niebieski freesbe
3. zielony sześcian (ok, może nie jest to najfajniejsza zabawka, jaką możesz sobie wyobrazić)

Zróbmy następującą wstępną hipotezę dotyczącą tego, jak można zrobić zabawkę:

1. Możliwe kolory to: czerwony, zielony, niebieski
2. Możliwe kształty to: koło, kwadrat, trójkąt

Teraz możemy mieć (num_colors * num_shapes) = 3 * 3 = 9 możliwych klastrów.

Chłopiec grupuje zabawki w następujący sposób:

• CLUSTER A) zawiera niebieską kulkę i niebieską freesbe, ponieważ mogą mieć ten sam kolor i kształt
• CLUSTER B) zawiera super zabawny zielony sześcian

Używając tylko tych 2 wymiarów (koloru, kształtu) mamy 2 niepuste skupiska: w tym pierwszym przypadku 7/9 ~ 77% naszej przestrzeni jest puste.

Teraz zwiększmy liczbę wymiarów, które dziecko musi wziąć pod uwagę. Robimy również następującą hipotezę dotyczącą sposobu wykonania zabawki:

3. Rozmiar zabawki może wynosić od kilku centymetrów do 1 metra, z krokiem dziesięciu centymetrów: 0-10 cm, 11-20 cm, ..., 91 cm-1 m
4. Waga zabawki może zmieniać się w podobny sposób do 1 kilograma, w krokach co 100 gramów: 0-100 g, 101-200 g, ..., 901 g-1 kg.

Jeśli chcemy teraz klastrować nasze zabawki, mamy (num_colours * num_shapes * num_sizes * num_weights) = 3 * 3 * 10 * 10 = 900 możliwych klastrów.

Chłopiec grupuje zabawki w następujący sposób:

• CLUSTER A) zawiera niebieską piłkę, ponieważ jest niebieska i ciężka
• CLUSTER B) zawiera niebieski freesbe, ponieważ jest niebieski i lekki
• CLUSTER C) zawiera super zabawny zielony sześcian

Używając aktualnych 4 wymiarów (kształt, kolor, rozmiar, waga) tylko 3 skupienia nie są puste: w tym przypadku 897/900 ~ 99,7% przestrzeni jest puste.

To jest przykład tego, co można znaleźć na Wikipedii ( https://en.wikipedia.org/wiki/Curse_of_dimensionality ):
... gdy wymiarowość rośnie, objętość przestrzeni rośnie tak szybko, że dostępne dane stają się rzadkie.

Edycja: Nie jestem pewien, czy naprawdę potrafiłbym wyjaśnić dziecku, dlaczego dystans czasami nie jest dobry w przestrzeniach o dużych wymiarach, ale spróbujmy pójść za naszym przykładem dziecka i jego zabawek.

Rozważ tylko dwie pierwsze cechy {kolor, kształt} wszyscy zgadzają się, że niebieska kula jest bardziej podobna do niebieskiego freesbe niż do zielonej kostki.

Dodajmy teraz 98 innych funkcji (powiedzmy: rozmiar, waga, dzień produkcji), materiał, miękkość, dzień w którym to zabawka była , kupowana przez tatusia, cena itp.: Cóż, dla mnie trudniej byłoby ocenić, która zabawka jest podobna do której.

Więc:

1. Duża liczba funkcji może być nieistotna w pewnym porównaniu podobieństwa, co prowadzi do uszkodzenia stosunku sygnału do szumu.
2. W wysokich wymiarach wszystkie przykłady wyglądają podobnie.
   
   

Jeśli mnie posłuchasz, dobrym wykładem jest „Kilka przydatnych rzeczy na temat uczenia maszynowego” ( http://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf ), w szczególności pkt 6 rodzaj rozumowania.

Mam nadzieję że to pomoże!

Natknąłem się na następujący link, który zapewnia bardzo intuicyjne (i szczegółowe) wyjaśnienie przekleństwa wymiarowości: http://www.visiondummy.com/2014/04/curse-dimensionality-affect-classification/

W tym artykule omówimy tak zwaną „Klątwę wymiaru” i wyjaśnimy, dlaczego jest to ważne przy projektowaniu klasyfikatora. W poniższych sekcjach przedstawię intuicyjne wyjaśnienie tej koncepcji, zilustrowane wyraźnym przykładem nadmiernego dopasowania z powodu przekleństwa wymiarowości.

W kilku słowach ten artykuł wywodzi (intuicyjnie), że dodanie większej liczby funkcji (tj. Zwiększenie wymiarów naszej przestrzeni funkcji) wymaga zebrania większej ilości danych. W rzeczywistości ilość danych, które musimy gromadzić (aby uniknąć nadmiernego dopasowania), rośnie wykładniczo w miarę dodawania kolejnych wymiarów.

Ma również ładne ilustracje, takie jak ta:

Klątwa wymiarowości jest nieco rozmyta z definicji, ponieważ opisuje różne, ale powiązane rzeczy w różnych dyscyplinach. Poniższy przykład ilustruje przekleństwo uczenia maszynowego:

Załóżmy, że dziewczyna ma dziesięć zabawek, z których lubi tylko te kursywą:

• brązowy miś
• niebieski samochód
• czerwony pociąg
• żółta koparka
• zielona książka
• szary pluszowy mors
• czarny wagon
• różowa kula
• biała książka
• pomarańczowa lalka

Teraz jej ojciec chce dać jej nową zabawkę jako prezent na urodziny i chce się upewnić, że jej się spodoba. Bardzo mocno myśli o tym, co łączy te zabawki, które lubi, i w końcu dochodzi do rozwiązania. Daje córce układankę w różnych kolorach. Kiedy ona jej nie lubi, odpowiada: „Dlaczego ci się to nie podoba? Zawiera literę w. ”

Ojciec padł ofiarą klątwy wymiarowej (i optymalizacji w próbie). Rozważając litery, poruszał się w 26-wymiarowej przestrzeni, dlatego bardzo prawdopodobne było, że znajdzie jakieś kryterium oddzielające zabawki lubiane przez córkę. Nie musiało to być kryterium jednoliterowe, jak w przykładzie, ale mogło być również coś w rodzaju

zawiera co najmniej jeden spośród a, n i p, ale żaden z u, f i s.

Aby odpowiednio powiedzieć, czy litery są dobrym kryterium do określenia, jakie zabawki lubi jego córka, ojciec musiałby poznać preferencje córki dotyczące olbrzymiej ilości zabawek¹ - lub po prostu użyć jego mózgu i wziąć pod uwagę tylko parametry, które faktycznie mogą wpłynąć na córkę opinia.

$2^{26}$

• Pomyśl o okręgu zamkniętym w kwadracie jednostki.
• Pomyśl o kuli zamkniętej w sześcianie jednostkowym.
• Pomyśl o n-wymiarowej hiperferze zamkniętej w n-wymiarowej jednostkowej hipersześcianie.

$1^n$

$\infty$

$\pi/4$$\pi/6$$\infty$

Ja: „Mam na myśli małe brązowe zwierzę zaczynające się na„ S ”. Co to jest?”

Jej: „Wiewiórka!”

Ja: „OK, trudniejsze. Mam na myśli małe brązowe zwierzę. Co to jest?”

Jej: „Nadal wiewiórka?”

Ja nie"

Jej: „Szczur, mysz, nornik?

Ja: „Nie”

Jej: „Umm ... daj mi wskazówkę”

Ja: „Nie, ale zrobię coś lepszego: pozwolę ci odpowiedzieć na pytanie CrossValidated”

Jej: [jęczy]

Ja: „Pytanie brzmi: jaka jest klątwa wymiarowości? A ty już znasz odpowiedź”

Jej: „Tak?”

Ja: „Masz. Dlaczego trudniej było zgadnąć pierwsze zwierzę niż drugie?”

Jej: „Ponieważ jest więcej małych brązowych zwierząt niż małych brązowych zwierząt zaczynających się na„ S ”?”

Ja: „Racja. I to jest przekleństwo wymiarowości. Zagrajmy jeszcze raz.”

Jej: „OK”

Ja: „Myślę o czymś. Co to jest?”

Jej: „Nie fair. Ta gra jest zbyt trudna”.

Ja: „To prawda. Dlatego nazywają to przekleństwem. Po prostu nie da się dobrze, nie wiedząc o rzeczach, o których zwykle myślę.”

Załóżmy, że chcesz wysłać niektóre towary. Chcesz zmarnować jak najmniej miejsca podczas pakowania towarów (tzn. Zostaw możliwie jak najmniej pustej przestrzeni), ponieważ koszty wysyłki są związane z ilością koperty / pudełka. Pojemniki do Państwa dyspozycji (koperty, pudełka) są ustawione pod kątem prostym, więc nie ma worków itp.

Pierwszy problem: wyślij długopis („linię”) - możesz zbudować wokół niego pudełko bez utraty miejsca.

Drugi problem: dostarcz dysk CD („kula”). Musisz umieścić go w kwadratowej kopercie. W zależności od wieku dziecko może obliczyć, ile koperty pozostanie puste (i nadal będzie wiedział, że są płyty CD, a nie tylko pliki do pobrania ;-)).

Trzeci problem: wysłać piłkę nożną (piłka nożna i musi być napompowana!). Musisz umieścić go w pudełku, a część miejsca pozostanie pusta. Ta pusta przestrzeń będzie większym ułamkiem całkowitej objętości niż w przykładzie z CD.

W tym momencie moja intuicja wykorzystująca tę analogię kończy się, ponieważ nie wyobrażam sobie czwartego wymiaru.

EDYCJA: Analogia jest najbardziej użyteczna (jeśli w ogóle) do estymacji nieparametrycznej, która wykorzystuje obserwacje „lokalne” do interesującego miejsca, aby oszacować, powiedzmy, gęstość lub funkcję regresji w tym punkcie. Klątwą wymiarowości jest to, że w wyższych wymiarach albo potrzebujemy znacznie większego sąsiedztwa dla danej liczby obserwacji (co sprawia, że ​​pojęcie lokalizacji jest wątpliwe), albo dużej ilości danych.

Moje 6 lat to bardziej werset z badań nad pierwotną przyczyną, jak w „ale skąd się wziął cały ten gaz we wszechświecie?”… Cóż, wyobrażam sobie, że twoje dziecko rozumie „wyższe wymiary”, co wydaje się bardzo mało prawdopodobne dla mnie.

$n$$[0,1]^n$$\left[ {1\over2}, {1\over2}\right]^n$

$\left({1\over 2}\right)^n$$2^n$

A teraz idź po swój pokój, tata musi pracować.

$2^n$${1\over 2}$

Pokazuje to klasyczny, podręcznikowy problem matematyczny.

Czy wolisz zarabiać (opcja 1) 100 groszy dziennie, każdego dnia przez miesiąc, czy (opcja 2) grosz podwajany codziennie przez miesiąc? Możesz zadać swojemu dziecku to pytanie.

Jeśli wybierzesz opcję 1,
w dniu 1 dostaniesz 100 groszy w dniu 2 otrzymasz 100 groszy w dniu 3 dostaniesz 100 groszy ... w dniu 30 dostaniesz 100 groszy

$n^{th}$

łączną liczbę centów oblicza się, mnożąc liczbę dni przez liczbę centów dziennie:

Jeśli wybierzesz opcję 2:
w dniu 1 dostajesz 1 grosz w dniu 2 dostajesz 2 grosz w dniu 3 dostajesz 4 grosz w dniu 4 dostajesz 8 grosz w dniu 5 dostajesz 16 grosz ... w dniu 30 dostajesz 1 073,741,824 grosze

$n^{th}$$2^n$

Każdy z chciwością wybierze większą liczbę. Prosta chciwość jest łatwa do znalezienia i nie wymaga wielu przemyśleń. Niewymowne zwierzęta są łatwo zdolne do zachłanności - owady są w tym bardzo dobre. Ludzie są zdolni do znacznie więcej.

Jeśli zaczniesz od jednego grosza zamiast stu, chciwość jest łatwiejsza, ale jeśli zmienisz moc wielomianu, będzie to bardziej skomplikowane. Kompleks może również oznaczać o wiele bardziej wartościowy.

O „klątwie”
„Najważniejszym” związanym z fizyką działaniem matematycznym jest odwrócenie macierzy. Steruje rozwiązaniami układów równań różniczkowych cząstkowych, z których najczęstsze to równania Maxwella (elektromagnetyczne), równania Naviera Stokesa (płyny), równania Poissona (przeniesienie dyfuzyjne) oraz wariacje na temat prawa Hookesa (ciał odkształcalnych). Każde z tych równań ma zbudowane wokół nich kursy uniwersyteckie.

$n^3$

Klątwa istnieje, ponieważ jeśli zostanie pokonana, na końcu tęczy znajduje się garnek o złotej wartości. To nie jest łatwe - wielkie umysły energicznie zaangażowały się w problem.

połączyć:

• https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

Fcop oferował świetną analogię do plików cookie, ale obejmował tylko aspekt gęstości próbkowania przekleństwa wymiarowości. Możemy rozszerzyć tę analogię na objętość próbkowania lub odległość, dystrybuując tę ​​samą liczbę ciasteczek Fcop w, powiedzmy, dziesięciu pudełkach w jednej linii, 10x10 pudełek płasko na stole i 10x10x10 w stosie. Następnie możesz pokazać, że aby zjeść tę samą część plików cookie, dziecko będzie musiało otwierać coraz więcej pudełek.

Tak naprawdę chodzi o oczekiwania, ale zilustrujmy to podejściem „najgorszego scenariusza”.

Jeśli jest 8 ciasteczek i chcemy zjeść połowę, tj. 4, z 10 pudełek w najgorszym przypadku wystarczy otworzyć tylko 6 pudełek. To 60% - również około połowy. Od 10x10 (znowu w najgorszym przypadku) - 96 (%). I od 10x10x10 - 996 (99,6%). To prawie wszystkie z nich!

Może to być analogia do przechowalni, a odległość między pokojami byłaby lepsza niż pudła.