COMP5318 — Week 8 Supplement
Mathematical Foundations
Discrete 2D convolution, feature-map size arithmetic, pooling, RNN recurrence, backpropagation through time, and the gate equations of an LSTM cell.
2D convolution and feature-map size
Convolution slides a filter \(K\) of size \(F \times F\) across an input \(I\) of size \(W \times W\), producing one output value per position. With stride \(S\) and padding \(P\) the output has size
Output dimension
\[ \text{out} = \left\lfloor \frac{W - F + 2P}{S} \right\rfloor + 1 \]
The same formula applies independently to height and width.
Discrete 2D convolution
\[ (I * K)(i, j) = \sum_{u=0}^{F-1}\sum_{v=0}^{F-1} I(i+u,\, j+v)\,K(u,v) + b \]
For \(C\) input channels, the filter becomes \(F \times F \times C\) and the sum extends over channels.
Worked Example 1: convolution output size
Image \(28 \times 28\), filter \(5 \times 5\), stride 1, padding 0.
No padding
\(\text{out} = (28 - 5 + 0)/1 + 1 = 24\). Output feature map: \(24 \times 24\).
Same padding
With \(P = 2\): \(\text{out} = (28 - 5 + 4)/1 + 1 = 28\). The feature map keeps the input size.
RNN recurrence and BPTT
Simple RNN equations
\[ h_t = \tanh\!\bigl(W_{xh}\,x_t + W_{hh}\,h_{t-1} + b_h\bigr) \]
\[ y_t = W_{hy}\,h_t + b_y \]
Unroll the recurrence \(T\) steps and treat the resulting graph as a feedforward network with shared weights. Gradients of \(W_{xh}, W_{hh}, W_{hy}\) are sums of their contributions across every time-step where they are used.
The gradient of \(h_t\) with respect to \(h_0\) involves a product of Jacobians of \(\tanh\) and \(W_{hh}\). Repeated multiplication of small singular values shrinks the gradient exponentially in \(T\), which is why vanilla RNNs struggle with long-range dependencies.
LSTM gate equations
An LSTM cell stores a cell state \(C_t\) alongside the hidden state \(h_t\). At each step three gates \(f_t, i_t, o_t \in [0,1]^d\) regulate information flow.
Gates
\[ f_t = \sigma(W_f [h_{t-1}, x_t] + b_f), \quad i_t = \sigma(W_i [h_{t-1}, x_t] + b_i), \quad o_t = \sigma(W_o [h_{t-1}, x_t] + b_o) \]
Candidate and state update
\[ \tilde{C}_t = \tanh(W_C [h_{t-1}, x_t] + b_C), \qquad C_t = f_t \odot C_{t-1} + i_t \odot \tilde{C}_t \]
\(\odot\) is element-wise multiplication.
Hidden output
\[ h_t = o_t \odot \tanh(C_t) \]