分区分数不是系统分数：分解算法选择中的部署保真度差距

# 分区评分非系统评分：分解算法选择中的部署保真度差距
来源：https://arxiv.org/html/2609.13785  
Jiachen Zhang††thanks:通讯作者:[email protected]  
Yu Tang  
单位：华中科技大学  
Li Zhu  
单位：香港城市大学

###### 摘要  
预言机风格的量，包括虚拟最佳求解器、选择性投资组合虚拟最佳求解器、虚拟最佳编码以及家族内最佳摘要，被广泛报告为可部署选择器可能达到的性能上界。在分解算法选择中，类似的分区级评分赋予预言机在所选家族内选择最佳算法的能力；一旦家族选择器被固定，可部署系统必须用学习到的家族内选择器替换该预言机。我们将*部署保真度差距* \(G(R)\) 定义为分区级效用与可部署端到端效用之差，并推导出两个核算推论：一个逐实例间隔-遗憾稳定性条件，用于判断分区时选择的家族何时是部署最优的；以及一个严格的纯分区识别区间，当该区间严格跨零时，阻止分区报告证明部署的赢家。在涵盖表格AutoML和组合CSP/SAT的五个公开算法选择基准测试中，所有分解流程的 \(G(R)\) 均为正值，范围从TabZilla上的0.012到PROTEUS-2014上的0.13。十个分解与扁平选择决策中有四个的点估计符号发生变化；在PROTEUS-2014上，33点的分区优势缩减为20点的端到端优势。一种训练侧的差距校正诊断方法在所有四个符号变化的单元格中恢复了点估计的可部署符号；这是一种报告辅助手段，而非直接端到端评估的替代品。分区和端到端评分应并行报告。

## 1 引言
算法选择（AS）系统越来越多地使用分解决策：它们并非直接从大型投资组合中选择，而是首先选择一个算法家族，然后在其中选择一个具体的算法（Kerschke 等，2019；Bischl 等，2016）。分解降低了多类别问题的难度，并展现出可解释的结构，但其评估可能与部署不同。常见的分区级评估会询问所选家族是否包含一个强算法，然后授予该家族的最佳成员。这为分区提供了上界，但它并非一个端到端的系统：部署必须使用学习到的家族内选择器。我们称这种差异为*部署保真度差距*：

\[ G(R) = S_{\text{part}}(R) - S_{\text{e2e}}(R), \tag{1} \]

其中 \(S_{\text{part}}\) 使用家族内预言机，而 \(S_{\text{e2e}}\) 使用可部署的选择器。\(G(R)\) 是当预言机被可用的家族内选择器替代时损失的效用。在涵盖表格AutoML（McElfresh 等，2023；Salinas 和 Erickson，2024；Ye 等，2024）和组合搜索（Bischl 等，2016；Hurley 等，2014）的五个公开AS基准测试（B1: TabZilla, B2: TabRepo, B3: TALENT, B4: MAXSAT-PMS-2016, B5: PROTEUS-2014）中，所有分解流程都显示出正的部署保真度差距，从TabZilla上的1.2点到PROTEUS-2014上的13点。这一差距改变了结论：在TabRepo和MAXSAT-PMS-2016上，分区级评估倾向于分解而非扁平选择，但端到端点估计符号发生变化，其中B2有一个单元格，B4的两个单元格端到端边际很小；在TabZilla上，优势几乎被吸收，但端到端仍为正；在PROTEUS-2014上，33点的分区优势缩减为20点的端到端优势（\(\rho \approx 0.41\)）。总体而言，安全性条件在4/10的分解与扁平部署决策中失败，而所有5个成对与多类别外层选择器的比较信号都较弱。因此，主要风险在于是否包含了家族内部署步骤，而非使用了哪个外层选择器。先前的工作使用预言机基线，如虚拟最佳求解器（VBS）作为上界（Xu 等，2008；Bischl 等，2016；Cameron 等，2016），而近期的工作研究了由划分和尺度缩放引起的基准测试陷阱（Petelin 和 Cenikj，2025）。我们研究的是一种不同的、*嵌套*预言机：在家族选择器已经行动之后引入的家族内预言机。新颖之处不在于预言机评分是乐观的，而在于一个常见的分解评分可以用预言机替换一个可部署阶段，并通过 \(G(R_1) - G(R_2)\) 改变比较结果。

##### 贡献。
1. **形式化**。我们定义了 \(G(R)\) 并将分区评分识别为预言机辅助的上界而非系统评分。两个核算引理（引理1，引理2）支持一个逐实例间隔-遗憾稳定性定理（定理1）和一个严格的纯分区识别定理（定理2），后者展示了分区报告何时无法证明部署的赢家。
2. **实证**。在五个公开的AS基准测试上，我们区分了*分解与扁平*部署决策（其中安全性条件在4/10的比较中失败，B2/B4有符号变化的点估计）和*分解与分解*外层选择器比较（其中成对和多类别几乎无法区分，\(\|A_{\text{part}}\| < 5 \times 10^{-3}\)）。间隔-遗憾违反率（0.23–0.56）和识别区间（所有15对跨零）证实了定理。
3. **实践**。一种训练侧的差距校正诊断方法在所有四个符号变化的单元格中恢复了点估计的可部署符号；一种部署感知的家族选择器在每个基准测试上都缩减了 \(G(R)\)，并在B1–B4上提高了 \(S_{\text{e2e}}\)，在PROTEUS上有一个小的权衡。我们提供了一个清单，要求将 \(S_{\text{part}}\)、\(S_{\text{e2e}}\)、\(G(R)\)、安全性条件和识别区间一起报告（§6）。

## 2 相关工作
##### 预言机基线和VBS。算法选择长期以来使用预言机基线，如虚拟最佳求解器（VBS）作为投资组合性能的上界（Xu 等，2008）。像AutoFolio（Lindauer 等，2015）和ASlib中的标准化AS场景（Bischl 等，2016）这样的框架明确地将可部署选择器与此VBS进行比较，而AS竞赛则通过SBS-VBS区间对分数进行归一化（Lindauer 等，2019）。Cameron 等（2016）进一步记录了当求解器是随机化时，VBS评估本身可能具有乐观偏差。超出完整投资组合VBS的预言机风格评分也经常被报告。*选择性投资组合*VBS出现在k-投资组合研究（Bach 等，2022）和用于自动算法选择的投资组合选择（Kostovska 等，2023）中；*子投资组合*虚拟最佳评分与可部署系统一起在Proteus（Hurley 等，2014）等分层求解器投资组合中报告，其四个家族对应于一个CSP原生求解器分支和三个输入的SAT编码。编码级选择有其自己的*虚拟最佳编码*作为标准上界（Stojadinović 和 Marić，2014；Ulrich-Oltean 等，2022，2023），而表格基准测试文献报告*家族内最佳*摘要——最佳深度模型与最佳梯度提升模型——作为主要比较对象（McElfresh 等，2023；Shmuel 等，2025）。附录R中给出了十二个此类报告对象的文献审查、每个行支持的主张以及该支持的强度；Shmuel 等（2025）是一个代表性的表格实例，其中DL最佳与TE最佳的比较是标题结论，并且未指定家族内可部署选择器。精神上最接近的是，Tornede 等（2023）在算法选择器上定义了一个AS预言机，并表明将预言机提升到该元级别可能会降低预言机性能；我们的设置不同，隐藏的预言机是在已选择家族内的算法上，而不是在完整的选择器上，因此相关的损失是家族内部署保真度差距 \(G(R)\)。

##### 方法论批判。Petelin 和 Cenikj（2025）在基于特征的AS基准测试中确定了两个陷阱——留一实例（LIO）划分和尺度敏感性能目标——这两者都与我们的关注点正交：LIO控制*哪些*测试实例被留出，尺度敏感性控制数字*目标*，而部署保真度差距关注的是*哪个系统*被评估。与划分或目标尺度效应不同，部署保真度差距改变了被评估对象本身：一个预言机辅助的分区评分替换了可部署选择器的一个阶段。

##### 算法选择和分类中的分解。成对分类（Sun 和 Pfahringer，2013；Galar 等，2011）、多类别选择器和家族级分解作为*训练*策略得到了充分研究，通常在纠错输出码框架内进行分析（Allwein 等，2000）。我们研究的是，一旦内部的家族内决策在部署时留给了一个学习的选择器，此类分解是如何被*评估*的。

## 3 设置
令 \(x \in \mathcal{X}\) 表示一个问题实例（例如一个数据集或一个SAT公式），\(\mathcal{A}\) 表示一个有限的算法池，\(\Pi = \{F_1, \dots, F_K\}\) 表示 \(\mathcal{A}\) 划分为算法家族的划分（对于 \(i \neq j\)，\(F_i \cap F_j = \emptyset\)，且 \(\bigcup_k F_k = \mathcal{A}\)）。令 \(u(x, a) \in \mathbb{R}\) 表示算法 \(a\) 在实例 \(x\) 上的效用；越高越好。在整篇论文中，我们对分数和优势都使用效用惯例。其原生指标是遗憾或运行时间的基准测试通过*逐实例*单调变换（附录A）映射到效用上，这保留了算法在实例内的排序；因此，所有报告的幅度和优势都解释为归一化效用尺度上的。一个*分解选择器* \(R\) 由一个家族级选择器 \(h_R: \mathcal{X} \rightarrow \{1, \dots, K\}\) 和，对于每个家族 \(k\)，一个家族内选择器 \(g_{R,k}: \mathcal{X} \rightarrow F_k\) 组成。令 \(\hat{k}_R(x) = h_R(x)\) 表示预测的家族，并定义家族 \(k\) 预言机最佳算法 \(a_k^*(x) = \arg\max_{a \in F_k} u(x, a)\)。

##### 分区评分。*分区级*评估授予预测家族内的预言机选择：
\[ S_{\text{part}}(R) = \mathbb{E}_x\bigl[\,u\bigl(x,\,a_{\hat{k}_R(x)}^*(x)\bigr)\,\bigr]. \tag{3} \]

##### 端到端评分。*端到端*评估部署实际可用的家族内选择器：
\[ S_{\text{e2e}}(R) = \mathbb{E}_x\bigl[\,u\bigl(x,\,g_{R,\hat{k}_R(x)}(x)\bigr)\,\bigr]. \tag{4} \]

##### 部署保真度差距。\(G(R) := S_{\text{part}}(R) - S_{\text{e2e}}(R)\) 衡量分区级评估在多大程度上高估了可部署系统。对于在同一测试分布上评估的两个流程 \(R_1, R_2\)，分区优势和端到端优势分别为 \(A_{\text{part}} := S_{\text{part}}(R_1) - S_{\text{part}}(R_2)\) 和 \(A_{\text{e2e}} := S_{\text{e2e}}(R_1) - S_{\text{e2e}}(R_2)\)。

## 4 从分区评分到部署稳定性
本节通过三个步骤关联§3中的四个估计量。§4.1记录两个核算引理：\(G(R)\) 等于家族内遗憾，且优势吸收等于差距之差。§4.2陈述一个间隔-遗憾稳定性定理，逐实例地刻画在分区时选择的家族何时也是部署最优的。§4.3表明，即使在分区报告中加入了所选家族的效用范围，两个流程之间的可部署优势也仅在一个区间内可识别，并且当该区间严格跨零时，报告无法证明部署的赢家。

### 4.1 核算引理
###### 引理1（差距恒等式）
对于任何分解选择器 \(R\)，
\[ G(R) = \mathbb{E}_x\Bigl[\,u\bigl(x,\,a_{\hat{k}_R(x)}^*(x)\bigr) - u\bigl(x,\,g_{R,\hat{k}_R(x)}(x)\bigr)\,\Bigr] \geq 0, \tag{5} \]
当且仅当家族内选择器几乎必然在预测家族内选择了一个预言机最优算法时，等式成立。

###### 证明概要
将 (3), (4) 代入 \(G(R)\) 并利用 \(u(x, a_{\hat{k}_R(x)}^*(x)) - u(x, g_{R,\hat{k}_R(x)}(x))\) 在每个实例上的非负性。完整证明见附录F。∎

###### 引理2（优势吸收）
对于任何两个分解选择器 \(R_1, R_2\)，
\[ A_{\text{e2e}} = A_{\text{part}} - \bigl[\,G(R_1) - G(R_2)\,\bigr], \tag{6} \]
或等价地
\[ A_{\text{part}} - A_{\text{e2e}} = G(R_1) - G(R_2). \]

###### 证明概要
根据定义，\(S_{\text{e2e}}(R) = S_{\text{part}}(R) - G(R)\)；展开 \(A_{\text{e2e}} = S_{\text{e2e}}(R_1) - S_{\text{e2e}}(R_2)\)。