A Simple Bigram Name Generator in Google Sheets

Onegram, twogram, redgram, bluegram

What is a bigram? A bigram is two adjacent letters in a string. Let's take the word "Dog" as an example. Here we can see two bigrams: "Do" and "og". Notice that 'Bi-' means two. Ostensibly, we can have n-grams of any size. Unigram, bigram, and trigram! Alternatively, we can give up with these fancy latin names and just call them by their number. four-gram, five-gram, six-gram!

The trigrams in the word "Hello" are:

• Hel
• ell
• llo

A bigram language model is a language model that predicts the next character in a sequence using a bigram frequency table. Let's look at a simple frequency table with just 5 characters.

I highlighted the first row. As you can see, in this frequency table the probability of c coming after a is 70%, very high! While the probability of b coming after a is 0%, completely improbable. This means that the bigram 'ac' is very common in our dataset, but the bigram 'ab' never appears, not even once.

Note: Each N-gram will have an N-dimensional frequency table. Bigram is a 2D table, trigram is 3D, and so on.

Dataset and Training a Model

Let's create the frequency table. First, let's download and import our dataset. The given examples use IPython and can be run in a Jupyter notebook.

    !wget https://raw.githubusercontent.com/karpathy/makemore/refs/heads/master/names.txt
    words = open("names.txt", "r").read().splitlines()
            

Next we need a way to convert characters into numbers. This numeric representation of a character is called a token. In large language models, tokens aren't just single characters, but entire word fragments. For simplicity, we'll just be using singular characters.

    chars = sorted(set(''.join(words)))
    vocab_size = len(chars)
    chartoint = {ch:idx for idx,ch in enumerate(chars)}
    
    print(chartoint['.']) # -> 0
    print(chartoint['a']) # -> 1
    print(chartoint['z']) # -> 26
            

Then we can count the frequencies of bigrams that appear in our dataset, putting the results into a tensor.

    import torch
    
    frequencies = torch.zeros((vocab_size, vocab_size))

    for word in words:
        for a, b in zip(word, word[:1]):
            ai = chartoint[a]
            bi = chartoint[b]
            frequencies[ai][bi] = frequencies[ai][bi] + 1
            

There is a flaw in our code though. Currently, the frequency table doesn't recognize the start or end of words. That can be fixed by adding special tokens for start and end.

    for word in words:
 +      word = ['<S>'] + list(word) + ['<E>']
        for a, b in zip(word, word[:1]):
            ai = chartoint[a]
            bi = chartoint[b]
            frequencies[ai][bi] = frequencies[ai][bi] + 1
            

Notice that '??? <S>' is an impossible pairing because '<S>' can only appear at the start, and '<E> ???' is an impossible pairing because '<E>' can only appear at the end. This wastes space because our frequency table is encoding pairings that can never occur. We can save on space by merging both cases into a single token. Let's call this combined start and end token '.', for no special reason other than it's simple and '.' never appears in our dataset.

    for word in words:
 -      word = ['<S>'] + list(word) + ['<E>']
 +      word = ['.'] + list(word) + ['.']
        for a, b in zip(word, word[:1]):
            ai = chartoint[a]
            bi = chartoint[b]
            frequencies[ai][bi] = frequencies[ai][bi] + 1
            

We'll have to update the above code to accomodate for this new character.

 -  chars = sorted(set(''.join(words)))
 +  chars = ['.'] + sorted(set(''.join(words)))
            

In analogy to deep learning language models with layers of neurons. You can imagine the frequency table as the weights of the model, and the process of calculating the frequencies as training the model. In fact, the two concepts are practically identical.

=MATCH(search_key, range)

Now we have a table of frequencies, we want to look-up the most likely next token given the previous token in Google Sheets. For this, we'll be using MATCH. MATCH is a function that accepts three parameters. The third parameter is optional and we'll ignore it because we don't need it ^{see more}. The two parameters we are using are the search_key (what to search for) and a range of numbers in ascending order (where to find it). MATCH returns the largest number that is less than or equal to the search_key by iterating through the elements in the given range and stopping as soon as an element is bigger than the search_key. It returns the 1-based index of the element it found.

Here are some examples.

• MATCH(2, A1:E1) = 1
• MATCH(7, A1:E1) = 3
• MATCH(11, A1:E1) = 5
• MATCH(1, A1:E1) = #N/A (No number found that is less than or equal to 1)

Note: Google Sheets is a subset of Excel and doesn't support Excels full breadth of features, but you can still import Excel files into Google Sheets.

RAND() returns a random number from 0..1. We can use MATCH(RAND(), ...) to pick a random element from our table. But, because of the way MATCH samples from our list, the frequencies need to be converted into probabilities, sorted in ascending order, then stored as a cumulative sum. A cumulative sum is a list where each element is the sum of the elements before it.

Here is an example probability table where each element is just as likely to occur, and it's accompanying cumulative sum table.

• A = 0
• B = A
• C = A + B
• D = A + B + C
• E = A + B + C + D

Running MATCH with the cumulative sum table in Google Sheets I get these numbers. Your numbers may vary, but they'll all be sampled from the distribution above.

• MATCH(RAND(), A1:E1) = 4
• MATCH(RAND(), A1:E1) = 2
• MATCH(RAND(), A1:E1) = 2

Tip: In Google Sheets, you can press DELETE on an empty cell to re-roll the random numbers.

Converting to a Cumulative Sum

Earlier we created a tensor of frequencies. Now let's convert those frequencies into a cumulative sum.

First, we want to convert our tensor of frequencies into a tensor of probabilities. To do this, we need to divide each element in a row by the row's sum. I'm using example values for demonstration.

probs = frequencies / frequencies.sum(dim=1, keepdim=True)

Which gives us these probability values.

dim=1 tells pytorch to sum the rows.

As opposed to dim=0 which sums the columns.

sum usually returns a tensor of dimension (N,) where N is the number of rows, but with keepdim=True it returns tensor of dimension (N,1) retaining the same dimension size as the input. This prevents pytorch broadcasting from dividing things the wrong way.

Now recall that MATCH needs each row in our table to be in ascending order. We'll have to sort it.

torch.sort returns the sorted tensor and a table of indices containing the old index of every sorted element. Keep a mental note of the indices table, as it will be useful later when we need to look-up the original position (aka the token number) of an element in the probability table.

probs, indices = torch.sort(probs)

Now we have a sorted probability distribution, we can turn it into a cumulative sum. Naively, we would do something like this.

    cumulprobs = torch.zeros_like(probs)

    for y in range(3):
        for x in range(3):
            cumulprobs[y][x] = probs[y][:x].sum()

But, there's a little mathematical trick with tensors that can do this for us in a more performant and succinct way.

What we're essentially doing is selecting all the elements before the current element and then summing them. We can utilize a function in pytorch to mask out the elements we want to sum. torch.tril is a function that masks the elements in a tensor to form a triangular shape.

torch.tril(torch.ones((5,5)))

We can change the diagonal parameter to shift when the triangle begins.

And if we multiply a trilled tensor with another tensor, it does about what you'd expect.

x = torch.arange(1,6).float()

torch.tril(torch.ones((5,5)),diagonal=-1) * x

Now from here, we could naively think to sum each row to get our cumulative sum, but there's a neat thing that happens when you use matrix multiplication instead of a regular multiply. Matrix multiplication sums the rows and columns automatically. With a bit of fiddling with dimensions using squeeze and unsqueeze, we can mask out the elements we want and sum them in a single operation. The symbol for matrix multiply in pytorch is @

mask = torch.tril(torch.ones((5,5)),diagonal=-1)
(mask @ x.unsqueeze(-1)).squeeze(-1)

Now we can finally bring back the sorted probability distribution from earlier.

And turn it into a cumulative sum.

(mask @ probs.unsqueeze(-1)).squeeze(-1)

And that's how we turn frequencies into a cumulative sum using pytorch! Additionally, there's the torch.cumsum function which automagically does everything for us, but it's fun (and useful) to learn about fancy tensor tricks.

In Google Sheets

So now we can construct a cumulative sum from the frequencies of bigrams in a dataset. We can take that cumulative sum tensor, convert it to CSV, and import it into Google Sheets. Now, let's try sampling from it in Google Sheets.

Here is our cumulative sum table and it's corresponding indices table (remember that? the one we got from torch.sort).

Let's try asking the table what letter comes after A. First we'll pick a random letter from the A row. Google Sheets doesn't have variable assignments but for demonstration let's pretend that it does.

To get the token number from the index, we need to lookup the corresponding cell in the indices table. Since we are selecting from the A row, we want the first row. Since the indices table is 4 columns to the right of the probs table, we want the 4th column to the right of idx.

ADDRESS gets the cell name as a string given the row and column number. INDIRECT takes that string and evalutes it to get its value. Now let's substitute our idx variable to get the function in it's entirety.

Woohoo! We managed to predict one character using our bigram table in Google Sheets! Now we need to chain predictions together. The next letter is dependent on the letter before it.

We hardcoded the function to always select from row 1, the A row. Let's generalize it. First, we'll need to be able to dynamically construct the range selector U1:W1 with any row, not just the second one. We can use INDIRECT alongside a new function CONCATENATE, which concatenates two strings together.

Then we can update our function from earlier to allow it to select from any row.

Then just copy-paste this formula a bunch of times where row refers to the cell before it. And there you have it, inference!

The code explained so far only gets the token number, but you might want to convert that number into a letter with yet another look-up table. But, I'll leave that as an exercise for the reader.

Click here to download the Microsoft Excel project file for the name generator.

Closing Notes

This one took a lot longer to write than I'd hoped. I thought I'd be able to bash this one out in a day but I kept on finding opportunities to divulge more fun facts and I couldn't stop myself! (And because I kept procrastinating writing it) This post definitely could have been one paragraph of text, but that's no fun isn't it. Oh, and, don't look at the CSS, it's horrible. I tried to make it look like a Google site.

Made with love, html, and css. If you have any questions or want to talk, my emails are open. johnnycambodia@gmail.com