臺灣博碩士論文加值系統

實時競價廣告 (Real-Time Bidding, RTB) 在近幾年改變了網路廣告產業的運作模式。而其中，如何幫助需求方平台 (Demand-Side Platform) 在 RTB 中獲利，是許多研究者探討的主題。過去的研究中，通常將最後得標價假想由一個機率分佈所產生，但由於 RTB 本身只有得標者能獲知最後得標假的特性，DSP 所擁有的資料是一個缺損的、部分無法觀測的分佈。本篇研究將著重在如何從部分無法觀測的分佈，還原出原本的得標價分佈。基於這些因素，提出一個新的模型：遮蔽森林 (Shaded Forest)，來處理 RTB 這類部分截斷的資料。從實驗結果來看，本篇研究提出的遮蔽森林具有很好的得標價預測能力，而當無法觀測的資料比例增加時，也能有穩定的表現，並不會因此而準確率下降。

Real-Time Bidding (RTB) has changed a game changer of online advertisement. In RTB, many researchers have focus on how to maximize the profit of Demand-side platform (DSP). These researches usually consider that winning price can express as a probability distribution. However, in RTB, if a DSP lose in an auction, it will not know the winning price of that bid. Which means, what DSPs own in their data base is a partial unobserved data. In this research, we will focus on how to recover the original distribution from partial unobserved data. We propose a new model, Shaded Forest, to deal with this kind of partial unobserved data in RTB. The results of experiment show that shaded forest the accuracy of predicting winning price is better than other algorithms and have good ability to handle data with high percentage of truncation.

致謝 i
中文摘要 ii
Abstract iii
Contents iv
List of Figures vii
List of Tables viii
1. Introduction 1
2. Literature Review 6
2.1. Profit Maximization for Online Advertisement 6
2.2. Click-Through Rate for Online Advertisement 7
2.3. Winning Price Prediction 9
2.4. Data Truncation of RTB 10
2.5. Models 11
2.5.1. Truncated Distribution 11
2.5.2. Decision Tree 11
2.5.3. Random Forest 12
2.5.4. Lasso and Ridge Regression 14
3. Design of Shaded Tree and Shaded Forest 15
3.1. Truncated Normal Distribution 16
3.2. Recovery from Truncated Normal Distribution 17
3.3. Shaded Tree 18
3.4. Shaded Forest 20
4. Data 22
4.1. Dataset Overview 22
4.2. Features and Preprocessing 23
4.3. Simulation 28
5. Evaluation and Results 29
5.1. Evaluation Design 29
5.2. Parameters Tuning 30
5.3. Results 31
5.4. Result under Low Losing Rate 31
5.5. Results under Higher Losing Rate 34
6. Conclusion and Future Work 36
7. REFERENCE 37

[1]Google, " The arrival of real-time bidding and what it means for media buyers," 2011.
[2]S. Yuan, J. Wang, and X. Zhao, "Real-time bidding for online advertising: measurement and analysis," in Proceedings of the Seventh International Workshop on Data Mining for Online Advertising, 2013, p. 3.
[3]A. Ghosh, B. I. Rubinstein, S. Vassilvitskii, and M. Zinkevich, "Adaptive bidding for display advertising," in Proceedings of the 18th international conference on World wide web, 2009, pp. 251-260.
[4]W. C.-H. Wu, M.-Y. Yeh, and M.-S. Chen, "Predicting winning price in real time bidding with censored data," in Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015, pp. 1305-1314.
[5]W. H. Greene, "Econometric analysis, 5th," Ed.. Upper Saddle River, NJ, 2003.
[6]A. Bhalgat, J. Feldman, and V. Mirrokni, "Online allocation of display ads with smooth delivery," in Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, 2012, pp. 1213-1221.
[7]V. Bharadwaj, W. Ma, M. Schwarz, J. Shanmugasundaram, E. Vee, J. Xie, et al., "Pricing guaranteed contracts in online display advertising," in Proceedings of the 19th ACM international conference on Information and knowledge management, 2010, pp. 399-408.
[8]W. Zhang and J. Wang, "Statistical arbitrage mining for display advertising," in Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015, pp. 1465-1474.
[9]H. B. McMahan, G. Holt, D. Sculley, M. Young, D. Ebner, J. Grady, et al., "Ad click prediction: a view from the trenches," in Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, 2013, pp. 1222-1230.
[10]H. Cheng, R. v. Zwol, J. Azimi, E. Manavoglu, R. Zhang, Y. Zhou, et al., "Multimedia features for click prediction of new ads in display advertising," in Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, 2012, pp. 777-785.
[11]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, 2011, pp. 265-273.
[12]W. Zhang, Y. Zhang, B. Gao, Y. Yu, X. Yuan, and T.-Y. Liu, "Joint optimization of bid and budget allocation in sponsored search," in Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, 2012, pp. 1177-1185.
[13]K.-C. Lee, A. Jalali, and A. Dasdan, "Real time bid optimization with smooth budget delivery in online advertising," in Proceedings of the Seventh International Workshop on Data Mining for Online Advertising, 2013, p. 1.
[14]Y. Sun, Y. Zhou, M. Yin, and X. Deng, "On the convergence and robustness of reserve pricing in keyword auctions," in Proceedings of the 14th Annual International Conference on Electronic Commerce, 2012, pp. 113-120.
[15]A. C. Cohen Jr, "Estimating the mean and variance of normal populations from singly truncated and doubly truncated samples," The Annals of Mathematical Statistics, pp. 557-569, 1950.
[16]S. Kotz, N. Balakrishnan, and N. L. Johnson, "Continuous Multivariate Distributions, Volume 1, Models and Applications, 2nd Edition," pp. 156-158, 1994.
[17]L. Breiman, J. Friedman, C. J. Stone, and R. A. Olshen, Classification and regression trees: CRC press, 1984.
[18]L. Breiman, "Random forests," Machine learning, vol. 45, pp. 5-32, 2001.
[19]H. Liao, L. Peng, Z. Liu, and X. Shen, "iPinYou global rtb bidding algorithm competition dataset," in Proceedings of the Eighth International Workshop on Data Mining for Online Advertising, 2014, pp. 1-6.