Anomaly Detection

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.

Of all the hyperplanes that separate two classes, take the one that sits as far as possible from the nearest points on either side. That clearance is the margin, and maximizing it is a bet worth stating plainly: a boundary with room around it is more likely to survive new data than one that squeaks between training points. Two things follow. Only the points on or inside the margin — the support vectors — affect the answer, so most of the training set could be deleted without changing the model. And because the solution depends on the data only through inner products, replacing that inner product with a kernel produces a nonlinear boundary without ever computing the coordinates it lives in.

One Gaussian describes a single blob; real data is usually several, so describe it as a weighted sum of Gaussians and let the fit decide how much of each. The obstacle is that you never observe which component produced a point — that assignment is the latent variable — so you alternate. Given the current components, compute how responsible each is for each point. Given those responsibilities, refit each component to the points it owns, weighted by ownership. The defining feature is that ownership is fractional: a point between two clusters belongs 60/40 rather than being forced into one. k-means is this same loop with the responsibilities rounded to 0 and 1 and every covariance forced spherical and equal, which is exactly why k-means cannot represent an elongated or overlapping cluster and this can.

Every other detector in this section models what normal looks like and flags whatever falls outside. This one models the anomalies directly, from a single observation: anomalies are few and different, so a random split is more likely to separate one from the pack than to separate two ordinary points from each other. Cut the data with random splits until every point is alone, and record how many cuts each one needed. Outliers fall out early, in a handful of cuts; points inside a dense cluster survive many. The depth at which a point becomes alone IS the anomaly score, and no density was ever estimated to get it.

Data with many correlated columns does not really occupy all those dimensions — it sits near a lower-dimensional plane inside them. PCA finds that plane: the direction along which the points spread out most, then the direction of most remaining spread perpendicular to it, and so on. Keep the first few and you have a compressed description that loses very little. The catch is in what "loses very little" means, and it is worth being suspicious of: PCA measures loss as squared distance, so it keeps whatever varies most. Variance is not the same as information, and the direction that separates two classes can easily be one of the ones you just discarded.

Stand on any point and count how many others are within a fixed radius ε. If at least minPts are (the point itself included), you are standing somewhere dense, and the point is a core point. Two core points within ε of each other are in the same cluster, and so is anything that chains through a sequence of such steps — the cluster is the crowd you can walk across without ever crossing a gap wider than ε in a crowded place. Points within ε of a core point but not dense themselves are border points: they join the cluster, but you cannot walk onward through them. Everything left over is noise. Nothing in this asks for the number of clusters, and nothing assumes a shape — a ring, a crescent and a blob are all just connected regions of density — which is exactly where k-means, with its convex Voronoi cells, fails. What it asks for instead is a single, global notion of "close", which is the whole difficulty: ε is a distance, so it is only as meaningful as the metric that measures it, and one ε cannot describe two clusters of different density.

Separate what the system is doing from what you managed to measure. The state is the thing you care about — a position, a level, a trend — and it evolves by its own rules. The observation is a noisy, possibly incomplete look at it. Then run two steps forever. Predict: push the state forward and let the uncertainty grow, because time passing makes you less sure. Update: take the measurement and move the estimate toward it, by an amount that depends on which you trust more. That trade-off is the whole filter, and the Kalman gain is literally its arithmetic — when your prediction is uncertain and the sensor is good, the gain is near one and you believe the sensor; when the reverse, you barely move.

A recurrent cell that carries an explicit memory track alongside its hidden state, and learns three gates that decide what to erase from that memory, what to write into it, and what to expose. The memory passes forward through addition rather than repeated multiplication, which is the entire trick: gradients can travel back hundreds of steps without vanishing.

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.

Ordinary least squares answers "what is the typical outcome here?" Quantile regression answers "what outcome should I expect to be exceeded only 10% of the time here?" It fits the same straight line, but penalizes a miss on one side more than a miss on the other: for the 90th percentile, undershooting costs nine times as much as overshooting, so the line is pushed up until exactly 90% of the points sit beneath it. Fit several tau values and you get a band, not a line, and the band can fan out where the data is noisier, which a single mean line cannot say.

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.

Start with every point as its own cluster, find the two closest clusters, merge them, and repeat until one cluster remains. The record of those merges — which two joined, and at what distance — is the dendrogram, and cutting it at any height or at any K gives a flat clustering for free. Everything interesting hides in one word, closest: the distance between two clusters is not defined until you choose a linkage. Single linkage uses the nearest pair of points, so clusters join along thin bridges and chain into long streaks. Complete linkage uses the farthest pair, so clusters stay compact. Average linkage splits the difference. Ward merges whichever pair increases the within-cluster sum of squares least, which is k-means’ objective applied greedily, and it is the only one of the four that needs Euclidean geometry. The others need only a dissimilarity — no mean, no coordinates, no metric axioms — so this is the clustering you reach for when your data is word sets compared by Jaccard, embeddings compared by cosine, or time series compared by dynamic time warping.

Slide a small learned filter across the input and record how strongly it responds at each position. Two assumptions are baked into that operation and they are the whole reason it works: nearby inputs are related (locality), and a feature worth detecting in one place is worth detecting everywhere (translation equivariance, via weight sharing). Stack these layers and the receptive field widens, so early layers see edges and later ones see objects.

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.

Downsampling is how a network learns WHAT is in an image, and it is exactly what destroys WHERE it is. A U-Net refuses to choose. A contracting path (convolution, then downsample, repeated) trades resolution for context until the bottleneck sees the whole scene. An expanding path (upsample, then convolution) climbs back to input resolution. And at every scale the encoder feature map is CONCATENATED onto the decoder feature map, handing the decoder the fine spatial detail the pooling threw away, so it only has to decide what each pixel is rather than reconstruct where the boundary was. The output is a class distribution at every pixel, which is why it is called dense prediction. Concatenation is the point: ResNet adds its skip, which forces the two sources to share channels and be summed blindly, whereas a U-Net stacks them and lets the next convolution learn how much of each to trust.

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.

A hundred traffic sensors are not a hundred independent series: congestion at one junction shows up downstream twenty minutes later, and the road network says which junctions are downstream. So alternate two operations — mix each node with its graph neighbours, then mix each node with its own recent past — and stack them. Spatial dependency comes from the graph rather than from being learned blind, which is the entire reason this beats a per-series model when the network is real.

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.

Instead of predicting tomorrow’s demand, predict the parameters of a distribution over tomorrow’s demand — a mean and a shape — and train by maximizing the likelihood of what actually happened. To forecast further than one step, sample a value from that distribution, feed it back as the next input, and continue; do that a few hundred times and you have a cloud of possible futures. Any quantile you need is then just a percentile of those trajectories, and crucially the uncertainty compounds correctly across the horizon because each step’s sample genuinely conditions the next.

An autoencoder that is forced to be probabilistic: instead of mapping an input to a single point in latent space, the encoder outputs a small Gaussian, and the decoder must reconstruct from a sample of it. Because nearby latent points now decode to similar outputs, the latent space becomes continuous rather than a scatter of memorized codes — which is what makes sampling from it produce something new rather than noise.

Start from a simple distribution you can sample and evaluate — a standard Gaussian — and push it through an invertible function. The change-of-variables formula says exactly what happens to the density: it is the base density at the preimage, corrected by how much the transformation stretched or compressed space there. So if you can build a flexible invertible function whose local volume change you can compute cheaply, you get an exact likelihood for free. The entire field is a search for such functions, and every architecture in it is a different answer to the same question: how do you keep a Jacobian determinant tractable without making the map trivial?

Draw the straight line (or hyperplane) that comes closest to every point at once, where "closest" means the sum of squared vertical distances is as small as it can be. Every coefficient answers one question: if this feature goes up by one unit and nothing else moves, how much does the prediction change?

Ordinary least squares will happily hand two nearly identical features enormous coefficients of opposite sign, because only their sum is pinned down by the data. Put a price on coefficient size and that stops. An L2 price (Ridge) is smooth, so it shrinks correlated features toward each other and keeps all of them; an L1 price (Lasso) has a corner at zero, so it pushes most coefficients exactly to zero and hands back a subset. Elastic net charges both. In every case you are buying a large reduction in variance with a small amount of bias — deliberately fitting the training data worse in order to predict new data better.

Take the linear model, then squash its unbounded output through a sigmoid so it lands in [0, 1] and can be read as a probability. Each coefficient answers: how much does one unit of this feature move the log-odds? The decision boundary is still a hyperplane — the sigmoid changes what the output means, not what shapes the model can separate.

Linear regression assumes what you are predicting is a real number with constant-variance noise. Counts are not: they cannot go negative, and a count with a mean of 100 is genuinely noisier than one with a mean of 2. A GLM keeps the linear predictor — a weighted sum of features — and changes two things around it. A link function maps that sum onto the range the response actually lives in, and a variance function states how the noise grows with the mean. Choose identity link and constant variance and you have recovered OLS; choose logit and mu(1-mu) and you have logistic regression; choose log and mu and you have Poisson regression. It is one algorithm with the distributional assumption written down instead of assumed away.

Use Bayes’ rule to turn "how likely is this evidence under each class" into "how likely is each class given this evidence" — then make one deliberately false assumption to render it computable: pretend every feature is independent of every other, given the class. Modelling the true joint distribution of a thousand features is hopeless; modelling a thousand one-dimensional distributions is arithmetic. The assumption is wrong on essentially every real dataset, and the classifier works anyway, because picking the largest score does not require the scores to be correct — only correctly ordered.

Instead of fitting one function, put a probability distribution over all the functions that could have produced the data, and let the observations narrow it. The kernel is what makes this concrete: it states how correlated the function values at two inputs should be, which is the same as stating how smooth, how wiggly, and how periodic you believe the function is. Conditioning that prior on the data gives a posterior that is again Gaussian, so the answer is closed-form — a mean and a variance at every input. The variance is the part that earns its keep: it is small where data is dense, and it widens automatically wherever you leave the data behind, which no point-estimate regressor will tell you.

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.

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.

Three ideas stacked, and the acronym is in the wrong order for how they are applied. First integrate: difference the series until it is stationary, because everything that follows assumes the statistical behaviour does not drift. Then autoregress: predict the differenced value from its own recent values. Then add moving average: also predict it from the recent forecast ERRORS, which is how the model absorbs shocks that persist for a few periods without permanently changing the level. The AR part remembers where the series was; the MA part remembers where the model was wrong. That second memory is what distinguishes ARIMA from a regression on lag features, and it is why its intervals are calibrated rather than optimistic.

Forecast with a weighted average of the past where recent observations count for more, and the weights fall away geometrically. One parameter controls how fast the memory fades: near one and the model chases every wiggle, near zero and it barely moves. That is simple exponential smoothing, which handles a level. Add a second component that tracks how fast the level is changing and you have a trend. Add a third that tracks the repeating pattern and you have Holt-Winters. Each component is updated by the same rule — blend what you just observed with what you already believed — so the entire model is three numbers of state and three parameters, and it never looks at more than the last observation.

A feedforward network sees a fixed-size input and has no way to represent "what came before". Give it a hidden state that is fed back in alongside the next input and it does: the state is a running summary of everything seen so far, updated once per step. Weights are shared across steps, so the same update rule applies at position three and position three hundred — which is what lets one model handle sequences of any length. The trouble is in the gradient. To learn from step three hundred what happened at step three, the error has to be multiplied back through three hundred copies of the same matrix, and repeated multiplication by a matrix either shrinks toward zero or grows without bound. Almost nothing in between.

A plain RNN overwrites its state at every step, which is why a signal from far back is gone by the time it would be useful. The fix is to let the network decide, per step and per dimension, how much to overwrite and how much to keep. That is the update gate: a number between zero and one that interpolates between the old state and a freshly computed candidate. Set it near zero and the state passes through untouched — and crucially, the gradient passes through with it, because carrying a value forward is addition rather than multiplication. The reset gate does the complementary job: it decides how much of the old state the candidate is even allowed to look at, which lets the unit forget deliberately rather than by decay.

A convolution over time looks at a fixed window, which is too short to be useful and too expensive to widen by brute force. Two modifications fix that. Causal: pad only on the left, so a position never sees the future — without which the model cheats and the validation numbers are fiction. Dilated: skip a growing number of positions between taps at each layer, so a stack of layers with dilations 1, 2, 4, 8 reaches back sixteen steps with four layers rather than sixteen. The receptive field doubles per layer, so it grows exponentially in depth while the parameter count grows linearly. And because nothing is carried forward, every output position is computed from its own window independently — the entire sequence in one parallel pass.

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.

Cut the image into a grid of 16-by-16 patches, flatten each one into a vector, and feed the resulting sequence to a plain text transformer with nothing changed. The model is told nothing about two-dimensional structure — not locality, not translation equivariance, not scale — beyond a learned position embedding per patch. That sounds like it should not work, and on a hundred thousand images it does not: below a certain data scale a convolutional network wins comfortably, because the biases a CNN hardcodes are true and free. Above that scale the transformer learns better biases than the ones we knew to build in, and overtakes.

Most forecasting inputs are not the same kind of thing. Store size never changes; a public holiday next Tuesday is known now; yesterday’s footfall was observed and tomorrow’s will not be. A plain sequence model that concatenates all of these into one vector per timestep either leaks future information or throws away covariates it legitimately has. TFT keeps the three kinds separate by construction, learns which variables matter at each step, and emits quantiles rather than a point — which is what a forecast is actually for, since the decision downstream is almost always asymmetric in cost.

Give a block the last few hundred observations and ask it for two things: a forecast, and a reconstruction of the input it thinks it explained. Subtract that reconstruction from the input and hand the remainder to the next block. Each block therefore works on what its predecessors could not explain, and the forecasts add up — which is gradient boosting’s idea rearranged into a neural network, and exactly the same idea as classical decomposition into trend and seasonality, except the components are learned instead of specified.

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.

A residual block computes h + f(h), which is Euler’s method for an ODE with a step size of one. Take that seriously: shrink the step, let the solver choose how many it needs, and the network stops being a fixed stack of layers and becomes a vector field that something else integrates. Two things follow that are not merely aesthetic. The trajectory is defined at every time, not just at layer boundaries, which is exactly what an irregularly sampled series needs. And because the dynamics are reversible, the backward pass can be recomputed instead of stored, so memory stops growing with depth.

A neural network is a differentiable function, so you can compute its derivatives exactly with the same machinery that computes its gradients. That means you can write down a differential equation, evaluate how badly the network violates it at a scatter of points, and make that violation the loss. The result is a mesh-free solver whose solution is a closed-form function you can differentiate anywhere — and, more usefully, a framework where unknown coefficients in the equation are just more parameters to fit alongside the network.

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.

Train a forger and a detective at the same time. The forger produces samples, the detective tries to tell them from real data, and each improves against the other. Neither ever sees an explicit description of what makes data realistic — the forger only ever learns from the detective’s mistakes. That is the appeal, because it means no likelihood needs to be defined and no reconstruction distance has to be chosen, which is why GAN images were sharp when everything else was blurry. It is also the problem: the target is moving, so there is nothing that decreases monotonically and no loss value that tells you how well it is going.

A plain GAN’s discriminator answers a classification question, and once it can answer it confidently it stops being informative — the gradient it hands back vanishes exactly when the generator most needs guidance. Replace it with a critic that scores rather than classifies, constrain how fast that score can change, and the answer becomes a distance that stays meaningful however far apart the two distributions are. Separately and independently: tell both networks what they are looking at. A generator given a class label learns one conditional distribution per label rather than one blurred mixture, and the critic can then check that the sample matches its label rather than merely looking real.

Generating an image in one step is hard; removing a little noise from a slightly noisy image is easy. So define a process that gradually destroys data into pure noise over a thousand steps, train one network to undo a single step of it, and then run that network a thousand times starting from noise. Nothing about any individual step is difficult, which is why this trains stably where a GAN does not — and the price is paid exactly where you would expect, at inference, where a thousand sequential network evaluations produce one sample.

Stop thinking about a thousand discrete denoising steps and think about a continuous path from noise to data. At any point along that path there is a direction that leads toward the data distribution — the score, or equivalently a velocity — and a network can be trained to predict it by regression. Once you have that direction field, generating a sample is solving a differential equation, which means every numerical-integration technique becomes available. Flow matching then asks the obvious follow-up: if the path is ours to choose, why not choose a straight one? A straight path can be traversed in very few large steps, which is the whole reason modern samplers need dozens rather than thousands.

Two ideas arriving at the same time. The first: a forecast and an imputation are the same operation — some values are known and some are not, and a conditional generative model fills in the unknown ones. Mask the future and you get forecasting; mask the middle and you get imputation; the model does not distinguish. The second: a model pretrained on millions of unrelated series learns what series look like in general, so it can forecast one it has never seen without being fitted to it. That is a genuinely new capability for forecasting, and it is also the one that most needs careful evaluation, because the corpus is enormous and the benchmarks are public.

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.

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.

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.

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.