YouTube推薦アルゴリズムの変遷

こちらのMedium記事を登壇で発表する機会があったため、pdf資料を公開しました。

YouTubeの推薦アルゴリズムの変遷を追う〜深層学習から強化学習まで〜
https://medium.com/eureka-engineering/youtube-recommender-algorithm-survey-341a3aa1fbd6

1. YouTube推薦アルゴリズムの変遷 〜深層学習から強化学習まで〜 Jun Ernesto Okumura Photo by Etienne Boulanger on Unsplash
2. 自己紹介：奥村 エルネスト 純 @pacocat 『データサイエンティスト養成読本 ビジネス活用編』（技術評論社） • データアナリスト ◦ ゲーム、オートモーティブ、マッチングサービス • AI研究開発エンジニア / PdM / チームリード ◦ ゲームAI・強化学習の案件推進※ • AI案件の推進 • データ利活用のための組織開発 • 強化学習 Career Interest ※ Applying AI in Games @ GDC2019 https://www.slideshare.net/juneokumura/applying-ai-in-games-gdc2019
3. Disclaimer 本資料は、Mediumで公開済みの記事のslide版になります。 （内容は記事を見れば把握できるようになっています） 内容について疑問点や修正点ある場合はTwitter : @pacocat まで連絡ください。 YouTubeの推薦アルゴリズムの変遷を追う〜深層学習から強化学習まで〜 https://medium.com/eureka-engineering/youtube-recommender-algorithm-survey-341a3aa1fbd6
4. Outline YouTubeにおける推薦アルゴリズムの変遷を以下の3本から解説します。 Deep Neural Networks for YouTube Recommendations Covington et al. 2016 (RecSys 2016) Latent Cross: Making Use of Context in Recurrent Recommender Systems Beutel et al. 2018 (WSDM 2018) Top-K Off-Policy Correction for a REINFORCE Recommender System Chen et al. 2019 (WSDM 2019) 1 2 3
5. Photo by Etienne Boulanger on Unsplash Deep Neural Networks for YouTube Recommendations Covington et al. 2016 (RecSys 2016) 1
6. Overview 概要 • Matrix FactorizationベースのアルゴリズムをDeepに置き換えて精度を改善 YouTubeにおける推薦の課題 • Scale: 数百万を超える動画を10億人以上のユーザーに推薦しないといけない • Freshness: 毎分500時間に渡る動画がアップロードされており※、 流行りなどは流動的 • Noise: 動画の視聴には様々な外部要因がある。 推薦アイテムにユーザーがどれくらい満足しているかは真には計測できない。 ※ Hours of video uploaded to YouTube every minute as of May 2019 https://www.statista.com/statistics/259477/hours-of-video-uploaded-to-youtube-every-minute/
7. YouTubeの推薦問題 • 対象ユーザーと各動画のペアから、視聴される確率を予測 : 対象ユーザーの埋め込みベクトル : 動画 の埋め込みベクトル ユーザー特徴 コンテキスト 時点で推薦する アイテム
8. 提案手法 • 推薦候補の絞り込み（数百万→数百）とランク付けを2つのDNNで実現 ① candidate generation 大雑把なアイテムの絞り込み ② ranking より精緻なランク付け
9. ① candidate generation アーキテクチャ
10. 入力特徴 • 推薦候補の絞り込み過去の視聴履歴 ◦ 視聴動画の埋め込みベクトルを平均化したもの（固定長 256次元） ◦ 論文の実験設定では過去 50件分を利用 • 過去の検索履歴 ◦ 検索内容のunigramとbigramを埋め込んで平均化したもの（固定長 256次元） ◦ 論文の実験設定では過去 50件分を利用 • 視聴地域の埋め込みベクトル • 訓練サンプルの経過時間（Example Age）と非線形変換 ◦ 推論時は0か小さな負数を入力 • ユーザーの性別 • etc…
11. Example Age特徴 • 動画には流行りがあり、モデルがどの時点で学習をしているのかを 明示的に入れる必要がある ◦ 推論時は0か小さな負数を入れることで、 training windowの最後（もしくは少し未来）で 推論していることを設定する Example Ageを入れると、 動画投稿後の視聴傾向が再現できる →
12. Training Sampleの作り方 • Training sampleを作る際には、ランダムなhold-out (左)ではなく、視聴履歴から将 来視聴する動画を予測する(右)ようにする ◦ ベーシックな協調フィルタリングでは過去と未来の情報を同時に取り扱う点に注意 • 視聴履歴は直近50件に制限 ◦ ヘビーユーザーの視聴行動に推薦が引きづられないようにする意図もあるらしい
13. ※ 機械翻訳文脈でも使われており、以下の解説記事が詳しい https://ruder.io/word-embeddings-softmax/index.html#importancesampling Softmax計算の工夫 • Softmax計算が重いためImportance Samplingを使った近似を使っている※ ◦ 他にも2分木でsoftmax計算を表現したHierarchical Softmaxなどの手法もあり、 本論文以降はそちらが活用されている • Serving時はユーザーベクトルuとアイテムベクトルvの内積空間で近傍探索 ◦ 真面目に確率を計算する必要がないため、落とせる計算量は落とす
14. ② ranking アーキテクチャ
15. 入力特徴 • ユーザーに表示した動画の埋め込みベクトル • ユーザーが視聴した動画の埋め込みベクトルの平均 • ユーザー言語と動画言語の埋め込みベクトル • 最終視聴からの経過時間と非線形変換 • 推薦回数 ◦ 過去のimpression数を入れることで「何度も推薦しているのに見られていない動画は外す」などの 学習も行われているらしい ◦ 推薦画面のリロードで見たかった動画が消えてることがあるが、この特徴のせいかも • etc…
16. Weighted Logistic Regression • 正のフィードバックを視聴時間で重み付けすることで、視聴時間の予測タスク を解くことになる ◦ サムネで視聴を煽る動画（ ”clickbeit”）に引きづられないためターゲットを視聴確率にはしない Logistic Regressionのオッズ比 Weighted Logistic Regressionのオッズ比 : # of positive impressions : # of training examples ※ P<<1より近似 : 視聴された動画の再生時間 : 動画をクリックする確率
17. 実験結果 • 既存アルゴリズムに対して、提案されたDeep手法でLossが改善
18. Photo by Etienne Boulanger on Unsplash Latent Cross: Making Use of Context in Recurrent Recommender Systems Beutel et al. 2018 (WSDM 2018) 2
19. Overview 概要 • ユーザーのコンテキスト情報をRNNに入力する際に、 Attentionとして入れる手法を提案※ 課題背景 • YouTubeの推薦システムでは、視聴時刻や場所・デバイスといったユーザーのコン テキスト情報が推薦精度に大きな役割を果たしている • コンテキストを含んだ入力特徴の相互作用を、どのようにNNに効率的に 学習させるかを知りたい ※ 日本語の解説・試験実装としては以下が分かりやすい。 WSDM2018 読み会 Latent cross making use of context in recurrent recommender systems https://www.slideshare.net/Quasi_quant2010/wsdm2018-latent-cross-making-use-of-context-in-recurrent-recommender-systemsslide ニューラルネットの推薦システムに時間・場所等のデータを活用する(Latent Cross) https://www.m3tech.blog/entry/2018/04/02/100122
20. NNにおける相互作用の学習について • NNにコンテキストを入れるには他の情報と一緒にconcatenateすればよさそう ◦ 著者達はFirst-order DNNと呼んでいる ◦ 一方で、この入力は特徴量同士の関係を明示的に入れないので、相互作用を獲得させることに なり、学習が非効率化する懸念がある • Matrix Factorizationのような行列分解手法は、ユーザーとアイテムの関係を 上手く学習できており、多くのアプリケーションで成果を出している ◦ ユーザーとアイテムを denseなベクトルで表現した上で内積を取って関係を明示的に与える ◦ 著者たちはSecond-order手法と呼んでいる • First-order DNNでSecond-order手法がどれくらい再現できるのか知りたい
21. トイタスク実験設定 • 各軸がN次元であるm軸テンソルを上式の正規分布から生成（rはランク） ◦ m=2, N=100, r=1であれば、それぞれ 100要素を持つ2個のベクトル（ユーザーベクトルとアイテムベク トル）をr=1に低ランク近似する問題と考えることができる ◦ m=2であればMatrix Factorizationで、軸を増やして（例えば時間情報を追加して） m=3とすれば Tensor Factorizationで解ける問題になる • 中間層1層のDNNを考えて、行列分解手法の結果を再現するか確認 ◦ 目的関数はMSE、OptimizerはAdagrad、再現の評価はピアソンの積率相関 ◦ 中間層のユニット数は 1-100まで様々に変化
22. トイタスク実験結果 • どの設定でも中間層の幅を広くすることで再現に成功 ◦ Matrix FactorizationをDNNで代替できそうに思える • 同mode/rankのもとで一方を増やすと精度を出すために多くのユニットが必要 ◦ 実アプリケーションでは r~200レベルの相互関係を学習することもあるため、精度を出すために 非常に大きなDNNが必要になってしまう DNNでも相互作用は学習できるが、実用レベルの問題を考えると非常に非効率になるのが問題
23. 提案手法：Latent Cross • 特徴入力をconcatenateではなく、RNN前後に要素積として作用させる ◦ Attentionとして機能させる（Maskをかける意味合い） ◦ RNNの前と後のどちらに入れるかは、問題や特徴によって考える必要がある Post-fusion • コンテキストのembeddingをGRUの出力に掛ける • 推薦結果にダイレクトに影響 Pre-fusion • コンテキストのembeddingをGRUの入力に掛ける • 中間ベクトルに影響
24. 論文で扱っているコンテキスト情報 • TimeDelta ◦ 前回の視聴から次の視聴（もしくは推論）までの時間 ◦ 先の論文でも言及されていたように、時間特徴は大切らしい • クライアント ◦ YouTubeはiOS/Android/Roku/Chromecastなど様々なデバイスで視聴されている ◦ 映画のような長時間コンテンツはモバイルよりも Rokuで視聴されやすい、などの傾向がある • ページ情報 ◦ YouTubeのトップページでは新着コンテンツが好んで視聴される一方、 動画視聴ページでは関連の高い動画をより深堀りたい視聴傾向がある
25. Latent Crossの入れ方 pre-fusion post-fusion : 入力層（GRUに入るReLUの手前） : コンテキストの埋め込みベクトル （0-mean Gaussianで初期化） : GRUからの出力 Multiple Features : 複数のコンテキスト埋め込みベクトル ↑複数featureを入れる際は学習効率を考えて積ではなく和で入れている
26. YouTubeの視聴データを使ったオフライン実験 • モデルが学習している時点から過去7日間までさかのぼり、 直近100個の視聴履歴を使って次の視聴動画の予測を行う ◦ 最終的に使われた動画は 50–200万に及んでいるため、 softmax高速化のためh-softmaxを利用 ◦ 使うコンテキストはTime Deltaに限って検証 • Map@kで、RNN x Latent Crossが好成績
27. YouTubeの視聴データを使ったオフライン実験 • Time Delta以外の特徴（クライント・デバイス）を入れるとさらに精度が改善
28. Photo by Etienne Boulanger on Unsplash Top-K Off-Policy Correction for a REINFORCE Recommender System Chen et al. 2019 (WSDM 2019) 3
29. Overview 概要 • 強化学習を使って、ユーザーの長期的なエンゲージを目指す推薦を提案 • 結果、ユーザーの視聴時間の向上と推薦アイテムの多様化を実現 課題背景 • これまでの推薦アルゴリズムでは、ユーザーの視聴履歴を教師として、 ユーザーが好みやすい動画の推薦を行っていた • その場その場で（短期的に）好みの動画を推薦するのではなく、ユーザーが長期的 にYouTubeへのエンゲージメントを高めるような推薦をしたい※ ※ 同様のビジネスアプローチは、DiDiによる配車アルゴリズムへの活用でも有名 Taxi dispatching / repositioningと強化学習活用の動向 https://speakerdeck.com/pacocat/reinforcement-learning-applications-in-taxi-dispatching-and-repositioning-domain
30. 強化学習の利用について • ある環境において長期的な収益の期待値を最大化するような行動系列を学習するの が強化学習の特徴 ◦ 収益（報酬の累積）には、距離の遠い KPIも置ける ◦ 必ずしも人間の教示が必要ではない • 本論文での設定 ◦ ユーザーの視聴時間を報酬として、ユーザーが長期的により YouTubeの動画を視聴するような 推薦モデルを作ることを考える
31. 強化学習システムの概要 時間 での ユーザー状態 アイテムの推薦 ユーザーの状態遷移モデル（環境） 推薦システム（エージェント） アイテムの推薦 報酬 報酬 時間 での ユーザー状態 時間 での ユーザー状態
32. YouTube推薦で強化学習を使う難しさ • 行動空間の広さ ◦ システムが推薦するアイテムは 1Mを超えており、それだけの行動選択肢を持っている ◦ 巨大な空間に対してどのように探索を行い、微かな報酬シグナルから学習すればいいか？ • 様々な方策の同居 ◦ サービスに投入された推薦アルゴリズムは、学習対象の強化学習エージェントだけではない ◦ 新規ユーザーに対して決定論的に特定動画を推薦するロジックなど、エージェントがコントロールでき ない複数方策が同居（自分だけでなく他人の試行錯誤からも学習する必要） • 学習の不安定さ ◦ 強化学習は実世界規模の問題ではとにかく不安定になることが活用のネック ◦ 不確かな状況下で試行錯誤をするためバリアンスは非常に大きく、バリアンスを軽減すると不要なバ イアスが持ち込まれてしまう • 複数アイテムの推薦 ◦ 行動空間が広さについて、 Top-1推薦であれば状況はまだマシで、 Top-K推薦の問題になると、 探索空間は行動の組み合わせの数だけ広がり、簡単に爆発する
33. 強化学習としての定式化
34. REINFORCEアルゴリズム
35. 複数方策が同居する問題 • YouTubeでは、集められたデータは様々な方策の出力が混ざったものになる ◦ 数時間ごとにデータを集めてパラメータ更新をするため、過去方策の影響が残る ◦ 決定論的な方策や他のモデルも存在するため、ピュアに「現方策の評価」ができない • 強化学習での対策方法 ◦ 学習対象の方策（推定方策）とは別の方策（挙動方策）の存在を認める ◦ 挙動方策の結果をサンプリングして、推定方策の学習に反映 • REINFORCEアルゴリズムはon-policy手法のため、off-policy補正が必要 ◦ On-policy手法：推定方策＝挙動方策（自分の振る舞いだけから方策を更新） ◦ Off-policy手法：推定方策 ≠ 挙動方策（他人の振る舞いデータから方策を更新）
36. REINFORCEアルゴリズムのoff-policy補正 • 軌跡の取得は挙動方策βから行い、πの更新にはImportance Samplingを使う • 一方で、この補正によってバリアンスが増大する課題も生まれる ◦ βが分母にくるため到達確率が小さい軌跡が探索されている場合は β→0となるため ◦ 特にβは多くの確率の掛け算に分解されるため、小さい値を取りやすくなる
37. Off-policy補正のvariance reduction 2つ目の近似は一見危うそうだが、この変換後もバリアンス の上界がある程度抑えられる（ Achiam et al. 2017） 他にWeight Capping, Normalized Importance Sampling, Trust Region Policy Optimizationを合わせて利用
38. off-policy補正のトイタスク実験 • 推薦アイテム（行動）が10個ある問題で補正の有効性を検証 ◦ 報酬はアイテムのインデックスで与える（つまり一番報酬が高いアイテムは a=10） ◦ 挙動方策は下式のように、 iが小さなアイテムほどたくさん選択される方策として与えてみる off-policy補正なし：βが小さいaに偏っている影響で、 πがβに引きずられる off-policy補正あり：最適（常に a=10を選択）に近い状態が実現
39. off-policy補正を組み込んだアーキテクチャ • RNN×Latent Crossを採用（前論文に引き続き） • 挙動方策βを別パラメータとして学習 ◦ 様々な同居している方策（自分以外の他人）をまとめて一つの方策として学習させている ▪ β={0,1}のような決定論的方策がいても勾配が計算しやすくなる ◦ gradientを推定方策ネットワークに流さないように伝搬を Blockしている※1 • ユーザー軌跡（実データ）からの学習※2 ◦ 挙動方策をデータから学習（ βの推定） ◦ 推定方策はより報酬が高くなる方向に学習（ πの強化学習） ※1: 別ネットワークに分離しても精度はあまり上がらなかったと報告されている ※2: シミュレータは使っていない点に注意
40. Top-k推薦の課題 • シングルアイテムの推薦であれば前頁のπの学習でOK • 組み合わせの推薦のためには、行動空間を拡張が必要 ◦ 行動空間がアイテムの組み合わせ分だけ爆発してしまうので現実的ではない
41. Top-kアルゴリズムへの拡張 • Top-k推薦をTop-1の繰り返しとして解釈 ◦ サンプリング時の重複も許容し、後で取り除く ※ ※ 重複除去後のアイテム数をどうやって担保しているかは記載がなく不明
42. Top-k REINFORCEアルゴリズム • Top-1時のREINFORCEと補正項λだけ異なる形に変形できる ◦ aが推薦されづらい時（ π→0）に報酬が発生すると、勾配は λ→K倍の更新がかかる ◦ 既にaが推薦されやすい場合（ π→1）には、λ→0に近づくため勾配の更新は抑制される
43. Top-k補正のトイタスク実験 • 報酬の高いアイテムを2つ用意し、この2つを正しく推薦するか検証 ◦ 挙動方策は簡単のため一様分布を仮定する Top-k補正なし：一番高い報酬に集中してしまい二番手が推薦されない Top-k補正あり：報酬の高い 2アイテムがちゃんと推薦される
44. YouTube環境での実験（視聴時間） • K=16の設定が一番視聴時間の増加が大きかった（最大0.8%程度） ◦ Kが減少するとパフォーマンスは悪化 ※ ◦ Kを増加させてもK=16からの変化は大きくなかった ※ 実際に推薦される動画は複数あるので、 K=1やK=2がどのような状況を際しているのかは読み取れなかった
45. YouTube環境での実験（アイテムの多様性） • Top-k off-policy補正で学習した方策は推薦アイテムを多様化した ◦ コントロール群（青）では人気の高い動画に推薦が集中してしまっている（分布が左に寄る） ◦ 本アルゴリズムのテスト群（緑）では、よりランクの低い動画も推薦される傾向が上がる ▪ 挙動方策に探索させることでより低ランク動画を引き上げやすい
46. まとめ • YouTubeの推薦アルゴリズムについて、① 深層学習の活用、② RNNへのコンテキ スト情報の導入、③ 強化学習の活用、の観点から変遷を解説した • 強化学習はoff-policy補正やTop-k補正、variance reductionなど、様々な工夫が必 要になるが、大規模なプロダクションでも活用が始まっている ◦ EC事業でも活用事例は出てきており、今後もこの傾向は加速すると思う ◦ 実際のビジネスではユーザーに悪影響のない範囲での探索に配慮する必要がありそう