8000 [RFC] Modularize the tree class in both Python and Cython to enable easy extensions · Issue #24000 · scikit-learn/scikit-learn · GitHub
[go: up one dir, main page]
Skip to content

[RFC] Modularize the tree class in both Python and Cython to enable easy extensions #24000

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
adam2392 opened this issue Jul 25, 2022 · 20 comments · May be fixed by #25118 or #25448
Open

[RFC] Modularize the tree class in both Python and Cython to enable easy extensions #24000

adam2392 opened this issue Jul 25, 2022 · 20 comments · May be fixed by #25118 or #25448
Labels
cython module:ensemble module:tree Needs Decision - Include Feature Requires decision regarding including feature New Feature Refactor Code refactor

Comments

@adam2392
Copy link
Member

Describe the workflow you want to enable

As we are waiting for a reviewer to review #22754 , @thomasjpfan suggested we just move forward with our goals of creating a package of more exotic tree splits. E.g. https://arxiv.org/abs/1909.11799. While we wait for reviewers, the suggestion is to make a package within scikit-learn-contrib.

Although we would like for #22754 to be eventually merged into scikit-learn, we understand reviewer backlog is an issue. To move forward while reviews occur, we would need to subclass existing scikit-learn code. Ideally, we would like to introduce minor refactoring changes that would make this task significantly easier.

We would like to subclass directly from scikit-learn without requiring us to keep an up-to-date fork of scikit-learn with all the bug fixes and maintenance that the dev team here does. We can limit this if we modularize the Python/Cython functions inside the sklearn/tree module.

Describe your proposed solution

I am proposing two refactoring modifications that have no impact on the performance of the current tree estimators in scikit-learn.

  1. Refactor the BaseDecisionTree Python class to have the following functions that can be overridden in a subclass:
  • _set_tree_class: sets the Tree Cython class that the Python API uses
  • _set_splitter: sets the Splitter Cython class that the Python API uses

For example, this makes the subclassing of BaseDecisionTree cleaner:

scikit-learn/sklearn/tree/_classes.py

Lines 410 to 416 in de06afa

def _set_tree_func(self):
"""Set tree function."""
return Tree
def _set_splitter(
self, issparse, criterion, min_samples_leaf, min_weight_leaf, random_state
):
.

  1. Refactor the Tree Cython class to have the following functions:
  • _set_node_values: transfers split node values to the storage node
  • _compute_feature_value: uses the storage node and the input data to compute the feature value to split on

For example, see

scikit-learn/sklearn/tree/_tree.pyx

Lines 770 to 787 in de06afa

cdef int _set_node_values(self, SplitRecord* split_node,
Node *node) nogil except -1:
"""Set node data.
"""
node.feature = split_node.feature
node.threshold = split_node.threshold
return 1
cdef DTYPE_t _compute_feature(self, const DTYPE_t[:] X_ndarray,
Node *node, SIZE_t node_id) nogil:
"""Compute feature from a given data matrix, X.
In axis-aligned trees, this is simply the value in the column of X
for this specific feature.
"""
# the feature index
cdef DTYPE_t feature = X_ndarray[node.feature]
return feature
.

  1. Refactor the TreeBuilder Cython class to pass around a Split pointer, rather than the struct itself

This will enable someone to use C-level functions to pass around another struct with a similar structure as Split.

For example, see

scikit-learn/sklearn/tree/_tree.pyx

Line 193 in de06afa

cdef SplitRecord* split_ptr = <SplitRecord *>malloc(splitter.pointer_size())
.

Describe alternatives you've considered, if relevant

Alternatives would require maintaining a copy of the sklearn/tree module and keep it up-to-date w/ sklearn changes. If this was just one Cython file, I would say it is possible, but the necessary ingredients span some of the underlying private API, making this a very time-consuming task. Introducing modularity into the private API that does not impact existing performance, therefore seems to be the best path forward?

Moreover, by introducing these refactoring changes, #22754 has a smaller diff and lower-cost to review.

Additional context

#22754 demonstrates that there is no performance regression, or issues w/ existing DecisionTree, or RandomForest when introducing these changes.
@adam2392 adam2392 added Needs Triage Issue requires triage New Feature labels Jul 25, 2022
@thomasjpfan
Copy link
Member

Note that since _set_tree_class and other extension points will be private in scikit-learn. This means that they can change without deprecation between scikit-learn versions. A third party library that subclasses these classes may have more maintenance overhead to support different scikit-learn versions.

I know I suggested it, but item 3 with the pointer_size is kind of hacky. I am okay with it being used internally, but I am uneasy about it as a third-party extension point. (I'm around +0.3)

Stepping back, the main issue is that the trees were designed around axis-aligned splits. For third party libraries that only need axis-aligned splits, it is easy to subclass. For scikit-learn, do we want to add these extension points to allow for non axis-aligned splits, when they are not in the library itself? I am slightly in favor at +0.5.

@thomasjpfan thomasjpfan added Refactor Code refactor Needs Decision - Include Feature Requires decision regarding including feature and removed Needs Triage Issue requires triage labels Jul 27, 2022
@adam2392
Copy link
Member Author
adam2392 commented Jul 27, 2022 •
edited
Loading

Thanks Thomas! Adding some comments to augment the discussion. The high level goal of all 3 I would say is to enable more flexibility wrt Python/Cython code to allow maximal reusability.

I know I suggested it, but item 3 with the pointer_size is kind of hacky. I am okay with it being used internally, but I am uneasy about it as a third-party extension point. (I'm around +0.3)

After you showed me this trick, I perused more and this actually seems to be an "accepted" standard for "inheritance" of structs in C. Unfortunately, Cython takes after C in this regard for structs and not C++. Perhaps some proper documentation inline code to reduce technical confusion of anyone in the future reading the Tree code, so that way they don't need to have extensive C knowledge.

Stepping back, the main issue is that the trees were designed around axis-aligned splits. For third party libraries that only need axis-aligned splits, it is easy to subclass. For scikit-learn, do we want to add these extension points to allow for non axis-aligned splits, when they are not in the library itself? I am slightly in favor at +0.5.

I somewhat agree with the point here. The extension points enable someone to subclass the existing code more flexibly I would argue rather than just enabling non axis-aligned splits. Say someone wants to define their own axis-aligned splitter and provide a Python API. e.g. some function that chooses splits using some graph traversal instead of at random. I'm just postulating here on ideas I've had in the past for improving RF. But even this hypothetical workflow is not possible in the current setup.

@adam2392
Copy link
Member Author
adam2392 commented Aug 9, 2022

In order to move #22754 along, and possibly get it into a state that can be easily refactored for a stand-alone scikit-learn-contrib package, just wanted to see if there was any consensus on this?

@jjerphan
Copy link
Member

I would say that maintainers have not discussed and agreed in modularizing those implementations yet. Ideally, it should be modular, but I do not think that's on the agenda on any maintainer: it's not that we are against it, it's just that the few maintainers working on this part of the code-base are busy with other maintenance aspects.

If you want #22754 to move along, I think the best is that you try to refactor it (I would like to help, but I yet can't). Also when re-factoring private Cython code, mind sharing responsibilities for unexpected subsequent users' issue.

@adam2392
Copy link
Member Author
adam2392 commented Aug 17, 2022 •
edited
Loading

Hey @jjerphan thanks for the reply!

I think for me I'm faced with a few obstacles and I'm hoping for some clarity here. Happy to discuss at OH whenever they restart...

The original issue #20819 has a few concerns that were cleared up: i) citation criterion and ii) maintainability due to stiffness of the tree code. I addressed i) and then I spent a lot of time figuring out how to make Oblique Trees inherit directly from the RF code to lower the LOC to be added. Then once I got the PR setup, the dev team requested a number of experiments to support this addition. Now those are documented in the PR #22754 . Then it was said that this would require a maintainer to review the code and everyone is busy and suggested that I try to add this to scikit-learn-contrib to allow us to build off the work that was done here. Totally understand that the dev team has other goals beyond what I want and they are busy, but I want to see what's the best path forward since there's a considerable amount of work done here to make sure a 10k+ cited paper with considerable empirical evidence is compatible with scikit-learn tree code. If the concern is maintainability, I'm happy to ask @jovo if his lab is willing to maintain this part of the code since they are one lab that is invested in extending oblique trees beyond what was proposed by Breiman.

The two options that were floated to me are:

  1. PRing oblique trees into scikit learn: It seems the inclusion is now mainly dependent on a review cycle, which it seems devs would prefer not to do if it is a big PR(?) I'm not sure how else to improve the code, but I'm willing to chop up the PR into smaller digestible bites. I offered to help refactor the Cython and Python code base to enable extensions that allow generalizations to the splitter but haven't gotten a reply :/.

  2. Oblique Trees as a separate scikit-learn contrib package for now: it was suggested this can help me move along with some of my projects while waiting for reviews on the direct PR of oblique trees. However this then relies on the suggested refactoring I noted above. However, it seems even this refactoring to enable scikit-learn tree code to be more generalizable is facing considerable bottlenecks.

The refactoring would not change any functionality based on the gif you sent. I understand tho this is OSS and the dev team is pretty busy with consolidation of the package. So anything I can do to help either the PR itself or the scikit-learn-contrib package move along, I'm happy to do so. Also happy to contribute more to the general scikit-learn package so the devs time is freed up. I would def appreciate any guidance here.

Lmk if I'm perhaps misunderstanding anything.

@jjerphan
Copy link
Member

Hi @adam2392,

Thank you for this long comment. I will add your contributions to discussion to the next core-developer meeting. You should be able to join it freely.

@adam2392
Copy link
Member Author
adam2392 commented Sep 5, 2022

Hi @jjerphan sorry about logging in late. Today was Labor Day in the USA, so I was actually traveling during this time. I tried joining a bit after the meeting had started, but the Google meets needed someone to "let me in". I think the meeting probably ended cuz I wasn't let in, so left after a few minutes.

Wanted to follow up to see what I could do to help out with making trees more modularizable and platform-friendly?

@adam2392
Copy link
Member Author
adam2392 commented Sep 28, 2022 •
edited
Loading

Following up on our discussion in dev meeting:

tldr: Both scikit-survival and quantile-forests generalize RF in different ways compared to what I am proposing. I am proposing generalizations for the split function. Scikit-survival proposes a generalization of the criterion. Quantile-forests proposes a generalization of how the leaf nodes are set, which is also something honest forests generalizes.

Scikit-survival

IIUC, this package cannot subclass BaseDecisionTree rn because of fundamental differences in y variable implemented in scikit-survival. The Criterion changes, but that can be passed in directly to the Decision Tree class. Another change is the structure of the y labels variable. In scikit-survival, each sample in y is a tuple consisting of a binary event indicator as first field, and time of event or time of censoring as second field. Basically, it is whether or not sample survived and then the length of survival. Rn event_times is directly passed into LogRankCriterion here, which prevents it from using BaseDecisionTree.

I think scikit-survival can benefit from a refactoring if we enable also a private _set_criterion function, which would enable subclassing of BaseDecisionTree that alters the Criterion class as well. For example:

def _set_criterion(self, X, y):
     # sets criterion class given metadata from the input X and y

This could potentially allow more exotic criterions. However, I can see this not being 100% necessary.

skurv refs

See the tree code: https://github.com/sebp/scikit-survival/blob/52c713dc8e3beb266f9cad7e6785dce5fa282f01/sksurv/tree/tree.py#L217-L230

And relevant Cython criterion that subclasses scikit-learn: https://github.com/sebp/scikit-survival/blob/master/sksurv/tree/_criterion.pyx

Quantile Forest

Quantile random forest (QRF) implements the entire forest using Cython. Fundamentally, the QRF needs to store information about all observations in its leaf nodes, rather than just the mean of the labels, which is currently done in scikit-learn's RF.

This refactoring unfortunately would not play a role here because it operates at generalizing the splitting.

However, QRF and honest forests are candidates that probably would benefit from a generalization of setting the leaves within the RF code of scikit-learn. Both QRF and honest forests use the leaves differently than that of RF, but both QRF and honest forests perform the splitting in the same way. The refactoring here would simply help QRF/honest-forests take advantage of more exotic splitting functions.

cc: @ogrisel @jjerphan @thomasjpfan Feel free to add anyone I missed.

@jjerphan jjerphan changed the title [Refactor] Modularize the tree class in both Python and Cython to enable easy extensions [RFC] Modularize the tree class in both Python and Cython to enable easy extensions Oct 6, 2022
@jjerphan jjerphan mentioned this issue Oct 6, 2022
Open
@adam2392
Copy link
Member Author
adam2392 commented Oct 6, 2022

In general, I have written up a more lengthy proposal for improving/simplifying the tree submodule. I have summarized it in this hackmd doc. Feel free to comment and take a look...

https://hackmd.io/@-5q0aS6xT4Sq6RULDW8EVw/HkpsR9hMi

cc: @thomasjpfan @jjerphan @ogrisel @glemaitre

@adam2392
Copy link
Member Author

Hi, I just wanted to follow up on this thread to see what the next steps are for any of the following:

Thanks!

@jjerphan
Copy link
Member

Hi @adam2392,

I've seen your request. I would like to get back to a few other things first and then I will have a look at your suggestion (hopefully today). Thank you for your patience!

@jjerphan
Copy link
Member

I read your general proposal of Tree and TreeBuilder modularizations and have some comments and suggestions. Is it possible to make you HackMD pad commentable (or even editable if relevant)?

@adam2392
Copy link
Member Author

Hey @jjerphan oops. Made the link editable now!

https://hackmd.io/@-5q0aS6xT4Sq6RULDW8EVw/HkpsR9hMi/edit

@adam2392 adam2392 mentioned this issue Oct 24, 2022
Draft
@jjerphan jjerphan mentioned this issue Oct 28, 2022
Closed
@adam2392 adam2392 linked a pull request Dec 6, 2022 that will close this issue
Draft
@adam2392 adam2392 linked a pull request Jan 20, 2023 that will close this issue
Draft
@lorentzenchr
Copy link
Member

@scikit-learn/core-devs We need a decision here. Even a straight no is better then lingering. And with a bit of courage, we could get a little lift of the tree module by someone who really cares.

My main concern is that building an internal API for a 3rd party package thereby becomes a somewhat public API. On the other side, it makes integration much easier should we one day wish for it.

@jjerphan
Copy link
Member

@adam2392 : do you want to maintain the implementations of the tree module?

@adam2392
Copy link
Member Author
adam2392 commented Jan 29, 2024 •
edited
Loading

Appreciate the feedback I have received and discussions here.

@adam2392 : do you want to maintain the implementations of the tree module?

Yes, I am always happy to contribute to scikit-learn anyway I can that is wanted by the team/community. I hope that is reflected as well from my PRs, GH activity, and Discord discussions.

@jjerphan
Copy link
Member

This contribution is interesting but it will complexify the project.

I think I would only accept those contributions if the tree module has a higher bus factor.

@adrinjalali
Copy link
Member

I think this is quite a good idea. And our tree code has become more maintainable in the past couple of years also thanks to @thomasjpfan

@thomasjpfan
Copy link
Member

Two concerns with adding more extension points:

  • We have to be careful with benchmarking. The tree code is quite optimized in some places and adding some Cython abstractions can make it slower.

My main concern is that building an internal API for a 3rd party package thereby becomes a somewhat public API. On the other side, it makes integration much easier should we one day wish for it.

  • This is still my concern. As long as we do not promise backward compatibility, I am okay with having more extension points.
    • BTW as a work around, a third party library can pin scikit-learn as a build dependency to get the Cython tree code for a specific scikit-learn version. During runtime, their code can still work with newer versions of scikit-learn.

@adam2392
Copy link
Member Author
adam2392 commented Feb 1, 2024

In general to summarize the points in this thread and others, private extension API is fine if:

  1. documentation clearly states no stability
  2. benchmarks against main demonstrate the trees do not lose performance in terms of runtime (accuracy is a given)
  3. the introduced abstractions are not difficult to maintain and are not too complex

Lmk if I missed anything.

BTW as a work around, a third party library can pin scikit-learn as a build dependency to get the Cython tree code for a specific scikit-learn version. During runtime, their code can still work with newer versions of scikit-learn.

Yes this is a good point. It is actually what I ended up doing in scikit-tree by leveraging a forked-submodule of scikit-learn purely for the Cython tree code.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
cython module:ensemble module:tree Needs Decision - Include Feature Requires decision regarding including feature New Feature Refactor Code refactor
Projects
None yet
Milestone
No milestone
5 participants
@adrinjalali @adam2392 @thomasjpfan @jjerphan @lorentzenchr
0