Studiuję PCA z kursu Andrew Ng Coursera i innych materiałów. W pierwszym zadaniu cs224n na kursie NLP w Stanford oraz w filmie wykładowym Andrew Ng dokonują dekompozycji wartości pojedynczej zamiast dekompozycji wektorów własnych macierzy kowariancji, a Ng twierdzi nawet, że SVD jest liczbowo bardziej stabilny niż skład eigend.
Z mojego zrozumienia, dla PCA powinniśmy wykonać SVD macierzy danych (m,n)
wielkości, a nie macierzy kowariancji (n,n)
wielkości. I rozkład własny wektora macierzy kowariancji.
Dlaczego robią SVD macierzy kowariancji, a nie macierzy danych?
pca
linear-algebra
svd
eigenvalues
numerics
DongukJu
źródło
źródło
x=randn(10000); x=x'*x; tic; eig(x); toc; tic; svd(x); toc;
na moim komputerze wyświetla 12s dla eig () i 26s dla svd (). Jeśli jest o wiele wolniejszy, musi przynajmniej być bardziej stabilny! :-)eig
lubsvd
na macierzy kowariancji, ale o ile wiem, nie ma dużej różnicy między użyciemeig
lubsvd
macierzą kowariancji - są oba algorytmy stabilne wstecz. Jeśli już, to postawiłbym swoje pieniądze na większą stabilność eig , ponieważ robi mniej obliczeń (zakładając, że oba są zaimplementowane przy użyciu najnowocześniejszych algorytmów).Odpowiedzi:
ameba udzieliła już dobrej odpowiedzi w komentarzach, ale jeśli chcesz formalnego argumentu, oto on.
Rozkład macierzy liczbie pojedynczej to , gdzie kolumny są wektorami własnymi a przekątne wpisy są pierwiastkami kwadratowymi jego wartości własnych, tj. .A = U Σ V T V A T A Σ σ i i = √A A=UΣVT V ATA Σ σii=λi(ATA)−−−−−−−√
Jak wiecie, głównymi składnikami są ortogonalne rzuty zmiennych na przestrzeń wektorów własnych empirycznej macierzy kowariancji . Wariancja składników jest podana przez jej wartości własne, .λi(11n−1ATA λi(1n−1ATA)
Rozważ dowolną macierz kwadratową , i wektor taki, że . Następnieα ∈ R v B v = λ vB α∈R v Bv=λv
Zdefiniujmy . SVD z obliczy składową elektroniczną aby uzyskaćS=1n−1ATA S STS=1(n−1)2ATAATA
Voilà!
Jeśli chodzi o stabilność liczbową, należałoby dowiedzieć się, jakie są zastosowane alogrithmy. Jeśli jesteś gotów, sądzę, że są to procedury LAPACK używane przez numpy:
Aktualizacja: Jeśli chodzi o stabilność, wydaje się, że implementacja SVD wykorzystuje podejście dziel i zwyciężaj, podczas gdy w składzie eigend zastosowano prosty algorytm QR. Nie mogę uzyskać dostępu do niektórych istotnych dokumentów SIAM z mojej instytucji (cięcia w badaniach), ale znalazłem coś, co mogłoby poprzeć ocenę, że procedura SVD jest bardziej stabilna.
W
porównują stabilność różnych algorytmów wartości własnych i wydaje się, że podejście dziel i zwyciężaj (używają tego samego co numpy w jednym z eksperymentów!) jest bardziej stabilne niż algorytm QR. To, wraz z twierdzeniami gdzie indziej, że metody D&C są rzeczywiście bardziej stabilne, popiera wybór Ng.
źródło
@amoeba miał doskonałe odpowiedzi na pytania PCA, w tym na temat stosunku SVD do PCA. Odpowiadając na twoje dokładne pytanie, podniosę trzy punkty:
Okazuje się, że SVD jest bardziej stabilny niż typowe procedury dekompozycji wartości własnej, szczególnie w przypadku uczenia maszynowego. W uczeniu maszynowym łatwo jest uzyskać bardzo kolinearne regresory. SVD działa lepiej w tych przypadkach.
Oto kod Pythona, aby pokazać punkt. Stworzyłem wysoce współliniową macierz danych, uzyskałem jej macierz kowariancji i próbowałem uzyskać wartości własne tej ostatniej. SVD nadal działa, podczas gdy zwykły rozkład własny nie udaje się w tym przypadku.
Wydajność:
Aktualizacja
Odpowiadając na komentarz Federico Poloni, oto kod z testami stabilności SVD vs Eig na 1000 losowych próbkach tej samej matrycy powyżej. W wielu przypadkach Eig wykazuje 0 małych wartości własnych, co prowadziłoby do osobliwości macierzy, a SVD nie robi tego tutaj. SVD jest około dwa razy bardziej precyzyjny przy niewielkim określaniu wartości własnej, co może, ale nie musi być ważne, w zależności od twojego problemu.
Wydajność:
Tutaj kod działa kod. Zamiast generować losową macierz kowariancji do testowania procedur, generuję macierz losowych danych z dwiema zmiennymi: gdzie - niezależne jednolite zmienne losowe. Zatem macierz kowariancji to gdzie - wariancje mundurów i współczynnik korelacji między im.u , v ( σ 2 1 σ 2 1
Jego najmniejsza wartość własna: Mała wartość własna nie może być obliczona po prostu podłączając do formuły ze względu na ograniczoną precyzję, więc musisz go rozwinąć:
Wykonuję symulacje realizacji macierzy danych, obliczam wartości własne symulowanej macierzy kowariancji i otrzymuję błędy .λ j e j = λ - λ jj=1,…,m λ^j ej=λ−λ^j
źródło
Użytkownikom Pythona chciałbym zauważyć, że w przypadku macierzy symetrycznych (takich jak macierz kowariancji) lepiej jest użyć
numpy.linalg.eigh
funkcji zamiastnumpy.linalg.eig
funkcji ogólnej .eigh
jest 9-10 razy szybszy niżeig
na moim komputerze (niezależnie od rozmiaru matrycy) i ma lepszą dokładność (na podstawie testu dokładności @ Aksakal).Nie jestem przekonany do wykazania korzyści z dokładności SVD przy małych wartościach własnych. Test Aksakala jest o 1-2 rzędy wielkości bardziej wrażliwy na losowy stan niż na algorytm (spróbuj wykreślić wszystkie błędy zamiast zmniejszać je do jednego absolutnego maksimum). Oznacza to, że małe błędy w macierzy kowariancji będą miały większy wpływ na dokładność niż wybór algorytmu składowego eigend. Nie ma to również związku z głównym pytaniem, które dotyczy PCA. Najmniejsze komponenty są ignorowane w PCA.
Podobny argument można postawić na temat stabilności liczbowej. Gdybym musiał użyć metody macierzy kowariancji dla PCA, rozłożyłbym ją za pomocą
eigh
zamiastsvd
. Jeśli się nie powiedzie (czego tu jeszcze nie pokazano), prawdopodobnie warto przemyśleć problem, który próbujesz rozwiązać, zanim zaczniesz szukać lepszego algorytmu.źródło
eigh
vseig
: mail.scipy.org/pipermail/numpy-discussion/2006-March/…Aby odpowiedzieć na ostatnią część pytania: „Dlaczego robią SVD macierzy kowariancji, a nie macierzy danych?”. Uważam, że dzieje się tak ze względu na wydajność i pamięć. Zazwyczaj będzie bardzo dużą liczbą i nawet jeśli jest duże, spodziewalibyśmy się .n m ≫ nm n m≫n
Obliczenie macierzy kowariancji, a następnie wykonanie SVD na tym jest znacznie szybsze niż obliczenie SVD na pełnej macierzy danych w tych warunkach, dla tego samego wyniku.
Nawet przy dość małych wartościach wzrost wydajności jest współczynnikiem tysięcy (milisekund vs sekund). Uruchomiłem kilka testów na moim komputerze, aby porównać za pomocą Matlaba:
To tylko czas pracy procesora, ale potrzeby w zakresie pamięci masowej są tak samo ważne, jeśli nie większe. Jeśli spróbujesz SVD na matrycy milion na tysiąc w Matlabie, domyślnie wystąpi błąd, ponieważ potrzebuje działającej wielkości tablicy 7,4 TB.
źródło