類神經網路進行convolution或pooling時，一定會遇到padding計算的問題，在經過不同大小的stride和kernel後，output的維度常常令人一知半解，在此筆記自己的理解。
Tensorflow關於padding有兩種設定，一種是SAME，另一種是VALID

1. VALID

Valid的想法很直觀，我們讓kernel在input上以s步長(strides)滑動，進行計算，同時保持kernel所覆蓋的範圍不能超出input。
因此計算上簡單的想法是，input size先扣掉最尾端的kernel size，剩餘的部份+1就是kernel anchor可以進行滑動的範圍。如果此範圍可以被strides整除，那就皆大歡喜。如果此範圍無法被strides整除，就代表剩餘的部份一定可以再放一個kernel。因此我們用取ceiling表達最後的output size。
VALID狀況下的output size計算公式：
\begin{equation}
\left \lceil{\frac{n_i - k + 1}{s}}\right \rceil = n_o
\end{equation}

2. SAME

Same的output size定義是這樣子的，
SAME狀況下的output size計算公式：
\begin{equation}
n_o = \left \lceil{\frac{n_i}{s}}\right \rceil
\end{equation}
如果設定為same，output size並不受kernel size影響，因為不管kernel size多大，都會自動補滿計算。唯一會影響output size的是步長，步長越大，output size就會按照比例縮小。
通常搞懂上面兩個公式，就可以了解網路架構的size在通過convolution和pooling之後會如何改變，剩下的細節問題會是：那Same怎麼知道要補多少padding，而且padding要怎麼補？

3. Padding

將Valid的狀況下，補上Padding，就會是Same的output size了，所以可以得到
\begin{equation}
\left \lceil{\frac{n_i + p_i - k + 1}{s}}\right \rceil = n_o = \left \lceil{\frac{n_i}{s}}\right \rceil
\end{equation}
等式的左邊是Valid補上Padding後的狀況，等式的右邊是Same的狀況。其中我們希望(p_i)盡可能小。在已知s, n_i, k的狀況下，我們希望分子盡可能小。
已知 (\left\lceil{\frac{x}{a}}\right \rceil = b) 在(a>0)的情況下，代表(b-1 < \frac{x}{a} \leq b)
因此(x = a\cdot (b-1) + 1)是我們所要尋找的等式
所以可得出
\begin{equation}
n_i + p_i - k + 1 = s\cdot (n_o - 1) + 1
\label{eq:tf_pad_2}
\end{equation}
移項得到
\begin{equation}
p_i = s\cdot (n_o - 1) + k - n_i
\label{eq:tf_pad_3}
\end{equation}
在某些情況下如果input很大，跨距s很大，output很小，同時kernel很小，pi可能是負的，因此加上max讓其最小為0而不是負數。
\begin{equation}
p_i = max(s\cdot (n_o - 1) + k - n_i, 0)
\end{equation}
接下來利用 (n_o = \left \lceil{\frac{n_i}{s}}\right \rceil)

• case1:

[n_i \text{ mod } s = 0]
在這樣的情況下，(n_o = \frac{n_i}{s})，因此
\begin{equation}
p_i = max(k - s, 0)
\end{equation}

• case2:

[n_i \text{ mod } s \neq 0]
Case2比較複雜一點，需要一點靈感
稍微思考一下，下列的式子必定成立
\begin{equation}
n_i = s\cdot\left \lceil{\frac{n_i}{s}}\right \rceil

• s \left(\left \lceil{\frac{n_i}{s}}\right \rceil -
  \left \lfloor{\frac{n_i}{s}}\right \rfloor\right)
• (n_i \text{ mod } s)
  \end{equation}
  既然其必定成立，則在(n_i \text{ mod } s \neq 0)的情況下，我們可以得到(\left
  \lceil{\frac{n_i}{s}}\right \rceil -\left \lfloor{\frac{n_i}{s}}\right \rfloor = 1)
  可以導出
  \begin{equation}
  n_i = s\cdot\left \lceil{\frac{n_i}{s}}\right \rceil
• s
• (n_i \text{ mod } s)
  \end{equation}
  接下來我們代換(n_o = \left \lceil{\frac{n_i}{s}}\right \rceil)就可以得到
  \begin{align}
  p_i &= max\left(s\cdot \left(\frac{n_i + s - (n_i \text{ mod } s)}{s}
• 1\right) + k - n_i, 0\right) \nonumber\
  &= max(n_i + s - (n_i \text{ mod } s) - s + k - n_i,0) \nonumber \
  &= max(k - (n_i \text{ mod } s),0)
  \end{align}
  總和上述兩式，就可以得到Padding總量的計算公式
  \begin{align}
  p_i =
  \begin{cases}
  max(k - s, 0), & \text{if $(n_i \text{ mod } s) = 0$} \
  max(k - (n_i \text{ mod } s),0), & \text{if $(n_i \text{ mod } s) \neq 0$}
  \end{cases}
  \end{align}

  左右分配

  得到總和之後，Padding必須平均的分配到兩端，分配方法很簡單，盡量平分，如果無法評分，則右邊比左邊多1，下面比上面多1
  pad_left = total_pad // 2
  pad_right = total_pad - pad_left

  conclusion

  以上內容來自於閱讀Tensorflow文件的理解和整理。

  Reference

  tensorflow document

  1. Notes on SAME Convolution Padding
  2. Convolution