Learning a document ranking using a loss function with a rank pair or a query parameter

• US 7,593,934 B2
• Filed: 07/28/2006
• Issued: 09/22/2009
• 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
• Primary Examiner(s): Mahmoudi; Tony
• Assistant Examiner(s): VO, CECILE H
• Application Number:
  US11/460,838
• Publication Number:
  US 20080027925A1
• Time in Patent Office: 1,152 Days
• Field of Search: 707 3- 7
• US Class Current: 1/1
• 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 processor; and

a memory for storing

a collection of queries, resultant documents, and relevance of each resultant document to its query, the collection being generated by submitting the queries to a search engine with search results for each query being the resultant documents for that query and inputting the relevance of each resultant document to its query; and

an application program for execution by the processor comprising;

a component that trains a ranking function using the resultant documents and their relevances by weighting incorrect rankings of relevant resultant documents more heavily than incorrect rankings of not relevant resultant documents so that the ranking function more correctly ranks relevant resultant documents than it does not relevant resultant documents, wherein a different weighting is used for each rank pair where a rank pair represents a combination of two different relevance classifications, the ranking function being trained by

for each resultant document, generating a feature vector of features for the resultant document,

for each query, generating ordered pairs of resultant documents with different relevances;

for each feature, initializing a current weighting parameter for the feature, the current weighting parameters forming the ranking function; and

modifying the current weighting parameters of the ranking function by iteratively applying the ranking function with current weighting parameters to the feature vectors of each pair of resultant documents and when the ranking for the resultant documents of a pair is in error, adjusting the weighting parameters by comparing an evaluation measure of incorrect rankings of documents to an evaluation measure of correct rankings of the documents, wherein the weighting is set to an average of differences between the evaluation measure of the correct ranking and the evaluation measure of the incorrect rankings, such that an error in ranking is weighted more heavily when a resultant document with a higher relevance is ranked incorrectly than when a resultant document with a lower relevance is ranked incorrectly; and

a component that ranks relevance of a document to a query that is not part of the collection

wherein the component that trains the ranking function uses a gradient descent algorithm.

2. 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.

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

4. The computer system of claim 1 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.

5. A computer-readable storage medium containing instructions for controlling a computing system to generate a ranking function to rank relevance of a document to a query, by a method comprising:

providing a collection of queries, resultant documents, and relevance of each resultant document to its query, the collection being generated by submitting the queries to a search engine with search results for each query being the resultant documents for that query and inputting the relevance of each resultant document to its query; and

training a ranking function using the resultant documents and their relevances by weighting incorrect rankings of relevant resultant documents more heavily than incorrect rankings of not relevant resultant documents so that the ranking function more correctly ranks relevant resultant documents than it does not relevant resultant documents, wherein a different weighting is used for each rank pair where a rank pair represents a combination of two different relevance classifications, the ranking function being trained by

for each resultant document, generating a feature vector of features for the resultant document,

for each query, generating ordered pairs of resultant documents with different relevances;

for each feature, initializing a current weighting parameter for the feature, the current weighting parameters forming the ranking function; and

modifying the current weighting parameters of the ranking function by iteratively applying the ranking function with current weighting parameters to the feature vectors of each pair of resultant documents and when the ranking for the resultant documents of a pair is in error, adjusting the weighting parameters by comparing an evaluation measure of incorrect rankings of documents to an evaluation measure of correct rankings of the documents, 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, such that an error in ranking is weighted more heavily when a resultant document with a higher relevance is ranked incorrectly than when a resultant document with a lower relevance is ranked incorrectly; and

ranking relevance of a document to a query that is not part of the collection

wherein the training of the ranking function uses a gradient descent algorithm.

6. The computer-readable storage medium of claim 5 including generating 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.

7. The computer-readable storage medium of claim 5 wherein the relevance classifications are relevant, partially relevant, and irrelevant.

8. The computer-readable storage medium of claim 5 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.