Md. Asif Uddin
    I.10.X07

    The GRU state stays in the box

    proof▲▲△

    Prove that a GRU in the form (I.10.7) keeps every coordinate of ht\vec h_t in [−1,1][-1,1] for all tt if h0\vec h_0 starts there. Then show the premise matters: start a coordinate at h0=3h_0=3 with z=0.5z=0.5 and candidate 00.

    Hint

    A convex combination of two numbers lies between them.

    Solution

    Fix a coordinate and write ht=z ht−1+(1−z)nh_t=z\,h_{t-1}+(1-z)n with z∈(0,1)z\in(0,1) and n=tanh⁡(⋅)∈(−1,1)n=\tanh(\cdot)\in(-1,1). By the triangle inequality,

    ∣ht∣≤z∣ht−1∣+(1−z)∣n∣≤max⁡(∣ht−1∣,∣n∣).|h_t|\leq z|h_{t-1}|+(1-z)|n|\leq\max(|h_{t-1}|,|n|).

    If ∣ht−1∣≤1|h_{t-1}|\leq1, the right-hand side is at most one, so ∣ht∣≤1|h_t|\leq1. Induction on tt from ∣h0∣≤1|h_0|\leq1 completes the proof. In fact ∣ht∣<1|h_t|<1 for t≥1t\geq1, since 1−z>01-z>0 and ∣n∣<1|n|<1.

    The argument uses the starting value. With h0=3h_0=3, z=0.5z=0.5 and n=0n=0 the states are 33, 1.51.5, 0.750.75, 0.3750.375: outside the box for one step, then inside. The same inequality shows ∣ht∣≤max⁡(∣h0∣,1)|h_t|\leq\max(|h_0|,1) in general.

    An LSTM has no such bound on ct\vec c_t, which is why I.10.T3 needs forget values below one for the cell.

    Draws on