Faster self-learning search engine through UvA algorithm
This article describes my work and was written by my colleagues David Graus and Marlies van der Wees (thanks!). It was posted on the uva.nl website on 4 November 2014.
How does Google know which search results to display? There are many algorithms that generate search results, but which one works best? Professor Maarten de Rijke of the University of Amsterdam (UvA) has headed the development of a new method for quickly comparing large numbers of search algorithms by examining the results users click on. The search engine learns quickly and continuously from user input, enabling it to determine which algorithms produce the best results.
The results of this study, which is part of the LiMoSINe Project (EU/FP7) supported by the Netherlands Organisation for Scientific Research (NWO), will be presented at the leading international ‘Conference on International and Knowledge Management’ (CIKM 2014) in Shanghai this week.
Search engines such as Google often use hundreds of different search algorithms, all of which aim to find the best possible match between a user’s search query and web page content. An important reason for Google’s leading position among search engines is the fact that they constantly expand and improve their search algorithms. But in order to improve those algorithms – and hence the results – it is vital to know which one produces the best results.
One way to compare algorithms is through interleaving, a method whereby the search engine analyses users’ click behaviour to determine the algorithm that yields the most satisfactory results. The results of two search algorithms (A and B) are displayed mixed together and the search engine then keeps track of which pages users click on. If the user clicks on a page found by search algorithm A, the search engine knows that A produces better results than B in this particular case. By scaling up this type of analysis (using millions of users), the search engine automatically learns which algorithm yields the best results.
Interleaving is, however, limited by the fact that only two algorithms can be compared at a time, and thousands of comparisons may therefore easily be required to determine which of the hundreds of algorithms works most effectively.
The method developed by the university allows multiple algorithms to be compared simultaneously and therefore identifies the best algorithm much more rapidly, enabling the faster improvement of search engines.
Schuth A., Sietsma F., Whiteson S., Lefortier D., de Rijke M. 2014. Multileaved comparisons for fast online evaluation. CIKM 2014: 23rd ACM Conference on Information and Knowledge Management.