Elamur Research⌕
☰
home / papers / 2002 / Parameter Estimation for Probabilistic Finite-State Transducers

Parameter Estimation for Probabilistic Finite-State Transducers

Paper · 2002 · Jason Eisner

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

  • I1. 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.
  • I2. 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.
  • I3. 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.
  • I4. 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.
  • I5. 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 UniversityBaltimore · United States187 works · 92,194 citations

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 worksComputational 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. DOI 10.3115/1073083.1073085

@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}
}

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
  2. Jean Berstel and Christophe Reutenauer. 1988. Rational Series and their Languages. Springer-Verlag. find
  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
  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
  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
  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
  7. Jason Eisner. 2001b. Smoothing a Probabilistic Lexicon via Syntactic Transformations. Ph.D. thesis, University of Pennsylvania. find
  8. D. Gerdemann and G. van Noord. 1999. Transducers from rewrite rules with backreferences. Proc. of EACL. find
  9. Anne Greenbaum. 1997. Iterative Methods for Solving Linear Systems. Soc. for Industrial and Applied Math. find
  10. Kevin Knight and Yaser Al-Onaizan. 1998. Translation with finite-state devices. In Proc. of AMTA. find
  11. Kevin Knight and Jonathan Graehl. 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
  13. D. J. Lehmann. 1977. Algebraic structures for transitive closure. Theoretical Computer Science, 4(1):59–76. find
  14. A. McCallum, D. Freitag, and F. Pereira. 2000. Maximum entropy Markov models for information extraction and segmentation. Proc. of ICML, 591–598. find
  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
  16. Mehryar Mohri and Richard Sproat. 1996. An efficient compiler for weighted rewrite rules. In Proc. of ACL. find
  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
  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
  19. Mark-Jan Nederhof. 2000. Practical experiments with regular approximation of context-free languages. Computational Linguistics, 26(1). find
  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
  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
  22. Stefan Riezler. 1999. Probabilistic Constraint Logic Programming. Ph.D. thesis, Universität Tübingen. find
  23. E. Ristad and P. Yianilos. 1996. Learning string edit distance. Tech. Report CS-TR-532-96, Princeton. find
  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
  25. Emmanuel Roche and Yves Schabes, editors. 1997. Finite-State Language Processing. MIT Press. find
  26. Günter Rote. 1985. A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion). Computing, 34(3):191–219. find
  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
  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
  29. Robert Endre Tarjan. 1981a. A unified approach to path problems. Journal of the ACM, 28(3):577–593, July. find
  30. Robert Endre Tarjan. 1981b. Fast algorithms for solving path problems. J. of the ACM, 28(3):594–614, July. find
  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

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/eisner-2002-parameter-estimation-probabilistic-finite-state/