Różnica między implementacjami PCA i TruncatedSVD w scikit-learn

12

Rozumiem związek między analizą głównych składników a rozkładem wartości osobliwych na poziomie algebraicznym / dokładnym. Moje pytanie dotyczy implementacji scikit-learn .

Dokumentacja mówi: „ [TruncatedSVD] jest bardzo podobny do PCA, ale działa bezpośrednio na przykładowe wektory, zamiast na macierz kowariancji. ”, Co odzwierciedlałoby różnicę algebraiczną między obydwoma podejściami. Jednak później mówi: „ Ten estymator [TruncatedSVD] obsługuje dwa algorytmy: szybki randomizowany solver SVD i„ naiwny ”algorytm, który wykorzystuje ARPACK jako eigensolver na (X * XT) lub (XT * X), ​​w zależności od tego, co jest bardziej wydajny. ”. W odniesieniu do PCA, mówi: „Liniowa redukcja wymiarów za pomocą dekompozycji danych w liczbie pojedynczej w celu jej projekcji ...”. A implementacja PCA obsługuje te same dwa algorytmy (randomizowane i ARPACK) oraz jeden inny, LAPACK. Patrząc na kod, widzę, że zarówno ARPACK, jak i LAPACK w PCA i TruncatedSVD robią svd na przykładowych danych X, ARPACK jest w stanie poradzić sobie z rzadkimi macierzami (używając svds).

Oprócz różnych atrybutów i metod, a PCA może dodatkowo dokonać dokładnego pełnego rozkładu pojedynczej wartości za pomocą LAPACK, PCA i TruncatedSVD implementacje scikit-learning wydają się być dokładnie tym samym algorytmem. Pierwsze pytanie: czy to prawda?

Drugie pytanie: mimo że LAPACK i ARPACK używają scipy.linalg.svd (X) i scipy.linalg.svds (X), będąc macierzą próbki X, obliczają rozkład wartości pojedynczej lub rozkład własny lub wewnętrznie. Podczas gdy „losowy” solver nie musi obliczać produktu. (Jest to istotne w związku ze stabilnością liczbową, patrz Dlaczego PCA danych za pomocą SVD danych? ). Czy to jest poprawne?XTXXXT

Odpowiedni kod: linia PCA 415. Skrócona linia SVD 137.

kaczor
źródło
1
czy możesz dodać link do kodu
seanv507 10.10.16
1
drake - Myślę, że zgadzam się z tobą w pierwszym Q. nie rozumiem drugiego. co masz na myśli: „obliczają one rozkład wartości osobliwych lub rozkład własny XT ∗ XXT ∗ X lub X ∗ XTX ∗ XT wewnętrznie” - właśnie pokazałeś kod, w którym wszystko to jest zrobione przy użyciu SVD na X? - problemy numeryczne odnoszą się do pierwszej obliczeniowej macierzy kowariancji (nazwij ją C), a następnie znalezienia wektorów własnych C
seanv507
@ seanv507 chodzi 2. pytanie - Chyba że scipy.linalg.svd (X) oblicza SVD wykonując eigen-rozkład i / lub . To samo dotyczy linalg.svds (X). Cytując: „szybki randomizowany solver SVD i„ naiwny ”algorytm, który wykorzystuje ARPACK jako eigensolver w (X * XT) lub (XT * X)”. Zobacz także ostatni wiersz w docs.scipy.org/doc/scipy/reference/generated/… . Jedyny sposób, w jaki rozumiem pierwszy cytat, to to, że algorytm losowy jest jedynym, który nie oblicza macierzy kowariancji / gramówXTXXXT
drake
1
Sądzę, że podejście ARPACK ma coś wspólnego z iteracją Arnoldiego , więc ma do czynienia tylko z produktami macierz-wektor. (Zasadniczo tego rodzaju metody iteracyjne nie zawierają nawet jawnego , tylko parę procedur i . Jest to typowe na przykład dla dużych rzadkich macierzy w XXtimes()Xt_times()
solverach
@ GeoMatt22 Czy możesz rozwinąć swój komentarz? Czy masz na myśli, że podejścia ARPACK lub LAPACK nie cierpią z powodu niestabilności numerycznej, ponieważ nie muszą obliczać macierzy kowariancji?
drake

Odpowiedzi:

13

Implementacje scikit-uczenia PCA i TruncatedSVD wydają się być dokładnie tym samym algorytmem.

Nie: PCA jest (obcięty) SVD na wyśrodkowanych danych (według średniej odejmowania według funkcji). Jeśli dane są już wyśrodkowane, te dwie klasy zrobią to samo.

W praktyce TruncatedSVDjest przydatny w przypadku dużych rzadkich zestawów danych, których nie można wyśrodkować bez gwałtownego wybuchu użycia pamięci.

  • numpy.linalg.svdi scipy.linalg.svdoba polegają na LAPACK _GESDD opisanym tutaj: http://www.netlib.org/lapack/lug/node32.html (sterownik dzielenia i zdobywania)

  • scipy.sparse.linalg.svdspolega na ARPACK do wykonania rozkładu wartości własnej XT. X lub X. XT (w zależności od kształtu danych) za pomocą metody iteracyjnej Arnoldi. Podręcznik użytkownika ARPACK w HTML ma niepoprawne formatowanie, które ukrywa szczegóły obliczeniowe, ale iteracja Arnoldi jest dobrze opisana na wikipedii: https://en.wikipedia.org/wiki/Arnoldi_iteration

Oto kod SVD opartego na ARPACK w scipy:

https://github.com/scipy/scipy/blob/master/scipy/sparse/linalg/eigen/arpack/arpack.py#L1642 (wyszukaj ciąg „def svds” w przypadku zmiany wiersza w kodzie źródłowym ).

ogrisel
źródło
2
Jeden może skutecznie obsługiwać rzadkie dane (TruncatedSVD), drugi nie może (PCA). Dlatego mamy 2 klasy.
ogrisel
1
Jeśli to jest powód, nazwałbym je SVD i SparseSVD (lub podobnym), aby uniknąć zamieszania.
drake
2
Ale ludzie chcą PCA i mogą nie wiedzieć, że PCA to tylko SVD na danych ześrodkowanych.
ogrisel
5
@drake Nie zgadzam się, że „procedury są różne (PCA używa macierzy kowariancji, a SVD używa macierzy danych)”. PCA to nazwa rodzaju analizy. Można do tego użyć różnych algorytmów i implementacji. EIG macierzy cov to jedna metoda, SVD ześrodkowanej macierzy danych to inna metoda, a następnie EIG i SVD można również wykonać różnymi metodami. Nie ma znaczenia - wszystko to PCA.
ameba
1
@amoeba Dziękujemy za wyjaśnienie / korektę terminologii. To, co mówisz, ma dla mnie więcej sensu, biorąc pod uwagę, że SVD i EIG są algebraicznymi twierdzeniami / metodami o szerszym zakresie niż PCA
drake