技術要約：Eコマース・マーケティング・キャンペーンにおける制約付きユーザー・アイテム割り当て

問題定義：オートターゲティング（Auto-Targeting）

本論文は、Eコマース・マーケティングにおける組合せ最適化問題である「オートターゲティング」を取り扱う。従来の、アイテム選択とユーザー割り当てを分離して考える手法や、あらかじめ定義されたキャンペーン構造を仮定する手法とは異なり、本研究ではこの問題を**結合最適化（joint optimization）**タスクとして定式化している。目標は、ユーザー集合とアイテム集合を $K$ 個の互いに素なキャンペーン（グループ）へと同時に分割することであり、以下の条件を満たす必要がある：

1. 凝集性（Cohesion）： 各キャンペーンは、割り当てられたユーザーとアイテム間の総内部親和性を最大化する。
2. 非重複性（Disjointness）： すべてのユーザーおよびアイテムは、高々1つのキャンペーンにのみ含まれる。
3. 制約（Constraints）： 各キャンペーンは、固定数のアイテム（$I$）と、特定の範囲内（$\tau_{min} \le |U_k| \le \tau_{max}$）のユーザー数を含まなければならない。

ユーザーとアイテムの間の親和性は、共有埋め込み空間（クリックや購入などの過去のインタラクションから学習されたもの）から導出され、近接性は相互の関心を意味する。目的関数は、すべてのキャンペーンにおける親和性の総和を最大化することを目指す：
$$\max_{\{I_k, U_k\}_{k=1}^K} \sum_{k=1}^K \sum_{i \in I_k} \sum_{u \in U_k} \text{affinity}(i, u)$$

この定式化は、指数関数的な探索空間と制約の結合により計算量的に極めて困難であり、大規模なデータセットに対して厳密解を求めることは不可能である。

手法

著者らは、Simulated Annealing（SA）をベースラインとして、この問題を解決するための3つの補完的なヒューリスティック戦略を提案している。

1. 制約付きスペクトラル・バイクラスタリング（Constrained Spectral Biclustering）

この手法は、ユーザー・アイテムの親和性行列における高密度領域を特定するために、スペクトラル・コ・クラスタリングを適応させたものである。

• オーバーサンプリング（Oversampling）： 多様な候補プールを確保するため、最初に $k' = \alpha k$ 個のバイクラスター（ここで $\alpha \ge 2$）を算出する。
• 枝刈り（Pruning）： 候補はサイズ制約を満たすように枝刈りされる。最大サイズに達するまで、バイクラスター内での平均親和性に基づいてアイテムとユーザーが逐次的に除去される。
• 選択（Selection）： 残った候補は密度（平均親和性）によってランク付けされ、上位 $k$ 個の非重複バイクラスターが最終的なキャンペーンとして選択される。

2. マルチアームド・バンディット（MAB）最適化

この手法は、キャンペーンをバンディット・フレームワークにおける「腕（arm）」として扱い、搾取（高い親和性を持つキャンペーンへのエンティティの割り当て）と探索のバランスを取る。

• 結合報酬（Coupled Rewards）： 報酬は内生的である。あるエンティティのキャンペーンに対する親和性は、そのキャンペーンの現在の構成に依存する。
• 戦略： 著者らは2つの探索ボーナスを実装している：
  • UCB1： 親和性スコアに信頼限界を加える。
  • トンプソン抽出法（Thompson Sampling）： スコアにガウスノイズを加え、キャンペーンへの割り当てが増えるにつれてノイズを減少させる。
• メカニズム： アルゴリズムは、変化するキャンペーン構成に適応するために、指数減衰を用いたローリングウィンドウ統計を用いながら、ユーザー割り当てフェーズとアイテム割り当てフェーズを交互に実行する。

3. グリーディ・ローカルサーチ（Greedy Local Search）

この戦略は、容量制約を伴うグリーディな手順と、それに続く洗練化プロセスを採用している。

• グリーディな割り当て： エンティティは、潜在的な利得の降順で処理され、最大スコア改善に基づきキャンペーンに割り当てられる。
• ペアワイズ・スワップ（Pairwise Swaps）： ローカルサーチのステップでは、異なるキャンペーン間でのエンティティの入れ替えを評価する。もしスワップが実現可能性を維持したまま目的関数を改善する場合、それが実行される。
• 反復： プロセスは、固定回数のイテレーションの間、ユーザー更新とアイテム更新を交互に行う。

ベースライン：逐次型シミュレーテッド・アニーリング（Sequential Simulated Annealing）

著者らは、SAをベースラインとして使用している。グローバルな問題を $K$ 個の逐次的なサブ問題に分解する。各キャンペーンについて、SAは、最適なバイクラスターを近似するために、温度制御された受理確率（add, remove, swap操作を使用）を用いた確率的ローカルサーチを実行する。

主な貢献

1. オートターゲティングの定式化： 本論文は、キャンペーン構造とユーザー・アイテムの割り当てを同時に推論する新しい結合最適化問題を定義しており、既存の手法が一方の割り当てを固定していたというギャップに対処している。
2. アルゴリズムの適応： 著者らは、非重複なカバレッジと容量制限という制約の下で、3つの異なるアプローチ（制約付きスペクトラル・バイクラスタリング、グリーディ・ローカルサーチ、マルチアームド・バンディット）を、結合された設定において扱えるよう適応させている。
3. 包括的な評価： 手法は、3つの異なるデータソースで評価されている：
   • 合成データ： 正解となる構造が既知の制御された環境。
   • 公開ベンチマーク： Amazon Reviews データセット（ベビー用品、楽器）。
   • 独自のデータ： 大規模な商用データセット（IKEA、インテリアデザイン）。

結果とパフォーマンス

評価には、Utility（総親和性）、Quality（平均親和性）、Lift（ランダム割り当てに対する改善度）、および Gini係数（ユーザー間のユーティリティ分布）の指標が用いられている。

• 解の質： 制約付きスペクトラル・バイクラスタリングは、すべてのデータセットにおいて、Lift、Quality、および公平性（最も低いGini係数）において一貫して最高のスコアを達成している。これは、基礎となる構造がノイズを含んでいたり重複していたりする場合でも、一貫性のある高親和性領域を復元することに特に効果的である。
• スケーラビリティと品質のトレードオフ：
  • バイクラスタリングは小規模なデータセットでは非常に効率的であるが、親和性行列が大きくなるにつれて計算コストが増大する（例：IKEAでの実行時間は1.2分であったが、Interior Designでは66.2分に増加した）。
  • バンディットベースの手法（UCB1およびトンプソン抽出法）は、大規模なデータセットに対するスケーラブルな代替案を提供し、非常に大規模なスケールにおいて、グリーディ法やSA法よりも大幅に短い実行時間で競争力のあるパフォーマンスを維持する。
  • グリーディ・ローカルサーチは、繰り返しのローカルサーチ・ステップがあるため、一般にバンディット法よりも低速である。
• ベースラインの性能： シミュレーテッド・アニーリングは、解の質において提案手法よりも大幅に劣り、かつ最も高い計算コストを要する（しば_しば数時間を要する）。著者らは、これを、単一エンティティの移動を用いて高次元の組合せ空間で意味のある進展を得ることの難しさに起因すると考えている。

意義と主張

本論文は、ユーザーとアイテムの結合構造を明示的にモデル化することが、効果的なキャンペーン設計において極めて重要であると主張している。結果は以下を示唆している：

• 結合最適化の優位性： アイテム選択とユーザー割り当てを切り離すと、結合最適化によってのみ現れるグループを見落としてしまう。
• 潜在的な意図の捕捉： 定性的な分析（Musical Instrumentsデータセットなど）によれば、バイクラスタリングは表面的な分類学ではなく、潜在的なユーザーの意図（例：サックスのメンテナンス用品のグループ化）に沿ったキャンペーンを復元する。
• ノイズへの堅牢性： バイクラスタリングは、クラスターの分散やノイズが増加しても堅牢であり、親和性信号が一部のペアに集中している一方で、ユーザーごとに分散している場合に、個々のエンティティの信号に依存する手法よりも優れた性能を示す。
• 実用的なトレードオフ： バイクラスタリングは最高の品質をもたらすが、実行時間が主要な制約となる非常に大規模な商用展開においては、バンディットベースの手法が実行可能なスケーラブルな代替案となる。

著者らは、彼らのフレームワークはターゲティングの関連性と効率を向上させるものの、行動データから学習された埋め込みに依存しているため、ユーザー・ターゲティングにおける既存の格差を助長しないための透明性と公平性への配慮が必要であると結論づけている。