Matrixfaktorisierung

Die Matrixfaktorisierung ist ein einfaches Einbettungsmodell. In Anbetracht der Feedbackmatrix A \(\in R^{m \times n}\), wobei \(m\) für die Anzahl der Nutzer (oder Suchanfragen) und \(n\) ist die Anzahl der Elemente, lernt das Modell:

• Eine Nutzereinbettungsmatrix \(U \in \mathbb R^{m \times d}\), Dabei ist Zeile i die Einbettung für Nutzer i.
• eine Elementeinbettungsmatrix \(V \in \mathbb R^{n \times d}\) Dabei ist Zeile j die Einbettung für Element j.

Die Einbettungen werden so erlernt, dass das Produkt \(U V^T\) ein eine gute Annäherung an die Feedbackmatrix A. Beachten Sie, dass die \((i, j)\) Eintrag von \(U . V^T\) ist einfach das Punktprodukt \(\langle U_i, V_j\rangle\) von Einbettungen des Nutzers \(i\) und das Element \(j\), das sich in der Nähe von \(A_{i, j}\)befinden soll.

Hinweis: Die Matrixfaktorisierung liefert in der Regel eine kompaktere Darstellung als um die Matrix zu lernen. Die vollständige Matrix enthält \(O(nm)\) Einträge, während die Einbettungsmatrizen \(U, \ V\) haben \(O((n+m)d)\) Einträge, wobei die Einbettungsgröße \(d\) ist normalerweise viel kleiner als \(m\) und \(n\). Daher wird bei der Matrixfaktorisierung die latente Struktur in unter der Annahme, dass die Beobachtungen nahe an einem niedrigdimensionalen Unterraum liegen. Im vorhergehenden Beispiel sind die Werte von n, m und d so niedrig, dass der Vorteil ist vernachlässigbar. In realen Empfehlungssystemen Matrixfaktorisierung kann wesentlich kompakter sein als das Lernen Matrix erstellen.

Zielfunktion auswählen

Eine intuitive Zielfunktion ist die quadrierte Entfernung. Gehen Sie dazu wie folgt vor: Minimieren Sie die Summe der quadratischen Fehler über 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.\]

In dieser Zielfunktion addieren Sie nur beobachtete Paare (i, j), also über Werte ungleich null in der Feedback-Matrix. Es kann jedoch nur die Summe ist keine gute Idee – eine Matrix aus allen Einsen einen minimalen Verlust zu reduzieren und ein Modell zu erstellen, das keine effektiven Empfehlungen und das verallgemeinert nur schlecht.

Vielleicht könnten Sie die unbeobachteten Werte als Null behandeln und Einträge in der Matrix. Dies entspricht der Minimierung der im Quadrat: Frobenius Abstand zwischen \(A\) und seiner 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 lösen, indem Sie Singular Value Decomposition (SVD) der Matrix. Sie können jedoch SVD ist auch keine gute Lösung, da in echten Anwendungen Matrix \(A\) ist möglicherweise sehr spärlich. Denken Sie zum Beispiel an alle Videos, auf YouTube verglichen mit allen Videos, die ein bestimmter Nutzer angesehen hat. Die Lösung \(UV^T\) (entspricht der Näherung des Modells) der Eingabematrix) wahrscheinlich nahe bei null liegen, was zu einer schlechten Generalisierungsleistung.

Im Gegensatz dazu zerlegt die gewichtete Matrixfaktorisierung das Ziel. die folgenden beiden Summen:

• 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.\]

Hier ist \(w_0\) ein Hyperparameter,der die beiden Begriffe damit das Ziel nicht von einem der beiden Faktoren dominiert wird. Die Feinabstimmung dieses Hyperparameters ist sehr wichtig.

Hinweis: In der Praxis müssen Sie auch die beobachteten Werte die Paare vorsichtig. z. B. häufig verwendete Artikel (z. B. extrem beliebte YouTube-Videos) oder häufige Suchanfragen (z. B. starke Nutzer) können die Zielfunktion dominieren. Sie können diesen Effekt korrigieren, indem Sie Trainingsbeispiele für die Gewichtung zur Berücksichtigung der Artikelhäufigkeit. Mit anderen Worten: können Sie die Zielfunktion durch Folgendes 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 von Abfrage i und Element j.

Zielfunktion minimieren

Gängige Algorithmen zur Minimierung der Zielfunktion sind:

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

• Weighted Alternating Least Squares (WALS) ist darauf spezialisiert, bestimmte Zielsetzung erreicht.

Die Zielsetzung ist in jeder der beiden Matrizen U und V quadratisch. (Hinweis: Allerdings ist das Problem nicht gemeinsam konvex.) WALS funktioniert nach der Initialisierung die Einbettungen nach dem Zufallsprinzip und wechseln dann zwischen:

• Problembehebung \(U\) und Problemlösung für \(V\).
• Problembehebung \(V\) und Problemlösung für \(U\).

Jede Phase lässt sich mithilfe eines linearen Systems genau lösen verteilt werden kann. Diese Technik konvergiert garantiert, da jeder Schritt reduziert den Verlust garantiert.

SGD im Vergleich zu WALS

SGD und WALS haben Vor- und Nachteile. In den folgenden Informationen finden Sie einen Vergleich:

SGD

Sehr flexibel – kann andere Verluste nutzen Funktionen.

Kann parallelisiert werden.

Langsamer – konvergiert nicht so schnell.

Es ist schwieriger, unbeobachtete Einträge zu handhaben, negative Stichproben oder die Schwerkraft verwenden.

WALS

Nur auf Loss Squares basieren.

Kann parallelisiert werden.

Konvergiert schneller als SGD

Einfachere Handhabung unbeobachteter Einträge.