卷积神经网络的复杂度分析[转]

Author： AIHGF
发布时间：January 21, 2019
7599views
No comments
7808 words
Categories：网络模型

原文：卷积神经网络的复杂度分析 - 知乎 - 2018.08.16
作者：Michael Yuan

在梳理CNN经典模型的过程中，作者理解到其实经典模型演进中的很多创新点都与改善模型计算复杂度紧密相关，因此这里就对卷积神经网络的复杂度分析简单总结一下下. 本文主要关注的是针对模型本身的复杂度分析.

1. 时间复杂度

时间复杂度，即模型的运算次数，可用 FLOPs 衡量，也就是浮点运算次数(FLoating-point OPerations).

1.1. 单个卷积层的时间复杂度

$$ \mathbf{Time} \sim O(M^2 \cdot K^2 \cdot C_{in} \cdot C_{out}) $$

其中，

$M$ 为每个卷积核输出特征图(Feature Map) 的边长；

$K$ 为每个卷积核(Kernel) 的边长；

$C_{in}$ 为每个卷积核的通道数，即输入通道数，也就是上一网络层的输出通道数；

$C_{out}$ 为当前卷积层所具有的卷积核个数，即输出通道数.

可见，每个卷积核的时间复杂度由输出特征图面积 $M^2$、卷积核面积$K^2$、输入通道数$C_{in}$ 和输出通道数 $C_{out}$ 完全决定的.

其中，输出特征图尺寸本身又由输入矩阵尺寸 $X$、卷积核尺寸 $K$、Padding，步长(Stride) 这四个参数所决定的，表示如下：

$$ M = \frac{(X-K+2*Padding)}{Stride} + 1 $$

注1：为了简化表达式中的变量个数，这里统一假设输入和卷积核的形状都是正方形.

注2：严格来讲，每层还应该包含 1 个 Bias 参数，这里简洁起见省略了.

1.2. 卷积神经网络整体的时间复杂度

$$ \mathbf{Time} \sim O(\sum_{l=1}^D M_l^2 \cdot K_l^2 \cdot C_{l-1} \cdot C_l) $$

其中，

$D$ 为神经网络所具有的卷积核数，即网络的深度；

$l$ 为神经网络的第 $l$ 个卷积层；

$C_{i}$ 为神经网络的第 $l$ 个卷积层的输出通道数 $C_{out}$ ，即该层的卷积核个数；

对于第 $l$ 个卷积层而言，其输入通道数 $C_{in}$ 就是第 $l-1$ 个卷积层的输出通道数.

可见，CNN 整体的时间复杂度并不神秘，只是所有卷积层的时间复杂度累加而已.

简而言之，层内连乘，层间累加.

1.3. 示例：用 Numpy 手动简单实现二维卷积

假设 Stride = 1, Padding = 0, img 和 kernel 都是 np.ndarray.

def conv2d(img, kernel):
    height, width, in_channels = img.shape
    kernel_height, kernel_width, in_channels, out_channels = kernel.shape
    out_height = height - kernel_height + 1
    out_width = width - kernel_width + 1
    feature_maps = np.zeros(shape=(out_height, out_width, out_channels))
    for oc in range(out_channels):  # Iterate out_channels (# of kernels)
        for h in range(out_height): # Iterate out_height
            for w in range(out_width): # Iterate out_width
                for ic in range(in_channels):   # Iterate in_channels
                    patch = img[h: h + kernel_height, w: w + kernel_width, ic]
                    feature_maps[h, w, oc] += np.sum(patch * kernel[:, :, ic, oc])

    return feature_maps

2. 空间复杂度

空间复杂度（访存量），严格来讲包括两部分：总参数量 + 各层输出特征图.

参数量：模型所有带参数的层的权重参数总量（即模型体积，下式第一个求和表达式）
特征图：模型在实时运行过程中每层所计算出的输出特征图大小（下式第二个求和表达式）

$$ \mathbf{Space} \sim O(\sum_{l=1}^D K_l^2 \cdot C_{l-1} \cdot C_l + \sum_{l=1}^D M^2 \cdot C_l) $$

总参数量只与卷积核的尺寸$K$、通道数$C$、层数$D$ 相关，而与输入数据的大小无关.

输出特征图的空间占用比较容易，即是其空间尺寸 $M^2$ 和通道数 $C$ 的连乘.

注：实际上，有些层(例如ReLU) 其实是可以通过原位运算完成的，此时就不用统计输出特征图这一项了.

3. 复杂度对模型的影响

时间复杂度决定了模型的训练/预测时间. 如果复杂度过高，则会导致模型训练和预测耗费大量时间，既无法快速的验证想法和改善模型，也无法做到快速的预测.
空间复杂度决定了模型的参数数量. 由于维度诅咒的限制，模型的参数越多，训练模型所需的数据量就越大，而现实生活中的数据集通常不会太大，这会导致模型的训练更容易过拟合.
当我们需要裁剪模型时，由于卷积核的空间尺寸通常已经很小（3x3），而网络的深度又与模型的表征能力紧密相关，不宜过多削减，因此模型裁剪通常最先下手的地方就是通道数.

4. Inception 系列模型是如何优化复杂度的

通过五个小例子说明模型的演进过程中是如何优化复杂度的.

4.1. InceptionV1 中 1x1 卷积降维同时优化时间复杂度和空间复杂度

[1] - InceptionV1 借鉴了 Network in Network 的思想，在一个 Inception Module 中构造了四个并行的不同尺寸的卷积/池化模块（上图左），有效的提升了网络的宽度. 但是这么做也造成了网络的时间和空间复杂度的激增. 对策就是添加 1 x 1 卷积（上图右红色模块）将输入通道数先降到一个较低的值，再进行真正的卷积.
[2] - 以 InceptionV1 论文中的 (3b) 模块为例，输入尺寸为 28x28x256， 1x1 卷积核 128 个， 3x3 卷积核 192 个， 5x5 卷积核 96 个，卷积核一律采用 Same Padding 确保输出不改变尺寸.
[3] - 在 3x3 卷积分支上加入 64 个 1x1 卷积前后的时间复杂度对比如下式：

$$ \begin{matrix} \mathbf{Before:} \ 28^2 \cdot 3^2 \cdot 256 \cdot 192 = 3.5 \times 10^8 \\ \mathbf{After:} \ 28^2 \cdot 1^2 \cdot 256 \cdot 64 + 28^2 \cdot 3^2 \cdot 64 \cdot 192 = 1 \times 10^8 \end{matrix} $$

[4] - 同理，在 5x5 卷积分支上加入 64 个 1x1 卷积前后的时间复杂度对比如下式：

$$ \begin{matrix} \mathbf{Before:} \ 28^2 \cdot 5^2 \cdot 256 \cdot 96 = 4.8 \times 10^8 \\ \mathbf{After:} \ 28^2 \cdot 1^2 \cdot 256 \cdot 64 + 28^2 \cdot 5^2 \cdot 64 \cdot 192 = 1.3 \times 10^8 \end{matrix} $$

[5] - 可见，使用 1x1 卷积降维可以降低时间复杂度3倍以上. 该层完整的运算量可以在论文中查到，为 300 M，即 $3 \times 10^8$ .

[6] - 另一方面，我们同样可以简单分析一下这一层参数量在使用 1x1 卷积前后的变化. 可以看到，由于 1x1 卷积的添加，3x3 和 5x5 卷积核的参数量得以降低 4 倍，因此本层的参数量从 1000K 降低到 300K 左右.

$$ \mathbf{Before:} \ x = \begin{cases} 1^2 \cdot 256 \cdot 128 \\ 3^2 \cdot 256 \cdot 192 \\ 5^2 \cdot 256 \cdot 196 \end{cases} $$

$$ \mathbf{After:} \ x = \begin{cases} 1^2 \cdot 256 \cdot 128 \\ 1^2 \cdot 256 \cdot 64 \\ 3^2 \cdot 64 \cdot 196 \\ 1^2 \cdot 256 \cdot 64 \\ 5^2 \cdot 64 \cdot 96 \\ 1^2 \cdot 256 \cdot 64 \end{cases} $$

4.2. InceptionV1 中使用 GAP 代替 Flatten

[1] - 全连接层可以视为一种特殊的卷积层，其卷积核尺寸 $K$ 与输入矩阵尺寸 $X$ 一模一样. 每个卷积核的输出特征图是一个标量点，即 $M = 1$ . 复杂度分析如下：$

$$ \mathbf{Time} \sim O(1^2 \cdot X^2 \cdot C_{in} \cdot C_{out}) $$

$$ \mathbf{Space} \sim O(X^2 \cdot C_{in} \cdot C_{out}) $$

[2] - 可见，与真正的卷积层不同，全连接层的空间复杂度与输入数据的尺寸密切相关. 因此如果输入图像尺寸越大，模型的体积也就会越大，这显然是不可接受的. 例如早期的VGG系列模型，其 90% 的参数都耗费在全连接层上.

[3] - InceptionV1 中使用的全局平均池化 GAP 改善了这个问题. 由于每个卷积核输出的特征图在经过全局平均池化后都会直接精炼成一个标量点，因此全连接层的复杂度不再与输入图像尺寸有关，运算量和参数数量都得以大规模削减. 复杂度分析如下：

$$ \mathbf{Time} \sim O(C_{in} \cdot C_{out}) $$

$$ \mathbf{Space} \sim O(C_{in} \cdot C_{out}) $$

GAP(Global Average Pooling)的方法可以代替FC(全连接). 思想就是：用 feature map 直接表示属于某个类的 confidence map，比如有10个类，就在最后输出10个 feature map，每个feature map中的值加起来求平均值，然后把得到的这些平均值直接作为属于某个类别的 confidence value，再输入softmax中分类，更重要的是实验效果并不比用 FC 差，所以全连接层的分类器的作用就可以被pool层合理代替掉.

而且，全连接层参数冗余（仅全连接层参数就可占整个网络参数60%-80%），计算量会集中在这些参数的计算上，而且随着你的层数的增加，你的计算成本越来越大，如果是非GPU的机器在计算的过程中会非常非常吃亏.

4.3. InceptionV2 中使用两个 3x3 卷积级联替代 5x5 卷积分支

卷积感受野不变.

[1] - 根据上面提到的二维卷积输入输出尺寸关系公式，可知：对于同一个输入尺寸，单个 5x5 卷积的输出与两个 3x3 卷积级联输出的尺寸完全一样，即感受野相同.
[2] - 同样根据上面提到的复杂度分析公式，可知：这种替换能够非常有效的降低时间和空间复杂度. 我们可以把辛辛苦苦省出来的这些复杂度用来提升模型的深度和宽度，使得我们的模型能够在复杂度不变的前提下，具有更大的容量，爽爽的.
同样以 InceptionV1 里的 (3b) 模块为例，替换前后的 5x5 卷积分支复杂度如下：

$$ \begin{matrix} \mathbf{Before:} \ 28^2 \cdot 1^2 \cdot 256 \cdot 64 + 28^2 \cdot 5^2 \cdot 64 \cdot 96 = 1.3 \times 10^8 \\ \mathbf{After:} \ 28^2 \cdot 1^2 \cdot 256 \cdot 64 + 28^2 \cdot 3^2 \cdot 64 \cdot 192 \cdot 2 = 1.0 \times 10^8 \end{matrix} $$

4.4. InceptionV3 中使用 Nx1 与 1xN 卷积级联替代 NxN 卷积

[1] - InceptionV3 中提出了卷积的 Factorization，在确保感受野不变的前提下进一步简化.

[2] - 复杂度的改善同理可得，不再赘述.

4.5. Xception 中使用 Depth-wise Separable Convolution

[1] - 我们之前讨论的都是标准卷积运算，每个卷积核都对输入的所有通道进行卷积.

[2] - Xception 模型挑战了这个思维定势，它让每个卷积核只负责输入的某一个通道，这就是所谓的 Depth-wise Separable Convolution.

[3] - 从输入通道的视角看，标准卷积中每个输入通道都会被所有卷积核蹂躏一遍，而 Xception 中每个输入通道只会被对应的一个卷积核扫描，降低了模型的冗余度.

[4] - 标准卷积与可分离卷积的时间复杂度对比：可以看到本质上是把连乘转化成为相加.

$$ \begin{matrix} \mathbf{Standard \ Conv - \ Time} \sim O(M^2 \cdot K^2 \cdot C_{in} \cdot C_{out}) \\ \mathbf{Depthwise \ Separable \ Conv - Time} \sim O(M^2 \cdot K^2 \cdot C_{in} + M^2 \cdot C_{in} \cdot C_{out}) \end{matrix} $$

5. 总结

通过上面的推导和经典模型的案例分析，我们可以清楚的看到其实很多创新点都是围绕模型复杂度的优化展开的，其基本逻辑就是乘变加. 模型的优化换来了更少的运算次数和更少的参数数量，一方面促使我们能够构建更轻更快的模型(例如MobileNet)，一方面促使我们能够构建更深更宽的网络(例如Xception)，提升模型的容量，打败各种大怪兽，欧耶~

6. 参考论文

[1] - Convolutional Neural Networks at Constrained Time Cost

[2] - Going Deeper with Convolutions

[3] - Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift

[4] - Rethinking the Inception Architecture for Computer Vision

[5] - Xception: Deep Learning with Depthwise Separable Convolutions

[6] - Roofline Model与深度学习模型的性能分析

Last modification：January 21st, 2019 at 09:27 pm

暂无相关推荐

卷积神经网络的复杂度分析[转]

AIHGF • 2019 年 01 月 21 日

原文：卷积神经网络的复杂度分析 - 知乎 - 2018.08.16
作者：Michael Yuan

1. 时间复杂度

时间复杂度，即模型的运算次数，可用 FLOPs 衡量，也就是浮点运算次数(FLoating-point OPerations).

1.1. 单个卷积层的时间复杂度

$$ \mathbf{Time} \sim O(M^2 \cdot K^2 \cdot C_{in} \cdot C_{out}) $$

其中，

$M$ 为每个卷积核输出特征图(Feature Map) 的边长；

$K$ 为每个卷积核(Kernel) 的边长；

$C_{in}$ 为每个卷积核的通道数，即输入通道数，也就是上一网络层的输出通道数；

$C_{out}$ 为当前卷积层所具有的卷积核个数，即输出通道数.

可见，每个卷积核的时间复杂度由输出特征图面积 $M^2$、卷积核面积$K^2$、输入通道数$C_{in}$ 和输出通道数 $C_{out}$ 完全决定的.

其中，输出特征图尺寸本身又由输入矩阵尺寸 $X$、卷积核尺寸 $K$、Padding，步长(Stride) 这四个参数所决定的，表示如下：

$$ M = \frac{(X-K+2*Padding)}{Stride} + 1 $$

注1：为了简化表达式中的变量个数，这里统一假设输入和卷积核的形状都是正方形.

注2：严格来讲，每层还应该包含 1 个 Bias 参数，这里简洁起见省略了.

1.2. 卷积神经网络整体的时间复杂度

$$ \mathbf{Time} \sim O(\sum_{l=1}^D M_l^2 \cdot K_l^2 \cdot C_{l-1} \cdot C_l) $$

其中，

$D$ 为神经网络所具有的卷积核数，即网络的深度；

$l$ 为神经网络的第 $l$ 个卷积层；

$C_{i}$ 为神经网络的第 $l$ 个卷积层的输出通道数 $C_{out}$ ，即该层的卷积核个数；

对于第 $l$ 个卷积层而言，其输入通道数 $C_{in}$ 就是第 $l-1$ 个卷积层的输出通道数.

可见，CNN 整体的时间复杂度并不神秘，只是所有卷积层的时间复杂度累加而已.

简而言之，层内连乘，层间累加.

1.3. 示例：用 Numpy 手动简单实现二维卷积

假设 Stride = 1, Padding = 0, img 和 kernel 都是 np.ndarray.

def conv2d(img, kernel):
    height, width, in_channels = img.shape
    kernel_height, kernel_width, in_channels, out_channels = kernel.shape
    out_height = height - kernel_height + 1
    out_width = width - kernel_width + 1
    feature_maps = np.zeros(shape=(out_height, out_width, out_channels))
    for oc in range(out_channels):  # Iterate out_channels (# of kernels)
        for h in range(out_height): # Iterate out_height
            for w in range(out_width): # Iterate out_width
                for ic in range(in_channels):   # Iterate in_channels
                    patch = img[h: h + kernel_height, w: w + kernel_width, ic]
                    feature_maps[h, w, oc] += np.sum(patch * kernel[:, :, ic, oc])

    return feature_maps

2. 空间复杂度

空间复杂度（访存量），严格来讲包括两部分：总参数量 + 各层输出特征图.

参数量：模型所有带参数的层的权重参数总量（即模型体积，下式第一个求和表达式）
特征图：模型在实时运行过程中每层所计算出的输出特征图大小（下式第二个求和表达式）

$$ \mathbf{Space} \sim O(\sum_{l=1}^D K_l^2 \cdot C_{l-1} \cdot C_l + \sum_{l=1}^D M^2 \cdot C_l) $$

总参数量只与卷积核的尺寸$K$、通道数$C$、层数$D$ 相关，而与输入数据的大小无关.

输出特征图的空间占用比较容易，即是其空间尺寸 $M^2$ 和通道数 $C$ 的连乘.

注：实际上，有些层(例如ReLU) 其实是可以通过原位运算完成的，此时就不用统计输出特征图这一项了.

3. 复杂度对模型的影响

时间复杂度决定了模型的训练/预测时间. 如果复杂度过高，则会导致模型训练和预测耗费大量时间，既无法快速的验证想法和改善模型，也无法做到快速的预测.
空间复杂度决定了模型的参数数量. 由于维度诅咒的限制，模型的参数越多，训练模型所需的数据量就越大，而现实生活中的数据集通常不会太大，这会导致模型的训练更容易过拟合.
当我们需要裁剪模型时，由于卷积核的空间尺寸通常已经很小（3x3），而网络的深度又与模型的表征能力紧密相关，不宜过多削减，因此模型裁剪通常最先下手的地方就是通道数.

4. Inception 系列模型是如何优化复杂度的

通过五个小例子说明模型的演进过程中是如何优化复杂度的.

4.1. InceptionV1 中 1x1 卷积降维同时优化时间复杂度和空间复杂度

[4] - 同理，在 5x5 卷积分支上加入 64 个 1x1 卷积前后的时间复杂度对比如下式：

[5] - 可见，使用 1x1 卷积降维可以降低时间复杂度3倍以上. 该层完整的运算量可以在论文中查到，为 300 M，即 $3 \times 10^8$ .

$$ \mathbf{Before:} \ x = \begin{cases} 1^2 \cdot 256 \cdot 128 \\ 3^2 \cdot 256 \cdot 192 \\ 5^2 \cdot 256 \cdot 196 \end{cases} $$

4.2. InceptionV1 中使用 GAP 代替 Flatten

$$ \mathbf{Time} \sim O(1^2 \cdot X^2 \cdot C_{in} \cdot C_{out}) $$

$$ \mathbf{Space} \sim O(X^2 \cdot C_{in} \cdot C_{out}) $$

$$ \mathbf{Time} \sim O(C_{in} \cdot C_{out}) $$

$$ \mathbf{Space} \sim O(C_{in} \cdot C_{out}) $$

4.3. InceptionV2 中使用两个 3x3 卷积级联替代 5x5 卷积分支

卷积感受野不变.

4.4. InceptionV3 中使用 Nx1 与 1xN 卷积级联替代 NxN 卷积

[1] - InceptionV3 中提出了卷积的 Factorization，在确保感受野不变的前提下进一步简化.

[2] - 复杂度的改善同理可得，不再赘述.

4.5. Xception 中使用 Depth-wise Separable Convolution

[1] - 我们之前讨论的都是标准卷积运算，每个卷积核都对输入的所有通道进行卷积.

[2] - Xception 模型挑战了这个思维定势，它让每个卷积核只负责输入的某一个通道，这就是所谓的 Depth-wise Separable Convolution.

[4] - 标准卷积与可分离卷积的时间复杂度对比：可以看到本质上是把连乘转化成为相加.

5. 总结

6. 参考论文

[1] - Convolutional Neural Networks at Constrained Time Cost

[2] - Going Deeper with Convolutions

[3] - Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift

[4] - Rethinking the Inception Architecture for Computer Vision

[5] - Xception: Deep Learning with Depthwise Separable Convolutions

[6] - Roofline Model与深度学习模型的性能分析

卷积神经网络的复杂度分析[转]

1. 时间复杂度

1.1. 单个卷积层的时间复杂度

1.2. 卷积神经网络整体的时间复杂度

1.3. 示例：用 Numpy 手动简单实现二维卷积

2. 空间复杂度

3. 复杂度对模型的影响

4. Inception 系列模型是如何优化复杂度的

4.1. InceptionV1 中 1x1 卷积降维同时优化时间复杂度和空间复杂度

4.2. InceptionV1 中使用 GAP 代替 Flatten

4.3. InceptionV2 中使用两个 3x3 卷积级联替代 5x5 卷积分支

4.4. InceptionV3 中使用 Nx1 与 1xN 卷积级联替代 NxN 卷积

4.5. Xception 中使用 Depth-wise Separable Convolution

5. 总结

6. 参考论文

※相关文章推荐※

※最新文章推荐※

Leave a Comment Cancel reply

卷积神经网络的复杂度分析[转]

1. 时间复杂度

1.1. 单个卷积层的时间复杂度

1.2. 卷积神经网络整体的时间复杂度

1.3. 示例：用 Numpy 手动简单实现二维卷积

2. 空间复杂度

3. 复杂度对模型的影响

4. Inception 系列模型是如何优化复杂度的

4.1. InceptionV1 中 1x1 卷积降维同时优化时间复杂度和空间复杂度

4.2. InceptionV1 中使用 GAP 代替 Flatten

4.3. InceptionV2 中使用两个 3x3 卷积级联替代 5x5 卷积分支

4.4. InceptionV3 中使用 Nx1 与 1xN 卷积级联替代 NxN 卷积

4.5. Xception 中使用 Depth-wise Separable Convolution

5. 总结

6. 参考论文