通过格遍历的多层感知机区间认证

# 多层感知机区间认证的格遍历方法
来源: https://arxiv.org/html/2607.08773

11institutetext:研究与技术基金会 — 赫拉斯，伊拉克利翁，希腊
11email:{mercoyris,varsosk,fgeo}@ics.forth.gr
22institutetext:克里特大学，伊拉克利翁，希腊
33institutetext:加泰罗尼亚高等研究机构，巴塞罗那，西班牙
33email:[email protected]
44institutetext:莱里达大学，莱里达，西班牙

###### 摘要

在本文中，我们针对人工智能安全的基础问题——**对抗鲁棒性**，提出了一个严谨的理论框架。具体而言，我们证明对抗鲁棒性问题可以归结为**格遍历**问题。该格的每个元素对应一个**区间**，即一个包含输入点 x\mathbf{x} 的轴对齐超矩形。考虑一个**多层感知机（MLP）分类器**。若 x∈I\mathbf{x}\in I 且 x\mathbf{x} 可在 II 内自由扰动而不改变 MLP 的预测，则区间 II 构成一个**可靠认证**。相应地，若 x∈I\mathbf{x}\in I 且当 x\mathbf{x} 移出 II 时 MLP 的预测必然改变，则区间 II 构成一个**完全认证**。虽然可靠认证问题对应着已被充分研究的对抗鲁棒性，但完全认证未有文献探讨。我们开发了格遍历算子，并将其应用于“细化与验证”迭代方案。通过使用形式化的 MLP 验证器，我们保证了可靠最大性和完全最小性。此外，我们研究了目标优化问题，并发现了一些有趣的非对称性。对于完全认证，可通过多项式次数的 Oracle 调用获得最小解。但对于可靠认证则不然，我们证明了强**难解性**结果。另外，我们研究了**对称**区间（即 l∞\ell_{\infty} 球）上的优化问题，并给出了对数级算法。最后，我们利用新颖的 ParallelepipedoNN111https://github.com/merkouris148/parallelepipedonn 系统进行了实证评估。

## 1 引言

人工智能，主要受深度神经网络 (NN) 驱动，正迅速成为我们日常生活的一部分，从媒体平台的推荐系统[39]到大型语言模型聊天机器人[4]。尽管取得了这些成就，但 NN 有望通过取代人类在关键决策领域（如驾驶[18]、医疗[21]或政府管理[40]）实现更大的突破。然而，NN 是脆弱的，意味着微小、通常不可察觉的输入扰动就能翻转其预测。这些输入通常被称为**对抗样本**[9, 24, 31]。确保神经网络对对抗攻击的**鲁棒性**仍然是人工智能安全的一个持续问题。

该领域的最早工作侧重于利用梯度信息生成对抗样本，随后将其融入学习过程，例如[9, 23]。尽管如此，这些初步尝试未能根本上解决该问题[37]。更复杂的方法利用了 NN 的凸松弛[6]，将对抗鲁棒性转化为一个凸优化问题。该问题可直接求解[12, 17, 19]或通过其对偶形式求解[33]。然而，这一系列方法由于依赖于原始问题的松弛，精度较低[25, 29]。对抗鲁棒性的难度源于 NN 的表示，似乎深深植根于其计算特性。NN 的激活函数引入了非线性，只能通过整数约束来研究。因此，NN 只能被准确描述为**混合整数线性规划 (MILP)**[13]。NN 的 MILP 描述使得构建可靠且完备的 NN 验证器（例如 Marabou[15, 34]）成为可能，改进了早期基于**可满足性模理论 (SMT)** 的方法（如 Reluplex[14]）。形式化 NN 验证器可证明 σ(X)=Y\sigma(X)=Y，其中 X,YX,Y 为输入/输出集，σ(⋅)\sigma(\cdot) 为给定 NN。若性质不成立，它们会提供一个**反例**，即某个 x∈X\mathbf{x}\in X，使得 σ(x)∉Y\sigma(\mathbf{x})\notin Y。然而，这种精度是有代价的。验证 NN 上的性质是 **NP-难**的[14]。此外，验证给定区域没有对抗样本并不存在近似算法[38]。

本文旨在对鲁棒性认证进行详细的形式化分析。我们的工作不同于以往的尝试[12, 17, 19, 33]，从根本上更一般地考虑了该问题。我们考虑**区间**认证族，即包含给定输入 x\mathbf{x} 的轴对齐超矩形。据我们所知，这是文献中考虑的最一般的认证族[12, 17]。利用 Sunaga 的区间代数[30]，我们证明了区间认证空间组织成一个**不可数的完备格**。我们引入一组**格遍历算子**，使得能够系统性地探索该空间。然后，将这些算子应用于“细化与验证”迭代方案，以计算**最大可靠**和**最小完全**的区间认证。若 x∈I\mathbf{x}\in I 且 x\mathbf{x} 可在 II 内任意变化而不改变模型预测，则区间 II 构成**可靠认证**。对偶地，若 x∈I\mathbf{x}\in I 且任何将 x\mathbf{x} 移出 II 的移动都必然改变预测，则 II 是**完全认证**。最小性和最大性是相对于集合包含关系定义的。现有方法[12, 17, 19, 33]计算可靠认证，**但不保证**最大性。此外，据我们所知，完全认证在文献中尚未被考虑过。

我们进一步研究了区间认证上的优化问题，重点关注**最小边长**目标，这在前人工作中广泛使用[17, 19, 33]。与现有方法相比，我们的方法为我们的认证提供了**非平凡性保证**。即，在某些假设下，我们的算法可以**判定**给定优化问题是否存在非平凡解。现有方法由于依赖松弛，缺乏这一核心功能。我们在表格1中提供了现有工作与我们的定性比较。最后，我们强化了已知的难解性结果，表明计算最优可靠区间认证不能在输入维度、验证调用次数和每次验证调用时间的多项式时间内实现。

| 工作 | MLP表示 | 认证类型 | 可靠 | 最大/最小 | 目标 | 非平凡解 |
|---|---|---|---|---|---|---|
| Wong 等人[33] | 对偶 | 均匀 | ✓ | ✗ | ✗ | α/A\alpha/\mathcal{A} | ✗ |
| Liu 等人[19] | 对偶 | 对称 | ✓ | ✗ | ✗ | α\alpha | ✗ |
| Li 等人[17] | 凸 | 一般 | ✓ | ✗ | ✗ | α\alpha | ✗ |
| Kabahala 等人[12] | MILP+凸 | 一般 | ✓ | ✗ | ✓ | A\mathcal{A} | ✗ |
| 本文 | MILP | 一般 | ✓ | ✓ | ✓ | α\alpha | ✓ |

表1: 将现有工作与 ParallelepipedoNN 进行比较。凸：主要凸近似。对偶：对偶凸近似。均匀：均匀区间，即 l∞\ell_{\infty} 球。对称：形如 [x−e,x+e][\mathbf{x}-\mathbf{e},\mathbf{x}+\mathbf{e}] 的对称区间。一般：一般区间。最后，用 α\alpha 表示最小边长，用 A\mathcal{A} 表示最大边长或**直径**。[12] 提供了最大解，但针对的是直径优化。[33] 研究均匀区间，因此对于 l∞\ell_{\infty} 范数，最小边长 α\alpha 和直径 A\mathcal{A} 重合。

**概述。** 在第2节中，我们介绍必要的预备知识。第3节开发了分析所需的区间代数，第4节探讨了区间认证空间的结构。第5节回顾了优化问题。最后，第6节介绍了 ParallelepipedoNN 系统并讨论了本工作的实际意义。

## 2 预备知识

在本节中，我们将回顾本文后续所需的一些基本概念和定义。对于任意自然数 d∈Nd\in\mathbb{N}，我们用 [d][d] 表示集合 {1,2,...,d}\{1,2,\dots,d\}。向量将用粗体表示，例如 x\mathbf{x}；标量用轻体表示，例如 xx。对于 dd 维向量 x\mathbf{x}，我们用 xix_i 表示其第 ii 个坐标。此外，令 f:R→Rf\colon\mathbb{R}\to\mathbb{R} 是一个以 x∈Rx\in\mathbb{R} 为输入的实际函数。对于向量输入 x∈Rd\mathbf{x}\in\mathbb{R}^d，我们用 f(x)∈Rd\mathbf{f}(\mathbf{x})\in\mathbb{R}^d 表示由 ff **导出的**向量函数，即 f(x)=(f(x1),...,f(xd))\mathbf{f}(\mathbf{x})=(f(x_1),\dots,f(x_d))。dd 维向量 0\mathbf{0} 和 1\mathbf{1} 分别表示零向量和全一向量。对于每个 i∈[d]i\in[d]，我们用 ei\mathbf{e}^i 表示一个向量，满足当 i≠ji\neq j 时 eji=0e^i_j=0，且 eii=1e^i_i=1。最后，矩阵 A∈Rd1×d2A\in\mathbb{R}^{d_1\times d_2} 用大写字母表示。

#### 赋范向量空间。
在本文中，我们关注 **实数域** R\mathbb{R} 上的 dd 维**赋范向量空间**。我们将使用 lp\ell_p 范数，记作 ‖x‖p\|\mathbf{x}\|_p，定义为 ‖x‖p=∑i∈[d]∣xi∣pp\|\mathbf{x}\|_p=\sqrt[p]{\sum_{i\in[d]}|x_i|^p}。在极限 p→∞p\to\infty 下，这简化为无穷范数 ‖x‖∞=maxi∈[d]∣xi∣\|\mathbf{x}\|_\infty=\max_{i\in[d]}|x_i|。用 Bp(x⋆,ρ)⊂Rd,ρ>0\mathcal{B}^p(\mathbf{x}^\star,\rho)\subset\mathbb{R}^d,\rho>0 表示围绕 x\mathbf{x}、半径为 ρ\rho（相对于 ∥⋅∥p\|\cdot\|_p 范数）的 dd 维球，即 Bp(x⋆,ρ)={x∈Rd∣‖x−x⋆‖p≤ρ}\mathcal{B}^p(\mathbf{x}^\star,\rho)=\{\mathbf{x}\in\mathbb{R}^d\mid \|\mathbf{x}-\mathbf{x}^\star\|_p\leq\rho\}。考虑一个集合 S⊆RdS\subseteq\mathbb{R}^d。用 ∂S\partial S 表示 SS 相对于度量 ∥⋅∥p\|\cdot\|_p 的**边界**，即 ∂S={x∈S∣∀ρ>0,Bp(x,ρ)∩(Rd∖S)≠∅}\partial S=\{\mathbf{x}\in S\mid \forall\rho>0,~~\mathcal{B}^p(\mathbf{x},\rho)\cap(\mathbb{R}^d\setminus S)\neq\emptyset\}。SS 的**内部**，记作 S∘S^\circ，由 SS 中不属于边界的点组成，即 S∘=S∖∂SS^\circ=S\setminus\partial S。集合 S⊆RdS\subseteq\mathbb{R}^d 相对于度量 ∥⋅∥p\|\cdot\|_p 是**开**的，如果对于每个 x∈S\mathbf{x}\in S，存在一个 ρ>0\rho>0 使得 Bp(x,ρ)⊆S\mathcal{B}^p(\mathbf{x},\rho)\subseteq S。集合 S⊆RdS\subseteq\mathbb{R}^d 是**闭**的，如果 Rd∖S\mathbb{R}^d\setminus S 是开的。集合 S⊆RdS\subseteq\mathbb{R}^d 称为**有界**的，如果存在某个有穷的 ρ>0\rho>0 使得 B∞(0,ρ)⊇S\mathcal{B}^\infty(\mathbf{0},\rho)\supseteq S。最后，闭且有界的集合是**紧**的。

#### 多层感知机。
MLP 是一个函数 σ:F→S\sigma\colon\mathbb{F}\to\mathbb{S}，其中 F⊂Rdin\mathbb{F}\subset\mathbb{R}^{d_{\text{in}}}，S⊂Rdout\mathbb{S}\subset\mathbb{R}^{d_{\text{out}}} 分别表示特征（输入）空间和得分（输出）空间。我们关注以**修正线性单元 (ReLU)**[7] 作为激活函数的 MLP。对于 x∈Rx\in\mathbb{R}，ReLU 函数 r(x)r(x) 定义为 r(x)=max(0,x)r(x)=\max(0,x)。在高维情况下，我们有 r(x)=(r(x1),...,r(xd))\mathbf{r}(\mathbf{x})=(r(x_1),\dots,r(x_d))。我们给出如下正式定义。

###### 定义1 (多层感知机)
一个**多层感知机** σ:F→S\sigma\colon\mathbb{F}\to\mathbb{S}，其中 F⊂Rdin,S⊂Rdout\mathbb{F}\subset\mathbb{R}^{d_{\text{in}}},\mathbb{S}\subset\mathbb{R}^{d_{\text{out}}}，被描述为元组 σ=⟨L,D,W,Q⟩\sigma=\langle L,D,W,Q\rangle。用 L∈NL\in\mathbb{N} 表示**层数**。用 DD 表示一个由 L+1L+1 个自然数组成的序列，其中 din=d0,d1,...,dL−1,dL=doutd_{\text{in}}=d_0,d_1,\dots,d_{L-1},d_L=d_{\text{out}}。用 WW 表示一个由 LL 个实数矩阵组成的序列，对于每个 i∈[L]i\in[L]，有 W(i)∈Rdi×di−1W^{(i)}\in\mathbb{R}^{d_i\times d_{i-1}}。最后，用 QQ 表示一个由 LL 个实数向量组成的序列，对于每个 i∈[L]i\in[L]，有 q(i)∈Rdi\mathbf{q}^{(i)}\in\mathbb{R}^{d_i}。对于输入 x∈F\mathbf{x}\in\mathbb{F}，σ(x)\sigma(\mathbf{x}) 的值由以下递归方程组中的 σ(L)\sigma^{(L)} 给出。

σ(0)=xσ(i)=r[W(i)σ(i−1)+q(i)],∀i∈[L]}\left.\begin{array}{ll}\sigma^{(0)}&=\mathbf{x}\\
\sigma^{(i)}&=\mathbf{r}[W^{(i)}\sigma^{(i-1)}+\mathbf{q}^{(i)}],\quad\forall i\in[L]\end{array}\right\}

对于**分类**问题，令 C⊂N\mathcal{C}\subset\mathbb{N} 是一个有穷的类别集合，且 ∣C∣=dout|\mathcal{C}|=d_{\text{out}}。一个分类器 κ:F→C\kappa\colon\mathbb{F}\to\mathcal{C} 相对于 MLP σ(⋅)\sigma(\cdot) 被构造为 κ(x)=argmaxi∈[dout]σi(x)\kappa(\mathbf{x})=\arg\max_{i\in[d_{\text{out}}]}\sigma_i(\mathbf{x})。