Alai

Im Jahr 2004 begannen Microsoft Research und das Microsoft Web Search Team eine gemeinsame Anstrengung zur Verbesserung der Relevanz unserer Websuchergebnisse. In den folgenden Jahren wurden drei Generationen von Ranking-Algorithmen für die Websuche entwickelt, die in den Boosted-Tree-Ensembles gipfelten, die Bing heute verwendet. Den ersten dieser Ranking-Algorithmen nannten wir RankNet. Kürzlich wurde das RankNet-Papier, das 2005 auf der International Conference on Machine Learning (ICML) veröffentlicht wurde, mit dem „Test of Time“-Preis der ICML ausgezeichnet, einer Auszeichnung, die jedes Jahr an ein einzelnes Papier vergeben wird, das zehn Jahre zuvor auf der Konferenz vorgestellt wurde und in den dazwischen liegenden Jahren den größten wissenschaftlichen Einfluss hatte. Dies ist eine große Ehre und auch eine Gelegenheit, einen Blick zurück zu werfen und unsere Fortschritte in den letzten zehn Jahren zu bewerten. In diesem Artikel möchte ich diese Geschichte erzählen.

Die Websuche funktioniert im Wesentlichen so, dass die Suchanfrage des Benutzers genommen und die Relevanz jedes indizierten Dokuments dazu bewertet wird. Nicht jede Webseite ist im Index enthalten, aber der Index enthält dennoch Hunderte von Milliarden von Dokumenten, die in einer speziellen Datenstruktur gespeichert sind, um ein schnelles Auffinden zu ermöglichen. Da die besten Ergebnisse dem Benutzer in wenigen hundert Millisekunden präsentiert werden müssen, erfordert dies einen äußerst effizienten Filter- und Rangordnungsprozess. Die hier beschriebenen Ranker arbeiten mit einer (immer noch großen) Teilmenge der Dokumente, die mit Hilfe dieses schnellen anfänglichen Filterungsprozesses ausgewählt wurde. Grundsätzlich arbeitet ein Ranker mit einer Liste von Zahlen, von denen jede die Qualität einer bestimmten Abfrage/Dokument-Übereinstimmung auf eine bestimmte Weise misst (z. B. eine binäre Zahl, die angibt, ob die Abfrage ein Wort im Titel des Dokuments enthält oder nicht). Der Ranker ordnet dann diese Liste von Zahlen einem einzigen Relevanzmaß zu, das dann verwendet wird, um alle Dokumente für diese Abfrage in eine Rangfolge zu bringen. Die geordnete Liste von Zahlen, die der Ranker auf eine einzelne Punktzahl abbildet, wird als Merkmalsvektor bezeichnet.

Wenn der Ranker also zur Laufzeit für eine bestimmte Abfrage verwendet wird, nimmt er den Merkmalsvektor für jedes Abfrage/Dokumentenpaar und bildet ihn auf eine Zahl ab, die die Relevanz des Dokuments für die Abfrage erfasst. RankNet ist ein neuronales Feedforward-Netzmodell. Bevor es verwendet werden kann, müssen seine Parameter anhand einer großen Menge von gekennzeichneten Daten, dem so genannten Trainingsset, gelernt werden. Der Trainingssatz besteht aus einer großen Anzahl von Abfrage-/Dokumentenpaaren, wobei für jedes Paar eine Zahl zur Bewertung der Qualität der Relevanz des Dokuments für diese Abfrage von menschlichen Experten vergeben wird. Obwohl die Kennzeichnung der Daten eine langsame und menschenintensive Aufgabe ist, erfolgt das Training des Netzes mit den gekennzeichneten Daten vollautomatisch und recht schnell. Das von Microsoft im Jahr 2004 für das Training des Rankers verwendete System hieß The Flying Dutchman. Wir fanden heraus, dass der Flying Dutchman mehrere Tage und einen Cluster benötigte, um ein trainiertes Modell zu erstellen, während RankNet in der Lage war, ein Ranking-Modell in nur ein paar Stunden mit nur einer Maschine zu erstellen. RankNet lieferte auch eine deutlich bessere Relevanz als der zuvor verwendete Ranker, da neuronale Netze ein sehr breites Spektrum möglicher Zuordnungen modellieren können, während das frühere System nur auf lineare Zuordnungen beschränkt war.

So weit so gut, aber hätten wir es besser machen können? Die Antwort ist Ja, aber um zu verstehen, warum, muss ich ein wenig erklären, wie RankNet trainiert wird. Für jede Abfrage im Trainingssatz, für jedes Paar von Dokumenten, die für diese Abfrage eingestuft werden sollen, werden RankNet die beiden Merkmalsvektoren gezeigt, und es passt dann seine Parameter ein wenig an, indem es eine Methode namens Stochastic Gradient Descent (SGD) verwendet, so dass sich die angepassten Output-Scores für die beiden Merkmale in die richtige Richtung bewegen – das heißt, der Score für das relevantere Dokument steigt und der für das weniger relevante sinkt. Das bedeutet jedoch, dass RankNet hart daran arbeiten wird, hoch relevante Dokumente, die in der Rangliste sehr weit unten stehen, nach oben zu bringen, und auch hoch bewertete, aber weniger relevante Dokumente nach unten zu bringen. Indem es seine Ressourcen auf diese Weise einsetzt, schenkt es den wenigen Links, die dem Nutzer angezeigt werden, nicht so viel Aufmerksamkeit, wie es sollte. Unser Bewertungsmaßstab war seinerzeit eine Punktzahl namens NDCG, die eine einzige Zahl zur Bewertung der Gesamtqualität des Rankings angibt, wobei der Schwerpunkt viel stärker auf den ersten paar Ergebnissen liegt, die dem Nutzer angezeigt werden. NDCG ist daher ein natürlicheres Maß für die Websuche als der paarweise Fehler. Dies stellte uns vor eine Herausforderung: SGD läuft auf eine Suche in einem kontinuierlichen Raum hinaus, aber NDCG ist grundsätzlich ein diskretes Maß, da sich sein Wert nur ändert, wenn mindestens zwei Dokumente ihre Position in der Rangliste ändern. Ausreichend kleine Änderungen in den Modellbewertungen führen zu keiner Änderung des NDCG, und da SGD durch die Untersuchung kleiner Änderungen in den Bewertungen funktioniert, ist es schwer zu erkennen, wie man das NDCG mit SGD optimieren kann.

Wir haben eine Lösung für dieses Rätsel gefunden, die wir LambdaRank nennen. Der Trick bestand darin, zu erkennen, dass das gesamte Trainingsverfahren für ein neuronales Netz nur die Gradienten der Kostenfunktion benötigt, nicht die Kostenfunktion selbst. Man kann sich diese Gradienten als kleine Pfeile vorstellen, die an jedes Dokument in der Rangliste angehängt sind und angeben, in welche Richtung wir diese Dokumente bewegen möchten. LambdaRank nahm einfach die RankNet-Gradienten, von denen wir wussten, dass sie gut funktionierten, und skalierte sie mit der Änderung der NDCG, die durch den Austausch jedes Dokumentenpaars gefunden wurde. Wir fanden heraus, dass dieses Training Modelle mit deutlich verbesserter Relevanz (gemessen am NDCG) erzeugte und als zusätzlichen Bonus einen weiteren Trick aufdeckte, der die Trainingsgeschwindigkeit insgesamt verbesserte (sowohl für RankNet als auch für LambdaRank). Darüber hinaus fanden wir überraschenderweise empirische Belege dafür (siehe auch dieses Papier), dass das Trainingsverfahren tatsächlich die NDCG optimiert, obwohl die Methode, obwohl sie intuitiv und sinnvoll ist, keine solche Garantie bietet.

So weit, so gut, aber hätten wir es noch besser machen können? Die Antwort war wieder Ja. Wir kannten eine Klasse von Modellen, die sogenannten Boosted-Tree-Ensembles, von denen bekannt war, dass sie sehr starke Multiklassenklassifikatoren liefern. Was passiert, wenn man das Ranking-Problem als ein Mehrklassen-Klassifikationsproblem behandelt, mit einer Klasse für jede der fünf Relevanzstufen, die in der Trainingsmenge identifiziert wurden? Wir haben festgestellt, dass dies zu besseren Ergebnissen führt als LambdaRank (insbesondere eine Variante namens ordinale Multiklassenklassifikation). Boosted Trees haben den weiteren Vorteil, dass sie kategoriale und andere Arten von diskreten Merkmalen, die für neuronale Netze weniger gut geeignet sind, problemlos verarbeiten können. Wir glaubten, dass diese Ergebnisse auf die bessere Eignung dieser Modellklasse für unsere Daten zurückzuführen waren, und so stellte sich natürlich die Frage, ob wir Boosted-Tree-Modelle mit der LambdaRank-Idee kombinieren können, um das Beste aus beiden Welten zu erhalten. Das Training eines Boosted-Tree-Modells kann auch als eine Form von SGD betrachtet werden, und so lautete die Antwort Ja, in Form eines Modells, das wir LambdaMART nannten. LambdaMART hatte einen zusätzlichen Vorteil: Das Training von Baum-Ensemble-Modellen kann im Vergleich zu den entsprechenden neuronalen Netzen erheblich beschleunigt werden (diese Arbeit, die von O. Dekel geleitet wurde, ist noch nicht veröffentlicht). Dadurch können wir mit viel größeren Datensätzen trainieren, was wiederum zu einer verbesserten Ranking-Genauigkeit führt.

Wie schneiden unsere Ranker im Vergleich zu anderen in der Branche ab? Im Jahr 2010 veranstaltete Yahoo! einen „Learning to Rank“-Wettbewerb, bei dem es darum ging, wer den besten Ranking-Algorithmus für die Websuche hat. 1.055 Teams meldeten sich für diesen Wettbewerb an. Unser Team gewann den Wettbewerb mit einem Ensemble von LambdaMART-Modellen.

Wenn man auf das letzte Jahrzehnt zurückblickt, ist die vielleicht wichtigste technische Lektion die Bedeutung der Trainingsgeschwindigkeit. Schnelleres Training ermöglicht sowohl mehr Experimente als auch die Verwendung größerer Datensätze. Ich glaube, dass diese beiden Faktoren letztlich wichtiger sind als die zugrunde liegenden Algorithmen, solange letztere ausreichend aussagekräftige Modelle für die jeweilige Aufgabe sind. Die andere „Lebenslektion“, die ich aus dieser Erfahrung ziehe, ist die Bedeutung von Beharrlichkeit, aber vor allem die Bedeutung des Geschenks, mit wunderbaren Kollegen in den Produktgruppen, in Microsoft Research und in der Wissenschaft zusammenarbeiten zu können.

Chris Burges ist Principal Researcher und Research Manager bei Microsoft Research, wo er seit 2000 tätig ist. Davor arbeitete er bei AT&T Bell Labs, wo er 1986 eintrat. Davor war er Postdoktorand in der Abteilung für Theoretische Physik am MIT, wo er nach einem mit Auszeichnung abgeschlossenen Physik- und Mathematikstudium in Oxford in Physik an der Brandeis University promovierte. Seine Interessen erstreckten sich auf die Systemtechnik großer Kommunikationsnetze (AT&T verwendet seine Algorithmen noch immer, um mehrere wichtige Netze zu routen), neuronale Netze für die Erkennung von Handschrift und Maschinendruck (er arbeitete an einem System, mit dem heute täglich Millionen von Schecks gelesen werden, und tatsächlich wurde sein langer Weg zum maschinellen Lernen durch eine besonders coole Demo eines neuronalen Netzes ausgelöst, das Anfang der 90er Jahre handgeschriebene Ziffern erkannte), Support Vector Machines (er hatte das Glück, in den Anfängen mit Vladimir Vapnik, dem Miterfinder der SVM, zusammenzuarbeiten, und schrieb ein Tutorial, das einigen Leuten gefiel), Audio Fingerprinting (seine Arbeit wird derzeit in Xbox und Windows Media Player zur Identifizierung von Musik verwendet), Sprecherverifizierung, Information Retrieval und Ranking (sein Ranking-Algorithmus wird derzeit von Bing für die Websuche verwendet). Chris‘ derzeitige Leidenschaft gilt der Entwicklung neuer Ansätze für ein skalierbares, umsetzbares maschinelles Textverständnis, das zwar zugegebenermaßen sehr ehrgeizig ist, uns aber dennoch etwas lehren wird, sofern wir nicht aufhören, es zu versuchen. Chris war Co-Vorsitzender der Neural Information Processing Systems 2012 und allgemeiner Co-Vorsitzender der NIPS 2013.

Weitere Nachrichten aus der Informatikforschung finden Sie unter ResearchNews.com.