分析凸松弛对神经网络验证的误差影响，揭示其失效边界。
The Cost of Relaxation: Evaluating the Error in Convex Neural Network Verification
- 用凸松弛替代整数约束加速验证，但牺牲了准确性
- 全松弛与原网络输出的ℓ∞距离随深度指数增长
- 适合关注验证系统可靠性或安全性研究者
许多神经网络验证系统将输入输出关系表示为约束规划。这类方法需引入整数约束以模拟激活值，而近期工作采用凸松弛替代整数约束以提升效率，代价是损失了严格正确性。凸松弛会包含原网络无法达到的输出。本文定量分析原网络与凸松弛之间的最坏情况偏差，定性与定量结合。松弛空间构成格结构，顶层对应完全松弛（所有神经元线性化），底层为原网络。本文给出ℓ∞距离的上下界：该距离随网络深度呈指数增长，随输入半径呈线性增长；误分类概率随输入半径呈现阶梯状变化。实验在MNIST、Fashion MNIST及随机网络上验证了结论。
原文摘要 · Abstract (English)
Many neural network (NN) verification systems represent the network's input-output relation as a constraint program. Sound and complete, representations involve integer constraints, for simulating the activations. Recent works convexly relax the integer constraints, improving performance, at the cost of soundness. Convex relaxations consider outputs that are unreachable by the original network. We study the worst case divergence between the original network and its convex relaxations; both qualitatively and quantitatively. The relaxations' space forms a lattice, where the top element corresponds to a full relaxation, with every neuron linearized. The bottom element corresponds to the original network. We provide analytical upper and lower bounds for the $\ell_\infty$-distance between the fully relaxed and original outputs. This distance grows exponentially, w.r.t. the network's depth, and linearly w.r.t. the input's radius. The misclassification probability exhibits a step-like behavior, w.r.t. input radius. Our results are supported by experiments on MNIST, Fashion MNIST and random networks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。