mixle.stats.latent.hmm_determinize module

Weighted determinization of a quantized terminal HMM, and exact n-best-strings over the result.

An ambiguous HMM assigns a sequence’s probability as a sum over its state paths, so naively ranking by best path gives the n-best paths, not the n-best sequences (the same sequence recurs on many paths). The fix is the standard one: determinize first, then rank. Determinization rebuilds the machine over belief states (normalized forward vectors) – new states that factor the duplicated mass out of the originals – so the result is deterministic (one path per sequence) and each edge weight is the exact conditional probability; products of edge weights are the exact marginals. Ranking the deterministic machine then yields duplicate-free, exact n-best sequences.

This is textbook weighted-automata theory, implemented natively so mixle stays self-contained:

• weighted determinization + the twins property characterizing when it terminates – Mohri, “On the Determinization of Weighted Finite Automata”, SIAM J. Comput. 1997;

• removing duplicate hypotheses by determinizing before the n-best step – Mohri & Riley, “An Efficient Algorithm for the n-Best-Strings Problem”, ICSLP 2002.

Termination: the belief orbit is finite iff the automaton satisfies the twins property (always true for acyclic / bounded-length HMMs). When it is not – e.g. an ergodic self-loop chain whose belief drifts through a new point per prefix – the expansion does not terminate; we cap it and raise EnumerationError (the caller then keeps the exact O(index) enumerate-and-bin path on the original HMM).

Exact arithmetic: belief states are compared for equality, so the expansion is done in exact rationals (fractions.Fraction) derived from the quantized HMM’s integer exponents; float beliefs would never compare equal and the expansion would never close.

determinize_quantized_terminal(dist, max_states=1 << 16)

Determinize a terminal-value quantized HMM into a DeterminizedSequenceDistribution.

Raises EnumerationError if the HMM has no terminal_values, or if the belief expansion exceeds max_states (the twins property fails – not finitely determinizable).

Parameters:

max_states (int)

determinize_terminal_hmm(dist, max_states=1 << 16, max_denominator=10**9)

Determinize a GENERAL terminal-value HMM (any transitions/initial, finite-discrete emissions).

Belief equality must be decidable, so the model’s float probabilities are first rationalized (Fraction(p).limit_denominator(max_denominator)) and the determinization is exact on that rationalized model – which equals the original to the rationalization precision. Requires terminal_values and enumerable finite emissions. Raises EnumerationError if not finitely determinizable within max_states or if an emission support is not finite/enumerable.

Parameters:

• max_states (int)

• max_denominator (int)

class DeterminizedSequenceDistribution(trans, accept, name=None)

Bases: SequenceEncodableProbabilityDistribution

A deterministic weighted machine over terminal-ended sequences (one path per sequence).

trans[q][x] = (log_weight, next_state) for a non-terminal symbol; accept[q][x] = log_weight for a terminal symbol that completes the sequence. log_density(x) is the unique path’s summed log-weight (== the original HMM’s exact marginal); enumeration yields exact, duplicate-free n-best-strings.

Parameters:

name (str | None)

density(x)

Return the probability density or mass at a single observation.

Concrete default: exponentiate log_density (the abstract method subclasses must provide). Leaves with a cheaper closed form may override this.

Return type:

float

log_density(x)

Return the log-density or log-mass at a single observation.

Return type:

float

seq_log_density(x)

Return vectorized log-density values for sequence-encoded observations.

Return type:

ndarray

dist_to_encoder()

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

Return type:

DeterminizedDataEncoder

enumerator()

Return a DistributionEnumerator over this distribution’s support.

Distributions with an enumerable (discrete) support override this; the default raises EnumerationError.

Return type:

DeterminizedEnumerator

quantized_count_index(quantizer, max_fine_bucket)

Structural count index over the deterministic machine -> sub-linear exact seek/rank.

The machine is deterministic (one path per sequence), so a forward reach DP over states counts each sequence exactly once at its (floored) cost: reach_by_len[t][q] is the count histogram of length-t non-terminal prefixes reaching state q; an accept edge then completes a length-(t+1) sequence. Unranking walks the reach DP backward through the (precomputed) incoming edges. Exact up to quantization tie granularity; no path over-count (the determinization already removed it).

Parameters:

max_fine_bucket (int)

sampler(seed=None)

Return a sampler for drawing observations from this distribution.

Parameters:

seed (int | None)

Return type:

DeterminizedSampler

estimator(pseudo_count=None)

Return an estimator for fitting this distribution from data.

Parameters:

pseudo_count (float | None)

class DeterminizedSampler(dist, seed=None)

Bases: object

Generative sampler: at each state the accept+transition edge weights are the conditional next-symbol distribution (they sum to 1), so walk it until a terminal (accept) edge is taken.

Parameters:

• dist (DeterminizedSequenceDistribution)

• seed (int | None)

sample(size=None)

Parameters:

size (int | None)

class DeterminizedDataEncoder

Bases: DataSequenceEncoder

seq_encode(x)

Encode the iid observation sequence x for vectorized evaluation.

class DeterminizedEnumerator(dist)

Bases: DistributionEnumerator

Exact descending-probability enumeration of sequences over the deterministic machine (n-best strings). Best-first with an admissible per-state best-completion bound (Viterbi over the machine).

Parameters:

dist (DeterminizedSequenceDistribution)

seek(index)

Sub-linear exact seek over the deterministic machine (no prefix enumeration).

Deepens the structural count index until index is covered or the support is provably exhausted (the count-DP’s reliable truncated flag), then unranks within the located fine bucket. Robust to gaps in the cost spectrum, unlike the shared total-growth deepening heuristic.

Parameters:

index (int)