March 23rd, 2011
Over the past few years, the one recurring question I’ve gotten from a number of people is — “Hey, how does Right Media’s predict work?” For obvious reasons I was never really able to answer the question.
Well, the patent we filed back in August of 2007 has finally been issued and is the information is now in the public domain. You can find the full patent here. It’s in lawyer-speak so a bit hard to read, but the diagrams show some interesting things. Of course, this is now four-year-old code & modeling which has certainly been updated so I’m not sure how useful it is, but if you asked me in late 2007/early 2008 how this all worked, now you know! Of course, if you want to rebuild it you’re in tough luck, because it’s patented!
The diagrams are particularly useful for understanding how it all worked. I won’t pretend to be able to explain this well after being completely disconnected from it for four years, but I pulled a few excerpts that are interesting to read for those that lack the patience to interpret lawyer speak.
The “tree” model:
Where probability represents the probability of the user taking the respective action for the node, success represents the number of times that the advertisement has been successful in generating the desired response (e.g., a click,a conversion), tries represents the number of times an advertisement has been posted, and probability.sub.parent represents the probability for the parent node on the tree structure (e.g., the node directly above the node for which the probability isbeing calculated). As summarized in table 1 below, what is meant by tries and successes varies dependent on whether the probability being calculated is a click probability, a post-view conversion probability or a post-click conversion probability.
When a node has a low number of tries, then the probability of the parent node has a greater influence over the calculated probability for the node than when the node has a large number of tries. In the extreme case, when a particular node haszero tries and zero successes, then the probability for the node equals the probability of the parent node. At the other extreme, when the node has a very large number of tries, the probability of the parent node has a negligible impact on theprobability calculated for the node. As such, when the node has a large number of tries, the probability is effectively the number of successes divided by the number tries. By factoring in the parent node probability in the calculation of a node’sprobability, a probability value may be obtained even if the granularity and/or size of the available data set on its own precludes the generation of a statistically accurate probability.
Learning Thresholds / “Aspiring CPMs”
FIG. 10 shows a process 300 for determining whether to continue learning for a particular creative based on the upper and lower limits. The transaction management system 100 retrieves a number of successes for a creative (302) and compares thenumber of successes to a threshold that indicates an upper limit on the amount of learning for a particular creative (304). If the number of successes is greater than the threshold, the transaction management system 100 removes the creative from thelearning inventory (306). Once the creative is removed from the learning inventory, the number of tries and successes generated during the learning period are used to determine a probability that a user will act on the creative (e.g., as describedabove). This probability is subsequently used to generate bids for the creative in response to a publisher posting an ad request.
Deciding on a learn vs. optimized creative:
In order for learning to occur, the transaction management system 100 devotes a percentage of the posted advertisements to learning creatives. The allocated inventory for learning is used to allow creatives to receive sufficient impressions togenerate information on the probability of a user taking action when the advertisement is posted. FIG. 11 shows an auction process 320 for selecting an ad creative to be served in responsive to an ad call received by the ad exchange. The transactionmanagement system 100 performs an auction among the non-learning creatives on the ad exchange to identify the highest optimized bid (324). Since a limited amount of inventory is devoted to learning, the system determines whether the ad call is allocatedto learning or is for non-learning (328). If the ad call is for non-learning, then the winning non-learning creative is posted in response to the ad call (326). If the ad call is allocated for learning, then the transaction management system 100retrieves a list of creatives eligible for learning (322). The list of creatives eligible for learning can be determined as described above. For the learning creatives, the transaction management system 100 calculates the aCPM for the creativesincluded in the list of creatives eligible for learning (330). Based on the calculated aCPM, the system 100 removes any creatives for which the calculated aCPM is lower than the highest optimized bid (332). The transaction management system 100randomly selects one of the remaining learning creatives (334) and posts the randomly selected creative in response to the ad call (336).