跳到主要内容
返回时间线
arXiv来源发表:

Hyperlyve把ReLU网络激活区域拆成并行子树,630万区域枚举不到16分钟

核心概要

Hyperlyve把深度ReLU网络诱导的激活区域枚举改成按隐藏层子树并行推进,并在每个仿射区域内对真实非线性动力学做可靠且完备的Lyapunov条件检验。此前同类枚举工具受逐神经元检查或网络展平拖累,在Rejoin RL的630万个8维区域上,RPM与Relucent均触发1小时超时,Hyperlyve在16分钟内完成。它还把连续分段仿射神经Lyapunov函数的验证问题刻画为co-NP完全,并嵌入反例引导的合成循环。

Source-provided article image: Hyperlyve: Parallelized Enumeration and Exact Lyapunov Stability Certification for Deep ReLU Networks
arXiv

深度剖析

Hyperlyve把深度ReLU网络诱导的超平面排列枚举拆成互不重叠的子树,让多个工作线程同时推进,而不需要全局共享队列。 此前的ReLU网络区域枚举要么卡在逐神经元评估上,要么依赖网络展平,难以并行;GPU加速的Berzins方法虽然并行度高,却只返回顶点,不给出区域稳定性检验所需的半空间描述。 在Rejoin RL网络上,Hyperlyve并行枚举630万个8维区域用时不到16分钟,RPM和Relucent在同一任务上都触发1小时超时;在ACAS Xu上,Hyperlyve用时8.0秒,RPM为350.2秒,Relucent为1212.3秒。

每个激活区域内的稳定性检验只针对该区域做分支定界,把Lyapunov网络本身的非线性从子问题里消掉,剩下的非线性只来自闭环动力学。 整体式完备验证器要同时界定Lyapunov网络与非线性动力学的复合,在整个域上界会迅速变松,触发大量分支;Hyperlyve改为逐区域推理,并用线性规划收紧LiRPA给出的仿射上界。 在AKP-10、AKP-100、IPNN、Lorenz、TLPRA以及SIS-3到SIS-10等系统上,Hyperlyve在多数算例中快于FOSSIL、LyZNet和Li等人的方法,并能在TLPRA上给出证书,而Li等人的方法在该系统上报错。

启示与展望

演示范围是紧凸多面体域内的连续时间动力学,Lyapunov函数取ReLU网络形成的连续分段仿射形式,控制器为预先训练好的网络;实验在AMD EPYC 7763 64核处理器上完成,未使用GPU,单次运行限时1小时。

最坏情况下算法仍是指数时间,因为所处理的两个判定问题都是co-NP完全的;分支定界的终止没有与输入无关的有限最坏情况保证;原点附近需要排除一个小球以避开浮点容差,证书因此不覆盖该球内。