Exercises — Anomaly detection methods

The rule is: flag as anomaly only if $p(x)<ϵ$ (strict — equality would count as normal). Here $p(x)=3\times 10^{-4}=30\times 10^{-5}$, and $ϵ=10^{-5}$. Since $30\times 10^{-5}>1\times 10^{-5}$, we have $p(x)>ϵ$. Answer: NORMAL. A larger density means the point sits where data is common.

First, what is $\bar{h}$? Each point is dropped down every tree in the forest and we record its path length $h$ in each tree separately — say tree-lengths $2,3,2,4,\dots$ Because random splits make any single tree noisy, we average those raw path lengths across all $t$ trees to get $\bar{h}(x)$; that averaging is exactly why we write the bar. A stable small $\bar{h}$ (short in tree after tree) is the fingerprint of an anomaly. Now the score direction. From $s(x)=2^{-\bar{h}(x)/c(n)}$: when $\bar{h}$ is small, the ratio $\bar{h}/c(n)$ is close to $0$, the exponent $-\bar{h}/c(n)$ is close to $0$, so $s\to 2^0=1$. Hence short average path ⇒ score near 1.

• $s(A)=0.83>0.6$ → anomaly, and higher score ⇒ shorter $\bar{h}$ ⇒ easier to isolate.
• $s(B)=0.41<0.6$ → normal. Answer: A is the anomaly and was easier to isolate.

The rule: $f(x)<0$ ⇒ the point is on the origin side, outside the learned normal region ⇒ anomaly. (Equality $f(x)=0$ means the point sits on the boundary and is treated as normal by our strict convention.) Here $f(x)=-0.12<0$. Answer: ANOMALY.

In 1-D the Mahalanobis distance squared is $\frac{(x-\mu {)}^2}{{\sigma }^2}$ (the matrix ${\Sigma }^{-1}$ becomes $1/{\sigma }^2$). $\frac{(16-10{)}^2}{4}=\frac{36}{4}=9.$ Answer: $9$ (equivalently a Mahalanobis distance of $\sqrt{9}=3$, i.e. "3 standard deviations out").

Normalizer: $\frac{1}{\sqrt{2\pi \cdot 4}}=\frac{1}{\sqrt{8\pi }}\approx \frac{1}{5.013}\approx 0.19947$. Exponent: $-\frac{9}{2}=-4.5$, and $e^{-4.5}\approx 0.011109$. $p(16)\approx 0.19947\times 0.011109\approx 2.216\times 10^{-3}.$ Answer: $\approx 2.22\times 10^{-3}$.

For a diagonal covariance, ${\Sigma }^{-1}=\left[\begin{array}{cc}1/4& 0\\ 0& 1/9\end{array}\right]$, and the quadratic form simplifies to a sum: $\frac{(x_1-{\mu }_1{)}^2}{{\sigma }_1^2}+\frac{(x_2-{\mu }_2{)}^2}{{\sigma }_2^2}=\frac{16}{4}+\frac{9}{9}=4+1=5.$ Answer: $5$. Notice each feature is judged in its own spread — the $x_1$ deviation of 4 is only "2 units" of its std, the $x_2$ deviation of 3 is "1 unit" of its std.

How to get $H_{255}$ without adding 255 fractions. The harmonic number obeys a well-known, extremely accurate approximation $H_k\approx \ln k+\gamma +\frac{1}{2k},\gamma \approx 0.5772(\text{the Euler–Mascheroni constant}).$ The $\ln k+\gamma$ part is the leading behaviour; the $+\frac{1}{2k}$ term is a small correction, and the error after it is only about $\frac{1}{12k^2}$ — for $k=255$ that error is under $2\times 10^{-6}$, i.e. negligible for our 4-digit answer. So a student can compute $H_{255}$ on any calculator, no summing required: $H_{255}\approx \ln 255+0.5772+\frac{1}{510}\approx 5.5413+0.5772+0.00196\approx 6.1205,$ which rounds to the true $H_{255}\approx 6.1179$ within the accuracy we need. Now $c(256)$: $c(256)=2(6.1179)-\frac{2\cdot 255}{256}=12.2358-1.9922=10.2436\approx \mathrm{10.24.}$ This is where the $10.24$ comes from — the harmonic term $2H_{n-1}$ minus the correction $2(n-1)/n$, not the crude $2\ln n$ shortcut. Now the score. Exponent: $-\frac{4.0}{10.24}=-0.390625$. $s(x)=2^{-0.390625}=e^{-0.390625\ln 2}=e^{-0.27077}\approx \mathrm{0.7628.}$ Answer: $c(256)\approx 10.24$ and $s(x)\approx 0.763$. Since $0.763>0.6$, this point would be flagged.

Step 1 — center: $x-\mu =[50,40{]}^T$. Step 2 — determinant: $|\Sigma |=25\cdot 36-10\cdot 10=900-100=800$. Step 3 — inverse: ${\Sigma }^{-1}=\frac{1}{800}\left[\begin{array}{cc}36& -10\\ -10& 25\end{array}\right]$. Step 4 — apply. First ${\Sigma }^{-1}(x-\mu )$: $\frac{1}{800}\left[\begin{array}{c}36\cdot 50-10\cdot 40\\ -10\cdot 50+25\cdot 40\end{array}\right]=\frac{1}{800}\left[\begin{array}{c}1400\\ 500\end{array}\right].$ Then dot with $(x-\mu {)}^T=[50,40]$: $\frac{1}{800}(50\cdot 1400+40\cdot 500)=\frac{70000+20000}{800}=\frac{90000}{800}=\mathrm{112.5.}$ Answer: $112.5$. A Mahalanobis distance of $\sqrt{112.5}\approx 10.6$ — enormously far, hence the near-zero density in the parent note.

The off-diagonal $+10$ means CPU ($x_1$) and memory ($x_2$) tend to rise together, so "normal" lies along a tilted ellipse leaning up-and-to-the-right. To make the comparison fair, we normalize each move by its squared Euclidean displacement $\Vert x-\mu {\Vert }^2$, which is what "per unit of raw distance" means. Move A — along correlation: $d_A=[10,10{]}^T$ (equal rise in both, the natural direction).

• Euclidean squared: $10^2+10^2=200$.
• Mahalanobis: ${\Sigma }^{-1}{d}_A=\frac{1}{800}[36\cdot 10-10\cdot 10,-10\cdot 10+25\cdot 10]=\frac{1}{800}[260,150]$; form $=\frac{1}{800}(10\cdot 260+10\cdot 150)=\frac{4100}{800}=5.125$.
• Ratio $=5.125/200=0.02563$. Move B — across correlation: $d_B=[10,-10{]}^T$ (CPU up, memory down — breaks the pattern), same raw length.
• Euclidean squared: $10^2+10^2=200$ (identical raw distance ✓).
• Mahalanobis: ${\Sigma }^{-1}{d}_B=\frac{1}{800}[36\cdot 10-10\cdot (-10),-10\cdot 10+25\cdot (-10)]=\frac{1}{800}[460,-350]$; form $=\frac{1}{800}(10\cdot 460+(-10)\cdot (-350))=\frac{4600+3500}{800}=\frac{8100}{800}=10.125$.
• Ratio $=10.125/200=0.05063$. Answer: for the same raw step (both length $\sqrt{200}$), the across-correlation move B has almost double the Mahalanobis cost ($10.125$ vs $5.125$), so its anomaly-per-unit-raw-distance ratio ($0.0506$ vs $0.0256$) is larger. Breaking the correlation is disproportionately suspicious.

Using the same harmonic approximation as L2.4, $H_{999}\approx \ln 999+0.5772+\frac{1}{1998}\approx 6.9068+0.5772+0.0005\approx 7.4845$ (true value $H_{999}\approx 7.4845$ — the correction terms make it dead-on). $c(1000)=2(7.4845)-\frac{2\cdot 999}{1000}=14.9690-1.998=12.9710\approx \mathrm{12.97.}$ Now the scores: $s(P)=2^{-2.1/12.97}=2^{-0.16191}=e^{-0.16191\cdot 0.69315}=e^{-0.11223}\approx 0.8938$. $s(Q)=2^{-9.5/12.97}=2^{-0.73246}=e^{-0.50772}\approx 0.6019$. Answers: $s(P)\approx 0.894$ (>0.6 ⇒ anomaly), $s(Q)\approx 0.602$ (just >0.6 ⇒ anomaly, barely). Key correction: the parent's box says "$c(n)\approx 2\ln n$", which would give $2\ln (1000)\approx 13.8$ — not the $18.4$ stated there (that number is simply wrong; $2\ln 1000=13.816$). And even $13.8$ is only the crude asymptotic; the exact value is $c(1000)\approx 12.97$. Always use the exact harmonic formula for real scoring.

Choose (b) Isolation Forest.

• Gaussian density estimation assumes normal data is a single unimodal blob described by one $\mu$ and one $\Sigma$. With multi-modal legit behaviour (e.g. two clusters: online micro-payments and in-store large payments), the single Gaussian smears a fat blob covering the empty valley between clusters — assigning high $p(x)$ to the sparse middle. A fraud point landing there escapes detection. That is the Gaussian's failure mode: false negatives in inter-cluster gaps.
• Isolation Forest makes no distributional assumption; it just measures how quickly random splits isolate a point, so multiple clusters are fine and correlated non-Gaussian features are handled.
• Caveat: if you insisted on Gaussian, you'd upgrade to a Mixture of Gaussians (one blob per cluster) — but plain single-Gaussian loses here.

Fix: transform the feature to be more Gaussian before fitting — e.g. use $x^{\prime }=\log (x+c)$ (a log or Box-Cox transform). Why it works: the Gaussian density $p(x)$ decays symmetrically around $\mu$. A skewed feature has a fat right tail of legit values; the symmetric bell can't model that, so it treats big legit values as far-from-$\mu$ anomalies. Log-compressing the tail pulls large values inward, making the transformed distribution roughly bell-shaped, so $\mu$ and $\Sigma$ describe it faithfully. The decision rule $p(x^{\prime })<ϵ$ is then meaningful. Sanity: $\log$ maps $[1,10,100,1000]$ (spread 999) to $[0,1,2,3]$ (spread 3) — the tail is tamed while ordering is preserved.

Evaluate each detector separately, then combine.

• Gaussian says anomaly? Compare $p(x)=4\times 10^{-6}$ against $ϵ=10^{-5}=10\times 10^{-6}$. Since $4\times 10^{-6}<10\times 10^{-6}$, we have $p(x)<ϵ$ ✓ — Gaussian fires (calls it anomaly).
• Isolation Forest says anomaly? Rule is $s(x)>0.6$. Here $s(x)=0.52$, and $0.52<0.6$, so the condition is false — Isolation Forest does not fire (calls it normal).
• Combine with AND. The "AND" rule alerts only when both detectors say anomaly. Truth table: (True AND False) $=$ False. Answer: the combined rule does NOT fire — no alert. Interpretation: the "AND" strategy trades recall for precision — you get far fewer false alarms (both must agree), but this borderline point, which the density detector flagged, slips through because the forest disagreed. If missing frauds is costlier than false alarms, prefer an "OR" rule (fire if either agrees) instead.

Derivation. Start from $p(x)<ϵ$ with $D^2=(x-\mu {)}^T{\Sigma }^{-1}(x-\mu )$: $\frac{1}{(2\pi {)}^{n/2}|\Sigma {|}^{1/2}}\exp (-\frac{1}{2}{D}^2)<ϵ.$ Multiply both sides by the positive normalizer $(2\pi {)}^{n/2}|\Sigma {|}^{1/2}$ (positive ⇒ direction of $<$ unchanged): $\exp (-\frac{1}{2}{D}^2)<ϵ(2\pi {)}^{n/2}|\Sigma {|}^{1/2}.$ Take $\ln$ (increasing, preserves the inequality): $-\frac{1}{2}{D}^2<\ln (ϵ(2\pi {)}^{n/2}|\Sigma {|}^{1/2}).$ Multiply by $-2$ (negative ⇒ flip the inequality): $D^2>-2\ln (ϵ(2\pi {)}^{n/2}|\Sigma {|}^{1/2}).$ So $D>k$ with $k=\sqrt{-2\ln (ϵ(2\pi {)}^{n/2}|\Sigma {|}^{1/2})}$. ∎

Numeric ($n=2$, $|\Sigma |=800$, $ϵ=10^{-5}$). Here $(2\pi {)}^{n/2}=(2\pi {)}^1=6.28319$ and $|\Sigma {|}^{1/2}=\sqrt{800}=28.2843$. Inside the log: $ϵ\cdot 6.28319\cdot 28.2843=10^{-5}\cdot 177.715=1.77715\times 10^{-3}$. $\ln (1.77715\times 10^{-3})=-6.33186$. Then $-2\cdot (-6.33186)=12.6637$, so $k=\sqrt{12.6637}\approx \mathrm{3.559.}$ Comparison. The server point has Mahalanobis distance $D=\sqrt{112.5}\approx 10.607$. Since $10.607>3.559=k$, the point exceeds the threshold ⇒ ANOMALY. This is fully consistent with the parent's $p\approx 10^{-26}<ϵ$: the two views (density vs distance) agree. ✓

In 1-D, $Z=(x-\mu )/\sigma$ is standard normal, and Mahalanobis distance $=|Z|$. We want $P(\text{flag a normal point})=P(|Z|>k)=0.01$. From the standard-normal table, $P(|Z|>2.576)=0.01$, so the cutoff is $k=2.576$. Raw boundary values: $x=\mu \pm k\sigma =10\pm 2.576\cdot 2=10\pm 5.152$. Answer: cutoff Mahalanobis distance $k=2.576$; boundaries at $x\approx 4.848$ and $x\approx 15.152$. Points with $x<4.848$ or $x>15.152$ are flagged, giving $\approx 1\%$ false-positive rate on genuinely normal data.

Write $s=2^{-\bar{h}/c}$ with $c=c(n)>0$ fixed. Then $s=e^{-(\ln 2/c)\bar{h}}$. Differentiate w.r.t. $\bar{h}$: $\frac{ds}{d\bar{h}}=-\frac{\ln 2}{c}{e}^{-(\ln 2/c)\bar{h}}<0$ because $\ln 2>0$, $c>0$, and the exponential is always positive. A negative derivative everywhere ⇒ strictly decreasing. So larger $\bar{h}$ (harder to isolate, normal) gives smaller $s$; smaller $\bar{h}$ (easy to isolate, anomaly) gives larger $s$. ∎ Limits: as $\bar{h}\to 0$, $s\to 2^0=1$ (maximal anomaly). As $\bar{h}\to \infty$, $s\to 2^{-\infty }=0$ (maximally normal). Thus $s\in (0,1]$, and the special value $\bar{h}=c(n)$ gives $s=2^{-1}=0.5$ — the "as expected for average data" reference point.

(i) Classification. Our strict convention flags anomaly only if $f(x)<0$. Here $f(x)=0$ is not $<0$, so the point is treated as normal — it sits on the boundary, the very edge of the accepted region. (ii) What the ${\alpha }_i$ mean. Solving the dual gives one multiplier ${\alpha }_i$ per training point, and the decision function $f$ is built only from points with ${\alpha }_i>0$ — these are the support vectors, the points lying on or outside the boundary that actually pin it down. Deeply-interior "obviously normal" points have ${\alpha }_i=0$: they satisfy the margin constraint with room to spare, contribute nothing to the sum ${\sum }_i{\alpha }_{i}K(x,x^{(i)})$, and could be deleted without changing the boundary at all. So a test point at $f=0$ is, by construction, right at the level set carved out by the support vectors. (Sanity check on the $\nu$ role from the parent: the fraction of points that end up as support vectors — those with ${\alpha }_i>0$ — is bounded below by $\nu$, and $\nu$ upper-bounds the training-outlier fraction.) (iii) Why fragile. $f=0$ is a measure-zero knife-edge. A microscopic change in $x$, in the kernel width $\gamma$, or in the solved $\rho$ tips $f$ to a small $+$ or $-$, flipping the label. In deployment you therefore never trust the exact boundary: you add a small margin band $|f(x)|<\delta$