mixle.enumeration.best_first module

Best-first / A*-style search over sorted enumeration streams.

The k-best engines used by the combinator distributions: ProductEnumerator (best-first over a Cartesian product of child streams), LengthFrontierMerge / frontier_merge (length-indexed frontier merge), and the best_first_union family (union of overlapping-support streams, re-scored exactly and emitted in provably correct descending-probability order). See mixle.stats.compute.pdist.DistributionEnumerator for the enumeration contract.

class ProductEnumerator(streams, combine=tuple, offset=0.0)[source]

Bases: object

Best-first enumeration of the Cartesian product of sorted child streams.

Yields (combine(values), log_prob) with log_prob = offset + sum of child log probs, in non-increasing order. Standard k-best lattice search: a max-heap over index tuples, with successors advancing one coordinate; correctness follows from each child stream being sorted (coordinate-wise monotonicity).

Duplicate-free successor rule: each heap entry carries the lowest coordinate it is allowed to advance, and a node only spawns successors for coordinates at or above that index. Every tuple is then reached by exactly one path – the one that increments coordinates in non-decreasing index order – so no visited set (and no O(n) per-successor tuple hashing) is needed. Best-first order is preserved because each successor’s score is <= its generating node’s (a sorted coordinate only decreases when advanced), so canonical edges are score-monotone.

Parameters:
class LengthFrontierMerge(len_stream, make_stream)[source]

Bases: object

Merge per-length sorted streams, instantiating lengths lazily from a sorted length stream.

len_stream yields (length, log_prob_of_length) in descending order. make_stream(length, lp_len) returns a sorted iterator of (value, log_prob) whose log probs already include lp_len and never exceed it (true whenever per-element contributions are log probs <= 0). The next un-instantiated length’s lp_len is then a valid upper bound on anything its stream could produce, so lengths are instantiated only when they can beat the best instantiated head. Supports of distinct lengths must be disjoint (no de-duplication).

Parameters:
frontier_merge(outer_stream, make_stream)[source]

Merge per-outer-key inner streams, instantiating outer keys lazily from a sorted outer stream.

The general form of LengthFrontierMerge for arbitrary (not necessarily integer) outer keys: outer_stream yields (key, lp_key) in descending lp_key order, and make_stream(key, lp_key) returns a sorted (value, log_prob) iterator whose log-probs are <= lp_key (true whenever the inner contribution is <= 0 and lp_key is folded in as an offset). The next un-instantiated key’s lp_key is then an upper bound on anything its stream could produce, so keys are instantiated only when they can beat the best instantiated head. Supports of distinct keys must be disjoint (no de-duplication). Used for conditional products where the inner distribution depends on the outer value (e.g. hidden-association S2 given S1).

Parameters:
Return type:

Iterator[tuple[Any, float]]

best_first_union(streams, log_offsets, exact_log_density, tol=1.0e-10)[source]

Enumerate the union of sorted streams with overlapping supports.

Candidate values are pulled from the streams (stream k shifted by log_offsets[k]), de-duplicated via freeze, re-scored exactly with exact_log_density, and buffered until their exact score is at least the upper bound on any not-yet-seen value: logsumexp_k(log_offsets[k] + head_lp_k). This is the mixture algorithm: any unseen x satisfies p_k(x) <= head_k for every k, hence sum_k w_k p_k(x) <= exp(bound).

Parameters:
Return type:

Iterator[tuple[Any, float]]

bounded_best_first_union_index(streams, log_offsets, exact_log_density, max_bits, bin_width_bits=1.0, tol=1.0e-10, component_log_density=None)[source]

Build a quantized index from a globally bounded best-first union.

This is the index-building counterpart of best_first_union. It is useful for mixtures: if each stream head bounds one component contribution, then the log-sum of live heads bounds every unseen value. Once that global frontier is below the requested probability threshold, all remaining qualifying values must already be in the exact-score buffer, so the index can stop without enumerating a looser per-component candidate prefix.

Parameters:
Return type:

QuantizedEnumerationIndex

best_first_union_max(streams, log_offsets, exact_log_density, tol=1.0e-10)[source]

Like best_first_union, but for a max-scored union (bound = max over heads).

Used to enumerate a deduped symbol pool ordered by max-over-states emission probability for markov/HMM enumerators.

Parameters:
Return type:

Iterator[tuple[Any, float]]

class SoundTopKResult(items, status, budget_bits, remaining_mass_bound)[source]

Bases: object

Outcome of sound_top_k(): the found items plus an explicit soundness certificate.

sound_top_k is named and documented as SOUND, so callers must be able to tell a mathematically-certified top-k apart from a best-effort guess it gave up on – unlike a plain list, this always carries the status that earned items.

Parameters:
items

the (value, log_prob) pairs ranked [start, start+k), in descending log_prob order. Fewer than k items only when status == "exhausted" and the distribution’s true support genuinely has fewer than start + k distinct values.

Type:

list[tuple[Any, float]]

status

how items was established.

  • "certified" – the mass certificate proved no unseen value can outrank the worst kept item: the accumulated seen mass leaves less than the worst kept item’s own probability unaccounted for. Sound regardless of the count-budget index’s internal seek order (deep/nested mixtures and HMMs included).

  • "exhausted" – the count-budget index was NOT truncated, i.e. it covers the distribution’s entire true support, so items is exact by construction: nothing was left unseen for the certificate to reason about.

  • "incomplete" – max_budget_bits was reached before either certificate above could be established. items is a best-effort prefix of whatever the search had found – NOT proven to be the true top-k. Callers that require soundness must treat this as a failure (retry with a larger max_budget_bits, or fall back to exact enumeration) rather than silently trusting items.

Type:

Literal[‘certified’, ‘exhausted’, ‘incomplete’]

budget_bits

the final (possibly doubled) count-budget-index budget used to produce items.

Type:

float

remaining_mass_bound

a conservative upper bound on the probability mass of every value not in items – never smaller than the truth, even accounting for floating-point rounding (see _fold_mass_lower_bound()). Certifies "certified" results (strictly less than the worst kept item’s probability); left at total_mass (a trivial but valid bound) when the heap never reached start + k items.

Type:

float

property sound: bool

True when items is a proven-correct top-k (status is not "incomplete").

sound_top_k(dist, k, start=0, budget_bits=40.0, oversample=8, bin_width_bits=1.0, max_budget_bits=512.0, total_mass=1.0, tol=1.0e-12)[source]

Exact true-descending observations ranked [start, start+k) for ANY normalized model.

Mass-threshold certificate, correct regardless of the seek stream’s ordering (so it holds for deep/nested mixtures and HMMs where the tropical order is badly displaced): pull distinct (value, log_prob) from the count-budget index, accumulate probability mass with a provable (never-overstated) lower bound, and keep the best start+k by probability. Since every unpulled item’s probability is at most the remaining mass total_mass - accumulated, once a sound upper bound on remaining drops below the (start+k)-th best probability the heap is exactly the true top start+k; return sorted_desc[start:start+k].

Running out of the in-budget stream is NOT by itself proof the support is exhausted: only a non-truncated index has genuinely covered the entire support, so seeing fewer than start + k distinct values THERE means that many is honestly all there is. A TRUNCATED index only proves “nothing more is visible to this bounded build” – running out of one deepens the budget (doubling up to max_budget_bits) instead of returning the partial prefix as the answer. If even max_budget_bits cannot certify or exhaust, the call fails closed: the returned status is "incomplete" and marked as such rather than silently shaped like a proof (see SoundTopKResult – this is why the return type is a structured result, not a plain list).

total_mass (default 1.0) may be a known upper bound for sub-normalized models; it is trusted as a valid bound on the model’s TRUE total probability mass (this function cannot re-derive a model’s own normalization) but is validated for basic sanity – finite and positive – before use, so a NaN/inf/non-positive caller bug cannot silently corrupt the certificate.

Cost is O(number pulled) – small for peaked distributions, large for flat ones, so for top-k from rank 0 dist.enumerator() is usually leaner; this adds the soundness certificate and the arbitrary start offset the sequential enumerator lacks.

Parameters:
Return type:

SoundTopKResult