文章/答案/技术大牛

发布

社区首页 >专栏 >ASE 2022 用于类比神经网络鲁棒性验证的可证更严格的近似值方法

ASE 2022 用于类比神经网络鲁棒性验证的可证更严格的近似值方法

CV君

发布于 2022-11-28 09:24:15

8590

文章被收录于专栏：我爱计算机视觉我爱计算机视觉

▌1 引言

该论文是关于神经网络鲁棒性理论类的文章。类似有Sigmoid激活函数的神经网络，由于其非线性，使得在进行神经网络鲁棒验证评估时，不可避免地会引入了不精确性。

当前的一个研究方向是寻找更严格的近似值以获得更精确的鲁棒验证结果。然而，现有的紧密度定义是启发式的，缺乏理论基础。在该论文中，作者对现有的神经元紧密度表征进行了全面的实证分析，并揭示它们仅在特定的神经网络上具有优势。

另外，作者基于神经网络紧密度的概念重新提出了一个统一的神经网络紧密度定义，并表明计算神经网络紧密度是一个复杂的非凸优化问题。为了能够更好地理解该论文原理，文末给出了论文中一些原理示例的相关代码。

论文链接： https://arxiv.org/abs/2208.09872

▌2 预备知识

神经网络是遵循逐层传播的，输入层上的每个神经元都接受一个输入值，该输入值乘以权重系数，然后传递给下一层的后续神经元。所有传入的数字相加。总和被馈送到激活函数

$\sigma$

，并且

$\sigma$

的输出与偏差

$b$

相加。然后将结果传播到下一层，直到到达输出层。

给定一个

$k$

层神经网络

$f:\mathbb{R}^n\rightarrow \mathbb{R}^m$

，即

$f^k\circ \sigma^{k-1}\circ\cdots\circ\sigma^1\circ f^1$

，其中

$\sigma^t$

是一个第

$t$

层非线性可微激活函数。

$f^t$

可以是仿射变换或卷积操作中的其中一个：

$\begin{array}{lr}f(x)=W x + b, & (\mathrm{Affine\text{ } Transformation}) \\ f(x)=W * x + b, & (\mathrm{Convolutional \text{ } Operation}) \end{array}$

其中

$W$

，

$b$

和

$*$

分别表示权重矩阵，偏置向量和卷积操作。在该论文中，作者主要关注的是

$\mathrm{Sigmoid}$

，

$\mathrm{Tanh}$

和

$\mathrm{Arctan}$

的激活函数如下所示：

$\sigma(x)=\frac{1}{1+e^{-x}},\quad \sigma(x)=\mathrm{Tanh}(x)=\frac{e^x-e^{-x}}{e^x+e^{-x}},\quad \sigma(x)=\mathrm{arctan}^{-1}(x)=\mathrm{Arctan}(x)$

神经网络

$f$

的输出是一个

$m$

维的值为

$0$

到

$1$

之间的向量，每一个维度其对应的是属于该类别的概率。令

$S$

是一个

$m$

类分类标签集合，

$\mathcal{L}(f(x))$

表示的是输入

$x$

的输出标签

$\mathcal{L}(f(x))=\arg\max\limits_{s \in \mathcal{S}}f(x)[s]$

上公式直观地发现，

$\mathcal{L}(f(x))$

返回了一个集合

$S$

中的标签

$s$

，

$f(x)[s]$

是个输出向量中最大值。

因为神经网络本质上是由计算机通过根据训练数据微调网络中的权重而组成的“程序”。与程序员开发的手工程序不同，神经网络缺乏形式化表示，几乎无法解释，这使得形式化和验证其属性非常具有挑战性。如果对神经网络的输入的合理扰动不会改变分类结果，则神经网络该扰动是鲁棒的。扰动通常通过扰动输入

$x$

和原始输入

$x$

之间的距离来测量，使用

$\ell_p$

范数来表示，其中

$p$

可以是

$1$

、

$2$

或

$\infty$

。一般的情况情况下，使用的度量范数是

$\ell_\infty$

。

神经网络的鲁棒性可以通过界

$\epsilon$

进行量化截断，

$\epsilon$

是一个安全的扰动距离，使得任何低于

$\epsilon$

的扰动都具有与神经网络的原始输入相同的分类结果。

定义1（局部鲁棒性）： 给定一个神经网络，一个输入和一个在下的边界。关于是鲁棒的，当且仅当对每个成立，使得。这样的被称为认证下界。

验证

$f$

的鲁棒性有如下两个问题：

需要证明对于每个

$x$

满足

$\|x − x_0\|_p \le \epsilon$

，则有

$f_{s_0}(x)-f_s(x)>0$

其中对于每个

$s\in \mathcal{S} − \{s_0\}$

成立，其中

$𝑠_0 = \mathcal{L}(f(x_0))$

，且

$f_s(x)$

返回概率

$P(\mathcal{L}(f(x)) = s)$

，即将

$x$

分类到类别

$s$

中；

计算可验证的下界，一个大的可验证的下界意味着更精确的鲁棒性验证结果。由于约束的非线性，会导致直接计算

$\epsilon$

很困难，大多数最先进的方法都采用高效的二分搜索算法。

由于包含非线性激活函数，所以神经网络

$f$

是高度非线性的。证明公式

$f_{s_0}(x)-f_s(x)>0$

的计算成本很高，即使对于最简单的全连接

$\mathrm{ReLU}$

网络也是NP-hard的。目前已经研究了许多方法来提高验证效率的，但同时也牺牲了完整性。具有代表性的方法包括区间分析、解释中的抽象和输出范围估计等。这些方法的基础技术是使用线性约束来过度逼近非线性激活函数，这可以比原始约束更有效地解决计算复杂度的问题。

基于近似的方法不是直接证明公式

$f_{s_0}(x)-f_s(x)>0$

，而是通过两个线性约束过度近似

$f_{s_0}(x)$

和

$f_s(x)$

，并证明

$f_{s_0}(x)$

的线性下界

$f_{L,s_0}(x)$

是大于

$f_s(x)$

的线性上界

$f_{U,s}(x)$

。显然，

$f_{L,s_0}(x)-f_{U,s}(x)>0$

是公式

$f_{s_0}(x)-f_s(x)>0$

的充分条件，证明或反证的效率明显更高。

定义2（上下线性界）： 令是在区间的非线性函数。已知系数，则有

$h_U(x)=\alpha_U x+\beta_U,\quad h_L(x)=\alpha_L x +\beta_L$

当以下条件成立时

$\forall x \in [l,u],\quad h_L(x)\le \sigma(x) \le h_U(x)$

$则h_U(x)$

和

$h_L(x)$

分别是

$\sigma(x)$

的上下线性界。

使用线性上下界过度逼近非线性激活函数是神经网络逼近的关键。对于区间

$[l,u]$

上的每个激活函数

$\sigma$

，作者定义了一个线性上界

$h_U$

和一个线性下界

$h_L$

以确保对于区间

$[l,u]$

中的所有

$x$

，使得

$\sigma(x)$

包含在

$[h_L(x), h_U(x)]$

。给定定义 1中的输入范围，网络的输出范围是通过传播每个网络的输出区间来计算的定义2中的神经元到输出层。

如下图所示考虑一个简单基于近似验证神经网络的示例，最初的验证问题是证明对于任何输入

$(x_1,x_2)$

，其中

$x_1\in[-1,1]$

和

$x_2\in[-1,1]$

，它总是被分类为神经元标签

$x_5$

。这相当于证明辅助神经元的输出

$x_7 = (x_5 −x_6)$

总是大于

$0$

。作者定义线性上/下界

$x_{U,3}, x_{L,3}$

和

$x_{U,4}, x_{L,4}$

分别近似神经元

$x_3$

和

$x_4$

。

由上图可知，

$x_{L,5}-x_{U,6}$

的输出区间为

$[0.177, 5.817]$

，从而证明网络对所有输入在

[- 1, 1] \times [- 1, 1]

$[−1, 1] \times [−1, 1]$

区间中是鲁棒的。

需要注意的是也可以考虑由一系列线段组成的分段线性边界来更紧密地逼近激活函数。然而，这种分段方式会导致约束的数量在逐层传播时呈指数级增长。这将大大降低验证的可扩展性。因此，使用一个线性上界和一个线性下界逼近激活函数是基于逼近的鲁棒性验证方法的最有效和广泛采用的选择。

▌3 神经网络紧密近似

在更严格的近似会产生更精确的验证结果的假设下，现有的紧密度表征是一种启发式的方法。但现有例子表明这个假设并不总是成立。这意味着定义每个单独神经元的紧密度对于实现紧密近似既不充分也不必要。那是因为神经元上的紧密度不能保证神经网络的输出间隔总是精确的。

但是，输出区间是判断网络是否鲁棒的基础。为了表征神经网络中激活函数的近似紧密度，作者引入了神经网络紧密度的概念，确保通过对激活函数的网络方式更紧密的逼近，使得神经网络产生更精确的输出间隔，从而产生更精确的验证结果。

定义3（神经网络紧密度）： 给定神经网络，。令是的线性近似，且和分别表示的上下界。如果是神经网络的最紧密逼近，则对于任意不同的线性逼近有

$\forall s \in S,\quad \min\limits_{x \in \mathbb{B}_p(x_0,\epsilon)}f_{L,s}(x)\ge \min\limits_{x\in\mathbb{B}_p(x_0,\epsilon)}\hat{f}_{L,s}(x)$

$\forall s \in S,\quad \max\limits_{x \in \mathbb{B}_p(x_0,\epsilon)}f_{U,s}(x)\le \max\limits_{x\in\mathbb{B}_p(x_0,\epsilon)}\hat{f}_{U,s}(x)$

其中

$f_{L,s}(x)$

和

$f_{U,s}(x)$

分别表示

$f_L(x)$

和

$f_U(x)$

的第

$s$

个元素。

定理1： 由定义3可知，如果比更紧密，则神经网络的近似比有更精确的鲁棒性。

证明： 令

$s_0=\mathcal{L}(f(x_0))$

有固定的扰动

$\epsilon$

。需要验证对于任意

$s$

有以下不等式成立

$\min\limits_{x\in\mathbb{B}_p(x_0,\varepsilon)} f_{L,s_0}(x)>\max\limits_{x\in\mathbb{B}_p(x_0,\varepsilon)}f_{U,s}(x)$

根据定义3可知，可得以下不等式

$\min\limits_{x\in\mathbb{B}_p(x_0,\varepsilon)} f_{L,s_0}(x)\ge \min\limits_{x\in\mathbb{B}_p(x_0,\varepsilon)} \hat{f}_{L,s_0}(x)>\max\limits_{x\in\mathbb{B}_p(x_0,\varepsilon)} \hat{f}_{U,s}(x)\ge \max\limits_{x\in\mathbb{B}_p(x_0,\varepsilon)} f_{U,s}(x)$

显然可知

$(f_L,f_U)$

是比

$(\hat{f}_L,\hat{f}_U)$

更紧密的近似。

给定一个

$k$

层神经网络

$f:\mathbb{R}^n \rightarrow \mathbb{R}^m$

，使用

$\phi_t$

来表示在应用第

$t$

个激活函数之前

$f$

层的复合函数，即

$\phi^t = f^t \circ \sigma^{t-1}\circ f^{t-1}\circ \cdots \circ \sigma^1 \circ f^1$

第

$t$

层有

$n^t$

个神经元，

$\phi^t_r(x)$

表示输出的第

$r$

个元素。对于每个激活函数

$\sigma(x),x\in[l,u]$

，其上和下线性界分别为

$h_U(x)=\alpha_Ux+\beta_U$

和

$h_L(x)=\alpha_Lx+\beta_L$

。然后可以将计算神经网络最紧密近似的问题形式化为以下优化问题：

$\begin{aligned}&\max\left(\min\limits_{x\in \mathbb{B}_\infty(x_0,\epsilon)}(A^k_{L,s}x+B^k_{L,s})\right)\\&\min\left(\max\limits_{x\in \mathbb{B}_\infty(x_0,\epsilon)}(A^k_{U,s}x+B^k_{U,s})\right)\\&\mathrm{s.t.}\quad \forall r\in \mathbb{Z},1\le r\le n^t, \forall t\in \mathbb{Z}, 1 < t < k \end{aligned}$

$\left\{\begin{aligned}&a^t_{L,r}z_r^t +\beta^t_{L,r}\le \sigma\\&\min\limits_{x\in\mathbb{B}_\infty(x_0,\epsilon)}A^t_{L,r}x+B^t_{L,r}\le z^t_r \le \max\limits_{x\in\mathbb{B}_\infty(x_0,\epsilon)}A_{U,r}^t x+B^t_{U,r}\end{aligned}\right.$

其中

$A^t_{L,r}x+B^t_{L,r}$

和

$A^t_{U,r}x+B^t_{U,r}$

分别表示

$\phi^t_r(x)$

的上下界，且

$A^t_{L,r}$

，

$A^t_{U,r}$

，

$B^t_{L,r}$

和

$B^t_{U,r}$

表示定义在权重

$W^t$

和偏置

$b^t$

的常数值，具体的定义如下所示：

$A^t_{L,r}=\left\{\begin{array}{lr}W^t_r,&t=1\\W^t_{\ge 0}\alpha^{t-1}_L \odot A^{t-1}_L+W^t_{<0,r}\alpha_U^{t-1}\odot A^{t-1}_L,&t \ge 2\end{array}\right.$

$B_{L,r}^t=\left\{\begin{array}{lr}b_r^t,&t=1\\W_{\ge 0,r}^t(\alpha^{t-1}_L\odot B^{t-1}_L+\beta_L^{t-1})+&\\W^{t}_{<0,r}(\alpha_U^{t-1}\odot B^{t-1}_L\odot+\beta^{t-1}_L)+b_r^t,&t \ge 2\end{array}\right.$

$A^t_{U,r}=\left\{\begin{array}{lr}W^t_r,&t=1\\W^t_{\ge 0}\alpha^{t-1}_U \odot A^{t-1}_U+W^t_{<0,r}\alpha_L^{t-1}\odot A^{t-1}_U,&t \ge 2\end{array}\right.$

$B_{L,r}^t=\left\{\begin{array}{lr}b_r^t,&t=1\\W_{\ge 0,r}^t(\alpha^{t-1}_U\odot B^{t-1}_U+\beta_U^{t-1})+&\\W^{t}_{<0,r}(\alpha_L^{t-1}\odot B^{t-1}_U\odot+\beta^{t-1}_U)+b_r^t,&t \ge 2\end{array}\right.$

需要注意的是，以上优化形式可能无法保证单个激活函数的近似值相对于现有的紧密度定义是最紧密的。

▌4 近似单隐层网络

对于单层网络，优化问题可以进一步简化如下：

$\max\left(\min\limits_{x\in\mathbb{B}_\infty(x_0,\epsilon)}(A_{L,s}x+B_{L,s})\right),\quad \min\left(\max\limits_{x\in\mathbb{B}_\infty(x_0,\epsilon)}(A_{U,s}x+B_{U,s})\right)$

$\mathrm{s.t.}\text{ } \left\{\begin{aligned}&\alpha_{L,r}z_r+\beta_{L,r}\le \sigma(z_r)\le \alpha_{U,r}z_r+\beta_{U,r},\\&\min\limits_{x\in\mathbb{B}_\infty(x_0,\epsilon)}W^1 x+b^1 \le z_r \le\max\limits_{x\in\mathbb{B}_\infty(x_0,\epsilon)}W^1x+b^1, \\&\forall r \in \mathbb{Z},\quad 1\le r\le n.\end{aligned}\right.$

其中

$A_{L,s}=W^2_{\ge 0,s}(\alpha_L \odot W^1)+W^2_{<0,s}(\alpha_U \odot W^1)$

，

$B_{L,s}= W^2_{\ge 0,s}(\alpha_L\odot b^1+\beta_L)+W^2_{<0,s}(\alpha_U\odot b^1+\beta_U)+b^2_s$

，

$n$

表示的是隐层的数量。

优化问题是一个凸变体，因此可以通过利用基于梯度下降的搜索算法来求解该问题，以下算法流程图为计算单隐层近似相关算法的伪代码。对于隐层神经元上的每个激活函数，首先确定穿过两个端点的线

$\omega$

可以是上线性界还是下线性界。然后选择激活函数的切线作为上线性界或下线性界，其截断点可以是优化变量。最后用梯度下降法去优化目标函数，并进一步更新系数

$\alpha_L$

，

$\alpha_U$

，

$\beta_L$

和

$\beta_U$

。

对于具有两个或更多隐层的神经网络，由于其非凸性使得求解相关的优化问题而变得不切实际。对于任何隐藏层，激活函数的输入间隔都受到前一个隐藏层激活函数的近似值的约束。在该论文中，作者提出了可计算的神经元最紧密近似，并确定了当神经网络中的所有权重都为非负时，神经元最紧密近似导致网络最紧密。

▌5 实验结果

如下表格所示为没有非负权重的Sigmoid模型的对比结果。在关于精度验证结果中，论文中提出的NEWISE计算可验证下界方法要比所有其它方法都要出色。尤其是针对于在Fashion Mnist数据集的训练出的模型，该方法甚至一度实现了验证结果高达 96.22%的精度。另外，NEWISE也相应对标准差的精度提高了129.33%。这也表明，跟其它方法相比，论文的方法可以对输入更加敏感。

如下表格所示为不同评估方法在具有混合权重的Sigmoid激活关于全连接神经网络和卷积神经网络对比结果。依然可以发现论文中提出的NEWISE计算可验证下界方法要比所有其它方法在提高评估精度和标准差方面都要出色。

▌6 实验程序

以下两个程序分别画出了单个sigmoid函数上下线性界以及论文中实例2的示意图。

from matplotlib import pyplot as plt
import numpy as np 
x = np.linspace(-10,10,10000)
Sigmoid_x = 1/(1 + np.exp(-x))
X_U3 = 0.104 * x + 0.670
X_L3 = 0.104 * x + 0.329
plt.plot(x, Sigmoid_x, label='Sigmoid(x)')
plt.plot(x, X_U3, label='X_U3')
plt.plot(x, X_L3, label='X_L3')
plt.xlabel('x')
plt.ylabel('y')
plt.legend(loc='best') 
# # plt.text(-0.5,3,r"$Loss=(w^8 - 1)^2$",fontsize=20,color="red")
plt.show()

以下两个程序分别画出了单个arctan函数上下线性界以及论文中关于arctan实例的示意图。

import numpy as np 
import mpl_toolkits.axisartist as ast 
from matplotlib import pyplot as plt 
from mpl_toolkits.mplot3d import Axes3D
data = np.linspace(-1, 1, 20)
x1, x2 = np.meshgrid(data, data)
x3_sigmoid = 1 / (1 + np.exp(-x1 - x2))
xu3 = 0.104 * (x1 + x2) + 0.670
xl3 = 0.104 * (x1 + x2) + 0.329
x4_sigmoid = 1 / (1 + np.exp(-x1 + x2))
xu4 = 0.104 * (x1 - x2) + 0.670
xl4 = 0.104 * (x1 - x2) + 0.329
x5 = 2 * x3_sigmoid + 2 * x4_sigmoid
xu5 = 2 * xu3 + 2 * xu4
xl5 = 2 * xl3 + 2 * xl4
x5 = 2 * x3_sigmoid + 2 * x4_sigmoid
x6 = 3 * x3_sigmoid - 5 * x4_sigmoid
xu6 = 3 * xu3 - 5 * xl4
xl6 = 3 * xl3 - 5 * xu4 
x7 = xl5 - xu6
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.plot_surface(x1, x2, x7)
# ax.plot_surface(x1, x2, xu6)
# ax.plot_surface(x1, x2, xl6)
# ax.plot_surface(x1, x2, xl5)
# ax.plot_surface(x1, x2, x5)
plt.show()

from matplotlib import pyplot as plt
import numpy as np 
x = np.linspace(-3,-1,10000)
Arctan_x = np.arctan(x)
X_U3 = 0.232 * x - 0.554
X_L3 = 0.200 * x - 0.707
plt.plot(x, Arctan_x, label='Arctan(x)')
plt.plot(x, X_U3, label='X_U3')
plt.plot(x, X_L3, label='X_L3')
plt.xlabel('x')
plt.ylabel('y')
plt.legend(loc='best') 
# # plt.text(-0.5,3,r"$Loss=(w^8 - 1)^2$",fontsize=20,color="red")
plt.show()

import numpy as np 
import mpl_toolkits.axisartist as ast 
from matplotlib import pyplot as plt 
from mpl_toolkits.mplot3d import Axes3D
data1 = np.linspace(-2, -1, 20)
data2 = np.linspace(-1, 0, 20)
x1, x2 = np.meshgrid(data1, data2)
x3_arctan = np.arctan(x1 + x2)
xu3 = 0.232 * (x1 + x2) - 0.554
# xl3 = 0.200 * (x1 + x2) - 0.707
xl3 = 0.100 * (x1 + x2) - 0.949
x4_arctan = np.arctan(x1 - x2)
xu4 = 0.554 * (x1 - x2) 
# xl4 = 0.500 * (x1 - x2) - 0.285
xl4 = 0.200 * (x1 - x2) - 0.707
x5 =  x3_arctan + 2 * x4_arctan
xu5 = xu3 + 2 * xu4
xl5 = xl3 + 2 * xl4
x6 = - x3_arctan + 2 * x4_arctan
xu6 = - xl3 + 2 * xu4
xl6 = - xu3 + 2 * xl4 
x7 = xl5 - xu6
print(x7.max())
print(x7.min())
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
x8 = 0 *(x1 + x2)
ax.plot_surface(x1, x2, x7)
ax.plot_surface(x1, x2, x8)
# ax.plot_surface(x1, x2, xl6)
# ax.plot_surface(x1, x2, xl5)
# ax.plot_surface(x1, x2, x5)
plt.show()