Yahoo! JAPANにおけるオンライン機械学習実例 #streamctjp

Yahoo! JAPANにおける オンライン機械学習実例 ヤフー株式会社 野村 拓也 2016年07月22日 http://www.yahoo.co.jp/

• http://www.yahoo.co.jp/

自己紹介 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 2

自己紹介 野村 拓也 • 業務 • 社内向けストリーム分散処理基盤の開発 • 機械学習を用いたシステム改善 • Hadoop/Stormなどの分散処理アプリの開発 • 趣味 • 苔 • ボルダリング Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 3

目次 • 今日話すこと • 背景・動機・問題設定 • ストリーム処理 • ログ処理 • 機械学習 • 結果 • まとめ Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 4

目次 • 今日話すこと • 背景・動機・問題設定 • ストリーム処理 • ログ処理 • 機械学習 • 結果 • まとめ Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 5

今日話すこと • 広告配信にオンライン機械学習を試験的に採用 • KPIが数%向上 • 構築したシステムについて • ストリーム基盤でのログの処理 • ストリーム機械学習 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 6

目次 • 今日話すこと • 背景・動機・問題設定 • ストリーム処理 • ログ処理 • 機械学習 • 結果 • まとめ Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 7

背景・動機 RecSys 2013 Tencent hourlyバッチ処理を リアルタイムに変更 → 34%のCTR改善 (資料が見つからなかったので 聴講者の写真で代用) https://twitter.com/torbenbrodt/status/390284591266668544 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 8

• https://twitter.com/torbenbrodt/status/390284591266668544

背景・動機 • Yahoo! JAPANのシステムに適用を検討したい • 特にリアルタイム性 • → 広告配信(YDN)のCTR予測 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 9

問題設定 - YDNについて http://promotionalads.yahoo.co.jp/service/ydn/ Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 10

• http://promotionalads.yahoo.co.jp/service/ydn/

問題設定 - CTR予測 • YDNは「クリック課金」の課金モデル • 期待収益の高い広告を配信したい • 期待収益 ＝ 広告クリック確率 × クリック単価 未知・状況で変化 広告主が設定 • クリック率(CTR: Click Through Rate)予測 • 現状バッチ処理で予測モデルを構築 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 11

目次 • 今日話すこと • 背景・動機・問題設定 • ストリーム処理 • ログ処理 • 機械学習 • 結果 • まとめ Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 12

再掲: 一般的なストリーム処理システム構成 サービス ログ回収 キューサーバ ストリーム処理 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 13

今回のシステム構成 Web ページ 広告配信 リクエスト ログ転送経路 配信サーバ 〜 〜 広告 クリック Kafka 内製ログ回収基盤 クリック サーバ scp scp KVS モデル配布サーバ Storm モデル転送経路 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 14

ストリーム処理 Spout(クリックログ) Spout(配信ログ) Bolt(ログ結合) Bolt(学習) Topology ディスクに書き出し モデル Stormクラスタ Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 15

ログ処理 - ログ結合 • ログ結合 • オンラインでログ結合 • JavaのLinkedHashMapを利用 • クリックログと紐付いたものは正例とする • そうでないログはサンプリングした上で負例とする Spout(クリックログ) Spout(配信ログ) ユニークIDでシャッフル Bolt(ログ結合) Bolt(ログ結合) Bolt(ログ結合) Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 16

ログ処理 - 正例・負例の排出 - 課題 1. 広告配信の有効期間=24時間のログ保持 – 有効ログを保持するとTBオーダーのメモリが必要 2. 負例の生成タイミング – クリックされないと確定するまで24時間かかる Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 17

ログ処理 - 正例を排出するための調査 • 累積クリック数の遷移 • 配信後10分待てば95%を捕捉でき十分 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 18

学習データの生成 - 正例・負例の排出 - 課題への対応 1. 広告配信の有効期間=24時間のログ保持 – 有効ログを保持するとTBオーダーのメモリが必要 – → 10分程度の配信ログを保持すれば十分 2. 負例の生成タイミング – クリックされないと確定するまで24時間かかる – → 上記の保持期間を過ぎたものを負例候補とする Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 19

目次 • 今日話すこと • 背景・動機・問題設定 • ストリーム処理 • ログ処理 • 機械学習 • 結果 • まとめ Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 20

機械学習 - バッチとの比較 バッチ学習 モデル ストリーム Logistic Regression 学習手法 Linear SVM SGD ハイパーパラメータ調整 Grid Search AdaDelta等 • ストリーム処理は逐次処理 • → 精度検証に課題 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 21

目次 • 今日話すこと • 背景・動機・問題設定 • ストリーム処理 • ログ処理 • 機械学習 • 結果 • まとめ Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 22

試験結果: KPI変化 • 一部配信面・一部トラフィックでA/Bテスト KPI 意味 KPIリフト iCTR ≒クリック率 4.1% CPC クリック単価 -2.5% RPR 1リクエストの売上 1.5% • iCTR向上 = ユーザに合った広告の配信ができた • CPC低下 = 広告主視点ではコスト削減 • RPR向上 = 売上向上 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 23

試験結果: モデル配布後のKPI変化 • 配布直後のKPIが増加傾向 RPR 配布後の経過時間 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 24

目次 • 今日話すこと • 背景・動機・問題設定 • ストリーム処理 • ログ処理 • 機械学習 • 結果 • まとめ Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 25

まとめ • CTR予測モデルの更新をリアルタイムに • ストリーム処理ならではの課題 • ログ結合、ハイパーパラメータ調整 • 試験結果としてはCTRが4%向上 • 更新間隔を短くすることでさらなる向上の可能性 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 26

質疑応答 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 27

Appendix Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 28

機械学習 - 素性とモデル • Logistic Regression ユーザ AD1 広告配信 リクエスト Web ページ • ドメイン: yahoo.co.jp • 配信面ID: 12345 配信 サーバ • 広告主ID: 123 • 広告ID: 1234567 • 過去実績: 0.1 • 性別: 男性 • 年代: 30代 • 興味カテゴリ: 車、料理 𝑓 男性, 30代, 車, 料理, … = 𝑠𝑖𝑔𝑚𝑜𝑖𝑑 𝑤𝑎 ∙ 男性 + 𝑤𝑏 ∙ 30代 + 𝑤𝑐 ∙ 車 + ⋯ Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 29

機械学習 - 学習手法 • SGD(確率的勾配降下法) • オンライン機会学習の学習手法 While(! 収束条件): 𝑓𝑜𝑟 𝑦𝑖 , 𝑥𝑖 𝑖𝑛 𝑑𝑎𝑡𝑎: 𝑤𝑡+1 = 𝑤𝑡 − 𝜂𝑡 𝛻𝑙 𝑦𝑖 , 𝑤𝑡 , 𝑥𝑖 学習率: 1回の勾配移動量を調整 基本は順次小さくする 勾配: wnの修正値 例) 𝜂𝑡+1 = 0.9 ∗ 𝜂𝑡 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 30

機械学習 - ハイパーパラメータの調整 • not オンライン、but ストリーム While(! 収束条件): 終わらない 𝑓𝑜𝑟 𝑦𝑖 , 𝑥𝑖 𝑖𝑛 𝑑𝑎𝑡𝑎: 𝑤𝑡+1 = 𝑤𝑡 − 𝜂𝑡 𝛻𝑙 𝑦𝑖 , 𝑤𝑡 , 𝑥𝑖 学習率: 1回の勾配移動量を調整 基本は順次小さくする 例) 𝜂𝑡+1 = 0.9 ∗ 𝜂𝑡 Copyright (C) 2016 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 勾配: wnの修正値 学習率の自動調整 → AdaDelta等 31