深度学习之---复杂性分析（参数量和计算次数）
深度学习之---复杂性分析（参数量和计算次数）
在深度学习领域，卷积神经网络（CNN）的复杂度分析是一个核心话题。本文将从时间复杂度和空间复杂度两个维度，深入探讨CNN的复杂度分析，并通过Inception系列模型的优化案例，展示如何通过创新来优化模型复杂度。
1. 时间复杂度
时间复杂度主要关注模型的运算次数，通常用浮点运算次数（FLOPs）来衡量。
1.1 单个卷积层的时间复杂度
对于单个卷积层，其时间复杂度由以下几个因素决定：
- 输出特征图的面积：记为(H \times W)
- 卷积核的面积：记为(K \times K)
- 输入通道数：记为(C_{in})
- 输出通道数：记为(C_{out})
具体来说，单个卷积层的时间复杂度可以表示为：
[O(H \times W \times K \times K \times C_{in} \times C_{out})]
其中，输出特征图的尺寸由输入矩阵尺寸、卷积核尺寸、步长和填充等因素决定。
1.2 卷积神经网络整体的时间复杂度
对于整个CNN网络，其时间复杂度是所有卷积层时间复杂度的累加。具体来说，如果网络有(L)层卷积层，第(l)层的输出通道数为(C_{out}^{(l)})，则整体时间复杂度可以表示为：
[\sum_{l=1}^{L} O(H^{(l)} \times W^{(l)} \times K^{(l)} \times K^{(l)} \times C_{in}^{(l)} \times C_{out}^{(l)})]
简而言之，层内连乘，层间累加。
示例：用Numpy手动实现二维卷积
下面是一个简单的二维卷积实现示例，假设Stride = 1, Padding = 0, img和kernel都是np.ndarray。
import numpy as np
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. 空间复杂度
空间复杂度主要关注模型的参数量和特征图的存储需求。
- 参数量：模型所有带参数的层的权重参数总量
- 特征图：模型在实时运行过程中每层所计算出的输出特征图大小
总参数量只与卷积核的尺寸、通道数、层数相关，而与输入数据的大小无关。输出特征图的空间占用是其空间尺寸和通道数的连乘。
3. 复杂度对模型的影响
- 时间复杂度决定了模型的训练/预测时间。如果复杂度过高，会导致模型训练和预测耗费大量时间，既无法快速验证想法和改善模型，也无法做到快速预测。
- 空间复杂度决定了模型的参数数量。由于维度诅咒的限制，模型的参数越多，训练模型所需的数据量就越大，而现实生活中的数据集通常不会太大，这会导致模型的训练更容易过拟合。
当需要裁剪模型时，由于卷积核的空间尺寸通常已经很小（3x3），而网络的深度又与模型的表征能力紧密相关，不宜过多削减，因此模型裁剪通常最先下手的地方就是通道数。
4. Inception系列模型的优化案例
通过五个小例子说明模型的演进过程中是如何优化复杂度的。
4.1 InceptionV1中的1x1卷积降维
InceptionV1借鉴了Network in Network的思想，在一个Inception Module中构造了四个并行的不同尺寸的卷积/池化模块。但是这么做也造成了网络的时间和空间复杂度的激增。对策就是添加1x1卷积将输入通道数先降到一个较低的值，再进行真正的卷积。
以InceptionV1论文中的(3b)模块为例，输入尺寸为(28 \times 28 \times 192)，(1 \times 1)卷积核128个，(3 \times 3)卷积核192个，(5 \times 5)卷积核32个，卷积核一律采用Same Padding确保输出不改变尺寸。
在(3 \times 3)卷积分支上加入(1 \times 1)卷积前后的时间复杂度对比如下式：
- 未使用(1 \times 1)卷积前：(28 \times 28 \times 3 \times 3 \times 192 \times 192)
- 使用(1 \times 1)卷积后：(28 \times 28 \times 3 \times 3 \times 128 \times 192)
可见，使用(1 \times 1)卷积降维可以降低时间复杂度3倍以上。该层完整的运算量可以在论文中查到，为300M，即(3 \times 10^8)。
另一方面，我们同样可以简单分析一下这一层参数量在使用(1 \times 1)卷积前后的变化。可以看到，由于(1 \times 1)卷积的添加，(3 \times 3)和(5 \times 5)卷积核的参数量得以降低4倍，因此本层的参数量从1000K降低到300K左右。
4.2 InceptionV1中使用全局平均池化GAP代替全连接层
全连接层可以视为一种特殊的卷积层，其卷积核尺寸与输入矩阵尺寸一模一样。每个卷积核的输出特征图是一个标量点，即(1 \times 1)。复杂度分析如下：
- 全连接层的空间复杂度与输入数据的尺寸密切相关。因此如果输入图像尺寸越大，模型的体积也就会越大，这显然是不可接受的。例如早期的VGG系列模型，其90%的参数都耗费在全连接层上。
InceptionV1中使用的全局平均池化GAP改善了这个问题。由于每个卷积核输出的特征图在经过全局平均池化后都会直接精炼成一个标量点，因此全连接层的复杂度不再与输入图像尺寸有关，运算量和参数数量都得以大规模削减。复杂度分析如下：
- 全局平均池化后的复杂度：(H \times W \times C_{in} \times C_{out})
4.3 InceptionV3中使用两个(3 \times 3)卷积级联替代(5 \times 5)卷积分支
根据上面提到的二维卷积输入输出尺寸关系公式，可知：对于同一个输入尺寸，单个(5 \times 5)卷积的输出与两个(3 \times 3)卷积级联输出的尺寸完全一样，即感受野相同。
同样根据上面提到的复杂度分析公式，可知：这种替换能够非常有效的降低时间和空间复杂度。我们可以把辛辛苦苦省出来的这些复杂度用来提升模型的深度和宽度，使得我们的模型能够在复杂度不变的前提下，具有更大的容量。
同样以InceptionV1里的(3b)模块为例，替换前后的(5 \times 5)卷积分支复杂度如下：
- 替换前：(28 \times 28 \times 5 \times 5 \times 192 \times 32)
- 替换后：(28 \times 28 \times 3 \times 3 \times 192 \times 32 + 28 \times 28 \times 3 \times 3 \times 32 \times 32)
4.4 InceptionV3中使用Factorization
InceptionV3提出了卷积的Factorization，在确保感受野不变的前提下进一步简化。复杂度的改善同理可得，不再赘述。
4.5 Xception中使用Depth-wise Separable Convolution
Xception模型挑战了标准卷积中每个卷积核都对输入的所有通道进行卷积的思维定势，它让每个卷积核只负责输入的某一个通道，这就是所谓的Depth-wise Separable Convolution。
从输入通道的视角看，标准卷积中每个输入通道都会被所有卷积核蹂躏一遍，而Xception中每个输入通道只会被对应的一个卷积核扫描，降低了模型的冗余度。
标准卷积与可分离卷积的时间复杂度对比：可以看到本质上是把连乘转化成为相加。
5. 总结
通过上面的推导和经典模型的案例分析，我们可以清楚地看到其实很多创新点都是围绕模型复杂度的优化展开的，其基本逻辑就是乘变加。模型的优化换来了更少的运算次数和更少的参数数量，一方面促使我们能够构建更轻更快的模型（例如MobileNet），一方面促使我们能够构建更深更宽的网络（例如Xception），提升模型的容量。