LMs | Algorithms

Bag-of-Words counts

Key idea: represent a document as a vector of word counts over a fixed vocabulary. Order is discarded.

Build a bag-of-words vector

function bow_vectorise(docs):
    vocab = sorted(unique_words(docs))   
    vectors = []
    for doc in docs:
        v = [0] * len(vocab)
        for word in tokenise(doc):
            v[ vocab.index(word) ] += 1     # count occurrences
        vectors.append(v)
    return vocab, vectors

# similarity between two docs = cosine of their count vectors
sim(a, b) = dot(a, b) / ( ||a|| * ||b|| )

Try it — vectorise & compare two documents

Edit either document. The shared vocabulary forms the columns; each doc becomes a row of counts. Cosine similarity measures overlap. Note that it ignores order entirely.

Interactive · Bag-of-Words

Doc A

Doc B

Count vectors

CapturesWord frequency

IgnoresOrder, meaning

Used forClassification, search, TF-IDF

N-grams counts + order

Key idea: predict the next word depending only on the previous n−1 words. Estimate the next-word probability by counting.

Train an n-gram model by counting

function train_ngram(corpus, n):
    # Example corpus (n = 3):
    #   I love NLP
    #   I love pizza
    #   I love NLP
    # counts = {
    #   ("I","love"): {
    #       "NLP": 2,
    #       "pizza": 1
    #   }
    # }
    counts = {}   # (context) -> {next_word: count}
    for sentence in corpus:
        toks = tokenise(sentence)
        for i in 0 .. len(toks) - n:
            context = toks[i : i+n-1]
            next    = toks[i+n-1]
            counts[context][next] += 1
    return counts

# prediction (with simple back-off if context unseen)
P(next | context) = counts[context][next] / sum(counts[context]) # P("NLP" | "I love") = 2/3

Try it — slide the window & count

Pick a window size, then Step to slide the n-gram window across the sentence, accumulating counts. Those counts are the model parameters.

Interactive · N-gram counter

Sentence

Sentence & sliding window

Counts so far (top 10)

ContextPrevious n−1 words

WeaknessSparse & huge n-gram tables for large n

Word2Vec embeddings

Key idea: "a word is known by the company it keeps." Each word's vector is trained/learned by predicting the words around it, and words used in similar contexts end up with similar vectors.

Skip-gram training data + objective

function function train_skipgram(sentence, window):
  # Example sentence (window = 1):
  # I love [NLP] very much
  #         ↑ center word
  # Training pairs:
  # (NLP, love)
  # (NLP, very)
  for center_i in sentence:
      for j in [center_i - W .. center_i + W], j != center_i:
          # Slide a window; and produce (center, context) pairs
          produce_training_pairs( center=word[center_i], context=word[j] ) 

  # Learn vectors so the center predicts its context words
  maximise  P(context | center) = softmax( v_context · v_center ) # P("love" | "NLP")
  # Gradient descent pushes the vectors of ("NLP", "love") and ("NLP", "very") closer together.

Try it — generate skip-gram pairs

Step through each center word; sliding the window produces a training pair with every neighbour.

Interactive · Skip-gram pairs

Sentence

Sentence (center + context)

(center → context) pairs

Explore the learned space

Once trained, vectors group by meaning. Click a word to see its nearest neighbours by cosine similarity (word vectors are toy 2D embeddings).

Interactive · Embedding map

2D embedding space

Nearest neighbours (cosine)

OutputOne dense vector per word

LimitOne vector per word regardless of context

Transformer attention

Key idea: each word learns its vector by weighting all other words in the sentence; more relevant words receive greater attention weights.

Scaled dot-product self-attention

function function self-attention(X):
  # X is the matrix of input token embeddings
  # embedding dimension (d = 4) - random initialisation 
          ┌────────────────────────────┐
  X =     │ I     0.2  0.8  0.1  0.5   │
          │ love  0.7  0.3  0.9  0.2   │
          │ NLP   0.6  0.5  0.4  0.8   │
          └────────────────────────────┘        
  # Each token is projected into Query, Key, Value vectors        
  Q = X · W_q,   K = X · W_k,   V = X · W_v 
  # How relevant each query is to each key?
  # Example: "love" as the center token
  # q_love · k_I
  # q_love · k_love
  # q_love · k_NLP
  # A larger dot product means that the other token is more relevant to "love". 
  scores   = (Q · Kᵀ) / sqrt(d)
  # Convert the scores into attention weights.
  # Example:
  # attention("love") = [0.20, 0.30, 0.50]
  #                     I     love   NLP    
  weights  = softmax(scores, axis = keys) 
  # Update input token embeddings
  # X("love") = 0.20 · v_I + 0.30 · v_love + 0.50 · v_NLP
  X   = weights · V               
  return X
  # done for all tokens at once → fully parallel

Try it — the attention matrix

Step goes to one query (a center token) at a time. It uses scaled dot-products to compute how important the other words are to the center word. Brighter cells = more important/relevant.

Interactive · Self-attention

Tokens

Attention weights (rows = query, cols = key, %)

ContextEvery token, all at once

StrengthContext-aware, long-range

Used byGPT, BERT, T5, Llama …

Language Model Algorithms

Jump to

Bag-of-Words counts

N-grams counts + order

Word2Vec embeddings

Transformer attention