Parameter Estimation for Probabilistic Finite-State Transducers

Weighted finite-state transducers suffer from the lack of a training algorithm. Training is even harder for transducers that have been assembled via finite-state operations such as composition, minimization, union, concatenation, and closure, as this yields tricky parameter tying. We formulate a "parameterized FST" paradigm and give training algorithms for it, including a general bookkeeping trick ("expectation semirings") that cleanly and efficiently computes expectations and gradients.

• Publication year

  2002

• Venue

  Annual Meeting of the Association for Computational Linguistics

• Publication date

  2002-07-06

• Fields of study

  Computer Science

• Identifiers
  DOI 10.3115/1073083.1073085
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Deterministically annealed design of hidden Markov model speech recognizers

  2001cited by this paper
• Regular Approximation of Context-Free Grammars through Transformation

  2001cited by this paper
• Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data

  2001cited by this paper
• Smoothing a probablistic lexicon via syntactic transformations

  2001cited by this paper
• Maximum Entropy Markov Models for Information Extraction and Segmentation

  2000influential reference
• Áòøøöòòøøóòòð Âóùöòòð Óó Óùòòòøøóò× Óó Óñôùøøö Ë Blockin

  2000cited by this paper
• Transducers from Rewrite Rules with Backreferences

  1999cited by this paper
• Practical Experiments with Regular Approximation of Context-Free Languages

  1999cited by this paper
• An Extendible Regular Expression Compiler for Finite-State Approaches in Natural Language Processing

  1999cited by this paper
• A Gaussian Prior for Smoothing Maximum Entropy Models

  1999cited by this paper
• Hidden Markov models with finite state supervision

  1999cited by this paper
• Translation with finite-state devices

  1998cited by this paper
• A Rational Design for a Weighted Finite-State Transducer Library

  1997cited by this paper
• Probabilistic Constraint Logic Programming

  1997cited by this paper
• Finite-State Language Processing

  1997cited by this paper
• Machine Transliteration

  1997cited by this paper
• Extended finite state models of language

  1997cited by this paper
• Iterative methods for solving linear systems

  1997cited by this paper
• Learning String-Edit Distance

  1996cited by this paper
• Compilation of Weighted Finite-State Transducers from Decision Trees

  1996cited by this paper
• Speech Recognition by Composition of Weighted Finite Automata

  1996cited by this paper
• An Efficient Compiler for Weighted Rewrite Rules

  1996cited by this paper
• Book Reviews: Extended Finite State Models of Language

  1996cited by this paper
• Inducing Features of Random Fields

  1995cited by this paper
• Best-first Model Merging for Hidden Markov Model Induction

  1994cited by this paper
• Rational series and their languages

  1988influential reference
• Robert Endre Tarjan

  1981cited by this paper
• A Unified Approach to Path Problems

  1981cited by this paper
• Fast Algorithms for Solving Path Problems

  1981cited by this paper
• Maximum likelihood from incomplete data via the EM - algorithm plus discussions on the paper

  1977cited by this paper
• Algebraic Structures for Transitive Closure

  1976cited by this paper
• An inequality and associated maximization technique in statistical estimation of probabilistic functions of a Markov process

  1972cited by this paper

• Fast and General Automatic Differentiation for Finite-State Methods

  2026cites this paper
• Scaling Optimization over Uncertainty via Compilation

  2025cites this paper
• Neuro-Symbolic Frameworks: Conceptual Characterization and Empirical Comparative Analysis

  2025cites this paper
• Nature's Insight: A Novel Framework and Comprehensive Analysis of Agentic Reasoning Through the Lens of Neuroscience

  2025cites this paper
• Encoding and Decoding Graph Representations of Natural Language

  2024cites this paper
• ASTRA: Aligning Speech and Text Representations for Asr without Sampling

  2024cites this paper
• aspmc: New frontiers of algebraic answer set counting

  2024cites this paper
• Can Transformers Learn n-gram Language Models?

  2024cites this paper
• Solving Decision Theory Problems with Probabilistic Answer Set Programming

  2024cites this paper
• What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages

  2024cites this paper
• Regular-pattern-sensitive CRFs for Distant Label Interactions

  2024cites this paper
• Generalizing Backpropagation for Gradient-Based Interpretability

  2023cites this paper
• Structure-Aware Path Inference for Neural Finite State Transducers

  2023cites this paper
• Revisiting the Entropy Semiring for Neural Speech Recognition

  2023cites this paper
• Don't Fine-Tune, Decode: Syntax Error-Free Tool Use via Constrained Decoding

  2023cites this paper
• Probabilistic phonology

  2023cites this paper
• SynJax: Structured Probability Distributions for JAX

  2023cites this paper
• A Latent-Variable Model for Intrinsic Probing

  2022cites this paper
• The Algebraic Path Problem for Graph Metrics

  2022cites this paper
• Recent Advances in Neural-symbolic Systems: A Survey

  2022cites this paper
• Comparative Error Analysis in Neural and Finite-state Models for Unsupervised Character-level Transduction

  2021cites this paper
• Treewidth-Aware Cycle Breaking for Algebraic Answer Set Counting

  2021cites this paper
• Linear-Time Calculation of the Expected Sum of Edge Lengths in Random Projective Linearizations of Trees

  2021cites this paper
• Minimal Supervision for Morphological Inflection

  2021cites this paper
• On the Complexity of Sum-of-Products Problems over Semirings

  2021cites this paper
• A Masked Segmental Language Model for Unsupervised Natural Language Segmentation

  2021cites this paper
• A survey on neural-symbolic learning systems

  2021cites this paper
• Handling epistemic and aleatory uncertainties in probabilistic circuits

  2021cites this paper
• Searching for More Efficient Dynamic Programs

  2021cites this paper
• Constraining Linear-chain CRFs to Regular Languages

  2021cites this paper
• Efficient Outside Computation

  2020cites this paper
• A Graph-Based Framework for Structured Prediction Tasks in Sanskrit

  2020cites this paper
• Differentiable Weighted Finite-State Transducers

  2020cites this paper
• Neural Data-to-Text Generation via Jointly Learning the Segmentation and Correspondence

  2020cites this paper
• Tropical time series, iterated-sums signatures and quasisymmetric functions

  2020cites this paper
• Factor Graph Grammars

  2020cites this paper
• Modelling Verbal Morphology in Nen

  2020cites this paper
• Exploring Looping Effects in RNN-based Architectures

  2020cites this paper
• CLUZH at SIGMORPHON 2020 Shared Task on Multilingual Grapheme-to-Phoneme Conversion

  2020cites this paper
• Algebraic Circuits for Decision Theoretic Inference and Learning

  2020cites this paper
• Phonetic and Visual Priors for Decipherment of Informal Romanization

  2020cites this paper
• Tensors over Semirings for Latent-Variable Weighted Logic Programs

  2020influential citation
• Computational Modeling of Phonological Learning

  2019cites this paper
• DeepProbLog: Integrating Logic and Learning through Algebraic Model Counting

  2019cites this paper
• Transforming Probabilistic Programs into Algebraic Circuits for Inference and Learning

  2019cites this paper
• CUNI–Malta system at SIGMORPHON 2019 Shared Task on Morphological Analysis and Lemmatization in context: Operation-based word formation

  2019cites this paper
• Neural probabilistic logic programming in DeepProbLog

  2019cites this paper
• Accidental Gaps and Surface-Based Phonotactic Learning: A Case Study of South Bolivian Quechua

  2018cites this paper
• Neural Transition-based String Transduction for Limited-Resource Setting in Morphology

  2018cites this paper
• Imitation Learning for Neural Morphological String Transduction

  2018cites this paper
• Learning to Discover, Ground and Use Words with Segmental Neural Language Models

  2018cites this paper
• Bridging CNNs, RNNs, and Weighted Finite-State Machines

  2018cites this paper
• Unsupervised Word Discovery with Segmental Neural Language Models

  2018cites this paper
• Rational Recurrences

  2018cites this paper
• DeepProbLog: Neural Probabilistic Logic Programming

  2018cites this paper
• Local String Transduction as Sequence Labeling

  2018cites this paper
• kProbLog: an algebraic Prolog for machine learning

  2017influential citation
• Optimizing Expected Word Error Rate via Sampling for Speech Recognition

  2017cites this paper
• Weighted DAG Automata for Semantic Graphs

  2017cites this paper
• Decoding with Finite-State Transducers on GPUs

  2017cites this paper
• Sequence to Sequence Transduction with Hard Monotonic Attention

  2016cites this paper
• Weighting Finite-State Transductions With Neural Context

  2016influential citation
• Composition of Constraint, Hypothesis and Error Models to improve interaction in Human-Machine Interfaces

  2016cites this paper
• Optimization for Statistical Machine Translation: A Survey

  2016cites this paper
• Inside-Outside and Forward-Backward Algorithms Are Just Backprop (tutorial paper)

  2016cites this paper
• Morphological Inflection Generation with Hard Monotonic Attention

  2016cites this paper
• hyp: A Toolkit for Representing, Manipulating, and Optimizing Hypergraphs

  2015cites this paper
• Penalized Expectation Propagation for Graphical Models over Strings

  2015cites this paper
• Long words in maximum entropy phonotactic grammars*

  2015influential citation
• Sequence Alignment With or Without Parallel Data

  2015cites this paper
• Marginal Consistency: Upper-Bounding Partition Functions over Commutative Semirings

  2015cites this paper
• Toward a generative theory of language transfer: Experiment and modeling of sC prothesis in L2 Spanish

  2015cites this paper
• Model Invertibility Regularization: Sequence Alignment With or Without Parallel Data

  2015cites this paper
• Morphological Inflection Generation Using Character Sequence to Sequence Learning

  2015cites this paper
• A Canonical Semi-Deterministic Transducer

  2014cites this paper
• 2 . 1 Gemination by orthographic influence

  2014cites this paper
• Issues in Analogical Inference Over Sequences of Symbols: A Case Study on Proper Name Transliteration

  2014cites this paper
• What is computational phonology

  2014cites this paper
• Flexible Noisy Text Correction

  2014cites this paper
• Conditional random fields for noisy text normalisation

  2014cites this paper
• Unsupervised spectral learning of FSTs

  2013cites this paper
• Efficient decoding with generative score-spaces using the expectation semiring

  2013cites this paper
• Realization of common statistical methods in computational linguistics with functional automata

  2013cites this paper
• Supervised Learning of Complete Morphological Paradigms

  2013cites this paper
• Spectral learning of transducers over continuous sequences

  2013cites this paper
• Phonemic variability and confusability in pronunciation modeling for automatic speech recognition. (Variabilité et confusabilité phonémique pour les modèles de prononciations au sein d'un système de reconnaissance automatique de la parole)

  2013cites this paper
• Probabilistic tree transducers for grammatical error correction

  2013cites this paper
• Speech Recognition Algorithms Based on Weighted Finite-State Transducers

  2013cites this paper
• Spectral Learning of Sequence Taggers over Continuous Sequences

  2013cites this paper
• Predicting Linguistic Structure with Incomplete and Cross-Lingual Supervision

  2013cites this paper
• Generative Kernels and Score-Spaces for Classi cation of Speech : Progress Report iii

  2012cites this paper
• Probabilistic Finite State Machines for Regression-based MT Evaluation

  2012cites this paper
• Intrasentential Grammatical Correction with Weighted Finite State Transducers

  2012cites this paper
• SPEDE: Probabilistic Edit Distance Metrics for MT Evaluation

  2012cites this paper
• Information theoretic approaches to phonological structure: the case of Finnish vowel harmony

  2012cites this paper
• Transferring Frames: Utilization of Linked Lexical Resources

  2012cites this paper
• Department of Engineering Eecient Decoding with Continuous Rational Kernels Using the Expectation Semiring

  2012cites this paper
• Unsupervised Learning on an Approximate Corpus

  2012influential citation
• Exploiting Partial Annotations with EM Training

  2012cites this paper
• Information theoretic approaches to phonological structure: the case of Finnish vowel harmony

  2012cites this paper