Bayesian inference for partial orders from random linear extensions: power relations from 12th Century Royal Acta

技术摘要：基于随机线性扩展的部分序贝叶斯推断

问题陈述
本文解决了从排序数据中推断随时间演变的社会等级的统计挑战，其中底层结构未必是完全（全）序。作者分析了 12 世纪英格兰和诺曼王室 Acta（法律文件）中的 371 份证人名单，记录了 67 位主教的列出顺序。历史学家假设这种排序反映了基于地位、资历和政治影响力的社会等级。然而，数据存在噪声且不完整（每份名单仅包含主教的子集），且底层等级可能包含不可比较的 actor 对（即部分序），而非单一的线性排名。现有的排序数据模型（如 Mallows 模型和 Plackett-Luce 模型）通常假设全序或上下文无关的概率，这可能不适用于该历史背景，因为在该背景下虽然预期具有传递性，但顺序是部分的。

方法论
作者提出了一种贝叶斯隐马尔可夫模型（HMM），其中潜在状态是演变的偏序集（poset），而观测数据是该偏序集的随机线性扩展。

1. 潜在变量参数化：

   • 时间 $t$ 处的偏序集 $h(t)$ 由潜在的 $K$ 维地位矩阵 $Z(t)$ 生成。
   • 对于每位主教 $j$，潜在权威向量 $U^{(t)}_j$ 随时间演变为一阶向量自回归（VAR）。
   • 基于资历的协变量效应 $\beta_{s_{t,j}}$ 被添加到权威向量中以形成地位向量：$Z^{(t)}_j = U^{(t)}_j + \mathbf{1}_K \beta_{s_{t,j}}$。
   • 偏序集 $h(t)$ 由 $Z(t)$ 的列导出的 $K$ 个全序的交集定义。当且仅当对于所有 $k=1,\dots,K$ 都有 $Z^{(t)}_{i,k} > Z^{(t)}_{j,k}$ 时，主教 $i$ 在偏序集中排在主教 $j$ 之前。
   • 维度 $K$ 选为 $\lfloor D/2 \rfloor$（其中 $D$ 是活跃主教的最大数量），确保模型能够表示任何可能的偏序集（通用表示性质）。

2. 观测模型（插队机制）：

   • 观测到的名单被建模为真实偏序集的“有噪声”线性扩展。
   • 作者引入了一种“插队”机制：以概率 $p$，名单中的下一个 actor 是均匀随机选择的（忽略偏序集约束）；否则，该 actor 是根据剩余子序的随机线性扩展选择的。
   • 这允许出现“噪声”，即观测顺序与底层等级相矛盾，同时保持有效线性扩展具有更高概率的约束。
   • 该模型通过对现有 actor 诱导的子序进行条件化，来处理不完整的名单（主教的子集）。

3. 先验与一致性：

   • 偏序集过程的先验被构建为边缘一致的，这意味着由 actor 子集诱导的子序分布与全序分布是一致的。这是通过对潜在向量 $U$ 和相关参数 $\rho$ 使用特定的先验来实现的。
   • 超参数 $\rho$ 控制偏序集的“深度”（最长链的长度）。先验设计为关于深度是非信息性的，避免了在所有偏序集上的均匀先验中观察到的对深度为 3 的偏序集的集中现象。
   • 资历效应 $\beta$ 被约束为有序（$\beta_1 > \beta_2 > \dots$），以反映历史预期，即资历与地位相关，尽管也测试了无约束模型。

4. 推断：

   • 后验推断使用带有 Metropolis-Hastings 更新的马尔可夫链蒙特卡洛（MCMC）进行。
   • 似然函数涉及计算线性扩展的数量，这是一个 #P-完全问题。作者利用了递归计数算法（特别是 lecount 包），这对于该数据集中较少的 actor 数量（$m \le 22$）是可行的，但限制了其在更大问题上的可扩展性。

主要贡献

• 新颖的模型类别： 本文引入了一个通用框架，用于建模底层结构为部分序的时间序列排序数据，推广了现有的 Mallows 和 Plackett-Luce 等模型。
• 边缘一致性： 作者推导并证明了其针对偏序集的潜在变量先验是边缘一致的，这一性质在针对部分序的临时先验中经常被违反。
• 通用表示： 他们证明，当潜在维度 $K \ge \lfloor D/2 \rfloor$ 时，模型可以表示任何可能的偏序集时间序列，确保不会对复杂等级产生结构性偏差。
• 历史应用： 这是对 12 世纪王室 Acta 证人名单的首次统计分析，明确将社会等级建模为部分序，区分了资历效应与个人权威。

结果

• 模型拟合： 基于偏序集的模型在拟合优度（通过留一交叉验证和贝叶斯因子衡量）方面优于更简单的替代方案（顶点 - 串联 - 并行序、桶序）以及 Plackett-Luce 时间序列混合模型。
• 资历与权威： 分析证实地位对资历有强烈的依赖性，且资历的影响随着排名数字的增加而减弱。然而，该模型成功分离了“权威”（对资历的偏离）。
• 历史见解：
  • 诺曼主教： 模型检测到诺曼主教（例如来自阿夫朗什、巴约、埃夫勒的主教）相对于英格兰主教的地位从 12 世纪初开始下降，这一趋势此前未被量化。
  • 政治影响力： 特定主教的地位（如斯蒂芬国王的兄弟亨利·德·布卢瓦和埃利的奈杰尔）的波动方式与政治恩宠或失宠相关，且独立于他们的资历。
  • 等级结构： 重建的共识偏序集相对较浅，通常由几组中等排名的主教组成，上方或下方只有少量 actor，而不是一个深层、僵化的等级结构。

意义与主张
本文声称其主要贡献是开发了一种统计上严谨的方法，用于从有噪声、不完整的排序数据中推断演变的偏序集。通过将此方法应用于历史 Acta，作者提供了关于 12 世纪社会等级如何运作的定量证据，特别是区分了结构性资历与流动的政治权威。

作者对其方法的计算可扩展性持谨慎态度，承认计算线性扩展数量的 #P-完全性质将模型限制在 actor 数量较少（约 20 个）的数据集上。他们建议，对于更大的数据集，可能需要对偏序集类别（如 VSP 或桶序）进行必要的妥协。他们还指出，虽然他们的模型拟合数据良好，但“噪声”模型假设错误仅在一个方向发生（插队），未来的工作可以探索双向噪声模型。

最终，本文认为，假设全序（如标准排名模型中那样）对于此类社会数据是不合理的，而部分序模型提供了对历史社会结构更准确、更可解释的表示。