YahooのMLFMを読む：1,098個の広告セグメントを特徴量の相互作用から予測する
KDD 2023のMLFM論文を、特徴量とフィールドの相互作用、軽量版の因子分解、広告データでの評価、再現時の注意点から解説します。
Xでシェア目次
AI利用の明示
本記事の構成と本文はCodexが作成しました。人間による内容確認はまだ実施していません。論文の報告と記事独自の解釈・実装案を区別して記載しています。
この論文の価値は、多数の広告セグメントを予測する際に、特徴量の相互作用を共有し、精度と推論コストの両立を図った点にあります。
取り上げるのは、Martin Pavlovskiら7名による「Extreme Multi-Label Classification for Ad Targeting using Factorization Machines」です。Yahoo Researchを中心とするチームがKDD 2023（2023年8月6〜10日）で発表しました。本文・図表・付録は著者公開版PDFで確認しています。以下はこの2023年の論文の解説であり、現在のYahooの配信仕様を説明するものではありません。
なぜ広告ターゲティングがmulti-label分類になるのか
広告のセグメントは、ある条件を満たす利用者の集合です。1人が旅行とペットの両方に関心を持つように、利用者は複数のセグメントへ同時に所属できます。したがって、1件の入力から1つのクラスを選ぶ分類ではなく、複数のラベルについて所属の可能性を予測するmulti-label分類になります。
論文の主対象は、コンバージョンに基づくセグメントです。入力にはURL、地域、時間帯、端末やブラウザーなどのフィールドを使い、出力には多数のセグメントへの所属を使います。広告そのものを直接1件選ぶモデルではなく、広告候補の選択に使う利用者のセグメントを推定するモデルです。
セグメントごとにロジスティック回帰を作るone-vs-all（OVA-LR）は分かりやすい構成ですが、ラベルが増えるほどモデルの管理が重くなります。また、通常の線形モデルは「地域と時間帯の組み合わせ」のような相互作用をそのままでは捉えられません。
そこで登場するのがMulti-Label Factorization Machine、略してMLFMです。原論文のSections 1〜3では、Factorization Machineの考え方を、多数のラベルとフィールドを持つ入力へ拡張しています。
MLFMは何を共有し、何をラベルごとに学習するのか
まず、フィールドと特徴量を分けて考えます。「国」はフィールド、その値をone-hot化した「国が日本である」は特徴量です。論文のカテゴリ入力の定式化では、各フィールドで1つの特徴量が有効になります。
通常のFactorization Machine（FM）は、特徴量ペアごとの重みを直接持つ代わりに、それぞれの特徴量へ小さなembeddingを割り当て、その内積で相互作用の強さを表します。特徴量が増えても、全ペアの独立したパラメータを保存せずに済みます。
MLFMでは、さらに「どのフィールド同士の組み合わせが、どのラベルに効くか」を学習します。標準版の構成は次の通りです。
| パラメータ | 役割 | ラベル間の共有 |
|---|---|---|
特徴量embedding v_i |
特徴量ペアの相互作用を内積で表す | 共有する |
線形重み w_i,l |
特徴量単体の寄与 | ラベルごと |
フィールド間重み r_a,b,l |
フィールドペアの重要度 | ラベルごと |
バイアス b_l |
ラベルの基礎スコア | ラベルごと |
ラベルlのスコアを、原論文の式(7)に沿って書くと次の形になります。F(i)は特徴量iのフィールド、dotは内積です。
score_l = b_l
+ Σ_i w_i,l × x_i
+ Σ_{i<j} r_F(i),F(j),l × dot(v_i, v_j) × x_i × x_j
p_l = sigmoid(score_l)たとえば、同じ「地域×時間帯」の組み合わせでも、旅行のラベルと飲食のラベルでは効き方が異なり得ます。これは仕組みを理解するための例ですが、共有embeddingとラベル別フィールド重みの役割を表しています。
全ラベルがembeddingを共同で学習するため、各ラベルで完全に独立したモデルを作る場合とは情報の使い方が変わります。ただし、この式がラベル同士の条件付き確率や階層制約を直接モデル化しているわけではありません。出力は各ラベルのsigmoidであり、合計が1になるsoftmaxではありません。
軽量版：ペアを列挙せず相互作用を集計する
標準版には、入力の特徴量ペアを走査する処理が残ります。軽量版では、ラベル別のフィールド間重みもembeddingの内積に置き換えます。
r_a,b,l = dot(u_a,l, u_b,l)
q_i,l = flatten(outer(u_F(i),l, v_i))v_iの次元をM、フィールドembeddingの次元をHとすると、q_i,lはH × M次元です。この表現を使えば、相互作用項は次の恒等式で計算できます。
interaction_l
= 1/2 × Σ_k [ (Σ_i q_i,l,k × x_i)^2
- Σ_i (q_i,l,k × x_i)^2 ]「総和を二乗した値」から「各項を二乗して足した値」を引くと、異なる項同士の積だけが残ります。同じペアを2回数えるので最後に半分にします。これが原論文の式(9)〜(12)の中心です。
有効な特徴量数をA、ラベル数をLとすると、軽量版の相互作用計算はO(L × A × M × H)になります。カテゴリ入力で各フィールドに1つの値がある場合、Aはフィールド数です。語彙全体の大きさと、1件の入力で有効な特徴量数を区別することが実装では大切です。
ここには2段階あります。まず、自由なフィールド間重みを内積で表すというモデル上の制約を導入します。その後、その表現の下で厳密な恒等式を使って計算します。したがって、任意の学習済み標準版が、小さなHで完全に同じ予測を保ったまま軽量版へ変換できる、という意味ではありません。これは数式から読み取れる実装上の注意点です。
また、ラベル数Lに対する計算は残ります。特徴量数に対して線形になったことだけで、数百万ラベルへの適用が実証されたとは言えません。
実験では何が改善したのか
評価の中心はラベル別のROC-AUCです。macro AUCは各ラベルを同じ重みで平均し、stratified AUCは正例数で重み付けします。後者は正例の多いラベルの影響を強く受けるため、希少ラベルの改善は個別の結果も見る必要があります。Precision@kやnDCG@kは、この論文では評価していません。
公開データでは精度と速度のトレードオフがある
公開ベンチマークはMediaMill、RCV1、EURLexの3つです。学習／テスト件数はそれぞれ30,993／12,914、623,847／155,962、45,000／6,000で、ラベル数は101、2,456、4,271です。提供済みの分割を使っています。
Table 3では、MLFMのmacro AUCはMediaMillで0.8456、EURLexで0.9613となり、掲載された比較手法を上回りました。一方、RCV1ではMLFMの0.9179に対してPfastreXMLが0.9354で、MLFMが常に最高精度という結果ではありません。
CPUでの平均推論時間も、EURLexではMLFMが7.9049 ms、FastXMLが0.9486 msです。実装言語やスレッド対応も異なるため、この値をアルゴリズムだけの差とは解釈できません。GPUで動くモデルとCPUの木モデルを比較して、ハードウェアの条件を省略した「高速化率」を出すことも避けるべきです。Sections 4.1〜4.3、Tables 2〜3
広告データではOVA-LRを多数のセグメントで上回る
主実験では1週間の広告リクエスト約9.5億件で学習し、その後3日間の約1.6億件でテストしています。特徴量は頻度上位20万個を選び、低頻度の値をotherへまとめます。コンバージョンが少なすぎるセグメントを除いた結果、対象は1,098ラベルになりました。
Table 4の代表的な比較は次の通りです。
| モデル | macro AUC | stratified AUC |
|---|---|---|
| OVA-LR | 0.7928 | 0.7477 |
| Parabel | 0.8239 | 0.7892 |
| MLFM | 0.8421 | 0.8006 |
OVA-LRに対する絶対差は、それぞれ+0.0493、+0.0529です。また、1,098セグメント中1,069セグメントで、MLFMのAUCがOVA-LRを上回りました。これは約97%のセグメントで比較相手を上回ったという意味で、予測の正解率が97%という意味ではありません。
別の興味関心ベースの実験では、425ラベル、学習1.8億件、テスト4,500万件を使用しています。macro AUCはOVA-LRの0.6865からMLFMの0.8522へ、stratified AUCは0.6048から0.8519へ上がりました。絶対差は+0.1657、+0.2471です。論文本文の改善率表現には絶対差に対応する値が含まれるため、ここでは元のAUCと差を明記しています。Sections 4.4.1〜4.4.2、Tables 4〜5
実トラフィックの5.32%はコンバージョン件数の比較
1週間の実トラフィックでOVA-LRと比較した結果、MLFMに帰属するコンバージョン件数が5.32%増えたと報告されています。これは件数の相対改善であり、コンバージョン率が5.32ポイント上がったという意味ではありません。
この報告箇所には、トラフィックの割当方法、母数、信頼区間などの詳細は示されていません。広告配信企業自身の評価でもあるため、他の環境で同じ効果が出る保証や、十分に条件が開示された因果効果の推定としては扱わず、著者による運用上の報告として読むのが適切です。Section 4.4.1
速さとメモリをどう読むか
コンバージョン向けデータで、M = H = 10とした推論時間の比較です。数値は1レコードあたりの平均です。
| モデル | 平均推論時間 |
|---|---|
| OVA-LR | 0.067447 ms |
| MLFM標準版 | 0.159827 ms |
| MLFM軽量版 | 0.101286 ms |
Table 6から計算すると、軽量版は標準版より約36.6%短時間ですが、OVA-LRよりは約1.50倍の時間がかかります。また、この表はモデルの推論時間であり、ネットワーク、特徴量取得、待ち行列を含めた広告リクエスト全体のp99応答時間ではありません。標準版と軽量版の精度を直接比較するablationも、この表にはありません。
Table 7では、OVA-LRが約3.9 GB、標準版MLFMが約4.0 GBと報告されています。注目したいのは、メモリの大半を特徴量×ラベルの線形重みが占めることです。相互作用を追加しても増分が小さい一方、線形重み自体の大きさは解消されません。報告されたGB値は論文の実装における値で、任意のテンソル実装で同じ容量になるとは限りません。Section 4.4.3、Tables 6〜7
手元で試すなら、まず相互作用の集計を確かめる
広告データは非公開で、確認した本文・付録には著者のMLFM実装リポジトリへのリンクがありません。付録には学習・推論の疑似コードがありますが、本番実験の完全再現には不足があります。以下は記事側で提案する小規模検証であり、論文の再現結果ではありません。
最小構成は、入力を(feature_id, field_id, value)の疎な配列、教師ラベルを長さLの0/1ベクトル、出力を長さLのスコアとするものです。軽量版の推論は次の疑似コードで整理できます。
for each label l:
score = bias[l]
sum_q = zeros(H, M)
sum_sq = zeros(H, M)
for (feature_id, field_id, value) in active_features:
score += W[feature_id, l] * value
q = outer(U[field_id, l], V[feature_id]) * value
sum_q += q
sum_sq += q * q
score += 0.5 * sum(sum_q * sum_q - sum_sq)
output[l] = sigmoid(score)ここで*は要素ごとの積です。学習前に、小さなランダム入力で「全ペアの内積を直接足す実装」とこの集計式の結果が一致するかを確認すると、自己相互作用の引き忘れや係数1/2のミスを検出できます。同じ因子U, Vを両方の計算に使うことが前提です。
学習にはラベルごとのbinary cross-entropyを使う構成が自然です。ただし、著者公開PDFの式(8)では負例側が(1-y)(1-log(p))と印字されています。標準的なbinary cross-entropyの負例側は(1-y)log(1-p)なので、誤記の可能性があります。著者による訂正は確認できておらず、式(8)をそのまま実装せず、損失の意図を確認する必要があります。
論文の学習設定は、Python 3、PyTorch 1.6.0、CUDA 10.1、AdamW、学習率0.01、バッチサイズ32、10 epoch、特徴量embedding次元10です。推論実装にはJavaとEJMLも使っています。これは当時の設定の記録であり、現在の環境へのインストール手順や最適値ではありません。この疑似コードの学習・実データ評価は本記事では実施していません。
実装を評価する際は、同じデータ分割でOVA-LR、標準版MLFM、軽量版MLFMを比べます。macro AUCと頻度別のラベル評価に加え、同一ハードウェア・同一バッチサイズの推論時間、ピークメモリ、運用する閾値でのprecision／recallを記録すると、精度と費用の判断につながります。カテゴリ入力では未知値をフィールド別に処理し、学習時と推論時で語彙・フィールドIDの対応を揃えることも必要です。これらは記事側の実装提案です。
適用範囲と残る課題
MLFMが特に参考になるのは、疎な表形式の特徴量から多数のラベルを予測し、線形モデルより相互作用を捉えたい場面です。一方、比較実験の最大ラベル数は4,271であり、あらゆる規模のextreme classificationで優位だとは実証されていません。
また、コンバージョンが極端に少ないラベルは主実験から除外されています。階層付きの興味関心ラベルで改善していても、親子の予測整合性を保証する仕組みはありません。希少ラベルや階層への対応は、著者自身も今後の課題に挙げています。
付録にはPECOSのXR-Linearとの比較もありますが、著者はXR-Linearが主としてランキング向けであることを断っています。AUCでの比較を、そのまま上位候補検索や文書推薦全般の優劣に広げるべきではありません。
この記事から得られる設計上の示唆は、何を共有し、どこにラベル固有の自由度を残すかを明確にすると、相互作用の表現力と推論コストを調整しやすいということです。MLFMでは、それを特徴量embeddingの共有と、フィールド間重みの因子分解で実現しています。
参照
- Pavlovski, M., Ravindran, S., Gligorijevic, D., Agrawal, S., Stojkovic, I., Segura-Nunez, N., and Gligorijevic, J. (2023). Extreme Multi-Label Classification for Ad Targeting using Factorization Machines. KDD ’23, pp. 4705–4716.
- ACM PDF ／ 本文確認に用いた著者公開版PDF（付録を含む12ページ）