IDENTIFICATION OF SAMPLE DATA ITEMS FOR RE-JUDGING

• US 20100318540A1
• Filed: 06/15/2009
• Published: 12/16/2010
• Est. Priority Date: 06/15/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Middha, Bhuvan, Svore, Krysta M., Burges, Christopher J.C., Abib, Elbio Renato Torres
• Granted Patent: US 8,935,258 B2
• Time in Patent Office: Days
• US Class Current: 707/759
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9566 URL specific, e.g. using aliases, detecting broken or misspelled links
• CPC Class Codes: G06F 18/2148 characterised by the process organisation or structure, e.g. boosting cascade

Abstract

Described is a technology for identifying sample data items (e.g., documents corresponding to query-URL pairs) having the greatest likelihood of being mislabeled when previously judged, and selecting those data items for re-judging. In one aspect, lambda gradient scores (information associated with ranked sample data items that indicates a relative direction and how “strongly” to move each data item for lowering a ranking cost) are summed for pairs of sample data items to compute re-judgment scores for each of those sample data items. The re-judgment scores indicate a relative likelihood of mislabeling. Once the selected sample data items are re-judged, a new training set is available, whereby a new ranker may be trained.

Claims

1. In a computing environment, a method comprising, obtaining lambda gradient scores for sample data items, using the lambda gradient scores to compute re-judgment scores for the sample data items, and selecting sample items for re-judging based upon the re-judgment score associated with each sample item.

2. The method of claim 1 wherein obtaining the lambda gradient scores comprises training a plurality of rankers, determining a best ranker of the plurality, and using the lambda gradient scores associated with that best ranker to compute the re-judgment scores.

3. The method of claim 2 wherein training the plurality of rankers comprises using LambdaRank training.

4. The method of claim 2 wherein training the plurality of rankers comprises using RankNet training.

5. The method of claim 1 wherein selecting the sample items for re-judging comprises sorting the data items based upon their re-judgment scores.

6. The method of claim 1 wherein selecting the sample items for re-judging comprises applying a user-provided threshold to select a subset of the data items based upon their re-judgment scores.

7. The method of claim 1 wherein obtaining the lambda gradient scores for the sample data items comprises using a normalized discounted cumulative gain cost function.

8. The method of claim 1 wherein obtaining the lambda gradient scores for the sample data items comprises using a discounted cumulative gain cost function, a mean average precision cost function, a mean reciprocal rank cost function, a Q-measure cost function or a generalized average precision cost function

9. The method of claim 1 wherein using the lambda gradient scores to compute re-judgment scores for the sample data items comprises summing the lambda gradient scores associated with a pair of data samples.

10. The method of claim 1 wherein using the lambda gradient scores to compute re-judgment scores for the sample data items comprises summing the absolute values of the lambda gradient scores associated with a pair of data samples.

11. The method of claim 1 wherein the selected sample items are re-judged to provide new training data, and further comprising, generating a new ranker using the re-judged data.

12. The method of claim 11 further comprising determining whether to use the new ranker based on evaluating the new ranker against a test set.

13. In a computing environment, a system comprising, a re-judging identification mechanism that computes re-judgment scores for sample data items based upon lambda gradient scores for the sample data items and identifies sample data items to re-judge based upon the re-judgment scores, and a ranker training mechanism that trains a ranker based upon a training set that includes sample data items that were re-judged based upon their identification by the re-judging identification mechanism.

14. The system of claim 13 wherein the ranker training mechanism is based on LambdaRank training.

15. The system of claim 13 wherein the ranker training mechanism is based on RankNet training.

16. The system of claim 13 wherein the sample data items comprise documents, and wherein the re-judging identification mechanism computes the re-judgment scores by summing the lambda gradient scores associated with a pair of documents.

17. One or more computer-readable media having computer-executable instructions, which when executed perform steps, comprising, computing re-judgment scores for documents, including by summing lambda gradient scores for pairs of documents, and selecting documents for re-judging based upon the re-judgment score associated with each sample item.

18. The one or more computer-readable media of claim 17 wherein selecting the sample items for re-judging comprises sorting the data items based upon their re-judgment scores, and applying a user-provided threshold to select a subset of the data items based upon their sort order.

19. The one or more computer-readable media of claim 17 wherein the selected sample items are re-judged to provide new training data, and having further computer-executable instructions comprising, generating a new ranker using the re-judged data.

20. The one or more computer-readable media of claim 19 having further computer-executable instructions comprising, determining whether to use the new ranker based on evaluating the new ranker against a test set.