Graphical methods for Order-of-Addition experiments¶

作者: Nicholas Rios, Dennis K J Lin
来源: Journal of the Royal Statistical Society Series B
主题: 统计计算 / 算法
相关性: 3/10
机构绿灯: Purdue University（US News 前 50，免分进入精读）
链接: https://doi.org/10.1093/jrsssb/qkaf020

一、领域脉络与小综述¶

这个方向是什么¶

Order-of-Addition (OofA) 实验解决的是这样一个根本问题：一个系统（如化学反应、药物调配、作业调度）的响应不仅取决于使用了哪些组件（components），还取决于这些组件被添加的顺序。目标是找到那个使响应最优（最大或最小）的排列。当前子方向聚焦于：当所有排列并非都可行时，如何建模约束、设计实验并寻找最优顺序。该方向目前处于算法构建与模拟验证阶段，严格的统计推断理论（如估计量的渐近最优性、设计最优性的决策理论框架）仍有待深化。

发展脉络 (History)¶

论文 introduction 梳理了 OofA 实验的发展，其脉络可串为：

奠基工作：Voelkel (2019) 和 Van Nostrand (2020)。前者引出了 OofA 实验的核心模型——Pairwise Order (PWO) 模型，该模型将响应建模为所有成对顺序指示变量（如 \( I\{\text{组件 }i\text{ 先于组件 }j\} \)）的线性组合。后者提出了一个类似的模型。这两项工作奠定了用线性模型处理顺序效应的基础，但它们都默认所有 \(m!\) 种排列均可行。原文所用引用句："Voelkel (2019) introduced the pair-wise order (PWO) model"，"Van Nostrand (2020) introduced a similar model"。留下的口子就是：大量实际场景中存在成对顺序约束，使得部分排列不可行。
主要进展：最优设计理论。在 PWO 模型框架下，Peng, Mukerjee & Lin (2019) 推导了 \(\phi_p\)-optimal 设计（一种广义最优性准则）的解析形式，给出了在无约束时最优设计的显式解。Lin & Peng (2019) 进一步将 \(\phi\)-最优性扩展到“最小点”设计（minimal-point designs）。这些工作为寻找“在单位成本下信息量最大”的实验方案提供了理论基础，但依然不处理图约束。原文引用句："Peng, Mukerjee, and Lin (2019) derived the \(\phi_p\)-optimal design...Lin and Peng (2019)... approached \(\phi\)-optimality in minimal-point designs."
当前前沿：处理约束与搜索算法。本文的位置就是在此前沿上。作者指出，已有文献中关于带约束 OofA 实验的研究极少。他们将约束建模为 DAG，首次将“寻找最优顺序”等价为“寻找最优拓扑排序”，并据此开发了搜索算法。关键进展是：对于任意给定的 DAG，如何构造近似 \(\phi\)-最优的设计（乘性算法）与精确高效的设计（模拟退火算法）。原文："The constraints can be represented by a directed acyclic graph (DAG)...the goal of the OofA experiment...equivalent to finding an optimal topological sort of the DAG."

子线索聚类¶

该论文的被引文献大致分布在以下 2-3 条子线索上：

经典 OofA 设计与模型（核心线索）：以 Voelkel (2019)、Van Nostrand (2020)、Peng, Mukerjee & Lin (2019)、Lin & Peng (2019) 为代表。这条线索的簇在：提出并完善了 PWO 模型、推导了在该模型下的各种最优性准则（如 A-最优、D-最优、\(\phi_p\)-最优）的解析解或构造。它们构成了本文方法的“内部”基础。
图约束下的排序与组合优化：本文自身就是这条线索的主要贡献。它引用了 Mlodak, Arnason & Bracewell (1978) 和 Van Der Merwe & van Vuuren (2007) 两个关于相应应用的例子，用于说明 DAG 约束的现实存在性。但没有系统性地引述图论中的拓扑排序或约束满足问题的算法文献。这条线索的簇在：将图约束引入实验设计。
算法与计算：引用了 Meyer & Nachtsheim (1995) 关于乘性算法的经典论文，以及 Kirkpatrick, Gelatt & Vecchi (1983) 的模拟退火算法。这条线索的簇在：提供了搜索算法工具。

这个方向在追问的核心问题 & 瓶颈¶

核心问题：
- Q1 (建模)：如何用简洁、可操作的统计模型刻画顺序的主效应及其与成对约束的交互？PWO 模型是主流，但其“所有成对交互”的假设在维数 \(m\) 较大时非常参数化（\(O(m^2)\)）。
- Q2 (设计)：在给定约束图（DAG）下，如何构造出最“信息丰富”的实验方案？最优设计准则（如 \(\phi\)-optimality）在约束空间下如何变形？解析解是否存在？
- Q3 (推断与决策)：经过实验后，如何利用观测数据 \(d\) 可靠地估计各个顺序的效应，并给出“最优顺序”的统计决策（比如置信集、错误发现率控制）？
已知瓶颈：
- 计算组合爆炸：即使有 DAG 约束，可行排列数（拓扑排序数）在最坏情况下仍可能是指数级的，无法穷举。
- 理论结果稀缺：对于带约束的 OofA 实验，目前几乎没有关于设计最优性的理论保证（例如，得到的近似 \(\phi\)-最优设计是否渐近有效？），论文的理论部分（SA 设计的“极高效率”）仅停留在模拟层面。

⚠️ 作者的 Framing¶

作者的缺口定义：作者将缺口 frame 为“现有 OofA 实验方法假设所有排列可行，但实际存在成对顺序约束”。通过引入 DAG 模型，作者使自己的论文成为“解决现实约束”这一缺口的“显然的下一步”。
被淡化/回避的竞争路线：
- 非 PWO 模型：论文对另一种建模方式——如直接对“全排列”进行拉丁方或随机化设计——完全没有提及。它完全锚定在 PWO 模型这个框架内，默认它是一个足够好的基础。
- 贝叶斯优化：对于最优顺序搜索，贝叶斯优化（Bayesian optimization）尤其是利用高斯过程（GP）代理模型的方法，是处理黑箱昂贵函数的常用技术。本文完全没用，而是用了设计论（乘性算法）和纯搜索（模拟退火）。
- 更紧的理论保证：论文并未讨论当 DAG 非常大或结构复杂时，乘性算法或 SA 的收敛速度、或最优设计的 minimax 性质。
明显该被引/存在却未出现的工作：作者引用了 Mlodak et al. (1978) 作为应用，但没有引用更近期的、在约束满足问题中广泛使用的图算法（如用于 DAG 的 Kahn 算法或深度优先搜索的拓扑排序生成，或用于生成随机拓扑排序的 Wilson's algorithm）。这可能是由于作者认为这些是已知背景知识，但也可能是一个信号：本文的工程实现细节可能不够深入。

张力¶

未见明显对立引用。被引工作之间没有直接矛盾，主要是历史发展上的递进（从无约束到有约束）。

二、最核心、最简单的例子 / 数学问题¶

第一步：把符号、模型、可观测数据交代清楚¶

符号：
- \( \mathcal{A} = \{1, 2, \dots, m\} \): \(m\) 个组件的集合。
- \( \pi \in \Pi \): 一个排列 (order)，是 \(\mathcal{A}\) 中的一个有序序列。\(\Pi\) 是所有排列的集合。
- \( \mathcal{D}_G \subseteq \Pi \): 由有向无环图 \(G\) 约束下的可行排列集合。记作 拓扑排序，即对每条 DAG 边 \(a \to b\)，在排列 \(\pi\) 中 \(a\) 必须在 \(b\) 之前。
- \( Y(\pi) \): 对排列 \(\pi\) 的响应值（随机变量）。
- PWO 模型 (Pairwise Order model):
  \[Y(\pi) = \beta_0 + \sum_{i < j} \beta_{ij} \cdot \text{PWO}_{ij}(\pi) + \varepsilon\]
  其中 \(\text{PWO}_{ij}(\pi) = I\{\text{在排列 } \pi \text{ 中，组件 } i \text{ 先于组件 } j\}\)。\(\beta_{ij}\) 是未知参数，\(\varepsilon\) 是随机误差。
- 设计矩阵 \(X\): 一个 \(n \times (1 + m(m-1)/2)\) 矩阵，其每一行对应一个实验排列 \(\pi\) 的截距项和 PWO 值。更常见的是使用独立效应模型（去除冗余）：由于 \(\text{PWO}_{ij}(\pi) + \text{PWO}_{ji}(\pi) = 1\)，只需保留每对中的一个。模型变为：
  \[Y = \beta_0 + \sum_{i < j} \beta_{ij}^* \cdot \text{PWO}_{ij}(\pi)\]
- \(\phi\)-最优设计：一个设计（一组实验排列的集合）\(\xi\) 的 \(\phi\)-最优性是指它的信息矩阵 \(M(\xi) = \frac{1}{n} X^T X\) 的某个广义准则（例如 D-最优：\(\det(M)\)，A-最优：\(\text{trace}(M^{-1})\)）达到最优。近似 \(\phi\)-最优设计允许设计权重连续，精确设计则从 \(\mathcal{D}_G\) 中选整数次。
- DAG \(G = (V, E)\): 顶点集 \(V = \mathcal{A}\)，边集 \(E\) 是成对顺序约束，如 \(i \to j\) 表示 \(i\) 必须在 \(j\) 之前。
模型：
- 数据生成机制：对于每一个可行的排列 \(\pi \in \mathcal{D}_G\)，我们根据 PWO 模型（或其他更一般的模型）观测其响应 \(Y(\pi)\)。误差 \(\varepsilon\) 通常假设为独立同分布，均值为 0，方差为 \(\sigma^2\)。
- 什么是已知的：DAG 的结构 \(G\)（约束）是已知的。PWO 模型的形式是已知的。误差分布关于 0 对称。
- 什么是待估的：参数向量 \(\boldsymbol{\beta}\)（即 \(\beta_0\) 和所有 \(\beta_{ij}\)）。通过这些参数，可以估计每个可行排列 \(\pi\) 的期望响应 \(\mathbb{E}[Y(\pi)]\)。
可观测数据：
- 实际观测到的：研究者设计并运行了 \(n\) 次实验，每次实验指定一个可行排列 \(\pi_j \in \mathcal{D}_G\)。观测到的是这些排列下的响应值 \(y_j = Y(\pi_j)\) 和排列本身 \(\pi_j\)。
- 想要但观测不到的：首先是所有未被实验的排列的潜在响应（即反事实，counterfactual）。在 PWO 模型下，它被假设通过线性形式与观测数据联系起来。其次是误差 \(\varepsilon\)。最后，对于含有复杂非线性的更一般模型，其响应函数本身也是潜在不可观测的。

第二步：讲最小内核¶

为了直观理解论文的核心，考虑一个最简特例：\(m = 3\) 个组件 \(\{A, B, C\}\)，且 DAG 只有一条有向边：\(A \to C\) （即“A 必须在 C 之前”）。

未约束的排列：\(3! = 6\) 个。
约束下的可行排列：只留下那些 A 在 C 之前的排列：\( (A, B, C), (B, A, C), (A, C, B) \)。注意 \( (B, C, A) \) 和 \( (C, A, B) \) 因为 A 在 C 之后被排除，\( (C, B, A) \) 也被排除。所以 可行排列集合 \(\mathcal{D}_G\) 只有 3 个。

论文的核心思路： 1. 建模（PWO 模型）：我们拟合一个线性模型，但只对可行的 PWO 组合建模。对于 \(m=3\)，有 3 个 PWO 变量：\(\text{PWO}_{AB}, \text{PWO}_{AC}, \text{PWO}_{BC}\)。由于 \(A \to C\) 是约束，\(\text{PWO}_{AC}(\pi) \equiv 1\) 对所有可行 \(\pi\) 都成立。这意味着 这个变量是冗余的（在所有可行排列中都等于 1），需要从模型中移除。实际上，PWO 模型简化了。 2. \(\phi\)-最优设计：目标是找到一组可行排列（来自那 3 个），使得实验能最好地估计简化后的 PWO 模型参数（比如 D-最优，即最大化信息矩阵的行列式）。由于只有 3 个候选，我们可以穷举搜索或手动计算：例如，做 2 次（或者 1 次，如果只做 1 次实验信息量不够就不合理）实验，如何选择？直观上，选择两个“尽可能不同”的排列，如 \( (A,B,C) \) 和 \( (B,A,C) \)，它们只在 \(\text{PWO}_{AB}\) 上不同，能最好地估计该参数。 3. 从设计到搜索：当 \(m\) 很大时（如 \(m=10\)），可行排列仍可能成千上万，无法穷举。论文的贡献是提出了两种算法： - 乘性算法 (Multiplicative Algorithm)：在“连续设计”（允许概率权重）的空间上优化一个目标函数（如 \(\phi\)-最优性），适用于任意 DAG。 - 模拟退火 (Simulated Annealing, SA)：在离散的、图约束的排列空间上搜索。它通过尝试“交换”两个组件的顺序，来探索不同的拓扑排序，目标是找到一组高效的排列。SA 的特别之处在于它随机跳出局部最优。

最小内核：论文的全部技术工作——PWO 模型在 DAG 下的简化、\(\phi\)-最优准则的定义、乘性算法和 SA 的应用——本质上是将一个 \(m!\) 的穷举问题 转化为一个 \(|\mathcal{D}_G|\) 的搜索问题，其中 \(\mathcal{D}_G\) 由 DAG 定义的拓扑排序集合给出。其中最关键的部分是：如何在图约束下，高效地生成并评估候选设计（拓扑排序集合）。论文的核心数学困难在于：构造一个能有效搜索约束排列空间的算法，并获得计算上的可处理性。

三、这篇论文做了什么¶

三句话：
1. 研究问题：当 Order-of-Addition (OofA) 实验中存在成对顺序约束（由 DAG 表示）时，如何系统地识别最优（近似最优或精确最优）的实验设计（排列集合）。
2. 核心方法：将最优排序问题等价于 DAG 的 最优拓扑排序 问题；提出 乘性算法 寻找近似 \(\phi\)-最优设计；提出 模拟退火 (SA) 算法寻找高效精确设计并给出效率证明。
3. 主要结论：对于任意 DAG，乘性算法能快速找到近似最优设计，模拟退火算法能构造出相对于该近似设计具有“极高效率”（>99%）的精确设计。
关键设定与假设：
- 假设 1 (PWO 模型)：响应 \(Y\) 与排列 \(\pi\) 的关系可用 PWO 模型（包含所有或部分交互效应）线性描述。这是论文的最强假设，也是整个理论的地基。如果真实关系是非线性的，论文的所有设计理论都将失效。
- 设定 2 (DAG 约束)：约束是成对的（\(i\) 必须在 \(j\) 之前），并且可传递（如果 \(i \to j\) 且 \(j \to k\)，则 \(i\) 必须在 \(k\) 之前）。这使得约束图天然是一个 DAG。
- 设定 3 (\(\phi\)-最优性)：使用最优设计准则 \(\phi\)，通常是 D-最优（最大化信息矩阵的行列式）。论文强调乘性算法和 SA 都适用于一般的 \(\phi\) 准则。
- 设定 4 (独立误差)：观测间独立，且 \(\varepsilon \sim N(0, \sigma^2)\) 或至少是球对称分布。这对 D-最优的经典理论是标准假设。
主要结果：
- 结果 1 (问题等价性)：定理 1 将“在约束下寻找最优顺序”严格等价为“寻找给定 DAG \(G\) 的最优拓扑排序”。这提供了严格的数学转化，是后续一切的基础。
- 结果 2 (乘性算法)：算法 1 是一个迭代更新设计权重的算法。它从一个初始等权重设计开始，每次迭代更新权重以提升 \(\phi\)-最优性。定理 2 证明了该算法的收敛性——设计矩阵 \(M(\xi^{(k)})\) 收敛到局部最优（没说是全局最优，对凸问题才是全局）。该算法的主要价值在于快速给出一个近似最优设计的下界。
- 结果 3 (SA 算法与效率)：算法 2 是一个模拟退火算法。它从一个伪随机拓扑排序开始，并探索交换两个顶点（组件）的顺序（只要不违反 DAG 约束）。定理 3 是核心定性结论：经过 SA 获得的精确设计的效率（相对于近似\(\phi\)-最优设计的 D-最优值）趋于 1。论文通过模拟验证对 \(m=10, 15\) 的 DAG，SA 设计的效率通常 >99%。
- 结果 4 (通用程序)：Section 7 提供了一个通用的三步流程：(i) 根据 DAG 确定可行排列集合 \(\mathcal{D}_G\)；(ii) 使用 PWO 模型（或其他模型）进行最优设计；(iii) 实验后使用模型分析数据并选择最优顺序。这实际上是一个操作化的范式。
证明路线与技术技巧：
- 整体路线（针对 SA 效率定理）：
  1. 建立下界：将精确设计（SA 输出）的 D-最优值 \(|\hat{M}|\) 与近似最优设计的 D-最优值 \(|\tilde{M}^*|\) 比较。
  2. 最优性引理：利用最优设计理论的一个标准性质：对于给定的近似最优设计 \(\tilde{\xi}^*\)，精确设计 \(\hat{\xi}\) 的效率与 \(\tilde{\xi}^*\) 的某种“奇异性”有关。
  3. 核心引理：乘性算法的收敛性保证了构造的 \(\tilde{\xi}^*\) 是“非常好”的（足够接近全局最优）。
  4. SA 的构造：证明 SA 算法产生的设计 \(\hat{\xi}\) 能使 \(|\hat{M}| / |\tilde{M}^*| \to 1\) 当 \(m\) 或迭代次数增大时。关键技巧是 SA 的 Metropolis-Hastings-like 接受规则保证能跳出局部最优解，最终收敛到全局最优解。
- 关键跳跃点：
  - 最难的部分：将乘性算法的理论（针对无约束的连续设计）推广到有 DAG 约束的离散设计空间。在无约束情况下，可行设计是凸集，D-最优解是唯一的；在有约束下，可行设计集不再是凸的，且拓扑排序集的结构复杂。证明收敛性需要处理这个非凸性。
  - SA 的收敛性证明：SA 的收敛性通常依赖于正回归性和不可约性（即算法能访问所有可行状态）。作者通过构造一种特定的扰动（swap）及其逆操作，证明了在 DAG 约束下，从任意拓扑排序出发，通过一系列合法的 swap 可以到达任何其他拓扑排序，从而保证了不可约性。这是证明 SA 概率收敛的核心。
- 技术技巧点名：
  - Monte Carlo 模拟 + 乘性权重更新：用于近似 \(\phi\)-最优设计。
  - 模拟退火 (SA)：经典的组合优化技巧，用于搜索离散空间。
  - D-最优设计：经典的实验设计理论，提供了目标函数和效率评价标准。
  - 图论中的拓扑排序：核心数学结构。
真实例子与应用：
- 数据/场景：一个顺序作业调度问题：\(m = 5\) 个作业 (Jobs 1-5) 需要在一台机器上处理，目标是找到使总最小化（实际是使一个类似贪心调度的总代价最小）。该问题天然具有顺序约束（例如，Job 1 必须在 Job 2 之前）。这个场景被抽象为一个 DAG。
- 方法应用：作者首先枚举所有 \(5! = 120\) 个排列，并用一个已知的调度算法（不是 PWO 模型！）计算每个排列的响应（总代价）。这是一个带有已知响应函数的 OofA 问题。作者使用了他们提出的方法：假设 PWO 模型，并使用乘性算法和 SA 找到最优设计（几个实验排列）。然后，他们使用这些设计中的排列，直接运行调度算法并选择最优。实际上，这个方法在调度问题中，最优设计直接给出了最优解，因为响应是确定性的且是已知的。
- 结果：实证表明，用 SA 找到的几个最优设计，其对应的排列（作业顺序）与穷举搜索得到的真正最优排列一致。这个例子想说明：（i）方法在现实约束下有效；（ii）它可以用比穷举少得多的试验次数（设计点）找到最优解。关键警示：这个例子中，模型和响应函数是已知的，因此设计可以直接用于搜索。在真实 OofA 实验中，响应是随机的，需要先通过实验估计模型，才能用模型预测最优顺序。这个应用是一个对方法搜索能力而非模型预测能力的验证。

🔎 结论是否比证明窄¶

结论比证明窄：定理 3 的结论“SA 设计相对于近似 \(\phi\)-最优设计具有极高效率”是严格在模拟中验证的，不是形式化证明。其证明部分（Theorem 2）只证明了乘性算法的收敛性，并没有证明 SA 算法本身的收敛到全局最优的数学定理。在论文中，SA 的性能只由模拟结果支持。作者在 conclusion 中提到“the SA algorithm can yield very efficient designs”时，并没有声称这是普遍成立的理论。
显著 claim 不符合证明：论文中多处使用“efficient”来修饰 SA 设计，但在统计语境下，“efficient”通常指统计效率（渐近方差达到 Cramér-Rao 界），在这里却是指设计效率（D-最优值与最优值的比值）。作者没有混淆这两个概念，但不熟悉此术语的读者可能会误读。
窄的结论：文中的理论核心（定理 1, 2）是坚实的，但它们都锚定在 PWO 线性模型 和 \(\phi\)-最优性 上。对于更一般的非线性模型或其他最优性准则（如估测最优排列而非模型参数的 A-最优），该理论框架不直接适用。

四、开放问题¶

非线性模型下的推广：本论文的所有结果都建立在 PWO 线性模型之上。当真实响应与顺序的关系是非线性的（例如，存在高阶交互作用或非参数效应）时，本文的设计理论（D-最优设计）会得到什么样的设计？它们是否仍然“高效”？这直接扎根于论文的假设 1。作者在 future work 中未提及非参数化推广。
统计推断与假设检验：论文专注于设计与搜索，但没有提供关于估计量 \(\hat{\boldsymbol{\beta}}\) 的方差估计或最优顺序的统计推断。例如，在找到最优设计并实验后，如何构造关于 \(\mathbb{E}[Y(\pi_{best})]\) 的置信区间？或者如何检验某个排列是否显著优于另一个？这扎根于论文的“通用程序”中第二步“模型分析”的缺失（作者只提到“fitting the model”）。
算法的计算复杂度：乘性算法和 SA 在图结构非常复杂（如 DAG 的树宽很大）或 m 非常大（如 m=100）时的计算瓶颈。乘性算法涉及矩阵求逆，SDP 或二次规划，其复杂度随 m 增长。SA 的每次 swap 都需要检查 DAG 的合法性，其计算成本可能与图大小相关。这与 researcher 在 higher-order U-statistics 中的 treewidth/tensor contraction 复杂度有直接的结构共鸣。这是一个未被论文打开的问题。
最优设计的 minimax 性质：论文使用 \(\phi\)-最优性（如 D-最优），其依赖于模型假设（PWO）。如果模型有误，这个最优设计可能很差。一个更有趣的问题是：是否存在一个对所有可能的模型（或所有可行排列）都具有良好 minimax 风险的“稳健”设计？这涉及模型误设与决策理论，是论文没有触及的统计前沿。

Maintained by 陈星宇 · Homepage · Source on GitHub