Information Retrieval and Ranking

• US 20090037401A1
• Filed: 07/31/2007
• Published: 02/05/2009
• Est. Priority Date: 07/31/2007
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Xu, Jun, Li, Hang
• Application Number:
  US11/831,836
• Publication Number:
  US 20090037401A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence

Abstract

A learning method is used to generate ranking models. The learning method can create a ranking function that assigns scores to documents and then ranks the documents using the scores. In this learning method, a training set along with performance measures are used to generate weak rankers which a used in the ranking model. During information retrieval, for a given query, the system may return a ranked list of documents in descending order of the relevance scores.

Claims

1. A method comprising:

fetching training data;

fetching one or more parameters that include performance measures as applied to the training data;

creating a weak ranker based on the performance parameters;

assigning a weight to the weak ranker; and

determining whether additional weak rankers are to be created.

2. The method of claim 1, wherein the fetching training data includes a set of query elements, a set of retrieved documents corresponding to each of the query elements, and pre-calculated relevance scores for the retrieved documents.

3. The method of claim 1, wherein the fetching one or more parameters includes performance parameters represented by a permutation created using a ranking function on a set of documents and user defined relevance scores.

4. The method of claim 1, wherein the creating the weak ranker is constructed with the training data having a weight distribution, and goodness of the weak ranker is measured by a performance measured weighted by the weight distribution.

5. The method of claim 1, wherein assigning a weak ranker weight is defined by the equation:

${\mathrm{\alpha <br><br>}}_t=\frac{1}{2}·<br><br>\ln <br><br>\frac{\underset{i=1}{\overset{m}{\sum <br><br>}}<br><br>P_t<br><br>\left(i\right)<br><br>\left\{1+E<br><br>\left(\mathrm{\pi <br><br>}<br><br>\left(q_i,d_i,h_t\right),y_i\right)\right\}}{\underset{i=1}{\overset{m}{\sum <br><br>}}<br><br>P_t<br><br>\left(i\right)<br><br>\left\{1-E<br><br>\left(\mathrm{\pi <br><br>}<br><br>\left(q_i,d_i,h_t\right),y_i\right)\right\}}$

6. The method of claim 1 further updating a ranking model after each iteration of rounds of creating weak rankers.

7. The method of claim 6, wherein the updating is performed by linearly combining the weak rankers.

8. The method of claim 6, further comprising updating distribution weights of the training data after each iteration.

9. The method of claim 1 as applied to information retrieval, wherein the information retrieval is directed to one of the following:

document retrieval, collaborative filtering, key term, extraction, or expert filtering.

10. The method of claim 1 as applied to natural language processing, wherein the natural language processing is directed to one of the following:

machine translation, paraphrasing, and sentiment analysis.

11. A method used in a ranking model comprising:

inputting a user query;

retrieving documents relevant to the user query;

generating a ranking model to rank the documents, wherein the ranking model is based on performance measures and the ranking model minimizes loss function and the performance measures; and

arranging the ranked documents in an index.

12. The method of claim 11, wherein the inputting is from one or more client computing devices.

13. The method of claim 11, wherein the retrieving is from distributed locations in a network.

14. The method of claim 11, wherein the generating the ranking model includes an exponential loss function.

15. The method of claim 11, wherein the generating the ranking module includes a loss function based on information retrieval performance measures.

16. A computing device comprising:

a processor;

a memory configured to the processor; and

a ranking module in the memory, implementing a learning method to generate a ranking model, wherein the learning method constructs weak rankers based on weighted training data and combines the weak rankers to generate the ranking model.

17. The computing device of claim 16, wherein weighted training data is adapted iteratively using weights in accordance with a pre-defined output.

18. The computing device of claim 16, wherein the training data includes arbitrary query elements, retrieved documents corresponding to the query elements, and user defined relevance levels to the retrieved documents.

19. The computing device of claim 16, wherein the training data is re-weighted after weak rankers are constructed.

20. The computing device of claim 16 further comprising a search module in the memory, to receive queries as input.