Evaluating Real-time Anomaly Detection Algorithms - the Numenta Anomaly Benchmark

In plain words

Software that watches a live stream of numbers, such as server load or a sensor reading, has to raise a flag as the data arrives, without seeing the future. Most benchmarks test detectors on a fixed file, and the usual scores ignore timing: a detector that flags a problem early earns no more than one that flags it late. This paper sets out a benchmark for that streaming case.

The benchmark is a collection of labelled time series, some real and some made up. Around each labelled anomaly it opens a window. A detection inside the window scores better the earlier it comes, detections far from any window count against the detector, and a window with no detection also counts against it. The scores are rescaled so that a perfect detector gets 100 and a null control gets 0. The authors use the benchmark to compare several open-source detectors.

TL;DR

• The Numenta Anomaly Benchmark (NAB) pairs labelled streaming data with a score designed for real-time detection §II.
• Each anomaly gets a window; the earliest detection inside it earns a score that falls off across the window, and detections outside windows are penalised §II.B §II.C.
• Scores are normalised between a perfect and a null detector eq. 4.
• Author-reported Table I, standard profile: Numenta HTM 64.7, Twitter ADVec 47.1, Etsy Skyline 35.7 tab. I.
• Several constants and the scoring details differ from the code, so read Paper vs code before implementing.

Problem

Real-time detectors must process each point as it arrives and decide without looking ahead; batch evaluation does not capture this §I. Standard classification metrics (TP, FP, TN, FN) do not reward early detection, so they do not reflect the value of catching a problem before it is visible §II.B. Benchmarks built for static datasets do not adequately capture the requirements of streaming applications, and the authors state that no benchmark adequately tests and scores real-time detectors §I [abstract].

Method

Benchmark data §II.A. The dataset holds 58 files. Each file is a time series of (timestamp, scalar value) rows, with 1,000 to 22,000 rows per file. The files include real data from several domains (IT metrics, sensors, social media) and some artificial files, with and without anomalies §II.A fig. 1. Labels were made by hand under a documented procedure, and a label-combining algorithm produced the ground truth §II.A, fn. 1.

Probation and windows §II.B fig. 2. The first 15% of each file is a probationary period, which the detector may use to learn but which is not scored. For each labelled anomaly the authors define a window centred on the label. Its length is 10% of the file length divided by the number of anomalies in that file. The authors tested window sizes from 5% to 20% and found the final score insensitive to the choice; 10% is their convenient default §II.B.

Per-detection weight §II.C eq. 1. A detection at relative position y gets the value

σ(y) = (A_TP − A_FP) · 1 / (1 + e^(5y)) − 1

where y = 0 at the right edge of the window and y = −1 at the left edge, and y > 0 lies after the window. The bounds are 0 ≤ A_TP, A_TN ≤ 1 and −1 ≤ A_FP, A_FN ≤ 0. The curve is flat-topped near the left edge and drops through zero at the right edge; past the window it approaches −1 fig. 3.

Score of one file §II.B §II.C eq. 2. Only the earliest detection inside each window is a true positive; later detections in the same window are ignored §II.B. Every detection outside all windows is a false positive, scored by its distance past the previous window §II.C. A window with no detection is a false negative, with score A_FN. The raw file score is the sum over detections plus A_FN times the count of missed windows eq. 2.

Corpus score eq. 3 eq. 4. The corpus raw score is the sum of the file scores eq. 3. The normalised score rescales it so that a perfect detector (all true positives, no false positives) gets 100 and a null detector gets 0 eq. 4.

Application profiles §II.B §II.C. Three profiles weight the four outcomes differently: standard, reward low false positives, and reward low false negatives. The paper says the profile weights are set so that random detections made 10% of the time score zero on average on the standard profile, and it does not give the numeric values. See Hyperparameters.

Threshold §III §IV. Each detector outputs an anomaly score in [0, 1]. The threshold is tuned on the full corpus, under the constraint that a single fixed number is used for all data files §IV.

Controls §III. The null detector outputs a constant score of 0.5. The perfect detector outputs only true positives, at the start of each window. The random detector outputs a random score between 0 and 1.

# Raw NAB score of one data file at one threshold  [eq. 1] [eq. 2]
# Input:  scores (N,) in [0, 1]; windows: list of (first, last) row indices
#         weights: tp, fp, fn weights of one application profile
# Output: raw score (float)

def raw_score(scores, windows, threshold, weights):
    # Rows in the probationary period are never scored  [§II.B] [fig. 2]
    # Code caps this at 750 rows  [code: nab/sweeper.py#L94-L98]
    cut = min(floor(0.15 * len(scores)), 0.15 * 5000)
    # Detections: rows at or above the threshold, after the cut
    detected = [i for i in range(cut, len(scores))
                if scores[i] >= threshold]
    in_window = set()
    total = 0.0
    for first, last in windows:
        in_window.update(range(first, last + 1))
        # Only the earliest detection in a window earns a score  [§II.B]
        hits = [i for i in detected if first <= i <= last]
        if not hits:
            # A window with no detection is a false negative  [eq. 2]
            total -= weights.fn
            continue
        # Position y: 0 at the right edge, -1 at the left edge  [eq. 1]
        # Code puts the last row at -1/width  [code: nab/sweeper.py#L165]
        width = last - first + 1
        y = -(last - hits[0] + 1) / width
        # Code divides by sigma(-1) so the best true positive is worth 1
        # [code: nab/sweeper.py#L137] [code: nab/sweeper.py#L167]
        total += weights.tp * sigma(y) / sigma(-1)
    # Detections outside every window are false positives  [§II.C]
    # Code scores -1 before the first window and beyond y = 3
    # [code: nab/sweeper.py#L54-L56] [code: nab/sweeper.py#L174]
    for i in detected:
        if i not in in_window:
            total += weights.fp * false_positive_sigma(i, windows)
    return total


# Corpus score and normalised NAB score  [eq. 3] [eq. 4]
def normalised_score(raw_total, raw_perfect, raw_null):
    # raw_total, raw_perfect, raw_null: sums over all files  [eq. 3]
    # Scale so the perfect detector is 100 and the null detector is 0  [eq. 4]
    return 100 * (raw_total - raw_null) / (raw_perfect - raw_null)

sigma(y) in the pseudocode is eq. 1 with A_TP = 1 and A_FP = −1, which is the form the code implements: 2σ(−5y) − 1 sweeper.py.

Hyperparameters

Results

Author-reported, on NAB v1.0 with the algorithms and profiles described above. Each detector's parameters were tuned to give its best score tab. I, note a. The random detector is not exactly 0 because of the optimisation step tab. I, note b.

Perfect detector: 100 on every profile by construction eq. 4. Twitter AnomalyDetectionTs is absent from the table: it failed on some files §III.

Analysis. HTM is best overall, and Skyline and ADVec are well above chance on all three profiles §IV-A. Skyline gains the most under reward-low-FN. On the 365,558-row corpus, Skyline flags 1,161 rows as anomalous, against 387 for HTM and 612 for ADVec, which explains why its score drops most under reward-low-FP §IV-B. Figures 4 to 6 illustrate early detection: HTM detects a temporal anomaly that the other detectors miss fig. 5, and HTM detects a change three hours earlier than Skyline and ADVec fig. 6.

Paper vs code

The code is numenta/NAB at ea702d75cc2258d9d7dd35ca8e5e2539d71f3140, the repository the paper links [cover note]. Its owner is Numenta, the authors' company [title page].

• Right edge of a window. The paper puts y = 0 at the right edge, where σ = 0 eq. 1 §II.C. The code uses −(last − i + 1)/width, so the last row of a window gets −1/width sweeper.py. For a 100-row window that is about 0.025 of credit, not 0.
• True-positive normalisation. The code divides the TP value by σ(−1) ≈ 0.98661, so the best possible TP is worth exactly the TP weight [code: nab/sweeper.py#L137] sweeper.py. Eq. 1 has no such division.
• False positives past a window. The paper says y = 1 is "past the right edge" but gives no distance §II.C. The code measures (i − R_prev)/(W_prev − 1), so y = 1 falls one window width past the edge sweeper.py. It also scores a detection before the first window as −1 [code: nab/sweeper.py#L174] and any y above 3.0 as −1 sweeper.py. None of this is in the paper.
• Probationary cap. The paper gives 15% fig. 2. The code uses min(floor(0.15 · N), 0.15 · 5000), so files longer than 5,000 rows are capped at 750 rows sweeper.py. The same formula is in nab/util.py#L25-L29.
• Unused TN weight. profiles.json sets a tn weight in every profile, but the sweeper reads only tp, fp and fn sweeper.py. The paper says TNs make no score contribution fig. 3.
• Threshold search. The paper describes a hill-climbing search §IV. The optimiser instead scores every observed value as a candidate threshold, sorts, and keeps the best optimizer.py.
• Window construction. The code takes windowLength/2 with Python 3 true division, so a window can start or end on a fractional row index for odd lengths labeler.py. I did not run this path to see what happens.
• Table I vs the repo. Table I gives Numenta HTM 64.7 and Random 16.8. The repo README gives HTM 70.5–69.7 for NuPIC 1.0 README.md and 70.1 for NuPIC v0.5.6 README.md, and Random 11.0 [code: README.md#L52]. ADVec (47.1, 33.6, 53.5) and Skyline (35.7, 27.1, 44.5) agree with the paper README.md README.md. config/thresholds.json has a different HTM entry, 46.63 standard thresholds.json. Treat Table I as the paper's numbers, not a value the current code reproduces.
• Licence. LICENSE.txt is MIT LICENSE.txt. The paper says the HTM implementation is AGPL §III. That is NuPIC, not this repository.

Pitfalls

• Missing constants. The paper does not give numeric values for A_TP, A_FP, A_FN or A_TN, or for any profile. The code's values (fp 0.11, 0.22; fn 2.0) are the only numeric source. Cross-check: the Fig. 3 total of 0.6909 is reproduced with TP weight 1 and FP weight 0.11, the code's standard value, using the three FP values of −1.0, −0.8093 and −1.0 and the TP value 0.9999 shown in the figure fig. 3. This check is my own arithmetic.
• Probation cap. A 22,000-row file gets 750 unscored rows, not 3,300. This matters for the longest files. The paper does not mention the cap.
• Right edge. Last-row credit is non-zero in the code, so an implementation that follows eq. 1 literally will score the same detections slightly lower.
• Window size is per file. The window depends on the count of anomalies in that file. Two files with the same length but different counts get different windows.
• Earliest detection only. Later detections inside a window earn nothing, and they are not counted as false positives either §II.B.
• Threshold is global. A single number is used for all files of a detector, so the total score hides how each file behaves §IV.
• Data licence unchecked. The repository's MIT licence covers the code. I found no licence statement for the files under data/ or labels/ in the repository, so their reuse terms are unverified. Do not republish the data from this card.
• Detector code is mixed. Some detectors in nab/detectors ship their own licence files (for example, skyline/SKYLINE_LICENSE.md). Check each detector's licence before copying code.
• Dataset size is inconsistent. The paper gives 365,551 rows in §II.A and 365,558 in §IV-B.
• Negative scores. Scores are normalised by the null detector, so a detector below the null scores below 0. The current config/thresholds.json has negative standard-profile scores for some detectors, for example skyline at −33.2 thresholds.json.

Lineage

• Builds on: none stated.
• Compared against: Numenta HTM §III (references 17 to 19); Etsy Skyline §III (reference 7); Twitter AnomalyDetectionVec and AnomalyDetectionTs §III (references 21 and 22); null, random and perfect controls §III.
• Superseded by: not known from content already in this wiki.