Beyond Kemeny Medians: Consensus Ranking Distributions - Definition, Properties and Statistical Learning¶

会议: NeurIPS 2026
arXiv: 2602.10640
领域: 学习理论
关键词: 排序聚合, 共识排序分布, 局部中位数, 最优传输, 决策树算法

一句话总结¶

本文突破经典 Kemeny 中位数对多峰排序分布总结过于粗糙的瓶颈，提出基于局部中位数的稀疏狄拉克混合模型“共识排序分布”（CRD），建立了基于 Kendall $\tau$ 最优传输的失真界，并设计了自顶向下的二叉递归划分算法 COAST 实现高效统计学习。

研究背景与动机¶

排序与偏好数据在现代推荐系统、搜索引擎以及社会选择等场景中无处不在。然而，对 $n$ 个对象进行排序时，全排列构成的对称群 $\mathfrak{S}_n$ 空间基数高达 $n!$，且其天然缺乏向量空间结构，使得多元统计分析中基础的均值、方差及直方图平滑等概念难以直接推广。为了总结一组排列样本的集中趋势，经典的共识排序（Ranking Aggregation）通常借助度量（特别是 Kendall $\tau$ 距离）定义重心排列即 Kemeny 中位数，并通过样本到中位数的平均距离量化离散度。

然而，在实际应用中，人群偏好往往呈现显著的多峰性（Multimodal）与异质性，单点式的 Kemeny 中位数无法捕获多元混合的偏好簇结构，信息压缩极其粗糙；若退而使用参数化概率模型（如 Mallows 模型或 Plackett-Luce 模型），又会受限于严格的单峰或随机传递性假设；而若直接采用非参数经验分布 $\widehat{P}_N$，在样本量 $N \ll n!$ 的现实条件下其方差和不确定性又过大，无法直接使用。

面对这一两难困境，本文借鉴多元非参数统计中的局部均值与直方图划分思想，探索在离散非欧几里得的排列群上构建自适应的“分段共识”近似结构。核心 idea：将排列群空间递归划分为具有传递相容性的局部区域，在每个区域内定义由局部 Kemeny 中位数支撑的狄拉克测度凸组合——共识排序分布（CRD），通过成对比较边际概率严密控制最优传输失真，并借助二叉决策树算法 COAST 从数据中自顶向下递归学习最优划分。

方法详解¶

整体框架¶

共识排序分布（Consensus Ranking Distribution, CRD）旨在寻找介于极简但粗糙的全局中位数 $\delta_{\sigma^*}$（维度 0，失真最大）与无偏但方差极大的全经验分布 $\widehat{P}_N$（维度 $n!-1$）之间的一类稀疏狄拉克测度混合模型。给定对称群 $\mathfrak{S}_n$ 的一个划分 $\mathcal{P} = \{\mathcal{C}_1, \dots, \mathcal{C}_K\}$，每个区域 $\mathcal{C}$ 对应一个局部条件分布 $P_{\mathcal{C}}$，其中心为局部 Kemeny 中位数 $\sigma^*_{\mathcal{C}}$。算法通过最小化在局部区域内的成对逆序离散度，构建自顶向下的树状划分结构 COAST，并在各叶节点聚合得到经验 CRD。

整个学习与推理流程如下图所示：

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入样本数据与停止阈值<br/>Σ_1, ..., Σ_N, ε ≥ 0"] --> B["共识排序决策树 COAST<br/>自顶向下递归二叉划分"]
    B --> C["相容划分规则与离散度准则<br/>选择最小化子节点离散度的序偶 (i, j)"]
    C --> D["局部 Kemeny 聚合与模型剪枝<br/>各叶节点求解局部中位数与复杂度正则化"]
    D --> E["输出经验共识排序分布 P_P<br/>稀疏局部狄拉克测度加权混合"]

关键设计¶

1. 共识排序分布与其最优传输失真界：将多峰分布建模为局部中位数混合

针对单一 Kemeny 中位数无法表达多峰偏好分布的缺陷，本文在对称群划分 $\mathcal{P}$ 的基础上定义了局部中位数与共识排序分布。对满足 $P(\mathcal{C}) > 0$ 的任意区域 $\mathcal{C} \subset \mathfrak{S}_n$，局部 Kemeny 中位数定义为条件分布 $P_{\mathcal{C}}$ 上的风险极小点： $$\sigma^*_{\mathcal{C}} \in \arg\min_{\sigma \in \mathfrak{S}_n} \mathbb{E}[d_{\tau}(\Sigma, \sigma) \mid \Sigma \in \mathcal{C}]$$ 相应的局部离散度记为 $V(\mathcal{C}) := \min_{\sigma \in \mathfrak{S}_n} L_{P_{\mathcal{C}}}(\sigma)$。在此基础上，分布 $P$ 相对于划分 $\mathcal{P}$ 的共识排序分布定义为混合测度 $P_{\mathcal{P}} = \sum_{\mathcal{C} \in \mathcal{P}} P(\mathcal{C}) \delta_{\sigma^*_{\mathcal{C}}}$。以 Kendall $\tau$ 距离诱导的 Wasserstein 距离（最优传输代价）衡量失真时，论文证明了精细的理论上界： $$W_{d}(P, P_{\mathcal{P}}) \leq \mathcal{E}_P(\mathcal{P}) := \sum_{\mathcal{C} \in \mathcal{P}} P(\mathcal{C}) V(\mathcal{C}) \leq 2 \sum_{\mathcal{C} \in \mathcal{P}} P(\mathcal{C}) V'( \mathcal{C} )$$ 其中局部变异度 $V'(\mathcal{C}) = \sum_{i < j} p_{i,j}(\mathcal{C})(1 - p_{i,j}(\mathcal{C}))$ 完全由该区域内的成对边际概率 $p_{i,j}(\mathcal{C}) = \mathbb{P}\{\Sigma(i) < \Sigma(j) \mid \Sigma \in \mathcal{C}\}$ 决定。这一理论结果极为关键：它将高维非欧空间中的最优传输失真上界，完全解耦并归结为局部成对统计量，为无需遍历 $n!$ 空间的统计推断奠定了理论基础。

2. COAST 递归二叉划分算法与分裂准则：构建传递相容的排序树

直接在集合系统上优化划分 $\mathcal{P}$ 属于组合优化难问题，本文为此设计了 COAST（COnsensus rAnking deciSion Trees）算法。算法从根节点 $\mathcal{P}_1 = \{\mathfrak{S}_n\}$ 开始，递归选择候选项目序偶 $(i, j)$ 将当前单元 $\mathcal{C}$ 切分为两个不相交子集 $\mathcal{C}^{(0)}_{i,j} = \{\sigma \in \mathcal{C} : \sigma(i) < \sigma(j)\}$ 与 $\mathcal{C}^{(1)}_{i,j} = \mathcal{C} \setminus \mathcal{C}^{(0)}_{i,j}$。每个单元本质上由一组偏序约束 $\mathcal{I} \subset \{(i,j): 1 \leq i \neq j \leq n\}$ 唯一刻画： $$\mathcal{C} = \{\sigma \in \mathfrak{S}_n : \sigma(i) < \sigma(j), \forall (i,j) \in \mathcal{I}\}$$ 为了保证分裂后的子节点非空，候选序偶集合 $\mathcal{J}(\mathcal{C})$ 必须满足偏序的传递性相容要求，这使得候选集随深度增加迅速缩小。在节点划分准则上，COAST 提供了两种互补机制： - 最小化失真准则（Min distortion）：精确最小化加权局部离散度 $\widehat{\mathcal{E}}'_{(i,j)}(\mathcal{C}) = \widehat{P}_N(\mathcal{C}_{i,j}^{(0)}) \widehat{V}'_N(\mathcal{C}_{i,j}^{(0)}) + \widehat{P}_N(\mathcal{C}_{i,j}^{(1)}) \widehat{V}'_N(\mathcal{C}_{i,j}^{(1)})$； - 均衡划分准则（Balanced size）：选择使局部先验概率 $|p_{i,j}(\mathcal{C}) - 1/2|$ 最接近 0 的序偶。该准则不仅极大平衡了子节点样本量，而且将计算复杂度从 $O((\#\mathcal{I}(\mathcal{C}))^4)$ 陡降至 $O(\#\mathcal{I}(\mathcal{C}))$，在大规模排序任务上带来上百倍的加速。

3. 统计泛化保证与复杂度正则化剪枝：平衡失真偏差与方差

当基于有限样本 $\Sigma_1, \dots, \Sigma_N$ 进行经验最小化时，经验准则 $\widehat{\mathcal{E}}'_N(\mathcal{P}) = \sum_{\mathcal{C} \in \mathcal{P}} \widehat{P}_N(\mathcal{C}) \widehat{V}'_N(\mathcal{C})$ 包含 $U$-统计量波动与经验权重估计误差。论文借助二阶非退化 $U$-统计量集中不等式与 Hoeffding 展开，证明了在有限划分族 $\Pi_K$ 上的统计泛化一致界：以至少 $1-\delta$ 的概率，经验最优划分 $\widehat{\mathcal{P}}_N$ 满足： $$W_d(P, P_{\widehat{\mathcal{P}}_N}) / 2 \leq \min_{\mathcal{P} \in \Pi_K} \mathcal{E}'(\mathcal{P}) + 2 \sqrt{\frac{\gamma(\Pi_K)}{\chi(\Pi_K)} \frac{\log(4 \#\Pi_K / \delta)}{N}} + 2 C \frac{K \|d\|_{\infty}}{\chi^2(\Pi_K)} \sqrt{\frac{\log(8K/\delta)}{2N}}$$ 其中 $\chi(\Pi_K)$ 为单元测度下界，$\gamma(\Pi_K)$ 为单元内最大直径。为防止过拟合，COAST 引入后剪枝机制：先以较小的方差容忍阈值 $\epsilon$ 将树生长到包含较大节点数 $\mathcal{T}_K$，随后采用类似 CART 的最小代价复杂度剪枝（Cost-Complexity Pruning），通过惩罚目标 $\widehat{\mathcal{E}}'_N(\mathcal{P}'_k) + \lambda k$ 逐步合并使离散度增量最小的兄弟子节点，得到各复杂度下的最优嵌套子树序列，自适应确定成分个数 $K$。

损失函数 / 训练策略¶

在经验划分确定后，每个叶节点 $\mathcal{C} \in \mathcal{P}$ 的局部中位数求解转化为针对落入该单元的样本子集 $\{\Sigma_k : \Sigma_k \in \mathcal{C}\}$ 运行排序聚合算法 $\mathcal{A}$： $$\widehat{\sigma}^*_{\mathcal{C}} \in \arg\min_{\sigma \in \mathfrak{S}_n} \sum_{k : \Sigma_k \in \mathcal{C}} d_{\tau}(\Sigma_k, \sigma)$$ 当条件分布在局部满足严格随机传递性（SST）时，局部中位数可直接通过局部的 Copeland 排序精确求解：$\widehat{\sigma}^*_{\mathcal{C}}(i) = 1 + \sum_{j \neq i} \mathbb{I}\{\widehat{p}_{i,j}(\mathcal{C}) < 1/2\}$。对于一般情况，可接入局部 Markov 链搜索或局部排序深度（Local Depth）上升算法，快速收敛到局部最优重心。此外，结合局部深度可进一步构建平滑型局部概率模型 $\widetilde{P}_{\mathcal{C}}(\sigma) = \sum_{i < j} p_{\sigma^{-1}(i), \sigma^{-1}(j)}(\mathcal{C}) / Z_{\mathcal{C}}$，其归一化常数 $Z_{\mathcal{C}}$ 可通过单元约束下的均匀分布分解在 $O(n^2 \#\mathcal{I}(\mathcal{C}))$ 复杂度内精确解析计算。

实验关键数据¶

主实验¶

论文在由 $K$ 个具有不同中心的分散 Mallows 模型构成的混合排序数据集上验证算法性能，并在单机标准 PC 上对比了两种分裂准则（精确最小失真 vs 快速均衡划分）在不同规模 $n$ 及聚类簇数 $K$ 下的耗时表现。

序列规模 $n$	簇数 $K$	均衡划分准则（Balanced size, s）	最小失真准则（Min distortion, s）	计算加速比
10	4	0.0826	0.0923	1.12×
50	4	0.5197	3.5002	6.73×
100	4	1.7686	48.4428	27.39×
150	4	4.3720	168.9550	38.64×
10	8	0.2424	0.3229	1.33×
50	8	1.4242	13.9436	9.79×
100	8	4.6943	161.8610	34.48×
150	8	15.0220	1094.1330	72.84×

消融与树结构分析¶

在经典真实数据集 Sushi Preference Dataset（$n=10$）上，COAST 展现了极强的树结构可解释性与对异质群体的有效解耦。下表展示了使用最小失真准则在迭代划分过程中恢复出的前 8 个叶节点的局部测度与单元内部离散度：

叶节点编号	局部经验权重 $\widehat{P}(\mathcal{C})$	单元内离散度 $\widehat{V}'(\mathcal{C})$	关键划分特征说明
Leaf 1	0.13	8.88	优先偏好寿司类型 3 且偏好模式高度内聚
Leaf 2	0.14	8.81	次级序偶分割出的稳定子群体 A
Leaf 3	0.12	8.92	次级序偶分割出的稳定子群体 B
Leaf 4	0.14	8.72	优先偏好寿司类型 4 且离散度显著下降
Leaf 5	0.12	9.00	次级条件子群体 C
Leaf 6	0.12	8.87	次级条件子群体 D
Leaf 7	0.10	8.81	极端小众但高度自洽的偏好偏置群
Leaf 8	0.13	8.69	离散度最低（8.69）的紧凑偏好簇

关键发现¶

分裂准则的近似精度与效率：虽然均衡划分准则（Balanced size）未在每步贪婪保证失真最大下降，但其实际收敛后的经验失真与精确最小失真准则基本吻合，而在 $n=150, K=8$ 的大规模场景下计算时间从 1094.1 秒锐减至 15.0 秒，加速高达 72.8 倍。
多峰识别与拐点截断：随着树迭代生长，经验失真上界 $\widehat{\mathcal{E}}'$ 在达到真实成分数 $K$ 时出现清晰的平台拐点（Plateau），通过代价复杂度剪枝能稳定恢复混合分布的真实簇数。
局部深度增强异常检测：在多峰分布下全局深度（Global Depth）无法区分离群点，而基于 COAST 划分的局部深度（Local Depth）拉开了正常样本与离群样本间的对比差距，使 DD-plot 呈现出高度分离的聚类模式。

亮点与洞察¶

将最优传输失真降维到成对概率：巧妙利用 Kendall $\tau$ 距离与 Wasserstein 测度的耦合结构，将非凸排列空间中的测度传输代价约束为局部成对边缘概率的二次型，突破了高维离散概率推断的维度灾难。
传递性驱动的分裂空间缩减：在二叉决策树中将序偶分割与偏序传递性强制绑定，不仅自然维持了单元的半序几何结构，而且使深层节点的候选划分空间急剧萎缩，保障了算法的可行性。
非参数树模型对传统参数混合的替代：打破了过去处理混合排序问题对 Mallows/Plackett-Luce 等刚性参数假设的依赖，为大规模多峰排序数据的无监督聚类与密度估计提供了直观、可解释的树形非参数工具。

局限与展望¶

作者承认的局限：均衡划分启发式准则在何种理论分布条件下能够保证准最优收敛，目前仍缺乏充分的理论充要证明。
实际存在的局限：在面对部分排序（Partial Rankings）或带并列（Ties）的复杂偏好数据时，排序空间需要拓展至弱序（Weak Orders），传递性校验与成对概率更新的组合复杂度将显著增加。
未来改进思路：可将 COAST 算法拓展为集成模型（如随机排序森林 Random Ranking Forests），通过子空间序偶采样与多树平滑进一步降低方差，并推广到多视角标注者不一致性建模任务中。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统性提出共识排序分布与基于局部中位数的非参数框架，理论设计非常典雅。
实验充分度: ⭐⭐⭐⭐ 涵盖合成 Mallows 混合、Sushi 真实数据集及同质性检验，实证与理论紧密互证。
写作质量: ⭐⭐⭐⭐⭐ 数学证明严密完整，从概念动机到算法落地的逻辑链条行云流水。
价值: ⭐⭐⭐⭐⭐ 为非欧偏好数据挖掘与排序学习提供了全新的方法论工具，理论与实际应用潜力兼备。