AdaStop：面向DNN测试选择的成本感知提前停止策略

# AdaStop: 面向 DNN 测试选择的成本感知早停策略
来源：https://arxiv.org/html/2607.05461
Bonan Shen1, Wei\-Jung Huang1, Xin Liu1, Jiazhou Gao1, Tao Ning1

###### 摘要

现有的深度神经网络（DNN）测试方法主要关注在固定标注预算下，优先选择可能揭示模型错误的测试输入。然而，在实际中，选择这一预算十分困难：测试过少会遗漏错误，而测试过多则会带来不必要的标注成本。本研究探讨了 DNN 测试中的停止问题。我们将测试形式化为一个成本-收益决策过程，其中标注一个输入产生成本 \(c\)，而发现一个错误则产生价值 \(v\)。基于这一形式化，我们引入了 **AdaStop** 框架，该框架在测试过程中估计边际错误发现率，并在估计率低于阈值 \(\tau = c/v\) 时停止标注。在多个数据集、架构和选择策略上的实验表明，仅使用 \(9\%\)–\(31\%\) 的标注预算，即可发现 \(65\%\)–\(84\%\) 的错误。

## I 引言

深度神经网络（DNN）越来越多地部署在可靠性至关重要的领域，包括自动驾驶【24 (https://arxiv.org/html/2607.05461#bib.bib24)】、医疗诊断【25 (https://arxiv.org/html/2607.05461#bib.bib25)】和金融系统【26 (https://arxiv.org/html/2607.05461#bib.bib26)】。确保可靠性需要系统性的测试，以识别模型做出错误预测的测试输入——通常称为 **错误**。然而，在许多场景下，验证预测需要真实标签，而这些标签通常需要通过领域专家进行昂贵的人工标注来获取【27 (https://arxiv.org/html/2607.05461#bib.bib27)】。

这就产生了一个根本性的实际挑战：**我们何时应该停止标注测试输入？** 过早停止可能会遗漏那些可能导致系统故障的错误；过晚停止则会浪费标注资源，用于那些不太可能发现新错误的输入。

现有的测试选择方法主要关注 **选择** 问题——即确定哪些输入应该优先标注——而互补的 **停止** 问题则受到的关注相对较少。我们指出了三个关键局限性：

1.  **缺乏原则性的停止准则。** 像 DeepGini【9 (https://arxiv.org/html/2607.05461#bib.bib9)】、TestRank【10 (https://arxiv.org/html/2607.05461#bib.bib10)】、ATS【11 (https://arxiv.org/html/2607.05461#bib.bib11)】和 DeepSample【12 (https://arxiv.org/html/2607.05461#bib.bib12)】等方法，通常在预定标注预算下评估性能，但没有提供测试何时应该终止的指导。
2.  **任意选择预算。** 在缺乏停止准则的情况下，实践者必须启发式地选择标注预算。然而，合适的预算依赖于模型质量和数据集特征等因素，这些因素通常是事先未知的。
3.  **未处理的成本-收益权衡。** 标注每个输入都会产生成本，而发现一个错误则带来价值。现有方法侧重于优化测试选择的 **顺序**，例如优先选择更可能揭示模型错误的输入，但并未明确考虑这种成本-收益权衡【9 (https://arxiv.org/html/2607.05461#bib.bib9)】。

尽管在相关领域存在停止准则，例如用于文档筛选的 SAFE 过程【18 (https://arxiv.org/html/2607.05461#bib.bib18)】和用于主动学习的基于收敛的停止方法【13 (https://arxiv.org/html/2607.05461#bib.bib13)】，但这些方法尚未被适配到 DNN 测试选择中，后者的目标是高效的错误发现。

一个关键的实证观察启发了我们的方法：测试选择通常表现出 **收益递减** 的特性。具有较高不确定性的输入（通常是优先选择的那些）往往以更高的比率揭示错误。随着测试的进行，剩余输入每个标注实例产生的错误逐渐减少。

这种行为表明，额外标注的价值随时间递减，从而产生一个自然点，超过该点后进一步测试将变得低效。基于这一观察，我们提出了 **AdaStop**，一个成本感知框架，当边际错误发现率 \(p(t)\) 低于成本调整后的阈值 \(\tau = c/v\) 时终止测试，其中 \(c\) 表示标注成本，\(v\) 表示发现一个错误的价值。

AdaStop 框架由三个组件组成：(1) 一个基于不确定性的选择策略 (DeepGini)，用于优先选择可能揭示错误的输入；(2) 一个边际错误发现率的滑动窗口估计器；(3) 一个成本感知的停止规则，当估计率低于 \(\tau\) 时终止标注。

**贡献。** (1) 我们将 DNN 测试选择构建为一个顺序成本-收益优化问题，推导出了最优停止条件 \(\tau = c/v\)。(2) 我们提出了一个基于成本感知阈值的停止规则，并将其与实用的替代方案（包括耐心策略、连续无错误策略、置信度策略和累积率策略）进行了比较。(3) 我们在 3 个数据集、4 种架构、3 个质量水平和 8 种策略上进行了全面评估，实现了 65–84% 的召回率和 70–91% 的预算节省。(4) 我们提供了开源实现以供社区采用。

## II 问题形式化

### II-A 设置与目标

考虑一个 DNN 分类器 \(M: \mathcal{X} \rightarrow \mathcal{Y}\) 和一个未标注的测试池 \(\mathcal{U} = \{x_1, \ldots, x_n\}\)。**错误** 是指输入 \(x\) 使得 \(M(x) \neq y^*\)（真实标签）。每次查询的标注成本为 \(c > 0\)；每个发现的价值为 \(v > 0\)。

测试选择按顺序进行：在步骤 \(t\)，通过策略 \(s\) 从剩余池中选择输入 \(x_t\)，向 oracle 查询标签 \(y_t\)，记录结果 \(r_t = \mathbf{1}[M(x_t) \neq y_t]\)，并决定是否继续。在停止时间 \(T\) 的 **净价值** 为：

\[
V(T) = v \cdot F(T) - c \cdot T \quad (1)
\]

其中 \(F(T) = \sum_{t=1}^{T} r_t\) 是发现的错误数量。

### II-B 最优停止阈值

在步骤 \(t\)，标注一个额外输入的边际成本为 \(c\)，边际收益为 \(v \cdot p(t)\)，其中 \(p(t) = \mathbb{E}[r_t]\) 是发现一个错误的概率。下一个标签的边际净价值为：

\[
\Delta V(t) = v \cdot p(t) - c \quad (2)
\]

最优决策规则直接由此得出：如果 \(v \cdot p(t) > c\)（边际价值为正），则 **继续**；如果 \(v \cdot p(t) \le c\)，则 **停止**。重新排列停止条件得到：

\[
\boxed{\tau = \frac{c}{v}} \quad (3)
\]

**命题 1（最优停止）。** 在收益递减的情况下（错误率 \(p(t)\) 非增），最优策略是在第一个满足 \(p(T) \le \tau = c/v\) 的 \(T\) 处停止。一旦 \(p(t)\) 降至 \(\tau\) 以下，它将在后续所有步骤中保持低于该值，因此立即停止是最优的。□

阈值 \(\tau\) 是 **盈亏平衡错误率**。例如，如果标注成本 \(c = \$1\)，每个错误价值 \(v = \$20\)，则 \(\tau = 0.05\)：当期望少于 5% 的标签能发现错误时，我们停止。此时，下一个标签的期望价值恰好等于其成本。该阈值会自动调整——在安全关键场景中（低 \(c/v\)）会继续更长时间；在昂贵标注场景中（高 \(c/v\)）则提前停止。

### II-C 错误率估计

由于 \(p(t)\) 不可直接观测，我们使用滑动窗口从近期历史中估计它：

\[
\hat{p}(t) = \frac{1}{W} \sum_{i=t-W+1}^{t} r_i \quad (4)
\]

其中 \(W\) 是窗口大小。该估计器解决了三个挑战：(1) **非平稳性**——错误率随测试进行而降低，因此我们只使用最近的样本而非全部历史；(2) **噪声**——单个结果是二值的，因此在 \(W\) 个样本上取平均提供了平滑；(3) **响应性**——窗口比累积平均更快地适应率的变化。\(W\) 的选择涉及偏差-方差权衡：小的 \(W\) 响应快但有噪声（可能导致过早停止）；大的 \(W\) 稳定但检测率下降较慢。我们在第六节 (https://arxiv.org/html/2607.05461#S6) 中对此进行了实证分析。

### II-D 收益递减性质

最优停止条件依赖于一个关键的实证观察：**测试选择表现出收益递减**。当使用基于不确定性的选择（例如 DeepGini）时，高不确定性的输入被优先选择。由于高不确定性与更高的错误概率相关，错误率 \(p(t)\) 随着 \(t\) 的增加而下降。这确保了存在一个自然的停止点，在该点 \(p(t)\) 下降到低于 \(\tau\)。缺乏这一性质，停止问题将是不明确的——错误率可能不可预测地波动。我们将在第六节 (https://arxiv.org/html/2607.05461#S6) 中使用 Mann-Kendall 单调性检验来形式化验证这一假设。

## III 相关工作

### III-A DNN 测试选择

**基于不确定性的方法** 优先选择模型最不确信的输入。DeepGini【9 (https://arxiv.org/html/2607.05461#bib.bib9)】使用 softmax 输出的基尼不纯度；FAST【15 (https://arxiv.org/html/2607.05461#bib.bib15)】通过引导特征选择解决过度自信问题；CertPri【17 (https://arxiv.org/html/2607.05461#bib.bib17)】使用带有形式鲁棒性保证的移动成本。**覆盖率和多样性驱动的方法** 旨在获得多样化的测试输入：NLC【19 (https://arxiv.org/html/2607.05461#bib.bib19)】捕捉神经元输出分布；DeepGD【16 (https://arxiv.org/html/2607.05461#bib.bib16)】通过 NSGA-II 结合基尼分数与几何多样性。**基于学习的方法** 包括 TestRank【10 (https://arxiv.org/html/2607.05461#bib.bib10)】（基于 GNN 的排序）和 ATS【11 (https://arxiv.org/html/2607.05461#bib.bib11)】（基于 RL 的自适应选择）。**基于采样的方法** 包括 DeepSample【12 (https://arxiv.org/html/2607.05461#bib.bib12)】和 DeepReduce【22 (https://arxiv.org/html/2607.05461#bib.bib22)】。所有这些方法都使用固定预算，缺乏原则性的停止准则。

### III-B 其他领域的停止准则

主动学习使用基于收敛的准则【13 (https://arxiv.org/html/2607.05461#bib.bib13), 14 (https://arxiv.org/html/2607.05461#bib.bib14), 20 (https://arxiv.org/html/2607.05461#bib.bib20)】——当模型停止改进时停止。这与我们的设置根本不同：我们不是训练模型，而是在一个固定模型中发现错误。文档筛选使用基于发现的准则：SAFE【18 (https://arxiv.org/html/2607.05461#bib.bib18)】监测发现率；Chao 估计器【21 (https://arxiv.org/html/2607.05461#bib.bib21)】预测相关文档总数。Mittal 等人【23 (https://arxiv.org/html/2607.05461#bib.bib23)】将模型评估形式化为一个 MDP，但目标是最小化估计误差，而非错误发现效率。我们将基于发现的停止概念进行适配，添加了专门针对 DNN 测试的成本-收益形式化。

### III-C 研究空白

现有方法通常假设一个固定的标注预算，而未提供关于何时额外测试不再有价值的指导原则。表 I (https://arxiv.org/html/2607.05461#S3.T1) 总结了比较情况。

表 I：相关工作比较

## IV 提出的方法

### IV-A 框架概述

图 1 (https://arxiv.org/html/2607.05461#S4.F1) 展示了 AdaStop 框架。系统迭代地通过基于不确定性的排序选择输入，从 oracle 获取标签，估计当前错误率，并在错误率低于成本合理阈值时停止。

测试池 \(\mathcal{U}\) → 模型 \(M\) → (\(\tau, W, c, v\)) → 选择（DeepGini）→ Oracle（标签）→ 率估计器 → 停止当：\(\hat{p}(t) < \tau\) → 测试集 \(\mathcal{L}\)  
\(x_t\) → \(r_t\) → 继续  
**图 1：** AdaStop 框架。系统通过 DeepGini 迭代选择输入，获取标签，估计错误率，并在 \(\hat{p}(t) < \tau\) 时停止。

### IV-B 选择策略

AdaStop 使用 DeepGini【9 (https://arxiv.org/html/2607.05461#bib.bib9)】作为其默认选择策略，根据 softmax 输出的基尼不纯度对输入进行排序：

\[
\text{Gini}(x) = 1 - \sum_{i=1}^{C} p_i(x)^2 \quad (5)
\]

其中 \(p_i(x)\) 是对类别 \(i\) 的预测概率，\(C\) 是类别数。在每一步，我们从剩余池中选择具有最高基尼分数的输入，因为不确定的预测更可能是错误的。我们选择 DeepGini 是因为其简单性（仅需 softmax 输出）、有效性（比随机好 4–5 倍）和广泛采用。AdaStop 的停止框架是 **策略无关的**，并且兼容任何能够产生排序顺序的策略（第六节-F (https://arxiv.org/html/2607.05461#S6.SS6)）。

### IV-C 停止准则

我们讨论了针对不同场景的四种实用停止准则：

**基于阈值的（默认）。** 当 \(\hat{p}(t) < \tau\) 时停止，并带有最小样本约束 \(N_{\min}\) 以确保估计可靠。直接实现了成本-收益最优条件。阈值 \(\tau = c/v\) 应反映测试场景的成本-收益比。

**耐心策略。** 当 \(\hat{p}(t)\) 首次降至 \(\tau\) 以下时，继续额外进行 \(k\) 个标签的耐心窗口，除非估计率再次升至 \(\tau\) 以上，否则停止。该准则在停止边界附近为瞬态波动增加了一个小的安全边际。

**连续无错误。** 在观察到 \(k\) 个连续无错误的标签后停止。该准则实现简单，无需设置明确的成本-收益阈值，但与最优条件关联较弱。

**基于置信度的。** 针对风险厌恶场景，当 Wilson 置信区间【8 (https://arxiv.org/html/2607.05461#bib.bib8)】的上界低于 \(\tau\) 时停止：\(\text{CI}_{\text{upper}}(\hat{p}) < \tau\)。这减少了过早停止的风险，但代价是更多预算。

### IV-D 完整算法

算法 1 (https://arxiv.org/html/2607.05461#alg1) 展示了 AdaStop 的完整过程。

**算法 1** AdaStop：成本感知测试选择
1. **输入：** 测试池 \(\mathcal{U}\)，模型 \(M\)，阈值 \(\tau\)，窗口 \(W\)，最小样本数 \(N_{\min}\)
2. **输出：** 标注的测试集 \(\mathcal{L}\)
3. 计算所有 \(x_i \in \mathcal{U}\) 的基尼分数 \(G_i \leftarrow 1 - \sum_j P_{ij}^2\)
4. \(\mathcal{R} \leftarrow \mathcal{U}\)，\(\mathcal{L} \leftarrow \emptyset\)，\(H \leftarrow []\)
5. **对于** \(t = 1, 2, \ldots\) **执行**
6.   \(x_t \leftarrow \arg\max_{x_i \in \mathcal{R}} G_i\)；\(\mathcal{R} \leftarrow \mathcal{R} \setminus \{x_t\}\)
7.   \(r_t \leftarrow \mathbf{1}[M(x_t) \neq \text{Oracle}(x_t)]\)；将 \(r_t\) 追加到 \(H\)
8.   \(\mathcal{L} \leftarrow \mathcal{L} \cup \{(x_t, r_t)\}\)
9.   \(\hat{p} \leftarrow \text{mean}(H[\max(1, |H|-W+1): |H|])\)
10.  **如果** \(|\mathcal{L}| \geq N_{\min}\) **且** \(\hat{p} < \tau\) **则**
11.     返回 \(\mathcal{L}\)  {成本感知停止}
12.  **结束如果**
13. **结束循环**

## V 实验设置

### V-A 研究问题

- • **RQ1:** AdaStop 能否以较小的预算比例实现高召回率？
- • **RQ2:** \(\tau\) 对召回率-预算平衡有何影响？
- • **RQ3:** 不同停止准则之间有什么差异？
- • **RQ4:** AdaStop 对窗口大小 \(W\) 有多敏感？
- • **RQ5:** AdaStop 在数据集和架构方面是否具有良好的泛化性能？
- • **RQ6:** AdaStop 是否策略无关？
- • **RQ7:** 如何设置