Notes for — The spelled-out intro to language modeling: building makemore
January 12th, 2023Derived from: https://github.com/karpathy/nn-zero-to-hero/blob/master/lectures/makemore/makemore_part1_bigrams.ipynb
Makemore
Purpose: to make more of examples you give it. Ie: names
training makemore on names will make unique sounding names
this dataset will be used to train a character level language model
modelling sequence of characters and able to predict next character in a sequence
makemore implements a services of language model neural nets
Bigram Bag of Words MLP RNN GRU Transformer like GPT2 (NanoGPT Yay!)
describe the problem in terms of probabilities. wrt name isabella, the i is likely to be first char in a word, s is likely to come after i and so on until a is the likely be after an l and the last letter of a name
understand the dataset, load into array and check min/max
words = open('names.txt', 'r').read().splitlines()
words[:10]
len(words)
min(len(w) for w in words)
max(len(w) for w in words)
wrt name isabella, the i is likely to be first char in a word, s is likely to come after i and so on until a is the likely be after an l and the last letter of a name
a bigram model looks at two characters at a time and tries to predict the next character in the sequence
zip(chs, chs[1:]) returns tuples of characters in each set. For example when the word is emma chs = emma and chs[1:] = mma Thus the tuples of emma, mma are: em, mm, ma, a[NULL] which returns NULL and you are just left with the first 3 tuples.
using a start and end tokens you can track what names start and end with
the dictionary b stores the counts of bigrams
b = {}
for w in words:
chs = ['<S>'] + list(w) + ['<E>']
for ch1, ch2 in zip(chs, chs[1:]):
bigram = (ch1, ch2)
b[bigram] = b.get(bigram, 0) + 1
b.items() returns the tuples of the bigram and counts sorted sorts by counts and - makes it decending order
sorted(b.items(), key = lambda kv: -kv[1])
what we see in the above example is that "n" is the most common character at the end of a name, followed by "a", "n" often comes after an "a" ... and so no
it is significantly more convenient to store this in a 2D array rows are the first character of the two characters and columns are the second character each entry will tell us how often the first character follows the second character in the dataset
you can index into a tensor arrays using comma separated. ie: a[1, 3] would index to a[1][3]
import torch
27 X 27 because we use the 26 characters + 1 start/end token
N = torch.zeros((27, 27), dtype=torch.int32)
chars is indexed list of characters stoi is an index mapping of each character to an integer index itos is the inverse lookup of stoi
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()}
as we iterate over each tuple we increment a counter in the tensor
instead of having two special tokens we can just use 1 because 2 is not needed and in fact creates an entire row and column of zeros because there would never be a characters before the first or after the last.
So we replace that with just a . token which can be used to represent both tokens and will provide more optimal storage efficiency.
for w in words:
chs = ['.'] + list(w) + ['.']
for ch1, ch2 in zip(chs, chs[1:]):
ix1 = stoi[ch1]
ix2 = stoi[ch2]
N[ix1, ix2] += 1
matplotlib allows you to create figures
the reason you have N[i, j].item() is because when you index into the array you get a tensor back. using .item() will return an int instead.
import numpy
import matplotlib.pyplot as plt
%matplotlib inline
plt.figure(figsize=(16,16))
plt.imshow(N, cmap='Blues')
for i in range(27):
for j in range(27):
chstr = itos[i] + itos[j]
plt.text(j, i, chstr, ha="center", va="bottom", color='gray')
plt.text(j, i, N[i, j].item(), ha="center", va="top", color='gray')
plt.axis('off');
this array has everything we need to sample from the bigram model
the counts tell us how often we start any word
N[0]
the reason we create floats is because we are going to normalize these counts to create a probability distribution
p = N[0].float()
p = p / p.sum()
p
torch.multinomial returns a sample from the multinomial distribution. you give me probabilities and I will give you integers which are sampled according to the probability distribution.
using a specific seed, will give us a deterministic example so that examples can align
so we create a seeded generator and use this to generate 1 sample according to the probability distribution p this returns us a tensor with a single integer sampled from p according to the seeded randomness we use .item() to pop out the int of the tensor and then use itos to convert it to a character
g = torch.Generator().manual_seed(2147483647)
ix = torch.multinomial(p, num_samples=1, replacement=True, generator=g).item()
itos[ix]
g = torch.Generator().manual_seed(2147483647)
p = torch.rand(3, generator=g)
p = p / p.sum()
p
torch.multinomial(p, num_samples=100, replacement=True, generator=g)
p.shape
we want to divide each row by their respective sums
if keepdim is True then the output tensor is the same size as the input except in the dimension(s) dim where it is size of 1. if keepdim is False the dimension is squeezed out
broadcasting semantics in torch two tensors are broadcastable if -each tensor has at least one dimension -when iterating over the dimension sizes, starting at the trailing dimension, the dimension sizes must either be equal or one of them is 1, or one of them does not exist
(27, 27) (27, 1)
it takes this dimension 1 and stretches it out, copies it 27 times to make both be 27, 27 internally
P = (N+1).float()
P /= P.sum(1, keepdims=True)
if we did not put in keepdims=True, then instead of having a 27, 1 array, the 1 dimension would be squeezed out leaving us with an array of 27. when doing the /= operation, the counts are aligned right to left so the dimension that gets added back in is on the left leaving us with a 1, 27. consequently we would be normalizing the columns instead of the rows and this causes a bug that gives us back garbage. The check below tests whether the row is normalized properly and should sum to 1
P /= P.sum... is an in place Tensor where as P = P / P.sum... would create another copy of P and be wasteful
P[0].sum()
https://pytorch.org/docs/stable/notes/broadcasting.html In order for an operation to be broadcastable: -each tensor has at least one dimension -when iterating over the dimension sizes starting at the trailing dimension, the dimension sizes must either be equal, one of them is 1 or one of them does not exist
we begin at index 0 while true we are going to grab the row of the array for the letter we are currently on we normalize this array into a probability distribution that sums to 1 we use the seeded generator object and we draw a single sample from the distribution and that will tell us what index for the next sample row will be we append the converted index to a character and append that to out if we select '.' as the indexed character (ix == 0) then we break
g = torch.Generator().manual_seed(2147483647)
for i in range(5):
out = []
ix = 0
while True:
p = P[ix]
ix = torch.multinomial(p, num_samples=1, replacement=True, generator=g).item()
out.append(itos[ix])
if ix == 0:
break
print(''.join(out))
# GOAL: maximize likelihood of the data w.r.t. model parameters (statistical modeling)
# equivalent to maximizing the log likelihood (because log is monotonic)
# equivalent to minimizing the negative log likelihood
# equivalent to minimizing the average negative log likelihood
# log(a*b*c) = log(a) + log(b) + log(c)
likelihood is product of probabilities by multiplying probabilities which have numbers between 0 and 1 you end up with a very small number to combat this, you use the log likelihood. log log_likelihood returns a number closer to 0 when probability is close to 1 and -inf when probability is close to 0 as commented above log(abc) = log(a) + log(b) + log(c) which are all negative. but for our loss function we want to minimize our loss and so lower numbers are better. therefore we need to take the negative log likelihood to invert the sign of the log likelihood so that our loss function makes sense if we then use a counter (n) to keep track of number of samples, we can normalize the negative log likelihood (nll) by dividing by n
in the example of andrejq, the probability of jq occuring is 0 which gives us infinite loss as such we modify the probability array from P = N.float() to P = (N+1).float() do give some unlikely but non-zero probability that will avoid give us infinity
log_likelihood = 0.0
n = 0
for w in words:
#for w in ["andrejq"]:
chs = ['.'] + list(w) + ['.']
for ch1, ch2 in zip(chs, chs[1:]):
ix1 = stoi[ch1]
ix2 = stoi[ch2]
prob = P[ix1, ix2]
logprob = torch.log(prob)
log_likelihood += logprob
n += 1
#print(f'{ch1}{ch2}: {prob:.4f} {logprob:.4f}')
print(f'{log_likelihood=}')
nll = -log_likelihood
print(f'{nll=}')
print(f'{nll/n}')
torch.tensor infers the dtype automatically while torch.Tensor returns a torch.FloatTensor stick with torch.tensor and explicity set dtype when applicable in the below example we want integers, so using .tensor is the best way to easily achieve that
# create the training set of bigrams (x,y)
xs, ys = [], []
for w in words[:1]:
chs = ['.'] + list(w) + ['.']
for ch1, ch2 in zip(chs, chs[1:]):
ix1 = stoi[ch1]
ix2 = stoi[ch2]
print(ch1, ch2)
xs.append(ix1)
ys.append(ix2)
xs = torch.tensor(xs)
ys = torch.tensor(ys)
xs
ys
as we iterate through xs, we want to tune the NN to have high probabilities wrt ys. for example with .emma. we want to tune NN to have e high probability of start, m high probability to follow e, m also high probability of following m ...
one hot encoding we take an integer like 13 and we make it all zeros except for the 13th position where it becomes a 1 this encoding is much better suited to feed into a NN than the integer value 13, you also supply the num_classes variable which is the size of the set you want to encode (26 + 1 for .)
one_hot function does not take in a dtype, so to ensure this is a float32 instead of int64, we need to append .float() to the end of the one_hot function call
import torch.nn.functional as F
xenc = F.one_hot(xs, num_classes=27).float()
xenc
xenc.shape
what we see is .emma represented by 5 rows of integer encodings of the character where each bit is turned on in the stoi'th column . => 0 => [1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.] e => 5 => [0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.] m => 13 => [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.] m => 13 => [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.], a => 1 => [0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.]
plt.imshow(xenc)
xenc.dtype
torch.randn fills a tensor with random numbers drawn from a normal distribution (most numbers will be around 0 but some will be as high/low as +-3)
W is size 27, 1 xenc is 5, 27 the @ operation is a matrix multiplication operater in pytorch (dot product) when we multiple 5,27 with 27,1 we get a result of size 5, 1
this leaves us with 5 activations of this neuron on these 5 inputs evaluated in parallel
W = torch.randn((27, 27))
xenc @ W
(xenc @ W).shape
the firing rate of the 13th neuron looking at the 3rd input
(xenc @ W)[3, 13]
(xenc[3])
W[:, 13]
(xenc[3] * W[:, 13]).sum()
logits = xenc @ W # log-counts
counts = logits.exp() # equivalent N
probs = counts / counts.sum(1, keepdims=True)
probs
probs[0]
probs[0].shape
probs[0].sum()
# (5, 27) @ (27, 27) -> (5, 27)
# SUMMARY ------------------------------>>>>
xs
ys
# randomly initialize 27 neurons' weights. each neuron receives 27 inputs
g = torch.Generator().manual_seed(2147483647)
W = torch.randn((27, 27), generator=g)
by exponentiating the random sampled array, we are given positive floats such as one that could be used to predict integer counts for likelihood the logits are the "log counts" therefore counts is logits.exp()
probs is the normalized probabilities of counts
@ exp() and / + are all differentiable operations
we are: -taking inputs -we have differentiable operations we can backpropagate through -we are getting out probability distributions
softmax is a very often used layer in a neural net which takes logits exponentiates them and divides and normalizes them it takes a nerual net layer which could be positive or negative and outputs a probability distribution that always sums to 1 (normalizing function)
xenc = F.one_hot(xs, num_classes=27).float() # input to the network: one-hot encoding
logits = xenc @ W # predict log-counts
counts = logits.exp() # counts, equivalent to N
probs = counts / counts.sum(1, keepdims=True) # probabilities for next character
# btw: the last 2 lines here are together called a 'softmax'
probs.shape
nlls = torch.zeros(5)
for i in range(5):
# i-th bigram:
x = xs[i].item() # input character index
y = ys[i].item() # label character index
print('--------')
print(f'bigram example {i+1}: {itos[x]}{itos[y]} (indexes {x},{y})')
print('input to the neural net:', x)
print('output probabilities from the neural net:', probs[i])
print('label (actual next character):', y)
p = probs[i, y]
print('probability assigned by the net to the the correct character:', p.item())
logp = torch.log(p)
print('log likelihood:', logp.item())
nll = -logp
print('negative log likelihood:', nll.item())
nlls[i] = nll
print('=========')
print('average negative log likelihood, i.e. loss =', nlls.mean().item())
# --------- !!! OPTIMIZATION !!! yay --------------
xs
ys
# randomly initialize 27 neurons' weights. each neuron receives 27 inputs
g = torch.Generator().manual_seed(2147483647)
W = torch.randn((27, 27), generator=g, requires_grad=True)
in makemore we are using negative log liklihood because we doing classification autograd used mean squared error because it was doing regression
loss is the negative log likelihood
to do gradient descent, you loop through forward pass, backward pass, adjustment for each labelled example tuning the NN
# forward pass
xenc = F.one_hot(xs, num_classes=27).float() # input to the network: one-hot encoding
logits = xenc @ W # predict log-counts
counts = logits.exp() # counts, equivalent to N
probs = counts / counts.sum(1, keepdims=True) # probabilities for next character
loss = -probs[torch.arange(5), ys].log().mean()
print(loss.item())
# backward pass
W.grad = None # set to zero the gradient
loss.backward()
W.grad
W.data += -0.1 * W.grad
# --------- !!! OPTIMIZATION !!! yay, but this time actually --------------
# create the dataset
xs, ys = [], []
for w in words:
chs = ['.'] + list(w) + ['.']
for ch1, ch2 in zip(chs, chs[1:]):
ix1 = stoi[ch1]
ix2 = stoi[ch2]
xs.append(ix1)
ys.append(ix2)
xs = torch.tensor(xs)
ys = torch.tensor(ys)
num = xs.nelement()
print('number of examples: ', num)
# initialize the 'network'
g = torch.Generator().manual_seed(2147483647)
W = torch.randn((27, 27), generator=g, requires_grad=True)
num
if the regularization loss to too strong, you wont be able to overcome the loss and everything will be uniform predictions
# gradient descent
for k in range(300):
# forward pass
xenc = F.one_hot(xs, num_classes=27).float() # input to the network: one-hot encoding
logits = xenc @ W # predict log-counts
counts = logits.exp() # counts, equivalent to N
probs = counts / counts.sum(1, keepdims=True) # probabilities for next character
loss = -probs[torch.arange(num), ys].log().mean() + 0.01*(W**2).mean() # + 0.01*(W**2).mean() regularization loss
print(loss.item())
# backward pass
W.grad = None # set to zero the gradient
loss.backward()
# update
W.data += -50 * W.grad
# finally, sample from the 'neural net' model
g = torch.Generator().manual_seed(2147483647)
for i in range(5):
out = []
ix = 0
while True:
# ----------
# BEFORE:
#p = P[ix]
# ----------
# NOW:
xenc = F.one_hot(torch.tensor([ix]), num_classes=27).float()
logits = xenc @ W # predict log-counts
counts = logits.exp() # counts, equivalent to N
p = counts / counts.sum(1, keepdims=True) # probabilities for next character
# ----------
ix = torch.multinomial(p, num_samples=1, replacement=True, generator=g).item()
out.append(itos[ix])
if ix == 0:
break
print(''.join(out))
both the bigram probability population (N) and the weights of the neural net (W) end up being the same though they arrive that these numbers much differently N is computed by summing up the probabilities and taking the log W is computed first by some random sampling, then multiplying the training set one_hot encoded with the training set to get the logits the logits exponentiated is equal to the counts the probs normalizes the counts into a probability distribution loss = -probs[torch.arange(num), ys].log().mean() + 0.01*(W**2).mean() probs[torch.arange(num), ys] plucks out the probabilities that the neural net assigns to the correct next character .log() because we actually look at the log probability .mean() is the average then we multiply by -1 to take the negative log likelihood
calling .backward() will fill in all the gradients for our W (W.grad)
Homework:
- Review Torch Broadcasting Semantics
Posted In:
ABOUT THE AUTHOR:Software Developer always striving to be better. Learn from others' mistakes, learn by doing, fail fast, maximize productivity, and really think hard about good defaults. Computer developers have the power to add an entire infinite dimension with a single Int (or maybe BigInt). The least we can do with that power is be creative.
Subscriptions:
The Limiting Factor
Whole Mars Catalog