scikit-learn: _weighted_percentile does not lead to the same result than np.median

While reviewing a test in https://github.com/scikit-learn/scikit-learn/pull/16937, it appears that our implementation of _weighted_percentile with unit sample_weight will lead to a different result than np.median which is a bit problematic for consistency.

In the gradient-boosting, it brakes the loss equivalence because the initial predictions are different. We could bypass this issue by always computing the median using _weighted_percentile there.

import pytest
import numpy as np
from sklearn.utils.stats import _weighted_percentile

rng = np.random.RandomState(42)
X = rng.randn(10)
X.sort()
sample_weight = np.ones(X.shape)

median_numpy = np.median(X)
median_numpy_percentile = np.percentile(X, 50)
median_sklearn = _weighted_percentile(X, sample_weight, percentile=50.0)

assert median_numpy == pytest.approx(np.mean(X[[4, 5]]))
assert median_sklearn == pytest.approx(X[4])
assert median_numpy == median_numpy_percentile
assert median_sklearn == pytest.approx(median_numpy)

About this issue

  • Original URL
  • State: closed
  • Created 6 years ago
  • Comments: 20 (20 by maintainers)

Most upvoted comments

Preface: I still consider this a non-issue because it’s mainly about cosmetics. The impact of different quantile methods on real use cases is well within the (usual) statistical uncertainty.

Main Part: The symmetrised version that @ogrisel is proposing is, if I’m not mistaken, the same as method="averaged_inverted_cdf". This is the only other method (besides "inverted_cdf"), for which I would consider to implement a weighted version in numpy.

Epilogue: Do we really want to discuss quantile methods again? See Fan & Hyndman (1996) and Sample quantiles 20 years later (Hyndman 2916).

I think this can be closed now that we have _average_weighted_percentile (which always gives the same value as median).

symmetrised version that @ogrisel is proposing is, if I’m not mistaken, the same as method=“averaged_inverted_cdf”

Just to document, I double checked this and I think they are the same. “averaged_inverted_cdf” sets $m=0$, such that $j\le pn\lt j+1$ , and:

\gamma = \left\{
\begin{array}{ll}
\frac{1}{2} & \text{if } g = 0 \\
1 & \text{if } g > 0
\end{array}
\right.

in the general equation $Q_{i}(p)=(1-\gamma)X_{(j)}+\gamma X_{(j+1)}$

np.searchsorted gives us a[i-1] < v <= a[i] (note that numpy is 0 index, whereas the paper assume 1 index, so it’s effectively a[j] < v <= a[j+1]). Thus, we get the same $j$ except when $v=j$ (i.e. the equals is on the other side). However, since we take the average of 100-percentile_rank of -array we are still taking the average of $j$ and $j+1$, so it’s the same.

When $g>0$ (i.e. fractional part is greater than 0), we are effectively taking the average of $j$ and $j+2$, which gives us $j+1$ (i.e. $\gamma=1$ in the general equation above)

I’m not sure what we should recover for a generic percentile q, but the symmetrization trick does not recover np.percentile(x_repeated, q, method="linear").

x = np.linspace(0, 1, 4)
w = np.asarray([2, 1, 1, 1])
x_repeated = x.repeat(repeats=w)
q = 60
p_lin = np.percentile(x_repeated, q, method="linear")
p_inf = np.percentile(x, q, weights=w, method="inverted_cdf")
p_sup = -np.percentile(-x, 100-q, weights=w, method="inverted_cdf")
p_mid = (p_inf + p_sup) / 2
# p_lin=0.467 p_inf=0.333 p_sup=0.667 p_mid=0.500

If I understood correctly np.median(x_repeated) is the same as np.percentile(x_repeated, 50, method="linear"), so perhaps we would like the same for a generic q ? Or is the issue only for the median (where some code uses np.median and other _weighted_percentile) ?

I think that our _weighted_precentile should offer the same default and maybe an interpolation parameter if required.

ping @lucyleeow Since you already look at the code, you might have some intuition why this is the case. We should actually have the above test as a regression test for our _weighted_percentile