Dlaczego Andrew Ng woli używać SVD, a nie EIG macierzy kowariancji do PCA?

29

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?

DongukJu
źródło
8
W przypadku kwadratowej symetrycznej dodatniej macierzy półfinałowej (takiej jak macierz kowariancji) rozkład wartości własnej i wartości w liczbie pojedynczej są dokładnie takie same.
ameba mówi Przywróć Monikę
5
Mam na myśli, że są matematycznie takie same. Liczbowo mogą rzeczywiście używać różnych algorytmów i jeden może być bardziej stabilny niż inny (jak mówi Ng). Byłoby interesujące dowiedzieć się więcej o +1.
ameba mówi Przywróć Monikę
4
Kilka informacji na ten temat tutaj: de.mathworks.com/matlabcentral/newsreader/view_thread/21268 . Należy jednak pamiętać, że każde wyjaśnienie, dlaczego jeden algorytm byłby bardziej stabilny niż inny, będzie bardzo techniczne.
ameba mówi Przywróć Monikę
2
W Matlabie 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! :-)
ameba mówi Przywróć Monikę
4
Może to wynikać z niepoprawnego zrozumienia: wykonanie SVD macierzy danych jest bardziej stabilne niż użycie eiglub svdna macierzy kowariancji, ale o ile wiem, nie ma dużej różnicy między użyciem eiglub svdmacierzą 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).
Federico Poloni

Odpowiedzi:

17

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 = AA=UΣVTVATAΣσ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(11n1ATAλi(1n1ATA)

Rozważ dowolną macierz kwadratową , i wektor taki, że . Następnieα R v B v = λ vBαRvBv=λv

  1. Bkv=λkv
  2. λ(αB)=αλ(B)

Zdefiniujmy . SVD z obliczy składową elektroniczną aby uzyskaćS=1n1ATASSTS=1(n1)2ATAATA

  1. wektory własne , które przez właściwość 1 są wektorami(ATA)TATA=ATAATAATA
  2. te pierwiastki kwadratowe o wartości własnych , która z właściwości 2, a następnie 1, a następnie 2 ponownie, to .1(n1)2ATAATA1(n1)2λi(ATAATA)=1(n1)2λi2(ATA)=1n1λi(ATA)=λi(1n1ATA)

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

Nakatsukasa, Yuji i Nicholas J. Higham. „Stabilne i wydajne algorytmy podziału i zdobycia widma dla symetrycznego rozkładu wartości własnych i SVD.” SIAM Journal on Scientific Computing 35.3 (2013): A1325-A1349.

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.

broncoAbierto
źródło
Wartości własne, które uzyskałem z svd na kowariancji i svd na średnich środkowych danych, nie są takie same.
theGD
Jednak wyniki, to jest X * V (gdzie V jest uzyskiwane z [U, S, V] = svd (x) lub svd (covx)), są takie same.
theGD
1
@GD Wartości własne cov (X) i liczby osobliwe (X) nie są identyczne, patrz stats.stackexchange.com/questions/134282 .
ameba mówi Przywróć Monikę
nie ma potrzeby rozpaczać z powodu braku dostępu do czasopism SIAM: cytowany
Dima Pasechnik
2
@broncoAbierto the tech. raport jest tutaj: cpsc.yale.edu/sites/default/files/files/tr932.pdf (prawdopodobnie nie można go łatwo znaleźć z powodu literówki „Symetric” w tytule na cpsc.yale.edu/research/technical-reports / 1992-raporty techniczne :-))
Dima Pasechnik
12

@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:

  • matematycznie nie ma różnicy, czy PCA oblicza się bezpośrednio na macierzy danych, czy na jej macierzy kowariancji
  • różnica wynika wyłącznie z precyzji liczbowej i złożoności. Zastosowanie zastosowania SVD bezpośrednio do macierzy danych jest liczbowo bardziej stabilne niż do macierzy kowariancji
  • SVD można zastosować do macierzy kowariancji w celu wykonania PCA lub uzyskania wartości własnych, w rzeczywistości jest to moja ulubiona metoda rozwiązywania problemów własnych

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.

import numpy as np
import math
from numpy import linalg as LA

np.random.seed(1)

# create the highly collinear series
T = 1000
X = np.random.rand(T,2)
eps = 1e-11
X[:,1] = X[:,0] + eps*X[:,1]

C = np.cov(np.transpose(X))
print('Cov: ',C)

U, s, V = LA.svd(C)
print('SVDs: ',s)

w, v = LA.eig(C)
print('eigen vals: ',w)

Wydajność:

Cov:  [[ 0.08311516  0.08311516]
 [ 0.08311516  0.08311516]]
SVDs:  [  1.66230312e-01   5.66687522e-18]
eigen vals:  [ 0.          0.16623031]

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.

import numpy as np
import math
from scipy.linalg import toeplitz
from numpy import linalg as LA

np.random.seed(1)

# create the highly collinear series
T = 100
p = 2
eps = 1e-8

m = 1000 # simulations
err = np.ones((m,2)) # accuracy of small eig value
for j in range(m):
    u = np.random.rand(T,p)
    X = np.ones(u.shape)
    X[:,0] = u[:,0]
    for i in range(1,p):
        X[:,i] = eps*u[:,i]+u[:,0]

    C = np.cov(np.transpose(X))

    U, s, V = LA.svd(C)

    w, v = LA.eig(C)

    # true eigen values
    te = eps**2/2 * np.var(u[:,1])*(1-np.corrcoef(u,rowvar=False)[0,1]**2)
    err[j,0] = s[p-1] - te
    err[j,1] = np.amin(w) - te


print('Cov: ',C)
print('SVDs: ',s)
print('eigen vals: ',w)
print('true small eigenvals: ',te)

acc = np.mean(np.abs(err),axis=0)    
print("small eigenval, accuracy SVD, Eig: ",acc[0]/te,acc[1]/te)

Wydajność:

Cov:  [[ 0.09189421  0.09189421]
 [ 0.09189421  0.09189421]]
SVDs:  [ 0.18378843  0.        ]
eigen vals:  [  1.38777878e-17   1.83788428e-01]
true small eigenvals:  4.02633695086e-18
small eigenval, accuracy SVD, Eig:  2.43114702041 3.31970128319

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

x1=ux2=u+εv
u,v
(σ12σ12+ερσ1σ2σ12+ερσ1σ2σ12+2ερσ1σ2+ε2σ22σ2)
σ12,σ22,ρ

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ąć:

λ=12(σ22ε2σ24ε4+4σ23ρσ1ε3+8σ22ρ2σ12ε2+8σ2ρσ13ε+4σ14+2σ2ρσ1ε+2σ12)
ε
λσ22ε2(1ρ2)/2

Wykonuję symulacje realizacji macierzy danych, obliczam wartości własne symulowanej macierzy kowariancji i otrzymuję błędy .λ j e j = λ - λ jj=1,,mλ^jej=λλ^j

Aksakal
źródło
4
Tak, ale tutaj OP pyta o SVD vs EIG zastosowane zarówno do macierzy kowariancji.
ameba mówi Przywróć Monikę
1
@amoeba, wyjaśniłem związek SVD i PCA
Aksakal
To dobra odpowiedź. Chciałbym jednak wspomnieć, że svd nie może wykryć ujemnych wartości własnych, gdy takie istnieją, a ty chcesz je zobaczyć (jeśli macierz kowariancji nie jest oryginalna, ale jest, powiedzmy, wygładzona lub oszacowana w jakiś sposób lub wywnioskowana lub wynika z usunięcia parami brakujących wartości). Co więcej, eig na macierzy cov pozostaje nieco szybszy niż na svd.
ttnphns
@ttnphns, nie dodatnia określona macierz jest oczywiście
problemem
1
@FedericoPoloni, na temat arytmetyki FP i nie znając dokładnej odpowiedzi, nie zgadzam się. W tym przypadku znam odpowiedź z wystarczającą precyzją do tego zadania. Na 2x2 masz rację. Coś wymyślę.
Aksakal,
6

Użytkownikom Pythona chciałbym zauważyć, że w przypadku macierzy symetrycznych (takich jak macierz kowariancji) lepiej jest użyć numpy.linalg.eighfunkcji zamiast numpy.linalg.eigfunkcji ogólnej .

eighjest 9-10 razy szybszy niż eigna 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ą eighzamiast svd. 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.

Mosalx
źródło
+1. Kilka informacji na temat eighvs eig: mail.scipy.org/pipermail/numpy-discussion/2006-March/…
amoeba mówi Przywróć Monikę
2

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 nmnmn

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: wprowadź opis zdjęcia tutaj

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.

Gburowaty
źródło
To nie odpowiada na pytanie dotyczące EIG macierzy kowariantu vs. SVD macierzy kowariancji .
ameba mówi Przywróć Monikę
1
Jego pytanie na końcu, wyróżnione pogrubioną czcionką, brzmi: „Dlaczego robią SVD macierzy kowariancji, a nie macierzy danych?”. na które odpowiedziałem.
Gruff
Zmienię zdanie wstępne, aby było jasne, że odpowiadałem na tę część pytania PO. Rozumiem, że to może być mylące. Dzięki.
Gruff
Jeśli spróbujesz SVD na matrycy milion na tysiąc w Matlabie, domyślnie wystąpi błąd. W takich przypadkach dobrą praktyką numeryczną jest stosowanie cienkiego SVD. To znacznie poprawi rozmiar i wydajność pamięci.
Federico Poloni