OPTIMIZING RANKING FUNCTIONS USING CLICK DATA

• US 20090265290A1
• Filed: 04/18/2008
• Published: 10/22/2009
• Est. Priority Date: 04/18/2008
• Status: Abandoned Application

• Current Assignee: Oath Inc. (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Murdock, Vanessa, Plachouras, Vassilis, Ciaramita, Massimiliano
• Application Number:
  US12/106,226
• Publication Number:
  US 20090265290A1
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06N 3/08 Learning methods
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A system for optimizing machine-learned ranking functions based on click data. The system determines the weighting for each feature of a plurality of features according to a learning model based on the click data. The system selects an element from a plurality of elements for display on a web page based on the weighting of each feature of the plurality of features. The system may rank the items to form a list on the web page based on the weighted features in order of inferred relevance according to the online learning model.

Claims

1. A system for optimizing machine-learned ranking functions based on click data, the system comprising:

a web server configured to collect click data for a set of queries and results;

an advertisement engine configured to determine weighting for each feature of a plurality of features according to an online learning model based the click data; and

wherein the advertisement engine selects an advertisement from a plurality of advertisements for display on a web page based on the weighting of each feature of the plurality of features.

2. The system according to claim 1, wherein the online learning model implements a perceptron algorithm.

3. The system according to claim 1, wherein the online learning model implements a classification algorithm.

4. The system according to claim 3, wherein the classification algorithm is based on the relationship:

α

^t+1=α

^t+y_tx_i

where y is the actual value, x is the input pattern, α

is weighting for the features;

t is the number is instances used in training.

5. The system according to claim 1, wherein the online learning model implements a ranking algorithm.

6. The system according to claim 5, wherein the ranking algorithm is based on the relationship:

α

^t+1=α

¹+(x₁−

x_i)τ

where x is the input pattern, α

is weighting for the features; and

τ

is the positive learning margin.

7. The system according to claim 1, wherein the online learning model implements a multilayer regression algorithm.

8. The system according to claim 7, wherein the multilayer regression algorithm is based on the relationship:

9. The system according to claim 1, wherein the features comprise at least one of word overlap, cosine similarity, and correlation.

10. The system according to claim 1, further comprising evaluating the weighting for each feature by predicting an predictive selected advertisement for a block of advertisements and comparing the predictive selected advertisement with an actually selected advertisement.

11. The system according to claim 1, further comprising ranking the plurality of advertisements based on the weighting.

12. The system according to claim 1, further comprising updating the ranking the plurality of advertisements based on a user click associated with an advertisement of the plurality of advertisements.

13. A method for optimizing machine-learned ranking functions based on click data, method comprising:

determining weighting for each feature of a plurality of features according to an online learning model based on click data;

selecting an element from a plurality of elements for display on a web page based on the weighting of each feature of the plurality of features.

14. The method according to claim 13, wherein the online learning model implements a perceptron algorithm.

15. The method according to claim 13, wherein the online learning model implements a classification algorithm.

16. The method according to claim 15, wherein the classification algorithm is based on the relationship:

α

^t+1=α

^t+y_1i

where y is the actual value, x is the input pattern, α

is weighting for the features;

t is the number is instances used in training.

17. The method according to claim 13, wherein the online learning model implements a ranking algorithm.

18. The method according to claim 17, wherein the ranking algorithm is based on the relationship:

α

^t+1=α

¹+(x₁−

x_i)τ

where x is the input pattern, α

is weighting for the features; and

τ

is the positive learning margin.

19. The method according to claim 13, wherein the online learning model implements a multilayer regression algorithm.

20. The method according to claim 19, wherein the multilayer regression algorithm is based on the relationship:

21. The method according to claim 13, wherein the features comprise at least one of word overlap, cosine similarity, and correlation.

22. The method according to claim 13, further comprising evaluating the weighting for each feature by predicting an predictive selected element for a block of elements and comparing the predictive selected element with an actually selected element.

23. The method according to claim 13, further comprising ranking the plurality of elements based on the weighting.

24. The method according to claim 13, further comprising updating the ranking the plurality of elements based on a user click associated with an element of the plurality of elements.

25. A computer readable medium having stored therein instructions executable by a programmed processor for optimizing machine-learned ranking functions based on click data, the computer readable medium comprising instructions for:

determining weighting for each feature of a plurality of features according to an online learning model based on click data;

selecting an element from a plurality of elements for display on a web page based on the weighting of each feature of the plurality of features.

26. The computer readable medium according to claim 25, further comprising evaluating the weighting for each feature by predicting an predictive selected element for a block of elements and comparing the predictive selected element with an actually selected element.

27. The computer readable medium according to claim 25, further comprising ranking the plurality of elements based on the weighting.

28. The computer readable medium according to claim 25, further comprising updating the ranking the plurality of elements based on a user click associated with an element of the plurality of elements.

29. The computer readable medium according to claim 25, wherein the online learning model comprises at least one of a classification algorithm, a ranking algorithm, or a multilayer regression algorithm.