在最小过参数化下，从示例中认证对电路和Transformer是困难的

# 从例子中进行认证在最小过参数化下对电路和 Transformer 而言是困难的  
来源：https://arxiv.org/html/2605.22964  

###### 摘要  
随着最先进的神经网络被部署在推理和算法任务上，正确性保证变得越来越重要。然而，高平均准确率仍然可能掩盖不一致的行为。这激发了精确认证的需求，即寻找最小数量的带标签例子，以证明学习得到的假设等于目标。我们证明，尽管某些假设易于认证，但即使是极小的过参数化也可能在多个假设类中使认证变得指数困难。对于深度 ≥ 2 的阈值电路，增加一个额外的门就可能导致证书大小在输入维度上呈指数增长。我们为具有仅常数架构开销的对数精度 Transformer 展示了类似的困难结果。我们还刻画了近似认证，表明即使只允许多项式数量的错误，仍然需要指数大的证书，而常数相对误差保证可能隐藏指数数量的错误。在实验上，我们研究了针对构造电路和训练好的 Transformer 在识别二进制加法任务上的认证。虽然构造电路体现了认证的指数障碍，但训练好的 Transformer 分析表明，不完美的模型可以通过大规模均匀采样的证书候选来逃避检测。  

## 1 引言  
前沿模型能够处理广泛的任务，然而研究揭示了在推理和算法设置中的不一致性 [25, 20]。即使模型实现了高平均准确率，这种不一致性暗示它可能没有实现预期的推理行为，并且仅凭平均评估很难检测到这些失败。这激发了一个更广泛的精确认证问题：在学习者返回一个候选假设后，需要多少个带标签的输入-输出例子，才能仅从行为上证明该候选假设等于预期目标？  
György 等人 [14] 将此认证问题标记为精确学习设置中的一个基础挑战，并在一个比特比较任务中展示了最坏情况下的认证。在本工作中，我们给出了认证困难的量化形式，主要关注两个与推理和计算密切相关的形式化假设类。由于认证仅使用带标签的输入-输出数据，我们通过与教学集文献密切相关的视角来形式化这一问题 [4,29,13]。对我们而言，关键量是证书大小，即需要的最小带标签例子数量，以便在假设类中唯一识别一个目标。该量不仅依赖于目标，还依赖于周围的假设类。我们的主要观察是，即使对假设类进行极小的扩展（仅常数因子增加模型容量），也可能使原始类中的每个目标的认证都变得指数困难，即使原始类中某些目标原本具有小的证书。  

##### 贡献。我们的贡献如下：  
1. 1. 我们提供了通过例子进行精确认证的困难量化形式。我们证明认证对周围的假设类高度敏感。即使常数扩展也可能使原始类中的每个目标的认证变得指数困难，尽管该类中存在具有小证书的目标。我们在与算法计算相关的两个设置中实例化了这一现象。  
   (a) 在电路设置中，我们研究了无界扇入类如 TC⁰ 和 AC⁰，以及有界扇入类 NC¹。我们最尖锐的结果是针对 TC⁰，其中深度 d ≥ 2 的电路仅仅增加一个额外的门，就迫使认证需要输入维度上指数数量的例子。  
   (b) 在 Transformer 设置中，受 Transformer 与电路复杂度之间联系的启发 [15,24,21,23,9]，我们研究了具有平均硬注意力 (AHAT) 的投影预归一化对数精度 Transformer [15,23]。我们证明，只要轻微过参数化，增加一个额外的注意力头和六个辅助嵌入/残差坐标，就已经使认证变得困难。  
   (c) 我们将困难分析扩展到近似认证。我们证明，仅允许多项式数量的绝对错误仍然需要指数大小的证书，而常数相对误差保证仍可能允许指数数量的绝对错误。  
2. 2. 我们通过两个关于识别二进制加法任务的实验认证分析来补充理论。首先，我们构造了一个用于识别加法的 TC⁰ 电路，以及一组不正确的电路，每个电路与目标仅在输入的不同块上一致。然后我们计算有多少这样的电路与均匀采样的证书候选保持一致。其次，我们研究训练好的 Transformer 以识别二进制加法。在选择了通过广泛验证检查的训练模型后，我们在一个大的保留测试集上评估它们。我们观察到，即使是多项式大小的证书候选，也可能使多个非精确的训练假设保持一致。  

## 2 相关工作  
我们的认证设置与经典的教学复杂度文献最为相关 [4,29,13]。后续工作发展了多种教师-学习者协议变体 [30,11,12]，并将教学参数与假设类的结构性质联系起来，例如类复杂度 [11,8,19]。在电路设置中，最接近的工作是 Servedio [28]，他证明了仅使用输入-输出例子时，多项式大小单调电路的证书大小的最坏情况指数下界。主要区别在于我们的下界并未孤立出一个最坏情况的目标。这一区别在我们关于阈值电路的结果 (定理 4.1) 中最为明显，该定理表明对于较小阈值电路类中的每个目标，增加一个相同深度的门就已经使精确认证变得指数困难。  
与通过例子进行认证相关的是精确学习，后者通常研究学习者和 oracle 之间的主动查询交互，包括成员查询、等价查询以及相关的 oracle 访问 [1,2,3,16,18,7]。该文献中的一个核心主题是，可学习性既依赖于交互模型，也依赖于学习者可能输出的假设类。例如，DNF 的正确学习和不当学习表现出不同的可学习性行为 [27,17]，而更丰富的 oracle 访问可以使电路学习变得可处理 [6]。在我们仅使用输入-输出的认证设置中，我们隔离了假设类的作用，并证明即使是类的微小扩展也会使认证变得困难。  
在神经网络的背景下，几项近期工作主张以精确保证（而非仅平均准确率）作为可靠推理和算法行为的基础 [14,10,26]。特别是，György 等人 [14] 强调了证明精确正确性的重要性和挑战性。我们的工作在此基础上量化了对数精度 Transformer 所需的证书大小。大多数关于对数精度 Transformer 的理论工作集中在表达能力上，其计算由阈值电路模型捕获 [24,21,23,22,9]。虽然这些结果刻画了此类模型能计算什么，但我们的结果解决了一个互补的问题：需要多少输入-输出例子来认证它们的行为。我们证明，在轻微过参数化的类中认证对数精度 Transformer，即使对于精确和近精确认证，也需要输入大小上的指数数量例子。  

## 3 预备知识与符号  
在本节中，我们介绍全文使用的符号和背景定义。我们用 \([n]\) 表示集合 \(\{1,2,\dots,n\}\)。对于向量 \(x\in\{0,1\}^n\) 和索引集合 \(I\subseteq[n]\)，我们用 \(x_I\) 表示 \(x\) 限制在索引 \(I\) 上的坐标。对于有限集合 \(S\)，我们令 \(\{0,1\}^S=\{\pi:S\to\{0,1\}\}\) 表示 \(S\) 上的二进制模式集合。  

电路复杂度与电路类。  
我们将电路用作有限语义假设类，因为它们使我们可以衡量增加一个或几个门增加了多少计算能力。电路也直接与 Transformer 的结果相关，因为对数精度 Transformer 的表达性通常与阈值电路计算进行比较 [24,23]。  
输入为 \(x_1,\ldots,x_n\) 的布尔电路是一个有向无环图，包含输入节点、内部门和一个输出门。其大小 \(|C|\) 是非输入门的数量，深度是最长输入到输出路径的长度。在多项式大小下，标准包含关系为 \(\mathrm{AC}^0 \subsetneq \mathrm{TC}^0 \subseteq \mathrm{NC}^1\)。这里 \(\mathrm{AC}^0\) 由常数深度、无界扇入的 AND/OR 门（作用于输入文字）构成，\(\mathrm{TC}^0\) 增加了常数深度的阈值门，而 \(\mathrm{NC}^1\) 允许对数深度的有界扇入电路。第一个包含是严格的，第二个的严格性尚未解决。对于有限的门预算，\(\mathrm{AC}^0_{d,s}\) 和 \(\mathrm{TC}^0_{d,s}\) 分别表示可由深度为 \(d\)、大小为 \(s\) 的相应类型电路计算的 \(n\) 输入函数。在 \(\mathrm{TC}^0_{d,s}\) 中，阈值门定义为 \(\mathrm{THR}_{w,\theta}(z)=\mathbf{1}[\sum_i w_i z_i \geq \theta]\)，其中 \(w_i,\theta\in\mathbb{Z}\)。对于 \(\mathrm{TC}^0\)，该类也可以用布尔析取/合取和多数门表示。所有这些门都可以表示为阈值门，但反向模拟会改变有限门预算，因此所述的 \(\mathrm{TC}^0\) 界应在阈值门约定下阅读。类 \(\mathrm{NC}^1_{s}\) 表示有界扇入的布尔电路，其大小最多为 \(s\)，深度最多为 \(c_{\mathrm{NC}^1}\log(n+1)\)，其中 \(c_{\mathrm{NC}^1}\) 是固定常数。  

输入-输出证书。  
所有证书都基于固定有限域 \(\mathcal{X}\)。固定一个假设类 \(\mathcal{H}\) 和一个目标 \(f^\star\in\mathcal{H}\)。我们通过其输入集合 \(S\subseteq\mathcal{X}\) 记录带标签样本，其中对应 \(x\in S\) 的标签为 \(f^\star(x)\)。在看到 \(S\) 后的版本空间为  
\[
\mathrm{VS}_{f^\star,\mathcal{H}}(S) := \{h\in\mathcal{H}: h(x)=f^\star(x) \text{ for every } x\in S\}.
\]  
集合 \(S\) 是 \(f^\star\) 在 \(\mathcal{H}\) 中的输入-输出证书，如果每个存活的假设在整个域上与 \(f^\star\) 一致：  
\[
\forall h\in\mathrm{VS}_{f^\star,\mathcal{H}}(S),\qquad h(x)=f^\star(x) \text{ for every } x\in\mathcal{X}.
\]  
证书大小为  
\[
\operatorname{cert}(f^\star,\mathcal{H}) := \min\{ |S| : S\subseteq\mathcal{X} \text{ and } S \text{ is an input-output certificate for } f^\star \text{ in } \mathcal{H} \}.
\]  
由于 \(S=\mathcal{X}\) 是一个证书，该最小值是良好定义的。该定义是语义性的：它证明了目标的输入-输出行为，并不区分在 \(\mathcal{X}\) 上行为相同的假设。这是通常的教学/说明概念 [29,13,4]。  

近似证书。  
保持相同的有限域 \(\mathcal{X}\)、假设类 \(\mathcal{H}\) 和目标 \(f^\star\)。对于 \(h\in\mathcal{H}\)，定义其相对于 \(f^\star\) 的绝对误差和归一化误差为  
\[
\Delta(h) := |\{x\in\mathcal{X}: h(x)\neq f^\star(x)\}|,\qquad \mathrm{err}(h) := \frac{\Delta(h)}{|\mathcal{X}|}.
\]  
对于 \(\rho\in\{\Delta,\mathrm{err}\}\)，看到 \(S\) 后剩余的最坏误差为  
\[
M_{\rho}(S) := \max_{h\in\mathrm{VS}_{f^\star,\mathcal{H}}(S)} \rho(h).
\]  
对于 \(\varepsilon,R\geq 0\)，近似证书大小为  
\[
\operatorname{cert}_{\varepsilon}(f^\star,\mathcal{H}) := \min\{ |S| : S\subseteq\mathcal{X} \text{ and } M_{\mathrm{err}}(S)\leq\varepsilon \},
\]  
和  
\[
\operatorname{cert}_{R}(f^\star,\mathcal{H}) := \min\{ |S| : S\subseteq\mathcal{X} \text{ and } M_{\Delta}(S)\leq R \}.
\]  
因此 \(\operatorname{cert}_{\varepsilon}\) 证明每个存活假设的一致误差最多为 \(\varepsilon\)，而 \(\operatorname{cert}_{R}\) 证明每个存活假设在 \(\mathcal{X}\) 上最多犯 \(R\) 个错误。精确认证是 \(\varepsilon=0\)（等价于 \(R=0\)）的情况。  

## 4 由过参数化导致的认证困难  
在整个这一节中，我们对在扩展后的假设类中唯一认证目标所需的带标签例子数量给出下界。