在这项工作中，我们提出了一个严格的理论框架，解决人工智能安全的基础问题——对抗鲁棒性。具体来说，我们展示了对抗鲁棒性问题可以简化为格遍历问题。该格的每个元素对应一个区间，即包含输入点 $\mathbf{x}$ 的轴对齐超矩形。
考虑一个多层感知机分类器（MLP）。如果 $\mathbf{x} \in I$ 并且 $\mathbf{x}$ 可以在区间 $I$ 中自由扰动而不改变 MLP 的预测，则区间 $I$ 构成一个有效认证。相反，如果 $\mathbf{x} \in I$ 而当 $\mathbf{x}$ 移动到 $I$ 之外时，MLP 的预测必定会改变，则区间 $I$ 构成一个完整认证。
有效认证问题对应于广泛研究的对抗鲁棒性，而完整认证在文献中尚未得到研究。我们开发了格遍历算子，并在精炼与验证的迭代方案中应用它们。使用正式的 MLP 验证器，确保了有效最大性和完整最小性。
此外，我们还研究了目标优化问题，发现了一些有趣的非对称性。对于完整认证，最小解可以在多项式 oracle 调用中获得，而对于有效认证，则证明了强不可解性结果。此外，我们还考察了对称区间（即 $\ell_\infty$-球体）中的优化问题，提供了对数算法。最后，我们使用新颖的 ParallelepipedoNN 系统进行了实证评估。
博主点评： 本文通过将对抗鲁棒性问题与格遍历相结合，为多层感知机的认证提供了新的视角和有效工具。尤其是完整认证的探索，填补了现有文献的空白，具有重要的理论及应用价值。