Method and apparatus for machine learning a document relevance function

• US 7,197,497 B2
• Filed: 04/25/2003
• Issued: 03/27/2007
• Est. Priority Date: 04/25/2003
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Overture Services Incorporated (Apollo Global Management, Inc.)
• Inventors: Cossock, David
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Black; Linh
• Application Number:
  US10/424,170
• Publication Number:
  US 20040215606A1
• Time in Patent Office: 1,432 Days
• Field of Search: 707 1-1041
• 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: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Provided is a method and computer program product for determining a document relevance function for estimating a relevance score of a document in a database with respect to a query. For each of a plurality of test queries, a respective set of result documents is collected. For each test query, a subset of the documents in the respective result set is selected, and a set of training relevance scores is assigned to documents in the subset. In one embodiment, at least some of the training relevance scores are assigned by human subjects who determine individual relevance scores for submitted documents with respect to the corresponding queries. Finally, a relevance function is determined based on the plurality of test queries, the subsets of documents, and the sets of training relevance scores.

Claims

1. A method for determining a document relevance function for estimating a relevance score of a document in a database with respect to a query, comprising:

(a) collecting a respective result set of documents from the database for each of a plurality of test queries;

(b) for each test query of the plurality of test queries, selecting a subset of the documents in the respective result set; and

assigning a set of training relevance scores to the documents in the subset; and

(c) determining a relevance function based on the plurality of test queries, the subsets of documents, and the sets of training relevance scores;

(d) outputting a list of one or more documents ordered based on the determined relevance function.

2. The method of claim 1, wherein a document ranking function is determined based at least in part on the determined relevance function, the document ranking function:

receiving a set of documents from the database;

receiving a query; and

outputting an ordered list of the set of documents, the list ordered so that the document in the set having the highest relevance score, as determined by the relevance function, is the first document on the list.

3. The method of claim 1, wherein the plurality of test queries are selected by:

sampling, from logs of queries submitted by users to a search engine, a preliminary set of query strings;

eliminating from the preliminary set queries determined to be outside the scope of knowledge of a user base; and

assigning remaining queries in the preliminary set to the plurality of test queries.

4. The method of claim 1, wherein the plurality of test queries are selected by:

sampling words from a lexicon of one-word entries; and

assigning each of the words so sampled to the plurality of test queries.

5. The method of claim 4, wherein selecting the plurality of test queries further comprises:

selecting combinations of two or more words sampled from the lexicon and assigning the combinations to the plurality of test queries.

6. The method of claim 1, wherein selecting a subset comprises:

for each test query, selecting a document from the respective result set, determining a surrogate relevance score relating the selected document to the current query, and assigning the selected document to at least one relevance tier of a plurality of relevance tiers based on the determined surrogate relevance score; and

repeating the document selecting step until each relevance tier contains at least a respective predefined number of documents.

7. The method of claim 6, wherein assigning the selected document comprises assigning the selected document to each tier in the plurality of relevance tiers for which the surrogate relevance score is greater than a respective predetermined threshold value of the tier.

8. The method of claim 6, wherein assigning the selected document comprises assigning the selected document to a tier in the plurality of relevance tiers for which the surrogate relevance score falls within a respective predetermined range of relevance scores associated with the tier.

9. The method of claim 8, wherein the respective predetermined ranges of relevance scores associated with the plurality of tiers are nonoverlapping.

10. The method of claim 6, wherein determining a surrogate relevance score comprises:

submitting the query to a search engine; and

determining the surrogate relevance score as a function of a position of the document in a list of result pages provided by the search engine.

11. The method of claim 6, wherein assigning a set of training relevance scores comprises:

submitting each of a first plurality of documents in the subset to a plurality of human subjects, wherein the first plurality of documents have surrogate relevance scores within a predefined range, one or more human subjects determining an individual relevance score for each submitted document with respect to the query; and

assigning a training relevance score to each submitted document with respect to the query based on the individual relevance scores determined by the human subjects.

12. The method of claim 11, wherein the individual relevance scores are numbers selected from a predetermined range and said assigning comprises computing an arithmetic mean of the individual relevance scores.

13. The method of claim 11, further including assigning to each of a second plurality of documents in the subset a training relevance score based on the surrogate relevance score determined for the document.

14. The method of claim 6, wherein determining a surrogate relevance score for the selected document comprises:

submitting the query to a plurality of search engines, each search engine returning a respective list of result pages from the database, each respective list of result pages including the selected document; and

determining the surrogate relevance score in accordance with an average numerical position of the selected document in the lists of result pages.

15. The method of claim 1, wherein assigning a set of training relevance scores comprises:

submitting each of a first plurality of documents in the subset to a respective plurality of human subjects, each human subject in the respective plurality of human subject determining an individual relevance score for the submitted document with respect to the query; and

assigning a training relevance score to each submitted document with respect to the query based on the individual relevance scores determined by the human subjects.

16. The method of claim 15, wherein the individual relevance scores are numbers selected from a predetermined range and said assigning comprises computing an arithmetic mean of the individual relevance scores.

17. The method of claim 15, further including assigning to each of a second plurality of documents in the subset a predefined low training relevance score.

18. The method of claim 1, wherein determining a relevance function comprises:

determining a set of features to be used as predictor variables in the construction of the relevance function, each of the features in the set comprising a function of one or more properties of a respective document, a respective query, or both;

parameterizing the relevance function in terms of a finite set of parameters and base functions, wherein each base function takes as its input a subset of said features and outputs a value;

defining a partial error relating the training relevance score of a given document with respect to a particular query to a value produced by the document relevance function as applied to the given document with respect to the particular query;

repeating the defining a partial error with respect to a plurality of given documents and a plurality of particular queries so as to produce a set of partial errors; and

selecting the parameters so as to minimize a total error, wherein the total error is a function of the set of partial errors.

19. The method of claim 18, wherein the set of features includes at least one query-dependent feature and at least one query-independent feature.

20. The method of claim 18, wherein the set of features includes at least one of the following:

Eignenrank (ER), Hub, URL Depth, Quality Score, Spam Index, Family Friendliness, Document Length, Anchor Text Score, Match Location, Match Frequency, Term Weight, and Proximity.

21. The method of claim 18, wherein the set of features includes at least four of the following:

Eigenrank (ER), Hub, URL Depth, Quality Score, Spam Index, Family Friendliness, Document Length, Anchor Text Score, Match Location, Match Frequency, Term Weight, and Proximity.

22. The method of claim 18, wherein defining a partial error further comprises:

defining a set of classes;

assigning the given document to one or more of the classes based, at least in part, on the training relevance score of the given document.

23. The method of claim 22, wherein the partial error is determined at least in part by a ratio, the ratio being a ratio of the relevance function to a difference, the difference being a difference between one and the relevance function.

24. The method of claim 18, wherein the partial error is defined to be a function of the square of a difference between the training relevance score of a document and a value produced by the document relevance function.

25. The method of claim 18, wherein the partial error is defined to be a function of the absolute value of a difference between the training relevance score of a document and a value produced by the document relevance function.

26. The method of claim 18, wherein at least one of the base functions is a node classification tree and the finite set of parameters include associated splitting variables, splitting locations, and terminal node values.

27. The method of claim 18, wherein selecting the parameters so as to minimize a total error is accomplished via a Boost procedure.

28. The method of claim 18, wherein selecting the parameters so as to minimize a total error is accomplished via a GradientBoost procedure, and wherein the base functions include at least one classification and regression tree (CART).

29. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism therein, the computer program mechanism comprising:

(a) a collecting module for collecting a respective result set of documents from the database for each of a plurality of test queries;

(b) a sampling module for selecting, for each test query of the plurality of test queries, a subset of the documents in the respective result set;

(c) a scoring module for assigning a set of training relevance scores to the documents in each selected subset; and

(d) a relevance function generation module for determining a relevance function based on the plurality of test queries, the subsets of documents, and the sets of training relevance scores.

30. The computer program product of claim 29, wherein the relevance function generation module further includes instructions for determining a document ranking function based at least in part on the determined relevance function, the document ranking function:

receiving a set of documents from the database;

receiving a query; and

outputting an ordered list of the set of documents, the list ordered so that the document in the set having the highest relevance score, as determined by the relevance function, is the first document on the list.

31. The computer program product of claim 29, wherein the collecting module includes instructions for generating the plurality of test queries by:

sampling, from logs of queries submitted by users to a search engine, a preliminary set of query strings;

eliminating from the preliminary set queries determined to be outside the scope of knowledge of a user base; and

assigning remaining queries in the preliminary set to the plurality of test queries.

32. The computer program product of claim 29, wherein the collecting module includes instructions for generating the plurality of test queries by:

sampling words from a lexicon of one-word entries; and

assigning each of the words so sampled to the plurality of test queries.

33. The computer program product of claim 32, wherein the collecting module further includes instructions for:

selecting combinations of two or more words sampled from the lexicon and assigning the combinations to the plurality of test queries.

34. The computer program product of claim 29, wherein the sampling module includes instructions for:

for each test query, selecting a document from the respective result set, determining a surrogate relevance score relating the selected document to the current query, and assigning the selected document to at least one relevance tier of a plurality of relevance tiers based on the determined surrogate relevance score; and

repeating the document selecting step until each relevance tier contains at least a respective predefined number of documents.

35. The computer program product of claim 34, wherein the sampling module further includes instructions for:

assigning the selected document to each tier in the plurality of relevance tiers for which the surrogate relevance score is greater than a respective predetermined threshold value of the tier.

36. The computer program product of claim 34, wherein the sampling module further includes instructions for:

assigning the selected document to a tier in the plurality of relevance tiers for which the surrogate relevance score falls within a respective predetermined range of relevance scores associated with the tier.

37. The computer program product of claim 36, wherein the respective predetermined ranges of relevance scores associated with the plurality of tiers are nonoverlapping.

38. The computer program product of claim 34, wherein the sampling module further includes instructions for:

for each test query, submitting the query to a search engine; and

determining the surrogate relevance score of a document in the subset as a function of a position of the document in a list of result pages provided by the search engine.

39. The computer program product of claim 34, wherein the scoring module includes instructions for:

submitting each of a first plurality of documents in the subset to a plurality of human subjects, wherein the first plurality of documents have surrogate relevance scores within a predefined range, each human subject determining an individual relevance score for the submitted document with respect to the query; and

assigning a training relevance score to each submitted document with respect to the query based on the individual relevance scores determined by the human subjects.

40. The computer program product of claim 39, wherein the individual relevance scores are numbers selected from a predetermined range and said assigning comprises computing an arithmetic mean of the individual relevance scores.

41. The computer program product of claim 39, wherein the scoring module further includes instructions for:

assigning to each of a second plurality of documents in the subset a training relevance score based on the surrogate relevance score determined for the document.

42. The computer program product of claim 34, wherein the sampling module further includes instructions for determining a surrogate relevance score relating the selected document to the current query by:

submitting the query to a plurality of search engines, each search engine returning a respective list of result pages from the database, each respective list of result pages including the selected document; and

determining the surrogate relevance score in accordance with an average numerical position of the selected document in the lists of result pages.

43. The computer program product of claim 29, wherein the scoring module includes instructions for:

submitting each of a first plurality of documents in each selected subset to a plurality of human subjects, each human subject determining an individual relevance score for the submitted document with respect to the query; and

assigning a training relevance score to each submitted document with respect to the query based on the individual relevance scores determined by the human subjects.

44. The computer program product of claim 43, wherein the individual relevance scores are numbers selected from a predetermined range and said assigning comprises computing an arithmetic mean of the individual relevance scores.

45. The computer program product of claim 43, wherein the scoring module further includes instructions for:

assigning to each of a second plurality of documents each selected subset a predefined low training relevance score.

46. The computer program product of claim 29, wherein the determining module includes instructions for:

parameterizing the relevance function in terms of a finite set of parameters and base functions, wherein each base function outputs a value for a respective input set of features, each feature comprising a function of one or more properties of a respective document, a respective query, or both;

defining a partial error relating the training relevance score of a given document with respect to a particular query to a value produced by the document relevance function as applied to the given document with respect to the particular query;

repeating the defining a partial error with respect to a plurality of given documents and a plurality of particular queries so as to produce a set of partial errors; and

selecting the parameters so as to minimize a total error, wherein the total error is a function of the set of partial errors.

47. The computer program product of claim 46, wherein the set of features includes at least one query-dependent feature and at least one query-independent feature.

48. The computer program product of claim 46, wherein the set of features includes at least one of the following:

Eignenrank (ER), Hub, URL Depth, Quality Score, Spam Index, Family Friendliness, Document Length, Anchor Text Score, Match Location, Match Frequency, Term Weight, and Proximity.

49. The computer program product of claim 46, wherein the set of features includes at least four of the following:

Eignenrank (ER), Hub, URL Depth, Quality Score, Spam Index, Family Friendliness, Document Length, Anchor Text Score, Match Location, Match Frequency, Term Weight, and Proximity.

50. The computer program product of claim 46, wherein the determining module further includes instructions for:

defining a set of classes;

assigning the given document to one or more of the classes based, at least in part, on the training relevance score of the given document.

51. The computer program product of claim 50, wherein the determining module further includes instructions for:

defining the partial error, the partial error defined at least in part by a ratio, the ratio being a ratio of the relevance function to a difference, the difference being a difference between one and the relevance function.

52. The computer program product of claim 46, wherein the determining module further includes instructions for:

defining the partial error to be a function of the square of a difference between the training relevance score of a document and a value produced by the document relevance function.

53. The computer program product of claim 46, wherein the determining module further includes instructions for:

defining the partial error to be a function of the absolute value of a difference between the training relevance score of a document and a value produced by the document relevance function.

54. The computer program product of claim 46, wherein at least one of the base functions is a node classification tree and the finite set of parameters include associated splitting variables, splitting locations, and terminal node values.

55. The computer program product of claim 46, wherein the determining module further includes instructions for:

selecting the parameters so as to minimize a total error is accomplished via a Boost procedure.

56. The computer program product of claim 46, wherein the determining module includes instructions for:

parameterizing the relevance function in terms of at least one classification and regression tree (CART); and

selecting the parameters so as to minimize a total error is accomplished via a GradientBoost procedure.