Linking convo as reference: neurodata#16 and specifically neurodata#16 (comment).

I am going to proceed by adding some lightweight unit tests to determine integrability, and getting a working version that we can come back to.

Then I will try out the idea of replacing SplitRecord and such with a cdef class (maybe even dataclass?), which will be used to pass around the data structure from node_split and add_node.

Progress as of 3/16/22

Added Oblique trees/forests to the existing unit tests parametrizations and they mostly work, with one minor issue on pickling. The following is a summary:

• sparse dataset support, which I think should not be addressed here? There is the issue of how this would be implemented, and needs more thinking in terms of how to handle "categorical" data as well. Overall, I added error messages where needed and updated tests where needed to handle testing Oblique trees/forests.
• pickling does not work on roundtrip for some reason. See below.
• added a few new tests of performance relative to Forest_RI (i.e. DecisionTreeClf and RandomForestClf)

The commit 458220e is a stable working version that has all the tree/ensemble unit tests passing and also works as intended. The next step is to explore whether or not we can substitute a cdef class for the SplitRecord/ObliqueSplitRecord, so that way we can support subclassing better.

Pickling Issue Summary

The issue arises in the test: sklearn/tree/tests/test_tree.py::test_min_impurity_decrease, which pickles the object and then compares metadata and performance before/after. The scoring fails, on the lines:

score2 = est2.score(X, y)
        assert (
            score == score2
        ), "Failed to generate same score  after pickling with {0}".format(name)

with score 1.0 before and then 0.97 after pickling.

I've essentially fixed it "almost" in a74d970, where all the internal data structures of the ObliqueTree all match before/after pickling, but for some reason the predict produces different answers... wth?

Update: I can fix it by setting max_depth=5, so I suspect there is some machine-precision rounding issue on this edge case of a dataset. Done in a582546

Notes 3/21/22

Remove the max_depth=5 and try again:

• look at predictions rather then the score to determine which leaf is problematic. Most likely coming from a mishandling of tie in the feature value decision threshold(?) E.g. float32 compared to float64
• run 1NN within the test and see if there are duplicates of the feature vector within X with different y-labels
• iris 101 and 142 lines are duplicated... but might not be relevant. we'll see.

Update May 12th, 2022

Turns out Cython silently allows for j in range(...), even if j is not initialized with a type(?). Weird. Fixed in 8a720ed

Discussion on Discord - 6/13/22

Attendees: w/ @ogrisel @glemaitre @jshinm (I don't have the other folks on GH, please feel free to add them):

1. Absolute value of the plots in addition to the delta plots, since maybe max_features -> results in diff performance in RF and OF. E.g. maybe RF at mtry='sqrt' is optimal, whereas OF at mtry='2*n_features' is optimal.
2. Perform grid/random search over max_features and n_estimators to show the results of OF vs RF. Store the end results for MNIST with ROC_auc for the metric, and store the fitted trees on the disc. The results can be stored in a pd.DataFrame. Note: allow max_features to be > n_features for OF by design and see what happens.

We can use code from: https://nbviewer.org/github/ogrisel/notebooks/blob/master/sklearn_demos/ames_housing.ipynb
to inspire additional plots we want to show educating the dev team + users of the tradeoffs.

At the end of the day, we have the following trade-offs: train time, score time, RAM size of the trees, actual performance (e.g. ROC_AUC). Once we have the results of the Search CV, we can quickly plot these.

Misc notes

Some ideas for measuring the size of the tree(s): Pickle.dump with protocol-5 to measure the length of the string

We are working on the notebook / example that demonstrates superiority of the oblique decision trees vs axis-aligned decision trees. But based on the feedback we have received, this is ready for review! Please see the PR main post for all the information/discussion relevant for inclusion, maintenance, modularity of code, testability, and documentation.

• built docs on oblique trees: https://output.circle-artifacts.com/output/job/d244cc90-0ee6-46a0-b0f8-be0a6624ec91/artifacts/0/doc/modules/tree.html#oblique-trees (the image linked is somehow swapped, so I need to fix that, but otw the text is there).

Thanks for all the feedback and discussion to get it to this point! @glemaitre @thomasjpfan @amueller @ogrisel

@ogrisel I fixed the merge commit as discussed yesterday.

Here is a "brief" summary. For full details, see the PR description. Let me know if this is too long / detailed:

What are oblique trees: oblique trees generate splits based on combinations of features. They can sample more than n_features candidate splits per split node (up to 2^n in fact). Sampling random linear combinations of features implicitly captures the dominant singular vectors of the dataset with high probability, as described by the Johnson Lindenstrauss lemma. Oblique trees do not necessarily need to sample linear combinations either. They can be generalized in countless ways, which opens the door for more usage of the sklearn.tree module.

When are oblique trees better than axis-aligned? Based on the geometric motivation above, one would suspect that oblique trees fare better than axis-aligned trees when there is a high degree of noise dimensions, and/or there are optimal split hyperplanes in the data that are not aligned with the features themselves. Thus oblique trees are suspected to perform significantly better when there are a high degree of noise dimensions.

When are axis-aligned trees better than oblique?
Thus axis-aligned trees perform better when there are informative splits that occur along the feature axes. In general, this is a more "rare" scenario (e.g. analogously think what are the chances of sampling a 0 eigenvalue in a random matrix? measure 0). Thus, we see that oblique trees on average perform better. However, there is a small increased computational and storage cost for oblique trees: the sampling and storage of the projection vectors for each split node. Thus it is recommended to use axis-aligned trees whenever computation and storage time is a critical requirement, but always test oblique trees via cross-validation if model performance in terms of scoring metrics is preferred.