SART:神经网络验证中二元变量约简的符号-绝对值重构理论
SART: Sign-Absolute Reformulation Theory for Binary Variable Reduction in Neural Network Verification
预印本 · 尚未经过同行评审
SART打破不稳定神经元与二元变量的一一对应,证明末层变量可压缩50%,并提出LayerABS验证器将收益扩展至全网。
对神经网络进行完整的形式化验证对其在安全关键领域的部署至关重要。一个关键瓶颈源于编码复杂度:传统方法为每个不稳定 ReLU 神经元分配一个二值变量。我们提出符号-绝对值重构理论(Sign-Absolute Reformulation Theory, SART),该理论通过建立形式化可归约准则,从根本上打破了不稳定神经元与二值变量之间传统的逐一映射关系。这允许更细粒度的建模,其中每个不稳定神经元平均对应少于一个二值变量,从而从源头降低验证复杂度。基于 SART,我们推导出完整验证所需二值变量数量的理论下界,并在假设 $P \neq NP$ 的前提下证明:最后一层的变量可压缩 50%,而中间层的变量数量无法进一步减少。为克服明显的“仅限最后一层”局限,我们将验证重构为序列过程,并且关键地表明该增益可提升至整个网络:LayerABS 是一种基于 SART 的渐进收紧验证器,它迭代地将中间层视为临时最后一层,并传播紧致边界,从而缩小全局搜索空间和二值变量数量。此外,我们揭示了一条影响验证复杂度的结构规律:当不稳定神经元权重的符号满足数值对称性,即正负权重相等或至多相差一时,最坏情况验证复杂度达到理论最优,这为设计验证友好的架构提供了理论指导。作为通用的底层编码,SART 的价值独立于具体算法。
中文由 AI 翻译,仅供参考,以原文为准。
来源:arXiv · Neural and Evolutionary Computing · arxiv.org