11 · Prawa i prawdy · 3 min czytania · aktualizacja
Czym jest hipoteza rozmaitości i dlaczego dane wysokowymiarowe da się modelować?
W skrócie
Dane wysokowymiarowe, jak obrazy czy dźwięk, skupiają się blisko powierzchni o znacznie niższym wymiarze. Dlatego uczenie z nich jest w ogóle wykonalne.
Co to jest
Dane rzeczywiste opisywane przez wiele zmiennych leżą w pobliżu rozmaitości (gładkiej „powierzchni”) o wymiarze znacznie niższym niż liczba tych zmiennych. To założenie robocze, a nie twierdzenie; stało się popularne w uczeniu maszynowym po pracach nad nieliniową redukcją wymiaru z 2000 roku (Isomap, LLE), a sprawdzalną statystycznie wersję zaproponowali Charles Fefferman, Sanjoy Mitter i Hariharan Narayanan w 2016 roku.
Przykład: obraz 8×8 pikseli to punkt w przestrzeni 64-wymiarowej. Gdyby losować wartości pikseli, prawie zawsze dostalibyśmy szum — obrazy cyfr zajmują znikomy ułamek tej przestrzeni. Co więcej, cyfrę „3” można płynnie zmieniać kilkoma pokrętłami: grubością kreski, nachyleniem, rozmiarem pętli. Tych pokręteł jest kilka–kilkanaście, nie 64. To one są „prawdziwymi” współrzędnymi danych.
Hipoteza tłumaczy, dlaczego przekleństwo wymiarowości nie zabija uczenia na obrazach czy tekście: efektywny wymiar problemu jest niski.
Mechanizm — dlaczego tak działa
Dane powstają w procesach z niewieloma stopniami swobody. Zdjęcie twarzy zależy od tożsamości, oświetlenia, pozy i mimiki — kilkudziesięciu parametrów — a nie od niezależnego wyboru miliona pikseli. Fizyka i biologia nakładają ograniczenia: sąsiednie piksele są skorelowane, mięśnie twarzy poruszają się w określony sposób. Wynik to wysokowymiarowy zapis niskowymiarowego zjawiska.
Konsekwencje dla uczenia: przekleństwo wymiarowości skaluje się z wymiarem wewnętrznym, nie z liczbą kolumn. Pope i in. (2021) oszacowali, że popularne zbiory obrazów mają wymiar wewnętrzny rzędu kilkudziesięciu, i pokazali, że to on, a nie liczba pikseli, przewiduje trudność uczenia. Autoenkodery, embeddingi i modele generatywne można rozumieć jako próby odnalezienia współrzędnych na tej rozmaitości; przykłady adwersarialne — jako punkty tuż obok niej, gdzie model nie ma danych.
Zastrzeżenia. Rozmaitość rzadko jest jedna i gładka: klasy mogą tworzyć osobne kawałki o różnych wymiarach, a szum rozmywa je w otoczce. Liniowe metody (PCA) zawyżają wymiar zakrzywionej rozmaitości. Estymatory wymiaru wewnętrznego są obciążone i zależą od skali, na którą patrzymy. Hipoteza jest więc bardzo użyteczną idealizacją, a nie dokładnym opisem.
Na przykładzie
Digits 8×8 (1797 obrazów, 64 piksele). PCA potrzebuje 13 składowych, by wyjaśnić 80% wariancji, 21 — dla 90%, 29 — dla 95% i 41 — dla 99%. To już mniej niż 64, ale PCA widzi tylko płaskie podprzestrzenie. Nieliniowe estymatory wymiaru wewnętrznego dają mniej: estymator największej wiarygodności Leviny i Bickela (k = 10 sąsiadów) — 8,8, estymator TwoNN — 9,0. Dla poszczególnych cyfr wynik waha się od 6,6 (jedynki) do 10,7 (zera).
Dla porównania: 1797 punktów z jednostajnego szumu w 64 wymiarach daje tym samym estymatorem 38 (estymator zaniża przy tak małej próbce, ale różnica jest wyraźna). Mediana odległości obrazu cyfry do najbliższej innej cyfry to 16,1, a losowego obrazu szumu do najbliższej cyfry — 56,9. Cyfry tworzą zwartą, niskowymiarową strukturę; szum leży daleko od niej.
Dane: Digits (ręcznie pisane cyfry 8×8)
W praktyce
- Wizualizacja rozmaitości:
TSNE,umap.UMAP,Isomap,LocallyLinearEmbedding(scikit-learn, pakiet umap-learn). - Krzywa
PCA().explained_variance_ratio_.cumsum()daje górne oszacowanie wymiaru; metody nieliniowe zwykle wskazują mniej. - Autoenkoder z wąskim gardłem (
nn.Linear(64, 10)) to praktyczny test, ile wymiarów wystarcza do odtworzenia danych. - Augmentacja danych (przesunięcia, obroty) dodaje przykłady wzdłuż rozmaitości — tam, gdzie model będzie testowany.
- Odległość euklidesowa w surowych cechach mierzy odległość „na skróty” przez pustą przestrzeń; odległości w embeddingach są zwykle sensowniejsze.
Najczęstsze pytania
- Czy hipoteza rozmaitości została udowodniona?
- Nie w sensie ogólnym — to empiryczna obserwacja o konkretnych typach danych. Istnieją testy statystyczne (Fefferman i in.) i liczne pomiary wymiaru wewnętrznego, które ją wspierają dla obrazów, dźwięku i tekstu.
- Jak zmierzyć wymiar wewnętrzny danych?
- Najprościej liczbą składowych PCA potrzebnych do wyjaśnienia większości wariancji (górne oszacowanie). Dokładniej estymatorami opartymi na odległościach do najbliższych sąsiadów, np. MLE Leviny–Bickela lub TwoNN.
- Czy dane tabelaryczne też leżą na rozmaitościach?
- Często częściowo — skorelowane cechy obniżają wymiar efektywny. Ale dane tabelaryczne mieszają zmienne kategoryczne i ciągłe, więc obraz gładkiej powierzchni pasuje do nich gorzej niż do obrazów.
Źródła
- Fefferman C., Mitter S., Narayanan H. (2016). Testing the Manifold Hypothesis. Journal of the American Mathematical Society, 29(4), 983–1049.
- Tenenbaum J. B., de Silva V., Langford J. C. (2000). A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science, 290(5500), 2319–2323.
- Levina E., Bickel P. J. (2004). Maximum Likelihood Estimation of Intrinsic Dimension. Advances in Neural Information Processing Systems 17.
- Pope P., Zhu C., Abdelkader A., Goldblum M., Goldstein T. (2021). The Intrinsic Dimension of Images and Its Impact on Learning. ICLR 2021.
- Goodfellow I., Bengio Y., Courville A. (2016). Deep Learning. MIT Press, rozdz. 5.11.3.