mixle.stats.rankings.matching module

Create, estimate, sample, and enumerate a weighted bipartite perfect-matching distribution.

Defines the MatchingDistribution, MatchingEnumerator, MatchingSampler, MatchingAccumulatorFactory, MatchingAccumulator, MatchingEstimator, and the MatchingDataEncoder classes for use with mixle.

Data type: a perfect matching of the complete bipartite graph K_{n,n} given as a permutation x of 0,…,n-1, where left node i is matched to right node x[i].

Each left-right edge (i, j) has a positive weight w[i, j]. A matching (permutation) sigma has

p(sigma) = prod_i w[i, sigma(i)] / Z, Z = sum over permutations of prod_i w[i, sigma(i)] = perm(W),

the matrix permanent. Unlike the Plackett-Luce model (a single worth vector over items), this scores a full edge-weight matrix, so it is the natural assignment / matching law. The permanent is computed exactly with Ryser’s formula, which is exponential in n, so the family targets small-to-moderate n (default cap max_nodes = 12). Sampling draws each match in turn from the exact conditional distribution (via permanents of the remaining submatrix); enumeration is lazy and streams matchings in decreasing probability via Murty’s k-best assignment (no n! materialization). Estimation matches the empirical or symmetrically smoothed assignment frequencies to the model edge marginals by projected gradient ascent on the log-weights.

class MatchingDistribution(weights, max_nodes=_DEFAULT_MAX_NODES, name=None, keys=None)[source]

Bases: SequenceEncodableProbabilityDistribution

Weighted bipartite perfect-matching distribution over n left/right nodes (permanent-normalized).

Data type: a permutation x of 0,…,n-1 (left node i matched to right node x[i]).

Parameters:
classmethod compute_capabilities()[source]
density(x)[source]

Return the probability of a matching x (a permutation).

Parameters:

x (Sequence[int])

Return type:

float

log_density(x)[source]

Return the log-probability of a matching x (left i matched to right x[i]).

Parameters:

x (Sequence[int])

Return type:

float

seq_log_density(x)[source]

Return vectorized log-probabilities for an (N, n) array of matchings.

Parameters:

x (ndarray)

Return type:

ndarray

sampler(seed=None)[source]

Return a sampler for drawing matchings from this distribution.

Parameters:

seed (int | None)

Return type:

MatchingSampler

enumerator()[source]

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

Return type:

MatchingEnumerator

estimator(pseudo_count=1.0)[source]

Return an estimator that keeps the node count fixed at this distribution’s n.

Parameters:

pseudo_count (float | None)

Return type:

MatchingEstimator

dist_to_encoder()[source]

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

Return type:

MatchingDataEncoder

class MatchingEnumerator(dist)[source]

Bases: DistributionEnumerator

Enumerate finite-probability perfect matchings in descending probability order.

Lazily, via Murty’s k-best assignment on the edge-cost matrix -log(weights): decreasing probability is increasing assignment cost, and zero-weight edges become +inf costs (forbidden), so only positive-probability matchings are yielded. This streams the top matchings without materializing the n! permutation support.

Parameters:

dist (MatchingDistribution)

class MatchingSampler(dist, seed=None)[source]

Bases: DistributionSampler

Draw iid matchings by sampling each left node’s match from the exact conditional permanent.

Parameters:

  • dist (MatchingDistribution)

  • seed (int | None)

sample(size=None)[source]

Draw matchings (each a permutation); a single matching when size is None.

Parameters:

size (int | None)

Return type:

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

class MatchingAccumulator(dim, keys=None)[source]

Bases: SequenceEncodableStatisticAccumulator

Accumulate the weighted assignment-frequency matrix (the sufficient statistic for the weights).

Parameters:
update(x, weight, estimate)[source]
Parameters:
Return type:

None

initialize(x, weight, rng)[source]
Parameters:
Return type:

None

seq_update(x, weights, estimate)[source]
Parameters:

  • x (ndarray)

  • weights (ndarray)

  • estimate (MatchingDistribution | None)

Return type:

None

seq_initialize(x, weights, rng)[source]
Parameters:
Return type:

None

combine(suff_stat)[source]
Parameters:

suff_stat (tuple[float, ndarray])

Return type:

MatchingAccumulator

value()[source]
Return type:

tuple[float, ndarray]

from_value(x)[source]
Parameters:

x (tuple[float, ndarray])

Return type:

MatchingAccumulator

key_merge(stats_dict)[source]

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)[source]

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()[source]
Return type:

MatchingDataEncoder

class MatchingAccumulatorFactory(dim, keys=None)[source]

Bases: StatisticAccumulatorFactory

Factory for MatchingAccumulator.

Parameters:
make()[source]
Return type:

MatchingAccumulator

class MatchingEstimator(dim, max_nodes=_DEFAULT_MAX_NODES, pseudo_count=1.0, max_steps=500, learning_rate=1.0, tol=1.0e-7, name=None, keys=None)[source]

Bases: ParameterEstimator

Maximum-likelihood estimator for the edge weights (matches empirical and model edge marginals).

Parameters:
accumulator_factory()[source]
Return type:

MatchingAccumulatorFactory

estimate(nobs, suff_stat)[source]
Parameters:
Return type:

MatchingDistribution

class MatchingDataEncoder(dim=None)[source]

Bases: DataSequenceEncoder

Encode a sequence of matchings (permutations) into an (N, n) integer array.

Parameters:

dim (int | None)

seq_encode(x)[source]

Encode the iid observation sequence x for vectorized evaluation.

Parameters:

x (Sequence[Sequence[int]])

Return type:

ndarray