Title

Fast Algorithms for Convolutional Neural Networks

Abstract

现如今，人们花费数天的时间在GPU上来训练一个大型的卷积神经网络，在自动驾驶中，对行人检测的延迟要求非常高，手机等移动设备上的图像识别又受限于有限的计算资源，因此,从某种程度上来说，卷积神经网络能发展到什么程度和其运行速度息息相关。
一种基于FFT的卷积算法在较大的卷积核上收效甚好，但是现在主流趋势是用多层小卷积核来代替单层的大卷积核，而FFT在小卷积核上的效果则差强人意，基于此，作者提出用Winograd的minimal filtering algorithms来进行小卷积核的卷积计算，该方法适用于卷积核较小和batchsize较小的情况，并且极大的降低了计算复杂度。
最终，作者在GPU上实现了一个VGG网络，并观察了batchsize=1~64下该算法的表现。

Method

Convolutional Neural Networks

卷积神经网络中，卷积计算是指K个C通道的RxS卷积核和N个C通道的HxW输入特征进行计算，我们分别用 G k , c , u , v G_{k,c,u,v} Gk,c,u,v​和 D i , c , x , y D_{i,c,x,y} Di,c,x,y​来卷积核中的元素和输入特征图中的元素，那么卷积计算可以描述为

Fast Algorithms

自从1980年以来，我们就知道，可以使用minimal
filtering algorithm来利用一个一维的长度为r的滤波器计算m个输出，
我们称此为F(m,r)，它一共需要

次乘法，受此启发，同样的，我们可以将F(m,r)和F(n,s)嵌套，从而得到一个2维的最小滤波器算法，它可以用一个rxs的卷积核计算mxn的输出，我们称之为F(mxn,rxs)，一共需要

次乘法。当然，我们可以继续进行嵌套，以计算更高维度的卷积。
有趣的是，最小滤波器算法所用的乘法次数恰好等于读取输入数据的次数，也就是说，对一维的F(m,r)，我们需要读入m+r-1个数据，进行m+r-1次乘法，对二维的F(mxn,rxs)，我们需要读入(m+r-1)x(n+s-1)个数据，同样进行(m+r-1)x(n+s-1)次乘法，因此可以认为，平均每个输入数据需要进行一次乘法运算。

1.F(2x2,3x3)

F(2,3)的标准版本（即不使用Winograd算法）需要2x3个乘法运算，而Winograd算法流程如下图所示：

其中d是输入元素，共2+3-1等于4个，即d0,d1,d2,d3，而g则是相应的卷积核，计算得到2个输出。这里右边的m取值如下

可以验证，左式和右式是相等的。该算法一共进行了4次乘法，4次加法（指d之间的加法）,3次加法（指g之间的加法，g0+g2只需计算一次）,2次和常数的乘法（同1/2相乘）以及4次加法（m之间的加法）。我们也可以写成如下形式：

对于F(2,3)，上述矩阵具有如下形式

这里 ⨀ \bigodot ⨀表示element-wise乘法。
同样，我们可以推广到二维的卷积，对 F ( m × m , r × r ) F(m\times m,r\times r) F(m×m,r×r)来说，有：

其中g是一个 r × r r\times r r×r的卷积核，而d是一个 ( m + r − 1 ) × ( m + r − 1 ) (m+r-1)\times (m+r-1) (m+r−1)×(m+r−1)的输入特征图，当然，上述算法也适用于卷积核和输入特征图不是方形的情况（即m ≠ \neq ​=n,r ≠ \neq ​=s)。
我们以 F ( 2 × 2 , 3 × 3 ) F(2\times 2,3\times 3) F(2×2,3×3)为例，它一共进行了16次乘法，而标准的卷积则需要进行 2 × 2 × 3 × 3 = 36 2\times 2\times 3\times 3=36 2×2×3×3=36次乘法，乘法次数降低了2倍多。当然其代价是输入数据的转换使用了32次加法，卷积核的转换使用了28次浮点指令，最后的逆变换则使用了24次加法，不过相对乘法来说，加法的计算复杂度是有显著降低的。
更一般的，对于 F ( m × m , r × r ) F(m\times m,r\times r) F(m×m,r×r)，每次需要读入 ( m + r − 1 ) ( m + r − 1 ) (m+r-1)(m+r-1) (m+r−1)(m+r−1)个输入数据，以及 r × r r\times r r×r个卷积核参数，计算得到 m × m m\times m m×m个输出，这个过程一共进行了(m+r-1)(m+r-1)次乘法。
因为每次计算 m × m m\times m m×m个输出，那么若设输出特征图尺寸为 H × W H\times W H×W，则整个输出特征图需分块计算 [ H / m ] [ W / m ] [H/m][W/m] [H/m][W/m]次，而且易知，相邻的输入tile会有r-1行或列的重叠。
若记 U = G g G T U=GgG^T U=GgGT, V = B T d B V=B^TdB V=BTdB,那么
Y = A T [ U ⨀ V ] A Y=A^T[U\bigodot V]A Y=AT[U⨀V]A
我们用 ( x ~ , y ~ ) (\widetilde{x},\widetilde{y}) (x ,y ​)来标记每一个读入的 ( m + r − 1 ) ( m + r − 1 ) (m+r-1)(m+r-1) (m+r−1)(m+r−1)的tile，那么输出可以计算如下:

这里的一个trick是，将 A T A^T AT和 A A A作用在 Σ \Sigma Σ以后的矩阵上，这主要得益于线性性质，通过此方法，可以使得本来需要进行C次的 A T ( . ) A A^T(.)A AT(.)A运算降低为只需进行1次。