🥇Wie wir an der Qualität und Geschwindigkeit der Empfehlungsanpassung arbeiten

Ich heiße Pavel Parkhomenko und bin ML-Entwickler. In diesem Artikel möchte ich über den Aufbau des Yandex.Zen-Dienstes sprechen und technische Verbesserungen teilen, die es ermöglicht haben, die Qualität der Empfehlungen zu steigern. Aus dem Post erfahren Sie, wie man in nur wenigen Millisekunden aus Millionen von Dokumenten die relevantesten für den Nutzer findet; wie man eine kontinuierliche Zerlegung einer großen Matrix (die aus Millionen von Spalten und Dutzenden Millionen von Zeilen besteht) durchführt, damit neue Dokumente in nur wenigen Minuten ihren Vektor erhalten; und wie man die Zerlegung der Matrix Nutzer-Artikel wiederverwendet, um eine gute vektorielle Darstellung für Videos zu erhalten.

Unsere Empfehlungsdatenbank enthält Millionen von Dokumenten verschiedener Formate: Textartikel, die auf unserer Plattform erstellt und von externen Websites entnommen wurden, Videos, Narrative und kurze Posts. Die Entwicklung eines solchen Dienstes ist mit einer Vielzahl technischer Herausforderungen verbunden. Hier sind einige davon:

Rechenaufgaben aufteilen: Alle schweren Operationen offline durchführen und in Echtzeit nur schnelle Modellanwendungen ausführen, um innerhalb von 100-200 ms zu antworten.
Die Aktionen des Nutzers schnell berücksichtigen. Dafür ist es notwendig, dass alle Ereignisse sofort an den Empfehlungsalgorithmus geliefert werden und die Ergebnisse der Modelle beeinflussen.
Der Feed sollte so gestaltet sein, dass er sich schnell an das Verhalten neuer Nutzer anpasst. Neu in das System kommende Personen sollten das Gefühl haben, dass ihr Feedback die Empfehlungen beeinflusst.
Schnell verstehen, wem eine neue Geschichte empfohlen werden sollte.
Schnell auf das ständige Erscheinen neuer Inhalte reagieren. Täglich erscheinen Zehntausende von Artikeln, von denen viele eine begrenzte Lebensdauer haben (zum Beispiel Nachrichten). Das unterscheidet sie von Filmen, Musik und sonstigem langlebigen und aufwendigen Content.
Wissen von einem Themenbereich auf einen anderen übertragen. Wenn im Empfehlungssystem trainierte Modelle für Textartikel vorhanden sind und wir Videos hinzufügen, können bestehende Modelle wiederverwendet werden, um neuen Content besser zu bewerten.

Ich werde erzählen, wie wir diese Aufgaben gelöst haben.

Auswahl von Kandidaten

Wie man in wenigen Millisekunden die Anzahl der betrachteten Dokumente um das Tausendfache reduziert, ohne die Qualität der Rangfolge wesentlich zu verschlechtern?

Nehmen wir an, wir haben viele ML-Modelle trainiert, basierend auf diesen Merkmale generiert und ein weiteres Modell trainiert, das Dokumente für den Benutzer rankt. Alles wäre gut, aber man kann nicht einfach alle Merkmale in Echtzeit für Millionen von Dokumenten berechnen und dabei Empfehlungen in 100-200 ms erstellen. Die Aufgabe besteht darin, eine bestimmte Untermenge aus Millionen auszuwählen, die für den Benutzer gerankt wird. Diese Phase nennt man in der Regel die Kandidatenauswahl. Dabei gibt es einige Anforderungen. Erstens muss die Auswahl sehr schnell erfolgen, damit für die eigentliche Rangfolge möglichst viel Zeit bleibt. Zweitens müssen wir, während wir die Anzahl der zu rankenden Dokumente stark reduzieren, alle für den Benutzer relevanten Dokumente so vollständig wie möglich erhalten.

Unser Prinzip der Kandidatenauswahl hat sich evolutionär entwickelt, und mittlerweile sind wir zu einem mehrstufigen Schema gekommen:

Zunächst werden alle Dokumente in Gruppen unterteilt, und aus jeder Gruppe werden die beliebtesten Dokumente entnommen. Gruppen können Websites, Themen oder Cluster sein. Für jeden Benutzer werden basierend auf seiner Historie die ihm am nächsten liegenden Gruppen ausgewählt, und aus diesen werden die besten Dokumente entnommen. Außerdem verwenden wir den kNN-Index, um die dem Benutzer am nächsten liegenden Dokumente in Echtzeit auszuwählen. Es gibt mehrere Methoden zur Erstellung des kNN-Index, bei uns hat am besten funktioniert HNSW (Hierarchische navigierbare kleine Weltgraphen). Dies ist ein hierarchisches Modell, das es ermöglicht, in wenigen Millisekunden die N nächsten Vektoren für den Benutzer aus einer Million großen Datenbank zu finden. Zuvor indizieren wir offline unsere gesamte Dokumentenbank. Da die Suche im Index ziemlich schnell funktioniert, kann man bei mehreren starken Embeddings mehrere Indizes erstellen (je einen Index für jedes Embedding) und in Echtzeit auf jeden von ihnen zugreifen.

Wir haben zehntausende Dokumente für jeden Benutzer. Das ist nach wie vor viel, um alle Merkmale zu zählen, daher wenden wir in diesem Schritt ein leichtes Ranking an – ein vereinfachtes Modell des schweren Rankings mit weniger Merkmalen. Die Aufgabe besteht darin, vorherzusagen, welche Dokumente in dem schweren Modell ganz oben stehen werden. Dokumente mit der höchsten Vorhersage werden im schweren Modell verwendet, also im letzten Schritt des Rankings. Dieser Ansatz ermöglicht es, die Datenbank der für den Benutzer in Betracht gezogenen Dokumente in nur wenigen Millisekunden von Millionen auf Tausende zu reduzieren.

ALS-Schritt zur Laufzeit

Wie berücksichtigt man das Feedback des Benutzers sofort nach dem Klick?

Ein wichtiger Faktor bei Empfehlungen ist die Reaktionszeit auf das Feedback des Benutzers. Dies ist besonders wichtig für neue Benutzer: Wenn jemand gerade erst beginnt, das Empfehlungssystem zu nutzen, erhält er einen unpersonalisierten Feed mit einer Vielzahl von Dokumenten zu verschiedenen Themen. Sobald er den ersten Klick macht, muss dies sofort berücksichtigt werden, um sich an seine Interessen anzupassen. Wenn alle Faktoren offline berechnet werden, wird eine schnelle Reaktion des Systems aufgrund von Verzögerungen unmöglich. Daher müssen die Aktionen des Benutzers in Echtzeit verarbeitet werden. Zu diesem Zweck verwenden wir den ALS-Schritt zur Laufzeit, um eine vektorielle Darstellung des Benutzers zu erstellen.

Angenommen, für alle Dokumente haben wir eine vektorielle Darstellung. Zum Beispiel können wir offline basierend auf dem Text des Artikels Einbettungen mit Hilfe von ELMo, BERT oder anderen Modellen des maschinellen Lernens erstellen. Wie kann man die vektorielle Darstellung der Benutzer im selben Raum basierend auf ihrer Interaktion im System erhalten?

Das allgemeine Prinzip der Bildung und Zerlegung der Benutzer-Dokument-MatrixAngenommen, wir haben m Benutzer und n Dokumente. Für einige Benutzer ist ihre Beziehung zu bestimmten Dokumenten bekannt. Dann kann diese Information in Form einer m x n-Matrix dargestellt werden: Die Zeilen entsprechen den Benutzern und die Spalten den Dokumenten. Da die meisten Dokumente von den Benutzern nicht gesehen wurden, bleiben die meisten Zellen der Matrix leer, während andere ausgefüllt sind. Für jedes Ereignis (Gefällt mir, Gefällt mir nicht, Klick) ist in der Matrix ein gewisser Wert vorgesehen – betrachten wir ein vereinfachtes Modell, in dem ein Gefällt mir 1 und ein Gefällt mir nicht –1 entspricht.

Wir zerlegen die Matrix in zwei: P (m x d) und Q (d x n), wobei d die Dimension der Vektorrepräsentation ist (gewöhnlich eine kleine Zahl). Dann entspricht jedem Objekt ein d-dimensionaler Vektor (dem Benutzer eine Zeile in der Matrix P, dem Dokument eine Spalte in der Matrix Q). Diese Vektoren sind die Embeddings der entsprechenden Objekte. Um vorherzusagen, ob einem Benutzer ein Dokument gefällt, können wir einfach ihre Embeddings multiplizieren.

Eine mögliche Methode zur Zerlegung der 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.

Dann wird der optimale Vektor des Benutzers (bei festen Dokumentvektoren) analytisch durch die Lösung der entsprechenden linearen Regression gefunden, wobei die mittlere quadrierte Abweichung minimiert wird.

Das wird als "ALS-Schritt" bezeichnet. Der Algorithmus ALS selbst besteht darin, dass wir abwechselnd eine der Matrizen (Benutzer und Artikel) fixieren und die andere aktualisieren, um die optimale Lösung zu finden.

Glücklicherweise ist das Finden der Vektorrepräsentation eines Benutzers eine relativ schnelle Operation, die zur Laufzeit unter Verwendung von Vektorbefehlen durchgeführt werden kann. Dieser Trick ermöglicht es, das Feedback des Benutzers sofort in die Rangliste einzubeziehen. Dasselbe Embedding kann auch im kNN-Index verwendet werden, um die Auswahl der Kandidaten zu verbessern.

Verteilte kollaborative Filterung

Wie kann man inkrementelle verteilte Matrixfaktorisierung durchführen und schnell die Vektorrepräsentation neuer Artikel finden?

Inhalte sind nicht die einzige Informationsquelle für Empfehlungen. Eine weitere wichtige Quelle ist die kollaborative Information. Gute Hinweise im Ranking können traditionell aus der Zerlegung der Nutzer-Dokument-Matrix gewonnen werden. Bei dem Versuch, eine solche Zerlegung durchzuführen, sind wir jedoch auf Probleme gestoßen:

1. Wir haben Millionen von Dokumenten und Dutzende Millionen von Nutzern. Die Matrix passt nicht vollständig auf eine einzelne Maschine, und die Zerlegung wird sehr lange dauern.
2. Bei den meisten Inhalten im System ist die Lebensdauer kurz: Dokumente sind nur wenige Stunden relevant. Daher ist es notwendig, so schnell wie möglich ihre Vektordarstellung zu erstellen.
3. Wenn die Zerlegung sofort nach der Veröffentlichung eines Dokuments erfolgt, haben nicht genügend Nutzer Zeit, ihre Bewertung abzugeben. Daher wird die Vektordarstellung mit großer Wahrscheinlichkeit nicht besonders gut sein.
4. Wenn ein Nutzer ein Like oder ein Dislike vergibt, können wir dies nicht sofort in die Zerlegung einbeziehen.

Um die genannten Probleme zu lösen, haben wir eine verteilte Zerlegung der Nutzer-Dokument-Matrix mit häufigen inkrementellen Updates implementiert. Wie funktioniert das genau?

Angenommen, wir haben einen Cluster von N Maschinen (N summiert sich zu Hunderten), und wir möchten eine verteilte Zerlegung der Matrix durchführen, die nicht auf eine einzelne Maschine passt. Die Frage ist, wie man diese Zerlegung so ausführt, dass einerseits genügend Daten auf jeder Maschine vorhanden sind und andererseits die Berechnungen unabhängig sind.

Wir werden den oben beschriebenen ALS-Zerlegungsalgorithmus verwenden. Lassen Sie uns betrachten, wie wir einen Schritt von ALS verteilt ausführen — die anderen Schritte werden ähnlich sein. Angenommen, wir haben die Dokumentenmatrix fixiert und möchten die Nutzermatrix erstellen. Dazu teilen wir sie in N Teile nach Zeilen auf, wobei jeder Teil ungefähr die gleiche Anzahl von Zeilen enthält. Wir senden die nicht leeren Zellen der entsprechenden Zeilen an jede Maschine sowie die Matrix der Dokumenteneinbettungen (komplett). Da diese nicht sehr groß ist und die Nutzer-Dokument-Matrix in der Regel stark spärlich ist, passen diese Daten auf eine gewöhnliche Maschine.

Dieser Trick kann über mehrere Epochen hinweg wiederholt werden, bis das Modell konvergiert, indem man abwechselnd die feste Matrix ändert. Aber selbst dann kann die Zerlegung der Matrix mehrere Stunden dauern. Das löst nicht das Problem, dass man schnell Embedding für neue Dokumente erhalten und die Embedding für die Dokumente aktualisieren muss, zu denen es bei der Erstellung des Modells wenig Informationen gab.

Uns hat die Einführung eines schnellen inkrementellen Updates des Modells geholfen. Angenommen, wir haben ein aktuelles trainiertes Modell. Seit seiner Schulung sind neue Artikel erschienen, mit denen unsere Benutzer interagiert haben, sowie Artikel, die während des Trainings wenig Interaktionen hatten. Um das Embedding solcher Artikel schnell zu erhalten, verwenden wir die Benutzer-Embeddings, die während des ersten großen Trainings des Modells erhalten wurden, und führen einen ALS-Schritt durch, um die Dokumentmatrix bei einer festen Benutzermatrix zu berechnen. Das ermöglicht es, das Embedding recht schnell zu erhalten — innerhalb weniger Minuten nach der Veröffentlichung eines Dokuments — und häufig die Embedding frischer Dokumente zu aktualisieren.

Um die Aktionen einer Person sofort in die Empfehlungen einzubeziehen, verwenden wir zur Laufzeit keine Benutzer-Embeddings, die offline erhalten wurden. Stattdessen führen wir einen ALS-Schritt durch und erhalten den aktuellen Benutzer-Vektor.

Übertragung auf ein anderes Anwendungsgebiet

Wie kann man das Feedback der Benutzer zu Textartikeln nutzen, um eine vektorielle Darstellung von Videos zu erstellen?

Ursprünglich haben wir nur Textartikel empfohlen, daher sind viele unserer Algorithmen auf diese Art von Inhalt ausgerichtet. Bei der Hinzufügung anderer Inhaltstypen standen wir vor der Notwendigkeit, die Modelle anzupassen. Wie haben wir dieses Problem am Beispiel von Videos gelöst? Eine Möglichkeit wäre gewesen, alle Modelle von Grund auf neu zu trainieren. Aber das dauert lange, zudem sind einige Algorithmen anspruchsvoll hinsichtlich der Menge an Trainingsdaten, die zu Beginn ihrer Lebensdauer auf dem Service für den neuen Inhalt noch nicht in ausreichendem Maße vorhanden sind.

Wir sind einen anderen Weg gegangen und haben Textmodelle für Videos wiederverwendet. Bei der Erstellung von Vektor-Darstellungen für Videos haben wir den gleichen Trick mit ALS verwendet. Wir haben die Vektor-Darstellung der Nutzer basierend auf Textartikeln genommen und einen ALS-Schritt gemacht, indem wir die Informationen über Videoaufrufe genutzt haben. So haben wir mühelos die Vektor-Darstellung für Videos erhalten. Zur Laufzeit berechnen wir einfach die Ähnlichkeit zwischen dem Nutzervektor, der auf den Textartikeln basiert, und dem Video-Vektor.

Fazit

Die Entwicklung des Kerns eines Echtzeit-Empfehlungssystems ist mit einer Vielzahl von Herausforderungen verbunden. Es müssen Daten schnell verarbeitet und ML-Methoden angewendet werden, um diese Daten effektiv zu nutzen; komplexe verteilte Systeme aufgebaut werden, die in der Lage sind, Benutzersignale und neue Inhalte in minimaler Zeit zu verarbeiten; sowie viele andere Aufgaben zu erledigen.

In dem aktuellen System, dessen Aufbau ich beschrieben habe, steigt die Qualität der Empfehlungen für den Nutzer mit seiner Aktivität und der Dauer seines Aufenthalts im Service. Doch hier liegt auch die größte Schwierigkeit: Es fällt dem System schwer, die Interessen einer Person zu verstehen, die wenig mit Inhalten interagiert hat. Die Verbesserung der Empfehlungen für neue Nutzer ist unsere Hauptaufgabe. Wir werden die Algorithmen weiterhin optimieren, damit relevante Inhalte schneller in ihren Feeds erscheinen und irrelevante nicht angezeigt werden.

Quelle: habr.com