LEARNING A DOCUMENT RANKING FUNCTION USING QUERY-LEVEL ERROR MEASUREMENTS

• US 20070233679A1
• Filed: 04/03/2006
• Published: 10/04/2007
• Est. Priority Date: 04/03/2006
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Liu, Tie-Yan, Qin, Tao
• Application Number:
  US11/278,508
• Publication Number:
  US 20070233679A1
• 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/9535 Search customisation based on user profiles and personalisation

Abstract

A method and system for learning a ranking function that uses a normalized, query-level error function is provided. A ranking system learns a ranking function using training data that includes, for each query, the corresponding documents and, for each document, its relevance to the corresponding query. The ranking system uses an error calculation algorithm that calculates an error between the actual relevances and the calculated relevances for the documents of each query. The ranking system normalizes the errors so that the total errors for each query will be weighted equally. The ranking system then uses the normalized error to learn a ranking function that works well for both queries with many documents in their search results and queries with few documents in their search results.

Claims

1. A computer system for generating a document ranking function, comprising:

a training store that contains, for each of a plurality of queries, features of documents corresponding to the query, and an actual relevance of each document to the query;

a error calculation component that calculates a normalized error between the actual relevances and calculated relevances of documents corresponding to a query; and

a training component that trains a ranking function using the normalized errors as calculated by the error calculation component to indicate accuracy of the ranking function in generating relevances of the documents to their corresponding queries.

2. The computer system of claim 1 wherein the normalized error for a query is independent of the number of documents corresponding to a query.

3. The computer system of claim 2 wherein the normalized error is represented as follows:

$J<br><br>\left(g<br><br>\left(q\right),H<br><br>\left(q\right)\right)=-\cos <br><br>\left(g<br><br>\left(q\right),H<br><br>\left(q\right)\right)=-\frac{g<br><br>{\left(q\right)}^T<br><br>H<br><br>\left(q\right)}{<br><br>g<br><br>\left(q\right)<br><br><br><br><br><br>H<br><br>\left(q\right)<br><br>}$

where J(g(q),H(q)) represents the normalized error for query q, g(q) represents a vector of actual relevances for the document corresponding to query q, H(q) represents a vector of calculated relevances for the document corresponding to query q, and ∥

∥

is the L-2 norm of a vector.

4. The computer system of claim 2 wherein the normalized error is based on an angle between a vector representing the actual relevances and the calculated relevances as represented in an n(q)-dimensional space where n(q) is the number of documents corresponding to query q.

5. The computer system of claim 1 wherein the training component trains the ranking function using an adaptive boosting algorithm.

6. The computer system of claim 5 wherein the adaptive boosting algorithm selects at each iteration a weak learner that when combined with previously selected weak learners results in an aggregate normalized error that is smallest.

7. The computer system of claim 6 wherein the adaptive boosting algorithm calculates a contribution weight for each weak learner that indicates contribution of the relevances of that weak learner relative to the other weak learners of the ranking function.

8. The computer system of claim 5 wherein the adaptive boosting algorithm calculates a query weight that indicates the weight to be accorded to the actual relevances of each query when selecting the next weak learner.

9. A computer system for calculating an error between actual relevances and training relevances of groups of documents, comprising:

a group error calculation component that calculates an error between the actual relevances and calculated relevances of documents of the group, the error being independent of the number of documents in the group; and

an overall error calculation component that aggregates the errors of the groups into an overall error for the groups of documents.

10. The computer system of claim 9 wherein the calculated relevances are calculated by a ranking function that ranks the relevance of each document of a group to the group.

11. The computer system of claim 9 wherein a user provides the actual relevance of a document to a group.

12. The computer system of claim 9 wherein each group corresponds to a query and the documents of the group are from a search result of the query.

13. The computer system of claim 12 wherein the normalized error is represented as follows:

$J<br><br>\left(g<br><br>\left(q\right),H<br><br>\left(q\right)\right)=-\cos <br><br>\left(g<br><br>\left(q\right),H<br><br>\left(q\right)\right)=-\frac{g<br><br>{\left(q\right)}^T<br><br>H<br><br>\left(q\right)}{<br><br>g<br><br>\left(q\right)<br><br><br><br><br><br>H<br><br>\left(q\right)<br><br>}$

where J(g(q),H(q)) represents the normalized error for query q, g(q) represents a vector of actual relevances for the documents corresponding to query q, H(q) represents a vector of calculated relevances for the documents corresponding to query q, and ∥

∥

is the L-2 norm of a vector.

14. The computer system of claim 12 wherein the normalized error is based on an angle between a vector representing the actual relevances and the calculated relevances as represented in an n(q)-dimensional space where n(q) is the number of documents corresponding to query q.

15. The computer system of claim 9 including a training component that learns a ranking function to rank relevance of documents to groups using an adaptive boosting algorithm that selects at each iteration a weak learner that when combined with previously selected weak learners results in an aggregate error that is smallest.

16. The computer system of claim 15 wherein the adaptive boosting algorithm calculates a combination weight for each weak learner that indicates contribution of the relevances of that weak learner relative to the other weak learners of the ranking function.

17. The computer system of claim 15 wherein the adaptive boosting algorithm calculates a group weight that indicates the weight to be accorded to the actual relevances of each group when selecting the next weak learner.

18. A computer system for ranking web pages, comprising:

a search store that contains a search result of a query conducted by a search engine service, the search result identifying web pages relevant to the query; and

a web page ranking component that ranks web pages of the search result based on relevance to the query, the web page ranking component having been trained using a normalized query-level error measurement.

19. The computer system of claim 18 wherein the web page ranking component has been trained using the normalized query-level error measurements to guide selection of weak learners for an adaptive boosting algorithm.

20. The computer system of claim 19 wherein the normalized query-level error is based on an angle between a vector representing actual relevances and calculated relevances of web pages to their corresponding query as represented in an n(q)-dimensional space where n(q) is the number of web pages corresponding to query q.