Wyjaśniono przekleństwo uczenia maszynowego dotyczące wymiarowości?

Mam problem ze zrozumieniem przekleństwa wymiarowości. W szczególności natknąłem się na to podczas wykonywania scikit-learnsamouczka w Pythonie. Czy ktoś może wyjaśnić poniżej w prostszy sposób? Przepraszam, staram się zrozumieć od dłuższego czasu i nie mogę zrozumieć, w jaki sposób wymyślili obliczenia liczby przykładów szkoleń, aby uzyskać skuteczny estymator KNN?

Oto wyjaśnienie:

Aby estymator był skuteczny, odległość między sąsiednimi punktami musi być mniejsza niż pewna wartość d, co zależy od problemu. W jednym wymiarze wymaga to średnio n ~ 1 / d punktów. W kontekście powyższego przykładu KNN, jeśli dane są opisane tylko przez jedną cechę o wartościach od 0 do 1 i n obserwacjach treningowych, wówczas nowe dane nie będą dalej niż 1 / n. Dlatego reguła decyzji najbliższego sąsiada będzie skuteczna, gdy tylko 1 / n będzie mała w porównaniu ze skalą wariantów cech międzyklasowych.

Jeśli liczba funkcji wynosi p, teraz potrzebujesz n ~ 1 / d ^ p punktów. Powiedzmy, że potrzebujemy 10 punktów w jednym wymiarze: Teraz 10 ^ p punktów jest wymaganych w wymiarach p, aby ułożyć przestrzeń [0, 1]. Gdy p staje się duże, liczba punktów treningowych wymaganych dla dobrego estymatora rośnie wykładniczo.

link tutaj

EDYCJA: czy tylda ( ~) ma reprezentować przybliżenie w tym przykładzie? lub operator tylda python?

Tłumaczenie tego akapitu:

Niech powstanie zestaw funkcji opisujących punkt danych. Może patrzysz na pogodę. Ten zestaw funkcji może obejmować takie rzeczy, jak temperatura, wilgotność, pora dnia itp. Więc każdy punkt danych może mieć jedną cechę (jeśli patrzysz tylko na temperaturę) lub może mieć 2 cechy (jeśli patrzysz na temperaturę i wilgotność) i tak dalej. Ten akapit mówi, że w oparciu o liczbę wymiarów danych (liczbę funkcji), tym trudniej jest dokonać oszacowania. Wynika to z faktu, że jeśli po prostu masz jedną cechę danych lub dane jednowymiarowe, to kiedy przejdziesz do wykresu tych danych, otrzymasz wykres liniowy i wyobrażając sobie wykres liniowy między, powiedzmy, 0-50 stopni C, wystarczy tylko 50 losowych punktów przed każdym punktem danych znajduje się około 1 stopnia od dowolnego innego punktu danych. Teraz pozwól' Pomyślmy o 2 wymiarach, mówiąc o wilgotności i temperaturze, teraz trudniej jest znaleźć takie d, że wszystkie punkty znajdują się w jednostkach „d” od siebie. Wyobraź sobie, że temperatura wciąż wynosi od 0 do 50, ale teraz wilgotność wynosi od 0 do 100%. Ile losowych punktów potrzeba, aby uzyskać wszystkie punkty w odległości 1 lub 2 od siebie? Teraz jest 100 * 50 lub ~ 5000! Teraz wyobraź sobie 3 wymiary itp. Zaczynasz potrzebować znacznie więcej punktów, aby upewnić się, że każdy punkt znajduje się w odległości d od innego punktu. Aby ułatwić Ci życie, spróbuj założyć, że „d” to 1 i zobacz, co się stanie. Mam nadzieję, że to pomaga! Ile losowych punktów potrzeba, aby uzyskać wszystkie punkty w odległości 1 lub 2 od siebie? Teraz jest 100 * 50 lub ~ 5000! Teraz wyobraź sobie 3 wymiary itp. Zaczynasz potrzebować znacznie więcej punktów, aby upewnić się, że każdy punkt znajduje się w odległości d od innego punktu. Aby ułatwić Ci życie, spróbuj założyć, że „d” to 1 i zobacz, co się stanie. Mam nadzieję, że to pomaga! Ile losowych punktów potrzeba, aby uzyskać wszystkie punkty w odległości 1 lub 2 od siebie? Teraz jest 100 * 50 lub ~ 5000! Teraz wyobraź sobie 3 wymiary itp. Zaczynasz potrzebować znacznie więcej punktów, aby upewnić się, że każdy punkt znajduje się w odległości d od innego punktu. Aby ułatwić Ci życie, spróbuj założyć, że „d” to 1 i zobacz, co się stanie. Mam nadzieję, że to pomaga!

matty-d udzielił już bardzo dobrej odpowiedzi, ale znalazłem inną odpowiedź, która równie dobrze wyjaśnia ten problem, od użytkownika Quora, Kevina Lackera:

Powiedzmy, że masz linię prostą o długości 100 jardów i gdzieś na niej upuściłeś grosz. Nie byłoby trudno go znaleźć. Idziesz wzdłuż linii i zajmuje to dwie minuty.

Teraz załóżmy, że masz kwadrat 100 jardów z każdej strony i upuściłeś gdzieś na nim grosz. Byłoby to dość trudne, jak przeszukanie dwóch połączonych ze sobą boisk piłkarskich. Może to zająć dni.

Teraz sześcian o średnicy 100 metrów. To tak, jakby przeszukać 30-piętrowy budynek wielkości stadionu piłkarskiego. Ugh.

Trudność przeszukiwania przestrzeni staje się znacznie trudniejsza, ponieważ masz więcej wymiarów. Być może nie zdajesz sobie z tego sprawy intuicyjnie, gdy jest to określone we wzorach matematycznych, ponieważ wszystkie mają tę samą „szerokość”. To przekleństwo wymiarowości. Ma nazwę, ponieważ jest nieintuicyjna, użyteczna, a jednocześnie prosta.

Ten przykład może dać trochę intuicji na temat problemu, ale w rzeczywistości nie jest wcale rygorystycznym dowodem: jest to tylko przykład, w którym potrzeba wielu próbek, aby uzyskać „dobre” pokrycie przestrzeni. Mogłoby być (a już są np. Sześciokąty już w 2D) znacznie bardziej wydajne pokrycia niż zwykła siatka ... (poświęcony jest temu wyrafinowany obszar sekwencji o niskiej rozbieżności) ... i udowadniając, że nawet przy tak lepszych pokryciach wciąż istnieje pewna klątwa wymiarów, to zupełnie inna kwestia. W rzeczywistości w niektórych obszarach funkcji istnieją nawet sposoby na obejście tego pozornego problemu.