Evaluating the ranking quality of a ranked list

• US 9,449,078 B2
• Filed: 10/01/2008
• Issued: 09/20/2016
• Est. Priority Date: 10/01/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Wang, Kuansan, Walker, Toby H., Zheng, Zijian, Behr, Frederic H. Jr., Chen, Yu, Wang, Robert C.
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): MUELLER, KURT A
• Application Number:
  US12/243,937
• Publication Number:
  US 20100082566A1
• Time in Patent Office: 2,911 Days
• Field of Search: 707/713, 707/752
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3326 using relevance feedback from the user, e.g. relevance feedback on documents, documents sets, document terms or passages
• CPC Class Codes: G06F 16/38 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

The ranking quality of a ranked list may be evaluated. In an example embodiment, a method is implemented by a system to access log data, ascertain which entries of a ranked list are skipped, and determine a ranking quality metric from the skipped entries. More specifically, log data that reflects user interactions with a ranked list having multiple entries is accessed. The user interactions include at least indications of which of the multiple entries are selected entries. It is ascertained which entries of the multiple entries of the ranked list are skipped entries based on the selected entries. The ranking quality metric for the ranked list is determined responsive to the skipped entries.

Claims

1. One or more processor-accessible storage media comprising processor-executable instructions for evaluating a ranking quality of a ranked list, wherein the processor-executable instructions, when executed, direct a system to perform acts comprising:

accessing log data that reflects user interactions by a user with the ranked list, the ranked list having multiple entries;

determining, from the log data, that the multiple entries of the ranked list include viewed entries that have been viewed by the user and unviewed entries that have not been viewed by the user;

ascertaining, from the log data, that the viewed entries include skipped viewed entries that the user has skipped and selected viewed entries that the user has selected, wherein each of the skipped viewed entries and each of the selected viewed entries are ranked relatively higher in the ranked list than the unviewed entries and the skipped viewed entries are interspersed with the selected viewed entries in the ranked list;

determining a first number of the skipped viewed entries and a second number of the viewed entries including both the skipped viewed entries and the selected viewed entries;

determining a ranking quality metric for the ranked list using the first number of the skipped viewed entries and the second number of the viewed entries; and

using the ranking quality metric to tune a search application,

wherein the skipped viewed entries include partially skipped viewed entries and fully skipped viewed entries, and

the ascertaining comprises using dwell times to identify the partially skipped viewed entries.

2. The one or more processor-accessible storage media as recited in claim 1, wherein the ranking quality metric reflects a probability of an individual entry of the multiple entries being skipped by the user reviewing the ranked list.

3. The one or more processor-accessible storage media as recited in claim 1, wherein the ranked list is ranked based on relevance to a query submitted by the user.

4. A system comprising:

at least one processing unit; and

at least one tangible media storing executable instructions which, when executed by the at least one processing unit, cause the at least one processing unit to;

access log data that reflects user interactions by a user with a ranked list, the ranked list having multiple entries;

ascertain, from the log data, that the multiple entries of the ranked list include viewed entries that have been viewed by the user and unviewed entries that have not been viewed by the user;

ascertain, from the log data, that the viewed entries include skipped viewed entries that the user has skipped and selected viewed entries that the user has selected, wherein the skipped viewed entries include partially skipped viewed entries and fully skipped viewed entries, the partially skipped viewed entries being identified using dwell times;

determine a first number of the skipped viewed entries and a second number of the viewed entries including both the skipped viewed entries and the selected viewed entries;

determine a ranking quality metric for the ranked list using the first number of the skipped viewed entries and the second number of the viewed entries; and

using the ranking quality metric to tune a search application,

wherein the skipped viewed entries and the selected viewed entries are ranked relatively higher in the ranked list than the unviewed entries and the skipped viewed entries are interspersed with the selected viewed entries in the ranked list.

5. The system of claim 4, wherein the ranked list appears in a first zone of a web search results page comprising multiple zones.

6. The system of claim 5, wherein the executable instructions further cause the at least one processing unit to:

determine another ranking quality metric for a second zone of the web search results page comprising another ranked list, the another ranking quality metric being determined using another number of other skipped viewed entries from the another ranked list and a further number of other viewed entries from the another ranked list.

7. The system of claim 6, wherein the first zone is a web search results zone and the second zone is an advertisement zone.

8. The system of claim 4, wherein the executable instructions further cause the at least one processing unit to:

determine the ranking quality metric for the ranked list with respect to a first category and determine another ranking quality metric for the ranked list with respect to a second category.

9. The system of claim 8, wherein the first category is music and the second category is sports.

10. The system of claim 4, wherein the executable instructions cause the at least one processing unit to:

determine the dwell times as lengths of time between first times when individual entries are selected and second times when the user engages in further interaction with the ranked list.

11. The system of claim 4, wherein executable instructions cause the at least one processing unit to:

determine a last clicked entry in the ranked list; and

designate certain entries appearing in the ranked list after the last clicked entry as the unviewed entries and a remainder of the multiple entries of the ranked list as the viewed entries.

12. A method performed by one or more processing units, the method comprising:

accessing log data that reflects user interactions by a user with a ranked list, the ranked list having multiple entries;

determining, from the log data, that the multiple entries of the ranked list include viewed entries that have been viewed by the user and unviewed entries that have not been viewed by the user;

ascertaining, from the log data, that the viewed entries include skipped viewed entries that the user has skipped and selected viewed entries that the user has selected, wherein the skipped viewed entries and the selected viewed entries are ranked relatively higher in the ranked list than the unviewed entries and the skipped viewed entries are interspersed with the selected viewed entries in the ranked list;

determining a first number of the skipped viewed entries and a second number of the viewed entries including both the skipped viewed entries and the selected viewed entries;

determining a ranking quality metric for the ranked list using the first number of the skipped viewed entries and the second number of the viewed entries; and

using the ranking quality metric to tune a search application,

wherein the skipped viewed entries include partially skipped viewed entries and fully skipped viewed entries, and

the ascertaining comprises using dwell times to identify the partially skipped viewed entries.

13. The method as recited in claim 12, further comprising:

ascertaining a position of a last viewed entry in the ranked list, and characterizing individual entries above the position on the ranked list as the viewed entries and other individual entries below the position on the ranked list as the unviewed entries.

14. The method as recited in claim 12, wherein determining the ranking quality metric comprises:

dividing the first number of the skipped viewed entries by the second number of the viewed entries.

15. The method as recited in claim 14, wherein determining the ranking quality metric comprises:

weighting a quotient of the dividing by a probability that the log data includes a query used to obtain the ranked list.

16. The method as recited in claim 12, wherein using the dwell times to identify the partially skipped viewed entries comprises comparing the dwell times to a threshold and characterizing individual entries having dwell times below the threshold as the partially skipped viewed entries.

17. The method as recited in claim 12, further comprising obtaining time stamps from the log data indicating when individual entries are selected by the user and using the time stamps to determine the dwell times.

18. The method as recited in claim 12, wherein the search application is a search engine that produced the ranked list.

19. The method as recited in claim 12, further comprising identifying the partially skipped viewed entries by:

collecting a dwell time distribution from the dwell times;

separating the dwell time distribution into at least two mixture components;

annotating, from the at least two mixture components, an individual mixture component with shorter dwell times as being a bad selection component; and

applying Bayes rule to obtain a probability that a selection of a particular viewed entry is a bad selection indicating the particular viewed entry is partially skipped.

20. The method as recited in claim 12, wherein determining the ranking quality metric further comprises:

determining the ranking quality metric based on one or more techniques comprising;

a Maximum Likelihood Estimation (MLE) technique, a Maximum Mutual Information technique, a Minimum Variance Estimation technique, or a Maximum A posterior Probability (MAP) technique.