Ad-DS Paper Circle #4

広告輪読会第四回スライド

Transcript

1. Deep Landscape Forecasting 
 for Real-time Bidding Advertising 
 
 アドテクDS勉強会 第4回 
 株式会社サイバーエージェント
 新田 拓真 / Takuma Nitta

2. 自己紹介
 新田 拓真 / Takuma Nitta 
 
 所属：AI事業本部プリズムパートナーカンパニー 
 職種：データサイエンティスト
 入社：2023年新卒入社
 業務：主に販促施策に向けた配信設計や効果検証等に従事 
 趣味：旅行✈、バレーボール🏐、語学󰑔󰎲、個人開発💻
 
 2
3. 1. 論文紹介 2. 研究背景と課題 3. 提案手法 4. 実験と評価 5. 考察とまとめ 6. 所感 7. Appendix 3
4. 1. 論文紹介 2. 研究背景と課題 3. 提案手法 4. 実験と評価 5. 考察とまとめ 6. 所感 7. Appendix 4
5. タイトル
 • Deep Landscape Forecasting for Real-time Bidding Advertising 
 
 著者
 • 上海交通大学 Data & Knowledge Management Labの方々 
 
 題材
 • RTB
 • Bid Landscape予測
 
 結論
 • 入力を工夫したRNNによるBid Landscape予測で既存手法の課題克服と性能向上に寄与 
 
 論文紹介
 5
6. 1. 論文紹介 2. 研究背景と課題 3. 提案手法 4. 実験と評価 5. 考察とまとめ 6. 所感 7. Appendix 6
7. Bid Landscape 
 • 市場価格 (2番目に高い入札額) の確率分布を予測する問題 → 勝率や市場価格の予測
 • セカンドプライスオークションでは最高入札額の次点の入札額で広告枠が取引される 
 • 入札額と入札勝率 (Win Rate) の関係を把握できるとコスト効率の良い入札戦略の立案が可能に なる
 • 市場価格より低額だとオークションで負けて機会損失になる 
 • 市場価格より高額だとオークションで勝てるが、過大評価の懸念もある 
 7
8. 関連研究 (Bid Landscape予測) 
 2つのアプローチに大別される
 • ノンパラメトリックアプローチ
 ◦ 概要：特定の分布を仮定せず、セグメント化したデータから市場価格の分布を推定 
 ◦ 利点：分布の仮定が不要 + データの特性を反映できる → 柔軟な分布の推定が可能 
 ◦ 課題：粒度が粗い + データスパース領域での予測が不安定 
 • パラメトリックアプローチ
 ◦ 概要：市場価格の分布を特定の確率分布で仮定してモデル化 
 ◦ 利点：データが少なくても安定した予測が可能 
 ◦ 課題：分布の仮定が強すぎる + 実データの複雑な分布に適合しない 
 
 8
9. 関連研究 (Bid Landscape予測) 
 両アプローチに共通する課題
 • Censorship問題
 ◦ 敗北時の市場価格が不明
 ◦ データのバイアスによる予測精度への影響 
 • 特徴量の扱い
 ◦ 非線形な相互作用の考慮が困難 
 ◦ 時系列的な依存関係の無視
 • 予測の柔軟性
 ◦ リアルタイムな市場変動への対応が困難 
 ◦ 新しいパターンへの適応能力が限定的 
 
 9 Lose
 入札価格 b
 観測可能なのは
 ここまで

10. 本研究の意義と新規性 
 以下3つの両立によって課題克服と性能向上と実用性の実現に寄与 
 • Fine-grained予測
 ◦ 個別オークションレベルでの予測を実現 
 ◦ 非線形な特徴量の相互作用を考慮 
 • Distribution-free
 ◦ 事前の分布仮定が不要
 • Censorship対応
 ◦ 勝敗両方のログを統合的に活用 
 ◦ 包括的な損失関数の設計
 ◦ 生存分析理論の拡張
 10
11. 1. 論文紹介 2. 研究背景と課題 3. 提案手法 4. 実験と評価 5. 考察とまとめ 6. 所感 7. Appendix 11
12. 前提知識
 入札価格と市場価格と勝率の関係 
 
 
 
 
 12 市場価格 z
 Win
 Lose
 入札価格 b
 入札の勝敗の概念
 勝率の
 累積分布関数(C.D.F.)
 W(b|x) 入札価格 b
 市場価格の
 確率密度関数(P.D.F.)
 p(z|x) 市場価格 z
 特徴ベクトル x
 広告情報、ユーザー情報、コンテキスト情報など
 = 競合他社の最高額

13. 予測タスクと問題設定 
 以下の設計思想で予測タスクおよびモデルを設計する 
 • 市場価格の確率分布を直接予測せず、条件付き勝率をモデル化 
 • 各価格区間での勝率を順次予測 
 • 確率の連鎖則により全体の分布を構築 
 
 13
14. 離散価格モデル 
 価格空間を離散化する
 
 
 
 
 
 確率計算を離散化する
 • 勝率　　：W(b_l) = 市場価格が b_l 未満である確率
 • 敗率　　：S(b_l) = 市場価格が b_l 以上である確率
 • 区間確率：p_l = 市場価格が区間 l に入る確率
 
 条件付き勝率の導入
 • h_l = 価格区間 l-1 まで負けている条件下で、区間 l で勝つ確率 (RNNによる予測対象) 
 14 市場価格 z Win Lose 入札額 b b_1 b_2 b_3 … b_l-1 b_l V_1 V_2 … V_l-1 V_l 入札額 b … … b_L V_L 入札の勝敗の概念
 離散価格モデル

15. 損失関数
 以下2つの損失の重み付け結合によって交互最適化して学習を安定化させている 
 • P.D.F.ベースの損失 (L_1) → 市場価格の予測が目的
 ◦ 定義：勝利ログでの実際の市場価格 z_iが観測される確率の負の対数尤度 
 ◦ 意図：実際の市場価格z_iでの確率密度を最大化したい
 • C.D.F.ベースの損失 (L_2 = L_win + L_lose) → 勝敗の予測が目的 ◦ L_win：勝利ログでの勝率予測
 ▪ 定義：入札額b_iでの勝率の負の対数尤度
 ▪ 意図：入札額b_iでの勝率( W(b)=Pr(b>z) )を最大化したい
 ◦ L_lose：敗北ログでの敗率予測
 ▪ 定義：入札額b_i以上の市場価格が出現する確率の負の対数尤度 
 ▪ 意図：入札額b_iでの敗率( S(b)=Pr(z≥b) )を最大化したい
 15
16. 実用性
 • 推論時間：平均22ミリ秒 → RTBの要件を満たす 
 • メモリ使用量：実用的な範囲
 • スケーラビリティ：大規模データセットでも安定 
 
 16
17. 1. 論文紹介 2. 研究背景と課題 3. 提案手法 4. 実験と評価 5. 考察とまとめ 6. 所感 7. Appendix 17
18. 実験設定 (データセット) 
 以下の2つのデータセットでそれぞれ評価する 
 
 
 18 iPinYouデータセット YOYIデータセット 入札回数 64.7M - 表示回数 19.5M 402M クリック回数 14.79K 500K コスト 16.0K (中国元) 428K (中国元) キャンペーン数 9 1 期間 10 days in 2013 8 days in Jan. 2016
19. 評価指標
 以下2つの指標で評価
 • ANLP (Average Negative Log Probability) 
 ◦ 市場価格分布の予測精度
 ◦ 値が小さいほど良い
 ◦ 分布の形状を直接評価
 • C-index (Concordance Index)
 ◦ 勝率予測の順序性の評価
 ◦ AUCに相当
 ◦ 値が1に近いほど良い
 
 19
20. 比較手法
 以下の手法をベースラインとして比較する 
 • ノンパラメトリックアプローチ
 ◦ KM：Kaplan-Meier推定量
 ◦ Lasso-Cox：L1正則化付きCoxモデル 
 ◦ MTLSA：マルチタスク生存分析
 ◦ DeepSurv：DNNベースのCoxモデル 
 • パラメトリックアプローチ
 ◦ Gamma：ガンマ分布回帰
 ◦ MM：混合回帰モデル
 • 最近のディープラーニング手法
 ◦ STM：Survival Tree Model
 ◦ DeepHit：確率直接予測モデル
 ◦ DWPP：深層勝率予測モデル
 ◦ RNN（DLEと同じアーキテクチャでCensorship処理なし） 
 20
21. 実験結果 (Bid Landscape予測のパフォーマンス) 
 • DLFが全てのベースラインを上回る 
 • DLFと同じ構造のRNNより著しく性能改善しており、Censorshipデータの対応が寄与 
 21
22. 実験結果 (勝利予測のパフォーマンス) 
 • RNNモデルは他の非深層ベースラインより良い性能 → 価格の順序性の学習が寄与 
 • DLFと同じ構造のRNNより著しく性能改善しており、Censorshipデータの対応が寄与 
 
 22
23. 実験結果 (モデルの収束) 
 • すぐに収束し、1エポックで安定した収束に低下している 
 • 2つの損失は、トレーニング中に交互に最適化され、学習が安定している 
 23
24. 追加分析
 • 分布予測の正確さ
 ◦ 市場価格に対応するようにWin Rateが急速に上昇している 
 ◦ DLFが真の市場価格に最も高い確率密度を正確に配置している 
 • Censorship対応
 ◦ RNNは市場価格分布と勝率をDLFと似た形で予測しているものの、勝率を過大評価 
 24
25. 1. 論文紹介 2. 研究背景と課題 3. 提案手法 4. 実験と評価 5. まとめ 6. 所感 7. Appendix 25
26. 結論と今後の展望 
 • RNNによる分布を仮定しない細かい粒度でのBid Landscape予測を提案した 
 • 価格の順序性の考慮やCensorship問題の考慮によって性能が向上した 
 • RTBに導入したい
 26
27. 1. 論文紹介 2. 研究背景と課題 3. 提案手法 4. 実験と評価 5. 考察とまとめ 6. 所感 7. Appendix 27
28. 所感
 • 価格の各区間ごとに条件付き確率を順番に予測して確率の連鎖鎖から分布全体を推定する二 段階構成のアイデアに感心
 • 推論速度が22ミリ秒で、RTBの要件を満たしていて実用的 
 • 市場価格の確率分布が提案手法において非常にフィットしているのは、 
 恐らく本手法での損失関数の設計の意図通りの挙動になっているから 
 • Google Ad Exchangeでは敗者にも市場価格が通知されるので改良の余地ありそう(?) 
 28
29. 1. 論文紹介 2. 研究背景と課題 3. 提案手法 4. 実験と評価 5. 考察とまとめ 6. 所感 7. Appendix 29
30. 生存分析
 生存分析の概要
 • 定義：ある事象 (死亡・再発等) が発生するまでの時間を分析する統計的手法 
 • 特徴：打ち切りデータ (censored data) の扱いが可能 
 • 主な応用分野：医療統計、社会学など 
 
 RTBとの親和性
 30 医療分野 RTB 事象 患者の死亡・再発 オークションでの勝利 時間 治療開始からの経過時間 入札価格 (価格空間での位置) 打ち切り 観察期間終了時に生存 敗北時の市場価格が不明