arXiv cs.AI· Adrian Wurm·· 10 小时前AI 评分26
神经网络鲁棒性验证的计算复杂性理论框架
Robustness Verification in Neural Networks
AI 导读
研究者为神经网络形式化验证建立理论框架，将安全性与效率问题相互转化并分析其计算复杂性。结果表明，在分段线性激活函数配合求和或最大值度量时，鲁棒性、网络等价性及最小化网络等问题大多属于 P 或至多 NP 类。该工作为近期依赖启发式算法近似求解的验证问题补上了复杂性理论依据。
正文 · AI 翻译
摘要：本文研究神经网络计算的形式化验证问题。其中最为重要的是各种鲁棒性与最小化问题，例如：给定以线性规划实例形式表示的允许输入与输出的符号化规范，一个问题是是否存在合法输入使得网络计算出合法输出？并且该性质是否对所有合法输入都成立？两个给定的网络是否计算同一个函数？是否存在一个更小的网络计算同一个函数？
这些问题的时间复杂度近来已从实用角度得到研究，并通过启发式算法加以近似。我们通过给出一个理论框架来补充这些成果，该框架使我们能够互换神经网络中的安全性与效率问题，并分析它们的计算复杂度。我们证明这些问题在半线性设定下是可解的，即对于分段线性激活函数，并且当使用和度量或最大值度量时，其中大多数问题属于 P 类，至多属于 NP 类。
| 评论： | 16 页，1 幅图，v2：修正了标题中的拼写错误 |
| 主题： | 人工智能（cs.AI）；机器学习（cs.LG） |
| 引用为： | arXiv:2403.13441 [cs.AI] |
| （或使用 arXiv:2403.13441v2 [cs.AI] 查看此版本） | |
| https://doi.org/10.48550/arXiv.2403.13441 由 DataCite 颁发的 arXiv DOI |
|
| 期刊 参考文献： | CPAIOR 2024, LNCS 14743, Springer, pp. 263-278 |
| 相关 DOI： | https://doi.org/10.1007/978-3-031-60599-4_18
链接到相关资源的 DOI |
提交历史
来自：Adrian Wurm [查看电子邮件]
[v1]
2024 年 3 月 20 日星期三 09:34:38 UTC（74 KB）
[v2]
2026 年 11 月 10 日星期二 13:39:14 UTC（74 KB）
来源：arXiv cs.AI · arxiv.org