Abstract
Probabilistic finite automata (PFAs) are com- mon statistical language model in natural lan- guage and speech processing. A typical task for PFAs is to compute the probability of all strings that match a query pattern. An impor- tant special case of this problem is computing the probability of a string appearing as a pre- fix, suffix, or infix. These problems find use in many natural language processing tasks such word prediction and text error correction. Recently, we gave the first incremental algorithm to efficiently compute the infix probabilities of each prefix of a string (Cognetta et al., 2018). We develop an asymptotic improvement of that algorithm and solve the open problem of computing the infix probabilities of PFAs from streaming data, which is crucial when process- ing queries online and is the ultimate goal of the incremental approach.- Anthology ID:
- P19-1528
- Volume:
- Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics
- Month:
- July
- Year:
- 2019
- Address:
- Florence, Italy
- Venue:
- ACL
- SIG:
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 5332–5337
- Language:
- URL:
- https://aclanthology.org/P19-1528
- DOI:
- 10.18653/v1/P19-1528
- Cite (ACL):
- Marco Cognetta, Yo-Sub Han, and Soon Chan Kwon. 2019. Online Infix Probability Computation for Probabilistic Finite Automata. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5332–5337, Florence, Italy. Association for Computational Linguistics.
- Cite (Informal):
- Online Infix Probability Computation for Probabilistic Finite Automata (Cognetta et al., ACL 2019)
- PDF:
- https://preview.aclanthology.org/ingestion-script-update/P19-1528.pdf