點擊上方“視學算法”，選擇加"星標"或“置頂”

重磅干貨，第一時間送達

作者 | Michael Yuan@知乎（已授權）
來源 |?https://zhuanlan.zhihu.com/p/31575074

編輯丨極市平臺

導讀

在梳理CNN經典模型的過程中，作者理解到其實經典模型演進中的很多創(chuàng)新點都與改善模型計算復雜度緊密相關，因此今天就讓我們對卷積神經網絡的復雜度分析簡單總結一下。

在梳理CNN經典模型的過程中，我理解到其實經典模型演進中的很多創(chuàng)新點都與改善模型計算復雜度緊密相關，因此今天就讓我們對卷積神經網絡的復雜度分析簡單總結一下下。

本文主要關注的是針對模型本身的復雜度分析（其實并不是很復雜啦～）。如果想要進一步評估模型在計算平臺上的理論計算性能，則需要了解 Roofline Model 的相關理論，歡迎閱讀本文的進階版：?Roofline Model與深度學習模型的性能分析。（鏈接：https://zhuanlan.zhihu.com/p/34204282 ）

時間復雜度

即模型的運算次數，可用衡量，也就是浮點運算次數（FLoating-point OPerations）。

1.1 單個卷積層的時間復雜度

每個卷積核輸出特征圖??的邊長
每個卷積核?的邊長
每個卷積核的通道數，也即輸入通道數，也即上一層的輸出通道數。
本卷積層具有的卷積核個數，也即輸出通道數。
可見，每個卷積層的時間復雜度由輸出特征圖面積?、卷積核面、輸入?和輸出通道數完全決定。
其中，輸出特征圖尺寸本身又由輸入矩陣尺寸?、卷積核尺寸?、這四個參數所決定，表示如下：

注1：為了簡化表達式中的變量個數，這里統(tǒng)一假設輸入和卷積核的形狀都是正方形。
注2：嚴格來講每層應該還包含 1 個?參數，這里為了簡潔就省略了。

1.2 卷積神經網絡整體的時間復雜度

神經網絡所具有的卷積層數，也即網絡的深度。
神經網絡第個卷積層
?神經網絡第個卷積層的輸出通道數，也即該層的卷積核個數。
對于第個卷積層而言，其輸入通道數就是第個卷積層的輸出通道數。
可見，CNN整體的時間復雜度并不神秘，只是所有卷積層的時間復雜度累加而已。
簡而言之，層內連乘，層間累加。

示例：用 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

空間復雜度

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

參數量：模型所有帶參數的層的權重參數總量（即模型體積，下式第一個求和表達式）
特征圖：模型在實時運行過程中每層所計算出的輸出特征圖大?。ㄏ率降诙€求和表達式）

總參數量只與卷積核的尺寸?、通道數、層數相關，而與輸入數據的大小無關。
輸出特征圖的空間占用比較容易，就是其空間尺寸和通道數的連乘。
注：實際上有些層（例如 ReLU）其實是可以通過原位運算完成的，此時就不用統(tǒng)計輸出特征圖這一項了。

復雜度對模型的影響

時間復雜度決定了模型的訓練/預測時間。如果復雜度過高，則會導致模型訓練和預測耗費大量時間，既無法快速的驗證想法和改善模型，也無法做到快速的預測。
空間復雜度決定了模型的參數數量。由于維度詛咒的限制，模型的參數越多，訓練模型所需的數據量就越大，而現實生活中的數據集通常不會太大，這會導致模型的訓練更容易過擬合。
當我們需要裁剪模型時，由于卷積核的空間尺寸通常已經很?。?x3），而網絡的深度又與模型的表征能力緊密相關，不宜過多削減，因此模型裁剪通常最先下手的地方就是通道數。

Inception?系列模型是如何優(yōu)化復雜度的

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

4.1?中的卷積降維同時優(yōu)化時間復雜度和空間復雜度

InceptionV1 借鑒了 Network in Network 的思想，在一個 Inception Module 中構造了四個并行的不同尺寸的卷積/池化模塊（上圖左），有效的提升了網絡的寬度。但是這么做也造成了網絡的時間和空間復雜度的激增。對策就是添加 1 x 1 卷積（上圖右紅色模塊）將輸入通道數先降到一個較低的值，再進行真正的卷積。
以 InceptionV1 論文中的 (3b) 模塊為例（可以點擊上圖看超級精美的大圖），輸入尺寸為，?卷積核??個，卷積核??個，卷積核??個，卷積核一律采用 Same Padding 確保輸出不改變尺寸。
在卷積分支上加入個卷積前后的時間復雜度對比如下式：
同理，在卷積分支上加入個卷積前后的時間復雜度對比如下式：

??? ?

可見，使用卷積降維可以降低時間復雜度3倍以上。該層完整的運算量可以在論文中查到，為 300 M，即。
另一方面，我們同樣可以簡單分析一下這一層參數量在使用 1 x 1 卷積前后的變化?？梢钥吹?，由于 1 x 1 卷積的添加，3 x 3 和 5 x 5 卷積核的參數量得以降低 4 倍，因此本層的參數量從 1000 K 降低到 300 K 左右。

4.2?中使用? 代替

全連接層可以視為一種特殊的卷積層，其卷積核尺寸??與輸入矩陣尺寸?一模一樣。每個卷積核的輸出特征圖是一個標量點，即?。復雜度分析如下：
可見，與真正的卷積層不同，全連接層的空間復雜度與輸入數據的尺寸密切相關。因此如果輸入圖像尺寸越大，模型的體積也就會越大，這顯然是不可接受的。例如早期的VGG系列模型，其 90% 的參數都耗費在全連接層上。
InceptionV1 中使用的全局平均池化 GAP?改善了這個問題。由于每個卷積核輸出的特征圖在經過全局平均池化后都會直接精煉成一個標量點，因此全連接層的復雜度不再與輸入圖像尺寸有關，運算量和參數數量都得以大規(guī)模削減。復雜度分析如下：

4.3?中使用兩個卷積級聯替代卷積分支

根據上面提到的二維卷積輸入輸出尺寸關系公式，可知：對于同一個輸入尺寸，單個卷積的輸出與兩個卷積級聯輸出的尺寸完全一樣，即感受野相同。
同樣根據上面提到的復雜度分析公式，可知：這種替換能夠非常有效的降低時間和空間復雜度。我們可以把辛辛苦苦省出來的這些復雜度用來提升模型的深度和寬度，使得我們的模型能夠在復雜度不變的前提下，具有更大的容量，爽爽的。
同樣以 InceptionV1 里的 (3b) 模塊為例，替換前后的卷積分支復雜度如下：

4.4?中使用??與卷積級聯替代?卷積

InceptionV3 中提出了卷積的 Factorization，在確保感受野不變的前提下進一步簡化。
復雜度的改善同理可得，不再贅述。

4.5?中使用?

我們之前討論的都是標準卷積運算，每個卷積核都對輸入的所有通道進行卷積。
Xception 模型挑戰(zhàn)了這個思維定勢，它讓每個卷積核只負責輸入的某一個通道，這就是所謂的 Depth-wise Separable Convolution。
從輸入通道的視角看，標準卷積中每個輸入通道都會被所有卷積核蹂躪一遍，而 Xception 中每個輸入通道只會被對應的一個卷積核掃描，降低了模型的冗余度。
標準卷積與可分離卷積的時間復雜度對比：可以看到本質上是把連乘轉化成為相加。

總結

通過上面的推導和經典模型的案例分析，我們可以清楚的看到其實很多創(chuàng)新點都是圍繞模型復雜度的優(yōu)化展開的，其基本邏輯就是乘變加。模型的優(yōu)化換來了更少的運算次數和更少的參數數量，一方面促使我們能夠構建更輕更快的模型（例如MobileNet），一方面促使我們能夠構建更深更寬的網絡（例如Xception），提升模型的容量，打敗各種大怪獸，歐耶~

參考論文

https://arxiv.org/abs/1412.1710
https://arxiv.org/abs/1409.4842
https://arxiv.org/abs/1502.03167
https://arxiv.org/abs/1512.00567
https://arxiv.org/abs/1610.02357

注：本文主要關注的是針對模型本身的復雜度分析。如果想要進一步評估模型在計算平臺上的理論計算性能，則需要了解 Roofline Model 的相關理論，歡迎閱讀本文的進階版：?Roofline Model與深度學習模型的性能分析。（文章鏈接：https://zhuanlan.zhihu.com/p/34204282 ）

如果覺得有用，就請分享到朋友圈吧！

點個在看 paper不斷！