Parameter estimation for probabilistic finite-state transducers
Published 1 January 2001Open access
Jason Eisner
Citations167
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A "parameterized FST" paradigm is formulated and training algorithms for it are given, including a general bookkeeping trick ("expectation semirings") that cleanly and efficiently computes expectations and gradients.
Abstract
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.
Keywords
Computer Science
Journal of the Royal Statistical Society Series B (Statistical Methodology)Maximum Likelihood from Incomplete Data Via the <i>EM</i> Algorithm
49,657 Citations1977A. P. Dempster, N. M. Laird +1 more
ScholarlyCommons (University of Pennsylvania)Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
12,978 Citations2001John Lafferty, Andrew McCallum +1 more
This work presents iterative parameter estimation algorithms for conditional random fields and compares the performance of the resulting models to HMMs and MEMMs on synthetic and natural-language data.
Maximum Entropy Markov Models for Information Extraction and Segmentation
1,333 Citations2000Andrew McCallum, Dayne Freitag +1 more
A new Markovian sequence model is presented that allows observations to be represented as arbitrary overlapping features (such as word, capitalization, formatting, part-of-speech), and defines the conditional probability of state sequences given observation sequences.
IEEE Transactions on Pattern Analysis and Machine IntelligenceInducing features of random fields
1,044 Citations1997S. Della Pietra, V. Della Pietra +1 more
The random field models and techniques introduced in this paper differ from those common to much of the computer vision literature in that the underlying random fields are non-Markovian and have a large number of parameters that must be estimated.
Texts in applied mathematicsIterative Methods for Solving Linear Systems
1,038 Citations2006Alfio Quarteroni, Riccardo Sacco +1 more
Language<b>Finite-state language processing.</b> Ed. by Emmanuel Roche and Yves Schabes. Cambridge, MA: MIT Press, 1997. Pp. xvii, 464.
355 Citations1999Michael A. Covington
Topics include finite-state morphology, approximation of phrase-structure grammars, deterministic part-of-speech tagging, application of a finite- state intersection grammar, a infinite-state transducer for extracting information from text, and speech recognition using weighted finite automata.
A Gaussian Prior for Smoothing Maximum Entropy Models
347 Citations1999Stanley F. Chen, Ronald Rosenfeld
Over a large number of data sets, it is found that an ME smoothing method proposed to us by Lafferty performs as well as or better than all other algorithms under consideration.
Journal of the ACMFast Algorithms for Solving Path Problems
282 Citations1981Robert E. Tarjan
A method to compute path expressions by dividing G into components, computing path expressions on the components by Gaussian elimination, and combining the solutions is described, which requires O(m $\alpha$(m,n) time on a reducible flow graph.
Journal of the ACMA Unified Approach to Path Problems
249 Citations1981Robert E. Tarjan
The results provide a general-purpose algorithm for solving any path problem, and show that the problem of constructing path expressions is in some sense the most general path problem.
An efficient compiler for weighted rewrite rules
162 Citations1996Mehryar Mohri, Richard Sproat
This work describes a new algorithm for compiling rewrite rules into finite-state transducers, and shows it to be simpler and more efficient than existing algorithms.
The MIT Press eBooksSpeech Recognition by Composition of Weighted Finite Automata
152 Citations1997Fernando C. N. Pereira, Michael Riley
ComputingA systolic array algorithm for the algebraic path problem (shortest paths; Matrix inversion)
122 Citations1985Giinter Rote
It is shown how the Gauß-Jordan Elimination algorithm for the Algebraic Path Problem can be implemented on a hexagonal systolic array of a quadratic number of simple processors in linear time.
Theoretical Computer ScienceAlgebraic structures for transitive closure
120 Citations1977Daniel Lehmann
Two algorithms are proved to compute the closure of a matrix oven any closed semiring using a generalization of algorithms by Warshall, Floyd and Kleene and a generalized version of Dijkstra algorithm.
ArXiv.orgBest-first Model Merging for Hidden Markov Model Induction
115 Citations1994Andreas Stolcke, Stephen M. Omohundro
A new technique for inducing the structure of Hidden Markov Models from data which is based on the general `model merging' strategy, and how the algorithm was incorporated in an operational speech understanding system, where it was combined with neural network acoustic likelihood estimators to improve performance over single-pronunciation word models.
Lecture notes in computer scienceTranslation with Finite-State Devices
113 Citations1998Kevin Knight, Yaser Al-Onaizan
The authors' is the first translation algorithm for “fertility/permutation” statistical models to be described in replicable detail and demonstrates the use of standard tools to compute statistically likely translations.
Text, speech and language technologyRegular Approximation of Context-Free Grammars through Transformation
109 Citations2001Mehryar Mohri, Mark-Jan Nederhof
The approximation algorithm is extended to the case of weighted context-free grammars and shows that the size of the minimal deterministic automata accepting the resulting approximations is of practical use for applications such as speech recognition.
Computational LinguisticsPractical Experiments with Regular Approximation of Context-Free Languages
106 Citations2000Mark-Jan Nederhof
Practical experiments with the different methods of regular approximation are performed for spoken-language input: hypotheses from a speech recognizer are filtered through a finite automaton.
arXiv (Cornell University)Probabilistic Constraint Logic Programming
61 Citations1997Stefan Riezler
An algorithm to estimate the parameters and to select the properties of log-linear models from incomplete data and an approach for searching for most probable analyses of the probabilistic constraint logic programming model are presented.
Extended finite state models of language
53 Citations1999András Kornai
Transducers from rewrite rules with backreferences
35 Citations1999Dale Gerdemann, Gertjan van Noord
Context sensitive rewrite rules have been widely used in several areas of natural language processing, including syntax, morphology, phonology and speech processing, by allowing a limited form of backreferencing in such rules.
Lecture notes in computer scienceAn Extendible Regular Expression Compiler for Finite-State Approaches in Natural Language Processing
31 Citations2001Gertjan van Noord, Dale Gerdemann
The paper discusses the regular expression operations provided by the compiler, and the possibilities to create new regular expression operators, and a number of examples taken from recent publications in the area of finite-state approaches to NLP.
Compilation of weighted finite-state transducers from decision trees
31 Citations1996Richard Sproat, Michael Riley
A method for compiling decision trees into weighted finite-state transducers using the weighted rewite-rule rule-compilation algorithm described in (Mohri and Sproat, 1996).
IEEE Transactions on Speech and Audio ProcessingDeterministically annealed design of hidden Markov model speech recognizers
31 Citations2001A.V. Rao, Kenneth Rose
Experiments on synthetic data and on a simplified recognizer for isolated English letters demonstrate that the DA design method can improve recognition error rates over both ML and GPD methods.
arXiv (Cornell University)Learning string edit distance
27 Citations1996Eric Sven Ristad, P.N. Yianilos
An Extendible Regular Expression Compiler for Finite-State Approaches in Natural Language Processing
27 Citations2001Gertjan van Noord, Dale Gerdemann
ScholarlyCommons (University of Pennsylvania)Smoothing a probablistic lexicon via syntactic transformations
17 Citations2001Jason Eisner, Mitchell P. Marcus
The proposed “transformation models” are probability distributions that arise from graph random walks with a log-linear parameterization that are suited to any domain where “related” events may have positively covarying probabilities.
Hidden Markov models with finite state supervision
3 Citations1999Eric Sven Ristad
This chapter provides a supervised training paradigm for hidden Markov models (HMMs) that is completely general, need not make any simplifying assumptions about independence, and can take better advantage of the information contained in the training corpus.