mixle.enumeration.hmm_paths module

Descending-probability enumeration AND unranking of HMM state paths (list-Viterbi / A* + count-DP).

The count-budget index handles the decomposable families (Sequence / Composite / MarkovChain). An HMM is non-decomposable – the latent state couples emissions across time – so it is not served by the count semiring. Two complementary tools live here:

  • hmm_best_paths() – exact, lazy enumeration in nonincreasing joint log-probability by A* search with the backward Viterbi value as an admissible (in fact tight) heuristic. The right tool for the head, but rank k costs O(k) expansions: there is no random access.

  • HMMPathIndex – the quantized precomputation structure: a forward count DP over integer score buckets (one O(T * K^2 * W) build, W = bit budget in fine buckets) that then answers count / unrank / threshold / mass_above in O(T * K) per query – random access into the ranked path list at any depth, which A* structurally cannot do. Ordering is exact up to the fine bucket width (bin_width_bits / oversample bits; raise oversample to sharpen); every returned path carries its exact joint log-probability.

For a path z_{1..T} the joint log-probability of the latent path with the observed emissions is log_pi[z_1] + log_b[0, z_1] + sum_{t>1} (log_A[z_{t-1}, z_t] + log_b[t, z_t]) where log_b[t, k] is the emission log-likelihood log p(x_t | z_t = k). The completion heuristic h[t, s] = max over z_{t+1..T} of the remaining transition+emission score is computed once by a backward max-product pass, so g + h is the exact score of the best path through (t, s) – an admissible bound that makes best-first emit paths in exactly nonincreasing joint log-probability.

hmm_best_paths(log_pi, log_A, log_b, k=None)[source]

Enumerate HMM state paths in nonincreasing joint log-probability.

Parameters:

  • log_pi (ndarray) – (K,) log initial-state distribution.

  • log_A (ndarray) – (K, K) log transition matrix (row j -> column k is log p(z_t=k | z_{t-1}=j)).

  • log_b (ndarray) – (T, K) per-position emission log-likelihoods log p(x_t | z_t=k).

  • k (int | None) – stop after the k best paths; None enumerates all K**T lazily.

Yields:

(path, joint_log_prob) with path a length-T tuple of state indices, highest first. The first yield is the Viterbi (MAP) path.

Return type:

Iterator[tuple[tuple[int, …], float]]

class CertifiedCount(value, certified)[source]

Bases: object

A path count from HMMPathIndex, honest about whether it is the complete answer.

HMMPathIndex is built to a finite quantized-bucket budget; when a query needs to look beyond that budget on a genuinely truncated index, the stored tables cannot answer it exactly – paths beyond the budget were never counted. Returning the in-budget count as a bare number would look identical to a complete answer with no way to tell the two apart (MXR-080-0230); this return type makes the distinction explicit instead.

Parameters:
value

the count of indexed (in-budget) paths satisfying the query. Always a sound LOWER bound on the true count – every path counted here genuinely qualifies, so this can only under-, never over-, state the truth. Exact (up to the ordinary quantization smear documented on HMMPathIndex.count(), unrelated to truncation) when certified.

Type:

int

certified

True when value is provably the complete answer – no path beyond the built budget could also qualify. False when the query reaches beyond the built budget on a truncated index, so additional qualifying paths may exist beyond value.

Type:

bool

class CertifiedMassBound(lower, upper, certified)[source]

Bases: object

A joint probability/density mass bracket from HMMPathIndex.mass_above().

Parameters:
lower

sound lower bound on the true mass above the threshold. Valid regardless of certified – paths beyond a truncated budget can only ADD mass, never invalidate a lower bound derived purely from the paths this index actually has.

Type:

float

upper

sound upper bound when certified; math.inf when not. A truncated index’s stored histogram cannot certify any FINITE upper bound on mass that might live beyond the built budget without deepening it – reporting the in-budget figure anyway would be an unsound bound wearing a sound bound’s shape (MXR-080-0230).

Type:

float

certified

True when both bounds are provably sound answers to the exact query; False when the threshold reaches beyond the built budget on a truncated index.

Type:

bool

class HMMPathIndex(log_pi, log_A, log_b, *, bin_width_bits=1.0, oversample=8, budget_bits=None)[source]

Bases: object

Quantized random-access index over an HMM’s state paths for one observation sequence.

log_pi/log_A/log_b are validated at construction (MXR-080-0228): shapes must be (K,)/(K, K)/(T, K) with a consistent K, every score must be finite-or-impossible (-inf, never NaN or +inf), and log_pi/log_A must describe at most one unit of total probability each (sub-stochastic rows – e.g. from forbidding individual transitions without renormalizing – are allowed; log_b is an emission LOG-LIKELIHOOD and may be positive/unnormalized – see hmm_best_paths()). An all-impossible initial vector or a position with no finite score at all is not an error: it is represented explicitly via empty_support (and total() reporting a certified zero), rather than crashing.

Precompute (once, O(T * K^2 * W)): quantize every step score – log_pi[s] + log_b[0, s] and log_A[s, s'] + log_b[t, s'], one floor per step so the accumulated smear is at most T fine buckets – and run a forward count DP: C_t[s'] is the histogram, over integer total-score buckets, of the number of length-t+1 prefixes ending in state s'. Counts are EXACT Python arbitrary-precision integers, never float64 (MXR-080-0229): the number of paths is K**T, which exceeds float64’s 2**53 exact-integer range for even modest T, and every operation this DP performs on a count is addition – no rounding is ever actually needed here.

Query (each O(T * K)): unrank(i) walks the stored tables backward – pick the final state whose bucket count covers the offset, then repeatedly the predecessor whose shifted prefix bucket does – returning the i-th best path by quantized score and its exact joint log-probability, exactly for any i within the built support. total / count / mass_above read the pooled final histogram and report a CertifiedCount / CertifiedMassBound: a query that reaches beyond a truncated index’s built budget gets a sound bound with certified=False rather than a bare number indistinguishable from a complete answer (MXR-080-0230).

Ordering contract: paths are ordered by their quantized bucket (width bin_width_bits/oversample bits); within a bucket the order is deterministic but unspecified – exactly the count-index semantics elsewhere in mixle.enumeration. hmm_best_paths() remains the exact-order tool for the head; this index is the random-access tool for depth (rank 1e6 costs one table walk, not 1e6 A* expansions).

Parameters:

  • log_pi (np.ndarray)

  • log_A (np.ndarray)

  • log_b (np.ndarray)

  • bin_width_bits (float)

  • oversample (int)

  • budget_bits (float | None)

bucket_of(log_joint)[source]

The index’s bucket frame for a true joint score (bits behind the per-position optimum).

Parameters:

log_joint (float)

Return type:

int

total()[source]

Number of state paths within the budget (== K**T when nothing truncated; exact integer count).

certified is False when the index is truncated: value is then only a sound LOWER bound on the true number of paths – some paths exceed the built budget and were never counted (MXR-080-0230). Deepen budget_bits (or omit it for the default, which is sized to cover every finite-score path) to certify a larger/complete total.

Return type:

CertifiedCount

count(min_log_joint)[source]

How many paths have quantized joint log-probability at least min_log_joint.

Counts every true qualifier (the structural bucket never over-states a path’s bits) plus at most the paths within the T-floor smear band below the threshold – this ordinary quantization smear applies regardless of certified.

certified is True whenever this query’s own bucket stays within the built budget: bucket costs only accumulate along a path (never decrease), so every bucket the index does hold is a complete, exact count regardless of the index’s global truncated flag. It is False only when the query needs to look beyond the built budget on a genuinely truncated index (MXR-080-0230): value is then a sound LOWER bound (every indexed path is a real qualifier), not the complete answer – more qualifying paths may live beyond the budget.

Parameters:

min_log_joint (float)

Return type:

CertifiedCount

mass_above(min_log_joint)[source]

A bracket on the total joint probability/density of paths above the threshold.

Bucket arithmetic with the T-floor smear: a path in bucket b carries between exp(total_offset) * 2**-((b + T) / fpb) and exp(total_offset) * 2**-(b / fpb) of joint mass (the offset restores the per-position shift, so unnormalized emission likelihoods work).

certified follows the same rule as count(): True unless this query reaches beyond the built budget on a truncated index. When not certified, lower remains a sound bound (unindexed paths can only add mass) but upper is replaced with math.inf – the in-budget figure is not a valid upper bound once qualifying mass may exist beyond the budget, so reporting it as one would be unsound, not just imprecise (MXR-080-0230).

Parameters:

min_log_joint (float)

Return type:

CertifiedMassBound

unrank(i)[source]

The i-th best state path by quantized score (0-based) and its exact joint log-probability.

One backward table walk – O(T * K) – regardless of how deep i is. Every table read along the walk is an exact Python int (MXR-080-0229), so i resolves exactly for supports far beyond float64’s 2**53 exact-integer range – adjacent ranks never alias to the same stored offset the way they would under float64 accumulation.

Parameters:

i (int)

Return type:

tuple[tuple[int, …], float]

threshold(rank)[source]

Exact joint log-probability of the rank-th best (quantized-order) path.

Parameters:

rank (int)

Return type:

float

iter_paths(start=0)[source]

Iterate paths from quantized rank start (sequential unranks over the stored tables).

Parameters:

start (int)

Return type:

Iterator[tuple[tuple[int, …], float]]