MedianRank

Bases: RankBasedMetric

The median rank.

The median rank is a robust measure of central tendency that is less sensitive to outliers than the arithmetic mean. For a set of ranks \(\mathcal{I}\), the median is the middle value when ranks are sorted.

Warning

Like other rank-based metrics, the median rank is dependent on the number of candidates. A median rank of 10 has different interpretations for a candidate set size of 100 versus 1,000,000.

Weighted Median

When weights \(w_1, \ldots, w_n\) are provided, the weighted median is computed as the value \(m\) such that the cumulative weight of all ranks less than or equal to \(m\) is at least half of the total weight, and the cumulative weight of all ranks greater than or equal to \(m\) is also at least half of the total weight. Formally, the weighted median \(m\) satisfies:

\[\sum_{r_i \leq m} w_i \geq \frac{1}{2} \sum_j w_j \quad \text{and} \quad \sum_{r_i \geq m} w_i \geq \frac{1}{2} \sum_j w_j\]

The weighted median generalizes the standard median: when all weights are equal, it reduces to the unweighted median. The implementation uses PyKEEN’s weighted_median() utility function.

Expected Value (Unweighted Case)

For the unweighted case, the expected value \(\mathbb{E}[\text{Median}]\) can be computed exactly. We model each rank as \(r_i \sim \mathcal{U}(1, N_i)\) and denote by \(C(x) = \|\{i : r_i \leq x\}\|\) the number of ranks not larger than \(x\). The \(j\)-th smallest rank \(X_{(j)}\) exceeds \(x\) if and only if \(C(x) \leq j - 1\). The count \(C(x)\) is a sum of independent binomial variables, one for each group of ranking tasks with identical number of candidates \(N\), with success probability \(\min(1, x / N)\). The expected value then follows from \(\mathbb{E}[X] = \sum_{x=0}^{\infty} P(X > x)\).

The median follows numpy.median(): for an odd number \(n\) of ranks it is \(X_{(\frac{n+1}{2})}\), and for an even number of ranks it is the average \(\frac{1}{2}(X_{(n/2)} + X_{(n/2 + 1)})\) of the two middle order statistics.

Variance (Unweighted Case)

The variance is computed from the first and second moments, where for non-negative integer variables

\[\mathbb{E}[X^2] = \sum_{x=0}^{\infty} (2x + 1) \cdot P(X > x)\]

For an even number of ranks, the second moment of the average of the two middle order statistics \(A \leq B\) additionally requires \(\mathbb{E}[AB] = \sum_{a, b \geq 0} P(A > a, B > b)\), which reduces to terms of the form \(P(C(a) = m, C(b) = m)\) with \(m = n / 2\), cf. compute_median_moments(). The result is clamped to be non-negative.

Complexity

Let \(n\) be the number of ranks, \(K = \max_i N_i\), and \(g\) the number of distinct numbers of candidates.

For \(g = 1\) (e.g., full ranking against all entities), the expected value and the variance are computed in \(O(K)\) time, irrespective of \(n\).
For \(g > 1\), the expected value, and the variance for odd \(n\), take \(O(K \cdot g \cdot n \log n)\) time. Memory is bounded, as the values of \(x\) are processed in chunks.
For the variance with even \(n\) and \(g > 1\), the exact computation additionally needs \(O(K^2 \cdot g \cdot n)\) time. If this exceeds a fixed work limit, it falls back to numeric estimation via sampling (which requires num_samples to be given, and raises NoClosedFormError otherwise).

Weighted Case

Warning

Computing the expected value and variance for the weighted median is computationally intractable, as it reduces to a variant of the Subset Sum Problem (NP-complete). Therefore, when weights are provided, the metric falls back to numeric estimation via sampling, which may be slow and less accurate.

Attributes Summary

`binarize`	whether the metric needs binarized scores
`closed_expectation`	whether there is a closed-form solution of the expectation
`closed_variance`	whether there is a closed-form solution of the variance
`increasing`	whether it is increasing, i.e., larger values are better
`key`	Return the key for use in metric result dictionaries.
`name`	The name of the metric
`needs_candidates`	whether the metric requires the number of candidates for each ranking task
`supported_rank_types`	the supported rank types.
`supports_weights`	whether the metric supports weights
`synonyms`	synonyms for this metric
`value_range`	the value range

Methods Summary

`__call__`(ranks[, num_candidates, weights])	Evaluate the metric.
`expected_value`(num_candidates[, ...])	Compute expected metric value.
`extra_repr`()	Generate the extra repr, cf.
`get_description`()	Get the description.
`get_link`()	Get the link from the docdata.
`get_range`()	Get the math notation for the range of this metric.
`get_sampled_values`(num_candidates, num_samples)	Calculate the metric on sampled rank arrays.
`iter_extra_repr`()	Iterate over the components of the `extra_repr()`.
`numeric_expected_value`(**kwargs)	Compute expected metric value by summation.
`numeric_expected_value_with_ci`(**kwargs)	Estimate expected value with confidence intervals.
`numeric_variance`(**kwargs)	Compute variance by summation.
`numeric_variance_with_ci`(**kwargs)	Estimate variance with confidence intervals.
`std`(num_candidates[, num_samples, weights])	Compute the standard deviation.
`variance`(num_candidates[, num_samples, weights])	Compute variance.

Attributes Documentation

binarize: ClassVar[bool] = False: whether the metric needs binarized scores

closed_expectation: ClassVar[bool] = True: whether there is a closed-form solution of the expectation

closed_variance: ClassVar[bool] = True: whether there is a closed-form solution of the variance

increasing: ClassVar[bool] = False: whether it is increasing, i.e., larger values are better

key: Return the key for use in metric result dictionaries.

name: ClassVar[str] = 'Median Rank': The name of the metric

needs_candidates: ClassVar[bool] = False: whether the metric requires the number of candidates for each ranking task

supported_rank_types: ClassVar[Collection[Literal['optimistic', 'realistic', 'pessimistic']]] = ('optimistic', 'realistic', 'pessimistic'): the supported rank types. Most of the time equal to all rank types

supports_weights: ClassVar[bool] = True: whether the metric supports weights

synonyms: ClassVar[Collection[str]] = (): synonyms for this metric

value_range: ClassVar[ValueRange] = ValueRange(lower=1, lower_inclusive=True, upper=inf, upper_inclusive=False): the value range

Methods Documentation

__call__(ranks: ndarray, num_candidates: ndarray | None = None, weights: ndarray | None = None) → float[source]

Evaluate the metric.

Parameters:

ranks (ndarray) – shape: s the individual ranks
num_candidates (ndarray | None) – shape: s the number of candidates for each individual ranking task
weights (ndarray | None) – shape: s the weights for the individual ranks

Return type:

float

expected_value(num_candidates: ndarray, num_samples: int | None = None, weights: ndarray | None = None, **kwargs) → float[source]

Compute expected metric value.

The expectation is computed under the assumption that each individual rank follows a discrete uniform distribution \(\mathcal{U}\left(1, C_i\right)\), where \(C_i\) denotes the number of candidates for ranking task \(r_i\).

Parameters:

num_candidates (ndarray) – the number of candidates for each individual rank computation
num_samples (int | None) – the number of samples to use for simulation, if no closed form expected value is implemented
weights (ndarray | None) – shape: s the weights for the individual ranking tasks
kwargs – additional keyword-based parameters passed to get_sampled_values(), if no closed form solution is available

Returns:

the expected value of this metric

Raises:

NoClosedFormError – raised if a closed form expectation has not been implemented and no number of samples are given

Return type:

float

Note

Prefers analytical solution, if available, but falls back to numeric estimation via summation, cf. RankBasedMetric.numeric_expected_value().

extra_repr() → str

Generate the extra repr, cf. :meth`torch.nn.Module.extra_repr`.

Returns:: the extra part of the repr()
Return type:: str

classmethod get_description() → str

Get the description.

Return type:: str

classmethod get_link() → str

Get the link from the docdata.

Return type:: str

classmethod get_range() → str

Get the math notation for the range of this metric.

Return type:: str

get_sampled_values(num_candidates: ndarray, num_samples: int, weights: ndarray | None = None, generator: Generator | None = None, memory_intense: bool = True) → ndarray

Calculate the metric on sampled rank arrays.

Parameters:

num_candidates (ndarray) – shape: s the number of candidates for each ranking task
num_samples (int) – the number of samples
weights (ndarray | None) – shape: s the weights for the individual ranking tasks
generator (Generator | None) – a random state for reproducibility
memory_intense (bool) – whether to use a more memory-intense variant, which draws all rank samples in a single batched (vectorized) call. Note that the metric itself is still evaluated sample by sample in a Python-level loop (via numpy.apply_along_axis()), so the speed-up is limited to the rank sampling.

Returns:

shape: (num_samples,) the metric evaluated on num_samples sampled rank arrays

Return type:

ndarray

iter_extra_repr() → Iterable[str]

Iterate over the components of the extra_repr().

This method is typically overridden. A common pattern would be

def iter_extra_repr(self) -> Iterable[str]:
    yield from super().iter_extra_repr()
    yield "<key1>=<value1>"
    yield "<key2>=<value2>"

Returns:: an iterable over individual components of the extra_repr()
Return type:: Iterable[str]

numeric_expected_value(**kwargs) → float

Compute expected metric value by summation.

The expectation is computed under the assumption that each individual rank follows a discrete uniform distribution \(\mathcal{U}\left(1, C_i\right)\), where \(C_i\) denotes the number of candidates for ranking task \(r_i\).

Parameters:: kwargs – keyword-based parameters passed to get_sampled_values()
Returns:: The estimated expected value of this metric
Return type:: float

Warning

Depending on the metric, the estimate may not be very accurate and converge slowly, cf. https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.rv_discrete.expect.html

numeric_expected_value_with_ci(**kwargs) → ndarray

Estimate expected value with confidence intervals.

Return type:: ndarray

numeric_variance(**kwargs) → float

Compute variance by summation.

The variance is computed under the assumption that each individual rank follows a discrete uniform distribution \(\mathcal{U}\left(1, C_i\right)\), where \(C_i\) denotes the number of candidates for ranking task \(r_i\).

Parameters:: kwargs – keyword-based parameters passed to get_sampled_values()
Returns:: The estimated variance of this metric
Return type:: float

Warning

Depending on the metric, the estimate may not be very accurate and converge slowly, cf. https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.rv_discrete.expect.html

numeric_variance_with_ci(**kwargs) → ndarray

Estimate variance with confidence intervals.

Return type:: ndarray

std(num_candidates: ndarray, num_samples: int | None = None, weights: ndarray | None = None, **kwargs) → float

Compute the standard deviation.

Parameters:

num_candidates (ndarray) – the number of candidates for each individual rank computation
num_samples (int | None) – the number of samples to use for simulation, if no closed form expected value is implemented
weights (ndarray | None) – shape: s the weights for the individual ranking tasks
kwargs – additional keyword-based parameters passed to variance(),

Returns:

The standard deviation (i.e. the square root of the variance) of this metric

Return type:

float

For a detailed explanation, cf. RankBasedMetric.variance().

variance(num_candidates: ndarray, num_samples: int | None = None, weights: ndarray | None = None, **kwargs) → float[source]

Compute variance.

The variance is computed under the assumption that each individual rank follows a discrete uniform distribution \(\mathcal{U}\left(1, C_i\right)\), where \(C_i\) denotes the number of candidates for ranking task \(r_i\).

Parameters:

num_candidates (ndarray) – the number of candidates for each individual rank computation
num_samples (int | None) – the number of samples to use for simulation, if no closed form expected value is implemented
weights (ndarray | None) – shape: s the weights for the individual ranking tasks
kwargs – additional keyword-based parameters passed to get_sampled_values(), if no closed form solution is available

Returns:

The variance of this metric

Raises:

NoClosedFormError – Raised if a closed form variance has not been implemented and no number of samples are given

Return type:

float

Note

Prefers analytical solution, if available, but falls back to numeric estimation via summation, cf. RankBasedMetric.numeric_variance().