CNN卷积层的Forward Propagation(FP)和Back Propagation(BP)与Deep Net全连层相比略有不同。卷积核在输入层上的平移使得Input值x发生变化,因此计算时需要定位卷积核位置。通过for循环可以暴力的让卷积核在Input层上平移,但如果想要用更更快的矩阵计算则需要一些额外的技巧。

Faster实现的效率对比

Stanford cs231n 的课程中要求手写CNN,不过对于FP和BP的过程只要求实现Naive的Loop版本,我之前按照课程要求写过一段代码实现。课程也提供了Fast Layers作为更快的版本,耗时对比如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 对于以下参数:
x = np.random.randn(100, 3, 31, 31) # 输入值
w = np.random.randn(25, 3, 3, 3) # 卷积核
b = np.random.randn(25,) # bias
dout = np.random.randn(100, 25, 16, 16) # 梯度
conv_param = {'stride': 2, 'pad': 1}

# 耗时如下:

# 前向传播:
Naive: 7.649808s
Fast: 0.019115s
# 反向传播:
Naive: 10.886264s
Fast: 0.026629s

可以看到利用矩阵运算可以提升2~3个数量级。那么利用矩阵运算如何快速计算CNN梯度呢?

Forward Propagation

前向的优化比较简单;我们用一个简单的例子看,假设padding为0,strike为1,channel为1的3x3矩阵,用2x2的卷积核计算卷积。

conv

上图表示卷积计算过程,卷积核在Input Layer上横向移动计算,这个过程必须依赖for循环来进行而非矩阵并行计算,因此会有额外时间损失。

那么很自然的优化想法是,我们按照卷积核把每一个待计算的区块取出来,再组合成一个大的矩阵,然后把每个区块和卷积核相乘。

这里区块的抽取理论上也是需要for循环实现,但其实映射操作有更加快速的方法,比如numpy就提供了以下函数用于区块抽取。

1
np.lib.stride_tricks.as_strided

$$ A_{3 \times 3} = \begin{bmatrix} 1&2&3 \\ 4&5&6 \\ 7&8&9 \end{bmatrix} \rightarrow \begin{bmatrix} \begin{bmatrix} 1&2 \\ 4&5 \end{bmatrix} & \begin{bmatrix}2&3\\5&6 \end{bmatrix} \\ \begin{bmatrix}4&5\\7&8 \end{bmatrix} & \begin{bmatrix}5&6\\8&9 \end{bmatrix} \end{bmatrix} = B_{2\times 2 \times 2 \times 2}$$

为了能够适配矩阵乘法,需要把$B$矩阵reshape为$4 \times 4$的矩阵$C_{4 \times 4}$,矩阵reshape的方式为把所有的小矩阵整合为一列,再把每个小矩阵变为一行。

接着就可以和同样reshape后的卷积核$W_{4 \times 1}$ 相乘,得到卷积乘法的解$D_{4 \times 1}$。

$$ C_{4\times 4} \cdot W_{4 \times 1} = \begin{bmatrix}1&2 &4&5\\2&3&5&6\\4&5&7&8\\5&6&8&9\end{bmatrix} \begin{bmatrix}1\\2\\3\\4\end{bmatrix} = D_{4 \times 1}$$

最后把$D_{4 \times 1}$重新reshape为$2 \times 2$ 的矩阵$F_{2 \times 2}$, 这就是最终卷积输出。

Back Propagation

在上述基础上,BP的过程也就明朗了很多。反向公式为

$$ \frac{\partial loss}{\partial W} =\frac{\partial loss}{\partial D}\frac{\partial D}{\partial W} $$

类似Deep Net的BP过程,$\frac{\partial loss}{\partial D}$ 是已知的,我们只需要求解$\frac{\partial D}{\partial W}$。
也就是说我们只需要用最后一步的公式
$$CW = D$$

这就简化为基础的矩阵乘法求导,问题也就迎刃而解了。

这里为了快速计算BP,我们可以在神经网络前向的过程中cache住矩阵C。

我们重新来回顾上面的矩阵$C_{4\times 4}$, 它的每行是矩阵$B$的子区块,也等效于A待计算的卷积区域。因此,在paddingstrike已知的情况下,我们其实可以推导出矩阵$C$进而进行快速的导数计算。