技术摘要：面向电子商务营销活动的受限用户-物品分配

问题定义：自动定向（Auto-Targeting）

本文研究了电子商务营销中一种被称为自动定向的组合分配问题。不同于传统的将物品选择与用户分配解耦或假设预定义营销结构的方法，这项工作将该问题形式化为一个联合优化任务。其目标是同时将一组用户和一组物品划分为 $K$ 个不相交的营销活动（组），使得：

1. 内聚性（Cohesion）： 每个营销活动最大化其分配的用户与物品之间的总组内亲和力（within-group affinity）。
2. 不相交性（Disjointness）： 每个用户和每个物品最多出现在一个营销活动中。
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）作为基准：

1. 受限谱双聚类（Constrained Spectral Biclustering）

该方法通过改进谱共聚类（spectral co-clustering）来识别用户-物品亲和矩阵中的密集区域。

• 过采样（Oversampling）： 它首先计算 $k' = \alpha k$ 个双聚类（其中 $\alpha \ge 2$），以确保拥有多样化的候选池。
• 剪枝（Pruning）： 对候选集进行剪枝以满足规模约束。根据物品和用户在其双聚类内的平均亲和力，按顺序移除它们，直到达到最大规模。
• 选择（Selection）： 剩余的候选集按密度（平均亲和力）进行排名，选出前 $k$ 个不重叠的双聚类作为最终的营销活动。

2. 多臂老虎机（MAB）优化

该方法将营销活动视为强化学习框架中的“臂”，平衡利用（将实体分配给高亲和力活动）与探索。

• 耦合奖励（Coupled Rewards）： 奖励是内生的；一个实体的亲和力取决于该营销活动当前的组成。
• 策略： 作者实现了两种探索奖励机制：
  • UCB1： 为亲和力得分添加置信上限。
  • 汤普森采样（Thompson Sampling）： 使用高斯噪声扰动得分，随着营销活动接收到的分配增加，噪声逐渐减小。
• 机制： 算法在用户分配阶段和物品分配阶段之间交替进行，使用带有指数衰减的滚动窗口统计数据来适应不断变化的营销活动组成。

3. 贪婪局部搜索（Greedy Local Search）

该策略采用带有容量约束的贪婪程序，随后进行精细化处理。

• 贪婪分配： 实体根据最大得分增量被分配到营销活动中，处理顺序按潜在收益降序排列。
• 成对交换（Pairwise Swaps）： 局部搜索步骤评估不同营销活动之间的实体交换。如果交换能在保持可行性的同时提高目标函数值，则执行交换。
• 迭代： 该过程在固定次数的迭代中交替进行用户和物品的更新。

基准：顺序模拟退火（Sequential Simulated Annealing）

作者使用模拟退火（SA）作为基准。全局问题被分解为 $K$ 个顺序子问题。对于每个营销活动，SA 通过受温度控制的接受概率执行随机局部搜索（使用添加、移除和交换操作），以逼近最优双聚类。

核心贡献

1. 自动定向的形式化： 本文定义了一个全新的联合优化问题，能够同时推断营销活动结构和用户-物品分配，解决了现有方法通常固定其中一侧分配的问题。
2. 算法适配： 作者通过改进三种不同的方法（受限谱双聚类、贪婪局部搜索和多臂老虎机），以处理耦合设置下不相交覆盖和容量限制的特定约束。
3. 全面的评估： 方法在三个不同的数据源上进行了评估：
   • 合成数据： 具有已知地面真值结构的受控环境。
   • 公开基准： Amazon Reviews 数据集（婴儿用品、乐器）。
   • 自有数据： 大规模商业数据集（宜家、室内设计）。

结果与性能

评估采用了以下指标：效用（Utility）（总亲和力）、质量（Quality）（平均亲和力）、提升度（Lift）（相对于随机分配的改进）以及 基尼系数（Gini Coefficient）（效用在用户间的分布）。

• 解的质量： 受限谱双聚类在所有数据集的提升度、质量和公平性（最低基尼系数）方面始终取得最高分。即使在底层结构具有噪声或重叠的情况下，它在恢复连贯的高亲和力区域方面也特别有效。
• 可扩展性与质量的权衡：
  • 双聚类法在较小的数据集上效率极高，但随着亲和矩阵的增长，计算成本会变得非常高（例如，在 IKEA 数据集上的运行时间为 1.2 分钟，而在 Interior Design 数据集上增加到 66.2 分钟）。
  • 基于老虎机的方法（UCB1 和汤普森采样）为大规模数据集提供了可扩展的替代方案，在极大规模下能以显著更短的运行时间维持具有竞争力的表现。
  • 贪婪局部搜索由于需要重复的局部搜索步骤，通常比基于老虎机的方法更慢。
• 基准表现： 模拟退火在解的质量方面明显逊于所提方法，且计算成本最高（通常需要数小时）。作者将其归因于在维度极高的组合空间中使用单实体移动很难取得实质性进展。

意义与主张

论文声称，显式建模联合用户-物品结构对于有效的营销活动设计至关重要。研究结果表明：

• 联合优化更优： 将物品选择与用户分配解耦会错过那些只有通过联合优化才能显现的组合。
• 双聚类捕捉潜在意图： 定性分析（如在乐器数据集上）显示，双聚类可以恢复与潜在用户意图一致的营销活动（例如，将萨克斯管保养用品归为一类），而非仅仅基于表面分类。
• 对噪声的鲁棒性： 双聚类对增加的聚类方差和噪声具有鲁棒性，在亲和信号在全球范围内集中在极少数对（pairs）中、但在单个用户层面较为分散时，其表现优于依赖个体实体信号的方法。
• 实际权衡： 虽然双聚类产生的质量最高，但基于老虎机的方法为运行时长作为主要约束条件的超大规模商业部署提供了一个可行的、可扩展的替代方案。

作者总结道，虽然其框架提高了定向的相关性和效率，但该框架依赖于从行为数据中学习到的嵌入，因此需要考虑透明度和公平性，以避免强化用户定向中现有的差异。