A Theoretical Characterization of the Good Properties of Extremely Randomized Trees for Random Forest-Distance Computation

Ensembles of Extremely Randomized Trees (ERT), initially introduced for supervised scenarios, have been shown to represent surprisingly effective models also in unsupervised contexts, for example, for the detection of anomalies (i.e., Isolation Forests) or for defining Random Forest-distances. In this paper, we focus on this last field, providing a theoretical characterization to support the excellent empirical behaviors shown by ERTs in the definition of RF-distances. We start by assuming the existence, in a given domain, of a proper representation, i.e., a vectorial representation fulfilling the Compactness Hypothesis given by Arkadev and Braverman in 1967. Then, given the "true" distance between a pair of objects, we show that it is possible to derive a bound on the approximation guaranteed by an ERT-based RF-distance with respect to such true measure. In words, we show that it is possible to compute a constant c such that, if a pair of objects are ε-close in the true distance, then, with high probability, they are (c · ε )-close also in the ERT-based RF-distance.