Ranking results using multiple nested ranking

• US 20060195440A1
• Filed: 12/05/2005
• Published: 08/31/2006
• Est. Priority Date: 02/25/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wong, Leon C.W., Burkard, Timo, Burges, Christopher J., Laucius, Andrew S., Matveeva, Irina
• Granted Patent: US 7,689,615 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/337 Profile generation, learning or modification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06N 3/045 Combinations of networks
• CPC Class Codes: G06N 3/084 Backpropagation, e.g. using gradient descent

Abstract

A unique system and method that facilitates improving the ranking of items is provided. The system and method involve re-ranking decreasing subsets of high ranked items in separate stages. In particular, a basic ranking component can rank a set of items. A subset of the top or high ranking items can be taken and used as a new training set to train a component for improving the ranking among these high ranked documents. This process can be repeated on an arbitrary number of successive high ranked subsets. Thus, high ranked items can be reordered in separate stages by focusing on the higher ranked items to facilitate placing the most relevant items at the top of a search results list.

Claims

1. A ranking system that provides improved rankings for items returned for a given query comprising:

an initial set of items for which an ordering thereof is desired; and

a multiple nested ranking component (120) that re-ranks one or more decreasing subsets of high ranked items to facilitate obtaining the most relevant ordering of the items.

2. The system of claim 1, the multiple nested ranking component comprises a plurality of ranking algorithms trained via machine learning or statistical methods.

3. The system of claim 2, the plurality of ranking algorithms comprising:

at least an initial ranking algorithm (NET₀) trained to rank the initial set of items; and

one or more subsequent ranking algorithms subsequently trained on ranked items taken from previous re-ranked subsets of items.

4. The system of claim 3, the first subset of items comprises items in the highest order positions on the list.

5. The system of claim 2 further comprises a training set modification component that successively prunes each previous training set in part by excluding one or more items from each training set to form a new training set, each new training set comprises a subset of the items from the previous training set.

7. The system of claim 1, the multiple nested ranking component reorders a subset of the initial set of items retrieved by the search component in one or more separate stages to place the most relevant high scoring items at the top of the list.

8. The system of claim 1 further comprises a display component that presents a search result list to the user, the search result list comprising at least a subset of items that have been reordered using a plurality of separately trained neural nets.

6. The system of claim 6, the plurality of ranking algorithms are trained in a successive manner using a corresponding training set.

9. A method that provides improved rankings for items returned for a given query comprising:

retrieving an initial ordered set of items; and

re-ranking one or more decreasing subsets of ranked items to facilitate obtaining the most relevant ordering of the items.

10. The method of claim 9 further comprises ranking the initial set of items and selecting a top subset of items therefrom to re-rank.

11. The method of claim 10, the re-ranking of the top subset of items is conducted in one or more separate stages.

12. The method of claim 9, the re-ranking comprises:

selecting decreasing top subsets of high ranked items;

modifying training sets used to train modified ranking algorithms; and

reordering the top subsets of high ranked items.

13. The method of claim 12, modifying training sets comprises:

pruning at least a first training set by excluding a plurality of low ranked items and leaving at least a top subset of high ranked items therein to form at least one modified training set; and

training at least one modified ranking algorithm on the at least one modified training set.

14. The method of claim 9, the re-ranking is conducted via at least one trained ranking algorithm.

15. The method of claim 9 further comprises presenting a list to the user, the list comprising a subset of items that have been re-ranked.

16. The method of claim 9 reorders a subset of the items from the initial set of items.

17. The method of claim 9, the re-ranking employs one or more ranking algorithms trained on datasets, whereby the ranking algorithms that are trained on smaller datasets are more complex learning algorithms than those trained on larger datasets.

18. A ranking system that provides improved rankings for items returned for a given query comprising:

a means for retrieving an initial ordered set of items for the given query; and

a means for re-ranking one or more decreasing subsets of high ranked items to facilitate obtaining the most relevant ordering of the items.

19. The system of claim 18 further comprises a means for modifying training sets to facilitate separately training a plurality of ranking algorithms.

20. The system of claim 18 further comprising a means for presenting a list of ordered items, the list comprising at least a subset of items that have been re-ranked.