# Install the course package
!pip install -q git+https://github.com/BaytAlhikmah/hands-on-llms-for-swes.git#subdirectory=pkg
print('✓ Setup complete!')
Chapter 3: From Theory to Practice — Prediction on Real Data
In Chapter 2, you learned entropy and cross-entropy, the theory behind measuring prediction quality. Now let’s apply those concepts to real prediction problems.
We’ll start small (3×3 Rock-Paper-Scissors) and scale up (28×28 character bigrams), building transition matrices, measuring their entropy, exploiting patterns, and discovering the V² wall that makes neural networks necessary.
Part 0: Setup
—📺 Highly Recommended: This chapter is heavily inspired by Andrej Karpathy’s excellent lecture “The spelled-out intro to language modeling: building makemore”. We strongly encourage watching it alongside this notebook — particularly the bigram model section (first ~45 minutes). The names dataset and pedagogical approach come directly from that resource.—
Part 1: Rock-Paper-Scissors (3×3 Transition Matrix)
Your friend thinks they play Rock-Paper-Scissors randomly. You’ve recorded 1,000 of their moves. Let’s see if that’s true — and if we can exploit their patterns.
Exercise 1: Load RPS Moves
Load the recorded moves and check the overall frequencies.
import csv
import math
import random
import urllib.request
import matplotlib.pyplot as plt
from alhikmah_llms import plot_matrix, TransitionLearner
# Load the recorded moves from GitHub
url = 'https://raw.githubusercontent.com/BaytAlhikmah/hands-on-llms-for-swes/main/chapters/3/rps_opponent_moves.csv'
response = urllib.request.urlopen(url)
lines = response.read().decode('utf-8').strip().split('\n')
moves: list[str] = []
reader = csv.DictReader(lines)
for row in reader:
moves.append(row['move'])
short = {'Rock': 'R', 'Paper': 'P', 'Scissors': 'S'}
moves_short = [short[m] for m in moves]
print(f'Total moves recorded: {len(moves)}')
print(f'First 20: {" ".join(moves_short[:20])}')
print()
# Overall frequencies
for m in ['Rock', 'Paper', 'Scissors']:
count = moves.count(m)
print(f' {m:<10s} {count:>4d} ({count/len(moves)*100:.1f}%)')
print()
print('Looks random...')Exercise 2: Count Transitions and Calculate Entropy
Overall frequencies are roughly equal — each move appears about 33% of the time. But that doesn’t mean the sequence is random.
Predict first: if your friend just played Rock, are they equally likely to play Rock, Paper, or Scissors next? Or is there a pattern?
# Count transitions: how often does move Y follow move X?
rps_labels = ['Rock', 'Paper', 'Scissors']
rps_stoi = {m: i for i, m in enumerate(rps_labels)}
rps_counts: list[list[int]] = [[0] * 3 for _ in range(3)]
for i in range(len(moves) - 1):
prev = rps_stoi[moves[i]]
curr = rps_stoi[moves[i + 1]]
rps_counts[prev][curr] += 1
# Display as bar chart
for i, prev_move in enumerate(rps_labels):
row_total = sum(rps_counts[i])
print(f'After {prev_move}:')
for j, next_move in enumerate(rps_labels):
pct = rps_counts[i][j] / row_total * 100
bar = chr(9608) * int(pct / 2)
print(f' -> {next_move:<10s} {rps_counts[i][j]:>3d} ({pct:5.1f}%) {bar}')
print()
plot_matrix(rps_counts, rps_labels, rps_labels,
title='RPS Transition Counts',
xlabel='Next move', ylabel='Previous move',
figsize=(4, 4))
print('They are NOT random.')Compute row entropy
Now let’s calculate the entropy of each row using the entropy formula from Chapter 2, and compare to uniform randomness:
def row_entropy(probs: list[float]) -> float:
"""Calculate entropy of a probability distribution."""
return -sum(p * math.log2(p) for p in probs if p > 0)
# Normalize counts to get probabilities for each row
print("Entropy by previous move:\n")
for i, prev_move in enumerate(rps_labels):
row_total = sum(rps_counts[i])
probs = [rps_counts[i][j] / row_total for j in range(3)]
h = row_entropy(probs)
print(f" After {prev_move:<10s} {h:.3f} bits")
# Compare to uniform (truly random)
uniform_entropy = row_entropy([1/3, 1/3, 1/3])
print(f"\n Uniform (random): {uniform_entropy:.3f} bits")
print(f"\nLower entropy = more predictable = easier to exploit!")
print(f"The entropy gap represents information you can use to win.")Optional
To better understand how this maps to entropy, refer to the supplemental notebook entropy_from_counts.ipynb
Exercise 3: Exploit the Patterns
The transition matrix reveals clear habits. If we can predict their next move, we play the counter: - They play Rock → we play Paper - They play Paper → we play Scissors - They play Scissors → we play Rock
But first, let’s see what happens if we just guess randomly.
beats = {'Rock': 'Paper', 'Paper': 'Scissors', 'Scissors': 'Rock'}
def play_rps(moves: list[str], strategy) -> tuple[int, int, int]:
"""Play RPS using a strategy function. Returns (wins, losses, draws)."""
wins = losses = draws = 0
for i in range(1, len(moves)):
their_move = moves[i]
our_move = strategy(moves, i)
if our_move == their_move:
draws += 1
elif beats[their_move] == our_move:
wins += 1
else:
losses += 1
return wins, losses, draws
def print_results(label: str, wins: int, losses: int, draws: int) -> None:
total = wins + losses + draws
print(f'{label} over {total} games:')
print(f' Wins: {wins:>4d} ({wins/total*100:.1f}%)')
print(f' Losses: {losses:>4d} ({losses/total*100:.1f}%)')
print(f' Draws: {draws:>4d} ({draws/total*100:.1f}%)')
# Random baseline
random.seed(42)
def random_strategy(moves: list[str], i: int) -> str:
return random.choice(rps_labels)
w, l, d = play_rps(moves, random_strategy)
print_results('Random guessing', w, l, d)
print()
print('No edge. We need a better strategy.')The counting approach
We already have the transition counts. Normalize each row to get probabilities, then predict their most likely next move and play the counter.
# Normalize counts to probabilities
P_rps_counted: list[list[float]] = [[0.0] * 3 for _ in range(3)]
for i in range(3):
row_total = sum(rps_counts[i])
for j in range(3):
P_rps_counted[i][j] = rps_counts[i][j] / row_total
plot_matrix(P_rps_counted, rps_labels, rps_labels,
title='RPS Transition Probabilities (counted)',
xlabel='Next move', ylabel='Previous move',
cmap='Purples', figsize=(4, 4))
def counter_strategy(P: list[list[float]]) -> callable:
"""Return a strategy that predicts from P and plays the counter."""
def strategy(moves: list[str], i: int) -> str:
prev = rps_stoi[moves[i - 1]]
probs = P[prev]
predicted = rps_labels[probs.index(max(probs))]
return beats[predicted]
return strategy
w, l, d = play_rps(moves, counter_strategy(P_rps_counted))
print_results('Counting model', w, l, d)
print(f'\nWin rate jumped from ~33% to {w/(w+l+d)*100:.1f}%.')Exercise 4: Learn the Probabilities Automatically
The counting approach works perfectly. But what if we started with a 3×3 matrix of random numbers and gradually improved them by looking at the data?
We’ll use TransitionLearner — a small helper that:
- Starts from uniform probabilities (knows nothing)
- Looks at the transitions, measures how wrong its guesses are
- Adjusts the numbers to be slightly less wrong
- Repeats
Treat it as a black box for now. The internals come later.
rps_model = TransitionLearner(n=3)
print('Initial probabilities (uniform — the model knows nothing):')
plot_matrix(rps_model.probabilities(), rps_labels, rps_labels,
title='RPS Before Training',
xlabel='Next move', ylabel='Previous move',
cmap='Purples', figsize=(4, 4))# Prepare training data
rps_xs = [rps_stoi[moves[i]] for i in range(len(moves) - 1)]
rps_ys = [rps_stoi[moves[i + 1]] for i in range(len(moves) - 1)]
print(f'Training on {len(rps_xs)} transitions...\n')
rps_model.train(rps_xs, rps_ys, steps=200, print_every=50)
print('\nLearned probabilities:')
plot_matrix(rps_model.probabilities(), rps_labels, rps_labels,
title='RPS After Training (learned)',
xlabel='Next move', ylabel='Previous move',
cmap='Purples', figsize=(4, 4))# Play with the learned model
P_rps_learned = rps_model.probabilities()
w, l, d = play_rps(moves, counter_strategy(P_rps_learned))
print_results('Learned model', w, l, d)
# Compare the two matrices
max_diff = 0.0
for i in range(3):
for j in range(3):
d_val = abs(P_rps_counted[i][j] - P_rps_learned[i][j])
if d_val > max_diff:
max_diff = d_val
print(f'\nMax difference between counted and learned: {max_diff:.4f}')
print('Same answer, different path.')Same answer, different path
Counting works because the problem is tiny: 3 moves, 9 transitions. We can observe every transition hundreds of times and get exact probabilities.
But what if the vocabulary were bigger? What if we couldn’t see every possible transition? That’s where learning pays off.
Part 2: Character Bigrams (28×28 Transition Matrix)
Same idea, bigger problem. Instead of 3 moves, we have 28 characters (a-z plus start and end tokens). Instead of predicting the next RPS move, we predict the next character in a name.
The transition matrix grows from 3×3 to 28×28, but the approach is identical.
Exercise 5: Load Names Dataset
What is a bigram? A bigram is a pair of consecutive characters.
# Load names dataset
url = 'https://raw.githubusercontent.com/karpathy/makemore/master/names.txt'
response = urllib.request.urlopen(url)
names = [n.strip().lower() for n in response.read().decode('utf-8').strip().split('\n') if n.strip()]
# Train/test split (90/10)
random.seed(42)
shuffled = names.copy()
random.shuffle(shuffled)
split = int(0.9 * len(shuffled))
train_names = shuffled[:split]
test_names = shuffled[split:]
print(f'Total names: {len(names):,}')
print(f' Train: {len(train_names):,}')
print(f' Test: {len(test_names):,}')
# Build vocabulary from ALL names (so test names don't have unknown characters)
chars = sorted(set(''.join(names)))
stoi: dict[str, int] = {'<S>': 0, '<E>': 1}
for i, c in enumerate(chars):
stoi[c] = i + 2
itos: dict[int, str] = {i: c for c, i in stoi.items()}
V = len(stoi)
print(f'\nVocab size (V): {V}')
print(f'Tokens: {" ".join(itos[i] for i in range(V))}')What is a bigram?
A bigram is a pair of consecutive characters. The name “emma” produces these bigrams:
<S> -> e (start of name -> 'e')
e -> m
m -> m
m -> a
a -> <E> ('a' -> end of name)The <S> and <E> tokens mark where names begin and end. Without them, the model wouldn’t know which characters tend to start or end names.
for name in ['emma', 'olivia', 'ava']:
chs = ['<S>'] + list(name) + ['<E>']
print(f"'{name}' -> {len(chs)-1} bigrams:")
for i in range(len(chs) - 1):
print(f" '{chs[i]}' -> '{chs[i+1]}'")
print()Exercise 6: Build 28×28 Count Matrix
Same as RPS: build a V × V count matrix where entry [i][j] = how many times character j follows character i.
# Build the count matrix (from training data only)
bg_counts: list[list[int]] = [[0] * V for _ in range(V)]
for name in train_names:
chs = ['<S>'] + list(name) + ['<E>']
for i in range(len(chs) - 1):
ix1 = stoi[chs[i]]
ix2 = stoi[chs[i + 1]]
bg_counts[ix1][ix2] += 1
total_bigrams = sum(sum(row) for row in bg_counts)
nonzero = sum(1 for i in range(V) for j in range(V) if bg_counts[i][j] > 0)
print(f'Total bigram occurrences (train): {total_bigrams:,}')
print(f'Non-zero entries: {nonzero} / {V*V} ({nonzero/(V*V)*100:.1f}%)')
# What follows 'm'?
m_id = stoi['m']
m_row = [(itos[j], bg_counts[m_id][j]) for j in range(V) if bg_counts[m_id][j] > 0]
m_row.sort(key=lambda x: -x[1])
print(f'\nAfter \'m\':')
for ch, cnt in m_row[:10]:
print(f' m -> {repr(ch):<5s} {cnt:>5,d} times')# Normalize to probabilities
P_bg_counted: list[list[float]] = [[0.0] * V for _ in range(V)]
for i in range(V):
row_total = sum(bg_counts[i])
if row_total > 0:
for j in range(V):
P_bg_counted[i][j] = bg_counts[i][j] / row_total
# Show P(next | 'm') top 10
print("P(next | 'm') -- top 10:")
m_probs = [(itos[j], P_bg_counted[m_id][j]) for j in range(V) if P_bg_counted[m_id][j] > 0]
m_probs.sort(key=lambda x: -x[1])
for ch, p in m_probs[:10]:
print(f" P('{ch}' | 'm') = {p:.4f}")
print(f'\nRow sum: {sum(P_bg_counted[m_id]):.6f} (should be 1.0)')bg_labels = [itos[i] for i in range(V)]
plot_matrix(bg_counts, bg_labels, bg_labels,
title='Bigram Counts',
xlabel='Next character', ylabel='Current character')
plot_matrix(P_bg_counted, bg_labels, bg_labels,
title='Bigram Probabilities — P(next | current)',
xlabel='Next character', ylabel='Current character',
cmap='Purples')Exercise 7: Generate Names
To generate a name: 1. Start with <S> 2. Sample the next character from P(next | current) 3. Repeat until we sample <E>
Predict first: will these names look real?
def generate_name(P: list[list[float]], stoi: dict[str, int],
itos: dict[int, str], max_len: int = 20) -> str:
"""Sample a name from a bigram probability matrix."""
current = stoi['<S>']
end = stoi['<E>']
result: list[str] = []
for _ in range(max_len):
row = P[current]
r = random.random()
cumulative = 0.0
for j in range(len(row)):
cumulative += row[j]
if cumulative >= r:
if j == end:
return ''.join(result)
result.append(itos[j])
current = j
break
return ''.join(result)
random.seed(42)
print('Generated names (counting bigram):')
for i in range(20):
name = generate_name(P_bg_counted, stoi, itos)
print(f' {i+1:>2d}. {name}')Exercise 8: Learn Bigrams with TransitionLearner
Same as RPS: use TransitionLearner to learn the 28×28 probability matrix from scratch via a learning algorithm.
# Prepare training data: every bigram as (input_id, target_id)
bg_xs: list[int] = []
bg_ys: list[int] = []
for name in train_names:
chs = ['<S>'] + list(name) + ['<E>']
for i in range(len(chs) - 1):
bg_xs.append(stoi[chs[i]])
bg_ys.append(stoi[chs[i + 1]])
print(f'Training pairs: {len(bg_xs):,}')
bg_model = TransitionLearner(n=V)
bg_model.train(bg_xs, bg_ys, steps=200, print_every=50)# Compare learned vs counted
P_bg_learned = bg_model.probabilities()
max_diff = 0.0
for i in range(V):
for j in range(V):
d_val = abs(P_bg_counted[i][j] - P_bg_learned[i][j])
if d_val > max_diff:
max_diff = d_val
print(f'Max absolute difference: {max_diff:.6f}')
# Side-by-side for 'm' row
print(f"\nP(next | 'm') -- top 10:")
print(f" {'char':>6s} {'counted':>10s} {'learned':>10s} {'diff':>10s}")
print(f' {"-" * 42}')
c_row = P_bg_counted[m_id]
l_row = P_bg_learned[m_id]
indices = sorted(range(V), key=lambda j: -c_row[j])[:10]
for idx in indices:
ch = itos[idx]
pc = c_row[idx]
pl = l_row[idx]
print(f' {repr(ch):>6s} {pc:>10.4f} {pl:>10.4f} {abs(pc - pl):>10.6f}')Exercise 9: Generate from Learned Model
Predict first: will these names look different from the counting model’s names?
# Generate names from the learned model
random.seed(42)
print('Generated names (learned bigram):')
for i in range(20):
name = generate_name(P_bg_learned, stoi, itos)
print(f' {i+1:>2d}. {name}')Exercise 10: The V² Wall
Our bigram model is a V × V matrix. With V = 28 characters, that’s 784 entries. Tiny.
But what if we used words instead of characters?
examples = [
('Characters (this notebook)', V),
('GPT-2 BPE tokens', 50_257),
('English words (typical)', 100_000),
('Llama 3 tokens', 128_256),
('Arabic words (news corpus)', 300_000),
]
print(f'{"Vocabulary":<30s} {"V":>10s} {"V^2":>15s} {"Memory":>10s}')
print('-' * 70)
for label, v in examples:
v_sq = v * v
mem = v_sq * 4 # float32 bytes
if mem < 1e6:
mem_str = f'{mem/1024:.0f} KB'
elif mem < 1e9:
mem_str = f'{mem/1e6:.0f} MB'
elif mem < 1e12:
mem_str = f'{mem/1e9:.0f} GB'
else:
mem_str = f'{mem/1e12:.0f} TB'
print(f'{label:<30s} {v:>10,d} {v_sq:>15,d} {mem_str:>10s}')