Prediction engines using probability tree and computing node probabilities for the probability tree

• US 7,908,238 B1
• Filed: 08/31/2007
• Issued: 03/15/2011
• Est. Priority Date: 08/31/2007
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: O'Kelley, Charles Brian, Mouzykantskii, Boris, Nolet, Michiel
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): Bharadwaj; Kalpana
• Application Number:
  US11/848,688
• Time in Patent Office: 1,292 Days
• Field of Search: None
• US Class Current: 706/52
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

There are methods and apparatus, including computer program products, for providing a probability tree of nodes in which each node is associated with a tries value and a success value, and at least one node is associated with a computed probability value representative of a predicted response rate for an advertisement creative; and computing a first probability value for a first node of the probability tree based on its associated tries value and success value, and a computed probability value associated with a parent node to the first node. In one exemplary embodiment, the first probability is computed according to the following equation:

$\mathrm{Probability}=\frac{\left(1+{\mathrm{Success}}_{\mathrm{node}}-{\mathrm{Success}}_{\mathrm{Child}}\right)}{({\mathrm{tries}}_{\mathrm{node}}+\frac{1}{{\mathrm{probability}}_{\mathrm{Parent}}}-{\mathrm{tries}}_{\mathrm{child}}}$

Claims

1. A computer-implemented method comprising:

providing a probability tree of nodes in which each node is associated with a tries value and a success value, and at least one node is associated with a computed probability value representative of a predicted response rate for an advertisement creative; and

computing a first probability value for a first node of the probability tree based on its associated tries value and success value, and a computed probability value associated with a parent node to the first node, wherein the first probability value is computed based on an algorithm that generates a probability value approximately equal to that of the parent node to the first node when the success value associated with the first node approaches zero.

2. The method of claim 1, further comprising:

storing the first computed probability value in the first node of the probability tree.

3. The method of claim 1, further comprising:

computing a probability value for each node of the probability tree based on its associated tries value and success value, and a computed probability value associated with its parent node; and

storing each computed value in the respective node of the probability tree.

4. The method of claim 1, further comprising:

collecting information that defines a tries value and a success value for the first node; and

re-computing the first probability value for the first node of the probability tree based in part on the collected information.

5. The method of claim 1, further comprising:

generating a bid for an advertisement placement transaction based on the first computed probability value.

6. A computer-implemented method comprising

providing a probability tree of nodes in which each node is associated with a tries value and a success value, and at least one node is associated with a computed probability value representative of a predicted response rate for an advertisement creative;

and

computing a first probability value for a first node of the probability tree based on its associated tries value and success value, and a computed probability value associated with a parent node to the first node, wherein the first probability value is computed by dividing the success value associated with the first node by the tries value associated with the first node when the success value associated with the first node approaches zero.

7. The method of claim 6, further comprising:

storing the first computed probability value in the first node of the probability tree.

8. The method of claim 6, further comprising:

computing a probability value for each node of the probability tree based on its associated tries value and success value, and a computed probability value associated with its parent node; and

storing each computed value in the respective node of the probability tree.

9. The method of claim 6, further comprising:

collecting information that defines a tries value and a success value for the first node; and

re-computing the first probability value for the first node of the probability tree based in part on the collected information.

10. The method of claim 6, further comprising:

generating a bid for an advertisement placement transaction based on the first computed probability value.

11. A computer-implemented method comprising:

providing a probability tree of nodes in which each node is associated with a tries value and a success value, and at least one node is associated with a computed probability value representative of a predicted response rate for an advertisement creative; and

computing a first probability value for a first node of the probability tree based on its associated tries value and success value, and a computed probability value associated with a parent node to the first node, wherein the first probability value is computed according to the following

12. The method of claim 11, further comprising:

storing the first computed probability value in the first node of the probability tree.

13. The method of claim 11, further comprising:

computing a probability value for each node of the probability tree based on its associated tries value and success value, and a computed probability value associated with its parent node; and

storing each computed value in the respective node of the probability tree.

14. The method of claim 11, further comprising:

collecting information that defines a tries value and a success value for the first node; and

re-computing the first probability value for the first node of the probability tree based in part on the collected information.

15. The method of claim 11, further comprising:

generating a bid for an advertisement placement transaction based on the first computed probability value.

16. A computer-implemented method comprising:

limiting a number of times advertisement impressions for a first creative are served on a particular publisher site to a throttling threshold that is based in part on a statistical accuracy of bids for the advertisement impressions;

providing a multi-level probability tree of nodes in which each node is associated with a computed probability value representative of a predicted response rate for an advertisement creative;

wherein the bids for advertisement impressions that are based on a computed probability value that is associated with a lower level tree node are more statistically accurate than the bids for advertisement impressions that are based on a computed probability value that is associated with a higher level tree node.

17. The method of claim 16, wherein the multi-level probability tree of nodes comprises:

a root node level that includes at least one publisher class node;

one or more intermediate node levels, each intermediate node level including at least one intermediate node that is subordinate to the root node level; and

a leaf node level that includes at least one uniform resource locator node that is subordinate to the one or more intermediate node levels.

18. The method of claim 16, wherein the multi-level probability tree of nodes includes a first level of nodes and a second level of nodes, at least one node of the second level being subordinate to the first level of nodes, the method further comprising:

assigning a first throttling threshold to the first level of nodes and assigning a second throttling threshold to the second level of nodes, the first throttling threshold being less than the second throttling threshold.

19. A machine-readable non-transitory medium that stores executable instructions to cause a machine to:

provide a probability tree of nodes in which each node is associated with a tries value and a success value, and at least one node is associated with a computed probability value representative of a predicted response rate for an advertisement creative; and

compute a first probability value for a first node of the probability tree based on its associated tries value and success value according to the following equation;

20. The machine-readable medium of claim 19, further comprising instructions to cause the machine to:

store the first computed probability value in the first node of the probability tree.

21. The machine-readable medium of claim 19, further comprising instructions to cause the machine to:

compute a probability value for each node of the probability tree based on its associated tries value and success value, and a computed probability value associated with its parent node; and

store each computed value in the respective node of the probability tree.

22. The machine-readable medium of claim 19, further comprising instructions to cause the machine to:

collect information that defines a tries value and a success value for the first node; and

re-compute the first probability value for the first node of the probability tree based in part on the collected information.

23. The machine-readable medium of claim 19, further comprising instructions to cause the machine to:

generating a bid for an advertisement placement transaction based on the first computed probability value.