Backpropagation through time

3.5.2 · AI-ML › Sequence Models

---

Problem: Recurrent Networks Mein Gradients

Ek standard RNN ka form hota hai: $h_t=\tanh (W_{hh}{h}_{t-1}+W_{xh}{x}_t+b_h)$ $y_t=W_{hy}{h}_t+b_y$

Hum ek sequence par loss minimize karna chahte hain: $L={\sum }_{t=1}^T{L}_t$

jahan $L_t$ time step $t$ par loss hai (jaise classification ke liye cross-entropy).

Challenge: $W_{hh}$ update karne ke liye, hume $\frac{\partial L}{\partial W_{hh}}$ chahiye. Lekin $W_{hh}$ har time step par use hoti hai, toh usmein changes sabhi future hidden states ko affect karte hain. Gradient ko time ke through sabhi paths account karne chahiye.

---

First Principles Se Derivation

Step 1: Computation Graph Ko Unroll Karo

Forward pass ko $T$ time steps ke liye explicitly likho:

$$\begin{array}{rl}{h}_1& =\tanh (W_{hh}{h}_0+W_{xh}{x}_1+b_h)\\ h_2& =\tanh (W_{hh}{h}_1+W_{xh}{x}_2+b_h)\\ & ⋮\\ h_T& =\tanh (W_{hh}{h}_{T-1}+W_{xh}{x}_T+b_h)\end{array}$$

Har $h_t$ depend karta hai $h_{t-1}$ par, jo depend karta hai $h_{t-2}$ par, aur aise aage. Isse ek chain of dependencies banti hai.

Step 2: Chain Rule Ko Time Ke Across Apply Karo

$\frac{\partial L}{\partial W_{hh}}$ find karne ke liye, sabhi time steps ke contributions sum karo: $\frac{\partial L}{\partial W_{hh}}={\sum }_{t=1}^T\frac{\partial L_t}{\partial W_{hh}}$

Yeh step kyun? $W_{hh}$ $h_1,h_2,\dots ,h_T$ ke computation mein appear hoti hai, toh total gradient har time par partial effects ka sum hai.

Ab, $L_t$ depend karta hai $y_t$ par, jo depend karta hai $h_t$ par. Lekin $h_t$ depend karta hai $h_{t-1},h_{t-2},\dots ,h_1$ par, jinmein sab mein $W_{hh}$ involved hai:

$\frac{\partial L_t}{\partial W_{hh}}=\frac{\partial L_t}{\partial h_t}\cdot \frac{\partial h_t}{\partial W_{hh}}$

Yahan key yeh hai: $\frac{\partial h_t}{\partial W_{hh}}$ ko direct effect (time $t$ par) aur indirect effects (pehle ke hidden states ke through) account karne chahiye:

$\frac{\partial h_t}{\partial W_{hh}}=\frac{\partial h_t}{\partial h_{t-1}}\cdot \frac{\partial h_{t-1}}{\partial W_{hh}}+\frac{\partial h_t}{\partial W_{hh}}{|}_{\text{direct}}$

Yeh step kyun? Multivariate chain rule se, gradient $h_{t-1}$ ke through (indirect path) flow karta hai aur seedha $h_t$ ko bhi affect karta hai (direct path).

Step 3: Recursive Gradient Flow

${\delta }_t=\frac{\partial L}{\partial h_t}$ define karo (post-activation hidden state ke w.r.t. gradient). Toh: ${\delta }_t=\frac{\partial L_t}{\partial h_t}+\frac{\partial L}{\partial h_{t+1}}\cdot \frac{\partial h_{t+1}}{\partial h_t}=\frac{\partial L_t}{\partial h_t}+{\delta }_{t+1}\cdot \frac{\partial h_{t+1}}{\partial h_t}$

Yeh step kyun? $h_t$ par gradient ke do sources hain: immediate loss $L_t$ aur future loss jo $h_{t+1}$ se back propagate hoti hai.

RNN update rule ke liye, $a_{t+1}=W_{hh}{h}_t+W_{xh}{x}_{t+1}+b_h$ ko pre-activation maano, toh $h_{t+1}=\tanh (a_{t+1})$: $\frac{\partial h_{t+1}}{\partial h_t}=\text{diag}(1-{\tanh }^2(a_{t+1}))\cdot W_{hh}=\text{diag}(1-h_{t+1}^2)\cdot W_{hh}$

Yeh step kyun? $\tanh$ ka derivative $1-{\tanh }^2$ hai, aur $h_{t+1}$ compute hoti hai $\tanh (\text{linear combination involving }{h}_t)$ se. Jacobian diagonal hai (elementwise nonlinearity) times $W_{hh}$.

Isliye: ${\delta }_t=\frac{\partial L_t}{\partial h_t}+W_{hh}^T\cdot \text{diag}(1-h_{t+1}^2)\cdot {\delta }_{t+1}$

Step 4: Weights Ke W.R.T. Gradient ($\tanh$ Factor Mat Bhoolna!)

Weight $W_{hh}$ pre-activation $a_t=W_{hh}{h}_{t-1}+\dots$ mein enter hoti hai, aur $h_t=\tanh (a_t)$. Toh step $t$ par $W_{hh}$ ke w.r.t. local gradient mein $\tanh$ derivative zaroor include hona chahiye: $\frac{\partial L_t}{\partial W_{hh}}=\left({\delta }_t\odot (1-h_t^2)\right)h_{t-1}^T$

Yeh step kyun? ${\delta }_t=\partial L/\partial h_t$ post-activation hai. $W_{hh}$ tak pahunchne ke liye hum $\tanh$ se guzarte hain: $\partial h_t/\partial a_t=\text{diag}(1-h_t^2)$, aur $\partial a_t/\partial W_{hh}=h_{t-1}^T$. $(1-h_t^2)$ term skip karna ek common bug hai.

Pre-activation gradient ${\hat{\delta }}_t={\delta }_t\odot (1-h_t^2)$ define karo, accumulated gradient yeh hai:

The BPTT Algorithm:

1. Forward pass: $h_1,\dots ,h_T$ aur losses $L_1,\dots ,L_T$ compute karo.
2. Backward pass: ${\delta }_T$ initialize karo, phir $t=T-1$ se $1$ tak recursively ${\delta }_t$ compute karo.
3. Gradients accumulate karo: $\frac{\partial L}{\partial W_{hh}}={\sum }_{t=1}^T({\delta }_t\odot (1-h_t^2))h_{t-1}^T={\sum }_{t=1}^T{\hat{\delta }}_t{h}_{t-1}^T$

---

---

Unrolled Network Ko Visualize Karo

Diagram dikhata hai:

• Forward pass (left se right): hidden states $h_t$ sequentially compute hoti hain.
• Backward pass (right se left): gradients ${\delta }_t$ time ke through backward flow karte hain.
• Shared weights $W_{hh}$: sabhi time steps ke gradient contributions sum kiye jaate hain.

---

---

Worked Example 1: Simple 2-Step RNN

Setup: 1-dimensional RNN, $T=2$, $W_{hh}=0.5$, $W_{xh}=1.0$, $\tanh$ activation, $h_0=0$.

Input: $x_1=1.0,x_2=0.5$. Target outputs: ${\hat{y}}_1=0.5,{\hat{y}}_2=0.3$. Loss: $L_t=\frac{1}{2}(y_t-{\hat{y}}_t{)}^2$ with $y_t=h_t$ (simplicity ke liye identity output).

Forward pass: $h_1=\tanh (0.5\cdot 0+1.0\cdot 1.0)=\tanh (1.0)\approx 0.7616$ $y_1=h_1=0.7616,L_1=\frac{1}{2}(0.7616-0.5{)}^2=0.0342$

$h_2=\tanh (0.5\cdot 0.7616+1.0\cdot 0.5)=\tanh (0.8808)\approx 0.7068$ $y_2=h_2=0.7068,L_2=\frac{1}{2}(0.7068-0.3{)}^2=0.0827$

Yeh steps kyun? Hum RNN equations seedha apply karte hain. Har hidden state pichle aur current input par depend karti hai.

Backward pass (post-activation ${\delta }_t$ compute karo):

$t=2$ par: ${\delta }_2=\frac{\partial L_2}{\partial h_2}=h_2-0.3=0.4068$

Yeh step kyun? Squared error ka $h_2=y_2$ ke w.r.t. derivative.

$t=1$ par: $\frac{\partial L_1}{\partial h_1}=h_1-0.5=0.2616$

$\frac{\partial h_2}{\partial h_1}=(1-h_2^2)\cdot W_{hh}=(1-0.7068^2)\cdot 0.5=0.5006\cdot 0.5=0.2503$

Yeh step kyun? Pre-activation par $\tanh$ ka derivative $1-h_2^2$ hai, aur linear part $W_{hh}$ contribute karta hai.

${\delta }_1=0.2616+0.4068\cdot 0.2503=0.3634$

Gradient — $\tanh$ factor $(1-h_t^2)$ include karo!

Pre-activation gradients: ${\hat{\delta }}_2={\delta }_2\cdot (1-h_2^2)=0.4068\cdot (1-0.7068^2)=0.4068\cdot 0.5006=0.2036$ ${\hat{\delta }}_1={\delta }_1\cdot (1-h_1^2)=0.3634\cdot (1-0.7616^2)=0.3634\cdot 0.4200=0.1526$

$\frac{\partial L}{\partial W_{hh}}={\hat{\delta }}_1\cdot h_0+{\hat{\delta }}_2\cdot h_1=0.1526\cdot 0+0.2036\cdot 0.7616\approx 0.1551$

Yeh step kyun? Har time step ${\hat{\delta }}_t\cdot h_{t-1}$ contribute karta hai (pre-activation gradient times incoming hidden state). $t=2$ ka term hai $0.4068\cdot (1-0.7068^2)\cdot 0.7616\approx 0.155$ — not $0.310$. $(1-h_t^2)$ factor bhoolne se answer yahan double ho jaata hai; yahi classic error hai.

---

Worked Example 2: Long Sequences Mein Gradient Vanishing

Setup: $T=10$, $W_{hh}=0.9$, $x_t=1.0$ sabhi $t$ ke liye, $h_0=0$.

Forward pass (carefully computed): $h_1=\tanh (0.9\cdot 0+1.0)=\tanh (1.0)\approx 0.7616$ $h_2=\tanh (0.9\cdot 0.7616+1.0)=\tanh (1.6854)\approx 0.9331$ $h_3=\tanh (0.9\cdot 0.9331+1.0)=\tanh (1.8398)\approx 0.9506$ $h_4=\tanh (0.9\cdot 0.9506+1.0)=\tanh (1.8555)\approx 0.9522$ $h_5\approx \tanh (0.9\cdot 0.9522+1.0)=\tanh (1.8570)\approx 0.9524,\dots$

Yeh steps kyun? Hidden states $0.952$ ke paas ek fixed point ki taraf saturate hoti hain kyunki $\tanh$ bade values ko squash kar deta hai.

Backward pass: Maano ${\delta }_{10}=1.0$. Recurrence factor hai: $\frac{\partial h_{t+1}}{\partial h_t}=(1-h_{t+1}^2)\cdot W_{hh}$

Saturated region mein $h\approx 0.952$ use karke, $1-h^2\approx 1-0.906=0.094$, toh har factor $\approx 0.094\cdot 0.9\approx 0.0846$ hai.

$t=9$ par: ${\delta }_9=1.0\cdot 0.0846\approx 0.0846$ $t=8$ par: ${\delta }_8=0.0846\cdot 0.0846\approx 0.00716$

Yeh step kyun? Har backward step $(1-h_{t+1}^2)\cdot W_{hh}\approx 0.085<1$ se multiply karta hai. Kyunki $h_t$ $0.952$ ke paas saturate hoti hai, $(1-h_t^2)$ bahut chhota hota hai, jo exponential decay cause karta hai.

9 steps baad: ${\delta }_1\approx 0.0846^9\approx 2.4\times 10^{-10}$. Vanishing gradient: time 10 ki information time 1 tak practically pahuncht hi nahi.

Yeh kyun matter karta hai: Long-range dependencies seekhe nahi ja sakte. Yahi LSTMs aur GRUs ko motivate karta hai.

---

---

---

---

Truncated BPTT: Practical Compromise

Long sequences ke liye, sabhi hidden states store karna aur exact gradients compute karna memory-intensive hai. Truncated BPTT sequence ko $k$ length ke chunks mein split karta hai:

1. $k$ steps ke liye forward pass.
2. Sirf un $k$ steps ke liye backward pass.
3. Gradient detach karo aur agle $k$ steps ke liye forward continue karo.

Trade-off: Gradients $k$ steps se aage propagate nahi ho sakte, jo model ki long-range dependencies seekhne ki ability limit karta hai. Lekin memory $O(T)$ se ghatakar $O(k)$ ho jaati hai.

Formula: $\frac{\partial L}{\partial W_{hh}}\approx {\sum }_{t=t_0}^{t_0+k}{\hat{\delta }}_t{h}_{t-1}^T$

jahan $t_0$ current chunk ki starting hai.

---

---

Recall Ek 12-Saal-Ke Bachche Ko Explain Karo

Imagine karo tum piano par ek song seekh rahe ho. Song mein 100 notes hain, aur tum better hona chahte ho.

Normal learning (feedforward): Tum ek note bajate ho, tumhara teacher correct karta hai, tum agle note par jaate ho. Har note independent hai. Recurrent learning (RNN): Tumhara har note bajana pichle notes par depend karta hai. Agar tum note 50 par galti karo, toh notes 51, 52, ..., 100 affect hoti hain. Seekhne ke liye, tumhe figure out karna hoga ki har note ne final mistake mein kya contribute kiya.

Backpropagation through time: Sabhi 100 notes bajane ke baad, tum song "rewind" karte ho aur poochte ho: "Note 1 ne final sound ko kaise affect kiya?" Tum backward trace karte ho: note 100 depend kiya 99 par, jo depend kiya 98 par, .., note 1 tak. Tum adjust karte ho ki tumne note 1 kaise bajaya, effects ki poori chain ke basis par.

Problem yeh hai: jitna peeche jaao, utna hi dhundha hota hai ki kya hua tha (vanishing gradients). Isliye RNNs lambe songs (sequences) ke saath struggle karte hain. LSTMs better notes lene jaisi hain taaki tum pehle ke parts clearly yaad raho.

---

---

Connections

• 3.5.01-Recurrent-Neural-Networks-RNNs: BPTT, RNNs ka training algorithm hai.
• 3.5.03-Vanishing-and-Exploding-Gradients: BPTT deep sequences mein vanishing/exploding gradient problem expose karta hai.
• 3.5.04-Long-Short-Term-Memory-LSTM: LSTMs gradient flow ko gate karke vanishing gradients mitigate karte hain.
• 3.5.05-Gated-Recurrent-Unit-GRU: GRUs LSTMs ko simplify karte hain, long-term gradient flow preserve karte hue.
• 2.2.03-Backpropagation-Algorithm: BPTT, unrolled computational graph par apply kiya gaya backprop hai.
• 3.5.07-Bidirectional-RNNs: BPTT bidirectional RNNs tak extend hota hai, dono directions mein backprop karke.

---

Summary

Backpropagation through time

Concept Map