mixle.stats.rankings.plackett_luce module

Create, estimate, and sample from a Plackett-Luce ranking distribution.

Defines the PlackettLuceDistribution, PlackettLuceEnumerator, PlackettLuceSampler, PlackettLuceAccumulatorFactory, PlackettLuceAccumulator, PlackettLuceEstimator, and the PlackettLuceDataEncoder classes for use with mixle.

Data type: List[int] (a full ranking of K items, given as an ordering: x[0] is the index of the top-ranked item, x[1] the second, …, x[K-1] the last). Each datum is a permutation of 0,…,K-1.

The Plackett-Luce model assigns each item a positive worth w_i (stored as log-worths so the representation is numerically stable and identified up to an additive constant; the constructor normalizes sum_i w_i = 1). The probability of an ordering x is the product of sequential softmax choices

p(x) = prod_{s=0}^{K-1} w_{x[s]} / sum_{t>=s} w_{x[t]},

so the most-preferred remaining item is drawn first, then the next, and so on. Equivalently, ranking the items by log w_i + Gumbel(0, 1) noise yields a Plackett-Luce sample, which the sampler uses.

Maximum likelihood has no closed form; the estimator runs the Minorization-Maximization (MM) update of Hunter (2004): w_i^{new} = num_i / den_i where num_i counts the rankings in which item i is not last and den_i accumulates 1 / sum_{t>=s} w_t over every stage s in which i is still in contention, evaluated at the current worths. Each fit iteration performs one MM step, monotonically increasing the likelihood.

class PlackettLuceDistribution(log_w, name=None, keys=None)

Bases: SequenceEncodableProbabilityDistribution

Plackett-Luce distribution over orderings of K items with log-worths log_w.

Data type: List[int] (an ordering: a permutation of 0,…,K-1, best-ranked item first).

Parameters:

• log_w (Sequence[float] | ndarray)

• name (str | None)

• keys (str | None)

classmethod compute_capabilities()

density(x)

Return the probability of an ordering x.

Parameters:

x (Sequence[int])

Return type:

float

log_density(x)

Return the log-probability of an ordering x.

x may be a full ranking (a permutation of 0,...,K-1) or a partial / top-m ranking (an ordered list of m <= K distinct items, best first, leaving the other K-m items unranked). For a partial ranking the sequential-choice denominator at each stage still includes the unranked items: p(x) = prod_{s=0}^{m-1} w_{x[s]} / (sum_{t>=s} w_{x[t]} + sum_{u unranked} w_u), which reduces to the full-ranking density when m = K.

Parameters:

x (Sequence[int])

Return type:

float

seq_log_density(x)

Return vectorized log-probabilities for encoded orderings.

A dense (N, K) integer array (the full-ranking encoding) is scored by the vectorized path; a ragged sequence of variable-length orderings (the partial / top-m encoding) is scored per-ranking via log_density(), which includes the unranked-item denominator term.

Parameters:

x (ndarray)

Return type:

ndarray

sampler(seed=None)

Return a sampler for drawing orderings from this distribution.

Parameters:

seed (int | None)

Return type:

PlackettLuceSampler

enumerator()

Return an exact finite enumerator over all orderings in decreasing probability order.

Return type:

PlackettLuceEnumerator

estimator(pseudo_count=None)

Return an MM estimator that keeps the item count fixed at this distribution’s K.

Parameters:

pseudo_count (float | None)

Return type:

PlackettLuceEstimator

dist_to_encoder()

Return the data encoder used by this distribution for vectorized methods.

Return type:

PlackettLuceDataEncoder

class PlackettLuceEnumerator(dist)

Bases: DistributionEnumerator

Enumerate Plackett–Luce orderings in descending probability order, lazily (A* best-first).

A ranking’s log-density is sum_k [theta_{x_k} - logsumexp(theta over the items not yet ranked at step k)]. The state is a chosen prefix with exact partial score g; the best possible completion ranks the remaining items by descending worth (which minimizes the remaining logsumexp denominators), giving an exact admissible bound h. A* on g + h streams the rankings in exact descending order without touching the n! support.

Parameters:

dist (PlackettLuceDistribution)

class PlackettLuceSampler(dist, seed=None)

Bases: DistributionSampler

Draw iid Plackett-Luce orderings via the Gumbel-max construction.

Parameters:

• dist (PlackettLuceDistribution)

• seed (int | None)

sample(size=None)

Draw orderings (permutations of 0,…,K-1); a single list when size is None.

Parameters:

size (int | None)

Return type:

list[int] | list[list[int]]

class PlackettLuceAccumulator(dim, keys=None)

Bases: SequenceEncodableStatisticAccumulator

Accumulate the Minorization-Maximization sufficient statistics for Plackett-Luce estimation.

num (non-last appearance counts) is data-only; den accumulates the stage reciprocals 1 / sum_{t>=s} w_t and is evaluated at the previous estimate (uniform worths when no estimate is supplied, which seeds the fit).

Parameters:

• dim (int)

• keys (str | None)

update(x, weight, estimate)

Parameters:

• x (Sequence[int])

• weight (float)

• estimate (PlackettLuceDistribution | None)

Return type:

None

initialize(x, weight, rng)

Parameters:

• x (Sequence[int])

• weight (float)

• rng (RandomState | None)

Return type:

None

seq_update(x, weights, estimate)

Parameters:

• x (ndarray)

• weights (ndarray)

• estimate (PlackettLuceDistribution | None)

Return type:

None

seq_initialize(x, weights, rng)

Parameters:

• x (ndarray)

• weights (ndarray)

• rng (RandomState | None)

Return type:

None

combine(suff_stat)

Parameters:

suff_stat (tuple[float, ndarray, ndarray])

Return type:

PlackettLuceAccumulator

value()

Return type:

tuple[float, ndarray, ndarray]

from_value(x)

Parameters:

x (tuple[float, ndarray, ndarray])

Return type:

PlackettLuceAccumulator

key_merge(stats_dict)

Pool this accumulator’s statistics into stats_dict under its merge key.

The structural default implements the common single-key pattern: store the accumulator under self.keys the first time the key is seen, else combine into the one already there. Accumulators with several named keys (e.g. an HMM’s init/trans/state keys) or a non-accumulator stats payload override this. A keys of None (the default) is a no-op.

Parameters:

stats_dict (dict[str, Any])

Return type:

None

key_replace(stats_dict)

Replace this accumulator’s statistics from the pooled stats_dict entry (see key_merge).

Parameters:

stats_dict (dict[str, Any])

Return type:

None

acc_to_encoder()

Return type:

PlackettLuceDataEncoder

class PlackettLuceAccumulatorFactory(dim, keys=None)

Bases: StatisticAccumulatorFactory

Factory for PlackettLuceAccumulator.

Parameters:

• dim (int)

• keys (str | None)

make()

Return type:

PlackettLuceAccumulator

class PlackettLuceEstimator(dim, pseudo_count=None, name=None, keys=None)

Bases: ParameterEstimator

Minorization-Maximization estimator for the Plackett-Luce log-worths (item count K fixed).

Parameters:

• dim (int)

• pseudo_count (float | None)

• name (str | None)

• keys (str | None)

accumulator_factory()

Return type:

PlackettLuceAccumulatorFactory

estimate(nobs, suff_stat)

Parameters:

• nobs (float | None)

• suff_stat (tuple[float, ndarray, ndarray])

Return type:

PlackettLuceDistribution

class PlackettLuceDataEncoder(dim=None)

Bases: DataSequenceEncoder

Encode a sequence of orderings (permutations of 0,…,K-1) into an (N, K) integer array.

Parameters:

dim (int | None)

seq_encode(x)

Encode the iid observation sequence x for vectorized evaluation.

Parameters:

x (Sequence[Sequence[int]])

Return type:

ndarray

class PlackettLucePartialDataEncoder(dim)

Bases: DataSequenceEncoder

Encode partial / top-m orderings (variable length) over a fixed item count dim.

Each datum is an ordered list of m <= dim distinct item indices (best first); the remaining items are left unranked. Encoded as a ragged list of 1-D int arrays.

Parameters:

dim (int)

seq_encode(x)

Encode the iid observation sequence x for vectorized evaluation.

Parameters:

x (Sequence[Sequence[int]])

Return type:

list[ndarray]

class PlackettLucePartialAccumulator(dim, keys=None)

Bases: SequenceEncodableStatisticAccumulator

Generalized Hunter (2004) MM statistics for partial / top-m Plackett-Luce rankings.

For each ranking, at every non-forced stage s (at least two items still available) the chosen item accrues a numerator count and all currently-available items (the unranked tail included) accrue weight / sum_{available} w to the denominator, evaluated at the previous estimate’s worths (uniform when none). On full rankings this reduces exactly to the vectorized full-ranking accumulator.

Parameters:

• dim (int)

• keys (str | None)

update(x, weight, estimate)

Parameters:

• x (Sequence[int])

• weight (float)

• estimate (PlackettLuceDistribution | None)

Return type:

None

initialize(x, weight, rng)

Parameters:

• x (Sequence[int])

• weight (float)

• rng (RandomState | None)

Return type:

None

seq_update(x, weights, estimate)

Parameters:

• x (Sequence[ndarray])

• weights (ndarray)

• estimate (PlackettLuceDistribution | None)

Return type:

None

seq_initialize(x, weights, rng)

Parameters:

• x (Sequence[ndarray])

• weights (ndarray)

• rng (RandomState | None)

Return type:

None

combine(suff_stat)

Parameters:

suff_stat (tuple[float, ndarray, ndarray])

Return type:

PlackettLucePartialAccumulator

value()

Return type:

tuple[float, ndarray, ndarray]

from_value(x)

Parameters:

x (tuple[float, ndarray, ndarray])

Return type:

PlackettLucePartialAccumulator

key_merge(stats_dict)

Pool this accumulator’s statistics into stats_dict under its merge key.

The structural default implements the common single-key pattern: store the accumulator under self.keys the first time the key is seen, else combine into the one already there. Accumulators with several named keys (e.g. an HMM’s init/trans/state keys) or a non-accumulator stats payload override this. A keys of None (the default) is a no-op.

Parameters:

stats_dict (dict[str, Any])

Return type:

None

key_replace(stats_dict)

Replace this accumulator’s statistics from the pooled stats_dict entry (see key_merge).

Parameters:

stats_dict (dict[str, Any])

Return type:

None

acc_to_encoder()

Return type:

PlackettLucePartialDataEncoder

class PlackettLucePartialAccumulatorFactory(dim, keys=None)

Bases: StatisticAccumulatorFactory

Factory for PlackettLucePartialAccumulator.

Parameters:

• dim (int)

• keys (str | None)

make()

Return type:

PlackettLucePartialAccumulator

class PlackettLucePartialEstimator(dim, pseudo_count=None, name=None, keys=None)

Bases: ParameterEstimator

MM estimator of Plackett-Luce log-worths from partial / top-m rankings (item count K fixed).

Parameters:

• dim (int)

• pseudo_count (float | None)

• name (str | None)

• keys (str | None)

accumulator_factory()

Return type:

PlackettLucePartialAccumulatorFactory

estimate(nobs, suff_stat)

Parameters:

• nobs (float | None)

• suff_stat (tuple[float, ndarray, ndarray])

Return type:

PlackettLuceDistribution