arXiv cs.AI· Brian Yarbrough, Jesse Wayment, Jingbo Wang, Philip E. Par\'{e}, Shreyas Sundaram·· 1 天前AI 评分31
Fit-LRP：为非凸区域神经网络验证拟合多面体线性松弛
Fit-LRP: Fitting Linear Relaxations to Polytopes for Neural Network Verification over Non-Convex Regions
AI 导读
Fit-LRP 框架通过对非凸多面体域（多面体并集）求解一系列小型低维线性规划，实现对仿射边界的精确优化，可直接增强 LiRPA 与 α,β-CROWN 分支定界（BaB）的最终优化步骤。在 ARCH-COMP 与神经 Lyapunov 基准上，该方法将最难区域的分支数减少 47 倍、最坏验证时间缩短 15 倍，配合区域划分在单 CPU 上比 GPU 上的 α,β-CROWN 快 6.1 倍。
正文 · AI 翻译
摘要：最先进的神经网络验证器在轴对齐边界框上评估线性松弛。然而，信息物理系统中的验证域很少是盒子。可达性规范、避障约束和神经 Lyapunov 证书通常产生斜向或非凸的多面体区域，基于盒子的边界在这些区域上变得极其宽松。本文提出 Fit-LRP（Fitting Linear Relaxations to Polytopes），一个通过在非凸域（由多面体并集表示）上求解一系列小型、低维线性规划来实现仿射边界精确优化的框架。我们的方法无缝增强了 LiRPA 和 $\alpha,\! \beta$-CROWN 分支定界（BaB）算法的最终优化步骤。在 BaB 验证中，用轴对齐分割近似斜向约束会导致严重的组合爆炸并有无法终止的风险。通过在精确的多面体状态空间约束上优化非线性函数的最终仿射边界，我们的方法消除了盒子引起的过度近似，从而实现更早的搜索树剪枝。在 ARCH-COMP 和神经 Lyapunov 基准上，Fit-LRP 将最难区域的分支减少了 $47\times$，将最坏情况验证时间缩短了 $15\times$，并且通过区域划分，在单个 CPU 上的验证速度比 GPU 上的 $\alpha,\! \beta$-CROWN 快 $6.1\times$。
| 学科： | 机器学习（cs.LG）；人工智能（cs.AI）；系统与控制（eess.SY）；优化与控制（math.OC） |
| ACM 分类： | I.2；F.3.1；G.1.6 |
| 引用为： | arXiv:2611.16003 [cs.LG] |
| （或 arXiv:2611.16003v1 [cs.LG] 为此版本） | |
| https://doi.org/10.48550/arXiv.2611.16003 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Brian Yarbrough [查看电子邮件]
[v1]
2026年11月11日星期三 21:05:13 UTC（170 KB）
来源：arXiv cs.AI · arxiv.org