Quantum Computing: A Beginner's Guide

Problem: zbyt wiele osi do obejrzenia

Rzeczywiste zbiory danych często żyją w dziesiątkach, setkach lub tysiącach wymiarów, a ludzkie wzrokowanie działa tylko w dwóch lub trzech. Redukcja wymiarowości znajduje niskowymiarowe układ współrzędnych, które jak najbardziej zachowują istotną strukturę wysokowymiarowych danych, tak aby klastry, gradienty i wartości odstępczego były niewidoczne w tabeli liczb, stały się widoczne na wykresie rozrzutowym. Trzy techniki porównane tutaj – PCA, t-SNE i UMAP – rozwiązują ten problem przy użyciu fundamentalnie różnych matematyki i fundamentalnie różnych koncepcji tego, co oznacza „zachowanie struktury”.

Analiza Głównych Składowych (PCS): najlepsza możliwa liniowa projekcja cienia

Analiza Głównych Składowych (PCS) zadaje czysto liniowe pytanie: który kierunek w danych uchwyca najwięcej zmienności? Centralizuj dane, oblicz macierz kowariancji Σ i przekształć ją następująco:

Σ = (1/n) XᵀX (Dane zcentralizowane liniowo, wiersze = próbki) Σ vi = λi vi wektory własne vi = składowe główna wartości własne λi = zmienność wzdłuż vi przekształć na k najlepszych wektorów własnych → widok o wymiarze k, który zachowuje jak największą całkowitą zmienność dla dowolnej projekcji liniowej Równoważnie, PCS wypływa bezpośrednio z rozkładu wartości osobliwych X = UΣVᵀ: wektory osobliwe prawe V są składowymi głównymi, a wartości osobliwe w Σ są proporcjonalne do pierwiastków kwadratowych z powyższych wartości własnych. Ponieważ jest to sztywna projekcja liniowa – dosłownie obracając dane i odrzucając osie o niskiej zmienności – PCS jest szybka (jedna dekompozycja ejszena, bez iteracji), deterministyczna i odwracalna w sensie, że zawsze wiemy dokładnie, jaką zmienność wyrzucono (stosunek odrzuconych do całkowitych wartości własnych).

Σ = (1/n) XᵀX                      (X mean-centred, rows = samples)
Σ vi = λi vi                       eigenvectors vi = principal components
                                    eigenvalues λi  = variance along vi

project onto the top k eigenvectors → the k-dimensional view that
                                       preserves the most total variance
                                       of any linear projection

t-SNE: Zachowanie sąsiadów, nie odległości

Uczenie się dystrybucji t-rozłożonych (t-SNE), wprowadzone przez van der Maaten i Hintona w 2008 roku, rezygnuje z zachowania odległości globalnie i zamiast tego próbuje zachować relacje sąsiedztwa. W przestrzeni o wysokiej wymiarowości przekształca parzyste odległości w prawdopodobieństwa warunkowe, wskazujące, że punkt j jest sąsiadem punktu i, używając rozkładu Gaussa, którego szerokość pasma jest dostosowywana dla każdego punktu na podstawie docelowej perplexity (luźno mówiąc, skuteczny licznik sąsiadów – typowe wartości 5 do 50):

pj|i ∝ exp( −||xi − xj||² / 2σi² ) szerokość pasma σi ustawiana na podstawie docelowej perplexity pij = (pj|i + pi|j) / 2n symmetryzowane prawdopodobieństwo warunkowe in przestrzeni o niskiej wymiarowości, używany jest rozkład Student-t o ciężkich ogonach: qij ∝ (1 + ||yi − yj||²)⁻¹ minimalizować KL(P ‖ Q) = Σ pij log(pij / qij) gradientem opadającym na yi Ciężki ogon rozkładu Student-t w przestrzeni o niskiej wymiarowości (zamiast innej Gaussi) jest kluczowym trikiem i rozwiązuje problem zagęszczenia, którego van der Maaten i Hinton nazwali: przestrzeń o wysokiej wymiarowości po prostu ma miejsce na znacznie więcej sąsiadów o równych odległościach niż płaszczyzna 2D, więc symetryczne embedding Gaussa jest zmuszone albo ścisną blisko siebie umiarkowane odległości, albo użyć nieuzasadnionych dużych odległości dla oddalonych punktów. Ogony rozkładu t są grubsze, co pozwala umiarkowanie różnym punktom wygodnie rozmieścić się daleko od siebie na mapie bez konieczności rozmieszczania blisko siebie również innych punktów, co nadaje t-SNE jego charakterystyczne ciasne, dobrze oddzielone klastry. Ceny to fakt, że tylko lokalna struktura jest niezawodna: rozmiary klastrów, odległości między klastrami i nawet liczba punktów znajdujących się w klastrze mogą być artefaktami perplexity i losowej inicjalizacji, a nie prawdziwej geometrii danych – klasyczną pułapką jest wyciąganie znaczenia z tego, jak daleko od siebie są t-SNE klastry, które algorytm w ogóle nie próbuje zachować.

pj|i ∝ exp( −||xi − xj||² / 2σi² )      per-point σi set by target perplexity
pij  = (pj|i + pi|j) / 2n               symmetrised joint probability

in the low-dimensional map, use a heavier-tailed Student-t distribution:
qij ∝ (1 + ||yi − yj||²)⁻¹

minimise  KL(P ‖ Q) = Σ pij log(pij / qij)   by gradient descent on the yi

UMAP: topologia zamiast prawdopodobieństwa

Uniform Manifold Approximation and Projection (McInnes, Healy & Melville, 2018) opiera się na innej koncepcji, zakorzenionej w analizie danych topologicznych: założenie, że dane o wysokiej wymiarowości leżą na (lub blisko) niweli o niższej wymiarowości, oraz próba odtworzenia rozmytej reprezentacji topologicznej tej niwy – dla każdego punktu tworzy się rozmyty zbiór symplicialny zbudowany z jego k najbliższych sąsiadów, gdzie wagi krawędzi maleją wraz z odległością tak samo jak prawdopodobieństwa w t-SNE, ale skala lokalnej odległości każdego punktu jest skalowana do jego własnego odległości od najbliższego sąsiada zamiast globalnego celu perplexity. Następnie optymalizuje się układ o niskiej wymiarowości, aby uzyskać najbardziej podobną topologię rozmytej, minimalizując entropię krzyżową między wysokowymiarowymi i nizmowymiarowymi zbiorami rozmyтыми, przy użyciu efektywnej stochastycznej metody gradientowej z próbkowaniem negatywnym zbliżonej w duchu do word2vec.

W praktyce UMAP zwykle działa zauważnie szybciej niż t-SNE na dużych zbiorach danych, a jego podstawy teoretyczne dają mu realną przewagę w zachowaniu bardziej globalnej struktury – względne położenia klastrów przenoszą nieco więcej informacji niż w t-SNE – choć nadal nie powinno się go interpretować jako zachowania prawdziwych odległości. Obie metody dzielą tę samą podstawową zasadę: są nieliniowe i stochastyczne, więc osie wykresu wyjściowego nie mają bezpośredniego znaczenia fizycznego (w przeciwieństwie do PCA, gdzie każda oś jest konkretną kombinacją liniową oryginalnych cech o znanym wariancie), a ponowne uruchomienie z innym ziarnem losowym lub parametrem może widocznie przemieszczać układ nawet wtedy, gdy relacje sąsiedzkie są podobne.

Które, i kiedy

PCA jest szybkie, deterministyczne, liniowe, osie są interpretowalne → pierwszy krok, przetwarzanie wstępne, struktura liniowa t-SNE jest wolniejsze (czasami), stochastyczne, doskonałe lokalne klastry, brak globalnej reprezentacji → eksploracja wizualna znaczenia odległości, wrażliwe na perplexity struktury klastrów UMAP jest szybsze niż t-SNE, lepiej zachowuje globalną strukturę, → dla dużych zbiorów danych, jest oparte na teorii, nadal nie zachowuje odległości w sposób dokładny w procesie/do użytku produkcyjnego Często stosowane i skuteczne podejście to łańcuch operacji: najpierw uruchamiamy PCA, aby zredukować, powiedzmy, 500 szumnych wymiarów do 30-50, które nadal uchwycą większość wariancji (co również redukuje szum i ogromnie przyspiesza to, co następuje), a następnie przekazujemy tę zmniejszoną reprezentację t-SNE lub UMAP do ostatecznego, nieliniowego embeddingu 2D lub 3D używanego do wizualizacji.

PCA      fast, deterministic, linear, axes are interpretable        →  first pass,
                                                                          preprocessing,
                                                                          linear structure
t-SNE    slow(er), stochastic, excellent local clusters, no global      →  visual exploration
         distance meaning, sensitive to perplexity                         of cluster structure
UMAP     faster than t-SNE, more global structure preserved,            →  large datasets,
         theoretically grounded, still not distance-preserving             pipeline/production use

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Dimensionality Reduction i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.