TransWikia.com

Isolation Forest Score Function Theory

Data Science Asked by Samyak Shah on February 27, 2021

I am currently reading this paper on isolation forests. In the section about the score function, they mention the following. For context, $h(x)$ is definded as the path length of a data point traversing an iTree, and $n$ is the sample size used to grow the iTree.

The difficulty in deriving such a score from $h(x)$
is that while the maximum possible height of iTree grows
in the order of $n$, the average height grows in the order of
$log(n)$. Normalization of $h(x)$ by any of the above terms
is either not bounded or cannot be directly compared.

So herein lies my first question. What do they mean that the normalization of $h(x)$ by any of the above terms is either not bounded or cannot be directly compared? The final score function in this paper is given by

$$s(x,n)=2^{-frac{E(h(x))}{c(n)}}$$

where

$$c(n)=2H_{n-1}-2(n-1)/n$$

is the average path length of an unsuccessful search from BST Theory. Note how they are taking the expectation of the path. So in that case we are averaging all the values anyway, so why can we not use the growth of the average height of the tree? Additionally they don’t even mention the analytical form of average height here, which from what I gather is $2sqrt{pi n}$ reference, though I have not read this reference thoroughly and may be mistaken.

Am I missing something here?

One Answer

I'm not certain on your first question; the paper does seem poorly written in this part. They seem to be arguing that taking just $E(h(x))/n$ or $E(h(x))/log n$ are inappropriate. The former tends to zero regardless of $x$, but the latter should be reasonable. Indeed, since $c(n)sim 2log n$, it's not far off from what they end up doing. (Exponentiation pushes the scores into the range $[0,1]$ which is nice, and using the more exact $c(n)$ calibrates things better for "(c) if all the instances return $sapprox 0.5$, then the entire sample does not really have any distinct anomaly.")

The rest of the confusion seems to be stemming from what set we're averaging over. In the isolation forest paper, the averaging is of the depths of (the leaf containing) $x$ over multiple trees in the isolation forest. In the other reference, the average is of the height of all binary trees on $n$ nodes.

Answered by Ben Reiniger on February 27, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP