Multi-Ranker For Search

• US 20090083248A1
• Filed: 09/21/2007
• Published: 03/26/2009
• Est. Priority Date: 09/21/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tao, Qin, Liu, Tie-Yan, Li, Hang
• Granted Patent: US 8,122,015 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G06N 20/20 Ensemble learning

Abstract

Systems and methods for processing user queries and identifying a set of documents relevant to the user query from a database using multi ranker search are described. In one implementation, the retrieved documents can be paired to form document pairs, or instance pairs, in a variety of combinations. Such instance pairs may have a rank order between them as they all have different ranks. A classifier, hyperplane, and a base ranker may be constructed for identifying the rank order relationships between the two instances in an instance pair. The base ranker may be generated for each rank pair. The systems use a divide and conquer strategy for learning to rank the instance pairs by employing multiple hyperplanes and aggregate the base rankers to form an ensemble of base rankers. Such an ensemble of base rankers can be used to rank the documents or instances.

Claims

1. A method comprising:

creating instance pairs from a set of documents;

generating subsets of the instance pairs corresponding to rank pairs;

constructing a base ranker for each rank pair;

identifying ordering relationships between instances in the instance pairs; and

aggregating ranks by creating a list of base rankers.

2. The method of claim 1, wherein the creating instance pairs from the set of documents includes documents ranked based on relevancy.

3. The method of claim 2, wherein the documents are ranked based on a vector of features.

4. The method of claim 1, wherein the constructing a base ranker includes constructing base rankers for related to adjacent rank pairs.

5. The method of claim 1, wherein the identifying is performed for instance pairs bellowing to a particular subset.

6. The method of claim 1, wherein the aggregating includes examining the list of base rankers to assign scores in each instance based on positing on the list.

7. The method of claim 1 further comprising assigning weights to the based rankers, wherein the weights give importance to instances belonging to subsets having the base rankers.

8. The method of claim 1 performed for searching on the world wide web.

9. A method comprising:

combining a first and second document to form an instance pair;

creating a subset of the instance pair belonging to a rank pair; and

generating a based ranker from a subset of the instance pair and other instance pairs.

10. The method of claim 9, wherein the combining is performed for all documents in a set of documents, until all the documents in the set are selected and paired.

11. The method of claim 9, wherein combining is of documents having two different ranks.

12. The method of claim 9, wherein the creating includes associating similar subsets with other rank pairs by grouping the instance pair with other instance pairs.

13. The method of claim 9, wherein the generating the based ranker is for adjacent rank pairs.

14. A system comprising:

a processor;

a memory configured to the processor; and

a query processing module in the memory, processing a user query received to identify documents relevant to a user query by comparing the parameters gathered from the user query with a database of documents; and

a ranking module that receives the documents for ranking and identifies document pairs belonging to a rank pair and creates a subset including the document pairs.

15. The system of claim 14, wherein the query processing module further groups the documents into several groups.

16. The system of claim 14, wherein the ranking module further generates a base ranker from the document pairs in the subset.

17. The system of claim 14, wherein the ranking module further generates multiple rank pairs are created and base rankers are created for each rank pair.

18. The system of claim 14, wherein the ranking module further crates base rankers for adjacent rank pairs.

19. The system of claim 14 further comprising a rank aggregation module that processes subsets of instance pairs received from the ranking module.

20. The system of claim 19 further wherein the rank aggregation module includes a scoring module to aggregate the subsets of the instance pairs.