Ad-DS Paper Circle #3

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

Transcript

1. Bid Shading in The Brave New World of First-Price Auctions 溝口幸宏
2. 自己紹介 2 溝口 幸宏　(Mizoguchi Yukihiro) 入社日 2022年中途入社 前職 損害保険系のデータサイエンティスト 趣味 筋トレ、英語、kaggle (健康に気を使っているのでTipsあれば是非)
3. 目次 3 1. オンライン広告オークションの背景 2. 提案手法 3. 実験と評価 1. オフライン評価 2. オンラインA/Bテスト 3. オンラインA/A/B/Bテスト 4. 結論と今後の展望
4. オンライン広告オークションの背景 - 全世界：2,500億ドル超 - - アメリカ単体：1,000億ドル超 - - 年間成長オンライン広告オークションの背景率： 20%以上 この成長を支えてきた中核技術が、広告枠の配分を決定するオークションメカニズムである 4 オンライン広告業界は黎明期から急速な成長を遂げ、 2018年の市場規模は以下の通りとなっている
5. オンライン広告オークションの背景 SPAは20年以上にわたり業界標準として機能してきた その根幹となる仕組みは 支払額_{SPA} = 次点入札額 + epsilon この方式の主要な特徴 • Vickreyプロパティ：真の価値での入札が最適戦略 • 価格決定の透明性：次点入札額に基づく明確な基準 • 運用の容易さ：戦略的考慮の必要性が低い 5 Second Price Auctionの基本原理
6. オンライン広告オークションの背景 業界全体で急速なFPAへの移行が進行 • 2017年1月：FPA採用率 0% • 2019年1月：FPA採用率 40% • 2019年12月：FPA採用率 ほぼ100% この急激な変化は、透明性の要求増大とアカウンタビリティの必要性に起因している 6 First Price Auction への移行状況
7. オンライン広告オークションの背景 FPA における基本的な価格決定 支払額_{FPA} = {入札額} この方式の特徴 • 価格の透明性：入札額がそのまま支払額 • 戦略的複雑性：最適な入札額の決定が必要 • 過払いリスク：適切な価格調整が不可欠 7 First Price Auction の価格決定メカニズム
8. オンライン広告オークションの背景 シェーディング率の定義 シェーディング率 = {真の価値見積もり}/ {実際の入札額} ある広告枠に対して、 • 広告主が考える真の価値：$5.00 • 実際に入れる入札額：$3.00 の場合、 • シェーディング率 = $3.00 / $5.00 = 0.6 (60%) 過払いを防ぎながら、適切な価格での落札を実現する手法として必須となっている 8 Bid Shading の定義と必要性
9. 提案手法 従来のCTR/CVR予測と異なり、 Bid Shading係数の推定には過去データの分析だけでなく 他の 入札者の行動予測も必要となる これらの課題に対応できる柔軟で堅牢なアルゴリズムの開発が必要 9 Bid Shading のモデリングの課題 システム要件の課題 •広告在庫の動的な変化 •予算とユーザーの常時変動 •複数の価格調整要因（ターゲティング、 CTR/CVR 予測等） •DSPシステムの変更に対する耐性が必要 データに関する課題 •最高競合入札価格の大きな変動性 •落札・失注を含む大量のデータ収集が必要 •オークションの一回性（同一条件の再現不可）
10. 提案手法 これらの課題に対応できる柔軟で堅牢なアルゴリズムの開発が必要 10 DSPのシステム概要 システム規模・構成 •40+エクスチェンジから日間 2000億+リクエストを処理 •フロントエンド：Webページ閲覧→SSP広告リクエスト →DSP入札→結果記録 •バックエンド：日次で機械学習モデル更新・配布 主な制約 •20ミリ秒以内で複数モジュールを順次処理 •並列処理非対応のため各モジュールに厳格なレイテンシー 制約
11. 提案手法 11 最適なBid Shading比率の予測手法 FMモデル • 各特徴iに対して2つの要素を学習 • 重みwi：個別の特徴の主効果 • 埋め込みベクトルvi ∈ RK：特徴間の相互作用 • 次元K=10の低次元空間で効率的に表現 FMの利点 • 計算効率：O(N²)の計算量で高速処理 • 疎データ対応：CTR/CVR予測で実績あり • 汎化性能：未出現の特徴組み合わせにも対応
12. 提案手法 12 入札余剰の最大化・支出増加・落札率向上も実現するため、独自損失関数を導入 カスタム損失関数の設計 • 基本：平均二乗誤差をベース • 拡張：非対称損失関数の導入 • 入札損失時に高ペナルティ • 余剰に応じた重み付け • 制御可能なハイパーパラメータ 最適化の特徴 • モデル式：ΦFM = w0 + Σxiwi + Σxixj⟨vi,vj⟩ • 損失関数：L = 1/N Σ(予測誤差² × 非対称項) • 標準的な勾配降下で学習可能
13. 実験と評価 13 実験と評価の概要 1. 実験設定 • 訓練データ：7日分 • テストデータ：翌日の落札データ • サンプル規模：約900万オークション/日 • 入力特徴量：13種の出版社・フィールド 2. 比較手法 • 線形回帰（LR） • 多層パーセプトロン回帰（MLP） 3. 評価指標 • 回帰性能： • 平均二乗誤差（MSE） • 決定係数（r²） • プラットフォーム性能： • 入札あたりの総余剰、総支出、落札率 • CPM（千回表示あたりのコスト）
14. オフライン評価 14 全体評価結果 機械学習アプローチの性能比較 • 回帰性能評価 • MLP：最も低性能 • 線形回帰：中間 • FM：最高性能 プラットフォーム性能指標での評価 • FMアプローチが最も優れた結果 • 最高の余剰改善・落札率
15. オフライン評価（ 目標タイプ別回帰性能分析 ) 15 目標タイプ別のFMアルゴリズムの回帰性能指標（MSEとr²） 主要な2つの目標タイプの性能が最も安定 • None（40.5%） • CPA（38.95%） 小規模目標タイプで性能低下 CPCV（0.57%） • CPViewImp（0.78%） • eCPM（3.60%） ノイズの影響が少ないシェアの大きい目標タイプで良好な性能
16. オフライン評価（ 目標タイプ別改善効果） 16 目標タイプ別の FMモデルによる性能改善率 主要な改善指標 • 余剰改善率・総支出増加率 • 落札率向上・CPM増加率 特筆すべき結果 • CPA目標で最大の余剰増加 • 全目標タイプで既存モデルを上回る • シェアの大きい目標タイプで安定した改善
17. オンライン A/Bテスト 17 目標タイプ別の FMモデルによる性能改善率 テスト設定 • 対象：LRモデルとFMモデル（MLPは除外） • 比較：非線形シェーディング 主な結果 • FMアプローチが最高性能を維持 • 実運用での改善効果 • 余剰：オフライン同等以上 • CPM増加：10%未満（オフラインの70%から大幅改善）
18. オンライン A/A/B/Bテスト 18 テスト構成 • 同一アルゴリズムの異なるサーバーでの性能比較 • 目標タイプ別の詳細分析（FMモデル） 検証結果 1. 安定性確認 1. 同一アルゴリズム間で一貫した性能 2. LR/FMともにサーバー間で類似した結果 2. FMモデルの優位性 1. すべての目標タイプで安定した改善 2. 入札余剰・総支出・落札率の向上
19. 結論と今後の展望 19 主要な成果 • 第一価格オークションにおける最適シェーディング係数の推定を実現 • FMモデルと非対称損失関数の組み合わせが優れた性能を発揮： • オフライン：18.57%の余剰改善 • オンライン：20.54%の余剰改善 • 目標タイプ別の安定性を確認 • オンラインA/Aテストでの一貫性も確認
20. 結論と今後の展望 20 今後の課題 1. モデリングの改善 1. 目標タイプごとの指標重み付けの考慮 2. 失注入札情報の活用 2. 性能向上の方向性 1. 総支出の改善 2. 入札競争のモデル化 3. ライン別パフォーマンスの向上 オンライン広告における第一価格オークションの一般化に対応し、 DSPの本番環境に適合した