证明二值神经网络的鲁棒性验证在多种情况下是计算难问题，但均匀遮挡可实现高效验证。
Some Complexity Results for Robustness Verification for Binarized Neural Networks
- 通过归约到SAT问题，证明线性性质可满足性为NP完全
- 非均匀遮挡下鲁棒性验证也是NP完全，计算复杂度高
- 均匀遮挡使输出呈分段常数结构，可设计多项式时间算法
本文研究了二值神经网络（BNNs）中激活值和权重均为二值时的验证问题的计算复杂性。具体考察三种验证问题：首先，通过从布尔可满足性（SAT）问题归约，证明BNN的线性性质可满足性为NP完全；其次，通过类似归约，表明在非均匀图像遮挡下的鲁棒性验证亦为NP完全；最后，发现均匀遮挡会诱导网络输出呈现分段常数结构，从而可设计出多项式时间的鲁棒性验证算法。
原文摘要 · Abstract (English)
This paper investigates the computational complexity of verification problems for Binarized Neural Networks (BNNs), in which activations and weights are binary. Specifically, we study three verification problems. First, we prove that checking the satisfiability of a linear property for a BNN is NP-complete via a reduction from the Boolean Satisfiability (SAT) problem. Second, we show that verifying robustness under non-uniform image occlusion is NP-complete through a reduction from SAT. Finally, we demonstrate that uniform occlusion induces a piecewise-constant structure in the network output, which enables the design of a polynomial-time algorithm for robustness verification.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。