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 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.

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 float64 (exact below 2**53; the number of paths is K**T, so deep problems carry the documented ~1e-16/op relative error instead of overflowing).

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. count / threshold / mass_above read the pooled final histogram.

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; float64 counts).

Return type:: float

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.

Parameters:: min_log_joint (float)
Return type:: float

mass_above(min_log_joint)[source]

A (lower, upper) 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).

Parameters:: min_log_joint (float)
Return type:: tuple[float, float]

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.

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]]