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 k
Ich würde vermutlich einen neuen Satz von Matrizen erstellen: was macht man dann?
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?
quelle
Antworten:
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.
quelle
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 yich j x y ich j x y
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 alsDas 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:ich k uich j k vj k ∑ uich binvj m
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!
quelle
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.A = U× s × V U V
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.ich j ich U j
quelle
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
,libFM
oderredsvd
.vowpal wabbit
verfü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):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:
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 wabbit
weiterhin 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 wabbit
nach einer ReiheN
latenter 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--lrq
Option nur der erste Buchstabe in jedem Namensraum verwendet wird .<N>
:N=14
unten ist die Anzahl der latenten Faktoren, die wir finden möchten-f model_filename
: Schreiben Sie das endgültige Modell inmodel_filename
Ein einfacher vollständiger Trainingsbefehl wäre also:
Sobald wir die
ratings.model
Modelldatei haben, können wir sie verwenden, um zusätzliche Bewertungen für einen neuen Datensatz vorherzusagenmore_ratings.vw
:Die Vorhersagen werden in die Datei geschrieben
more_ratings.predicted
.Unter Verwendung
demo/movielens
desvowpalwabbit
Quellbaums erhalte ich nach dem Training mit 1 Million Benutzer- / Filmbewertungenml-1m.ratings.train.vw
mit 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-Setml-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 wabbit
Quellbaum von github:--rank
Option--lrq
OptionAnmerkungen:
movielens
Demo verwendet mehrere Optionen I ( der Einfachheit halber) weggelassen aus meinem Beispiel: insbesondere--loss_function quantile
,--adaptive
und--invariant
--lrq
Implementierungvw
ist wesentlich schneller als--rank
insbesondere 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 implementiertquelle
Ich würde sagen, dass der Name
SVD
irreführend ist. Tatsächlich verwendet dieSVD
Methode im Empfehlungssystem die SVD-Faktorisierung nicht direkt. Stattdessen wird der stochastische Gradientenabstieg verwendet, um die Verzerrungen und Faktorvektoren zu trainieren.Einzelheiten zu
SVD
und zu denSVD++
Algorithmen für das Empfehlungssystem finden Sie in den Abschnitten5.3.1
und5.3.2
im BuchFrancesco 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.quelle