跳转至

Space-filling foldover designs for order-of-addition experiments under Kendall tau distance criteria

讲者: Hui Shao
会场: Experimental Design and Educational Measurement and Psychometrics
报告题目: Space-Filling Order-of-Addition Designs Based on the Kendall-Tau Distance
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述

这个方向是什么

这个子方向是顺序添加实验（Order-of-Addition, OofA）的统计设计。其根本的科学问题是：当一个系统的响应依赖于一组组件被添加的顺序时，如何从所有可能的 \(m!\) 个排列中，选择一个小的、信息量大的子集（即一个“部分设计”）来进行实验，从而能够高效地建模、预测或找到最优顺序。当前成熟度：这是一个相对年轻但快速发展的领域，核心挑战在于设计空间（排列空间）的离散、巨大且缺乏天然欧几里得结构。已有工作主要围绕两类模型（成对排序模型和组件位置模型）和两类设计方法（代数构造和算法搜索）展开。

发展脉络（history）

  1. 奠基工作与核心模型：

    • Van Nostrand (1995)：提出了成对排序（PWO）模型，将每个排列表示为一个 \( \binom{m}{2} \) 维的向量，每个分量指示一对组件的相对顺序。这为OofA实验的统计建模奠定了基础。
    • Voelkel (2017)：系统性地引入了OofA实验的设计问题，提出了OofA正交阵列（OofA-OA） 的概念，并建立了其与D-最优性的联系。这是设计领域的开创性工作。
    • Yang, Sun, Xu (2020)：提出了组件位置（CP）模型，从组件占据的位置角度建模，并引入了组件正交阵列（COA）。该文指出COA在CP模型下具有与全设计相同的D-效率，并在PWO模型下也表现良好。

  2. 主要进展：设计准则与构造方法：

    • Peng, Mukerjee, Lin (2019)：在PWO模型下，证明了全设计的信息矩阵是最优的，并给出了其谱分解。这为衡量部分设计的效率提供了基准。本文引用其结论来推导Corollary 1。
    • Zhao, Lin, Liu (2021)：对PWO设计进行了深入研究，推导了全PWO设计的D-效率，并提出了最小点PWO设计。
    • Mee (2020)：研究了PWO模型的交互效应，并提出了衡量PWO设计对模型误设稳健性的方法。
    • Stokes, Wong, Xu (2023)：将元启发式算法（差分进化DE和粒子群优化PSO） 引入OofA设计搜索，用于优化模型基准则（如D-最优性）和空间填充准则（基于位置距离）。这代表了算法搜索路线的进展。
    • Huang and Yang (2025)：提出了最大最小距离组件正交阵列（MCOA），旨在同时保证COA的平衡性和空间填充性（基于位置距离），以提高设计的稳健性。

  3. 当前前沿与本文位置：

    • Tsai (2025)：通过中心化广义字长模式（CGWP） 来刻画和比较OofA-OA，为比较部分设计提供了新的视角。本文将其与Kendall tau距离矩联系起来。
    • Jiao and Vert (2015) & Deshwal et al. (2022)：将Mallows核（基于Kendall tau距离的正定核）用于排列空间上的高斯过程（GP）建模和贝叶斯优化。这为OofA设计提供了基于GP模型的动机。
    • 本文（Shao et al., 2026）：定位在“模型无关”的空间填充设计路线上。它指出，已有的空间填充准则多基于位置距离（Hamming, \(L_1, L_2\)），这些距离与PWO模型的对齐性不强。因此，本文提出直接使用与PWO编码天然对齐的Kendall tau距离来定义空间填充准则，并为此开发了一种高效的折叠模拟退火算法（FSA-KD）。

子线索聚类

  1. 模型与准则：关注如何对OofA实验建模以及定义“好”的设计。代表工作：PWO模型（Van Nostrand, 1995; Peng et al., 2019; Mee, 2020; Wang and Lin, 2023），CP模型（Yang et al., 2021; Stokes and Xu, 2022），GP模型（Jiao and Vert, 2015; Deshwal et al., 2022），以及基于信息矩阵的准则（D-, A-, MS-最优性）和基于字长模式的准则（Tsai, 2025）。
  2. 代数构造：通过组合结构直接构造具有特定性质的设计。代表工作：OofA-OA（Voelkel, 2017; Zhao et al., 2021; Schoen and Mee, 2023），COA（Yang et al., 2021），MCOA（Huang and Yang, 2025）。这些方法通常对运行次数 \(n\) 和组件数 \(m\) 有严格限制。
  3. 算法搜索：使用计算优化算法在排列空间中搜索最优设计。代表工作：元启发式算法（Stokes et al., 2023），以及本文的FSA-KD。这类方法更灵活，能处理各种 \(n\) 和 \(m\)。

这个方向在追问的核心问题

  1. 如何定义“好”的设计？ 是模型依赖的（如D-最优性）还是模型无关的（如空间填充性）？不同定义下的设计有何关系？
  2. 如何高效构造设计？ 代数构造有理论保证但限制多，算法搜索灵活但计算成本高。如何平衡二者？
  3. 如何保证设计的稳健性？ 当真实模型未知或与假设模型不同时，一个设计是否仍然有效？（如Mee, 2020; Huang and Yang, 2025的工作）
  4. 如何将设计准则与下游任务（预测、优化）联系起来？ 一个好的设计是否必然带来更好的预测或更快的优化收敛？

⚠️ 作者的 framing

  • 作者把缺口 frame 成什么？ 作者认为，已有的空间填充OofA设计（如Stokes et al., 2023; Huang and Yang, 2025）主要基于位置距离（Hamming, \(L_1, L_2\)），这些距离“do not directly measure discrepancies in pairwise precedence”，因此与PWO模型的对齐性不强。作者将缺口定位为：缺乏一个与PWO模型天然对齐的、基于Kendall tau距离的空间填充准则，以及一个能高效构造此类设计的算法。本文因此成为“显然的下一步”。
  • 哪些竞争路线被他淡化或回避了？ 作者淡化了模型基准则（如D-最优性）的路线。虽然Theorem 1和Proposition 1建立了Kendall tau距离矩与MS-最优性及CGWP的联系，但本文的核心贡献是提出并优化一个模型无关的准则。作者回避了与代数构造路线的直接竞争，指出代数构造（OofA-OA, COA）对 \(n\) 和 \(m\) 限制严格，而本文的算法方法更灵活。
  • 什么明显该被引 / 该存在、却没出现在 intro 里？ 从提供的材料看，intro引用了该领域几乎所有关键工作。一个值得研究者去查的问题是：是否有其他工作也尝试过使用Kendall tau距离来设计OofA实验？ 如果存在，作者是如何与之区分的？如果没有，这本身就是一个信号。

张力

未见明显对立引用。不同工作（如PWO vs CP模型，代数 vs 算法构造）更多是互补关系，而非矛盾。一个潜在的张力在于：模型基最优性（如D-最优性）与空间填充性（如最大最小距离）在OofA设计中是否总是一致？ 本文的Theorem 1表明，在PWO模型下，MS-最优性等价于Kendall tau距离矩的特定组合，这暗示了在PWO模型下二者是统一的。但在其他模型下，这种关系可能不成立，这正是Huang and Yang (2025) 提出MCOA的动机。

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

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

  • 符号：

    • \(m\)：组件个数。
    • \(\mathcal{Z}_m = \{0, 1, \dots, m-1\}\)：组件集合。
    • \(\mathcal{S}_m\)：所有 \(m!\) 个排列的集合。
    • \(n\)：设计中的运行次数（即选择的排列个数）。
    • \(D = \{x_1, \dots, x_n\}\)：一个 \(n \times m\) 的OofA设计矩阵，其中 \(x_i = (x_{i1}, \dots, x_{im}) \in \mathcal{S}_m\) 是第 \(i\) 次运行的排列。
    • \(\pi_{x_i}(c)\)：组件 \(c\) 在排列 \(x_i\) 中的位置（从1到m）。
    • \(k(x_i, x_j)\)：两个排列 \(x_i\) 和 \(x_j\) 之间的Kendall tau距离，即它们之间顺序相反的组件对的数量。取值范围是 \(0\) 到 \(\binom{m}{2}\)。
    • \(q = \binom{m}{2}\)：最大Kendall tau距离。
    • \(z_{ab}(x)\)：PWO编码，若组件 \(a\) 在排列 \(x\) 中先于 \(b\)，则 \(z_{ab}(x) = +1\)，否则为 \(-1\)。
    • \(z(x) = (z_{ab}(x) : 0 \le a < b \le m-1)^\top\)：一个 \(q\) 维的PWO向量。
    • \(k_{\min}(D), k_{\text{ave}}(D), k_{m^2}(D)\)：设计 \(D\) 中所有运行对之间Kendall tau距离的最小值、平均值和二阶矩。
    • \(\tilde{x}\)：排列 \(x\) 的折叠（foldover），即其逆序排列。

  • 模型：

    • PWO模型：\(y(x) = \beta_0 + \sum_{0\le a < b \le m-1} \beta_{ab} z_{ab}(x) + \varepsilon\)。响应 \(y\) 被建模为所有组件对之间相对顺序的线性函数。
    • GP模型：\(Y(x) = \mu + Z(x)\)，其中 \(Z(x)\) 是零均值高斯过程，协方差函数为Mallows核：\(\text{Cov}\{Z(x_i), Z(x_j)\} = \sigma^2 \exp\{-\theta \cdot k(x_i, x_j)\}\)。相关性随Kendall tau距离增加而指数衰减。

  • 可观测数据：

    • 可观测：研究者可以观测到 \(n\) 个排列 \(x_1, \dots, x_n\)（即设计 \(D\)），以及在这些排列下实验得到的响应值 \(y(x_1), \dots, y(x_n)\)。
    • 想要但观测不到：所有 \(m!\) 个排列的响应值。研究者只能通过部分设计 \(D\) 来推断整个排列空间 \(\mathcal{S}_m\) 上的响应面，或找到最优排列。在PWO模型下，不可观测的是回归系数 \(\beta_{ab}\)；在GP模型下，不可观测的是GP的超参数 \(\mu, \sigma^2, \theta\) 以及未观测点的响应。

第二步：讲最小内核

本文的核心思路是：用Kendall tau距离来量化排列之间的“分离程度”，并构造一个在该距离下“分离得好”的设计。其最小内核可以浓缩为以下问题：

最简特例：考虑 \(m=4\) 个组件，我们想构造一个 \(n=4\) 次运行的设计。全设计有 \(4! = 24\) 个排列。

  • 核心想法：我们不关心排列的具体位置，只关心每对排列之间有多少对组件的相对顺序是相反的（即Kendall tau距离）。一个好的空间填充设计，应该让这4个排列两两之间的Kendall tau距离都尽可能大，且分布均匀。
  • 例子：论文中的Example 1给出了两个 \(4\times 4\) 的设计 \(D_1\) 和 \(D_2\)。它们都是平衡设计（每个组件在每个位置出现次数相同），但它们的Kendall tau距离分布不同：
    • \(D_1\) 的6个距离为：3, 4, 3, 3, 4, 3。\(k_{\min}=3, k_{\text{ave}}=10/3, k_{m^2}=34/3\)。
    • \(D_2\) 的6个距离为：3, 3, 6, 6, 3, 3。\(k_{\min}=3, k_{\text{ave}}=4, k_{m^2}=18\)。
  • 解读：
    • \(k_{\min}\) 相同（都是3），说明两个设计在最坏情况下的分离程度一样。
    • \(k_{\text{ave}}\) 不同（\(D_2\) 更大），说明 \(D_2\) 的排列在“平均意义”上分离得更开。
    • \(k_{m^2}\) 不同（\(D_1\) 更小），说明 \(D_1\) 的距离分布更集中，波动更小。
  • 本文的贡献：本文提出，一个好的设计应该同时优化这三个指标。对于 \(n\) 为偶数的情况，本文进一步提出使用折叠结构（即设计由一半的排列和它们的逆序组成）。这个结构有一个关键性质（Theorem 3(ii)）：任何无重复运行的折叠设计的平均Kendall tau距离 \(k_{\text{ave}}\) 是固定的，等于全设计基准值 \(nm(m-1)/[4(n-1)]\)。这使得搜索问题简化为：在固定 \(k_{\text{ave}}\) 的前提下，最大化 \(k_{\min}\) 并最小化 \(k_{m^2}\)。

因此，本文在数学上干了一件什么事？在排列空间 \(\mathcal{S}_m\) 上，寻找一个大小为 \(n\) 的子集 \(D\)，使得其元素间的Kendall tau距离分布具有最大的最小值和最小的二阶矩（在平均值固定的约束下），并为此开发了一个高效的搜索算法。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：研究了基于Kendall tau距离的空间填充顺序添加（OofA）实验设计问题，提出了最小距离、平均距离和二阶矩三个准则。
  2. 核心工具 / 方法：提出了一个基于折叠结构的模拟退火算法（FSA-KD），该算法利用折叠恒等式和局部交换实现距离的增量更新，从而高效搜索。
  3. 主要结论：理论证明了这些距离准则与PWO模型下的MS-最优性、Tsai (2025)的中心化字长模式以及Mallows核GP模型下的渐近D-最优性之间的联系。数值实验表明，FSA-KD构造的设计在Kendall tau空间填充性、稀疏PWO模型预测、Mallows核GP预测和贝叶斯优化任务中均优于随机采样和基于位置距离的元启发式基线。

关键设定与假设

  • 设定：\(m\) 个组件，\(n\) 次运行（\(n\) 为偶数时主要研究，奇数时通过删除步骤扩展）。设计 \(D\) 是一个 \(n \times m\) 的矩阵，每行是一个排列。
  • 假设：
    • 无重复运行：设计 \(D\) 中所有排列互不相同。这是空间填充设计的基本要求。
    • PWO模型假设（用于Theorem 1）：响应 \(y\) 与PWO向量 \(z(x)\) 是线性关系，误差独立同分布，均值为0，方差为 \(\sigma^2\)。
    • GP模型假设（用于Theorem 2）：响应 \(Y(x)\) 服从一个具有Mallows核的平稳高斯过程。该假设是Theorem 2成立的基础。
    • 折叠结构假设（用于Section 4）：设计由一半的排列 \(H\) 和它们的逆序 \(\tilde{H}\) 组成，即 \(D = H \cup \tilde{H}\)。这是FSA-KD算法的核心结构约束。
  • 相比已有文献的放宽或强化：
    • 放宽：相比代数构造（OofA-OA, COA），FSA-KD对 \(n\) 和 \(m\) 的限制更少，能处理更灵活的设计规模。
    • 强化：相比已有的基于位置距离（\(L_2\)）的空间填充设计（如Stokes et al., 2023），本文提出的准则直接针对Kendall tau距离，与PWO模型的对齐性更强。

主要结果

  • Theorem 1 (PWO模型下的MS-最优性)：在PWO模型下，MS-最优性准则 \(\text{tr}(M^2)\) 可以表示为 \(k_{\text{ave}}(D)\) 和 \(k_{m^2}(D)\) 的线性组合。这意味着，最大化 \(k_{\text{ave}}\) 和最小化 \(k_{m^2}\) 等价于最小化 \(\text{tr}(M^2)\)，从而为距离准则提供了模型基的统计解释。
  • Theorem 2 (GP模型下的渐近D-最优性)：在Mallows核GP模型下，当核的衰减速率 \(\theta \to \infty\) 时，最大最小Kendall tau距离设计（即最大化 \(k_{\min}\) 的设计）是渐近D-最优的。这为最大化 \(k_{\min}\) 准则提供了基于GP模型的动机。必要条件：设计无重复运行，且在所有达到最大 \(k_{\min}\) 的设计中，达到该最小距离的配对数量最少。
  • Theorem 3 (折叠设计的距离性质)：对于一个 \(n=2h\) 的无重复运行折叠设计 \(D = H \cup \tilde{H}\)：
    1. 所有距离可由 \(H\) 的距离矩阵决定。
    2. \(k_{\text{ave}}(D)\) 是固定的，等于 \(nm(m-1)/[4(n-1)]\)。这是FSA-KD算法能简化搜索的关键。
    3. \(k_{\min}(D)\) 的上界是 \(\lfloor m(m-1)/4 \rfloor\)。
    4. \(k_{m^2}(D)\) 有明确的上下界。

证明路线与技术技巧

  • 整体路线：
    1. 建立联系：首先，通过代数推导（Proof of Theorem 1），将PWO模型下的MS-最优性准则 \(\text{tr}(M^2)\) 展开，并利用 \(z(x_i)^\top z(x_j) = q - 2k(x_i, x_j)\) 这一关键恒等式，将其转化为 \(k_{\text{ave}}\) 和 \(k_{m^2}\) 的函数。
    2. 渐近论证：对于GP模型（Proof of Theorem 2），利用 \(\theta \to \infty\) 时，相关矩阵 \(\Sigma_D(\theta)\) 趋近于单位矩阵。通过行列式的展开式 \(\det(I + E) = 1 - \frac{1}{2}\text{tr}(E^2) + O(\|E\|^3)\)，证明主导项由最小距离 \(k_{\min}\) 及其频数决定，从而得出最大最小距离设计的渐近最优性。
    3. 折叠结构分析：通过分析折叠变换 \(\tilde{x}\) 的性质（\(z(\tilde{x}) = -z(x)\)），推导出折叠设计中所有距离与代表半设计 \(H\) 中距离的关系（Theorem 3(i)），进而计算出固定的 \(k_{\text{ave}}\) 和 \(k_{m^2}\) 的上下界。
  • 关键跳跃点：最吃功夫的引理是Theorem 1的证明，它成功地将一个看似复杂的模型基准则（\(\text{tr}(M^2)\)）与一个简洁的几何量（Kendall tau距离的矩）联系起来。这个跳跃依赖于对PWO向量内积 \(z(x_i)^\top z(x_j)\) 与Kendall tau距离 \(k(x_i, x_j)\) 之间关系的深刻理解。
  • 技术技巧点名：
    • 代数恒等式：\(z(x_i)^\top z(x_j) = q - 2k(x_i, x_j)\)。这是连接PWO模型和Kendall tau距离的桥梁，在Theorem 1和Proposition 1的证明中反复使用。
    • 行列式展开：用于Theorem 2的证明，将 \(\det(\Sigma_D(\theta))\) 在 \(\theta \to \infty\) 时展开，从而将问题简化为比较最小距离项。
    • 折叠恒等式：\(k(\tilde{x}_i, \tilde{x}_j) = k(x_i, x_j)\) 和 \(k(x_i, \tilde{x}_j) = q - k(x_i, x_j)\)。这是FSA-KD算法能实现计算加速的理论基础。
    • 增量更新：在FSA-KD算法中，通过只更新被修改的排列与其他排列的距离，将每次迭代的计算复杂度从 \(O(n^2 m^2)\) 降低到 \(O(h m^2)\)（全局替换）或 \(O(h m)\)（局部交换）。局部交换的更新利用了PWO符号的变化规律。

真实例子与应用

本文包含模拟实验和真实数据驱动的应用，但没有使用真实世界的实验数据。其“应用”部分是通过模拟来验证方法在统计任务中的有效性。

  • 用的什么数据 / 场景：
    1. 稀疏PWO模型预测：模拟生成一个只有10个活跃效应的PWO模型（\(m=10\)），并添加噪声。任务是用部分设计拟合弹性网络，预测2000个测试排列的响应。
    2. Mallows核GP预测：使用一个非线性的作业调度（job scheduling） 目标函数（公式见论文Section 5.3）。任务是用部分设计拟合Mallows核GP，预测500个测试排列的响应。
    3. 贝叶斯优化：在同一个作业调度目标函数上，用部分设计作为初始样本，然后进行期望改进（EI）步骤的贝叶斯优化，寻找最优排列。
  • 怎么把本文方法用上去：用FSA-KD算法构造设计 \(D\)，然后在这些设计上运行上述统计模型。对比基线包括随机采样（SRS）和基于位置距离的元启发式设计（Maximin-\(L_2\), Maximin-Hamming）。
  • 得到什么结果：
    • 稀疏PWO预测（Table 2）：对于 \(n=20, 30\)，FSA-KD设计的预测误差（nRMSE）最小。
    • GP预测（Table 3）：对于 \(m=5, 10\) 和 \(n=2m, 4m\)，FSA-KD设计的预测误差最小。
    • 贝叶斯优化（Figure 3）：FSA-KD设计提供了更好的初始点，使得优化曲线更快地收敛到更优的值，尤其在优化早期优势明显。
  • 这个例子想说明什么：这些例子旨在验证本文的核心论点：基于Kendall tau距离的空间填充设计，不仅在几何上“好看”，而且在PWO模型和GP模型下的预测和优化任务中“好用”。它们证明了距离准则的统计相关性。

🔎 结论是否比证明窄

  • Theorem 2 的结论是“渐近D-最优”（asymptotically D-optimal as \(\theta \to \infty\)）。论文在Remark 1中明确指出，对于有限 \(\theta\)，该结论不严格成立，需要更高阶的项来区分。因此，论文的结论（渐近最优）比证明（仅对 \(\theta \to \infty\) 严格）窄。论文在正文中也谨慎地将其描述为“asymptotic motivation rather than a finite-\(\theta\) characterization”。
  • 论文在Section 6的“Concluding remarks”中提到了算法的计算挑战和可能的扩展，这些是诚实的自我评估，没有过度泛化。

四、开放问题

  1. 更高效的搜索策略：论文提到“The FSA-KD algorithm may still face computational challenges because the permutation space still grows rapidly with the number of components”。一个开放问题是：能否设计出比模拟退火更快的搜索策略，例如利用问题结构的并行算法或混合算法，来处理更大的 \(m\)（如 \(m > 20\)）？（扎根于Section 6第一段）
  2. 代数构造：论文指出“It would also be useful to develop algebraic constructions with good Kendall tau distance properties”。一个开放问题是：能否找到一种类似于OofA-OA或COA的代数构造，直接生成在Kendall tau距离下最优或接近最优的设计，从而避免算法搜索？（扎根于Section 6第二段）
  3. 扩展到更一般的顺序结构：论文提到“extensions to more general order-structured experiments, including settings with partial orders or additional constraints”。一个开放问题是：当组件之间存在偏序约束（如某些组件必须排在另一些之前）时，如何定义和构造基于Kendall tau距离的空间填充设计？（扎根于Section 6第二段）
  4. 与自适应采样的结合：论文提到“sequential designs that combine an initial FSA-KD design with adaptive sampling or Bayesian optimization”。一个开放问题是：如何将FSA-KD构造的初始设计与后续的自适应采样策略（如贝叶斯优化）最优地结合起来，以最小化找到全局最优解所需的总实验次数？（扎根于Section 6第二段）

Maintained by 陈星宇 · Homepage · Source on GitHub

评论