MNT Refactor _average_weighted_percentile to avoid double sort
#31775
Conversation
|
|
||
| result = xp.where( | ||
| is_fraction_above, | ||
| array[percentile_in_sorted, col_indices], |
There was a problem hiding this comment.
I initially thought this should be percentile_plus_one_in_sorted as from the paper, when g>0, but but searchsorted defaults to left (equals is on the right), whereas the paper defined j <= pn < j+1searchsorted effectively gives i-1 < pn <= i whereas the paper had j <= pn < j+1. This means that when pn is greater than the LHS, searchsorted's i equals j+1, from the paper.
When the quantile exactly matches an index, searchsorted's i equals j, from the paper (as the equals is on opposite sides in paper vs searchsorted).
1 similar comment
There was a problem hiding this comment.
Thanks very much @lucyleeow for diving into this. I pushed a commit to make the randomized NumPy equivalence tests stronger and checked locally that they pass with all random seeds:
SKLEARN_TESTS_GLOBAL_RANDOM_SEED="all" pytest -vl sklearn/utils/tests/test_stats.py
It seems that this PR fixes a rare edge case bug found in another PR (in addition to the CPU speed-up and memory improvements): #29641. We could write a changelog entry to document this. However, doing so would require crafting a minimal reproducer to precisely characterize the conditions under which this edge case can be triggered. Maybe we could have a generic changelog entry such as "improve CPU and memory usage in estimators and metric functions that rely on weighted percentiles and better handle edge cases" or something similar.
Please fix the conflicts and feel free to ping me again for the final review.
| When `g=0` and `percentile_indices` is at max index, quantile is perfectly at 100 | ||
| and take the average of 2x the max index. |
There was a problem hiding this comment.
| When `g=0` and `percentile_indices` is at max index, quantile is perfectly at 100 | |
| and take the average of 2x the max index. | |
| When `g=0` and `percentile_indices` is at max index, percentile rank is perfectly | |
| at 100 and take the average of 2x the max index. |
| When `g=0` and `percentile_indices` is at max index, quantile is perfectly at 100 | ||
| and take the average of 2x the max index. | ||
| """ | ||
| # Note for both spercentile_rank`s`,`percentile_indices` is already at max index |
There was a problem hiding this comment.
| # Note for both spercentile_rank`s`,`percentile_indices` is already at max index | |
| # Note for both percentile_rank`s`,`percentile_indices` is already at max index |
| Uses 'inverted_cdf' method when `average=False` (default) and | ||
| 'averaged_inverted_cdf' when `average=True`. |
There was a problem hiding this comment.
| Uses 'inverted_cdf' method when `average=False` (default) and | |
| 'averaged_inverted_cdf' when `average=True`. | |
| Implement an array API compatible (weighted version) of NumPy's 'inverted_cdf' | |
| method when `average=False` (default) and 'averaged_inverted_cdf' when | |
| `average=True`. |
Reference Issues/PRs
Supercedes #30945
What does this implement/fix? Explain your changes.
Refactor
_average_weighted_percentileso we are not just performing_weighted_percentiletwice, thus avoids sorting and computing cumulative sum twice.#30945 essentially uses the sorted indicies and calculates
_weighted_percentile(-array, 100-percentile_rank)- this was verbose and required computing cumulative sum again on the negative (you could have used symmetry to avoid computing cumulative sum in cases when fraction above is greater than 0 - i.e.,g>0from Hyndman and Fan)I've followed the Hyndman and Fan computation more closely and calculate
gand just usej+1(since we already knowj). This did make handling the case wherej+1had a sample weight of 0 (or when you have sample weight of 0 at the end of the array) more complex.Any other comments?