Decisioning / January 23, 2018

Decision Sciences 101: Machine Learning Algorithms

Online advertising campaigns with user targeting belong to the category of performance campaigns. The goal here is to accurately identify and target the most receptive audiences with traits matching the product or service being advertised.

At Eyeview, we currently receive more than 35 billion bid requests daily, out of those we bid on fewer than 1%. Therefore, decisioning on which bid requests to respond to, what is the right bid price and what video ad to show to the potential user, is critical to the campaign outcome as well as the profitability of the company. The objective of any campaign is to deliver the requested amount of impressions while maximizing the reach to the desired audience within the budget constraint. This is a non-trivial optimization problem, which we will discuss here. For instance, reach to the desired audience is determined by a particular user score function, which is dependent on campaign goals. For each bid request we need to determine user importance – score and bid price, bid rate necessary to achieve campaign goals – this process takes place online in less than one minute and below 50 millisecond for each auction. Two main elements of performance campaigns with user targeting are: user score function and optimization engine.

User Modeling/Segments

User score functions assign numerical value (user score) to each bid request, this is website visitation. Such user scores represent the importance of the given audience to the advertiser. Determining the user score function may be very simple, for instance basing it on user segments provided by the brand or more complex, which involves machine-learning algorithms such as nearest-neighbor, random forest, gradient boosting, clustering techniques as well feature extraction and dimension reduction. Generation of user score models has a long-existing practice in direct marketing and was covered in a separate article. Correctness of the audience score function is determined by campaign performance – outcome/conversion.

Optimization

Based on data from available inventory, the number of bid requests per user segment, required impressions and budget constraints we need to make the decision on campaign budget allocation: bid price and bid rate per each user score segment to maximize campaign performance – increase reach to most desired by advertiser audience. The problem we are addressing belongs to the category of NLP problems where our objective function – average user score is a non-linear function of our variables in this case bid price and bid rate. These problems are complex due to difficulty of determination of global optimum and to this day subject of research.

Depending on the volume of available inventory, bid requests that come from exchanges, whether it’s high, moderate or limited, Figure 1, we can distinguish three different optimization modes during a performance CPM campaign.

Figure 1. Population distribution across different user score value

The first and most desired scenario is high inventory of desired users which guarantees achievement of high average user scores and allows to optimize for margin – minimizing cost of the campaign. In this case we can assure we achieve the highest average user score but we also try to minimize the cost by selecting the minimum bid price that guarantees meeting campaign criteria: number of impression per booking period, highest available user score and budget constraint. It is the most desired situation but due to limited inventory is rarely taking place.

The second most common case is moderate inventory when there is not sufficient bid requests of highest value audience to meet all campaign goals. In this case we need to perform “portfolio” optimization, we determine bid price and bid rate per each user segment which satisfies our campaign goals and maximizes the average user score of our audience. Due to distribution of audience in different user score segments, which usually shows much higher population of lower score users compared to higher score users number of impressions that we can acquire for given bid price is much higher compared to higher scored users. In this case we make sure that we acquire the high user score audience first and add lower user score segments to meet requirements on number of impressions to be delivered under budget constraint. As users of higher segments are more valuable to us we need to make sure that the price that we pay per impression is proportional to the user value to the campaign.

The third case is constrained inventory when bid requests do not meet our campaign criteria and inventory is very limited. In this case we perform impression maximization, under given campaign constraints of minimum average user score and cost per impression, we try to determine bid price and bid rate which delivers maximum number of impressions. This case takes place usually during the night when internet activity is reduced compared to one during the day and therefore available inventory of bid request coming from exchange is reduced significantly. In such cases, we need to bid for higher prices and higher frequency – bid rate to achieve desired performance. Resulting in under-delivery of impressions during the night will be compensated during the day to meet campaign goals over booking period.

Eyeview’s optimization engine for real-time bidding based on inventory information evaluates possible solutions for each of the scenarios in the order presented above. This guarantees the highest campaign performance and provides bid price and bid rate per each audience segment which satisfies campaign constraints at the lowest cost, Figure 2.

 

Figure 2. System diagram

As one can notice, one of the challenges of a real-time bidding system for online advertising campaigns, is the determination of win price and win rate of a given auction for a given bid price. Bid requests come from ad exchanges that operate using second price auctions: auction is won by highest bidder but the winner pays second highest price. Therefore, to be able to make meaningful decisions requires knowledge of expected win price – price being paid by advertiser for given bid price and the probability of winning auction given bid price which is between 0 and 1. In real life probability curve usually reaches plateau below 0.3, Figure 3, (meaning with given bid price we may win 30% of auctions we participated in) and due to nonlinearity of the function increase of bid price over certain level does not significantly increase your chances of winning but can lead to overspending of your campaign budget.

Figure 3. Effect of bid price on win rate per auction

 

Figure 4. Bid price and win price over time per one thousand impressions

 

Knowledge of accurate win price has significant importance for campaign budget management, the cost of the campaign is proportional to the win price being paid for impression, Figure 4. By increasing bid price, we increase our probability of winning auction but if all participants in given auction will bid maximum bid price it will drive increase of win price. We don’t know the bid prices of other participants in the auction so we need to be able to predict the win price and bid price before submitting bid to the exchange. Eyeview has developed models of win price and win rate probability of bid price for different auctions which are being trained daily based on feedback from the previous day auction results. Accuracy of these models determine how accurate the decision will be provided by optimizer.

To suppress the effect of daily and hourly fluctuations of available inventory and therefore accuracy in win price and win rate predictions given by our models in bidding decision engine we incorporated controller which provides minute by minute learning to the system by adjustment of bid price and bid rate to meet goals provided by optimizer based on feedback from the exchange – actual win rate and win price, Figure 5.

 

Figure 5. Real time bidding system – feedback loop.

 

All these decisions need to be generated within 60 seconds for hundreds of auctions. Therefore our solutions to proposed by our Data Science team need be robust and scalable.

We have discussed a novel real-time bidding system that enables effective targeting of desired audiences – most relevant to the brand and product being advertised and delivery of required impressions under budget constraint. We have implemented an optimization engine using an adaptive optimization strategy to adjust optimization objective to available inventory: maximization of margin under high inventory scenario, maximization of user score under moderate inventory and maximization of impressions under  constraint inventory. This novel RTB approach has proven significant improvements (double digits) in campaign performance, increase of site visitation rate, and lower effective cost per impression.

 
Wojciech Kowalinski

Wojciech Kowalinski Decision Scientist

Date: 01.23.2018
Tags: