ml.lab
Python sleeps until you run code
08 LSTMs

Lesson 4 of 6

The forward and backward pass

Run an LSTM over a whole sequence while saving what the backward pass will need, derive the gradient of one step gate by gate, carry it back through time, and prove the whole thing correct with a numerical gradient check.

About 55 minutes
By the end you can
  • Run an LSTM forward over a batch of sequences and say what each cached quantity is for.

  • Derive the backward pass of one LSTM step, line by line, from the chain rule.

  • Explain why the gradient on ct\mathbf{c}_t has two parts and why the weight gradients are sums over time.

  • Carry gradients back through two steps by hand, and implement the full forward and backward pass over a sequence with a gradient check.

You can compute an LSTM step, you know why its cell path carries gradients, and you can program one by hand. To train one, you need the gradient of the loss with respect to every weight, through every step of every sequence. No library will do it for you in this module: you will derive the backward pass of one step, run it backwards through time, and check it numerically.

This is the most intricate derivation in Part 1, and also the most mechanical. Here is one step in the stacked form of the first lesson, with a=[xt,ht−1]\mathbf{a} = [\mathbf{x}_t,\allowbreak \mathbf{h}_{t-1}] the joined input: one matrix product, then the three gates and the candidate, then the memory and the output.

z=aW+b=[ zi∣zf∣zg∣zo ]one product for all four blocksit=σ(zi),ft=σ(zf),ot=σ(zo)the gatesgt=tanh⁡(zg)the candidatect=ft⊙ct−1+it⊙gtthe memoryht=ot⊙tanh⁡(ct)the output\begin{aligned} \mathbf{z} &= \mathbf{a}\mathbf{W} + \mathbf{b} = [\,\mathbf{z}_i \mid \mathbf{z}_f \mid \mathbf{z}_g \mid \mathbf{z}_o\,] && \text{one product for all four blocks} \\ \mathbf{i}_t &= \sigma(\mathbf{z}_i), \quad \mathbf{f}_t = \sigma(\mathbf{z}_f), \quad \mathbf{o}_t = \sigma(\mathbf{z}_o) && \text{the gates} \\ \mathbf{g}_t &= \tanh(\mathbf{z}_g) && \text{the candidate} \\ \mathbf{c}_t &= \mathbf{f}_t \odot \mathbf{c}_{t-1} + \mathbf{i}_t \odot \mathbf{g}_t && \text{the memory} \\ \mathbf{h}_t &= \mathbf{o}_t \odot \tanh(\mathbf{c}_t) && \text{the output} \end{aligned}

Every line of the backward pass is the chain rule applied to one of these lines. Apart from the one matrix product that computes z\mathbf{z}, every operation acts entry by entry, so its backward line is an elementwise product. If you can do backprop through a linear layer and backprop through time, you can do this. The difficulty is bookkeeping, and bookkeeping errors are silent: a wrong backward pass often still trains, just worse, and nothing tells you why. That is why the lesson ends with a gradient check and why its exercise is the main exercise of the module.

Notation: from here on the code convention is used throughout. A batch of BB examples is stored as rows, the input xt\mathbf{x}_t has shape B×mB \times m, and ht\mathbf{h}_t, ct\mathbf{c}_t and every gate have shape B×nB \times n. For any quantity qq, dq\mathrm{d}q means ∂L/∂q\partial L / \partial q, the gradient of the scalar loss LL with respect to it, which always has the same shape as qq.

Forward over a sequence, with a cache

The backward pass needs numbers from the forward pass, so the forward pass has to save them. The forward pass over a sequence is a loop: start from h0\mathbf{h}_0 and c0\mathbf{c}_0 (zeros unless the sequence continues an earlier one), apply the step TT times, and keep every output.

def lstm_forward(X, h0, c0, W, b):
    """X (B, T, m). Returns Hs (B, T, n), the final (hT, cT), and one cache per step."""
    B, T, m = X.shape
    n = W.shape[1] // 4
    h = np.zeros((B, n)) if h0 is None else h0
    c = np.zeros((B, n)) if c0 is None else c0
    Hs = np.empty((B, T, n))
    caches = []
    for t in range(T):
        h, c, cache = lstm_step(X[:, t], h, c, W, b)
        Hs[:, t] = h
        caches.append(cache)
    return Hs, (h, c), caches

The interesting part is the cache: what each step saves for the backward pass. Look ahead at what the backward lines below will need.

CachedShapeNeeded for
[xt,ht−1][\mathbf{x}_t,\allowbreak \mathbf{h}_{t-1}]B×(m+n)B \times (m + n)the weight gradient dW\mathrm{d}\mathbf{W}
ct−1\mathbf{c}_{t-1}B×nB \times nthe forget gate's gradient
it,ft,gt,ot\mathbf{i}_t,\allowbreak \mathbf{f}_t,\allowbreak \mathbf{g}_t,\allowbreak \mathbf{o}_tB×nB \times n eachproducts in the cell update, and the slopes of σ\sigma and tanh⁡\tanh
tanh⁡(ct)\tanh(\mathbf{c}_t)B×nB \times nthe output gate's gradient, and the slope of the output tanh
W\mathbf{W}(m+n)×4n(m + n) \times 4npassing the gradient to xt\mathbf{x}_t and ht−1\mathbf{h}_{t-1}

Why save the gate values rather than the pre-activations? Because both squashing functions have derivatives that are easiest to write with their outputs, as derived in module 5: if s=σ(z)s = \sigma(z) then σ′(z)=s(1−s)\sigma'(z) = s(1 - s), and if g=tanh⁡(z)g = \tanh(z) then tanh⁡′(z)=1−g2\tanh'(z) = 1 - g^2. With the output saved, each slope costs one multiplication.

The cache is also the price of training a recurrent network. Count the entries of the table, leaving out W\mathbf{W}, which is shared: (m+n)+n+4n+n=m+7n(m + n) + n + 4n + n = m + 7n numbers per example per step. So its size grows with the batch and with the sequence length TT. This is one reason models are trained on windows of limited length, the truncation of backprop through time.

One step backward, gate by gate

Now the core derivation: the gradient through one step. Five rules from module 6 do all of the work. For quantities combined entry by entry:

  1. Product, p=u⊙v\mathbf{p} = \mathbf{u} \odot \mathbf{v}: each factor gets the upstream gradient times the other factor, du=dp⊙v\mathrm{d}\mathbf{u} = \mathrm{d}\mathbf{p} \odot \mathbf{v} and dv=dp⊙u\mathrm{d}\mathbf{v} = \mathrm{d}\mathbf{p} \odot \mathbf{u}.
  2. Sum, s=u+v\mathbf{s} = \mathbf{u} + \mathbf{v}: each term gets the upstream gradient unchanged.
  3. Squashing, y=φ(z)\mathbf{y} = \varphi(\mathbf{z}) entry by entry: dz=dy⊙φ′(z)\mathrm{d}\mathbf{z} = \mathrm{d}\mathbf{y} \odot \varphi'(\mathbf{z}).
  4. Used twice: a value that feeds two places gets the sum of the gradients from both.
  5. Linear layer, z=aW+b\mathbf{z} = \mathbf{a}\mathbf{W} + \mathbf{b}: dW=a⊤dz\mathrm{d}\mathbf{W} = \mathbf{a}^\top \mathrm{d}\mathbf{z}, db\mathrm{d}\mathbf{b} is the sum of the rows of dz\mathrm{d}\mathbf{z}, and da=dz W⊤\mathrm{d}\mathbf{a} = \mathrm{d}\mathbf{z}\,\mathbf{W}^\top.

Stand at step tt during the backward pass. Two gradients arrive from later in the sequence:

  • dht\mathrm{d}\mathbf{h}_t, the total gradient on this step's output. The output ht\mathbf{h}_t is used twice, by whatever reads it at step tt (the output layer) and by the four gates of step t+1t + 1, so by rule 4 its gradient is the sum of the two contributions.
  • dct\mathrm{d}\mathbf{c}_t from step t+1t + 1, along the cell path. The cell state feeds ct+1\mathbf{c}_{t+1} directly.

From these, the step must produce the gradients for its inputs (dxt\mathrm{d}\mathbf{x}_t, dht−1\mathrm{d}\mathbf{h}_{t-1}, dct−1\mathrm{d}\mathbf{c}_{t-1}) and for the weights (dW\mathrm{d}\mathbf{W}, db\mathrm{d}\mathbf{b}). Walk the forward equations in reverse, from the output back to z\mathbf{z}, in four stages.

Stage 1: the output, ht=ot⊙tanh⁡(ct)\mathbf{h}_t = \mathbf{o}_t \odot \tanh(\mathbf{c}_t). It is a product (rule 1), so the output gate gets dht\mathrm{d}\mathbf{h}_t times the other factor, tanh⁡(ct)\tanh(\mathbf{c}_t). The other factor, tanh⁡(ct)\tanh(\mathbf{c}_t), gets dht⊙ot\mathrm{d}\mathbf{h}_t \odot \mathbf{o}_t, and passing that through the tanh (rule 3) multiplies by its slope 1−tanh⁡2(ct)1 - \tanh^2(\mathbf{c}_t):

do=dht⊙tanh⁡(ct),dct+=dht⊙ot⊙(1−tanh⁡2(ct)).\mathrm{d}\mathbf{o} = \mathrm{d}\mathbf{h}_t \odot \tanh(\mathbf{c}_t), \qquad \mathrm{d}\mathbf{c}_t \mathrel{+}= \mathrm{d}\mathbf{h}_t \odot \mathbf{o}_t \odot \big(1 - \tanh^2(\mathbf{c}_t)\big).

The +=\mathrel{+}= is rule 4. The cell state is also used twice, by ht\mathbf{h}_t and by ct+1\mathbf{c}_{t+1}, so the gradient through the output is added to the gradient that arrived along the cell path. From here on, dc\mathrm{d}\mathbf{c} means this total.

Stage 2: the cell update, ct=ft⊙ct−1+it⊙gt\mathbf{c}_t = \mathbf{f}_t \odot \mathbf{c}_{t-1} + \mathbf{i}_t \odot \mathbf{g}_t. The sum passes dc\mathrm{d}\mathbf{c} to both terms unchanged (rule 2), and each product hands each factor dc\mathrm{d}\mathbf{c} times the other factor (rule 1):

df=dc⊙ct−1,di=dc⊙gt,dg=dc⊙it,dct−1=dc⊙ft.\mathrm{d}\mathbf{f} = \mathrm{d}\mathbf{c} \odot \mathbf{c}_{t-1}, \qquad \mathrm{d}\mathbf{i} = \mathrm{d}\mathbf{c} \odot \mathbf{g}_t, \qquad \mathrm{d}\mathbf{g} = \mathrm{d}\mathbf{c} \odot \mathbf{i}_t, \qquad \mathrm{d}\mathbf{c}_{t-1} = \mathrm{d}\mathbf{c} \odot \mathbf{f}_t.

The last one is the cell path from the previous lessons, now as a line of code: the gradient sent back to the previous cell is the current one times the forget gate.

Stage 3: through the squashing functions (rule 3), from each gate back to its pre-activation, with each slope written using the saved output:

dzi=di⊙it⊙(1−it),dzf=df⊙ft⊙(1−ft),dzg=dg⊙(1−gt2),dzo=do⊙ot⊙(1−ot).\mathrm{d}\mathbf{z}_i = \mathrm{d}\mathbf{i} \odot \mathbf{i}_t \odot (1 - \mathbf{i}_t), \quad \mathrm{d}\mathbf{z}_f = \mathrm{d}\mathbf{f} \odot \mathbf{f}_t \odot (1 - \mathbf{f}_t), \quad \mathrm{d}\mathbf{z}_g = \mathrm{d}\mathbf{g} \odot (1 - \mathbf{g}_t^2), \quad \mathrm{d}\mathbf{z}_o = \mathrm{d}\mathbf{o} \odot \mathbf{o}_t \odot (1 - \mathbf{o}_t).

Place them side by side in the same order as the forward pass, dz=[dzi∣dzf∣dzg∣dzo]\mathrm{d}\mathbf{z} = [\mathrm{d}\mathbf{z}_i \mid \mathrm{d}\mathbf{z}_f \mid \mathrm{d}\mathbf{z}_g \mid \mathrm{d}\mathbf{z}_o], of shape B×4nB \times 4n.

Stage 4: the stacked linear layer, z=aW+b\mathbf{z} = \mathbf{a}\mathbf{W} + \mathbf{b} with a=[xt,ht−1]\mathbf{a} = [\mathbf{x}_t,\allowbreak \mathbf{h}_{t-1}]. This is an ordinary layer, so rule 5 applies:

dW=a⊤dz,db=∑rowsdz,da=dz W⊤.\mathrm{d}\mathbf{W} = \mathbf{a}^\top \mathrm{d}\mathbf{z}, \qquad \mathrm{d}\mathbf{b} = \textstyle\sum_{\text{rows}} \mathrm{d}\mathbf{z}, \qquad \mathrm{d}\mathbf{a} = \mathrm{d}\mathbf{z}\,\mathbf{W}^\top.

Split da\mathrm{d}\mathbf{a} (shape B×(m+n)B \times (m + n)) back into its two parts: the first mm columns are dxt\mathrm{d}\mathbf{x}_t and the last nn are dht−1\mathrm{d}\mathbf{h}_{t-1}. Check the shapes, which is the fastest way to catch a transpose in the wrong place: a⊤\mathbf{a}^\top is (m+n)×B(m + n) \times B and dz\mathrm{d}\mathbf{z} is B×4nB \times 4n, so dW\mathrm{d}\mathbf{W} is (m+n)×4n(m + n) \times 4n, the shape of W\mathbf{W}. And dz\mathrm{d}\mathbf{z} is B×4nB \times 4n times W⊤\mathbf{W}^\top, which is 4n×(m+n)4n \times (m + n), so da\mathrm{d}\mathbf{a} is B×(m+n)B \times (m + n), the shape of a\mathbf{a}.

Here is the whole step on one page, forward on the left, backward on the right:

ForwardBackward
z=aW+b\mathbf{z} = \mathbf{a}\mathbf{W} + \mathbf{b}dW=a⊤dz\mathrm{d}\mathbf{W} = \mathbf{a}^\top\mathrm{d}\mathbf{z}, db=∑rowsdz\mathrm{d}\mathbf{b} = \sum_{\text{rows}}\mathrm{d}\mathbf{z}, [dxt,dht−1]=dz W⊤[\mathrm{d}\mathbf{x}_t,\allowbreak \mathrm{d}\mathbf{h}_{t-1}] = \mathrm{d}\mathbf{z}\,\mathbf{W}^\top
i=σ(zi)\mathbf{i} = \sigma(\mathbf{z}_i), f=σ(zf)\mathbf{f} = \sigma(\mathbf{z}_f), o=σ(zo)\mathbf{o} = \sigma(\mathbf{z}_o)dzi=di⊙i⊙(1−i)\mathrm{d}\mathbf{z}_i = \mathrm{d}\mathbf{i} \odot \mathbf{i} \odot (1 - \mathbf{i}), and the same for f\mathbf{f} and o\mathbf{o}
g=tanh⁡(zg)\mathbf{g} = \tanh(\mathbf{z}_g)dzg=dg⊙(1−g2)\mathrm{d}\mathbf{z}_g = \mathrm{d}\mathbf{g} \odot (1 - \mathbf{g}^2)
ct=f⊙ct−1+i⊙g\mathbf{c}_t = \mathbf{f} \odot \mathbf{c}_{t-1} + \mathbf{i} \odot \mathbf{g}df=dc⊙ct−1\mathrm{d}\mathbf{f} = \mathrm{d}\mathbf{c} \odot \mathbf{c}_{t-1}, di=dc⊙g\mathrm{d}\mathbf{i} = \mathrm{d}\mathbf{c} \odot \mathbf{g}, dg=dc⊙i\mathrm{d}\mathbf{g} = \mathrm{d}\mathbf{c} \odot \mathbf{i}, dct−1=dc⊙f\mathrm{d}\mathbf{c}_{t-1} = \mathrm{d}\mathbf{c} \odot \mathbf{f}
ht=o⊙tanh⁡(ct)\mathbf{h}_t = \mathbf{o} \odot \tanh(\mathbf{c}_t)do=dht⊙tanh⁡(ct)\mathrm{d}\mathbf{o} = \mathrm{d}\mathbf{h}_t \odot \tanh(\mathbf{c}_t), dc=dct+dht⊙o⊙(1−tanh⁡2ct)\mathrm{d}\mathbf{c} = \mathrm{d}\mathbf{c}_t + \mathrm{d}\mathbf{h}_t \odot \mathbf{o} \odot (1 - \tanh^2\mathbf{c}_t)

Read the right column from the bottom up: that is the order the code runs in.

Go slower: Every line from the chain rule

Work with one example (one row) and one unit jj; the batch and the other units follow because every operation below is elementwise or linear. Write τj=tanh⁡(ct,j)\tau_j = \tanh(c_{t,j}).

Stage 1. ht,j=ojτjh_{t,j} = o_j \tau_j, and LL depends on ojo_j only through ht,jh_{t,j}, so ∂L∂oj=∂L∂ht,j∂ht,j∂oj=dht,j τj\frac{\partial L}{\partial o_j} = \frac{\partial L}{\partial h_{t,j}}\frac{\partial h_{t,j}}{\partial o_j} = \mathrm{d}h_{t,j}\,\tau_j. The cell state ct,jc_{t,j} affects LL through two routes, ht,jh_{t,j} and ct+1,jc_{t+1,j}, so the multivariable chain rule adds them: ∂L∂ct,j=∂L∂ct+1,j∂ct+1,j∂ct,j⏟arrives from step t+1+∂L∂ht,j∂ht,j∂ct,j,∂ht,j∂ct,j=oj (1−τj2).\frac{\partial L}{\partial c_{t,j}} = \underbrace{\frac{\partial L}{\partial c_{t+1,j}}\frac{\partial c_{t+1,j}}{\partial c_{t,j}}}_{\text{arrives from step } t+1} + \frac{\partial L}{\partial h_{t,j}}\frac{\partial h_{t,j}}{\partial c_{t,j}},\allowbreak \qquad \frac{\partial h_{t,j}}{\partial c_{t,j}} = o_j\,(1 - \tau_j^2). The first term is what step t+1t + 1 passed back (it computed it in its own stage 2); the second is the new contribution. The last equation holds because ht,j=ojtanh⁡(ct,j)h_{t,j} = o_j \tanh(c_{t,j}) with ojo_j fixed, and the slope of tanh is 1−tanh⁡21 - \tanh^2.

Stage 2. ct,j=fjct−1,j+ijgjc_{t,j} = f_j c_{t-1,j} + i_j g_j. The partial derivatives are ∂ct,j/∂fj=ct−1,j\partial c_{t,j}/\partial f_j = c_{t-1,j}, ∂ct,j/∂ij=gj\partial c_{t,j}/\partial i_j = g_j, ∂ct,j/∂gj=ij\partial c_{t,j}/\partial g_j = i_j and ∂ct,j/∂ct−1,j=fj\partial c_{t,j}/\partial c_{t-1,j} = f_j. Multiplying each by dcj\mathrm{d}c_j (the total from stage 1) gives the four lines. Within this step ct−1,jc_{t-1,j} appears only here, so dct−1,j=dcjfj\mathrm{d}c_{t-1,j} = \mathrm{d}c_j f_j is its complete gradient from step tt; step t−1t - 1 will add its own output route to it.

Stage 3. For a sigmoid gate s=σ(z)=(1+e−z)−1s = \sigma(z) = (1 + e^{-z})^{-1}, use the chain rule with the outer function u−1u^{-1} (slope −u−2-u^{-2}) and the inner function u=1+e−zu = 1 + e^{-z} (slope −e−z-e^{-z}): σ′(z)=−(1+e−z)−2⋅(−e−z)=e−z(1+e−z)2\sigma'(z) = -(1 + e^{-z})^{-2} \cdot (-e^{-z}) = \frac{e^{-z}}{(1 + e^{-z})^2}. Split that fraction into two factors: 11+e−z⋅e−z1+e−z\frac{1}{1 + e^{-z}}\cdot\frac{e^{-z}}{1 + e^{-z}}. The first factor is ss. The second is (1+e−z)−11+e−z=1−s\frac{(1 + e^{-z}) - 1}{1 + e^{-z}} = 1 - s. So σ′(z)=s(1−s)\sigma'(z) = s(1 - s) and dz=ds s(1−s)\mathrm{d}z = \mathrm{d}s\,s(1 - s). For the candidate g=tanh⁡(z)g = \tanh(z): tanh⁡′(z)=1−tanh⁡2z=1−g2\tanh'(z) = 1 - \tanh^2 z = 1 - g^2, so dz=dg (1−g2)\mathrm{d}z = \mathrm{d}g\,(1 - g^2). Each gate entry depends only on its own pre-activation entry, so there are no cross terms.

Stage 4. With a=[xt,ht−1]\mathbf{a} = [\mathbf{x}_t,\allowbreak \mathbf{h}_{t-1}], entry kk of the pre-activation is zk=∑rarWrk+bkz_k = \sum_{r} a_r W_{rk} + b_k. So ∂zk/∂Wrk=ar\partial z_k / \partial W_{rk} = a_r, ∂zk/∂bk=1\partial z_k / \partial b_k = 1 and ∂zk/∂ar=Wrk\partial z_k/\partial a_r = W_{rk}. Hence ∂L∂Wrk=ar dzk\frac{\partial L}{\partial W_{rk}} = a_r\,\mathrm{d}z_k, which for all r,kr,\allowbreak k at once is the outer product a⊤dz\mathbf{a}^\top \mathrm{d}\mathbf{z}. Next, ∂L∂bk=dzk\frac{\partial L}{\partial b_k} = \mathrm{d}z_k. And ara_r feeds every zkz_k, so it collects one term from each: ∂L∂ar=∑kWrk dzk\frac{\partial L}{\partial a_r} = \sum_k W_{rk}\,\mathrm{d}z_k, which is entry rr of dz W⊤\mathrm{d}\mathbf{z}\,\mathbf{W}^\top.

The batch. Each row is an independent example that shares W\mathbf{W} and b\mathbf{b}, so the weight gradients are sums over rows: ∑rowsarow⊤ dzrow=a⊤dz\sum_{\text{rows}} \mathbf{a}_\text{row}^\top\,\mathrm{d}\mathbf{z}_\text{row} = \mathbf{a}^\top\mathrm{d}\mathbf{z} with a\mathbf{a} and dz\mathrm{d}\mathbf{z} as full matrices, and db\mathrm{d}\mathbf{b} is the sum of the rows of dz\mathrm{d}\mathbf{z}. The input gradients dxt\mathrm{d}\mathbf{x}_t, dht−1\mathrm{d}\mathbf{h}_{t-1}, dct−1\mathrm{d}\mathbf{c}_{t-1} stay one row per example.

To recap before the numbers: stage 1 splits the output product and adds the output route to the cell's gradient; stage 2 splits the cell update; stage 3 passes through the squashing functions using the saved gate values; stage 4 is a linear layer.

One step with numbers

Take the one-unit cell from the first lesson's worked example. Its weights (ww on xtx_t, uu on ht−1h_{t-1}, bb) were, listed now in the stacked order with the input gate first:

wwuubb
input2−2-2−1-1
forget120
candidate100
output−1-12−1-1

With xt=1x_t = 1, ht−1=0.5h_{t-1} = 0.5 and ct−1=1.5c_{t-1} = 1.5 the forward pass gave i=0.5i = 0.5, f=0.8808f = 0.8808, g=0.7616g = 0.7616, o=0.2689o = 0.2689, ct=1.7020c_t = 1.7020, tanh⁡(ct)=0.9357\tanh(c_t) = 0.9357 and ht=0.2516h_t = 0.2516. Suppose the loss is L=htL = h_t, so dht=1\mathrm{d}h_t = 1, and nothing comes along the cell path, dct=0\mathrm{d}c_t = 0. (Every number below is rounded to four decimals for printing but computed from unrounded values, so redoing a line from the printed numbers can change its last digit.)

Stage 1. The output gate gets do=dhttanh⁡(ct)=1×0.9357=0.9357\mathrm{d}o = \mathrm{d}h_t \tanh(c_t) = 1 \times 0.9357 = 0.9357. The cell gets the output route: 1−0.93572=1−0.8755=0.12451 - 0.9357^2 = 1 - 0.8755 = 0.1245, so dc=0+1×0.2689×0.1245≈0.0335\mathrm{d}c = 0 + 1 \times 0.2689 \times 0.1245 \approx 0.0335.

Stage 2. Each factor of the cell update gets dc\mathrm{d}c times its partner: df=0.0335×1.5≈0.0502\mathrm{d}f = 0.0335 \times 1.5 \approx 0.0502, di=0.0335×0.7616≈0.0255\mathrm{d}i = 0.0335 \times 0.7616 \approx 0.0255, dg=0.0335×0.5≈0.0167\mathrm{d}g = 0.0335 \times 0.5 \approx 0.0167, and the cell path gets dct−1=0.0335×0.8808≈0.0295\mathrm{d}c_{t-1} = 0.0335 \times 0.8808 \approx 0.0295.

Stage 3. First the four slopes: i(1−i)=0.5×0.5=0.25i(1 - i) = 0.5 \times 0.5 = 0.25, f(1−f)=0.8808×0.1192=0.1050f(1 - f) = 0.8808 \times 0.1192 = 0.1050, 1−g2=1−0.5800=0.42001 - g^2 = 1 - 0.5800 = 0.4200, o(1−o)=0.2689×0.7311=0.1966o(1 - o) = 0.2689 \times 0.7311 = 0.1966. Then multiply: dzi=0.0255×0.25≈0.0064\mathrm{d}z_i = 0.0255 \times 0.25 \approx 0.0064, dzf=0.0502×0.1050≈0.0053\mathrm{d}z_f = 0.0502 \times 0.1050 \approx 0.0053, dzg=0.0167×0.4200≈0.0070\mathrm{d}z_g = 0.0167 \times 0.4200 \approx 0.0070, dzo=0.9357×0.1966≈0.1840\mathrm{d}z_o = 0.9357 \times 0.1966 \approx 0.1840.

Stage 4. Each gate's pre-activation is wxt+uht−1+bw x_t + u h_{t-1} + b, so its ww gets dz×xt=dz×1\mathrm{d}z \times x_t = \mathrm{d}z \times 1, its uu gets dz×ht−1=dz×0.5\mathrm{d}z \times h_{t-1} = \mathrm{d}z \times 0.5, and its bb gets dz\mathrm{d}z:

gatedz\mathrm{d}zdw=dz⋅1\mathrm{d}w = \mathrm{d}z \cdot 1du=dz⋅0.5\mathrm{d}u = \mathrm{d}z \cdot 0.5db=dz\mathrm{d}b = \mathrm{d}z
input0.00640.00640.00320.0064
forget0.00530.00530.00260.0053
candidate0.00700.00700.00350.0070
output0.18400.18400.09200.1840

Going the other way through the weights, xtx_t feeds every gate through its ww and ht−1h_{t-1} through its uu, so each collects four terms:

dxt=2(0.0064)+1(0.0053)+1(0.0070)−1(0.1840)=0.0128+0.0053+0.0070−0.1840≈−0.159,dht−1=−2(0.0064)+2(0.0053)+0(0.0070)+2(0.1840)=−0.0128+0.0106+0+0.3680≈0.366.\begin{aligned} \mathrm{d}x_t &= 2(0.0064) + 1(0.0053) + 1(0.0070) - 1(0.1840) = 0.0128 + 0.0053 + 0.0070 - 0.1840 \approx -0.159, \\ \mathrm{d}h_{t-1} &= -2(0.0064) + 2(0.0053) + 0(0.0070) + 2(0.1840) = -0.0128 + 0.0106 + 0 + 0.3680 \approx 0.366. \end{aligned}

The numbers tell a story. The output gate's pre-activation received dzo=0.184\mathrm{d}z_o = 0.184, while the cell received only dc=0.0335\mathrm{d}c = 0.0335, for two reasons: the output gate was mostly closed (o=0.27o = 0.27), and the cell was saturated (tanh⁡(1.70)=0.94\tanh(1.70) = 0.94, where the slope of tanh is only 0.120.12). A large cell state shields itself from gradients arriving through the output. The cell path from later steps is not affected by this, which is the point of having it.

Now the same four stages on your own, with a gradient arriving along the cell path as well, so both parts of dc\mathrm{d}c are nonzero.

On paperBackprop through one step by hand

Take the one-unit cell from the first lesson's paper exercise. Its weights (ww on xtx_t, uu on ht−1h_{t-1}, bb) are forget (1,1,0)(1,\allowbreak 1,\allowbreak 0), input (1,0,−2)(1,\allowbreak 0,\allowbreak -2), candidate (−1,−1,0.5)(-1,\allowbreak -1,\allowbreak 0.5) and output (0.5,−1,0)(0.5,\allowbreak -1,\allowbreak 0). With xt=2x_t = 2, ht−1=−1h_{t-1} = -1 and ct−1=0.8c_{t-1} = 0.8 the forward pass gave

f=0.7311,i=0.5,g=−0.4621,o=0.8808,ct=0.3538,tanh⁡(ct)=0.3397.f = 0.7311,\allowbreak \quad i = 0.5,\allowbreak \quad g = -0.4621,\allowbreak \quad o = 0.8808,\allowbreak \quad c_t = 0.3538,\allowbreak \quad \tanh(c_t) = 0.3397.

During the backward pass, dht=2\mathrm{d}h_t = 2 arrives at the output and dct=1\mathrm{d}c_t = 1 arrives along the cell path from step t+1t + 1.

  1. Stage 1: find do\mathrm{d}o and the total gradient on the cell, dc\mathrm{d}c.
  2. Stage 2: find df\mathrm{d}f, di\mathrm{d}i, dg\mathrm{d}g and dct−1\mathrm{d}c_{t-1}.
  3. Stage 3: find the four pre-activation gradients dzi,dzf,dzg,dzo\mathrm{d}z_i,\allowbreak \mathrm{d}z_f,\allowbreak \mathrm{d}z_g,\allowbreak \mathrm{d}z_o.
  4. Stage 4: find the forget gate's weight gradients dwf\mathrm{d}w_f, duf\mathrm{d}u_f, dbf\mathrm{d}b_f, and the gradient dht−1\mathrm{d}h_{t-1} sent to the previous step.

Keep four decimals as you go. The check at the top takes dct−1\mathrm{d}c_{t-1}, dzi\mathrm{d}z_i, dzf\mathrm{d}z_f, dzg\mathrm{d}z_g and dzo\mathrm{d}z_o, in that order, to 3 decimal places.

Work it on real paper: writing each step is the point. Then check your final answer here and compare your working with the walk-through.

dc_{t-1}, dz_i, dz_f, dz_g, dz_o

One entry per box, top to bottom. 0.25, -2, 3/4 and sqrt(2) all work. Enter moves to the next empty box and checks once all are filled.

Backward through time

One step is not a sequence. The step's backward pass needs two gradients from the future, and it produces the same two for its past. So the backward pass through the sequence is a loop that runs from the last step to the first, handing dht−1\mathrm{d}\mathbf{h}_{t-1} and dct−1\mathrm{d}\mathbf{c}_{t-1} back one step at a time.

def lstm_backward(dHs, caches, dhT=None, dcT=None):
    """dHs (B, T, n) is dL/dh_t from whatever used each output (usually the output layer)."""
    B, T, n = dHs.shape
    dh_next = np.zeros((B, n)) if dhT is None else dhT   # arrives from "step T + 1"
    dc_next = np.zeros((B, n)) if dcT is None else dcT
    dW, db = 0, 0
    dX = []
    for t in reversed(range(T)):
        dh = dHs[:, t] + dh_next                          # h_t was used twice: add both
        dx, dh_next, dc_next, dW_t, db_t = lstm_step_backward(dh, dc_next, caches[t])
        dW, db = dW + dW_t, db + db_t                     # the same W at every step: sum
        dX.insert(0, dx)
    return np.stack(dX, axis=1), dW, db, dh_next, dc_next  # the last two are dh0 and dc0

Three details carry the whole idea.

  • Two sources for dht\mathrm{d}\mathbf{h}_t. dHs[:, t] is the gradient from the output layer at step tt; dh_next is what step t+1t + 1 sent back through its gates. Dropping dh_next is the sneaky mistake: with one step and no gradient on the final state it is zero anyway, so the code is right for sequences of length 1 and wrong for anything longer. (Dropping dHs[:, t] is wrong at every length.)
  • Sums over time for dW\mathrm{d}\mathbf{W} and db\mathrm{d}\mathbf{b}. One matrix W\mathbf{W} is used at every step, so its gradient is the sum of the gradients it receives at each use: the same weight sharing as the plain RNN's, and rule 4 applied TT times.
  • dhT and dcT. If the final state is used afterwards, for example carried into the next window of a long text, its gradient enters here. When it is not used, both are zero.

dc_next carries the cell path. Unrolled, the gradient that travels from ct\mathbf{c}_t to ct−k\mathbf{c}_{t-k} along it is multiplied by ft⊙ft−1⊙⋯⊙ft−k+1\mathbf{f}_t \odot \mathbf{f}_{t-1} \odot \cdots \odot \mathbf{f}_{t-k+1}, one forget gate per step, exactly the product from the previous lessons, except that at every step the output route also adds a fresh contribution.

Two steps with numbers

The loop is easiest to trust once you have watched it hand numbers back. Run the same cell for two steps. Step 1 is the worked example above: x1=1x_1 = 1 from h0=0.5h_0 = 0.5 and c0=1.5c_0 = 1.5, giving h1=0.2516h_1 = 0.2516 and c1=1.7020c_1 = 1.7020. Step 2 reads x2=1x_2 = 1 again. (As before, every number is rounded for printing and computed from unrounded values.)

  • pre-activations: input 2(1)−2(0.2516)−1≈0.49672(1) - 2(0.2516) - 1 \approx 0.4967, forget 1(1)+2(0.2516)+0≈1.50331(1) + 2(0.2516) + 0 \approx 1.5033, candidate 1(1)+0+0=11(1) + 0 + 0 = 1, output −1(1)+2(0.2516)−1≈−1.4967-1(1) + 2(0.2516) - 1 \approx -1.4967;
  • gates: i2≈0.6217i_2 \approx 0.6217, f2≈0.8181f_2 \approx 0.8181, g2=tanh⁡(1)≈0.7616g_2 = \tanh(1) \approx 0.7616, o2≈0.1829o_2 \approx 0.1829;
  • memory and output: c2=0.8181×1.7020+0.6217×0.7616≈1.3923+0.4735=1.8658c_2 = 0.8181 \times 1.7020 + 0.6217 \times 0.7616 \approx 1.3923 + 0.4735 = 1.8658, tanh⁡(c2)≈0.9532\tanh(c_2) \approx 0.9532, h2=0.1829×0.9532≈0.1744h_2 = 0.1829 \times 0.9532 \approx 0.1744.

Let the loss look only at the last output, L=h2L = h_2. So dHs holds 1 for step 2 and 0 for step 1, and nothing arrives from beyond step 2. The loop runs t=2t = 2 first, then t=1t = 1:

step 2step 1
from the output layer, dHs[:, t]10
from the later step, dh_next00.2874
total dht\mathrm{d}h_t10.2874
arriving on the cell path, dc_next00.0137
output route, dht ot (1−tanh⁡2ct)\mathrm{d}h_t\, o_t\,(1 - \tanh^2 c_t)1×0.1829×0.0914≈0.01671 \times 0.1829 \times 0.0914 \approx 0.01670.2874×0.2689×0.1245≈0.00960.2874 \times 0.2689 \times 0.1245 \approx 0.0096
total dc\mathrm{d}c0.01670.0137+0.0096=0.02330.0137 + 0.0096 = 0.0233
dz=(dzi,dzf,dzg,dzo)\mathrm{d}\mathbf{z} = (\mathrm{d}z_i,\allowbreak \mathrm{d}z_f,\allowbreak \mathrm{d}z_g,\allowbreak \mathrm{d}z_o)(0.0030,0.0042,0.0044,0.1425)(0.0030,\allowbreak 0.0042,\allowbreak 0.0044,\allowbreak 0.1425)(0.0044,0.0037,0.0049,0.0529)(0.0044,\allowbreak 0.0037,\allowbreak 0.0049,\allowbreak 0.0529)
sent back, dht−1\mathrm{d}h_{t-1}0.28740.1042
sent back, dct−1=dc⋅ft\mathrm{d}c_{t-1} = \mathrm{d}c \cdot f_t0.0167×0.8181≈0.01370.0167 \times 0.8181 \approx 0.01370.0233×0.8808≈0.02050.0233 \times 0.8808 \approx 0.0205

Read it column by column. Step 2 is a one-step backward pass like the one above, and it ends by sending two numbers down: dh1=−2(0.0030)+2(0.0042)+0(0.0044)+2(0.1425)≈0.2874\mathrm{d}h_1 = -2(0.0030) + 2(0.0042) + 0(0.0044) + 2(0.1425) \approx 0.2874 through its uu weights, and dc1≈0.0137\mathrm{d}c_1 \approx 0.0137 along the cell path. Step 1 then starts from them. Its output layer contributed nothing (the loss does not look at h1h_1), so all of dh1\mathrm{d}h_1 came through step 2's gates: that is the dh_next term. Dropping it would leave step 1 with only the 0.01370.0137 that arrived on the cell path, and its output gate would get no gradient at all. Its cell gradient is the arriving 0.01370.0137 plus its own output route, 0.00960.0096. After the loop, the last numbers sent back are dh0≈0.1042\mathrm{d}h_0 \approx 0.1042 and dc0≈0.0205\mathrm{d}c_0 \approx 0.0205.

The weight gradients add up over the two steps. The forget gate's bias, for example, gets dzf\mathrm{d}z_f from each step: 0.0042+0.0037=0.00790.0042 + 0.0037 = 0.0079. Its ww gets dzf×xt\mathrm{d}z_f \times x_t from each step, and both inputs are 1, so also 0.00790.0079. Its uu gets dzf×ht−1\mathrm{d}z_f \times h_{t-1} from each step, with h1=0.2516h_1 = 0.2516 at step 2 and h0=0.5h_0 = 0.5 at step 1: with five decimals, 0.00423×0.2516+0.00367×0.5≈0.00106+0.00184=0.00290.00423 \times 0.2516 + 0.00367 \times 0.5 \approx 0.00106 + 0.00184 = 0.0029.

Go slower: Every number of the two-step example

Step 2, stage 1. do=1×0.9532=0.9532\mathrm{d}o = 1 \times 0.9532 = 0.9532. Output route: 1−0.95322=1−0.9086=0.09141 - 0.9532^2 = 1 - 0.9086 = 0.0914, times o2=0.1829o_2 = 0.1829, gives 0.016720.01672 (five decimals here, because the next four products are sensitive to it). Nothing arrives on the cell path, so dc=0.01672\mathrm{d}c = 0.01672.

Step 2, stage 2. df=0.01672×c1=0.01672×1.7020≈0.0285\mathrm{d}f = 0.01672 \times c_1 = 0.01672 \times 1.7020 \approx 0.0285; di=0.01672×0.7616≈0.0127\mathrm{d}i = 0.01672 \times 0.7616 \approx 0.0127; dg=0.01672×0.6217≈0.0104\mathrm{d}g = 0.01672 \times 0.6217 \approx 0.0104; dc1=0.01672×0.8181≈0.0137\mathrm{d}c_1 = 0.01672 \times 0.8181 \approx 0.0137.

Step 2, stage 3. Slopes: 0.6217×0.3783≈0.23520.6217 \times 0.3783 \approx 0.2352, 0.8181×0.1819≈0.14880.8181 \times 0.1819 \approx 0.1488, 1−0.76162=0.42001 - 0.7616^2 = 0.4200, 0.1829×0.8171≈0.14950.1829 \times 0.8171 \approx 0.1495. So dzi≈0.0127×0.2352≈0.0030\mathrm{d}z_i \approx 0.0127 \times 0.2352 \approx 0.0030, dzf≈0.0285×0.1488≈0.0042\mathrm{d}z_f \approx 0.0285 \times 0.1488 \approx 0.0042, dzg≈0.0104×0.4200≈0.0044\mathrm{d}z_g \approx 0.0104 \times 0.4200 \approx 0.0044, dzo≈0.9532×0.1495≈0.1425\mathrm{d}z_o \approx 0.9532 \times 0.1495 \approx 0.1425.

Step 2, stage 4. dh1=ui dzi+uf dzf+ug dzg+uo dzo=−2(0.0030)+2(0.0042)+0+2(0.1425)≈0.2874\mathrm{d}h_1 = u_i\,\mathrm{d}z_i + u_f\,\mathrm{d}z_f + u_g\,\mathrm{d}z_g + u_o\,\mathrm{d}z_o = -2(0.0030) + 2(0.0042) + 0 + 2(0.1425) \approx 0.2874. The weights get this step's share: db=dz\mathrm{d}b = \mathrm{d}\mathbf{z}, dw=dz×1\mathrm{d}w = \mathrm{d}\mathbf{z} \times 1, du=dz×0.2516\mathrm{d}u = \mathrm{d}\mathbf{z} \times 0.2516.

Step 1, stage 1. dh1=0+0.2874\mathrm{d}h_1 = 0 + 0.2874. do=0.2874×0.9357≈0.2689\mathrm{d}o = 0.2874 \times 0.9357 \approx 0.2689. Output route: 0.2874×0.2689×0.1245≈0.00960.2874 \times 0.2689 \times 0.1245 \approx 0.0096, so dc=0.0137+0.0096=0.0233\mathrm{d}c = 0.0137 + 0.0096 = 0.0233.

Step 1, stage 2. df=0.0233×1.5≈0.0350\mathrm{d}f = 0.0233 \times 1.5 \approx 0.0350; di=0.0233×0.7616≈0.0177\mathrm{d}i = 0.0233 \times 0.7616 \approx 0.0177; dg=0.0233×0.5≈0.0117\mathrm{d}g = 0.0233 \times 0.5 \approx 0.0117; dc0=0.0233×0.8808≈0.0205\mathrm{d}c_0 = 0.0233 \times 0.8808 \approx 0.0205.

Step 1, stage 3. The slopes are the ones from the one-step example: 0.250.25, 0.10500.1050, 0.42000.4200, 0.19660.1966. So dzi≈0.0177×0.25≈0.0044\mathrm{d}z_i \approx 0.0177 \times 0.25 \approx 0.0044, dzf≈0.0350×0.1050≈0.0037\mathrm{d}z_f \approx 0.0350 \times 0.1050 \approx 0.0037, dzg≈0.0117×0.4200≈0.0049\mathrm{d}z_g \approx 0.0117 \times 0.4200 \approx 0.0049, dzo≈0.2689×0.1966≈0.0529\mathrm{d}z_o \approx 0.2689 \times 0.1966 \approx 0.0529.

Step 1, stage 4. With five decimals, dz≈(0.00444,0.00367,0.00489,0.05287)\mathrm{d}\mathbf{z} \approx (0.00444,\allowbreak 0.00367,\allowbreak 0.00489,\allowbreak 0.05287), and dh0=−2(0.00444)+2(0.00367)+0+2(0.05287)=−0.00888+0.00734+0.10574=0.1042\mathrm{d}h_0 = -2(0.00444) + 2(0.00367) + 0 + 2(0.05287) = -0.00888 + 0.00734 + 0.10574 = 0.1042. (From the four-decimal values you would get 0.10440.1044: the doubled rounding errors add up.) The weights get this step's share, with h0=0.5h_0 = 0.5: du=dz×0.5\mathrm{d}u = \mathrm{d}\mathbf{z} \times 0.5.

The sums. db=dz(2)+dz(1)≈(0.0074,0.0079,0.0093,0.1953)\mathrm{d}\mathbf{b} = \mathrm{d}\mathbf{z}^{(2)} + \mathrm{d}\mathbf{z}^{(1)} \approx (0.0074,\allowbreak 0.0079,\allowbreak 0.0093,\allowbreak 0.1953), computed from the unrounded values. mlref.lstm.lstm_backward returns the same numbers.

Bugs in this loop hide in a particular way. Test yourself on which ones.

Quick checkBugs that hide at length 1

Your gradient check passes for sequences of length T=1T = 1 (with dhT=dcT=0\mathrm{d}\mathbf{h}_T = \mathrm{d}\mathbf{c}_T = 0) but fails for T≥2T \ge 2. Which of these bugs could cause exactly that? Select every one that fits.

Choose every option that applies, then check.

Check it numerically

Every line above is simple, and there are about twenty of them. The only reliable way to know they are all right is to compare them with a numerical gradient, as in module 6. For each input array, nudge one entry by ±ϵ\pm\epsilon, rerun the forward pass, and use the central difference (module 5 wrote the step as hh, a letter this lesson needs for the hidden state, so here it is ϵ\epsilon, the eps of the code)

∂L∂θ≈L(θ+ϵ)−L(θ−ϵ)2ϵ,\frac{\partial L}{\partial \theta} \approx \frac{L(\theta + \epsilon) - L(\theta - \epsilon)}{2\epsilon},

then compare with the analytic gradient using the relative error ∣a−n∣∣a∣+∣n∣\frac{|a - n|}{|a| + |n|}, where aa is your analytic value and nn the numerical one. The relative error ignores the overall size of the gradient: a=0.1840a = 0.1840 against n=0.1841n = 0.1841 gives 0.0001/0.3681≈0.00030.0001/0.3681 \approx 0.0003, and a tiny gradient is judged by the same scale. In float64 with ϵ=10−5\epsilon = 10^{-5}, a correct backward pass gives relative errors around 10−710^{-7} or smaller; a bug usually gives something near 1.

The loss you check with matters. A loss such as L=∑HsL = \sum \mathbf{H}_s (every output weighted by 1) sends the same upstream gradient to every unit, and symmetric inputs can hide bugs such as mixing up two units or summing over the wrong axis. Use fixed random weights instead, and make the loss depend on the final states too, so that every path gets exercised:

L=∑R⊙Hs+∑P⊙hT+∑Q⊙cT,L = \sum \mathbf{R} \odot \mathbf{H}_s + \sum \mathbf{P} \odot \mathbf{h}_T + \sum \mathbf{Q} \odot \mathbf{c}_T,

where Hs\mathbf{H}_s stacks all the outputs, R\mathbf{R}, P\mathbf{P} and Q\mathbf{Q} are fixed random arrays of the matching shapes, and each sum adds up every entry. Its gradients are known exactly: dHs=R\mathrm{d}\mathbf{H}_s = \mathbf{R}, dhT=P\mathrm{d}\mathbf{h}_T = \mathbf{P} and dcT=Q\mathrm{d}\mathbf{c}_T = \mathbf{Q}. Check every input: W\mathbf{W}, b\mathbf{b}, the inputs X\mathbf{X} and both starting states. Keep the problem small (a few units and steps) so that nudging every entry is cheap.

Here is what correct and incorrect look like, using the reference implementation. The second check forgets to pass dcT\mathrm{d}\mathbf{c}_T into the backward pass, a one-argument mistake. Expect errors of about 10−710^{-7} or smaller on the first three lines and errors near 1 on the last three:

⌘+Enter runs · edit freelyPython sleeps until you run code

Now write the whole thing yourself: the step's backward pass, the loops over time and the check. The worked example of this lesson is one of its tests, so the numbers above are your first debugging aid.

Code itThe full forward and backward pass

Write the LSTM's forward and backward pass over a whole sequence, and the gradient check that proves them right. This is the heart of mlref/lstm.py, with the same function names and shapes.

  1. lstm_step_backward(dh, dc, cache): the four stages of the lesson for one step. dh is the total gradient on ht\mathbf{h}_t, dc the gradient arriving along the cell path. Return dx, dh_prev, dc_prev, dW, db.
  2. lstm_forward(X, h0, c0, W, b): loop the given lstm_step over X of shape (B,T,m)(B,\allowbreak T,\allowbreak m), with None meaning a zero starting state. Return Hs (B,T,n)(B,\allowbreak T,\allowbreak n), (hT, cT) and the list of caches.
  3. lstm_backward(dHs, caches, dhT=None, dcT=None): backward through time. Return dX (B,T,m)(B,\allowbreak T,\allowbreak m), dW, db, dh0, dc0.
  4. gradient_check(backward): the random problem and loss are set up for you. Compute the analytic gradients with backward, the numerical ones with numerical_gradient, and return the largest relative error for each of W, b, X, h0, c0.
⌘+Enter runsPython sleeps until you run code
Write your code where the starter says raise NotImplementedError, then press Run tests. Each check says what it expects.

Last, explain the bookkeeping in words, as you would in a code review.

In your own wordsTwo gradients and a sum

Explain, as if reviewing a colleague's LSTM code, why the gradient on the cell state ct\mathbf{c}_t has two parts, why the gradient on ht\mathbf{h}_t also has two parts, why dW\mathrm{d}\mathbf{W} is summed over the time steps, and what the cache saved during the forward pass is for.

A few sentences first: 0 of 60 characters.

Saved in this browser as you type.

Next: Training an LSTM