Alai

In 2004, begonnen Microsoft Research en Microsoft’s Web Search team een gezamenlijke inspanning om de relevantie van onze web zoekresultaten te verbeteren. Er volgde een langdurige inspanning die, gedurende de volgende jaren, resulteerde in onze verzending van drie generaties van web search ranking algoritmen, culminerend in de boosted tree ensembles die Bing vandaag gebruikt. We noemden de eerste van deze ranking algoritmen RankNet. Onlangs won het RankNet artikel, dat werd gepubliceerd in de International Conference on Machine Learning (ICML) in 2005, ICML’s “Test of Time” prijs, een prijs die elk jaar wordt gegeven aan dat ene artikel dat tien jaar eerder op de conferentie werd gepresenteerd en waarvan werd geoordeeld dat het de hoogste algemene academische impact had in de tussenliggende jaren. Dit is een grote eer en ook een gelegenheid om terug te blikken en onze vooruitgang in het afgelopen decennium te evalueren. In dit artikel wil ik dit verhaal vertellen.

Web search werkt in wezen door de zoekvraag van de gebruiker te nemen en de relevantie van elk geïndexeerd document daarvoor te beoordelen. Niet elke webpagina staat in de index, maar de index bevat niettemin honderden miljarden documenten, opgeslagen in een speciale datastructuur om het opzoeken snel te maken. Aangezien de topresultaten in een paar honderd milliseconden aan de gebruiker moeten worden gepresenteerd, vereist dit een uiterst efficiënt filter- en rangschikkingsproces. De hier beschreven rangschikkers werken op een (nog steeds grote) subset van de documenten, die wordt gekozen met behulp van dit snelle initiële filterproces. In principe werkt een rangschikker door een lijst van getallen te nemen, die elk de kwaliteit van een bepaalde query/document overeenkomst op een bepaalde manier meten (bijvoorbeeld een binair getal dat weergeeft of de query al dan niet een woord in de titel van het document bevat). De rangschikker zet die lijst van getallen vervolgens om in één enkele relevantiemaatstaf, die vervolgens wordt gebruikt om alle documenten voor die query te rangschikken. De geordende lijst van getallen die de ranker in een enkele score omzet wordt een feature vector genoemd.

Dus wanneer gebruikt bij runtime, voor een gegeven query, neemt de ranker de feature vector voor elk query/document paar en zet deze om in een getal dat de relevantie van dat document voor de query weergeeft. RankNet is een feedforward neuraal netwerk model. Voordat het kan worden gebruikt moeten zijn parameters worden geleerd met behulp van een grote hoeveelheid gelabelde gegevens, de trainings set genoemd. De trainingsset bestaat uit een groot aantal query/document paren, waarbij voor elk paar een getal wordt toegekend door menselijke experts, dat de kwaliteit van de relevantie van het document voor die query beoordeelt. Hoewel het labelen van de gegevens een langzame en mensintensieve taak is, verloopt het trainen van het net, gegeven de gelabelde gegevens, volledig automatisch en vrij snel. Het systeem dat Microsoft in 2004 gebruikte voor het trainen van de ranker heette The Flying Dutchman. Wij ontdekten dat, terwijl The Flying Dutchman verscheidene dagen en een cluster nodig had om een getraind model te produceren, RankNet in staat was om een ranking model te produceren in slechts een paar uur met slechts één machine. RankNet gaf ook significant verbeterde relevantie ten opzichte van de eerder gebruikte ranker, omdat neurale netten een zeer breed scala van mogelijke mappings kunnen modelleren, terwijl het vorige systeem beperkt was tot slechts lineaire mappings.

So far so good, but could we have done better? Het antwoord is Ja, maar om te zien waarom, moet ik een beetje uitleggen hoe RankNet wordt getraind. Voor elke query in de training set, voor elk paar documenten die gerangschikt moeten worden voor die query, wordt RankNet de twee kenmerk vectoren getoond en het past dan zijn parameters een beetje aan, met behulp van een methode genaamd Stochastic Gradient Descent (SGD), zodat de aangepaste output scores voor de twee kenmerken in de juiste richting bewegen – dat wil zeggen, de score voor het meer relevante document stijgt, en die voor het minder relevante, daalt. Maar dat betekent dat RankNet hard zal werken om zeer relevante documenten die zeer laag in de rangschikking staan te verhogen, en ook om hoog scorende maar minder relevante documenten te verlagen. Door zijn middelen op deze manier te besteden, besteedt het niet zo veel aandacht als het zou moeten besteden aan alleen de bovenste paar links die aan de gebruiker worden getoond. In feite was onze evaluatiemethode destijds een score die NDCG werd genoemd, en die één getal oplevert dat de algemene kwaliteit van de rangschikking beoordeelt, met een veel grotere nadruk op de top enkele resultaten die aan de gebruiker worden getoond. NDCG is dus een meer natuurlijke maatstaf voor websearch dan paarsgewijze fouten. Dit stelde ons voor een uitdaging: SGD komt neer op een zoektocht in een continue ruimte, maar NDCG is fundamenteel een discrete maatstaf, in die zin dat de waarde alleen verandert als ten minste twee documenten van positie veranderen in de gerangschikte lijst. Voldoende kleine veranderingen in modelscores geven geen verandering in NDCG, en aangezien SGD werkt door kleine veranderingen in scores te onderzoeken, is het moeilijk te zien hoe NDCG met behulp van SGD kan worden geoptimaliseerd.

We hebben een antwoord op deze puzzel gevonden, dat we LambdaRank hebben genoemd. De truc was om op te merken dat de hele trainingsprocedure voor een neuraal net alleen de gradiënten van de kostenfunctie nodig heeft, niet de kostenfunctie zelf. Je kunt deze gradiënten zien als kleine pijltjes die aan elk document in de gerangschikte lijst zijn vastgemaakt, en die aangeven in welke richting we willen dat die documenten bewegen. LambdaRank nam gewoon de RankNet gradiënten, waarvan we wisten dat ze goed werkten, en schaalde ze met de verandering in NDCG die gevonden werd door elk paar documenten te verwisselen. We ontdekten dat deze training modellen genereerde met significant verbeterde relevantie (zoals gemeten door NDCG) en als extra bonus ontdekten we nog een truc die de totale trainingssnelheid verbeterde (voor zowel RankNet als LambdaRank). Bovendien vonden we, verrassend genoeg, empirisch bewijs (zie ook dit artikel) dat de trainingsprocedure inderdaad NDCG optimaliseert, ook al heeft de methode, hoewel intuïtief en verstandig, die garantie niet.

Zo ver zo goed, maar nogmaals, hadden we het beter kunnen doen? Het antwoord was weer ja. We kenden een klasse van modellen, genaamd “boosted tree ensembles”, waarvan bekend is dat ze zeer sterke multiclass classifiers maken. Wat gebeurt er als je het rangschikkingsprobleem behandelt als een multiklasse classificatieprobleem, met een klasse voor elk van de vijf niveaus van relevantie die in de trainingsset zijn geïdentificeerd? We ontdekten dat dit betere resultaten gaf dan LambdaRank (vooral een variant die ordinale multiklasse classificatie wordt genoemd). Boosted trees hebben het voordeel dat zij gemakkelijk kunnen omgaan met categorische en andere discrete kenmerken, die minder geschikt zijn voor neurale netten. Wij dachten dat deze resultaten te danken waren aan de betere geschiktheid van deze klasse van modellen voor onze gegevens, en dus was de natuurlijke vraag, kunnen we boosted tree modellen combineren met het LambdaRank idee, om het beste van twee werelden te krijgen? Het trainen van een boosted tree model kan ook worden gezien als een vorm van SGD, en dus was het antwoord ja, in de vorm van een model dat we LambdaMART noemden. LambdaMART had een bijkomend voordeel: de training van boom-ensemble modellen kan zeer aanzienlijk worden versneld ten opzichte van het neurale net equivalent (dit werk, geleid door O. Dekel, is nog niet gepubliceerd). Dit stelt ons in staat om te trainen met veel grotere datasets, wat opnieuw een verbeterde ranking nauwkeurigheid geeft.

Hoe verhouden onze rankers zich tot anderen in de industrie? In 2010, Yahoo! organiseerde een learning to rank uitdaging, waarvan een track was ontworpen om te zien wie de beste web search ranking algoritme had. 1.055 teams schreven zich in voor de uitdaging. Ons team won de wedstrijd met een ensemble van LambdaMART-modellen.

Terugkijkend op het afgelopen decennium is de meest in het oog springende technische les misschien wel het belang van trainingssnelheid. Snellere training maakt zowel meer experimenten mogelijk als het gebruik van grotere datasets. Ik denk dat deze twee factoren uiteindelijk belangrijker zijn dan de onderliggende algoritmen die worden gebruikt, zolang deze laatste maar voldoende expressieve modellen zijn voor de taak in kwestie. De andere “levensles” die ik uit deze ervaring trek, is het belang van volharding, maar vooral van het geschenk te kunnen samenwerken met fantastische collega’s, in de productgroepen, in Microsoft Research, en in de academische wereld.

Chris Burges is Principal Researcher en Research Manager bij Microsoft Research, waar hij sinds 2000 werkzaam is. Daarvoor werkte hij bij AT&T Bell Labs, waar hij in 1986 in dienst trad. Daarvoor was hij postdoctoraal medewerker bij de afdeling Theoretische Fysica van het MIT, waar hij in dienst trad nadat hij zijn doctoraat in de fysica had behaald aan Brandeis, na een graad met First Class Honors in fysica en wiskunde aan Oxford. Zijn interesses strekken zich uit over de systeemengineering van grote communicatienetwerken (AT&T gebruikt nog steeds zijn algoritmen om verschillende belangrijke netwerken te leiden), neurale netwerken voor handschriftherkenning en machineafdrukherkenning (hij werkte aan een systeem dat nu dagelijks wordt gebruikt om miljoenen cheques te lezen, en in feite werd zijn lange afdaling in machine learning getriggerd door een bijzonder coole demo van een neuraal net dat handgeschreven cijfers herkende in het begin van de jaren ’90), support vector machines (hij had het geluk om samen te werken met Vladimir Vapnik, de medebedenker van SVM, in de begindagen, en hij schreef een tutorial die sommige mensen leuk vonden), audio fingerprinting (zijn werk wordt momenteel gebruikt in Xbox en Windows Media Player om muziek te identificeren), speaker verificatie, information retrieval, en ranking (zijn ranking algoritme wordt momenteel gebruikt door Bing voor web search). Chris’ huidige passie ligt bij het ontwikkelen van nieuwe benaderingen voor schaalbaar, bruikbaar machinaal tekstbegrip, dat weliswaar erg ambitieus is, maar ons waarschijnlijk toch iets zal leren, tenzij we stoppen met proberen. Chris was programma covoorzitter van Neural Information Processing Systems 2012 en algemeen covoorzitter van NIPS 2013.

Voor meer computerwetenschappelijk onderzoeksnieuws, bezoek ResearchNews.com.