{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.11"
  },
  "colab": {
   "provenance": []
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "id": "cell-0000",
   "metadata": {},
   "source": [
    "# Recurrent Neural Networks\n",
    "\n",
    "Give a network memory — the recurrence behind RNNs, unrolling through time, vanishing gradients, and nn.RNN on a next-step prediction task.\n",
    "\n",
    "*Part of the free [Deep Learning with PyTorch](https://ramadnsyh.dev/courses/deep-learning) course by [Muhammad Ramadiansyah](https://ramadnsyh.dev). This notebook is generated from the interactive lesson — [read it online](https://ramadnsyh.dev/courses/deep-learning/recurrent-neural-networks).*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0001",
   "metadata": {},
   "source": [
    "Every network so far took a fixed-size input and processed it all at once. But\n",
    "much of the world's data arrives as a **sequence** — sentences, sensor\n",
    "readings, daily temperatures, audio — where the *order* carries the meaning.\n",
    "In this lesson you'll build the recurrence that lets a network remember, run a\n",
    "tiny RNN cell by hand in NumPy, meet the vanishing-gradient problem that\n",
    "haunts it, and train `nn.RNN` on a next-step prediction task."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0002",
   "metadata": {},
   "source": [
    "## Order is information\n",
    "\n",
    "Compare \"the movie was good, not bad\" with \"the movie was bad, not good\".\n",
    "Same words, opposite meanings — only the order differs. The same goes for time\n",
    "series: a temperature of 15°C means something different in a *falling* trend\n",
    "than in a rising one. Context lives in the sequence.\n",
    "\n",
    "A plain feedforward network struggles here for three reasons:\n",
    "\n",
    "- **Fixed input size.** An MLP expects exactly `n` inputs. Sentences and\n",
    "  series come in every length.\n",
    "- **No memory.** Feed it one time step at a time and each prediction starts\n",
    "  from scratch — step 10 knows nothing about steps 1–9.\n",
    "- **No parameter sharing across time.** Concatenate a window of steps into one\n",
    "  big input and the network must relearn the same pattern separately at every\n",
    "  position.\n",
    "\n",
    "The fix: give the network a **hidden state** that persists between steps — a\n",
    "working memory."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0003",
   "metadata": {},
   "source": [
    "## The recurrence\n",
    "\n",
    "An RNN processes a sequence one element at a time. At step `t` it combines\n",
    "the current input `x_t` with its own previous hidden state `h_(t-1)`:\n",
    "\n",
    "**h_t = tanh(Wx·x_t + Wh·h_(t-1) + b)**\n",
    "\n",
    "That's it — a linear combination of \"what I see now\" and \"what I remember\",\n",
    "squashed by a tanh. The same weights `Wx` and `Wh` are used at *every* step,\n",
    "so the network can handle any sequence length with a fixed number of\n",
    "parameters. Run the cell yourself:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0004",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "rng = np.random.default_rng(1)\n",
    "hidden_size = 3\n",
    "\n",
    "Wx = rng.normal(0, 0.8, hidden_size)                 # input -> hidden\n",
    "Wh = rng.normal(0, 0.8, (hidden_size, hidden_size))  # hidden -> hidden\n",
    "b = np.zeros(hidden_size)\n",
    "\n",
    "def run(sequence):\n",
    "    h = np.zeros(hidden_size)                        # empty memory\n",
    "    for t, x in enumerate(sequence):\n",
    "        h = np.tanh(Wx * x + Wh @ h + b)\n",
    "        print(f\"  t={t}  x={x:+.1f}  ->  h = {np.round(h, 3)}\")\n",
    "    return h\n",
    "\n",
    "print(\"sequence A: [0.5, -0.1, 0.8, 0.3]\")\n",
    "hA = run([0.5, -0.1, 0.8, 0.3])\n",
    "\n",
    "print(\"sequence B: same values, different order\")\n",
    "hB = run([0.3, 0.8, -0.1, 0.5])\n",
    "\n",
    "print(f\"final states differ: {not np.allclose(hA, hB)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0005",
   "metadata": {},
   "source": [
    "Two things to notice. The hidden state changes at every step — it accumulates\n",
    "a summary of everything seen so far. And the two sequences contain identical\n",
    "values yet end in *different* final states: unlike an averaging model, the RNN\n",
    "is genuinely order-sensitive."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0006",
   "metadata": {},
   "source": [
    "## Unrolling through time\n",
    "\n",
    "The loop above can be drawn as a chain: copy the cell once per time step and\n",
    "pass the hidden state along. **Unrolled**, an RNN over a 100-step sequence\n",
    "looks like a 100-layer feedforward network — except every \"layer\" shares the\n",
    "same weights.\n",
    "\n",
    "Training uses **backpropagation through time (BPTT)**: run the forward pass\n",
    "over the whole sequence, compute the loss, and backpropagate through the\n",
    "unrolled chain, summing each weight's gradient contributions across all time\n",
    "steps. For long sequences this gets expensive (the graph for a 10,000-step\n",
    "series is enormous), so in practice we use **truncated BPTT**: chop the\n",
    "sequence into chunks of, say, 50 steps, carry the hidden state forward from\n",
    "chunk to chunk, but *detach* it between chunks (`hidden.detach()` in PyTorch)\n",
    "so gradients only flow within a chunk. It's a biased approximation — the model\n",
    "can't learn dependencies longer than the truncation window through gradients —\n",
    "but it keeps memory and compute bounded, and it's what makes training on long\n",
    "sequences feasible at all."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0007",
   "metadata": {},
   "source": [
    "## The trouble with deep time\n",
    "\n",
    "An unrolled RNN is a very deep network, and gradients flowing back through it\n",
    "get multiplied by (roughly) the same recurrent weights at every step. What\n",
    "happens when you multiply by the same number many times?"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0008",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "for t in [1, 10, 50, 100]:\n",
    "    print(f\"t={t:>3}:   0.9^t = {0.9**t:12.2e}     1.1^t = {1.1**t:12.2e}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0009",
   "metadata": {},
   "source": [
    "- If the effective factor is below 1, gradients **vanish** — by step 100 they\n",
    "  are numerically zero, so the network cannot learn long-range dependencies.\n",
    "  What happened 80 steps ago simply never reaches the weights.\n",
    "- If it's above 1, gradients **explode** — the loss becomes NaN and training\n",
    "  blows up.\n",
    "\n",
    "Exploding gradients have a blunt but effective fix, gradient clipping (next\n",
    "lesson). Vanishing gradients are the deep problem: they're why vanilla RNNs\n",
    "in practice remember only 10–20 steps, and why the LSTM was invented. Hold\n",
    "that thought."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0010",
   "metadata": {},
   "source": [
    "## nn.RNN in PyTorch\n",
    "\n",
    "PyTorch packages the recurrence (with all the batching and multi-layer\n",
    "machinery) as `nn.RNN`. With `batch_first=True`, it expects input of shape\n",
    "`(batch, seq_len, input_size)` and returns two things:\n",
    "\n",
    "- `output` — shape `(batch, seq_len, hidden_size)`: the hidden state at\n",
    "  *every* time step of the top layer,\n",
    "- `h_n` — shape `(num_layers, batch, hidden_size)`: the *final* hidden state\n",
    "  of each layer.\n",
    "\n",
    "For \"predict the next value\" we take the last time step of `output` and map\n",
    "it through a linear head. Here's the full task — predicting the next point of\n",
    "a sine wave — to run in Colab:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0011",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import torch\n",
    "from torch import nn, optim\n",
    "\n",
    "torch.manual_seed(0)\n",
    "\n",
    "# --- data: a sine wave, windowed into (input sequence, next value) pairs ---\n",
    "t = torch.linspace(0, 60, 600)\n",
    "series = torch.sin(t)\n",
    "\n",
    "seq_len = 20\n",
    "X = torch.stack([series[i:i + seq_len] for i in range(len(series) - seq_len)])\n",
    "y = series[seq_len:]\n",
    "X = X.unsqueeze(-1)          # (580, 20, 1)  — batch, seq_len, input_size\n",
    "y = y.unsqueeze(-1)          # (580, 1)\n",
    "\n",
    "# --- model ---\n",
    "class NextStepRNN(nn.Module):\n",
    "    def __init__(self, hidden_size=32):\n",
    "        super().__init__()\n",
    "        self.rnn = nn.RNN(input_size=1, hidden_size=hidden_size, num_layers=1,\n",
    "                          batch_first=True)\n",
    "        self.fc = nn.Linear(hidden_size, 1)\n",
    "\n",
    "    def forward(self, x):\n",
    "        out, h_n = self.rnn(x)        # out: (batch, seq_len, hidden)\n",
    "        return self.fc(out[:, -1, :]) # last time step -> prediction\n",
    "\n",
    "model = NextStepRNN()\n",
    "criterion = nn.MSELoss()\n",
    "optimizer = optim.Adam(model.parameters(), lr=1e-3)\n",
    "\n",
    "for epoch in range(300):\n",
    "    pred = model(X)\n",
    "    loss = criterion(pred, y)\n",
    "    loss.backward()\n",
    "    optimizer.step()\n",
    "    optimizer.zero_grad()\n",
    "    if epoch % 50 == 0:\n",
    "        print(f\"epoch {epoch:3d}: MSE = {loss.item():.5f}\")\n",
    "\n",
    "with torch.inference_mode():\n",
    "    print(\"next value after the last window:\", model(X[-1:]).item())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0012",
   "metadata": {},
   "source": [
    "The loss should fall to nearly zero — a sine wave is about the friendliest\n",
    "sequence there is. The point isn't the task; it's the plumbing: window the\n",
    "series, get the shapes right, take the last step's hidden state, regress."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0013",
   "metadata": {},
   "source": [
    "## Sequence shapes cheat sheet\n",
    "\n",
    "Shape bugs are the number-one RNN frustration. With `batch_first=True`:\n",
    "\n",
    "| Tensor | Shape | Meaning |\n",
    "|---|---|---|\n",
    "| input `x` | `(batch, seq_len, input_size)` | `input_size` = features per time step (1 for a univariate series) |\n",
    "| `output` | `(batch, seq_len, hidden_size)` | top-layer hidden state at every step |\n",
    "| `h_n` | `(num_layers, batch, hidden_size)` | final hidden state per layer |\n",
    "| `output[:, -1, :]` | `(batch, hidden_size)` | last step — feed this to the head |\n",
    "| head output | `(batch, output_size)` | your prediction |\n",
    "\n",
    "Without `batch_first=True` the default is `(seq_len, batch, input_size)` —\n",
    "a classic source of silently wrong results, since a transposed tensor often\n",
    "still *runs*."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0014",
   "metadata": {},
   "source": [
    "### 🏋️ Exercise — Reproduce nn.RNN by hand\n",
    "\n",
    "In Colab, create a single-layer `nn.RNN` with `input_size=1`, `hidden_size=4`,\n",
    "`batch_first=True`, and run it on one random sequence of 5 steps. Then\n",
    "reimplement the recurrence yourself with a Python loop using the module's own\n",
    "weight tensors, and verify with `torch.allclose` that your hand-rolled hidden\n",
    "states match both `output` and `h_n` exactly."
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0015",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Your solution here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0016",
   "metadata": {},
   "source": [
    "<details><summary>✅ Show solution</summary>\n",
    "\n",
    "```python\n",
    "import torch\n",
    "from torch import nn\n",
    "\n",
    "torch.manual_seed(0)\n",
    "rnn = nn.RNN(input_size=1, hidden_size=4, num_layers=1, batch_first=True)\n",
    "\n",
    "x = torch.randn(1, 5, 1)          # one sequence, 5 steps\n",
    "out, h_n = rnn(x)\n",
    "\n",
    "W_ih = rnn.weight_ih_l0           # (hidden, input)\n",
    "W_hh = rnn.weight_hh_l0           # (hidden, hidden)\n",
    "b_ih = rnn.bias_ih_l0\n",
    "b_hh = rnn.bias_hh_l0\n",
    "\n",
    "h = torch.zeros(4)\n",
    "manual = []\n",
    "for t in range(5):\n",
    "    h = torch.tanh(x[0, t] @ W_ih.T + h @ W_hh.T + b_ih + b_hh)\n",
    "    manual.append(h)\n",
    "manual = torch.stack(manual)\n",
    "\n",
    "print(\"matches nn.RNN:\", torch.allclose(out[0], manual, atol=1e-6))\n",
    "print(\"final state matches h_n:\", torch.allclose(h_n[0, 0], manual[-1], atol=1e-6))\n",
    "```\n",
    "\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0017",
   "metadata": {},
   "source": [
    "Next: the vanishing gradient gets its cure — gated memory cells. LSTM and GRU\n",
    "give the network a conveyor belt for long-term memory."
   ]
  }
 ]
}