menu
19 augustus 2016

Beste learning to rank resultaten op LETOR4.0

Onze academische achtergrond dwingt ons om de algoritmes die we ontwikkelen grondig te testen. En dit doen we dus ook. Recente experimenten op publieke data (LETOR4.0) laten zien dat onze zelflerende zoekmachine substantieel beter presteert dan bestaande state-of-the-art zoekalgoritmes. Wat betekent dit? Dat je waarschijnlijk geen beter (machine learning) zoekalgoritme vindt dan wij hebben.

LETOR4.0 details

Laten we de details eens bekijken. We hebben de experimenten gedraaid op de LETOR4.0 dataset, beschikbaar gemaakt door Microsoft. Deze dataset is vooral bruikbaar voor het testen van learning to rank methodes: zoekalgoritmes gebaseerd op machine learning. Aangezien 904Labs zelflerende zoekmachine precies dat is, is de LETOR4.0 dataset perfect om zijn prestaties te bepalen. De dataset bevat zo'n 25 miljoen webdocumenten en ongeveer 1.700 zoekvragen met gelabelde documenten. Gelabelde documenten hebben een relevantiescore voor een gegeven zoekvraag zodat we weten welke documenten relevant zijn en welke niet.

Voor learning to rank experimenten hebben we niet de originele teksten van documenten en zoekvragen nodig. In de LETOR4.0 dataset worden documenten en zoekvragen gerepresenteerd door feature vectoren. Een simpel voorbeeld: we hebben de zoekvraag "fiets" en een document X (van 100 woorden lang) dat het woord fiets acht keer bevat. Daarbovenop heeft het document 20 inkomende links en een URL lengte van 70 karakters. In plaats van het document en de zoekvraag als tekst te representeren kunnen we nu ook zeggen dat voor de zoekvraag "fiets" document X eruit ziet als [100, 8, 20, 70]. We hebben het document nu gerepresenteerd met vier features en hun waardes: documentlengte (100), frequentie van de zoekvraag (8), het aantal inkomende links (20) en de lengte van de URL (70). We kunnen nog veel meer features bedenken en dit is wat voor LETOR4.0 ook gedaan is. De dataset bevat 46 features die allemaal beschreven zijn in deze pdf.

Learning To Rank systemen

Het doel van elk learning to rank systeem is om de optimale combinatie van de beschikbare features te vinden om zo de beste sortering van zoekresultaten te genereren voor elke willekeurige zoekvraag. Om dit te bereiken moeten de systemen getraind worden. De LETOR4.0 dataset bevat een training-, validatie- en testset. Systemen worden eerste getraind op de trainingset en worden gevalideerd op de validatieset. Dit kan enkele keren herhaald worden totdat de resultaten bevredigend zijn. Pas nadat alles in orde lijkt te zijn wordt het laatst-getrainde systeem toegepast op de testdata. Hierdoor weten we zeker dat de testdata nog nooit eerder gezien is door het systeem en het systeem kan dus niks "uit zijn hoofd" geleerd hebben.

Door de jaren heen zijn er vele verschillende learning to rank systemen voorgesteld. De belangrijkste hiervan zijn getraind en getest op de LETOR4.0 dataset. Deze systemen zijn RankSVM-Struct, ListNet, AdaRank, en RankBoost. In de resultatensectie hieronder vergelijken we deze systemen met de learning to rank methode die in onze zelflerende zoekmachine zit, genaamd 3PR.

Resultaten

We meten de prestaties in nDCG@5. Normalized Discounted Cumulative Gain (nDCG) is een metriek die uitdrukt hoe goed een systeem is in het tonen van de beste zoekresultaten bovenaan de lijst. Hoe beter het systeem hierin is, hoe dichter de score komt bij 1.0. We meten nDCG over de eerste vijf documenten voor elke zoekvraag, waarmee we een gebruiker nabootsen die de beste resultaten in de top 5 wil zien. De resultaten in de onderstaande lijst tonen aan dat ons systeem ruim 4% beter is in nDCG dan het beste learning to rank systeem (RankBoost).

  1. 904Labs: 0.4366
  2. RankBoost: 0.4183
  3. ListNet: 0.4170
  4. RankSVM-Struct: 0.4143
  5. AdaRank: 0.4102

Onderstaande grafiek toont dat de prestatie van onze zelflerende zoekmachine verbetert wanneer er meer trainingsdata gebruikt kan worden. Dit kan gezien worden als een simulatie van tijd: terwijl meer data het zelflerende systeem binnenkomt, wordt deze beter in het combineren van de beschikbare features en genereert daardoor betere zoekresultaten.

904Labs on MSLR2007

Samenvattend, 904Labs zelflerende zoekmachine wordt ondersteund door de beste learning to rank methode beschikbaar. Wil je meer weten over onze producten of over de onderliggende algoritmes, neem dan gerust contact op.