基于FFT的高效神经网络设计

12024蝴蝶变形：一种高效的基于FFT的神经网络结构设计Keivan Alizadeh vahid，Anish Prabhu，Ali Farhadi，MohammadRastegari华盛顿大学，keivan@cs.washington.edu摘要在本文中，我们证明了将FFT算法的蝶形运算扩展点态卷积，我们称之为通道融合，是最先进的高效CNN中的主要计算瓶颈（例如，我们引入了一组信道融合准则，并证明了BFT产生关于这些准则的渐近最优FLOP计数。通过用BFT代替逐点卷积，我们将这些层的计算复杂度从O（n2）降低到O（nlogn）。我们的实验评估表明，我们的方法的结果在广泛的网络架构中显著提高精度，尤其是在低FLOP范围内。例如，BFT导致高达6。MobileNetV 1的75%绝对Top-1改进[15]，4. 4%用于ShuffleNet V2[28]和5. 4%的MobileNetV3[14]在ImageNet上，在类似的FLOPS数量下。值得注意的是，ShuffleNet-V2+BFT优于最先进的架构搜索方法MNasNet[43]，FBNet[46]和MobilenetV3[14]在低FLOP制度。1. 介绍设计能够在资源受限的边缘设备上高效运行的卷积神经网络（CNN）已经成为一个重要的研究领域。有一个持续的推动，把越来越多的能力在设备上的个人隐私，延迟和解决方案的可扩展性。在这些受限的设备上，通常对有限的资源量（包括计算和存储器）以及功率约束有极高的需求，以增加电池寿命。随着这一趋势 的发展，定制 芯片组、现 场可编程门 阵列（FPGA）和低端处理器也越来越普遍，这些处理器可用于运行CNN，而不是传统的GPU。一个常见的设计选择是通过将卷积层[15，38，28，50]分解为深度可分离卷积来图1：在最先进的架构中用BFT取代逐点卷积，在资源受限的设置中获得了显着的精度增益。由两部分组成：（1）空间融合，其中每个空间通道通过深度卷积独立地卷积，以及（2）通道融合，其中所有空间通道通过1×1卷积线性组合，称为逐点卷积。检查计算机-这些网络在推理时的状态曲线表明，与信道融合相比，空间融合的计算负担相对可以忽略不计[15]。在本文中，我们专注于设计一个有效的替代这些逐点卷积。我们提出了一套原则来设计一个替代逐点卷积的效率和准确性。拟议的原则如下：（1）从每个输入到所有输出的完全连接性：允许输出使用所有可用信息，（2）大信息瓶颈：增加整个网络的表示能力，（3）低运算计数：减少计算成本，（4）运算对称性：允许运算堆叠成密集矩阵乘法。在第3节中，我们正式定义了这些原则，并在数学上证明了满足这些原则的O（nlogn）操作我们提出了一种基于蝴蝶变换（BFT）的新型轻量级卷积构建块我们证明了BFT产生一个渐近最优的FLOP计数下12025这些原则。我们表明，BFT可以用作几种最先进的高效CNN中逐点卷积的直接替代。这大大降低了这些网络的计算瓶颈。例如，用BFT替换逐点卷积将MobileNetV1的计算瓶颈从95%降低到60%，如图3所示。我们的经验表明，使用BFT导致显着增加的准确性，在约束设置，包括高达6。MobileNetV1、4的绝对前1增长率为75%。ShuffleNet V2和5的4%。MobileNetV3在ImageNet[7]数据集上为4%。在神经网络中使用蝶形运算已经有了一些努力[20，6，33]，但据我们所知，我们的方法优于所有其他结构化矩阵方法（表2b），用于在低FLOP范围内大幅度取代逐点卷积以及最先进的神经架构搜索（表2a）2. 相关工作深度神经网络受到密集计算的影响已经提出了几种方法来解决深度神经网络中的有效训练和推理。高效的CNN架构设计：最近在视觉识别任务中的成功，包括对象分类，检测和分割，可以归因于对不同CNN设计的探索[23，39，13，21，42，17]。为了使这些网络设计更有效，一些方法将卷积分解为不同的步骤，将重点放在空间和信道融合上[15，38]。此外，其他方法在信道融合[28，50]或空间融合[30]中扩展了具有稀疏结构的因子分解方案。[16]在网络的层之间强制更多的连接，但是通过设计更小的层来减少计算我们的方法遵循相同的方向，设计一个稀疏结构的通道融合，使计算量更低，精度损失最小。结构矩阵：已经有许多方法试图通过利用CNN经常被过度参数化的事实来减少CNN中的计算[44，24，8，19]。这些模型通过在训练过程中强制执行线性变换结构来学习CNN或全连接层，该结构具有比原始线性变换更少的已经研究了用于压缩深度神经网络的不同类型的结构化矩阵，包括循环矩阵[9]、类托普利茨矩阵[40]、低秩矩阵[37]和傅立叶相关矩阵[32]。这些结构化矩阵已被用于近似内核或取代全连接层。UGConv [51]考虑用酉卷积代替ShuffleNet结构中的一个逐点卷积。组卷积，而我们的蝴蝶变换能够取代所有的逐点卷积。蝴蝶结构已经在线性代数[34，26]和神经网络模型[31]中研究了很长时间。最近，它受到了研究人员的更多关注，他们将其用于RNN [20]，内核近似[33，29，4]和完全连接层[6]。我们已经推广了蝶形结构来代替逐点卷积，并且在这个任务中显著优于所有已知的结构矩阵方法，如表2b所示。网络修剪：这方面的工作重点是通过修剪神经元或权重来减少CNN中大量的冗余参数[11，12，45，2]。我们的方法与这些类型的方法不同之处在于，我们一开始就强制使用预定义的稀疏信道结构，并且在训练过程中不改变网络的结构量化：另一种提高深度网络效率的方法是使用量化来表示网络权重和神经元[41，35，47，5，52，18，1]。这些方法使用更少的位（而不是32位高精度浮点）来表示网络标准训练过程的权重和神经元在极低位宽（1位）的情况下[35]不得不修改训练过程，以找到网络中权重和神经元的离散二进制值。我们的方法是正交的这条工作线，这些方法是我们的网络的补充。神经架构搜索：最近，已经提出了神经搜索方法，包括强化学习和遗传算法，以自动构建网络架构[53，48，36，54，43，27]。最近搜索-基于方法[43，3，46，14]使用反转残差块[38]作为自动网络设计的基本搜索块。在大多数基于搜索的方法中的主要计算瓶颈是在信道融合中，并且我们的蝶形结构不存在于这些方法的任何预定义块中。我们的高效信道融合可以用这些模型来增强，以进一步提高这些网络的效率我们的实验表明，我们提出的蝴蝶结构优于最近的架构搜索模型的小型网络设计。3. 模型在本节中，我们概述了所提出的模型的细节。如上所述，当前高效神经架构设计中的主要计算瓶颈是通道融合步骤，其利用逐点卷积层来实现。该层的输入是张量尺寸为n的X，单位为×h×w，其中n为通道12026ℎ..2222j=0jQj=02j2x1x2.x n−1BFT（n，2）一年二年.y n−11−BFLayer2−BFLayer日志记录−BFLayer2n2x n+1x n+2.xn−1xnn2y n+1y n+2二、.n−1n图2：BFT架构：该图说明了所提出的蝴蝶变换的图形结构。左图显示了应用于输入张量的BFT的递归过程，右图显示了递归过程的扩展版本，如网络中的logn蝴蝶层。W 和 H 分 别 是 宽 度 和 高 度 。 权 重 张 量W 的 大 小 为nout×nin×1×1，输出张量Y为nout×h×w。为了简单起见，我们假设n=nin=nout。逐点卷积层的复杂度是O（n2wh），这主要受通道数n的影响。我们建议使用蝴蝶变换作为一个层，它具有O（（nlogn）wh）的复杂度。该设计的灵感来自快速傅立叶变换（FFT）算法，该算法已被广泛应用于各种应用的计算引擎中，并且针对该算法的关键操作存在许多优化的硬件/软件设计，这些设计适用于我们的方法。在下面的小节中，我们将解释问题的公式化和蝶形变换的结构。3.1. 矩阵向量乘积的点态卷积逐点卷积可以定义为函数P如下所示Y=P（X; W）（1）通过将输入张量X重新整形为大小为n× （hw）（每列）的2-D矩阵X，可以将其写成矩阵乘积X中的向量对应于空间向量X[：，i，j]），并且转换时，这种转换必须尊重下文详述的理想特性。融合网络设计原则：1）从每个输入到所有输出的完全连接：这种条件允许每个输出都可以访问输入中的所有可用信息。2)大信息瓶颈：瓶颈大小被定义为网络中的最小节点数量，如果删除，从输入通道到输出通道的信息流将被完全切断（即。将没有从任何输入信道到任何输出信道的路径）。网络的代表能力受到瓶颈大小的限制。为了确保信息在通过信道融合时不会丢失，我们将最小瓶颈大小设置为n。3)低操作计数：图中的操作或等效边越少，融合所需的计算就越少因此，我们希望减少边缘的数量。4)操作对称性：通过强制每一层中存在相等的出度，操作可以堆叠成密集矩阵乘法，这在实践中比稀疏计算的推理快得多。声明：具有这些属性的多层网络具有将权重张量整形为2-D矩阵Wn×n，Y=WX尺寸（二）时间复杂度O（n）证明：假设在第i层中存在ni个节点删除一层中的所有节点将断开输入和输出。由于最大可能的瓶颈大小是n，其中Y是输出张量Y的矩阵表示。这可以看作是使用W作为变换矩阵对X的列中的向量进行线性变换。因此ni≥n。现在假设第i层每个节点的出度为di。在第i层中，从输入通道可到达的节点eQs的数量是i-1d。因为线 性 变 换 是 一 个 矩 阵 - 向 量 乘 积 ， 其 复 杂 度 为 O（n2）。通过在该变换矩阵上强制结构，可以降低变换的复杂性然而，为了有效地作为通道融合，每个节点到所有节点的连接，输出中的所有n个节点层是可到达的。因此m−1d≥n。这意味j=0jthatm−1 log (d ) ≥ log (n).边的总数为：......2BFT（n，2BFT（n，.................Xy12027KKK好吧..1K....KK1（，k）Mm−1nd≥nm−1d≥nm−1log（d）≥其中y=kDx.注意，M（n，k）y是一个较小j=0j jj=0jj=02jij=1K我的天nlog2n□在下面的部分中，我们将介绍一个网络结构满足融合网络的所有设计原则。3.2. 蝴蝶变换如上所述，我们可以降低通过在矩阵上强制结构来实现矩阵-向量乘积。有几种方法可以在矩阵上实施结构。在这里，我们首先解释如何通过BFT完成信道融合，然后显示一族结构化矩阵这种融合导致O（nlogn）的操作和参数的复杂度，同时保持准确性。通过BFT进行通道融合：我们想把所有渠道的信息融合起来。我们按顺序分层进行 在第一层中，我们将通道划分为k个部分，每个部分的大小为n，x1，...， xk. 我们还将该第一层的输出声道划分为k个部分，每个部分具有n个大小，y1，..，是的。我们将元素连接起来因此，我们可以使用分治法来递归地计算乘积B（n，k）x。如果我们考虑T（n，k）由于计算复杂性的产品之间的（n，k）蝶形矩阵和n-D向量。从等式5，乘积可以通过n阶蝶形矩阵的k个乘积来计算，其复杂度为kT（n/k，k）。 对于所有i ∈ {1，. - 是的- 是的因此，k}的时间复杂度为O（kn）：时间复杂度：O（n，k）=O（n，k）时间复杂度O（k（nlogkn））通过较小的k（2≤k≤n）选择，我们可以实现较低的复杂度。算法1示出了当k=2时蝶形变换的递归过程。算法1：递归蝴蝶变换kn1函数ButterflyTransform（W，X，n）：xi到yj有k条平行边Dij。在以这种方式组合信息之后，每个yi包含来自所有通道，然后我们递归地融合每个通道的信息，yi在下一层中。蝴蝶矩阵：根据矩阵B（n，k）是一个n阶k基蝶形矩阵，其中B（n，k）∈IRn×n，相当于前面描述的融合过程/*算法作为递归函数*/数据：W包含2nlog（n）数的权重数据：X包含n个数字的输入如果n = 1，则return[X];4用W的前2n个数字作D11、D12、D21、D22;n（n，k）MkD11。（n，k）. - 是的- 是的M1kD1k.5将剩余的2n（log（n）−1）个数拆分为两个序列W1，W2，每个长度为n（log（n）-1）。6将X拆分为X1，X2;B（n，k）=0.. -是的-是的.中国（3）7y1←−D11X1+D12X2;（n，k）MkkDk1（n，k）. - 是的- 是的M kkDkk8y2←−D21X1+D22X2;9My1←−ButterflyTransform（W 1，y 1，n−1）;其中M（n，k）是n阶蝶形矩阵，10My2←−ButterflyTransform（W2，y2，n−1）;in nk11returnConcat（My1，My 2）;基为k且Dij是任意对角k×k矩阵。 的蝶形矩阵B（n，k）与向量x∈IRn为：nk1（n，k）D 11. - 是的- 是的M 1kD1kX13.3. 蝶形神经网络在算法1中解释的过程可以表示为B（n，k）x =0..（n，k）. -是的-是的..（n，k）好吧一个类似于FFT的蝴蝶图蝴蝶网络结构已被用于函数表示[25]和用于近似线性变换的快速因式分解[6]。M·K·KnDk1. - 是的-是的 M·K·KDkkXK（四）我们采用此图作为神经网络各层的架构设计。图2说明了一个蝶形程序其中xi∈IRk是x的一个子部分，通过将x分解为k个大小相等的向量。因此，乘积可以通过将M分解为以下因子来简化：基k=2的网络应用于大小为n×h×w的输入张量。左图显示了BFT的递归结构如何作为网络。 右图显示了构建的多层n（n，k）（n，k）具有lognButterfly Layers（BFLayer）的网络注意Mj=1D1jxjM1KY1每个蝴蝶层的复杂度是O（n）（2n次操作），因此，BFT架构的总复杂度将是12028..i=1M（，k）Σ（n，k）（n，k）k（n，k）时间复杂度O（n）B x =MikjDijxj=Mkyi。好吧每个Butterfly层都可以通过批处理范数和非线性函数（例如ReLU，Sigmoid）进行增强在第4.2节中，我们研究了（n，k）M·K·Kkj=1DkjxjnKKyk（五）使用这些功能的不同选择的效果。我们发现批处理范数和非线性函数（ReLU和Sigmoid）在BFLayers中都不是有效的批量定额未生效12029n+n图3：FLOP的分布：该图显示，用BFT替换逐点卷积减少了计算瓶颈的大小。这主要是因为它的复杂度与BFLayer的O（n）相同，因此，它使整个变换的计算量加倍。我们只在变换结束时使用批范数非线性激活ReLU和Sigmoid会将每个BFLayer中几乎一半的值清零，因此在整个前向传播过程中这些值的相乘会BF层可以以不同的方式与剩余连接进行内部连接。在我们的实验中，我们发现最好的残差连接是将第一个BFLayer的输入连接到最后一个BFLayer的输出的连接。BFT的基础影响FLOP的形状和数量。我们已经根据经验发现，基数k=4实现了最高的精度，同时具有与基数k=2相同的FLOP数量，如图5c所示。蝶形网络满足所有融合网络设计原则。在每个输入通道到所有输出通道之间恰好存在一条路径，图中每个节点的度恰好为k，瓶颈大小为n，并且边的数量为时间复杂度O（n）我 们 使 用 BFT 架 构 作 为 不 同 CNN 架 构 中 逐 点 卷 积 层（ 1×1convs ） 的 替 代 ， 包 括 MobileNetV1[15] ，ShuffleNetV2[28] 和 MobileNetV3[14] 。 我 们 的 实 验 结 果 表明，在在相同的FLOP数下，与具有较小信道速率的原始模型相比，BFT的效率增益在准确性方面更有效。我们在几个架构设置中显示了一致的准确性提高。使用BFT而不是逐点卷积来融合通道可以大幅降低计算瓶颈的大小。图3显示了在网络中的前向传递中每个块类型请注意，当应用BFT增长8倍。4. 实验在本节中，我们将展示所提出的BFT在大规模图像分类任务上的性能。为了证明-MobileNetV1、（2）ShuffleNetV2和（3）MobileNetV3。我们比较我们的结果与其他类型的结构矩阵，具有O（nlogn）的计算（例如。低秩变换和循环变换）。我们还表明，我们的方法优于国家的在低FLOP范围内的现有技术架构搜索方法。4.1. 图像分类4.1.1实施和数据集详细信息：按照标准实践，我们在ImageNet数据集上评估了不同复杂程度 的 But-maths 变 换 的 性 能 ， 范 围 从 14 MFLOPS 到 150MFLOPS。ImageNet分类数据集包含120万个训练样本和50K个验证样本，均匀分布在1000个类中。对于每种架构，我们用Butterfly Transforms代替逐点卷积为了保持BFT和逐点卷积之间的FLOP计数相似，我们调整了基础架构（MobileNetV 1，ShuffleNetV 2和Mo-bileNetV 3）中的通道数。对于所有架构，我们通过使用SGD最小化交叉熵损失来优化网络。具体的学习率制度用于每个架构，可以在附录中找到。由于BFT对权重衰减敏感，我们发现使用很少或没有权重衰减提供了更好的准确性。我们通过实验发现（图5c），蝶形基底k=4表现最好。我们还使用了自定义权重初始化的内部权重的蝴蝶变换，我们概述如下。关于这些超参数的更多信息和直觉可以在我们的消融研究中找到（第4.2节）。重量初始化：正确的权重初始化对于神经网络的收敛至关重要，如果操作不当，可能会导致训练不稳定和性能低下。这是...由于层内乘法的放大效应，这可能会产生非常大或非常小的值，因此对于蝴蝶变换来说也是如此。初始化逐点卷积解的一种常用技术是从我们的方法在设计非常小的网络方面的优势，（−x，x）其中x=6，被称为Xavier在外层我们比较了蝴蝶变换和逐点变换的性能，三种最先进的高效架构中的卷积：（一）初始化[10]。我们不能简单地将此初始化应用于蝴蝶层，因为我们正在改变内部结构。12030u，vu，v(a)（c）第（1）款FlopsShuffleNetV2ShuffleNetV2+BFT增益14米50.86（14个月）*55.26（14个月）4.4021 M55.21（21个月）*57.83（21个月）2.6240米59.70（41个月）*60.30（41个月）61.33（41个月）1.631.03(b)FlopsMobileNetV3MobileNetV3+BFT增益10-15米49.8（13个月）55.21（15个月）5.41表1：这些表格比较了ShuffleNetV2、MobileNetV1和MobileNetV3在使用标准逐点卷积与使用BFT时的准确性我们将每个条目B（n，k）表示为从节点u到v的路径中所有边的乘积。我们建议从范围（-y，y）初始化蝶形层的权重，使得乘法-沿着路径的所有边的阳离子，或者等价地B（n，k）中的值，初始化为接近范围（−x，x）。要做到这一点，我们求解一个y，它使B（n，k）的元素的绝对值的期望等于标准Xavier初始化的权重的绝对值的期望，即x/2。 令e1，..， elog（n）是从输入节点u到输出节点v的路径p上的边。我们有以下几个：在41 MFLOPs，这意味着它可以得到更高的精度与几乎一半的FLOPs。这是在根本不改变架构的情况下实现的，而只是简单地替换逐点卷积，这意味着通过考虑BFT来设计架构可能会有进一步的收益。4.1.3ShuffleNetV2 + BFT我们修改ShuffleNet块以将BFT添加到ShuffleNetv2。在表1a中，我们显示了ShuffleNetV2+BFT的结果，与原始结果E[|B（n，k）|] =E[|loYg（n）i=1ei|]= x2（八）ShuffleNetV2. 我 们 已 经 内 插 了 输 出 通 道 的 数 量 来 构 建ShuffleNetV 2 -1.25+BFT，在FLOP中与ShuffleNetV 2 -0.5相当我们比较了这两种方法在不同的输入分辨率（128，160，224），结果在FLOP我们在range（−y，y）中初始化每个ei，其中从14M到41M。ShuffleNetV 2 -1.25+BFT实现约（y）2log（n）=x21=y=xlog（n）2log（n）−1log（n）-是的（九）比我们使用逐点卷积的ShuffleNetV 2 -0.5实现的准确率高1.6%它比ShuffleNetV2 [28]在41 MFLOPs上报告的数字高出1%4.1.2MobileNetV1 + BFT要将BFT添加到MobileNeV 1，对于所有由depth层和逐点层组成的Mo-bileNetV 1块，我们将逐点卷积替换为Butterfly Transform，如图4所我们想 强 调 的 是 ， 这 意 味 着 我 们 将MobileNetV1中的所有在表1中，我们表明，我们在大约14M到150M FLOP的范围内优于MobileNetV1的频谱，而MobileNetV1 +BFT的我们的经验-图4：MobileNetV1+BFT块4.1.4MobileNetV3 + BFT我们遵循一个非常类似于Mo-bileNetV 1 +BFT的过程，并简单地将所有逐点卷积替换为蝴蝶变换。 我们训练了一个MobileNetV3+BFT Small，网络宽度为0.5，输入分辨率为224，达到了55。21%Top-1准确度。该模型优于Mo-bileNetV3小网络宽度0.35和输入分辨率224在一个类似的FLOP范围约5。4%Top-1，如1b所示。由于资源限制，我们只训练了一个变体Mo-bileNetV 3 +BFT。4.1.5与神经结构搜索的比较MobileNetV1+BFT的部分包括宽度乘数1.00和2.00的所有组合，以及输入分辨率128、160、192和224。我们还增加了一个输入分辨率为96的宽度倍增器1.00完整的结果表见附录。在表1c中，我们展示了使用BFT在整个频谱上都优于传统的MobileNets，但在低FLOP范围内特别有效例如，使用BFT导致在23个MFLOP处的前1个准确度增加6.75%请注意，MobileNetV1+ BFT在23 MFLOP下的准确度比MobileNetV1高得多FlopsMobileNetMobileNet+BFT增益14米41.50（14个月）46.58（14个月）5.0820米45.50（21个月）52.26（23个月）6.7640米47.70（34个月）50.60（41个月）54.30（35个月）6.603.7050米56.30（49个57.56（51个月）1.262.0512031在ShuffleNetV2中包括BFT使我们能够在极其复杂的环境中实现比最先进的架构搜索方法MNasNet[43]，FBNet [46]和MobileNetV3 [14]更高的准确性。低资源设置（14M FLOPs）。这些架构搜索方法搜索预定义的构建块的空间，其中用于信道融合的最有效的块是逐点卷积。在表2a中，我们表明，通过简单地替换ShuffleNetv 2中的逐点卷积，我们能够在ImageNet上的Top-1准确性方面超越最先进的架构搜索方法。我们希望这将导致未来的工作，其中BFT是在-12032模型精度ShuffleNetV2+BFT（14 M）55.26MobileNetV 3小型-224-0.5+BFT（15M）55.21FBNet-96-0.35-1（12.9 M）50.2FBNet-96-0.35-2（13.7 M）51.9MNasNet（12.7 M）49.3MobileNetV 3小-224-0.35（13 M）49.8MobileNetV3Small-128-1.0（12 M）51.7模型精度MobilenetV1+BFT（35 M）54.3MobilenetV1（42 M）50.6MobilenetV1+循环液 *（42M）35.68MobilenetV1+低级别 *（37M）43.78MobilenetV1+ BBP（35 M）49.65MobilenetV1+Toeplitz*（37M）40.09(a) BFT与 架构搜索（b）BFT与 其他结构化矩阵方法表2：这些表格将BFT与其他高效网络设计方法进行了比较。在表（a）中，我们表明ShuffleNetV2 + BFT优于最先进的神经架构搜索方法（MNasNet [43]，FBNet[46]，MobilenetV3[14]）。在表（b）中，我们表明BFT实现了比可用于信道融合的其他结构化矩阵方法显著更高的准确性。* 表示这是我们的实现。作为架构搜索中的构建块之一，因为它为通道融合提供了极低的FLOP方法。4.1.6与结构矩阵的为了进一步说明蝴蝶变换的好处，我们将其与其他结构矩阵方法进行了比较，这些方法可用于降低逐点卷积的计算复杂度在表2b中，我们表明BFT在相似的FLOP范围内显著优于所有这些其他方法为了可比性，我们扩展了所有其他方法，以便在必要时用作逐点卷积的替代然后，我们为每种方法替换了MobileNetV 1中的所有逐点卷积，并在ImageNet上报告了Top-1验证精度在这里，我们总结这些其他方法：循环块：在这个块中，表示逐点卷积的矩阵是循环矩阵。在循环矩阵中，行是彼此循环移位的版本[9]。产品这个循环矩阵的列可以有效地计算，时间复杂度为O（nlog（n））。低秩矩阵：在该块中，表示逐点卷积的矩阵是两个log（n）秩矩阵的乘积（W = UV T）。因此，逐点卷积可以由两个后接的小矩阵乘积执行，总复杂度为O（nlogn）。Toeplitz Like：Toeplitz Like矩阵已经在[40]。它们已经被证明在核近似上工作得很好我们在实验中使用了位移秩r = 1。快餐：此块已在[22]中引入，并在[49]第四十九章：你是谁？在Deep Fried Nets中，他们用FastFood取代了完全连接的层。通过统一batch，height和width维度，我们可以使用全连接层作为逐点卷积。BBP：该方法使用蝴蝶网络结构进行快速因子分解，以近似线性变换，例如离散傅立叶变换（DFT）和Hadamard变换[6]。我们通过使用上面Fastfood部分中解释的技巧扩展BBP以处理逐点卷积，并在ImageNet上进行了实验。4.2. 消融研究现在，我们研究BFT模型的不同元素。如前所述，残余连接和非线性激活可以在 我 们 的 BFLayers 中 得 到 增 强 。 在 这 里 ， 我 们 使 用MobileNetv 1作为基础网络，在CIFAR-10数据集上单独显示了这些元素的性能。唯一的例外是在ImageNet上进行的But-baseBase实验。剩余连接：用逐点卷积代替BFTransform得到的图非常深。残余连接通常有助于训练深度网络。表3：剩余连接我们实验了三个添加剩余连接的不同方式：（1）先到后，其将第一个BFLayer的输入连接到最后一个BFLayer的输出，（2）每隔一层，其连接每隔一个BFLayer，以及（3）无剩余，其中不存在剩余连接。我们发现，如表3所示，从第一个到最后一个是最有效的剩余连接类型有/无非线 性：正如 [38] 所研究 的那样， 将ReLU 或Sigmoid等非线性函数添加到窄层（通道很少）会降低精度，因为它会将内部层的一半值切为零。在BFT中，输入通道i对输出通道o的影响由i和o之间的路径上的所有边缘的乘法确定。将路径上的任何值降为零将破坏两个节点之间传输的所有丢弃每个内部层的一半值会破坏整个层中的几乎所有信息正因为如此，我们图5b比较了具有和不具有非线性激活函数的BFT模型的学习曲线有/无重量衰减：我们发现BFT对重量衰减非常敏感。这是因为在BFT中，从输入通道i到输出通道o只有一条路径。i对o的影响由沿着i和o之间的路径的所有中间边的乘积确定。将所有权重值推到零，将显著降低i对o的影响。因此，重量衰减在BFT中是非常具有破坏性的图5a示出了在BFT上使用和不使用权重衰减的学习曲线。蝶形底座：B（n，k）中的参数k决定了蝶形变换的结构，对模型的精度有重要影响。BFT的内部结构将模型精度无残余79.2每层81.12从第一个到最后一个81.7512033(a)重量衰减的影响（b）激活的影响（c）蝴蝶基地图5：BFT的设计选择：a）在BFT中，我们不应该强制权重衰减，因为它显著降低了输入通道对输出通道的影响。b）同样，我们不应该应用常见的非线性激活函数。这些函数将中间BF层中几乎一半的值归零，这导致从输入通道到输出通道的信息流灾难性地下降c）蝶形底座决定BFT的结构在4000万FLOP预算基数k=4的情况下，效果最好。包含logk（n）层。因此，非常小的k值会导致更深的内部结构，这可能更难以训练。k值越大，越浅，但计算量越大，因为BFT内部的层中的每个节点都有一个出度k。对于较大的k值，这种额外的计算以更多的FLOP为代价我们在MobileNetV1+BFT上测试了k=2，4，8，n的值，输入分辨率为160x160，结果为1040MFLOP。当k=n时，这等价于标准逐点卷积。为了进行公平的比较，我们确保持有FLOP通过改变通道的数量，在我们所有的实验中保持一致，并在ImageNet上使用相同的超参数测试了所有模型我们在图5c中的结果表明，k=4显著优于所有其他k值。我们的直觉是，由于块的浅性，这种设置可以让块很容易地被训练，并且比这更多的计算最好花在其他地方，例如在这种情况下增加通道的数量很可能存在一个更优的k值，该值在整个模型中变化，而不是固定的。我们也仅在相对较低的FLOP 范围（40M）上进行了该消融研究，因此可能是较大架构在不同k值下表现更好的情况。这种设计选择有很大的未来探索空间5. 缺点我们的模型的一个弱点是，当使用BFT时，工作内存会增加例如，MobileNetV 1 -2.0+BFT与MobileNetV 1 -0.5具有相同的 FLOPS数量，这意味着它将使用大约四倍的工作内存。请注意，中间的BF层可以就地计算，因此它们不会增加所需的工作内存量。由于使用更宽的通道，GPU训练时间也增加了。在我们的实现中，在前向传递中，我们从BFLayer的当前权重计算B（n，k），这是训练中的瓶颈。Introducing a GPUimplementation of butterfly operations would greatly reducetraining time.6. 结论和未来工作在本文中，我们演示了一系列被称为蝴蝶变换的高效变换如何在各种神经架构中取代逐点卷积，以减少计算量，同时保持准确性。我们探索了该块的许多设计决策，包括剩余连接、非线性、权重衰减、BFT的功率，并且还引入了新的权重初始化，这使我们能够显著优于我们所知道的用于有效信道融合的所有其他结构化矩阵方法。我们还提供了一套融合网络设计的原则，BFT表现出所有这些性质。作为高效卷积神经网络中逐点卷积的直接替代，我们已经证明，我们的方法显着提高了模型的准确性，特别是在低FLOP范围内，并且可以在资源受限的边缘设备上实现新的功能。值得注意的是，这些神经架构根本没有针对BFT进行优化，我们希望这项工作将导致更多针对蝴蝶变换设计的网络的研究，无论是通过手动设计还是架构搜索。BFT还可以扩展到其他领域，如语言和语音，以及新型架构，如递归神经网络和变压器。我们期待着未来的推理实现，但-ESTA结构，这将有望验证我们的假设，这个块可以非常有效地实现，特别是在嵌入式设备和FPGA。最后，我们面临的主要挑战之一是训练BFT所需的大量时间和GPU内存，我们相信作为未来的工作，优化这个块的训练有很大的空间。确认感 谢 Aditya Kusupati ， Carlo Del Mundo ， GolnooshSamei，Hessam Bagherinezhad，James Gabriel和Tim Dettmers的帮助和宝贵意见。这项工作得到NSF IIS 1652052、IIS17303166、DARPA N66001-19-2-4031、67102239的部分支持还有艾伦人工智能12034引用[1] Renzo Andri，Lukas Cavigelli，Davide Rossi，and LucaBenini.Yodann：超低功耗二进制权重cnn加速架构。IEEE Transactions on Computer Aided Design of IntegratedCircuits and Systems，2018。[2] Hessam Bagherinezhad，Mohammad Rastegari，and AliFarhadi. LCNN：基于查找的卷积神经网络。CoRR，abs/1611.06473，2016。[3] 韩才、朱立庚、宋涵。ProxylessNAS：在目标任务和硬件上直接搜索神经架构。2019年，在ICLR[4] Krzysztof Choromanski，Mark Rowland，Wenyu Chen，and Adrian Weller.统一正交蒙特卡罗方法。在KamalikaChaudhuri和Ruslan Salakhutdinov，编辑，第36届国际机器学习会议论文集，机器学习研究论文集第97卷，第1203-1212页，长滩，加利福尼亚州，美国，2019年6月9日至15日。PMLR。[5] Matthieu Courbariaux、Itay Hubara、Daniel Soudry、RanEl-Yaniv和Yoshua Bengio。二进制神经网络：训练神经网络，权重和激活限制为+1或-1。arXiv预印本arXiv：1602.02830，2016。[6] Tri Dao，Albert Gu，Matthew Eichhorn，Atri Rudra，and Christopher Ré.使用蝶形分解学习线性变换的快速算法。arXiv预印本arXiv：1903.05895，2019。[7] Jia Deng，Wei Dong，Richard Socher，Li-Jia Li，KaiLi，and Li Fei-Fei.Imagenet：一个大规模的分层图像数据库。2009年IEEE计算机视觉和模式识别会议，第248-255页。Ieee，2009年。[8] 艾米丽·L·丹顿、沃伊切赫·扎伦巴、琼·布鲁纳、扬·勒昆和罗布·弗格斯。利用卷积网络中的线性结构进行有效评估。神经信息处理系统的进展，第1269-1277页，2014年[9] 丁彩文，廖思宇，王延智，李哲，刘宁，卓有为，王超，钱学海，白宇，耿元，等。cir cnn：使用块循环权重矩阵加速和压缩深度神经网络在第50届IEEE/ACM国际微架构研讨会论文集，第395-408页ACM，2017。[10] 泽维尔·格洛特和约舒亚·本吉奥了解训练深度前馈神经网络的困难。在Yee Whye Teh和Mike Titterington的编辑，ProceedingsoftheThirteenthInternationalConference on Artificial Intel- ligence and Statistics ，Proceedings of Machine Learning Research的第9卷，第249-PMLR。[11] Song Han，Huizi Mao，and William J Dally.深度压缩：使用修剪、训练量化和霍夫曼编码压缩深度神经网络。arXiv预印本arXiv：1510.00149，2015。[12] Song Han，Jeff Pool，John Tran，and William Dally.学习权值和连接以实现高效的神经网络。2015年，在NIPS[13] Kaiming He，Xiangyu Zhang，Shaoying Ren，and JianSun.用于图像识别的深度残差学习在CVPR，2016年。[14] Andrew Howard ， Mark Sandler ， Grac