mixle.enumeration.quantization.semiring module

The two enumeration primitives and the bridges between them (step-1 contract).

The enumeration system has two orthogonal computational modes:

Axis A – aggregate computation: fold a distribution’s complete-probability reduction into a

summary. Density, structural counts, and bounds all live here. This is captured by DecomposableSemiring: a family expresses its reduction with leaf/plus/times and the carrier decides what is computed. The carrier must be witness-retaining – its elements keep enough structure to invert a rank back to a value (unranking) – which a plain scalar semiring cannot do. CountSemiring is the witness-retaining carrier over mixle.enumeration.quantization.CountIndex that yields the count-budget seek index.

Axis B – ordered access: produce values in strict descending probability order, lazily. This is

a best-first search, not a fold, and a semiring cannot generate it; it is the existing enumerator() machinery (mixle.stats.compute.pdist.DistributionEnumerator), aliased here as OrderedStream for symmetry.

The two axes trade in one currency – (value, log_prob) pairs under a shared mixle.enumeration.quantization.Quantizer – connected by two coercion bridges:

• enumerate_and_bin() (Axis B -> Axis A): the universal fallback. Any OrderedStream can be tabulated into a bounded count index; O(count), so only viable for small budgets.

• ordered_stream_from_count_index() (Axis A -> Axis B): unrank in bin order to get an approximately-ordered stream when exact best-first is too expensive.

So a family implements whichever axis is natural and the bridges synthesize the other (lossily). This module is the contract; CountSemiring is the witness-retaining carrier for everything count-shaped, and TropicalSemiring is the (max, +) carrier that computes the Viterbi configuration and its log-prob – an exact bound that factors through the non-decomposable families (HMM/Mixture) by swapping only the carrier.

For those non-decomposable families the state-augmented count DP IS implemented – as a conservative upper bound – by HiddenMarkovModelDistribution.quantized_count_index (a forward count DP over the (state-path, observation) trellis) and MixtureDistribution.quantized_count_index (a plus-fold of weight-scaled component indices). What is not available is the EXACT MARGINAL count/rank, which sums over the latent and is provably hard (mixture/HMM marginal rank is k-SUM- / W[1]-hard); the exact head plus a certified unbiased Monte-Carlo estimator for the tail lives in mixle.enumeration.density_rank (density_rank), and exact HMM path enumeration in mixle.enumeration.hmm_paths.

class DecomposableSemiring

Bases: ABC

A witness-retaining semiring over which a likelihood reduction is evaluated.

zero/one are the additive/multiplicative identities; plus pools mutually exclusive alternatives (e.g. different sequence lengths or Markov end-states); times composes independent factors (whose log-probabilities add); product is n-ary times. leaf lifts a single scored atom into the carrier. Implementations choose the carrier E; for counting it is CountIndex, whose per-bucket structure is the witness needed to unrank.

abstractmethod zero()

Return type:

E

abstractmethod one()

Return type:

E

abstractmethod leaf(value, log_prob, quantizer)

Parameters:

• value (Any)

• log_prob (float)

• quantizer (Quantizer)

Return type:

E

abstractmethod plus(a, b)

Parameters:

• a (E)

• b (E)

Return type:

E

abstractmethod times(a, b, quantizer, max_fine_bucket)

Parameters:

• a (E)

• b (E)

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

E

product(elements, quantizer, max_fine_bucket)

n-ary times. Default folds times; carriers may override for efficiency/order.

Parameters:

• elements (Sequence[E])

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

E

class CountSemiring

Bases: DecomposableSemiring

Witness-retaining carrier over reified nodes / CountIndex: structural counting + unranking.

leaf/plus/scale/map_values build _CNode trees unranked by the iterative _unrank() (bounded call-stack regardless of chain depth); times/product convolve via mixle.enumeration.quantization.convolve_indices() (flat unranker – identical bin counts and within-bucket order to the previous path). Both element kinds expose .hist and .get_in_bucket, so they interoperate freely.

zero()

Return type:

_CNode

one()

Return type:

_CNode

leaf(value, log_prob, quantizer)

Parameters:

• value (Any)

• log_prob (float)

• quantizer (Quantizer)

Return type:

_CNode

from_enumerator(enum, quantizer, max_fine_bucket)

Lift an atomic distribution’s exact enumerator into a carrier element (depth-bounded).

Parameters:

• enum (Iterator[tuple[Any, float]])

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

tuple[CountIndex, bool]

plus(a, b)

Return type:

_CNode

times(a, b, quantizer, max_fine_bucket)

Parameters:

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

CountIndex

product(elements, quantizer, max_fine_bucket)

n-ary times. Default folds times; carriers may override for efficiency/order.

Parameters:

• elements (Sequence[Any])

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

CountIndex

scale(a, log_prob, quantizer, max_fine_bucket=None)

Multiply by a constant probability factor: shift buckets by the factor, value unchanged.

This is the action of the base log-prob monoid on the carrier (e.g. a sequence length term, a Markov transition/initial term). Optionally truncate the shifted histogram to a depth bound.

Parameters:

• log_prob (float)

• quantizer (Quantizer)

• max_fine_bucket (int | None)

Return type:

_CNode

map_values(a, fn)

Relabel values (pushforward) without touching counts or buckets – e.g. tuple -> list.

Parameters:

fn (Callable[[Any], Any])

Return type:

_CNode

power_prefix(a, max_k, quantizer, max_fine_bucket)

Return [a^(times 0), …, a^(times K)] (K <= max_k), the k-fold self-products.

The histograms are built incrementally (O(max_k) convolutions, shared), so this is the count side of an iid sequence. Each element’s unranker is the flat product of k copies, built lazily and cached – identical bin counts and within-bucket order to calling product([a]*k) directly, but without the O(k^2) eager cost. Stops early if the element mass is exhausted within the depth bound.

Parameters:

• a (CountIndex)

• max_k (int)

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

Sequence[CountIndex]

class TropicalSemiring

Bases: DecomposableSemiring

Max-plus (Viterbi) carrier: the single best configuration and its log-probability.

The second realization of DecomposableSemiring – it swaps only the carrier (the contract this module was built around). Where CountSemiring counts the support in each quantized bin, the tropical carrier folds the same leaf/plus/times reduction over the (max, +) semiring: plus keeps the higher-probability alternative, times/product add log-probabilities and concatenate witnesses. The result is the Viterbi (most-probable) configuration and its exact log-probability – the top of the descending-probability order, and hence an exact bound usable by any family expressible in leaf/plus/times.

Crucially this includes the non-decomposable families (HMM / Mixture): exact counting couples across structure (which is why the count index does not serve them), but the Viterbi bound factors cleanly through the tropical fold. (Exact bounded counting for those families is the state-augmented count DP – a further step; for HMM the exact descending enumeration is already available via mixle.enumeration.hmm_paths.hmm_best_paths().)

The witness is the flat tuple of leaf atoms along the best configuration (the tropical carrier keeps a single witness, not the per-child structured value the count carrier reconstructs on unrank), which is exactly what a Viterbi decode wants. quantizer / max_fine_bucket are accepted for interface symmetry but unused – the tropical fold needs no quantization.

zero()

Return type:

_Trop

one()

Return type:

_Trop

leaf(value, log_prob, quantizer=None)

Parameters:

• value (Any)

• log_prob (float)

• quantizer (Quantizer | None)

Return type:

_Trop

plus(a, b)

Parameters:

• a (_Trop)

• b (_Trop)

Return type:

_Trop

times(a, b, quantizer=None, max_fine_bucket=None)

Parameters:

• a (_Trop)

• b (_Trop)

• quantizer (Quantizer | None)

• max_fine_bucket (int | None)

Return type:

_Trop

product(elements, quantizer=None, max_fine_bucket=None)

n-ary times. Default folds times; carriers may override for efficiency/order.

Parameters:

• elements (Sequence[_Trop])

• quantizer (Quantizer | None)

• max_fine_bucket (int | None)

Return type:

_Trop

OrderedStream

Exact strict-descending lazy stream of (value, log_prob) – produced by enumerator().

alias of Iterator[tuple[Any, float]]

enumerate_and_bin(stream, quantizer, max_fine_bucket)

Axis B -> Axis A: tabulate an ordered stream into a bounded count index.

The universal fallback for distributions that can only enumerate. O(number of in-bound values), so feasible only for small budgets. Returns (CountIndex, truncated).

Parameters:

• stream (Iterator[tuple[Any, float]])

• quantizer (Quantizer)

• max_fine_bucket (int)

Return type:

tuple[CountIndex, bool]

bounded_dedup_stream(stream, max_entries=1 << 16, key=None)

Deduplicate an (approximately) descending (value, log_prob) stream in O(max_entries) memory.

The structural BoundedCount index for a MARGINAL family (Mixture / HMM) emits a value once per contributing component / state-path; every copy reports the same exact log_density (it is path/component-independent), so the duplicates are exact repeats of the value. This wrapper keeps a least-recently-seen window of at most max_entries keys and suppresses repeats within it.

Memory is hard-capped at max_entries – never the full (up to 2**M) support. The trade: a duplicate whose two occurrences are more than max_entries distinct values apart in the stream (i.e. its second copy is far deeper / effectively outside the bound of interest) may survive. Set max_entries to bound how far apart duplicates can be and still be removed.

Parameters:

• stream (Iterator[tuple[Any, float]])

• max_entries (int)

• key (Callable[[Any], Any] | None)

Return type:

Iterator[tuple[Any, float]]

ordered_stream_from_count_index(index, max_items=None)

Axis A -> Axis B: unrank a built count index in coarse-bin order (approximately descending).

index is a built LazyQuantizedEnumerationIndex (from count_budget_index). The order is exact across coarse bins but unspecified within a bin – a good-enough stream when exact best-first enumeration is too expensive.

Parameters:

max_items (int | None)

Return type:

Iterator[tuple[Any, float]]