Banner advertisement selecting method

• US 6,591,248 B1
• Filed: 11/29/1999
• Issued: 07/08/2003
• Est. Priority Date: 11/27/1998
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Nakamura, Atsuyoshi, Abe, Naoki
• Primary Examiner(s): CHAMPAGNE, DONALD
• Application Number:
  US09/447,946
• Time in Patent Office: 1,317 Days
• Field of Search: 705/14
• US Class Current: 705/14.52
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0254 based on statistics
• CPC Class Codes: G06Q 30/0255 based on user history
• CPC Class Codes: G06Q 30/0277 Online advertisement

Abstract

A banner advertisement selecting method is disclosed comprising the steps of (a) estimating the input probability of each attribute and the click rate of each advertisement for each attribute corresponding to an input attribute distribution of the banner advertisement and a click history of which the banner advertisement was clicked, (b) obtaining a display probability of each banner advertisement for each attribute so that the total click rate becomes maximum with conditions such as the desired number of display times of each banner advertisement being satisfied, (c) selecting a banner advertisement according to the display probability, and (d) transforming a restricted objective function maximizing problem obtained at step (b) to a transportation problem and solving the transportation problem.

Claims

1. A banner advertisement selecting method for selecting a banner advertisement displayed on a page browsed through the world wide web (WWW) from an attribute list obtained corresponding to information transmitted with a page browsing request, information of the browsed page, and user information, the method comprising the steps of:

(a) estimating the input probability of each attribute and the click rate of each advertisement for each attribute corresponding to an input attribute distribution of the banner advertisement and a click history of which the banner advertisement was clicked;

(b) obtaining a display probability of each banner advertisement for each attribute so that the total click rate becomes maximum;

(c) selecting a banner advertisement according to the display probability; and

(d) transforming a constrained objective function maximizing problem obtained at step (b) to the known transportation problem and solving the transportation problem.

2. The banner advertisement selecting method as set forth in claim 1, further comprising the steps of:

(e) clustering attributes with similar click histories, step (e) being followed by step (b);

(f) obtaining a cluster to which the input attribute belongs; and

(g) selecting a banner advertisement to be displayed according to the display probability of each banner advertisement for the cluster.

3. The banner advertisement selecting method as set forth in claim 2,

wherein step (b) is performed by treating step (e) as a problem for estimating a click rate conditioned with each attribute using a past click rate history for each attribute, and repeatedly combining attributes that causes the total description length to be minimized or sub-minimized using a greedy heuristic based on the theory of minimum description length so as to decrease the number of estimation parameters and improve the estimation accuracy.

4. The banner advertisement selecting method as set forth in claim 2,

wherein step (b) is performed by treating step (e) as a problem for estimating a click rate conditioned with each attribute using a past click rate history for each attribute, and repeatedly combining attributes that causes the total information amount to be minimized or sub-minimized using a greedy heuristic based on Akaike information criterion so as to decrease the number of estimation parameters and improve the estimation accuracy.

5. The banner advertisement selecting method as set forth in claim 1, further comprising the step of:

(h) securing a large value as the minimum display probability that is inversely proportional to the square root of the number of display times of each banner advertisement with each attribute.

6. The banner advertisement selecting method as set forth in claim 1, further comprising the steps of:

(i) calculating estimation value c of the click rate for each banner advertisement j with each attribute i using the number of display times and the number of click times;

obtaining estimation value μ

of the click rate for attribute i of past banner advertisement j′

having attributes similar to the attributes of banner advertisement j;

(j) adding 1 to the number of display times of banner advertisement j with attribute i; and

(k) calculating estimation value c of the click rate with a value of which μ

is added to the number of click times.

7. The banner advertisement selecting method as set forth in claim 1,

wherein Gittins Index or compensated Gittins Index compensated by Laplace estimation is used instead of the estimation value of the click rate that forms the maximized objective function.

8. The banner advertisement selecting method as set forth in claim 1, further comprising the step of:

(l) randomly selecting one attribute from a plurality of input attributes; and

(m) selecting a banner advertisement to be displayed according to the display probability of each banner advertisement with the selected attribute.

9. The banner advertisement selecting method as set forth in claim 2, further comprising the step of:

(h) securing a large value as the minimum display probability that is inversely proportional to the square root of the number of display times of each banner advertisement with each attribute.

10. The banner advertisement selecting method as set forth in claim 2, further comprising the steps of:

(i) calculating estimation value c of the click rate for each banner advertisement j with each attribute i using the number of display times and the number of click times;

obtaining estimation value μ

of the click rate for attribute i of past banner advertisement j′

having attributes similar to the attribute of banner advertisement j;

adding 1 to the number of display times of banner advertisement j with attribute i; and

(k) calculating estimation value c of the click rate with a value of which μ

is added to the number of click times.

11. The banner advertisement selecting method as set forth in claim 2,

wherein Gittins Index or compensated Gittins Index compensated by Laplace estimation is used instead of the estimation value of the click rate that forms the maximized objective function.

12. The banner advertisement selecting method as set forth in claim 2, further comprising the step of:

(l) randomly selecting one attribute from a plurality of input attributes; and

(m) selecting a banner advertisement to be displayed according to the display probability of each banner advertisement with the selected attribute.

13. A banner advertisement selecting apparatus for selecting a banner advertisement displayed on a page browsed through the world wide web from an attribute list obtained corresponding to information transmitted with a page browsing request, information of the browsed page, and user information, comprising:

estimating means for estimating the input probability of each attribute and the click rate of each advertisement for each attribute corresponding to an input attribute distribution of the banner advertisement and a click history of which the banner advertisement was clicked;

display probability securing means for obtaining a display probability of each banner advertisement for each attribute so that the total click rate becomes maximum;

display probability creating means for transforming a constrained objective function maximizing problem obtained by said display probability securing means to the known transportation problem, solving the known transportation problem and creating the display probability of each banner advertisement; and

selector for selecting a banner advertisement according to the display probability.

14. The banner advertisement selecting apparatus as set forth in claim 13, further comprising:

cluster creating means for clustering attributes with similar click histories, obtaining a cluster to which the input attribute belongs, and selecting the banner advertisement to be displayed according to the display probability of each banner advertisement for the cluster.

15. The banner advertisement selecting method as set forth in claim 13,

wherein said display probability securing means is performed by treating said display probability creating means as a problem for estimating a click rate conditioned with each attribute using a past click rate history for each attribute, and repeatedly combining attributes that causes the total description length to be minimized or sub-minimized using a greedy heuristic based on the theory of minimum description length so as to decrease the number of estimation parameters and improve the estimation accuracy.

16. The banner advertisement selecting method as set forth in claim 14,

wherein said display probability securing means is performed by treating said display probability creating means as a problem for estimating a click rate conditioned with each attribute using a past click rate history for each attribute, and repeatedly combining attributes that causes the total description length to be minimized or sub-minimized using a greedy heuristic based on Akaike information criterion so as to decrease the number of estimation parameters and improve the estimation accuracy.

17. A banner advertisement selecting apparatus for selecting a banner advertisement displayed on a page browsed through the world wide web (WWW) from an attribute list obtained corresponding to information transmitted with a page browsing request, information of the browsed page, and user information, comprising:

banner advertisement displaying means for selecting the banner advertisement and transmitting image data thereof to the web browsing software;

advertisement page displaying means for recording a click history and displaying detailed advertisement pages of the advertisement provider;

learning information providing means for providing to a learning engine with an input attribute distribution, the click history, and advertisement information so that the learning engine learns a display probability function used to select an advertisement;

advertisement managing means for managing advertisement contract information;

wherein the learning engine comprise;

advertisement selecting means for selecting one attribute from an attribute list at random;

a display probability function storing portion for being stored a cluster table clustering an attribute based on input information;

learning means for storing a predictive display probability function referenced by the advertisement selecting means to the display probability function storing portion;

a data storing portion for being referenced and updated by said learning means.