Abstract
In natural language processing, a common task is to compute the probability of a phrase appearing in a document or to calculate the probability of all phrases matching a given pattern. For instance, one computes affix (prefix, suffix, infix, etc.) probabilities of a string or a set of strings with respect to a probability distribution of patterns. The problem of computing infix probabilities of strings when the pattern distribution is given by a probabilistic context-free grammar or by a probabilistic finite automaton is already solved, yet it was open to compute the infix probabilities in an incremental manner. The incremental computation is crucial when a new query is built from a previous query. We tackle this problem and suggest a method that computes infix probabilities incrementally for probabilistic finite automata by representing all the probabilities of matching strings as a series of transition matrix calculations. We show that the proposed approach is theoretically faster than the previous method and, using real world data, demonstrate that our approach has vastly better performance in practice.- Anthology ID:
- D18-1293
- Volume:
- Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing
- Month:
- October-November
- Year:
- 2018
- Address:
- Brussels, Belgium
- Editors:
- Ellen Riloff, David Chiang, Julia Hockenmaier, Jun’ichi Tsujii
- Venue:
- EMNLP
- SIG:
- SIGDAT
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 2732–2741
- Language:
- URL:
- https://aclanthology.org/D18-1293
- DOI:
- 10.18653/v1/D18-1293
- Cite (ACL):
- Marco Cognetta, Yo-Sub Han, and Soon Chan Kwon. 2018. Incremental Computation of Infix Probabilities for Probabilistic Finite Automata. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 2732–2741, Brussels, Belgium. Association for Computational Linguistics.
- Cite (Informal):
- Incremental Computation of Infix Probabilities for Probabilistic Finite Automata (Cognetta et al., EMNLP 2018)
- PDF:
- https://preview.aclanthology.org/improve-issue-templates/D18-1293.pdf