Generalized Top-k Mallows Model for Ranked Choices

基本信息

• 论文ID: 2510.22040
• 标题: Generalized Top-k Mallows Model for Ranked Choices
• 作者: Shahrzad Haddadan (Rutgers Business School), Sara Ahmadian (Google Research)
• 分类: cs.LG, cs.DS, stat.ML
• 发表会议: NeurIPS 2025 (39th Conference on Neural Information Processing Systems)
• 论文链接: https://arxiv.org/abs/2510.22040

摘要

经典的Mallows模型是建模用户偏好的基础工具，但在捕捉真实场景时存在局限性——用户通常只关注有限的偏好项目集合，对其余项目无差异。本文针对广义top-k Mallows模型的若干挑战展开研究，聚焦于买家选择分析。核心贡献包括：(1) 针对广义top-k Mallows模型定制的新型采样方案；(2) 该模型下计算选择概率的高效算法；(3) 从观测选择数据估计模型参数的主动学习算法。这些贡献为关键决策场景中的分析和预测提供了新工具，并通过严格的数学分析和大量合成及真实数据实验验证了方法的可扩展性和准确性。

研究背景与动机

问题定义

本文要解决的核心问题是：如何在用户只提供部分排序信息（top-k列表）而非完整排序的现实场景中，有效建模用户偏好并预测其选择行为。

问题重要性

1. 实际应用广泛：推荐系统、广告平台、搜索引擎、新闻聚合器等场景中，用户通常只表达对有限数量项目的偏好
2. 商业决策价值：准确预测客户选择行为对收益管理、产品组合优化等决策至关重要
3. 理论意义：扩展经典概率排序模型到更现实的部分排序场景

现有方法的局限性

1. 经典Mallows模型：仅限于完整排列（full permutations），无法处理部分排序
2. Multinomial Logit (MNL)模型：虽简单但表达能力有限，满足不相关备选项独立性（IIA）假设，限制了对复杂选择行为的建模
3. 已有top-k扩展：Chierichetti等人(2018)提出的top-k Mallows模型缺乏高效的采样算法和选择概率计算方法
4. 参数学习困难：从选择数据（而非完整排序）学习模型参数缺乏理论保证

研究动机

作者认为，将Mallows模型扩展到top-k列表能更真实地反映用户偏好结构，但需要解决三个关键算法问题：高效采样、选择概率计算和参数学习。

核心贡献

本文的主要贡献包括：

1. PRIM采样算法：提出Profile-based Repeated Insertion Method (PRIM)，实现从TopKGMM分布的高效采样，将时间复杂度从O(k²4^k + k²log n)降低到O(k2^k + k²log n)
2. DYPCHIP选择概率算法：设计Dynamic Programming for Choice Probabilities (DYPCHIP)算法，能够高效计算top-k Mallows模型下的选择概率
3. BUCCHOI主动学习算法：开发Build Center from Choices (BUCCHOI)主动学习算法，通过呈现指定大小的产品组合并观察选择，推断分布中心和中心大小k，样本复杂度为Θ(r²log n)
4. 模型泛化：将Chierichetti等人的top-k Mallows模型扩展为广义版本（TopKGMM），为每个产品关联权重
5. 实证验证：在Sushi偏好数据集上证明top-k Mallows模型比MNL模型具有显著更高的预测准确性

方法详解

任务定义

输入：

• 产品集合 N = n ∪ {∅}（包含n个产品和"不购买"选项）
• 产品组合（assortment）A ⊆ n

输出：

• 用户从组合A中选择产品i的概率 C_D(i, A)

模型假设：

• 用户偏好遵循TopKGMM分布D
• 用户选择函数：C_τ(A) = i 当且仅当i是A∪{∅}中相对于τ排名最高的元素

模型架构

1. TopKGMM分布定义

给定中心τ* ∈ T_{k,N}和参数β ≥ 0, w ∈ R^{k+1}_{≥0}, p > 0，top-k列表τ的概率为：

P_D[τ] ∝ exp(-β K_{p,w}(τ, τ*))

其中距离度量定义为：

K_{p,w}(τ, τ*) = w_0·p·Q(τ) + Σ_{i∈[k]} w_i·(I_i(τ) + p·P_i(τ))

关键组件：

• I_i(τ)（反转向量）：优先级低于i但在τ中排名更高的元素数量
• P_i(τ)：原本排名低于i但在τ中不可比的元素数量
• Q(τ)：τ*中未排序元素间的不可比对数量
• w_i：元素权重，允许不同元素有不同重要性

2. Profile概念

Profile定义：S ⊆ k表示样本top-k列表τ与中心τ的交集，即τ ∩ τ = S

Profile概率（Lemma 3.3）：

P_D[S] ∝ exp(-βf(S))·Z(S)

其中：

f(S) = w_0·p·Q(S) + Σ_{j∈[k]\S} w_j(I_j(S) + p·P_j(S))

Z(S) = C(n-k, k-ℓ)·(k-ℓ)! · Π_{j=1}^ℓ Σ_{r=0}^{k-j} e^{-βw_{s_j}r}

这一分解是算法设计的核心创新，将复杂的top-k列表分布分解为profile选择和条件排序两个阶段。

技术创新点

1. PRIM采样算法（Algorithm 3-5）

核心思想：

1. 首先根据P_DS采样profile S
2. 然后在给定S的条件下，通过重复插入法构造τ

算法流程：

1. 预计算所有profile的概率（O(2^γk)时间，γ=min{k,n-k}）
2. 采样profile S
3. 初始化：从[n]\[k]中均匀随机采样k-ℓ个元素
4. 按优先级顺序插入S中元素s，在位置j插入的概率为：
   P(插入s在位置j) ∝ exp(-βw_s·j)

创新点：

• 解决了Chierichetti等人留下的开放问题（缺乏类似RIM的采样方法）
• 通过profile分解显著降低了复杂度
• 预处理后每个样本的摊销成本仅为O(k log n)

2. DYPCHIP选择概率算法（Section 4.1）

核心思想：通过动态规划，在给定profile S的条件下计算选择概率

算法结构：

• 三维DP表 π_S(i, j, q)：
  • i：产品组合A中的第i个元素
  • j：当前位置
  • q：PRIM算法的第q次迭代
  • 含义：在第q次迭代后，a_i是A∅中排名最高且位于第j位的概率

递推关系：

当新元素不在A中：
π_S(i,j,q) = π_S(i,j,q-1)·P(插入>j) + π_S(i,j-1,q-1)·P(插入≤j-1)

当新元素在A中：
π_S(i,j,q) = π_S(i,j,q-1)·P(插入>j)
π_S(cur,j,q) = P(插入=j)·Σ_{i<cur}Σ_{j'≥j}π_S(i,j',q-1)

最终选择概率：

C_D(a,A) = Σ_{S⊆[k]} P_D[S]·(π_S(a) + π̄_S(a))

复杂度：O(2^{min{k,n-k}}·k³·|A|²)

3. BUCCHOI主动学习算法（Algorithm 2）

核心思想：通过主动选择产品组合并观察选择来学习中心τ*

关键子算法FINDTOP（Algorithm 1）：

• 维护矩阵X_：记录产品i被选择而j未被选择的次数差
• 判断准则：Y_ = X_/m，如果存在a使得Y_{aa'} > (1+|A|)/2对所有a'∈A∅{a}成立，则a是顶部元素

理论保证（Lemma 5.2）：

• 当β ≥ log(3)/w_时
• 使用Θ(ζ(r+1)²log n)个样本
• 以概率至少1-o(n^{-ζ})正确识别顶部元素

BUCCHOI流程：

1. 维护三个集合：T（确定在τ中）、B（确定在τ̄中）、U（未知）
2. 重复：选择大小为r的组合A，调用FINDTOP
3. 如果找到顶部元素，移至T；否则整个A移至B
4. 最后调用SORTCNTR对T中元素排序

样本复杂度：Θ(r²log n)

实验设置

数据集

1. Sushi偏好数据集（真实数据）

• 来源：Kamishima et al. (2005)
• 规模：5000个用户偏好，每个表示为top-10列表
• 产品数：100种不同寿司类型
• 划分：80%训练集，20%测试集
• 用途：评估模型预测能力和与MNL比较

2. 合成数据

• 参数范围：
  • n（产品数）：200-20000
  • k（top-k大小）：6-16
  • β（衰减参数）：0.01-5
  • p（Kendall's Tau参数）：0.01-5
  • r（组合大小）：根据k调整
• 用途：评估算法准确性和复杂度，验证理论结果

评价指标

1. 预测准确性

• 测试误差：经验选择概率与预测概率之间的绝对误差
• 计算方法：在测试集上随机采样组合，记录实际选择，与DYPCHIP预测对比

2. 学习准确性

• Kendall's Tau距离：学习到的中心与真实中心之间的距离K_p(τ_learned, τ_true)
• FINDTOP准确率：正确识别顶部元素的频率

3. 时间复杂度

• PRIM：预处理时间和每样本摊销时间
• DYPCHIP：计算所有选择概率的总时间
• 学习算法：达到指定准确度所需的样本数

对比方法

1. Multinomial Logit (MNL)：经典选择模型baseline
2. Chierichetti等人的DP采样：之前的top-k Mallows采样方法
3. 无聚类vs聚类：单一TopKGMM vs 混合TopKGMM（2-5个簇）

实现细节

Sushi数据集实验

• 参数调优：网格搜索β∈{0.01,0.025,0.05,...,5}, p∈{0.05,0.1,...,2}
• 聚类方法：基于K_p距离的k-means，簇数∈{2,3,5}
• 轮廓系数：用于评估聚类质量
• 中心学习：使用BUCCHOI-II（Algorithm 7）处理top-10列表样本

合成数据实验

• 重复次数：每组参数10次运行
• 样本数范围：50-250（根据任务调整）
• 权重设置：w=2⃗1或w=32222111等
• 计算环境：MacBook Pro M1 Max, 32GB RAM

实验结果

主要结果

1. TopKGMM vs MNL（真实数据）

无聚类情况（Table 1）：

• 最佳参数：β=0.05, p=0.5
• TopKGMM测试误差：0.0817
• MNL测试误差：0.168
• 相对提升：51.4%误差减少

关键发现：

• β较小时（0.01-0.1）性能较好，表明分布相对均匀
• p=0.5时效果最佳，平衡了不同类型的不一致性
• TopKGMM显著优于MNL，验证了模型表达能力

聚类情况（Table 2，2个簇）：

• p=0.1, β=0.1：测试误差0.0771
• p=1.25, β=0.05：测试误差0.0788
• 观察：聚类后性能略有提升，但轮廓系数很低（<0.012），表明数据可能来自单一分布

2. DYPCHIP准确性（Figure 2a）

实验设置：n=200, k=6, r=4, p=0.5, w=2⃗1

• 使用PRIM生成样本，计算经验选择频率
• 与DYPCHIP预测对比
• 在20个随机组合上重复

结果：

• 平均绝对误差<0.02
• 标准差很小，表明预测稳定
• 验证了DYPCHIP的正确性

3. PRIM时间复杂度（Table 3）

预处理时间（秒）：

每样本摊销时间（秒）：

观察：

• 预处理时间随k指数增长（符合O(k2^k)理论）
• 摊销时间非常小，大规模采样高效
• n的影响很小（验证了O(k log n)复杂度）

4. DYPCHIP时间复杂度（Figure 3）

实验参数：β=0.6, p=0.5, w=2⃗1, r=k-2

• k=6时：约0.05秒
• k=8时：约0.5秒
• k=10时：约5秒
• k=12时：约50秒

观察：

• 时间随k指数增长
• n的影响较小
• k>12时计算成本显著，限制了实际应用

消融实验

1. FINDTOP样本复杂度（Figure 2b, Figure 4）

参数影响：

• β的影响（n=900, k=10, r=5, p=1）：
  • β=0.2：需要200+样本达到80%准确率
  • β=0.6：需要100样本达到95%准确率
  • β=1.2：需要50样本达到100%准确率
  • 结论：β越大，分布越集中，学习越容易
• k的影响：
  • k=12 vs k=14（其他参数相同）：k越大需要更多样本
  • 符合理论的O(r²log n)复杂度
• r的影响：
  • r=5 vs r=10：r越大每次观察信息更多，但也增加了噪声

2. BUCCHOI样本复杂度（Figure 2c-d, Figure 5）

实验1（n=500, k=10, p=0.5, w=2⃗1）：

• 50样本：Kendall's Tau距离≈12
• 100样本：距离≈3
• 200样本：距离≈0（完美恢复）

实验2（n=300, k=8, p=2, w=32222111）：

• 非均匀权重增加了学习难度
• 需要更多样本达到相同准确度
• 但仍在Θ(r²log n)范围内

β的影响（Table 5，n=1000, k=12）：

观察：

• β≥1时，100样本足以完美恢复中心
• β=0.4时即使100样本仍有误差
• 验证了理论要求β≥log(3)/w_

案例分析

Sushi数据集聚类分析

正轮廓系数的聚类：

• p=0.1, 2簇：轮廓系数=0.0063
• p=1.25, 2簇：轮廓系数=0.0078
• p=5, 2簇：轮廓系数=0.0110
• p=5, 3簇：轮廓系数=0.0023

解释：

• 轮廓系数极低表明簇内差异大
• 单一TopKGMM可能更合适
• 这与无聚类时误差更低一致

实验发现

1. 模型表达能力：TopKGMM在真实数据上显著优于MNL，误差减少超过50%
2. 算法效率：
   • PRIM在预处理后采样高效
   • DYPCHIP对k<12的情况实用
   • 学习算法样本复杂度对数级别
3. 参数敏感性：
   • β是关键参数，影响分布集中度和学习难度
   • p需要根据数据特性调优
   • 权重非均匀性增加学习复杂度
4. 理论验证：实验结果与理论复杂度分析高度一致

相关工作

1. 选择建模（Choice Modeling）

Multinomial Logit (MNL)：

• Bradley & Terry (1952)提出
• 优点：简单、可解释、满足IIA
• 缺点：表达能力有限

混合MNL：

• McFadden & Train (2000)推广
• 学习方法：EM算法（Dempster et al. 1977）
• 理论保证：Chierichetti et al. (2018b), Oh & Shah (2014)

其他框架：

• Mallows选择模型（Désir et al. 2021）
• 马尔可夫链模型（Blanchet et al. 2016）

2. Mallows模型

经典Mallows模型：

• Mallows (1957)原始定义
• 基于Kendall's Tau距离的排列分布
• 规范化常数有闭式解

top-k扩展：

• Fligner & Verducci (1986), Lebanon & Mao (2008)早期工作
• Chierichetti et al. (2018a)提出TopKMM
• 问题：缺乏闭式规范化常数和高效采样

广义Mallows模型：

• Fligner & Verducci (1986)引入权重
• 本文首次扩展到top-k列表

3. Mallows模型的选择应用

Désir等人的工作：

• Désir et al. (2021)首次用Mallows建模选择
• 证明比MNL预测更准确
• 开发了完整排列的选择概率DP算法

后续研究：

• 收益管理和产品组合优化（Désir et al. 2021, 2023; Feng & Tang 2022）
• 简化模型（Feng & Tang 2022）

本文贡献：扩展到top-k列表，提供完整算法工具链

4. 参数学习

从完整排序学习：

• Liu & Moitra (2018), Braverman & Mossel (2008)
• Awasthi et al. (2014), Seshadri et al. (2020)

从部分观察学习：

• 成对比较（Lu & Boutilier 2014; Vitelli et al. 2018）
• 从选择学习：较少研究，缺乏理论保证

本文贡献：

• 首个从选择数据学习top-k Mallows的主动学习算法
• 提供有限样本复杂度保证Θ(r²log n)

结论与讨论

主要结论

1. 理论贡献：
   • 提出广义top-k Mallows模型（TopKGMM）
   • 通过profile分解实现高效算法设计
   • 提供严格的数学分析和复杂度保证
2. 算法贡献：
   • PRIM：O(k2^k + k²log n)采样算法
   • DYPCHIP：O(2^{min{k,n-k}}k³|A|²)选择概率算法
   • BUCCHOI：Θ(r²log n)样本复杂度的主动学习算法
3. 实证贡献：
   • 在真实数据上验证TopKGMM优于MNL（51%误差减少）
   • 验证算法的准确性和效率
   • 提供参数调优指导

局限性

1. 计算复杂度：
   • DYPCHIP对k的指数依赖限制了大k场景（k>15）
   • PRIM预处理时间随k指数增长
   • 实际应用中k需要较小
2. 理论假设：
   • BUCCHOI要求β≥log(3)/w_，限制了低β场景
   • 假设∅∉τ*，否则只能恢复部分中心
3. 模型假设：
   • 单一TopKGMM可能不足以捕捉多类型用户
   • 混合模型的参数学习仍是开放问题
4. 实验范围：
   • 仅在一个真实数据集上验证
   • 需要更多领域的应用验证

未来方向

1. 学习混合TopKGMM：
   • 从选择数据学习多个客户类型
   • 类似于混合MNL的学习算法
2. 降低计算复杂度：
   • 近似算法减少对k的指数依赖
   • 分布式或并行计算
3. 扩展模型：
   • 考虑上下文信息（contextual Mallows）
   • 动态偏好建模
4. 实际应用：
   • 收益管理和定价
   • 推荐系统优化
   • A/B测试设计

深度评价

优点

1. 理论严密性：
   • 所有算法都有严格的正确性证明
   • 复杂度分析完整（Theorems 3.1, 4.1, 5.1）
   • 样本复杂度有概率保证
2. 方法创新性：
   • Profile分解是核心创新，巧妙地将复杂分布分解为易处理的部分
   • 解决了Chierichetti等人的开放问题
   • 首次实现top-k Mallows的选择概率计算
3. 实验充分性：
   • 合成数据广泛覆盖参数空间
   • 真实数据验证实际效果
   • 消融实验分析各参数影响
   • 代码公开可复现
4. 实用价值：
   • 在真实数据上显著优于MNL
   • 算法在合理参数范围内高效
   • 提供完整的工具链（采样-推断-学习）
5. 写作清晰度：
   • 结构清晰，逻辑严密
   • 数学符号定义准确
   • 算法伪代码详细（附录）

不足

1. 计算可扩展性：
   • k的指数依赖是根本限制
   • 对于k>15的场景不实用
   • 缺少近似算法讨论
2. 实验局限：
   • 仅一个真实数据集：Sushi数据集可能不代表所有应用场景
   • 未与其他top-k选择模型对比（如top-k MNL变体）
   • 缺少大规模数据集实验
3. 模型假设：
   • 假设∅∉τ*限制了应用范围
   • 单一分布假设在聚类效果不明显时可能不合理
   • 未讨论模型误设定的鲁棒性
4. 参数选择：
   • β和p的选择依赖网格搜索
   • 缺少自动参数选择方法
   • 权重w的设定缺少指导
5. 理论-实践差距：
   • BUCCHOI的理论要求β≥log(3)/w_≈1.1，但实验中β=0.05也有效
   • 理论复杂度是最坏情况，实际可能更好

影响力

1. 学术贡献：
   • 填补了top-k Mallows选择建模的空白
   • 为后续研究提供了基础算法
   • 可能激发更多基于Mallows的选择模型研究
2. 实用价值：
   • 推荐系统：建模用户对top-k推荐的偏好
   • 电商：产品组合优化
   • 搜索引擎：理解用户点击行为
3. 可复现性：
   • 代码公开：https://github.com/ShahrzadGit/topkmallows-choices
   • 使用公开数据集
   • 算法伪代码详细
4. 局限性对影响的制约：
   • k的限制可能阻碍在大规模应用中的采用
   • 需要更多真实数据集验证才能广泛应用

适用场景

高度适用：

1. 小到中等k的推荐系统（k≤12）：
   • 显示top-10产品并预测用户选择
   • 新闻推荐、视频推荐
2. 产品组合优化：
   • 零售商选择展示哪些产品
   • 菜单设计
3. A/B测试：
   • 比较不同产品组合的吸引力
   • 主动学习算法可减少测试样本

谨慎使用：

1. 大k场景（k>15）：计算成本高
2. 实时系统：DYPCHIP计算时间可能不满足延迟要求
3. 极端非均匀权重：学习复杂度增加

不适用：

1. 完整排序已知：应使用经典Mallows模型
2. 用户偏好完全随机：MNL可能更简单有效
3. 需要可解释性：Mallows模型的参数解释性不如MNL

参考文献（关键文献）

1. Mallows (1957): 原始Mallows模型
2. Chierichetti et al. (2018a): Top-k Mallows模型基础
3. Désir et al. (2021, 2023): Mallows选择模型开创性工作
4. Bradley & Terry (1952): MNL模型基础
5. McFadden & Train (2000): 混合MNL模型
6. Fligner & Verducci (1986): 广义Mallows模型

总结

本文在top-k Mallows模型和选择建模的交叉领域做出了重要贡献。通过巧妙的profile分解，作者设计了一套完整的算法工具链，并提供了严格的理论分析。实验验证了方法的有效性，特别是在真实数据上相比MNL的显著优势。

主要价值在于：(1) 理论上解决了重要的开放问题；(2) 实践上提供了可用的工具；(3) 为未来研究奠定了基础。

主要限制是对k的指数依赖，限制了在大k场景的应用。未来研究混合模型的学习和开发近似算法将进一步提升该方法的实用性。

对于需要建模部分排序偏好并预测选择行为的应用，本文提供的TopKGMM框架和算法是有价值的工具，特别是在k较小（≤12）且需要高预测准确性的场景。