DarkNet CNN 实现

DarkNet CNN 实现

在了解 全连接层反向传播的机理后,我在 Google 上找了一圈,都没有找到讲得很好的 CNN 反向传播的计算,本想通过研究 Pytorch 源码分析算法原理,发现 Pytorch 底层是调用 C 代码的,也就不了了之了。最近在学习 Darknet 源码时,终于搞懂了这部分的原理。

1. 前向传播

这里要先说明一点,这个地方对应学过数字信号处理的同学来说,还是非常坑的。

数字信号处理中,实际的卷积操作如下: \[
(f*h)[m,n]=\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty f[i,j]\cdot h[m-i,n-j]
\]
而深度学习的卷积操作如下: \[
(f*h)[m,n]=\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty f[i,j]\cdot h[i-m,j-n]
\]
也就是说,深度学习中的卷积操作实际上是相关操作 (correlation)

在数字信号处理中,一维卷积需要把信号序列 (一般是时间序列) 绕原点翻转,二维卷积则需要把信号序列 (一般是图像序列) 绕中心点旋转 \(180^{\circ}\)

convolution is a filtering operation. correlation compared the similarity of two sets of data. Correlation is a measure of relatedness of two signals.

但其实,在深度学习中,卷积和相关可以理解为是相同的。

因为我们学习的就是卷积核权重,即卷积核未知,每次反向传播都会自动更新使得误差最小。而传统的图像处理采用已知的卷积核,如果不做翻转处理,结果完全不一样。当然,卷积核绕中心 \(180^{\circ}\) 对称的话,两种处理结果也是相同的。

感兴趣的还可以看下 我的这篇博客 Thinking of 2D convolution

1.1 输出尺寸

大多数博客只提到 CNN 算法的前向传播原理。其实如果搞过传统图像处理的,应该都知道,卷积层的本质就是滤波,包括高通滤波用于边缘检测,低通滤波 (如高斯滤波器) 用于图片平滑。感兴趣的可以去找相关书籍看看。

前向传播一个稍微麻烦的地方是 如果根据 input height, input width, kernel size, padding, stride 计算输出 output height , output width

公式如下: \[
\text {output height} = \Big \lfloor \cfrac {\text {input height} + 2 \times \text {padding} – \text {kernel size}} {\text {stride}} \Big \rfloor + 1
\]
output width 计算是类似的。

参考论文: A guide to convolution arithmetic for deep learning

对应的 GitHub repo: conv_arithmetic

1.2 卷积实现

这一小节参考的博客: Why GEMM is at the heart of deep learning

本博客着重讲的是第二点,如果实现二维卷积计算 ?

传统的数字信号处理中,对于两个长度相当的数据,我们通常用傅里叶变换间接求两个信号的卷积。

但由于深度学习中,常见的卷积核大小为 \(3 \times 3\), \(5 \times 5\) 等,采用傅里叶变换得不偿失,我们通常利用卷积定义直接计算。

由此引入本文的核心: GEMM – GEneral Matrix to Matrix Multiplication

它是 BLAS (Basic Linear Algebra Subprograms) library 的一部分。

GELL 听上去很高大上,是不是 ?

其实说白了就是 矩阵乘法 的计算实现。

矩阵乘法在深度学习中最直观的使用莫过于全连接层了,输入神经元和权重矩阵进行矩阵乘法,再和偏置矩阵相加,得到输出神经元的值。

言归正传,回到 CNN 实现

CNN 层输入数据尺寸为 batch_size \(\times\) depth (channel) \(\times\) input height \(\times\) input width,这是一个4维张量,在 Pytorch 中输入张量的顺序也是 batch \(\times\) depth \(\times\) height \(\times\) width

如果考虑对 batch 循环处理,那么每次的输入数据尺寸为 depth(channel) \(\times\) input height \(\times\) input width

卷积核的大小则为 output depth \(\times\) depth \(\times\) kernel size \(\times\) kernel size

注: 这里和别的博客说法不同,一般都将单个卷积核视为二维的,但其实想一下,考虑沿着深度方向 (每个输入通道) 都存在相应的不同卷积核,最后叠加。那么我们直接将沿着深度方向的所有卷积核视为一个卷积核,进行 3 维的相乘累加操作,不是更方便吗 ?

下图展示了输入数据尺寸为 \(1 \times 2 \times 5 \times 5\) (batch:1, depth:2, height: 5, width: 5),卷积核尺寸为 \(3 \times 2 \times 3 \times 3\) (output depth: 3, input depth: 2, kernel size: 3 ),输出数据尺寸为 \(1 \times 3 \times 3 \times 3\)

每次卷积核的运算: 相乘并累加

矩阵乘法 \(C = AB\) 的单次运算: \(A\) 的行向量与 \(B\) 的列向量相乘并累加

不知道你有没有看出来两者的联系 ?

是的,基本操作都是相乘并累加。

所有,有的人就想到了,将卷积层的计算也用矩阵乘法实现:

\(A\) 的每一行大小为 depth \(\times\) kernel size \(\times\) kernel size ,\(B\) 的每一列也是相同大小,矩阵相乘的基本运算对应的就是单次卷积核相乘累加操作。

也就是说,我们需要将 CNN 层的输入数据重新排列,根据它可以组成矩阵 \(A\) 的每一行 – 矩阵 \(A\) 每一行的数据就是按步长移动卷积核后,其对应位置上的原始输入数据。

如下图所示,将 4维的输入张量数据转为 2维矩阵 \(A\) ,通常称为 im2col, 表示 image-to-column

有的人可能会说,在步长 stride 比较小,kernel 比较大的情况下,上图中不同 patch 之间必然会相互覆盖 (overlap),也就是说生成的 2 维矩阵 \(A\) 会有大量的重复数据,生成这样的矩阵既浪费内存,又浪费时间,效率会高吗 ?

但是,请相信,和后面的矩阵乘法的高效比起来,这一步浪费的时间是有价值的。

The benefits from the very regular patterns of memory access outweigh the wasteful storage costs. The paper from Nvidia cuDNN: efficient primitives for Deep Learning describe why they ended up with a modified version of GEMM. There are a lot of advantages to being able to batch up a lot of input images against the same kernels at once.

根据前面的分析:

  1. \(A\) 的行数为 patch 的数目,即 batch size * output height * output width
  2. \(B\) 的列数为卷积核的数目,即 output depth

于是输出的 2 维矩阵大小为: batch size * output height * output width \(\times\) output depth ,在下一层看来,它又是一个新的 4 维矩阵。

如下图所示:

1.3 利用 numpy 验证

我们通过 numpy 验证两种方式计算卷积,哪一种更高效。

背景:

首先我们实现 zero_pad 函数实现 边缘补 0

方法一: 通过 卷积定义计算,我们需要使用两个 for 循环

方法二: GEMM,矩阵相乘计算

最终结果:

结果如下:

conv_fast: took 0.563950 seconds.
conv_faster: took 0.221714 seconds.

使用 GEMM 算法快了 50%,是不是很有效 !

1.4 Darknet 实现

convolutional_layer.c 中,实现了 forward_convolutional_layer 函数,里面主要使用了两个函数:

  1. im2col_cpu : 实现重排,考虑 padding, stride, kernel size 等参数
  2. gemm : 实现矩阵乘法 \(C = \alpha * AB + \beta * C\)

注意: gemm 支持 A, B 转置,因此具体实现有 4 个对应的函数

这两个函数分别在 im2col.cgemm.c 实现

2. 反向传播

说白了,我们要获得 3 个值,该层的 weight_updatesbias_updates ,以及更新前一层的 delta

如果从 GEMM 的角度考虑,得到 weight_updatesbias_updates 就很容易,因为它就是矩阵相乘的偏导,我们只要把前一层的 ouput 重排一下重新得到上面的矩阵 \(A\) ,然后和全连接层类似。

至于 前一层的 delta ,我们在计算矩阵偏导后,还需要多一步,逆重排,在 Darknet 中通过 col2im_cpu 实现,注意这一步基本是叠加元素叠加实现的。感觉具体细节比较麻烦,主要是如何寻找索引,详细请看 col2im_cpu.c 文件

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d 博主赞过: