Anomaly detection using surprisals

This paper proposes a unified anomaly detection framework that identifies outliers as observations with unusually low model probability by converting them into univariate surprisal scores and estimating their tail probabilities using either empirical or extreme-value methods, demonstrating robustness against model misspecification in complex datasets.

The Gist

Imagine you are a security guard at a very fancy, crowded party. Your job is to spot the "anomalies"—the people who don't belong, the ones acting strangely, or the ones who are out of place.

In the world of data science, this is called Anomaly Detection. Usually, guards (algorithms) use simple rules: "If someone is taller than 7 feet, they are an anomaly," or "If someone is wearing a tuxedo to a beach party, they are an anomaly."

The problem with these old rules is that they are often too rigid. They might miss a spy who is wearing a normal t-shirt but standing in a spot where no one else stands (a "low-density gap"). Or, they might flag a tall person who actually belongs there because they are a basketball player.

Rob Hyndman and David Frazier have proposed a new, smarter way to be a security guard. They call it the "Surprisal" Framework.

Here is how it works, broken down into simple concepts:

1. The Concept of "Surprisal" (The "Wait, What?" Meter)

Instead of measuring how tall someone is or what they are wearing, this new method measures how surprised the party host would be to see that person.

• High Density (Common): If 500 people are wearing red shirts, seeing another red shirt isn't surprising. The "Surprisal" score is low.
• Low Density (Rare): If only one person is wearing a neon green hat, seeing them is very surprising. The "Surprisal" score is high.

In math terms, they calculate a number called Surprisal (which is just the negative log of the probability).

• Low Surprisal = "Oh, I've seen this before. Totally normal."
• High Surprisal = "Whoa! I've never seen this before! This is weird!"

2. The Magic Trick: Turning a Complex Party into a Simple Line

The hardest part of spotting anomalies is that the data can be messy. Maybe you are looking at a 3D map of a city, or a list of 100 different health metrics for a patient. It's hard to know what "weird" looks like in 100 dimensions.

The authors' genius move is to flatten everything.
They take every single data point, calculate its "Surprisal" score, and turn the whole complex party into a single line of numbers (a univariate distribution).

Now, instead of asking, "Is this 100-dimensional point weird?", you just ask: "Is this Surprisal score on the far right end of the line?"
If the score is way out in the tail (the extreme right), it's an anomaly.

3. The "Guessing Game" (Handling Mistakes)

Here is the real kicker: You don't need to know the exact rules of the party to do this.

Imagine you are guessing the rules of the party.

• Scenario A: You guess the party is for "Garden Lovers." You expect everyone to be wearing floral shirts.
• Scenario B: The party is actually for "Rock Stars," and everyone is wearing leather jackets.

If you use your "Garden Lover" guess to calculate Surprisal, you might think the leather jackets are weird. But here is the magic: Even if your guess is wrong, the ranking of "weirdness" often stays the same.

The paper proves that as long as your "Surprisal Meter" agrees on which things are the most surprising (even if it gets the exact numbers wrong), you can still find the anomalies.

They offer two ways to set the "Alarm Threshold":

• Method 1: The "Counting" Method (Empirical)
  You just look at the line of Surprisal scores you have. If a score is higher than 99% of the others, you flag it. It's like saying, "This is in the top 1% of weirdness." This works great if you have a lot of data.
• Method 2: The "Crystal Ball" Method (Extreme Value Theory)
  If you don't have enough data to count, you use a mathematical crystal ball (called a Generalized Pareto Distribution). You look at the top few "weirdest" scores and use math to predict how far out the tail goes. This helps you catch anomalies even if you haven't seen them before.

4. Real-World Examples from the Paper

Example 1: French Mortality Rates (The Time Travelers)
They looked at death rates in France over 200 years.

• The Anomaly: They didn't just look for "high death rates." They looked for years where the pattern of death was unexpectedly strange compared to the model.
• The Result: The "Surprisal" alarm went off exactly during historical disasters: the 1832 Cholera outbreak, the Franco-Prussian War, and the Spanish Flu. The model didn't need to know about wars or germs; it just knew that the death patterns were "surprising" compared to the usual trend.

Example 2: Cricket Players (The Defensive Batsmen)
They analyzed cricket players to see who was "weird."

• The Anomaly: They found a player, Jimmy Anderson, who had an unusually high number of "not outs" (getting to bat without being dismissed).
• The Twist: He wasn't a great batter. He was actually a "tail-ender" (a weak player). But because he was so good at defending (staying at the crease without scoring), he stayed in the game longer than expected.
• Why it matters: A simple rule might have said, "He's not a great batter, so he's normal." But the Surprisal model said, "Wait, the pattern of his survival is statistically weird compared to the model." It caught a subtle anomaly that other methods missed.

The Big Takeaway

The old way of finding anomalies was like trying to find a needle in a haystack by only looking for needles that are gold. If the needle is silver, you miss it.

This new Surprisal method is like measuring how much the haystack shakes when you pull something out.

• It doesn't matter if you think the needle is gold or silver (model misspecification).
• It doesn't matter if the haystack is in a barn or a field (complex data).
• If the haystack shakes violently, you know you found something unusual.

In short: This paper gives us a robust, flexible, and mathematically sound way to say, "This doesn't fit the pattern," even when we aren't 100% sure what the pattern should look like. It turns the complex art of finding needles into the simple science of measuring surprise.

Technical Summary

Here is a detailed technical summary of the paper "Anomaly detection using surprisals" by Rob J. Hyndman and David T. Frazier.

1. Problem Statement

Anomaly detection is a critical task in statistics and machine learning, yet existing methods suffer from significant limitations:

• Ad hoc nature: Many methods rely on arbitrary rules without a solid theoretical foundation.
• Strong assumptions: Methods often assume specific distributions (e.g., Normality) that rarely hold in practice.
• Tail bias: Most techniques focus on extreme tail events, failing to detect "inlier" anomalies. These are observations that occur in low-density gaps between modes of a multimodal distribution or in other low-probability regions that are not necessarily extreme in magnitude.
• Dimensionality issues: Distance-based methods struggle with skewed, heavy-tailed, or high-dimensional data.

The authors propose a unified framework to define an anomaly as an observation with unusually low probability under a specified model, regardless of whether that model is perfectly specified.

2. Methodology: The Surprisal Framework

The core innovation is the conversion of a potentially complex multivariate anomaly detection problem into a univariate problem using surprisal.

A. Definition of Surprisal

For an observation $y_i$ drawn from a distribution with generalized density $f$, the surprisal $s_i$ is defined as:
$$s_i = -\log f(y_i)$$

• Interpretation: High density (typical values) yields low surprisal; low density (unlikely values) yields high surprisal.
• Generality: $f$ can be a probability density function (continuous), probability mass function (discrete), or a mixture (using Dirac delta functions).

B. Anomaly Scoring

Instead of flagging observations based on raw density or distance, the method calculates an anomaly score $p_i$, defined as the probability of observing a surprisal at least as large as the observed $s_i$:
$$p_i = \Pr(S \ge s_i) = 1 - G(s_i^-)$$
where $G(s)$ is the cumulative distribution function (CDF) of the random variable $S = -\log f(Y)$.

• An observation is flagged as an anomaly if $p_i < \alpha$ (where $\alpha$ is a chosen significance level).
• This approach naturally handles "inlier" anomalies (e.g., between modes) because it relies on the density of the observation, not its distance from a mean.

C. Estimation Strategies

Since the true distribution $F$ is usually unknown, the authors propose three approaches to estimate $p_i$, with the latter two being robust to model misspecification:

1. Theoretical: Compute $p_i$ directly from the assumed model $F$ (assumes $F$ is correct).
2. Empirical: Estimate $p_i$ as the proportion of observed surprisals $\{s_1, \dots, s_n\}$ that are greater than or equal to $s_i$.
3. Extreme Value Theory (EVT): Fit a Generalized Pareto Distribution (GPD) to the largest surprisal values to estimate the tail probabilities.

3. Key Theoretical Contributions

The paper provides rigorous theoretical justification for the robustness of the Empirical and GPD approaches under model misspecification.

A. Empirical Estimator Robustness

• Condition for Validity: The authors establish Assumption 2.1: The true surprisal $S$ and the fitted surprisal $\hat{S}$ must be related by a strictly increasing transformation on the upper tail (i.e., they must preserve the ordering of extreme values).
• Result: If this ordering is preserved, the empirical estimator provides a valid uniform confidence band for the true tail probabilities (via the Dvoretzky–Kiefer–Wolfowitz inequality).
• Implication: The model does not need to capture the exact shape of the tail, only the relative ordering of low-density regions.

B. Extreme Value Theory for Surprisals

• Convergence: The authors prove (Theorem 3.1) that under broad conditions (Sub-Gaussian, Sub-exponential, or Polynomial tails of the surprisal distribution), the maximum surprisal $M_n$ converges to a Generalized Extreme Value (GEV) distribution.
• GPD Approximation: Consequently, the upper tail of the surprisal distribution can be approximated by a GPD.
• Misspecification Safety:
  • If the true data has heavier tails than the assumed model, the GPD fit may be slow to converge but remains consistent.
  • If the assumed model has heavier tails than the true data, the GPD fit remains consistent with the lighter tail.
  • Practical Heuristic: It is safer to assume a heavier-tailed model (e.g., Student-t) than a lighter one (e.g., Normal) to avoid slow convergence and inaccurate detection.

C. Conditional Distributions

The framework extends to conditional models (e.g., regression). By fixing conditioning variables $X$, the surprisal $S = -\log f(Z|X)$ remains univariate and iid, allowing the same theoretical guarantees to apply.

4. Experimental Results and Applications

A. Simulation Studies

• Normal vs. t-distribution: When data is generated from a Normal distribution but modeled with a $t(4)$ distribution (and vice versa), both the Empirical and GPD methods accurately estimate tail probabilities, whereas the "Assumed Distribution" method fails.
• Bivariate Gamma vs. Normal: In a bivariate Gamma setting modeled with a Normal distribution, the Empirical method performs perfectly (due to preserved ranking). The GPD method performs well if the reference distribution has heavier tails (Student-t) but poorly if it has lighter tails (Normal). This confirms the "safer to overestimate tail heaviness" heuristic.

B. Real-World Applications

1. French Mortality Rates (1816–1999):
   • Data: 172 time series of mortality rates by age and sex.
   • Method: Used conditional distributions and GPD to detect anomalies.
   • Result: Successfully identified historical anomalies corresponding to cholera outbreaks (1832, 1849), the Franco-Prussian war (1870), the Paris Commune (1871), WWI, the Spanish Flu (1918), and WWII (1940).
2. Test Cricket "Not Outs":
   • Data: 97,649 innings of cricket batting data.
   • Method: Modeled "not outs" using a Binomial distribution with a Generalized Additive Model (GAM) for the probability of dismissal. Used GPD on surprisals to find anomalies.
   • Result: Identified English bowler Jimmy Anderson as an anomaly. While his "not out" rate wasn't extreme in isolation, the statistical model (accounting for the discrete nature of innings and career progression) flagged his specific combination of high innings count and high number of not-outs as statistically surprising. This highlights the method's ability to detect context-specific anomalies that simple ratios miss.

5. Significance and Conclusion

• Unified Framework: The paper unifies anomaly detection for univariate, multivariate, discrete, continuous, and mixed data types under a single probabilistic definition.
• Robustness to Misspecification: The most significant contribution is demonstrating that anomaly detection does not require a perfectly specified model. As long as the ordering of low-density regions is preserved (Empirical) or the tail behavior follows extreme value theory (GPD), the method remains effective.
• Handling "Inlier" Anomalies: Unlike distance-based methods, this approach detects anomalies in low-density gaps between modes, not just in the extreme tails.
• Practical Implementation: The authors provide the weird R package, making the methodology accessible. The approach is computationally efficient (linear in sample size for surprisal calculation) and scalable.

In summary, Hyndman and Frazier propose a paradigm shift from "distance-based" or "tail-only" anomaly detection to a probability-based surprisal framework. By decoupling the model specification from the tail probability estimation, they achieve a method that is theoretically grounded, interpretable, and robust to the inevitable misspecification found in real-world data.