Talip7/scikit-learn-issues-multilabel huggingface dataset:
RFC: Allow training random forests with histograms on binned feature values

This issue is very related to #27873.

If/when the above is implemented, it should also be possible to refactor the tree code to leverage histogram splits for bagging-based tree ensembles.

Histogram-based split is the main reason, while scikit-learn-intelex's `RandomForestClassifier` is much faster that our `RandomForestClassifier` when trained on datasets with many data points.

COMMENT:
I agree that dynamic histograms are an interesting idea worth exploring, both for RFs and GB models. Since RFs typically have deeper trees, they will likely benefit the most of it. However, it would be great to have GB models that work efficiently on smaller datasets as well. This way we could wrap them inside a `BaggingRegressor`/`Classifier` and get a favorable resolution / calibration / speed tradeoff as a result for small to medium data.

Labels: RFC
RFC: Allow training random forests with histograms on binned feature values

This issue is very related to #27873.

If/when the above is implemented, it should also be possible to refactor the tree code to leverage histogram splits for bagging-based tree ensembles.

Histogram-based split is the main reason, while scikit-learn-intelex's `RandomForestClassifier` is much faster that our `RandomForestClassifier` when trained on datasets with many data points.

COMMENT:
> For my education: what you mean is using something like a Pipeline with KBinsDiscretizer followed by a RandomForestClassifier (with a specialised treatment that is based on the knowledge that all features are now binned)?

@betatim this is only half of the work. Once the feature values are binned, the node splitter can/should leverage this to find optimal splits using histograms (complexity: O(n) where n is the number of training data points that reached that node) instead of sort-based splits (complexity: O(n log(n))). `HistGradientBoostingClassifer/Regressor` do histogram based splits (on internally binned feature values) while `GradientBoostingClassifier/Regressor` and `RandomForestClassifier/Regressor` use regular sort-based splits on the original continuous feature values.

EDIT: I had not considered the possible interplay between discretized feature values and various sorting algorithms described in the second part of https://github.com/scikit-learn/scikit-learn/issues/32704#issuecomment-3542914553 when first writing this comment. Things are probably a bit more complex than the naive complexity analysis above. Also the interplay with threading and memory bandwidth constraints would be important to investigate further.

Labels: RFC
RFC: Allow training random forests with histograms on binned feature values

This issue is very related to #27873.

If/when the above is implemented, it should also be possible to refactor the tree code to leverage histogram splits for bagging-based tree ensembles.

Histogram-based split is the main reason, while scikit-learn-intelex's `RandomForestClassifier` is much faster that our `RandomForestClassifier` when trained on datasets with many data points.

COMMENT:
Some thoughts:

**binning + MAE criterion:**
- I'm pretty sure histogram based split is not compatible with MAE criterion (try to think about how computing the median in a "histogram-way", pretty sure it's not feasible).Suel
- Because of that, binning would not bring a significant speed up for MAE (because MAE splitting run time is dominated by `precompute_absolute_errors` anyway, so making the sort/partitioning faster is kinda pointless).

=> it would be ok not to support binning + MAE criterion, it wouldn't bring a lot of value.

----

**binning + deep trees**

I said that histogram based splitting is not adapted for deep trees: well maybe this can be mitigated. And because it's incredibly fast for the first "floors" of the tree, the overall speed might be great.
But the current implementation will not be easy to adapt, especially if we want to keep the `prange`s.

I'm experimenting with my idea of O(n) bin-based sorting, and I think it's promising, we can gain a ~10x speed-up. I guess histogram based splitting could be even faster though. The implementation I would has a good memory locality.

---

**binning + other criteria:**

I need to give it some serious thinking to be sure, but I think other criteria (gini, log-loss, mse, poisson) are compatible with histogram based splitting, including multi-class and multi-output cases I think. 
... Might be a mess to implement though 😅 

---

I noticed almost nothing scales well with the number of threads on my laptop. So I can't really do benchmarks with multi-threading :/

Labels: RFC
RFC: Allow training random forests with histograms on binned feature values

This issue is very related to #27873.

If/when the above is implemented, it should also be possible to refactor the tree code to leverage histogram splits for bagging-based tree ensembles.

Histogram-based split is the main reason, while scikit-learn-intelex's `RandomForestClassifier` is much faster that our `RandomForestClassifier` when trained on datasets with many data points.

COMMENT:
> binning + MAE criterion:
>…I'm pretty sure histogram based split is not compatible with MAE criterion

I don’t think this is an obstacle. The features X are binned, not the (unbinned) target y. The median is computed on y. Also, it works for HGB and the line search step computes quantiles/medians on y.

To check the impact on prediction performance, @betatim‘s idea of using a pipeline with kbinsdiscretizer is a good one. Sure, an native implementation would then improve the fit time.

Labels: RFC
RFC: Allow training random forests with histograms on binned feature values

This issue is very related to #27873.

If/when the above is implemented, it should also be possible to refactor the tree code to leverage histogram splits for bagging-based tree ensembles.

Histogram-based split is the main reason, while scikit-learn-intelex's `RandomForestClassifier` is much faster that our `RandomForestClassifier` when trained on datasets with many data points.

COMMENT:
> To check the impact on prediction performance, @betatim‘s idea of using a pipeline with kbinsdiscretizer is a good one. Sure, a native implementation would then improve the fit time.

The main point of dynamic (approx) binning is two-fold:
1. improve efficiency (bias/variance) tradeoff of learning
2. improve runtime efficiency.

To my understanding, the kbinsdiscretizer + current implementation of decision trees would not improve much the bias/variance tradeoff (performance) nor runtime performance  since it's i) binning your data once, and ii) split finding doesn't take advantage of the binned data types, so it's still doing O(n log n).

> I don’t think this is an obstacle. The features X are binned, not the (unbinned) target y. The median is computed on y. Also, it works for HGB and the line search step computes quantiles/medians on y.

+1.

Labels: RFC
RFC: Allow training random forests with histograms on binned feature values

This issue is very related to #27873.

If/when the above is implemented, it should also be possible to refactor the tree code to leverage histogram splits for bagging-based tree ensembles.

Histogram-based split is the main reason, while scikit-learn-intelex's `RandomForestClassifier` is much faster that our `RandomForestClassifier` when trained on datasets with many data points.

COMMENT:
@betatim Your summer student still has to learn about forests and trees. Random forests like very random deep trees, gradient grown forests like shallow trees. LightGBM's default parameters have gradient grown trees in mind.
One of the biggest differences is
- scikit-learn `RandomForestClassifier` defaults to `min_samples_split=2` and `min_samples_leaf=1`
- LightGBM defaults to `min_data_in_leaf=20`

Labels: RFC
RFC: Allow training random forests with histograms on binned feature values

This issue is very related to #27873.

If/when the above is implemented, it should also be possible to refactor the tree code to leverage histogram splits for bagging-based tree ensembles.

Histogram-based split is the main reason, while scikit-learn-intelex's `RandomForestClassifier` is much faster that our `RandomForestClassifier` when trained on datasets with many data points.

COMMENT:
> > I'm pretty sure histogram based split is not compatible with MAE criterion
> 
> I don’t think this is an obstacle. The features X are binned, not the (unbinned) target y. The median is computed on y. Also, it works for HGB and the line search step computes quantiles/medians on y.

Sorry, my message was not super clear: it's totally possible to do binning + MAE criterion. But I maintain that it's impossible to adapt the histogram-based splitting algorithm to the MAE criterion.

What we mean by "histogram-based splitting algorithm" is the following algorithm:

For most criteria, binning lets you find the best split in two efficient steps (for each feature):
- Compute some kind of aggregates per bin (sum of targets per bin, counts per bin, ...). This is what we call a histogram in the HGB code. This step is O(n) and is highly optimized in the HGB code.
- Use this histogram to find the best split in O(n_bins). This works because, for instance, sum_left = sum of bin_sum for bins on the left. You don't have such property for the median.

This is efficient because it's O(n) overall. Moreover, it has a fairly good memory access pattern/locality and a small memory footprint, so it can be efficiently parallelized over features.

(I'll let @ogrisel thumbs up if my explanation of histogram-based splits is correct.)

Now my claim: it's not possible to apply this algorithm for the MAE criterion; moreover, the best complexity you can get for finding the best split with the MAE criterion is O(n log n) - or O(n * n_bins), which is good if you have only a few bins but not great for 256 bins.

Labels: RFC
CI Collect coverage results on the CUDA CI

We currently don't collect and report coverage information to codecov for the CUDA CI, see https://github.com/scikit-learn/scikit-learn/pull/31829#issuecomment-3503237010

The `.github/workflows/unit-tests.yml` script contains a working setup for collecting coverage and uploading it to codecov using GitHub Actions. This is probably a good starting point for the CUDA CI which is defined in `.github/workflows/cuda-ci.yml`. We might also have to adjust the options passed to `pytest` in the CUDA CI so that it generates coverage statistics.

One thing to double check/think about is how having a CI that only runs sometimes ends up being displayed on codecov when comparing commits. For example, if `main` has no coverage for some code because we don't run the CUDA CI on `main` will it always look like you have missing coverage on a PR? Or does it not matter because our coverage requirements are calculated on the diff only?

COMMENT:
Uploading coverage for the CUDA CI seems doable in finite time but I am wondering about how useful this would actually be in practice.

As an not-related data point, we don't have coverage on Windows (was removed because it was too slow a while ago) and I don't think that it a blind spot that has harmed us in the past.

Personally I only look at the coverage when it is red and if the not covered lines are a bit of an edge case, I am like "let's not bother about it".

> One thing to double check/think about is how having a CI that only runs sometimes ends up being displayed on codecov when comparing commits

I think [patch coverage](https://about.codecov.io/blog/why-patch-coverage-is-more-important-than-project-coverage/) is based on difference between the PR and `main` (or the common ancestor 
between the PR branch and `main`?) and not between one commit and the next one.

The codecov page tells you the commit it is comparing against for example this [one](https://app.codecov.io/gh/scikit-learn/scikit-learn/pull/31829)

<img width="1090" height="771" alt="Image" src="https://github.com/user-attachments/assets/e781ed79-1f25-4298-b455-6248d119092a" />

> One thing to double check/think about is how having a CI that only runs sometimes ends up being displayed on codecov when comparing commits. For example, if main has no coverage for some code because we don't run the CUDA CI on main will it always look like you have missing coverage on a PR?

If I had a bet to place, I would guess it's the other way around, a PR with the CUDA label will always have more coverage than `main` (assuming we don't run the CUDA CI on `main` which is what we do currently)? I would guess that the additional coverage would be quite small though and would be ignored in practice.

Labels: Build / CI, Array API
CI Collect coverage results on the CUDA CI

We currently don't collect and report coverage information to codecov for the CUDA CI, see https://github.com/scikit-learn/scikit-learn/pull/31829#issuecomment-3503237010

The `.github/workflows/unit-tests.yml` script contains a working setup for collecting coverage and uploading it to codecov using GitHub Actions. This is probably a good starting point for the CUDA CI which is defined in `.github/workflows/cuda-ci.yml`. We might also have to adjust the options passed to `pytest` in the CUDA CI so that it generates coverage statistics.

One thing to double check/think about is how having a CI that only runs sometimes ends up being displayed on codecov when comparing commits. For example, if `main` has no coverage for some code because we don't run the CUDA CI on `main` will it always look like you have missing coverage on a PR? Or does it not matter because our coverage requirements are calculated on the diff only?

COMMENT:
In the linked PR it came up that we are missing a bit of coverage. Hence this issue. If it isn't a lot of work and doesn't add a lot of runtime I'd vote for adding it. But low priority.

Labels: Build / CI, Array API
CI Collect coverage results on the CUDA CI

We currently don't collect and report coverage information to codecov for the CUDA CI, see https://github.com/scikit-learn/scikit-learn/pull/31829#issuecomment-3503237010

The `.github/workflows/unit-tests.yml` script contains a working setup for collecting coverage and uploading it to codecov using GitHub Actions. This is probably a good starting point for the CUDA CI which is defined in `.github/workflows/cuda-ci.yml`. We might also have to adjust the options passed to `pytest` in the CUDA CI so that it generates coverage statistics.

One thing to double check/think about is how having a CI that only runs sometimes ends up being displayed on codecov when comparing commits. For example, if `main` has no coverage for some code because we don't run the CUDA CI on `main` will it always look like you have missing coverage on a PR? Or does it not matter because our coverage requirements are calculated on the diff only?

COMMENT:
> In the linked PR it came up that we are missing a bit of coverage. Hence this issue.

Yep I got that. I was talking mostly about `main` without CUDA CI compared to PR with CUDA CI (in the case we do add coverage to the CUDA CI), which I thought was one of the worries/questions.

Labels: Build / CI, Array API
CI Collect coverage results on the CUDA CI

We currently don't collect and report coverage information to codecov for the CUDA CI, see https://github.com/scikit-learn/scikit-learn/pull/31829#issuecomment-3503237010

The `.github/workflows/unit-tests.yml` script contains a working setup for collecting coverage and uploading it to codecov using GitHub Actions. This is probably a good starting point for the CUDA CI which is defined in `.github/workflows/cuda-ci.yml`. We might also have to adjust the options passed to `pytest` in the CUDA CI so that it generates coverage statistics.

One thing to double check/think about is how having a CI that only runs sometimes ends up being displayed on codecov when comparing commits. For example, if `main` has no coverage for some code because we don't run the CUDA CI on `main` will it always look like you have missing coverage on a PR? Or does it not matter because our coverage requirements are calculated on the diff only?

COMMENT:
Thanks for the work you've done so far. The goal of this comment
is to set expectations.

Deciding on new features or substantial changes is a lengthy
process. It frequently happens that no maintainer is available
to take on this task right now.

Please do not create a Pull Request before a decision has been
made regarding the proposed work. Making this decision can
often take a significant amount of time and effort.

Labels: Build / CI, Array API
CI Collect coverage results on the CUDA CI

We currently don't collect and report coverage information to codecov for the CUDA CI, see https://github.com/scikit-learn/scikit-learn/pull/31829#issuecomment-3503237010

The `.github/workflows/unit-tests.yml` script contains a working setup for collecting coverage and uploading it to codecov using GitHub Actions. This is probably a good starting point for the CUDA CI which is defined in `.github/workflows/cuda-ci.yml`. We might also have to adjust the options passed to `pytest` in the CUDA CI so that it generates coverage statistics.

One thing to double check/think about is how having a CI that only runs sometimes ends up being displayed on codecov when comparing commits. For example, if `main` has no coverage for some code because we don't run the CUDA CI on `main` will it always look like you have missing coverage on a PR? Or does it not matter because our coverage requirements are calculated on the diff only?

COMMENT:
If someone wants to implement this, it would be welcome. It should mostly be a question of copying the relevant bit of `.github/workflows/unit-tests.yml` to the `cuda-ci.yml`. Then fixing what doesn't work.

It isn't a super high priority though as we only rarely run into the problem of missing coverage.

Labels: Build / CI, Array API
Clarify docs for allowable KDTree metrics

### Describe the issue linked to the documentation

https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html currently states, for the metrics kwarg: "Metric to use for distance computation. Default is “minkowski”, which results in the standard Euclidean distance when p = 2. A list of valid metrics for KDTree is given by the attribute valid_metrics. See the documentation of [scipy.spatial.distance](https://docs.scipy.org/doc/scipy/reference/spatial.distance.html) and the metrics listed in [distance_metrics](https://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.distance_metrics.html#sklearn.metrics.pairwise.distance_metrics) for more information on any distance metric."

Yet clicking on `distance_metrics` yields the following list of metrics: cityblock, cosine, euclidean, haversine, l1, l2, manhattan, nan_euclidean, which is different from the actual list of supported metrics (euclidean, l2, minkowski, p, manhattan, cityblock, l1, chebyshev, infinity).  I could not find this list other than by actually printing out the value of `KDTree.valid_metrics`.

### Suggest a potential alternative/fix

Explicitly list the actually supported metrics in the docs (or at least, not link to a list that is different).

A few minor related possible improvements:
- There's a formatting issue immediately after the `metric` kwarg in https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html; likely the "Note:" should be moved to a real rst note (or indented as part of the doc for the metric kwarg).
- The list in https://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.distance_metrics.html could group together equivalent metrics ("'l1', 'cityblock', 'manhattan': metrics.pairwise.manhattan_distance; 'l2', 'euclidean': ..., )

COMMENT:
Hello, I am a new contributor and would like to try and fix this documentation issue. Can I be assigned?

Labels: Documentation
Clarify docs for allowable KDTree metrics

### Describe the issue linked to the documentation

https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html currently states, for the metrics kwarg: "Metric to use for distance computation. Default is “minkowski”, which results in the standard Euclidean distance when p = 2. A list of valid metrics for KDTree is given by the attribute valid_metrics. See the documentation of [scipy.spatial.distance](https://docs.scipy.org/doc/scipy/reference/spatial.distance.html) and the metrics listed in [distance_metrics](https://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.distance_metrics.html#sklearn.metrics.pairwise.distance_metrics) for more information on any distance metric."

Yet clicking on `distance_metrics` yields the following list of metrics: cityblock, cosine, euclidean, haversine, l1, l2, manhattan, nan_euclidean, which is different from the actual list of supported metrics (euclidean, l2, minkowski, p, manhattan, cityblock, l1, chebyshev, infinity).  I could not find this list other than by actually printing out the value of `KDTree.valid_metrics`.

### Suggest a potential alternative/fix

Explicitly list the actually supported metrics in the docs (or at least, not link to a list that is different).

A few minor related possible improvements:
- There's a formatting issue immediately after the `metric` kwarg in https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html; likely the "Note:" should be moved to a real rst note (or indented as part of the doc for the metric kwarg).
- The list in https://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.distance_metrics.html could group together equivalent metrics ("'l1', 'cityblock', 'manhattan': metrics.pairwise.manhattan_distance; 'l2', 'euclidean': ..., )

COMMENT:
@yaswinrajm no you cannot. You've commented on the issue before the "needs triage" is removed, and the original poster should have the chance to fix the issue themselves if we decide this is something we'd like to have. You posting to be assigned w/o considering these things and w/o reading the issues will result in you being banned from the org.

Labels: Documentation