Recommendation & Ranking

Do not build a model of the world. Keep every example you have seen, and when a new point arrives, find the handful that look most like it and copy their answer — a majority vote for a class, an average for a number. Everything hard about the method is hidden in "look most like it": the distance function is the model, and choosing it badly is a modelling error that no amount of tuning k will repair. The trade is stark and worth stating up front: training costs nothing, and inference costs everything.

Describe every item as a vector of its own properties — the words in an article, the tags on a film, an embedding of a product photo — then describe a user as the average of the items they liked. To recommend, find the unseen items whose vector points the same way as the user’s. Nothing here looks at what other people did, which is its defining strength (a brand-new item can be recommended the moment it is described) and its defining weakness (it can only ever recommend more of what the user already showed they like). The method is a chain of three representation decisions — how items become vectors, how likes become a profile, how similarity becomes a score — and the third is where most implementations are quietly wrong. Cosine is right for TF-IDF because it divides out document length; Jaccard is right for binary tag sets because it penalises size imbalance; a raw dot product is right only when vector magnitude is meant to carry popularity or confidence. Choosing among them is a claim about the data, not a tuning knob.

Fit a shallow tree, look at what it got wrong, then fit another tree to those errors, and keep going. Each tree is deliberately weak — a few splits, shrunk by a small learning rate — so no single one can overfit, and the ensemble corrects itself gradually. Random Forest averages many independent strong trees to reduce variance; boosting chains many dependent weak trees to reduce bias, which is why the two behave so differently despite both being tree ensembles.

A ratings matrix has millions of rows and columns and almost nothing in it — most users have touched almost nothing. The bet is that behaviour is driven by a small number of underlying factors, so the matrix is approximately low rank: describe each user by a short vector of tastes, each item by a short vector of attributes, and predict an interaction as the dot product between them. Nothing says what the factors mean, and they are not interpretable; what matters is that fitting them on the entries you observed lets you fill in the ones you did not. The crucial detail is that the sum runs only over observed entries — treating the blanks as zeros would be a completely different and much worse model.

A transaction is a set of items — a basket, a session, a patient’s diagnosis codes — and the question is which items keep turning up together. Count how often every combination appears, keep the combinations that appear often enough (high support), and from each frequent combination read off rules of the form X ⇒ Y whose confidence — of the baskets containing X, the fraction that also contain Y — is high enough to act on. There are no coordinates, no vectors and no distances here: a basket is an unordered bag with no magnitude, so every comparison is an overlap of sets. The one structural fact that makes this tractable is that a combination can only be frequent if all of its sub-combinations are, which lets the search discard most of an astronomically large lattice without ever counting it. What the method cannot do is tell you why items co-occur, and the first number everyone reaches for, confidence, is misleading whenever the consequent is popular — which is why lift exists.

A single linear layer can only draw a straight boundary. Put two of them back to back with a nonlinearity in between and the first layer can bend the space before the second one cuts it — which is enough to separate things no straight line could. Stack more and each layer works on features the previous one built rather than on the raw input. Training runs the network forward to see how wrong it is, then walks the error backwards through the layers, and at each step the chain rule says how much each weight contributed. Backpropagation is exactly that: the chain rule, with the shared intermediate results computed once instead of once per weight.

Word2vec learned that a word is defined by the words it appears near. A graph has no sentences, so make some: start at a node and take a random walk, and treat the sequence of nodes you visit as a sentence. Then run skip-gram on that corpus unchanged. Nodes that keep showing up in each other’s walks get similar vectors, and because a walk can be biased to either circle a neighbourhood or head away from it, the same machinery produces either community structure or structural role depending on two knobs.

Once a model has turned a million documents into a million vectors, answering a query means finding the nearest few — and comparing against all million is too slow. So give up exactness: build a structure that looks at a few thousand candidates instead of a million and usually finds the same answer. The word "usually" is the entire subject. An ANN index does not fail by being slow, it fails by silently returning the second-best neighbour, and how often it does so is a dial you set rather than a property you measure once.

Two separate encoders — one for the query, one for the item — trained so that relevant pairs land close together in a shared vector space. The separation is the entire architectural point: because the item tower never sees the query, every item embedding can be computed offline and indexed. Retrieval then becomes nearest-neighbour search rather than scoring millions of candidates one at a time. A cross-encoder is more accurate and structurally cannot do this.

Nothing here specifies what an embedding should be. It specifies only that paired things should end up closer than unpaired things, and the geometry falls out of enforcing that over millions of pairs. This is why the technique is defined almost entirely by its data: the encoder is ordinary, and the consequential choices are what counts as a positive pair, where the negatives come from, and the temperature that decides how hard the loss pushes on the closest wrong answer. Get the pairs right and a small encoder beats a much larger one. Get them wrong and the embeddings look fine on held-out pairs from the same distribution while failing on everything real, because the model learned to solve the sampling artefact rather than the task.

Everything else in this category spends its effort on credit assignment across time. A bandit has no time to assign across — you pick an arm, you get a reward, and the next decision starts from the same place. What is left when the temporal structure is gone is the exploration-exploitation trade in its purest form: you can only learn about an arm by pulling it, and every pull spent learning is a pull not spent earning. Three answers matter. Epsilon-greedy explores at random with some probability, which is simple and wasteful, because it explores arms it already knows are bad just as often as promising ones. UCB is optimistic in the face of uncertainty: score each arm by its estimated mean plus a confidence bonus that shrinks as it is pulled, then take the best score. An arm that looks bad but has barely been tried keeps a high bonus and gets tried again; an arm that has been tried and is genuinely bad falls away. Thompson sampling is Bayesian and even simpler to state: keep a posterior over each arm's value, draw one sample from each, play the argmax of the samples. Arms the posterior is uncertain about sometimes draw high and get played, in exact proportion to the probability they are best. What makes this group worth studying is that it is the only one here with meaningful theory — regret bounds that hold, are tight, and are actually predictive of behaviour — and simultaneously the group that appears most often in production, usually in contextual form. It is also the group most often reached for wrongly, because the assumption it rests on, that actions do not change the state, fails quietly rather than loudly.

Summarize the data with k representative points. Start with k guesses, assign every observation to its nearest guess, then move each guess to the centre of what it just captured, and repeat until nothing moves. The objective it descends is the total squared distance from points to their own centre, and the two steps alternate between the two things that objective depends on — which assignment, and which centres. What makes it so widely used is that both steps are trivial and it converges quickly. What makes it so widely misused is that it always returns exactly k clusters, whether or not the data has any.

Each node builds a representation by gathering messages from its neighbours, combining them, and updating itself — then repeats. After k rounds a node has absorbed information from everything within k hops. It is convolution generalized off the grid: a CNN assumes neighbours are the adjacent pixels, a GNN asks you to supply the adjacency explicitly. That single change is what lets it operate on molecules, payment networks, and road systems, where "nearby" is a relationship rather than a coordinate.

Every position looks at every other position and decides, from content alone, which ones matter to it. A convolution asserts in advance that neighbours are relevant; recurrence asserts that recency is. Attention asserts neither — it learns the routing. That is why it transfers across modalities, and also why it needs far more data than architectures whose prior is built in: it has to learn from scratch what the others assume.

Force the data through a narrow layer and demand that it come out intact. Because the bottleneck cannot carry everything, the network has to discover what is worth keeping — and whatever survives that squeeze is a representation. The corollary is the useful part: an input the network cannot rebuild is an input unlike anything it learned to compress, which is exactly what an anomaly is.

Tabular Q-learning stores one number per state-action pair, which means it cannot play a game whose screen has more configurations than there are atoms in anything. Replace the table with a network that maps a state to a vector of action values and the method generalizes: states that look alike get similar values without being visited separately. That substitution is the entire idea, and it breaks the convergence proof immediately. The proof relied on each update touching exactly one cell; a network update moves every state at once, including the state the target was just computed from, so the agent is chasing a target that moves because it moved. DQN makes this work with two blunt interventions. Experience goes into a large replay buffer and minibatches are drawn from it at random, which breaks the temporal correlation that makes consecutive samples nearly identical. And the target is computed from a separate copy of the network that is frozen for thousands of steps, which stops the target from moving every time the estimate does. Neither is a fix. They convert a method that reliably diverges into one that usually does not, and the residual failure is not an error message — it is a Q-value curve that climbs smoothly to a thousand while the agent gets worse. The right time to reach for DQN is when actions are discrete, a simulator can supply tens of millions of transitions, and a policy-gradient method is not a better fit. That is a narrower set of conditions than its fame suggests.

Every value-based method so far has produced a policy as a by-product: learn the values, take the argmax. That works until the action space is continuous or combinatorial, at which point the argmax itself becomes an optimization problem you cannot afford to solve at every step. REINFORCE takes the other route and parameterizes the policy directly, then asks how to improve it. The obstacle is that expected return is an expectation over trajectories the policy itself generates, so changing the parameters changes the distribution being averaged over, and there is no obvious way to differentiate through that. The score-function identity resolves it in one line: the gradient of an expectation over a parameterized distribution equals the expectation of the outcome times the gradient of the log-density. Both sides are expectations you can sample. So the algorithm is embarrassingly simple — run an episode, compute the return, and take a gradient step that makes every action taken more likely in proportion to how good the return was. Good episodes get reinforced, bad ones get suppressed, and nothing needs to be known about the environment. What you pay for that generality is variance. The estimator is unbiased and it is also so noisy that the raw form is essentially unusable on anything real, which is why every practical policy-gradient method is REINFORCE plus a stack of variance reductions. The failure mode is distinctive too: with no exploration mechanism outside the policy itself, a policy that becomes deterministic early has no way back, because the gradient for an action it never takes is never sampled.

Regress the outcome on the covariates, regress the treatment on the covariates, and then regress one set of residuals on the other. What is left after removing everything the covariates explain is the part of the treatment that was effectively random, and its relationship to the leftover outcome is the effect. Using flexible learners for both nuisance models would normally bias the result; the residual-on-residual form plus cross-fitting is what cancels that bias out.

Write the decision as a list of numbers, the cost as a weighted sum of them, and every rule as a weighted sum that must stay under a limit. Each rule cuts space in half with a flat wall, so the set of decisions that obey every rule is a many-faced solid, a polytope. A linear cost is a tilted plane, and sliding that plane as far as it will go while still touching the solid always ends on a corner. That one geometric fact is the whole algorithm: simplex starts at a corner and walks along edges to a neighbouring corner that is cheaper, and it can stop the moment no neighbour is cheaper, because a convex solid has no false peaks. Interior-point methods reach the same corner by a different route, cutting through the inside along a smooth path instead of along the skin. The second idea is what makes this explainable to a business: every wall has a price. The dual variable on the machine-hours constraint says what one more hour is worth, and it comes out of the same solve for free. Then comes the cliff. Require that some variables be whole numbers (build the plant or do not, ship whole pallets) and the feasible set stops being a solid and becomes a scatter of lattice points inside one. The problem becomes NP-hard, and the practical method is to solve the continuous version, branch on a fractional variable, and let the continuous solution serve as a bound that prunes most of the tree. Everything that follows is about how well the continuous relaxation approximates the integer problem.

Instead of asking a stack of layers to learn the mapping H(x) directly, ask it to learn only the correction F(x) = H(x) - x and add the input back: y = F(x) + x. If the best thing a block can do is nothing, it only has to push its weights toward zero, which is easy; a plain stack has to learn the identity map through several nonlinear layers, which turns out to be hard. That is the whole idea, and its consequence was surprising: before it, making a network deeper made it train worse, not just generalise worse. After it, hundreds of layers train with ordinary SGD, and the shortcut became the default way to wire any deep network.

Predict the next token, over and over, on everything ever written. The objective is trivial and the consequence is not: to predict the next token well you have to model syntax, then facts, then reasoning, then style, because all of those constrain what comes next. Nothing in the training says "learn arithmetic" — arithmetic is learned because it helps predict the token after an equals sign. That is the whole argument for scale, and it is also why the capabilities are uneven in ways that are hard to predict from the objective.

A dense layer applies every parameter to every token, which ties capacity to cost: doubling the parameters doubles the arithmetic. Replace the layer with many copies and a small router that picks one or two per token, and the two quantities come apart — total parameters grow with the expert count while per-token compute stays fixed. The difficulty is immediate and is the whole subject: the router is trained by gradient descent on the primary loss, and the fastest way for it to reduce that loss early is to send everything to whichever expert is currently best, which starves the others of gradient and makes them permanently worse. So a separate auxiliary loss is added whose only job is to stop that, and tuning its weight against the primary loss is the real engineering.

Fine-tuning a large model means changing every weight, which means storing a gradient and two optimizer moments for every weight — several times the model's own size in memory before a single activation is saved. The observation behind LoRA is that the CHANGE a fine-tune makes is far simpler than the model it changes: adapting a general model to legal drafting or to one company's support tone is not learning language again, it is nudging behaviour the model already has. So freeze the pretrained weight and learn a low-rank correction beside it, W0 + BA with an inner dimension of eight or sixteen instead of four thousand. Two consequences fall straight out. Training memory collapses, because optimizer state is proportional to trainable parameters and there are now a thousand times fewer. And the result is a small file that means nothing on its own, which is a feature — one frozen base can serve hundreds of tenants, each with their own adapter, if you are willing to keep it unmerged. The failure mode is the mirror image of the premise: when the task really does require capability the base does not have, a low-rank update cannot express it, and no amount of tuning reveals that the ceiling is structural rather than statistical.

A pretrained model can produce a plausible continuation but has no notion of which of two plausible continuations anyone would rather receive, and the reason is structural: next-token likelihood rewards imitating the training distribution, which contains excellent and terrible text in unknown proportion. Preferences are the missing supervision, and they are cheap in a specific form — people are unreliable at scoring a response out of ten and fairly reliable at saying which of two they prefer. So collect comparisons, fit something that explains them, and push the model toward what wins. Two routes from there. Classic RLHF fits a reward model to the comparisons and then optimizes the policy against it with reinforcement learning, held near the original by a KL penalty. DPO observes that the optimal policy under that penalty has a closed form, inverts it to express the reward in terms of the policy itself, and lands on a logistic loss over preference pairs with no reward model and no sampling. The idea that makes both work is also the one that makes them fail: because only differences are ever observed, the optimization has a direction it can run in forever, and the KL term is the only thing holding it. Release that and you get a model that scores superbly and is worse.

Decide once what counts as the state, and make it a state that renders the past irrelevant — everything you need to know about history is in the current description. Then the value of a situation decomposes: what you get now, plus the discounted value of wherever you land. That recursion is the whole idea, and it is the reason a problem spanning a thousand steps can be attacked one step at a time. What makes it more than a tautology is the discount. Because a future reward is worth strictly less than a present one, the one-step backup shrinks disagreements between any two guesses by a constant factor, so repeating it drives every starting point to the same answer. Existence, uniqueness and a convergence rate all fall out of that single fact. The cost is stated equally simply: the whole structure rests on the state being genuinely Markov, and when it is not, the equations still have a fixed point — just not the one anybody wanted, and nothing in the arithmetic says so.

Two loops that chase each other. One asks "given how I currently act, what is each state worth?", the other asks "given those values, is there a better action anywhere?". Improve the policy and the old values are stale; re-evaluate and the policy may no longer be greedy. Run them against each other and they converge to the pair that is consistent — the optimal policy and its value function. The interesting part is how much evaluation to do before improving again. Solve it exactly every time and you have policy iteration, which takes very few rounds and pays heavily for each. Do a single backup and improve immediately and you have value iteration, which takes many cheap rounds. They are the two ends of one dial, the answer is identical, and which end is cheaper depends almost entirely on the discount — a fact that decides real runtimes and is almost never checked before a solver is written.

Play the episode to the end, add up what you actually received, and use that as the value of every state-action pair you passed through. Average over enough episodes and the averages converge on the truth, because they are averages of exactly the thing being estimated. Two consequences follow and they are both unusual. The estimate is unbiased and it never assumes the state is Markov — it does not predict the future from the current state, it measures the future that occurred, so a state representation that hides something still produces correct values for the process as experienced. Nothing else in this category can say that. The costs are equally plain. You learn nothing until the episode terminates, which rules out continuing tasks entirely, and the return of a long episode is the sum of many random quantities, so the variance is large and shrinks only as the square root of the episode count. The subject that actually dominates any implementation, though, is neither: it is that a greedy policy visits a vanishing fraction of the state-action pairs, so most of the table is never estimated at all and the improvement step chooses between numbers that were never measured.

Monte Carlo waits for the episode to finish and averages what happened. Temporal-difference learning refuses to wait: it takes one step, sees the reward, looks at its own estimate of where it landed, and updates toward that. The target is therefore partly made up — it contains the very quantity being learned — and the whole method is an argument that this is a good trade. It is. Substituting an estimate for the remaining trajectory removes almost all of the variance, because a single reward plus one value lookup is far less random than a sum over a hundred future steps, and the resulting method learns online, from incomplete episodes, in tasks that never terminate. What it buys with is bias and an assumption. The bias is real and does not vanish with data — a wrong value at the next state propagates backwards into this one. The assumption is that the state is Markov, because bootstrapping trusts the next state's estimate to summarize everything after it; where Monte Carlo is simply indifferent to state aliasing, this converges confidently to the wrong answer. Lambda is the dial between the two extremes, and the best setting is almost always in the middle.

Q-learning asks "what would this be worth if I acted optimally from here?" and answers a question about a policy nobody is following, because the agent is still exploring. SARSA asks the question the agent can actually act on: "what is this worth given that I will keep behaving the way I am behaving, mistakes included?" The change is one symbol in the update — the next action is the one that will be taken rather than the best available — and the consequence is a genuinely different value function. An agent learning under SARSA discovers that standing next to a cliff is dangerous, because sometimes it does fall off, and it routes around the edge. Q-learning learns the shortest path along the edge and then keeps falling off it, because the values it learned assume an optimality its own exploration contradicts. Neither is wrong: SARSA is correct about the policy being run and Q-learning is correct about a policy that would be run if exploration stopped. Which one you want depends on whether exploration is free, and the answer to that is usually no.

Keep a table of "how good is taking action a in state s", then wander the environment updating each entry toward the reward you just got plus the best value you think is available from wherever you landed. The bootstrapping is the whole trick: you never wait to see how the episode ends, you update toward your own current estimate of the future. Do that enough times and the estimates converge on the truth — and acting greedily on them is the optimal policy.