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

Area of Science:

• Machine Learning
• Data Mining
• Theoretical Computer Science

Background:

• Extremely Randomized Trees (ERT), initially designed for supervised tasks, demonstrate efficacy in unsupervised contexts like anomaly detection and Random Forest (RF) distance calculations.
• Existing empirical evidence suggests ERT-based RF distances perform well, but a theoretical foundation is lacking.

Purpose of the Study:

• To provide a theoretical characterization supporting the empirical success of ERTs in defining RF distances.
• To derive a bound on the approximation error of ERT-based RF distances compared to true object distances.

Main Methods:

• Assumed the existence of a proper vectorial representation satisfying the Compactness Hypothesis (Arkadev and Braverman, 1967).
• Derived a theoretical bound on the approximation error for ERT-based RF distances relative to the true distance metric.

Main Results:

• Established a theoretical guarantee for ERT-based RF distances.
• Demonstrated that if two objects are $\epsilon$-close in true distance, they are $(c \cdot \epsilon)$-close in ERT-based RF distance with high probability, for a computable constant $c$.

Conclusions:

• The study provides theoretical validation for using ERTs to compute RF distances in unsupervised settings.
• The derived bound offers a quantifiable understanding of the approximation quality of ERT-based RF distances.