What I learned today

Intro

I have been dabbling off and on in various aspects of machine learning. At times I struggled to stay engaged as the material I looked at seemed a little ‘handwavy’. A friend of mine suggested that I check out the videos on LLMs from Andrej Karpathy. I did and was really impressed. Andrej presents complex concepts from the ground up going through Jupyter notebooks, injecting pen-and-paper theory where it makes sense. Andrej is a gifted teacher and I stayed engaged as I followed along. Andrej breaks down complex concepts, explains them really well and helps develop an intuitive understanding of LLM principles. I am documenting my learning journey in this blog that summarizes the content and more importantly elaborates on concepts that I initially struggled to wrap my head around. All you need to follow along is a laptop, some basic Python skills and the willingness to at times brush up on your high-school math.

Setting up your runtime

To follow Andrej along I tried Google Colab and Jupyter notebooks on my laptop. Colab is a fully managed notebook environment run by Google. Unless you upgrade to a paid version performance is not great but good enough for going through the exercises. One big benefit of Colab is that it is integreated with Gemini, Google’s AI/ML model. Through this integration Colab provides code assistant functionality that can drastically increase your productivity when you are stuck with an error message or need a code sample.

Colab

To get started, download the notebook from Andrej’s github page.

Upload the notebook to Google Drive. Right click on the notebook file in Google drive and open with Google Colaboratory.

The notebook will open in Colab. Add the cell below as the first cell (Escape-A) in the Colab notebook to download names.txt, a list of names needed for testing and training throughout the series, and execute (Shift-Return).

You should be set to follow along. For the later Makemore videos Andrej provides a ready-to-go Colab link for the respective notebooks.

Jupyter

“The Jupyter Notebook App is a server-client application that allows editing and running notebook documents via a web browser. The Jupyter Notebook App can be executed on a local desktop requiring no internet access or can be installed on a remote server and accessed through the internet” (Jupyter/IPython Notebook Quick Start Guide).

The following instructions are for setting up the Jupyter server on your laptop and connecting to it. They are for Ubuntu 22.04 and should work on all Debian based systems. Python 3 ships with all distributions so we are assuming that it is already available on your system.

First we need to install the Python package manager pip. We need to add the ‘universe’ repo

sudo add-apt-repository universe

Now we can install the Python package manager pip3

sudo apt install python3-pip

And verify the installation

ubuntu@ubuntu:~$ pip3 --version
pip 22.0.2 from /usr/lib/python3/dist-packages/pip (python 3.10)

Python installs packages side-by-side with OS Python packages. If you install and update packages you can easily ‘shoot yourself in the foot’. You could, for example, update a version of a package that another package depends on. If the depending package relies on a specific older version of the package you just updated you broke things. Therefore it is best that you set up an isolated, virtual environment where you can install and break things without affecting the system installation of Python. I am using virtualenv to manage my virtual enironment

pip3 install virtualenv

As the installation output suggests you want to add virtualenv to your path in your .bashrc. Now you can create and activate a new virtual environment with

virtualenv myenv
. ./virtualenv/bin/activate

And you should see something like this

Now you can install the packages we need in your virtual environment

pip3 install notebook
pip3 install torch
pip install numpy
pip install matplotlib

If you don’t have github installed on your system install it with

sudo apt update && sudo apt install git

Clone Andrej’s repo with

git clone https://github.com/karpathy/nn-zero-to-hero/

cd into the directory with the notebook we need and download the names file that we will train the model on.

wget https://github.com/karpathy/makemore/blob/master/names.txt

Now you can launch jupyter with

jupyter notebook

Makemore

What is Makemore?

Makemore is a character level language model. It is trained on a list of names. The trained model is then used to generate new names. These names are generated character by character. The model takes an input character and predicts the following character in the name picking the next likely character based on a probability distribution. Each tuple of input and predicted character is called a bigram. The model uses the ‘.’ character as a delimiter that is added as the first and last character of a name. For inferring names we start feeding the model the ‘.’ character. The next character is predicted and then fed back into the model to predict the second character etc. The next predicted ‘.’ character will be terminating the predicted name (details below in the ‘Putting it all together’ section). The first model we are building is not generated through training a neural network, the second one is. The first model uses bigrams found in an list of over 32,000 names to build 27 probability distributions (one per character) we can use for predictions. The second model is trained starting with randomly initialized numbers and also generates one probability distribution per character.

If this does not really make sense yet that is totally OK. Please keep reading and it will most likely make sense to you in the end.

Importing Packages

First we import the Matplotlib and Pytorch libraries. Matplotlib is a visualization library. Pytorch is a deep learning framework. We will use the torch.tensor module to create and perform operations on multi-dimensional arrays.

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

The dataset

names.txt is an ascii file that contains 32033 names. To build a character based model we need to get a list of all characters we have. We open the file, read all names into one large string and split that string by line break so that each word gets added to the list ‘words’. By joining all words and ‘casting’ to a Python set we eliminate duplicate characters. We then pass these characters to to the sort function and end up with a character list of length 26.

words = open('names.txt', 'r').read().splitlines()
chars = sorted(set(''.join(words)))

Mapping characters to integers

To build our simple model we need to translate bigrams to integers. By enumerating over all characters and adding a mapping of ‘.’ to zero we create a dictionary stoi that maps each character in a name to an integer { ‘.’: 0, ‘a’: 1, ‘b’: 2 …}. itos does the reverse mapping.

stoi = {s:i+1 for i,s in enumerate(chars)}
stoi['.'] = 0
itos = {i:s for s,i in stoi.items()}
print(itos)

Count and probability matrix

To represent the bigram counts for our names we create a 27×27 pytorch matrix of type integer with all values set to 0. We iterate over all words in our list of names. We prepend and append ‘.’ to each name and extract the bigrams for each name. chs is the list of all characters in a name, chs[1:] is the same list skipping the first element. If we look at the name ’emma’, chs is [.],[e],[m],[m],[a],[.] and chs[1:] is [e],[m],[m],[a],[.]. The zip function creates an iterator over tuples that are the paired up characters from chs and chs[1:] in our example (‘.’, ‘e’), (‘e’, ‘m’), (‘m’, ‘m’) …. ch1 and ch2 are the characters in each tuple/bigram. We map the bigram characters to integers with stoi and index into our count matrix N to increase the count for each bigram.

N = torch.zeros((27,27), dtype=torch.int32)
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

And we can now visualize our count matrix N with matplotlib. ‘%matplotlib inline’ specifies that our matplotlib graphs will be included in our notebook, next to the code. plt.figure sets the size of our image and plt.imshow visualizes the count matrix N, mapping the values to a blue colormap. Now with i and j we loop over all bigrams and for each bigram reverse map to the respective characters. We display the bigram characters and their count in the corresponding position in the count matrix plot. ‘plt.axis(‘off’)’ removes the labels along the x and y axis.

Each row represents a character and all possible following characters from ‘.’ to ‘z’. The first row in this matrix shows how often each character is the first character , the first column shows how often each character is the last character.

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');

Side note: The elements in the count matrix are of pytorch type tensor. To convert these numbers to regular integers you need to use the pytorch function item() on the elements.

To enable sampling from the model that enables us to predict the next character we need to convert the counts to probabilties so that each row can be interpreted as a probability distribution. We convert all numbers to type float. For each row we normalize by dividing each value by the sum of values in that row to get a value between 0 and 1 that represents a probability.

To calculate the sum over all columns in a row we use pytorch.sum. We need the arguments ‘1’ and ‘keepdims=True’. The ‘1’ is equivalent to ‘dim=1’ and indicates that we want to calculate the sum over all columns in a row. The number indicates the direction in which we want to ‘collapse’ all inputs. ‘0’ would be over all rows, ‘1’ collapses over all columns in a row. ‘keepdim=True’ indicates that we want to keep the dimension. A ‘mickey mouse’ example helps understand this

Without keepdim=True the dimension of the result is reduced to a vector with 2 elements. With keepdim=True the dimension is retained and we have a matrix of 2 rows with 1 column each. This matters as we are dividing P of shape 27×27 by ‘P.sum(1, keepdims=True)’, a matrix of shape 27×1.

P = N.float()
P /= P.sum(1, keepdims=True)

When encountered with a mismatch in dimensions pytorch ‘broadcasts‘. The single column of ‘P.sum(1, keepdims=True)’ is automatically copied (in our example 26 times) to generate a matrix that matches P so that each element of P can be divided by the ‘row sum’.

As seen in our ‘mickey mouse’ example without ‘keepdims=True’ we would have a row vector instead of a column vector as torch.sum() removes (‘squeezes out’) the dimension that has only one value. For the division pytorch’s broadcasting would implicitly copy the row vector instead of the column vector and we would end up with the wrong result. It is very important to be aware of broadcasting and dimensions.

To start the prediction we initialize torch.Generator, seeding it with a fixed number (2147483647) so that we get consistent, deterministic ‘random’ values. This allows for comparing results. The pytorch function torch.multinomial returns a sample value for a probability distribution.

g = torch.Generator().manual_seed(2147483647)

for i in range(20):
    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))

Likelihood

If we want to get a sense of the quality of the model we need to look at the probabilities for the correct characters. If we take the bigrams of the first three input names we can get their respective probabilities from P.

In a completely random distribution the probability for each bigram would be 1/27=3.7%. A probability higher than 3.7% indicates that the model has ‘learned’ and will have a higher than average probability for predicting the correct following character. The probability for each correct bigram is an indication of the model’s accuracy. To measure the quality of the entire model we can use the likelihood which is the product of probabilities for all existing bigrams in the training dataset. Theoretically, if every second character in the dataset can be predicted with 100% accuracy, the product of all probabilities sums to 1 i.e. the model is 100% accurate.

Log Likelihood

In reality the probability numbers are relatively small and the product of all probabilities will be an extremely small number which could lead to rounding errors and are generally ‘unwieldy’. Instead of calculating the likelihood by multiplying probabilities we can add the logs of the probabilities to make the numbers more manageable as the logarithm of a product is the sum of the logarithms of the factors as

We can use the sum of logs instead of the product of probabilities as a quality measure as the logarithm function is monotonically increasing i.e. a higher value for the probability always means that the value of the log of the probability is higher as well. The sum over the logs of probabilities for each correct bigram is called the log likelihood. The log likelihood range is -infinity to 0 for the perfect model. Note that torch.log is the logarithm with a basis of e not 10 IOW in this context ‘log()’ means ‘ln()’.

Negative Log Likelihood

As we are trying to identify a loss function that we can then minimize through an optimization (“An optimization problem seeks to minimize a loss function.“) we use use the negative of the log likelihood as a quality measure. The lowest the negative log likelihood can get is 0 for the perfect model and the higher it is the worse the model is. Sometimes people like to average the likelihood instead of summing it (normalized log likelihood).

log_likelihood = 0.0
n = 0
for w in words[:3]:
    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}')

So our goal is to maximize the likelihood (the product of probabilities) with respect to the model parameters. In our case the parameters are the bigram counts in the table. Later with neural nets we will see how we can optimize these parameters to maximize the log likelihood. Maximizing the log likelihood is equivalent to minimizing the (average) negative log likelihood.

Model Smoothing

If we have a bigram with a 0 count i.e. a zero probability we have a negative infinite number for that bigram as ln(0) is negative infinity. This means we cannot calculate the negative log likelihood. To prevent that we can add a count of 1.

P = (N+1).float()
P /= P.sum(1, keepdims=True)

This is called model smoothing. We can add any value. The higher the value the more uniform the model is, with uniform meaning that we are closer to an even distribution where all bigrams are predicted with the same probability.

Neural Network Approach

We arrived at the current model by counting characters and translating the counts into probabilities. Now we are taking an alternative approach using a neural network. With this approach we have a (randomly initialized) model with parameters/weights. The model takes a set of characters as an input and produces a set of following characters as output. In the training of the model we feed the model a set of characters of each bigram and calculate the loss using the ‘known’ following character. We then optimize the model (“tune the weights”) by adjusting the (at first randomly initialized) parameters/weights to minimize the loss for the correct following characters (the label).

To start we need to create a list of characters translated to integers that maps to the correct following characters translated to integers. That list is casted to a pytorch tensor. Note that for lowercase tensor the default type we are converting to is int64 where it is float for uppercase Tensor.

One Hot Encoding

Character prediction is a classification problem. The model tries to predict the label (i.e. following character) for a given input (character). For classification problems we need to think in terms of categories. Each character is in one of 27 categories. In our example we use one hot encoding to map each integer that represents a character, to an array of the size of the character set (27). All elements of that array are set to zero except the element that represents the input character e.g. [1,0,0, …] for ‘.’, [0,1,0, …] for ‘a’ etc.

Pytorch has a built-in function one_hot for one hot encoding and we can visualize the ‘bits’ that are turned on for our ’emma’ example. Note that we need to cast the output of one_hot to float.

Building a neural network

In the minimal neural network we are building here a neuron is simply a column vector W. The output is the dot product of input vector x and the weights of the column vector W. Typically neurons also have a bias that is added for each column vector and a non-linear activation function but we are ignoring that here.

We can create a neuron starting with a randomly initialized column vector of size 27 initialized with torch.randn that takes the one hot encoded vectors of size 27 that we created for each character as input. For each input we get one numerical value as output. So for 5 letters (input matrix of size 5×27) we get an output matrix of 5×1.

What we want to get to is a probability distribution for 27 characters for each input, analogous to the previous example where we calculated the probability distribution through bigram counting. We can achieve that through a matrix W of size 27×27 that produces one row vector of size 27 for each one hot encoded input i.e. for each letter. Our 5 letter input produces a 5×27 matrix as output. If we manipulate the matrix so that the output can be interpreted as a probability distribution (will do that below), we have one distribution per input character.

What do we need to do to go from randomly initialized values that follow a normal distribution to values that can be interpreted as a probability? torch.randn produces a normal distribution with values from roughly -3 to +3. When we dot multiply the one hot encoded input with the matrix we effectively select the row in the matrix that corresponds to the element of the input that is set to 1. So the dot product follows the same normal distribution as the randomly initialized matrix. But we don’t want a value distribution with a range of -3 to 3. We are trying to come to a probability distribution for the next character. To translate the random numbers into something that can represent a probability distribution for the next character we apply what is called a softmax function to each row of the matrix. We know that the probability distribution (the distribution in each row of W) needs to add up to 1 and each value is between 0 and 1. So we calculate the exponent for each value to make it positive and normalize by the sum of exponents over the row to normalize and come to a value between 0 and 1.

The result of the exponentiation can be interpreted as a count (also called logit) and the normalized results can be interpreted as a probability. With that, each row of the output now represents a probability distribution.

logits = xenc @ W
counts = logits.exp()
probs = counts / counts.sum(1, keepdims = True)

So putting this all together …

For the first character ‘.’ in the first bigram ‘.e’ in the first name “.emma.” we get one row of output probabilties [0.0607, 0.0100, 0.0123 … 0.1459] for each character. The probability of the correct character ‘e’ that follows the ‘first ‘.’ is 0.012286. The negative natural logarithm (basis e) of that value is 4.39927. This is a ‘bad’ prediction as even 1/27, the probability of an assumed even distribution, is higher than this value.

To evaluate the quality of the model we save the negative log likelihood for each bigram in an array that we average over once we have looped over all first characters.

Optimizing our neural network

What we have calculated up to now, going from the dot product of the one hot encoded input vectors and a randomly initialized matrix W, to the calculation of the mean over the negative loss likelihood for each prediction is called the forward pass. Our objective is to adjust the weights of W to minimize the loss that is a reflection of the accuracy of the model.

We can optimize the model through a technique that is called backpropagation. Andrej discussed the concept in detail in a separate video. Backpropagation calculates the derivative of the loss with respect to the model weights. The derivative for each element of W determines how each element influences the loss of the model. The derivative of the loss with respect to the first element in the first row of the weight matrix, w11 for example, is a value that indicates how a small change of w11 impacts the loss.

The derivative can be interpreted as the slope of the tangent of the loss function over w11 (the blue line in the graph). In this (made up) example the slope at w11=0.75 is about 0.7. If all other elements of the weight matrix stay constant and we increase w11 by a small numerical value of let’s say 0.1 the loss increases by ‘slope*stepwidth’, in our example roughly 0.07 from 0.68 to 0.75. If we step in the opposite direction the loss decreases by the same amount from 0.68 to 0.61. Backpropagation calculates the ‘slope’ for every element of the weight matrix. To lower the overall loss we adjust the numerical value of each weight in the direction of the negative gradient. So in our example where we have a slope of 0.7 and a step with of 0.1 we would update w11 to a new value of w11 – (0.7*0.1) = 0.61 to lower the loss.

After updating all elements to lower their respective contribution to the loss we run another forward pass to update the probabilities and recalculate the loss. The model is optimized by repeatedly going through this cycle. This approach is also called gradient descent.

The goal of this process is to converge to a minimum of the loss function and it is important to find the right step width. If it is too small it will take too many steps to reach the minimum i.e. set the weights to values that minimize the loss. If it is too large we could miss that minimum and ‘oscillate’ around the minimum and never converge.

To calculate the derivatives, Pytorch offers the backward function. Pytorch tracks the computational graph for the loss calculation and can work from the loss ‘backward’ as discussed in detail in Andrej’s micrograd video. To use backward() we need to make sure that our matrix is initialized with requires_grad=True. Before every invocation of backward we also need to make sure that we reset the gradients to ‘None’.

Putting it all together

So revisiting this full example, we first calculate the forward pass. Note that we set requires_grad=True for the weight matrix so that we can later calculate the gradient for the loss function. We iterate over all words in the dataset. xs holds each first character, ys, each second character, and we have again the randomly initialized 27×27 matrix as a starting point.

xs, ys = [], []
for w in words[:1]: #UPDATE!!!!
    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 - using the generator we can 
# generate reproducible 'random' numbers
g = torch.Generator().manual_seed(2147483647)
W = torch.randn((27,27), generator=g, requires_grad=True)

Now we run a for loop over 100 forward and a backward passes

for k in range(100):
    xenc = F.one_hot(xs, num_classes=27).float()
    logits = xenc @ W
    counts = logits.exp()
    probs = counts / counts.sum(1, keepdims = True)
    loss = -probs[torch.arange(num), ys].log().mean()
    print(loss.item())

    W.grad = None
    loss.backward()

    W.data += -0.1 * W.grad

We see that the results improve as we increase the learning rate i.e. the step width by which we multiply the gradient to adjust the weights. We adjust it from 0.1 all the way up to 50. This means that initially we were adjusting the weight values in increments that were too small and it would have taken a very long time to converge to the minimum.

Interestingly, the approach of training a network yields a result that is very close to the approach we took initially where we calculated a probability distribution by counting and normalizing the occurrences of each bigram. This is the probability distribution for character ‘.’ (int 0) obtained through counting

This is the probability distribution for ‘.’ (int 0) calculated through 100 iterations of forward and backward pass with a stepwidth/learning rate of 50

What we gained through the gradient based approach is flexibility. Right now we feed one character into the net but going forward we want to add more context i.e. feed more previous characters to predict the next character. With more input characters the approach of counting would be very difficult to model as we would have a massive amount of permutations. A bigram with two characters for example can be represented as a 27×27 matrix, if we add one more character we would need a three dimensional matrix of 27x27x27. As the number of characters in a context increases the number of characters to count over grows exponentially making it difficult to scale the model.

The other interesting thing is that adding a fixed very high value to all characters (see previous section on smoothing) is similar to setting all weights to 0. This creates a probability distribution that is similar to an even distribution as setting weights to 0 means setting counts to 1 (e^0=1) and probs to 1/<# of columns>.

If we add a component that increases the loss as the weights increase the forward/backwards pass model training will keep the values low, smoothing the distribution. Smoothing the distribution is important as it helps prevent overfitting the model, meaning training the model to work really well for the exact training set but not generalizing well. Adding a component to the loss that increases the loss as the weights increase is called regularization, for example

loss = -probs[torch.arange(num), ys].log().mean() + 0.01*(W**2).mean()

This can be thought of as a force that puts pressure on the optimization to keep the values of the weights low. Adding a larger constant (in our example 0.01) as multiplier is equivalent to adding a larger constant to the count in in the initial model.

Lastly we are looking at how we can predict the right following character from the model. We start with the character ‘.’ (int 0) and multiply the one-hot encoded vector with the trained weight matrix. We apply the softmax function to obtain a probability distribution that we sample from to predict the next character. The we use that predicted character as input for the next iteration. The loop breaks when we hit the final ‘.’ character and we re-start with the ‘.’ character for the next name.

# 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))

predicts ‘names’ like

The prediction is the same regardless of whether we obtained the probabilties through counting or training the model (if we train the model with the right learning rate and number of iterations). Because we are only using a single character to predict the next character the model does not perform well and the poor performance i.e. prediction of ‘names’ that are not really names is to be expected. We will improve the model in the follow-up videos.