Depth estimation in half-space trees and feature range formulation for novelty detection

Tree-based methods such as Isolation Forest (iForest) and Half-Space Trees (HS-Trees) are widely used for unsupervised anomaly detection due to their efficiency and scalability. However, the classical depth estimator $c(n)$, originally derived for iForest under random partitioning assumptions, becomes inadequate for alternative tree constructions such as HS-Trees, where splits are deterministic. In this paper, we formally analyse the generative process of HS-Trees, establish the theoretical foundation for their expected depth, and prove that a modified estimator $c'(n)$ better captures their structural properties. We derive both the exact expression and an efficient approximation of $c'(n)$, showing analytically and empirically that the approximation converges and remains stable. This formulation enables accurate depth estimation in HS-Tree--based models.In the second part of the paper, we address the problem of initial feature range estimation, which plays a crucial role in detecting novel data points that, by definition, lie outside the training distribution. We show that the choice of initial feature ranges can significantly influence the model's ability to capture out-of-distribution behaviour.Through analytical discussion and empirical experiments, we highlight the sensitivity of novelty detection performance to these design choices and propose improvements that lead to more robust and accurate detection in real-world scenarios.