---
title: "Parameter Estimation for Probabilistic Finite-State Transducers"
description: "Eisner proposes \"parameterized finite-state machines,\" in which arc weights are functions of a small… 31 references, cited by 63 papers here."
authors: ["Jason Eisner"]
year: 2002
venue: "Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics"
source: "https://aclanthology.org/P02-1001/"
doi: "10.3115/1073083.1073085"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/eisner-2002-parameter-estimation-probabilistic-finite-state/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/eisner-2002-parameter-estimation-probabilistic-finite-state/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2002](https://md.research.elamur.ai/free/en/papers/2002/) / Parameter Estimation for Probabilistic Finite-State Transducers

# Parameter Estimation for Probabilistic Finite-State Transducers

**Authors:** [Jason Eisner](https://md.research.elamur.ai/free/en/authors/jason-eisner/) · **Year:** 2002 · **Venue:** [Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics](https://md.research.elamur.ai/free/en/venues/acl/) ([ACL 2002](https://md.research.elamur.ai/free/en/venues/acl/2002/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/P02-1001/) · [PDF](https://aclanthology.org/P02-1001.pdf) · [DOI 10.3115/1073083.1073085](https://doi.org/10.3115/1073083.1073085) · [OpenAlex](https://openalex.org/W2105738468)

**Citations:** 161 citations (OpenAlex, 2026-10-14) · [63](https://md.research.elamur.ai/free/en/papers/eisner-2002-parameter-estimation-probabilistic-finite-state/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
Weighted finite-state transducers (FSTs) are a convenient declarative tool for statistical NLP: models for tagging, segmentation, alignment, speech recognition or noisy-channel translation can be compiled from regular expressions and combined with operations like composition, union and closure. Toolkits had no built-in way to learn the weights, however. Practitioners trained them with external, model-specific algorithms such as forward-backward for HMMs and attached the results to arcs afterward. Eisner proposes "parameterized finite-state machines," in which arc weights are functions of a small set of underlying parameters, even after composition and other operations tie those parameters together in complex ways. Training means fitting these parameters to (possibly partially observed) input/output data. The central device is the "expectation semiring," which carries each weight together with a vector of expectations or gradients. Ordinary finite-state algorithms then produce training statistics as a side effect. The paper also shows how to make the computation efficient. The result is a single general recipe, EM or gradient-based, covering cyclic, epsilon-containing machines and whole noisy-channel cascades.

## Key points
- Running example: Fig. 1a has 17 arc and stop weights. Requiring it to stay Markovian leaves 13 free parameters. Viewing it as a composition of Fig. 1b and Fig. 1c reduces this to 6 (5 + 1). Describing Fig. 1b with a probabilistic regexp brings the total down to just 4 (λ, µ, ν, ρ).
- Theorem: for weighted regular relations, three properties coincide:
  - being a joint probabilistic relation,
  - being computable by some Markovian FST whose probability of eventually stopping is 1,
  - being expressible as a probabilistic regexp built with concatenation, probabilistic union and probabilistic closure.
- Normalization of positively weighted FSTs can be done in two ways:
  - Per-state normalization is simple but suffers from "label bias" and leaks probability mass at dead ends.
  - Global normalization divides by the total path weight, or by a determinized, reciprocal-weighted domain machine in the conditional case.
- Efficiency comes from three choices:
  - Training needs only the single-source algebraic path problem, which is roughly O(m) for acyclic graphs, rather than all-pairs epsilon-closure.
  - A reinstated backward pass avoids costly vector operations.
  - A Viterbi variant runs in O(m + n log n).
- Claimed new capabilities include:
  - EM for FSTs with cycles and epsilons,
  - HMM and contextual edit-distance training on incomplete data,
  - end-to-end training of noisy-channel cascades,
  - discriminative training,
  - training of MEMMs and CRFs on unbounded sequences.

## Interesting ideas
- **Expectation semiring.** Each weight is paired with a vector, and multiplication follows the product rule, so any existing semiring algorithm also returns gradients or expected counts. This is essentially forward-mode differentiation hidden inside the algebra. It could be reused in any dynamic program built on semirings, such as parsers or lattice rescoring.
- **Separating parameters from arc weights.** Composition multiplies arc counts but only adds parameter counts, so optimizing the underlying parameters keeps models compact and well constrained. This is a useful design principle for any compiled or composed model.
- **End-to-end training of cascades.** A pipeline of conditional machines can be trained jointly from observations at its two ends only, with no separate labeled data for each stage. This suits pipelines where intermediate annotations are expensive.
- **Reintroducing a backward pass.** Pushing gradient vectors forward is general but slow because the vectors lose sparsity. Computing scalar forward and backward probabilities and then combining them per edge recovers forward-backward efficiency. This is a good template for trading generality against speed.
- **Matching the algorithm to the query.** Solving only the single-source path problem, rather than all-pairs, and exploiting acyclic structure or Tarjan-style decomposition of hard subgraphs gives large savings. It is a reminder to check which quantity is actually needed before reaching for a generic operation.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Johns Hopkins University](https://md.research.elamur.ai/free/en/universities/johns-hopkins-university/) — University, Baltimore, United States · 187 works · 92,194 citations

📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,085 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,888 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 116 works

## Cite

Cite as: Jason Eisner. 2002. Parameter Estimation for Probabilistic Finite-State Transducers. Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{eisner2002parameter,
  title = {{Parameter Estimation for Probabilistic Finite-State Transducers}},
  author = {Jason Eisner},
  booktitle = {Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics},
  year = {2002},
  doi = {10.3115/1073083.1073085},
  url = {https://doi.org/10.3115/1073083.1073085}
}
```

- [← previous Entropy Rate Constancy in Text](https://md.research.elamur.ai/free/en/papers/genzel-2002-entropy-rate-constancy-text/)
- [next → The LinGO Redwoods Treebank: Motivation and Preliminary Applications](https://md.research.elamur.ai/free/en/papers/oepen-2002-lingo-redwoods-treebank-motivation-preliminary/)
- [↑ back to papers of 2002](https://md.research.elamur.ai/free/en/papers/2002/)

## References

31 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. L. E. Baum. 1972. An inequality and associated maximization technique in statistical estimation of probabilistic functions of a Markov process. Inequalities, 3. [find](https://scholar.google.com/scholar?q=L%2E+E%2E+Baum%2E+1972%2E+An+inequality+and+associated+maximization+technique+in+statistical+estimation+of+probabilistic+functions+of+a+Markov+process%2E+Inequalities%2C+3%2E)
2. Jean Berstel and Christophe Reutenauer. 1988. Rational Series and their Languages. Springer-Verlag. [find](https://scholar.google.com/scholar?q=Jean+Berstel+and+Christophe+Reutenauer%2E+1988%2E+Rational+Series+and+their+Languages%2E+Springer%2DVerlag%2E)
3. Stanley F. Chen and Ronald Rosenfeld. 1999. A Gaussian prior for smoothing maximum entropy models. Technical Report CMU-CS-99-108, Carnegie Mellon. [find](https://scholar.google.com/scholar?q=Stanley+F%2E+Chen+and+Ronald+Rosenfeld%2E+1999%2E+A+Gaussian+prior+for+smoothing+maximum+entropy+models%2E+Technical+Report+CMU%2DCS%2D99%2D108%2C+Carnegie+Mellon%2E)
4. S. Della Pietra, V. Della Pietra, and J. Lafferty. 1997. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(4). [find](https://scholar.google.com/scholar?q=S%2E+Della+Pietra%2C+V%2E+Della+Pietra%2C+and+J%2E+Lafferty%2E+1997%2E+Inducing+features+of+random+fields%2E+IEEE+Transactions+on+Pattern+Analysis+and+Machine+Intelligence%2C+19%284%29%2E)
5. A. P. Dempster, N. M. Laird, and D. B. Rubin. 1977. Maximum likelihood from incomplete data via the EM algorithm. J. Royal Statist. Soc. Ser. B, 39(1):1–38. [find](https://scholar.google.com/scholar?q=A%2E+P%2E+Dempster%2C+N%2E+M%2E+Laird%2C+and+D%2E+B%2E+Rubin%2E+1977%2E+Maximum+likelihood+from+incomplete+data+via+the+EM+algorithm%2E+J%2E+Royal+Statist%2E+Soc%2E+Ser%2E+B%2C+39%281%29%3A1%E2%80%9338%2E)
6. Jason Eisner. 2001a. Expectation semirings: Flexible EM for finite-state transducers. In G. van Noord, ed., Proc. of the ESSLLI Workshop on Finite-State Methods in Natural Language Processing. Extended abstract. [find](https://scholar.google.com/scholar?q=Jason+Eisner%2E+2001a%2E+Expectation+semirings%3A+Flexible+EM+for+finite%2Dstate+transducers%2E+In+G%2E+van+Noord%2C+ed%2E%2C+Proc%2E+of+the+ESSLLI+Workshop+on+Finite%2DState+Methods+in+Natural+Language+Processing%2E+Extende)
7. Jason Eisner. 2001b. Smoothing a Probabilistic Lexicon via Syntactic Transformations. Ph.D. thesis, University of Pennsylvania. [find](https://scholar.google.com/scholar?q=Jason+Eisner%2E+2001b%2E+Smoothing+a+Probabilistic+Lexicon+via+Syntactic+Transformations%2E+Ph%2ED%2E+thesis%2C+University+of+Pennsylvania%2E)
8. D. Gerdemann and G. van Noord. 1999. Transducers from rewrite rules with backreferences. Proc. of EACL. [find](https://scholar.google.com/scholar?q=D%2E+Gerdemann+and+G%2E+van+Noord%2E+1999%2E+Transducers+from+rewrite+rules+with+backreferences%2E+Proc%2E+of+EACL%2E)
9. Anne Greenbaum. 1997. Iterative Methods for Solving Linear Systems. Soc. for Industrial and Applied Math. [find](https://scholar.google.com/scholar?q=Anne+Greenbaum%2E+1997%2E+Iterative+Methods+for+Solving+Linear+Systems%2E+Soc%2E+for+Industrial+and+Applied+Math%2E)
10. Kevin Knight and Yaser Al-Onaizan. 1998. Translation with finite-state devices. In Proc. of AMTA. [find](https://scholar.google.com/scholar?q=Kevin+Knight+and+Yaser+Al%2DOnaizan%2E+1998%2E+Translation+with+finite%2Dstate+devices%2E+In+Proc%2E+of+AMTA%2E)
11. Kevin Knight and Jonathan Graehl. 1998. [Machine transliteration](https://md.research.elamur.ai/free/en/papers/knight-1998-machine-transliteration/). Computational Linguistics, 24(4).
12. J. Lafferty, A. McCallum, and F. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. Proc. of ICML. [find](https://scholar.google.com/scholar?q=J%2E+Lafferty%2C+A%2E+McCallum%2C+and+F%2E+Pereira%2E+2001%2E+Conditional+random+fields%3A+Probabilistic+models+for+segmenting+and+labeling+sequence+data%2E+Proc%2E+of+ICML%2E)
13. D. J. Lehmann. 1977. Algebraic structures for transitive closure. Theoretical Computer Science, 4(1):59–76. [find](https://scholar.google.com/scholar?q=D%2E+J%2E+Lehmann%2E+1977%2E+Algebraic+structures+for+transitive+closure%2E+Theoretical+Computer+Science%2C+4%281%29%3A59%E2%80%9376%2E)
14. A. McCallum, D. Freitag, and F. Pereira. 2000. Maximum entropy Markov models for information extraction and segmentation. Proc. of ICML, 591–598. [find](https://scholar.google.com/scholar?q=A%2E+McCallum%2C+D%2E+Freitag%2C+and+F%2E+Pereira%2E+2000%2E+Maximum+entropy+Markov+models+for+information+extraction+and+segmentation%2E+Proc%2E+of+ICML%2C+591%E2%80%93598%2E)
15. M. Mohri and M.-J. Nederhof. 2001. Regular approximation of context-free grammars through transformation. In J.-C. Junqua and G. van Noord, eds., Robustness in Language and Speech Technology. Kluwer. [find](https://scholar.google.com/scholar?q=M%2E+Mohri+and+M%2E%2DJ%2E+Nederhof%2E+2001%2E+Regular+approximation+of+context%2Dfree+grammars+through+transformation%2E+In+J%2E%2DC%2E+Junqua+and+G%2E+van+Noord%2C+eds%2E%2C+Robustness+in+Language+and+Speech+Technology%2E+Kluwer%2E)
16. Mehryar Mohri and Richard Sproat. 1996. An efficient compiler for weighted rewrite rules. In Proc. of ACL. [find](https://scholar.google.com/scholar?q=Mehryar+Mohri+and+Richard+Sproat%2E+1996%2E+An+efficient+compiler+for+weighted+rewrite+rules%2E+In+Proc%2E+of+ACL%2E)
17. M. Mohri, F. Pereira, and M. Riley. 1998. A rational design for a weighted finite-state transducer library. Lecture Notes in Computer Science, 1436. [find](https://scholar.google.com/scholar?q=M%2E+Mohri%2C+F%2E+Pereira%2C+and+M%2E+Riley%2E+1998%2E+A+rational+design+for+a+weighted+finite%2Dstate+transducer+library%2E+Lecture+Notes+in+Computer+Science%2C+1436%2E)
18. M. Mohri. 2002. Generic epsilon-removal and input epsilon-normalization algorithms for weighted transducers. Int. J. of Foundations of Comp. Sci., 1(13). [find](https://scholar.google.com/scholar?q=M%2E+Mohri%2E+2002%2E+Generic+epsilon%2Dremoval+and+input+epsilon%2Dnormalization+algorithms+for+weighted+transducers%2E+Int%2E+J%2E+of+Foundations+of+Comp%2E+Sci%2E%2C+1%2813%29%2E)
19. Mark-Jan Nederhof. 2000. Practical experiments with regular approximation of context-free languages. Computational Linguistics, 26(1). [find](https://scholar.google.com/scholar?q=Mark%2DJan+Nederhof%2E+2000%2E+Practical+experiments+with+regular+approximation+of+context%2Dfree+languages%2E+Computational+Linguistics%2C+26%281%29%2E)
20. Fernando C. N. Pereira and Michael Riley. 1997. Speech recognition by composition of weighted finite automata. In E. Roche and Y. Schabes, eds., Finite-State Language Processing. MIT Press, Cambridge, MA. [find](https://scholar.google.com/scholar?q=Fernando+C%2E+N%2E+Pereira+and+Michael+Riley%2E+1997%2E+Speech+recognition+by+composition+of+weighted+finite+automata%2E+In+E%2E+Roche+and+Y%2E+Schabes%2C+eds%2E%2C+Finite%2DState+Language+Processing%2E+MIT+Press%2C+Cambridge%2C)
21. A. Rao and K. Rose. 2001 Deterministically annealed design of hidden Markov movel speech recognizers. In IEEE Trans. on Speech and Audio Processing, 9(2). [find](https://scholar.google.com/scholar?q=A%2E+Rao+and+K%2E+Rose%2E+2001+Deterministically+annealed+design+of+hidden+Markov+movel+speech+recognizers%2E+In+IEEE+Trans%2E+on+Speech+and+Audio+Processing%2C+9%282%29%2E)
22. Stefan Riezler. 1999. Probabilistic Constraint Logic Programming. Ph.D. thesis, Universität Tübingen. [find](https://scholar.google.com/scholar?q=Stefan+Riezler%2E+1999%2E+Probabilistic+Constraint+Logic+Programming%2E+Ph%2ED%2E+thesis%2C+Universita%CC%88t+Tu%CC%88bingen%2E)
23. E. Ristad and P. Yianilos. 1996. Learning string edit distance. Tech. Report CS-TR-532-96, Princeton. [find](https://scholar.google.com/scholar?q=E%2E+Ristad+and+P%2E+Yianilos%2E+1996%2E+Learning+string+edit+distance%2E+Tech%2E+Report+CS%2DTR%2D532%2D96%2C+Princeton%2E)
24. E. Ristad. 1998. Hidden Markov models with finite state supervision. In A. Kornai, ed., Extended Finite State Models of Language. Cambridge University Press. [find](https://scholar.google.com/scholar?q=E%2E+Ristad%2E+1998%2E+Hidden+Markov+models+with+finite+state+supervision%2E+In+A%2E+Kornai%2C+ed%2E%2C+Extended+Finite+State+Models+of+Language%2E+Cambridge+University+Press%2E)
25. Emmanuel Roche and Yves Schabes, editors. 1997. Finite-State Language Processing. MIT Press. [find](https://scholar.google.com/scholar?q=Emmanuel+Roche+and+Yves+Schabes%2C+editors%2E+1997%2E+Finite%2DState+Language+Processing%2E+MIT+Press%2E)
26. Günter Rote. 1985. A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion). Computing, 34(3):191–219. [find](https://scholar.google.com/scholar?q=Gu%CC%88nter+Rote%2E+1985%2E+A+systolic+array+algorithm+for+the+algebraic+path+problem+%28shortest+paths%3B+matrix+inversion%29%2E+Computing%2C+34%283%29%3A191%E2%80%93219%2E)
27. Richard Sproat and Michael Riley. 1996. Compilation of weighted finite-state transducers from decision trees. In Proceedings of the 34th Annual Meeting of the ACL. [find](https://scholar.google.com/scholar?q=Richard+Sproat+and+Michael+Riley%2E+1996%2E+Compilation+of+weighted+finite%2Dstate+transducers+from+decision+trees%2E+In+Proceedings+of+the+34th+Annual+Meeting+of+the+ACL%2E)
28. Andreas Stolcke and Stephen M. Omohundro. 1994. Best-first model merging for hidden Markov model induction. Tech. Report ICSI TR-94-003, Berkeley, CA. [find](https://scholar.google.com/scholar?q=Andreas+Stolcke+and+Stephen+M%2E+Omohundro%2E+1994%2E+Best%2Dfirst+model+merging+for+hidden+Markov+model+induction%2E+Tech%2E+Report+ICSI+TR%2D94%2D003%2C+Berkeley%2C+CA%2E)
29. Robert Endre Tarjan. 1981a. A unified approach to path problems. Journal of the ACM, 28(3):577–593, July. [find](https://scholar.google.com/scholar?q=Robert+Endre+Tarjan%2E+1981a%2E+A+unified+approach+to+path+problems%2E+Journal+of+the+ACM%2C+28%283%29%3A577%E2%80%93593%2C+July%2E)
30. Robert Endre Tarjan. 1981b. Fast algorithms for solving path problems. J. of the ACM, 28(3):594–614, July. [find](https://scholar.google.com/scholar?q=Robert+Endre+Tarjan%2E+1981b%2E+Fast+algorithms+for+solving+path+problems%2E+J%2E+of+the+ACM%2C+28%283%29%3A594%E2%80%93614%2C+July%2E)
31. G. van Noord and D. Gerdemann. 2001. An extendible regular expression compiler for finite-state approaches in natural language processing. In Automata Implementation, no. 22 in Springer Lecture Notes in CS. [find](https://scholar.google.com/scholar?q=G%2E+van+Noord+and+D%2E+Gerdemann%2E+2001%2E+An+extendible+regular+expression+compiler+for+finite%2Dstate+approaches+in+natural+language+processing%2E+In+Automata+Implementation%2C+no%2E+22+in+Springer+Lecture+Notes+)

*Updated 24 October 2026*