Skip to content

Refactor weighted percentile functions to avoid redundant sorting #30945

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
wants to merge 1 commit into
base: main
Choose a base branch
from
Open

Refactor weighted percentile functions to avoid redundant sorting #30945

wants to merge 1 commit into from

Conversation

Nujra40
Copy link
Contributor

@Nujra40 Nujra40 commented Mar 5, 2025

REF: Integrate symmetrization in _weighted_percentile to avoid double sorting

Description

This pull request refactors the computation of weighted percentiles by integrating symmetrization directly into the _weighted_percentile function. With this change, we avoid sorting the input array twice when computing the averaged weighted percentile. The following changes have been made:

  • Added a symmetrize parameter to _weighted_percentile that, when enabled, computes the averaged weighted percentile using both positive and negative arrays.
  • Updated _averaged_weighted_percentile to leverage the new symmetrization functionality.
  • Preserved the original functionality and all existing comments.
  • Ensured that the code complies with the scikit-learn contributing guidelines and passes all relevant tests.

This refactor improves efficiency without altering the external API or behavior.

Please review and let me know if any adjustments are required.

@github-actions GitHub Actions
Copy link

github-actions bot commented Mar 5, 2025 •
edited
Loading

✔️ Linting Passed

All linting checks passed. Your pull request is in excellent shape! ☀️

Generated for commit: f45abdb. Link to the linter CI: here

@Nujra40 Nujra40 marked this pull request as draft March 5, 2025 10:06
@betatim
Copy link
Member

betatim commented Mar 5, 2025 •
edited
Loading

Thanks for opening this PR! It is still a draft, so I've not looked at the diff too closely yet. I wanted to raise one thing already though: how did you decide to do this work? The reason I am asking is that I think the new code is quite a bit more complex than what it replaced, so having some benchmarks or motivation for why making this change is worth it would be good to have.

There is a TODO comment in the code that suggests making this change, but I think we need to remember/figure out again why that comment was put there. IMHO the comment itself isn't a good enough motivation

@Nujra40
Copy link
Contributor Author

Nujra40 commented Mar 5, 2025

Hi @betatim

Thanks for your feedback! I'm new to open source and eager to contribute. I found this TODO and thought it would make a difference, but I see your point about complexity. I’d love any advice—not just on this PR but on open source in general. Looking forward to your thoughts!

@ogrisel ogrisel mentioned this pull request Mar 21, 2025
Open
7 tasks
@ogrisel
Copy link
Member

ogrisel commented Mar 21, 2025

As the author of the TODO, I confirm that this refactoring is needed; otherwise we won't be able to generalize the use of this function throughout the code base whenever it's needed to fix sample_weight related problems (see #16298) without introducing significant performance regressions.

@ogrisel
Copy link
Member

ogrisel commented Mar 21, 2025

Note that there is also a concurrent PR that refactors this function for a different purpose:

Not sure which will be ready to merge first, but both are valuable and once one is merged, the other will need to be adapted accordingly.

@Nujra40 Nujra40 marked this pull request as ready for review April 4, 2025 09:48
@ogrisel
Copy link
Member

ogrisel commented Apr 4, 2025 •
edited
Loading

@Nujra40 there are a bunch of failing tests. Would you mind trying to fix the code to get them to pass before we start the review? Unless you need help to solve some of them, if so please ask in the comments:

FAILED tests/test_common.py::test_estimators[KBinsDiscretizer(quantile_method='averaged_inverted_cdf')-check_sample_weights_shape] - IndexError: index -1 is out of bounds for axis 0 with size 0
FAILED tests/test_common.py::test_estimators[KBinsDiscretizer(quantile_method='averaged_inverted_cdf')-check_sample_weights_not_overwritten] - IndexError: index -1 is out of bounds for axis 0 with size 0
FAILED tests/test_common.py::test_estimators[KBinsDiscretizer(quantile_method='averaged_inverted_cdf',subsample=None)-check_sample_weight_equivalence_on_dense_data] - AssertionError: 
FAILED preprocessing/tests/test_discretization.py::test_fit_transform[quantile-averaged_inverted_cdf-expected5-sample_weight5] - AssertionError: 
FAILED preprocessing/tests/test_discretization.py::test_fit_transform[quantile-averaged_inverted_cdf-expected6-sample_weight6] - AssertionError: 
FAILED preprocessing/tests/test_discretization.py::test_fit_transform[quantile-averaged_inverted_cdf-expected7-sample_weight7] - AssertionError: 
FAILED preprocessing/tests/test_discretization.py::test_fit_transform_n_bins_array[quantile-averaged_inverted_cdf-expected4-sample_weight4] - AssertionError: 
FAILED preprocessing/tests/test_discretization.py::test_fit_transform_n_bins_array[quantile-averaged_inverted_cdf-expected5-sample_weight5] - AssertionError: 
FAILED preprocessing/tests/test_discretization.py::test_fit_transform_n_bins_array[quantile-averaged_inverted_cdf-expected6-sample_weight6] - AssertionError: 
FAILED preprocessing/tests/test_discretization.py::test_kbinsdiscretizer_effect_sample_weight - AssertionError: 
FAILED utils/tests/test_stats.py::test_averaged_weighted_median - AssertionError
FAILED utils/tests/test_stats.py::test_averaged_weighted_percentile - AssertionError
FAILED utils/tests/test_stats.py::test_averaged_and_weighted_percentile - AssertionError

See the continuous integration logs ("failing checks") for details.

Furthermore, @lucyleeow's #29431 PR has just been merged in main so this PR's branch needs to be updated by merging the current main branch into it and solve the conflicts before proceeding further. Please let us know if you need help.

@Nujra40
Copy link
Contributor Author

Nujra40 commented Apr 5, 2025

Hi @ogrisel I will look into it and get back to you if required.

@Nujra40 Nujra40 closed this Apr 5, 2025
@Nujra40 Nujra40 force-pushed the refactor/weighted-percentile-symmetrization branch from 7b943ae to 00d3ef9 Compare April 5, 2025 17:08
@Nujra40 Nujra40 reopened this Apr 5, 2025
@Nujra40
Copy link
Contributor Author

Nujra40 commented Apr 6, 2025

Hi @ogrisel Need some help to figure out whats wrong. Is the tests not complete for my added parts of the code?

@lucyleeow
Copy link
Member

@Nujra40

Looking at codecov: https://app.codecov.io/gh/scikit-learn/scikit-learn/pull/30945?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=checks&utm_campaign=pr+comments&utm_term=scikit-learn

It seems to be complaining about these 2 lines being untested:

image

lucyleeow
lucyleeow reviewed Apr 7, 2025
View reviewed changes
sklearn/utils/stats.py
@@ -41,13 +43,17 @@ def _weighted_percentile(array, sample_weight, percentile_rank=50, xp=None):
xp : array_namespace, default=None
The standard-compatible namespace for `array`. Default: infer.

symmetrize : bool, default=False
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nit about this name - could we make it more consistent with how it's named elsewhere? I know this function is private and we ultimately would like to use the scipy quantile so we don't have to maintain our own, but it would still be nice if it was clearer what this method was equivalent to.

I think this quantile method is called "averaged_inverted_cdf" in numpy/scipy. And we were calling it _averaged_weighted_percentile. I can understand "symmetrize" term but what about "average" or "average_inverted" etc ?

sklearn/utils/stats.py
return result[0] if n_dim == 1 else result


# TODO: refactor to do the symmetrisation inside _weighted_percentile to avoid
# sorting the input array twice.
def _averaged_weighted_percentile(array, sample_weight, percentile_rank=50, xp=None):
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why not just replace instances of _averaged_weighted_percentile with _weighted_percentile(symmetrize=True) ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@lucyleeow lucyleeow lucyleeow left review comments

At least 1 approving review is required to merge this pull request.

Assignees
No one assigned
Labels
module:utils
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
4 participants
@Nujra40 @betatim @ogrisel @lucyleeow