Research map / Learning theory and algorithms / Prediction and decision losses
Fast Hyperboloid Decision Tree Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends CART decision trees and random forests to the hyperboloid model by using homogeneous hyperplanes (geodesic decision boundaries) evaluated via inner products, avoiding Riemannian optimization and pairwise comparisons.
Problem
Hyperbolic classifiers often rely on Riemannian optimization or costly horosphere computations, making them slow and numerically unstable, while efficient decision-tree methods for hyperbolic embeddings are lacking.
Approach
Replace axis-parallel splits with homogeneous hyperplanes through the origin of Minkowski space, which intersect the hyperboloid in geodesic submanifolds; restrict candidates to single-axis rotations so each split is an O(1) sparse inner-product test, and compute midpoint angles in closed form.
Key results
- HyperDT had the highest micro-F1 in 28 of 36 dataset/dimension/sample-size combinations, with significant advantage over scikit-learn decision trees in 7 cases and over HoroRF in 27.
- HyperRF won 22 of 36 combinations, significantly outperforming scikit-learn random forests in 11 cases and HoroRF in 13.
- Runtime of HyperDT grows linearly with sample size while HoroRF grows quadratically; HyperDT is always faster than HoroRF but slower than scikit-learn by a constant factor.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use HyperDT instead of a scikit-learn decision tree | decision-tree classification · Gaussian, D=2, n=100 | micro-F1: 87.90 -> 89.10 | Helped |
| Use HyperRF instead of a scikit-learn random forest | random-forest classification · Gaussian, D=2, n=100 | micro-F1: 87.50 -> 90.70 | Helped |
| Use HyperDT instead of a scikit-learn decision tree | decision-tree classification · NeuroSEED, D=2, n=100 | micro-F1: 55.60 -> 56.60 | Helped |
| Use HyperRF instead of a scikit-learn random forest | random-forest classification · NeuroSEED, D=8, n=100 | micro-F1: 82.80 -> 79.50 | Hurt |
| Use HyperDT instead of a scikit-learn decision tree | decision-tree classification · Polblogs, D=2, n=979 | micro-F1: 70.35 -> 71.04 | Helped |
| Use HyperRF instead of a scikit-learn random forest | random-forest classification · Polblogs, D=2, n=979 | micro-F1: 71.65 -> 71.40 | Hurt |
| Use HyperDT instead of the strongest tested classifier | Gaussian mixture classification · D=4, 800 samples, 2 classes | micro-F1: 99.41 -> 99.30 | Hurt |
| Increase maximum tree depth (ablation) | HyperRF · Gaussian mixture classification | micro-F1 | Hurt |
| Use HyperRF rather than the other evaluated predictors | random-forest classification · Gaussian mixture classification, maximum-depth comparison | micro-F1 | Mixed |
| Use HyperDT instead of HoroRF | decision-tree classification · Classification benchmarks | runtime | Helped |
Surprising findings
- On 8-dimensional NeuroSEED data, scikit-learn random forests statistically outperformed HyperRF in all four sample sizes.
- The best model for NeuroSEED embeddings varied by dimensionality, which the authors note warrants further investigation.
Limitations
- Benchmarks are limited to shallow trees (depth <= 3) and 12-tree forests on small datasets (up to 800 samples) plus one 979-node graph dataset.
- Runtime comparisons to HoroRF are hardware-dependent since HoroRF is GPU-optimized and HyperRF is CPU-parallel; HyperRF may lack scikit-learn optimizations.
- Only classification is benchmarked in the main results; regression is implemented but not evaluated.
Experimental setup
Datasets: wrapped normal hyperbolic Gaussian mixtures NeuroSEED RNA embeddings (Greengenes / American Gut) Polblogs graph embeddings
Benchmarks: wrapped normal Gaussian mixtures NeuroSEED Polblogs
Metrics: micro-F1 macro-F1 AUPR runtime
Baselines: scikit-learn decision tree scikit-learn random forest HoroDT HoroRF hyperbolic SVM hyperbolic logistic regression
Builds on: CART random forests HoroRF scikit-learn
Closest papers by meaning
- Mixed-curvature decision trees and random forests (ICML 2025 · similarity 0.89)
- Random Laplacian Features for Learning with Hyperbolic Space (ICLR 2023 · similarity 0.88)
- Hyperbolic Embeddings of Supervised Models (NeurIPS 2024 · similarity 0.87)
- Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity (NeurIPS 2025 · similarity 0.86)
- Hyperbolic Dataset Distillation (NeurIPS 2025 · similarity 0.86)
- Robust Hyperbolic Learning with Curvature-Aware Optimization (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.