Learnings
A map of what Henry Hsu is learning, from data systems to reinforcement learning, each page taught with interactive figures you can play with.
Algorithms
Most problems solved with code reuse a small number of ideas: take the choice that looks best and never look back, split the problem and combine the halves, remember answers already worked out. This field gives each idea its own pages, written to show how it works, when to reach for it, and how to tell it is right.
It starts with Greedy; more patterns join as they are written.
Bandits
A bandit is the simplest setting where exploring matters: the same few options, again and again, and all you learn is what each choice paid. Nothing you do changes the situation, so every idea about balancing curiosity and greed shows up cleanly here before it has to share the stage with states and time.
When the world changes keeps estimates current. Optimism explores and The benefit of the doubt explore on purpose instead of at random, and Counting what you missed scores how well an explorer does. Preferences, not values learns what to favour rather than what each option is worth, and Reading the situation adds a clue about which situation you are in, the bridge to the full problem.
Read Explore or exploit first.
- Reading the situation
When a clue tells you which situation you are in, learn a rule from situation to choice.
- Preferences, not values
Learn how much to favour each option, and compare every reward with what you usually get.
- Optimism explores
Expect the best of everything untried, and even a learner that never gambles tries it all.
- Counting what you missed
Regret in multi-armed bandits: what not knowing the best arm costs, why a fixed share of exploring pays forever, and how to explore less as you learn.
- When the world changes
A plain average never forgets; a fixed step trusts recent rewards more, and keeps up when things change.
- The benefit of the doubt
Pick by how good an option looks plus how unsure you still are about it.
Learning to act
Without the rules of the world you can still learn to act well: try moves, see what follows, and update the worth of each move as you go, while still exploring. This is where reinforcement learning stops planning and starts learning from experience, and these methods are the workhorses of the field.
Average, switch, and keep trying learns from whole episodes, and shows why every move must stay in play. Learning from someone else’s trips judges one way of acting from episodes of another. Learning the way by walking it (Sarsa) learns after every step from the moves you make; Learning the best while still exploring (Q-learning) learns the best moves while behaving otherwise. The lucky favourite explains why Q-learning overrates moves, and the simple fix. Where your move leaves you scores the position a move lands in rather than the move itself, so moves that end up in the same place learn together.
Read Play it out, then average and Two pulls, one answer first, and Temporal-difference learning before Sarsa.
- Where your move leaves you
Afterstates score the situation your move leaves you in, not every state–action pair, so every way of reaching it shares one value and learns faster.
- Learning from someone else’s trips
Off-policy evaluation with importance sampling: weight each return by how much likelier your policy makes its moves. Ordinary is unbiased; weighted is steadier.
- The lucky favourite
Maximization bias: the best of several noisy estimates is overrated, so Q-learning's max overestimates, and Double Q-learning splits picking from scoring.
- Average, switch, and keep trying
Monte Carlo control learns to act from whole episodes: average each move's return, switch to the best, and keep exploring with exploring starts or ε-greedy.
- Learning the best while still exploring
Q-learning backs up the best next move instead of the one taken, so it learns optimal values while still exploring (off-policy TD control).
- Learning the way by walking it
Sarsa, on-policy TD control: nudge each state–action value toward the reward plus the value of the move you take next, while choosing moves by those values.
Data systems
Most applications today are limited less by computing power than by data: how much there is, how fast it changes and how quickly it has to be served. This field follows Designing Data-Intensive Applications through the three things such a system has to get right.
Data systems are built from parts sets the scene: a database, a cache and an index joined together, with keeping them in step left to you. Reliability is about working when things go wrong, Scalability about staying fast as load grows, and Maintainability about keeping the system easy to run, understand and change.
This field treats the database as one part among several. Inside a database opens it up: how it stores rows, finds them, plans a query and survives a crash.
- Data systems are built from parts
Combine a database, a cache and an index, and keeping them in step is your job.
- Maintainability
Easy to run, easy to understand, easy to change.
Deep RL
A table with one entry per state works for a board of thirty squares, not for a screen of pixels or the angles of a robot's joints. Deep RL replaces the table with a neural network that carries what it learned about states it has seen over to ones it has not. That is what let these methods play Atari from the screen, and it is also where learning becomes unstable.
Deep Q-networks shows why a network chasing its own guesses runs away, and the two fixes that steady it. Continuous actions handles actions that can be any number, like a dial or a torque, by training a second network to choose them; it comes last, after the policy gradient pages.
Read Learning the best while still exploring first.
- Continuous actions
DDPG (deep deterministic policy gradient) handles continuous actions: an actor climbs the critic's slope to the best action, with noise to explore nearby.
- Deep Q-networks
Deep Q-networks (DQN) replace Q-learning's table with a neural network, steadied by experience replay and a frozen target network.
Fitting a model
Fitting a model means choosing its weights so its predictions match the examples. This topic does it with the simplest model, a straight line, because every idea here carries over to the bigger models later on the map.
Least squares picks the line whose squared misses add up to the least, and solves for it directly. Ridge regression steadies the weights when two features nearly copy each other. Bias and variance explains why a more flexible model can predict new cases worse. Convexity says when the lowest point you walk to is the lowest there is, and Gradient descent walks there when no formula will, and shows how long each step can be.
Nothing comes first: this is the way in.
- Bias-variance tradeoff: why flexible models overfit
See why test error splits into bias², variance and noise, and why it is U-shaped as model complexity grows: the bias-variance tradeoff.
- Convexity: why a convex loss has no bad minima
What makes a loss convex, why every local minimum of a convex function is global, and how to check with the second derivative (Hessian ⪰ 0).
- Gradient descent: step size and convergence
How gradient descent steps against the gradient, why the step size (learning rate) must stay under 2/L, and how the condition number sets its pace.
- Least squares regression: fitting a line
How ordinary least squares (OLS) fits a line: minimise the sum of squared errors, solve the normal equations XᵀXw = Xᵀy, and see the fit as a projection.
- Ridge regression: steadying collinear features
Why near-duplicate features make least-squares weights swing, and how ridge regression (L2 regularization) adds λ to XᵀX's eigenvalues to steady them.
Generating images
Recognising a picture means mapping it to a label. Generating one runs the other way, from random numbers to a new image, and there is no simple loss for "looks real". This topic follows the three answers that took over in turn.
GANs train a generator against a discriminator that learns what real looks like, and show why that game stalls and collapses onto a few kinds of picture. Variational autoencoders squeeze each picture into a small code and fill the code space so any random code decodes to something. Diffusion models learn to remove a little noise at a time and build a picture from pure static. Classifier-free guidance makes them follow a prompt harder, and latent diffusion runs the whole process in a small compressed space: Stable Diffusion.
Learning to see and Labelling every pixel come first; CLIP helps with the last page.
- Classifier-free guidance (CFG) for diffusion models
How classifier-free guidance (CFG) makes diffusion models follow a prompt: drop it in training, then step past the prompted noise guess by a guidance scale w.
- Diffusion models (DDPM): from noise to images
How denoising diffusion probabilistic models (DDPM) add noise step by step, learn to predict it with a simple MSE loss, and generate by denoising.
- GANs: generative adversarial networks explained
How generative adversarial networks (GANs) train a generator against a discriminator, why the generator's gradient vanishes, and what mode collapse is.
- Latent diffusion: how Stable Diffusion works
How latent diffusion (Stable Diffusion) runs denoising in an autoencoder's small latent: 48× fewer numbers per step, decoded to a full image once.
- Variational autoencoders (VAE): latent space without holes
How a variational autoencoder (VAE) fills an autoencoder's latent holes: encode to a Gaussian, the reparameterization trick, and the KL penalty.
Greedy
A greedy algorithm builds its answer one choice at a time, always taking what looks best right now and never undoing it. When it works it is the simplest and fastest method there is. When it fails it fails quietly, with an answer that looks fine and is not, so the real skill is telling the two apart.
Finish first shows both sides on one problem, booking the most meetings into one room: three natural rules that lose, the one that never does, and how to prove it.
Nothing comes first.
- Finish first
The greedy choice for interval scheduling: book the meeting that ends first to fit the most, why other greedy rules fail, and the stays-ahead proof.
Images meet text
Transformers read tokens. This topic turns pictures into tokens too, so one model can work with images and words together.
The Vision Transformer cuts an image into patches and feeds each one to a standard Transformer, and shows why it needs far more data than a convolutional network to catch up. CLIP trains an image encoder and a text encoder side by side so that a picture and its caption land close together, which lets it sort photos into classes it was never shown just by writing their names. Vision-language models hand a frozen image encoder's patch tokens to a language model through a small projector, and the last section shows why the number of visual tokens decides what small print it can read.
Learning to see and Transformers, from Natural language processing, come first.
- CLIP: contrastive image–text pretraining
How CLIP (Contrastive Language-Image Pre-training) learns from captions alone: the similarity matrix, contrastive loss, temperature and zero-shot prompts.
- Vision-language models: how LLaVA sees images
How vision-language models (VLMs) like LLaVA turn image patches into visual tokens for a language model, and why Qwen2-VL's token count follows image size.
- Vision Transformer (ViT): images as 16×16 patches
How the Vision Transformer (ViT) cuts an image into patches, turns each into a token with a [class] token, and why it needs far more data than a CNN.
Indexes
An index lets a database find a few rows without reading the whole table. Every index is a trade: pages spent keeping it, work on every insert, and a promise of fewer disk trips per lookup. This topic is about how the two common kinds keep that promise as a table grows, and when they break it.
Linear hashing grows a hash file one bucket at a time, without ever stopping to rebuild. B+-trees keeps a sorted index so shallow that any one of a billion rows is four page reads away, and range searches walk sideways. The index that points everywhere shows when following an index loses to simply reading the table.
Read Getting there costs more than reading first.
- B+-trees: why an index lookup takes four reads
How a B+-tree index stays shallow: fanout from big disk pages gives log-base-500 height, leaf splits keep it balanced, linked leaves serve range scans.
- Clustered vs unclustered index: when a scan wins
Clustered vs unclustered (secondary) indexes: why an index that pays a random read per row loses to a full table scan past a tiny selectivity.
- Linear hashing: growing a hash index one bucket at a time
How linear hashing grows a disk hash table one bucket at a time, splitting at a pointer instead of the full bucket, versus static and extendible hashing.
Inside a database
Inside a database follows a query down to the disk and back: how a database stores rows, finds them quickly, turns a question in SQL into a plan, and keeps its data whole through crashes and crowds. It is the machinery under every system in Data systems, seen from the inside.
Storage sets the cost that drives everything else: a trip to the disk is slow, so pages are big and memory is precious. Indexes find rows without reading whole tables. Relational queries says what a query means. Query optimization turns it into the cheapest of many equal plans. Transactions keeps the data whole when the power fails or two users change the same row.
Nothing comes first: Storage is the way in.
Labelling every pixel
A photo classifier names one thing and throws away where it is. Dense prediction keeps the where: it gives every pixel its own label, which is how a network cuts out a person, a road or a tumour.
Semantic segmentation rewrites a classifier's last layers as convolutions so it slides over any image, then grows its coarse map back to full size with transposed convolutions, and widens its view with dilated ones. The U-Net adds the piece that gets edges back: an encoder that shrinks to see what is there, a decoder that grows back, and skip connections that copy the fine detail across. The U-Net returns later as the denoiser inside diffusion models.
Learning to see comes first.
- Semantic segmentation: a label for every pixel
How semantic segmentation labels every pixel: fully convolutional networks (FCN), transposed convolutions, checkerboards, and dilated convolutions.
- U-Net: skip connections for image segmentation
How the U-Net segments images: an encoder shrinks to see what is there, a decoder grows back, and skip connections copy fine detail across.
Large language models
Take the pretrained Transformer and make it far bigger, and something changes: the same model, never retrained, can do new tasks from a few lines of instructions. This topic is about what scale buys and how to use it.
Scaling laws say how loss falls as parameters, data and compute grow, and how to split a fixed budget between a bigger model and more text. In-context learning shows a frozen model picking up a task from examples in its prompt. Calibrate before use shows why those examples' order and labels can swing the answer, and how a blank input measures the lean so it can be divided out.
Chain of thought closes the field: letting the model write its steps before it answers, and voting over several sampled chains, solves problems a direct answer gets wrong.
- Calibrate before use: contextual calibration for LLMs
Why few-shot accuracy swings with example order (majority label and recency bias), and how contextual calibration with an "N/A" input divides the lean out.
- Chain-of-thought prompting and self-consistency
Why letting an LLM write its steps first (chain-of-thought prompting) solves more word problems, and how voting over sampled chains (self-consistency) helps.
- In-context learning: zero-shot and few-shot prompting
How in-context learning (ICL) lets a frozen language model do a new task from a few examples in its prompt, with patterns, verbalizers and no weight updates.
- Scaling laws: compute-optimal LLMs (Chinchilla)
Why LLM loss falls as a power law in parameters and tokens, C ≈ 6ND, and the Chinchilla compute-optimal rule of about 20 tokens per parameter.
Learning to see
A colour photo is hundreds of thousands of numbers, and the thing in it can sit anywhere. This topic is how networks cope with that, and how they are trained once they get deep.
Image convolution slides a small grid of weights over the pixels: averaging blurs, differencing finds edges. Convolutional networks learn those filters instead of hand-making them, share them across the whole image, pool, and stack layers from LeNet to AlexNet and VGG. The last three pages are about training deep networks: momentum steadies the steps of gradient descent, dropout switches units off at random so none can lean on another, and batch normalization evens out each layer's numbers over the batch.
Nothing comes first; neural networks and gradient descent help.
- Batch normalization: why networks normalize each batch
How batch normalization (BatchNorm) evens out each channel over a mini-batch, what the learned γ and β do, and why it uses running averages at test time.
- Convolutional neural networks (CNNs): filters, pooling
How convolutional neural networks (CNNs) learn small filters shared across an image, count their weights, pool, and stack layers, from LeNet to AlexNet and VGG.
- Dropout: why switching off neurons prevents overfitting
How dropout regularizes neural networks: random units are zeroed in training, kept units scaled by 1/(1−p), so the net acts like an average of thinned networks.
- Image convolution: filters, blur and edge detection
How image convolution slides a small filter over a grid of pixels: box and Gaussian blur, padding and output size, and Sobel edge detection.
- Momentum in SGD: why β = 0.9 speeds up training
How SGD with momentum keeps a running velocity of gradients, cancelling zigzags and mini-batch noise while speeding along steady directions.
Linear classifiers
A classifier answers a yes-or-no question about each example: spam or not, flu or not. The simplest draw a straight boundary through the space of features and call one side yes. This topic is about where to put that line, how sure to be near it, and how a straight line can still make a curved boundary.
Logistic regression gives a chance instead of a verdict and fits it by log loss. The perceptron learns only from its mistakes and stops within a known number when a line exists. Maximum margin picks the line with the widest empty street, decided by the few points on its edges. Soft margins lets some points break the rule for a price. The kernel trick bends the boundary by comparing points instead of building new features.
Read Least squares and Gradient descent first.
- Kernel trick: curved boundaries from inner products
How the kernel trick lets SVMs and other linear methods learn curved boundaries: feature maps, the representer theorem and the Gaussian (RBF) kernel.
- Logistic regression: sigmoid and log loss
How logistic regression turns a linear score into a probability with the sigmoid, and fits it by maximum likelihood: minimising log loss (cross-entropy).
- Maximum margin: the hard-margin SVM's widest street
How a hard-margin support vector machine (SVM) picks the separating line with the widest margin, 2/‖w‖, and why only its support vectors decide it.
- The perceptron: mistake-driven learning and its bound
How the perceptron learns a linear classifier from its mistakes alone, and why on separable data it stops within (R/γ)² mistakes.
- Soft-margin SVM: slack, hinge loss and C
How a soft-margin support vector machine (SVM) lets points sit inside or across the street for a price: slack, the hinge loss, and the C trade-off.
Machine learning
Machine learning turns examples into a model that makes predictions about cases it has not seen. Nearly every method on this map comes down to the same moves: choose a shape for the model, measure how wrong it is on the examples, and adjust it to be less wrong, without fitting the examples so closely that new cases suffer.
Fitting a model covers those moves on the simplest model there is, a straight line. Linear classifiers use a straight boundary to answer yes-or-no questions, from logistic regression to support vector machines and the kernel trick that lets the boundary curve. Trees and ensembles ask one question at a time and then average many trees to steady them. Unsupervised learning drops the answers altogether and finds structure in the data itself: groups, the few directions that matter, and the blanks in a table.
Nothing comes first: Fitting a model is the way in.
Markov decision processes
Once your choices change what happens next, a score per option is not enough: you need states, actions, rewards and the chances that link one step to the next. A Markov decision process writes the whole problem down that way, and every method after this point is a way to solve one.
Now is enough says what a state has to hold. Reward what you want and Sooner is worth more set the goal: what to reward, and how much a later reward counts. A square is worth its neighbours turns values into an equation, and The best from here says what the best behaviour looks like in those terms.
Read Reward versus value first.
- A square is worth its neighbours
A state is worth the average of reward plus the discounted worth of where you land: the Bellman equation.
- Reward what you want
An agent chases exactly the reward it is given: reward the outcome, never the steps you expect.
- Sooner is worth more
Count each reward further off for less, and even a task that never ends has a finite return.
- Now is enough
A good state keeps whatever about the past still matters, so what happens next depends on now alone.
- The best from here
The best values take the best move instead of the average, and with them one step ahead is all the planning you need.
Natural language processing
Natural language processing teaches computers to read and write human language. This field follows Rice's COMP 584 from counting words to the large language models behind today's chatbots, and each step answers a problem the one before left open.
Words as numbers turns text into vectors a model can use, from word counts to embeddings that know which words mean alike. Predicting the next word gives sentences probabilities, first by counting and then with recurrent networks. Translation and generation turns one sentence into another and writes new text, with attention letting the writer look back. Transformers drop recurrence for self-attention and learn from raw text before any task. Large language models are what happens when that is scaled up: prompting, its pitfalls, and chains of thought. Post-training, from COMP 646, turns such a model into an assistant: cheap fine-tuning, instruction tuning, learning from preferences, and rewards a program can check.
Nothing comes first: Bag of words is the way in. Logistic regression, from Machine learning, helps.
Planning
If you know the rules of the world, its chances and its rewards, you can work out the best behaviour without taking a single real step. That is planning, also called dynamic programming. Real problems rarely hand you the rules, but the learning methods that follow copy the moves made here, only from experience instead of from the rules.
Judging a way of playing finds what a fixed behaviour is worth by sweeping the Bellman equation until nothing changes. Better, then best alternates judging and improving until it lands on the best. Improve as you go folds the two into one sweep. Skip the sweep backs up only the states your play reaches, for worlds too big to sweep. Two pulls, one answer shows the pattern under all of them, which every learning method after it shares.
Read A square is worth its neighbours and The best from here first.
- Skip the sweep
Asynchronous dynamic programming backs up one state at a time in any order; values still settle, so you can back up only the states play reaches.
- Two pulls, one answer
Generalized policy iteration: evaluation pulls values toward the policy, improvement pulls the policy toward the values, and both meet at the best policy.
- Judging a way of playing
Iterative policy evaluation: a state is worth one step's reward plus the average worth of where you land (the Bellman equation), swept until values settle.
- Better, then best
Policy iteration alternates judging a policy and switching every state to its best-looking move; each round is never worse, and it reaches the optimal policy.
- Improve as you go
Value iteration gives every state the value of its best move, sweeps until the values stop changing, then reads off the optimal policy once.
Policy gradients
Every method before this learns how good things are, then acts on it. Policy gradients learn the behaviour directly: preferences for each move, nudged toward whatever turned out better than usual. That suits actions with no easy maximum to take, keeps some randomness in the behaviour for free, and is the family that PPO, the method used to fine-tune many language models, belongs to.
Learning the policy itself (REINFORCE) makes each move more likely in proportion to the return that followed it. A critic at every step replaces that return with a learned judgement right after each move, which learns faster and with less noise. A centre and a spread takes the same push to actions that can be any amount: the policy becomes a bell curve, and how widely it keeps trying is learned along with where it aims. Stay close to the notes is PPO: it reuses each batch for many updates, and clips each move's push so the policy has no reason to drift far from the one that collected it.
Preferences, not values is the same idea without states; read it first, with Play it out, then average.
- A critic at every step
Actor-critic methods judge each move as it is made with a learned critic and its TD error, instead of waiting for the return: less luck, some bias.
- A centre and a spread
Gaussian policies for continuous actions: draw each action from a bell curve and let the policy gradient move its centre and learn how widely to explore.
- Stay close to the notes
PPO (proximal policy optimization) reuses one batch for many updates by clipping the probability ratio at 1 ± ε, keeping the policy close to the old one.
- Learning the policy itself
REINFORCE, the Monte Carlo policy gradient: make each move more likely in proportion to how much better than usual its return was, with a baseline to cut noise.
Post-training
A pretrained language model has read much of the web, but it continues text rather than answering it. Post-training is everything done after that first long run to turn it into an assistant you can ask things of, and it costs a sliver of the pretraining compute.
LoRA comes first because it makes the rest affordable: freeze the model and learn a small low-rank change to its weights. Instruction tuning then shows the model worked answers to instructions, scoring only the answers. Preferences go further than imitation: DPO learns from pairs where people picked the better reply, reaching what RLHF's reward model and RL loop reach with one plain loss. RLVR closes the topic: for maths and code a program can check the answer, and GRPO pushes each sampled answer by how far it beats its own group.
Large language models comes first; PPO and REINFORCE, from Reinforcement learning, help with the last two pages.
- DPO vs RLHF: learning from human preferences
How Direct Preference Optimization (DPO) trains a model on human preference pairs with one loss, reaching RLHF's result with no reward model or RL loop.
- Instruction tuning (SFT): teaching a model to answer
Instruction tuning, or supervised fine-tuning (SFT), trains a pretrained model on instruction–response pairs, scoring only the response tokens.
- LoRA: low-rank fine-tuning for large language models
How Low-Rank Adaptation (LoRA) fine-tunes a large language model by freezing its weights and training a small rank-r change BA, merged in at the end.
- RLVR and GRPO: rewards you can check
How reinforcement learning with verifiable rewards (RLVR) trains reasoning models, and how GRPO scores each answer against its own group's mean.
Predicting the next word
A language model gives every sentence a probability, one next word at a time. That single skill sits under spelling correction, speech recognition, translation and today's chatbots.
N-gram models count which word follows which, and smoothing keeps one unseen pair from making a whole sentence impossible. Perplexity turns a model's chances on held-out text into one number to compare models by.
Recurrent networks replace the counts with a small memory carried word to word, and show why that memory fades. LSTMs add gates, so a word can still count twenty words later.
- LSTM: long short-term memory and its gates
How long short-term memory (LSTM) networks use a cell state and forget, input and output gates to carry words, and gradients, across long sentences.
- N-gram language models: predicting the next word
How n-gram language models give a sentence a probability: the chain rule, the Markov assumption, counting bigrams, and why tables explode with n.
- Perplexity: how language models are scored
Perplexity scores a language model by the per-word chance it gives held-out text, read as how many words it is choosing between at each step.
- Recurrent neural networks (RNNs) and vanishing gradients
How a recurrent neural network (RNN) language model reads any length with shared weights, trains by backpropagation through time, and why gradients vanish.
- Smoothing: add-one and add-k for n-gram language models
Why one unseen word pair gives a sentence zero probability, and how add-one (Laplace) and add-k smoothing and the UNK token fix it.
Query optimization
The same SQL query can be run by many plans that give the same answer, and the cheapest can be millions of times faster than the first one written down. This topic is about how an optimizer finds it without running them all.
Predicate pushdown rewrites the plan so filters run before joins, without changing the answer. Estimating result sizes guesses how many rows each step will make, from two numbers per table. Join order uses those guesses to pick which tables to join first, solving each set of tables once. Join algorithms picks how each join runs, from how big the tables are and how much memory there is.
Read Relational algebra first.
- Join algorithms: nested loop, hash join, sort-merge
How block nested loop, hash, Grace hash and sort-merge joins differ in page I/Os, and why memory M decides which one wins: once, 3 trips, or up to M² pages.
- Join order optimization: dynamic programming over subsets
Why join order changes query cost by orders of magnitude, and how optimizers find the best order with dynamic programming over subsets (System R).
- Predicate pushdown: filter before you join
Predicate pushdown in a query optimizer: split the WHERE into CNF clauses and push selections and projections below joins without changing the answer.
- Size estimation: how optimizers guess row counts
How query optimizers estimate result sizes (cardinality estimation) from T(R) and V(R,a): selectivity, the join-size formula, and when independence fails.
Reinforcement learning
Reinforcement learning is learning what to do when nobody gives you the right answer, only a score after you act. The same idea runs a program that plays games, a robot arm learning to grasp, and a recommender that adjusts to what people click.
The topics go in the order the ideas build. The problem says what an agent is up against. Bandits strips it down to repeated choices, Values and Markov decision processes add a world that changes with what you do. Planning solves that world when its rules are known, Learning to act when they are not, Deep RL when there are too many states for a table, and Policy gradients learns the behaviour itself instead of its values.
Averages and a little probability are enough to start; each page brings the rest.
Relational queries
You tell a database what you want, never how to find it. This topic is about what such a question means: rows with no pointers between them, a handful of operators that turn tables into tables, and the places where SQL's answer is not the one you meant.
Relational algebra shows how every query becomes a tree of operators, the plan the database actually runs. All means none missing builds "every" and "only" out of operators that can only say "some", by subtracting the counterexamples. Yes, no and unknown follows NULL through comparisons, and shows why one missing value can empty a NOT IN.
Read Relational algebra first.
- For all queries in SQL: double NOT EXISTS
How to write "for all" and "only" queries in SQL and relational algebra: ∀ = ¬∃¬, the double NOT EXISTS, and everyone minus the counterexamples.
- Relational algebra: a query as a tree of operators
Relational algebra explained: relations as sets of rows, the operators σ, π, ×, ⋈, ∪, − and ∩, and how every SQL query becomes a tree of them, a query plan.
- SQL NULL and three-valued logic: the NOT IN trap
Why comparisons with SQL NULL return UNKNOWN in three-valued logic, why WHERE drops them, and why NOT IN with one NULL returns no rows.
Reliability
A system is reliable when it keeps doing the right thing even when parts of it fail: disks die, networks drop messages and people make mistakes. At scale failure is not the exception; something is always broken somewhere.
Faults and failures separates the faults that spare parts absorb from the ones that hit every machine at once, and what to do about each.
Read Data systems are built from parts first.
- Faults and failures
Spares stop random faults; bugs and mistakes hit everything at once.
The problem
Before any algorithm, it helps to see what makes this kind of learning hard. There is no teacher with answers, only a number that says how things went, and the only way to find something better is to try things that might turn out worse.
Learning from reward sets out the loop of acting, scoring and adjusting. Explore or exploit names the tension that every method on the rest of the map has to manage.
Nothing comes first: this is the way in.
- Explore or exploit
Use what you know, or find out more: an agent that only does one does badly.
- Learning from reward
Learning from a score, not from answers: try, see how it went, do more of what worked.
Scalability
Scalability is not something a system has or lacks; it is the question of what happens when load grows. Answering it takes words for load and for performance before any talk of more machines.
Describing load picks the few numbers that drive your costs. Percentiles explains why to watch the slow tail rather than the average, and Tail latency amplification why that tail gets worse when one request fans out to many servers. Scaling up and out weighs a bigger machine against more of them.
Read Data systems are built from parts first.
- Describing load
The few numbers that drive your costs, from Twitter’s timelines.
- Percentiles
The average describes nobody; watch the median and the tail.
- Scaling up and out
A bigger machine while it’s simple; more machines for what holds no data.
- Tail latency amplification
A page waits on its slowest server, so rare slowness is common.
Storage
A database keeps its data on disk and works on it in memory, and much of its design comes from how slow the first is next to the second. This topic covers that bottom layer: how data reaches the disk, survives it, and comes back.
Getting there costs more than reading shows why a database moves whole pages and keeps related rows together. One disk that can rebuild any other protects the data with parity instead of full copies. Making room in memory picks which pages stay in the buffer pool, and why the usual rule fails on a scan. External merge sort sorts far more than fits in memory in two passes.
Nothing comes first: this is the way in.
- Buffer pool replacement: LRU, MRU and Clock
Why LRU misses every read when a scan loops over a file one page bigger than the buffer pool (sequential flooding), and when MRU or Clock does better.
- Disk access cost: random vs sequential I/O
Why seek and rotation make random I/O over 100× slower than sequential I/O on a disk, and why databases use large pages and locality.
- External merge sort: sorting data bigger than memory
How a database sorts data far bigger than memory with two-phase multiway merge sort (TPMMS): two passes over the data handle about M² pages.
- RAID parity: one extra disk rebuilds any one
How RAID parity (XOR) rebuilds any one failed disk for 1/N extra space, why every write must update parity, and how RAID 5 spreads that work.
Transactions
A transaction is a group of changes that should happen all together or not at all, and look as if it ran alone. Two things fight that promise: a crash can land between any two disk writes, and other transactions are changing the same rows at the same time. This topic covers how a database keeps the promise anyway.
Write it down first shows how a log written before the data makes a crash harmless. Where recovery can stop keeps that log from growing forever. As if one at a time says when interleaved transactions are safe, and Two-phase locking is the rule that keeps them that way as they run.
Read Getting there costs more than reading and Making room in memory first.
- Database checkpoints: quiescent vs nonquiescent
How database checkpoints let crash recovery stop reading the log early, and how nonquiescent (fuzzy) checkpoints do it without pausing new transactions.
- Conflict serializability and precedence graphs
How a database tells if interleaved transactions are safe: conflicts, the precedence graph and conflict serializability, shown on a lost update.
- Two-phase locking (2PL), strict 2PL and deadlock
How two-phase locking (2PL) makes concurrent transactions serializable, why it can deadlock, and how strict 2PL stops dirty reads and cascading aborts.
- Undo and redo logging: write-ahead logging (WAL)
How write-ahead logging (WAL) makes transactions atomic and durable: undo, redo and undo/redo logs, their write rules, crash recovery, steal and force.
Transformers
The Transformer drops the recurrent network's word-by-word memory and lets every word look at every other word at once. It is the architecture under BERT, GPT, T5 and every large language model since.
Self-attention gives each word a query, a key and a value, and needs position vectors and a mask to know order. Multi-head attention scales the scores by √d_k and splits the work into several heads. The Transformer block wraps attention in residual connections, layer norm and a feed-forward step, and stacks of blocks become encoders, decoders or both.
Subword tokenization decides what the model reads, splitting rare words into common pieces. Pretraining objectives are the games a Transformer plays on raw text before it is ever given a task: next-word prediction, masked words and span corruption.
- Multi-head attention and the √d_k scale
Why Transformers divide attention scores by √d_k (dot products grow and saturate the softmax) and split attention into multi-head attention.
- Pretraining objectives: BERT, GPT and T5
How Transformers learn from raw text: next-word prediction (GPT), masked language modelling with the 80/10/10 rule (BERT), and span corruption (T5).
- Self-attention: queries, keys, values and masking
Self-attention lets every word attend to every word through queries, keys and values; why it needs position vectors, and how a decoder masks the future.
- Subword tokenization: byte-pair encoding (BPE)
How byte-pair encoding (BPE) builds a subword vocabulary by merging the most frequent pair, so a model can split any new word into known pieces.
- Transformer block: residuals, layer norm, encoder–decoder
How a Transformer block wraps attention and a feed-forward network in residual connections and layer norm, and how stacks of blocks become BERT, GPT and T5.
Translation and generation
A language model can score a sentence; this topic makes it write one, either by translating a sentence from another language or by carrying on a piece of text.
IBM Model 1 learns which word translates which from sentence pairs alone, with no dictionary. Seq2seq replaces the counts with an encoder that reads the whole sentence into one vector and a decoder that writes from it. Attention lets the decoder look back at every source word as it writes, instead of relying on that one vector.
The last three pages are about the output. Beam search keeps several drafts to find a likely sentence, sampling with top-k, top-p and temperature keeps open-ended text from going dull, and BLEU scores a translation against one a person wrote.
- Attention in seq2seq: soft alignment for translation
How the attention mechanism lets an encoder–decoder build a fresh context vector at each step: scores, softmax weights, and attention as soft alignment.
- Beam search: decoding beyond greedy
Why greedy decoding can miss the likeliest sentence, how beam search keeps the k best hypotheses, length normalisation, and why it repeats itself in open text.
- BLEU score: how machine translation is evaluated
How BLEU (Bilingual Evaluation Understudy) scores generated text: clipped n-gram precision, the geometric mean and the brevity penalty, and where it fails.
- IBM Model 1: learning word alignments for translation
How IBM Model 1 learns word translations from sentence pairs alone: hidden alignments summed out, EM, and the noisy channel model for translation.
- Top-k, top-p (nucleus) sampling and temperature
How language models pick the next word: sampling, top-k, top-p (nucleus) sampling and temperature, and why cutting the tail keeps text varied but sensible.
- Seq2seq: encoder–decoder translation
How sequence-to-sequence (seq2seq) encoder–decoder models translate: a decoder as a conditional language model, teacher forcing, and the bottleneck.
Trees and ensembles
A decision tree predicts by asking one yes-or-no question after another, which makes it easy to read and able to bend around any shape in the data. That same freedom makes a single tree unstable: change a few examples and it grows differently. This topic is about growing trees, and about taming them by growing many.
Decision trees picks each question greedily by how much purer it leaves the groups, and shows why a tree grown until every leaf is pure gets new data wrong. Random forests averages many trees grown on resampled data, and hides features from each split so the trees disagree in useful ways.
Read Bias and variance first.
- Decision trees: Gini, entropy and greedy splits
How a decision tree picks each split greedily by Gini impurity or entropy, and why a tree grown until every leaf is pure overfits.
- Random forests: bagging, bootstrap and decorrelated trees
Why averaging trees helps: bagging (bootstrap aggregating), out-of-bag error, and how random forests lower tree correlation ρ in ρσ² + (1−ρ)σ²/B.
Unsupervised learning
Most data comes with no answers attached: no labels saying which group a point belongs to or what it should predict. Unsupervised learning finds structure anyway, by assuming the data is simpler than it looks: a few groups, a few directions, a few hidden tastes.
k-means clustering sorts points into groups around centres, and shows why the obvious method can settle on the wrong ones. Which bell did it come from? lets a point belong partly to several groups of different spreads, fitted by EM. The longest shadow (PCA) finds the few directions that carry most of the variation. Matrix completion fills in a mostly empty table, like a film site's ratings, from a few hidden factors.
Read Least squares first.
- Gaussian mixture models and the EM algorithm
How a Gaussian mixture model (GMM) gives each point soft shares in every cluster, and how the EM algorithm fits it, with k-means as the hard limit.
- k-means clustering and k-means++
How k-means clustering groups unlabelled points: Lloyd's algorithm never raises its objective but can stick at a local optimum; k-means++ starts it well.
- Matrix completion: how recommenders fill in ratings
How matrix completion fills a mostly empty ratings grid: low-rank factorization, alternating least squares (ALS), and why a few percent of ratings is enough.
- Principal component analysis (PCA): the longest shadow
Principal component analysis (PCA) finds the directions of most variance, the covariance's top eigenvectors, and how many to keep for the least loss.
Values
A reward says how good this moment is; a value says how good it is to be here, counting everything likely to follow. Almost every method on the map learns values or acts on them, so this is the idea to have solid.
Reward versus value draws the line between the two. Temporal-difference learning and Learning from every move show the first way to learn values from play: nudge one guess toward the next. Play it out, then average learns them from whole episodes instead. Same notes, two answers gives both ways the same few episodes and shows why they disagree, and which one to trust when. Walk a few steps, then guess sits between the two, trading bias for noise.
The last three pages lean on A square is worth its neighbours and Judging a way of playing, so read those first.
- Same notes, two answers
Why batch Monte Carlo and TD(0) disagree on the same episodes: Monte Carlo fits the returns, TD(0) solves the model the data suggests (certainty equivalence).
- Learning from every move
Scoring each position teaches far faster than keeping the strategies that won.
- Play it out, then average
Monte Carlo prediction estimates a state's value with no model by averaging the returns that follow each visit: unbiased, but it waits for the episode to end.
- Walk a few steps, then guess
Add up the next n rewards, then trust the value of where you land: a dial between TD(0) and Monte Carlo, where more steps mean less bias and more variance.
- Reward versus value
Reward is what’s good now; value is all the reward still to come. Choose by value.
- Temporal-difference learning
Nudge each guess toward the next one, and learn during the game, not after it.
Vision and language
To a computer a photo is a grid of numbers. This field follows Rice's COMP 646 from that grid to models that label every pixel, read pictures alongside words, and draw new pictures from a sentence.
Learning to see starts with a small filter sliding over pixels and builds it into convolutional networks, with the training tricks that make deep ones work: momentum, dropout and batch normalization. Labelling every pixel turns a classifier into a network that names each pixel, ending with the U-Net. Images meet text cuts a picture into tokens a Transformer can read, trains pictures and captions into one shared space with CLIP, and hands those tokens to a language model. Generating images runs the other way, from GANs and variational autoencoders to diffusion models, guidance and Stable Diffusion.
Nothing comes first: Image convolution is the way in. Neural networks and Transformers, from Natural language processing, help.
Words as numbers
A model can only add and multiply, so before it can read a review or a sentence, every word has to become a number. This topic follows the ways that has been done, from plain counts to vectors that know which words mean alike.
Bag of words counts each word and throws the order away, which is enough to sort most reviews. Neural networks add a hidden layer, so a classifier can learn that "not" turns the next word round, and backpropagation trains it. LIME then asks such a black box which words it leaned on.
The last three pages give words meanings of their own. LSA squeezes word–document counts with an SVD, skip-gram learns vectors by guessing each word's neighbours, and GloVe fits vectors to ratios of how often words appear together, with the analogies and biases that come with them.
- Bag of words: turning text into word counts
How the bag-of-words model turns text into word counts for text classification, why learned weights beat word lists, and what losing word order costs.
- GloVe: word vectors from co-occurrence ratios
How GloVe (Global Vectors) turns ratios of word co-occurrence counts into vectors, why king − man + woman ≈ queen works, and how bias rides along.
- LIME: explaining one prediction of a black box
LIME (Local Interpretable Model-agnostic Explanations) explains one prediction: cover words at random, ask the model, fit a weighted straight line.
- Latent semantic analysis (LSA): word vectors from counts
How latent semantic analysis (LSA) turns word–document counts into dense word vectors with a truncated SVD, compared by cosine and weighted by TF-IDF.
- Neural networks and backpropagation, step by step
How a hidden layer lets a neural network bend its boundary, and how backpropagation, the chain rule run backwards, trains it on word counts.
- Skip-gram and negative sampling (word2vec)
How word2vec's skip-gram learns word vectors by guessing each word's neighbours, and why negative sampling makes it fast. Toy corpus, live training.