應用多重預測模型與多維劃分於實時競價競標最佳化

Real-Time Bidding Optimization with Multiple Predictors and Multi-Dimensional Segmentation

林其儁(Chi-Chun Lin)

指導教授 ： 陳銘憲

國立臺灣大學/電機資訊學院/電機工程學研究所/博士(2020年)

https://doi.org/10.6342/NTU201904405

摘要

本論文所探討的主旨乃關於【實時競價】廣告環境之中的前瞻課題：競標策略設計。此課題之目的在於發展最佳化的競標策略，來針對廣告營銷活動中的每一個【曝光機會】進行投標，從而在一定的預算限制之下捕獲最多的點擊次數。當前已知最先進的競標演算法僅依賴單一預測模型，亦即所謂的【點擊機率預測】，來為每個廣告曝光機會計算其投標價。如果所採用的點擊預測模型具備足夠的預測精確度，則這樣的演算法可以達成不錯的表現。然而，當預測模型精確度有限時，此類傳統方法通常無法提供最佳結果。為了改進這種情況，我們提出新的方法，額外地將【得標價格預測】模型納入競標流程之中，開發出結合多重預測模型的競標演算法。此演算法乃透過與計算機科學中經典的【隨機線上背包問題】之類比衍生而來，我們同時也運用此類比來對新演算法的效率進行理論分析。除了理論以外，實務上我們亦搭配真實世界中的實時競價資料集安排各種實驗。其結果顯示在有限的預算之下，新的演算法不但能夠比傳統方法獲得更多的點擊次數，而且在每個點擊之平均成本上的表現也來得較佳。
接下來，我們更加深入，提出一個能夠潛在地與任何競標演算法整合之框架，透過【多維劃分】的概念來進一步優化。一般情況下，實時競價廣告營銷活動經常在特定的維度上表現出某些特性。例如，若我們觀察曝光機會之捕獲成本與曝光密度在時間維度上的分佈，可能會發現每個不同時間區段呈現不一樣的分佈。這一點啟發了我們設計新方法，將不同區段的特徵納入考量以優化競標流程。具體而言，我們將廣告營銷活動依時間軸劃分為數個一維區段，並針對每個區段單獨訓練專屬的競標演算法參數。此模式相較於原先之從頭到尾都採用同一組參數的作法，能夠達成更好的競標結果。我們進一步將這個想法推廣為多維劃分的框架，並且分別設計採用【貪婪演算法】與【動態規劃】兩種不同手段的優化系統。此框架的有效性，在透過完整的實驗之後獲得證實。

關鍵字

實時競價 ； 需求方平台 ； 競標演算法設計 ； 多重預測模型 ； 多維劃分

並列摘要

In this dissertation, we pursue a better solution for the promising problem, i.e., the bidding strategy design, in the real-time bidding (RTB) advertising (AD) environment. Under the budget constraint, the design of an optimal strategy for bidding on each incoming impression opportunity targets at acquiring as many clicks as possible during an AD campaign. State-of-the-art bidding algorithms rely on a single predictor, the clickthrough rate predictor, to calculate the bidding value for each impression. This provides reasonable performance if the predictor has appropriate accuracy in predicting the probability of user clicking. However, the classical methods usually fail to capture optimal results since the predictor accuracy is limited. We improve the situation by accomplishing an additional winning price predictor in the bidding process. To explore the idea, an algorithm combining powers of multiple prediction models is developed. It emerges from an analogy to the online stochastic knapsack problem, and the efficiency of the algorithm is also theoretically analyzed. Experiments conducted on real world RTB datasets show that the proposed solution performs better with regard to both number of clicks achieved and effective cost per click in many different settings of budget constraints.
To dive deeper, we also propose a multi-dimensional segmentation framework for optimizing RTB advertising performance incorporated with potentially any bidding algorithm. Typically an RTB campaign often exhibits some special characteristics along certain dimensions. For example, if we observe the cost and density distribution of impressions from a campaign over the temporal dimension, we may find that different time sections demonstrate different distributions. This inspires us to design a method that optimizes by taking different segments' specific characteristics into consideration. That is, we slice an RTB campaign into several temporal segments and train different sets of bidding algorithm parameters for each segment. These sets of parameters contribute to a better outcome than the ordinary non-sliced scheme that uses the same set of parameters throughout the campaign. We also generalize the idea into a multi-dimensional segmentation framework and develop systems to optimize the overall campaign performance in both the greedy and the dynamic programming tactics. Comprehensive experiments are also conducted to show the effectiveness of the proposed framework.

並列關鍵字

real-time bidding ； demand-side platform ； bidding strategy design ； bidding with click and winning price predictors ； multi-dimensional segmentation

參考文獻

[1] D. Agarwal, S. Ghosh, K. Wei, and S. You. Budget pacing for targeted online advertisements at linkedin. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1613–1619. ACM, 2014.

[2] K. Amin, M. Kearns, P. Key, and A. Schwaighofer. Budget optimization for sponsored search: Censored learning in mdps. In Proceedings of the 28th Conf. on Uncertainty in Artificial Intelligence (UAI), 2012.

[3] H. Cai, K. Ren, W. Zhang, K. Malialis, J. Wang, Y. Yu, and D. Guo. Real-time bidding by reinforcement learning in display advertising. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, pages 661–670, 2017.

[4] J. Chen and J. Stallaert. An economic analysis of online advertising using behavioral targeting. Mis Quarterly, 38(2), 2014.

[5] Y. Cui, R. Zhang, W. Li, and J. Mao. Bid landscape forecasting in online ad exchange marketplace. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 265–273. ACM, 2011.