Jak obliczyć SVD ogromnej rzadkiej macierzy?

26

Jaki jest najlepszy sposób obliczenia dekompozycji wartości pojedynczej (SVD) bardzo dużej macierzy dodatniej (65 M x 3,4 M), w której dane są bardzo rzadkie?

Mniej niż 0,1% matrycy jest niezerowe. Potrzebuję sposobu, który:

  • zmieści się w pamięci (wiem, że istnieją metody online)
  • zostaną obliczone w rozsądnym czasie: 3,4 dni
  • będą wystarczająco dokładne, jednak dokładność nie jest moim głównym zmartwieniem i chciałbym móc kontrolować, ile zasobów w to włożę.

Byłoby wspaniale mieć bibliotekę Haskell, Python, C # itp., Która ją implementuje. Nie używam mathlaba ani R, ale w razie potrzeby mogę użyć R.

svd numerics Sonia
źródło
3
Ile masz pamięci? 0,1% z 65 mln * 3,4 mln to wciąż niezerowe wartości 221e9. Jeśli używasz 4 bajtów na wartość, to wciąż więcej niż 55 GB przy założeniu braku obciążenia, więc rzadkość nadal nie rozwiązuje problemu ... Czy musisz załadować cały zestaw na raz?
Bitwise
Powinienem był być bardziej precyzyjny. Nie więcej niż 250-500 MB z 32-bitową liczbą całkowitą. Prawdopodobnie znacznie mniej, ale wymiar jest problemem, jak go rozumiem. Mam maszynę 16 GB.
Sonia
Co powiesz na to? quora.com/…
Bitwise
Ta strona prowadzi do biblioteki Pythona, która implementuje „szybki, przyrostowy algorytm SVD o małej pamięci i dużej matrycy”: en.wikipedia.org/wiki/Latent_semantic_analysis
Bitwise
Zobacz także stats.stackexchange.com/questions/2806 .
ameba mówi Przywróć Monikę

Odpowiedzi:

21

Jeśli pasuje do pamięci, zbuduj rzadką macierz w R za pomocą pakietu Matrix i wypróbuj irlba dla SVD. Możesz określić, ile pojedynczych wektorów chcesz w wyniku, co jest innym sposobem ograniczenia obliczeń.

To dość duża matryca, ale w przeszłości miałem bardzo dobre wyniki z tą metodą. irlbajest najnowocześniejszy. Wykorzystuje domyślnie zrestartowany algorytm bi-diagonalizacji Lanczosa .

Może przeszukiwać zestaw danych nagród Netflix (480 189 wierszy przez 17 770 kolumn, 100 480 507 niezerowych wpisów) w milisekundach. Twój zestaw danych jest ~ 200 000 razy większy niż zestaw danych Netflix, więc zajmuje to znacznie więcej czasu. Rozsądne może być oczekiwanie, że obliczenia te zostaną wykonane w ciągu kilku dni.

Zach
źródło
matryca danych pasuje do pamięci, czy irlba poradzi sobie z rozkładem również w sposób efektywny pod względem pamięci?
Sonia
@Sonia: irlba jest bardzo wydajna pod względem pamięci: oblicza przybliżone rozwiązanie, można ograniczyć liczbę pojedynczych wektorów i została zaprojektowana do pracy na rzadkich macierzach. O ile mi wiadomo, jest to tak szybkie, jak to możliwe do obliczania częściowych SVD.
Zach
@Sonia: Powodzenia!
Zach
Wypróbowałem pamięć ... Przed uruchomieniem obliczę formę bloku trójkąta.
Sonia,
@Sonia, czy masz to zapisane jako rzadkie Matrix? Spróbuj ograniczyć liczbę wyliczanych pojedynczych wartości ... może po prostu spojrzeć na 10 najlepszych?
Zach.