神经网络鲁棒性验证的理论框架与计算复杂度分析
Robustness Verification in Neural Networks
AI 导读
该论文研究神经网络计算的形式化验证问题，涵盖鲁棒性与最小化问题，如网络是否对所有有效输入都产生有效输出、两个网络是否计算同一函数等。作者提出一个理论框架，可交换神经网络的安全性与效率问题并分析其计算复杂度。结果表明在分段线性激活函数及使用求和或最大度量时，多数问题处于 P 或至多 NP 复杂度。
正文 · 原文
Abstract:In this paper we investigate formal verification problems for Neural Network computations. Of central importance will be various robustness and minimization problems such as: Given symbolic specifications of allowed inputs and outputs in form of Linear Programming instances, one question is whether there do exist valid inputs such that the network computes a valid output? And does this property hold for all valid inputs? Do two given networks compute the same function? Is there a smaller network computing the same function?
The complexity of these questions have been investigated recently from a practical point of view and approximated by heuristic algorithms. We complement these achievements by giving a theoretical framework that enables us to interchange security and efficiency questions in neural networks and analyze their computational complexities. We show that the problems are conquerable in a semi-linear setting, meaning that for piecewise linear activation functions and when the sum- or maximum metric is used, most of them are in P or in NP at most.
| Comments: | 16 pages, 1 figure, v2: corrected typo in the title |
| Subjects: | Artificial Intelligence (cs.AI); Machine Learning (cs.LG) |
| Cite as: | arXiv:2403.13441 [cs.AI] |
| (or arXiv:2403.13441v2 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2403.13441 arXiv-issued DOI via DataCite |
|
| Journal reference: | CPAIOR 2024, LNCS 14743, Springer, pp. 263-278 |
| Related DOI: | https://doi.org/10.1007/978-3-031-60599-4_18
DOI(s) linking to related resources |
Submission history
From: Adrian Wurm [view email]
[v1]
Wed, 20 Mar 2024 09:34:38 UTC (74 KB)
[v2]
Tue, 10 Nov 2026 13:39:14 UTC (74 KB)
来源：arXiv cs.AI · arxiv.org