Anomaly Detection

Clustering asked which unlabelled points belong together. This note asks the opposite question of the same unlabelled data: which point does not belong at all?

An aircraft engine comes off the line and is measured — heat generated, vibration intensity, a dozen other numbers. Thousands of engines have been measured before it, and almost all of them were fine. Nobody has labelled which of the earlier engines were faulty, and nobody can list the ways a new engine might fail. What is available is a cloud of points that represents normal, and one new point that is either in it or outside it.

In one line. Fit a probability model $p(\vec{x})$ to data you believe is normal, then flag any new example whose probability falls below a threshold: $p(\vec{x}) < \epsilon$ means anomaly. With one Gaussian fitted per feature and the features treated as independent, $p(\vec{x})$ is just the product of $n$ one-dimensional bell curves — and $\epsilon$ is chosen on a cross-validation set that does contain a few labelled failures.

The question, and where it is asked

The setup is always the same shape. You have ${\vec{x}^{(1)}, \ldots, \vec{x}^{(m)}}$ — examples that are mostly normal — and a new $\vec{x}_{\text{test}}$, and you must decide whether the new one is unusual enough to act on. Three standard settings:

• Manufacturing. $\vec{x}^{(i)}$ is the measured features of product $i$ — an aircraft engine, a circuit board, a smartphone. An anomalous unit gets pulled for inspection.
• Fraud detection. $\vec{x}^{(i)}$ is the features of user $i$'s activity: pages visited, transactions per day, posts written, typing speed. Users with low $p(\vec{x})$ are not banned — they are sent for additional checks, because the model's output is a suspicion, not a verdict.
• Monitoring machines in a data centre. $x_1$ memory use, $x_2$ disk accesses per second, $x_3$ CPU load, $x_4$ the ratio of CPU load to network traffic. That last one is a constructed feature, and it is the interesting one: a web server with high CPU and high traffic is busy, while high CPU with low traffic is a machine stuck in a loop.

Density estimation

The method is to model how the normal data is distributed and then read off how likely the new point is under that model:

Picture the training points as a cloud with contour rings drawn around its centre. Points inside the inner rings sit where the data is dense and get a high probability; points out past the last ring get a small one. $\epsilon$ is where you decide to draw the line, and it is a genuine design choice — §8 is about how to make it. Figure 4 draws that picture for real once the parameters are in hand, and the thing worth noticing in advance is that choosing $\epsilon$ is choosing one of the rings.

The Gaussian

The formula and its two parameters

For a single number $x$, the model is the normal (Gaussian, bell-shaped) distribution:

Two things follow from that normalisation and are worth holding on to. The area under the whole curve is $1$, because $x$ has to take some value. And the curve is a density, not a probability — its height at a point can exceed 1, as it does below for $\sigma = 0.5$.

What $\mu$ and $\sigma$ do to the curve

Fitting the parameters

Given the training data, $\mu$ and $\sigma^2$ are estimated the obvious way — the mean of the data and the mean squared deviation from it:

$\frac{1}{m}$ or $\frac{1}{m-1}$? Statistics texts divide the variance by $m-1$ to make the estimator unbiased; maximum likelihood gives $m$. For anomaly detection it makes no practical difference — $m$ is in the thousands, the two differ by a factor of $m/(m-1) \approx 1.0002$, and any effect is absorbed when you tune $\epsilon$ anyway.

From one feature to many

The independence product

Each example is a vector now, and the model treats the features as statistically independent, which turns the joint density into a product of the individual ones:

The independence assumption is, strictly, false — heat and vibration in an engine are correlated. It is made anyway, and it works, because what matters is the ranking of points by probability rather than the probability being right.

Why a product catches things a single feature cannot

Multiplying is what makes the method sensitive. Suppose an engine's heat is on the high side — something one engine in ten does — and its vibration is high too, one in twenty. Neither number is alarming alone. Together:

$$ p(x_1)\,p(x_2) = \tfrac{1}{10} \times \tfrac{1}{20} = \tfrac{1}{200}, $$

and a one-in-two-hundred engine is worth looking at. Each additional feature multiplies another number below 1 into the product, so a point that is mildly unusual in several respects at once ends up with a very small $p(\vec{x})$ — which is exactly the kind of failure a human inspector would miss.

The algorithm

1. Choose $n$ features $x_j$ that you think might be indicative of anomalous examples.
2. Fit the parameters $\mu_1, \ldots, \mu_n$ and $\sigma_1^2, \ldots, \sigma_n^2$ from the training set. Vectorized, the means are just $\vec{\mu} = \frac{1}{m}\sum_i \vec{x}^{(i)}$.
3. Given a new example, compute $p(\vec{x}) = \prod_j p(x_j; \mu_j, \sigma_j^2)$ and declare an anomaly if $p(\vec{x}) < \epsilon$.

There is no iteration and no gradient descent anywhere — step 2 is closed-form.

A worked example

Two features, with parameters already fitted, and the threshold set at $\epsilon = 0.02$:

$$ \mu_1 = 5,\; \sigma_1 = 2 \qquad\text{and}\qquad \mu_2 = 3,\; \sigma_2 = 1 . $$

Neither individual factor looks damning — $0.027$ and $0.054$ are small but not absurd. It is their product, $0.001458$, that is thirteen times below the threshold. That is the mechanism of §5.2 doing its job on real numbers.

Evaluating it, and choosing $\epsilon$

The importance of a single number

So far nothing has said whether the system is any good, or where $\epsilon$ should sit. Developing any learning algorithm — choosing features, tuning thresholds — is far easier when each change produces one number you can compare. That requires some labelled data, which seems to contradict the whole premise; the resolution is that you need very few labels, and only for evaluation, never for fitting.

Label the examples you do know about: $y = 1$ for anomalous, $y = 0$ for normal. Then:

• the training set is normal examples only ($y = 0$), and is what $\mu_j, \sigma_j^2$ are fitted from — a stray anomaly or two in there does little harm;
• the cross-validation and test sets are mostly normal but contain the handful of known anomalies, and are used to tune $\epsilon$ (and the feature choices) and then to report the result.

How to split data you have almost none of

Ng's worked case: 10,000 good engines and 20 flawed ones.

The second row is for when labelled anomalies are very few. It costs you the thing a test set buys: because $\epsilon$ and the features were tuned on the same 20 anomalies that report the score, the reported score is optimistic — a higher risk of overfitting, and you should say so when quoting the number.

Which metric

On the cross-validation set, turn the density into a prediction and score it:

Score it — but not with accuracy — with 2,000 normal engines and 10 flawed ones, predicting "normal" every time scores $99.5\%$ and catches nothing. The metrics that survive a skew like that are the ones from model development: true/false positives and negatives, precision and recall, and $F_1$. Sweep $\epsilon$ over a range, compute $F_1$ on the cross-validation set for each, and keep the best.

Anomaly detection or supervised learning?

Both use labelled anomalies. The question of which to use is decided by how many you have and whether the future will look like the past:

Fraud and spam are the pair worth remembering. Spam is supervised: there are millions of labelled spam messages and tomorrow's spam looks much like today's. Fraud is anomaly detection: the profitable frauds are the new ones, and a classifier trained on last year's schemes is trained on exactly the schemes that no longer work.

The one-line difference. Anomaly detection models $p(\vec{x})$ — the density of normal data — and thresholds it. Supervised learning models $p(y \mid \vec{x})$ — the boundary between labelled classes. One asks "is this like the data I have seen?", the other asks "which class is this?"

Beyond the independent Gaussians. The product model above assumes the features do not interact. When they do, the standard upgrade is a multivariate Gaussian, $\vec{x} \sim \mathcal{N}(\vec{\mu}, \Sigma)$ with a full covariance matrix, which scores a point by its Mahalanobis distance $D_M^2 = (\vec{x}-\vec{\mu})^{\mathsf{T}}\Sigma^{-1}(\vec{x}-\vec{\mu})$ and so can flag a point that is unremarkable in every single feature but sits far off the correlation ridge. Other variants replace the density model entirely — one-class SVM, isolation forest, or an autoencoder flagging large reconstruction error $\lVert \vec{x} - \hat{\vec{x}} \rVert^2$. All of them keep the same two-part shape: a score for normality, and a threshold tuned on a few labelled failures.

Where this goes next

That completes the unsupervised pair: k-means groups unlabelled data, anomaly detection models it densely enough to say what falls outside. Both take a cloud of $\vec{x}$ with no $y$ and extract something usable from its geometry alone.

The next subject in the course keeps the "no explicit labels" flavour but changes the object of study completely:

• Recommender systems work from a matrix with most of its entries missing — users by items, filled in only where someone rated something. Collaborative filtering learns a feature vector per item and per user at the same time, from nothing but those sparse ratings, and the learned item features turn out to place similar items near each other so that "related items" falls out as a distance computation.
• After that, reinforcement learning drops the dataset altogether: there is no fixed set of examples, only an agent, a sequence of states, and rewards that arrive late.

Backwards from here: model development has the precision/recall and $F_1$ machinery §8.3 leans on, and clustering is the other half of this track.