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次。
我们进一步简化标记 (
i
,
x
~
,
y
~
)
为
b
(i,\widetilde{x},\widetilde{y})为b (i,x ,y )为b，则有下式
固定 ξ
和
ν
\xi和\nu ξ和ν，那么这个式子可以看成是矩阵 U
k
,
c
(
ξ
,
ν
)
和
矩
阵
V
c
,
b
(
ξ
,
ν
)
的
乘
法
U^{(\xi,\nu)}_{k,c}和矩阵V^{(\xi,\nu)}_{c,b}的乘法 Uk,c(ξ,ν)和矩阵Vc,b(ξ,ν)的乘法，即
我们知道，矩阵乘法在CPU、GPU或者是FPGA上都有相当多的优化手段，因此，该算法是可行的。下图则是整个算法的流程示意图
其中P是tiles的个数， α
\alpha α则是输入tile的尺寸，算法大致可以分为三步：
1.输入特征的变换以及卷积核的变换，得到U和V
2.计算矩阵乘法 M
(
ξ
,
ν
)
=
U
(
ξ
,
ν
)
V
(
ξ
,
ν
)
M^{(\xi,\nu)}=U^{(\xi,\nu)}V^{(\xi,\nu)} M(ξ,ν)=U(ξ,ν)V(ξ,ν)
3.逆变换得到Y
2.F(3x3,2x2)
F(3X3,2X2)的变换矩阵如下
这个F(3X3,2X2)主要用于反向传播时的卷积计算，原理同上。
3.F(4x4,3x3)
A minimal algorithm for F(4, 3) has the form:
这里，输入数据的变换用了13个浮点指令，卷积核变换用了8个，逆变换用了10个。
对F(4,3)进行嵌套，F(4X4,3X3)共使用了36次乘法，是普通卷积144的1/4，数据变换使用了13*（6+6）=156次浮点指令，卷积核变换使用了8*（3+6）=72次，逆变换则使用了10*（6+4）=100次。
我们发现，随着tile尺度的增大，因为变换和逆变换所引起的加法以及常量乘法的运算次数呈抛物线增长，因此，如果tile过大，那么乘法次数带来的计算量下降会被加法和常量乘法所抵消。
同时，逆变换矩阵A的尺寸也随着tile的增大而增大，从而导致计算精度的降低(why?)，因此，大尺寸的tile也不利于神经网络的精度，不过好在神经网络并不需要很高的精度，其抗干扰能力是十分强的。
4.Fast Fourier Transform
略
5.Arithmetic Complexity Analysis
在本文所述的计算模型中，算法的乘法复杂度约为
为了进一步简化上式，我们假设H,W被m,n整除，且m=n,R=S,则上式可以简写为
而输入数据、卷积核、逆变换所带来的计算开销为：
其中, β
,
γ
,
δ
分
别
是
单
个
t
i
l
e
进
行
计
算
的
开
销
\beta,\gamma,\delta分别是单个tile进行计算的开销 β,γ,δ分别是单个tile进行计算的开销
将它们除以M，得到相对复杂度
这里 P
=
N
H
W
/
m
2
P=NHW/m^2 P=NHW/m2,是每个输出通道tiles的总数。
因此，Winograd算法总的计算复杂度为
为了得到尽可能大的加速比，我们希望 α
′
\alpha' α′越小越好，而 β
′
,
γ
′
,
δ
′
相
对
K
,
P
,
C
也
越
小
越
好
\beta',\gamma',\delta'相对K,P,C也越小越好 β′,γ′,δ′相对K,P,C也越小越好
Experiment&Result
略
