可证解释的 ReLU-MLP 布尔任务训练，确保真值表泛化

# 基于真值表泛化保证的布尔任务可证可解释ReLU-MLP训练
来源：https://arxiv.org/html/2609.13439  
Hrad Ghoukasian  
hrad\.ghoukasian@mail\.utoronto\.ca  
所属机构：电气与计算机工程系  
所属机构：多伦多大学  
所属机构：加拿大安大略省多伦多市圣乔治街40号，M5S 2E4  
Anastasis Kratsios  
kratsioa@mcmaster\.ca  
所属机构：数学系  
所属机构：麦克马斯特大学及Vector研究所  
所属机构：加拿大安大略省汉密尔顿市主西街1280号，L8S 4K1  

###### 摘要  
随着计算规模扩大、模型演进与训练算法进步，我们解释日益强大的AI系统的能力却在减弱。为维护可解释性，我们提出专用训练算法Macchiato，该算法同时完成（i）从部分真值表观测构建显式结构化ReLU\operatorname{ReLU}多层感知机（MLP）；（ii）基于带符号文字（AND, OR, XOR门）\{\\operatorname{AND},\\operatorname{OR},\\operatorname{XOR\}的显式布尔电路，以认证子网络的计算内容与组合方式。直观而言，我们通过迭代投影布尔函数残差至低维\{AND, OR, XOR\}电路类，并将所得电路精确编译为ReLU MLP；该过程结合ReLU MLP电路编译、Espresso逻辑最小化及基于影响力变量选择。简言之，我们的可解释性证书辅以统计保证：在定理影响力恢复条件下，若每阶段残差最多依赖\(\log_2(B)\)比特信息，则基于\(T\)次真值表观测的样本分割算法将训练出六层（含输入层）宽度为\(\mathcal{O}(mB)\)的ReLU MLP，其真值表误差为\(\mathcal{O}\bigl(\sqrt{m(B+\log(m/\delta))/T}\bigr)\)。在合成随机junta任务中，本网络在数据稀疏或投影对齐场景下超越深度与隐藏宽度匹配的Adam训练MLP，而ReLU MLP在其他场景表现更优。此外，在显式PyEDA真值表实现中，迭代流程在常规维度Espresso超出三小时计算预算时仍能完成。  

††简短标题：布尔任务可证可解释ReLU-MLP训练 / H\. Ghoukasian与A\. Kratsios  
††首页：1  
††编辑：我的编辑  

###### 关键词  
AI可解释性；可证可解释性；逻辑推理；布尔函数学习；部分真值表；可解释神经网络；布尔电路；逻辑最小化。  

## 1 引言  
现代AI的卓越进展由计算能力（Owens et al., 2008）、日益富有表达力的模型架构（Vaswani et al., 2017）及日趋复杂的梯度训练算法（Loshchilov and Hutter, 2019）共同驱动。然而，现代深度学习的快速规模扩展（Hestness et al., 2017；Kaplan et al., 2020；Bahri et al., 2024）引发了诸多AI安全担忧（如Bengio et al., 2024；Bengio et al., 2026），部分源于我们解释复杂模型预测机制的能力有限。这些担忧反映在近期北美（加拿大财政部委员会秘书处, 2026；墨西哥内政部, 2024；美国NIST, 2023）、欧洲（欧洲议会与欧盟理事会, 2024）、中国（国家互联网信息办公室等四部门, 2022）及俄罗斯（俄罗斯总统令, 2024）等地为AI系统建立可解释性与透明度规范的立法努力中。然而，由于标准化AI解释工具仍不成熟，此类准则往往不如治理其他"具有广泛社会影响的数学技术"（如2008年金融危机后金融风险管理领域发展的标准化量化工具——预期短缺（Delbaen, 1998）及相应明确监管要求（巴塞尔银行监管委员会, 2009, 2012））的监管框架具体。虽然AI可解释性的标准化仍属长期目标，本文旨在为构建内部计算可解释的模型迈出具体一步。不同于开发解释标准梯度训练模型的工具（如推理探针（Alain and Bengio, 2017；Hewitt and Liang, 2019；Burns et al., 2023）与归因方法（Ribeiro et al., 2016；Lundberg and Lee, 2017；Sundararajan et al., 2017）），我们提出一种同时生成（i）预测神经网络与（ii）可读为逻辑公式的显式网络分解的训练算法。此路径基于日益增多的证据表明：梯度训练神经网络可能插值训练数据或利用统计捷径，而非必然恢复任务底层规则（Zhang et al., 2017；Geirhos et al., 2020；McCoy et al., 2019；Vershynin, 2020；Vardi et al., 2022；Hong and Kratsios, 2024）。本文聚焦此可解释性路径的最简化现实版本：考虑\(B\)位布尔分类器\(f:\{0,1\}^{B}\to\{0,1\}\)，通过\(T\)个真值表样本观测。目标是开发训练过程，推断出既能在训练数据外泛化又足够灵活以重构广泛布尔任务\(f\)的模型，同时满足属于可解释网络中少数"组合意义明确"子集的约束——即精确计算\(\operatorname{AND}\)、\(\operatorname{OR}\)与\(\operatorname{XOR}\)组合的网络。我们选择这些基本连接词基于下文讨论的语言动机（参见§1.2）。  

### 1.1 主要贡献  
主要实践贡献为算法1与2及其理论保证。算法1（Macchiato¹）从\(T\)个标记真值表观测推断部分观测布尔函数\(f\)的显式\{AND, OR, XOR\}电路表示。其迭代过程为：识别当前残差最具影响力的小坐标集，对剩余坐标边缘化，并应用Espresso（Brayton et al., 1982）²推断低维布尔修正，随后通过\(\operatorname{XOR}\)整合到累积电路中。算法1的关键实践特性在于从不将完整环境维度真值表传递至Espresso：每次调用最多涉及\(K\ll B\)坐标，避免了\(2^{B}\)规模的指数环境表示，并显著扩展了基于Espresso学习的计算可行范围。在最大规模实验中，直接环境维度Espresso无法在计算预算内返回，而算法1成功完成（表2-3及5.1节）。  

##### 算法1（Macchiato – 推理）：可扩展迭代电路推断  
在残差影响力分离条件（假设8）下，我们建立量化影响力恢复保证（定理6），并证明当阶段残差具有低有效维度时，算法1能获得相应的高概率真值表精度保证（定理9）。更一般地，定理14给出任意有限布尔函数类的同步影响力恢复保证，定理20量化了所选投影产生非零逼近误差时的预测误差。尽管主结果基于\(\{0,1\}^{B}\)上的均匀采样陈述，分析可扩展至任意输入分布（见附录F.2）。具体而言，分布依赖的影响力恢复保证见推论22，命题24提供均匀与分布依赖影响力的直接比较。  

##### 算法2（Macchiato – 编译）：可证ReLU MLP编译  
我们的可解释性证书由定理11形式化，该定理证明算法2产生的ReLU MLP精确实现了第一阶段学习的\{AND, OR, XOR\}电路。简言之，采用Kratsios et al.（2026a，命题6.6）的"手术"技术，我们构建标准化小型ReLU子网络以精确实现所需布尔门，并替换学习电路中的对应门。因此，布尔电路首先被学习，其ReLU MLP实现随后被*编译*。这与事后解释流程相反——后者先训练神经网络，再解释或符号化近似其内部计算。需强调，我们的证书是*模块化*的：并非声称每个神经元都具有独立语义解释，而是可识别的神经元或小子网络共同精确实现\(\operatorname{AND}\)、\(\operatorname{OR}\)与\(\operatorname{XOR}\)基本运算，且其组合方式由构造可知。  

### 1.2 连接词选择的语义动机  
我们聚焦\(\operatorname{AND}\)、\(\operatorname{OR}\)与\(\operatorname{XOR}\)连接词，因心理学研究表明合取（\(\operatorname{AND}\)）是日常命题推理的基本操作（Johnson-Laird et al., 1992），而异或（\(\operatorname{XOR}\)）自然作为英语"or"的语用解释出现³。尽管析取（\(\operatorname{OR}\)）在日常英语中稍显不自然，但它是形式数学推理与初等逻辑的标准基本连接词（Dawkins and Cook, 2017）。相比之下，多数表决（\(\operatorname{MAJ}\)）虽计算效率更高（Furst et al., 1984；Håstad, 1986），但在英语初等命题连接词中无直接对应。其自然语言实现为比例量词如"大多数"与"超过半数"，其中"大多数A是B"通过比较\(\#(A\cap B)\)与\(\#(A\setminus B)\)评估（Pietroski et al., 2009）。此外，英语"most"未必对应\(\operatorname{MAJ}\)编码的严格50%阈值，常被解释为"显著超过半数"（Denić and Szymanik, 2022）。比例量词如"超过半数"也比简单量词"所有"与"存在"验证更慢且更不精确（Szymanik and Zajenkowski, 2010）。因此，多数表决在日常英语中可能较难直接解释，故我们未将其纳入。  

### 1.3 相关工作  
#### 1.3.1 与逻辑最小化及Espresso的关联  
近期Qiao et al.（2023）使用Espresso在黑盒去噪后学习紧凑可解释DNF分类器。更广泛而言，尽管启发式Espresso常逼近计算代价高昂的精确最小化器（McCluskey, 1956；Rudell and Sangiovanni-Vincentelli, 1987），其自身可扩展性限制催生了SAT、GPU及百万级变体（Sapra et al., 2003；Kanakia et al., 2021；Nazemi et al., 2021）。与这些工作不同，我们通过残差避免高维最小化。