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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.