Fast Hyperboloid Decision Tree Algorithms

We thank you for your comments on the efficiency, ingenuity, and practicality of our method.

We have modified the paper to strengthen our conceptual contributions in response to your astute observations. Specifically, we have added a discussion of theoretical reasons to prefer geodesic boundaries and also added a discussion of more advanced decision tree algorithms, noting that the suboptimality of CART remains a concern in our model. We additionally added experiments showing HyperDT is more parsimonious than other decision trees (Section A.6.1) and added comparisons to other classifiers (A.6.2), other models of hyperbolic space (A.6.3), and a new WordNet classification benchmark (A.6.5). Although we have replaced the numerical approximation for midpoint angles with an analytic solution, we nonetheless carried out a midpoint ablation study in A.6.6. We now respond to your comments inline:

My primary concerns are related to the CART-like design employed in the paper. As CART is known for its top-down, greedy approach, it tends to yield suboptimal solutions [1]. It is essential to acknowledge that the proposed method may also encounter this suboptimal behavior due to its similarity to CART. For additional concerns, please refer to the questions section.

While the duration of the reply period limited us to adding comparisons against hyperbolic logistic regression and hyperbolic SVMs, HyperDT can be adapted to other decision tree algorithms besides CART. The decision to adapt CART was motivated by its widespread popularity, effectiveness in machine learning, and the desire to avoid confounding the comparison of predictors’ geometries by differences in optimization procedures. We have updated the related work section and conclusion to include a discussion of other decision tree frameworks and leave additional extensions for future work. We believe that, since Quant-BnB is based on axis-parallel splits, it is in principle possible to wed globally optimal optimization procedures with geodesic decision boundaries.

In Section 3.2, the authors mentioned that the interpretation of axis-aligned hyperplanes within the hyperboloid model is unclear. Can the authors provide a more detailed explanation of why the use of axis-aligned hyperplanes lacks clarity in this context? I am considering that any geodesic could potentially be represented by two axis-aligned or oblique planes, making the use of axis-aligned planes reasonable.

We have revised the discussion of geodesic decision boundaries in Sections 1.2, 3.2, and 5 to emphasize that, of the three classes of decision tree algorithms considered, ours is the only one that splits the space into topologically continuous subspaces closed under geodesic combinations—a property of axis-aligned decision splits one may take for granted in a proper Euclidean context. Additionally, we observe that, although it is possible to represent geodesics using a combination of planes, CART-based algorithms fit single hyperplanes at a time, creating hyperbolas. Specifically, “lacking clarity” can be refined to mean “not closed under geodesics”—it is possible for the shortest path between two points separated by an axis-parallel split to cross this decision boundary, which can limit the ability of learned splits to generalize.

Additionally, does the geodesic boundary offer advantages beyond classification scores and interpretation? One potential advantage I am considering is that geodesic trees may require fewer nodes compared to axis-aligned trees to achieve similar classification scores. Could the authors include metrics, such as the average number of nodes used in the experiments presented in Table 1, to support this claim?

We have added an experiment, detailed in Section A.6.1, on the effect of increasing the maximum depth of the tree on the accuracy of HyperRF, HoroRF, and Euclidean random forests. We found that, controlling for maximum depth, HyperRF was consistently at least as good as the other classifiers, but also that its advantage over other predictors was strongest at lower depths. This supports the theory that, as you suggest, geodesic splits are more parsimonious than Euclidean splits and, interestingly, horospherical splits as well.

We thank you for your support of our paper and your suggestions for further experiments.

We have added a more theoretical discussion of geodesic boundaries to the introduction, arguing that this is the first random forest method to maintain topological continuity and convexity of all decision areas after an arbitrary number of iterations. We have also performed a number of new experiments, including a comparison to hyperbolic and Euclidean versions of support vector machines and logistic regression classifiers, which is quite favorable to our method as well. We reply to your comments inline:

It is unclear why using geodesics as decision boundary is better than using horospheres as used in [1].

We note distinct characteristics of decision boundaries in different classifiers. Euclidean decision trees employ splits that can be extended indefinitely while preserving topological continuity and convexity. In contrast, HoroRF decision regions lack continuity and convexity, especially outside horospheres, where non-convex areas emerge, and the combination of two horospherical splits may result in separate exteriors. Axis-parallel hyperplanes can be extended continuously but lack convexity, allowing geodesics to cross decision boundaries. Geodesic partitions exhibit both convexity under geodesic combinations and topological continuity, aligning more closely with the properties of axis-parallel boundaries in Euclidean classifiers. The superior accuracy of HyperDT and HyperRF, compared to other decision tree-based classifiers, supports the effectiveness of geodesic boundaries in decision trees.

Although the main goal is to generalzie decision tree to hyperbolic space, the paper lacks some comparisions agaist previous classification methods likes hyperbolic logistic regression and hyperbolic SVM. Without sush comparision, it is not clear whether the proposed hyperbolic decision tree has enough advantages compared with other classifiers.

We have performed this comparison and wrote it up in Section A.6.2 of the Appendix. These results show HyperDT consistently outperformed both Euclidean and Hyperbolic versions of SVMs and logistic regression classifiers. Since HyperDT is a much simpler classifier than HyperRF, this is strong evidence that our methods outperform other existing hyperbolic classifiers.

We thank you for your support of our method and your close engagement with the mathematical details of our model.

We have taken your review into consideration and rewritten the sections of the paper and appendix dealing with parameterizing the decision boundaries. We hope that the new version is clearer, more detailed, and more general. In particular, we explicitly show how to parameterize decision boundaries to arbitrary dimensions. Please see sections 3.4 and A.2 for the fully revised description. We have also replaced the numerical approximation for midpoint angles with an analytic closed form, which is described in sections 3.3 and A.3. We will now respond to your comments inline:

Language in the description of Eq. (11) seems imprecise. "... the hyperplane parameterized by and will intersect at: [ Eq.(11)]". This seems to suggest there is only one point of intersection. I assume that the point characterized by Eq (11) is the closest point to the origin in said intersection?

(Please note that this is now equation 12 in the paper.)

You are correct to point out that we are choosing the closest point for this analysis, which can be done by setting all other dimensions to 0. This additionally reduces the computation to a 1-dimensional hyperbola, as shown in Figure 4 in the Appendix. We have changed the language in the paper and appendix to be clearer about this by adding the phrases “when all other dimensions are 0…” and “note that this is the point on the intersection of $\mathbf{P}(\theta)$ and $\mathbb{H}^{D,K}$ closest to the origin.”

We further hope that, by making the role of other dimensions (and specifically the u vectors) clearer, it will be clearer why it is natural to start parameterizing the geodesic submanifold by choosing the closest point to the origin.

As a general suggestion, it may be useful to the reader to have both Eq. (7) and Eq. (11) in Figure 1.

Because Equations 7 and 11 describe the specific axis-inclined hyperplanes used in HoroDT, whereas we wish for Figure 1 to deal with geodesic separators more generally, we have elected to keep Figure 1 as is. While it is true that the particular hyperplane drawn in Figure 1 is axis-inclined (hence the theta), we wish to keep the figure general to provide context and intuition for geodesics in general.

In the set up of Appendix A.2, a vector is defined. It is unclear exactly what this is. From the combined definition in A.2.2 and Eq. (24), I believe that it is a unit vector pointing in a spacelike direction? What exact is its role?

(Equation 24 has been removed; it is now broken into Equations 30-32.)

We hope that our rewritten Section A.2 is much clearer with respect to the basis vectors of the decision hyperplane. Indeed, we choose the $\mathbf{u}$ vectors to be unit vectors in each of the non-$d$ spacelike dimensions (see the new Eq. 21). Section A.2.1 describes this basis.

Spacelike unit vectors are used in the construction of geodesic arcs according to the method described in section A.2.3, and can be further composed into geodesic submanifolds according to the method in A.2.4.

I am unsure how you went from Eq. (24) to Eqs. (25-27). From what I am guessing, defines the direction of the intersecting geodesic, but I am unsure about the "\sinh" parameterization given.

(Equation 24 is now broken into Equations 30-32; Equations 25-27 are now 33-35)

Here are two links that lay out a simple version of this formulation of the geodesic:

https://math.stackexchange.com/questions/4663901/geodesics-in-hyperboloid-model-of-hyperbolic-space#:~:text=being%20the%20formula%20for%20a,the%20definition%20of%20the%20hyperboloid

https://en.wikipedia.org/wiki/Hyperboloid_model#Straight_lines

We have added a citation to Chami et al (2019): Hyperbolic Graph Convolutional Networks before Equations 33-35 as well: Proposition 3.1 in this paper contains a version of this formulation.

What is the connection between dimension in Eq. (12) and the normal vector characeterization of Eq. (8/9)?

(Equation 12 has been removed. It is now Equations 13-16).

The dimension $d$ used in the normal vector characterization and the dimension $d$ used in the characterization of the geodesic are the same: the basis vector $\mathbf{v}$ is nonzero in precisely dimensions 0 and $d$, which corresponds to the decision hyperplane $P(\theta)$ being inclined along axis $d$.

Thank you very much for your feedback and your endorsement of our paper’s contribution to the field.

We have revised the paper in accordance with your comments. Specifically, we have added a discussion of the advantages of geodesic decision boundaries to the Introduction, Methods, and Conclusions, and added experiments involving random forests in other models of hyperbolic geometry to the appendix. Our point-by-point response to your comments follows:

What is lacking in my opinion is a theoretical analysis of different decision boundaries and their performance for certain kinds of data (certain kinds of distributions of the data, that we may consider natural in certain classes of problems). For example, in case of regular decision trees, it may be observed that tabular data (where regular decision trees are best performers) is usually situated on axis-parallel hyperplanes and is easily separated by similar axis-parallel splits (due to naturally repeating nature / distribution of the data in tables along some dimensions)

The paper contains an interesting (and possibly simple to further analyze) case of synthetic data in hyperbolic space consisting of a sample from a mixture of Gaussians. It was observed empirically, that proposed method consistently outperforms the previous HoroRF/HoroDT. Providing a theoretical analysis of why it is the case would fill in the gaps and justify a choice of the proposed subset among all possible decision boundaries in hyperbolic space.

We have added a brief discussion of the advantages of geodesic decision boundaries to the Introduction of the paper. Our position is that the decision boundaries employed by Euclidean CART algorithms partition the space into continuous and convex subregions (“decision areas”), but these properties do not carry over to the hyperbolic case when applying existing tools. Specifically, HoroRF splits the space into one convex and one nonconvex region, and further splitting the nonconvex regions can create non-continuous decision areas. Euclidean random forests, on the other hand, preserve continuity but are not closed under geodesic combinations of their elements. Ours is the first method to guarantee both continuity and convexity of the resulting decision areas in hyperbolic space, which we believe helps the decision areas more naturally follow the data distribution and to generalize better with fewer splits. The empirical performance of our methods on benchmarks, as well as the advantages of Klein model embeddings over other models of hyperbolic space with Euclidean classifiers (see Section A.6.3 in the Appendix), corroborate the advantages of classification by geodesic splits.

Considering the proposed method and HoroRF, we know two ways of splitting the hyperbolic space, which correspond to an inductive bias that we impose on the data. Are there any other inductive biases / splits that can be considered, but perhaps are currently infeasible or otherwise unsuitable?

Another simple split to consider, an unrestricted linear split, is used by support vector machines and logistic regression classifiers. This type of split also has no geometric interpretation in the hyperboloid model, but it has the advantage of being able to search over all possible hyperplanes. The experiment carried out in Section A.6.2 suggests that our classifier works better, although it is not a 1:1 comparison because we permit a maximum depth of 3. The comparisons to other hyperbolic models in Section A.6.3 are also new classes of splits, although (with the exception of the Klein model) these hyperplane splits of the coordinate system are not immediately meaningful. Further comparisons to oblique decision trees and kernel support vector machines may also be informative.

Particularly, there is an inherent asymmetry of the hyperbolic space towards the center of the Poincare ball - and embeddings usually automatically (without being instructed to do so, during regular optimization) utilize this asymmetry to represent well the hierarchical data. Can we use this asymmetry in designing the splitting method?

There is a similar asymmetry to the hyperboloid model, where deeper levels of the hierarchy are represented as having a higher value in the timelike dimension; this is equivalent to having a greater radius in the Poincare disk model. In general, HyperDT/RF splits utilize this by having angles closer to $\pi/4$ or $3\pi/4$, corresponding to planes that intersect the hyperboloid farther up the timelike axis. Evidence from the new classification benchmark on nested WordNet embeddings in Section A.6.5 in the Appendix suggests that the splits used in HyperDT/RF indeed capture multiple levels of the hierarchy successfully compared to both HoroDT/RF and Euclidean decision trees/random forests, even in nested multiclass classification settings.

We thank you for your endorsement of our method’s novelty and performance, your appreciation of our paper’s presentation, and your thoughtful suggestions for further experiments.

We have carried out all experiments you have proposed and added them to Section A.6, “Additional Experiments,” in the appendix. We now address your comments inline:

All datasets seem to be better suited for the algorithm proposed by the authors. The authors do not provide the performance of the algorithm for other different types of datasets.

In Section A.6.5, we have added a new comparison where we classify hyperbolic embeddings of WordNet data, following the example in the HoroRF paper. The data for this was not public at submission time, so we are happy to have the opportunity to extend our analysis to a problem from natural language processing. The results of this experiment once again favor HyperDT/RF over HoroDT/RF and Scikit-Learn’s Euclidean classifiers.

Additionally, we would look to draw your attention to Section A.6.4 on classifying hyperbolic image embeddings, which was included in the Appendix to the original submission as its own section. This experiment shows mixed results: although HyperRF with hyperbolic embeddings outperforms all other combinations of random forest algorithm and geometry, we fail to meet the logistic regression baseline reported in the original paper. This suggests that random forests in general are not well-suited to the image classification task, but HoroRF is nevertheless more effective than its Euclidean counterparts.

How about the deeper tree (T>3 or even 7)?

We have performed a number of new scaling benchmarks, which we report in Section A.6.1. Figure 6d shows the effect of tree depth (up to 20) on the runtime and accuracy of HyperRF; Figure 7 compares the accuracy scaling with HoroRF and scikit-learn random forests. In particular, we are able to demonstrate a consistent advantage over the other methods at small tree depths, with all classifiers converging to roughly the same accuracy at high depths. We would like to emphasize that these results are on a toy dataset (mixture of Gaussians), and overfitting may become a bigger problem for all classifiers on other datasets.

What is the scalability of the algorithm? The author only tested the datasets of samples within 1000 and dimensions within 16.

Section A.6.1 now contains runtime and accuracy benchmarks for increasing the number of samples up to 3,000, the dimensionality up to 64, the number of trees in an ensemble up to 30, and the maximum depth up to 20. With the exception of tree depth, each experiment is consistent with linear scaling of runtime; interestingly, runtime seems to scale sublinearly with tree depth. This is likely due to two factors: first, the maximum depth is much higher than the actually achieved depth due to early stopping conditions of the algorithm; second, caching optimizations that allow us to reuse computations during the candidate selection step of the CART algorithm speed up late splits.

There are many other new decision tree training algorithms proposed these years. What is the performance of HYPERDT when compared with other advanced decision tree algorithms? (e.g., [1], [2])

While the duration of the reply period limited us to adding comparisons against hyperbolic logistic regression and hyperbolic SVMs, HyperDT can be adapted to other decision tree algorithms besides CART. The decision to adapt CART was motivated by its widespread popularity, effectiveness in machine learning, and the desire to avoid confounding the comparison of predictors’ geometries by differences in optimization procedures. We have updated the related work section and conclusion to include a discussion of other decision tree frameworks and leave additional extensions for future work.