Cluster-based and rule-based approach for automated web-based targeted advertising with quotas

• US 7,472,102 B1
• Filed: 10/29/1999
• Issued: 12/30/2008
• Est. Priority Date: 10/29/1999
• Status: Expired due to Fees

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Heckerman, David E., Rosen, Daniel, Chickering, D. Maxwell
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/430,767
• Time in Patent Office: 3,350 Days
• Field of Search: 706/45, 706/47, 705/10, 705/14, 705/8, 707/505, 709/217, 725/116
• US Class Current: 706/47
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Targeted delivery of items with inventory management using a cluster-based approach or a rule-based approach is disclosed. An example of items is advertisements. Each item is allocated to one or more clusters. The allocation is made based on a predetermined criterion accounting for at least a quota for each item and possibly a constraint for each cluster. The former can refer to the number of times an item must be shown. The latter can refer to the number of times a given group of web pages is likely to be visited by users, and hence is the number of times items can be shown in a given cluster. The invention is not limited to any particular definition of what constitutes a cluster or item.

Claims

1. A computer-implemented method comprising:

allocating each of a plurality of ads to at least one of a plurality of clusters, based on a predetermined criterion accounting for at least a quota for each ad and a constraint for each cluster;

selecting an ad for a current cluster from ads allocated to the current cluster; and

effecting the ad, the predetermined criterion increases an actuation occurrence of the effected ad.

2. The method of claim 1, effecting the ad comprises displaying the ad.

3. The method of claim 2, the predetermined criterion further accounts for a particular one of the plurality of ads restricted from being shown in a particular one or more of the plurality of clusters.

4. The method of claim 2, the predetermined criterion comprises maximizing an expression

$\sum _{}$

ij ⁢

p ij ⁢

x ij ,

were p_ij comprises a probability that a user in cluster j will actuate ad i.

5. The method of claim 4, the predetermined criterion further comprises maximizing the expression subject to a constraint

$\sum _{}$

j ⁢

x ij = q i ,

where q_i comprises a quota for ad i, and x_ij comprises a total number of times ad i is shown in cluster j.

6. The method of claim 4, the predetermined criterion further comprises maximizing the expression subject to a constraint

$\sum _{}$

i ⁢

⁢

x ij = c j ,

where c_j, comprises a constraint for cluster j, and x_ij comprises a total number of times ad i is shown in cluster j.

7. The method of claim 4, the predetermined criterion comprises maximizing the expression subject to a first constraint

$\sum _{}$

j ⁢

⁢

x ij = q i ,

where q_i comprises a quota for ad i, and x_ij comprises a total number of times ad i is shown in cluster j, and a second constraint

$\underset{i}{\sum <br><br>}<br><br><br><br>x_{\mathrm{ij}}=c_j,$

where c_j comprises a constraint for cluster j, and x_ij comprises a total number of times ad i is shown in cluster j, such that the expression, the first constraint and the second constraint define a linear program.

8. The method of claim 7, the linear program is solved by the Simplex Algorithm.

9. The method of claim 2, allocating each of a plurality of ads to at least one of the plurality of clusters comprises determining for each ad in each cluster a probability that a user in the cluster will actuate the ad.

10. The method of claim 9, the probability that a user in the cluster will actuate the ad comprises the probability that a user in the cluster will click on the ad.

11. The method of claim 9, determining for each ad in each cluster a probability that a user in the cluster will actuate the ad comprises inputting training data from which to determine for each ad in each cluster the probability that a user in the cluster will actuate the ad.

12. The method of claim 9, determining for each ad in each cluster a probability that a user in the cluster will actuate the ad comprises utilizing at least one of:

a maximum likelihood approach, a MAP method approach, and, a hierarchical Bayesian approach.

13. The method of claim 2, the predetermined criterion comprises maximizing an expected number of actuations of the plurality of ads, given the quota for each ad and the constraint for each cluster.

14. The method of claim 2, the constraint for each cluster comprises a total number of times the cluster is visited by any user.

15. The method of claim 2, the quota for each ad comprises a total number of times that the ad must be displayed.

16. The method of claim 2, the criterion comprises favoring at least one ad over other ads within the plurality of ads in allocating the at least one ad.

17. The method of claim 2, the criterion comprises accounting for at least one house ad.

18. The method of claim 2, the predetermined criterion comprises minimizing an expression

$\sum _{}$

ij ⁢

⁢

p ij ⁢

x ij ,

where p_ij comprises a probability that a user in cluster j will actuate ad i.

19. The method of claim 2, the predetermined criterion comprises maximizing an expression

$\sum _{}$

ij ⁢

⁢

α

i ⁢

p ij ⁢

x ij ,

where p_ij comprises a probability that a user in cluster j will actuate ad i, and α

_i comprises a coefficient for the ad i to indicate weighting of the ad i.

20. The method of claim 4, the predetermined criterion further comprises maximizing the expression subject to a constraint x_ij=0 for a particular ad i within a particular cluster j, where x_ij comprises a total number of times the ad i is shown in the cluster j.

21. The method of claim 4, the predetermined criterion further comprises maximizing the expression subject to a constraint

$\sum _{}$

i ⁢

⁢

x ij ⁢

<

_ ⁢

c j ,

where c_j comprises a constraint for cluster j, and x_ij comprises a total number of times ad i is shown in cluster j.

22. The method of claim 9, the probability that a user in the cluster will actuate the ad comprises the probability that a user in the cluster will make a purchase based on the ad.

23. The method of claim 2, the method includes first initially defining the plurality of clusters.

24. The method of claim 23, defining the plurality of clusters comprises utilizing user information obtained without monitoring.

25. The method of claim 23, utilizing user information obtained without monitoring comprises utilizing a category tag (e.g., page group) of the page on which the ad is to be displayed.

26. The method of claim 24, utilizing user information obtained without monitoring comprises utilizing user information obtained from the user via a questionnaire.

27. The method of claim 23, defining the plurality of clusters comprises utilizing a preexisting plurality of groups as the plurality of clusters.

28. The method of claim 23, defining the plurality of clusters comprises utilizing a Bayesian network.

29. The method of claim 23, defining the plurality of clusters comprises utilizing a naï

ve-Bayes-network clustering approach.

30. The method of claim 29, utilizing a Bayesian network clustering approach comprises utilizing a bottleneck architecture.

31. The method of claim 29, utilizing a Bayesian network clustering approach comprises utilizing a bottleneck architecture recursively to construct a hierarchy of clusters.

32. The method of claim 29, utilizing a Bayesian network clustering approach comprises training a Bayesian network using a stochastic gradient descent technique.

33. The method of claim 29, utilizing a Bayesian network clustering approach comprises employing a single hidden variable having a plurality of values.

34. The method of claim 29, utilizing a Bayesian network clustering approach comprises employing a plurality of hidden variables, each having two values.

35. A computer-implemented method comprising:

defining a plurality of clusters, each cluster corresponding to a group of users who are most receptive to a given type of ad, defining the plurality of clusters comprises utilizing one of;

user information obtained without monitoring;

a Bayesian network;

or

a naï

ve-Bayes-network clustering approach;

allocating an ad having a particular type to at least one cluster based on the particular type of the ad and based on a predetermined criterion to maximize the number of click throughs of the allocated ad; and

outputting the allocated ad to the group of users.

36. The method of claim 35, utilizing user information obtained without monitoring comprises utilizing user information obtained from the user via a questionnaire.

37. The method of claim 35, utilizing a Bayesian network clustering approach comprises utilizing a bottleneck architecture.

38. The method of claim 35, utilizing a Bayesian network clustering approach comprises utilizing a hierarchical bottleneck architecture.

39. The method of claim 35, utilizing a Bayesian network clustering approach comprises training a Bayesian network using a stochastic gradient descent technique.

40. The method of claim 35, utilizing a Bayesian network clustering approach comprises employing a single hidden variable having a plurality of values.

41. The method of claim 35, utilizing a Bayesian network clustering approach comprises employing a plurality of hidden variables, each having two values.

42. A computer-implemented method comprising:

determining an allocation for each of a plurality of ads to at least one of a plurality of clusters, given a constraint

$\underset{j}{\sum <br><br>}<br><br><br><br>x_{\mathrm{ij}}=q_i,$

where q_i comprises a quota for ad i, and x_ij comprises a total number of times ad i is shown in cluster j; and

outputting the allocation of each ad to at least one of the plurality of clusters, the allocation provides a preference to at least one of the plurality of ads.

43. The method of claim 42, determining an allocation for each of a plurality of ads to at least one of the plurality of clusters comprises maximizing an expression

$\underset{\mathrm{ij}}{\sum \; <li></li>}<br><br><br><br>p_{\mathrm{ij}}<br><br>x_{\mathrm{ij}},$

where p_ij comprises a probability that a user in cluster j will actuate ad i, given the constraint.

44. The method of claim 42, determining an allocation for each of a plurality of ads to at least one of the plurality of clusters comprises determining the allocation for each of the plurality of ads to at least one of the plurality of clusters further given a constraint

$\sum _{}$

i ⁢

⁢

x ij = c j ,

where c_j comprises a constraint for cluster j, and x_ij comprises a total number of times ad i is shown in cluster j.

45. The method of claim 42, further comprising:

selecting an ad for a current cluster from the allocation of each ad to the current cluster; and

,

displaying the ad.

46. A computerized system comprising:

a database storing a plurality of ads, each ad having an item purchase quota;

an allocator to allocate each of the plurality of ads to at least one of a plurality of clusters, based on a predetermined criterion accounting for at least the item purchase quota for each ad and a constraint for each cluster; and

,

a communicator to select an ad for a current cluster from ads allocated to the current cluster and output the ad to a user.

47. The system of claim 46, at least one of the allocator and the communicator comprises a computer program executed from a computer-readable medium by a processor.

48. The system of claim 46, the database is stored as data on a computer-readable medium.

49. A machine-readable medium having instructions stored thereon for execution by a processor to perform a method comprising:

allocating each of a plurality of ads to at least one of a plurality of clusters, based on a predetermined criterion accounting for at least a quota for each ad and a constraint for each cluster, the quota for each ad is an ad display quota;

selecting an ad for a current cluster from ads allocated to the current cluster; and

displaying the ad to achieve the ad display quota.

50. The medium of claim 49, the predetermined criterion comprises maximizing an expression

$\sum _{}$

ij ⁢

⁢

p ij ⁢

x ij ,

where p_ij comprises a probability that a user in cluster j will actuate ad I.

51. The medium of claim 50, the predetermined criterion further comprises maximizing the expression subject to a constraint

$\sum _{}$

j ⁢

⁢

x ij = q i ,

where q_i comprises a quota for ad i, and x_ij comprises a total number of times ad i is shown in cluster j.

52. The medium of claim 50, the predetermined criterion further comprises maximizing the expression subject to a constraint

$\sum _{}$

i ⁢

⁢

x ij = c j ,

where c_j comprises a constraint for cluster j, and x_ij comprises a total number of times ad i is shown in cluster j.

53. The medium of claim 49, allocating each of a plurality of ads to at least one of the plurality of clusters comprises determining for each ad in each cluster a probability that a user in the cluster will actuate the ad.

54. The medium of claim 49, the predetermined criterion comprises maximizing an expected number of actuations of the plurality of ads, given the quota for each ad and the constraint for each cluster.

55. A machine-readable medium having instructions stored thereon for execution by a processor to perform a method comprising:

determining an allocation for each of a plurality of ads to at least one of a plurality of clusters, given a constraint

$\underset{j}{\sum <br><br>}<br><br><br><br>x_{\mathrm{ij}}=q_i,$

where q_i comprises a quota for ad i, and x_ij comprises a total number of times ad i is shown in cluster j; and

outputting the allocation of each ad to at least one of the plurality of clusters, the allocation provides a preference to at least one of the plurality of ads.

56. The medium of claim 55, determining an allocation for each of a plurality of ads to at least one of the plurality of clusters comprises maximizing an expression

$\underset{\mathrm{ij}}{\sum \; <li></li>}<br><br><br><br>p_{\mathrm{ij}}<br><br>x_{\mathrm{ij}},$

where p_ij comprises a probability that a user in cluster j will actuate ad i, given the constraint.

57. The medium of claim 55, determining an allocation for each of a plurality of ads to at least one of the plurality of clusters comprises determining the allocation for each of the plurality of ads to at least one of the plurality of clusters further given a constraint

$\sum _{}$

i ⁢

⁢

x ij = c j ,

where c_j comprises a constraint for cluster j, and x_ij comprises a total number of times ad i is shown in cluster j.

58. A computer-implemented method comprising:

applying each of at least one first item to an ordered set of rules, each rule accounting for a click-through rate quota for each of a plurality of ads, to determine an ad for each of the at least one first item; and

effecting the ad for each of the at least one first item to achieve the click-through rate quota.

59. The method of claim 58, each first item comprises at least information about a user, and a web page currently being browsed by the user.

60. The method of claim 58, effecting the ad comprises displaying the ad.

61. The method of claim 58, further comprising generating the ordered set of rules based on training data.

62. The method of claim 61, generating the ordered set of rules comprises:

determining at least one significant correlation between a plurality of binary features of the training data and a plurality of activations of ads of the training data;

determining an ad and at least one binary feature providing a largest activation; and

,

generating a rule based on the ad and the at least one binary feature providing the largest activation.

63. The method of claim 62, generating the ordered set of rules further comprises:

removing records from the training data matching the rule generated; and

,

repeating to generate another, lower-ordered rule while at least one significant correlation still exists.

64. The method of claim 62, determining at least one significant correlation comprises utilizing one of:

Chi-squared method, Fisher exact test method, and Bayesian model selection method.

65. A computer-implemented method for inventory management comprising:

determining at least one significant correlation between a plurality of binary features of training data and a plurality of activation of items from the training data;

determining an ad and at least one binary feature providing a largest activation, each rule accounting for at least a quota for the item;

generating a rule based on the ad and the at least one binary feature providing the largest activation;

removing records from the training data matching the rule generated; and

repeating to generate another, lower-ordered rule while at least one significant correlation still exists.

66. The method of claim 65, each ad comprises an ad.

67. A machine-readable medium having instructions stored thereon for execution by a processor to perform a method comprising:

applying each of at least one first item to an ordered set of rules, each rule accounting for at least a quota for each of a plurality of second items, to determine a second item for each of the at least one first item; and

,

effecting the second item for each of the at least one first item.

68. The medium of claim 67, the method further comprising generating the ordered set of rules based on training data.

69. The medium of claim 67, each first item comprises at least information about a user, and a web page currently being browsed by the user, and each second item comprises an ad.

70. The medium of claim 67, generating the ordered set of rules comprises:

determining at least one significant correlation between a plurality of binary features of the training data and a plurality of activations of second item of the training data;

determining a second item and at least one binary feature providing a largest activation;

generating a rule based on the second item and the at least one binary feature providing the largest activation;

removing records from the training data matching the rule generated; and

,

repeating to generate another, lower-ordered rule while at least one significant correlation still exists.

71. A machine-readable medium having instructions stored thereon for execution by a processor to perform a method comprising:

determining at least one significant correlation between a plurality of binary features of training data and a plurality of activations of an item from training data;

determining an ad and at least one binary feature providing a largest activation, each rule accounting for at least a quota for the item;

generating a rule based on the ad and the at least one binary feature providing the largest activation;

removing records from the training data matching the rule generated; and

,

repeating to generate another, lower-ordered rule while at least one significant correlation still exists.