Training a search result ranker with automatically-generated samples

• US 8,060,456 B2
• Filed: 10/01/2008
• Issued: 11/15/2011
• Est. Priority Date: 10/01/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Kuansan, Gao, Jianfeng
• Primary Examiner(s): Holmes; Michael B
• Application Number:
  US12/243,359
• Publication Number:
  US 20100082510A1
• Time in Patent Office: 1,140 Days
• Field of Search: 706/12
• US Class Current: 706/12
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A search result ranker may be trained with automatically-generated samples. In an example embodiment, user interests are inferred from user interactions with search results for a particular query so as to determine respective relevance scores associated with respective query-identifier pairs of the search results. Query-identifier-relevance score triplets are formulated from the respective relevance scores associated with the respective query-identifier pairs. The query-identifier-relevance score triplets are submitted as training samples to a search result ranker. The search result ranker is trained as a learning machine with multiple training samples of the query-identifier-relevance score triplets.

Claims

1. One or more processor-accessible tangible media comprising processor-executable instructions for training a search result ranker, wherein the processor-executable instructions, when executed, direct a system to perform acts comprising:

inferring user interests from user interactions with search results for a particular query, the search results including identifiers that comprise uniform resource locators (URLs);

determining respective relevance scores associated with respective query-identifier pairs of the search results, each respective relevance score comprising a respective probability of the respective identifier being skipped by a user;

formulating query-identifier-relevance score triplets from the respective relevance scores associated with the respective query-identifier pairs;

submitting the query-identifier-relevance score triplets as training samples to a search result ranker; and

training the search result ranker as a learning machine with multiple training samples comprising the query-identifier-relevance score triplets.

2. The one or more processor-accessible tangible media as recited in claim 1, wherein the user interactions comprise one or more of:

identifier selection, dwell time on an item corresponding to a selected identifier, viewing of an identifier of a search result, or skipping an identifier of a search result.

3. The one or more processor-accessible tangible media as recited in claim 1, wherein the acts of inferring and determining comprise:

automatically determining relevance scores from the user interactions without manual label relevance input from users.

4. A method implemented by a system for training a search result ranker, the method comprising acts of:

inferring user interests from user interactions with search results for a particular query to determine respective relevance scores associated with respective query-identifier pairs of the search results;

formulating query-identifier-relevance score triplets from the respective relevance scores associated with the respective query-identifier pairs;

submitting the query-identifier-relevance score triplets as training samples to a search result ranker; and

training the search result ranker as a learning machine with multiple training samples comprising the query-identifier-relevance score triplets.

5. The method as recited in claim 4, further comprising:

employing the trained search result ranker to rank different search results for new queries.

6. The method as recited in claim 4, further comprising:

repeatedly acquiring and applying new training samples derived from other queries to automatically train the search result ranker.

7. The method as recited in claim 4, wherein the act of inferring comprises:

automatically determining relevance scores from the user interactions without manual label relevance input from users.

8. The method as recited in claim 4, further comprising:

providing the search results for the particular query, the search results including multiple query-identifier pairs; and

monitoring the user interactions with the query-identifier pairs of the search results for the particular query.

9. The method as recited in claim 4, wherein the user interactions comprise one or more of:

identifier selection, dwell time on an item corresponding to a selected identifier, viewing of an identifier of a search result, or skipping an identifier of a search result.

10. The method as recited in claim 4, wherein the relevance scores comprise one or more of:

click-through rate, average dwell time, or probability of being skipped.

11. The method as recited in claim 4, wherein each identifier comprises a uniform resource locator (URL);

and wherein the method further comprises;

monitoring the user interactions with the query-identifier pairs of the search results remotely over an internet.

12. The method as recited in claim 4, wherein the act of training comprises:

mathematically minimizing an error function that represents a current error level between determined relevance scores and relevance scores output by the learning machine.

13. The method as recited in claim 4, wherein the search result ranker comprises a neural network.

14. A system that is capable of training a search result ranker, the system comprising:

a relevance score determiner to infer user interests from user interactions with search results for a particular query and to determine respective relevance scores associated with respective query-identifier pairs of the search results;

a training sample handler to formulate query-identifier-relevance score triplets from the respective relevance scores associated with the respective query-identifier pairs and to submit the query-identifier-relevance score triplets as training samples to a learning machine; and

a search result ranker to be trained as the learning machine with multiple training samples comprising the query-identifier-relevance score triplets.

15. The system as recited in claim 14, further comprising:

a user interaction unit to monitor the user interactions with the query-identifier pairs of the search results for the particular query remotely by receiving information from an instrumented browser.

16. The system as recited in claim 14, wherein the search result ranker comprises a two-layer neural network.

17. The system as recited in claim 14, wherein the system is to train the search result ranker by learning a weighting vector.

18. The system as recited in claim 17, wherein the system is to train the search result ranker by at least reducing distances between (i) respective estimated relevance scores inferred by the relevance score determiner and (i) respective output values of the learning machine.

19. The system as recited in claim 14, wherein the relevance score determiner is further to implicitly infer the user interests from the user interactions automatically without manual label relevance input from users.

20. The system as recited in claim 14, wherein the relevance score determiner is further to retrieve the user interactions from one or more query session logs.