Wie verwende ich die SVD bei der kollaborativen Filterung?

30

Ich bin ein bisschen verwirrt darüber, wie die SVD bei der kollaborativen Filterung verwendet wird. Angenommen, ich habe ein soziales Diagramm und erstelle aus den Kanten eine Adjazenzmatrix. Dann nehme ich eine SVD (vergessen wir die Regularisierung, Lernraten, Sparsity-Optimierungen usw.). Wie verwende ich diese SVD, um meine Empfehlungen zu verbessern?

Angenommen, mein soziales Diagramm entspricht instagram, und ich wurde mit der Verantwortung beauftragt, Benutzern im Dienst nur auf der Grundlage des sozialen Diagramms zu empfehlen. Ich würde zuerst eine Adjazenzmatrix erstellen , die SVD nehmen, , die ersten Eigenwerte auswählen , und was dann? ( m × m ) A = U s V kEIN (m×m)EIN=UsVk

Ich würde vermutlich einen neuen Satz von Matrizen erstellen: was macht man dann?

Unewm×ksnewk×kVnewk×m

Ich habe im Internet nachgesehen, und die meisten Links konzentrieren sich auf die Berechnung der SVD, aber niemand sagt Ihnen, was Sie damit tun sollen. Also was soll ich tun?

Vishal
quelle
1
Dies könnte Ihre Frage beantworten: datascience.stackexchange.com/a/16523
avli

Antworten:

7

Allerdings: Bei reiner Vanille-SVD können Sie Probleme haben, die ursprüngliche Matrix wiederherzustellen, geschweige denn, Werte für fehlende Elemente vorherzusagen. Die nützliche Faustregel in diesem Bereich besteht darin, die durchschnittliche Bewertung pro Film zu berechnen und diesen Durchschnitt für jede Benutzer- / Filmkombination zu subtrahieren, dh die Filmverzerrung von jedem Benutzer zu subtrahieren. Dann wird empfohlen, SVD auszuführen, und natürlich müssten Sie diese Bias-Werte irgendwo aufzeichnen, um Bewertungen neu zu erstellen oder für unbekannte Werte Vorhersagen zu treffen. Ich würde Simon Funk 'Beitrag über SVD lesen, um Empfehlungen zu erhalten - er hat während des Netflix-Wettbewerbs einen inkrementellen SVD-Ansatz erfunden.

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

Ich denke, Matrix A vor SVD zu erniedrigen, macht Sinn, da SVDs enger Cousin PCA auch auf ähnliche Weise funktioniert. In Bezug auf die inkrementelle Berechnung hat Funk mir mitgeteilt, dass die erste Gradientenrichtung den Rest der Berechnung dominiert, wenn Sie sie nicht herabsetzen. Ich habe dies aus erster Hand gesehen, im Grunde ohne erniedrigende Dinge funktionieren nicht.

BBDynSys
quelle
24

Ich möchte eine abweichende Meinung äußern:

Fehlende Kanten als fehlende Werte

Bei einem kollaborativen Filterproblem werden die nicht vorhandenen Verbindungen (Benutzer hat Element nicht bewertet , Person hat Person nicht befreundet ) im Allgemeinen als fehlende vorherzusagende Werte und nicht als Nullen behandelt. Das heißt, wenn der Benutzer das Element nicht bewertet hat , möchten wir raten, was er bewerten könnte, wenn er es bewertet hätte. Wenn Person nicht friended hat , wollen wir erraten , wie wahrscheinlich ist es , dass er würde wollen ihn Freund. Die Empfehlungen basieren auf den rekonstruierten Werten.j x y i j x yichjxyichjxy

Wenn Sie die SVD des sozialen Graphen nehmen (z. B. durchstecken svd()), geben Sie praktisch Nullen an allen fehlenden Stellen an. Dass dies problematisch ist, wird im Setup für die Bewertung von Benutzerelementen für die kollaborative Filterung deutlicher. Wenn ich die fehlenden Einträge zuverlässig ausfüllen könnte, müsste ich SVD überhaupt nicht verwenden. Ich würde nur Empfehlungen basierend auf den ausgefüllten Einträgen geben. Wenn ich keine Möglichkeit dazu habe, sollte ich sie nicht füllen, bevor ich die SVD mache. *

SVD mit fehlenden Werten

Natürlich svd()weiß die Funktion nicht, wie sie mit fehlenden Werten umgehen soll. Also, was genau sollst du tun? Nun, es gibt eine Möglichkeit , das Problem umzubenennen als

"Finde die Matrix mit Rang die der ursprünglichen Matrix am nächsten kommt"k

Das ist wirklich das Problem, das Sie zu lösen versuchen, und Sie werden es nicht verwenden svd(), um es zu lösen. Ein Weg, der für mich (in Bezug auf die Netflix-Preisdaten) funktioniert hat, war:

  • Versuchen Sie, die Einträge mit einem einfachen Modell zu versehen, z. B. . Das macht eigentlich einen guten Job.X^ich,j=μ+αich+βj

  • Weisen Sie jeden Benutzer ein -vector und jedes Element a -vector . (In Ihrem Fall erhält jede Person einen rechten und einen linken Vektor). werden Sie die Residuen als Punktprodukte vorhersagen:ichkuichjkvjkuichmvjm

  • Verwenden Sie einen Algorithmus, um die Vektoren zu finden, die den Abstand zur ursprünglichen Matrix minimieren. Verwenden Sie zum Beispiel dieses Papier

Viel Glück!

*: Tenali empfiehlt grundsätzlich die nächsten Nachbarn. Sie versuchen, Benutzer zu finden, die ähnlich sind, und geben Empfehlungen dazu. Leider macht es das Sparsity-Problem (~ 99% der Matrix haben keine Werte) schwierig, die nächsten Nachbarn mithilfe des Kosinusabstands oder der Jaccard-Ähnlichkeit oder was auch immer zu finden. Daher empfiehlt er, eine SVD der Matrix (mit Nullen, die bei den fehlenden Werten unterstellt werden) durchzuführen, um Benutzer zunächst in einen kleineren Funktionsbereich zu komprimieren und dann dort Vergleiche durchzuführen. SVD-Nächsten-Nachbarn zu machen ist in Ordnung, aber ich würde trotzdem empfehlen, die SVD richtig zu machen (ich meine ... meinen Weg). Keine unsinnige Wertanrechnung nötig!

Stumpy Joe Pete
quelle
Dies war eigentlich die Antwort, nach der ich gesucht hatte und die ich hören wollte :) Vielen Dank!
Vishal
Seltsamerweise stellte sich die Frage: "Ich habe im Internet nachgesehen und die meisten Links konzentrieren sich auf die Berechnung der SVD, aber niemand sagt Ihnen, was Sie damit tun sollen. Also, was soll ich tun?" oder im Titel steht: "Wie verwende ich die SVD bei der kollaborativen Filterung?"
TenaliRaman
Ja, und meine Antwort fasste zusammen, wie ich es bei der kollaborativen Filterung verwende.
Stumpy Joe Pete
1
+1, so wie ich es verstehe, berechnen Sie die niedrigrangige Matrix nicht mit SVD, sondern mit einer iterativen Methode, um den quadratischen Fehler zu minimieren, oder? Wenn ich jedoch SVD verwenden möchte, sollte ich die fehlenden Einträge mit einigen Werten ausfüllen, bevor ich die Matrixfaktorisierung durchführe, oder?
Avocado
1
Wenn sie also sagen, dass sie svd verwendet haben, heißt das nicht, für die zu verwenden? Der Grund, warum sie svd sagen, ist, dass das Ergebnis oder die Grundidee hinter dieser iterativen Lösung svd ähnelt? svd()
Avocado
14

Der Grund, warum dir niemand sagt, was du damit machen sollst, ist, dass, wenn du weißt, was SVD macht, es ein bisschen offensichtlich ist, was du damit machen sollst :-).

Da Ihre Zeilen und Spalten dieselbe Menge sind, erkläre ich dies anhand einer anderen Matrix A. Die Matrix A sei so, dass die Zeilen die Benutzer und die Spalten die Elemente sind, die dem Benutzer gefallen. Beachten Sie, dass diese Matrix nicht symmetrisch sein muss, aber in Ihrem Fall stellt sich heraus, dass sie symmetrisch ist. Eine Möglichkeit, sich SVD vorzustellen, ist folgende: SVD findet einen verborgenen Merkmalsbereich, in dem die Benutzer und Elemente, die sie mögen, Merkmalsvektoren haben, die eng ausgerichtet sind.

Wenn wir also berechnen, stellt die Matrix die Merkmalsvektoren dar, die den Benutzern im verborgenen Merkmalsraum entsprechen, und die Matrix stellt die Merkmalsvektoren dar, die den Elementen im verborgenen Merkmalsraum entsprechen.EIN=U×s×VUV

Nun, wenn ich Ihnen zwei Vektoren aus dem gleichen Merkmalsraum gebe und Sie fragen, ob sie ähnlich sind, was ist das Einfachste, was Sie sich vorstellen können, um dies zu erreichen? Skalarprodukt.

Wenn ich also sehen möchte, dass der Benutzer Artikel mag , muss ich nur das Skalarprodukt aus dem ten Eintrag in und dem ten Eintrag in V nehmen. Natürlich ist das Skalarprodukt keineswegs das Einzige, was Sie tun gelten kann, ist jedes Ähnlichkeitsmaß anwendbar, das Sie sich vorstellen können.ichjichUj

TenaliRaman
quelle
Zwei Fragen: 1) Füllen Sie fehlende Werte mit Null (Element j nicht von Benutzer i überprüft), bevor Sie SVD ausführen? 2) Wie wird berechnet, ob einem neuen Benutzer Artikel j gefällt?
B_Miner
1
@B_Miner Hallo, entschuldige die verspätete Antwort. Die Antworten: 1) Ja, normalerweise füllen wir die fehlenden Werte mit Null, bevor Sie SVD ausführen. Normalerweise empfehle ich jedoch, es mit einer Bewertung ungleich Null zu füllen. Beispielsweise können Sie die fehlenden Werte mit der durchschnittlichen Bewertung füllen, die der Benutzer bisher abgegeben hat. 2) Der SVD-basierte Ansatz gilt nur für bekannte Benutzer und bekannte Elemente. Es kann keine neuen Benutzer oder neue Elemente verarbeiten. Und wie kann es sein, wenn ein neuer User reinkommt, wir wissen in diesem Framework nichts über ihn vorherzusagen.
TenaliRaman
1
@B_Miner Wenn Sie mit neuen Benutzern / Elementen arbeiten möchten, müssen wir davon ausgehen, dass wir Zugriff auf einige Benutzer- und Elementfunktionen haben. Dann können Sie ein komplexeres Modell wie PDLF (Predictive Discrete Latent Factor Model) verwenden. Auf diese Weise können Sie neue Benutzer / Elemente bearbeiten, da dies mit einem bekannten Funktionsbereich funktioniert.
TenaliRaman
@TenaliRaman Ich bin mir nicht sicher, ob du das siehst, aber es geht los. Daher habe ich Themenmodelle (Topic Models, LDA) verwendet, um Funktionen für Benutzer (im wahrsten Sinne des Wortes Benutzer) basierend auf den von ihnen gelesenen Dokumenten zu erstellen. Ich mittle nur die Topic-Vektoren, um einen "User-Topic-Vektor" zu erhalten. Ich möchte etwas Ähnliches mit SVD (oder möglicherweise ALS) machen. Angenommen, ich berechne SVD mit bekannten Benutzerelementdaten und habe dann neue Benutzer, die mehrere bekannte Elemente "besuchen". In diesem Fall sind die Artikelvektoren bekannt, aber die Benutzervektoren sind unbekannt. Kann ich die Artikelvektoren zur Berechnung des Benutzervektors verwenden oder muss ich die SVD erneut mit allen Daten berechnen?
thecity2
tolle antwort tenali. Sehr hilfreich für das Verständnis des Konzepts
Nihal
3

Hiermit soll versucht werden, den Teil der Frage zu beantworten, der sich an diejenigen richtet, die Sparse-SVD-Empfehlungen praktisch umsetzen oder den Quellcode auf Details überprüfen möchten. Sie können eine handelsübliche FOSS-Software verwenden, um dünn besetzte SVDs zu modellieren. Zum Beispiel vowpal wabbit, libFModer redsvd.

vowpal wabbitverfügt über 3 Implementierungen von "SVD-ähnlichen" Algorithmen (jeweils mit einer von 3 Befehlszeilenoptionen auswählbar). Streng genommen sollten diese als "ungefähre, iterative Matrixfaktorisierung" und nicht als reine "klassische" SVD bezeichnet werden, sie sind jedoch eng mit der SVD verwandt Nullen) Matrix.

Hier ist ein komplettes, funktionierendes Rezept für die Umsetzung von Filmempfehlungen im Netflix-Stil mit der für mich am besten geeigneten Option vowpal wabbit"low-ranked quadratic" ( --lrq):

Datei im Datensatzformat ratings.vw(jede Bewertung in einer Zeile nach Benutzer und Film):

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

Dabei ist die erste Zahl die Bewertung (1 bis 5 Sterne), gefolgt von der ID des bewerteten Benutzers und der Film-ID, die bewertet wurde.

Die Testdaten haben dasselbe Format, können jedoch (optional) die Bewertungsspalte weglassen:

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

Optional, weil wir zum Bewerten / Testen von Vorhersagen Bewertungen benötigen, mit denen die Vorhersagen verglichen werden können. Wenn wir die Bewertungen weglassen, werden die Bewertungen vowpal wabbitweiterhin vorhergesagt, können aber den Vorhersagefehler nicht abschätzen (vorhergesagte Werte im Vergleich zu tatsächlichen Werten in den Daten).

Zum Trainieren fragen wir vowpal wabbitnach einer Reihe Nlatenter Interaktionsfaktoren zwischen Benutzern und Filmen, die sie mögen (oder nicht mögen). Sie können sich das so vorstellen, dass Sie allgemeine Themen suchen, bei denen ähnliche Benutzer eine Teilmenge von Filmen auf ähnliche Weise bewerten, und anhand dieser allgemeinen Themen vorhersagen, wie ein Benutzer einen Film bewerten würde, den er noch nicht bewertet hat.

vw Optionen und Argumente, die wir verwenden müssen:

  • --lrq <x><y><N> findet "niedrigrangige quadratische" latente Faktoren.
  • <x><y>: "um" bedeutet, dass die Namensräume "users" und "m" im Datensatz gekreuzt werden. Beachten Sie, dass bei der --lrqOption nur der erste Buchstabe in jedem Namensraum verwendet wird .
  • <N>: N=14unten ist die Anzahl der latenten Faktoren, die wir finden möchten
  • -f model_filename: Schreiben Sie das endgültige Modell in model_filename

Ein einfacher vollständiger Trainingsbefehl wäre also:

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

Sobald wir die ratings.modelModelldatei haben, können wir sie verwenden, um zusätzliche Bewertungen für einen neuen Datensatz vorherzusagen more_ratings.vw:

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

Die Vorhersagen werden in die Datei geschrieben more_ratings.predicted.

Unter Verwendung demo/movielensdes vowpalwabbitQuellbaums erhalte ich nach dem Training mit 1 Million Benutzer- / Filmbewertungen ml-1m.ratings.train.vwmit 14 Latentfaktoren (was bedeutet, dass die mittlere SVD-Matrix eine Matrix mit 14 × 14 Zeilen × Spalten ist) und dem Testen auf der unabhängigen Basis ~ 0,693 MAE (mittlerer absoluter Fehler) Test-Set ml-1m.ratings.test.vw. Wie gut ist 0,69 MAE? Für den gesamten Bereich möglicher Vorhersagen, einschließlich des Falls ohne Bewertung (0) [0 bis 5], beträgt ein Fehler von 0,69 ~ 13,8% (0,69 / 5,0) des gesamten Bereichs, dh ungefähr 86,2% Genauigkeit (1 - 0,138).

Beispiele und eine vollständige Demo für einen ähnlichen Datensatz (movielens) mit Dokumentation finden Sie im vowpal wabbitQuellbaum von github:

Anmerkungen:

  • Die movielensDemo verwendet mehrere Optionen I ( der Einfachheit halber) weggelassen aus meinem Beispiel: insbesondere --loss_function quantile, --adaptiveund--invariant
  • Die --lrqImplementierung vwist wesentlich schneller als --rankinsbesondere beim Speichern und Laden der Modelle.

Credits:

  • --rank Die vw-Option wurde von Jake Hofman implementiert
  • --lrq Die Option vw (mit optionalem Dropout) wurde von Paul Minero implementiert
  • vowpal wabbit (alias vw) ist das Gehirnkind von John Langford
Arielf
quelle
1

Ich würde sagen, dass der Name SVDirreführend ist. Tatsächlich verwendet die SVDMethode im Empfehlungssystem die SVD-Faktorisierung nicht direkt. Stattdessen wird der stochastische Gradientenabstieg verwendet, um die Verzerrungen und Faktorvektoren zu trainieren.

Einzelheiten zu SVDund zu den SVD++Algorithmen für das Empfehlungssystem finden Sie in den Abschnitten 5.3.1und 5.3.2im Buch Francesco Ricci, Lior Rokach, Bracha Shapira, and Paul B. Kantor. Recommender Systems Handbook. 1st edition, 2010.

In Python gibt es ein etabliertes Paket, das diese Algorithmen namens implementiert surprise. In ihrer Dokumentation erwähnen sie auch die Details dieser Algorithmen.

lenhhoxung
quelle