Upgrade to Pro — share decks privately, control downloads, hide ads and more …

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

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

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

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

Jun Ernesto Okumura

December 24, 2019
Tweet

More Decks by Jun Ernesto Okumura

Other Decks in Technology

Transcript

  1. 自己紹介:奥村 エルネスト 純 @pacocat 『データサイエンティスト養成読本 ビジネス活用編』(技術評論社) • データアナリスト ◦ ゲーム、オートモーティブ、マッチングサービス

    • AI研究開発エンジニア / PdM / チームリード ◦ ゲームAI・強化学習の案件推進※ • AI案件の推進 • データ利活用のための組織開発 • 強化学習 Career Interest ※ Applying AI in Games @ GDC2019 https://www.slideshare.net/juneokumura/applying-ai-in-games-gdc2019
  2. 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
  3. Photo by Etienne Boulanger on Unsplash Deep Neural Networks for

    YouTube Recommendations Covington et al. 2016 (RecSys 2016) 1
  4. 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/
  5. 入力特徴 • 推薦候補の絞り込み過去の視聴履歴 ◦ 視聴動画の埋め込みベクトルを平均化したもの(固定長 256次元) ◦ 論文の実験設定では過去 50件分を利用 •

    過去の検索履歴 ◦ 検索内容のunigramとbigramを埋め込んで平均化したもの(固定長 256次元) ◦ 論文の実験設定では過去 50件分を利用 • 視聴地域の埋め込みベクトル • 訓練サンプルの経過時間(Example Age)と非線形変換 ◦ 推論時は0か小さな負数を入力 • ユーザーの性別 • etc…
  6. ※ 機械翻訳文脈でも使われており、以下の解説記事が詳しい https://ruder.io/word-embeddings-softmax/index.html#importancesampling Softmax計算の工夫 • Softmax計算が重いためImportance Samplingを使った近似を使っている※ ◦ 他にも2分木でsoftmax計算を表現したHierarchical Softmaxなどの手法もあり、

    本論文以降はそちらが活用されている • Serving時はユーザーベクトルuとアイテムベクトルvの内積空間で近傍探索 ◦ 真面目に確率を計算する必要がないため、落とせる計算量は落とす
  7. 入力特徴 • ユーザーに表示した動画の埋め込みベクトル • ユーザーが視聴した動画の埋め込みベクトルの平均 • ユーザー言語と動画言語の埋め込みベクトル • 最終視聴からの経過時間と非線形変換 •

    推薦回数 ◦ 過去のimpression数を入れることで「何度も推薦しているのに見られていない動画は外す」などの 学習も行われているらしい ◦ 推薦画面のリロードで見たかった動画が消えてることがあるが、この特徴のせいかも • etc…
  8. Weighted Logistic Regression • 正のフィードバックを視聴時間で重み付けすることで、視聴時間の予測タスク を解くことになる ◦ サムネで視聴を煽る動画( ”clickbeit”)に引きづられないためターゲットを視聴確率にはしない Logistic

    Regressionのオッズ比 Weighted Logistic Regressionのオッズ比 : # of positive impressions : # of training examples ※ P<<1より近似 : 視聴された動画の再生時間 : 動画をクリックする確率
  9. Photo by Etienne Boulanger on Unsplash Latent Cross: Making Use

    of Context in Recurrent Recommender Systems Beutel et al. 2018 (WSDM 2018) 2
  10. 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
  11. NNにおける相互作用の学習について • NNにコンテキストを入れるには他の情報と一緒にconcatenateすればよさそう ◦ 著者達はFirst-order DNNと呼んでいる ◦ 一方で、この入力は特徴量同士の関係を明示的に入れないので、相互作用を獲得させることに なり、学習が非効率化する懸念がある •

    Matrix Factorizationのような行列分解手法は、ユーザーとアイテムの関係を 上手く学習できており、多くのアプリケーションで成果を出している ◦ ユーザーとアイテムを denseなベクトルで表現した上で内積を取って関係を明示的に与える ◦ 著者たちはSecond-order手法と呼んでいる • First-order DNNでSecond-order手法がどれくらい再現できるのか知りたい
  12. トイタスク実験設定 • 各軸が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まで様々に変化
  13. トイタスク実験結果 • どの設定でも中間層の幅を広くすることで再現に成功 ◦ Matrix FactorizationをDNNで代替できそうに思える • 同mode/rankのもとで一方を増やすと精度を出すために多くのユニットが必要 ◦ 実アプリケーションでは

    r~200レベルの相互関係を学習することもあるため、精度を出すために 非常に大きなDNNが必要になってしまう DNNでも相互作用は学習できるが、実用レベルの問題を考えると非常に非効率になるのが問題
  14. 提案手法:Latent Cross • 特徴入力をconcatenateではなく、RNN前後に要素積として作用させる ◦ Attentionとして機能させる(Maskをかける意味合い) ◦ RNNの前と後のどちらに入れるかは、問題や特徴によって考える必要がある Post-fusion •

    コンテキストのembeddingをGRUの出力に掛ける • 推薦結果にダイレクトに影響 Pre-fusion • コンテキストのembeddingをGRUの入力に掛ける • 中間ベクトルに影響
  15. 論文で扱っているコンテキスト情報 • TimeDelta ◦ 前回の視聴から次の視聴(もしくは推論)までの時間 ◦ 先の論文でも言及されていたように、時間特徴は大切らしい • クライアント ◦

    YouTubeはiOS/Android/Roku/Chromecastなど様々なデバイスで視聴されている ◦ 映画のような長時間コンテンツはモバイルよりも Rokuで視聴されやすい、などの傾向がある • ページ情報 ◦ YouTubeのトップページでは新着コンテンツが好んで視聴される一方、 動画視聴ページでは関連の高い動画をより深堀りたい視聴傾向がある
  16. Latent Crossの入れ方 pre-fusion post-fusion : 入力層(GRUに入るReLUの手前) : コンテキストの埋め込みベクトル (0-mean Gaussianで初期化)

    : GRUからの出力 Multiple Features : 複数のコンテキスト埋め込みベクトル ↑複数featureを入れる際は学習効率を考えて積ではなく和で入れている
  17. Photo by Etienne Boulanger on Unsplash Top-K Off-Policy Correction for

    a REINFORCE Recommender System Chen et al. 2019 (WSDM 2019) 3
  18. Overview 概要 • 強化学習を使って、ユーザーの長期的なエンゲージを目指す推薦を提案 • 結果、ユーザーの視聴時間の向上と推薦アイテムの多様化を実現 課題背景 • これまでの推薦アルゴリズムでは、ユーザーの視聴履歴を教師として、 ユーザーが好みやすい動画の推薦を行っていた

    • その場その場で(短期的に)好みの動画を推薦するのではなく、ユーザーが長期的 にYouTubeへのエンゲージメントを高めるような推薦をしたい※ ※ 同様のビジネスアプローチは、DiDiによる配車アルゴリズムへの活用でも有名 Taxi dispatching / repositioningと強化学習活用の動向 https://speakerdeck.com/pacocat/reinforcement-learning-applications-in-taxi-dispatching-and-repositioning-domain
  19. YouTube推薦で強化学習を使う難しさ • 行動空間の広さ ◦ システムが推薦するアイテムは 1Mを超えており、それだけの行動選択肢を持っている ◦ 巨大な空間に対してどのように探索を行い、微かな報酬シグナルから学習すればいいか? • 様々な方策の同居

    ◦ サービスに投入された推薦アルゴリズムは、学習対象の強化学習エージェントだけではない ◦ 新規ユーザーに対して決定論的に特定動画を推薦するロジックなど、エージェントがコントロールでき ない複数方策が同居(自分だけでなく他人の試行錯誤からも学習する必要) • 学習の不安定さ ◦ 強化学習は実世界規模の問題ではとにかく不安定になることが活用のネック ◦ 不確かな状況下で試行錯誤をするためバリアンスは非常に大きく、バリアンスを軽減すると不要なバ イアスが持ち込まれてしまう • 複数アイテムの推薦 ◦ 行動空間が広さについて、 Top-1推薦であれば状況はまだマシで、 Top-K推薦の問題になると、 探索空間は行動の組み合わせの数だけ広がり、簡単に爆発する
  20. 複数方策が同居する問題 • YouTubeでは、集められたデータは様々な方策の出力が混ざったものになる ◦ 数時間ごとにデータを集めてパラメータ更新をするため、過去方策の影響が残る ◦ 決定論的な方策や他のモデルも存在するため、ピュアに「現方策の評価」ができない • 強化学習での対策方法 ◦

    学習対象の方策(推定方策)とは別の方策(挙動方策)の存在を認める ◦ 挙動方策の結果をサンプリングして、推定方策の学習に反映 • REINFORCEアルゴリズムはon-policy手法のため、off-policy補正が必要 ◦ On-policy手法:推定方策=挙動方策(自分の振る舞いだけから方策を更新) ◦ Off-policy手法:推定方策 ≠ 挙動方策(他人の振る舞いデータから方策を更新)
  21. off-policy補正を組み込んだアーキテクチャ • RNN×Latent Crossを採用(前論文に引き続き) • 挙動方策βを別パラメータとして学習 ◦ 様々な同居している方策(自分以外の他人)をまとめて一つの方策として学習させている ▪ β={0,1}のような決定論的方策がいても勾配が計算しやすくなる

    ◦ gradientを推定方策ネットワークに流さないように伝搬を Blockしている※1 • ユーザー軌跡(実データ)からの学習※2 ◦ 挙動方策をデータから学習( βの推定) ◦ 推定方策はより報酬が高くなる方向に学習( πの強化学習) ※1: 別ネットワークに分離しても精度はあまり上がらなかったと報告されている ※2: シミュレータは使っていない点に注意
  22. まとめ • YouTubeの推薦アルゴリズムについて、① 深層学習の活用、② RNNへのコンテキ スト情報の導入、③ 強化学習の活用、の観点から変遷を解説した • 強化学習はoff-policy補正やTop-k補正、variance reductionなど、様々な工夫が必

    要になるが、大規模なプロダクションでも活用が始まっている ◦ EC事業でも活用事例は出てきており、今後もこの傾向は加速すると思う ◦ 実際のビジネスではユーザーに悪影響のない範囲での探索に配慮する必要がありそう