🤖

論文紹介 TwERC

に公開
AI
機械学習
広告
推薦システム
idea

この記事について

Cai, et al.の2023年の論文「TwERC: High Performance Ensembled Candidate Generation for Ads Recommendation at Twitter」の紹介です。

Abstract

(要旨)

要約

推薦システムは、通常「候補生成（Candidate Generation）」と「高負荷なランキング（Heavy Ranking）」の2段階で構成されます。
本論文では候補生成フェーズに焦点を当て、TwERCと呼ばれる新しいアーキテクチャを提案します。
リアルタイムの軽量ランカー（Light Ranker）と、追加情報を捉えることができる調達戦略（Sourcing Strategies）を組み合わせたシステムが収益をもたらすことを示します。
2つの戦略を提示します。

  1. Graph Based Strategy: 相互作用グラフに基づく類似性を利用（収益 +4.08%）。
  2. Rankscore Based Strategy: 過去のランキングスコアをキャッシュして利用（収益 +1.38%）。

解釈

リアルタイムの「軽量ランカー（Light Ranker）」だけでは捉えきれないユーザーの興味を、別のアルゴリズムで補完するというアプローチです。

1. Introduction

(導入)

要約

Twitterは数億人のユーザーに対し関連性の高い広告を推薦することで、ユーザー体験の悪化を防ぎつつ収益化を図っています。
現代の推薦システムは計算コストと品質のバランスを取るため、膨大なアイテムを数千に絞り込む「候補生成（Candidate Generation）」と、それらを精密に評価する「ランキング（Ranking）」の2段階構成が一般的です。
ランキングモデルは広く研究されていますが、候補生成システムは学術・産業の両面で注目されることが比較的少なく、本論文はこの「候補生成」に焦点を当てています。
本論文では候補生成フェーズを再構築した TwERC (Twitter Ensembled Retrieval of Candidates) を提案します。
TwERCは以下の要素を組み合わせたアンサンブル手法です。

  • フィードバックループに対抗するシステム
  • 反事仮想的（Counterfactual）な候補生成
  • グラフ類似性に基づく候補生成
  • 混合器（Blender）

オフライン及びオンライン実験において、TwERCが無関係な広告を減らし、関連性の高い広告を増やすことで、候補生成プロセスの効率と効果を向上させることを示します。

解釈

推薦システムは「ランキングモデル」に焦点を当てがちですが、本論文は「その前段階で何を拾ってくるか（Candidate Generation）」に焦点を当てています。
数十億の広告在庫がある中で、ランキングモデルに渡す「最初の数千個」に正解（ユーザーが興味を持つ広告）が含まれていなければ、後段でどんなに高性能なランキングを行っても意味がないということだと思います。
もうひとつのポイントは「異なる性質を持つ複数の調達戦略（Sourcing Strategies）」を組み合わせるというアプローチです。

  • フィードバックループに対抗するシステム: 自分自身が過去に行った推薦によって生成されたデータを使って再び学習してしまうことを防ぐための仕組み。
  • 反事仮想的（Counterfactual）な候補生成: 上述のフィードバックループを打破し、見逃している高価値な広告を救い上げる手法。
  • グラフ類似性に基づく候補生成: ユーザーと広告の関係性グラフを利用する手法。
  • 混合器（Blender）: これら複数の情報源を統合するモジュール。

これらを組み合わせることで、リアルタイム性を犠牲にせず各手法の弱点を補完し合う「いいとこ取り」の構成を目指すと思われます。

2. RELATED WORK

(関連研究)
※ RELATED WORKとありますが、このセクションには実際には提案手法の詳細も含まれています。

Counterfactual Data Collection and Policy Evaluation

(反実仮想データ収集とポリシー評価)

要約

産業界の推薦システムにおいて、フィードバックループ（Feedback Loops）やオンライン/オフラインの乖離（Online/Offline Gaps）は大きな課題です。
システムが提示したものしかユーザーは評価できないため、バイアスが発生します。
これに対処するため、「反実仮想的（Counterfactual）」な評価手法が用いられます。
先行研究では、オークション参加者のデータ（勝者と敗者）を用いたシミュレーションエンジンにより、システム変更のインパクトを推定します。
本研究でも同様のオフライン評価を採用し、これを候補生成（Candidate Generation）の評価に応用しています。

解釈

「過去に配信されなかった広告をもし配信していたらどうなっていたか？」を推定するのが反実仮想的評価です。
これにより、上述のフィードバックループ解決、オンライン実験を行う前にオフラインでの評価精度向上を目指すと思われます。

Graph Machine Learning

(グラフ機械学習)

要約

グラフ埋め込み（Graph Embeddings）は、NLPの手法（SkipGram, Word2Vec）やランダムウォーク（DeepWalk, Node2Vec）に触発され発展してきました。
近年では、異種混合グラフ（Heterogeneous Graphs）を扱うための翻訳ベースの手法（TransEなど）や、Webスケールのグラフを扱うフレームワーク（PyTorch-BigGraphなど）が開発されています。

解釈

単一のノードタイプしか扱えない手法に対して、多様な関係を表現できる異種混合グラフ（Heterogeneous Graph）を用いて、「ユーザー」「ツイート」「広告主」などが複雑に絡み合う構造を表現したいのだと思います。

Candidate Generation

(候補生成)

要約

候補生成の目的は、数十億のアイテムの中から関連性の高い数千個を効率的に抽出することです。
情報検索（IR）の分野と密接に関連しており、ブール検索やベクトル空間モデルが一般的です。
先行研究であるTwHINやSimClustersは、グラフ埋め込みが候補検索の品質向上に有用であることを示しています。
Twitterの広告システムは以下の3段階で構成されています。

  1. Targeting and Filtering: 広告主が設定したハード制約（年齢、地域などのand条件）とソフト制約（興味関心などのor条件）によるフィルタリング。
  2. Early Ranking (Light Ranker): 数百万の候補からTop-Kを選抜する軽量なランキングモデル。推論予算（レイテンシ制約）が厳しいため、モデルの表現力には限界がある。
  3. Ranking and Auction (Heavy Ranking): 複雑なディープニューラルネットワークを用い、正確なエンゲージメント確率（pEng）と入札額（Bid）に基づいて最終的なスコア（Rankscore）を算出する。

本研究では、Early Rankingの段階において、「Tail Replacement（末尾置換）」という手法を提案します。
これは、Light Rankerが選んだTop-K候補の下位M%を切り捨て、代わりに別の戦略（TwERC）で選んだ候補に置き換えるアプローチです。

解釈

TwHIN(Twitter Heterogeneous Information Network)という先行研究は、異種混合グラフ埋め込み技術のようです。
既存のシステム（Light Ranker）を完全に置き換えるのではなく、「弱点を補強する」現実的なアプローチをとっています。
Light Rankerは高速ですが単純なため、複雑な関係性を見逃します。
その「見逃し」を、後述するオフラインの高度な計算（Rankscore戦略、Graph戦略）でカバーし、最終的なHeavy Rankerに渡す候補の質を底上げすることを目指すと思われます。

2.1 Rankscore Candidate Generation

(ランクスコアに基づく候補生成)

要約

Unconstrained Ad Serving (UAS)と呼ばれるシステムを利用します。
これは、少量のトラフィックに対してフィルタリングを行わずに全ての適格な広告候補をスコアリングし、ログとして保存するものです。
このデータを用い、ユーザー u と広告 a の間の時間減衰を考慮した品質スコア q(u,a) を計算します。

q(u,a)=\frac{\sum rankscore(u,a,t)\cdot e^{t-t_{0}}}{\sum e^{t-t_{0}}} \quad (1)

ここで、t はデータ収集時刻、t_0 は現在時刻です。
このスコアが高いTop-Kの広告を3時間ごとにバッチ生成し、KVSに保存します。

解釈

数式(1)の e^{t-t_0} は、データが古いほど指数的に小さくなる（忘却する）重みです。
リアルタイム計算のような高負荷をかけずに、Heavy Rankerの知識をキャッシュして再利用する効果を得ています。

2.2 Graph Based Candidate Sourcing

(グラフベースの候補調達)

要約

ユーザーと広告のエンゲージメント履歴から有向マルチグラフを構築し、TwHINの手法を用いて低次元ベクトルに埋め込みます。

Graph Embeddings:
ユーザーとアイテムの距離をエンゲージメントの可能性として解釈します。類似したユーザーとアイテムが近くに配置される空間を作ります。

Embedding Update Cycles (Tic-Toc Cycle):
グラフの鮮度を保つため、2種類の更新サイクルを採用しています。

  • Tic (12時間ごと): Warm-start（追加学習）。古いノードの埋め込みを凍結（Freeze）し、新規ノードのみを既存空間に投影します（新しい頂点を含むエッジのみ利用）。高速です。
  • Toc (週1回): 全ノードの凍結を解除し、グラフ全体を緩和（Relaxation）（再学習）させます。

Candidate Generation:
MapReduceパイプラインと FAISS (IVF + HNSW) を使用し、1.3億人のヘビーユーザーに対して近似再近傍探索（ANN）をバッチ実行します。

解釈

ユーザーとアイテムの類似度を学習する手法です。
「Tic-Toc」手法により、計算コストを抑えつつ新規ユーザーや新着広告への対応速度（鮮度）を維持しています。

2.3 Blending

(混合)

要約

複数の戦略（Rankscore戦略とGraph戦略）から得られた候補を、動的に割り当てられた容量（Capacity）に基づいてマージするコンポーネント「Blender」を構築しました。
実験の結果、Rankscore: 20%, Graph: 20%の比率でマージし、Light Rankerの下位候補と置換（Tail Replacement）するのが最適であることが経験的に確認されました。

解釈

  • Rankscore戦略: 過去の実績重視
  • Graph戦略: 潜在的な類似性重視

性質の異なる候補を混ぜることで、多様性を確保しつつ全体の精度を向上させるという意図だと思われます。

2.4 Efficiency

(効率)

要約

提案手法はすべてバッチ処理（オフライン）で実行され、結果はKVSに保存されます。
オンラインでの処理は単なる「Look-up（参照）」のみです。
これにより、Heavy Rankingの推論時間を圧迫することなく、高度なモデルを利用可能です。
障害時もデータが古くなるだけで、配信停止には至りません。

解釈

「推論の重さをオフラインに逃がす」設計です。
リアルタイムでグラフ探索を行うと遅延が許容範囲を超えますが、事前計算することで、複雑なアルゴリズムを実用化しています。
Twitter規模のトラフィックを捌くための現実解と言えます。

2.5 Metrics

(評価指標)

要約

モデルの評価には以下の指標を用いています。

Recall (再現率):

R=\frac{TP}{TP+FN} \quad (2)

ユーザーがエンゲージした広告を正解とします。

Auction Recall (オークション再現率):

実際にオークションに勝利した広告を正解とする再現率です。

Rankscore NCG (ランクスコア正規化累積利得):

アルゴリズムによって選択された広告のランクスコアの合計と、仮想的なアルゴリズムによって見つけ出されるであろう潜在的なランクスコアの合計との比率です。

rNCG_m = \frac{\sum_{i=1}^{n} \sum_{j=1}^{min(m,|C_i|)} C_{i,(|C_i|-j+1)}}{\sum_{i=1}^{n} \sum_{j=1}^{min(m,|R_i|)} R_{i,(|R_i|-j+1)}} \quad (3)
  • R_{i}: ターゲティングフィルタ適用後の i 番目のリクエストに対するすべての適格な広告のランクスコアの集合
  • C_{i}: 候補生成アルゴリズムによって R_{i} から選択された広告候補
  • n: 広告リクエストの数
  • m オークションに進む広告の数

この値が低いほど、候補生成の改善の余地が大きいことを示します。

Inequality (不平等 / T1PS):

広告主の上位1%が占める配信シェア（Top 1 Percent Share）です。

T1PS = \frac{\sum_{S_i \ge S_{(0.99|S|)}} S_i}{\sum_{i} S_i} \quad (4)
  • S_{i}: ある一定期間において、全ユーザーに対して広告主 i から配信された広告の数

中小企業の広告体験を向上させることを目指します。

Ads Value (広告価値):

広告の平均価値を推定することは困難ですが、CPAを価値の自然な代理指標として使用できます。
この直感に基づき、広告価値を以下のように定義します。

\text{AdsValue}(j) = \sum_{i} \frac{R_i}{C_i} C_{ij} \quad (5)
  • j: 実験バケット (実験群、対照群)
  • i: キャンペーンのインデックス
  • R_{i}: そのキャンペーンの収益
  • C_{i}: そのキャンペーンの総コンバージョン数
  • C_{ij}: j 番目の実験バケットにおける i 番目のキャンペーンのコンバージョン数

広告主側の価値を示します。

Utility (効用):
ランクスコアの確率値を、実際の観測値に置き換えて計算したものです。
この指標の向上が予測品質の向上を示します。

解釈

様々な指標を提示しています。

  • 単にユーザーが好むか？ (Recall)
  • ビジネス的に収益になるか？ (Auction Recall, Rankscore NCG)
  • プラットフォームは公平か？ (Inequality)
  • 広告主にとって価値があるか？ (Ads Value)
    • CPAを広告主にとっての価値と解釈するのはやや飛躍がありますが、要約に書いた通り実際の価値を推定するのが困難なため、「そのコンバージョンには少なくともこれだけの金銭的価値がある」という解釈と思われます。
  • 高単価なエンゲージメントを正しく予測できるか？ (Utility)

様々な視点からのバランスを取ることを目指していると思われます。

3. Experiments

(実験)

要約

全トラフィックの2%を使用したオンラインA/Bテストを最低7日間実施しました。
比較対象は、現在本番稼働している「Early Ranker」（2タワーニューラルネットワークによる軽量なクリック確率予測モデル）です。
機密保持のため、広告の具体的な目的（クリック、動画視聴、アプリインストールなど）は隠蔽して扱われます。

3.1 Rankscore Candidate Sourcing

既存のアーリーランカーが選んだ候補のうち、下位の最大 M\% を、オフラインで特定した広告に置き換えます。
オフライン: オークション再現率（Auction Recall）が最大20%改善しました。
オンライン: 純収益（Net Revenue）が 1.38% 増加、効用（Utility）が 4.71% 増加、広告価値（Ads Value）が 1.05% 増加しました。

3.2 Graph Based Candidate Sourcing

高アクティブユーザーの3分の1を対象に、グラフ埋め込み空間での近似最近傍探索（ANN）を用いて候補を生成しました。
これを既存のアーリーランカーが選出した候補の下位 M\% と置き換える「末尾置換」（tail replacement）を行いました。
オフライン: オークション再現率（Auction Recall）が最大5%改善しました。
オンライン: 純収益 (Net Revenue): +4.08%、効用 (Utility): +6.42%、広告価値 (Ads Value): +1.26%
さらに不平等性の観点では、T1PSが1.2%減少しました。

3.3 Time Dependent Embeddings

従来のユーザー埋め込みは、過去のすべてのエンゲージメントの平均に収束するため、ユーザーの長期的な興味は捉えられるものの、直近の興味や時間的な変化を見逃してしまうという欠点がありました。
ランクスコアの計算と同様に、ユーザー埋め込みの作成にも「指数的減衰」を導入しました。
これにより、直近のインタラクションに大きな重みを与え、古い情報を徐々に忘却させることで現在の興味を鮮明に反映させました。

\vec{u}_{i,t}^{user} = \frac{\sum_{j \in \mathcal{N}_i} e^{\lambda(t_j - t_0)} \vec{v}_{j}^{tweet}}{\sum_{j \in \mathcal{N}_i} e^{\lambda(t - t_0)}} \quad (6)
  • \mathcal{N}: 直近N回のエンゲージメントの集合
  • t_0: ジョブの実行時刻
  • t_j: j番目のインタラクションの時刻
  • \lambda: 減衰定数（decay constant）

オフライン: 5つの目的のうち4つでオークション再現率（Auction Recall）が 7.2% 〜 10.2%向上しました。

3.4 Embedding Induction

広告や広告主とのインタラクション履歴がないユーザー（新規ユーザー、ライトユーザーなど）は、エンゲージメントグラフに含まれないためグラフ埋め込みを持たず、高精度な近似最近傍探索の恩恵を受けられませんでした。
フォロー関係を利用した「特徴伝播」（Feature Propagation）を用い、埋め込みを持たないユーザーのベクトルを「そのユーザーがフォローしているユーザーたちのベクトルの平均」として推論・補完しました。
これは、「フォローしている人の興味は、本人の興味の近似になる」という直感に基づいています。

\boldsymbol{x}_i = \frac{1}{|N_{S,T}^{+}(i)|} \sum_{j \in N_{S,T}^{+}(i)} \boldsymbol{x}_j \quad \forall i \in U_M \quad (7)
  • U_{M}: 埋め込みを持たないユーザー（missing users）
  • \mathcal{N}_{S,T}^{+}(i): 埋め込みを持つiのフォローしている人の中からランダムにサンプリングされた100人のセット

オフライン実験において、この拡散埋め込み（Diffused embeddings）は本来の（真の）グラフ埋め込みが持つHR(Hit Rate)@300の約79%（34.38% vs 43.53%）を達成しました。

解釈

多様な戦略を組み合わせることで、計算コストを抑えながら収益・精度・公平性が同時に向上したことを示しています。

4. Conclusion

(結論)

要約

異種混合（Heterogeneous）候補生成システムが計算コストを大幅に増やすことなく性能を向上
させるという仮説を立てました。
そして、このアンサンブル手法のオフライン、オンライン双方における有意な改善を示しました。

解釈

「Heavy Rankingを改善する」という王道のアプローチではなく、「前段の候補生成を賢く多様化する」というアプローチで成果を出した事例です。

参考文献

https://arxiv.org/abs/2302.13915

Discussion