LEARNING A DOCUMENT RANKING USING A LOSS FUNCTION WITH A RANK PAIR OR A QUERY PARAMETER

• US 20080027925A1
• Filed: 07/28/2006
• Published: 01/31/2008
• Est. Priority Date: 07/28/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Tie-Yan, Xu, Jun, Li, Hang, Cao, Yunbo
• Granted Patent: US 7,593,934 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

A method and system for generating a ranking function to rank the relevance of documents to a query is provided. The ranking system learns a ranking function from training data that includes queries, resultant documents, and relevance of each document to its query. The ranking system learns a ranking function using the training data by weighting incorrect rankings of relevant documents more heavily than the incorrect rankings of not relevant documents so that more emphasis is placed on correctly ranking relevant documents. The ranking system may also learn a ranking function using the training data by normalizing the contribution of each query to the ranking function so that it is independent of the number of relevant documents of each query.

Claims

1. A computer system for generating a ranking function to rank relevance of a document to a query, comprising:

a collection of queries, resultant documents, and relevance of each document to its query; and

a component that trains a ranking function using the documents and the relevances by weighting incorrect rankings of relevant documents more heavily than the incorrect ranking of not relevant documents so that the ranking function more correctly ranks relevant documents than it does not relevant documents.

2. The computer system of claim 1 including a component that uses the generated ranking function to rank the relevance of documents to a query.

3. The computer system of claim 1 including a component that generates training data from queries, documents, and relevances, the training data comprising feature vectors and labels, each feature vector being derived from a query and a resultant document, each label indicating correct ordering of relevance of a pair of resultant documents of a query.

4. The computer system of claim 1 wherein a different weighting is used for each rank pair where a rank pair represents a combination of two different relevance classifications.

5. The computer system of claim 4 wherein the relevance classifications are relevant, partially relevant, and irrelevant.

6. The computer system of claim 4 including a component that generates the weightings by comparing an evaluation measure of incorrect rankings of documents to an evaluation measure of correct rankings of the documents.

7. The computer system of claim 6 wherein the evaluation measure is selected from the group consisting of mean reciprocal rank, winner take all, mean average precision, and normalized discounted cumulative gain.

8. The computer system of claim 6 wherein the weighting is set to an average of differences between the evaluation measure of the correct rankings and the evaluation measure of the incorrect rankings.

9. The computer system of claim 1 wherein the component that trains the ranking function uses a gradient descent algorithm.

10. A computer system for generating a ranking function to rank relevance of a document to a query, comprising:

a collection of queries, resultant documents, and relevance of each document to its query; and

a component that trains a ranking function using the queries, resultant documents, and relevances by normalizing a contribution of each query to the ranking function by factoring in instance pairs of resultant documents of a query so that the contributions of queries are independent of the number of instance pairs of a query.

11. The computer system of claim 10 including a component that uses the generated ranking function to rank the relevance of documents to a query.

12. The computer system of claim 10 including a component that generates training data from queries, documents, and relevances, the training data comprising feature vectors and labels, each feature vector being derived from a query and a resultant document, each label indicating correct ordering of relevance of a pair of resultant documents of a query.

13. The computer system of claim 12 wherein each pair of documents includes documents from different relevance classifications.

14. The computer system of claim 13 wherein the relevance classifications are relevant, partially relevant, and irrelevant.

15. The computer system of claim 10 wherein the contribution of a query is inversely proportional to the number of instance pairs for the query to the maximum number of instance pairs of a query.

16. The computer system of claim 10 wherein the component that trains the ranking function weights incorrect rankings of relevant documents more heavily than the incorrect ranking of not relevant documents so that the ranking function more correctly ranks relevant documents than it does not relevant documents.

17. A computer system for ranking relevance of a document to a query, comprising:

a component that ranks relevance of a document to a query using feature weights to apply to features of the document, the feature weights being learned based on training data of features and relevances of documents to queries by weighting incorrect ranking of relevant documents more heavily than the incorrect ranking of not relevant documents so that relevant documents are more correctly ranked than not relevant documents;

a component that identifies features of resultant documents of a query; and

a component that provides the features of the resultant documents to the component that ranks the resultant documents of the query.

18. The computer system of claim 17 wherein the component that ranks learns feature weights by normalizing a contribution of each query by factoring into the contribution the number of relevant documents of a query so that a query with more relevant documents makes a contribution similar to a query with fewer relevant documents.

19. The computer system of claim 17 wherein an incorrect ranking of a relevant document as an irrelevant document is weighted more heavily than an incorrect ranking of a relevant document as a partially relevant document.

20. The computer system of claim 17 wherein the component that provides the features provides features for pairs of resultant documents.