This cannot be an even number due to #17370, inspired by @ogrisel last paragraph in #17370 (comment), even though I agree it's a temporary fix.

Since #29907 was merged, it should be possible to update median_absolute_error to handle even number of data points (with or without weights) as explained below.

I don't quite understand why this test would be 'flaky' for median_absolute_error for the 'check that the weighted and unweighted scores are unequal' check in check_sample_weight_invariance. Both 0 and 2 fail here 🤷

To check that it was not our _weighted_percentile doing something wrong, I used numpys quantile with sample weights (which I trust, because I saw that PR and the scrutiny and all the tests):

import numpy as np

from sklearn.metrics import median_absolute_error
from sklearn.utils.validation import check_random_state

n_samples = 51
random_state = check_random_state(0)
# regression
y_true = random_state.random_sample(size=(n_samples,))
y_pred = random_state.random_sample(size=(n_samples,))

rng = np.random.RandomState(0)
sample_weight = rng.randint(1, 10, size=len(y_true))

no_weights = np.median(np.abs(y_pred - y_true), axis=0)
# gives np.float64(0.26234528145390845)

weights = np.quantile(
    np.abs(y_pred - y_true), 0.5, axis=0, method='inverted_cdf',
    weights=sample_weight
)
# gives array(0.26234528)

I may be missing something, but I don't know why this would be likely to be the same with and without wights.

Note that changing max value in sample_weight = rng.randint(1, 10, size=len(y_true)) from 10 to a smaller value, 5 or 8 etc, was also very effective.

On even numbers of samples (taking weights into account), inverted_cdf yields an asymmetric result, while np.median (on repeated samples) yields a symmetric result (as it uses the "linear" interpolation definition of "in between data points" quantiles).

We need to use a symmetric version of _weighted_percentile which named _averaged_weighted_percentile which was merged yesterday as part of #29907 which is equivalent to the method="averaged_inverted_cdf" of np.quantile.

Sorry I was not clear, random state seed being 0 or 2 fail. But 1 passes.
The specific check that is failing is:

Which is odd right? See above sanity check.

Also I agree that it would be better to use numpy implementation of weights but our min support version is not high enough. Do you think we should vendor the code?

Okay I looked into this more, and it seems that this is just not a good check for median_absolute_error (red line is median value, weighted 'median' is calculated with np.quantile(method="inverted_cdf")):

fig, axes = plt.subplots(nrows=3, ncols=3, figsize=(12, 10))

# Different weight ranges for each row
weight_ranges = [(None, "No Weights"), (np.arange(1, 10), "Weights (1-9)"), (np.arange(1, 5), "Weights (1-5)")]

# Different random seeds for each column
seeds = [0, 1, 2]

# Loop over rows (weights) and columns (seeds)
for row, (weight_range, weight_label) in enumerate(weight_ranges):
    for col, seed in enumerate(seeds):
        random_state = check_random_state(seed)
        y_true = random_state.random_sample(size=(51,))
        y_pred = random_state.random_sample(size=(51,))
        values = np.abs(y_pred - y_true)

        rng = np.random.RandomState(seed)
        sample_weight = rng.randint(weight_range.min(), weight_range.max() + 1, size=len(y_true)) if weight_range is not None else None

        # Plot histogram
        if sample_weight is None:
            axes[row, col].hist(values, bins=15, edgecolor="black", alpha=0.7, density=True)
            median_value = np.median(values)
        else:
            axes[row, col].hist(values, bins=15, weights=sample_weight, edgecolor="black", alpha=0.7, density=True)
            median_value = np.quantile(values, 0.5, method="inverted_cdf", weights=sample_weight)

        # Add median line
        axes[row, col].axvline(median_value, color="red", linestyle="dashed", linewidth=1, label="Median")

        # Set title
        axes[row, col].set_title(f"Seed {seed} - {weight_label}")
# Adjust layout for readability
plt.tight_layout()
plt.show()

Weights don't change the distribution of abs(y_pred - y_true) enough to change the median value.

We can change the test to make this check (e.g., we could try adding only high or low weights to a subset of the values), but I am not 100% sure about changing checking this for all regression metrics. To be fair this test is just ensuring that weighted and un-weighted are different, so it should probably be okay?

cc @ogrisel

Also I agree that it would be better to use numpy implementation of weights but our min support version is not high enough. Do you think we should vendor the code?

If the complexity of vendoring is not to high, we should definitely benefit from it.

Considering we added _averaged_weighted_percentile recently in #29907 and also the open PR #29034 , I agree that vendoring is a good option... (as we are having to spend a lot of effort maintaining this function anyway)

OK I see. I think that I would define weights as np.arange(len(y_true)) and I think that it would good enough for this test. I indeed agree with your analysis @lucyleeow.

I'll check the subsequent changes in the test to see if np.arange could be an issue.

I would like to use _averaged_weighted_percentile directly to latter be able to add an array API compatible version.

At the time of writing numpy.quantile(..., method="averaged_inverted_cdf") does not support weights (yet) and is not part of the array API spec. So we need a version that supports both weights, the symmetric behavior with even numbers of data points, and possible array API support.

Changed as suggested in #30787 (comment). This works great.

I've amended check_sample_weight_invariance to optionally take sample_weight as I didn't want to change the sample_weight for all tests that use check_sample_weight_invariance, WDYT @glemaitre ?

This is a problem due to numerical instability in cumulative sum (NOT fixed by stable_cumsum) in _weighted_percentile. It is rare for this problem to appear.

In this test, the final value in cumulative_sum was a small amount (within tolerance in stable_cumsum) higher than 'actual' value, this resulted in the adjusted_percentile_rank being a small amount higher than the 'actual' value:

adjusted_percentile_rank was 17.400000000000002 , when it should have been 17.4, which just happens to be a value in weight_cdf. Thus when we do searchsorted

the index should be that of the 17.4 element in weight_cdf, but instead it is the next index. stable_cumsum does not fix this particular problem as it does not matter how close adjusted_percentile_rank value is to the true value, if the true value is itself present within weight_cdf, searchsorted will take the adjacent index.

Note that I checked using numpy.quantile (with "inverted_cdf`, which now supports weights) and got the same test failure).

For completeness, I will reference the recent discussion regarding use of stable_cumsum (#29431 (comment)) - it was decided to not be required in _weighted_percentile (cc @ogrisel).
Further numpy's quantile implementation simply uses cumsum.

Note that I checked using numpy.quantile (with "inverted_cdf`, which now supports weights) and got the same test failure).

Can you check the behavior of numpy.quantile with "averaged_inverted_cdf" and _averaged_weighted_percentile on this kind of edge case?

EDIT: I am not sure if the comment above was written before the switch from _weighted_percentile to _averaged_weighted_percentile or not.

Sorry I should have clarified that the failure persists with _averaged_weighted_percentile. But I agree that I also thought _averaged_weighted_percentile should fix the problem so I did some more digging.

_averaged_weighted_percentile errors with:

E           Max absolute difference among violations: 0.00704464
E           Max relative difference among violations: 0.0095152
E            ACTUAL: array(0.733313)
E            DESIRED: array(0.740357)

_weighted_percentile errors with:

E           Max absolute difference among violations: 0.01408929
E           Max relative difference among violations: 0.01903039
E            ACTUAL: array(0.726268)
E            DESIRED: array(0.740357)

So _averaged_weighted_percentile halves the error. And the reason is because:

• with (+)array the cumulative sum has the instability problem (i.e. adjusted_percentile_rank is 17.400000000000002)
• with -array the cumulative sum does not have the instability problem (i.e. adjusted_percentile_rank is 17.4) 🙃

If cumulative sum had the instability problem with both array and -array I think the problem would have been fixed.
numpy.quantile with weights only supports inverted_cdf (I double checked in dev docs https://numpy.org/devdocs/reference/generated/numpy.quantile.html and numpy PRs).

🙃

Just documenting a reminder to myself - potentially when we refactor _averaged_weighted_percentile to avoid sorting twice, we won't use -array, in which case scale=0.3 may pass.

(I've been wanting to do the refactoring, but it has not reached the top of my todo yet 😬 )