TECHNOLOGY NLP AI

【日本語訳】Monolith: Real Time Recommendation System With Collisionless Embedding Table【TikTok,ByteDance】

2023年4月21日

悩んでいる人

Monolith: Real Time Recommendation System With Collisionless Embedding Tableの日本語訳を教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOS(Linuxカーネル)の授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校(UNC)コンピュータサイエンス学部で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発.
  • プログラミング歴15年以上,習得している言語: C/C++PythonSolidity/Vyper,Java,Ruby,Go,Rust,D,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開
  • 2020年1月~現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務.2022年6月~現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO.
  • 最近は自然言語処理AIイーサリアムに関する有益な情報発信に従事.
    • (AI全般を含む)自然言語処理AIの論文の日本語訳や,AIチャットボット(ChatGPT,Auto-GPT,Gemini(旧Bard)など)の記事を50本以上執筆.アメリカのサンフランシスコ(広義のシリコンバレー)の会社でプロンプトエンジニア・マネージャー・Quality Assurance(QA)の業務委託の経験あり.
    • (スマートコントラクトのプログラミングを含む)イーサリアムや仮想通貨全般の記事を200本以上執筆.イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり.

こういった私から学べます.

AIのプログラミング言語「C++/Python言語」を学べるおすすめのWebサイトを知りたいあなたはこちらからどうぞ.

独学が難しいあなたは,AIを学べるオンラインプログラミングスクール3社で自分に合うスクールを見つけましょう.後悔はさせません!

国内・海外のAIエンジニアのおすすめ求人サイトを知りたいあなたはこちらからどうぞ.

国内・海外のプロンプトエンジニアのおすすめ求人サイトを知りたいあなたはこちらからどうぞ.

Monolith: Real Time Recommendation System With Collisionless Embedding Tableの日本語訳を紹介します.

※図表を含む論文の著作権はMonolith: Real Time Recommendation System With Collisionless Embedding Tableの著者に帰属します.

TikTokの推薦アルゴリズム「Monolith」がわかります.

Monolith: Real Time Recommendation System With Collisionless Embedding Tableの目次は以下になります.

  • Abstract
  • 1章:INTRODUCTION
  • 2章:DESIGN
  • 3章:EVALUATION
  • 4章:RELATED WORK
  • 5章:CONCLUSION
  • ACKNOWLEDGMENTS

Monolith: Real Time Recommendation System With Collisionless Embedding Tableを解説しつつ,私の考えも語ります.

Monolith: Real Time Recommendation System With Collisionless Embedding Tableの概要と私の日本語訳は以下になります.

Building a scalable and real-time recommendation system is vital for many businesses driven by time-sensitive customer feedback, such as short-videos ranking or online ads.
スケーラブルでリアルタイムな推薦システムの構築は,ショート動画のランキングやオンライン広告など,時間に敏感な顧客フィードバックによって駆動される多くのビジネスにとって不可欠である.

Despite the ubiquitous adoption of production-scale deep learning frameworks like TensorFlow or PyTorch, these general-purpose frameworks fall short of business demands in recommendation scenarios for various reasons:
TensorFlowやPyTorchのようなプロダクションスケールの深層学習フレームワークが至る所で採用されているにもかかわらず,これらの汎用フレームワークは,様々な理由で推薦シナリオにおけるビジネス需要に欠けている.

on one hand, tweaking systems based on static parameters and dense computations for recommendation with dynamic and sparse features is detrimental to model quality;
一方では,動的で疎な特徴を持つ推薦のために,静的なパラメータと高密度な計算に基づいてシステムを調整することは,モデルの品質を損なうことになる.

on the other hand, such frameworks are designed with batch-training stage and serving stage completely separated, preventing the model from interacting with customer feedback in real-time.
他方,このようなフレームワークは,バッチ訓練ステージとサービスステージを完全に分離して設計されており,モデルがリアルタイムで顧客のフィードバックと相互作用することを妨げている.

These issues led us to reexamine traditional approaches and explore radically different design choices.
これらの問題から,我々は従来のアプローチを再検討し,根本的に異なる設計の選択肢を模索することになりました.

In this paper, we present Monolith, a system tailored for online training.
本論文では,オンライン訓練に特化したシステム「Monolith」を紹介する.

※Monolithのコードは近日公開予定である.(訳注:https://github.com/bytedance/monolithに公開済み)

Our design has been driven by observations of our application workloads and production environment that reflects a marked departure from other recommendations systems.
Monolithの設計は,アプリケーションのワークロードとプロダクション環境の観察に基づいており,他の推薦システムとは著しく異なっている.

Our contributions are manifold: first, we crafted a collisionless embedding table with optimizations such as expirable embeddings and frequency filtering to reduce its memory footprint;
我々の貢献は多岐にわたる.第1に,衝突のない埋め込みテーブルを作成し,有効期限付きの埋め込みや周波数フィルタリングなどの最適化によって,メモリフットプリントを削減した.

second, we provide an production-ready online training architecture with high fault-tolerance;
第2に,高いフォールトトレラント性を持つ,プロダクション可能なオンライン訓練アーキテクチャを提供した.

finally, we proved that system reliability could be traded-off for real-time learning.
最後に,システムの信頼性はリアルタイム学習とのトレードオフであることを証明した.

Monolith has successfully landed in the BytePlus Recommend product.
Monolithは,BytePlusのRecommend製品に採用されることに成功した.

https://arxiv.org/abs/2209.07663

私の日本語訳の注意点は以下になります.

  • 概要は英語と日本語を両方掲載しましたが,本文は私の日本語訳のみを掲載していること(英語で読みたいあなたは原文を読みましょう!)
  • 基本的には原文の直訳ですが,わかりにくい箇所は意訳や説明を追加している箇所があること
  • 原文の「ACKNOWLEDGMENTS」(謝辞)は省略していること
  • 本文中に登場する表記「[5, 6, 10, 12, 20, 21]」などは参考文献ですので,興味がある方は本記事の参考文献を参照されたいこと

それでは,Monolith: Real Time Recommendation System With Collisionless Embedding Tableの本文を読みすすめましょう!

1章:Introduction(はじめに)

過去10年間,推薦技術を利用したビジネスが盛んに行われてきた.

より良い顧客体験を追求するため,個々のユーザに対してパーソナライズされたコンテンツをリアルタイムに提供することが,これらのビジネスアプリケーションの共通の目標となっている.

そのため,ユーザの最新のインタラクションの情報は,ユーザのポートレートを最もよく描き,ユーザの興味や将来の行動を予測することができるため,モデルを学習するための主要な入力として使用されることが多い.

ディープラーニングは,膨大な量のユーザデータが大量データ駆動型ニューラルモデルに自然に適合することから,推薦モデルを支配してきた[5, 6, 10, 12, 20, 21].

しかし,業界レベルの推薦システムで深層学習の力を活用しようとすると,現実のユーザ行動から得られるデータのユニークな特徴に起因する問題に常に遭遇することになる.

これらのデータは,言語モデリングやコンピュータビジョンのような従来のディープラーニングの問題で使われるものとは,2つの点で大きく異なっている.

  1. 特徴量はスパース,カテゴリー,ダイナミックに変化することがほとんどである.
  2. 訓練データの分布が非定常である,別名「コンセプトドリフト」[8].

このような違いは,推薦システムに携わる研究者や技術者にユニークな課題を突きつけている.

1.1節:Sparsity and Dynamism(スパース性とダイナミズム)

推薦のためのデータは,ほとんどが疎なカテゴリー特徴量を含んでおり,その中には低い頻度で現れるものもある.

これらを高次元埋め込み空間にマッピングすることは,一般的に行われていることであり,一連の問題を生じさせる.

  • 単語数が限られている言語モデルとは異なり,ユーザやランキングの項目は桁違いに多い.このような巨大な埋め込みテーブルは,1つのホストのメモリに収まることはまずないだろう.
  • さらに悪いことに,[1, 17]のようなフレームワークでは,固定サイズの密な変数を使って埋め込みテーブルを表現しているが,埋め込みテーブルのサイズは,ユーザやアイテムが増えるにつれて時間とともに大きくなることが予想される.

実際には,多くのシステムで,メモリフットプリントを削減し,IDの成長を可能にする方法として,低衝突ハッシュ[3, 6]が採用されている.

これは,埋め込みテーブルのIDが均等に分布しており,衝突してもモデルの品質には影響がないという過大な理想論に基づくものである.

残念ながら,現実の推薦システムでは,少数のユーザやアイテムの出現頻度が著しく高くなるため,このようなことはほとんど起こらない.

埋め込みテーブルのサイズが有機的に増大すると,ハッシュキーの衝突の可能性が高まり,モデルの品質を低下させることになる[3].

そのため,プロダクションスケールの推薦システムには,できるだけ多くの特徴をパラメータに取り込み,さらに,帳尻を合わせようとするユーザやアイテムの数を弾力的に調整する機能が当然のように求められる.

1.2節:Non-stationary Distribution(非定常的な分布)

視覚的・言語的なパターンは数百年単位で変化し,あるトピックに興味を持った同じユーザが,次の瞬間にはその熱意が変化していることもある.

その結果,ユーザデータの根本的な分布は非定常となり,一般にコンセプトドリフトと呼ばれる現象が発生する[8].

直感的には,より新しい履歴からの情報は,より効果的にユーザの行動変化を予測することに貢献することができる.

コンセプトドリフトの影響を軽減するためには,ユーザの最新の興味を反映させるために,新しいユーザフィードバックからできるだけリアルタイムにモデルを更新する必要がある.

我々は,このような問題点を解決するために,大規模推薦システムMonolithを設計した.

我々は,プロダクション環境での設計を検証し,反復するために大規模な実験を行った.

Monolithは,以下のような機能を備えている.

  1. 非衝突ハッシュテーブルと動的特徴量追い出し機構を設計することで,スパース特徴量の表現力をフルに発揮する.
  2. オンライン訓練で,リアルタイムに訓練にフィードバックすることができる.

Monolithは,このようなアーキテクチャの能力を活かして,衝突を伴うハッシュトリックを採用したシステムに対して,ほぼ同等のメモリ使用量で常に高い性能を発揮し,サーバの計算能力に過度の負担をかけることなく,最先端のオンラインサービスAUCを達成する.

本論文の残りの部分は,以下のように構成されている.

まず2章で,Monolithが衝突のないハッシュテーブルとリアルタイム訓練によって既存の課題に取り組む方法について,設計の詳細を詳しく説明する.

3章では,実験と結果,そして実機で検証した結論と,時間感度,信頼性,モデル品質間のトレードオフに関するいくつかの議論を紹介する予定である.

4章では,関連する研究を要約し,それらをMonolithと比較する.

5章では,本研究の結論を述べる.

2章:DESIGN(設計)

Monolith Figure2
図2:Worker-PSアーキテクチャ.

Monolithの全体的なアーキテクチャは,概ねTensorFlowのdistributed Worker-ParameterServerの設定に準拠している(図2).

※訳注:図1より図2が先に参照されていますが,図1は2.2節で参照します.

Worker-PSアーキテクチャでは,マシンに異なる役割が割り当てられる.

Workerマシンはグラフで定義された計算を実行し,PSマシンはパラメータを保存し,Workerが計算した勾配に従ってパラメータを更新する役割を担っている.

推薦モデルでは,パラメータは密と疎の2種類に分類される.

密なパラメータはディープニューラルネットワークの重み/変数であり,疎なパラメータは疎な特徴に対応する埋め込みテーブルを意味する.

我々の設計では,密なパラメータも疎なパラメータもTensorFlow Graphの一部であり,パラメータサーバに格納される.

TensorFlowの密なパラメータに対するVariableと同様に,疎なパラメータに対する高効率,非衝突,柔軟なHashTable操作のセットを設計した.

TensorFlowの学習と推論の分離に起因する制限を補完するために,Monolithの弾性的にスケーラブルなオンライン訓練は,フォールトトレラント性機構によってモデルの堅牢性を保証しつつ,短い間隔で学習PSからオンラインサービスPSにパラメータを効率的に同期させるように設計されている.

2.1節:Hash Table(ハッシュテーブル)

疎なパラメータ表現の設計の第一原則は,異なるIDの情報を同じ固定サイズの埋め込みに詰め込むことを避けることである.

TensorFlowのVariableで動的なサイズの埋め込みテーブルをシミュレートすると,必然的にIDの衝突が起こり,新しいIDが到着してテーブルが大きくなるにつれて悪化する.

そこで,Variableをベースにするのではなく,疎なパラメータ用のキーバリューHashTableを新規に開発した.

Monolith Figure3
図3:Cuckoo HashMap.

HashTableはCuckoo Hashmap[16]を利用しており,既存のキーと衝突することなく新しいキーを挿入することをサポートしている.

Cuckoo Hashingは,ルックアップと削除で最悪の場合\(\mathcal{O}(1)\)の時間計算量を達成し,挿入では期待通りの償却時間\(\mathcal{O}(1)\)を達成している.

図3に示すように,異なるハッシュ関数\(h_0 (x)\),\(h_1 (x)\)を持つ2つのテーブル\(T_0\),\(T_1\)を保持し,要素はそのどちらかに格納される.

※訳注:図1より図3が先に参照されていますが,図1は2.2節で参照します.

要素Aを\(T_0\)に挿入する場合,まず\(h_0 (A)\)にAを置こうとする.

もし\(h_0 (A)\)が他の要素Bで占められていたら,\(T_0\)からBを追い出し,同じ論理で\(T_1\)への挿入を試す.

このプロセスは,すべての要素が安定するまで繰り返されるか,挿入がサイクルに陥ったときに再ハッシュが発生する.

メモリフットプリントの削減も,我々の設計では重要な考慮事項である.

新しいIDをすべてHashTableに挿入するという素朴なアプローチでは,メモリがすぐに枯渇してしまう.

実際のプロダクションモデルを観察した結果,2つの結論が導き出された.

  1. ほんの一握りの回数しか出現しないIDは,モデルの品質向上への貢献度は低い.IDはロングテール分布をしており,人気のあるIDは数百万回出現するが,人気のないIDは10回以下しか出現しないという重要な観察結果がある.これらの頻度の低いIDに対応する埋め込みは,学習データの不足により適合度が低く,モデルはこれに基づいて正しい推定を行うことができない.結局のところ,これらのIDは結果に影響を与えないので,出現頻度の低いIDを削除してもモデルの品質が低下することはない.
  2. 遠い過去に作られた古いIDは,その多くが一度も訪問されていないため,現在のモデルに貢献することはほとんどない.これはおそらく,もうアクティブでないユーザや,古くなったショート動画が原因である可能性がある.このようなIDの埋め込みを保存しても,モデルには何の役にも立たないどころか,無駄にPSメモリを消耗することになる.

これらの観察に基づき,我々はHashTableをよりメモリ効率よく実装するために,いくつかの特徴IDフィルタリングのヒューリスティックを設計した.

  1. IDは,埋め込みテーブルに認められる前にフィルタリングされる.フィルタリングの方法は2種類ある.まず,キーとして挿入される前に,IDの出現頻度によってフィルタリングを行う.ここで,出現頻度の閾値は,モデルごとに異なる調整可能なハイパーパラメータである.さらに,メモリ使用量を削減するために,確率的なフィルタリングを利用している.
  2. IDには時間が設定されており,あらかじめ定義された期間,非アクティブになると失効するように設定されている.また,履歴情報に対する感度が異なる特徴量を区別するために,埋め込みテーブルごとに有効期限を調整することができる.

我々の実装では,HashTableはTensorFlowリソース操作として実装されている.

Variableと同様に,ルックアップとアップデートもTensorFlowのネイティブオペレーションとして実装されており,統合が容易で互換性が高い.

2.2節:Online Training(オンライン訓練)

Monolith Figure1
図1:Monolithオンライン訓練のアーキテクチャ.

Monolithでは,訓練は2つのステージに分かれている(図1).

  1. バッチ訓練ステージ.このステージは,通常のTensorFlow訓練ループとして動作する.各訓練ステップでは,訓練ワーカーがストレージから1つのミニバッチの訓練例を読み込み,PSからパラメータを要求し,フォワードパスとバックワードパスを計算し,最後に訓練PSに更新パラメータをプッシュする.他の一般的な深層学習タスクとは若干異なり,データセットを1パス分しか訓練しない.バッチ訓練は,モデルアーキテクチャを変更してモデルを再訓練する際に,過去のデータを訓練するのに便利である.
  2. オンライン訓練ステージ.モデルがオンラインサービスにデプロイされた後,訓練は停止せず,オンライン訓練ステージに入る.ストレージからミニバッチ例を読み込む代わりに,訓練ワーカーがリアルタイムデータをオンザフライで消費し,訓練PSを更新する.訓練PSは定期的にパラメータをサービスPSに同期させ,ユーザ側ですぐに効果を発揮する.これにより,本モデルはユーザのフィードバックに応じてリアルタイムでインタラクティブに適応することができる.

2.2.1項:Streaming Engine(ストリーミングエンジン)

Monolith Figure4
図4:ストリーミングエンジン.

Monolithは,バッチ訓練とオンライン訓練をシームレスに切り替えることができるように構築されている.

これは,図4に示すように,ストリーミングエンジンの設計によって実現されている.

我々の設計では,ユーザのアクション(例:アイテムのクリック,アイテムの「いいね」など)を記録するために1つのKafka[13]キューを使用し,特徴量用に別のKafkaキューを使用している.

エンジンの中核となるのは,Flink[4]のストリーミングジョブで,オンライン特徴量Joinerのためのものである.

このオンラインJoinerは,特徴量とユーザアクションからのラベルを連結して訓練例を生成し,それをKafkaキューに書き出す.

訓練例のためのキューは,オンライン訓練とバッチ訓練の両方で消費される.

  • オンライン訓練では,訓練ワーカーがKafkaキューから直接データを読み取る.
  • バッチ訓練では,まずデータダンプジョブがデータをHDFSにダンプする[18].HDFSにデータが一定量溜まったら,訓練ワーカーがHDFSからデータを取り出してバッチ訓練を行う.

訓練PSで更新されたパラメータは,パラメータ同期スケジュールに従って,サービスPSにプッシュされる.

2.2.2項:Online Joiner(オンラインJoiner)

Monolith Figure5
図5:オンラインJoiner.

実際のアプリケーションでは,ユーザの行動ログと特徴量が時間順を保証することなくオンラインJoiner(図5)にストリーミングされる.

そこで,ユーザアクションと特徴量が正しくペアリングできるように,各リクエストにユニークなキーを使用している.

また,ユーザのアクションの遅れも問題になる可能性がある.

例えば,数日前に提示された商品を購入すると決めるまで,ユーザは数日かかるかもしれない.

すべての特徴量をキャッシュに保存すると,単純にメモリに収まらなくなるため,これはJoinerにとっての課題である.

我々のシステムでは,ディスク上のキーバリューストレージを利用して,一定期間以上待たされる特徴量を保存している.

ユーザの行動ログが届くと,まずメモリ内のキャッシュを検索し,キャッシュがない場合はキーバリューストレージを検索する.

また,実世界のアプリケーションでは,ネガティブな例とポジティブな例の分布が非常に不均一であり,前者の数が後者より数桁多いという問題が発生することがある.

ポジティブな例がネガティブな例に圧倒されるのを防ぐために,一般的な戦略としてネガティブサンプリングが行われる.

この場合,訓練済みモデルの基本的な分布は確実に変化し,ポジティブな予測を行う確率が高くなるように調整される.

このため,オンラインモデルが元の分布の不偏推定であることを確認するため,ログオッズ補正[19]を適用している.

2.2.3項:Parameter Synchronization(パラメータ同期)

オンライン訓練中,Monolith訓練クラスタはオンラインサービスモジュールからデータを受け取り続け,訓練PSのパラメータを更新する.

オンラインサービスPSが新しく学習したパラメータを利用するためには,更新されたモデルパラメータの同期が重要なステップとなる.

プロダクション環境では,以下のような課題がある.

  • オンラインサービスPS上のモデルは,更新時にサービスを停止してはならない.プロダクションのモデルは通常数テラバイトのサイズであり,その結果,すべてのパラメータを置き換えるには時間がかかる.リプレイスメントの際に,オンラインPSがモデルのサービスを停止するのは忍びなく,更新はオンザフライで行う必要がある.
  • 数テラバイトのモデル全体を訓練PSからオンラインサービスPSに転送する場合,新たに到着したモデルを受け入れるために2倍のモデルサイズのメモリを必要とするため,PSのネットワーク帯域幅とメモリの両方に大きな負担がかかると考えられる.

オンライン訓練がビジネスシナリオの規模に対応できるよう,Monolithでは,モデルの顕著な特徴量に基づき,インクリメンタルなオンザフライで定期的なパラメータ同期機構を設計した.

  1. 疎なパラメータが推薦モデルのサイズを支配している.
  2. 短い範囲のタイムウィンドウを与え,IDのごく一部しか訓練せず,それらの埋め込みを更新する.
  3. 密な変数の動きは,疎な埋め込みデータよりもはるかに遅い.これは,モメンタムベースのオプティマイザでは,密な変数のモメンタムの蓄積は,推薦訓練データの巨大なサイズによって拡大される一方,1つのデータバッチで更新を受けるスパース埋め込みはわずかであるためである.

(1)と(2)により,すべての特徴量IDにまたがるスパースな更新を利用することができる.

Monolithでは,最後のパラメータ同期以降にエンベッディングが学習されたIDを表す,タッチキーのハッシュセットを保持している.

我々は,タッチキーセットに含まれるキーを持つ疎なパラメータのサブセットを,訓練PSからオンラインサービスPSへ,分単位の時間間隔でプッシュする.

このような比較的小さくインクリメンタルなパラメータ更新のパックは,ネットワーク伝送のために軽量であり,同期中に急激なメモリスパイクを引き起こすことはないであろう.

また,(3)を利用して,疎なパラメータの同期スケジュールをより積極的に設定し,密なパラメータの更新頻度を低くすることで,ネットワークI/Oとメモリ使用量をさらに削減した.

このため,疎なパラメータと比較して,密なパラメータが比較的古いバージョンであるという状況が発生する可能性がある.

しかし,このような矛盾は,(3)で述べた理由によって,目立った損失が観察されないため,許容される可能性がある.

2.3節:Fault Tolerance(フォールトトレランス)

Monolithは実稼働中のシステムとして,PSが故障した場合に復旧できるように設計されている.

フォールトトレランスの一般的な選択は,定期的にモデルの状態をスナップショットし,PSの障害が検出されたときに最新のスナップショットから回復することである.

スナップショットの頻度の選択は,次の2つの大きな影響を及ぼす.

  1. モデルの品質:直感的には,スナップショット頻度が高くなると,最近の履歴の喪失によるモデルの質の低下は少なくなる.
  2. 計算のオーバーヘッド:マルチテラバイトのモデルをスナップショットするのは無料ではない.メモリコピーとディスクI/Oの大きなチャンクが発生する.

モデルの品質と計算オーバーヘッドのトレードオフとして,Monolithは毎日すべての訓練PSをスナップショットする.

障害が発生した場合,PSは1日分の更新を失うことになるが,実験を通じて性能低下は許容範囲内であることがわかった.

次の章では,PSの信頼性の効果について分析する.

3章:EVALUATION(評価)

我々の提案する設計がもたらす利点とトレードオフをよりよく理解するために,我々は,さまざまな側面からMonolithを評価し検証するために,プロダクション規模でのいくつかの実験とライブサービスのトラフィックでA/Bテストを実施した.

我々は,実験によって以下の質問に答えることを目的としている.

  1. 非衝突HashTableの恩恵はどの程度受けられるのでしょうか?
  2. リアルタイムのオンライン訓練の重要性は?
  3. Monolithのパラメータ同期設計は,大規模なプロダクションシナリオにおいて十分なロバスト性を持っているのでしょうか?

本章では,まず実験設定を紹介し,その後に結果と我々の発見を詳細に説明する.

3.1項:Experimental Setup(実験セットアップ)

3.1.1項:Embedding Table(埋め込みテーブル)

2.1節で説明したように,Monolithの埋め込みテーブルは,非衝突のHashTablesとして実装されている.

埋め込みテーブルの衝突回避の必要性を証明し,非衝突実装による利点を定量化するために,Movielensデータセットと社内プロダクションデータセットのそれぞれで2グループの実験を行った.

Monolith FIgure6
図6:DeepFMモデルのアーキテクチャ.

Monolith Table1
表1:ハッシュ化前と後のIDの統計値.

  1. MovieLens ml-25mデータセット[11]:
    約162000人のユーザと62000本の映画に関わる2500万件の評価を含む,映画評価の標準的な公開データセットである.
    • ラベルの前処理.元のラベルは0.5から5.0までの評価だが,プロダクションではタスクはユーザから2値信号を受け取ることがほとんどである.プロダクションモデルをよりよくシミュレートするために,「スコア≧3.5」をポジティブサンプル,残りをネガティブサンプルとして扱うことで,スケールラベルを2値ラベルに変換している.
    • モデルとメトリクス.推薦問題でよく使われるモデルアーキテクチャである標準的なDeepFM[9]モデルを実装した.これは,FMコンポーネントとdenseコンポーネントで構成されている(図6).
      ※訳注:denseコンポーネントは,MLPコンポーネントのことだと思います.
      予測はAUC[2]によって評価され,これは実際のモデルの主要な測定値である.
    • 埋め込み衝突.このデータセットには,約16万個のユーザIDと約6万個の映画IDが含まれている.埋め込みテーブルの衝突のない実装と比較するために,IDをMD5ハッシュで前処理し,より小さなID空間にマッピングする別の実験グループを行った.その結果,一部のIDは他のIDと埋め込みを共有することになる.表1は,ハッシュ化前とハッシュ化後のユーザIDおよび映画IDの詳細な統計データである.
  2. 社内推薦データセット
    また,プロダクション環境における推薦モデルの実験も行った.このモデルは一般的にマルチタワーアーキテクチャを採用しており,各タワーは特化した種類のユーザ行動を予測するための学習を担当する.
    • 各モデルには約1000個の埋め込みテーブルがあり,埋め込みテーブルの大きさの分布は非常に不均一である.
    • 埋め込みテーブルの元のID空間は\(2^{48}\)である.我々のベースラインでは,埋め込みテーブルのサイズを小さくするために,分解によるハッシュ化手法を適用している.具体的には,1つの巨大な埋め込みテーブルではなく,2つの小さな埋め込みテーブルを使い,ベクトルの組み合わせによって,各IDに対してユニークな埋め込みを生成している.
      $$ID_r = ID \% 2^{24} \\ ID_q = ID ÷ 2^{24} \\ E = E_r + E_q$$
      ここで,\(E_r\),\(E_q\)は,\(ID_r\),\(ID_q\)に対応する埋め込みである.これにより,埋め込みテーブルのサイズは\(2^{48}\)から\(2^{25}\)に効果的に削減される.
    • このモデルは実際のプロダクションで使用されており,本実験の性能は,実際に使用されているトラフィックを用いたオンラインAUCで測定されている.

3.1.2項:Online Training(オンライン訓練)

オンライン訓練中は,分レベルの間隔で最新のパラメータセットでオンラインサービスPSを更新している.

モデルの品質とシステムの堅牢性を検証するために,2つの実験グループを設計した.

Monolith Algorithm1
アルゴリズム1:シミュレートされたオンライン訓練

  1. 更新頻度:
    分レベルの更新頻度の必要性を検討するため,訓練モデルから予測モデルへのパラメータの同期を異なる間隔で行う実験を行った.
    使用するデータセットは,CTRモデルのベンチマーク用の大規模な標準データセットであるCriteo Display Ads Challenge datasetである.特徴量やクリックアクションを記録した時系列に並んだ7日間のデータが含まれている.この実験では,図6で説明したように,標準的なDeepFM[9]モデルを使用する.
    オンライン訓練をシミュレートするために,データセットに対して以下の前処理を行った.データセットから7日分のデータを取り出し,バッチ訓練用の5日分のデータとオンライン訓練用の2日分のデータに分割する.さらに,2日分のデータを時系列にNシャードに分割する.オンライン訓練はアルゴリズム1によってシミュレートされる.
    そのため,データシャードの数によって決まる間隔で,訓練したパラメータをオンラインサービスPSに同期させるシミュレーションを行った.更新間隔が5hr,1h,30minにほぼ対応するN=10,50,100で実験した.
  2. ライブ実験:
    さらに,オンライン訓練の重要性を実世界で実証するため,実際の配信トラフィックを使ったライブ実験も行った.このA/B実験では,当社の広告モデルの1つをプロダクションで使用し,オンライン訓練とバッチ訓練を比較した.

3.2節:Results and Analysis(結果および分析)

3.2.1項:The Effect of Embedding Collision(埋め込み衝突の効果)

Monolith Figure7
図7:DeepFM,MovieLensにおける埋め込み衝突の影響

Monolith Figure8
図8:プロダクション中の推薦モデルにおける埋め込み衝突の効果.
この推薦モデルの性能を,コンセプトドリフトにより日ごとに変動するオンラインサービスAUCで測定している.

MovieLensデータセットと社内推薦データセットの結果は,いずれも衝突を埋め込むとモデルの品質が低下することを示している.

  1. 衝突のないHashTableを使用したモデルは,衝突のあるモデルを常に凌駕している.この結論は,以下の条件に関係なく成立する.
    • 訓練エポック数の増加.図7に示すように,衝突のない埋め込みテーブルを用いたモデルは,最初のエポックからAUCが高くなり,高い値で収束する.
    • コンセプトドリフトによる時間経過に伴う分布の変化.図8に示すように,衝突のない埋め込みテーブルを用いたモデルも,時間の経過やユーザ/アイテムのコンテキストが変化してもロバストであることがわかる.
  2. 非衝突埋め込みテーブルによるデータの疎密は,モデルのオーバーフィッティングを引き起こさない.図7に示すように,非衝突埋め込みテーブルを用いたモデルは,収束した後もオーバーフィットすることはない.

3.2.2項:Online Training: Trading-off Reliability For Realtime(オンライン訓練:信頼性とリアルタイム性のトレードオフ)

Monolith Figure9
図9:Criteoデータセットにおけるオンライン訓練vs.バッチ訓練.
青線:オンライン訓練によるモデルのAUC,黄線:バッチ訓練モデルのAUCをストリーミングデータに対して評価したもの.

Monolith Figure10
図10:オンライン訓練の同期間隔の違いによる比較.

Monolith Table2
表2:CriteoデータセットにおけるDeepFMモデルの平均AUC比較.

Monolith Table3
表3:AdsモデルのライブA/B実験による,オンライン訓練のバッチ訓練に対する改善効果.

その結果,パラメータ同期頻度が高いほどオンライン配信のAUCが向上すること,オンライン配信モデルは予想以上にPSの数シャードの損失に対して寛容であることを発見した.

  1. パラメータ同期周波数の影響:
    Criteo Display Ads Challengeデータセットを用いたオンラインストリーミング訓練実験(1)では,2つの観点からの比較で明らかなように,パラメータ同期頻度の増加とともにモデル品質が一貫して向上していることが確認された.
    • オンライン訓練を行ったモデルは,行っていないモデルよりも性能が高い.図9a,9b,9cは,次のシャードデータで評価したオンライン訓練モデルと,各シャードデータで評価したバッチ訓練モデルのAUCを比較したものである.
    • パラメータ同期間隔が小さいモデルは,間隔が大きいモデルよりも性能が高い.図10と表2は,同期間隔が5hr,1hr,30minのモデルのオンラインサービスAUCをそれぞれ比較したものである.
      プロダクション中のAdsモデルでオンライン訓練とバッチ訓練のライブA/B実験を行ったところ,オンラインサービスAUCが大きく跳ね上がっていることも確認した(表3).
      この観察に触発され,計算オーバーヘッドとシステムの信頼性が耐えられる範囲で,疎なパラメータをできるだけ頻繁に(現在は分レベルで)量産モデルのPSに同期させるようにした.密なパラメータは,2.2.3項で説明したように,それほど頻繁に更新する必要はなく,日レベルで更新している.そうすることで,計算オーバーヘッドを非常に低く抑えることができる.仮に1分間に10万個のIDが更新され,埋め込みの次元が1024であるとすると,1分間に転送すべきデータの総量は4KB*100,000≒400MBである.高密度なパラメータは毎日同期されるため,トラフィックが最も少ない時間帯(例:深夜)に同期を行うようにする.
  2. PS信頼性の効果:
    分単位でパラメータを同期させるため,当初はリアルタイム更新に対応するため,より頻繁に学習用PSのスナップショットを取得することが予想された.しかし,スナップショットの間隔を1日に拡大しても,モデルの品質低下はほとんど見られなかった.
    個人向けランキングシステムにおいて,モデルの品質と計算オーバーヘッドの適切なトレードオフを見つけることは,ユーザが推薦品質に非常に敏感であるため,困難である.従来,大規模システムでは,モデルのスナップショットスケジュールを頻繁に設定する傾向があり,これは,モデル品質の損失を最小限に抑える代わりに計算リソースを犠牲にすることになる.我々は,この点に関してもかなり検討を重ねたが,驚いたことに,モデルの品質は予想以上に頑健だった.PSマシンの1日あたりの故障率が0.01%であるにもかかわらず,前日のモデルが恥ずかしくなるほどよく動くことがわかった.これは,次のような計算で説明できる.あるモデルのパラメータが1000台のPSでシャードされ,毎日スナップショットされるとする.故障率が0.01%だとすると,10日ごとにそのうちの1つがダウンし,このPSの更新が1日分失われる.DAUが1500万で,各PSのユーザIDが均等に分布していると仮定すると,10日ごとに15000人のユーザからの1日分のフィードバックが失われることになる.これは以下の理由で許容範囲内である.(a)ユーザ固有の疎な特徴量の場合,0.01%DAUのごく一部を失うことに相当する.(b)密な変数については,2.2.3項で述べたように更新が遅いので,1000PSのうち1日分の更新を失うことは無視できる.

4章:RELATED WORK(関連研究)

ディープラーニングを業界レベルの推薦システムに適用して成功を収めて以来[6, 10],研究者やエンジニアは,1章で述べた問題を改善するために様々な技術を採用してきた.

疎な特徴量表現の問題に対処するため,[3, 6]では,ハッシュトリックを用いた固定サイズの埋め込みテーブルを使用している.

また,衝突を減らすためにハッシュを改良する試みも行われている[3, 7].

また,ネイティブのキーバリューハッシュテーブルを直接利用し,テーブルサイズの動的な拡張を可能にする研究もある[12, 15, 20, 21].

これらの実装はTensorFlowをベースにしているが,ハッシュテーブルにアクセスし管理するために特別に設計されたソフトウェア機構[14, 15, 20]またはハードウェア[21]に依存する.

これらのソリューションと比較すると,Monolithのハッシュテーブルは,TensorFlowのネイティブな操作の1つである.

開発者に優しく,クロスプラットフォームでの相互運用性が高いので,ToBシナリオに適している.

また,TensorFlowとの有機的かつ緊密な統合により,計算性能の最適化が容易になる.

また,訓練とサービス間のギャップを埋め,コンセプトドリフト[8]を緩和することも関心の高いテーマである.

オンライン更新をサポートし,メモリの問題を回避するために,[12]と[20]は,埋め込みテーブルのサイズを柔軟に調整するための特徴量の追い出し機構を設計した.

また,[12]と[14]は,何らかの形でオンライン訓練をサポートしており,学習したパラメータは,従来のバッチ訓練に比べて比較的短い間隔でサービスに同期され,フォールトトレランス機構を備えている.

Monolithは,モデルの品質を保証するために,より軽量なパラメータ同期機構を持っているが,弾力的に特徴量を追加および削除するために同様のアプローチを取った.

5章:CONCLUSION(結論)

本研究では,プロダクションレベルの推薦システムにおけるいくつかの最も重要な課題を検討し,それらに対処するための実稼働中のシステムMonolithを発表し,既存のソリューションと比較して最高の性能を達成した.

モデル品質には衝突のない埋め込みテーブルが不可欠であることを証明し,Cuckoo HashMapベースの埋め込みテーブルの実装が,メモリ効率とオンラインサービスメトリクスの向上に役立つことを実証した.

また,推薦システムにおいてリアルタイム配信は非常に重要であり,究極のモデル性能を実現するためには,パラメータ同期間隔をできるだけ短くする必要があることを証明した.

Monolithのオンラインリアルタイムサービスのためのソリューションは,パラメータ同期とフォールトトレランス機構を繊細に設計している.

パラメータ同期アルゴリズムでは,パラメータの異なる部分におけるバージョンの一貫性が,ネットワーク帯域幅の消費削減とトレードオフできることを示した.

フォールトトレラント設計では,PSの信頼性とリアルタイム性をトレードオフする戦略がロバストなソリューションであることを実証した.

最後に,Monolithは,プロダクションスケールの推薦システムのための一般的なソリューションを提供することに成功した.

REFERENCES(参考文献)

  1. Martín Abadi, Paul Barham, Jianmin Chen, Z. Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek Gordon Murray, Benoit Steiner, Paul A. Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zhang. 2016. TensorFlow: A system for large-scale machine learning. ArXiv abs/1605.08695 (2016).
  2. Andrew P. Bradley. 1997. The use of the area under the ROC curve in the evaluation of machine learning algorithms. Pattern Recognit. 30 (1997), 1145–1159.
  3. Thomas Bredillet. 2019. Core modeling at Instagram. https://instagram-engineering.com/core-modeling-at-instagram-a51e0158aa48
  4. Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache Flink™: Stream and Batch Processing in a Single Engine. IEEE Data Eng. Bull. 38 (2015), 28–38.
  5. Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishikesh B. Aradhye, Glen Anderson, Gregory S. Corrado, Wei Chai, Mustafa Ispir, Rohan Anil, Zakaria Haque, Lichan Hong, Vihan Jain, Xiaobing Liu, and Hemal Shah. 2016. Wide & Deep Learning for Recommender Systems. Proceedings of the 1st Workshop on Deep Learning for Recommender Systems (2016).
  6. Paul Covington, Jay K. Adams, and Emre Sargin. 2016. Deep Neural Networks for YouTube Recommendations. Proceedings of the 10th ACM Conference on Recommender Systems (2016).
  7. Alexandra Egg. 2021. Online Learning for Recommendations at Grubhub. Fifteenth ACM Conference on Recommender Systems (2021).
  8. João Gama, Indr˙e Žliobait˙e, Albert Bifet, Mykola Pechenizkiy, and A. Bouchachia. 2014. A survey on concept drift adaptation. ACM Computing Surveys (CSUR) 46 (2014), 1–37.
  9. Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. 2017. DeepFM: A Factorization-Machine based Neural Network for CTR Prediction. In IJCAI.
  10. Udit Gupta, Xiaodong Wang, Maxim Naumov, Carole-Jean Wu, Brandon Reagen, David M. Brooks, Bradford Cottel, Kim M. Hazelwood, Bill Jia, Hsien-Hsin S. Lee, Andrey Malevich, Dheevatsa Mudigere, Mikhail Smelyanskiy, Liang Xiong, and Xuan Zhang. 2020. The Architectural Implications of Facebook’s DNN-Based Personalized Recommendation. 2020 IEEE International Symposium on High Performance Computer Architecture (HPCA) (2020), 488–501.
  11. F. Maxwell Harper and Joseph A. Konstan. 2015. The MovieLens Datasets: History and Context. ACM Trans. Interact. Intell. Syst. 5 (2015), 19:1–19:19.
  12. Biye Jiang, Chao Deng, Huimin Yi, Zelin Hu, Guorui Zhou, Yang Zheng, Sui Huang, Xinyang Guo, Dongyue Wang, Yue Song, Liqin Zhao, Zhi Wang, Peng Sun, Yu Zhang, Di Zhang, Jinhui Li, Jian Xu, Xiaoqiang Zhu, and Kun Gai. 2019. XDL: an industrial deep learning framework for high-dimensional sparse data. Proceedings of the 1st International Workshop on Deep Learning Practice for High- Dimensional Sparse Data (2019).
  13. Jay Kreps. 2011. Kafka : a Distributed Messaging System for Log Processing.
  14. Xiangru Lian, Binhang Yuan, Xuefeng Zhu, YulongWang, Yongjun He, Honghuan Wu, Lei Sun, Haodong Lyu, Chengjun Liu, Xing Dong, Yiqiao Liao, Mingnan Luo, Congfei Zhang, Jingru Xie, Haonan Li, Lei Chen, Renjie Huang, Jianying Lin, Chengchun Shu, Xue-Bo Qiu, Zhishan Liu, Dongying Kong, Lei Yuan, Hai bo Yu, Sen Yang, Ce Zhang, and Ji Liu. 2021. Persia: An Open, Hybrid System Scaling Deep Learning-based Recommenders up to 100 Trillion Parameters. ArXiv abs/2111.05897 (2021).
  15. Meituan. 2021. Distributed Training Optimization for TensorFlow in Recommender Systems (in Chinese). https://tech.meituan.com/2021/12/09/meituantensorflow-in-recommender-systems.html
  16. R. Pagh and Flemming Friche Rodler. 2001. Cuckoo Hashing. In ESA.
  17. Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In NeurIPS.
  18. Konstantin V. Shvachko, Hairong Kuang, Sanjay R. Radia, and Robert J. Chansler. 2010. The Hadoop Distributed File System. 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST) (2010), 1–10.
  19. HaiYing Wang, Aonan Zhang, and Chong Wang. 2021. Nonuniform Negative Sampling and Log Odds Correction with Rare Events Data. In Advances in Neural Information Processing Systems.
  20. Minhui Xie, Kai Ren, Youyou Lu, Guangxu Yang, Qingxing Xu, BihaiWu, Jiazhen Lin, Hongbo Ao, Wanhong Xu, and Jiwu Shu. 2020. Kraken: Memory-Efficient Continual Learning for Large-Scale Real-Time Recommendations. SC20: International Conference for High Performance Computing, Networking, Storage and Analysis (2020), 1–17.
  21. Weijie Zhao, Jingyuan Zhang, Deping Xie, Yulei Qian, Ronglai Jia, and Ping Li. 2019. AIBox: CTR Prediction Model Training on a Single Node. Proceedings of the 28th ACM International Conference on Information and Knowledge Management (2019).

参考:Monolith: Real Time Recommendation System With Collisionless Embedding Tableの解説動画

Monolith: Real Time Recommendation System With Collisionless Embedding Tableの解説動画です.

まとめ

Monolith: Real Time Recommendation System With Collisionless Embedding Tableの日本語訳を紹介しました.

TikTokの推薦アルゴリズム「Monolith」がわかりました.

AIのプログラミング言語「C++/Python言語」を学べるおすすめのWebサイトを知りたいあなたはこちらからどうぞ.

独学が難しいあなたは,AIを学べるオンラインプログラミングスクール3社で自分に合うスクールを見つけましょう.後悔はさせません!

国内・海外のAIエンジニアのおすすめ求人サイトを知りたいあなたはこちらからどうぞ.

国内・海外のプロンプトエンジニアのおすすめ求人サイトを知りたいあなたはこちらからどうぞ.

-TECHNOLOGY, NLP AI
-, , ,