Bytedance のリアルタイム推薦システム

はじめに

この記事は、Bytedance から出版され RecSys'22 の Workshop で取り上げられた以下の論文（Monolith: Real Time Recommendation System With Collisionless Embedding Table）の内容のメモです。詳細はあまり踏み込まないので興味ある方は論文を読んでいただければと思います。

https://arxiv.org/abs/2209.07663

この論文は、一言で言うと、「実際の推薦サービスにおいてオンライン学習するためには」ということにフォーカスしてます。多くの企業では基本的にモデルの学習は、オフライン環境のバッチ処理で行うことが普通だと思います。なぜオンラインで学習する必要があるのかも含めて見ていこうと思います。この論文を選んだのは、実サービスで動くオンライン学習システムを扱っていたからです。
また一部^[1]実装が公開されてます。
https://github.com/bytedance/monolith

Monolith は BytePlus というプロダクトに導入済みと書かれています。
https://www.byteplus.com/en

オンライン学習に関する一般の資料

• https://www.datacamp.com/blog/what-is-online-machine-learning
• https://huyenchip.com/2020/12/27/real-time-machine-learning.html
• https://huyenchip.com/2022/01/02/real-time-machine-learning-challenges-and-solutions.html
• https://github.com/online-ml/awesome-online-machine-learning

以下では注釈がない画像は上の論文より拝借してます。

Introduction

論文内では、推薦モデルが言語モデルや画像モデルと大きく異なる点として

1. (Sparcity and Dynamism) 特徴量の大半がスパースで、カテゴリカルかつダイナミックに変化する
2. (Non-stationary Distribution) 学習データの分布が非定常である（Concept Drift）

という2点が挙げられています。

Sparcity and Dynamism

• 言語モデルではトークン数は多くても 100k ~ 200k のオーダーだが、推薦モデルのユーザ数やアイテム数はそれよりオーダーが大きくなることがあり、その場合は一つのホストのメモリには乗り切らない。
• さらに、新規ユーザーや新規アイテムによって embedding テーブルのサイズが時間の経過とともに大きくなることが多い。

もちろん、アイテム自体の特徴量、いわゆる、content features を使って embedding を生成する方法もあるが、この論文はあくまで id などを直接使うことを想定している。

（応用上の）既存手法

• 諦める
  • 学習データで頻度の高いもの上位 N 件のみ別々に扱いそれ以外は1つの embedding にマッピングする。
  • hash(id) mod j
• collision を防ぐ
  • linear probing
  • double hash
    • Online Learning for Recommendations at Grubhub
• 一致を避ける
  • 組み合わせの利用 Quotient-Remainder Embedding

これらの手法は、全ての ID が同じ頻度で現れるとして平等に扱っているが、実際はロングテールで少数のユーザやアイテムが高頻度で出現。
また、時間と共にテーブルが大きくなり、衝突が起こることでモデルの精度低下につながる。

Non-stationary Distribution

言語モデルや画像モデルでは数ヶ月から長いと百年というタイムオーダ（つまりほぼ時間による影響は無視）だが、推薦システムでは同じユーザでも分単位で興味が変化することがある。つまり、データは非定常であり、学習時と推論時でデータの分布が変わることを Concept Drift という。

解決法

上の2つの課題を

• 衝突しない embedding テーブル
• 高い耐障害性を持つリアルタイムオンライントレーニング

で解決しようとした論文。

Design

当該の Monolith は Tensorflow の distributed Worker-ParameterServer という機能を用いている。
https://www.tensorflow.org/tutorials/distribute/parameter_server_training?hl=ja

Worker はデータを読み込んで gradient を計算し、Parameter Server は gradient を受け取りモデルパラメタを更新するアーキテクチャである。

Hash Table

以下の3点が主な特徴です。

• Cuckoo Hashmap の利用
• 出現頻度が閾値を超えて初めて挿入する
• TTL

下2つは自明だと思うので、Cuckoo Hashmap だけ少し見ます。

Cuckoo Hashmap の利用

衝突なしに key を挿入できるハッシュマップです。

• $O(1)$ でルックアップと削除が可能
• ならし $O(1)$ で挿入が可能

仮にサイクルになった場合は、再ハッシュされる。

余談ですが、Cuckoo はカッコウ（鳥）で、以下のような恐ろしい習性を持っています。

オオヨシキリの卵をひとつ取り出し、そのあとで自分の卵をひとつ産んだのです。巣の中には、カッコウの卵と、オオヨシキリの卵がひとつずつ残されていました。およそ１２日で、カッコウのヒナが誕生します。カッコウは、オオヨシキリより早く孵ります。数時間もするとヒナはオオヨシキリの卵を外に捨てます。最後にはカッコウのヒナしか残りません。

https://www2.nhk.or.jp/school/watch/clip/?das_id=D0005400217_00000

この「追い出す」ところが同じであるところから、Cuckoo Hashmap という名前が付けられたようです。

Online Traning

• 学習はバッチとオンライン両方に対応
• 推論時の特徴量をユーザログに join する（おそらく）
  • ユーザログが届いた時点の特徴量ではない

汎用性の高いシステムにする場合に懸念すべきことは、推論時には得られない特徴量があるということである。例えば、ポジションバイアスを除去するために表示位置を特徴量に含めることは多いが、推論時は表示位置を統一して（例えば０にして）推論するはずである。そのため、学習に使う際は、ユーザログ経由で得られた実際の表示位置で特徴量を上書きする必要がある。

• ユーザログの遅れ（数日レベル）も join できるように disk レベルのキャッシュも利用
• negative sampling
  • log adds correction を用いて推論時に分布を補正
• インクリメンタルなパラメタ同期
  • モデルサイズは数テラバイト。推論を止めず、ネットワークなどにも影響を出さない同期が必要
  • sparse なパラメタがモデルの大半を占めるので、前回の同期から更新されたパラメタのみを分レベルの間隔で同期
  • dense なパラメタは同期頻度を小さくする（モーメンタムを利用したアルゴリズムでは急激な変化は起こりにくいため）
• パラメタの snapshot は daily
  • これはパラメタサーバが落ちるなどシステムの異常時のため

旧 Twitter 社のほぼ^[2]オンライン学習のシステムアーキテクチャ (2020.6) はこちらです。

Streaming logging pipeline of Home timeline prediction system の Figure 7 より

推論時の特徴量の特徴量とユーザのログから学習データを生成するところは同様のようです。^[3]

• オンライン学習では刻一刻とパラメタが更新されるため、精度のモニタリングが必要不可欠である。モニタリングの仕方として、以下の2種類がある。

  • 推論サーバーに同期する前にバリデーションをした精度のモニタリング
  • 推論サーバーに同期した後に実際のユーザログを用いた精度モニタリング

  前者の結果によってはパラメタを推論サーバに同期しない選択肢もあり得るが、そのような言及は論文中にはなかった。
  ちなみに 旧 Twitter 社のオンライン学習のシステムには前者に相当する Observation Worker が存在しているようである。
  
  Parameter Server Approach for Online Learning at Twitter より

• 仮に精度が急落した場合に、パラメタをある時点までロールバックするような機能があることが望ましいが、そのような仕組みがあるかの言及についてはなかった。

実験

実サービスの ID 数は $2^{48} = 281,473,976,710,656$ らしい。愚直にそれだけの embedding を用意するのは不可能なので、Quotient-Remainder Embedding を用いて $2^{25} = 33,554,432$ まで落としている。

「衝突なし」ハッシュテーブルは有効か

• どちらのケースでも「衝突なし」ハッシュテーブルの方が AUC が大きく性能が高い
• 実データの結果（右図）で AUC が上下しているのは Concept Drift による。（この時のパラメタ同期頻度は不明）

リアルタイムオンライン学習は重要か

• 頻度にかかわらずオンライン学習なしよりもありの方が性能が高い
• 頻度が短くなるほど性能が高くなる

• 実システムの Ads モデルでは大きな性能向上が見られた

実システムで AB をどのようにしたかに関する詳細な記述はない。
推論で用いた特徴量を学習時に利用する都合上、推論してないユーザログは学習に使えない。 そのため、仮に推論リクエストを２分割すると学習データも２分割されてしまい、学習データ量が完全なリリース状態と異なる状態が生まれてしまう。
推論リクエストをミラーして全てのモデルに流しているのだろうか。それとも学習データ量はモデルの精度に影響を与えないと仮定しているのか。

パラメタ同期の仕組みはロバストか

略

感想

• モデルサイズがこれ以上大きくなると（今話題の）分散学習も必要になってきそうだが、 model parallelism と組み合わせたりするとかなり難易度が上がりそう。
• 他にもオンライン学習を行なっている実サービスの話があれば教えてください。
• Bytedance はオンライン学習をいろんなサービスで用いるので、参考になる。実際以下のように述べている。^[4]

  Ultimately, your For You feed is powered by your feedback: the system is designed to continuously improve, correct, and learn from your own engagement with the platform to produce personalized recommendations that we hope inspire creativity and bring joy with every refresh of your For You feed.

  • https://arxiv.org/abs/2404.19357
  • https://arxiv.org/abs/2501.15817

参考

https://blog.x.com/engineering/en_us/topics/insights/2020/distributed-training-of-sparse-machine-learning-models-2
https://www.slideshare.net/slideshow/parameter-server-approach-for-online-learning-at-twitter/80869014

脚注

1. feature と log を join する Flink のコードはないです。

2. 「ほぼ」と書いたのは Kafka でリアルタイムで用意したデータを一度 HDFS に入れて、学習部分はバッチで行なっているという記述があるためです。これはあくまで記事が書かれた時点 (2020.6) の話なので今はオンライン学習になっているかもしれないですし、そもそもシステムが大きく変化してる可能性もあります。

3. Flink ではなく KSQLDB を使っているようです。また、非常に大量のデータを捌くためにデータの持ち方や downsampling などを行なっているようです。

4. https://newsroom.tiktok.com/en-us/how-tiktok-recommends-videos-for-you