卷積神經(jīng)網(wǎng)絡(luò)的復(fù)雜度分析

1. 時(shí)間復(fù)雜度

即模型的運(yùn)算次數(shù)，可用 FLOPs衡量，也就是浮點(diǎn)運(yùn)算次數(shù)（FLoating-point OPerations）。

1.1 單個(gè)卷積層的時(shí)間復(fù)雜度

M: 每個(gè)卷積核輸出特征圖的邊長

K: 每個(gè)卷積核的邊長

Cin每個(gè)卷積核的通道數(shù)，也即輸入通道數(shù)，也即上一層的輸出通道數(shù)。

Cout本卷積層具有的卷積核個(gè)數(shù)，也即輸出通道數(shù)。

可見，每個(gè)卷積層的時(shí)間復(fù)雜度由輸出特征圖面積M^2、卷積核面積 K^2 、輸入 Cin和輸出通道數(shù) Cout 完全決定。

其中，輸出特征圖尺寸本身又由輸入矩陣尺寸X、卷積核尺寸 K 、Padding、Stride 這四個(gè)參數(shù)所決定，表示如下：

注1：為了簡化表達(dá)式中的變量個(gè)數(shù)，這里統(tǒng)一假設(shè)輸入和卷積核的形狀都是正方形。

注2：嚴(yán)格來講每層應(yīng)該還包含 1 個(gè) Bias 參數(shù)，這里為了簡潔就省略了。

1.2 卷積神經(jīng)網(wǎng)絡(luò)整體的時(shí)間復(fù)雜度

D神經(jīng)網(wǎng)絡(luò)所具有的卷積層數(shù)，也即網(wǎng)絡(luò)的深度。

l神經(jīng)網(wǎng)絡(luò)第 l 個(gè)卷積層

Cl神經(jīng)網(wǎng)絡(luò)第 Cl 個(gè)卷積層的輸出通道數(shù) Cout ，也即該層的卷積核個(gè)數(shù)。

對于第 l 個(gè)卷積層而言，其輸入通道數(shù) Cin 就是第 l-1 個(gè)卷積層的輸出通道數(shù)。

可見，CNN整體的時(shí)間復(fù)雜度并不神秘，只是所有卷積層的時(shí)間復(fù)雜度累加而已。

簡而言之，層內(nèi)連乘，層間累加。

示例：用 Numpy 手動(dòng)簡單實(shí)現(xiàn)二維卷積

假設(shè) 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. 空間復(fù)雜度

空間復(fù)雜度（訪存量），嚴(yán)格來講包括兩部分：總參數(shù)量 + 各層輸出特征圖。

• 參數(shù)量：模型所有帶參數(shù)的層的權(quán)重參數(shù)總量（即模型體積，下式第一個(gè)求和表達(dá)式）

• 特征圖：模型在實(shí)時(shí)運(yùn)行過程中每層所計(jì)算出的輸出特征圖大小（下式第二個(gè)求和表達(dá)式）

• 總參數(shù)量只與卷積核的尺寸 K 、通道數(shù) C 、層數(shù) D 相關(guān)，而與輸入數(shù)據(jù)的大小無關(guān)。

• 輸出特征圖的空間占用比較容易，就是其空間尺寸 M^2 和通道數(shù) C 的連乘。

• 注：實(shí)際上有些層（例如 ReLU）其實(shí)是可以通過原位運(yùn)算完成的，此時(shí)就不用統(tǒng)計(jì)輸出特征圖這一項(xiàng)了。

  
  

3. 復(fù)雜度對模型的影響

時(shí)間復(fù)雜度決定了模型的訓(xùn)練/預(yù)測時(shí)間。如果復(fù)雜度過高，則會(huì)導(dǎo)致模型訓(xùn)練和預(yù)測耗費(fèi)大量時(shí)間，既無法快速的驗(yàn)證想法和改善模型，也無法做到快速的預(yù)測。

空間復(fù)雜度決定了模型的參數(shù)數(shù)量。由于維度詛咒的限制，模型的參數(shù)越多，訓(xùn)練模型所需的數(shù)據(jù)量就越大，而現(xiàn)實(shí)生活中的數(shù)據(jù)集通常不會(huì)太大，這會(huì)導(dǎo)致模型的訓(xùn)練更容易過擬合。

當(dāng)我們需要裁剪模型時(shí)，由于卷積核的空間尺寸通常已經(jīng)很小（3x3），而網(wǎng)絡(luò)的深度又與模型的表征能力緊密相關(guān)，不宜過多削減，因此模型裁剪通常最先下手的地方就是通道數(shù)。

4. Inception系列模型是如何優(yōu)化復(fù)雜度的

通過五個(gè)小例子說明模型的演進(jìn)過程中是如何優(yōu)化復(fù)雜度的。

4.1 InceptionV1 中的 1X1 卷積降維同時(shí)優(yōu)化時(shí)間復(fù)雜度和空間復(fù)雜度

InceptionV1 借鑒了 Network in Network 的思想，在一個(gè) Inception Module 中構(gòu)造了四個(gè)并行的不同尺寸的卷積/池化模塊（上圖左），有效的提升了網(wǎng)絡(luò)的寬度。但是這么做也造成了網(wǎng)絡(luò)的時(shí)間和空間復(fù)雜度的激增。對策就是添加 1 x 1 卷積（上圖右紅色模塊）將輸入通道數(shù)先降到一個(gè)較低的值，再進(jìn)行真正的卷積。

以 InceptionV1 論文中的 (3b) 模塊為例（可以點(diǎn)擊上圖看超級精美的大圖），輸入尺寸為 28x28x256， 1x1 卷積核 128 個(gè), 3x3 卷積核 192 個(gè)， 5x5 卷積核 96 個(gè)，卷積核一律采用 Same Padding 確保輸出不改變尺寸。

在 3x3 卷積分支上加入 64 個(gè) 1x1 卷積前后的時(shí)間復(fù)雜度對比如下式：

同理，在 5x5 卷積分支上加入 64 個(gè) 1x1 卷積前后的時(shí)間復(fù)雜度對比如下式：

可見，使用 1x1 卷積降維可以降低時(shí)間復(fù)雜度3倍以上。該層完整的運(yùn)算量可以在論文中查到，為 300 M，即 3x10^8 。

另一方面，我們同樣可以簡單分析一下這一層參數(shù)量在使用 1 x 1 卷積前后的變化。可以看到，由于 1 x 1 卷積的添加，3 x 3 和 5 x 5 卷積核的參數(shù)量得以降低 4 倍，因此本層的參數(shù)量從 1000 K 降低到 300 K 左右。

4.2 InceptionV1 中使用GAP代替 Flatten

全連接層可以視為一種特殊的卷積層，其卷積核尺寸 K 與輸入矩陣尺寸 X 一模一樣。每個(gè)卷積核的輸出特征圖是一個(gè)標(biāo)量點(diǎn)，即 M = 1 。復(fù)雜度分析如下：

可見，與真正的卷積層不同，全連接層的空間復(fù)雜度與輸入數(shù)據(jù)的尺寸密切相關(guān)。因此如果輸入圖像尺寸越大，模型的體積也就會(huì)越大，這顯然是不可接受的。例如早期的VGG系列模型，其 90% 的參數(shù)都耗費(fèi)在全連接層上。

InceptionV1 中使用的全局平均池化 GAP 改善了這個(gè)問題。由于每個(gè)卷積核輸出的特征圖在經(jīng)過全局平均池化后都會(huì)直接精煉成一個(gè)標(biāo)量點(diǎn)，因此全連接層的復(fù)雜度不再與輸入圖像尺寸有關(guān)，運(yùn)算量和參數(shù)數(shù)量都得以大規(guī)模削減。復(fù)雜度分析如下：

4.3 InceptionV2 中使用兩個(gè) 3x3 卷積級聯(lián)替代 5x5 卷積分支

根據(jù)上面提到的二維卷積輸入輸出尺寸關(guān)系公式，可知：對于同一個(gè)輸入尺寸，單個(gè) 5x5 卷積的輸出與兩個(gè) 3x3 卷積級聯(lián)輸出的尺寸完全一樣，即感受野相同。

4.4 InceptionV3 中使用 1xN 與 Nx1 卷積級聯(lián)替代 NxN 卷積

InceptionV3 中提出了卷積的 Factorization，在確保感受野不變的前提下進(jìn)一步簡化。

復(fù)雜度的改善同理可得，不再贅述。

4.5 Xception 中使用 Depth-wise Separable Convolution

5. 總結(jié)

參考論文

Convolutional Neural Networks at Constrained Time Cost
Going Deeper with Convolutions
Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
Rethinking the Inception Architecture for Computer Vision
Xception: Deep Learning with Depthwise Separable Convolutions

點(diǎn)贊三連，支持一下吧↓