Information retrieval system

• US 8,037,043 B2
• Filed: 09/09/2008
• Issued: 10/11/2011
• Est. Priority Date: 09/09/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Snelson, Edward Lloyd, Zoeter, Onno, Szummer, Martin, Taylor, Michael J., Craswell, Nicholas, Guiver, John P.
• Primary Examiner(s): Coby; Frantz
• Application Number:
  US12/207,315
• Publication Number:
  US 20100076949A1
• Time in Patent Office: 1,127 Days
• Field of Search: 707705-709, 707/758, 707769-770
• US Class Current: 707/705
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

An information retrieval system is described for retrieving a list of documents such as web pages or other items from a document index in response to a user query. In an embodiment a prediction engine is used to predict both explicit relevance information such as judgment labels and implicit relevance information such as click data. In an embodiment the predicted relevance information is applied to a stored utility function that describes user satisfaction with a search session. This produces utility scores for proposed lists of documents. Using the utility scores one of the lists of documents is selected. In this way different sources of relevance information are combined into a single information retrieval system in a principled and effective manner which gives improved performance.

Claims

1. An information retrieval system comprising:

an input arranged to receive user query terms;

a processor arranged to generate a plurality of lists of documents using the query terms and by accessing a document index;

a prediction engine arranged to predict, for each of the lists of documents, implicit relevance information and explicit relevance information;

a utility engine arranged to calculate a utility score for each of the lists of documents using the predicted relevance information and a stored utility function;

the utility engine also being arranged to select and store one of the lists of documents on the basis of the utility scores.

2. An information retrieval system as claimed in claim 1 wherein the prediction engine is a machine learning system comprising a stored probabilistic model of the form p(y|x,a), and wherein the prediction engine is arranged to apply the model to give the probability p of observing y after selecting a when x is observed, where the symbol x represents inputs to the prediction engine, the symbol y represents outputs from the model being predicted relevance information, and the symbol a represents a list of documents.

3. An information retrieval system as claimed in claim 1 wherein the prediction engine comprises at least two independent modules, one arranged to predict explicit relevance information and one arranged to predict implicit relevance information.

4. An information retrieval system as claimed in claim 1 wherein the prediction engine is a machine learning system comprising a stored Bayesian generalized linear model comprising a plurality of model weights.

5. An information retrieval system as claimed in claim 1 wherein the prediction engine comprises:

a judgment model arranged to predict for each document in a ranked list of documents, a relevance judgment; and

a click model arranged to predict for each document in a ranked list of documents, a click event.

6. An information retrieval system as claimed in claim 5 wherein the click model is arranged to take as input document specific features.

7. An information retrieval system as claimed in claim 6 wherein the click model is also arranged to take as input query related identifiers.

8. An information retrieval system as claimed in claim 1 wherein the utility engine comprises a stored utility function which is related to the discounted cumulative gain metric.

9. An information retrieval system as claimed in claim 1 wherein the utility engine comprises a stored utility function component which takes into account only predicted click events.

10. An information retrieval system as claimed in claim 1 wherein the utility engine comprises a stored utility function component which takes into account only predicted judgments.

11. An information retrieval system as claimed in claim 1 wherein the utility engine comprises a stored utility function comprising a first component which takes into account only predicted implicit relevance information and a second component which takes into account only predicted explicit relevance information and where those two components are combined using a specified parameter.

12. An information retrieval system as claimed in claim 9 wherein the utility function component incorporates a concave function in order to encourage diversity in the selected list of documents.

13. An information retrieval system as claimed in claim 12 wherein the prediction engine comprises a stored model which is arranged to model correlations between click events.

14. A computer-implemented method of retrieving a ranked list of documents from an index of documents comprising

receiving at least one query term;

generating a plurality of lists of documents from the index using the query term;

predicting, for each of the lists of documents, implicit relevance information and explicit relevance information;

calculating a utility score for each of the lists of documents using the predicted relevance information and a stored utility function;

selecting and storing one of the lists of documents on the basis of the utility scores.

15. A computer-implemented method as claimed in claim 14 which comprises using a machine learning system comprising a stored probabilistic model of the form p(y|x,a) to make the prediction by applying the model to give the probability p of observing y after selecting a when x is observed, where the symbol x represents inputs to the prediction engine, the symbol y represents outputs from the model being predicted relevance information, and the symbol a represents a list of documents.

16. A computer-implemented method as claimed in claim 15 which further comprises training the model using historical {x, y, a} triplet values.

17. A computer-implemented method as claimed in claim 16 which further comprises using a Bayesian generalized linear model comprising a plurality of weights and obtaining values for the weights as a result of the training process.

18. One or more device-readable media with device executable instructions for performing steps comprising:

receiving at least one query term being part of a request to retrieve a ranked list of documents from a document index;

generating a plurality of ranked lists of documents from the index using the query term;

using a machine learning system comprising a stored probabilistic model to predict, for each of the ranked lists of documents, implicit relevance information and explicit relevance information;

calculating a utility score for each of the ranked lists of documents using both the predicted implicit relevance information and the predicted explicit relevance information as well as a stored utility function;

selecting and storing one of the ranked lists of documents on the basis of the utility scores.

19. One or more device-readable media as claimed in claim 18 further comprising device-executable instructions for performing steps comprising:

training the stored probabilistic model using historical values.

20. One or more device-readable media as claimed in claim 18 further comprising device-executable instructions for performing steps comprising:

using a specified parameter to combine two components of the utility function, one of those components related to explicit relevance information and the other of those components related to implicit relevance information.