citynames_manual_backprop.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "170d1007",
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import random\n",
    "import torch\n",
    "import torch.nn.functional as F\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "582b823c",
   "metadata": {},
   "source": [
    "# Dataset Exploration and Modification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "15bcf213",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['peosta', 'camp hill', 'mazama', 'springport', 'new trier']"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# read in us-city-place-names.csv and modify input so that the list only contains \n",
    "# unique lowercase city names\n",
    "cityname_csv = pd.read_csv(\"us-city-place-names.csv\")\n",
    "citynames = cityname_csv['city'].tolist()\n",
    "citynames = [d.lower().strip() for d in citynames]\n",
    "random.shuffle(citynames)\n",
    "citynames[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "e40e9f31",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "28\n",
      "stoi:  {' ': 1, 'a': 2, 'b': 3, 'c': 4, 'd': 5, 'e': 6, 'f': 7, 'g': 8, 'h': 9, 'i': 10, 'j': 11, 'k': 12, 'l': 13, 'm': 14, 'n': 15, 'o': 16, 'p': 17, 'q': 18, 'r': 19, 's': 20, 't': 21, 'u': 22, 'v': 23, 'w': 24, 'x': 25, 'y': 26, 'z': 27, '.': 0}\n",
      "itos:  {1: ' ', 2: 'a', 3: 'b', 4: 'c', 5: 'd', 6: 'e', 7: 'f', 8: 'g', 9: 'h', 10: 'i', 11: 'j', 12: 'k', 13: 'l', 14: 'm', 15: 'n', 16: 'o', 17: 'p', 18: 'q', 19: 'r', 20: 's', 21: 't', 22: 'u', 23: 'v', 24: 'w', 25: 'x', 26: 'y', 27: 'z', 0: '.'}\n"
     ]
    }
   ],
   "source": [
    "chars = sorted(list(set(''.join(citynames)))) # sort letter alphabetically with no repeating letters\n",
    "stoi = {s:i+1 for i, s in enumerate(chars)} # create a mapping of chars to integers\n",
    "stoi['.'] = 0 # add special start and end character\n",
    "\n",
    "itos = {i:s for s,i in stoi.items()} # create a integer to char mapping\n",
    "\n",
    "vocab_size = len(itos)\n",
    "print(vocab_size)\n",
    "print(\"stoi: \",  stoi)\n",
    "print(\"itos: \", itos)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "346e0899",
   "metadata": {},
   "source": [
    "# Dataset Initialization and Splitting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "df490ba8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TRAIN:  torch.Size([223899, 3]) torch.Size([223899])\n",
      "DEV:  torch.Size([28034, 3]) torch.Size([28034])\n",
      "TEST:  torch.Size([28303, 3]) torch.Size([28303])\n"
     ]
    }
   ],
   "source": [
    "# for reproducibility\n",
    "g = torch.Generator().manual_seed(42)\n",
    "\n",
    "# dataset splitting into train(80%), dev/validation(10%), test(10%)\n",
    "# train is used to train parameters\n",
    "# dev/validation is used to train hyperparameters\n",
    "# test is used to evaluate the model\n",
    "train, dev, test = torch.utils.data.random_split(citynames, [0.8, 0.1, 0.1], generator=g)\n",
    "\n",
    "block_size = 3 # number of characters needed to predict the next one\n",
    "\n",
    "# function to create inputs and outputs from dataset\n",
    "def build_dataset(dataset):\n",
    "    X, Y = [], []\n",
    "    for d in dataset:\n",
    "        context = [0] * block_size # create context 'window'\n",
    "        for char in d + '.':\n",
    "            idx = stoi[char] # get current character index\n",
    "\n",
    "            X.append(context) # add current context to inputs\n",
    "            Y.append(idx) # add current index to label\n",
    "            context = context[1:] + [idx] # slide context 'window'\n",
    "            \n",
    "    X = torch.tensor(X)\n",
    "    Y = torch.tensor(Y)\n",
    "    return X,Y\n",
    "    \n",
    "\n",
    "# defining training inputs and labels\n",
    "Xtr, Ytr = build_dataset(train)\n",
    "print(\"TRAIN: \", Xtr.shape, Ytr.shape)\n",
    "\n",
    "# defining validation inputs and labels\n",
    "Xdev, Ydev = build_dataset(dev)\n",
    "print(\"DEV: \", Xdev.shape, Ydev.shape)\n",
    "\n",
    "# defining test inputs and labels\n",
    "Xte, Yte = build_dataset(test)\n",
    "print(\"TEST: \", Xte.shape, Yte.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69d387be",
   "metadata": {},
   "source": [
    "# Compare Gradients"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "b4feabba",
   "metadata": {},
   "outputs": [],
   "source": [
    "# utility function to compare manual gradients to PyTorch gradients\n",
    "\n",
    "def cmp(s, dt, t): # dt are manual gradients; t.grad are PyTorch gradients\n",
    "    \n",
    "    ex = torch.all(dt == t.grad).item() # tensor that evaluates to true if the gradients are equal\n",
    "    \n",
    "    app = torch.allclose(dt, t.grad) # tensor that evaluates to true if the gradients are within 1e-05 to 1e-08\n",
    "    \n",
    "    maxdiff = (dt - t.grad).abs().max().item() # calculates the maximum difference between the gradients\n",
    "    \n",
    "    print(f'{s:15s} | exact: {str(ex):5s} | approximate: {str(app):5s} | maxdiff: {maxdiff}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d44de2dd",
   "metadata": {},
   "source": [
    "# Initialize Model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "64927cf8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# of parameters:  4212\n"
     ]
    }
   ],
   "source": [
    "n_embed = 10 # dimensionality of charcter embedding vectors\n",
    "n_hidden = 64 # number of neurons in each hidden layer\n",
    "\n",
    "C = torch.randn((vocab_size, n_embed),             generator=g) # create a lookup table\n",
    "\n",
    "# layer 1\n",
    "W1 = torch.randn((n_embed * block_size ,n_hidden), generator=g) * (5/3) / ((n_embed * block_size)**0.5) # weights matrix\n",
    "b1 = torch.randn(n_hidden,                         generator=g) * 0.01 # b1 does nothing because of batch norm\n",
    "\n",
    "# layer 2\n",
    "W2 = torch.randn((n_hidden, vocab_size),           generator=g) * 0.01 # weights matrix\n",
    "b2 = torch.randn(vocab_size,                       generator=g) * 0.01 # bias\n",
    "\n",
    "# batch norm params\n",
    "batchn_gain = torch.randn((1, n_hidden)) * 0.1 + 1.0\n",
    "batchn_bias = torch.randn((1, n_hidden)) * 0.1\n",
    "\n",
    "\n",
    "params = [C,W1,b1,W2,b2,batchn_gain, batchn_bias]\n",
    "\n",
    "print(\"# of parameters: \", sum(p.nelement() for p in params))\n",
    "for p in params:\n",
    "    p.requires_grad = True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "5601fbd2",
   "metadata": {},
   "outputs": [],
   "source": [
    "batch_size = 32\n",
    "n = batch_size # short variable for convenience\n",
    "idx = torch.randint(0, Xtr.shape[0], (n, ), generator=g)\n",
    "Xb, Yb = Xtr[idx], Ytr[idx] # batch X and Y"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7970858",
   "metadata": {},
   "source": [
    "# Expanded Forward Pass "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "f1185fc1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.3281118869781494"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# forward pass (expanded because of manual backprop)\n",
    "\n",
    "emb = C[Xb] # get character embeddings\n",
    "emb_concat = emb.view(emb.shape[0], -1) # concat vectors\n",
    "\n",
    "# linear layer 1\n",
    "hprebn = emb_concat @ W1 + b1 # hidden layer pre-activation pre-batchnorm\n",
    "\n",
    "# batch norm layer (same as gamma * (x - mean) / (std) + beta)\n",
    "bnmeani = 1 / n * hprebn.sum(0, keepdims=True)\n",
    "bndiff = hprebn - bnmeani\n",
    "bndiff2 = bndiff**2\n",
    "bnvar = 1 / (n - 1) * bndiff2.sum(0, keepdims=True)\n",
    "bnvar_inv = (bnvar + 1e-5)**-0.5\n",
    "bnraw = bndiff * bnvar_inv\n",
    "hpreact = batchn_gain * bnraw + batchn_bias\n",
    "\n",
    "# non-linear activation function\n",
    "h = torch.tanh(hpreact) # hidden layer\n",
    "\n",
    "# linear layer 2\n",
    "logits = h @ W2 + b2 # output layer\n",
    "\n",
    "# cross entropy loss (same as F.cross_entropy(logits, Yb))\n",
    "logit_maxes = logits.max(1, keepdims=True).values\n",
    "norm_logits = logits - logit_maxes # subtract for exp stability. ex: [5, -3, 10] - 10 ==> [-5, -13, 0]\n",
    "counts = norm_logits.exp()\n",
    "counts_sum = counts.sum(1, keepdims=True)\n",
    "counts_sum_inv = counts_sum**-1\n",
    "probs = counts * counts_sum_inv\n",
    "logprobs = probs.log()\n",
    "loss = -logprobs[range(n), Yb].mean()\n",
    "\n",
    "# PyTorch backward pass\n",
    "for p in params:\n",
    "    p.grad = None\n",
    "for t in [ logprobs, probs, counts_sum_inv, counts_sum, counts, norm_logits, logit_maxes, logits, h,\n",
    "           hpreact, bnraw, bnvar_inv, bnvar, bndiff2, bndiff, bnmeani, hprebn, emb_concat, emb]:\n",
    "    t.retain_grad()\n",
    "loss.backward()\n",
    "loss.item()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76fa7b0a",
   "metadata": {},
   "source": [
    "# Yay! Manual Backpropogation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "26e2a7c9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "logprobs        | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "probs           | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "counts_sum_inv  | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "counts_sum      | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "counts          | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "norm_logits     | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "logit_maxes     | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "logits          | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "h               | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "W2              | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "b2              | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "hpreact         | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "batchn_gain     | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "bnraw           | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "batchn_bias     | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "bnvar_inv       | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "bnvar           | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "bndiff2         | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "bndiff          | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "bnmeani         | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "hprebn          | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "emb_concat      | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "W1              | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "b1              | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "emb             | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "C               | exact: True  | approximate: True  | maxdiff: 0.0\n",
      "yay!\n"
     ]
    }
   ],
   "source": [
    "# backprop through every variable in the forward pass manually\n",
    "\n",
    "# logprobs\n",
    "dlogprobs = torch.zeros_like(logprobs)\n",
    "dlogprobs[range(n), Yb] = -1.0 / n\n",
    "cmp('logprobs', dlogprobs, logprobs)\n",
    "\n",
    "# probs\n",
    "dprobs = (1.0 / probs) * dlogprobs\n",
    "cmp('probs', dprobs, probs)\n",
    "\n",
    "# counts_sum_inv\n",
    "dcounts_sum_inv = (counts * dprobs).sum(1, keepdims=True)\n",
    "dcounts = counts_sum_inv * dprobs\n",
    "cmp('counts_sum_inv', dcounts_sum_inv, counts_sum_inv)\n",
    "\n",
    "# counts_sum\n",
    "dcounts_sum = (-counts_sum**-2) * dcounts_sum_inv\n",
    "cmp('counts_sum', dcounts_sum, counts_sum)\n",
    "\n",
    "# counts\n",
    "dcounts += torch.ones_like(counts) * dcounts_sum\n",
    "cmp(\"counts\", dcounts, counts)\n",
    "\n",
    "# norm_logits\n",
    "dnorm_logits = counts * dcounts\n",
    "dlogits = dnorm_logits.clone()\n",
    "cmp(\"norm_logits\", dnorm_logits, norm_logits)\n",
    "\n",
    "# logit_maxes\n",
    "dlogit_maxes = (-dnorm_logits).sum(1, keepdims=True)\n",
    "cmp('logit_maxes', dlogit_maxes, logit_maxes)\n",
    "\n",
    "# logits (can also use one hot encoding)\n",
    "ones = torch.zeros_like(logits)\n",
    "ones[range(n), logits.max(1).indices] = 1\n",
    "dlogits +=  ones * dlogit_maxes\n",
    "cmp('logits', dlogits, logits)\n",
    "\n",
    "# h, W2, b2\n",
    "dh = dlogits @ W2.T\n",
    "dW2 = h.T @ dlogits\n",
    "db2 = dlogits.sum(0)\n",
    "cmp('h', dh, h)\n",
    "cmp('W2', dW2, W2)\n",
    "cmp('b2', db2, b2)\n",
    "\n",
    "# hpreact\n",
    "dhpreact = (1.0 - h**2) * dh\n",
    "cmp('hpreact', dhpreact, hpreact)\n",
    "\n",
    "# batchn_gain\n",
    "dbatchn_gain = (bnraw * dhpreact).sum(0, keepdims=True)\n",
    "cmp('batchn_gain', dbatchn_gain, batchn_gain)\n",
    "\n",
    "# bnraw\n",
    "dbnraw = batchn_gain * dhpreact\n",
    "cmp('bnraw', dbnraw, bnraw)\n",
    "\n",
    "# batchn_bias\n",
    "dbatchn_bias = dhpreact.sum(0, keepdims=True)\n",
    "cmp('batchn_bias', dbatchn_bias, batchn_bias)\n",
    "\n",
    "# bnvar_inv\n",
    "dbnvar_inv = (bndiff * dbnraw).sum(0, keepdims=True)\n",
    "dbndiff = bnvar_inv * dbnraw \n",
    "cmp('bnvar_inv', dbnvar_inv, bnvar_inv)\n",
    "\n",
    "# bnvar\n",
    "dbnvar = (-0.5 * (bnvar + 1e-5)**-1.5) * dbnvar_inv\n",
    "cmp('bnvar', dbnvar, bnvar)\n",
    "\n",
    "# bndiff2\n",
    "dbndiff2 = (1.0 / (n-1)) * torch.ones_like(bndiff2) * dbnvar\n",
    "cmp('bndiff2', dbndiff2, bndiff2)\n",
    "\n",
    "# bndiff\n",
    "dbndiff += (2 * bndiff) * dbndiff2\n",
    "cmp('bndiff', dbndiff, bndiff)\n",
    "\n",
    "# bnmeani\n",
    "dhprebn = dbndiff.clone()\n",
    "dbnmeani = (-dbndiff).sum(0, keepdims=True)\n",
    "cmp('bnmeani', dbnmeani, bnmeani)\n",
    "\n",
    "# hprebn\n",
    "dhprebn += (1.0 / n) * torch.ones_like(hprebn) * dbnmeani\n",
    "cmp('hprebn', dhprebn, hprebn)\n",
    "\n",
    "# emb_concat, W1, b1\n",
    "demb_concat = dhprebn @ W1.T\n",
    "dW1 = emb_concat.T @ dhprebn\n",
    "db1 = dhprebn.sum(0)\n",
    "cmp('emb_concat', demb_concat, emb_concat)\n",
    "cmp('W1', dW1, W1)\n",
    "cmp('b1', db1, b1)\n",
    "\n",
    "# emb\n",
    "demb = demb_concat.view(emb.shape)\n",
    "cmp('emb', demb, emb)\n",
    "\n",
    "# C\n",
    "dC = torch.zeros_like(C)\n",
    "for k in range(Xb.shape[0]):\n",
    "    for j in range (Xb.shape[1]):\n",
    "        idx = Xb[k,j]\n",
    "        dC[idx] += demb[k,j]\n",
    "cmp('C', dC, C)\n",
    "\n",
    "print(\"yay!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73c39c7a",
   "metadata": {},
   "source": [
    "### This was way too much! Rather than backpropogating through every single step, lets optimize and do seperate parts of the forward pass"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51208cef",
   "metadata": {},
   "source": [
    "# Backprop Cross-Entropy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "b1bc9f0f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.3281121253967285 diff: 2.384185791015625e-07\n"
     ]
    }
   ],
   "source": [
    "# now lets backpropogate through the loss function (cross entropy) all in one go\n",
    "\n",
    "# forward pass\n",
    "\n",
    "# before:\n",
    "# logit_maxes = logits.max(1, keepdims=True).values\n",
    "# norm_logits = logits - logit_maxes\n",
    "# counts = norm_logits.exp()\n",
    "# counts_sum = counts.sum(1, keepdims=True)\n",
    "# counts_sum_inv = counts_sum**-1\n",
    "# probs = counts * counts_sum_inv\n",
    "# logprobs = probs.log()\n",
    "# loss = -logprobs[range(n), Yb].mean()\n",
    "\n",
    "# now:\n",
    "loss_ce = F.cross_entropy(logits, Yb)\n",
    "print(loss_ce.item(), \"diff:\", (loss_ce - loss).item())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "bb5384ce",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "logits          | exact: False | approximate: True  | maxdiff: 7.566995918750763e-09\n"
     ]
    }
   ],
   "source": [
    "# backward pass\n",
    "\n",
    "# before:\n",
    "# dlogprobs = torch.zeros_like(logprobs)\n",
    "# dlogprobs[range(n), Yb] = -1.0 / n\n",
    "# dprobs = (1.0 / probs) * dlogprobs\n",
    "# dcounts_sum_inv = (counts * dprobs).sum(1, keepdims=True)\n",
    "# dcounts = counts_sum_inv * dprobs\n",
    "# dcounts_sum = (-counts_sum**-2) * dcounts_sum_inv\n",
    "# dcounts += torch.ones_like(counts) * dcounts_sum\n",
    "# dnorm_logits = counts * dcounts\n",
    "# dlogits = dnorm_logits.clone()\n",
    "# dlogit_maxes = (-dnorm_logits).sum(1, keepdims=True)\n",
    "# ones = torch.zeros_like(logits)\n",
    "# ones[range(n), logits.max(1).indices] = 1\n",
    "# dlogits +=  ones * dlogit_maxes\n",
    "\n",
    "# now:\n",
    "dlogits = F.softmax(logits, 1)\n",
    "dlogits[range(n), Yb] -= 1\n",
    "dlogits /= n\n",
    "cmp('logits', dlogits, logits) # cannot get exact number but 5e-09 is very small"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "cc2252a3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.image.AxesImage at 0x119091420>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAkoAAAKTCAYAAADmEid+AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAo/UlEQVR4nO3dcWxd5Xn48efaJgZKfD0TEseLkwZooS1NJqUQIlpGR0aSSohAkCjttIAQFcygQdRRZSpQtErZqNSyThT+GqxSAx1TAwKpVDQUo2qBjlQRYxoRyTIlKHFo0ewbwjCZ7/n9gXB/LnkJN3lv7onv5yNZIvbl9XPOPcf+5vjmuFIURREAAHxAR6sHAAAoK6EEAJAglAAAEoQSAECCUAIASBBKAAAJQgkAIKGr1QP8vnq9Hnv37o2ZM2dGpVJp9TgAwDRTFEUcOHAgBgYGoqPjw68ZlS6U9u7dG4ODg60eAwCY5vbs2RPz5s370MeULpRmzpwZERG7d++Onp6eFk/Dsert7c263ujoaNb1yij3zfKP9LelRpT1Rv65rz6XdTvbRbvs/3b4qUlZz81arRbz58+fbI4PU7pQen+n9vT0CKVpIPdJ0g7HhFBqXFm/GHN02mX/C6XG5T42Psp8XswNAJAglAAAEoQSAEBC00Lp/vvvj49//ONx8sknx9KlS+NXv/pVsz4VAEBTNCWUfvzjH8e6devi7rvvjl//+texePHiWLFiRbzxxhvN+HQAAE3RlFD67ne/GzfeeGNcf/318elPfzoefPDBOPXUU+Mf//Efm/HpAACaInsovfvuu7F169ZYvnz57z5JR0csX748tmzZ8oHHj4+PR61Wm/IGAFAG2UPpt7/9bUxMTMScOXOmvH/OnDkxMjLygcdv2LAhqtXq5Ju7cgMAZdHyf/W2fv36GBsbm3zbs2dPq0cCAIiIJtyZe9asWdHZ2Rn79++f8v79+/dHf3//Bx7f3d0d3d3duccAADhm2a8ozZgxI5YsWRKbN2+efF+9Xo/NmzfHsmXLcn86AICmacrvelu3bl2sXbs2Pve5z8UFF1wQ9913Xxw8eDCuv/76Znw6AICmaEooXXPNNfGb3/wm7rrrrhgZGYk/+qM/iqeffvoDL/AGACizSlGyX9Ncq9WiWq3G6OhoW/ym+Omus7Mz63oTExNZ1yuj3KdkR0e+n7CX7MvFpLL/hnIa0y77P/dxW0ZlPTdrtVr09vbG2NjYEVuj5f/qDQCgrIQSAEBCU16jxIkt56XSMv+oLOd25lyrXq9nWyuivD/GyLnPyrqN7STnc5Dzx8U5Oc4aNx32WTmPRgCAEhBKAAAJQgkAIEEoAQAkCCUAgAShBACQIJQAABKEEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAldrR4gpSiKKIrimNepVCoZpnlPR0ferqzX61nXo3VyPpc5j9mIyHIeNWOtMivrdub+GpRTWfdZWefixFHesw4AoMWEEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCABKEEAJAglAAAEoQSAECCUAIASOhq9QAplUolKpVKlnVyqdfr2daKKPdsNCbnc5lzrYi8x0bu2XIp61wReWcriiLbWrm1y3bmlHM7y3wOnOhcUQIASBBKAAAJQgkAIEEoAQAkCCUAgAShBACQIJQAABKEEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAldrR4gpVKpRKVSOeZ16vV6hmnek2Oe/19RFNnW6ujI17w558ot53OQ89jIqaxzReQ9NnI+l2U+Zss6W5m/nuVcq7OzM9tauc/Nsn7dLut53iquKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCABKEEAJAglAAAEoQSAECCUAIASBBKAAAJQgkAIEEoAQAkCCUAgISuVg+QUq1Wo1KpHPM69Xo9wzTvKYoi21q5lXm2nHJuZ47jq93YZ9NHmb9m5DzOcn4PyK2sz0FHR75rKGXdxka4ogQAkCCUAAAShBIAQIJQAgBIEEoAAAnZQ+lb3/pWVCqVKW/nnntu7k8DANB0Tbk9wGc+85n4+c9//rtP0lXauxAAACQ1pWC6urqiv7+/GUsDABw3TXmN0muvvRYDAwNx5plnxle/+tXYvXt38rHj4+NRq9WmvAEAlEH2UFq6dGk8/PDD8fTTT8cDDzwQu3btii984Qtx4MCBwz5+w4YNUa1WJ98GBwdzjwQAcFQqRZPvLz46OhoLFiyI7373u3HDDTd84OPj4+MxPj4++edarTYZS36FCQAcXzl/hUxZv2/WarXo7e2NsbGx6Onp+dDHNv1V1r29vfHJT34yduzYcdiPd3d3R3d3d7PHAABoWNPvo/TWW2/Fzp07Y+7cuc3+VAAAWWUPpa9//esxPDwc//3f/x3/+q//GldeeWV0dnbGtddem/tTAQA0VfYfvb3++utx7bXXxptvvhlnnHFGfP7zn48XXnghzjjjjNyfCgCgqbKH0qOPPpp7SQCAlvC73gAAEoQSAEBCaX8J2+jo6BHvbfBR5LyHQ857S0SU9/4ScDx0dnZmWyvn/dIiyntulvnrWU7tsp05lfXeR9Ph+6YrSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCABKEEAJAglAAAEoQSAECCUAIASBBKAAAJQgkAIEEoAQAkdLV6gJRKpRKVSuWY1ymKIsM0+deKiCzb977cs+VS1rkiIrq68h3+ExMT2dYqs5zP5//93/9lW6tdzs2cc5VZu2xnTmX9WlvWuRrhihIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCABKEEAJAglAAAEoQSAECCUAIASBBKAAAJQgkAIEEoAQAkCCUAgAShBACQIJQAABKEEgBAglACAEjoavUAKUVRRFEUrR6jqXJuX1n3VaVSafUISRMTE60e4bBy77Ocx0ZHR76/W5X1mI0o92ztIOc5UObnMuf5VK/Xs63FVK4oAQAkCCUAgAShBACQIJQAABKEEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCAhK5WD9BsRVFkW6uzszPbWhER9Xo921qVSiXbWjQu5/7PeczmlnO2nGuV+fhvl2OjXbYzp5zfA9rlfGoFV5QAABKEEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCABKEEAJAglAAAEoQSAEBCV6sHaLZKpZJtrXq9nm2tiLyzFUWRbS0al3P/5zwuIhwbrVbWYyP3cVHW7ezoyHc9YGJiIttaueX+usHvuKIEAJAglAAAEoQSAECCUAIASBBKAAAJQgkAIKHhUHr++efj8ssvj4GBgahUKvH4449P+XhRFHHXXXfF3Llz45RTTonly5fHa6+9lmteAIDjpuFQOnjwYCxevDjuv//+w3783nvvje9///vx4IMPxosvvhgf+9jHYsWKFfHOO+8c87AAAMdTwzecXLVqVaxateqwHyuKIu6777745je/GVdccUVERPzwhz+MOXPmxOOPPx5f/vKXP/D/jI+Px/j4+OSfa7VaoyMBADRF1tco7dq1K0ZGRmL58uWT76tWq7F06dLYsmXLYf+fDRs2RLVanXwbHBzMORIAwFHLGkojIyMRETFnzpwp758zZ87kx37f+vXrY2xsbPJtz549OUcCADhqLf9db93d3dHd3d3qMQAAPiDrFaX+/v6IiNi/f/+U9+/fv3/yYwAAJ4qsobRw4cLo7++PzZs3T76vVqvFiy++GMuWLcv5qQAAmq7hH7299dZbsWPHjsk/79q1K7Zt2xZ9fX0xf/78uO222+Lb3/52fOITn4iFCxfGnXfeGQMDA7F69eqccwMANF3DofTSSy/FF7/4xck/r1u3LiIi1q5dGw8//HDccccdcfDgwfja174Wo6Oj8fnPfz6efvrpOPnkk/NNDQBwHFSKoihaPcT/r1arRbVajdHR0ejp6Wn1OE1VqVSyrVWyp5FjkPO4iCjvsZFzrtz7rKza5WtGzu3s6Mj3CpOJiYlsa9FatVotent7Y2xs7Iit4Xe9AQAkCCUAgISW30ep2cp8eb/Ml77Lqh1+9JB7rrLus87Ozmxr1ev1bGvllnOflfnrWU45n892+XFZWc/z6fB90xUlAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCABKEEAJAglAAAEoQSAECCUAIASBBKAAAJQgkAIEEoAQAkCCUAgAShBACQ0NXqAZqtUqmUcq2IiKIosq5XRmXeZ7lnyyX3ceE4a1xZj7N2eC4j2ufcbAfTYZ+5ogQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCABKEEAJAglAAAEoQSAECCUAIASBBKAAAJQgkAIEEoAQAkCCUAgAShBACQIJQAABK6Wj1ASm9vb1QqlWNeZ2JiIsM07ymKItta7aLM+6zMs5VVzn1Wr9ezrdUuz2WOr4kcvTLv/5znQJm3sxVcUQIASBBKAAAJQgkAIEEoAQAkCCUAgAShBACQIJQAABKEEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAldrR4gZXR0NHp6elo9BnwklUol21pFUWRbK7ec21lm7fB85p6rrMdGzu0s6zZGRHR15ft2Xq/Xs61V1uO/Ea4oAQAkCCUAgAShBACQIJQAABKEEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCABKEEAJDQ1eoBKJ9KpZJtraIosq2VW7tsZ1mVef/nXK+jI9/fR+v1era1cu7/iPLuszIfZzlNTExkW6vM29kKrigBACQIJQCABKEEAJAglAAAEoQSAEBCw6H0/PPPx+WXXx4DAwNRqVTi8ccfn/Lx6667LiqVypS3lStX5poXAOC4aTiUDh48GIsXL477778/+ZiVK1fGvn37Jt8eeeSRYxoSAKAVGr6P0qpVq2LVqlUf+pju7u7o7+8/6qEAAMqgKa9Reu6552L27NlxzjnnxM033xxvvvlm8rHj4+NRq9WmvAEAlEH2UFq5cmX88Ic/jM2bN8ff/d3fxfDwcKxatSp519ANGzZEtVqdfBscHMw9EgDAUakUx3Cv8kqlEps2bYrVq1cnH/Nf//VfcdZZZ8XPf/7zuPTSSz/w8fHx8RgfH5/8c61Wi8HBwRgdHY2enp6jHY1j0C63/G+X7Syrdtn/Zf0VJrmV9VeY5FTm44zG1Gq16O3tjbGxsSO2RtOPxjPPPDNmzZoVO3bsOOzHu7u7o6enZ8obAEAZND2UXn/99XjzzTdj7ty5zf5UAABZNfyv3t56660pV4d27doV27Zti76+vujr64t77rkn1qxZE/39/bFz586444474uyzz44VK1ZkHRwAoNkaDqWXXnopvvjFL07+ed26dRERsXbt2njggQfi5Zdfjn/6p3+K0dHRGBgYiMsuuyz+5m/+Jrq7u/NNDQBwHBzTi7mboVarRbVa9WLuFmqXF9m2y3aWVbvsfy/mbpwXc9NspXoxNwDAiUooAQAkNPwapeOlKIoslzlzXt5vFzkvL+fe/zlnK+tl9DLvs3aRc5+V9cdlZf7amPNHb6mbHXN8lPXrTyNzuaIEAJAglAAAEoQSAECCUAIASBBKAAAJQgkAIEEoAQAkCCUAgAShBACQIJQAABKEEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAASulo9QEqlUolKpdLqMThGHR15W7xer2dbqyiKbGvlVNa5cmuX7SyrMu//djjP20Xu7+OteD5dUQIASBBKAAAJQgkAIEEoAQAkCCUAgAShBACQIJQAABKEEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAldrR6g2YqiyLZWpVLJtla7yLn/m7EeHE5Zz/Wcczk3G5d7G8t6nJVZrn3WyDquKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCABKEEAJAglAAAEoQSAECCUAIASBBKAAAJQgkAIEEoAQAkCCUAgAShBACQ0NXqAVJ6e3uzrFMURZZ1IiLq9Xq2tSIiKpVK1vXKKOf+zy3n89kOz2VuOY+N3Pu/rLOV+Xxqh3OgoyPvtYUyP5/8jitKAAAJQgkAIEEoAQAkCCUAgAShBACQIJQAABKEEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgoavVA6SMjo5GT0/PMa9TFEWGaThaZd7/HR35/p6QczsrlUq2tSLyzlbm7cwp57GRU5n3f8716vV6trVyKutcEeU+n3LKtZ2NrFPOrwYAACUglAAAEoQSAECCUAIASBBKAAAJDYXShg0b4vzzz4+ZM2fG7NmzY/Xq1bF9+/Ypj3nnnXdiaGgoTj/99DjttNNizZo1sX///qxDAwAcDw2F0vDwcAwNDcULL7wQzzzzTBw6dCguu+yyOHjw4ORjbr/99njyySfjsccei+Hh4di7d29cddVV2QcHAGi2SnEMN+b4zW9+E7Nnz47h4eG4+OKLY2xsLM4444zYuHFjXH311RER8eqrr8anPvWp2LJlS1x44YVHXLNWq0W1Ws12H6Wcct8TqF3ue1FWOfd/me9v4z5KjSvrbGXe/+1wH6Uy3xeurMdsbrm28/3WGBsbO2JrHNNrlMbGxiIioq+vLyIitm7dGocOHYrly5dPPubcc8+N+fPnx5YtWw67xvj4eNRqtSlvAABlcNShVK/X47bbbouLLroozjvvvIiIGBkZiRkzZkRvb++Ux86ZMydGRkYOu86GDRuiWq1Ovg0ODh7tSAAAWR11KA0NDcUrr7wSjz766DENsH79+hgbG5t827NnzzGtBwCQy1H9rrdbbrklnnrqqXj++edj3rx5k+/v7++Pd999N0ZHR6dcVdq/f3/09/cfdq3u7u7o7u4+mjEAAJqqoStKRVHELbfcEps2bYpnn302Fi5cOOXjS5YsiZNOOik2b948+b7t27fH7t27Y9myZXkmBgA4Thq6ojQ0NBQbN26MJ554ImbOnDn5uqNqtRqnnHJKVKvVuOGGG2LdunXR19cXPT09ceutt8ayZcs+0r94AwAok4ZC6YEHHoiIiEsuuWTK+x966KG47rrrIiLie9/7XnR0dMSaNWtifHw8VqxYET/4wQ+yDAsAcDwd032UmsF9lDhe3EeptWuV+fgv62xl3v/uo9RaZT1mczvh7qMEADCdCSUAgISjuj3A8fD7N608Wjkv4Zb5UnVZLwmX+ceVZf2RVG5l3WdlnSv3ejm3s8z7bGJiIut6ZdQuP97KqczfAz4qV5QAABKEEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCABKEEAJAglAAAEoQSAEBCV6sHSPmf//mf6OnpafUYUxRFkXW9SqWSdb1cyjpXmZV5n+U8bsu8nTl1dOT7O2S9Xs+2VpnlPDbKepzlfi7Lup1lluvrWSPruKIEAJAglAAAEoQSAECCUAIASBBKAAAJQgkAIEEoAQAkCCUAgAShBACQIJQAABKEEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQEJXqwdIqVQqUalUjnmdoigyTNMcOWfLsa/el3Oujo68LV7W57Osc0WU99go61oREfV6Pet6uTg3WyvnudQucu+zXOs1so4rSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCABKEEAJAglAAAEoQSAECCUAIASBBKAAAJQgkAIKGr1QM0W6VSafUISUVRtHqEttYu+78dtrPM53lZlfm4KOtsuY+zsm5nzrk6OvJej8k1WyPruKIEAJAglAAAEoQSAECCUAIASBBKAAAJQgkAIEEoAQAkCCUAgAShBACQIJQAABKEEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAASulo9QLMVRZFtrUqlkm2t3Do7O7OtNTExkW2ter2eba3c2uXYyDlbzuezoyPf39NyPpdlVubjrB3kPs5yPp9l/Xo2Hc5NV5QAABKEEgBAglACAEgQSgAACUIJACChoVDasGFDnH/++TFz5syYPXt2rF69OrZv3z7lMZdccklUKpUpbzfddFPWoQEAjoeGQml4eDiGhobihRdeiGeeeSYOHToUl112WRw8eHDK42688cbYt2/f5Nu9996bdWgAgOOhofsoPf3001P+/PDDD8fs2bNj69atcfHFF0++/9RTT43+/v48EwIAtMgxvUZpbGwsIiL6+vqmvP9HP/pRzJo1K84777xYv359vP3228k1xsfHo1arTXkDACiDo74zd71ej9tuuy0uuuiiOO+88ybf/5WvfCUWLFgQAwMD8fLLL8c3vvGN2L59e/zkJz857DobNmyIe+6552jHAABomkpxlPcXv/nmm+OnP/1p/PKXv4x58+YlH/fss8/GpZdeGjt27IizzjrrAx8fHx+P8fHxyT/XarUYHByM0dHR6OnpOZrRpijrbd0j8s7W1ZXvt9Hk/BUmuZX113GU+VdLlHWf+RUmtDu/KqR1arVa9Pb2xtjY2BFb46i+u95yyy3x1FNPxfPPP/+hkRQRsXTp0oiIZCh1d3dHd3f30YwBANBUDYVSURRx6623xqZNm+K5556LhQsXHvH/2bZtW0REzJ0796gGBABolYZCaWhoKDZu3BhPPPFEzJw5M0ZGRiIiolqtximnnBI7d+6MjRs3xpe+9KU4/fTT4+WXX47bb789Lr744li0aFFTNgAAoFkaeo1S6uepDz30UFx33XWxZ8+e+LM/+7N45ZVX4uDBgzE4OBhXXnllfPOb3/zIrzeq1WpRrVa9RqlBXqPUOK9RapzXKEE+XqPUOk17jdKRnojBwcEYHh5uZEkAgNLyu94AABKEEgBAQr4XtmT2/i/Unc5yvkYj52tHyvyz7jK/5qysyvp8lnWuMuvs7My2Vplfi1hW7fI1o8xyfd1oZB1XlAAAEoQSAECCUAIASBBKAAAJQgkAIEEoAQAkCCUAgAShBACQIJQAABKEEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBI6Gr1AClFUURRFFnWyaVSqWRbKyLvbGXezrIq63bmfC5z6+jI93erMm9nzmMj5z6bmJjItlbu/V/W8ymnMh+z7SLXcdbIOq4oAQAkCCUAgAShBACQIJQAABKEEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCAhK5WD9BsHR35WrBer2dbKyKiUqmUcq0yy7mdRVFkWyun3M9lzu0s6z7LLed25v660Q7K/HWb9uOKEgBAglACAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCABKEEAJAglAAAEoQSAECCUAIASOhq9QDNVq/XWz1CUqVSafUIh1UURatHOOG0yz7LuZ1lPf5zK+uxkXv/59zOsn7dzv1clvUc6OjIdw1lYmIi21oR+WZrZN+7ogQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCABKEEAJAglAAAEoQSAECCUAIASBBKAAAJQgkAIEEoAQAkCCUAgAShBACQIJQAABK6Wj3AiaSjI29XFkWRdb12kHOf5VyrUqlkWyu3Ms+WS+5tLOu5Wda5yqwdjv+IvNtZr9ezrZX7+2au2Ro5l1xRAgBIEEoAAAlCCQAgQSgBACQIJQCABKEEAJDQUCg98MADsWjRoujp6Ymenp5YtmxZ/PSnP538+DvvvBNDQ0Nx+umnx2mnnRZr1qyJ/fv3Zx8aAOB4aCiU5s2bF3/7t38bW7dujZdeein+5E/+JK644or4j//4j4iIuP322+PJJ5+Mxx57LIaHh2Pv3r1x1VVXNWVwAIBmqxTHeAezvr6++M53vhNXX311nHHGGbFx48a4+uqrIyLi1VdfjU996lOxZcuWuPDCCw/7/4+Pj8f4+Pjkn2u1WgwODsbo6Gj09PQcy2gRkfcGbW44Ob244WTjynrMuuFk48p8zObUDsd/RHm3s6w3nKzVatHb2xtjY2NHbI2j3oKJiYl49NFH4+DBg7Fs2bLYunVrHDp0KJYvXz75mHPPPTfmz58fW7ZsSa6zYcOGqFark2+Dg4NHOxIAQFYNh9K///u/x2mnnRbd3d1x0003xaZNm+LTn/50jIyMxIwZM6K3t3fK4+fMmRMjIyPJ9davXx9jY2OTb3v27Gl4IwAAmqHh3/V2zjnnxLZt22JsbCz+5V/+JdauXRvDw8NHPUB3d3d0d3cf9f8PANAsDYfSjBkz4uyzz46IiCVLlsS//du/xd///d/HNddcE++++26Mjo5Ouaq0f//+6O/vzzYwAMDxcsyvsqrX6zE+Ph5LliyJk046KTZv3jz5se3bt8fu3btj2bJlx/ppAACOu4auKK1fvz5WrVoV8+fPjwMHDsTGjRvjueeei5/97GdRrVbjhhtuiHXr1kVfX1/09PTErbfeGsuWLUv+izcAgDJrKJTeeOON+PM///PYt29fVKvVWLRoUfzsZz+LP/3TP42IiO9973vR0dERa9asifHx8VixYkX84Ac/aMrgAADNdsz3UcqtVqtFtVp1HyWarl3uSVPW+6vk5D5KjSvzMZtTOxz/EeXdzra+jxIAwHQnlAAAEhq+PcCJJuflyNyXECcmJrKuV0Zl/pFIu/zoocw/LsilHbYxon2O2ZxyHhu5j7Oy/rgsp9xztWI7XVECAEgQSgAACUIJACBBKAEAJAglAIAEoQQAkCCUAAAShBIAQIJQAgBIEEoAAAlCCQAgQSgBACQIJQCABKEEAJAglAAAEoQSAECCUAIASOhq9QC/ryiKiIio1WotnuSD3p8tlzJuY26VSiXrermfA4CPKvfXn9xfH8uorN8D3v/++1HWK10oHThwICIi5s+f3+JJmq+3t7fVIwBA2zpw4EBUq9UPfUylKNlf0ev1euzduzdmzpz5oSVaq9VicHAw9uzZEz09PcdxQiLs/1az/1vPc9Ba9n9rnej7vyiKOHDgQAwMDERHx4e/Cql0V5Q6Ojpi3rx5H/nxPT09J+STNF3Y/61l/7ee56C17P/WOpH3/5GuJL3Pi7kBABKEEgBAwgkbSt3d3XH33XdHd3d3q0dpS/Z/a9n/rec5aC37v7Xaaf+X7sXcAABlccJeUQIAaDahBACQIJQAABKEEgBAglACAEg4IUPp/vvvj49//ONx8sknx9KlS+NXv/pVq0dqG9/61reiUqlMeTv33HNbPda09fzzz8fll18eAwMDUalU4vHHH5/y8aIo4q677oq5c+fGKaecEsuXL4/XXnutNcNOQ0fa/9ddd90HzoeVK1e2ZthpaMOGDXH++efHzJkzY/bs2bF69erYvn37lMe88847MTQ0FKeffnqcdtppsWbNmti/f3+LJp5ePsr+v+SSSz5wDtx0000tmrg5TrhQ+vGPfxzr1q2Lu+++O37961/H4sWLY8WKFfHGG2+0erS28ZnPfCb27ds3+fbLX/6y1SNNWwcPHozFixfH/ffff9iP33vvvfH9738/HnzwwXjxxRfjYx/7WKxYsSLeeeed4zzp9HSk/R8RsXLlyinnwyOPPHIcJ5zehoeHY2hoKF544YV45pln4tChQ3HZZZfFwYMHJx9z++23x5NPPhmPPfZYDA8Px969e+Oqq65q4dTTx0fZ/xERN95445Rz4N57723RxE1SnGAuuOCCYmhoaPLPExMTxcDAQLFhw4YWTtU+7r777mLx4sWtHqMtRUSxadOmyT/X6/Wiv7+/+M53vjP5vtHR0aK7u7t45JFHWjDh9Pb7+78oimLt2rXFFVdc0ZJ52tEbb7xRREQxPDxcFMV7x/tJJ51UPPbYY5OP+c///M8iIootW7a0asxp6/f3f1EUxR//8R8Xf/mXf9m6oY6DE+qK0rvvvhtbt26N5cuXT76vo6Mjli9fHlu2bGnhZO3ltddei4GBgTjzzDPjq1/9auzevbvVI7WlXbt2xcjIyJTzoVqtxtKlS50Px9Fzzz0Xs2fPjnPOOSduvvnmePPNN1s90rQ1NjYWERF9fX0REbF169Y4dOjQlHPg3HPPjfnz5zsHmuD39//7fvSjH8WsWbPivPPOi/Xr18fbb7/divGapqvVAzTit7/9bUxMTMScOXOmvH/OnDnx6quvtmiq9rJ06dJ4+OGH45xzzol9+/bFPffcE1/4whfilVdeiZkzZ7Z6vLYyMjISEXHY8+H9j9FcK1eujKuuuioWLlwYO3fujL/+67+OVatWxZYtW6Kzs7PV400r9Xo9brvttrjooovivPPOi4j3zoEZM2ZEb2/vlMc6B/I73P6PiPjKV74SCxYsiIGBgXj55ZfjG9/4Rmzfvj1+8pOftHDavE6oUKL1Vq1aNfnfixYtiqVLl8aCBQvin//5n+OGG25o4WRw/H35y1+e/O/PfvazsWjRojjrrLPiueeei0svvbSFk00/Q0ND8corr3hNZIuk9v/Xvva1yf/+7Gc/G3Pnzo1LL700du7cGWedddbxHrMpTqgfvc2aNSs6Ozs/8C8a9u/fH/39/S2aqr319vbGJz/5ydixY0erR2k77x/zzofyOPPMM2PWrFnOh8xuueWWeOqpp+IXv/hFzJs3b/L9/f398e6778bo6OiUxzsH8krt/8NZunRpRMS0OgdOqFCaMWNGLFmyJDZv3jz5vnq9Hps3b45ly5a1cLL29dZbb8XOnTtj7ty5rR6l7SxcuDD6+/unnA+1Wi1efPFF50OLvP766/Hmm286HzIpiiJuueWW2LRpUzz77LOxcOHCKR9fsmRJnHTSSVPOge3bt8fu3budAxkcaf8fzrZt2yIiptU5cML96G3dunWxdu3a+NznPhcXXHBB3HfffXHw4MG4/vrrWz1aW/j6178el19+eSxYsCD27t0bd999d3R2dsa1117b6tGmpbfeemvK38x27doV27Zti76+vpg/f37cdttt8e1vfzs+8YlPxMKFC+POO++MgYGBWL16deuGnkY+bP/39fXFPffcE2vWrIn+/v7YuXNn3HHHHXH22WfHihUrWjj19DE0NBQbN26MJ554ImbOnDn5uqNqtRqnnHJKVKvVuOGGG2LdunXR19cXPT09ceutt8ayZcviwgsvbPH0J74j7f+dO3fGxo0b40tf+lKcfvrp8fLLL8ftt98eF198cSxatKjF02fU6n92dzT+4R/+oZg/f34xY8aM4oILLiheeOGFVo/UNq655ppi7ty5xYwZM4o//MM/LK655ppix44drR5r2vrFL35RRMQH3tauXVsUxXu3CLjzzjuLOXPmFN3d3cWll15abN++vbVDTyMftv/ffvvt4rLLLivOOOOM4qSTTioWLFhQ3HjjjcXIyEirx542DrfvI6J46KGHJh/zv//7v8Vf/MVfFH/wB39QnHrqqcWVV15Z7Nu3r3VDTyNH2v+7d+8uLr744qKvr6/o7u4uzj777OKv/uqvirGxsdYOnlmlKIrieIYZAMCJ4oR6jRIAwPEklAAAEoQSAECCUAIASBBKAAAJQgkAIEEoAQAkCCUAgAShBACQIJQAABKEEgBAwv8DmRGYJY3YPSEAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 800x800 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# a quick look at dlogits\n",
    "plt.figure(figsize=(8,8))\n",
    "plt.imshow(dlogits.detach(), cmap='gray') # black squares represent the index where we subtracted 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1321a62e",
   "metadata": {},
   "source": [
    "# Backprop BatchNorm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "4089ce44",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "maxdiff: 1.52587890625e-05\n"
     ]
    }
   ],
   "source": [
    "# just like cross entropy, we will backpropogate through BatchNorm all in one go\n",
    "\n",
    "# forward pass\n",
    "\n",
    "# before: \n",
    "# bnmeani = 1 / n * hprebn.sum(0, keepdims=True)\n",
    "# bndiff = hprebn - bnmeani\n",
    "# bndiff2 = bndiff**2\n",
    "# bnvar = 1 / (n - 1) * bndiff2.sum(0, keepdims=True)\n",
    "# bnvar_inv = (bnvar + 1e-5)**-0.5\n",
    "# bnraw = bndiff * bnvar_inv\n",
    "# hpreact = batchn_gain * bnraw + batchn_bias\n",
    "\n",
    "# now:\n",
    "hpreact_bn = batchn_gain * (hprebn - hprebn.mean(0, keepdims=True)) / torch.sqrt(hprebn.var(0, keepdims=True, unbiased=True)) + batchn_bias\n",
    "print(\"maxdiff:\", (hpreact_bn - hpreact).abs().max().item())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "34774a3e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hprebn          | exact: False | approximate: True  | maxdiff: 1.1641532182693481e-10\n"
     ]
    }
   ],
   "source": [
    "# backward pass\n",
    "\n",
    "# before\n",
    "# dbnraw = batchn_gain * dhpreact\n",
    "# dbatchn_bias = dhpreact.sum(0, keepdims=True)\n",
    "# dbnvar_inv = (bndiff * dbnraw).sum(0, keepdims=True)\n",
    "# dbndiff = bnvar_inv * dbnraw \n",
    "# dbnvar = (-0.5 * (bnvar + 1e-5)**-1.5) * dbnvar_inv\n",
    "# dbndiff2 = (1.0 / (n-1)) * torch.ones_like(bndiff2) * dbnvar\n",
    "# dbndiff += (2 * bndiff) * dbndiff2\n",
    "# dhprebn = dbndiff.clone()\n",
    "# dbnmeani = (-dbndiff).sum(0, keepdims=True)\n",
    "# dhprebn += (1.0 / n) * torch.ones_like(hprebn) * dbnmeani\n",
    "\n",
    "# now:\n",
    "dhprebn = batchn_gain * bnvar_inv / n * (n * dhpreact - dhpreact.sum(0) - n / (n - 1) * bnraw * (dhpreact * bnraw).sum(0))\n",
    "cmp('hprebn', dhprebn, hprebn) # cannot get exact number but 8e-11 is very small"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3ac8082",
   "metadata": {},
   "source": [
    "# Putting It All Together"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bb9745cb",
   "metadata": {},
   "source": [
    "### Now that we have the simplified backward pass of both the loss function and the batch norm layer, we can use them to train the MLP with our own  manual backward pass!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "46308362",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# of parameters:  6408\n",
      "      0/200000: 3.3452\n",
      "  10000/200000: 1.9160\n",
      "  20000/200000: 1.8283\n",
      "  30000/200000: 2.2049\n",
      "  40000/200000: 1.5346\n",
      "  50000/200000: 1.8802\n",
      "  60000/200000: 1.9436\n",
      "  70000/200000: 1.8928\n",
      "  80000/200000: 1.6813\n",
      "  90000/200000: 2.3385\n",
      " 100000/200000: 1.7800\n",
      " 110000/200000: 1.9994\n",
      " 120000/200000: 1.7383\n",
      " 130000/200000: 1.9245\n",
      " 140000/200000: 2.2288\n",
      " 150000/200000: 1.6355\n",
      " 160000/200000: 2.0972\n",
      " 170000/200000: 1.8194\n",
      " 180000/200000: 1.8499\n",
      " 190000/200000: 1.9338\n"
     ]
    }
   ],
   "source": [
    "# train MLP with manual backward pass\n",
    "\n",
    "# initialize\n",
    "n_embed = 10 # dimensionality of charcter embedding vectors\n",
    "n_hidden = 100 # number of neurons in each hidden layer\n",
    "\n",
    "g = torch.Generator().manual_seed(42)\n",
    "\n",
    "C = torch.randn((vocab_size, n_embed),             generator=g) # create a lookup table\n",
    "\n",
    "# layer 1\n",
    "W1 = torch.randn((n_embed * block_size ,n_hidden), generator=g) * (5/3) / ((n_embed * block_size)**0.5) # weights matrix\n",
    "b1 = torch.randn(n_hidden,                         generator=g) * 0.01 # b1 does nothing because of batch norm\n",
    "\n",
    "# layer 2\n",
    "W2 = torch.randn((n_hidden, vocab_size),           generator=g) * 0.01 # weights matrix\n",
    "b2 = torch.randn(vocab_size,                       generator=g) * 0.01 # bias\n",
    "\n",
    "# batch norm params\n",
    "batchn_gain = torch.randn((1, n_hidden)) * 0.1 + 1.0\n",
    "batchn_bias = torch.randn((1, n_hidden)) * 0.1\n",
    "\n",
    "\n",
    "params = [C,W1,b1,W2,b2,batchn_gain,batchn_bias]\n",
    "\n",
    "print(\"# of parameters: \", sum(p.nelement() for p in params))\n",
    "for p in params:\n",
    "    p.requires_grad = True\n",
    "    \n",
    "max_steps = 200000\n",
    "batch_size = 32\n",
    "n = batch_size # short variable for convenience\n",
    "lossi = []\n",
    "\n",
    "with torch.no_grad(): # since we will be computing backprop ourselves\n",
    "    for i in range(max_steps):\n",
    "    \n",
    "        # create batch\n",
    "        idx = torch.randint(0, Xtr.shape[0], (n, ), generator=g)\n",
    "        Xb, Yb = Xtr[idx], Ytr[idx] # batch X and Y\n",
    "        \n",
    "        # forward pass\n",
    "        emb = C[Xb] # get character embeddings\n",
    "        emb_concat = emb.view(emb.shape[0], -1) # concat vectors\n",
    "\n",
    "        # linear layer 1\n",
    "        hprebn = emb_concat @ W1 + b1 # hidden layer pre-activation pre-batchnorm\n",
    "\n",
    "        # batch norm layer (same as gamma * (x - mean) / (std) + beta)\n",
    "        bnmean = hprebn.mean(0, keepdims=True)\n",
    "        bnvar = hprebn.var(0, keepdims=True, unbiased=True)\n",
    "        bnvar_inv = (bnvar + 1e-5)**-0.5\n",
    "        bnraw = (hprebn - bnmean) * bnvar_inv\n",
    "        hpreact = batchn_gain * bnraw + batchn_bias\n",
    "\n",
    "        # non-linear activation function\n",
    "        h = torch.tanh(hpreact) # hidden layer\n",
    "\n",
    "        # linear layer 2\n",
    "        logits = h @ W2 + b2 # output layer\n",
    "\n",
    "        # cross entropy loss (same as F.cross_entropy(logits, Yb))\n",
    "        loss = F.cross_entropy(logits, Yb)\n",
    "\n",
    "        # PyTorch backward pass\n",
    "        for p in params:\n",
    "            p.grad = None\n",
    "        \n",
    "        # manual backprop\n",
    "        #----------------------------\n",
    "        # loss\n",
    "        dlogits = F.softmax(logits, 1)\n",
    "        dlogits[range(n), Yb] -= 1\n",
    "        dlogits /= n\n",
    "        \n",
    "        # linear layer 2\n",
    "        dh = dlogits @ W2.T\n",
    "        dW2 = h.T @ dlogits\n",
    "        db2 = dlogits.sum(0)\n",
    "        \n",
    "        # non-linear activation function\n",
    "        dhpreact = (1.0 - h**2) * dh\n",
    "        \n",
    "        # batch norm layer\n",
    "        dbatchn_gain = (bnraw * dhpreact).sum(0, keepdims=True)\n",
    "        dbatchn_bias = dhpreact.sum(0, keepdims=True)\n",
    "        dhprebn = batchn_gain * bnvar_inv / n * (n * dhpreact - dhpreact.sum(0) - n / (n - 1) * bnraw * (dhpreact * bnraw).sum(0))\n",
    "\n",
    "        # linear layer 1\n",
    "        demb_concat = dhprebn @ W1.T\n",
    "        dW1 = emb_concat.T @ dhprebn\n",
    "        db1 = dhprebn.sum(0)\n",
    "        \n",
    "        # embedding\n",
    "        demb = demb_concat.view(emb.shape)\n",
    "        dC = torch.zeros_like(C)\n",
    "        for k in range(Xb.shape[0]):\n",
    "            for j in range (Xb.shape[1]):\n",
    "                idx = Xb[k,j]\n",
    "                dC[idx] += demb[k,j]\n",
    "        grads = [dC, dW1, db1, dW2, db2, dbatchn_gain, dbatchn_bias]\n",
    "        #----------------------------\n",
    "        \n",
    "        \n",
    "        lr = 0.1 if i < (150000) else 0.01\n",
    "        for p, grad in zip(params, grads):\n",
    "            p.data += -lr * grad\n",
    "            \n",
    "        if i % 10000 == 0:\n",
    "            print(f'{i:7d}/{max_steps}: {loss.item():.4f}')\n",
    "        lossi.append(loss.log10().item())\n",
    "        \n",
    "#         if i > 1000:\n",
    "#             break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "06f8752c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# calibrate batch norm at end of training\n",
    "with torch.no_grad():\n",
    "    # use training set\n",
    "    emb = C[Xtr]\n",
    "    emb_concat = emb.view(emb.shape[0], -1)\n",
    "    hpreact = emb_concat @ W1 + b1\n",
    "    \n",
    "    # mean and variance over entire set\n",
    "    bnmean = hpreact.mean(0, keepdims=True)\n",
    "    bnvar =  hpreact.var(0, keepdims=True, unbiased=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "606d552c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "train loss: 2.4964325428009033\n",
      "dev loss: 2.49499249458313\n"
     ]
    }
   ],
   "source": [
    "@torch.no_grad()\n",
    "def dataset_loss(dataset):\n",
    "    x, y = {\n",
    "        'train': (Xtr, Ytr),\n",
    "        'dev': (Xdev, Ydev),\n",
    "        'test': (Xte, Yte),\n",
    "    }[dataset]\n",
    "    \n",
    "    emb = C[x] # create embedding of characters into vectors\n",
    "    emb_concat = emb.view(emb.shape[0], -1) # concetenate vectors\n",
    "\n",
    "    h_preact = emb_concat @ W1 + b1 # hidden layer pre-activation\n",
    "    h_preact = batchn_gain * (h_preact - bnmean) / bnvar + batchn_bias\n",
    "    h = torch.tanh(h_preact) # hidden layer\n",
    "    logits = h @ W2 + b2 # output layer\n",
    "\n",
    "    loss = F.cross_entropy(logits, y) # use cross entropy as loss function\n",
    "    print(f'{dataset} loss: {loss.item()}')\n",
    "\n",
    "dataset_loss('train')\n",
    "dataset_loss('dev')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "f8ead071",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "anoula l maroe.\n",
      "harrlanv aesuld.\n",
      "flino.\n",
      "togle.\n",
      "vorwol.\n"
     ]
    }
   ],
   "source": [
    "# sample from model\n",
    "for _ in range(5):\n",
    "    out = [] # output array\n",
    "    context = [0] * block_size # context 'window'\n",
    "    \n",
    "    while True:\n",
    "        emb = C[torch.tensor([context])] # get embeddings from context and lookup table\n",
    "        emb_concat = emb.view(emb.shape[0], -1)\n",
    "        \n",
    "        h_preact = emb_concat @ W1 + b1 # hidden layer pre-activation\n",
    "        h_preact = batchn_gain * (h_preact - bnmean) / bnvar + batchn_bias\n",
    "        h = torch.tanh(h_preact) # hidden layer\n",
    "        logits = h @ W2 + b2 # output layer\n",
    "        probs = F.softmax(logits, dim=1) # softmax to get probabilites\n",
    "        \n",
    "        idx = torch.multinomial(probs, num_samples=1, generator=g).item() # get next predicted letter\n",
    "        context = context[1:] + [idx] # slide the context 'window'\n",
    "        out.append(idx) # append the new letter to the output\n",
    "        \n",
    "        # if the character is '.' then end the word\n",
    "        if idx == 0:\n",
    "            break\n",
    "    \n",
    "    print(''.join(itos[i] for i in out))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "532e324c",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "makemore (env)",
   "language": "python",
   "name": "env"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}