卷積網絡複雜度分析方法及其在Inception系列網絡中的實際展現
轉載自知乎：卷積神經網絡的複雜度分析
之前的Inception學習部落格：
『TensorFlow』讀書筆記_Inception_V3_上
『TensorFlow』讀書筆記_Inception_V3_下
一、時間複雜度
即模型的運算次數，可用FLOPs衡量，也就是浮點運算次數（FLoating-point OPerations）。
單個卷積層的時間複雜度
Time~O(M2·K2·Cin·Cout)
M：輸出特征圖邊長
K：卷積核尺寸
C：通道數目
輸出邊長M計算公式為：
M = (X - K + 2*Padding)//Stride + 1
- 注1：為了簡化表達式中的變量個數，這裡統一假設輸入和卷積核的形狀都是正方形
- 注2：嚴格來講每層應該還包含 1 個 參數，這裡為了簡潔就省略了
『高性能模型』卷積複雜度以及Inception系列 - 注3：TensorFlow中SAME形式輸出為(X/Stride)上取整，因為TF中預設總共填充K/2，注意不需要進行2*Padding
下圖展示了單個Cout的上單個點的計算示意，需要重複計算：Cout·每張輸出特征圖上像素數次。
卷積神經網絡整體複雜度
Time~O(∑l=1 M2·K2·Cl-1·Cl)
l表示層編号，實質就是對各個層求和。
卷積層實作可以很好的看清實作機理：out層、out長寬、in層循環，循環體内k2級别運算：
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
二、空間複雜度
空間複雜度（訪存量），嚴格來講包括兩部分：總參數量 + 各層輸出特征圖。
- 參數量：模型所有帶參數的層的權重參數總量（即模型體積，下式第一個求和表達式）
- 特征：模型在實時運作過程中每層所計算出的輸出特征圖大小（下式第二個求和表達式）
Space~O(∑K2·Cl-1·Cl + ∑M2·Cl)
M：輸出特征圖邊長
K：卷積核尺寸
C：通道數目
三、複雜度對模型的影響
時間複雜度決定了模型的訓練/預測時間。如果複雜度過高，則會導緻模型訓練和預測耗費大量時間，既無法快速的驗證想法和改善模型，也無法做到快速的預測。
空間複雜度決定了模型的參數數量。由于次元詛咒的限制，模型的參數越多，訓練模型所需的資料量就越大，而現實生活中的資料集通常不會太大，這會導緻模型的訓練更容易過拟合。
當我們需要裁剪模型時，由于卷積核的空間尺寸通常已經很小（3x3），而網絡的深度又與模型的表征能力緊密相關，不宜過多削減，是以模型裁剪通常最先下手的地方就是通道數。
四、Inception系列優化思路
1、Inception_v1：1*1卷積降維同時優化時間複雜度和空間複雜度
InceptionV1 借鑒了 Network in Network 的思想，在一個 Inception Module 中構造了四個并行的不同尺寸的卷積/池化子產品（上圖左），有效的提升了網絡的寬度。但是這麼做也造成了網絡的時間和空間複雜度的激增。對策就是添加 1 x 1 卷積（上圖右紅色子產品）将輸入通道數先降到一個較低的值，再進行真正的卷積。
在3*3卷積分支上加入64個1*1卷積前後的時間複雜度對比如下式：
同理，在5*5卷積分支上加入64個1*1卷積前後的時間複雜度對比如下式：
整個層的參數量變化如下：
2、Inception_v1：使用GAP（全局平局均池化）代替全連接配接
全連接配接層複雜度分析：X*X的輸入Flatten為X2的輸入，輸出神經元個數可以視為1*1*Cout,則：
Time~O(12·X2·Cin·Cout)
Space~O(X2·Cin·Cout + X2·Cin) ~ O(X2·Cin·Cout)
空間複雜度第一部分為權重參數，第二部分為目前輸入大小。順便一提我之前的一個誤區：全連接配接層相對卷積層其運算瓶頸不在時間複雜度，而在空間複雜度，我之前的印象裡把兩者混為一談了。
使用GAP後，首先将Cin·X2的輸入轉化為Cin，然後1*1卷積為Cout：
Time~O(Cin·Cout)
Space~O(Cin·Cout + Cin）~ O(Cin·Cout)
Space來說可能有點問題：Cin·X2的原輸入應該還是要存儲的，不過由于不涉及到卷積運算，姑且不細究。
但是注意：GAP會影響收斂速度，不過并不會影響最終的精度。
3、Inception_v2：兩個3*3卷積聯級替代5*5卷積
兩個3*3卷積聯級的感受野與單個5*5卷積相當，計算公式可見『計算機視覺』感受野和anchor，替換後時間複雜度卻可降低：
4、Inception_v3：使用N*1和1*N卷積聯級代替N*N卷積
InceptionV3 中提出了卷積的 Factorization，在確定感受野不變的前提下進一步簡化，複雜度的改善同理可得，不再贅述。
5、Xnception：使用Depth wise Separable Convolution
Xception 中每個輸入通道隻會被對應的一個卷積核掃描，降低了模型的備援度。對于深度可分離卷積Depthwise Separable 是一個 Depthwise conv 加一個 Pointwise conv，其中 Depthwise 是M2·K2·Cin，Pointwise 是M2·Cin·Cout，即：
Time~O(M2·K2·Cin + M2·Cin·Cout)