Talip7/scikit-learn-issues-multilabel huggingface dataset:
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:
@cakedev0 Thanks for your efforts.

I suggest to search for reviewer capacity ahead of PRs and align with those about the order/priority of possible PRs.
Anyone who volunteers to review such PRs?

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:
About sorting: @thomasjpfan changed sorting in #22868 (which I merged). But later a performance regression was detected and the PR reverted. Numpy also invested a lot in SIMD accelerated sorting routines...

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:
This RFC is precisely a way to align on priorities. 

What I understood for now: performance work is welcomed but binning and categorical support have a higher priority. Binning is a priority mostly for performance reasons.

My main focus is on those two topics, but they both have a strong performance component, so I think it makes sense to think about how they fit in a broader strategy for performance improvement.

Anyway, I don't plan to open any big PR on trees while #32119 is not merged.

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:
About sorting: I'm not surprised something like that* happened due to the variability in the geometry of the problem, esp. this point I mentioned above:

> distribution of the data (small/high number of unique values, repeated values, etc.): this affects a lot the benefits or not of different sorting strategies (or not sorting).

The sort that is currently implemented in trees is really efficient for some cases (e.g. geometric law, binary variable, ...), even more than the SIMD-accelerated sort from numpy. And those cases are common for tabular data.

Numpy does a 2-way partitioning quicksort, while trees uses a 3-way partitioning quicksort.

*that =  perf regression after changing the sort

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:
I personally would really like to see native categorical support because this is not only a performance improvement but simplifies the pipeline quite a bit => user friendly.

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:
I would recommend considering performance improvement based on single threaded executions profiling records (one better optimise what one can measure).

`py-spy`, `perf(1)`, `samply` with speedscope or Firefox profiler are handy for such work.

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:
I use `py-spy` a lot, it's really nice. I use `perf stat` a bit too, to try to measure memory contention.

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:
It might also be worth understanding whether free-threading builds helps with some GIL-contention we observed in the past (see https://github.com/scikit-learn/scikit-learn/discussions/20651).

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:
> I had a spare minute and wondered what kind of benchmark cases/scenarios would highlight the differences between scikit-learn and lightgbm's random forest classifier implementation. I used lightgbm because it looks like it has a useful RF implementation. So I asked Cursor to generate a benchmark script.

@antoinebaker and @ogrisel also have done quite a bit of benchmarking comparing the different libraries AFAIK. Maybe they could share some information here.

Labels: RFC
RFC: Add deflation process to PLSSVD

### Describe the workflow you want to enable

At the moment, `PLSSVD` performs SVD once on $X^TY$ and uses the singular vectors in the transform method. However, PLS-SVD in the literature often includes a deflation step.

The [reference paper](https://stat.uw.edu/sites/default/files/files/reports/2000/tr371.pdf) in the [User Guide](https://scikit-learn.org/stable/modules/cross_decomposition.html) mentions an additional deflation step. On page 15, the paper states that for the second component, the updated value in PLS-SVD is

$$X^TY-d_1u_1v_1^T.$$

Other sources like [this paper](https://hal.science/hal-00300204/document) also include deflation process for PLS-SVD.

### Describe your proposed solution

I propose two options for implementation.
1. Implement `deflation_mode='covariance'` in `_PLS` and have `PLSSVD` inherit from it.
2. Deprecate `PLSSVD` and implement `algorithm='pls_svd'` in `_PLS`. 

The first option would be easier to implement without disrupting the existing code.

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

If this is by design, we should add a note to the User Guide and the docstring to avoid confusion.

### Additional context

The User Guide and the docstring explicitly outline the current process, but I'm not sure if this implementation is different from the common conception of PLS-SVD dy design.

COMMENT:
Not a PLS expert, so I don't have a good answer about this.

To be honest, I am not sure whether improving/fixing this is really worth the effort. I don't think `PLS` is used a lot and I would guess `PLSSVD` even less.

On the other hand, tweaking the documentation, in case it is misleading, would be totally acceptable.

Labels: New Feature