Jak korzystać z SVD w filtrowaniu grupowym?

30

Jestem trochę zdezorientowany tym, w jaki sposób SVD jest używane do wspólnego filtrowania. Załóżmy, że mam wykres społecznościowy i buduję macierz przylegania z krawędzi, a następnie biorę SVD (zapomnijmy o regularyzacji, wskaźnikach uczenia się, optymalizacjach sparityzacji itp.), W jaki sposób użyć tego SVD, aby poprawić moje rekomendacje?

Załóżmy, że mój wykres społecznościowy odpowiada instagramowi, a ja miałem za zadanie polecać użytkowników w serwisie wyłącznie na podstawie wykresu społecznościowego. Ja najpierw budować przylegania matrycy , trochę SVD, , wybrać pierwsze wartości własnych, to co? $\mathbf A$ $(m\times m)$ $\mathbf A = \mathbf{U s V}$ $k$

Prawdopodobnie stworzyłbym nowy zestaw macierzy: to co robi?

\begin{aligned} U_{n e w} & \sim m \times k \\ s_{n e w} & \sim k \times k \\ V_{n e w} & \sim k \times m \end{aligned}

$\begin{align} \mathbf U_{new} &\sim m\times k \\ \mathbf s_{new} &\sim k\times k \\ \mathbf V_{new} &\sim k\times m \end{align}$

Szukałem w Internecie i większość linków koncentruje się na obliczaniu SVD, ale nikt nie mówi, co z tym zrobić. Więc co powinienem zrobić?

svd recommender-system

— Vishal
źródło

1

To może odpowiedzieć na twoje pytanie: datascience.stackexchange.com/a/16523

— avli

7

Jednak: W przypadku czystego waniliowego SVD możesz mieć problemy z odtworzeniem oryginalnej matrycy, nie mówiąc już o przewidywaniu wartości brakujących elementów. Przydatną ogólną zasadą w tym obszarze jest obliczanie średniej oceny na film i odejmowanie tej średniej dla każdej kombinacji użytkownik / film, to znaczy odejmowanie stronniczości filmu od każdego użytkownika. Następnie zaleca się uruchomienie SVD i oczywiście trzeba gdzieś zapisać te wartości odchylenia, aby odtworzyć oceny lub przewidzieć nieznane wartości. Przeczytałem post Simona Funka na SVD w celu uzyskania rekomendacji - wynalazł on przyrostowe podejście SVD podczas zawodów Netflix.

http://sifter.org/~simon/journal/20061211.html

Wydaje mi się, że poniżająca macierz A przed SVD ma sens, ponieważ bliski kuzyn SVD PCA również działa w podobny sposób. Jeśli chodzi o obliczenia przyrostowe, Funk powiedział mi, że jeśli nie poniżasz, pierwszy kierunek gradientu dominuje nad resztą obliczeń. Widziałem to z pierwszej ręki, w zasadzie bez poniżających rzeczy nie działają.

— BBDynSys
źródło

24

Chciałbym przedstawić zdanie odrębne:

Brakujące krawędzie jako brakujące wartości

W przypadku problemu z filtrowaniem grupowym połączenia, które nie istnieją (użytkownik nie ocenił elementu , osoba nie zaprzyjaźniła się z osobą ) są zwykle traktowane jako brakujące wartości, które należy przewidzieć, a nie jako zera. Oznacza to, że jeśli użytkownik nie ocenił artykuł chcemy odgadnąć, co on może ją ocenić, gdyby nie ocenił go. Jeśli osoba nie friended , chcemy zgadywać, jakie jest prawdopodobieństwo, że on chce , aby mu przyjaciela. Zalecenia oparte są na zrekonstruowanych wartościach. $i$ $j$ $x$ $y$ $i$ $j$ $x$ $y$

Kiedy weźmiesz SVD z wykresu społecznościowego (np. Przełączysz go svd()), w zasadzie przypisujesz zerom wszystkie brakujące miejsca. To, że jest to problematyczne, jest bardziej oczywiste w konfiguracji oceniania pozycji użytkownika dla wspólnego filtrowania. Gdybym miał sposób na niezawodne uzupełnienie brakujących wpisów, w ogóle nie musiałbym używać SVD. Po prostu dawałbym rekomendacje na podstawie wypełnionych wpisów. Jeśli nie mam na to sposobu, nie powinienem ich wypełniać przed wykonaniem SVD. *

SVD z brakującymi wartościami

Oczywiście svd()funkcja nie wie, jak poradzić sobie z brakującymi wartościami. Co dokładnie powinieneś zrobić? Cóż, istnieje sposób na przeformułowanie problemu jako

„Znajdź macierz rangi , która jest najbliższa oryginalnej matrycy” $k$

To jest naprawdę problem, który próbujesz rozwiązać i nie zamierzasz go użyć svd(). Sposób, który zadziałał dla mnie (w przypadku danych nagród Netflix) był następujący:

Spróbuj dopasować wpisy do prostego modelu, np. . To naprawdę dobra robota. $\hat{X}_{i,j} = \mu + \alpha_i + \beta_j$
Przypisać każdemu użytkownikowi do -wektor i każda pozycja -wektor . (W twoim przypadku każda osoba dostaje prawy i lewy wektor ). Ostatecznie będziesz przewidywał resztki jako produkty kropkowe: $i$ $k$ $u_i$ $j$ $k$ $v_j$ $k$ $\sum u_{im}v_{jm}$
Użyj algorytmu, aby znaleźć wektory, które minimalizują odległość do oryginalnej macierzy. Na przykład użyj tego papieru

Powodzenia!

_{*: Tenali zaleca w zasadzie najbliższych sąsiadów. Próbujesz znaleźć użytkowników, którzy są do siebie podobni, i wydaje ci zalecenia. Niestety problem rzadkości (około 99% macierzy nie ma wartości) utrudnia znalezienie najbliższych sąsiadów przy użyciu podobieństwa cosinusowego lub podobieństwa jaccard lub cokolwiek innego. Dlatego zaleca wykonanie SVD macierzy (z zerami przypisanymi do brakujących wartości), aby najpierw skompresować użytkowników do mniejszej przestrzeni funkcji, a następnie dokonać porównań. Wykonywanie SVD najbliższych sąsiadów jest w porządku, ale nadal zalecałbym wykonanie SVD we właściwy sposób (mam na myśli ... mój sposób). Nie trzeba bezsensownego przypisywania wartości!}

— Kikut Joe Pete
źródło

To była odpowiedź, której szukałem i chciałem usłyszeć :) Dziękuję bardzo!

— Vishal,

Dziwne pytanie brzmiało: „Szukałem w Internecie, a większość linków koncentruje się na obliczaniu SVD, ale nikt nie mówi ci, co z tym zrobić. Więc co mam zrobić?” lub w tej kwestii tytuł mówi: „Jak korzystać z SVD we wspólnym filtrowaniu?”

— TenaliRaman,

Tak, a moja odpowiedź podsumowała, w jaki sposób używam go do wspólnego filtrowania.

— Stumpy Joe Pete,

1

+1, jak rozumiem, nie obliczasz macierzy niskiej rangi za pomocą SVD, ale iteracyjną metodę minimalizowania błędu kwadratu, prawda? Jeśli jednak chcę użyć SVD, powinienem uzupełnić brakujące wpisy pewnymi wartościami przed faktoryzacją macierzy, prawda?

— awokado

1

Więc kiedy powiedzieli, że użyli svd, nie mieli na myśli użycia do faktoryzacji macierzy? Powodem, dla którego mówią svd, jest to, że wynik lub podstawowa idea tego iteracyjnego rozwiązania przypomina svd?

s v d ()

$svd()$

— awokado

14

Powodem, dla którego nikt nie mówi, co z tym zrobić, jest to, że jeśli wiesz, co robi SVD, to jest trochę oczywiste, co z tym zrobić :-).

Ponieważ wiersze i kolumny są tego samego zestawu, wyjaśnię to za pomocą innej macierzy A. Niech macierz A będzie taka, że wiersze są użytkownikami, a kolumny to elementy, które użytkownik lubi. Zauważ, że ta matryca nie musi być symetryczna, ale w twoim przypadku wydaje się, że jest symetryczna. Jednym ze sposobów myślenia o SVD jest: SVD znajduje ukrytą przestrzeń cech, w której użytkownicy i elementy, które lubią, mają wektory cech, które są ściśle dopasowane.

Kiedy więc obliczamy , macierz reprezentuje wektory cech odpowiadające użytkownikom w ukrytej przestrzeni cech, a macierz reprezentuje wektory cech odpowiadające elementom w ukrytej przestrzeni cech. $A = U \times s \times V$ $U$ $V$

Otóż, jeśli dam wam dwa wektory z tej samej przestrzeni cech i poproszę o sprawdzenie, czy są one podobne, jaka jest najprostsza rzecz, którą można wymyślić, aby to osiągnąć? Produkt kropkowy.

Tak więc, jeśli chcę zobaczyć użytkownikowi lubi pozycję , wszystko muszę zrobić, to wziąć iloczyn skalarny z th wpisu i th wpisu V. Oczywiście, kropka produkt nie jest bynajmniej jedyną rzeczą, którą można zastosować, zastosowanie może mieć każdy podobieństwo, o którym myślisz. $i$ $j$ $i$ $U$ $j$

— TenaliRaman
źródło

Dwa pytania: 1) Czy uzupełniasz brakujące wartości zerami (pozycja j nie została sprawdzona przez użytkownika i) przed uruchomieniem SVD? 2) Jak obliczyć, czy nowy użytkownik polubi pozycję j?

— B_Miner

1

@B_Miner Cześć, przepraszam za opóźnioną odpowiedź. Odpowiedzi: 1) Tak, zazwyczaj wypełniamy brakujące wartości zerami przed uruchomieniem SVD. Zazwyczaj jednak zalecam wypełnienie go niezerową oceną - na przykład możesz uzupełnić brakujące wartości średnią oceną, którą dotychczas wystawił użytkownik. 2) Podejście oparte na SVD dotyczy tylko znanych użytkowników i znanych elementów. Nie obsługuje nowych użytkowników ani nowych elementów. I jak to możliwe, jeśli nowy użytkownik wejdzie, nie wiemy nic o nim w tych ramach do przewidzenia.

— TenaliRaman,

1

@B_Miner Jeśli chcesz pracować z nowymi użytkownikami / przedmiotami, musimy założyć, że mamy dostęp do niektórych funkcji użytkownika i funkcji przedmiotów. Następnie możesz użyć bardziej wyrafinowanego modelu, takiego jak PDLF (Predictive Discrete Latent Factor model). Umożliwi to obsługę nowych użytkowników / elementów, ponieważ działa ze znaną przestrzenią funkcji.

— TenaliRaman,

@TenaliRaman Nie jestem pewien, czy to zobaczysz, ale proszę bardzo. Użyłem więc modeli tematycznych (LDA) do tworzenia funkcji dla użytkowników (dosłownie użytkowników) na podstawie przeczytanych dokumentów. Po prostu uśredniam wektory tematyczne, aby uzyskać „wektor tematu użytkownika”. Chcę zrobić coś podobnego z SVD (ewentualnie ALS). Powiedzmy, że obliczam SVD przy użyciu znanych danych pozycji użytkownika, a następnie mam nowych użytkowników, którzy „odwiedzają” kilka znanych pozycji. W tym przypadku wektory przedmiotów są znane, ale wektory użytkownika są nieznane. Czy mogę użyć wektorów pozycji do obliczenia wektora użytkownika, czy też muszę ponownie obliczyć SVD przy użyciu wszystkich danych?

— thecity2

świetna odpowiedź tenali. bardzo pomocne dla zrozumienia koncepcji

— Nihal

3

Ma to na celu odpowiedzieć na pytanie „jak to zrobić” dla tych, którzy chcą praktycznie wdrożyć rzadkie zalecenia SVD lub sprawdzić kod źródłowy w celu uzyskania szczegółowych informacji. Do modelowania sparse-SVD można użyć gotowego oprogramowania FOSS. Na przykład vowpal wabbit, libFMalbo redsvd.

vowpal wabbitma 3 implementacje algorytmów „podobnych do SVD” (każdy do wyboru za pomocą jednej z 3 opcji wiersza poleceń). Ściśle mówiąc, należy je nazwać „przybliżonym, iteracyjnym rozkładem macierzy”, a nie czystym „klasycznym” SVD ", ale są one ściśle powiązane z SVD. Można je traktować jako bardzo wydajne obliczeniowo przybliżone rozkładanie SVD rzadkiego (głównie zera) macierz.

Oto pełny, działający przepis na robienie rekomendacji filmowych w stylu Netflix z vowpal wabbitjego --lrqopcją „niskiej pozycji kwadratowej” ( ), która wydaje mi się najlepsza dla mnie:

Plik formatu zestawu danych ratings.vw(każda ocena w jednym wierszu według użytkownika i filmu):

5 |user 1 |movie 37
3 |user 2 |movie 1019
4 |user 1 |movie 25
1 |user 3 |movie 238
...

Gdzie 1. liczba to ocena (od 1 do 5 gwiazdek), po której następuje identyfikator użytkownika, który ocenił oraz identyfikator filmu, który został oceniony.

Dane testowe mają ten sam format, ale mogą (opcjonalnie) pominąć kolumnę ocen:

 |user 1 |movie 234
 |user 12 |movie 1019
...

opcjonalnie, ponieważ do oceny / testowania prognoz potrzebujemy ocen, aby porównać prognozy. Jeśli pominiemy oceny, vowpal wabbitnadal będziemy przewidywać oceny, ale nie będziemy w stanie oszacować błędu prognozowania (wartości prognozowane vs. wartości rzeczywiste w danych).

Aby trenować, prosimy vowpal wabbito znalezienie zestawu Nukrytych czynników interakcji między użytkownikami a filmami, które lubią (lub nie lubią). Możesz myśleć o tym jako o znajdowaniu wspólnych tematów, w których podobni użytkownicy oceniają podzbiór filmów w podobny sposób i używaniu tych wspólnych motywów, aby przewidzieć, jak użytkownik oceni film, którego jeszcze nie ocenił.

vw opcje i argumenty, których musimy użyć:

--lrq <x><y><N> znajduje „ukryte kwadratowe” czynniki utajone.
<x><y>: „um” oznacza krzyżyk u [ser] i m [ovie] przestrzeni nazw w zbiorze danych. Zauważ, że z pierwszą --lrqopcją używana jest tylko pierwsza litera w każdej przestrzeni nazw .
<N>: N=14poniżej znajduje się liczba ukrytych czynników, które chcemy znaleźć
-f model_filename: napisz ostateczny model do model_filename

Tak więc proste polecenie pełnego szkolenia byłoby:

    vw --lrq um14 -d ratings.vw -f ratings.model

Po uzyskaniu ratings.modelpliku modelu możemy go wykorzystać do przewidywania dodatkowych ocen dla nowego zestawu danych more_ratings.vw:

    vw -i ratings.model -d more_ratings.vw -p more_ratings.predicted

Prognozy zostaną zapisane do pliku more_ratings.predicted.

Korzystając demo/movielensz vowpalwabbitdrzewa źródłowego, otrzymuję ~ 0,693 MAE (średni błąd bezwzględny) po przeszkoleniu 1 miliona ocen użytkowników / filmów ml-1m.ratings.train.vwz 14 ukrytymi czynnikami (co oznacza, że macierz środkowa SVD ma matrycę 14 x 14 wierszy x kolumny) i testuje na niezależnym zestaw testowy ml-1m.ratings.test.vw. Jak dobra jest 0.69 MAE? Dla pełnego zakresu możliwych prognoz, w tym przypadku bez oceny (0) [0 do 5], błąd 0,69 wynosi ~ 13,8% (0,69 / 5,0) pełnego zakresu, tj. Około 86,2% dokładności (1 - 0,138).

Przykłady i pełną wersję demonstracyjną podobnego zestawu danych (movielens) z dokumentacją można znaleźć w vowpal wabbitdrzewie źródeł na github:

Uwagi:

movielensDemo wykorzystuje kilka opcji pominąłem (dla uproszczenia) z moim przykładzie: w szczególności --loss_function quantile, --adaptiveoraz--invariant
--lrqRealizacja w vwto dużo szybciej niż --rankw szczególności podczas zapisywania i wczytywania modeli.

Kredyty:

--rank Opcja vw została wdrożona przez Jake'a Hofmana
--lrq Opcja vw (z opcjonalnym rezygnacją) została zaimplementowana przez Paula Minero
wedpal wabbit (alias vw) jest dzieckiem mózgu Johna Langforda

— arielf
źródło

1

Powiedziałbym, że nazwa SVDwprowadza w błąd. W rzeczywistości SVDmetoda w systemie rekomendującym nie wykorzystuje bezpośrednio faktoryzacji SVD. Zamiast tego używa stochastycznego spadku gradientu do trenowania błędów i wektorów czynnikowych.

Szczegóły SVDi SVD++algorytmy dla systemu rekomendującego można znaleźć w rozdziałach 5.3.1i 5.3.2książce Francesco Ricci, Lior Rokach, Bracha Shapira, and Paul B. Kantor. Recommender Systems Handbook. 1st edition, 2010.

W Pythonie istnieje dobrze ugruntowany pakiet implementujący te algorytmy o nazwie surprise. W swojej dokumentacji wspominają również szczegóły tych algorytmów.

— lenhhoxung
źródło