Convolutional Neural Networks (CNN)：各層結構與序列實作

#application-case-study #deep-learning #convolutional-neural-network #backpropagation #pooling-layer

重點總覽 (Overview)

CNN 是一種特殊的 feedforward network，用 convolutional layer 取代昂貴的 fully connected layer：每個 classifier 只看輸入的一小塊 (patch) 且 共享權重 (weight sharing)，因此能用少量權重支援大量 classifier。本筆記涵蓋 LeNet-5 的三類層、它們的 forward inference 與 backpropagation 序列 C 程式，以及 minibatch 批次化。

概念	關鍵點	維度 / 公式
Convolutional layer	每個 output pixel = 所有 input map patch 的 3D convolution + activation	輸入 `X[C,H,W]`、輸出 `Y[M,H-K+1,W-K+1]`、權重 `W[M,C,K,K]`
Filter banks	每對 (input map, output map) 一組；可視為 M 個 3D filter	數量 = M × C
Subsampling / pooling	K×K 鄰域平均 → 降維，加 bias 後過 sigmoid	輸出 = `H/K × W/K`，map 數不變
Fully connected	`Y = sigmoid(W·X + b)`，等價 m 個 perceptron	W 為 `m × n`
Weight sharing	同一 filter 套用到整張 map 的不同位置	大幅減少參數量
Backprop (FC)	`∂E/∂x = Wᵀ(∂E/∂y)`；`∂E/∂w = (∂E/∂y)xᵀ` (outer product)	—
Backprop (conv)	`∂E/∂x` = 與 transposed filter 的 backward convolution	見下方公式
Minibatch	對 N 張影像累積 gradient 再更新一次權重	所有陣列多一維 `n`

為何 CNN 適合 GPU

CNN 有 高 compute-to-memory-access ratio 與 高度平行性（N、M、H、W 四層迴圈皆可平行），是 GPU 加速的理想對象。GPU kernel 實作見 16-Deep-Learning/03-GPU-Convolutional-Layer-CUDA-Kernel-and-GEMM。

CNN 動機與 LeNet-5 架構 (Motivation & LeNet-5 Architecture)

Fully connected layer 的問題：m 個輸出、n 個輸入需要 m × n 權重矩陣。影像辨識中 n（像素數）可達數百萬、m（類別/位置/尺度變化）可達數百，餵所有輸入給所有 classifier 既昂貴又浪費。
Convolutional layer 的解法：
- 每個 classifier 只取輸入的一塊 patch 做 convolution。
- 跨 classifier 共享同一組權重 (filter)，等於把同一 classifier 套用到影像不同位置。
- 輸出稱為 output feature map，每個 pixel 是一個 classifier (perceptron) 的 activation 結果。
Deep learning = 用一層層 feature extractor 的階層自動學出複雜特徵；2012 AlexNet（約 60M 參數、在 2 顆 GPU 上用 CUDA library 訓練一週）在 ImageNet 把錯誤率從 26.2% 降到 15.3%，引爆 CNN 革命。

LeNet-5（手寫數字辨識）由三類層構成：convolutional / subsampling (pooling) / fully connected。

        1@32x32   6@28x28   6@14x14   16@10x10  16@5x5   120    84    10
INPUT  ──C1───────S2────────C3────────S4────────C5──────F6────OUT
        5x5 conv  2x2 pool  5x5 conv  2x2 pool  5x5 conv FC    Gaussian
        1->6      avg       6->16     avg       16->120  120x84
        (6 banks) (subsamp) (96 banks)(subsamp)(1920 banks)

層	型態	輸入→輸出 maps	尺寸	filter banks
C1	conv	1 → 6	32×32 → 28×28	1×6 = 6
S2	pool	6 → 6	28×28 → 14×14	—
C3	conv	6 → 16	14×14 → 10×10	6×16 = 96
S4	pool	16 → 16	10×10 → 5×5	—
C5	conv	16 → 120	5×5 → 1×1	16×120 = 1920
F6	FC	120 → 84	1D	W 為 120×84
OUT	Gaussian	84 → 10	機率向量	—

Ghost cells 的處理

Chapter 7 的 convolution 需對邊界 ghost cells 做假設。LeNet-5 改用「捨棄邊緣」：每維各砍掉兩端共 4 個 (top/bottom/left/right 各 2)，所以 5×5 filter 把 32×32 變成 28×28，即輸出尺寸 H - K + 1。

Convolutional Layer Forward Inference

資料佈局（皆 row-major 線性化，見 03-Multidimensional-Grids-And-Data/02-Mapping-Threads-to-Multidimensional-Data）：
- X[C, H, W]：C = input feature map 數（channel），最高維選 channel。
- Y[M, H-K+1, W-K+1]：M = output feature map 數。
- W[M, C, K, K]：共 M × C 個 2D filter；W[m,c,_,_] 用於 input map X[c] 計算 output map Y[m]。
每個 output map = 一個 3D convolution：對所有 C 個 input map 做 convolution 後加總；整層 = M 個 3D convolution。

3 input maps        6 filter banks (3x2)        2 output maps
  X[0] ─┐  w(0,0)
  X[1] ─┼──► Σ conv ───────────────────────────► Y[0]
  X[2] ─┘  w(0,1),w(0,2)   (一個 3D filter bank)
  X[0] ─┐  w(1,0)
  X[1] ─┼──► Σ conv ───────────────────────────► Y[1]
  X[2] ─┘  w(1,1),w(1,2)
   每個 Y[m] pixel = Σc Σp Σq X[c,h+p,w+q]·W[m,c,p,q]

void convLayer_forward(int M, int C, int H, int W, int K,
                       float* X, float* W, float* Y) {
    int H_out = H - K + 1;
    int W_out = W - K + 1;
    for (int m = 0; m < M; m++)            // each output feature map
      for (int h = 0; h < H_out; h++)      // each output element
        for (int w = 0; w < W_out; w++) {
          Y[m, h, w] = 0;
          for (int c = 0; c < C; c++)      // sum over all input feature maps
            for (int p = 0; p < K; p++)    // KxK filter
              for (int q = 0; q < K; q++)
                Y[m, h, w] += X[c, h+p, w+q] * W[m, c, p, q];
        }
}

外三層 (m, h, w) 各產生一個 output pixel；內三層 (c, p, q) 執行 3D convolution。

Subsampling / Pooling Layer

把 K×K 鄰域的像素合併（LeNet-5 用 2×2 平均）→ 行列各減半，map 數不變。
每個 output pixel 等價一個 perceptron：取 K×K 個輸入、加 per-map bias b[m]、過 sigmoid。

void subsamplingLayer_forward(int M, int H, int W, int K,
                              float* Y, float* S) {
    for (int m = 0; m < M; m++)            // each output feature map
      for (int h = 0; h < H/K; h++)        // assumes H,W are multiples of K
        for (int w = 0; w < W/K; w++) {
          S[m, h, w] = 0.;
          for (int p = 0; p < K; p++)      // KxK input samples
            for (int q = 0; q < K; q++)
              S[m, h, w] += Y[m, K*h+p, K*w+q] / (K*K);   // average
          S[m, h, w] = sigmoid(S[m, h, w] + b[m]);        // bias + activation
        }
}

Activation 放哪裡？

若 conv layer 後面接 pooling layer，activation function 放在 pooling layer（如上 sigmoid）；若沒有 pooling，則 activation 放在 conv layer。常見替代為 ReLU：Y = X if X ≥ 0 else 0，是只放行非負值的簡單非線性 filter。

CNN Backpropagation

訓練用 SGD + backpropagation（基礎見 16-Deep-Learning/01-Machine-Learning-Foundations-Perceptrons-Backpropagation）。從最後一層算 ∂E/∂y，往前逐層傳遞：每層收到對其輸出的 gradient（即後一層的 ∂E/∂x），算出對輸入的 ∂E/∂x；若有權重再算 ∂E/∂w。

              ∂E/∂y  (= 後一層的 ∂E/∂x)
                │
   ┌────────────▼────────────┐
   │   layer (weights w)      │──► ∂E/∂w  (調整本層權重用)
   │                          │
   └────────────┬────────────┘
                ▼
              ∂E/∂x  (= 前一層的 ∂E/∂y，往前傳)

Fully connected layer：`y = w·x`

gradient	公式	直觀
對輸入	`∂E/∂x = Wᵀ (∂E/∂y)`	轉置把 row/column 角色互換，使每個 y 把貢獻傳回每個 x
對權重	`∂E/∂w = (∂E/∂y) xᵀ`	`∂E/∂y`（單欄）與 `xᵀ`（單列）的 outer product

Convolutional layer：`∂E/∂x`（backward convolution）

\frac{\partial E}{\partial x} (c, h, w) = \sum_{m = 0}^{M - 1} \sum_{p = 0}^{K - 1} \sum_{q = 0}^{K - 1} \frac{\partial E}{\partial y} (m, h - p, w - q) \cdot w (m, c, K - p, K - q)

用 h-p, w-q 的索引 = 與 transposed filter wᵀ 的 convolution：forward 時 x_{h,w} 透過某些 w 影響某些 y；backward 時這些 y 的 ∂E/∂y 須循同樣權重回傳給 x_{h,w}。

forward: x_{h,w} 影響 9 個 y (3x3 filter)
   x_{h,w} · w_{2,2} → y_{h-2,w-2}
   x_{h,w} · w_{0,0} → y_{h,w}
backward: ∂E/∂x_{h,w} 收這 9 個 y 的 ∂E/∂y (用 transposed filter)

void convLayer_backward_x_grad(int M, int C, int H_in, int W_in, int K,
                               float* dE_dY, float* W, float* dE_dX) {
    int H_out = H_in - K + 1, W_out = W_in - K + 1;
    for (int c = 0; c < C; c++)            // zero-init dE_dX
      for (int h = 0; h < H_in; h++)
        for (int w = 0; w < W_in; w++)
          dE_dX[c, h, w] = 0;
    for (int m = 0; m < M; m++)
      for (int h = 0; h < H_in; h++)
        for (int w = 0; w < W_in; w++)
          for (int c = 0; c < C; c++)
            for (int p = 0; p < K; p++)
              for (int q = 0; q < K; q++)
                if (h-p >= 0 && w-q >= 0 && h-p < H_out && w-q < W_out)
                  dE_dX[c,h,w] += dE_dY[m,h-p,w-q] * W[m,c,K-p,K-q];
}

Convolutional layer：`∂E/∂w`

\frac{\partial E}{\partial w} (m, c, p, q) = \sum_{h = 0}^{H_{o u t} - 1} \sum_{w = 0}^{W_{o u t} - 1} X (c, h + p, w + q) \cdot \frac{\partial E}{\partial y} (m, h, w)

因為每個 W(m,c) 影響 output map Y(m) 的所有 pixel，須對該 output map 全部像素累積 gradient。

void convLayer_backward_w_grad(int M, int C, int H, int W, int K,
                               float* dE_dY, float* X, float* dE_dW) {
    int H_out = H - K + 1, W_out = W - K + 1;
    // zero-init dE_dW[M,C,K,K] ...
    for (int m = 0; m < M; m++)
      for (int h = 0; h < H_out; h++)
        for (int w = 0; w < W_out; w++)
          for (int c = 0; c < C; c++)
            for (int p = 0; p < K; p++)
              for (int q = 0; q < K; q++)
                dE_dW[m,c,p,q] += X[c,h+p,w+q] * dE_dY[m,h,w];
}

權重更新：w ← w - ε·(∂E/∂w)，ε 為 learning rate，隨 epoch 遞減以確保收斂；負號使更新方向與 gradient 相反以降低 error。
∂E/∂x 負責把 gradient 往前傳；∂E/∂w 才是調整本層權重的關鍵。

Minibatch 批次化 (Minibatch Training)

backpropagation 昂貴，不對單筆觸發，而是對一個 minibatch（N 張影像） 累積 gradient 後更新一次權重，再換下一個 minibatch；走完整個 training set 稱一個 epoch，之後 shuffle 再來。
實作上所有陣列多一維 n，並多一層 sample 迴圈。

void convLayer_batched(int N, int M, int C, int H, int W, int K,
                       float* X, float* W, float* Y) {
    int H_out = H - K + 1, W_out = W - K + 1;
    for (int n = 0; n < N; n++)            // each sample in the minibatch
      for (int m = 0; m < M; m++)          // each output feature map
        for (int h = 0; h < H_out; h++)    // each output element
          for (int w = 0; w < W_out; w++) {
            Y[n,m,h,w] = 0;
            for (int c = 0; c < C; c++)    // sum over input feature maps
              for (int p = 0; p < K; p++)
                for (int q = 0; q < K; q++)
                  Y[n,m,h,w] += X[n,c,h+p,w+q] * W[m,c,p,q];
          }
}

四層「容易」的平行性

n(samples)、m(output maps)、h、w 四層迴圈彼此獨立，總平行度 = N × M × H_out × W_out。內三層 (c, p, q) 也有平行性，但會對同一 Y 元素做 read-modify-write，需 atomic operations，故除非缺平行度否則保持序列。GPU 化見 16-Deep-Learning/03-GPU-Convolutional-Layer-CUDA-Kernel-and-GEMM。

考試/面試重點 (Exam / Test Patterns)

情境 / 關鍵字	答案 / 技巧
Conv layer 比 FC layer 省在哪	patch（少輸入）+ weight sharing（少權重），同 classifier 套到不同位置
filter bank 數量	M × C（每對 input/output map 一組）；可視為 M 個 3D filter
output feature map 尺寸	`H - K + 1`（LeNet 丟棄邊緣 ghost cells，每維各砍 K-1）
pooling 輸出尺寸 / map 數	尺寸 `H/K × W/K`，map 數不變
activation 放哪	有 pooling → 放 pooling 層；沒有 → 放 conv 層；ReLU = max(0,X)
FC backprop 公式	`∂E/∂x = Wᵀ∂E/∂y`；`∂E/∂w = ∂E/∂y · xᵀ`（outer product）
conv `∂E/∂x` 本質	與 transposed filter wᵀ 的 backward convolution（索引 `h-p, w-q`）
conv `∂E/∂w` 為何要累加	每個 `W(m,c)` 影響整張 `Y(m)`，須對所有 output pixel 累積
為何 minibatch 內三層保持序列	c/p/q 平行會對同一 Y 做 RMW，需 atomic，故除非缺平行度否則不展開
CNN 總平行度	N × M × H_out × W_out（四層 easy parallelism）
權重更新式	`w ← w - ε·∂E/∂w`，ε 隨 epoch 遞減
為何 sign→sigmoid	sign 不可微（0 處不連續），sigmoid 平滑可微以利 backprop