Talip7/scikit-learn-issues-multilabel huggingface dataset:
[FEAT] Enhancing decision trees

### Describe the workflow you want to enable

I'd like the decision tree to be capable at capturing more complex interactions.

### Describe your proposed solution

Include new parameters:
- A global maximum gain threshold.
- A secondary threshold where if no splits are available due to the max gain threshold, and if all values exceed this 2nd threshold, use the lowest gain available, otherwise it becomes a leaf node.

This would be in contrast with the minimum impurity reduction threshold, and should encourage the tree to learn more complex interactions.

It would be more ideal if the minimum and maximum thresholds were also configurable per-feature, but that'd be going overboard.

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

_No response_

COMMENT:
Will need to wait for triage first, then a deciison to be made if this is to be made.

Technically ensembles / forests already resolve the complexity issue of decision trees, however there's 2 key benefits to this approach:
1. More predictive power for regular trees, which are interpretable unlike forests.
2. With more complex trees, it's possible that the required trees for forests could be reduced.

For my personal use-case, it'd be using H-VRT https://github.com/HotProtato/H-VRT as I've built it on top of the decision tree regressor, to partition by treating all x values as y in addition to y, with z-score normalization on the y representation of continuous values, and the gini impurity for categories (placing them on the same scale).

I've included some metrics and diagnostics for partition quality, and plan on manipulating it to be used as an intermediary for downstream models. Beyond that, I've tested H-VRT for anomoly detection, and it's the most accurate anomaly detector model that's interpretable. That max gain threshold could potentially improve partition quality, and the results of my anomaly detector.

Labels: New Feature, Needs Decision
[FEAT] Enhancing decision trees

### Describe the workflow you want to enable

I'd like the decision tree to be capable at capturing more complex interactions.

### Describe your proposed solution

Include new parameters:
- A global maximum gain threshold.
- A secondary threshold where if no splits are available due to the max gain threshold, and if all values exceed this 2nd threshold, use the lowest gain available, otherwise it becomes a leaf node.

This would be in contrast with the minimum impurity reduction threshold, and should encourage the tree to learn more complex interactions.

It would be more ideal if the minimum and maximum thresholds were also configurable per-feature, but that'd be going overboard.

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

_No response_

COMMENT:
@HotProtato thanks for opening an issue! Not a tree expert, do you have a link to an article that describe this approach? We have a somewhat strict [inclusion criterion](https://scikit-learn.org/stable/faq.html#what-are-the-inclusion-criteria-for-new-algorithms) for new algorithms to strike the right balance between adding new features and maintenance costs.

cc @adam2392 in case you have some quick opinion on this?

@Nithurshen this is indeed not a good issue for newish contributors. Please have a look at our [contributing doc](https://scikit-learn.org/dev/developers/contributing.html) and in particular the section [Issues for new contributors](https://scikit-learn.org/dev/developers/contributing.html#new-contributors).

Labels: New Feature, Needs Decision
[FEAT] Enhancing decision trees

### Describe the workflow you want to enable

I'd like the decision tree to be capable at capturing more complex interactions.

### Describe your proposed solution

Include new parameters:
- A global maximum gain threshold.
- A secondary threshold where if no splits are available due to the max gain threshold, and if all values exceed this 2nd threshold, use the lowest gain available, otherwise it becomes a leaf node.

This would be in contrast with the minimum impurity reduction threshold, and should encourage the tree to learn more complex interactions.

It would be more ideal if the minimum and maximum thresholds were also configurable per-feature, but that'd be going overboard.

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

_No response_

COMMENT:
@lesteve Thank you. Local testing showed modest results, with many cases yielding smaller trees outperforming the current DecisionTreeRegressor's current approach. I also opted to simplify it so there's only one parameter; the maximum gain threshold where it eliminates potential splits that exceed it, but if there's no available splits, then the smallest gain is used.

From what I could see, this approach has yet to be formally tested and reported on. The inclusion criterion is rather strict, thank you for sharing it. I'm happy to test this with HPO using Optuna on a variety of datasets and share my findings, including for classification tasks.

Labels: New Feature, Needs Decision
[FEAT] Enhancing decision trees

### Describe the workflow you want to enable

I'd like the decision tree to be capable at capturing more complex interactions.

### Describe your proposed solution

Include new parameters:
- A global maximum gain threshold.
- A secondary threshold where if no splits are available due to the max gain threshold, and if all values exceed this 2nd threshold, use the lowest gain available, otherwise it becomes a leaf node.

This would be in contrast with the minimum impurity reduction threshold, and should encourage the tree to learn more complex interactions.

It would be more ideal if the minimum and maximum thresholds were also configurable per-feature, but that'd be going overboard.

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

_No response_

COMMENT:
> From what I could see, this approach has yet to be formally tested and reported on

Yeah, so this is typically NOT a good candidate for scikit-learn inclusion I am afraid.

I am going to close this one, because I feel it is unlikely to happen in scikit-learn in the foreseeable future.

At this point I would suggest you keep working on your repo https://github.com/HotProtato/H-VRT. If one day your repo/ideas gain traction, we may reconsider this 😉.

Labels: New Feature, Needs Decision
[FEAT] Enhancing decision trees

### Describe the workflow you want to enable

I'd like the decision tree to be capable at capturing more complex interactions.

### Describe your proposed solution

Include new parameters:
- A global maximum gain threshold.
- A secondary threshold where if no splits are available due to the max gain threshold, and if all values exceed this 2nd threshold, use the lowest gain available, otherwise it becomes a leaf node.

This would be in contrast with the minimum impurity reduction threshold, and should encourage the tree to learn more complex interactions.

It would be more ideal if the minimum and maximum thresholds were also configurable per-feature, but that'd be going overboard.

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

_No response_

COMMENT:
Understood. I will say that my experiments have shown high encouragements for boosting in using the max gain threshold in this way.

For anyone else interested in looking into this. Perhaps it could reveal more properties of data, while positively impacting interpretability, as it may be easier to interpret one or a few boosting pathways to find where the majority of predictions lie, compared to sporadic leaf nodes.

Also, it performs rather poorly for categorical data from what I have observed so far. I have been experimenting with another approach for categorical data, and plan to investigate ways on improving efficiency by leveraging parent nodes' inference scores but overall, the approach is instead of maximizing the HHI (as Gini impurity is simply 1 - hhi of class proportions), you get inference at every point, and you optimize for (metric with respect to errors) * lambda * (1 - HHI of errors), or even just HHI of errors depending on if you want to prioritize recall or precision. For (metric), you could also prioritize precision, recall, or F1, I think precision would make the most logical sense there though.

With this approach, the max gain threshold has more of an impact overall for categorical trees.

Labels: New Feature, Needs Decision
RFC: is optimizing `DecisionTree*`/`ExtraTree*` worth the effort/extra complexity?

I've been working quite a lot on trees lately (and on partitioning/sorting too, which helps here). And I have some ideas to optimize some things in `sklearn/tree`. Some of those ideas are backed-up by encouraging early experiments, some are not.

But I'm not super aware of the usage of `scikit-learn` today. I used it mostly between 2017 and 2020. So I'm not sure how relevant it is to put some possibly significant efforts into optimizing the trees. So I'm asking for opinions, cc @adam2392 @ogrisel @adrinjalali @thomasjpfan @jjerphan @lorentzenchr @glemaitre.

Here is the list of my ideas:
1. **improve partitioning in `partition_samples`**: small change and clear impact on `ExtraTrees*`. This one I'm decided to open a PR.
2. **F-order X in trees:** not too big of a change, but not as easy as it seems because it requires many careful changes in `sklearn/ensemble`, for now impact is hard to measure.
3. **Improve sorting**: this hard, but this could be huge, like 1.5x speedup  in average. The current sort (intro-sort) uses a 3-way partitioning scheme that is very efficient when there are a LOT of duplicates, but much slower when it's not the case. With no duplicates, the usual 2-way partitioning scheme is ~5-8x times faster! But with a LOT of duplicates, it can be up to 3x slower. I think it's possible to mix both to get the best of both worlds. **The hardest part here in this is doing reliable benchmarks**. It's very very data-dependent: I would need a lot if real-world use cases to build confidence in the speedup measurements.
5. **Specialized code for `n_outputs=1` (and maybe for `sample_weights=None`)**: might have some non-negligible impact on `ExtraTree*`
6. **Sort `y` (and possibly the weights) along with `feature_values`**: max possible speed-up: ~10% for both `DecisionTree*` and `ExtraTree*` I'd say (based on flame graphs). Increases memory usage.

COMMENT:
An other big change we have discussed here and there in the past would be to bring the histogram-tree growing of hist gradient boosting as a new option to RFs and merge the GradientBoosting* and HistGradientBoosting* classes.

Labels: RFC
RFC: is optimizing `DecisionTree*`/`ExtraTree*` worth the effort/extra complexity?

I've been working quite a lot on trees lately (and on partitioning/sorting too, which helps here). And I have some ideas to optimize some things in `sklearn/tree`. Some of those ideas are backed-up by encouraging early experiments, some are not.

But I'm not super aware of the usage of `scikit-learn` today. I used it mostly between 2017 and 2020. So I'm not sure how relevant it is to put some possibly significant efforts into optimizing the trees. So I'm asking for opinions, cc @adam2392 @ogrisel @adrinjalali @thomasjpfan @jjerphan @lorentzenchr @glemaitre.

Here is the list of my ideas:
1. **improve partitioning in `partition_samples`**: small change and clear impact on `ExtraTrees*`. This one I'm decided to open a PR.
2. **F-order X in trees:** not too big of a change, but not as easy as it seems because it requires many careful changes in `sklearn/ensemble`, for now impact is hard to measure.
3. **Improve sorting**: this hard, but this could be huge, like 1.5x speedup  in average. The current sort (intro-sort) uses a 3-way partitioning scheme that is very efficient when there are a LOT of duplicates, but much slower when it's not the case. With no duplicates, the usual 2-way partitioning scheme is ~5-8x times faster! But with a LOT of duplicates, it can be up to 3x slower. I think it's possible to mix both to get the best of both worlds. **The hardest part here in this is doing reliable benchmarks**. It's very very data-dependent: I would need a lot if real-world use cases to build confidence in the speedup measurements.
5. **Specialized code for `n_outputs=1` (and maybe for `sample_weights=None`)**: might have some non-negligible impact on `ExtraTree*`
6. **Sort `y` (and possibly the weights) along with `feature_values`**: max possible speed-up: ~10% for both `DecisionTree*` and `ExtraTree*` I'd say (based on flame graphs). Increases memory usage.

COMMENT:
You can also finish the work in NOCATS (https://github.com/scikit-learn/scikit-learn/pull/12866) which is very much upvoted.

As for relevance, trees are very relevant and we have also seen random forests being used in some cases and beating HGBT. So any work in this area of the codebase is very much appreciated.

You can also create a meta-issue and triage and list all existing stale PRs and issues to have an overview of what's there to do.

Otherwise, you're ideas here also seem all relevant, and we very much appreciate your work and happy you've been putting time here recently ❤️

Labels: RFC
RFC: is optimizing `DecisionTree*`/`ExtraTree*` worth the effort/extra complexity?

I've been working quite a lot on trees lately (and on partitioning/sorting too, which helps here). And I have some ideas to optimize some things in `sklearn/tree`. Some of those ideas are backed-up by encouraging early experiments, some are not.

But I'm not super aware of the usage of `scikit-learn` today. I used it mostly between 2017 and 2020. So I'm not sure how relevant it is to put some possibly significant efforts into optimizing the trees. So I'm asking for opinions, cc @adam2392 @ogrisel @adrinjalali @thomasjpfan @jjerphan @lorentzenchr @glemaitre.

Here is the list of my ideas:
1. **improve partitioning in `partition_samples`**: small change and clear impact on `ExtraTrees*`. This one I'm decided to open a PR.
2. **F-order X in trees:** not too big of a change, but not as easy as it seems because it requires many careful changes in `sklearn/ensemble`, for now impact is hard to measure.
3. **Improve sorting**: this hard, but this could be huge, like 1.5x speedup  in average. The current sort (intro-sort) uses a 3-way partitioning scheme that is very efficient when there are a LOT of duplicates, but much slower when it's not the case. With no duplicates, the usual 2-way partitioning scheme is ~5-8x times faster! But with a LOT of duplicates, it can be up to 3x slower. I think it's possible to mix both to get the best of both worlds. **The hardest part here in this is doing reliable benchmarks**. It's very very data-dependent: I would need a lot if real-world use cases to build confidence in the speedup measurements.
5. **Specialized code for `n_outputs=1` (and maybe for `sample_weights=None`)**: might have some non-negligible impact on `ExtraTree*`
6. **Sort `y` (and possibly the weights) along with `feature_values`**: max possible speed-up: ~10% for both `DecisionTree*` and `ExtraTree*` I'd say (based on flame graphs). Increases memory usage.

COMMENT:
Answers on subjects that are not directly about optimizing the current code:

**(1) Categorical features**
Working on categories is in my roadmap: I already did the core part of the work, and I'm fairly happy with the result. The added complexity to the code is very reasonable, and performance is good, if not great.
The PR is on my repo: https://github.com/cakedev0/scikit-learn/pull/2 (it's on top of another branch that simplifies quite a lot some pieces of code in `sklearn/tree`, it was easier to start from there).

**(2) histogram-tree**
I need to take a look at the histogram-tree growing of hist gradient boosting. My first intuition is that the current code of `sklearn/tree` could support binning in a very natural/elegant manner, the same way I introduced support for categorical features, as written in my PR:

> The central idea is to replace the call to `sort` in `DensePartitioner.sort_samples_and_feature_values` by a call to `_breiman_sort_categories`

Similarly, I think we could call a O(n_bins) `_sort_binned_feature` instead of `sort`, while preserving entirely the rest of the code and that would do the trick.

Labels: RFC
RFC: is optimizing `DecisionTree*`/`ExtraTree*` worth the effort/extra complexity?

I've been working quite a lot on trees lately (and on partitioning/sorting too, which helps here). And I have some ideas to optimize some things in `sklearn/tree`. Some of those ideas are backed-up by encouraging early experiments, some are not.

But I'm not super aware of the usage of `scikit-learn` today. I used it mostly between 2017 and 2020. So I'm not sure how relevant it is to put some possibly significant efforts into optimizing the trees. So I'm asking for opinions, cc @adam2392 @ogrisel @adrinjalali @thomasjpfan @jjerphan @lorentzenchr @glemaitre.

Here is the list of my ideas:
1. **improve partitioning in `partition_samples`**: small change and clear impact on `ExtraTrees*`. This one I'm decided to open a PR.
2. **F-order X in trees:** not too big of a change, but not as easy as it seems because it requires many careful changes in `sklearn/ensemble`, for now impact is hard to measure.
3. **Improve sorting**: this hard, but this could be huge, like 1.5x speedup  in average. The current sort (intro-sort) uses a 3-way partitioning scheme that is very efficient when there are a LOT of duplicates, but much slower when it's not the case. With no duplicates, the usual 2-way partitioning scheme is ~5-8x times faster! But with a LOT of duplicates, it can be up to 3x slower. I think it's possible to mix both to get the best of both worlds. **The hardest part here in this is doing reliable benchmarks**. It's very very data-dependent: I would need a lot if real-world use cases to build confidence in the speedup measurements.
5. **Specialized code for `n_outputs=1` (and maybe for `sample_weights=None`)**: might have some non-negligible impact on `ExtraTree*`
6. **Sort `y` (and possibly the weights) along with `feature_values`**: max possible speed-up: ~10% for both `DecisionTree*` and `ExtraTree*` I'd say (based on flame graphs). Increases memory usage.

COMMENT:
Re categorical splits: I am very interested in getting sklearn to support categorical splits. Have you seen https://github.com/scikit-learn/scikit-learn/pull/29437? This just needs some work in testing, but haven't had the time in the past months. To prevent overlap in work, perhaps worth converging there first. 

Re optimizations: I think all those you list are worth exploring, but sound quite complex. Idk if it's worth it compared to the histogram-tree.

Re histogram-tree: This could be super impactful when done right imo by adding implicit regularization (discretization of features), and potentially runtime performance improvements since we only have to sort over `n_bins` unique values. The overarching problem that prevents us from doing this with the HistGradBoostingTree code is the need to generalize datatypes from float32 to uint8. This would require full-fledged C++ templating (Cython supports templating but not 100% compared to C++).

Labels: RFC
RFC: is optimizing `DecisionTree*`/`ExtraTree*` worth the effort/extra complexity?

I've been working quite a lot on trees lately (and on partitioning/sorting too, which helps here). And I have some ideas to optimize some things in `sklearn/tree`. Some of those ideas are backed-up by encouraging early experiments, some are not.

But I'm not super aware of the usage of `scikit-learn` today. I used it mostly between 2017 and 2020. So I'm not sure how relevant it is to put some possibly significant efforts into optimizing the trees. So I'm asking for opinions, cc @adam2392 @ogrisel @adrinjalali @thomasjpfan @jjerphan @lorentzenchr @glemaitre.

Here is the list of my ideas:
1. **improve partitioning in `partition_samples`**: small change and clear impact on `ExtraTrees*`. This one I'm decided to open a PR.
2. **F-order X in trees:** not too big of a change, but not as easy as it seems because it requires many careful changes in `sklearn/ensemble`, for now impact is hard to measure.
3. **Improve sorting**: this hard, but this could be huge, like 1.5x speedup  in average. The current sort (intro-sort) uses a 3-way partitioning scheme that is very efficient when there are a LOT of duplicates, but much slower when it's not the case. With no duplicates, the usual 2-way partitioning scheme is ~5-8x times faster! But with a LOT of duplicates, it can be up to 3x slower. I think it's possible to mix both to get the best of both worlds. **The hardest part here in this is doing reliable benchmarks**. It's very very data-dependent: I would need a lot if real-world use cases to build confidence in the speedup measurements.
5. **Specialized code for `n_outputs=1` (and maybe for `sample_weights=None`)**: might have some non-negligible impact on `ExtraTree*`
6. **Sort `y` (and possibly the weights) along with `feature_values`**: max possible speed-up: ~10% for both `DecisionTree*` and `ExtraTree*` I'd say (based on flame graphs). Increases memory usage.

COMMENT:
Yes my PR is highly inspired from your PR https://github.com/scikit-learn/scikit-learn/pull/29437 👍

Labels: RFC
RFC: is optimizing `DecisionTree*`/`ExtraTree*` worth the effort/extra complexity?

I've been working quite a lot on trees lately (and on partitioning/sorting too, which helps here). And I have some ideas to optimize some things in `sklearn/tree`. Some of those ideas are backed-up by encouraging early experiments, some are not.

But I'm not super aware of the usage of `scikit-learn` today. I used it mostly between 2017 and 2020. So I'm not sure how relevant it is to put some possibly significant efforts into optimizing the trees. So I'm asking for opinions, cc @adam2392 @ogrisel @adrinjalali @thomasjpfan @jjerphan @lorentzenchr @glemaitre.

Here is the list of my ideas:
1. **improve partitioning in `partition_samples`**: small change and clear impact on `ExtraTrees*`. This one I'm decided to open a PR.
2. **F-order X in trees:** not too big of a change, but not as easy as it seems because it requires many careful changes in `sklearn/ensemble`, for now impact is hard to measure.
3. **Improve sorting**: this hard, but this could be huge, like 1.5x speedup  in average. The current sort (intro-sort) uses a 3-way partitioning scheme that is very efficient when there are a LOT of duplicates, but much slower when it's not the case. With no duplicates, the usual 2-way partitioning scheme is ~5-8x times faster! But with a LOT of duplicates, it can be up to 3x slower. I think it's possible to mix both to get the best of both worlds. **The hardest part here in this is doing reliable benchmarks**. It's very very data-dependent: I would need a lot if real-world use cases to build confidence in the speedup measurements.
5. **Specialized code for `n_outputs=1` (and maybe for `sample_weights=None`)**: might have some non-negligible impact on `ExtraTree*`
6. **Sort `y` (and possibly the weights) along with `feature_values`**: max possible speed-up: ~10% for both `DecisionTree*` and `ExtraTree*` I'd say (based on flame graphs). Increases memory usage.

COMMENT:
Re **histogram-tree**: I took a look at the code of `HistGradientBoosting` and:
- it shouldn't be too hard to implement binning in trees. Though I think it might help to first refactor the `Dense/SparsePartitioner` classes in favor of `Feature` classes playing roughly the same role but specialized for different cases: `DenseNumericalFeature` (~ `DensePartitioner`), `SparseNumericalFeature` (~ `SparsePartitioner`), `CategoricalFeature`, `BinnedFeature`, ... Anyway, let's focus on the categorical features support first.
- it will likely be fairly hard to reach similar performance than the HGB code while keeping the same code-path for different criteria and for sparse data... But it might be possible. That would be fairly ambitious work though.

Labels: RFC