Wie prognostizieren wir die Zukunft bei der Yandex-Suche: von Fehlerkorrekturen bis zu Erkennungsabfragen

Die Leute formulieren ihre Anfragen nicht immer genau, daher sollten Suchmaschinen ihnen dabei helfen. Mein Name ist Sergey Yudin. Ich leite eine Gruppe von Suchfunktionsanalysen in Yandex. Jeden Tag verbessern wir etwas durch maschinelles Lernen. Letztes Jahr haben wir Technologien entwickelt, die menschliche Interessen vorsehen.

Mit einer Expertin aus meinem Team Anastasia GaidashenkoavgaydashenkoIch werde den Lesern von Habr erzählen, wie diese Technologie funktioniert, ich werde Architektur und angewandte Algorithmen beschreiben. Sie erfahren auch, wie sich die Vorhersage der nächsten Anfrage von der Vorhersage zukünftiger menschlicher Interessen unterscheidet.

Was will der Benutzer?

Lassen Sie uns am Beispiel eines imaginären Benutzers sehen, wie Yandex-Technologien bei der Lösung von Problemen helfen. Angenommen, er druckt "Ticket speichern" in das Suchfeld. Was will er finden? Um etwas über die Anhäufung von Tickets zu erfahren, oder hat er sich einfach geirrt?



Ja, er war versiegelt. Er will nicht sparen, sondern ein Ticket kaufen. Yandex verstand ihn, der Vormund half ihm dabei - ein System, das falsch eingegebene Anfragen korrigiert . Mathematisch maximiert dieses System die Wahrscheinlichkeit einer korrekt eingegebenen Abfrage, vorausgesetzt, der Benutzer hat den Text eingegeben. Dieses Problem wurde in Yandex seit mehr als zehn Jahren gelöst. Und das nicht nur bei der Suche.

Also gab unser imaginärer Benutzer die Anfrage "Ticket kaufen" ein. An diesem Punkt kommt ein Sjest ins Spiel .(oder Suchvorschläge). Sajest hilft dem Benutzer, die Anfrage zu formulieren und korrekt zu vervollständigen.



Unser Sajest hat einen langen Weg zurückgelegt. Vor ein paar Jahren haben wir die Aufgabe kompliziert. Ich wollte nicht nur den logischsten Abschluss der Anfrage anzeigen, sondern auch vorhersagen, welche Anfrage dieser Benutzer am Ende eingeben und seinen Prerender vor dem Klick starten würde. Wenn Sie daran interessiert sind, wie das funktioniert, können Sie sich Habré ansehen .

Unser imaginärer Benutzer wählt das Ende der Anfrage aus einer Reihe von Tipps aus: Es stellt sich heraus, dass er nach Tickets für die Tretjakow-Galerie gesucht hat. Damit hat das Empfehlungssystem seine erste Aufgabe erledigt - es hat dem Benutzer geholfen, eine Anfrage zu formulieren .

Diese Aufgabe wurde abgeschlossen, aber der Benutzer hat noch Fragen. Was wird er als nächstes suchen? Vielleicht möchte er wissen, wie er zur Galerie kommt? Ja, er druckt Lavrushinsky per. 10, um die Adresse zu überprüfen.



Können wir diese Anfrage vorhersagen? Ja. Und das machen wir schon seit einiger Zeit. Es gibt einen solchen Block - "Auch gefragt" am Ende der Ausgabe. Es zeigt die Abfragen, die normalerweise nach dem Eingeben in das Suchfeld gestellt werden. Darin sehen wir unsere Anfrage mit der Adresse der Tretjakow-Galerie.



Wir maximieren die Wahrscheinlichkeit einer Anfrage, die einer vorherigen Benutzeranfrage unterliegt. Das System hat die zweite Aufgabe abgeschlossen - die nächste Anforderung vorhergesagt .

Und dann passiert etwas sehr Interessantes. Der Benutzer druckt die Anfrage "Wann kann ich die Tretjakow-Galerie kostenlos besuchen?". Diese Anforderung unterscheidet sich von den anderen, läuft der Benutzeraufgabe entgegen und löst eine orthogonale Aufgabe.



Aber denken wir mal: Wenn wir nach Tickets für die Galerie suchen würden, was würden wir gerne als Empfehlung sehen? Eine große Anzahl von Menschen möchte wissen, dass ein Ticket möglicherweise nicht gekauft werden muss. Dies ist der dritte, schwierigste und interessanteste Teil der Aufgabe - dem Benutzer etwas Neues und Nützliches zu empfehlen. Etwas, an das er selbst noch nicht gedacht hatte.

Wir nennen solche Anfragen Entdeckung. Wir lernen, sie in unseren Suchprotokollen zu identifizieren, zu speichern und am Ende der Ausgabe zu empfehlen. Und genau an dieser neuen und revolutionären Aufgabe arbeiten wir gerade aktiv. Für eine Person, die skandinavische Sticks kauft, kann Yandex eine Anfrage empfehlen, wie sie nach Größe abgeholt werden sollen. Wenn eine Person häufig reist, interessiert sie sich möglicherweise für die Suchanfrage "Wohin ohne Visum?". Usw.



Die mathematische Formulierung des Problems in diesem Fall sieht folgendermaßen aus: Wir maximieren nicht die Wahrscheinlichkeit der nächsten Anforderung, sondern die Wahrscheinlichkeit eines Klicks auf die Anforderung, die wir dem Benutzer basierend auf seiner vorherigen Sitzung empfehlen.

Wie es funktioniert?

Schauen wir uns an, wie unser Empfehlungssystem implementiert ist und welche Architektur dahinter verborgen ist. Zunächst werden wir jedoch festlegen, was wir im Allgemeinen vom Empfehlungssystem erhalten möchten.

1. Nützliche Empfehlungen! Natürlich möchten wir, dass die Anfragen, die wir dem Benutzer empfehlen, seinen Interessen entsprechen. Sie sollten nützlich und relevant sein.

2. Skalierbarkeit. Wir hoffen, dass das System gut wird: Es wird immer mehr Benutzer geben und die Anzahl der Anfragen wird zunehmen. Und wir möchten die Abdeckung für diejenigen erhöhen, zu denen wir Empfehlungen aussprechen können.

3. Einfache Implementierung.Wir gehen davon aus, dass unser System weiterhin funktioniert, und wir möchten es nicht viele Male neu schreiben. Das System sollte einfach zu implementieren sein, damit wir es später verbessern können, ohne eine neue Version zu starten, sondern die aktuelle zu verbessern.

Nachdem wir uns für unsere Wünsche entschieden haben, wollen wir sehen, wie Sie sie zum Leben erwecken können.

Wir haben eine Discovery-Datenbank - eine Datenbank mit Abfragen, die unseren Benutzern interessant und nützlich erscheinen können. Wenn wir jedoch anfangen, diese gesamte Basis zu bewerten, werden wir nicht genug Rechenleistung haben. Benutzer haben viele Anforderungen, sie sind unterschiedlich, daher müssen wir zuerst diese Datenbank filtern.



Das Filtern kann mit verschiedenen Methoden erfolgen. In Yandex verwenden wir dafür kNN (k-nächste Nachbarn)- Der grundlegende Klassifizierungsalgorithmus beim maschinellen Lernen, bekannt als "Suche nach dem nächsten Nachbarn". Mit diesem Algorithmus möchten wir die Datenbank filtern: Wählen Sie die Abfragen aus, die dem Benutzer am nächsten kommen. Zu diesem Zweck möchten wir die Benutzeranforderung mit den Anforderungen vergleichen, die wir im Vektorraum empfehlen möchten.

Aber um diese Anforderungen in einen Vektorraum zu bringen, müssen wir uns auch etwas einfallen lassen. Sie können beispielsweise DSSM (Deep Structured Semantic Model) verwenden - eine Art Black Box, mit der verschiedene Entitäten in einen Vektorraum übersetzt werden können. Dieser Ansatz wurde ursprünglich in einem Artikel von Microsoft vorgeschlagen. Aber Yandex hat es bereits ziemlich stark an seine Aufgaben angepasst und ist weit von der ursprünglichen Idee entfernt. Wenn Sie mehr darüber lesen möchten , finden Sie die Informationen beispielsweise im Artikel über den Palekh-Suchalgorithmus .



Der nächste Schritt ist das Ranking. Wenn wir eine Liste von Anfragen haben, die nahe an dem liegen, woran der Benutzer interessiert sein könnte, möchten wir verstehen, was für ihn interessanter und was weniger interessant ist.

Zum Beispiel haben wir 100 Abfragen ausgewählt. Es ist unwahrscheinlich, dass der Benutzer alle 100 scrollt. Sie müssen die Top 5 auswählen und empfehlen. Dazu weisen wir unseren Anfragen Bewertungen zu. Wir erhalten diese Schätzungen basierend auf der Wahrscheinlichkeit eines Klicks auf eine Anfrage, die wir dem Benutzer aufgrund seiner vorherigen Sitzung empfehlen.

Wie erhalten wir die Wahrscheinlichkeit des nächsten Klicks? Unser System ist bereits in Betrieb, daher sammeln wir einfach Feedback von Benutzern - und verbessern dadurch schrittweise unser Empfehlungssystem.



Nachdem wir alle Schritte separat überprüft haben, kehren wir zum Anfang zurück und fügen alles zusammen. Insgesamt: Der Benutzer kommt mit einer Anfrage zu uns und wir haben eine Art Empfehlungsbasis. Wir nehmen diese Datenbank und filtern sie. Wir erhalten Anfragen, die wir arrangieren und dem Benutzer empfehlen möchten.



Denken Sie jetzt daran, dass wir allgemein Wünsche für unser Empfehlungssystem formuliert haben. Und lassen Sie uns sehen, wie wir sie in die resultierende Architektur implementieren können.

Zum Beispiel wollten wir Skalierbarkeit im Hinblick auf die Verbesserung der Basis. Unsere Implementierungsmethode verfügt über alle für eine solche Skalierung erforderlichen Eigenschaften. Wir sollten nicht die gesamte Basis im Speicher behalten: Sobald sich die Basis so stark erweitert, dass sie nicht auf einen Cluster passt, können wir sie in zwei Teile aufteilen. Und wenn wir früher einen Cluster mit kNN durchlaufen und die Top 100 ausgewählt haben, die wir bewerten werden, können wir jetzt zwei Cluster separat durchlaufen und beispielsweise die Top 50 in jedem auswählen. Oder teilen Sie Cluster im Allgemeinen nach Themen auf und gehen Sie mit kNN nur zu den gewünschten Themen.

Um die Anzahl der Benutzer zu skalieren, können Sie einfach zusätzliche Rechenleistung hinzufügen und jeden einzeln verarbeiten, da es in unserer Architektur keine Orte gibt, an denen alle Benutzer gleichzeitig im Speicher bleiben müssten.

Bei einigen anderen Ansätzen gibt es Stellen, die beispielsweise beim Zerlegen einer Matrix filtern. Die Matrixzerlegung ist ein weiterer Ansatz, der in den Empfehlungen verwendet wird. Tatsächlich verwendet Yandex es auch, jedoch nicht zum Filtern, sondern als zusätzliche Funktionen für das Training, da noch viele Informationen zu analysieren sind.

Zusätzliche Funktionen, neue Algorithmen und andere Methoden können auf den Rest der Architektur angewendet werden. Wenn das System betriebsbereit ist, können wir damit beginnen, es zu verbessern.

Wo funktioniert es?

Eine solche Architektur wurde bereits in Yandex implementiert, und im Vergleich zu den üblichen Umformulierungen können wir, als wir versuchten, den Benutzer zu beraten, die Adresse der Tretjakow-Galerie herauszufinden, bereits beraten, wie man zur Tretjakow-Galerie gelangt, ohne in der Schlange zu stehen oder sogar kostenlos.



Dies ist eine neue Ebene der Interaktion zwischen der Suchmaschine und den Benutzern. Wir korrigieren nicht nur Fehler und ergänzen Anfragen, sondern lernen, die Interessen einer Person vorherzusagen und ihr etwas Neues anzubieten. Vielleicht ist dies die Suche nach der Zukunft. Was denken Sie?