网络素描：在深度卷积神经网络中利用二元结构

Abstract

具有深度架构的卷积神经网络（CNN）极大地推动了计算机视觉任务的最先进技术水平。然而，深度网络通常资源密集，因此在移动设备上部署困难。近年来，具有二值权重的 CNN 因其显著的效率优势引起了广泛关注，但在实际应用中，此类模型的准确性往往不尽如人意。在本文中，我们提出“网络素描”（network sketching）这一新技术，用于构建二值权重 CNN，旨在实现更准确的推理并在实际应用中取得更好的权衡效果。我们的基本思想是直接在预训练的滤波器组中利用二值结构，并通过张量扩张生成二值权重模型。整个过程可视为一种由粗到细的模型近似方法，类似于铅笔素描中先勾勒轮廓、后添加阴影的步骤。为了进一步加速生成的模型（即“素描”），我们还提出了一种二值张量卷积的关联实现方式。实验结果表明，在对 ImageNet 大规模分类任务中，经过适当处理的 AlexNet（或 ResNet）的素描模型在性能上大幅优于现有的二值权重模型，而用于存储网络参数的内存开销仅略有增加。

1. Introduction

近年来，研究者设计了具有二值权重的卷积神经网络（CNN）以解决这一问题。通过将连接权重限制为仅两个可能的值（通常为 +1 和 −1），研究人员试图消除网络推理过程中所需的浮点乘法运算（FMULs），因为这些操作被认为是计算成本最高的。此外，由于实值权重被转换为二值形式，这类网络在存储参数时所占空间大幅减少，从而显著降低了内存占用和能耗 [8]。已有多种方法被提出用于训练此类网络 [1, 2, 22]。然而，这些方法在大容量数据集（如 ImageNet）上所得模型的准确率尚不理想 [22]。更为严峻的是，简单地扩大网络宽度并不能保证准确率的提升 [14]，因此，目前尚不清楚如何在这类方法中在模型精度与预期准确率之间取得平衡。

在本文中，我们提出网络素描（network sketching）作为一种追求二值权重卷积神经网络（CNNs）的新途径，其中二值结构被应用于预训练模型，而非从头开始训练。为了探索生成最先进模型的可能性，我们提出了两种具有理论依据的算法，使得能够通过调节素描的精度来实现更准确的推理。此外，为了进一步提升生成模型（即素描）的效率，我们还提出了一种算法，以关联方式实现二值张量卷积，从而同样减少了所需的浮点加减运算（FADDs）数量。实验结果表明，我们的方法在AlexNet和ResNet上都表现得极其出色。也就是说，仅需增加少量的FLOPs和内存占用，生成的素描便在性能上大幅超越了现有的二值权重AlexNet和ResNet，在ImageNet数据集上达到了接近最先进的识别准确率。

3. Network Sketching

一般而言，卷积层和全连接层是深度 CNN 中最耗资源的组件。幸运的是，两者均被认为是过度参数化的 [4, 30]。在本节中，我们阐述本方法的动机，并以卷积层为例介绍其实现细节。全连接层可采用类似的方式进行处理。

假设卷积层 L 的可学习权重可排列并表示为 {W(i) : 0 ≤ i < n}，其中 n 表示目标特征图的数量，而 W(i) ∈ Rc×w×h 是其第 i 个滤波器的权重张量。存储所有这些权重需要 32 × c × w × h × n 比特的内存，而卷积的直接实现则需要 s × c × w × h × n 次浮点乘加运算（FMULs，伴随相同数量的浮点加法运算 FADDs），其中 s 表示目标特征图的空间尺寸。

由于许多卷积模型被认为存在信息冗余，因此有可能为其寻找低精度且紧凑的等效形式，以提升效率。基于这一考虑，我们通过采用分治策略，探索在 L 中利用二进制结构。我们首先用某些二进制基的线性张量来近似预训练的滤波器，然后将相同的基张量进行分组，以追求最大的网络效率。

3.1. 滤波器近似

如上所述，我们的第一个目标是寻找权值 W 的二进制展开，使其能够良好地近似 W（如图 2 所示），即 $$W\approx ⟨B,a⟩=\sum _{j=0}^{m-1}{a}_j{B}_j$$，其中 $B\in {+1,-1}^{c\times w\times h\times m}$ 和 $a\in R^m$ 分别是 m 个二进制张量 $B_0,...,B_{m-1}$ 和相同数量的尺度因子 $a_0,...,a_{m-1}$ 的拼接。在此，我们研究在固定 m 的情况下对 B 和 a 的合适选择。第 3.1.1 节和第 3.1.2 节分别提出了两种具有理论依据的算法。

3.1.1 直接近似法

为了便于理解，我们首先介绍直接近似算法。一般而言，为了在展开后保持模型精度，应最小化重构误差（亦称近似误差、舍入误差）$e_2:=\Vert W-⟨B,a\Vert {\Vert }_2$。然而，作为一个具体的决策问题，直接最小化 $e_2$ 似乎是 NP-hard 的，因此求解该问题可能非常耗时 [3]。为了在合理时间内完成计算，我们提出了一种启发式算法：在该算法中，$B_j$ 和 $a_j$ 被依次学习，且每一次都根据 $e_2$ 最小化准则将它们选为当前最优解。即，

$$B_j,a_j=\arg \underset{B\in \mathcal{B},a\in \mathbb{R}}{\min }{\Vert {\hat{W}}_j-aB\Vert }^2,(1)$$

其中 B:={+1,−1}c×w×h\mathcal{B} := \{+1, -1\}^{c \times w \times h}B:={+1,−1}c×w×h，范数运算符 $\Vert \cdot \Vert$ 对于任意三维张量 $X$ 定义为 $\Vert X\Vert :=⟨X,X{⟩}^{1/2}$，而 ${\hat{W}}_j$ 表示合并所有此前生成的张量后的近似残差。特别地，若 $j=0$，则 ${\hat{W}}_j=W$；若 $j\ge 1$，则

$${\hat{W}}_j=W-\sum _{k=0}^{j-1}{a}_k{B}_k(2)$$

容易通过导数计算得知，公式 (1) 等价于

$$B_j=\text{sgn}({\hat{W}}_j)\text{且}{a}_j=\frac{⟨B_j,{\hat{W}}_j⟩}{t}(3)$$

算法 1：直接近似算法

• 输入： $W$：预训练的权重张量；$m$：所需的二进制基的基数。
• 输出： {Bj,aj:0≤j<m}\{B_j, a_j : 0 \le j < m\}{Bj​,aj​:0≤j<m}：一组二进制基及一系列缩放因子。
• 步骤：
  1. 初始化 $j\leftarrow 0$ 且 ${\hat{W}}_j\leftarrow W$。
  2. 重复以下过程：
     a. 通过公式 (3) 计算 $B_j$ 和 $a_j$。
     b. 计算 ${\hat{W}}_{j+1}={\hat{W}}_j-a_j{B}_j$ 并更新 $j\leftarrow j+1$。
  3. 直到 $j$ 达到最大数量 $m$ 为止。

在此情境下，函数 $\text{sgn}(\cdot )$ 计算输入张量的逐元素符号，且 $t=c\times w\times h$。上述算法总结于算法 1 中。该算法被视为启发式（或贪婪）算法，因为每次选择 $B_j$ 使其成为当前最优解，而不管其是否会排除后续更好的近似可能性。

此外，通过一些简单的推导可得如下理论结果。

定理 1： 对于任意 $m\ge 0$，算法 1 实现的满足重构误差 $e_2$ 满足：

$$e_2\le \Vert W{\Vert }^2{\left(1-\frac{1}{t}\right)}^m.(4)$$

证明： 由于 $B_j=\text{sgn}({\hat{W}}_j)$，我们可以得出，

$$⟨B_j,{\hat{W}}_j⟩=\sum _l|{\hat{w}}_j^{(l)}|\ge \Vert {\hat{W}}_j\Vert ,(5)$$

其中 ${\hat{w}}_j$ 是 ${\hat{W}}_j$ 的一个元素，上标 $(l)$ 表示其索引。由公式 (2) 和 (5)，我们有

$$\begin{array}{rl}\Vert {\hat{W}}_{j+1}{\Vert }^2& =\Vert {\hat{W}}_j{\Vert }^2-a_j⟨B_j,{\hat{W}}_j⟩\\ & =\Vert {\hat{W}}_j{\Vert }^2\left(1-\frac{⟨B_j,{\hat{W}}_j{⟩}^2}{t\Vert {\hat{W}}_j{\Vert }^2}\right)\\ & \le \Vert {\hat{W}}_j{\Vert }^2\left(1-\frac{1}{t}\right).(6)\end{array}$$

通过对 $j$ 从 $0$ 到 $m-1$ 应用公式 (6)，即可得到该结果。

3.1.2 带 refinements 的近似方法

从定理 1 可以看出，通过利用直接近似算法，重构误差 $e_2$ 以与 $1/t$ 成正比的速率指数级衰减。也就是说，给定一个尺寸较小（即 $t$ 较小）的张量 $W$，算法 1 仅使用少量二元张量即可实现相当不错的近似效果。然而，当 $t$ 相对较大时，重构误差下降缓慢，即使使用大量二元张量，近似效果也可能令人不满意。在本节中，我们提出对直接近似算法进行 refine（细化/精炼），以获得更好的重构性能。

算法 2 带细化的近似方法：

输入： $W$：预训练权重张量，$m$：二元基所需的基数（数量）。
输出： {Bj,aj:0≤j<m}\{B_j, a_j : 0 \le j < m\}{Bj​,aj​:0≤j<m}：一组二元基及一系列缩放因子。
初始化 $j\leftarrow 0$ 且 ${\hat{W}}_j\leftarrow W$。
重复执行：
通过公式 (3) 和 (7) 计算 $B_j$ 和 $a_j$。
更新 $j\leftarrow j+1$ 并通过公式 (2) 计算 ${\hat{W}}_j$。
直到 $j$ 达到其最大数量 $m$。

考虑到在算法 1 中，$B_j$ 和 $a_j$ 是在固定对方的情况下被选择以最小化 $e_2$ 的。然而，在大多数情况下，$B$ 和 $a$ 是否是整体最优的是值得怀疑的。如果不是，为了获得更好的近似效果，我们可能需要至少对其中一个进行 refine。出于计算简单性的考虑，我们转向 $B$ 固定的特定情况。也就是说，假设直接近似已经产生了 $\hat{B}$ 和 $\hat{a}$，我们在此寻找另一个缩放向量 $a$，满足 $\Vert W-⟨\hat{B},a⟩{\Vert }_2\le \Vert W-⟨\hat{B},\hat{a}⟩{\Vert }_2$。为了实现这一点，我们遵循最小二乘回归法并得到：

$$a_j=(B_j^T{B}_j{)}^{-1}{B}_j^T\cdot \text{vec}(W),(7)$$

其中，算子 $\text{vec}(\cdot )$ 获取一个列向量，其元素取自输入张量，而 $B_j$ 由 $[\text{vec}(B_0),...,\text{vec}(B_j)]$ 构成。

上述带有缩放因子细化的算法总结在算法 2 中。直观地说，细化操作赋予了我们的方法一种类似记忆的特性，而以下定理确保了与算法 1 相比，它收敛速度更快。

定理 2。 对于任意 $m\ge 0$，算法 2 实现的重构误差 $e_2$ 满足：

$$e_2\le \Vert W{\Vert }_2^2\prod _{j=0}^{m-1}\left(1-\frac{1}{t-\lambda (j,t)}\right),(8)$$

其中 $\lambda (j,t)\ge 0$，对于 $0\le j\le m-1$。

证明： 为简化符号表示，让我们进一步记 $w_j:=\text{vec}(W_j)$ 和 $b_{j+1}:=\text{vec}(B_{j+1})$，则我们可以通过分块矩阵乘法和逆运算得到：

$$(B_{j+1}^T{B}_{j+1}{)}^{-1}=\left[\begin{array}{cc}\Phi +\Phi \psi {\psi }^T\Phi /r& -\Phi \psi /r\\ -{\psi }^T\Phi /r& 1/r\end{array}\right],(9)$$

其中 $\Phi =(B_j^T{B}_j{)}^{-1}$，$\psi =B_j^T{b}_{j+1}$，且 $r=b_{j+1}^T{b}_{j+1}-{\psi }^T\Phi \psi$。因此，对于 $j=0,...,m-1$，我们有以下方程：

$$w_{j+1}=\left(I-\frac{\Lambda (b_{j+1}{b}_{j+1}^T)}{b_{j+1}^T\Lambda b_{j+1}}\right)w_j,(10)$$

这里定义 $\Lambda :=I-B_j\Phi B_j^T$。众所周知，给定半正定矩阵 $X$ 和 $Y$，有 $\text{tr}(XY)\le \text{tr}(X)\text{tr}(Y)$。于是，公式 (10) 给出：

$$\begin{array}{rl}\Vert {\hat{W}}_{j+1}{\Vert }_2^2& \le \Vert {\hat{W}}_j{\Vert }_2^2-\frac{w_j^T(b_{j+1}{b}_{j+1}^T)\Lambda (b_{j+1}{b}_{j+1}^T)w_j}{(b_{j+1}^T\Lambda b_{j+1}{)}^2}\\ & =\Vert {\hat{W}}_j{\Vert }_2^2-\frac{w_j^T(b_{j+1}{b}_{j+1}^T)w_j}{b_{j+1}^T\Lambda b_{j+1}}\\ & =\Vert {\hat{W}}_j{\Vert }_2^2\left(1-\frac{⟨B_j,{\hat{W}}_j{⟩}^2}{b_{j+1}^T\Lambda b_{j+1}\Vert {\hat{W}}_j{\Vert }_2^2}\right).\end{array}$$

显然，由此可得：

$$\Vert {\hat{W}}_{j+1}{\Vert }_2^2\le \Vert {\hat{W}}_j{\Vert }_2^2(1-1/(t-\lambda (j,t))),(11)$$

其中 $\lambda (j,t):=b_{j+1}^T(I-\Lambda )b_{j+1}$。由于 $\lambda (j,t)$ 代表 $b_{j+1}$ 的正交投影的平方欧几里得范数，不难证明 $\lambda (j,t)\ge 0$，从而得出上述结果。

3.2. 几何解释

在对预训练滤波器进行扩展之后，我们可以将相同的二值张量进行分组，从而进一步节省内存占用。在本文中，我们将整个技术命名为网络草绘（network sketching），并将生成的二值权重模型直接称为草绘（sketch）。接下来，我们将从几何角度对草绘过程进行解释。

首先，我们需要认识到，公式（1）本质上是在寻找由一组 t 维二值向量张成的线性子空间，以最小化该子空间与 vec(W) 之间的欧几里得距离。从概念上讲，该问题中存在两个需要确定的变量。算法 1 和算法 2 均采用启发式方法求解此问题，并且第 j 个二值向量始终通过最小化其自身与当前近似残差之间的距离来估计。二者之间的区别在于：算法 2 利用了其前 j−1 次估计的线性张成空间以获得更好的近似效果，而算法 1 则未利用这一点。

现在我们仔细考察定理 2。与定理 1 中的公式（4）相比，公式（8）的主要区别在于 λ(j, t) 的存在。显然，只要对于任意 j ∈ [0, m−1] 都有 λ(j, t) > 0 成立，算法 2 的收敛速度就会快于算法 1。
从几何角度来看，如果我们将 $B_j(B_j^T{B}_j{)}^{-1}{B}_j^T$ 视为向 $S_j:=span(b_0,...,b_j)$ 的正交投影矩阵，那么 λ(j, t) 等于某个向量投影的欧几里得范数的平方。因此，λ(j, t) = 0 当且仅当向量 $b_{j+1}$ 与 $S_j$ 正交，换句话说，$b_{j+1}$ 与集合 $b_0,...,b_j$ 中的每个元素都正交。这种情况发生的概率极低，且仅在 $t\in 2^k:k\in N$ 的条件下才可能出现。因此，在实际应用中，算法 2 很可能优于算法 1。

4. 加速草图模型

利用算法1或算法2，可以方便地获得L上的一组mn个二元张量，这意味着可学习权重的存储需求降低为原来的32t/(32m+tm)倍。在应用模型时，所需的浮点乘法运算（FMULs）数量也显著减少，降低为原来的(t/m)倍。草图方法可能带来的唯一副作用是浮点加法运算（FADDs）数量的某些增加，因为它给计算单元带来了额外的负担。 在本节中，我们尝试改进这一缺陷，并引入一种进一步加速二元权重网络的算法。我们从一个观察出发：尽管所需的浮点加法运算数量随m单调增长，但对于给定的L输入，被加数和加数的固有数量始终保持固定。也就是说，在二元张量卷积的直接实现中存在重复的浮点加法运算。令X ∈ Rc×w×h表示输入子特征图，图3给出了示意图。

4.1. 关联性实现

为了避免冗余操作，我们首先提出一种在集合 $L$ 上对多个卷积 $X\ast B_0,\dots ,X\ast B_{mn-1}$ 进行计算的关联性实现方法，其中充分利用了不同卷积之间的联系。具体来说，我们的策略是以分层且渐进的方式执行卷积。也就是说，每个卷积结果都作为后续计算的基准。假设第 $j_0$ 个卷积已预先计算得出，并产生结果 $X\ast B_{j_0}=s$，则 $X$ 与 $B_{j_1}$ 的卷积可以通过以下公式推导得出：

$$X\ast B_{j_1}=s+(X\ast (B_{j_0}\circ B_{j_1}))\times 2,(12)$$

或者 alternatively：

$$X\ast B_{j_1}=s-(X\ast (\neg B_{j_0}\circ B_{j_1}))\times 2,(13)$$

其中 $\neg$ 表示逐元素非运算，$\circ$ 表示逐元素运算符，其行为如表 1 所示。

表 1. 逐元素运算符 $\circ$ 的真值表

$B_{j_1}$	$B_{j_2}$	$B_{j_1}\circ B_{j_2}$
+1	-1	-1
+1	+1	0
-1	-1	0
-1	+1	+1

由于 $B_{j_0}\circ B_{j_1}$ 在每个索引位置上产生三值输出，我们可以自然地将 $X\ast (B_{j_0}\circ B_{j_1})$ 视为一系列 switch ... case ... 语句的迭代。通过这种方式，只需对 $B_{j_0}\circ B_{j_1}$ 中对应于 $\pm 1$ 的 $X$ 中的条目进行操作，从而获得加速效果。假设 $B_{j_0}$ 与 $B_{j_1}$ 的内积等于 $r$，则计算公式 (12) 和 (13) 分别仍需要 $(t-r)/2+1$ 和 $(t+r)/2+1$ 次浮点加法运算（FADDs）。显然，我们希望实数 $r\in [-t,+t]$ 接近 $t$ 或 $-t$ 的某个值，以便减少 FADD 次数，从而在我们的实现中获得更快的卷积速度。特别地，如果 $r\ge 0$，为了获得更好的效率，选择公式 (12)；否则，应选择公式 (13)。

4.2. 构建依赖树

我们的实现通过适当重新排列二进制张量，并以间接方式实现二进制张量卷积来工作。因此，除了公式 (12) 和 (13) 之外，还需要一棵依赖树来驱动整个流程。特别地，依赖关系是指某些二进制张量之间的链接关系，用于指定首先执行哪个卷积，以及随后执行哪些卷积。例如，采用深度优先搜索策略，图 4 中的树 $T$ 显示了一棵依赖树，表明首先计算 $X\ast B_1$，然后从前一个结果推导 $X\ast B_0$，接着以 $X\ast B_0$ 为基础计算 $X\ast B_3$，依此类推。通过遍历整棵树，所有 $mn$ 个卷积将被渐进且高效地计算出来。

事实上，我们的算法能够处理随机生成的树，但为了获得最优性能，仍需针对特定场景构建专用的依赖树 $T$。令 $G=(V,E)$ 为一个无向加权图，其中 $V$ 为顶点集，$E\in {\mathbb{R}}^{mn\times mn}$ 为权重矩阵。$V$ 中的每个元素代表一个单一的二阶张量，而 $E$ 中的元素则用于度量所选两个张量之间的距离。

算法 3 关联式实现：

• 输入： {Bj:0≤j<mn}\{B_j : 0 \le j < mn\}{Bj​:0≤j<mn}：二阶张量集合；$X$：输入子特征图；$T$：依赖树。
• 输出： {yj:0≤j<mn}\{y_j : 0 \le j < mn\}{yj​:0≤j<mn}：卷积运算的结果。
  获取 $z=T.\text{root}$，并计算 $y_{z.\text{key}}=X\ast B_{z.\text{key}}$。
  通过 $s\leftarrow y_{z.\text{key}}$ 初始化基线值。
  重复
  搜索 $T$ 的下一个节点并更新 $z$ 和 $s$。
  利用公式 (12) 或 (13) 计算 $y_{z.\text{key}}$。
  直到 搜索结束。

为与前一小节保持一致，此处定义距离函数如下：

$$d(B_{j_0},B_{j_1}):=\min \left(\frac{t+r}{2},\frac{t-r}{2}\right),(14)$$

其中 $r=⟨B_{j_0},B_{j_1}⟩$ 表示 $B_{j_0}$ 和 $B_{j_1}$ 的内积。显然，所定义的函数是定义在 {−1,+1}c×w×h\{-1, +1\}^{c \times w \times h}{−1,+1}c×w×h 上的度量函数，其取值范围限制在 $[0,t]$。回顾前一小节可知，我们期望 $r$ 的值接近 $\pm t$。因此，最优的依赖树应具备从根节点到其任意顶点的距离最短这一特性，故图 $G$ 的最小生成树（MST）即为我们所求。

从这一视角出发，我们可以利用现成的算法来构建此类树。本文选择 Prim 算法 [21]，原因之一是其时间复杂度关于边数 $|E|$ 呈线性关系，即在 $L$ 上的复杂度为 $O(m^2{n}^2)$。在获得 $T$ 之后，便很容易实现我们的算法，整个过程总结于算法 3 中。需要注意的是，虽然全连接层执行的是向量-矩阵乘法，但可将其视为一系列张量卷积。因此，在二进制情况下，我们也可以借助算法 3 在全连接层实现加速。

6. 结论

在本文中，我们引入（network sketching）作为实现二进制权重卷积神经网络（CNN）的一种新颖技术。该技术相较于现有方法具有更高的灵活性，使研究人员和工程师能够调控所生成速写的精度，从而在模型效率与准确性之间获得更优的权衡。我们通过理论分析与实证分析验证了其有效性。此外，我们还提出了一种关联式实现方案，用于加速二进制张量卷积，进一步提升速写的执行速度。经过上述努力，我们成功生成了二进制权重的 AlexNet 和 ResNet 模型，能够在 ImageNet 分类任务上实现既高效又忠实（高保真）的推理。未来的工作将包括探索其他 CNN 架构的速写结果。