arXiv cs.AI· Adrian Wurm·· 10 小时前AI 评分26
神经网络鲁棒性验证的计算复杂性理论框架
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