Mein Name ist Pavel Parkhomenko, ich bin ML-Entwickler. In diesem Artikel möchte ich über die Struktur des Yandex.Zen-Dienstes sprechen und technische Verbesserungen vorstellen, deren Umsetzung es ermöglicht hat, die Qualität der Empfehlungen zu steigern. In diesem Beitrag erfahren Sie, wie Sie in wenigen Millisekunden aus Millionen von Dokumenten die für den Benutzer relevantesten finden. Wie führt man eine kontinuierliche Zerlegung einer großen Matrix (bestehend aus Millionen von Spalten und Dutzenden von Millionen Zeilen) durch, sodass neue Dokumente ihren Vektor in Dutzenden von Minuten erhalten? wie man die Benutzer-Artikel-Matrixzerlegung wiederverwendet, um eine gute Vektordarstellung für Videos zu erhalten.
Unsere Empfehlungsdatenbank enthält Millionen von Dokumenten unterschiedlicher Formate: Textartikel, die auf unserer Plattform erstellt und von externen Websites übernommen wurden, Videos, Erzählungen und kurze Beiträge. Die Entwicklung eines solchen Dienstes ist mit einer Vielzahl technischer Herausforderungen verbunden. Hier sind einige davon:
- Teilen Sie die Rechenaufgaben auf: Führen Sie alle schweren Operationen offline aus und führen Sie in Echtzeit nur schnelle Anwendungen von Modellen durch, um 100–200 ms zu verantworten.
- Berücksichtigen Sie Benutzeraktionen schnell. Dazu ist es notwendig, dass alle Ereignisse sofort an den Empfehlungsgeber übermittelt werden und die Ergebnisse der Modelle beeinflussen.
- Gestalten Sie den Feed so, dass er sich bei neuen Benutzern schnell an deren Verhalten anpasst. Personen, die dem System gerade erst beigetreten sind, sollten das Gefühl haben, dass ihr Feedback Einfluss auf die Empfehlungen hat.
- Verstehen Sie schnell, wem Sie einen neuen Artikel empfehlen können.
- Reagieren Sie schnell auf das ständige Auftauchen neuer Inhalte. Täglich werden Zehntausende Artikel veröffentlicht, von denen viele nur eine begrenzte Lebensdauer haben (z. B. Nachrichten). Das unterscheidet sie von Filmen, Musik und anderen langlebigen und kostspieligen Inhalten.
- Übertragen Sie Wissen von einem Domänenbereich auf einen anderen. Wenn ein Empfehlungssystem über trainierte Modelle für Textartikel verfügt und wir Videos hinzufügen, können wir die vorhandenen Modelle wiederverwenden, sodass der neue Inhaltstyp besser rankt.
Ich werde Ihnen sagen, wie wir diese Probleme gelöst haben.
Auswahl der Kandidaten
Wie lässt sich die Anzahl der betrachteten Dokumente in wenigen Millisekunden um das Tausendfache reduzieren, ohne dass sich die Qualität des Rankings verschlechtert?
Angenommen, wir haben viele ML-Modelle trainiert, darauf basierende Funktionen generiert und ein weiteres Modell trainiert, das Dokumente für den Benutzer einordnet. Alles wäre in Ordnung, aber Sie können nicht einfach alle Zeichen für alle Dokumente in Echtzeit erfassen und berechnen, wenn es Millionen dieser Dokumente gibt und Empfehlungen in 100 bis 200 ms erstellt werden müssen. Die Aufgabe besteht darin, aus Millionen eine bestimmte Teilmenge auszuwählen, die für den Benutzer gerankt wird. Diese Phase wird üblicherweise als Kandidatenauswahl bezeichnet. Dafür gibt es mehrere Voraussetzungen. Erstens muss die Auswahl sehr schnell erfolgen, damit möglichst viel Zeit für das Ranking selbst bleibt. Zweitens müssen wir, nachdem wir die Anzahl der Dokumente für das Ranking stark reduziert haben, die für den Benutzer relevanten Dokumente so vollständig wie möglich erhalten.
Unser Prinzip der Kandidatenauswahl hat sich weiterentwickelt und ist mittlerweile zu einem mehrstufigen Schema gelangt:
Zunächst werden alle Dokumente in Gruppen eingeteilt und aus jeder Gruppe werden die beliebtesten Dokumente entnommen. Gruppen können Websites, Themen oder Cluster sein. Für jeden Benutzer werden anhand seiner Historie die ihm am nächsten stehenden Gruppen ausgewählt und daraus die besten Dokumente entnommen. Wir verwenden auch den kNN-Index, um in Echtzeit Dokumente auszuwählen, die dem Benutzer am nächsten sind. Es gibt mehrere Methoden zum Erstellen eines kNN-Index; unsere hat am besten funktioniert (Hierarchische navigierbare Small-World-Graphen). Hierbei handelt es sich um ein hierarchisches Modell, mit dem Sie in wenigen Millisekunden aus einer Millionendatenbank die N nächstgelegenen Vektoren für einen Benutzer finden können. Wir indizieren zunächst unsere gesamte Dokumentendatenbank offline. Da die Suche im Index recht schnell funktioniert, können Sie bei mehreren starken Einbettungen mehrere Indizes erstellen (einen Index für jede Einbettung) und auf jeden davon in Echtzeit zugreifen.
Wir haben immer noch Zehntausende Dokumente für jeden Benutzer. Das ist immer noch viel, um alle Funktionen zu zählen, daher verwenden wir in dieser Phase das Light-Ranking – ein leichtes, schweres Ranking-Modell mit weniger Features. Die Aufgabe besteht darin, vorherzusagen, welche Dokumente ein schweres Modell oben haben wird. Dokumente mit dem höchsten Prädiktor werden im schweren Modell verwendet, d. h. in der letzten Rangfolgestufe. Dieser Ansatz ermöglicht es Ihnen, die Datenbank der für den Benutzer berücksichtigten Dokumente innerhalb von zehn Millisekunden von Millionen auf Tausende zu reduzieren.
ALS-Schritt zur Laufzeit
Wie kann das Nutzer-Feedback unmittelbar nach einem Klick berücksichtigt werden?
Ein wichtiger Faktor bei Empfehlungen ist die Reaktionszeit auf Benutzerfeedback. Dies ist besonders wichtig für neue Benutzer: Wenn eine Person gerade erst mit der Nutzung des Empfehlungssystems beginnt, erhält sie einen nicht personalisierten Feed mit Dokumenten zu verschiedenen Themen. Sobald er den ersten Klick macht, müssen Sie dies sofort berücksichtigen und sich an seine Interessen anpassen. Wenn Sie alle Faktoren offline berechnen, ist eine schnelle Reaktion des Systems aufgrund der Verzögerung unmöglich. Daher ist es notwendig, Benutzeraktionen in Echtzeit zu verarbeiten. Für diese Zwecke verwenden wir den ALS-Schritt zur Laufzeit, um eine Vektordarstellung des Benutzers zu erstellen.
Nehmen wir an, wir haben für alle Dokumente eine Vektordarstellung. Beispielsweise können wir mithilfe von ELMo, BERT oder anderen maschinellen Lernmodellen Einbettungen offline basierend auf dem Text eines Artikels erstellen. Wie können wir basierend auf ihren Interaktionen im System eine Vektordarstellung der Benutzer im selben Raum erhalten?
Allgemeines Prinzip der Bildung und Zerlegung der BenutzerdokumentmatrixLassen Sie uns m Benutzer und n Dokumente haben. Für einige Benutzer ist ihre Beziehung zu bestimmten Dokumenten bekannt. Dann können diese Informationen als MXN-Matrix dargestellt werden: Zeilen entsprechen Benutzern und Spalten entsprechen Dokumenten. Da die Person die meisten Dokumente nicht gesehen hat, bleiben die meisten Matrixzellen leer, während andere gefüllt werden. Für jedes Ereignis (Gefällt mir, Gefällt mir nicht, Klick) wird in der Matrix ein Wert angegeben. Betrachten wir jedoch ein vereinfachtes Modell, in dem „Gefällt mir“ 1 und „Gefällt mir nicht“ -1 entspricht.
Zerlegen wir die Matrix in zwei Teile: P (mxd) und Q (dxn), wobei d die Dimension der Vektordarstellung ist (normalerweise eine kleine Zahl). Dann entspricht jedes Objekt einem d-dimensionalen Vektor (für einen Benutzer – eine Zeile in der Matrix P, für ein Dokument – eine Spalte in der Matrix Q). Diese Vektoren sind die Einbettungen der entsprechenden Objekte. Um vorherzusagen, ob einem Benutzer ein Dokument gefallen wird, können Sie einfach seine Einbettungen multiplizieren.
Eine der möglichen Methoden zur Zerlegung einer Matrix ist ALS (Alternating Least Squares). Wir werden die folgende Verlustfunktion optimieren:
Hier ist rui die Interaktion des Benutzers u mit dem Dokument i, qi ist der Vektor des Dokuments i, pu ist der Vektor des Benutzers u.
Anschließend wird der optimale Benutzervektor aus Sicht des mittleren quadratischen Fehlers (für feste Dokumentvektoren) analytisch durch Lösen der entsprechenden linearen Regression gefunden.
Dies wird als „ALS-Schritt“ bezeichnet. Und der ALS-Algorithmus selbst besteht darin, dass wir abwechselnd eine der Matrizen (Benutzer und Artikel) korrigieren und die andere aktualisieren, um die optimale Lösung zu finden.
Glücklicherweise ist das Finden der Vektordarstellung des Benutzers ein ziemlich schneller Vorgang, der zur Laufzeit mithilfe von Vektoranweisungen durchgeführt werden kann. Mit diesem Trick können Sie das Feedback der Nutzer sofort im Ranking berücksichtigen. Die gleiche Einbettung kann im kNN-Index verwendet werden, um die Kandidatenauswahl zu verbessern.
Verteilte kollaborative Filterung
Wie führt man eine inkrementelle verteilte Matrixfaktorisierung durch und findet schnell Vektordarstellungen neuer Artikel?
Inhalte sind nicht die einzige Quelle für Empfehlungssignale. Eine weitere wichtige Quelle sind kollaborative Informationen. Gute Ranking-Merkmale können traditionell aus der Zerlegung der Benutzer-Dokument-Matrix gewonnen werden. Bei dem Versuch, eine solche Zerlegung durchzuführen, stießen wir jedoch auf Probleme:
1. Wir haben Millionen von Dokumenten und zig Millionen Benutzer. Die Matrix passt nicht vollständig auf eine Maschine und die Zerlegung wird sehr lange dauern.
2. Die meisten Inhalte im System haben eine kurze Lebensdauer: Dokumente bleiben nur wenige Stunden relevant. Daher ist es notwendig, ihre Vektordarstellung so schnell wie möglich zu erstellen.
3. Wenn Sie eine Zerlegung unmittelbar nach der Veröffentlichung des Dokuments erstellen, haben nicht genügend Benutzer Zeit, es auszuwerten. Daher wird seine Vektordarstellung höchstwahrscheinlich nicht sehr gut sein.
4. Wenn einem Benutzer etwas gefällt oder nicht gefällt, können wir dies bei der Zerlegung nicht sofort berücksichtigen.
Um diese Probleme zu lösen, haben wir eine verteilte Zerlegung der Benutzerdokumentmatrix mit häufigen inkrementellen Aktualisierungen implementiert. Wie genau funktioniert es?
Angenommen, wir haben einen Cluster von N Maschinen (N liegt im Hunderterbereich) und wir möchten auf ihnen eine verteilte Zerlegung einer Matrix durchführen, die nicht auf eine Maschine passt. Die Frage ist, wie diese Zerlegung durchgeführt werden kann, damit einerseits genügend Daten auf jeder Maschine vorhanden sind und andererseits die Berechnungen unabhängig sind.
Wir werden den oben beschriebenen ALS-Zerlegungsalgorithmus verwenden. Schauen wir uns an, wie ein ALS-Schritt verteilt ausgeführt wird – die restlichen Schritte werden ähnlich sein. Nehmen wir an, wir haben eine feste Matrix von Dokumenten und möchten eine Matrix von Benutzern erstellen. Dazu teilen wir es zeilenweise in N Teile auf, wobei jeder Teil ungefähr die gleiche Anzahl Zeilen enthält. Wir senden an jede Maschine nicht leere Zellen der entsprechenden Zeilen sowie die Matrix der Dokumenteinbettungen (vollständig). Da seine Größe nicht sehr groß ist und die Benutzerdokumentmatrix normalerweise sehr spärlich ist, passen diese Daten auf einen normalen Computer.
Dieser Trick kann über mehrere Epochen hinweg wiederholt werden, bis das Modell konvergiert, wobei die feste Matrix eine nach der anderen wechselt. Aber selbst dann kann die Matrixzerlegung mehrere Stunden dauern. Und das löst nicht das Problem, dass Sie schnell Einbettungen neuer Dokumente erhalten und die Einbettungen derjenigen aktualisieren müssen, über die beim Erstellen des Modells nur wenige Informationen vorlagen.
Die Einführung schneller inkrementeller Modellaktualisierungen hat uns geholfen. Nehmen wir an, wir haben ein aktuell trainiertes Modell. Seit ihrer Schulung gab es neue Artikel, mit denen unsere Benutzer interagiert haben, aber auch Artikel, die während der Schulung wenig Interaktion hatten. Um die Einbettungen solcher Artikel schnell zu erhalten, verwenden wir die Benutzereinbettungen, die wir während des ersten großen Trainings des Modells erhalten haben, und führen einen ALS-Schritt durch, um die Dokumentmatrix bei gegebener fester Benutzermatrix zu berechnen. Auf diese Weise können Sie Einbettungen recht schnell erhalten – innerhalb weniger Minuten nach der Veröffentlichung des Dokuments – und häufig die Einbettungen aktueller Dokumente aktualisieren.
Damit Empfehlungen unmittelbar menschliche Handlungen berücksichtigen, verwenden wir zur Laufzeit keine offline erhaltenen Benutzereinbettungen. Stattdessen führen wir einen ALS-Schritt durch und erhalten den tatsächlichen Benutzervektor.
Transfer in einen anderen Domainbereich
Wie kann ich Benutzerfeedback zu Textartikeln nutzen, um eine Vektordarstellung eines Videos zu erstellen?
Da wir zunächst nur Textartikel empfohlen haben, sind viele unserer Algorithmen auf diese Art von Inhalten zugeschnitten. Beim Hinzufügen anderer Arten von Inhalten standen wir jedoch vor der Notwendigkeit, die Modelle anzupassen. Wie haben wir dieses Problem anhand eines Videobeispiels gelöst? Eine Möglichkeit besteht darin, alle Modelle von Grund auf neu zu trainieren. Dies dauert jedoch lange und einige der Algorithmen stellen hohe Anforderungen an die Größe der Trainingsstichprobe, die für einen neuen Inhaltstyp in den ersten Momenten seines Lebens im Dienst noch nicht in der erforderlichen Menge verfügbar ist.
Wir sind den umgekehrten Weg gegangen und haben die Textmodelle für das Video wiederverwendet. Der gleiche ALS-Trick hat uns dabei geholfen, Vektordarstellungen von Videos zu erstellen. Wir haben eine Vektordarstellung von Benutzern basierend auf Textartikeln erstellt und einen ALS-Schritt unter Verwendung von Videoansichtsinformationen durchgeführt. So haben wir ganz einfach eine Vektordarstellung des Videos erhalten. Und zur Laufzeit berechnen wir einfach die Nähe zwischen dem aus Textartikeln gewonnenen Benutzervektor und dem Videovektor.
Abschluss
Die Entwicklung des Kerns eines Echtzeit-Empfehlungssystems bringt viele Herausforderungen mit sich. Sie müssen Daten schnell verarbeiten und ML-Methoden anwenden, um diese Daten effektiv zu nutzen. Erstellen Sie komplexe verteilte Systeme, die in der Lage sind, Benutzersignale und neue Inhaltseinheiten in kürzester Zeit zu verarbeiten. und viele andere Aufgaben.
Im aktuellen System, dessen Aufbau ich beschrieben habe, wächst die Qualität der Empfehlungen für den Nutzer mit seiner Aktivität und Verweildauer im Dienst. Aber hier liegt natürlich die Hauptschwierigkeit: Es ist für das System schwierig, die Interessen einer Person, die kaum mit den Inhalten interagiert, sofort zu verstehen. Die Verbesserung der Empfehlungen für neue Benutzer ist unser Hauptziel. Wir werden die Algorithmen weiter optimieren, sodass für eine Person relevante Inhalte schneller in ihren Feed gelangen und irrelevante Inhalte nicht angezeigt werden.
Source: habr.com