Matrix Factorization

Die Matrixfaktorisierung ist ein einfaches Einbettungsmodell. Basierend auf der Feedbackmatrix A \(\in R^{m \times n}\), wobei \(m\) die Anzahl der Nutzer (oder Abfragen) und \(n\) die Anzahl der Elemente ist, lernt das Modell:

• Eine Nutzereinbettmatrix \(U \in \mathbb R^{m \times d}\), wobei Zeile i die Einbettung für Nutzer i ist.
• Eine Matrix für die Einbettung von Elementen \(V \in \mathbb R^{n \times d}\), wobei Zeile j die Einbettung für Element j ist.

Die Einbettungen werden so lernt, dass sich das Produkt \(U V^T\) als gute Annäherung an die Feedbackmatrix A eignet. Der\((i, j)\) Eintrag von \(U . V^T\) ist einfach das Punktprodukt\(\langle U_i, V_j\rangle\) der Einbettungen von Nutzer \(i\)und Artikel \(j\), die sich in der Nähe von \(A_{i, j}\)befinden sollten.

Hinweis: Die Matrixfaktorisierung ist in der Regel kompakter als das vollständige Lernen. Die vollständige Matrix enthält \(O(nm)\) Einträge, während die Einbettungsmatrizen \(U, \ V\) Einträge \(O((n+m)d)\) haben. Die Einbettungsdimension \(d\) ist normalerweise viel kleiner als \(m\)und \(n\). Daher findet die Matrixfaktorisierung eine latente Struktur in den Daten, unter der Annahme, dass Beobachtungen nahe an einem niedrigdimensionalen Unterraum liegen. Im vorherigen Beispiel sind die Werte von n, m und d so niedrig, dass der Vorteil vernachlässigbar ist. In der Praxis sind die Matrixfaktorisierungen jedoch wesentlich kompakter als das vollständige Lernen der Matrix.

Zielfunktion auswählen

Eine intuitive Zielfunktion ist der quadratische Abstand. Minimieren Sie dazu die Summe der quadratischen Fehler für alle Paare beobachteter Einträge:

\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \sum_{(i, j) \in \text{obs}} (A_{ij} - \langle U_{i}, V_{j} \rangle)^2.\]

Bei dieser Zielfunktion addieren Sie nur die beobachteten Paare (i, j), also über Werte ungleich null in der Feedbackmatrix. Es ist jedoch keine gute Idee, nur die Werte eines Faktors zusammenzufassen. Eine Matrix all dieser Werte hätte nur einen minimalen Verlust und liefert ein Modell, das keine effektiven Empfehlungen geben und sich verschlechtern lässt.

Vielleicht könnten Sie die unbeobachteten Werte als Null behandeln und alle Einträge in der Matrix addieren. Dies entspricht der Minimierung der quadratischen Frobenius-Entfernung zwischen \(A\) und dessen Näherung \(U V^T\):

\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \|A - U V^T\|_F^2.\]

Sie können dieses quadratische Problem durch die Singularwertzerlegung (SVD) der Matrix lösen. SVD ist jedoch auch keine gute Lösung, da die Matrix in echten Anwendungen unter Umständen sehr dünnbesetzt ist. \(A\) Vergleiche beispielsweise die Videos auf YouTube mit denen eines bestimmten Nutzers. Die Lösung \(UV^T\) (die der Annäherung der Eingabematrix des Modells entspricht) liegt wahrscheinlich nahe an null, was zu einer schlechten Generalisierungsleistung führt.

Im Gegensatz dazu wird bei der gewichteten Matrixfaktorisierung das Ziel in die folgenden zwei Summen aufgeteilt:

• Eine Summe der beobachteten Einträge.
• Eine Summe aus nicht beobachteten Einträgen (als Nullen behandelt)

\[\min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \sum_{(i, j) \in \text{obs}} (A_{ij} - \langle U_{i}, V_{j} \rangle)^2 + w_0 \sum_{(i, j) \not \in \text{obs}} (\langle U_i, V_j\rangle)^2.\]

In diesem Beispiel ist \(w_0\) ein Hyperparameter, der die beiden Begriffe gewichtet, sodass das Ziel nicht von einem der beiden Begriffe dominiert wird. Es ist sehr wichtig, diesen Hyperparameter abzustimmen.

Hinweis:In der Praxis müssen Sie die beobachteten Paare außerdem sorgfältig gewichten. So können z. B. häufige Elemente (z. B. sehr beliebte YouTube-Videos) oder häufige Abfragen (z. B. umfangreiche Nutzer) die Zielfunktion dominieren. Sie können diesen Effekt korrigieren, indem Sie Trainingsbeispiele gewichten, um die Elementhäufigkeit zu berücksichtigen. Sie können die Zielfunktion also so ersetzen:

\[\sum_{(i, j) \in \text{obs}} w_{i, j} (A_{i, j} - \langle U_i, V_j \rangle)^2 + w_0 \sum_{i, j \not \in \text{obs}} \langle U_i, V_j \rangle^2\]

Dabei ist \(w_{i, j}\) eine Funktion der Häufigkeit der Suchanfrage i und von Element j.

Zielfunktion minimieren

Gängige Algorithmen zur Minimierung der Zielfunktion:

• Der stochastische Gradientenabstieg (SGD) ist eine allgemeine Methode zur Minimierung von Verlustfunktionen.

• Gewichtete alternierende kleinste Quadrate (WALS) sind auf dieses spezielle Ziel ausgerichtet.

Das Ziel ist in jeder der beiden Matrizen U und V quadratisch. Das Problem ist jedoch nicht gemeinsam konvex. WALS initialisiert die Einbettungen nach dem Zufallsprinzip und wechselt dann zwischen folgenden Komponenten:

• Probleme \(U\) beheben und beheben \(V\)
• Probleme \(V\) beheben und beheben \(U\)

Jede Phase kann genau gelöst werden (über die Lösung eines linearen Systems) und verteilt werden. Diese Methode wird garantiert konvergiert, da jeder Schritt garantiert den Verlust reduziert.

SGD vs. WALS

SGD und WALS haben Vor- und Nachteile. Im Folgenden finden Sie einen Vergleich der beiden Optionen:

SGD

Sehr flexibel – kann andere Verlustfunktionen verwenden

Kann parallelisiert werden.

Langsamer, konvergiert nicht so schnell.

Harter Umgang mit unbeobachteten Einträgen (Verwendung negativer Stichproben oder Schwerkraft)

WALS

Verlassen Sie sich nur auf Verlustplätze.

Kann parallelisiert werden.

Konvergent schneller als SGD

Einfachere Handhabung nicht beobachteter Einträge.