Anomaly detection methods

What Makes a Point Anomalous?

WHY this matters: In real systems, anomalies are rare (<1% of data) but high-impact. A fraudulent transaction costs money; a network breach compromises security. We need automated methods because human inspection doesn't scale.

Method 1: Statistical (Gaussian) Anomaly Detection

Derivation from First Principles

WHAT: Model normal data as following a multivariate Gaussian distribution. Points with very low probability density are anomalies.

WHY: If normal behavior clusters around a mean with some spread, points far from this cluster are suspicious. The Gaussian captures "typical" in terms of mean and variance.

HOW:

Step 1 - Fit the Distribution: Given training data $\{x^{(1)}, .., x^{(m)}\}$ where $x^{(i)} \in \mathbb{R}^n$:

$\mu = \frac{1}{m}\sum_{i=1}^{m} x^{(i)}$

Why this step? The mean $\mu$ is our best estimate of "center of normal behavior" under squared loss.

$\Sigma = \frac{1}{m}\sum_{i=1}^{m} (x^{(i)} - \mu)(x^{(i)} - \mu)^T$

Why this step? The covariance $\Sigma$ captures how features vary together. It tells us the "shape" of normal data—which directions have high/low variance.

Step 2 - Compute Probability Density: For a new point $x$, compute:

$p(x) = \frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}} \exp\left(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)\right)$

Why this formula?

• The term $(x-\mu)^T\Sigma^{-1}(x-\mu)$ is the Mahalanobis distance: how far $x$ is from $\mu$ measured in units of $\Sigma$.
• The exponential decays as distance increases: far points → low probability.
• The normalization constant ensures $\int p(x)dx = 1$.

Step 3 - Flag Anomalies: If $p(x) < \epsilon$, flag $x$ as anomaly.

Why this step? We set a threshold $\epsilon$ based on desired false-positive rate. Lower $\epsilon$ = stricter detection = fewer false alarms but may miss some anomalies.

Equivalently, flag if Mahalanobis distance $> k$ where $k = \sqrt{-2\ln(\epsilon \cdot (2\pi)^{n/2}|\Sigma|^{1/2})}$.

New observation: $x = [80, 90]^T$

Step 1: Compute Mahalanobis distance: $x - \mu = [50, 40]^T$ $\Sigma^{-1} = \frac{1}{25 \cdot 36 - 100}\begin{bmatrix}36 & -10\\-10 & 25\end{bmatrix} = \frac{1}{800}\begin{bmatrix}36 & -10\\-10 & 25\end{bmatrix}$

Why this step? We invert the covariance to measure distance in the natural coordinate system of the data.

$(x-\mu)^T\Sigma^{-1}(x-\mu) = [50, 40] \cdot \frac{1}{800}\begin{bmatrix}36 & -10\\-10 & 25\end{bmatrix}\begin{bmatrix}50\\40\end{bmatrix}$ $= \frac{1}{800}[50, 40] \cdot [1400, -500 + 1000] = \frac{1}{800}[1400 \cdot 50 + 500 \cdot 40] = \frac{9000}{800} = 112.5$

Step 2: Compute $p(x)$: $|\Sigma| = 900- 100 = 800$ $p(x) = \frac{1}{2\pi\sqrt{800}}\exp(-112.5/2) \approx \frac{1}{177.6}\exp(-56.25) \approx 10^{-26}$

Why this step? The probability is astronomically small—this server is behaving nothing like normal.

Step 3: If $\epsilon = 10^{-5}$, this is anomaly (possible CPU/memory leak).

Method 2: Isolation Forest

Derivation from First Principles

WHAT: Build random decision trees that isolate points. Anomalies are easier to isolate (require fewer splits) than normal points.

WHY: Normal points are "deep in the crowd"—you need many questions to separate them. Anomalies are "out alone"—one or two questions isolate them.

HOW:

Step 1 - Build Isolation Trees: For each tree:

1. Randomly select feature $q$ and split value $p$ between min/max of $q$
2. Partition data: $\{x: x_q < p\}$ vs $\{x: x_q \geq p\}$
3. Recurse until points isolated or max depth reached

Why random splits? We're not trying to classify—just partition space. Random splits avoid overfitting to "normal" structure and naturally isolate outliers quickly.

Step 2 - Compute Path Length: For a point $x$, its path length $h(x)$ is the number of splits to reach a leaf in a tree.

Why this step? Short path = easy to isolate = likely anomaly. Normal points require more splits to separate from neighbors.

Step 3 - Aggregate Over Trees: Average path length over $t$ trees: $\bar{h}(x)$

Anomaly score: $s(x) = 2^{-\bar{h}(x)/c(n)}$

where $c(n) = 2H(n-1) - 2(n-1)/n$ is the average path length for $n$ points (for normalization).

Why this formula?

• $c(n)$ is the expected depth of an unsuccessful search in a Binary Search Tree—our baseline for "normal"
• We normalize by $c(n)$ so scores are comparable across dataset sizes
• The exponential $2^{-\cdot}$ maps to [0,1]: scores near 1 = anomaly, near 0 = normal

If $s(x) > 0.6$, typically flag as anomaly.

Normal transaction: $45 at 2pm in user's city → average path length $\bar{h} = 7.2$ Why? Many similar transactions exist; takes ~7 splits to isolate from neighbors.

Anomalous transaction: $9,999 at 3am in foreign country → $\bar{h} = 2.1$ Why? Very few transactions like this; isolated in ~2 splits (maybe one amount, one on location).

Scoring: $c(1000) \approx 2\ln(1000) = 18.4$ $s(\text{normal}) = 2^{-7.2/18.4} \approx 0.77$ $s(\text{anomaly}) = 2^{-2.1/18.4} \approx 0.92$

Decision: 0.92 > 0.6 threshold → flag for fraud review.

Method 3: One-Class SVM

Derivation from First Principles

WHAT: Find a hypersphere (or hyperplane) that tightly encloses normal data in feature space. Points outside are anomalies.

WHY: We want a decision boundary that separates normal data from the rest of space, maximizing the margin to capture "normal" compactly.

HOW:

Step 1 - Kernel Mapping: Map data to high-dimensional space via kernel $K(x, x') = \phi(x)^T\phi(x')$. Common choice: RBF kernel $K(x,x') = \exp(-\gamma\|x-x'\|^2)$.

Why this step? In high dimensions, data that's not linearly separable input space often becomes separable. The kernel trick avoids explicit computation.

Step 2 - Optimization Problem: Find hyperplane $w^T\phi(x) = \rho$ that separates data from origin with maximum margin:

$\min_{w,\rho,\xi} \frac{1}{2}\|w\|^2 - \rho + \frac{1}{\nu m}\sum_{i=1}^{m}\xi_i$ subject to: $w^T\phi(x^{(i)}) \geq \rho - \xi_i, \quad \xi_i \geq 0$

Why this objective?

• $\frac{1}{2}\|w\|^2$: minimize (maximize margin $1/\|w\|$)
• $-\rho$: push hyperplane away from origin (larger normal region)
• $\frac{1}{\nu m}\sum \xi_i$: allow some slack for outliers in training data
• $\nu \in (0,1]$: controls trade-off (upper bound on fraction of outliers)

Step 3 - Decision Function: For new point $x$: $f(x) = \text{sign}\left(\sum_{i=1}^{m}\alpha_i K(x, x^{(i)}) - \rho\right)$

where $\alpha_i$ are Lagrange multipliers from solving dual problem.

Why this step? $f(x) < 0$ means $x$ is on the "origin side"—outside the normal region, hence anomaly.

where support vectors ($\alpha_i > 0$) define the boundary.

Normal packet: size=512, duration=0.5s, protocol=HTTP → $f(x) = +0.23 > 0$ ✓ Why? Within the learned boundary of typical HTTP traffic.

Suspicious packet: size=6535, duration=0.01s, protocol=ICMP → $f(x) = -0.87 < 0$ ✗ Why? Max-size ICMP with tiny duration is unlike normal; kernel distance to all support vectors is large, pushing $f(x)$ negative.

Method 4: Autoencoder-Based Detection

Derivation from First Principles

WHAT: Train a neural network to compress then reconstruct normal data. Anomalies have high reconstruction error because the network never learned to encode them.

WHY: If a network learns the manifold of normal data, it can faithfully reproduce normal points but struggles with anomalies (they're off-manifold).

HOW:

Step 1 - Architecture: Encoder: $h = f_e(x)$ maps $x \in \mathbb{R}^n$ to code $h \in \mathbb{R}^k$ where $k \ll n$ Decoder: $\hat{x} = f_d(h)$ reconstructs from code

Why bottleneck? Forcing compression to low $k$ ensures the network learns essential structure, not memorizes every point.

Step 2 - Training Objective: Minimize reconstruction loss on normal data: $L = \frac{1}{m}\sum_{i=1}^{m}\|x^{(i)} - f_d(f_e(x^{(i)}))\|^2$

Why squared error? It's the maximum likelihood estimate under Gaussian noise assumption. Other losses (absolute, perceptual) work too.

Step 3 - Anomaly Detection: For test point $x$, compute: $\text{Reconstruction Error: } E(x) = \|x - \hat{x}\|^2$

If $E(x) > \tau$ (threshold set on validation set), flag as anomaly.

Why this works? The autoencoder's weights encode $p(\text{normal})$. When shown anomaly, the decoder tries to "hallucinate" the nearest normal point, yielding large error.

Normal board: Input pixel patterns match training → $E(x) = 120$ (low error, reconstructs faithfully) Why? The network learned features of solder joints, traces, components. It can regenerate them accurately.

Defective board: Missing component, short circuit → $E(x) = 3400$ (high error) Why? The defect is out-of-distribution. The decoder tries to "imagine" a component there (from learned prior), but actual pixels differ drastically.

Decision: If $\tau = 500$, defect flaged (3400 > 500).

Comparing Methods

Method	Strengths	Weaknesses	Best For
Gaussian	Fast, interpretable, works well if data ~Gaussian	Assumes Gaussian, breaks with multi-modal or skewed data	Low-dimensional numerical data, when you need explain-ability
Isolation Forest	No distribution assumption, handles high-dim, fast	Harder to interpret, needs tuning tree count	High-dimensional data, mixed feature types

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, is note ka core idea bahut simple hai - hume machine ko sikhana hai ki "normal" kaisa dikhta hai, aur phir jo bhi cheez normal se bahut door hai, use anomaly (outlier) mark kar do. Jaise fraud detection mein, network security mein, ya factory mein defective products dhoondhne mein - yeh sab jagah rare events hote hain jo common cheezon se zyada important hote hain. Problem yeh hai ki humare paas anomalies ke labels nahi hote, kyunki woh itne rare hote hain (1% se bhi kam), isliye hume sirf unlabeled normal data se hi "normal ka pattern" seekhna padta hai.

Ab statistical method mein kya karte hain - hum maan lete hain ki normal data ek Gaussian distribution follow karta hai. Iske liye do cheezein calculate karte hain: mean ($\mu$) jo batata hai ki normal data ka center kahan hai, aur covariance ($\Sigma$) jo batata hai ki data ka shape kaisa hai - matlab kaunse directions mein zyada spread hai. Phir jab koi naya point aata hai, hum uski probability density $p(x)$ nikalte hain. Yahan Mahalanobis distance ka concept aata hai - yeh simple straight-line distance nahi hai, balki data ke natural spread ko consider karke distance measure karta hai. Agar yeh distance zyada hai toh probability bahut kam ho jaati hai, aur agar $p(x) < \epsilon$ (threshold) toh hum use anomaly bol dete hain.

Yeh important isliye hai kyunki real-world mein human inspection scale nahi karti - lakhon transactions ya servers ko manually check karna impossible hai. Server example dekho: normal CPU 30% aur memory 50% tha, lekin ek server 80% CPU aur 90% memory dikha raha hai - iski probability $10^{-26}$ nikli, matlab yeh point normal behavior se bilkul match nahi karta. Yahi automated detection ka power hai. Aur $\epsilon$ threshold ko adjust karke aap decide kar sakte ho ki kitna strict rehna hai - kam $\epsilon$ matlab kam false alarms lekin kuch real anomalies miss ho sakti hain. Yeh trade-off samajhna practical applications ke liye bahut zaroori hai.