Anomaly detection using surprisals

Deze paper introduceert een unificerend raamwerk voor anomaliedetectie dat observaties met een ongewoon lage waarschijnlijkheid identificeert via hun surprisal en de bijbehorende uitzonderlijkheid berekent met behulp van robuuste schatters voor de staart van de surprisalverdeling, zoals een empirische methode en een Generalized Pareto Distribution-schatter.

De kern

Stel je voor dat je een enorme bibliotheek hebt met boeken. De meeste boeken zijn heel gewoon: romans, reisgidsen, kookboeken. Maar af en toe duikt er een raar boek op. Misschien is het een kookboek dat alleen recepten bevat voor het eten van schoenen, of een reisgids voor een planeet die niet bestaat.

In de wereld van data noemen we deze rare boeken anomalieën (afwijkingen). De vraag is: hoe vind je die rare boeken snel en betrouwbaar, zonder dat je elke pagina van elke boek moet lezen?

Dit is wat Rob Hyndman en David Frazier in hun paper doen. Ze hebben een nieuwe, slimme manier bedacht om deze rare boeken te vinden, zelfs als je niet precies weet wat de "normale" bibliotheek eruit moet zien.

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen.

1. Het oude probleem: De "Ad-hoc" jagers

Vroeger was het vinden van afwijkingen vaak een beetje gissen. Mensen gebruikten simpele regels, zoals: "Als een getal te ver van het gemiddelde ligt, is het raar."

• Het probleem: Dit werkt goed als je alleen naar de uiterste randen kijkt (de "staart" van de verdeling). Maar wat als er een raar boek ligt in het midden van de bibliotheek? Bijvoorbeeld een kookboek tussen de romans, maar niet helemaal aan de rand? De oude methodes missen deze vaak. Ze kijken alleen naar de uiterste hoeken en vergeten de "gaten" tussen de normale boeken.

2. De nieuwe oplossing: De "Verwonderings-meter" (Surprisal)

De auteurs introduceren een nieuw concept: Surprisal (verwondering).
Stel je voor dat je een boek pakt en zegt: "Hoe verrast zou ik zijn als ik dit boek in deze bibliotheek tegenkom?"

• Veel voorkomende boeken (zoals een standaard roman) geven weinig verwondering. Je zegt: "Oh, ja, dat zie ik vaak." (Lage score).
• Zeldzame boeken geven veel verwondering. Je zegt: "Wauw, wat doet dit boek hier?" (Hoge score).

In de wiskunde noemen ze dit de negatieve log-dichtheid. Laten we het gewoon "Verwonderings-score" noemen.

• De kernidee: In plaats van te kijken of een getal "ver weg" is, kijken we gewoon naar hoe onwaarschijnlijk het is. Hoe onwaarschijnlijker, hoe hoger de verwondering.

3. De slimme truc: Van complex naar simpel

Het mooie van deze methode is dat ze een complex probleem (bijvoorbeeld: "Is deze combinatie van leeftijd, geslacht en sterftecijfer raar?") omtoveren naar een heel simpel probleem.

Stel je voor dat je een enorme, ingewikkelde 3D-kaart hebt van de bibliotheek. Het is moeilijk om daar een punt op te vinden dat "raar" is.
De auteurs zeggen: "Laten we elke boek omzetten in één enkel getal: de Verwonderings-score."
Nu hebben we geen ingewikkelde 3D-kaart meer, maar gewoon een lange lijst met getallen (de scores).

• De vraag wordt dan: "Is deze score in de top 1% van de meest verrassende scores?"
  Dit maakt het probleem veel makkelijker op te lossen, of het nu gaat om één getal of duizenden tegelijk.

4. Twee manieren om de "raarheid" te meten

Je weet misschien niet precies welke boeken er in de bibliotheek liggen (je hebt geen perfecte lijst). Je moet het dus schatten. De auteurs bieden twee manieren om dit te doen, zelfs als je schatting niet perfect is:

Manier A: De "Telling" (Empirisch)
Je kijkt naar alle boeken die je nu hebt. Je telt: "Hoeveel boeken zijn er minstens zo verrassend als dit ene boek?"

• De kracht: Zelfs als je denkt dat de bibliotheek er anders uitziet dan hij echt is, werkt dit vaak nog steeds. Zolang je de volgorde van de rare boeken goed hebt (dus dat je weet welke boeken meer verrassend zijn dan andere), werkt het. Het is alsof je zegt: "Ik weet niet precies hoeveel boeken er zijn, maar ik weet zeker dat dit boek in de top 10 van rare boeken zit."

Manier B: De "Extremen-expert" (GPD)
Soms heb je niet genoeg boeken om alles te tellen, of zijn de aller-raarste boeken zo extreem dat je ze niet kunt tellen. Dan gebruiken ze een wiskundige techniek uit de "Extreme Waarde Theorie".

• De analogie: Stel je voor dat je de windkracht meet. Je weet dat er stormen komen die nog nooit zijn gezien. Je kijkt naar de laatste 10% van de stormen en past een patroon daarop toe om te voorspellen hoe extreem de volgende kan zijn.
• Het geheim: Zelfs als je het verkeerde model gebruikt om de "normale" boeken te beschrijven, werkt deze methode vaak nog steeds goed, mits je niet denkt dat de rare boeken minder extreem zijn dan ze echt zijn.
  • Tip van de auteurs: Het is veiliger om te denken dat de rare dingen extreem zijn, dan dat je denkt dat ze "normaal" zijn. Als je denkt dat een orkaan een zacht briesje is, ben je in de problemen. Als je denkt dat een briesje een orkaan is, maak je je misschien een beetje zorgen, maar je wordt niet verrast.

5. Wat hebben ze bewezen? (Met voorbeelden)

Ze hebben hun methode getest op echte data:

1. Franse sterftecijfers: Ze keken naar sterftecijfers per leeftijd en geslacht. Hun methode vond automatisch de jaren met grote rampen, zoals de cholera-uitbraken (1832, 1849) en de Eerste Wereldoorlog (1914-1918). Zelfs als je het verkeerde wiskundige model gebruikt om de sterftecijfers te beschrijven, vonden ze deze rampen toch.
2. Cricket: Ze keken naar honkballers (cricketers) die heel vaak "niet uit" (not out) waren. De methode vond een speler (Jimmy Anderson) die heel vaak niet uit bleef, niet omdat hij een slechte speler was, maar omdat hij als laatste in het team sloeg en vaak de partij overleefde. Het model zag dit als een "anomalie" in de context van het spel, wat een interessant verhaal opleverde.

Conclusie: Waarom is dit geweldig?

Deze paper zegt eigenlijk: "Je hoeft niet perfect te zijn om rare dingen te vinden."

• Flexibiliteit: Je kunt een "foutief" model gebruiken (bijvoorbeeld denken dat alles normaal verdeeld is, terwijl het niet zo is), en je vindt de rare dingen toch.
• Veiligheid: Het is beter om te denken dat de wereld "extreem" is dan dat je denkt dat alles "normaal" is.
• Eenvoud: Ze maken een ingewikkeld, multidimensionaal probleem (veel variabelen tegelijk) om tot één simpele vraag: "Is dit getal verrassend genoeg?"

Kortom: Het is een nieuwe, robuuste manier om de "raarste boeken" in de bibliotheek van de data te vinden, zonder dat je de hele bibliotheek eerst perfect hoeft te begrijpen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Anomaly detection using surprisals" van Rob J. Hyndman en David T. Frazier, vertaald en samengevat in het Nederlands.

Titel: Anomaliedetectie met behulp van surprisals

Auteurs: Rob J. Hyndman en David T. Frazier (Monash University)
Datum: 11 maart 2026

---

1. Het Probleem

Bestaande methoden voor anomaliedetectie lijden vaak aan twee fundamentele tekortkomingen:

1. Ad-hoc regels: Veel methoden gebaseerd zijn op heuristieken zonder een solide theoretische onderbouwing.
2. Sterke aannames: Methoden die wel een theoretische basis hebben, maken vaak sterke aannames over de onderliggende verdeling (bijv. normaliteit), wat in de praktijk zelden opgaat.
3. Focus op staarten: Traditionele methoden richten zich vaak alleen op uiterste waarden (staartgebeurtenissen) en missen "inlier"-anomalieën. Dit zijn waarnemingen die zich in gebieden met lage dichtheid bevinden tussen modi (bijv. in multimodale verdelingen), maar niet noodzakelijk in de uiterste staarten.

Het doel van dit artikel is een unificerend kader te bieden dat anomalieën definieert als waarnemingen met een ongewoon lage waarschijnlijkheid onder een (mogelijk verkeerd gespecificeerd) model, zonder afhankelijk te zijn van de specifieke vorm van de verdeling.

2. Methodologie

De kern van de voorgestelde aanpak is het gebruik van surprisals (verrassingswaarden) om het detectieprobleem te reduceren tot een eendimensionaal probleem.

A. Definitie van Surprisal

Voor een waarneming $y_i$ uit een verdeling met verdelingsfunctie $F$ en gegeneraliseerde dichtheidsfunctie $f$, wordt de surprisal $s_i$ gedefinieerd als:
$$s_i = -\log f(y_i)$$
Een hoge surprisal-waarde duidt op een onwaarschijnlijke (en potentieel anomalie) waarneming. Dit transformeert een complex multivariaat probleem naar een univariate verdeling van surprisals.

B. Anomalie-score

In plaats van direct de kans op de waarneming te berekenen, wordt de anomalie-score $p_i$ gedefinieerd als de kans op het observeren van een surprisal die minstens zo groot is als de geobserveerde $s_i$:
$$p_i = \Pr(S \ge s_i) = 1 - G(s_i^-)$$
waarbij $G$ de cumulatieve verdelingsfunctie (CDF) is van de surprisals $S$. Waarnemingen met $p_i < \alpha$ worden gemarkeerd als anomalieën. Dit biedt een gecontroleerde kans op vals-positieven.

C. Schatting van Staartkansen

Omdat de ware verdeling $F$ zelden bekend is, worden drie benaderingen voorgesteld om de surprisals en hun staartkansen te schatten:

1. Theoretisch: Gebruik de veronderstelde verdeling $F$ direct (gevoelig voor misspecification).
2. Empirisch: Gebruik de empirische verdelingsfunctie van de geobserveerde surprisals.
3. Extreme Waarde Theorie (EVT): Pas een Generalized Pareto Distribution (GPD) aan op de grootste surprisal-waarden om de staart te modelleren.

De auteurs benadrukken dat de empirische en GPD-methoden robuust zijn tegen misspecification van het onderliggende model, zolang de rangschikking van de surprisals in de staart behouden blijft.

3. Belangrijkste Bijdragen en Theoretische Resultaten

Robuustheid tegen Misspecification

De paper toont aan dat de methode effectief blijft zelfs als het model $F$ verkeerd is gespecificeerd, mits aan bepaalde voorwaarden wordt voldaan:

• Voor de empirische methode: De ware en de geschatte surprisals moeten in de staart gerelateerd zijn door een strikt stijgende transformatie (Assumptie 2.1). Dit betekent dat het model de locatie van de lage-dichtheidsgebieden correct moet identificeren, zelfs als de vorm van de staart niet exact overeenkomt.
• Voor de GPD-methode: De paper bewijst dat onder brede voorwaarden (sub-Gaussisch, sub-exponentieel of polynoom-gedrag van de surprisal-verdeling), de maximale surprisal convergeert naar een verdeling binnen de familie van extreme waarden (Gumbel, Fréchet of Weibull). Hierdoor kan een GPD worden gebruikt om staartkansen te schatten.

Theoretische Garanties

• Lemma 2.1: Biedt eindige-steekproef betrouwbaarheidsintervallen voor de empirische schatter via de Dvoretzky–Kiefer–Wolfowitz ongelijkheid, mits de rangschikking in de staart behouden blijft.
• Stelling 3.1: Bewijst de convergentie van de maximale surprisal naar extreme-waardeverdelingen onder drie verschillende aannames over de zwaarte van de staart.
• Insight over Staartzwaarte: Het is veiliger om een model aan te nemen met zwaardere staarten dan de werkelijkheid (over-schatting) dan om een model met lichtere staarten aan te nemen (onderschatting). Onderschatting leidt tot trage convergentie en onnauwkeurige detectie, terwijl overschatting relatief weinig kosten met zich meebrengt.

4. Resultaten en Toepassingen

Simulaties

• Univariate Normaliteit: Zelfs wanneer data uit een $N(0,1)$ verdeling komt maar een $t(4)$ verdeling wordt gebruikt voor de berekening van surprisals (en vice versa), leveren de empirische en GPD-methoden nauwkeurige staatkansschattingen op. De directe berekening via het verkeerde model faalt echter.
• Bivariate Gamma: Bij bivariate data (Gamma-verdeling) die gemodelleerd wordt met een bivariate normale verdeling, presteert de GPD-methode met een Student-t referentieverdeling (zwaardere staart) beter dan met een normale referentieverdeling (lichtere staart). Dit bevestigt de theorie dat het veiliger is om uit te gaan van zwaardere staarten.

Toepassing 1: Franse Sterftecijfers

• Data: Mortaliteitsdata per leeftijd en geslacht (1816–1999).
• Resultaat: De methode detecteerde anomalieën die overeenkwamen met historische gebeurtenissen zoals cholera-uitbraken (1832, 1849), de Frans-Pruisische oorlog (1870), de Commune van Parijs (1871), de Eerste Wereldoorlog (1914-1918), de Spaanse griep (1918) en de Tweede Wereldoorlog (1940).
• Voordeel: De methode kon complexe, conditionele patronen (leeftijd, geslacht, tijd) detecteren die niet direct zichtbaar waren in ruwe data.

Toepassing 2: Testcricket (Niet-uit innings)

• Data: Batting-statistieken van honderden spelers.
• Doel: Spelers vinden met een ongewoon hoog percentage "not out" innings.
• Resultaat: De methode identificeerde Jimmy Anderson als een anomalie. Hoewel zijn percentage "not out" op zich niet extreem leek in de ruwe data, was het in de context van het statistische model (Binomiaal met logit-link, rekening houdend met het aantal innings) een significante afwijking. Dit illustreert hoe de methode anomalieën kan vinden die niet extreem zijn in de marges, maar wel in de context van het model.

5. Betekenis en Conclusie

De paper introduceert een flexibel en theoretisch onderbouwd kader voor anomaliedetectie dat de volgende voordelen biedt:

• Onafhankelijkheid van verdelingsvorm: Werkt voor univariate, multivariate, discrete, continue en gemengde data.
• Robuustheid: Effectief zelfs bij aanzienlijke misspecification van het onderliggende model, zolang de rangschikking in de staart behouden blijft.
• Interpreteerbaarheid: Biedt een enkele maatstaf (de surprisal-kans) voor onwaarschijnlijkheid.
• Efficiëntie: De berekening is lineair in de steekproefgrootte; de GPD-aanpassing is snel.

De auteurs concluderen dat door de specificatie van een werkend model te scheiden van de schatting van de staatkansen (via empirische of extreme-waarde methoden), een systeem ontstaat dat zeer goed presteert in complexe, real-world scenario's. De methoden zijn geïmplementeerd in het R-pakket weird.