Stochastic Estimation of Transduced Language Models
Transduced language models (TLMs) compose a pretrained \emph{source} language model with a functional finite-state transducer to induce a language model over \emph{target} strings. Computing the probability of a target prefix under a TLM amounts to summing the source-model probabilities of all source strings that the transducer maps to target strings beginning with that prefix. This set can be exponentially large or infinite. Prior work uses a computational shortcut based on source prefix probabilities, then approximates the resulting sum with threshold-pruned beam summing. This produces a lower bound with unknown error. Instead, we resample source prefixes without replacement and reweight each selected prefix by the inverse of its inclusion probability. We show that applying this correction recursively gives an unbiased estimator of the target prefix probability and lets us estimate the mass lost by threshold pruning. Our beam-summing algorithm extends the retained source prefixes and samples which prefixes to keep, reducing their number as more probability mass is added to the running estimate. This can save computation and guarantees that the run halts with probability one. We evaluate the method on encyclopedic text and DNA against sequential Monte Carlo baselines that resample with replacement. It achieves a better compute--variance tradeoff on text and lower error at the same maximum number of particles on DNA. On a DNA-to-amino-acid transduction, it reduces runtime by several orders of magnitude relative to threshold-pruned beam summing and makes estimating prefix probabilities for long target strings feasible. Replacing threshold pruning with unbiased sampling in a published reading-time analysis substantially lowers the estimated corpus surprisal but leaves the published conclusions unchanged.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Time, control, and the nervous system
Because organisms are able to sense its passage, it is perhaps tempting to treat time as a sensory modality, akin to vision or audition. Indeed, certain features of sensory estimation, such as Weber's law, apply to timin…
Symbolic Autoencoding for Self-Supervised Sequence Learning
Traditional language models, adept at next-token prediction in text sequences, often struggle with transduction tasks between distinct symbolic systems, particularly when parallel data is scarce. Addressing this issue, w…
Weakly-supervised LearningSequence-to-Sequence Learning with Latent Neural Grammars
Sequence-to-sequence learning with neural networks has become the de facto standard for sequence prediction tasks. This approach typically models the local distribution over the next word with a powerful neural network t…
DiagnosticFeature EngineeringMachine TranslationStyle Transfer+1Linear Noise Approximation of Intensity-Driven Signal Transduction Channels
Biochemical signal transduction, a form of molecular communication, can be modeled using graphical Markov channels with input-modulated transition rates. Such channel models are strongly non-Gaussian. In this paper we us…