Exercise 3

In [ ]:

# This exercise wasn't exactly smooth sailing for me, but I did try to understand most of it. Will try to come back to this whenever I can

# This exercise wasn't exactly smooth sailing for me, but I did try to understand most of it. Will try to come back to this whenever I can

In [1]:

# there no change change in the first several cells from last lecture

import torch
import torch.nn.functional as F
import matplotlib.pyplot as plt # for making figures
%matplotlib inline

# there no change change in the first several cells from last lecture import torch import torch.nn.functional as F import matplotlib.pyplot as plt # for making figures %matplotlib inline

In [ ]:

# download the names.txt file from github
!wget https://raw.githubusercontent.com/karpathy/makemore/master/names.txt

# download the names.txt file from github !wget https://raw.githubusercontent.com/karpathy/makemore/master/names.txt

In [3]:

# read in all the words
words = open('names.txt', 'r').read().splitlines()
# print(len(words))
# print(max(len(w) for w in words))
# print(words[:8])

# build the vocabulary of characters and mappings to/from integers
chars = sorted(list(set(''.join(words))))
stoi = {s:i+1 for i,s in enumerate(chars)}
stoi['.'] = 0
itos = {i:s for s,i in stoi.items()}
vocab_size = len(itos)
# print(itos)
# print(vocab_size)

# build the dataset
block_size = 3 # context length: how many characters do we take to predict the next one?

def build_dataset(words):
  X, Y = [], []

  for w in words:
    context = [0] * block_size
    for ch in w + '.':
      ix = stoi[ch]
      X.append(context)
      Y.append(ix)
      context = context[1:] + [ix] # crop and append

  X = torch.tensor(X)
  Y = torch.tensor(Y)
  # print(X.shape, Y.shape)
  return X, Y

import random
random.seed(42)
random.shuffle(words)
n1 = int(0.8*len(words))
n2 = int(0.9*len(words))

Xtr,  Ytr  = build_dataset(words[:n1])     # 80%
Xdev, Ydev = build_dataset(words[n1:n2])   # 10%
Xte,  Yte  = build_dataset(words[n2:])     # 10%

# read in all the words words = open('names.txt', 'r').read().splitlines() # print(len(words)) # print(max(len(w) for w in words)) # print(words[:8]) # build the vocabulary of characters and mappings to/from integers chars = sorted(list(set(''.join(words)))) stoi = {s:i+1 for i,s in enumerate(chars)} stoi['.'] = 0 itos = {i:s for s,i in stoi.items()} vocab_size = len(itos) # print(itos) # print(vocab_size) # build the dataset block_size = 3 # context length: how many characters do we take to predict the next one? def build_dataset(words): X, Y = [], [] for w in words: context = [0] * block_size for ch in w + '.': ix = stoi[ch] X.append(context) Y.append(ix) context = context[1:] + [ix] # crop and append X = torch.tensor(X) Y = torch.tensor(Y) # print(X.shape, Y.shape) return X, Y import random random.seed(42) random.shuffle(words) n1 = int(0.8*len(words)) n2 = int(0.9*len(words)) Xtr, Ytr = build_dataset(words[:n1]) # 80% Xdev, Ydev = build_dataset(words[n1:n2]) # 10% Xte, Yte = build_dataset(words[n2:]) # 10%

In [4]:

# utility function we will use later when comparing manual gradients to PyTorch gradients
def cmp(s, dt, t):
  ex = torch.all(dt == t.grad).item()
  app = torch.allclose(dt, t.grad)
  maxdiff = (dt - t.grad).abs().max().item()
  print(f'{s:15s} | exact: {str(ex):5s} | approximate: {str(app):5s} | maxdiff: {maxdiff}')

# utility function we will use later when comparing manual gradients to PyTorch gradients def cmp(s, dt, t): ex = torch.all(dt == t.grad).item() app = torch.allclose(dt, t.grad) maxdiff = (dt - t.grad).abs().max().item() print(f'{s:15s} | exact: {str(ex):5s} | approximate: {str(app):5s} | maxdiff: {maxdiff}')

In [9]:

n_embd = 10 # the dimensionality of the character embedding vectors
n_hidden = 64 # the number of neurons in the hidden layer of the MLP

g = torch.Generator().manual_seed(2147483647) # for reproducibility
C  = torch.randn((vocab_size, n_embd),            generator=g)
# Layer 1
W1 = torch.randn((n_embd * block_size, n_hidden), generator=g) * (5/3)/((n_embd * block_size)**0.5)
b1 = torch.randn(n_hidden,                        generator=g) * 0.1 # using b1 just for fun, it's useless because of BN
# Layer 2
W2 = torch.randn((n_hidden, vocab_size),          generator=g) * 0.1
b2 = torch.randn(vocab_size,                      generator=g) * 0.1
# BatchNorm parameters
bngain = torch.randn((1, n_hidden))*0.1 + 1.0
bnbias = torch.randn((1, n_hidden))*0.1

# Note: I am initializating many of these parameters in non-standard ways
# because sometimes initializating with e.g. all zeros could mask an incorrect
# implementation of the backward pass.

parameters = [C, W1, b1, W2, b2, bngain, bnbias]
print(sum(p.nelement() for p in parameters)) # number of parameters in total
for p in parameters:
  p.requires_grad = True

n_embd = 10 # the dimensionality of the character embedding vectors n_hidden = 64 # the number of neurons in the hidden layer of the MLP g = torch.Generator().manual_seed(2147483647) # for reproducibility C = torch.randn((vocab_size, n_embd), generator=g) # Layer 1 W1 = torch.randn((n_embd * block_size, n_hidden), generator=g) * (5/3)/((n_embd * block_size)**0.5) b1 = torch.randn(n_hidden, generator=g) * 0.1 # using b1 just for fun, it's useless because of BN # Layer 2 W2 = torch.randn((n_hidden, vocab_size), generator=g) * 0.1 b2 = torch.randn(vocab_size, generator=g) * 0.1 # BatchNorm parameters bngain = torch.randn((1, n_hidden))*0.1 + 1.0 bnbias = torch.randn((1, n_hidden))*0.1 # Note: I am initializating many of these parameters in non-standard ways # because sometimes initializating with e.g. all zeros could mask an incorrect # implementation of the backward pass. parameters = [C, W1, b1, W2, b2, bngain, bnbias] print(sum(p.nelement() for p in parameters)) # number of parameters in total for p in parameters: p.requires_grad = True

4137

In [10]:

batch_size = 32
n = batch_size # a shorter variable also, for convenience
# construct a minibatch
ix = torch.randint(0, Xtr.shape[0], (batch_size,), generator=g)
Xb, Yb = Xtr[ix], Ytr[ix] # batch X,Y

batch_size = 32 n = batch_size # a shorter variable also, for convenience # construct a minibatch ix = torch.randint(0, Xtr.shape[0], (batch_size,), generator=g) Xb, Yb = Xtr[ix], Ytr[ix] # batch X,Y

In [11]:

# forward pass, "chunkated" into smaller steps that are possible to backward one at a time

emb = C[Xb] # embed the characters into vectors
embcat = emb.view(emb.shape[0], -1) # concatenate the vectors
# Linear layer 1
hprebn = embcat @ W1 + b1 # hidden layer pre-activation
# BatchNorm layer
bnmeani = 1/n*hprebn.sum(0, keepdim=True)
bndiff = hprebn - bnmeani
bndiff2 = bndiff**2
bnvar = 1/(n-1)*(bndiff2).sum(0, keepdim=True) # note: Bessel's correction (dividing by n-1, not n)
bnvar_inv = (bnvar + 1e-5)**-0.5
bnraw = bndiff * bnvar_inv
hpreact = bngain * bnraw + bnbias
# Non-linearity
h = torch.tanh(hpreact) # hidden layer
# Linear layer 2
logits = h @ W2 + b2 # output layer
# cross entropy loss (same as F.cross_entropy(logits, Yb))
logit_maxes = logits.max(1, keepdim=True).values
norm_logits = logits - logit_maxes # subtract max for numerical stability
counts = norm_logits.exp()
counts_sum = counts.sum(1, keepdims=True)
counts_sum_inv = counts_sum**-1 # if I use (1.0 / counts_sum) instead then I can't get backprop to be bit exact...
probs = counts * counts_sum_inv
logprobs = probs.log()
loss = -logprobs[range(n), Yb].mean()

# PyTorch backward pass
for p in parameters:
  p.grad = None
for t in [logprobs, probs, counts, counts_sum, counts_sum_inv, # afaik there is no cleaner way
          norm_logits, logit_maxes, logits, h, hpreact, bnraw,
         bnvar_inv, bnvar, bndiff2, bndiff, hprebn, bnmeani,
         embcat, emb]:
  t.retain_grad()
loss.backward()
loss

# forward pass, "chunkated" into smaller steps that are possible to backward one at a time emb = C[Xb] # embed the characters into vectors embcat = emb.view(emb.shape[0], -1) # concatenate the vectors # Linear layer 1 hprebn = embcat @ W1 + b1 # hidden layer pre-activation # BatchNorm layer bnmeani = 1/n*hprebn.sum(0, keepdim=True) bndiff = hprebn - bnmeani bndiff2 = bndiff**2 bnvar = 1/(n-1)*(bndiff2).sum(0, keepdim=True) # note: Bessel's correction (dividing by n-1, not n) bnvar_inv = (bnvar + 1e-5)**-0.5 bnraw = bndiff * bnvar_inv hpreact = bngain * bnraw + bnbias # Non-linearity h = torch.tanh(hpreact) # hidden layer # Linear layer 2 logits = h @ W2 + b2 # output layer # cross entropy loss (same as F.cross_entropy(logits, Yb)) logit_maxes = logits.max(1, keepdim=True).values norm_logits = logits - logit_maxes # subtract max for numerical stability counts = norm_logits.exp() counts_sum = counts.sum(1, keepdims=True) counts_sum_inv = counts_sum**-1 # if I use (1.0 / counts_sum) instead then I can't get backprop to be bit exact... probs = counts * counts_sum_inv logprobs = probs.log() loss = -logprobs[range(n), Yb].mean() # PyTorch backward pass for p in parameters: p.grad = None for t in [logprobs, probs, counts, counts_sum, counts_sum_inv, # afaik there is no cleaner way norm_logits, logit_maxes, logits, h, hpreact, bnraw, bnvar_inv, bnvar, bndiff2, bndiff, hprebn, bnmeani, embcat, emb]: t.retain_grad() loss.backward() loss

Out[11]:

tensor(3.3479, grad_fn=<NegBackward0>)

In [12]:

#The entire Exercise 1 implementation combined

dlogprobs = torch.zeros_like(logprobs)
dlogprobs[range(n), Yb] = -1.0/n
dprobs = (1.0 / probs) * dlogprobs
dcounts_sum_inv = (counts * dprobs).sum(1, keepdim=True)
dcounts = counts_sum_inv * dprobs
dcounts_sum = (-counts_sum**-2) * dcounts_sum_inv
dcounts += torch.ones_like(counts) * dcounts_sum
dnorm_logits = counts * dcounts
dlogits = dnorm_logits.clone()
dlogit_maxes = (-dnorm_logits).sum(1, keepdim=True)
dlogits += F.one_hot(logits.max(1).indices, num_classes=logits.shape[1]) * dlogit_maxes
dh = dlogits @ W2.T
dW2 = h.T @ dlogits
db2 = dlogits.sum(0)
dhpreact = (1.0 - h**2) * dh
dbngain = (bnraw * dhpreact).sum(0, keepdim=True)
dbnraw = bngain * dhpreact
dbnbias = dhpreact.sum(0, keepdim=True)
dbndiff = bnvar_inv * dbnraw
dbnvar_inv = (bndiff * dbnraw).sum(0, keepdim=True)
dbnvar = (-0.5*(bnvar + 1e-5)**-1.5) * dbnvar_inv
dbndiff2 = (1.0/(n-1))*torch.ones_like(bndiff2) * dbnvar
dbndiff += (2*bndiff) * dbndiff2
dhprebn = dbndiff.clone()
dbnmeani = (-dbndiff).sum(0)
dhprebn += 1.0/n * (torch.ones_like(hprebn) * dbnmeani)
dembcat = dhprebn @ W1.T
dW1 = embcat.T @ dhprebn
db1 = dhprebn.sum(0)
demb = dembcat.view(emb.shape)
dC = torch.zeros_like(C)
for k in range(Xb.shape[0]):
  for j in range(Xb.shape[1]):
    ix = Xb[k,j]
    dC[ix] += demb[k,j]

#The entire Exercise 1 implementation combined dlogprobs = torch.zeros_like(logprobs) dlogprobs[range(n), Yb] = -1.0/n dprobs = (1.0 / probs) * dlogprobs dcounts_sum_inv = (counts * dprobs).sum(1, keepdim=True) dcounts = counts_sum_inv * dprobs dcounts_sum = (-counts_sum**-2) * dcounts_sum_inv dcounts += torch.ones_like(counts) * dcounts_sum dnorm_logits = counts * dcounts dlogits = dnorm_logits.clone() dlogit_maxes = (-dnorm_logits).sum(1, keepdim=True) dlogits += F.one_hot(logits.max(1).indices, num_classes=logits.shape[1]) * dlogit_maxes dh = dlogits @ W2.T dW2 = h.T @ dlogits db2 = dlogits.sum(0) dhpreact = (1.0 - h**2) * dh dbngain = (bnraw * dhpreact).sum(0, keepdim=True) dbnraw = bngain * dhpreact dbnbias = dhpreact.sum(0, keepdim=True) dbndiff = bnvar_inv * dbnraw dbnvar_inv = (bndiff * dbnraw).sum(0, keepdim=True) dbnvar = (-0.5*(bnvar + 1e-5)**-1.5) * dbnvar_inv dbndiff2 = (1.0/(n-1))*torch.ones_like(bndiff2) * dbnvar dbndiff += (2*bndiff) * dbndiff2 dhprebn = dbndiff.clone() dbnmeani = (-dbndiff).sum(0) dhprebn += 1.0/n * (torch.ones_like(hprebn) * dbnmeani) dembcat = dhprebn @ W1.T dW1 = embcat.T @ dhprebn db1 = dhprebn.sum(0) demb = dembcat.view(emb.shape) dC = torch.zeros_like(C) for k in range(Xb.shape[0]): for j in range(Xb.shape[1]): ix = Xb[k,j] dC[ix] += demb[k,j]

Similar boiler plate codes as done in the prev exercise and provided in the starter code^

---

EXERCISE 3

1:36:38 to 1:48:35 - Pen and Paper derivation

1:48:36 to - Implementation of the derivation in code

In [13]:

# Exercise 3: backprop through batchnorm but all in one go
# to complete this challenge look at the mathematical expression of the output of batchnorm,
# take the derivative w.r.t. its input, simplify the expression, and just write it out
# BatchNorm paper: https://arxiv.org/abs/1502.03167

# forward pass

# before:
# bnmeani = 1/n*hprebn.sum(0, keepdim=True)
# bndiff = hprebn - bnmeani
# bndiff2 = bndiff**2
# bnvar = 1/(n-1)*(bndiff2).sum(0, keepdim=True) # note: Bessel's correction (dividing by n-1, not n)
# bnvar_inv = (bnvar + 1e-5)**-0.5
# bnraw = bndiff * bnvar_inv
# hpreact = bngain * bnraw + bnbias

# now:
hpreact_fast = bngain * (hprebn - hprebn.mean(0, keepdim=True)) / torch.sqrt(hprebn.var(0, keepdim=True, unbiased=True) + 1e-5) + bnbias
print('max diff:', (hpreact_fast - hpreact).abs().max())

# Exercise 3: backprop through batchnorm but all in one go # to complete this challenge look at the mathematical expression of the output of batchnorm, # take the derivative w.r.t. its input, simplify the expression, and just write it out # BatchNorm paper: https://arxiv.org/abs/1502.03167 # forward pass # before: # bnmeani = 1/n*hprebn.sum(0, keepdim=True) # bndiff = hprebn - bnmeani # bndiff2 = bndiff**2 # bnvar = 1/(n-1)*(bndiff2).sum(0, keepdim=True) # note: Bessel's correction (dividing by n-1, not n) # bnvar_inv = (bnvar + 1e-5)**-0.5 # bnraw = bndiff * bnvar_inv # hpreact = bngain * bnraw + bnbias # now: hpreact_fast = bngain * (hprebn - hprebn.mean(0, keepdim=True)) / torch.sqrt(hprebn.var(0, keepdim=True, unbiased=True) + 1e-5) + bnbias print('max diff:', (hpreact_fast - hpreact).abs().max())

max diff: tensor(7.1526e-07, grad_fn=<MaxBackward1>)

In [14]:

# backward pass

# before we had:
# dbnraw = bngain * dhpreact
# dbndiff = bnvar_inv * dbnraw
# dbnvar_inv = (bndiff * dbnraw).sum(0, keepdim=True)
# dbnvar = (-0.5*(bnvar + 1e-5)**-1.5) * dbnvar_inv
# dbndiff2 = (1.0/(n-1))*torch.ones_like(bndiff2) * dbnvar
# dbndiff += (2*bndiff) * dbndiff2
# dhprebn = dbndiff.clone()
# dbnmeani = (-dbndiff).sum(0)
# dhprebn += 1.0/n * (torch.ones_like(hprebn) * dbnmeani)

# calculate dhprebn given dhpreact (i.e. backprop through the batchnorm)
# (you'll also need to use some of the variables from the forward pass up above)

#This is a direct implementation of what sensei did, as he said in the video this equation itself has a lot of breakdown steps to be considered
#But this is what we come up with at the end
dhprebn = bngain*bnvar_inv/n * (n*dhpreact - dhpreact.sum(0) - n/(n-1)*bnraw*(dhpreact*bnraw).sum(0))

cmp('hprebn', dhprebn, hprebn) # I can only get approximate to be true, my maxdiff is 9e-10

# backward pass # before we had: # dbnraw = bngain * dhpreact # dbndiff = bnvar_inv * dbnraw # dbnvar_inv = (bndiff * dbnraw).sum(0, keepdim=True) # dbnvar = (-0.5*(bnvar + 1e-5)**-1.5) * dbnvar_inv # dbndiff2 = (1.0/(n-1))*torch.ones_like(bndiff2) * dbnvar # dbndiff += (2*bndiff) * dbndiff2 # dhprebn = dbndiff.clone() # dbnmeani = (-dbndiff).sum(0) # dhprebn += 1.0/n * (torch.ones_like(hprebn) * dbnmeani) # calculate dhprebn given dhpreact (i.e. backprop through the batchnorm) # (you'll also need to use some of the variables from the forward pass up above) #This is a direct implementation of what sensei did, as he said in the video this equation itself has a lot of breakdown steps to be considered #But this is what we come up with at the end dhprebn = bngain*bnvar_inv/n * (n*dhpreact - dhpreact.sum(0) - n/(n-1)*bnraw*(dhpreact*bnraw).sum(0)) cmp('hprebn', dhprebn, hprebn) # I can only get approximate to be true, my maxdiff is 9e-10

hprebn          | exact: False | approximate: True  | maxdiff: 9.313225746154785e-10