Sampling from Stochastic Finite Automata with Applications to CTC Decoding
Stochastic finite automata arise naturally in many language and speech processing tasks. They include stochastic acceptors, which represent certain probability distributions over random strings. We consider the problem of efficient sampling: drawing random string variates from the probability distribution represented by stochastic automata and transformations of those. We show that path-sampling is effective and can be efficient if the epsilon-graph of a finite automaton is acyclic. We provide an algorithm that ensures this by conflating epsilon-cycles within strongly connected components. Sampling is also effective in the presence of non-injective transformations of strings. We illustrate this in the context of decoding for Connectionist Temporal Classification (CTC), where the predictive probabilities yield auxiliary sequences which are transformed into shorter labeling strings. We can sample efficiently from the transformed labeling distribution and use this in two different strategies for finding the most probable CTC labeling.
Code (2)
Similar Papers 제목 키워드 기반
Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata
Constrained decoding is essential for serving LLMs, ensuring that generated outputs follow specific structures such as JSON schema-formatted function calls. Existing systems are designed for autoregressive models and ass…
Mitigating Bias in Locally Constrained Decoding via Tractable Proposals
Generations from large language models often fail to conform to desired constraints such as JSON schema. Existing locally constrained decoding (LCD) approaches enforce constraints by myopically masking out next tokens, r…
On the Theory of Stochastic Automata
The theory of discrete stochastic systems has been initiated by the work of Shannon and von Neumann. While Shannon has considered memory-less communication channels and their generalization by introducing states, von Neu…
Decoding with Finite-State Transducers on GPUs
Weighted finite automata and transducers (including hidden Markov models and conditional random fields) are widely used in natural language processing (NLP) to perform tasks such as morphological analysis, part-of-speech…
ChunkingGPUMorphological Analysisnamed-entity-recognition+5Spectral Learning from a Single Trajectory under Finite-State Policies
We present spectral methods of moments for learning sequential models from a single trajectory, in stark contrast with the classical literature that assumes the availability of multiple i.i.d. trajectories. Our appr…